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:
388 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
390 case ISD::TargetConstantFP:
391 case ISD::ConstantFP: {
392 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
395 case ISD::TargetGlobalAddress:
396 case ISD::GlobalAddress:
397 case ISD::TargetGlobalTLSAddress:
398 case ISD::GlobalTLSAddress: {
399 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
400 ID.AddPointer(GA->getGlobal());
401 ID.AddInteger(GA->getOffset());
402 ID.AddInteger(GA->getTargetFlags());
403 ID.AddInteger(GA->getAddressSpace());
406 case ISD::BasicBlock:
407 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
410 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
412 case ISD::RegisterMask:
413 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
416 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
418 case ISD::FrameIndex:
419 case ISD::TargetFrameIndex:
420 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
423 case ISD::TargetJumpTable:
424 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
425 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
427 case ISD::ConstantPool:
428 case ISD::TargetConstantPool: {
429 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
430 ID.AddInteger(CP->getAlignment());
431 ID.AddInteger(CP->getOffset());
432 if (CP->isMachineConstantPoolEntry())
433 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
435 ID.AddPointer(CP->getConstVal());
436 ID.AddInteger(CP->getTargetFlags());
439 case ISD::TargetIndex: {
440 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
441 ID.AddInteger(TI->getIndex());
442 ID.AddInteger(TI->getOffset());
443 ID.AddInteger(TI->getTargetFlags());
447 const LoadSDNode *LD = cast<LoadSDNode>(N);
448 ID.AddInteger(LD->getMemoryVT().getRawBits());
449 ID.AddInteger(LD->getRawSubclassData());
450 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
454 const StoreSDNode *ST = cast<StoreSDNode>(N);
455 ID.AddInteger(ST->getMemoryVT().getRawBits());
456 ID.AddInteger(ST->getRawSubclassData());
457 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
460 case ISD::ATOMIC_CMP_SWAP:
461 case ISD::ATOMIC_SWAP:
462 case ISD::ATOMIC_LOAD_ADD:
463 case ISD::ATOMIC_LOAD_SUB:
464 case ISD::ATOMIC_LOAD_AND:
465 case ISD::ATOMIC_LOAD_OR:
466 case ISD::ATOMIC_LOAD_XOR:
467 case ISD::ATOMIC_LOAD_NAND:
468 case ISD::ATOMIC_LOAD_MIN:
469 case ISD::ATOMIC_LOAD_MAX:
470 case ISD::ATOMIC_LOAD_UMIN:
471 case ISD::ATOMIC_LOAD_UMAX:
472 case ISD::ATOMIC_LOAD:
473 case ISD::ATOMIC_STORE: {
474 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
475 ID.AddInteger(AT->getMemoryVT().getRawBits());
476 ID.AddInteger(AT->getRawSubclassData());
477 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
480 case ISD::PREFETCH: {
481 const MemSDNode *PF = cast<MemSDNode>(N);
482 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
485 case ISD::VECTOR_SHUFFLE: {
486 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
487 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
489 ID.AddInteger(SVN->getMaskElt(i));
492 case ISD::TargetBlockAddress:
493 case ISD::BlockAddress: {
494 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
495 ID.AddPointer(BA->getBlockAddress());
496 ID.AddInteger(BA->getOffset());
497 ID.AddInteger(BA->getTargetFlags());
500 } // end switch (N->getOpcode())
502 // Target specific memory nodes could also have address spaces to check.
503 if (N->isTargetMemoryOpcode())
504 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
507 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
509 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
510 AddNodeIDOpcode(ID, N->getOpcode());
511 // Add the return value info.
512 AddNodeIDValueTypes(ID, N->getVTList());
513 // Add the operand info.
514 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
516 // Handle SDNode leafs with special info.
517 AddNodeIDCustom(ID, N);
520 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
521 /// the CSE map that carries volatility, temporalness, indexing mode, and
522 /// extension/truncation information.
524 static inline unsigned
525 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
526 bool isNonTemporal, bool isInvariant) {
527 assert((ConvType & 3) == ConvType &&
528 "ConvType may not require more than 2 bits!");
529 assert((AM & 7) == AM &&
530 "AM may not require more than 3 bits!");
534 (isNonTemporal << 6) |
538 //===----------------------------------------------------------------------===//
539 // SelectionDAG Class
540 //===----------------------------------------------------------------------===//
542 /// doNotCSE - Return true if CSE should not be performed for this node.
543 static bool doNotCSE(SDNode *N) {
544 if (N->getValueType(0) == MVT::Glue)
545 return true; // Never CSE anything that produces a flag.
547 switch (N->getOpcode()) {
549 case ISD::HANDLENODE:
551 return true; // Never CSE these nodes.
554 // Check that remaining values produced are not flags.
555 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
556 if (N->getValueType(i) == MVT::Glue)
557 return true; // Never CSE anything that produces a flag.
562 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
564 void SelectionDAG::RemoveDeadNodes() {
565 // Create a dummy node (which is not added to allnodes), that adds a reference
566 // to the root node, preventing it from being deleted.
567 HandleSDNode Dummy(getRoot());
569 SmallVector<SDNode*, 128> DeadNodes;
571 // Add all obviously-dead nodes to the DeadNodes worklist.
572 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
574 DeadNodes.push_back(I);
576 RemoveDeadNodes(DeadNodes);
578 // If the root changed (e.g. it was a dead load, update the root).
579 setRoot(Dummy.getValue());
582 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
583 /// given list, and any nodes that become unreachable as a result.
584 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
586 // Process the worklist, deleting the nodes and adding their uses to the
588 while (!DeadNodes.empty()) {
589 SDNode *N = DeadNodes.pop_back_val();
591 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
592 DUL->NodeDeleted(N, 0);
594 // Take the node out of the appropriate CSE map.
595 RemoveNodeFromCSEMaps(N);
597 // Next, brutally remove the operand list. This is safe to do, as there are
598 // no cycles in the graph.
599 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
601 SDNode *Operand = Use.getNode();
604 // Now that we removed this operand, see if there are no uses of it left.
605 if (Operand->use_empty())
606 DeadNodes.push_back(Operand);
613 void SelectionDAG::RemoveDeadNode(SDNode *N){
614 SmallVector<SDNode*, 16> DeadNodes(1, N);
616 // Create a dummy node that adds a reference to the root node, preventing
617 // it from being deleted. (This matters if the root is an operand of the
619 HandleSDNode Dummy(getRoot());
621 RemoveDeadNodes(DeadNodes);
624 void SelectionDAG::DeleteNode(SDNode *N) {
625 // First take this out of the appropriate CSE map.
626 RemoveNodeFromCSEMaps(N);
628 // Finally, remove uses due to operands of this node, remove from the
629 // AllNodes list, and delete the node.
630 DeleteNodeNotInCSEMaps(N);
633 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
634 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
635 assert(N->use_empty() && "Cannot delete a node that is not dead!");
637 // Drop all of the operands and decrement used node's use counts.
643 void SelectionDAG::DeallocateNode(SDNode *N) {
644 if (N->OperandsNeedDelete)
645 delete[] N->OperandList;
647 // Set the opcode to DELETED_NODE to help catch bugs when node
648 // memory is reallocated.
649 N->NodeType = ISD::DELETED_NODE;
651 NodeAllocator.Deallocate(AllNodes.remove(N));
653 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
654 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
655 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
656 DbgVals[i]->setIsInvalidated();
659 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
660 /// correspond to it. This is useful when we're about to delete or repurpose
661 /// the node. We don't want future request for structurally identical nodes
662 /// to return N anymore.
663 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
665 switch (N->getOpcode()) {
666 case ISD::HANDLENODE: return false; // noop.
668 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
669 "Cond code doesn't exist!");
670 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
671 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
673 case ISD::ExternalSymbol:
674 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
676 case ISD::TargetExternalSymbol: {
677 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
678 Erased = TargetExternalSymbols.erase(
679 std::pair<std::string,unsigned char>(ESN->getSymbol(),
680 ESN->getTargetFlags()));
683 case ISD::VALUETYPE: {
684 EVT VT = cast<VTSDNode>(N)->getVT();
685 if (VT.isExtended()) {
686 Erased = ExtendedValueTypeNodes.erase(VT);
688 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
689 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
694 // Remove it from the CSE Map.
695 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
696 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
697 Erased = CSEMap.RemoveNode(N);
701 // Verify that the node was actually in one of the CSE maps, unless it has a
702 // flag result (which cannot be CSE'd) or is one of the special cases that are
703 // not subject to CSE.
704 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
705 !N->isMachineOpcode() && !doNotCSE(N)) {
708 llvm_unreachable("Node is not in map!");
714 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
715 /// maps and modified in place. Add it back to the CSE maps, unless an identical
716 /// node already exists, in which case transfer all its users to the existing
717 /// node. This transfer can potentially trigger recursive merging.
720 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
721 // For node types that aren't CSE'd, just act as if no identical node
724 SDNode *Existing = CSEMap.GetOrInsertNode(N);
726 // If there was already an existing matching node, use ReplaceAllUsesWith
727 // to replace the dead one with the existing one. This can cause
728 // recursive merging of other unrelated nodes down the line.
729 ReplaceAllUsesWith(N, Existing);
731 // N is now dead. Inform the listeners and delete it.
732 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
733 DUL->NodeDeleted(N, Existing);
734 DeleteNodeNotInCSEMaps(N);
739 // If the node doesn't already exist, we updated it. Inform listeners.
740 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
744 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
745 /// were replaced with those specified. If this node is never memoized,
746 /// return null, otherwise return a pointer to the slot it would take. If a
747 /// node already exists with these operands, the slot will be non-null.
748 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
753 SDValue Ops[] = { Op };
755 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
756 AddNodeIDCustom(ID, N);
757 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
761 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
762 /// were replaced with those specified. If this node is never memoized,
763 /// return null, otherwise return a pointer to the slot it would take. If a
764 /// node already exists with these operands, the slot will be non-null.
765 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
766 SDValue Op1, SDValue Op2,
771 SDValue Ops[] = { Op1, Op2 };
773 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
774 AddNodeIDCustom(ID, N);
775 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
780 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
781 /// were replaced with those specified. If this node is never memoized,
782 /// return null, otherwise return a pointer to the slot it would take. If a
783 /// node already exists with these operands, the slot will be non-null.
784 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
785 const SDValue *Ops,unsigned NumOps,
791 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
792 AddNodeIDCustom(ID, N);
793 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
798 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
799 static void VerifyNodeCommon(SDNode *N) {
800 switch (N->getOpcode()) {
803 case ISD::BUILD_PAIR: {
804 EVT VT = N->getValueType(0);
805 assert(N->getNumValues() == 1 && "Too many results!");
806 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
807 "Wrong return type!");
808 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
809 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
810 "Mismatched operand types!");
811 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
812 "Wrong operand type!");
813 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
814 "Wrong return type size");
817 case ISD::BUILD_VECTOR: {
818 assert(N->getNumValues() == 1 && "Too many results!");
819 assert(N->getValueType(0).isVector() && "Wrong return type!");
820 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
821 "Wrong number of operands!");
822 EVT EltVT = N->getValueType(0).getVectorElementType();
823 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
824 assert((I->getValueType() == EltVT ||
825 (EltVT.isInteger() && I->getValueType().isInteger() &&
826 EltVT.bitsLE(I->getValueType()))) &&
827 "Wrong operand type!");
828 assert(I->getValueType() == N->getOperand(0).getValueType() &&
829 "Operands must all have the same type");
836 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
837 static void VerifySDNode(SDNode *N) {
838 // The SDNode allocators cannot be used to allocate nodes with fields that are
839 // not present in an SDNode!
840 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
841 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
842 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
843 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
844 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
845 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
846 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
847 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
848 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
849 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
850 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
851 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
852 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
853 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
854 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
855 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
856 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
857 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
858 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
863 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
865 static void VerifyMachineNode(SDNode *N) {
866 // The MachineNode allocators cannot be used to allocate nodes with fields
867 // that are not present in a MachineNode!
868 // Currently there are no such nodes.
874 /// getEVTAlignment - Compute the default alignment value for the
877 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
878 Type *Ty = VT == MVT::iPTR ?
879 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
880 VT.getTypeForEVT(*getContext());
882 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
885 // EntryNode could meaningfully have debug info if we can find it...
886 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
887 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TTI(0), TLI(0), OptLevel(OL),
888 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
889 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
891 AllNodes.push_back(&EntryNode);
892 DbgInfo = new SDDbgInfo();
895 void SelectionDAG::init(MachineFunction &mf, const TargetTransformInfo *tti,
896 const TargetLowering *tli) {
900 Context = &mf.getFunction()->getContext();
903 SelectionDAG::~SelectionDAG() {
904 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
909 void SelectionDAG::allnodes_clear() {
910 assert(&*AllNodes.begin() == &EntryNode);
911 AllNodes.remove(AllNodes.begin());
912 while (!AllNodes.empty())
913 DeallocateNode(AllNodes.begin());
916 void SelectionDAG::clear() {
918 OperandAllocator.Reset();
921 ExtendedValueTypeNodes.clear();
922 ExternalSymbols.clear();
923 TargetExternalSymbols.clear();
924 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
925 static_cast<CondCodeSDNode*>(0));
926 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
927 static_cast<SDNode*>(0));
929 EntryNode.UseList = 0;
930 AllNodes.push_back(&EntryNode);
931 Root = getEntryNode();
935 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
936 return VT.bitsGT(Op.getValueType()) ?
937 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
938 getNode(ISD::TRUNCATE, DL, VT, Op);
941 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
942 return VT.bitsGT(Op.getValueType()) ?
943 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
944 getNode(ISD::TRUNCATE, DL, VT, Op);
947 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
948 return VT.bitsGT(Op.getValueType()) ?
949 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
950 getNode(ISD::TRUNCATE, DL, VT, Op);
953 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
954 assert(!VT.isVector() &&
955 "getZeroExtendInReg should use the vector element type instead of "
957 if (Op.getValueType() == VT) return Op;
958 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
959 APInt Imm = APInt::getLowBitsSet(BitWidth,
961 return getNode(ISD::AND, DL, Op.getValueType(), Op,
962 getConstant(Imm, Op.getValueType()));
965 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
967 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
968 EVT EltVT = VT.getScalarType();
970 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
971 return getNode(ISD::XOR, DL, VT, Val, NegOne);
974 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
975 EVT EltVT = VT.getScalarType();
976 assert((EltVT.getSizeInBits() >= 64 ||
977 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
978 "getConstant with a uint64_t value that doesn't fit in the type!");
979 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
982 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
983 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
986 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
987 assert(VT.isInteger() && "Cannot create FP integer constant!");
989 EVT EltVT = VT.getScalarType();
990 const ConstantInt *Elt = &Val;
992 const TargetLowering *TLI = TM.getTargetLowering();
994 // In some cases the vector type is legal but the element type is illegal and
995 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
996 // inserted value (the type does not need to match the vector element type).
997 // Any extra bits introduced will be truncated away.
998 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
999 TargetLowering::TypePromoteInteger) {
1000 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1001 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1002 Elt = ConstantInt::get(*getContext(), NewVal);
1004 // In other cases the element type is illegal and needs to be expanded, for
1005 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1006 // the value into n parts and use a vector type with n-times the elements.
1007 // Then bitcast to the type requested.
1008 // Legalizing constants too early makes the DAGCombiner's job harder so we
1009 // only legalize if the DAG tells us we must produce legal types.
1010 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1011 TLI->getTypeAction(*getContext(), EltVT) ==
1012 TargetLowering::TypeExpandInteger) {
1013 APInt NewVal = Elt->getValue();
1014 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1015 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1016 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1017 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1019 // Check the temporary vector is the correct size. If this fails then
1020 // getTypeToTransformTo() probably returned a type whose size (in bits)
1021 // isn't a power-of-2 factor of the requested type size.
1022 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1024 SmallVector<SDValue, 2> EltParts;
1025 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1026 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1027 .trunc(ViaEltSizeInBits),
1031 // EltParts is currently in little endian order. If we actually want
1032 // big-endian order then reverse it now.
1033 if (TLI->isBigEndian())
1034 std::reverse(EltParts.begin(), EltParts.end());
1036 // The elements must be reversed when the element order is different
1037 // to the endianness of the elements (because the BITCAST is itself a
1038 // vector shuffle in this situation). However, we do not need any code to
1039 // perform this reversal because getConstant() is producing a vector
1041 // This situation occurs in MIPS MSA.
1043 SmallVector<SDValue, 8> Ops;
1044 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1045 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1047 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1048 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1049 &Ops[0], Ops.size()));
1053 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1054 "APInt size does not match type size!");
1055 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1056 FoldingSetNodeID ID;
1057 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1061 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1063 return SDValue(N, 0);
1066 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1067 CSEMap.InsertNode(N, IP);
1068 AllNodes.push_back(N);
1071 SDValue Result(N, 0);
1072 if (VT.isVector()) {
1073 SmallVector<SDValue, 8> Ops;
1074 Ops.assign(VT.getVectorNumElements(), Result);
1075 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1080 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1081 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1085 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1086 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1089 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1090 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1092 EVT EltVT = VT.getScalarType();
1094 // Do the map lookup using the actual bit pattern for the floating point
1095 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1096 // we don't have issues with SNANs.
1097 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1098 FoldingSetNodeID ID;
1099 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1103 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1105 return SDValue(N, 0);
1108 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1109 CSEMap.InsertNode(N, IP);
1110 AllNodes.push_back(N);
1113 SDValue Result(N, 0);
1114 if (VT.isVector()) {
1115 SmallVector<SDValue, 8> Ops;
1116 Ops.assign(VT.getVectorNumElements(), Result);
1117 // FIXME SDLoc info might be appropriate here
1118 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1123 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1124 EVT EltVT = VT.getScalarType();
1125 if (EltVT==MVT::f32)
1126 return getConstantFP(APFloat((float)Val), VT, isTarget);
1127 else if (EltVT==MVT::f64)
1128 return getConstantFP(APFloat(Val), VT, isTarget);
1129 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1132 APFloat apf = APFloat(Val);
1133 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1135 return getConstantFP(apf, VT, isTarget);
1137 llvm_unreachable("Unsupported type in getConstantFP");
1140 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1141 EVT VT, int64_t Offset,
1143 unsigned char TargetFlags) {
1144 assert((TargetFlags == 0 || isTargetGA) &&
1145 "Cannot set target flags on target-independent globals");
1146 const TargetLowering *TLI = TM.getTargetLowering();
1148 // Truncate (with sign-extension) the offset value to the pointer size.
1149 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1151 Offset = SignExtend64(Offset, BitWidth);
1153 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1155 // If GV is an alias then use the aliasee for determining thread-localness.
1156 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1157 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1161 if (GVar && GVar->isThreadLocal())
1162 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1164 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1166 FoldingSetNodeID ID;
1167 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1169 ID.AddInteger(Offset);
1170 ID.AddInteger(TargetFlags);
1171 ID.AddInteger(GV->getType()->getAddressSpace());
1173 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1174 return SDValue(E, 0);
1176 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1177 DL.getDebugLoc(), GV, VT,
1178 Offset, TargetFlags);
1179 CSEMap.InsertNode(N, IP);
1180 AllNodes.push_back(N);
1181 return SDValue(N, 0);
1184 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1185 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1186 FoldingSetNodeID ID;
1187 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1190 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1191 return SDValue(E, 0);
1193 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1194 CSEMap.InsertNode(N, IP);
1195 AllNodes.push_back(N);
1196 return SDValue(N, 0);
1199 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1200 unsigned char TargetFlags) {
1201 assert((TargetFlags == 0 || isTarget) &&
1202 "Cannot set target flags on target-independent jump tables");
1203 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1204 FoldingSetNodeID ID;
1205 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1207 ID.AddInteger(TargetFlags);
1209 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1210 return SDValue(E, 0);
1212 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1214 CSEMap.InsertNode(N, IP);
1215 AllNodes.push_back(N);
1216 return SDValue(N, 0);
1219 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1220 unsigned Alignment, int Offset,
1222 unsigned char TargetFlags) {
1223 assert((TargetFlags == 0 || isTarget) &&
1224 "Cannot set target flags on target-independent globals");
1227 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1228 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1229 FoldingSetNodeID ID;
1230 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1231 ID.AddInteger(Alignment);
1232 ID.AddInteger(Offset);
1234 ID.AddInteger(TargetFlags);
1236 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1237 return SDValue(E, 0);
1239 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1240 Alignment, TargetFlags);
1241 CSEMap.InsertNode(N, IP);
1242 AllNodes.push_back(N);
1243 return SDValue(N, 0);
1247 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1248 unsigned Alignment, int Offset,
1250 unsigned char TargetFlags) {
1251 assert((TargetFlags == 0 || isTarget) &&
1252 "Cannot set target flags on target-independent globals");
1255 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1256 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1257 FoldingSetNodeID ID;
1258 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1259 ID.AddInteger(Alignment);
1260 ID.AddInteger(Offset);
1261 C->addSelectionDAGCSEId(ID);
1262 ID.AddInteger(TargetFlags);
1264 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1265 return SDValue(E, 0);
1267 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1268 Alignment, TargetFlags);
1269 CSEMap.InsertNode(N, IP);
1270 AllNodes.push_back(N);
1271 return SDValue(N, 0);
1274 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1275 unsigned char TargetFlags) {
1276 FoldingSetNodeID ID;
1277 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1278 ID.AddInteger(Index);
1279 ID.AddInteger(Offset);
1280 ID.AddInteger(TargetFlags);
1282 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1283 return SDValue(E, 0);
1285 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1287 CSEMap.InsertNode(N, IP);
1288 AllNodes.push_back(N);
1289 return SDValue(N, 0);
1292 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1293 FoldingSetNodeID ID;
1294 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1297 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1298 return SDValue(E, 0);
1300 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1301 CSEMap.InsertNode(N, IP);
1302 AllNodes.push_back(N);
1303 return SDValue(N, 0);
1306 SDValue SelectionDAG::getValueType(EVT VT) {
1307 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1308 ValueTypeNodes.size())
1309 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1311 SDNode *&N = VT.isExtended() ?
1312 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1314 if (N) return SDValue(N, 0);
1315 N = new (NodeAllocator) VTSDNode(VT);
1316 AllNodes.push_back(N);
1317 return SDValue(N, 0);
1320 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1321 SDNode *&N = ExternalSymbols[Sym];
1322 if (N) return SDValue(N, 0);
1323 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1324 AllNodes.push_back(N);
1325 return SDValue(N, 0);
1328 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1329 unsigned char TargetFlags) {
1331 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1333 if (N) return SDValue(N, 0);
1334 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1335 AllNodes.push_back(N);
1336 return SDValue(N, 0);
1339 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1340 if ((unsigned)Cond >= CondCodeNodes.size())
1341 CondCodeNodes.resize(Cond+1);
1343 if (CondCodeNodes[Cond] == 0) {
1344 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1345 CondCodeNodes[Cond] = N;
1346 AllNodes.push_back(N);
1349 return SDValue(CondCodeNodes[Cond], 0);
1352 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1353 // the shuffle mask M that point at N1 to point at N2, and indices that point
1354 // N2 to point at N1.
1355 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1357 int NElts = M.size();
1358 for (int i = 0; i != NElts; ++i) {
1366 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1367 SDValue N2, const int *Mask) {
1368 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1369 "Invalid VECTOR_SHUFFLE");
1371 // Canonicalize shuffle undef, undef -> undef
1372 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1373 return getUNDEF(VT);
1375 // Validate that all indices in Mask are within the range of the elements
1376 // input to the shuffle.
1377 unsigned NElts = VT.getVectorNumElements();
1378 SmallVector<int, 8> MaskVec;
1379 for (unsigned i = 0; i != NElts; ++i) {
1380 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1381 MaskVec.push_back(Mask[i]);
1384 // Canonicalize shuffle v, v -> v, undef
1387 for (unsigned i = 0; i != NElts; ++i)
1388 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1391 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1392 if (N1.getOpcode() == ISD::UNDEF)
1393 commuteShuffle(N1, N2, MaskVec);
1395 // Canonicalize all index into lhs, -> shuffle lhs, undef
1396 // Canonicalize all index into rhs, -> shuffle rhs, undef
1397 bool AllLHS = true, AllRHS = true;
1398 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1399 for (unsigned i = 0; i != NElts; ++i) {
1400 if (MaskVec[i] >= (int)NElts) {
1405 } else if (MaskVec[i] >= 0) {
1409 if (AllLHS && AllRHS)
1410 return getUNDEF(VT);
1411 if (AllLHS && !N2Undef)
1415 commuteShuffle(N1, N2, MaskVec);
1418 // If Identity shuffle return that node.
1419 bool Identity = true;
1420 for (unsigned i = 0; i != NElts; ++i) {
1421 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1423 if (Identity && NElts)
1426 FoldingSetNodeID ID;
1427 SDValue Ops[2] = { N1, N2 };
1428 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1429 for (unsigned i = 0; i != NElts; ++i)
1430 ID.AddInteger(MaskVec[i]);
1433 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1434 return SDValue(E, 0);
1436 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1437 // SDNode doesn't have access to it. This memory will be "leaked" when
1438 // the node is deallocated, but recovered when the NodeAllocator is released.
1439 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1440 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1442 ShuffleVectorSDNode *N =
1443 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1444 dl.getDebugLoc(), N1, N2,
1446 CSEMap.InsertNode(N, IP);
1447 AllNodes.push_back(N);
1448 return SDValue(N, 0);
1451 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1452 SDValue Val, SDValue DTy,
1453 SDValue STy, SDValue Rnd, SDValue Sat,
1454 ISD::CvtCode Code) {
1455 // If the src and dest types are the same and the conversion is between
1456 // integer types of the same sign or two floats, no conversion is necessary.
1458 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1461 FoldingSetNodeID ID;
1462 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1463 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1465 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1466 return SDValue(E, 0);
1468 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1471 CSEMap.InsertNode(N, IP);
1472 AllNodes.push_back(N);
1473 return SDValue(N, 0);
1476 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1477 FoldingSetNodeID ID;
1478 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1479 ID.AddInteger(RegNo);
1481 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1482 return SDValue(E, 0);
1484 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1485 CSEMap.InsertNode(N, IP);
1486 AllNodes.push_back(N);
1487 return SDValue(N, 0);
1490 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1491 FoldingSetNodeID ID;
1492 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1493 ID.AddPointer(RegMask);
1495 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1496 return SDValue(E, 0);
1498 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1499 CSEMap.InsertNode(N, IP);
1500 AllNodes.push_back(N);
1501 return SDValue(N, 0);
1504 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1505 FoldingSetNodeID ID;
1506 SDValue Ops[] = { Root };
1507 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1508 ID.AddPointer(Label);
1510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1511 return SDValue(E, 0);
1513 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1514 dl.getDebugLoc(), Root, Label);
1515 CSEMap.InsertNode(N, IP);
1516 AllNodes.push_back(N);
1517 return SDValue(N, 0);
1521 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1524 unsigned char TargetFlags) {
1525 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1527 FoldingSetNodeID ID;
1528 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1530 ID.AddInteger(Offset);
1531 ID.AddInteger(TargetFlags);
1533 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1534 return SDValue(E, 0);
1536 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1538 CSEMap.InsertNode(N, IP);
1539 AllNodes.push_back(N);
1540 return SDValue(N, 0);
1543 SDValue SelectionDAG::getSrcValue(const Value *V) {
1544 assert((!V || V->getType()->isPointerTy()) &&
1545 "SrcValue is not a pointer?");
1547 FoldingSetNodeID ID;
1548 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1552 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1553 return SDValue(E, 0);
1555 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1556 CSEMap.InsertNode(N, IP);
1557 AllNodes.push_back(N);
1558 return SDValue(N, 0);
1561 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1562 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1563 FoldingSetNodeID ID;
1564 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1568 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1569 return SDValue(E, 0);
1571 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1572 CSEMap.InsertNode(N, IP);
1573 AllNodes.push_back(N);
1574 return SDValue(N, 0);
1577 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1578 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1579 unsigned SrcAS, unsigned DestAS) {
1580 SDValue Ops[] = {Ptr};
1581 FoldingSetNodeID ID;
1582 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1583 ID.AddInteger(SrcAS);
1584 ID.AddInteger(DestAS);
1587 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1588 return SDValue(E, 0);
1590 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1592 VT, Ptr, SrcAS, DestAS);
1593 CSEMap.InsertNode(N, IP);
1594 AllNodes.push_back(N);
1595 return SDValue(N, 0);
1598 /// getShiftAmountOperand - Return the specified value casted to
1599 /// the target's desired shift amount type.
1600 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1601 EVT OpTy = Op.getValueType();
1602 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1603 if (OpTy == ShTy || OpTy.isVector()) return Op;
1605 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1606 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1609 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1610 /// specified value type.
1611 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1612 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1613 unsigned ByteSize = VT.getStoreSize();
1614 Type *Ty = VT.getTypeForEVT(*getContext());
1615 const TargetLowering *TLI = TM.getTargetLowering();
1616 unsigned StackAlign =
1617 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1619 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1620 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1623 /// CreateStackTemporary - Create a stack temporary suitable for holding
1624 /// either of the specified value types.
1625 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1626 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1627 VT2.getStoreSizeInBits())/8;
1628 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1629 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1630 const TargetLowering *TLI = TM.getTargetLowering();
1631 const DataLayout *TD = TLI->getDataLayout();
1632 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1633 TD->getPrefTypeAlignment(Ty2));
1635 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1636 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1637 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1640 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1641 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1642 // These setcc operations always fold.
1646 case ISD::SETFALSE2: return getConstant(0, VT);
1648 case ISD::SETTRUE2: {
1649 const TargetLowering *TLI = TM.getTargetLowering();
1650 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1652 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1665 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1669 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1670 const APInt &C2 = N2C->getAPIntValue();
1671 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1672 const APInt &C1 = N1C->getAPIntValue();
1675 default: llvm_unreachable("Unknown integer setcc!");
1676 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1677 case ISD::SETNE: return getConstant(C1 != C2, VT);
1678 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1679 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1680 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1681 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1682 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1683 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1684 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1685 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1689 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1690 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1691 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1694 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1695 return getUNDEF(VT);
1697 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1698 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1699 return getUNDEF(VT);
1701 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1702 R==APFloat::cmpLessThan, VT);
1703 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1704 return getUNDEF(VT);
1706 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1707 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1708 return getUNDEF(VT);
1710 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1711 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1712 return getUNDEF(VT);
1714 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1715 R==APFloat::cmpEqual, VT);
1716 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1717 return getUNDEF(VT);
1719 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1720 R==APFloat::cmpEqual, VT);
1721 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1722 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1723 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1724 R==APFloat::cmpEqual, VT);
1725 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1726 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1727 R==APFloat::cmpLessThan, VT);
1728 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1729 R==APFloat::cmpUnordered, VT);
1730 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1731 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1734 // Ensure that the constant occurs on the RHS.
1735 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1736 MVT CompVT = N1.getValueType().getSimpleVT();
1737 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1740 return getSetCC(dl, VT, N2, N1, SwappedCond);
1744 // Could not fold it.
1748 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1749 /// use this predicate to simplify operations downstream.
1750 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1751 // This predicate is not safe for vector operations.
1752 if (Op.getValueType().isVector())
1755 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1756 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1759 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1760 /// this predicate to simplify operations downstream. Mask is known to be zero
1761 /// for bits that V cannot have.
1762 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1763 unsigned Depth) const {
1764 APInt KnownZero, KnownOne;
1765 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1766 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1767 return (KnownZero & Mask) == Mask;
1770 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1771 /// known to be either zero or one and return them in the KnownZero/KnownOne
1772 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1774 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1775 APInt &KnownOne, unsigned Depth) const {
1776 const TargetLowering *TLI = TM.getTargetLowering();
1777 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1779 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1781 return; // Limit search depth.
1783 APInt KnownZero2, KnownOne2;
1785 switch (Op.getOpcode()) {
1787 // We know all of the bits for a constant!
1788 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1789 KnownZero = ~KnownOne;
1792 // If either the LHS or the RHS are Zero, the result is zero.
1793 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1794 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1795 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1796 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1798 // Output known-1 bits are only known if set in both the LHS & RHS.
1799 KnownOne &= KnownOne2;
1800 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1801 KnownZero |= KnownZero2;
1804 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1805 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1806 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1807 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1809 // Output known-0 bits are only known if clear in both the LHS & RHS.
1810 KnownZero &= KnownZero2;
1811 // Output known-1 are known to be set if set in either the LHS | RHS.
1812 KnownOne |= KnownOne2;
1815 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1816 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1817 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1818 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1820 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1821 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1822 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1823 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1824 KnownZero = KnownZeroOut;
1828 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1829 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1830 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1831 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1833 // If low bits are zero in either operand, output low known-0 bits.
1834 // Also compute a conserative estimate for high known-0 bits.
1835 // More trickiness is possible, but this is sufficient for the
1836 // interesting case of alignment computation.
1837 KnownOne.clearAllBits();
1838 unsigned TrailZ = KnownZero.countTrailingOnes() +
1839 KnownZero2.countTrailingOnes();
1840 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1841 KnownZero2.countLeadingOnes(),
1842 BitWidth) - BitWidth;
1844 TrailZ = std::min(TrailZ, BitWidth);
1845 LeadZ = std::min(LeadZ, BitWidth);
1846 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1847 APInt::getHighBitsSet(BitWidth, LeadZ);
1851 // For the purposes of computing leading zeros we can conservatively
1852 // treat a udiv as a logical right shift by the power of 2 known to
1853 // be less than the denominator.
1854 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1855 unsigned LeadZ = KnownZero2.countLeadingOnes();
1857 KnownOne2.clearAllBits();
1858 KnownZero2.clearAllBits();
1859 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1860 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1861 if (RHSUnknownLeadingOnes != BitWidth)
1862 LeadZ = std::min(BitWidth,
1863 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1865 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1869 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1870 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1871 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1872 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1874 // Only known if known in both the LHS and RHS.
1875 KnownOne &= KnownOne2;
1876 KnownZero &= KnownZero2;
1878 case ISD::SELECT_CC:
1879 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1880 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1881 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1882 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1884 // Only known if known in both the LHS and RHS.
1885 KnownOne &= KnownOne2;
1886 KnownZero &= KnownZero2;
1894 if (Op.getResNo() != 1)
1896 // The boolean result conforms to getBooleanContents. Fall through.
1898 // If we know the result of a setcc has the top bits zero, use this info.
1899 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1900 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1901 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1904 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1905 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1906 unsigned ShAmt = SA->getZExtValue();
1908 // If the shift count is an invalid immediate, don't do anything.
1909 if (ShAmt >= BitWidth)
1912 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1913 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1914 KnownZero <<= ShAmt;
1916 // low bits known zero.
1917 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1921 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1922 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1923 unsigned ShAmt = SA->getZExtValue();
1925 // If the shift count is an invalid immediate, don't do anything.
1926 if (ShAmt >= BitWidth)
1929 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1930 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1931 KnownZero = KnownZero.lshr(ShAmt);
1932 KnownOne = KnownOne.lshr(ShAmt);
1934 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1935 KnownZero |= HighBits; // High bits known zero.
1939 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1940 unsigned ShAmt = SA->getZExtValue();
1942 // If the shift count is an invalid immediate, don't do anything.
1943 if (ShAmt >= BitWidth)
1946 // If any of the demanded bits are produced by the sign extension, we also
1947 // demand the input sign bit.
1948 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1950 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1951 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1952 KnownZero = KnownZero.lshr(ShAmt);
1953 KnownOne = KnownOne.lshr(ShAmt);
1955 // Handle the sign bits.
1956 APInt SignBit = APInt::getSignBit(BitWidth);
1957 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1959 if (KnownZero.intersects(SignBit)) {
1960 KnownZero |= HighBits; // New bits are known zero.
1961 } else if (KnownOne.intersects(SignBit)) {
1962 KnownOne |= HighBits; // New bits are known one.
1966 case ISD::SIGN_EXTEND_INREG: {
1967 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1968 unsigned EBits = EVT.getScalarType().getSizeInBits();
1970 // Sign extension. Compute the demanded bits in the result that are not
1971 // present in the input.
1972 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1974 APInt InSignBit = APInt::getSignBit(EBits);
1975 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1977 // If the sign extended bits are demanded, we know that the sign
1979 InSignBit = InSignBit.zext(BitWidth);
1980 if (NewBits.getBoolValue())
1981 InputDemandedBits |= InSignBit;
1983 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1984 KnownOne &= InputDemandedBits;
1985 KnownZero &= InputDemandedBits;
1986 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1988 // If the sign bit of the input is known set or clear, then we know the
1989 // top bits of the result.
1990 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1991 KnownZero |= NewBits;
1992 KnownOne &= ~NewBits;
1993 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1994 KnownOne |= NewBits;
1995 KnownZero &= ~NewBits;
1996 } else { // Input sign bit unknown
1997 KnownZero &= ~NewBits;
1998 KnownOne &= ~NewBits;
2003 case ISD::CTTZ_ZERO_UNDEF:
2005 case ISD::CTLZ_ZERO_UNDEF:
2007 unsigned LowBits = Log2_32(BitWidth)+1;
2008 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2009 KnownOne.clearAllBits();
2013 LoadSDNode *LD = cast<LoadSDNode>(Op);
2014 // If this is a ZEXTLoad and we are looking at the loaded value.
2015 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2016 EVT VT = LD->getMemoryVT();
2017 unsigned MemBits = VT.getScalarType().getSizeInBits();
2018 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2019 } else if (const MDNode *Ranges = LD->getRanges()) {
2020 computeMaskedBitsLoad(*Ranges, KnownZero);
2024 case ISD::ZERO_EXTEND: {
2025 EVT InVT = Op.getOperand(0).getValueType();
2026 unsigned InBits = InVT.getScalarType().getSizeInBits();
2027 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2028 KnownZero = KnownZero.trunc(InBits);
2029 KnownOne = KnownOne.trunc(InBits);
2030 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2031 KnownZero = KnownZero.zext(BitWidth);
2032 KnownOne = KnownOne.zext(BitWidth);
2033 KnownZero |= NewBits;
2036 case ISD::SIGN_EXTEND: {
2037 EVT InVT = Op.getOperand(0).getValueType();
2038 unsigned InBits = InVT.getScalarType().getSizeInBits();
2039 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2041 KnownZero = KnownZero.trunc(InBits);
2042 KnownOne = KnownOne.trunc(InBits);
2043 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2045 // Note if the sign bit is known to be zero or one.
2046 bool SignBitKnownZero = KnownZero.isNegative();
2047 bool SignBitKnownOne = KnownOne.isNegative();
2048 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2049 "Sign bit can't be known to be both zero and one!");
2051 KnownZero = KnownZero.zext(BitWidth);
2052 KnownOne = KnownOne.zext(BitWidth);
2054 // If the sign bit is known zero or one, the top bits match.
2055 if (SignBitKnownZero)
2056 KnownZero |= NewBits;
2057 else if (SignBitKnownOne)
2058 KnownOne |= NewBits;
2061 case ISD::ANY_EXTEND: {
2062 EVT InVT = Op.getOperand(0).getValueType();
2063 unsigned InBits = InVT.getScalarType().getSizeInBits();
2064 KnownZero = KnownZero.trunc(InBits);
2065 KnownOne = KnownOne.trunc(InBits);
2066 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2067 KnownZero = KnownZero.zext(BitWidth);
2068 KnownOne = KnownOne.zext(BitWidth);
2071 case ISD::TRUNCATE: {
2072 EVT InVT = Op.getOperand(0).getValueType();
2073 unsigned InBits = InVT.getScalarType().getSizeInBits();
2074 KnownZero = KnownZero.zext(InBits);
2075 KnownOne = KnownOne.zext(InBits);
2076 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2077 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2078 KnownZero = KnownZero.trunc(BitWidth);
2079 KnownOne = KnownOne.trunc(BitWidth);
2082 case ISD::AssertZext: {
2083 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2084 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2085 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2086 KnownZero |= (~InMask);
2087 KnownOne &= (~KnownZero);
2091 // All bits are zero except the low bit.
2092 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2096 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2097 // We know that the top bits of C-X are clear if X contains less bits
2098 // than C (i.e. no wrap-around can happen). For example, 20-X is
2099 // positive if we can prove that X is >= 0 and < 16.
2100 if (CLHS->getAPIntValue().isNonNegative()) {
2101 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2102 // NLZ can't be BitWidth with no sign bit
2103 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2104 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2106 // If all of the MaskV bits are known to be zero, then we know the
2107 // output top bits are zero, because we now know that the output is
2109 if ((KnownZero2 & MaskV) == MaskV) {
2110 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2111 // Top bits known zero.
2112 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2120 // Output known-0 bits are known if clear or set in both the low clear bits
2121 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2122 // low 3 bits clear.
2123 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2124 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2125 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2127 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2128 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2129 KnownZeroOut = std::min(KnownZeroOut,
2130 KnownZero2.countTrailingOnes());
2132 if (Op.getOpcode() == ISD::ADD) {
2133 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2137 // With ADDE, a carry bit may be added in, so we can only use this
2138 // information if we know (at least) that the low two bits are clear. We
2139 // then return to the caller that the low bit is unknown but that other bits
2141 if (KnownZeroOut >= 2) // ADDE
2142 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2146 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2147 const APInt &RA = Rem->getAPIntValue().abs();
2148 if (RA.isPowerOf2()) {
2149 APInt LowBits = RA - 1;
2150 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2152 // The low bits of the first operand are unchanged by the srem.
2153 KnownZero = KnownZero2 & LowBits;
2154 KnownOne = KnownOne2 & LowBits;
2156 // If the first operand is non-negative or has all low bits zero, then
2157 // the upper bits are all zero.
2158 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2159 KnownZero |= ~LowBits;
2161 // If the first operand is negative and not all low bits are zero, then
2162 // the upper bits are all one.
2163 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2164 KnownOne |= ~LowBits;
2165 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2170 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2171 const APInt &RA = Rem->getAPIntValue();
2172 if (RA.isPowerOf2()) {
2173 APInt LowBits = (RA - 1);
2174 KnownZero |= ~LowBits;
2175 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2176 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2181 // Since the result is less than or equal to either operand, any leading
2182 // zero bits in either operand must also exist in the result.
2183 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2184 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2186 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2187 KnownZero2.countLeadingOnes());
2188 KnownOne.clearAllBits();
2189 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2192 case ISD::FrameIndex:
2193 case ISD::TargetFrameIndex:
2194 if (unsigned Align = InferPtrAlignment(Op)) {
2195 // The low bits are known zero if the pointer is aligned.
2196 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2202 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2205 case ISD::INTRINSIC_WO_CHAIN:
2206 case ISD::INTRINSIC_W_CHAIN:
2207 case ISD::INTRINSIC_VOID:
2208 // Allow the target to implement this method for its nodes.
2209 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2214 /// ComputeNumSignBits - Return the number of times the sign bit of the
2215 /// register is replicated into the other bits. We know that at least 1 bit
2216 /// is always equal to the sign bit (itself), but other cases can give us
2217 /// information. For example, immediately after an "SRA X, 2", we know that
2218 /// the top 3 bits are all equal to each other, so we return 3.
2219 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2220 const TargetLowering *TLI = TM.getTargetLowering();
2221 EVT VT = Op.getValueType();
2222 assert(VT.isInteger() && "Invalid VT!");
2223 unsigned VTBits = VT.getScalarType().getSizeInBits();
2225 unsigned FirstAnswer = 1;
2228 return 1; // Limit search depth.
2230 switch (Op.getOpcode()) {
2232 case ISD::AssertSext:
2233 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2234 return VTBits-Tmp+1;
2235 case ISD::AssertZext:
2236 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2239 case ISD::Constant: {
2240 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2241 return Val.getNumSignBits();
2244 case ISD::SIGN_EXTEND:
2246 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2247 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2249 case ISD::SIGN_EXTEND_INREG:
2250 // Max of the input and what this extends.
2252 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2255 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2256 return std::max(Tmp, Tmp2);
2259 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2260 // SRA X, C -> adds C sign bits.
2261 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2262 Tmp += C->getZExtValue();
2263 if (Tmp > VTBits) Tmp = VTBits;
2267 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2268 // shl destroys sign bits.
2269 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2270 if (C->getZExtValue() >= VTBits || // Bad shift.
2271 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2272 return Tmp - C->getZExtValue();
2277 case ISD::XOR: // NOT is handled here.
2278 // Logical binary ops preserve the number of sign bits at the worst.
2279 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2281 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2282 FirstAnswer = std::min(Tmp, Tmp2);
2283 // We computed what we know about the sign bits as our first
2284 // answer. Now proceed to the generic code that uses
2285 // ComputeMaskedBits, and pick whichever answer is better.
2290 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2291 if (Tmp == 1) return 1; // Early out.
2292 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2293 return std::min(Tmp, Tmp2);
2301 if (Op.getResNo() != 1)
2303 // The boolean result conforms to getBooleanContents. Fall through.
2305 // If setcc returns 0/-1, all bits are sign bits.
2306 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2307 TargetLowering::ZeroOrNegativeOneBooleanContent)
2312 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2313 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2315 // Handle rotate right by N like a rotate left by 32-N.
2316 if (Op.getOpcode() == ISD::ROTR)
2317 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2319 // If we aren't rotating out all of the known-in sign bits, return the
2320 // number that are left. This handles rotl(sext(x), 1) for example.
2321 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2322 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2326 // Add can have at most one carry bit. Thus we know that the output
2327 // is, at worst, one more bit than the inputs.
2328 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2329 if (Tmp == 1) return 1; // Early out.
2331 // Special case decrementing a value (ADD X, -1):
2332 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2333 if (CRHS->isAllOnesValue()) {
2334 APInt KnownZero, KnownOne;
2335 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2337 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2339 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2342 // If we are subtracting one from a positive number, there is no carry
2343 // out of the result.
2344 if (KnownZero.isNegative())
2348 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2349 if (Tmp2 == 1) return 1;
2350 return std::min(Tmp, Tmp2)-1;
2353 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2354 if (Tmp2 == 1) return 1;
2357 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2358 if (CLHS->isNullValue()) {
2359 APInt KnownZero, KnownOne;
2360 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2361 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2363 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2366 // If the input is known to be positive (the sign bit is known clear),
2367 // the output of the NEG has the same number of sign bits as the input.
2368 if (KnownZero.isNegative())
2371 // Otherwise, we treat this like a SUB.
2374 // Sub can have at most one carry bit. Thus we know that the output
2375 // is, at worst, one more bit than the inputs.
2376 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2377 if (Tmp == 1) return 1; // Early out.
2378 return std::min(Tmp, Tmp2)-1;
2380 // FIXME: it's tricky to do anything useful for this, but it is an important
2381 // case for targets like X86.
2385 // If we are looking at the loaded value of the SDNode.
2386 if (Op.getResNo() == 0) {
2387 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2388 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2389 unsigned ExtType = LD->getExtensionType();
2392 case ISD::SEXTLOAD: // '17' bits known
2393 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2394 return VTBits-Tmp+1;
2395 case ISD::ZEXTLOAD: // '16' bits known
2396 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2402 // Allow the target to implement this method for its nodes.
2403 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2404 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2405 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2406 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2407 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2408 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2411 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2412 // use this information.
2413 APInt KnownZero, KnownOne;
2414 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2417 if (KnownZero.isNegative()) { // sign bit is 0
2419 } else if (KnownOne.isNegative()) { // sign bit is 1;
2426 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2427 // the number of identical bits in the top of the input value.
2429 Mask <<= Mask.getBitWidth()-VTBits;
2430 // Return # leading zeros. We use 'min' here in case Val was zero before
2431 // shifting. We don't want to return '64' as for an i32 "0".
2432 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2435 /// isBaseWithConstantOffset - Return true if the specified operand is an
2436 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2437 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2438 /// semantics as an ADD. This handles the equivalence:
2439 /// X|Cst == X+Cst iff X&Cst = 0.
2440 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2441 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2442 !isa<ConstantSDNode>(Op.getOperand(1)))
2445 if (Op.getOpcode() == ISD::OR &&
2446 !MaskedValueIsZero(Op.getOperand(0),
2447 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2454 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2455 // If we're told that NaNs won't happen, assume they won't.
2456 if (getTarget().Options.NoNaNsFPMath)
2459 // If the value is a constant, we can obviously see if it is a NaN or not.
2460 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2461 return !C->getValueAPF().isNaN();
2463 // TODO: Recognize more cases here.
2468 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2469 // If the value is a constant, we can obviously see if it is a zero or not.
2470 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2471 return !C->isZero();
2473 // TODO: Recognize more cases here.
2474 switch (Op.getOpcode()) {
2477 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2478 return !C->isNullValue();
2485 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2486 // Check the obvious case.
2487 if (A == B) return true;
2489 // For for negative and positive zero.
2490 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2491 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2492 if (CA->isZero() && CB->isZero()) return true;
2494 // Otherwise they may not be equal.
2498 /// getNode - Gets or creates the specified node.
2500 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2501 FoldingSetNodeID ID;
2502 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2504 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2505 return SDValue(E, 0);
2507 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2508 DL.getDebugLoc(), getVTList(VT));
2509 CSEMap.InsertNode(N, IP);
2511 AllNodes.push_back(N);
2515 return SDValue(N, 0);
2518 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2519 EVT VT, SDValue Operand) {
2520 // Constant fold unary operations with an integer constant operand.
2521 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2522 const APInt &Val = C->getAPIntValue();
2525 case ISD::SIGN_EXTEND:
2526 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2527 case ISD::ANY_EXTEND:
2528 case ISD::ZERO_EXTEND:
2530 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2531 case ISD::UINT_TO_FP:
2532 case ISD::SINT_TO_FP: {
2533 APFloat apf(EVTToAPFloatSemantics(VT),
2534 APInt::getNullValue(VT.getSizeInBits()));
2535 (void)apf.convertFromAPInt(Val,
2536 Opcode==ISD::SINT_TO_FP,
2537 APFloat::rmNearestTiesToEven);
2538 return getConstantFP(apf, VT);
2541 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2542 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2543 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2544 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2547 return getConstant(Val.byteSwap(), VT);
2549 return getConstant(Val.countPopulation(), VT);
2551 case ISD::CTLZ_ZERO_UNDEF:
2552 return getConstant(Val.countLeadingZeros(), VT);
2554 case ISD::CTTZ_ZERO_UNDEF:
2555 return getConstant(Val.countTrailingZeros(), VT);
2559 // Constant fold unary operations with a floating point constant operand.
2560 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2561 APFloat V = C->getValueAPF(); // make copy
2565 return getConstantFP(V, VT);
2568 return getConstantFP(V, VT);
2570 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2571 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2572 return getConstantFP(V, VT);
2576 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2577 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2578 return getConstantFP(V, VT);
2582 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2583 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2584 return getConstantFP(V, VT);
2587 case ISD::FP_EXTEND: {
2589 // This can return overflow, underflow, or inexact; we don't care.
2590 // FIXME need to be more flexible about rounding mode.
2591 (void)V.convert(EVTToAPFloatSemantics(VT),
2592 APFloat::rmNearestTiesToEven, &ignored);
2593 return getConstantFP(V, VT);
2595 case ISD::FP_TO_SINT:
2596 case ISD::FP_TO_UINT: {
2599 assert(integerPartWidth >= 64);
2600 // FIXME need to be more flexible about rounding mode.
2601 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2602 Opcode==ISD::FP_TO_SINT,
2603 APFloat::rmTowardZero, &ignored);
2604 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2606 APInt api(VT.getSizeInBits(), x);
2607 return getConstant(api, VT);
2610 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2611 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2612 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2613 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2618 unsigned OpOpcode = Operand.getNode()->getOpcode();
2620 case ISD::TokenFactor:
2621 case ISD::MERGE_VALUES:
2622 case ISD::CONCAT_VECTORS:
2623 return Operand; // Factor, merge or concat of one node? No need.
2624 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2625 case ISD::FP_EXTEND:
2626 assert(VT.isFloatingPoint() &&
2627 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2628 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2629 assert((!VT.isVector() ||
2630 VT.getVectorNumElements() ==
2631 Operand.getValueType().getVectorNumElements()) &&
2632 "Vector element count mismatch!");
2633 if (Operand.getOpcode() == ISD::UNDEF)
2634 return getUNDEF(VT);
2636 case ISD::SIGN_EXTEND:
2637 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2638 "Invalid SIGN_EXTEND!");
2639 if (Operand.getValueType() == VT) return Operand; // noop extension
2640 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2641 "Invalid sext node, dst < src!");
2642 assert((!VT.isVector() ||
2643 VT.getVectorNumElements() ==
2644 Operand.getValueType().getVectorNumElements()) &&
2645 "Vector element count mismatch!");
2646 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2647 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2648 else if (OpOpcode == ISD::UNDEF)
2649 // sext(undef) = 0, because the top bits will all be the same.
2650 return getConstant(0, VT);
2652 case ISD::ZERO_EXTEND:
2653 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2654 "Invalid ZERO_EXTEND!");
2655 if (Operand.getValueType() == VT) return Operand; // noop extension
2656 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2657 "Invalid zext node, dst < src!");
2658 assert((!VT.isVector() ||
2659 VT.getVectorNumElements() ==
2660 Operand.getValueType().getVectorNumElements()) &&
2661 "Vector element count mismatch!");
2662 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2663 return getNode(ISD::ZERO_EXTEND, DL, VT,
2664 Operand.getNode()->getOperand(0));
2665 else if (OpOpcode == ISD::UNDEF)
2666 // zext(undef) = 0, because the top bits will be zero.
2667 return getConstant(0, VT);
2669 case ISD::ANY_EXTEND:
2670 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2671 "Invalid ANY_EXTEND!");
2672 if (Operand.getValueType() == VT) return Operand; // noop extension
2673 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2674 "Invalid anyext node, dst < src!");
2675 assert((!VT.isVector() ||
2676 VT.getVectorNumElements() ==
2677 Operand.getValueType().getVectorNumElements()) &&
2678 "Vector element count mismatch!");
2680 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2681 OpOpcode == ISD::ANY_EXTEND)
2682 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2683 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2684 else if (OpOpcode == ISD::UNDEF)
2685 return getUNDEF(VT);
2687 // (ext (trunx x)) -> x
2688 if (OpOpcode == ISD::TRUNCATE) {
2689 SDValue OpOp = Operand.getNode()->getOperand(0);
2690 if (OpOp.getValueType() == VT)
2695 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2696 "Invalid TRUNCATE!");
2697 if (Operand.getValueType() == VT) return Operand; // noop truncate
2698 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2699 "Invalid truncate node, src < dst!");
2700 assert((!VT.isVector() ||
2701 VT.getVectorNumElements() ==
2702 Operand.getValueType().getVectorNumElements()) &&
2703 "Vector element count mismatch!");
2704 if (OpOpcode == ISD::TRUNCATE)
2705 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2706 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2707 OpOpcode == ISD::ANY_EXTEND) {
2708 // If the source is smaller than the dest, we still need an extend.
2709 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2710 .bitsLT(VT.getScalarType()))
2711 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2712 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2713 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2714 return Operand.getNode()->getOperand(0);
2716 if (OpOpcode == ISD::UNDEF)
2717 return getUNDEF(VT);
2720 // Basic sanity checking.
2721 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2722 && "Cannot BITCAST between types of different sizes!");
2723 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2724 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2725 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2726 if (OpOpcode == ISD::UNDEF)
2727 return getUNDEF(VT);
2729 case ISD::SCALAR_TO_VECTOR:
2730 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2731 (VT.getVectorElementType() == Operand.getValueType() ||
2732 (VT.getVectorElementType().isInteger() &&
2733 Operand.getValueType().isInteger() &&
2734 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2735 "Illegal SCALAR_TO_VECTOR node!");
2736 if (OpOpcode == ISD::UNDEF)
2737 return getUNDEF(VT);
2738 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2739 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2740 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2741 Operand.getConstantOperandVal(1) == 0 &&
2742 Operand.getOperand(0).getValueType() == VT)
2743 return Operand.getOperand(0);
2746 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2747 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2748 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2749 Operand.getNode()->getOperand(0));
2750 if (OpOpcode == ISD::FNEG) // --X -> X
2751 return Operand.getNode()->getOperand(0);
2754 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2755 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2760 SDVTList VTs = getVTList(VT);
2761 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2762 FoldingSetNodeID ID;
2763 SDValue Ops[1] = { Operand };
2764 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2766 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2767 return SDValue(E, 0);
2769 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2770 DL.getDebugLoc(), VTs, Operand);
2771 CSEMap.InsertNode(N, IP);
2773 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2774 DL.getDebugLoc(), VTs, Operand);
2777 AllNodes.push_back(N);
2781 return SDValue(N, 0);
2784 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2785 SDNode *Cst1, SDNode *Cst2) {
2786 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2787 SmallVector<SDValue, 4> Outputs;
2788 EVT SVT = VT.getScalarType();
2790 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2791 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2792 if (Scalar1 && Scalar2) {
2793 // Scalar instruction.
2794 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2796 // For vectors extract each constant element into Inputs so we can constant
2797 // fold them individually.
2798 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2799 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2803 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2805 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2806 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2807 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2808 if (!V1 || !V2) // Not a constant, bail.
2811 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2812 // FIXME: This is valid and could be handled by truncating the APInts.
2813 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2816 Inputs.push_back(std::make_pair(V1, V2));
2820 // We have a number of constant values, constant fold them element by element.
2821 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2822 const APInt &C1 = Inputs[I].first->getAPIntValue();
2823 const APInt &C2 = Inputs[I].second->getAPIntValue();
2827 Outputs.push_back(getConstant(C1 + C2, SVT));
2830 Outputs.push_back(getConstant(C1 - C2, SVT));
2833 Outputs.push_back(getConstant(C1 * C2, SVT));
2836 if (!C2.getBoolValue())
2838 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2841 if (!C2.getBoolValue())
2843 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2846 if (!C2.getBoolValue())
2848 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2851 if (!C2.getBoolValue())
2853 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2856 Outputs.push_back(getConstant(C1 & C2, SVT));
2859 Outputs.push_back(getConstant(C1 | C2, SVT));
2862 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2865 Outputs.push_back(getConstant(C1 << C2, SVT));
2868 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2871 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2874 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2877 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2884 // Handle the scalar case first.
2885 if (Scalar1 && Scalar2)
2886 return Outputs.back();
2888 // Otherwise build a big vector out of the scalar elements we generated.
2889 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2893 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2895 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2896 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2899 case ISD::TokenFactor:
2900 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2901 N2.getValueType() == MVT::Other && "Invalid token factor!");
2902 // Fold trivial token factors.
2903 if (N1.getOpcode() == ISD::EntryToken) return N2;
2904 if (N2.getOpcode() == ISD::EntryToken) return N1;
2905 if (N1 == N2) return N1;
2907 case ISD::CONCAT_VECTORS:
2908 // Concat of UNDEFs is UNDEF.
2909 if (N1.getOpcode() == ISD::UNDEF &&
2910 N2.getOpcode() == ISD::UNDEF)
2911 return getUNDEF(VT);
2913 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2914 // one big BUILD_VECTOR.
2915 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2916 N2.getOpcode() == ISD::BUILD_VECTOR) {
2917 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2918 N1.getNode()->op_end());
2919 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2920 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2924 assert(VT.isInteger() && "This operator does not apply to FP types!");
2925 assert(N1.getValueType() == N2.getValueType() &&
2926 N1.getValueType() == VT && "Binary operator types must match!");
2927 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2928 // worth handling here.
2929 if (N2C && N2C->isNullValue())
2931 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2938 assert(VT.isInteger() && "This operator does not apply to FP types!");
2939 assert(N1.getValueType() == N2.getValueType() &&
2940 N1.getValueType() == VT && "Binary operator types must match!");
2941 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2942 // it's worth handling here.
2943 if (N2C && N2C->isNullValue())
2953 assert(VT.isInteger() && "This operator does not apply to FP types!");
2954 assert(N1.getValueType() == N2.getValueType() &&
2955 N1.getValueType() == VT && "Binary operator types must match!");
2962 if (getTarget().Options.UnsafeFPMath) {
2963 if (Opcode == ISD::FADD) {
2965 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2966 if (CFP->getValueAPF().isZero())
2969 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2970 if (CFP->getValueAPF().isZero())
2972 } else if (Opcode == ISD::FSUB) {
2974 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2975 if (CFP->getValueAPF().isZero())
2977 } else if (Opcode == ISD::FMUL) {
2978 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2981 // If the first operand isn't the constant, try the second
2983 CFP = dyn_cast<ConstantFPSDNode>(N2);
2990 return SDValue(CFP,0);
2992 if (CFP->isExactlyValue(1.0))
2997 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2998 assert(N1.getValueType() == N2.getValueType() &&
2999 N1.getValueType() == VT && "Binary operator types must match!");
3001 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3002 assert(N1.getValueType() == VT &&
3003 N1.getValueType().isFloatingPoint() &&
3004 N2.getValueType().isFloatingPoint() &&
3005 "Invalid FCOPYSIGN!");
3012 assert(VT == N1.getValueType() &&
3013 "Shift operators return type must be the same as their first arg");
3014 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3015 "Shifts only work on integers");
3016 assert((!VT.isVector() || VT == N2.getValueType()) &&
3017 "Vector shift amounts must be in the same as their first arg");
3018 // Verify that the shift amount VT is bit enough to hold valid shift
3019 // amounts. This catches things like trying to shift an i1024 value by an
3020 // i8, which is easy to fall into in generic code that uses
3021 // TLI.getShiftAmount().
3022 assert(N2.getValueType().getSizeInBits() >=
3023 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3024 "Invalid use of small shift amount with oversized value!");
3026 // Always fold shifts of i1 values so the code generator doesn't need to
3027 // handle them. Since we know the size of the shift has to be less than the
3028 // size of the value, the shift/rotate count is guaranteed to be zero.
3031 if (N2C && N2C->isNullValue())
3034 case ISD::FP_ROUND_INREG: {
3035 EVT EVT = cast<VTSDNode>(N2)->getVT();
3036 assert(VT == N1.getValueType() && "Not an inreg round!");
3037 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3038 "Cannot FP_ROUND_INREG integer types");
3039 assert(EVT.isVector() == VT.isVector() &&
3040 "FP_ROUND_INREG type should be vector iff the operand "
3042 assert((!EVT.isVector() ||
3043 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3044 "Vector element counts must match in FP_ROUND_INREG");
3045 assert(EVT.bitsLE(VT) && "Not rounding down!");
3047 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3051 assert(VT.isFloatingPoint() &&
3052 N1.getValueType().isFloatingPoint() &&
3053 VT.bitsLE(N1.getValueType()) &&
3054 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3055 if (N1.getValueType() == VT) return N1; // noop conversion.
3057 case ISD::AssertSext:
3058 case ISD::AssertZext: {
3059 EVT EVT = cast<VTSDNode>(N2)->getVT();
3060 assert(VT == N1.getValueType() && "Not an inreg extend!");
3061 assert(VT.isInteger() && EVT.isInteger() &&
3062 "Cannot *_EXTEND_INREG FP types");
3063 assert(!EVT.isVector() &&
3064 "AssertSExt/AssertZExt type should be the vector element type "
3065 "rather than the vector type!");
3066 assert(EVT.bitsLE(VT) && "Not extending!");
3067 if (VT == EVT) return N1; // noop assertion.
3070 case ISD::SIGN_EXTEND_INREG: {
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() == VT.isVector() &&
3076 "SIGN_EXTEND_INREG type should be vector iff the operand "
3078 assert((!EVT.isVector() ||
3079 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3080 "Vector element counts must match in SIGN_EXTEND_INREG");
3081 assert(EVT.bitsLE(VT) && "Not extending!");
3082 if (EVT == VT) return N1; // Not actually extending
3085 APInt Val = N1C->getAPIntValue();
3086 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3087 Val <<= Val.getBitWidth()-FromBits;
3088 Val = Val.ashr(Val.getBitWidth()-FromBits);
3089 return getConstant(Val, VT);
3093 case ISD::EXTRACT_VECTOR_ELT:
3094 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3095 if (N1.getOpcode() == ISD::UNDEF)
3096 return getUNDEF(VT);
3098 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3099 // expanding copies of large vectors from registers.
3101 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3102 N1.getNumOperands() > 0) {
3104 N1.getOperand(0).getValueType().getVectorNumElements();
3105 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3106 N1.getOperand(N2C->getZExtValue() / Factor),
3107 getConstant(N2C->getZExtValue() % Factor,
3108 N2.getValueType()));
3111 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3112 // expanding large vector constants.
3113 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3114 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3116 if (VT != Elt.getValueType())
3117 // If the vector element type is not legal, the BUILD_VECTOR operands
3118 // are promoted and implicitly truncated, and the result implicitly
3119 // extended. Make that explicit here.
3120 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3125 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3126 // operations are lowered to scalars.
3127 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3128 // If the indices are the same, return the inserted element else
3129 // if the indices are known different, extract the element from
3130 // the original vector.
3131 SDValue N1Op2 = N1.getOperand(2);
3132 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3134 if (N1Op2C && N2C) {
3135 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3136 if (VT == N1.getOperand(1).getValueType())
3137 return N1.getOperand(1);
3139 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3142 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3146 case ISD::EXTRACT_ELEMENT:
3147 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3148 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3149 (N1.getValueType().isInteger() == VT.isInteger()) &&
3150 N1.getValueType() != VT &&
3151 "Wrong types for EXTRACT_ELEMENT!");
3153 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3154 // 64-bit integers into 32-bit parts. Instead of building the extract of
3155 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3156 if (N1.getOpcode() == ISD::BUILD_PAIR)
3157 return N1.getOperand(N2C->getZExtValue());
3159 // EXTRACT_ELEMENT of a constant int is also very common.
3160 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3161 unsigned ElementSize = VT.getSizeInBits();
3162 unsigned Shift = ElementSize * N2C->getZExtValue();
3163 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3164 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3167 case ISD::EXTRACT_SUBVECTOR: {
3169 if (VT.isSimple() && N1.getValueType().isSimple()) {
3170 assert(VT.isVector() && N1.getValueType().isVector() &&
3171 "Extract subvector VTs must be a vectors!");
3172 assert(VT.getVectorElementType() ==
3173 N1.getValueType().getVectorElementType() &&
3174 "Extract subvector VTs must have the same element type!");
3175 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3176 "Extract subvector must be from larger vector to smaller vector!");
3178 if (isa<ConstantSDNode>(Index.getNode())) {
3179 assert((VT.getVectorNumElements() +
3180 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3181 <= N1.getValueType().getVectorNumElements())
3182 && "Extract subvector overflow!");
3185 // Trivial extraction.
3186 if (VT.getSimpleVT() == N1.getSimpleValueType())
3193 // Perform trivial constant folding.
3194 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3195 if (SV.getNode()) return SV;
3197 // Canonicalize constant to RHS if commutative.
3198 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3199 std::swap(N1C, N2C);
3203 // Constant fold FP operations.
3204 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3205 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3207 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3208 // Canonicalize constant to RHS if commutative.
3209 std::swap(N1CFP, N2CFP);
3212 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3213 APFloat::opStatus s;
3216 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3217 if (s != APFloat::opInvalidOp)
3218 return getConstantFP(V1, VT);
3221 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3222 if (s!=APFloat::opInvalidOp)
3223 return getConstantFP(V1, VT);
3226 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3227 if (s!=APFloat::opInvalidOp)
3228 return getConstantFP(V1, VT);
3231 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3232 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3233 return getConstantFP(V1, VT);
3236 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3237 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3238 return getConstantFP(V1, VT);
3240 case ISD::FCOPYSIGN:
3242 return getConstantFP(V1, VT);
3247 if (Opcode == ISD::FP_ROUND) {
3248 APFloat V = N1CFP->getValueAPF(); // make copy
3250 // This can return overflow, underflow, or inexact; we don't care.
3251 // FIXME need to be more flexible about rounding mode.
3252 (void)V.convert(EVTToAPFloatSemantics(VT),
3253 APFloat::rmNearestTiesToEven, &ignored);
3254 return getConstantFP(V, VT);
3258 // Canonicalize an UNDEF to the RHS, even over a constant.
3259 if (N1.getOpcode() == ISD::UNDEF) {
3260 if (isCommutativeBinOp(Opcode)) {
3264 case ISD::FP_ROUND_INREG:
3265 case ISD::SIGN_EXTEND_INREG:
3271 return N1; // fold op(undef, arg2) -> undef
3279 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3280 // For vectors, we can't easily build an all zero vector, just return
3287 // Fold a bunch of operators when the RHS is undef.
3288 if (N2.getOpcode() == ISD::UNDEF) {
3291 if (N1.getOpcode() == ISD::UNDEF)
3292 // Handle undef ^ undef -> 0 special case. This is a common
3294 return getConstant(0, VT);
3304 return N2; // fold op(arg1, undef) -> undef
3310 if (getTarget().Options.UnsafeFPMath)
3318 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3319 // For vectors, we can't easily build an all zero vector, just return
3324 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3325 // For vectors, we can't easily build an all one vector, just return
3333 // Memoize this node if possible.
3335 SDVTList VTs = getVTList(VT);
3336 if (VT != MVT::Glue) {
3337 SDValue Ops[] = { N1, N2 };
3338 FoldingSetNodeID ID;
3339 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3341 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3342 return SDValue(E, 0);
3344 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3345 DL.getDebugLoc(), VTs, N1, N2);
3346 CSEMap.InsertNode(N, IP);
3348 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3349 DL.getDebugLoc(), VTs, N1, N2);
3352 AllNodes.push_back(N);
3356 return SDValue(N, 0);
3359 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3360 SDValue N1, SDValue N2, SDValue N3) {
3361 // Perform various simplifications.
3362 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3365 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3366 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3367 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3368 if (N1CFP && N2CFP && N3CFP) {
3369 APFloat V1 = N1CFP->getValueAPF();
3370 const APFloat &V2 = N2CFP->getValueAPF();
3371 const APFloat &V3 = N3CFP->getValueAPF();
3372 APFloat::opStatus s =
3373 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3374 if (s != APFloat::opInvalidOp)
3375 return getConstantFP(V1, VT);
3379 case ISD::CONCAT_VECTORS:
3380 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3381 // one big BUILD_VECTOR.
3382 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3383 N2.getOpcode() == ISD::BUILD_VECTOR &&
3384 N3.getOpcode() == ISD::BUILD_VECTOR) {
3385 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3386 N1.getNode()->op_end());
3387 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3388 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3389 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3393 // Use FoldSetCC to simplify SETCC's.
3394 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3395 if (Simp.getNode()) return Simp;
3400 if (N1C->getZExtValue())
3401 return N2; // select true, X, Y -> X
3402 return N3; // select false, X, Y -> Y
3405 if (N2 == N3) return N2; // select C, X, X -> X
3407 case ISD::VECTOR_SHUFFLE:
3408 llvm_unreachable("should use getVectorShuffle constructor!");
3409 case ISD::INSERT_SUBVECTOR: {
3411 if (VT.isSimple() && N1.getValueType().isSimple()
3412 && N2.getValueType().isSimple()) {
3413 assert(VT.isVector() && N1.getValueType().isVector() &&
3414 N2.getValueType().isVector() &&
3415 "Insert subvector VTs must be a vectors");
3416 assert(VT == N1.getValueType() &&
3417 "Dest and insert subvector source types must match!");
3418 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3419 "Insert subvector must be from smaller vector to larger vector!");
3420 if (isa<ConstantSDNode>(Index.getNode())) {
3421 assert((N2.getValueType().getVectorNumElements() +
3422 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3423 <= VT.getVectorNumElements())
3424 && "Insert subvector overflow!");
3427 // Trivial insertion.
3428 if (VT.getSimpleVT() == N2.getSimpleValueType())
3434 // Fold bit_convert nodes from a type to themselves.
3435 if (N1.getValueType() == VT)
3440 // Memoize node if it doesn't produce a flag.
3442 SDVTList VTs = getVTList(VT);
3443 if (VT != MVT::Glue) {
3444 SDValue Ops[] = { N1, N2, N3 };
3445 FoldingSetNodeID ID;
3446 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3448 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3449 return SDValue(E, 0);
3451 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3452 DL.getDebugLoc(), VTs, N1, N2, N3);
3453 CSEMap.InsertNode(N, IP);
3455 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3456 DL.getDebugLoc(), VTs, N1, N2, N3);
3459 AllNodes.push_back(N);
3463 return SDValue(N, 0);
3466 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3467 SDValue N1, SDValue N2, SDValue N3,
3469 SDValue Ops[] = { N1, N2, N3, N4 };
3470 return getNode(Opcode, DL, VT, Ops, 4);
3473 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3474 SDValue N1, SDValue N2, SDValue N3,
3475 SDValue N4, SDValue N5) {
3476 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3477 return getNode(Opcode, DL, VT, Ops, 5);
3480 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3481 /// the incoming stack arguments to be loaded from the stack.
3482 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3483 SmallVector<SDValue, 8> ArgChains;
3485 // Include the original chain at the beginning of the list. When this is
3486 // used by target LowerCall hooks, this helps legalize find the
3487 // CALLSEQ_BEGIN node.
3488 ArgChains.push_back(Chain);
3490 // Add a chain value for each stack argument.
3491 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3492 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3493 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3494 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3495 if (FI->getIndex() < 0)
3496 ArgChains.push_back(SDValue(L, 1));
3498 // Build a tokenfactor for all the chains.
3499 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3500 &ArgChains[0], ArgChains.size());
3503 /// getMemsetValue - Vectorized representation of the memset value
3505 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3507 assert(Value.getOpcode() != ISD::UNDEF);
3509 unsigned NumBits = VT.getScalarType().getSizeInBits();
3510 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3511 assert(C->getAPIntValue().getBitWidth() == 8);
3512 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3514 return DAG.getConstant(Val, VT);
3515 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3518 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3520 // Use a multiplication with 0x010101... to extend the input to the
3522 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3523 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3529 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3530 /// used when a memcpy is turned into a memset when the source is a constant
3532 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3533 const TargetLowering &TLI, StringRef Str) {
3534 // Handle vector with all elements zero.
3537 return DAG.getConstant(0, VT);
3538 else if (VT == MVT::f32 || VT == MVT::f64)
3539 return DAG.getConstantFP(0.0, VT);
3540 else if (VT.isVector()) {
3541 unsigned NumElts = VT.getVectorNumElements();
3542 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3543 return DAG.getNode(ISD::BITCAST, dl, VT,
3544 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3547 llvm_unreachable("Expected type!");
3550 assert(!VT.isVector() && "Can't handle vector type here!");
3551 unsigned NumVTBits = VT.getSizeInBits();
3552 unsigned NumVTBytes = NumVTBits / 8;
3553 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3555 APInt Val(NumVTBits, 0);
3556 if (TLI.isLittleEndian()) {
3557 for (unsigned i = 0; i != NumBytes; ++i)
3558 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3560 for (unsigned i = 0; i != NumBytes; ++i)
3561 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3564 // If the "cost" of materializing the integer immediate is 1 or free, then
3565 // it is cost effective to turn the load into the immediate.
3566 const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
3567 if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
3568 return DAG.getConstant(Val, VT);
3569 return SDValue(0, 0);
3572 /// getMemBasePlusOffset - Returns base and offset node for the
3574 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3575 SelectionDAG &DAG) {
3576 EVT VT = Base.getValueType();
3577 return DAG.getNode(ISD::ADD, dl,
3578 VT, Base, DAG.getConstant(Offset, VT));
3581 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3583 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3584 unsigned SrcDelta = 0;
3585 GlobalAddressSDNode *G = NULL;
3586 if (Src.getOpcode() == ISD::GlobalAddress)
3587 G = cast<GlobalAddressSDNode>(Src);
3588 else if (Src.getOpcode() == ISD::ADD &&
3589 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3590 Src.getOperand(1).getOpcode() == ISD::Constant) {
3591 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3592 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3597 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3600 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3601 /// to replace the memset / memcpy. Return true if the number of memory ops
3602 /// is below the threshold. It returns the types of the sequence of
3603 /// memory ops to perform memset / memcpy by reference.
3604 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3605 unsigned Limit, uint64_t Size,
3606 unsigned DstAlign, unsigned SrcAlign,
3612 const TargetLowering &TLI) {
3613 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3614 "Expecting memcpy / memset source to meet alignment requirement!");
3615 // If 'SrcAlign' is zero, that means the memory operation does not need to
3616 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3617 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3618 // is the specified alignment of the memory operation. If it is zero, that
3619 // means it's possible to change the alignment of the destination.
3620 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3621 // not need to be loaded.
3622 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3623 IsMemset, ZeroMemset, MemcpyStrSrc,
3624 DAG.getMachineFunction());
3626 if (VT == MVT::Other) {
3627 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3628 TLI.allowsUnalignedMemoryAccesses(VT)) {
3629 VT = TLI.getPointerTy();
3631 switch (DstAlign & 7) {
3632 case 0: VT = MVT::i64; break;
3633 case 4: VT = MVT::i32; break;
3634 case 2: VT = MVT::i16; break;
3635 default: VT = MVT::i8; break;
3640 while (!TLI.isTypeLegal(LVT))
3641 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3642 assert(LVT.isInteger());
3648 unsigned NumMemOps = 0;
3650 unsigned VTSize = VT.getSizeInBits() / 8;
3651 while (VTSize > Size) {
3652 // For now, only use non-vector load / store's for the left-over pieces.
3657 if (VT.isVector() || VT.isFloatingPoint()) {
3658 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3659 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3660 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3662 else if (NewVT == MVT::i64 &&
3663 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3664 TLI.isSafeMemOpType(MVT::f64)) {
3665 // i64 is usually not legal on 32-bit targets, but f64 may be.
3673 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3674 if (NewVT == MVT::i8)
3676 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3678 NewVTSize = NewVT.getSizeInBits() / 8;
3680 // If the new VT cannot cover all of the remaining bits, then consider
3681 // issuing a (or a pair of) unaligned and overlapping load / store.
3682 // FIXME: Only does this for 64-bit or more since we don't have proper
3683 // cost model for unaligned load / store.
3685 if (NumMemOps && AllowOverlap &&
3686 VTSize >= 8 && NewVTSize < Size &&
3687 TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3695 if (++NumMemOps > Limit)
3698 MemOps.push_back(VT);
3705 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3706 SDValue Chain, SDValue Dst,
3707 SDValue Src, uint64_t Size,
3708 unsigned Align, bool isVol,
3710 MachinePointerInfo DstPtrInfo,
3711 MachinePointerInfo SrcPtrInfo) {
3712 // Turn a memcpy of undef to nop.
3713 if (Src.getOpcode() == ISD::UNDEF)
3716 // Expand memcpy to a series of load and store ops if the size operand falls
3717 // below a certain threshold.
3718 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3719 // rather than maybe a humongous number of loads and stores.
3720 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3721 std::vector<EVT> MemOps;
3722 bool DstAlignCanChange = false;
3723 MachineFunction &MF = DAG.getMachineFunction();
3724 MachineFrameInfo *MFI = MF.getFrameInfo();
3726 MF.getFunction()->getAttributes().
3727 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3728 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3729 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3730 DstAlignCanChange = true;
3731 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3732 if (Align > SrcAlign)
3735 bool CopyFromStr = isMemSrcFromString(Src, Str);
3736 bool isZeroStr = CopyFromStr && Str.empty();
3737 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3739 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3740 (DstAlignCanChange ? 0 : Align),
3741 (isZeroStr ? 0 : SrcAlign),
3742 false, false, CopyFromStr, true, DAG, TLI))
3745 if (DstAlignCanChange) {
3746 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3747 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3749 // Don't promote to an alignment that would require dynamic stack
3751 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3752 if (!TRI->needsStackRealignment(MF))
3753 while (NewAlign > Align &&
3754 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3757 if (NewAlign > Align) {
3758 // Give the stack frame object a larger alignment if needed.
3759 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3760 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3765 SmallVector<SDValue, 8> OutChains;
3766 unsigned NumMemOps = MemOps.size();
3767 uint64_t SrcOff = 0, DstOff = 0;
3768 for (unsigned i = 0; i != NumMemOps; ++i) {
3770 unsigned VTSize = VT.getSizeInBits() / 8;
3771 SDValue Value, Store;
3773 if (VTSize > Size) {
3774 // Issuing an unaligned load / store pair that overlaps with the previous
3775 // pair. Adjust the offset accordingly.
3776 assert(i == NumMemOps-1 && i != 0);
3777 SrcOff -= VTSize - Size;
3778 DstOff -= VTSize - Size;
3782 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3783 // It's unlikely a store of a vector immediate can be done in a single
3784 // instruction. It would require a load from a constantpool first.
3785 // We only handle zero vectors here.
3786 // FIXME: Handle other cases where store of vector immediate is done in
3787 // a single instruction.
3788 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3789 if (Value.getNode())
3790 Store = DAG.getStore(Chain, dl, Value,
3791 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3792 DstPtrInfo.getWithOffset(DstOff), isVol,
3796 if (!Store.getNode()) {
3797 // The type might not be legal for the target. This should only happen
3798 // if the type is smaller than a legal type, as on PPC, so the right
3799 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3800 // to Load/Store if NVT==VT.
3801 // FIXME does the case above also need this?
3802 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3803 assert(NVT.bitsGE(VT));
3804 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3805 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3806 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3807 MinAlign(SrcAlign, SrcOff));
3808 Store = DAG.getTruncStore(Chain, dl, Value,
3809 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3810 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3813 OutChains.push_back(Store);
3819 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3820 &OutChains[0], OutChains.size());
3823 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3824 SDValue Chain, SDValue Dst,
3825 SDValue Src, uint64_t Size,
3826 unsigned Align, bool isVol,
3828 MachinePointerInfo DstPtrInfo,
3829 MachinePointerInfo SrcPtrInfo) {
3830 // Turn a memmove of undef to nop.
3831 if (Src.getOpcode() == ISD::UNDEF)
3834 // Expand memmove to a series of load and store ops if the size operand falls
3835 // below a certain threshold.
3836 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3837 std::vector<EVT> MemOps;
3838 bool DstAlignCanChange = false;
3839 MachineFunction &MF = DAG.getMachineFunction();
3840 MachineFrameInfo *MFI = MF.getFrameInfo();
3841 bool OptSize = MF.getFunction()->getAttributes().
3842 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3843 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3844 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3845 DstAlignCanChange = true;
3846 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3847 if (Align > SrcAlign)
3849 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3851 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3852 (DstAlignCanChange ? 0 : Align), SrcAlign,
3853 false, false, false, false, DAG, TLI))
3856 if (DstAlignCanChange) {
3857 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3858 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3859 if (NewAlign > Align) {
3860 // Give the stack frame object a larger alignment if needed.
3861 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3862 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3867 uint64_t SrcOff = 0, DstOff = 0;
3868 SmallVector<SDValue, 8> LoadValues;
3869 SmallVector<SDValue, 8> LoadChains;
3870 SmallVector<SDValue, 8> OutChains;
3871 unsigned NumMemOps = MemOps.size();
3872 for (unsigned i = 0; i < NumMemOps; i++) {
3874 unsigned VTSize = VT.getSizeInBits() / 8;
3877 Value = DAG.getLoad(VT, dl, Chain,
3878 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3879 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3880 false, false, SrcAlign);
3881 LoadValues.push_back(Value);
3882 LoadChains.push_back(Value.getValue(1));
3885 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3886 &LoadChains[0], LoadChains.size());
3888 for (unsigned i = 0; i < NumMemOps; i++) {
3890 unsigned VTSize = VT.getSizeInBits() / 8;
3893 Store = DAG.getStore(Chain, dl, LoadValues[i],
3894 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3895 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3896 OutChains.push_back(Store);
3900 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3901 &OutChains[0], OutChains.size());
3904 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3907 /// \param DAG Selection DAG where lowered code is placed.
3908 /// \param dl Link to corresponding IR location.
3909 /// \param Chain Control flow dependency.
3910 /// \param Dst Pointer to destination memory location.
3911 /// \param Src Value of byte to write into the memory.
3912 /// \param Size Number of bytes to write.
3913 /// \param Align Alignment of the destination in bytes.
3914 /// \param isVol True if destination is volatile.
3915 /// \param DstPtrInfo IR information on the memory pointer.
3916 /// \returns New head in the control flow, if lowering was successful, empty
3917 /// SDValue otherwise.
3919 /// The function tries to replace 'llvm.memset' intrinsic with several store
3920 /// operations and value calculation code. This is usually profitable for small
3922 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3923 SDValue Chain, SDValue Dst,
3924 SDValue Src, uint64_t Size,
3925 unsigned Align, bool isVol,
3926 MachinePointerInfo DstPtrInfo) {
3927 // Turn a memset of undef to nop.
3928 if (Src.getOpcode() == ISD::UNDEF)
3931 // Expand memset to a series of load/store ops if the size operand
3932 // falls below a certain threshold.
3933 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3934 std::vector<EVT> MemOps;
3935 bool DstAlignCanChange = false;
3936 MachineFunction &MF = DAG.getMachineFunction();
3937 MachineFrameInfo *MFI = MF.getFrameInfo();
3938 bool OptSize = MF.getFunction()->getAttributes().
3939 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3940 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3941 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3942 DstAlignCanChange = true;
3944 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3945 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3946 Size, (DstAlignCanChange ? 0 : Align), 0,
3947 true, IsZeroVal, false, true, DAG, TLI))
3950 if (DstAlignCanChange) {
3951 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3952 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3953 if (NewAlign > Align) {
3954 // Give the stack frame object a larger alignment if needed.
3955 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3956 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3961 SmallVector<SDValue, 8> OutChains;
3962 uint64_t DstOff = 0;
3963 unsigned NumMemOps = MemOps.size();
3965 // Find the largest store and generate the bit pattern for it.
3966 EVT LargestVT = MemOps[0];
3967 for (unsigned i = 1; i < NumMemOps; i++)
3968 if (MemOps[i].bitsGT(LargestVT))
3969 LargestVT = MemOps[i];
3970 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3972 for (unsigned i = 0; i < NumMemOps; i++) {
3974 unsigned VTSize = VT.getSizeInBits() / 8;
3975 if (VTSize > Size) {
3976 // Issuing an unaligned load / store pair that overlaps with the previous
3977 // pair. Adjust the offset accordingly.
3978 assert(i == NumMemOps-1 && i != 0);
3979 DstOff -= VTSize - Size;
3982 // If this store is smaller than the largest store see whether we can get
3983 // the smaller value for free with a truncate.
3984 SDValue Value = MemSetValue;
3985 if (VT.bitsLT(LargestVT)) {
3986 if (!LargestVT.isVector() && !VT.isVector() &&
3987 TLI.isTruncateFree(LargestVT, VT))
3988 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3990 Value = getMemsetValue(Src, VT, DAG, dl);
3992 assert(Value.getValueType() == VT && "Value with wrong type.");
3993 SDValue Store = DAG.getStore(Chain, dl, Value,
3994 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3995 DstPtrInfo.getWithOffset(DstOff),
3996 isVol, false, Align);
3997 OutChains.push_back(Store);
3998 DstOff += VT.getSizeInBits() / 8;
4002 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4003 &OutChains[0], OutChains.size());
4006 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4007 SDValue Src, SDValue Size,
4008 unsigned Align, bool isVol, bool AlwaysInline,
4009 MachinePointerInfo DstPtrInfo,
4010 MachinePointerInfo SrcPtrInfo) {
4011 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4013 // Check to see if we should lower the memcpy to loads and stores first.
4014 // For cases within the target-specified limits, this is the best choice.
4015 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4017 // Memcpy with size zero? Just return the original chain.
4018 if (ConstantSize->isNullValue())
4021 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4022 ConstantSize->getZExtValue(),Align,
4023 isVol, false, DstPtrInfo, SrcPtrInfo);
4024 if (Result.getNode())
4028 // Then check to see if we should lower the memcpy with target-specific
4029 // code. If the target chooses to do this, this is the next best.
4031 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4032 isVol, AlwaysInline,
4033 DstPtrInfo, SrcPtrInfo);
4034 if (Result.getNode())
4037 // If we really need inline code and the target declined to provide it,
4038 // use a (potentially long) sequence of loads and stores.
4040 assert(ConstantSize && "AlwaysInline requires a constant size!");
4041 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4042 ConstantSize->getZExtValue(), Align, isVol,
4043 true, DstPtrInfo, SrcPtrInfo);
4046 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4047 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4048 // respect volatile, so they may do things like read or write memory
4049 // beyond the given memory regions. But fixing this isn't easy, and most
4050 // people don't care.
4052 const TargetLowering *TLI = TM.getTargetLowering();
4054 // Emit a library call.
4055 TargetLowering::ArgListTy Args;
4056 TargetLowering::ArgListEntry Entry;
4057 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4058 Entry.Node = Dst; Args.push_back(Entry);
4059 Entry.Node = Src; Args.push_back(Entry);
4060 Entry.Node = Size; Args.push_back(Entry);
4061 // FIXME: pass in SDLoc
4063 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4064 false, false, false, false, 0,
4065 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4066 /*isTailCall=*/false,
4067 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4068 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4069 TLI->getPointerTy()),
4071 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4073 return CallResult.second;
4076 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4077 SDValue Src, SDValue Size,
4078 unsigned Align, bool isVol,
4079 MachinePointerInfo DstPtrInfo,
4080 MachinePointerInfo SrcPtrInfo) {
4081 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4083 // Check to see if we should lower the memmove to loads and stores first.
4084 // For cases within the target-specified limits, this is the best choice.
4085 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4087 // Memmove with size zero? Just return the original chain.
4088 if (ConstantSize->isNullValue())
4092 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4093 ConstantSize->getZExtValue(), Align, isVol,
4094 false, DstPtrInfo, SrcPtrInfo);
4095 if (Result.getNode())
4099 // Then check to see if we should lower the memmove with target-specific
4100 // code. If the target chooses to do this, this is the next best.
4102 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4103 DstPtrInfo, SrcPtrInfo);
4104 if (Result.getNode())
4107 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4108 // not be safe. See memcpy above for more details.
4110 const TargetLowering *TLI = TM.getTargetLowering();
4112 // Emit a library call.
4113 TargetLowering::ArgListTy Args;
4114 TargetLowering::ArgListEntry Entry;
4115 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4116 Entry.Node = Dst; Args.push_back(Entry);
4117 Entry.Node = Src; Args.push_back(Entry);
4118 Entry.Node = Size; Args.push_back(Entry);
4119 // FIXME: pass in SDLoc
4121 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4122 false, false, false, false, 0,
4123 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4124 /*isTailCall=*/false,
4125 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4126 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4127 TLI->getPointerTy()),
4129 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4131 return CallResult.second;
4134 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4135 SDValue Src, SDValue Size,
4136 unsigned Align, bool isVol,
4137 MachinePointerInfo DstPtrInfo) {
4138 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4140 // Check to see if we should lower the memset to stores first.
4141 // For cases within the target-specified limits, this is the best choice.
4142 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4144 // Memset with size zero? Just return the original chain.
4145 if (ConstantSize->isNullValue())
4149 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4150 Align, isVol, DstPtrInfo);
4152 if (Result.getNode())
4156 // Then check to see if we should lower the memset with target-specific
4157 // code. If the target chooses to do this, this is the next best.
4159 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4161 if (Result.getNode())
4164 // Emit a library call.
4165 const TargetLowering *TLI = TM.getTargetLowering();
4166 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4167 TargetLowering::ArgListTy Args;
4168 TargetLowering::ArgListEntry Entry;
4169 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4170 Args.push_back(Entry);
4171 // Extend or truncate the argument to be an i32 value for the call.
4172 if (Src.getValueType().bitsGT(MVT::i32))
4173 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4175 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4177 Entry.Ty = Type::getInt32Ty(*getContext());
4178 Entry.isSExt = true;
4179 Args.push_back(Entry);
4181 Entry.Ty = IntPtrTy;
4182 Entry.isSExt = false;
4183 Args.push_back(Entry);
4184 // FIXME: pass in SDLoc
4186 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4187 false, false, false, false, 0,
4188 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4189 /*isTailCall=*/false,
4190 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4191 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4192 TLI->getPointerTy()),
4194 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4196 return CallResult.second;
4199 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4200 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4201 MachineMemOperand *MMO,
4202 AtomicOrdering Ordering,
4203 SynchronizationScope SynchScope) {
4204 FoldingSetNodeID ID;
4205 ID.AddInteger(MemVT.getRawBits());
4206 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4207 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4209 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4210 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4211 return SDValue(E, 0);
4214 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4215 // SDNode doesn't have access to it. This memory will be "leaked" when
4216 // the node is deallocated, but recovered when the allocator is released.
4217 // If the number of operands is less than 5 we use AtomicSDNode's internal
4219 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4221 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4222 dl.getDebugLoc(), VTList, MemVT,
4223 Ops, DynOps, NumOps, MMO,
4224 Ordering, SynchScope);
4225 CSEMap.InsertNode(N, IP);
4226 AllNodes.push_back(N);
4227 return SDValue(N, 0);
4230 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4231 SDValue Chain, SDValue Ptr, SDValue Cmp,
4232 SDValue Swp, MachinePointerInfo PtrInfo,
4234 AtomicOrdering Ordering,
4235 SynchronizationScope SynchScope) {
4236 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4237 Alignment = getEVTAlignment(MemVT);
4239 MachineFunction &MF = getMachineFunction();
4241 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4242 // For now, atomics are considered to be volatile always.
4243 // FIXME: Volatile isn't really correct; we should keep track of atomic
4244 // orderings in the memoperand.
4245 unsigned Flags = MachineMemOperand::MOVolatile;
4246 if (Opcode != ISD::ATOMIC_STORE)
4247 Flags |= MachineMemOperand::MOLoad;
4248 if (Opcode != ISD::ATOMIC_LOAD)
4249 Flags |= MachineMemOperand::MOStore;
4251 MachineMemOperand *MMO =
4252 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4254 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4255 Ordering, SynchScope);
4258 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4260 SDValue Ptr, SDValue Cmp,
4261 SDValue Swp, MachineMemOperand *MMO,
4262 AtomicOrdering Ordering,
4263 SynchronizationScope SynchScope) {
4264 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4265 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4267 EVT VT = Cmp.getValueType();
4269 SDVTList VTs = getVTList(VT, MVT::Other);
4270 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4271 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4274 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4276 SDValue Ptr, SDValue Val,
4277 const Value* PtrVal,
4279 AtomicOrdering Ordering,
4280 SynchronizationScope SynchScope) {
4281 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4282 Alignment = getEVTAlignment(MemVT);
4284 MachineFunction &MF = getMachineFunction();
4285 // An atomic store does not load. An atomic load does not store.
4286 // (An atomicrmw obviously both loads and stores.)
4287 // For now, atomics are considered to be volatile always, and they are
4289 // FIXME: Volatile isn't really correct; we should keep track of atomic
4290 // orderings in the memoperand.
4291 unsigned Flags = MachineMemOperand::MOVolatile;
4292 if (Opcode != ISD::ATOMIC_STORE)
4293 Flags |= MachineMemOperand::MOLoad;
4294 if (Opcode != ISD::ATOMIC_LOAD)
4295 Flags |= MachineMemOperand::MOStore;
4297 MachineMemOperand *MMO =
4298 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4299 MemVT.getStoreSize(), Alignment);
4301 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4302 Ordering, SynchScope);
4305 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4307 SDValue Ptr, SDValue Val,
4308 MachineMemOperand *MMO,
4309 AtomicOrdering Ordering,
4310 SynchronizationScope SynchScope) {
4311 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4312 Opcode == ISD::ATOMIC_LOAD_SUB ||
4313 Opcode == ISD::ATOMIC_LOAD_AND ||
4314 Opcode == ISD::ATOMIC_LOAD_OR ||
4315 Opcode == ISD::ATOMIC_LOAD_XOR ||
4316 Opcode == ISD::ATOMIC_LOAD_NAND ||
4317 Opcode == ISD::ATOMIC_LOAD_MIN ||
4318 Opcode == ISD::ATOMIC_LOAD_MAX ||
4319 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4320 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4321 Opcode == ISD::ATOMIC_SWAP ||
4322 Opcode == ISD::ATOMIC_STORE) &&
4323 "Invalid Atomic Op");
4325 EVT VT = Val.getValueType();
4327 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4328 getVTList(VT, MVT::Other);
4329 SDValue Ops[] = {Chain, Ptr, Val};
4330 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4333 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4334 EVT VT, SDValue Chain,
4336 const Value* PtrVal,
4338 AtomicOrdering Ordering,
4339 SynchronizationScope SynchScope) {
4340 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4341 Alignment = getEVTAlignment(MemVT);
4343 MachineFunction &MF = getMachineFunction();
4344 // An atomic store does not load. An atomic load does not store.
4345 // (An atomicrmw obviously both loads and stores.)
4346 // For now, atomics are considered to be volatile always, and they are
4348 // FIXME: Volatile isn't really correct; we should keep track of atomic
4349 // orderings in the memoperand.
4350 unsigned Flags = MachineMemOperand::MOVolatile;
4351 if (Opcode != ISD::ATOMIC_STORE)
4352 Flags |= MachineMemOperand::MOLoad;
4353 if (Opcode != ISD::ATOMIC_LOAD)
4354 Flags |= MachineMemOperand::MOStore;
4356 MachineMemOperand *MMO =
4357 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4358 MemVT.getStoreSize(), Alignment);
4360 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4361 Ordering, SynchScope);
4364 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4365 EVT VT, SDValue Chain,
4367 MachineMemOperand *MMO,
4368 AtomicOrdering Ordering,
4369 SynchronizationScope SynchScope) {
4370 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4372 SDVTList VTs = getVTList(VT, MVT::Other);
4373 SDValue Ops[] = {Chain, Ptr};
4374 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4377 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4378 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4383 SmallVector<EVT, 4> VTs;
4384 VTs.reserve(NumOps);
4385 for (unsigned i = 0; i < NumOps; ++i)
4386 VTs.push_back(Ops[i].getValueType());
4387 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4392 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4393 const EVT *VTs, unsigned NumVTs,
4394 const SDValue *Ops, unsigned NumOps,
4395 EVT MemVT, MachinePointerInfo PtrInfo,
4396 unsigned Align, bool Vol,
4397 bool ReadMem, bool WriteMem) {
4398 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4399 MemVT, PtrInfo, Align, Vol,
4404 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4405 const SDValue *Ops, unsigned NumOps,
4406 EVT MemVT, MachinePointerInfo PtrInfo,
4407 unsigned Align, bool Vol,
4408 bool ReadMem, bool WriteMem) {
4409 if (Align == 0) // Ensure that codegen never sees alignment 0
4410 Align = getEVTAlignment(MemVT);
4412 MachineFunction &MF = getMachineFunction();
4415 Flags |= MachineMemOperand::MOStore;
4417 Flags |= MachineMemOperand::MOLoad;
4419 Flags |= MachineMemOperand::MOVolatile;
4420 MachineMemOperand *MMO =
4421 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4423 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4427 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4428 const SDValue *Ops, unsigned NumOps,
4429 EVT MemVT, MachineMemOperand *MMO) {
4430 assert((Opcode == ISD::INTRINSIC_VOID ||
4431 Opcode == ISD::INTRINSIC_W_CHAIN ||
4432 Opcode == ISD::PREFETCH ||
4433 Opcode == ISD::LIFETIME_START ||
4434 Opcode == ISD::LIFETIME_END ||
4435 (Opcode <= INT_MAX &&
4436 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4437 "Opcode is not a memory-accessing opcode!");
4439 // Memoize the node unless it returns a flag.
4440 MemIntrinsicSDNode *N;
4441 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4442 FoldingSetNodeID ID;
4443 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4444 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4446 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4447 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4448 return SDValue(E, 0);
4451 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4452 dl.getDebugLoc(), VTList, Ops,
4453 NumOps, MemVT, MMO);
4454 CSEMap.InsertNode(N, IP);
4456 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4457 dl.getDebugLoc(), VTList, Ops,
4458 NumOps, MemVT, MMO);
4460 AllNodes.push_back(N);
4461 return SDValue(N, 0);
4464 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4465 /// MachinePointerInfo record from it. This is particularly useful because the
4466 /// code generator has many cases where it doesn't bother passing in a
4467 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4468 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4469 // If this is FI+Offset, we can model it.
4470 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4471 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4473 // If this is (FI+Offset1)+Offset2, we can model it.
4474 if (Ptr.getOpcode() != ISD::ADD ||
4475 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4476 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4477 return MachinePointerInfo();
4479 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4480 return MachinePointerInfo::getFixedStack(FI, Offset+
4481 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4484 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4485 /// MachinePointerInfo record from it. This is particularly useful because the
4486 /// code generator has many cases where it doesn't bother passing in a
4487 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4488 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4489 // If the 'Offset' value isn't a constant, we can't handle this.
4490 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4491 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4492 if (OffsetOp.getOpcode() == ISD::UNDEF)
4493 return InferPointerInfo(Ptr);
4494 return MachinePointerInfo();
4499 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4500 EVT VT, SDLoc dl, SDValue Chain,
4501 SDValue Ptr, SDValue Offset,
4502 MachinePointerInfo PtrInfo, EVT MemVT,
4503 bool isVolatile, bool isNonTemporal, bool isInvariant,
4504 unsigned Alignment, const MDNode *TBAAInfo,
4505 const MDNode *Ranges) {
4506 assert(Chain.getValueType() == MVT::Other &&
4507 "Invalid chain type");
4508 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4509 Alignment = getEVTAlignment(VT);
4511 unsigned Flags = MachineMemOperand::MOLoad;
4513 Flags |= MachineMemOperand::MOVolatile;
4515 Flags |= MachineMemOperand::MONonTemporal;
4517 Flags |= MachineMemOperand::MOInvariant;
4519 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4522 PtrInfo = InferPointerInfo(Ptr, Offset);
4524 MachineFunction &MF = getMachineFunction();
4525 MachineMemOperand *MMO =
4526 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4528 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4532 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4533 EVT VT, SDLoc dl, SDValue Chain,
4534 SDValue Ptr, SDValue Offset, EVT MemVT,
4535 MachineMemOperand *MMO) {
4537 ExtType = ISD::NON_EXTLOAD;
4538 } else if (ExtType == ISD::NON_EXTLOAD) {
4539 assert(VT == MemVT && "Non-extending load from different memory type!");
4542 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4543 "Should only be an extending load, not truncating!");
4544 assert(VT.isInteger() == MemVT.isInteger() &&
4545 "Cannot convert from FP to Int or Int -> FP!");
4546 assert(VT.isVector() == MemVT.isVector() &&
4547 "Cannot use trunc store to convert to or from a vector!");
4548 assert((!VT.isVector() ||
4549 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4550 "Cannot use trunc store to change the number of vector elements!");
4553 bool Indexed = AM != ISD::UNINDEXED;
4554 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4555 "Unindexed load with an offset!");
4557 SDVTList VTs = Indexed ?
4558 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4559 SDValue Ops[] = { Chain, Ptr, Offset };
4560 FoldingSetNodeID ID;
4561 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4562 ID.AddInteger(MemVT.getRawBits());
4563 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4564 MMO->isNonTemporal(),
4565 MMO->isInvariant()));
4566 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4568 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4569 cast<LoadSDNode>(E)->refineAlignment(MMO);
4570 return SDValue(E, 0);
4572 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4573 dl.getDebugLoc(), VTs, AM, ExtType,
4575 CSEMap.InsertNode(N, IP);
4576 AllNodes.push_back(N);
4577 return SDValue(N, 0);
4580 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4581 SDValue Chain, SDValue Ptr,
4582 MachinePointerInfo PtrInfo,
4583 bool isVolatile, bool isNonTemporal,
4584 bool isInvariant, unsigned Alignment,
4585 const MDNode *TBAAInfo,
4586 const MDNode *Ranges) {
4587 SDValue Undef = getUNDEF(Ptr.getValueType());
4588 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4589 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4593 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4594 SDValue Chain, SDValue Ptr,
4595 MachineMemOperand *MMO) {
4596 SDValue Undef = getUNDEF(Ptr.getValueType());
4597 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4601 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4602 SDValue Chain, SDValue Ptr,
4603 MachinePointerInfo PtrInfo, EVT MemVT,
4604 bool isVolatile, bool isNonTemporal,
4605 unsigned Alignment, const MDNode *TBAAInfo) {
4606 SDValue Undef = getUNDEF(Ptr.getValueType());
4607 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4608 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4613 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4614 SDValue Chain, SDValue Ptr, EVT MemVT,
4615 MachineMemOperand *MMO) {
4616 SDValue Undef = getUNDEF(Ptr.getValueType());
4617 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4622 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4623 SDValue Offset, ISD::MemIndexedMode AM) {
4624 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4625 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4626 "Load is already a indexed load!");
4627 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4628 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4629 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4630 false, LD->getAlignment());
4633 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4634 SDValue Ptr, MachinePointerInfo PtrInfo,
4635 bool isVolatile, bool isNonTemporal,
4636 unsigned Alignment, const MDNode *TBAAInfo) {
4637 assert(Chain.getValueType() == MVT::Other &&
4638 "Invalid chain type");
4639 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4640 Alignment = getEVTAlignment(Val.getValueType());
4642 unsigned Flags = MachineMemOperand::MOStore;
4644 Flags |= MachineMemOperand::MOVolatile;
4646 Flags |= MachineMemOperand::MONonTemporal;
4649 PtrInfo = InferPointerInfo(Ptr);
4651 MachineFunction &MF = getMachineFunction();
4652 MachineMemOperand *MMO =
4653 MF.getMachineMemOperand(PtrInfo, Flags,
4654 Val.getValueType().getStoreSize(), Alignment,
4657 return getStore(Chain, dl, Val, Ptr, MMO);
4660 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4661 SDValue Ptr, MachineMemOperand *MMO) {
4662 assert(Chain.getValueType() == MVT::Other &&
4663 "Invalid chain type");
4664 EVT VT = Val.getValueType();
4665 SDVTList VTs = getVTList(MVT::Other);
4666 SDValue Undef = getUNDEF(Ptr.getValueType());
4667 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4668 FoldingSetNodeID ID;
4669 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4670 ID.AddInteger(VT.getRawBits());
4671 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4672 MMO->isNonTemporal(), MMO->isInvariant()));
4673 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4675 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4676 cast<StoreSDNode>(E)->refineAlignment(MMO);
4677 return SDValue(E, 0);
4679 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4680 dl.getDebugLoc(), VTs,
4681 ISD::UNINDEXED, false, VT, MMO);
4682 CSEMap.InsertNode(N, IP);
4683 AllNodes.push_back(N);
4684 return SDValue(N, 0);
4687 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4688 SDValue Ptr, MachinePointerInfo PtrInfo,
4689 EVT SVT,bool isVolatile, bool isNonTemporal,
4691 const MDNode *TBAAInfo) {
4692 assert(Chain.getValueType() == MVT::Other &&
4693 "Invalid chain type");
4694 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4695 Alignment = getEVTAlignment(SVT);
4697 unsigned Flags = MachineMemOperand::MOStore;
4699 Flags |= MachineMemOperand::MOVolatile;
4701 Flags |= MachineMemOperand::MONonTemporal;
4704 PtrInfo = InferPointerInfo(Ptr);
4706 MachineFunction &MF = getMachineFunction();
4707 MachineMemOperand *MMO =
4708 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4711 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4714 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4715 SDValue Ptr, EVT SVT,
4716 MachineMemOperand *MMO) {
4717 EVT VT = Val.getValueType();
4719 assert(Chain.getValueType() == MVT::Other &&
4720 "Invalid chain type");
4722 return getStore(Chain, dl, Val, Ptr, MMO);
4724 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4725 "Should only be a truncating store, not extending!");
4726 assert(VT.isInteger() == SVT.isInteger() &&
4727 "Can't do FP-INT conversion!");
4728 assert(VT.isVector() == SVT.isVector() &&
4729 "Cannot use trunc store to convert to or from a vector!");
4730 assert((!VT.isVector() ||
4731 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4732 "Cannot use trunc store to change the number of vector elements!");
4734 SDVTList VTs = getVTList(MVT::Other);
4735 SDValue Undef = getUNDEF(Ptr.getValueType());
4736 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4737 FoldingSetNodeID ID;
4738 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4739 ID.AddInteger(SVT.getRawBits());
4740 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4741 MMO->isNonTemporal(), MMO->isInvariant()));
4742 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4744 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4745 cast<StoreSDNode>(E)->refineAlignment(MMO);
4746 return SDValue(E, 0);
4748 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4749 dl.getDebugLoc(), VTs,
4750 ISD::UNINDEXED, true, SVT, MMO);
4751 CSEMap.InsertNode(N, IP);
4752 AllNodes.push_back(N);
4753 return SDValue(N, 0);
4757 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4758 SDValue Offset, ISD::MemIndexedMode AM) {
4759 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4760 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4761 "Store is already a indexed store!");
4762 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4763 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4764 FoldingSetNodeID ID;
4765 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4766 ID.AddInteger(ST->getMemoryVT().getRawBits());
4767 ID.AddInteger(ST->getRawSubclassData());
4768 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4770 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4771 return SDValue(E, 0);
4773 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4774 dl.getDebugLoc(), VTs, AM,
4775 ST->isTruncatingStore(),
4777 ST->getMemOperand());
4778 CSEMap.InsertNode(N, IP);
4779 AllNodes.push_back(N);
4780 return SDValue(N, 0);
4783 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4784 SDValue Chain, SDValue Ptr,
4787 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4788 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4791 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4792 const SDUse *Ops, unsigned NumOps) {
4794 case 0: return getNode(Opcode, DL, VT);
4795 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4796 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4797 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4801 // Copy from an SDUse array into an SDValue array for use with
4802 // the regular getNode logic.
4803 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4804 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4807 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4808 const SDValue *Ops, unsigned NumOps) {
4810 case 0: return getNode(Opcode, DL, VT);
4811 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4812 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4813 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4819 case ISD::SELECT_CC: {
4820 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4821 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4822 "LHS and RHS of condition must have same type!");
4823 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4824 "True and False arms of SelectCC must have same type!");
4825 assert(Ops[2].getValueType() == VT &&
4826 "select_cc node must be of same type as true and false value!");
4830 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4831 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4832 "LHS/RHS of comparison should match types!");
4839 SDVTList VTs = getVTList(VT);
4841 if (VT != MVT::Glue) {
4842 FoldingSetNodeID ID;
4843 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4846 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4847 return SDValue(E, 0);
4849 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4851 CSEMap.InsertNode(N, IP);
4853 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4857 AllNodes.push_back(N);
4861 return SDValue(N, 0);
4864 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4865 ArrayRef<EVT> ResultTys,
4866 const SDValue *Ops, unsigned NumOps) {
4867 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4871 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4872 const EVT *VTs, unsigned NumVTs,
4873 const SDValue *Ops, unsigned NumOps) {
4875 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4876 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4879 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4880 const SDValue *Ops, unsigned NumOps) {
4881 if (VTList.NumVTs == 1)
4882 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4886 // FIXME: figure out how to safely handle things like
4887 // int foo(int x) { return 1 << (x & 255); }
4888 // int bar() { return foo(256); }
4889 case ISD::SRA_PARTS:
4890 case ISD::SRL_PARTS:
4891 case ISD::SHL_PARTS:
4892 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4893 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4894 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4895 else if (N3.getOpcode() == ISD::AND)
4896 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4897 // If the and is only masking out bits that cannot effect the shift,
4898 // eliminate the and.
4899 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4900 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4901 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4907 // Memoize the node unless it returns a flag.
4909 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4910 FoldingSetNodeID ID;
4911 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4913 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4914 return SDValue(E, 0);
4917 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4918 DL.getDebugLoc(), VTList, Ops[0]);
4919 } else if (NumOps == 2) {
4920 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4921 DL.getDebugLoc(), VTList, Ops[0],
4923 } else if (NumOps == 3) {
4924 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4925 DL.getDebugLoc(), VTList, Ops[0],
4928 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4929 VTList, Ops, NumOps);
4931 CSEMap.InsertNode(N, IP);
4934 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4935 DL.getDebugLoc(), VTList, Ops[0]);
4936 } else if (NumOps == 2) {
4937 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4938 DL.getDebugLoc(), VTList, Ops[0],
4940 } else if (NumOps == 3) {
4941 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4942 DL.getDebugLoc(), VTList, Ops[0],
4945 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4946 VTList, Ops, NumOps);
4949 AllNodes.push_back(N);
4953 return SDValue(N, 0);
4956 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4957 return getNode(Opcode, DL, VTList, 0, 0);
4960 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4962 SDValue Ops[] = { N1 };
4963 return getNode(Opcode, DL, VTList, Ops, 1);
4966 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4967 SDValue N1, SDValue N2) {
4968 SDValue Ops[] = { N1, N2 };
4969 return getNode(Opcode, DL, VTList, Ops, 2);
4972 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4973 SDValue N1, SDValue N2, SDValue N3) {
4974 SDValue Ops[] = { N1, N2, N3 };
4975 return getNode(Opcode, DL, VTList, Ops, 3);
4978 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4979 SDValue N1, SDValue N2, SDValue N3,
4981 SDValue Ops[] = { N1, N2, N3, N4 };
4982 return getNode(Opcode, DL, VTList, Ops, 4);
4985 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4986 SDValue N1, SDValue N2, SDValue N3,
4987 SDValue N4, SDValue N5) {
4988 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4989 return getNode(Opcode, DL, VTList, Ops, 5);
4992 SDVTList SelectionDAG::getVTList(EVT VT) {
4993 return makeVTList(SDNode::getValueTypeList(VT), 1);
4996 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4997 FoldingSetNodeID ID;
4999 ID.AddInteger(VT1.getRawBits());
5000 ID.AddInteger(VT2.getRawBits());
5003 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5004 if (Result == NULL) {
5005 EVT *Array = Allocator.Allocate<EVT>(2);
5008 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5009 VTListMap.InsertNode(Result, IP);
5011 return Result->getSDVTList();
5014 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5015 FoldingSetNodeID ID;
5017 ID.AddInteger(VT1.getRawBits());
5018 ID.AddInteger(VT2.getRawBits());
5019 ID.AddInteger(VT3.getRawBits());
5022 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5023 if (Result == NULL) {
5024 EVT *Array = Allocator.Allocate<EVT>(3);
5028 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5029 VTListMap.InsertNode(Result, IP);
5031 return Result->getSDVTList();
5034 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5035 FoldingSetNodeID ID;
5037 ID.AddInteger(VT1.getRawBits());
5038 ID.AddInteger(VT2.getRawBits());
5039 ID.AddInteger(VT3.getRawBits());
5040 ID.AddInteger(VT4.getRawBits());
5043 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5044 if (Result == NULL) {
5045 EVT *Array = Allocator.Allocate<EVT>(4);
5050 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5051 VTListMap.InsertNode(Result, IP);
5053 return Result->getSDVTList();
5056 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5057 FoldingSetNodeID ID;
5058 ID.AddInteger(NumVTs);
5059 for (unsigned index = 0; index < NumVTs; index++) {
5060 ID.AddInteger(VTs[index].getRawBits());
5064 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5065 if (Result == NULL) {
5066 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5067 std::copy(VTs, VTs + NumVTs, Array);
5068 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5069 VTListMap.InsertNode(Result, IP);
5071 return Result->getSDVTList();
5075 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5076 /// specified operands. If the resultant node already exists in the DAG,
5077 /// this does not modify the specified node, instead it returns the node that
5078 /// already exists. If the resultant node does not exist in the DAG, the
5079 /// input node is returned. As a degenerate case, if you specify the same
5080 /// input operands as the node already has, the input node is returned.
5081 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5082 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5084 // Check to see if there is no change.
5085 if (Op == N->getOperand(0)) return N;
5087 // See if the modified node already exists.
5088 void *InsertPos = 0;
5089 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5092 // Nope it doesn't. Remove the node from its current place in the maps.
5094 if (!RemoveNodeFromCSEMaps(N))
5097 // Now we update the operands.
5098 N->OperandList[0].set(Op);
5100 // If this gets put into a CSE map, add it.
5101 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5105 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5106 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5108 // Check to see if there is no change.
5109 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5110 return N; // No operands changed, just return the input node.
5112 // See if the modified node already exists.
5113 void *InsertPos = 0;
5114 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5117 // Nope it doesn't. Remove the node from its current place in the maps.
5119 if (!RemoveNodeFromCSEMaps(N))
5122 // Now we update the operands.
5123 if (N->OperandList[0] != Op1)
5124 N->OperandList[0].set(Op1);
5125 if (N->OperandList[1] != Op2)
5126 N->OperandList[1].set(Op2);
5128 // If this gets put into a CSE map, add it.
5129 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5133 SDNode *SelectionDAG::
5134 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5135 SDValue Ops[] = { Op1, Op2, Op3 };
5136 return UpdateNodeOperands(N, Ops, 3);
5139 SDNode *SelectionDAG::
5140 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5141 SDValue Op3, SDValue Op4) {
5142 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5143 return UpdateNodeOperands(N, Ops, 4);
5146 SDNode *SelectionDAG::
5147 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5148 SDValue Op3, SDValue Op4, SDValue Op5) {
5149 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5150 return UpdateNodeOperands(N, Ops, 5);
5153 SDNode *SelectionDAG::
5154 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5155 assert(N->getNumOperands() == NumOps &&
5156 "Update with wrong number of operands");
5158 // Check to see if there is no change.
5159 bool AnyChange = false;
5160 for (unsigned i = 0; i != NumOps; ++i) {
5161 if (Ops[i] != N->getOperand(i)) {
5167 // No operands changed, just return the input node.
5168 if (!AnyChange) return N;
5170 // See if the modified node already exists.
5171 void *InsertPos = 0;
5172 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5175 // Nope it doesn't. Remove the node from its current place in the maps.
5177 if (!RemoveNodeFromCSEMaps(N))
5180 // Now we update the operands.
5181 for (unsigned i = 0; i != NumOps; ++i)
5182 if (N->OperandList[i] != Ops[i])
5183 N->OperandList[i].set(Ops[i]);
5185 // If this gets put into a CSE map, add it.
5186 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5190 /// DropOperands - Release the operands and set this node to have
5192 void SDNode::DropOperands() {
5193 // Unlike the code in MorphNodeTo that does this, we don't need to
5194 // watch for dead nodes here.
5195 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5201 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5204 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5206 SDVTList VTs = getVTList(VT);
5207 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5210 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5211 EVT VT, SDValue Op1) {
5212 SDVTList VTs = getVTList(VT);
5213 SDValue Ops[] = { Op1 };
5214 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5217 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5218 EVT VT, SDValue Op1,
5220 SDVTList VTs = getVTList(VT);
5221 SDValue Ops[] = { Op1, Op2 };
5222 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5225 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5226 EVT VT, SDValue Op1,
5227 SDValue Op2, SDValue Op3) {
5228 SDVTList VTs = getVTList(VT);
5229 SDValue Ops[] = { Op1, Op2, Op3 };
5230 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5233 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5234 EVT VT, const SDValue *Ops,
5236 SDVTList VTs = getVTList(VT);
5237 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5240 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5241 EVT VT1, EVT VT2, const SDValue *Ops,
5243 SDVTList VTs = getVTList(VT1, VT2);
5244 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5247 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5249 SDVTList VTs = getVTList(VT1, VT2);
5250 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5253 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5254 EVT VT1, EVT VT2, EVT VT3,
5255 const SDValue *Ops, unsigned NumOps) {
5256 SDVTList VTs = getVTList(VT1, VT2, VT3);
5257 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5260 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5261 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5262 const SDValue *Ops, unsigned NumOps) {
5263 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5264 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5267 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 SDVTList VTs = getVTList(VT1, VT2);
5271 SDValue Ops[] = { Op1 };
5272 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5275 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5277 SDValue Op1, SDValue Op2) {
5278 SDVTList VTs = getVTList(VT1, VT2);
5279 SDValue Ops[] = { Op1, Op2 };
5280 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5285 SDValue Op1, SDValue Op2,
5287 SDVTList VTs = getVTList(VT1, VT2);
5288 SDValue Ops[] = { Op1, Op2, Op3 };
5289 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 EVT VT1, EVT VT2, EVT VT3,
5294 SDValue Op1, SDValue Op2,
5296 SDVTList VTs = getVTList(VT1, VT2, VT3);
5297 SDValue Ops[] = { Op1, Op2, Op3 };
5298 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5301 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 SDVTList VTs, const SDValue *Ops,
5304 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5305 // Reset the NodeID to -1.
5310 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5311 /// the line number information on the merged node since it is not possible to
5312 /// preserve the information that operation is associated with multiple lines.
5313 /// This will make the debugger working better at -O0, were there is a higher
5314 /// probability having other instructions associated with that line.
5316 /// For IROrder, we keep the smaller of the two
5317 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5318 DebugLoc NLoc = N->getDebugLoc();
5319 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5320 (OLoc.getDebugLoc() != NLoc)) {
5321 N->setDebugLoc(DebugLoc());
5323 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5324 N->setIROrder(Order);
5328 /// MorphNodeTo - This *mutates* the specified node to have the specified
5329 /// return type, opcode, and operands.
5331 /// Note that MorphNodeTo returns the resultant node. If there is already a
5332 /// node of the specified opcode and operands, it returns that node instead of
5333 /// the current one. Note that the SDLoc need not be the same.
5335 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5336 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5337 /// node, and because it doesn't require CSE recalculation for any of
5338 /// the node's users.
5340 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5341 SDVTList VTs, const SDValue *Ops,
5343 // If an identical node already exists, use it.
5345 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5346 FoldingSetNodeID ID;
5347 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5348 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5349 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5352 if (!RemoveNodeFromCSEMaps(N))
5355 // Start the morphing.
5357 N->ValueList = VTs.VTs;
5358 N->NumValues = VTs.NumVTs;
5360 // Clear the operands list, updating used nodes to remove this from their
5361 // use list. Keep track of any operands that become dead as a result.
5362 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5363 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5365 SDNode *Used = Use.getNode();
5367 if (Used->use_empty())
5368 DeadNodeSet.insert(Used);
5371 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5372 // Initialize the memory references information.
5373 MN->setMemRefs(0, 0);
5374 // If NumOps is larger than the # of operands we can have in a
5375 // MachineSDNode, reallocate the operand list.
5376 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5377 if (MN->OperandsNeedDelete)
5378 delete[] MN->OperandList;
5379 if (NumOps > array_lengthof(MN->LocalOperands))
5380 // We're creating a final node that will live unmorphed for the
5381 // remainder of the current SelectionDAG iteration, so we can allocate
5382 // the operands directly out of a pool with no recycling metadata.
5383 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5386 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5387 MN->OperandsNeedDelete = false;
5389 MN->InitOperands(MN->OperandList, Ops, NumOps);
5391 // If NumOps is larger than the # of operands we currently have, reallocate
5392 // the operand list.
5393 if (NumOps > N->NumOperands) {
5394 if (N->OperandsNeedDelete)
5395 delete[] N->OperandList;
5396 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5397 N->OperandsNeedDelete = true;
5399 N->InitOperands(N->OperandList, Ops, NumOps);
5402 // Delete any nodes that are still dead after adding the uses for the
5404 if (!DeadNodeSet.empty()) {
5405 SmallVector<SDNode *, 16> DeadNodes;
5406 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5407 E = DeadNodeSet.end(); I != E; ++I)
5408 if ((*I)->use_empty())
5409 DeadNodes.push_back(*I);
5410 RemoveDeadNodes(DeadNodes);
5414 CSEMap.InsertNode(N, IP); // Memoize the new node.
5419 /// getMachineNode - These are used for target selectors to create a new node
5420 /// with specified return type(s), MachineInstr opcode, and operands.
5422 /// Note that getMachineNode returns the resultant node. If there is already a
5423 /// node of the specified opcode and operands, it returns that node instead of
5424 /// the current one.
5426 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5427 SDVTList VTs = getVTList(VT);
5428 return getMachineNode(Opcode, dl, VTs, None);
5432 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5433 SDVTList VTs = getVTList(VT);
5434 SDValue Ops[] = { Op1 };
5435 return getMachineNode(Opcode, dl, VTs, Ops);
5439 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5440 SDValue Op1, SDValue Op2) {
5441 SDVTList VTs = getVTList(VT);
5442 SDValue Ops[] = { Op1, Op2 };
5443 return getMachineNode(Opcode, dl, VTs, Ops);
5447 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5448 SDValue Op1, SDValue Op2, SDValue Op3) {
5449 SDVTList VTs = getVTList(VT);
5450 SDValue Ops[] = { Op1, Op2, Op3 };
5451 return getMachineNode(Opcode, dl, VTs, Ops);
5455 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5456 ArrayRef<SDValue> Ops) {
5457 SDVTList VTs = getVTList(VT);
5458 return getMachineNode(Opcode, dl, VTs, Ops);
5462 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5463 SDVTList VTs = getVTList(VT1, VT2);
5464 return getMachineNode(Opcode, dl, VTs, None);
5468 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5469 EVT VT1, EVT VT2, SDValue Op1) {
5470 SDVTList VTs = getVTList(VT1, VT2);
5471 SDValue Ops[] = { Op1 };
5472 return getMachineNode(Opcode, dl, VTs, Ops);
5476 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5477 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5478 SDVTList VTs = getVTList(VT1, VT2);
5479 SDValue Ops[] = { Op1, Op2 };
5480 return getMachineNode(Opcode, dl, VTs, Ops);
5484 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5485 EVT VT1, EVT VT2, SDValue Op1,
5486 SDValue Op2, SDValue Op3) {
5487 SDVTList VTs = getVTList(VT1, VT2);
5488 SDValue Ops[] = { Op1, Op2, Op3 };
5489 return getMachineNode(Opcode, dl, VTs, Ops);
5493 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5495 ArrayRef<SDValue> Ops) {
5496 SDVTList VTs = getVTList(VT1, VT2);
5497 return getMachineNode(Opcode, dl, VTs, Ops);
5501 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5502 EVT VT1, EVT VT2, EVT VT3,
5503 SDValue Op1, SDValue Op2) {
5504 SDVTList VTs = getVTList(VT1, VT2, VT3);
5505 SDValue Ops[] = { Op1, Op2 };
5506 return getMachineNode(Opcode, dl, VTs, Ops);
5510 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5511 EVT VT1, EVT VT2, EVT VT3,
5512 SDValue Op1, SDValue Op2, SDValue Op3) {
5513 SDVTList VTs = getVTList(VT1, VT2, VT3);
5514 SDValue Ops[] = { Op1, Op2, Op3 };
5515 return getMachineNode(Opcode, dl, VTs, Ops);
5519 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5520 EVT VT1, EVT VT2, EVT VT3,
5521 ArrayRef<SDValue> Ops) {
5522 SDVTList VTs = getVTList(VT1, VT2, VT3);
5523 return getMachineNode(Opcode, dl, VTs, Ops);
5527 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5528 EVT VT2, EVT VT3, EVT VT4,
5529 ArrayRef<SDValue> Ops) {
5530 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5531 return getMachineNode(Opcode, dl, VTs, Ops);
5535 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5536 ArrayRef<EVT> ResultTys,
5537 ArrayRef<SDValue> Ops) {
5538 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5539 return getMachineNode(Opcode, dl, VTs, Ops);
5543 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5544 ArrayRef<SDValue> OpsArray) {
5545 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5548 const SDValue *Ops = OpsArray.data();
5549 unsigned NumOps = OpsArray.size();
5552 FoldingSetNodeID ID;
5553 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5555 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5556 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5560 // Allocate a new MachineSDNode.
5561 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5562 DL.getDebugLoc(), VTs);
5564 // Initialize the operands list.
5565 if (NumOps > array_lengthof(N->LocalOperands))
5566 // We're creating a final node that will live unmorphed for the
5567 // remainder of the current SelectionDAG iteration, so we can allocate
5568 // the operands directly out of a pool with no recycling metadata.
5569 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5572 N->InitOperands(N->LocalOperands, Ops, NumOps);
5573 N->OperandsNeedDelete = false;
5576 CSEMap.InsertNode(N, IP);
5578 AllNodes.push_back(N);
5580 VerifyMachineNode(N);
5585 /// getTargetExtractSubreg - A convenience function for creating
5586 /// TargetOpcode::EXTRACT_SUBREG nodes.
5588 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5590 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5591 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5592 VT, Operand, SRIdxVal);
5593 return SDValue(Subreg, 0);
5596 /// getTargetInsertSubreg - A convenience function for creating
5597 /// TargetOpcode::INSERT_SUBREG nodes.
5599 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5600 SDValue Operand, SDValue Subreg) {
5601 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5602 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5603 VT, Operand, Subreg, SRIdxVal);
5604 return SDValue(Result, 0);
5607 /// getNodeIfExists - Get the specified node if it's already available, or
5608 /// else return NULL.
5609 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5610 const SDValue *Ops, unsigned NumOps) {
5611 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5612 FoldingSetNodeID ID;
5613 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5621 /// getDbgValue - Creates a SDDbgValue node.
5624 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5625 DebugLoc DL, unsigned O) {
5626 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5630 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5631 DebugLoc DL, unsigned O) {
5632 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5636 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5637 DebugLoc DL, unsigned O) {
5638 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5643 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5644 /// pointed to by a use iterator is deleted, increment the use iterator
5645 /// so that it doesn't dangle.
5647 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5648 SDNode::use_iterator &UI;
5649 SDNode::use_iterator &UE;
5651 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5652 // Increment the iterator as needed.
5653 while (UI != UE && N == *UI)
5658 RAUWUpdateListener(SelectionDAG &d,
5659 SDNode::use_iterator &ui,
5660 SDNode::use_iterator &ue)
5661 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5666 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5667 /// This can cause recursive merging of nodes in the DAG.
5669 /// This version assumes From has a single result value.
5671 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5672 SDNode *From = FromN.getNode();
5673 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5674 "Cannot replace with this method!");
5675 assert(From != To.getNode() && "Cannot replace uses of with self");
5677 // Iterate over all the existing uses of From. New uses will be added
5678 // to the beginning of the use list, which we avoid visiting.
5679 // This specifically avoids visiting uses of From that arise while the
5680 // replacement is happening, because any such uses would be the result
5681 // of CSE: If an existing node looks like From after one of its operands
5682 // is replaced by To, we don't want to replace of all its users with To
5683 // too. See PR3018 for more info.
5684 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5685 RAUWUpdateListener Listener(*this, UI, UE);
5689 // This node is about to morph, remove its old self from the CSE maps.
5690 RemoveNodeFromCSEMaps(User);
5692 // A user can appear in a use list multiple times, and when this
5693 // happens the uses are usually next to each other in the list.
5694 // To help reduce the number of CSE recomputations, process all
5695 // the uses of this user that we can find this way.
5697 SDUse &Use = UI.getUse();
5700 } while (UI != UE && *UI == User);
5702 // Now that we have modified User, add it back to the CSE maps. If it
5703 // already exists there, recursively merge the results together.
5704 AddModifiedNodeToCSEMaps(User);
5707 // If we just RAUW'd the root, take note.
5708 if (FromN == getRoot())
5712 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5713 /// This can cause recursive merging of nodes in the DAG.
5715 /// This version assumes that for each value of From, there is a
5716 /// corresponding value in To in the same position with the same type.
5718 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5720 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5721 assert((!From->hasAnyUseOfValue(i) ||
5722 From->getValueType(i) == To->getValueType(i)) &&
5723 "Cannot use this version of ReplaceAllUsesWith!");
5726 // Handle the trivial case.
5730 // Iterate over just the existing users of From. See the comments in
5731 // the ReplaceAllUsesWith above.
5732 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5733 RAUWUpdateListener Listener(*this, UI, UE);
5737 // This node is about to morph, remove its old self from the CSE maps.
5738 RemoveNodeFromCSEMaps(User);
5740 // A user can appear in a use list multiple times, and when this
5741 // happens the uses are usually next to each other in the list.
5742 // To help reduce the number of CSE recomputations, process all
5743 // the uses of this user that we can find this way.
5745 SDUse &Use = UI.getUse();
5748 } while (UI != UE && *UI == User);
5750 // Now that we have modified User, add it back to the CSE maps. If it
5751 // already exists there, recursively merge the results together.
5752 AddModifiedNodeToCSEMaps(User);
5755 // If we just RAUW'd the root, take note.
5756 if (From == getRoot().getNode())
5757 setRoot(SDValue(To, getRoot().getResNo()));
5760 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5761 /// This can cause recursive merging of nodes in the DAG.
5763 /// This version can replace From with any result values. To must match the
5764 /// number and types of values returned by From.
5765 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5766 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5767 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5769 // Iterate over just the existing users of From. See the comments in
5770 // the ReplaceAllUsesWith above.
5771 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5772 RAUWUpdateListener Listener(*this, UI, UE);
5776 // This node is about to morph, remove its old self from the CSE maps.
5777 RemoveNodeFromCSEMaps(User);
5779 // A user can appear in a use list multiple times, and when this
5780 // happens the uses are usually next to each other in the list.
5781 // To help reduce the number of CSE recomputations, process all
5782 // the uses of this user that we can find this way.
5784 SDUse &Use = UI.getUse();
5785 const SDValue &ToOp = To[Use.getResNo()];
5788 } while (UI != UE && *UI == User);
5790 // Now that we have modified User, add it back to the CSE maps. If it
5791 // already exists there, recursively merge the results together.
5792 AddModifiedNodeToCSEMaps(User);
5795 // If we just RAUW'd the root, take note.
5796 if (From == getRoot().getNode())
5797 setRoot(SDValue(To[getRoot().getResNo()]));
5800 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5801 /// uses of other values produced by From.getNode() alone. The Deleted
5802 /// vector is handled the same way as for ReplaceAllUsesWith.
5803 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5804 // Handle the really simple, really trivial case efficiently.
5805 if (From == To) return;
5807 // Handle the simple, trivial, case efficiently.
5808 if (From.getNode()->getNumValues() == 1) {
5809 ReplaceAllUsesWith(From, To);
5813 // Iterate over just the existing users of From. See the comments in
5814 // the ReplaceAllUsesWith above.
5815 SDNode::use_iterator UI = From.getNode()->use_begin(),
5816 UE = From.getNode()->use_end();
5817 RAUWUpdateListener Listener(*this, UI, UE);
5820 bool UserRemovedFromCSEMaps = false;
5822 // A user can appear in a use list multiple times, and when this
5823 // happens the uses are usually next to each other in the list.
5824 // To help reduce the number of CSE recomputations, process all
5825 // the uses of this user that we can find this way.
5827 SDUse &Use = UI.getUse();
5829 // Skip uses of different values from the same node.
5830 if (Use.getResNo() != From.getResNo()) {
5835 // If this node hasn't been modified yet, it's still in the CSE maps,
5836 // so remove its old self from the CSE maps.
5837 if (!UserRemovedFromCSEMaps) {
5838 RemoveNodeFromCSEMaps(User);
5839 UserRemovedFromCSEMaps = true;
5844 } while (UI != UE && *UI == User);
5846 // We are iterating over all uses of the From node, so if a use
5847 // doesn't use the specific value, no changes are made.
5848 if (!UserRemovedFromCSEMaps)
5851 // Now that we have modified User, add it back to the CSE maps. If it
5852 // already exists there, recursively merge the results together.
5853 AddModifiedNodeToCSEMaps(User);
5856 // If we just RAUW'd the root, take note.
5857 if (From == getRoot())
5862 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5863 /// to record information about a use.
5870 /// operator< - Sort Memos by User.
5871 bool operator<(const UseMemo &L, const UseMemo &R) {
5872 return (intptr_t)L.User < (intptr_t)R.User;
5876 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5877 /// uses of other values produced by From.getNode() alone. The same value
5878 /// may appear in both the From and To list. The Deleted vector is
5879 /// handled the same way as for ReplaceAllUsesWith.
5880 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5883 // Handle the simple, trivial case efficiently.
5885 return ReplaceAllUsesOfValueWith(*From, *To);
5887 // Read up all the uses and make records of them. This helps
5888 // processing new uses that are introduced during the
5889 // replacement process.
5890 SmallVector<UseMemo, 4> Uses;
5891 for (unsigned i = 0; i != Num; ++i) {
5892 unsigned FromResNo = From[i].getResNo();
5893 SDNode *FromNode = From[i].getNode();
5894 for (SDNode::use_iterator UI = FromNode->use_begin(),
5895 E = FromNode->use_end(); UI != E; ++UI) {
5896 SDUse &Use = UI.getUse();
5897 if (Use.getResNo() == FromResNo) {
5898 UseMemo Memo = { *UI, i, &Use };
5899 Uses.push_back(Memo);
5904 // Sort the uses, so that all the uses from a given User are together.
5905 std::sort(Uses.begin(), Uses.end());
5907 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5908 UseIndex != UseIndexEnd; ) {
5909 // We know that this user uses some value of From. If it is the right
5910 // value, update it.
5911 SDNode *User = Uses[UseIndex].User;
5913 // This node is about to morph, remove its old self from the CSE maps.
5914 RemoveNodeFromCSEMaps(User);
5916 // The Uses array is sorted, so all the uses for a given User
5917 // are next to each other in the list.
5918 // To help reduce the number of CSE recomputations, process all
5919 // the uses of this user that we can find this way.
5921 unsigned i = Uses[UseIndex].Index;
5922 SDUse &Use = *Uses[UseIndex].Use;
5926 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5928 // Now that we have modified User, add it back to the CSE maps. If it
5929 // already exists there, recursively merge the results together.
5930 AddModifiedNodeToCSEMaps(User);
5934 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5935 /// based on their topological order. It returns the maximum id and a vector
5936 /// of the SDNodes* in assigned order by reference.
5937 unsigned SelectionDAG::AssignTopologicalOrder() {
5939 unsigned DAGSize = 0;
5941 // SortedPos tracks the progress of the algorithm. Nodes before it are
5942 // sorted, nodes after it are unsorted. When the algorithm completes
5943 // it is at the end of the list.
5944 allnodes_iterator SortedPos = allnodes_begin();
5946 // Visit all the nodes. Move nodes with no operands to the front of
5947 // the list immediately. Annotate nodes that do have operands with their
5948 // operand count. Before we do this, the Node Id fields of the nodes
5949 // may contain arbitrary values. After, the Node Id fields for nodes
5950 // before SortedPos will contain the topological sort index, and the
5951 // Node Id fields for nodes At SortedPos and after will contain the
5952 // count of outstanding operands.
5953 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5956 unsigned Degree = N->getNumOperands();
5958 // A node with no uses, add it to the result array immediately.
5959 N->setNodeId(DAGSize++);
5960 allnodes_iterator Q = N;
5962 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5963 assert(SortedPos != AllNodes.end() && "Overran node list");
5966 // Temporarily use the Node Id as scratch space for the degree count.
5967 N->setNodeId(Degree);
5971 // Visit all the nodes. As we iterate, move nodes into sorted order,
5972 // such that by the time the end is reached all nodes will be sorted.
5973 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5976 // N is in sorted position, so all its uses have one less operand
5977 // that needs to be sorted.
5978 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5981 unsigned Degree = P->getNodeId();
5982 assert(Degree != 0 && "Invalid node degree");
5985 // All of P's operands are sorted, so P may sorted now.
5986 P->setNodeId(DAGSize++);
5988 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5989 assert(SortedPos != AllNodes.end() && "Overran node list");
5992 // Update P's outstanding operand count.
5993 P->setNodeId(Degree);
5996 if (I == SortedPos) {
5999 dbgs() << "Overran sorted position:\n";
6002 llvm_unreachable(0);
6006 assert(SortedPos == AllNodes.end() &&
6007 "Topological sort incomplete!");
6008 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6009 "First node in topological sort is not the entry token!");
6010 assert(AllNodes.front().getNodeId() == 0 &&
6011 "First node in topological sort has non-zero id!");
6012 assert(AllNodes.front().getNumOperands() == 0 &&
6013 "First node in topological sort has operands!");
6014 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6015 "Last node in topologic sort has unexpected id!");
6016 assert(AllNodes.back().use_empty() &&
6017 "Last node in topologic sort has users!");
6018 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6022 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6023 /// value is produced by SD.
6024 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6025 DbgInfo->add(DB, SD, isParameter);
6027 SD->setHasDebugValue(true);
6030 /// TransferDbgValues - Transfer SDDbgValues.
6031 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6032 if (From == To || !From.getNode()->getHasDebugValue())
6034 SDNode *FromNode = From.getNode();
6035 SDNode *ToNode = To.getNode();
6036 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6037 SmallVector<SDDbgValue *, 2> ClonedDVs;
6038 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6040 SDDbgValue *Dbg = *I;
6041 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6042 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6043 Dbg->getOffset(), Dbg->getDebugLoc(),
6045 ClonedDVs.push_back(Clone);
6048 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6049 E = ClonedDVs.end(); I != E; ++I)
6050 AddDbgValue(*I, ToNode, false);
6053 //===----------------------------------------------------------------------===//
6055 //===----------------------------------------------------------------------===//
6057 HandleSDNode::~HandleSDNode() {
6061 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6062 DebugLoc DL, const GlobalValue *GA,
6063 EVT VT, int64_t o, unsigned char TF)
6064 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6068 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6069 SDValue X, unsigned SrcAS,
6071 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6072 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6074 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6075 EVT memvt, MachineMemOperand *mmo)
6076 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6077 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6078 MMO->isNonTemporal(), MMO->isInvariant());
6079 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6080 assert(isNonTemporal() == MMO->isNonTemporal() &&
6081 "Non-temporal encoding error!");
6082 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6085 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6086 const SDValue *Ops, unsigned NumOps, EVT memvt,
6087 MachineMemOperand *mmo)
6088 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6089 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(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6096 /// Profile - Gather unique data for the node.
6098 void SDNode::Profile(FoldingSetNodeID &ID) const {
6099 AddNodeIDNode(ID, this);
6104 std::vector<EVT> VTs;
6107 VTs.reserve(MVT::LAST_VALUETYPE);
6108 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6109 VTs.push_back(MVT((MVT::SimpleValueType)i));
6114 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6115 static ManagedStatic<EVTArray> SimpleVTArray;
6116 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6118 /// getValueTypeList - Return a pointer to the specified value type.
6120 const EVT *SDNode::getValueTypeList(EVT VT) {
6121 if (VT.isExtended()) {
6122 sys::SmartScopedLock<true> Lock(*VTMutex);
6123 return &(*EVTs->insert(VT).first);
6125 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6126 "Value type out of range!");
6127 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6131 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6132 /// indicated value. This method ignores uses of other values defined by this
6134 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6135 assert(Value < getNumValues() && "Bad value!");
6137 // TODO: Only iterate over uses of a given value of the node
6138 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6139 if (UI.getUse().getResNo() == Value) {
6146 // Found exactly the right number of uses?
6151 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6152 /// value. This method ignores uses of other values defined by this operation.
6153 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6154 assert(Value < getNumValues() && "Bad value!");
6156 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6157 if (UI.getUse().getResNo() == Value)
6164 /// isOnlyUserOf - Return true if this node is the only use of N.
6166 bool SDNode::isOnlyUserOf(SDNode *N) const {
6168 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6179 /// isOperand - Return true if this node is an operand of N.
6181 bool SDValue::isOperandOf(SDNode *N) const {
6182 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6183 if (*this == N->getOperand(i))
6188 bool SDNode::isOperandOf(SDNode *N) const {
6189 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6190 if (this == N->OperandList[i].getNode())
6195 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6196 /// be a chain) reaches the specified operand without crossing any
6197 /// side-effecting instructions on any chain path. In practice, this looks
6198 /// through token factors and non-volatile loads. In order to remain efficient,
6199 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6200 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6201 unsigned Depth) const {
6202 if (*this == Dest) return true;
6204 // Don't search too deeply, we just want to be able to see through
6205 // TokenFactor's etc.
6206 if (Depth == 0) return false;
6208 // If this is a token factor, all inputs to the TF happen in parallel. If any
6209 // of the operands of the TF does not reach dest, then we cannot do the xform.
6210 if (getOpcode() == ISD::TokenFactor) {
6211 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6212 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6217 // Loads don't have side effects, look through them.
6218 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6219 if (!Ld->isVolatile())
6220 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6225 /// hasPredecessor - Return true if N is a predecessor of this node.
6226 /// N is either an operand of this node, or can be reached by recursively
6227 /// traversing up the operands.
6228 /// NOTE: This is an expensive method. Use it carefully.
6229 bool SDNode::hasPredecessor(const SDNode *N) const {
6230 SmallPtrSet<const SDNode *, 32> Visited;
6231 SmallVector<const SDNode *, 16> Worklist;
6232 return hasPredecessorHelper(N, Visited, Worklist);
6236 SDNode::hasPredecessorHelper(const SDNode *N,
6237 SmallPtrSet<const SDNode *, 32> &Visited,
6238 SmallVectorImpl<const SDNode *> &Worklist) const {
6239 if (Visited.empty()) {
6240 Worklist.push_back(this);
6242 // Take a look in the visited set. If we've already encountered this node
6243 // we needn't search further.
6244 if (Visited.count(N))
6248 // Haven't visited N yet. Continue the search.
6249 while (!Worklist.empty()) {
6250 const SDNode *M = Worklist.pop_back_val();
6251 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6252 SDNode *Op = M->getOperand(i).getNode();
6253 if (Visited.insert(Op))
6254 Worklist.push_back(Op);
6263 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6264 assert(Num < NumOperands && "Invalid child # of SDNode!");
6265 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6268 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6269 assert(N->getNumValues() == 1 &&
6270 "Can't unroll a vector with multiple results!");
6272 EVT VT = N->getValueType(0);
6273 unsigned NE = VT.getVectorNumElements();
6274 EVT EltVT = VT.getVectorElementType();
6277 SmallVector<SDValue, 8> Scalars;
6278 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6280 // If ResNE is 0, fully unroll the vector op.
6283 else if (NE > ResNE)
6287 for (i= 0; i != NE; ++i) {
6288 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6289 SDValue Operand = N->getOperand(j);
6290 EVT OperandVT = Operand.getValueType();
6291 if (OperandVT.isVector()) {
6292 // A vector operand; extract a single element.
6293 const TargetLowering *TLI = TM.getTargetLowering();
6294 EVT OperandEltVT = OperandVT.getVectorElementType();
6295 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6298 getConstant(i, TLI->getVectorIdxTy()));
6300 // A scalar operand; just use it as is.
6301 Operands[j] = Operand;
6305 switch (N->getOpcode()) {
6307 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6308 &Operands[0], Operands.size()));
6311 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6312 &Operands[0], Operands.size()));
6319 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6320 getShiftAmountOperand(Operands[0].getValueType(),
6323 case ISD::SIGN_EXTEND_INREG:
6324 case ISD::FP_ROUND_INREG: {
6325 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6326 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6328 getValueType(ExtVT)));
6333 for (; i < ResNE; ++i)
6334 Scalars.push_back(getUNDEF(EltVT));
6336 return getNode(ISD::BUILD_VECTOR, dl,
6337 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6338 &Scalars[0], Scalars.size());
6342 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6343 /// location that is 'Dist' units away from the location that the 'Base' load
6344 /// is loading from.
6345 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6346 unsigned Bytes, int Dist) const {
6347 if (LD->getChain() != Base->getChain())
6349 EVT VT = LD->getValueType(0);
6350 if (VT.getSizeInBits() / 8 != Bytes)
6353 SDValue Loc = LD->getOperand(1);
6354 SDValue BaseLoc = Base->getOperand(1);
6355 if (Loc.getOpcode() == ISD::FrameIndex) {
6356 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6358 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6359 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6360 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6361 int FS = MFI->getObjectSize(FI);
6362 int BFS = MFI->getObjectSize(BFI);
6363 if (FS != BFS || FS != (int)Bytes) return false;
6364 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6368 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6369 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6372 const GlobalValue *GV1 = NULL;
6373 const GlobalValue *GV2 = NULL;
6374 int64_t Offset1 = 0;
6375 int64_t Offset2 = 0;
6376 const TargetLowering *TLI = TM.getTargetLowering();
6377 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6378 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6379 if (isGA1 && isGA2 && GV1 == GV2)
6380 return Offset1 == (Offset2 + Dist*Bytes);
6385 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6386 /// it cannot be inferred.
6387 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6388 // If this is a GlobalAddress + cst, return the alignment.
6389 const GlobalValue *GV;
6390 int64_t GVOffset = 0;
6391 const TargetLowering *TLI = TM.getTargetLowering();
6392 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6393 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6394 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6395 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6396 TLI->getDataLayout());
6397 unsigned AlignBits = KnownZero.countTrailingOnes();
6398 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6400 return MinAlign(Align, GVOffset);
6403 // If this is a direct reference to a stack slot, use information about the
6404 // stack slot's alignment.
6405 int FrameIdx = 1 << 31;
6406 int64_t FrameOffset = 0;
6407 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6408 FrameIdx = FI->getIndex();
6409 } else if (isBaseWithConstantOffset(Ptr) &&
6410 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6412 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6413 FrameOffset = Ptr.getConstantOperandVal(1);
6416 if (FrameIdx != (1 << 31)) {
6417 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6418 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6426 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6427 /// which is split (or expanded) into two not necessarily identical pieces.
6428 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6429 // Currently all types are split in half.
6431 if (!VT.isVector()) {
6432 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6434 unsigned NumElements = VT.getVectorNumElements();
6435 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6436 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6439 return std::make_pair(LoVT, HiVT);
6442 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6444 std::pair<SDValue, SDValue>
6445 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6447 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6448 N.getValueType().getVectorNumElements() &&
6449 "More vector elements requested than available!");
6451 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6452 getConstant(0, TLI->getVectorIdxTy()));
6453 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6454 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6455 return std::make_pair(Lo, Hi);
6458 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6459 unsigned GlobalAddressSDNode::getAddressSpace() const {
6460 return getGlobal()->getType()->getAddressSpace();
6464 Type *ConstantPoolSDNode::getType() const {
6465 if (isMachineConstantPoolEntry())
6466 return Val.MachineCPVal->getType();
6467 return Val.ConstVal->getType();
6470 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6472 unsigned &SplatBitSize,
6474 unsigned MinSplatBits,
6476 EVT VT = getValueType(0);
6477 assert(VT.isVector() && "Expected a vector type");
6478 unsigned sz = VT.getSizeInBits();
6479 if (MinSplatBits > sz)
6482 SplatValue = APInt(sz, 0);
6483 SplatUndef = APInt(sz, 0);
6485 // Get the bits. Bits with undefined values (when the corresponding element
6486 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6487 // in SplatValue. If any of the values are not constant, give up and return
6489 unsigned int nOps = getNumOperands();
6490 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6491 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6493 for (unsigned j = 0; j < nOps; ++j) {
6494 unsigned i = isBigEndian ? nOps-1-j : j;
6495 SDValue OpVal = getOperand(i);
6496 unsigned BitPos = j * EltBitSize;
6498 if (OpVal.getOpcode() == ISD::UNDEF)
6499 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6500 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6501 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6502 zextOrTrunc(sz) << BitPos;
6503 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6504 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6509 // The build_vector is all constants or undefs. Find the smallest element
6510 // size that splats the vector.
6512 HasAnyUndefs = (SplatUndef != 0);
6515 unsigned HalfSize = sz / 2;
6516 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6517 APInt LowValue = SplatValue.trunc(HalfSize);
6518 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6519 APInt LowUndef = SplatUndef.trunc(HalfSize);
6521 // If the two halves do not match (ignoring undef bits), stop here.
6522 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6523 MinSplatBits > HalfSize)
6526 SplatValue = HighValue | LowValue;
6527 SplatUndef = HighUndef & LowUndef;
6536 bool BuildVectorSDNode::isConstant() const {
6537 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6538 unsigned Opc = getOperand(i).getOpcode();
6539 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6545 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6546 // Find the first non-undef value in the shuffle mask.
6548 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6551 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6553 // Make sure all remaining elements are either undef or the same as the first
6555 for (int Idx = Mask[i]; i != e; ++i)
6556 if (Mask[i] >= 0 && Mask[i] != Idx)
6562 static void checkForCyclesHelper(const SDNode *N,
6563 SmallPtrSet<const SDNode*, 32> &Visited,
6564 SmallPtrSet<const SDNode*, 32> &Checked) {
6565 // If this node has already been checked, don't check it again.
6566 if (Checked.count(N))
6569 // If a node has already been visited on this depth-first walk, reject it as
6571 if (!Visited.insert(N)) {
6572 dbgs() << "Offending node:\n";
6574 errs() << "Detected cycle in SelectionDAG\n";
6578 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6579 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6586 void llvm::checkForCycles(const llvm::SDNode *N) {
6588 assert(N && "Checking nonexistent SDNode");
6589 SmallPtrSet<const SDNode*, 32> visited;
6590 SmallPtrSet<const SDNode*, 32> checked;
6591 checkForCyclesHelper(N, visited, checked);
6595 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6596 checkForCycles(DAG->getRoot().getNode());