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::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
996 EVT EltVT = VT.getScalarType();
997 assert((EltVT.getSizeInBits() >= 64 ||
998 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
999 "getConstant with a uint64_t value that doesn't fit in the type!");
1000 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1003 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1005 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1008 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1010 assert(VT.isInteger() && "Cannot create FP integer constant!");
1012 EVT EltVT = VT.getScalarType();
1013 const ConstantInt *Elt = &Val;
1015 const TargetLowering *TLI = TM.getTargetLowering();
1017 // In some cases the vector type is legal but the element type is illegal and
1018 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1019 // inserted value (the type does not need to match the vector element type).
1020 // Any extra bits introduced will be truncated away.
1021 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1022 TargetLowering::TypePromoteInteger) {
1023 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1024 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1025 Elt = ConstantInt::get(*getContext(), NewVal);
1027 // In other cases the element type is illegal and needs to be expanded, for
1028 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1029 // the value into n parts and use a vector type with n-times the elements.
1030 // Then bitcast to the type requested.
1031 // Legalizing constants too early makes the DAGCombiner's job harder so we
1032 // only legalize if the DAG tells us we must produce legal types.
1033 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1034 TLI->getTypeAction(*getContext(), EltVT) ==
1035 TargetLowering::TypeExpandInteger) {
1036 APInt NewVal = Elt->getValue();
1037 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1038 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1039 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1040 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1042 // Check the temporary vector is the correct size. If this fails then
1043 // getTypeToTransformTo() probably returned a type whose size (in bits)
1044 // isn't a power-of-2 factor of the requested type size.
1045 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1047 SmallVector<SDValue, 2> EltParts;
1048 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1049 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1050 .trunc(ViaEltSizeInBits),
1051 ViaEltVT, isT, isO));
1054 // EltParts is currently in little endian order. If we actually want
1055 // big-endian order then reverse it now.
1056 if (TLI->isBigEndian())
1057 std::reverse(EltParts.begin(), EltParts.end());
1059 // The elements must be reversed when the element order is different
1060 // to the endianness of the elements (because the BITCAST is itself a
1061 // vector shuffle in this situation). However, we do not need any code to
1062 // perform this reversal because getConstant() is producing a vector
1064 // This situation occurs in MIPS MSA.
1066 SmallVector<SDValue, 8> Ops;
1067 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1068 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1070 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1071 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1076 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1077 "APInt size does not match type size!");
1078 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1079 FoldingSetNodeID ID;
1080 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1084 SDNode *N = nullptr;
1085 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1087 return SDValue(N, 0);
1090 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1091 CSEMap.InsertNode(N, IP);
1092 AllNodes.push_back(N);
1095 SDValue Result(N, 0);
1096 if (VT.isVector()) {
1097 SmallVector<SDValue, 8> Ops;
1098 Ops.assign(VT.getVectorNumElements(), Result);
1099 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1104 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1105 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1109 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1110 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1113 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1114 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1116 EVT EltVT = VT.getScalarType();
1118 // Do the map lookup using the actual bit pattern for the floating point
1119 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1120 // we don't have issues with SNANs.
1121 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1122 FoldingSetNodeID ID;
1123 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1126 SDNode *N = nullptr;
1127 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1129 return SDValue(N, 0);
1132 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1133 CSEMap.InsertNode(N, IP);
1134 AllNodes.push_back(N);
1137 SDValue Result(N, 0);
1138 if (VT.isVector()) {
1139 SmallVector<SDValue, 8> Ops;
1140 Ops.assign(VT.getVectorNumElements(), Result);
1141 // FIXME SDLoc info might be appropriate here
1142 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1147 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1148 EVT EltVT = VT.getScalarType();
1149 if (EltVT==MVT::f32)
1150 return getConstantFP(APFloat((float)Val), VT, isTarget);
1151 else if (EltVT==MVT::f64)
1152 return getConstantFP(APFloat(Val), VT, isTarget);
1153 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1156 APFloat apf = APFloat(Val);
1157 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1159 return getConstantFP(apf, VT, isTarget);
1161 llvm_unreachable("Unsupported type in getConstantFP");
1164 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1165 EVT VT, int64_t Offset,
1167 unsigned char TargetFlags) {
1168 assert((TargetFlags == 0 || isTargetGA) &&
1169 "Cannot set target flags on target-independent globals");
1170 const TargetLowering *TLI = TM.getTargetLowering();
1172 // Truncate (with sign-extension) the offset value to the pointer size.
1173 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1175 Offset = SignExtend64(Offset, BitWidth);
1177 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1179 // If GV is an alias then use the aliasee for determining thread-localness.
1180 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1181 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1185 if (GVar && GVar->isThreadLocal())
1186 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1188 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1190 FoldingSetNodeID ID;
1191 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1193 ID.AddInteger(Offset);
1194 ID.AddInteger(TargetFlags);
1195 ID.AddInteger(GV->getType()->getAddressSpace());
1197 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1198 return SDValue(E, 0);
1200 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1201 DL.getDebugLoc(), GV, VT,
1202 Offset, TargetFlags);
1203 CSEMap.InsertNode(N, IP);
1204 AllNodes.push_back(N);
1205 return SDValue(N, 0);
1208 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1209 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1210 FoldingSetNodeID ID;
1211 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1214 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1215 return SDValue(E, 0);
1217 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1218 CSEMap.InsertNode(N, IP);
1219 AllNodes.push_back(N);
1220 return SDValue(N, 0);
1223 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1224 unsigned char TargetFlags) {
1225 assert((TargetFlags == 0 || isTarget) &&
1226 "Cannot set target flags on target-independent jump tables");
1227 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1228 FoldingSetNodeID ID;
1229 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1231 ID.AddInteger(TargetFlags);
1233 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1234 return SDValue(E, 0);
1236 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1238 CSEMap.InsertNode(N, IP);
1239 AllNodes.push_back(N);
1240 return SDValue(N, 0);
1243 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1244 unsigned Alignment, int Offset,
1246 unsigned char TargetFlags) {
1247 assert((TargetFlags == 0 || isTarget) &&
1248 "Cannot set target flags on target-independent globals");
1251 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1252 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1253 FoldingSetNodeID ID;
1254 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1255 ID.AddInteger(Alignment);
1256 ID.AddInteger(Offset);
1258 ID.AddInteger(TargetFlags);
1260 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1261 return SDValue(E, 0);
1263 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1264 Alignment, TargetFlags);
1265 CSEMap.InsertNode(N, IP);
1266 AllNodes.push_back(N);
1267 return SDValue(N, 0);
1271 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1272 unsigned Alignment, int Offset,
1274 unsigned char TargetFlags) {
1275 assert((TargetFlags == 0 || isTarget) &&
1276 "Cannot set target flags on target-independent globals");
1279 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1280 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1281 FoldingSetNodeID ID;
1282 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1283 ID.AddInteger(Alignment);
1284 ID.AddInteger(Offset);
1285 C->addSelectionDAGCSEId(ID);
1286 ID.AddInteger(TargetFlags);
1288 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1289 return SDValue(E, 0);
1291 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1292 Alignment, TargetFlags);
1293 CSEMap.InsertNode(N, IP);
1294 AllNodes.push_back(N);
1295 return SDValue(N, 0);
1298 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1299 unsigned char TargetFlags) {
1300 FoldingSetNodeID ID;
1301 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1302 ID.AddInteger(Index);
1303 ID.AddInteger(Offset);
1304 ID.AddInteger(TargetFlags);
1306 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1307 return SDValue(E, 0);
1309 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1311 CSEMap.InsertNode(N, IP);
1312 AllNodes.push_back(N);
1313 return SDValue(N, 0);
1316 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1321 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1322 return SDValue(E, 0);
1324 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1325 CSEMap.InsertNode(N, IP);
1326 AllNodes.push_back(N);
1327 return SDValue(N, 0);
1330 SDValue SelectionDAG::getValueType(EVT VT) {
1331 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1332 ValueTypeNodes.size())
1333 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1335 SDNode *&N = VT.isExtended() ?
1336 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1338 if (N) return SDValue(N, 0);
1339 N = new (NodeAllocator) VTSDNode(VT);
1340 AllNodes.push_back(N);
1341 return SDValue(N, 0);
1344 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1345 SDNode *&N = ExternalSymbols[Sym];
1346 if (N) return SDValue(N, 0);
1347 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1348 AllNodes.push_back(N);
1349 return SDValue(N, 0);
1352 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1353 unsigned char TargetFlags) {
1355 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1357 if (N) return SDValue(N, 0);
1358 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1359 AllNodes.push_back(N);
1360 return SDValue(N, 0);
1363 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1364 if ((unsigned)Cond >= CondCodeNodes.size())
1365 CondCodeNodes.resize(Cond+1);
1367 if (!CondCodeNodes[Cond]) {
1368 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1369 CondCodeNodes[Cond] = N;
1370 AllNodes.push_back(N);
1373 return SDValue(CondCodeNodes[Cond], 0);
1376 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1377 // the shuffle mask M that point at N1 to point at N2, and indices that point
1378 // N2 to point at N1.
1379 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1381 int NElts = M.size();
1382 for (int i = 0; i != NElts; ++i) {
1390 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1391 SDValue N2, const int *Mask) {
1392 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1393 "Invalid VECTOR_SHUFFLE");
1395 // Canonicalize shuffle undef, undef -> undef
1396 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1397 return getUNDEF(VT);
1399 // Validate that all indices in Mask are within the range of the elements
1400 // input to the shuffle.
1401 unsigned NElts = VT.getVectorNumElements();
1402 SmallVector<int, 8> MaskVec;
1403 for (unsigned i = 0; i != NElts; ++i) {
1404 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1405 MaskVec.push_back(Mask[i]);
1408 // Canonicalize shuffle v, v -> v, undef
1411 for (unsigned i = 0; i != NElts; ++i)
1412 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1415 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1416 if (N1.getOpcode() == ISD::UNDEF)
1417 commuteShuffle(N1, N2, MaskVec);
1419 // Canonicalize all index into lhs, -> shuffle lhs, undef
1420 // Canonicalize all index into rhs, -> shuffle rhs, undef
1421 bool AllLHS = true, AllRHS = true;
1422 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1423 for (unsigned i = 0; i != NElts; ++i) {
1424 if (MaskVec[i] >= (int)NElts) {
1429 } else if (MaskVec[i] >= 0) {
1433 if (AllLHS && AllRHS)
1434 return getUNDEF(VT);
1435 if (AllLHS && !N2Undef)
1439 commuteShuffle(N1, N2, MaskVec);
1442 // If Identity shuffle return that node.
1443 bool Identity = true;
1444 for (unsigned i = 0; i != NElts; ++i) {
1445 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1447 if (Identity && NElts)
1450 // Shuffling a constant splat doesn't change the result.
1451 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1452 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1455 FoldingSetNodeID ID;
1456 SDValue Ops[2] = { N1, N2 };
1457 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1458 for (unsigned i = 0; i != NElts; ++i)
1459 ID.AddInteger(MaskVec[i]);
1462 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1463 return SDValue(E, 0);
1465 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1466 // SDNode doesn't have access to it. This memory will be "leaked" when
1467 // the node is deallocated, but recovered when the NodeAllocator is released.
1468 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1469 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1471 ShuffleVectorSDNode *N =
1472 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1473 dl.getDebugLoc(), N1, N2,
1475 CSEMap.InsertNode(N, IP);
1476 AllNodes.push_back(N);
1477 return SDValue(N, 0);
1480 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1481 SDValue Val, SDValue DTy,
1482 SDValue STy, SDValue Rnd, SDValue Sat,
1483 ISD::CvtCode Code) {
1484 // If the src and dest types are the same and the conversion is between
1485 // integer types of the same sign or two floats, no conversion is necessary.
1487 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1490 FoldingSetNodeID ID;
1491 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1492 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1494 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1495 return SDValue(E, 0);
1497 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1500 CSEMap.InsertNode(N, IP);
1501 AllNodes.push_back(N);
1502 return SDValue(N, 0);
1505 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1506 FoldingSetNodeID ID;
1507 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1508 ID.AddInteger(RegNo);
1510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1511 return SDValue(E, 0);
1513 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1514 CSEMap.InsertNode(N, IP);
1515 AllNodes.push_back(N);
1516 return SDValue(N, 0);
1519 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1520 FoldingSetNodeID ID;
1521 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1522 ID.AddPointer(RegMask);
1524 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1525 return SDValue(E, 0);
1527 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1528 CSEMap.InsertNode(N, IP);
1529 AllNodes.push_back(N);
1530 return SDValue(N, 0);
1533 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1534 FoldingSetNodeID ID;
1535 SDValue Ops[] = { Root };
1536 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1537 ID.AddPointer(Label);
1539 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1540 return SDValue(E, 0);
1542 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1543 dl.getDebugLoc(), Root, Label);
1544 CSEMap.InsertNode(N, IP);
1545 AllNodes.push_back(N);
1546 return SDValue(N, 0);
1550 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1553 unsigned char TargetFlags) {
1554 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1556 FoldingSetNodeID ID;
1557 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1559 ID.AddInteger(Offset);
1560 ID.AddInteger(TargetFlags);
1562 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1563 return SDValue(E, 0);
1565 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1567 CSEMap.InsertNode(N, IP);
1568 AllNodes.push_back(N);
1569 return SDValue(N, 0);
1572 SDValue SelectionDAG::getSrcValue(const Value *V) {
1573 assert((!V || V->getType()->isPointerTy()) &&
1574 "SrcValue is not a pointer?");
1576 FoldingSetNodeID ID;
1577 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1581 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1582 return SDValue(E, 0);
1584 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1585 CSEMap.InsertNode(N, IP);
1586 AllNodes.push_back(N);
1587 return SDValue(N, 0);
1590 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1591 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1592 FoldingSetNodeID ID;
1593 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1597 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1598 return SDValue(E, 0);
1600 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1601 CSEMap.InsertNode(N, IP);
1602 AllNodes.push_back(N);
1603 return SDValue(N, 0);
1606 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1607 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1608 unsigned SrcAS, unsigned DestAS) {
1609 SDValue Ops[] = {Ptr};
1610 FoldingSetNodeID ID;
1611 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1612 ID.AddInteger(SrcAS);
1613 ID.AddInteger(DestAS);
1616 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1617 return SDValue(E, 0);
1619 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1621 VT, Ptr, SrcAS, DestAS);
1622 CSEMap.InsertNode(N, IP);
1623 AllNodes.push_back(N);
1624 return SDValue(N, 0);
1627 /// getShiftAmountOperand - Return the specified value casted to
1628 /// the target's desired shift amount type.
1629 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1630 EVT OpTy = Op.getValueType();
1631 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1632 if (OpTy == ShTy || OpTy.isVector()) return Op;
1634 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1635 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1638 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1639 /// specified value type.
1640 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1641 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1642 unsigned ByteSize = VT.getStoreSize();
1643 Type *Ty = VT.getTypeForEVT(*getContext());
1644 const TargetLowering *TLI = TM.getTargetLowering();
1645 unsigned StackAlign =
1646 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1648 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1649 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1652 /// CreateStackTemporary - Create a stack temporary suitable for holding
1653 /// either of the specified value types.
1654 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1655 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1656 VT2.getStoreSizeInBits())/8;
1657 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1658 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1659 const TargetLowering *TLI = TM.getTargetLowering();
1660 const DataLayout *TD = TLI->getDataLayout();
1661 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1662 TD->getPrefTypeAlignment(Ty2));
1664 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1665 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1666 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1669 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1670 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1671 // These setcc operations always fold.
1675 case ISD::SETFALSE2: return getConstant(0, VT);
1677 case ISD::SETTRUE2: {
1678 const TargetLowering *TLI = TM.getTargetLowering();
1679 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1681 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1694 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1698 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1699 const APInt &C2 = N2C->getAPIntValue();
1700 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1701 const APInt &C1 = N1C->getAPIntValue();
1704 default: llvm_unreachable("Unknown integer setcc!");
1705 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1706 case ISD::SETNE: return getConstant(C1 != C2, VT);
1707 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1708 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1709 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1710 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1711 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1712 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1713 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1714 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1718 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1719 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1720 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1723 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1724 return getUNDEF(VT);
1726 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1727 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1728 return getUNDEF(VT);
1730 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1731 R==APFloat::cmpLessThan, VT);
1732 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1733 return getUNDEF(VT);
1735 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1736 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1737 return getUNDEF(VT);
1739 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1740 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1741 return getUNDEF(VT);
1743 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1744 R==APFloat::cmpEqual, VT);
1745 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1746 return getUNDEF(VT);
1748 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1749 R==APFloat::cmpEqual, VT);
1750 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1751 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1752 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1753 R==APFloat::cmpEqual, VT);
1754 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1755 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1756 R==APFloat::cmpLessThan, VT);
1757 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1758 R==APFloat::cmpUnordered, VT);
1759 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1760 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1763 // Ensure that the constant occurs on the RHS.
1764 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1765 MVT CompVT = N1.getValueType().getSimpleVT();
1766 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1769 return getSetCC(dl, VT, N2, N1, SwappedCond);
1773 // Could not fold it.
1777 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1778 /// use this predicate to simplify operations downstream.
1779 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1780 // This predicate is not safe for vector operations.
1781 if (Op.getValueType().isVector())
1784 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1785 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1788 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1789 /// this predicate to simplify operations downstream. Mask is known to be zero
1790 /// for bits that V cannot have.
1791 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1792 unsigned Depth) const {
1793 APInt KnownZero, KnownOne;
1794 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1795 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1796 return (KnownZero & Mask) == Mask;
1799 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1800 /// known to be either zero or one and return them in the KnownZero/KnownOne
1801 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1803 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1804 APInt &KnownOne, unsigned Depth) const {
1805 const TargetLowering *TLI = TM.getTargetLowering();
1806 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1808 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1810 return; // Limit search depth.
1812 APInt KnownZero2, KnownOne2;
1814 switch (Op.getOpcode()) {
1816 // We know all of the bits for a constant!
1817 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1818 KnownZero = ~KnownOne;
1821 // If either the LHS or the RHS are Zero, the result is zero.
1822 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1823 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1824 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1825 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1827 // Output known-1 bits are only known if set in both the LHS & RHS.
1828 KnownOne &= KnownOne2;
1829 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1830 KnownZero |= KnownZero2;
1833 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1834 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1835 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1836 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1838 // Output known-0 bits are only known if clear in both the LHS & RHS.
1839 KnownZero &= KnownZero2;
1840 // Output known-1 are known to be set if set in either the LHS | RHS.
1841 KnownOne |= KnownOne2;
1844 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1845 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1846 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1847 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1849 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1850 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1851 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1852 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1853 KnownZero = KnownZeroOut;
1857 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1858 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1859 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1860 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1862 // If low bits are zero in either operand, output low known-0 bits.
1863 // Also compute a conserative estimate for high known-0 bits.
1864 // More trickiness is possible, but this is sufficient for the
1865 // interesting case of alignment computation.
1866 KnownOne.clearAllBits();
1867 unsigned TrailZ = KnownZero.countTrailingOnes() +
1868 KnownZero2.countTrailingOnes();
1869 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1870 KnownZero2.countLeadingOnes(),
1871 BitWidth) - BitWidth;
1873 TrailZ = std::min(TrailZ, BitWidth);
1874 LeadZ = std::min(LeadZ, BitWidth);
1875 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1876 APInt::getHighBitsSet(BitWidth, LeadZ);
1880 // For the purposes of computing leading zeros we can conservatively
1881 // treat a udiv as a logical right shift by the power of 2 known to
1882 // be less than the denominator.
1883 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1884 unsigned LeadZ = KnownZero2.countLeadingOnes();
1886 KnownOne2.clearAllBits();
1887 KnownZero2.clearAllBits();
1888 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1889 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1890 if (RHSUnknownLeadingOnes != BitWidth)
1891 LeadZ = std::min(BitWidth,
1892 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1894 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1898 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1899 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1900 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1901 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1903 // Only known if known in both the LHS and RHS.
1904 KnownOne &= KnownOne2;
1905 KnownZero &= KnownZero2;
1907 case ISD::SELECT_CC:
1908 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1909 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1910 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1911 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1913 // Only known if known in both the LHS and RHS.
1914 KnownOne &= KnownOne2;
1915 KnownZero &= KnownZero2;
1923 if (Op.getResNo() != 1)
1925 // The boolean result conforms to getBooleanContents. Fall through.
1927 // If we know the result of a setcc has the top bits zero, use this info.
1928 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1929 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1930 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1933 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1934 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1935 unsigned ShAmt = SA->getZExtValue();
1937 // If the shift count is an invalid immediate, don't do anything.
1938 if (ShAmt >= BitWidth)
1941 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1942 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1943 KnownZero <<= ShAmt;
1945 // low bits known zero.
1946 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1950 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1951 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1952 unsigned ShAmt = SA->getZExtValue();
1954 // If the shift count is an invalid immediate, don't do anything.
1955 if (ShAmt >= BitWidth)
1958 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1959 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1960 KnownZero = KnownZero.lshr(ShAmt);
1961 KnownOne = KnownOne.lshr(ShAmt);
1963 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1964 KnownZero |= HighBits; // High bits known zero.
1968 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1969 unsigned ShAmt = SA->getZExtValue();
1971 // If the shift count is an invalid immediate, don't do anything.
1972 if (ShAmt >= BitWidth)
1975 // If any of the demanded bits are produced by the sign extension, we also
1976 // demand the input sign bit.
1977 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1979 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1980 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1981 KnownZero = KnownZero.lshr(ShAmt);
1982 KnownOne = KnownOne.lshr(ShAmt);
1984 // Handle the sign bits.
1985 APInt SignBit = APInt::getSignBit(BitWidth);
1986 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1988 if (KnownZero.intersects(SignBit)) {
1989 KnownZero |= HighBits; // New bits are known zero.
1990 } else if (KnownOne.intersects(SignBit)) {
1991 KnownOne |= HighBits; // New bits are known one.
1995 case ISD::SIGN_EXTEND_INREG: {
1996 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1997 unsigned EBits = EVT.getScalarType().getSizeInBits();
1999 // Sign extension. Compute the demanded bits in the result that are not
2000 // present in the input.
2001 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2003 APInt InSignBit = APInt::getSignBit(EBits);
2004 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2006 // If the sign extended bits are demanded, we know that the sign
2008 InSignBit = InSignBit.zext(BitWidth);
2009 if (NewBits.getBoolValue())
2010 InputDemandedBits |= InSignBit;
2012 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2013 KnownOne &= InputDemandedBits;
2014 KnownZero &= InputDemandedBits;
2015 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2017 // If the sign bit of the input is known set or clear, then we know the
2018 // top bits of the result.
2019 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2020 KnownZero |= NewBits;
2021 KnownOne &= ~NewBits;
2022 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2023 KnownOne |= NewBits;
2024 KnownZero &= ~NewBits;
2025 } else { // Input sign bit unknown
2026 KnownZero &= ~NewBits;
2027 KnownOne &= ~NewBits;
2032 case ISD::CTTZ_ZERO_UNDEF:
2034 case ISD::CTLZ_ZERO_UNDEF:
2036 unsigned LowBits = Log2_32(BitWidth)+1;
2037 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2038 KnownOne.clearAllBits();
2042 LoadSDNode *LD = cast<LoadSDNode>(Op);
2043 // If this is a ZEXTLoad and we are looking at the loaded value.
2044 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2045 EVT VT = LD->getMemoryVT();
2046 unsigned MemBits = VT.getScalarType().getSizeInBits();
2047 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2048 } else if (const MDNode *Ranges = LD->getRanges()) {
2049 computeMaskedBitsLoad(*Ranges, KnownZero);
2053 case ISD::ZERO_EXTEND: {
2054 EVT InVT = Op.getOperand(0).getValueType();
2055 unsigned InBits = InVT.getScalarType().getSizeInBits();
2056 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2057 KnownZero = KnownZero.trunc(InBits);
2058 KnownOne = KnownOne.trunc(InBits);
2059 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2060 KnownZero = KnownZero.zext(BitWidth);
2061 KnownOne = KnownOne.zext(BitWidth);
2062 KnownZero |= NewBits;
2065 case ISD::SIGN_EXTEND: {
2066 EVT InVT = Op.getOperand(0).getValueType();
2067 unsigned InBits = InVT.getScalarType().getSizeInBits();
2068 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2070 KnownZero = KnownZero.trunc(InBits);
2071 KnownOne = KnownOne.trunc(InBits);
2072 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2074 // Note if the sign bit is known to be zero or one.
2075 bool SignBitKnownZero = KnownZero.isNegative();
2076 bool SignBitKnownOne = KnownOne.isNegative();
2077 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2078 "Sign bit can't be known to be both zero and one!");
2080 KnownZero = KnownZero.zext(BitWidth);
2081 KnownOne = KnownOne.zext(BitWidth);
2083 // If the sign bit is known zero or one, the top bits match.
2084 if (SignBitKnownZero)
2085 KnownZero |= NewBits;
2086 else if (SignBitKnownOne)
2087 KnownOne |= NewBits;
2090 case ISD::ANY_EXTEND: {
2091 EVT InVT = Op.getOperand(0).getValueType();
2092 unsigned InBits = InVT.getScalarType().getSizeInBits();
2093 KnownZero = KnownZero.trunc(InBits);
2094 KnownOne = KnownOne.trunc(InBits);
2095 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2096 KnownZero = KnownZero.zext(BitWidth);
2097 KnownOne = KnownOne.zext(BitWidth);
2100 case ISD::TRUNCATE: {
2101 EVT InVT = Op.getOperand(0).getValueType();
2102 unsigned InBits = InVT.getScalarType().getSizeInBits();
2103 KnownZero = KnownZero.zext(InBits);
2104 KnownOne = KnownOne.zext(InBits);
2105 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2106 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2107 KnownZero = KnownZero.trunc(BitWidth);
2108 KnownOne = KnownOne.trunc(BitWidth);
2111 case ISD::AssertZext: {
2112 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2113 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2114 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2115 KnownZero |= (~InMask);
2116 KnownOne &= (~KnownZero);
2120 // All bits are zero except the low bit.
2121 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2125 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2126 // We know that the top bits of C-X are clear if X contains less bits
2127 // than C (i.e. no wrap-around can happen). For example, 20-X is
2128 // positive if we can prove that X is >= 0 and < 16.
2129 if (CLHS->getAPIntValue().isNonNegative()) {
2130 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2131 // NLZ can't be BitWidth with no sign bit
2132 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2133 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2135 // If all of the MaskV bits are known to be zero, then we know the
2136 // output top bits are zero, because we now know that the output is
2138 if ((KnownZero2 & MaskV) == MaskV) {
2139 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2140 // Top bits known zero.
2141 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2149 // Output known-0 bits are known if clear or set in both the low clear bits
2150 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2151 // low 3 bits clear.
2152 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2153 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2154 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2156 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2157 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2158 KnownZeroOut = std::min(KnownZeroOut,
2159 KnownZero2.countTrailingOnes());
2161 if (Op.getOpcode() == ISD::ADD) {
2162 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2166 // With ADDE, a carry bit may be added in, so we can only use this
2167 // information if we know (at least) that the low two bits are clear. We
2168 // then return to the caller that the low bit is unknown but that other bits
2170 if (KnownZeroOut >= 2) // ADDE
2171 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2175 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2176 const APInt &RA = Rem->getAPIntValue().abs();
2177 if (RA.isPowerOf2()) {
2178 APInt LowBits = RA - 1;
2179 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2181 // The low bits of the first operand are unchanged by the srem.
2182 KnownZero = KnownZero2 & LowBits;
2183 KnownOne = KnownOne2 & LowBits;
2185 // If the first operand is non-negative or has all low bits zero, then
2186 // the upper bits are all zero.
2187 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2188 KnownZero |= ~LowBits;
2190 // If the first operand is negative and not all low bits are zero, then
2191 // the upper bits are all one.
2192 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2193 KnownOne |= ~LowBits;
2194 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2199 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2200 const APInt &RA = Rem->getAPIntValue();
2201 if (RA.isPowerOf2()) {
2202 APInt LowBits = (RA - 1);
2203 KnownZero |= ~LowBits;
2204 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2205 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2210 // Since the result is less than or equal to either operand, any leading
2211 // zero bits in either operand must also exist in the result.
2212 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2213 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2215 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2216 KnownZero2.countLeadingOnes());
2217 KnownOne.clearAllBits();
2218 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2221 case ISD::FrameIndex:
2222 case ISD::TargetFrameIndex:
2223 if (unsigned Align = InferPtrAlignment(Op)) {
2224 // The low bits are known zero if the pointer is aligned.
2225 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2231 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2234 case ISD::INTRINSIC_WO_CHAIN:
2235 case ISD::INTRINSIC_W_CHAIN:
2236 case ISD::INTRINSIC_VOID:
2237 // Allow the target to implement this method for its nodes.
2238 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2243 /// ComputeNumSignBits - Return the number of times the sign bit of the
2244 /// register is replicated into the other bits. We know that at least 1 bit
2245 /// is always equal to the sign bit (itself), but other cases can give us
2246 /// information. For example, immediately after an "SRA X, 2", we know that
2247 /// the top 3 bits are all equal to each other, so we return 3.
2248 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2249 const TargetLowering *TLI = TM.getTargetLowering();
2250 EVT VT = Op.getValueType();
2251 assert(VT.isInteger() && "Invalid VT!");
2252 unsigned VTBits = VT.getScalarType().getSizeInBits();
2254 unsigned FirstAnswer = 1;
2257 return 1; // Limit search depth.
2259 switch (Op.getOpcode()) {
2261 case ISD::AssertSext:
2262 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2263 return VTBits-Tmp+1;
2264 case ISD::AssertZext:
2265 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2268 case ISD::Constant: {
2269 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2270 return Val.getNumSignBits();
2273 case ISD::SIGN_EXTEND:
2275 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2276 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2278 case ISD::SIGN_EXTEND_INREG:
2279 // Max of the input and what this extends.
2281 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2284 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2285 return std::max(Tmp, Tmp2);
2288 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2289 // SRA X, C -> adds C sign bits.
2290 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2291 Tmp += C->getZExtValue();
2292 if (Tmp > VTBits) Tmp = VTBits;
2296 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2297 // shl destroys sign bits.
2298 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2299 if (C->getZExtValue() >= VTBits || // Bad shift.
2300 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2301 return Tmp - C->getZExtValue();
2306 case ISD::XOR: // NOT is handled here.
2307 // Logical binary ops preserve the number of sign bits at the worst.
2308 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2310 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2311 FirstAnswer = std::min(Tmp, Tmp2);
2312 // We computed what we know about the sign bits as our first
2313 // answer. Now proceed to the generic code that uses
2314 // ComputeMaskedBits, and pick whichever answer is better.
2319 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2320 if (Tmp == 1) return 1; // Early out.
2321 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2322 return std::min(Tmp, Tmp2);
2330 if (Op.getResNo() != 1)
2332 // The boolean result conforms to getBooleanContents. Fall through.
2334 // If setcc returns 0/-1, all bits are sign bits.
2335 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2336 TargetLowering::ZeroOrNegativeOneBooleanContent)
2341 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2342 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2344 // Handle rotate right by N like a rotate left by 32-N.
2345 if (Op.getOpcode() == ISD::ROTR)
2346 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2348 // If we aren't rotating out all of the known-in sign bits, return the
2349 // number that are left. This handles rotl(sext(x), 1) for example.
2350 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2351 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2355 // Add can have at most one carry bit. Thus we know that the output
2356 // is, at worst, one more bit than the inputs.
2357 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2358 if (Tmp == 1) return 1; // Early out.
2360 // Special case decrementing a value (ADD X, -1):
2361 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2362 if (CRHS->isAllOnesValue()) {
2363 APInt KnownZero, KnownOne;
2364 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2366 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2368 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2371 // If we are subtracting one from a positive number, there is no carry
2372 // out of the result.
2373 if (KnownZero.isNegative())
2377 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2378 if (Tmp2 == 1) return 1;
2379 return std::min(Tmp, Tmp2)-1;
2382 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2383 if (Tmp2 == 1) return 1;
2386 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2387 if (CLHS->isNullValue()) {
2388 APInt KnownZero, KnownOne;
2389 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2390 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2392 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2395 // If the input is known to be positive (the sign bit is known clear),
2396 // the output of the NEG has the same number of sign bits as the input.
2397 if (KnownZero.isNegative())
2400 // Otherwise, we treat this like a SUB.
2403 // Sub can have at most one carry bit. Thus we know that the output
2404 // is, at worst, one more bit than the inputs.
2405 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2406 if (Tmp == 1) return 1; // Early out.
2407 return std::min(Tmp, Tmp2)-1;
2409 // FIXME: it's tricky to do anything useful for this, but it is an important
2410 // case for targets like X86.
2414 // If we are looking at the loaded value of the SDNode.
2415 if (Op.getResNo() == 0) {
2416 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2417 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2418 unsigned ExtType = LD->getExtensionType();
2421 case ISD::SEXTLOAD: // '17' bits known
2422 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2423 return VTBits-Tmp+1;
2424 case ISD::ZEXTLOAD: // '16' bits known
2425 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2431 // Allow the target to implement this method for its nodes.
2432 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2433 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2434 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2435 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2436 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2437 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2440 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2441 // use this information.
2442 APInt KnownZero, KnownOne;
2443 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2446 if (KnownZero.isNegative()) { // sign bit is 0
2448 } else if (KnownOne.isNegative()) { // sign bit is 1;
2455 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2456 // the number of identical bits in the top of the input value.
2458 Mask <<= Mask.getBitWidth()-VTBits;
2459 // Return # leading zeros. We use 'min' here in case Val was zero before
2460 // shifting. We don't want to return '64' as for an i32 "0".
2461 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2464 /// isBaseWithConstantOffset - Return true if the specified operand is an
2465 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2466 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2467 /// semantics as an ADD. This handles the equivalence:
2468 /// X|Cst == X+Cst iff X&Cst = 0.
2469 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2470 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2471 !isa<ConstantSDNode>(Op.getOperand(1)))
2474 if (Op.getOpcode() == ISD::OR &&
2475 !MaskedValueIsZero(Op.getOperand(0),
2476 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2483 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2484 // If we're told that NaNs won't happen, assume they won't.
2485 if (getTarget().Options.NoNaNsFPMath)
2488 // If the value is a constant, we can obviously see if it is a NaN or not.
2489 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2490 return !C->getValueAPF().isNaN();
2492 // TODO: Recognize more cases here.
2497 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2498 // If the value is a constant, we can obviously see if it is a zero or not.
2499 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2500 return !C->isZero();
2502 // TODO: Recognize more cases here.
2503 switch (Op.getOpcode()) {
2506 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2507 return !C->isNullValue();
2514 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2515 // Check the obvious case.
2516 if (A == B) return true;
2518 // For for negative and positive zero.
2519 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2520 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2521 if (CA->isZero() && CB->isZero()) return true;
2523 // Otherwise they may not be equal.
2527 /// getNode - Gets or creates the specified node.
2529 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2530 FoldingSetNodeID ID;
2531 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2533 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2534 return SDValue(E, 0);
2536 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2537 DL.getDebugLoc(), getVTList(VT));
2538 CSEMap.InsertNode(N, IP);
2540 AllNodes.push_back(N);
2544 return SDValue(N, 0);
2547 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2548 EVT VT, SDValue Operand) {
2549 // Constant fold unary operations with an integer constant operand. Even
2550 // opaque constant will be folded, because the folding of unary operations
2551 // doesn't create new constants with different values. Nevertheless, the
2552 // opaque flag is preserved during folding to prevent future folding with
2554 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2555 const APInt &Val = C->getAPIntValue();
2558 case ISD::SIGN_EXTEND:
2559 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2560 C->isTargetOpcode(), C->isOpaque());
2561 case ISD::ANY_EXTEND:
2562 case ISD::ZERO_EXTEND:
2564 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2565 C->isTargetOpcode(), C->isOpaque());
2566 case ISD::UINT_TO_FP:
2567 case ISD::SINT_TO_FP: {
2568 APFloat apf(EVTToAPFloatSemantics(VT),
2569 APInt::getNullValue(VT.getSizeInBits()));
2570 (void)apf.convertFromAPInt(Val,
2571 Opcode==ISD::SINT_TO_FP,
2572 APFloat::rmNearestTiesToEven);
2573 return getConstantFP(apf, VT);
2576 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2577 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2578 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2579 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2582 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2585 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2588 case ISD::CTLZ_ZERO_UNDEF:
2589 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2592 case ISD::CTTZ_ZERO_UNDEF:
2593 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2598 // Constant fold unary operations with a floating point constant operand.
2599 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2600 APFloat V = C->getValueAPF(); // make copy
2604 return getConstantFP(V, VT);
2607 return getConstantFP(V, VT);
2609 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2610 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2611 return getConstantFP(V, VT);
2615 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2616 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2617 return getConstantFP(V, VT);
2621 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2622 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2623 return getConstantFP(V, VT);
2626 case ISD::FP_EXTEND: {
2628 // This can return overflow, underflow, or inexact; we don't care.
2629 // FIXME need to be more flexible about rounding mode.
2630 (void)V.convert(EVTToAPFloatSemantics(VT),
2631 APFloat::rmNearestTiesToEven, &ignored);
2632 return getConstantFP(V, VT);
2634 case ISD::FP_TO_SINT:
2635 case ISD::FP_TO_UINT: {
2638 assert(integerPartWidth >= 64);
2639 // FIXME need to be more flexible about rounding mode.
2640 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2641 Opcode==ISD::FP_TO_SINT,
2642 APFloat::rmTowardZero, &ignored);
2643 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2645 APInt api(VT.getSizeInBits(), x);
2646 return getConstant(api, VT);
2649 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2650 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2651 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2652 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2657 unsigned OpOpcode = Operand.getNode()->getOpcode();
2659 case ISD::TokenFactor:
2660 case ISD::MERGE_VALUES:
2661 case ISD::CONCAT_VECTORS:
2662 return Operand; // Factor, merge or concat of one node? No need.
2663 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2664 case ISD::FP_EXTEND:
2665 assert(VT.isFloatingPoint() &&
2666 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2667 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2668 assert((!VT.isVector() ||
2669 VT.getVectorNumElements() ==
2670 Operand.getValueType().getVectorNumElements()) &&
2671 "Vector element count mismatch!");
2672 if (Operand.getOpcode() == ISD::UNDEF)
2673 return getUNDEF(VT);
2675 case ISD::SIGN_EXTEND:
2676 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2677 "Invalid SIGN_EXTEND!");
2678 if (Operand.getValueType() == VT) return Operand; // noop extension
2679 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2680 "Invalid sext node, dst < src!");
2681 assert((!VT.isVector() ||
2682 VT.getVectorNumElements() ==
2683 Operand.getValueType().getVectorNumElements()) &&
2684 "Vector element count mismatch!");
2685 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2686 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2687 else if (OpOpcode == ISD::UNDEF)
2688 // sext(undef) = 0, because the top bits will all be the same.
2689 return getConstant(0, VT);
2691 case ISD::ZERO_EXTEND:
2692 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2693 "Invalid ZERO_EXTEND!");
2694 if (Operand.getValueType() == VT) return Operand; // noop extension
2695 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2696 "Invalid zext node, dst < src!");
2697 assert((!VT.isVector() ||
2698 VT.getVectorNumElements() ==
2699 Operand.getValueType().getVectorNumElements()) &&
2700 "Vector element count mismatch!");
2701 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2702 return getNode(ISD::ZERO_EXTEND, DL, VT,
2703 Operand.getNode()->getOperand(0));
2704 else if (OpOpcode == ISD::UNDEF)
2705 // zext(undef) = 0, because the top bits will be zero.
2706 return getConstant(0, VT);
2708 case ISD::ANY_EXTEND:
2709 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2710 "Invalid ANY_EXTEND!");
2711 if (Operand.getValueType() == VT) return Operand; // noop extension
2712 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2713 "Invalid anyext node, dst < src!");
2714 assert((!VT.isVector() ||
2715 VT.getVectorNumElements() ==
2716 Operand.getValueType().getVectorNumElements()) &&
2717 "Vector element count mismatch!");
2719 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2720 OpOpcode == ISD::ANY_EXTEND)
2721 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2722 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2723 else if (OpOpcode == ISD::UNDEF)
2724 return getUNDEF(VT);
2726 // (ext (trunx x)) -> x
2727 if (OpOpcode == ISD::TRUNCATE) {
2728 SDValue OpOp = Operand.getNode()->getOperand(0);
2729 if (OpOp.getValueType() == VT)
2734 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2735 "Invalid TRUNCATE!");
2736 if (Operand.getValueType() == VT) return Operand; // noop truncate
2737 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2738 "Invalid truncate node, src < dst!");
2739 assert((!VT.isVector() ||
2740 VT.getVectorNumElements() ==
2741 Operand.getValueType().getVectorNumElements()) &&
2742 "Vector element count mismatch!");
2743 if (OpOpcode == ISD::TRUNCATE)
2744 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2745 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2746 OpOpcode == ISD::ANY_EXTEND) {
2747 // If the source is smaller than the dest, we still need an extend.
2748 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2749 .bitsLT(VT.getScalarType()))
2750 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2751 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2752 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2753 return Operand.getNode()->getOperand(0);
2755 if (OpOpcode == ISD::UNDEF)
2756 return getUNDEF(VT);
2759 // Basic sanity checking.
2760 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2761 && "Cannot BITCAST between types of different sizes!");
2762 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2763 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2764 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2765 if (OpOpcode == ISD::UNDEF)
2766 return getUNDEF(VT);
2768 case ISD::SCALAR_TO_VECTOR:
2769 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2770 (VT.getVectorElementType() == Operand.getValueType() ||
2771 (VT.getVectorElementType().isInteger() &&
2772 Operand.getValueType().isInteger() &&
2773 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2774 "Illegal SCALAR_TO_VECTOR node!");
2775 if (OpOpcode == ISD::UNDEF)
2776 return getUNDEF(VT);
2777 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2778 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2779 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2780 Operand.getConstantOperandVal(1) == 0 &&
2781 Operand.getOperand(0).getValueType() == VT)
2782 return Operand.getOperand(0);
2785 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2786 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2787 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2788 Operand.getNode()->getOperand(0));
2789 if (OpOpcode == ISD::FNEG) // --X -> X
2790 return Operand.getNode()->getOperand(0);
2793 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2794 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2799 SDVTList VTs = getVTList(VT);
2800 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2801 FoldingSetNodeID ID;
2802 SDValue Ops[1] = { Operand };
2803 AddNodeIDNode(ID, Opcode, VTs, Ops);
2805 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2806 return SDValue(E, 0);
2808 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2809 DL.getDebugLoc(), VTs, Operand);
2810 CSEMap.InsertNode(N, IP);
2812 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2813 DL.getDebugLoc(), VTs, Operand);
2816 AllNodes.push_back(N);
2820 return SDValue(N, 0);
2823 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2824 SDNode *Cst1, SDNode *Cst2) {
2825 // If the opcode is a target-specific ISD node, there's nothing we can
2826 // do here and the operand rules may not line up with the below, so
2828 if (Opcode >= ISD::BUILTIN_OP_END)
2831 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2832 SmallVector<SDValue, 4> Outputs;
2833 EVT SVT = VT.getScalarType();
2835 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2836 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2837 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2840 if (Scalar1 && Scalar2)
2841 // Scalar instruction.
2842 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2844 // For vectors extract each constant element into Inputs so we can constant
2845 // fold them individually.
2846 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2847 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2851 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2853 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2854 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2855 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2856 if (!V1 || !V2) // Not a constant, bail.
2859 if (V1->isOpaque() || V2->isOpaque())
2862 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2863 // FIXME: This is valid and could be handled by truncating the APInts.
2864 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2867 Inputs.push_back(std::make_pair(V1, V2));
2871 // We have a number of constant values, constant fold them element by element.
2872 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2873 const APInt &C1 = Inputs[I].first->getAPIntValue();
2874 const APInt &C2 = Inputs[I].second->getAPIntValue();
2878 Outputs.push_back(getConstant(C1 + C2, SVT));
2881 Outputs.push_back(getConstant(C1 - C2, SVT));
2884 Outputs.push_back(getConstant(C1 * C2, SVT));
2887 if (!C2.getBoolValue())
2889 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2892 if (!C2.getBoolValue())
2894 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2897 if (!C2.getBoolValue())
2899 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2902 if (!C2.getBoolValue())
2904 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2907 Outputs.push_back(getConstant(C1 & C2, SVT));
2910 Outputs.push_back(getConstant(C1 | C2, SVT));
2913 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2916 Outputs.push_back(getConstant(C1 << C2, SVT));
2919 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2922 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2925 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2928 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2935 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2936 "Expected a scalar or vector!"));
2938 // Handle the scalar case first.
2940 return Outputs.back();
2942 // We may have a vector type but a scalar result. Create a splat.
2943 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2945 // Build a big vector out of the scalar elements we generated.
2946 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2949 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2951 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2952 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2955 case ISD::TokenFactor:
2956 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2957 N2.getValueType() == MVT::Other && "Invalid token factor!");
2958 // Fold trivial token factors.
2959 if (N1.getOpcode() == ISD::EntryToken) return N2;
2960 if (N2.getOpcode() == ISD::EntryToken) return N1;
2961 if (N1 == N2) return N1;
2963 case ISD::CONCAT_VECTORS:
2964 // Concat of UNDEFs is UNDEF.
2965 if (N1.getOpcode() == ISD::UNDEF &&
2966 N2.getOpcode() == ISD::UNDEF)
2967 return getUNDEF(VT);
2969 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2970 // one big BUILD_VECTOR.
2971 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2972 N2.getOpcode() == ISD::BUILD_VECTOR) {
2973 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2974 N1.getNode()->op_end());
2975 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2976 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2980 assert(VT.isInteger() && "This operator does not apply to FP types!");
2981 assert(N1.getValueType() == N2.getValueType() &&
2982 N1.getValueType() == VT && "Binary operator types must match!");
2983 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2984 // worth handling here.
2985 if (N2C && N2C->isNullValue())
2987 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2994 assert(VT.isInteger() && "This operator does not apply to FP types!");
2995 assert(N1.getValueType() == N2.getValueType() &&
2996 N1.getValueType() == VT && "Binary operator types must match!");
2997 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2998 // it's worth handling here.
2999 if (N2C && N2C->isNullValue())
3009 assert(VT.isInteger() && "This operator does not apply to FP types!");
3010 assert(N1.getValueType() == N2.getValueType() &&
3011 N1.getValueType() == VT && "Binary operator types must match!");
3018 if (getTarget().Options.UnsafeFPMath) {
3019 if (Opcode == ISD::FADD) {
3021 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3022 if (CFP->getValueAPF().isZero())
3025 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3026 if (CFP->getValueAPF().isZero())
3028 } else if (Opcode == ISD::FSUB) {
3030 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3031 if (CFP->getValueAPF().isZero())
3033 } else if (Opcode == ISD::FMUL) {
3034 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3037 // If the first operand isn't the constant, try the second
3039 CFP = dyn_cast<ConstantFPSDNode>(N2);
3046 return SDValue(CFP,0);
3048 if (CFP->isExactlyValue(1.0))
3053 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3054 assert(N1.getValueType() == N2.getValueType() &&
3055 N1.getValueType() == VT && "Binary operator types must match!");
3057 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3058 assert(N1.getValueType() == VT &&
3059 N1.getValueType().isFloatingPoint() &&
3060 N2.getValueType().isFloatingPoint() &&
3061 "Invalid FCOPYSIGN!");
3068 assert(VT == N1.getValueType() &&
3069 "Shift operators return type must be the same as their first arg");
3070 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3071 "Shifts only work on integers");
3072 assert((!VT.isVector() || VT == N2.getValueType()) &&
3073 "Vector shift amounts must be in the same as their first arg");
3074 // Verify that the shift amount VT is bit enough to hold valid shift
3075 // amounts. This catches things like trying to shift an i1024 value by an
3076 // i8, which is easy to fall into in generic code that uses
3077 // TLI.getShiftAmount().
3078 assert(N2.getValueType().getSizeInBits() >=
3079 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3080 "Invalid use of small shift amount with oversized value!");
3082 // Always fold shifts of i1 values so the code generator doesn't need to
3083 // handle them. Since we know the size of the shift has to be less than the
3084 // size of the value, the shift/rotate count is guaranteed to be zero.
3087 if (N2C && N2C->isNullValue())
3090 case ISD::FP_ROUND_INREG: {
3091 EVT EVT = cast<VTSDNode>(N2)->getVT();
3092 assert(VT == N1.getValueType() && "Not an inreg round!");
3093 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3094 "Cannot FP_ROUND_INREG integer types");
3095 assert(EVT.isVector() == VT.isVector() &&
3096 "FP_ROUND_INREG type should be vector iff the operand "
3098 assert((!EVT.isVector() ||
3099 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3100 "Vector element counts must match in FP_ROUND_INREG");
3101 assert(EVT.bitsLE(VT) && "Not rounding down!");
3103 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3107 assert(VT.isFloatingPoint() &&
3108 N1.getValueType().isFloatingPoint() &&
3109 VT.bitsLE(N1.getValueType()) &&
3110 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3111 if (N1.getValueType() == VT) return N1; // noop conversion.
3113 case ISD::AssertSext:
3114 case ISD::AssertZext: {
3115 EVT EVT = cast<VTSDNode>(N2)->getVT();
3116 assert(VT == N1.getValueType() && "Not an inreg extend!");
3117 assert(VT.isInteger() && EVT.isInteger() &&
3118 "Cannot *_EXTEND_INREG FP types");
3119 assert(!EVT.isVector() &&
3120 "AssertSExt/AssertZExt type should be the vector element type "
3121 "rather than the vector type!");
3122 assert(EVT.bitsLE(VT) && "Not extending!");
3123 if (VT == EVT) return N1; // noop assertion.
3126 case ISD::SIGN_EXTEND_INREG: {
3127 EVT EVT = cast<VTSDNode>(N2)->getVT();
3128 assert(VT == N1.getValueType() && "Not an inreg extend!");
3129 assert(VT.isInteger() && EVT.isInteger() &&
3130 "Cannot *_EXTEND_INREG FP types");
3131 assert(EVT.isVector() == VT.isVector() &&
3132 "SIGN_EXTEND_INREG type should be vector iff the operand "
3134 assert((!EVT.isVector() ||
3135 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3136 "Vector element counts must match in SIGN_EXTEND_INREG");
3137 assert(EVT.bitsLE(VT) && "Not extending!");
3138 if (EVT == VT) return N1; // Not actually extending
3141 APInt Val = N1C->getAPIntValue();
3142 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3143 Val <<= Val.getBitWidth()-FromBits;
3144 Val = Val.ashr(Val.getBitWidth()-FromBits);
3145 return getConstant(Val, VT);
3149 case ISD::EXTRACT_VECTOR_ELT:
3150 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3151 if (N1.getOpcode() == ISD::UNDEF)
3152 return getUNDEF(VT);
3154 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3155 // expanding copies of large vectors from registers.
3157 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3158 N1.getNumOperands() > 0) {
3160 N1.getOperand(0).getValueType().getVectorNumElements();
3161 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3162 N1.getOperand(N2C->getZExtValue() / Factor),
3163 getConstant(N2C->getZExtValue() % Factor,
3164 N2.getValueType()));
3167 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3168 // expanding large vector constants.
3169 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3170 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3172 if (VT != Elt.getValueType())
3173 // If the vector element type is not legal, the BUILD_VECTOR operands
3174 // are promoted and implicitly truncated, and the result implicitly
3175 // extended. Make that explicit here.
3176 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3181 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3182 // operations are lowered to scalars.
3183 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3184 // If the indices are the same, return the inserted element else
3185 // if the indices are known different, extract the element from
3186 // the original vector.
3187 SDValue N1Op2 = N1.getOperand(2);
3188 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3190 if (N1Op2C && N2C) {
3191 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3192 if (VT == N1.getOperand(1).getValueType())
3193 return N1.getOperand(1);
3195 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3198 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3202 case ISD::EXTRACT_ELEMENT:
3203 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3204 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3205 (N1.getValueType().isInteger() == VT.isInteger()) &&
3206 N1.getValueType() != VT &&
3207 "Wrong types for EXTRACT_ELEMENT!");
3209 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3210 // 64-bit integers into 32-bit parts. Instead of building the extract of
3211 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3212 if (N1.getOpcode() == ISD::BUILD_PAIR)
3213 return N1.getOperand(N2C->getZExtValue());
3215 // EXTRACT_ELEMENT of a constant int is also very common.
3216 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3217 unsigned ElementSize = VT.getSizeInBits();
3218 unsigned Shift = ElementSize * N2C->getZExtValue();
3219 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3220 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3223 case ISD::EXTRACT_SUBVECTOR: {
3225 if (VT.isSimple() && N1.getValueType().isSimple()) {
3226 assert(VT.isVector() && N1.getValueType().isVector() &&
3227 "Extract subvector VTs must be a vectors!");
3228 assert(VT.getVectorElementType() ==
3229 N1.getValueType().getVectorElementType() &&
3230 "Extract subvector VTs must have the same element type!");
3231 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3232 "Extract subvector must be from larger vector to smaller vector!");
3234 if (isa<ConstantSDNode>(Index.getNode())) {
3235 assert((VT.getVectorNumElements() +
3236 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3237 <= N1.getValueType().getVectorNumElements())
3238 && "Extract subvector overflow!");
3241 // Trivial extraction.
3242 if (VT.getSimpleVT() == N1.getSimpleValueType())
3249 // Perform trivial constant folding.
3250 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3251 if (SV.getNode()) return SV;
3253 // Canonicalize constant to RHS if commutative.
3254 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3255 std::swap(N1C, N2C);
3259 // Constant fold FP operations.
3260 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3261 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3263 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3264 // Canonicalize constant to RHS if commutative.
3265 std::swap(N1CFP, N2CFP);
3268 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3269 APFloat::opStatus s;
3272 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3273 if (s != APFloat::opInvalidOp)
3274 return getConstantFP(V1, VT);
3277 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3278 if (s!=APFloat::opInvalidOp)
3279 return getConstantFP(V1, VT);
3282 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3283 if (s!=APFloat::opInvalidOp)
3284 return getConstantFP(V1, VT);
3287 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3288 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3289 return getConstantFP(V1, VT);
3292 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3293 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3294 return getConstantFP(V1, VT);
3296 case ISD::FCOPYSIGN:
3298 return getConstantFP(V1, VT);
3303 if (Opcode == ISD::FP_ROUND) {
3304 APFloat V = N1CFP->getValueAPF(); // make copy
3306 // This can return overflow, underflow, or inexact; we don't care.
3307 // FIXME need to be more flexible about rounding mode.
3308 (void)V.convert(EVTToAPFloatSemantics(VT),
3309 APFloat::rmNearestTiesToEven, &ignored);
3310 return getConstantFP(V, VT);
3314 // Canonicalize an UNDEF to the RHS, even over a constant.
3315 if (N1.getOpcode() == ISD::UNDEF) {
3316 if (isCommutativeBinOp(Opcode)) {
3320 case ISD::FP_ROUND_INREG:
3321 case ISD::SIGN_EXTEND_INREG:
3327 return N1; // fold op(undef, arg2) -> undef
3335 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3336 // For vectors, we can't easily build an all zero vector, just return
3343 // Fold a bunch of operators when the RHS is undef.
3344 if (N2.getOpcode() == ISD::UNDEF) {
3347 if (N1.getOpcode() == ISD::UNDEF)
3348 // Handle undef ^ undef -> 0 special case. This is a common
3350 return getConstant(0, VT);
3360 return N2; // fold op(arg1, undef) -> undef
3366 if (getTarget().Options.UnsafeFPMath)
3374 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3375 // For vectors, we can't easily build an all zero vector, just return
3380 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3381 // For vectors, we can't easily build an all one vector, just return
3389 // Memoize this node if possible.
3391 SDVTList VTs = getVTList(VT);
3392 if (VT != MVT::Glue) {
3393 SDValue Ops[] = { N1, N2 };
3394 FoldingSetNodeID ID;
3395 AddNodeIDNode(ID, Opcode, VTs, Ops);
3397 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3398 return SDValue(E, 0);
3400 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3401 DL.getDebugLoc(), VTs, N1, N2);
3402 CSEMap.InsertNode(N, IP);
3404 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3405 DL.getDebugLoc(), VTs, N1, N2);
3408 AllNodes.push_back(N);
3412 return SDValue(N, 0);
3415 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3416 SDValue N1, SDValue N2, SDValue N3) {
3417 // Perform various simplifications.
3418 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3421 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3422 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3423 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3424 if (N1CFP && N2CFP && N3CFP) {
3425 APFloat V1 = N1CFP->getValueAPF();
3426 const APFloat &V2 = N2CFP->getValueAPF();
3427 const APFloat &V3 = N3CFP->getValueAPF();
3428 APFloat::opStatus s =
3429 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3430 if (s != APFloat::opInvalidOp)
3431 return getConstantFP(V1, VT);
3435 case ISD::CONCAT_VECTORS:
3436 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3437 // one big BUILD_VECTOR.
3438 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3439 N2.getOpcode() == ISD::BUILD_VECTOR &&
3440 N3.getOpcode() == ISD::BUILD_VECTOR) {
3441 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3442 N1.getNode()->op_end());
3443 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3444 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3445 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3449 // Use FoldSetCC to simplify SETCC's.
3450 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3451 if (Simp.getNode()) return Simp;
3456 if (N1C->getZExtValue())
3457 return N2; // select true, X, Y -> X
3458 return N3; // select false, X, Y -> Y
3461 if (N2 == N3) return N2; // select C, X, X -> X
3463 case ISD::VECTOR_SHUFFLE:
3464 llvm_unreachable("should use getVectorShuffle constructor!");
3465 case ISD::INSERT_SUBVECTOR: {
3467 if (VT.isSimple() && N1.getValueType().isSimple()
3468 && N2.getValueType().isSimple()) {
3469 assert(VT.isVector() && N1.getValueType().isVector() &&
3470 N2.getValueType().isVector() &&
3471 "Insert subvector VTs must be a vectors");
3472 assert(VT == N1.getValueType() &&
3473 "Dest and insert subvector source types must match!");
3474 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3475 "Insert subvector must be from smaller vector to larger vector!");
3476 if (isa<ConstantSDNode>(Index.getNode())) {
3477 assert((N2.getValueType().getVectorNumElements() +
3478 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3479 <= VT.getVectorNumElements())
3480 && "Insert subvector overflow!");
3483 // Trivial insertion.
3484 if (VT.getSimpleVT() == N2.getSimpleValueType())
3490 // Fold bit_convert nodes from a type to themselves.
3491 if (N1.getValueType() == VT)
3496 // Memoize node if it doesn't produce a flag.
3498 SDVTList VTs = getVTList(VT);
3499 if (VT != MVT::Glue) {
3500 SDValue Ops[] = { N1, N2, N3 };
3501 FoldingSetNodeID ID;
3502 AddNodeIDNode(ID, Opcode, VTs, Ops);
3504 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3505 return SDValue(E, 0);
3507 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3508 DL.getDebugLoc(), VTs, N1, N2, N3);
3509 CSEMap.InsertNode(N, IP);
3511 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3512 DL.getDebugLoc(), VTs, N1, N2, N3);
3515 AllNodes.push_back(N);
3519 return SDValue(N, 0);
3522 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3523 SDValue N1, SDValue N2, SDValue N3,
3525 SDValue Ops[] = { N1, N2, N3, N4 };
3526 return getNode(Opcode, DL, VT, Ops);
3529 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3530 SDValue N1, SDValue N2, SDValue N3,
3531 SDValue N4, SDValue N5) {
3532 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3533 return getNode(Opcode, DL, VT, Ops);
3536 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3537 /// the incoming stack arguments to be loaded from the stack.
3538 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3539 SmallVector<SDValue, 8> ArgChains;
3541 // Include the original chain at the beginning of the list. When this is
3542 // used by target LowerCall hooks, this helps legalize find the
3543 // CALLSEQ_BEGIN node.
3544 ArgChains.push_back(Chain);
3546 // Add a chain value for each stack argument.
3547 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3548 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3549 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3550 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3551 if (FI->getIndex() < 0)
3552 ArgChains.push_back(SDValue(L, 1));
3554 // Build a tokenfactor for all the chains.
3555 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3558 /// getMemsetValue - Vectorized representation of the memset value
3560 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3562 assert(Value.getOpcode() != ISD::UNDEF);
3564 unsigned NumBits = VT.getScalarType().getSizeInBits();
3565 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3566 assert(C->getAPIntValue().getBitWidth() == 8);
3567 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3569 return DAG.getConstant(Val, VT);
3570 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3573 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3575 // Use a multiplication with 0x010101... to extend the input to the
3577 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3578 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3584 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3585 /// used when a memcpy is turned into a memset when the source is a constant
3587 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3588 const TargetLowering &TLI, StringRef Str) {
3589 // Handle vector with all elements zero.
3592 return DAG.getConstant(0, VT);
3593 else if (VT == MVT::f32 || VT == MVT::f64)
3594 return DAG.getConstantFP(0.0, VT);
3595 else if (VT.isVector()) {
3596 unsigned NumElts = VT.getVectorNumElements();
3597 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3598 return DAG.getNode(ISD::BITCAST, dl, VT,
3599 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3602 llvm_unreachable("Expected type!");
3605 assert(!VT.isVector() && "Can't handle vector type here!");
3606 unsigned NumVTBits = VT.getSizeInBits();
3607 unsigned NumVTBytes = NumVTBits / 8;
3608 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3610 APInt Val(NumVTBits, 0);
3611 if (TLI.isLittleEndian()) {
3612 for (unsigned i = 0; i != NumBytes; ++i)
3613 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3615 for (unsigned i = 0; i != NumBytes; ++i)
3616 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3619 // If the "cost" of materializing the integer immediate is less than the cost
3620 // of a load, then it is cost effective to turn the load into the immediate.
3621 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3622 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3623 return DAG.getConstant(Val, VT);
3624 return SDValue(nullptr, 0);
3627 /// getMemBasePlusOffset - Returns base and offset node for the
3629 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3630 SelectionDAG &DAG) {
3631 EVT VT = Base.getValueType();
3632 return DAG.getNode(ISD::ADD, dl,
3633 VT, Base, DAG.getConstant(Offset, VT));
3636 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3638 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3639 unsigned SrcDelta = 0;
3640 GlobalAddressSDNode *G = nullptr;
3641 if (Src.getOpcode() == ISD::GlobalAddress)
3642 G = cast<GlobalAddressSDNode>(Src);
3643 else if (Src.getOpcode() == ISD::ADD &&
3644 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3645 Src.getOperand(1).getOpcode() == ISD::Constant) {
3646 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3647 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3652 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3655 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3656 /// to replace the memset / memcpy. Return true if the number of memory ops
3657 /// is below the threshold. It returns the types of the sequence of
3658 /// memory ops to perform memset / memcpy by reference.
3659 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3660 unsigned Limit, uint64_t Size,
3661 unsigned DstAlign, unsigned SrcAlign,
3667 const TargetLowering &TLI) {
3668 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3669 "Expecting memcpy / memset source to meet alignment requirement!");
3670 // If 'SrcAlign' is zero, that means the memory operation does not need to
3671 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3672 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3673 // is the specified alignment of the memory operation. If it is zero, that
3674 // means it's possible to change the alignment of the destination.
3675 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3676 // not need to be loaded.
3677 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3678 IsMemset, ZeroMemset, MemcpyStrSrc,
3679 DAG.getMachineFunction());
3681 if (VT == MVT::Other) {
3683 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3684 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3685 VT = TLI.getPointerTy();
3687 switch (DstAlign & 7) {
3688 case 0: VT = MVT::i64; break;
3689 case 4: VT = MVT::i32; break;
3690 case 2: VT = MVT::i16; break;
3691 default: VT = MVT::i8; break;
3696 while (!TLI.isTypeLegal(LVT))
3697 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3698 assert(LVT.isInteger());
3704 unsigned NumMemOps = 0;
3706 unsigned VTSize = VT.getSizeInBits() / 8;
3707 while (VTSize > Size) {
3708 // For now, only use non-vector load / store's for the left-over pieces.
3713 if (VT.isVector() || VT.isFloatingPoint()) {
3714 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3715 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3716 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3718 else if (NewVT == MVT::i64 &&
3719 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3720 TLI.isSafeMemOpType(MVT::f64)) {
3721 // i64 is usually not legal on 32-bit targets, but f64 may be.
3729 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3730 if (NewVT == MVT::i8)
3732 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3734 NewVTSize = NewVT.getSizeInBits() / 8;
3736 // If the new VT cannot cover all of the remaining bits, then consider
3737 // issuing a (or a pair of) unaligned and overlapping load / store.
3738 // FIXME: Only does this for 64-bit or more since we don't have proper
3739 // cost model for unaligned load / store.
3742 if (NumMemOps && AllowOverlap &&
3743 VTSize >= 8 && NewVTSize < Size &&
3744 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3752 if (++NumMemOps > Limit)
3755 MemOps.push_back(VT);
3762 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3763 SDValue Chain, SDValue Dst,
3764 SDValue Src, uint64_t Size,
3765 unsigned Align, bool isVol,
3767 MachinePointerInfo DstPtrInfo,
3768 MachinePointerInfo SrcPtrInfo) {
3769 // Turn a memcpy of undef to nop.
3770 if (Src.getOpcode() == ISD::UNDEF)
3773 // Expand memcpy to a series of load and store ops if the size operand falls
3774 // below a certain threshold.
3775 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3776 // rather than maybe a humongous number of loads and stores.
3777 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3778 std::vector<EVT> MemOps;
3779 bool DstAlignCanChange = false;
3780 MachineFunction &MF = DAG.getMachineFunction();
3781 MachineFrameInfo *MFI = MF.getFrameInfo();
3783 MF.getFunction()->getAttributes().
3784 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3785 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3786 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3787 DstAlignCanChange = true;
3788 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3789 if (Align > SrcAlign)
3792 bool CopyFromStr = isMemSrcFromString(Src, Str);
3793 bool isZeroStr = CopyFromStr && Str.empty();
3794 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3796 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3797 (DstAlignCanChange ? 0 : Align),
3798 (isZeroStr ? 0 : SrcAlign),
3799 false, false, CopyFromStr, true, DAG, TLI))
3802 if (DstAlignCanChange) {
3803 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3804 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3806 // Don't promote to an alignment that would require dynamic stack
3808 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3809 if (!TRI->needsStackRealignment(MF))
3810 while (NewAlign > Align &&
3811 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3814 if (NewAlign > Align) {
3815 // Give the stack frame object a larger alignment if needed.
3816 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3817 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3822 SmallVector<SDValue, 8> OutChains;
3823 unsigned NumMemOps = MemOps.size();
3824 uint64_t SrcOff = 0, DstOff = 0;
3825 for (unsigned i = 0; i != NumMemOps; ++i) {
3827 unsigned VTSize = VT.getSizeInBits() / 8;
3828 SDValue Value, Store;
3830 if (VTSize > Size) {
3831 // Issuing an unaligned load / store pair that overlaps with the previous
3832 // pair. Adjust the offset accordingly.
3833 assert(i == NumMemOps-1 && i != 0);
3834 SrcOff -= VTSize - Size;
3835 DstOff -= VTSize - Size;
3839 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3840 // It's unlikely a store of a vector immediate can be done in a single
3841 // instruction. It would require a load from a constantpool first.
3842 // We only handle zero vectors here.
3843 // FIXME: Handle other cases where store of vector immediate is done in
3844 // a single instruction.
3845 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3846 if (Value.getNode())
3847 Store = DAG.getStore(Chain, dl, Value,
3848 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3849 DstPtrInfo.getWithOffset(DstOff), isVol,
3853 if (!Store.getNode()) {
3854 // The type might not be legal for the target. This should only happen
3855 // if the type is smaller than a legal type, as on PPC, so the right
3856 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3857 // to Load/Store if NVT==VT.
3858 // FIXME does the case above also need this?
3859 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3860 assert(NVT.bitsGE(VT));
3861 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3862 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3863 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3864 MinAlign(SrcAlign, SrcOff));
3865 Store = DAG.getTruncStore(Chain, dl, Value,
3866 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3867 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3870 OutChains.push_back(Store);
3876 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3879 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3880 SDValue Chain, SDValue Dst,
3881 SDValue Src, uint64_t Size,
3882 unsigned Align, bool isVol,
3884 MachinePointerInfo DstPtrInfo,
3885 MachinePointerInfo SrcPtrInfo) {
3886 // Turn a memmove of undef to nop.
3887 if (Src.getOpcode() == ISD::UNDEF)
3890 // Expand memmove to a series of load and store ops if the size operand falls
3891 // below a certain threshold.
3892 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3893 std::vector<EVT> MemOps;
3894 bool DstAlignCanChange = false;
3895 MachineFunction &MF = DAG.getMachineFunction();
3896 MachineFrameInfo *MFI = MF.getFrameInfo();
3897 bool OptSize = MF.getFunction()->getAttributes().
3898 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3899 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3900 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3901 DstAlignCanChange = true;
3902 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3903 if (Align > SrcAlign)
3905 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3907 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3908 (DstAlignCanChange ? 0 : Align), SrcAlign,
3909 false, false, false, false, DAG, TLI))
3912 if (DstAlignCanChange) {
3913 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3914 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3915 if (NewAlign > Align) {
3916 // Give the stack frame object a larger alignment if needed.
3917 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3918 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3923 uint64_t SrcOff = 0, DstOff = 0;
3924 SmallVector<SDValue, 8> LoadValues;
3925 SmallVector<SDValue, 8> LoadChains;
3926 SmallVector<SDValue, 8> OutChains;
3927 unsigned NumMemOps = MemOps.size();
3928 for (unsigned i = 0; i < NumMemOps; i++) {
3930 unsigned VTSize = VT.getSizeInBits() / 8;
3933 Value = DAG.getLoad(VT, dl, Chain,
3934 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3935 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3936 false, false, SrcAlign);
3937 LoadValues.push_back(Value);
3938 LoadChains.push_back(Value.getValue(1));
3941 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3943 for (unsigned i = 0; i < NumMemOps; i++) {
3945 unsigned VTSize = VT.getSizeInBits() / 8;
3948 Store = DAG.getStore(Chain, dl, LoadValues[i],
3949 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3950 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3951 OutChains.push_back(Store);
3955 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3958 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3961 /// \param DAG Selection DAG where lowered code is placed.
3962 /// \param dl Link to corresponding IR location.
3963 /// \param Chain Control flow dependency.
3964 /// \param Dst Pointer to destination memory location.
3965 /// \param Src Value of byte to write into the memory.
3966 /// \param Size Number of bytes to write.
3967 /// \param Align Alignment of the destination in bytes.
3968 /// \param isVol True if destination is volatile.
3969 /// \param DstPtrInfo IR information on the memory pointer.
3970 /// \returns New head in the control flow, if lowering was successful, empty
3971 /// SDValue otherwise.
3973 /// The function tries to replace 'llvm.memset' intrinsic with several store
3974 /// operations and value calculation code. This is usually profitable for small
3976 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3977 SDValue Chain, SDValue Dst,
3978 SDValue Src, uint64_t Size,
3979 unsigned Align, bool isVol,
3980 MachinePointerInfo DstPtrInfo) {
3981 // Turn a memset of undef to nop.
3982 if (Src.getOpcode() == ISD::UNDEF)
3985 // Expand memset to a series of load/store ops if the size operand
3986 // falls below a certain threshold.
3987 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3988 std::vector<EVT> MemOps;
3989 bool DstAlignCanChange = false;
3990 MachineFunction &MF = DAG.getMachineFunction();
3991 MachineFrameInfo *MFI = MF.getFrameInfo();
3992 bool OptSize = MF.getFunction()->getAttributes().
3993 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3994 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3995 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3996 DstAlignCanChange = true;
3998 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3999 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4000 Size, (DstAlignCanChange ? 0 : Align), 0,
4001 true, IsZeroVal, false, true, DAG, TLI))
4004 if (DstAlignCanChange) {
4005 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4006 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4007 if (NewAlign > Align) {
4008 // Give the stack frame object a larger alignment if needed.
4009 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4010 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4015 SmallVector<SDValue, 8> OutChains;
4016 uint64_t DstOff = 0;
4017 unsigned NumMemOps = MemOps.size();
4019 // Find the largest store and generate the bit pattern for it.
4020 EVT LargestVT = MemOps[0];
4021 for (unsigned i = 1; i < NumMemOps; i++)
4022 if (MemOps[i].bitsGT(LargestVT))
4023 LargestVT = MemOps[i];
4024 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4026 for (unsigned i = 0; i < NumMemOps; i++) {
4028 unsigned VTSize = VT.getSizeInBits() / 8;
4029 if (VTSize > Size) {
4030 // Issuing an unaligned load / store pair that overlaps with the previous
4031 // pair. Adjust the offset accordingly.
4032 assert(i == NumMemOps-1 && i != 0);
4033 DstOff -= VTSize - Size;
4036 // If this store is smaller than the largest store see whether we can get
4037 // the smaller value for free with a truncate.
4038 SDValue Value = MemSetValue;
4039 if (VT.bitsLT(LargestVT)) {
4040 if (!LargestVT.isVector() && !VT.isVector() &&
4041 TLI.isTruncateFree(LargestVT, VT))
4042 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4044 Value = getMemsetValue(Src, VT, DAG, dl);
4046 assert(Value.getValueType() == VT && "Value with wrong type.");
4047 SDValue Store = DAG.getStore(Chain, dl, Value,
4048 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4049 DstPtrInfo.getWithOffset(DstOff),
4050 isVol, false, Align);
4051 OutChains.push_back(Store);
4052 DstOff += VT.getSizeInBits() / 8;
4056 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4059 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4060 SDValue Src, SDValue Size,
4061 unsigned Align, bool isVol, bool AlwaysInline,
4062 MachinePointerInfo DstPtrInfo,
4063 MachinePointerInfo SrcPtrInfo) {
4064 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4066 // Check to see if we should lower the memcpy to loads and stores first.
4067 // For cases within the target-specified limits, this is the best choice.
4068 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4070 // Memcpy with size zero? Just return the original chain.
4071 if (ConstantSize->isNullValue())
4074 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4075 ConstantSize->getZExtValue(),Align,
4076 isVol, false, DstPtrInfo, SrcPtrInfo);
4077 if (Result.getNode())
4081 // Then check to see if we should lower the memcpy with target-specific
4082 // code. If the target chooses to do this, this is the next best.
4084 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4085 isVol, AlwaysInline,
4086 DstPtrInfo, SrcPtrInfo);
4087 if (Result.getNode())
4090 // If we really need inline code and the target declined to provide it,
4091 // use a (potentially long) sequence of loads and stores.
4093 assert(ConstantSize && "AlwaysInline requires a constant size!");
4094 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4095 ConstantSize->getZExtValue(), Align, isVol,
4096 true, DstPtrInfo, SrcPtrInfo);
4099 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4100 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4101 // respect volatile, so they may do things like read or write memory
4102 // beyond the given memory regions. But fixing this isn't easy, and most
4103 // people don't care.
4105 const TargetLowering *TLI = TM.getTargetLowering();
4107 // Emit a library call.
4108 TargetLowering::ArgListTy Args;
4109 TargetLowering::ArgListEntry Entry;
4110 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4111 Entry.Node = Dst; Args.push_back(Entry);
4112 Entry.Node = Src; Args.push_back(Entry);
4113 Entry.Node = Size; Args.push_back(Entry);
4114 // FIXME: pass in SDLoc
4116 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4117 false, false, false, false, 0,
4118 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4119 /*isTailCall=*/false,
4120 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4121 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4122 TLI->getPointerTy()),
4124 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4126 return CallResult.second;
4129 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4130 SDValue Src, SDValue Size,
4131 unsigned Align, bool isVol,
4132 MachinePointerInfo DstPtrInfo,
4133 MachinePointerInfo SrcPtrInfo) {
4134 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4136 // Check to see if we should lower the memmove to loads and stores first.
4137 // For cases within the target-specified limits, this is the best choice.
4138 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4140 // Memmove with size zero? Just return the original chain.
4141 if (ConstantSize->isNullValue())
4145 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4146 ConstantSize->getZExtValue(), Align, isVol,
4147 false, DstPtrInfo, SrcPtrInfo);
4148 if (Result.getNode())
4152 // Then check to see if we should lower the memmove with target-specific
4153 // code. If the target chooses to do this, this is the next best.
4155 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4156 DstPtrInfo, SrcPtrInfo);
4157 if (Result.getNode())
4160 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4161 // not be safe. See memcpy above for more details.
4163 const TargetLowering *TLI = TM.getTargetLowering();
4165 // Emit a library call.
4166 TargetLowering::ArgListTy Args;
4167 TargetLowering::ArgListEntry Entry;
4168 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4169 Entry.Node = Dst; Args.push_back(Entry);
4170 Entry.Node = Src; Args.push_back(Entry);
4171 Entry.Node = Size; Args.push_back(Entry);
4172 // FIXME: pass in SDLoc
4174 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4175 false, false, false, false, 0,
4176 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4177 /*isTailCall=*/false,
4178 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4179 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4180 TLI->getPointerTy()),
4182 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4184 return CallResult.second;
4187 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4188 SDValue Src, SDValue Size,
4189 unsigned Align, bool isVol,
4190 MachinePointerInfo DstPtrInfo) {
4191 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4193 // Check to see if we should lower the memset to stores first.
4194 // For cases within the target-specified limits, this is the best choice.
4195 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4197 // Memset with size zero? Just return the original chain.
4198 if (ConstantSize->isNullValue())
4202 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4203 Align, isVol, DstPtrInfo);
4205 if (Result.getNode())
4209 // Then check to see if we should lower the memset with target-specific
4210 // code. If the target chooses to do this, this is the next best.
4212 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4214 if (Result.getNode())
4217 // Emit a library call.
4218 const TargetLowering *TLI = TM.getTargetLowering();
4219 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4220 TargetLowering::ArgListTy Args;
4221 TargetLowering::ArgListEntry Entry;
4222 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4223 Args.push_back(Entry);
4224 // Extend or truncate the argument to be an i32 value for the call.
4225 if (Src.getValueType().bitsGT(MVT::i32))
4226 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4228 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4230 Entry.Ty = Type::getInt32Ty(*getContext());
4231 Entry.isSExt = true;
4232 Args.push_back(Entry);
4234 Entry.Ty = IntPtrTy;
4235 Entry.isSExt = false;
4236 Args.push_back(Entry);
4237 // FIXME: pass in SDLoc
4239 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4240 false, false, false, false, 0,
4241 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4242 /*isTailCall=*/false,
4243 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4244 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4245 TLI->getPointerTy()),
4247 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4249 return CallResult.second;
4252 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4253 SDVTList VTList, ArrayRef<SDValue> Ops,
4254 MachineMemOperand *MMO,
4255 AtomicOrdering SuccessOrdering,
4256 AtomicOrdering FailureOrdering,
4257 SynchronizationScope SynchScope) {
4258 FoldingSetNodeID ID;
4259 ID.AddInteger(MemVT.getRawBits());
4260 AddNodeIDNode(ID, Opcode, VTList, Ops);
4261 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4263 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4264 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4265 return SDValue(E, 0);
4268 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4269 // SDNode doesn't have access to it. This memory will be "leaked" when
4270 // the node is deallocated, but recovered when the allocator is released.
4271 // If the number of operands is less than 5 we use AtomicSDNode's internal
4273 unsigned NumOps = Ops.size();
4274 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4277 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4278 dl.getDebugLoc(), VTList, MemVT,
4279 Ops.data(), DynOps, NumOps, MMO,
4280 SuccessOrdering, FailureOrdering,
4282 CSEMap.InsertNode(N, IP);
4283 AllNodes.push_back(N);
4284 return SDValue(N, 0);
4287 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4288 SDVTList VTList, ArrayRef<SDValue> Ops,
4289 MachineMemOperand *MMO,
4290 AtomicOrdering Ordering,
4291 SynchronizationScope SynchScope) {
4292 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4293 Ordering, SynchScope);
4296 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4297 SDValue Chain, SDValue Ptr, SDValue Cmp,
4298 SDValue Swp, MachinePointerInfo PtrInfo,
4300 AtomicOrdering SuccessOrdering,
4301 AtomicOrdering FailureOrdering,
4302 SynchronizationScope SynchScope) {
4303 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4304 Alignment = getEVTAlignment(MemVT);
4306 MachineFunction &MF = getMachineFunction();
4308 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4309 // For now, atomics are considered to be volatile always.
4310 // FIXME: Volatile isn't really correct; we should keep track of atomic
4311 // orderings in the memoperand.
4312 unsigned Flags = MachineMemOperand::MOVolatile;
4313 if (Opcode != ISD::ATOMIC_STORE)
4314 Flags |= MachineMemOperand::MOLoad;
4315 if (Opcode != ISD::ATOMIC_LOAD)
4316 Flags |= MachineMemOperand::MOStore;
4318 MachineMemOperand *MMO =
4319 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4321 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4322 SuccessOrdering, FailureOrdering, SynchScope);
4325 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4327 SDValue Ptr, SDValue Cmp,
4328 SDValue Swp, MachineMemOperand *MMO,
4329 AtomicOrdering SuccessOrdering,
4330 AtomicOrdering FailureOrdering,
4331 SynchronizationScope SynchScope) {
4332 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4333 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4335 EVT VT = Cmp.getValueType();
4337 SDVTList VTs = getVTList(VT, MVT::Other);
4338 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4339 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4340 FailureOrdering, SynchScope);
4343 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4345 SDValue Ptr, SDValue Val,
4346 const Value* PtrVal,
4348 AtomicOrdering Ordering,
4349 SynchronizationScope SynchScope) {
4350 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4351 Alignment = getEVTAlignment(MemVT);
4353 MachineFunction &MF = getMachineFunction();
4354 // An atomic store does not load. An atomic load does not store.
4355 // (An atomicrmw obviously both loads and stores.)
4356 // For now, atomics are considered to be volatile always, and they are
4358 // FIXME: Volatile isn't really correct; we should keep track of atomic
4359 // orderings in the memoperand.
4360 unsigned Flags = MachineMemOperand::MOVolatile;
4361 if (Opcode != ISD::ATOMIC_STORE)
4362 Flags |= MachineMemOperand::MOLoad;
4363 if (Opcode != ISD::ATOMIC_LOAD)
4364 Flags |= MachineMemOperand::MOStore;
4366 MachineMemOperand *MMO =
4367 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4368 MemVT.getStoreSize(), Alignment);
4370 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4371 Ordering, SynchScope);
4374 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4376 SDValue Ptr, SDValue Val,
4377 MachineMemOperand *MMO,
4378 AtomicOrdering Ordering,
4379 SynchronizationScope SynchScope) {
4380 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4381 Opcode == ISD::ATOMIC_LOAD_SUB ||
4382 Opcode == ISD::ATOMIC_LOAD_AND ||
4383 Opcode == ISD::ATOMIC_LOAD_OR ||
4384 Opcode == ISD::ATOMIC_LOAD_XOR ||
4385 Opcode == ISD::ATOMIC_LOAD_NAND ||
4386 Opcode == ISD::ATOMIC_LOAD_MIN ||
4387 Opcode == ISD::ATOMIC_LOAD_MAX ||
4388 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4389 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4390 Opcode == ISD::ATOMIC_SWAP ||
4391 Opcode == ISD::ATOMIC_STORE) &&
4392 "Invalid Atomic Op");
4394 EVT VT = Val.getValueType();
4396 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4397 getVTList(VT, MVT::Other);
4398 SDValue Ops[] = {Chain, Ptr, Val};
4399 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4402 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4403 EVT VT, SDValue Chain,
4405 MachineMemOperand *MMO,
4406 AtomicOrdering Ordering,
4407 SynchronizationScope SynchScope) {
4408 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4410 SDVTList VTs = getVTList(VT, MVT::Other);
4411 SDValue Ops[] = {Chain, Ptr};
4412 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4415 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4416 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4417 if (Ops.size() == 1)
4420 SmallVector<EVT, 4> VTs;
4421 VTs.reserve(Ops.size());
4422 for (unsigned i = 0; i < Ops.size(); ++i)
4423 VTs.push_back(Ops[i].getValueType());
4424 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4428 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4429 ArrayRef<SDValue> Ops,
4430 EVT MemVT, MachinePointerInfo PtrInfo,
4431 unsigned Align, bool Vol,
4432 bool ReadMem, bool WriteMem) {
4433 if (Align == 0) // Ensure that codegen never sees alignment 0
4434 Align = getEVTAlignment(MemVT);
4436 MachineFunction &MF = getMachineFunction();
4439 Flags |= MachineMemOperand::MOStore;
4441 Flags |= MachineMemOperand::MOLoad;
4443 Flags |= MachineMemOperand::MOVolatile;
4444 MachineMemOperand *MMO =
4445 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4447 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4451 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4452 ArrayRef<SDValue> Ops, EVT MemVT,
4453 MachineMemOperand *MMO) {
4454 assert((Opcode == ISD::INTRINSIC_VOID ||
4455 Opcode == ISD::INTRINSIC_W_CHAIN ||
4456 Opcode == ISD::PREFETCH ||
4457 Opcode == ISD::LIFETIME_START ||
4458 Opcode == ISD::LIFETIME_END ||
4459 (Opcode <= INT_MAX &&
4460 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4461 "Opcode is not a memory-accessing opcode!");
4463 // Memoize the node unless it returns a flag.
4464 MemIntrinsicSDNode *N;
4465 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4466 FoldingSetNodeID ID;
4467 AddNodeIDNode(ID, Opcode, VTList, Ops);
4468 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4470 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4471 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4472 return SDValue(E, 0);
4475 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4476 dl.getDebugLoc(), VTList, Ops,
4478 CSEMap.InsertNode(N, IP);
4480 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4481 dl.getDebugLoc(), VTList, Ops,
4484 AllNodes.push_back(N);
4485 return SDValue(N, 0);
4488 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4489 /// MachinePointerInfo record from it. This is particularly useful because the
4490 /// code generator has many cases where it doesn't bother passing in a
4491 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4492 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4493 // If this is FI+Offset, we can model it.
4494 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4495 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4497 // If this is (FI+Offset1)+Offset2, we can model it.
4498 if (Ptr.getOpcode() != ISD::ADD ||
4499 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4500 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4501 return MachinePointerInfo();
4503 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4504 return MachinePointerInfo::getFixedStack(FI, Offset+
4505 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4508 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4509 /// MachinePointerInfo record from it. This is particularly useful because the
4510 /// code generator has many cases where it doesn't bother passing in a
4511 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4512 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4513 // If the 'Offset' value isn't a constant, we can't handle this.
4514 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4515 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4516 if (OffsetOp.getOpcode() == ISD::UNDEF)
4517 return InferPointerInfo(Ptr);
4518 return MachinePointerInfo();
4523 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4524 EVT VT, SDLoc dl, SDValue Chain,
4525 SDValue Ptr, SDValue Offset,
4526 MachinePointerInfo PtrInfo, EVT MemVT,
4527 bool isVolatile, bool isNonTemporal, bool isInvariant,
4528 unsigned Alignment, const MDNode *TBAAInfo,
4529 const MDNode *Ranges) {
4530 assert(Chain.getValueType() == MVT::Other &&
4531 "Invalid chain type");
4532 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4533 Alignment = getEVTAlignment(VT);
4535 unsigned Flags = MachineMemOperand::MOLoad;
4537 Flags |= MachineMemOperand::MOVolatile;
4539 Flags |= MachineMemOperand::MONonTemporal;
4541 Flags |= MachineMemOperand::MOInvariant;
4543 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4545 if (PtrInfo.V.isNull())
4546 PtrInfo = InferPointerInfo(Ptr, Offset);
4548 MachineFunction &MF = getMachineFunction();
4549 MachineMemOperand *MMO =
4550 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4552 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4556 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4557 EVT VT, SDLoc dl, SDValue Chain,
4558 SDValue Ptr, SDValue Offset, EVT MemVT,
4559 MachineMemOperand *MMO) {
4561 ExtType = ISD::NON_EXTLOAD;
4562 } else if (ExtType == ISD::NON_EXTLOAD) {
4563 assert(VT == MemVT && "Non-extending load from different memory type!");
4566 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4567 "Should only be an extending load, not truncating!");
4568 assert(VT.isInteger() == MemVT.isInteger() &&
4569 "Cannot convert from FP to Int or Int -> FP!");
4570 assert(VT.isVector() == MemVT.isVector() &&
4571 "Cannot use trunc store to convert to or from a vector!");
4572 assert((!VT.isVector() ||
4573 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4574 "Cannot use trunc store to change the number of vector elements!");
4577 bool Indexed = AM != ISD::UNINDEXED;
4578 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4579 "Unindexed load with an offset!");
4581 SDVTList VTs = Indexed ?
4582 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4583 SDValue Ops[] = { Chain, Ptr, Offset };
4584 FoldingSetNodeID ID;
4585 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4586 ID.AddInteger(MemVT.getRawBits());
4587 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4588 MMO->isNonTemporal(),
4589 MMO->isInvariant()));
4590 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4592 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4593 cast<LoadSDNode>(E)->refineAlignment(MMO);
4594 return SDValue(E, 0);
4596 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4597 dl.getDebugLoc(), VTs, AM, ExtType,
4599 CSEMap.InsertNode(N, IP);
4600 AllNodes.push_back(N);
4601 return SDValue(N, 0);
4604 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4605 SDValue Chain, SDValue Ptr,
4606 MachinePointerInfo PtrInfo,
4607 bool isVolatile, bool isNonTemporal,
4608 bool isInvariant, unsigned Alignment,
4609 const MDNode *TBAAInfo,
4610 const MDNode *Ranges) {
4611 SDValue Undef = getUNDEF(Ptr.getValueType());
4612 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4613 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4617 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4618 SDValue Chain, SDValue Ptr,
4619 MachineMemOperand *MMO) {
4620 SDValue Undef = getUNDEF(Ptr.getValueType());
4621 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4625 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4626 SDValue Chain, SDValue Ptr,
4627 MachinePointerInfo PtrInfo, EVT MemVT,
4628 bool isVolatile, bool isNonTemporal,
4629 unsigned Alignment, const MDNode *TBAAInfo) {
4630 SDValue Undef = getUNDEF(Ptr.getValueType());
4631 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4632 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4637 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4638 SDValue Chain, SDValue Ptr, EVT MemVT,
4639 MachineMemOperand *MMO) {
4640 SDValue Undef = getUNDEF(Ptr.getValueType());
4641 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4646 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4647 SDValue Offset, ISD::MemIndexedMode AM) {
4648 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4649 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4650 "Load is already a indexed load!");
4651 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4652 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4653 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4654 false, LD->getAlignment());
4657 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4658 SDValue Ptr, MachinePointerInfo PtrInfo,
4659 bool isVolatile, bool isNonTemporal,
4660 unsigned Alignment, const MDNode *TBAAInfo) {
4661 assert(Chain.getValueType() == MVT::Other &&
4662 "Invalid chain type");
4663 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4664 Alignment = getEVTAlignment(Val.getValueType());
4666 unsigned Flags = MachineMemOperand::MOStore;
4668 Flags |= MachineMemOperand::MOVolatile;
4670 Flags |= MachineMemOperand::MONonTemporal;
4672 if (PtrInfo.V.isNull())
4673 PtrInfo = InferPointerInfo(Ptr);
4675 MachineFunction &MF = getMachineFunction();
4676 MachineMemOperand *MMO =
4677 MF.getMachineMemOperand(PtrInfo, Flags,
4678 Val.getValueType().getStoreSize(), Alignment,
4681 return getStore(Chain, dl, Val, Ptr, MMO);
4684 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4685 SDValue Ptr, MachineMemOperand *MMO) {
4686 assert(Chain.getValueType() == MVT::Other &&
4687 "Invalid chain type");
4688 EVT VT = Val.getValueType();
4689 SDVTList VTs = getVTList(MVT::Other);
4690 SDValue Undef = getUNDEF(Ptr.getValueType());
4691 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4692 FoldingSetNodeID ID;
4693 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4694 ID.AddInteger(VT.getRawBits());
4695 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4696 MMO->isNonTemporal(), MMO->isInvariant()));
4697 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4699 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4700 cast<StoreSDNode>(E)->refineAlignment(MMO);
4701 return SDValue(E, 0);
4703 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4704 dl.getDebugLoc(), VTs,
4705 ISD::UNINDEXED, false, VT, MMO);
4706 CSEMap.InsertNode(N, IP);
4707 AllNodes.push_back(N);
4708 return SDValue(N, 0);
4711 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4712 SDValue Ptr, MachinePointerInfo PtrInfo,
4713 EVT SVT,bool isVolatile, bool isNonTemporal,
4715 const MDNode *TBAAInfo) {
4716 assert(Chain.getValueType() == MVT::Other &&
4717 "Invalid chain type");
4718 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4719 Alignment = getEVTAlignment(SVT);
4721 unsigned Flags = MachineMemOperand::MOStore;
4723 Flags |= MachineMemOperand::MOVolatile;
4725 Flags |= MachineMemOperand::MONonTemporal;
4727 if (PtrInfo.V.isNull())
4728 PtrInfo = InferPointerInfo(Ptr);
4730 MachineFunction &MF = getMachineFunction();
4731 MachineMemOperand *MMO =
4732 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4735 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4738 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4739 SDValue Ptr, EVT SVT,
4740 MachineMemOperand *MMO) {
4741 EVT VT = Val.getValueType();
4743 assert(Chain.getValueType() == MVT::Other &&
4744 "Invalid chain type");
4746 return getStore(Chain, dl, Val, Ptr, MMO);
4748 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4749 "Should only be a truncating store, not extending!");
4750 assert(VT.isInteger() == SVT.isInteger() &&
4751 "Can't do FP-INT conversion!");
4752 assert(VT.isVector() == SVT.isVector() &&
4753 "Cannot use trunc store to convert to or from a vector!");
4754 assert((!VT.isVector() ||
4755 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4756 "Cannot use trunc store to change the number of vector elements!");
4758 SDVTList VTs = getVTList(MVT::Other);
4759 SDValue Undef = getUNDEF(Ptr.getValueType());
4760 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4761 FoldingSetNodeID ID;
4762 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4763 ID.AddInteger(SVT.getRawBits());
4764 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4765 MMO->isNonTemporal(), MMO->isInvariant()));
4766 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4768 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4769 cast<StoreSDNode>(E)->refineAlignment(MMO);
4770 return SDValue(E, 0);
4772 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4773 dl.getDebugLoc(), VTs,
4774 ISD::UNINDEXED, true, SVT, MMO);
4775 CSEMap.InsertNode(N, IP);
4776 AllNodes.push_back(N);
4777 return SDValue(N, 0);
4781 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4782 SDValue Offset, ISD::MemIndexedMode AM) {
4783 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4784 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4785 "Store is already a indexed store!");
4786 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4787 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4788 FoldingSetNodeID ID;
4789 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4790 ID.AddInteger(ST->getMemoryVT().getRawBits());
4791 ID.AddInteger(ST->getRawSubclassData());
4792 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4794 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4795 return SDValue(E, 0);
4797 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4798 dl.getDebugLoc(), VTs, AM,
4799 ST->isTruncatingStore(),
4801 ST->getMemOperand());
4802 CSEMap.InsertNode(N, IP);
4803 AllNodes.push_back(N);
4804 return SDValue(N, 0);
4807 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4808 SDValue Chain, SDValue Ptr,
4811 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4812 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4815 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4816 ArrayRef<SDUse> Ops) {
4817 switch (Ops.size()) {
4818 case 0: return getNode(Opcode, DL, VT);
4819 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4820 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4821 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4825 // Copy from an SDUse array into an SDValue array for use with
4826 // the regular getNode logic.
4827 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4828 return getNode(Opcode, DL, VT, NewOps);
4831 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4832 ArrayRef<SDValue> Ops) {
4833 unsigned NumOps = Ops.size();
4835 case 0: return getNode(Opcode, DL, VT);
4836 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4837 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4838 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4844 case ISD::SELECT_CC: {
4845 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4846 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4847 "LHS and RHS of condition must have same type!");
4848 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4849 "True and False arms of SelectCC must have same type!");
4850 assert(Ops[2].getValueType() == VT &&
4851 "select_cc node must be of same type as true and false value!");
4855 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4856 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4857 "LHS/RHS of comparison should match types!");
4864 SDVTList VTs = getVTList(VT);
4866 if (VT != MVT::Glue) {
4867 FoldingSetNodeID ID;
4868 AddNodeIDNode(ID, Opcode, VTs, Ops);
4871 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4872 return SDValue(E, 0);
4874 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4876 CSEMap.InsertNode(N, IP);
4878 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4882 AllNodes.push_back(N);
4886 return SDValue(N, 0);
4889 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4890 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4891 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4894 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4895 ArrayRef<SDValue> Ops) {
4896 if (VTList.NumVTs == 1)
4897 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4901 // FIXME: figure out how to safely handle things like
4902 // int foo(int x) { return 1 << (x & 255); }
4903 // int bar() { return foo(256); }
4904 case ISD::SRA_PARTS:
4905 case ISD::SRL_PARTS:
4906 case ISD::SHL_PARTS:
4907 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4908 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4909 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4910 else if (N3.getOpcode() == ISD::AND)
4911 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4912 // If the and is only masking out bits that cannot effect the shift,
4913 // eliminate the and.
4914 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4915 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4916 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4922 // Memoize the node unless it returns a flag.
4924 unsigned NumOps = Ops.size();
4925 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4926 FoldingSetNodeID ID;
4927 AddNodeIDNode(ID, Opcode, VTList, Ops);
4929 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4930 return SDValue(E, 0);
4933 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4934 DL.getDebugLoc(), VTList, Ops[0]);
4935 } else if (NumOps == 2) {
4936 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4937 DL.getDebugLoc(), VTList, Ops[0],
4939 } else if (NumOps == 3) {
4940 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4941 DL.getDebugLoc(), VTList, Ops[0],
4944 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4947 CSEMap.InsertNode(N, IP);
4950 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4951 DL.getDebugLoc(), VTList, Ops[0]);
4952 } else if (NumOps == 2) {
4953 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4954 DL.getDebugLoc(), VTList, Ops[0],
4956 } else if (NumOps == 3) {
4957 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4958 DL.getDebugLoc(), VTList, Ops[0],
4961 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4965 AllNodes.push_back(N);
4969 return SDValue(N, 0);
4972 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4973 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4976 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4978 SDValue Ops[] = { N1 };
4979 return getNode(Opcode, DL, VTList, Ops);
4982 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4983 SDValue N1, SDValue N2) {
4984 SDValue Ops[] = { N1, N2 };
4985 return getNode(Opcode, DL, VTList, Ops);
4988 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4989 SDValue N1, SDValue N2, SDValue N3) {
4990 SDValue Ops[] = { N1, N2, N3 };
4991 return getNode(Opcode, DL, VTList, Ops);
4994 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4995 SDValue N1, SDValue N2, SDValue N3,
4997 SDValue Ops[] = { N1, N2, N3, N4 };
4998 return getNode(Opcode, DL, VTList, Ops);
5001 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5002 SDValue N1, SDValue N2, SDValue N3,
5003 SDValue N4, SDValue N5) {
5004 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5005 return getNode(Opcode, DL, VTList, Ops);
5008 SDVTList SelectionDAG::getVTList(EVT VT) {
5009 return makeVTList(SDNode::getValueTypeList(VT), 1);
5012 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5013 FoldingSetNodeID ID;
5015 ID.AddInteger(VT1.getRawBits());
5016 ID.AddInteger(VT2.getRawBits());
5019 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5021 EVT *Array = Allocator.Allocate<EVT>(2);
5024 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5025 VTListMap.InsertNode(Result, IP);
5027 return Result->getSDVTList();
5030 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5031 FoldingSetNodeID ID;
5033 ID.AddInteger(VT1.getRawBits());
5034 ID.AddInteger(VT2.getRawBits());
5035 ID.AddInteger(VT3.getRawBits());
5038 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5040 EVT *Array = Allocator.Allocate<EVT>(3);
5044 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5045 VTListMap.InsertNode(Result, IP);
5047 return Result->getSDVTList();
5050 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5051 FoldingSetNodeID ID;
5053 ID.AddInteger(VT1.getRawBits());
5054 ID.AddInteger(VT2.getRawBits());
5055 ID.AddInteger(VT3.getRawBits());
5056 ID.AddInteger(VT4.getRawBits());
5059 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5061 EVT *Array = Allocator.Allocate<EVT>(4);
5066 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5067 VTListMap.InsertNode(Result, IP);
5069 return Result->getSDVTList();
5072 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5073 unsigned NumVTs = VTs.size();
5074 FoldingSetNodeID ID;
5075 ID.AddInteger(NumVTs);
5076 for (unsigned index = 0; index < NumVTs; index++) {
5077 ID.AddInteger(VTs[index].getRawBits());
5081 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5083 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5084 std::copy(VTs.begin(), VTs.end(), Array);
5085 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5086 VTListMap.InsertNode(Result, IP);
5088 return Result->getSDVTList();
5092 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5093 /// specified operands. If the resultant node already exists in the DAG,
5094 /// this does not modify the specified node, instead it returns the node that
5095 /// already exists. If the resultant node does not exist in the DAG, the
5096 /// input node is returned. As a degenerate case, if you specify the same
5097 /// input operands as the node already has, the input node is returned.
5098 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5099 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5101 // Check to see if there is no change.
5102 if (Op == N->getOperand(0)) return N;
5104 // See if the modified node already exists.
5105 void *InsertPos = nullptr;
5106 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5109 // Nope it doesn't. Remove the node from its current place in the maps.
5111 if (!RemoveNodeFromCSEMaps(N))
5112 InsertPos = nullptr;
5114 // Now we update the operands.
5115 N->OperandList[0].set(Op);
5117 // If this gets put into a CSE map, add it.
5118 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5122 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5123 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5125 // Check to see if there is no change.
5126 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5127 return N; // No operands changed, just return the input node.
5129 // See if the modified node already exists.
5130 void *InsertPos = nullptr;
5131 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5134 // Nope it doesn't. Remove the node from its current place in the maps.
5136 if (!RemoveNodeFromCSEMaps(N))
5137 InsertPos = nullptr;
5139 // Now we update the operands.
5140 if (N->OperandList[0] != Op1)
5141 N->OperandList[0].set(Op1);
5142 if (N->OperandList[1] != Op2)
5143 N->OperandList[1].set(Op2);
5145 // If this gets put into a CSE map, add it.
5146 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5150 SDNode *SelectionDAG::
5151 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5152 SDValue Ops[] = { Op1, Op2, Op3 };
5153 return UpdateNodeOperands(N, Ops);
5156 SDNode *SelectionDAG::
5157 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5158 SDValue Op3, SDValue Op4) {
5159 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5160 return UpdateNodeOperands(N, Ops);
5163 SDNode *SelectionDAG::
5164 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5165 SDValue Op3, SDValue Op4, SDValue Op5) {
5166 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5167 return UpdateNodeOperands(N, Ops);
5170 SDNode *SelectionDAG::
5171 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5172 unsigned NumOps = Ops.size();
5173 assert(N->getNumOperands() == NumOps &&
5174 "Update with wrong number of operands");
5176 // Check to see if there is no change.
5177 bool AnyChange = false;
5178 for (unsigned i = 0; i != NumOps; ++i) {
5179 if (Ops[i] != N->getOperand(i)) {
5185 // No operands changed, just return the input node.
5186 if (!AnyChange) return N;
5188 // See if the modified node already exists.
5189 void *InsertPos = nullptr;
5190 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5193 // Nope it doesn't. Remove the node from its current place in the maps.
5195 if (!RemoveNodeFromCSEMaps(N))
5196 InsertPos = nullptr;
5198 // Now we update the operands.
5199 for (unsigned i = 0; i != NumOps; ++i)
5200 if (N->OperandList[i] != Ops[i])
5201 N->OperandList[i].set(Ops[i]);
5203 // If this gets put into a CSE map, add it.
5204 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5208 /// DropOperands - Release the operands and set this node to have
5210 void SDNode::DropOperands() {
5211 // Unlike the code in MorphNodeTo that does this, we don't need to
5212 // watch for dead nodes here.
5213 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5219 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5222 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5224 SDVTList VTs = getVTList(VT);
5225 return SelectNodeTo(N, MachineOpc, VTs, None);
5228 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5229 EVT VT, SDValue Op1) {
5230 SDVTList VTs = getVTList(VT);
5231 SDValue Ops[] = { Op1 };
5232 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5235 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5236 EVT VT, SDValue Op1,
5238 SDVTList VTs = getVTList(VT);
5239 SDValue Ops[] = { Op1, Op2 };
5240 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5243 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5244 EVT VT, SDValue Op1,
5245 SDValue Op2, SDValue Op3) {
5246 SDVTList VTs = getVTList(VT);
5247 SDValue Ops[] = { Op1, Op2, Op3 };
5248 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5251 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5252 EVT VT, ArrayRef<SDValue> Ops) {
5253 SDVTList VTs = getVTList(VT);
5254 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5257 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5259 SDVTList VTs = getVTList(VT1, VT2);
5260 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5263 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5265 SDVTList VTs = getVTList(VT1, VT2);
5266 return SelectNodeTo(N, MachineOpc, VTs, None);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 EVT VT1, EVT VT2, EVT VT3,
5271 ArrayRef<SDValue> Ops) {
5272 SDVTList VTs = getVTList(VT1, VT2, VT3);
5273 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5276 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5277 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5278 ArrayRef<SDValue> Ops) {
5279 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5280 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 SDVTList VTs = getVTList(VT1, VT2);
5287 SDValue Ops[] = { Op1 };
5288 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5291 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 SDValue Op1, SDValue Op2) {
5294 SDVTList VTs = getVTList(VT1, VT2);
5295 SDValue Ops[] = { Op1, Op2 };
5296 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5299 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5301 SDValue Op1, SDValue Op2,
5303 SDVTList VTs = getVTList(VT1, VT2);
5304 SDValue Ops[] = { Op1, Op2, Op3 };
5305 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5308 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5309 EVT VT1, EVT VT2, EVT VT3,
5310 SDValue Op1, SDValue Op2,
5312 SDVTList VTs = getVTList(VT1, VT2, VT3);
5313 SDValue Ops[] = { Op1, Op2, Op3 };
5314 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5317 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5318 SDVTList VTs,ArrayRef<SDValue> Ops) {
5319 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5320 // Reset the NodeID to -1.
5325 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5326 /// the line number information on the merged node since it is not possible to
5327 /// preserve the information that operation is associated with multiple lines.
5328 /// This will make the debugger working better at -O0, were there is a higher
5329 /// probability having other instructions associated with that line.
5331 /// For IROrder, we keep the smaller of the two
5332 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5333 DebugLoc NLoc = N->getDebugLoc();
5334 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5335 (OLoc.getDebugLoc() != NLoc)) {
5336 N->setDebugLoc(DebugLoc());
5338 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5339 N->setIROrder(Order);
5343 /// MorphNodeTo - This *mutates* the specified node to have the specified
5344 /// return type, opcode, and operands.
5346 /// Note that MorphNodeTo returns the resultant node. If there is already a
5347 /// node of the specified opcode and operands, it returns that node instead of
5348 /// the current one. Note that the SDLoc need not be the same.
5350 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5351 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5352 /// node, and because it doesn't require CSE recalculation for any of
5353 /// the node's users.
5355 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5356 SDVTList VTs, ArrayRef<SDValue> Ops) {
5357 unsigned NumOps = Ops.size();
5358 // If an identical node already exists, use it.
5360 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5361 FoldingSetNodeID ID;
5362 AddNodeIDNode(ID, Opc, VTs, Ops);
5363 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5364 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5367 if (!RemoveNodeFromCSEMaps(N))
5370 // Start the morphing.
5372 N->ValueList = VTs.VTs;
5373 N->NumValues = VTs.NumVTs;
5375 // Clear the operands list, updating used nodes to remove this from their
5376 // use list. Keep track of any operands that become dead as a result.
5377 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5378 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5380 SDNode *Used = Use.getNode();
5382 if (Used->use_empty())
5383 DeadNodeSet.insert(Used);
5386 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5387 // Initialize the memory references information.
5388 MN->setMemRefs(nullptr, nullptr);
5389 // If NumOps is larger than the # of operands we can have in a
5390 // MachineSDNode, reallocate the operand list.
5391 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5392 if (MN->OperandsNeedDelete)
5393 delete[] MN->OperandList;
5394 if (NumOps > array_lengthof(MN->LocalOperands))
5395 // We're creating a final node that will live unmorphed for the
5396 // remainder of the current SelectionDAG iteration, so we can allocate
5397 // the operands directly out of a pool with no recycling metadata.
5398 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5399 Ops.data(), NumOps);
5401 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5402 MN->OperandsNeedDelete = false;
5404 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5406 // If NumOps is larger than the # of operands we currently have, reallocate
5407 // the operand list.
5408 if (NumOps > N->NumOperands) {
5409 if (N->OperandsNeedDelete)
5410 delete[] N->OperandList;
5411 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5412 N->OperandsNeedDelete = true;
5414 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5417 // Delete any nodes that are still dead after adding the uses for the
5419 if (!DeadNodeSet.empty()) {
5420 SmallVector<SDNode *, 16> DeadNodes;
5421 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5422 E = DeadNodeSet.end(); I != E; ++I)
5423 if ((*I)->use_empty())
5424 DeadNodes.push_back(*I);
5425 RemoveDeadNodes(DeadNodes);
5429 CSEMap.InsertNode(N, IP); // Memoize the new node.
5434 /// getMachineNode - These are used for target selectors to create a new node
5435 /// with specified return type(s), MachineInstr opcode, and operands.
5437 /// Note that getMachineNode returns the resultant node. If there is already a
5438 /// node of the specified opcode and operands, it returns that node instead of
5439 /// the current one.
5441 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5442 SDVTList VTs = getVTList(VT);
5443 return getMachineNode(Opcode, dl, VTs, None);
5447 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5448 SDVTList VTs = getVTList(VT);
5449 SDValue Ops[] = { Op1 };
5450 return getMachineNode(Opcode, dl, VTs, Ops);
5454 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5455 SDValue Op1, SDValue Op2) {
5456 SDVTList VTs = getVTList(VT);
5457 SDValue Ops[] = { Op1, Op2 };
5458 return getMachineNode(Opcode, dl, VTs, Ops);
5462 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5463 SDValue Op1, SDValue Op2, SDValue Op3) {
5464 SDVTList VTs = getVTList(VT);
5465 SDValue Ops[] = { Op1, Op2, Op3 };
5466 return getMachineNode(Opcode, dl, VTs, Ops);
5470 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5471 ArrayRef<SDValue> Ops) {
5472 SDVTList VTs = getVTList(VT);
5473 return getMachineNode(Opcode, dl, VTs, Ops);
5477 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5478 SDVTList VTs = getVTList(VT1, VT2);
5479 return getMachineNode(Opcode, dl, VTs, None);
5483 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5484 EVT VT1, EVT VT2, SDValue Op1) {
5485 SDVTList VTs = getVTList(VT1, VT2);
5486 SDValue Ops[] = { Op1 };
5487 return getMachineNode(Opcode, dl, VTs, Ops);
5491 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5492 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5493 SDVTList VTs = getVTList(VT1, VT2);
5494 SDValue Ops[] = { Op1, Op2 };
5495 return getMachineNode(Opcode, dl, VTs, Ops);
5499 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5500 EVT VT1, EVT VT2, SDValue Op1,
5501 SDValue Op2, SDValue Op3) {
5502 SDVTList VTs = getVTList(VT1, VT2);
5503 SDValue Ops[] = { Op1, Op2, Op3 };
5504 return getMachineNode(Opcode, dl, VTs, Ops);
5508 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5510 ArrayRef<SDValue> Ops) {
5511 SDVTList VTs = getVTList(VT1, VT2);
5512 return getMachineNode(Opcode, dl, VTs, Ops);
5516 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5517 EVT VT1, EVT VT2, EVT VT3,
5518 SDValue Op1, SDValue Op2) {
5519 SDVTList VTs = getVTList(VT1, VT2, VT3);
5520 SDValue Ops[] = { Op1, Op2 };
5521 return getMachineNode(Opcode, dl, VTs, Ops);
5525 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5526 EVT VT1, EVT VT2, EVT VT3,
5527 SDValue Op1, SDValue Op2, SDValue Op3) {
5528 SDVTList VTs = getVTList(VT1, VT2, VT3);
5529 SDValue Ops[] = { Op1, Op2, Op3 };
5530 return getMachineNode(Opcode, dl, VTs, Ops);
5534 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5535 EVT VT1, EVT VT2, EVT VT3,
5536 ArrayRef<SDValue> Ops) {
5537 SDVTList VTs = getVTList(VT1, VT2, VT3);
5538 return getMachineNode(Opcode, dl, VTs, Ops);
5542 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5543 EVT VT2, EVT VT3, EVT VT4,
5544 ArrayRef<SDValue> Ops) {
5545 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5546 return getMachineNode(Opcode, dl, VTs, Ops);
5550 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5551 ArrayRef<EVT> ResultTys,
5552 ArrayRef<SDValue> Ops) {
5553 SDVTList VTs = getVTList(ResultTys);
5554 return getMachineNode(Opcode, dl, VTs, Ops);
5558 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5559 ArrayRef<SDValue> OpsArray) {
5560 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5563 const SDValue *Ops = OpsArray.data();
5564 unsigned NumOps = OpsArray.size();
5567 FoldingSetNodeID ID;
5568 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5570 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5571 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5575 // Allocate a new MachineSDNode.
5576 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5577 DL.getDebugLoc(), VTs);
5579 // Initialize the operands list.
5580 if (NumOps > array_lengthof(N->LocalOperands))
5581 // We're creating a final node that will live unmorphed for the
5582 // remainder of the current SelectionDAG iteration, so we can allocate
5583 // the operands directly out of a pool with no recycling metadata.
5584 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5587 N->InitOperands(N->LocalOperands, Ops, NumOps);
5588 N->OperandsNeedDelete = false;
5591 CSEMap.InsertNode(N, IP);
5593 AllNodes.push_back(N);
5595 VerifyMachineNode(N);
5600 /// getTargetExtractSubreg - A convenience function for creating
5601 /// TargetOpcode::EXTRACT_SUBREG nodes.
5603 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5605 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5606 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5607 VT, Operand, SRIdxVal);
5608 return SDValue(Subreg, 0);
5611 /// getTargetInsertSubreg - A convenience function for creating
5612 /// TargetOpcode::INSERT_SUBREG nodes.
5614 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5615 SDValue Operand, SDValue Subreg) {
5616 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5617 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5618 VT, Operand, Subreg, SRIdxVal);
5619 return SDValue(Result, 0);
5622 /// getNodeIfExists - Get the specified node if it's already available, or
5623 /// else return NULL.
5624 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5625 ArrayRef<SDValue> Ops) {
5626 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5627 FoldingSetNodeID ID;
5628 AddNodeIDNode(ID, Opcode, VTList, Ops);
5630 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5636 /// getDbgValue - Creates a SDDbgValue node.
5640 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5641 bool IsIndirect, uint64_t Off,
5642 DebugLoc DL, unsigned O) {
5643 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5648 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5650 DebugLoc DL, unsigned O) {
5651 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5656 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5657 DebugLoc DL, unsigned O) {
5658 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5663 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5664 /// pointed to by a use iterator is deleted, increment the use iterator
5665 /// so that it doesn't dangle.
5667 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5668 SDNode::use_iterator &UI;
5669 SDNode::use_iterator &UE;
5671 void NodeDeleted(SDNode *N, SDNode *E) override {
5672 // Increment the iterator as needed.
5673 while (UI != UE && N == *UI)
5678 RAUWUpdateListener(SelectionDAG &d,
5679 SDNode::use_iterator &ui,
5680 SDNode::use_iterator &ue)
5681 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5686 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5687 /// This can cause recursive merging of nodes in the DAG.
5689 /// This version assumes From has a single result value.
5691 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5692 SDNode *From = FromN.getNode();
5693 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5694 "Cannot replace with this method!");
5695 assert(From != To.getNode() && "Cannot replace uses of with self");
5697 // Iterate over all the existing uses of From. New uses will be added
5698 // to the beginning of the use list, which we avoid visiting.
5699 // This specifically avoids visiting uses of From that arise while the
5700 // replacement is happening, because any such uses would be the result
5701 // of CSE: If an existing node looks like From after one of its operands
5702 // is replaced by To, we don't want to replace of all its users with To
5703 // too. See PR3018 for more info.
5704 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5705 RAUWUpdateListener Listener(*this, UI, UE);
5709 // This node is about to morph, remove its old self from the CSE maps.
5710 RemoveNodeFromCSEMaps(User);
5712 // A user can appear in a use list multiple times, and when this
5713 // happens the uses are usually next to each other in the list.
5714 // To help reduce the number of CSE recomputations, process all
5715 // the uses of this user that we can find this way.
5717 SDUse &Use = UI.getUse();
5720 } while (UI != UE && *UI == User);
5722 // Now that we have modified User, add it back to the CSE maps. If it
5723 // already exists there, recursively merge the results together.
5724 AddModifiedNodeToCSEMaps(User);
5727 // If we just RAUW'd the root, take note.
5728 if (FromN == getRoot())
5732 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5733 /// This can cause recursive merging of nodes in the DAG.
5735 /// This version assumes that for each value of From, there is a
5736 /// corresponding value in To in the same position with the same type.
5738 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5740 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5741 assert((!From->hasAnyUseOfValue(i) ||
5742 From->getValueType(i) == To->getValueType(i)) &&
5743 "Cannot use this version of ReplaceAllUsesWith!");
5746 // Handle the trivial case.
5750 // Iterate over just the existing users of From. See the comments in
5751 // the ReplaceAllUsesWith above.
5752 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5753 RAUWUpdateListener Listener(*this, UI, UE);
5757 // This node is about to morph, remove its old self from the CSE maps.
5758 RemoveNodeFromCSEMaps(User);
5760 // A user can appear in a use list multiple times, and when this
5761 // happens the uses are usually next to each other in the list.
5762 // To help reduce the number of CSE recomputations, process all
5763 // the uses of this user that we can find this way.
5765 SDUse &Use = UI.getUse();
5768 } while (UI != UE && *UI == User);
5770 // Now that we have modified User, add it back to the CSE maps. If it
5771 // already exists there, recursively merge the results together.
5772 AddModifiedNodeToCSEMaps(User);
5775 // If we just RAUW'd the root, take note.
5776 if (From == getRoot().getNode())
5777 setRoot(SDValue(To, getRoot().getResNo()));
5780 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5781 /// This can cause recursive merging of nodes in the DAG.
5783 /// This version can replace From with any result values. To must match the
5784 /// number and types of values returned by From.
5785 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5786 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5787 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5789 // Iterate over just the existing users of From. See the comments in
5790 // the ReplaceAllUsesWith above.
5791 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5792 RAUWUpdateListener Listener(*this, UI, UE);
5796 // This node is about to morph, remove its old self from the CSE maps.
5797 RemoveNodeFromCSEMaps(User);
5799 // A user can appear in a use list multiple times, and when this
5800 // happens the uses are usually next to each other in the list.
5801 // To help reduce the number of CSE recomputations, process all
5802 // the uses of this user that we can find this way.
5804 SDUse &Use = UI.getUse();
5805 const SDValue &ToOp = To[Use.getResNo()];
5808 } while (UI != UE && *UI == User);
5810 // Now that we have modified User, add it back to the CSE maps. If it
5811 // already exists there, recursively merge the results together.
5812 AddModifiedNodeToCSEMaps(User);
5815 // If we just RAUW'd the root, take note.
5816 if (From == getRoot().getNode())
5817 setRoot(SDValue(To[getRoot().getResNo()]));
5820 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5821 /// uses of other values produced by From.getNode() alone. The Deleted
5822 /// vector is handled the same way as for ReplaceAllUsesWith.
5823 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5824 // Handle the really simple, really trivial case efficiently.
5825 if (From == To) return;
5827 // Handle the simple, trivial, case efficiently.
5828 if (From.getNode()->getNumValues() == 1) {
5829 ReplaceAllUsesWith(From, To);
5833 // Iterate over just the existing users of From. See the comments in
5834 // the ReplaceAllUsesWith above.
5835 SDNode::use_iterator UI = From.getNode()->use_begin(),
5836 UE = From.getNode()->use_end();
5837 RAUWUpdateListener Listener(*this, UI, UE);
5840 bool UserRemovedFromCSEMaps = false;
5842 // A user can appear in a use list multiple times, and when this
5843 // happens the uses are usually next to each other in the list.
5844 // To help reduce the number of CSE recomputations, process all
5845 // the uses of this user that we can find this way.
5847 SDUse &Use = UI.getUse();
5849 // Skip uses of different values from the same node.
5850 if (Use.getResNo() != From.getResNo()) {
5855 // If this node hasn't been modified yet, it's still in the CSE maps,
5856 // so remove its old self from the CSE maps.
5857 if (!UserRemovedFromCSEMaps) {
5858 RemoveNodeFromCSEMaps(User);
5859 UserRemovedFromCSEMaps = true;
5864 } while (UI != UE && *UI == User);
5866 // We are iterating over all uses of the From node, so if a use
5867 // doesn't use the specific value, no changes are made.
5868 if (!UserRemovedFromCSEMaps)
5871 // Now that we have modified User, add it back to the CSE maps. If it
5872 // already exists there, recursively merge the results together.
5873 AddModifiedNodeToCSEMaps(User);
5876 // If we just RAUW'd the root, take note.
5877 if (From == getRoot())
5882 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5883 /// to record information about a use.
5890 /// operator< - Sort Memos by User.
5891 bool operator<(const UseMemo &L, const UseMemo &R) {
5892 return (intptr_t)L.User < (intptr_t)R.User;
5896 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5897 /// uses of other values produced by From.getNode() alone. The same value
5898 /// may appear in both the From and To list. The Deleted vector is
5899 /// handled the same way as for ReplaceAllUsesWith.
5900 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5903 // Handle the simple, trivial case efficiently.
5905 return ReplaceAllUsesOfValueWith(*From, *To);
5907 // Read up all the uses and make records of them. This helps
5908 // processing new uses that are introduced during the
5909 // replacement process.
5910 SmallVector<UseMemo, 4> Uses;
5911 for (unsigned i = 0; i != Num; ++i) {
5912 unsigned FromResNo = From[i].getResNo();
5913 SDNode *FromNode = From[i].getNode();
5914 for (SDNode::use_iterator UI = FromNode->use_begin(),
5915 E = FromNode->use_end(); UI != E; ++UI) {
5916 SDUse &Use = UI.getUse();
5917 if (Use.getResNo() == FromResNo) {
5918 UseMemo Memo = { *UI, i, &Use };
5919 Uses.push_back(Memo);
5924 // Sort the uses, so that all the uses from a given User are together.
5925 std::sort(Uses.begin(), Uses.end());
5927 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5928 UseIndex != UseIndexEnd; ) {
5929 // We know that this user uses some value of From. If it is the right
5930 // value, update it.
5931 SDNode *User = Uses[UseIndex].User;
5933 // This node is about to morph, remove its old self from the CSE maps.
5934 RemoveNodeFromCSEMaps(User);
5936 // The Uses array is sorted, so all the uses for a given User
5937 // are next to each other in the list.
5938 // To help reduce the number of CSE recomputations, process all
5939 // the uses of this user that we can find this way.
5941 unsigned i = Uses[UseIndex].Index;
5942 SDUse &Use = *Uses[UseIndex].Use;
5946 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5948 // Now that we have modified User, add it back to the CSE maps. If it
5949 // already exists there, recursively merge the results together.
5950 AddModifiedNodeToCSEMaps(User);
5954 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5955 /// based on their topological order. It returns the maximum id and a vector
5956 /// of the SDNodes* in assigned order by reference.
5957 unsigned SelectionDAG::AssignTopologicalOrder() {
5959 unsigned DAGSize = 0;
5961 // SortedPos tracks the progress of the algorithm. Nodes before it are
5962 // sorted, nodes after it are unsorted. When the algorithm completes
5963 // it is at the end of the list.
5964 allnodes_iterator SortedPos = allnodes_begin();
5966 // Visit all the nodes. Move nodes with no operands to the front of
5967 // the list immediately. Annotate nodes that do have operands with their
5968 // operand count. Before we do this, the Node Id fields of the nodes
5969 // may contain arbitrary values. After, the Node Id fields for nodes
5970 // before SortedPos will contain the topological sort index, and the
5971 // Node Id fields for nodes At SortedPos and after will contain the
5972 // count of outstanding operands.
5973 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5976 unsigned Degree = N->getNumOperands();
5978 // A node with no uses, add it to the result array immediately.
5979 N->setNodeId(DAGSize++);
5980 allnodes_iterator Q = N;
5982 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5983 assert(SortedPos != AllNodes.end() && "Overran node list");
5986 // Temporarily use the Node Id as scratch space for the degree count.
5987 N->setNodeId(Degree);
5991 // Visit all the nodes. As we iterate, move nodes into sorted order,
5992 // such that by the time the end is reached all nodes will be sorted.
5993 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5996 // N is in sorted position, so all its uses have one less operand
5997 // that needs to be sorted.
5998 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6001 unsigned Degree = P->getNodeId();
6002 assert(Degree != 0 && "Invalid node degree");
6005 // All of P's operands are sorted, so P may sorted now.
6006 P->setNodeId(DAGSize++);
6008 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6009 assert(SortedPos != AllNodes.end() && "Overran node list");
6012 // Update P's outstanding operand count.
6013 P->setNodeId(Degree);
6016 if (I == SortedPos) {
6019 dbgs() << "Overran sorted position:\n";
6022 llvm_unreachable(nullptr);
6026 assert(SortedPos == AllNodes.end() &&
6027 "Topological sort incomplete!");
6028 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6029 "First node in topological sort is not the entry token!");
6030 assert(AllNodes.front().getNodeId() == 0 &&
6031 "First node in topological sort has non-zero id!");
6032 assert(AllNodes.front().getNumOperands() == 0 &&
6033 "First node in topological sort has operands!");
6034 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6035 "Last node in topologic sort has unexpected id!");
6036 assert(AllNodes.back().use_empty() &&
6037 "Last node in topologic sort has users!");
6038 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6042 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6043 /// value is produced by SD.
6044 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6045 DbgInfo->add(DB, SD, isParameter);
6047 SD->setHasDebugValue(true);
6050 /// TransferDbgValues - Transfer SDDbgValues.
6051 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6052 if (From == To || !From.getNode()->getHasDebugValue())
6054 SDNode *FromNode = From.getNode();
6055 SDNode *ToNode = To.getNode();
6056 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6057 SmallVector<SDDbgValue *, 2> ClonedDVs;
6058 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6060 SDDbgValue *Dbg = *I;
6061 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6062 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6064 Dbg->getOffset(), Dbg->getDebugLoc(),
6066 ClonedDVs.push_back(Clone);
6069 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6070 E = ClonedDVs.end(); I != E; ++I)
6071 AddDbgValue(*I, ToNode, false);
6074 //===----------------------------------------------------------------------===//
6076 //===----------------------------------------------------------------------===//
6078 HandleSDNode::~HandleSDNode() {
6082 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6083 DebugLoc DL, const GlobalValue *GA,
6084 EVT VT, int64_t o, unsigned char TF)
6085 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6089 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6090 SDValue X, unsigned SrcAS,
6092 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6093 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6095 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6096 EVT memvt, MachineMemOperand *mmo)
6097 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6098 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6099 MMO->isNonTemporal(), MMO->isInvariant());
6100 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6101 assert(isNonTemporal() == MMO->isNonTemporal() &&
6102 "Non-temporal encoding error!");
6103 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6106 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6107 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6108 : SDNode(Opc, Order, dl, VTs, Ops),
6109 MemoryVT(memvt), MMO(mmo) {
6110 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6111 MMO->isNonTemporal(), MMO->isInvariant());
6112 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6113 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6116 /// Profile - Gather unique data for the node.
6118 void SDNode::Profile(FoldingSetNodeID &ID) const {
6119 AddNodeIDNode(ID, this);
6124 std::vector<EVT> VTs;
6127 VTs.reserve(MVT::LAST_VALUETYPE);
6128 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6129 VTs.push_back(MVT((MVT::SimpleValueType)i));
6134 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6135 static ManagedStatic<EVTArray> SimpleVTArray;
6136 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6138 /// getValueTypeList - Return a pointer to the specified value type.
6140 const EVT *SDNode::getValueTypeList(EVT VT) {
6141 if (VT.isExtended()) {
6142 sys::SmartScopedLock<true> Lock(*VTMutex);
6143 return &(*EVTs->insert(VT).first);
6145 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6146 "Value type out of range!");
6147 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6151 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6152 /// indicated value. This method ignores uses of other values defined by this
6154 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6155 assert(Value < getNumValues() && "Bad value!");
6157 // TODO: Only iterate over uses of a given value of the node
6158 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6159 if (UI.getUse().getResNo() == Value) {
6166 // Found exactly the right number of uses?
6171 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6172 /// value. This method ignores uses of other values defined by this operation.
6173 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6174 assert(Value < getNumValues() && "Bad value!");
6176 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6177 if (UI.getUse().getResNo() == Value)
6184 /// isOnlyUserOf - Return true if this node is the only use of N.
6186 bool SDNode::isOnlyUserOf(SDNode *N) const {
6188 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6199 /// isOperand - Return true if this node is an operand of N.
6201 bool SDValue::isOperandOf(SDNode *N) const {
6202 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6203 if (*this == N->getOperand(i))
6208 bool SDNode::isOperandOf(SDNode *N) const {
6209 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6210 if (this == N->OperandList[i].getNode())
6215 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6216 /// be a chain) reaches the specified operand without crossing any
6217 /// side-effecting instructions on any chain path. In practice, this looks
6218 /// through token factors and non-volatile loads. In order to remain efficient,
6219 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6220 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6221 unsigned Depth) const {
6222 if (*this == Dest) return true;
6224 // Don't search too deeply, we just want to be able to see through
6225 // TokenFactor's etc.
6226 if (Depth == 0) return false;
6228 // If this is a token factor, all inputs to the TF happen in parallel. If any
6229 // of the operands of the TF does not reach dest, then we cannot do the xform.
6230 if (getOpcode() == ISD::TokenFactor) {
6231 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6232 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6237 // Loads don't have side effects, look through them.
6238 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6239 if (!Ld->isVolatile())
6240 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6245 /// hasPredecessor - Return true if N is a predecessor of this node.
6246 /// N is either an operand of this node, or can be reached by recursively
6247 /// traversing up the operands.
6248 /// NOTE: This is an expensive method. Use it carefully.
6249 bool SDNode::hasPredecessor(const SDNode *N) const {
6250 SmallPtrSet<const SDNode *, 32> Visited;
6251 SmallVector<const SDNode *, 16> Worklist;
6252 return hasPredecessorHelper(N, Visited, Worklist);
6256 SDNode::hasPredecessorHelper(const SDNode *N,
6257 SmallPtrSet<const SDNode *, 32> &Visited,
6258 SmallVectorImpl<const SDNode *> &Worklist) const {
6259 if (Visited.empty()) {
6260 Worklist.push_back(this);
6262 // Take a look in the visited set. If we've already encountered this node
6263 // we needn't search further.
6264 if (Visited.count(N))
6268 // Haven't visited N yet. Continue the search.
6269 while (!Worklist.empty()) {
6270 const SDNode *M = Worklist.pop_back_val();
6271 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6272 SDNode *Op = M->getOperand(i).getNode();
6273 if (Visited.insert(Op))
6274 Worklist.push_back(Op);
6283 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6284 assert(Num < NumOperands && "Invalid child # of SDNode!");
6285 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6288 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6289 assert(N->getNumValues() == 1 &&
6290 "Can't unroll a vector with multiple results!");
6292 EVT VT = N->getValueType(0);
6293 unsigned NE = VT.getVectorNumElements();
6294 EVT EltVT = VT.getVectorElementType();
6297 SmallVector<SDValue, 8> Scalars;
6298 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6300 // If ResNE is 0, fully unroll the vector op.
6303 else if (NE > ResNE)
6307 for (i= 0; i != NE; ++i) {
6308 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6309 SDValue Operand = N->getOperand(j);
6310 EVT OperandVT = Operand.getValueType();
6311 if (OperandVT.isVector()) {
6312 // A vector operand; extract a single element.
6313 const TargetLowering *TLI = TM.getTargetLowering();
6314 EVT OperandEltVT = OperandVT.getVectorElementType();
6315 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6318 getConstant(i, TLI->getVectorIdxTy()));
6320 // A scalar operand; just use it as is.
6321 Operands[j] = Operand;
6325 switch (N->getOpcode()) {
6327 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6330 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6337 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6338 getShiftAmountOperand(Operands[0].getValueType(),
6341 case ISD::SIGN_EXTEND_INREG:
6342 case ISD::FP_ROUND_INREG: {
6343 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6344 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6346 getValueType(ExtVT)));
6351 for (; i < ResNE; ++i)
6352 Scalars.push_back(getUNDEF(EltVT));
6354 return getNode(ISD::BUILD_VECTOR, dl,
6355 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6359 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6360 /// location that is 'Dist' units away from the location that the 'Base' load
6361 /// is loading from.
6362 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6363 unsigned Bytes, int Dist) const {
6364 if (LD->getChain() != Base->getChain())
6366 EVT VT = LD->getValueType(0);
6367 if (VT.getSizeInBits() / 8 != Bytes)
6370 SDValue Loc = LD->getOperand(1);
6371 SDValue BaseLoc = Base->getOperand(1);
6372 if (Loc.getOpcode() == ISD::FrameIndex) {
6373 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6375 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6376 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6377 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6378 int FS = MFI->getObjectSize(FI);
6379 int BFS = MFI->getObjectSize(BFI);
6380 if (FS != BFS || FS != (int)Bytes) return false;
6381 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6385 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6386 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6389 const GlobalValue *GV1 = nullptr;
6390 const GlobalValue *GV2 = nullptr;
6391 int64_t Offset1 = 0;
6392 int64_t Offset2 = 0;
6393 const TargetLowering *TLI = TM.getTargetLowering();
6394 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6395 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6396 if (isGA1 && isGA2 && GV1 == GV2)
6397 return Offset1 == (Offset2 + Dist*Bytes);
6402 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6403 /// it cannot be inferred.
6404 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6405 // If this is a GlobalAddress + cst, return the alignment.
6406 const GlobalValue *GV;
6407 int64_t GVOffset = 0;
6408 const TargetLowering *TLI = TM.getTargetLowering();
6409 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6410 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6411 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6412 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6413 TLI->getDataLayout());
6414 unsigned AlignBits = KnownZero.countTrailingOnes();
6415 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6417 return MinAlign(Align, GVOffset);
6420 // If this is a direct reference to a stack slot, use information about the
6421 // stack slot's alignment.
6422 int FrameIdx = 1 << 31;
6423 int64_t FrameOffset = 0;
6424 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6425 FrameIdx = FI->getIndex();
6426 } else if (isBaseWithConstantOffset(Ptr) &&
6427 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6429 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6430 FrameOffset = Ptr.getConstantOperandVal(1);
6433 if (FrameIdx != (1 << 31)) {
6434 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6435 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6443 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6444 /// which is split (or expanded) into two not necessarily identical pieces.
6445 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6446 // Currently all types are split in half.
6448 if (!VT.isVector()) {
6449 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6451 unsigned NumElements = VT.getVectorNumElements();
6452 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6453 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6456 return std::make_pair(LoVT, HiVT);
6459 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6461 std::pair<SDValue, SDValue>
6462 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6464 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6465 N.getValueType().getVectorNumElements() &&
6466 "More vector elements requested than available!");
6468 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6469 getConstant(0, TLI->getVectorIdxTy()));
6470 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6471 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6472 return std::make_pair(Lo, Hi);
6475 void SelectionDAG::ExtractVectorElements(SDValue Op,
6476 SmallVectorImpl<SDValue> &Args,
6477 unsigned Start, unsigned Count) {
6478 EVT VT = Op.getValueType();
6480 Count = VT.getVectorNumElements();
6482 EVT EltVT = VT.getVectorElementType();
6483 EVT IdxTy = TLI->getVectorIdxTy();
6485 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6486 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6487 Op, getConstant(i, IdxTy)));
6491 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6492 unsigned GlobalAddressSDNode::getAddressSpace() const {
6493 return getGlobal()->getType()->getAddressSpace();
6497 Type *ConstantPoolSDNode::getType() const {
6498 if (isMachineConstantPoolEntry())
6499 return Val.MachineCPVal->getType();
6500 return Val.ConstVal->getType();
6503 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6505 unsigned &SplatBitSize,
6507 unsigned MinSplatBits,
6508 bool isBigEndian) const {
6509 EVT VT = getValueType(0);
6510 assert(VT.isVector() && "Expected a vector type");
6511 unsigned sz = VT.getSizeInBits();
6512 if (MinSplatBits > sz)
6515 SplatValue = APInt(sz, 0);
6516 SplatUndef = APInt(sz, 0);
6518 // Get the bits. Bits with undefined values (when the corresponding element
6519 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6520 // in SplatValue. If any of the values are not constant, give up and return
6522 unsigned int nOps = getNumOperands();
6523 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6524 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6526 for (unsigned j = 0; j < nOps; ++j) {
6527 unsigned i = isBigEndian ? nOps-1-j : j;
6528 SDValue OpVal = getOperand(i);
6529 unsigned BitPos = j * EltBitSize;
6531 if (OpVal.getOpcode() == ISD::UNDEF)
6532 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6533 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6534 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6535 zextOrTrunc(sz) << BitPos;
6536 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6537 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6542 // The build_vector is all constants or undefs. Find the smallest element
6543 // size that splats the vector.
6545 HasAnyUndefs = (SplatUndef != 0);
6548 unsigned HalfSize = sz / 2;
6549 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6550 APInt LowValue = SplatValue.trunc(HalfSize);
6551 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6552 APInt LowUndef = SplatUndef.trunc(HalfSize);
6554 // If the two halves do not match (ignoring undef bits), stop here.
6555 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6556 MinSplatBits > HalfSize)
6559 SplatValue = HighValue | LowValue;
6560 SplatUndef = HighUndef & LowUndef;
6569 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6570 SDValue Op0 = getOperand(0);
6571 if (Op0.getOpcode() != ISD::Constant)
6574 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6575 if (getOperand(i) != Op0)
6578 return cast<ConstantSDNode>(Op0);
6581 bool BuildVectorSDNode::isConstant() const {
6582 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6583 unsigned Opc = getOperand(i).getOpcode();
6584 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6590 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6591 // Find the first non-undef value in the shuffle mask.
6593 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6596 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6598 // Make sure all remaining elements are either undef or the same as the first
6600 for (int Idx = Mask[i]; i != e; ++i)
6601 if (Mask[i] >= 0 && Mask[i] != Idx)
6607 static void checkForCyclesHelper(const SDNode *N,
6608 SmallPtrSet<const SDNode*, 32> &Visited,
6609 SmallPtrSet<const SDNode*, 32> &Checked) {
6610 // If this node has already been checked, don't check it again.
6611 if (Checked.count(N))
6614 // If a node has already been visited on this depth-first walk, reject it as
6616 if (!Visited.insert(N)) {
6617 dbgs() << "Offending node:\n";
6619 errs() << "Detected cycle in SelectionDAG\n";
6623 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6624 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6631 void llvm::checkForCycles(const llvm::SDNode *N) {
6633 assert(N && "Checking nonexistent SDNode");
6634 SmallPtrSet<const SDNode*, 32> visited;
6635 SmallPtrSet<const SDNode*, 32> checked;
6636 checkForCyclesHelper(N, visited, checked);
6640 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6641 checkForCycles(DAG->getRoot().getNode());