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/TargetTransformInfo.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineConstantPool.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineModuleInfo.h"
27 #include "llvm/DebugInfo.h"
28 #include "llvm/IR/CallingConv.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/GlobalAlias.h"
34 #include "llvm/IR/GlobalVariable.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/ManagedStatic.h"
40 #include "llvm/Support/MathExtras.h"
41 #include "llvm/Support/Mutex.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Target/TargetInstrInfo.h"
44 #include "llvm/Target/TargetIntrinsicInfo.h"
45 #include "llvm/Target/TargetLowering.h"
46 #include "llvm/Target/TargetMachine.h"
47 #include "llvm/Target/TargetOptions.h"
48 #include "llvm/Target/TargetRegisterInfo.h"
49 #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 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
236 /// when given the operation for (X op Y).
237 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
238 // To perform this operation, we just need to swap the L and G bits of the
240 unsigned OldL = (Operation >> 2) & 1;
241 unsigned OldG = (Operation >> 1) & 1;
242 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
243 (OldL << 1) | // New G bit
244 (OldG << 2)); // New L bit.
247 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
248 /// 'op' is a valid SetCC operation.
249 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
250 unsigned Operation = Op;
252 Operation ^= 7; // Flip L, G, E bits, but not U.
254 Operation ^= 15; // Flip all of the condition bits.
256 if (Operation > ISD::SETTRUE2)
257 Operation &= ~8; // Don't let N and U bits get set.
259 return ISD::CondCode(Operation);
263 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
264 /// signed operation and 2 if the result is an unsigned comparison. Return zero
265 /// if the operation does not depend on the sign of the input (setne and seteq).
266 static int isSignedOp(ISD::CondCode Opcode) {
268 default: llvm_unreachable("Illegal integer setcc operation!");
270 case ISD::SETNE: return 0;
274 case ISD::SETGE: return 1;
278 case ISD::SETUGE: return 2;
282 /// getSetCCOrOperation - Return the result of a logical OR between different
283 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
284 /// returns SETCC_INVALID if it is not possible to represent the resultant
286 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
288 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
289 // Cannot fold a signed integer setcc with an unsigned integer setcc.
290 return ISD::SETCC_INVALID;
292 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
294 // If the N and U bits get set then the resultant comparison DOES suddenly
295 // care about orderedness, and is true when ordered.
296 if (Op > ISD::SETTRUE2)
297 Op &= ~16; // Clear the U bit if the N bit is set.
299 // Canonicalize illegal integer setcc's.
300 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
303 return ISD::CondCode(Op);
306 /// getSetCCAndOperation - Return the result of a logical AND between different
307 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
308 /// function returns zero if it is not possible to represent the resultant
310 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
312 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
313 // Cannot fold a signed setcc with an unsigned setcc.
314 return ISD::SETCC_INVALID;
316 // Combine all of the condition bits.
317 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
319 // Canonicalize illegal integer setcc's.
323 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
324 case ISD::SETOEQ: // SETEQ & SETU[LG]E
325 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
326 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
327 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
334 //===----------------------------------------------------------------------===//
335 // SDNode Profile Support
336 //===----------------------------------------------------------------------===//
338 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
340 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
344 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
345 /// solely with their pointer.
346 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
347 ID.AddPointer(VTList.VTs);
350 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
352 static void AddNodeIDOperands(FoldingSetNodeID &ID,
353 const SDValue *Ops, unsigned NumOps) {
354 for (; NumOps; --NumOps, ++Ops) {
355 ID.AddPointer(Ops->getNode());
356 ID.AddInteger(Ops->getResNo());
360 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
362 static void AddNodeIDOperands(FoldingSetNodeID &ID,
363 const SDUse *Ops, unsigned NumOps) {
364 for (; NumOps; --NumOps, ++Ops) {
365 ID.AddPointer(Ops->getNode());
366 ID.AddInteger(Ops->getResNo());
370 static void AddNodeIDNode(FoldingSetNodeID &ID,
371 unsigned short OpC, SDVTList VTList,
372 const SDValue *OpList, unsigned N) {
373 AddNodeIDOpcode(ID, OpC);
374 AddNodeIDValueTypes(ID, VTList);
375 AddNodeIDOperands(ID, OpList, N);
378 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
380 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
381 switch (N->getOpcode()) {
382 case ISD::TargetExternalSymbol:
383 case ISD::ExternalSymbol:
384 llvm_unreachable("Should only be used on nodes with operands");
385 default: break; // Normal nodes don't need extra info.
386 case ISD::TargetConstant:
387 case ISD::Constant: {
388 const ConstantSDNode *C = cast<ConstantSDNode>(N);
389 ID.AddPointer(C->getConstantIntValue());
390 ID.AddBoolean(C->isOpaque());
393 case ISD::TargetConstantFP:
394 case ISD::ConstantFP: {
395 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
398 case ISD::TargetGlobalAddress:
399 case ISD::GlobalAddress:
400 case ISD::TargetGlobalTLSAddress:
401 case ISD::GlobalTLSAddress: {
402 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
403 ID.AddPointer(GA->getGlobal());
404 ID.AddInteger(GA->getOffset());
405 ID.AddInteger(GA->getTargetFlags());
406 ID.AddInteger(GA->getAddressSpace());
409 case ISD::BasicBlock:
410 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
413 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
415 case ISD::RegisterMask:
416 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
419 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
421 case ISD::FrameIndex:
422 case ISD::TargetFrameIndex:
423 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
426 case ISD::TargetJumpTable:
427 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
428 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
430 case ISD::ConstantPool:
431 case ISD::TargetConstantPool: {
432 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
433 ID.AddInteger(CP->getAlignment());
434 ID.AddInteger(CP->getOffset());
435 if (CP->isMachineConstantPoolEntry())
436 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
438 ID.AddPointer(CP->getConstVal());
439 ID.AddInteger(CP->getTargetFlags());
442 case ISD::TargetIndex: {
443 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
444 ID.AddInteger(TI->getIndex());
445 ID.AddInteger(TI->getOffset());
446 ID.AddInteger(TI->getTargetFlags());
450 const LoadSDNode *LD = cast<LoadSDNode>(N);
451 ID.AddInteger(LD->getMemoryVT().getRawBits());
452 ID.AddInteger(LD->getRawSubclassData());
453 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
457 const StoreSDNode *ST = cast<StoreSDNode>(N);
458 ID.AddInteger(ST->getMemoryVT().getRawBits());
459 ID.AddInteger(ST->getRawSubclassData());
460 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
463 case ISD::ATOMIC_CMP_SWAP:
464 case ISD::ATOMIC_SWAP:
465 case ISD::ATOMIC_LOAD_ADD:
466 case ISD::ATOMIC_LOAD_SUB:
467 case ISD::ATOMIC_LOAD_AND:
468 case ISD::ATOMIC_LOAD_OR:
469 case ISD::ATOMIC_LOAD_XOR:
470 case ISD::ATOMIC_LOAD_NAND:
471 case ISD::ATOMIC_LOAD_MIN:
472 case ISD::ATOMIC_LOAD_MAX:
473 case ISD::ATOMIC_LOAD_UMIN:
474 case ISD::ATOMIC_LOAD_UMAX:
475 case ISD::ATOMIC_LOAD:
476 case ISD::ATOMIC_STORE: {
477 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
478 ID.AddInteger(AT->getMemoryVT().getRawBits());
479 ID.AddInteger(AT->getRawSubclassData());
480 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
483 case ISD::PREFETCH: {
484 const MemSDNode *PF = cast<MemSDNode>(N);
485 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
488 case ISD::VECTOR_SHUFFLE: {
489 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
490 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
492 ID.AddInteger(SVN->getMaskElt(i));
495 case ISD::TargetBlockAddress:
496 case ISD::BlockAddress: {
497 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
498 ID.AddPointer(BA->getBlockAddress());
499 ID.AddInteger(BA->getOffset());
500 ID.AddInteger(BA->getTargetFlags());
503 } // end switch (N->getOpcode())
505 // Target specific memory nodes could also have address spaces to check.
506 if (N->isTargetMemoryOpcode())
507 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
510 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
512 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
513 AddNodeIDOpcode(ID, N->getOpcode());
514 // Add the return value info.
515 AddNodeIDValueTypes(ID, N->getVTList());
516 // Add the operand info.
517 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
519 // Handle SDNode leafs with special info.
520 AddNodeIDCustom(ID, N);
523 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
524 /// the CSE map that carries volatility, temporalness, indexing mode, and
525 /// extension/truncation information.
527 static inline unsigned
528 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
529 bool isNonTemporal, bool isInvariant) {
530 assert((ConvType & 3) == ConvType &&
531 "ConvType may not require more than 2 bits!");
532 assert((AM & 7) == AM &&
533 "AM may not require more than 3 bits!");
537 (isNonTemporal << 6) |
541 //===----------------------------------------------------------------------===//
542 // SelectionDAG Class
543 //===----------------------------------------------------------------------===//
545 /// doNotCSE - Return true if CSE should not be performed for this node.
546 static bool doNotCSE(SDNode *N) {
547 if (N->getValueType(0) == MVT::Glue)
548 return true; // Never CSE anything that produces a flag.
550 switch (N->getOpcode()) {
552 case ISD::HANDLENODE:
554 return true; // Never CSE these nodes.
557 // Check that remaining values produced are not flags.
558 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
559 if (N->getValueType(i) == MVT::Glue)
560 return true; // Never CSE anything that produces a flag.
565 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
567 void SelectionDAG::RemoveDeadNodes() {
568 // Create a dummy node (which is not added to allnodes), that adds a reference
569 // to the root node, preventing it from being deleted.
570 HandleSDNode Dummy(getRoot());
572 SmallVector<SDNode*, 128> DeadNodes;
574 // Add all obviously-dead nodes to the DeadNodes worklist.
575 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
577 DeadNodes.push_back(I);
579 RemoveDeadNodes(DeadNodes);
581 // If the root changed (e.g. it was a dead load, update the root).
582 setRoot(Dummy.getValue());
585 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
586 /// given list, and any nodes that become unreachable as a result.
587 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
589 // Process the worklist, deleting the nodes and adding their uses to the
591 while (!DeadNodes.empty()) {
592 SDNode *N = DeadNodes.pop_back_val();
594 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
595 DUL->NodeDeleted(N, 0);
597 // Take the node out of the appropriate CSE map.
598 RemoveNodeFromCSEMaps(N);
600 // Next, brutally remove the operand list. This is safe to do, as there are
601 // no cycles in the graph.
602 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
604 SDNode *Operand = Use.getNode();
607 // Now that we removed this operand, see if there are no uses of it left.
608 if (Operand->use_empty())
609 DeadNodes.push_back(Operand);
616 void SelectionDAG::RemoveDeadNode(SDNode *N){
617 SmallVector<SDNode*, 16> DeadNodes(1, N);
619 // Create a dummy node that adds a reference to the root node, preventing
620 // it from being deleted. (This matters if the root is an operand of the
622 HandleSDNode Dummy(getRoot());
624 RemoveDeadNodes(DeadNodes);
627 void SelectionDAG::DeleteNode(SDNode *N) {
628 // First take this out of the appropriate CSE map.
629 RemoveNodeFromCSEMaps(N);
631 // Finally, remove uses due to operands of this node, remove from the
632 // AllNodes list, and delete the node.
633 DeleteNodeNotInCSEMaps(N);
636 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
637 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
638 assert(N->use_empty() && "Cannot delete a node that is not dead!");
640 // Drop all of the operands and decrement used node's use counts.
646 void SelectionDAG::DeallocateNode(SDNode *N) {
647 if (N->OperandsNeedDelete)
648 delete[] N->OperandList;
650 // Set the opcode to DELETED_NODE to help catch bugs when node
651 // memory is reallocated.
652 N->NodeType = ISD::DELETED_NODE;
654 NodeAllocator.Deallocate(AllNodes.remove(N));
656 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
657 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
658 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
659 DbgVals[i]->setIsInvalidated();
662 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
663 /// correspond to it. This is useful when we're about to delete or repurpose
664 /// the node. We don't want future request for structurally identical nodes
665 /// to return N anymore.
666 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
668 switch (N->getOpcode()) {
669 case ISD::HANDLENODE: return false; // noop.
671 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
672 "Cond code doesn't exist!");
673 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
674 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
676 case ISD::ExternalSymbol:
677 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
679 case ISD::TargetExternalSymbol: {
680 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
681 Erased = TargetExternalSymbols.erase(
682 std::pair<std::string,unsigned char>(ESN->getSymbol(),
683 ESN->getTargetFlags()));
686 case ISD::VALUETYPE: {
687 EVT VT = cast<VTSDNode>(N)->getVT();
688 if (VT.isExtended()) {
689 Erased = ExtendedValueTypeNodes.erase(VT);
691 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
692 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
697 // Remove it from the CSE Map.
698 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
699 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
700 Erased = CSEMap.RemoveNode(N);
704 // Verify that the node was actually in one of the CSE maps, unless it has a
705 // flag result (which cannot be CSE'd) or is one of the special cases that are
706 // not subject to CSE.
707 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
708 !N->isMachineOpcode() && !doNotCSE(N)) {
711 llvm_unreachable("Node is not in map!");
717 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
718 /// maps and modified in place. Add it back to the CSE maps, unless an identical
719 /// node already exists, in which case transfer all its users to the existing
720 /// node. This transfer can potentially trigger recursive merging.
723 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
724 // For node types that aren't CSE'd, just act as if no identical node
727 SDNode *Existing = CSEMap.GetOrInsertNode(N);
729 // If there was already an existing matching node, use ReplaceAllUsesWith
730 // to replace the dead one with the existing one. This can cause
731 // recursive merging of other unrelated nodes down the line.
732 ReplaceAllUsesWith(N, Existing);
734 // N is now dead. Inform the listeners and delete it.
735 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
736 DUL->NodeDeleted(N, Existing);
737 DeleteNodeNotInCSEMaps(N);
742 // If the node doesn't already exist, we updated it. Inform listeners.
743 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
747 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
748 /// were replaced with those specified. If this node is never memoized,
749 /// return null, otherwise return a pointer to the slot it would take. If a
750 /// node already exists with these operands, the slot will be non-null.
751 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
756 SDValue Ops[] = { Op };
758 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
759 AddNodeIDCustom(ID, N);
760 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
764 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
765 /// were replaced with those specified. If this node is never memoized,
766 /// return null, otherwise return a pointer to the slot it would take. If a
767 /// node already exists with these operands, the slot will be non-null.
768 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
769 SDValue Op1, SDValue Op2,
774 SDValue Ops[] = { Op1, Op2 };
776 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
777 AddNodeIDCustom(ID, N);
778 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
783 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
784 /// were replaced with those specified. If this node is never memoized,
785 /// return null, otherwise return a pointer to the slot it would take. If a
786 /// node already exists with these operands, the slot will be non-null.
787 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
788 const SDValue *Ops,unsigned NumOps,
794 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
795 AddNodeIDCustom(ID, N);
796 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
801 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
802 static void VerifyNodeCommon(SDNode *N) {
803 switch (N->getOpcode()) {
806 case ISD::BUILD_PAIR: {
807 EVT VT = N->getValueType(0);
808 assert(N->getNumValues() == 1 && "Too many results!");
809 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
810 "Wrong return type!");
811 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
812 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
813 "Mismatched operand types!");
814 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
815 "Wrong operand type!");
816 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
817 "Wrong return type size");
820 case ISD::BUILD_VECTOR: {
821 assert(N->getNumValues() == 1 && "Too many results!");
822 assert(N->getValueType(0).isVector() && "Wrong return type!");
823 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
824 "Wrong number of operands!");
825 EVT EltVT = N->getValueType(0).getVectorElementType();
826 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
827 assert((I->getValueType() == EltVT ||
828 (EltVT.isInteger() && I->getValueType().isInteger() &&
829 EltVT.bitsLE(I->getValueType()))) &&
830 "Wrong operand type!");
831 assert(I->getValueType() == N->getOperand(0).getValueType() &&
832 "Operands must all have the same type");
839 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
840 static void VerifySDNode(SDNode *N) {
841 // The SDNode allocators cannot be used to allocate nodes with fields that are
842 // not present in an SDNode!
843 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
844 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
845 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
846 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
847 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
848 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
849 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
850 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
851 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
852 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
853 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
854 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
855 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
856 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
857 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
858 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
859 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
860 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
861 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
866 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
868 static void VerifyMachineNode(SDNode *N) {
869 // The MachineNode allocators cannot be used to allocate nodes with fields
870 // that are not present in a MachineNode!
871 // Currently there are no such nodes.
877 /// getEVTAlignment - Compute the default alignment value for the
880 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
881 Type *Ty = VT == MVT::iPTR ?
882 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
883 VT.getTypeForEVT(*getContext());
885 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
888 // EntryNode could meaningfully have debug info if we can find it...
889 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
890 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TTI(0), TLI(0), OptLevel(OL),
891 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
892 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
894 AllNodes.push_back(&EntryNode);
895 DbgInfo = new SDDbgInfo();
898 void SelectionDAG::init(MachineFunction &mf, const TargetTransformInfo *tti,
899 const TargetLowering *tli) {
903 Context = &mf.getFunction()->getContext();
906 SelectionDAG::~SelectionDAG() {
907 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
912 void SelectionDAG::allnodes_clear() {
913 assert(&*AllNodes.begin() == &EntryNode);
914 AllNodes.remove(AllNodes.begin());
915 while (!AllNodes.empty())
916 DeallocateNode(AllNodes.begin());
919 void SelectionDAG::clear() {
921 OperandAllocator.Reset();
924 ExtendedValueTypeNodes.clear();
925 ExternalSymbols.clear();
926 TargetExternalSymbols.clear();
927 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
928 static_cast<CondCodeSDNode*>(0));
929 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
930 static_cast<SDNode*>(0));
932 EntryNode.UseList = 0;
933 AllNodes.push_back(&EntryNode);
934 Root = getEntryNode();
938 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
939 return VT.bitsGT(Op.getValueType()) ?
940 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
941 getNode(ISD::TRUNCATE, DL, VT, Op);
944 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
945 return VT.bitsGT(Op.getValueType()) ?
946 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
947 getNode(ISD::TRUNCATE, DL, VT, Op);
950 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
951 return VT.bitsGT(Op.getValueType()) ?
952 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
953 getNode(ISD::TRUNCATE, DL, VT, Op);
956 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
957 assert(!VT.isVector() &&
958 "getZeroExtendInReg should use the vector element type instead of "
960 if (Op.getValueType() == VT) return Op;
961 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
962 APInt Imm = APInt::getLowBitsSet(BitWidth,
964 return getNode(ISD::AND, DL, Op.getValueType(), Op,
965 getConstant(Imm, Op.getValueType()));
968 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
970 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
971 EVT EltVT = VT.getScalarType();
973 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
974 return getNode(ISD::XOR, DL, VT, Val, NegOne);
977 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
978 EVT EltVT = VT.getScalarType();
979 assert((EltVT.getSizeInBits() >= 64 ||
980 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
981 "getConstant with a uint64_t value that doesn't fit in the type!");
982 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
985 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
987 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
990 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
992 assert(VT.isInteger() && "Cannot create FP integer constant!");
994 EVT EltVT = VT.getScalarType();
995 const ConstantInt *Elt = &Val;
997 const TargetLowering *TLI = TM.getTargetLowering();
999 // In some cases the vector type is legal but the element type is illegal and
1000 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1001 // inserted value (the type does not need to match the vector element type).
1002 // Any extra bits introduced will be truncated away.
1003 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1004 TargetLowering::TypePromoteInteger) {
1005 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1006 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1007 Elt = ConstantInt::get(*getContext(), NewVal);
1009 // In other cases the element type is illegal and needs to be expanded, for
1010 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1011 // the value into n parts and use a vector type with n-times the elements.
1012 // Then bitcast to the type requested.
1013 // Legalizing constants too early makes the DAGCombiner's job harder so we
1014 // only legalize if the DAG tells us we must produce legal types.
1015 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1016 TLI->getTypeAction(*getContext(), EltVT) ==
1017 TargetLowering::TypeExpandInteger) {
1018 APInt NewVal = Elt->getValue();
1019 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1020 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1021 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1022 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1024 // Check the temporary vector is the correct size. If this fails then
1025 // getTypeToTransformTo() probably returned a type whose size (in bits)
1026 // isn't a power-of-2 factor of the requested type size.
1027 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1029 SmallVector<SDValue, 2> EltParts;
1030 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1031 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1032 .trunc(ViaEltSizeInBits),
1033 ViaEltVT, isT, isO));
1036 // EltParts is currently in little endian order. If we actually want
1037 // big-endian order then reverse it now.
1038 if (TLI->isBigEndian())
1039 std::reverse(EltParts.begin(), EltParts.end());
1041 // The elements must be reversed when the element order is different
1042 // to the endianness of the elements (because the BITCAST is itself a
1043 // vector shuffle in this situation). However, we do not need any code to
1044 // perform this reversal because getConstant() is producing a vector
1046 // This situation occurs in MIPS MSA.
1048 SmallVector<SDValue, 8> Ops;
1049 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1050 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1052 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1053 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1054 &Ops[0], Ops.size()));
1058 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1059 "APInt size does not match type size!");
1060 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1061 FoldingSetNodeID ID;
1062 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1067 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1069 return SDValue(N, 0);
1072 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1073 CSEMap.InsertNode(N, IP);
1074 AllNodes.push_back(N);
1077 SDValue Result(N, 0);
1078 if (VT.isVector()) {
1079 SmallVector<SDValue, 8> Ops;
1080 Ops.assign(VT.getVectorNumElements(), Result);
1081 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1086 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1087 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1091 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1092 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1095 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1096 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1098 EVT EltVT = VT.getScalarType();
1100 // Do the map lookup using the actual bit pattern for the floating point
1101 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1102 // we don't have issues with SNANs.
1103 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1104 FoldingSetNodeID ID;
1105 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1109 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1111 return SDValue(N, 0);
1114 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1115 CSEMap.InsertNode(N, IP);
1116 AllNodes.push_back(N);
1119 SDValue Result(N, 0);
1120 if (VT.isVector()) {
1121 SmallVector<SDValue, 8> Ops;
1122 Ops.assign(VT.getVectorNumElements(), Result);
1123 // FIXME SDLoc info might be appropriate here
1124 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1129 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1130 EVT EltVT = VT.getScalarType();
1131 if (EltVT==MVT::f32)
1132 return getConstantFP(APFloat((float)Val), VT, isTarget);
1133 else if (EltVT==MVT::f64)
1134 return getConstantFP(APFloat(Val), VT, isTarget);
1135 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1138 APFloat apf = APFloat(Val);
1139 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1141 return getConstantFP(apf, VT, isTarget);
1143 llvm_unreachable("Unsupported type in getConstantFP");
1146 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1147 EVT VT, int64_t Offset,
1149 unsigned char TargetFlags) {
1150 assert((TargetFlags == 0 || isTargetGA) &&
1151 "Cannot set target flags on target-independent globals");
1152 const TargetLowering *TLI = TM.getTargetLowering();
1154 // Truncate (with sign-extension) the offset value to the pointer size.
1155 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1157 Offset = SignExtend64(Offset, BitWidth);
1159 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1161 // If GV is an alias then use the aliasee for determining thread-localness.
1162 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1163 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1167 if (GVar && GVar->isThreadLocal())
1168 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1170 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1172 FoldingSetNodeID ID;
1173 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1175 ID.AddInteger(Offset);
1176 ID.AddInteger(TargetFlags);
1177 ID.AddInteger(GV->getType()->getAddressSpace());
1179 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1180 return SDValue(E, 0);
1182 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1183 DL.getDebugLoc(), GV, VT,
1184 Offset, TargetFlags);
1185 CSEMap.InsertNode(N, IP);
1186 AllNodes.push_back(N);
1187 return SDValue(N, 0);
1190 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1191 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1192 FoldingSetNodeID ID;
1193 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1196 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1197 return SDValue(E, 0);
1199 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1200 CSEMap.InsertNode(N, IP);
1201 AllNodes.push_back(N);
1202 return SDValue(N, 0);
1205 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1206 unsigned char TargetFlags) {
1207 assert((TargetFlags == 0 || isTarget) &&
1208 "Cannot set target flags on target-independent jump tables");
1209 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1210 FoldingSetNodeID ID;
1211 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1213 ID.AddInteger(TargetFlags);
1215 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1216 return SDValue(E, 0);
1218 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1220 CSEMap.InsertNode(N, IP);
1221 AllNodes.push_back(N);
1222 return SDValue(N, 0);
1225 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1226 unsigned Alignment, int Offset,
1228 unsigned char TargetFlags) {
1229 assert((TargetFlags == 0 || isTarget) &&
1230 "Cannot set target flags on target-independent globals");
1233 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1234 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1235 FoldingSetNodeID ID;
1236 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1237 ID.AddInteger(Alignment);
1238 ID.AddInteger(Offset);
1240 ID.AddInteger(TargetFlags);
1242 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1243 return SDValue(E, 0);
1245 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1246 Alignment, TargetFlags);
1247 CSEMap.InsertNode(N, IP);
1248 AllNodes.push_back(N);
1249 return SDValue(N, 0);
1253 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1254 unsigned Alignment, int Offset,
1256 unsigned char TargetFlags) {
1257 assert((TargetFlags == 0 || isTarget) &&
1258 "Cannot set target flags on target-independent globals");
1261 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1262 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1263 FoldingSetNodeID ID;
1264 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1265 ID.AddInteger(Alignment);
1266 ID.AddInteger(Offset);
1267 C->addSelectionDAGCSEId(ID);
1268 ID.AddInteger(TargetFlags);
1270 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1271 return SDValue(E, 0);
1273 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1274 Alignment, TargetFlags);
1275 CSEMap.InsertNode(N, IP);
1276 AllNodes.push_back(N);
1277 return SDValue(N, 0);
1280 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1281 unsigned char TargetFlags) {
1282 FoldingSetNodeID ID;
1283 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1284 ID.AddInteger(Index);
1285 ID.AddInteger(Offset);
1286 ID.AddInteger(TargetFlags);
1288 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1289 return SDValue(E, 0);
1291 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1293 CSEMap.InsertNode(N, IP);
1294 AllNodes.push_back(N);
1295 return SDValue(N, 0);
1298 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1299 FoldingSetNodeID ID;
1300 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1307 CSEMap.InsertNode(N, IP);
1308 AllNodes.push_back(N);
1309 return SDValue(N, 0);
1312 SDValue SelectionDAG::getValueType(EVT VT) {
1313 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1314 ValueTypeNodes.size())
1315 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1317 SDNode *&N = VT.isExtended() ?
1318 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1320 if (N) return SDValue(N, 0);
1321 N = new (NodeAllocator) VTSDNode(VT);
1322 AllNodes.push_back(N);
1323 return SDValue(N, 0);
1326 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1327 SDNode *&N = ExternalSymbols[Sym];
1328 if (N) return SDValue(N, 0);
1329 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1330 AllNodes.push_back(N);
1331 return SDValue(N, 0);
1334 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1335 unsigned char TargetFlags) {
1337 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1339 if (N) return SDValue(N, 0);
1340 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1341 AllNodes.push_back(N);
1342 return SDValue(N, 0);
1345 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1346 if ((unsigned)Cond >= CondCodeNodes.size())
1347 CondCodeNodes.resize(Cond+1);
1349 if (CondCodeNodes[Cond] == 0) {
1350 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1351 CondCodeNodes[Cond] = N;
1352 AllNodes.push_back(N);
1355 return SDValue(CondCodeNodes[Cond], 0);
1358 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1359 // the shuffle mask M that point at N1 to point at N2, and indices that point
1360 // N2 to point at N1.
1361 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1363 int NElts = M.size();
1364 for (int i = 0; i != NElts; ++i) {
1372 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1373 SDValue N2, const int *Mask) {
1374 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1375 "Invalid VECTOR_SHUFFLE");
1377 // Canonicalize shuffle undef, undef -> undef
1378 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1379 return getUNDEF(VT);
1381 // Validate that all indices in Mask are within the range of the elements
1382 // input to the shuffle.
1383 unsigned NElts = VT.getVectorNumElements();
1384 SmallVector<int, 8> MaskVec;
1385 for (unsigned i = 0; i != NElts; ++i) {
1386 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1387 MaskVec.push_back(Mask[i]);
1390 // Canonicalize shuffle v, v -> v, undef
1393 for (unsigned i = 0; i != NElts; ++i)
1394 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1397 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1398 if (N1.getOpcode() == ISD::UNDEF)
1399 commuteShuffle(N1, N2, MaskVec);
1401 // Canonicalize all index into lhs, -> shuffle lhs, undef
1402 // Canonicalize all index into rhs, -> shuffle rhs, undef
1403 bool AllLHS = true, AllRHS = true;
1404 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1405 for (unsigned i = 0; i != NElts; ++i) {
1406 if (MaskVec[i] >= (int)NElts) {
1411 } else if (MaskVec[i] >= 0) {
1415 if (AllLHS && AllRHS)
1416 return getUNDEF(VT);
1417 if (AllLHS && !N2Undef)
1421 commuteShuffle(N1, N2, MaskVec);
1424 // If Identity shuffle return that node.
1425 bool Identity = true;
1426 for (unsigned i = 0; i != NElts; ++i) {
1427 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1429 if (Identity && NElts)
1432 FoldingSetNodeID ID;
1433 SDValue Ops[2] = { N1, N2 };
1434 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1435 for (unsigned i = 0; i != NElts; ++i)
1436 ID.AddInteger(MaskVec[i]);
1439 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1440 return SDValue(E, 0);
1442 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1443 // SDNode doesn't have access to it. This memory will be "leaked" when
1444 // the node is deallocated, but recovered when the NodeAllocator is released.
1445 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1446 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1448 ShuffleVectorSDNode *N =
1449 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1450 dl.getDebugLoc(), N1, N2,
1452 CSEMap.InsertNode(N, IP);
1453 AllNodes.push_back(N);
1454 return SDValue(N, 0);
1457 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1458 SDValue Val, SDValue DTy,
1459 SDValue STy, SDValue Rnd, SDValue Sat,
1460 ISD::CvtCode Code) {
1461 // If the src and dest types are the same and the conversion is between
1462 // integer types of the same sign or two floats, no conversion is necessary.
1464 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1467 FoldingSetNodeID ID;
1468 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1469 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1471 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1472 return SDValue(E, 0);
1474 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1477 CSEMap.InsertNode(N, IP);
1478 AllNodes.push_back(N);
1479 return SDValue(N, 0);
1482 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1483 FoldingSetNodeID ID;
1484 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1485 ID.AddInteger(RegNo);
1487 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1488 return SDValue(E, 0);
1490 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1491 CSEMap.InsertNode(N, IP);
1492 AllNodes.push_back(N);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1497 FoldingSetNodeID ID;
1498 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1499 ID.AddPointer(RegMask);
1501 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1502 return SDValue(E, 0);
1504 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1505 CSEMap.InsertNode(N, IP);
1506 AllNodes.push_back(N);
1507 return SDValue(N, 0);
1510 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1511 FoldingSetNodeID ID;
1512 SDValue Ops[] = { Root };
1513 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1514 ID.AddPointer(Label);
1516 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1517 return SDValue(E, 0);
1519 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1520 dl.getDebugLoc(), Root, Label);
1521 CSEMap.InsertNode(N, IP);
1522 AllNodes.push_back(N);
1523 return SDValue(N, 0);
1527 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1530 unsigned char TargetFlags) {
1531 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1533 FoldingSetNodeID ID;
1534 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1536 ID.AddInteger(Offset);
1537 ID.AddInteger(TargetFlags);
1539 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1540 return SDValue(E, 0);
1542 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1544 CSEMap.InsertNode(N, IP);
1545 AllNodes.push_back(N);
1546 return SDValue(N, 0);
1549 SDValue SelectionDAG::getSrcValue(const Value *V) {
1550 assert((!V || V->getType()->isPointerTy()) &&
1551 "SrcValue is not a pointer?");
1553 FoldingSetNodeID ID;
1554 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1558 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1559 return SDValue(E, 0);
1561 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1562 CSEMap.InsertNode(N, IP);
1563 AllNodes.push_back(N);
1564 return SDValue(N, 0);
1567 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1568 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1569 FoldingSetNodeID ID;
1570 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1574 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1575 return SDValue(E, 0);
1577 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1578 CSEMap.InsertNode(N, IP);
1579 AllNodes.push_back(N);
1580 return SDValue(N, 0);
1583 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1584 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1585 unsigned SrcAS, unsigned DestAS) {
1586 SDValue Ops[] = {Ptr};
1587 FoldingSetNodeID ID;
1588 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1589 ID.AddInteger(SrcAS);
1590 ID.AddInteger(DestAS);
1593 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1594 return SDValue(E, 0);
1596 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1598 VT, Ptr, SrcAS, DestAS);
1599 CSEMap.InsertNode(N, IP);
1600 AllNodes.push_back(N);
1601 return SDValue(N, 0);
1604 /// getShiftAmountOperand - Return the specified value casted to
1605 /// the target's desired shift amount type.
1606 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1607 EVT OpTy = Op.getValueType();
1608 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1609 if (OpTy == ShTy || OpTy.isVector()) return Op;
1611 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1612 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1615 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1616 /// specified value type.
1617 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1618 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1619 unsigned ByteSize = VT.getStoreSize();
1620 Type *Ty = VT.getTypeForEVT(*getContext());
1621 const TargetLowering *TLI = TM.getTargetLowering();
1622 unsigned StackAlign =
1623 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1625 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1626 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1629 /// CreateStackTemporary - Create a stack temporary suitable for holding
1630 /// either of the specified value types.
1631 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1632 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1633 VT2.getStoreSizeInBits())/8;
1634 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1635 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1636 const TargetLowering *TLI = TM.getTargetLowering();
1637 const DataLayout *TD = TLI->getDataLayout();
1638 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1639 TD->getPrefTypeAlignment(Ty2));
1641 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1642 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1643 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1646 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1647 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1648 // These setcc operations always fold.
1652 case ISD::SETFALSE2: return getConstant(0, VT);
1654 case ISD::SETTRUE2: {
1655 const TargetLowering *TLI = TM.getTargetLowering();
1656 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1658 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1671 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1675 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1676 const APInt &C2 = N2C->getAPIntValue();
1677 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1678 const APInt &C1 = N1C->getAPIntValue();
1681 default: llvm_unreachable("Unknown integer setcc!");
1682 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1683 case ISD::SETNE: return getConstant(C1 != C2, VT);
1684 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1685 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1686 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1687 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1688 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1689 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1690 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1691 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1695 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1696 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1697 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1700 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1701 return getUNDEF(VT);
1703 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1704 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1705 return getUNDEF(VT);
1707 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1708 R==APFloat::cmpLessThan, VT);
1709 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1710 return getUNDEF(VT);
1712 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1713 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1714 return getUNDEF(VT);
1716 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1717 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1718 return getUNDEF(VT);
1720 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1721 R==APFloat::cmpEqual, VT);
1722 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1723 return getUNDEF(VT);
1725 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1726 R==APFloat::cmpEqual, VT);
1727 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1728 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1729 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1730 R==APFloat::cmpEqual, VT);
1731 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1732 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1733 R==APFloat::cmpLessThan, VT);
1734 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1735 R==APFloat::cmpUnordered, VT);
1736 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1737 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1740 // Ensure that the constant occurs on the RHS.
1741 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1742 MVT CompVT = N1.getValueType().getSimpleVT();
1743 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1746 return getSetCC(dl, VT, N2, N1, SwappedCond);
1750 // Could not fold it.
1754 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1755 /// use this predicate to simplify operations downstream.
1756 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1757 // This predicate is not safe for vector operations.
1758 if (Op.getValueType().isVector())
1761 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1762 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1765 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1766 /// this predicate to simplify operations downstream. Mask is known to be zero
1767 /// for bits that V cannot have.
1768 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1769 unsigned Depth) const {
1770 APInt KnownZero, KnownOne;
1771 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1772 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1773 return (KnownZero & Mask) == Mask;
1776 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1777 /// known to be either zero or one and return them in the KnownZero/KnownOne
1778 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1780 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1781 APInt &KnownOne, unsigned Depth) const {
1782 const TargetLowering *TLI = TM.getTargetLowering();
1783 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1785 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1787 return; // Limit search depth.
1789 APInt KnownZero2, KnownOne2;
1791 switch (Op.getOpcode()) {
1793 // We know all of the bits for a constant!
1794 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1795 KnownZero = ~KnownOne;
1798 // If either the LHS or the RHS are Zero, the result is zero.
1799 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1800 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1801 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1802 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1804 // Output known-1 bits are only known if set in both the LHS & RHS.
1805 KnownOne &= KnownOne2;
1806 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1807 KnownZero |= KnownZero2;
1810 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1811 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1812 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1813 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1815 // Output known-0 bits are only known if clear in both the LHS & RHS.
1816 KnownZero &= KnownZero2;
1817 // Output known-1 are known to be set if set in either the LHS | RHS.
1818 KnownOne |= KnownOne2;
1821 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1822 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1823 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1824 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1826 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1827 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1828 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1829 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1830 KnownZero = KnownZeroOut;
1834 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1835 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1836 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1837 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1839 // If low bits are zero in either operand, output low known-0 bits.
1840 // Also compute a conserative estimate for high known-0 bits.
1841 // More trickiness is possible, but this is sufficient for the
1842 // interesting case of alignment computation.
1843 KnownOne.clearAllBits();
1844 unsigned TrailZ = KnownZero.countTrailingOnes() +
1845 KnownZero2.countTrailingOnes();
1846 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1847 KnownZero2.countLeadingOnes(),
1848 BitWidth) - BitWidth;
1850 TrailZ = std::min(TrailZ, BitWidth);
1851 LeadZ = std::min(LeadZ, BitWidth);
1852 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1853 APInt::getHighBitsSet(BitWidth, LeadZ);
1857 // For the purposes of computing leading zeros we can conservatively
1858 // treat a udiv as a logical right shift by the power of 2 known to
1859 // be less than the denominator.
1860 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1861 unsigned LeadZ = KnownZero2.countLeadingOnes();
1863 KnownOne2.clearAllBits();
1864 KnownZero2.clearAllBits();
1865 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1866 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1867 if (RHSUnknownLeadingOnes != BitWidth)
1868 LeadZ = std::min(BitWidth,
1869 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1871 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1875 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1876 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1877 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1878 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1880 // Only known if known in both the LHS and RHS.
1881 KnownOne &= KnownOne2;
1882 KnownZero &= KnownZero2;
1884 case ISD::SELECT_CC:
1885 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1886 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1887 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1888 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1890 // Only known if known in both the LHS and RHS.
1891 KnownOne &= KnownOne2;
1892 KnownZero &= KnownZero2;
1900 if (Op.getResNo() != 1)
1902 // The boolean result conforms to getBooleanContents. Fall through.
1904 // If we know the result of a setcc has the top bits zero, use this info.
1905 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1906 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1907 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1910 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1911 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1912 unsigned ShAmt = SA->getZExtValue();
1914 // If the shift count is an invalid immediate, don't do anything.
1915 if (ShAmt >= BitWidth)
1918 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1919 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1920 KnownZero <<= ShAmt;
1922 // low bits known zero.
1923 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1927 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1928 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1929 unsigned ShAmt = SA->getZExtValue();
1931 // If the shift count is an invalid immediate, don't do anything.
1932 if (ShAmt >= BitWidth)
1935 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1936 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1937 KnownZero = KnownZero.lshr(ShAmt);
1938 KnownOne = KnownOne.lshr(ShAmt);
1940 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1941 KnownZero |= HighBits; // High bits known zero.
1945 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1946 unsigned ShAmt = SA->getZExtValue();
1948 // If the shift count is an invalid immediate, don't do anything.
1949 if (ShAmt >= BitWidth)
1952 // If any of the demanded bits are produced by the sign extension, we also
1953 // demand the input sign bit.
1954 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1956 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1957 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1958 KnownZero = KnownZero.lshr(ShAmt);
1959 KnownOne = KnownOne.lshr(ShAmt);
1961 // Handle the sign bits.
1962 APInt SignBit = APInt::getSignBit(BitWidth);
1963 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1965 if (KnownZero.intersects(SignBit)) {
1966 KnownZero |= HighBits; // New bits are known zero.
1967 } else if (KnownOne.intersects(SignBit)) {
1968 KnownOne |= HighBits; // New bits are known one.
1972 case ISD::SIGN_EXTEND_INREG: {
1973 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1974 unsigned EBits = EVT.getScalarType().getSizeInBits();
1976 // Sign extension. Compute the demanded bits in the result that are not
1977 // present in the input.
1978 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1980 APInt InSignBit = APInt::getSignBit(EBits);
1981 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1983 // If the sign extended bits are demanded, we know that the sign
1985 InSignBit = InSignBit.zext(BitWidth);
1986 if (NewBits.getBoolValue())
1987 InputDemandedBits |= InSignBit;
1989 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1990 KnownOne &= InputDemandedBits;
1991 KnownZero &= InputDemandedBits;
1992 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1994 // If the sign bit of the input is known set or clear, then we know the
1995 // top bits of the result.
1996 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1997 KnownZero |= NewBits;
1998 KnownOne &= ~NewBits;
1999 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2000 KnownOne |= NewBits;
2001 KnownZero &= ~NewBits;
2002 } else { // Input sign bit unknown
2003 KnownZero &= ~NewBits;
2004 KnownOne &= ~NewBits;
2009 case ISD::CTTZ_ZERO_UNDEF:
2011 case ISD::CTLZ_ZERO_UNDEF:
2013 unsigned LowBits = Log2_32(BitWidth)+1;
2014 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2015 KnownOne.clearAllBits();
2019 LoadSDNode *LD = cast<LoadSDNode>(Op);
2020 // If this is a ZEXTLoad and we are looking at the loaded value.
2021 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2022 EVT VT = LD->getMemoryVT();
2023 unsigned MemBits = VT.getScalarType().getSizeInBits();
2024 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2025 } else if (const MDNode *Ranges = LD->getRanges()) {
2026 computeMaskedBitsLoad(*Ranges, KnownZero);
2030 case ISD::ZERO_EXTEND: {
2031 EVT InVT = Op.getOperand(0).getValueType();
2032 unsigned InBits = InVT.getScalarType().getSizeInBits();
2033 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2034 KnownZero = KnownZero.trunc(InBits);
2035 KnownOne = KnownOne.trunc(InBits);
2036 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2037 KnownZero = KnownZero.zext(BitWidth);
2038 KnownOne = KnownOne.zext(BitWidth);
2039 KnownZero |= NewBits;
2042 case ISD::SIGN_EXTEND: {
2043 EVT InVT = Op.getOperand(0).getValueType();
2044 unsigned InBits = InVT.getScalarType().getSizeInBits();
2045 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2047 KnownZero = KnownZero.trunc(InBits);
2048 KnownOne = KnownOne.trunc(InBits);
2049 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2051 // Note if the sign bit is known to be zero or one.
2052 bool SignBitKnownZero = KnownZero.isNegative();
2053 bool SignBitKnownOne = KnownOne.isNegative();
2054 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2055 "Sign bit can't be known to be both zero and one!");
2057 KnownZero = KnownZero.zext(BitWidth);
2058 KnownOne = KnownOne.zext(BitWidth);
2060 // If the sign bit is known zero or one, the top bits match.
2061 if (SignBitKnownZero)
2062 KnownZero |= NewBits;
2063 else if (SignBitKnownOne)
2064 KnownOne |= NewBits;
2067 case ISD::ANY_EXTEND: {
2068 EVT InVT = Op.getOperand(0).getValueType();
2069 unsigned InBits = InVT.getScalarType().getSizeInBits();
2070 KnownZero = KnownZero.trunc(InBits);
2071 KnownOne = KnownOne.trunc(InBits);
2072 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2073 KnownZero = KnownZero.zext(BitWidth);
2074 KnownOne = KnownOne.zext(BitWidth);
2077 case ISD::TRUNCATE: {
2078 EVT InVT = Op.getOperand(0).getValueType();
2079 unsigned InBits = InVT.getScalarType().getSizeInBits();
2080 KnownZero = KnownZero.zext(InBits);
2081 KnownOne = KnownOne.zext(InBits);
2082 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2083 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2084 KnownZero = KnownZero.trunc(BitWidth);
2085 KnownOne = KnownOne.trunc(BitWidth);
2088 case ISD::AssertZext: {
2089 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2090 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2091 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2092 KnownZero |= (~InMask);
2093 KnownOne &= (~KnownZero);
2097 // All bits are zero except the low bit.
2098 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2102 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2103 // We know that the top bits of C-X are clear if X contains less bits
2104 // than C (i.e. no wrap-around can happen). For example, 20-X is
2105 // positive if we can prove that X is >= 0 and < 16.
2106 if (CLHS->getAPIntValue().isNonNegative()) {
2107 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2108 // NLZ can't be BitWidth with no sign bit
2109 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2110 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2112 // If all of the MaskV bits are known to be zero, then we know the
2113 // output top bits are zero, because we now know that the output is
2115 if ((KnownZero2 & MaskV) == MaskV) {
2116 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2117 // Top bits known zero.
2118 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2126 // Output known-0 bits are known if clear or set in both the low clear bits
2127 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2128 // low 3 bits clear.
2129 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2130 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2131 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2133 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2134 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2135 KnownZeroOut = std::min(KnownZeroOut,
2136 KnownZero2.countTrailingOnes());
2138 if (Op.getOpcode() == ISD::ADD) {
2139 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2143 // With ADDE, a carry bit may be added in, so we can only use this
2144 // information if we know (at least) that the low two bits are clear. We
2145 // then return to the caller that the low bit is unknown but that other bits
2147 if (KnownZeroOut >= 2) // ADDE
2148 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2152 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2153 const APInt &RA = Rem->getAPIntValue().abs();
2154 if (RA.isPowerOf2()) {
2155 APInt LowBits = RA - 1;
2156 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2158 // The low bits of the first operand are unchanged by the srem.
2159 KnownZero = KnownZero2 & LowBits;
2160 KnownOne = KnownOne2 & LowBits;
2162 // If the first operand is non-negative or has all low bits zero, then
2163 // the upper bits are all zero.
2164 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2165 KnownZero |= ~LowBits;
2167 // If the first operand is negative and not all low bits are zero, then
2168 // the upper bits are all one.
2169 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2170 KnownOne |= ~LowBits;
2171 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2176 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2177 const APInt &RA = Rem->getAPIntValue();
2178 if (RA.isPowerOf2()) {
2179 APInt LowBits = (RA - 1);
2180 KnownZero |= ~LowBits;
2181 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2182 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2187 // Since the result is less than or equal to either operand, any leading
2188 // zero bits in either operand must also exist in the result.
2189 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2190 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2192 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2193 KnownZero2.countLeadingOnes());
2194 KnownOne.clearAllBits();
2195 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2198 case ISD::FrameIndex:
2199 case ISD::TargetFrameIndex:
2200 if (unsigned Align = InferPtrAlignment(Op)) {
2201 // The low bits are known zero if the pointer is aligned.
2202 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2208 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2211 case ISD::INTRINSIC_WO_CHAIN:
2212 case ISD::INTRINSIC_W_CHAIN:
2213 case ISD::INTRINSIC_VOID:
2214 // Allow the target to implement this method for its nodes.
2215 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2220 /// ComputeNumSignBits - Return the number of times the sign bit of the
2221 /// register is replicated into the other bits. We know that at least 1 bit
2222 /// is always equal to the sign bit (itself), but other cases can give us
2223 /// information. For example, immediately after an "SRA X, 2", we know that
2224 /// the top 3 bits are all equal to each other, so we return 3.
2225 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2226 const TargetLowering *TLI = TM.getTargetLowering();
2227 EVT VT = Op.getValueType();
2228 assert(VT.isInteger() && "Invalid VT!");
2229 unsigned VTBits = VT.getScalarType().getSizeInBits();
2231 unsigned FirstAnswer = 1;
2234 return 1; // Limit search depth.
2236 switch (Op.getOpcode()) {
2238 case ISD::AssertSext:
2239 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2240 return VTBits-Tmp+1;
2241 case ISD::AssertZext:
2242 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2245 case ISD::Constant: {
2246 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2247 return Val.getNumSignBits();
2250 case ISD::SIGN_EXTEND:
2252 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2253 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2255 case ISD::SIGN_EXTEND_INREG:
2256 // Max of the input and what this extends.
2258 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2261 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2262 return std::max(Tmp, Tmp2);
2265 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2266 // SRA X, C -> adds C sign bits.
2267 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2268 Tmp += C->getZExtValue();
2269 if (Tmp > VTBits) Tmp = VTBits;
2273 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2274 // shl destroys sign bits.
2275 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2276 if (C->getZExtValue() >= VTBits || // Bad shift.
2277 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2278 return Tmp - C->getZExtValue();
2283 case ISD::XOR: // NOT is handled here.
2284 // Logical binary ops preserve the number of sign bits at the worst.
2285 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2287 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2288 FirstAnswer = std::min(Tmp, Tmp2);
2289 // We computed what we know about the sign bits as our first
2290 // answer. Now proceed to the generic code that uses
2291 // ComputeMaskedBits, and pick whichever answer is better.
2296 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2297 if (Tmp == 1) return 1; // Early out.
2298 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2299 return std::min(Tmp, Tmp2);
2307 if (Op.getResNo() != 1)
2309 // The boolean result conforms to getBooleanContents. Fall through.
2311 // If setcc returns 0/-1, all bits are sign bits.
2312 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2313 TargetLowering::ZeroOrNegativeOneBooleanContent)
2318 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2319 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2321 // Handle rotate right by N like a rotate left by 32-N.
2322 if (Op.getOpcode() == ISD::ROTR)
2323 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2325 // If we aren't rotating out all of the known-in sign bits, return the
2326 // number that are left. This handles rotl(sext(x), 1) for example.
2327 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2328 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2332 // Add can have at most one carry bit. Thus we know that the output
2333 // is, at worst, one more bit than the inputs.
2334 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2335 if (Tmp == 1) return 1; // Early out.
2337 // Special case decrementing a value (ADD X, -1):
2338 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2339 if (CRHS->isAllOnesValue()) {
2340 APInt KnownZero, KnownOne;
2341 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2343 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2345 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2348 // If we are subtracting one from a positive number, there is no carry
2349 // out of the result.
2350 if (KnownZero.isNegative())
2354 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2355 if (Tmp2 == 1) return 1;
2356 return std::min(Tmp, Tmp2)-1;
2359 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2360 if (Tmp2 == 1) return 1;
2363 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2364 if (CLHS->isNullValue()) {
2365 APInt KnownZero, KnownOne;
2366 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2367 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2369 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2372 // If the input is known to be positive (the sign bit is known clear),
2373 // the output of the NEG has the same number of sign bits as the input.
2374 if (KnownZero.isNegative())
2377 // Otherwise, we treat this like a SUB.
2380 // Sub can have at most one carry bit. Thus we know that the output
2381 // is, at worst, one more bit than the inputs.
2382 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2383 if (Tmp == 1) return 1; // Early out.
2384 return std::min(Tmp, Tmp2)-1;
2386 // FIXME: it's tricky to do anything useful for this, but it is an important
2387 // case for targets like X86.
2391 // If we are looking at the loaded value of the SDNode.
2392 if (Op.getResNo() == 0) {
2393 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2394 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2395 unsigned ExtType = LD->getExtensionType();
2398 case ISD::SEXTLOAD: // '17' bits known
2399 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2400 return VTBits-Tmp+1;
2401 case ISD::ZEXTLOAD: // '16' bits known
2402 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2408 // Allow the target to implement this method for its nodes.
2409 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2410 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2411 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2412 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2413 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2414 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2417 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2418 // use this information.
2419 APInt KnownZero, KnownOne;
2420 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2423 if (KnownZero.isNegative()) { // sign bit is 0
2425 } else if (KnownOne.isNegative()) { // sign bit is 1;
2432 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2433 // the number of identical bits in the top of the input value.
2435 Mask <<= Mask.getBitWidth()-VTBits;
2436 // Return # leading zeros. We use 'min' here in case Val was zero before
2437 // shifting. We don't want to return '64' as for an i32 "0".
2438 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2441 /// isBaseWithConstantOffset - Return true if the specified operand is an
2442 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2443 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2444 /// semantics as an ADD. This handles the equivalence:
2445 /// X|Cst == X+Cst iff X&Cst = 0.
2446 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2447 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2448 !isa<ConstantSDNode>(Op.getOperand(1)))
2451 if (Op.getOpcode() == ISD::OR &&
2452 !MaskedValueIsZero(Op.getOperand(0),
2453 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2460 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2461 // If we're told that NaNs won't happen, assume they won't.
2462 if (getTarget().Options.NoNaNsFPMath)
2465 // If the value is a constant, we can obviously see if it is a NaN or not.
2466 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2467 return !C->getValueAPF().isNaN();
2469 // TODO: Recognize more cases here.
2474 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2475 // If the value is a constant, we can obviously see if it is a zero or not.
2476 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2477 return !C->isZero();
2479 // TODO: Recognize more cases here.
2480 switch (Op.getOpcode()) {
2483 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2484 return !C->isNullValue();
2491 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2492 // Check the obvious case.
2493 if (A == B) return true;
2495 // For for negative and positive zero.
2496 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2497 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2498 if (CA->isZero() && CB->isZero()) return true;
2500 // Otherwise they may not be equal.
2504 /// getNode - Gets or creates the specified node.
2506 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2507 FoldingSetNodeID ID;
2508 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2511 return SDValue(E, 0);
2513 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2514 DL.getDebugLoc(), getVTList(VT));
2515 CSEMap.InsertNode(N, IP);
2517 AllNodes.push_back(N);
2521 return SDValue(N, 0);
2524 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2525 EVT VT, SDValue Operand) {
2526 // Constant fold unary operations with an integer constant operand.
2527 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2528 const APInt &Val = C->getAPIntValue();
2531 case ISD::SIGN_EXTEND:
2532 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2533 case ISD::ANY_EXTEND:
2534 case ISD::ZERO_EXTEND:
2536 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2537 case ISD::UINT_TO_FP:
2538 case ISD::SINT_TO_FP: {
2539 APFloat apf(EVTToAPFloatSemantics(VT),
2540 APInt::getNullValue(VT.getSizeInBits()));
2541 (void)apf.convertFromAPInt(Val,
2542 Opcode==ISD::SINT_TO_FP,
2543 APFloat::rmNearestTiesToEven);
2544 return getConstantFP(apf, VT);
2547 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2548 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2549 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2550 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2553 return getConstant(Val.byteSwap(), VT);
2555 return getConstant(Val.countPopulation(), VT);
2557 case ISD::CTLZ_ZERO_UNDEF:
2558 return getConstant(Val.countLeadingZeros(), VT);
2560 case ISD::CTTZ_ZERO_UNDEF:
2561 return getConstant(Val.countTrailingZeros(), VT);
2565 // Constant fold unary operations with a floating point constant operand.
2566 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2567 APFloat V = C->getValueAPF(); // make copy
2571 return getConstantFP(V, VT);
2574 return getConstantFP(V, VT);
2576 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2577 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2578 return getConstantFP(V, VT);
2582 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2583 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2584 return getConstantFP(V, VT);
2588 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2589 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2590 return getConstantFP(V, VT);
2593 case ISD::FP_EXTEND: {
2595 // This can return overflow, underflow, or inexact; we don't care.
2596 // FIXME need to be more flexible about rounding mode.
2597 (void)V.convert(EVTToAPFloatSemantics(VT),
2598 APFloat::rmNearestTiesToEven, &ignored);
2599 return getConstantFP(V, VT);
2601 case ISD::FP_TO_SINT:
2602 case ISD::FP_TO_UINT: {
2605 assert(integerPartWidth >= 64);
2606 // FIXME need to be more flexible about rounding mode.
2607 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2608 Opcode==ISD::FP_TO_SINT,
2609 APFloat::rmTowardZero, &ignored);
2610 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2612 APInt api(VT.getSizeInBits(), x);
2613 return getConstant(api, VT);
2616 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2617 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2618 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2619 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2624 unsigned OpOpcode = Operand.getNode()->getOpcode();
2626 case ISD::TokenFactor:
2627 case ISD::MERGE_VALUES:
2628 case ISD::CONCAT_VECTORS:
2629 return Operand; // Factor, merge or concat of one node? No need.
2630 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2631 case ISD::FP_EXTEND:
2632 assert(VT.isFloatingPoint() &&
2633 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2634 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2635 assert((!VT.isVector() ||
2636 VT.getVectorNumElements() ==
2637 Operand.getValueType().getVectorNumElements()) &&
2638 "Vector element count mismatch!");
2639 if (Operand.getOpcode() == ISD::UNDEF)
2640 return getUNDEF(VT);
2642 case ISD::SIGN_EXTEND:
2643 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2644 "Invalid SIGN_EXTEND!");
2645 if (Operand.getValueType() == VT) return Operand; // noop extension
2646 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2647 "Invalid sext node, dst < src!");
2648 assert((!VT.isVector() ||
2649 VT.getVectorNumElements() ==
2650 Operand.getValueType().getVectorNumElements()) &&
2651 "Vector element count mismatch!");
2652 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2653 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2654 else if (OpOpcode == ISD::UNDEF)
2655 // sext(undef) = 0, because the top bits will all be the same.
2656 return getConstant(0, VT);
2658 case ISD::ZERO_EXTEND:
2659 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2660 "Invalid ZERO_EXTEND!");
2661 if (Operand.getValueType() == VT) return Operand; // noop extension
2662 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2663 "Invalid zext node, dst < src!");
2664 assert((!VT.isVector() ||
2665 VT.getVectorNumElements() ==
2666 Operand.getValueType().getVectorNumElements()) &&
2667 "Vector element count mismatch!");
2668 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2669 return getNode(ISD::ZERO_EXTEND, DL, VT,
2670 Operand.getNode()->getOperand(0));
2671 else if (OpOpcode == ISD::UNDEF)
2672 // zext(undef) = 0, because the top bits will be zero.
2673 return getConstant(0, VT);
2675 case ISD::ANY_EXTEND:
2676 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2677 "Invalid ANY_EXTEND!");
2678 if (Operand.getValueType() == VT) return Operand; // noop extension
2679 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2680 "Invalid anyext node, dst < src!");
2681 assert((!VT.isVector() ||
2682 VT.getVectorNumElements() ==
2683 Operand.getValueType().getVectorNumElements()) &&
2684 "Vector element count mismatch!");
2686 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2687 OpOpcode == ISD::ANY_EXTEND)
2688 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2689 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2690 else if (OpOpcode == ISD::UNDEF)
2691 return getUNDEF(VT);
2693 // (ext (trunx x)) -> x
2694 if (OpOpcode == ISD::TRUNCATE) {
2695 SDValue OpOp = Operand.getNode()->getOperand(0);
2696 if (OpOp.getValueType() == VT)
2701 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2702 "Invalid TRUNCATE!");
2703 if (Operand.getValueType() == VT) return Operand; // noop truncate
2704 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2705 "Invalid truncate node, src < dst!");
2706 assert((!VT.isVector() ||
2707 VT.getVectorNumElements() ==
2708 Operand.getValueType().getVectorNumElements()) &&
2709 "Vector element count mismatch!");
2710 if (OpOpcode == ISD::TRUNCATE)
2711 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2712 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2713 OpOpcode == ISD::ANY_EXTEND) {
2714 // If the source is smaller than the dest, we still need an extend.
2715 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2716 .bitsLT(VT.getScalarType()))
2717 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2718 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2719 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2720 return Operand.getNode()->getOperand(0);
2722 if (OpOpcode == ISD::UNDEF)
2723 return getUNDEF(VT);
2726 // Basic sanity checking.
2727 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2728 && "Cannot BITCAST between types of different sizes!");
2729 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2730 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2731 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2732 if (OpOpcode == ISD::UNDEF)
2733 return getUNDEF(VT);
2735 case ISD::SCALAR_TO_VECTOR:
2736 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2737 (VT.getVectorElementType() == Operand.getValueType() ||
2738 (VT.getVectorElementType().isInteger() &&
2739 Operand.getValueType().isInteger() &&
2740 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2741 "Illegal SCALAR_TO_VECTOR node!");
2742 if (OpOpcode == ISD::UNDEF)
2743 return getUNDEF(VT);
2744 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2745 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2746 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2747 Operand.getConstantOperandVal(1) == 0 &&
2748 Operand.getOperand(0).getValueType() == VT)
2749 return Operand.getOperand(0);
2752 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2753 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2754 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2755 Operand.getNode()->getOperand(0));
2756 if (OpOpcode == ISD::FNEG) // --X -> X
2757 return Operand.getNode()->getOperand(0);
2760 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2761 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2766 SDVTList VTs = getVTList(VT);
2767 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2768 FoldingSetNodeID ID;
2769 SDValue Ops[1] = { Operand };
2770 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2772 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2773 return SDValue(E, 0);
2775 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2776 DL.getDebugLoc(), VTs, Operand);
2777 CSEMap.InsertNode(N, IP);
2779 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2780 DL.getDebugLoc(), VTs, Operand);
2783 AllNodes.push_back(N);
2787 return SDValue(N, 0);
2790 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2791 SDNode *Cst1, SDNode *Cst2) {
2792 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2793 SmallVector<SDValue, 4> Outputs;
2794 EVT SVT = VT.getScalarType();
2796 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2797 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2798 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2801 if (Scalar1 && Scalar2)
2802 // Scalar instruction.
2803 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2805 // For vectors extract each constant element into Inputs so we can constant
2806 // fold them individually.
2807 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2808 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2812 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2814 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2815 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2816 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2817 if (!V1 || !V2) // Not a constant, bail.
2820 if (V1->isOpaque() || V2->isOpaque())
2823 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2824 // FIXME: This is valid and could be handled by truncating the APInts.
2825 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2828 Inputs.push_back(std::make_pair(V1, V2));
2832 // We have a number of constant values, constant fold them element by element.
2833 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2834 const APInt &C1 = Inputs[I].first->getAPIntValue();
2835 const APInt &C2 = Inputs[I].second->getAPIntValue();
2839 Outputs.push_back(getConstant(C1 + C2, SVT));
2842 Outputs.push_back(getConstant(C1 - C2, SVT));
2845 Outputs.push_back(getConstant(C1 * C2, SVT));
2848 if (!C2.getBoolValue())
2850 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2853 if (!C2.getBoolValue())
2855 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2858 if (!C2.getBoolValue())
2860 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2863 if (!C2.getBoolValue())
2865 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2868 Outputs.push_back(getConstant(C1 & C2, SVT));
2871 Outputs.push_back(getConstant(C1 | C2, SVT));
2874 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2877 Outputs.push_back(getConstant(C1 << C2, SVT));
2880 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2883 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2886 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2889 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2896 // Handle the scalar case first.
2897 if (Scalar1 && Scalar2)
2898 return Outputs.back();
2900 // Otherwise build a big vector out of the scalar elements we generated.
2901 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2905 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2907 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2908 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2911 case ISD::TokenFactor:
2912 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2913 N2.getValueType() == MVT::Other && "Invalid token factor!");
2914 // Fold trivial token factors.
2915 if (N1.getOpcode() == ISD::EntryToken) return N2;
2916 if (N2.getOpcode() == ISD::EntryToken) return N1;
2917 if (N1 == N2) return N1;
2919 case ISD::CONCAT_VECTORS:
2920 // Concat of UNDEFs is UNDEF.
2921 if (N1.getOpcode() == ISD::UNDEF &&
2922 N2.getOpcode() == ISD::UNDEF)
2923 return getUNDEF(VT);
2925 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2926 // one big BUILD_VECTOR.
2927 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2928 N2.getOpcode() == ISD::BUILD_VECTOR) {
2929 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2930 N1.getNode()->op_end());
2931 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2932 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2936 assert(VT.isInteger() && "This operator does not apply to FP types!");
2937 assert(N1.getValueType() == N2.getValueType() &&
2938 N1.getValueType() == VT && "Binary operator types must match!");
2939 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2940 // worth handling here.
2941 if (N2C && N2C->isNullValue())
2943 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2950 assert(VT.isInteger() && "This operator does not apply to FP types!");
2951 assert(N1.getValueType() == N2.getValueType() &&
2952 N1.getValueType() == VT && "Binary operator types must match!");
2953 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2954 // it's worth handling here.
2955 if (N2C && N2C->isNullValue())
2965 assert(VT.isInteger() && "This operator does not apply to FP types!");
2966 assert(N1.getValueType() == N2.getValueType() &&
2967 N1.getValueType() == VT && "Binary operator types must match!");
2974 if (getTarget().Options.UnsafeFPMath) {
2975 if (Opcode == ISD::FADD) {
2977 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2978 if (CFP->getValueAPF().isZero())
2981 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2982 if (CFP->getValueAPF().isZero())
2984 } else if (Opcode == ISD::FSUB) {
2986 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2987 if (CFP->getValueAPF().isZero())
2989 } else if (Opcode == ISD::FMUL) {
2990 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2993 // If the first operand isn't the constant, try the second
2995 CFP = dyn_cast<ConstantFPSDNode>(N2);
3002 return SDValue(CFP,0);
3004 if (CFP->isExactlyValue(1.0))
3009 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3010 assert(N1.getValueType() == N2.getValueType() &&
3011 N1.getValueType() == VT && "Binary operator types must match!");
3013 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3014 assert(N1.getValueType() == VT &&
3015 N1.getValueType().isFloatingPoint() &&
3016 N2.getValueType().isFloatingPoint() &&
3017 "Invalid FCOPYSIGN!");
3024 assert(VT == N1.getValueType() &&
3025 "Shift operators return type must be the same as their first arg");
3026 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3027 "Shifts only work on integers");
3028 assert((!VT.isVector() || VT == N2.getValueType()) &&
3029 "Vector shift amounts must be in the same as their first arg");
3030 // Verify that the shift amount VT is bit enough to hold valid shift
3031 // amounts. This catches things like trying to shift an i1024 value by an
3032 // i8, which is easy to fall into in generic code that uses
3033 // TLI.getShiftAmount().
3034 assert(N2.getValueType().getSizeInBits() >=
3035 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3036 "Invalid use of small shift amount with oversized value!");
3038 // Always fold shifts of i1 values so the code generator doesn't need to
3039 // handle them. Since we know the size of the shift has to be less than the
3040 // size of the value, the shift/rotate count is guaranteed to be zero.
3043 if (N2C && N2C->isNullValue())
3046 case ISD::FP_ROUND_INREG: {
3047 EVT EVT = cast<VTSDNode>(N2)->getVT();
3048 assert(VT == N1.getValueType() && "Not an inreg round!");
3049 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3050 "Cannot FP_ROUND_INREG integer types");
3051 assert(EVT.isVector() == VT.isVector() &&
3052 "FP_ROUND_INREG type should be vector iff the operand "
3054 assert((!EVT.isVector() ||
3055 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3056 "Vector element counts must match in FP_ROUND_INREG");
3057 assert(EVT.bitsLE(VT) && "Not rounding down!");
3059 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3063 assert(VT.isFloatingPoint() &&
3064 N1.getValueType().isFloatingPoint() &&
3065 VT.bitsLE(N1.getValueType()) &&
3066 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3067 if (N1.getValueType() == VT) return N1; // noop conversion.
3069 case ISD::AssertSext:
3070 case ISD::AssertZext: {
3071 EVT EVT = cast<VTSDNode>(N2)->getVT();
3072 assert(VT == N1.getValueType() && "Not an inreg extend!");
3073 assert(VT.isInteger() && EVT.isInteger() &&
3074 "Cannot *_EXTEND_INREG FP types");
3075 assert(!EVT.isVector() &&
3076 "AssertSExt/AssertZExt type should be the vector element type "
3077 "rather than the vector type!");
3078 assert(EVT.bitsLE(VT) && "Not extending!");
3079 if (VT == EVT) return N1; // noop assertion.
3082 case ISD::SIGN_EXTEND_INREG: {
3083 EVT EVT = cast<VTSDNode>(N2)->getVT();
3084 assert(VT == N1.getValueType() && "Not an inreg extend!");
3085 assert(VT.isInteger() && EVT.isInteger() &&
3086 "Cannot *_EXTEND_INREG FP types");
3087 assert(EVT.isVector() == VT.isVector() &&
3088 "SIGN_EXTEND_INREG type should be vector iff the operand "
3090 assert((!EVT.isVector() ||
3091 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3092 "Vector element counts must match in SIGN_EXTEND_INREG");
3093 assert(EVT.bitsLE(VT) && "Not extending!");
3094 if (EVT == VT) return N1; // Not actually extending
3097 APInt Val = N1C->getAPIntValue();
3098 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3099 Val <<= Val.getBitWidth()-FromBits;
3100 Val = Val.ashr(Val.getBitWidth()-FromBits);
3101 return getConstant(Val, VT);
3105 case ISD::EXTRACT_VECTOR_ELT:
3106 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3107 if (N1.getOpcode() == ISD::UNDEF)
3108 return getUNDEF(VT);
3110 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3111 // expanding copies of large vectors from registers.
3113 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3114 N1.getNumOperands() > 0) {
3116 N1.getOperand(0).getValueType().getVectorNumElements();
3117 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3118 N1.getOperand(N2C->getZExtValue() / Factor),
3119 getConstant(N2C->getZExtValue() % Factor,
3120 N2.getValueType()));
3123 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3124 // expanding large vector constants.
3125 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3126 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3128 if (VT != Elt.getValueType())
3129 // If the vector element type is not legal, the BUILD_VECTOR operands
3130 // are promoted and implicitly truncated, and the result implicitly
3131 // extended. Make that explicit here.
3132 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3137 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3138 // operations are lowered to scalars.
3139 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3140 // If the indices are the same, return the inserted element else
3141 // if the indices are known different, extract the element from
3142 // the original vector.
3143 SDValue N1Op2 = N1.getOperand(2);
3144 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3146 if (N1Op2C && N2C) {
3147 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3148 if (VT == N1.getOperand(1).getValueType())
3149 return N1.getOperand(1);
3151 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3154 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3158 case ISD::EXTRACT_ELEMENT:
3159 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3160 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3161 (N1.getValueType().isInteger() == VT.isInteger()) &&
3162 N1.getValueType() != VT &&
3163 "Wrong types for EXTRACT_ELEMENT!");
3165 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3166 // 64-bit integers into 32-bit parts. Instead of building the extract of
3167 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3168 if (N1.getOpcode() == ISD::BUILD_PAIR)
3169 return N1.getOperand(N2C->getZExtValue());
3171 // EXTRACT_ELEMENT of a constant int is also very common.
3172 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3173 unsigned ElementSize = VT.getSizeInBits();
3174 unsigned Shift = ElementSize * N2C->getZExtValue();
3175 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3176 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3179 case ISD::EXTRACT_SUBVECTOR: {
3181 if (VT.isSimple() && N1.getValueType().isSimple()) {
3182 assert(VT.isVector() && N1.getValueType().isVector() &&
3183 "Extract subvector VTs must be a vectors!");
3184 assert(VT.getVectorElementType() ==
3185 N1.getValueType().getVectorElementType() &&
3186 "Extract subvector VTs must have the same element type!");
3187 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3188 "Extract subvector must be from larger vector to smaller vector!");
3190 if (isa<ConstantSDNode>(Index.getNode())) {
3191 assert((VT.getVectorNumElements() +
3192 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3193 <= N1.getValueType().getVectorNumElements())
3194 && "Extract subvector overflow!");
3197 // Trivial extraction.
3198 if (VT.getSimpleVT() == N1.getSimpleValueType())
3205 // Perform trivial constant folding.
3206 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3207 if (SV.getNode()) return SV;
3209 // Canonicalize constant to RHS if commutative.
3210 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3211 std::swap(N1C, N2C);
3215 // Constant fold FP operations.
3216 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3217 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3219 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3220 // Canonicalize constant to RHS if commutative.
3221 std::swap(N1CFP, N2CFP);
3224 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3225 APFloat::opStatus s;
3228 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3229 if (s != APFloat::opInvalidOp)
3230 return getConstantFP(V1, VT);
3233 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3234 if (s!=APFloat::opInvalidOp)
3235 return getConstantFP(V1, VT);
3238 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3239 if (s!=APFloat::opInvalidOp)
3240 return getConstantFP(V1, VT);
3243 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3244 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3245 return getConstantFP(V1, VT);
3248 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3249 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3250 return getConstantFP(V1, VT);
3252 case ISD::FCOPYSIGN:
3254 return getConstantFP(V1, VT);
3259 if (Opcode == ISD::FP_ROUND) {
3260 APFloat V = N1CFP->getValueAPF(); // make copy
3262 // This can return overflow, underflow, or inexact; we don't care.
3263 // FIXME need to be more flexible about rounding mode.
3264 (void)V.convert(EVTToAPFloatSemantics(VT),
3265 APFloat::rmNearestTiesToEven, &ignored);
3266 return getConstantFP(V, VT);
3270 // Canonicalize an UNDEF to the RHS, even over a constant.
3271 if (N1.getOpcode() == ISD::UNDEF) {
3272 if (isCommutativeBinOp(Opcode)) {
3276 case ISD::FP_ROUND_INREG:
3277 case ISD::SIGN_EXTEND_INREG:
3283 return N1; // fold op(undef, arg2) -> undef
3291 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3292 // For vectors, we can't easily build an all zero vector, just return
3299 // Fold a bunch of operators when the RHS is undef.
3300 if (N2.getOpcode() == ISD::UNDEF) {
3303 if (N1.getOpcode() == ISD::UNDEF)
3304 // Handle undef ^ undef -> 0 special case. This is a common
3306 return getConstant(0, VT);
3316 return N2; // fold op(arg1, undef) -> undef
3322 if (getTarget().Options.UnsafeFPMath)
3330 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3331 // For vectors, we can't easily build an all zero vector, just return
3336 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3337 // For vectors, we can't easily build an all one vector, just return
3345 // Memoize this node if possible.
3347 SDVTList VTs = getVTList(VT);
3348 if (VT != MVT::Glue) {
3349 SDValue Ops[] = { N1, N2 };
3350 FoldingSetNodeID ID;
3351 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3353 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3354 return SDValue(E, 0);
3356 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3357 DL.getDebugLoc(), VTs, N1, N2);
3358 CSEMap.InsertNode(N, IP);
3360 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3361 DL.getDebugLoc(), VTs, N1, N2);
3364 AllNodes.push_back(N);
3368 return SDValue(N, 0);
3371 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3372 SDValue N1, SDValue N2, SDValue N3) {
3373 // Perform various simplifications.
3374 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3377 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3378 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3379 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3380 if (N1CFP && N2CFP && N3CFP) {
3381 APFloat V1 = N1CFP->getValueAPF();
3382 const APFloat &V2 = N2CFP->getValueAPF();
3383 const APFloat &V3 = N3CFP->getValueAPF();
3384 APFloat::opStatus s =
3385 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3386 if (s != APFloat::opInvalidOp)
3387 return getConstantFP(V1, VT);
3391 case ISD::CONCAT_VECTORS:
3392 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3393 // one big BUILD_VECTOR.
3394 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3395 N2.getOpcode() == ISD::BUILD_VECTOR &&
3396 N3.getOpcode() == ISD::BUILD_VECTOR) {
3397 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3398 N1.getNode()->op_end());
3399 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3400 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3401 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3405 // Use FoldSetCC to simplify SETCC's.
3406 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3407 if (Simp.getNode()) return Simp;
3412 if (N1C->getZExtValue())
3413 return N2; // select true, X, Y -> X
3414 return N3; // select false, X, Y -> Y
3417 if (N2 == N3) return N2; // select C, X, X -> X
3419 case ISD::VECTOR_SHUFFLE:
3420 llvm_unreachable("should use getVectorShuffle constructor!");
3421 case ISD::INSERT_SUBVECTOR: {
3423 if (VT.isSimple() && N1.getValueType().isSimple()
3424 && N2.getValueType().isSimple()) {
3425 assert(VT.isVector() && N1.getValueType().isVector() &&
3426 N2.getValueType().isVector() &&
3427 "Insert subvector VTs must be a vectors");
3428 assert(VT == N1.getValueType() &&
3429 "Dest and insert subvector source types must match!");
3430 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3431 "Insert subvector must be from smaller vector to larger vector!");
3432 if (isa<ConstantSDNode>(Index.getNode())) {
3433 assert((N2.getValueType().getVectorNumElements() +
3434 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3435 <= VT.getVectorNumElements())
3436 && "Insert subvector overflow!");
3439 // Trivial insertion.
3440 if (VT.getSimpleVT() == N2.getSimpleValueType())
3446 // Fold bit_convert nodes from a type to themselves.
3447 if (N1.getValueType() == VT)
3452 // Memoize node if it doesn't produce a flag.
3454 SDVTList VTs = getVTList(VT);
3455 if (VT != MVT::Glue) {
3456 SDValue Ops[] = { N1, N2, N3 };
3457 FoldingSetNodeID ID;
3458 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3460 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3461 return SDValue(E, 0);
3463 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3464 DL.getDebugLoc(), VTs, N1, N2, N3);
3465 CSEMap.InsertNode(N, IP);
3467 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3468 DL.getDebugLoc(), VTs, N1, N2, N3);
3471 AllNodes.push_back(N);
3475 return SDValue(N, 0);
3478 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3479 SDValue N1, SDValue N2, SDValue N3,
3481 SDValue Ops[] = { N1, N2, N3, N4 };
3482 return getNode(Opcode, DL, VT, Ops, 4);
3485 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3486 SDValue N1, SDValue N2, SDValue N3,
3487 SDValue N4, SDValue N5) {
3488 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3489 return getNode(Opcode, DL, VT, Ops, 5);
3492 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3493 /// the incoming stack arguments to be loaded from the stack.
3494 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3495 SmallVector<SDValue, 8> ArgChains;
3497 // Include the original chain at the beginning of the list. When this is
3498 // used by target LowerCall hooks, this helps legalize find the
3499 // CALLSEQ_BEGIN node.
3500 ArgChains.push_back(Chain);
3502 // Add a chain value for each stack argument.
3503 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3504 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3505 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3506 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3507 if (FI->getIndex() < 0)
3508 ArgChains.push_back(SDValue(L, 1));
3510 // Build a tokenfactor for all the chains.
3511 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3512 &ArgChains[0], ArgChains.size());
3515 /// getMemsetValue - Vectorized representation of the memset value
3517 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3519 assert(Value.getOpcode() != ISD::UNDEF);
3521 unsigned NumBits = VT.getScalarType().getSizeInBits();
3522 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3523 assert(C->getAPIntValue().getBitWidth() == 8);
3524 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3526 return DAG.getConstant(Val, VT);
3527 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3530 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3532 // Use a multiplication with 0x010101... to extend the input to the
3534 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3535 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3541 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3542 /// used when a memcpy is turned into a memset when the source is a constant
3544 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3545 const TargetLowering &TLI, StringRef Str) {
3546 // Handle vector with all elements zero.
3549 return DAG.getConstant(0, VT);
3550 else if (VT == MVT::f32 || VT == MVT::f64)
3551 return DAG.getConstantFP(0.0, VT);
3552 else if (VT.isVector()) {
3553 unsigned NumElts = VT.getVectorNumElements();
3554 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3555 return DAG.getNode(ISD::BITCAST, dl, VT,
3556 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3559 llvm_unreachable("Expected type!");
3562 assert(!VT.isVector() && "Can't handle vector type here!");
3563 unsigned NumVTBits = VT.getSizeInBits();
3564 unsigned NumVTBytes = NumVTBits / 8;
3565 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3567 APInt Val(NumVTBits, 0);
3568 if (TLI.isLittleEndian()) {
3569 for (unsigned i = 0; i != NumBytes; ++i)
3570 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3572 for (unsigned i = 0; i != NumBytes; ++i)
3573 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3576 // If the "cost" of materializing the integer immediate is less than the cost
3577 // of a load, then it is cost effective to turn the load into the immediate.
3578 const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
3579 if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) <
3580 TargetTransformInfo::TCC_Load)
3581 return DAG.getConstant(Val, VT);
3582 return SDValue(0, 0);
3585 /// getMemBasePlusOffset - Returns base and offset node for the
3587 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3588 SelectionDAG &DAG) {
3589 EVT VT = Base.getValueType();
3590 return DAG.getNode(ISD::ADD, dl,
3591 VT, Base, DAG.getConstant(Offset, VT));
3594 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3596 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3597 unsigned SrcDelta = 0;
3598 GlobalAddressSDNode *G = NULL;
3599 if (Src.getOpcode() == ISD::GlobalAddress)
3600 G = cast<GlobalAddressSDNode>(Src);
3601 else if (Src.getOpcode() == ISD::ADD &&
3602 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3603 Src.getOperand(1).getOpcode() == ISD::Constant) {
3604 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3605 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3610 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3613 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3614 /// to replace the memset / memcpy. Return true if the number of memory ops
3615 /// is below the threshold. It returns the types of the sequence of
3616 /// memory ops to perform memset / memcpy by reference.
3617 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3618 unsigned Limit, uint64_t Size,
3619 unsigned DstAlign, unsigned SrcAlign,
3625 const TargetLowering &TLI) {
3626 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3627 "Expecting memcpy / memset source to meet alignment requirement!");
3628 // If 'SrcAlign' is zero, that means the memory operation does not need to
3629 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3630 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3631 // is the specified alignment of the memory operation. If it is zero, that
3632 // means it's possible to change the alignment of the destination.
3633 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3634 // not need to be loaded.
3635 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3636 IsMemset, ZeroMemset, MemcpyStrSrc,
3637 DAG.getMachineFunction());
3639 if (VT == MVT::Other) {
3640 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3641 TLI.allowsUnalignedMemoryAccesses(VT)) {
3642 VT = TLI.getPointerTy();
3644 switch (DstAlign & 7) {
3645 case 0: VT = MVT::i64; break;
3646 case 4: VT = MVT::i32; break;
3647 case 2: VT = MVT::i16; break;
3648 default: VT = MVT::i8; break;
3653 while (!TLI.isTypeLegal(LVT))
3654 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3655 assert(LVT.isInteger());
3661 unsigned NumMemOps = 0;
3663 unsigned VTSize = VT.getSizeInBits() / 8;
3664 while (VTSize > Size) {
3665 // For now, only use non-vector load / store's for the left-over pieces.
3670 if (VT.isVector() || VT.isFloatingPoint()) {
3671 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3672 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3673 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3675 else if (NewVT == MVT::i64 &&
3676 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3677 TLI.isSafeMemOpType(MVT::f64)) {
3678 // i64 is usually not legal on 32-bit targets, but f64 may be.
3686 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3687 if (NewVT == MVT::i8)
3689 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3691 NewVTSize = NewVT.getSizeInBits() / 8;
3693 // If the new VT cannot cover all of the remaining bits, then consider
3694 // issuing a (or a pair of) unaligned and overlapping load / store.
3695 // FIXME: Only does this for 64-bit or more since we don't have proper
3696 // cost model for unaligned load / store.
3698 if (NumMemOps && AllowOverlap &&
3699 VTSize >= 8 && NewVTSize < Size &&
3700 TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3708 if (++NumMemOps > Limit)
3711 MemOps.push_back(VT);
3718 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3719 SDValue Chain, SDValue Dst,
3720 SDValue Src, uint64_t Size,
3721 unsigned Align, bool isVol,
3723 MachinePointerInfo DstPtrInfo,
3724 MachinePointerInfo SrcPtrInfo) {
3725 // Turn a memcpy of undef to nop.
3726 if (Src.getOpcode() == ISD::UNDEF)
3729 // Expand memcpy to a series of load and store ops if the size operand falls
3730 // below a certain threshold.
3731 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3732 // rather than maybe a humongous number of loads and stores.
3733 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3734 std::vector<EVT> MemOps;
3735 bool DstAlignCanChange = false;
3736 MachineFunction &MF = DAG.getMachineFunction();
3737 MachineFrameInfo *MFI = MF.getFrameInfo();
3739 MF.getFunction()->getAttributes().
3740 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3741 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3742 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3743 DstAlignCanChange = true;
3744 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3745 if (Align > SrcAlign)
3748 bool CopyFromStr = isMemSrcFromString(Src, Str);
3749 bool isZeroStr = CopyFromStr && Str.empty();
3750 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3752 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3753 (DstAlignCanChange ? 0 : Align),
3754 (isZeroStr ? 0 : SrcAlign),
3755 false, false, CopyFromStr, true, DAG, TLI))
3758 if (DstAlignCanChange) {
3759 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3760 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3762 // Don't promote to an alignment that would require dynamic stack
3764 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3765 if (!TRI->needsStackRealignment(MF))
3766 while (NewAlign > Align &&
3767 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3770 if (NewAlign > Align) {
3771 // Give the stack frame object a larger alignment if needed.
3772 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3773 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3778 SmallVector<SDValue, 8> OutChains;
3779 unsigned NumMemOps = MemOps.size();
3780 uint64_t SrcOff = 0, DstOff = 0;
3781 for (unsigned i = 0; i != NumMemOps; ++i) {
3783 unsigned VTSize = VT.getSizeInBits() / 8;
3784 SDValue Value, Store;
3786 if (VTSize > Size) {
3787 // Issuing an unaligned load / store pair that overlaps with the previous
3788 // pair. Adjust the offset accordingly.
3789 assert(i == NumMemOps-1 && i != 0);
3790 SrcOff -= VTSize - Size;
3791 DstOff -= VTSize - Size;
3795 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3796 // It's unlikely a store of a vector immediate can be done in a single
3797 // instruction. It would require a load from a constantpool first.
3798 // We only handle zero vectors here.
3799 // FIXME: Handle other cases where store of vector immediate is done in
3800 // a single instruction.
3801 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3802 if (Value.getNode())
3803 Store = DAG.getStore(Chain, dl, Value,
3804 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3805 DstPtrInfo.getWithOffset(DstOff), isVol,
3809 if (!Store.getNode()) {
3810 // The type might not be legal for the target. This should only happen
3811 // if the type is smaller than a legal type, as on PPC, so the right
3812 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3813 // to Load/Store if NVT==VT.
3814 // FIXME does the case above also need this?
3815 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3816 assert(NVT.bitsGE(VT));
3817 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3818 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3819 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3820 MinAlign(SrcAlign, SrcOff));
3821 Store = DAG.getTruncStore(Chain, dl, Value,
3822 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3823 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3826 OutChains.push_back(Store);
3832 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3833 &OutChains[0], OutChains.size());
3836 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3837 SDValue Chain, SDValue Dst,
3838 SDValue Src, uint64_t Size,
3839 unsigned Align, bool isVol,
3841 MachinePointerInfo DstPtrInfo,
3842 MachinePointerInfo SrcPtrInfo) {
3843 // Turn a memmove of undef to nop.
3844 if (Src.getOpcode() == ISD::UNDEF)
3847 // Expand memmove to a series of load and store ops if the size operand falls
3848 // below a certain threshold.
3849 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3850 std::vector<EVT> MemOps;
3851 bool DstAlignCanChange = false;
3852 MachineFunction &MF = DAG.getMachineFunction();
3853 MachineFrameInfo *MFI = MF.getFrameInfo();
3854 bool OptSize = MF.getFunction()->getAttributes().
3855 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3856 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3857 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3858 DstAlignCanChange = true;
3859 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3860 if (Align > SrcAlign)
3862 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3864 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3865 (DstAlignCanChange ? 0 : Align), SrcAlign,
3866 false, false, false, false, DAG, TLI))
3869 if (DstAlignCanChange) {
3870 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3871 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3872 if (NewAlign > Align) {
3873 // Give the stack frame object a larger alignment if needed.
3874 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3875 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3880 uint64_t SrcOff = 0, DstOff = 0;
3881 SmallVector<SDValue, 8> LoadValues;
3882 SmallVector<SDValue, 8> LoadChains;
3883 SmallVector<SDValue, 8> OutChains;
3884 unsigned NumMemOps = MemOps.size();
3885 for (unsigned i = 0; i < NumMemOps; i++) {
3887 unsigned VTSize = VT.getSizeInBits() / 8;
3890 Value = DAG.getLoad(VT, dl, Chain,
3891 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3892 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3893 false, false, SrcAlign);
3894 LoadValues.push_back(Value);
3895 LoadChains.push_back(Value.getValue(1));
3898 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3899 &LoadChains[0], LoadChains.size());
3901 for (unsigned i = 0; i < NumMemOps; i++) {
3903 unsigned VTSize = VT.getSizeInBits() / 8;
3906 Store = DAG.getStore(Chain, dl, LoadValues[i],
3907 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3908 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3909 OutChains.push_back(Store);
3913 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3914 &OutChains[0], OutChains.size());
3917 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3920 /// \param DAG Selection DAG where lowered code is placed.
3921 /// \param dl Link to corresponding IR location.
3922 /// \param Chain Control flow dependency.
3923 /// \param Dst Pointer to destination memory location.
3924 /// \param Src Value of byte to write into the memory.
3925 /// \param Size Number of bytes to write.
3926 /// \param Align Alignment of the destination in bytes.
3927 /// \param isVol True if destination is volatile.
3928 /// \param DstPtrInfo IR information on the memory pointer.
3929 /// \returns New head in the control flow, if lowering was successful, empty
3930 /// SDValue otherwise.
3932 /// The function tries to replace 'llvm.memset' intrinsic with several store
3933 /// operations and value calculation code. This is usually profitable for small
3935 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3936 SDValue Chain, SDValue Dst,
3937 SDValue Src, uint64_t Size,
3938 unsigned Align, bool isVol,
3939 MachinePointerInfo DstPtrInfo) {
3940 // Turn a memset of undef to nop.
3941 if (Src.getOpcode() == ISD::UNDEF)
3944 // Expand memset to a series of load/store ops if the size operand
3945 // falls below a certain threshold.
3946 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3947 std::vector<EVT> MemOps;
3948 bool DstAlignCanChange = false;
3949 MachineFunction &MF = DAG.getMachineFunction();
3950 MachineFrameInfo *MFI = MF.getFrameInfo();
3951 bool OptSize = MF.getFunction()->getAttributes().
3952 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3953 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3954 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3955 DstAlignCanChange = true;
3957 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3958 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3959 Size, (DstAlignCanChange ? 0 : Align), 0,
3960 true, IsZeroVal, false, true, DAG, TLI))
3963 if (DstAlignCanChange) {
3964 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3965 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3966 if (NewAlign > Align) {
3967 // Give the stack frame object a larger alignment if needed.
3968 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3969 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3974 SmallVector<SDValue, 8> OutChains;
3975 uint64_t DstOff = 0;
3976 unsigned NumMemOps = MemOps.size();
3978 // Find the largest store and generate the bit pattern for it.
3979 EVT LargestVT = MemOps[0];
3980 for (unsigned i = 1; i < NumMemOps; i++)
3981 if (MemOps[i].bitsGT(LargestVT))
3982 LargestVT = MemOps[i];
3983 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3985 for (unsigned i = 0; i < NumMemOps; i++) {
3987 unsigned VTSize = VT.getSizeInBits() / 8;
3988 if (VTSize > Size) {
3989 // Issuing an unaligned load / store pair that overlaps with the previous
3990 // pair. Adjust the offset accordingly.
3991 assert(i == NumMemOps-1 && i != 0);
3992 DstOff -= VTSize - Size;
3995 // If this store is smaller than the largest store see whether we can get
3996 // the smaller value for free with a truncate.
3997 SDValue Value = MemSetValue;
3998 if (VT.bitsLT(LargestVT)) {
3999 if (!LargestVT.isVector() && !VT.isVector() &&
4000 TLI.isTruncateFree(LargestVT, VT))
4001 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4003 Value = getMemsetValue(Src, VT, DAG, dl);
4005 assert(Value.getValueType() == VT && "Value with wrong type.");
4006 SDValue Store = DAG.getStore(Chain, dl, Value,
4007 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4008 DstPtrInfo.getWithOffset(DstOff),
4009 isVol, false, Align);
4010 OutChains.push_back(Store);
4011 DstOff += VT.getSizeInBits() / 8;
4015 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4016 &OutChains[0], OutChains.size());
4019 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4020 SDValue Src, SDValue Size,
4021 unsigned Align, bool isVol, bool AlwaysInline,
4022 MachinePointerInfo DstPtrInfo,
4023 MachinePointerInfo SrcPtrInfo) {
4024 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4026 // Check to see if we should lower the memcpy to loads and stores first.
4027 // For cases within the target-specified limits, this is the best choice.
4028 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4030 // Memcpy with size zero? Just return the original chain.
4031 if (ConstantSize->isNullValue())
4034 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4035 ConstantSize->getZExtValue(),Align,
4036 isVol, false, DstPtrInfo, SrcPtrInfo);
4037 if (Result.getNode())
4041 // Then check to see if we should lower the memcpy with target-specific
4042 // code. If the target chooses to do this, this is the next best.
4044 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4045 isVol, AlwaysInline,
4046 DstPtrInfo, SrcPtrInfo);
4047 if (Result.getNode())
4050 // If we really need inline code and the target declined to provide it,
4051 // use a (potentially long) sequence of loads and stores.
4053 assert(ConstantSize && "AlwaysInline requires a constant size!");
4054 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4055 ConstantSize->getZExtValue(), Align, isVol,
4056 true, DstPtrInfo, SrcPtrInfo);
4059 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4060 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4061 // respect volatile, so they may do things like read or write memory
4062 // beyond the given memory regions. But fixing this isn't easy, and most
4063 // people don't care.
4065 const TargetLowering *TLI = TM.getTargetLowering();
4067 // Emit a library call.
4068 TargetLowering::ArgListTy Args;
4069 TargetLowering::ArgListEntry Entry;
4070 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4071 Entry.Node = Dst; Args.push_back(Entry);
4072 Entry.Node = Src; Args.push_back(Entry);
4073 Entry.Node = Size; Args.push_back(Entry);
4074 // FIXME: pass in SDLoc
4076 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4077 false, false, false, false, 0,
4078 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4079 /*isTailCall=*/false,
4080 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4081 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4082 TLI->getPointerTy()),
4084 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4086 return CallResult.second;
4089 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4090 SDValue Src, SDValue Size,
4091 unsigned Align, bool isVol,
4092 MachinePointerInfo DstPtrInfo,
4093 MachinePointerInfo SrcPtrInfo) {
4094 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4096 // Check to see if we should lower the memmove to loads and stores first.
4097 // For cases within the target-specified limits, this is the best choice.
4098 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4100 // Memmove with size zero? Just return the original chain.
4101 if (ConstantSize->isNullValue())
4105 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4106 ConstantSize->getZExtValue(), Align, isVol,
4107 false, DstPtrInfo, SrcPtrInfo);
4108 if (Result.getNode())
4112 // Then check to see if we should lower the memmove with target-specific
4113 // code. If the target chooses to do this, this is the next best.
4115 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4116 DstPtrInfo, SrcPtrInfo);
4117 if (Result.getNode())
4120 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4121 // not be safe. See memcpy above for more details.
4123 const TargetLowering *TLI = TM.getTargetLowering();
4125 // Emit a library call.
4126 TargetLowering::ArgListTy Args;
4127 TargetLowering::ArgListEntry Entry;
4128 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4129 Entry.Node = Dst; Args.push_back(Entry);
4130 Entry.Node = Src; Args.push_back(Entry);
4131 Entry.Node = Size; Args.push_back(Entry);
4132 // FIXME: pass in SDLoc
4134 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4135 false, false, false, false, 0,
4136 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4137 /*isTailCall=*/false,
4138 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4139 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4140 TLI->getPointerTy()),
4142 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4144 return CallResult.second;
4147 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4148 SDValue Src, SDValue Size,
4149 unsigned Align, bool isVol,
4150 MachinePointerInfo DstPtrInfo) {
4151 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4153 // Check to see if we should lower the memset to stores first.
4154 // For cases within the target-specified limits, this is the best choice.
4155 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4157 // Memset with size zero? Just return the original chain.
4158 if (ConstantSize->isNullValue())
4162 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4163 Align, isVol, DstPtrInfo);
4165 if (Result.getNode())
4169 // Then check to see if we should lower the memset with target-specific
4170 // code. If the target chooses to do this, this is the next best.
4172 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4174 if (Result.getNode())
4177 // Emit a library call.
4178 const TargetLowering *TLI = TM.getTargetLowering();
4179 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4180 TargetLowering::ArgListTy Args;
4181 TargetLowering::ArgListEntry Entry;
4182 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4183 Args.push_back(Entry);
4184 // Extend or truncate the argument to be an i32 value for the call.
4185 if (Src.getValueType().bitsGT(MVT::i32))
4186 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4188 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4190 Entry.Ty = Type::getInt32Ty(*getContext());
4191 Entry.isSExt = true;
4192 Args.push_back(Entry);
4194 Entry.Ty = IntPtrTy;
4195 Entry.isSExt = false;
4196 Args.push_back(Entry);
4197 // FIXME: pass in SDLoc
4199 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4200 false, false, false, false, 0,
4201 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4202 /*isTailCall=*/false,
4203 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4204 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4205 TLI->getPointerTy()),
4207 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4209 return CallResult.second;
4212 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4213 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4214 MachineMemOperand *MMO,
4215 AtomicOrdering Ordering,
4216 SynchronizationScope SynchScope) {
4217 FoldingSetNodeID ID;
4218 ID.AddInteger(MemVT.getRawBits());
4219 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4220 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4222 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4223 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4224 return SDValue(E, 0);
4227 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4228 // SDNode doesn't have access to it. This memory will be "leaked" when
4229 // the node is deallocated, but recovered when the allocator is released.
4230 // If the number of operands is less than 5 we use AtomicSDNode's internal
4232 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4234 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4235 dl.getDebugLoc(), VTList, MemVT,
4236 Ops, DynOps, NumOps, MMO,
4237 Ordering, SynchScope);
4238 CSEMap.InsertNode(N, IP);
4239 AllNodes.push_back(N);
4240 return SDValue(N, 0);
4243 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4244 SDValue Chain, SDValue Ptr, SDValue Cmp,
4245 SDValue Swp, MachinePointerInfo PtrInfo,
4247 AtomicOrdering Ordering,
4248 SynchronizationScope SynchScope) {
4249 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4250 Alignment = getEVTAlignment(MemVT);
4252 MachineFunction &MF = getMachineFunction();
4254 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4255 // For now, atomics are considered to be volatile always.
4256 // FIXME: Volatile isn't really correct; we should keep track of atomic
4257 // orderings in the memoperand.
4258 unsigned Flags = MachineMemOperand::MOVolatile;
4259 if (Opcode != ISD::ATOMIC_STORE)
4260 Flags |= MachineMemOperand::MOLoad;
4261 if (Opcode != ISD::ATOMIC_LOAD)
4262 Flags |= MachineMemOperand::MOStore;
4264 MachineMemOperand *MMO =
4265 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4267 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4268 Ordering, SynchScope);
4271 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4273 SDValue Ptr, SDValue Cmp,
4274 SDValue Swp, MachineMemOperand *MMO,
4275 AtomicOrdering Ordering,
4276 SynchronizationScope SynchScope) {
4277 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4278 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4280 EVT VT = Cmp.getValueType();
4282 SDVTList VTs = getVTList(VT, MVT::Other);
4283 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4284 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4287 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4289 SDValue Ptr, SDValue Val,
4290 const Value* PtrVal,
4292 AtomicOrdering Ordering,
4293 SynchronizationScope SynchScope) {
4294 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4295 Alignment = getEVTAlignment(MemVT);
4297 MachineFunction &MF = getMachineFunction();
4298 // An atomic store does not load. An atomic load does not store.
4299 // (An atomicrmw obviously both loads and stores.)
4300 // For now, atomics are considered to be volatile always, and they are
4302 // FIXME: Volatile isn't really correct; we should keep track of atomic
4303 // orderings in the memoperand.
4304 unsigned Flags = MachineMemOperand::MOVolatile;
4305 if (Opcode != ISD::ATOMIC_STORE)
4306 Flags |= MachineMemOperand::MOLoad;
4307 if (Opcode != ISD::ATOMIC_LOAD)
4308 Flags |= MachineMemOperand::MOStore;
4310 MachineMemOperand *MMO =
4311 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4312 MemVT.getStoreSize(), Alignment);
4314 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4315 Ordering, SynchScope);
4318 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4320 SDValue Ptr, SDValue Val,
4321 MachineMemOperand *MMO,
4322 AtomicOrdering Ordering,
4323 SynchronizationScope SynchScope) {
4324 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4325 Opcode == ISD::ATOMIC_LOAD_SUB ||
4326 Opcode == ISD::ATOMIC_LOAD_AND ||
4327 Opcode == ISD::ATOMIC_LOAD_OR ||
4328 Opcode == ISD::ATOMIC_LOAD_XOR ||
4329 Opcode == ISD::ATOMIC_LOAD_NAND ||
4330 Opcode == ISD::ATOMIC_LOAD_MIN ||
4331 Opcode == ISD::ATOMIC_LOAD_MAX ||
4332 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4333 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4334 Opcode == ISD::ATOMIC_SWAP ||
4335 Opcode == ISD::ATOMIC_STORE) &&
4336 "Invalid Atomic Op");
4338 EVT VT = Val.getValueType();
4340 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4341 getVTList(VT, MVT::Other);
4342 SDValue Ops[] = {Chain, Ptr, Val};
4343 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4346 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4347 EVT VT, SDValue Chain,
4349 const Value* PtrVal,
4351 AtomicOrdering Ordering,
4352 SynchronizationScope SynchScope) {
4353 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4354 Alignment = getEVTAlignment(MemVT);
4356 MachineFunction &MF = getMachineFunction();
4357 // An atomic store does not load. An atomic load does not store.
4358 // (An atomicrmw obviously both loads and stores.)
4359 // For now, atomics are considered to be volatile always, and they are
4361 // FIXME: Volatile isn't really correct; we should keep track of atomic
4362 // orderings in the memoperand.
4363 unsigned Flags = MachineMemOperand::MOVolatile;
4364 if (Opcode != ISD::ATOMIC_STORE)
4365 Flags |= MachineMemOperand::MOLoad;
4366 if (Opcode != ISD::ATOMIC_LOAD)
4367 Flags |= MachineMemOperand::MOStore;
4369 MachineMemOperand *MMO =
4370 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4371 MemVT.getStoreSize(), Alignment);
4373 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4374 Ordering, SynchScope);
4377 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4378 EVT VT, SDValue Chain,
4380 MachineMemOperand *MMO,
4381 AtomicOrdering Ordering,
4382 SynchronizationScope SynchScope) {
4383 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4385 SDVTList VTs = getVTList(VT, MVT::Other);
4386 SDValue Ops[] = {Chain, Ptr};
4387 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4390 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4391 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4396 SmallVector<EVT, 4> VTs;
4397 VTs.reserve(NumOps);
4398 for (unsigned i = 0; i < NumOps; ++i)
4399 VTs.push_back(Ops[i].getValueType());
4400 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4405 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4406 const EVT *VTs, unsigned NumVTs,
4407 const SDValue *Ops, unsigned NumOps,
4408 EVT MemVT, MachinePointerInfo PtrInfo,
4409 unsigned Align, bool Vol,
4410 bool ReadMem, bool WriteMem) {
4411 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4412 MemVT, PtrInfo, Align, Vol,
4417 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4418 const SDValue *Ops, unsigned NumOps,
4419 EVT MemVT, MachinePointerInfo PtrInfo,
4420 unsigned Align, bool Vol,
4421 bool ReadMem, bool WriteMem) {
4422 if (Align == 0) // Ensure that codegen never sees alignment 0
4423 Align = getEVTAlignment(MemVT);
4425 MachineFunction &MF = getMachineFunction();
4428 Flags |= MachineMemOperand::MOStore;
4430 Flags |= MachineMemOperand::MOLoad;
4432 Flags |= MachineMemOperand::MOVolatile;
4433 MachineMemOperand *MMO =
4434 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4436 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4440 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4441 const SDValue *Ops, unsigned NumOps,
4442 EVT MemVT, MachineMemOperand *MMO) {
4443 assert((Opcode == ISD::INTRINSIC_VOID ||
4444 Opcode == ISD::INTRINSIC_W_CHAIN ||
4445 Opcode == ISD::PREFETCH ||
4446 Opcode == ISD::LIFETIME_START ||
4447 Opcode == ISD::LIFETIME_END ||
4448 (Opcode <= INT_MAX &&
4449 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4450 "Opcode is not a memory-accessing opcode!");
4452 // Memoize the node unless it returns a flag.
4453 MemIntrinsicSDNode *N;
4454 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4455 FoldingSetNodeID ID;
4456 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4457 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4459 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4460 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4461 return SDValue(E, 0);
4464 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4465 dl.getDebugLoc(), VTList, Ops,
4466 NumOps, MemVT, MMO);
4467 CSEMap.InsertNode(N, IP);
4469 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4470 dl.getDebugLoc(), VTList, Ops,
4471 NumOps, MemVT, MMO);
4473 AllNodes.push_back(N);
4474 return SDValue(N, 0);
4477 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4478 /// MachinePointerInfo record from it. This is particularly useful because the
4479 /// code generator has many cases where it doesn't bother passing in a
4480 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4481 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4482 // If this is FI+Offset, we can model it.
4483 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4484 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4486 // If this is (FI+Offset1)+Offset2, we can model it.
4487 if (Ptr.getOpcode() != ISD::ADD ||
4488 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4489 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4490 return MachinePointerInfo();
4492 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4493 return MachinePointerInfo::getFixedStack(FI, Offset+
4494 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4497 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4498 /// MachinePointerInfo record from it. This is particularly useful because the
4499 /// code generator has many cases where it doesn't bother passing in a
4500 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4501 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4502 // If the 'Offset' value isn't a constant, we can't handle this.
4503 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4504 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4505 if (OffsetOp.getOpcode() == ISD::UNDEF)
4506 return InferPointerInfo(Ptr);
4507 return MachinePointerInfo();
4512 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4513 EVT VT, SDLoc dl, SDValue Chain,
4514 SDValue Ptr, SDValue Offset,
4515 MachinePointerInfo PtrInfo, EVT MemVT,
4516 bool isVolatile, bool isNonTemporal, bool isInvariant,
4517 unsigned Alignment, const MDNode *TBAAInfo,
4518 const MDNode *Ranges) {
4519 assert(Chain.getValueType() == MVT::Other &&
4520 "Invalid chain type");
4521 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4522 Alignment = getEVTAlignment(VT);
4524 unsigned Flags = MachineMemOperand::MOLoad;
4526 Flags |= MachineMemOperand::MOVolatile;
4528 Flags |= MachineMemOperand::MONonTemporal;
4530 Flags |= MachineMemOperand::MOInvariant;
4532 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4535 PtrInfo = InferPointerInfo(Ptr, Offset);
4537 MachineFunction &MF = getMachineFunction();
4538 MachineMemOperand *MMO =
4539 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4541 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4545 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4546 EVT VT, SDLoc dl, SDValue Chain,
4547 SDValue Ptr, SDValue Offset, EVT MemVT,
4548 MachineMemOperand *MMO) {
4550 ExtType = ISD::NON_EXTLOAD;
4551 } else if (ExtType == ISD::NON_EXTLOAD) {
4552 assert(VT == MemVT && "Non-extending load from different memory type!");
4555 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4556 "Should only be an extending load, not truncating!");
4557 assert(VT.isInteger() == MemVT.isInteger() &&
4558 "Cannot convert from FP to Int or Int -> FP!");
4559 assert(VT.isVector() == MemVT.isVector() &&
4560 "Cannot use trunc store to convert to or from a vector!");
4561 assert((!VT.isVector() ||
4562 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4563 "Cannot use trunc store to change the number of vector elements!");
4566 bool Indexed = AM != ISD::UNINDEXED;
4567 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4568 "Unindexed load with an offset!");
4570 SDVTList VTs = Indexed ?
4571 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4572 SDValue Ops[] = { Chain, Ptr, Offset };
4573 FoldingSetNodeID ID;
4574 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4575 ID.AddInteger(MemVT.getRawBits());
4576 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4577 MMO->isNonTemporal(),
4578 MMO->isInvariant()));
4579 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4581 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4582 cast<LoadSDNode>(E)->refineAlignment(MMO);
4583 return SDValue(E, 0);
4585 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4586 dl.getDebugLoc(), VTs, AM, ExtType,
4588 CSEMap.InsertNode(N, IP);
4589 AllNodes.push_back(N);
4590 return SDValue(N, 0);
4593 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4594 SDValue Chain, SDValue Ptr,
4595 MachinePointerInfo PtrInfo,
4596 bool isVolatile, bool isNonTemporal,
4597 bool isInvariant, unsigned Alignment,
4598 const MDNode *TBAAInfo,
4599 const MDNode *Ranges) {
4600 SDValue Undef = getUNDEF(Ptr.getValueType());
4601 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4602 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4606 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4607 SDValue Chain, SDValue Ptr,
4608 MachineMemOperand *MMO) {
4609 SDValue Undef = getUNDEF(Ptr.getValueType());
4610 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4614 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4615 SDValue Chain, SDValue Ptr,
4616 MachinePointerInfo PtrInfo, EVT MemVT,
4617 bool isVolatile, bool isNonTemporal,
4618 unsigned Alignment, const MDNode *TBAAInfo) {
4619 SDValue Undef = getUNDEF(Ptr.getValueType());
4620 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4621 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4626 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4627 SDValue Chain, SDValue Ptr, EVT MemVT,
4628 MachineMemOperand *MMO) {
4629 SDValue Undef = getUNDEF(Ptr.getValueType());
4630 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4635 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4636 SDValue Offset, ISD::MemIndexedMode AM) {
4637 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4638 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4639 "Load is already a indexed load!");
4640 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4641 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4642 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4643 false, LD->getAlignment());
4646 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4647 SDValue Ptr, MachinePointerInfo PtrInfo,
4648 bool isVolatile, bool isNonTemporal,
4649 unsigned Alignment, const MDNode *TBAAInfo) {
4650 assert(Chain.getValueType() == MVT::Other &&
4651 "Invalid chain type");
4652 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4653 Alignment = getEVTAlignment(Val.getValueType());
4655 unsigned Flags = MachineMemOperand::MOStore;
4657 Flags |= MachineMemOperand::MOVolatile;
4659 Flags |= MachineMemOperand::MONonTemporal;
4662 PtrInfo = InferPointerInfo(Ptr);
4664 MachineFunction &MF = getMachineFunction();
4665 MachineMemOperand *MMO =
4666 MF.getMachineMemOperand(PtrInfo, Flags,
4667 Val.getValueType().getStoreSize(), Alignment,
4670 return getStore(Chain, dl, Val, Ptr, MMO);
4673 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4674 SDValue Ptr, MachineMemOperand *MMO) {
4675 assert(Chain.getValueType() == MVT::Other &&
4676 "Invalid chain type");
4677 EVT VT = Val.getValueType();
4678 SDVTList VTs = getVTList(MVT::Other);
4679 SDValue Undef = getUNDEF(Ptr.getValueType());
4680 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4681 FoldingSetNodeID ID;
4682 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4683 ID.AddInteger(VT.getRawBits());
4684 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4685 MMO->isNonTemporal(), MMO->isInvariant()));
4686 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4688 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4689 cast<StoreSDNode>(E)->refineAlignment(MMO);
4690 return SDValue(E, 0);
4692 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4693 dl.getDebugLoc(), VTs,
4694 ISD::UNINDEXED, false, VT, MMO);
4695 CSEMap.InsertNode(N, IP);
4696 AllNodes.push_back(N);
4697 return SDValue(N, 0);
4700 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4701 SDValue Ptr, MachinePointerInfo PtrInfo,
4702 EVT SVT,bool isVolatile, bool isNonTemporal,
4704 const MDNode *TBAAInfo) {
4705 assert(Chain.getValueType() == MVT::Other &&
4706 "Invalid chain type");
4707 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4708 Alignment = getEVTAlignment(SVT);
4710 unsigned Flags = MachineMemOperand::MOStore;
4712 Flags |= MachineMemOperand::MOVolatile;
4714 Flags |= MachineMemOperand::MONonTemporal;
4717 PtrInfo = InferPointerInfo(Ptr);
4719 MachineFunction &MF = getMachineFunction();
4720 MachineMemOperand *MMO =
4721 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4724 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4727 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4728 SDValue Ptr, EVT SVT,
4729 MachineMemOperand *MMO) {
4730 EVT VT = Val.getValueType();
4732 assert(Chain.getValueType() == MVT::Other &&
4733 "Invalid chain type");
4735 return getStore(Chain, dl, Val, Ptr, MMO);
4737 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4738 "Should only be a truncating store, not extending!");
4739 assert(VT.isInteger() == SVT.isInteger() &&
4740 "Can't do FP-INT conversion!");
4741 assert(VT.isVector() == SVT.isVector() &&
4742 "Cannot use trunc store to convert to or from a vector!");
4743 assert((!VT.isVector() ||
4744 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4745 "Cannot use trunc store to change the number of vector elements!");
4747 SDVTList VTs = getVTList(MVT::Other);
4748 SDValue Undef = getUNDEF(Ptr.getValueType());
4749 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4750 FoldingSetNodeID ID;
4751 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4752 ID.AddInteger(SVT.getRawBits());
4753 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4754 MMO->isNonTemporal(), MMO->isInvariant()));
4755 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4757 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4758 cast<StoreSDNode>(E)->refineAlignment(MMO);
4759 return SDValue(E, 0);
4761 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4762 dl.getDebugLoc(), VTs,
4763 ISD::UNINDEXED, true, SVT, MMO);
4764 CSEMap.InsertNode(N, IP);
4765 AllNodes.push_back(N);
4766 return SDValue(N, 0);
4770 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4771 SDValue Offset, ISD::MemIndexedMode AM) {
4772 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4773 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4774 "Store is already a indexed store!");
4775 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4776 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4777 FoldingSetNodeID ID;
4778 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4779 ID.AddInteger(ST->getMemoryVT().getRawBits());
4780 ID.AddInteger(ST->getRawSubclassData());
4781 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4783 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4784 return SDValue(E, 0);
4786 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4787 dl.getDebugLoc(), VTs, AM,
4788 ST->isTruncatingStore(),
4790 ST->getMemOperand());
4791 CSEMap.InsertNode(N, IP);
4792 AllNodes.push_back(N);
4793 return SDValue(N, 0);
4796 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4797 SDValue Chain, SDValue Ptr,
4800 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4801 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4804 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4805 const SDUse *Ops, unsigned NumOps) {
4807 case 0: return getNode(Opcode, DL, VT);
4808 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4809 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4810 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4814 // Copy from an SDUse array into an SDValue array for use with
4815 // the regular getNode logic.
4816 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4817 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4820 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4821 const SDValue *Ops, unsigned NumOps) {
4823 case 0: return getNode(Opcode, DL, VT);
4824 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4825 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4826 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4832 case ISD::SELECT_CC: {
4833 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4834 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4835 "LHS and RHS of condition must have same type!");
4836 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4837 "True and False arms of SelectCC must have same type!");
4838 assert(Ops[2].getValueType() == VT &&
4839 "select_cc node must be of same type as true and false value!");
4843 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4844 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4845 "LHS/RHS of comparison should match types!");
4852 SDVTList VTs = getVTList(VT);
4854 if (VT != MVT::Glue) {
4855 FoldingSetNodeID ID;
4856 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4859 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4860 return SDValue(E, 0);
4862 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4864 CSEMap.InsertNode(N, IP);
4866 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4870 AllNodes.push_back(N);
4874 return SDValue(N, 0);
4877 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4878 ArrayRef<EVT> ResultTys,
4879 const SDValue *Ops, unsigned NumOps) {
4880 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4884 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4885 const EVT *VTs, unsigned NumVTs,
4886 const SDValue *Ops, unsigned NumOps) {
4888 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4889 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4892 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4893 const SDValue *Ops, unsigned NumOps) {
4894 if (VTList.NumVTs == 1)
4895 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4899 // FIXME: figure out how to safely handle things like
4900 // int foo(int x) { return 1 << (x & 255); }
4901 // int bar() { return foo(256); }
4902 case ISD::SRA_PARTS:
4903 case ISD::SRL_PARTS:
4904 case ISD::SHL_PARTS:
4905 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4906 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4907 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4908 else if (N3.getOpcode() == ISD::AND)
4909 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4910 // If the and is only masking out bits that cannot effect the shift,
4911 // eliminate the and.
4912 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4913 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4914 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4920 // Memoize the node unless it returns a flag.
4922 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4923 FoldingSetNodeID ID;
4924 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4926 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4927 return SDValue(E, 0);
4930 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4931 DL.getDebugLoc(), VTList, Ops[0]);
4932 } else if (NumOps == 2) {
4933 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4934 DL.getDebugLoc(), VTList, Ops[0],
4936 } else if (NumOps == 3) {
4937 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4938 DL.getDebugLoc(), VTList, Ops[0],
4941 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4942 VTList, Ops, NumOps);
4944 CSEMap.InsertNode(N, IP);
4947 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4948 DL.getDebugLoc(), VTList, Ops[0]);
4949 } else if (NumOps == 2) {
4950 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4951 DL.getDebugLoc(), VTList, Ops[0],
4953 } else if (NumOps == 3) {
4954 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4955 DL.getDebugLoc(), VTList, Ops[0],
4958 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4959 VTList, Ops, NumOps);
4962 AllNodes.push_back(N);
4966 return SDValue(N, 0);
4969 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4970 return getNode(Opcode, DL, VTList, 0, 0);
4973 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4975 SDValue Ops[] = { N1 };
4976 return getNode(Opcode, DL, VTList, Ops, 1);
4979 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4980 SDValue N1, SDValue N2) {
4981 SDValue Ops[] = { N1, N2 };
4982 return getNode(Opcode, DL, VTList, Ops, 2);
4985 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4986 SDValue N1, SDValue N2, SDValue N3) {
4987 SDValue Ops[] = { N1, N2, N3 };
4988 return getNode(Opcode, DL, VTList, Ops, 3);
4991 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4992 SDValue N1, SDValue N2, SDValue N3,
4994 SDValue Ops[] = { N1, N2, N3, N4 };
4995 return getNode(Opcode, DL, VTList, Ops, 4);
4998 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4999 SDValue N1, SDValue N2, SDValue N3,
5000 SDValue N4, SDValue N5) {
5001 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5002 return getNode(Opcode, DL, VTList, Ops, 5);
5005 SDVTList SelectionDAG::getVTList(EVT VT) {
5006 return makeVTList(SDNode::getValueTypeList(VT), 1);
5009 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5010 FoldingSetNodeID ID;
5012 ID.AddInteger(VT1.getRawBits());
5013 ID.AddInteger(VT2.getRawBits());
5016 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5017 if (Result == NULL) {
5018 EVT *Array = Allocator.Allocate<EVT>(2);
5021 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5022 VTListMap.InsertNode(Result, IP);
5024 return Result->getSDVTList();
5027 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5028 FoldingSetNodeID ID;
5030 ID.AddInteger(VT1.getRawBits());
5031 ID.AddInteger(VT2.getRawBits());
5032 ID.AddInteger(VT3.getRawBits());
5035 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5036 if (Result == NULL) {
5037 EVT *Array = Allocator.Allocate<EVT>(3);
5041 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5042 VTListMap.InsertNode(Result, IP);
5044 return Result->getSDVTList();
5047 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5048 FoldingSetNodeID ID;
5050 ID.AddInteger(VT1.getRawBits());
5051 ID.AddInteger(VT2.getRawBits());
5052 ID.AddInteger(VT3.getRawBits());
5053 ID.AddInteger(VT4.getRawBits());
5056 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5057 if (Result == NULL) {
5058 EVT *Array = Allocator.Allocate<EVT>(4);
5063 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5064 VTListMap.InsertNode(Result, IP);
5066 return Result->getSDVTList();
5069 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5070 FoldingSetNodeID ID;
5071 ID.AddInteger(NumVTs);
5072 for (unsigned index = 0; index < NumVTs; index++) {
5073 ID.AddInteger(VTs[index].getRawBits());
5077 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5078 if (Result == NULL) {
5079 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5080 std::copy(VTs, VTs + NumVTs, Array);
5081 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5082 VTListMap.InsertNode(Result, IP);
5084 return Result->getSDVTList();
5088 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5089 /// specified operands. If the resultant node already exists in the DAG,
5090 /// this does not modify the specified node, instead it returns the node that
5091 /// already exists. If the resultant node does not exist in the DAG, the
5092 /// input node is returned. As a degenerate case, if you specify the same
5093 /// input operands as the node already has, the input node is returned.
5094 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5095 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5097 // Check to see if there is no change.
5098 if (Op == N->getOperand(0)) return N;
5100 // See if the modified node already exists.
5101 void *InsertPos = 0;
5102 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5105 // Nope it doesn't. Remove the node from its current place in the maps.
5107 if (!RemoveNodeFromCSEMaps(N))
5110 // Now we update the operands.
5111 N->OperandList[0].set(Op);
5113 // If this gets put into a CSE map, add it.
5114 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5118 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5119 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5121 // Check to see if there is no change.
5122 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5123 return N; // No operands changed, just return the input node.
5125 // See if the modified node already exists.
5126 void *InsertPos = 0;
5127 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5130 // Nope it doesn't. Remove the node from its current place in the maps.
5132 if (!RemoveNodeFromCSEMaps(N))
5135 // Now we update the operands.
5136 if (N->OperandList[0] != Op1)
5137 N->OperandList[0].set(Op1);
5138 if (N->OperandList[1] != Op2)
5139 N->OperandList[1].set(Op2);
5141 // If this gets put into a CSE map, add it.
5142 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5146 SDNode *SelectionDAG::
5147 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5148 SDValue Ops[] = { Op1, Op2, Op3 };
5149 return UpdateNodeOperands(N, Ops, 3);
5152 SDNode *SelectionDAG::
5153 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5154 SDValue Op3, SDValue Op4) {
5155 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5156 return UpdateNodeOperands(N, Ops, 4);
5159 SDNode *SelectionDAG::
5160 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5161 SDValue Op3, SDValue Op4, SDValue Op5) {
5162 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5163 return UpdateNodeOperands(N, Ops, 5);
5166 SDNode *SelectionDAG::
5167 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5168 assert(N->getNumOperands() == NumOps &&
5169 "Update with wrong number of operands");
5171 // Check to see if there is no change.
5172 bool AnyChange = false;
5173 for (unsigned i = 0; i != NumOps; ++i) {
5174 if (Ops[i] != N->getOperand(i)) {
5180 // No operands changed, just return the input node.
5181 if (!AnyChange) return N;
5183 // See if the modified node already exists.
5184 void *InsertPos = 0;
5185 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5188 // Nope it doesn't. Remove the node from its current place in the maps.
5190 if (!RemoveNodeFromCSEMaps(N))
5193 // Now we update the operands.
5194 for (unsigned i = 0; i != NumOps; ++i)
5195 if (N->OperandList[i] != Ops[i])
5196 N->OperandList[i].set(Ops[i]);
5198 // If this gets put into a CSE map, add it.
5199 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5203 /// DropOperands - Release the operands and set this node to have
5205 void SDNode::DropOperands() {
5206 // Unlike the code in MorphNodeTo that does this, we don't need to
5207 // watch for dead nodes here.
5208 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5214 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5217 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5219 SDVTList VTs = getVTList(VT);
5220 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5223 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5224 EVT VT, SDValue Op1) {
5225 SDVTList VTs = getVTList(VT);
5226 SDValue Ops[] = { Op1 };
5227 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5230 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5231 EVT VT, SDValue Op1,
5233 SDVTList VTs = getVTList(VT);
5234 SDValue Ops[] = { Op1, Op2 };
5235 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5238 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5239 EVT VT, SDValue Op1,
5240 SDValue Op2, SDValue Op3) {
5241 SDVTList VTs = getVTList(VT);
5242 SDValue Ops[] = { Op1, Op2, Op3 };
5243 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5246 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5247 EVT VT, const SDValue *Ops,
5249 SDVTList VTs = getVTList(VT);
5250 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5253 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5254 EVT VT1, EVT VT2, const SDValue *Ops,
5256 SDVTList VTs = getVTList(VT1, VT2);
5257 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5260 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5262 SDVTList VTs = getVTList(VT1, VT2);
5263 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5266 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5267 EVT VT1, EVT VT2, EVT VT3,
5268 const SDValue *Ops, unsigned NumOps) {
5269 SDVTList VTs = getVTList(VT1, VT2, VT3);
5270 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5273 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5274 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5275 const SDValue *Ops, unsigned NumOps) {
5276 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5277 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5280 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5283 SDVTList VTs = getVTList(VT1, VT2);
5284 SDValue Ops[] = { Op1 };
5285 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5288 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5290 SDValue Op1, SDValue Op2) {
5291 SDVTList VTs = getVTList(VT1, VT2);
5292 SDValue Ops[] = { Op1, Op2 };
5293 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5296 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5298 SDValue Op1, SDValue Op2,
5300 SDVTList VTs = getVTList(VT1, VT2);
5301 SDValue Ops[] = { Op1, Op2, Op3 };
5302 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5305 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5306 EVT VT1, EVT VT2, EVT VT3,
5307 SDValue Op1, SDValue Op2,
5309 SDVTList VTs = getVTList(VT1, VT2, VT3);
5310 SDValue Ops[] = { Op1, Op2, Op3 };
5311 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5314 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5315 SDVTList VTs, const SDValue *Ops,
5317 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5318 // Reset the NodeID to -1.
5323 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5324 /// the line number information on the merged node since it is not possible to
5325 /// preserve the information that operation is associated with multiple lines.
5326 /// This will make the debugger working better at -O0, were there is a higher
5327 /// probability having other instructions associated with that line.
5329 /// For IROrder, we keep the smaller of the two
5330 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5331 DebugLoc NLoc = N->getDebugLoc();
5332 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5333 (OLoc.getDebugLoc() != NLoc)) {
5334 N->setDebugLoc(DebugLoc());
5336 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5337 N->setIROrder(Order);
5341 /// MorphNodeTo - This *mutates* the specified node to have the specified
5342 /// return type, opcode, and operands.
5344 /// Note that MorphNodeTo returns the resultant node. If there is already a
5345 /// node of the specified opcode and operands, it returns that node instead of
5346 /// the current one. Note that the SDLoc need not be the same.
5348 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5349 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5350 /// node, and because it doesn't require CSE recalculation for any of
5351 /// the node's users.
5353 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5354 SDVTList VTs, const SDValue *Ops,
5356 // If an identical node already exists, use it.
5358 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5359 FoldingSetNodeID ID;
5360 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5361 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5362 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5365 if (!RemoveNodeFromCSEMaps(N))
5368 // Start the morphing.
5370 N->ValueList = VTs.VTs;
5371 N->NumValues = VTs.NumVTs;
5373 // Clear the operands list, updating used nodes to remove this from their
5374 // use list. Keep track of any operands that become dead as a result.
5375 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5376 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5378 SDNode *Used = Use.getNode();
5380 if (Used->use_empty())
5381 DeadNodeSet.insert(Used);
5384 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5385 // Initialize the memory references information.
5386 MN->setMemRefs(0, 0);
5387 // If NumOps is larger than the # of operands we can have in a
5388 // MachineSDNode, reallocate the operand list.
5389 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5390 if (MN->OperandsNeedDelete)
5391 delete[] MN->OperandList;
5392 if (NumOps > array_lengthof(MN->LocalOperands))
5393 // We're creating a final node that will live unmorphed for the
5394 // remainder of the current SelectionDAG iteration, so we can allocate
5395 // the operands directly out of a pool with no recycling metadata.
5396 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5399 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5400 MN->OperandsNeedDelete = false;
5402 MN->InitOperands(MN->OperandList, Ops, NumOps);
5404 // If NumOps is larger than the # of operands we currently have, reallocate
5405 // the operand list.
5406 if (NumOps > N->NumOperands) {
5407 if (N->OperandsNeedDelete)
5408 delete[] N->OperandList;
5409 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5410 N->OperandsNeedDelete = true;
5412 N->InitOperands(N->OperandList, Ops, NumOps);
5415 // Delete any nodes that are still dead after adding the uses for the
5417 if (!DeadNodeSet.empty()) {
5418 SmallVector<SDNode *, 16> DeadNodes;
5419 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5420 E = DeadNodeSet.end(); I != E; ++I)
5421 if ((*I)->use_empty())
5422 DeadNodes.push_back(*I);
5423 RemoveDeadNodes(DeadNodes);
5427 CSEMap.InsertNode(N, IP); // Memoize the new node.
5432 /// getMachineNode - These are used for target selectors to create a new node
5433 /// with specified return type(s), MachineInstr opcode, and operands.
5435 /// Note that getMachineNode returns the resultant node. If there is already a
5436 /// node of the specified opcode and operands, it returns that node instead of
5437 /// the current one.
5439 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5440 SDVTList VTs = getVTList(VT);
5441 return getMachineNode(Opcode, dl, VTs, None);
5445 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5446 SDVTList VTs = getVTList(VT);
5447 SDValue Ops[] = { Op1 };
5448 return getMachineNode(Opcode, dl, VTs, Ops);
5452 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5453 SDValue Op1, SDValue Op2) {
5454 SDVTList VTs = getVTList(VT);
5455 SDValue Ops[] = { Op1, Op2 };
5456 return getMachineNode(Opcode, dl, VTs, Ops);
5460 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5461 SDValue Op1, SDValue Op2, SDValue Op3) {
5462 SDVTList VTs = getVTList(VT);
5463 SDValue Ops[] = { Op1, Op2, Op3 };
5464 return getMachineNode(Opcode, dl, VTs, Ops);
5468 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5469 ArrayRef<SDValue> Ops) {
5470 SDVTList VTs = getVTList(VT);
5471 return getMachineNode(Opcode, dl, VTs, Ops);
5475 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5476 SDVTList VTs = getVTList(VT1, VT2);
5477 return getMachineNode(Opcode, dl, VTs, None);
5481 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5482 EVT VT1, EVT VT2, SDValue Op1) {
5483 SDVTList VTs = getVTList(VT1, VT2);
5484 SDValue Ops[] = { Op1 };
5485 return getMachineNode(Opcode, dl, VTs, Ops);
5489 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5490 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5491 SDVTList VTs = getVTList(VT1, VT2);
5492 SDValue Ops[] = { Op1, Op2 };
5493 return getMachineNode(Opcode, dl, VTs, Ops);
5497 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5498 EVT VT1, EVT VT2, SDValue Op1,
5499 SDValue Op2, SDValue Op3) {
5500 SDVTList VTs = getVTList(VT1, VT2);
5501 SDValue Ops[] = { Op1, Op2, Op3 };
5502 return getMachineNode(Opcode, dl, VTs, Ops);
5506 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5508 ArrayRef<SDValue> Ops) {
5509 SDVTList VTs = getVTList(VT1, VT2);
5510 return getMachineNode(Opcode, dl, VTs, Ops);
5514 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5515 EVT VT1, EVT VT2, EVT VT3,
5516 SDValue Op1, SDValue Op2) {
5517 SDVTList VTs = getVTList(VT1, VT2, VT3);
5518 SDValue Ops[] = { Op1, Op2 };
5519 return getMachineNode(Opcode, dl, VTs, Ops);
5523 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5524 EVT VT1, EVT VT2, EVT VT3,
5525 SDValue Op1, SDValue Op2, SDValue Op3) {
5526 SDVTList VTs = getVTList(VT1, VT2, VT3);
5527 SDValue Ops[] = { Op1, Op2, Op3 };
5528 return getMachineNode(Opcode, dl, VTs, Ops);
5532 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5533 EVT VT1, EVT VT2, EVT VT3,
5534 ArrayRef<SDValue> Ops) {
5535 SDVTList VTs = getVTList(VT1, VT2, VT3);
5536 return getMachineNode(Opcode, dl, VTs, Ops);
5540 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5541 EVT VT2, EVT VT3, EVT VT4,
5542 ArrayRef<SDValue> Ops) {
5543 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5544 return getMachineNode(Opcode, dl, VTs, Ops);
5548 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5549 ArrayRef<EVT> ResultTys,
5550 ArrayRef<SDValue> Ops) {
5551 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5552 return getMachineNode(Opcode, dl, VTs, Ops);
5556 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5557 ArrayRef<SDValue> OpsArray) {
5558 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5561 const SDValue *Ops = OpsArray.data();
5562 unsigned NumOps = OpsArray.size();
5565 FoldingSetNodeID ID;
5566 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5568 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5569 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5573 // Allocate a new MachineSDNode.
5574 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5575 DL.getDebugLoc(), VTs);
5577 // Initialize the operands list.
5578 if (NumOps > array_lengthof(N->LocalOperands))
5579 // We're creating a final node that will live unmorphed for the
5580 // remainder of the current SelectionDAG iteration, so we can allocate
5581 // the operands directly out of a pool with no recycling metadata.
5582 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5585 N->InitOperands(N->LocalOperands, Ops, NumOps);
5586 N->OperandsNeedDelete = false;
5589 CSEMap.InsertNode(N, IP);
5591 AllNodes.push_back(N);
5593 VerifyMachineNode(N);
5598 /// getTargetExtractSubreg - A convenience function for creating
5599 /// TargetOpcode::EXTRACT_SUBREG nodes.
5601 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5603 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5604 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5605 VT, Operand, SRIdxVal);
5606 return SDValue(Subreg, 0);
5609 /// getTargetInsertSubreg - A convenience function for creating
5610 /// TargetOpcode::INSERT_SUBREG nodes.
5612 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5613 SDValue Operand, SDValue Subreg) {
5614 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5615 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5616 VT, Operand, Subreg, SRIdxVal);
5617 return SDValue(Result, 0);
5620 /// getNodeIfExists - Get the specified node if it's already available, or
5621 /// else return NULL.
5622 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5623 const SDValue *Ops, unsigned NumOps) {
5624 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5625 FoldingSetNodeID ID;
5626 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5628 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5634 /// getDbgValue - Creates a SDDbgValue node.
5637 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5638 DebugLoc DL, unsigned O) {
5639 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5643 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5644 DebugLoc DL, unsigned O) {
5645 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5649 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5650 DebugLoc DL, unsigned O) {
5651 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5656 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5657 /// pointed to by a use iterator is deleted, increment the use iterator
5658 /// so that it doesn't dangle.
5660 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5661 SDNode::use_iterator &UI;
5662 SDNode::use_iterator &UE;
5664 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5665 // Increment the iterator as needed.
5666 while (UI != UE && N == *UI)
5671 RAUWUpdateListener(SelectionDAG &d,
5672 SDNode::use_iterator &ui,
5673 SDNode::use_iterator &ue)
5674 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5679 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5680 /// This can cause recursive merging of nodes in the DAG.
5682 /// This version assumes From has a single result value.
5684 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5685 SDNode *From = FromN.getNode();
5686 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5687 "Cannot replace with this method!");
5688 assert(From != To.getNode() && "Cannot replace uses of with self");
5690 // Iterate over all the existing uses of From. New uses will be added
5691 // to the beginning of the use list, which we avoid visiting.
5692 // This specifically avoids visiting uses of From that arise while the
5693 // replacement is happening, because any such uses would be the result
5694 // of CSE: If an existing node looks like From after one of its operands
5695 // is replaced by To, we don't want to replace of all its users with To
5696 // too. See PR3018 for more info.
5697 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5698 RAUWUpdateListener Listener(*this, UI, UE);
5702 // This node is about to morph, remove its old self from the CSE maps.
5703 RemoveNodeFromCSEMaps(User);
5705 // A user can appear in a use list multiple times, and when this
5706 // happens the uses are usually next to each other in the list.
5707 // To help reduce the number of CSE recomputations, process all
5708 // the uses of this user that we can find this way.
5710 SDUse &Use = UI.getUse();
5713 } while (UI != UE && *UI == User);
5715 // Now that we have modified User, add it back to the CSE maps. If it
5716 // already exists there, recursively merge the results together.
5717 AddModifiedNodeToCSEMaps(User);
5720 // If we just RAUW'd the root, take note.
5721 if (FromN == getRoot())
5725 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5726 /// This can cause recursive merging of nodes in the DAG.
5728 /// This version assumes that for each value of From, there is a
5729 /// corresponding value in To in the same position with the same type.
5731 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5733 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5734 assert((!From->hasAnyUseOfValue(i) ||
5735 From->getValueType(i) == To->getValueType(i)) &&
5736 "Cannot use this version of ReplaceAllUsesWith!");
5739 // Handle the trivial case.
5743 // Iterate over just the existing users of From. See the comments in
5744 // the ReplaceAllUsesWith above.
5745 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5746 RAUWUpdateListener Listener(*this, UI, UE);
5750 // This node is about to morph, remove its old self from the CSE maps.
5751 RemoveNodeFromCSEMaps(User);
5753 // A user can appear in a use list multiple times, and when this
5754 // happens the uses are usually next to each other in the list.
5755 // To help reduce the number of CSE recomputations, process all
5756 // the uses of this user that we can find this way.
5758 SDUse &Use = UI.getUse();
5761 } while (UI != UE && *UI == User);
5763 // Now that we have modified User, add it back to the CSE maps. If it
5764 // already exists there, recursively merge the results together.
5765 AddModifiedNodeToCSEMaps(User);
5768 // If we just RAUW'd the root, take note.
5769 if (From == getRoot().getNode())
5770 setRoot(SDValue(To, getRoot().getResNo()));
5773 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5774 /// This can cause recursive merging of nodes in the DAG.
5776 /// This version can replace From with any result values. To must match the
5777 /// number and types of values returned by From.
5778 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5779 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5780 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5782 // Iterate over just the existing users of From. See the comments in
5783 // the ReplaceAllUsesWith above.
5784 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5785 RAUWUpdateListener Listener(*this, UI, UE);
5789 // This node is about to morph, remove its old self from the CSE maps.
5790 RemoveNodeFromCSEMaps(User);
5792 // A user can appear in a use list multiple times, and when this
5793 // happens the uses are usually next to each other in the list.
5794 // To help reduce the number of CSE recomputations, process all
5795 // the uses of this user that we can find this way.
5797 SDUse &Use = UI.getUse();
5798 const SDValue &ToOp = To[Use.getResNo()];
5801 } while (UI != UE && *UI == User);
5803 // Now that we have modified User, add it back to the CSE maps. If it
5804 // already exists there, recursively merge the results together.
5805 AddModifiedNodeToCSEMaps(User);
5808 // If we just RAUW'd the root, take note.
5809 if (From == getRoot().getNode())
5810 setRoot(SDValue(To[getRoot().getResNo()]));
5813 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5814 /// uses of other values produced by From.getNode() alone. The Deleted
5815 /// vector is handled the same way as for ReplaceAllUsesWith.
5816 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5817 // Handle the really simple, really trivial case efficiently.
5818 if (From == To) return;
5820 // Handle the simple, trivial, case efficiently.
5821 if (From.getNode()->getNumValues() == 1) {
5822 ReplaceAllUsesWith(From, To);
5826 // Iterate over just the existing users of From. See the comments in
5827 // the ReplaceAllUsesWith above.
5828 SDNode::use_iterator UI = From.getNode()->use_begin(),
5829 UE = From.getNode()->use_end();
5830 RAUWUpdateListener Listener(*this, UI, UE);
5833 bool UserRemovedFromCSEMaps = false;
5835 // A user can appear in a use list multiple times, and when this
5836 // happens the uses are usually next to each other in the list.
5837 // To help reduce the number of CSE recomputations, process all
5838 // the uses of this user that we can find this way.
5840 SDUse &Use = UI.getUse();
5842 // Skip uses of different values from the same node.
5843 if (Use.getResNo() != From.getResNo()) {
5848 // If this node hasn't been modified yet, it's still in the CSE maps,
5849 // so remove its old self from the CSE maps.
5850 if (!UserRemovedFromCSEMaps) {
5851 RemoveNodeFromCSEMaps(User);
5852 UserRemovedFromCSEMaps = true;
5857 } while (UI != UE && *UI == User);
5859 // We are iterating over all uses of the From node, so if a use
5860 // doesn't use the specific value, no changes are made.
5861 if (!UserRemovedFromCSEMaps)
5864 // Now that we have modified User, add it back to the CSE maps. If it
5865 // already exists there, recursively merge the results together.
5866 AddModifiedNodeToCSEMaps(User);
5869 // If we just RAUW'd the root, take note.
5870 if (From == getRoot())
5875 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5876 /// to record information about a use.
5883 /// operator< - Sort Memos by User.
5884 bool operator<(const UseMemo &L, const UseMemo &R) {
5885 return (intptr_t)L.User < (intptr_t)R.User;
5889 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5890 /// uses of other values produced by From.getNode() alone. The same value
5891 /// may appear in both the From and To list. The Deleted vector is
5892 /// handled the same way as for ReplaceAllUsesWith.
5893 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5896 // Handle the simple, trivial case efficiently.
5898 return ReplaceAllUsesOfValueWith(*From, *To);
5900 // Read up all the uses and make records of them. This helps
5901 // processing new uses that are introduced during the
5902 // replacement process.
5903 SmallVector<UseMemo, 4> Uses;
5904 for (unsigned i = 0; i != Num; ++i) {
5905 unsigned FromResNo = From[i].getResNo();
5906 SDNode *FromNode = From[i].getNode();
5907 for (SDNode::use_iterator UI = FromNode->use_begin(),
5908 E = FromNode->use_end(); UI != E; ++UI) {
5909 SDUse &Use = UI.getUse();
5910 if (Use.getResNo() == FromResNo) {
5911 UseMemo Memo = { *UI, i, &Use };
5912 Uses.push_back(Memo);
5917 // Sort the uses, so that all the uses from a given User are together.
5918 std::sort(Uses.begin(), Uses.end());
5920 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5921 UseIndex != UseIndexEnd; ) {
5922 // We know that this user uses some value of From. If it is the right
5923 // value, update it.
5924 SDNode *User = Uses[UseIndex].User;
5926 // This node is about to morph, remove its old self from the CSE maps.
5927 RemoveNodeFromCSEMaps(User);
5929 // The Uses array is sorted, so all the uses for a given User
5930 // are next to each other in the list.
5931 // To help reduce the number of CSE recomputations, process all
5932 // the uses of this user that we can find this way.
5934 unsigned i = Uses[UseIndex].Index;
5935 SDUse &Use = *Uses[UseIndex].Use;
5939 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5941 // Now that we have modified User, add it back to the CSE maps. If it
5942 // already exists there, recursively merge the results together.
5943 AddModifiedNodeToCSEMaps(User);
5947 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5948 /// based on their topological order. It returns the maximum id and a vector
5949 /// of the SDNodes* in assigned order by reference.
5950 unsigned SelectionDAG::AssignTopologicalOrder() {
5952 unsigned DAGSize = 0;
5954 // SortedPos tracks the progress of the algorithm. Nodes before it are
5955 // sorted, nodes after it are unsorted. When the algorithm completes
5956 // it is at the end of the list.
5957 allnodes_iterator SortedPos = allnodes_begin();
5959 // Visit all the nodes. Move nodes with no operands to the front of
5960 // the list immediately. Annotate nodes that do have operands with their
5961 // operand count. Before we do this, the Node Id fields of the nodes
5962 // may contain arbitrary values. After, the Node Id fields for nodes
5963 // before SortedPos will contain the topological sort index, and the
5964 // Node Id fields for nodes At SortedPos and after will contain the
5965 // count of outstanding operands.
5966 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5969 unsigned Degree = N->getNumOperands();
5971 // A node with no uses, add it to the result array immediately.
5972 N->setNodeId(DAGSize++);
5973 allnodes_iterator Q = N;
5975 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5976 assert(SortedPos != AllNodes.end() && "Overran node list");
5979 // Temporarily use the Node Id as scratch space for the degree count.
5980 N->setNodeId(Degree);
5984 // Visit all the nodes. As we iterate, move nodes into sorted order,
5985 // such that by the time the end is reached all nodes will be sorted.
5986 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5989 // N is in sorted position, so all its uses have one less operand
5990 // that needs to be sorted.
5991 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5994 unsigned Degree = P->getNodeId();
5995 assert(Degree != 0 && "Invalid node degree");
5998 // All of P's operands are sorted, so P may sorted now.
5999 P->setNodeId(DAGSize++);
6001 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6002 assert(SortedPos != AllNodes.end() && "Overran node list");
6005 // Update P's outstanding operand count.
6006 P->setNodeId(Degree);
6009 if (I == SortedPos) {
6012 dbgs() << "Overran sorted position:\n";
6015 llvm_unreachable(0);
6019 assert(SortedPos == AllNodes.end() &&
6020 "Topological sort incomplete!");
6021 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6022 "First node in topological sort is not the entry token!");
6023 assert(AllNodes.front().getNodeId() == 0 &&
6024 "First node in topological sort has non-zero id!");
6025 assert(AllNodes.front().getNumOperands() == 0 &&
6026 "First node in topological sort has operands!");
6027 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6028 "Last node in topologic sort has unexpected id!");
6029 assert(AllNodes.back().use_empty() &&
6030 "Last node in topologic sort has users!");
6031 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6035 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6036 /// value is produced by SD.
6037 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6038 DbgInfo->add(DB, SD, isParameter);
6040 SD->setHasDebugValue(true);
6043 /// TransferDbgValues - Transfer SDDbgValues.
6044 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6045 if (From == To || !From.getNode()->getHasDebugValue())
6047 SDNode *FromNode = From.getNode();
6048 SDNode *ToNode = To.getNode();
6049 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6050 SmallVector<SDDbgValue *, 2> ClonedDVs;
6051 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6053 SDDbgValue *Dbg = *I;
6054 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6055 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6056 Dbg->getOffset(), Dbg->getDebugLoc(),
6058 ClonedDVs.push_back(Clone);
6061 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6062 E = ClonedDVs.end(); I != E; ++I)
6063 AddDbgValue(*I, ToNode, false);
6066 //===----------------------------------------------------------------------===//
6068 //===----------------------------------------------------------------------===//
6070 HandleSDNode::~HandleSDNode() {
6074 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6075 DebugLoc DL, const GlobalValue *GA,
6076 EVT VT, int64_t o, unsigned char TF)
6077 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6081 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6082 SDValue X, unsigned SrcAS,
6084 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6085 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6087 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6088 EVT memvt, MachineMemOperand *mmo)
6089 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6090 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6091 MMO->isNonTemporal(), MMO->isInvariant());
6092 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6093 assert(isNonTemporal() == MMO->isNonTemporal() &&
6094 "Non-temporal encoding error!");
6095 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6098 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6099 const SDValue *Ops, unsigned NumOps, EVT memvt,
6100 MachineMemOperand *mmo)
6101 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6102 MemoryVT(memvt), MMO(mmo) {
6103 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6104 MMO->isNonTemporal(), MMO->isInvariant());
6105 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6106 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6109 /// Profile - Gather unique data for the node.
6111 void SDNode::Profile(FoldingSetNodeID &ID) const {
6112 AddNodeIDNode(ID, this);
6117 std::vector<EVT> VTs;
6120 VTs.reserve(MVT::LAST_VALUETYPE);
6121 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6122 VTs.push_back(MVT((MVT::SimpleValueType)i));
6127 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6128 static ManagedStatic<EVTArray> SimpleVTArray;
6129 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6131 /// getValueTypeList - Return a pointer to the specified value type.
6133 const EVT *SDNode::getValueTypeList(EVT VT) {
6134 if (VT.isExtended()) {
6135 sys::SmartScopedLock<true> Lock(*VTMutex);
6136 return &(*EVTs->insert(VT).first);
6138 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6139 "Value type out of range!");
6140 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6144 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6145 /// indicated value. This method ignores uses of other values defined by this
6147 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6148 assert(Value < getNumValues() && "Bad value!");
6150 // TODO: Only iterate over uses of a given value of the node
6151 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6152 if (UI.getUse().getResNo() == Value) {
6159 // Found exactly the right number of uses?
6164 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6165 /// value. This method ignores uses of other values defined by this operation.
6166 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6167 assert(Value < getNumValues() && "Bad value!");
6169 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6170 if (UI.getUse().getResNo() == Value)
6177 /// isOnlyUserOf - Return true if this node is the only use of N.
6179 bool SDNode::isOnlyUserOf(SDNode *N) const {
6181 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6192 /// isOperand - Return true if this node is an operand of N.
6194 bool SDValue::isOperandOf(SDNode *N) const {
6195 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6196 if (*this == N->getOperand(i))
6201 bool SDNode::isOperandOf(SDNode *N) const {
6202 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6203 if (this == N->OperandList[i].getNode())
6208 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6209 /// be a chain) reaches the specified operand without crossing any
6210 /// side-effecting instructions on any chain path. In practice, this looks
6211 /// through token factors and non-volatile loads. In order to remain efficient,
6212 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6213 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6214 unsigned Depth) const {
6215 if (*this == Dest) return true;
6217 // Don't search too deeply, we just want to be able to see through
6218 // TokenFactor's etc.
6219 if (Depth == 0) return false;
6221 // If this is a token factor, all inputs to the TF happen in parallel. If any
6222 // of the operands of the TF does not reach dest, then we cannot do the xform.
6223 if (getOpcode() == ISD::TokenFactor) {
6224 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6225 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6230 // Loads don't have side effects, look through them.
6231 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6232 if (!Ld->isVolatile())
6233 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6238 /// hasPredecessor - Return true if N is a predecessor of this node.
6239 /// N is either an operand of this node, or can be reached by recursively
6240 /// traversing up the operands.
6241 /// NOTE: This is an expensive method. Use it carefully.
6242 bool SDNode::hasPredecessor(const SDNode *N) const {
6243 SmallPtrSet<const SDNode *, 32> Visited;
6244 SmallVector<const SDNode *, 16> Worklist;
6245 return hasPredecessorHelper(N, Visited, Worklist);
6249 SDNode::hasPredecessorHelper(const SDNode *N,
6250 SmallPtrSet<const SDNode *, 32> &Visited,
6251 SmallVectorImpl<const SDNode *> &Worklist) const {
6252 if (Visited.empty()) {
6253 Worklist.push_back(this);
6255 // Take a look in the visited set. If we've already encountered this node
6256 // we needn't search further.
6257 if (Visited.count(N))
6261 // Haven't visited N yet. Continue the search.
6262 while (!Worklist.empty()) {
6263 const SDNode *M = Worklist.pop_back_val();
6264 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6265 SDNode *Op = M->getOperand(i).getNode();
6266 if (Visited.insert(Op))
6267 Worklist.push_back(Op);
6276 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6277 assert(Num < NumOperands && "Invalid child # of SDNode!");
6278 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6281 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6282 assert(N->getNumValues() == 1 &&
6283 "Can't unroll a vector with multiple results!");
6285 EVT VT = N->getValueType(0);
6286 unsigned NE = VT.getVectorNumElements();
6287 EVT EltVT = VT.getVectorElementType();
6290 SmallVector<SDValue, 8> Scalars;
6291 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6293 // If ResNE is 0, fully unroll the vector op.
6296 else if (NE > ResNE)
6300 for (i= 0; i != NE; ++i) {
6301 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6302 SDValue Operand = N->getOperand(j);
6303 EVT OperandVT = Operand.getValueType();
6304 if (OperandVT.isVector()) {
6305 // A vector operand; extract a single element.
6306 const TargetLowering *TLI = TM.getTargetLowering();
6307 EVT OperandEltVT = OperandVT.getVectorElementType();
6308 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6311 getConstant(i, TLI->getVectorIdxTy()));
6313 // A scalar operand; just use it as is.
6314 Operands[j] = Operand;
6318 switch (N->getOpcode()) {
6320 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6321 &Operands[0], Operands.size()));
6324 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6325 &Operands[0], Operands.size()));
6332 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6333 getShiftAmountOperand(Operands[0].getValueType(),
6336 case ISD::SIGN_EXTEND_INREG:
6337 case ISD::FP_ROUND_INREG: {
6338 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6339 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6341 getValueType(ExtVT)));
6346 for (; i < ResNE; ++i)
6347 Scalars.push_back(getUNDEF(EltVT));
6349 return getNode(ISD::BUILD_VECTOR, dl,
6350 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6351 &Scalars[0], Scalars.size());
6355 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6356 /// location that is 'Dist' units away from the location that the 'Base' load
6357 /// is loading from.
6358 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6359 unsigned Bytes, int Dist) const {
6360 if (LD->getChain() != Base->getChain())
6362 EVT VT = LD->getValueType(0);
6363 if (VT.getSizeInBits() / 8 != Bytes)
6366 SDValue Loc = LD->getOperand(1);
6367 SDValue BaseLoc = Base->getOperand(1);
6368 if (Loc.getOpcode() == ISD::FrameIndex) {
6369 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6371 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6372 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6373 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6374 int FS = MFI->getObjectSize(FI);
6375 int BFS = MFI->getObjectSize(BFI);
6376 if (FS != BFS || FS != (int)Bytes) return false;
6377 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6381 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6382 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6385 const GlobalValue *GV1 = NULL;
6386 const GlobalValue *GV2 = NULL;
6387 int64_t Offset1 = 0;
6388 int64_t Offset2 = 0;
6389 const TargetLowering *TLI = TM.getTargetLowering();
6390 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6391 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6392 if (isGA1 && isGA2 && GV1 == GV2)
6393 return Offset1 == (Offset2 + Dist*Bytes);
6398 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6399 /// it cannot be inferred.
6400 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6401 // If this is a GlobalAddress + cst, return the alignment.
6402 const GlobalValue *GV;
6403 int64_t GVOffset = 0;
6404 const TargetLowering *TLI = TM.getTargetLowering();
6405 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6406 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6407 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6408 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6409 TLI->getDataLayout());
6410 unsigned AlignBits = KnownZero.countTrailingOnes();
6411 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6413 return MinAlign(Align, GVOffset);
6416 // If this is a direct reference to a stack slot, use information about the
6417 // stack slot's alignment.
6418 int FrameIdx = 1 << 31;
6419 int64_t FrameOffset = 0;
6420 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6421 FrameIdx = FI->getIndex();
6422 } else if (isBaseWithConstantOffset(Ptr) &&
6423 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6425 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6426 FrameOffset = Ptr.getConstantOperandVal(1);
6429 if (FrameIdx != (1 << 31)) {
6430 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6431 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6439 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6440 /// which is split (or expanded) into two not necessarily identical pieces.
6441 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6442 // Currently all types are split in half.
6444 if (!VT.isVector()) {
6445 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6447 unsigned NumElements = VT.getVectorNumElements();
6448 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6449 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6452 return std::make_pair(LoVT, HiVT);
6455 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6457 std::pair<SDValue, SDValue>
6458 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6460 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6461 N.getValueType().getVectorNumElements() &&
6462 "More vector elements requested than available!");
6464 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6465 getConstant(0, TLI->getVectorIdxTy()));
6466 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6467 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6468 return std::make_pair(Lo, Hi);
6471 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6472 unsigned GlobalAddressSDNode::getAddressSpace() const {
6473 return getGlobal()->getType()->getAddressSpace();
6477 Type *ConstantPoolSDNode::getType() const {
6478 if (isMachineConstantPoolEntry())
6479 return Val.MachineCPVal->getType();
6480 return Val.ConstVal->getType();
6483 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6485 unsigned &SplatBitSize,
6487 unsigned MinSplatBits,
6489 EVT VT = getValueType(0);
6490 assert(VT.isVector() && "Expected a vector type");
6491 unsigned sz = VT.getSizeInBits();
6492 if (MinSplatBits > sz)
6495 SplatValue = APInt(sz, 0);
6496 SplatUndef = APInt(sz, 0);
6498 // Get the bits. Bits with undefined values (when the corresponding element
6499 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6500 // in SplatValue. If any of the values are not constant, give up and return
6502 unsigned int nOps = getNumOperands();
6503 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6504 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6506 for (unsigned j = 0; j < nOps; ++j) {
6507 unsigned i = isBigEndian ? nOps-1-j : j;
6508 SDValue OpVal = getOperand(i);
6509 unsigned BitPos = j * EltBitSize;
6511 if (OpVal.getOpcode() == ISD::UNDEF)
6512 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6513 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6514 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6515 zextOrTrunc(sz) << BitPos;
6516 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6517 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6522 // The build_vector is all constants or undefs. Find the smallest element
6523 // size that splats the vector.
6525 HasAnyUndefs = (SplatUndef != 0);
6528 unsigned HalfSize = sz / 2;
6529 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6530 APInt LowValue = SplatValue.trunc(HalfSize);
6531 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6532 APInt LowUndef = SplatUndef.trunc(HalfSize);
6534 // If the two halves do not match (ignoring undef bits), stop here.
6535 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6536 MinSplatBits > HalfSize)
6539 SplatValue = HighValue | LowValue;
6540 SplatUndef = HighUndef & LowUndef;
6549 bool BuildVectorSDNode::isConstant() const {
6550 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6551 unsigned Opc = getOperand(i).getOpcode();
6552 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6558 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6559 // Find the first non-undef value in the shuffle mask.
6561 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6564 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6566 // Make sure all remaining elements are either undef or the same as the first
6568 for (int Idx = Mask[i]; i != e; ++i)
6569 if (Mask[i] >= 0 && Mask[i] != Idx)
6575 static void checkForCyclesHelper(const SDNode *N,
6576 SmallPtrSet<const SDNode*, 32> &Visited,
6577 SmallPtrSet<const SDNode*, 32> &Checked) {
6578 // If this node has already been checked, don't check it again.
6579 if (Checked.count(N))
6582 // If a node has already been visited on this depth-first walk, reject it as
6584 if (!Visited.insert(N)) {
6585 dbgs() << "Offending node:\n";
6587 errs() << "Detected cycle in SelectionDAG\n";
6591 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6592 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6599 void llvm::checkForCycles(const llvm::SDNode *N) {
6601 assert(N && "Checking nonexistent SDNode");
6602 SmallPtrSet<const SDNode*, 32> visited;
6603 SmallPtrSet<const SDNode*, 32> checked;
6604 checkForCyclesHelper(N, visited, checked);
6608 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6609 checkForCycles(DAG->getRoot().getNode());