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"
54 /// makeVTList - Return an instance of the SDVTList struct initialized with the
55 /// specified members.
56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
57 SDVTList Res = {VTs, NumVTs};
61 // Default null implementations of the callbacks.
62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
65 //===----------------------------------------------------------------------===//
66 // ConstantFPSDNode Class
67 //===----------------------------------------------------------------------===//
69 /// isExactlyValue - We don't rely on operator== working on double values, as
70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
71 /// As such, this method can be used to do an exact bit-for-bit comparison of
72 /// two floating point values.
73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
74 return getValueAPF().bitwiseIsEqual(V);
77 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 assert(VT.isFloatingPoint() && "Can only convert between FP types");
81 // convert modifies in place, so make a copy.
82 APFloat Val2 = APFloat(Val);
84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
85 APFloat::rmNearestTiesToEven,
90 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
94 /// isBuildVectorAllOnes - Return true if the specified node is a
95 /// BUILD_VECTOR where all of the elements are ~0 or undef.
96 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
97 // Look through a bit convert.
98 if (N->getOpcode() == ISD::BITCAST)
99 N = N->getOperand(0).getNode();
101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
103 unsigned i = 0, e = N->getNumOperands();
105 // Skip over all of the undef values.
106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109 // Do not accept an all-undef vector.
110 if (i == e) return false;
112 // Do not accept build_vectors that aren't all constants or which have non-~0
113 // elements. We have to be a bit careful here, as the type of the constant
114 // may not be the same as the type of the vector elements due to type
115 // legalization (the elements are promoted to a legal type for the target and
116 // a vector of a type may be legal when the base element type is not).
117 // We only want to check enough bits to cover the vector elements, because
118 // we care if the resultant vector is all ones, not whether the individual
120 SDValue NotZero = N->getOperand(i);
121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
123 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
131 // Okay, we have at least one ~0 value, check to see if the rest match or are
132 // undefs. Even with the above element type twiddling, this should be OK, as
133 // the same type legalization should have applied to all the elements.
134 for (++i; i != e; ++i)
135 if (N->getOperand(i) != NotZero &&
136 N->getOperand(i).getOpcode() != ISD::UNDEF)
142 /// isBuildVectorAllZeros - Return true if the specified node is a
143 /// BUILD_VECTOR where all of the elements are 0 or undef.
144 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
145 // Look through a bit convert.
146 if (N->getOpcode() == ISD::BITCAST)
147 N = N->getOperand(0).getNode();
149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
151 unsigned i = 0, e = N->getNumOperands();
153 // Skip over all of the undef values.
154 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept an all-undef vector.
158 if (i == e) return false;
160 // Do not accept build_vectors that aren't all constants or which have non-0
162 SDValue Zero = N->getOperand(i);
163 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
164 if (!CN->isNullValue())
166 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
167 if (!CFPN->getValueAPF().isPosZero())
172 // Okay, we have at least one 0 value, check to see if the rest match or are
174 for (++i; i != e; ++i)
175 if (N->getOperand(i) != Zero &&
176 N->getOperand(i).getOpcode() != ISD::UNDEF)
181 /// \brief Return true if the specified node is a BUILD_VECTOR node of
182 /// all ConstantSDNode or undef.
183 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
184 if (N->getOpcode() != ISD::BUILD_VECTOR)
187 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
188 SDValue Op = N->getOperand(i);
189 if (Op.getOpcode() == ISD::UNDEF)
191 if (!isa<ConstantSDNode>(Op))
197 /// isScalarToVector - Return true if the specified node is a
198 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
199 /// element is not an undef.
200 bool ISD::isScalarToVector(const SDNode *N) {
201 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
204 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
208 unsigned NumElems = N->getNumOperands();
211 for (unsigned i = 1; i < NumElems; ++i) {
212 SDValue V = N->getOperand(i);
213 if (V.getOpcode() != ISD::UNDEF)
219 /// allOperandsUndef - Return true if the node has at least one operand
220 /// and all operands of the specified node are ISD::UNDEF.
221 bool ISD::allOperandsUndef(const SDNode *N) {
222 // Return false if the node has no operands.
223 // This is "logically inconsistent" with the definition of "all" but
224 // is probably the desired behavior.
225 if (N->getNumOperands() == 0)
228 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
229 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
235 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
238 return ISD::ANY_EXTEND;
240 return ISD::SIGN_EXTEND;
242 return ISD::ZERO_EXTEND;
247 llvm_unreachable("Invalid LoadExtType");
250 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
251 /// when given the operation for (X op Y).
252 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
253 // To perform this operation, we just need to swap the L and G bits of the
255 unsigned OldL = (Operation >> 2) & 1;
256 unsigned OldG = (Operation >> 1) & 1;
257 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
258 (OldL << 1) | // New G bit
259 (OldG << 2)); // New L bit.
262 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
263 /// 'op' is a valid SetCC operation.
264 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
265 unsigned Operation = Op;
267 Operation ^= 7; // Flip L, G, E bits, but not U.
269 Operation ^= 15; // Flip all of the condition bits.
271 if (Operation > ISD::SETTRUE2)
272 Operation &= ~8; // Don't let N and U bits get set.
274 return ISD::CondCode(Operation);
278 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
279 /// signed operation and 2 if the result is an unsigned comparison. Return zero
280 /// if the operation does not depend on the sign of the input (setne and seteq).
281 static int isSignedOp(ISD::CondCode Opcode) {
283 default: llvm_unreachable("Illegal integer setcc operation!");
285 case ISD::SETNE: return 0;
289 case ISD::SETGE: return 1;
293 case ISD::SETUGE: return 2;
297 /// getSetCCOrOperation - Return the result of a logical OR between different
298 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
299 /// returns SETCC_INVALID if it is not possible to represent the resultant
301 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
303 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
304 // Cannot fold a signed integer setcc with an unsigned integer setcc.
305 return ISD::SETCC_INVALID;
307 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
309 // If the N and U bits get set then the resultant comparison DOES suddenly
310 // care about orderedness, and is true when ordered.
311 if (Op > ISD::SETTRUE2)
312 Op &= ~16; // Clear the U bit if the N bit is set.
314 // Canonicalize illegal integer setcc's.
315 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
318 return ISD::CondCode(Op);
321 /// getSetCCAndOperation - Return the result of a logical AND between different
322 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
323 /// function returns zero if it is not possible to represent the resultant
325 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
327 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
328 // Cannot fold a signed setcc with an unsigned setcc.
329 return ISD::SETCC_INVALID;
331 // Combine all of the condition bits.
332 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
334 // Canonicalize illegal integer setcc's.
338 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
339 case ISD::SETOEQ: // SETEQ & SETU[LG]E
340 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
341 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
342 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
349 //===----------------------------------------------------------------------===//
350 // SDNode Profile Support
351 //===----------------------------------------------------------------------===//
353 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
355 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
359 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
360 /// solely with their pointer.
361 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
362 ID.AddPointer(VTList.VTs);
365 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
367 static void AddNodeIDOperands(FoldingSetNodeID &ID,
368 ArrayRef<SDValue> Ops) {
369 for (auto& Op : Ops) {
370 ID.AddPointer(Op.getNode());
371 ID.AddInteger(Op.getResNo());
375 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
377 static void AddNodeIDOperands(FoldingSetNodeID &ID,
378 ArrayRef<SDUse> Ops) {
379 for (auto& Op : Ops) {
380 ID.AddPointer(Op.getNode());
381 ID.AddInteger(Op.getResNo());
385 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
389 ID.AddBoolean(exact);
392 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
393 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
394 bool nuw, bool nsw, bool exact) {
395 if (isBinOpWithFlags(Opcode))
396 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
399 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
400 SDVTList VTList, ArrayRef<SDValue> OpList) {
401 AddNodeIDOpcode(ID, OpC);
402 AddNodeIDValueTypes(ID, VTList);
403 AddNodeIDOperands(ID, OpList);
406 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
408 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
409 switch (N->getOpcode()) {
410 case ISD::TargetExternalSymbol:
411 case ISD::ExternalSymbol:
412 llvm_unreachable("Should only be used on nodes with operands");
413 default: break; // Normal nodes don't need extra info.
414 case ISD::TargetConstant:
415 case ISD::Constant: {
416 const ConstantSDNode *C = cast<ConstantSDNode>(N);
417 ID.AddPointer(C->getConstantIntValue());
418 ID.AddBoolean(C->isOpaque());
421 case ISD::TargetConstantFP:
422 case ISD::ConstantFP: {
423 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
426 case ISD::TargetGlobalAddress:
427 case ISD::GlobalAddress:
428 case ISD::TargetGlobalTLSAddress:
429 case ISD::GlobalTLSAddress: {
430 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
431 ID.AddPointer(GA->getGlobal());
432 ID.AddInteger(GA->getOffset());
433 ID.AddInteger(GA->getTargetFlags());
434 ID.AddInteger(GA->getAddressSpace());
437 case ISD::BasicBlock:
438 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
441 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
443 case ISD::RegisterMask:
444 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
447 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
449 case ISD::FrameIndex:
450 case ISD::TargetFrameIndex:
451 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
454 case ISD::TargetJumpTable:
455 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
456 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
458 case ISD::ConstantPool:
459 case ISD::TargetConstantPool: {
460 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
461 ID.AddInteger(CP->getAlignment());
462 ID.AddInteger(CP->getOffset());
463 if (CP->isMachineConstantPoolEntry())
464 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
466 ID.AddPointer(CP->getConstVal());
467 ID.AddInteger(CP->getTargetFlags());
470 case ISD::TargetIndex: {
471 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
472 ID.AddInteger(TI->getIndex());
473 ID.AddInteger(TI->getOffset());
474 ID.AddInteger(TI->getTargetFlags());
478 const LoadSDNode *LD = cast<LoadSDNode>(N);
479 ID.AddInteger(LD->getMemoryVT().getRawBits());
480 ID.AddInteger(LD->getRawSubclassData());
481 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
485 const StoreSDNode *ST = cast<StoreSDNode>(N);
486 ID.AddInteger(ST->getMemoryVT().getRawBits());
487 ID.AddInteger(ST->getRawSubclassData());
488 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
499 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
500 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
501 BinNode->hasNoSignedWrap(), BinNode->isExact());
504 case ISD::ATOMIC_CMP_SWAP:
505 case ISD::ATOMIC_SWAP:
506 case ISD::ATOMIC_LOAD_ADD:
507 case ISD::ATOMIC_LOAD_SUB:
508 case ISD::ATOMIC_LOAD_AND:
509 case ISD::ATOMIC_LOAD_OR:
510 case ISD::ATOMIC_LOAD_XOR:
511 case ISD::ATOMIC_LOAD_NAND:
512 case ISD::ATOMIC_LOAD_MIN:
513 case ISD::ATOMIC_LOAD_MAX:
514 case ISD::ATOMIC_LOAD_UMIN:
515 case ISD::ATOMIC_LOAD_UMAX:
516 case ISD::ATOMIC_LOAD:
517 case ISD::ATOMIC_STORE: {
518 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
519 ID.AddInteger(AT->getMemoryVT().getRawBits());
520 ID.AddInteger(AT->getRawSubclassData());
521 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
524 case ISD::PREFETCH: {
525 const MemSDNode *PF = cast<MemSDNode>(N);
526 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
529 case ISD::VECTOR_SHUFFLE: {
530 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
531 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
533 ID.AddInteger(SVN->getMaskElt(i));
536 case ISD::TargetBlockAddress:
537 case ISD::BlockAddress: {
538 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
539 ID.AddPointer(BA->getBlockAddress());
540 ID.AddInteger(BA->getOffset());
541 ID.AddInteger(BA->getTargetFlags());
544 } // end switch (N->getOpcode())
546 // Target specific memory nodes could also have address spaces to check.
547 if (N->isTargetMemoryOpcode())
548 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
551 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
553 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
554 AddNodeIDOpcode(ID, N->getOpcode());
555 // Add the return value info.
556 AddNodeIDValueTypes(ID, N->getVTList());
557 // Add the operand info.
558 AddNodeIDOperands(ID, makeArrayRef(N->op_begin(), N->op_end()));
560 // Handle SDNode leafs with special info.
561 AddNodeIDCustom(ID, N);
564 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
565 /// the CSE map that carries volatility, temporalness, indexing mode, and
566 /// extension/truncation information.
568 static inline unsigned
569 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
570 bool isNonTemporal, bool isInvariant) {
571 assert((ConvType & 3) == ConvType &&
572 "ConvType may not require more than 2 bits!");
573 assert((AM & 7) == AM &&
574 "AM may not require more than 3 bits!");
578 (isNonTemporal << 6) |
582 //===----------------------------------------------------------------------===//
583 // SelectionDAG Class
584 //===----------------------------------------------------------------------===//
586 /// doNotCSE - Return true if CSE should not be performed for this node.
587 static bool doNotCSE(SDNode *N) {
588 if (N->getValueType(0) == MVT::Glue)
589 return true; // Never CSE anything that produces a flag.
591 switch (N->getOpcode()) {
593 case ISD::HANDLENODE:
595 return true; // Never CSE these nodes.
598 // Check that remaining values produced are not flags.
599 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
600 if (N->getValueType(i) == MVT::Glue)
601 return true; // Never CSE anything that produces a flag.
606 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
608 void SelectionDAG::RemoveDeadNodes() {
609 // Create a dummy node (which is not added to allnodes), that adds a reference
610 // to the root node, preventing it from being deleted.
611 HandleSDNode Dummy(getRoot());
613 SmallVector<SDNode*, 128> DeadNodes;
615 // Add all obviously-dead nodes to the DeadNodes worklist.
616 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
618 DeadNodes.push_back(I);
620 RemoveDeadNodes(DeadNodes);
622 // If the root changed (e.g. it was a dead load, update the root).
623 setRoot(Dummy.getValue());
626 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
627 /// given list, and any nodes that become unreachable as a result.
628 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
630 // Process the worklist, deleting the nodes and adding their uses to the
632 while (!DeadNodes.empty()) {
633 SDNode *N = DeadNodes.pop_back_val();
635 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
636 DUL->NodeDeleted(N, nullptr);
638 // Take the node out of the appropriate CSE map.
639 RemoveNodeFromCSEMaps(N);
641 // Next, brutally remove the operand list. This is safe to do, as there are
642 // no cycles in the graph.
643 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
645 SDNode *Operand = Use.getNode();
648 // Now that we removed this operand, see if there are no uses of it left.
649 if (Operand->use_empty())
650 DeadNodes.push_back(Operand);
657 void SelectionDAG::RemoveDeadNode(SDNode *N){
658 SmallVector<SDNode*, 16> DeadNodes(1, N);
660 // Create a dummy node that adds a reference to the root node, preventing
661 // it from being deleted. (This matters if the root is an operand of the
663 HandleSDNode Dummy(getRoot());
665 RemoveDeadNodes(DeadNodes);
668 void SelectionDAG::DeleteNode(SDNode *N) {
669 // First take this out of the appropriate CSE map.
670 RemoveNodeFromCSEMaps(N);
672 // Finally, remove uses due to operands of this node, remove from the
673 // AllNodes list, and delete the node.
674 DeleteNodeNotInCSEMaps(N);
677 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
678 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
679 assert(N->use_empty() && "Cannot delete a node that is not dead!");
681 // Drop all of the operands and decrement used node's use counts.
687 void SelectionDAG::DeallocateNode(SDNode *N) {
688 if (N->OperandsNeedDelete)
689 delete[] N->OperandList;
691 // Set the opcode to DELETED_NODE to help catch bugs when node
692 // memory is reallocated.
693 N->NodeType = ISD::DELETED_NODE;
695 NodeAllocator.Deallocate(AllNodes.remove(N));
697 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
698 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
699 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
700 DbgVals[i]->setIsInvalidated();
703 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
704 /// correspond to it. This is useful when we're about to delete or repurpose
705 /// the node. We don't want future request for structurally identical nodes
706 /// to return N anymore.
707 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
709 switch (N->getOpcode()) {
710 case ISD::HANDLENODE: return false; // noop.
712 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
713 "Cond code doesn't exist!");
714 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
715 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
717 case ISD::ExternalSymbol:
718 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
720 case ISD::TargetExternalSymbol: {
721 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
722 Erased = TargetExternalSymbols.erase(
723 std::pair<std::string,unsigned char>(ESN->getSymbol(),
724 ESN->getTargetFlags()));
727 case ISD::VALUETYPE: {
728 EVT VT = cast<VTSDNode>(N)->getVT();
729 if (VT.isExtended()) {
730 Erased = ExtendedValueTypeNodes.erase(VT);
732 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
733 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
738 // Remove it from the CSE Map.
739 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
740 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
741 Erased = CSEMap.RemoveNode(N);
745 // Verify that the node was actually in one of the CSE maps, unless it has a
746 // flag result (which cannot be CSE'd) or is one of the special cases that are
747 // not subject to CSE.
748 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
749 !N->isMachineOpcode() && !doNotCSE(N)) {
752 llvm_unreachable("Node is not in map!");
758 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
759 /// maps and modified in place. Add it back to the CSE maps, unless an identical
760 /// node already exists, in which case transfer all its users to the existing
761 /// node. This transfer can potentially trigger recursive merging.
764 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
765 // For node types that aren't CSE'd, just act as if no identical node
768 SDNode *Existing = CSEMap.GetOrInsertNode(N);
770 // If there was already an existing matching node, use ReplaceAllUsesWith
771 // to replace the dead one with the existing one. This can cause
772 // recursive merging of other unrelated nodes down the line.
773 ReplaceAllUsesWith(N, Existing);
775 // N is now dead. Inform the listeners and delete it.
776 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
777 DUL->NodeDeleted(N, Existing);
778 DeleteNodeNotInCSEMaps(N);
783 // If the node doesn't already exist, we updated it. Inform listeners.
784 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
788 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
789 /// were replaced with those specified. If this node is never memoized,
790 /// return null, otherwise return a pointer to the slot it would take. If a
791 /// node already exists with these operands, the slot will be non-null.
792 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
797 SDValue Ops[] = { Op };
799 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
800 AddNodeIDCustom(ID, N);
801 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
805 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
806 /// were replaced with those specified. If this node is never memoized,
807 /// return null, otherwise return a pointer to the slot it would take. If a
808 /// node already exists with these operands, the slot will be non-null.
809 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
810 SDValue Op1, SDValue Op2,
815 SDValue Ops[] = { Op1, Op2 };
817 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
818 AddNodeIDCustom(ID, N);
819 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
824 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
825 /// were replaced with those specified. If this node is never memoized,
826 /// return null, otherwise return a pointer to the slot it would take. If a
827 /// node already exists with these operands, the slot will be non-null.
828 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
834 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
835 AddNodeIDCustom(ID, N);
836 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
841 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
842 static void VerifyNodeCommon(SDNode *N) {
843 switch (N->getOpcode()) {
846 case ISD::BUILD_PAIR: {
847 EVT VT = N->getValueType(0);
848 assert(N->getNumValues() == 1 && "Too many results!");
849 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
850 "Wrong return type!");
851 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
852 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
853 "Mismatched operand types!");
854 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
855 "Wrong operand type!");
856 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
857 "Wrong return type size");
860 case ISD::BUILD_VECTOR: {
861 assert(N->getNumValues() == 1 && "Too many results!");
862 assert(N->getValueType(0).isVector() && "Wrong return type!");
863 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
864 "Wrong number of operands!");
865 EVT EltVT = N->getValueType(0).getVectorElementType();
866 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
867 assert((I->getValueType() == EltVT ||
868 (EltVT.isInteger() && I->getValueType().isInteger() &&
869 EltVT.bitsLE(I->getValueType()))) &&
870 "Wrong operand type!");
871 assert(I->getValueType() == N->getOperand(0).getValueType() &&
872 "Operands must all have the same type");
879 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
880 static void VerifySDNode(SDNode *N) {
881 // The SDNode allocators cannot be used to allocate nodes with fields that are
882 // not present in an SDNode!
883 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
884 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
885 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
886 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
887 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
888 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
889 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
890 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
891 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
892 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
893 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
894 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
895 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
896 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
897 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
898 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
899 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
900 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
901 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
906 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
908 static void VerifyMachineNode(SDNode *N) {
909 // The MachineNode allocators cannot be used to allocate nodes with fields
910 // that are not present in a MachineNode!
911 // Currently there are no such nodes.
917 /// getEVTAlignment - Compute the default alignment value for the
920 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
921 Type *Ty = VT == MVT::iPTR ?
922 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
923 VT.getTypeForEVT(*getContext());
925 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
928 // EntryNode could meaningfully have debug info if we can find it...
929 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
930 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
931 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
932 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
933 UpdateListeners(nullptr) {
934 AllNodes.push_back(&EntryNode);
935 DbgInfo = new SDDbgInfo();
938 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
941 Context = &mf.getFunction()->getContext();
944 SelectionDAG::~SelectionDAG() {
945 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
950 void SelectionDAG::allnodes_clear() {
951 assert(&*AllNodes.begin() == &EntryNode);
952 AllNodes.remove(AllNodes.begin());
953 while (!AllNodes.empty())
954 DeallocateNode(AllNodes.begin());
957 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
958 SDVTList VTs, SDValue N1,
959 SDValue N2, bool nuw, bool nsw,
961 if (isBinOpWithFlags(Opcode)) {
962 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
963 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
964 FN->setHasNoUnsignedWrap(nuw);
965 FN->setHasNoSignedWrap(nsw);
966 FN->setIsExact(exact);
971 BinarySDNode *N = new (NodeAllocator)
972 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
976 void SelectionDAG::clear() {
978 OperandAllocator.Reset();
981 ExtendedValueTypeNodes.clear();
982 ExternalSymbols.clear();
983 TargetExternalSymbols.clear();
984 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
985 static_cast<CondCodeSDNode*>(nullptr));
986 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
987 static_cast<SDNode*>(nullptr));
989 EntryNode.UseList = nullptr;
990 AllNodes.push_back(&EntryNode);
991 Root = getEntryNode();
995 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
996 return VT.bitsGT(Op.getValueType()) ?
997 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
998 getNode(ISD::TRUNCATE, DL, VT, Op);
1001 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1002 return VT.bitsGT(Op.getValueType()) ?
1003 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1004 getNode(ISD::TRUNCATE, DL, VT, Op);
1007 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1008 return VT.bitsGT(Op.getValueType()) ?
1009 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1010 getNode(ISD::TRUNCATE, DL, VT, Op);
1013 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
1014 if (VT.bitsLE(Op.getValueType()))
1015 return getNode(ISD::TRUNCATE, SL, VT, Op);
1017 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
1018 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1021 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1022 assert(!VT.isVector() &&
1023 "getZeroExtendInReg should use the vector element type instead of "
1024 "the vector type!");
1025 if (Op.getValueType() == VT) return Op;
1026 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1027 APInt Imm = APInt::getLowBitsSet(BitWidth,
1028 VT.getSizeInBits());
1029 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1030 getConstant(Imm, Op.getValueType()));
1033 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1035 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1036 EVT EltVT = VT.getScalarType();
1038 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1039 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1042 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1043 EVT EltVT = VT.getScalarType();
1045 switch (TLI->getBooleanContents(VT.isVector())) {
1046 case TargetLowering::ZeroOrOneBooleanContent:
1047 case TargetLowering::UndefinedBooleanContent:
1048 TrueValue = getConstant(1, VT);
1050 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1051 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1055 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1058 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1059 EVT EltVT = VT.getScalarType();
1060 assert((EltVT.getSizeInBits() >= 64 ||
1061 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1062 "getConstant with a uint64_t value that doesn't fit in the type!");
1063 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1066 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1068 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1071 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1073 assert(VT.isInteger() && "Cannot create FP integer constant!");
1075 EVT EltVT = VT.getScalarType();
1076 const ConstantInt *Elt = &Val;
1078 const TargetLowering *TLI = TM.getTargetLowering();
1080 // In some cases the vector type is legal but the element type is illegal and
1081 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1082 // inserted value (the type does not need to match the vector element type).
1083 // Any extra bits introduced will be truncated away.
1084 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1085 TargetLowering::TypePromoteInteger) {
1086 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1087 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1088 Elt = ConstantInt::get(*getContext(), NewVal);
1090 // In other cases the element type is illegal and needs to be expanded, for
1091 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1092 // the value into n parts and use a vector type with n-times the elements.
1093 // Then bitcast to the type requested.
1094 // Legalizing constants too early makes the DAGCombiner's job harder so we
1095 // only legalize if the DAG tells us we must produce legal types.
1096 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1097 TLI->getTypeAction(*getContext(), EltVT) ==
1098 TargetLowering::TypeExpandInteger) {
1099 APInt NewVal = Elt->getValue();
1100 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1101 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1102 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1103 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1105 // Check the temporary vector is the correct size. If this fails then
1106 // getTypeToTransformTo() probably returned a type whose size (in bits)
1107 // isn't a power-of-2 factor of the requested type size.
1108 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1110 SmallVector<SDValue, 2> EltParts;
1111 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1112 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1113 .trunc(ViaEltSizeInBits),
1114 ViaEltVT, isT, isO));
1117 // EltParts is currently in little endian order. If we actually want
1118 // big-endian order then reverse it now.
1119 if (TLI->isBigEndian())
1120 std::reverse(EltParts.begin(), EltParts.end());
1122 // The elements must be reversed when the element order is different
1123 // to the endianness of the elements (because the BITCAST is itself a
1124 // vector shuffle in this situation). However, we do not need any code to
1125 // perform this reversal because getConstant() is producing a vector
1127 // This situation occurs in MIPS MSA.
1129 SmallVector<SDValue, 8> Ops;
1130 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1131 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1133 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1134 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1139 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1140 "APInt size does not match type size!");
1141 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1142 FoldingSetNodeID ID;
1143 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1147 SDNode *N = nullptr;
1148 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1150 return SDValue(N, 0);
1153 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1154 CSEMap.InsertNode(N, IP);
1155 AllNodes.push_back(N);
1158 SDValue Result(N, 0);
1159 if (VT.isVector()) {
1160 SmallVector<SDValue, 8> Ops;
1161 Ops.assign(VT.getVectorNumElements(), Result);
1162 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1167 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1168 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1172 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1173 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1176 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1177 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1179 EVT EltVT = VT.getScalarType();
1181 // Do the map lookup using the actual bit pattern for the floating point
1182 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1183 // we don't have issues with SNANs.
1184 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1185 FoldingSetNodeID ID;
1186 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1189 SDNode *N = nullptr;
1190 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1192 return SDValue(N, 0);
1195 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1196 CSEMap.InsertNode(N, IP);
1197 AllNodes.push_back(N);
1200 SDValue Result(N, 0);
1201 if (VT.isVector()) {
1202 SmallVector<SDValue, 8> Ops;
1203 Ops.assign(VT.getVectorNumElements(), Result);
1204 // FIXME SDLoc info might be appropriate here
1205 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1210 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1211 EVT EltVT = VT.getScalarType();
1212 if (EltVT==MVT::f32)
1213 return getConstantFP(APFloat((float)Val), VT, isTarget);
1214 else if (EltVT==MVT::f64)
1215 return getConstantFP(APFloat(Val), VT, isTarget);
1216 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1219 APFloat apf = APFloat(Val);
1220 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1222 return getConstantFP(apf, VT, isTarget);
1224 llvm_unreachable("Unsupported type in getConstantFP");
1227 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1228 EVT VT, int64_t Offset,
1230 unsigned char TargetFlags) {
1231 assert((TargetFlags == 0 || isTargetGA) &&
1232 "Cannot set target flags on target-independent globals");
1233 const TargetLowering *TLI = TM.getTargetLowering();
1235 // Truncate (with sign-extension) the offset value to the pointer size.
1236 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1238 Offset = SignExtend64(Offset, BitWidth);
1241 if (GV->isThreadLocal())
1242 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1244 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1246 FoldingSetNodeID ID;
1247 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1249 ID.AddInteger(Offset);
1250 ID.AddInteger(TargetFlags);
1251 ID.AddInteger(GV->getType()->getAddressSpace());
1253 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1254 return SDValue(E, 0);
1256 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1257 DL.getDebugLoc(), GV, VT,
1258 Offset, TargetFlags);
1259 CSEMap.InsertNode(N, IP);
1260 AllNodes.push_back(N);
1261 return SDValue(N, 0);
1264 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1265 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1266 FoldingSetNodeID ID;
1267 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1270 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1271 return SDValue(E, 0);
1273 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1274 CSEMap.InsertNode(N, IP);
1275 AllNodes.push_back(N);
1276 return SDValue(N, 0);
1279 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1280 unsigned char TargetFlags) {
1281 assert((TargetFlags == 0 || isTarget) &&
1282 "Cannot set target flags on target-independent jump tables");
1283 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1284 FoldingSetNodeID ID;
1285 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1287 ID.AddInteger(TargetFlags);
1289 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1290 return SDValue(E, 0);
1292 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1294 CSEMap.InsertNode(N, IP);
1295 AllNodes.push_back(N);
1296 return SDValue(N, 0);
1299 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1300 unsigned Alignment, int Offset,
1302 unsigned char TargetFlags) {
1303 assert((TargetFlags == 0 || isTarget) &&
1304 "Cannot set target flags on target-independent globals");
1307 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1308 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1309 FoldingSetNodeID ID;
1310 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1311 ID.AddInteger(Alignment);
1312 ID.AddInteger(Offset);
1314 ID.AddInteger(TargetFlags);
1316 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1317 return SDValue(E, 0);
1319 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1320 Alignment, TargetFlags);
1321 CSEMap.InsertNode(N, IP);
1322 AllNodes.push_back(N);
1323 return SDValue(N, 0);
1327 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1328 unsigned Alignment, int Offset,
1330 unsigned char TargetFlags) {
1331 assert((TargetFlags == 0 || isTarget) &&
1332 "Cannot set target flags on target-independent globals");
1335 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1336 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1337 FoldingSetNodeID ID;
1338 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1339 ID.AddInteger(Alignment);
1340 ID.AddInteger(Offset);
1341 C->addSelectionDAGCSEId(ID);
1342 ID.AddInteger(TargetFlags);
1344 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1345 return SDValue(E, 0);
1347 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1348 Alignment, TargetFlags);
1349 CSEMap.InsertNode(N, IP);
1350 AllNodes.push_back(N);
1351 return SDValue(N, 0);
1354 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1355 unsigned char TargetFlags) {
1356 FoldingSetNodeID ID;
1357 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1358 ID.AddInteger(Index);
1359 ID.AddInteger(Offset);
1360 ID.AddInteger(TargetFlags);
1362 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1363 return SDValue(E, 0);
1365 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1367 CSEMap.InsertNode(N, IP);
1368 AllNodes.push_back(N);
1369 return SDValue(N, 0);
1372 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1373 FoldingSetNodeID ID;
1374 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1377 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1378 return SDValue(E, 0);
1380 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1381 CSEMap.InsertNode(N, IP);
1382 AllNodes.push_back(N);
1383 return SDValue(N, 0);
1386 SDValue SelectionDAG::getValueType(EVT VT) {
1387 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1388 ValueTypeNodes.size())
1389 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1391 SDNode *&N = VT.isExtended() ?
1392 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1394 if (N) return SDValue(N, 0);
1395 N = new (NodeAllocator) VTSDNode(VT);
1396 AllNodes.push_back(N);
1397 return SDValue(N, 0);
1400 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1401 SDNode *&N = ExternalSymbols[Sym];
1402 if (N) return SDValue(N, 0);
1403 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1404 AllNodes.push_back(N);
1405 return SDValue(N, 0);
1408 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1409 unsigned char TargetFlags) {
1411 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1413 if (N) return SDValue(N, 0);
1414 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1415 AllNodes.push_back(N);
1416 return SDValue(N, 0);
1419 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1420 if ((unsigned)Cond >= CondCodeNodes.size())
1421 CondCodeNodes.resize(Cond+1);
1423 if (!CondCodeNodes[Cond]) {
1424 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1425 CondCodeNodes[Cond] = N;
1426 AllNodes.push_back(N);
1429 return SDValue(CondCodeNodes[Cond], 0);
1432 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1433 // the shuffle mask M that point at N1 to point at N2, and indices that point
1434 // N2 to point at N1.
1435 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1437 int NElts = M.size();
1438 for (int i = 0; i != NElts; ++i) {
1446 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1447 SDValue N2, const int *Mask) {
1448 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1449 "Invalid VECTOR_SHUFFLE");
1451 // Canonicalize shuffle undef, undef -> undef
1452 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1453 return getUNDEF(VT);
1455 // Validate that all indices in Mask are within the range of the elements
1456 // input to the shuffle.
1457 unsigned NElts = VT.getVectorNumElements();
1458 SmallVector<int, 8> MaskVec;
1459 for (unsigned i = 0; i != NElts; ++i) {
1460 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1461 MaskVec.push_back(Mask[i]);
1464 // Canonicalize shuffle v, v -> v, undef
1467 for (unsigned i = 0; i != NElts; ++i)
1468 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1471 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1472 if (N1.getOpcode() == ISD::UNDEF)
1473 commuteShuffle(N1, N2, MaskVec);
1475 // Canonicalize all index into lhs, -> shuffle lhs, undef
1476 // Canonicalize all index into rhs, -> shuffle rhs, undef
1477 bool AllLHS = true, AllRHS = true;
1478 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1479 for (unsigned i = 0; i != NElts; ++i) {
1480 if (MaskVec[i] >= (int)NElts) {
1485 } else if (MaskVec[i] >= 0) {
1489 if (AllLHS && AllRHS)
1490 return getUNDEF(VT);
1491 if (AllLHS && !N2Undef)
1495 commuteShuffle(N1, N2, MaskVec);
1498 // If Identity shuffle return that node.
1499 bool Identity = true;
1500 for (unsigned i = 0; i != NElts; ++i) {
1501 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1503 if (Identity && NElts)
1506 // Shuffling a constant splat doesn't change the result.
1507 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1508 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1511 FoldingSetNodeID ID;
1512 SDValue Ops[2] = { N1, N2 };
1513 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1514 for (unsigned i = 0; i != NElts; ++i)
1515 ID.AddInteger(MaskVec[i]);
1518 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1519 return SDValue(E, 0);
1521 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1522 // SDNode doesn't have access to it. This memory will be "leaked" when
1523 // the node is deallocated, but recovered when the NodeAllocator is released.
1524 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1525 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1527 ShuffleVectorSDNode *N =
1528 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1529 dl.getDebugLoc(), N1, N2,
1531 CSEMap.InsertNode(N, IP);
1532 AllNodes.push_back(N);
1533 return SDValue(N, 0);
1536 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1537 SDValue Val, SDValue DTy,
1538 SDValue STy, SDValue Rnd, SDValue Sat,
1539 ISD::CvtCode Code) {
1540 // If the src and dest types are the same and the conversion is between
1541 // integer types of the same sign or two floats, no conversion is necessary.
1543 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1546 FoldingSetNodeID ID;
1547 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1548 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1550 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1551 return SDValue(E, 0);
1553 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1556 CSEMap.InsertNode(N, IP);
1557 AllNodes.push_back(N);
1558 return SDValue(N, 0);
1561 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1562 FoldingSetNodeID ID;
1563 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1564 ID.AddInteger(RegNo);
1566 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1567 return SDValue(E, 0);
1569 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1570 CSEMap.InsertNode(N, IP);
1571 AllNodes.push_back(N);
1572 return SDValue(N, 0);
1575 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1576 FoldingSetNodeID ID;
1577 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1578 ID.AddPointer(RegMask);
1580 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1581 return SDValue(E, 0);
1583 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1584 CSEMap.InsertNode(N, IP);
1585 AllNodes.push_back(N);
1586 return SDValue(N, 0);
1589 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1590 FoldingSetNodeID ID;
1591 SDValue Ops[] = { Root };
1592 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1593 ID.AddPointer(Label);
1595 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1596 return SDValue(E, 0);
1598 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1599 dl.getDebugLoc(), Root, Label);
1600 CSEMap.InsertNode(N, IP);
1601 AllNodes.push_back(N);
1602 return SDValue(N, 0);
1606 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1609 unsigned char TargetFlags) {
1610 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1612 FoldingSetNodeID ID;
1613 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1615 ID.AddInteger(Offset);
1616 ID.AddInteger(TargetFlags);
1618 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1619 return SDValue(E, 0);
1621 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1623 CSEMap.InsertNode(N, IP);
1624 AllNodes.push_back(N);
1625 return SDValue(N, 0);
1628 SDValue SelectionDAG::getSrcValue(const Value *V) {
1629 assert((!V || V->getType()->isPointerTy()) &&
1630 "SrcValue is not a pointer?");
1632 FoldingSetNodeID ID;
1633 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1637 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1638 return SDValue(E, 0);
1640 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1641 CSEMap.InsertNode(N, IP);
1642 AllNodes.push_back(N);
1643 return SDValue(N, 0);
1646 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1647 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1648 FoldingSetNodeID ID;
1649 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1653 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1654 return SDValue(E, 0);
1656 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1657 CSEMap.InsertNode(N, IP);
1658 AllNodes.push_back(N);
1659 return SDValue(N, 0);
1662 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1663 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1664 unsigned SrcAS, unsigned DestAS) {
1665 SDValue Ops[] = {Ptr};
1666 FoldingSetNodeID ID;
1667 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1668 ID.AddInteger(SrcAS);
1669 ID.AddInteger(DestAS);
1672 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1673 return SDValue(E, 0);
1675 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1677 VT, Ptr, SrcAS, DestAS);
1678 CSEMap.InsertNode(N, IP);
1679 AllNodes.push_back(N);
1680 return SDValue(N, 0);
1683 /// getShiftAmountOperand - Return the specified value casted to
1684 /// the target's desired shift amount type.
1685 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1686 EVT OpTy = Op.getValueType();
1687 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1688 if (OpTy == ShTy || OpTy.isVector()) return Op;
1690 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1691 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1694 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1695 /// specified value type.
1696 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1697 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1698 unsigned ByteSize = VT.getStoreSize();
1699 Type *Ty = VT.getTypeForEVT(*getContext());
1700 const TargetLowering *TLI = TM.getTargetLowering();
1701 unsigned StackAlign =
1702 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1704 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1705 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1708 /// CreateStackTemporary - Create a stack temporary suitable for holding
1709 /// either of the specified value types.
1710 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1711 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1712 VT2.getStoreSizeInBits())/8;
1713 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1714 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1715 const TargetLowering *TLI = TM.getTargetLowering();
1716 const DataLayout *TD = TLI->getDataLayout();
1717 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1718 TD->getPrefTypeAlignment(Ty2));
1720 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1721 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1722 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1725 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1726 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1727 // These setcc operations always fold.
1731 case ISD::SETFALSE2: return getConstant(0, VT);
1733 case ISD::SETTRUE2: {
1734 const TargetLowering *TLI = TM.getTargetLowering();
1735 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1737 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1750 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1754 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1755 const APInt &C2 = N2C->getAPIntValue();
1756 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1757 const APInt &C1 = N1C->getAPIntValue();
1760 default: llvm_unreachable("Unknown integer setcc!");
1761 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1762 case ISD::SETNE: return getConstant(C1 != C2, VT);
1763 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1764 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1765 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1766 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1767 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1768 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1769 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1770 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1774 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1775 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1776 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1779 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1780 return getUNDEF(VT);
1782 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1783 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1784 return getUNDEF(VT);
1786 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1787 R==APFloat::cmpLessThan, VT);
1788 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1789 return getUNDEF(VT);
1791 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1792 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1793 return getUNDEF(VT);
1795 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1796 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1797 return getUNDEF(VT);
1799 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1800 R==APFloat::cmpEqual, VT);
1801 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1802 return getUNDEF(VT);
1804 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1805 R==APFloat::cmpEqual, VT);
1806 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1807 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1808 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1809 R==APFloat::cmpEqual, VT);
1810 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1811 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1812 R==APFloat::cmpLessThan, VT);
1813 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1814 R==APFloat::cmpUnordered, VT);
1815 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1816 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1819 // Ensure that the constant occurs on the RHS.
1820 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1821 MVT CompVT = N1.getValueType().getSimpleVT();
1822 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1825 return getSetCC(dl, VT, N2, N1, SwappedCond);
1829 // Could not fold it.
1833 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1834 /// use this predicate to simplify operations downstream.
1835 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1836 // This predicate is not safe for vector operations.
1837 if (Op.getValueType().isVector())
1840 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1841 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1844 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1845 /// this predicate to simplify operations downstream. Mask is known to be zero
1846 /// for bits that V cannot have.
1847 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1848 unsigned Depth) const {
1849 APInt KnownZero, KnownOne;
1850 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1851 return (KnownZero & Mask) == Mask;
1854 /// Determine which bits of Op are known to be either zero or one and return
1855 /// them in the KnownZero/KnownOne bitsets.
1856 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1857 APInt &KnownOne, unsigned Depth) const {
1858 const TargetLowering *TLI = TM.getTargetLowering();
1859 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1861 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1863 return; // Limit search depth.
1865 APInt KnownZero2, KnownOne2;
1867 switch (Op.getOpcode()) {
1869 // We know all of the bits for a constant!
1870 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1871 KnownZero = ~KnownOne;
1874 // If either the LHS or the RHS are Zero, the result is zero.
1875 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1876 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1878 // Output known-1 bits are only known if set in both the LHS & RHS.
1879 KnownOne &= KnownOne2;
1880 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1881 KnownZero |= KnownZero2;
1884 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1885 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1887 // Output known-0 bits are only known if clear in both the LHS & RHS.
1888 KnownZero &= KnownZero2;
1889 // Output known-1 are known to be set if set in either the LHS | RHS.
1890 KnownOne |= KnownOne2;
1893 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1894 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1896 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1897 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1898 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1899 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1900 KnownZero = KnownZeroOut;
1904 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1905 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1907 // If low bits are zero in either operand, output low known-0 bits.
1908 // Also compute a conserative estimate for high known-0 bits.
1909 // More trickiness is possible, but this is sufficient for the
1910 // interesting case of alignment computation.
1911 KnownOne.clearAllBits();
1912 unsigned TrailZ = KnownZero.countTrailingOnes() +
1913 KnownZero2.countTrailingOnes();
1914 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1915 KnownZero2.countLeadingOnes(),
1916 BitWidth) - BitWidth;
1918 TrailZ = std::min(TrailZ, BitWidth);
1919 LeadZ = std::min(LeadZ, BitWidth);
1920 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1921 APInt::getHighBitsSet(BitWidth, LeadZ);
1925 // For the purposes of computing leading zeros we can conservatively
1926 // treat a udiv as a logical right shift by the power of 2 known to
1927 // be less than the denominator.
1928 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1929 unsigned LeadZ = KnownZero2.countLeadingOnes();
1931 KnownOne2.clearAllBits();
1932 KnownZero2.clearAllBits();
1933 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1934 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1935 if (RHSUnknownLeadingOnes != BitWidth)
1936 LeadZ = std::min(BitWidth,
1937 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1939 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1943 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1944 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1946 // Only known if known in both the LHS and RHS.
1947 KnownOne &= KnownOne2;
1948 KnownZero &= KnownZero2;
1950 case ISD::SELECT_CC:
1951 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1952 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1954 // Only known if known in both the LHS and RHS.
1955 KnownOne &= KnownOne2;
1956 KnownZero &= KnownZero2;
1964 if (Op.getResNo() != 1)
1966 // The boolean result conforms to getBooleanContents. Fall through.
1968 // If we know the result of a setcc has the top bits zero, use this info.
1969 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1970 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1971 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1974 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1975 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1976 unsigned ShAmt = SA->getZExtValue();
1978 // If the shift count is an invalid immediate, don't do anything.
1979 if (ShAmt >= BitWidth)
1982 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1983 KnownZero <<= ShAmt;
1985 // low bits known zero.
1986 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1990 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1991 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1992 unsigned ShAmt = SA->getZExtValue();
1994 // If the shift count is an invalid immediate, don't do anything.
1995 if (ShAmt >= BitWidth)
1998 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1999 KnownZero = KnownZero.lshr(ShAmt);
2000 KnownOne = KnownOne.lshr(ShAmt);
2002 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2003 KnownZero |= HighBits; // High bits known zero.
2007 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2008 unsigned ShAmt = SA->getZExtValue();
2010 // If the shift count is an invalid immediate, don't do anything.
2011 if (ShAmt >= BitWidth)
2014 // If any of the demanded bits are produced by the sign extension, we also
2015 // demand the input sign bit.
2016 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2018 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2019 KnownZero = KnownZero.lshr(ShAmt);
2020 KnownOne = KnownOne.lshr(ShAmt);
2022 // Handle the sign bits.
2023 APInt SignBit = APInt::getSignBit(BitWidth);
2024 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2026 if (KnownZero.intersects(SignBit)) {
2027 KnownZero |= HighBits; // New bits are known zero.
2028 } else if (KnownOne.intersects(SignBit)) {
2029 KnownOne |= HighBits; // New bits are known one.
2033 case ISD::SIGN_EXTEND_INREG: {
2034 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2035 unsigned EBits = EVT.getScalarType().getSizeInBits();
2037 // Sign extension. Compute the demanded bits in the result that are not
2038 // present in the input.
2039 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2041 APInt InSignBit = APInt::getSignBit(EBits);
2042 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2044 // If the sign extended bits are demanded, we know that the sign
2046 InSignBit = InSignBit.zext(BitWidth);
2047 if (NewBits.getBoolValue())
2048 InputDemandedBits |= InSignBit;
2050 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2051 KnownOne &= InputDemandedBits;
2052 KnownZero &= InputDemandedBits;
2054 // If the sign bit of the input is known set or clear, then we know the
2055 // top bits of the result.
2056 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2057 KnownZero |= NewBits;
2058 KnownOne &= ~NewBits;
2059 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2060 KnownOne |= NewBits;
2061 KnownZero &= ~NewBits;
2062 } else { // Input sign bit unknown
2063 KnownZero &= ~NewBits;
2064 KnownOne &= ~NewBits;
2069 case ISD::CTTZ_ZERO_UNDEF:
2071 case ISD::CTLZ_ZERO_UNDEF:
2073 unsigned LowBits = Log2_32(BitWidth)+1;
2074 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2075 KnownOne.clearAllBits();
2079 LoadSDNode *LD = cast<LoadSDNode>(Op);
2080 // If this is a ZEXTLoad and we are looking at the loaded value.
2081 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2082 EVT VT = LD->getMemoryVT();
2083 unsigned MemBits = VT.getScalarType().getSizeInBits();
2084 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2085 } else if (const MDNode *Ranges = LD->getRanges()) {
2086 computeKnownBitsLoad(*Ranges, KnownZero);
2090 case ISD::ZERO_EXTEND: {
2091 EVT InVT = Op.getOperand(0).getValueType();
2092 unsigned InBits = InVT.getScalarType().getSizeInBits();
2093 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2094 KnownZero = KnownZero.trunc(InBits);
2095 KnownOne = KnownOne.trunc(InBits);
2096 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2097 KnownZero = KnownZero.zext(BitWidth);
2098 KnownOne = KnownOne.zext(BitWidth);
2099 KnownZero |= NewBits;
2102 case ISD::SIGN_EXTEND: {
2103 EVT InVT = Op.getOperand(0).getValueType();
2104 unsigned InBits = InVT.getScalarType().getSizeInBits();
2105 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2107 KnownZero = KnownZero.trunc(InBits);
2108 KnownOne = KnownOne.trunc(InBits);
2109 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2111 // Note if the sign bit is known to be zero or one.
2112 bool SignBitKnownZero = KnownZero.isNegative();
2113 bool SignBitKnownOne = KnownOne.isNegative();
2115 KnownZero = KnownZero.zext(BitWidth);
2116 KnownOne = KnownOne.zext(BitWidth);
2118 // If the sign bit is known zero or one, the top bits match.
2119 if (SignBitKnownZero)
2120 KnownZero |= NewBits;
2121 else if (SignBitKnownOne)
2122 KnownOne |= NewBits;
2125 case ISD::ANY_EXTEND: {
2126 EVT InVT = Op.getOperand(0).getValueType();
2127 unsigned InBits = InVT.getScalarType().getSizeInBits();
2128 KnownZero = KnownZero.trunc(InBits);
2129 KnownOne = KnownOne.trunc(InBits);
2130 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2131 KnownZero = KnownZero.zext(BitWidth);
2132 KnownOne = KnownOne.zext(BitWidth);
2135 case ISD::TRUNCATE: {
2136 EVT InVT = Op.getOperand(0).getValueType();
2137 unsigned InBits = InVT.getScalarType().getSizeInBits();
2138 KnownZero = KnownZero.zext(InBits);
2139 KnownOne = KnownOne.zext(InBits);
2140 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141 KnownZero = KnownZero.trunc(BitWidth);
2142 KnownOne = KnownOne.trunc(BitWidth);
2145 case ISD::AssertZext: {
2146 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2147 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2148 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2149 KnownZero |= (~InMask);
2150 KnownOne &= (~KnownZero);
2154 // All bits are zero except the low bit.
2155 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2159 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2160 // We know that the top bits of C-X are clear if X contains less bits
2161 // than C (i.e. no wrap-around can happen). For example, 20-X is
2162 // positive if we can prove that X is >= 0 and < 16.
2163 if (CLHS->getAPIntValue().isNonNegative()) {
2164 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2165 // NLZ can't be BitWidth with no sign bit
2166 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2167 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2169 // If all of the MaskV bits are known to be zero, then we know the
2170 // output top bits are zero, because we now know that the output is
2172 if ((KnownZero2 & MaskV) == MaskV) {
2173 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2174 // Top bits known zero.
2175 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2183 // Output known-0 bits are known if clear or set in both the low clear bits
2184 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2185 // low 3 bits clear.
2186 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2187 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2189 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2190 KnownZeroOut = std::min(KnownZeroOut,
2191 KnownZero2.countTrailingOnes());
2193 if (Op.getOpcode() == ISD::ADD) {
2194 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2198 // With ADDE, a carry bit may be added in, so we can only use this
2199 // information if we know (at least) that the low two bits are clear. We
2200 // then return to the caller that the low bit is unknown but that other bits
2202 if (KnownZeroOut >= 2) // ADDE
2203 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2207 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2208 const APInt &RA = Rem->getAPIntValue().abs();
2209 if (RA.isPowerOf2()) {
2210 APInt LowBits = RA - 1;
2211 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2213 // The low bits of the first operand are unchanged by the srem.
2214 KnownZero = KnownZero2 & LowBits;
2215 KnownOne = KnownOne2 & LowBits;
2217 // If the first operand is non-negative or has all low bits zero, then
2218 // the upper bits are all zero.
2219 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2220 KnownZero |= ~LowBits;
2222 // If the first operand is negative and not all low bits are zero, then
2223 // the upper bits are all one.
2224 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2225 KnownOne |= ~LowBits;
2226 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2231 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2232 const APInt &RA = Rem->getAPIntValue();
2233 if (RA.isPowerOf2()) {
2234 APInt LowBits = (RA - 1);
2235 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2237 // The upper bits are all zero, the lower ones are unchanged.
2238 KnownZero = KnownZero2 | ~LowBits;
2239 KnownOne = KnownOne2 & LowBits;
2244 // Since the result is less than or equal to either operand, any leading
2245 // zero bits in either operand must also exist in the result.
2246 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2247 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2249 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2250 KnownZero2.countLeadingOnes());
2251 KnownOne.clearAllBits();
2252 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2255 case ISD::FrameIndex:
2256 case ISD::TargetFrameIndex:
2257 if (unsigned Align = InferPtrAlignment(Op)) {
2258 // The low bits are known zero if the pointer is aligned.
2259 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2265 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2268 case ISD::INTRINSIC_WO_CHAIN:
2269 case ISD::INTRINSIC_W_CHAIN:
2270 case ISD::INTRINSIC_VOID:
2271 // Allow the target to implement this method for its nodes.
2272 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2276 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2279 /// ComputeNumSignBits - Return the number of times the sign bit of the
2280 /// register is replicated into the other bits. We know that at least 1 bit
2281 /// is always equal to the sign bit (itself), but other cases can give us
2282 /// information. For example, immediately after an "SRA X, 2", we know that
2283 /// the top 3 bits are all equal to each other, so we return 3.
2284 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2285 const TargetLowering *TLI = TM.getTargetLowering();
2286 EVT VT = Op.getValueType();
2287 assert(VT.isInteger() && "Invalid VT!");
2288 unsigned VTBits = VT.getScalarType().getSizeInBits();
2290 unsigned FirstAnswer = 1;
2293 return 1; // Limit search depth.
2295 switch (Op.getOpcode()) {
2297 case ISD::AssertSext:
2298 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2299 return VTBits-Tmp+1;
2300 case ISD::AssertZext:
2301 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2304 case ISD::Constant: {
2305 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2306 return Val.getNumSignBits();
2309 case ISD::SIGN_EXTEND:
2311 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2312 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2314 case ISD::SIGN_EXTEND_INREG:
2315 // Max of the input and what this extends.
2317 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2320 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2321 return std::max(Tmp, Tmp2);
2324 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2325 // SRA X, C -> adds C sign bits.
2326 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2327 Tmp += C->getZExtValue();
2328 if (Tmp > VTBits) Tmp = VTBits;
2332 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2333 // shl destroys sign bits.
2334 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2335 if (C->getZExtValue() >= VTBits || // Bad shift.
2336 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2337 return Tmp - C->getZExtValue();
2342 case ISD::XOR: // NOT is handled here.
2343 // Logical binary ops preserve the number of sign bits at the worst.
2344 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2346 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2347 FirstAnswer = std::min(Tmp, Tmp2);
2348 // We computed what we know about the sign bits as our first
2349 // answer. Now proceed to the generic code that uses
2350 // computeKnownBits, and pick whichever answer is better.
2355 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2356 if (Tmp == 1) return 1; // Early out.
2357 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2358 return std::min(Tmp, Tmp2);
2366 if (Op.getResNo() != 1)
2368 // The boolean result conforms to getBooleanContents. Fall through.
2370 // If setcc returns 0/-1, all bits are sign bits.
2371 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2372 TargetLowering::ZeroOrNegativeOneBooleanContent)
2377 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2378 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2380 // Handle rotate right by N like a rotate left by 32-N.
2381 if (Op.getOpcode() == ISD::ROTR)
2382 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2384 // If we aren't rotating out all of the known-in sign bits, return the
2385 // number that are left. This handles rotl(sext(x), 1) for example.
2386 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2387 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2391 // Add can have at most one carry bit. Thus we know that the output
2392 // is, at worst, one more bit than the inputs.
2393 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2394 if (Tmp == 1) return 1; // Early out.
2396 // Special case decrementing a value (ADD X, -1):
2397 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2398 if (CRHS->isAllOnesValue()) {
2399 APInt KnownZero, KnownOne;
2400 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2402 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2404 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2407 // If we are subtracting one from a positive number, there is no carry
2408 // out of the result.
2409 if (KnownZero.isNegative())
2413 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2414 if (Tmp2 == 1) return 1;
2415 return std::min(Tmp, Tmp2)-1;
2418 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2419 if (Tmp2 == 1) return 1;
2422 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2423 if (CLHS->isNullValue()) {
2424 APInt KnownZero, KnownOne;
2425 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2426 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2428 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2431 // If the input is known to be positive (the sign bit is known clear),
2432 // the output of the NEG has the same number of sign bits as the input.
2433 if (KnownZero.isNegative())
2436 // Otherwise, we treat this like a SUB.
2439 // Sub can have at most one carry bit. Thus we know that the output
2440 // is, at worst, one more bit than the inputs.
2441 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2442 if (Tmp == 1) return 1; // Early out.
2443 return std::min(Tmp, Tmp2)-1;
2445 // FIXME: it's tricky to do anything useful for this, but it is an important
2446 // case for targets like X86.
2450 // If we are looking at the loaded value of the SDNode.
2451 if (Op.getResNo() == 0) {
2452 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2453 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2454 unsigned ExtType = LD->getExtensionType();
2457 case ISD::SEXTLOAD: // '17' bits known
2458 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2459 return VTBits-Tmp+1;
2460 case ISD::ZEXTLOAD: // '16' bits known
2461 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2467 // Allow the target to implement this method for its nodes.
2468 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2469 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2470 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2471 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2472 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2473 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2476 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2477 // use this information.
2478 APInt KnownZero, KnownOne;
2479 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2482 if (KnownZero.isNegative()) { // sign bit is 0
2484 } else if (KnownOne.isNegative()) { // sign bit is 1;
2491 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2492 // the number of identical bits in the top of the input value.
2494 Mask <<= Mask.getBitWidth()-VTBits;
2495 // Return # leading zeros. We use 'min' here in case Val was zero before
2496 // shifting. We don't want to return '64' as for an i32 "0".
2497 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2500 /// isBaseWithConstantOffset - Return true if the specified operand is an
2501 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2502 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2503 /// semantics as an ADD. This handles the equivalence:
2504 /// X|Cst == X+Cst iff X&Cst = 0.
2505 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2506 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2507 !isa<ConstantSDNode>(Op.getOperand(1)))
2510 if (Op.getOpcode() == ISD::OR &&
2511 !MaskedValueIsZero(Op.getOperand(0),
2512 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2519 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2520 // If we're told that NaNs won't happen, assume they won't.
2521 if (getTarget().Options.NoNaNsFPMath)
2524 // If the value is a constant, we can obviously see if it is a NaN or not.
2525 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2526 return !C->getValueAPF().isNaN();
2528 // TODO: Recognize more cases here.
2533 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2534 // If the value is a constant, we can obviously see if it is a zero or not.
2535 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2536 return !C->isZero();
2538 // TODO: Recognize more cases here.
2539 switch (Op.getOpcode()) {
2542 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2543 return !C->isNullValue();
2550 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2551 // Check the obvious case.
2552 if (A == B) return true;
2554 // For for negative and positive zero.
2555 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2556 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2557 if (CA->isZero() && CB->isZero()) return true;
2559 // Otherwise they may not be equal.
2563 /// getNode - Gets or creates the specified node.
2565 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2566 FoldingSetNodeID ID;
2567 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2569 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2570 return SDValue(E, 0);
2572 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2573 DL.getDebugLoc(), getVTList(VT));
2574 CSEMap.InsertNode(N, IP);
2576 AllNodes.push_back(N);
2580 return SDValue(N, 0);
2583 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2584 EVT VT, SDValue Operand) {
2585 // Constant fold unary operations with an integer constant operand. Even
2586 // opaque constant will be folded, because the folding of unary operations
2587 // doesn't create new constants with different values. Nevertheless, the
2588 // opaque flag is preserved during folding to prevent future folding with
2590 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2591 const APInt &Val = C->getAPIntValue();
2594 case ISD::SIGN_EXTEND:
2595 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2596 C->isTargetOpcode(), C->isOpaque());
2597 case ISD::ANY_EXTEND:
2598 case ISD::ZERO_EXTEND:
2600 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2601 C->isTargetOpcode(), C->isOpaque());
2602 case ISD::UINT_TO_FP:
2603 case ISD::SINT_TO_FP: {
2604 APFloat apf(EVTToAPFloatSemantics(VT),
2605 APInt::getNullValue(VT.getSizeInBits()));
2606 (void)apf.convertFromAPInt(Val,
2607 Opcode==ISD::SINT_TO_FP,
2608 APFloat::rmNearestTiesToEven);
2609 return getConstantFP(apf, VT);
2612 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2613 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2614 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2615 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2618 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2621 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2624 case ISD::CTLZ_ZERO_UNDEF:
2625 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2628 case ISD::CTTZ_ZERO_UNDEF:
2629 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2634 // Constant fold unary operations with a floating point constant operand.
2635 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2636 APFloat V = C->getValueAPF(); // make copy
2640 return getConstantFP(V, VT);
2643 return getConstantFP(V, VT);
2645 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2646 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2647 return getConstantFP(V, VT);
2651 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2652 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2653 return getConstantFP(V, VT);
2657 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2658 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2659 return getConstantFP(V, VT);
2662 case ISD::FP_EXTEND: {
2664 // This can return overflow, underflow, or inexact; we don't care.
2665 // FIXME need to be more flexible about rounding mode.
2666 (void)V.convert(EVTToAPFloatSemantics(VT),
2667 APFloat::rmNearestTiesToEven, &ignored);
2668 return getConstantFP(V, VT);
2670 case ISD::FP_TO_SINT:
2671 case ISD::FP_TO_UINT: {
2674 assert(integerPartWidth >= 64);
2675 // FIXME need to be more flexible about rounding mode.
2676 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2677 Opcode==ISD::FP_TO_SINT,
2678 APFloat::rmTowardZero, &ignored);
2679 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2681 APInt api(VT.getSizeInBits(), x);
2682 return getConstant(api, VT);
2685 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2686 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2687 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2688 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2693 unsigned OpOpcode = Operand.getNode()->getOpcode();
2695 case ISD::TokenFactor:
2696 case ISD::MERGE_VALUES:
2697 case ISD::CONCAT_VECTORS:
2698 return Operand; // Factor, merge or concat of one node? No need.
2699 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2700 case ISD::FP_EXTEND:
2701 assert(VT.isFloatingPoint() &&
2702 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2703 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2704 assert((!VT.isVector() ||
2705 VT.getVectorNumElements() ==
2706 Operand.getValueType().getVectorNumElements()) &&
2707 "Vector element count mismatch!");
2708 if (Operand.getOpcode() == ISD::UNDEF)
2709 return getUNDEF(VT);
2711 case ISD::SIGN_EXTEND:
2712 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2713 "Invalid SIGN_EXTEND!");
2714 if (Operand.getValueType() == VT) return Operand; // noop extension
2715 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2716 "Invalid sext node, dst < src!");
2717 assert((!VT.isVector() ||
2718 VT.getVectorNumElements() ==
2719 Operand.getValueType().getVectorNumElements()) &&
2720 "Vector element count mismatch!");
2721 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2722 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2723 else if (OpOpcode == ISD::UNDEF)
2724 // sext(undef) = 0, because the top bits will all be the same.
2725 return getConstant(0, VT);
2727 case ISD::ZERO_EXTEND:
2728 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2729 "Invalid ZERO_EXTEND!");
2730 if (Operand.getValueType() == VT) return Operand; // noop extension
2731 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2732 "Invalid zext node, dst < src!");
2733 assert((!VT.isVector() ||
2734 VT.getVectorNumElements() ==
2735 Operand.getValueType().getVectorNumElements()) &&
2736 "Vector element count mismatch!");
2737 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2738 return getNode(ISD::ZERO_EXTEND, DL, VT,
2739 Operand.getNode()->getOperand(0));
2740 else if (OpOpcode == ISD::UNDEF)
2741 // zext(undef) = 0, because the top bits will be zero.
2742 return getConstant(0, VT);
2744 case ISD::ANY_EXTEND:
2745 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2746 "Invalid ANY_EXTEND!");
2747 if (Operand.getValueType() == VT) return Operand; // noop extension
2748 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2749 "Invalid anyext node, dst < src!");
2750 assert((!VT.isVector() ||
2751 VT.getVectorNumElements() ==
2752 Operand.getValueType().getVectorNumElements()) &&
2753 "Vector element count mismatch!");
2755 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2756 OpOpcode == ISD::ANY_EXTEND)
2757 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2758 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2759 else if (OpOpcode == ISD::UNDEF)
2760 return getUNDEF(VT);
2762 // (ext (trunx x)) -> x
2763 if (OpOpcode == ISD::TRUNCATE) {
2764 SDValue OpOp = Operand.getNode()->getOperand(0);
2765 if (OpOp.getValueType() == VT)
2770 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2771 "Invalid TRUNCATE!");
2772 if (Operand.getValueType() == VT) return Operand; // noop truncate
2773 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2774 "Invalid truncate node, src < dst!");
2775 assert((!VT.isVector() ||
2776 VT.getVectorNumElements() ==
2777 Operand.getValueType().getVectorNumElements()) &&
2778 "Vector element count mismatch!");
2779 if (OpOpcode == ISD::TRUNCATE)
2780 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2781 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2782 OpOpcode == ISD::ANY_EXTEND) {
2783 // If the source is smaller than the dest, we still need an extend.
2784 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2785 .bitsLT(VT.getScalarType()))
2786 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2787 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2788 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2789 return Operand.getNode()->getOperand(0);
2791 if (OpOpcode == ISD::UNDEF)
2792 return getUNDEF(VT);
2795 // Basic sanity checking.
2796 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2797 && "Cannot BITCAST between types of different sizes!");
2798 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2799 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2800 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2801 if (OpOpcode == ISD::UNDEF)
2802 return getUNDEF(VT);
2804 case ISD::SCALAR_TO_VECTOR:
2805 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2806 (VT.getVectorElementType() == Operand.getValueType() ||
2807 (VT.getVectorElementType().isInteger() &&
2808 Operand.getValueType().isInteger() &&
2809 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2810 "Illegal SCALAR_TO_VECTOR node!");
2811 if (OpOpcode == ISD::UNDEF)
2812 return getUNDEF(VT);
2813 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2814 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2815 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2816 Operand.getConstantOperandVal(1) == 0 &&
2817 Operand.getOperand(0).getValueType() == VT)
2818 return Operand.getOperand(0);
2821 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2822 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2823 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2824 Operand.getNode()->getOperand(0));
2825 if (OpOpcode == ISD::FNEG) // --X -> X
2826 return Operand.getNode()->getOperand(0);
2829 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2830 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2835 SDVTList VTs = getVTList(VT);
2836 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2837 FoldingSetNodeID ID;
2838 SDValue Ops[1] = { Operand };
2839 AddNodeIDNode(ID, Opcode, VTs, Ops);
2841 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2842 return SDValue(E, 0);
2844 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2845 DL.getDebugLoc(), VTs, Operand);
2846 CSEMap.InsertNode(N, IP);
2848 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2849 DL.getDebugLoc(), VTs, Operand);
2852 AllNodes.push_back(N);
2856 return SDValue(N, 0);
2859 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2860 SDNode *Cst1, SDNode *Cst2) {
2861 // If the opcode is a target-specific ISD node, there's nothing we can
2862 // do here and the operand rules may not line up with the below, so
2864 if (Opcode >= ISD::BUILTIN_OP_END)
2867 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2868 SmallVector<SDValue, 4> Outputs;
2869 EVT SVT = VT.getScalarType();
2871 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2872 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2873 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2876 if (Scalar1 && Scalar2)
2877 // Scalar instruction.
2878 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2880 // For vectors extract each constant element into Inputs so we can constant
2881 // fold them individually.
2882 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2883 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2887 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2889 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2890 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2891 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2892 if (!V1 || !V2) // Not a constant, bail.
2895 if (V1->isOpaque() || V2->isOpaque())
2898 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2899 // FIXME: This is valid and could be handled by truncating the APInts.
2900 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2903 Inputs.push_back(std::make_pair(V1, V2));
2907 // We have a number of constant values, constant fold them element by element.
2908 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2909 const APInt &C1 = Inputs[I].first->getAPIntValue();
2910 const APInt &C2 = Inputs[I].second->getAPIntValue();
2914 Outputs.push_back(getConstant(C1 + C2, SVT));
2917 Outputs.push_back(getConstant(C1 - C2, SVT));
2920 Outputs.push_back(getConstant(C1 * C2, SVT));
2923 if (!C2.getBoolValue())
2925 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2928 if (!C2.getBoolValue())
2930 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2933 if (!C2.getBoolValue())
2935 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2938 if (!C2.getBoolValue())
2940 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2943 Outputs.push_back(getConstant(C1 & C2, SVT));
2946 Outputs.push_back(getConstant(C1 | C2, SVT));
2949 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2952 Outputs.push_back(getConstant(C1 << C2, SVT));
2955 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2958 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2961 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2964 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2971 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2972 "Expected a scalar or vector!"));
2974 // Handle the scalar case first.
2976 return Outputs.back();
2978 // We may have a vector type but a scalar result. Create a splat.
2979 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2981 // Build a big vector out of the scalar elements we generated.
2982 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2985 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2986 SDValue N2, bool nuw, bool nsw, bool exact) {
2987 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2988 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2991 case ISD::TokenFactor:
2992 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2993 N2.getValueType() == MVT::Other && "Invalid token factor!");
2994 // Fold trivial token factors.
2995 if (N1.getOpcode() == ISD::EntryToken) return N2;
2996 if (N2.getOpcode() == ISD::EntryToken) return N1;
2997 if (N1 == N2) return N1;
2999 case ISD::CONCAT_VECTORS:
3000 // Concat of UNDEFs is UNDEF.
3001 if (N1.getOpcode() == ISD::UNDEF &&
3002 N2.getOpcode() == ISD::UNDEF)
3003 return getUNDEF(VT);
3005 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3006 // one big BUILD_VECTOR.
3007 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3008 N2.getOpcode() == ISD::BUILD_VECTOR) {
3009 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3010 N1.getNode()->op_end());
3011 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3012 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3016 assert(VT.isInteger() && "This operator does not apply to FP types!");
3017 assert(N1.getValueType() == N2.getValueType() &&
3018 N1.getValueType() == VT && "Binary operator types must match!");
3019 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3020 // worth handling here.
3021 if (N2C && N2C->isNullValue())
3023 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3030 assert(VT.isInteger() && "This operator does not apply to FP types!");
3031 assert(N1.getValueType() == N2.getValueType() &&
3032 N1.getValueType() == VT && "Binary operator types must match!");
3033 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3034 // it's worth handling here.
3035 if (N2C && N2C->isNullValue())
3045 assert(VT.isInteger() && "This operator does not apply to FP types!");
3046 assert(N1.getValueType() == N2.getValueType() &&
3047 N1.getValueType() == VT && "Binary operator types must match!");
3054 if (getTarget().Options.UnsafeFPMath) {
3055 if (Opcode == ISD::FADD) {
3057 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3058 if (CFP->getValueAPF().isZero())
3061 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3062 if (CFP->getValueAPF().isZero())
3064 } else if (Opcode == ISD::FSUB) {
3066 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3067 if (CFP->getValueAPF().isZero())
3069 } else if (Opcode == ISD::FMUL) {
3070 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3073 // If the first operand isn't the constant, try the second
3075 CFP = dyn_cast<ConstantFPSDNode>(N2);
3082 return SDValue(CFP,0);
3084 if (CFP->isExactlyValue(1.0))
3089 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3090 assert(N1.getValueType() == N2.getValueType() &&
3091 N1.getValueType() == VT && "Binary operator types must match!");
3093 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3094 assert(N1.getValueType() == VT &&
3095 N1.getValueType().isFloatingPoint() &&
3096 N2.getValueType().isFloatingPoint() &&
3097 "Invalid FCOPYSIGN!");
3104 assert(VT == N1.getValueType() &&
3105 "Shift operators return type must be the same as their first arg");
3106 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3107 "Shifts only work on integers");
3108 assert((!VT.isVector() || VT == N2.getValueType()) &&
3109 "Vector shift amounts must be in the same as their first arg");
3110 // Verify that the shift amount VT is bit enough to hold valid shift
3111 // amounts. This catches things like trying to shift an i1024 value by an
3112 // i8, which is easy to fall into in generic code that uses
3113 // TLI.getShiftAmount().
3114 assert(N2.getValueType().getSizeInBits() >=
3115 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3116 "Invalid use of small shift amount with oversized value!");
3118 // Always fold shifts of i1 values so the code generator doesn't need to
3119 // handle them. Since we know the size of the shift has to be less than the
3120 // size of the value, the shift/rotate count is guaranteed to be zero.
3123 if (N2C && N2C->isNullValue())
3126 case ISD::FP_ROUND_INREG: {
3127 EVT EVT = cast<VTSDNode>(N2)->getVT();
3128 assert(VT == N1.getValueType() && "Not an inreg round!");
3129 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3130 "Cannot FP_ROUND_INREG integer types");
3131 assert(EVT.isVector() == VT.isVector() &&
3132 "FP_ROUND_INREG type should be vector iff the operand "
3134 assert((!EVT.isVector() ||
3135 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3136 "Vector element counts must match in FP_ROUND_INREG");
3137 assert(EVT.bitsLE(VT) && "Not rounding down!");
3139 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3143 assert(VT.isFloatingPoint() &&
3144 N1.getValueType().isFloatingPoint() &&
3145 VT.bitsLE(N1.getValueType()) &&
3146 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3147 if (N1.getValueType() == VT) return N1; // noop conversion.
3149 case ISD::AssertSext:
3150 case ISD::AssertZext: {
3151 EVT EVT = cast<VTSDNode>(N2)->getVT();
3152 assert(VT == N1.getValueType() && "Not an inreg extend!");
3153 assert(VT.isInteger() && EVT.isInteger() &&
3154 "Cannot *_EXTEND_INREG FP types");
3155 assert(!EVT.isVector() &&
3156 "AssertSExt/AssertZExt type should be the vector element type "
3157 "rather than the vector type!");
3158 assert(EVT.bitsLE(VT) && "Not extending!");
3159 if (VT == EVT) return N1; // noop assertion.
3162 case ISD::SIGN_EXTEND_INREG: {
3163 EVT EVT = cast<VTSDNode>(N2)->getVT();
3164 assert(VT == N1.getValueType() && "Not an inreg extend!");
3165 assert(VT.isInteger() && EVT.isInteger() &&
3166 "Cannot *_EXTEND_INREG FP types");
3167 assert(EVT.isVector() == VT.isVector() &&
3168 "SIGN_EXTEND_INREG type should be vector iff the operand "
3170 assert((!EVT.isVector() ||
3171 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3172 "Vector element counts must match in SIGN_EXTEND_INREG");
3173 assert(EVT.bitsLE(VT) && "Not extending!");
3174 if (EVT == VT) return N1; // Not actually extending
3177 APInt Val = N1C->getAPIntValue();
3178 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3179 Val <<= Val.getBitWidth()-FromBits;
3180 Val = Val.ashr(Val.getBitWidth()-FromBits);
3181 return getConstant(Val, VT);
3185 case ISD::EXTRACT_VECTOR_ELT:
3186 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3187 if (N1.getOpcode() == ISD::UNDEF)
3188 return getUNDEF(VT);
3190 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3191 // expanding copies of large vectors from registers.
3193 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3194 N1.getNumOperands() > 0) {
3196 N1.getOperand(0).getValueType().getVectorNumElements();
3197 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3198 N1.getOperand(N2C->getZExtValue() / Factor),
3199 getConstant(N2C->getZExtValue() % Factor,
3200 N2.getValueType()));
3203 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3204 // expanding large vector constants.
3205 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3206 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3208 if (VT != Elt.getValueType())
3209 // If the vector element type is not legal, the BUILD_VECTOR operands
3210 // are promoted and implicitly truncated, and the result implicitly
3211 // extended. Make that explicit here.
3212 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3217 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3218 // operations are lowered to scalars.
3219 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3220 // If the indices are the same, return the inserted element else
3221 // if the indices are known different, extract the element from
3222 // the original vector.
3223 SDValue N1Op2 = N1.getOperand(2);
3224 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3226 if (N1Op2C && N2C) {
3227 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3228 if (VT == N1.getOperand(1).getValueType())
3229 return N1.getOperand(1);
3231 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3234 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3238 case ISD::EXTRACT_ELEMENT:
3239 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3240 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3241 (N1.getValueType().isInteger() == VT.isInteger()) &&
3242 N1.getValueType() != VT &&
3243 "Wrong types for EXTRACT_ELEMENT!");
3245 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3246 // 64-bit integers into 32-bit parts. Instead of building the extract of
3247 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3248 if (N1.getOpcode() == ISD::BUILD_PAIR)
3249 return N1.getOperand(N2C->getZExtValue());
3251 // EXTRACT_ELEMENT of a constant int is also very common.
3252 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3253 unsigned ElementSize = VT.getSizeInBits();
3254 unsigned Shift = ElementSize * N2C->getZExtValue();
3255 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3256 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3259 case ISD::EXTRACT_SUBVECTOR: {
3261 if (VT.isSimple() && N1.getValueType().isSimple()) {
3262 assert(VT.isVector() && N1.getValueType().isVector() &&
3263 "Extract subvector VTs must be a vectors!");
3264 assert(VT.getVectorElementType() ==
3265 N1.getValueType().getVectorElementType() &&
3266 "Extract subvector VTs must have the same element type!");
3267 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3268 "Extract subvector must be from larger vector to smaller vector!");
3270 if (isa<ConstantSDNode>(Index.getNode())) {
3271 assert((VT.getVectorNumElements() +
3272 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3273 <= N1.getValueType().getVectorNumElements())
3274 && "Extract subvector overflow!");
3277 // Trivial extraction.
3278 if (VT.getSimpleVT() == N1.getSimpleValueType())
3285 // Perform trivial constant folding.
3286 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3287 if (SV.getNode()) return SV;
3289 // Canonicalize constant to RHS if commutative.
3290 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3291 std::swap(N1C, N2C);
3295 // Constant fold FP operations.
3296 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3297 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3299 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3300 // Canonicalize constant to RHS if commutative.
3301 std::swap(N1CFP, N2CFP);
3304 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3305 APFloat::opStatus s;
3308 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3309 if (s != APFloat::opInvalidOp)
3310 return getConstantFP(V1, VT);
3313 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3314 if (s!=APFloat::opInvalidOp)
3315 return getConstantFP(V1, VT);
3318 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3319 if (s!=APFloat::opInvalidOp)
3320 return getConstantFP(V1, VT);
3323 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3324 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3325 return getConstantFP(V1, VT);
3328 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3329 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3330 return getConstantFP(V1, VT);
3332 case ISD::FCOPYSIGN:
3334 return getConstantFP(V1, VT);
3339 if (Opcode == ISD::FP_ROUND) {
3340 APFloat V = N1CFP->getValueAPF(); // make copy
3342 // This can return overflow, underflow, or inexact; we don't care.
3343 // FIXME need to be more flexible about rounding mode.
3344 (void)V.convert(EVTToAPFloatSemantics(VT),
3345 APFloat::rmNearestTiesToEven, &ignored);
3346 return getConstantFP(V, VT);
3350 // Canonicalize an UNDEF to the RHS, even over a constant.
3351 if (N1.getOpcode() == ISD::UNDEF) {
3352 if (isCommutativeBinOp(Opcode)) {
3356 case ISD::FP_ROUND_INREG:
3357 case ISD::SIGN_EXTEND_INREG:
3363 return N1; // fold op(undef, arg2) -> undef
3371 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3372 // For vectors, we can't easily build an all zero vector, just return
3379 // Fold a bunch of operators when the RHS is undef.
3380 if (N2.getOpcode() == ISD::UNDEF) {
3383 if (N1.getOpcode() == ISD::UNDEF)
3384 // Handle undef ^ undef -> 0 special case. This is a common
3386 return getConstant(0, VT);
3396 return N2; // fold op(arg1, undef) -> undef
3402 if (getTarget().Options.UnsafeFPMath)
3410 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3411 // For vectors, we can't easily build an all zero vector, just return
3416 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3417 // For vectors, we can't easily build an all one vector, just return
3425 // Memoize this node if possible.
3427 SDVTList VTs = getVTList(VT);
3428 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3429 if (VT != MVT::Glue) {
3430 SDValue Ops[] = {N1, N2};
3431 FoldingSetNodeID ID;
3432 AddNodeIDNode(ID, Opcode, VTs, Ops);
3434 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3436 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3437 return SDValue(E, 0);
3439 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3441 CSEMap.InsertNode(N, IP);
3444 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3447 AllNodes.push_back(N);
3451 return SDValue(N, 0);
3454 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3455 SDValue N1, SDValue N2, SDValue N3) {
3456 // Perform various simplifications.
3457 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3460 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3461 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3462 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3463 if (N1CFP && N2CFP && N3CFP) {
3464 APFloat V1 = N1CFP->getValueAPF();
3465 const APFloat &V2 = N2CFP->getValueAPF();
3466 const APFloat &V3 = N3CFP->getValueAPF();
3467 APFloat::opStatus s =
3468 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3469 if (s != APFloat::opInvalidOp)
3470 return getConstantFP(V1, VT);
3474 case ISD::CONCAT_VECTORS:
3475 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3476 // one big BUILD_VECTOR.
3477 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3478 N2.getOpcode() == ISD::BUILD_VECTOR &&
3479 N3.getOpcode() == ISD::BUILD_VECTOR) {
3480 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3481 N1.getNode()->op_end());
3482 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3483 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3484 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3488 // Use FoldSetCC to simplify SETCC's.
3489 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3490 if (Simp.getNode()) return Simp;
3495 if (N1C->getZExtValue())
3496 return N2; // select true, X, Y -> X
3497 return N3; // select false, X, Y -> Y
3500 if (N2 == N3) return N2; // select C, X, X -> X
3502 case ISD::VECTOR_SHUFFLE:
3503 llvm_unreachable("should use getVectorShuffle constructor!");
3504 case ISD::INSERT_SUBVECTOR: {
3506 if (VT.isSimple() && N1.getValueType().isSimple()
3507 && N2.getValueType().isSimple()) {
3508 assert(VT.isVector() && N1.getValueType().isVector() &&
3509 N2.getValueType().isVector() &&
3510 "Insert subvector VTs must be a vectors");
3511 assert(VT == N1.getValueType() &&
3512 "Dest and insert subvector source types must match!");
3513 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3514 "Insert subvector must be from smaller vector to larger vector!");
3515 if (isa<ConstantSDNode>(Index.getNode())) {
3516 assert((N2.getValueType().getVectorNumElements() +
3517 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3518 <= VT.getVectorNumElements())
3519 && "Insert subvector overflow!");
3522 // Trivial insertion.
3523 if (VT.getSimpleVT() == N2.getSimpleValueType())
3529 // Fold bit_convert nodes from a type to themselves.
3530 if (N1.getValueType() == VT)
3535 // Memoize node if it doesn't produce a flag.
3537 SDVTList VTs = getVTList(VT);
3538 if (VT != MVT::Glue) {
3539 SDValue Ops[] = { N1, N2, N3 };
3540 FoldingSetNodeID ID;
3541 AddNodeIDNode(ID, Opcode, VTs, Ops);
3543 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3544 return SDValue(E, 0);
3546 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3547 DL.getDebugLoc(), VTs, N1, N2, N3);
3548 CSEMap.InsertNode(N, IP);
3550 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3551 DL.getDebugLoc(), VTs, N1, N2, N3);
3554 AllNodes.push_back(N);
3558 return SDValue(N, 0);
3561 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3562 SDValue N1, SDValue N2, SDValue N3,
3564 SDValue Ops[] = { N1, N2, N3, N4 };
3565 return getNode(Opcode, DL, VT, Ops);
3568 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3569 SDValue N1, SDValue N2, SDValue N3,
3570 SDValue N4, SDValue N5) {
3571 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3572 return getNode(Opcode, DL, VT, Ops);
3575 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3576 /// the incoming stack arguments to be loaded from the stack.
3577 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3578 SmallVector<SDValue, 8> ArgChains;
3580 // Include the original chain at the beginning of the list. When this is
3581 // used by target LowerCall hooks, this helps legalize find the
3582 // CALLSEQ_BEGIN node.
3583 ArgChains.push_back(Chain);
3585 // Add a chain value for each stack argument.
3586 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3587 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3588 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3589 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3590 if (FI->getIndex() < 0)
3591 ArgChains.push_back(SDValue(L, 1));
3593 // Build a tokenfactor for all the chains.
3594 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3597 /// getMemsetValue - Vectorized representation of the memset value
3599 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3601 assert(Value.getOpcode() != ISD::UNDEF);
3603 unsigned NumBits = VT.getScalarType().getSizeInBits();
3604 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3605 assert(C->getAPIntValue().getBitWidth() == 8);
3606 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3608 return DAG.getConstant(Val, VT);
3609 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3612 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3614 // Use a multiplication with 0x010101... to extend the input to the
3616 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3617 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3623 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3624 /// used when a memcpy is turned into a memset when the source is a constant
3626 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3627 const TargetLowering &TLI, StringRef Str) {
3628 // Handle vector with all elements zero.
3631 return DAG.getConstant(0, VT);
3632 else if (VT == MVT::f32 || VT == MVT::f64)
3633 return DAG.getConstantFP(0.0, VT);
3634 else if (VT.isVector()) {
3635 unsigned NumElts = VT.getVectorNumElements();
3636 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3637 return DAG.getNode(ISD::BITCAST, dl, VT,
3638 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3641 llvm_unreachable("Expected type!");
3644 assert(!VT.isVector() && "Can't handle vector type here!");
3645 unsigned NumVTBits = VT.getSizeInBits();
3646 unsigned NumVTBytes = NumVTBits / 8;
3647 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3649 APInt Val(NumVTBits, 0);
3650 if (TLI.isLittleEndian()) {
3651 for (unsigned i = 0; i != NumBytes; ++i)
3652 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3654 for (unsigned i = 0; i != NumBytes; ++i)
3655 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3658 // If the "cost" of materializing the integer immediate is less than the cost
3659 // of a load, then it is cost effective to turn the load into the immediate.
3660 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3661 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3662 return DAG.getConstant(Val, VT);
3663 return SDValue(nullptr, 0);
3666 /// getMemBasePlusOffset - Returns base and offset node for the
3668 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3669 SelectionDAG &DAG) {
3670 EVT VT = Base.getValueType();
3671 return DAG.getNode(ISD::ADD, dl,
3672 VT, Base, DAG.getConstant(Offset, VT));
3675 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3677 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3678 unsigned SrcDelta = 0;
3679 GlobalAddressSDNode *G = nullptr;
3680 if (Src.getOpcode() == ISD::GlobalAddress)
3681 G = cast<GlobalAddressSDNode>(Src);
3682 else if (Src.getOpcode() == ISD::ADD &&
3683 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3684 Src.getOperand(1).getOpcode() == ISD::Constant) {
3685 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3686 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3691 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3694 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3695 /// to replace the memset / memcpy. Return true if the number of memory ops
3696 /// is below the threshold. It returns the types of the sequence of
3697 /// memory ops to perform memset / memcpy by reference.
3698 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3699 unsigned Limit, uint64_t Size,
3700 unsigned DstAlign, unsigned SrcAlign,
3706 const TargetLowering &TLI) {
3707 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3708 "Expecting memcpy / memset source to meet alignment requirement!");
3709 // If 'SrcAlign' is zero, that means the memory operation does not need to
3710 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3711 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3712 // is the specified alignment of the memory operation. If it is zero, that
3713 // means it's possible to change the alignment of the destination.
3714 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3715 // not need to be loaded.
3716 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3717 IsMemset, ZeroMemset, MemcpyStrSrc,
3718 DAG.getMachineFunction());
3720 if (VT == MVT::Other) {
3722 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3723 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3724 VT = TLI.getPointerTy();
3726 switch (DstAlign & 7) {
3727 case 0: VT = MVT::i64; break;
3728 case 4: VT = MVT::i32; break;
3729 case 2: VT = MVT::i16; break;
3730 default: VT = MVT::i8; break;
3735 while (!TLI.isTypeLegal(LVT))
3736 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3737 assert(LVT.isInteger());
3743 unsigned NumMemOps = 0;
3745 unsigned VTSize = VT.getSizeInBits() / 8;
3746 while (VTSize > Size) {
3747 // For now, only use non-vector load / store's for the left-over pieces.
3752 if (VT.isVector() || VT.isFloatingPoint()) {
3753 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3754 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3755 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3757 else if (NewVT == MVT::i64 &&
3758 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3759 TLI.isSafeMemOpType(MVT::f64)) {
3760 // i64 is usually not legal on 32-bit targets, but f64 may be.
3768 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3769 if (NewVT == MVT::i8)
3771 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3773 NewVTSize = NewVT.getSizeInBits() / 8;
3775 // If the new VT cannot cover all of the remaining bits, then consider
3776 // issuing a (or a pair of) unaligned and overlapping load / store.
3777 // FIXME: Only does this for 64-bit or more since we don't have proper
3778 // cost model for unaligned load / store.
3781 if (NumMemOps && AllowOverlap &&
3782 VTSize >= 8 && NewVTSize < Size &&
3783 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3791 if (++NumMemOps > Limit)
3794 MemOps.push_back(VT);
3801 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3802 SDValue Chain, SDValue Dst,
3803 SDValue Src, uint64_t Size,
3804 unsigned Align, bool isVol,
3806 MachinePointerInfo DstPtrInfo,
3807 MachinePointerInfo SrcPtrInfo) {
3808 // Turn a memcpy of undef to nop.
3809 if (Src.getOpcode() == ISD::UNDEF)
3812 // Expand memcpy to a series of load and store ops if the size operand falls
3813 // below a certain threshold.
3814 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3815 // rather than maybe a humongous number of loads and stores.
3816 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3817 std::vector<EVT> MemOps;
3818 bool DstAlignCanChange = false;
3819 MachineFunction &MF = DAG.getMachineFunction();
3820 MachineFrameInfo *MFI = MF.getFrameInfo();
3822 MF.getFunction()->getAttributes().
3823 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3824 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3825 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3826 DstAlignCanChange = true;
3827 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3828 if (Align > SrcAlign)
3831 bool CopyFromStr = isMemSrcFromString(Src, Str);
3832 bool isZeroStr = CopyFromStr && Str.empty();
3833 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3835 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3836 (DstAlignCanChange ? 0 : Align),
3837 (isZeroStr ? 0 : SrcAlign),
3838 false, false, CopyFromStr, true, DAG, TLI))
3841 if (DstAlignCanChange) {
3842 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3843 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3845 // Don't promote to an alignment that would require dynamic stack
3847 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3848 if (!TRI->needsStackRealignment(MF))
3849 while (NewAlign > Align &&
3850 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3853 if (NewAlign > Align) {
3854 // Give the stack frame object a larger alignment if needed.
3855 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3856 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3861 SmallVector<SDValue, 8> OutChains;
3862 unsigned NumMemOps = MemOps.size();
3863 uint64_t SrcOff = 0, DstOff = 0;
3864 for (unsigned i = 0; i != NumMemOps; ++i) {
3866 unsigned VTSize = VT.getSizeInBits() / 8;
3867 SDValue Value, Store;
3869 if (VTSize > Size) {
3870 // Issuing an unaligned load / store pair that overlaps with the previous
3871 // pair. Adjust the offset accordingly.
3872 assert(i == NumMemOps-1 && i != 0);
3873 SrcOff -= VTSize - Size;
3874 DstOff -= VTSize - Size;
3878 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3879 // It's unlikely a store of a vector immediate can be done in a single
3880 // instruction. It would require a load from a constantpool first.
3881 // We only handle zero vectors here.
3882 // FIXME: Handle other cases where store of vector immediate is done in
3883 // a single instruction.
3884 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3885 if (Value.getNode())
3886 Store = DAG.getStore(Chain, dl, Value,
3887 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3888 DstPtrInfo.getWithOffset(DstOff), isVol,
3892 if (!Store.getNode()) {
3893 // The type might not be legal for the target. This should only happen
3894 // if the type is smaller than a legal type, as on PPC, so the right
3895 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3896 // to Load/Store if NVT==VT.
3897 // FIXME does the case above also need this?
3898 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3899 assert(NVT.bitsGE(VT));
3900 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3901 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3902 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3903 MinAlign(SrcAlign, SrcOff));
3904 Store = DAG.getTruncStore(Chain, dl, Value,
3905 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3906 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3909 OutChains.push_back(Store);
3915 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3918 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3919 SDValue Chain, SDValue Dst,
3920 SDValue Src, uint64_t Size,
3921 unsigned Align, bool isVol,
3923 MachinePointerInfo DstPtrInfo,
3924 MachinePointerInfo SrcPtrInfo) {
3925 // Turn a memmove of undef to nop.
3926 if (Src.getOpcode() == ISD::UNDEF)
3929 // Expand memmove to a series of load and store ops if the size operand falls
3930 // below a certain threshold.
3931 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3932 std::vector<EVT> MemOps;
3933 bool DstAlignCanChange = false;
3934 MachineFunction &MF = DAG.getMachineFunction();
3935 MachineFrameInfo *MFI = MF.getFrameInfo();
3936 bool OptSize = MF.getFunction()->getAttributes().
3937 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3938 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3939 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3940 DstAlignCanChange = true;
3941 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3942 if (Align > SrcAlign)
3944 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3946 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3947 (DstAlignCanChange ? 0 : Align), SrcAlign,
3948 false, false, false, false, DAG, TLI))
3951 if (DstAlignCanChange) {
3952 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3953 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3954 if (NewAlign > Align) {
3955 // Give the stack frame object a larger alignment if needed.
3956 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3957 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3962 uint64_t SrcOff = 0, DstOff = 0;
3963 SmallVector<SDValue, 8> LoadValues;
3964 SmallVector<SDValue, 8> LoadChains;
3965 SmallVector<SDValue, 8> OutChains;
3966 unsigned NumMemOps = MemOps.size();
3967 for (unsigned i = 0; i < NumMemOps; i++) {
3969 unsigned VTSize = VT.getSizeInBits() / 8;
3972 Value = DAG.getLoad(VT, dl, Chain,
3973 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3974 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3975 false, false, SrcAlign);
3976 LoadValues.push_back(Value);
3977 LoadChains.push_back(Value.getValue(1));
3980 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3982 for (unsigned i = 0; i < NumMemOps; i++) {
3984 unsigned VTSize = VT.getSizeInBits() / 8;
3987 Store = DAG.getStore(Chain, dl, LoadValues[i],
3988 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3989 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3990 OutChains.push_back(Store);
3994 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3997 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4000 /// \param DAG Selection DAG where lowered code is placed.
4001 /// \param dl Link to corresponding IR location.
4002 /// \param Chain Control flow dependency.
4003 /// \param Dst Pointer to destination memory location.
4004 /// \param Src Value of byte to write into the memory.
4005 /// \param Size Number of bytes to write.
4006 /// \param Align Alignment of the destination in bytes.
4007 /// \param isVol True if destination is volatile.
4008 /// \param DstPtrInfo IR information on the memory pointer.
4009 /// \returns New head in the control flow, if lowering was successful, empty
4010 /// SDValue otherwise.
4012 /// The function tries to replace 'llvm.memset' intrinsic with several store
4013 /// operations and value calculation code. This is usually profitable for small
4015 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4016 SDValue Chain, SDValue Dst,
4017 SDValue Src, uint64_t Size,
4018 unsigned Align, bool isVol,
4019 MachinePointerInfo DstPtrInfo) {
4020 // Turn a memset of undef to nop.
4021 if (Src.getOpcode() == ISD::UNDEF)
4024 // Expand memset to a series of load/store ops if the size operand
4025 // falls below a certain threshold.
4026 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4027 std::vector<EVT> MemOps;
4028 bool DstAlignCanChange = false;
4029 MachineFunction &MF = DAG.getMachineFunction();
4030 MachineFrameInfo *MFI = MF.getFrameInfo();
4031 bool OptSize = MF.getFunction()->getAttributes().
4032 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4033 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4034 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4035 DstAlignCanChange = true;
4037 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4038 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4039 Size, (DstAlignCanChange ? 0 : Align), 0,
4040 true, IsZeroVal, false, true, DAG, TLI))
4043 if (DstAlignCanChange) {
4044 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4045 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4046 if (NewAlign > Align) {
4047 // Give the stack frame object a larger alignment if needed.
4048 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4049 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4054 SmallVector<SDValue, 8> OutChains;
4055 uint64_t DstOff = 0;
4056 unsigned NumMemOps = MemOps.size();
4058 // Find the largest store and generate the bit pattern for it.
4059 EVT LargestVT = MemOps[0];
4060 for (unsigned i = 1; i < NumMemOps; i++)
4061 if (MemOps[i].bitsGT(LargestVT))
4062 LargestVT = MemOps[i];
4063 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4065 for (unsigned i = 0; i < NumMemOps; i++) {
4067 unsigned VTSize = VT.getSizeInBits() / 8;
4068 if (VTSize > Size) {
4069 // Issuing an unaligned load / store pair that overlaps with the previous
4070 // pair. Adjust the offset accordingly.
4071 assert(i == NumMemOps-1 && i != 0);
4072 DstOff -= VTSize - Size;
4075 // If this store is smaller than the largest store see whether we can get
4076 // the smaller value for free with a truncate.
4077 SDValue Value = MemSetValue;
4078 if (VT.bitsLT(LargestVT)) {
4079 if (!LargestVT.isVector() && !VT.isVector() &&
4080 TLI.isTruncateFree(LargestVT, VT))
4081 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4083 Value = getMemsetValue(Src, VT, DAG, dl);
4085 assert(Value.getValueType() == VT && "Value with wrong type.");
4086 SDValue Store = DAG.getStore(Chain, dl, Value,
4087 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4088 DstPtrInfo.getWithOffset(DstOff),
4089 isVol, false, Align);
4090 OutChains.push_back(Store);
4091 DstOff += VT.getSizeInBits() / 8;
4095 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4098 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4099 SDValue Src, SDValue Size,
4100 unsigned Align, bool isVol, bool AlwaysInline,
4101 MachinePointerInfo DstPtrInfo,
4102 MachinePointerInfo SrcPtrInfo) {
4103 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4105 // Check to see if we should lower the memcpy to loads and stores first.
4106 // For cases within the target-specified limits, this is the best choice.
4107 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4109 // Memcpy with size zero? Just return the original chain.
4110 if (ConstantSize->isNullValue())
4113 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4114 ConstantSize->getZExtValue(),Align,
4115 isVol, false, DstPtrInfo, SrcPtrInfo);
4116 if (Result.getNode())
4120 // Then check to see if we should lower the memcpy with target-specific
4121 // code. If the target chooses to do this, this is the next best.
4123 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4124 isVol, AlwaysInline,
4125 DstPtrInfo, SrcPtrInfo);
4126 if (Result.getNode())
4129 // If we really need inline code and the target declined to provide it,
4130 // use a (potentially long) sequence of loads and stores.
4132 assert(ConstantSize && "AlwaysInline requires a constant size!");
4133 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4134 ConstantSize->getZExtValue(), Align, isVol,
4135 true, DstPtrInfo, SrcPtrInfo);
4138 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4139 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4140 // respect volatile, so they may do things like read or write memory
4141 // beyond the given memory regions. But fixing this isn't easy, and most
4142 // people don't care.
4144 const TargetLowering *TLI = TM.getTargetLowering();
4146 // Emit a library call.
4147 TargetLowering::ArgListTy Args;
4148 TargetLowering::ArgListEntry Entry;
4149 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4150 Entry.Node = Dst; Args.push_back(Entry);
4151 Entry.Node = Src; Args.push_back(Entry);
4152 Entry.Node = Size; Args.push_back(Entry);
4153 // FIXME: pass in SDLoc
4154 TargetLowering::CallLoweringInfo CLI(*this);
4155 CLI.setDebugLoc(dl).setChain(Chain)
4156 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4157 Type::getVoidTy(*getContext()),
4158 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4159 TLI->getPointerTy()), &Args, 0)
4160 .setDiscardResult();
4161 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4163 return CallResult.second;
4166 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4167 SDValue Src, SDValue Size,
4168 unsigned Align, bool isVol,
4169 MachinePointerInfo DstPtrInfo,
4170 MachinePointerInfo SrcPtrInfo) {
4171 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4173 // Check to see if we should lower the memmove to loads and stores first.
4174 // For cases within the target-specified limits, this is the best choice.
4175 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4177 // Memmove with size zero? Just return the original chain.
4178 if (ConstantSize->isNullValue())
4182 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4183 ConstantSize->getZExtValue(), Align, isVol,
4184 false, DstPtrInfo, SrcPtrInfo);
4185 if (Result.getNode())
4189 // Then check to see if we should lower the memmove with target-specific
4190 // code. If the target chooses to do this, this is the next best.
4192 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4193 DstPtrInfo, SrcPtrInfo);
4194 if (Result.getNode())
4197 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4198 // not be safe. See memcpy above for more details.
4200 const TargetLowering *TLI = TM.getTargetLowering();
4202 // Emit a library call.
4203 TargetLowering::ArgListTy Args;
4204 TargetLowering::ArgListEntry Entry;
4205 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4206 Entry.Node = Dst; Args.push_back(Entry);
4207 Entry.Node = Src; Args.push_back(Entry);
4208 Entry.Node = Size; Args.push_back(Entry);
4209 // FIXME: pass in SDLoc
4210 TargetLowering::CallLoweringInfo CLI(*this);
4211 CLI.setDebugLoc(dl).setChain(Chain)
4212 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4213 Type::getVoidTy(*getContext()),
4214 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4215 TLI->getPointerTy()), &Args, 0)
4216 .setDiscardResult();
4217 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4219 return CallResult.second;
4222 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4223 SDValue Src, SDValue Size,
4224 unsigned Align, bool isVol,
4225 MachinePointerInfo DstPtrInfo) {
4226 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4228 // Check to see if we should lower the memset to stores first.
4229 // For cases within the target-specified limits, this is the best choice.
4230 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4232 // Memset with size zero? Just return the original chain.
4233 if (ConstantSize->isNullValue())
4237 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4238 Align, isVol, DstPtrInfo);
4240 if (Result.getNode())
4244 // Then check to see if we should lower the memset with target-specific
4245 // code. If the target chooses to do this, this is the next best.
4247 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4249 if (Result.getNode())
4252 // Emit a library call.
4253 const TargetLowering *TLI = TM.getTargetLowering();
4254 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4255 TargetLowering::ArgListTy Args;
4256 TargetLowering::ArgListEntry Entry;
4257 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4258 Args.push_back(Entry);
4259 // Extend or truncate the argument to be an i32 value for the call.
4260 if (Src.getValueType().bitsGT(MVT::i32))
4261 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4263 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4265 Entry.Ty = Type::getInt32Ty(*getContext());
4266 Entry.isSExt = true;
4267 Args.push_back(Entry);
4269 Entry.Ty = IntPtrTy;
4270 Entry.isSExt = false;
4271 Args.push_back(Entry);
4273 // FIXME: pass in SDLoc
4274 TargetLowering::CallLoweringInfo CLI(*this);
4275 CLI.setDebugLoc(dl).setChain(Chain)
4276 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4277 Type::getVoidTy(*getContext()),
4278 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4279 TLI->getPointerTy()), &Args, 0)
4280 .setDiscardResult();
4282 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4283 return CallResult.second;
4286 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4287 SDVTList VTList, ArrayRef<SDValue> Ops,
4288 MachineMemOperand *MMO,
4289 AtomicOrdering SuccessOrdering,
4290 AtomicOrdering FailureOrdering,
4291 SynchronizationScope SynchScope) {
4292 FoldingSetNodeID ID;
4293 ID.AddInteger(MemVT.getRawBits());
4294 AddNodeIDNode(ID, Opcode, VTList, Ops);
4295 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4297 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4298 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4299 return SDValue(E, 0);
4302 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4303 // SDNode doesn't have access to it. This memory will be "leaked" when
4304 // the node is deallocated, but recovered when the allocator is released.
4305 // If the number of operands is less than 5 we use AtomicSDNode's internal
4307 unsigned NumOps = Ops.size();
4308 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4311 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4312 dl.getDebugLoc(), VTList, MemVT,
4313 Ops.data(), DynOps, NumOps, MMO,
4314 SuccessOrdering, FailureOrdering,
4316 CSEMap.InsertNode(N, IP);
4317 AllNodes.push_back(N);
4318 return SDValue(N, 0);
4321 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4322 SDVTList VTList, ArrayRef<SDValue> Ops,
4323 MachineMemOperand *MMO,
4324 AtomicOrdering Ordering,
4325 SynchronizationScope SynchScope) {
4326 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4327 Ordering, SynchScope);
4330 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4331 SDValue Chain, SDValue Ptr, SDValue Cmp,
4332 SDValue Swp, MachinePointerInfo PtrInfo,
4334 AtomicOrdering SuccessOrdering,
4335 AtomicOrdering FailureOrdering,
4336 SynchronizationScope SynchScope) {
4337 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4338 Alignment = getEVTAlignment(MemVT);
4340 MachineFunction &MF = getMachineFunction();
4342 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4343 // For now, atomics are considered to be volatile always.
4344 // FIXME: Volatile isn't really correct; we should keep track of atomic
4345 // orderings in the memoperand.
4346 unsigned Flags = MachineMemOperand::MOVolatile;
4347 if (Opcode != ISD::ATOMIC_STORE)
4348 Flags |= MachineMemOperand::MOLoad;
4349 if (Opcode != ISD::ATOMIC_LOAD)
4350 Flags |= MachineMemOperand::MOStore;
4352 MachineMemOperand *MMO =
4353 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4355 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4356 SuccessOrdering, FailureOrdering, SynchScope);
4359 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4361 SDValue Ptr, SDValue Cmp,
4362 SDValue Swp, MachineMemOperand *MMO,
4363 AtomicOrdering SuccessOrdering,
4364 AtomicOrdering FailureOrdering,
4365 SynchronizationScope SynchScope) {
4366 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4367 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4369 EVT VT = Cmp.getValueType();
4371 SDVTList VTs = getVTList(VT, MVT::Other);
4372 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4373 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4374 FailureOrdering, SynchScope);
4377 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4379 SDValue Ptr, SDValue Val,
4380 const Value* PtrVal,
4382 AtomicOrdering Ordering,
4383 SynchronizationScope SynchScope) {
4384 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4385 Alignment = getEVTAlignment(MemVT);
4387 MachineFunction &MF = getMachineFunction();
4388 // An atomic store does not load. An atomic load does not store.
4389 // (An atomicrmw obviously both loads and stores.)
4390 // For now, atomics are considered to be volatile always, and they are
4392 // FIXME: Volatile isn't really correct; we should keep track of atomic
4393 // orderings in the memoperand.
4394 unsigned Flags = MachineMemOperand::MOVolatile;
4395 if (Opcode != ISD::ATOMIC_STORE)
4396 Flags |= MachineMemOperand::MOLoad;
4397 if (Opcode != ISD::ATOMIC_LOAD)
4398 Flags |= MachineMemOperand::MOStore;
4400 MachineMemOperand *MMO =
4401 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4402 MemVT.getStoreSize(), Alignment);
4404 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4405 Ordering, SynchScope);
4408 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4410 SDValue Ptr, SDValue Val,
4411 MachineMemOperand *MMO,
4412 AtomicOrdering Ordering,
4413 SynchronizationScope SynchScope) {
4414 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4415 Opcode == ISD::ATOMIC_LOAD_SUB ||
4416 Opcode == ISD::ATOMIC_LOAD_AND ||
4417 Opcode == ISD::ATOMIC_LOAD_OR ||
4418 Opcode == ISD::ATOMIC_LOAD_XOR ||
4419 Opcode == ISD::ATOMIC_LOAD_NAND ||
4420 Opcode == ISD::ATOMIC_LOAD_MIN ||
4421 Opcode == ISD::ATOMIC_LOAD_MAX ||
4422 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4423 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4424 Opcode == ISD::ATOMIC_SWAP ||
4425 Opcode == ISD::ATOMIC_STORE) &&
4426 "Invalid Atomic Op");
4428 EVT VT = Val.getValueType();
4430 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4431 getVTList(VT, MVT::Other);
4432 SDValue Ops[] = {Chain, Ptr, Val};
4433 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4436 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4437 EVT VT, SDValue Chain,
4439 MachineMemOperand *MMO,
4440 AtomicOrdering Ordering,
4441 SynchronizationScope SynchScope) {
4442 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4444 SDVTList VTs = getVTList(VT, MVT::Other);
4445 SDValue Ops[] = {Chain, Ptr};
4446 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4449 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4450 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4451 if (Ops.size() == 1)
4454 SmallVector<EVT, 4> VTs;
4455 VTs.reserve(Ops.size());
4456 for (unsigned i = 0; i < Ops.size(); ++i)
4457 VTs.push_back(Ops[i].getValueType());
4458 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4462 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4463 ArrayRef<SDValue> Ops,
4464 EVT MemVT, MachinePointerInfo PtrInfo,
4465 unsigned Align, bool Vol,
4466 bool ReadMem, bool WriteMem) {
4467 if (Align == 0) // Ensure that codegen never sees alignment 0
4468 Align = getEVTAlignment(MemVT);
4470 MachineFunction &MF = getMachineFunction();
4473 Flags |= MachineMemOperand::MOStore;
4475 Flags |= MachineMemOperand::MOLoad;
4477 Flags |= MachineMemOperand::MOVolatile;
4478 MachineMemOperand *MMO =
4479 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4481 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4485 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4486 ArrayRef<SDValue> Ops, EVT MemVT,
4487 MachineMemOperand *MMO) {
4488 assert((Opcode == ISD::INTRINSIC_VOID ||
4489 Opcode == ISD::INTRINSIC_W_CHAIN ||
4490 Opcode == ISD::PREFETCH ||
4491 Opcode == ISD::LIFETIME_START ||
4492 Opcode == ISD::LIFETIME_END ||
4493 (Opcode <= INT_MAX &&
4494 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4495 "Opcode is not a memory-accessing opcode!");
4497 // Memoize the node unless it returns a flag.
4498 MemIntrinsicSDNode *N;
4499 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4500 FoldingSetNodeID ID;
4501 AddNodeIDNode(ID, Opcode, VTList, Ops);
4502 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4504 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4505 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4506 return SDValue(E, 0);
4509 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4510 dl.getDebugLoc(), VTList, Ops,
4512 CSEMap.InsertNode(N, IP);
4514 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4515 dl.getDebugLoc(), VTList, Ops,
4518 AllNodes.push_back(N);
4519 return SDValue(N, 0);
4522 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4523 /// MachinePointerInfo record from it. This is particularly useful because the
4524 /// code generator has many cases where it doesn't bother passing in a
4525 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4526 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4527 // If this is FI+Offset, we can model it.
4528 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4529 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4531 // If this is (FI+Offset1)+Offset2, we can model it.
4532 if (Ptr.getOpcode() != ISD::ADD ||
4533 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4534 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4535 return MachinePointerInfo();
4537 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4538 return MachinePointerInfo::getFixedStack(FI, Offset+
4539 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4542 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4543 /// MachinePointerInfo record from it. This is particularly useful because the
4544 /// code generator has many cases where it doesn't bother passing in a
4545 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4546 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4547 // If the 'Offset' value isn't a constant, we can't handle this.
4548 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4549 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4550 if (OffsetOp.getOpcode() == ISD::UNDEF)
4551 return InferPointerInfo(Ptr);
4552 return MachinePointerInfo();
4557 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4558 EVT VT, SDLoc dl, SDValue Chain,
4559 SDValue Ptr, SDValue Offset,
4560 MachinePointerInfo PtrInfo, EVT MemVT,
4561 bool isVolatile, bool isNonTemporal, bool isInvariant,
4562 unsigned Alignment, const MDNode *TBAAInfo,
4563 const MDNode *Ranges) {
4564 assert(Chain.getValueType() == MVT::Other &&
4565 "Invalid chain type");
4566 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4567 Alignment = getEVTAlignment(VT);
4569 unsigned Flags = MachineMemOperand::MOLoad;
4571 Flags |= MachineMemOperand::MOVolatile;
4573 Flags |= MachineMemOperand::MONonTemporal;
4575 Flags |= MachineMemOperand::MOInvariant;
4577 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4579 if (PtrInfo.V.isNull())
4580 PtrInfo = InferPointerInfo(Ptr, Offset);
4582 MachineFunction &MF = getMachineFunction();
4583 MachineMemOperand *MMO =
4584 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4586 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4590 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4591 EVT VT, SDLoc dl, SDValue Chain,
4592 SDValue Ptr, SDValue Offset, EVT MemVT,
4593 MachineMemOperand *MMO) {
4595 ExtType = ISD::NON_EXTLOAD;
4596 } else if (ExtType == ISD::NON_EXTLOAD) {
4597 assert(VT == MemVT && "Non-extending load from different memory type!");
4600 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4601 "Should only be an extending load, not truncating!");
4602 assert(VT.isInteger() == MemVT.isInteger() &&
4603 "Cannot convert from FP to Int or Int -> FP!");
4604 assert(VT.isVector() == MemVT.isVector() &&
4605 "Cannot use trunc store to convert to or from a vector!");
4606 assert((!VT.isVector() ||
4607 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4608 "Cannot use trunc store to change the number of vector elements!");
4611 bool Indexed = AM != ISD::UNINDEXED;
4612 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4613 "Unindexed load with an offset!");
4615 SDVTList VTs = Indexed ?
4616 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4617 SDValue Ops[] = { Chain, Ptr, Offset };
4618 FoldingSetNodeID ID;
4619 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4620 ID.AddInteger(MemVT.getRawBits());
4621 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4622 MMO->isNonTemporal(),
4623 MMO->isInvariant()));
4624 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4627 cast<LoadSDNode>(E)->refineAlignment(MMO);
4628 return SDValue(E, 0);
4630 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4631 dl.getDebugLoc(), VTs, AM, ExtType,
4633 CSEMap.InsertNode(N, IP);
4634 AllNodes.push_back(N);
4635 return SDValue(N, 0);
4638 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4639 SDValue Chain, SDValue Ptr,
4640 MachinePointerInfo PtrInfo,
4641 bool isVolatile, bool isNonTemporal,
4642 bool isInvariant, unsigned Alignment,
4643 const MDNode *TBAAInfo,
4644 const MDNode *Ranges) {
4645 SDValue Undef = getUNDEF(Ptr.getValueType());
4646 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4647 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4651 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4652 SDValue Chain, SDValue Ptr,
4653 MachineMemOperand *MMO) {
4654 SDValue Undef = getUNDEF(Ptr.getValueType());
4655 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4659 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4660 SDValue Chain, SDValue Ptr,
4661 MachinePointerInfo PtrInfo, EVT MemVT,
4662 bool isVolatile, bool isNonTemporal,
4663 unsigned Alignment, const MDNode *TBAAInfo) {
4664 SDValue Undef = getUNDEF(Ptr.getValueType());
4665 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4666 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4671 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4672 SDValue Chain, SDValue Ptr, EVT MemVT,
4673 MachineMemOperand *MMO) {
4674 SDValue Undef = getUNDEF(Ptr.getValueType());
4675 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4680 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4681 SDValue Offset, ISD::MemIndexedMode AM) {
4682 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4683 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4684 "Load is already a indexed load!");
4685 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4686 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4687 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4688 false, LD->getAlignment());
4691 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4692 SDValue Ptr, MachinePointerInfo PtrInfo,
4693 bool isVolatile, bool isNonTemporal,
4694 unsigned Alignment, const MDNode *TBAAInfo) {
4695 assert(Chain.getValueType() == MVT::Other &&
4696 "Invalid chain type");
4697 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4698 Alignment = getEVTAlignment(Val.getValueType());
4700 unsigned Flags = MachineMemOperand::MOStore;
4702 Flags |= MachineMemOperand::MOVolatile;
4704 Flags |= MachineMemOperand::MONonTemporal;
4706 if (PtrInfo.V.isNull())
4707 PtrInfo = InferPointerInfo(Ptr);
4709 MachineFunction &MF = getMachineFunction();
4710 MachineMemOperand *MMO =
4711 MF.getMachineMemOperand(PtrInfo, Flags,
4712 Val.getValueType().getStoreSize(), Alignment,
4715 return getStore(Chain, dl, Val, Ptr, MMO);
4718 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4719 SDValue Ptr, MachineMemOperand *MMO) {
4720 assert(Chain.getValueType() == MVT::Other &&
4721 "Invalid chain type");
4722 EVT VT = Val.getValueType();
4723 SDVTList VTs = getVTList(MVT::Other);
4724 SDValue Undef = getUNDEF(Ptr.getValueType());
4725 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4726 FoldingSetNodeID ID;
4727 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4728 ID.AddInteger(VT.getRawBits());
4729 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4730 MMO->isNonTemporal(), MMO->isInvariant()));
4731 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4733 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4734 cast<StoreSDNode>(E)->refineAlignment(MMO);
4735 return SDValue(E, 0);
4737 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4738 dl.getDebugLoc(), VTs,
4739 ISD::UNINDEXED, false, VT, MMO);
4740 CSEMap.InsertNode(N, IP);
4741 AllNodes.push_back(N);
4742 return SDValue(N, 0);
4745 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4746 SDValue Ptr, MachinePointerInfo PtrInfo,
4747 EVT SVT,bool isVolatile, bool isNonTemporal,
4749 const MDNode *TBAAInfo) {
4750 assert(Chain.getValueType() == MVT::Other &&
4751 "Invalid chain type");
4752 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4753 Alignment = getEVTAlignment(SVT);
4755 unsigned Flags = MachineMemOperand::MOStore;
4757 Flags |= MachineMemOperand::MOVolatile;
4759 Flags |= MachineMemOperand::MONonTemporal;
4761 if (PtrInfo.V.isNull())
4762 PtrInfo = InferPointerInfo(Ptr);
4764 MachineFunction &MF = getMachineFunction();
4765 MachineMemOperand *MMO =
4766 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4769 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4772 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4773 SDValue Ptr, EVT SVT,
4774 MachineMemOperand *MMO) {
4775 EVT VT = Val.getValueType();
4777 assert(Chain.getValueType() == MVT::Other &&
4778 "Invalid chain type");
4780 return getStore(Chain, dl, Val, Ptr, MMO);
4782 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4783 "Should only be a truncating store, not extending!");
4784 assert(VT.isInteger() == SVT.isInteger() &&
4785 "Can't do FP-INT conversion!");
4786 assert(VT.isVector() == SVT.isVector() &&
4787 "Cannot use trunc store to convert to or from a vector!");
4788 assert((!VT.isVector() ||
4789 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4790 "Cannot use trunc store to change the number of vector elements!");
4792 SDVTList VTs = getVTList(MVT::Other);
4793 SDValue Undef = getUNDEF(Ptr.getValueType());
4794 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4795 FoldingSetNodeID ID;
4796 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4797 ID.AddInteger(SVT.getRawBits());
4798 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4799 MMO->isNonTemporal(), MMO->isInvariant()));
4800 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4802 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4803 cast<StoreSDNode>(E)->refineAlignment(MMO);
4804 return SDValue(E, 0);
4806 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4807 dl.getDebugLoc(), VTs,
4808 ISD::UNINDEXED, true, SVT, MMO);
4809 CSEMap.InsertNode(N, IP);
4810 AllNodes.push_back(N);
4811 return SDValue(N, 0);
4815 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4816 SDValue Offset, ISD::MemIndexedMode AM) {
4817 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4818 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4819 "Store is already a indexed store!");
4820 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4821 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4822 FoldingSetNodeID ID;
4823 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4824 ID.AddInteger(ST->getMemoryVT().getRawBits());
4825 ID.AddInteger(ST->getRawSubclassData());
4826 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4828 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4829 return SDValue(E, 0);
4831 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4832 dl.getDebugLoc(), VTs, AM,
4833 ST->isTruncatingStore(),
4835 ST->getMemOperand());
4836 CSEMap.InsertNode(N, IP);
4837 AllNodes.push_back(N);
4838 return SDValue(N, 0);
4841 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4842 SDValue Chain, SDValue Ptr,
4845 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4846 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4849 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4850 ArrayRef<SDUse> Ops) {
4851 switch (Ops.size()) {
4852 case 0: return getNode(Opcode, DL, VT);
4853 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4854 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4855 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4859 // Copy from an SDUse array into an SDValue array for use with
4860 // the regular getNode logic.
4861 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4862 return getNode(Opcode, DL, VT, NewOps);
4865 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4866 ArrayRef<SDValue> Ops) {
4867 unsigned NumOps = Ops.size();
4869 case 0: return getNode(Opcode, DL, VT);
4870 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4871 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4872 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4878 case ISD::SELECT_CC: {
4879 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4880 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4881 "LHS and RHS of condition must have same type!");
4882 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4883 "True and False arms of SelectCC must have same type!");
4884 assert(Ops[2].getValueType() == VT &&
4885 "select_cc node must be of same type as true and false value!");
4889 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4890 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4891 "LHS/RHS of comparison should match types!");
4898 SDVTList VTs = getVTList(VT);
4900 if (VT != MVT::Glue) {
4901 FoldingSetNodeID ID;
4902 AddNodeIDNode(ID, Opcode, VTs, Ops);
4905 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4906 return SDValue(E, 0);
4908 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4910 CSEMap.InsertNode(N, IP);
4912 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4916 AllNodes.push_back(N);
4920 return SDValue(N, 0);
4923 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4924 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4925 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4928 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4929 ArrayRef<SDValue> Ops) {
4930 if (VTList.NumVTs == 1)
4931 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4935 // FIXME: figure out how to safely handle things like
4936 // int foo(int x) { return 1 << (x & 255); }
4937 // int bar() { return foo(256); }
4938 case ISD::SRA_PARTS:
4939 case ISD::SRL_PARTS:
4940 case ISD::SHL_PARTS:
4941 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4942 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4943 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4944 else if (N3.getOpcode() == ISD::AND)
4945 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4946 // If the and is only masking out bits that cannot effect the shift,
4947 // eliminate the and.
4948 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4949 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4950 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4956 // Memoize the node unless it returns a flag.
4958 unsigned NumOps = Ops.size();
4959 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4960 FoldingSetNodeID ID;
4961 AddNodeIDNode(ID, Opcode, VTList, Ops);
4963 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4964 return SDValue(E, 0);
4967 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4968 DL.getDebugLoc(), VTList, Ops[0]);
4969 } else if (NumOps == 2) {
4970 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4971 DL.getDebugLoc(), VTList, Ops[0],
4973 } else if (NumOps == 3) {
4974 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4975 DL.getDebugLoc(), VTList, Ops[0],
4978 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4981 CSEMap.InsertNode(N, IP);
4984 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4985 DL.getDebugLoc(), VTList, Ops[0]);
4986 } else if (NumOps == 2) {
4987 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4988 DL.getDebugLoc(), VTList, Ops[0],
4990 } else if (NumOps == 3) {
4991 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4992 DL.getDebugLoc(), VTList, Ops[0],
4995 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4999 AllNodes.push_back(N);
5003 return SDValue(N, 0);
5006 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5007 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5010 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5012 SDValue Ops[] = { N1 };
5013 return getNode(Opcode, DL, VTList, Ops);
5016 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5017 SDValue N1, SDValue N2) {
5018 SDValue Ops[] = { N1, N2 };
5019 return getNode(Opcode, DL, VTList, Ops);
5022 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5023 SDValue N1, SDValue N2, SDValue N3) {
5024 SDValue Ops[] = { N1, N2, N3 };
5025 return getNode(Opcode, DL, VTList, Ops);
5028 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5029 SDValue N1, SDValue N2, SDValue N3,
5031 SDValue Ops[] = { N1, N2, N3, N4 };
5032 return getNode(Opcode, DL, VTList, Ops);
5035 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5036 SDValue N1, SDValue N2, SDValue N3,
5037 SDValue N4, SDValue N5) {
5038 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5039 return getNode(Opcode, DL, VTList, Ops);
5042 SDVTList SelectionDAG::getVTList(EVT VT) {
5043 return makeVTList(SDNode::getValueTypeList(VT), 1);
5046 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5047 FoldingSetNodeID ID;
5049 ID.AddInteger(VT1.getRawBits());
5050 ID.AddInteger(VT2.getRawBits());
5053 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5055 EVT *Array = Allocator.Allocate<EVT>(2);
5058 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5059 VTListMap.InsertNode(Result, IP);
5061 return Result->getSDVTList();
5064 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5065 FoldingSetNodeID ID;
5067 ID.AddInteger(VT1.getRawBits());
5068 ID.AddInteger(VT2.getRawBits());
5069 ID.AddInteger(VT3.getRawBits());
5072 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5074 EVT *Array = Allocator.Allocate<EVT>(3);
5078 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5079 VTListMap.InsertNode(Result, IP);
5081 return Result->getSDVTList();
5084 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5085 FoldingSetNodeID ID;
5087 ID.AddInteger(VT1.getRawBits());
5088 ID.AddInteger(VT2.getRawBits());
5089 ID.AddInteger(VT3.getRawBits());
5090 ID.AddInteger(VT4.getRawBits());
5093 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5095 EVT *Array = Allocator.Allocate<EVT>(4);
5100 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5101 VTListMap.InsertNode(Result, IP);
5103 return Result->getSDVTList();
5106 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5107 unsigned NumVTs = VTs.size();
5108 FoldingSetNodeID ID;
5109 ID.AddInteger(NumVTs);
5110 for (unsigned index = 0; index < NumVTs; index++) {
5111 ID.AddInteger(VTs[index].getRawBits());
5115 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5117 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5118 std::copy(VTs.begin(), VTs.end(), Array);
5119 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5120 VTListMap.InsertNode(Result, IP);
5122 return Result->getSDVTList();
5126 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5127 /// specified operands. If the resultant node already exists in the DAG,
5128 /// this does not modify the specified node, instead it returns the node that
5129 /// already exists. If the resultant node does not exist in the DAG, the
5130 /// input node is returned. As a degenerate case, if you specify the same
5131 /// input operands as the node already has, the input node is returned.
5132 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5133 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5135 // Check to see if there is no change.
5136 if (Op == N->getOperand(0)) return N;
5138 // See if the modified node already exists.
5139 void *InsertPos = nullptr;
5140 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5143 // Nope it doesn't. Remove the node from its current place in the maps.
5145 if (!RemoveNodeFromCSEMaps(N))
5146 InsertPos = nullptr;
5148 // Now we update the operands.
5149 N->OperandList[0].set(Op);
5151 // If this gets put into a CSE map, add it.
5152 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5156 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5157 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5159 // Check to see if there is no change.
5160 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5161 return N; // No operands changed, just return the input node.
5163 // See if the modified node already exists.
5164 void *InsertPos = nullptr;
5165 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5168 // Nope it doesn't. Remove the node from its current place in the maps.
5170 if (!RemoveNodeFromCSEMaps(N))
5171 InsertPos = nullptr;
5173 // Now we update the operands.
5174 if (N->OperandList[0] != Op1)
5175 N->OperandList[0].set(Op1);
5176 if (N->OperandList[1] != Op2)
5177 N->OperandList[1].set(Op2);
5179 // If this gets put into a CSE map, add it.
5180 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5184 SDNode *SelectionDAG::
5185 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5186 SDValue Ops[] = { Op1, Op2, Op3 };
5187 return UpdateNodeOperands(N, Ops);
5190 SDNode *SelectionDAG::
5191 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5192 SDValue Op3, SDValue Op4) {
5193 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5194 return UpdateNodeOperands(N, Ops);
5197 SDNode *SelectionDAG::
5198 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5199 SDValue Op3, SDValue Op4, SDValue Op5) {
5200 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5201 return UpdateNodeOperands(N, Ops);
5204 SDNode *SelectionDAG::
5205 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5206 unsigned NumOps = Ops.size();
5207 assert(N->getNumOperands() == NumOps &&
5208 "Update with wrong number of operands");
5210 // Check to see if there is no change.
5211 bool AnyChange = false;
5212 for (unsigned i = 0; i != NumOps; ++i) {
5213 if (Ops[i] != N->getOperand(i)) {
5219 // No operands changed, just return the input node.
5220 if (!AnyChange) return N;
5222 // See if the modified node already exists.
5223 void *InsertPos = nullptr;
5224 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5227 // Nope it doesn't. Remove the node from its current place in the maps.
5229 if (!RemoveNodeFromCSEMaps(N))
5230 InsertPos = nullptr;
5232 // Now we update the operands.
5233 for (unsigned i = 0; i != NumOps; ++i)
5234 if (N->OperandList[i] != Ops[i])
5235 N->OperandList[i].set(Ops[i]);
5237 // If this gets put into a CSE map, add it.
5238 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5242 /// DropOperands - Release the operands and set this node to have
5244 void SDNode::DropOperands() {
5245 // Unlike the code in MorphNodeTo that does this, we don't need to
5246 // watch for dead nodes here.
5247 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5253 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5256 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 SDVTList VTs = getVTList(VT);
5259 return SelectNodeTo(N, MachineOpc, VTs, None);
5262 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5263 EVT VT, SDValue Op1) {
5264 SDVTList VTs = getVTList(VT);
5265 SDValue Ops[] = { Op1 };
5266 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 EVT VT, SDValue Op1,
5272 SDVTList VTs = getVTList(VT);
5273 SDValue Ops[] = { Op1, Op2 };
5274 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5277 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5278 EVT VT, SDValue Op1,
5279 SDValue Op2, SDValue Op3) {
5280 SDVTList VTs = getVTList(VT);
5281 SDValue Ops[] = { Op1, Op2, Op3 };
5282 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5285 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 EVT VT, ArrayRef<SDValue> Ops) {
5287 SDVTList VTs = getVTList(VT);
5288 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5291 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5292 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5293 SDVTList VTs = getVTList(VT1, VT2);
5294 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5297 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5299 SDVTList VTs = getVTList(VT1, VT2);
5300 return SelectNodeTo(N, MachineOpc, VTs, None);
5303 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5304 EVT VT1, EVT VT2, EVT VT3,
5305 ArrayRef<SDValue> Ops) {
5306 SDVTList VTs = getVTList(VT1, VT2, VT3);
5307 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5310 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5311 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5312 ArrayRef<SDValue> Ops) {
5313 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5314 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5317 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5320 SDVTList VTs = getVTList(VT1, VT2);
5321 SDValue Ops[] = { Op1 };
5322 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5325 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5327 SDValue Op1, SDValue Op2) {
5328 SDVTList VTs = getVTList(VT1, VT2);
5329 SDValue Ops[] = { Op1, Op2 };
5330 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5333 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5335 SDValue Op1, SDValue Op2,
5337 SDVTList VTs = getVTList(VT1, VT2);
5338 SDValue Ops[] = { Op1, Op2, Op3 };
5339 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5342 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5343 EVT VT1, EVT VT2, EVT VT3,
5344 SDValue Op1, SDValue Op2,
5346 SDVTList VTs = getVTList(VT1, VT2, VT3);
5347 SDValue Ops[] = { Op1, Op2, Op3 };
5348 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5351 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5352 SDVTList VTs,ArrayRef<SDValue> Ops) {
5353 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5354 // Reset the NodeID to -1.
5359 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5360 /// the line number information on the merged node since it is not possible to
5361 /// preserve the information that operation is associated with multiple lines.
5362 /// This will make the debugger working better at -O0, were there is a higher
5363 /// probability having other instructions associated with that line.
5365 /// For IROrder, we keep the smaller of the two
5366 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5367 DebugLoc NLoc = N->getDebugLoc();
5368 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5369 (OLoc.getDebugLoc() != NLoc)) {
5370 N->setDebugLoc(DebugLoc());
5372 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5373 N->setIROrder(Order);
5377 /// MorphNodeTo - This *mutates* the specified node to have the specified
5378 /// return type, opcode, and operands.
5380 /// Note that MorphNodeTo returns the resultant node. If there is already a
5381 /// node of the specified opcode and operands, it returns that node instead of
5382 /// the current one. Note that the SDLoc need not be the same.
5384 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5385 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5386 /// node, and because it doesn't require CSE recalculation for any of
5387 /// the node's users.
5389 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5390 SDVTList VTs, ArrayRef<SDValue> Ops) {
5391 unsigned NumOps = Ops.size();
5392 // If an identical node already exists, use it.
5394 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5395 FoldingSetNodeID ID;
5396 AddNodeIDNode(ID, Opc, VTs, Ops);
5397 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5398 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5401 if (!RemoveNodeFromCSEMaps(N))
5404 // Start the morphing.
5406 N->ValueList = VTs.VTs;
5407 N->NumValues = VTs.NumVTs;
5409 // Clear the operands list, updating used nodes to remove this from their
5410 // use list. Keep track of any operands that become dead as a result.
5411 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5412 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5414 SDNode *Used = Use.getNode();
5416 if (Used->use_empty())
5417 DeadNodeSet.insert(Used);
5420 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5421 // Initialize the memory references information.
5422 MN->setMemRefs(nullptr, nullptr);
5423 // If NumOps is larger than the # of operands we can have in a
5424 // MachineSDNode, reallocate the operand list.
5425 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5426 if (MN->OperandsNeedDelete)
5427 delete[] MN->OperandList;
5428 if (NumOps > array_lengthof(MN->LocalOperands))
5429 // We're creating a final node that will live unmorphed for the
5430 // remainder of the current SelectionDAG iteration, so we can allocate
5431 // the operands directly out of a pool with no recycling metadata.
5432 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5433 Ops.data(), NumOps);
5435 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5436 MN->OperandsNeedDelete = false;
5438 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5440 // If NumOps is larger than the # of operands we currently have, reallocate
5441 // the operand list.
5442 if (NumOps > N->NumOperands) {
5443 if (N->OperandsNeedDelete)
5444 delete[] N->OperandList;
5445 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5446 N->OperandsNeedDelete = true;
5448 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5451 // Delete any nodes that are still dead after adding the uses for the
5453 if (!DeadNodeSet.empty()) {
5454 SmallVector<SDNode *, 16> DeadNodes;
5455 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5456 E = DeadNodeSet.end(); I != E; ++I)
5457 if ((*I)->use_empty())
5458 DeadNodes.push_back(*I);
5459 RemoveDeadNodes(DeadNodes);
5463 CSEMap.InsertNode(N, IP); // Memoize the new node.
5468 /// getMachineNode - These are used for target selectors to create a new node
5469 /// with specified return type(s), MachineInstr opcode, and operands.
5471 /// Note that getMachineNode returns the resultant node. If there is already a
5472 /// node of the specified opcode and operands, it returns that node instead of
5473 /// the current one.
5475 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5476 SDVTList VTs = getVTList(VT);
5477 return getMachineNode(Opcode, dl, VTs, None);
5481 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5482 SDVTList VTs = getVTList(VT);
5483 SDValue Ops[] = { Op1 };
5484 return getMachineNode(Opcode, dl, VTs, Ops);
5488 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5489 SDValue Op1, SDValue Op2) {
5490 SDVTList VTs = getVTList(VT);
5491 SDValue Ops[] = { Op1, Op2 };
5492 return getMachineNode(Opcode, dl, VTs, Ops);
5496 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5497 SDValue Op1, SDValue Op2, SDValue Op3) {
5498 SDVTList VTs = getVTList(VT);
5499 SDValue Ops[] = { Op1, Op2, Op3 };
5500 return getMachineNode(Opcode, dl, VTs, Ops);
5504 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5505 ArrayRef<SDValue> Ops) {
5506 SDVTList VTs = getVTList(VT);
5507 return getMachineNode(Opcode, dl, VTs, Ops);
5511 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5512 SDVTList VTs = getVTList(VT1, VT2);
5513 return getMachineNode(Opcode, dl, VTs, None);
5517 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5518 EVT VT1, EVT VT2, SDValue Op1) {
5519 SDVTList VTs = getVTList(VT1, VT2);
5520 SDValue Ops[] = { Op1 };
5521 return getMachineNode(Opcode, dl, VTs, Ops);
5525 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5526 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5527 SDVTList VTs = getVTList(VT1, VT2);
5528 SDValue Ops[] = { Op1, Op2 };
5529 return getMachineNode(Opcode, dl, VTs, Ops);
5533 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5534 EVT VT1, EVT VT2, SDValue Op1,
5535 SDValue Op2, SDValue Op3) {
5536 SDVTList VTs = getVTList(VT1, VT2);
5537 SDValue Ops[] = { Op1, Op2, Op3 };
5538 return getMachineNode(Opcode, dl, VTs, Ops);
5542 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5544 ArrayRef<SDValue> Ops) {
5545 SDVTList VTs = getVTList(VT1, VT2);
5546 return getMachineNode(Opcode, dl, VTs, Ops);
5550 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5551 EVT VT1, EVT VT2, EVT VT3,
5552 SDValue Op1, SDValue Op2) {
5553 SDVTList VTs = getVTList(VT1, VT2, VT3);
5554 SDValue Ops[] = { Op1, Op2 };
5555 return getMachineNode(Opcode, dl, VTs, Ops);
5559 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5560 EVT VT1, EVT VT2, EVT VT3,
5561 SDValue Op1, SDValue Op2, SDValue Op3) {
5562 SDVTList VTs = getVTList(VT1, VT2, VT3);
5563 SDValue Ops[] = { Op1, Op2, Op3 };
5564 return getMachineNode(Opcode, dl, VTs, Ops);
5568 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5569 EVT VT1, EVT VT2, EVT VT3,
5570 ArrayRef<SDValue> Ops) {
5571 SDVTList VTs = getVTList(VT1, VT2, VT3);
5572 return getMachineNode(Opcode, dl, VTs, Ops);
5576 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5577 EVT VT2, EVT VT3, EVT VT4,
5578 ArrayRef<SDValue> Ops) {
5579 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5580 return getMachineNode(Opcode, dl, VTs, Ops);
5584 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5585 ArrayRef<EVT> ResultTys,
5586 ArrayRef<SDValue> Ops) {
5587 SDVTList VTs = getVTList(ResultTys);
5588 return getMachineNode(Opcode, dl, VTs, Ops);
5592 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5593 ArrayRef<SDValue> OpsArray) {
5594 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5597 const SDValue *Ops = OpsArray.data();
5598 unsigned NumOps = OpsArray.size();
5601 FoldingSetNodeID ID;
5602 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5604 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5605 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5609 // Allocate a new MachineSDNode.
5610 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5611 DL.getDebugLoc(), VTs);
5613 // Initialize the operands list.
5614 if (NumOps > array_lengthof(N->LocalOperands))
5615 // We're creating a final node that will live unmorphed for the
5616 // remainder of the current SelectionDAG iteration, so we can allocate
5617 // the operands directly out of a pool with no recycling metadata.
5618 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5621 N->InitOperands(N->LocalOperands, Ops, NumOps);
5622 N->OperandsNeedDelete = false;
5625 CSEMap.InsertNode(N, IP);
5627 AllNodes.push_back(N);
5629 VerifyMachineNode(N);
5634 /// getTargetExtractSubreg - A convenience function for creating
5635 /// TargetOpcode::EXTRACT_SUBREG nodes.
5637 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5639 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5640 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5641 VT, Operand, SRIdxVal);
5642 return SDValue(Subreg, 0);
5645 /// getTargetInsertSubreg - A convenience function for creating
5646 /// TargetOpcode::INSERT_SUBREG nodes.
5648 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5649 SDValue Operand, SDValue Subreg) {
5650 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5651 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5652 VT, Operand, Subreg, SRIdxVal);
5653 return SDValue(Result, 0);
5656 /// getNodeIfExists - Get the specified node if it's already available, or
5657 /// else return NULL.
5658 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5659 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5661 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5662 FoldingSetNodeID ID;
5663 AddNodeIDNode(ID, Opcode, VTList, Ops);
5664 if (isBinOpWithFlags(Opcode))
5665 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5667 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5673 /// getDbgValue - Creates a SDDbgValue node.
5677 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5678 bool IsIndirect, uint64_t Off,
5679 DebugLoc DL, unsigned O) {
5680 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5685 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5687 DebugLoc DL, unsigned O) {
5688 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5693 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5694 DebugLoc DL, unsigned O) {
5695 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5700 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5701 /// pointed to by a use iterator is deleted, increment the use iterator
5702 /// so that it doesn't dangle.
5704 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5705 SDNode::use_iterator &UI;
5706 SDNode::use_iterator &UE;
5708 void NodeDeleted(SDNode *N, SDNode *E) override {
5709 // Increment the iterator as needed.
5710 while (UI != UE && N == *UI)
5715 RAUWUpdateListener(SelectionDAG &d,
5716 SDNode::use_iterator &ui,
5717 SDNode::use_iterator &ue)
5718 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5723 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5724 /// This can cause recursive merging of nodes in the DAG.
5726 /// This version assumes From has a single result value.
5728 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5729 SDNode *From = FromN.getNode();
5730 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5731 "Cannot replace with this method!");
5732 assert(From != To.getNode() && "Cannot replace uses of with self");
5734 // Iterate over all the existing uses of From. New uses will be added
5735 // to the beginning of the use list, which we avoid visiting.
5736 // This specifically avoids visiting uses of From that arise while the
5737 // replacement is happening, because any such uses would be the result
5738 // of CSE: If an existing node looks like From after one of its operands
5739 // is replaced by To, we don't want to replace of all its users with To
5740 // too. See PR3018 for more info.
5741 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5742 RAUWUpdateListener Listener(*this, UI, UE);
5746 // This node is about to morph, remove its old self from the CSE maps.
5747 RemoveNodeFromCSEMaps(User);
5749 // A user can appear in a use list multiple times, and when this
5750 // happens the uses are usually next to each other in the list.
5751 // To help reduce the number of CSE recomputations, process all
5752 // the uses of this user that we can find this way.
5754 SDUse &Use = UI.getUse();
5757 } while (UI != UE && *UI == User);
5759 // Now that we have modified User, add it back to the CSE maps. If it
5760 // already exists there, recursively merge the results together.
5761 AddModifiedNodeToCSEMaps(User);
5764 // If we just RAUW'd the root, take note.
5765 if (FromN == getRoot())
5769 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5770 /// This can cause recursive merging of nodes in the DAG.
5772 /// This version assumes that for each value of From, there is a
5773 /// corresponding value in To in the same position with the same type.
5775 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5777 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5778 assert((!From->hasAnyUseOfValue(i) ||
5779 From->getValueType(i) == To->getValueType(i)) &&
5780 "Cannot use this version of ReplaceAllUsesWith!");
5783 // Handle the trivial case.
5787 // Iterate over just the existing users of From. See the comments in
5788 // the ReplaceAllUsesWith above.
5789 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5790 RAUWUpdateListener Listener(*this, UI, UE);
5794 // This node is about to morph, remove its old self from the CSE maps.
5795 RemoveNodeFromCSEMaps(User);
5797 // A user can appear in a use list multiple times, and when this
5798 // happens the uses are usually next to each other in the list.
5799 // To help reduce the number of CSE recomputations, process all
5800 // the uses of this user that we can find this way.
5802 SDUse &Use = UI.getUse();
5805 } while (UI != UE && *UI == User);
5807 // Now that we have modified User, add it back to the CSE maps. If it
5808 // already exists there, recursively merge the results together.
5809 AddModifiedNodeToCSEMaps(User);
5812 // If we just RAUW'd the root, take note.
5813 if (From == getRoot().getNode())
5814 setRoot(SDValue(To, getRoot().getResNo()));
5817 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5818 /// This can cause recursive merging of nodes in the DAG.
5820 /// This version can replace From with any result values. To must match the
5821 /// number and types of values returned by From.
5822 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5823 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5824 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5826 // Iterate over just the existing users of From. See the comments in
5827 // the ReplaceAllUsesWith above.
5828 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5829 RAUWUpdateListener Listener(*this, UI, UE);
5833 // This node is about to morph, remove its old self from the CSE maps.
5834 RemoveNodeFromCSEMaps(User);
5836 // A user can appear in a use list multiple times, and when this
5837 // happens the uses are usually next to each other in the list.
5838 // To help reduce the number of CSE recomputations, process all
5839 // the uses of this user that we can find this way.
5841 SDUse &Use = UI.getUse();
5842 const SDValue &ToOp = To[Use.getResNo()];
5845 } while (UI != UE && *UI == User);
5847 // Now that we have modified User, add it back to the CSE maps. If it
5848 // already exists there, recursively merge the results together.
5849 AddModifiedNodeToCSEMaps(User);
5852 // If we just RAUW'd the root, take note.
5853 if (From == getRoot().getNode())
5854 setRoot(SDValue(To[getRoot().getResNo()]));
5857 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5858 /// uses of other values produced by From.getNode() alone. The Deleted
5859 /// vector is handled the same way as for ReplaceAllUsesWith.
5860 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5861 // Handle the really simple, really trivial case efficiently.
5862 if (From == To) return;
5864 // Handle the simple, trivial, case efficiently.
5865 if (From.getNode()->getNumValues() == 1) {
5866 ReplaceAllUsesWith(From, To);
5870 // Iterate over just the existing users of From. See the comments in
5871 // the ReplaceAllUsesWith above.
5872 SDNode::use_iterator UI = From.getNode()->use_begin(),
5873 UE = From.getNode()->use_end();
5874 RAUWUpdateListener Listener(*this, UI, UE);
5877 bool UserRemovedFromCSEMaps = false;
5879 // A user can appear in a use list multiple times, and when this
5880 // happens the uses are usually next to each other in the list.
5881 // To help reduce the number of CSE recomputations, process all
5882 // the uses of this user that we can find this way.
5884 SDUse &Use = UI.getUse();
5886 // Skip uses of different values from the same node.
5887 if (Use.getResNo() != From.getResNo()) {
5892 // If this node hasn't been modified yet, it's still in the CSE maps,
5893 // so remove its old self from the CSE maps.
5894 if (!UserRemovedFromCSEMaps) {
5895 RemoveNodeFromCSEMaps(User);
5896 UserRemovedFromCSEMaps = true;
5901 } while (UI != UE && *UI == User);
5903 // We are iterating over all uses of the From node, so if a use
5904 // doesn't use the specific value, no changes are made.
5905 if (!UserRemovedFromCSEMaps)
5908 // Now that we have modified User, add it back to the CSE maps. If it
5909 // already exists there, recursively merge the results together.
5910 AddModifiedNodeToCSEMaps(User);
5913 // If we just RAUW'd the root, take note.
5914 if (From == getRoot())
5919 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5920 /// to record information about a use.
5927 /// operator< - Sort Memos by User.
5928 bool operator<(const UseMemo &L, const UseMemo &R) {
5929 return (intptr_t)L.User < (intptr_t)R.User;
5933 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5934 /// uses of other values produced by From.getNode() alone. The same value
5935 /// may appear in both the From and To list. The Deleted vector is
5936 /// handled the same way as for ReplaceAllUsesWith.
5937 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5940 // Handle the simple, trivial case efficiently.
5942 return ReplaceAllUsesOfValueWith(*From, *To);
5944 // Read up all the uses and make records of them. This helps
5945 // processing new uses that are introduced during the
5946 // replacement process.
5947 SmallVector<UseMemo, 4> Uses;
5948 for (unsigned i = 0; i != Num; ++i) {
5949 unsigned FromResNo = From[i].getResNo();
5950 SDNode *FromNode = From[i].getNode();
5951 for (SDNode::use_iterator UI = FromNode->use_begin(),
5952 E = FromNode->use_end(); UI != E; ++UI) {
5953 SDUse &Use = UI.getUse();
5954 if (Use.getResNo() == FromResNo) {
5955 UseMemo Memo = { *UI, i, &Use };
5956 Uses.push_back(Memo);
5961 // Sort the uses, so that all the uses from a given User are together.
5962 std::sort(Uses.begin(), Uses.end());
5964 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5965 UseIndex != UseIndexEnd; ) {
5966 // We know that this user uses some value of From. If it is the right
5967 // value, update it.
5968 SDNode *User = Uses[UseIndex].User;
5970 // This node is about to morph, remove its old self from the CSE maps.
5971 RemoveNodeFromCSEMaps(User);
5973 // The Uses array is sorted, so all the uses for a given User
5974 // are next to each other in the list.
5975 // To help reduce the number of CSE recomputations, process all
5976 // the uses of this user that we can find this way.
5978 unsigned i = Uses[UseIndex].Index;
5979 SDUse &Use = *Uses[UseIndex].Use;
5983 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5985 // Now that we have modified User, add it back to the CSE maps. If it
5986 // already exists there, recursively merge the results together.
5987 AddModifiedNodeToCSEMaps(User);
5991 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5992 /// based on their topological order. It returns the maximum id and a vector
5993 /// of the SDNodes* in assigned order by reference.
5994 unsigned SelectionDAG::AssignTopologicalOrder() {
5996 unsigned DAGSize = 0;
5998 // SortedPos tracks the progress of the algorithm. Nodes before it are
5999 // sorted, nodes after it are unsorted. When the algorithm completes
6000 // it is at the end of the list.
6001 allnodes_iterator SortedPos = allnodes_begin();
6003 // Visit all the nodes. Move nodes with no operands to the front of
6004 // the list immediately. Annotate nodes that do have operands with their
6005 // operand count. Before we do this, the Node Id fields of the nodes
6006 // may contain arbitrary values. After, the Node Id fields for nodes
6007 // before SortedPos will contain the topological sort index, and the
6008 // Node Id fields for nodes At SortedPos and after will contain the
6009 // count of outstanding operands.
6010 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6012 checkForCycles(N, this);
6013 unsigned Degree = N->getNumOperands();
6015 // A node with no uses, add it to the result array immediately.
6016 N->setNodeId(DAGSize++);
6017 allnodes_iterator Q = N;
6019 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6020 assert(SortedPos != AllNodes.end() && "Overran node list");
6023 // Temporarily use the Node Id as scratch space for the degree count.
6024 N->setNodeId(Degree);
6028 // Visit all the nodes. As we iterate, move nodes into sorted order,
6029 // such that by the time the end is reached all nodes will be sorted.
6030 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6032 checkForCycles(N, this);
6033 // N is in sorted position, so all its uses have one less operand
6034 // that needs to be sorted.
6035 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6038 unsigned Degree = P->getNodeId();
6039 assert(Degree != 0 && "Invalid node degree");
6042 // All of P's operands are sorted, so P may sorted now.
6043 P->setNodeId(DAGSize++);
6045 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6046 assert(SortedPos != AllNodes.end() && "Overran node list");
6049 // Update P's outstanding operand count.
6050 P->setNodeId(Degree);
6053 if (I == SortedPos) {
6056 dbgs() << "Overran sorted position:\n";
6057 S->dumprFull(this); dbgs() << "\n";
6058 dbgs() << "Checking if this is due to cycles\n";
6059 checkForCycles(this, true);
6061 llvm_unreachable(nullptr);
6065 assert(SortedPos == AllNodes.end() &&
6066 "Topological sort incomplete!");
6067 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6068 "First node in topological sort is not the entry token!");
6069 assert(AllNodes.front().getNodeId() == 0 &&
6070 "First node in topological sort has non-zero id!");
6071 assert(AllNodes.front().getNumOperands() == 0 &&
6072 "First node in topological sort has operands!");
6073 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6074 "Last node in topologic sort has unexpected id!");
6075 assert(AllNodes.back().use_empty() &&
6076 "Last node in topologic sort has users!");
6077 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6081 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6082 /// value is produced by SD.
6083 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6084 DbgInfo->add(DB, SD, isParameter);
6086 SD->setHasDebugValue(true);
6089 /// TransferDbgValues - Transfer SDDbgValues.
6090 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6091 if (From == To || !From.getNode()->getHasDebugValue())
6093 SDNode *FromNode = From.getNode();
6094 SDNode *ToNode = To.getNode();
6095 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6096 SmallVector<SDDbgValue *, 2> ClonedDVs;
6097 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6099 SDDbgValue *Dbg = *I;
6100 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6101 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6103 Dbg->getOffset(), Dbg->getDebugLoc(),
6105 ClonedDVs.push_back(Clone);
6108 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6109 E = ClonedDVs.end(); I != E; ++I)
6110 AddDbgValue(*I, ToNode, false);
6113 //===----------------------------------------------------------------------===//
6115 //===----------------------------------------------------------------------===//
6117 HandleSDNode::~HandleSDNode() {
6121 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6122 DebugLoc DL, const GlobalValue *GA,
6123 EVT VT, int64_t o, unsigned char TF)
6124 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6128 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6129 SDValue X, unsigned SrcAS,
6131 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6132 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6134 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6135 EVT memvt, MachineMemOperand *mmo)
6136 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6137 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6138 MMO->isNonTemporal(), MMO->isInvariant());
6139 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6140 assert(isNonTemporal() == MMO->isNonTemporal() &&
6141 "Non-temporal encoding error!");
6142 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6145 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6146 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6147 : SDNode(Opc, Order, dl, VTs, Ops),
6148 MemoryVT(memvt), MMO(mmo) {
6149 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6150 MMO->isNonTemporal(), MMO->isInvariant());
6151 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6152 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6155 /// Profile - Gather unique data for the node.
6157 void SDNode::Profile(FoldingSetNodeID &ID) const {
6158 AddNodeIDNode(ID, this);
6163 std::vector<EVT> VTs;
6166 VTs.reserve(MVT::LAST_VALUETYPE);
6167 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6168 VTs.push_back(MVT((MVT::SimpleValueType)i));
6173 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6174 static ManagedStatic<EVTArray> SimpleVTArray;
6175 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6177 /// getValueTypeList - Return a pointer to the specified value type.
6179 const EVT *SDNode::getValueTypeList(EVT VT) {
6180 if (VT.isExtended()) {
6181 sys::SmartScopedLock<true> Lock(*VTMutex);
6182 return &(*EVTs->insert(VT).first);
6184 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6185 "Value type out of range!");
6186 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6190 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6191 /// indicated value. This method ignores uses of other values defined by this
6193 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6194 assert(Value < getNumValues() && "Bad value!");
6196 // TODO: Only iterate over uses of a given value of the node
6197 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6198 if (UI.getUse().getResNo() == Value) {
6205 // Found exactly the right number of uses?
6210 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6211 /// value. This method ignores uses of other values defined by this operation.
6212 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6213 assert(Value < getNumValues() && "Bad value!");
6215 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6216 if (UI.getUse().getResNo() == Value)
6223 /// isOnlyUserOf - Return true if this node is the only use of N.
6225 bool SDNode::isOnlyUserOf(SDNode *N) const {
6227 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6238 /// isOperand - Return true if this node is an operand of N.
6240 bool SDValue::isOperandOf(SDNode *N) const {
6241 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6242 if (*this == N->getOperand(i))
6247 bool SDNode::isOperandOf(SDNode *N) const {
6248 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6249 if (this == N->OperandList[i].getNode())
6254 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6255 /// be a chain) reaches the specified operand without crossing any
6256 /// side-effecting instructions on any chain path. In practice, this looks
6257 /// through token factors and non-volatile loads. In order to remain efficient,
6258 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6259 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6260 unsigned Depth) const {
6261 if (*this == Dest) return true;
6263 // Don't search too deeply, we just want to be able to see through
6264 // TokenFactor's etc.
6265 if (Depth == 0) return false;
6267 // If this is a token factor, all inputs to the TF happen in parallel. If any
6268 // of the operands of the TF does not reach dest, then we cannot do the xform.
6269 if (getOpcode() == ISD::TokenFactor) {
6270 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6271 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6276 // Loads don't have side effects, look through them.
6277 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6278 if (!Ld->isVolatile())
6279 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6284 /// hasPredecessor - Return true if N is a predecessor of this node.
6285 /// N is either an operand of this node, or can be reached by recursively
6286 /// traversing up the operands.
6287 /// NOTE: This is an expensive method. Use it carefully.
6288 bool SDNode::hasPredecessor(const SDNode *N) const {
6289 SmallPtrSet<const SDNode *, 32> Visited;
6290 SmallVector<const SDNode *, 16> Worklist;
6291 return hasPredecessorHelper(N, Visited, Worklist);
6295 SDNode::hasPredecessorHelper(const SDNode *N,
6296 SmallPtrSet<const SDNode *, 32> &Visited,
6297 SmallVectorImpl<const SDNode *> &Worklist) const {
6298 if (Visited.empty()) {
6299 Worklist.push_back(this);
6301 // Take a look in the visited set. If we've already encountered this node
6302 // we needn't search further.
6303 if (Visited.count(N))
6307 // Haven't visited N yet. Continue the search.
6308 while (!Worklist.empty()) {
6309 const SDNode *M = Worklist.pop_back_val();
6310 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6311 SDNode *Op = M->getOperand(i).getNode();
6312 if (Visited.insert(Op))
6313 Worklist.push_back(Op);
6322 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6323 assert(Num < NumOperands && "Invalid child # of SDNode!");
6324 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6327 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6328 assert(N->getNumValues() == 1 &&
6329 "Can't unroll a vector with multiple results!");
6331 EVT VT = N->getValueType(0);
6332 unsigned NE = VT.getVectorNumElements();
6333 EVT EltVT = VT.getVectorElementType();
6336 SmallVector<SDValue, 8> Scalars;
6337 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6339 // If ResNE is 0, fully unroll the vector op.
6342 else if (NE > ResNE)
6346 for (i= 0; i != NE; ++i) {
6347 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6348 SDValue Operand = N->getOperand(j);
6349 EVT OperandVT = Operand.getValueType();
6350 if (OperandVT.isVector()) {
6351 // A vector operand; extract a single element.
6352 const TargetLowering *TLI = TM.getTargetLowering();
6353 EVT OperandEltVT = OperandVT.getVectorElementType();
6354 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6357 getConstant(i, TLI->getVectorIdxTy()));
6359 // A scalar operand; just use it as is.
6360 Operands[j] = Operand;
6364 switch (N->getOpcode()) {
6366 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6369 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6376 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6377 getShiftAmountOperand(Operands[0].getValueType(),
6380 case ISD::SIGN_EXTEND_INREG:
6381 case ISD::FP_ROUND_INREG: {
6382 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6383 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6385 getValueType(ExtVT)));
6390 for (; i < ResNE; ++i)
6391 Scalars.push_back(getUNDEF(EltVT));
6393 return getNode(ISD::BUILD_VECTOR, dl,
6394 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6398 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6399 /// location that is 'Dist' units away from the location that the 'Base' load
6400 /// is loading from.
6401 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6402 unsigned Bytes, int Dist) const {
6403 if (LD->getChain() != Base->getChain())
6405 EVT VT = LD->getValueType(0);
6406 if (VT.getSizeInBits() / 8 != Bytes)
6409 SDValue Loc = LD->getOperand(1);
6410 SDValue BaseLoc = Base->getOperand(1);
6411 if (Loc.getOpcode() == ISD::FrameIndex) {
6412 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6414 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6415 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6416 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6417 int FS = MFI->getObjectSize(FI);
6418 int BFS = MFI->getObjectSize(BFI);
6419 if (FS != BFS || FS != (int)Bytes) return false;
6420 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6424 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6425 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6428 const GlobalValue *GV1 = nullptr;
6429 const GlobalValue *GV2 = nullptr;
6430 int64_t Offset1 = 0;
6431 int64_t Offset2 = 0;
6432 const TargetLowering *TLI = TM.getTargetLowering();
6433 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6434 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6435 if (isGA1 && isGA2 && GV1 == GV2)
6436 return Offset1 == (Offset2 + Dist*Bytes);
6441 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6442 /// it cannot be inferred.
6443 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6444 // If this is a GlobalAddress + cst, return the alignment.
6445 const GlobalValue *GV;
6446 int64_t GVOffset = 0;
6447 const TargetLowering *TLI = TM.getTargetLowering();
6448 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6449 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6450 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6451 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6452 TLI->getDataLayout());
6453 unsigned AlignBits = KnownZero.countTrailingOnes();
6454 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6456 return MinAlign(Align, GVOffset);
6459 // If this is a direct reference to a stack slot, use information about the
6460 // stack slot's alignment.
6461 int FrameIdx = 1 << 31;
6462 int64_t FrameOffset = 0;
6463 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6464 FrameIdx = FI->getIndex();
6465 } else if (isBaseWithConstantOffset(Ptr) &&
6466 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6468 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6469 FrameOffset = Ptr.getConstantOperandVal(1);
6472 if (FrameIdx != (1 << 31)) {
6473 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6474 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6482 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6483 /// which is split (or expanded) into two not necessarily identical pieces.
6484 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6485 // Currently all types are split in half.
6487 if (!VT.isVector()) {
6488 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6490 unsigned NumElements = VT.getVectorNumElements();
6491 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6492 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6495 return std::make_pair(LoVT, HiVT);
6498 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6500 std::pair<SDValue, SDValue>
6501 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6503 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6504 N.getValueType().getVectorNumElements() &&
6505 "More vector elements requested than available!");
6507 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6508 getConstant(0, TLI->getVectorIdxTy()));
6509 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6510 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6511 return std::make_pair(Lo, Hi);
6514 void SelectionDAG::ExtractVectorElements(SDValue Op,
6515 SmallVectorImpl<SDValue> &Args,
6516 unsigned Start, unsigned Count) {
6517 EVT VT = Op.getValueType();
6519 Count = VT.getVectorNumElements();
6521 EVT EltVT = VT.getVectorElementType();
6522 EVT IdxTy = TLI->getVectorIdxTy();
6524 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6525 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6526 Op, getConstant(i, IdxTy)));
6530 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6531 unsigned GlobalAddressSDNode::getAddressSpace() const {
6532 return getGlobal()->getType()->getAddressSpace();
6536 Type *ConstantPoolSDNode::getType() const {
6537 if (isMachineConstantPoolEntry())
6538 return Val.MachineCPVal->getType();
6539 return Val.ConstVal->getType();
6542 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6544 unsigned &SplatBitSize,
6546 unsigned MinSplatBits,
6547 bool isBigEndian) const {
6548 EVT VT = getValueType(0);
6549 assert(VT.isVector() && "Expected a vector type");
6550 unsigned sz = VT.getSizeInBits();
6551 if (MinSplatBits > sz)
6554 SplatValue = APInt(sz, 0);
6555 SplatUndef = APInt(sz, 0);
6557 // Get the bits. Bits with undefined values (when the corresponding element
6558 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6559 // in SplatValue. If any of the values are not constant, give up and return
6561 unsigned int nOps = getNumOperands();
6562 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6563 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6565 for (unsigned j = 0; j < nOps; ++j) {
6566 unsigned i = isBigEndian ? nOps-1-j : j;
6567 SDValue OpVal = getOperand(i);
6568 unsigned BitPos = j * EltBitSize;
6570 if (OpVal.getOpcode() == ISD::UNDEF)
6571 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6572 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6573 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6574 zextOrTrunc(sz) << BitPos;
6575 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6576 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6581 // The build_vector is all constants or undefs. Find the smallest element
6582 // size that splats the vector.
6584 HasAnyUndefs = (SplatUndef != 0);
6587 unsigned HalfSize = sz / 2;
6588 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6589 APInt LowValue = SplatValue.trunc(HalfSize);
6590 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6591 APInt LowUndef = SplatUndef.trunc(HalfSize);
6593 // If the two halves do not match (ignoring undef bits), stop here.
6594 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6595 MinSplatBits > HalfSize)
6598 SplatValue = HighValue | LowValue;
6599 SplatUndef = HighUndef & LowUndef;
6608 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6609 SDValue Op0 = getOperand(0);
6610 if (Op0.getOpcode() != ISD::Constant)
6613 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6614 if (getOperand(i) != Op0)
6617 return cast<ConstantSDNode>(Op0);
6620 bool BuildVectorSDNode::isConstant() const {
6621 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6622 unsigned Opc = getOperand(i).getOpcode();
6623 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6629 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6630 // Find the first non-undef value in the shuffle mask.
6632 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6635 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6637 // Make sure all remaining elements are either undef or the same as the first
6639 for (int Idx = Mask[i]; i != e; ++i)
6640 if (Mask[i] >= 0 && Mask[i] != Idx)
6646 static void checkForCyclesHelper(const SDNode *N,
6647 SmallPtrSet<const SDNode*, 32> &Visited,
6648 SmallPtrSet<const SDNode*, 32> &Checked,
6649 const llvm::SelectionDAG *DAG) {
6650 // If this node has already been checked, don't check it again.
6651 if (Checked.count(N))
6654 // If a node has already been visited on this depth-first walk, reject it as
6656 if (!Visited.insert(N)) {
6657 errs() << "Detected cycle in SelectionDAG\n";
6658 dbgs() << "Offending node:\n";
6659 N->dumprFull(DAG); dbgs() << "\n";
6663 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6664 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6671 void llvm::checkForCycles(const llvm::SDNode *N,
6672 const llvm::SelectionDAG *DAG,
6680 assert(N && "Checking nonexistent SDNode");
6681 SmallPtrSet<const SDNode*, 32> visited;
6682 SmallPtrSet<const SDNode*, 32> checked;
6683 checkForCyclesHelper(N, visited, checked, DAG);
6688 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6689 checkForCycles(DAG->getRoot().getNode(), DAG, force);