1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
53 /// makeVTList - Return an instance of the SDVTList struct initialized with the
54 /// specified members.
55 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
56 SDVTList Res = {VTs, NumVTs};
60 // Default null implementations of the callbacks.
61 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
62 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
64 //===----------------------------------------------------------------------===//
65 // ConstantFPSDNode Class
66 //===----------------------------------------------------------------------===//
68 /// isExactlyValue - We don't rely on operator== working on double values, as
69 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
70 /// As such, this method can be used to do an exact bit-for-bit comparison of
71 /// two floating point values.
72 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
73 return getValueAPF().bitwiseIsEqual(V);
76 bool ConstantFPSDNode::isValueValidForType(EVT VT,
78 assert(VT.isFloatingPoint() && "Can only convert between FP types");
80 // convert modifies in place, so make a copy.
81 APFloat Val2 = APFloat(Val);
83 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
84 APFloat::rmNearestTiesToEven,
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 /// isBuildVectorAllOnes - Return true if the specified node is a
94 /// BUILD_VECTOR where all of the elements are ~0 or undef.
95 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96 // Look through a bit convert.
97 if (N->getOpcode() == ISD::BITCAST)
98 N = N->getOperand(0).getNode();
100 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
102 unsigned i = 0, e = N->getNumOperands();
104 // Skip over all of the undef values.
105 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 // Do not accept an all-undef vector.
109 if (i == e) return false;
111 // Do not accept build_vectors that aren't all constants or which have non-~0
112 // elements. We have to be a bit careful here, as the type of the constant
113 // may not be the same as the type of the vector elements due to type
114 // legalization (the elements are promoted to a legal type for the target and
115 // a vector of a type may be legal when the base element type is not).
116 // We only want to check enough bits to cover the vector elements, because
117 // we care if the resultant vector is all ones, not whether the individual
119 SDValue NotZero = N->getOperand(i);
120 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
121 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
122 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
124 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
125 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
130 // Okay, we have at least one ~0 value, check to see if the rest match or are
131 // undefs. Even with the above element type twiddling, this should be OK, as
132 // the same type legalization should have applied to all the elements.
133 for (++i; i != e; ++i)
134 if (N->getOperand(i) != NotZero &&
135 N->getOperand(i).getOpcode() != ISD::UNDEF)
141 /// isBuildVectorAllZeros - Return true if the specified node is a
142 /// BUILD_VECTOR where all of the elements are 0 or undef.
143 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
144 // Look through a bit convert.
145 if (N->getOpcode() == ISD::BITCAST)
146 N = N->getOperand(0).getNode();
148 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
150 unsigned i = 0, e = N->getNumOperands();
152 // Skip over all of the undef values.
153 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept an all-undef vector.
157 if (i == e) return false;
159 // Do not accept build_vectors that aren't all constants or which have non-0
161 SDValue Zero = N->getOperand(i);
162 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
163 if (!CN->isNullValue())
165 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
166 if (!CFPN->getValueAPF().isPosZero())
171 // Okay, we have at least one 0 value, check to see if the rest match or are
173 for (++i; i != e; ++i)
174 if (N->getOperand(i) != Zero &&
175 N->getOperand(i).getOpcode() != ISD::UNDEF)
180 /// \brief Return true if the specified node is a BUILD_VECTOR node of
181 /// all ConstantSDNode or undef.
182 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
183 if (N->getOpcode() != ISD::BUILD_VECTOR)
186 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
187 SDValue Op = N->getOperand(i);
188 if (Op.getOpcode() == ISD::UNDEF)
190 if (!isa<ConstantSDNode>(Op))
196 /// isScalarToVector - Return true if the specified node is a
197 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
198 /// element is not an undef.
199 bool ISD::isScalarToVector(const SDNode *N) {
200 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
207 unsigned NumElems = N->getNumOperands();
210 for (unsigned i = 1; i < NumElems; ++i) {
211 SDValue V = N->getOperand(i);
212 if (V.getOpcode() != ISD::UNDEF)
218 /// allOperandsUndef - Return true if the node has at least one operand
219 /// and all operands of the specified node are ISD::UNDEF.
220 bool ISD::allOperandsUndef(const SDNode *N) {
221 // Return false if the node has no operands.
222 // This is "logically inconsistent" with the definition of "all" but
223 // is probably the desired behavior.
224 if (N->getNumOperands() == 0)
227 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
228 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
234 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
237 return ISD::ANY_EXTEND;
239 return ISD::SIGN_EXTEND;
241 return ISD::ZERO_EXTEND;
246 llvm_unreachable("Invalid LoadExtType");
249 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
250 /// when given the operation for (X op Y).
251 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
252 // To perform this operation, we just need to swap the L and G bits of the
254 unsigned OldL = (Operation >> 2) & 1;
255 unsigned OldG = (Operation >> 1) & 1;
256 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
257 (OldL << 1) | // New G bit
258 (OldG << 2)); // New L bit.
261 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
262 /// 'op' is a valid SetCC operation.
263 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
264 unsigned Operation = Op;
266 Operation ^= 7; // Flip L, G, E bits, but not U.
268 Operation ^= 15; // Flip all of the condition bits.
270 if (Operation > ISD::SETTRUE2)
271 Operation &= ~8; // Don't let N and U bits get set.
273 return ISD::CondCode(Operation);
277 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
278 /// signed operation and 2 if the result is an unsigned comparison. Return zero
279 /// if the operation does not depend on the sign of the input (setne and seteq).
280 static int isSignedOp(ISD::CondCode Opcode) {
282 default: llvm_unreachable("Illegal integer setcc operation!");
284 case ISD::SETNE: return 0;
288 case ISD::SETGE: return 1;
292 case ISD::SETUGE: return 2;
296 /// getSetCCOrOperation - Return the result of a logical OR between different
297 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
298 /// returns SETCC_INVALID if it is not possible to represent the resultant
300 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
302 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
303 // Cannot fold a signed integer setcc with an unsigned integer setcc.
304 return ISD::SETCC_INVALID;
306 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
308 // If the N and U bits get set then the resultant comparison DOES suddenly
309 // care about orderedness, and is true when ordered.
310 if (Op > ISD::SETTRUE2)
311 Op &= ~16; // Clear the U bit if the N bit is set.
313 // Canonicalize illegal integer setcc's.
314 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
317 return ISD::CondCode(Op);
320 /// getSetCCAndOperation - Return the result of a logical AND between different
321 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
322 /// function returns zero if it is not possible to represent the resultant
324 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
326 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
327 // Cannot fold a signed setcc with an unsigned setcc.
328 return ISD::SETCC_INVALID;
330 // Combine all of the condition bits.
331 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
333 // Canonicalize illegal integer setcc's.
337 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
338 case ISD::SETOEQ: // SETEQ & SETU[LG]E
339 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
340 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
341 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
348 //===----------------------------------------------------------------------===//
349 // SDNode Profile Support
350 //===----------------------------------------------------------------------===//
352 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
354 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
359 /// solely with their pointer.
360 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
361 ID.AddPointer(VTList.VTs);
364 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
366 static void AddNodeIDOperands(FoldingSetNodeID &ID,
367 ArrayRef<SDValue> Ops) {
368 for (auto& Op : Ops) {
369 ID.AddPointer(Op.getNode());
370 ID.AddInteger(Op.getResNo());
374 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
376 static void AddNodeIDOperands(FoldingSetNodeID &ID,
377 ArrayRef<SDUse> Ops) {
378 for (auto& Op : Ops) {
379 ID.AddPointer(Op.getNode());
380 ID.AddInteger(Op.getResNo());
384 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
385 SDVTList VTList, ArrayRef<SDValue> OpList) {
386 AddNodeIDOpcode(ID, OpC);
387 AddNodeIDValueTypes(ID, VTList);
388 AddNodeIDOperands(ID, OpList);
391 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
393 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
394 switch (N->getOpcode()) {
395 case ISD::TargetExternalSymbol:
396 case ISD::ExternalSymbol:
397 llvm_unreachable("Should only be used on nodes with operands");
398 default: break; // Normal nodes don't need extra info.
399 case ISD::TargetConstant:
400 case ISD::Constant: {
401 const ConstantSDNode *C = cast<ConstantSDNode>(N);
402 ID.AddPointer(C->getConstantIntValue());
403 ID.AddBoolean(C->isOpaque());
406 case ISD::TargetConstantFP:
407 case ISD::ConstantFP: {
408 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
411 case ISD::TargetGlobalAddress:
412 case ISD::GlobalAddress:
413 case ISD::TargetGlobalTLSAddress:
414 case ISD::GlobalTLSAddress: {
415 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
416 ID.AddPointer(GA->getGlobal());
417 ID.AddInteger(GA->getOffset());
418 ID.AddInteger(GA->getTargetFlags());
419 ID.AddInteger(GA->getAddressSpace());
422 case ISD::BasicBlock:
423 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
426 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
428 case ISD::RegisterMask:
429 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
432 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
434 case ISD::FrameIndex:
435 case ISD::TargetFrameIndex:
436 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
439 case ISD::TargetJumpTable:
440 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
441 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
443 case ISD::ConstantPool:
444 case ISD::TargetConstantPool: {
445 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
446 ID.AddInteger(CP->getAlignment());
447 ID.AddInteger(CP->getOffset());
448 if (CP->isMachineConstantPoolEntry())
449 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
451 ID.AddPointer(CP->getConstVal());
452 ID.AddInteger(CP->getTargetFlags());
455 case ISD::TargetIndex: {
456 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
457 ID.AddInteger(TI->getIndex());
458 ID.AddInteger(TI->getOffset());
459 ID.AddInteger(TI->getTargetFlags());
463 const LoadSDNode *LD = cast<LoadSDNode>(N);
464 ID.AddInteger(LD->getMemoryVT().getRawBits());
465 ID.AddInteger(LD->getRawSubclassData());
466 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
470 const StoreSDNode *ST = cast<StoreSDNode>(N);
471 ID.AddInteger(ST->getMemoryVT().getRawBits());
472 ID.AddInteger(ST->getRawSubclassData());
473 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
476 case ISD::ATOMIC_CMP_SWAP:
477 case ISD::ATOMIC_SWAP:
478 case ISD::ATOMIC_LOAD_ADD:
479 case ISD::ATOMIC_LOAD_SUB:
480 case ISD::ATOMIC_LOAD_AND:
481 case ISD::ATOMIC_LOAD_OR:
482 case ISD::ATOMIC_LOAD_XOR:
483 case ISD::ATOMIC_LOAD_NAND:
484 case ISD::ATOMIC_LOAD_MIN:
485 case ISD::ATOMIC_LOAD_MAX:
486 case ISD::ATOMIC_LOAD_UMIN:
487 case ISD::ATOMIC_LOAD_UMAX:
488 case ISD::ATOMIC_LOAD:
489 case ISD::ATOMIC_STORE: {
490 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
491 ID.AddInteger(AT->getMemoryVT().getRawBits());
492 ID.AddInteger(AT->getRawSubclassData());
493 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
496 case ISD::PREFETCH: {
497 const MemSDNode *PF = cast<MemSDNode>(N);
498 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
501 case ISD::VECTOR_SHUFFLE: {
502 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
503 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
505 ID.AddInteger(SVN->getMaskElt(i));
508 case ISD::TargetBlockAddress:
509 case ISD::BlockAddress: {
510 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
511 ID.AddPointer(BA->getBlockAddress());
512 ID.AddInteger(BA->getOffset());
513 ID.AddInteger(BA->getTargetFlags());
516 } // end switch (N->getOpcode())
518 // Target specific memory nodes could also have address spaces to check.
519 if (N->isTargetMemoryOpcode())
520 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
523 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
525 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
526 AddNodeIDOpcode(ID, N->getOpcode());
527 // Add the return value info.
528 AddNodeIDValueTypes(ID, N->getVTList());
529 // Add the operand info.
530 AddNodeIDOperands(ID, makeArrayRef(N->op_begin(), N->op_end()));
532 // Handle SDNode leafs with special info.
533 AddNodeIDCustom(ID, N);
536 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
537 /// the CSE map that carries volatility, temporalness, indexing mode, and
538 /// extension/truncation information.
540 static inline unsigned
541 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
542 bool isNonTemporal, bool isInvariant) {
543 assert((ConvType & 3) == ConvType &&
544 "ConvType may not require more than 2 bits!");
545 assert((AM & 7) == AM &&
546 "AM may not require more than 3 bits!");
550 (isNonTemporal << 6) |
554 //===----------------------------------------------------------------------===//
555 // SelectionDAG Class
556 //===----------------------------------------------------------------------===//
558 /// doNotCSE - Return true if CSE should not be performed for this node.
559 static bool doNotCSE(SDNode *N) {
560 if (N->getValueType(0) == MVT::Glue)
561 return true; // Never CSE anything that produces a flag.
563 switch (N->getOpcode()) {
565 case ISD::HANDLENODE:
567 return true; // Never CSE these nodes.
570 // Check that remaining values produced are not flags.
571 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
572 if (N->getValueType(i) == MVT::Glue)
573 return true; // Never CSE anything that produces a flag.
578 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
580 void SelectionDAG::RemoveDeadNodes() {
581 // Create a dummy node (which is not added to allnodes), that adds a reference
582 // to the root node, preventing it from being deleted.
583 HandleSDNode Dummy(getRoot());
585 SmallVector<SDNode*, 128> DeadNodes;
587 // Add all obviously-dead nodes to the DeadNodes worklist.
588 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
590 DeadNodes.push_back(I);
592 RemoveDeadNodes(DeadNodes);
594 // If the root changed (e.g. it was a dead load, update the root).
595 setRoot(Dummy.getValue());
598 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
599 /// given list, and any nodes that become unreachable as a result.
600 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
602 // Process the worklist, deleting the nodes and adding their uses to the
604 while (!DeadNodes.empty()) {
605 SDNode *N = DeadNodes.pop_back_val();
607 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
608 DUL->NodeDeleted(N, nullptr);
610 // Take the node out of the appropriate CSE map.
611 RemoveNodeFromCSEMaps(N);
613 // Next, brutally remove the operand list. This is safe to do, as there are
614 // no cycles in the graph.
615 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
617 SDNode *Operand = Use.getNode();
620 // Now that we removed this operand, see if there are no uses of it left.
621 if (Operand->use_empty())
622 DeadNodes.push_back(Operand);
629 void SelectionDAG::RemoveDeadNode(SDNode *N){
630 SmallVector<SDNode*, 16> DeadNodes(1, N);
632 // Create a dummy node that adds a reference to the root node, preventing
633 // it from being deleted. (This matters if the root is an operand of the
635 HandleSDNode Dummy(getRoot());
637 RemoveDeadNodes(DeadNodes);
640 void SelectionDAG::DeleteNode(SDNode *N) {
641 // First take this out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Finally, remove uses due to operands of this node, remove from the
645 // AllNodes list, and delete the node.
646 DeleteNodeNotInCSEMaps(N);
649 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
650 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
651 assert(N->use_empty() && "Cannot delete a node that is not dead!");
653 // Drop all of the operands and decrement used node's use counts.
659 void SelectionDAG::DeallocateNode(SDNode *N) {
660 if (N->OperandsNeedDelete)
661 delete[] N->OperandList;
663 // Set the opcode to DELETED_NODE to help catch bugs when node
664 // memory is reallocated.
665 N->NodeType = ISD::DELETED_NODE;
667 NodeAllocator.Deallocate(AllNodes.remove(N));
669 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
670 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
671 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
672 DbgVals[i]->setIsInvalidated();
675 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
676 /// correspond to it. This is useful when we're about to delete or repurpose
677 /// the node. We don't want future request for structurally identical nodes
678 /// to return N anymore.
679 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
681 switch (N->getOpcode()) {
682 case ISD::HANDLENODE: return false; // noop.
684 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
685 "Cond code doesn't exist!");
686 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
687 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
689 case ISD::ExternalSymbol:
690 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
692 case ISD::TargetExternalSymbol: {
693 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
694 Erased = TargetExternalSymbols.erase(
695 std::pair<std::string,unsigned char>(ESN->getSymbol(),
696 ESN->getTargetFlags()));
699 case ISD::VALUETYPE: {
700 EVT VT = cast<VTSDNode>(N)->getVT();
701 if (VT.isExtended()) {
702 Erased = ExtendedValueTypeNodes.erase(VT);
704 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
705 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
710 // Remove it from the CSE Map.
711 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
712 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
713 Erased = CSEMap.RemoveNode(N);
717 // Verify that the node was actually in one of the CSE maps, unless it has a
718 // flag result (which cannot be CSE'd) or is one of the special cases that are
719 // not subject to CSE.
720 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
721 !N->isMachineOpcode() && !doNotCSE(N)) {
724 llvm_unreachable("Node is not in map!");
730 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
731 /// maps and modified in place. Add it back to the CSE maps, unless an identical
732 /// node already exists, in which case transfer all its users to the existing
733 /// node. This transfer can potentially trigger recursive merging.
736 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
737 // For node types that aren't CSE'd, just act as if no identical node
740 SDNode *Existing = CSEMap.GetOrInsertNode(N);
742 // If there was already an existing matching node, use ReplaceAllUsesWith
743 // to replace the dead one with the existing one. This can cause
744 // recursive merging of other unrelated nodes down the line.
745 ReplaceAllUsesWith(N, Existing);
747 // N is now dead. Inform the listeners and delete it.
748 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
749 DUL->NodeDeleted(N, Existing);
750 DeleteNodeNotInCSEMaps(N);
755 // If the node doesn't already exist, we updated it. Inform listeners.
756 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
760 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
761 /// were replaced with those specified. If this node is never memoized,
762 /// return null, otherwise return a pointer to the slot it would take. If a
763 /// node already exists with these operands, the slot will be non-null.
764 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
769 SDValue Ops[] = { Op };
771 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
772 AddNodeIDCustom(ID, N);
773 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
777 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
778 /// were replaced with those specified. If this node is never memoized,
779 /// return null, otherwise return a pointer to the slot it would take. If a
780 /// node already exists with these operands, the slot will be non-null.
781 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
782 SDValue Op1, SDValue Op2,
787 SDValue Ops[] = { Op1, Op2 };
789 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
790 AddNodeIDCustom(ID, N);
791 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
796 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
797 /// were replaced with those specified. If this node is never memoized,
798 /// return null, otherwise return a pointer to the slot it would take. If a
799 /// node already exists with these operands, the slot will be non-null.
800 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
806 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
807 AddNodeIDCustom(ID, N);
808 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
813 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
814 static void VerifyNodeCommon(SDNode *N) {
815 switch (N->getOpcode()) {
818 case ISD::BUILD_PAIR: {
819 EVT VT = N->getValueType(0);
820 assert(N->getNumValues() == 1 && "Too many results!");
821 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
822 "Wrong return type!");
823 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
824 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
825 "Mismatched operand types!");
826 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
827 "Wrong operand type!");
828 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
829 "Wrong return type size");
832 case ISD::BUILD_VECTOR: {
833 assert(N->getNumValues() == 1 && "Too many results!");
834 assert(N->getValueType(0).isVector() && "Wrong return type!");
835 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
836 "Wrong number of operands!");
837 EVT EltVT = N->getValueType(0).getVectorElementType();
838 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
839 assert((I->getValueType() == EltVT ||
840 (EltVT.isInteger() && I->getValueType().isInteger() &&
841 EltVT.bitsLE(I->getValueType()))) &&
842 "Wrong operand type!");
843 assert(I->getValueType() == N->getOperand(0).getValueType() &&
844 "Operands must all have the same type");
851 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
852 static void VerifySDNode(SDNode *N) {
853 // The SDNode allocators cannot be used to allocate nodes with fields that are
854 // not present in an SDNode!
855 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
856 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
857 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
858 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
859 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
860 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
861 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
862 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
863 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
864 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
865 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
866 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
867 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
868 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
869 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
870 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
871 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
872 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
873 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
878 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
880 static void VerifyMachineNode(SDNode *N) {
881 // The MachineNode allocators cannot be used to allocate nodes with fields
882 // that are not present in a MachineNode!
883 // Currently there are no such nodes.
889 /// getEVTAlignment - Compute the default alignment value for the
892 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
893 Type *Ty = VT == MVT::iPTR ?
894 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
895 VT.getTypeForEVT(*getContext());
897 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
900 // EntryNode could meaningfully have debug info if we can find it...
901 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
902 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
903 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
904 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
905 UpdateListeners(nullptr) {
906 AllNodes.push_back(&EntryNode);
907 DbgInfo = new SDDbgInfo();
910 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
913 Context = &mf.getFunction()->getContext();
916 SelectionDAG::~SelectionDAG() {
917 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
922 void SelectionDAG::allnodes_clear() {
923 assert(&*AllNodes.begin() == &EntryNode);
924 AllNodes.remove(AllNodes.begin());
925 while (!AllNodes.empty())
926 DeallocateNode(AllNodes.begin());
929 void SelectionDAG::clear() {
931 OperandAllocator.Reset();
934 ExtendedValueTypeNodes.clear();
935 ExternalSymbols.clear();
936 TargetExternalSymbols.clear();
937 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
938 static_cast<CondCodeSDNode*>(nullptr));
939 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
940 static_cast<SDNode*>(nullptr));
942 EntryNode.UseList = nullptr;
943 AllNodes.push_back(&EntryNode);
944 Root = getEntryNode();
948 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
949 return VT.bitsGT(Op.getValueType()) ?
950 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
951 getNode(ISD::TRUNCATE, DL, VT, Op);
954 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
955 return VT.bitsGT(Op.getValueType()) ?
956 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
957 getNode(ISD::TRUNCATE, DL, VT, Op);
960 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
961 return VT.bitsGT(Op.getValueType()) ?
962 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
963 getNode(ISD::TRUNCATE, DL, VT, Op);
966 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
967 if (VT.bitsLE(Op.getValueType()))
968 return getNode(ISD::TRUNCATE, SL, VT, Op);
970 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
971 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
974 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
975 assert(!VT.isVector() &&
976 "getZeroExtendInReg should use the vector element type instead of "
978 if (Op.getValueType() == VT) return Op;
979 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
980 APInt Imm = APInt::getLowBitsSet(BitWidth,
982 return getNode(ISD::AND, DL, Op.getValueType(), Op,
983 getConstant(Imm, Op.getValueType()));
986 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
988 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
989 EVT EltVT = VT.getScalarType();
991 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
992 return getNode(ISD::XOR, DL, VT, Val, NegOne);
995 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
996 EVT EltVT = VT.getScalarType();
998 switch (TLI->getBooleanContents(VT.isVector())) {
999 case TargetLowering::ZeroOrOneBooleanContent:
1000 case TargetLowering::UndefinedBooleanContent:
1001 TrueValue = getConstant(1, VT);
1003 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1004 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1008 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1011 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1012 EVT EltVT = VT.getScalarType();
1013 assert((EltVT.getSizeInBits() >= 64 ||
1014 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1015 "getConstant with a uint64_t value that doesn't fit in the type!");
1016 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1019 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1021 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1024 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1026 assert(VT.isInteger() && "Cannot create FP integer constant!");
1028 EVT EltVT = VT.getScalarType();
1029 const ConstantInt *Elt = &Val;
1031 const TargetLowering *TLI = TM.getTargetLowering();
1033 // In some cases the vector type is legal but the element type is illegal and
1034 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1035 // inserted value (the type does not need to match the vector element type).
1036 // Any extra bits introduced will be truncated away.
1037 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1038 TargetLowering::TypePromoteInteger) {
1039 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1040 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1041 Elt = ConstantInt::get(*getContext(), NewVal);
1043 // In other cases the element type is illegal and needs to be expanded, for
1044 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1045 // the value into n parts and use a vector type with n-times the elements.
1046 // Then bitcast to the type requested.
1047 // Legalizing constants too early makes the DAGCombiner's job harder so we
1048 // only legalize if the DAG tells us we must produce legal types.
1049 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1050 TLI->getTypeAction(*getContext(), EltVT) ==
1051 TargetLowering::TypeExpandInteger) {
1052 APInt NewVal = Elt->getValue();
1053 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1054 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1055 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1056 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1058 // Check the temporary vector is the correct size. If this fails then
1059 // getTypeToTransformTo() probably returned a type whose size (in bits)
1060 // isn't a power-of-2 factor of the requested type size.
1061 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1063 SmallVector<SDValue, 2> EltParts;
1064 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1065 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1066 .trunc(ViaEltSizeInBits),
1067 ViaEltVT, isT, isO));
1070 // EltParts is currently in little endian order. If we actually want
1071 // big-endian order then reverse it now.
1072 if (TLI->isBigEndian())
1073 std::reverse(EltParts.begin(), EltParts.end());
1075 // The elements must be reversed when the element order is different
1076 // to the endianness of the elements (because the BITCAST is itself a
1077 // vector shuffle in this situation). However, we do not need any code to
1078 // perform this reversal because getConstant() is producing a vector
1080 // This situation occurs in MIPS MSA.
1082 SmallVector<SDValue, 8> Ops;
1083 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1084 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1086 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1087 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1092 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1093 "APInt size does not match type size!");
1094 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1095 FoldingSetNodeID ID;
1096 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1100 SDNode *N = nullptr;
1101 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1103 return SDValue(N, 0);
1106 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1107 CSEMap.InsertNode(N, IP);
1108 AllNodes.push_back(N);
1111 SDValue Result(N, 0);
1112 if (VT.isVector()) {
1113 SmallVector<SDValue, 8> Ops;
1114 Ops.assign(VT.getVectorNumElements(), Result);
1115 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1120 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1121 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1125 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1126 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1129 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1130 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1132 EVT EltVT = VT.getScalarType();
1134 // Do the map lookup using the actual bit pattern for the floating point
1135 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1136 // we don't have issues with SNANs.
1137 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1138 FoldingSetNodeID ID;
1139 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1142 SDNode *N = nullptr;
1143 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1145 return SDValue(N, 0);
1148 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1149 CSEMap.InsertNode(N, IP);
1150 AllNodes.push_back(N);
1153 SDValue Result(N, 0);
1154 if (VT.isVector()) {
1155 SmallVector<SDValue, 8> Ops;
1156 Ops.assign(VT.getVectorNumElements(), Result);
1157 // FIXME SDLoc info might be appropriate here
1158 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1163 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1164 EVT EltVT = VT.getScalarType();
1165 if (EltVT==MVT::f32)
1166 return getConstantFP(APFloat((float)Val), VT, isTarget);
1167 else if (EltVT==MVT::f64)
1168 return getConstantFP(APFloat(Val), VT, isTarget);
1169 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1172 APFloat apf = APFloat(Val);
1173 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1175 return getConstantFP(apf, VT, isTarget);
1177 llvm_unreachable("Unsupported type in getConstantFP");
1180 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1181 EVT VT, int64_t Offset,
1183 unsigned char TargetFlags) {
1184 assert((TargetFlags == 0 || isTargetGA) &&
1185 "Cannot set target flags on target-independent globals");
1186 const TargetLowering *TLI = TM.getTargetLowering();
1188 // Truncate (with sign-extension) the offset value to the pointer size.
1189 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1191 Offset = SignExtend64(Offset, BitWidth);
1193 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1195 // If GV is an alias then use the aliasee for determining thread-localness.
1196 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1197 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1201 if (GVar && GVar->isThreadLocal())
1202 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1204 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1206 FoldingSetNodeID ID;
1207 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1209 ID.AddInteger(Offset);
1210 ID.AddInteger(TargetFlags);
1211 ID.AddInteger(GV->getType()->getAddressSpace());
1213 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1214 return SDValue(E, 0);
1216 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1217 DL.getDebugLoc(), GV, VT,
1218 Offset, TargetFlags);
1219 CSEMap.InsertNode(N, IP);
1220 AllNodes.push_back(N);
1221 return SDValue(N, 0);
1224 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1225 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1226 FoldingSetNodeID ID;
1227 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1230 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1231 return SDValue(E, 0);
1233 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1234 CSEMap.InsertNode(N, IP);
1235 AllNodes.push_back(N);
1236 return SDValue(N, 0);
1239 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1240 unsigned char TargetFlags) {
1241 assert((TargetFlags == 0 || isTarget) &&
1242 "Cannot set target flags on target-independent jump tables");
1243 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1244 FoldingSetNodeID ID;
1245 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1247 ID.AddInteger(TargetFlags);
1249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1250 return SDValue(E, 0);
1252 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1254 CSEMap.InsertNode(N, IP);
1255 AllNodes.push_back(N);
1256 return SDValue(N, 0);
1259 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1260 unsigned Alignment, int Offset,
1262 unsigned char TargetFlags) {
1263 assert((TargetFlags == 0 || isTarget) &&
1264 "Cannot set target flags on target-independent globals");
1267 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1268 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1269 FoldingSetNodeID ID;
1270 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1271 ID.AddInteger(Alignment);
1272 ID.AddInteger(Offset);
1274 ID.AddInteger(TargetFlags);
1276 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1277 return SDValue(E, 0);
1279 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1280 Alignment, TargetFlags);
1281 CSEMap.InsertNode(N, IP);
1282 AllNodes.push_back(N);
1283 return SDValue(N, 0);
1287 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1288 unsigned Alignment, int Offset,
1290 unsigned char TargetFlags) {
1291 assert((TargetFlags == 0 || isTarget) &&
1292 "Cannot set target flags on target-independent globals");
1295 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1296 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1297 FoldingSetNodeID ID;
1298 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1299 ID.AddInteger(Alignment);
1300 ID.AddInteger(Offset);
1301 C->addSelectionDAGCSEId(ID);
1302 ID.AddInteger(TargetFlags);
1304 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1305 return SDValue(E, 0);
1307 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1308 Alignment, TargetFlags);
1309 CSEMap.InsertNode(N, IP);
1310 AllNodes.push_back(N);
1311 return SDValue(N, 0);
1314 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1315 unsigned char TargetFlags) {
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1318 ID.AddInteger(Index);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1322 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1327 CSEMap.InsertNode(N, IP);
1328 AllNodes.push_back(N);
1329 return SDValue(N, 0);
1332 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1333 FoldingSetNodeID ID;
1334 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1337 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1338 return SDValue(E, 0);
1340 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1341 CSEMap.InsertNode(N, IP);
1342 AllNodes.push_back(N);
1343 return SDValue(N, 0);
1346 SDValue SelectionDAG::getValueType(EVT VT) {
1347 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1348 ValueTypeNodes.size())
1349 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1351 SDNode *&N = VT.isExtended() ?
1352 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1354 if (N) return SDValue(N, 0);
1355 N = new (NodeAllocator) VTSDNode(VT);
1356 AllNodes.push_back(N);
1357 return SDValue(N, 0);
1360 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1361 SDNode *&N = ExternalSymbols[Sym];
1362 if (N) return SDValue(N, 0);
1363 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1364 AllNodes.push_back(N);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1369 unsigned char TargetFlags) {
1371 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1373 if (N) return SDValue(N, 0);
1374 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1375 AllNodes.push_back(N);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1380 if ((unsigned)Cond >= CondCodeNodes.size())
1381 CondCodeNodes.resize(Cond+1);
1383 if (!CondCodeNodes[Cond]) {
1384 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1385 CondCodeNodes[Cond] = N;
1386 AllNodes.push_back(N);
1389 return SDValue(CondCodeNodes[Cond], 0);
1392 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1393 // the shuffle mask M that point at N1 to point at N2, and indices that point
1394 // N2 to point at N1.
1395 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1397 int NElts = M.size();
1398 for (int i = 0; i != NElts; ++i) {
1406 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1407 SDValue N2, const int *Mask) {
1408 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1409 "Invalid VECTOR_SHUFFLE");
1411 // Canonicalize shuffle undef, undef -> undef
1412 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1413 return getUNDEF(VT);
1415 // Validate that all indices in Mask are within the range of the elements
1416 // input to the shuffle.
1417 unsigned NElts = VT.getVectorNumElements();
1418 SmallVector<int, 8> MaskVec;
1419 for (unsigned i = 0; i != NElts; ++i) {
1420 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1421 MaskVec.push_back(Mask[i]);
1424 // Canonicalize shuffle v, v -> v, undef
1427 for (unsigned i = 0; i != NElts; ++i)
1428 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1431 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1432 if (N1.getOpcode() == ISD::UNDEF)
1433 commuteShuffle(N1, N2, MaskVec);
1435 // Canonicalize all index into lhs, -> shuffle lhs, undef
1436 // Canonicalize all index into rhs, -> shuffle rhs, undef
1437 bool AllLHS = true, AllRHS = true;
1438 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1439 for (unsigned i = 0; i != NElts; ++i) {
1440 if (MaskVec[i] >= (int)NElts) {
1445 } else if (MaskVec[i] >= 0) {
1449 if (AllLHS && AllRHS)
1450 return getUNDEF(VT);
1451 if (AllLHS && !N2Undef)
1455 commuteShuffle(N1, N2, MaskVec);
1458 // If Identity shuffle return that node.
1459 bool Identity = true;
1460 for (unsigned i = 0; i != NElts; ++i) {
1461 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1463 if (Identity && NElts)
1466 // Shuffling a constant splat doesn't change the result.
1467 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1468 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1471 FoldingSetNodeID ID;
1472 SDValue Ops[2] = { N1, N2 };
1473 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1474 for (unsigned i = 0; i != NElts; ++i)
1475 ID.AddInteger(MaskVec[i]);
1478 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1479 return SDValue(E, 0);
1481 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1482 // SDNode doesn't have access to it. This memory will be "leaked" when
1483 // the node is deallocated, but recovered when the NodeAllocator is released.
1484 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1485 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1487 ShuffleVectorSDNode *N =
1488 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1489 dl.getDebugLoc(), N1, N2,
1491 CSEMap.InsertNode(N, IP);
1492 AllNodes.push_back(N);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1497 SDValue Val, SDValue DTy,
1498 SDValue STy, SDValue Rnd, SDValue Sat,
1499 ISD::CvtCode Code) {
1500 // If the src and dest types are the same and the conversion is between
1501 // integer types of the same sign or two floats, no conversion is necessary.
1503 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1506 FoldingSetNodeID ID;
1507 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1508 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1511 return SDValue(E, 0);
1513 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1516 CSEMap.InsertNode(N, IP);
1517 AllNodes.push_back(N);
1518 return SDValue(N, 0);
1521 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1522 FoldingSetNodeID ID;
1523 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1524 ID.AddInteger(RegNo);
1526 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1527 return SDValue(E, 0);
1529 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1530 CSEMap.InsertNode(N, IP);
1531 AllNodes.push_back(N);
1532 return SDValue(N, 0);
1535 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1536 FoldingSetNodeID ID;
1537 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1538 ID.AddPointer(RegMask);
1540 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1541 return SDValue(E, 0);
1543 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1544 CSEMap.InsertNode(N, IP);
1545 AllNodes.push_back(N);
1546 return SDValue(N, 0);
1549 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1550 FoldingSetNodeID ID;
1551 SDValue Ops[] = { Root };
1552 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1553 ID.AddPointer(Label);
1555 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1556 return SDValue(E, 0);
1558 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1559 dl.getDebugLoc(), Root, Label);
1560 CSEMap.InsertNode(N, IP);
1561 AllNodes.push_back(N);
1562 return SDValue(N, 0);
1566 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1569 unsigned char TargetFlags) {
1570 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1572 FoldingSetNodeID ID;
1573 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1575 ID.AddInteger(Offset);
1576 ID.AddInteger(TargetFlags);
1578 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1579 return SDValue(E, 0);
1581 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1583 CSEMap.InsertNode(N, IP);
1584 AllNodes.push_back(N);
1585 return SDValue(N, 0);
1588 SDValue SelectionDAG::getSrcValue(const Value *V) {
1589 assert((!V || V->getType()->isPointerTy()) &&
1590 "SrcValue is not a pointer?");
1592 FoldingSetNodeID ID;
1593 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1597 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1598 return SDValue(E, 0);
1600 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1601 CSEMap.InsertNode(N, IP);
1602 AllNodes.push_back(N);
1603 return SDValue(N, 0);
1606 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1607 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1608 FoldingSetNodeID ID;
1609 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1613 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1614 return SDValue(E, 0);
1616 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1617 CSEMap.InsertNode(N, IP);
1618 AllNodes.push_back(N);
1619 return SDValue(N, 0);
1622 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1623 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1624 unsigned SrcAS, unsigned DestAS) {
1625 SDValue Ops[] = {Ptr};
1626 FoldingSetNodeID ID;
1627 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1628 ID.AddInteger(SrcAS);
1629 ID.AddInteger(DestAS);
1632 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1633 return SDValue(E, 0);
1635 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1637 VT, Ptr, SrcAS, DestAS);
1638 CSEMap.InsertNode(N, IP);
1639 AllNodes.push_back(N);
1640 return SDValue(N, 0);
1643 /// getShiftAmountOperand - Return the specified value casted to
1644 /// the target's desired shift amount type.
1645 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1646 EVT OpTy = Op.getValueType();
1647 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1648 if (OpTy == ShTy || OpTy.isVector()) return Op;
1650 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1651 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1654 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1655 /// specified value type.
1656 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1657 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1658 unsigned ByteSize = VT.getStoreSize();
1659 Type *Ty = VT.getTypeForEVT(*getContext());
1660 const TargetLowering *TLI = TM.getTargetLowering();
1661 unsigned StackAlign =
1662 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1664 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1665 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1668 /// CreateStackTemporary - Create a stack temporary suitable for holding
1669 /// either of the specified value types.
1670 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1671 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1672 VT2.getStoreSizeInBits())/8;
1673 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1674 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1675 const TargetLowering *TLI = TM.getTargetLowering();
1676 const DataLayout *TD = TLI->getDataLayout();
1677 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1678 TD->getPrefTypeAlignment(Ty2));
1680 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1681 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1682 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1685 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1686 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1687 // These setcc operations always fold.
1691 case ISD::SETFALSE2: return getConstant(0, VT);
1693 case ISD::SETTRUE2: {
1694 const TargetLowering *TLI = TM.getTargetLowering();
1695 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1697 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1710 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1714 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1715 const APInt &C2 = N2C->getAPIntValue();
1716 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1717 const APInt &C1 = N1C->getAPIntValue();
1720 default: llvm_unreachable("Unknown integer setcc!");
1721 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1722 case ISD::SETNE: return getConstant(C1 != C2, VT);
1723 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1724 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1725 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1726 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1727 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1728 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1729 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1730 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1734 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1735 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1736 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1739 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1740 return getUNDEF(VT);
1742 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1743 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1744 return getUNDEF(VT);
1746 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1747 R==APFloat::cmpLessThan, VT);
1748 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1749 return getUNDEF(VT);
1751 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1752 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1753 return getUNDEF(VT);
1755 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1756 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1757 return getUNDEF(VT);
1759 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1760 R==APFloat::cmpEqual, VT);
1761 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1762 return getUNDEF(VT);
1764 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1765 R==APFloat::cmpEqual, VT);
1766 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1767 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1768 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1769 R==APFloat::cmpEqual, VT);
1770 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1771 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1772 R==APFloat::cmpLessThan, VT);
1773 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1774 R==APFloat::cmpUnordered, VT);
1775 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1776 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1779 // Ensure that the constant occurs on the RHS.
1780 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1781 MVT CompVT = N1.getValueType().getSimpleVT();
1782 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1785 return getSetCC(dl, VT, N2, N1, SwappedCond);
1789 // Could not fold it.
1793 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1794 /// use this predicate to simplify operations downstream.
1795 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1796 // This predicate is not safe for vector operations.
1797 if (Op.getValueType().isVector())
1800 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1801 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1804 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1805 /// this predicate to simplify operations downstream. Mask is known to be zero
1806 /// for bits that V cannot have.
1807 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1808 unsigned Depth) const {
1809 APInt KnownZero, KnownOne;
1810 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1811 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1812 return (KnownZero & Mask) == Mask;
1815 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1816 /// known to be either zero or one and return them in the KnownZero/KnownOne
1817 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1819 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1820 APInt &KnownOne, unsigned Depth) const {
1821 const TargetLowering *TLI = TM.getTargetLowering();
1822 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1824 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1826 return; // Limit search depth.
1828 APInt KnownZero2, KnownOne2;
1830 switch (Op.getOpcode()) {
1832 // We know all of the bits for a constant!
1833 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1834 KnownZero = ~KnownOne;
1837 // If either the LHS or the RHS are Zero, the result is zero.
1838 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1839 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1840 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1841 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1843 // Output known-1 bits are only known if set in both the LHS & RHS.
1844 KnownOne &= KnownOne2;
1845 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1846 KnownZero |= KnownZero2;
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 // Output known-0 bits are only known if clear in both the LHS & RHS.
1855 KnownZero &= KnownZero2;
1856 // Output known-1 are known to be set if set in either the LHS | RHS.
1857 KnownOne |= KnownOne2;
1860 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1861 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1862 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1863 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1865 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1866 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1867 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1868 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1869 KnownZero = KnownZeroOut;
1873 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1874 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1875 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1876 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1878 // If low bits are zero in either operand, output low known-0 bits.
1879 // Also compute a conserative estimate for high known-0 bits.
1880 // More trickiness is possible, but this is sufficient for the
1881 // interesting case of alignment computation.
1882 KnownOne.clearAllBits();
1883 unsigned TrailZ = KnownZero.countTrailingOnes() +
1884 KnownZero2.countTrailingOnes();
1885 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1886 KnownZero2.countLeadingOnes(),
1887 BitWidth) - BitWidth;
1889 TrailZ = std::min(TrailZ, BitWidth);
1890 LeadZ = std::min(LeadZ, BitWidth);
1891 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1892 APInt::getHighBitsSet(BitWidth, LeadZ);
1896 // For the purposes of computing leading zeros we can conservatively
1897 // treat a udiv as a logical right shift by the power of 2 known to
1898 // be less than the denominator.
1899 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1900 unsigned LeadZ = KnownZero2.countLeadingOnes();
1902 KnownOne2.clearAllBits();
1903 KnownZero2.clearAllBits();
1904 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1905 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1906 if (RHSUnknownLeadingOnes != BitWidth)
1907 LeadZ = std::min(BitWidth,
1908 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1910 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1914 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1915 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1916 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1917 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1919 // Only known if known in both the LHS and RHS.
1920 KnownOne &= KnownOne2;
1921 KnownZero &= KnownZero2;
1923 case ISD::SELECT_CC:
1924 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1925 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1926 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1927 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1929 // Only known if known in both the LHS and RHS.
1930 KnownOne &= KnownOne2;
1931 KnownZero &= KnownZero2;
1939 if (Op.getResNo() != 1)
1941 // The boolean result conforms to getBooleanContents. Fall through.
1943 // If we know the result of a setcc has the top bits zero, use this info.
1944 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1945 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1946 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1949 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1950 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1951 unsigned ShAmt = SA->getZExtValue();
1953 // If the shift count is an invalid immediate, don't do anything.
1954 if (ShAmt >= BitWidth)
1957 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1958 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1959 KnownZero <<= ShAmt;
1961 // low bits known zero.
1962 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1966 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1967 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1968 unsigned ShAmt = SA->getZExtValue();
1970 // If the shift count is an invalid immediate, don't do anything.
1971 if (ShAmt >= BitWidth)
1974 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1975 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1976 KnownZero = KnownZero.lshr(ShAmt);
1977 KnownOne = KnownOne.lshr(ShAmt);
1979 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1980 KnownZero |= HighBits; // High bits known zero.
1984 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1985 unsigned ShAmt = SA->getZExtValue();
1987 // If the shift count is an invalid immediate, don't do anything.
1988 if (ShAmt >= BitWidth)
1991 // If any of the demanded bits are produced by the sign extension, we also
1992 // demand the input sign bit.
1993 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1995 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1996 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1997 KnownZero = KnownZero.lshr(ShAmt);
1998 KnownOne = KnownOne.lshr(ShAmt);
2000 // Handle the sign bits.
2001 APInt SignBit = APInt::getSignBit(BitWidth);
2002 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2004 if (KnownZero.intersects(SignBit)) {
2005 KnownZero |= HighBits; // New bits are known zero.
2006 } else if (KnownOne.intersects(SignBit)) {
2007 KnownOne |= HighBits; // New bits are known one.
2011 case ISD::SIGN_EXTEND_INREG: {
2012 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2013 unsigned EBits = EVT.getScalarType().getSizeInBits();
2015 // Sign extension. Compute the demanded bits in the result that are not
2016 // present in the input.
2017 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2019 APInt InSignBit = APInt::getSignBit(EBits);
2020 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2022 // If the sign extended bits are demanded, we know that the sign
2024 InSignBit = InSignBit.zext(BitWidth);
2025 if (NewBits.getBoolValue())
2026 InputDemandedBits |= InSignBit;
2028 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2029 KnownOne &= InputDemandedBits;
2030 KnownZero &= InputDemandedBits;
2031 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2033 // If the sign bit of the input is known set or clear, then we know the
2034 // top bits of the result.
2035 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2036 KnownZero |= NewBits;
2037 KnownOne &= ~NewBits;
2038 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2039 KnownOne |= NewBits;
2040 KnownZero &= ~NewBits;
2041 } else { // Input sign bit unknown
2042 KnownZero &= ~NewBits;
2043 KnownOne &= ~NewBits;
2048 case ISD::CTTZ_ZERO_UNDEF:
2050 case ISD::CTLZ_ZERO_UNDEF:
2052 unsigned LowBits = Log2_32(BitWidth)+1;
2053 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2054 KnownOne.clearAllBits();
2058 LoadSDNode *LD = cast<LoadSDNode>(Op);
2059 // If this is a ZEXTLoad and we are looking at the loaded value.
2060 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2061 EVT VT = LD->getMemoryVT();
2062 unsigned MemBits = VT.getScalarType().getSizeInBits();
2063 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2064 } else if (const MDNode *Ranges = LD->getRanges()) {
2065 computeMaskedBitsLoad(*Ranges, KnownZero);
2069 case ISD::ZERO_EXTEND: {
2070 EVT InVT = Op.getOperand(0).getValueType();
2071 unsigned InBits = InVT.getScalarType().getSizeInBits();
2072 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2073 KnownZero = KnownZero.trunc(InBits);
2074 KnownOne = KnownOne.trunc(InBits);
2075 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2076 KnownZero = KnownZero.zext(BitWidth);
2077 KnownOne = KnownOne.zext(BitWidth);
2078 KnownZero |= NewBits;
2081 case ISD::SIGN_EXTEND: {
2082 EVT InVT = Op.getOperand(0).getValueType();
2083 unsigned InBits = InVT.getScalarType().getSizeInBits();
2084 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2086 KnownZero = KnownZero.trunc(InBits);
2087 KnownOne = KnownOne.trunc(InBits);
2088 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2090 // Note if the sign bit is known to be zero or one.
2091 bool SignBitKnownZero = KnownZero.isNegative();
2092 bool SignBitKnownOne = KnownOne.isNegative();
2093 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2094 "Sign bit can't be known to be both zero and one!");
2096 KnownZero = KnownZero.zext(BitWidth);
2097 KnownOne = KnownOne.zext(BitWidth);
2099 // If the sign bit is known zero or one, the top bits match.
2100 if (SignBitKnownZero)
2101 KnownZero |= NewBits;
2102 else if (SignBitKnownOne)
2103 KnownOne |= NewBits;
2106 case ISD::ANY_EXTEND: {
2107 EVT InVT = Op.getOperand(0).getValueType();
2108 unsigned InBits = InVT.getScalarType().getSizeInBits();
2109 KnownZero = KnownZero.trunc(InBits);
2110 KnownOne = KnownOne.trunc(InBits);
2111 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2112 KnownZero = KnownZero.zext(BitWidth);
2113 KnownOne = KnownOne.zext(BitWidth);
2116 case ISD::TRUNCATE: {
2117 EVT InVT = Op.getOperand(0).getValueType();
2118 unsigned InBits = InVT.getScalarType().getSizeInBits();
2119 KnownZero = KnownZero.zext(InBits);
2120 KnownOne = KnownOne.zext(InBits);
2121 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2122 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2123 KnownZero = KnownZero.trunc(BitWidth);
2124 KnownOne = KnownOne.trunc(BitWidth);
2127 case ISD::AssertZext: {
2128 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2129 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2130 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2131 KnownZero |= (~InMask);
2132 KnownOne &= (~KnownZero);
2136 // All bits are zero except the low bit.
2137 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2141 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2142 // We know that the top bits of C-X are clear if X contains less bits
2143 // than C (i.e. no wrap-around can happen). For example, 20-X is
2144 // positive if we can prove that X is >= 0 and < 16.
2145 if (CLHS->getAPIntValue().isNonNegative()) {
2146 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2147 // NLZ can't be BitWidth with no sign bit
2148 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2149 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2151 // If all of the MaskV bits are known to be zero, then we know the
2152 // output top bits are zero, because we now know that the output is
2154 if ((KnownZero2 & MaskV) == MaskV) {
2155 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2156 // Top bits known zero.
2157 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2165 // Output known-0 bits are known if clear or set in both the low clear bits
2166 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2167 // low 3 bits clear.
2168 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2169 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2170 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2172 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2173 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2174 KnownZeroOut = std::min(KnownZeroOut,
2175 KnownZero2.countTrailingOnes());
2177 if (Op.getOpcode() == ISD::ADD) {
2178 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2182 // With ADDE, a carry bit may be added in, so we can only use this
2183 // information if we know (at least) that the low two bits are clear. We
2184 // then return to the caller that the low bit is unknown but that other bits
2186 if (KnownZeroOut >= 2) // ADDE
2187 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2191 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 const APInt &RA = Rem->getAPIntValue().abs();
2193 if (RA.isPowerOf2()) {
2194 APInt LowBits = RA - 1;
2195 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2197 // The low bits of the first operand are unchanged by the srem.
2198 KnownZero = KnownZero2 & LowBits;
2199 KnownOne = KnownOne2 & LowBits;
2201 // If the first operand is non-negative or has all low bits zero, then
2202 // the upper bits are all zero.
2203 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2204 KnownZero |= ~LowBits;
2206 // If the first operand is negative and not all low bits are zero, then
2207 // the upper bits are all one.
2208 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2209 KnownOne |= ~LowBits;
2210 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2215 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2216 const APInt &RA = Rem->getAPIntValue();
2217 if (RA.isPowerOf2()) {
2218 APInt LowBits = (RA - 1);
2219 KnownZero |= ~LowBits;
2220 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2221 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2226 // Since the result is less than or equal to either operand, any leading
2227 // zero bits in either operand must also exist in the result.
2228 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2229 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2231 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2232 KnownZero2.countLeadingOnes());
2233 KnownOne.clearAllBits();
2234 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2237 case ISD::FrameIndex:
2238 case ISD::TargetFrameIndex:
2239 if (unsigned Align = InferPtrAlignment(Op)) {
2240 // The low bits are known zero if the pointer is aligned.
2241 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2247 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2250 case ISD::INTRINSIC_WO_CHAIN:
2251 case ISD::INTRINSIC_W_CHAIN:
2252 case ISD::INTRINSIC_VOID:
2253 // Allow the target to implement this method for its nodes.
2254 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2259 /// ComputeNumSignBits - Return the number of times the sign bit of the
2260 /// register is replicated into the other bits. We know that at least 1 bit
2261 /// is always equal to the sign bit (itself), but other cases can give us
2262 /// information. For example, immediately after an "SRA X, 2", we know that
2263 /// the top 3 bits are all equal to each other, so we return 3.
2264 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2265 const TargetLowering *TLI = TM.getTargetLowering();
2266 EVT VT = Op.getValueType();
2267 assert(VT.isInteger() && "Invalid VT!");
2268 unsigned VTBits = VT.getScalarType().getSizeInBits();
2270 unsigned FirstAnswer = 1;
2273 return 1; // Limit search depth.
2275 switch (Op.getOpcode()) {
2277 case ISD::AssertSext:
2278 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2279 return VTBits-Tmp+1;
2280 case ISD::AssertZext:
2281 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2284 case ISD::Constant: {
2285 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2286 return Val.getNumSignBits();
2289 case ISD::SIGN_EXTEND:
2291 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2292 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2294 case ISD::SIGN_EXTEND_INREG:
2295 // Max of the input and what this extends.
2297 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2300 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2301 return std::max(Tmp, Tmp2);
2304 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2305 // SRA X, C -> adds C sign bits.
2306 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2307 Tmp += C->getZExtValue();
2308 if (Tmp > VTBits) Tmp = VTBits;
2312 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2313 // shl destroys sign bits.
2314 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2315 if (C->getZExtValue() >= VTBits || // Bad shift.
2316 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2317 return Tmp - C->getZExtValue();
2322 case ISD::XOR: // NOT is handled here.
2323 // Logical binary ops preserve the number of sign bits at the worst.
2324 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2326 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2327 FirstAnswer = std::min(Tmp, Tmp2);
2328 // We computed what we know about the sign bits as our first
2329 // answer. Now proceed to the generic code that uses
2330 // ComputeMaskedBits, and pick whichever answer is better.
2335 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2336 if (Tmp == 1) return 1; // Early out.
2337 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2338 return std::min(Tmp, Tmp2);
2346 if (Op.getResNo() != 1)
2348 // The boolean result conforms to getBooleanContents. Fall through.
2350 // If setcc returns 0/-1, all bits are sign bits.
2351 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2352 TargetLowering::ZeroOrNegativeOneBooleanContent)
2357 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2358 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2360 // Handle rotate right by N like a rotate left by 32-N.
2361 if (Op.getOpcode() == ISD::ROTR)
2362 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2364 // If we aren't rotating out all of the known-in sign bits, return the
2365 // number that are left. This handles rotl(sext(x), 1) for example.
2366 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2367 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2371 // Add can have at most one carry bit. Thus we know that the output
2372 // is, at worst, one more bit than the inputs.
2373 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2374 if (Tmp == 1) return 1; // Early out.
2376 // Special case decrementing a value (ADD X, -1):
2377 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2378 if (CRHS->isAllOnesValue()) {
2379 APInt KnownZero, KnownOne;
2380 ComputeMaskedBits(Op.getOperand(0), 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 we are subtracting one from a positive number, there is no carry
2388 // out of the result.
2389 if (KnownZero.isNegative())
2393 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2394 if (Tmp2 == 1) return 1;
2395 return std::min(Tmp, Tmp2)-1;
2398 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2399 if (Tmp2 == 1) return 1;
2402 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2403 if (CLHS->isNullValue()) {
2404 APInt KnownZero, KnownOne;
2405 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2406 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2408 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2411 // If the input is known to be positive (the sign bit is known clear),
2412 // the output of the NEG has the same number of sign bits as the input.
2413 if (KnownZero.isNegative())
2416 // Otherwise, we treat this like a SUB.
2419 // Sub can have at most one carry bit. Thus we know that the output
2420 // is, at worst, one more bit than the inputs.
2421 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2422 if (Tmp == 1) return 1; // Early out.
2423 return std::min(Tmp, Tmp2)-1;
2425 // FIXME: it's tricky to do anything useful for this, but it is an important
2426 // case for targets like X86.
2430 // If we are looking at the loaded value of the SDNode.
2431 if (Op.getResNo() == 0) {
2432 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2433 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2434 unsigned ExtType = LD->getExtensionType();
2437 case ISD::SEXTLOAD: // '17' bits known
2438 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2439 return VTBits-Tmp+1;
2440 case ISD::ZEXTLOAD: // '16' bits known
2441 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2447 // Allow the target to implement this method for its nodes.
2448 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2449 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2450 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2451 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2452 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2453 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2456 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2457 // use this information.
2458 APInt KnownZero, KnownOne;
2459 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2462 if (KnownZero.isNegative()) { // sign bit is 0
2464 } else if (KnownOne.isNegative()) { // sign bit is 1;
2471 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2472 // the number of identical bits in the top of the input value.
2474 Mask <<= Mask.getBitWidth()-VTBits;
2475 // Return # leading zeros. We use 'min' here in case Val was zero before
2476 // shifting. We don't want to return '64' as for an i32 "0".
2477 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2480 /// isBaseWithConstantOffset - Return true if the specified operand is an
2481 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2482 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2483 /// semantics as an ADD. This handles the equivalence:
2484 /// X|Cst == X+Cst iff X&Cst = 0.
2485 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2486 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2487 !isa<ConstantSDNode>(Op.getOperand(1)))
2490 if (Op.getOpcode() == ISD::OR &&
2491 !MaskedValueIsZero(Op.getOperand(0),
2492 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2499 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2500 // If we're told that NaNs won't happen, assume they won't.
2501 if (getTarget().Options.NoNaNsFPMath)
2504 // If the value is a constant, we can obviously see if it is a NaN or not.
2505 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2506 return !C->getValueAPF().isNaN();
2508 // TODO: Recognize more cases here.
2513 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2514 // If the value is a constant, we can obviously see if it is a zero or not.
2515 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2516 return !C->isZero();
2518 // TODO: Recognize more cases here.
2519 switch (Op.getOpcode()) {
2522 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2523 return !C->isNullValue();
2530 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2531 // Check the obvious case.
2532 if (A == B) return true;
2534 // For for negative and positive zero.
2535 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2536 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2537 if (CA->isZero() && CB->isZero()) return true;
2539 // Otherwise they may not be equal.
2543 /// getNode - Gets or creates the specified node.
2545 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2546 FoldingSetNodeID ID;
2547 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2549 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2550 return SDValue(E, 0);
2552 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2553 DL.getDebugLoc(), getVTList(VT));
2554 CSEMap.InsertNode(N, IP);
2556 AllNodes.push_back(N);
2560 return SDValue(N, 0);
2563 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2564 EVT VT, SDValue Operand) {
2565 // Constant fold unary operations with an integer constant operand. Even
2566 // opaque constant will be folded, because the folding of unary operations
2567 // doesn't create new constants with different values. Nevertheless, the
2568 // opaque flag is preserved during folding to prevent future folding with
2570 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2571 const APInt &Val = C->getAPIntValue();
2574 case ISD::SIGN_EXTEND:
2575 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2576 C->isTargetOpcode(), C->isOpaque());
2577 case ISD::ANY_EXTEND:
2578 case ISD::ZERO_EXTEND:
2580 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2581 C->isTargetOpcode(), C->isOpaque());
2582 case ISD::UINT_TO_FP:
2583 case ISD::SINT_TO_FP: {
2584 APFloat apf(EVTToAPFloatSemantics(VT),
2585 APInt::getNullValue(VT.getSizeInBits()));
2586 (void)apf.convertFromAPInt(Val,
2587 Opcode==ISD::SINT_TO_FP,
2588 APFloat::rmNearestTiesToEven);
2589 return getConstantFP(apf, VT);
2592 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2593 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2594 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2595 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2598 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2601 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2604 case ISD::CTLZ_ZERO_UNDEF:
2605 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2608 case ISD::CTTZ_ZERO_UNDEF:
2609 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2614 // Constant fold unary operations with a floating point constant operand.
2615 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2616 APFloat V = C->getValueAPF(); // make copy
2620 return getConstantFP(V, VT);
2623 return getConstantFP(V, VT);
2625 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2626 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2627 return getConstantFP(V, VT);
2631 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2632 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2633 return getConstantFP(V, VT);
2637 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2638 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2639 return getConstantFP(V, VT);
2642 case ISD::FP_EXTEND: {
2644 // This can return overflow, underflow, or inexact; we don't care.
2645 // FIXME need to be more flexible about rounding mode.
2646 (void)V.convert(EVTToAPFloatSemantics(VT),
2647 APFloat::rmNearestTiesToEven, &ignored);
2648 return getConstantFP(V, VT);
2650 case ISD::FP_TO_SINT:
2651 case ISD::FP_TO_UINT: {
2654 assert(integerPartWidth >= 64);
2655 // FIXME need to be more flexible about rounding mode.
2656 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2657 Opcode==ISD::FP_TO_SINT,
2658 APFloat::rmTowardZero, &ignored);
2659 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2661 APInt api(VT.getSizeInBits(), x);
2662 return getConstant(api, VT);
2665 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2666 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2667 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2668 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2673 unsigned OpOpcode = Operand.getNode()->getOpcode();
2675 case ISD::TokenFactor:
2676 case ISD::MERGE_VALUES:
2677 case ISD::CONCAT_VECTORS:
2678 return Operand; // Factor, merge or concat of one node? No need.
2679 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2680 case ISD::FP_EXTEND:
2681 assert(VT.isFloatingPoint() &&
2682 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2683 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2684 assert((!VT.isVector() ||
2685 VT.getVectorNumElements() ==
2686 Operand.getValueType().getVectorNumElements()) &&
2687 "Vector element count mismatch!");
2688 if (Operand.getOpcode() == ISD::UNDEF)
2689 return getUNDEF(VT);
2691 case ISD::SIGN_EXTEND:
2692 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2693 "Invalid SIGN_EXTEND!");
2694 if (Operand.getValueType() == VT) return Operand; // noop extension
2695 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2696 "Invalid sext node, dst < src!");
2697 assert((!VT.isVector() ||
2698 VT.getVectorNumElements() ==
2699 Operand.getValueType().getVectorNumElements()) &&
2700 "Vector element count mismatch!");
2701 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2702 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2703 else if (OpOpcode == ISD::UNDEF)
2704 // sext(undef) = 0, because the top bits will all be the same.
2705 return getConstant(0, VT);
2707 case ISD::ZERO_EXTEND:
2708 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2709 "Invalid ZERO_EXTEND!");
2710 if (Operand.getValueType() == VT) return Operand; // noop extension
2711 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2712 "Invalid zext node, dst < src!");
2713 assert((!VT.isVector() ||
2714 VT.getVectorNumElements() ==
2715 Operand.getValueType().getVectorNumElements()) &&
2716 "Vector element count mismatch!");
2717 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2718 return getNode(ISD::ZERO_EXTEND, DL, VT,
2719 Operand.getNode()->getOperand(0));
2720 else if (OpOpcode == ISD::UNDEF)
2721 // zext(undef) = 0, because the top bits will be zero.
2722 return getConstant(0, VT);
2724 case ISD::ANY_EXTEND:
2725 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2726 "Invalid ANY_EXTEND!");
2727 if (Operand.getValueType() == VT) return Operand; // noop extension
2728 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2729 "Invalid anyext node, dst < src!");
2730 assert((!VT.isVector() ||
2731 VT.getVectorNumElements() ==
2732 Operand.getValueType().getVectorNumElements()) &&
2733 "Vector element count mismatch!");
2735 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2736 OpOpcode == ISD::ANY_EXTEND)
2737 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2738 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2739 else if (OpOpcode == ISD::UNDEF)
2740 return getUNDEF(VT);
2742 // (ext (trunx x)) -> x
2743 if (OpOpcode == ISD::TRUNCATE) {
2744 SDValue OpOp = Operand.getNode()->getOperand(0);
2745 if (OpOp.getValueType() == VT)
2750 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2751 "Invalid TRUNCATE!");
2752 if (Operand.getValueType() == VT) return Operand; // noop truncate
2753 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2754 "Invalid truncate node, src < dst!");
2755 assert((!VT.isVector() ||
2756 VT.getVectorNumElements() ==
2757 Operand.getValueType().getVectorNumElements()) &&
2758 "Vector element count mismatch!");
2759 if (OpOpcode == ISD::TRUNCATE)
2760 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2761 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2762 OpOpcode == ISD::ANY_EXTEND) {
2763 // If the source is smaller than the dest, we still need an extend.
2764 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2765 .bitsLT(VT.getScalarType()))
2766 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2767 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2768 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2769 return Operand.getNode()->getOperand(0);
2771 if (OpOpcode == ISD::UNDEF)
2772 return getUNDEF(VT);
2775 // Basic sanity checking.
2776 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2777 && "Cannot BITCAST between types of different sizes!");
2778 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2779 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2780 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2781 if (OpOpcode == ISD::UNDEF)
2782 return getUNDEF(VT);
2784 case ISD::SCALAR_TO_VECTOR:
2785 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2786 (VT.getVectorElementType() == Operand.getValueType() ||
2787 (VT.getVectorElementType().isInteger() &&
2788 Operand.getValueType().isInteger() &&
2789 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2790 "Illegal SCALAR_TO_VECTOR node!");
2791 if (OpOpcode == ISD::UNDEF)
2792 return getUNDEF(VT);
2793 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2794 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2795 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2796 Operand.getConstantOperandVal(1) == 0 &&
2797 Operand.getOperand(0).getValueType() == VT)
2798 return Operand.getOperand(0);
2801 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2802 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2803 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2804 Operand.getNode()->getOperand(0));
2805 if (OpOpcode == ISD::FNEG) // --X -> X
2806 return Operand.getNode()->getOperand(0);
2809 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2810 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2815 SDVTList VTs = getVTList(VT);
2816 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2817 FoldingSetNodeID ID;
2818 SDValue Ops[1] = { Operand };
2819 AddNodeIDNode(ID, Opcode, VTs, Ops);
2821 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2822 return SDValue(E, 0);
2824 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2825 DL.getDebugLoc(), VTs, Operand);
2826 CSEMap.InsertNode(N, IP);
2828 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2829 DL.getDebugLoc(), VTs, Operand);
2832 AllNodes.push_back(N);
2836 return SDValue(N, 0);
2839 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2840 SDNode *Cst1, SDNode *Cst2) {
2841 // If the opcode is a target-specific ISD node, there's nothing we can
2842 // do here and the operand rules may not line up with the below, so
2844 if (Opcode >= ISD::BUILTIN_OP_END)
2847 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2848 SmallVector<SDValue, 4> Outputs;
2849 EVT SVT = VT.getScalarType();
2851 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2852 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2853 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2856 if (Scalar1 && Scalar2)
2857 // Scalar instruction.
2858 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2860 // For vectors extract each constant element into Inputs so we can constant
2861 // fold them individually.
2862 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2863 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2867 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2869 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2870 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2871 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2872 if (!V1 || !V2) // Not a constant, bail.
2875 if (V1->isOpaque() || V2->isOpaque())
2878 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2879 // FIXME: This is valid and could be handled by truncating the APInts.
2880 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2883 Inputs.push_back(std::make_pair(V1, V2));
2887 // We have a number of constant values, constant fold them element by element.
2888 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2889 const APInt &C1 = Inputs[I].first->getAPIntValue();
2890 const APInt &C2 = Inputs[I].second->getAPIntValue();
2894 Outputs.push_back(getConstant(C1 + C2, SVT));
2897 Outputs.push_back(getConstant(C1 - C2, SVT));
2900 Outputs.push_back(getConstant(C1 * C2, SVT));
2903 if (!C2.getBoolValue())
2905 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2908 if (!C2.getBoolValue())
2910 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2913 if (!C2.getBoolValue())
2915 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2918 if (!C2.getBoolValue())
2920 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2923 Outputs.push_back(getConstant(C1 & C2, SVT));
2926 Outputs.push_back(getConstant(C1 | C2, SVT));
2929 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2932 Outputs.push_back(getConstant(C1 << C2, SVT));
2935 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2938 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2941 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2944 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2951 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2952 "Expected a scalar or vector!"));
2954 // Handle the scalar case first.
2956 return Outputs.back();
2958 // We may have a vector type but a scalar result. Create a splat.
2959 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2961 // Build a big vector out of the scalar elements we generated.
2962 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2965 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2967 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2968 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2971 case ISD::TokenFactor:
2972 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2973 N2.getValueType() == MVT::Other && "Invalid token factor!");
2974 // Fold trivial token factors.
2975 if (N1.getOpcode() == ISD::EntryToken) return N2;
2976 if (N2.getOpcode() == ISD::EntryToken) return N1;
2977 if (N1 == N2) return N1;
2979 case ISD::CONCAT_VECTORS:
2980 // Concat of UNDEFs is UNDEF.
2981 if (N1.getOpcode() == ISD::UNDEF &&
2982 N2.getOpcode() == ISD::UNDEF)
2983 return getUNDEF(VT);
2985 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2986 // one big BUILD_VECTOR.
2987 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2988 N2.getOpcode() == ISD::BUILD_VECTOR) {
2989 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2990 N1.getNode()->op_end());
2991 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2992 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2996 assert(VT.isInteger() && "This operator does not apply to FP types!");
2997 assert(N1.getValueType() == N2.getValueType() &&
2998 N1.getValueType() == VT && "Binary operator types must match!");
2999 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3000 // worth handling here.
3001 if (N2C && N2C->isNullValue())
3003 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3010 assert(VT.isInteger() && "This operator does not apply to FP types!");
3011 assert(N1.getValueType() == N2.getValueType() &&
3012 N1.getValueType() == VT && "Binary operator types must match!");
3013 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3014 // it's worth handling here.
3015 if (N2C && N2C->isNullValue())
3025 assert(VT.isInteger() && "This operator does not apply to FP types!");
3026 assert(N1.getValueType() == N2.getValueType() &&
3027 N1.getValueType() == VT && "Binary operator types must match!");
3034 if (getTarget().Options.UnsafeFPMath) {
3035 if (Opcode == ISD::FADD) {
3037 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3038 if (CFP->getValueAPF().isZero())
3041 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3042 if (CFP->getValueAPF().isZero())
3044 } else if (Opcode == ISD::FSUB) {
3046 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3047 if (CFP->getValueAPF().isZero())
3049 } else if (Opcode == ISD::FMUL) {
3050 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3053 // If the first operand isn't the constant, try the second
3055 CFP = dyn_cast<ConstantFPSDNode>(N2);
3062 return SDValue(CFP,0);
3064 if (CFP->isExactlyValue(1.0))
3069 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3070 assert(N1.getValueType() == N2.getValueType() &&
3071 N1.getValueType() == VT && "Binary operator types must match!");
3073 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3074 assert(N1.getValueType() == VT &&
3075 N1.getValueType().isFloatingPoint() &&
3076 N2.getValueType().isFloatingPoint() &&
3077 "Invalid FCOPYSIGN!");
3084 assert(VT == N1.getValueType() &&
3085 "Shift operators return type must be the same as their first arg");
3086 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3087 "Shifts only work on integers");
3088 assert((!VT.isVector() || VT == N2.getValueType()) &&
3089 "Vector shift amounts must be in the same as their first arg");
3090 // Verify that the shift amount VT is bit enough to hold valid shift
3091 // amounts. This catches things like trying to shift an i1024 value by an
3092 // i8, which is easy to fall into in generic code that uses
3093 // TLI.getShiftAmount().
3094 assert(N2.getValueType().getSizeInBits() >=
3095 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3096 "Invalid use of small shift amount with oversized value!");
3098 // Always fold shifts of i1 values so the code generator doesn't need to
3099 // handle them. Since we know the size of the shift has to be less than the
3100 // size of the value, the shift/rotate count is guaranteed to be zero.
3103 if (N2C && N2C->isNullValue())
3106 case ISD::FP_ROUND_INREG: {
3107 EVT EVT = cast<VTSDNode>(N2)->getVT();
3108 assert(VT == N1.getValueType() && "Not an inreg round!");
3109 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3110 "Cannot FP_ROUND_INREG integer types");
3111 assert(EVT.isVector() == VT.isVector() &&
3112 "FP_ROUND_INREG type should be vector iff the operand "
3114 assert((!EVT.isVector() ||
3115 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3116 "Vector element counts must match in FP_ROUND_INREG");
3117 assert(EVT.bitsLE(VT) && "Not rounding down!");
3119 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3123 assert(VT.isFloatingPoint() &&
3124 N1.getValueType().isFloatingPoint() &&
3125 VT.bitsLE(N1.getValueType()) &&
3126 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3127 if (N1.getValueType() == VT) return N1; // noop conversion.
3129 case ISD::AssertSext:
3130 case ISD::AssertZext: {
3131 EVT EVT = cast<VTSDNode>(N2)->getVT();
3132 assert(VT == N1.getValueType() && "Not an inreg extend!");
3133 assert(VT.isInteger() && EVT.isInteger() &&
3134 "Cannot *_EXTEND_INREG FP types");
3135 assert(!EVT.isVector() &&
3136 "AssertSExt/AssertZExt type should be the vector element type "
3137 "rather than the vector type!");
3138 assert(EVT.bitsLE(VT) && "Not extending!");
3139 if (VT == EVT) return N1; // noop assertion.
3142 case ISD::SIGN_EXTEND_INREG: {
3143 EVT EVT = cast<VTSDNode>(N2)->getVT();
3144 assert(VT == N1.getValueType() && "Not an inreg extend!");
3145 assert(VT.isInteger() && EVT.isInteger() &&
3146 "Cannot *_EXTEND_INREG FP types");
3147 assert(EVT.isVector() == VT.isVector() &&
3148 "SIGN_EXTEND_INREG type should be vector iff the operand "
3150 assert((!EVT.isVector() ||
3151 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3152 "Vector element counts must match in SIGN_EXTEND_INREG");
3153 assert(EVT.bitsLE(VT) && "Not extending!");
3154 if (EVT == VT) return N1; // Not actually extending
3157 APInt Val = N1C->getAPIntValue();
3158 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3159 Val <<= Val.getBitWidth()-FromBits;
3160 Val = Val.ashr(Val.getBitWidth()-FromBits);
3161 return getConstant(Val, VT);
3165 case ISD::EXTRACT_VECTOR_ELT:
3166 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3167 if (N1.getOpcode() == ISD::UNDEF)
3168 return getUNDEF(VT);
3170 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3171 // expanding copies of large vectors from registers.
3173 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3174 N1.getNumOperands() > 0) {
3176 N1.getOperand(0).getValueType().getVectorNumElements();
3177 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3178 N1.getOperand(N2C->getZExtValue() / Factor),
3179 getConstant(N2C->getZExtValue() % Factor,
3180 N2.getValueType()));
3183 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3184 // expanding large vector constants.
3185 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3186 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3188 if (VT != Elt.getValueType())
3189 // If the vector element type is not legal, the BUILD_VECTOR operands
3190 // are promoted and implicitly truncated, and the result implicitly
3191 // extended. Make that explicit here.
3192 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3197 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3198 // operations are lowered to scalars.
3199 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3200 // If the indices are the same, return the inserted element else
3201 // if the indices are known different, extract the element from
3202 // the original vector.
3203 SDValue N1Op2 = N1.getOperand(2);
3204 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3206 if (N1Op2C && N2C) {
3207 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3208 if (VT == N1.getOperand(1).getValueType())
3209 return N1.getOperand(1);
3211 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3214 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3218 case ISD::EXTRACT_ELEMENT:
3219 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3220 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3221 (N1.getValueType().isInteger() == VT.isInteger()) &&
3222 N1.getValueType() != VT &&
3223 "Wrong types for EXTRACT_ELEMENT!");
3225 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3226 // 64-bit integers into 32-bit parts. Instead of building the extract of
3227 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3228 if (N1.getOpcode() == ISD::BUILD_PAIR)
3229 return N1.getOperand(N2C->getZExtValue());
3231 // EXTRACT_ELEMENT of a constant int is also very common.
3232 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3233 unsigned ElementSize = VT.getSizeInBits();
3234 unsigned Shift = ElementSize * N2C->getZExtValue();
3235 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3236 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3239 case ISD::EXTRACT_SUBVECTOR: {
3241 if (VT.isSimple() && N1.getValueType().isSimple()) {
3242 assert(VT.isVector() && N1.getValueType().isVector() &&
3243 "Extract subvector VTs must be a vectors!");
3244 assert(VT.getVectorElementType() ==
3245 N1.getValueType().getVectorElementType() &&
3246 "Extract subvector VTs must have the same element type!");
3247 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3248 "Extract subvector must be from larger vector to smaller vector!");
3250 if (isa<ConstantSDNode>(Index.getNode())) {
3251 assert((VT.getVectorNumElements() +
3252 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3253 <= N1.getValueType().getVectorNumElements())
3254 && "Extract subvector overflow!");
3257 // Trivial extraction.
3258 if (VT.getSimpleVT() == N1.getSimpleValueType())
3265 // Perform trivial constant folding.
3266 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3267 if (SV.getNode()) return SV;
3269 // Canonicalize constant to RHS if commutative.
3270 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3271 std::swap(N1C, N2C);
3275 // Constant fold FP operations.
3276 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3277 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3279 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3280 // Canonicalize constant to RHS if commutative.
3281 std::swap(N1CFP, N2CFP);
3284 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3285 APFloat::opStatus s;
3288 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3289 if (s != APFloat::opInvalidOp)
3290 return getConstantFP(V1, VT);
3293 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3294 if (s!=APFloat::opInvalidOp)
3295 return getConstantFP(V1, VT);
3298 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3299 if (s!=APFloat::opInvalidOp)
3300 return getConstantFP(V1, VT);
3303 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3304 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3305 return getConstantFP(V1, VT);
3308 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3309 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3310 return getConstantFP(V1, VT);
3312 case ISD::FCOPYSIGN:
3314 return getConstantFP(V1, VT);
3319 if (Opcode == ISD::FP_ROUND) {
3320 APFloat V = N1CFP->getValueAPF(); // make copy
3322 // This can return overflow, underflow, or inexact; we don't care.
3323 // FIXME need to be more flexible about rounding mode.
3324 (void)V.convert(EVTToAPFloatSemantics(VT),
3325 APFloat::rmNearestTiesToEven, &ignored);
3326 return getConstantFP(V, VT);
3330 // Canonicalize an UNDEF to the RHS, even over a constant.
3331 if (N1.getOpcode() == ISD::UNDEF) {
3332 if (isCommutativeBinOp(Opcode)) {
3336 case ISD::FP_ROUND_INREG:
3337 case ISD::SIGN_EXTEND_INREG:
3343 return N1; // fold op(undef, arg2) -> undef
3351 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3352 // For vectors, we can't easily build an all zero vector, just return
3359 // Fold a bunch of operators when the RHS is undef.
3360 if (N2.getOpcode() == ISD::UNDEF) {
3363 if (N1.getOpcode() == ISD::UNDEF)
3364 // Handle undef ^ undef -> 0 special case. This is a common
3366 return getConstant(0, VT);
3376 return N2; // fold op(arg1, undef) -> undef
3382 if (getTarget().Options.UnsafeFPMath)
3390 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3391 // For vectors, we can't easily build an all zero vector, just return
3396 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3397 // For vectors, we can't easily build an all one vector, just return
3405 // Memoize this node if possible.
3407 SDVTList VTs = getVTList(VT);
3408 if (VT != MVT::Glue) {
3409 SDValue Ops[] = { N1, N2 };
3410 FoldingSetNodeID ID;
3411 AddNodeIDNode(ID, Opcode, VTs, Ops);
3413 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3414 return SDValue(E, 0);
3416 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3417 DL.getDebugLoc(), VTs, N1, N2);
3418 CSEMap.InsertNode(N, IP);
3420 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3421 DL.getDebugLoc(), VTs, N1, N2);
3424 AllNodes.push_back(N);
3428 return SDValue(N, 0);
3431 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3432 SDValue N1, SDValue N2, SDValue N3) {
3433 // Perform various simplifications.
3434 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3437 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3438 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3439 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3440 if (N1CFP && N2CFP && N3CFP) {
3441 APFloat V1 = N1CFP->getValueAPF();
3442 const APFloat &V2 = N2CFP->getValueAPF();
3443 const APFloat &V3 = N3CFP->getValueAPF();
3444 APFloat::opStatus s =
3445 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3446 if (s != APFloat::opInvalidOp)
3447 return getConstantFP(V1, VT);
3451 case ISD::CONCAT_VECTORS:
3452 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3453 // one big BUILD_VECTOR.
3454 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3455 N2.getOpcode() == ISD::BUILD_VECTOR &&
3456 N3.getOpcode() == ISD::BUILD_VECTOR) {
3457 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3458 N1.getNode()->op_end());
3459 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3460 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3461 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3465 // Use FoldSetCC to simplify SETCC's.
3466 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3467 if (Simp.getNode()) return Simp;
3472 if (N1C->getZExtValue())
3473 return N2; // select true, X, Y -> X
3474 return N3; // select false, X, Y -> Y
3477 if (N2 == N3) return N2; // select C, X, X -> X
3479 case ISD::VECTOR_SHUFFLE:
3480 llvm_unreachable("should use getVectorShuffle constructor!");
3481 case ISD::INSERT_SUBVECTOR: {
3483 if (VT.isSimple() && N1.getValueType().isSimple()
3484 && N2.getValueType().isSimple()) {
3485 assert(VT.isVector() && N1.getValueType().isVector() &&
3486 N2.getValueType().isVector() &&
3487 "Insert subvector VTs must be a vectors");
3488 assert(VT == N1.getValueType() &&
3489 "Dest and insert subvector source types must match!");
3490 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3491 "Insert subvector must be from smaller vector to larger vector!");
3492 if (isa<ConstantSDNode>(Index.getNode())) {
3493 assert((N2.getValueType().getVectorNumElements() +
3494 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3495 <= VT.getVectorNumElements())
3496 && "Insert subvector overflow!");
3499 // Trivial insertion.
3500 if (VT.getSimpleVT() == N2.getSimpleValueType())
3506 // Fold bit_convert nodes from a type to themselves.
3507 if (N1.getValueType() == VT)
3512 // Memoize node if it doesn't produce a flag.
3514 SDVTList VTs = getVTList(VT);
3515 if (VT != MVT::Glue) {
3516 SDValue Ops[] = { N1, N2, N3 };
3517 FoldingSetNodeID ID;
3518 AddNodeIDNode(ID, Opcode, VTs, Ops);
3520 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3521 return SDValue(E, 0);
3523 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3524 DL.getDebugLoc(), VTs, N1, N2, N3);
3525 CSEMap.InsertNode(N, IP);
3527 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3528 DL.getDebugLoc(), VTs, N1, N2, N3);
3531 AllNodes.push_back(N);
3535 return SDValue(N, 0);
3538 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3539 SDValue N1, SDValue N2, SDValue N3,
3541 SDValue Ops[] = { N1, N2, N3, N4 };
3542 return getNode(Opcode, DL, VT, Ops);
3545 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3546 SDValue N1, SDValue N2, SDValue N3,
3547 SDValue N4, SDValue N5) {
3548 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3549 return getNode(Opcode, DL, VT, Ops);
3552 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3553 /// the incoming stack arguments to be loaded from the stack.
3554 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3555 SmallVector<SDValue, 8> ArgChains;
3557 // Include the original chain at the beginning of the list. When this is
3558 // used by target LowerCall hooks, this helps legalize find the
3559 // CALLSEQ_BEGIN node.
3560 ArgChains.push_back(Chain);
3562 // Add a chain value for each stack argument.
3563 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3564 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3565 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3566 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3567 if (FI->getIndex() < 0)
3568 ArgChains.push_back(SDValue(L, 1));
3570 // Build a tokenfactor for all the chains.
3571 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3574 /// getMemsetValue - Vectorized representation of the memset value
3576 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3578 assert(Value.getOpcode() != ISD::UNDEF);
3580 unsigned NumBits = VT.getScalarType().getSizeInBits();
3581 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3582 assert(C->getAPIntValue().getBitWidth() == 8);
3583 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3585 return DAG.getConstant(Val, VT);
3586 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3589 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3591 // Use a multiplication with 0x010101... to extend the input to the
3593 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3594 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3600 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3601 /// used when a memcpy is turned into a memset when the source is a constant
3603 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3604 const TargetLowering &TLI, StringRef Str) {
3605 // Handle vector with all elements zero.
3608 return DAG.getConstant(0, VT);
3609 else if (VT == MVT::f32 || VT == MVT::f64)
3610 return DAG.getConstantFP(0.0, VT);
3611 else if (VT.isVector()) {
3612 unsigned NumElts = VT.getVectorNumElements();
3613 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3614 return DAG.getNode(ISD::BITCAST, dl, VT,
3615 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3618 llvm_unreachable("Expected type!");
3621 assert(!VT.isVector() && "Can't handle vector type here!");
3622 unsigned NumVTBits = VT.getSizeInBits();
3623 unsigned NumVTBytes = NumVTBits / 8;
3624 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3626 APInt Val(NumVTBits, 0);
3627 if (TLI.isLittleEndian()) {
3628 for (unsigned i = 0; i != NumBytes; ++i)
3629 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3631 for (unsigned i = 0; i != NumBytes; ++i)
3632 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3635 // If the "cost" of materializing the integer immediate is less than the cost
3636 // of a load, then it is cost effective to turn the load into the immediate.
3637 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3638 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3639 return DAG.getConstant(Val, VT);
3640 return SDValue(nullptr, 0);
3643 /// getMemBasePlusOffset - Returns base and offset node for the
3645 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3646 SelectionDAG &DAG) {
3647 EVT VT = Base.getValueType();
3648 return DAG.getNode(ISD::ADD, dl,
3649 VT, Base, DAG.getConstant(Offset, VT));
3652 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3654 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3655 unsigned SrcDelta = 0;
3656 GlobalAddressSDNode *G = nullptr;
3657 if (Src.getOpcode() == ISD::GlobalAddress)
3658 G = cast<GlobalAddressSDNode>(Src);
3659 else if (Src.getOpcode() == ISD::ADD &&
3660 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3661 Src.getOperand(1).getOpcode() == ISD::Constant) {
3662 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3663 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3668 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3671 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3672 /// to replace the memset / memcpy. Return true if the number of memory ops
3673 /// is below the threshold. It returns the types of the sequence of
3674 /// memory ops to perform memset / memcpy by reference.
3675 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3676 unsigned Limit, uint64_t Size,
3677 unsigned DstAlign, unsigned SrcAlign,
3683 const TargetLowering &TLI) {
3684 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3685 "Expecting memcpy / memset source to meet alignment requirement!");
3686 // If 'SrcAlign' is zero, that means the memory operation does not need to
3687 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3688 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3689 // is the specified alignment of the memory operation. If it is zero, that
3690 // means it's possible to change the alignment of the destination.
3691 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3692 // not need to be loaded.
3693 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3694 IsMemset, ZeroMemset, MemcpyStrSrc,
3695 DAG.getMachineFunction());
3697 if (VT == MVT::Other) {
3699 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3700 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3701 VT = TLI.getPointerTy();
3703 switch (DstAlign & 7) {
3704 case 0: VT = MVT::i64; break;
3705 case 4: VT = MVT::i32; break;
3706 case 2: VT = MVT::i16; break;
3707 default: VT = MVT::i8; break;
3712 while (!TLI.isTypeLegal(LVT))
3713 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3714 assert(LVT.isInteger());
3720 unsigned NumMemOps = 0;
3722 unsigned VTSize = VT.getSizeInBits() / 8;
3723 while (VTSize > Size) {
3724 // For now, only use non-vector load / store's for the left-over pieces.
3729 if (VT.isVector() || VT.isFloatingPoint()) {
3730 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3731 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3732 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3734 else if (NewVT == MVT::i64 &&
3735 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3736 TLI.isSafeMemOpType(MVT::f64)) {
3737 // i64 is usually not legal on 32-bit targets, but f64 may be.
3745 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3746 if (NewVT == MVT::i8)
3748 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3750 NewVTSize = NewVT.getSizeInBits() / 8;
3752 // If the new VT cannot cover all of the remaining bits, then consider
3753 // issuing a (or a pair of) unaligned and overlapping load / store.
3754 // FIXME: Only does this for 64-bit or more since we don't have proper
3755 // cost model for unaligned load / store.
3758 if (NumMemOps && AllowOverlap &&
3759 VTSize >= 8 && NewVTSize < Size &&
3760 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3768 if (++NumMemOps > Limit)
3771 MemOps.push_back(VT);
3778 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3779 SDValue Chain, SDValue Dst,
3780 SDValue Src, uint64_t Size,
3781 unsigned Align, bool isVol,
3783 MachinePointerInfo DstPtrInfo,
3784 MachinePointerInfo SrcPtrInfo) {
3785 // Turn a memcpy of undef to nop.
3786 if (Src.getOpcode() == ISD::UNDEF)
3789 // Expand memcpy to a series of load and store ops if the size operand falls
3790 // below a certain threshold.
3791 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3792 // rather than maybe a humongous number of loads and stores.
3793 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3794 std::vector<EVT> MemOps;
3795 bool DstAlignCanChange = false;
3796 MachineFunction &MF = DAG.getMachineFunction();
3797 MachineFrameInfo *MFI = MF.getFrameInfo();
3799 MF.getFunction()->getAttributes().
3800 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3801 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3802 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3803 DstAlignCanChange = true;
3804 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3805 if (Align > SrcAlign)
3808 bool CopyFromStr = isMemSrcFromString(Src, Str);
3809 bool isZeroStr = CopyFromStr && Str.empty();
3810 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3812 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3813 (DstAlignCanChange ? 0 : Align),
3814 (isZeroStr ? 0 : SrcAlign),
3815 false, false, CopyFromStr, true, DAG, TLI))
3818 if (DstAlignCanChange) {
3819 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3820 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3822 // Don't promote to an alignment that would require dynamic stack
3824 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3825 if (!TRI->needsStackRealignment(MF))
3826 while (NewAlign > Align &&
3827 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3830 if (NewAlign > Align) {
3831 // Give the stack frame object a larger alignment if needed.
3832 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3833 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3838 SmallVector<SDValue, 8> OutChains;
3839 unsigned NumMemOps = MemOps.size();
3840 uint64_t SrcOff = 0, DstOff = 0;
3841 for (unsigned i = 0; i != NumMemOps; ++i) {
3843 unsigned VTSize = VT.getSizeInBits() / 8;
3844 SDValue Value, Store;
3846 if (VTSize > Size) {
3847 // Issuing an unaligned load / store pair that overlaps with the previous
3848 // pair. Adjust the offset accordingly.
3849 assert(i == NumMemOps-1 && i != 0);
3850 SrcOff -= VTSize - Size;
3851 DstOff -= VTSize - Size;
3855 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3856 // It's unlikely a store of a vector immediate can be done in a single
3857 // instruction. It would require a load from a constantpool first.
3858 // We only handle zero vectors here.
3859 // FIXME: Handle other cases where store of vector immediate is done in
3860 // a single instruction.
3861 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3862 if (Value.getNode())
3863 Store = DAG.getStore(Chain, dl, Value,
3864 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3865 DstPtrInfo.getWithOffset(DstOff), isVol,
3869 if (!Store.getNode()) {
3870 // The type might not be legal for the target. This should only happen
3871 // if the type is smaller than a legal type, as on PPC, so the right
3872 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3873 // to Load/Store if NVT==VT.
3874 // FIXME does the case above also need this?
3875 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3876 assert(NVT.bitsGE(VT));
3877 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3878 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3879 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3880 MinAlign(SrcAlign, SrcOff));
3881 Store = DAG.getTruncStore(Chain, dl, Value,
3882 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3883 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3886 OutChains.push_back(Store);
3892 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3895 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3896 SDValue Chain, SDValue Dst,
3897 SDValue Src, uint64_t Size,
3898 unsigned Align, bool isVol,
3900 MachinePointerInfo DstPtrInfo,
3901 MachinePointerInfo SrcPtrInfo) {
3902 // Turn a memmove of undef to nop.
3903 if (Src.getOpcode() == ISD::UNDEF)
3906 // Expand memmove to a series of load and store ops if the size operand falls
3907 // below a certain threshold.
3908 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3909 std::vector<EVT> MemOps;
3910 bool DstAlignCanChange = false;
3911 MachineFunction &MF = DAG.getMachineFunction();
3912 MachineFrameInfo *MFI = MF.getFrameInfo();
3913 bool OptSize = MF.getFunction()->getAttributes().
3914 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3915 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3916 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3917 DstAlignCanChange = true;
3918 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3919 if (Align > SrcAlign)
3921 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3923 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3924 (DstAlignCanChange ? 0 : Align), SrcAlign,
3925 false, false, false, false, DAG, TLI))
3928 if (DstAlignCanChange) {
3929 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3930 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3931 if (NewAlign > Align) {
3932 // Give the stack frame object a larger alignment if needed.
3933 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3934 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3939 uint64_t SrcOff = 0, DstOff = 0;
3940 SmallVector<SDValue, 8> LoadValues;
3941 SmallVector<SDValue, 8> LoadChains;
3942 SmallVector<SDValue, 8> OutChains;
3943 unsigned NumMemOps = MemOps.size();
3944 for (unsigned i = 0; i < NumMemOps; i++) {
3946 unsigned VTSize = VT.getSizeInBits() / 8;
3949 Value = DAG.getLoad(VT, dl, Chain,
3950 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3951 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3952 false, false, SrcAlign);
3953 LoadValues.push_back(Value);
3954 LoadChains.push_back(Value.getValue(1));
3957 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3959 for (unsigned i = 0; i < NumMemOps; i++) {
3961 unsigned VTSize = VT.getSizeInBits() / 8;
3964 Store = DAG.getStore(Chain, dl, LoadValues[i],
3965 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3966 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3967 OutChains.push_back(Store);
3971 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3974 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3977 /// \param DAG Selection DAG where lowered code is placed.
3978 /// \param dl Link to corresponding IR location.
3979 /// \param Chain Control flow dependency.
3980 /// \param Dst Pointer to destination memory location.
3981 /// \param Src Value of byte to write into the memory.
3982 /// \param Size Number of bytes to write.
3983 /// \param Align Alignment of the destination in bytes.
3984 /// \param isVol True if destination is volatile.
3985 /// \param DstPtrInfo IR information on the memory pointer.
3986 /// \returns New head in the control flow, if lowering was successful, empty
3987 /// SDValue otherwise.
3989 /// The function tries to replace 'llvm.memset' intrinsic with several store
3990 /// operations and value calculation code. This is usually profitable for small
3992 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3993 SDValue Chain, SDValue Dst,
3994 SDValue Src, uint64_t Size,
3995 unsigned Align, bool isVol,
3996 MachinePointerInfo DstPtrInfo) {
3997 // Turn a memset of undef to nop.
3998 if (Src.getOpcode() == ISD::UNDEF)
4001 // Expand memset to a series of load/store ops if the size operand
4002 // falls below a certain threshold.
4003 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4004 std::vector<EVT> MemOps;
4005 bool DstAlignCanChange = false;
4006 MachineFunction &MF = DAG.getMachineFunction();
4007 MachineFrameInfo *MFI = MF.getFrameInfo();
4008 bool OptSize = MF.getFunction()->getAttributes().
4009 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4010 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4011 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4012 DstAlignCanChange = true;
4014 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4015 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4016 Size, (DstAlignCanChange ? 0 : Align), 0,
4017 true, IsZeroVal, false, true, DAG, TLI))
4020 if (DstAlignCanChange) {
4021 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4022 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4023 if (NewAlign > Align) {
4024 // Give the stack frame object a larger alignment if needed.
4025 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4026 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4031 SmallVector<SDValue, 8> OutChains;
4032 uint64_t DstOff = 0;
4033 unsigned NumMemOps = MemOps.size();
4035 // Find the largest store and generate the bit pattern for it.
4036 EVT LargestVT = MemOps[0];
4037 for (unsigned i = 1; i < NumMemOps; i++)
4038 if (MemOps[i].bitsGT(LargestVT))
4039 LargestVT = MemOps[i];
4040 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4042 for (unsigned i = 0; i < NumMemOps; i++) {
4044 unsigned VTSize = VT.getSizeInBits() / 8;
4045 if (VTSize > Size) {
4046 // Issuing an unaligned load / store pair that overlaps with the previous
4047 // pair. Adjust the offset accordingly.
4048 assert(i == NumMemOps-1 && i != 0);
4049 DstOff -= VTSize - Size;
4052 // If this store is smaller than the largest store see whether we can get
4053 // the smaller value for free with a truncate.
4054 SDValue Value = MemSetValue;
4055 if (VT.bitsLT(LargestVT)) {
4056 if (!LargestVT.isVector() && !VT.isVector() &&
4057 TLI.isTruncateFree(LargestVT, VT))
4058 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4060 Value = getMemsetValue(Src, VT, DAG, dl);
4062 assert(Value.getValueType() == VT && "Value with wrong type.");
4063 SDValue Store = DAG.getStore(Chain, dl, Value,
4064 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4065 DstPtrInfo.getWithOffset(DstOff),
4066 isVol, false, Align);
4067 OutChains.push_back(Store);
4068 DstOff += VT.getSizeInBits() / 8;
4072 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4075 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4076 SDValue Src, SDValue Size,
4077 unsigned Align, bool isVol, bool AlwaysInline,
4078 MachinePointerInfo DstPtrInfo,
4079 MachinePointerInfo SrcPtrInfo) {
4080 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4082 // Check to see if we should lower the memcpy to loads and stores first.
4083 // For cases within the target-specified limits, this is the best choice.
4084 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4086 // Memcpy with size zero? Just return the original chain.
4087 if (ConstantSize->isNullValue())
4090 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4091 ConstantSize->getZExtValue(),Align,
4092 isVol, false, DstPtrInfo, SrcPtrInfo);
4093 if (Result.getNode())
4097 // Then check to see if we should lower the memcpy with target-specific
4098 // code. If the target chooses to do this, this is the next best.
4100 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4101 isVol, AlwaysInline,
4102 DstPtrInfo, SrcPtrInfo);
4103 if (Result.getNode())
4106 // If we really need inline code and the target declined to provide it,
4107 // use a (potentially long) sequence of loads and stores.
4109 assert(ConstantSize && "AlwaysInline requires a constant size!");
4110 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4111 ConstantSize->getZExtValue(), Align, isVol,
4112 true, DstPtrInfo, SrcPtrInfo);
4115 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4116 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4117 // respect volatile, so they may do things like read or write memory
4118 // beyond the given memory regions. But fixing this isn't easy, and most
4119 // people don't care.
4121 const TargetLowering *TLI = TM.getTargetLowering();
4123 // Emit a library call.
4124 TargetLowering::ArgListTy Args;
4125 TargetLowering::ArgListEntry Entry;
4126 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4127 Entry.Node = Dst; Args.push_back(Entry);
4128 Entry.Node = Src; Args.push_back(Entry);
4129 Entry.Node = Size; Args.push_back(Entry);
4130 // FIXME: pass in SDLoc
4132 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4133 false, false, false, false, 0,
4134 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4135 /*isTailCall=*/false,
4136 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4137 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4138 TLI->getPointerTy()),
4140 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4142 return CallResult.second;
4145 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4146 SDValue Src, SDValue Size,
4147 unsigned Align, bool isVol,
4148 MachinePointerInfo DstPtrInfo,
4149 MachinePointerInfo SrcPtrInfo) {
4150 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4152 // Check to see if we should lower the memmove to loads and stores first.
4153 // For cases within the target-specified limits, this is the best choice.
4154 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4156 // Memmove with size zero? Just return the original chain.
4157 if (ConstantSize->isNullValue())
4161 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4162 ConstantSize->getZExtValue(), Align, isVol,
4163 false, DstPtrInfo, SrcPtrInfo);
4164 if (Result.getNode())
4168 // Then check to see if we should lower the memmove with target-specific
4169 // code. If the target chooses to do this, this is the next best.
4171 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4172 DstPtrInfo, SrcPtrInfo);
4173 if (Result.getNode())
4176 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4177 // not be safe. See memcpy above for more details.
4179 const TargetLowering *TLI = TM.getTargetLowering();
4181 // Emit a library call.
4182 TargetLowering::ArgListTy Args;
4183 TargetLowering::ArgListEntry Entry;
4184 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4185 Entry.Node = Dst; Args.push_back(Entry);
4186 Entry.Node = Src; Args.push_back(Entry);
4187 Entry.Node = Size; Args.push_back(Entry);
4188 // FIXME: pass in SDLoc
4190 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4191 false, false, false, false, 0,
4192 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4193 /*isTailCall=*/false,
4194 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4195 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4196 TLI->getPointerTy()),
4198 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4200 return CallResult.second;
4203 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4204 SDValue Src, SDValue Size,
4205 unsigned Align, bool isVol,
4206 MachinePointerInfo DstPtrInfo) {
4207 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4209 // Check to see if we should lower the memset to stores first.
4210 // For cases within the target-specified limits, this is the best choice.
4211 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4213 // Memset with size zero? Just return the original chain.
4214 if (ConstantSize->isNullValue())
4218 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4219 Align, isVol, DstPtrInfo);
4221 if (Result.getNode())
4225 // Then check to see if we should lower the memset with target-specific
4226 // code. If the target chooses to do this, this is the next best.
4228 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4230 if (Result.getNode())
4233 // Emit a library call.
4234 const TargetLowering *TLI = TM.getTargetLowering();
4235 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4236 TargetLowering::ArgListTy Args;
4237 TargetLowering::ArgListEntry Entry;
4238 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4239 Args.push_back(Entry);
4240 // Extend or truncate the argument to be an i32 value for the call.
4241 if (Src.getValueType().bitsGT(MVT::i32))
4242 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4244 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4246 Entry.Ty = Type::getInt32Ty(*getContext());
4247 Entry.isSExt = true;
4248 Args.push_back(Entry);
4250 Entry.Ty = IntPtrTy;
4251 Entry.isSExt = false;
4252 Args.push_back(Entry);
4253 // FIXME: pass in SDLoc
4255 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4256 false, false, false, false, 0,
4257 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4258 /*isTailCall=*/false,
4259 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4260 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4261 TLI->getPointerTy()),
4263 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4265 return CallResult.second;
4268 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4269 SDVTList VTList, ArrayRef<SDValue> Ops,
4270 MachineMemOperand *MMO,
4271 AtomicOrdering SuccessOrdering,
4272 AtomicOrdering FailureOrdering,
4273 SynchronizationScope SynchScope) {
4274 FoldingSetNodeID ID;
4275 ID.AddInteger(MemVT.getRawBits());
4276 AddNodeIDNode(ID, Opcode, VTList, Ops);
4277 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4279 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4280 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4281 return SDValue(E, 0);
4284 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4285 // SDNode doesn't have access to it. This memory will be "leaked" when
4286 // the node is deallocated, but recovered when the allocator is released.
4287 // If the number of operands is less than 5 we use AtomicSDNode's internal
4289 unsigned NumOps = Ops.size();
4290 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4293 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4294 dl.getDebugLoc(), VTList, MemVT,
4295 Ops.data(), DynOps, NumOps, MMO,
4296 SuccessOrdering, FailureOrdering,
4298 CSEMap.InsertNode(N, IP);
4299 AllNodes.push_back(N);
4300 return SDValue(N, 0);
4303 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4304 SDVTList VTList, ArrayRef<SDValue> Ops,
4305 MachineMemOperand *MMO,
4306 AtomicOrdering Ordering,
4307 SynchronizationScope SynchScope) {
4308 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4309 Ordering, SynchScope);
4312 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4313 SDValue Chain, SDValue Ptr, SDValue Cmp,
4314 SDValue Swp, MachinePointerInfo PtrInfo,
4316 AtomicOrdering SuccessOrdering,
4317 AtomicOrdering FailureOrdering,
4318 SynchronizationScope SynchScope) {
4319 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4320 Alignment = getEVTAlignment(MemVT);
4322 MachineFunction &MF = getMachineFunction();
4324 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4325 // For now, atomics are considered to be volatile always.
4326 // FIXME: Volatile isn't really correct; we should keep track of atomic
4327 // orderings in the memoperand.
4328 unsigned Flags = MachineMemOperand::MOVolatile;
4329 if (Opcode != ISD::ATOMIC_STORE)
4330 Flags |= MachineMemOperand::MOLoad;
4331 if (Opcode != ISD::ATOMIC_LOAD)
4332 Flags |= MachineMemOperand::MOStore;
4334 MachineMemOperand *MMO =
4335 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4337 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4338 SuccessOrdering, FailureOrdering, SynchScope);
4341 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4343 SDValue Ptr, SDValue Cmp,
4344 SDValue Swp, MachineMemOperand *MMO,
4345 AtomicOrdering SuccessOrdering,
4346 AtomicOrdering FailureOrdering,
4347 SynchronizationScope SynchScope) {
4348 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4349 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4351 EVT VT = Cmp.getValueType();
4353 SDVTList VTs = getVTList(VT, MVT::Other);
4354 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4355 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4356 FailureOrdering, SynchScope);
4359 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4361 SDValue Ptr, SDValue Val,
4362 const Value* PtrVal,
4364 AtomicOrdering Ordering,
4365 SynchronizationScope SynchScope) {
4366 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4367 Alignment = getEVTAlignment(MemVT);
4369 MachineFunction &MF = getMachineFunction();
4370 // An atomic store does not load. An atomic load does not store.
4371 // (An atomicrmw obviously both loads and stores.)
4372 // For now, atomics are considered to be volatile always, and they are
4374 // FIXME: Volatile isn't really correct; we should keep track of atomic
4375 // orderings in the memoperand.
4376 unsigned Flags = MachineMemOperand::MOVolatile;
4377 if (Opcode != ISD::ATOMIC_STORE)
4378 Flags |= MachineMemOperand::MOLoad;
4379 if (Opcode != ISD::ATOMIC_LOAD)
4380 Flags |= MachineMemOperand::MOStore;
4382 MachineMemOperand *MMO =
4383 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4384 MemVT.getStoreSize(), Alignment);
4386 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4387 Ordering, SynchScope);
4390 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4392 SDValue Ptr, SDValue Val,
4393 MachineMemOperand *MMO,
4394 AtomicOrdering Ordering,
4395 SynchronizationScope SynchScope) {
4396 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4397 Opcode == ISD::ATOMIC_LOAD_SUB ||
4398 Opcode == ISD::ATOMIC_LOAD_AND ||
4399 Opcode == ISD::ATOMIC_LOAD_OR ||
4400 Opcode == ISD::ATOMIC_LOAD_XOR ||
4401 Opcode == ISD::ATOMIC_LOAD_NAND ||
4402 Opcode == ISD::ATOMIC_LOAD_MIN ||
4403 Opcode == ISD::ATOMIC_LOAD_MAX ||
4404 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4405 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4406 Opcode == ISD::ATOMIC_SWAP ||
4407 Opcode == ISD::ATOMIC_STORE) &&
4408 "Invalid Atomic Op");
4410 EVT VT = Val.getValueType();
4412 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4413 getVTList(VT, MVT::Other);
4414 SDValue Ops[] = {Chain, Ptr, Val};
4415 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4418 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4419 EVT VT, SDValue Chain,
4421 MachineMemOperand *MMO,
4422 AtomicOrdering Ordering,
4423 SynchronizationScope SynchScope) {
4424 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4426 SDVTList VTs = getVTList(VT, MVT::Other);
4427 SDValue Ops[] = {Chain, Ptr};
4428 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4431 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4432 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4433 if (Ops.size() == 1)
4436 SmallVector<EVT, 4> VTs;
4437 VTs.reserve(Ops.size());
4438 for (unsigned i = 0; i < Ops.size(); ++i)
4439 VTs.push_back(Ops[i].getValueType());
4440 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4444 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4445 ArrayRef<SDValue> Ops,
4446 EVT MemVT, MachinePointerInfo PtrInfo,
4447 unsigned Align, bool Vol,
4448 bool ReadMem, bool WriteMem) {
4449 if (Align == 0) // Ensure that codegen never sees alignment 0
4450 Align = getEVTAlignment(MemVT);
4452 MachineFunction &MF = getMachineFunction();
4455 Flags |= MachineMemOperand::MOStore;
4457 Flags |= MachineMemOperand::MOLoad;
4459 Flags |= MachineMemOperand::MOVolatile;
4460 MachineMemOperand *MMO =
4461 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4463 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4467 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4468 ArrayRef<SDValue> Ops, EVT MemVT,
4469 MachineMemOperand *MMO) {
4470 assert((Opcode == ISD::INTRINSIC_VOID ||
4471 Opcode == ISD::INTRINSIC_W_CHAIN ||
4472 Opcode == ISD::PREFETCH ||
4473 Opcode == ISD::LIFETIME_START ||
4474 Opcode == ISD::LIFETIME_END ||
4475 (Opcode <= INT_MAX &&
4476 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4477 "Opcode is not a memory-accessing opcode!");
4479 // Memoize the node unless it returns a flag.
4480 MemIntrinsicSDNode *N;
4481 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4482 FoldingSetNodeID ID;
4483 AddNodeIDNode(ID, Opcode, VTList, Ops);
4484 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4486 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4487 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4488 return SDValue(E, 0);
4491 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4492 dl.getDebugLoc(), VTList, Ops,
4494 CSEMap.InsertNode(N, IP);
4496 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4497 dl.getDebugLoc(), VTList, Ops,
4500 AllNodes.push_back(N);
4501 return SDValue(N, 0);
4504 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4505 /// MachinePointerInfo record from it. This is particularly useful because the
4506 /// code generator has many cases where it doesn't bother passing in a
4507 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4508 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4509 // If this is FI+Offset, we can model it.
4510 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4511 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4513 // If this is (FI+Offset1)+Offset2, we can model it.
4514 if (Ptr.getOpcode() != ISD::ADD ||
4515 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4516 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4517 return MachinePointerInfo();
4519 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4520 return MachinePointerInfo::getFixedStack(FI, Offset+
4521 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4524 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4525 /// MachinePointerInfo record from it. This is particularly useful because the
4526 /// code generator has many cases where it doesn't bother passing in a
4527 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4528 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4529 // If the 'Offset' value isn't a constant, we can't handle this.
4530 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4531 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4532 if (OffsetOp.getOpcode() == ISD::UNDEF)
4533 return InferPointerInfo(Ptr);
4534 return MachinePointerInfo();
4539 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4540 EVT VT, SDLoc dl, SDValue Chain,
4541 SDValue Ptr, SDValue Offset,
4542 MachinePointerInfo PtrInfo, EVT MemVT,
4543 bool isVolatile, bool isNonTemporal, bool isInvariant,
4544 unsigned Alignment, const MDNode *TBAAInfo,
4545 const MDNode *Ranges) {
4546 assert(Chain.getValueType() == MVT::Other &&
4547 "Invalid chain type");
4548 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4549 Alignment = getEVTAlignment(VT);
4551 unsigned Flags = MachineMemOperand::MOLoad;
4553 Flags |= MachineMemOperand::MOVolatile;
4555 Flags |= MachineMemOperand::MONonTemporal;
4557 Flags |= MachineMemOperand::MOInvariant;
4559 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4561 if (PtrInfo.V.isNull())
4562 PtrInfo = InferPointerInfo(Ptr, Offset);
4564 MachineFunction &MF = getMachineFunction();
4565 MachineMemOperand *MMO =
4566 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4568 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4572 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4573 EVT VT, SDLoc dl, SDValue Chain,
4574 SDValue Ptr, SDValue Offset, EVT MemVT,
4575 MachineMemOperand *MMO) {
4577 ExtType = ISD::NON_EXTLOAD;
4578 } else if (ExtType == ISD::NON_EXTLOAD) {
4579 assert(VT == MemVT && "Non-extending load from different memory type!");
4582 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4583 "Should only be an extending load, not truncating!");
4584 assert(VT.isInteger() == MemVT.isInteger() &&
4585 "Cannot convert from FP to Int or Int -> FP!");
4586 assert(VT.isVector() == MemVT.isVector() &&
4587 "Cannot use trunc store to convert to or from a vector!");
4588 assert((!VT.isVector() ||
4589 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4590 "Cannot use trunc store to change the number of vector elements!");
4593 bool Indexed = AM != ISD::UNINDEXED;
4594 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4595 "Unindexed load with an offset!");
4597 SDVTList VTs = Indexed ?
4598 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4599 SDValue Ops[] = { Chain, Ptr, Offset };
4600 FoldingSetNodeID ID;
4601 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4602 ID.AddInteger(MemVT.getRawBits());
4603 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4604 MMO->isNonTemporal(),
4605 MMO->isInvariant()));
4606 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4609 cast<LoadSDNode>(E)->refineAlignment(MMO);
4610 return SDValue(E, 0);
4612 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4613 dl.getDebugLoc(), VTs, AM, ExtType,
4615 CSEMap.InsertNode(N, IP);
4616 AllNodes.push_back(N);
4617 return SDValue(N, 0);
4620 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4621 SDValue Chain, SDValue Ptr,
4622 MachinePointerInfo PtrInfo,
4623 bool isVolatile, bool isNonTemporal,
4624 bool isInvariant, unsigned Alignment,
4625 const MDNode *TBAAInfo,
4626 const MDNode *Ranges) {
4627 SDValue Undef = getUNDEF(Ptr.getValueType());
4628 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4629 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4633 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4634 SDValue Chain, SDValue Ptr,
4635 MachineMemOperand *MMO) {
4636 SDValue Undef = getUNDEF(Ptr.getValueType());
4637 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4641 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4642 SDValue Chain, SDValue Ptr,
4643 MachinePointerInfo PtrInfo, EVT MemVT,
4644 bool isVolatile, bool isNonTemporal,
4645 unsigned Alignment, const MDNode *TBAAInfo) {
4646 SDValue Undef = getUNDEF(Ptr.getValueType());
4647 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4648 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4653 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4654 SDValue Chain, SDValue Ptr, EVT MemVT,
4655 MachineMemOperand *MMO) {
4656 SDValue Undef = getUNDEF(Ptr.getValueType());
4657 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4662 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4663 SDValue Offset, ISD::MemIndexedMode AM) {
4664 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4665 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4666 "Load is already a indexed load!");
4667 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4668 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4669 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4670 false, LD->getAlignment());
4673 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4674 SDValue Ptr, MachinePointerInfo PtrInfo,
4675 bool isVolatile, bool isNonTemporal,
4676 unsigned Alignment, const MDNode *TBAAInfo) {
4677 assert(Chain.getValueType() == MVT::Other &&
4678 "Invalid chain type");
4679 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4680 Alignment = getEVTAlignment(Val.getValueType());
4682 unsigned Flags = MachineMemOperand::MOStore;
4684 Flags |= MachineMemOperand::MOVolatile;
4686 Flags |= MachineMemOperand::MONonTemporal;
4688 if (PtrInfo.V.isNull())
4689 PtrInfo = InferPointerInfo(Ptr);
4691 MachineFunction &MF = getMachineFunction();
4692 MachineMemOperand *MMO =
4693 MF.getMachineMemOperand(PtrInfo, Flags,
4694 Val.getValueType().getStoreSize(), Alignment,
4697 return getStore(Chain, dl, Val, Ptr, MMO);
4700 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4701 SDValue Ptr, MachineMemOperand *MMO) {
4702 assert(Chain.getValueType() == MVT::Other &&
4703 "Invalid chain type");
4704 EVT VT = Val.getValueType();
4705 SDVTList VTs = getVTList(MVT::Other);
4706 SDValue Undef = getUNDEF(Ptr.getValueType());
4707 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4708 FoldingSetNodeID ID;
4709 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4710 ID.AddInteger(VT.getRawBits());
4711 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4712 MMO->isNonTemporal(), MMO->isInvariant()));
4713 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4715 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4716 cast<StoreSDNode>(E)->refineAlignment(MMO);
4717 return SDValue(E, 0);
4719 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4720 dl.getDebugLoc(), VTs,
4721 ISD::UNINDEXED, false, VT, MMO);
4722 CSEMap.InsertNode(N, IP);
4723 AllNodes.push_back(N);
4724 return SDValue(N, 0);
4727 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4728 SDValue Ptr, MachinePointerInfo PtrInfo,
4729 EVT SVT,bool isVolatile, bool isNonTemporal,
4731 const MDNode *TBAAInfo) {
4732 assert(Chain.getValueType() == MVT::Other &&
4733 "Invalid chain type");
4734 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4735 Alignment = getEVTAlignment(SVT);
4737 unsigned Flags = MachineMemOperand::MOStore;
4739 Flags |= MachineMemOperand::MOVolatile;
4741 Flags |= MachineMemOperand::MONonTemporal;
4743 if (PtrInfo.V.isNull())
4744 PtrInfo = InferPointerInfo(Ptr);
4746 MachineFunction &MF = getMachineFunction();
4747 MachineMemOperand *MMO =
4748 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4751 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4754 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4755 SDValue Ptr, EVT SVT,
4756 MachineMemOperand *MMO) {
4757 EVT VT = Val.getValueType();
4759 assert(Chain.getValueType() == MVT::Other &&
4760 "Invalid chain type");
4762 return getStore(Chain, dl, Val, Ptr, MMO);
4764 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4765 "Should only be a truncating store, not extending!");
4766 assert(VT.isInteger() == SVT.isInteger() &&
4767 "Can't do FP-INT conversion!");
4768 assert(VT.isVector() == SVT.isVector() &&
4769 "Cannot use trunc store to convert to or from a vector!");
4770 assert((!VT.isVector() ||
4771 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4772 "Cannot use trunc store to change the number of vector elements!");
4774 SDVTList VTs = getVTList(MVT::Other);
4775 SDValue Undef = getUNDEF(Ptr.getValueType());
4776 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4777 FoldingSetNodeID ID;
4778 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4779 ID.AddInteger(SVT.getRawBits());
4780 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4781 MMO->isNonTemporal(), MMO->isInvariant()));
4782 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4784 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4785 cast<StoreSDNode>(E)->refineAlignment(MMO);
4786 return SDValue(E, 0);
4788 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4789 dl.getDebugLoc(), VTs,
4790 ISD::UNINDEXED, true, SVT, MMO);
4791 CSEMap.InsertNode(N, IP);
4792 AllNodes.push_back(N);
4793 return SDValue(N, 0);
4797 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4798 SDValue Offset, ISD::MemIndexedMode AM) {
4799 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4800 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4801 "Store is already a indexed store!");
4802 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4803 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4804 FoldingSetNodeID ID;
4805 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4806 ID.AddInteger(ST->getMemoryVT().getRawBits());
4807 ID.AddInteger(ST->getRawSubclassData());
4808 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4810 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4811 return SDValue(E, 0);
4813 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4814 dl.getDebugLoc(), VTs, AM,
4815 ST->isTruncatingStore(),
4817 ST->getMemOperand());
4818 CSEMap.InsertNode(N, IP);
4819 AllNodes.push_back(N);
4820 return SDValue(N, 0);
4823 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4824 SDValue Chain, SDValue Ptr,
4827 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4828 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4831 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4832 ArrayRef<SDUse> Ops) {
4833 switch (Ops.size()) {
4834 case 0: return getNode(Opcode, DL, VT);
4835 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4836 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4837 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4841 // Copy from an SDUse array into an SDValue array for use with
4842 // the regular getNode logic.
4843 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4844 return getNode(Opcode, DL, VT, NewOps);
4847 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4848 ArrayRef<SDValue> Ops) {
4849 unsigned NumOps = Ops.size();
4851 case 0: return getNode(Opcode, DL, VT);
4852 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4853 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4854 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4860 case ISD::SELECT_CC: {
4861 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4862 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4863 "LHS and RHS of condition must have same type!");
4864 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4865 "True and False arms of SelectCC must have same type!");
4866 assert(Ops[2].getValueType() == VT &&
4867 "select_cc node must be of same type as true and false value!");
4871 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4872 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4873 "LHS/RHS of comparison should match types!");
4880 SDVTList VTs = getVTList(VT);
4882 if (VT != MVT::Glue) {
4883 FoldingSetNodeID ID;
4884 AddNodeIDNode(ID, Opcode, VTs, Ops);
4887 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4888 return SDValue(E, 0);
4890 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4892 CSEMap.InsertNode(N, IP);
4894 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4898 AllNodes.push_back(N);
4902 return SDValue(N, 0);
4905 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4906 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4907 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4910 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4911 ArrayRef<SDValue> Ops) {
4912 if (VTList.NumVTs == 1)
4913 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4917 // FIXME: figure out how to safely handle things like
4918 // int foo(int x) { return 1 << (x & 255); }
4919 // int bar() { return foo(256); }
4920 case ISD::SRA_PARTS:
4921 case ISD::SRL_PARTS:
4922 case ISD::SHL_PARTS:
4923 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4924 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4925 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4926 else if (N3.getOpcode() == ISD::AND)
4927 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4928 // If the and is only masking out bits that cannot effect the shift,
4929 // eliminate the and.
4930 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4931 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4932 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4938 // Memoize the node unless it returns a flag.
4940 unsigned NumOps = Ops.size();
4941 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4942 FoldingSetNodeID ID;
4943 AddNodeIDNode(ID, Opcode, VTList, Ops);
4945 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4946 return SDValue(E, 0);
4949 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4950 DL.getDebugLoc(), VTList, Ops[0]);
4951 } else if (NumOps == 2) {
4952 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4953 DL.getDebugLoc(), VTList, Ops[0],
4955 } else if (NumOps == 3) {
4956 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4957 DL.getDebugLoc(), VTList, Ops[0],
4960 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4963 CSEMap.InsertNode(N, IP);
4966 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4967 DL.getDebugLoc(), VTList, Ops[0]);
4968 } else if (NumOps == 2) {
4969 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4970 DL.getDebugLoc(), VTList, Ops[0],
4972 } else if (NumOps == 3) {
4973 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4974 DL.getDebugLoc(), VTList, Ops[0],
4977 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4981 AllNodes.push_back(N);
4985 return SDValue(N, 0);
4988 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4989 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4992 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4994 SDValue Ops[] = { N1 };
4995 return getNode(Opcode, DL, VTList, Ops);
4998 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4999 SDValue N1, SDValue N2) {
5000 SDValue Ops[] = { N1, N2 };
5001 return getNode(Opcode, DL, VTList, Ops);
5004 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5005 SDValue N1, SDValue N2, SDValue N3) {
5006 SDValue Ops[] = { N1, N2, N3 };
5007 return getNode(Opcode, DL, VTList, Ops);
5010 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5011 SDValue N1, SDValue N2, SDValue N3,
5013 SDValue Ops[] = { N1, N2, N3, N4 };
5014 return getNode(Opcode, DL, VTList, Ops);
5017 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5018 SDValue N1, SDValue N2, SDValue N3,
5019 SDValue N4, SDValue N5) {
5020 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5021 return getNode(Opcode, DL, VTList, Ops);
5024 SDVTList SelectionDAG::getVTList(EVT VT) {
5025 return makeVTList(SDNode::getValueTypeList(VT), 1);
5028 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5029 FoldingSetNodeID ID;
5031 ID.AddInteger(VT1.getRawBits());
5032 ID.AddInteger(VT2.getRawBits());
5035 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5037 EVT *Array = Allocator.Allocate<EVT>(2);
5040 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5041 VTListMap.InsertNode(Result, IP);
5043 return Result->getSDVTList();
5046 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5047 FoldingSetNodeID ID;
5049 ID.AddInteger(VT1.getRawBits());
5050 ID.AddInteger(VT2.getRawBits());
5051 ID.AddInteger(VT3.getRawBits());
5054 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5056 EVT *Array = Allocator.Allocate<EVT>(3);
5060 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5061 VTListMap.InsertNode(Result, IP);
5063 return Result->getSDVTList();
5066 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5067 FoldingSetNodeID ID;
5069 ID.AddInteger(VT1.getRawBits());
5070 ID.AddInteger(VT2.getRawBits());
5071 ID.AddInteger(VT3.getRawBits());
5072 ID.AddInteger(VT4.getRawBits());
5075 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5077 EVT *Array = Allocator.Allocate<EVT>(4);
5082 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5083 VTListMap.InsertNode(Result, IP);
5085 return Result->getSDVTList();
5088 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5089 unsigned NumVTs = VTs.size();
5090 FoldingSetNodeID ID;
5091 ID.AddInteger(NumVTs);
5092 for (unsigned index = 0; index < NumVTs; index++) {
5093 ID.AddInteger(VTs[index].getRawBits());
5097 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5099 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5100 std::copy(VTs.begin(), VTs.end(), Array);
5101 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5102 VTListMap.InsertNode(Result, IP);
5104 return Result->getSDVTList();
5108 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5109 /// specified operands. If the resultant node already exists in the DAG,
5110 /// this does not modify the specified node, instead it returns the node that
5111 /// already exists. If the resultant node does not exist in the DAG, the
5112 /// input node is returned. As a degenerate case, if you specify the same
5113 /// input operands as the node already has, the input node is returned.
5114 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5115 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5117 // Check to see if there is no change.
5118 if (Op == N->getOperand(0)) return N;
5120 // See if the modified node already exists.
5121 void *InsertPos = nullptr;
5122 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5125 // Nope it doesn't. Remove the node from its current place in the maps.
5127 if (!RemoveNodeFromCSEMaps(N))
5128 InsertPos = nullptr;
5130 // Now we update the operands.
5131 N->OperandList[0].set(Op);
5133 // If this gets put into a CSE map, add it.
5134 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5138 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5139 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5141 // Check to see if there is no change.
5142 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5143 return N; // No operands changed, just return the input node.
5145 // See if the modified node already exists.
5146 void *InsertPos = nullptr;
5147 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5150 // Nope it doesn't. Remove the node from its current place in the maps.
5152 if (!RemoveNodeFromCSEMaps(N))
5153 InsertPos = nullptr;
5155 // Now we update the operands.
5156 if (N->OperandList[0] != Op1)
5157 N->OperandList[0].set(Op1);
5158 if (N->OperandList[1] != Op2)
5159 N->OperandList[1].set(Op2);
5161 // If this gets put into a CSE map, add it.
5162 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5166 SDNode *SelectionDAG::
5167 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5168 SDValue Ops[] = { Op1, Op2, Op3 };
5169 return UpdateNodeOperands(N, Ops);
5172 SDNode *SelectionDAG::
5173 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5174 SDValue Op3, SDValue Op4) {
5175 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5176 return UpdateNodeOperands(N, Ops);
5179 SDNode *SelectionDAG::
5180 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5181 SDValue Op3, SDValue Op4, SDValue Op5) {
5182 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5183 return UpdateNodeOperands(N, Ops);
5186 SDNode *SelectionDAG::
5187 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5188 unsigned NumOps = Ops.size();
5189 assert(N->getNumOperands() == NumOps &&
5190 "Update with wrong number of operands");
5192 // Check to see if there is no change.
5193 bool AnyChange = false;
5194 for (unsigned i = 0; i != NumOps; ++i) {
5195 if (Ops[i] != N->getOperand(i)) {
5201 // No operands changed, just return the input node.
5202 if (!AnyChange) return N;
5204 // See if the modified node already exists.
5205 void *InsertPos = nullptr;
5206 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5209 // Nope it doesn't. Remove the node from its current place in the maps.
5211 if (!RemoveNodeFromCSEMaps(N))
5212 InsertPos = nullptr;
5214 // Now we update the operands.
5215 for (unsigned i = 0; i != NumOps; ++i)
5216 if (N->OperandList[i] != Ops[i])
5217 N->OperandList[i].set(Ops[i]);
5219 // If this gets put into a CSE map, add it.
5220 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5224 /// DropOperands - Release the operands and set this node to have
5226 void SDNode::DropOperands() {
5227 // Unlike the code in MorphNodeTo that does this, we don't need to
5228 // watch for dead nodes here.
5229 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5235 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5238 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5240 SDVTList VTs = getVTList(VT);
5241 return SelectNodeTo(N, MachineOpc, VTs, None);
5244 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5245 EVT VT, SDValue Op1) {
5246 SDVTList VTs = getVTList(VT);
5247 SDValue Ops[] = { Op1 };
5248 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5251 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5252 EVT VT, SDValue Op1,
5254 SDVTList VTs = getVTList(VT);
5255 SDValue Ops[] = { Op1, Op2 };
5256 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5259 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5260 EVT VT, SDValue Op1,
5261 SDValue Op2, SDValue Op3) {
5262 SDVTList VTs = getVTList(VT);
5263 SDValue Ops[] = { Op1, Op2, Op3 };
5264 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5267 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5268 EVT VT, ArrayRef<SDValue> Ops) {
5269 SDVTList VTs = getVTList(VT);
5270 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5273 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5274 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5275 SDVTList VTs = getVTList(VT1, VT2);
5276 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5279 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5281 SDVTList VTs = getVTList(VT1, VT2);
5282 return SelectNodeTo(N, MachineOpc, VTs, None);
5285 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 EVT VT1, EVT VT2, EVT VT3,
5287 ArrayRef<SDValue> Ops) {
5288 SDVTList VTs = getVTList(VT1, VT2, VT3);
5289 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5294 ArrayRef<SDValue> Ops) {
5295 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5296 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5299 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 SDVTList VTs = getVTList(VT1, VT2);
5303 SDValue Ops[] = { Op1 };
5304 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5307 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5309 SDValue Op1, SDValue Op2) {
5310 SDVTList VTs = getVTList(VT1, VT2);
5311 SDValue Ops[] = { Op1, Op2 };
5312 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5315 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5317 SDValue Op1, SDValue Op2,
5319 SDVTList VTs = getVTList(VT1, VT2);
5320 SDValue Ops[] = { Op1, Op2, Op3 };
5321 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5324 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5325 EVT VT1, EVT VT2, EVT VT3,
5326 SDValue Op1, SDValue Op2,
5328 SDVTList VTs = getVTList(VT1, VT2, VT3);
5329 SDValue Ops[] = { Op1, Op2, Op3 };
5330 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5333 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5334 SDVTList VTs,ArrayRef<SDValue> Ops) {
5335 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5336 // Reset the NodeID to -1.
5341 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5342 /// the line number information on the merged node since it is not possible to
5343 /// preserve the information that operation is associated with multiple lines.
5344 /// This will make the debugger working better at -O0, were there is a higher
5345 /// probability having other instructions associated with that line.
5347 /// For IROrder, we keep the smaller of the two
5348 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5349 DebugLoc NLoc = N->getDebugLoc();
5350 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5351 (OLoc.getDebugLoc() != NLoc)) {
5352 N->setDebugLoc(DebugLoc());
5354 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5355 N->setIROrder(Order);
5359 /// MorphNodeTo - This *mutates* the specified node to have the specified
5360 /// return type, opcode, and operands.
5362 /// Note that MorphNodeTo returns the resultant node. If there is already a
5363 /// node of the specified opcode and operands, it returns that node instead of
5364 /// the current one. Note that the SDLoc need not be the same.
5366 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5367 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5368 /// node, and because it doesn't require CSE recalculation for any of
5369 /// the node's users.
5371 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5372 SDVTList VTs, ArrayRef<SDValue> Ops) {
5373 unsigned NumOps = Ops.size();
5374 // If an identical node already exists, use it.
5376 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5377 FoldingSetNodeID ID;
5378 AddNodeIDNode(ID, Opc, VTs, Ops);
5379 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5380 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5383 if (!RemoveNodeFromCSEMaps(N))
5386 // Start the morphing.
5388 N->ValueList = VTs.VTs;
5389 N->NumValues = VTs.NumVTs;
5391 // Clear the operands list, updating used nodes to remove this from their
5392 // use list. Keep track of any operands that become dead as a result.
5393 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5394 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5396 SDNode *Used = Use.getNode();
5398 if (Used->use_empty())
5399 DeadNodeSet.insert(Used);
5402 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5403 // Initialize the memory references information.
5404 MN->setMemRefs(nullptr, nullptr);
5405 // If NumOps is larger than the # of operands we can have in a
5406 // MachineSDNode, reallocate the operand list.
5407 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5408 if (MN->OperandsNeedDelete)
5409 delete[] MN->OperandList;
5410 if (NumOps > array_lengthof(MN->LocalOperands))
5411 // We're creating a final node that will live unmorphed for the
5412 // remainder of the current SelectionDAG iteration, so we can allocate
5413 // the operands directly out of a pool with no recycling metadata.
5414 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5415 Ops.data(), NumOps);
5417 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5418 MN->OperandsNeedDelete = false;
5420 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5422 // If NumOps is larger than the # of operands we currently have, reallocate
5423 // the operand list.
5424 if (NumOps > N->NumOperands) {
5425 if (N->OperandsNeedDelete)
5426 delete[] N->OperandList;
5427 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5428 N->OperandsNeedDelete = true;
5430 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5433 // Delete any nodes that are still dead after adding the uses for the
5435 if (!DeadNodeSet.empty()) {
5436 SmallVector<SDNode *, 16> DeadNodes;
5437 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5438 E = DeadNodeSet.end(); I != E; ++I)
5439 if ((*I)->use_empty())
5440 DeadNodes.push_back(*I);
5441 RemoveDeadNodes(DeadNodes);
5445 CSEMap.InsertNode(N, IP); // Memoize the new node.
5450 /// getMachineNode - These are used for target selectors to create a new node
5451 /// with specified return type(s), MachineInstr opcode, and operands.
5453 /// Note that getMachineNode returns the resultant node. If there is already a
5454 /// node of the specified opcode and operands, it returns that node instead of
5455 /// the current one.
5457 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5458 SDVTList VTs = getVTList(VT);
5459 return getMachineNode(Opcode, dl, VTs, None);
5463 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5464 SDVTList VTs = getVTList(VT);
5465 SDValue Ops[] = { Op1 };
5466 return getMachineNode(Opcode, dl, VTs, Ops);
5470 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5471 SDValue Op1, SDValue Op2) {
5472 SDVTList VTs = getVTList(VT);
5473 SDValue Ops[] = { Op1, Op2 };
5474 return getMachineNode(Opcode, dl, VTs, Ops);
5478 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5479 SDValue Op1, SDValue Op2, SDValue Op3) {
5480 SDVTList VTs = getVTList(VT);
5481 SDValue Ops[] = { Op1, Op2, Op3 };
5482 return getMachineNode(Opcode, dl, VTs, Ops);
5486 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5487 ArrayRef<SDValue> Ops) {
5488 SDVTList VTs = getVTList(VT);
5489 return getMachineNode(Opcode, dl, VTs, Ops);
5493 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5494 SDVTList VTs = getVTList(VT1, VT2);
5495 return getMachineNode(Opcode, dl, VTs, None);
5499 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5500 EVT VT1, EVT VT2, SDValue Op1) {
5501 SDVTList VTs = getVTList(VT1, VT2);
5502 SDValue Ops[] = { Op1 };
5503 return getMachineNode(Opcode, dl, VTs, Ops);
5507 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5508 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5509 SDVTList VTs = getVTList(VT1, VT2);
5510 SDValue Ops[] = { Op1, Op2 };
5511 return getMachineNode(Opcode, dl, VTs, Ops);
5515 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5516 EVT VT1, EVT VT2, SDValue Op1,
5517 SDValue Op2, SDValue Op3) {
5518 SDVTList VTs = getVTList(VT1, VT2);
5519 SDValue Ops[] = { Op1, Op2, Op3 };
5520 return getMachineNode(Opcode, dl, VTs, Ops);
5524 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5526 ArrayRef<SDValue> Ops) {
5527 SDVTList VTs = getVTList(VT1, VT2);
5528 return getMachineNode(Opcode, dl, VTs, Ops);
5532 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5533 EVT VT1, EVT VT2, EVT VT3,
5534 SDValue Op1, SDValue Op2) {
5535 SDVTList VTs = getVTList(VT1, VT2, VT3);
5536 SDValue Ops[] = { Op1, Op2 };
5537 return getMachineNode(Opcode, dl, VTs, Ops);
5541 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5542 EVT VT1, EVT VT2, EVT VT3,
5543 SDValue Op1, SDValue Op2, SDValue Op3) {
5544 SDVTList VTs = getVTList(VT1, VT2, VT3);
5545 SDValue Ops[] = { Op1, Op2, Op3 };
5546 return getMachineNode(Opcode, dl, VTs, Ops);
5550 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5551 EVT VT1, EVT VT2, EVT VT3,
5552 ArrayRef<SDValue> Ops) {
5553 SDVTList VTs = getVTList(VT1, VT2, VT3);
5554 return getMachineNode(Opcode, dl, VTs, Ops);
5558 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5559 EVT VT2, EVT VT3, EVT VT4,
5560 ArrayRef<SDValue> Ops) {
5561 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5562 return getMachineNode(Opcode, dl, VTs, Ops);
5566 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5567 ArrayRef<EVT> ResultTys,
5568 ArrayRef<SDValue> Ops) {
5569 SDVTList VTs = getVTList(ResultTys);
5570 return getMachineNode(Opcode, dl, VTs, Ops);
5574 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5575 ArrayRef<SDValue> OpsArray) {
5576 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5579 const SDValue *Ops = OpsArray.data();
5580 unsigned NumOps = OpsArray.size();
5583 FoldingSetNodeID ID;
5584 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5586 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5587 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5591 // Allocate a new MachineSDNode.
5592 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5593 DL.getDebugLoc(), VTs);
5595 // Initialize the operands list.
5596 if (NumOps > array_lengthof(N->LocalOperands))
5597 // We're creating a final node that will live unmorphed for the
5598 // remainder of the current SelectionDAG iteration, so we can allocate
5599 // the operands directly out of a pool with no recycling metadata.
5600 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5603 N->InitOperands(N->LocalOperands, Ops, NumOps);
5604 N->OperandsNeedDelete = false;
5607 CSEMap.InsertNode(N, IP);
5609 AllNodes.push_back(N);
5611 VerifyMachineNode(N);
5616 /// getTargetExtractSubreg - A convenience function for creating
5617 /// TargetOpcode::EXTRACT_SUBREG nodes.
5619 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5621 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5622 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5623 VT, Operand, SRIdxVal);
5624 return SDValue(Subreg, 0);
5627 /// getTargetInsertSubreg - A convenience function for creating
5628 /// TargetOpcode::INSERT_SUBREG nodes.
5630 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5631 SDValue Operand, SDValue Subreg) {
5632 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5633 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5634 VT, Operand, Subreg, SRIdxVal);
5635 return SDValue(Result, 0);
5638 /// getNodeIfExists - Get the specified node if it's already available, or
5639 /// else return NULL.
5640 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5641 ArrayRef<SDValue> Ops) {
5642 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5643 FoldingSetNodeID ID;
5644 AddNodeIDNode(ID, Opcode, VTList, Ops);
5646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5652 /// getDbgValue - Creates a SDDbgValue node.
5656 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5657 bool IsIndirect, uint64_t Off,
5658 DebugLoc DL, unsigned O) {
5659 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5664 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5666 DebugLoc DL, unsigned O) {
5667 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5672 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5673 DebugLoc DL, unsigned O) {
5674 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5679 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5680 /// pointed to by a use iterator is deleted, increment the use iterator
5681 /// so that it doesn't dangle.
5683 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5684 SDNode::use_iterator &UI;
5685 SDNode::use_iterator &UE;
5687 void NodeDeleted(SDNode *N, SDNode *E) override {
5688 // Increment the iterator as needed.
5689 while (UI != UE && N == *UI)
5694 RAUWUpdateListener(SelectionDAG &d,
5695 SDNode::use_iterator &ui,
5696 SDNode::use_iterator &ue)
5697 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5702 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5703 /// This can cause recursive merging of nodes in the DAG.
5705 /// This version assumes From has a single result value.
5707 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5708 SDNode *From = FromN.getNode();
5709 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5710 "Cannot replace with this method!");
5711 assert(From != To.getNode() && "Cannot replace uses of with self");
5713 // Iterate over all the existing uses of From. New uses will be added
5714 // to the beginning of the use list, which we avoid visiting.
5715 // This specifically avoids visiting uses of From that arise while the
5716 // replacement is happening, because any such uses would be the result
5717 // of CSE: If an existing node looks like From after one of its operands
5718 // is replaced by To, we don't want to replace of all its users with To
5719 // too. See PR3018 for more info.
5720 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5721 RAUWUpdateListener Listener(*this, UI, UE);
5725 // This node is about to morph, remove its old self from the CSE maps.
5726 RemoveNodeFromCSEMaps(User);
5728 // A user can appear in a use list multiple times, and when this
5729 // happens the uses are usually next to each other in the list.
5730 // To help reduce the number of CSE recomputations, process all
5731 // the uses of this user that we can find this way.
5733 SDUse &Use = UI.getUse();
5736 } while (UI != UE && *UI == User);
5738 // Now that we have modified User, add it back to the CSE maps. If it
5739 // already exists there, recursively merge the results together.
5740 AddModifiedNodeToCSEMaps(User);
5743 // If we just RAUW'd the root, take note.
5744 if (FromN == getRoot())
5748 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5749 /// This can cause recursive merging of nodes in the DAG.
5751 /// This version assumes that for each value of From, there is a
5752 /// corresponding value in To in the same position with the same type.
5754 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5756 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5757 assert((!From->hasAnyUseOfValue(i) ||
5758 From->getValueType(i) == To->getValueType(i)) &&
5759 "Cannot use this version of ReplaceAllUsesWith!");
5762 // Handle the trivial case.
5766 // Iterate over just the existing users of From. See the comments in
5767 // the ReplaceAllUsesWith above.
5768 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5769 RAUWUpdateListener Listener(*this, UI, UE);
5773 // This node is about to morph, remove its old self from the CSE maps.
5774 RemoveNodeFromCSEMaps(User);
5776 // A user can appear in a use list multiple times, and when this
5777 // happens the uses are usually next to each other in the list.
5778 // To help reduce the number of CSE recomputations, process all
5779 // the uses of this user that we can find this way.
5781 SDUse &Use = UI.getUse();
5784 } while (UI != UE && *UI == User);
5786 // Now that we have modified User, add it back to the CSE maps. If it
5787 // already exists there, recursively merge the results together.
5788 AddModifiedNodeToCSEMaps(User);
5791 // If we just RAUW'd the root, take note.
5792 if (From == getRoot().getNode())
5793 setRoot(SDValue(To, getRoot().getResNo()));
5796 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5797 /// This can cause recursive merging of nodes in the DAG.
5799 /// This version can replace From with any result values. To must match the
5800 /// number and types of values returned by From.
5801 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5802 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5803 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5805 // Iterate over just the existing users of From. See the comments in
5806 // the ReplaceAllUsesWith above.
5807 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5808 RAUWUpdateListener Listener(*this, UI, UE);
5812 // This node is about to morph, remove its old self from the CSE maps.
5813 RemoveNodeFromCSEMaps(User);
5815 // A user can appear in a use list multiple times, and when this
5816 // happens the uses are usually next to each other in the list.
5817 // To help reduce the number of CSE recomputations, process all
5818 // the uses of this user that we can find this way.
5820 SDUse &Use = UI.getUse();
5821 const SDValue &ToOp = To[Use.getResNo()];
5824 } while (UI != UE && *UI == User);
5826 // Now that we have modified User, add it back to the CSE maps. If it
5827 // already exists there, recursively merge the results together.
5828 AddModifiedNodeToCSEMaps(User);
5831 // If we just RAUW'd the root, take note.
5832 if (From == getRoot().getNode())
5833 setRoot(SDValue(To[getRoot().getResNo()]));
5836 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5837 /// uses of other values produced by From.getNode() alone. The Deleted
5838 /// vector is handled the same way as for ReplaceAllUsesWith.
5839 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5840 // Handle the really simple, really trivial case efficiently.
5841 if (From == To) return;
5843 // Handle the simple, trivial, case efficiently.
5844 if (From.getNode()->getNumValues() == 1) {
5845 ReplaceAllUsesWith(From, To);
5849 // Iterate over just the existing users of From. See the comments in
5850 // the ReplaceAllUsesWith above.
5851 SDNode::use_iterator UI = From.getNode()->use_begin(),
5852 UE = From.getNode()->use_end();
5853 RAUWUpdateListener Listener(*this, UI, UE);
5856 bool UserRemovedFromCSEMaps = false;
5858 // A user can appear in a use list multiple times, and when this
5859 // happens the uses are usually next to each other in the list.
5860 // To help reduce the number of CSE recomputations, process all
5861 // the uses of this user that we can find this way.
5863 SDUse &Use = UI.getUse();
5865 // Skip uses of different values from the same node.
5866 if (Use.getResNo() != From.getResNo()) {
5871 // If this node hasn't been modified yet, it's still in the CSE maps,
5872 // so remove its old self from the CSE maps.
5873 if (!UserRemovedFromCSEMaps) {
5874 RemoveNodeFromCSEMaps(User);
5875 UserRemovedFromCSEMaps = true;
5880 } while (UI != UE && *UI == User);
5882 // We are iterating over all uses of the From node, so if a use
5883 // doesn't use the specific value, no changes are made.
5884 if (!UserRemovedFromCSEMaps)
5887 // Now that we have modified User, add it back to the CSE maps. If it
5888 // already exists there, recursively merge the results together.
5889 AddModifiedNodeToCSEMaps(User);
5892 // If we just RAUW'd the root, take note.
5893 if (From == getRoot())
5898 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5899 /// to record information about a use.
5906 /// operator< - Sort Memos by User.
5907 bool operator<(const UseMemo &L, const UseMemo &R) {
5908 return (intptr_t)L.User < (intptr_t)R.User;
5912 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5913 /// uses of other values produced by From.getNode() alone. The same value
5914 /// may appear in both the From and To list. The Deleted vector is
5915 /// handled the same way as for ReplaceAllUsesWith.
5916 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5919 // Handle the simple, trivial case efficiently.
5921 return ReplaceAllUsesOfValueWith(*From, *To);
5923 // Read up all the uses and make records of them. This helps
5924 // processing new uses that are introduced during the
5925 // replacement process.
5926 SmallVector<UseMemo, 4> Uses;
5927 for (unsigned i = 0; i != Num; ++i) {
5928 unsigned FromResNo = From[i].getResNo();
5929 SDNode *FromNode = From[i].getNode();
5930 for (SDNode::use_iterator UI = FromNode->use_begin(),
5931 E = FromNode->use_end(); UI != E; ++UI) {
5932 SDUse &Use = UI.getUse();
5933 if (Use.getResNo() == FromResNo) {
5934 UseMemo Memo = { *UI, i, &Use };
5935 Uses.push_back(Memo);
5940 // Sort the uses, so that all the uses from a given User are together.
5941 std::sort(Uses.begin(), Uses.end());
5943 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5944 UseIndex != UseIndexEnd; ) {
5945 // We know that this user uses some value of From. If it is the right
5946 // value, update it.
5947 SDNode *User = Uses[UseIndex].User;
5949 // This node is about to morph, remove its old self from the CSE maps.
5950 RemoveNodeFromCSEMaps(User);
5952 // The Uses array is sorted, so all the uses for a given User
5953 // are next to each other in the list.
5954 // To help reduce the number of CSE recomputations, process all
5955 // the uses of this user that we can find this way.
5957 unsigned i = Uses[UseIndex].Index;
5958 SDUse &Use = *Uses[UseIndex].Use;
5962 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5964 // Now that we have modified User, add it back to the CSE maps. If it
5965 // already exists there, recursively merge the results together.
5966 AddModifiedNodeToCSEMaps(User);
5970 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5971 /// based on their topological order. It returns the maximum id and a vector
5972 /// of the SDNodes* in assigned order by reference.
5973 unsigned SelectionDAG::AssignTopologicalOrder() {
5975 unsigned DAGSize = 0;
5977 // SortedPos tracks the progress of the algorithm. Nodes before it are
5978 // sorted, nodes after it are unsorted. When the algorithm completes
5979 // it is at the end of the list.
5980 allnodes_iterator SortedPos = allnodes_begin();
5982 // Visit all the nodes. Move nodes with no operands to the front of
5983 // the list immediately. Annotate nodes that do have operands with their
5984 // operand count. Before we do this, the Node Id fields of the nodes
5985 // may contain arbitrary values. After, the Node Id fields for nodes
5986 // before SortedPos will contain the topological sort index, and the
5987 // Node Id fields for nodes At SortedPos and after will contain the
5988 // count of outstanding operands.
5989 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5992 unsigned Degree = N->getNumOperands();
5994 // A node with no uses, add it to the result array immediately.
5995 N->setNodeId(DAGSize++);
5996 allnodes_iterator Q = N;
5998 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5999 assert(SortedPos != AllNodes.end() && "Overran node list");
6002 // Temporarily use the Node Id as scratch space for the degree count.
6003 N->setNodeId(Degree);
6007 // Visit all the nodes. As we iterate, move nodes into sorted order,
6008 // such that by the time the end is reached all nodes will be sorted.
6009 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6012 // N is in sorted position, so all its uses have one less operand
6013 // that needs to be sorted.
6014 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6017 unsigned Degree = P->getNodeId();
6018 assert(Degree != 0 && "Invalid node degree");
6021 // All of P's operands are sorted, so P may sorted now.
6022 P->setNodeId(DAGSize++);
6024 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6025 assert(SortedPos != AllNodes.end() && "Overran node list");
6028 // Update P's outstanding operand count.
6029 P->setNodeId(Degree);
6032 if (I == SortedPos) {
6035 dbgs() << "Overran sorted position:\n";
6038 llvm_unreachable(nullptr);
6042 assert(SortedPos == AllNodes.end() &&
6043 "Topological sort incomplete!");
6044 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6045 "First node in topological sort is not the entry token!");
6046 assert(AllNodes.front().getNodeId() == 0 &&
6047 "First node in topological sort has non-zero id!");
6048 assert(AllNodes.front().getNumOperands() == 0 &&
6049 "First node in topological sort has operands!");
6050 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6051 "Last node in topologic sort has unexpected id!");
6052 assert(AllNodes.back().use_empty() &&
6053 "Last node in topologic sort has users!");
6054 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6058 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6059 /// value is produced by SD.
6060 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6061 DbgInfo->add(DB, SD, isParameter);
6063 SD->setHasDebugValue(true);
6066 /// TransferDbgValues - Transfer SDDbgValues.
6067 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6068 if (From == To || !From.getNode()->getHasDebugValue())
6070 SDNode *FromNode = From.getNode();
6071 SDNode *ToNode = To.getNode();
6072 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6073 SmallVector<SDDbgValue *, 2> ClonedDVs;
6074 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6076 SDDbgValue *Dbg = *I;
6077 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6078 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6080 Dbg->getOffset(), Dbg->getDebugLoc(),
6082 ClonedDVs.push_back(Clone);
6085 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6086 E = ClonedDVs.end(); I != E; ++I)
6087 AddDbgValue(*I, ToNode, false);
6090 //===----------------------------------------------------------------------===//
6092 //===----------------------------------------------------------------------===//
6094 HandleSDNode::~HandleSDNode() {
6098 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6099 DebugLoc DL, const GlobalValue *GA,
6100 EVT VT, int64_t o, unsigned char TF)
6101 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6105 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6106 SDValue X, unsigned SrcAS,
6108 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6109 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6111 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6112 EVT memvt, MachineMemOperand *mmo)
6113 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6114 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6115 MMO->isNonTemporal(), MMO->isInvariant());
6116 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6117 assert(isNonTemporal() == MMO->isNonTemporal() &&
6118 "Non-temporal encoding error!");
6119 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6122 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6123 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6124 : SDNode(Opc, Order, dl, VTs, Ops),
6125 MemoryVT(memvt), MMO(mmo) {
6126 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6127 MMO->isNonTemporal(), MMO->isInvariant());
6128 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6129 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6132 /// Profile - Gather unique data for the node.
6134 void SDNode::Profile(FoldingSetNodeID &ID) const {
6135 AddNodeIDNode(ID, this);
6140 std::vector<EVT> VTs;
6143 VTs.reserve(MVT::LAST_VALUETYPE);
6144 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6145 VTs.push_back(MVT((MVT::SimpleValueType)i));
6150 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6151 static ManagedStatic<EVTArray> SimpleVTArray;
6152 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6154 /// getValueTypeList - Return a pointer to the specified value type.
6156 const EVT *SDNode::getValueTypeList(EVT VT) {
6157 if (VT.isExtended()) {
6158 sys::SmartScopedLock<true> Lock(*VTMutex);
6159 return &(*EVTs->insert(VT).first);
6161 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6162 "Value type out of range!");
6163 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6167 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6168 /// indicated value. This method ignores uses of other values defined by this
6170 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6171 assert(Value < getNumValues() && "Bad value!");
6173 // TODO: Only iterate over uses of a given value of the node
6174 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6175 if (UI.getUse().getResNo() == Value) {
6182 // Found exactly the right number of uses?
6187 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6188 /// value. This method ignores uses of other values defined by this operation.
6189 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6190 assert(Value < getNumValues() && "Bad value!");
6192 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6193 if (UI.getUse().getResNo() == Value)
6200 /// isOnlyUserOf - Return true if this node is the only use of N.
6202 bool SDNode::isOnlyUserOf(SDNode *N) const {
6204 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6215 /// isOperand - Return true if this node is an operand of N.
6217 bool SDValue::isOperandOf(SDNode *N) const {
6218 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6219 if (*this == N->getOperand(i))
6224 bool SDNode::isOperandOf(SDNode *N) const {
6225 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6226 if (this == N->OperandList[i].getNode())
6231 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6232 /// be a chain) reaches the specified operand without crossing any
6233 /// side-effecting instructions on any chain path. In practice, this looks
6234 /// through token factors and non-volatile loads. In order to remain efficient,
6235 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6236 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6237 unsigned Depth) const {
6238 if (*this == Dest) return true;
6240 // Don't search too deeply, we just want to be able to see through
6241 // TokenFactor's etc.
6242 if (Depth == 0) return false;
6244 // If this is a token factor, all inputs to the TF happen in parallel. If any
6245 // of the operands of the TF does not reach dest, then we cannot do the xform.
6246 if (getOpcode() == ISD::TokenFactor) {
6247 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6248 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6253 // Loads don't have side effects, look through them.
6254 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6255 if (!Ld->isVolatile())
6256 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6261 /// hasPredecessor - Return true if N is a predecessor of this node.
6262 /// N is either an operand of this node, or can be reached by recursively
6263 /// traversing up the operands.
6264 /// NOTE: This is an expensive method. Use it carefully.
6265 bool SDNode::hasPredecessor(const SDNode *N) const {
6266 SmallPtrSet<const SDNode *, 32> Visited;
6267 SmallVector<const SDNode *, 16> Worklist;
6268 return hasPredecessorHelper(N, Visited, Worklist);
6272 SDNode::hasPredecessorHelper(const SDNode *N,
6273 SmallPtrSet<const SDNode *, 32> &Visited,
6274 SmallVectorImpl<const SDNode *> &Worklist) const {
6275 if (Visited.empty()) {
6276 Worklist.push_back(this);
6278 // Take a look in the visited set. If we've already encountered this node
6279 // we needn't search further.
6280 if (Visited.count(N))
6284 // Haven't visited N yet. Continue the search.
6285 while (!Worklist.empty()) {
6286 const SDNode *M = Worklist.pop_back_val();
6287 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6288 SDNode *Op = M->getOperand(i).getNode();
6289 if (Visited.insert(Op))
6290 Worklist.push_back(Op);
6299 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6300 assert(Num < NumOperands && "Invalid child # of SDNode!");
6301 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6304 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6305 assert(N->getNumValues() == 1 &&
6306 "Can't unroll a vector with multiple results!");
6308 EVT VT = N->getValueType(0);
6309 unsigned NE = VT.getVectorNumElements();
6310 EVT EltVT = VT.getVectorElementType();
6313 SmallVector<SDValue, 8> Scalars;
6314 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6316 // If ResNE is 0, fully unroll the vector op.
6319 else if (NE > ResNE)
6323 for (i= 0; i != NE; ++i) {
6324 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6325 SDValue Operand = N->getOperand(j);
6326 EVT OperandVT = Operand.getValueType();
6327 if (OperandVT.isVector()) {
6328 // A vector operand; extract a single element.
6329 const TargetLowering *TLI = TM.getTargetLowering();
6330 EVT OperandEltVT = OperandVT.getVectorElementType();
6331 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6334 getConstant(i, TLI->getVectorIdxTy()));
6336 // A scalar operand; just use it as is.
6337 Operands[j] = Operand;
6341 switch (N->getOpcode()) {
6343 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6346 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6353 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6354 getShiftAmountOperand(Operands[0].getValueType(),
6357 case ISD::SIGN_EXTEND_INREG:
6358 case ISD::FP_ROUND_INREG: {
6359 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6360 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6362 getValueType(ExtVT)));
6367 for (; i < ResNE; ++i)
6368 Scalars.push_back(getUNDEF(EltVT));
6370 return getNode(ISD::BUILD_VECTOR, dl,
6371 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6375 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6376 /// location that is 'Dist' units away from the location that the 'Base' load
6377 /// is loading from.
6378 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6379 unsigned Bytes, int Dist) const {
6380 if (LD->getChain() != Base->getChain())
6382 EVT VT = LD->getValueType(0);
6383 if (VT.getSizeInBits() / 8 != Bytes)
6386 SDValue Loc = LD->getOperand(1);
6387 SDValue BaseLoc = Base->getOperand(1);
6388 if (Loc.getOpcode() == ISD::FrameIndex) {
6389 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6391 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6392 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6393 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6394 int FS = MFI->getObjectSize(FI);
6395 int BFS = MFI->getObjectSize(BFI);
6396 if (FS != BFS || FS != (int)Bytes) return false;
6397 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6401 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6402 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6405 const GlobalValue *GV1 = nullptr;
6406 const GlobalValue *GV2 = nullptr;
6407 int64_t Offset1 = 0;
6408 int64_t Offset2 = 0;
6409 const TargetLowering *TLI = TM.getTargetLowering();
6410 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6411 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6412 if (isGA1 && isGA2 && GV1 == GV2)
6413 return Offset1 == (Offset2 + Dist*Bytes);
6418 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6419 /// it cannot be inferred.
6420 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6421 // If this is a GlobalAddress + cst, return the alignment.
6422 const GlobalValue *GV;
6423 int64_t GVOffset = 0;
6424 const TargetLowering *TLI = TM.getTargetLowering();
6425 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6426 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6427 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6428 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6429 TLI->getDataLayout());
6430 unsigned AlignBits = KnownZero.countTrailingOnes();
6431 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6433 return MinAlign(Align, GVOffset);
6436 // If this is a direct reference to a stack slot, use information about the
6437 // stack slot's alignment.
6438 int FrameIdx = 1 << 31;
6439 int64_t FrameOffset = 0;
6440 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6441 FrameIdx = FI->getIndex();
6442 } else if (isBaseWithConstantOffset(Ptr) &&
6443 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6445 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6446 FrameOffset = Ptr.getConstantOperandVal(1);
6449 if (FrameIdx != (1 << 31)) {
6450 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6451 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6459 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6460 /// which is split (or expanded) into two not necessarily identical pieces.
6461 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6462 // Currently all types are split in half.
6464 if (!VT.isVector()) {
6465 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6467 unsigned NumElements = VT.getVectorNumElements();
6468 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6469 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6472 return std::make_pair(LoVT, HiVT);
6475 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6477 std::pair<SDValue, SDValue>
6478 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6480 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6481 N.getValueType().getVectorNumElements() &&
6482 "More vector elements requested than available!");
6484 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6485 getConstant(0, TLI->getVectorIdxTy()));
6486 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6487 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6488 return std::make_pair(Lo, Hi);
6491 void SelectionDAG::ExtractVectorElements(SDValue Op,
6492 SmallVectorImpl<SDValue> &Args,
6493 unsigned Start, unsigned Count) {
6494 EVT VT = Op.getValueType();
6496 Count = VT.getVectorNumElements();
6498 EVT EltVT = VT.getVectorElementType();
6499 EVT IdxTy = TLI->getVectorIdxTy();
6501 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6502 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6503 Op, getConstant(i, IdxTy)));
6507 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6508 unsigned GlobalAddressSDNode::getAddressSpace() const {
6509 return getGlobal()->getType()->getAddressSpace();
6513 Type *ConstantPoolSDNode::getType() const {
6514 if (isMachineConstantPoolEntry())
6515 return Val.MachineCPVal->getType();
6516 return Val.ConstVal->getType();
6519 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6521 unsigned &SplatBitSize,
6523 unsigned MinSplatBits,
6524 bool isBigEndian) const {
6525 EVT VT = getValueType(0);
6526 assert(VT.isVector() && "Expected a vector type");
6527 unsigned sz = VT.getSizeInBits();
6528 if (MinSplatBits > sz)
6531 SplatValue = APInt(sz, 0);
6532 SplatUndef = APInt(sz, 0);
6534 // Get the bits. Bits with undefined values (when the corresponding element
6535 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6536 // in SplatValue. If any of the values are not constant, give up and return
6538 unsigned int nOps = getNumOperands();
6539 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6540 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6542 for (unsigned j = 0; j < nOps; ++j) {
6543 unsigned i = isBigEndian ? nOps-1-j : j;
6544 SDValue OpVal = getOperand(i);
6545 unsigned BitPos = j * EltBitSize;
6547 if (OpVal.getOpcode() == ISD::UNDEF)
6548 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6549 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6550 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6551 zextOrTrunc(sz) << BitPos;
6552 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6553 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6558 // The build_vector is all constants or undefs. Find the smallest element
6559 // size that splats the vector.
6561 HasAnyUndefs = (SplatUndef != 0);
6564 unsigned HalfSize = sz / 2;
6565 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6566 APInt LowValue = SplatValue.trunc(HalfSize);
6567 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6568 APInt LowUndef = SplatUndef.trunc(HalfSize);
6570 // If the two halves do not match (ignoring undef bits), stop here.
6571 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6572 MinSplatBits > HalfSize)
6575 SplatValue = HighValue | LowValue;
6576 SplatUndef = HighUndef & LowUndef;
6585 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6586 SDValue Op0 = getOperand(0);
6587 if (Op0.getOpcode() != ISD::Constant)
6590 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6591 if (getOperand(i) != Op0)
6594 return cast<ConstantSDNode>(Op0);
6597 bool BuildVectorSDNode::isConstant() const {
6598 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6599 unsigned Opc = getOperand(i).getOpcode();
6600 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6606 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6607 // Find the first non-undef value in the shuffle mask.
6609 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6612 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6614 // Make sure all remaining elements are either undef or the same as the first
6616 for (int Idx = Mask[i]; i != e; ++i)
6617 if (Mask[i] >= 0 && Mask[i] != Idx)
6623 static void checkForCyclesHelper(const SDNode *N,
6624 SmallPtrSet<const SDNode*, 32> &Visited,
6625 SmallPtrSet<const SDNode*, 32> &Checked) {
6626 // If this node has already been checked, don't check it again.
6627 if (Checked.count(N))
6630 // If a node has already been visited on this depth-first walk, reject it as
6632 if (!Visited.insert(N)) {
6633 dbgs() << "Offending node:\n";
6635 errs() << "Detected cycle in SelectionDAG\n";
6639 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6640 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6647 void llvm::checkForCycles(const llvm::SDNode *N) {
6649 assert(N && "Checking nonexistent SDNode");
6650 SmallPtrSet<const SDNode*, 32> visited;
6651 SmallPtrSet<const SDNode*, 32> checked;
6652 checkForCyclesHelper(N, visited, checked);
6656 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6657 checkForCycles(DAG->getRoot().getNode());