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 "SDNodeOrdering.h"
16 #include "SDNodeDbgValue.h"
17 #include "llvm/CallingConv.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DebugInfo.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/GlobalAlias.h"
23 #include "llvm/GlobalVariable.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Assembly/Writer.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineConstantPool.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineModuleInfo.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetData.h"
33 #include "llvm/Target/TargetLowering.h"
34 #include "llvm/Target/TargetSelectionDAGInfo.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Target/TargetInstrInfo.h"
37 #include "llvm/Target/TargetIntrinsicInfo.h"
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/ManagedStatic.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Support/Mutex.h"
46 #include "llvm/ADT/SetVector.h"
47 #include "llvm/ADT/SmallPtrSet.h"
48 #include "llvm/ADT/SmallSet.h"
49 #include "llvm/ADT/SmallVector.h"
50 #include "llvm/ADT/StringExtras.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 static const fltSemantics *EVTToAPFloatSemantics(EVT VT) {
63 switch (VT.getSimpleVT().SimpleTy) {
64 default: llvm_unreachable("Unknown FP format");
65 case MVT::f16: return &APFloat::IEEEhalf;
66 case MVT::f32: return &APFloat::IEEEsingle;
67 case MVT::f64: return &APFloat::IEEEdouble;
68 case MVT::f80: return &APFloat::x87DoubleExtended;
69 case MVT::f128: return &APFloat::IEEEquad;
70 case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
74 // Default null implementations of the callbacks.
75 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
76 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
78 //===----------------------------------------------------------------------===//
79 // ConstantFPSDNode Class
80 //===----------------------------------------------------------------------===//
82 /// isExactlyValue - We don't rely on operator== working on double values, as
83 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
84 /// As such, this method can be used to do an exact bit-for-bit comparison of
85 /// two floating point values.
86 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
87 return getValueAPF().bitwiseIsEqual(V);
90 bool ConstantFPSDNode::isValueValidForType(EVT VT,
92 assert(VT.isFloatingPoint() && "Can only convert between FP types");
94 // PPC long double cannot be converted to any other type.
95 if (VT == MVT::ppcf128 ||
96 &Val.getSemantics() == &APFloat::PPCDoubleDouble)
99 // convert modifies in place, so make a copy.
100 APFloat Val2 = APFloat(Val);
102 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven,
107 //===----------------------------------------------------------------------===//
109 //===----------------------------------------------------------------------===//
111 /// isBuildVectorAllOnes - Return true if the specified node is a
112 /// BUILD_VECTOR where all of the elements are ~0 or undef.
113 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
114 // Look through a bit convert.
115 if (N->getOpcode() == ISD::BITCAST)
116 N = N->getOperand(0).getNode();
118 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
120 unsigned i = 0, e = N->getNumOperands();
122 // Skip over all of the undef values.
123 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
126 // Do not accept an all-undef vector.
127 if (i == e) return false;
129 // Do not accept build_vectors that aren't all constants or which have non-~0
130 // elements. We have to be a bit careful here, as the type of the constant
131 // may not be the same as the type of the vector elements due to type
132 // legalization (the elements are promoted to a legal type for the target and
133 // a vector of a type may be legal when the base element type is not).
134 // We only want to check enough bits to cover the vector elements, because
135 // we care if the resultant vector is all ones, not whether the individual
137 SDValue NotZero = N->getOperand(i);
138 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
139 if (isa<ConstantSDNode>(NotZero)) {
140 if (cast<ConstantSDNode>(NotZero)->getAPIntValue().countTrailingOnes() <
143 } else if (isa<ConstantFPSDNode>(NotZero)) {
144 if (cast<ConstantFPSDNode>(NotZero)->getValueAPF()
145 .bitcastToAPInt().countTrailingOnes() < EltSize)
150 // Okay, we have at least one ~0 value, check to see if the rest match or are
151 // undefs. Even with the above element type twiddling, this should be OK, as
152 // the same type legalization should have applied to all the elements.
153 for (++i; i != e; ++i)
154 if (N->getOperand(i) != NotZero &&
155 N->getOperand(i).getOpcode() != ISD::UNDEF)
161 /// isBuildVectorAllZeros - Return true if the specified node is a
162 /// BUILD_VECTOR where all of the elements are 0 or undef.
163 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
164 // Look through a bit convert.
165 if (N->getOpcode() == ISD::BITCAST)
166 N = N->getOperand(0).getNode();
168 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
170 unsigned i = 0, e = N->getNumOperands();
172 // Skip over all of the undef values.
173 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
176 // Do not accept an all-undef vector.
177 if (i == e) return false;
179 // Do not accept build_vectors that aren't all constants or which have non-0
181 SDValue Zero = N->getOperand(i);
182 if (isa<ConstantSDNode>(Zero)) {
183 if (!cast<ConstantSDNode>(Zero)->isNullValue())
185 } else if (isa<ConstantFPSDNode>(Zero)) {
186 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
191 // Okay, we have at least one 0 value, check to see if the rest match or are
193 for (++i; i != e; ++i)
194 if (N->getOperand(i) != Zero &&
195 N->getOperand(i).getOpcode() != ISD::UNDEF)
200 /// isScalarToVector - Return true if the specified node is a
201 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
202 /// element is not an undef.
203 bool ISD::isScalarToVector(const SDNode *N) {
204 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
207 if (N->getOpcode() != ISD::BUILD_VECTOR)
209 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
211 unsigned NumElems = N->getNumOperands();
214 for (unsigned i = 1; i < NumElems; ++i) {
215 SDValue V = N->getOperand(i);
216 if (V.getOpcode() != ISD::UNDEF)
222 /// allOperandsUndef - Return true if the node has at least one operand
223 /// and all operands of the specified node are ISD::UNDEF.
224 bool ISD::allOperandsUndef(const SDNode *N) {
225 // Return false if the node has no operands.
226 // This is "logically inconsistent" with the definition of "all" but
227 // is probably the desired behavior.
228 if (N->getNumOperands() == 0)
231 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
232 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
238 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
239 /// when given the operation for (X op Y).
240 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
241 // To perform this operation, we just need to swap the L and G bits of the
243 unsigned OldL = (Operation >> 2) & 1;
244 unsigned OldG = (Operation >> 1) & 1;
245 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
246 (OldL << 1) | // New G bit
247 (OldG << 2)); // New L bit.
250 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
251 /// 'op' is a valid SetCC operation.
252 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
253 unsigned Operation = Op;
255 Operation ^= 7; // Flip L, G, E bits, but not U.
257 Operation ^= 15; // Flip all of the condition bits.
259 if (Operation > ISD::SETTRUE2)
260 Operation &= ~8; // Don't let N and U bits get set.
262 return ISD::CondCode(Operation);
266 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
267 /// signed operation and 2 if the result is an unsigned comparison. Return zero
268 /// if the operation does not depend on the sign of the input (setne and seteq).
269 static int isSignedOp(ISD::CondCode Opcode) {
271 default: llvm_unreachable("Illegal integer setcc operation!");
273 case ISD::SETNE: return 0;
277 case ISD::SETGE: return 1;
281 case ISD::SETUGE: return 2;
285 /// getSetCCOrOperation - Return the result of a logical OR between different
286 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
287 /// returns SETCC_INVALID if it is not possible to represent the resultant
289 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
291 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
292 // Cannot fold a signed integer setcc with an unsigned integer setcc.
293 return ISD::SETCC_INVALID;
295 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
297 // If the N and U bits get set then the resultant comparison DOES suddenly
298 // care about orderedness, and is true when ordered.
299 if (Op > ISD::SETTRUE2)
300 Op &= ~16; // Clear the U bit if the N bit is set.
302 // Canonicalize illegal integer setcc's.
303 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
306 return ISD::CondCode(Op);
309 /// getSetCCAndOperation - Return the result of a logical AND between different
310 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
311 /// function returns zero if it is not possible to represent the resultant
313 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
315 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
316 // Cannot fold a signed setcc with an unsigned setcc.
317 return ISD::SETCC_INVALID;
319 // Combine all of the condition bits.
320 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
322 // Canonicalize illegal integer setcc's.
326 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
327 case ISD::SETOEQ: // SETEQ & SETU[LG]E
328 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
329 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
330 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
337 //===----------------------------------------------------------------------===//
338 // SDNode Profile Support
339 //===----------------------------------------------------------------------===//
341 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
343 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
347 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
348 /// solely with their pointer.
349 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
350 ID.AddPointer(VTList.VTs);
353 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
355 static void AddNodeIDOperands(FoldingSetNodeID &ID,
356 const SDValue *Ops, unsigned NumOps) {
357 for (; NumOps; --NumOps, ++Ops) {
358 ID.AddPointer(Ops->getNode());
359 ID.AddInteger(Ops->getResNo());
363 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
365 static void AddNodeIDOperands(FoldingSetNodeID &ID,
366 const SDUse *Ops, unsigned NumOps) {
367 for (; NumOps; --NumOps, ++Ops) {
368 ID.AddPointer(Ops->getNode());
369 ID.AddInteger(Ops->getResNo());
373 static void AddNodeIDNode(FoldingSetNodeID &ID,
374 unsigned short OpC, SDVTList VTList,
375 const SDValue *OpList, unsigned N) {
376 AddNodeIDOpcode(ID, OpC);
377 AddNodeIDValueTypes(ID, VTList);
378 AddNodeIDOperands(ID, OpList, N);
381 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
383 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
384 switch (N->getOpcode()) {
385 case ISD::TargetExternalSymbol:
386 case ISD::ExternalSymbol:
387 llvm_unreachable("Should only be used on nodes with operands");
388 default: break; // Normal nodes don't need extra info.
389 case ISD::TargetConstant:
391 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
393 case ISD::TargetConstantFP:
394 case ISD::ConstantFP: {
395 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
398 case ISD::TargetGlobalAddress:
399 case ISD::GlobalAddress:
400 case ISD::TargetGlobalTLSAddress:
401 case ISD::GlobalTLSAddress: {
402 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
403 ID.AddPointer(GA->getGlobal());
404 ID.AddInteger(GA->getOffset());
405 ID.AddInteger(GA->getTargetFlags());
406 ID.AddInteger(GA->getAddressSpace());
409 case ISD::BasicBlock:
410 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
413 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
415 case ISD::RegisterMask:
416 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
419 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
421 case ISD::FrameIndex:
422 case ISD::TargetFrameIndex:
423 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
426 case ISD::TargetJumpTable:
427 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
428 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
430 case ISD::ConstantPool:
431 case ISD::TargetConstantPool: {
432 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
433 ID.AddInteger(CP->getAlignment());
434 ID.AddInteger(CP->getOffset());
435 if (CP->isMachineConstantPoolEntry())
436 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
438 ID.AddPointer(CP->getConstVal());
439 ID.AddInteger(CP->getTargetFlags());
442 case ISD::TargetIndex: {
443 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
444 ID.AddInteger(TI->getIndex());
445 ID.AddInteger(TI->getOffset());
446 ID.AddInteger(TI->getTargetFlags());
450 const LoadSDNode *LD = cast<LoadSDNode>(N);
451 ID.AddInteger(LD->getMemoryVT().getRawBits());
452 ID.AddInteger(LD->getRawSubclassData());
453 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
457 const StoreSDNode *ST = cast<StoreSDNode>(N);
458 ID.AddInteger(ST->getMemoryVT().getRawBits());
459 ID.AddInteger(ST->getRawSubclassData());
460 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
463 case ISD::ATOMIC_CMP_SWAP:
464 case ISD::ATOMIC_SWAP:
465 case ISD::ATOMIC_LOAD_ADD:
466 case ISD::ATOMIC_LOAD_SUB:
467 case ISD::ATOMIC_LOAD_AND:
468 case ISD::ATOMIC_LOAD_OR:
469 case ISD::ATOMIC_LOAD_XOR:
470 case ISD::ATOMIC_LOAD_NAND:
471 case ISD::ATOMIC_LOAD_MIN:
472 case ISD::ATOMIC_LOAD_MAX:
473 case ISD::ATOMIC_LOAD_UMIN:
474 case ISD::ATOMIC_LOAD_UMAX:
475 case ISD::ATOMIC_LOAD:
476 case ISD::ATOMIC_STORE: {
477 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
478 ID.AddInteger(AT->getMemoryVT().getRawBits());
479 ID.AddInteger(AT->getRawSubclassData());
480 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
483 case ISD::PREFETCH: {
484 const MemSDNode *PF = cast<MemSDNode>(N);
485 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
488 case ISD::VECTOR_SHUFFLE: {
489 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
490 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
492 ID.AddInteger(SVN->getMaskElt(i));
495 case ISD::TargetBlockAddress:
496 case ISD::BlockAddress: {
497 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
498 ID.AddPointer(BA->getBlockAddress());
499 ID.AddInteger(BA->getOffset());
500 ID.AddInteger(BA->getTargetFlags());
503 } // end switch (N->getOpcode())
505 // Target specific memory nodes could also have address spaces to check.
506 if (N->isTargetMemoryOpcode())
507 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
510 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
512 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
513 AddNodeIDOpcode(ID, N->getOpcode());
514 // Add the return value info.
515 AddNodeIDValueTypes(ID, N->getVTList());
516 // Add the operand info.
517 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
519 // Handle SDNode leafs with special info.
520 AddNodeIDCustom(ID, N);
523 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
524 /// the CSE map that carries volatility, temporalness, indexing mode, and
525 /// extension/truncation information.
527 static inline unsigned
528 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
529 bool isNonTemporal, bool isInvariant) {
530 assert((ConvType & 3) == ConvType &&
531 "ConvType may not require more than 2 bits!");
532 assert((AM & 7) == AM &&
533 "AM may not require more than 3 bits!");
537 (isNonTemporal << 6) |
541 //===----------------------------------------------------------------------===//
542 // SelectionDAG Class
543 //===----------------------------------------------------------------------===//
545 /// doNotCSE - Return true if CSE should not be performed for this node.
546 static bool doNotCSE(SDNode *N) {
547 if (N->getValueType(0) == MVT::Glue)
548 return true; // Never CSE anything that produces a flag.
550 switch (N->getOpcode()) {
552 case ISD::HANDLENODE:
554 return true; // Never CSE these nodes.
557 // Check that remaining values produced are not flags.
558 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
559 if (N->getValueType(i) == MVT::Glue)
560 return true; // Never CSE anything that produces a flag.
565 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
567 void SelectionDAG::RemoveDeadNodes() {
568 // Create a dummy node (which is not added to allnodes), that adds a reference
569 // to the root node, preventing it from being deleted.
570 HandleSDNode Dummy(getRoot());
572 SmallVector<SDNode*, 128> DeadNodes;
574 // Add all obviously-dead nodes to the DeadNodes worklist.
575 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
577 DeadNodes.push_back(I);
579 RemoveDeadNodes(DeadNodes);
581 // If the root changed (e.g. it was a dead load, update the root).
582 setRoot(Dummy.getValue());
585 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
586 /// given list, and any nodes that become unreachable as a result.
587 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
589 // Process the worklist, deleting the nodes and adding their uses to the
591 while (!DeadNodes.empty()) {
592 SDNode *N = DeadNodes.pop_back_val();
594 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
595 DUL->NodeDeleted(N, 0);
597 // Take the node out of the appropriate CSE map.
598 RemoveNodeFromCSEMaps(N);
600 // Next, brutally remove the operand list. This is safe to do, as there are
601 // no cycles in the graph.
602 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
604 SDNode *Operand = Use.getNode();
607 // Now that we removed this operand, see if there are no uses of it left.
608 if (Operand->use_empty())
609 DeadNodes.push_back(Operand);
616 void SelectionDAG::RemoveDeadNode(SDNode *N){
617 SmallVector<SDNode*, 16> DeadNodes(1, N);
619 // Create a dummy node that adds a reference to the root node, preventing
620 // it from being deleted. (This matters if the root is an operand of the
622 HandleSDNode Dummy(getRoot());
624 RemoveDeadNodes(DeadNodes);
627 void SelectionDAG::DeleteNode(SDNode *N) {
628 // First take this out of the appropriate CSE map.
629 RemoveNodeFromCSEMaps(N);
631 // Finally, remove uses due to operands of this node, remove from the
632 // AllNodes list, and delete the node.
633 DeleteNodeNotInCSEMaps(N);
636 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
637 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
638 assert(N->use_empty() && "Cannot delete a node that is not dead!");
640 // Drop all of the operands and decrement used node's use counts.
646 void SelectionDAG::DeallocateNode(SDNode *N) {
647 if (N->OperandsNeedDelete)
648 delete[] N->OperandList;
650 // Set the opcode to DELETED_NODE to help catch bugs when node
651 // memory is reallocated.
652 N->NodeType = ISD::DELETED_NODE;
654 NodeAllocator.Deallocate(AllNodes.remove(N));
656 // Remove the ordering of this node.
659 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
660 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
661 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
662 DbgVals[i]->setIsInvalidated();
665 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
666 /// correspond to it. This is useful when we're about to delete or repurpose
667 /// the node. We don't want future request for structurally identical nodes
668 /// to return N anymore.
669 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
671 switch (N->getOpcode()) {
672 case ISD::HANDLENODE: return false; // noop.
674 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
675 "Cond code doesn't exist!");
676 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
677 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
679 case ISD::ExternalSymbol:
680 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
682 case ISD::TargetExternalSymbol: {
683 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
684 Erased = TargetExternalSymbols.erase(
685 std::pair<std::string,unsigned char>(ESN->getSymbol(),
686 ESN->getTargetFlags()));
689 case ISD::VALUETYPE: {
690 EVT VT = cast<VTSDNode>(N)->getVT();
691 if (VT.isExtended()) {
692 Erased = ExtendedValueTypeNodes.erase(VT);
694 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
695 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
700 // Remove it from the CSE Map.
701 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
702 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
703 Erased = CSEMap.RemoveNode(N);
707 // Verify that the node was actually in one of the CSE maps, unless it has a
708 // flag result (which cannot be CSE'd) or is one of the special cases that are
709 // not subject to CSE.
710 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
711 !N->isMachineOpcode() && !doNotCSE(N)) {
714 llvm_unreachable("Node is not in map!");
720 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
721 /// maps and modified in place. Add it back to the CSE maps, unless an identical
722 /// node already exists, in which case transfer all its users to the existing
723 /// node. This transfer can potentially trigger recursive merging.
726 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
727 // For node types that aren't CSE'd, just act as if no identical node
730 SDNode *Existing = CSEMap.GetOrInsertNode(N);
732 // If there was already an existing matching node, use ReplaceAllUsesWith
733 // to replace the dead one with the existing one. This can cause
734 // recursive merging of other unrelated nodes down the line.
735 ReplaceAllUsesWith(N, Existing);
737 // N is now dead. Inform the listeners and delete it.
738 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
739 DUL->NodeDeleted(N, Existing);
740 DeleteNodeNotInCSEMaps(N);
745 // If the node doesn't already exist, we updated it. Inform listeners.
746 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
750 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
751 /// were replaced with those specified. If this node is never memoized,
752 /// return null, otherwise return a pointer to the slot it would take. If a
753 /// node already exists with these operands, the slot will be non-null.
754 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
759 SDValue Ops[] = { Op };
761 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
762 AddNodeIDCustom(ID, N);
763 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
767 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
768 /// were replaced with those specified. If this node is never memoized,
769 /// return null, otherwise return a pointer to the slot it would take. If a
770 /// node already exists with these operands, the slot will be non-null.
771 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
772 SDValue Op1, SDValue Op2,
777 SDValue Ops[] = { Op1, Op2 };
779 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
780 AddNodeIDCustom(ID, N);
781 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
786 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
787 /// were replaced with those specified. If this node is never memoized,
788 /// return null, otherwise return a pointer to the slot it would take. If a
789 /// node already exists with these operands, the slot will be non-null.
790 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
791 const SDValue *Ops,unsigned NumOps,
797 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
798 AddNodeIDCustom(ID, N);
799 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
804 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
805 static void VerifyNodeCommon(SDNode *N) {
806 switch (N->getOpcode()) {
809 case ISD::BUILD_PAIR: {
810 EVT VT = N->getValueType(0);
811 assert(N->getNumValues() == 1 && "Too many results!");
812 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
813 "Wrong return type!");
814 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
815 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
816 "Mismatched operand types!");
817 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
818 "Wrong operand type!");
819 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
820 "Wrong return type size");
823 case ISD::BUILD_VECTOR: {
824 assert(N->getNumValues() == 1 && "Too many results!");
825 assert(N->getValueType(0).isVector() && "Wrong return type!");
826 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
827 "Wrong number of operands!");
828 EVT EltVT = N->getValueType(0).getVectorElementType();
829 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
830 assert((I->getValueType() == EltVT ||
831 (EltVT.isInteger() && I->getValueType().isInteger() &&
832 EltVT.bitsLE(I->getValueType()))) &&
833 "Wrong operand type!");
834 assert(I->getValueType() == N->getOperand(0).getValueType() &&
835 "Operands must all have the same type");
842 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
843 static void VerifySDNode(SDNode *N) {
844 // The SDNode allocators cannot be used to allocate nodes with fields that are
845 // not present in an SDNode!
846 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
847 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
848 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
849 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
850 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
851 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
852 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
853 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
854 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
855 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
856 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
857 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
858 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
859 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
860 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
861 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
862 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
863 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
864 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
869 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
871 static void VerifyMachineNode(SDNode *N) {
872 // The MachineNode allocators cannot be used to allocate nodes with fields
873 // that are not present in a MachineNode!
874 // Currently there are no such nodes.
880 /// getEVTAlignment - Compute the default alignment value for the
883 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
884 Type *Ty = VT == MVT::iPTR ?
885 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
886 VT.getTypeForEVT(*getContext());
888 return TLI.getTargetData()->getABITypeAlignment(Ty);
891 // EntryNode could meaningfully have debug info if we can find it...
892 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
893 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
894 OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
895 Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
896 AllNodes.push_back(&EntryNode);
897 Ordering = new SDNodeOrdering();
898 DbgInfo = new SDDbgInfo();
901 void SelectionDAG::init(MachineFunction &mf) {
903 Context = &mf.getFunction()->getContext();
906 SelectionDAG::~SelectionDAG() {
907 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
913 void SelectionDAG::allnodes_clear() {
914 assert(&*AllNodes.begin() == &EntryNode);
915 AllNodes.remove(AllNodes.begin());
916 while (!AllNodes.empty())
917 DeallocateNode(AllNodes.begin());
920 void SelectionDAG::clear() {
922 OperandAllocator.Reset();
925 ExtendedValueTypeNodes.clear();
926 ExternalSymbols.clear();
927 TargetExternalSymbols.clear();
928 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
929 static_cast<CondCodeSDNode*>(0));
930 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
931 static_cast<SDNode*>(0));
933 EntryNode.UseList = 0;
934 AllNodes.push_back(&EntryNode);
935 Root = getEntryNode();
940 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
941 return VT.bitsGT(Op.getValueType()) ?
942 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
943 getNode(ISD::TRUNCATE, DL, VT, Op);
946 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
947 return VT.bitsGT(Op.getValueType()) ?
948 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
949 getNode(ISD::TRUNCATE, DL, VT, Op);
952 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
953 return VT.bitsGT(Op.getValueType()) ?
954 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
955 getNode(ISD::TRUNCATE, DL, VT, Op);
958 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
959 assert(!VT.isVector() &&
960 "getZeroExtendInReg should use the vector element type instead of "
962 if (Op.getValueType() == VT) return Op;
963 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
964 APInt Imm = APInt::getLowBitsSet(BitWidth,
966 return getNode(ISD::AND, DL, Op.getValueType(), Op,
967 getConstant(Imm, Op.getValueType()));
970 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
972 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
973 EVT EltVT = VT.getScalarType();
975 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
976 return getNode(ISD::XOR, DL, VT, Val, NegOne);
979 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
980 EVT EltVT = VT.getScalarType();
981 assert((EltVT.getSizeInBits() >= 64 ||
982 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
983 "getConstant with a uint64_t value that doesn't fit in the type!");
984 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
987 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
988 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
991 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
992 assert(VT.isInteger() && "Cannot create FP integer constant!");
994 EVT EltVT = VT.getScalarType();
995 const ConstantInt *Elt = &Val;
997 // In some cases the vector type is legal but the element type is illegal and
998 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
999 // inserted value (the type does not need to match the vector element type).
1000 // Any extra bits introduced will be truncated away.
1001 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
1002 TargetLowering::TypePromoteInteger) {
1003 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
1004 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1005 Elt = ConstantInt::get(*getContext(), NewVal);
1008 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1009 "APInt size does not match type size!");
1010 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1011 FoldingSetNodeID ID;
1012 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1016 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1018 return SDValue(N, 0);
1021 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1022 CSEMap.InsertNode(N, IP);
1023 AllNodes.push_back(N);
1026 SDValue Result(N, 0);
1027 if (VT.isVector()) {
1028 SmallVector<SDValue, 8> Ops;
1029 Ops.assign(VT.getVectorNumElements(), Result);
1030 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1035 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1036 return getConstant(Val, TLI.getPointerTy(), isTarget);
1040 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1041 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1044 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1045 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1047 EVT EltVT = VT.getScalarType();
1049 // Do the map lookup using the actual bit pattern for the floating point
1050 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1051 // we don't have issues with SNANs.
1052 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1053 FoldingSetNodeID ID;
1054 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1058 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1060 return SDValue(N, 0);
1063 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1064 CSEMap.InsertNode(N, IP);
1065 AllNodes.push_back(N);
1068 SDValue Result(N, 0);
1069 if (VT.isVector()) {
1070 SmallVector<SDValue, 8> Ops;
1071 Ops.assign(VT.getVectorNumElements(), Result);
1072 // FIXME DebugLoc info might be appropriate here
1073 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1078 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1079 EVT EltVT = VT.getScalarType();
1080 if (EltVT==MVT::f32)
1081 return getConstantFP(APFloat((float)Val), VT, isTarget);
1082 else if (EltVT==MVT::f64)
1083 return getConstantFP(APFloat(Val), VT, isTarget);
1084 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::f16) {
1086 APFloat apf = APFloat(Val);
1087 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1089 return getConstantFP(apf, VT, isTarget);
1091 llvm_unreachable("Unsupported type in getConstantFP");
1094 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1095 EVT VT, int64_t Offset,
1097 unsigned char TargetFlags) {
1098 assert((TargetFlags == 0 || isTargetGA) &&
1099 "Cannot set target flags on target-independent globals");
1101 // Truncate (with sign-extension) the offset value to the pointer size.
1102 unsigned BitWidth = TLI.getPointerTy().getSizeInBits();
1104 Offset = SignExtend64(Offset, BitWidth);
1106 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1108 // If GV is an alias then use the aliasee for determining thread-localness.
1109 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1110 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1114 if (GVar && GVar->isThreadLocal())
1115 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1117 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1119 FoldingSetNodeID ID;
1120 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1122 ID.AddInteger(Offset);
1123 ID.AddInteger(TargetFlags);
1124 ID.AddInteger(GV->getType()->getAddressSpace());
1126 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1127 return SDValue(E, 0);
1129 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1130 Offset, TargetFlags);
1131 CSEMap.InsertNode(N, IP);
1132 AllNodes.push_back(N);
1133 return SDValue(N, 0);
1136 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1137 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1138 FoldingSetNodeID ID;
1139 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1142 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1143 return SDValue(E, 0);
1145 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1146 CSEMap.InsertNode(N, IP);
1147 AllNodes.push_back(N);
1148 return SDValue(N, 0);
1151 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1152 unsigned char TargetFlags) {
1153 assert((TargetFlags == 0 || isTarget) &&
1154 "Cannot set target flags on target-independent jump tables");
1155 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1156 FoldingSetNodeID ID;
1157 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1159 ID.AddInteger(TargetFlags);
1161 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1162 return SDValue(E, 0);
1164 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1166 CSEMap.InsertNode(N, IP);
1167 AllNodes.push_back(N);
1168 return SDValue(N, 0);
1171 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1172 unsigned Alignment, int Offset,
1174 unsigned char TargetFlags) {
1175 assert((TargetFlags == 0 || isTarget) &&
1176 "Cannot set target flags on target-independent globals");
1178 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1179 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1180 FoldingSetNodeID ID;
1181 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1182 ID.AddInteger(Alignment);
1183 ID.AddInteger(Offset);
1185 ID.AddInteger(TargetFlags);
1187 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1188 return SDValue(E, 0);
1190 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1191 Alignment, TargetFlags);
1192 CSEMap.InsertNode(N, IP);
1193 AllNodes.push_back(N);
1194 return SDValue(N, 0);
1198 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1199 unsigned Alignment, int Offset,
1201 unsigned char TargetFlags) {
1202 assert((TargetFlags == 0 || isTarget) &&
1203 "Cannot set target flags on target-independent globals");
1205 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1206 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1207 FoldingSetNodeID ID;
1208 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1209 ID.AddInteger(Alignment);
1210 ID.AddInteger(Offset);
1211 C->addSelectionDAGCSEId(ID);
1212 ID.AddInteger(TargetFlags);
1214 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1215 return SDValue(E, 0);
1217 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1218 Alignment, TargetFlags);
1219 CSEMap.InsertNode(N, IP);
1220 AllNodes.push_back(N);
1221 return SDValue(N, 0);
1224 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1225 unsigned char TargetFlags) {
1226 FoldingSetNodeID ID;
1227 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1228 ID.AddInteger(Index);
1229 ID.AddInteger(Offset);
1230 ID.AddInteger(TargetFlags);
1232 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1233 return SDValue(E, 0);
1235 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1237 CSEMap.InsertNode(N, IP);
1238 AllNodes.push_back(N);
1239 return SDValue(N, 0);
1242 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1243 FoldingSetNodeID ID;
1244 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1247 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1248 return SDValue(E, 0);
1250 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1251 CSEMap.InsertNode(N, IP);
1252 AllNodes.push_back(N);
1253 return SDValue(N, 0);
1256 SDValue SelectionDAG::getValueType(EVT VT) {
1257 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1258 ValueTypeNodes.size())
1259 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1261 SDNode *&N = VT.isExtended() ?
1262 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1264 if (N) return SDValue(N, 0);
1265 N = new (NodeAllocator) VTSDNode(VT);
1266 AllNodes.push_back(N);
1267 return SDValue(N, 0);
1270 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1271 SDNode *&N = ExternalSymbols[Sym];
1272 if (N) return SDValue(N, 0);
1273 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1274 AllNodes.push_back(N);
1275 return SDValue(N, 0);
1278 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1279 unsigned char TargetFlags) {
1281 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1283 if (N) return SDValue(N, 0);
1284 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1285 AllNodes.push_back(N);
1286 return SDValue(N, 0);
1289 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1290 if ((unsigned)Cond >= CondCodeNodes.size())
1291 CondCodeNodes.resize(Cond+1);
1293 if (CondCodeNodes[Cond] == 0) {
1294 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1295 CondCodeNodes[Cond] = N;
1296 AllNodes.push_back(N);
1299 return SDValue(CondCodeNodes[Cond], 0);
1302 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1303 // the shuffle mask M that point at N1 to point at N2, and indices that point
1304 // N2 to point at N1.
1305 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1307 int NElts = M.size();
1308 for (int i = 0; i != NElts; ++i) {
1316 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1317 SDValue N2, const int *Mask) {
1318 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1319 assert(VT.isVector() && N1.getValueType().isVector() &&
1320 "Vector Shuffle VTs must be a vectors");
1321 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1322 && "Vector Shuffle VTs must have same element type");
1324 // Canonicalize shuffle undef, undef -> undef
1325 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1326 return getUNDEF(VT);
1328 // Validate that all indices in Mask are within the range of the elements
1329 // input to the shuffle.
1330 unsigned NElts = VT.getVectorNumElements();
1331 SmallVector<int, 8> MaskVec;
1332 for (unsigned i = 0; i != NElts; ++i) {
1333 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1334 MaskVec.push_back(Mask[i]);
1337 // Canonicalize shuffle v, v -> v, undef
1340 for (unsigned i = 0; i != NElts; ++i)
1341 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1344 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1345 if (N1.getOpcode() == ISD::UNDEF)
1346 commuteShuffle(N1, N2, MaskVec);
1348 // Canonicalize all index into lhs, -> shuffle lhs, undef
1349 // Canonicalize all index into rhs, -> shuffle rhs, undef
1350 bool AllLHS = true, AllRHS = true;
1351 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1352 for (unsigned i = 0; i != NElts; ++i) {
1353 if (MaskVec[i] >= (int)NElts) {
1358 } else if (MaskVec[i] >= 0) {
1362 if (AllLHS && AllRHS)
1363 return getUNDEF(VT);
1364 if (AllLHS && !N2Undef)
1368 commuteShuffle(N1, N2, MaskVec);
1371 // If Identity shuffle, or all shuffle in to undef, return that node.
1372 bool AllUndef = true;
1373 bool Identity = true;
1374 for (unsigned i = 0; i != NElts; ++i) {
1375 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1376 if (MaskVec[i] >= 0) AllUndef = false;
1378 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1381 return getUNDEF(VT);
1383 FoldingSetNodeID ID;
1384 SDValue Ops[2] = { N1, N2 };
1385 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1386 for (unsigned i = 0; i != NElts; ++i)
1387 ID.AddInteger(MaskVec[i]);
1390 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1391 return SDValue(E, 0);
1393 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1394 // SDNode doesn't have access to it. This memory will be "leaked" when
1395 // the node is deallocated, but recovered when the NodeAllocator is released.
1396 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1397 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1399 ShuffleVectorSDNode *N =
1400 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1401 CSEMap.InsertNode(N, IP);
1402 AllNodes.push_back(N);
1403 return SDValue(N, 0);
1406 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1407 SDValue Val, SDValue DTy,
1408 SDValue STy, SDValue Rnd, SDValue Sat,
1409 ISD::CvtCode Code) {
1410 // If the src and dest types are the same and the conversion is between
1411 // integer types of the same sign or two floats, no conversion is necessary.
1413 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1416 FoldingSetNodeID ID;
1417 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1418 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1420 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1421 return SDValue(E, 0);
1423 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1425 CSEMap.InsertNode(N, IP);
1426 AllNodes.push_back(N);
1427 return SDValue(N, 0);
1430 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1431 FoldingSetNodeID ID;
1432 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1433 ID.AddInteger(RegNo);
1435 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1436 return SDValue(E, 0);
1438 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1439 CSEMap.InsertNode(N, IP);
1440 AllNodes.push_back(N);
1441 return SDValue(N, 0);
1444 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1445 FoldingSetNodeID ID;
1446 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1447 ID.AddPointer(RegMask);
1449 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1450 return SDValue(E, 0);
1452 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1453 CSEMap.InsertNode(N, IP);
1454 AllNodes.push_back(N);
1455 return SDValue(N, 0);
1458 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1459 FoldingSetNodeID ID;
1460 SDValue Ops[] = { Root };
1461 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1462 ID.AddPointer(Label);
1464 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1465 return SDValue(E, 0);
1467 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1468 CSEMap.InsertNode(N, IP);
1469 AllNodes.push_back(N);
1470 return SDValue(N, 0);
1474 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1477 unsigned char TargetFlags) {
1478 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1480 FoldingSetNodeID ID;
1481 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1483 ID.AddInteger(Offset);
1484 ID.AddInteger(TargetFlags);
1486 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1487 return SDValue(E, 0);
1489 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1491 CSEMap.InsertNode(N, IP);
1492 AllNodes.push_back(N);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getSrcValue(const Value *V) {
1497 assert((!V || V->getType()->isPointerTy()) &&
1498 "SrcValue is not a pointer?");
1500 FoldingSetNodeID ID;
1501 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1505 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1506 return SDValue(E, 0);
1508 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1509 CSEMap.InsertNode(N, IP);
1510 AllNodes.push_back(N);
1511 return SDValue(N, 0);
1514 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1515 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1516 FoldingSetNodeID ID;
1517 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1521 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1522 return SDValue(E, 0);
1524 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1525 CSEMap.InsertNode(N, IP);
1526 AllNodes.push_back(N);
1527 return SDValue(N, 0);
1531 /// getShiftAmountOperand - Return the specified value casted to
1532 /// the target's desired shift amount type.
1533 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1534 EVT OpTy = Op.getValueType();
1535 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1536 if (OpTy == ShTy || OpTy.isVector()) return Op;
1538 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1539 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1542 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1543 /// specified value type.
1544 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1545 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1546 unsigned ByteSize = VT.getStoreSize();
1547 Type *Ty = VT.getTypeForEVT(*getContext());
1548 unsigned StackAlign =
1549 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1551 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1552 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1555 /// CreateStackTemporary - Create a stack temporary suitable for holding
1556 /// either of the specified value types.
1557 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1558 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1559 VT2.getStoreSizeInBits())/8;
1560 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1561 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1562 const TargetData *TD = TLI.getTargetData();
1563 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1564 TD->getPrefTypeAlignment(Ty2));
1566 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1567 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1568 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1571 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1572 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1573 // These setcc operations always fold.
1577 case ISD::SETFALSE2: return getConstant(0, VT);
1579 case ISD::SETTRUE2: return getConstant(1, VT);
1591 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1595 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1596 const APInt &C2 = N2C->getAPIntValue();
1597 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1598 const APInt &C1 = N1C->getAPIntValue();
1601 default: llvm_unreachable("Unknown integer setcc!");
1602 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1603 case ISD::SETNE: return getConstant(C1 != C2, VT);
1604 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1605 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1606 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1607 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1608 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1609 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1610 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1611 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1615 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1616 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1617 // No compile time operations on this type yet.
1618 if (N1C->getValueType(0) == MVT::ppcf128)
1621 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1624 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1625 return getUNDEF(VT);
1627 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1628 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1629 return getUNDEF(VT);
1631 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1632 R==APFloat::cmpLessThan, VT);
1633 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1634 return getUNDEF(VT);
1636 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1637 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1638 return getUNDEF(VT);
1640 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1641 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1642 return getUNDEF(VT);
1644 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1645 R==APFloat::cmpEqual, VT);
1646 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1647 return getUNDEF(VT);
1649 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1650 R==APFloat::cmpEqual, VT);
1651 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1652 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1653 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1654 R==APFloat::cmpEqual, VT);
1655 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1656 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1657 R==APFloat::cmpLessThan, VT);
1658 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1659 R==APFloat::cmpUnordered, VT);
1660 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1661 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1664 // Ensure that the constant occurs on the RHS.
1665 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1669 // Could not fold it.
1673 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1674 /// use this predicate to simplify operations downstream.
1675 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1676 // This predicate is not safe for vector operations.
1677 if (Op.getValueType().isVector())
1680 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1681 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1684 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1685 /// this predicate to simplify operations downstream. Mask is known to be zero
1686 /// for bits that V cannot have.
1687 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1688 unsigned Depth) const {
1689 APInt KnownZero, KnownOne;
1690 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1691 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1692 return (KnownZero & Mask) == Mask;
1695 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1696 /// known to be either zero or one and return them in the KnownZero/KnownOne
1697 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1699 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1700 APInt &KnownOne, unsigned Depth) const {
1701 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1703 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1705 return; // Limit search depth.
1707 APInt KnownZero2, KnownOne2;
1709 switch (Op.getOpcode()) {
1711 // We know all of the bits for a constant!
1712 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1713 KnownZero = ~KnownOne;
1716 // If either the LHS or the RHS are Zero, the result is zero.
1717 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1718 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1719 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1720 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1722 // Output known-1 bits are only known if set in both the LHS & RHS.
1723 KnownOne &= KnownOne2;
1724 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1725 KnownZero |= KnownZero2;
1728 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1729 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1730 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1731 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1733 // Output known-0 bits are only known if clear in both the LHS & RHS.
1734 KnownZero &= KnownZero2;
1735 // Output known-1 are known to be set if set in either the LHS | RHS.
1736 KnownOne |= KnownOne2;
1739 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1740 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1741 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1742 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1744 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1745 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1746 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1747 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1748 KnownZero = KnownZeroOut;
1752 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1753 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1754 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1755 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1757 // If low bits are zero in either operand, output low known-0 bits.
1758 // Also compute a conserative estimate for high known-0 bits.
1759 // More trickiness is possible, but this is sufficient for the
1760 // interesting case of alignment computation.
1761 KnownOne.clearAllBits();
1762 unsigned TrailZ = KnownZero.countTrailingOnes() +
1763 KnownZero2.countTrailingOnes();
1764 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1765 KnownZero2.countLeadingOnes(),
1766 BitWidth) - BitWidth;
1768 TrailZ = std::min(TrailZ, BitWidth);
1769 LeadZ = std::min(LeadZ, BitWidth);
1770 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1771 APInt::getHighBitsSet(BitWidth, LeadZ);
1775 // For the purposes of computing leading zeros we can conservatively
1776 // treat a udiv as a logical right shift by the power of 2 known to
1777 // be less than the denominator.
1778 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1779 unsigned LeadZ = KnownZero2.countLeadingOnes();
1781 KnownOne2.clearAllBits();
1782 KnownZero2.clearAllBits();
1783 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1784 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1785 if (RHSUnknownLeadingOnes != BitWidth)
1786 LeadZ = std::min(BitWidth,
1787 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1789 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1793 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1794 ComputeMaskedBits(Op.getOperand(1), 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 // Only known if known in both the LHS and RHS.
1799 KnownOne &= KnownOne2;
1800 KnownZero &= KnownZero2;
1802 case ISD::SELECT_CC:
1803 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1804 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1805 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1806 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1808 // Only known if known in both the LHS and RHS.
1809 KnownOne &= KnownOne2;
1810 KnownZero &= KnownZero2;
1818 if (Op.getResNo() != 1)
1820 // The boolean result conforms to getBooleanContents. Fall through.
1822 // If we know the result of a setcc has the top bits zero, use this info.
1823 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1824 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1825 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1828 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1829 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1830 unsigned ShAmt = SA->getZExtValue();
1832 // If the shift count is an invalid immediate, don't do anything.
1833 if (ShAmt >= BitWidth)
1836 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1837 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1838 KnownZero <<= ShAmt;
1840 // low bits known zero.
1841 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1845 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1846 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1847 unsigned ShAmt = SA->getZExtValue();
1849 // If the shift count is an invalid immediate, don't do anything.
1850 if (ShAmt >= BitWidth)
1853 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1854 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1855 KnownZero = KnownZero.lshr(ShAmt);
1856 KnownOne = KnownOne.lshr(ShAmt);
1858 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1859 KnownZero |= HighBits; // High bits known zero.
1863 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1864 unsigned ShAmt = SA->getZExtValue();
1866 // If the shift count is an invalid immediate, don't do anything.
1867 if (ShAmt >= BitWidth)
1870 // If any of the demanded bits are produced by the sign extension, we also
1871 // demand the input sign bit.
1872 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1874 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1875 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1876 KnownZero = KnownZero.lshr(ShAmt);
1877 KnownOne = KnownOne.lshr(ShAmt);
1879 // Handle the sign bits.
1880 APInt SignBit = APInt::getSignBit(BitWidth);
1881 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1883 if (KnownZero.intersects(SignBit)) {
1884 KnownZero |= HighBits; // New bits are known zero.
1885 } else if (KnownOne.intersects(SignBit)) {
1886 KnownOne |= HighBits; // New bits are known one.
1890 case ISD::SIGN_EXTEND_INREG: {
1891 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1892 unsigned EBits = EVT.getScalarType().getSizeInBits();
1894 // Sign extension. Compute the demanded bits in the result that are not
1895 // present in the input.
1896 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1898 APInt InSignBit = APInt::getSignBit(EBits);
1899 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1901 // If the sign extended bits are demanded, we know that the sign
1903 InSignBit = InSignBit.zext(BitWidth);
1904 if (NewBits.getBoolValue())
1905 InputDemandedBits |= InSignBit;
1907 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1908 KnownOne &= InputDemandedBits;
1909 KnownZero &= InputDemandedBits;
1910 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1912 // If the sign bit of the input is known set or clear, then we know the
1913 // top bits of the result.
1914 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1915 KnownZero |= NewBits;
1916 KnownOne &= ~NewBits;
1917 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1918 KnownOne |= NewBits;
1919 KnownZero &= ~NewBits;
1920 } else { // Input sign bit unknown
1921 KnownZero &= ~NewBits;
1922 KnownOne &= ~NewBits;
1927 case ISD::CTTZ_ZERO_UNDEF:
1929 case ISD::CTLZ_ZERO_UNDEF:
1931 unsigned LowBits = Log2_32(BitWidth)+1;
1932 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1933 KnownOne.clearAllBits();
1937 LoadSDNode *LD = cast<LoadSDNode>(Op);
1938 if (ISD::isZEXTLoad(Op.getNode())) {
1939 EVT VT = LD->getMemoryVT();
1940 unsigned MemBits = VT.getScalarType().getSizeInBits();
1941 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
1942 } else if (const MDNode *Ranges = LD->getRanges()) {
1943 computeMaskedBitsLoad(*Ranges, KnownZero);
1947 case ISD::ZERO_EXTEND: {
1948 EVT InVT = Op.getOperand(0).getValueType();
1949 unsigned InBits = InVT.getScalarType().getSizeInBits();
1950 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1951 KnownZero = KnownZero.trunc(InBits);
1952 KnownOne = KnownOne.trunc(InBits);
1953 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1954 KnownZero = KnownZero.zext(BitWidth);
1955 KnownOne = KnownOne.zext(BitWidth);
1956 KnownZero |= NewBits;
1959 case ISD::SIGN_EXTEND: {
1960 EVT InVT = Op.getOperand(0).getValueType();
1961 unsigned InBits = InVT.getScalarType().getSizeInBits();
1962 APInt InSignBit = APInt::getSignBit(InBits);
1963 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1965 KnownZero = KnownZero.trunc(InBits);
1966 KnownOne = KnownOne.trunc(InBits);
1967 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1969 // Note if the sign bit is known to be zero or one.
1970 bool SignBitKnownZero = KnownZero.isNegative();
1971 bool SignBitKnownOne = KnownOne.isNegative();
1972 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1973 "Sign bit can't be known to be both zero and one!");
1975 KnownZero = KnownZero.zext(BitWidth);
1976 KnownOne = KnownOne.zext(BitWidth);
1978 // If the sign bit is known zero or one, the top bits match.
1979 if (SignBitKnownZero)
1980 KnownZero |= NewBits;
1981 else if (SignBitKnownOne)
1982 KnownOne |= NewBits;
1985 case ISD::ANY_EXTEND: {
1986 EVT InVT = Op.getOperand(0).getValueType();
1987 unsigned InBits = InVT.getScalarType().getSizeInBits();
1988 KnownZero = KnownZero.trunc(InBits);
1989 KnownOne = KnownOne.trunc(InBits);
1990 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1991 KnownZero = KnownZero.zext(BitWidth);
1992 KnownOne = KnownOne.zext(BitWidth);
1995 case ISD::TRUNCATE: {
1996 EVT InVT = Op.getOperand(0).getValueType();
1997 unsigned InBits = InVT.getScalarType().getSizeInBits();
1998 KnownZero = KnownZero.zext(InBits);
1999 KnownOne = KnownOne.zext(InBits);
2000 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2001 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2002 KnownZero = KnownZero.trunc(BitWidth);
2003 KnownOne = KnownOne.trunc(BitWidth);
2006 case ISD::AssertZext: {
2007 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2008 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2009 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2010 KnownZero |= (~InMask);
2011 KnownOne &= (~KnownZero);
2015 // All bits are zero except the low bit.
2016 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2020 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2021 // We know that the top bits of C-X are clear if X contains less bits
2022 // than C (i.e. no wrap-around can happen). For example, 20-X is
2023 // positive if we can prove that X is >= 0 and < 16.
2024 if (CLHS->getAPIntValue().isNonNegative()) {
2025 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2026 // NLZ can't be BitWidth with no sign bit
2027 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2028 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2030 // If all of the MaskV bits are known to be zero, then we know the
2031 // output top bits are zero, because we now know that the output is
2033 if ((KnownZero2 & MaskV) == MaskV) {
2034 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2035 // Top bits known zero.
2036 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2044 // Output known-0 bits are known if clear or set in both the low clear bits
2045 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2046 // low 3 bits clear.
2047 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2048 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2049 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2051 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2052 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2053 KnownZeroOut = std::min(KnownZeroOut,
2054 KnownZero2.countTrailingOnes());
2056 if (Op.getOpcode() == ISD::ADD) {
2057 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2061 // With ADDE, a carry bit may be added in, so we can only use this
2062 // information if we know (at least) that the low two bits are clear. We
2063 // then return to the caller that the low bit is unknown but that other bits
2065 if (KnownZeroOut >= 2) // ADDE
2066 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2070 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2071 const APInt &RA = Rem->getAPIntValue().abs();
2072 if (RA.isPowerOf2()) {
2073 APInt LowBits = RA - 1;
2074 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2075 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2077 // The low bits of the first operand are unchanged by the srem.
2078 KnownZero = KnownZero2 & LowBits;
2079 KnownOne = KnownOne2 & LowBits;
2081 // If the first operand is non-negative or has all low bits zero, then
2082 // the upper bits are all zero.
2083 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2084 KnownZero |= ~LowBits;
2086 // If the first operand is negative and not all low bits are zero, then
2087 // the upper bits are all one.
2088 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2089 KnownOne |= ~LowBits;
2090 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2095 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2096 const APInt &RA = Rem->getAPIntValue();
2097 if (RA.isPowerOf2()) {
2098 APInt LowBits = (RA - 1);
2099 KnownZero |= ~LowBits;
2100 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2101 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2106 // Since the result is less than or equal to either operand, any leading
2107 // zero bits in either operand must also exist in the result.
2108 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2109 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2111 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2112 KnownZero2.countLeadingOnes());
2113 KnownOne.clearAllBits();
2114 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2117 case ISD::FrameIndex:
2118 case ISD::TargetFrameIndex:
2119 if (unsigned Align = InferPtrAlignment(Op)) {
2120 // The low bits are known zero if the pointer is aligned.
2121 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2127 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2130 case ISD::INTRINSIC_WO_CHAIN:
2131 case ISD::INTRINSIC_W_CHAIN:
2132 case ISD::INTRINSIC_VOID:
2133 // Allow the target to implement this method for its nodes.
2134 TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2139 /// ComputeNumSignBits - Return the number of times the sign bit of the
2140 /// register is replicated into the other bits. We know that at least 1 bit
2141 /// is always equal to the sign bit (itself), but other cases can give us
2142 /// information. For example, immediately after an "SRA X, 2", we know that
2143 /// the top 3 bits are all equal to each other, so we return 3.
2144 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2145 EVT VT = Op.getValueType();
2146 assert(VT.isInteger() && "Invalid VT!");
2147 unsigned VTBits = VT.getScalarType().getSizeInBits();
2149 unsigned FirstAnswer = 1;
2152 return 1; // Limit search depth.
2154 switch (Op.getOpcode()) {
2156 case ISD::AssertSext:
2157 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2158 return VTBits-Tmp+1;
2159 case ISD::AssertZext:
2160 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2163 case ISD::Constant: {
2164 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2165 return Val.getNumSignBits();
2168 case ISD::SIGN_EXTEND:
2169 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2170 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2172 case ISD::SIGN_EXTEND_INREG:
2173 // Max of the input and what this extends.
2175 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2178 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2179 return std::max(Tmp, Tmp2);
2182 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2183 // SRA X, C -> adds C sign bits.
2184 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2185 Tmp += C->getZExtValue();
2186 if (Tmp > VTBits) Tmp = VTBits;
2190 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2191 // shl destroys sign bits.
2192 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2193 if (C->getZExtValue() >= VTBits || // Bad shift.
2194 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2195 return Tmp - C->getZExtValue();
2200 case ISD::XOR: // NOT is handled here.
2201 // Logical binary ops preserve the number of sign bits at the worst.
2202 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2204 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2205 FirstAnswer = std::min(Tmp, Tmp2);
2206 // We computed what we know about the sign bits as our first
2207 // answer. Now proceed to the generic code that uses
2208 // ComputeMaskedBits, and pick whichever answer is better.
2213 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2214 if (Tmp == 1) return 1; // Early out.
2215 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2216 return std::min(Tmp, Tmp2);
2224 if (Op.getResNo() != 1)
2226 // The boolean result conforms to getBooleanContents. Fall through.
2228 // If setcc returns 0/-1, all bits are sign bits.
2229 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2230 TargetLowering::ZeroOrNegativeOneBooleanContent)
2235 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2236 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2238 // Handle rotate right by N like a rotate left by 32-N.
2239 if (Op.getOpcode() == ISD::ROTR)
2240 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2242 // If we aren't rotating out all of the known-in sign bits, return the
2243 // number that are left. This handles rotl(sext(x), 1) for example.
2244 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2245 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2249 // Add can have at most one carry bit. Thus we know that the output
2250 // is, at worst, one more bit than the inputs.
2251 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2252 if (Tmp == 1) return 1; // Early out.
2254 // Special case decrementing a value (ADD X, -1):
2255 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2256 if (CRHS->isAllOnesValue()) {
2257 APInt KnownZero, KnownOne;
2258 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2260 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2262 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2265 // If we are subtracting one from a positive number, there is no carry
2266 // out of the result.
2267 if (KnownZero.isNegative())
2271 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2272 if (Tmp2 == 1) return 1;
2273 return std::min(Tmp, Tmp2)-1;
2276 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2277 if (Tmp2 == 1) return 1;
2280 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2281 if (CLHS->isNullValue()) {
2282 APInt KnownZero, KnownOne;
2283 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2284 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2286 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2289 // If the input is known to be positive (the sign bit is known clear),
2290 // the output of the NEG has the same number of sign bits as the input.
2291 if (KnownZero.isNegative())
2294 // Otherwise, we treat this like a SUB.
2297 // Sub can have at most one carry bit. Thus we know that the output
2298 // is, at worst, one more bit than the inputs.
2299 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2300 if (Tmp == 1) return 1; // Early out.
2301 return std::min(Tmp, Tmp2)-1;
2303 // FIXME: it's tricky to do anything useful for this, but it is an important
2304 // case for targets like X86.
2308 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2309 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2310 unsigned ExtType = LD->getExtensionType();
2313 case ISD::SEXTLOAD: // '17' bits known
2314 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2315 return VTBits-Tmp+1;
2316 case ISD::ZEXTLOAD: // '16' bits known
2317 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2322 // Allow the target to implement this method for its nodes.
2323 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2324 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2325 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2326 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2327 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2328 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2331 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2332 // use this information.
2333 APInt KnownZero, KnownOne;
2334 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2337 if (KnownZero.isNegative()) { // sign bit is 0
2339 } else if (KnownOne.isNegative()) { // sign bit is 1;
2346 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2347 // the number of identical bits in the top of the input value.
2349 Mask <<= Mask.getBitWidth()-VTBits;
2350 // Return # leading zeros. We use 'min' here in case Val was zero before
2351 // shifting. We don't want to return '64' as for an i32 "0".
2352 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2355 /// isBaseWithConstantOffset - Return true if the specified operand is an
2356 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2357 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2358 /// semantics as an ADD. This handles the equivalence:
2359 /// X|Cst == X+Cst iff X&Cst = 0.
2360 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2361 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2362 !isa<ConstantSDNode>(Op.getOperand(1)))
2365 if (Op.getOpcode() == ISD::OR &&
2366 !MaskedValueIsZero(Op.getOperand(0),
2367 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2374 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2375 // If we're told that NaNs won't happen, assume they won't.
2376 if (getTarget().Options.NoNaNsFPMath)
2379 // If the value is a constant, we can obviously see if it is a NaN or not.
2380 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2381 return !C->getValueAPF().isNaN();
2383 // TODO: Recognize more cases here.
2388 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2389 // If the value is a constant, we can obviously see if it is a zero or not.
2390 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2391 return !C->isZero();
2393 // TODO: Recognize more cases here.
2394 switch (Op.getOpcode()) {
2397 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2398 return !C->isNullValue();
2405 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2406 // Check the obvious case.
2407 if (A == B) return true;
2409 // For for negative and positive zero.
2410 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2411 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2412 if (CA->isZero() && CB->isZero()) return true;
2414 // Otherwise they may not be equal.
2418 /// getNode - Gets or creates the specified node.
2420 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2421 FoldingSetNodeID ID;
2422 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2424 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2425 return SDValue(E, 0);
2427 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2428 CSEMap.InsertNode(N, IP);
2430 AllNodes.push_back(N);
2434 return SDValue(N, 0);
2437 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2438 EVT VT, SDValue Operand) {
2439 // Constant fold unary operations with an integer constant operand.
2440 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2441 const APInt &Val = C->getAPIntValue();
2444 case ISD::SIGN_EXTEND:
2445 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2446 case ISD::ANY_EXTEND:
2447 case ISD::ZERO_EXTEND:
2449 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2450 case ISD::UINT_TO_FP:
2451 case ISD::SINT_TO_FP: {
2452 // No compile time operations on ppcf128.
2453 if (VT == MVT::ppcf128) break;
2454 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2455 (void)apf.convertFromAPInt(Val,
2456 Opcode==ISD::SINT_TO_FP,
2457 APFloat::rmNearestTiesToEven);
2458 return getConstantFP(apf, VT);
2461 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2462 return getConstantFP(APFloat(Val), VT);
2463 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2464 return getConstantFP(APFloat(Val), VT);
2467 return getConstant(Val.byteSwap(), VT);
2469 return getConstant(Val.countPopulation(), VT);
2471 case ISD::CTLZ_ZERO_UNDEF:
2472 return getConstant(Val.countLeadingZeros(), VT);
2474 case ISD::CTTZ_ZERO_UNDEF:
2475 return getConstant(Val.countTrailingZeros(), VT);
2479 // Constant fold unary operations with a floating point constant operand.
2480 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2481 APFloat V = C->getValueAPF(); // make copy
2482 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2486 return getConstantFP(V, VT);
2489 return getConstantFP(V, VT);
2491 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2492 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2493 return getConstantFP(V, VT);
2497 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2498 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2499 return getConstantFP(V, VT);
2503 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2504 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2505 return getConstantFP(V, VT);
2508 case ISD::FP_EXTEND: {
2510 // This can return overflow, underflow, or inexact; we don't care.
2511 // FIXME need to be more flexible about rounding mode.
2512 (void)V.convert(*EVTToAPFloatSemantics(VT),
2513 APFloat::rmNearestTiesToEven, &ignored);
2514 return getConstantFP(V, VT);
2516 case ISD::FP_TO_SINT:
2517 case ISD::FP_TO_UINT: {
2520 assert(integerPartWidth >= 64);
2521 // FIXME need to be more flexible about rounding mode.
2522 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2523 Opcode==ISD::FP_TO_SINT,
2524 APFloat::rmTowardZero, &ignored);
2525 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2527 APInt api(VT.getSizeInBits(), x);
2528 return getConstant(api, VT);
2531 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2532 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2533 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2534 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2540 unsigned OpOpcode = Operand.getNode()->getOpcode();
2542 case ISD::TokenFactor:
2543 case ISD::MERGE_VALUES:
2544 case ISD::CONCAT_VECTORS:
2545 return Operand; // Factor, merge or concat of one node? No need.
2546 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2547 case ISD::FP_EXTEND:
2548 assert(VT.isFloatingPoint() &&
2549 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2550 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2551 assert((!VT.isVector() ||
2552 VT.getVectorNumElements() ==
2553 Operand.getValueType().getVectorNumElements()) &&
2554 "Vector element count mismatch!");
2555 if (Operand.getOpcode() == ISD::UNDEF)
2556 return getUNDEF(VT);
2558 case ISD::SIGN_EXTEND:
2559 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2560 "Invalid SIGN_EXTEND!");
2561 if (Operand.getValueType() == VT) return Operand; // noop extension
2562 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2563 "Invalid sext node, dst < src!");
2564 assert((!VT.isVector() ||
2565 VT.getVectorNumElements() ==
2566 Operand.getValueType().getVectorNumElements()) &&
2567 "Vector element count mismatch!");
2568 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2569 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2570 else if (OpOpcode == ISD::UNDEF)
2571 // sext(undef) = 0, because the top bits will all be the same.
2572 return getConstant(0, VT);
2574 case ISD::ZERO_EXTEND:
2575 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2576 "Invalid ZERO_EXTEND!");
2577 if (Operand.getValueType() == VT) return Operand; // noop extension
2578 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2579 "Invalid zext node, dst < src!");
2580 assert((!VT.isVector() ||
2581 VT.getVectorNumElements() ==
2582 Operand.getValueType().getVectorNumElements()) &&
2583 "Vector element count mismatch!");
2584 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2585 return getNode(ISD::ZERO_EXTEND, DL, VT,
2586 Operand.getNode()->getOperand(0));
2587 else if (OpOpcode == ISD::UNDEF)
2588 // zext(undef) = 0, because the top bits will be zero.
2589 return getConstant(0, VT);
2591 case ISD::ANY_EXTEND:
2592 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2593 "Invalid ANY_EXTEND!");
2594 if (Operand.getValueType() == VT) return Operand; // noop extension
2595 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2596 "Invalid anyext node, dst < src!");
2597 assert((!VT.isVector() ||
2598 VT.getVectorNumElements() ==
2599 Operand.getValueType().getVectorNumElements()) &&
2600 "Vector element count mismatch!");
2602 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2603 OpOpcode == ISD::ANY_EXTEND)
2604 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2605 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2606 else if (OpOpcode == ISD::UNDEF)
2607 return getUNDEF(VT);
2609 // (ext (trunx x)) -> x
2610 if (OpOpcode == ISD::TRUNCATE) {
2611 SDValue OpOp = Operand.getNode()->getOperand(0);
2612 if (OpOp.getValueType() == VT)
2617 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2618 "Invalid TRUNCATE!");
2619 if (Operand.getValueType() == VT) return Operand; // noop truncate
2620 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2621 "Invalid truncate node, src < dst!");
2622 assert((!VT.isVector() ||
2623 VT.getVectorNumElements() ==
2624 Operand.getValueType().getVectorNumElements()) &&
2625 "Vector element count mismatch!");
2626 if (OpOpcode == ISD::TRUNCATE)
2627 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2628 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2629 OpOpcode == ISD::ANY_EXTEND) {
2630 // If the source is smaller than the dest, we still need an extend.
2631 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2632 .bitsLT(VT.getScalarType()))
2633 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2634 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2635 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2636 return Operand.getNode()->getOperand(0);
2638 if (OpOpcode == ISD::UNDEF)
2639 return getUNDEF(VT);
2642 // Basic sanity checking.
2643 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2644 && "Cannot BITCAST between types of different sizes!");
2645 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2646 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2647 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2648 if (OpOpcode == ISD::UNDEF)
2649 return getUNDEF(VT);
2651 case ISD::SCALAR_TO_VECTOR:
2652 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2653 (VT.getVectorElementType() == Operand.getValueType() ||
2654 (VT.getVectorElementType().isInteger() &&
2655 Operand.getValueType().isInteger() &&
2656 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2657 "Illegal SCALAR_TO_VECTOR node!");
2658 if (OpOpcode == ISD::UNDEF)
2659 return getUNDEF(VT);
2660 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2661 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2662 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2663 Operand.getConstantOperandVal(1) == 0 &&
2664 Operand.getOperand(0).getValueType() == VT)
2665 return Operand.getOperand(0);
2668 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2669 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2670 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2671 Operand.getNode()->getOperand(0));
2672 if (OpOpcode == ISD::FNEG) // --X -> X
2673 return Operand.getNode()->getOperand(0);
2676 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2677 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2682 SDVTList VTs = getVTList(VT);
2683 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2684 FoldingSetNodeID ID;
2685 SDValue Ops[1] = { Operand };
2686 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2688 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2689 return SDValue(E, 0);
2691 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2692 CSEMap.InsertNode(N, IP);
2694 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2697 AllNodes.push_back(N);
2701 return SDValue(N, 0);
2704 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2706 ConstantSDNode *Cst1,
2707 ConstantSDNode *Cst2) {
2708 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2711 case ISD::ADD: return getConstant(C1 + C2, VT);
2712 case ISD::SUB: return getConstant(C1 - C2, VT);
2713 case ISD::MUL: return getConstant(C1 * C2, VT);
2715 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2718 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2721 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2724 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2726 case ISD::AND: return getConstant(C1 & C2, VT);
2727 case ISD::OR: return getConstant(C1 | C2, VT);
2728 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2729 case ISD::SHL: return getConstant(C1 << C2, VT);
2730 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2731 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2732 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2733 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2740 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2741 SDValue N1, SDValue N2) {
2742 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2743 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2746 case ISD::TokenFactor:
2747 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2748 N2.getValueType() == MVT::Other && "Invalid token factor!");
2749 // Fold trivial token factors.
2750 if (N1.getOpcode() == ISD::EntryToken) return N2;
2751 if (N2.getOpcode() == ISD::EntryToken) return N1;
2752 if (N1 == N2) return N1;
2754 case ISD::CONCAT_VECTORS:
2755 // Concat of UNDEFs is UNDEF.
2756 if (N1.getOpcode() == ISD::UNDEF &&
2757 N2.getOpcode() == ISD::UNDEF)
2758 return getUNDEF(VT);
2760 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2761 // one big BUILD_VECTOR.
2762 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2763 N2.getOpcode() == ISD::BUILD_VECTOR) {
2764 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2765 N1.getNode()->op_end());
2766 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2767 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2771 assert(VT.isInteger() && "This operator does not apply to FP types!");
2772 assert(N1.getValueType() == N2.getValueType() &&
2773 N1.getValueType() == VT && "Binary operator types must match!");
2774 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2775 // worth handling here.
2776 if (N2C && N2C->isNullValue())
2778 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2785 assert(VT.isInteger() && "This operator does not apply to FP types!");
2786 assert(N1.getValueType() == N2.getValueType() &&
2787 N1.getValueType() == VT && "Binary operator types must match!");
2788 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2789 // it's worth handling here.
2790 if (N2C && N2C->isNullValue())
2800 assert(VT.isInteger() && "This operator does not apply to FP types!");
2801 assert(N1.getValueType() == N2.getValueType() &&
2802 N1.getValueType() == VT && "Binary operator types must match!");
2809 if (getTarget().Options.UnsafeFPMath) {
2810 if (Opcode == ISD::FADD) {
2812 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2813 if (CFP->getValueAPF().isZero())
2816 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2817 if (CFP->getValueAPF().isZero())
2819 } else if (Opcode == ISD::FSUB) {
2821 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2822 if (CFP->getValueAPF().isZero())
2824 } else if (Opcode == ISD::FMUL) {
2825 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2828 // If the first operand isn't the constant, try the second
2830 CFP = dyn_cast<ConstantFPSDNode>(N2);
2837 return SDValue(CFP,0);
2839 if (CFP->isExactlyValue(1.0))
2844 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2845 assert(N1.getValueType() == N2.getValueType() &&
2846 N1.getValueType() == VT && "Binary operator types must match!");
2848 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2849 assert(N1.getValueType() == VT &&
2850 N1.getValueType().isFloatingPoint() &&
2851 N2.getValueType().isFloatingPoint() &&
2852 "Invalid FCOPYSIGN!");
2859 assert(VT == N1.getValueType() &&
2860 "Shift operators return type must be the same as their first arg");
2861 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2862 "Shifts only work on integers");
2863 // Verify that the shift amount VT is bit enough to hold valid shift
2864 // amounts. This catches things like trying to shift an i1024 value by an
2865 // i8, which is easy to fall into in generic code that uses
2866 // TLI.getShiftAmount().
2867 assert(N2.getValueType().getSizeInBits() >=
2868 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2869 "Invalid use of small shift amount with oversized value!");
2871 // Always fold shifts of i1 values so the code generator doesn't need to
2872 // handle them. Since we know the size of the shift has to be less than the
2873 // size of the value, the shift/rotate count is guaranteed to be zero.
2876 if (N2C && N2C->isNullValue())
2879 case ISD::FP_ROUND_INREG: {
2880 EVT EVT = cast<VTSDNode>(N2)->getVT();
2881 assert(VT == N1.getValueType() && "Not an inreg round!");
2882 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2883 "Cannot FP_ROUND_INREG integer types");
2884 assert(EVT.isVector() == VT.isVector() &&
2885 "FP_ROUND_INREG type should be vector iff the operand "
2887 assert((!EVT.isVector() ||
2888 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2889 "Vector element counts must match in FP_ROUND_INREG");
2890 assert(EVT.bitsLE(VT) && "Not rounding down!");
2892 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2896 assert(VT.isFloatingPoint() &&
2897 N1.getValueType().isFloatingPoint() &&
2898 VT.bitsLE(N1.getValueType()) &&
2899 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2900 if (N1.getValueType() == VT) return N1; // noop conversion.
2902 case ISD::AssertSext:
2903 case ISD::AssertZext: {
2904 EVT EVT = cast<VTSDNode>(N2)->getVT();
2905 assert(VT == N1.getValueType() && "Not an inreg extend!");
2906 assert(VT.isInteger() && EVT.isInteger() &&
2907 "Cannot *_EXTEND_INREG FP types");
2908 assert(!EVT.isVector() &&
2909 "AssertSExt/AssertZExt type should be the vector element type "
2910 "rather than the vector type!");
2911 assert(EVT.bitsLE(VT) && "Not extending!");
2912 if (VT == EVT) return N1; // noop assertion.
2915 case ISD::SIGN_EXTEND_INREG: {
2916 EVT EVT = cast<VTSDNode>(N2)->getVT();
2917 assert(VT == N1.getValueType() && "Not an inreg extend!");
2918 assert(VT.isInteger() && EVT.isInteger() &&
2919 "Cannot *_EXTEND_INREG FP types");
2920 assert(EVT.isVector() == VT.isVector() &&
2921 "SIGN_EXTEND_INREG type should be vector iff the operand "
2923 assert((!EVT.isVector() ||
2924 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2925 "Vector element counts must match in SIGN_EXTEND_INREG");
2926 assert(EVT.bitsLE(VT) && "Not extending!");
2927 if (EVT == VT) return N1; // Not actually extending
2930 APInt Val = N1C->getAPIntValue();
2931 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2932 Val <<= Val.getBitWidth()-FromBits;
2933 Val = Val.ashr(Val.getBitWidth()-FromBits);
2934 return getConstant(Val, VT);
2938 case ISD::EXTRACT_VECTOR_ELT:
2939 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2940 if (N1.getOpcode() == ISD::UNDEF)
2941 return getUNDEF(VT);
2943 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2944 // expanding copies of large vectors from registers.
2946 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2947 N1.getNumOperands() > 0) {
2949 N1.getOperand(0).getValueType().getVectorNumElements();
2950 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2951 N1.getOperand(N2C->getZExtValue() / Factor),
2952 getConstant(N2C->getZExtValue() % Factor,
2953 N2.getValueType()));
2956 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2957 // expanding large vector constants.
2958 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2959 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2961 if (VT != Elt.getValueType())
2962 // If the vector element type is not legal, the BUILD_VECTOR operands
2963 // are promoted and implicitly truncated, and the result implicitly
2964 // extended. Make that explicit here.
2965 Elt = getAnyExtOrTrunc(Elt, DL, VT);
2970 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2971 // operations are lowered to scalars.
2972 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2973 // If the indices are the same, return the inserted element else
2974 // if the indices are known different, extract the element from
2975 // the original vector.
2976 SDValue N1Op2 = N1.getOperand(2);
2977 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2979 if (N1Op2C && N2C) {
2980 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2981 if (VT == N1.getOperand(1).getValueType())
2982 return N1.getOperand(1);
2984 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2987 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2991 case ISD::EXTRACT_ELEMENT:
2992 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2993 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2994 (N1.getValueType().isInteger() == VT.isInteger()) &&
2995 N1.getValueType() != VT &&
2996 "Wrong types for EXTRACT_ELEMENT!");
2998 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2999 // 64-bit integers into 32-bit parts. Instead of building the extract of
3000 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3001 if (N1.getOpcode() == ISD::BUILD_PAIR)
3002 return N1.getOperand(N2C->getZExtValue());
3004 // EXTRACT_ELEMENT of a constant int is also very common.
3005 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3006 unsigned ElementSize = VT.getSizeInBits();
3007 unsigned Shift = ElementSize * N2C->getZExtValue();
3008 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3009 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3012 case ISD::EXTRACT_SUBVECTOR: {
3014 if (VT.isSimple() && N1.getValueType().isSimple()) {
3015 assert(VT.isVector() && N1.getValueType().isVector() &&
3016 "Extract subvector VTs must be a vectors!");
3017 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
3018 "Extract subvector VTs must have the same element type!");
3019 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3020 "Extract subvector must be from larger vector to smaller vector!");
3022 if (isa<ConstantSDNode>(Index.getNode())) {
3023 assert((VT.getVectorNumElements() +
3024 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3025 <= N1.getValueType().getVectorNumElements())
3026 && "Extract subvector overflow!");
3029 // Trivial extraction.
3030 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
3039 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
3040 if (SV.getNode()) return SV;
3041 } else { // Cannonicalize constant to RHS if commutative
3042 if (isCommutativeBinOp(Opcode)) {
3043 std::swap(N1C, N2C);
3049 // Constant fold FP operations.
3050 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3051 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3053 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3054 // Cannonicalize constant to RHS if commutative
3055 std::swap(N1CFP, N2CFP);
3057 } else if (N2CFP && VT != MVT::ppcf128) {
3058 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3059 APFloat::opStatus s;
3062 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3063 if (s != APFloat::opInvalidOp)
3064 return getConstantFP(V1, VT);
3067 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3068 if (s!=APFloat::opInvalidOp)
3069 return getConstantFP(V1, VT);
3072 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3073 if (s!=APFloat::opInvalidOp)
3074 return getConstantFP(V1, VT);
3077 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3078 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3079 return getConstantFP(V1, VT);
3082 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3083 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3084 return getConstantFP(V1, VT);
3086 case ISD::FCOPYSIGN:
3088 return getConstantFP(V1, VT);
3093 if (Opcode == ISD::FP_ROUND) {
3094 APFloat V = N1CFP->getValueAPF(); // make copy
3096 // This can return overflow, underflow, or inexact; we don't care.
3097 // FIXME need to be more flexible about rounding mode.
3098 (void)V.convert(*EVTToAPFloatSemantics(VT),
3099 APFloat::rmNearestTiesToEven, &ignored);
3100 return getConstantFP(V, VT);
3104 // Canonicalize an UNDEF to the RHS, even over a constant.
3105 if (N1.getOpcode() == ISD::UNDEF) {
3106 if (isCommutativeBinOp(Opcode)) {
3110 case ISD::FP_ROUND_INREG:
3111 case ISD::SIGN_EXTEND_INREG:
3117 return N1; // fold op(undef, arg2) -> undef
3125 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3126 // For vectors, we can't easily build an all zero vector, just return
3133 // Fold a bunch of operators when the RHS is undef.
3134 if (N2.getOpcode() == ISD::UNDEF) {
3137 if (N1.getOpcode() == ISD::UNDEF)
3138 // Handle undef ^ undef -> 0 special case. This is a common
3140 return getConstant(0, VT);
3150 return N2; // fold op(arg1, undef) -> undef
3156 if (getTarget().Options.UnsafeFPMath)
3164 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3165 // For vectors, we can't easily build an all zero vector, just return
3170 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3171 // For vectors, we can't easily build an all one vector, just return
3179 // Memoize this node if possible.
3181 SDVTList VTs = getVTList(VT);
3182 if (VT != MVT::Glue) {
3183 SDValue Ops[] = { N1, N2 };
3184 FoldingSetNodeID ID;
3185 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3187 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3188 return SDValue(E, 0);
3190 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3191 CSEMap.InsertNode(N, IP);
3193 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3196 AllNodes.push_back(N);
3200 return SDValue(N, 0);
3203 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3204 SDValue N1, SDValue N2, SDValue N3) {
3205 // Perform various simplifications.
3206 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3208 case ISD::CONCAT_VECTORS:
3209 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3210 // one big BUILD_VECTOR.
3211 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3212 N2.getOpcode() == ISD::BUILD_VECTOR &&
3213 N3.getOpcode() == ISD::BUILD_VECTOR) {
3214 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3215 N1.getNode()->op_end());
3216 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3217 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3218 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3222 // Use FoldSetCC to simplify SETCC's.
3223 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3224 if (Simp.getNode()) return Simp;
3229 if (N1C->getZExtValue())
3230 return N2; // select true, X, Y -> X
3231 return N3; // select false, X, Y -> Y
3234 if (N2 == N3) return N2; // select C, X, X -> X
3236 case ISD::VECTOR_SHUFFLE:
3237 llvm_unreachable("should use getVectorShuffle constructor!");
3238 case ISD::INSERT_SUBVECTOR: {
3240 if (VT.isSimple() && N1.getValueType().isSimple()
3241 && N2.getValueType().isSimple()) {
3242 assert(VT.isVector() && N1.getValueType().isVector() &&
3243 N2.getValueType().isVector() &&
3244 "Insert subvector VTs must be a vectors");
3245 assert(VT == N1.getValueType() &&
3246 "Dest and insert subvector source types must match!");
3247 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3248 "Insert subvector must be from smaller vector to larger vector!");
3249 if (isa<ConstantSDNode>(Index.getNode())) {
3250 assert((N2.getValueType().getVectorNumElements() +
3251 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3252 <= VT.getVectorNumElements())
3253 && "Insert subvector overflow!");
3256 // Trivial insertion.
3257 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3263 // Fold bit_convert nodes from a type to themselves.
3264 if (N1.getValueType() == VT)
3269 // Memoize node if it doesn't produce a flag.
3271 SDVTList VTs = getVTList(VT);
3272 if (VT != MVT::Glue) {
3273 SDValue Ops[] = { N1, N2, N3 };
3274 FoldingSetNodeID ID;
3275 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3277 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3278 return SDValue(E, 0);
3280 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3281 CSEMap.InsertNode(N, IP);
3283 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3286 AllNodes.push_back(N);
3290 return SDValue(N, 0);
3293 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3294 SDValue N1, SDValue N2, SDValue N3,
3296 SDValue Ops[] = { N1, N2, N3, N4 };
3297 return getNode(Opcode, DL, VT, Ops, 4);
3300 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3301 SDValue N1, SDValue N2, SDValue N3,
3302 SDValue N4, SDValue N5) {
3303 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3304 return getNode(Opcode, DL, VT, Ops, 5);
3307 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3308 /// the incoming stack arguments to be loaded from the stack.
3309 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3310 SmallVector<SDValue, 8> ArgChains;
3312 // Include the original chain at the beginning of the list. When this is
3313 // used by target LowerCall hooks, this helps legalize find the
3314 // CALLSEQ_BEGIN node.
3315 ArgChains.push_back(Chain);
3317 // Add a chain value for each stack argument.
3318 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3319 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3320 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3321 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3322 if (FI->getIndex() < 0)
3323 ArgChains.push_back(SDValue(L, 1));
3325 // Build a tokenfactor for all the chains.
3326 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3327 &ArgChains[0], ArgChains.size());
3330 /// SplatByte - Distribute ByteVal over NumBits bits.
3331 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3332 APInt Val = APInt(NumBits, ByteVal);
3334 for (unsigned i = NumBits; i > 8; i >>= 1) {
3335 Val = (Val << Shift) | Val;
3341 /// getMemsetValue - Vectorized representation of the memset value
3343 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3345 assert(Value.getOpcode() != ISD::UNDEF);
3347 unsigned NumBits = VT.getScalarType().getSizeInBits();
3348 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3349 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3351 return DAG.getConstant(Val, VT);
3352 return DAG.getConstantFP(APFloat(Val), VT);
3355 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3357 // Use a multiplication with 0x010101... to extend the input to the
3359 APInt Magic = SplatByte(NumBits, 0x01);
3360 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3366 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3367 /// used when a memcpy is turned into a memset when the source is a constant
3369 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3370 const TargetLowering &TLI, StringRef Str) {
3371 // Handle vector with all elements zero.
3374 return DAG.getConstant(0, VT);
3375 else if (VT == MVT::f32 || VT == MVT::f64)
3376 return DAG.getConstantFP(0.0, VT);
3377 else if (VT.isVector()) {
3378 unsigned NumElts = VT.getVectorNumElements();
3379 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3380 return DAG.getNode(ISD::BITCAST, dl, VT,
3381 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3384 llvm_unreachable("Expected type!");
3387 assert(!VT.isVector() && "Can't handle vector type here!");
3388 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3389 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3392 if (TLI.isLittleEndian()) {
3393 for (unsigned i = 0; i != NumBytes; ++i)
3394 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3396 for (unsigned i = 0; i != NumBytes; ++i)
3397 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3400 return DAG.getConstant(Val, VT);
3403 /// getMemBasePlusOffset - Returns base and offset node for the
3405 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3406 SelectionDAG &DAG) {
3407 EVT VT = Base.getValueType();
3408 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3409 VT, Base, DAG.getConstant(Offset, VT));
3412 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3414 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3415 unsigned SrcDelta = 0;
3416 GlobalAddressSDNode *G = NULL;
3417 if (Src.getOpcode() == ISD::GlobalAddress)
3418 G = cast<GlobalAddressSDNode>(Src);
3419 else if (Src.getOpcode() == ISD::ADD &&
3420 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3421 Src.getOperand(1).getOpcode() == ISD::Constant) {
3422 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3423 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3428 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3431 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3432 /// to replace the memset / memcpy. Return true if the number of memory ops
3433 /// is below the threshold. It returns the types of the sequence of
3434 /// memory ops to perform memset / memcpy by reference.
3435 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3436 unsigned Limit, uint64_t Size,
3437 unsigned DstAlign, unsigned SrcAlign,
3441 const TargetLowering &TLI) {
3442 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3443 "Expecting memcpy / memset source to meet alignment requirement!");
3444 // If 'SrcAlign' is zero, that means the memory operation does not need to
3445 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3446 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3447 // is the specified alignment of the memory operation. If it is zero, that
3448 // means it's possible to change the alignment of the destination.
3449 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3450 // not need to be loaded.
3451 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3452 IsZeroVal, MemcpyStrSrc,
3453 DAG.getMachineFunction());
3455 if (VT == MVT::Other) {
3456 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3457 TLI.allowsUnalignedMemoryAccesses(VT)) {
3458 VT = TLI.getPointerTy();
3460 switch (DstAlign & 7) {
3461 case 0: VT = MVT::i64; break;
3462 case 4: VT = MVT::i32; break;
3463 case 2: VT = MVT::i16; break;
3464 default: VT = MVT::i8; break;
3469 while (!TLI.isTypeLegal(LVT))
3470 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3471 assert(LVT.isInteger());
3477 unsigned NumMemOps = 0;
3479 unsigned VTSize = VT.getSizeInBits() / 8;
3480 while (VTSize > Size) {
3481 // For now, only use non-vector load / store's for the left-over pieces.
3482 if (VT.isVector() || VT.isFloatingPoint()) {
3484 while (!TLI.isTypeLegal(VT))
3485 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3486 VTSize = VT.getSizeInBits() / 8;
3488 // This can result in a type that is not legal on the target, e.g.
3489 // 1 or 2 bytes on PPC.
3490 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3495 if (++NumMemOps > Limit)
3497 MemOps.push_back(VT);
3504 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3505 SDValue Chain, SDValue Dst,
3506 SDValue Src, uint64_t Size,
3507 unsigned Align, bool isVol,
3509 MachinePointerInfo DstPtrInfo,
3510 MachinePointerInfo SrcPtrInfo) {
3511 // Turn a memcpy of undef to nop.
3512 if (Src.getOpcode() == ISD::UNDEF)
3515 // Expand memcpy to a series of load and store ops if the size operand falls
3516 // below a certain threshold.
3517 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3518 // rather than maybe a humongous number of loads and stores.
3519 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3520 std::vector<EVT> MemOps;
3521 bool DstAlignCanChange = false;
3522 MachineFunction &MF = DAG.getMachineFunction();
3523 MachineFrameInfo *MFI = MF.getFrameInfo();
3524 bool OptSize = MF.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3525 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3526 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3527 DstAlignCanChange = true;
3528 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3529 if (Align > SrcAlign)
3532 bool CopyFromStr = isMemSrcFromString(Src, Str);
3533 bool isZeroStr = CopyFromStr && Str.empty();
3534 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3536 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3537 (DstAlignCanChange ? 0 : Align),
3538 (isZeroStr ? 0 : SrcAlign),
3539 true, CopyFromStr, DAG, TLI))
3542 if (DstAlignCanChange) {
3543 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3544 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3545 if (NewAlign > Align) {
3546 // Give the stack frame object a larger alignment if needed.
3547 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3548 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3553 SmallVector<SDValue, 8> OutChains;
3554 unsigned NumMemOps = MemOps.size();
3555 uint64_t SrcOff = 0, DstOff = 0;
3556 for (unsigned i = 0; i != NumMemOps; ++i) {
3558 unsigned VTSize = VT.getSizeInBits() / 8;
3559 SDValue Value, Store;
3562 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3563 // It's unlikely a store of a vector immediate can be done in a single
3564 // instruction. It would require a load from a constantpool first.
3565 // We only handle zero vectors here.
3566 // FIXME: Handle other cases where store of vector immediate is done in
3567 // a single instruction.
3568 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3569 Store = DAG.getStore(Chain, dl, Value,
3570 getMemBasePlusOffset(Dst, DstOff, DAG),
3571 DstPtrInfo.getWithOffset(DstOff), isVol,
3574 // The type might not be legal for the target. This should only happen
3575 // if the type is smaller than a legal type, as on PPC, so the right
3576 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3577 // to Load/Store if NVT==VT.
3578 // FIXME does the case above also need this?
3579 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3580 assert(NVT.bitsGE(VT));
3581 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3582 getMemBasePlusOffset(Src, SrcOff, DAG),
3583 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3584 MinAlign(SrcAlign, SrcOff));
3585 Store = DAG.getTruncStore(Chain, dl, Value,
3586 getMemBasePlusOffset(Dst, DstOff, DAG),
3587 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3590 OutChains.push_back(Store);
3595 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3596 &OutChains[0], OutChains.size());
3599 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3600 SDValue Chain, SDValue Dst,
3601 SDValue Src, uint64_t Size,
3602 unsigned Align, bool isVol,
3604 MachinePointerInfo DstPtrInfo,
3605 MachinePointerInfo SrcPtrInfo) {
3606 // Turn a memmove of undef to nop.
3607 if (Src.getOpcode() == ISD::UNDEF)
3610 // Expand memmove to a series of load and store ops if the size operand falls
3611 // below a certain threshold.
3612 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3613 std::vector<EVT> MemOps;
3614 bool DstAlignCanChange = false;
3615 MachineFunction &MF = DAG.getMachineFunction();
3616 MachineFrameInfo *MFI = MF.getFrameInfo();
3617 bool OptSize = MF.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3618 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3619 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3620 DstAlignCanChange = true;
3621 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3622 if (Align > SrcAlign)
3624 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3626 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3627 (DstAlignCanChange ? 0 : Align),
3628 SrcAlign, true, false, DAG, TLI))
3631 if (DstAlignCanChange) {
3632 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3633 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3634 if (NewAlign > Align) {
3635 // Give the stack frame object a larger alignment if needed.
3636 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3637 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3642 uint64_t SrcOff = 0, DstOff = 0;
3643 SmallVector<SDValue, 8> LoadValues;
3644 SmallVector<SDValue, 8> LoadChains;
3645 SmallVector<SDValue, 8> OutChains;
3646 unsigned NumMemOps = MemOps.size();
3647 for (unsigned i = 0; i < NumMemOps; i++) {
3649 unsigned VTSize = VT.getSizeInBits() / 8;
3650 SDValue Value, Store;
3652 Value = DAG.getLoad(VT, dl, Chain,
3653 getMemBasePlusOffset(Src, SrcOff, DAG),
3654 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3655 false, false, SrcAlign);
3656 LoadValues.push_back(Value);
3657 LoadChains.push_back(Value.getValue(1));
3660 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3661 &LoadChains[0], LoadChains.size());
3663 for (unsigned i = 0; i < NumMemOps; i++) {
3665 unsigned VTSize = VT.getSizeInBits() / 8;
3666 SDValue Value, Store;
3668 Store = DAG.getStore(Chain, dl, LoadValues[i],
3669 getMemBasePlusOffset(Dst, DstOff, DAG),
3670 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3671 OutChains.push_back(Store);
3675 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3676 &OutChains[0], OutChains.size());
3679 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3680 SDValue Chain, SDValue Dst,
3681 SDValue Src, uint64_t Size,
3682 unsigned Align, bool isVol,
3683 MachinePointerInfo DstPtrInfo) {
3684 // Turn a memset of undef to nop.
3685 if (Src.getOpcode() == ISD::UNDEF)
3688 // Expand memset to a series of load/store ops if the size operand
3689 // falls below a certain threshold.
3690 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3691 std::vector<EVT> MemOps;
3692 bool DstAlignCanChange = false;
3693 MachineFunction &MF = DAG.getMachineFunction();
3694 MachineFrameInfo *MFI = MF.getFrameInfo();
3695 bool OptSize = MF.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3696 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3697 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3698 DstAlignCanChange = true;
3700 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3701 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3702 Size, (DstAlignCanChange ? 0 : Align), 0,
3703 IsZeroVal, false, DAG, TLI))
3706 if (DstAlignCanChange) {
3707 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3708 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3709 if (NewAlign > Align) {
3710 // Give the stack frame object a larger alignment if needed.
3711 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3712 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3717 SmallVector<SDValue, 8> OutChains;
3718 uint64_t DstOff = 0;
3719 unsigned NumMemOps = MemOps.size();
3721 // Find the largest store and generate the bit pattern for it.
3722 EVT LargestVT = MemOps[0];
3723 for (unsigned i = 1; i < NumMemOps; i++)
3724 if (MemOps[i].bitsGT(LargestVT))
3725 LargestVT = MemOps[i];
3726 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3728 for (unsigned i = 0; i < NumMemOps; i++) {
3731 // If this store is smaller than the largest store see whether we can get
3732 // the smaller value for free with a truncate.
3733 SDValue Value = MemSetValue;
3734 if (VT.bitsLT(LargestVT)) {
3735 if (!LargestVT.isVector() && !VT.isVector() &&
3736 TLI.isTruncateFree(LargestVT, VT))
3737 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3739 Value = getMemsetValue(Src, VT, DAG, dl);
3741 assert(Value.getValueType() == VT && "Value with wrong type.");
3742 SDValue Store = DAG.getStore(Chain, dl, Value,
3743 getMemBasePlusOffset(Dst, DstOff, DAG),
3744 DstPtrInfo.getWithOffset(DstOff),
3745 isVol, false, Align);
3746 OutChains.push_back(Store);
3747 DstOff += VT.getSizeInBits() / 8;
3750 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3751 &OutChains[0], OutChains.size());
3754 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3755 SDValue Src, SDValue Size,
3756 unsigned Align, bool isVol, bool AlwaysInline,
3757 MachinePointerInfo DstPtrInfo,
3758 MachinePointerInfo SrcPtrInfo) {
3760 // Check to see if we should lower the memcpy to loads and stores first.
3761 // For cases within the target-specified limits, this is the best choice.
3762 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3764 // Memcpy with size zero? Just return the original chain.
3765 if (ConstantSize->isNullValue())
3768 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3769 ConstantSize->getZExtValue(),Align,
3770 isVol, false, DstPtrInfo, SrcPtrInfo);
3771 if (Result.getNode())
3775 // Then check to see if we should lower the memcpy with target-specific
3776 // code. If the target chooses to do this, this is the next best.
3778 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3779 isVol, AlwaysInline,
3780 DstPtrInfo, SrcPtrInfo);
3781 if (Result.getNode())
3784 // If we really need inline code and the target declined to provide it,
3785 // use a (potentially long) sequence of loads and stores.
3787 assert(ConstantSize && "AlwaysInline requires a constant size!");
3788 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3789 ConstantSize->getZExtValue(), Align, isVol,
3790 true, DstPtrInfo, SrcPtrInfo);
3793 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3794 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3795 // respect volatile, so they may do things like read or write memory
3796 // beyond the given memory regions. But fixing this isn't easy, and most
3797 // people don't care.
3799 // Emit a library call.
3800 TargetLowering::ArgListTy Args;
3801 TargetLowering::ArgListEntry Entry;
3802 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3803 Entry.Node = Dst; Args.push_back(Entry);
3804 Entry.Node = Src; Args.push_back(Entry);
3805 Entry.Node = Size; Args.push_back(Entry);
3806 // FIXME: pass in DebugLoc
3808 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3809 false, false, false, false, 0,
3810 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3811 /*isTailCall=*/false,
3812 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3813 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3814 TLI.getPointerTy()),
3816 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3818 return CallResult.second;
3821 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3822 SDValue Src, SDValue Size,
3823 unsigned Align, bool isVol,
3824 MachinePointerInfo DstPtrInfo,
3825 MachinePointerInfo SrcPtrInfo) {
3827 // Check to see if we should lower the memmove to loads and stores first.
3828 // For cases within the target-specified limits, this is the best choice.
3829 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3831 // Memmove with size zero? Just return the original chain.
3832 if (ConstantSize->isNullValue())
3836 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3837 ConstantSize->getZExtValue(), Align, isVol,
3838 false, DstPtrInfo, SrcPtrInfo);
3839 if (Result.getNode())
3843 // Then check to see if we should lower the memmove with target-specific
3844 // code. If the target chooses to do this, this is the next best.
3846 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3847 DstPtrInfo, SrcPtrInfo);
3848 if (Result.getNode())
3851 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3852 // not be safe. See memcpy above for more details.
3854 // Emit a library call.
3855 TargetLowering::ArgListTy Args;
3856 TargetLowering::ArgListEntry Entry;
3857 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3858 Entry.Node = Dst; Args.push_back(Entry);
3859 Entry.Node = Src; Args.push_back(Entry);
3860 Entry.Node = Size; Args.push_back(Entry);
3861 // FIXME: pass in DebugLoc
3863 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3864 false, false, false, false, 0,
3865 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3866 /*isTailCall=*/false,
3867 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3868 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3869 TLI.getPointerTy()),
3871 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3873 return CallResult.second;
3876 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3877 SDValue Src, SDValue Size,
3878 unsigned Align, bool isVol,
3879 MachinePointerInfo DstPtrInfo) {
3881 // Check to see if we should lower the memset to stores first.
3882 // For cases within the target-specified limits, this is the best choice.
3883 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3885 // Memset with size zero? Just return the original chain.
3886 if (ConstantSize->isNullValue())
3890 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3891 Align, isVol, DstPtrInfo);
3893 if (Result.getNode())
3897 // Then check to see if we should lower the memset with target-specific
3898 // code. If the target chooses to do this, this is the next best.
3900 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3902 if (Result.getNode())
3905 // Emit a library call.
3906 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3907 TargetLowering::ArgListTy Args;
3908 TargetLowering::ArgListEntry Entry;
3909 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3910 Args.push_back(Entry);
3911 // Extend or truncate the argument to be an i32 value for the call.
3912 if (Src.getValueType().bitsGT(MVT::i32))
3913 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3915 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3917 Entry.Ty = Type::getInt32Ty(*getContext());
3918 Entry.isSExt = true;
3919 Args.push_back(Entry);
3921 Entry.Ty = IntPtrTy;
3922 Entry.isSExt = false;
3923 Args.push_back(Entry);
3924 // FIXME: pass in DebugLoc
3926 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3927 false, false, false, false, 0,
3928 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3929 /*isTailCall=*/false,
3930 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3931 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3932 TLI.getPointerTy()),
3934 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3936 return CallResult.second;
3939 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3940 SDValue Chain, SDValue Ptr, SDValue Cmp,
3941 SDValue Swp, MachinePointerInfo PtrInfo,
3943 AtomicOrdering Ordering,
3944 SynchronizationScope SynchScope) {
3945 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3946 Alignment = getEVTAlignment(MemVT);
3948 MachineFunction &MF = getMachineFunction();
3950 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
3951 // For now, atomics are considered to be volatile always.
3952 // FIXME: Volatile isn't really correct; we should keep track of atomic
3953 // orderings in the memoperand.
3954 unsigned Flags = MachineMemOperand::MOVolatile;
3955 if (Opcode != ISD::ATOMIC_STORE)
3956 Flags |= MachineMemOperand::MOLoad;
3957 if (Opcode != ISD::ATOMIC_LOAD)
3958 Flags |= MachineMemOperand::MOStore;
3960 MachineMemOperand *MMO =
3961 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3963 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3964 Ordering, SynchScope);
3967 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3969 SDValue Ptr, SDValue Cmp,
3970 SDValue Swp, MachineMemOperand *MMO,
3971 AtomicOrdering Ordering,
3972 SynchronizationScope SynchScope) {
3973 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3974 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3976 EVT VT = Cmp.getValueType();
3978 SDVTList VTs = getVTList(VT, MVT::Other);
3979 FoldingSetNodeID ID;
3980 ID.AddInteger(MemVT.getRawBits());
3981 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3982 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3983 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
3985 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3986 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3987 return SDValue(E, 0);
3989 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3990 Ptr, Cmp, Swp, MMO, Ordering,
3992 CSEMap.InsertNode(N, IP);
3993 AllNodes.push_back(N);
3994 return SDValue(N, 0);
3997 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3999 SDValue Ptr, SDValue Val,
4000 const Value* PtrVal,
4002 AtomicOrdering Ordering,
4003 SynchronizationScope SynchScope) {
4004 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4005 Alignment = getEVTAlignment(MemVT);
4007 MachineFunction &MF = getMachineFunction();
4008 // An atomic store does not load. An atomic load does not store.
4009 // (An atomicrmw obviously both loads and stores.)
4010 // For now, atomics are considered to be volatile always, and they are
4012 // FIXME: Volatile isn't really correct; we should keep track of atomic
4013 // orderings in the memoperand.
4014 unsigned Flags = MachineMemOperand::MOVolatile;
4015 if (Opcode != ISD::ATOMIC_STORE)
4016 Flags |= MachineMemOperand::MOLoad;
4017 if (Opcode != ISD::ATOMIC_LOAD)
4018 Flags |= MachineMemOperand::MOStore;
4020 MachineMemOperand *MMO =
4021 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4022 MemVT.getStoreSize(), Alignment);
4024 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4025 Ordering, SynchScope);
4028 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4030 SDValue Ptr, SDValue Val,
4031 MachineMemOperand *MMO,
4032 AtomicOrdering Ordering,
4033 SynchronizationScope SynchScope) {
4034 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4035 Opcode == ISD::ATOMIC_LOAD_SUB ||
4036 Opcode == ISD::ATOMIC_LOAD_AND ||
4037 Opcode == ISD::ATOMIC_LOAD_OR ||
4038 Opcode == ISD::ATOMIC_LOAD_XOR ||
4039 Opcode == ISD::ATOMIC_LOAD_NAND ||
4040 Opcode == ISD::ATOMIC_LOAD_MIN ||
4041 Opcode == ISD::ATOMIC_LOAD_MAX ||
4042 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4043 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4044 Opcode == ISD::ATOMIC_SWAP ||
4045 Opcode == ISD::ATOMIC_STORE) &&
4046 "Invalid Atomic Op");
4048 EVT VT = Val.getValueType();
4050 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4051 getVTList(VT, MVT::Other);
4052 FoldingSetNodeID ID;
4053 ID.AddInteger(MemVT.getRawBits());
4054 SDValue Ops[] = {Chain, Ptr, Val};
4055 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
4056 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4058 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4059 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4060 return SDValue(E, 0);
4062 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4064 Ordering, SynchScope);
4065 CSEMap.InsertNode(N, IP);
4066 AllNodes.push_back(N);
4067 return SDValue(N, 0);
4070 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4071 EVT VT, SDValue Chain,
4073 const Value* PtrVal,
4075 AtomicOrdering Ordering,
4076 SynchronizationScope SynchScope) {
4077 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4078 Alignment = getEVTAlignment(MemVT);
4080 MachineFunction &MF = getMachineFunction();
4081 // An atomic store does not load. An atomic load does not store.
4082 // (An atomicrmw obviously both loads and stores.)
4083 // For now, atomics are considered to be volatile always, and they are
4085 // FIXME: Volatile isn't really correct; we should keep track of atomic
4086 // orderings in the memoperand.
4087 unsigned Flags = MachineMemOperand::MOVolatile;
4088 if (Opcode != ISD::ATOMIC_STORE)
4089 Flags |= MachineMemOperand::MOLoad;
4090 if (Opcode != ISD::ATOMIC_LOAD)
4091 Flags |= MachineMemOperand::MOStore;
4093 MachineMemOperand *MMO =
4094 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4095 MemVT.getStoreSize(), Alignment);
4097 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4098 Ordering, SynchScope);
4101 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4102 EVT VT, SDValue Chain,
4104 MachineMemOperand *MMO,
4105 AtomicOrdering Ordering,
4106 SynchronizationScope SynchScope) {
4107 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4109 SDVTList VTs = getVTList(VT, MVT::Other);
4110 FoldingSetNodeID ID;
4111 ID.AddInteger(MemVT.getRawBits());
4112 SDValue Ops[] = {Chain, Ptr};
4113 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4114 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4116 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4117 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4118 return SDValue(E, 0);
4120 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4121 Ptr, MMO, Ordering, SynchScope);
4122 CSEMap.InsertNode(N, IP);
4123 AllNodes.push_back(N);
4124 return SDValue(N, 0);
4127 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4128 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4133 SmallVector<EVT, 4> VTs;
4134 VTs.reserve(NumOps);
4135 for (unsigned i = 0; i < NumOps; ++i)
4136 VTs.push_back(Ops[i].getValueType());
4137 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4142 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4143 const EVT *VTs, unsigned NumVTs,
4144 const SDValue *Ops, unsigned NumOps,
4145 EVT MemVT, MachinePointerInfo PtrInfo,
4146 unsigned Align, bool Vol,
4147 bool ReadMem, bool WriteMem) {
4148 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4149 MemVT, PtrInfo, Align, Vol,
4154 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4155 const SDValue *Ops, unsigned NumOps,
4156 EVT MemVT, MachinePointerInfo PtrInfo,
4157 unsigned Align, bool Vol,
4158 bool ReadMem, bool WriteMem) {
4159 if (Align == 0) // Ensure that codegen never sees alignment 0
4160 Align = getEVTAlignment(MemVT);
4162 MachineFunction &MF = getMachineFunction();
4165 Flags |= MachineMemOperand::MOStore;
4167 Flags |= MachineMemOperand::MOLoad;
4169 Flags |= MachineMemOperand::MOVolatile;
4170 MachineMemOperand *MMO =
4171 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4173 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4177 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4178 const SDValue *Ops, unsigned NumOps,
4179 EVT MemVT, MachineMemOperand *MMO) {
4180 assert((Opcode == ISD::INTRINSIC_VOID ||
4181 Opcode == ISD::INTRINSIC_W_CHAIN ||
4182 Opcode == ISD::PREFETCH ||
4183 Opcode == ISD::LIFETIME_START ||
4184 Opcode == ISD::LIFETIME_END ||
4185 (Opcode <= INT_MAX &&
4186 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4187 "Opcode is not a memory-accessing opcode!");
4189 // Memoize the node unless it returns a flag.
4190 MemIntrinsicSDNode *N;
4191 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4192 FoldingSetNodeID ID;
4193 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4194 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4196 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4197 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4198 return SDValue(E, 0);
4201 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4203 CSEMap.InsertNode(N, IP);
4205 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4208 AllNodes.push_back(N);
4209 return SDValue(N, 0);
4212 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4213 /// MachinePointerInfo record from it. This is particularly useful because the
4214 /// code generator has many cases where it doesn't bother passing in a
4215 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4216 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4217 // If this is FI+Offset, we can model it.
4218 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4219 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4221 // If this is (FI+Offset1)+Offset2, we can model it.
4222 if (Ptr.getOpcode() != ISD::ADD ||
4223 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4224 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4225 return MachinePointerInfo();
4227 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4228 return MachinePointerInfo::getFixedStack(FI, Offset+
4229 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4232 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4233 /// MachinePointerInfo record from it. This is particularly useful because the
4234 /// code generator has many cases where it doesn't bother passing in a
4235 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4236 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4237 // If the 'Offset' value isn't a constant, we can't handle this.
4238 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4239 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4240 if (OffsetOp.getOpcode() == ISD::UNDEF)
4241 return InferPointerInfo(Ptr);
4242 return MachinePointerInfo();
4247 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4248 EVT VT, DebugLoc dl, SDValue Chain,
4249 SDValue Ptr, SDValue Offset,
4250 MachinePointerInfo PtrInfo, EVT MemVT,
4251 bool isVolatile, bool isNonTemporal, bool isInvariant,
4252 unsigned Alignment, const MDNode *TBAAInfo,
4253 const MDNode *Ranges) {
4254 assert(Chain.getValueType() == MVT::Other &&
4255 "Invalid chain type");
4256 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4257 Alignment = getEVTAlignment(VT);
4259 unsigned Flags = MachineMemOperand::MOLoad;
4261 Flags |= MachineMemOperand::MOVolatile;
4263 Flags |= MachineMemOperand::MONonTemporal;
4265 Flags |= MachineMemOperand::MOInvariant;
4267 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4270 PtrInfo = InferPointerInfo(Ptr, Offset);
4272 MachineFunction &MF = getMachineFunction();
4273 MachineMemOperand *MMO =
4274 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4276 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4280 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4281 EVT VT, DebugLoc dl, SDValue Chain,
4282 SDValue Ptr, SDValue Offset, EVT MemVT,
4283 MachineMemOperand *MMO) {
4285 ExtType = ISD::NON_EXTLOAD;
4286 } else if (ExtType == ISD::NON_EXTLOAD) {
4287 assert(VT == MemVT && "Non-extending load from different memory type!");
4290 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4291 "Should only be an extending load, not truncating!");
4292 assert(VT.isInteger() == MemVT.isInteger() &&
4293 "Cannot convert from FP to Int or Int -> FP!");
4294 assert(VT.isVector() == MemVT.isVector() &&
4295 "Cannot use trunc store to convert to or from a vector!");
4296 assert((!VT.isVector() ||
4297 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4298 "Cannot use trunc store to change the number of vector elements!");
4301 bool Indexed = AM != ISD::UNINDEXED;
4302 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4303 "Unindexed load with an offset!");
4305 SDVTList VTs = Indexed ?
4306 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4307 SDValue Ops[] = { Chain, Ptr, Offset };
4308 FoldingSetNodeID ID;
4309 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4310 ID.AddInteger(MemVT.getRawBits());
4311 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4312 MMO->isNonTemporal(),
4313 MMO->isInvariant()));
4314 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4316 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4317 cast<LoadSDNode>(E)->refineAlignment(MMO);
4318 return SDValue(E, 0);
4320 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4322 CSEMap.InsertNode(N, IP);
4323 AllNodes.push_back(N);
4324 return SDValue(N, 0);
4327 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4328 SDValue Chain, SDValue Ptr,
4329 MachinePointerInfo PtrInfo,
4330 bool isVolatile, bool isNonTemporal,
4331 bool isInvariant, unsigned Alignment,
4332 const MDNode *TBAAInfo,
4333 const MDNode *Ranges) {
4334 SDValue Undef = getUNDEF(Ptr.getValueType());
4335 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4336 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4340 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4341 SDValue Chain, SDValue Ptr,
4342 MachinePointerInfo PtrInfo, EVT MemVT,
4343 bool isVolatile, bool isNonTemporal,
4344 unsigned Alignment, const MDNode *TBAAInfo) {
4345 SDValue Undef = getUNDEF(Ptr.getValueType());
4346 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4347 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4353 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4354 SDValue Offset, ISD::MemIndexedMode AM) {
4355 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4356 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4357 "Load is already a indexed load!");
4358 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4359 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4360 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4361 false, LD->getAlignment());
4364 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4365 SDValue Ptr, MachinePointerInfo PtrInfo,
4366 bool isVolatile, bool isNonTemporal,
4367 unsigned Alignment, const MDNode *TBAAInfo) {
4368 assert(Chain.getValueType() == MVT::Other &&
4369 "Invalid chain type");
4370 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4371 Alignment = getEVTAlignment(Val.getValueType());
4373 unsigned Flags = MachineMemOperand::MOStore;
4375 Flags |= MachineMemOperand::MOVolatile;
4377 Flags |= MachineMemOperand::MONonTemporal;
4380 PtrInfo = InferPointerInfo(Ptr);
4382 MachineFunction &MF = getMachineFunction();
4383 MachineMemOperand *MMO =
4384 MF.getMachineMemOperand(PtrInfo, Flags,
4385 Val.getValueType().getStoreSize(), Alignment,
4388 return getStore(Chain, dl, Val, Ptr, MMO);
4391 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4392 SDValue Ptr, MachineMemOperand *MMO) {
4393 assert(Chain.getValueType() == MVT::Other &&
4394 "Invalid chain type");
4395 EVT VT = Val.getValueType();
4396 SDVTList VTs = getVTList(MVT::Other);
4397 SDValue Undef = getUNDEF(Ptr.getValueType());
4398 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4399 FoldingSetNodeID ID;
4400 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4401 ID.AddInteger(VT.getRawBits());
4402 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4403 MMO->isNonTemporal(), MMO->isInvariant()));
4404 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4406 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4407 cast<StoreSDNode>(E)->refineAlignment(MMO);
4408 return SDValue(E, 0);
4410 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4412 CSEMap.InsertNode(N, IP);
4413 AllNodes.push_back(N);
4414 return SDValue(N, 0);
4417 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4418 SDValue Ptr, MachinePointerInfo PtrInfo,
4419 EVT SVT,bool isVolatile, bool isNonTemporal,
4421 const MDNode *TBAAInfo) {
4422 assert(Chain.getValueType() == MVT::Other &&
4423 "Invalid chain type");
4424 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4425 Alignment = getEVTAlignment(SVT);
4427 unsigned Flags = MachineMemOperand::MOStore;
4429 Flags |= MachineMemOperand::MOVolatile;
4431 Flags |= MachineMemOperand::MONonTemporal;
4434 PtrInfo = InferPointerInfo(Ptr);
4436 MachineFunction &MF = getMachineFunction();
4437 MachineMemOperand *MMO =
4438 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4441 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4444 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4445 SDValue Ptr, EVT SVT,
4446 MachineMemOperand *MMO) {
4447 EVT VT = Val.getValueType();
4449 assert(Chain.getValueType() == MVT::Other &&
4450 "Invalid chain type");
4452 return getStore(Chain, dl, Val, Ptr, MMO);
4454 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4455 "Should only be a truncating store, not extending!");
4456 assert(VT.isInteger() == SVT.isInteger() &&
4457 "Can't do FP-INT conversion!");
4458 assert(VT.isVector() == SVT.isVector() &&
4459 "Cannot use trunc store to convert to or from a vector!");
4460 assert((!VT.isVector() ||
4461 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4462 "Cannot use trunc store to change the number of vector elements!");
4464 SDVTList VTs = getVTList(MVT::Other);
4465 SDValue Undef = getUNDEF(Ptr.getValueType());
4466 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4467 FoldingSetNodeID ID;
4468 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4469 ID.AddInteger(SVT.getRawBits());
4470 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4471 MMO->isNonTemporal(), MMO->isInvariant()));
4472 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4474 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4475 cast<StoreSDNode>(E)->refineAlignment(MMO);
4476 return SDValue(E, 0);
4478 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4480 CSEMap.InsertNode(N, IP);
4481 AllNodes.push_back(N);
4482 return SDValue(N, 0);
4486 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4487 SDValue Offset, ISD::MemIndexedMode AM) {
4488 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4489 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4490 "Store is already a indexed store!");
4491 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4492 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4493 FoldingSetNodeID ID;
4494 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4495 ID.AddInteger(ST->getMemoryVT().getRawBits());
4496 ID.AddInteger(ST->getRawSubclassData());
4497 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4499 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4500 return SDValue(E, 0);
4502 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4503 ST->isTruncatingStore(),
4505 ST->getMemOperand());
4506 CSEMap.InsertNode(N, IP);
4507 AllNodes.push_back(N);
4508 return SDValue(N, 0);
4511 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4512 SDValue Chain, SDValue Ptr,
4515 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4516 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4519 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4520 const SDUse *Ops, unsigned NumOps) {
4522 case 0: return getNode(Opcode, DL, VT);
4523 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4524 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4525 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4529 // Copy from an SDUse array into an SDValue array for use with
4530 // the regular getNode logic.
4531 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4532 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4535 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4536 const SDValue *Ops, unsigned NumOps) {
4538 case 0: return getNode(Opcode, DL, VT);
4539 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4540 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4541 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4547 case ISD::SELECT_CC: {
4548 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4549 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4550 "LHS and RHS of condition must have same type!");
4551 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4552 "True and False arms of SelectCC must have same type!");
4553 assert(Ops[2].getValueType() == VT &&
4554 "select_cc node must be of same type as true and false value!");
4558 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4559 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4560 "LHS/RHS of comparison should match types!");
4567 SDVTList VTs = getVTList(VT);
4569 if (VT != MVT::Glue) {
4570 FoldingSetNodeID ID;
4571 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4574 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4575 return SDValue(E, 0);
4577 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4578 CSEMap.InsertNode(N, IP);
4580 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4583 AllNodes.push_back(N);
4587 return SDValue(N, 0);
4590 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4591 const std::vector<EVT> &ResultTys,
4592 const SDValue *Ops, unsigned NumOps) {
4593 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4597 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4598 const EVT *VTs, unsigned NumVTs,
4599 const SDValue *Ops, unsigned NumOps) {
4601 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4602 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4605 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4606 const SDValue *Ops, unsigned NumOps) {
4607 if (VTList.NumVTs == 1)
4608 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4612 // FIXME: figure out how to safely handle things like
4613 // int foo(int x) { return 1 << (x & 255); }
4614 // int bar() { return foo(256); }
4615 case ISD::SRA_PARTS:
4616 case ISD::SRL_PARTS:
4617 case ISD::SHL_PARTS:
4618 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4619 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4620 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4621 else if (N3.getOpcode() == ISD::AND)
4622 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4623 // If the and is only masking out bits that cannot effect the shift,
4624 // eliminate the and.
4625 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4626 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4627 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4633 // Memoize the node unless it returns a flag.
4635 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4636 FoldingSetNodeID ID;
4637 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4639 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4640 return SDValue(E, 0);
4643 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4644 } else if (NumOps == 2) {
4645 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4646 } else if (NumOps == 3) {
4647 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4650 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4652 CSEMap.InsertNode(N, IP);
4655 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4656 } else if (NumOps == 2) {
4657 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4658 } else if (NumOps == 3) {
4659 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4662 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4665 AllNodes.push_back(N);
4669 return SDValue(N, 0);
4672 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4673 return getNode(Opcode, DL, VTList, 0, 0);
4676 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4678 SDValue Ops[] = { N1 };
4679 return getNode(Opcode, DL, VTList, Ops, 1);
4682 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4683 SDValue N1, SDValue N2) {
4684 SDValue Ops[] = { N1, N2 };
4685 return getNode(Opcode, DL, VTList, Ops, 2);
4688 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4689 SDValue N1, SDValue N2, SDValue N3) {
4690 SDValue Ops[] = { N1, N2, N3 };
4691 return getNode(Opcode, DL, VTList, Ops, 3);
4694 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4695 SDValue N1, SDValue N2, SDValue N3,
4697 SDValue Ops[] = { N1, N2, N3, N4 };
4698 return getNode(Opcode, DL, VTList, Ops, 4);
4701 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4702 SDValue N1, SDValue N2, SDValue N3,
4703 SDValue N4, SDValue N5) {
4704 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4705 return getNode(Opcode, DL, VTList, Ops, 5);
4708 SDVTList SelectionDAG::getVTList(EVT VT) {
4709 return makeVTList(SDNode::getValueTypeList(VT), 1);
4712 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4713 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4714 E = VTList.rend(); I != E; ++I)
4715 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4718 EVT *Array = Allocator.Allocate<EVT>(2);
4721 SDVTList Result = makeVTList(Array, 2);
4722 VTList.push_back(Result);
4726 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4727 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4728 E = VTList.rend(); I != E; ++I)
4729 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4733 EVT *Array = Allocator.Allocate<EVT>(3);
4737 SDVTList Result = makeVTList(Array, 3);
4738 VTList.push_back(Result);
4742 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4743 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4744 E = VTList.rend(); I != E; ++I)
4745 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4746 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4749 EVT *Array = Allocator.Allocate<EVT>(4);
4754 SDVTList Result = makeVTList(Array, 4);
4755 VTList.push_back(Result);
4759 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4761 case 0: llvm_unreachable("Cannot have nodes without results!");
4762 case 1: return getVTList(VTs[0]);
4763 case 2: return getVTList(VTs[0], VTs[1]);
4764 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4765 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4769 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4770 E = VTList.rend(); I != E; ++I) {
4771 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4774 if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2]))
4778 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4779 std::copy(VTs, VTs+NumVTs, Array);
4780 SDVTList Result = makeVTList(Array, NumVTs);
4781 VTList.push_back(Result);
4786 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4787 /// specified operands. If the resultant node already exists in the DAG,
4788 /// this does not modify the specified node, instead it returns the node that
4789 /// already exists. If the resultant node does not exist in the DAG, the
4790 /// input node is returned. As a degenerate case, if you specify the same
4791 /// input operands as the node already has, the input node is returned.
4792 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4793 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4795 // Check to see if there is no change.
4796 if (Op == N->getOperand(0)) return N;
4798 // See if the modified node already exists.
4799 void *InsertPos = 0;
4800 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4803 // Nope it doesn't. Remove the node from its current place in the maps.
4805 if (!RemoveNodeFromCSEMaps(N))
4808 // Now we update the operands.
4809 N->OperandList[0].set(Op);
4811 // If this gets put into a CSE map, add it.
4812 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4816 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4817 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4819 // Check to see if there is no change.
4820 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4821 return N; // No operands changed, just return the input node.
4823 // See if the modified node already exists.
4824 void *InsertPos = 0;
4825 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4828 // Nope it doesn't. Remove the node from its current place in the maps.
4830 if (!RemoveNodeFromCSEMaps(N))
4833 // Now we update the operands.
4834 if (N->OperandList[0] != Op1)
4835 N->OperandList[0].set(Op1);
4836 if (N->OperandList[1] != Op2)
4837 N->OperandList[1].set(Op2);
4839 // If this gets put into a CSE map, add it.
4840 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4844 SDNode *SelectionDAG::
4845 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4846 SDValue Ops[] = { Op1, Op2, Op3 };
4847 return UpdateNodeOperands(N, Ops, 3);
4850 SDNode *SelectionDAG::
4851 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4852 SDValue Op3, SDValue Op4) {
4853 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4854 return UpdateNodeOperands(N, Ops, 4);
4857 SDNode *SelectionDAG::
4858 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4859 SDValue Op3, SDValue Op4, SDValue Op5) {
4860 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4861 return UpdateNodeOperands(N, Ops, 5);
4864 SDNode *SelectionDAG::
4865 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4866 assert(N->getNumOperands() == NumOps &&
4867 "Update with wrong number of operands");
4869 // Check to see if there is no change.
4870 bool AnyChange = false;
4871 for (unsigned i = 0; i != NumOps; ++i) {
4872 if (Ops[i] != N->getOperand(i)) {
4878 // No operands changed, just return the input node.
4879 if (!AnyChange) return N;
4881 // See if the modified node already exists.
4882 void *InsertPos = 0;
4883 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4886 // Nope it doesn't. Remove the node from its current place in the maps.
4888 if (!RemoveNodeFromCSEMaps(N))
4891 // Now we update the operands.
4892 for (unsigned i = 0; i != NumOps; ++i)
4893 if (N->OperandList[i] != Ops[i])
4894 N->OperandList[i].set(Ops[i]);
4896 // If this gets put into a CSE map, add it.
4897 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4901 /// DropOperands - Release the operands and set this node to have
4903 void SDNode::DropOperands() {
4904 // Unlike the code in MorphNodeTo that does this, we don't need to
4905 // watch for dead nodes here.
4906 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4912 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4915 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4917 SDVTList VTs = getVTList(VT);
4918 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4921 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4922 EVT VT, SDValue Op1) {
4923 SDVTList VTs = getVTList(VT);
4924 SDValue Ops[] = { Op1 };
4925 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4928 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4929 EVT VT, SDValue Op1,
4931 SDVTList VTs = getVTList(VT);
4932 SDValue Ops[] = { Op1, Op2 };
4933 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4936 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4937 EVT VT, SDValue Op1,
4938 SDValue Op2, SDValue Op3) {
4939 SDVTList VTs = getVTList(VT);
4940 SDValue Ops[] = { Op1, Op2, Op3 };
4941 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4944 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4945 EVT VT, const SDValue *Ops,
4947 SDVTList VTs = getVTList(VT);
4948 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4951 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4952 EVT VT1, EVT VT2, const SDValue *Ops,
4954 SDVTList VTs = getVTList(VT1, VT2);
4955 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4958 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4960 SDVTList VTs = getVTList(VT1, VT2);
4961 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4964 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4965 EVT VT1, EVT VT2, EVT VT3,
4966 const SDValue *Ops, unsigned NumOps) {
4967 SDVTList VTs = getVTList(VT1, VT2, VT3);
4968 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4971 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4972 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4973 const SDValue *Ops, unsigned NumOps) {
4974 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4975 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4978 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4981 SDVTList VTs = getVTList(VT1, VT2);
4982 SDValue Ops[] = { Op1 };
4983 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4986 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4988 SDValue Op1, SDValue Op2) {
4989 SDVTList VTs = getVTList(VT1, VT2);
4990 SDValue Ops[] = { Op1, Op2 };
4991 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4994 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4996 SDValue Op1, SDValue Op2,
4998 SDVTList VTs = getVTList(VT1, VT2);
4999 SDValue Ops[] = { Op1, Op2, Op3 };
5000 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5003 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5004 EVT VT1, EVT VT2, EVT VT3,
5005 SDValue Op1, SDValue Op2,
5007 SDVTList VTs = getVTList(VT1, VT2, VT3);
5008 SDValue Ops[] = { Op1, Op2, Op3 };
5009 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5012 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5013 SDVTList VTs, const SDValue *Ops,
5015 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5016 // Reset the NodeID to -1.
5021 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
5022 /// the line number information on the merged node since it is not possible to
5023 /// preserve the information that operation is associated with multiple lines.
5024 /// This will make the debugger working better at -O0, were there is a higher
5025 /// probability having other instructions associated with that line.
5027 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
5028 DebugLoc NLoc = N->getDebugLoc();
5029 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
5030 N->setDebugLoc(DebugLoc());
5035 /// MorphNodeTo - This *mutates* the specified node to have the specified
5036 /// return type, opcode, and operands.
5038 /// Note that MorphNodeTo returns the resultant node. If there is already a
5039 /// node of the specified opcode and operands, it returns that node instead of
5040 /// the current one. Note that the DebugLoc need not be the same.
5042 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5043 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5044 /// node, and because it doesn't require CSE recalculation for any of
5045 /// the node's users.
5047 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5048 SDVTList VTs, const SDValue *Ops,
5050 // If an identical node already exists, use it.
5052 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5053 FoldingSetNodeID ID;
5054 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5055 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5056 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
5059 if (!RemoveNodeFromCSEMaps(N))
5062 // Start the morphing.
5064 N->ValueList = VTs.VTs;
5065 N->NumValues = VTs.NumVTs;
5067 // Clear the operands list, updating used nodes to remove this from their
5068 // use list. Keep track of any operands that become dead as a result.
5069 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5070 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5072 SDNode *Used = Use.getNode();
5074 if (Used->use_empty())
5075 DeadNodeSet.insert(Used);
5078 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5079 // Initialize the memory references information.
5080 MN->setMemRefs(0, 0);
5081 // If NumOps is larger than the # of operands we can have in a
5082 // MachineSDNode, reallocate the operand list.
5083 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5084 if (MN->OperandsNeedDelete)
5085 delete[] MN->OperandList;
5086 if (NumOps > array_lengthof(MN->LocalOperands))
5087 // We're creating a final node that will live unmorphed for the
5088 // remainder of the current SelectionDAG iteration, so we can allocate
5089 // the operands directly out of a pool with no recycling metadata.
5090 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5093 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5094 MN->OperandsNeedDelete = false;
5096 MN->InitOperands(MN->OperandList, Ops, NumOps);
5098 // If NumOps is larger than the # of operands we currently have, reallocate
5099 // the operand list.
5100 if (NumOps > N->NumOperands) {
5101 if (N->OperandsNeedDelete)
5102 delete[] N->OperandList;
5103 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5104 N->OperandsNeedDelete = true;
5106 N->InitOperands(N->OperandList, Ops, NumOps);
5109 // Delete any nodes that are still dead after adding the uses for the
5111 if (!DeadNodeSet.empty()) {
5112 SmallVector<SDNode *, 16> DeadNodes;
5113 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5114 E = DeadNodeSet.end(); I != E; ++I)
5115 if ((*I)->use_empty())
5116 DeadNodes.push_back(*I);
5117 RemoveDeadNodes(DeadNodes);
5121 CSEMap.InsertNode(N, IP); // Memoize the new node.
5126 /// getMachineNode - These are used for target selectors to create a new node
5127 /// with specified return type(s), MachineInstr opcode, and operands.
5129 /// Note that getMachineNode returns the resultant node. If there is already a
5130 /// node of the specified opcode and operands, it returns that node instead of
5131 /// the current one.
5133 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5134 SDVTList VTs = getVTList(VT);
5135 return getMachineNode(Opcode, dl, VTs, 0, 0);
5139 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5140 SDVTList VTs = getVTList(VT);
5141 SDValue Ops[] = { Op1 };
5142 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5146 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5147 SDValue Op1, SDValue Op2) {
5148 SDVTList VTs = getVTList(VT);
5149 SDValue Ops[] = { Op1, Op2 };
5150 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5154 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5155 SDValue Op1, SDValue Op2, SDValue Op3) {
5156 SDVTList VTs = getVTList(VT);
5157 SDValue Ops[] = { Op1, Op2, Op3 };
5158 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5162 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5163 const SDValue *Ops, unsigned NumOps) {
5164 SDVTList VTs = getVTList(VT);
5165 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5169 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5170 SDVTList VTs = getVTList(VT1, VT2);
5171 return getMachineNode(Opcode, dl, VTs, 0, 0);
5175 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5176 EVT VT1, EVT VT2, SDValue Op1) {
5177 SDVTList VTs = getVTList(VT1, VT2);
5178 SDValue Ops[] = { Op1 };
5179 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5183 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5184 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5185 SDVTList VTs = getVTList(VT1, VT2);
5186 SDValue Ops[] = { Op1, Op2 };
5187 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5191 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5192 EVT VT1, EVT VT2, SDValue Op1,
5193 SDValue Op2, SDValue Op3) {
5194 SDVTList VTs = getVTList(VT1, VT2);
5195 SDValue Ops[] = { Op1, Op2, Op3 };
5196 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5200 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5202 const SDValue *Ops, unsigned NumOps) {
5203 SDVTList VTs = getVTList(VT1, VT2);
5204 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5208 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5209 EVT VT1, EVT VT2, EVT VT3,
5210 SDValue Op1, SDValue Op2) {
5211 SDVTList VTs = getVTList(VT1, VT2, VT3);
5212 SDValue Ops[] = { Op1, Op2 };
5213 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5217 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5218 EVT VT1, EVT VT2, EVT VT3,
5219 SDValue Op1, SDValue Op2, SDValue Op3) {
5220 SDVTList VTs = getVTList(VT1, VT2, VT3);
5221 SDValue Ops[] = { Op1, Op2, Op3 };
5222 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5226 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5227 EVT VT1, EVT VT2, EVT VT3,
5228 const SDValue *Ops, unsigned NumOps) {
5229 SDVTList VTs = getVTList(VT1, VT2, VT3);
5230 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5234 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5235 EVT VT2, EVT VT3, EVT VT4,
5236 const SDValue *Ops, unsigned NumOps) {
5237 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5238 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5242 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5243 const std::vector<EVT> &ResultTys,
5244 const SDValue *Ops, unsigned NumOps) {
5245 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5246 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5250 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5251 const SDValue *Ops, unsigned NumOps) {
5252 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5257 FoldingSetNodeID ID;
5258 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5260 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5261 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5265 // Allocate a new MachineSDNode.
5266 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5268 // Initialize the operands list.
5269 if (NumOps > array_lengthof(N->LocalOperands))
5270 // We're creating a final node that will live unmorphed for the
5271 // remainder of the current SelectionDAG iteration, so we can allocate
5272 // the operands directly out of a pool with no recycling metadata.
5273 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5276 N->InitOperands(N->LocalOperands, Ops, NumOps);
5277 N->OperandsNeedDelete = false;
5280 CSEMap.InsertNode(N, IP);
5282 AllNodes.push_back(N);
5284 VerifyMachineNode(N);
5289 /// getTargetExtractSubreg - A convenience function for creating
5290 /// TargetOpcode::EXTRACT_SUBREG nodes.
5292 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5294 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5295 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5296 VT, Operand, SRIdxVal);
5297 return SDValue(Subreg, 0);
5300 /// getTargetInsertSubreg - A convenience function for creating
5301 /// TargetOpcode::INSERT_SUBREG nodes.
5303 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5304 SDValue Operand, SDValue Subreg) {
5305 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5306 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5307 VT, Operand, Subreg, SRIdxVal);
5308 return SDValue(Result, 0);
5311 /// getNodeIfExists - Get the specified node if it's already available, or
5312 /// else return NULL.
5313 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5314 const SDValue *Ops, unsigned NumOps) {
5315 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5316 FoldingSetNodeID ID;
5317 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5319 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5325 /// getDbgValue - Creates a SDDbgValue node.
5328 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5329 DebugLoc DL, unsigned O) {
5330 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5334 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5335 DebugLoc DL, unsigned O) {
5336 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5340 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5341 DebugLoc DL, unsigned O) {
5342 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5347 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5348 /// pointed to by a use iterator is deleted, increment the use iterator
5349 /// so that it doesn't dangle.
5351 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5352 SDNode::use_iterator &UI;
5353 SDNode::use_iterator &UE;
5355 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5356 // Increment the iterator as needed.
5357 while (UI != UE && N == *UI)
5362 RAUWUpdateListener(SelectionDAG &d,
5363 SDNode::use_iterator &ui,
5364 SDNode::use_iterator &ue)
5365 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5370 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5371 /// This can cause recursive merging of nodes in the DAG.
5373 /// This version assumes From has a single result value.
5375 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5376 SDNode *From = FromN.getNode();
5377 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5378 "Cannot replace with this method!");
5379 assert(From != To.getNode() && "Cannot replace uses of with self");
5381 // Iterate over all the existing uses of From. New uses will be added
5382 // to the beginning of the use list, which we avoid visiting.
5383 // This specifically avoids visiting uses of From that arise while the
5384 // replacement is happening, because any such uses would be the result
5385 // of CSE: If an existing node looks like From after one of its operands
5386 // is replaced by To, we don't want to replace of all its users with To
5387 // too. See PR3018 for more info.
5388 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5389 RAUWUpdateListener Listener(*this, UI, UE);
5393 // This node is about to morph, remove its old self from the CSE maps.
5394 RemoveNodeFromCSEMaps(User);
5396 // A user can appear in a use list multiple times, and when this
5397 // happens the uses are usually next to each other in the list.
5398 // To help reduce the number of CSE recomputations, process all
5399 // the uses of this user that we can find this way.
5401 SDUse &Use = UI.getUse();
5404 } while (UI != UE && *UI == User);
5406 // Now that we have modified User, add it back to the CSE maps. If it
5407 // already exists there, recursively merge the results together.
5408 AddModifiedNodeToCSEMaps(User);
5411 // If we just RAUW'd the root, take note.
5412 if (FromN == getRoot())
5416 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5417 /// This can cause recursive merging of nodes in the DAG.
5419 /// This version assumes that for each value of From, there is a
5420 /// corresponding value in To in the same position with the same type.
5422 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5424 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5425 assert((!From->hasAnyUseOfValue(i) ||
5426 From->getValueType(i) == To->getValueType(i)) &&
5427 "Cannot use this version of ReplaceAllUsesWith!");
5430 // Handle the trivial case.
5434 // Iterate over just the existing users of From. See the comments in
5435 // the ReplaceAllUsesWith above.
5436 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5437 RAUWUpdateListener Listener(*this, UI, UE);
5441 // This node is about to morph, remove its old self from the CSE maps.
5442 RemoveNodeFromCSEMaps(User);
5444 // A user can appear in a use list multiple times, and when this
5445 // happens the uses are usually next to each other in the list.
5446 // To help reduce the number of CSE recomputations, process all
5447 // the uses of this user that we can find this way.
5449 SDUse &Use = UI.getUse();
5452 } while (UI != UE && *UI == User);
5454 // Now that we have modified User, add it back to the CSE maps. If it
5455 // already exists there, recursively merge the results together.
5456 AddModifiedNodeToCSEMaps(User);
5459 // If we just RAUW'd the root, take note.
5460 if (From == getRoot().getNode())
5461 setRoot(SDValue(To, getRoot().getResNo()));
5464 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5465 /// This can cause recursive merging of nodes in the DAG.
5467 /// This version can replace From with any result values. To must match the
5468 /// number and types of values returned by From.
5469 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5470 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5471 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5473 // Iterate over just the existing users of From. See the comments in
5474 // the ReplaceAllUsesWith above.
5475 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5476 RAUWUpdateListener Listener(*this, UI, UE);
5480 // This node is about to morph, remove its old self from the CSE maps.
5481 RemoveNodeFromCSEMaps(User);
5483 // A user can appear in a use list multiple times, and when this
5484 // happens the uses are usually next to each other in the list.
5485 // To help reduce the number of CSE recomputations, process all
5486 // the uses of this user that we can find this way.
5488 SDUse &Use = UI.getUse();
5489 const SDValue &ToOp = To[Use.getResNo()];
5492 } while (UI != UE && *UI == User);
5494 // Now that we have modified User, add it back to the CSE maps. If it
5495 // already exists there, recursively merge the results together.
5496 AddModifiedNodeToCSEMaps(User);
5499 // If we just RAUW'd the root, take note.
5500 if (From == getRoot().getNode())
5501 setRoot(SDValue(To[getRoot().getResNo()]));
5504 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5505 /// uses of other values produced by From.getNode() alone. The Deleted
5506 /// vector is handled the same way as for ReplaceAllUsesWith.
5507 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5508 // Handle the really simple, really trivial case efficiently.
5509 if (From == To) return;
5511 // Handle the simple, trivial, case efficiently.
5512 if (From.getNode()->getNumValues() == 1) {
5513 ReplaceAllUsesWith(From, To);
5517 // Iterate over just the existing users of From. See the comments in
5518 // the ReplaceAllUsesWith above.
5519 SDNode::use_iterator UI = From.getNode()->use_begin(),
5520 UE = From.getNode()->use_end();
5521 RAUWUpdateListener Listener(*this, UI, UE);
5524 bool UserRemovedFromCSEMaps = false;
5526 // A user can appear in a use list multiple times, and when this
5527 // happens the uses are usually next to each other in the list.
5528 // To help reduce the number of CSE recomputations, process all
5529 // the uses of this user that we can find this way.
5531 SDUse &Use = UI.getUse();
5533 // Skip uses of different values from the same node.
5534 if (Use.getResNo() != From.getResNo()) {
5539 // If this node hasn't been modified yet, it's still in the CSE maps,
5540 // so remove its old self from the CSE maps.
5541 if (!UserRemovedFromCSEMaps) {
5542 RemoveNodeFromCSEMaps(User);
5543 UserRemovedFromCSEMaps = true;
5548 } while (UI != UE && *UI == User);
5550 // We are iterating over all uses of the From node, so if a use
5551 // doesn't use the specific value, no changes are made.
5552 if (!UserRemovedFromCSEMaps)
5555 // Now that we have modified User, add it back to the CSE maps. If it
5556 // already exists there, recursively merge the results together.
5557 AddModifiedNodeToCSEMaps(User);
5560 // If we just RAUW'd the root, take note.
5561 if (From == getRoot())
5566 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5567 /// to record information about a use.
5574 /// operator< - Sort Memos by User.
5575 bool operator<(const UseMemo &L, const UseMemo &R) {
5576 return (intptr_t)L.User < (intptr_t)R.User;
5580 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5581 /// uses of other values produced by From.getNode() alone. The same value
5582 /// may appear in both the From and To list. The Deleted vector is
5583 /// handled the same way as for ReplaceAllUsesWith.
5584 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5587 // Handle the simple, trivial case efficiently.
5589 return ReplaceAllUsesOfValueWith(*From, *To);
5591 // Read up all the uses and make records of them. This helps
5592 // processing new uses that are introduced during the
5593 // replacement process.
5594 SmallVector<UseMemo, 4> Uses;
5595 for (unsigned i = 0; i != Num; ++i) {
5596 unsigned FromResNo = From[i].getResNo();
5597 SDNode *FromNode = From[i].getNode();
5598 for (SDNode::use_iterator UI = FromNode->use_begin(),
5599 E = FromNode->use_end(); UI != E; ++UI) {
5600 SDUse &Use = UI.getUse();
5601 if (Use.getResNo() == FromResNo) {
5602 UseMemo Memo = { *UI, i, &Use };
5603 Uses.push_back(Memo);
5608 // Sort the uses, so that all the uses from a given User are together.
5609 std::sort(Uses.begin(), Uses.end());
5611 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5612 UseIndex != UseIndexEnd; ) {
5613 // We know that this user uses some value of From. If it is the right
5614 // value, update it.
5615 SDNode *User = Uses[UseIndex].User;
5617 // This node is about to morph, remove its old self from the CSE maps.
5618 RemoveNodeFromCSEMaps(User);
5620 // The Uses array is sorted, so all the uses for a given User
5621 // are next to each other in the list.
5622 // To help reduce the number of CSE recomputations, process all
5623 // the uses of this user that we can find this way.
5625 unsigned i = Uses[UseIndex].Index;
5626 SDUse &Use = *Uses[UseIndex].Use;
5630 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5632 // Now that we have modified User, add it back to the CSE maps. If it
5633 // already exists there, recursively merge the results together.
5634 AddModifiedNodeToCSEMaps(User);
5638 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5639 /// based on their topological order. It returns the maximum id and a vector
5640 /// of the SDNodes* in assigned order by reference.
5641 unsigned SelectionDAG::AssignTopologicalOrder() {
5643 unsigned DAGSize = 0;
5645 // SortedPos tracks the progress of the algorithm. Nodes before it are
5646 // sorted, nodes after it are unsorted. When the algorithm completes
5647 // it is at the end of the list.
5648 allnodes_iterator SortedPos = allnodes_begin();
5650 // Visit all the nodes. Move nodes with no operands to the front of
5651 // the list immediately. Annotate nodes that do have operands with their
5652 // operand count. Before we do this, the Node Id fields of the nodes
5653 // may contain arbitrary values. After, the Node Id fields for nodes
5654 // before SortedPos will contain the topological sort index, and the
5655 // Node Id fields for nodes At SortedPos and after will contain the
5656 // count of outstanding operands.
5657 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5660 unsigned Degree = N->getNumOperands();
5662 // A node with no uses, add it to the result array immediately.
5663 N->setNodeId(DAGSize++);
5664 allnodes_iterator Q = N;
5666 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5667 assert(SortedPos != AllNodes.end() && "Overran node list");
5670 // Temporarily use the Node Id as scratch space for the degree count.
5671 N->setNodeId(Degree);
5675 // Visit all the nodes. As we iterate, move nodes into sorted order,
5676 // such that by the time the end is reached all nodes will be sorted.
5677 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5680 // N is in sorted position, so all its uses have one less operand
5681 // that needs to be sorted.
5682 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5685 unsigned Degree = P->getNodeId();
5686 assert(Degree != 0 && "Invalid node degree");
5689 // All of P's operands are sorted, so P may sorted now.
5690 P->setNodeId(DAGSize++);
5692 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5693 assert(SortedPos != AllNodes.end() && "Overran node list");
5696 // Update P's outstanding operand count.
5697 P->setNodeId(Degree);
5700 if (I == SortedPos) {
5703 dbgs() << "Overran sorted position:\n";
5706 llvm_unreachable(0);
5710 assert(SortedPos == AllNodes.end() &&
5711 "Topological sort incomplete!");
5712 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5713 "First node in topological sort is not the entry token!");
5714 assert(AllNodes.front().getNodeId() == 0 &&
5715 "First node in topological sort has non-zero id!");
5716 assert(AllNodes.front().getNumOperands() == 0 &&
5717 "First node in topological sort has operands!");
5718 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5719 "Last node in topologic sort has unexpected id!");
5720 assert(AllNodes.back().use_empty() &&
5721 "Last node in topologic sort has users!");
5722 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5726 /// AssignOrdering - Assign an order to the SDNode.
5727 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5728 assert(SD && "Trying to assign an order to a null node!");
5729 Ordering->add(SD, Order);
5732 /// GetOrdering - Get the order for the SDNode.
5733 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5734 assert(SD && "Trying to get the order of a null node!");
5735 return Ordering->getOrder(SD);
5738 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5739 /// value is produced by SD.
5740 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5741 DbgInfo->add(DB, SD, isParameter);
5743 SD->setHasDebugValue(true);
5746 /// TransferDbgValues - Transfer SDDbgValues.
5747 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5748 if (From == To || !From.getNode()->getHasDebugValue())
5750 SDNode *FromNode = From.getNode();
5751 SDNode *ToNode = To.getNode();
5752 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5753 SmallVector<SDDbgValue *, 2> ClonedDVs;
5754 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5756 SDDbgValue *Dbg = *I;
5757 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5758 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5759 Dbg->getOffset(), Dbg->getDebugLoc(),
5761 ClonedDVs.push_back(Clone);
5764 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5765 E = ClonedDVs.end(); I != E; ++I)
5766 AddDbgValue(*I, ToNode, false);
5769 //===----------------------------------------------------------------------===//
5771 //===----------------------------------------------------------------------===//
5773 HandleSDNode::~HandleSDNode() {
5777 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5778 const GlobalValue *GA,
5779 EVT VT, int64_t o, unsigned char TF)
5780 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5784 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5785 MachineMemOperand *mmo)
5786 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5787 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5788 MMO->isNonTemporal(), MMO->isInvariant());
5789 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5790 assert(isNonTemporal() == MMO->isNonTemporal() &&
5791 "Non-temporal encoding error!");
5792 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5795 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5796 const SDValue *Ops, unsigned NumOps, EVT memvt,
5797 MachineMemOperand *mmo)
5798 : SDNode(Opc, dl, VTs, Ops, NumOps),
5799 MemoryVT(memvt), MMO(mmo) {
5800 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5801 MMO->isNonTemporal(), MMO->isInvariant());
5802 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5803 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5806 /// Profile - Gather unique data for the node.
5808 void SDNode::Profile(FoldingSetNodeID &ID) const {
5809 AddNodeIDNode(ID, this);
5814 std::vector<EVT> VTs;
5817 VTs.reserve(MVT::LAST_VALUETYPE);
5818 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5819 VTs.push_back(MVT((MVT::SimpleValueType)i));
5824 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5825 static ManagedStatic<EVTArray> SimpleVTArray;
5826 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5828 /// getValueTypeList - Return a pointer to the specified value type.
5830 const EVT *SDNode::getValueTypeList(EVT VT) {
5831 if (VT.isExtended()) {
5832 sys::SmartScopedLock<true> Lock(*VTMutex);
5833 return &(*EVTs->insert(VT).first);
5835 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5836 "Value type out of range!");
5837 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5841 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5842 /// indicated value. This method ignores uses of other values defined by this
5844 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5845 assert(Value < getNumValues() && "Bad value!");
5847 // TODO: Only iterate over uses of a given value of the node
5848 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5849 if (UI.getUse().getResNo() == Value) {
5856 // Found exactly the right number of uses?
5861 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5862 /// value. This method ignores uses of other values defined by this operation.
5863 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5864 assert(Value < getNumValues() && "Bad value!");
5866 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5867 if (UI.getUse().getResNo() == Value)
5874 /// isOnlyUserOf - Return true if this node is the only use of N.
5876 bool SDNode::isOnlyUserOf(SDNode *N) const {
5878 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5889 /// isOperand - Return true if this node is an operand of N.
5891 bool SDValue::isOperandOf(SDNode *N) const {
5892 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5893 if (*this == N->getOperand(i))
5898 bool SDNode::isOperandOf(SDNode *N) const {
5899 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5900 if (this == N->OperandList[i].getNode())
5905 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5906 /// be a chain) reaches the specified operand without crossing any
5907 /// side-effecting instructions on any chain path. In practice, this looks
5908 /// through token factors and non-volatile loads. In order to remain efficient,
5909 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5910 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5911 unsigned Depth) const {
5912 if (*this == Dest) return true;
5914 // Don't search too deeply, we just want to be able to see through
5915 // TokenFactor's etc.
5916 if (Depth == 0) return false;
5918 // If this is a token factor, all inputs to the TF happen in parallel. If any
5919 // of the operands of the TF does not reach dest, then we cannot do the xform.
5920 if (getOpcode() == ISD::TokenFactor) {
5921 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5922 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5927 // Loads don't have side effects, look through them.
5928 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5929 if (!Ld->isVolatile())
5930 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5935 /// hasPredecessor - Return true if N is a predecessor of this node.
5936 /// N is either an operand of this node, or can be reached by recursively
5937 /// traversing up the operands.
5938 /// NOTE: This is an expensive method. Use it carefully.
5939 bool SDNode::hasPredecessor(const SDNode *N) const {
5940 SmallPtrSet<const SDNode *, 32> Visited;
5941 SmallVector<const SDNode *, 16> Worklist;
5942 return hasPredecessorHelper(N, Visited, Worklist);
5945 bool SDNode::hasPredecessorHelper(const SDNode *N,
5946 SmallPtrSet<const SDNode *, 32> &Visited,
5947 SmallVector<const SDNode *, 16> &Worklist) const {
5948 if (Visited.empty()) {
5949 Worklist.push_back(this);
5951 // Take a look in the visited set. If we've already encountered this node
5952 // we needn't search further.
5953 if (Visited.count(N))
5957 // Haven't visited N yet. Continue the search.
5958 while (!Worklist.empty()) {
5959 const SDNode *M = Worklist.pop_back_val();
5960 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5961 SDNode *Op = M->getOperand(i).getNode();
5962 if (Visited.insert(Op))
5963 Worklist.push_back(Op);
5972 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5973 assert(Num < NumOperands && "Invalid child # of SDNode!");
5974 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5977 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5978 assert(N->getNumValues() == 1 &&
5979 "Can't unroll a vector with multiple results!");
5981 EVT VT = N->getValueType(0);
5982 unsigned NE = VT.getVectorNumElements();
5983 EVT EltVT = VT.getVectorElementType();
5984 DebugLoc dl = N->getDebugLoc();
5986 SmallVector<SDValue, 8> Scalars;
5987 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5989 // If ResNE is 0, fully unroll the vector op.
5992 else if (NE > ResNE)
5996 for (i= 0; i != NE; ++i) {
5997 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5998 SDValue Operand = N->getOperand(j);
5999 EVT OperandVT = Operand.getValueType();
6000 if (OperandVT.isVector()) {
6001 // A vector operand; extract a single element.
6002 EVT OperandEltVT = OperandVT.getVectorElementType();
6003 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6006 getConstant(i, TLI.getPointerTy()));
6008 // A scalar operand; just use it as is.
6009 Operands[j] = Operand;
6013 switch (N->getOpcode()) {
6015 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6016 &Operands[0], Operands.size()));
6019 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6020 &Operands[0], Operands.size()));
6027 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6028 getShiftAmountOperand(Operands[0].getValueType(),
6031 case ISD::SIGN_EXTEND_INREG:
6032 case ISD::FP_ROUND_INREG: {
6033 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6034 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6036 getValueType(ExtVT)));
6041 for (; i < ResNE; ++i)
6042 Scalars.push_back(getUNDEF(EltVT));
6044 return getNode(ISD::BUILD_VECTOR, dl,
6045 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6046 &Scalars[0], Scalars.size());
6050 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6051 /// location that is 'Dist' units away from the location that the 'Base' load
6052 /// is loading from.
6053 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6054 unsigned Bytes, int Dist) const {
6055 if (LD->getChain() != Base->getChain())
6057 EVT VT = LD->getValueType(0);
6058 if (VT.getSizeInBits() / 8 != Bytes)
6061 SDValue Loc = LD->getOperand(1);
6062 SDValue BaseLoc = Base->getOperand(1);
6063 if (Loc.getOpcode() == ISD::FrameIndex) {
6064 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6066 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6067 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6068 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6069 int FS = MFI->getObjectSize(FI);
6070 int BFS = MFI->getObjectSize(BFI);
6071 if (FS != BFS || FS != (int)Bytes) return false;
6072 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6076 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6077 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6080 const GlobalValue *GV1 = NULL;
6081 const GlobalValue *GV2 = NULL;
6082 int64_t Offset1 = 0;
6083 int64_t Offset2 = 0;
6084 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6085 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6086 if (isGA1 && isGA2 && GV1 == GV2)
6087 return Offset1 == (Offset2 + Dist*Bytes);
6092 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6093 /// it cannot be inferred.
6094 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6095 // If this is a GlobalAddress + cst, return the alignment.
6096 const GlobalValue *GV;
6097 int64_t GVOffset = 0;
6098 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6099 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6100 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6101 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6102 TLI.getTargetData());
6103 unsigned AlignBits = KnownZero.countTrailingOnes();
6104 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6106 return MinAlign(Align, GVOffset);
6109 // If this is a direct reference to a stack slot, use information about the
6110 // stack slot's alignment.
6111 int FrameIdx = 1 << 31;
6112 int64_t FrameOffset = 0;
6113 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6114 FrameIdx = FI->getIndex();
6115 } else if (isBaseWithConstantOffset(Ptr) &&
6116 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6118 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6119 FrameOffset = Ptr.getConstantOperandVal(1);
6122 if (FrameIdx != (1 << 31)) {
6123 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6124 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6132 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6133 unsigned GlobalAddressSDNode::getAddressSpace() const {
6134 return getGlobal()->getType()->getAddressSpace();
6138 Type *ConstantPoolSDNode::getType() const {
6139 if (isMachineConstantPoolEntry())
6140 return Val.MachineCPVal->getType();
6141 return Val.ConstVal->getType();
6144 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6146 unsigned &SplatBitSize,
6148 unsigned MinSplatBits,
6150 EVT VT = getValueType(0);
6151 assert(VT.isVector() && "Expected a vector type");
6152 unsigned sz = VT.getSizeInBits();
6153 if (MinSplatBits > sz)
6156 SplatValue = APInt(sz, 0);
6157 SplatUndef = APInt(sz, 0);
6159 // Get the bits. Bits with undefined values (when the corresponding element
6160 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6161 // in SplatValue. If any of the values are not constant, give up and return
6163 unsigned int nOps = getNumOperands();
6164 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6165 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6167 for (unsigned j = 0; j < nOps; ++j) {
6168 unsigned i = isBigEndian ? nOps-1-j : j;
6169 SDValue OpVal = getOperand(i);
6170 unsigned BitPos = j * EltBitSize;
6172 if (OpVal.getOpcode() == ISD::UNDEF)
6173 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6174 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6175 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6176 zextOrTrunc(sz) << BitPos;
6177 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6178 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6183 // The build_vector is all constants or undefs. Find the smallest element
6184 // size that splats the vector.
6186 HasAnyUndefs = (SplatUndef != 0);
6189 unsigned HalfSize = sz / 2;
6190 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6191 APInt LowValue = SplatValue.trunc(HalfSize);
6192 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6193 APInt LowUndef = SplatUndef.trunc(HalfSize);
6195 // If the two halves do not match (ignoring undef bits), stop here.
6196 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6197 MinSplatBits > HalfSize)
6200 SplatValue = HighValue | LowValue;
6201 SplatUndef = HighUndef & LowUndef;
6210 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6211 // Find the first non-undef value in the shuffle mask.
6213 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6216 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6218 // Make sure all remaining elements are either undef or the same as the first
6220 for (int Idx = Mask[i]; i != e; ++i)
6221 if (Mask[i] >= 0 && Mask[i] != Idx)
6227 static void checkForCyclesHelper(const SDNode *N,
6228 SmallPtrSet<const SDNode*, 32> &Visited,
6229 SmallPtrSet<const SDNode*, 32> &Checked) {
6230 // If this node has already been checked, don't check it again.
6231 if (Checked.count(N))
6234 // If a node has already been visited on this depth-first walk, reject it as
6236 if (!Visited.insert(N)) {
6237 dbgs() << "Offending node:\n";
6239 errs() << "Detected cycle in SelectionDAG\n";
6243 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6244 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6251 void llvm::checkForCycles(const llvm::SDNode *N) {
6253 assert(N && "Checking nonexistant SDNode");
6254 SmallPtrSet<const SDNode*, 32> visited;
6255 SmallPtrSet<const SDNode*, 32> checked;
6256 checkForCyclesHelper(N, visited, checked);
6260 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6261 checkForCycles(DAG->getRoot().getNode());