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());
443 const LoadSDNode *LD = cast<LoadSDNode>(N);
444 ID.AddInteger(LD->getMemoryVT().getRawBits());
445 ID.AddInteger(LD->getRawSubclassData());
446 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
450 const StoreSDNode *ST = cast<StoreSDNode>(N);
451 ID.AddInteger(ST->getMemoryVT().getRawBits());
452 ID.AddInteger(ST->getRawSubclassData());
453 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
456 case ISD::ATOMIC_CMP_SWAP:
457 case ISD::ATOMIC_SWAP:
458 case ISD::ATOMIC_LOAD_ADD:
459 case ISD::ATOMIC_LOAD_SUB:
460 case ISD::ATOMIC_LOAD_AND:
461 case ISD::ATOMIC_LOAD_OR:
462 case ISD::ATOMIC_LOAD_XOR:
463 case ISD::ATOMIC_LOAD_NAND:
464 case ISD::ATOMIC_LOAD_MIN:
465 case ISD::ATOMIC_LOAD_MAX:
466 case ISD::ATOMIC_LOAD_UMIN:
467 case ISD::ATOMIC_LOAD_UMAX:
468 case ISD::ATOMIC_LOAD:
469 case ISD::ATOMIC_STORE: {
470 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
471 ID.AddInteger(AT->getMemoryVT().getRawBits());
472 ID.AddInteger(AT->getRawSubclassData());
473 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
476 case ISD::PREFETCH: {
477 const MemSDNode *PF = cast<MemSDNode>(N);
478 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
481 case ISD::VECTOR_SHUFFLE: {
482 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
483 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
485 ID.AddInteger(SVN->getMaskElt(i));
488 case ISD::TargetBlockAddress:
489 case ISD::BlockAddress: {
490 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress());
491 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags());
494 } // end switch (N->getOpcode())
496 // Target specific memory nodes could also have address spaces to check.
497 if (N->isTargetMemoryOpcode())
498 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
501 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
503 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
504 AddNodeIDOpcode(ID, N->getOpcode());
505 // Add the return value info.
506 AddNodeIDValueTypes(ID, N->getVTList());
507 // Add the operand info.
508 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
510 // Handle SDNode leafs with special info.
511 AddNodeIDCustom(ID, N);
514 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
515 /// the CSE map that carries volatility, temporalness, indexing mode, and
516 /// extension/truncation information.
518 static inline unsigned
519 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
520 bool isNonTemporal, bool isInvariant) {
521 assert((ConvType & 3) == ConvType &&
522 "ConvType may not require more than 2 bits!");
523 assert((AM & 7) == AM &&
524 "AM may not require more than 3 bits!");
528 (isNonTemporal << 6) |
532 //===----------------------------------------------------------------------===//
533 // SelectionDAG Class
534 //===----------------------------------------------------------------------===//
536 /// doNotCSE - Return true if CSE should not be performed for this node.
537 static bool doNotCSE(SDNode *N) {
538 if (N->getValueType(0) == MVT::Glue)
539 return true; // Never CSE anything that produces a flag.
541 switch (N->getOpcode()) {
543 case ISD::HANDLENODE:
545 return true; // Never CSE these nodes.
548 // Check that remaining values produced are not flags.
549 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
550 if (N->getValueType(i) == MVT::Glue)
551 return true; // Never CSE anything that produces a flag.
556 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
558 void SelectionDAG::RemoveDeadNodes() {
559 // Create a dummy node (which is not added to allnodes), that adds a reference
560 // to the root node, preventing it from being deleted.
561 HandleSDNode Dummy(getRoot());
563 SmallVector<SDNode*, 128> DeadNodes;
565 // Add all obviously-dead nodes to the DeadNodes worklist.
566 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
568 DeadNodes.push_back(I);
570 RemoveDeadNodes(DeadNodes);
572 // If the root changed (e.g. it was a dead load, update the root).
573 setRoot(Dummy.getValue());
576 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
577 /// given list, and any nodes that become unreachable as a result.
578 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
580 // Process the worklist, deleting the nodes and adding their uses to the
582 while (!DeadNodes.empty()) {
583 SDNode *N = DeadNodes.pop_back_val();
585 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
586 DUL->NodeDeleted(N, 0);
588 // Take the node out of the appropriate CSE map.
589 RemoveNodeFromCSEMaps(N);
591 // Next, brutally remove the operand list. This is safe to do, as there are
592 // no cycles in the graph.
593 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
595 SDNode *Operand = Use.getNode();
598 // Now that we removed this operand, see if there are no uses of it left.
599 if (Operand->use_empty())
600 DeadNodes.push_back(Operand);
607 void SelectionDAG::RemoveDeadNode(SDNode *N){
608 SmallVector<SDNode*, 16> DeadNodes(1, N);
610 // Create a dummy node that adds a reference to the root node, preventing
611 // it from being deleted. (This matters if the root is an operand of the
613 HandleSDNode Dummy(getRoot());
615 RemoveDeadNodes(DeadNodes);
618 void SelectionDAG::DeleteNode(SDNode *N) {
619 // First take this out of the appropriate CSE map.
620 RemoveNodeFromCSEMaps(N);
622 // Finally, remove uses due to operands of this node, remove from the
623 // AllNodes list, and delete the node.
624 DeleteNodeNotInCSEMaps(N);
627 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
628 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
629 assert(N->use_empty() && "Cannot delete a node that is not dead!");
631 // Drop all of the operands and decrement used node's use counts.
637 void SelectionDAG::DeallocateNode(SDNode *N) {
638 if (N->OperandsNeedDelete)
639 delete[] N->OperandList;
641 // Set the opcode to DELETED_NODE to help catch bugs when node
642 // memory is reallocated.
643 N->NodeType = ISD::DELETED_NODE;
645 NodeAllocator.Deallocate(AllNodes.remove(N));
647 // Remove the ordering of this node.
650 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
651 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
652 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
653 DbgVals[i]->setIsInvalidated();
656 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
657 /// correspond to it. This is useful when we're about to delete or repurpose
658 /// the node. We don't want future request for structurally identical nodes
659 /// to return N anymore.
660 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
662 switch (N->getOpcode()) {
663 case ISD::HANDLENODE: return false; // noop.
665 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
666 "Cond code doesn't exist!");
667 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
668 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
670 case ISD::ExternalSymbol:
671 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
673 case ISD::TargetExternalSymbol: {
674 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
675 Erased = TargetExternalSymbols.erase(
676 std::pair<std::string,unsigned char>(ESN->getSymbol(),
677 ESN->getTargetFlags()));
680 case ISD::VALUETYPE: {
681 EVT VT = cast<VTSDNode>(N)->getVT();
682 if (VT.isExtended()) {
683 Erased = ExtendedValueTypeNodes.erase(VT);
685 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
686 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
691 // Remove it from the CSE Map.
692 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
693 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
694 Erased = CSEMap.RemoveNode(N);
698 // Verify that the node was actually in one of the CSE maps, unless it has a
699 // flag result (which cannot be CSE'd) or is one of the special cases that are
700 // not subject to CSE.
701 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
702 !N->isMachineOpcode() && !doNotCSE(N)) {
705 llvm_unreachable("Node is not in map!");
711 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
712 /// maps and modified in place. Add it back to the CSE maps, unless an identical
713 /// node already exists, in which case transfer all its users to the existing
714 /// node. This transfer can potentially trigger recursive merging.
717 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
718 // For node types that aren't CSE'd, just act as if no identical node
721 SDNode *Existing = CSEMap.GetOrInsertNode(N);
723 // If there was already an existing matching node, use ReplaceAllUsesWith
724 // to replace the dead one with the existing one. This can cause
725 // recursive merging of other unrelated nodes down the line.
726 ReplaceAllUsesWith(N, Existing);
728 // N is now dead. Inform the listeners and delete it.
729 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
730 DUL->NodeDeleted(N, Existing);
731 DeleteNodeNotInCSEMaps(N);
736 // If the node doesn't already exist, we updated it. Inform listeners.
737 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
741 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
742 /// were replaced with those specified. If this node is never memoized,
743 /// return null, otherwise return a pointer to the slot it would take. If a
744 /// node already exists with these operands, the slot will be non-null.
745 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
750 SDValue Ops[] = { Op };
752 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
753 AddNodeIDCustom(ID, N);
754 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
758 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
759 /// were replaced with those specified. If this node is never memoized,
760 /// return null, otherwise return a pointer to the slot it would take. If a
761 /// node already exists with these operands, the slot will be non-null.
762 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
763 SDValue Op1, SDValue Op2,
768 SDValue Ops[] = { Op1, Op2 };
770 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
771 AddNodeIDCustom(ID, N);
772 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
777 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
778 /// were replaced with those specified. If this node is never memoized,
779 /// return null, otherwise return a pointer to the slot it would take. If a
780 /// node already exists with these operands, the slot will be non-null.
781 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
782 const SDValue *Ops,unsigned NumOps,
788 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
789 AddNodeIDCustom(ID, N);
790 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
795 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
796 static void VerifyNodeCommon(SDNode *N) {
797 switch (N->getOpcode()) {
800 case ISD::BUILD_PAIR: {
801 EVT VT = N->getValueType(0);
802 assert(N->getNumValues() == 1 && "Too many results!");
803 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
804 "Wrong return type!");
805 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
806 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
807 "Mismatched operand types!");
808 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
809 "Wrong operand type!");
810 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
811 "Wrong return type size");
814 case ISD::BUILD_VECTOR: {
815 assert(N->getNumValues() == 1 && "Too many results!");
816 assert(N->getValueType(0).isVector() && "Wrong return type!");
817 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
818 "Wrong number of operands!");
819 EVT EltVT = N->getValueType(0).getVectorElementType();
820 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
821 assert((I->getValueType() == EltVT ||
822 (EltVT.isInteger() && I->getValueType().isInteger() &&
823 EltVT.bitsLE(I->getValueType()))) &&
824 "Wrong operand type!");
825 assert(I->getValueType() == N->getOperand(0).getValueType() &&
826 "Operands must all have the same type");
833 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
834 static void VerifySDNode(SDNode *N) {
835 // The SDNode allocators cannot be used to allocate nodes with fields that are
836 // not present in an SDNode!
837 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
838 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
839 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
840 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
841 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
842 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
843 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
844 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
845 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
846 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
847 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
848 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
849 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
850 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
851 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
852 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
853 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
854 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
855 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
860 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
862 static void VerifyMachineNode(SDNode *N) {
863 // The MachineNode allocators cannot be used to allocate nodes with fields
864 // that are not present in a MachineNode!
865 // Currently there are no such nodes.
871 /// getEVTAlignment - Compute the default alignment value for the
874 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
875 Type *Ty = VT == MVT::iPTR ?
876 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
877 VT.getTypeForEVT(*getContext());
879 return TLI.getTargetData()->getABITypeAlignment(Ty);
882 // EntryNode could meaningfully have debug info if we can find it...
883 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
884 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
885 OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
886 Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
887 AllNodes.push_back(&EntryNode);
888 Ordering = new SDNodeOrdering();
889 DbgInfo = new SDDbgInfo();
892 void SelectionDAG::init(MachineFunction &mf) {
894 Context = &mf.getFunction()->getContext();
897 SelectionDAG::~SelectionDAG() {
898 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
904 void SelectionDAG::allnodes_clear() {
905 assert(&*AllNodes.begin() == &EntryNode);
906 AllNodes.remove(AllNodes.begin());
907 while (!AllNodes.empty())
908 DeallocateNode(AllNodes.begin());
911 void SelectionDAG::clear() {
913 OperandAllocator.Reset();
916 ExtendedValueTypeNodes.clear();
917 ExternalSymbols.clear();
918 TargetExternalSymbols.clear();
919 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
920 static_cast<CondCodeSDNode*>(0));
921 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
922 static_cast<SDNode*>(0));
924 EntryNode.UseList = 0;
925 AllNodes.push_back(&EntryNode);
926 Root = getEntryNode();
931 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
932 return VT.bitsGT(Op.getValueType()) ?
933 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
934 getNode(ISD::TRUNCATE, DL, VT, Op);
937 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
938 return VT.bitsGT(Op.getValueType()) ?
939 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
940 getNode(ISD::TRUNCATE, DL, VT, Op);
943 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
944 return VT.bitsGT(Op.getValueType()) ?
945 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
946 getNode(ISD::TRUNCATE, DL, VT, Op);
949 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
950 assert(!VT.isVector() &&
951 "getZeroExtendInReg should use the vector element type instead of "
953 if (Op.getValueType() == VT) return Op;
954 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
955 APInt Imm = APInt::getLowBitsSet(BitWidth,
957 return getNode(ISD::AND, DL, Op.getValueType(), Op,
958 getConstant(Imm, Op.getValueType()));
961 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
963 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
964 EVT EltVT = VT.getScalarType();
966 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
967 return getNode(ISD::XOR, DL, VT, Val, NegOne);
970 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
971 EVT EltVT = VT.getScalarType();
972 assert((EltVT.getSizeInBits() >= 64 ||
973 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
974 "getConstant with a uint64_t value that doesn't fit in the type!");
975 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
978 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
979 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
982 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
983 assert(VT.isInteger() && "Cannot create FP integer constant!");
985 EVT EltVT = VT.getScalarType();
986 const ConstantInt *Elt = &Val;
988 // In some cases the vector type is legal but the element type is illegal and
989 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
990 // inserted value (the type does not need to match the vector element type).
991 // Any extra bits introduced will be truncated away.
992 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
993 TargetLowering::TypePromoteInteger) {
994 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
995 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
996 Elt = ConstantInt::get(*getContext(), NewVal);
999 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1000 "APInt size does not match type size!");
1001 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1002 FoldingSetNodeID ID;
1003 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1007 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1009 return SDValue(N, 0);
1012 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1013 CSEMap.InsertNode(N, IP);
1014 AllNodes.push_back(N);
1017 SDValue Result(N, 0);
1018 if (VT.isVector()) {
1019 SmallVector<SDValue, 8> Ops;
1020 Ops.assign(VT.getVectorNumElements(), Result);
1021 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1026 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1027 return getConstant(Val, TLI.getPointerTy(), isTarget);
1031 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1032 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1035 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1036 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1038 EVT EltVT = VT.getScalarType();
1040 // Do the map lookup using the actual bit pattern for the floating point
1041 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1042 // we don't have issues with SNANs.
1043 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1044 FoldingSetNodeID ID;
1045 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1049 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1051 return SDValue(N, 0);
1054 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1055 CSEMap.InsertNode(N, IP);
1056 AllNodes.push_back(N);
1059 SDValue Result(N, 0);
1060 if (VT.isVector()) {
1061 SmallVector<SDValue, 8> Ops;
1062 Ops.assign(VT.getVectorNumElements(), Result);
1063 // FIXME DebugLoc info might be appropriate here
1064 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1069 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1070 EVT EltVT = VT.getScalarType();
1071 if (EltVT==MVT::f32)
1072 return getConstantFP(APFloat((float)Val), VT, isTarget);
1073 else if (EltVT==MVT::f64)
1074 return getConstantFP(APFloat(Val), VT, isTarget);
1075 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::f16) {
1077 APFloat apf = APFloat(Val);
1078 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1080 return getConstantFP(apf, VT, isTarget);
1082 llvm_unreachable("Unsupported type in getConstantFP");
1085 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1086 EVT VT, int64_t Offset,
1088 unsigned char TargetFlags) {
1089 assert((TargetFlags == 0 || isTargetGA) &&
1090 "Cannot set target flags on target-independent globals");
1092 // Truncate (with sign-extension) the offset value to the pointer size.
1093 EVT PTy = TLI.getPointerTy();
1094 unsigned BitWidth = PTy.getSizeInBits();
1096 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth));
1098 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1100 // If GV is an alias then use the aliasee for determining thread-localness.
1101 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1102 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1106 if (GVar && GVar->isThreadLocal())
1107 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1109 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1111 FoldingSetNodeID ID;
1112 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1114 ID.AddInteger(Offset);
1115 ID.AddInteger(TargetFlags);
1116 ID.AddInteger(GV->getType()->getAddressSpace());
1118 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1119 return SDValue(E, 0);
1121 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1122 Offset, TargetFlags);
1123 CSEMap.InsertNode(N, IP);
1124 AllNodes.push_back(N);
1125 return SDValue(N, 0);
1128 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1129 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1130 FoldingSetNodeID ID;
1131 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1134 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1135 return SDValue(E, 0);
1137 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1138 CSEMap.InsertNode(N, IP);
1139 AllNodes.push_back(N);
1140 return SDValue(N, 0);
1143 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1144 unsigned char TargetFlags) {
1145 assert((TargetFlags == 0 || isTarget) &&
1146 "Cannot set target flags on target-independent jump tables");
1147 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1148 FoldingSetNodeID ID;
1149 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1151 ID.AddInteger(TargetFlags);
1153 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1154 return SDValue(E, 0);
1156 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1158 CSEMap.InsertNode(N, IP);
1159 AllNodes.push_back(N);
1160 return SDValue(N, 0);
1163 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1164 unsigned Alignment, int Offset,
1166 unsigned char TargetFlags) {
1167 assert((TargetFlags == 0 || isTarget) &&
1168 "Cannot set target flags on target-independent globals");
1170 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1171 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1172 FoldingSetNodeID ID;
1173 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1174 ID.AddInteger(Alignment);
1175 ID.AddInteger(Offset);
1177 ID.AddInteger(TargetFlags);
1179 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1180 return SDValue(E, 0);
1182 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1183 Alignment, TargetFlags);
1184 CSEMap.InsertNode(N, IP);
1185 AllNodes.push_back(N);
1186 return SDValue(N, 0);
1190 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1191 unsigned Alignment, int Offset,
1193 unsigned char TargetFlags) {
1194 assert((TargetFlags == 0 || isTarget) &&
1195 "Cannot set target flags on target-independent globals");
1197 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1198 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1199 FoldingSetNodeID ID;
1200 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1201 ID.AddInteger(Alignment);
1202 ID.AddInteger(Offset);
1203 C->addSelectionDAGCSEId(ID);
1204 ID.AddInteger(TargetFlags);
1206 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1207 return SDValue(E, 0);
1209 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1210 Alignment, TargetFlags);
1211 CSEMap.InsertNode(N, IP);
1212 AllNodes.push_back(N);
1213 return SDValue(N, 0);
1216 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1217 FoldingSetNodeID ID;
1218 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1221 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1222 return SDValue(E, 0);
1224 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1225 CSEMap.InsertNode(N, IP);
1226 AllNodes.push_back(N);
1227 return SDValue(N, 0);
1230 SDValue SelectionDAG::getValueType(EVT VT) {
1231 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1232 ValueTypeNodes.size())
1233 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1235 SDNode *&N = VT.isExtended() ?
1236 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1238 if (N) return SDValue(N, 0);
1239 N = new (NodeAllocator) VTSDNode(VT);
1240 AllNodes.push_back(N);
1241 return SDValue(N, 0);
1244 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1245 SDNode *&N = ExternalSymbols[Sym];
1246 if (N) return SDValue(N, 0);
1247 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1248 AllNodes.push_back(N);
1249 return SDValue(N, 0);
1252 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1253 unsigned char TargetFlags) {
1255 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1257 if (N) return SDValue(N, 0);
1258 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1259 AllNodes.push_back(N);
1260 return SDValue(N, 0);
1263 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1264 if ((unsigned)Cond >= CondCodeNodes.size())
1265 CondCodeNodes.resize(Cond+1);
1267 if (CondCodeNodes[Cond] == 0) {
1268 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1269 CondCodeNodes[Cond] = N;
1270 AllNodes.push_back(N);
1273 return SDValue(CondCodeNodes[Cond], 0);
1276 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1277 // the shuffle mask M that point at N1 to point at N2, and indices that point
1278 // N2 to point at N1.
1279 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1281 int NElts = M.size();
1282 for (int i = 0; i != NElts; ++i) {
1290 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1291 SDValue N2, const int *Mask) {
1292 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1293 assert(VT.isVector() && N1.getValueType().isVector() &&
1294 "Vector Shuffle VTs must be a vectors");
1295 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1296 && "Vector Shuffle VTs must have same element type");
1298 // Canonicalize shuffle undef, undef -> undef
1299 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1300 return getUNDEF(VT);
1302 // Validate that all indices in Mask are within the range of the elements
1303 // input to the shuffle.
1304 unsigned NElts = VT.getVectorNumElements();
1305 SmallVector<int, 8> MaskVec;
1306 for (unsigned i = 0; i != NElts; ++i) {
1307 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1308 MaskVec.push_back(Mask[i]);
1311 // Canonicalize shuffle v, v -> v, undef
1314 for (unsigned i = 0; i != NElts; ++i)
1315 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1318 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1319 if (N1.getOpcode() == ISD::UNDEF)
1320 commuteShuffle(N1, N2, MaskVec);
1322 // Canonicalize all index into lhs, -> shuffle lhs, undef
1323 // Canonicalize all index into rhs, -> shuffle rhs, undef
1324 bool AllLHS = true, AllRHS = true;
1325 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1326 for (unsigned i = 0; i != NElts; ++i) {
1327 if (MaskVec[i] >= (int)NElts) {
1332 } else if (MaskVec[i] >= 0) {
1336 if (AllLHS && AllRHS)
1337 return getUNDEF(VT);
1338 if (AllLHS && !N2Undef)
1342 commuteShuffle(N1, N2, MaskVec);
1345 // If Identity shuffle, or all shuffle in to undef, return that node.
1346 bool AllUndef = true;
1347 bool Identity = true;
1348 for (unsigned i = 0; i != NElts; ++i) {
1349 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1350 if (MaskVec[i] >= 0) AllUndef = false;
1352 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1355 return getUNDEF(VT);
1357 FoldingSetNodeID ID;
1358 SDValue Ops[2] = { N1, N2 };
1359 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1360 for (unsigned i = 0; i != NElts; ++i)
1361 ID.AddInteger(MaskVec[i]);
1364 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1365 return SDValue(E, 0);
1367 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1368 // SDNode doesn't have access to it. This memory will be "leaked" when
1369 // the node is deallocated, but recovered when the NodeAllocator is released.
1370 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1371 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1373 ShuffleVectorSDNode *N =
1374 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1375 CSEMap.InsertNode(N, IP);
1376 AllNodes.push_back(N);
1377 return SDValue(N, 0);
1380 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1381 SDValue Val, SDValue DTy,
1382 SDValue STy, SDValue Rnd, SDValue Sat,
1383 ISD::CvtCode Code) {
1384 // If the src and dest types are the same and the conversion is between
1385 // integer types of the same sign or two floats, no conversion is necessary.
1387 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1390 FoldingSetNodeID ID;
1391 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1392 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1394 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1395 return SDValue(E, 0);
1397 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1399 CSEMap.InsertNode(N, IP);
1400 AllNodes.push_back(N);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1407 ID.AddInteger(RegNo);
1409 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1410 return SDValue(E, 0);
1412 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1413 CSEMap.InsertNode(N, IP);
1414 AllNodes.push_back(N);
1415 return SDValue(N, 0);
1418 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1419 FoldingSetNodeID ID;
1420 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1421 ID.AddPointer(RegMask);
1423 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1424 return SDValue(E, 0);
1426 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1427 CSEMap.InsertNode(N, IP);
1428 AllNodes.push_back(N);
1429 return SDValue(N, 0);
1432 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1433 FoldingSetNodeID ID;
1434 SDValue Ops[] = { Root };
1435 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1436 ID.AddPointer(Label);
1438 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1439 return SDValue(E, 0);
1441 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1442 CSEMap.InsertNode(N, IP);
1443 AllNodes.push_back(N);
1444 return SDValue(N, 0);
1448 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1450 unsigned char TargetFlags) {
1451 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1453 FoldingSetNodeID ID;
1454 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1456 ID.AddInteger(TargetFlags);
1458 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1459 return SDValue(E, 0);
1461 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, TargetFlags);
1462 CSEMap.InsertNode(N, IP);
1463 AllNodes.push_back(N);
1464 return SDValue(N, 0);
1467 SDValue SelectionDAG::getSrcValue(const Value *V) {
1468 assert((!V || V->getType()->isPointerTy()) &&
1469 "SrcValue is not a pointer?");
1471 FoldingSetNodeID ID;
1472 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1476 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1477 return SDValue(E, 0);
1479 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1480 CSEMap.InsertNode(N, IP);
1481 AllNodes.push_back(N);
1482 return SDValue(N, 0);
1485 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1486 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1487 FoldingSetNodeID ID;
1488 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1492 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1493 return SDValue(E, 0);
1495 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1496 CSEMap.InsertNode(N, IP);
1497 AllNodes.push_back(N);
1498 return SDValue(N, 0);
1502 /// getShiftAmountOperand - Return the specified value casted to
1503 /// the target's desired shift amount type.
1504 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1505 EVT OpTy = Op.getValueType();
1506 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1507 if (OpTy == ShTy || OpTy.isVector()) return Op;
1509 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1510 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1513 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1514 /// specified value type.
1515 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1516 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1517 unsigned ByteSize = VT.getStoreSize();
1518 Type *Ty = VT.getTypeForEVT(*getContext());
1519 unsigned StackAlign =
1520 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1522 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1523 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1526 /// CreateStackTemporary - Create a stack temporary suitable for holding
1527 /// either of the specified value types.
1528 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1529 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1530 VT2.getStoreSizeInBits())/8;
1531 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1532 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1533 const TargetData *TD = TLI.getTargetData();
1534 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1535 TD->getPrefTypeAlignment(Ty2));
1537 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1538 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1539 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1542 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1543 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1544 // These setcc operations always fold.
1548 case ISD::SETFALSE2: return getConstant(0, VT);
1550 case ISD::SETTRUE2: return getConstant(1, VT);
1562 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1566 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1567 const APInt &C2 = N2C->getAPIntValue();
1568 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1569 const APInt &C1 = N1C->getAPIntValue();
1572 default: llvm_unreachable("Unknown integer setcc!");
1573 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1574 case ISD::SETNE: return getConstant(C1 != C2, VT);
1575 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1576 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1577 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1578 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1579 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1580 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1581 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1582 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1586 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1587 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1588 // No compile time operations on this type yet.
1589 if (N1C->getValueType(0) == MVT::ppcf128)
1592 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1595 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1596 return getUNDEF(VT);
1598 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1599 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1600 return getUNDEF(VT);
1602 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1603 R==APFloat::cmpLessThan, VT);
1604 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1605 return getUNDEF(VT);
1607 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1608 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1609 return getUNDEF(VT);
1611 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1612 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1613 return getUNDEF(VT);
1615 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1616 R==APFloat::cmpEqual, VT);
1617 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1618 return getUNDEF(VT);
1620 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1621 R==APFloat::cmpEqual, VT);
1622 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1623 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1624 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1625 R==APFloat::cmpEqual, VT);
1626 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1627 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1628 R==APFloat::cmpLessThan, VT);
1629 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1630 R==APFloat::cmpUnordered, VT);
1631 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1632 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1635 // Ensure that the constant occurs on the RHS.
1636 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1640 // Could not fold it.
1644 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1645 /// use this predicate to simplify operations downstream.
1646 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1647 // This predicate is not safe for vector operations.
1648 if (Op.getValueType().isVector())
1651 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1652 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1655 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1656 /// this predicate to simplify operations downstream. Mask is known to be zero
1657 /// for bits that V cannot have.
1658 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1659 unsigned Depth) const {
1660 APInt KnownZero, KnownOne;
1661 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1662 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1663 return (KnownZero & Mask) == Mask;
1666 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1667 /// known to be either zero or one and return them in the KnownZero/KnownOne
1668 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1670 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1671 APInt &KnownOne, unsigned Depth) const {
1672 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1674 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1676 return; // Limit search depth.
1678 APInt KnownZero2, KnownOne2;
1680 switch (Op.getOpcode()) {
1682 // We know all of the bits for a constant!
1683 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1684 KnownZero = ~KnownOne;
1687 // If either the LHS or the RHS are Zero, the result is zero.
1688 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1689 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1690 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1691 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1693 // Output known-1 bits are only known if set in both the LHS & RHS.
1694 KnownOne &= KnownOne2;
1695 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1696 KnownZero |= KnownZero2;
1699 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1700 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1701 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1702 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1704 // Output known-0 bits are only known if clear in both the LHS & RHS.
1705 KnownZero &= KnownZero2;
1706 // Output known-1 are known to be set if set in either the LHS | RHS.
1707 KnownOne |= KnownOne2;
1710 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1711 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1712 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1713 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1715 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1716 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1717 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1718 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1719 KnownZero = KnownZeroOut;
1723 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1724 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1725 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1726 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1728 // If low bits are zero in either operand, output low known-0 bits.
1729 // Also compute a conserative estimate for high known-0 bits.
1730 // More trickiness is possible, but this is sufficient for the
1731 // interesting case of alignment computation.
1732 KnownOne.clearAllBits();
1733 unsigned TrailZ = KnownZero.countTrailingOnes() +
1734 KnownZero2.countTrailingOnes();
1735 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1736 KnownZero2.countLeadingOnes(),
1737 BitWidth) - BitWidth;
1739 TrailZ = std::min(TrailZ, BitWidth);
1740 LeadZ = std::min(LeadZ, BitWidth);
1741 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1742 APInt::getHighBitsSet(BitWidth, LeadZ);
1746 // For the purposes of computing leading zeros we can conservatively
1747 // treat a udiv as a logical right shift by the power of 2 known to
1748 // be less than the denominator.
1749 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1750 unsigned LeadZ = KnownZero2.countLeadingOnes();
1752 KnownOne2.clearAllBits();
1753 KnownZero2.clearAllBits();
1754 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1755 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1756 if (RHSUnknownLeadingOnes != BitWidth)
1757 LeadZ = std::min(BitWidth,
1758 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1760 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1764 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1765 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1766 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1767 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1769 // Only known if known in both the LHS and RHS.
1770 KnownOne &= KnownOne2;
1771 KnownZero &= KnownZero2;
1773 case ISD::SELECT_CC:
1774 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1775 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1776 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1777 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1779 // Only known if known in both the LHS and RHS.
1780 KnownOne &= KnownOne2;
1781 KnownZero &= KnownZero2;
1789 if (Op.getResNo() != 1)
1791 // The boolean result conforms to getBooleanContents. Fall through.
1793 // If we know the result of a setcc has the top bits zero, use this info.
1794 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1795 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1796 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1799 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1800 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1801 unsigned ShAmt = SA->getZExtValue();
1803 // If the shift count is an invalid immediate, don't do anything.
1804 if (ShAmt >= BitWidth)
1807 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1808 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1809 KnownZero <<= ShAmt;
1811 // low bits known zero.
1812 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1816 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1817 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1818 unsigned ShAmt = SA->getZExtValue();
1820 // If the shift count is an invalid immediate, don't do anything.
1821 if (ShAmt >= BitWidth)
1824 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1825 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1826 KnownZero = KnownZero.lshr(ShAmt);
1827 KnownOne = KnownOne.lshr(ShAmt);
1829 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1830 KnownZero |= HighBits; // High bits known zero.
1834 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1835 unsigned ShAmt = SA->getZExtValue();
1837 // If the shift count is an invalid immediate, don't do anything.
1838 if (ShAmt >= BitWidth)
1841 // If any of the demanded bits are produced by the sign extension, we also
1842 // demand the input sign bit.
1843 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1845 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1846 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1847 KnownZero = KnownZero.lshr(ShAmt);
1848 KnownOne = KnownOne.lshr(ShAmt);
1850 // Handle the sign bits.
1851 APInt SignBit = APInt::getSignBit(BitWidth);
1852 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1854 if (KnownZero.intersects(SignBit)) {
1855 KnownZero |= HighBits; // New bits are known zero.
1856 } else if (KnownOne.intersects(SignBit)) {
1857 KnownOne |= HighBits; // New bits are known one.
1861 case ISD::SIGN_EXTEND_INREG: {
1862 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1863 unsigned EBits = EVT.getScalarType().getSizeInBits();
1865 // Sign extension. Compute the demanded bits in the result that are not
1866 // present in the input.
1867 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1869 APInt InSignBit = APInt::getSignBit(EBits);
1870 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1872 // If the sign extended bits are demanded, we know that the sign
1874 InSignBit = InSignBit.zext(BitWidth);
1875 if (NewBits.getBoolValue())
1876 InputDemandedBits |= InSignBit;
1878 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1879 KnownOne &= InputDemandedBits;
1880 KnownZero &= InputDemandedBits;
1881 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1883 // If the sign bit of the input is known set or clear, then we know the
1884 // top bits of the result.
1885 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1886 KnownZero |= NewBits;
1887 KnownOne &= ~NewBits;
1888 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1889 KnownOne |= NewBits;
1890 KnownZero &= ~NewBits;
1891 } else { // Input sign bit unknown
1892 KnownZero &= ~NewBits;
1893 KnownOne &= ~NewBits;
1898 case ISD::CTTZ_ZERO_UNDEF:
1900 case ISD::CTLZ_ZERO_UNDEF:
1902 unsigned LowBits = Log2_32(BitWidth)+1;
1903 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1904 KnownOne.clearAllBits();
1908 LoadSDNode *LD = cast<LoadSDNode>(Op);
1909 if (ISD::isZEXTLoad(Op.getNode())) {
1910 EVT VT = LD->getMemoryVT();
1911 unsigned MemBits = VT.getScalarType().getSizeInBits();
1912 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
1913 } else if (const MDNode *Ranges = LD->getRanges()) {
1914 computeMaskedBitsLoad(*Ranges, KnownZero);
1918 case ISD::ZERO_EXTEND: {
1919 EVT InVT = Op.getOperand(0).getValueType();
1920 unsigned InBits = InVT.getScalarType().getSizeInBits();
1921 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1922 KnownZero = KnownZero.trunc(InBits);
1923 KnownOne = KnownOne.trunc(InBits);
1924 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1925 KnownZero = KnownZero.zext(BitWidth);
1926 KnownOne = KnownOne.zext(BitWidth);
1927 KnownZero |= NewBits;
1930 case ISD::SIGN_EXTEND: {
1931 EVT InVT = Op.getOperand(0).getValueType();
1932 unsigned InBits = InVT.getScalarType().getSizeInBits();
1933 APInt InSignBit = APInt::getSignBit(InBits);
1934 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1936 KnownZero = KnownZero.trunc(InBits);
1937 KnownOne = KnownOne.trunc(InBits);
1938 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1940 // Note if the sign bit is known to be zero or one.
1941 bool SignBitKnownZero = KnownZero.isNegative();
1942 bool SignBitKnownOne = KnownOne.isNegative();
1943 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1944 "Sign bit can't be known to be both zero and one!");
1946 KnownZero = KnownZero.zext(BitWidth);
1947 KnownOne = KnownOne.zext(BitWidth);
1949 // If the sign bit is known zero or one, the top bits match.
1950 if (SignBitKnownZero)
1951 KnownZero |= NewBits;
1952 else if (SignBitKnownOne)
1953 KnownOne |= NewBits;
1956 case ISD::ANY_EXTEND: {
1957 EVT InVT = Op.getOperand(0).getValueType();
1958 unsigned InBits = InVT.getScalarType().getSizeInBits();
1959 KnownZero = KnownZero.trunc(InBits);
1960 KnownOne = KnownOne.trunc(InBits);
1961 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1962 KnownZero = KnownZero.zext(BitWidth);
1963 KnownOne = KnownOne.zext(BitWidth);
1966 case ISD::TRUNCATE: {
1967 EVT InVT = Op.getOperand(0).getValueType();
1968 unsigned InBits = InVT.getScalarType().getSizeInBits();
1969 KnownZero = KnownZero.zext(InBits);
1970 KnownOne = KnownOne.zext(InBits);
1971 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1972 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1973 KnownZero = KnownZero.trunc(BitWidth);
1974 KnownOne = KnownOne.trunc(BitWidth);
1977 case ISD::AssertZext: {
1978 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1979 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1980 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1981 KnownZero |= (~InMask);
1982 KnownOne &= (~KnownZero);
1986 // All bits are zero except the low bit.
1987 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1991 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1992 // We know that the top bits of C-X are clear if X contains less bits
1993 // than C (i.e. no wrap-around can happen). For example, 20-X is
1994 // positive if we can prove that X is >= 0 and < 16.
1995 if (CLHS->getAPIntValue().isNonNegative()) {
1996 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1997 // NLZ can't be BitWidth with no sign bit
1998 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1999 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2001 // If all of the MaskV bits are known to be zero, then we know the
2002 // output top bits are zero, because we now know that the output is
2004 if ((KnownZero2 & MaskV) == MaskV) {
2005 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2006 // Top bits known zero.
2007 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2015 // Output known-0 bits are known if clear or set in both the low clear bits
2016 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2017 // low 3 bits clear.
2018 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2019 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2020 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2022 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2023 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2024 KnownZeroOut = std::min(KnownZeroOut,
2025 KnownZero2.countTrailingOnes());
2027 if (Op.getOpcode() == ISD::ADD) {
2028 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2032 // With ADDE, a carry bit may be added in, so we can only use this
2033 // information if we know (at least) that the low two bits are clear. We
2034 // then return to the caller that the low bit is unknown but that other bits
2036 if (KnownZeroOut >= 2) // ADDE
2037 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2041 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2042 const APInt &RA = Rem->getAPIntValue().abs();
2043 if (RA.isPowerOf2()) {
2044 APInt LowBits = RA - 1;
2045 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2046 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2048 // The low bits of the first operand are unchanged by the srem.
2049 KnownZero = KnownZero2 & LowBits;
2050 KnownOne = KnownOne2 & LowBits;
2052 // If the first operand is non-negative or has all low bits zero, then
2053 // the upper bits are all zero.
2054 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2055 KnownZero |= ~LowBits;
2057 // If the first operand is negative and not all low bits are zero, then
2058 // the upper bits are all one.
2059 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2060 KnownOne |= ~LowBits;
2061 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2066 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2067 const APInt &RA = Rem->getAPIntValue();
2068 if (RA.isPowerOf2()) {
2069 APInt LowBits = (RA - 1);
2070 KnownZero |= ~LowBits;
2071 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2072 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2077 // Since the result is less than or equal to either operand, any leading
2078 // zero bits in either operand must also exist in the result.
2079 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2080 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2082 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2083 KnownZero2.countLeadingOnes());
2084 KnownOne.clearAllBits();
2085 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2088 case ISD::FrameIndex:
2089 case ISD::TargetFrameIndex:
2090 if (unsigned Align = InferPtrAlignment(Op)) {
2091 // The low bits are known zero if the pointer is aligned.
2092 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2098 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2101 case ISD::INTRINSIC_WO_CHAIN:
2102 case ISD::INTRINSIC_W_CHAIN:
2103 case ISD::INTRINSIC_VOID:
2104 // Allow the target to implement this method for its nodes.
2105 TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2110 /// ComputeNumSignBits - Return the number of times the sign bit of the
2111 /// register is replicated into the other bits. We know that at least 1 bit
2112 /// is always equal to the sign bit (itself), but other cases can give us
2113 /// information. For example, immediately after an "SRA X, 2", we know that
2114 /// the top 3 bits are all equal to each other, so we return 3.
2115 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2116 EVT VT = Op.getValueType();
2117 assert(VT.isInteger() && "Invalid VT!");
2118 unsigned VTBits = VT.getScalarType().getSizeInBits();
2120 unsigned FirstAnswer = 1;
2123 return 1; // Limit search depth.
2125 switch (Op.getOpcode()) {
2127 case ISD::AssertSext:
2128 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2129 return VTBits-Tmp+1;
2130 case ISD::AssertZext:
2131 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2134 case ISD::Constant: {
2135 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2136 return Val.getNumSignBits();
2139 case ISD::SIGN_EXTEND:
2140 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2141 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2143 case ISD::SIGN_EXTEND_INREG:
2144 // Max of the input and what this extends.
2146 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2149 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2150 return std::max(Tmp, Tmp2);
2153 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2154 // SRA X, C -> adds C sign bits.
2155 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2156 Tmp += C->getZExtValue();
2157 if (Tmp > VTBits) Tmp = VTBits;
2161 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2162 // shl destroys sign bits.
2163 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2164 if (C->getZExtValue() >= VTBits || // Bad shift.
2165 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2166 return Tmp - C->getZExtValue();
2171 case ISD::XOR: // NOT is handled here.
2172 // Logical binary ops preserve the number of sign bits at the worst.
2173 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2175 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2176 FirstAnswer = std::min(Tmp, Tmp2);
2177 // We computed what we know about the sign bits as our first
2178 // answer. Now proceed to the generic code that uses
2179 // ComputeMaskedBits, and pick whichever answer is better.
2184 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2185 if (Tmp == 1) return 1; // Early out.
2186 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2187 return std::min(Tmp, Tmp2);
2195 if (Op.getResNo() != 1)
2197 // The boolean result conforms to getBooleanContents. Fall through.
2199 // If setcc returns 0/-1, all bits are sign bits.
2200 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2201 TargetLowering::ZeroOrNegativeOneBooleanContent)
2206 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2207 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2209 // Handle rotate right by N like a rotate left by 32-N.
2210 if (Op.getOpcode() == ISD::ROTR)
2211 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2213 // If we aren't rotating out all of the known-in sign bits, return the
2214 // number that are left. This handles rotl(sext(x), 1) for example.
2215 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2216 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2220 // Add can have at most one carry bit. Thus we know that the output
2221 // is, at worst, one more bit than the inputs.
2222 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2223 if (Tmp == 1) return 1; // Early out.
2225 // Special case decrementing a value (ADD X, -1):
2226 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2227 if (CRHS->isAllOnesValue()) {
2228 APInt KnownZero, KnownOne;
2229 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2231 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2233 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2236 // If we are subtracting one from a positive number, there is no carry
2237 // out of the result.
2238 if (KnownZero.isNegative())
2242 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2243 if (Tmp2 == 1) return 1;
2244 return std::min(Tmp, Tmp2)-1;
2247 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2248 if (Tmp2 == 1) return 1;
2251 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2252 if (CLHS->isNullValue()) {
2253 APInt KnownZero, KnownOne;
2254 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2255 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2257 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2260 // If the input is known to be positive (the sign bit is known clear),
2261 // the output of the NEG has the same number of sign bits as the input.
2262 if (KnownZero.isNegative())
2265 // Otherwise, we treat this like a SUB.
2268 // Sub can have at most one carry bit. Thus we know that the output
2269 // is, at worst, one more bit than the inputs.
2270 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2271 if (Tmp == 1) return 1; // Early out.
2272 return std::min(Tmp, Tmp2)-1;
2274 // FIXME: it's tricky to do anything useful for this, but it is an important
2275 // case for targets like X86.
2279 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2280 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2281 unsigned ExtType = LD->getExtensionType();
2284 case ISD::SEXTLOAD: // '17' bits known
2285 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2286 return VTBits-Tmp+1;
2287 case ISD::ZEXTLOAD: // '16' bits known
2288 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2293 // Allow the target to implement this method for its nodes.
2294 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2295 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2296 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2297 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2298 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2299 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2302 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2303 // use this information.
2304 APInt KnownZero, KnownOne;
2305 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2308 if (KnownZero.isNegative()) { // sign bit is 0
2310 } else if (KnownOne.isNegative()) { // sign bit is 1;
2317 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2318 // the number of identical bits in the top of the input value.
2320 Mask <<= Mask.getBitWidth()-VTBits;
2321 // Return # leading zeros. We use 'min' here in case Val was zero before
2322 // shifting. We don't want to return '64' as for an i32 "0".
2323 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2326 /// isBaseWithConstantOffset - Return true if the specified operand is an
2327 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2328 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2329 /// semantics as an ADD. This handles the equivalence:
2330 /// X|Cst == X+Cst iff X&Cst = 0.
2331 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2332 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2333 !isa<ConstantSDNode>(Op.getOperand(1)))
2336 if (Op.getOpcode() == ISD::OR &&
2337 !MaskedValueIsZero(Op.getOperand(0),
2338 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2345 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2346 // If we're told that NaNs won't happen, assume they won't.
2347 if (getTarget().Options.NoNaNsFPMath)
2350 // If the value is a constant, we can obviously see if it is a NaN or not.
2351 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2352 return !C->getValueAPF().isNaN();
2354 // TODO: Recognize more cases here.
2359 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2360 // If the value is a constant, we can obviously see if it is a zero or not.
2361 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2362 return !C->isZero();
2364 // TODO: Recognize more cases here.
2365 switch (Op.getOpcode()) {
2368 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2369 return !C->isNullValue();
2376 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2377 // Check the obvious case.
2378 if (A == B) return true;
2380 // For for negative and positive zero.
2381 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2382 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2383 if (CA->isZero() && CB->isZero()) return true;
2385 // Otherwise they may not be equal.
2389 /// getNode - Gets or creates the specified node.
2391 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2392 FoldingSetNodeID ID;
2393 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2396 return SDValue(E, 0);
2398 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2399 CSEMap.InsertNode(N, IP);
2401 AllNodes.push_back(N);
2405 return SDValue(N, 0);
2408 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2409 EVT VT, SDValue Operand) {
2410 // Constant fold unary operations with an integer constant operand.
2411 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2412 const APInt &Val = C->getAPIntValue();
2415 case ISD::SIGN_EXTEND:
2416 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2417 case ISD::ANY_EXTEND:
2418 case ISD::ZERO_EXTEND:
2420 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2421 case ISD::UINT_TO_FP:
2422 case ISD::SINT_TO_FP: {
2423 // No compile time operations on ppcf128.
2424 if (VT == MVT::ppcf128) break;
2425 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2426 (void)apf.convertFromAPInt(Val,
2427 Opcode==ISD::SINT_TO_FP,
2428 APFloat::rmNearestTiesToEven);
2429 return getConstantFP(apf, VT);
2432 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2433 return getConstantFP(Val.bitsToFloat(), VT);
2434 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2435 return getConstantFP(Val.bitsToDouble(), VT);
2438 return getConstant(Val.byteSwap(), VT);
2440 return getConstant(Val.countPopulation(), VT);
2442 case ISD::CTLZ_ZERO_UNDEF:
2443 return getConstant(Val.countLeadingZeros(), VT);
2445 case ISD::CTTZ_ZERO_UNDEF:
2446 return getConstant(Val.countTrailingZeros(), VT);
2450 // Constant fold unary operations with a floating point constant operand.
2451 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2452 APFloat V = C->getValueAPF(); // make copy
2453 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2457 return getConstantFP(V, VT);
2460 return getConstantFP(V, VT);
2461 case ISD::FP_EXTEND: {
2463 // This can return overflow, underflow, or inexact; we don't care.
2464 // FIXME need to be more flexible about rounding mode.
2465 (void)V.convert(*EVTToAPFloatSemantics(VT),
2466 APFloat::rmNearestTiesToEven, &ignored);
2467 return getConstantFP(V, VT);
2469 case ISD::FP_TO_SINT:
2470 case ISD::FP_TO_UINT: {
2473 assert(integerPartWidth >= 64);
2474 // FIXME need to be more flexible about rounding mode.
2475 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2476 Opcode==ISD::FP_TO_SINT,
2477 APFloat::rmTowardZero, &ignored);
2478 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2480 APInt api(VT.getSizeInBits(), x);
2481 return getConstant(api, VT);
2484 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2485 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2486 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2487 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2493 unsigned OpOpcode = Operand.getNode()->getOpcode();
2495 case ISD::TokenFactor:
2496 case ISD::MERGE_VALUES:
2497 case ISD::CONCAT_VECTORS:
2498 return Operand; // Factor, merge or concat of one node? No need.
2499 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2500 case ISD::FP_EXTEND:
2501 assert(VT.isFloatingPoint() &&
2502 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2503 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2504 assert((!VT.isVector() ||
2505 VT.getVectorNumElements() ==
2506 Operand.getValueType().getVectorNumElements()) &&
2507 "Vector element count mismatch!");
2508 if (Operand.getOpcode() == ISD::UNDEF)
2509 return getUNDEF(VT);
2511 case ISD::SIGN_EXTEND:
2512 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2513 "Invalid SIGN_EXTEND!");
2514 if (Operand.getValueType() == VT) return Operand; // noop extension
2515 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2516 "Invalid sext node, dst < src!");
2517 assert((!VT.isVector() ||
2518 VT.getVectorNumElements() ==
2519 Operand.getValueType().getVectorNumElements()) &&
2520 "Vector element count mismatch!");
2521 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2522 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2523 else if (OpOpcode == ISD::UNDEF)
2524 // sext(undef) = 0, because the top bits will all be the same.
2525 return getConstant(0, VT);
2527 case ISD::ZERO_EXTEND:
2528 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2529 "Invalid ZERO_EXTEND!");
2530 if (Operand.getValueType() == VT) return Operand; // noop extension
2531 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2532 "Invalid zext node, dst < src!");
2533 assert((!VT.isVector() ||
2534 VT.getVectorNumElements() ==
2535 Operand.getValueType().getVectorNumElements()) &&
2536 "Vector element count mismatch!");
2537 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2538 return getNode(ISD::ZERO_EXTEND, DL, VT,
2539 Operand.getNode()->getOperand(0));
2540 else if (OpOpcode == ISD::UNDEF)
2541 // zext(undef) = 0, because the top bits will be zero.
2542 return getConstant(0, VT);
2544 case ISD::ANY_EXTEND:
2545 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2546 "Invalid ANY_EXTEND!");
2547 if (Operand.getValueType() == VT) return Operand; // noop extension
2548 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2549 "Invalid anyext node, dst < src!");
2550 assert((!VT.isVector() ||
2551 VT.getVectorNumElements() ==
2552 Operand.getValueType().getVectorNumElements()) &&
2553 "Vector element count mismatch!");
2555 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2556 OpOpcode == ISD::ANY_EXTEND)
2557 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2558 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2559 else if (OpOpcode == ISD::UNDEF)
2560 return getUNDEF(VT);
2562 // (ext (trunx x)) -> x
2563 if (OpOpcode == ISD::TRUNCATE) {
2564 SDValue OpOp = Operand.getNode()->getOperand(0);
2565 if (OpOp.getValueType() == VT)
2570 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2571 "Invalid TRUNCATE!");
2572 if (Operand.getValueType() == VT) return Operand; // noop truncate
2573 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2574 "Invalid truncate node, src < dst!");
2575 assert((!VT.isVector() ||
2576 VT.getVectorNumElements() ==
2577 Operand.getValueType().getVectorNumElements()) &&
2578 "Vector element count mismatch!");
2579 if (OpOpcode == ISD::TRUNCATE)
2580 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2581 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2582 OpOpcode == ISD::ANY_EXTEND) {
2583 // If the source is smaller than the dest, we still need an extend.
2584 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2585 .bitsLT(VT.getScalarType()))
2586 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2587 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2588 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2589 return Operand.getNode()->getOperand(0);
2591 if (OpOpcode == ISD::UNDEF)
2592 return getUNDEF(VT);
2595 // Basic sanity checking.
2596 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2597 && "Cannot BITCAST between types of different sizes!");
2598 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2599 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2600 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2601 if (OpOpcode == ISD::UNDEF)
2602 return getUNDEF(VT);
2604 case ISD::SCALAR_TO_VECTOR:
2605 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2606 (VT.getVectorElementType() == Operand.getValueType() ||
2607 (VT.getVectorElementType().isInteger() &&
2608 Operand.getValueType().isInteger() &&
2609 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2610 "Illegal SCALAR_TO_VECTOR node!");
2611 if (OpOpcode == ISD::UNDEF)
2612 return getUNDEF(VT);
2613 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2614 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2615 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2616 Operand.getConstantOperandVal(1) == 0 &&
2617 Operand.getOperand(0).getValueType() == VT)
2618 return Operand.getOperand(0);
2621 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2622 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2623 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2624 Operand.getNode()->getOperand(0));
2625 if (OpOpcode == ISD::FNEG) // --X -> X
2626 return Operand.getNode()->getOperand(0);
2629 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2630 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2635 SDVTList VTs = getVTList(VT);
2636 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2637 FoldingSetNodeID ID;
2638 SDValue Ops[1] = { Operand };
2639 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2641 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2642 return SDValue(E, 0);
2644 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2645 CSEMap.InsertNode(N, IP);
2647 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2650 AllNodes.push_back(N);
2654 return SDValue(N, 0);
2657 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2659 ConstantSDNode *Cst1,
2660 ConstantSDNode *Cst2) {
2661 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2664 case ISD::ADD: return getConstant(C1 + C2, VT);
2665 case ISD::SUB: return getConstant(C1 - C2, VT);
2666 case ISD::MUL: return getConstant(C1 * C2, VT);
2668 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2671 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2674 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2677 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2679 case ISD::AND: return getConstant(C1 & C2, VT);
2680 case ISD::OR: return getConstant(C1 | C2, VT);
2681 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2682 case ISD::SHL: return getConstant(C1 << C2, VT);
2683 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2684 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2685 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2686 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2693 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2694 SDValue N1, SDValue N2) {
2695 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2696 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2699 case ISD::TokenFactor:
2700 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2701 N2.getValueType() == MVT::Other && "Invalid token factor!");
2702 // Fold trivial token factors.
2703 if (N1.getOpcode() == ISD::EntryToken) return N2;
2704 if (N2.getOpcode() == ISD::EntryToken) return N1;
2705 if (N1 == N2) return N1;
2707 case ISD::CONCAT_VECTORS:
2708 // Concat of UNDEFs is UNDEF.
2709 if (N1.getOpcode() == ISD::UNDEF &&
2710 N2.getOpcode() == ISD::UNDEF)
2711 return getUNDEF(VT);
2713 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2714 // one big BUILD_VECTOR.
2715 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2716 N2.getOpcode() == ISD::BUILD_VECTOR) {
2717 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2718 N1.getNode()->op_end());
2719 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2720 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2724 assert(VT.isInteger() && "This operator does not apply to FP types!");
2725 assert(N1.getValueType() == N2.getValueType() &&
2726 N1.getValueType() == VT && "Binary operator types must match!");
2727 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2728 // worth handling here.
2729 if (N2C && N2C->isNullValue())
2731 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2738 assert(VT.isInteger() && "This operator does not apply to FP types!");
2739 assert(N1.getValueType() == N2.getValueType() &&
2740 N1.getValueType() == VT && "Binary operator types must match!");
2741 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2742 // it's worth handling here.
2743 if (N2C && N2C->isNullValue())
2753 assert(VT.isInteger() && "This operator does not apply to FP types!");
2754 assert(N1.getValueType() == N2.getValueType() &&
2755 N1.getValueType() == VT && "Binary operator types must match!");
2762 if (getTarget().Options.UnsafeFPMath) {
2763 if (Opcode == ISD::FADD) {
2765 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2766 if (CFP->getValueAPF().isZero())
2769 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2770 if (CFP->getValueAPF().isZero())
2772 } else if (Opcode == ISD::FSUB) {
2774 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2775 if (CFP->getValueAPF().isZero())
2779 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2780 assert(N1.getValueType() == N2.getValueType() &&
2781 N1.getValueType() == VT && "Binary operator types must match!");
2783 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2784 assert(N1.getValueType() == VT &&
2785 N1.getValueType().isFloatingPoint() &&
2786 N2.getValueType().isFloatingPoint() &&
2787 "Invalid FCOPYSIGN!");
2794 assert(VT == N1.getValueType() &&
2795 "Shift operators return type must be the same as their first arg");
2796 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2797 "Shifts only work on integers");
2798 // Verify that the shift amount VT is bit enough to hold valid shift
2799 // amounts. This catches things like trying to shift an i1024 value by an
2800 // i8, which is easy to fall into in generic code that uses
2801 // TLI.getShiftAmount().
2802 assert(N2.getValueType().getSizeInBits() >=
2803 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2804 "Invalid use of small shift amount with oversized value!");
2806 // Always fold shifts of i1 values so the code generator doesn't need to
2807 // handle them. Since we know the size of the shift has to be less than the
2808 // size of the value, the shift/rotate count is guaranteed to be zero.
2811 if (N2C && N2C->isNullValue())
2814 case ISD::FP_ROUND_INREG: {
2815 EVT EVT = cast<VTSDNode>(N2)->getVT();
2816 assert(VT == N1.getValueType() && "Not an inreg round!");
2817 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2818 "Cannot FP_ROUND_INREG integer types");
2819 assert(EVT.isVector() == VT.isVector() &&
2820 "FP_ROUND_INREG type should be vector iff the operand "
2822 assert((!EVT.isVector() ||
2823 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2824 "Vector element counts must match in FP_ROUND_INREG");
2825 assert(EVT.bitsLE(VT) && "Not rounding down!");
2827 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2831 assert(VT.isFloatingPoint() &&
2832 N1.getValueType().isFloatingPoint() &&
2833 VT.bitsLE(N1.getValueType()) &&
2834 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2835 if (N1.getValueType() == VT) return N1; // noop conversion.
2837 case ISD::AssertSext:
2838 case ISD::AssertZext: {
2839 EVT EVT = cast<VTSDNode>(N2)->getVT();
2840 assert(VT == N1.getValueType() && "Not an inreg extend!");
2841 assert(VT.isInteger() && EVT.isInteger() &&
2842 "Cannot *_EXTEND_INREG FP types");
2843 assert(!EVT.isVector() &&
2844 "AssertSExt/AssertZExt type should be the vector element type "
2845 "rather than the vector type!");
2846 assert(EVT.bitsLE(VT) && "Not extending!");
2847 if (VT == EVT) return N1; // noop assertion.
2850 case ISD::SIGN_EXTEND_INREG: {
2851 EVT EVT = cast<VTSDNode>(N2)->getVT();
2852 assert(VT == N1.getValueType() && "Not an inreg extend!");
2853 assert(VT.isInteger() && EVT.isInteger() &&
2854 "Cannot *_EXTEND_INREG FP types");
2855 assert(EVT.isVector() == VT.isVector() &&
2856 "SIGN_EXTEND_INREG type should be vector iff the operand "
2858 assert((!EVT.isVector() ||
2859 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2860 "Vector element counts must match in SIGN_EXTEND_INREG");
2861 assert(EVT.bitsLE(VT) && "Not extending!");
2862 if (EVT == VT) return N1; // Not actually extending
2865 APInt Val = N1C->getAPIntValue();
2866 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2867 Val <<= Val.getBitWidth()-FromBits;
2868 Val = Val.ashr(Val.getBitWidth()-FromBits);
2869 return getConstant(Val, VT);
2873 case ISD::EXTRACT_VECTOR_ELT:
2874 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2875 if (N1.getOpcode() == ISD::UNDEF)
2876 return getUNDEF(VT);
2878 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2879 // expanding copies of large vectors from registers.
2881 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2882 N1.getNumOperands() > 0) {
2884 N1.getOperand(0).getValueType().getVectorNumElements();
2885 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2886 N1.getOperand(N2C->getZExtValue() / Factor),
2887 getConstant(N2C->getZExtValue() % Factor,
2888 N2.getValueType()));
2891 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2892 // expanding large vector constants.
2893 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2894 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2895 EVT VEltTy = N1.getValueType().getVectorElementType();
2896 if (Elt.getValueType() != VEltTy) {
2897 // If the vector element type is not legal, the BUILD_VECTOR operands
2898 // are promoted and implicitly truncated. Make that explicit here.
2899 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt);
2902 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT
2903 // result is implicitly extended.
2904 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt);
2909 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2910 // operations are lowered to scalars.
2911 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2912 // If the indices are the same, return the inserted element else
2913 // if the indices are known different, extract the element from
2914 // the original vector.
2915 SDValue N1Op2 = N1.getOperand(2);
2916 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2918 if (N1Op2C && N2C) {
2919 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2920 if (VT == N1.getOperand(1).getValueType())
2921 return N1.getOperand(1);
2923 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2926 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2930 case ISD::EXTRACT_ELEMENT:
2931 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2932 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2933 (N1.getValueType().isInteger() == VT.isInteger()) &&
2934 N1.getValueType() != VT &&
2935 "Wrong types for EXTRACT_ELEMENT!");
2937 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2938 // 64-bit integers into 32-bit parts. Instead of building the extract of
2939 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2940 if (N1.getOpcode() == ISD::BUILD_PAIR)
2941 return N1.getOperand(N2C->getZExtValue());
2943 // EXTRACT_ELEMENT of a constant int is also very common.
2944 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2945 unsigned ElementSize = VT.getSizeInBits();
2946 unsigned Shift = ElementSize * N2C->getZExtValue();
2947 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2948 return getConstant(ShiftedVal.trunc(ElementSize), VT);
2951 case ISD::EXTRACT_SUBVECTOR: {
2953 if (VT.isSimple() && N1.getValueType().isSimple()) {
2954 assert(VT.isVector() && N1.getValueType().isVector() &&
2955 "Extract subvector VTs must be a vectors!");
2956 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2957 "Extract subvector VTs must have the same element type!");
2958 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2959 "Extract subvector must be from larger vector to smaller vector!");
2961 if (isa<ConstantSDNode>(Index.getNode())) {
2962 assert((VT.getVectorNumElements() +
2963 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
2964 <= N1.getValueType().getVectorNumElements())
2965 && "Extract subvector overflow!");
2968 // Trivial extraction.
2969 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
2978 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
2979 if (SV.getNode()) return SV;
2980 } else { // Cannonicalize constant to RHS if commutative
2981 if (isCommutativeBinOp(Opcode)) {
2982 std::swap(N1C, N2C);
2988 // Constant fold FP operations.
2989 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
2990 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
2992 if (!N2CFP && isCommutativeBinOp(Opcode)) {
2993 // Cannonicalize constant to RHS if commutative
2994 std::swap(N1CFP, N2CFP);
2996 } else if (N2CFP && VT != MVT::ppcf128) {
2997 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2998 APFloat::opStatus s;
3001 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3002 if (s != APFloat::opInvalidOp)
3003 return getConstantFP(V1, VT);
3006 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3007 if (s!=APFloat::opInvalidOp)
3008 return getConstantFP(V1, VT);
3011 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3012 if (s!=APFloat::opInvalidOp)
3013 return getConstantFP(V1, VT);
3016 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3017 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3018 return getConstantFP(V1, VT);
3021 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3022 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3023 return getConstantFP(V1, VT);
3025 case ISD::FCOPYSIGN:
3027 return getConstantFP(V1, VT);
3032 if (Opcode == ISD::FP_ROUND) {
3033 APFloat V = N1CFP->getValueAPF(); // make copy
3035 // This can return overflow, underflow, or inexact; we don't care.
3036 // FIXME need to be more flexible about rounding mode.
3037 (void)V.convert(*EVTToAPFloatSemantics(VT),
3038 APFloat::rmNearestTiesToEven, &ignored);
3039 return getConstantFP(V, VT);
3043 // Canonicalize an UNDEF to the RHS, even over a constant.
3044 if (N1.getOpcode() == ISD::UNDEF) {
3045 if (isCommutativeBinOp(Opcode)) {
3049 case ISD::FP_ROUND_INREG:
3050 case ISD::SIGN_EXTEND_INREG:
3056 return N1; // fold op(undef, arg2) -> undef
3064 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3065 // For vectors, we can't easily build an all zero vector, just return
3072 // Fold a bunch of operators when the RHS is undef.
3073 if (N2.getOpcode() == ISD::UNDEF) {
3076 if (N1.getOpcode() == ISD::UNDEF)
3077 // Handle undef ^ undef -> 0 special case. This is a common
3079 return getConstant(0, VT);
3089 return N2; // fold op(arg1, undef) -> undef
3095 if (getTarget().Options.UnsafeFPMath)
3103 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3104 // For vectors, we can't easily build an all zero vector, just return
3109 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3110 // For vectors, we can't easily build an all one vector, just return
3118 // Memoize this node if possible.
3120 SDVTList VTs = getVTList(VT);
3121 if (VT != MVT::Glue) {
3122 SDValue Ops[] = { N1, N2 };
3123 FoldingSetNodeID ID;
3124 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3126 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3127 return SDValue(E, 0);
3129 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3130 CSEMap.InsertNode(N, IP);
3132 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3135 AllNodes.push_back(N);
3139 return SDValue(N, 0);
3142 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3143 SDValue N1, SDValue N2, SDValue N3) {
3144 // Perform various simplifications.
3145 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3147 case ISD::CONCAT_VECTORS:
3148 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3149 // one big BUILD_VECTOR.
3150 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3151 N2.getOpcode() == ISD::BUILD_VECTOR &&
3152 N3.getOpcode() == ISD::BUILD_VECTOR) {
3153 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3154 N1.getNode()->op_end());
3155 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3156 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3157 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3161 // Use FoldSetCC to simplify SETCC's.
3162 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3163 if (Simp.getNode()) return Simp;
3168 if (N1C->getZExtValue())
3169 return N2; // select true, X, Y -> X
3170 return N3; // select false, X, Y -> Y
3173 if (N2 == N3) return N2; // select C, X, X -> X
3175 case ISD::VECTOR_SHUFFLE:
3176 llvm_unreachable("should use getVectorShuffle constructor!");
3177 case ISD::INSERT_SUBVECTOR: {
3179 if (VT.isSimple() && N1.getValueType().isSimple()
3180 && N2.getValueType().isSimple()) {
3181 assert(VT.isVector() && N1.getValueType().isVector() &&
3182 N2.getValueType().isVector() &&
3183 "Insert subvector VTs must be a vectors");
3184 assert(VT == N1.getValueType() &&
3185 "Dest and insert subvector source types must match!");
3186 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3187 "Insert subvector must be from smaller vector to larger vector!");
3188 if (isa<ConstantSDNode>(Index.getNode())) {
3189 assert((N2.getValueType().getVectorNumElements() +
3190 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3191 <= VT.getVectorNumElements())
3192 && "Insert subvector overflow!");
3195 // Trivial insertion.
3196 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3202 // Fold bit_convert nodes from a type to themselves.
3203 if (N1.getValueType() == VT)
3208 // Memoize node if it doesn't produce a flag.
3210 SDVTList VTs = getVTList(VT);
3211 if (VT != MVT::Glue) {
3212 SDValue Ops[] = { N1, N2, N3 };
3213 FoldingSetNodeID ID;
3214 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3216 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3217 return SDValue(E, 0);
3219 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3220 CSEMap.InsertNode(N, IP);
3222 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3225 AllNodes.push_back(N);
3229 return SDValue(N, 0);
3232 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3233 SDValue N1, SDValue N2, SDValue N3,
3235 SDValue Ops[] = { N1, N2, N3, N4 };
3236 return getNode(Opcode, DL, VT, Ops, 4);
3239 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3240 SDValue N1, SDValue N2, SDValue N3,
3241 SDValue N4, SDValue N5) {
3242 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3243 return getNode(Opcode, DL, VT, Ops, 5);
3246 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3247 /// the incoming stack arguments to be loaded from the stack.
3248 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3249 SmallVector<SDValue, 8> ArgChains;
3251 // Include the original chain at the beginning of the list. When this is
3252 // used by target LowerCall hooks, this helps legalize find the
3253 // CALLSEQ_BEGIN node.
3254 ArgChains.push_back(Chain);
3256 // Add a chain value for each stack argument.
3257 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3258 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3259 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3260 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3261 if (FI->getIndex() < 0)
3262 ArgChains.push_back(SDValue(L, 1));
3264 // Build a tokenfactor for all the chains.
3265 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3266 &ArgChains[0], ArgChains.size());
3269 /// SplatByte - Distribute ByteVal over NumBits bits.
3270 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3271 APInt Val = APInt(NumBits, ByteVal);
3273 for (unsigned i = NumBits; i > 8; i >>= 1) {
3274 Val = (Val << Shift) | Val;
3280 /// getMemsetValue - Vectorized representation of the memset value
3282 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3284 assert(Value.getOpcode() != ISD::UNDEF);
3286 unsigned NumBits = VT.getScalarType().getSizeInBits();
3287 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3288 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3290 return DAG.getConstant(Val, VT);
3291 return DAG.getConstantFP(APFloat(Val), VT);
3294 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3296 // Use a multiplication with 0x010101... to extend the input to the
3298 APInt Magic = SplatByte(NumBits, 0x01);
3299 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3305 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3306 /// used when a memcpy is turned into a memset when the source is a constant
3308 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3309 const TargetLowering &TLI, StringRef Str) {
3310 // Handle vector with all elements zero.
3313 return DAG.getConstant(0, VT);
3314 else if (VT == MVT::f32 || VT == MVT::f64)
3315 return DAG.getConstantFP(0.0, VT);
3316 else if (VT.isVector()) {
3317 unsigned NumElts = VT.getVectorNumElements();
3318 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3319 return DAG.getNode(ISD::BITCAST, dl, VT,
3320 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3323 llvm_unreachable("Expected type!");
3326 assert(!VT.isVector() && "Can't handle vector type here!");
3327 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3328 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3331 if (TLI.isLittleEndian()) {
3332 for (unsigned i = 0; i != NumBytes; ++i)
3333 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3335 for (unsigned i = 0; i != NumBytes; ++i)
3336 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3339 return DAG.getConstant(Val, VT);
3342 /// getMemBasePlusOffset - Returns base and offset node for the
3344 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3345 SelectionDAG &DAG) {
3346 EVT VT = Base.getValueType();
3347 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3348 VT, Base, DAG.getConstant(Offset, VT));
3351 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3353 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3354 unsigned SrcDelta = 0;
3355 GlobalAddressSDNode *G = NULL;
3356 if (Src.getOpcode() == ISD::GlobalAddress)
3357 G = cast<GlobalAddressSDNode>(Src);
3358 else if (Src.getOpcode() == ISD::ADD &&
3359 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3360 Src.getOperand(1).getOpcode() == ISD::Constant) {
3361 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3362 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3367 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3370 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3371 /// to replace the memset / memcpy. Return true if the number of memory ops
3372 /// is below the threshold. It returns the types of the sequence of
3373 /// memory ops to perform memset / memcpy by reference.
3374 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3375 unsigned Limit, uint64_t Size,
3376 unsigned DstAlign, unsigned SrcAlign,
3380 const TargetLowering &TLI) {
3381 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3382 "Expecting memcpy / memset source to meet alignment requirement!");
3383 // If 'SrcAlign' is zero, that means the memory operation does not need to
3384 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3385 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3386 // is the specified alignment of the memory operation. If it is zero, that
3387 // means it's possible to change the alignment of the destination.
3388 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3389 // not need to be loaded.
3390 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3391 IsZeroVal, MemcpyStrSrc,
3392 DAG.getMachineFunction());
3394 if (VT == MVT::Other) {
3395 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3396 TLI.allowsUnalignedMemoryAccesses(VT)) {
3397 VT = TLI.getPointerTy();
3399 switch (DstAlign & 7) {
3400 case 0: VT = MVT::i64; break;
3401 case 4: VT = MVT::i32; break;
3402 case 2: VT = MVT::i16; break;
3403 default: VT = MVT::i8; break;
3408 while (!TLI.isTypeLegal(LVT))
3409 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3410 assert(LVT.isInteger());
3416 unsigned NumMemOps = 0;
3418 unsigned VTSize = VT.getSizeInBits() / 8;
3419 while (VTSize > Size) {
3420 // For now, only use non-vector load / store's for the left-over pieces.
3421 if (VT.isVector() || VT.isFloatingPoint()) {
3423 while (!TLI.isTypeLegal(VT))
3424 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3425 VTSize = VT.getSizeInBits() / 8;
3427 // This can result in a type that is not legal on the target, e.g.
3428 // 1 or 2 bytes on PPC.
3429 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3434 if (++NumMemOps > Limit)
3436 MemOps.push_back(VT);
3443 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3444 SDValue Chain, SDValue Dst,
3445 SDValue Src, uint64_t Size,
3446 unsigned Align, bool isVol,
3448 MachinePointerInfo DstPtrInfo,
3449 MachinePointerInfo SrcPtrInfo) {
3450 // Turn a memcpy of undef to nop.
3451 if (Src.getOpcode() == ISD::UNDEF)
3454 // Expand memcpy to a series of load and store ops if the size operand falls
3455 // below a certain threshold.
3456 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3457 // rather than maybe a humongous number of loads and stores.
3458 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3459 std::vector<EVT> MemOps;
3460 bool DstAlignCanChange = false;
3461 MachineFunction &MF = DAG.getMachineFunction();
3462 MachineFrameInfo *MFI = MF.getFrameInfo();
3463 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3464 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3465 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3466 DstAlignCanChange = true;
3467 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3468 if (Align > SrcAlign)
3471 bool CopyFromStr = isMemSrcFromString(Src, Str);
3472 bool isZeroStr = CopyFromStr && Str.empty();
3473 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3475 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3476 (DstAlignCanChange ? 0 : Align),
3477 (isZeroStr ? 0 : SrcAlign),
3478 true, CopyFromStr, DAG, TLI))
3481 if (DstAlignCanChange) {
3482 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3483 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3484 if (NewAlign > Align) {
3485 // Give the stack frame object a larger alignment if needed.
3486 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3487 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3492 SmallVector<SDValue, 8> OutChains;
3493 unsigned NumMemOps = MemOps.size();
3494 uint64_t SrcOff = 0, DstOff = 0;
3495 for (unsigned i = 0; i != NumMemOps; ++i) {
3497 unsigned VTSize = VT.getSizeInBits() / 8;
3498 SDValue Value, Store;
3501 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3502 // It's unlikely a store of a vector immediate can be done in a single
3503 // instruction. It would require a load from a constantpool first.
3504 // We only handle zero vectors here.
3505 // FIXME: Handle other cases where store of vector immediate is done in
3506 // a single instruction.
3507 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3508 Store = DAG.getStore(Chain, dl, Value,
3509 getMemBasePlusOffset(Dst, DstOff, DAG),
3510 DstPtrInfo.getWithOffset(DstOff), isVol,
3513 // The type might not be legal for the target. This should only happen
3514 // if the type is smaller than a legal type, as on PPC, so the right
3515 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3516 // to Load/Store if NVT==VT.
3517 // FIXME does the case above also need this?
3518 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3519 assert(NVT.bitsGE(VT));
3520 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3521 getMemBasePlusOffset(Src, SrcOff, DAG),
3522 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3523 MinAlign(SrcAlign, SrcOff));
3524 Store = DAG.getTruncStore(Chain, dl, Value,
3525 getMemBasePlusOffset(Dst, DstOff, DAG),
3526 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3529 OutChains.push_back(Store);
3534 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3535 &OutChains[0], OutChains.size());
3538 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3539 SDValue Chain, SDValue Dst,
3540 SDValue Src, uint64_t Size,
3541 unsigned Align, bool isVol,
3543 MachinePointerInfo DstPtrInfo,
3544 MachinePointerInfo SrcPtrInfo) {
3545 // Turn a memmove of undef to nop.
3546 if (Src.getOpcode() == ISD::UNDEF)
3549 // Expand memmove to a series of load and store ops if the size operand falls
3550 // below a certain threshold.
3551 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3552 std::vector<EVT> MemOps;
3553 bool DstAlignCanChange = false;
3554 MachineFunction &MF = DAG.getMachineFunction();
3555 MachineFrameInfo *MFI = MF.getFrameInfo();
3556 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3557 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3558 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3559 DstAlignCanChange = true;
3560 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3561 if (Align > SrcAlign)
3563 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3565 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3566 (DstAlignCanChange ? 0 : Align),
3567 SrcAlign, true, false, DAG, TLI))
3570 if (DstAlignCanChange) {
3571 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3572 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3573 if (NewAlign > Align) {
3574 // Give the stack frame object a larger alignment if needed.
3575 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3576 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3581 uint64_t SrcOff = 0, DstOff = 0;
3582 SmallVector<SDValue, 8> LoadValues;
3583 SmallVector<SDValue, 8> LoadChains;
3584 SmallVector<SDValue, 8> OutChains;
3585 unsigned NumMemOps = MemOps.size();
3586 for (unsigned i = 0; i < NumMemOps; i++) {
3588 unsigned VTSize = VT.getSizeInBits() / 8;
3589 SDValue Value, Store;
3591 Value = DAG.getLoad(VT, dl, Chain,
3592 getMemBasePlusOffset(Src, SrcOff, DAG),
3593 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3594 false, false, SrcAlign);
3595 LoadValues.push_back(Value);
3596 LoadChains.push_back(Value.getValue(1));
3599 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3600 &LoadChains[0], LoadChains.size());
3602 for (unsigned i = 0; i < NumMemOps; i++) {
3604 unsigned VTSize = VT.getSizeInBits() / 8;
3605 SDValue Value, Store;
3607 Store = DAG.getStore(Chain, dl, LoadValues[i],
3608 getMemBasePlusOffset(Dst, DstOff, DAG),
3609 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3610 OutChains.push_back(Store);
3614 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3615 &OutChains[0], OutChains.size());
3618 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3619 SDValue Chain, SDValue Dst,
3620 SDValue Src, uint64_t Size,
3621 unsigned Align, bool isVol,
3622 MachinePointerInfo DstPtrInfo) {
3623 // Turn a memset of undef to nop.
3624 if (Src.getOpcode() == ISD::UNDEF)
3627 // Expand memset to a series of load/store ops if the size operand
3628 // falls below a certain threshold.
3629 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3630 std::vector<EVT> MemOps;
3631 bool DstAlignCanChange = false;
3632 MachineFunction &MF = DAG.getMachineFunction();
3633 MachineFrameInfo *MFI = MF.getFrameInfo();
3634 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3635 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3636 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3637 DstAlignCanChange = true;
3639 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3640 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3641 Size, (DstAlignCanChange ? 0 : Align), 0,
3642 IsZeroVal, false, DAG, TLI))
3645 if (DstAlignCanChange) {
3646 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3647 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3648 if (NewAlign > Align) {
3649 // Give the stack frame object a larger alignment if needed.
3650 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3651 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3656 SmallVector<SDValue, 8> OutChains;
3657 uint64_t DstOff = 0;
3658 unsigned NumMemOps = MemOps.size();
3660 // Find the largest store and generate the bit pattern for it.
3661 EVT LargestVT = MemOps[0];
3662 for (unsigned i = 1; i < NumMemOps; i++)
3663 if (MemOps[i].bitsGT(LargestVT))
3664 LargestVT = MemOps[i];
3665 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3667 for (unsigned i = 0; i < NumMemOps; i++) {
3670 // If this store is smaller than the largest store see whether we can get
3671 // the smaller value for free with a truncate.
3672 SDValue Value = MemSetValue;
3673 if (VT.bitsLT(LargestVT)) {
3674 if (!LargestVT.isVector() && !VT.isVector() &&
3675 TLI.isTruncateFree(LargestVT, VT))
3676 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3678 Value = getMemsetValue(Src, VT, DAG, dl);
3680 assert(Value.getValueType() == VT && "Value with wrong type.");
3681 SDValue Store = DAG.getStore(Chain, dl, Value,
3682 getMemBasePlusOffset(Dst, DstOff, DAG),
3683 DstPtrInfo.getWithOffset(DstOff),
3684 isVol, false, Align);
3685 OutChains.push_back(Store);
3686 DstOff += VT.getSizeInBits() / 8;
3689 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3690 &OutChains[0], OutChains.size());
3693 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3694 SDValue Src, SDValue Size,
3695 unsigned Align, bool isVol, bool AlwaysInline,
3696 MachinePointerInfo DstPtrInfo,
3697 MachinePointerInfo SrcPtrInfo) {
3699 // Check to see if we should lower the memcpy to loads and stores first.
3700 // For cases within the target-specified limits, this is the best choice.
3701 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3703 // Memcpy with size zero? Just return the original chain.
3704 if (ConstantSize->isNullValue())
3707 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3708 ConstantSize->getZExtValue(),Align,
3709 isVol, false, DstPtrInfo, SrcPtrInfo);
3710 if (Result.getNode())
3714 // Then check to see if we should lower the memcpy with target-specific
3715 // code. If the target chooses to do this, this is the next best.
3717 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3718 isVol, AlwaysInline,
3719 DstPtrInfo, SrcPtrInfo);
3720 if (Result.getNode())
3723 // If we really need inline code and the target declined to provide it,
3724 // use a (potentially long) sequence of loads and stores.
3726 assert(ConstantSize && "AlwaysInline requires a constant size!");
3727 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3728 ConstantSize->getZExtValue(), Align, isVol,
3729 true, DstPtrInfo, SrcPtrInfo);
3732 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3733 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3734 // respect volatile, so they may do things like read or write memory
3735 // beyond the given memory regions. But fixing this isn't easy, and most
3736 // people don't care.
3738 // Emit a library call.
3739 TargetLowering::ArgListTy Args;
3740 TargetLowering::ArgListEntry Entry;
3741 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3742 Entry.Node = Dst; Args.push_back(Entry);
3743 Entry.Node = Src; Args.push_back(Entry);
3744 Entry.Node = Size; Args.push_back(Entry);
3745 // FIXME: pass in DebugLoc
3747 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3748 false, false, false, false, 0,
3749 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3750 /*isTailCall=*/false,
3751 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3752 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3753 TLI.getPointerTy()),
3755 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3757 return CallResult.second;
3760 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3761 SDValue Src, SDValue Size,
3762 unsigned Align, bool isVol,
3763 MachinePointerInfo DstPtrInfo,
3764 MachinePointerInfo SrcPtrInfo) {
3766 // Check to see if we should lower the memmove to loads and stores first.
3767 // For cases within the target-specified limits, this is the best choice.
3768 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3770 // Memmove with size zero? Just return the original chain.
3771 if (ConstantSize->isNullValue())
3775 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3776 ConstantSize->getZExtValue(), Align, isVol,
3777 false, DstPtrInfo, SrcPtrInfo);
3778 if (Result.getNode())
3782 // Then check to see if we should lower the memmove with target-specific
3783 // code. If the target chooses to do this, this is the next best.
3785 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3786 DstPtrInfo, SrcPtrInfo);
3787 if (Result.getNode())
3790 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3791 // not be safe. See memcpy above for more details.
3793 // Emit a library call.
3794 TargetLowering::ArgListTy Args;
3795 TargetLowering::ArgListEntry Entry;
3796 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3797 Entry.Node = Dst; Args.push_back(Entry);
3798 Entry.Node = Src; Args.push_back(Entry);
3799 Entry.Node = Size; Args.push_back(Entry);
3800 // FIXME: pass in DebugLoc
3802 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3803 false, false, false, false, 0,
3804 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3805 /*isTailCall=*/false,
3806 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3807 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3808 TLI.getPointerTy()),
3810 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3812 return CallResult.second;
3815 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3816 SDValue Src, SDValue Size,
3817 unsigned Align, bool isVol,
3818 MachinePointerInfo DstPtrInfo) {
3820 // Check to see if we should lower the memset to stores first.
3821 // For cases within the target-specified limits, this is the best choice.
3822 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3824 // Memset with size zero? Just return the original chain.
3825 if (ConstantSize->isNullValue())
3829 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3830 Align, isVol, DstPtrInfo);
3832 if (Result.getNode())
3836 // Then check to see if we should lower the memset with target-specific
3837 // code. If the target chooses to do this, this is the next best.
3839 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3841 if (Result.getNode())
3844 // Emit a library call.
3845 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3846 TargetLowering::ArgListTy Args;
3847 TargetLowering::ArgListEntry Entry;
3848 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3849 Args.push_back(Entry);
3850 // Extend or truncate the argument to be an i32 value for the call.
3851 if (Src.getValueType().bitsGT(MVT::i32))
3852 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3854 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3856 Entry.Ty = Type::getInt32Ty(*getContext());
3857 Entry.isSExt = true;
3858 Args.push_back(Entry);
3860 Entry.Ty = IntPtrTy;
3861 Entry.isSExt = false;
3862 Args.push_back(Entry);
3863 // FIXME: pass in DebugLoc
3865 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3866 false, false, false, false, 0,
3867 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3868 /*isTailCall=*/false,
3869 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3870 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3871 TLI.getPointerTy()),
3873 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3875 return CallResult.second;
3878 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3879 SDValue Chain, SDValue Ptr, SDValue Cmp,
3880 SDValue Swp, MachinePointerInfo PtrInfo,
3882 AtomicOrdering Ordering,
3883 SynchronizationScope SynchScope) {
3884 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3885 Alignment = getEVTAlignment(MemVT);
3887 MachineFunction &MF = getMachineFunction();
3888 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
3890 // For now, atomics are considered to be volatile always.
3891 // FIXME: Volatile isn't really correct; we should keep track of atomic
3892 // orderings in the memoperand.
3893 Flags |= MachineMemOperand::MOVolatile;
3895 MachineMemOperand *MMO =
3896 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3898 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3899 Ordering, SynchScope);
3902 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3904 SDValue Ptr, SDValue Cmp,
3905 SDValue Swp, MachineMemOperand *MMO,
3906 AtomicOrdering Ordering,
3907 SynchronizationScope SynchScope) {
3908 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3909 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3911 EVT VT = Cmp.getValueType();
3913 SDVTList VTs = getVTList(VT, MVT::Other);
3914 FoldingSetNodeID ID;
3915 ID.AddInteger(MemVT.getRawBits());
3916 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3917 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3918 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
3920 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3921 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3922 return SDValue(E, 0);
3924 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3925 Ptr, Cmp, Swp, MMO, Ordering,
3927 CSEMap.InsertNode(N, IP);
3928 AllNodes.push_back(N);
3929 return SDValue(N, 0);
3932 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3934 SDValue Ptr, SDValue Val,
3935 const Value* PtrVal,
3937 AtomicOrdering Ordering,
3938 SynchronizationScope SynchScope) {
3939 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3940 Alignment = getEVTAlignment(MemVT);
3942 MachineFunction &MF = getMachineFunction();
3943 // A monotonic store does not load; a release store "loads" in the sense
3944 // that other stores cannot be sunk past it.
3945 // (An atomicrmw obviously both loads and stores.)
3946 unsigned Flags = MachineMemOperand::MOStore;
3947 if (Opcode != ISD::ATOMIC_STORE || Ordering > Monotonic)
3948 Flags |= MachineMemOperand::MOLoad;
3950 // For now, atomics are considered to be volatile always.
3951 // FIXME: Volatile isn't really correct; we should keep track of atomic
3952 // orderings in the memoperand.
3953 Flags |= MachineMemOperand::MOVolatile;
3955 MachineMemOperand *MMO =
3956 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3957 MemVT.getStoreSize(), Alignment);
3959 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
3960 Ordering, SynchScope);
3963 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3965 SDValue Ptr, SDValue Val,
3966 MachineMemOperand *MMO,
3967 AtomicOrdering Ordering,
3968 SynchronizationScope SynchScope) {
3969 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
3970 Opcode == ISD::ATOMIC_LOAD_SUB ||
3971 Opcode == ISD::ATOMIC_LOAD_AND ||
3972 Opcode == ISD::ATOMIC_LOAD_OR ||
3973 Opcode == ISD::ATOMIC_LOAD_XOR ||
3974 Opcode == ISD::ATOMIC_LOAD_NAND ||
3975 Opcode == ISD::ATOMIC_LOAD_MIN ||
3976 Opcode == ISD::ATOMIC_LOAD_MAX ||
3977 Opcode == ISD::ATOMIC_LOAD_UMIN ||
3978 Opcode == ISD::ATOMIC_LOAD_UMAX ||
3979 Opcode == ISD::ATOMIC_SWAP ||
3980 Opcode == ISD::ATOMIC_STORE) &&
3981 "Invalid Atomic Op");
3983 EVT VT = Val.getValueType();
3985 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
3986 getVTList(VT, MVT::Other);
3987 FoldingSetNodeID ID;
3988 ID.AddInteger(MemVT.getRawBits());
3989 SDValue Ops[] = {Chain, Ptr, Val};
3990 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3991 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
3993 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3994 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3995 return SDValue(E, 0);
3997 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3999 Ordering, SynchScope);
4000 CSEMap.InsertNode(N, IP);
4001 AllNodes.push_back(N);
4002 return SDValue(N, 0);
4005 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4006 EVT VT, SDValue Chain,
4008 const Value* PtrVal,
4010 AtomicOrdering Ordering,
4011 SynchronizationScope SynchScope) {
4012 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4013 Alignment = getEVTAlignment(MemVT);
4015 MachineFunction &MF = getMachineFunction();
4016 // A monotonic load does not store; an acquire load "stores" in the sense
4017 // that other loads cannot be hoisted past it.
4018 unsigned Flags = MachineMemOperand::MOLoad;
4019 if (Ordering > Monotonic)
4020 Flags |= MachineMemOperand::MOStore;
4022 // For now, atomics are considered to be volatile always.
4023 // FIXME: Volatile isn't really correct; we should keep track of atomic
4024 // orderings in the memoperand.
4025 Flags |= MachineMemOperand::MOVolatile;
4027 MachineMemOperand *MMO =
4028 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4029 MemVT.getStoreSize(), Alignment);
4031 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4032 Ordering, SynchScope);
4035 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4036 EVT VT, SDValue Chain,
4038 MachineMemOperand *MMO,
4039 AtomicOrdering Ordering,
4040 SynchronizationScope SynchScope) {
4041 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4043 SDVTList VTs = getVTList(VT, MVT::Other);
4044 FoldingSetNodeID ID;
4045 ID.AddInteger(MemVT.getRawBits());
4046 SDValue Ops[] = {Chain, Ptr};
4047 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4048 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4050 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4051 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4052 return SDValue(E, 0);
4054 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4055 Ptr, MMO, Ordering, SynchScope);
4056 CSEMap.InsertNode(N, IP);
4057 AllNodes.push_back(N);
4058 return SDValue(N, 0);
4061 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4062 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4067 SmallVector<EVT, 4> VTs;
4068 VTs.reserve(NumOps);
4069 for (unsigned i = 0; i < NumOps; ++i)
4070 VTs.push_back(Ops[i].getValueType());
4071 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4076 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4077 const EVT *VTs, unsigned NumVTs,
4078 const SDValue *Ops, unsigned NumOps,
4079 EVT MemVT, MachinePointerInfo PtrInfo,
4080 unsigned Align, bool Vol,
4081 bool ReadMem, bool WriteMem) {
4082 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4083 MemVT, PtrInfo, Align, Vol,
4088 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4089 const SDValue *Ops, unsigned NumOps,
4090 EVT MemVT, MachinePointerInfo PtrInfo,
4091 unsigned Align, bool Vol,
4092 bool ReadMem, bool WriteMem) {
4093 if (Align == 0) // Ensure that codegen never sees alignment 0
4094 Align = getEVTAlignment(MemVT);
4096 MachineFunction &MF = getMachineFunction();
4099 Flags |= MachineMemOperand::MOStore;
4101 Flags |= MachineMemOperand::MOLoad;
4103 Flags |= MachineMemOperand::MOVolatile;
4104 MachineMemOperand *MMO =
4105 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4107 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4111 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4112 const SDValue *Ops, unsigned NumOps,
4113 EVT MemVT, MachineMemOperand *MMO) {
4114 assert((Opcode == ISD::INTRINSIC_VOID ||
4115 Opcode == ISD::INTRINSIC_W_CHAIN ||
4116 Opcode == ISD::PREFETCH ||
4117 (Opcode <= INT_MAX &&
4118 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4119 "Opcode is not a memory-accessing opcode!");
4121 // Memoize the node unless it returns a flag.
4122 MemIntrinsicSDNode *N;
4123 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4124 FoldingSetNodeID ID;
4125 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4126 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4128 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4129 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4130 return SDValue(E, 0);
4133 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4135 CSEMap.InsertNode(N, IP);
4137 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4140 AllNodes.push_back(N);
4141 return SDValue(N, 0);
4144 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4145 /// MachinePointerInfo record from it. This is particularly useful because the
4146 /// code generator has many cases where it doesn't bother passing in a
4147 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4148 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4149 // If this is FI+Offset, we can model it.
4150 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4151 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4153 // If this is (FI+Offset1)+Offset2, we can model it.
4154 if (Ptr.getOpcode() != ISD::ADD ||
4155 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4156 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4157 return MachinePointerInfo();
4159 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4160 return MachinePointerInfo::getFixedStack(FI, Offset+
4161 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4164 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4165 /// MachinePointerInfo record from it. This is particularly useful because the
4166 /// code generator has many cases where it doesn't bother passing in a
4167 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4168 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4169 // If the 'Offset' value isn't a constant, we can't handle this.
4170 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4171 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4172 if (OffsetOp.getOpcode() == ISD::UNDEF)
4173 return InferPointerInfo(Ptr);
4174 return MachinePointerInfo();
4179 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4180 EVT VT, DebugLoc dl, SDValue Chain,
4181 SDValue Ptr, SDValue Offset,
4182 MachinePointerInfo PtrInfo, EVT MemVT,
4183 bool isVolatile, bool isNonTemporal, bool isInvariant,
4184 unsigned Alignment, const MDNode *TBAAInfo,
4185 const MDNode *Ranges) {
4186 assert(Chain.getValueType() == MVT::Other &&
4187 "Invalid chain type");
4188 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4189 Alignment = getEVTAlignment(VT);
4191 unsigned Flags = MachineMemOperand::MOLoad;
4193 Flags |= MachineMemOperand::MOVolatile;
4195 Flags |= MachineMemOperand::MONonTemporal;
4197 Flags |= MachineMemOperand::MOInvariant;
4199 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4202 PtrInfo = InferPointerInfo(Ptr, Offset);
4204 MachineFunction &MF = getMachineFunction();
4205 MachineMemOperand *MMO =
4206 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4208 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4212 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4213 EVT VT, DebugLoc dl, SDValue Chain,
4214 SDValue Ptr, SDValue Offset, EVT MemVT,
4215 MachineMemOperand *MMO) {
4217 ExtType = ISD::NON_EXTLOAD;
4218 } else if (ExtType == ISD::NON_EXTLOAD) {
4219 assert(VT == MemVT && "Non-extending load from different memory type!");
4222 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4223 "Should only be an extending load, not truncating!");
4224 assert(VT.isInteger() == MemVT.isInteger() &&
4225 "Cannot convert from FP to Int or Int -> FP!");
4226 assert(VT.isVector() == MemVT.isVector() &&
4227 "Cannot use trunc store to convert to or from a vector!");
4228 assert((!VT.isVector() ||
4229 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4230 "Cannot use trunc store to change the number of vector elements!");
4233 bool Indexed = AM != ISD::UNINDEXED;
4234 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4235 "Unindexed load with an offset!");
4237 SDVTList VTs = Indexed ?
4238 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4239 SDValue Ops[] = { Chain, Ptr, Offset };
4240 FoldingSetNodeID ID;
4241 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4242 ID.AddInteger(MemVT.getRawBits());
4243 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4244 MMO->isNonTemporal(),
4245 MMO->isInvariant()));
4246 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4248 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4249 cast<LoadSDNode>(E)->refineAlignment(MMO);
4250 return SDValue(E, 0);
4252 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4254 CSEMap.InsertNode(N, IP);
4255 AllNodes.push_back(N);
4256 return SDValue(N, 0);
4259 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4260 SDValue Chain, SDValue Ptr,
4261 MachinePointerInfo PtrInfo,
4262 bool isVolatile, bool isNonTemporal,
4263 bool isInvariant, unsigned Alignment,
4264 const MDNode *TBAAInfo,
4265 const MDNode *Ranges) {
4266 SDValue Undef = getUNDEF(Ptr.getValueType());
4267 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4268 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4272 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4273 SDValue Chain, SDValue Ptr,
4274 MachinePointerInfo PtrInfo, EVT MemVT,
4275 bool isVolatile, bool isNonTemporal,
4276 unsigned Alignment, const MDNode *TBAAInfo) {
4277 SDValue Undef = getUNDEF(Ptr.getValueType());
4278 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4279 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4285 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4286 SDValue Offset, ISD::MemIndexedMode AM) {
4287 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4288 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4289 "Load is already a indexed load!");
4290 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4291 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4292 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4293 false, LD->getAlignment());
4296 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4297 SDValue Ptr, MachinePointerInfo PtrInfo,
4298 bool isVolatile, bool isNonTemporal,
4299 unsigned Alignment, const MDNode *TBAAInfo) {
4300 assert(Chain.getValueType() == MVT::Other &&
4301 "Invalid chain type");
4302 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4303 Alignment = getEVTAlignment(Val.getValueType());
4305 unsigned Flags = MachineMemOperand::MOStore;
4307 Flags |= MachineMemOperand::MOVolatile;
4309 Flags |= MachineMemOperand::MONonTemporal;
4312 PtrInfo = InferPointerInfo(Ptr);
4314 MachineFunction &MF = getMachineFunction();
4315 MachineMemOperand *MMO =
4316 MF.getMachineMemOperand(PtrInfo, Flags,
4317 Val.getValueType().getStoreSize(), Alignment,
4320 return getStore(Chain, dl, Val, Ptr, MMO);
4323 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4324 SDValue Ptr, MachineMemOperand *MMO) {
4325 assert(Chain.getValueType() == MVT::Other &&
4326 "Invalid chain type");
4327 EVT VT = Val.getValueType();
4328 SDVTList VTs = getVTList(MVT::Other);
4329 SDValue Undef = getUNDEF(Ptr.getValueType());
4330 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4331 FoldingSetNodeID ID;
4332 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4333 ID.AddInteger(VT.getRawBits());
4334 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4335 MMO->isNonTemporal(), MMO->isInvariant()));
4336 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4338 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4339 cast<StoreSDNode>(E)->refineAlignment(MMO);
4340 return SDValue(E, 0);
4342 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4344 CSEMap.InsertNode(N, IP);
4345 AllNodes.push_back(N);
4346 return SDValue(N, 0);
4349 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4350 SDValue Ptr, MachinePointerInfo PtrInfo,
4351 EVT SVT,bool isVolatile, bool isNonTemporal,
4353 const MDNode *TBAAInfo) {
4354 assert(Chain.getValueType() == MVT::Other &&
4355 "Invalid chain type");
4356 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4357 Alignment = getEVTAlignment(SVT);
4359 unsigned Flags = MachineMemOperand::MOStore;
4361 Flags |= MachineMemOperand::MOVolatile;
4363 Flags |= MachineMemOperand::MONonTemporal;
4366 PtrInfo = InferPointerInfo(Ptr);
4368 MachineFunction &MF = getMachineFunction();
4369 MachineMemOperand *MMO =
4370 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4373 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4376 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4377 SDValue Ptr, EVT SVT,
4378 MachineMemOperand *MMO) {
4379 EVT VT = Val.getValueType();
4381 assert(Chain.getValueType() == MVT::Other &&
4382 "Invalid chain type");
4384 return getStore(Chain, dl, Val, Ptr, MMO);
4386 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4387 "Should only be a truncating store, not extending!");
4388 assert(VT.isInteger() == SVT.isInteger() &&
4389 "Can't do FP-INT conversion!");
4390 assert(VT.isVector() == SVT.isVector() &&
4391 "Cannot use trunc store to convert to or from a vector!");
4392 assert((!VT.isVector() ||
4393 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4394 "Cannot use trunc store to change the number of vector elements!");
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(SVT.getRawBits());
4402 ID.AddInteger(encodeMemSDNodeFlags(true, 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);
4418 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4419 SDValue Offset, ISD::MemIndexedMode AM) {
4420 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4421 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4422 "Store is already a indexed store!");
4423 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4424 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4425 FoldingSetNodeID ID;
4426 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4427 ID.AddInteger(ST->getMemoryVT().getRawBits());
4428 ID.AddInteger(ST->getRawSubclassData());
4429 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4431 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4432 return SDValue(E, 0);
4434 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4435 ST->isTruncatingStore(),
4437 ST->getMemOperand());
4438 CSEMap.InsertNode(N, IP);
4439 AllNodes.push_back(N);
4440 return SDValue(N, 0);
4443 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4444 SDValue Chain, SDValue Ptr,
4447 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4448 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4451 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4452 const SDUse *Ops, unsigned NumOps) {
4454 case 0: return getNode(Opcode, DL, VT);
4455 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4456 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4457 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4461 // Copy from an SDUse array into an SDValue array for use with
4462 // the regular getNode logic.
4463 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4464 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4467 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4468 const SDValue *Ops, unsigned NumOps) {
4470 case 0: return getNode(Opcode, DL, VT);
4471 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4472 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4473 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4479 case ISD::SELECT_CC: {
4480 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4481 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4482 "LHS and RHS of condition must have same type!");
4483 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4484 "True and False arms of SelectCC must have same type!");
4485 assert(Ops[2].getValueType() == VT &&
4486 "select_cc node must be of same type as true and false value!");
4490 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4491 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4492 "LHS/RHS of comparison should match types!");
4499 SDVTList VTs = getVTList(VT);
4501 if (VT != MVT::Glue) {
4502 FoldingSetNodeID ID;
4503 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4506 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4507 return SDValue(E, 0);
4509 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4510 CSEMap.InsertNode(N, IP);
4512 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4515 AllNodes.push_back(N);
4519 return SDValue(N, 0);
4522 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4523 const std::vector<EVT> &ResultTys,
4524 const SDValue *Ops, unsigned NumOps) {
4525 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4529 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4530 const EVT *VTs, unsigned NumVTs,
4531 const SDValue *Ops, unsigned NumOps) {
4533 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4534 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4537 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4538 const SDValue *Ops, unsigned NumOps) {
4539 if (VTList.NumVTs == 1)
4540 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4544 // FIXME: figure out how to safely handle things like
4545 // int foo(int x) { return 1 << (x & 255); }
4546 // int bar() { return foo(256); }
4547 case ISD::SRA_PARTS:
4548 case ISD::SRL_PARTS:
4549 case ISD::SHL_PARTS:
4550 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4551 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4552 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4553 else if (N3.getOpcode() == ISD::AND)
4554 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4555 // If the and is only masking out bits that cannot effect the shift,
4556 // eliminate the and.
4557 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4558 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4559 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4565 // Memoize the node unless it returns a flag.
4567 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4568 FoldingSetNodeID ID;
4569 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4571 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4572 return SDValue(E, 0);
4575 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4576 } else if (NumOps == 2) {
4577 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4578 } else if (NumOps == 3) {
4579 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4582 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4584 CSEMap.InsertNode(N, IP);
4587 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4588 } else if (NumOps == 2) {
4589 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4590 } else if (NumOps == 3) {
4591 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4594 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4597 AllNodes.push_back(N);
4601 return SDValue(N, 0);
4604 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4605 return getNode(Opcode, DL, VTList, 0, 0);
4608 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4610 SDValue Ops[] = { N1 };
4611 return getNode(Opcode, DL, VTList, Ops, 1);
4614 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4615 SDValue N1, SDValue N2) {
4616 SDValue Ops[] = { N1, N2 };
4617 return getNode(Opcode, DL, VTList, Ops, 2);
4620 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4621 SDValue N1, SDValue N2, SDValue N3) {
4622 SDValue Ops[] = { N1, N2, N3 };
4623 return getNode(Opcode, DL, VTList, Ops, 3);
4626 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4627 SDValue N1, SDValue N2, SDValue N3,
4629 SDValue Ops[] = { N1, N2, N3, N4 };
4630 return getNode(Opcode, DL, VTList, Ops, 4);
4633 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4634 SDValue N1, SDValue N2, SDValue N3,
4635 SDValue N4, SDValue N5) {
4636 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4637 return getNode(Opcode, DL, VTList, Ops, 5);
4640 SDVTList SelectionDAG::getVTList(EVT VT) {
4641 return makeVTList(SDNode::getValueTypeList(VT), 1);
4644 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4645 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4646 E = VTList.rend(); I != E; ++I)
4647 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4650 EVT *Array = Allocator.Allocate<EVT>(2);
4653 SDVTList Result = makeVTList(Array, 2);
4654 VTList.push_back(Result);
4658 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4659 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4660 E = VTList.rend(); I != E; ++I)
4661 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4665 EVT *Array = Allocator.Allocate<EVT>(3);
4669 SDVTList Result = makeVTList(Array, 3);
4670 VTList.push_back(Result);
4674 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4675 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4676 E = VTList.rend(); I != E; ++I)
4677 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4678 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4681 EVT *Array = Allocator.Allocate<EVT>(4);
4686 SDVTList Result = makeVTList(Array, 4);
4687 VTList.push_back(Result);
4691 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4693 case 0: llvm_unreachable("Cannot have nodes without results!");
4694 case 1: return getVTList(VTs[0]);
4695 case 2: return getVTList(VTs[0], VTs[1]);
4696 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4697 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4701 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4702 E = VTList.rend(); I != E; ++I) {
4703 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4706 if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2]))
4710 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4711 std::copy(VTs, VTs+NumVTs, Array);
4712 SDVTList Result = makeVTList(Array, NumVTs);
4713 VTList.push_back(Result);
4718 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4719 /// specified operands. If the resultant node already exists in the DAG,
4720 /// this does not modify the specified node, instead it returns the node that
4721 /// already exists. If the resultant node does not exist in the DAG, the
4722 /// input node is returned. As a degenerate case, if you specify the same
4723 /// input operands as the node already has, the input node is returned.
4724 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4725 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4727 // Check to see if there is no change.
4728 if (Op == N->getOperand(0)) return N;
4730 // See if the modified node already exists.
4731 void *InsertPos = 0;
4732 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4735 // Nope it doesn't. Remove the node from its current place in the maps.
4737 if (!RemoveNodeFromCSEMaps(N))
4740 // Now we update the operands.
4741 N->OperandList[0].set(Op);
4743 // If this gets put into a CSE map, add it.
4744 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4748 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4749 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4751 // Check to see if there is no change.
4752 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4753 return N; // No operands changed, just return the input node.
4755 // See if the modified node already exists.
4756 void *InsertPos = 0;
4757 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4760 // Nope it doesn't. Remove the node from its current place in the maps.
4762 if (!RemoveNodeFromCSEMaps(N))
4765 // Now we update the operands.
4766 if (N->OperandList[0] != Op1)
4767 N->OperandList[0].set(Op1);
4768 if (N->OperandList[1] != Op2)
4769 N->OperandList[1].set(Op2);
4771 // If this gets put into a CSE map, add it.
4772 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4776 SDNode *SelectionDAG::
4777 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4778 SDValue Ops[] = { Op1, Op2, Op3 };
4779 return UpdateNodeOperands(N, Ops, 3);
4782 SDNode *SelectionDAG::
4783 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4784 SDValue Op3, SDValue Op4) {
4785 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4786 return UpdateNodeOperands(N, Ops, 4);
4789 SDNode *SelectionDAG::
4790 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4791 SDValue Op3, SDValue Op4, SDValue Op5) {
4792 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4793 return UpdateNodeOperands(N, Ops, 5);
4796 SDNode *SelectionDAG::
4797 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4798 assert(N->getNumOperands() == NumOps &&
4799 "Update with wrong number of operands");
4801 // Check to see if there is no change.
4802 bool AnyChange = false;
4803 for (unsigned i = 0; i != NumOps; ++i) {
4804 if (Ops[i] != N->getOperand(i)) {
4810 // No operands changed, just return the input node.
4811 if (!AnyChange) return N;
4813 // See if the modified node already exists.
4814 void *InsertPos = 0;
4815 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4818 // Nope it doesn't. Remove the node from its current place in the maps.
4820 if (!RemoveNodeFromCSEMaps(N))
4823 // Now we update the operands.
4824 for (unsigned i = 0; i != NumOps; ++i)
4825 if (N->OperandList[i] != Ops[i])
4826 N->OperandList[i].set(Ops[i]);
4828 // If this gets put into a CSE map, add it.
4829 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4833 /// DropOperands - Release the operands and set this node to have
4835 void SDNode::DropOperands() {
4836 // Unlike the code in MorphNodeTo that does this, we don't need to
4837 // watch for dead nodes here.
4838 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4844 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4847 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4849 SDVTList VTs = getVTList(VT);
4850 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4853 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4854 EVT VT, SDValue Op1) {
4855 SDVTList VTs = getVTList(VT);
4856 SDValue Ops[] = { Op1 };
4857 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4860 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4861 EVT VT, SDValue Op1,
4863 SDVTList VTs = getVTList(VT);
4864 SDValue Ops[] = { Op1, Op2 };
4865 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4868 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4869 EVT VT, SDValue Op1,
4870 SDValue Op2, SDValue Op3) {
4871 SDVTList VTs = getVTList(VT);
4872 SDValue Ops[] = { Op1, Op2, Op3 };
4873 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4876 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4877 EVT VT, const SDValue *Ops,
4879 SDVTList VTs = getVTList(VT);
4880 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4883 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4884 EVT VT1, EVT VT2, const SDValue *Ops,
4886 SDVTList VTs = getVTList(VT1, VT2);
4887 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4890 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4892 SDVTList VTs = getVTList(VT1, VT2);
4893 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4896 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4897 EVT VT1, EVT VT2, EVT VT3,
4898 const SDValue *Ops, unsigned NumOps) {
4899 SDVTList VTs = getVTList(VT1, VT2, VT3);
4900 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4903 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4904 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4905 const SDValue *Ops, unsigned NumOps) {
4906 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4907 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4910 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4913 SDVTList VTs = getVTList(VT1, VT2);
4914 SDValue Ops[] = { Op1 };
4915 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4918 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4920 SDValue Op1, SDValue Op2) {
4921 SDVTList VTs = getVTList(VT1, VT2);
4922 SDValue Ops[] = { Op1, Op2 };
4923 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4926 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4928 SDValue Op1, SDValue Op2,
4930 SDVTList VTs = getVTList(VT1, VT2);
4931 SDValue Ops[] = { Op1, Op2, Op3 };
4932 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4935 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4936 EVT VT1, EVT VT2, EVT VT3,
4937 SDValue Op1, SDValue Op2,
4939 SDVTList VTs = getVTList(VT1, VT2, VT3);
4940 SDValue Ops[] = { Op1, Op2, Op3 };
4941 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4944 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4945 SDVTList VTs, const SDValue *Ops,
4947 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
4948 // Reset the NodeID to -1.
4953 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
4954 /// the line number information on the merged node since it is not possible to
4955 /// preserve the information that operation is associated with multiple lines.
4956 /// This will make the debugger working better at -O0, were there is a higher
4957 /// probability having other instructions associated with that line.
4959 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
4960 DebugLoc NLoc = N->getDebugLoc();
4961 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
4962 N->setDebugLoc(DebugLoc());
4967 /// MorphNodeTo - This *mutates* the specified node to have the specified
4968 /// return type, opcode, and operands.
4970 /// Note that MorphNodeTo returns the resultant node. If there is already a
4971 /// node of the specified opcode and operands, it returns that node instead of
4972 /// the current one. Note that the DebugLoc need not be the same.
4974 /// Using MorphNodeTo is faster than creating a new node and swapping it in
4975 /// with ReplaceAllUsesWith both because it often avoids allocating a new
4976 /// node, and because it doesn't require CSE recalculation for any of
4977 /// the node's users.
4979 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
4980 SDVTList VTs, const SDValue *Ops,
4982 // If an identical node already exists, use it.
4984 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
4985 FoldingSetNodeID ID;
4986 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
4987 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
4988 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
4991 if (!RemoveNodeFromCSEMaps(N))
4994 // Start the morphing.
4996 N->ValueList = VTs.VTs;
4997 N->NumValues = VTs.NumVTs;
4999 // Clear the operands list, updating used nodes to remove this from their
5000 // use list. Keep track of any operands that become dead as a result.
5001 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5002 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5004 SDNode *Used = Use.getNode();
5006 if (Used->use_empty())
5007 DeadNodeSet.insert(Used);
5010 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5011 // Initialize the memory references information.
5012 MN->setMemRefs(0, 0);
5013 // If NumOps is larger than the # of operands we can have in a
5014 // MachineSDNode, reallocate the operand list.
5015 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5016 if (MN->OperandsNeedDelete)
5017 delete[] MN->OperandList;
5018 if (NumOps > array_lengthof(MN->LocalOperands))
5019 // We're creating a final node that will live unmorphed for the
5020 // remainder of the current SelectionDAG iteration, so we can allocate
5021 // the operands directly out of a pool with no recycling metadata.
5022 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5025 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5026 MN->OperandsNeedDelete = false;
5028 MN->InitOperands(MN->OperandList, Ops, NumOps);
5030 // If NumOps is larger than the # of operands we currently have, reallocate
5031 // the operand list.
5032 if (NumOps > N->NumOperands) {
5033 if (N->OperandsNeedDelete)
5034 delete[] N->OperandList;
5035 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5036 N->OperandsNeedDelete = true;
5038 N->InitOperands(N->OperandList, Ops, NumOps);
5041 // Delete any nodes that are still dead after adding the uses for the
5043 if (!DeadNodeSet.empty()) {
5044 SmallVector<SDNode *, 16> DeadNodes;
5045 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5046 E = DeadNodeSet.end(); I != E; ++I)
5047 if ((*I)->use_empty())
5048 DeadNodes.push_back(*I);
5049 RemoveDeadNodes(DeadNodes);
5053 CSEMap.InsertNode(N, IP); // Memoize the new node.
5058 /// getMachineNode - These are used for target selectors to create a new node
5059 /// with specified return type(s), MachineInstr opcode, and operands.
5061 /// Note that getMachineNode returns the resultant node. If there is already a
5062 /// node of the specified opcode and operands, it returns that node instead of
5063 /// the current one.
5065 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5066 SDVTList VTs = getVTList(VT);
5067 return getMachineNode(Opcode, dl, VTs, 0, 0);
5071 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5072 SDVTList VTs = getVTList(VT);
5073 SDValue Ops[] = { Op1 };
5074 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5078 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5079 SDValue Op1, SDValue Op2) {
5080 SDVTList VTs = getVTList(VT);
5081 SDValue Ops[] = { Op1, Op2 };
5082 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5086 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5087 SDValue Op1, SDValue Op2, SDValue Op3) {
5088 SDVTList VTs = getVTList(VT);
5089 SDValue Ops[] = { Op1, Op2, Op3 };
5090 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5094 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5095 const SDValue *Ops, unsigned NumOps) {
5096 SDVTList VTs = getVTList(VT);
5097 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5101 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5102 SDVTList VTs = getVTList(VT1, VT2);
5103 return getMachineNode(Opcode, dl, VTs, 0, 0);
5107 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5108 EVT VT1, EVT VT2, SDValue Op1) {
5109 SDVTList VTs = getVTList(VT1, VT2);
5110 SDValue Ops[] = { Op1 };
5111 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5115 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5116 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5117 SDVTList VTs = getVTList(VT1, VT2);
5118 SDValue Ops[] = { Op1, Op2 };
5119 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5123 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5124 EVT VT1, EVT VT2, SDValue Op1,
5125 SDValue Op2, SDValue Op3) {
5126 SDVTList VTs = getVTList(VT1, VT2);
5127 SDValue Ops[] = { Op1, Op2, Op3 };
5128 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5132 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5134 const SDValue *Ops, unsigned NumOps) {
5135 SDVTList VTs = getVTList(VT1, VT2);
5136 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5140 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5141 EVT VT1, EVT VT2, EVT VT3,
5142 SDValue Op1, SDValue Op2) {
5143 SDVTList VTs = getVTList(VT1, VT2, VT3);
5144 SDValue Ops[] = { Op1, Op2 };
5145 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5149 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5150 EVT VT1, EVT VT2, EVT VT3,
5151 SDValue Op1, SDValue Op2, SDValue Op3) {
5152 SDVTList VTs = getVTList(VT1, VT2, VT3);
5153 SDValue Ops[] = { Op1, Op2, Op3 };
5154 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5158 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5159 EVT VT1, EVT VT2, EVT VT3,
5160 const SDValue *Ops, unsigned NumOps) {
5161 SDVTList VTs = getVTList(VT1, VT2, VT3);
5162 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5166 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5167 EVT VT2, EVT VT3, EVT VT4,
5168 const SDValue *Ops, unsigned NumOps) {
5169 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5170 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5174 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5175 const std::vector<EVT> &ResultTys,
5176 const SDValue *Ops, unsigned NumOps) {
5177 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5178 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5182 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5183 const SDValue *Ops, unsigned NumOps) {
5184 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5189 FoldingSetNodeID ID;
5190 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5192 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5193 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5197 // Allocate a new MachineSDNode.
5198 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5200 // Initialize the operands list.
5201 if (NumOps > array_lengthof(N->LocalOperands))
5202 // We're creating a final node that will live unmorphed for the
5203 // remainder of the current SelectionDAG iteration, so we can allocate
5204 // the operands directly out of a pool with no recycling metadata.
5205 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5208 N->InitOperands(N->LocalOperands, Ops, NumOps);
5209 N->OperandsNeedDelete = false;
5212 CSEMap.InsertNode(N, IP);
5214 AllNodes.push_back(N);
5216 VerifyMachineNode(N);
5221 /// getTargetExtractSubreg - A convenience function for creating
5222 /// TargetOpcode::EXTRACT_SUBREG nodes.
5224 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5226 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5227 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5228 VT, Operand, SRIdxVal);
5229 return SDValue(Subreg, 0);
5232 /// getTargetInsertSubreg - A convenience function for creating
5233 /// TargetOpcode::INSERT_SUBREG nodes.
5235 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5236 SDValue Operand, SDValue Subreg) {
5237 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5238 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5239 VT, Operand, Subreg, SRIdxVal);
5240 return SDValue(Result, 0);
5243 /// getNodeIfExists - Get the specified node if it's already available, or
5244 /// else return NULL.
5245 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5246 const SDValue *Ops, unsigned NumOps) {
5247 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5248 FoldingSetNodeID ID;
5249 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5251 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5257 /// getDbgValue - Creates a SDDbgValue node.
5260 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5261 DebugLoc DL, unsigned O) {
5262 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5266 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5267 DebugLoc DL, unsigned O) {
5268 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5272 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5273 DebugLoc DL, unsigned O) {
5274 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5279 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5280 /// pointed to by a use iterator is deleted, increment the use iterator
5281 /// so that it doesn't dangle.
5283 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5284 SDNode::use_iterator &UI;
5285 SDNode::use_iterator &UE;
5287 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5288 // Increment the iterator as needed.
5289 while (UI != UE && N == *UI)
5294 RAUWUpdateListener(SelectionDAG &d,
5295 SDNode::use_iterator &ui,
5296 SDNode::use_iterator &ue)
5297 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5302 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5303 /// This can cause recursive merging of nodes in the DAG.
5305 /// This version assumes From has a single result value.
5307 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5308 SDNode *From = FromN.getNode();
5309 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5310 "Cannot replace with this method!");
5311 assert(From != To.getNode() && "Cannot replace uses of with self");
5313 // Iterate over all the existing uses of From. New uses will be added
5314 // to the beginning of the use list, which we avoid visiting.
5315 // This specifically avoids visiting uses of From that arise while the
5316 // replacement is happening, because any such uses would be the result
5317 // of CSE: If an existing node looks like From after one of its operands
5318 // is replaced by To, we don't want to replace of all its users with To
5319 // too. See PR3018 for more info.
5320 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5321 RAUWUpdateListener Listener(*this, UI, UE);
5325 // This node is about to morph, remove its old self from the CSE maps.
5326 RemoveNodeFromCSEMaps(User);
5328 // A user can appear in a use list multiple times, and when this
5329 // happens the uses are usually next to each other in the list.
5330 // To help reduce the number of CSE recomputations, process all
5331 // the uses of this user that we can find this way.
5333 SDUse &Use = UI.getUse();
5336 } while (UI != UE && *UI == User);
5338 // Now that we have modified User, add it back to the CSE maps. If it
5339 // already exists there, recursively merge the results together.
5340 AddModifiedNodeToCSEMaps(User);
5343 // If we just RAUW'd the root, take note.
5344 if (FromN == getRoot())
5348 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5349 /// This can cause recursive merging of nodes in the DAG.
5351 /// This version assumes that for each value of From, there is a
5352 /// corresponding value in To in the same position with the same type.
5354 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5356 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5357 assert((!From->hasAnyUseOfValue(i) ||
5358 From->getValueType(i) == To->getValueType(i)) &&
5359 "Cannot use this version of ReplaceAllUsesWith!");
5362 // Handle the trivial case.
5366 // Iterate over just the existing users of From. See the comments in
5367 // the ReplaceAllUsesWith above.
5368 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5369 RAUWUpdateListener Listener(*this, UI, UE);
5373 // This node is about to morph, remove its old self from the CSE maps.
5374 RemoveNodeFromCSEMaps(User);
5376 // A user can appear in a use list multiple times, and when this
5377 // happens the uses are usually next to each other in the list.
5378 // To help reduce the number of CSE recomputations, process all
5379 // the uses of this user that we can find this way.
5381 SDUse &Use = UI.getUse();
5384 } while (UI != UE && *UI == User);
5386 // Now that we have modified User, add it back to the CSE maps. If it
5387 // already exists there, recursively merge the results together.
5388 AddModifiedNodeToCSEMaps(User);
5391 // If we just RAUW'd the root, take note.
5392 if (From == getRoot().getNode())
5393 setRoot(SDValue(To, getRoot().getResNo()));
5396 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5397 /// This can cause recursive merging of nodes in the DAG.
5399 /// This version can replace From with any result values. To must match the
5400 /// number and types of values returned by From.
5401 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5402 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5403 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5405 // Iterate over just the existing users of From. See the comments in
5406 // the ReplaceAllUsesWith above.
5407 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5408 RAUWUpdateListener Listener(*this, UI, UE);
5412 // This node is about to morph, remove its old self from the CSE maps.
5413 RemoveNodeFromCSEMaps(User);
5415 // A user can appear in a use list multiple times, and when this
5416 // happens the uses are usually next to each other in the list.
5417 // To help reduce the number of CSE recomputations, process all
5418 // the uses of this user that we can find this way.
5420 SDUse &Use = UI.getUse();
5421 const SDValue &ToOp = To[Use.getResNo()];
5424 } while (UI != UE && *UI == User);
5426 // Now that we have modified User, add it back to the CSE maps. If it
5427 // already exists there, recursively merge the results together.
5428 AddModifiedNodeToCSEMaps(User);
5431 // If we just RAUW'd the root, take note.
5432 if (From == getRoot().getNode())
5433 setRoot(SDValue(To[getRoot().getResNo()]));
5436 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5437 /// uses of other values produced by From.getNode() alone. The Deleted
5438 /// vector is handled the same way as for ReplaceAllUsesWith.
5439 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5440 // Handle the really simple, really trivial case efficiently.
5441 if (From == To) return;
5443 // Handle the simple, trivial, case efficiently.
5444 if (From.getNode()->getNumValues() == 1) {
5445 ReplaceAllUsesWith(From, To);
5449 // Iterate over just the existing users of From. See the comments in
5450 // the ReplaceAllUsesWith above.
5451 SDNode::use_iterator UI = From.getNode()->use_begin(),
5452 UE = From.getNode()->use_end();
5453 RAUWUpdateListener Listener(*this, UI, UE);
5456 bool UserRemovedFromCSEMaps = false;
5458 // A user can appear in a use list multiple times, and when this
5459 // happens the uses are usually next to each other in the list.
5460 // To help reduce the number of CSE recomputations, process all
5461 // the uses of this user that we can find this way.
5463 SDUse &Use = UI.getUse();
5465 // Skip uses of different values from the same node.
5466 if (Use.getResNo() != From.getResNo()) {
5471 // If this node hasn't been modified yet, it's still in the CSE maps,
5472 // so remove its old self from the CSE maps.
5473 if (!UserRemovedFromCSEMaps) {
5474 RemoveNodeFromCSEMaps(User);
5475 UserRemovedFromCSEMaps = true;
5480 } while (UI != UE && *UI == User);
5482 // We are iterating over all uses of the From node, so if a use
5483 // doesn't use the specific value, no changes are made.
5484 if (!UserRemovedFromCSEMaps)
5487 // Now that we have modified User, add it back to the CSE maps. If it
5488 // already exists there, recursively merge the results together.
5489 AddModifiedNodeToCSEMaps(User);
5492 // If we just RAUW'd the root, take note.
5493 if (From == getRoot())
5498 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5499 /// to record information about a use.
5506 /// operator< - Sort Memos by User.
5507 bool operator<(const UseMemo &L, const UseMemo &R) {
5508 return (intptr_t)L.User < (intptr_t)R.User;
5512 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5513 /// uses of other values produced by From.getNode() alone. The same value
5514 /// may appear in both the From and To list. The Deleted vector is
5515 /// handled the same way as for ReplaceAllUsesWith.
5516 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5519 // Handle the simple, trivial case efficiently.
5521 return ReplaceAllUsesOfValueWith(*From, *To);
5523 // Read up all the uses and make records of them. This helps
5524 // processing new uses that are introduced during the
5525 // replacement process.
5526 SmallVector<UseMemo, 4> Uses;
5527 for (unsigned i = 0; i != Num; ++i) {
5528 unsigned FromResNo = From[i].getResNo();
5529 SDNode *FromNode = From[i].getNode();
5530 for (SDNode::use_iterator UI = FromNode->use_begin(),
5531 E = FromNode->use_end(); UI != E; ++UI) {
5532 SDUse &Use = UI.getUse();
5533 if (Use.getResNo() == FromResNo) {
5534 UseMemo Memo = { *UI, i, &Use };
5535 Uses.push_back(Memo);
5540 // Sort the uses, so that all the uses from a given User are together.
5541 std::sort(Uses.begin(), Uses.end());
5543 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5544 UseIndex != UseIndexEnd; ) {
5545 // We know that this user uses some value of From. If it is the right
5546 // value, update it.
5547 SDNode *User = Uses[UseIndex].User;
5549 // This node is about to morph, remove its old self from the CSE maps.
5550 RemoveNodeFromCSEMaps(User);
5552 // The Uses array is sorted, so all the uses for a given User
5553 // are next to each other in the list.
5554 // To help reduce the number of CSE recomputations, process all
5555 // the uses of this user that we can find this way.
5557 unsigned i = Uses[UseIndex].Index;
5558 SDUse &Use = *Uses[UseIndex].Use;
5562 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5564 // Now that we have modified User, add it back to the CSE maps. If it
5565 // already exists there, recursively merge the results together.
5566 AddModifiedNodeToCSEMaps(User);
5570 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5571 /// based on their topological order. It returns the maximum id and a vector
5572 /// of the SDNodes* in assigned order by reference.
5573 unsigned SelectionDAG::AssignTopologicalOrder() {
5575 unsigned DAGSize = 0;
5577 // SortedPos tracks the progress of the algorithm. Nodes before it are
5578 // sorted, nodes after it are unsorted. When the algorithm completes
5579 // it is at the end of the list.
5580 allnodes_iterator SortedPos = allnodes_begin();
5582 // Visit all the nodes. Move nodes with no operands to the front of
5583 // the list immediately. Annotate nodes that do have operands with their
5584 // operand count. Before we do this, the Node Id fields of the nodes
5585 // may contain arbitrary values. After, the Node Id fields for nodes
5586 // before SortedPos will contain the topological sort index, and the
5587 // Node Id fields for nodes At SortedPos and after will contain the
5588 // count of outstanding operands.
5589 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5592 unsigned Degree = N->getNumOperands();
5594 // A node with no uses, add it to the result array immediately.
5595 N->setNodeId(DAGSize++);
5596 allnodes_iterator Q = N;
5598 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5599 assert(SortedPos != AllNodes.end() && "Overran node list");
5602 // Temporarily use the Node Id as scratch space for the degree count.
5603 N->setNodeId(Degree);
5607 // Visit all the nodes. As we iterate, move nodes into sorted order,
5608 // such that by the time the end is reached all nodes will be sorted.
5609 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5612 // N is in sorted position, so all its uses have one less operand
5613 // that needs to be sorted.
5614 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5617 unsigned Degree = P->getNodeId();
5618 assert(Degree != 0 && "Invalid node degree");
5621 // All of P's operands are sorted, so P may sorted now.
5622 P->setNodeId(DAGSize++);
5624 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5625 assert(SortedPos != AllNodes.end() && "Overran node list");
5628 // Update P's outstanding operand count.
5629 P->setNodeId(Degree);
5632 if (I == SortedPos) {
5635 dbgs() << "Overran sorted position:\n";
5638 llvm_unreachable(0);
5642 assert(SortedPos == AllNodes.end() &&
5643 "Topological sort incomplete!");
5644 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5645 "First node in topological sort is not the entry token!");
5646 assert(AllNodes.front().getNodeId() == 0 &&
5647 "First node in topological sort has non-zero id!");
5648 assert(AllNodes.front().getNumOperands() == 0 &&
5649 "First node in topological sort has operands!");
5650 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5651 "Last node in topologic sort has unexpected id!");
5652 assert(AllNodes.back().use_empty() &&
5653 "Last node in topologic sort has users!");
5654 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5658 /// AssignOrdering - Assign an order to the SDNode.
5659 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5660 assert(SD && "Trying to assign an order to a null node!");
5661 Ordering->add(SD, Order);
5664 /// GetOrdering - Get the order for the SDNode.
5665 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5666 assert(SD && "Trying to get the order of a null node!");
5667 return Ordering->getOrder(SD);
5670 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5671 /// value is produced by SD.
5672 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5673 DbgInfo->add(DB, SD, isParameter);
5675 SD->setHasDebugValue(true);
5678 /// TransferDbgValues - Transfer SDDbgValues.
5679 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5680 if (From == To || !From.getNode()->getHasDebugValue())
5682 SDNode *FromNode = From.getNode();
5683 SDNode *ToNode = To.getNode();
5684 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5685 SmallVector<SDDbgValue *, 2> ClonedDVs;
5686 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5688 SDDbgValue *Dbg = *I;
5689 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5690 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5691 Dbg->getOffset(), Dbg->getDebugLoc(),
5693 ClonedDVs.push_back(Clone);
5696 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5697 E = ClonedDVs.end(); I != E; ++I)
5698 AddDbgValue(*I, ToNode, false);
5701 //===----------------------------------------------------------------------===//
5703 //===----------------------------------------------------------------------===//
5705 HandleSDNode::~HandleSDNode() {
5709 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5710 const GlobalValue *GA,
5711 EVT VT, int64_t o, unsigned char TF)
5712 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5716 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5717 MachineMemOperand *mmo)
5718 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5719 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5720 MMO->isNonTemporal(), MMO->isInvariant());
5721 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5722 assert(isNonTemporal() == MMO->isNonTemporal() &&
5723 "Non-temporal encoding error!");
5724 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5727 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5728 const SDValue *Ops, unsigned NumOps, EVT memvt,
5729 MachineMemOperand *mmo)
5730 : SDNode(Opc, dl, VTs, Ops, NumOps),
5731 MemoryVT(memvt), MMO(mmo) {
5732 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5733 MMO->isNonTemporal(), MMO->isInvariant());
5734 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5735 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5738 /// Profile - Gather unique data for the node.
5740 void SDNode::Profile(FoldingSetNodeID &ID) const {
5741 AddNodeIDNode(ID, this);
5746 std::vector<EVT> VTs;
5749 VTs.reserve(MVT::LAST_VALUETYPE);
5750 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5751 VTs.push_back(MVT((MVT::SimpleValueType)i));
5756 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5757 static ManagedStatic<EVTArray> SimpleVTArray;
5758 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5760 /// getValueTypeList - Return a pointer to the specified value type.
5762 const EVT *SDNode::getValueTypeList(EVT VT) {
5763 if (VT.isExtended()) {
5764 sys::SmartScopedLock<true> Lock(*VTMutex);
5765 return &(*EVTs->insert(VT).first);
5767 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5768 "Value type out of range!");
5769 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5773 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5774 /// indicated value. This method ignores uses of other values defined by this
5776 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5777 assert(Value < getNumValues() && "Bad value!");
5779 // TODO: Only iterate over uses of a given value of the node
5780 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5781 if (UI.getUse().getResNo() == Value) {
5788 // Found exactly the right number of uses?
5793 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5794 /// value. This method ignores uses of other values defined by this operation.
5795 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5796 assert(Value < getNumValues() && "Bad value!");
5798 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5799 if (UI.getUse().getResNo() == Value)
5806 /// isOnlyUserOf - Return true if this node is the only use of N.
5808 bool SDNode::isOnlyUserOf(SDNode *N) const {
5810 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5821 /// isOperand - Return true if this node is an operand of N.
5823 bool SDValue::isOperandOf(SDNode *N) const {
5824 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5825 if (*this == N->getOperand(i))
5830 bool SDNode::isOperandOf(SDNode *N) const {
5831 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5832 if (this == N->OperandList[i].getNode())
5837 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5838 /// be a chain) reaches the specified operand without crossing any
5839 /// side-effecting instructions on any chain path. In practice, this looks
5840 /// through token factors and non-volatile loads. In order to remain efficient,
5841 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5842 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5843 unsigned Depth) const {
5844 if (*this == Dest) return true;
5846 // Don't search too deeply, we just want to be able to see through
5847 // TokenFactor's etc.
5848 if (Depth == 0) return false;
5850 // If this is a token factor, all inputs to the TF happen in parallel. If any
5851 // of the operands of the TF does not reach dest, then we cannot do the xform.
5852 if (getOpcode() == ISD::TokenFactor) {
5853 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5854 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5859 // Loads don't have side effects, look through them.
5860 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5861 if (!Ld->isVolatile())
5862 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5867 /// hasPredecessor - Return true if N is a predecessor of this node.
5868 /// N is either an operand of this node, or can be reached by recursively
5869 /// traversing up the operands.
5870 /// NOTE: This is an expensive method. Use it carefully.
5871 bool SDNode::hasPredecessor(const SDNode *N) const {
5872 SmallPtrSet<const SDNode *, 32> Visited;
5873 SmallVector<const SDNode *, 16> Worklist;
5874 return hasPredecessorHelper(N, Visited, Worklist);
5877 bool SDNode::hasPredecessorHelper(const SDNode *N,
5878 SmallPtrSet<const SDNode *, 32> &Visited,
5879 SmallVector<const SDNode *, 16> &Worklist) const {
5880 if (Visited.empty()) {
5881 Worklist.push_back(this);
5883 // Take a look in the visited set. If we've already encountered this node
5884 // we needn't search further.
5885 if (Visited.count(N))
5889 // Haven't visited N yet. Continue the search.
5890 while (!Worklist.empty()) {
5891 const SDNode *M = Worklist.pop_back_val();
5892 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5893 SDNode *Op = M->getOperand(i).getNode();
5894 if (Visited.insert(Op))
5895 Worklist.push_back(Op);
5904 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5905 assert(Num < NumOperands && "Invalid child # of SDNode!");
5906 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5909 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5910 assert(N->getNumValues() == 1 &&
5911 "Can't unroll a vector with multiple results!");
5913 EVT VT = N->getValueType(0);
5914 unsigned NE = VT.getVectorNumElements();
5915 EVT EltVT = VT.getVectorElementType();
5916 DebugLoc dl = N->getDebugLoc();
5918 SmallVector<SDValue, 8> Scalars;
5919 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5921 // If ResNE is 0, fully unroll the vector op.
5924 else if (NE > ResNE)
5928 for (i= 0; i != NE; ++i) {
5929 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5930 SDValue Operand = N->getOperand(j);
5931 EVT OperandVT = Operand.getValueType();
5932 if (OperandVT.isVector()) {
5933 // A vector operand; extract a single element.
5934 EVT OperandEltVT = OperandVT.getVectorElementType();
5935 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
5938 getConstant(i, TLI.getPointerTy()));
5940 // A scalar operand; just use it as is.
5941 Operands[j] = Operand;
5945 switch (N->getOpcode()) {
5947 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5948 &Operands[0], Operands.size()));
5951 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
5952 &Operands[0], Operands.size()));
5959 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
5960 getShiftAmountOperand(Operands[0].getValueType(),
5963 case ISD::SIGN_EXTEND_INREG:
5964 case ISD::FP_ROUND_INREG: {
5965 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
5966 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
5968 getValueType(ExtVT)));
5973 for (; i < ResNE; ++i)
5974 Scalars.push_back(getUNDEF(EltVT));
5976 return getNode(ISD::BUILD_VECTOR, dl,
5977 EVT::getVectorVT(*getContext(), EltVT, ResNE),
5978 &Scalars[0], Scalars.size());
5982 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
5983 /// location that is 'Dist' units away from the location that the 'Base' load
5984 /// is loading from.
5985 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
5986 unsigned Bytes, int Dist) const {
5987 if (LD->getChain() != Base->getChain())
5989 EVT VT = LD->getValueType(0);
5990 if (VT.getSizeInBits() / 8 != Bytes)
5993 SDValue Loc = LD->getOperand(1);
5994 SDValue BaseLoc = Base->getOperand(1);
5995 if (Loc.getOpcode() == ISD::FrameIndex) {
5996 if (BaseLoc.getOpcode() != ISD::FrameIndex)
5998 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
5999 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6000 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6001 int FS = MFI->getObjectSize(FI);
6002 int BFS = MFI->getObjectSize(BFI);
6003 if (FS != BFS || FS != (int)Bytes) return false;
6004 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6008 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6009 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6012 const GlobalValue *GV1 = NULL;
6013 const GlobalValue *GV2 = NULL;
6014 int64_t Offset1 = 0;
6015 int64_t Offset2 = 0;
6016 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6017 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6018 if (isGA1 && isGA2 && GV1 == GV2)
6019 return Offset1 == (Offset2 + Dist*Bytes);
6024 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6025 /// it cannot be inferred.
6026 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6027 // If this is a GlobalAddress + cst, return the alignment.
6028 const GlobalValue *GV;
6029 int64_t GVOffset = 0;
6030 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6031 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6032 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6033 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6034 TLI.getTargetData());
6035 unsigned AlignBits = KnownZero.countTrailingOnes();
6036 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6038 return MinAlign(Align, GVOffset);
6041 // If this is a direct reference to a stack slot, use information about the
6042 // stack slot's alignment.
6043 int FrameIdx = 1 << 31;
6044 int64_t FrameOffset = 0;
6045 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6046 FrameIdx = FI->getIndex();
6047 } else if (isBaseWithConstantOffset(Ptr) &&
6048 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6050 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6051 FrameOffset = Ptr.getConstantOperandVal(1);
6054 if (FrameIdx != (1 << 31)) {
6055 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6056 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6064 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6065 unsigned GlobalAddressSDNode::getAddressSpace() const {
6066 return getGlobal()->getType()->getAddressSpace();
6070 Type *ConstantPoolSDNode::getType() const {
6071 if (isMachineConstantPoolEntry())
6072 return Val.MachineCPVal->getType();
6073 return Val.ConstVal->getType();
6076 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6078 unsigned &SplatBitSize,
6080 unsigned MinSplatBits,
6082 EVT VT = getValueType(0);
6083 assert(VT.isVector() && "Expected a vector type");
6084 unsigned sz = VT.getSizeInBits();
6085 if (MinSplatBits > sz)
6088 SplatValue = APInt(sz, 0);
6089 SplatUndef = APInt(sz, 0);
6091 // Get the bits. Bits with undefined values (when the corresponding element
6092 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6093 // in SplatValue. If any of the values are not constant, give up and return
6095 unsigned int nOps = getNumOperands();
6096 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6097 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6099 for (unsigned j = 0; j < nOps; ++j) {
6100 unsigned i = isBigEndian ? nOps-1-j : j;
6101 SDValue OpVal = getOperand(i);
6102 unsigned BitPos = j * EltBitSize;
6104 if (OpVal.getOpcode() == ISD::UNDEF)
6105 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6106 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6107 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6108 zextOrTrunc(sz) << BitPos;
6109 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6110 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6115 // The build_vector is all constants or undefs. Find the smallest element
6116 // size that splats the vector.
6118 HasAnyUndefs = (SplatUndef != 0);
6121 unsigned HalfSize = sz / 2;
6122 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6123 APInt LowValue = SplatValue.trunc(HalfSize);
6124 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6125 APInt LowUndef = SplatUndef.trunc(HalfSize);
6127 // If the two halves do not match (ignoring undef bits), stop here.
6128 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6129 MinSplatBits > HalfSize)
6132 SplatValue = HighValue | LowValue;
6133 SplatUndef = HighUndef & LowUndef;
6142 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6143 // Find the first non-undef value in the shuffle mask.
6145 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6148 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6150 // Make sure all remaining elements are either undef or the same as the first
6152 for (int Idx = Mask[i]; i != e; ++i)
6153 if (Mask[i] >= 0 && Mask[i] != Idx)
6159 static void checkForCyclesHelper(const SDNode *N,
6160 SmallPtrSet<const SDNode*, 32> &Visited,
6161 SmallPtrSet<const SDNode*, 32> &Checked) {
6162 // If this node has already been checked, don't check it again.
6163 if (Checked.count(N))
6166 // If a node has already been visited on this depth-first walk, reject it as
6168 if (!Visited.insert(N)) {
6169 dbgs() << "Offending node:\n";
6171 errs() << "Detected cycle in SelectionDAG\n";
6175 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6176 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6183 void llvm::checkForCycles(const llvm::SDNode *N) {
6185 assert(N && "Checking nonexistant SDNode");
6186 SmallPtrSet<const SDNode*, 32> visited;
6187 SmallPtrSet<const SDNode*, 32> checked;
6188 checkForCyclesHelper(N, visited, checked);
6192 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6193 checkForCycles(DAG->getRoot().getNode());