1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
53 /// makeVTList - Return an instance of the SDVTList struct initialized with the
54 /// specified members.
55 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
56 SDVTList Res = {VTs, NumVTs};
60 // Default null implementations of the callbacks.
61 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
62 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
64 //===----------------------------------------------------------------------===//
65 // ConstantFPSDNode Class
66 //===----------------------------------------------------------------------===//
68 /// isExactlyValue - We don't rely on operator== working on double values, as
69 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
70 /// As such, this method can be used to do an exact bit-for-bit comparison of
71 /// two floating point values.
72 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
73 return getValueAPF().bitwiseIsEqual(V);
76 bool ConstantFPSDNode::isValueValidForType(EVT VT,
78 assert(VT.isFloatingPoint() && "Can only convert between FP types");
80 // convert modifies in place, so make a copy.
81 APFloat Val2 = APFloat(Val);
83 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
84 APFloat::rmNearestTiesToEven,
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 /// isBuildVectorAllOnes - Return true if the specified node is a
94 /// BUILD_VECTOR where all of the elements are ~0 or undef.
95 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96 // Look through a bit convert.
97 if (N->getOpcode() == ISD::BITCAST)
98 N = N->getOperand(0).getNode();
100 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
102 unsigned i = 0, e = N->getNumOperands();
104 // Skip over all of the undef values.
105 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 // Do not accept an all-undef vector.
109 if (i == e) return false;
111 // Do not accept build_vectors that aren't all constants or which have non-~0
112 // elements. We have to be a bit careful here, as the type of the constant
113 // may not be the same as the type of the vector elements due to type
114 // legalization (the elements are promoted to a legal type for the target and
115 // a vector of a type may be legal when the base element type is not).
116 // We only want to check enough bits to cover the vector elements, because
117 // we care if the resultant vector is all ones, not whether the individual
119 SDValue NotZero = N->getOperand(i);
120 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
121 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
122 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
124 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
125 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
130 // Okay, we have at least one ~0 value, check to see if the rest match or are
131 // undefs. Even with the above element type twiddling, this should be OK, as
132 // the same type legalization should have applied to all the elements.
133 for (++i; i != e; ++i)
134 if (N->getOperand(i) != NotZero &&
135 N->getOperand(i).getOpcode() != ISD::UNDEF)
141 /// isBuildVectorAllZeros - Return true if the specified node is a
142 /// BUILD_VECTOR where all of the elements are 0 or undef.
143 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
144 // Look through a bit convert.
145 if (N->getOpcode() == ISD::BITCAST)
146 N = N->getOperand(0).getNode();
148 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
150 unsigned i = 0, e = N->getNumOperands();
152 // Skip over all of the undef values.
153 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept an all-undef vector.
157 if (i == e) return false;
159 // Do not accept build_vectors that aren't all constants or which have non-0
161 SDValue Zero = N->getOperand(i);
162 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
163 if (!CN->isNullValue())
165 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
166 if (!CFPN->getValueAPF().isPosZero())
171 // Okay, we have at least one 0 value, check to see if the rest match or are
173 for (++i; i != e; ++i)
174 if (N->getOperand(i) != Zero &&
175 N->getOperand(i).getOpcode() != ISD::UNDEF)
180 /// \brief Return true if the specified node is a BUILD_VECTOR node of
181 /// all ConstantSDNode or undef.
182 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
183 if (N->getOpcode() != ISD::BUILD_VECTOR)
186 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
187 SDValue Op = N->getOperand(i);
188 if (Op.getOpcode() == ISD::UNDEF)
190 if (!isa<ConstantSDNode>(Op))
196 /// isScalarToVector - Return true if the specified node is a
197 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
198 /// element is not an undef.
199 bool ISD::isScalarToVector(const SDNode *N) {
200 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
207 unsigned NumElems = N->getNumOperands();
210 for (unsigned i = 1; i < NumElems; ++i) {
211 SDValue V = N->getOperand(i);
212 if (V.getOpcode() != ISD::UNDEF)
218 /// allOperandsUndef - Return true if the node has at least one operand
219 /// and all operands of the specified node are ISD::UNDEF.
220 bool ISD::allOperandsUndef(const SDNode *N) {
221 // Return false if the node has no operands.
222 // This is "logically inconsistent" with the definition of "all" but
223 // is probably the desired behavior.
224 if (N->getNumOperands() == 0)
227 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
228 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
234 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
237 return ISD::ANY_EXTEND;
239 return ISD::SIGN_EXTEND;
241 return ISD::ZERO_EXTEND;
246 llvm_unreachable("Invalid LoadExtType");
249 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
250 /// when given the operation for (X op Y).
251 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
252 // To perform this operation, we just need to swap the L and G bits of the
254 unsigned OldL = (Operation >> 2) & 1;
255 unsigned OldG = (Operation >> 1) & 1;
256 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
257 (OldL << 1) | // New G bit
258 (OldG << 2)); // New L bit.
261 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
262 /// 'op' is a valid SetCC operation.
263 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
264 unsigned Operation = Op;
266 Operation ^= 7; // Flip L, G, E bits, but not U.
268 Operation ^= 15; // Flip all of the condition bits.
270 if (Operation > ISD::SETTRUE2)
271 Operation &= ~8; // Don't let N and U bits get set.
273 return ISD::CondCode(Operation);
277 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
278 /// signed operation and 2 if the result is an unsigned comparison. Return zero
279 /// if the operation does not depend on the sign of the input (setne and seteq).
280 static int isSignedOp(ISD::CondCode Opcode) {
282 default: llvm_unreachable("Illegal integer setcc operation!");
284 case ISD::SETNE: return 0;
288 case ISD::SETGE: return 1;
292 case ISD::SETUGE: return 2;
296 /// getSetCCOrOperation - Return the result of a logical OR between different
297 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
298 /// returns SETCC_INVALID if it is not possible to represent the resultant
300 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
302 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
303 // Cannot fold a signed integer setcc with an unsigned integer setcc.
304 return ISD::SETCC_INVALID;
306 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
308 // If the N and U bits get set then the resultant comparison DOES suddenly
309 // care about orderedness, and is true when ordered.
310 if (Op > ISD::SETTRUE2)
311 Op &= ~16; // Clear the U bit if the N bit is set.
313 // Canonicalize illegal integer setcc's.
314 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
317 return ISD::CondCode(Op);
320 /// getSetCCAndOperation - Return the result of a logical AND between different
321 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
322 /// function returns zero if it is not possible to represent the resultant
324 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
326 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
327 // Cannot fold a signed setcc with an unsigned setcc.
328 return ISD::SETCC_INVALID;
330 // Combine all of the condition bits.
331 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
333 // Canonicalize illegal integer setcc's.
337 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
338 case ISD::SETOEQ: // SETEQ & SETU[LG]E
339 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
340 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
341 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
348 //===----------------------------------------------------------------------===//
349 // SDNode Profile Support
350 //===----------------------------------------------------------------------===//
352 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
354 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
359 /// solely with their pointer.
360 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
361 ID.AddPointer(VTList.VTs);
364 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
366 static void AddNodeIDOperands(FoldingSetNodeID &ID,
367 ArrayRef<SDValue> Ops) {
368 for (auto& Op : Ops) {
369 ID.AddPointer(Op.getNode());
370 ID.AddInteger(Op.getResNo());
374 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
376 static void AddNodeIDOperands(FoldingSetNodeID &ID,
377 ArrayRef<SDUse> Ops) {
378 for (auto& Op : Ops) {
379 ID.AddPointer(Op.getNode());
380 ID.AddInteger(Op.getResNo());
384 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
385 SDVTList VTList, ArrayRef<SDValue> OpList) {
386 AddNodeIDOpcode(ID, OpC);
387 AddNodeIDValueTypes(ID, VTList);
388 AddNodeIDOperands(ID, OpList);
391 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
393 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
394 switch (N->getOpcode()) {
395 case ISD::TargetExternalSymbol:
396 case ISD::ExternalSymbol:
397 llvm_unreachable("Should only be used on nodes with operands");
398 default: break; // Normal nodes don't need extra info.
399 case ISD::TargetConstant:
400 case ISD::Constant: {
401 const ConstantSDNode *C = cast<ConstantSDNode>(N);
402 ID.AddPointer(C->getConstantIntValue());
403 ID.AddBoolean(C->isOpaque());
406 case ISD::TargetConstantFP:
407 case ISD::ConstantFP: {
408 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
411 case ISD::TargetGlobalAddress:
412 case ISD::GlobalAddress:
413 case ISD::TargetGlobalTLSAddress:
414 case ISD::GlobalTLSAddress: {
415 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
416 ID.AddPointer(GA->getGlobal());
417 ID.AddInteger(GA->getOffset());
418 ID.AddInteger(GA->getTargetFlags());
419 ID.AddInteger(GA->getAddressSpace());
422 case ISD::BasicBlock:
423 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
426 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
428 case ISD::RegisterMask:
429 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
432 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
434 case ISD::FrameIndex:
435 case ISD::TargetFrameIndex:
436 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
439 case ISD::TargetJumpTable:
440 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
441 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
443 case ISD::ConstantPool:
444 case ISD::TargetConstantPool: {
445 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
446 ID.AddInteger(CP->getAlignment());
447 ID.AddInteger(CP->getOffset());
448 if (CP->isMachineConstantPoolEntry())
449 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
451 ID.AddPointer(CP->getConstVal());
452 ID.AddInteger(CP->getTargetFlags());
455 case ISD::TargetIndex: {
456 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
457 ID.AddInteger(TI->getIndex());
458 ID.AddInteger(TI->getOffset());
459 ID.AddInteger(TI->getTargetFlags());
463 const LoadSDNode *LD = cast<LoadSDNode>(N);
464 ID.AddInteger(LD->getMemoryVT().getRawBits());
465 ID.AddInteger(LD->getRawSubclassData());
466 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
470 const StoreSDNode *ST = cast<StoreSDNode>(N);
471 ID.AddInteger(ST->getMemoryVT().getRawBits());
472 ID.AddInteger(ST->getRawSubclassData());
473 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
476 case ISD::ATOMIC_CMP_SWAP:
477 case ISD::ATOMIC_SWAP:
478 case ISD::ATOMIC_LOAD_ADD:
479 case ISD::ATOMIC_LOAD_SUB:
480 case ISD::ATOMIC_LOAD_AND:
481 case ISD::ATOMIC_LOAD_OR:
482 case ISD::ATOMIC_LOAD_XOR:
483 case ISD::ATOMIC_LOAD_NAND:
484 case ISD::ATOMIC_LOAD_MIN:
485 case ISD::ATOMIC_LOAD_MAX:
486 case ISD::ATOMIC_LOAD_UMIN:
487 case ISD::ATOMIC_LOAD_UMAX:
488 case ISD::ATOMIC_LOAD:
489 case ISD::ATOMIC_STORE: {
490 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
491 ID.AddInteger(AT->getMemoryVT().getRawBits());
492 ID.AddInteger(AT->getRawSubclassData());
493 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
496 case ISD::PREFETCH: {
497 const MemSDNode *PF = cast<MemSDNode>(N);
498 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
501 case ISD::VECTOR_SHUFFLE: {
502 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
503 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
505 ID.AddInteger(SVN->getMaskElt(i));
508 case ISD::TargetBlockAddress:
509 case ISD::BlockAddress: {
510 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
511 ID.AddPointer(BA->getBlockAddress());
512 ID.AddInteger(BA->getOffset());
513 ID.AddInteger(BA->getTargetFlags());
516 } // end switch (N->getOpcode())
518 // Target specific memory nodes could also have address spaces to check.
519 if (N->isTargetMemoryOpcode())
520 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
523 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
525 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
526 AddNodeIDOpcode(ID, N->getOpcode());
527 // Add the return value info.
528 AddNodeIDValueTypes(ID, N->getVTList());
529 // Add the operand info.
530 AddNodeIDOperands(ID, makeArrayRef(N->op_begin(), N->op_end()));
532 // Handle SDNode leafs with special info.
533 AddNodeIDCustom(ID, N);
536 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
537 /// the CSE map that carries volatility, temporalness, indexing mode, and
538 /// extension/truncation information.
540 static inline unsigned
541 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
542 bool isNonTemporal, bool isInvariant) {
543 assert((ConvType & 3) == ConvType &&
544 "ConvType may not require more than 2 bits!");
545 assert((AM & 7) == AM &&
546 "AM may not require more than 3 bits!");
550 (isNonTemporal << 6) |
554 //===----------------------------------------------------------------------===//
555 // SelectionDAG Class
556 //===----------------------------------------------------------------------===//
558 /// doNotCSE - Return true if CSE should not be performed for this node.
559 static bool doNotCSE(SDNode *N) {
560 if (N->getValueType(0) == MVT::Glue)
561 return true; // Never CSE anything that produces a flag.
563 switch (N->getOpcode()) {
565 case ISD::HANDLENODE:
567 return true; // Never CSE these nodes.
570 // Check that remaining values produced are not flags.
571 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
572 if (N->getValueType(i) == MVT::Glue)
573 return true; // Never CSE anything that produces a flag.
578 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
580 void SelectionDAG::RemoveDeadNodes() {
581 // Create a dummy node (which is not added to allnodes), that adds a reference
582 // to the root node, preventing it from being deleted.
583 HandleSDNode Dummy(getRoot());
585 SmallVector<SDNode*, 128> DeadNodes;
587 // Add all obviously-dead nodes to the DeadNodes worklist.
588 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
590 DeadNodes.push_back(I);
592 RemoveDeadNodes(DeadNodes);
594 // If the root changed (e.g. it was a dead load, update the root).
595 setRoot(Dummy.getValue());
598 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
599 /// given list, and any nodes that become unreachable as a result.
600 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
602 // Process the worklist, deleting the nodes and adding their uses to the
604 while (!DeadNodes.empty()) {
605 SDNode *N = DeadNodes.pop_back_val();
607 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
608 DUL->NodeDeleted(N, nullptr);
610 // Take the node out of the appropriate CSE map.
611 RemoveNodeFromCSEMaps(N);
613 // Next, brutally remove the operand list. This is safe to do, as there are
614 // no cycles in the graph.
615 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
617 SDNode *Operand = Use.getNode();
620 // Now that we removed this operand, see if there are no uses of it left.
621 if (Operand->use_empty())
622 DeadNodes.push_back(Operand);
629 void SelectionDAG::RemoveDeadNode(SDNode *N){
630 SmallVector<SDNode*, 16> DeadNodes(1, N);
632 // Create a dummy node that adds a reference to the root node, preventing
633 // it from being deleted. (This matters if the root is an operand of the
635 HandleSDNode Dummy(getRoot());
637 RemoveDeadNodes(DeadNodes);
640 void SelectionDAG::DeleteNode(SDNode *N) {
641 // First take this out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Finally, remove uses due to operands of this node, remove from the
645 // AllNodes list, and delete the node.
646 DeleteNodeNotInCSEMaps(N);
649 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
650 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
651 assert(N->use_empty() && "Cannot delete a node that is not dead!");
653 // Drop all of the operands and decrement used node's use counts.
659 void SelectionDAG::DeallocateNode(SDNode *N) {
660 if (N->OperandsNeedDelete)
661 delete[] N->OperandList;
663 // Set the opcode to DELETED_NODE to help catch bugs when node
664 // memory is reallocated.
665 N->NodeType = ISD::DELETED_NODE;
667 NodeAllocator.Deallocate(AllNodes.remove(N));
669 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
670 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
671 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
672 DbgVals[i]->setIsInvalidated();
675 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
676 /// correspond to it. This is useful when we're about to delete or repurpose
677 /// the node. We don't want future request for structurally identical nodes
678 /// to return N anymore.
679 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
681 switch (N->getOpcode()) {
682 case ISD::HANDLENODE: return false; // noop.
684 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
685 "Cond code doesn't exist!");
686 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
687 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
689 case ISD::ExternalSymbol:
690 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
692 case ISD::TargetExternalSymbol: {
693 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
694 Erased = TargetExternalSymbols.erase(
695 std::pair<std::string,unsigned char>(ESN->getSymbol(),
696 ESN->getTargetFlags()));
699 case ISD::VALUETYPE: {
700 EVT VT = cast<VTSDNode>(N)->getVT();
701 if (VT.isExtended()) {
702 Erased = ExtendedValueTypeNodes.erase(VT);
704 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
705 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
710 // Remove it from the CSE Map.
711 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
712 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
713 Erased = CSEMap.RemoveNode(N);
717 // Verify that the node was actually in one of the CSE maps, unless it has a
718 // flag result (which cannot be CSE'd) or is one of the special cases that are
719 // not subject to CSE.
720 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
721 !N->isMachineOpcode() && !doNotCSE(N)) {
724 llvm_unreachable("Node is not in map!");
730 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
731 /// maps and modified in place. Add it back to the CSE maps, unless an identical
732 /// node already exists, in which case transfer all its users to the existing
733 /// node. This transfer can potentially trigger recursive merging.
736 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
737 // For node types that aren't CSE'd, just act as if no identical node
740 SDNode *Existing = CSEMap.GetOrInsertNode(N);
742 // If there was already an existing matching node, use ReplaceAllUsesWith
743 // to replace the dead one with the existing one. This can cause
744 // recursive merging of other unrelated nodes down the line.
745 ReplaceAllUsesWith(N, Existing);
747 // N is now dead. Inform the listeners and delete it.
748 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
749 DUL->NodeDeleted(N, Existing);
750 DeleteNodeNotInCSEMaps(N);
755 // If the node doesn't already exist, we updated it. Inform listeners.
756 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
760 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
761 /// were replaced with those specified. If this node is never memoized,
762 /// return null, otherwise return a pointer to the slot it would take. If a
763 /// node already exists with these operands, the slot will be non-null.
764 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
769 SDValue Ops[] = { Op };
771 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
772 AddNodeIDCustom(ID, N);
773 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
777 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
778 /// were replaced with those specified. If this node is never memoized,
779 /// return null, otherwise return a pointer to the slot it would take. If a
780 /// node already exists with these operands, the slot will be non-null.
781 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
782 SDValue Op1, SDValue Op2,
787 SDValue Ops[] = { Op1, Op2 };
789 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
790 AddNodeIDCustom(ID, N);
791 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
796 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
797 /// were replaced with those specified. If this node is never memoized,
798 /// return null, otherwise return a pointer to the slot it would take. If a
799 /// node already exists with these operands, the slot will be non-null.
800 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
806 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
807 AddNodeIDCustom(ID, N);
808 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
813 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
814 static void VerifyNodeCommon(SDNode *N) {
815 switch (N->getOpcode()) {
818 case ISD::BUILD_PAIR: {
819 EVT VT = N->getValueType(0);
820 assert(N->getNumValues() == 1 && "Too many results!");
821 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
822 "Wrong return type!");
823 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
824 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
825 "Mismatched operand types!");
826 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
827 "Wrong operand type!");
828 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
829 "Wrong return type size");
832 case ISD::BUILD_VECTOR: {
833 assert(N->getNumValues() == 1 && "Too many results!");
834 assert(N->getValueType(0).isVector() && "Wrong return type!");
835 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
836 "Wrong number of operands!");
837 EVT EltVT = N->getValueType(0).getVectorElementType();
838 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
839 assert((I->getValueType() == EltVT ||
840 (EltVT.isInteger() && I->getValueType().isInteger() &&
841 EltVT.bitsLE(I->getValueType()))) &&
842 "Wrong operand type!");
843 assert(I->getValueType() == N->getOperand(0).getValueType() &&
844 "Operands must all have the same type");
851 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
852 static void VerifySDNode(SDNode *N) {
853 // The SDNode allocators cannot be used to allocate nodes with fields that are
854 // not present in an SDNode!
855 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
856 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
857 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
858 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
859 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
860 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
861 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
862 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
863 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
864 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
865 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
866 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
867 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
868 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
869 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
870 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
871 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
872 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
873 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
878 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
880 static void VerifyMachineNode(SDNode *N) {
881 // The MachineNode allocators cannot be used to allocate nodes with fields
882 // that are not present in a MachineNode!
883 // Currently there are no such nodes.
889 /// getEVTAlignment - Compute the default alignment value for the
892 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
893 Type *Ty = VT == MVT::iPTR ?
894 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
895 VT.getTypeForEVT(*getContext());
897 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
900 // EntryNode could meaningfully have debug info if we can find it...
901 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
902 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
903 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
904 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
905 UpdateListeners(nullptr) {
906 AllNodes.push_back(&EntryNode);
907 DbgInfo = new SDDbgInfo();
910 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
913 Context = &mf.getFunction()->getContext();
916 SelectionDAG::~SelectionDAG() {
917 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
922 void SelectionDAG::allnodes_clear() {
923 assert(&*AllNodes.begin() == &EntryNode);
924 AllNodes.remove(AllNodes.begin());
925 while (!AllNodes.empty())
926 DeallocateNode(AllNodes.begin());
929 void SelectionDAG::clear() {
931 OperandAllocator.Reset();
934 ExtendedValueTypeNodes.clear();
935 ExternalSymbols.clear();
936 TargetExternalSymbols.clear();
937 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
938 static_cast<CondCodeSDNode*>(nullptr));
939 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
940 static_cast<SDNode*>(nullptr));
942 EntryNode.UseList = nullptr;
943 AllNodes.push_back(&EntryNode);
944 Root = getEntryNode();
948 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
949 return VT.bitsGT(Op.getValueType()) ?
950 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
951 getNode(ISD::TRUNCATE, DL, VT, Op);
954 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
955 return VT.bitsGT(Op.getValueType()) ?
956 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
957 getNode(ISD::TRUNCATE, DL, VT, Op);
960 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
961 return VT.bitsGT(Op.getValueType()) ?
962 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
963 getNode(ISD::TRUNCATE, DL, VT, Op);
966 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
967 assert(!VT.isVector() &&
968 "getZeroExtendInReg should use the vector element type instead of "
970 if (Op.getValueType() == VT) return Op;
971 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
972 APInt Imm = APInt::getLowBitsSet(BitWidth,
974 return getNode(ISD::AND, DL, Op.getValueType(), Op,
975 getConstant(Imm, Op.getValueType()));
978 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
980 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
981 EVT EltVT = VT.getScalarType();
983 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
984 return getNode(ISD::XOR, DL, VT, Val, NegOne);
987 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
988 EVT EltVT = VT.getScalarType();
989 assert((EltVT.getSizeInBits() >= 64 ||
990 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
991 "getConstant with a uint64_t value that doesn't fit in the type!");
992 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
995 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
997 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1000 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1002 assert(VT.isInteger() && "Cannot create FP integer constant!");
1004 EVT EltVT = VT.getScalarType();
1005 const ConstantInt *Elt = &Val;
1007 const TargetLowering *TLI = TM.getTargetLowering();
1009 // In some cases the vector type is legal but the element type is illegal and
1010 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1011 // inserted value (the type does not need to match the vector element type).
1012 // Any extra bits introduced will be truncated away.
1013 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1014 TargetLowering::TypePromoteInteger) {
1015 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1016 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1017 Elt = ConstantInt::get(*getContext(), NewVal);
1019 // In other cases the element type is illegal and needs to be expanded, for
1020 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1021 // the value into n parts and use a vector type with n-times the elements.
1022 // Then bitcast to the type requested.
1023 // Legalizing constants too early makes the DAGCombiner's job harder so we
1024 // only legalize if the DAG tells us we must produce legal types.
1025 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1026 TLI->getTypeAction(*getContext(), EltVT) ==
1027 TargetLowering::TypeExpandInteger) {
1028 APInt NewVal = Elt->getValue();
1029 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1030 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1031 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1032 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1034 // Check the temporary vector is the correct size. If this fails then
1035 // getTypeToTransformTo() probably returned a type whose size (in bits)
1036 // isn't a power-of-2 factor of the requested type size.
1037 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1039 SmallVector<SDValue, 2> EltParts;
1040 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1041 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1042 .trunc(ViaEltSizeInBits),
1043 ViaEltVT, isT, isO));
1046 // EltParts is currently in little endian order. If we actually want
1047 // big-endian order then reverse it now.
1048 if (TLI->isBigEndian())
1049 std::reverse(EltParts.begin(), EltParts.end());
1051 // The elements must be reversed when the element order is different
1052 // to the endianness of the elements (because the BITCAST is itself a
1053 // vector shuffle in this situation). However, we do not need any code to
1054 // perform this reversal because getConstant() is producing a vector
1056 // This situation occurs in MIPS MSA.
1058 SmallVector<SDValue, 8> Ops;
1059 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1060 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1062 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1063 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1068 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1069 "APInt size does not match type size!");
1070 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1071 FoldingSetNodeID ID;
1072 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1076 SDNode *N = nullptr;
1077 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1079 return SDValue(N, 0);
1082 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1083 CSEMap.InsertNode(N, IP);
1084 AllNodes.push_back(N);
1087 SDValue Result(N, 0);
1088 if (VT.isVector()) {
1089 SmallVector<SDValue, 8> Ops;
1090 Ops.assign(VT.getVectorNumElements(), Result);
1091 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1096 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1097 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1101 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1102 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1105 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1106 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1108 EVT EltVT = VT.getScalarType();
1110 // Do the map lookup using the actual bit pattern for the floating point
1111 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1112 // we don't have issues with SNANs.
1113 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1114 FoldingSetNodeID ID;
1115 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1118 SDNode *N = nullptr;
1119 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1121 return SDValue(N, 0);
1124 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1125 CSEMap.InsertNode(N, IP);
1126 AllNodes.push_back(N);
1129 SDValue Result(N, 0);
1130 if (VT.isVector()) {
1131 SmallVector<SDValue, 8> Ops;
1132 Ops.assign(VT.getVectorNumElements(), Result);
1133 // FIXME SDLoc info might be appropriate here
1134 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1139 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1140 EVT EltVT = VT.getScalarType();
1141 if (EltVT==MVT::f32)
1142 return getConstantFP(APFloat((float)Val), VT, isTarget);
1143 else if (EltVT==MVT::f64)
1144 return getConstantFP(APFloat(Val), VT, isTarget);
1145 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1148 APFloat apf = APFloat(Val);
1149 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1151 return getConstantFP(apf, VT, isTarget);
1153 llvm_unreachable("Unsupported type in getConstantFP");
1156 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1157 EVT VT, int64_t Offset,
1159 unsigned char TargetFlags) {
1160 assert((TargetFlags == 0 || isTargetGA) &&
1161 "Cannot set target flags on target-independent globals");
1162 const TargetLowering *TLI = TM.getTargetLowering();
1164 // Truncate (with sign-extension) the offset value to the pointer size.
1165 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1167 Offset = SignExtend64(Offset, BitWidth);
1169 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1171 // If GV is an alias then use the aliasee for determining thread-localness.
1172 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1173 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1177 if (GVar && GVar->isThreadLocal())
1178 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1180 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1182 FoldingSetNodeID ID;
1183 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1185 ID.AddInteger(Offset);
1186 ID.AddInteger(TargetFlags);
1187 ID.AddInteger(GV->getType()->getAddressSpace());
1189 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1190 return SDValue(E, 0);
1192 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1193 DL.getDebugLoc(), GV, VT,
1194 Offset, TargetFlags);
1195 CSEMap.InsertNode(N, IP);
1196 AllNodes.push_back(N);
1197 return SDValue(N, 0);
1200 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1201 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1202 FoldingSetNodeID ID;
1203 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1206 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1207 return SDValue(E, 0);
1209 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1210 CSEMap.InsertNode(N, IP);
1211 AllNodes.push_back(N);
1212 return SDValue(N, 0);
1215 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1216 unsigned char TargetFlags) {
1217 assert((TargetFlags == 0 || isTarget) &&
1218 "Cannot set target flags on target-independent jump tables");
1219 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1220 FoldingSetNodeID ID;
1221 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1223 ID.AddInteger(TargetFlags);
1225 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1226 return SDValue(E, 0);
1228 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1230 CSEMap.InsertNode(N, IP);
1231 AllNodes.push_back(N);
1232 return SDValue(N, 0);
1235 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1236 unsigned Alignment, int Offset,
1238 unsigned char TargetFlags) {
1239 assert((TargetFlags == 0 || isTarget) &&
1240 "Cannot set target flags on target-independent globals");
1243 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1244 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1245 FoldingSetNodeID ID;
1246 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1247 ID.AddInteger(Alignment);
1248 ID.AddInteger(Offset);
1250 ID.AddInteger(TargetFlags);
1252 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1253 return SDValue(E, 0);
1255 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1256 Alignment, TargetFlags);
1257 CSEMap.InsertNode(N, IP);
1258 AllNodes.push_back(N);
1259 return SDValue(N, 0);
1263 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1264 unsigned Alignment, int Offset,
1266 unsigned char TargetFlags) {
1267 assert((TargetFlags == 0 || isTarget) &&
1268 "Cannot set target flags on target-independent globals");
1271 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1272 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1273 FoldingSetNodeID ID;
1274 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1275 ID.AddInteger(Alignment);
1276 ID.AddInteger(Offset);
1277 C->addSelectionDAGCSEId(ID);
1278 ID.AddInteger(TargetFlags);
1280 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1281 return SDValue(E, 0);
1283 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1284 Alignment, TargetFlags);
1285 CSEMap.InsertNode(N, IP);
1286 AllNodes.push_back(N);
1287 return SDValue(N, 0);
1290 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1291 unsigned char TargetFlags) {
1292 FoldingSetNodeID ID;
1293 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1294 ID.AddInteger(Index);
1295 ID.AddInteger(Offset);
1296 ID.AddInteger(TargetFlags);
1298 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1299 return SDValue(E, 0);
1301 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1303 CSEMap.InsertNode(N, IP);
1304 AllNodes.push_back(N);
1305 return SDValue(N, 0);
1308 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1309 FoldingSetNodeID ID;
1310 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1313 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1314 return SDValue(E, 0);
1316 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1317 CSEMap.InsertNode(N, IP);
1318 AllNodes.push_back(N);
1319 return SDValue(N, 0);
1322 SDValue SelectionDAG::getValueType(EVT VT) {
1323 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1324 ValueTypeNodes.size())
1325 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1327 SDNode *&N = VT.isExtended() ?
1328 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1330 if (N) return SDValue(N, 0);
1331 N = new (NodeAllocator) VTSDNode(VT);
1332 AllNodes.push_back(N);
1333 return SDValue(N, 0);
1336 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1337 SDNode *&N = ExternalSymbols[Sym];
1338 if (N) return SDValue(N, 0);
1339 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1340 AllNodes.push_back(N);
1341 return SDValue(N, 0);
1344 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1345 unsigned char TargetFlags) {
1347 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1349 if (N) return SDValue(N, 0);
1350 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1351 AllNodes.push_back(N);
1352 return SDValue(N, 0);
1355 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1356 if ((unsigned)Cond >= CondCodeNodes.size())
1357 CondCodeNodes.resize(Cond+1);
1359 if (!CondCodeNodes[Cond]) {
1360 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1361 CondCodeNodes[Cond] = N;
1362 AllNodes.push_back(N);
1365 return SDValue(CondCodeNodes[Cond], 0);
1368 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1369 // the shuffle mask M that point at N1 to point at N2, and indices that point
1370 // N2 to point at N1.
1371 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1373 int NElts = M.size();
1374 for (int i = 0; i != NElts; ++i) {
1382 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1383 SDValue N2, const int *Mask) {
1384 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1385 "Invalid VECTOR_SHUFFLE");
1387 // Canonicalize shuffle undef, undef -> undef
1388 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1389 return getUNDEF(VT);
1391 // Validate that all indices in Mask are within the range of the elements
1392 // input to the shuffle.
1393 unsigned NElts = VT.getVectorNumElements();
1394 SmallVector<int, 8> MaskVec;
1395 for (unsigned i = 0; i != NElts; ++i) {
1396 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1397 MaskVec.push_back(Mask[i]);
1400 // Canonicalize shuffle v, v -> v, undef
1403 for (unsigned i = 0; i != NElts; ++i)
1404 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1407 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1408 if (N1.getOpcode() == ISD::UNDEF)
1409 commuteShuffle(N1, N2, MaskVec);
1411 // Canonicalize all index into lhs, -> shuffle lhs, undef
1412 // Canonicalize all index into rhs, -> shuffle rhs, undef
1413 bool AllLHS = true, AllRHS = true;
1414 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1415 for (unsigned i = 0; i != NElts; ++i) {
1416 if (MaskVec[i] >= (int)NElts) {
1421 } else if (MaskVec[i] >= 0) {
1425 if (AllLHS && AllRHS)
1426 return getUNDEF(VT);
1427 if (AllLHS && !N2Undef)
1431 commuteShuffle(N1, N2, MaskVec);
1434 // If Identity shuffle return that node.
1435 bool Identity = true;
1436 for (unsigned i = 0; i != NElts; ++i) {
1437 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1439 if (Identity && NElts)
1442 // Shuffling a constant splat doesn't change the result.
1443 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1444 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1447 FoldingSetNodeID ID;
1448 SDValue Ops[2] = { N1, N2 };
1449 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1450 for (unsigned i = 0; i != NElts; ++i)
1451 ID.AddInteger(MaskVec[i]);
1454 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1455 return SDValue(E, 0);
1457 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1458 // SDNode doesn't have access to it. This memory will be "leaked" when
1459 // the node is deallocated, but recovered when the NodeAllocator is released.
1460 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1461 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1463 ShuffleVectorSDNode *N =
1464 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1465 dl.getDebugLoc(), N1, N2,
1467 CSEMap.InsertNode(N, IP);
1468 AllNodes.push_back(N);
1469 return SDValue(N, 0);
1472 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1473 SDValue Val, SDValue DTy,
1474 SDValue STy, SDValue Rnd, SDValue Sat,
1475 ISD::CvtCode Code) {
1476 // If the src and dest types are the same and the conversion is between
1477 // integer types of the same sign or two floats, no conversion is necessary.
1479 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1482 FoldingSetNodeID ID;
1483 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1484 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1486 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1487 return SDValue(E, 0);
1489 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1492 CSEMap.InsertNode(N, IP);
1493 AllNodes.push_back(N);
1494 return SDValue(N, 0);
1497 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1498 FoldingSetNodeID ID;
1499 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1500 ID.AddInteger(RegNo);
1502 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1503 return SDValue(E, 0);
1505 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1506 CSEMap.InsertNode(N, IP);
1507 AllNodes.push_back(N);
1508 return SDValue(N, 0);
1511 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1512 FoldingSetNodeID ID;
1513 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1514 ID.AddPointer(RegMask);
1516 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1517 return SDValue(E, 0);
1519 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1520 CSEMap.InsertNode(N, IP);
1521 AllNodes.push_back(N);
1522 return SDValue(N, 0);
1525 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1526 FoldingSetNodeID ID;
1527 SDValue Ops[] = { Root };
1528 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1529 ID.AddPointer(Label);
1531 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1532 return SDValue(E, 0);
1534 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1535 dl.getDebugLoc(), Root, Label);
1536 CSEMap.InsertNode(N, IP);
1537 AllNodes.push_back(N);
1538 return SDValue(N, 0);
1542 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1545 unsigned char TargetFlags) {
1546 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1548 FoldingSetNodeID ID;
1549 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1551 ID.AddInteger(Offset);
1552 ID.AddInteger(TargetFlags);
1554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1555 return SDValue(E, 0);
1557 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1559 CSEMap.InsertNode(N, IP);
1560 AllNodes.push_back(N);
1561 return SDValue(N, 0);
1564 SDValue SelectionDAG::getSrcValue(const Value *V) {
1565 assert((!V || V->getType()->isPointerTy()) &&
1566 "SrcValue is not a pointer?");
1568 FoldingSetNodeID ID;
1569 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1573 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1574 return SDValue(E, 0);
1576 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1577 CSEMap.InsertNode(N, IP);
1578 AllNodes.push_back(N);
1579 return SDValue(N, 0);
1582 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1583 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1584 FoldingSetNodeID ID;
1585 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1589 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1590 return SDValue(E, 0);
1592 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1593 CSEMap.InsertNode(N, IP);
1594 AllNodes.push_back(N);
1595 return SDValue(N, 0);
1598 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1599 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1600 unsigned SrcAS, unsigned DestAS) {
1601 SDValue Ops[] = {Ptr};
1602 FoldingSetNodeID ID;
1603 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1604 ID.AddInteger(SrcAS);
1605 ID.AddInteger(DestAS);
1608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1609 return SDValue(E, 0);
1611 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1613 VT, Ptr, SrcAS, DestAS);
1614 CSEMap.InsertNode(N, IP);
1615 AllNodes.push_back(N);
1616 return SDValue(N, 0);
1619 /// getShiftAmountOperand - Return the specified value casted to
1620 /// the target's desired shift amount type.
1621 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1622 EVT OpTy = Op.getValueType();
1623 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1624 if (OpTy == ShTy || OpTy.isVector()) return Op;
1626 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1627 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1630 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1631 /// specified value type.
1632 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1633 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1634 unsigned ByteSize = VT.getStoreSize();
1635 Type *Ty = VT.getTypeForEVT(*getContext());
1636 const TargetLowering *TLI = TM.getTargetLowering();
1637 unsigned StackAlign =
1638 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1640 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1641 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1644 /// CreateStackTemporary - Create a stack temporary suitable for holding
1645 /// either of the specified value types.
1646 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1647 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1648 VT2.getStoreSizeInBits())/8;
1649 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1650 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1651 const TargetLowering *TLI = TM.getTargetLowering();
1652 const DataLayout *TD = TLI->getDataLayout();
1653 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1654 TD->getPrefTypeAlignment(Ty2));
1656 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1657 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1658 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1661 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1662 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1663 // These setcc operations always fold.
1667 case ISD::SETFALSE2: return getConstant(0, VT);
1669 case ISD::SETTRUE2: {
1670 const TargetLowering *TLI = TM.getTargetLowering();
1671 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1673 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1686 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1690 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1691 const APInt &C2 = N2C->getAPIntValue();
1692 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1693 const APInt &C1 = N1C->getAPIntValue();
1696 default: llvm_unreachable("Unknown integer setcc!");
1697 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1698 case ISD::SETNE: return getConstant(C1 != C2, VT);
1699 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1700 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1701 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1702 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1703 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1704 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1705 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1706 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1710 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1711 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1712 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1715 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1716 return getUNDEF(VT);
1718 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1719 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1720 return getUNDEF(VT);
1722 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1723 R==APFloat::cmpLessThan, VT);
1724 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1725 return getUNDEF(VT);
1727 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1728 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1729 return getUNDEF(VT);
1731 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1732 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1733 return getUNDEF(VT);
1735 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1736 R==APFloat::cmpEqual, VT);
1737 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1738 return getUNDEF(VT);
1740 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1741 R==APFloat::cmpEqual, VT);
1742 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1743 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1744 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1745 R==APFloat::cmpEqual, VT);
1746 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1747 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1748 R==APFloat::cmpLessThan, VT);
1749 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1750 R==APFloat::cmpUnordered, VT);
1751 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1752 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1755 // Ensure that the constant occurs on the RHS.
1756 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1757 MVT CompVT = N1.getValueType().getSimpleVT();
1758 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1761 return getSetCC(dl, VT, N2, N1, SwappedCond);
1765 // Could not fold it.
1769 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1770 /// use this predicate to simplify operations downstream.
1771 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1772 // This predicate is not safe for vector operations.
1773 if (Op.getValueType().isVector())
1776 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1777 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1780 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1781 /// this predicate to simplify operations downstream. Mask is known to be zero
1782 /// for bits that V cannot have.
1783 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1784 unsigned Depth) const {
1785 APInt KnownZero, KnownOne;
1786 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1787 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1788 return (KnownZero & Mask) == Mask;
1791 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1792 /// known to be either zero or one and return them in the KnownZero/KnownOne
1793 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1795 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1796 APInt &KnownOne, unsigned Depth) const {
1797 const TargetLowering *TLI = TM.getTargetLowering();
1798 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1800 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1802 return; // Limit search depth.
1804 APInt KnownZero2, KnownOne2;
1806 switch (Op.getOpcode()) {
1808 // We know all of the bits for a constant!
1809 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1810 KnownZero = ~KnownOne;
1813 // If either the LHS or the RHS are Zero, the result is zero.
1814 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1815 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1816 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1817 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1819 // Output known-1 bits are only known if set in both the LHS & RHS.
1820 KnownOne &= KnownOne2;
1821 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1822 KnownZero |= KnownZero2;
1825 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1826 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1827 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1828 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1830 // Output known-0 bits are only known if clear in both the LHS & RHS.
1831 KnownZero &= KnownZero2;
1832 // Output known-1 are known to be set if set in either the LHS | RHS.
1833 KnownOne |= KnownOne2;
1836 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1837 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1838 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1839 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1841 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1842 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1843 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1844 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1845 KnownZero = KnownZeroOut;
1849 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1850 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1851 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1852 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1854 // If low bits are zero in either operand, output low known-0 bits.
1855 // Also compute a conserative estimate for high known-0 bits.
1856 // More trickiness is possible, but this is sufficient for the
1857 // interesting case of alignment computation.
1858 KnownOne.clearAllBits();
1859 unsigned TrailZ = KnownZero.countTrailingOnes() +
1860 KnownZero2.countTrailingOnes();
1861 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1862 KnownZero2.countLeadingOnes(),
1863 BitWidth) - BitWidth;
1865 TrailZ = std::min(TrailZ, BitWidth);
1866 LeadZ = std::min(LeadZ, BitWidth);
1867 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1868 APInt::getHighBitsSet(BitWidth, LeadZ);
1872 // For the purposes of computing leading zeros we can conservatively
1873 // treat a udiv as a logical right shift by the power of 2 known to
1874 // be less than the denominator.
1875 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1876 unsigned LeadZ = KnownZero2.countLeadingOnes();
1878 KnownOne2.clearAllBits();
1879 KnownZero2.clearAllBits();
1880 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1881 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1882 if (RHSUnknownLeadingOnes != BitWidth)
1883 LeadZ = std::min(BitWidth,
1884 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1886 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1890 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1891 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1892 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1893 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1895 // Only known if known in both the LHS and RHS.
1896 KnownOne &= KnownOne2;
1897 KnownZero &= KnownZero2;
1899 case ISD::SELECT_CC:
1900 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1901 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1902 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1903 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1905 // Only known if known in both the LHS and RHS.
1906 KnownOne &= KnownOne2;
1907 KnownZero &= KnownZero2;
1915 if (Op.getResNo() != 1)
1917 // The boolean result conforms to getBooleanContents. Fall through.
1919 // If we know the result of a setcc has the top bits zero, use this info.
1920 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1921 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1922 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1925 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1926 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1927 unsigned ShAmt = SA->getZExtValue();
1929 // If the shift count is an invalid immediate, don't do anything.
1930 if (ShAmt >= BitWidth)
1933 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1934 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1935 KnownZero <<= ShAmt;
1937 // low bits known zero.
1938 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1942 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1943 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1944 unsigned ShAmt = SA->getZExtValue();
1946 // If the shift count is an invalid immediate, don't do anything.
1947 if (ShAmt >= BitWidth)
1950 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1951 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1952 KnownZero = KnownZero.lshr(ShAmt);
1953 KnownOne = KnownOne.lshr(ShAmt);
1955 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1956 KnownZero |= HighBits; // High bits known zero.
1960 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1961 unsigned ShAmt = SA->getZExtValue();
1963 // If the shift count is an invalid immediate, don't do anything.
1964 if (ShAmt >= BitWidth)
1967 // If any of the demanded bits are produced by the sign extension, we also
1968 // demand the input sign bit.
1969 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1971 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1972 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1973 KnownZero = KnownZero.lshr(ShAmt);
1974 KnownOne = KnownOne.lshr(ShAmt);
1976 // Handle the sign bits.
1977 APInt SignBit = APInt::getSignBit(BitWidth);
1978 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1980 if (KnownZero.intersects(SignBit)) {
1981 KnownZero |= HighBits; // New bits are known zero.
1982 } else if (KnownOne.intersects(SignBit)) {
1983 KnownOne |= HighBits; // New bits are known one.
1987 case ISD::SIGN_EXTEND_INREG: {
1988 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1989 unsigned EBits = EVT.getScalarType().getSizeInBits();
1991 // Sign extension. Compute the demanded bits in the result that are not
1992 // present in the input.
1993 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1995 APInt InSignBit = APInt::getSignBit(EBits);
1996 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1998 // If the sign extended bits are demanded, we know that the sign
2000 InSignBit = InSignBit.zext(BitWidth);
2001 if (NewBits.getBoolValue())
2002 InputDemandedBits |= InSignBit;
2004 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2005 KnownOne &= InputDemandedBits;
2006 KnownZero &= InputDemandedBits;
2007 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2009 // If the sign bit of the input is known set or clear, then we know the
2010 // top bits of the result.
2011 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2012 KnownZero |= NewBits;
2013 KnownOne &= ~NewBits;
2014 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2015 KnownOne |= NewBits;
2016 KnownZero &= ~NewBits;
2017 } else { // Input sign bit unknown
2018 KnownZero &= ~NewBits;
2019 KnownOne &= ~NewBits;
2024 case ISD::CTTZ_ZERO_UNDEF:
2026 case ISD::CTLZ_ZERO_UNDEF:
2028 unsigned LowBits = Log2_32(BitWidth)+1;
2029 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2030 KnownOne.clearAllBits();
2034 LoadSDNode *LD = cast<LoadSDNode>(Op);
2035 // If this is a ZEXTLoad and we are looking at the loaded value.
2036 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2037 EVT VT = LD->getMemoryVT();
2038 unsigned MemBits = VT.getScalarType().getSizeInBits();
2039 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2040 } else if (const MDNode *Ranges = LD->getRanges()) {
2041 computeMaskedBitsLoad(*Ranges, KnownZero);
2045 case ISD::ZERO_EXTEND: {
2046 EVT InVT = Op.getOperand(0).getValueType();
2047 unsigned InBits = InVT.getScalarType().getSizeInBits();
2048 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2049 KnownZero = KnownZero.trunc(InBits);
2050 KnownOne = KnownOne.trunc(InBits);
2051 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2052 KnownZero = KnownZero.zext(BitWidth);
2053 KnownOne = KnownOne.zext(BitWidth);
2054 KnownZero |= NewBits;
2057 case ISD::SIGN_EXTEND: {
2058 EVT InVT = Op.getOperand(0).getValueType();
2059 unsigned InBits = InVT.getScalarType().getSizeInBits();
2060 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2062 KnownZero = KnownZero.trunc(InBits);
2063 KnownOne = KnownOne.trunc(InBits);
2064 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2066 // Note if the sign bit is known to be zero or one.
2067 bool SignBitKnownZero = KnownZero.isNegative();
2068 bool SignBitKnownOne = KnownOne.isNegative();
2069 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2070 "Sign bit can't be known to be both zero and one!");
2072 KnownZero = KnownZero.zext(BitWidth);
2073 KnownOne = KnownOne.zext(BitWidth);
2075 // If the sign bit is known zero or one, the top bits match.
2076 if (SignBitKnownZero)
2077 KnownZero |= NewBits;
2078 else if (SignBitKnownOne)
2079 KnownOne |= NewBits;
2082 case ISD::ANY_EXTEND: {
2083 EVT InVT = Op.getOperand(0).getValueType();
2084 unsigned InBits = InVT.getScalarType().getSizeInBits();
2085 KnownZero = KnownZero.trunc(InBits);
2086 KnownOne = KnownOne.trunc(InBits);
2087 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2088 KnownZero = KnownZero.zext(BitWidth);
2089 KnownOne = KnownOne.zext(BitWidth);
2092 case ISD::TRUNCATE: {
2093 EVT InVT = Op.getOperand(0).getValueType();
2094 unsigned InBits = InVT.getScalarType().getSizeInBits();
2095 KnownZero = KnownZero.zext(InBits);
2096 KnownOne = KnownOne.zext(InBits);
2097 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2098 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2099 KnownZero = KnownZero.trunc(BitWidth);
2100 KnownOne = KnownOne.trunc(BitWidth);
2103 case ISD::AssertZext: {
2104 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2105 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2106 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2107 KnownZero |= (~InMask);
2108 KnownOne &= (~KnownZero);
2112 // All bits are zero except the low bit.
2113 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2117 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2118 // We know that the top bits of C-X are clear if X contains less bits
2119 // than C (i.e. no wrap-around can happen). For example, 20-X is
2120 // positive if we can prove that X is >= 0 and < 16.
2121 if (CLHS->getAPIntValue().isNonNegative()) {
2122 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2123 // NLZ can't be BitWidth with no sign bit
2124 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2125 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2127 // If all of the MaskV bits are known to be zero, then we know the
2128 // output top bits are zero, because we now know that the output is
2130 if ((KnownZero2 & MaskV) == MaskV) {
2131 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2132 // Top bits known zero.
2133 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2141 // Output known-0 bits are known if clear or set in both the low clear bits
2142 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2143 // low 3 bits clear.
2144 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2145 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2146 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2148 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2149 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2150 KnownZeroOut = std::min(KnownZeroOut,
2151 KnownZero2.countTrailingOnes());
2153 if (Op.getOpcode() == ISD::ADD) {
2154 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2158 // With ADDE, a carry bit may be added in, so we can only use this
2159 // information if we know (at least) that the low two bits are clear. We
2160 // then return to the caller that the low bit is unknown but that other bits
2162 if (KnownZeroOut >= 2) // ADDE
2163 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2167 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2168 const APInt &RA = Rem->getAPIntValue().abs();
2169 if (RA.isPowerOf2()) {
2170 APInt LowBits = RA - 1;
2171 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2173 // The low bits of the first operand are unchanged by the srem.
2174 KnownZero = KnownZero2 & LowBits;
2175 KnownOne = KnownOne2 & LowBits;
2177 // If the first operand is non-negative or has all low bits zero, then
2178 // the upper bits are all zero.
2179 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2180 KnownZero |= ~LowBits;
2182 // If the first operand is negative and not all low bits are zero, then
2183 // the upper bits are all one.
2184 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2185 KnownOne |= ~LowBits;
2186 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2191 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 const APInt &RA = Rem->getAPIntValue();
2193 if (RA.isPowerOf2()) {
2194 APInt LowBits = (RA - 1);
2195 KnownZero |= ~LowBits;
2196 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2197 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2202 // Since the result is less than or equal to either operand, any leading
2203 // zero bits in either operand must also exist in the result.
2204 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2205 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2207 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2208 KnownZero2.countLeadingOnes());
2209 KnownOne.clearAllBits();
2210 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2213 case ISD::FrameIndex:
2214 case ISD::TargetFrameIndex:
2215 if (unsigned Align = InferPtrAlignment(Op)) {
2216 // The low bits are known zero if the pointer is aligned.
2217 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2223 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2226 case ISD::INTRINSIC_WO_CHAIN:
2227 case ISD::INTRINSIC_W_CHAIN:
2228 case ISD::INTRINSIC_VOID:
2229 // Allow the target to implement this method for its nodes.
2230 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2235 /// ComputeNumSignBits - Return the number of times the sign bit of the
2236 /// register is replicated into the other bits. We know that at least 1 bit
2237 /// is always equal to the sign bit (itself), but other cases can give us
2238 /// information. For example, immediately after an "SRA X, 2", we know that
2239 /// the top 3 bits are all equal to each other, so we return 3.
2240 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2241 const TargetLowering *TLI = TM.getTargetLowering();
2242 EVT VT = Op.getValueType();
2243 assert(VT.isInteger() && "Invalid VT!");
2244 unsigned VTBits = VT.getScalarType().getSizeInBits();
2246 unsigned FirstAnswer = 1;
2249 return 1; // Limit search depth.
2251 switch (Op.getOpcode()) {
2253 case ISD::AssertSext:
2254 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2255 return VTBits-Tmp+1;
2256 case ISD::AssertZext:
2257 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2260 case ISD::Constant: {
2261 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2262 return Val.getNumSignBits();
2265 case ISD::SIGN_EXTEND:
2267 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2268 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2270 case ISD::SIGN_EXTEND_INREG:
2271 // Max of the input and what this extends.
2273 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2276 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2277 return std::max(Tmp, Tmp2);
2280 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2281 // SRA X, C -> adds C sign bits.
2282 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2283 Tmp += C->getZExtValue();
2284 if (Tmp > VTBits) Tmp = VTBits;
2288 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2289 // shl destroys sign bits.
2290 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2291 if (C->getZExtValue() >= VTBits || // Bad shift.
2292 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2293 return Tmp - C->getZExtValue();
2298 case ISD::XOR: // NOT is handled here.
2299 // Logical binary ops preserve the number of sign bits at the worst.
2300 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2302 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2303 FirstAnswer = std::min(Tmp, Tmp2);
2304 // We computed what we know about the sign bits as our first
2305 // answer. Now proceed to the generic code that uses
2306 // ComputeMaskedBits, and pick whichever answer is better.
2311 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2312 if (Tmp == 1) return 1; // Early out.
2313 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2314 return std::min(Tmp, Tmp2);
2322 if (Op.getResNo() != 1)
2324 // The boolean result conforms to getBooleanContents. Fall through.
2326 // If setcc returns 0/-1, all bits are sign bits.
2327 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2328 TargetLowering::ZeroOrNegativeOneBooleanContent)
2333 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2334 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2336 // Handle rotate right by N like a rotate left by 32-N.
2337 if (Op.getOpcode() == ISD::ROTR)
2338 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2340 // If we aren't rotating out all of the known-in sign bits, return the
2341 // number that are left. This handles rotl(sext(x), 1) for example.
2342 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2343 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2347 // Add can have at most one carry bit. Thus we know that the output
2348 // is, at worst, one more bit than the inputs.
2349 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2350 if (Tmp == 1) return 1; // Early out.
2352 // Special case decrementing a value (ADD X, -1):
2353 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2354 if (CRHS->isAllOnesValue()) {
2355 APInt KnownZero, KnownOne;
2356 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2358 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2360 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2363 // If we are subtracting one from a positive number, there is no carry
2364 // out of the result.
2365 if (KnownZero.isNegative())
2369 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2370 if (Tmp2 == 1) return 1;
2371 return std::min(Tmp, Tmp2)-1;
2374 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2375 if (Tmp2 == 1) return 1;
2378 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2379 if (CLHS->isNullValue()) {
2380 APInt KnownZero, KnownOne;
2381 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2382 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2384 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2387 // If the input is known to be positive (the sign bit is known clear),
2388 // the output of the NEG has the same number of sign bits as the input.
2389 if (KnownZero.isNegative())
2392 // Otherwise, we treat this like a SUB.
2395 // Sub can have at most one carry bit. Thus we know that the output
2396 // is, at worst, one more bit than the inputs.
2397 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2398 if (Tmp == 1) return 1; // Early out.
2399 return std::min(Tmp, Tmp2)-1;
2401 // FIXME: it's tricky to do anything useful for this, but it is an important
2402 // case for targets like X86.
2406 // If we are looking at the loaded value of the SDNode.
2407 if (Op.getResNo() == 0) {
2408 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2409 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2410 unsigned ExtType = LD->getExtensionType();
2413 case ISD::SEXTLOAD: // '17' bits known
2414 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2415 return VTBits-Tmp+1;
2416 case ISD::ZEXTLOAD: // '16' bits known
2417 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2423 // Allow the target to implement this method for its nodes.
2424 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2425 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2426 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2427 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2428 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2429 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2432 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2433 // use this information.
2434 APInt KnownZero, KnownOne;
2435 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2438 if (KnownZero.isNegative()) { // sign bit is 0
2440 } else if (KnownOne.isNegative()) { // sign bit is 1;
2447 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2448 // the number of identical bits in the top of the input value.
2450 Mask <<= Mask.getBitWidth()-VTBits;
2451 // Return # leading zeros. We use 'min' here in case Val was zero before
2452 // shifting. We don't want to return '64' as for an i32 "0".
2453 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2456 /// isBaseWithConstantOffset - Return true if the specified operand is an
2457 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2458 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2459 /// semantics as an ADD. This handles the equivalence:
2460 /// X|Cst == X+Cst iff X&Cst = 0.
2461 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2462 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2463 !isa<ConstantSDNode>(Op.getOperand(1)))
2466 if (Op.getOpcode() == ISD::OR &&
2467 !MaskedValueIsZero(Op.getOperand(0),
2468 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2475 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2476 // If we're told that NaNs won't happen, assume they won't.
2477 if (getTarget().Options.NoNaNsFPMath)
2480 // If the value is a constant, we can obviously see if it is a NaN or not.
2481 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2482 return !C->getValueAPF().isNaN();
2484 // TODO: Recognize more cases here.
2489 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2490 // If the value is a constant, we can obviously see if it is a zero or not.
2491 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2492 return !C->isZero();
2494 // TODO: Recognize more cases here.
2495 switch (Op.getOpcode()) {
2498 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2499 return !C->isNullValue();
2506 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2507 // Check the obvious case.
2508 if (A == B) return true;
2510 // For for negative and positive zero.
2511 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2512 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2513 if (CA->isZero() && CB->isZero()) return true;
2515 // Otherwise they may not be equal.
2519 /// getNode - Gets or creates the specified node.
2521 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2522 FoldingSetNodeID ID;
2523 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2525 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2526 return SDValue(E, 0);
2528 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2529 DL.getDebugLoc(), getVTList(VT));
2530 CSEMap.InsertNode(N, IP);
2532 AllNodes.push_back(N);
2536 return SDValue(N, 0);
2539 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2540 EVT VT, SDValue Operand) {
2541 // Constant fold unary operations with an integer constant operand. Even
2542 // opaque constant will be folded, because the folding of unary operations
2543 // doesn't create new constants with different values. Nevertheless, the
2544 // opaque flag is preserved during folding to prevent future folding with
2546 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2547 const APInt &Val = C->getAPIntValue();
2550 case ISD::SIGN_EXTEND:
2551 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2552 C->isTargetOpcode(), C->isOpaque());
2553 case ISD::ANY_EXTEND:
2554 case ISD::ZERO_EXTEND:
2556 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2557 C->isTargetOpcode(), C->isOpaque());
2558 case ISD::UINT_TO_FP:
2559 case ISD::SINT_TO_FP: {
2560 APFloat apf(EVTToAPFloatSemantics(VT),
2561 APInt::getNullValue(VT.getSizeInBits()));
2562 (void)apf.convertFromAPInt(Val,
2563 Opcode==ISD::SINT_TO_FP,
2564 APFloat::rmNearestTiesToEven);
2565 return getConstantFP(apf, VT);
2568 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2569 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2570 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2571 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2574 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2577 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2580 case ISD::CTLZ_ZERO_UNDEF:
2581 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2584 case ISD::CTTZ_ZERO_UNDEF:
2585 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2590 // Constant fold unary operations with a floating point constant operand.
2591 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2592 APFloat V = C->getValueAPF(); // make copy
2596 return getConstantFP(V, VT);
2599 return getConstantFP(V, VT);
2601 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2602 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2603 return getConstantFP(V, VT);
2607 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2608 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2609 return getConstantFP(V, VT);
2613 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2614 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2615 return getConstantFP(V, VT);
2618 case ISD::FP_EXTEND: {
2620 // This can return overflow, underflow, or inexact; we don't care.
2621 // FIXME need to be more flexible about rounding mode.
2622 (void)V.convert(EVTToAPFloatSemantics(VT),
2623 APFloat::rmNearestTiesToEven, &ignored);
2624 return getConstantFP(V, VT);
2626 case ISD::FP_TO_SINT:
2627 case ISD::FP_TO_UINT: {
2630 assert(integerPartWidth >= 64);
2631 // FIXME need to be more flexible about rounding mode.
2632 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2633 Opcode==ISD::FP_TO_SINT,
2634 APFloat::rmTowardZero, &ignored);
2635 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2637 APInt api(VT.getSizeInBits(), x);
2638 return getConstant(api, VT);
2641 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2642 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2643 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2644 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2649 unsigned OpOpcode = Operand.getNode()->getOpcode();
2651 case ISD::TokenFactor:
2652 case ISD::MERGE_VALUES:
2653 case ISD::CONCAT_VECTORS:
2654 return Operand; // Factor, merge or concat of one node? No need.
2655 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2656 case ISD::FP_EXTEND:
2657 assert(VT.isFloatingPoint() &&
2658 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2659 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2660 assert((!VT.isVector() ||
2661 VT.getVectorNumElements() ==
2662 Operand.getValueType().getVectorNumElements()) &&
2663 "Vector element count mismatch!");
2664 if (Operand.getOpcode() == ISD::UNDEF)
2665 return getUNDEF(VT);
2667 case ISD::SIGN_EXTEND:
2668 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2669 "Invalid SIGN_EXTEND!");
2670 if (Operand.getValueType() == VT) return Operand; // noop extension
2671 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2672 "Invalid sext node, dst < src!");
2673 assert((!VT.isVector() ||
2674 VT.getVectorNumElements() ==
2675 Operand.getValueType().getVectorNumElements()) &&
2676 "Vector element count mismatch!");
2677 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2678 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2679 else if (OpOpcode == ISD::UNDEF)
2680 // sext(undef) = 0, because the top bits will all be the same.
2681 return getConstant(0, VT);
2683 case ISD::ZERO_EXTEND:
2684 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2685 "Invalid ZERO_EXTEND!");
2686 if (Operand.getValueType() == VT) return Operand; // noop extension
2687 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2688 "Invalid zext node, dst < src!");
2689 assert((!VT.isVector() ||
2690 VT.getVectorNumElements() ==
2691 Operand.getValueType().getVectorNumElements()) &&
2692 "Vector element count mismatch!");
2693 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2694 return getNode(ISD::ZERO_EXTEND, DL, VT,
2695 Operand.getNode()->getOperand(0));
2696 else if (OpOpcode == ISD::UNDEF)
2697 // zext(undef) = 0, because the top bits will be zero.
2698 return getConstant(0, VT);
2700 case ISD::ANY_EXTEND:
2701 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2702 "Invalid ANY_EXTEND!");
2703 if (Operand.getValueType() == VT) return Operand; // noop extension
2704 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2705 "Invalid anyext node, dst < src!");
2706 assert((!VT.isVector() ||
2707 VT.getVectorNumElements() ==
2708 Operand.getValueType().getVectorNumElements()) &&
2709 "Vector element count mismatch!");
2711 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2712 OpOpcode == ISD::ANY_EXTEND)
2713 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2714 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2715 else if (OpOpcode == ISD::UNDEF)
2716 return getUNDEF(VT);
2718 // (ext (trunx x)) -> x
2719 if (OpOpcode == ISD::TRUNCATE) {
2720 SDValue OpOp = Operand.getNode()->getOperand(0);
2721 if (OpOp.getValueType() == VT)
2726 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2727 "Invalid TRUNCATE!");
2728 if (Operand.getValueType() == VT) return Operand; // noop truncate
2729 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2730 "Invalid truncate node, src < dst!");
2731 assert((!VT.isVector() ||
2732 VT.getVectorNumElements() ==
2733 Operand.getValueType().getVectorNumElements()) &&
2734 "Vector element count mismatch!");
2735 if (OpOpcode == ISD::TRUNCATE)
2736 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2737 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2738 OpOpcode == ISD::ANY_EXTEND) {
2739 // If the source is smaller than the dest, we still need an extend.
2740 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2741 .bitsLT(VT.getScalarType()))
2742 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2743 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2744 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2745 return Operand.getNode()->getOperand(0);
2747 if (OpOpcode == ISD::UNDEF)
2748 return getUNDEF(VT);
2751 // Basic sanity checking.
2752 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2753 && "Cannot BITCAST between types of different sizes!");
2754 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2755 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2756 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2757 if (OpOpcode == ISD::UNDEF)
2758 return getUNDEF(VT);
2760 case ISD::SCALAR_TO_VECTOR:
2761 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2762 (VT.getVectorElementType() == Operand.getValueType() ||
2763 (VT.getVectorElementType().isInteger() &&
2764 Operand.getValueType().isInteger() &&
2765 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2766 "Illegal SCALAR_TO_VECTOR node!");
2767 if (OpOpcode == ISD::UNDEF)
2768 return getUNDEF(VT);
2769 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2770 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2771 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2772 Operand.getConstantOperandVal(1) == 0 &&
2773 Operand.getOperand(0).getValueType() == VT)
2774 return Operand.getOperand(0);
2777 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2778 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2779 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2780 Operand.getNode()->getOperand(0));
2781 if (OpOpcode == ISD::FNEG) // --X -> X
2782 return Operand.getNode()->getOperand(0);
2785 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2786 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2791 SDVTList VTs = getVTList(VT);
2792 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2793 FoldingSetNodeID ID;
2794 SDValue Ops[1] = { Operand };
2795 AddNodeIDNode(ID, Opcode, VTs, Ops);
2797 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2798 return SDValue(E, 0);
2800 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2801 DL.getDebugLoc(), VTs, Operand);
2802 CSEMap.InsertNode(N, IP);
2804 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2805 DL.getDebugLoc(), VTs, Operand);
2808 AllNodes.push_back(N);
2812 return SDValue(N, 0);
2815 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2816 SDNode *Cst1, SDNode *Cst2) {
2817 // If the opcode is a target-specific ISD node, there's nothing we can
2818 // do here and the operand rules may not line up with the below, so
2820 if (Opcode >= ISD::BUILTIN_OP_END)
2823 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2824 SmallVector<SDValue, 4> Outputs;
2825 EVT SVT = VT.getScalarType();
2827 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2828 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2829 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2832 if (Scalar1 && Scalar2)
2833 // Scalar instruction.
2834 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2836 // For vectors extract each constant element into Inputs so we can constant
2837 // fold them individually.
2838 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2839 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2843 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2845 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2846 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2847 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2848 if (!V1 || !V2) // Not a constant, bail.
2851 if (V1->isOpaque() || V2->isOpaque())
2854 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2855 // FIXME: This is valid and could be handled by truncating the APInts.
2856 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2859 Inputs.push_back(std::make_pair(V1, V2));
2863 // We have a number of constant values, constant fold them element by element.
2864 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2865 const APInt &C1 = Inputs[I].first->getAPIntValue();
2866 const APInt &C2 = Inputs[I].second->getAPIntValue();
2870 Outputs.push_back(getConstant(C1 + C2, SVT));
2873 Outputs.push_back(getConstant(C1 - C2, SVT));
2876 Outputs.push_back(getConstant(C1 * C2, SVT));
2879 if (!C2.getBoolValue())
2881 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2884 if (!C2.getBoolValue())
2886 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2889 if (!C2.getBoolValue())
2891 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2894 if (!C2.getBoolValue())
2896 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2899 Outputs.push_back(getConstant(C1 & C2, SVT));
2902 Outputs.push_back(getConstant(C1 | C2, SVT));
2905 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2908 Outputs.push_back(getConstant(C1 << C2, SVT));
2911 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2914 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2917 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2920 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2927 assert((Scalar1 && Scalar2) ||
2928 VT.getVectorNumElements() == Outputs.size() && "No scalar or vector!");
2930 // Handle the scalar case first.
2932 return Outputs.back();
2934 // We may have a vector type but a scalar result. Create a splat.
2935 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2937 // Build a big vector out of the scalar elements we generated.
2938 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2941 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2943 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2944 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2947 case ISD::TokenFactor:
2948 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2949 N2.getValueType() == MVT::Other && "Invalid token factor!");
2950 // Fold trivial token factors.
2951 if (N1.getOpcode() == ISD::EntryToken) return N2;
2952 if (N2.getOpcode() == ISD::EntryToken) return N1;
2953 if (N1 == N2) return N1;
2955 case ISD::CONCAT_VECTORS:
2956 // Concat of UNDEFs is UNDEF.
2957 if (N1.getOpcode() == ISD::UNDEF &&
2958 N2.getOpcode() == ISD::UNDEF)
2959 return getUNDEF(VT);
2961 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2962 // one big BUILD_VECTOR.
2963 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2964 N2.getOpcode() == ISD::BUILD_VECTOR) {
2965 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2966 N1.getNode()->op_end());
2967 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2968 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2972 assert(VT.isInteger() && "This operator does not apply to FP types!");
2973 assert(N1.getValueType() == N2.getValueType() &&
2974 N1.getValueType() == VT && "Binary operator types must match!");
2975 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2976 // worth handling here.
2977 if (N2C && N2C->isNullValue())
2979 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2986 assert(VT.isInteger() && "This operator does not apply to FP types!");
2987 assert(N1.getValueType() == N2.getValueType() &&
2988 N1.getValueType() == VT && "Binary operator types must match!");
2989 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2990 // it's worth handling here.
2991 if (N2C && N2C->isNullValue())
3001 assert(VT.isInteger() && "This operator does not apply to FP types!");
3002 assert(N1.getValueType() == N2.getValueType() &&
3003 N1.getValueType() == VT && "Binary operator types must match!");
3010 if (getTarget().Options.UnsafeFPMath) {
3011 if (Opcode == ISD::FADD) {
3013 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3014 if (CFP->getValueAPF().isZero())
3017 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3018 if (CFP->getValueAPF().isZero())
3020 } else if (Opcode == ISD::FSUB) {
3022 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3023 if (CFP->getValueAPF().isZero())
3025 } else if (Opcode == ISD::FMUL) {
3026 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3029 // If the first operand isn't the constant, try the second
3031 CFP = dyn_cast<ConstantFPSDNode>(N2);
3038 return SDValue(CFP,0);
3040 if (CFP->isExactlyValue(1.0))
3045 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3046 assert(N1.getValueType() == N2.getValueType() &&
3047 N1.getValueType() == VT && "Binary operator types must match!");
3049 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3050 assert(N1.getValueType() == VT &&
3051 N1.getValueType().isFloatingPoint() &&
3052 N2.getValueType().isFloatingPoint() &&
3053 "Invalid FCOPYSIGN!");
3060 assert(VT == N1.getValueType() &&
3061 "Shift operators return type must be the same as their first arg");
3062 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3063 "Shifts only work on integers");
3064 assert((!VT.isVector() || VT == N2.getValueType()) &&
3065 "Vector shift amounts must be in the same as their first arg");
3066 // Verify that the shift amount VT is bit enough to hold valid shift
3067 // amounts. This catches things like trying to shift an i1024 value by an
3068 // i8, which is easy to fall into in generic code that uses
3069 // TLI.getShiftAmount().
3070 assert(N2.getValueType().getSizeInBits() >=
3071 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3072 "Invalid use of small shift amount with oversized value!");
3074 // Always fold shifts of i1 values so the code generator doesn't need to
3075 // handle them. Since we know the size of the shift has to be less than the
3076 // size of the value, the shift/rotate count is guaranteed to be zero.
3079 if (N2C && N2C->isNullValue())
3082 case ISD::FP_ROUND_INREG: {
3083 EVT EVT = cast<VTSDNode>(N2)->getVT();
3084 assert(VT == N1.getValueType() && "Not an inreg round!");
3085 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3086 "Cannot FP_ROUND_INREG integer types");
3087 assert(EVT.isVector() == VT.isVector() &&
3088 "FP_ROUND_INREG type should be vector iff the operand "
3090 assert((!EVT.isVector() ||
3091 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3092 "Vector element counts must match in FP_ROUND_INREG");
3093 assert(EVT.bitsLE(VT) && "Not rounding down!");
3095 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3099 assert(VT.isFloatingPoint() &&
3100 N1.getValueType().isFloatingPoint() &&
3101 VT.bitsLE(N1.getValueType()) &&
3102 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3103 if (N1.getValueType() == VT) return N1; // noop conversion.
3105 case ISD::AssertSext:
3106 case ISD::AssertZext: {
3107 EVT EVT = cast<VTSDNode>(N2)->getVT();
3108 assert(VT == N1.getValueType() && "Not an inreg extend!");
3109 assert(VT.isInteger() && EVT.isInteger() &&
3110 "Cannot *_EXTEND_INREG FP types");
3111 assert(!EVT.isVector() &&
3112 "AssertSExt/AssertZExt type should be the vector element type "
3113 "rather than the vector type!");
3114 assert(EVT.bitsLE(VT) && "Not extending!");
3115 if (VT == EVT) return N1; // noop assertion.
3118 case ISD::SIGN_EXTEND_INREG: {
3119 EVT EVT = cast<VTSDNode>(N2)->getVT();
3120 assert(VT == N1.getValueType() && "Not an inreg extend!");
3121 assert(VT.isInteger() && EVT.isInteger() &&
3122 "Cannot *_EXTEND_INREG FP types");
3123 assert(EVT.isVector() == VT.isVector() &&
3124 "SIGN_EXTEND_INREG type should be vector iff the operand "
3126 assert((!EVT.isVector() ||
3127 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3128 "Vector element counts must match in SIGN_EXTEND_INREG");
3129 assert(EVT.bitsLE(VT) && "Not extending!");
3130 if (EVT == VT) return N1; // Not actually extending
3133 APInt Val = N1C->getAPIntValue();
3134 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3135 Val <<= Val.getBitWidth()-FromBits;
3136 Val = Val.ashr(Val.getBitWidth()-FromBits);
3137 return getConstant(Val, VT);
3141 case ISD::EXTRACT_VECTOR_ELT:
3142 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3143 if (N1.getOpcode() == ISD::UNDEF)
3144 return getUNDEF(VT);
3146 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3147 // expanding copies of large vectors from registers.
3149 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3150 N1.getNumOperands() > 0) {
3152 N1.getOperand(0).getValueType().getVectorNumElements();
3153 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3154 N1.getOperand(N2C->getZExtValue() / Factor),
3155 getConstant(N2C->getZExtValue() % Factor,
3156 N2.getValueType()));
3159 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3160 // expanding large vector constants.
3161 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3162 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3164 if (VT != Elt.getValueType())
3165 // If the vector element type is not legal, the BUILD_VECTOR operands
3166 // are promoted and implicitly truncated, and the result implicitly
3167 // extended. Make that explicit here.
3168 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3173 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3174 // operations are lowered to scalars.
3175 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3176 // If the indices are the same, return the inserted element else
3177 // if the indices are known different, extract the element from
3178 // the original vector.
3179 SDValue N1Op2 = N1.getOperand(2);
3180 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3182 if (N1Op2C && N2C) {
3183 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3184 if (VT == N1.getOperand(1).getValueType())
3185 return N1.getOperand(1);
3187 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3190 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3194 case ISD::EXTRACT_ELEMENT:
3195 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3196 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3197 (N1.getValueType().isInteger() == VT.isInteger()) &&
3198 N1.getValueType() != VT &&
3199 "Wrong types for EXTRACT_ELEMENT!");
3201 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3202 // 64-bit integers into 32-bit parts. Instead of building the extract of
3203 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3204 if (N1.getOpcode() == ISD::BUILD_PAIR)
3205 return N1.getOperand(N2C->getZExtValue());
3207 // EXTRACT_ELEMENT of a constant int is also very common.
3208 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3209 unsigned ElementSize = VT.getSizeInBits();
3210 unsigned Shift = ElementSize * N2C->getZExtValue();
3211 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3212 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3215 case ISD::EXTRACT_SUBVECTOR: {
3217 if (VT.isSimple() && N1.getValueType().isSimple()) {
3218 assert(VT.isVector() && N1.getValueType().isVector() &&
3219 "Extract subvector VTs must be a vectors!");
3220 assert(VT.getVectorElementType() ==
3221 N1.getValueType().getVectorElementType() &&
3222 "Extract subvector VTs must have the same element type!");
3223 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3224 "Extract subvector must be from larger vector to smaller vector!");
3226 if (isa<ConstantSDNode>(Index.getNode())) {
3227 assert((VT.getVectorNumElements() +
3228 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3229 <= N1.getValueType().getVectorNumElements())
3230 && "Extract subvector overflow!");
3233 // Trivial extraction.
3234 if (VT.getSimpleVT() == N1.getSimpleValueType())
3241 // Perform trivial constant folding.
3242 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3243 if (SV.getNode()) return SV;
3245 // Canonicalize constant to RHS if commutative.
3246 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3247 std::swap(N1C, N2C);
3251 // Constant fold FP operations.
3252 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3253 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3255 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3256 // Canonicalize constant to RHS if commutative.
3257 std::swap(N1CFP, N2CFP);
3260 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3261 APFloat::opStatus s;
3264 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3265 if (s != APFloat::opInvalidOp)
3266 return getConstantFP(V1, VT);
3269 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3270 if (s!=APFloat::opInvalidOp)
3271 return getConstantFP(V1, VT);
3274 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3275 if (s!=APFloat::opInvalidOp)
3276 return getConstantFP(V1, VT);
3279 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3280 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3281 return getConstantFP(V1, VT);
3284 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3285 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3286 return getConstantFP(V1, VT);
3288 case ISD::FCOPYSIGN:
3290 return getConstantFP(V1, VT);
3295 if (Opcode == ISD::FP_ROUND) {
3296 APFloat V = N1CFP->getValueAPF(); // make copy
3298 // This can return overflow, underflow, or inexact; we don't care.
3299 // FIXME need to be more flexible about rounding mode.
3300 (void)V.convert(EVTToAPFloatSemantics(VT),
3301 APFloat::rmNearestTiesToEven, &ignored);
3302 return getConstantFP(V, VT);
3306 // Canonicalize an UNDEF to the RHS, even over a constant.
3307 if (N1.getOpcode() == ISD::UNDEF) {
3308 if (isCommutativeBinOp(Opcode)) {
3312 case ISD::FP_ROUND_INREG:
3313 case ISD::SIGN_EXTEND_INREG:
3319 return N1; // fold op(undef, arg2) -> undef
3327 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3328 // For vectors, we can't easily build an all zero vector, just return
3335 // Fold a bunch of operators when the RHS is undef.
3336 if (N2.getOpcode() == ISD::UNDEF) {
3339 if (N1.getOpcode() == ISD::UNDEF)
3340 // Handle undef ^ undef -> 0 special case. This is a common
3342 return getConstant(0, VT);
3352 return N2; // fold op(arg1, undef) -> undef
3358 if (getTarget().Options.UnsafeFPMath)
3366 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3367 // For vectors, we can't easily build an all zero vector, just return
3372 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3373 // For vectors, we can't easily build an all one vector, just return
3381 // Memoize this node if possible.
3383 SDVTList VTs = getVTList(VT);
3384 if (VT != MVT::Glue) {
3385 SDValue Ops[] = { N1, N2 };
3386 FoldingSetNodeID ID;
3387 AddNodeIDNode(ID, Opcode, VTs, Ops);
3389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3390 return SDValue(E, 0);
3392 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3393 DL.getDebugLoc(), VTs, N1, N2);
3394 CSEMap.InsertNode(N, IP);
3396 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3397 DL.getDebugLoc(), VTs, N1, N2);
3400 AllNodes.push_back(N);
3404 return SDValue(N, 0);
3407 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3408 SDValue N1, SDValue N2, SDValue N3) {
3409 // Perform various simplifications.
3410 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3413 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3414 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3415 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3416 if (N1CFP && N2CFP && N3CFP) {
3417 APFloat V1 = N1CFP->getValueAPF();
3418 const APFloat &V2 = N2CFP->getValueAPF();
3419 const APFloat &V3 = N3CFP->getValueAPF();
3420 APFloat::opStatus s =
3421 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3422 if (s != APFloat::opInvalidOp)
3423 return getConstantFP(V1, VT);
3427 case ISD::CONCAT_VECTORS:
3428 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3429 // one big BUILD_VECTOR.
3430 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3431 N2.getOpcode() == ISD::BUILD_VECTOR &&
3432 N3.getOpcode() == ISD::BUILD_VECTOR) {
3433 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3434 N1.getNode()->op_end());
3435 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3436 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3437 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3441 // Use FoldSetCC to simplify SETCC's.
3442 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3443 if (Simp.getNode()) return Simp;
3448 if (N1C->getZExtValue())
3449 return N2; // select true, X, Y -> X
3450 return N3; // select false, X, Y -> Y
3453 if (N2 == N3) return N2; // select C, X, X -> X
3455 case ISD::VECTOR_SHUFFLE:
3456 llvm_unreachable("should use getVectorShuffle constructor!");
3457 case ISD::INSERT_SUBVECTOR: {
3459 if (VT.isSimple() && N1.getValueType().isSimple()
3460 && N2.getValueType().isSimple()) {
3461 assert(VT.isVector() && N1.getValueType().isVector() &&
3462 N2.getValueType().isVector() &&
3463 "Insert subvector VTs must be a vectors");
3464 assert(VT == N1.getValueType() &&
3465 "Dest and insert subvector source types must match!");
3466 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3467 "Insert subvector must be from smaller vector to larger vector!");
3468 if (isa<ConstantSDNode>(Index.getNode())) {
3469 assert((N2.getValueType().getVectorNumElements() +
3470 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3471 <= VT.getVectorNumElements())
3472 && "Insert subvector overflow!");
3475 // Trivial insertion.
3476 if (VT.getSimpleVT() == N2.getSimpleValueType())
3482 // Fold bit_convert nodes from a type to themselves.
3483 if (N1.getValueType() == VT)
3488 // Memoize node if it doesn't produce a flag.
3490 SDVTList VTs = getVTList(VT);
3491 if (VT != MVT::Glue) {
3492 SDValue Ops[] = { N1, N2, N3 };
3493 FoldingSetNodeID ID;
3494 AddNodeIDNode(ID, Opcode, VTs, Ops);
3496 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3497 return SDValue(E, 0);
3499 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3500 DL.getDebugLoc(), VTs, N1, N2, N3);
3501 CSEMap.InsertNode(N, IP);
3503 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3504 DL.getDebugLoc(), VTs, N1, N2, N3);
3507 AllNodes.push_back(N);
3511 return SDValue(N, 0);
3514 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3515 SDValue N1, SDValue N2, SDValue N3,
3517 SDValue Ops[] = { N1, N2, N3, N4 };
3518 return getNode(Opcode, DL, VT, Ops);
3521 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3522 SDValue N1, SDValue N2, SDValue N3,
3523 SDValue N4, SDValue N5) {
3524 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3525 return getNode(Opcode, DL, VT, Ops);
3528 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3529 /// the incoming stack arguments to be loaded from the stack.
3530 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3531 SmallVector<SDValue, 8> ArgChains;
3533 // Include the original chain at the beginning of the list. When this is
3534 // used by target LowerCall hooks, this helps legalize find the
3535 // CALLSEQ_BEGIN node.
3536 ArgChains.push_back(Chain);
3538 // Add a chain value for each stack argument.
3539 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3540 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3541 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3542 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3543 if (FI->getIndex() < 0)
3544 ArgChains.push_back(SDValue(L, 1));
3546 // Build a tokenfactor for all the chains.
3547 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3550 /// getMemsetValue - Vectorized representation of the memset value
3552 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3554 assert(Value.getOpcode() != ISD::UNDEF);
3556 unsigned NumBits = VT.getScalarType().getSizeInBits();
3557 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3558 assert(C->getAPIntValue().getBitWidth() == 8);
3559 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3561 return DAG.getConstant(Val, VT);
3562 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3565 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3567 // Use a multiplication with 0x010101... to extend the input to the
3569 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3570 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3576 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3577 /// used when a memcpy is turned into a memset when the source is a constant
3579 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3580 const TargetLowering &TLI, StringRef Str) {
3581 // Handle vector with all elements zero.
3584 return DAG.getConstant(0, VT);
3585 else if (VT == MVT::f32 || VT == MVT::f64)
3586 return DAG.getConstantFP(0.0, VT);
3587 else if (VT.isVector()) {
3588 unsigned NumElts = VT.getVectorNumElements();
3589 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3590 return DAG.getNode(ISD::BITCAST, dl, VT,
3591 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3594 llvm_unreachable("Expected type!");
3597 assert(!VT.isVector() && "Can't handle vector type here!");
3598 unsigned NumVTBits = VT.getSizeInBits();
3599 unsigned NumVTBytes = NumVTBits / 8;
3600 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3602 APInt Val(NumVTBits, 0);
3603 if (TLI.isLittleEndian()) {
3604 for (unsigned i = 0; i != NumBytes; ++i)
3605 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3607 for (unsigned i = 0; i != NumBytes; ++i)
3608 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3611 // If the "cost" of materializing the integer immediate is less than the cost
3612 // of a load, then it is cost effective to turn the load into the immediate.
3613 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3614 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3615 return DAG.getConstant(Val, VT);
3616 return SDValue(nullptr, 0);
3619 /// getMemBasePlusOffset - Returns base and offset node for the
3621 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3622 SelectionDAG &DAG) {
3623 EVT VT = Base.getValueType();
3624 return DAG.getNode(ISD::ADD, dl,
3625 VT, Base, DAG.getConstant(Offset, VT));
3628 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3630 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3631 unsigned SrcDelta = 0;
3632 GlobalAddressSDNode *G = nullptr;
3633 if (Src.getOpcode() == ISD::GlobalAddress)
3634 G = cast<GlobalAddressSDNode>(Src);
3635 else if (Src.getOpcode() == ISD::ADD &&
3636 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3637 Src.getOperand(1).getOpcode() == ISD::Constant) {
3638 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3639 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3644 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3647 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3648 /// to replace the memset / memcpy. Return true if the number of memory ops
3649 /// is below the threshold. It returns the types of the sequence of
3650 /// memory ops to perform memset / memcpy by reference.
3651 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3652 unsigned Limit, uint64_t Size,
3653 unsigned DstAlign, unsigned SrcAlign,
3659 const TargetLowering &TLI) {
3660 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3661 "Expecting memcpy / memset source to meet alignment requirement!");
3662 // If 'SrcAlign' is zero, that means the memory operation does not need to
3663 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3664 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3665 // is the specified alignment of the memory operation. If it is zero, that
3666 // means it's possible to change the alignment of the destination.
3667 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3668 // not need to be loaded.
3669 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3670 IsMemset, ZeroMemset, MemcpyStrSrc,
3671 DAG.getMachineFunction());
3673 if (VT == MVT::Other) {
3675 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3676 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3677 VT = TLI.getPointerTy();
3679 switch (DstAlign & 7) {
3680 case 0: VT = MVT::i64; break;
3681 case 4: VT = MVT::i32; break;
3682 case 2: VT = MVT::i16; break;
3683 default: VT = MVT::i8; break;
3688 while (!TLI.isTypeLegal(LVT))
3689 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3690 assert(LVT.isInteger());
3696 unsigned NumMemOps = 0;
3698 unsigned VTSize = VT.getSizeInBits() / 8;
3699 while (VTSize > Size) {
3700 // For now, only use non-vector load / store's for the left-over pieces.
3705 if (VT.isVector() || VT.isFloatingPoint()) {
3706 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3707 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3708 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3710 else if (NewVT == MVT::i64 &&
3711 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3712 TLI.isSafeMemOpType(MVT::f64)) {
3713 // i64 is usually not legal on 32-bit targets, but f64 may be.
3721 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3722 if (NewVT == MVT::i8)
3724 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3726 NewVTSize = NewVT.getSizeInBits() / 8;
3728 // If the new VT cannot cover all of the remaining bits, then consider
3729 // issuing a (or a pair of) unaligned and overlapping load / store.
3730 // FIXME: Only does this for 64-bit or more since we don't have proper
3731 // cost model for unaligned load / store.
3734 if (NumMemOps && AllowOverlap &&
3735 VTSize >= 8 && NewVTSize < Size &&
3736 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3744 if (++NumMemOps > Limit)
3747 MemOps.push_back(VT);
3754 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3755 SDValue Chain, SDValue Dst,
3756 SDValue Src, uint64_t Size,
3757 unsigned Align, bool isVol,
3759 MachinePointerInfo DstPtrInfo,
3760 MachinePointerInfo SrcPtrInfo) {
3761 // Turn a memcpy of undef to nop.
3762 if (Src.getOpcode() == ISD::UNDEF)
3765 // Expand memcpy to a series of load and store ops if the size operand falls
3766 // below a certain threshold.
3767 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3768 // rather than maybe a humongous number of loads and stores.
3769 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3770 std::vector<EVT> MemOps;
3771 bool DstAlignCanChange = false;
3772 MachineFunction &MF = DAG.getMachineFunction();
3773 MachineFrameInfo *MFI = MF.getFrameInfo();
3775 MF.getFunction()->getAttributes().
3776 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3777 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3778 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3779 DstAlignCanChange = true;
3780 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3781 if (Align > SrcAlign)
3784 bool CopyFromStr = isMemSrcFromString(Src, Str);
3785 bool isZeroStr = CopyFromStr && Str.empty();
3786 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3788 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3789 (DstAlignCanChange ? 0 : Align),
3790 (isZeroStr ? 0 : SrcAlign),
3791 false, false, CopyFromStr, true, DAG, TLI))
3794 if (DstAlignCanChange) {
3795 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3796 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3798 // Don't promote to an alignment that would require dynamic stack
3800 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3801 if (!TRI->needsStackRealignment(MF))
3802 while (NewAlign > Align &&
3803 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3806 if (NewAlign > Align) {
3807 // Give the stack frame object a larger alignment if needed.
3808 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3809 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3814 SmallVector<SDValue, 8> OutChains;
3815 unsigned NumMemOps = MemOps.size();
3816 uint64_t SrcOff = 0, DstOff = 0;
3817 for (unsigned i = 0; i != NumMemOps; ++i) {
3819 unsigned VTSize = VT.getSizeInBits() / 8;
3820 SDValue Value, Store;
3822 if (VTSize > Size) {
3823 // Issuing an unaligned load / store pair that overlaps with the previous
3824 // pair. Adjust the offset accordingly.
3825 assert(i == NumMemOps-1 && i != 0);
3826 SrcOff -= VTSize - Size;
3827 DstOff -= VTSize - Size;
3831 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3832 // It's unlikely a store of a vector immediate can be done in a single
3833 // instruction. It would require a load from a constantpool first.
3834 // We only handle zero vectors here.
3835 // FIXME: Handle other cases where store of vector immediate is done in
3836 // a single instruction.
3837 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3838 if (Value.getNode())
3839 Store = DAG.getStore(Chain, dl, Value,
3840 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3841 DstPtrInfo.getWithOffset(DstOff), isVol,
3845 if (!Store.getNode()) {
3846 // The type might not be legal for the target. This should only happen
3847 // if the type is smaller than a legal type, as on PPC, so the right
3848 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3849 // to Load/Store if NVT==VT.
3850 // FIXME does the case above also need this?
3851 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3852 assert(NVT.bitsGE(VT));
3853 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3854 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3855 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3856 MinAlign(SrcAlign, SrcOff));
3857 Store = DAG.getTruncStore(Chain, dl, Value,
3858 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3859 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3862 OutChains.push_back(Store);
3868 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3871 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3872 SDValue Chain, SDValue Dst,
3873 SDValue Src, uint64_t Size,
3874 unsigned Align, bool isVol,
3876 MachinePointerInfo DstPtrInfo,
3877 MachinePointerInfo SrcPtrInfo) {
3878 // Turn a memmove of undef to nop.
3879 if (Src.getOpcode() == ISD::UNDEF)
3882 // Expand memmove to a series of load and store ops if the size operand falls
3883 // below a certain threshold.
3884 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3885 std::vector<EVT> MemOps;
3886 bool DstAlignCanChange = false;
3887 MachineFunction &MF = DAG.getMachineFunction();
3888 MachineFrameInfo *MFI = MF.getFrameInfo();
3889 bool OptSize = MF.getFunction()->getAttributes().
3890 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3891 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3892 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3893 DstAlignCanChange = true;
3894 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3895 if (Align > SrcAlign)
3897 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3899 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3900 (DstAlignCanChange ? 0 : Align), SrcAlign,
3901 false, false, false, false, DAG, TLI))
3904 if (DstAlignCanChange) {
3905 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3906 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3907 if (NewAlign > Align) {
3908 // Give the stack frame object a larger alignment if needed.
3909 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3910 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3915 uint64_t SrcOff = 0, DstOff = 0;
3916 SmallVector<SDValue, 8> LoadValues;
3917 SmallVector<SDValue, 8> LoadChains;
3918 SmallVector<SDValue, 8> OutChains;
3919 unsigned NumMemOps = MemOps.size();
3920 for (unsigned i = 0; i < NumMemOps; i++) {
3922 unsigned VTSize = VT.getSizeInBits() / 8;
3925 Value = DAG.getLoad(VT, dl, Chain,
3926 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3927 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3928 false, false, SrcAlign);
3929 LoadValues.push_back(Value);
3930 LoadChains.push_back(Value.getValue(1));
3933 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3935 for (unsigned i = 0; i < NumMemOps; i++) {
3937 unsigned VTSize = VT.getSizeInBits() / 8;
3940 Store = DAG.getStore(Chain, dl, LoadValues[i],
3941 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3942 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3943 OutChains.push_back(Store);
3947 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3950 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3953 /// \param DAG Selection DAG where lowered code is placed.
3954 /// \param dl Link to corresponding IR location.
3955 /// \param Chain Control flow dependency.
3956 /// \param Dst Pointer to destination memory location.
3957 /// \param Src Value of byte to write into the memory.
3958 /// \param Size Number of bytes to write.
3959 /// \param Align Alignment of the destination in bytes.
3960 /// \param isVol True if destination is volatile.
3961 /// \param DstPtrInfo IR information on the memory pointer.
3962 /// \returns New head in the control flow, if lowering was successful, empty
3963 /// SDValue otherwise.
3965 /// The function tries to replace 'llvm.memset' intrinsic with several store
3966 /// operations and value calculation code. This is usually profitable for small
3968 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3969 SDValue Chain, SDValue Dst,
3970 SDValue Src, uint64_t Size,
3971 unsigned Align, bool isVol,
3972 MachinePointerInfo DstPtrInfo) {
3973 // Turn a memset of undef to nop.
3974 if (Src.getOpcode() == ISD::UNDEF)
3977 // Expand memset to a series of load/store ops if the size operand
3978 // falls below a certain threshold.
3979 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3980 std::vector<EVT> MemOps;
3981 bool DstAlignCanChange = false;
3982 MachineFunction &MF = DAG.getMachineFunction();
3983 MachineFrameInfo *MFI = MF.getFrameInfo();
3984 bool OptSize = MF.getFunction()->getAttributes().
3985 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3986 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3987 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3988 DstAlignCanChange = true;
3990 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3991 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3992 Size, (DstAlignCanChange ? 0 : Align), 0,
3993 true, IsZeroVal, false, true, DAG, TLI))
3996 if (DstAlignCanChange) {
3997 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3998 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3999 if (NewAlign > Align) {
4000 // Give the stack frame object a larger alignment if needed.
4001 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4002 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4007 SmallVector<SDValue, 8> OutChains;
4008 uint64_t DstOff = 0;
4009 unsigned NumMemOps = MemOps.size();
4011 // Find the largest store and generate the bit pattern for it.
4012 EVT LargestVT = MemOps[0];
4013 for (unsigned i = 1; i < NumMemOps; i++)
4014 if (MemOps[i].bitsGT(LargestVT))
4015 LargestVT = MemOps[i];
4016 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4018 for (unsigned i = 0; i < NumMemOps; i++) {
4020 unsigned VTSize = VT.getSizeInBits() / 8;
4021 if (VTSize > Size) {
4022 // Issuing an unaligned load / store pair that overlaps with the previous
4023 // pair. Adjust the offset accordingly.
4024 assert(i == NumMemOps-1 && i != 0);
4025 DstOff -= VTSize - Size;
4028 // If this store is smaller than the largest store see whether we can get
4029 // the smaller value for free with a truncate.
4030 SDValue Value = MemSetValue;
4031 if (VT.bitsLT(LargestVT)) {
4032 if (!LargestVT.isVector() && !VT.isVector() &&
4033 TLI.isTruncateFree(LargestVT, VT))
4034 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4036 Value = getMemsetValue(Src, VT, DAG, dl);
4038 assert(Value.getValueType() == VT && "Value with wrong type.");
4039 SDValue Store = DAG.getStore(Chain, dl, Value,
4040 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4041 DstPtrInfo.getWithOffset(DstOff),
4042 isVol, false, Align);
4043 OutChains.push_back(Store);
4044 DstOff += VT.getSizeInBits() / 8;
4048 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4051 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4052 SDValue Src, SDValue Size,
4053 unsigned Align, bool isVol, bool AlwaysInline,
4054 MachinePointerInfo DstPtrInfo,
4055 MachinePointerInfo SrcPtrInfo) {
4056 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4058 // Check to see if we should lower the memcpy to loads and stores first.
4059 // For cases within the target-specified limits, this is the best choice.
4060 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4062 // Memcpy with size zero? Just return the original chain.
4063 if (ConstantSize->isNullValue())
4066 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4067 ConstantSize->getZExtValue(),Align,
4068 isVol, false, DstPtrInfo, SrcPtrInfo);
4069 if (Result.getNode())
4073 // Then check to see if we should lower the memcpy with target-specific
4074 // code. If the target chooses to do this, this is the next best.
4076 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4077 isVol, AlwaysInline,
4078 DstPtrInfo, SrcPtrInfo);
4079 if (Result.getNode())
4082 // If we really need inline code and the target declined to provide it,
4083 // use a (potentially long) sequence of loads and stores.
4085 assert(ConstantSize && "AlwaysInline requires a constant size!");
4086 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4087 ConstantSize->getZExtValue(), Align, isVol,
4088 true, DstPtrInfo, SrcPtrInfo);
4091 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4092 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4093 // respect volatile, so they may do things like read or write memory
4094 // beyond the given memory regions. But fixing this isn't easy, and most
4095 // people don't care.
4097 const TargetLowering *TLI = TM.getTargetLowering();
4099 // Emit a library call.
4100 TargetLowering::ArgListTy Args;
4101 TargetLowering::ArgListEntry Entry;
4102 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4103 Entry.Node = Dst; Args.push_back(Entry);
4104 Entry.Node = Src; Args.push_back(Entry);
4105 Entry.Node = Size; Args.push_back(Entry);
4106 // FIXME: pass in SDLoc
4108 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4109 false, false, false, false, 0,
4110 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4111 /*isTailCall=*/false,
4112 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4113 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4114 TLI->getPointerTy()),
4116 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4118 return CallResult.second;
4121 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4122 SDValue Src, SDValue Size,
4123 unsigned Align, bool isVol,
4124 MachinePointerInfo DstPtrInfo,
4125 MachinePointerInfo SrcPtrInfo) {
4126 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4128 // Check to see if we should lower the memmove to loads and stores first.
4129 // For cases within the target-specified limits, this is the best choice.
4130 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4132 // Memmove with size zero? Just return the original chain.
4133 if (ConstantSize->isNullValue())
4137 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4138 ConstantSize->getZExtValue(), Align, isVol,
4139 false, DstPtrInfo, SrcPtrInfo);
4140 if (Result.getNode())
4144 // Then check to see if we should lower the memmove with target-specific
4145 // code. If the target chooses to do this, this is the next best.
4147 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4148 DstPtrInfo, SrcPtrInfo);
4149 if (Result.getNode())
4152 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4153 // not be safe. See memcpy above for more details.
4155 const TargetLowering *TLI = TM.getTargetLowering();
4157 // Emit a library call.
4158 TargetLowering::ArgListTy Args;
4159 TargetLowering::ArgListEntry Entry;
4160 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4161 Entry.Node = Dst; Args.push_back(Entry);
4162 Entry.Node = Src; Args.push_back(Entry);
4163 Entry.Node = Size; Args.push_back(Entry);
4164 // FIXME: pass in SDLoc
4166 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4167 false, false, false, false, 0,
4168 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4169 /*isTailCall=*/false,
4170 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4171 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4172 TLI->getPointerTy()),
4174 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4176 return CallResult.second;
4179 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4180 SDValue Src, SDValue Size,
4181 unsigned Align, bool isVol,
4182 MachinePointerInfo DstPtrInfo) {
4183 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4185 // Check to see if we should lower the memset to stores first.
4186 // For cases within the target-specified limits, this is the best choice.
4187 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4189 // Memset with size zero? Just return the original chain.
4190 if (ConstantSize->isNullValue())
4194 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4195 Align, isVol, DstPtrInfo);
4197 if (Result.getNode())
4201 // Then check to see if we should lower the memset with target-specific
4202 // code. If the target chooses to do this, this is the next best.
4204 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4206 if (Result.getNode())
4209 // Emit a library call.
4210 const TargetLowering *TLI = TM.getTargetLowering();
4211 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4212 TargetLowering::ArgListTy Args;
4213 TargetLowering::ArgListEntry Entry;
4214 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4215 Args.push_back(Entry);
4216 // Extend or truncate the argument to be an i32 value for the call.
4217 if (Src.getValueType().bitsGT(MVT::i32))
4218 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4220 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4222 Entry.Ty = Type::getInt32Ty(*getContext());
4223 Entry.isSExt = true;
4224 Args.push_back(Entry);
4226 Entry.Ty = IntPtrTy;
4227 Entry.isSExt = false;
4228 Args.push_back(Entry);
4229 // FIXME: pass in SDLoc
4231 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4232 false, false, false, false, 0,
4233 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4234 /*isTailCall=*/false,
4235 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4236 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4237 TLI->getPointerTy()),
4239 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4241 return CallResult.second;
4244 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4245 SDVTList VTList, ArrayRef<SDValue> Ops,
4246 MachineMemOperand *MMO,
4247 AtomicOrdering SuccessOrdering,
4248 AtomicOrdering FailureOrdering,
4249 SynchronizationScope SynchScope) {
4250 FoldingSetNodeID ID;
4251 ID.AddInteger(MemVT.getRawBits());
4252 AddNodeIDNode(ID, Opcode, VTList, Ops);
4253 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4255 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4256 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4257 return SDValue(E, 0);
4260 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4261 // SDNode doesn't have access to it. This memory will be "leaked" when
4262 // the node is deallocated, but recovered when the allocator is released.
4263 // If the number of operands is less than 5 we use AtomicSDNode's internal
4265 unsigned NumOps = Ops.size();
4266 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4269 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4270 dl.getDebugLoc(), VTList, MemVT,
4271 Ops.data(), DynOps, NumOps, MMO,
4272 SuccessOrdering, FailureOrdering,
4274 CSEMap.InsertNode(N, IP);
4275 AllNodes.push_back(N);
4276 return SDValue(N, 0);
4279 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4280 SDVTList VTList, ArrayRef<SDValue> Ops,
4281 MachineMemOperand *MMO,
4282 AtomicOrdering Ordering,
4283 SynchronizationScope SynchScope) {
4284 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4285 Ordering, SynchScope);
4288 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4289 SDValue Chain, SDValue Ptr, SDValue Cmp,
4290 SDValue Swp, MachinePointerInfo PtrInfo,
4292 AtomicOrdering SuccessOrdering,
4293 AtomicOrdering FailureOrdering,
4294 SynchronizationScope SynchScope) {
4295 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4296 Alignment = getEVTAlignment(MemVT);
4298 MachineFunction &MF = getMachineFunction();
4300 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4301 // For now, atomics are considered to be volatile always.
4302 // FIXME: Volatile isn't really correct; we should keep track of atomic
4303 // orderings in the memoperand.
4304 unsigned Flags = MachineMemOperand::MOVolatile;
4305 if (Opcode != ISD::ATOMIC_STORE)
4306 Flags |= MachineMemOperand::MOLoad;
4307 if (Opcode != ISD::ATOMIC_LOAD)
4308 Flags |= MachineMemOperand::MOStore;
4310 MachineMemOperand *MMO =
4311 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4313 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4314 SuccessOrdering, FailureOrdering, SynchScope);
4317 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4319 SDValue Ptr, SDValue Cmp,
4320 SDValue Swp, MachineMemOperand *MMO,
4321 AtomicOrdering SuccessOrdering,
4322 AtomicOrdering FailureOrdering,
4323 SynchronizationScope SynchScope) {
4324 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4325 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4327 EVT VT = Cmp.getValueType();
4329 SDVTList VTs = getVTList(VT, MVT::Other);
4330 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4331 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4332 FailureOrdering, SynchScope);
4335 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4337 SDValue Ptr, SDValue Val,
4338 const Value* PtrVal,
4340 AtomicOrdering Ordering,
4341 SynchronizationScope SynchScope) {
4342 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4343 Alignment = getEVTAlignment(MemVT);
4345 MachineFunction &MF = getMachineFunction();
4346 // An atomic store does not load. An atomic load does not store.
4347 // (An atomicrmw obviously both loads and stores.)
4348 // For now, atomics are considered to be volatile always, and they are
4350 // FIXME: Volatile isn't really correct; we should keep track of atomic
4351 // orderings in the memoperand.
4352 unsigned Flags = MachineMemOperand::MOVolatile;
4353 if (Opcode != ISD::ATOMIC_STORE)
4354 Flags |= MachineMemOperand::MOLoad;
4355 if (Opcode != ISD::ATOMIC_LOAD)
4356 Flags |= MachineMemOperand::MOStore;
4358 MachineMemOperand *MMO =
4359 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4360 MemVT.getStoreSize(), Alignment);
4362 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4363 Ordering, SynchScope);
4366 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4368 SDValue Ptr, SDValue Val,
4369 MachineMemOperand *MMO,
4370 AtomicOrdering Ordering,
4371 SynchronizationScope SynchScope) {
4372 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4373 Opcode == ISD::ATOMIC_LOAD_SUB ||
4374 Opcode == ISD::ATOMIC_LOAD_AND ||
4375 Opcode == ISD::ATOMIC_LOAD_OR ||
4376 Opcode == ISD::ATOMIC_LOAD_XOR ||
4377 Opcode == ISD::ATOMIC_LOAD_NAND ||
4378 Opcode == ISD::ATOMIC_LOAD_MIN ||
4379 Opcode == ISD::ATOMIC_LOAD_MAX ||
4380 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4381 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4382 Opcode == ISD::ATOMIC_SWAP ||
4383 Opcode == ISD::ATOMIC_STORE) &&
4384 "Invalid Atomic Op");
4386 EVT VT = Val.getValueType();
4388 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4389 getVTList(VT, MVT::Other);
4390 SDValue Ops[] = {Chain, Ptr, Val};
4391 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4394 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4395 EVT VT, SDValue Chain,
4397 MachineMemOperand *MMO,
4398 AtomicOrdering Ordering,
4399 SynchronizationScope SynchScope) {
4400 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4402 SDVTList VTs = getVTList(VT, MVT::Other);
4403 SDValue Ops[] = {Chain, Ptr};
4404 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4407 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4408 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4409 if (Ops.size() == 1)
4412 SmallVector<EVT, 4> VTs;
4413 VTs.reserve(Ops.size());
4414 for (unsigned i = 0; i < Ops.size(); ++i)
4415 VTs.push_back(Ops[i].getValueType());
4416 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4420 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4421 ArrayRef<SDValue> Ops,
4422 EVT MemVT, MachinePointerInfo PtrInfo,
4423 unsigned Align, bool Vol,
4424 bool ReadMem, bool WriteMem) {
4425 if (Align == 0) // Ensure that codegen never sees alignment 0
4426 Align = getEVTAlignment(MemVT);
4428 MachineFunction &MF = getMachineFunction();
4431 Flags |= MachineMemOperand::MOStore;
4433 Flags |= MachineMemOperand::MOLoad;
4435 Flags |= MachineMemOperand::MOVolatile;
4436 MachineMemOperand *MMO =
4437 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4439 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4443 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4444 ArrayRef<SDValue> Ops, EVT MemVT,
4445 MachineMemOperand *MMO) {
4446 assert((Opcode == ISD::INTRINSIC_VOID ||
4447 Opcode == ISD::INTRINSIC_W_CHAIN ||
4448 Opcode == ISD::PREFETCH ||
4449 Opcode == ISD::LIFETIME_START ||
4450 Opcode == ISD::LIFETIME_END ||
4451 (Opcode <= INT_MAX &&
4452 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4453 "Opcode is not a memory-accessing opcode!");
4455 // Memoize the node unless it returns a flag.
4456 MemIntrinsicSDNode *N;
4457 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4458 FoldingSetNodeID ID;
4459 AddNodeIDNode(ID, Opcode, VTList, Ops);
4460 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4462 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4463 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4464 return SDValue(E, 0);
4467 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4468 dl.getDebugLoc(), VTList, Ops,
4470 CSEMap.InsertNode(N, IP);
4472 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4473 dl.getDebugLoc(), VTList, Ops,
4476 AllNodes.push_back(N);
4477 return SDValue(N, 0);
4480 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4481 /// MachinePointerInfo record from it. This is particularly useful because the
4482 /// code generator has many cases where it doesn't bother passing in a
4483 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4484 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4485 // If this is FI+Offset, we can model it.
4486 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4487 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4489 // If this is (FI+Offset1)+Offset2, we can model it.
4490 if (Ptr.getOpcode() != ISD::ADD ||
4491 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4492 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4493 return MachinePointerInfo();
4495 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4496 return MachinePointerInfo::getFixedStack(FI, Offset+
4497 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4500 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4501 /// MachinePointerInfo record from it. This is particularly useful because the
4502 /// code generator has many cases where it doesn't bother passing in a
4503 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4504 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4505 // If the 'Offset' value isn't a constant, we can't handle this.
4506 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4507 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4508 if (OffsetOp.getOpcode() == ISD::UNDEF)
4509 return InferPointerInfo(Ptr);
4510 return MachinePointerInfo();
4515 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4516 EVT VT, SDLoc dl, SDValue Chain,
4517 SDValue Ptr, SDValue Offset,
4518 MachinePointerInfo PtrInfo, EVT MemVT,
4519 bool isVolatile, bool isNonTemporal, bool isInvariant,
4520 unsigned Alignment, const MDNode *TBAAInfo,
4521 const MDNode *Ranges) {
4522 assert(Chain.getValueType() == MVT::Other &&
4523 "Invalid chain type");
4524 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4525 Alignment = getEVTAlignment(VT);
4527 unsigned Flags = MachineMemOperand::MOLoad;
4529 Flags |= MachineMemOperand::MOVolatile;
4531 Flags |= MachineMemOperand::MONonTemporal;
4533 Flags |= MachineMemOperand::MOInvariant;
4535 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4537 if (PtrInfo.V.isNull())
4538 PtrInfo = InferPointerInfo(Ptr, Offset);
4540 MachineFunction &MF = getMachineFunction();
4541 MachineMemOperand *MMO =
4542 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4544 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4548 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4549 EVT VT, SDLoc dl, SDValue Chain,
4550 SDValue Ptr, SDValue Offset, EVT MemVT,
4551 MachineMemOperand *MMO) {
4553 ExtType = ISD::NON_EXTLOAD;
4554 } else if (ExtType == ISD::NON_EXTLOAD) {
4555 assert(VT == MemVT && "Non-extending load from different memory type!");
4558 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4559 "Should only be an extending load, not truncating!");
4560 assert(VT.isInteger() == MemVT.isInteger() &&
4561 "Cannot convert from FP to Int or Int -> FP!");
4562 assert(VT.isVector() == MemVT.isVector() &&
4563 "Cannot use trunc store to convert to or from a vector!");
4564 assert((!VT.isVector() ||
4565 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4566 "Cannot use trunc store to change the number of vector elements!");
4569 bool Indexed = AM != ISD::UNINDEXED;
4570 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4571 "Unindexed load with an offset!");
4573 SDVTList VTs = Indexed ?
4574 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4575 SDValue Ops[] = { Chain, Ptr, Offset };
4576 FoldingSetNodeID ID;
4577 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4578 ID.AddInteger(MemVT.getRawBits());
4579 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4580 MMO->isNonTemporal(),
4581 MMO->isInvariant()));
4582 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4584 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4585 cast<LoadSDNode>(E)->refineAlignment(MMO);
4586 return SDValue(E, 0);
4588 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4589 dl.getDebugLoc(), VTs, AM, ExtType,
4591 CSEMap.InsertNode(N, IP);
4592 AllNodes.push_back(N);
4593 return SDValue(N, 0);
4596 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4597 SDValue Chain, SDValue Ptr,
4598 MachinePointerInfo PtrInfo,
4599 bool isVolatile, bool isNonTemporal,
4600 bool isInvariant, unsigned Alignment,
4601 const MDNode *TBAAInfo,
4602 const MDNode *Ranges) {
4603 SDValue Undef = getUNDEF(Ptr.getValueType());
4604 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4605 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4609 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4610 SDValue Chain, SDValue Ptr,
4611 MachineMemOperand *MMO) {
4612 SDValue Undef = getUNDEF(Ptr.getValueType());
4613 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4617 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4618 SDValue Chain, SDValue Ptr,
4619 MachinePointerInfo PtrInfo, EVT MemVT,
4620 bool isVolatile, bool isNonTemporal,
4621 unsigned Alignment, const MDNode *TBAAInfo) {
4622 SDValue Undef = getUNDEF(Ptr.getValueType());
4623 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4624 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4629 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4630 SDValue Chain, SDValue Ptr, EVT MemVT,
4631 MachineMemOperand *MMO) {
4632 SDValue Undef = getUNDEF(Ptr.getValueType());
4633 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4638 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4639 SDValue Offset, ISD::MemIndexedMode AM) {
4640 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4641 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4642 "Load is already a indexed load!");
4643 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4644 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4645 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4646 false, LD->getAlignment());
4649 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4650 SDValue Ptr, MachinePointerInfo PtrInfo,
4651 bool isVolatile, bool isNonTemporal,
4652 unsigned Alignment, const MDNode *TBAAInfo) {
4653 assert(Chain.getValueType() == MVT::Other &&
4654 "Invalid chain type");
4655 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4656 Alignment = getEVTAlignment(Val.getValueType());
4658 unsigned Flags = MachineMemOperand::MOStore;
4660 Flags |= MachineMemOperand::MOVolatile;
4662 Flags |= MachineMemOperand::MONonTemporal;
4664 if (PtrInfo.V.isNull())
4665 PtrInfo = InferPointerInfo(Ptr);
4667 MachineFunction &MF = getMachineFunction();
4668 MachineMemOperand *MMO =
4669 MF.getMachineMemOperand(PtrInfo, Flags,
4670 Val.getValueType().getStoreSize(), Alignment,
4673 return getStore(Chain, dl, Val, Ptr, MMO);
4676 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4677 SDValue Ptr, MachineMemOperand *MMO) {
4678 assert(Chain.getValueType() == MVT::Other &&
4679 "Invalid chain type");
4680 EVT VT = Val.getValueType();
4681 SDVTList VTs = getVTList(MVT::Other);
4682 SDValue Undef = getUNDEF(Ptr.getValueType());
4683 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4684 FoldingSetNodeID ID;
4685 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4686 ID.AddInteger(VT.getRawBits());
4687 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4688 MMO->isNonTemporal(), MMO->isInvariant()));
4689 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4691 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4692 cast<StoreSDNode>(E)->refineAlignment(MMO);
4693 return SDValue(E, 0);
4695 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4696 dl.getDebugLoc(), VTs,
4697 ISD::UNINDEXED, false, VT, MMO);
4698 CSEMap.InsertNode(N, IP);
4699 AllNodes.push_back(N);
4700 return SDValue(N, 0);
4703 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4704 SDValue Ptr, MachinePointerInfo PtrInfo,
4705 EVT SVT,bool isVolatile, bool isNonTemporal,
4707 const MDNode *TBAAInfo) {
4708 assert(Chain.getValueType() == MVT::Other &&
4709 "Invalid chain type");
4710 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4711 Alignment = getEVTAlignment(SVT);
4713 unsigned Flags = MachineMemOperand::MOStore;
4715 Flags |= MachineMemOperand::MOVolatile;
4717 Flags |= MachineMemOperand::MONonTemporal;
4719 if (PtrInfo.V.isNull())
4720 PtrInfo = InferPointerInfo(Ptr);
4722 MachineFunction &MF = getMachineFunction();
4723 MachineMemOperand *MMO =
4724 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4727 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4730 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4731 SDValue Ptr, EVT SVT,
4732 MachineMemOperand *MMO) {
4733 EVT VT = Val.getValueType();
4735 assert(Chain.getValueType() == MVT::Other &&
4736 "Invalid chain type");
4738 return getStore(Chain, dl, Val, Ptr, MMO);
4740 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4741 "Should only be a truncating store, not extending!");
4742 assert(VT.isInteger() == SVT.isInteger() &&
4743 "Can't do FP-INT conversion!");
4744 assert(VT.isVector() == SVT.isVector() &&
4745 "Cannot use trunc store to convert to or from a vector!");
4746 assert((!VT.isVector() ||
4747 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4748 "Cannot use trunc store to change the number of vector elements!");
4750 SDVTList VTs = getVTList(MVT::Other);
4751 SDValue Undef = getUNDEF(Ptr.getValueType());
4752 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4753 FoldingSetNodeID ID;
4754 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4755 ID.AddInteger(SVT.getRawBits());
4756 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4757 MMO->isNonTemporal(), MMO->isInvariant()));
4758 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4760 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4761 cast<StoreSDNode>(E)->refineAlignment(MMO);
4762 return SDValue(E, 0);
4764 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4765 dl.getDebugLoc(), VTs,
4766 ISD::UNINDEXED, true, SVT, MMO);
4767 CSEMap.InsertNode(N, IP);
4768 AllNodes.push_back(N);
4769 return SDValue(N, 0);
4773 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4774 SDValue Offset, ISD::MemIndexedMode AM) {
4775 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4776 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4777 "Store is already a indexed store!");
4778 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4779 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4780 FoldingSetNodeID ID;
4781 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4782 ID.AddInteger(ST->getMemoryVT().getRawBits());
4783 ID.AddInteger(ST->getRawSubclassData());
4784 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4786 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4787 return SDValue(E, 0);
4789 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4790 dl.getDebugLoc(), VTs, AM,
4791 ST->isTruncatingStore(),
4793 ST->getMemOperand());
4794 CSEMap.InsertNode(N, IP);
4795 AllNodes.push_back(N);
4796 return SDValue(N, 0);
4799 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4800 SDValue Chain, SDValue Ptr,
4803 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4804 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4807 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4808 ArrayRef<SDUse> Ops) {
4809 switch (Ops.size()) {
4810 case 0: return getNode(Opcode, DL, VT);
4811 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4812 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4813 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4817 // Copy from an SDUse array into an SDValue array for use with
4818 // the regular getNode logic.
4819 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4820 return getNode(Opcode, DL, VT, NewOps);
4823 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4824 ArrayRef<SDValue> Ops) {
4825 unsigned NumOps = Ops.size();
4827 case 0: return getNode(Opcode, DL, VT);
4828 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4829 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4830 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4836 case ISD::SELECT_CC: {
4837 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4838 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4839 "LHS and RHS of condition must have same type!");
4840 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4841 "True and False arms of SelectCC must have same type!");
4842 assert(Ops[2].getValueType() == VT &&
4843 "select_cc node must be of same type as true and false value!");
4847 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4848 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4849 "LHS/RHS of comparison should match types!");
4856 SDVTList VTs = getVTList(VT);
4858 if (VT != MVT::Glue) {
4859 FoldingSetNodeID ID;
4860 AddNodeIDNode(ID, Opcode, VTs, Ops);
4863 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4864 return SDValue(E, 0);
4866 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4868 CSEMap.InsertNode(N, IP);
4870 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4874 AllNodes.push_back(N);
4878 return SDValue(N, 0);
4881 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4882 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4883 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4886 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4887 ArrayRef<SDValue> Ops) {
4888 if (VTList.NumVTs == 1)
4889 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4893 // FIXME: figure out how to safely handle things like
4894 // int foo(int x) { return 1 << (x & 255); }
4895 // int bar() { return foo(256); }
4896 case ISD::SRA_PARTS:
4897 case ISD::SRL_PARTS:
4898 case ISD::SHL_PARTS:
4899 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4900 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4901 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4902 else if (N3.getOpcode() == ISD::AND)
4903 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4904 // If the and is only masking out bits that cannot effect the shift,
4905 // eliminate the and.
4906 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4907 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4908 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4914 // Memoize the node unless it returns a flag.
4916 unsigned NumOps = Ops.size();
4917 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4918 FoldingSetNodeID ID;
4919 AddNodeIDNode(ID, Opcode, VTList, Ops);
4921 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4922 return SDValue(E, 0);
4925 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4926 DL.getDebugLoc(), VTList, Ops[0]);
4927 } else if (NumOps == 2) {
4928 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4929 DL.getDebugLoc(), VTList, Ops[0],
4931 } else if (NumOps == 3) {
4932 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4933 DL.getDebugLoc(), VTList, Ops[0],
4936 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4939 CSEMap.InsertNode(N, IP);
4942 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4943 DL.getDebugLoc(), VTList, Ops[0]);
4944 } else if (NumOps == 2) {
4945 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4946 DL.getDebugLoc(), VTList, Ops[0],
4948 } else if (NumOps == 3) {
4949 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4950 DL.getDebugLoc(), VTList, Ops[0],
4953 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4957 AllNodes.push_back(N);
4961 return SDValue(N, 0);
4964 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4965 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4968 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4970 SDValue Ops[] = { N1 };
4971 return getNode(Opcode, DL, VTList, Ops);
4974 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4975 SDValue N1, SDValue N2) {
4976 SDValue Ops[] = { N1, N2 };
4977 return getNode(Opcode, DL, VTList, Ops);
4980 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4981 SDValue N1, SDValue N2, SDValue N3) {
4982 SDValue Ops[] = { N1, N2, N3 };
4983 return getNode(Opcode, DL, VTList, Ops);
4986 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4987 SDValue N1, SDValue N2, SDValue N3,
4989 SDValue Ops[] = { N1, N2, N3, N4 };
4990 return getNode(Opcode, DL, VTList, Ops);
4993 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4994 SDValue N1, SDValue N2, SDValue N3,
4995 SDValue N4, SDValue N5) {
4996 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4997 return getNode(Opcode, DL, VTList, Ops);
5000 SDVTList SelectionDAG::getVTList(EVT VT) {
5001 return makeVTList(SDNode::getValueTypeList(VT), 1);
5004 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5005 FoldingSetNodeID ID;
5007 ID.AddInteger(VT1.getRawBits());
5008 ID.AddInteger(VT2.getRawBits());
5011 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5013 EVT *Array = Allocator.Allocate<EVT>(2);
5016 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5017 VTListMap.InsertNode(Result, IP);
5019 return Result->getSDVTList();
5022 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5023 FoldingSetNodeID ID;
5025 ID.AddInteger(VT1.getRawBits());
5026 ID.AddInteger(VT2.getRawBits());
5027 ID.AddInteger(VT3.getRawBits());
5030 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5032 EVT *Array = Allocator.Allocate<EVT>(3);
5036 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5037 VTListMap.InsertNode(Result, IP);
5039 return Result->getSDVTList();
5042 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5043 FoldingSetNodeID ID;
5045 ID.AddInteger(VT1.getRawBits());
5046 ID.AddInteger(VT2.getRawBits());
5047 ID.AddInteger(VT3.getRawBits());
5048 ID.AddInteger(VT4.getRawBits());
5051 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5053 EVT *Array = Allocator.Allocate<EVT>(4);
5058 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5059 VTListMap.InsertNode(Result, IP);
5061 return Result->getSDVTList();
5064 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5065 unsigned NumVTs = VTs.size();
5066 FoldingSetNodeID ID;
5067 ID.AddInteger(NumVTs);
5068 for (unsigned index = 0; index < NumVTs; index++) {
5069 ID.AddInteger(VTs[index].getRawBits());
5073 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5075 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5076 std::copy(VTs.begin(), VTs.end(), Array);
5077 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5078 VTListMap.InsertNode(Result, IP);
5080 return Result->getSDVTList();
5084 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5085 /// specified operands. If the resultant node already exists in the DAG,
5086 /// this does not modify the specified node, instead it returns the node that
5087 /// already exists. If the resultant node does not exist in the DAG, the
5088 /// input node is returned. As a degenerate case, if you specify the same
5089 /// input operands as the node already has, the input node is returned.
5090 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5091 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5093 // Check to see if there is no change.
5094 if (Op == N->getOperand(0)) return N;
5096 // See if the modified node already exists.
5097 void *InsertPos = nullptr;
5098 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5101 // Nope it doesn't. Remove the node from its current place in the maps.
5103 if (!RemoveNodeFromCSEMaps(N))
5104 InsertPos = nullptr;
5106 // Now we update the operands.
5107 N->OperandList[0].set(Op);
5109 // If this gets put into a CSE map, add it.
5110 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5114 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5115 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5117 // Check to see if there is no change.
5118 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5119 return N; // No operands changed, just return the input node.
5121 // See if the modified node already exists.
5122 void *InsertPos = nullptr;
5123 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5126 // Nope it doesn't. Remove the node from its current place in the maps.
5128 if (!RemoveNodeFromCSEMaps(N))
5129 InsertPos = nullptr;
5131 // Now we update the operands.
5132 if (N->OperandList[0] != Op1)
5133 N->OperandList[0].set(Op1);
5134 if (N->OperandList[1] != Op2)
5135 N->OperandList[1].set(Op2);
5137 // If this gets put into a CSE map, add it.
5138 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5142 SDNode *SelectionDAG::
5143 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5144 SDValue Ops[] = { Op1, Op2, Op3 };
5145 return UpdateNodeOperands(N, Ops);
5148 SDNode *SelectionDAG::
5149 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5150 SDValue Op3, SDValue Op4) {
5151 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5152 return UpdateNodeOperands(N, Ops);
5155 SDNode *SelectionDAG::
5156 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5157 SDValue Op3, SDValue Op4, SDValue Op5) {
5158 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5159 return UpdateNodeOperands(N, Ops);
5162 SDNode *SelectionDAG::
5163 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5164 unsigned NumOps = Ops.size();
5165 assert(N->getNumOperands() == NumOps &&
5166 "Update with wrong number of operands");
5168 // Check to see if there is no change.
5169 bool AnyChange = false;
5170 for (unsigned i = 0; i != NumOps; ++i) {
5171 if (Ops[i] != N->getOperand(i)) {
5177 // No operands changed, just return the input node.
5178 if (!AnyChange) return N;
5180 // See if the modified node already exists.
5181 void *InsertPos = nullptr;
5182 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5185 // Nope it doesn't. Remove the node from its current place in the maps.
5187 if (!RemoveNodeFromCSEMaps(N))
5188 InsertPos = nullptr;
5190 // Now we update the operands.
5191 for (unsigned i = 0; i != NumOps; ++i)
5192 if (N->OperandList[i] != Ops[i])
5193 N->OperandList[i].set(Ops[i]);
5195 // If this gets put into a CSE map, add it.
5196 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5200 /// DropOperands - Release the operands and set this node to have
5202 void SDNode::DropOperands() {
5203 // Unlike the code in MorphNodeTo that does this, we don't need to
5204 // watch for dead nodes here.
5205 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5211 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5214 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5216 SDVTList VTs = getVTList(VT);
5217 return SelectNodeTo(N, MachineOpc, VTs, None);
5220 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5221 EVT VT, SDValue Op1) {
5222 SDVTList VTs = getVTList(VT);
5223 SDValue Ops[] = { Op1 };
5224 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5227 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5228 EVT VT, SDValue Op1,
5230 SDVTList VTs = getVTList(VT);
5231 SDValue Ops[] = { Op1, Op2 };
5232 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5235 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5236 EVT VT, SDValue Op1,
5237 SDValue Op2, SDValue Op3) {
5238 SDVTList VTs = getVTList(VT);
5239 SDValue Ops[] = { Op1, Op2, Op3 };
5240 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5243 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5244 EVT VT, ArrayRef<SDValue> Ops) {
5245 SDVTList VTs = getVTList(VT);
5246 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5249 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5250 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5251 SDVTList VTs = getVTList(VT1, VT2);
5252 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5255 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5257 SDVTList VTs = getVTList(VT1, VT2);
5258 return SelectNodeTo(N, MachineOpc, VTs, None);
5261 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5262 EVT VT1, EVT VT2, EVT VT3,
5263 ArrayRef<SDValue> Ops) {
5264 SDVTList VTs = getVTList(VT1, VT2, VT3);
5265 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5268 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5269 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5270 ArrayRef<SDValue> Ops) {
5271 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5272 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5275 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5278 SDVTList VTs = getVTList(VT1, VT2);
5279 SDValue Ops[] = { Op1 };
5280 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5285 SDValue Op1, SDValue Op2) {
5286 SDVTList VTs = getVTList(VT1, VT2);
5287 SDValue Ops[] = { Op1, Op2 };
5288 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5291 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 SDValue Op1, SDValue Op2,
5295 SDVTList VTs = getVTList(VT1, VT2);
5296 SDValue Ops[] = { Op1, Op2, Op3 };
5297 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5300 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5301 EVT VT1, EVT VT2, EVT VT3,
5302 SDValue Op1, SDValue Op2,
5304 SDVTList VTs = getVTList(VT1, VT2, VT3);
5305 SDValue Ops[] = { Op1, Op2, Op3 };
5306 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5309 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5310 SDVTList VTs,ArrayRef<SDValue> Ops) {
5311 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5312 // Reset the NodeID to -1.
5317 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5318 /// the line number information on the merged node since it is not possible to
5319 /// preserve the information that operation is associated with multiple lines.
5320 /// This will make the debugger working better at -O0, were there is a higher
5321 /// probability having other instructions associated with that line.
5323 /// For IROrder, we keep the smaller of the two
5324 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5325 DebugLoc NLoc = N->getDebugLoc();
5326 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5327 (OLoc.getDebugLoc() != NLoc)) {
5328 N->setDebugLoc(DebugLoc());
5330 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5331 N->setIROrder(Order);
5335 /// MorphNodeTo - This *mutates* the specified node to have the specified
5336 /// return type, opcode, and operands.
5338 /// Note that MorphNodeTo returns the resultant node. If there is already a
5339 /// node of the specified opcode and operands, it returns that node instead of
5340 /// the current one. Note that the SDLoc need not be the same.
5342 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5343 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5344 /// node, and because it doesn't require CSE recalculation for any of
5345 /// the node's users.
5347 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5348 SDVTList VTs, ArrayRef<SDValue> Ops) {
5349 unsigned NumOps = Ops.size();
5350 // If an identical node already exists, use it.
5352 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5353 FoldingSetNodeID ID;
5354 AddNodeIDNode(ID, Opc, VTs, Ops);
5355 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5356 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5359 if (!RemoveNodeFromCSEMaps(N))
5362 // Start the morphing.
5364 N->ValueList = VTs.VTs;
5365 N->NumValues = VTs.NumVTs;
5367 // Clear the operands list, updating used nodes to remove this from their
5368 // use list. Keep track of any operands that become dead as a result.
5369 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5370 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5372 SDNode *Used = Use.getNode();
5374 if (Used->use_empty())
5375 DeadNodeSet.insert(Used);
5378 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5379 // Initialize the memory references information.
5380 MN->setMemRefs(nullptr, nullptr);
5381 // If NumOps is larger than the # of operands we can have in a
5382 // MachineSDNode, reallocate the operand list.
5383 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5384 if (MN->OperandsNeedDelete)
5385 delete[] MN->OperandList;
5386 if (NumOps > array_lengthof(MN->LocalOperands))
5387 // We're creating a final node that will live unmorphed for the
5388 // remainder of the current SelectionDAG iteration, so we can allocate
5389 // the operands directly out of a pool with no recycling metadata.
5390 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5391 Ops.data(), NumOps);
5393 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5394 MN->OperandsNeedDelete = false;
5396 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5398 // If NumOps is larger than the # of operands we currently have, reallocate
5399 // the operand list.
5400 if (NumOps > N->NumOperands) {
5401 if (N->OperandsNeedDelete)
5402 delete[] N->OperandList;
5403 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5404 N->OperandsNeedDelete = true;
5406 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5409 // Delete any nodes that are still dead after adding the uses for the
5411 if (!DeadNodeSet.empty()) {
5412 SmallVector<SDNode *, 16> DeadNodes;
5413 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5414 E = DeadNodeSet.end(); I != E; ++I)
5415 if ((*I)->use_empty())
5416 DeadNodes.push_back(*I);
5417 RemoveDeadNodes(DeadNodes);
5421 CSEMap.InsertNode(N, IP); // Memoize the new node.
5426 /// getMachineNode - These are used for target selectors to create a new node
5427 /// with specified return type(s), MachineInstr opcode, and operands.
5429 /// Note that getMachineNode returns the resultant node. If there is already a
5430 /// node of the specified opcode and operands, it returns that node instead of
5431 /// the current one.
5433 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5434 SDVTList VTs = getVTList(VT);
5435 return getMachineNode(Opcode, dl, VTs, None);
5439 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5440 SDVTList VTs = getVTList(VT);
5441 SDValue Ops[] = { Op1 };
5442 return getMachineNode(Opcode, dl, VTs, Ops);
5446 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5447 SDValue Op1, SDValue Op2) {
5448 SDVTList VTs = getVTList(VT);
5449 SDValue Ops[] = { Op1, Op2 };
5450 return getMachineNode(Opcode, dl, VTs, Ops);
5454 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5455 SDValue Op1, SDValue Op2, SDValue Op3) {
5456 SDVTList VTs = getVTList(VT);
5457 SDValue Ops[] = { Op1, Op2, Op3 };
5458 return getMachineNode(Opcode, dl, VTs, Ops);
5462 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5463 ArrayRef<SDValue> Ops) {
5464 SDVTList VTs = getVTList(VT);
5465 return getMachineNode(Opcode, dl, VTs, Ops);
5469 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5470 SDVTList VTs = getVTList(VT1, VT2);
5471 return getMachineNode(Opcode, dl, VTs, None);
5475 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5476 EVT VT1, EVT VT2, SDValue Op1) {
5477 SDVTList VTs = getVTList(VT1, VT2);
5478 SDValue Ops[] = { Op1 };
5479 return getMachineNode(Opcode, dl, VTs, Ops);
5483 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5484 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5485 SDVTList VTs = getVTList(VT1, VT2);
5486 SDValue Ops[] = { Op1, Op2 };
5487 return getMachineNode(Opcode, dl, VTs, Ops);
5491 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5492 EVT VT1, EVT VT2, SDValue Op1,
5493 SDValue Op2, SDValue Op3) {
5494 SDVTList VTs = getVTList(VT1, VT2);
5495 SDValue Ops[] = { Op1, Op2, Op3 };
5496 return getMachineNode(Opcode, dl, VTs, Ops);
5500 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5502 ArrayRef<SDValue> Ops) {
5503 SDVTList VTs = getVTList(VT1, VT2);
5504 return getMachineNode(Opcode, dl, VTs, Ops);
5508 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5509 EVT VT1, EVT VT2, EVT VT3,
5510 SDValue Op1, SDValue Op2) {
5511 SDVTList VTs = getVTList(VT1, VT2, VT3);
5512 SDValue Ops[] = { Op1, Op2 };
5513 return getMachineNode(Opcode, dl, VTs, Ops);
5517 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5518 EVT VT1, EVT VT2, EVT VT3,
5519 SDValue Op1, SDValue Op2, SDValue Op3) {
5520 SDVTList VTs = getVTList(VT1, VT2, VT3);
5521 SDValue Ops[] = { Op1, Op2, Op3 };
5522 return getMachineNode(Opcode, dl, VTs, Ops);
5526 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5527 EVT VT1, EVT VT2, EVT VT3,
5528 ArrayRef<SDValue> Ops) {
5529 SDVTList VTs = getVTList(VT1, VT2, VT3);
5530 return getMachineNode(Opcode, dl, VTs, Ops);
5534 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5535 EVT VT2, EVT VT3, EVT VT4,
5536 ArrayRef<SDValue> Ops) {
5537 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5538 return getMachineNode(Opcode, dl, VTs, Ops);
5542 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5543 ArrayRef<EVT> ResultTys,
5544 ArrayRef<SDValue> Ops) {
5545 SDVTList VTs = getVTList(ResultTys);
5546 return getMachineNode(Opcode, dl, VTs, Ops);
5550 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5551 ArrayRef<SDValue> OpsArray) {
5552 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5555 const SDValue *Ops = OpsArray.data();
5556 unsigned NumOps = OpsArray.size();
5559 FoldingSetNodeID ID;
5560 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5562 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5563 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5567 // Allocate a new MachineSDNode.
5568 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5569 DL.getDebugLoc(), VTs);
5571 // Initialize the operands list.
5572 if (NumOps > array_lengthof(N->LocalOperands))
5573 // We're creating a final node that will live unmorphed for the
5574 // remainder of the current SelectionDAG iteration, so we can allocate
5575 // the operands directly out of a pool with no recycling metadata.
5576 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5579 N->InitOperands(N->LocalOperands, Ops, NumOps);
5580 N->OperandsNeedDelete = false;
5583 CSEMap.InsertNode(N, IP);
5585 AllNodes.push_back(N);
5587 VerifyMachineNode(N);
5592 /// getTargetExtractSubreg - A convenience function for creating
5593 /// TargetOpcode::EXTRACT_SUBREG nodes.
5595 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5597 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5598 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5599 VT, Operand, SRIdxVal);
5600 return SDValue(Subreg, 0);
5603 /// getTargetInsertSubreg - A convenience function for creating
5604 /// TargetOpcode::INSERT_SUBREG nodes.
5606 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5607 SDValue Operand, SDValue Subreg) {
5608 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5609 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5610 VT, Operand, Subreg, SRIdxVal);
5611 return SDValue(Result, 0);
5614 /// getNodeIfExists - Get the specified node if it's already available, or
5615 /// else return NULL.
5616 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5617 ArrayRef<SDValue> Ops) {
5618 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5619 FoldingSetNodeID ID;
5620 AddNodeIDNode(ID, Opcode, VTList, Ops);
5622 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5628 /// getDbgValue - Creates a SDDbgValue node.
5632 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5633 bool IsIndirect, uint64_t Off,
5634 DebugLoc DL, unsigned O) {
5635 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5640 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5642 DebugLoc DL, unsigned O) {
5643 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5648 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5649 DebugLoc DL, unsigned O) {
5650 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5655 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5656 /// pointed to by a use iterator is deleted, increment the use iterator
5657 /// so that it doesn't dangle.
5659 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5660 SDNode::use_iterator &UI;
5661 SDNode::use_iterator &UE;
5663 void NodeDeleted(SDNode *N, SDNode *E) override {
5664 // Increment the iterator as needed.
5665 while (UI != UE && N == *UI)
5670 RAUWUpdateListener(SelectionDAG &d,
5671 SDNode::use_iterator &ui,
5672 SDNode::use_iterator &ue)
5673 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5678 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5679 /// This can cause recursive merging of nodes in the DAG.
5681 /// This version assumes From has a single result value.
5683 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5684 SDNode *From = FromN.getNode();
5685 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5686 "Cannot replace with this method!");
5687 assert(From != To.getNode() && "Cannot replace uses of with self");
5689 // Iterate over all the existing uses of From. New uses will be added
5690 // to the beginning of the use list, which we avoid visiting.
5691 // This specifically avoids visiting uses of From that arise while the
5692 // replacement is happening, because any such uses would be the result
5693 // of CSE: If an existing node looks like From after one of its operands
5694 // is replaced by To, we don't want to replace of all its users with To
5695 // too. See PR3018 for more info.
5696 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5697 RAUWUpdateListener Listener(*this, UI, UE);
5701 // This node is about to morph, remove its old self from the CSE maps.
5702 RemoveNodeFromCSEMaps(User);
5704 // A user can appear in a use list multiple times, and when this
5705 // happens the uses are usually next to each other in the list.
5706 // To help reduce the number of CSE recomputations, process all
5707 // the uses of this user that we can find this way.
5709 SDUse &Use = UI.getUse();
5712 } while (UI != UE && *UI == User);
5714 // Now that we have modified User, add it back to the CSE maps. If it
5715 // already exists there, recursively merge the results together.
5716 AddModifiedNodeToCSEMaps(User);
5719 // If we just RAUW'd the root, take note.
5720 if (FromN == getRoot())
5724 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5725 /// This can cause recursive merging of nodes in the DAG.
5727 /// This version assumes that for each value of From, there is a
5728 /// corresponding value in To in the same position with the same type.
5730 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5732 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5733 assert((!From->hasAnyUseOfValue(i) ||
5734 From->getValueType(i) == To->getValueType(i)) &&
5735 "Cannot use this version of ReplaceAllUsesWith!");
5738 // Handle the trivial case.
5742 // Iterate over just the existing users of From. See the comments in
5743 // the ReplaceAllUsesWith above.
5744 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5745 RAUWUpdateListener Listener(*this, UI, UE);
5749 // This node is about to morph, remove its old self from the CSE maps.
5750 RemoveNodeFromCSEMaps(User);
5752 // A user can appear in a use list multiple times, and when this
5753 // happens the uses are usually next to each other in the list.
5754 // To help reduce the number of CSE recomputations, process all
5755 // the uses of this user that we can find this way.
5757 SDUse &Use = UI.getUse();
5760 } while (UI != UE && *UI == User);
5762 // Now that we have modified User, add it back to the CSE maps. If it
5763 // already exists there, recursively merge the results together.
5764 AddModifiedNodeToCSEMaps(User);
5767 // If we just RAUW'd the root, take note.
5768 if (From == getRoot().getNode())
5769 setRoot(SDValue(To, getRoot().getResNo()));
5772 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5773 /// This can cause recursive merging of nodes in the DAG.
5775 /// This version can replace From with any result values. To must match the
5776 /// number and types of values returned by From.
5777 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5778 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5779 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5781 // Iterate over just the existing users of From. See the comments in
5782 // the ReplaceAllUsesWith above.
5783 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5784 RAUWUpdateListener Listener(*this, UI, UE);
5788 // This node is about to morph, remove its old self from the CSE maps.
5789 RemoveNodeFromCSEMaps(User);
5791 // A user can appear in a use list multiple times, and when this
5792 // happens the uses are usually next to each other in the list.
5793 // To help reduce the number of CSE recomputations, process all
5794 // the uses of this user that we can find this way.
5796 SDUse &Use = UI.getUse();
5797 const SDValue &ToOp = To[Use.getResNo()];
5800 } while (UI != UE && *UI == User);
5802 // Now that we have modified User, add it back to the CSE maps. If it
5803 // already exists there, recursively merge the results together.
5804 AddModifiedNodeToCSEMaps(User);
5807 // If we just RAUW'd the root, take note.
5808 if (From == getRoot().getNode())
5809 setRoot(SDValue(To[getRoot().getResNo()]));
5812 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5813 /// uses of other values produced by From.getNode() alone. The Deleted
5814 /// vector is handled the same way as for ReplaceAllUsesWith.
5815 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5816 // Handle the really simple, really trivial case efficiently.
5817 if (From == To) return;
5819 // Handle the simple, trivial, case efficiently.
5820 if (From.getNode()->getNumValues() == 1) {
5821 ReplaceAllUsesWith(From, To);
5825 // Iterate over just the existing users of From. See the comments in
5826 // the ReplaceAllUsesWith above.
5827 SDNode::use_iterator UI = From.getNode()->use_begin(),
5828 UE = From.getNode()->use_end();
5829 RAUWUpdateListener Listener(*this, UI, UE);
5832 bool UserRemovedFromCSEMaps = false;
5834 // A user can appear in a use list multiple times, and when this
5835 // happens the uses are usually next to each other in the list.
5836 // To help reduce the number of CSE recomputations, process all
5837 // the uses of this user that we can find this way.
5839 SDUse &Use = UI.getUse();
5841 // Skip uses of different values from the same node.
5842 if (Use.getResNo() != From.getResNo()) {
5847 // If this node hasn't been modified yet, it's still in the CSE maps,
5848 // so remove its old self from the CSE maps.
5849 if (!UserRemovedFromCSEMaps) {
5850 RemoveNodeFromCSEMaps(User);
5851 UserRemovedFromCSEMaps = true;
5856 } while (UI != UE && *UI == User);
5858 // We are iterating over all uses of the From node, so if a use
5859 // doesn't use the specific value, no changes are made.
5860 if (!UserRemovedFromCSEMaps)
5863 // Now that we have modified User, add it back to the CSE maps. If it
5864 // already exists there, recursively merge the results together.
5865 AddModifiedNodeToCSEMaps(User);
5868 // If we just RAUW'd the root, take note.
5869 if (From == getRoot())
5874 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5875 /// to record information about a use.
5882 /// operator< - Sort Memos by User.
5883 bool operator<(const UseMemo &L, const UseMemo &R) {
5884 return (intptr_t)L.User < (intptr_t)R.User;
5888 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5889 /// uses of other values produced by From.getNode() alone. The same value
5890 /// may appear in both the From and To list. The Deleted vector is
5891 /// handled the same way as for ReplaceAllUsesWith.
5892 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5895 // Handle the simple, trivial case efficiently.
5897 return ReplaceAllUsesOfValueWith(*From, *To);
5899 // Read up all the uses and make records of them. This helps
5900 // processing new uses that are introduced during the
5901 // replacement process.
5902 SmallVector<UseMemo, 4> Uses;
5903 for (unsigned i = 0; i != Num; ++i) {
5904 unsigned FromResNo = From[i].getResNo();
5905 SDNode *FromNode = From[i].getNode();
5906 for (SDNode::use_iterator UI = FromNode->use_begin(),
5907 E = FromNode->use_end(); UI != E; ++UI) {
5908 SDUse &Use = UI.getUse();
5909 if (Use.getResNo() == FromResNo) {
5910 UseMemo Memo = { *UI, i, &Use };
5911 Uses.push_back(Memo);
5916 // Sort the uses, so that all the uses from a given User are together.
5917 std::sort(Uses.begin(), Uses.end());
5919 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5920 UseIndex != UseIndexEnd; ) {
5921 // We know that this user uses some value of From. If it is the right
5922 // value, update it.
5923 SDNode *User = Uses[UseIndex].User;
5925 // This node is about to morph, remove its old self from the CSE maps.
5926 RemoveNodeFromCSEMaps(User);
5928 // The Uses array is sorted, so all the uses for a given User
5929 // are next to each other in the list.
5930 // To help reduce the number of CSE recomputations, process all
5931 // the uses of this user that we can find this way.
5933 unsigned i = Uses[UseIndex].Index;
5934 SDUse &Use = *Uses[UseIndex].Use;
5938 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5940 // Now that we have modified User, add it back to the CSE maps. If it
5941 // already exists there, recursively merge the results together.
5942 AddModifiedNodeToCSEMaps(User);
5946 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5947 /// based on their topological order. It returns the maximum id and a vector
5948 /// of the SDNodes* in assigned order by reference.
5949 unsigned SelectionDAG::AssignTopologicalOrder() {
5951 unsigned DAGSize = 0;
5953 // SortedPos tracks the progress of the algorithm. Nodes before it are
5954 // sorted, nodes after it are unsorted. When the algorithm completes
5955 // it is at the end of the list.
5956 allnodes_iterator SortedPos = allnodes_begin();
5958 // Visit all the nodes. Move nodes with no operands to the front of
5959 // the list immediately. Annotate nodes that do have operands with their
5960 // operand count. Before we do this, the Node Id fields of the nodes
5961 // may contain arbitrary values. After, the Node Id fields for nodes
5962 // before SortedPos will contain the topological sort index, and the
5963 // Node Id fields for nodes At SortedPos and after will contain the
5964 // count of outstanding operands.
5965 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5968 unsigned Degree = N->getNumOperands();
5970 // A node with no uses, add it to the result array immediately.
5971 N->setNodeId(DAGSize++);
5972 allnodes_iterator Q = N;
5974 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5975 assert(SortedPos != AllNodes.end() && "Overran node list");
5978 // Temporarily use the Node Id as scratch space for the degree count.
5979 N->setNodeId(Degree);
5983 // Visit all the nodes. As we iterate, move nodes into sorted order,
5984 // such that by the time the end is reached all nodes will be sorted.
5985 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5988 // N is in sorted position, so all its uses have one less operand
5989 // that needs to be sorted.
5990 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5993 unsigned Degree = P->getNodeId();
5994 assert(Degree != 0 && "Invalid node degree");
5997 // All of P's operands are sorted, so P may sorted now.
5998 P->setNodeId(DAGSize++);
6000 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6001 assert(SortedPos != AllNodes.end() && "Overran node list");
6004 // Update P's outstanding operand count.
6005 P->setNodeId(Degree);
6008 if (I == SortedPos) {
6011 dbgs() << "Overran sorted position:\n";
6014 llvm_unreachable(nullptr);
6018 assert(SortedPos == AllNodes.end() &&
6019 "Topological sort incomplete!");
6020 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6021 "First node in topological sort is not the entry token!");
6022 assert(AllNodes.front().getNodeId() == 0 &&
6023 "First node in topological sort has non-zero id!");
6024 assert(AllNodes.front().getNumOperands() == 0 &&
6025 "First node in topological sort has operands!");
6026 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6027 "Last node in topologic sort has unexpected id!");
6028 assert(AllNodes.back().use_empty() &&
6029 "Last node in topologic sort has users!");
6030 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6034 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6035 /// value is produced by SD.
6036 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6037 DbgInfo->add(DB, SD, isParameter);
6039 SD->setHasDebugValue(true);
6042 /// TransferDbgValues - Transfer SDDbgValues.
6043 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6044 if (From == To || !From.getNode()->getHasDebugValue())
6046 SDNode *FromNode = From.getNode();
6047 SDNode *ToNode = To.getNode();
6048 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6049 SmallVector<SDDbgValue *, 2> ClonedDVs;
6050 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6052 SDDbgValue *Dbg = *I;
6053 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6054 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6056 Dbg->getOffset(), Dbg->getDebugLoc(),
6058 ClonedDVs.push_back(Clone);
6061 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6062 E = ClonedDVs.end(); I != E; ++I)
6063 AddDbgValue(*I, ToNode, false);
6066 //===----------------------------------------------------------------------===//
6068 //===----------------------------------------------------------------------===//
6070 HandleSDNode::~HandleSDNode() {
6074 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6075 DebugLoc DL, const GlobalValue *GA,
6076 EVT VT, int64_t o, unsigned char TF)
6077 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6081 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6082 SDValue X, unsigned SrcAS,
6084 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6085 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6087 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6088 EVT memvt, MachineMemOperand *mmo)
6089 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6090 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6091 MMO->isNonTemporal(), MMO->isInvariant());
6092 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6093 assert(isNonTemporal() == MMO->isNonTemporal() &&
6094 "Non-temporal encoding error!");
6095 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6098 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6099 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6100 : SDNode(Opc, Order, dl, VTs, Ops),
6101 MemoryVT(memvt), MMO(mmo) {
6102 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6103 MMO->isNonTemporal(), MMO->isInvariant());
6104 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6105 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6108 /// Profile - Gather unique data for the node.
6110 void SDNode::Profile(FoldingSetNodeID &ID) const {
6111 AddNodeIDNode(ID, this);
6116 std::vector<EVT> VTs;
6119 VTs.reserve(MVT::LAST_VALUETYPE);
6120 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6121 VTs.push_back(MVT((MVT::SimpleValueType)i));
6126 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6127 static ManagedStatic<EVTArray> SimpleVTArray;
6128 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6130 /// getValueTypeList - Return a pointer to the specified value type.
6132 const EVT *SDNode::getValueTypeList(EVT VT) {
6133 if (VT.isExtended()) {
6134 sys::SmartScopedLock<true> Lock(*VTMutex);
6135 return &(*EVTs->insert(VT).first);
6137 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6138 "Value type out of range!");
6139 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6143 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6144 /// indicated value. This method ignores uses of other values defined by this
6146 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6147 assert(Value < getNumValues() && "Bad value!");
6149 // TODO: Only iterate over uses of a given value of the node
6150 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6151 if (UI.getUse().getResNo() == Value) {
6158 // Found exactly the right number of uses?
6163 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6164 /// value. This method ignores uses of other values defined by this operation.
6165 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6166 assert(Value < getNumValues() && "Bad value!");
6168 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6169 if (UI.getUse().getResNo() == Value)
6176 /// isOnlyUserOf - Return true if this node is the only use of N.
6178 bool SDNode::isOnlyUserOf(SDNode *N) const {
6180 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6191 /// isOperand - Return true if this node is an operand of N.
6193 bool SDValue::isOperandOf(SDNode *N) const {
6194 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6195 if (*this == N->getOperand(i))
6200 bool SDNode::isOperandOf(SDNode *N) const {
6201 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6202 if (this == N->OperandList[i].getNode())
6207 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6208 /// be a chain) reaches the specified operand without crossing any
6209 /// side-effecting instructions on any chain path. In practice, this looks
6210 /// through token factors and non-volatile loads. In order to remain efficient,
6211 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6212 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6213 unsigned Depth) const {
6214 if (*this == Dest) return true;
6216 // Don't search too deeply, we just want to be able to see through
6217 // TokenFactor's etc.
6218 if (Depth == 0) return false;
6220 // If this is a token factor, all inputs to the TF happen in parallel. If any
6221 // of the operands of the TF does not reach dest, then we cannot do the xform.
6222 if (getOpcode() == ISD::TokenFactor) {
6223 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6224 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6229 // Loads don't have side effects, look through them.
6230 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6231 if (!Ld->isVolatile())
6232 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6237 /// hasPredecessor - Return true if N is a predecessor of this node.
6238 /// N is either an operand of this node, or can be reached by recursively
6239 /// traversing up the operands.
6240 /// NOTE: This is an expensive method. Use it carefully.
6241 bool SDNode::hasPredecessor(const SDNode *N) const {
6242 SmallPtrSet<const SDNode *, 32> Visited;
6243 SmallVector<const SDNode *, 16> Worklist;
6244 return hasPredecessorHelper(N, Visited, Worklist);
6248 SDNode::hasPredecessorHelper(const SDNode *N,
6249 SmallPtrSet<const SDNode *, 32> &Visited,
6250 SmallVectorImpl<const SDNode *> &Worklist) const {
6251 if (Visited.empty()) {
6252 Worklist.push_back(this);
6254 // Take a look in the visited set. If we've already encountered this node
6255 // we needn't search further.
6256 if (Visited.count(N))
6260 // Haven't visited N yet. Continue the search.
6261 while (!Worklist.empty()) {
6262 const SDNode *M = Worklist.pop_back_val();
6263 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6264 SDNode *Op = M->getOperand(i).getNode();
6265 if (Visited.insert(Op))
6266 Worklist.push_back(Op);
6275 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6276 assert(Num < NumOperands && "Invalid child # of SDNode!");
6277 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6280 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6281 assert(N->getNumValues() == 1 &&
6282 "Can't unroll a vector with multiple results!");
6284 EVT VT = N->getValueType(0);
6285 unsigned NE = VT.getVectorNumElements();
6286 EVT EltVT = VT.getVectorElementType();
6289 SmallVector<SDValue, 8> Scalars;
6290 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6292 // If ResNE is 0, fully unroll the vector op.
6295 else if (NE > ResNE)
6299 for (i= 0; i != NE; ++i) {
6300 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6301 SDValue Operand = N->getOperand(j);
6302 EVT OperandVT = Operand.getValueType();
6303 if (OperandVT.isVector()) {
6304 // A vector operand; extract a single element.
6305 const TargetLowering *TLI = TM.getTargetLowering();
6306 EVT OperandEltVT = OperandVT.getVectorElementType();
6307 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6310 getConstant(i, TLI->getVectorIdxTy()));
6312 // A scalar operand; just use it as is.
6313 Operands[j] = Operand;
6317 switch (N->getOpcode()) {
6319 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6322 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6329 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6330 getShiftAmountOperand(Operands[0].getValueType(),
6333 case ISD::SIGN_EXTEND_INREG:
6334 case ISD::FP_ROUND_INREG: {
6335 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6336 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6338 getValueType(ExtVT)));
6343 for (; i < ResNE; ++i)
6344 Scalars.push_back(getUNDEF(EltVT));
6346 return getNode(ISD::BUILD_VECTOR, dl,
6347 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6351 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6352 /// location that is 'Dist' units away from the location that the 'Base' load
6353 /// is loading from.
6354 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6355 unsigned Bytes, int Dist) const {
6356 if (LD->getChain() != Base->getChain())
6358 EVT VT = LD->getValueType(0);
6359 if (VT.getSizeInBits() / 8 != Bytes)
6362 SDValue Loc = LD->getOperand(1);
6363 SDValue BaseLoc = Base->getOperand(1);
6364 if (Loc.getOpcode() == ISD::FrameIndex) {
6365 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6367 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6368 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6369 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6370 int FS = MFI->getObjectSize(FI);
6371 int BFS = MFI->getObjectSize(BFI);
6372 if (FS != BFS || FS != (int)Bytes) return false;
6373 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6377 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6378 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6381 const GlobalValue *GV1 = nullptr;
6382 const GlobalValue *GV2 = nullptr;
6383 int64_t Offset1 = 0;
6384 int64_t Offset2 = 0;
6385 const TargetLowering *TLI = TM.getTargetLowering();
6386 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6387 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6388 if (isGA1 && isGA2 && GV1 == GV2)
6389 return Offset1 == (Offset2 + Dist*Bytes);
6394 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6395 /// it cannot be inferred.
6396 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6397 // If this is a GlobalAddress + cst, return the alignment.
6398 const GlobalValue *GV;
6399 int64_t GVOffset = 0;
6400 const TargetLowering *TLI = TM.getTargetLowering();
6401 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6402 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6403 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6404 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6405 TLI->getDataLayout());
6406 unsigned AlignBits = KnownZero.countTrailingOnes();
6407 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6409 return MinAlign(Align, GVOffset);
6412 // If this is a direct reference to a stack slot, use information about the
6413 // stack slot's alignment.
6414 int FrameIdx = 1 << 31;
6415 int64_t FrameOffset = 0;
6416 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6417 FrameIdx = FI->getIndex();
6418 } else if (isBaseWithConstantOffset(Ptr) &&
6419 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6421 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6422 FrameOffset = Ptr.getConstantOperandVal(1);
6425 if (FrameIdx != (1 << 31)) {
6426 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6427 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6435 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6436 /// which is split (or expanded) into two not necessarily identical pieces.
6437 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6438 // Currently all types are split in half.
6440 if (!VT.isVector()) {
6441 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6443 unsigned NumElements = VT.getVectorNumElements();
6444 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6445 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6448 return std::make_pair(LoVT, HiVT);
6451 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6453 std::pair<SDValue, SDValue>
6454 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6456 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6457 N.getValueType().getVectorNumElements() &&
6458 "More vector elements requested than available!");
6460 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6461 getConstant(0, TLI->getVectorIdxTy()));
6462 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6463 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6464 return std::make_pair(Lo, Hi);
6467 void SelectionDAG::ExtractVectorElements(SDValue Op,
6468 SmallVectorImpl<SDValue> &Args,
6469 unsigned Start, unsigned Count) {
6470 EVT VT = Op.getValueType();
6472 Count = VT.getVectorNumElements();
6474 EVT EltVT = VT.getVectorElementType();
6475 EVT IdxTy = TLI->getVectorIdxTy();
6477 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6478 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6479 Op, getConstant(i, IdxTy)));
6483 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6484 unsigned GlobalAddressSDNode::getAddressSpace() const {
6485 return getGlobal()->getType()->getAddressSpace();
6489 Type *ConstantPoolSDNode::getType() const {
6490 if (isMachineConstantPoolEntry())
6491 return Val.MachineCPVal->getType();
6492 return Val.ConstVal->getType();
6495 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6497 unsigned &SplatBitSize,
6499 unsigned MinSplatBits,
6500 bool isBigEndian) const {
6501 EVT VT = getValueType(0);
6502 assert(VT.isVector() && "Expected a vector type");
6503 unsigned sz = VT.getSizeInBits();
6504 if (MinSplatBits > sz)
6507 SplatValue = APInt(sz, 0);
6508 SplatUndef = APInt(sz, 0);
6510 // Get the bits. Bits with undefined values (when the corresponding element
6511 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6512 // in SplatValue. If any of the values are not constant, give up and return
6514 unsigned int nOps = getNumOperands();
6515 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6516 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6518 for (unsigned j = 0; j < nOps; ++j) {
6519 unsigned i = isBigEndian ? nOps-1-j : j;
6520 SDValue OpVal = getOperand(i);
6521 unsigned BitPos = j * EltBitSize;
6523 if (OpVal.getOpcode() == ISD::UNDEF)
6524 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6525 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6526 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6527 zextOrTrunc(sz) << BitPos;
6528 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6529 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6534 // The build_vector is all constants or undefs. Find the smallest element
6535 // size that splats the vector.
6537 HasAnyUndefs = (SplatUndef != 0);
6540 unsigned HalfSize = sz / 2;
6541 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6542 APInt LowValue = SplatValue.trunc(HalfSize);
6543 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6544 APInt LowUndef = SplatUndef.trunc(HalfSize);
6546 // If the two halves do not match (ignoring undef bits), stop here.
6547 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6548 MinSplatBits > HalfSize)
6551 SplatValue = HighValue | LowValue;
6552 SplatUndef = HighUndef & LowUndef;
6561 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6562 SDValue Op0 = getOperand(0);
6563 if (Op0.getOpcode() != ISD::Constant)
6566 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6567 if (getOperand(i) != Op0)
6570 return cast<ConstantSDNode>(Op0);
6573 bool BuildVectorSDNode::isConstant() const {
6574 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6575 unsigned Opc = getOperand(i).getOpcode();
6576 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6582 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6583 // Find the first non-undef value in the shuffle mask.
6585 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6588 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6590 // Make sure all remaining elements are either undef or the same as the first
6592 for (int Idx = Mask[i]; i != e; ++i)
6593 if (Mask[i] >= 0 && Mask[i] != Idx)
6599 static void checkForCyclesHelper(const SDNode *N,
6600 SmallPtrSet<const SDNode*, 32> &Visited,
6601 SmallPtrSet<const SDNode*, 32> &Checked) {
6602 // If this node has already been checked, don't check it again.
6603 if (Checked.count(N))
6606 // If a node has already been visited on this depth-first walk, reject it as
6608 if (!Visited.insert(N)) {
6609 dbgs() << "Offending node:\n";
6611 errs() << "Detected cycle in SelectionDAG\n";
6615 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6616 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6623 void llvm::checkForCycles(const llvm::SDNode *N) {
6625 assert(N && "Checking nonexistent SDNode");
6626 SmallPtrSet<const SDNode*, 32> visited;
6627 SmallPtrSet<const SDNode*, 32> checked;
6628 checkForCyclesHelper(N, visited, checked);
6632 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6633 checkForCycles(DAG->getRoot().getNode());