1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
53 /// makeVTList - Return an instance of the SDVTList struct initialized with the
54 /// specified members.
55 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
56 SDVTList Res = {VTs, NumVTs};
60 // Default null implementations of the callbacks.
61 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
62 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
64 //===----------------------------------------------------------------------===//
65 // ConstantFPSDNode Class
66 //===----------------------------------------------------------------------===//
68 /// isExactlyValue - We don't rely on operator== working on double values, as
69 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
70 /// As such, this method can be used to do an exact bit-for-bit comparison of
71 /// two floating point values.
72 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
73 return getValueAPF().bitwiseIsEqual(V);
76 bool ConstantFPSDNode::isValueValidForType(EVT VT,
78 assert(VT.isFloatingPoint() && "Can only convert between FP types");
80 // convert modifies in place, so make a copy.
81 APFloat Val2 = APFloat(Val);
83 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
84 APFloat::rmNearestTiesToEven,
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 /// isBuildVectorAllOnes - Return true if the specified node is a
94 /// BUILD_VECTOR where all of the elements are ~0 or undef.
95 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96 // Look through a bit convert.
97 if (N->getOpcode() == ISD::BITCAST)
98 N = N->getOperand(0).getNode();
100 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
102 unsigned i = 0, e = N->getNumOperands();
104 // Skip over all of the undef values.
105 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 // Do not accept an all-undef vector.
109 if (i == e) return false;
111 // Do not accept build_vectors that aren't all constants or which have non-~0
112 // elements. We have to be a bit careful here, as the type of the constant
113 // may not be the same as the type of the vector elements due to type
114 // legalization (the elements are promoted to a legal type for the target and
115 // a vector of a type may be legal when the base element type is not).
116 // We only want to check enough bits to cover the vector elements, because
117 // we care if the resultant vector is all ones, not whether the individual
119 SDValue NotZero = N->getOperand(i);
120 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
121 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
122 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
124 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
125 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
130 // Okay, we have at least one ~0 value, check to see if the rest match or are
131 // undefs. Even with the above element type twiddling, this should be OK, as
132 // the same type legalization should have applied to all the elements.
133 for (++i; i != e; ++i)
134 if (N->getOperand(i) != NotZero &&
135 N->getOperand(i).getOpcode() != ISD::UNDEF)
141 /// isBuildVectorAllZeros - Return true if the specified node is a
142 /// BUILD_VECTOR where all of the elements are 0 or undef.
143 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
144 // Look through a bit convert.
145 if (N->getOpcode() == ISD::BITCAST)
146 N = N->getOperand(0).getNode();
148 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
150 unsigned i = 0, e = N->getNumOperands();
152 // Skip over all of the undef values.
153 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept an all-undef vector.
157 if (i == e) return false;
159 // Do not accept build_vectors that aren't all constants or which have non-0
161 SDValue Zero = N->getOperand(i);
162 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
163 if (!CN->isNullValue())
165 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
166 if (!CFPN->getValueAPF().isPosZero())
171 // Okay, we have at least one 0 value, check to see if the rest match or are
173 for (++i; i != e; ++i)
174 if (N->getOperand(i) != Zero &&
175 N->getOperand(i).getOpcode() != ISD::UNDEF)
180 /// \brief Return true if the specified node is a BUILD_VECTOR node of
181 /// all ConstantSDNode or undef.
182 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
183 if (N->getOpcode() != ISD::BUILD_VECTOR)
186 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
187 SDValue Op = N->getOperand(i);
188 if (Op.getOpcode() == ISD::UNDEF)
190 if (!isa<ConstantSDNode>(Op))
196 /// isScalarToVector - Return true if the specified node is a
197 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
198 /// element is not an undef.
199 bool ISD::isScalarToVector(const SDNode *N) {
200 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
207 unsigned NumElems = N->getNumOperands();
210 for (unsigned i = 1; i < NumElems; ++i) {
211 SDValue V = N->getOperand(i);
212 if (V.getOpcode() != ISD::UNDEF)
218 /// allOperandsUndef - Return true if the node has at least one operand
219 /// and all operands of the specified node are ISD::UNDEF.
220 bool ISD::allOperandsUndef(const SDNode *N) {
221 // Return false if the node has no operands.
222 // This is "logically inconsistent" with the definition of "all" but
223 // is probably the desired behavior.
224 if (N->getNumOperands() == 0)
227 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
228 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
234 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
237 return ISD::ANY_EXTEND;
239 return ISD::SIGN_EXTEND;
241 return ISD::ZERO_EXTEND;
246 llvm_unreachable("Invalid LoadExtType");
249 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
250 /// when given the operation for (X op Y).
251 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
252 // To perform this operation, we just need to swap the L and G bits of the
254 unsigned OldL = (Operation >> 2) & 1;
255 unsigned OldG = (Operation >> 1) & 1;
256 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
257 (OldL << 1) | // New G bit
258 (OldG << 2)); // New L bit.
261 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
262 /// 'op' is a valid SetCC operation.
263 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
264 unsigned Operation = Op;
266 Operation ^= 7; // Flip L, G, E bits, but not U.
268 Operation ^= 15; // Flip all of the condition bits.
270 if (Operation > ISD::SETTRUE2)
271 Operation &= ~8; // Don't let N and U bits get set.
273 return ISD::CondCode(Operation);
277 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
278 /// signed operation and 2 if the result is an unsigned comparison. Return zero
279 /// if the operation does not depend on the sign of the input (setne and seteq).
280 static int isSignedOp(ISD::CondCode Opcode) {
282 default: llvm_unreachable("Illegal integer setcc operation!");
284 case ISD::SETNE: return 0;
288 case ISD::SETGE: return 1;
292 case ISD::SETUGE: return 2;
296 /// getSetCCOrOperation - Return the result of a logical OR between different
297 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
298 /// returns SETCC_INVALID if it is not possible to represent the resultant
300 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
302 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
303 // Cannot fold a signed integer setcc with an unsigned integer setcc.
304 return ISD::SETCC_INVALID;
306 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
308 // If the N and U bits get set then the resultant comparison DOES suddenly
309 // care about orderedness, and is true when ordered.
310 if (Op > ISD::SETTRUE2)
311 Op &= ~16; // Clear the U bit if the N bit is set.
313 // Canonicalize illegal integer setcc's.
314 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
317 return ISD::CondCode(Op);
320 /// getSetCCAndOperation - Return the result of a logical AND between different
321 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
322 /// function returns zero if it is not possible to represent the resultant
324 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
326 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
327 // Cannot fold a signed setcc with an unsigned setcc.
328 return ISD::SETCC_INVALID;
330 // Combine all of the condition bits.
331 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
333 // Canonicalize illegal integer setcc's.
337 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
338 case ISD::SETOEQ: // SETEQ & SETU[LG]E
339 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
340 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
341 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
348 //===----------------------------------------------------------------------===//
349 // SDNode Profile Support
350 //===----------------------------------------------------------------------===//
352 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
354 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
359 /// solely with their pointer.
360 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
361 ID.AddPointer(VTList.VTs);
364 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
366 static void AddNodeIDOperands(FoldingSetNodeID &ID,
367 ArrayRef<SDValue> Ops) {
368 for (auto& Op : Ops) {
369 ID.AddPointer(Op.getNode());
370 ID.AddInteger(Op.getResNo());
374 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
376 static void AddNodeIDOperands(FoldingSetNodeID &ID,
377 ArrayRef<SDUse> Ops) {
378 for (auto& Op : Ops) {
379 ID.AddPointer(Op.getNode());
380 ID.AddInteger(Op.getResNo());
384 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
385 SDVTList VTList, ArrayRef<SDValue> OpList) {
386 AddNodeIDOpcode(ID, OpC);
387 AddNodeIDValueTypes(ID, VTList);
388 AddNodeIDOperands(ID, OpList);
391 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
393 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
394 switch (N->getOpcode()) {
395 case ISD::TargetExternalSymbol:
396 case ISD::ExternalSymbol:
397 llvm_unreachable("Should only be used on nodes with operands");
398 default: break; // Normal nodes don't need extra info.
399 case ISD::TargetConstant:
400 case ISD::Constant: {
401 const ConstantSDNode *C = cast<ConstantSDNode>(N);
402 ID.AddPointer(C->getConstantIntValue());
403 ID.AddBoolean(C->isOpaque());
406 case ISD::TargetConstantFP:
407 case ISD::ConstantFP: {
408 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
411 case ISD::TargetGlobalAddress:
412 case ISD::GlobalAddress:
413 case ISD::TargetGlobalTLSAddress:
414 case ISD::GlobalTLSAddress: {
415 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
416 ID.AddPointer(GA->getGlobal());
417 ID.AddInteger(GA->getOffset());
418 ID.AddInteger(GA->getTargetFlags());
419 ID.AddInteger(GA->getAddressSpace());
422 case ISD::BasicBlock:
423 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
426 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
428 case ISD::RegisterMask:
429 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
432 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
434 case ISD::FrameIndex:
435 case ISD::TargetFrameIndex:
436 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
439 case ISD::TargetJumpTable:
440 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
441 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
443 case ISD::ConstantPool:
444 case ISD::TargetConstantPool: {
445 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
446 ID.AddInteger(CP->getAlignment());
447 ID.AddInteger(CP->getOffset());
448 if (CP->isMachineConstantPoolEntry())
449 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
451 ID.AddPointer(CP->getConstVal());
452 ID.AddInteger(CP->getTargetFlags());
455 case ISD::TargetIndex: {
456 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
457 ID.AddInteger(TI->getIndex());
458 ID.AddInteger(TI->getOffset());
459 ID.AddInteger(TI->getTargetFlags());
463 const LoadSDNode *LD = cast<LoadSDNode>(N);
464 ID.AddInteger(LD->getMemoryVT().getRawBits());
465 ID.AddInteger(LD->getRawSubclassData());
466 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
470 const StoreSDNode *ST = cast<StoreSDNode>(N);
471 ID.AddInteger(ST->getMemoryVT().getRawBits());
472 ID.AddInteger(ST->getRawSubclassData());
473 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
476 case ISD::ATOMIC_CMP_SWAP:
477 case ISD::ATOMIC_SWAP:
478 case ISD::ATOMIC_LOAD_ADD:
479 case ISD::ATOMIC_LOAD_SUB:
480 case ISD::ATOMIC_LOAD_AND:
481 case ISD::ATOMIC_LOAD_OR:
482 case ISD::ATOMIC_LOAD_XOR:
483 case ISD::ATOMIC_LOAD_NAND:
484 case ISD::ATOMIC_LOAD_MIN:
485 case ISD::ATOMIC_LOAD_MAX:
486 case ISD::ATOMIC_LOAD_UMIN:
487 case ISD::ATOMIC_LOAD_UMAX:
488 case ISD::ATOMIC_LOAD:
489 case ISD::ATOMIC_STORE: {
490 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
491 ID.AddInteger(AT->getMemoryVT().getRawBits());
492 ID.AddInteger(AT->getRawSubclassData());
493 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
496 case ISD::PREFETCH: {
497 const MemSDNode *PF = cast<MemSDNode>(N);
498 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
501 case ISD::VECTOR_SHUFFLE: {
502 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
503 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
505 ID.AddInteger(SVN->getMaskElt(i));
508 case ISD::TargetBlockAddress:
509 case ISD::BlockAddress: {
510 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
511 ID.AddPointer(BA->getBlockAddress());
512 ID.AddInteger(BA->getOffset());
513 ID.AddInteger(BA->getTargetFlags());
516 } // end switch (N->getOpcode())
518 // Target specific memory nodes could also have address spaces to check.
519 if (N->isTargetMemoryOpcode())
520 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
523 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
525 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
526 AddNodeIDOpcode(ID, N->getOpcode());
527 // Add the return value info.
528 AddNodeIDValueTypes(ID, N->getVTList());
529 // Add the operand info.
530 AddNodeIDOperands(ID, makeArrayRef(N->op_begin(), N->op_end()));
532 // Handle SDNode leafs with special info.
533 AddNodeIDCustom(ID, N);
536 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
537 /// the CSE map that carries volatility, temporalness, indexing mode, and
538 /// extension/truncation information.
540 static inline unsigned
541 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
542 bool isNonTemporal, bool isInvariant) {
543 assert((ConvType & 3) == ConvType &&
544 "ConvType may not require more than 2 bits!");
545 assert((AM & 7) == AM &&
546 "AM may not require more than 3 bits!");
550 (isNonTemporal << 6) |
554 //===----------------------------------------------------------------------===//
555 // SelectionDAG Class
556 //===----------------------------------------------------------------------===//
558 /// doNotCSE - Return true if CSE should not be performed for this node.
559 static bool doNotCSE(SDNode *N) {
560 if (N->getValueType(0) == MVT::Glue)
561 return true; // Never CSE anything that produces a flag.
563 switch (N->getOpcode()) {
565 case ISD::HANDLENODE:
567 return true; // Never CSE these nodes.
570 // Check that remaining values produced are not flags.
571 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
572 if (N->getValueType(i) == MVT::Glue)
573 return true; // Never CSE anything that produces a flag.
578 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
580 void SelectionDAG::RemoveDeadNodes() {
581 // Create a dummy node (which is not added to allnodes), that adds a reference
582 // to the root node, preventing it from being deleted.
583 HandleSDNode Dummy(getRoot());
585 SmallVector<SDNode*, 128> DeadNodes;
587 // Add all obviously-dead nodes to the DeadNodes worklist.
588 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
590 DeadNodes.push_back(I);
592 RemoveDeadNodes(DeadNodes);
594 // If the root changed (e.g. it was a dead load, update the root).
595 setRoot(Dummy.getValue());
598 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
599 /// given list, and any nodes that become unreachable as a result.
600 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
602 // Process the worklist, deleting the nodes and adding their uses to the
604 while (!DeadNodes.empty()) {
605 SDNode *N = DeadNodes.pop_back_val();
607 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
608 DUL->NodeDeleted(N, nullptr);
610 // Take the node out of the appropriate CSE map.
611 RemoveNodeFromCSEMaps(N);
613 // Next, brutally remove the operand list. This is safe to do, as there are
614 // no cycles in the graph.
615 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
617 SDNode *Operand = Use.getNode();
620 // Now that we removed this operand, see if there are no uses of it left.
621 if (Operand->use_empty())
622 DeadNodes.push_back(Operand);
629 void SelectionDAG::RemoveDeadNode(SDNode *N){
630 SmallVector<SDNode*, 16> DeadNodes(1, N);
632 // Create a dummy node that adds a reference to the root node, preventing
633 // it from being deleted. (This matters if the root is an operand of the
635 HandleSDNode Dummy(getRoot());
637 RemoveDeadNodes(DeadNodes);
640 void SelectionDAG::DeleteNode(SDNode *N) {
641 // First take this out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Finally, remove uses due to operands of this node, remove from the
645 // AllNodes list, and delete the node.
646 DeleteNodeNotInCSEMaps(N);
649 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
650 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
651 assert(N->use_empty() && "Cannot delete a node that is not dead!");
653 // Drop all of the operands and decrement used node's use counts.
659 void SelectionDAG::DeallocateNode(SDNode *N) {
660 if (N->OperandsNeedDelete)
661 delete[] N->OperandList;
663 // Set the opcode to DELETED_NODE to help catch bugs when node
664 // memory is reallocated.
665 N->NodeType = ISD::DELETED_NODE;
667 NodeAllocator.Deallocate(AllNodes.remove(N));
669 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
670 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
671 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
672 DbgVals[i]->setIsInvalidated();
675 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
676 /// correspond to it. This is useful when we're about to delete or repurpose
677 /// the node. We don't want future request for structurally identical nodes
678 /// to return N anymore.
679 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
681 switch (N->getOpcode()) {
682 case ISD::HANDLENODE: return false; // noop.
684 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
685 "Cond code doesn't exist!");
686 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
687 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
689 case ISD::ExternalSymbol:
690 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
692 case ISD::TargetExternalSymbol: {
693 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
694 Erased = TargetExternalSymbols.erase(
695 std::pair<std::string,unsigned char>(ESN->getSymbol(),
696 ESN->getTargetFlags()));
699 case ISD::VALUETYPE: {
700 EVT VT = cast<VTSDNode>(N)->getVT();
701 if (VT.isExtended()) {
702 Erased = ExtendedValueTypeNodes.erase(VT);
704 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
705 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
710 // Remove it from the CSE Map.
711 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
712 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
713 Erased = CSEMap.RemoveNode(N);
717 // Verify that the node was actually in one of the CSE maps, unless it has a
718 // flag result (which cannot be CSE'd) or is one of the special cases that are
719 // not subject to CSE.
720 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
721 !N->isMachineOpcode() && !doNotCSE(N)) {
724 llvm_unreachable("Node is not in map!");
730 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
731 /// maps and modified in place. Add it back to the CSE maps, unless an identical
732 /// node already exists, in which case transfer all its users to the existing
733 /// node. This transfer can potentially trigger recursive merging.
736 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
737 // For node types that aren't CSE'd, just act as if no identical node
740 SDNode *Existing = CSEMap.GetOrInsertNode(N);
742 // If there was already an existing matching node, use ReplaceAllUsesWith
743 // to replace the dead one with the existing one. This can cause
744 // recursive merging of other unrelated nodes down the line.
745 ReplaceAllUsesWith(N, Existing);
747 // N is now dead. Inform the listeners and delete it.
748 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
749 DUL->NodeDeleted(N, Existing);
750 DeleteNodeNotInCSEMaps(N);
755 // If the node doesn't already exist, we updated it. Inform listeners.
756 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
760 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
761 /// were replaced with those specified. If this node is never memoized,
762 /// return null, otherwise return a pointer to the slot it would take. If a
763 /// node already exists with these operands, the slot will be non-null.
764 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
769 SDValue Ops[] = { Op };
771 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
772 AddNodeIDCustom(ID, N);
773 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
777 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
778 /// were replaced with those specified. If this node is never memoized,
779 /// return null, otherwise return a pointer to the slot it would take. If a
780 /// node already exists with these operands, the slot will be non-null.
781 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
782 SDValue Op1, SDValue Op2,
787 SDValue Ops[] = { Op1, Op2 };
789 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
790 AddNodeIDCustom(ID, N);
791 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
796 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
797 /// were replaced with those specified. If this node is never memoized,
798 /// return null, otherwise return a pointer to the slot it would take. If a
799 /// node already exists with these operands, the slot will be non-null.
800 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
806 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
807 AddNodeIDCustom(ID, N);
808 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
813 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
814 static void VerifyNodeCommon(SDNode *N) {
815 switch (N->getOpcode()) {
818 case ISD::BUILD_PAIR: {
819 EVT VT = N->getValueType(0);
820 assert(N->getNumValues() == 1 && "Too many results!");
821 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
822 "Wrong return type!");
823 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
824 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
825 "Mismatched operand types!");
826 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
827 "Wrong operand type!");
828 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
829 "Wrong return type size");
832 case ISD::BUILD_VECTOR: {
833 assert(N->getNumValues() == 1 && "Too many results!");
834 assert(N->getValueType(0).isVector() && "Wrong return type!");
835 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
836 "Wrong number of operands!");
837 EVT EltVT = N->getValueType(0).getVectorElementType();
838 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
839 assert((I->getValueType() == EltVT ||
840 (EltVT.isInteger() && I->getValueType().isInteger() &&
841 EltVT.bitsLE(I->getValueType()))) &&
842 "Wrong operand type!");
843 assert(I->getValueType() == N->getOperand(0).getValueType() &&
844 "Operands must all have the same type");
851 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
852 static void VerifySDNode(SDNode *N) {
853 // The SDNode allocators cannot be used to allocate nodes with fields that are
854 // not present in an SDNode!
855 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
856 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
857 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
858 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
859 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
860 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
861 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
862 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
863 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
864 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
865 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
866 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
867 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
868 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
869 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
870 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
871 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
872 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
873 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
878 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
880 static void VerifyMachineNode(SDNode *N) {
881 // The MachineNode allocators cannot be used to allocate nodes with fields
882 // that are not present in a MachineNode!
883 // Currently there are no such nodes.
889 /// getEVTAlignment - Compute the default alignment value for the
892 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
893 Type *Ty = VT == MVT::iPTR ?
894 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
895 VT.getTypeForEVT(*getContext());
897 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
900 // EntryNode could meaningfully have debug info if we can find it...
901 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
902 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
903 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
904 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
905 UpdateListeners(nullptr) {
906 AllNodes.push_back(&EntryNode);
907 DbgInfo = new SDDbgInfo();
910 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
913 Context = &mf.getFunction()->getContext();
916 SelectionDAG::~SelectionDAG() {
917 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
922 void SelectionDAG::allnodes_clear() {
923 assert(&*AllNodes.begin() == &EntryNode);
924 AllNodes.remove(AllNodes.begin());
925 while (!AllNodes.empty())
926 DeallocateNode(AllNodes.begin());
929 void SelectionDAG::clear() {
931 OperandAllocator.Reset();
934 ExtendedValueTypeNodes.clear();
935 ExternalSymbols.clear();
936 TargetExternalSymbols.clear();
937 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
938 static_cast<CondCodeSDNode*>(nullptr));
939 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
940 static_cast<SDNode*>(nullptr));
942 EntryNode.UseList = nullptr;
943 AllNodes.push_back(&EntryNode);
944 Root = getEntryNode();
948 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
949 return VT.bitsGT(Op.getValueType()) ?
950 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
951 getNode(ISD::TRUNCATE, DL, VT, Op);
954 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
955 return VT.bitsGT(Op.getValueType()) ?
956 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
957 getNode(ISD::TRUNCATE, DL, VT, Op);
960 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
961 return VT.bitsGT(Op.getValueType()) ?
962 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
963 getNode(ISD::TRUNCATE, DL, VT, Op);
966 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
967 if (VT.bitsLE(Op.getValueType()))
968 return getNode(ISD::TRUNCATE, SL, VT, Op);
970 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
971 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
974 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
975 assert(!VT.isVector() &&
976 "getZeroExtendInReg should use the vector element type instead of "
978 if (Op.getValueType() == VT) return Op;
979 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
980 APInt Imm = APInt::getLowBitsSet(BitWidth,
982 return getNode(ISD::AND, DL, Op.getValueType(), Op,
983 getConstant(Imm, Op.getValueType()));
986 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
988 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
989 EVT EltVT = VT.getScalarType();
991 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
992 return getNode(ISD::XOR, DL, VT, Val, NegOne);
995 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
996 EVT EltVT = VT.getScalarType();
998 switch (TLI->getBooleanContents(VT.isVector())) {
999 case TargetLowering::ZeroOrOneBooleanContent:
1000 case TargetLowering::UndefinedBooleanContent:
1001 TrueValue = getConstant(1, VT);
1003 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1004 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1008 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1011 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1012 EVT EltVT = VT.getScalarType();
1013 assert((EltVT.getSizeInBits() >= 64 ||
1014 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1015 "getConstant with a uint64_t value that doesn't fit in the type!");
1016 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1019 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1021 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1024 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1026 assert(VT.isInteger() && "Cannot create FP integer constant!");
1028 EVT EltVT = VT.getScalarType();
1029 const ConstantInt *Elt = &Val;
1031 const TargetLowering *TLI = TM.getTargetLowering();
1033 // In some cases the vector type is legal but the element type is illegal and
1034 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1035 // inserted value (the type does not need to match the vector element type).
1036 // Any extra bits introduced will be truncated away.
1037 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1038 TargetLowering::TypePromoteInteger) {
1039 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1040 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1041 Elt = ConstantInt::get(*getContext(), NewVal);
1043 // In other cases the element type is illegal and needs to be expanded, for
1044 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1045 // the value into n parts and use a vector type with n-times the elements.
1046 // Then bitcast to the type requested.
1047 // Legalizing constants too early makes the DAGCombiner's job harder so we
1048 // only legalize if the DAG tells us we must produce legal types.
1049 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1050 TLI->getTypeAction(*getContext(), EltVT) ==
1051 TargetLowering::TypeExpandInteger) {
1052 APInt NewVal = Elt->getValue();
1053 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1054 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1055 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1056 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1058 // Check the temporary vector is the correct size. If this fails then
1059 // getTypeToTransformTo() probably returned a type whose size (in bits)
1060 // isn't a power-of-2 factor of the requested type size.
1061 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1063 SmallVector<SDValue, 2> EltParts;
1064 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1065 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1066 .trunc(ViaEltSizeInBits),
1067 ViaEltVT, isT, isO));
1070 // EltParts is currently in little endian order. If we actually want
1071 // big-endian order then reverse it now.
1072 if (TLI->isBigEndian())
1073 std::reverse(EltParts.begin(), EltParts.end());
1075 // The elements must be reversed when the element order is different
1076 // to the endianness of the elements (because the BITCAST is itself a
1077 // vector shuffle in this situation). However, we do not need any code to
1078 // perform this reversal because getConstant() is producing a vector
1080 // This situation occurs in MIPS MSA.
1082 SmallVector<SDValue, 8> Ops;
1083 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1084 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1086 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1087 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1092 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1093 "APInt size does not match type size!");
1094 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1095 FoldingSetNodeID ID;
1096 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1100 SDNode *N = nullptr;
1101 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1103 return SDValue(N, 0);
1106 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1107 CSEMap.InsertNode(N, IP);
1108 AllNodes.push_back(N);
1111 SDValue Result(N, 0);
1112 if (VT.isVector()) {
1113 SmallVector<SDValue, 8> Ops;
1114 Ops.assign(VT.getVectorNumElements(), Result);
1115 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1120 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1121 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1125 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1126 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1129 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1130 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1132 EVT EltVT = VT.getScalarType();
1134 // Do the map lookup using the actual bit pattern for the floating point
1135 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1136 // we don't have issues with SNANs.
1137 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1138 FoldingSetNodeID ID;
1139 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1142 SDNode *N = nullptr;
1143 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1145 return SDValue(N, 0);
1148 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1149 CSEMap.InsertNode(N, IP);
1150 AllNodes.push_back(N);
1153 SDValue Result(N, 0);
1154 if (VT.isVector()) {
1155 SmallVector<SDValue, 8> Ops;
1156 Ops.assign(VT.getVectorNumElements(), Result);
1157 // FIXME SDLoc info might be appropriate here
1158 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1163 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1164 EVT EltVT = VT.getScalarType();
1165 if (EltVT==MVT::f32)
1166 return getConstantFP(APFloat((float)Val), VT, isTarget);
1167 else if (EltVT==MVT::f64)
1168 return getConstantFP(APFloat(Val), VT, isTarget);
1169 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1172 APFloat apf = APFloat(Val);
1173 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1175 return getConstantFP(apf, VT, isTarget);
1177 llvm_unreachable("Unsupported type in getConstantFP");
1180 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1181 EVT VT, int64_t Offset,
1183 unsigned char TargetFlags) {
1184 assert((TargetFlags == 0 || isTargetGA) &&
1185 "Cannot set target flags on target-independent globals");
1186 const TargetLowering *TLI = TM.getTargetLowering();
1188 // Truncate (with sign-extension) the offset value to the pointer size.
1189 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1191 Offset = SignExtend64(Offset, BitWidth);
1193 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1195 // If GV is an alias then use the aliasee for determining thread-localness.
1196 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1197 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1201 if (GVar && GVar->isThreadLocal())
1202 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1204 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1206 FoldingSetNodeID ID;
1207 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1209 ID.AddInteger(Offset);
1210 ID.AddInteger(TargetFlags);
1211 ID.AddInteger(GV->getType()->getAddressSpace());
1213 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1214 return SDValue(E, 0);
1216 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1217 DL.getDebugLoc(), GV, VT,
1218 Offset, TargetFlags);
1219 CSEMap.InsertNode(N, IP);
1220 AllNodes.push_back(N);
1221 return SDValue(N, 0);
1224 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1225 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1226 FoldingSetNodeID ID;
1227 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1230 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1231 return SDValue(E, 0);
1233 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1234 CSEMap.InsertNode(N, IP);
1235 AllNodes.push_back(N);
1236 return SDValue(N, 0);
1239 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1240 unsigned char TargetFlags) {
1241 assert((TargetFlags == 0 || isTarget) &&
1242 "Cannot set target flags on target-independent jump tables");
1243 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1244 FoldingSetNodeID ID;
1245 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1247 ID.AddInteger(TargetFlags);
1249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1250 return SDValue(E, 0);
1252 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1254 CSEMap.InsertNode(N, IP);
1255 AllNodes.push_back(N);
1256 return SDValue(N, 0);
1259 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1260 unsigned Alignment, int Offset,
1262 unsigned char TargetFlags) {
1263 assert((TargetFlags == 0 || isTarget) &&
1264 "Cannot set target flags on target-independent globals");
1267 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1268 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1269 FoldingSetNodeID ID;
1270 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1271 ID.AddInteger(Alignment);
1272 ID.AddInteger(Offset);
1274 ID.AddInteger(TargetFlags);
1276 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1277 return SDValue(E, 0);
1279 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1280 Alignment, TargetFlags);
1281 CSEMap.InsertNode(N, IP);
1282 AllNodes.push_back(N);
1283 return SDValue(N, 0);
1287 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1288 unsigned Alignment, int Offset,
1290 unsigned char TargetFlags) {
1291 assert((TargetFlags == 0 || isTarget) &&
1292 "Cannot set target flags on target-independent globals");
1295 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1296 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1297 FoldingSetNodeID ID;
1298 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1299 ID.AddInteger(Alignment);
1300 ID.AddInteger(Offset);
1301 C->addSelectionDAGCSEId(ID);
1302 ID.AddInteger(TargetFlags);
1304 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1305 return SDValue(E, 0);
1307 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1308 Alignment, TargetFlags);
1309 CSEMap.InsertNode(N, IP);
1310 AllNodes.push_back(N);
1311 return SDValue(N, 0);
1314 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1315 unsigned char TargetFlags) {
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1318 ID.AddInteger(Index);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1322 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1327 CSEMap.InsertNode(N, IP);
1328 AllNodes.push_back(N);
1329 return SDValue(N, 0);
1332 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1333 FoldingSetNodeID ID;
1334 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1337 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1338 return SDValue(E, 0);
1340 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1341 CSEMap.InsertNode(N, IP);
1342 AllNodes.push_back(N);
1343 return SDValue(N, 0);
1346 SDValue SelectionDAG::getValueType(EVT VT) {
1347 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1348 ValueTypeNodes.size())
1349 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1351 SDNode *&N = VT.isExtended() ?
1352 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1354 if (N) return SDValue(N, 0);
1355 N = new (NodeAllocator) VTSDNode(VT);
1356 AllNodes.push_back(N);
1357 return SDValue(N, 0);
1360 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1361 SDNode *&N = ExternalSymbols[Sym];
1362 if (N) return SDValue(N, 0);
1363 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1364 AllNodes.push_back(N);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1369 unsigned char TargetFlags) {
1371 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1373 if (N) return SDValue(N, 0);
1374 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1375 AllNodes.push_back(N);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1380 if ((unsigned)Cond >= CondCodeNodes.size())
1381 CondCodeNodes.resize(Cond+1);
1383 if (!CondCodeNodes[Cond]) {
1384 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1385 CondCodeNodes[Cond] = N;
1386 AllNodes.push_back(N);
1389 return SDValue(CondCodeNodes[Cond], 0);
1392 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1393 // the shuffle mask M that point at N1 to point at N2, and indices that point
1394 // N2 to point at N1.
1395 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1397 int NElts = M.size();
1398 for (int i = 0; i != NElts; ++i) {
1406 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1407 SDValue N2, const int *Mask) {
1408 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1409 "Invalid VECTOR_SHUFFLE");
1411 // Canonicalize shuffle undef, undef -> undef
1412 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1413 return getUNDEF(VT);
1415 // Validate that all indices in Mask are within the range of the elements
1416 // input to the shuffle.
1417 unsigned NElts = VT.getVectorNumElements();
1418 SmallVector<int, 8> MaskVec;
1419 for (unsigned i = 0; i != NElts; ++i) {
1420 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1421 MaskVec.push_back(Mask[i]);
1424 // Canonicalize shuffle v, v -> v, undef
1427 for (unsigned i = 0; i != NElts; ++i)
1428 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1431 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1432 if (N1.getOpcode() == ISD::UNDEF)
1433 commuteShuffle(N1, N2, MaskVec);
1435 // Canonicalize all index into lhs, -> shuffle lhs, undef
1436 // Canonicalize all index into rhs, -> shuffle rhs, undef
1437 bool AllLHS = true, AllRHS = true;
1438 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1439 for (unsigned i = 0; i != NElts; ++i) {
1440 if (MaskVec[i] >= (int)NElts) {
1445 } else if (MaskVec[i] >= 0) {
1449 if (AllLHS && AllRHS)
1450 return getUNDEF(VT);
1451 if (AllLHS && !N2Undef)
1455 commuteShuffle(N1, N2, MaskVec);
1458 // If Identity shuffle return that node.
1459 bool Identity = true;
1460 for (unsigned i = 0; i != NElts; ++i) {
1461 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1463 if (Identity && NElts)
1466 // Shuffling a constant splat doesn't change the result.
1467 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1468 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1471 FoldingSetNodeID ID;
1472 SDValue Ops[2] = { N1, N2 };
1473 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1474 for (unsigned i = 0; i != NElts; ++i)
1475 ID.AddInteger(MaskVec[i]);
1478 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1479 return SDValue(E, 0);
1481 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1482 // SDNode doesn't have access to it. This memory will be "leaked" when
1483 // the node is deallocated, but recovered when the NodeAllocator is released.
1484 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1485 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1487 ShuffleVectorSDNode *N =
1488 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1489 dl.getDebugLoc(), N1, N2,
1491 CSEMap.InsertNode(N, IP);
1492 AllNodes.push_back(N);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1497 SDValue Val, SDValue DTy,
1498 SDValue STy, SDValue Rnd, SDValue Sat,
1499 ISD::CvtCode Code) {
1500 // If the src and dest types are the same and the conversion is between
1501 // integer types of the same sign or two floats, no conversion is necessary.
1503 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1506 FoldingSetNodeID ID;
1507 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1508 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1511 return SDValue(E, 0);
1513 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1516 CSEMap.InsertNode(N, IP);
1517 AllNodes.push_back(N);
1518 return SDValue(N, 0);
1521 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1522 FoldingSetNodeID ID;
1523 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1524 ID.AddInteger(RegNo);
1526 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1527 return SDValue(E, 0);
1529 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1530 CSEMap.InsertNode(N, IP);
1531 AllNodes.push_back(N);
1532 return SDValue(N, 0);
1535 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1536 FoldingSetNodeID ID;
1537 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1538 ID.AddPointer(RegMask);
1540 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1541 return SDValue(E, 0);
1543 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1544 CSEMap.InsertNode(N, IP);
1545 AllNodes.push_back(N);
1546 return SDValue(N, 0);
1549 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1550 FoldingSetNodeID ID;
1551 SDValue Ops[] = { Root };
1552 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1553 ID.AddPointer(Label);
1555 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1556 return SDValue(E, 0);
1558 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1559 dl.getDebugLoc(), Root, Label);
1560 CSEMap.InsertNode(N, IP);
1561 AllNodes.push_back(N);
1562 return SDValue(N, 0);
1566 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1569 unsigned char TargetFlags) {
1570 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1572 FoldingSetNodeID ID;
1573 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1575 ID.AddInteger(Offset);
1576 ID.AddInteger(TargetFlags);
1578 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1579 return SDValue(E, 0);
1581 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1583 CSEMap.InsertNode(N, IP);
1584 AllNodes.push_back(N);
1585 return SDValue(N, 0);
1588 SDValue SelectionDAG::getSrcValue(const Value *V) {
1589 assert((!V || V->getType()->isPointerTy()) &&
1590 "SrcValue is not a pointer?");
1592 FoldingSetNodeID ID;
1593 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1597 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1598 return SDValue(E, 0);
1600 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1601 CSEMap.InsertNode(N, IP);
1602 AllNodes.push_back(N);
1603 return SDValue(N, 0);
1606 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1607 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1608 FoldingSetNodeID ID;
1609 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1613 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1614 return SDValue(E, 0);
1616 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1617 CSEMap.InsertNode(N, IP);
1618 AllNodes.push_back(N);
1619 return SDValue(N, 0);
1622 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1623 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1624 unsigned SrcAS, unsigned DestAS) {
1625 SDValue Ops[] = {Ptr};
1626 FoldingSetNodeID ID;
1627 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1628 ID.AddInteger(SrcAS);
1629 ID.AddInteger(DestAS);
1632 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1633 return SDValue(E, 0);
1635 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1637 VT, Ptr, SrcAS, DestAS);
1638 CSEMap.InsertNode(N, IP);
1639 AllNodes.push_back(N);
1640 return SDValue(N, 0);
1643 /// getShiftAmountOperand - Return the specified value casted to
1644 /// the target's desired shift amount type.
1645 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1646 EVT OpTy = Op.getValueType();
1647 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1648 if (OpTy == ShTy || OpTy.isVector()) return Op;
1650 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1651 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1654 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1655 /// specified value type.
1656 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1657 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1658 unsigned ByteSize = VT.getStoreSize();
1659 Type *Ty = VT.getTypeForEVT(*getContext());
1660 const TargetLowering *TLI = TM.getTargetLowering();
1661 unsigned StackAlign =
1662 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1664 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1665 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1668 /// CreateStackTemporary - Create a stack temporary suitable for holding
1669 /// either of the specified value types.
1670 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1671 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1672 VT2.getStoreSizeInBits())/8;
1673 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1674 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1675 const TargetLowering *TLI = TM.getTargetLowering();
1676 const DataLayout *TD = TLI->getDataLayout();
1677 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1678 TD->getPrefTypeAlignment(Ty2));
1680 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1681 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1682 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1685 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1686 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1687 // These setcc operations always fold.
1691 case ISD::SETFALSE2: return getConstant(0, VT);
1693 case ISD::SETTRUE2: {
1694 const TargetLowering *TLI = TM.getTargetLowering();
1695 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1697 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1710 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1714 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1715 const APInt &C2 = N2C->getAPIntValue();
1716 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1717 const APInt &C1 = N1C->getAPIntValue();
1720 default: llvm_unreachable("Unknown integer setcc!");
1721 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1722 case ISD::SETNE: return getConstant(C1 != C2, VT);
1723 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1724 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1725 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1726 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1727 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1728 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1729 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1730 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1734 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1735 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1736 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1739 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1740 return getUNDEF(VT);
1742 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1743 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1744 return getUNDEF(VT);
1746 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1747 R==APFloat::cmpLessThan, VT);
1748 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1749 return getUNDEF(VT);
1751 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1752 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1753 return getUNDEF(VT);
1755 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1756 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1757 return getUNDEF(VT);
1759 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1760 R==APFloat::cmpEqual, VT);
1761 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1762 return getUNDEF(VT);
1764 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1765 R==APFloat::cmpEqual, VT);
1766 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1767 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1768 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1769 R==APFloat::cmpEqual, VT);
1770 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1771 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1772 R==APFloat::cmpLessThan, VT);
1773 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1774 R==APFloat::cmpUnordered, VT);
1775 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1776 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1779 // Ensure that the constant occurs on the RHS.
1780 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1781 MVT CompVT = N1.getValueType().getSimpleVT();
1782 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1785 return getSetCC(dl, VT, N2, N1, SwappedCond);
1789 // Could not fold it.
1793 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1794 /// use this predicate to simplify operations downstream.
1795 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1796 // This predicate is not safe for vector operations.
1797 if (Op.getValueType().isVector())
1800 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1801 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1804 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1805 /// this predicate to simplify operations downstream. Mask is known to be zero
1806 /// for bits that V cannot have.
1807 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1808 unsigned Depth) const {
1809 APInt KnownZero, KnownOne;
1810 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1811 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1812 return (KnownZero & Mask) == Mask;
1815 /// Determine which bits of Op are known to be either zero or one and return
1816 /// them in the KnownZero/KnownOne bitsets.
1817 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1818 APInt &KnownOne, unsigned Depth) const {
1819 const TargetLowering *TLI = TM.getTargetLowering();
1820 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1822 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1824 return; // Limit search depth.
1826 APInt KnownZero2, KnownOne2;
1828 switch (Op.getOpcode()) {
1830 // We know all of the bits for a constant!
1831 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1832 KnownZero = ~KnownOne;
1835 // If either the LHS or the RHS are Zero, the result is zero.
1836 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1837 computeKnownBits(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-1 bits are only known if set in both the LHS & RHS.
1842 KnownOne &= KnownOne2;
1843 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1844 KnownZero |= KnownZero2;
1847 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1848 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1849 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1850 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1852 // Output known-0 bits are only known if clear in both the LHS & RHS.
1853 KnownZero &= KnownZero2;
1854 // Output known-1 are known to be set if set in either the LHS | RHS.
1855 KnownOne |= KnownOne2;
1858 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1859 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1860 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1861 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1863 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1864 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1865 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1866 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1867 KnownZero = KnownZeroOut;
1871 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1872 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1873 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1874 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1876 // If low bits are zero in either operand, output low known-0 bits.
1877 // Also compute a conserative estimate for high known-0 bits.
1878 // More trickiness is possible, but this is sufficient for the
1879 // interesting case of alignment computation.
1880 KnownOne.clearAllBits();
1881 unsigned TrailZ = KnownZero.countTrailingOnes() +
1882 KnownZero2.countTrailingOnes();
1883 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1884 KnownZero2.countLeadingOnes(),
1885 BitWidth) - BitWidth;
1887 TrailZ = std::min(TrailZ, BitWidth);
1888 LeadZ = std::min(LeadZ, BitWidth);
1889 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1890 APInt::getHighBitsSet(BitWidth, LeadZ);
1894 // For the purposes of computing leading zeros we can conservatively
1895 // treat a udiv as a logical right shift by the power of 2 known to
1896 // be less than the denominator.
1897 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1898 unsigned LeadZ = KnownZero2.countLeadingOnes();
1900 KnownOne2.clearAllBits();
1901 KnownZero2.clearAllBits();
1902 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1903 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1904 if (RHSUnknownLeadingOnes != BitWidth)
1905 LeadZ = std::min(BitWidth,
1906 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1908 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1912 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1913 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1914 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1915 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1917 // Only known if known in both the LHS and RHS.
1918 KnownOne &= KnownOne2;
1919 KnownZero &= KnownZero2;
1921 case ISD::SELECT_CC:
1922 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1923 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1924 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1925 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1927 // Only known if known in both the LHS and RHS.
1928 KnownOne &= KnownOne2;
1929 KnownZero &= KnownZero2;
1937 if (Op.getResNo() != 1)
1939 // The boolean result conforms to getBooleanContents. Fall through.
1941 // If we know the result of a setcc has the top bits zero, use this info.
1942 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1943 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1944 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1947 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1948 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1949 unsigned ShAmt = SA->getZExtValue();
1951 // If the shift count is an invalid immediate, don't do anything.
1952 if (ShAmt >= BitWidth)
1955 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1956 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1957 KnownZero <<= ShAmt;
1959 // low bits known zero.
1960 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1964 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1965 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1966 unsigned ShAmt = SA->getZExtValue();
1968 // If the shift count is an invalid immediate, don't do anything.
1969 if (ShAmt >= BitWidth)
1972 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1973 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1974 KnownZero = KnownZero.lshr(ShAmt);
1975 KnownOne = KnownOne.lshr(ShAmt);
1977 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1978 KnownZero |= HighBits; // High bits known zero.
1982 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1983 unsigned ShAmt = SA->getZExtValue();
1985 // If the shift count is an invalid immediate, don't do anything.
1986 if (ShAmt >= BitWidth)
1989 // If any of the demanded bits are produced by the sign extension, we also
1990 // demand the input sign bit.
1991 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1993 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1994 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1995 KnownZero = KnownZero.lshr(ShAmt);
1996 KnownOne = KnownOne.lshr(ShAmt);
1998 // Handle the sign bits.
1999 APInt SignBit = APInt::getSignBit(BitWidth);
2000 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2002 if (KnownZero.intersects(SignBit)) {
2003 KnownZero |= HighBits; // New bits are known zero.
2004 } else if (KnownOne.intersects(SignBit)) {
2005 KnownOne |= HighBits; // New bits are known one.
2009 case ISD::SIGN_EXTEND_INREG: {
2010 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2011 unsigned EBits = EVT.getScalarType().getSizeInBits();
2013 // Sign extension. Compute the demanded bits in the result that are not
2014 // present in the input.
2015 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2017 APInt InSignBit = APInt::getSignBit(EBits);
2018 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2020 // If the sign extended bits are demanded, we know that the sign
2022 InSignBit = InSignBit.zext(BitWidth);
2023 if (NewBits.getBoolValue())
2024 InputDemandedBits |= InSignBit;
2026 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2027 KnownOne &= InputDemandedBits;
2028 KnownZero &= InputDemandedBits;
2029 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2031 // If the sign bit of the input is known set or clear, then we know the
2032 // top bits of the result.
2033 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2034 KnownZero |= NewBits;
2035 KnownOne &= ~NewBits;
2036 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2037 KnownOne |= NewBits;
2038 KnownZero &= ~NewBits;
2039 } else { // Input sign bit unknown
2040 KnownZero &= ~NewBits;
2041 KnownOne &= ~NewBits;
2046 case ISD::CTTZ_ZERO_UNDEF:
2048 case ISD::CTLZ_ZERO_UNDEF:
2050 unsigned LowBits = Log2_32(BitWidth)+1;
2051 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2052 KnownOne.clearAllBits();
2056 LoadSDNode *LD = cast<LoadSDNode>(Op);
2057 // If this is a ZEXTLoad and we are looking at the loaded value.
2058 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2059 EVT VT = LD->getMemoryVT();
2060 unsigned MemBits = VT.getScalarType().getSizeInBits();
2061 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2062 } else if (const MDNode *Ranges = LD->getRanges()) {
2063 computeKnownBitsLoad(*Ranges, KnownZero);
2067 case ISD::ZERO_EXTEND: {
2068 EVT InVT = Op.getOperand(0).getValueType();
2069 unsigned InBits = InVT.getScalarType().getSizeInBits();
2070 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2071 KnownZero = KnownZero.trunc(InBits);
2072 KnownOne = KnownOne.trunc(InBits);
2073 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2074 KnownZero = KnownZero.zext(BitWidth);
2075 KnownOne = KnownOne.zext(BitWidth);
2076 KnownZero |= NewBits;
2079 case ISD::SIGN_EXTEND: {
2080 EVT InVT = Op.getOperand(0).getValueType();
2081 unsigned InBits = InVT.getScalarType().getSizeInBits();
2082 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2084 KnownZero = KnownZero.trunc(InBits);
2085 KnownOne = KnownOne.trunc(InBits);
2086 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2088 // Note if the sign bit is known to be zero or one.
2089 bool SignBitKnownZero = KnownZero.isNegative();
2090 bool SignBitKnownOne = KnownOne.isNegative();
2091 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2092 "Sign bit can't be known to be both zero and one!");
2094 KnownZero = KnownZero.zext(BitWidth);
2095 KnownOne = KnownOne.zext(BitWidth);
2097 // If the sign bit is known zero or one, the top bits match.
2098 if (SignBitKnownZero)
2099 KnownZero |= NewBits;
2100 else if (SignBitKnownOne)
2101 KnownOne |= NewBits;
2104 case ISD::ANY_EXTEND: {
2105 EVT InVT = Op.getOperand(0).getValueType();
2106 unsigned InBits = InVT.getScalarType().getSizeInBits();
2107 KnownZero = KnownZero.trunc(InBits);
2108 KnownOne = KnownOne.trunc(InBits);
2109 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2110 KnownZero = KnownZero.zext(BitWidth);
2111 KnownOne = KnownOne.zext(BitWidth);
2114 case ISD::TRUNCATE: {
2115 EVT InVT = Op.getOperand(0).getValueType();
2116 unsigned InBits = InVT.getScalarType().getSizeInBits();
2117 KnownZero = KnownZero.zext(InBits);
2118 KnownOne = KnownOne.zext(InBits);
2119 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2120 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2121 KnownZero = KnownZero.trunc(BitWidth);
2122 KnownOne = KnownOne.trunc(BitWidth);
2125 case ISD::AssertZext: {
2126 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2127 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2128 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2129 KnownZero |= (~InMask);
2130 KnownOne &= (~KnownZero);
2134 // All bits are zero except the low bit.
2135 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2139 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2140 // We know that the top bits of C-X are clear if X contains less bits
2141 // than C (i.e. no wrap-around can happen). For example, 20-X is
2142 // positive if we can prove that X is >= 0 and < 16.
2143 if (CLHS->getAPIntValue().isNonNegative()) {
2144 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2145 // NLZ can't be BitWidth with no sign bit
2146 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2147 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2149 // If all of the MaskV bits are known to be zero, then we know the
2150 // output top bits are zero, because we now know that the output is
2152 if ((KnownZero2 & MaskV) == MaskV) {
2153 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2154 // Top bits known zero.
2155 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2163 // Output known-0 bits are known if clear or set in both the low clear bits
2164 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2165 // low 3 bits clear.
2166 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2167 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2168 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2170 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2171 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2172 KnownZeroOut = std::min(KnownZeroOut,
2173 KnownZero2.countTrailingOnes());
2175 if (Op.getOpcode() == ISD::ADD) {
2176 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2180 // With ADDE, a carry bit may be added in, so we can only use this
2181 // information if we know (at least) that the low two bits are clear. We
2182 // then return to the caller that the low bit is unknown but that other bits
2184 if (KnownZeroOut >= 2) // ADDE
2185 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2189 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2190 const APInt &RA = Rem->getAPIntValue().abs();
2191 if (RA.isPowerOf2()) {
2192 APInt LowBits = RA - 1;
2193 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2195 // The low bits of the first operand are unchanged by the srem.
2196 KnownZero = KnownZero2 & LowBits;
2197 KnownOne = KnownOne2 & LowBits;
2199 // If the first operand is non-negative or has all low bits zero, then
2200 // the upper bits are all zero.
2201 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2202 KnownZero |= ~LowBits;
2204 // If the first operand is negative and not all low bits are zero, then
2205 // the upper bits are all one.
2206 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2207 KnownOne |= ~LowBits;
2208 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2213 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2214 const APInt &RA = Rem->getAPIntValue();
2215 if (RA.isPowerOf2()) {
2216 APInt LowBits = (RA - 1);
2217 KnownZero |= ~LowBits;
2218 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2219 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2224 // Since the result is less than or equal to either operand, any leading
2225 // zero bits in either operand must also exist in the result.
2226 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2227 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2229 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2230 KnownZero2.countLeadingOnes());
2231 KnownOne.clearAllBits();
2232 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2235 case ISD::FrameIndex:
2236 case ISD::TargetFrameIndex:
2237 if (unsigned Align = InferPtrAlignment(Op)) {
2238 // The low bits are known zero if the pointer is aligned.
2239 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2245 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2248 case ISD::INTRINSIC_WO_CHAIN:
2249 case ISD::INTRINSIC_W_CHAIN:
2250 case ISD::INTRINSIC_VOID:
2251 // Allow the target to implement this method for its nodes.
2252 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2257 /// ComputeNumSignBits - Return the number of times the sign bit of the
2258 /// register is replicated into the other bits. We know that at least 1 bit
2259 /// is always equal to the sign bit (itself), but other cases can give us
2260 /// information. For example, immediately after an "SRA X, 2", we know that
2261 /// the top 3 bits are all equal to each other, so we return 3.
2262 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2263 const TargetLowering *TLI = TM.getTargetLowering();
2264 EVT VT = Op.getValueType();
2265 assert(VT.isInteger() && "Invalid VT!");
2266 unsigned VTBits = VT.getScalarType().getSizeInBits();
2268 unsigned FirstAnswer = 1;
2271 return 1; // Limit search depth.
2273 switch (Op.getOpcode()) {
2275 case ISD::AssertSext:
2276 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2277 return VTBits-Tmp+1;
2278 case ISD::AssertZext:
2279 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2282 case ISD::Constant: {
2283 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2284 return Val.getNumSignBits();
2287 case ISD::SIGN_EXTEND:
2289 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2290 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2292 case ISD::SIGN_EXTEND_INREG:
2293 // Max of the input and what this extends.
2295 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2298 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2299 return std::max(Tmp, Tmp2);
2302 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2303 // SRA X, C -> adds C sign bits.
2304 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2305 Tmp += C->getZExtValue();
2306 if (Tmp > VTBits) Tmp = VTBits;
2310 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2311 // shl destroys sign bits.
2312 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2313 if (C->getZExtValue() >= VTBits || // Bad shift.
2314 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2315 return Tmp - C->getZExtValue();
2320 case ISD::XOR: // NOT is handled here.
2321 // Logical binary ops preserve the number of sign bits at the worst.
2322 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2324 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2325 FirstAnswer = std::min(Tmp, Tmp2);
2326 // We computed what we know about the sign bits as our first
2327 // answer. Now proceed to the generic code that uses
2328 // computeKnownBits, and pick whichever answer is better.
2333 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2334 if (Tmp == 1) return 1; // Early out.
2335 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2336 return std::min(Tmp, Tmp2);
2344 if (Op.getResNo() != 1)
2346 // The boolean result conforms to getBooleanContents. Fall through.
2348 // If setcc returns 0/-1, all bits are sign bits.
2349 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2350 TargetLowering::ZeroOrNegativeOneBooleanContent)
2355 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2356 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2358 // Handle rotate right by N like a rotate left by 32-N.
2359 if (Op.getOpcode() == ISD::ROTR)
2360 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2362 // If we aren't rotating out all of the known-in sign bits, return the
2363 // number that are left. This handles rotl(sext(x), 1) for example.
2364 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2365 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2369 // Add can have at most one carry bit. Thus we know that the output
2370 // is, at worst, one more bit than the inputs.
2371 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2372 if (Tmp == 1) return 1; // Early out.
2374 // Special case decrementing a value (ADD X, -1):
2375 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2376 if (CRHS->isAllOnesValue()) {
2377 APInt KnownZero, KnownOne;
2378 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2380 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2382 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2385 // If we are subtracting one from a positive number, there is no carry
2386 // out of the result.
2387 if (KnownZero.isNegative())
2391 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2392 if (Tmp2 == 1) return 1;
2393 return std::min(Tmp, Tmp2)-1;
2396 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2397 if (Tmp2 == 1) return 1;
2400 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2401 if (CLHS->isNullValue()) {
2402 APInt KnownZero, KnownOne;
2403 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2404 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2406 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2409 // If the input is known to be positive (the sign bit is known clear),
2410 // the output of the NEG has the same number of sign bits as the input.
2411 if (KnownZero.isNegative())
2414 // Otherwise, we treat this like a SUB.
2417 // Sub can have at most one carry bit. Thus we know that the output
2418 // is, at worst, one more bit than the inputs.
2419 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2420 if (Tmp == 1) return 1; // Early out.
2421 return std::min(Tmp, Tmp2)-1;
2423 // FIXME: it's tricky to do anything useful for this, but it is an important
2424 // case for targets like X86.
2428 // If we are looking at the loaded value of the SDNode.
2429 if (Op.getResNo() == 0) {
2430 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2431 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2432 unsigned ExtType = LD->getExtensionType();
2435 case ISD::SEXTLOAD: // '17' bits known
2436 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2437 return VTBits-Tmp+1;
2438 case ISD::ZEXTLOAD: // '16' bits known
2439 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2445 // Allow the target to implement this method for its nodes.
2446 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2447 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2448 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2449 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2450 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2451 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2454 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2455 // use this information.
2456 APInt KnownZero, KnownOne;
2457 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2460 if (KnownZero.isNegative()) { // sign bit is 0
2462 } else if (KnownOne.isNegative()) { // sign bit is 1;
2469 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2470 // the number of identical bits in the top of the input value.
2472 Mask <<= Mask.getBitWidth()-VTBits;
2473 // Return # leading zeros. We use 'min' here in case Val was zero before
2474 // shifting. We don't want to return '64' as for an i32 "0".
2475 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2478 /// isBaseWithConstantOffset - Return true if the specified operand is an
2479 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2480 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2481 /// semantics as an ADD. This handles the equivalence:
2482 /// X|Cst == X+Cst iff X&Cst = 0.
2483 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2484 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2485 !isa<ConstantSDNode>(Op.getOperand(1)))
2488 if (Op.getOpcode() == ISD::OR &&
2489 !MaskedValueIsZero(Op.getOperand(0),
2490 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2497 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2498 // If we're told that NaNs won't happen, assume they won't.
2499 if (getTarget().Options.NoNaNsFPMath)
2502 // If the value is a constant, we can obviously see if it is a NaN or not.
2503 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2504 return !C->getValueAPF().isNaN();
2506 // TODO: Recognize more cases here.
2511 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2512 // If the value is a constant, we can obviously see if it is a zero or not.
2513 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2514 return !C->isZero();
2516 // TODO: Recognize more cases here.
2517 switch (Op.getOpcode()) {
2520 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2521 return !C->isNullValue();
2528 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2529 // Check the obvious case.
2530 if (A == B) return true;
2532 // For for negative and positive zero.
2533 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2534 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2535 if (CA->isZero() && CB->isZero()) return true;
2537 // Otherwise they may not be equal.
2541 /// getNode - Gets or creates the specified node.
2543 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2544 FoldingSetNodeID ID;
2545 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2547 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2548 return SDValue(E, 0);
2550 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2551 DL.getDebugLoc(), getVTList(VT));
2552 CSEMap.InsertNode(N, IP);
2554 AllNodes.push_back(N);
2558 return SDValue(N, 0);
2561 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2562 EVT VT, SDValue Operand) {
2563 // Constant fold unary operations with an integer constant operand. Even
2564 // opaque constant will be folded, because the folding of unary operations
2565 // doesn't create new constants with different values. Nevertheless, the
2566 // opaque flag is preserved during folding to prevent future folding with
2568 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2569 const APInt &Val = C->getAPIntValue();
2572 case ISD::SIGN_EXTEND:
2573 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2574 C->isTargetOpcode(), C->isOpaque());
2575 case ISD::ANY_EXTEND:
2576 case ISD::ZERO_EXTEND:
2578 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2579 C->isTargetOpcode(), C->isOpaque());
2580 case ISD::UINT_TO_FP:
2581 case ISD::SINT_TO_FP: {
2582 APFloat apf(EVTToAPFloatSemantics(VT),
2583 APInt::getNullValue(VT.getSizeInBits()));
2584 (void)apf.convertFromAPInt(Val,
2585 Opcode==ISD::SINT_TO_FP,
2586 APFloat::rmNearestTiesToEven);
2587 return getConstantFP(apf, VT);
2590 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2591 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2592 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2593 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2596 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2599 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2602 case ISD::CTLZ_ZERO_UNDEF:
2603 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2606 case ISD::CTTZ_ZERO_UNDEF:
2607 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2612 // Constant fold unary operations with a floating point constant operand.
2613 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2614 APFloat V = C->getValueAPF(); // make copy
2618 return getConstantFP(V, VT);
2621 return getConstantFP(V, VT);
2623 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2624 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2625 return getConstantFP(V, VT);
2629 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2630 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2631 return getConstantFP(V, VT);
2635 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2636 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2637 return getConstantFP(V, VT);
2640 case ISD::FP_EXTEND: {
2642 // This can return overflow, underflow, or inexact; we don't care.
2643 // FIXME need to be more flexible about rounding mode.
2644 (void)V.convert(EVTToAPFloatSemantics(VT),
2645 APFloat::rmNearestTiesToEven, &ignored);
2646 return getConstantFP(V, VT);
2648 case ISD::FP_TO_SINT:
2649 case ISD::FP_TO_UINT: {
2652 assert(integerPartWidth >= 64);
2653 // FIXME need to be more flexible about rounding mode.
2654 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2655 Opcode==ISD::FP_TO_SINT,
2656 APFloat::rmTowardZero, &ignored);
2657 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2659 APInt api(VT.getSizeInBits(), x);
2660 return getConstant(api, VT);
2663 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2664 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2665 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2666 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2671 unsigned OpOpcode = Operand.getNode()->getOpcode();
2673 case ISD::TokenFactor:
2674 case ISD::MERGE_VALUES:
2675 case ISD::CONCAT_VECTORS:
2676 return Operand; // Factor, merge or concat of one node? No need.
2677 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2678 case ISD::FP_EXTEND:
2679 assert(VT.isFloatingPoint() &&
2680 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2681 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2682 assert((!VT.isVector() ||
2683 VT.getVectorNumElements() ==
2684 Operand.getValueType().getVectorNumElements()) &&
2685 "Vector element count mismatch!");
2686 if (Operand.getOpcode() == ISD::UNDEF)
2687 return getUNDEF(VT);
2689 case ISD::SIGN_EXTEND:
2690 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2691 "Invalid SIGN_EXTEND!");
2692 if (Operand.getValueType() == VT) return Operand; // noop extension
2693 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2694 "Invalid sext node, dst < src!");
2695 assert((!VT.isVector() ||
2696 VT.getVectorNumElements() ==
2697 Operand.getValueType().getVectorNumElements()) &&
2698 "Vector element count mismatch!");
2699 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2700 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2701 else if (OpOpcode == ISD::UNDEF)
2702 // sext(undef) = 0, because the top bits will all be the same.
2703 return getConstant(0, VT);
2705 case ISD::ZERO_EXTEND:
2706 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2707 "Invalid ZERO_EXTEND!");
2708 if (Operand.getValueType() == VT) return Operand; // noop extension
2709 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2710 "Invalid zext node, dst < src!");
2711 assert((!VT.isVector() ||
2712 VT.getVectorNumElements() ==
2713 Operand.getValueType().getVectorNumElements()) &&
2714 "Vector element count mismatch!");
2715 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2716 return getNode(ISD::ZERO_EXTEND, DL, VT,
2717 Operand.getNode()->getOperand(0));
2718 else if (OpOpcode == ISD::UNDEF)
2719 // zext(undef) = 0, because the top bits will be zero.
2720 return getConstant(0, VT);
2722 case ISD::ANY_EXTEND:
2723 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2724 "Invalid ANY_EXTEND!");
2725 if (Operand.getValueType() == VT) return Operand; // noop extension
2726 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2727 "Invalid anyext node, dst < src!");
2728 assert((!VT.isVector() ||
2729 VT.getVectorNumElements() ==
2730 Operand.getValueType().getVectorNumElements()) &&
2731 "Vector element count mismatch!");
2733 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2734 OpOpcode == ISD::ANY_EXTEND)
2735 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2736 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2737 else if (OpOpcode == ISD::UNDEF)
2738 return getUNDEF(VT);
2740 // (ext (trunx x)) -> x
2741 if (OpOpcode == ISD::TRUNCATE) {
2742 SDValue OpOp = Operand.getNode()->getOperand(0);
2743 if (OpOp.getValueType() == VT)
2748 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2749 "Invalid TRUNCATE!");
2750 if (Operand.getValueType() == VT) return Operand; // noop truncate
2751 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2752 "Invalid truncate node, src < dst!");
2753 assert((!VT.isVector() ||
2754 VT.getVectorNumElements() ==
2755 Operand.getValueType().getVectorNumElements()) &&
2756 "Vector element count mismatch!");
2757 if (OpOpcode == ISD::TRUNCATE)
2758 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2759 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2760 OpOpcode == ISD::ANY_EXTEND) {
2761 // If the source is smaller than the dest, we still need an extend.
2762 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2763 .bitsLT(VT.getScalarType()))
2764 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2765 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2766 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2767 return Operand.getNode()->getOperand(0);
2769 if (OpOpcode == ISD::UNDEF)
2770 return getUNDEF(VT);
2773 // Basic sanity checking.
2774 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2775 && "Cannot BITCAST between types of different sizes!");
2776 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2777 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2778 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2779 if (OpOpcode == ISD::UNDEF)
2780 return getUNDEF(VT);
2782 case ISD::SCALAR_TO_VECTOR:
2783 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2784 (VT.getVectorElementType() == Operand.getValueType() ||
2785 (VT.getVectorElementType().isInteger() &&
2786 Operand.getValueType().isInteger() &&
2787 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2788 "Illegal SCALAR_TO_VECTOR node!");
2789 if (OpOpcode == ISD::UNDEF)
2790 return getUNDEF(VT);
2791 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2792 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2793 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2794 Operand.getConstantOperandVal(1) == 0 &&
2795 Operand.getOperand(0).getValueType() == VT)
2796 return Operand.getOperand(0);
2799 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2800 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2801 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2802 Operand.getNode()->getOperand(0));
2803 if (OpOpcode == ISD::FNEG) // --X -> X
2804 return Operand.getNode()->getOperand(0);
2807 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2808 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2813 SDVTList VTs = getVTList(VT);
2814 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2815 FoldingSetNodeID ID;
2816 SDValue Ops[1] = { Operand };
2817 AddNodeIDNode(ID, Opcode, VTs, Ops);
2819 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2820 return SDValue(E, 0);
2822 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2823 DL.getDebugLoc(), VTs, Operand);
2824 CSEMap.InsertNode(N, IP);
2826 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2827 DL.getDebugLoc(), VTs, Operand);
2830 AllNodes.push_back(N);
2834 return SDValue(N, 0);
2837 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2838 SDNode *Cst1, SDNode *Cst2) {
2839 // If the opcode is a target-specific ISD node, there's nothing we can
2840 // do here and the operand rules may not line up with the below, so
2842 if (Opcode >= ISD::BUILTIN_OP_END)
2845 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2846 SmallVector<SDValue, 4> Outputs;
2847 EVT SVT = VT.getScalarType();
2849 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2850 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2851 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2854 if (Scalar1 && Scalar2)
2855 // Scalar instruction.
2856 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2858 // For vectors extract each constant element into Inputs so we can constant
2859 // fold them individually.
2860 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2861 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2865 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2867 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2868 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2869 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2870 if (!V1 || !V2) // Not a constant, bail.
2873 if (V1->isOpaque() || V2->isOpaque())
2876 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2877 // FIXME: This is valid and could be handled by truncating the APInts.
2878 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2881 Inputs.push_back(std::make_pair(V1, V2));
2885 // We have a number of constant values, constant fold them element by element.
2886 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2887 const APInt &C1 = Inputs[I].first->getAPIntValue();
2888 const APInt &C2 = Inputs[I].second->getAPIntValue();
2892 Outputs.push_back(getConstant(C1 + C2, SVT));
2895 Outputs.push_back(getConstant(C1 - C2, SVT));
2898 Outputs.push_back(getConstant(C1 * C2, SVT));
2901 if (!C2.getBoolValue())
2903 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2906 if (!C2.getBoolValue())
2908 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2911 if (!C2.getBoolValue())
2913 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2916 if (!C2.getBoolValue())
2918 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2921 Outputs.push_back(getConstant(C1 & C2, SVT));
2924 Outputs.push_back(getConstant(C1 | C2, SVT));
2927 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2930 Outputs.push_back(getConstant(C1 << C2, SVT));
2933 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2936 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2939 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2942 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2949 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2950 "Expected a scalar or vector!"));
2952 // Handle the scalar case first.
2954 return Outputs.back();
2956 // We may have a vector type but a scalar result. Create a splat.
2957 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2959 // Build a big vector out of the scalar elements we generated.
2960 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2963 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2965 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2966 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2969 case ISD::TokenFactor:
2970 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2971 N2.getValueType() == MVT::Other && "Invalid token factor!");
2972 // Fold trivial token factors.
2973 if (N1.getOpcode() == ISD::EntryToken) return N2;
2974 if (N2.getOpcode() == ISD::EntryToken) return N1;
2975 if (N1 == N2) return N1;
2977 case ISD::CONCAT_VECTORS:
2978 // Concat of UNDEFs is UNDEF.
2979 if (N1.getOpcode() == ISD::UNDEF &&
2980 N2.getOpcode() == ISD::UNDEF)
2981 return getUNDEF(VT);
2983 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2984 // one big BUILD_VECTOR.
2985 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2986 N2.getOpcode() == ISD::BUILD_VECTOR) {
2987 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2988 N1.getNode()->op_end());
2989 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2990 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2994 assert(VT.isInteger() && "This operator does not apply to FP types!");
2995 assert(N1.getValueType() == N2.getValueType() &&
2996 N1.getValueType() == VT && "Binary operator types must match!");
2997 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2998 // worth handling here.
2999 if (N2C && N2C->isNullValue())
3001 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3008 assert(VT.isInteger() && "This operator does not apply to FP types!");
3009 assert(N1.getValueType() == N2.getValueType() &&
3010 N1.getValueType() == VT && "Binary operator types must match!");
3011 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3012 // it's worth handling here.
3013 if (N2C && N2C->isNullValue())
3023 assert(VT.isInteger() && "This operator does not apply to FP types!");
3024 assert(N1.getValueType() == N2.getValueType() &&
3025 N1.getValueType() == VT && "Binary operator types must match!");
3032 if (getTarget().Options.UnsafeFPMath) {
3033 if (Opcode == ISD::FADD) {
3035 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3036 if (CFP->getValueAPF().isZero())
3039 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3040 if (CFP->getValueAPF().isZero())
3042 } else if (Opcode == ISD::FSUB) {
3044 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3045 if (CFP->getValueAPF().isZero())
3047 } else if (Opcode == ISD::FMUL) {
3048 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3051 // If the first operand isn't the constant, try the second
3053 CFP = dyn_cast<ConstantFPSDNode>(N2);
3060 return SDValue(CFP,0);
3062 if (CFP->isExactlyValue(1.0))
3067 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3068 assert(N1.getValueType() == N2.getValueType() &&
3069 N1.getValueType() == VT && "Binary operator types must match!");
3071 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3072 assert(N1.getValueType() == VT &&
3073 N1.getValueType().isFloatingPoint() &&
3074 N2.getValueType().isFloatingPoint() &&
3075 "Invalid FCOPYSIGN!");
3082 assert(VT == N1.getValueType() &&
3083 "Shift operators return type must be the same as their first arg");
3084 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3085 "Shifts only work on integers");
3086 assert((!VT.isVector() || VT == N2.getValueType()) &&
3087 "Vector shift amounts must be in the same as their first arg");
3088 // Verify that the shift amount VT is bit enough to hold valid shift
3089 // amounts. This catches things like trying to shift an i1024 value by an
3090 // i8, which is easy to fall into in generic code that uses
3091 // TLI.getShiftAmount().
3092 assert(N2.getValueType().getSizeInBits() >=
3093 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3094 "Invalid use of small shift amount with oversized value!");
3096 // Always fold shifts of i1 values so the code generator doesn't need to
3097 // handle them. Since we know the size of the shift has to be less than the
3098 // size of the value, the shift/rotate count is guaranteed to be zero.
3101 if (N2C && N2C->isNullValue())
3104 case ISD::FP_ROUND_INREG: {
3105 EVT EVT = cast<VTSDNode>(N2)->getVT();
3106 assert(VT == N1.getValueType() && "Not an inreg round!");
3107 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3108 "Cannot FP_ROUND_INREG integer types");
3109 assert(EVT.isVector() == VT.isVector() &&
3110 "FP_ROUND_INREG type should be vector iff the operand "
3112 assert((!EVT.isVector() ||
3113 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3114 "Vector element counts must match in FP_ROUND_INREG");
3115 assert(EVT.bitsLE(VT) && "Not rounding down!");
3117 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3121 assert(VT.isFloatingPoint() &&
3122 N1.getValueType().isFloatingPoint() &&
3123 VT.bitsLE(N1.getValueType()) &&
3124 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3125 if (N1.getValueType() == VT) return N1; // noop conversion.
3127 case ISD::AssertSext:
3128 case ISD::AssertZext: {
3129 EVT EVT = cast<VTSDNode>(N2)->getVT();
3130 assert(VT == N1.getValueType() && "Not an inreg extend!");
3131 assert(VT.isInteger() && EVT.isInteger() &&
3132 "Cannot *_EXTEND_INREG FP types");
3133 assert(!EVT.isVector() &&
3134 "AssertSExt/AssertZExt type should be the vector element type "
3135 "rather than the vector type!");
3136 assert(EVT.bitsLE(VT) && "Not extending!");
3137 if (VT == EVT) return N1; // noop assertion.
3140 case ISD::SIGN_EXTEND_INREG: {
3141 EVT EVT = cast<VTSDNode>(N2)->getVT();
3142 assert(VT == N1.getValueType() && "Not an inreg extend!");
3143 assert(VT.isInteger() && EVT.isInteger() &&
3144 "Cannot *_EXTEND_INREG FP types");
3145 assert(EVT.isVector() == VT.isVector() &&
3146 "SIGN_EXTEND_INREG type should be vector iff the operand "
3148 assert((!EVT.isVector() ||
3149 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3150 "Vector element counts must match in SIGN_EXTEND_INREG");
3151 assert(EVT.bitsLE(VT) && "Not extending!");
3152 if (EVT == VT) return N1; // Not actually extending
3155 APInt Val = N1C->getAPIntValue();
3156 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3157 Val <<= Val.getBitWidth()-FromBits;
3158 Val = Val.ashr(Val.getBitWidth()-FromBits);
3159 return getConstant(Val, VT);
3163 case ISD::EXTRACT_VECTOR_ELT:
3164 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3165 if (N1.getOpcode() == ISD::UNDEF)
3166 return getUNDEF(VT);
3168 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3169 // expanding copies of large vectors from registers.
3171 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3172 N1.getNumOperands() > 0) {
3174 N1.getOperand(0).getValueType().getVectorNumElements();
3175 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3176 N1.getOperand(N2C->getZExtValue() / Factor),
3177 getConstant(N2C->getZExtValue() % Factor,
3178 N2.getValueType()));
3181 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3182 // expanding large vector constants.
3183 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3184 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3186 if (VT != Elt.getValueType())
3187 // If the vector element type is not legal, the BUILD_VECTOR operands
3188 // are promoted and implicitly truncated, and the result implicitly
3189 // extended. Make that explicit here.
3190 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3195 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3196 // operations are lowered to scalars.
3197 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3198 // If the indices are the same, return the inserted element else
3199 // if the indices are known different, extract the element from
3200 // the original vector.
3201 SDValue N1Op2 = N1.getOperand(2);
3202 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3204 if (N1Op2C && N2C) {
3205 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3206 if (VT == N1.getOperand(1).getValueType())
3207 return N1.getOperand(1);
3209 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3212 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3216 case ISD::EXTRACT_ELEMENT:
3217 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3218 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3219 (N1.getValueType().isInteger() == VT.isInteger()) &&
3220 N1.getValueType() != VT &&
3221 "Wrong types for EXTRACT_ELEMENT!");
3223 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3224 // 64-bit integers into 32-bit parts. Instead of building the extract of
3225 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3226 if (N1.getOpcode() == ISD::BUILD_PAIR)
3227 return N1.getOperand(N2C->getZExtValue());
3229 // EXTRACT_ELEMENT of a constant int is also very common.
3230 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3231 unsigned ElementSize = VT.getSizeInBits();
3232 unsigned Shift = ElementSize * N2C->getZExtValue();
3233 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3234 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3237 case ISD::EXTRACT_SUBVECTOR: {
3239 if (VT.isSimple() && N1.getValueType().isSimple()) {
3240 assert(VT.isVector() && N1.getValueType().isVector() &&
3241 "Extract subvector VTs must be a vectors!");
3242 assert(VT.getVectorElementType() ==
3243 N1.getValueType().getVectorElementType() &&
3244 "Extract subvector VTs must have the same element type!");
3245 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3246 "Extract subvector must be from larger vector to smaller vector!");
3248 if (isa<ConstantSDNode>(Index.getNode())) {
3249 assert((VT.getVectorNumElements() +
3250 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3251 <= N1.getValueType().getVectorNumElements())
3252 && "Extract subvector overflow!");
3255 // Trivial extraction.
3256 if (VT.getSimpleVT() == N1.getSimpleValueType())
3263 // Perform trivial constant folding.
3264 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3265 if (SV.getNode()) return SV;
3267 // Canonicalize constant to RHS if commutative.
3268 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3269 std::swap(N1C, N2C);
3273 // Constant fold FP operations.
3274 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3275 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3277 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3278 // Canonicalize constant to RHS if commutative.
3279 std::swap(N1CFP, N2CFP);
3282 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3283 APFloat::opStatus s;
3286 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3287 if (s != APFloat::opInvalidOp)
3288 return getConstantFP(V1, VT);
3291 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3292 if (s!=APFloat::opInvalidOp)
3293 return getConstantFP(V1, VT);
3296 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3297 if (s!=APFloat::opInvalidOp)
3298 return getConstantFP(V1, VT);
3301 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3302 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3303 return getConstantFP(V1, VT);
3306 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3307 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3308 return getConstantFP(V1, VT);
3310 case ISD::FCOPYSIGN:
3312 return getConstantFP(V1, VT);
3317 if (Opcode == ISD::FP_ROUND) {
3318 APFloat V = N1CFP->getValueAPF(); // make copy
3320 // This can return overflow, underflow, or inexact; we don't care.
3321 // FIXME need to be more flexible about rounding mode.
3322 (void)V.convert(EVTToAPFloatSemantics(VT),
3323 APFloat::rmNearestTiesToEven, &ignored);
3324 return getConstantFP(V, VT);
3328 // Canonicalize an UNDEF to the RHS, even over a constant.
3329 if (N1.getOpcode() == ISD::UNDEF) {
3330 if (isCommutativeBinOp(Opcode)) {
3334 case ISD::FP_ROUND_INREG:
3335 case ISD::SIGN_EXTEND_INREG:
3341 return N1; // fold op(undef, arg2) -> undef
3349 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3350 // For vectors, we can't easily build an all zero vector, just return
3357 // Fold a bunch of operators when the RHS is undef.
3358 if (N2.getOpcode() == ISD::UNDEF) {
3361 if (N1.getOpcode() == ISD::UNDEF)
3362 // Handle undef ^ undef -> 0 special case. This is a common
3364 return getConstant(0, VT);
3374 return N2; // fold op(arg1, undef) -> undef
3380 if (getTarget().Options.UnsafeFPMath)
3388 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3389 // For vectors, we can't easily build an all zero vector, just return
3394 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3395 // For vectors, we can't easily build an all one vector, just return
3403 // Memoize this node if possible.
3405 SDVTList VTs = getVTList(VT);
3406 if (VT != MVT::Glue) {
3407 SDValue Ops[] = { N1, N2 };
3408 FoldingSetNodeID ID;
3409 AddNodeIDNode(ID, Opcode, VTs, Ops);
3411 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3412 return SDValue(E, 0);
3414 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3415 DL.getDebugLoc(), VTs, N1, N2);
3416 CSEMap.InsertNode(N, IP);
3418 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3419 DL.getDebugLoc(), VTs, N1, N2);
3422 AllNodes.push_back(N);
3426 return SDValue(N, 0);
3429 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3430 SDValue N1, SDValue N2, SDValue N3) {
3431 // Perform various simplifications.
3432 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3435 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3436 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3437 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3438 if (N1CFP && N2CFP && N3CFP) {
3439 APFloat V1 = N1CFP->getValueAPF();
3440 const APFloat &V2 = N2CFP->getValueAPF();
3441 const APFloat &V3 = N3CFP->getValueAPF();
3442 APFloat::opStatus s =
3443 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3444 if (s != APFloat::opInvalidOp)
3445 return getConstantFP(V1, VT);
3449 case ISD::CONCAT_VECTORS:
3450 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3451 // one big BUILD_VECTOR.
3452 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3453 N2.getOpcode() == ISD::BUILD_VECTOR &&
3454 N3.getOpcode() == ISD::BUILD_VECTOR) {
3455 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3456 N1.getNode()->op_end());
3457 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3458 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3459 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3463 // Use FoldSetCC to simplify SETCC's.
3464 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3465 if (Simp.getNode()) return Simp;
3470 if (N1C->getZExtValue())
3471 return N2; // select true, X, Y -> X
3472 return N3; // select false, X, Y -> Y
3475 if (N2 == N3) return N2; // select C, X, X -> X
3477 case ISD::VECTOR_SHUFFLE:
3478 llvm_unreachable("should use getVectorShuffle constructor!");
3479 case ISD::INSERT_SUBVECTOR: {
3481 if (VT.isSimple() && N1.getValueType().isSimple()
3482 && N2.getValueType().isSimple()) {
3483 assert(VT.isVector() && N1.getValueType().isVector() &&
3484 N2.getValueType().isVector() &&
3485 "Insert subvector VTs must be a vectors");
3486 assert(VT == N1.getValueType() &&
3487 "Dest and insert subvector source types must match!");
3488 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3489 "Insert subvector must be from smaller vector to larger vector!");
3490 if (isa<ConstantSDNode>(Index.getNode())) {
3491 assert((N2.getValueType().getVectorNumElements() +
3492 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3493 <= VT.getVectorNumElements())
3494 && "Insert subvector overflow!");
3497 // Trivial insertion.
3498 if (VT.getSimpleVT() == N2.getSimpleValueType())
3504 // Fold bit_convert nodes from a type to themselves.
3505 if (N1.getValueType() == VT)
3510 // Memoize node if it doesn't produce a flag.
3512 SDVTList VTs = getVTList(VT);
3513 if (VT != MVT::Glue) {
3514 SDValue Ops[] = { N1, N2, N3 };
3515 FoldingSetNodeID ID;
3516 AddNodeIDNode(ID, Opcode, VTs, Ops);
3518 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3519 return SDValue(E, 0);
3521 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3522 DL.getDebugLoc(), VTs, N1, N2, N3);
3523 CSEMap.InsertNode(N, IP);
3525 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3526 DL.getDebugLoc(), VTs, N1, N2, N3);
3529 AllNodes.push_back(N);
3533 return SDValue(N, 0);
3536 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3537 SDValue N1, SDValue N2, SDValue N3,
3539 SDValue Ops[] = { N1, N2, N3, N4 };
3540 return getNode(Opcode, DL, VT, Ops);
3543 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3544 SDValue N1, SDValue N2, SDValue N3,
3545 SDValue N4, SDValue N5) {
3546 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3547 return getNode(Opcode, DL, VT, Ops);
3550 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3551 /// the incoming stack arguments to be loaded from the stack.
3552 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3553 SmallVector<SDValue, 8> ArgChains;
3555 // Include the original chain at the beginning of the list. When this is
3556 // used by target LowerCall hooks, this helps legalize find the
3557 // CALLSEQ_BEGIN node.
3558 ArgChains.push_back(Chain);
3560 // Add a chain value for each stack argument.
3561 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3562 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3563 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3564 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3565 if (FI->getIndex() < 0)
3566 ArgChains.push_back(SDValue(L, 1));
3568 // Build a tokenfactor for all the chains.
3569 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3572 /// getMemsetValue - Vectorized representation of the memset value
3574 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3576 assert(Value.getOpcode() != ISD::UNDEF);
3578 unsigned NumBits = VT.getScalarType().getSizeInBits();
3579 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3580 assert(C->getAPIntValue().getBitWidth() == 8);
3581 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3583 return DAG.getConstant(Val, VT);
3584 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3587 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3589 // Use a multiplication with 0x010101... to extend the input to the
3591 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3592 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3598 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3599 /// used when a memcpy is turned into a memset when the source is a constant
3601 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3602 const TargetLowering &TLI, StringRef Str) {
3603 // Handle vector with all elements zero.
3606 return DAG.getConstant(0, VT);
3607 else if (VT == MVT::f32 || VT == MVT::f64)
3608 return DAG.getConstantFP(0.0, VT);
3609 else if (VT.isVector()) {
3610 unsigned NumElts = VT.getVectorNumElements();
3611 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3612 return DAG.getNode(ISD::BITCAST, dl, VT,
3613 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3616 llvm_unreachable("Expected type!");
3619 assert(!VT.isVector() && "Can't handle vector type here!");
3620 unsigned NumVTBits = VT.getSizeInBits();
3621 unsigned NumVTBytes = NumVTBits / 8;
3622 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3624 APInt Val(NumVTBits, 0);
3625 if (TLI.isLittleEndian()) {
3626 for (unsigned i = 0; i != NumBytes; ++i)
3627 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3629 for (unsigned i = 0; i != NumBytes; ++i)
3630 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3633 // If the "cost" of materializing the integer immediate is less than the cost
3634 // of a load, then it is cost effective to turn the load into the immediate.
3635 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3636 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3637 return DAG.getConstant(Val, VT);
3638 return SDValue(nullptr, 0);
3641 /// getMemBasePlusOffset - Returns base and offset node for the
3643 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3644 SelectionDAG &DAG) {
3645 EVT VT = Base.getValueType();
3646 return DAG.getNode(ISD::ADD, dl,
3647 VT, Base, DAG.getConstant(Offset, VT));
3650 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3652 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3653 unsigned SrcDelta = 0;
3654 GlobalAddressSDNode *G = nullptr;
3655 if (Src.getOpcode() == ISD::GlobalAddress)
3656 G = cast<GlobalAddressSDNode>(Src);
3657 else if (Src.getOpcode() == ISD::ADD &&
3658 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3659 Src.getOperand(1).getOpcode() == ISD::Constant) {
3660 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3661 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3666 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3669 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3670 /// to replace the memset / memcpy. Return true if the number of memory ops
3671 /// is below the threshold. It returns the types of the sequence of
3672 /// memory ops to perform memset / memcpy by reference.
3673 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3674 unsigned Limit, uint64_t Size,
3675 unsigned DstAlign, unsigned SrcAlign,
3681 const TargetLowering &TLI) {
3682 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3683 "Expecting memcpy / memset source to meet alignment requirement!");
3684 // If 'SrcAlign' is zero, that means the memory operation does not need to
3685 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3686 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3687 // is the specified alignment of the memory operation. If it is zero, that
3688 // means it's possible to change the alignment of the destination.
3689 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3690 // not need to be loaded.
3691 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3692 IsMemset, ZeroMemset, MemcpyStrSrc,
3693 DAG.getMachineFunction());
3695 if (VT == MVT::Other) {
3697 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3698 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3699 VT = TLI.getPointerTy();
3701 switch (DstAlign & 7) {
3702 case 0: VT = MVT::i64; break;
3703 case 4: VT = MVT::i32; break;
3704 case 2: VT = MVT::i16; break;
3705 default: VT = MVT::i8; break;
3710 while (!TLI.isTypeLegal(LVT))
3711 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3712 assert(LVT.isInteger());
3718 unsigned NumMemOps = 0;
3720 unsigned VTSize = VT.getSizeInBits() / 8;
3721 while (VTSize > Size) {
3722 // For now, only use non-vector load / store's for the left-over pieces.
3727 if (VT.isVector() || VT.isFloatingPoint()) {
3728 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3729 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3730 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3732 else if (NewVT == MVT::i64 &&
3733 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3734 TLI.isSafeMemOpType(MVT::f64)) {
3735 // i64 is usually not legal on 32-bit targets, but f64 may be.
3743 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3744 if (NewVT == MVT::i8)
3746 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3748 NewVTSize = NewVT.getSizeInBits() / 8;
3750 // If the new VT cannot cover all of the remaining bits, then consider
3751 // issuing a (or a pair of) unaligned and overlapping load / store.
3752 // FIXME: Only does this for 64-bit or more since we don't have proper
3753 // cost model for unaligned load / store.
3756 if (NumMemOps && AllowOverlap &&
3757 VTSize >= 8 && NewVTSize < Size &&
3758 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3766 if (++NumMemOps > Limit)
3769 MemOps.push_back(VT);
3776 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3777 SDValue Chain, SDValue Dst,
3778 SDValue Src, uint64_t Size,
3779 unsigned Align, bool isVol,
3781 MachinePointerInfo DstPtrInfo,
3782 MachinePointerInfo SrcPtrInfo) {
3783 // Turn a memcpy of undef to nop.
3784 if (Src.getOpcode() == ISD::UNDEF)
3787 // Expand memcpy to a series of load and store ops if the size operand falls
3788 // below a certain threshold.
3789 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3790 // rather than maybe a humongous number of loads and stores.
3791 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3792 std::vector<EVT> MemOps;
3793 bool DstAlignCanChange = false;
3794 MachineFunction &MF = DAG.getMachineFunction();
3795 MachineFrameInfo *MFI = MF.getFrameInfo();
3797 MF.getFunction()->getAttributes().
3798 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3799 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3800 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3801 DstAlignCanChange = true;
3802 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3803 if (Align > SrcAlign)
3806 bool CopyFromStr = isMemSrcFromString(Src, Str);
3807 bool isZeroStr = CopyFromStr && Str.empty();
3808 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3810 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3811 (DstAlignCanChange ? 0 : Align),
3812 (isZeroStr ? 0 : SrcAlign),
3813 false, false, CopyFromStr, true, DAG, TLI))
3816 if (DstAlignCanChange) {
3817 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3818 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3820 // Don't promote to an alignment that would require dynamic stack
3822 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3823 if (!TRI->needsStackRealignment(MF))
3824 while (NewAlign > Align &&
3825 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3828 if (NewAlign > Align) {
3829 // Give the stack frame object a larger alignment if needed.
3830 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3831 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3836 SmallVector<SDValue, 8> OutChains;
3837 unsigned NumMemOps = MemOps.size();
3838 uint64_t SrcOff = 0, DstOff = 0;
3839 for (unsigned i = 0; i != NumMemOps; ++i) {
3841 unsigned VTSize = VT.getSizeInBits() / 8;
3842 SDValue Value, Store;
3844 if (VTSize > Size) {
3845 // Issuing an unaligned load / store pair that overlaps with the previous
3846 // pair. Adjust the offset accordingly.
3847 assert(i == NumMemOps-1 && i != 0);
3848 SrcOff -= VTSize - Size;
3849 DstOff -= VTSize - Size;
3853 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3854 // It's unlikely a store of a vector immediate can be done in a single
3855 // instruction. It would require a load from a constantpool first.
3856 // We only handle zero vectors here.
3857 // FIXME: Handle other cases where store of vector immediate is done in
3858 // a single instruction.
3859 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3860 if (Value.getNode())
3861 Store = DAG.getStore(Chain, dl, Value,
3862 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3863 DstPtrInfo.getWithOffset(DstOff), isVol,
3867 if (!Store.getNode()) {
3868 // The type might not be legal for the target. This should only happen
3869 // if the type is smaller than a legal type, as on PPC, so the right
3870 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3871 // to Load/Store if NVT==VT.
3872 // FIXME does the case above also need this?
3873 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3874 assert(NVT.bitsGE(VT));
3875 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3876 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3877 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3878 MinAlign(SrcAlign, SrcOff));
3879 Store = DAG.getTruncStore(Chain, dl, Value,
3880 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3881 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3884 OutChains.push_back(Store);
3890 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3893 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3894 SDValue Chain, SDValue Dst,
3895 SDValue Src, uint64_t Size,
3896 unsigned Align, bool isVol,
3898 MachinePointerInfo DstPtrInfo,
3899 MachinePointerInfo SrcPtrInfo) {
3900 // Turn a memmove of undef to nop.
3901 if (Src.getOpcode() == ISD::UNDEF)
3904 // Expand memmove to a series of load and store ops if the size operand falls
3905 // below a certain threshold.
3906 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3907 std::vector<EVT> MemOps;
3908 bool DstAlignCanChange = false;
3909 MachineFunction &MF = DAG.getMachineFunction();
3910 MachineFrameInfo *MFI = MF.getFrameInfo();
3911 bool OptSize = MF.getFunction()->getAttributes().
3912 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3913 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3914 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3915 DstAlignCanChange = true;
3916 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3917 if (Align > SrcAlign)
3919 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3921 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3922 (DstAlignCanChange ? 0 : Align), SrcAlign,
3923 false, false, false, false, DAG, TLI))
3926 if (DstAlignCanChange) {
3927 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3928 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3929 if (NewAlign > Align) {
3930 // Give the stack frame object a larger alignment if needed.
3931 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3932 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3937 uint64_t SrcOff = 0, DstOff = 0;
3938 SmallVector<SDValue, 8> LoadValues;
3939 SmallVector<SDValue, 8> LoadChains;
3940 SmallVector<SDValue, 8> OutChains;
3941 unsigned NumMemOps = MemOps.size();
3942 for (unsigned i = 0; i < NumMemOps; i++) {
3944 unsigned VTSize = VT.getSizeInBits() / 8;
3947 Value = DAG.getLoad(VT, dl, Chain,
3948 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3949 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3950 false, false, SrcAlign);
3951 LoadValues.push_back(Value);
3952 LoadChains.push_back(Value.getValue(1));
3955 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3957 for (unsigned i = 0; i < NumMemOps; i++) {
3959 unsigned VTSize = VT.getSizeInBits() / 8;
3962 Store = DAG.getStore(Chain, dl, LoadValues[i],
3963 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3964 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3965 OutChains.push_back(Store);
3969 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3972 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3975 /// \param DAG Selection DAG where lowered code is placed.
3976 /// \param dl Link to corresponding IR location.
3977 /// \param Chain Control flow dependency.
3978 /// \param Dst Pointer to destination memory location.
3979 /// \param Src Value of byte to write into the memory.
3980 /// \param Size Number of bytes to write.
3981 /// \param Align Alignment of the destination in bytes.
3982 /// \param isVol True if destination is volatile.
3983 /// \param DstPtrInfo IR information on the memory pointer.
3984 /// \returns New head in the control flow, if lowering was successful, empty
3985 /// SDValue otherwise.
3987 /// The function tries to replace 'llvm.memset' intrinsic with several store
3988 /// operations and value calculation code. This is usually profitable for small
3990 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3991 SDValue Chain, SDValue Dst,
3992 SDValue Src, uint64_t Size,
3993 unsigned Align, bool isVol,
3994 MachinePointerInfo DstPtrInfo) {
3995 // Turn a memset of undef to nop.
3996 if (Src.getOpcode() == ISD::UNDEF)
3999 // Expand memset to a series of load/store ops if the size operand
4000 // falls below a certain threshold.
4001 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4002 std::vector<EVT> MemOps;
4003 bool DstAlignCanChange = false;
4004 MachineFunction &MF = DAG.getMachineFunction();
4005 MachineFrameInfo *MFI = MF.getFrameInfo();
4006 bool OptSize = MF.getFunction()->getAttributes().
4007 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4008 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4009 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4010 DstAlignCanChange = true;
4012 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4013 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4014 Size, (DstAlignCanChange ? 0 : Align), 0,
4015 true, IsZeroVal, false, true, DAG, TLI))
4018 if (DstAlignCanChange) {
4019 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4020 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4021 if (NewAlign > Align) {
4022 // Give the stack frame object a larger alignment if needed.
4023 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4024 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4029 SmallVector<SDValue, 8> OutChains;
4030 uint64_t DstOff = 0;
4031 unsigned NumMemOps = MemOps.size();
4033 // Find the largest store and generate the bit pattern for it.
4034 EVT LargestVT = MemOps[0];
4035 for (unsigned i = 1; i < NumMemOps; i++)
4036 if (MemOps[i].bitsGT(LargestVT))
4037 LargestVT = MemOps[i];
4038 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4040 for (unsigned i = 0; i < NumMemOps; i++) {
4042 unsigned VTSize = VT.getSizeInBits() / 8;
4043 if (VTSize > Size) {
4044 // Issuing an unaligned load / store pair that overlaps with the previous
4045 // pair. Adjust the offset accordingly.
4046 assert(i == NumMemOps-1 && i != 0);
4047 DstOff -= VTSize - Size;
4050 // If this store is smaller than the largest store see whether we can get
4051 // the smaller value for free with a truncate.
4052 SDValue Value = MemSetValue;
4053 if (VT.bitsLT(LargestVT)) {
4054 if (!LargestVT.isVector() && !VT.isVector() &&
4055 TLI.isTruncateFree(LargestVT, VT))
4056 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4058 Value = getMemsetValue(Src, VT, DAG, dl);
4060 assert(Value.getValueType() == VT && "Value with wrong type.");
4061 SDValue Store = DAG.getStore(Chain, dl, Value,
4062 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4063 DstPtrInfo.getWithOffset(DstOff),
4064 isVol, false, Align);
4065 OutChains.push_back(Store);
4066 DstOff += VT.getSizeInBits() / 8;
4070 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4073 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4074 SDValue Src, SDValue Size,
4075 unsigned Align, bool isVol, bool AlwaysInline,
4076 MachinePointerInfo DstPtrInfo,
4077 MachinePointerInfo SrcPtrInfo) {
4078 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4080 // Check to see if we should lower the memcpy to loads and stores first.
4081 // For cases within the target-specified limits, this is the best choice.
4082 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4084 // Memcpy with size zero? Just return the original chain.
4085 if (ConstantSize->isNullValue())
4088 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4089 ConstantSize->getZExtValue(),Align,
4090 isVol, false, DstPtrInfo, SrcPtrInfo);
4091 if (Result.getNode())
4095 // Then check to see if we should lower the memcpy with target-specific
4096 // code. If the target chooses to do this, this is the next best.
4098 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4099 isVol, AlwaysInline,
4100 DstPtrInfo, SrcPtrInfo);
4101 if (Result.getNode())
4104 // If we really need inline code and the target declined to provide it,
4105 // use a (potentially long) sequence of loads and stores.
4107 assert(ConstantSize && "AlwaysInline requires a constant size!");
4108 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4109 ConstantSize->getZExtValue(), Align, isVol,
4110 true, DstPtrInfo, SrcPtrInfo);
4113 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4114 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4115 // respect volatile, so they may do things like read or write memory
4116 // beyond the given memory regions. But fixing this isn't easy, and most
4117 // people don't care.
4119 const TargetLowering *TLI = TM.getTargetLowering();
4121 // Emit a library call.
4122 TargetLowering::ArgListTy Args;
4123 TargetLowering::ArgListEntry Entry;
4124 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4125 Entry.Node = Dst; Args.push_back(Entry);
4126 Entry.Node = Src; Args.push_back(Entry);
4127 Entry.Node = Size; Args.push_back(Entry);
4128 // FIXME: pass in SDLoc
4130 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4131 false, false, false, false, 0,
4132 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4133 /*isTailCall=*/false,
4134 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4135 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4136 TLI->getPointerTy()),
4138 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4140 return CallResult.second;
4143 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4144 SDValue Src, SDValue Size,
4145 unsigned Align, bool isVol,
4146 MachinePointerInfo DstPtrInfo,
4147 MachinePointerInfo SrcPtrInfo) {
4148 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4150 // Check to see if we should lower the memmove to loads and stores first.
4151 // For cases within the target-specified limits, this is the best choice.
4152 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4154 // Memmove with size zero? Just return the original chain.
4155 if (ConstantSize->isNullValue())
4159 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4160 ConstantSize->getZExtValue(), Align, isVol,
4161 false, DstPtrInfo, SrcPtrInfo);
4162 if (Result.getNode())
4166 // Then check to see if we should lower the memmove with target-specific
4167 // code. If the target chooses to do this, this is the next best.
4169 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4170 DstPtrInfo, SrcPtrInfo);
4171 if (Result.getNode())
4174 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4175 // not be safe. See memcpy above for more details.
4177 const TargetLowering *TLI = TM.getTargetLowering();
4179 // Emit a library call.
4180 TargetLowering::ArgListTy Args;
4181 TargetLowering::ArgListEntry Entry;
4182 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4183 Entry.Node = Dst; Args.push_back(Entry);
4184 Entry.Node = Src; Args.push_back(Entry);
4185 Entry.Node = Size; Args.push_back(Entry);
4186 // FIXME: pass in SDLoc
4188 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4189 false, false, false, false, 0,
4190 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4191 /*isTailCall=*/false,
4192 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4193 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4194 TLI->getPointerTy()),
4196 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4198 return CallResult.second;
4201 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4202 SDValue Src, SDValue Size,
4203 unsigned Align, bool isVol,
4204 MachinePointerInfo DstPtrInfo) {
4205 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4207 // Check to see if we should lower the memset to stores first.
4208 // For cases within the target-specified limits, this is the best choice.
4209 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4211 // Memset with size zero? Just return the original chain.
4212 if (ConstantSize->isNullValue())
4216 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4217 Align, isVol, DstPtrInfo);
4219 if (Result.getNode())
4223 // Then check to see if we should lower the memset with target-specific
4224 // code. If the target chooses to do this, this is the next best.
4226 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4228 if (Result.getNode())
4231 // Emit a library call.
4232 const TargetLowering *TLI = TM.getTargetLowering();
4233 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4234 TargetLowering::ArgListTy Args;
4235 TargetLowering::ArgListEntry Entry;
4236 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4237 Args.push_back(Entry);
4238 // Extend or truncate the argument to be an i32 value for the call.
4239 if (Src.getValueType().bitsGT(MVT::i32))
4240 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4242 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4244 Entry.Ty = Type::getInt32Ty(*getContext());
4245 Entry.isSExt = true;
4246 Args.push_back(Entry);
4248 Entry.Ty = IntPtrTy;
4249 Entry.isSExt = false;
4250 Args.push_back(Entry);
4251 // FIXME: pass in SDLoc
4253 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4254 false, false, false, false, 0,
4255 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4256 /*isTailCall=*/false,
4257 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4258 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4259 TLI->getPointerTy()),
4261 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4263 return CallResult.second;
4266 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4267 SDVTList VTList, ArrayRef<SDValue> Ops,
4268 MachineMemOperand *MMO,
4269 AtomicOrdering SuccessOrdering,
4270 AtomicOrdering FailureOrdering,
4271 SynchronizationScope SynchScope) {
4272 FoldingSetNodeID ID;
4273 ID.AddInteger(MemVT.getRawBits());
4274 AddNodeIDNode(ID, Opcode, VTList, Ops);
4275 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4277 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4278 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4279 return SDValue(E, 0);
4282 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4283 // SDNode doesn't have access to it. This memory will be "leaked" when
4284 // the node is deallocated, but recovered when the allocator is released.
4285 // If the number of operands is less than 5 we use AtomicSDNode's internal
4287 unsigned NumOps = Ops.size();
4288 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4291 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4292 dl.getDebugLoc(), VTList, MemVT,
4293 Ops.data(), DynOps, NumOps, MMO,
4294 SuccessOrdering, FailureOrdering,
4296 CSEMap.InsertNode(N, IP);
4297 AllNodes.push_back(N);
4298 return SDValue(N, 0);
4301 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4302 SDVTList VTList, ArrayRef<SDValue> Ops,
4303 MachineMemOperand *MMO,
4304 AtomicOrdering Ordering,
4305 SynchronizationScope SynchScope) {
4306 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4307 Ordering, SynchScope);
4310 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4311 SDValue Chain, SDValue Ptr, SDValue Cmp,
4312 SDValue Swp, MachinePointerInfo PtrInfo,
4314 AtomicOrdering SuccessOrdering,
4315 AtomicOrdering FailureOrdering,
4316 SynchronizationScope SynchScope) {
4317 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4318 Alignment = getEVTAlignment(MemVT);
4320 MachineFunction &MF = getMachineFunction();
4322 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4323 // For now, atomics are considered to be volatile always.
4324 // FIXME: Volatile isn't really correct; we should keep track of atomic
4325 // orderings in the memoperand.
4326 unsigned Flags = MachineMemOperand::MOVolatile;
4327 if (Opcode != ISD::ATOMIC_STORE)
4328 Flags |= MachineMemOperand::MOLoad;
4329 if (Opcode != ISD::ATOMIC_LOAD)
4330 Flags |= MachineMemOperand::MOStore;
4332 MachineMemOperand *MMO =
4333 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4335 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4336 SuccessOrdering, FailureOrdering, SynchScope);
4339 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4341 SDValue Ptr, SDValue Cmp,
4342 SDValue Swp, MachineMemOperand *MMO,
4343 AtomicOrdering SuccessOrdering,
4344 AtomicOrdering FailureOrdering,
4345 SynchronizationScope SynchScope) {
4346 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4347 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4349 EVT VT = Cmp.getValueType();
4351 SDVTList VTs = getVTList(VT, MVT::Other);
4352 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4353 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4354 FailureOrdering, SynchScope);
4357 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4359 SDValue Ptr, SDValue Val,
4360 const Value* PtrVal,
4362 AtomicOrdering Ordering,
4363 SynchronizationScope SynchScope) {
4364 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4365 Alignment = getEVTAlignment(MemVT);
4367 MachineFunction &MF = getMachineFunction();
4368 // An atomic store does not load. An atomic load does not store.
4369 // (An atomicrmw obviously both loads and stores.)
4370 // For now, atomics are considered to be volatile always, and they are
4372 // FIXME: Volatile isn't really correct; we should keep track of atomic
4373 // orderings in the memoperand.
4374 unsigned Flags = MachineMemOperand::MOVolatile;
4375 if (Opcode != ISD::ATOMIC_STORE)
4376 Flags |= MachineMemOperand::MOLoad;
4377 if (Opcode != ISD::ATOMIC_LOAD)
4378 Flags |= MachineMemOperand::MOStore;
4380 MachineMemOperand *MMO =
4381 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4382 MemVT.getStoreSize(), Alignment);
4384 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4385 Ordering, SynchScope);
4388 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4390 SDValue Ptr, SDValue Val,
4391 MachineMemOperand *MMO,
4392 AtomicOrdering Ordering,
4393 SynchronizationScope SynchScope) {
4394 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4395 Opcode == ISD::ATOMIC_LOAD_SUB ||
4396 Opcode == ISD::ATOMIC_LOAD_AND ||
4397 Opcode == ISD::ATOMIC_LOAD_OR ||
4398 Opcode == ISD::ATOMIC_LOAD_XOR ||
4399 Opcode == ISD::ATOMIC_LOAD_NAND ||
4400 Opcode == ISD::ATOMIC_LOAD_MIN ||
4401 Opcode == ISD::ATOMIC_LOAD_MAX ||
4402 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4403 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4404 Opcode == ISD::ATOMIC_SWAP ||
4405 Opcode == ISD::ATOMIC_STORE) &&
4406 "Invalid Atomic Op");
4408 EVT VT = Val.getValueType();
4410 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4411 getVTList(VT, MVT::Other);
4412 SDValue Ops[] = {Chain, Ptr, Val};
4413 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4416 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4417 EVT VT, SDValue Chain,
4419 MachineMemOperand *MMO,
4420 AtomicOrdering Ordering,
4421 SynchronizationScope SynchScope) {
4422 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4424 SDVTList VTs = getVTList(VT, MVT::Other);
4425 SDValue Ops[] = {Chain, Ptr};
4426 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4429 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4430 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4431 if (Ops.size() == 1)
4434 SmallVector<EVT, 4> VTs;
4435 VTs.reserve(Ops.size());
4436 for (unsigned i = 0; i < Ops.size(); ++i)
4437 VTs.push_back(Ops[i].getValueType());
4438 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4442 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4443 ArrayRef<SDValue> Ops,
4444 EVT MemVT, MachinePointerInfo PtrInfo,
4445 unsigned Align, bool Vol,
4446 bool ReadMem, bool WriteMem) {
4447 if (Align == 0) // Ensure that codegen never sees alignment 0
4448 Align = getEVTAlignment(MemVT);
4450 MachineFunction &MF = getMachineFunction();
4453 Flags |= MachineMemOperand::MOStore;
4455 Flags |= MachineMemOperand::MOLoad;
4457 Flags |= MachineMemOperand::MOVolatile;
4458 MachineMemOperand *MMO =
4459 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4461 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4465 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4466 ArrayRef<SDValue> Ops, EVT MemVT,
4467 MachineMemOperand *MMO) {
4468 assert((Opcode == ISD::INTRINSIC_VOID ||
4469 Opcode == ISD::INTRINSIC_W_CHAIN ||
4470 Opcode == ISD::PREFETCH ||
4471 Opcode == ISD::LIFETIME_START ||
4472 Opcode == ISD::LIFETIME_END ||
4473 (Opcode <= INT_MAX &&
4474 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4475 "Opcode is not a memory-accessing opcode!");
4477 // Memoize the node unless it returns a flag.
4478 MemIntrinsicSDNode *N;
4479 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4480 FoldingSetNodeID ID;
4481 AddNodeIDNode(ID, Opcode, VTList, Ops);
4482 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4484 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4485 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4486 return SDValue(E, 0);
4489 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4490 dl.getDebugLoc(), VTList, Ops,
4492 CSEMap.InsertNode(N, IP);
4494 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4495 dl.getDebugLoc(), VTList, Ops,
4498 AllNodes.push_back(N);
4499 return SDValue(N, 0);
4502 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4503 /// MachinePointerInfo record from it. This is particularly useful because the
4504 /// code generator has many cases where it doesn't bother passing in a
4505 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4506 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4507 // If this is FI+Offset, we can model it.
4508 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4509 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4511 // If this is (FI+Offset1)+Offset2, we can model it.
4512 if (Ptr.getOpcode() != ISD::ADD ||
4513 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4514 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4515 return MachinePointerInfo();
4517 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4518 return MachinePointerInfo::getFixedStack(FI, Offset+
4519 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4522 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4523 /// MachinePointerInfo record from it. This is particularly useful because the
4524 /// code generator has many cases where it doesn't bother passing in a
4525 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4526 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4527 // If the 'Offset' value isn't a constant, we can't handle this.
4528 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4529 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4530 if (OffsetOp.getOpcode() == ISD::UNDEF)
4531 return InferPointerInfo(Ptr);
4532 return MachinePointerInfo();
4537 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4538 EVT VT, SDLoc dl, SDValue Chain,
4539 SDValue Ptr, SDValue Offset,
4540 MachinePointerInfo PtrInfo, EVT MemVT,
4541 bool isVolatile, bool isNonTemporal, bool isInvariant,
4542 unsigned Alignment, const MDNode *TBAAInfo,
4543 const MDNode *Ranges) {
4544 assert(Chain.getValueType() == MVT::Other &&
4545 "Invalid chain type");
4546 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4547 Alignment = getEVTAlignment(VT);
4549 unsigned Flags = MachineMemOperand::MOLoad;
4551 Flags |= MachineMemOperand::MOVolatile;
4553 Flags |= MachineMemOperand::MONonTemporal;
4555 Flags |= MachineMemOperand::MOInvariant;
4557 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4559 if (PtrInfo.V.isNull())
4560 PtrInfo = InferPointerInfo(Ptr, Offset);
4562 MachineFunction &MF = getMachineFunction();
4563 MachineMemOperand *MMO =
4564 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4566 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4570 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4571 EVT VT, SDLoc dl, SDValue Chain,
4572 SDValue Ptr, SDValue Offset, EVT MemVT,
4573 MachineMemOperand *MMO) {
4575 ExtType = ISD::NON_EXTLOAD;
4576 } else if (ExtType == ISD::NON_EXTLOAD) {
4577 assert(VT == MemVT && "Non-extending load from different memory type!");
4580 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4581 "Should only be an extending load, not truncating!");
4582 assert(VT.isInteger() == MemVT.isInteger() &&
4583 "Cannot convert from FP to Int or Int -> FP!");
4584 assert(VT.isVector() == MemVT.isVector() &&
4585 "Cannot use trunc store to convert to or from a vector!");
4586 assert((!VT.isVector() ||
4587 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4588 "Cannot use trunc store to change the number of vector elements!");
4591 bool Indexed = AM != ISD::UNINDEXED;
4592 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4593 "Unindexed load with an offset!");
4595 SDVTList VTs = Indexed ?
4596 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4597 SDValue Ops[] = { Chain, Ptr, Offset };
4598 FoldingSetNodeID ID;
4599 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4600 ID.AddInteger(MemVT.getRawBits());
4601 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4602 MMO->isNonTemporal(),
4603 MMO->isInvariant()));
4604 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4606 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4607 cast<LoadSDNode>(E)->refineAlignment(MMO);
4608 return SDValue(E, 0);
4610 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4611 dl.getDebugLoc(), VTs, AM, ExtType,
4613 CSEMap.InsertNode(N, IP);
4614 AllNodes.push_back(N);
4615 return SDValue(N, 0);
4618 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4619 SDValue Chain, SDValue Ptr,
4620 MachinePointerInfo PtrInfo,
4621 bool isVolatile, bool isNonTemporal,
4622 bool isInvariant, unsigned Alignment,
4623 const MDNode *TBAAInfo,
4624 const MDNode *Ranges) {
4625 SDValue Undef = getUNDEF(Ptr.getValueType());
4626 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4627 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4631 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4632 SDValue Chain, SDValue Ptr,
4633 MachineMemOperand *MMO) {
4634 SDValue Undef = getUNDEF(Ptr.getValueType());
4635 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4639 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4640 SDValue Chain, SDValue Ptr,
4641 MachinePointerInfo PtrInfo, EVT MemVT,
4642 bool isVolatile, bool isNonTemporal,
4643 unsigned Alignment, const MDNode *TBAAInfo) {
4644 SDValue Undef = getUNDEF(Ptr.getValueType());
4645 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4646 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4651 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4652 SDValue Chain, SDValue Ptr, EVT MemVT,
4653 MachineMemOperand *MMO) {
4654 SDValue Undef = getUNDEF(Ptr.getValueType());
4655 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4660 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4661 SDValue Offset, ISD::MemIndexedMode AM) {
4662 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4663 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4664 "Load is already a indexed load!");
4665 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4666 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4667 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4668 false, LD->getAlignment());
4671 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4672 SDValue Ptr, MachinePointerInfo PtrInfo,
4673 bool isVolatile, bool isNonTemporal,
4674 unsigned Alignment, const MDNode *TBAAInfo) {
4675 assert(Chain.getValueType() == MVT::Other &&
4676 "Invalid chain type");
4677 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4678 Alignment = getEVTAlignment(Val.getValueType());
4680 unsigned Flags = MachineMemOperand::MOStore;
4682 Flags |= MachineMemOperand::MOVolatile;
4684 Flags |= MachineMemOperand::MONonTemporal;
4686 if (PtrInfo.V.isNull())
4687 PtrInfo = InferPointerInfo(Ptr);
4689 MachineFunction &MF = getMachineFunction();
4690 MachineMemOperand *MMO =
4691 MF.getMachineMemOperand(PtrInfo, Flags,
4692 Val.getValueType().getStoreSize(), Alignment,
4695 return getStore(Chain, dl, Val, Ptr, MMO);
4698 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4699 SDValue Ptr, MachineMemOperand *MMO) {
4700 assert(Chain.getValueType() == MVT::Other &&
4701 "Invalid chain type");
4702 EVT VT = Val.getValueType();
4703 SDVTList VTs = getVTList(MVT::Other);
4704 SDValue Undef = getUNDEF(Ptr.getValueType());
4705 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4706 FoldingSetNodeID ID;
4707 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4708 ID.AddInteger(VT.getRawBits());
4709 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4710 MMO->isNonTemporal(), MMO->isInvariant()));
4711 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4713 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4714 cast<StoreSDNode>(E)->refineAlignment(MMO);
4715 return SDValue(E, 0);
4717 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4718 dl.getDebugLoc(), VTs,
4719 ISD::UNINDEXED, false, VT, MMO);
4720 CSEMap.InsertNode(N, IP);
4721 AllNodes.push_back(N);
4722 return SDValue(N, 0);
4725 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4726 SDValue Ptr, MachinePointerInfo PtrInfo,
4727 EVT SVT,bool isVolatile, bool isNonTemporal,
4729 const MDNode *TBAAInfo) {
4730 assert(Chain.getValueType() == MVT::Other &&
4731 "Invalid chain type");
4732 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4733 Alignment = getEVTAlignment(SVT);
4735 unsigned Flags = MachineMemOperand::MOStore;
4737 Flags |= MachineMemOperand::MOVolatile;
4739 Flags |= MachineMemOperand::MONonTemporal;
4741 if (PtrInfo.V.isNull())
4742 PtrInfo = InferPointerInfo(Ptr);
4744 MachineFunction &MF = getMachineFunction();
4745 MachineMemOperand *MMO =
4746 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4749 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4752 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4753 SDValue Ptr, EVT SVT,
4754 MachineMemOperand *MMO) {
4755 EVT VT = Val.getValueType();
4757 assert(Chain.getValueType() == MVT::Other &&
4758 "Invalid chain type");
4760 return getStore(Chain, dl, Val, Ptr, MMO);
4762 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4763 "Should only be a truncating store, not extending!");
4764 assert(VT.isInteger() == SVT.isInteger() &&
4765 "Can't do FP-INT conversion!");
4766 assert(VT.isVector() == SVT.isVector() &&
4767 "Cannot use trunc store to convert to or from a vector!");
4768 assert((!VT.isVector() ||
4769 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4770 "Cannot use trunc store to change the number of vector elements!");
4772 SDVTList VTs = getVTList(MVT::Other);
4773 SDValue Undef = getUNDEF(Ptr.getValueType());
4774 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4775 FoldingSetNodeID ID;
4776 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4777 ID.AddInteger(SVT.getRawBits());
4778 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4779 MMO->isNonTemporal(), MMO->isInvariant()));
4780 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4782 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4783 cast<StoreSDNode>(E)->refineAlignment(MMO);
4784 return SDValue(E, 0);
4786 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4787 dl.getDebugLoc(), VTs,
4788 ISD::UNINDEXED, true, SVT, MMO);
4789 CSEMap.InsertNode(N, IP);
4790 AllNodes.push_back(N);
4791 return SDValue(N, 0);
4795 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4796 SDValue Offset, ISD::MemIndexedMode AM) {
4797 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4798 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4799 "Store is already a indexed store!");
4800 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4801 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4802 FoldingSetNodeID ID;
4803 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4804 ID.AddInteger(ST->getMemoryVT().getRawBits());
4805 ID.AddInteger(ST->getRawSubclassData());
4806 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4808 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4809 return SDValue(E, 0);
4811 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4812 dl.getDebugLoc(), VTs, AM,
4813 ST->isTruncatingStore(),
4815 ST->getMemOperand());
4816 CSEMap.InsertNode(N, IP);
4817 AllNodes.push_back(N);
4818 return SDValue(N, 0);
4821 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4822 SDValue Chain, SDValue Ptr,
4825 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4826 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4829 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4830 ArrayRef<SDUse> Ops) {
4831 switch (Ops.size()) {
4832 case 0: return getNode(Opcode, DL, VT);
4833 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4834 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4835 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4839 // Copy from an SDUse array into an SDValue array for use with
4840 // the regular getNode logic.
4841 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4842 return getNode(Opcode, DL, VT, NewOps);
4845 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4846 ArrayRef<SDValue> Ops) {
4847 unsigned NumOps = Ops.size();
4849 case 0: return getNode(Opcode, DL, VT);
4850 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4851 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4852 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4858 case ISD::SELECT_CC: {
4859 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4860 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4861 "LHS and RHS of condition must have same type!");
4862 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4863 "True and False arms of SelectCC must have same type!");
4864 assert(Ops[2].getValueType() == VT &&
4865 "select_cc node must be of same type as true and false value!");
4869 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4870 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4871 "LHS/RHS of comparison should match types!");
4878 SDVTList VTs = getVTList(VT);
4880 if (VT != MVT::Glue) {
4881 FoldingSetNodeID ID;
4882 AddNodeIDNode(ID, Opcode, VTs, Ops);
4885 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4886 return SDValue(E, 0);
4888 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4890 CSEMap.InsertNode(N, IP);
4892 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4896 AllNodes.push_back(N);
4900 return SDValue(N, 0);
4903 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4904 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4905 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4908 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4909 ArrayRef<SDValue> Ops) {
4910 if (VTList.NumVTs == 1)
4911 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4915 // FIXME: figure out how to safely handle things like
4916 // int foo(int x) { return 1 << (x & 255); }
4917 // int bar() { return foo(256); }
4918 case ISD::SRA_PARTS:
4919 case ISD::SRL_PARTS:
4920 case ISD::SHL_PARTS:
4921 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4922 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4923 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4924 else if (N3.getOpcode() == ISD::AND)
4925 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4926 // If the and is only masking out bits that cannot effect the shift,
4927 // eliminate the and.
4928 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4929 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4930 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4936 // Memoize the node unless it returns a flag.
4938 unsigned NumOps = Ops.size();
4939 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4940 FoldingSetNodeID ID;
4941 AddNodeIDNode(ID, Opcode, VTList, Ops);
4943 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4944 return SDValue(E, 0);
4947 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4948 DL.getDebugLoc(), VTList, Ops[0]);
4949 } else if (NumOps == 2) {
4950 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4951 DL.getDebugLoc(), VTList, Ops[0],
4953 } else if (NumOps == 3) {
4954 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4955 DL.getDebugLoc(), VTList, Ops[0],
4958 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4961 CSEMap.InsertNode(N, IP);
4964 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4965 DL.getDebugLoc(), VTList, Ops[0]);
4966 } else if (NumOps == 2) {
4967 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4968 DL.getDebugLoc(), VTList, Ops[0],
4970 } else if (NumOps == 3) {
4971 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4972 DL.getDebugLoc(), VTList, Ops[0],
4975 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4979 AllNodes.push_back(N);
4983 return SDValue(N, 0);
4986 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4987 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4990 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4992 SDValue Ops[] = { N1 };
4993 return getNode(Opcode, DL, VTList, Ops);
4996 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4997 SDValue N1, SDValue N2) {
4998 SDValue Ops[] = { N1, N2 };
4999 return getNode(Opcode, DL, VTList, Ops);
5002 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5003 SDValue N1, SDValue N2, SDValue N3) {
5004 SDValue Ops[] = { N1, N2, N3 };
5005 return getNode(Opcode, DL, VTList, Ops);
5008 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5009 SDValue N1, SDValue N2, SDValue N3,
5011 SDValue Ops[] = { N1, N2, N3, N4 };
5012 return getNode(Opcode, DL, VTList, Ops);
5015 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5016 SDValue N1, SDValue N2, SDValue N3,
5017 SDValue N4, SDValue N5) {
5018 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5019 return getNode(Opcode, DL, VTList, Ops);
5022 SDVTList SelectionDAG::getVTList(EVT VT) {
5023 return makeVTList(SDNode::getValueTypeList(VT), 1);
5026 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5027 FoldingSetNodeID ID;
5029 ID.AddInteger(VT1.getRawBits());
5030 ID.AddInteger(VT2.getRawBits());
5033 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5035 EVT *Array = Allocator.Allocate<EVT>(2);
5038 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5039 VTListMap.InsertNode(Result, IP);
5041 return Result->getSDVTList();
5044 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5045 FoldingSetNodeID ID;
5047 ID.AddInteger(VT1.getRawBits());
5048 ID.AddInteger(VT2.getRawBits());
5049 ID.AddInteger(VT3.getRawBits());
5052 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5054 EVT *Array = Allocator.Allocate<EVT>(3);
5058 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5059 VTListMap.InsertNode(Result, IP);
5061 return Result->getSDVTList();
5064 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5065 FoldingSetNodeID ID;
5067 ID.AddInteger(VT1.getRawBits());
5068 ID.AddInteger(VT2.getRawBits());
5069 ID.AddInteger(VT3.getRawBits());
5070 ID.AddInteger(VT4.getRawBits());
5073 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5075 EVT *Array = Allocator.Allocate<EVT>(4);
5080 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5081 VTListMap.InsertNode(Result, IP);
5083 return Result->getSDVTList();
5086 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5087 unsigned NumVTs = VTs.size();
5088 FoldingSetNodeID ID;
5089 ID.AddInteger(NumVTs);
5090 for (unsigned index = 0; index < NumVTs; index++) {
5091 ID.AddInteger(VTs[index].getRawBits());
5095 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5097 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5098 std::copy(VTs.begin(), VTs.end(), Array);
5099 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5100 VTListMap.InsertNode(Result, IP);
5102 return Result->getSDVTList();
5106 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5107 /// specified operands. If the resultant node already exists in the DAG,
5108 /// this does not modify the specified node, instead it returns the node that
5109 /// already exists. If the resultant node does not exist in the DAG, the
5110 /// input node is returned. As a degenerate case, if you specify the same
5111 /// input operands as the node already has, the input node is returned.
5112 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5113 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5115 // Check to see if there is no change.
5116 if (Op == N->getOperand(0)) return N;
5118 // See if the modified node already exists.
5119 void *InsertPos = nullptr;
5120 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5123 // Nope it doesn't. Remove the node from its current place in the maps.
5125 if (!RemoveNodeFromCSEMaps(N))
5126 InsertPos = nullptr;
5128 // Now we update the operands.
5129 N->OperandList[0].set(Op);
5131 // If this gets put into a CSE map, add it.
5132 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5136 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5137 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5139 // Check to see if there is no change.
5140 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5141 return N; // No operands changed, just return the input node.
5143 // See if the modified node already exists.
5144 void *InsertPos = nullptr;
5145 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5148 // Nope it doesn't. Remove the node from its current place in the maps.
5150 if (!RemoveNodeFromCSEMaps(N))
5151 InsertPos = nullptr;
5153 // Now we update the operands.
5154 if (N->OperandList[0] != Op1)
5155 N->OperandList[0].set(Op1);
5156 if (N->OperandList[1] != Op2)
5157 N->OperandList[1].set(Op2);
5159 // If this gets put into a CSE map, add it.
5160 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5164 SDNode *SelectionDAG::
5165 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5166 SDValue Ops[] = { Op1, Op2, Op3 };
5167 return UpdateNodeOperands(N, Ops);
5170 SDNode *SelectionDAG::
5171 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5172 SDValue Op3, SDValue Op4) {
5173 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5174 return UpdateNodeOperands(N, Ops);
5177 SDNode *SelectionDAG::
5178 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5179 SDValue Op3, SDValue Op4, SDValue Op5) {
5180 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5181 return UpdateNodeOperands(N, Ops);
5184 SDNode *SelectionDAG::
5185 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5186 unsigned NumOps = Ops.size();
5187 assert(N->getNumOperands() == NumOps &&
5188 "Update with wrong number of operands");
5190 // Check to see if there is no change.
5191 bool AnyChange = false;
5192 for (unsigned i = 0; i != NumOps; ++i) {
5193 if (Ops[i] != N->getOperand(i)) {
5199 // No operands changed, just return the input node.
5200 if (!AnyChange) return N;
5202 // See if the modified node already exists.
5203 void *InsertPos = nullptr;
5204 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5207 // Nope it doesn't. Remove the node from its current place in the maps.
5209 if (!RemoveNodeFromCSEMaps(N))
5210 InsertPos = nullptr;
5212 // Now we update the operands.
5213 for (unsigned i = 0; i != NumOps; ++i)
5214 if (N->OperandList[i] != Ops[i])
5215 N->OperandList[i].set(Ops[i]);
5217 // If this gets put into a CSE map, add it.
5218 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5222 /// DropOperands - Release the operands and set this node to have
5224 void SDNode::DropOperands() {
5225 // Unlike the code in MorphNodeTo that does this, we don't need to
5226 // watch for dead nodes here.
5227 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5233 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5236 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5238 SDVTList VTs = getVTList(VT);
5239 return SelectNodeTo(N, MachineOpc, VTs, None);
5242 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5243 EVT VT, SDValue Op1) {
5244 SDVTList VTs = getVTList(VT);
5245 SDValue Ops[] = { Op1 };
5246 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5249 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5250 EVT VT, SDValue Op1,
5252 SDVTList VTs = getVTList(VT);
5253 SDValue Ops[] = { Op1, Op2 };
5254 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5257 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 EVT VT, SDValue Op1,
5259 SDValue Op2, SDValue Op3) {
5260 SDVTList VTs = getVTList(VT);
5261 SDValue Ops[] = { Op1, Op2, Op3 };
5262 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5265 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5266 EVT VT, ArrayRef<SDValue> Ops) {
5267 SDVTList VTs = getVTList(VT);
5268 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5271 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5272 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5273 SDVTList VTs = getVTList(VT1, VT2);
5274 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5277 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5279 SDVTList VTs = getVTList(VT1, VT2);
5280 return SelectNodeTo(N, MachineOpc, VTs, None);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5284 EVT VT1, EVT VT2, EVT VT3,
5285 ArrayRef<SDValue> Ops) {
5286 SDVTList VTs = getVTList(VT1, VT2, VT3);
5287 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5290 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5291 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5292 ArrayRef<SDValue> Ops) {
5293 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5294 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5297 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5300 SDVTList VTs = getVTList(VT1, VT2);
5301 SDValue Ops[] = { Op1 };
5302 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5305 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5307 SDValue Op1, SDValue Op2) {
5308 SDVTList VTs = getVTList(VT1, VT2);
5309 SDValue Ops[] = { Op1, Op2 };
5310 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5313 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5315 SDValue Op1, SDValue Op2,
5317 SDVTList VTs = getVTList(VT1, VT2);
5318 SDValue Ops[] = { Op1, Op2, Op3 };
5319 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5322 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5323 EVT VT1, EVT VT2, EVT VT3,
5324 SDValue Op1, SDValue Op2,
5326 SDVTList VTs = getVTList(VT1, VT2, VT3);
5327 SDValue Ops[] = { Op1, Op2, Op3 };
5328 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5331 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5332 SDVTList VTs,ArrayRef<SDValue> Ops) {
5333 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5334 // Reset the NodeID to -1.
5339 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5340 /// the line number information on the merged node since it is not possible to
5341 /// preserve the information that operation is associated with multiple lines.
5342 /// This will make the debugger working better at -O0, were there is a higher
5343 /// probability having other instructions associated with that line.
5345 /// For IROrder, we keep the smaller of the two
5346 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5347 DebugLoc NLoc = N->getDebugLoc();
5348 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5349 (OLoc.getDebugLoc() != NLoc)) {
5350 N->setDebugLoc(DebugLoc());
5352 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5353 N->setIROrder(Order);
5357 /// MorphNodeTo - This *mutates* the specified node to have the specified
5358 /// return type, opcode, and operands.
5360 /// Note that MorphNodeTo returns the resultant node. If there is already a
5361 /// node of the specified opcode and operands, it returns that node instead of
5362 /// the current one. Note that the SDLoc need not be the same.
5364 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5365 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5366 /// node, and because it doesn't require CSE recalculation for any of
5367 /// the node's users.
5369 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5370 SDVTList VTs, ArrayRef<SDValue> Ops) {
5371 unsigned NumOps = Ops.size();
5372 // If an identical node already exists, use it.
5374 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5375 FoldingSetNodeID ID;
5376 AddNodeIDNode(ID, Opc, VTs, Ops);
5377 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5378 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5381 if (!RemoveNodeFromCSEMaps(N))
5384 // Start the morphing.
5386 N->ValueList = VTs.VTs;
5387 N->NumValues = VTs.NumVTs;
5389 // Clear the operands list, updating used nodes to remove this from their
5390 // use list. Keep track of any operands that become dead as a result.
5391 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5392 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5394 SDNode *Used = Use.getNode();
5396 if (Used->use_empty())
5397 DeadNodeSet.insert(Used);
5400 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5401 // Initialize the memory references information.
5402 MN->setMemRefs(nullptr, nullptr);
5403 // If NumOps is larger than the # of operands we can have in a
5404 // MachineSDNode, reallocate the operand list.
5405 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5406 if (MN->OperandsNeedDelete)
5407 delete[] MN->OperandList;
5408 if (NumOps > array_lengthof(MN->LocalOperands))
5409 // We're creating a final node that will live unmorphed for the
5410 // remainder of the current SelectionDAG iteration, so we can allocate
5411 // the operands directly out of a pool with no recycling metadata.
5412 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5413 Ops.data(), NumOps);
5415 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5416 MN->OperandsNeedDelete = false;
5418 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5420 // If NumOps is larger than the # of operands we currently have, reallocate
5421 // the operand list.
5422 if (NumOps > N->NumOperands) {
5423 if (N->OperandsNeedDelete)
5424 delete[] N->OperandList;
5425 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5426 N->OperandsNeedDelete = true;
5428 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5431 // Delete any nodes that are still dead after adding the uses for the
5433 if (!DeadNodeSet.empty()) {
5434 SmallVector<SDNode *, 16> DeadNodes;
5435 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5436 E = DeadNodeSet.end(); I != E; ++I)
5437 if ((*I)->use_empty())
5438 DeadNodes.push_back(*I);
5439 RemoveDeadNodes(DeadNodes);
5443 CSEMap.InsertNode(N, IP); // Memoize the new node.
5448 /// getMachineNode - These are used for target selectors to create a new node
5449 /// with specified return type(s), MachineInstr opcode, and operands.
5451 /// Note that getMachineNode returns the resultant node. If there is already a
5452 /// node of the specified opcode and operands, it returns that node instead of
5453 /// the current one.
5455 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5456 SDVTList VTs = getVTList(VT);
5457 return getMachineNode(Opcode, dl, VTs, None);
5461 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5462 SDVTList VTs = getVTList(VT);
5463 SDValue Ops[] = { Op1 };
5464 return getMachineNode(Opcode, dl, VTs, Ops);
5468 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5469 SDValue Op1, SDValue Op2) {
5470 SDVTList VTs = getVTList(VT);
5471 SDValue Ops[] = { Op1, Op2 };
5472 return getMachineNode(Opcode, dl, VTs, Ops);
5476 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5477 SDValue Op1, SDValue Op2, SDValue Op3) {
5478 SDVTList VTs = getVTList(VT);
5479 SDValue Ops[] = { Op1, Op2, Op3 };
5480 return getMachineNode(Opcode, dl, VTs, Ops);
5484 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5485 ArrayRef<SDValue> Ops) {
5486 SDVTList VTs = getVTList(VT);
5487 return getMachineNode(Opcode, dl, VTs, Ops);
5491 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5492 SDVTList VTs = getVTList(VT1, VT2);
5493 return getMachineNode(Opcode, dl, VTs, None);
5497 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5498 EVT VT1, EVT VT2, SDValue Op1) {
5499 SDVTList VTs = getVTList(VT1, VT2);
5500 SDValue Ops[] = { Op1 };
5501 return getMachineNode(Opcode, dl, VTs, Ops);
5505 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5506 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5507 SDVTList VTs = getVTList(VT1, VT2);
5508 SDValue Ops[] = { Op1, Op2 };
5509 return getMachineNode(Opcode, dl, VTs, Ops);
5513 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5514 EVT VT1, EVT VT2, SDValue Op1,
5515 SDValue Op2, SDValue Op3) {
5516 SDVTList VTs = getVTList(VT1, VT2);
5517 SDValue Ops[] = { Op1, Op2, Op3 };
5518 return getMachineNode(Opcode, dl, VTs, Ops);
5522 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5524 ArrayRef<SDValue> Ops) {
5525 SDVTList VTs = getVTList(VT1, VT2);
5526 return getMachineNode(Opcode, dl, VTs, Ops);
5530 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5531 EVT VT1, EVT VT2, EVT VT3,
5532 SDValue Op1, SDValue Op2) {
5533 SDVTList VTs = getVTList(VT1, VT2, VT3);
5534 SDValue Ops[] = { Op1, Op2 };
5535 return getMachineNode(Opcode, dl, VTs, Ops);
5539 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5540 EVT VT1, EVT VT2, EVT VT3,
5541 SDValue Op1, SDValue Op2, SDValue Op3) {
5542 SDVTList VTs = getVTList(VT1, VT2, VT3);
5543 SDValue Ops[] = { Op1, Op2, Op3 };
5544 return getMachineNode(Opcode, dl, VTs, Ops);
5548 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5549 EVT VT1, EVT VT2, EVT VT3,
5550 ArrayRef<SDValue> Ops) {
5551 SDVTList VTs = getVTList(VT1, VT2, VT3);
5552 return getMachineNode(Opcode, dl, VTs, Ops);
5556 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5557 EVT VT2, EVT VT3, EVT VT4,
5558 ArrayRef<SDValue> Ops) {
5559 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5560 return getMachineNode(Opcode, dl, VTs, Ops);
5564 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5565 ArrayRef<EVT> ResultTys,
5566 ArrayRef<SDValue> Ops) {
5567 SDVTList VTs = getVTList(ResultTys);
5568 return getMachineNode(Opcode, dl, VTs, Ops);
5572 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5573 ArrayRef<SDValue> OpsArray) {
5574 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5577 const SDValue *Ops = OpsArray.data();
5578 unsigned NumOps = OpsArray.size();
5581 FoldingSetNodeID ID;
5582 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5584 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5585 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5589 // Allocate a new MachineSDNode.
5590 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5591 DL.getDebugLoc(), VTs);
5593 // Initialize the operands list.
5594 if (NumOps > array_lengthof(N->LocalOperands))
5595 // We're creating a final node that will live unmorphed for the
5596 // remainder of the current SelectionDAG iteration, so we can allocate
5597 // the operands directly out of a pool with no recycling metadata.
5598 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5601 N->InitOperands(N->LocalOperands, Ops, NumOps);
5602 N->OperandsNeedDelete = false;
5605 CSEMap.InsertNode(N, IP);
5607 AllNodes.push_back(N);
5609 VerifyMachineNode(N);
5614 /// getTargetExtractSubreg - A convenience function for creating
5615 /// TargetOpcode::EXTRACT_SUBREG nodes.
5617 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5619 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5620 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5621 VT, Operand, SRIdxVal);
5622 return SDValue(Subreg, 0);
5625 /// getTargetInsertSubreg - A convenience function for creating
5626 /// TargetOpcode::INSERT_SUBREG nodes.
5628 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5629 SDValue Operand, SDValue Subreg) {
5630 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5631 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5632 VT, Operand, Subreg, SRIdxVal);
5633 return SDValue(Result, 0);
5636 /// getNodeIfExists - Get the specified node if it's already available, or
5637 /// else return NULL.
5638 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5639 ArrayRef<SDValue> Ops) {
5640 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5641 FoldingSetNodeID ID;
5642 AddNodeIDNode(ID, Opcode, VTList, Ops);
5644 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5650 /// getDbgValue - Creates a SDDbgValue node.
5654 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5655 bool IsIndirect, uint64_t Off,
5656 DebugLoc DL, unsigned O) {
5657 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5662 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5664 DebugLoc DL, unsigned O) {
5665 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5670 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5671 DebugLoc DL, unsigned O) {
5672 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5677 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5678 /// pointed to by a use iterator is deleted, increment the use iterator
5679 /// so that it doesn't dangle.
5681 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5682 SDNode::use_iterator &UI;
5683 SDNode::use_iterator &UE;
5685 void NodeDeleted(SDNode *N, SDNode *E) override {
5686 // Increment the iterator as needed.
5687 while (UI != UE && N == *UI)
5692 RAUWUpdateListener(SelectionDAG &d,
5693 SDNode::use_iterator &ui,
5694 SDNode::use_iterator &ue)
5695 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5700 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5701 /// This can cause recursive merging of nodes in the DAG.
5703 /// This version assumes From has a single result value.
5705 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5706 SDNode *From = FromN.getNode();
5707 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5708 "Cannot replace with this method!");
5709 assert(From != To.getNode() && "Cannot replace uses of with self");
5711 // Iterate over all the existing uses of From. New uses will be added
5712 // to the beginning of the use list, which we avoid visiting.
5713 // This specifically avoids visiting uses of From that arise while the
5714 // replacement is happening, because any such uses would be the result
5715 // of CSE: If an existing node looks like From after one of its operands
5716 // is replaced by To, we don't want to replace of all its users with To
5717 // too. See PR3018 for more info.
5718 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5719 RAUWUpdateListener Listener(*this, UI, UE);
5723 // This node is about to morph, remove its old self from the CSE maps.
5724 RemoveNodeFromCSEMaps(User);
5726 // A user can appear in a use list multiple times, and when this
5727 // happens the uses are usually next to each other in the list.
5728 // To help reduce the number of CSE recomputations, process all
5729 // the uses of this user that we can find this way.
5731 SDUse &Use = UI.getUse();
5734 } while (UI != UE && *UI == User);
5736 // Now that we have modified User, add it back to the CSE maps. If it
5737 // already exists there, recursively merge the results together.
5738 AddModifiedNodeToCSEMaps(User);
5741 // If we just RAUW'd the root, take note.
5742 if (FromN == getRoot())
5746 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5747 /// This can cause recursive merging of nodes in the DAG.
5749 /// This version assumes that for each value of From, there is a
5750 /// corresponding value in To in the same position with the same type.
5752 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5754 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5755 assert((!From->hasAnyUseOfValue(i) ||
5756 From->getValueType(i) == To->getValueType(i)) &&
5757 "Cannot use this version of ReplaceAllUsesWith!");
5760 // Handle the trivial case.
5764 // Iterate over just the existing users of From. See the comments in
5765 // the ReplaceAllUsesWith above.
5766 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5767 RAUWUpdateListener Listener(*this, UI, UE);
5771 // This node is about to morph, remove its old self from the CSE maps.
5772 RemoveNodeFromCSEMaps(User);
5774 // A user can appear in a use list multiple times, and when this
5775 // happens the uses are usually next to each other in the list.
5776 // To help reduce the number of CSE recomputations, process all
5777 // the uses of this user that we can find this way.
5779 SDUse &Use = UI.getUse();
5782 } while (UI != UE && *UI == User);
5784 // Now that we have modified User, add it back to the CSE maps. If it
5785 // already exists there, recursively merge the results together.
5786 AddModifiedNodeToCSEMaps(User);
5789 // If we just RAUW'd the root, take note.
5790 if (From == getRoot().getNode())
5791 setRoot(SDValue(To, getRoot().getResNo()));
5794 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5795 /// This can cause recursive merging of nodes in the DAG.
5797 /// This version can replace From with any result values. To must match the
5798 /// number and types of values returned by From.
5799 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5800 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5801 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5803 // Iterate over just the existing users of From. See the comments in
5804 // the ReplaceAllUsesWith above.
5805 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5806 RAUWUpdateListener Listener(*this, UI, UE);
5810 // This node is about to morph, remove its old self from the CSE maps.
5811 RemoveNodeFromCSEMaps(User);
5813 // A user can appear in a use list multiple times, and when this
5814 // happens the uses are usually next to each other in the list.
5815 // To help reduce the number of CSE recomputations, process all
5816 // the uses of this user that we can find this way.
5818 SDUse &Use = UI.getUse();
5819 const SDValue &ToOp = To[Use.getResNo()];
5822 } while (UI != UE && *UI == User);
5824 // Now that we have modified User, add it back to the CSE maps. If it
5825 // already exists there, recursively merge the results together.
5826 AddModifiedNodeToCSEMaps(User);
5829 // If we just RAUW'd the root, take note.
5830 if (From == getRoot().getNode())
5831 setRoot(SDValue(To[getRoot().getResNo()]));
5834 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5835 /// uses of other values produced by From.getNode() alone. The Deleted
5836 /// vector is handled the same way as for ReplaceAllUsesWith.
5837 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5838 // Handle the really simple, really trivial case efficiently.
5839 if (From == To) return;
5841 // Handle the simple, trivial, case efficiently.
5842 if (From.getNode()->getNumValues() == 1) {
5843 ReplaceAllUsesWith(From, To);
5847 // Iterate over just the existing users of From. See the comments in
5848 // the ReplaceAllUsesWith above.
5849 SDNode::use_iterator UI = From.getNode()->use_begin(),
5850 UE = From.getNode()->use_end();
5851 RAUWUpdateListener Listener(*this, UI, UE);
5854 bool UserRemovedFromCSEMaps = false;
5856 // A user can appear in a use list multiple times, and when this
5857 // happens the uses are usually next to each other in the list.
5858 // To help reduce the number of CSE recomputations, process all
5859 // the uses of this user that we can find this way.
5861 SDUse &Use = UI.getUse();
5863 // Skip uses of different values from the same node.
5864 if (Use.getResNo() != From.getResNo()) {
5869 // If this node hasn't been modified yet, it's still in the CSE maps,
5870 // so remove its old self from the CSE maps.
5871 if (!UserRemovedFromCSEMaps) {
5872 RemoveNodeFromCSEMaps(User);
5873 UserRemovedFromCSEMaps = true;
5878 } while (UI != UE && *UI == User);
5880 // We are iterating over all uses of the From node, so if a use
5881 // doesn't use the specific value, no changes are made.
5882 if (!UserRemovedFromCSEMaps)
5885 // Now that we have modified User, add it back to the CSE maps. If it
5886 // already exists there, recursively merge the results together.
5887 AddModifiedNodeToCSEMaps(User);
5890 // If we just RAUW'd the root, take note.
5891 if (From == getRoot())
5896 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5897 /// to record information about a use.
5904 /// operator< - Sort Memos by User.
5905 bool operator<(const UseMemo &L, const UseMemo &R) {
5906 return (intptr_t)L.User < (intptr_t)R.User;
5910 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5911 /// uses of other values produced by From.getNode() alone. The same value
5912 /// may appear in both the From and To list. The Deleted vector is
5913 /// handled the same way as for ReplaceAllUsesWith.
5914 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5917 // Handle the simple, trivial case efficiently.
5919 return ReplaceAllUsesOfValueWith(*From, *To);
5921 // Read up all the uses and make records of them. This helps
5922 // processing new uses that are introduced during the
5923 // replacement process.
5924 SmallVector<UseMemo, 4> Uses;
5925 for (unsigned i = 0; i != Num; ++i) {
5926 unsigned FromResNo = From[i].getResNo();
5927 SDNode *FromNode = From[i].getNode();
5928 for (SDNode::use_iterator UI = FromNode->use_begin(),
5929 E = FromNode->use_end(); UI != E; ++UI) {
5930 SDUse &Use = UI.getUse();
5931 if (Use.getResNo() == FromResNo) {
5932 UseMemo Memo = { *UI, i, &Use };
5933 Uses.push_back(Memo);
5938 // Sort the uses, so that all the uses from a given User are together.
5939 std::sort(Uses.begin(), Uses.end());
5941 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5942 UseIndex != UseIndexEnd; ) {
5943 // We know that this user uses some value of From. If it is the right
5944 // value, update it.
5945 SDNode *User = Uses[UseIndex].User;
5947 // This node is about to morph, remove its old self from the CSE maps.
5948 RemoveNodeFromCSEMaps(User);
5950 // The Uses array is sorted, so all the uses for a given User
5951 // are next to each other in the list.
5952 // To help reduce the number of CSE recomputations, process all
5953 // the uses of this user that we can find this way.
5955 unsigned i = Uses[UseIndex].Index;
5956 SDUse &Use = *Uses[UseIndex].Use;
5960 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5962 // Now that we have modified User, add it back to the CSE maps. If it
5963 // already exists there, recursively merge the results together.
5964 AddModifiedNodeToCSEMaps(User);
5968 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5969 /// based on their topological order. It returns the maximum id and a vector
5970 /// of the SDNodes* in assigned order by reference.
5971 unsigned SelectionDAG::AssignTopologicalOrder() {
5973 unsigned DAGSize = 0;
5975 // SortedPos tracks the progress of the algorithm. Nodes before it are
5976 // sorted, nodes after it are unsorted. When the algorithm completes
5977 // it is at the end of the list.
5978 allnodes_iterator SortedPos = allnodes_begin();
5980 // Visit all the nodes. Move nodes with no operands to the front of
5981 // the list immediately. Annotate nodes that do have operands with their
5982 // operand count. Before we do this, the Node Id fields of the nodes
5983 // may contain arbitrary values. After, the Node Id fields for nodes
5984 // before SortedPos will contain the topological sort index, and the
5985 // Node Id fields for nodes At SortedPos and after will contain the
5986 // count of outstanding operands.
5987 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5990 unsigned Degree = N->getNumOperands();
5992 // A node with no uses, add it to the result array immediately.
5993 N->setNodeId(DAGSize++);
5994 allnodes_iterator Q = N;
5996 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5997 assert(SortedPos != AllNodes.end() && "Overran node list");
6000 // Temporarily use the Node Id as scratch space for the degree count.
6001 N->setNodeId(Degree);
6005 // Visit all the nodes. As we iterate, move nodes into sorted order,
6006 // such that by the time the end is reached all nodes will be sorted.
6007 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6010 // N is in sorted position, so all its uses have one less operand
6011 // that needs to be sorted.
6012 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6015 unsigned Degree = P->getNodeId();
6016 assert(Degree != 0 && "Invalid node degree");
6019 // All of P's operands are sorted, so P may sorted now.
6020 P->setNodeId(DAGSize++);
6022 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6023 assert(SortedPos != AllNodes.end() && "Overran node list");
6026 // Update P's outstanding operand count.
6027 P->setNodeId(Degree);
6030 if (I == SortedPos) {
6033 dbgs() << "Overran sorted position:\n";
6036 llvm_unreachable(nullptr);
6040 assert(SortedPos == AllNodes.end() &&
6041 "Topological sort incomplete!");
6042 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6043 "First node in topological sort is not the entry token!");
6044 assert(AllNodes.front().getNodeId() == 0 &&
6045 "First node in topological sort has non-zero id!");
6046 assert(AllNodes.front().getNumOperands() == 0 &&
6047 "First node in topological sort has operands!");
6048 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6049 "Last node in topologic sort has unexpected id!");
6050 assert(AllNodes.back().use_empty() &&
6051 "Last node in topologic sort has users!");
6052 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6056 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6057 /// value is produced by SD.
6058 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6059 DbgInfo->add(DB, SD, isParameter);
6061 SD->setHasDebugValue(true);
6064 /// TransferDbgValues - Transfer SDDbgValues.
6065 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6066 if (From == To || !From.getNode()->getHasDebugValue())
6068 SDNode *FromNode = From.getNode();
6069 SDNode *ToNode = To.getNode();
6070 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6071 SmallVector<SDDbgValue *, 2> ClonedDVs;
6072 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6074 SDDbgValue *Dbg = *I;
6075 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6076 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6078 Dbg->getOffset(), Dbg->getDebugLoc(),
6080 ClonedDVs.push_back(Clone);
6083 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6084 E = ClonedDVs.end(); I != E; ++I)
6085 AddDbgValue(*I, ToNode, false);
6088 //===----------------------------------------------------------------------===//
6090 //===----------------------------------------------------------------------===//
6092 HandleSDNode::~HandleSDNode() {
6096 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6097 DebugLoc DL, const GlobalValue *GA,
6098 EVT VT, int64_t o, unsigned char TF)
6099 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6103 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6104 SDValue X, unsigned SrcAS,
6106 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6107 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6109 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6110 EVT memvt, MachineMemOperand *mmo)
6111 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6112 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6113 MMO->isNonTemporal(), MMO->isInvariant());
6114 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6115 assert(isNonTemporal() == MMO->isNonTemporal() &&
6116 "Non-temporal encoding error!");
6117 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6120 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6121 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6122 : SDNode(Opc, Order, dl, VTs, Ops),
6123 MemoryVT(memvt), MMO(mmo) {
6124 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6125 MMO->isNonTemporal(), MMO->isInvariant());
6126 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6127 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6130 /// Profile - Gather unique data for the node.
6132 void SDNode::Profile(FoldingSetNodeID &ID) const {
6133 AddNodeIDNode(ID, this);
6138 std::vector<EVT> VTs;
6141 VTs.reserve(MVT::LAST_VALUETYPE);
6142 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6143 VTs.push_back(MVT((MVT::SimpleValueType)i));
6148 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6149 static ManagedStatic<EVTArray> SimpleVTArray;
6150 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6152 /// getValueTypeList - Return a pointer to the specified value type.
6154 const EVT *SDNode::getValueTypeList(EVT VT) {
6155 if (VT.isExtended()) {
6156 sys::SmartScopedLock<true> Lock(*VTMutex);
6157 return &(*EVTs->insert(VT).first);
6159 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6160 "Value type out of range!");
6161 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6165 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6166 /// indicated value. This method ignores uses of other values defined by this
6168 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6169 assert(Value < getNumValues() && "Bad value!");
6171 // TODO: Only iterate over uses of a given value of the node
6172 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6173 if (UI.getUse().getResNo() == Value) {
6180 // Found exactly the right number of uses?
6185 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6186 /// value. This method ignores uses of other values defined by this operation.
6187 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6188 assert(Value < getNumValues() && "Bad value!");
6190 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6191 if (UI.getUse().getResNo() == Value)
6198 /// isOnlyUserOf - Return true if this node is the only use of N.
6200 bool SDNode::isOnlyUserOf(SDNode *N) const {
6202 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6213 /// isOperand - Return true if this node is an operand of N.
6215 bool SDValue::isOperandOf(SDNode *N) const {
6216 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6217 if (*this == N->getOperand(i))
6222 bool SDNode::isOperandOf(SDNode *N) const {
6223 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6224 if (this == N->OperandList[i].getNode())
6229 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6230 /// be a chain) reaches the specified operand without crossing any
6231 /// side-effecting instructions on any chain path. In practice, this looks
6232 /// through token factors and non-volatile loads. In order to remain efficient,
6233 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6234 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6235 unsigned Depth) const {
6236 if (*this == Dest) return true;
6238 // Don't search too deeply, we just want to be able to see through
6239 // TokenFactor's etc.
6240 if (Depth == 0) return false;
6242 // If this is a token factor, all inputs to the TF happen in parallel. If any
6243 // of the operands of the TF does not reach dest, then we cannot do the xform.
6244 if (getOpcode() == ISD::TokenFactor) {
6245 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6246 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6251 // Loads don't have side effects, look through them.
6252 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6253 if (!Ld->isVolatile())
6254 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6259 /// hasPredecessor - Return true if N is a predecessor of this node.
6260 /// N is either an operand of this node, or can be reached by recursively
6261 /// traversing up the operands.
6262 /// NOTE: This is an expensive method. Use it carefully.
6263 bool SDNode::hasPredecessor(const SDNode *N) const {
6264 SmallPtrSet<const SDNode *, 32> Visited;
6265 SmallVector<const SDNode *, 16> Worklist;
6266 return hasPredecessorHelper(N, Visited, Worklist);
6270 SDNode::hasPredecessorHelper(const SDNode *N,
6271 SmallPtrSet<const SDNode *, 32> &Visited,
6272 SmallVectorImpl<const SDNode *> &Worklist) const {
6273 if (Visited.empty()) {
6274 Worklist.push_back(this);
6276 // Take a look in the visited set. If we've already encountered this node
6277 // we needn't search further.
6278 if (Visited.count(N))
6282 // Haven't visited N yet. Continue the search.
6283 while (!Worklist.empty()) {
6284 const SDNode *M = Worklist.pop_back_val();
6285 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6286 SDNode *Op = M->getOperand(i).getNode();
6287 if (Visited.insert(Op))
6288 Worklist.push_back(Op);
6297 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6298 assert(Num < NumOperands && "Invalid child # of SDNode!");
6299 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6302 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6303 assert(N->getNumValues() == 1 &&
6304 "Can't unroll a vector with multiple results!");
6306 EVT VT = N->getValueType(0);
6307 unsigned NE = VT.getVectorNumElements();
6308 EVT EltVT = VT.getVectorElementType();
6311 SmallVector<SDValue, 8> Scalars;
6312 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6314 // If ResNE is 0, fully unroll the vector op.
6317 else if (NE > ResNE)
6321 for (i= 0; i != NE; ++i) {
6322 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6323 SDValue Operand = N->getOperand(j);
6324 EVT OperandVT = Operand.getValueType();
6325 if (OperandVT.isVector()) {
6326 // A vector operand; extract a single element.
6327 const TargetLowering *TLI = TM.getTargetLowering();
6328 EVT OperandEltVT = OperandVT.getVectorElementType();
6329 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6332 getConstant(i, TLI->getVectorIdxTy()));
6334 // A scalar operand; just use it as is.
6335 Operands[j] = Operand;
6339 switch (N->getOpcode()) {
6341 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6344 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6351 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6352 getShiftAmountOperand(Operands[0].getValueType(),
6355 case ISD::SIGN_EXTEND_INREG:
6356 case ISD::FP_ROUND_INREG: {
6357 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6358 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6360 getValueType(ExtVT)));
6365 for (; i < ResNE; ++i)
6366 Scalars.push_back(getUNDEF(EltVT));
6368 return getNode(ISD::BUILD_VECTOR, dl,
6369 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6373 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6374 /// location that is 'Dist' units away from the location that the 'Base' load
6375 /// is loading from.
6376 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6377 unsigned Bytes, int Dist) const {
6378 if (LD->getChain() != Base->getChain())
6380 EVT VT = LD->getValueType(0);
6381 if (VT.getSizeInBits() / 8 != Bytes)
6384 SDValue Loc = LD->getOperand(1);
6385 SDValue BaseLoc = Base->getOperand(1);
6386 if (Loc.getOpcode() == ISD::FrameIndex) {
6387 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6389 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6390 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6391 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6392 int FS = MFI->getObjectSize(FI);
6393 int BFS = MFI->getObjectSize(BFI);
6394 if (FS != BFS || FS != (int)Bytes) return false;
6395 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6399 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6400 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6403 const GlobalValue *GV1 = nullptr;
6404 const GlobalValue *GV2 = nullptr;
6405 int64_t Offset1 = 0;
6406 int64_t Offset2 = 0;
6407 const TargetLowering *TLI = TM.getTargetLowering();
6408 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6409 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6410 if (isGA1 && isGA2 && GV1 == GV2)
6411 return Offset1 == (Offset2 + Dist*Bytes);
6416 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6417 /// it cannot be inferred.
6418 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6419 // If this is a GlobalAddress + cst, return the alignment.
6420 const GlobalValue *GV;
6421 int64_t GVOffset = 0;
6422 const TargetLowering *TLI = TM.getTargetLowering();
6423 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6424 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6425 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6426 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6427 TLI->getDataLayout());
6428 unsigned AlignBits = KnownZero.countTrailingOnes();
6429 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6431 return MinAlign(Align, GVOffset);
6434 // If this is a direct reference to a stack slot, use information about the
6435 // stack slot's alignment.
6436 int FrameIdx = 1 << 31;
6437 int64_t FrameOffset = 0;
6438 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6439 FrameIdx = FI->getIndex();
6440 } else if (isBaseWithConstantOffset(Ptr) &&
6441 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6443 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6444 FrameOffset = Ptr.getConstantOperandVal(1);
6447 if (FrameIdx != (1 << 31)) {
6448 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6449 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6457 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6458 /// which is split (or expanded) into two not necessarily identical pieces.
6459 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6460 // Currently all types are split in half.
6462 if (!VT.isVector()) {
6463 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6465 unsigned NumElements = VT.getVectorNumElements();
6466 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6467 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6470 return std::make_pair(LoVT, HiVT);
6473 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6475 std::pair<SDValue, SDValue>
6476 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6478 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6479 N.getValueType().getVectorNumElements() &&
6480 "More vector elements requested than available!");
6482 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6483 getConstant(0, TLI->getVectorIdxTy()));
6484 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6485 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6486 return std::make_pair(Lo, Hi);
6489 void SelectionDAG::ExtractVectorElements(SDValue Op,
6490 SmallVectorImpl<SDValue> &Args,
6491 unsigned Start, unsigned Count) {
6492 EVT VT = Op.getValueType();
6494 Count = VT.getVectorNumElements();
6496 EVT EltVT = VT.getVectorElementType();
6497 EVT IdxTy = TLI->getVectorIdxTy();
6499 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6500 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6501 Op, getConstant(i, IdxTy)));
6505 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6506 unsigned GlobalAddressSDNode::getAddressSpace() const {
6507 return getGlobal()->getType()->getAddressSpace();
6511 Type *ConstantPoolSDNode::getType() const {
6512 if (isMachineConstantPoolEntry())
6513 return Val.MachineCPVal->getType();
6514 return Val.ConstVal->getType();
6517 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6519 unsigned &SplatBitSize,
6521 unsigned MinSplatBits,
6522 bool isBigEndian) const {
6523 EVT VT = getValueType(0);
6524 assert(VT.isVector() && "Expected a vector type");
6525 unsigned sz = VT.getSizeInBits();
6526 if (MinSplatBits > sz)
6529 SplatValue = APInt(sz, 0);
6530 SplatUndef = APInt(sz, 0);
6532 // Get the bits. Bits with undefined values (when the corresponding element
6533 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6534 // in SplatValue. If any of the values are not constant, give up and return
6536 unsigned int nOps = getNumOperands();
6537 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6538 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6540 for (unsigned j = 0; j < nOps; ++j) {
6541 unsigned i = isBigEndian ? nOps-1-j : j;
6542 SDValue OpVal = getOperand(i);
6543 unsigned BitPos = j * EltBitSize;
6545 if (OpVal.getOpcode() == ISD::UNDEF)
6546 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6547 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6548 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6549 zextOrTrunc(sz) << BitPos;
6550 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6551 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6556 // The build_vector is all constants or undefs. Find the smallest element
6557 // size that splats the vector.
6559 HasAnyUndefs = (SplatUndef != 0);
6562 unsigned HalfSize = sz / 2;
6563 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6564 APInt LowValue = SplatValue.trunc(HalfSize);
6565 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6566 APInt LowUndef = SplatUndef.trunc(HalfSize);
6568 // If the two halves do not match (ignoring undef bits), stop here.
6569 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6570 MinSplatBits > HalfSize)
6573 SplatValue = HighValue | LowValue;
6574 SplatUndef = HighUndef & LowUndef;
6583 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6584 SDValue Op0 = getOperand(0);
6585 if (Op0.getOpcode() != ISD::Constant)
6588 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6589 if (getOperand(i) != Op0)
6592 return cast<ConstantSDNode>(Op0);
6595 bool BuildVectorSDNode::isConstant() const {
6596 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6597 unsigned Opc = getOperand(i).getOpcode();
6598 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6604 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6605 // Find the first non-undef value in the shuffle mask.
6607 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6610 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6612 // Make sure all remaining elements are either undef or the same as the first
6614 for (int Idx = Mask[i]; i != e; ++i)
6615 if (Mask[i] >= 0 && Mask[i] != Idx)
6621 static void checkForCyclesHelper(const SDNode *N,
6622 SmallPtrSet<const SDNode*, 32> &Visited,
6623 SmallPtrSet<const SDNode*, 32> &Checked) {
6624 // If this node has already been checked, don't check it again.
6625 if (Checked.count(N))
6628 // If a node has already been visited on this depth-first walk, reject it as
6630 if (!Visited.insert(N)) {
6631 dbgs() << "Offending node:\n";
6633 errs() << "Detected cycle in SelectionDAG\n";
6637 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6638 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6645 void llvm::checkForCycles(const llvm::SDNode *N) {
6647 assert(N && "Checking nonexistent SDNode");
6648 SmallPtrSet<const SDNode*, 32> visited;
6649 SmallPtrSet<const SDNode*, 32> checked;
6650 checkForCyclesHelper(N, visited, checked);
6654 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6655 checkForCycles(DAG->getRoot().getNode());