1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeOrdering.h"
16 #include "SDNodeDbgValue.h"
17 #include "llvm/CallingConv.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DebugInfo.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/GlobalAlias.h"
23 #include "llvm/GlobalVariable.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Assembly/Writer.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineConstantPool.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineModuleInfo.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetData.h"
33 #include "llvm/Target/TargetLowering.h"
34 #include "llvm/Target/TargetSelectionDAGInfo.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Target/TargetInstrInfo.h"
37 #include "llvm/Target/TargetIntrinsicInfo.h"
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/ManagedStatic.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Support/Mutex.h"
46 #include "llvm/ADT/SetVector.h"
47 #include "llvm/ADT/SmallPtrSet.h"
48 #include "llvm/ADT/SmallSet.h"
49 #include "llvm/ADT/SmallVector.h"
50 #include "llvm/ADT/StringExtras.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 static const fltSemantics *EVTToAPFloatSemantics(EVT VT) {
63 switch (VT.getSimpleVT().SimpleTy) {
64 default: llvm_unreachable("Unknown FP format");
65 case MVT::f16: return &APFloat::IEEEhalf;
66 case MVT::f32: return &APFloat::IEEEsingle;
67 case MVT::f64: return &APFloat::IEEEdouble;
68 case MVT::f80: return &APFloat::x87DoubleExtended;
69 case MVT::f128: return &APFloat::IEEEquad;
70 case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
74 // Default null implementations of the callbacks.
75 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
76 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
78 //===----------------------------------------------------------------------===//
79 // ConstantFPSDNode Class
80 //===----------------------------------------------------------------------===//
82 /// isExactlyValue - We don't rely on operator== working on double values, as
83 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
84 /// As such, this method can be used to do an exact bit-for-bit comparison of
85 /// two floating point values.
86 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
87 return getValueAPF().bitwiseIsEqual(V);
90 bool ConstantFPSDNode::isValueValidForType(EVT VT,
92 assert(VT.isFloatingPoint() && "Can only convert between FP types");
94 // PPC long double cannot be converted to any other type.
95 if (VT == MVT::ppcf128 ||
96 &Val.getSemantics() == &APFloat::PPCDoubleDouble)
99 // convert modifies in place, so make a copy.
100 APFloat Val2 = APFloat(Val);
102 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven,
107 //===----------------------------------------------------------------------===//
109 //===----------------------------------------------------------------------===//
111 /// isBuildVectorAllOnes - Return true if the specified node is a
112 /// BUILD_VECTOR where all of the elements are ~0 or undef.
113 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
114 // Look through a bit convert.
115 if (N->getOpcode() == ISD::BITCAST)
116 N = N->getOperand(0).getNode();
118 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
120 unsigned i = 0, e = N->getNumOperands();
122 // Skip over all of the undef values.
123 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
126 // Do not accept an all-undef vector.
127 if (i == e) return false;
129 // Do not accept build_vectors that aren't all constants or which have non-~0
130 // elements. We have to be a bit careful here, as the type of the constant
131 // may not be the same as the type of the vector elements due to type
132 // legalization (the elements are promoted to a legal type for the target and
133 // a vector of a type may be legal when the base element type is not).
134 // We only want to check enough bits to cover the vector elements, because
135 // we care if the resultant vector is all ones, not whether the individual
137 SDValue NotZero = N->getOperand(i);
138 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
139 if (isa<ConstantSDNode>(NotZero)) {
140 if (cast<ConstantSDNode>(NotZero)->getAPIntValue().countTrailingOnes() <
143 } else if (isa<ConstantFPSDNode>(NotZero)) {
144 if (cast<ConstantFPSDNode>(NotZero)->getValueAPF()
145 .bitcastToAPInt().countTrailingOnes() < EltSize)
150 // Okay, we have at least one ~0 value, check to see if the rest match or are
151 // undefs. Even with the above element type twiddling, this should be OK, as
152 // the same type legalization should have applied to all the elements.
153 for (++i; i != e; ++i)
154 if (N->getOperand(i) != NotZero &&
155 N->getOperand(i).getOpcode() != ISD::UNDEF)
161 /// isBuildVectorAllZeros - Return true if the specified node is a
162 /// BUILD_VECTOR where all of the elements are 0 or undef.
163 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
164 // Look through a bit convert.
165 if (N->getOpcode() == ISD::BITCAST)
166 N = N->getOperand(0).getNode();
168 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
170 unsigned i = 0, e = N->getNumOperands();
172 // Skip over all of the undef values.
173 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
176 // Do not accept an all-undef vector.
177 if (i == e) return false;
179 // Do not accept build_vectors that aren't all constants or which have non-0
181 SDValue Zero = N->getOperand(i);
182 if (isa<ConstantSDNode>(Zero)) {
183 if (!cast<ConstantSDNode>(Zero)->isNullValue())
185 } else if (isa<ConstantFPSDNode>(Zero)) {
186 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
191 // Okay, we have at least one 0 value, check to see if the rest match or are
193 for (++i; i != e; ++i)
194 if (N->getOperand(i) != Zero &&
195 N->getOperand(i).getOpcode() != ISD::UNDEF)
200 /// isScalarToVector - Return true if the specified node is a
201 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
202 /// element is not an undef.
203 bool ISD::isScalarToVector(const SDNode *N) {
204 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
207 if (N->getOpcode() != ISD::BUILD_VECTOR)
209 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
211 unsigned NumElems = N->getNumOperands();
214 for (unsigned i = 1; i < NumElems; ++i) {
215 SDValue V = N->getOperand(i);
216 if (V.getOpcode() != ISD::UNDEF)
222 /// allOperandsUndef - Return true if the node has at least one operand
223 /// and all operands of the specified node are ISD::UNDEF.
224 bool ISD::allOperandsUndef(const SDNode *N) {
225 // Return false if the node has no operands.
226 // This is "logically inconsistent" with the definition of "all" but
227 // is probably the desired behavior.
228 if (N->getNumOperands() == 0)
231 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
232 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
238 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
239 /// when given the operation for (X op Y).
240 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
241 // To perform this operation, we just need to swap the L and G bits of the
243 unsigned OldL = (Operation >> 2) & 1;
244 unsigned OldG = (Operation >> 1) & 1;
245 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
246 (OldL << 1) | // New G bit
247 (OldG << 2)); // New L bit.
250 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
251 /// 'op' is a valid SetCC operation.
252 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
253 unsigned Operation = Op;
255 Operation ^= 7; // Flip L, G, E bits, but not U.
257 Operation ^= 15; // Flip all of the condition bits.
259 if (Operation > ISD::SETTRUE2)
260 Operation &= ~8; // Don't let N and U bits get set.
262 return ISD::CondCode(Operation);
266 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
267 /// signed operation and 2 if the result is an unsigned comparison. Return zero
268 /// if the operation does not depend on the sign of the input (setne and seteq).
269 static int isSignedOp(ISD::CondCode Opcode) {
271 default: llvm_unreachable("Illegal integer setcc operation!");
273 case ISD::SETNE: return 0;
277 case ISD::SETGE: return 1;
281 case ISD::SETUGE: return 2;
285 /// getSetCCOrOperation - Return the result of a logical OR between different
286 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
287 /// returns SETCC_INVALID if it is not possible to represent the resultant
289 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
291 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
292 // Cannot fold a signed integer setcc with an unsigned integer setcc.
293 return ISD::SETCC_INVALID;
295 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
297 // If the N and U bits get set then the resultant comparison DOES suddenly
298 // care about orderedness, and is true when ordered.
299 if (Op > ISD::SETTRUE2)
300 Op &= ~16; // Clear the U bit if the N bit is set.
302 // Canonicalize illegal integer setcc's.
303 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
306 return ISD::CondCode(Op);
309 /// getSetCCAndOperation - Return the result of a logical AND between different
310 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
311 /// function returns zero if it is not possible to represent the resultant
313 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
315 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
316 // Cannot fold a signed setcc with an unsigned setcc.
317 return ISD::SETCC_INVALID;
319 // Combine all of the condition bits.
320 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
322 // Canonicalize illegal integer setcc's.
326 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
327 case ISD::SETOEQ: // SETEQ & SETU[LG]E
328 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
329 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
330 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
337 //===----------------------------------------------------------------------===//
338 // SDNode Profile Support
339 //===----------------------------------------------------------------------===//
341 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
343 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
347 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
348 /// solely with their pointer.
349 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
350 ID.AddPointer(VTList.VTs);
353 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
355 static void AddNodeIDOperands(FoldingSetNodeID &ID,
356 const SDValue *Ops, unsigned NumOps) {
357 for (; NumOps; --NumOps, ++Ops) {
358 ID.AddPointer(Ops->getNode());
359 ID.AddInteger(Ops->getResNo());
363 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
365 static void AddNodeIDOperands(FoldingSetNodeID &ID,
366 const SDUse *Ops, unsigned NumOps) {
367 for (; NumOps; --NumOps, ++Ops) {
368 ID.AddPointer(Ops->getNode());
369 ID.AddInteger(Ops->getResNo());
373 static void AddNodeIDNode(FoldingSetNodeID &ID,
374 unsigned short OpC, SDVTList VTList,
375 const SDValue *OpList, unsigned N) {
376 AddNodeIDOpcode(ID, OpC);
377 AddNodeIDValueTypes(ID, VTList);
378 AddNodeIDOperands(ID, OpList, N);
381 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
383 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
384 switch (N->getOpcode()) {
385 case ISD::TargetExternalSymbol:
386 case ISD::ExternalSymbol:
387 llvm_unreachable("Should only be used on nodes with operands");
388 default: break; // Normal nodes don't need extra info.
389 case ISD::TargetConstant:
391 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
393 case ISD::TargetConstantFP:
394 case ISD::ConstantFP: {
395 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
398 case ISD::TargetGlobalAddress:
399 case ISD::GlobalAddress:
400 case ISD::TargetGlobalTLSAddress:
401 case ISD::GlobalTLSAddress: {
402 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
403 ID.AddPointer(GA->getGlobal());
404 ID.AddInteger(GA->getOffset());
405 ID.AddInteger(GA->getTargetFlags());
406 ID.AddInteger(GA->getAddressSpace());
409 case ISD::BasicBlock:
410 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
413 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
415 case ISD::RegisterMask:
416 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
419 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
421 case ISD::FrameIndex:
422 case ISD::TargetFrameIndex:
423 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
426 case ISD::TargetJumpTable:
427 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
428 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
430 case ISD::ConstantPool:
431 case ISD::TargetConstantPool: {
432 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
433 ID.AddInteger(CP->getAlignment());
434 ID.AddInteger(CP->getOffset());
435 if (CP->isMachineConstantPoolEntry())
436 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
438 ID.AddPointer(CP->getConstVal());
439 ID.AddInteger(CP->getTargetFlags());
442 case ISD::TargetIndex: {
443 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
444 ID.AddInteger(TI->getIndex());
445 ID.AddInteger(TI->getOffset());
446 ID.AddInteger(TI->getTargetFlags());
450 const LoadSDNode *LD = cast<LoadSDNode>(N);
451 ID.AddInteger(LD->getMemoryVT().getRawBits());
452 ID.AddInteger(LD->getRawSubclassData());
453 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
457 const StoreSDNode *ST = cast<StoreSDNode>(N);
458 ID.AddInteger(ST->getMemoryVT().getRawBits());
459 ID.AddInteger(ST->getRawSubclassData());
460 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
463 case ISD::ATOMIC_CMP_SWAP:
464 case ISD::ATOMIC_SWAP:
465 case ISD::ATOMIC_LOAD_ADD:
466 case ISD::ATOMIC_LOAD_SUB:
467 case ISD::ATOMIC_LOAD_AND:
468 case ISD::ATOMIC_LOAD_OR:
469 case ISD::ATOMIC_LOAD_XOR:
470 case ISD::ATOMIC_LOAD_NAND:
471 case ISD::ATOMIC_LOAD_MIN:
472 case ISD::ATOMIC_LOAD_MAX:
473 case ISD::ATOMIC_LOAD_UMIN:
474 case ISD::ATOMIC_LOAD_UMAX:
475 case ISD::ATOMIC_LOAD:
476 case ISD::ATOMIC_STORE: {
477 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
478 ID.AddInteger(AT->getMemoryVT().getRawBits());
479 ID.AddInteger(AT->getRawSubclassData());
480 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
483 case ISD::PREFETCH: {
484 const MemSDNode *PF = cast<MemSDNode>(N);
485 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
488 case ISD::VECTOR_SHUFFLE: {
489 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
490 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
492 ID.AddInteger(SVN->getMaskElt(i));
495 case ISD::TargetBlockAddress:
496 case ISD::BlockAddress: {
497 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress());
498 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags());
501 } // end switch (N->getOpcode())
503 // Target specific memory nodes could also have address spaces to check.
504 if (N->isTargetMemoryOpcode())
505 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
508 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
510 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
511 AddNodeIDOpcode(ID, N->getOpcode());
512 // Add the return value info.
513 AddNodeIDValueTypes(ID, N->getVTList());
514 // Add the operand info.
515 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
517 // Handle SDNode leafs with special info.
518 AddNodeIDCustom(ID, N);
521 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
522 /// the CSE map that carries volatility, temporalness, indexing mode, and
523 /// extension/truncation information.
525 static inline unsigned
526 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
527 bool isNonTemporal, bool isInvariant) {
528 assert((ConvType & 3) == ConvType &&
529 "ConvType may not require more than 2 bits!");
530 assert((AM & 7) == AM &&
531 "AM may not require more than 3 bits!");
535 (isNonTemporal << 6) |
539 //===----------------------------------------------------------------------===//
540 // SelectionDAG Class
541 //===----------------------------------------------------------------------===//
543 /// doNotCSE - Return true if CSE should not be performed for this node.
544 static bool doNotCSE(SDNode *N) {
545 if (N->getValueType(0) == MVT::Glue)
546 return true; // Never CSE anything that produces a flag.
548 switch (N->getOpcode()) {
550 case ISD::HANDLENODE:
552 return true; // Never CSE these nodes.
555 // Check that remaining values produced are not flags.
556 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
557 if (N->getValueType(i) == MVT::Glue)
558 return true; // Never CSE anything that produces a flag.
563 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
565 void SelectionDAG::RemoveDeadNodes() {
566 // Create a dummy node (which is not added to allnodes), that adds a reference
567 // to the root node, preventing it from being deleted.
568 HandleSDNode Dummy(getRoot());
570 SmallVector<SDNode*, 128> DeadNodes;
572 // Add all obviously-dead nodes to the DeadNodes worklist.
573 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
575 DeadNodes.push_back(I);
577 RemoveDeadNodes(DeadNodes);
579 // If the root changed (e.g. it was a dead load, update the root).
580 setRoot(Dummy.getValue());
583 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
584 /// given list, and any nodes that become unreachable as a result.
585 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
587 // Process the worklist, deleting the nodes and adding their uses to the
589 while (!DeadNodes.empty()) {
590 SDNode *N = DeadNodes.pop_back_val();
592 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
593 DUL->NodeDeleted(N, 0);
595 // Take the node out of the appropriate CSE map.
596 RemoveNodeFromCSEMaps(N);
598 // Next, brutally remove the operand list. This is safe to do, as there are
599 // no cycles in the graph.
600 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
602 SDNode *Operand = Use.getNode();
605 // Now that we removed this operand, see if there are no uses of it left.
606 if (Operand->use_empty())
607 DeadNodes.push_back(Operand);
614 void SelectionDAG::RemoveDeadNode(SDNode *N){
615 SmallVector<SDNode*, 16> DeadNodes(1, N);
617 // Create a dummy node that adds a reference to the root node, preventing
618 // it from being deleted. (This matters if the root is an operand of the
620 HandleSDNode Dummy(getRoot());
622 RemoveDeadNodes(DeadNodes);
625 void SelectionDAG::DeleteNode(SDNode *N) {
626 // First take this out of the appropriate CSE map.
627 RemoveNodeFromCSEMaps(N);
629 // Finally, remove uses due to operands of this node, remove from the
630 // AllNodes list, and delete the node.
631 DeleteNodeNotInCSEMaps(N);
634 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
635 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
636 assert(N->use_empty() && "Cannot delete a node that is not dead!");
638 // Drop all of the operands and decrement used node's use counts.
644 void SelectionDAG::DeallocateNode(SDNode *N) {
645 if (N->OperandsNeedDelete)
646 delete[] N->OperandList;
648 // Set the opcode to DELETED_NODE to help catch bugs when node
649 // memory is reallocated.
650 N->NodeType = ISD::DELETED_NODE;
652 NodeAllocator.Deallocate(AllNodes.remove(N));
654 // Remove the ordering of this node.
657 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
658 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
659 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
660 DbgVals[i]->setIsInvalidated();
663 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
664 /// correspond to it. This is useful when we're about to delete or repurpose
665 /// the node. We don't want future request for structurally identical nodes
666 /// to return N anymore.
667 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
669 switch (N->getOpcode()) {
670 case ISD::HANDLENODE: return false; // noop.
672 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
673 "Cond code doesn't exist!");
674 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
675 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
677 case ISD::ExternalSymbol:
678 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
680 case ISD::TargetExternalSymbol: {
681 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
682 Erased = TargetExternalSymbols.erase(
683 std::pair<std::string,unsigned char>(ESN->getSymbol(),
684 ESN->getTargetFlags()));
687 case ISD::VALUETYPE: {
688 EVT VT = cast<VTSDNode>(N)->getVT();
689 if (VT.isExtended()) {
690 Erased = ExtendedValueTypeNodes.erase(VT);
692 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
693 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
698 // Remove it from the CSE Map.
699 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
700 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
701 Erased = CSEMap.RemoveNode(N);
705 // Verify that the node was actually in one of the CSE maps, unless it has a
706 // flag result (which cannot be CSE'd) or is one of the special cases that are
707 // not subject to CSE.
708 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
709 !N->isMachineOpcode() && !doNotCSE(N)) {
712 llvm_unreachable("Node is not in map!");
718 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
719 /// maps and modified in place. Add it back to the CSE maps, unless an identical
720 /// node already exists, in which case transfer all its users to the existing
721 /// node. This transfer can potentially trigger recursive merging.
724 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
725 // For node types that aren't CSE'd, just act as if no identical node
728 SDNode *Existing = CSEMap.GetOrInsertNode(N);
730 // If there was already an existing matching node, use ReplaceAllUsesWith
731 // to replace the dead one with the existing one. This can cause
732 // recursive merging of other unrelated nodes down the line.
733 ReplaceAllUsesWith(N, Existing);
735 // N is now dead. Inform the listeners and delete it.
736 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
737 DUL->NodeDeleted(N, Existing);
738 DeleteNodeNotInCSEMaps(N);
743 // If the node doesn't already exist, we updated it. Inform listeners.
744 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
748 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
749 /// were replaced with those specified. If this node is never memoized,
750 /// return null, otherwise return a pointer to the slot it would take. If a
751 /// node already exists with these operands, the slot will be non-null.
752 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
757 SDValue Ops[] = { Op };
759 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
760 AddNodeIDCustom(ID, N);
761 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
765 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
766 /// were replaced with those specified. If this node is never memoized,
767 /// return null, otherwise return a pointer to the slot it would take. If a
768 /// node already exists with these operands, the slot will be non-null.
769 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
770 SDValue Op1, SDValue Op2,
775 SDValue Ops[] = { Op1, Op2 };
777 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
778 AddNodeIDCustom(ID, N);
779 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
784 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
785 /// were replaced with those specified. If this node is never memoized,
786 /// return null, otherwise return a pointer to the slot it would take. If a
787 /// node already exists with these operands, the slot will be non-null.
788 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
789 const SDValue *Ops,unsigned NumOps,
795 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
796 AddNodeIDCustom(ID, N);
797 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
802 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
803 static void VerifyNodeCommon(SDNode *N) {
804 switch (N->getOpcode()) {
807 case ISD::BUILD_PAIR: {
808 EVT VT = N->getValueType(0);
809 assert(N->getNumValues() == 1 && "Too many results!");
810 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
811 "Wrong return type!");
812 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
813 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
814 "Mismatched operand types!");
815 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
816 "Wrong operand type!");
817 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
818 "Wrong return type size");
821 case ISD::BUILD_VECTOR: {
822 assert(N->getNumValues() == 1 && "Too many results!");
823 assert(N->getValueType(0).isVector() && "Wrong return type!");
824 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
825 "Wrong number of operands!");
826 EVT EltVT = N->getValueType(0).getVectorElementType();
827 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
828 assert((I->getValueType() == EltVT ||
829 (EltVT.isInteger() && I->getValueType().isInteger() &&
830 EltVT.bitsLE(I->getValueType()))) &&
831 "Wrong operand type!");
832 assert(I->getValueType() == N->getOperand(0).getValueType() &&
833 "Operands must all have the same type");
840 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
841 static void VerifySDNode(SDNode *N) {
842 // The SDNode allocators cannot be used to allocate nodes with fields that are
843 // not present in an SDNode!
844 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
845 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
846 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
847 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
848 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
849 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
850 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
851 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
852 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
853 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
854 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
855 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
856 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
857 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
858 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
859 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
860 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
861 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
862 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
867 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
869 static void VerifyMachineNode(SDNode *N) {
870 // The MachineNode allocators cannot be used to allocate nodes with fields
871 // that are not present in a MachineNode!
872 // Currently there are no such nodes.
878 /// getEVTAlignment - Compute the default alignment value for the
881 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
882 Type *Ty = VT == MVT::iPTR ?
883 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
884 VT.getTypeForEVT(*getContext());
886 return TLI.getTargetData()->getABITypeAlignment(Ty);
889 // EntryNode could meaningfully have debug info if we can find it...
890 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
891 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
892 OptLevel(OL), EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
893 Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
894 AllNodes.push_back(&EntryNode);
895 Ordering = new SDNodeOrdering();
896 DbgInfo = new SDDbgInfo();
899 void SelectionDAG::init(MachineFunction &mf) {
901 Context = &mf.getFunction()->getContext();
904 SelectionDAG::~SelectionDAG() {
905 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
911 void SelectionDAG::allnodes_clear() {
912 assert(&*AllNodes.begin() == &EntryNode);
913 AllNodes.remove(AllNodes.begin());
914 while (!AllNodes.empty())
915 DeallocateNode(AllNodes.begin());
918 void SelectionDAG::clear() {
920 OperandAllocator.Reset();
923 ExtendedValueTypeNodes.clear();
924 ExternalSymbols.clear();
925 TargetExternalSymbols.clear();
926 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
927 static_cast<CondCodeSDNode*>(0));
928 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
929 static_cast<SDNode*>(0));
931 EntryNode.UseList = 0;
932 AllNodes.push_back(&EntryNode);
933 Root = getEntryNode();
938 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
939 return VT.bitsGT(Op.getValueType()) ?
940 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
941 getNode(ISD::TRUNCATE, DL, VT, Op);
944 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
945 return VT.bitsGT(Op.getValueType()) ?
946 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
947 getNode(ISD::TRUNCATE, DL, VT, Op);
950 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
951 return VT.bitsGT(Op.getValueType()) ?
952 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
953 getNode(ISD::TRUNCATE, DL, VT, Op);
956 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
957 assert(!VT.isVector() &&
958 "getZeroExtendInReg should use the vector element type instead of "
960 if (Op.getValueType() == VT) return Op;
961 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
962 APInt Imm = APInt::getLowBitsSet(BitWidth,
964 return getNode(ISD::AND, DL, Op.getValueType(), Op,
965 getConstant(Imm, Op.getValueType()));
968 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
970 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
971 EVT EltVT = VT.getScalarType();
973 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
974 return getNode(ISD::XOR, DL, VT, Val, NegOne);
977 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
978 EVT EltVT = VT.getScalarType();
979 assert((EltVT.getSizeInBits() >= 64 ||
980 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
981 "getConstant with a uint64_t value that doesn't fit in the type!");
982 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
985 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
986 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
989 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
990 assert(VT.isInteger() && "Cannot create FP integer constant!");
992 EVT EltVT = VT.getScalarType();
993 const ConstantInt *Elt = &Val;
995 // In some cases the vector type is legal but the element type is illegal and
996 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
997 // inserted value (the type does not need to match the vector element type).
998 // Any extra bits introduced will be truncated away.
999 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
1000 TargetLowering::TypePromoteInteger) {
1001 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
1002 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1003 Elt = ConstantInt::get(*getContext(), NewVal);
1006 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1007 "APInt size does not match type size!");
1008 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1009 FoldingSetNodeID ID;
1010 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1014 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1016 return SDValue(N, 0);
1019 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1020 CSEMap.InsertNode(N, IP);
1021 AllNodes.push_back(N);
1024 SDValue Result(N, 0);
1025 if (VT.isVector()) {
1026 SmallVector<SDValue, 8> Ops;
1027 Ops.assign(VT.getVectorNumElements(), Result);
1028 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1033 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1034 return getConstant(Val, TLI.getPointerTy(), isTarget);
1038 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1039 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1042 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1043 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1045 EVT EltVT = VT.getScalarType();
1047 // Do the map lookup using the actual bit pattern for the floating point
1048 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1049 // we don't have issues with SNANs.
1050 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1051 FoldingSetNodeID ID;
1052 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1056 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1058 return SDValue(N, 0);
1061 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1062 CSEMap.InsertNode(N, IP);
1063 AllNodes.push_back(N);
1066 SDValue Result(N, 0);
1067 if (VT.isVector()) {
1068 SmallVector<SDValue, 8> Ops;
1069 Ops.assign(VT.getVectorNumElements(), Result);
1070 // FIXME DebugLoc info might be appropriate here
1071 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1076 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1077 EVT EltVT = VT.getScalarType();
1078 if (EltVT==MVT::f32)
1079 return getConstantFP(APFloat((float)Val), VT, isTarget);
1080 else if (EltVT==MVT::f64)
1081 return getConstantFP(APFloat(Val), VT, isTarget);
1082 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::f16) {
1084 APFloat apf = APFloat(Val);
1085 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1087 return getConstantFP(apf, VT, isTarget);
1089 llvm_unreachable("Unsupported type in getConstantFP");
1092 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1093 EVT VT, int64_t Offset,
1095 unsigned char TargetFlags) {
1096 assert((TargetFlags == 0 || isTargetGA) &&
1097 "Cannot set target flags on target-independent globals");
1099 // Truncate (with sign-extension) the offset value to the pointer size.
1100 unsigned BitWidth = TLI.getPointerTy().getSizeInBits();
1102 Offset = SignExtend64(Offset, BitWidth);
1104 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1106 // If GV is an alias then use the aliasee for determining thread-localness.
1107 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1108 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1112 if (GVar && GVar->isThreadLocal())
1113 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1115 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1117 FoldingSetNodeID ID;
1118 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1120 ID.AddInteger(Offset);
1121 ID.AddInteger(TargetFlags);
1122 ID.AddInteger(GV->getType()->getAddressSpace());
1124 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1125 return SDValue(E, 0);
1127 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1128 Offset, TargetFlags);
1129 CSEMap.InsertNode(N, IP);
1130 AllNodes.push_back(N);
1131 return SDValue(N, 0);
1134 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1135 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1136 FoldingSetNodeID ID;
1137 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1140 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1141 return SDValue(E, 0);
1143 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1144 CSEMap.InsertNode(N, IP);
1145 AllNodes.push_back(N);
1146 return SDValue(N, 0);
1149 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1150 unsigned char TargetFlags) {
1151 assert((TargetFlags == 0 || isTarget) &&
1152 "Cannot set target flags on target-independent jump tables");
1153 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1154 FoldingSetNodeID ID;
1155 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1157 ID.AddInteger(TargetFlags);
1159 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1160 return SDValue(E, 0);
1162 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1164 CSEMap.InsertNode(N, IP);
1165 AllNodes.push_back(N);
1166 return SDValue(N, 0);
1169 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1170 unsigned Alignment, int Offset,
1172 unsigned char TargetFlags) {
1173 assert((TargetFlags == 0 || isTarget) &&
1174 "Cannot set target flags on target-independent globals");
1176 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1177 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1178 FoldingSetNodeID ID;
1179 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1180 ID.AddInteger(Alignment);
1181 ID.AddInteger(Offset);
1183 ID.AddInteger(TargetFlags);
1185 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1186 return SDValue(E, 0);
1188 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1189 Alignment, TargetFlags);
1190 CSEMap.InsertNode(N, IP);
1191 AllNodes.push_back(N);
1192 return SDValue(N, 0);
1196 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1197 unsigned Alignment, int Offset,
1199 unsigned char TargetFlags) {
1200 assert((TargetFlags == 0 || isTarget) &&
1201 "Cannot set target flags on target-independent globals");
1203 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1204 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1205 FoldingSetNodeID ID;
1206 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1207 ID.AddInteger(Alignment);
1208 ID.AddInteger(Offset);
1209 C->addSelectionDAGCSEId(ID);
1210 ID.AddInteger(TargetFlags);
1212 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1213 return SDValue(E, 0);
1215 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1216 Alignment, TargetFlags);
1217 CSEMap.InsertNode(N, IP);
1218 AllNodes.push_back(N);
1219 return SDValue(N, 0);
1222 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1223 unsigned char TargetFlags) {
1224 FoldingSetNodeID ID;
1225 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1226 ID.AddInteger(Index);
1227 ID.AddInteger(Offset);
1228 ID.AddInteger(TargetFlags);
1230 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1231 return SDValue(E, 0);
1233 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1235 CSEMap.InsertNode(N, IP);
1236 AllNodes.push_back(N);
1237 return SDValue(N, 0);
1240 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1241 FoldingSetNodeID ID;
1242 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1245 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1246 return SDValue(E, 0);
1248 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1249 CSEMap.InsertNode(N, IP);
1250 AllNodes.push_back(N);
1251 return SDValue(N, 0);
1254 SDValue SelectionDAG::getValueType(EVT VT) {
1255 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1256 ValueTypeNodes.size())
1257 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1259 SDNode *&N = VT.isExtended() ?
1260 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1262 if (N) return SDValue(N, 0);
1263 N = new (NodeAllocator) VTSDNode(VT);
1264 AllNodes.push_back(N);
1265 return SDValue(N, 0);
1268 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1269 SDNode *&N = ExternalSymbols[Sym];
1270 if (N) return SDValue(N, 0);
1271 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1272 AllNodes.push_back(N);
1273 return SDValue(N, 0);
1276 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1277 unsigned char TargetFlags) {
1279 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1281 if (N) return SDValue(N, 0);
1282 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1283 AllNodes.push_back(N);
1284 return SDValue(N, 0);
1287 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1288 if ((unsigned)Cond >= CondCodeNodes.size())
1289 CondCodeNodes.resize(Cond+1);
1291 if (CondCodeNodes[Cond] == 0) {
1292 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1293 CondCodeNodes[Cond] = N;
1294 AllNodes.push_back(N);
1297 return SDValue(CondCodeNodes[Cond], 0);
1300 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1301 // the shuffle mask M that point at N1 to point at N2, and indices that point
1302 // N2 to point at N1.
1303 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1305 int NElts = M.size();
1306 for (int i = 0; i != NElts; ++i) {
1314 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1315 SDValue N2, const int *Mask) {
1316 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1317 assert(VT.isVector() && N1.getValueType().isVector() &&
1318 "Vector Shuffle VTs must be a vectors");
1319 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1320 && "Vector Shuffle VTs must have same element type");
1322 // Canonicalize shuffle undef, undef -> undef
1323 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1324 return getUNDEF(VT);
1326 // Validate that all indices in Mask are within the range of the elements
1327 // input to the shuffle.
1328 unsigned NElts = VT.getVectorNumElements();
1329 SmallVector<int, 8> MaskVec;
1330 for (unsigned i = 0; i != NElts; ++i) {
1331 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1332 MaskVec.push_back(Mask[i]);
1335 // Canonicalize shuffle v, v -> v, undef
1338 for (unsigned i = 0; i != NElts; ++i)
1339 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1342 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1343 if (N1.getOpcode() == ISD::UNDEF)
1344 commuteShuffle(N1, N2, MaskVec);
1346 // Canonicalize all index into lhs, -> shuffle lhs, undef
1347 // Canonicalize all index into rhs, -> shuffle rhs, undef
1348 bool AllLHS = true, AllRHS = true;
1349 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1350 for (unsigned i = 0; i != NElts; ++i) {
1351 if (MaskVec[i] >= (int)NElts) {
1356 } else if (MaskVec[i] >= 0) {
1360 if (AllLHS && AllRHS)
1361 return getUNDEF(VT);
1362 if (AllLHS && !N2Undef)
1366 commuteShuffle(N1, N2, MaskVec);
1369 // If Identity shuffle, or all shuffle in to undef, return that node.
1370 bool AllUndef = true;
1371 bool Identity = true;
1372 for (unsigned i = 0; i != NElts; ++i) {
1373 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1374 if (MaskVec[i] >= 0) AllUndef = false;
1376 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1379 return getUNDEF(VT);
1381 FoldingSetNodeID ID;
1382 SDValue Ops[2] = { N1, N2 };
1383 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1384 for (unsigned i = 0; i != NElts; ++i)
1385 ID.AddInteger(MaskVec[i]);
1388 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1389 return SDValue(E, 0);
1391 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1392 // SDNode doesn't have access to it. This memory will be "leaked" when
1393 // the node is deallocated, but recovered when the NodeAllocator is released.
1394 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1395 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1397 ShuffleVectorSDNode *N =
1398 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1399 CSEMap.InsertNode(N, IP);
1400 AllNodes.push_back(N);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1405 SDValue Val, SDValue DTy,
1406 SDValue STy, SDValue Rnd, SDValue Sat,
1407 ISD::CvtCode Code) {
1408 // If the src and dest types are the same and the conversion is between
1409 // integer types of the same sign or two floats, no conversion is necessary.
1411 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1414 FoldingSetNodeID ID;
1415 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1416 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1418 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1419 return SDValue(E, 0);
1421 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1423 CSEMap.InsertNode(N, IP);
1424 AllNodes.push_back(N);
1425 return SDValue(N, 0);
1428 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1429 FoldingSetNodeID ID;
1430 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1431 ID.AddInteger(RegNo);
1433 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1434 return SDValue(E, 0);
1436 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1437 CSEMap.InsertNode(N, IP);
1438 AllNodes.push_back(N);
1439 return SDValue(N, 0);
1442 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1443 FoldingSetNodeID ID;
1444 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1445 ID.AddPointer(RegMask);
1447 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1448 return SDValue(E, 0);
1450 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1451 CSEMap.InsertNode(N, IP);
1452 AllNodes.push_back(N);
1453 return SDValue(N, 0);
1456 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1457 FoldingSetNodeID ID;
1458 SDValue Ops[] = { Root };
1459 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1460 ID.AddPointer(Label);
1462 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1463 return SDValue(E, 0);
1465 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1466 CSEMap.InsertNode(N, IP);
1467 AllNodes.push_back(N);
1468 return SDValue(N, 0);
1472 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1474 unsigned char TargetFlags) {
1475 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1477 FoldingSetNodeID ID;
1478 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1480 ID.AddInteger(TargetFlags);
1482 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1483 return SDValue(E, 0);
1485 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, TargetFlags);
1486 CSEMap.InsertNode(N, IP);
1487 AllNodes.push_back(N);
1488 return SDValue(N, 0);
1491 SDValue SelectionDAG::getSrcValue(const Value *V) {
1492 assert((!V || V->getType()->isPointerTy()) &&
1493 "SrcValue is not a pointer?");
1495 FoldingSetNodeID ID;
1496 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1500 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1501 return SDValue(E, 0);
1503 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1504 CSEMap.InsertNode(N, IP);
1505 AllNodes.push_back(N);
1506 return SDValue(N, 0);
1509 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1510 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1511 FoldingSetNodeID ID;
1512 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1516 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1517 return SDValue(E, 0);
1519 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1520 CSEMap.InsertNode(N, IP);
1521 AllNodes.push_back(N);
1522 return SDValue(N, 0);
1526 /// getShiftAmountOperand - Return the specified value casted to
1527 /// the target's desired shift amount type.
1528 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1529 EVT OpTy = Op.getValueType();
1530 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1531 if (OpTy == ShTy || OpTy.isVector()) return Op;
1533 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1534 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1537 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1538 /// specified value type.
1539 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1540 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1541 unsigned ByteSize = VT.getStoreSize();
1542 Type *Ty = VT.getTypeForEVT(*getContext());
1543 unsigned StackAlign =
1544 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1546 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1547 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1550 /// CreateStackTemporary - Create a stack temporary suitable for holding
1551 /// either of the specified value types.
1552 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1553 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1554 VT2.getStoreSizeInBits())/8;
1555 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1556 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1557 const TargetData *TD = TLI.getTargetData();
1558 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1559 TD->getPrefTypeAlignment(Ty2));
1561 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1562 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1563 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1566 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1567 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1568 // These setcc operations always fold.
1572 case ISD::SETFALSE2: return getConstant(0, VT);
1574 case ISD::SETTRUE2: return getConstant(1, VT);
1586 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1590 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1591 const APInt &C2 = N2C->getAPIntValue();
1592 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1593 const APInt &C1 = N1C->getAPIntValue();
1596 default: llvm_unreachable("Unknown integer setcc!");
1597 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1598 case ISD::SETNE: return getConstant(C1 != C2, VT);
1599 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1600 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1601 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1602 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1603 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1604 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1605 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1606 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1610 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1611 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1612 // No compile time operations on this type yet.
1613 if (N1C->getValueType(0) == MVT::ppcf128)
1616 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1619 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1620 return getUNDEF(VT);
1622 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1623 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1624 return getUNDEF(VT);
1626 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1627 R==APFloat::cmpLessThan, VT);
1628 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1629 return getUNDEF(VT);
1631 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1632 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1633 return getUNDEF(VT);
1635 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1636 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1637 return getUNDEF(VT);
1639 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1640 R==APFloat::cmpEqual, VT);
1641 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1642 return getUNDEF(VT);
1644 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1645 R==APFloat::cmpEqual, VT);
1646 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1647 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1648 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1649 R==APFloat::cmpEqual, VT);
1650 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1651 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1652 R==APFloat::cmpLessThan, VT);
1653 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1654 R==APFloat::cmpUnordered, VT);
1655 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1656 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1659 // Ensure that the constant occurs on the RHS.
1660 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1664 // Could not fold it.
1668 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1669 /// use this predicate to simplify operations downstream.
1670 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1671 // This predicate is not safe for vector operations.
1672 if (Op.getValueType().isVector())
1675 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1676 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1679 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1680 /// this predicate to simplify operations downstream. Mask is known to be zero
1681 /// for bits that V cannot have.
1682 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1683 unsigned Depth) const {
1684 APInt KnownZero, KnownOne;
1685 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1686 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1687 return (KnownZero & Mask) == Mask;
1690 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1691 /// known to be either zero or one and return them in the KnownZero/KnownOne
1692 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1694 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1695 APInt &KnownOne, unsigned Depth) const {
1696 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1698 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1700 return; // Limit search depth.
1702 APInt KnownZero2, KnownOne2;
1704 switch (Op.getOpcode()) {
1706 // We know all of the bits for a constant!
1707 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1708 KnownZero = ~KnownOne;
1711 // If either the LHS or the RHS are Zero, the result is zero.
1712 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1713 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1714 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1715 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1717 // Output known-1 bits are only known if set in both the LHS & RHS.
1718 KnownOne &= KnownOne2;
1719 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1720 KnownZero |= KnownZero2;
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 // Output known-0 bits are only known if clear in both the LHS & RHS.
1729 KnownZero &= KnownZero2;
1730 // Output known-1 are known to be set if set in either the LHS | RHS.
1731 KnownOne |= KnownOne2;
1734 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1735 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1736 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1737 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1739 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1740 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1741 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1742 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1743 KnownZero = KnownZeroOut;
1747 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1748 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1749 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1750 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1752 // If low bits are zero in either operand, output low known-0 bits.
1753 // Also compute a conserative estimate for high known-0 bits.
1754 // More trickiness is possible, but this is sufficient for the
1755 // interesting case of alignment computation.
1756 KnownOne.clearAllBits();
1757 unsigned TrailZ = KnownZero.countTrailingOnes() +
1758 KnownZero2.countTrailingOnes();
1759 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1760 KnownZero2.countLeadingOnes(),
1761 BitWidth) - BitWidth;
1763 TrailZ = std::min(TrailZ, BitWidth);
1764 LeadZ = std::min(LeadZ, BitWidth);
1765 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1766 APInt::getHighBitsSet(BitWidth, LeadZ);
1770 // For the purposes of computing leading zeros we can conservatively
1771 // treat a udiv as a logical right shift by the power of 2 known to
1772 // be less than the denominator.
1773 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1774 unsigned LeadZ = KnownZero2.countLeadingOnes();
1776 KnownOne2.clearAllBits();
1777 KnownZero2.clearAllBits();
1778 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1779 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1780 if (RHSUnknownLeadingOnes != BitWidth)
1781 LeadZ = std::min(BitWidth,
1782 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1784 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1788 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1789 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1790 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1791 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1793 // Only known if known in both the LHS and RHS.
1794 KnownOne &= KnownOne2;
1795 KnownZero &= KnownZero2;
1797 case ISD::SELECT_CC:
1798 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1799 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1800 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1801 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1803 // Only known if known in both the LHS and RHS.
1804 KnownOne &= KnownOne2;
1805 KnownZero &= KnownZero2;
1813 if (Op.getResNo() != 1)
1815 // The boolean result conforms to getBooleanContents. Fall through.
1817 // If we know the result of a setcc has the top bits zero, use this info.
1818 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1819 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1820 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1823 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1824 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1825 unsigned ShAmt = SA->getZExtValue();
1827 // If the shift count is an invalid immediate, don't do anything.
1828 if (ShAmt >= BitWidth)
1831 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1832 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1833 KnownZero <<= ShAmt;
1835 // low bits known zero.
1836 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1840 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1841 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1842 unsigned ShAmt = SA->getZExtValue();
1844 // If the shift count is an invalid immediate, don't do anything.
1845 if (ShAmt >= BitWidth)
1848 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1849 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1850 KnownZero = KnownZero.lshr(ShAmt);
1851 KnownOne = KnownOne.lshr(ShAmt);
1853 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1854 KnownZero |= HighBits; // High bits known zero.
1858 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1859 unsigned ShAmt = SA->getZExtValue();
1861 // If the shift count is an invalid immediate, don't do anything.
1862 if (ShAmt >= BitWidth)
1865 // If any of the demanded bits are produced by the sign extension, we also
1866 // demand the input sign bit.
1867 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1869 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1870 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1871 KnownZero = KnownZero.lshr(ShAmt);
1872 KnownOne = KnownOne.lshr(ShAmt);
1874 // Handle the sign bits.
1875 APInt SignBit = APInt::getSignBit(BitWidth);
1876 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1878 if (KnownZero.intersects(SignBit)) {
1879 KnownZero |= HighBits; // New bits are known zero.
1880 } else if (KnownOne.intersects(SignBit)) {
1881 KnownOne |= HighBits; // New bits are known one.
1885 case ISD::SIGN_EXTEND_INREG: {
1886 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1887 unsigned EBits = EVT.getScalarType().getSizeInBits();
1889 // Sign extension. Compute the demanded bits in the result that are not
1890 // present in the input.
1891 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1893 APInt InSignBit = APInt::getSignBit(EBits);
1894 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1896 // If the sign extended bits are demanded, we know that the sign
1898 InSignBit = InSignBit.zext(BitWidth);
1899 if (NewBits.getBoolValue())
1900 InputDemandedBits |= InSignBit;
1902 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1903 KnownOne &= InputDemandedBits;
1904 KnownZero &= InputDemandedBits;
1905 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1907 // If the sign bit of the input is known set or clear, then we know the
1908 // top bits of the result.
1909 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1910 KnownZero |= NewBits;
1911 KnownOne &= ~NewBits;
1912 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1913 KnownOne |= NewBits;
1914 KnownZero &= ~NewBits;
1915 } else { // Input sign bit unknown
1916 KnownZero &= ~NewBits;
1917 KnownOne &= ~NewBits;
1922 case ISD::CTTZ_ZERO_UNDEF:
1924 case ISD::CTLZ_ZERO_UNDEF:
1926 unsigned LowBits = Log2_32(BitWidth)+1;
1927 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1928 KnownOne.clearAllBits();
1932 LoadSDNode *LD = cast<LoadSDNode>(Op);
1933 if (ISD::isZEXTLoad(Op.getNode())) {
1934 EVT VT = LD->getMemoryVT();
1935 unsigned MemBits = VT.getScalarType().getSizeInBits();
1936 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
1937 } else if (const MDNode *Ranges = LD->getRanges()) {
1938 computeMaskedBitsLoad(*Ranges, KnownZero);
1942 case ISD::ZERO_EXTEND: {
1943 EVT InVT = Op.getOperand(0).getValueType();
1944 unsigned InBits = InVT.getScalarType().getSizeInBits();
1945 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1946 KnownZero = KnownZero.trunc(InBits);
1947 KnownOne = KnownOne.trunc(InBits);
1948 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1949 KnownZero = KnownZero.zext(BitWidth);
1950 KnownOne = KnownOne.zext(BitWidth);
1951 KnownZero |= NewBits;
1954 case ISD::SIGN_EXTEND: {
1955 EVT InVT = Op.getOperand(0).getValueType();
1956 unsigned InBits = InVT.getScalarType().getSizeInBits();
1957 APInt InSignBit = APInt::getSignBit(InBits);
1958 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
1960 KnownZero = KnownZero.trunc(InBits);
1961 KnownOne = KnownOne.trunc(InBits);
1962 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1964 // Note if the sign bit is known to be zero or one.
1965 bool SignBitKnownZero = KnownZero.isNegative();
1966 bool SignBitKnownOne = KnownOne.isNegative();
1967 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1968 "Sign bit can't be known to be both zero and one!");
1970 KnownZero = KnownZero.zext(BitWidth);
1971 KnownOne = KnownOne.zext(BitWidth);
1973 // If the sign bit is known zero or one, the top bits match.
1974 if (SignBitKnownZero)
1975 KnownZero |= NewBits;
1976 else if (SignBitKnownOne)
1977 KnownOne |= NewBits;
1980 case ISD::ANY_EXTEND: {
1981 EVT InVT = Op.getOperand(0).getValueType();
1982 unsigned InBits = InVT.getScalarType().getSizeInBits();
1983 KnownZero = KnownZero.trunc(InBits);
1984 KnownOne = KnownOne.trunc(InBits);
1985 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1986 KnownZero = KnownZero.zext(BitWidth);
1987 KnownOne = KnownOne.zext(BitWidth);
1990 case ISD::TRUNCATE: {
1991 EVT InVT = Op.getOperand(0).getValueType();
1992 unsigned InBits = InVT.getScalarType().getSizeInBits();
1993 KnownZero = KnownZero.zext(InBits);
1994 KnownOne = KnownOne.zext(InBits);
1995 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1996 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1997 KnownZero = KnownZero.trunc(BitWidth);
1998 KnownOne = KnownOne.trunc(BitWidth);
2001 case ISD::AssertZext: {
2002 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2003 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2004 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2005 KnownZero |= (~InMask);
2006 KnownOne &= (~KnownZero);
2010 // All bits are zero except the low bit.
2011 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2015 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2016 // We know that the top bits of C-X are clear if X contains less bits
2017 // than C (i.e. no wrap-around can happen). For example, 20-X is
2018 // positive if we can prove that X is >= 0 and < 16.
2019 if (CLHS->getAPIntValue().isNonNegative()) {
2020 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2021 // NLZ can't be BitWidth with no sign bit
2022 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2023 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2025 // If all of the MaskV bits are known to be zero, then we know the
2026 // output top bits are zero, because we now know that the output is
2028 if ((KnownZero2 & MaskV) == MaskV) {
2029 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2030 // Top bits known zero.
2031 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2039 // Output known-0 bits are known if clear or set in both the low clear bits
2040 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2041 // low 3 bits clear.
2042 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2043 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2044 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2046 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2047 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2048 KnownZeroOut = std::min(KnownZeroOut,
2049 KnownZero2.countTrailingOnes());
2051 if (Op.getOpcode() == ISD::ADD) {
2052 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2056 // With ADDE, a carry bit may be added in, so we can only use this
2057 // information if we know (at least) that the low two bits are clear. We
2058 // then return to the caller that the low bit is unknown but that other bits
2060 if (KnownZeroOut >= 2) // ADDE
2061 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2065 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2066 const APInt &RA = Rem->getAPIntValue().abs();
2067 if (RA.isPowerOf2()) {
2068 APInt LowBits = RA - 1;
2069 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2070 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2072 // The low bits of the first operand are unchanged by the srem.
2073 KnownZero = KnownZero2 & LowBits;
2074 KnownOne = KnownOne2 & LowBits;
2076 // If the first operand is non-negative or has all low bits zero, then
2077 // the upper bits are all zero.
2078 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2079 KnownZero |= ~LowBits;
2081 // If the first operand is negative and not all low bits are zero, then
2082 // the upper bits are all one.
2083 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2084 KnownOne |= ~LowBits;
2085 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2090 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2091 const APInt &RA = Rem->getAPIntValue();
2092 if (RA.isPowerOf2()) {
2093 APInt LowBits = (RA - 1);
2094 KnownZero |= ~LowBits;
2095 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2096 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2101 // Since the result is less than or equal to either operand, any leading
2102 // zero bits in either operand must also exist in the result.
2103 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2104 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2106 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2107 KnownZero2.countLeadingOnes());
2108 KnownOne.clearAllBits();
2109 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2112 case ISD::FrameIndex:
2113 case ISD::TargetFrameIndex:
2114 if (unsigned Align = InferPtrAlignment(Op)) {
2115 // The low bits are known zero if the pointer is aligned.
2116 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2122 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2125 case ISD::INTRINSIC_WO_CHAIN:
2126 case ISD::INTRINSIC_W_CHAIN:
2127 case ISD::INTRINSIC_VOID:
2128 // Allow the target to implement this method for its nodes.
2129 TLI.computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2134 /// ComputeNumSignBits - Return the number of times the sign bit of the
2135 /// register is replicated into the other bits. We know that at least 1 bit
2136 /// is always equal to the sign bit (itself), but other cases can give us
2137 /// information. For example, immediately after an "SRA X, 2", we know that
2138 /// the top 3 bits are all equal to each other, so we return 3.
2139 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2140 EVT VT = Op.getValueType();
2141 assert(VT.isInteger() && "Invalid VT!");
2142 unsigned VTBits = VT.getScalarType().getSizeInBits();
2144 unsigned FirstAnswer = 1;
2147 return 1; // Limit search depth.
2149 switch (Op.getOpcode()) {
2151 case ISD::AssertSext:
2152 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2153 return VTBits-Tmp+1;
2154 case ISD::AssertZext:
2155 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2158 case ISD::Constant: {
2159 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2160 return Val.getNumSignBits();
2163 case ISD::SIGN_EXTEND:
2164 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2165 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2167 case ISD::SIGN_EXTEND_INREG:
2168 // Max of the input and what this extends.
2170 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2173 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2174 return std::max(Tmp, Tmp2);
2177 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2178 // SRA X, C -> adds C sign bits.
2179 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2180 Tmp += C->getZExtValue();
2181 if (Tmp > VTBits) Tmp = VTBits;
2185 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2186 // shl destroys sign bits.
2187 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2188 if (C->getZExtValue() >= VTBits || // Bad shift.
2189 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2190 return Tmp - C->getZExtValue();
2195 case ISD::XOR: // NOT is handled here.
2196 // Logical binary ops preserve the number of sign bits at the worst.
2197 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2199 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2200 FirstAnswer = std::min(Tmp, Tmp2);
2201 // We computed what we know about the sign bits as our first
2202 // answer. Now proceed to the generic code that uses
2203 // ComputeMaskedBits, and pick whichever answer is better.
2208 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2209 if (Tmp == 1) return 1; // Early out.
2210 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2211 return std::min(Tmp, Tmp2);
2219 if (Op.getResNo() != 1)
2221 // The boolean result conforms to getBooleanContents. Fall through.
2223 // If setcc returns 0/-1, all bits are sign bits.
2224 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2225 TargetLowering::ZeroOrNegativeOneBooleanContent)
2230 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2231 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2233 // Handle rotate right by N like a rotate left by 32-N.
2234 if (Op.getOpcode() == ISD::ROTR)
2235 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2237 // If we aren't rotating out all of the known-in sign bits, return the
2238 // number that are left. This handles rotl(sext(x), 1) for example.
2239 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2240 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2244 // Add can have at most one carry bit. Thus we know that the output
2245 // is, at worst, one more bit than the inputs.
2246 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2247 if (Tmp == 1) return 1; // Early out.
2249 // Special case decrementing a value (ADD X, -1):
2250 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2251 if (CRHS->isAllOnesValue()) {
2252 APInt KnownZero, KnownOne;
2253 ComputeMaskedBits(Op.getOperand(0), 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 we are subtracting one from a positive number, there is no carry
2261 // out of the result.
2262 if (KnownZero.isNegative())
2266 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2267 if (Tmp2 == 1) return 1;
2268 return std::min(Tmp, Tmp2)-1;
2271 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2272 if (Tmp2 == 1) return 1;
2275 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2276 if (CLHS->isNullValue()) {
2277 APInt KnownZero, KnownOne;
2278 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2279 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2281 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2284 // If the input is known to be positive (the sign bit is known clear),
2285 // the output of the NEG has the same number of sign bits as the input.
2286 if (KnownZero.isNegative())
2289 // Otherwise, we treat this like a SUB.
2292 // Sub can have at most one carry bit. Thus we know that the output
2293 // is, at worst, one more bit than the inputs.
2294 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2295 if (Tmp == 1) return 1; // Early out.
2296 return std::min(Tmp, Tmp2)-1;
2298 // FIXME: it's tricky to do anything useful for this, but it is an important
2299 // case for targets like X86.
2303 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2304 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2305 unsigned ExtType = LD->getExtensionType();
2308 case ISD::SEXTLOAD: // '17' bits known
2309 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2310 return VTBits-Tmp+1;
2311 case ISD::ZEXTLOAD: // '16' bits known
2312 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2317 // Allow the target to implement this method for its nodes.
2318 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2319 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2320 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2321 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2322 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2323 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2326 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2327 // use this information.
2328 APInt KnownZero, KnownOne;
2329 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2332 if (KnownZero.isNegative()) { // sign bit is 0
2334 } else if (KnownOne.isNegative()) { // sign bit is 1;
2341 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2342 // the number of identical bits in the top of the input value.
2344 Mask <<= Mask.getBitWidth()-VTBits;
2345 // Return # leading zeros. We use 'min' here in case Val was zero before
2346 // shifting. We don't want to return '64' as for an i32 "0".
2347 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2350 /// isBaseWithConstantOffset - Return true if the specified operand is an
2351 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2352 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2353 /// semantics as an ADD. This handles the equivalence:
2354 /// X|Cst == X+Cst iff X&Cst = 0.
2355 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2356 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2357 !isa<ConstantSDNode>(Op.getOperand(1)))
2360 if (Op.getOpcode() == ISD::OR &&
2361 !MaskedValueIsZero(Op.getOperand(0),
2362 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2369 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2370 // If we're told that NaNs won't happen, assume they won't.
2371 if (getTarget().Options.NoNaNsFPMath)
2374 // If the value is a constant, we can obviously see if it is a NaN or not.
2375 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2376 return !C->getValueAPF().isNaN();
2378 // TODO: Recognize more cases here.
2383 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2384 // If the value is a constant, we can obviously see if it is a zero or not.
2385 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2386 return !C->isZero();
2388 // TODO: Recognize more cases here.
2389 switch (Op.getOpcode()) {
2392 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2393 return !C->isNullValue();
2400 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2401 // Check the obvious case.
2402 if (A == B) return true;
2404 // For for negative and positive zero.
2405 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2406 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2407 if (CA->isZero() && CB->isZero()) return true;
2409 // Otherwise they may not be equal.
2413 /// getNode - Gets or creates the specified node.
2415 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2416 FoldingSetNodeID ID;
2417 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2419 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2420 return SDValue(E, 0);
2422 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2423 CSEMap.InsertNode(N, IP);
2425 AllNodes.push_back(N);
2429 return SDValue(N, 0);
2432 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2433 EVT VT, SDValue Operand) {
2434 // Constant fold unary operations with an integer constant operand.
2435 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2436 const APInt &Val = C->getAPIntValue();
2439 case ISD::SIGN_EXTEND:
2440 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2441 case ISD::ANY_EXTEND:
2442 case ISD::ZERO_EXTEND:
2444 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2445 case ISD::UINT_TO_FP:
2446 case ISD::SINT_TO_FP: {
2447 // No compile time operations on ppcf128.
2448 if (VT == MVT::ppcf128) break;
2449 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2450 (void)apf.convertFromAPInt(Val,
2451 Opcode==ISD::SINT_TO_FP,
2452 APFloat::rmNearestTiesToEven);
2453 return getConstantFP(apf, VT);
2456 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2457 return getConstantFP(APFloat(Val), VT);
2458 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2459 return getConstantFP(APFloat(Val), VT);
2462 return getConstant(Val.byteSwap(), VT);
2464 return getConstant(Val.countPopulation(), VT);
2466 case ISD::CTLZ_ZERO_UNDEF:
2467 return getConstant(Val.countLeadingZeros(), VT);
2469 case ISD::CTTZ_ZERO_UNDEF:
2470 return getConstant(Val.countTrailingZeros(), VT);
2474 // Constant fold unary operations with a floating point constant operand.
2475 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2476 APFloat V = C->getValueAPF(); // make copy
2477 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2481 return getConstantFP(V, VT);
2484 return getConstantFP(V, VT);
2486 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2487 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2488 return getConstantFP(V, VT);
2492 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2493 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2494 return getConstantFP(V, VT);
2498 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2499 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2500 return getConstantFP(V, VT);
2503 case ISD::FP_EXTEND: {
2505 // This can return overflow, underflow, or inexact; we don't care.
2506 // FIXME need to be more flexible about rounding mode.
2507 (void)V.convert(*EVTToAPFloatSemantics(VT),
2508 APFloat::rmNearestTiesToEven, &ignored);
2509 return getConstantFP(V, VT);
2511 case ISD::FP_TO_SINT:
2512 case ISD::FP_TO_UINT: {
2515 assert(integerPartWidth >= 64);
2516 // FIXME need to be more flexible about rounding mode.
2517 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2518 Opcode==ISD::FP_TO_SINT,
2519 APFloat::rmTowardZero, &ignored);
2520 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2522 APInt api(VT.getSizeInBits(), x);
2523 return getConstant(api, VT);
2526 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2527 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2528 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2529 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2535 unsigned OpOpcode = Operand.getNode()->getOpcode();
2537 case ISD::TokenFactor:
2538 case ISD::MERGE_VALUES:
2539 case ISD::CONCAT_VECTORS:
2540 return Operand; // Factor, merge or concat of one node? No need.
2541 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2542 case ISD::FP_EXTEND:
2543 assert(VT.isFloatingPoint() &&
2544 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2545 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2546 assert((!VT.isVector() ||
2547 VT.getVectorNumElements() ==
2548 Operand.getValueType().getVectorNumElements()) &&
2549 "Vector element count mismatch!");
2550 if (Operand.getOpcode() == ISD::UNDEF)
2551 return getUNDEF(VT);
2553 case ISD::SIGN_EXTEND:
2554 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2555 "Invalid SIGN_EXTEND!");
2556 if (Operand.getValueType() == VT) return Operand; // noop extension
2557 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2558 "Invalid sext node, dst < src!");
2559 assert((!VT.isVector() ||
2560 VT.getVectorNumElements() ==
2561 Operand.getValueType().getVectorNumElements()) &&
2562 "Vector element count mismatch!");
2563 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2564 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2565 else if (OpOpcode == ISD::UNDEF)
2566 // sext(undef) = 0, because the top bits will all be the same.
2567 return getConstant(0, VT);
2569 case ISD::ZERO_EXTEND:
2570 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2571 "Invalid ZERO_EXTEND!");
2572 if (Operand.getValueType() == VT) return Operand; // noop extension
2573 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2574 "Invalid zext node, dst < src!");
2575 assert((!VT.isVector() ||
2576 VT.getVectorNumElements() ==
2577 Operand.getValueType().getVectorNumElements()) &&
2578 "Vector element count mismatch!");
2579 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2580 return getNode(ISD::ZERO_EXTEND, DL, VT,
2581 Operand.getNode()->getOperand(0));
2582 else if (OpOpcode == ISD::UNDEF)
2583 // zext(undef) = 0, because the top bits will be zero.
2584 return getConstant(0, VT);
2586 case ISD::ANY_EXTEND:
2587 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2588 "Invalid ANY_EXTEND!");
2589 if (Operand.getValueType() == VT) return Operand; // noop extension
2590 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2591 "Invalid anyext node, dst < src!");
2592 assert((!VT.isVector() ||
2593 VT.getVectorNumElements() ==
2594 Operand.getValueType().getVectorNumElements()) &&
2595 "Vector element count mismatch!");
2597 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2598 OpOpcode == ISD::ANY_EXTEND)
2599 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2600 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2601 else if (OpOpcode == ISD::UNDEF)
2602 return getUNDEF(VT);
2604 // (ext (trunx x)) -> x
2605 if (OpOpcode == ISD::TRUNCATE) {
2606 SDValue OpOp = Operand.getNode()->getOperand(0);
2607 if (OpOp.getValueType() == VT)
2612 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2613 "Invalid TRUNCATE!");
2614 if (Operand.getValueType() == VT) return Operand; // noop truncate
2615 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2616 "Invalid truncate node, src < dst!");
2617 assert((!VT.isVector() ||
2618 VT.getVectorNumElements() ==
2619 Operand.getValueType().getVectorNumElements()) &&
2620 "Vector element count mismatch!");
2621 if (OpOpcode == ISD::TRUNCATE)
2622 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2623 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2624 OpOpcode == ISD::ANY_EXTEND) {
2625 // If the source is smaller than the dest, we still need an extend.
2626 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2627 .bitsLT(VT.getScalarType()))
2628 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2629 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2630 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2631 return Operand.getNode()->getOperand(0);
2633 if (OpOpcode == ISD::UNDEF)
2634 return getUNDEF(VT);
2637 // Basic sanity checking.
2638 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2639 && "Cannot BITCAST between types of different sizes!");
2640 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2641 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2642 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2643 if (OpOpcode == ISD::UNDEF)
2644 return getUNDEF(VT);
2646 case ISD::SCALAR_TO_VECTOR:
2647 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2648 (VT.getVectorElementType() == Operand.getValueType() ||
2649 (VT.getVectorElementType().isInteger() &&
2650 Operand.getValueType().isInteger() &&
2651 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2652 "Illegal SCALAR_TO_VECTOR node!");
2653 if (OpOpcode == ISD::UNDEF)
2654 return getUNDEF(VT);
2655 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2656 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2657 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2658 Operand.getConstantOperandVal(1) == 0 &&
2659 Operand.getOperand(0).getValueType() == VT)
2660 return Operand.getOperand(0);
2663 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2664 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2665 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2666 Operand.getNode()->getOperand(0));
2667 if (OpOpcode == ISD::FNEG) // --X -> X
2668 return Operand.getNode()->getOperand(0);
2671 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2672 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2677 SDVTList VTs = getVTList(VT);
2678 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2679 FoldingSetNodeID ID;
2680 SDValue Ops[1] = { Operand };
2681 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2683 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2684 return SDValue(E, 0);
2686 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2687 CSEMap.InsertNode(N, IP);
2689 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2692 AllNodes.push_back(N);
2696 return SDValue(N, 0);
2699 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2701 ConstantSDNode *Cst1,
2702 ConstantSDNode *Cst2) {
2703 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2706 case ISD::ADD: return getConstant(C1 + C2, VT);
2707 case ISD::SUB: return getConstant(C1 - C2, VT);
2708 case ISD::MUL: return getConstant(C1 * C2, VT);
2710 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2713 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2716 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2719 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2721 case ISD::AND: return getConstant(C1 & C2, VT);
2722 case ISD::OR: return getConstant(C1 | C2, VT);
2723 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2724 case ISD::SHL: return getConstant(C1 << C2, VT);
2725 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2726 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2727 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2728 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2735 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2736 SDValue N1, SDValue N2) {
2737 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2738 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2741 case ISD::TokenFactor:
2742 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2743 N2.getValueType() == MVT::Other && "Invalid token factor!");
2744 // Fold trivial token factors.
2745 if (N1.getOpcode() == ISD::EntryToken) return N2;
2746 if (N2.getOpcode() == ISD::EntryToken) return N1;
2747 if (N1 == N2) return N1;
2749 case ISD::CONCAT_VECTORS:
2750 // Concat of UNDEFs is UNDEF.
2751 if (N1.getOpcode() == ISD::UNDEF &&
2752 N2.getOpcode() == ISD::UNDEF)
2753 return getUNDEF(VT);
2755 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2756 // one big BUILD_VECTOR.
2757 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2758 N2.getOpcode() == ISD::BUILD_VECTOR) {
2759 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2760 N1.getNode()->op_end());
2761 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2762 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2766 assert(VT.isInteger() && "This operator does not apply to FP types!");
2767 assert(N1.getValueType() == N2.getValueType() &&
2768 N1.getValueType() == VT && "Binary operator types must match!");
2769 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2770 // worth handling here.
2771 if (N2C && N2C->isNullValue())
2773 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2780 assert(VT.isInteger() && "This operator does not apply to FP types!");
2781 assert(N1.getValueType() == N2.getValueType() &&
2782 N1.getValueType() == VT && "Binary operator types must match!");
2783 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2784 // it's worth handling here.
2785 if (N2C && N2C->isNullValue())
2795 assert(VT.isInteger() && "This operator does not apply to FP types!");
2796 assert(N1.getValueType() == N2.getValueType() &&
2797 N1.getValueType() == VT && "Binary operator types must match!");
2804 if (getTarget().Options.UnsafeFPMath) {
2805 if (Opcode == ISD::FADD) {
2807 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2808 if (CFP->getValueAPF().isZero())
2811 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2812 if (CFP->getValueAPF().isZero())
2814 } else if (Opcode == ISD::FSUB) {
2816 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2817 if (CFP->getValueAPF().isZero())
2819 } else if (Opcode == ISD::FMUL) {
2820 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2823 // If the first operand isn't the constant, try the second
2825 CFP = dyn_cast<ConstantFPSDNode>(N2);
2832 return SDValue(CFP,0);
2834 if (CFP->isExactlyValue(1.0))
2839 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2840 assert(N1.getValueType() == N2.getValueType() &&
2841 N1.getValueType() == VT && "Binary operator types must match!");
2843 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2844 assert(N1.getValueType() == VT &&
2845 N1.getValueType().isFloatingPoint() &&
2846 N2.getValueType().isFloatingPoint() &&
2847 "Invalid FCOPYSIGN!");
2854 assert(VT == N1.getValueType() &&
2855 "Shift operators return type must be the same as their first arg");
2856 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2857 "Shifts only work on integers");
2858 // Verify that the shift amount VT is bit enough to hold valid shift
2859 // amounts. This catches things like trying to shift an i1024 value by an
2860 // i8, which is easy to fall into in generic code that uses
2861 // TLI.getShiftAmount().
2862 assert(N2.getValueType().getSizeInBits() >=
2863 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2864 "Invalid use of small shift amount with oversized value!");
2866 // Always fold shifts of i1 values so the code generator doesn't need to
2867 // handle them. Since we know the size of the shift has to be less than the
2868 // size of the value, the shift/rotate count is guaranteed to be zero.
2871 if (N2C && N2C->isNullValue())
2874 case ISD::FP_ROUND_INREG: {
2875 EVT EVT = cast<VTSDNode>(N2)->getVT();
2876 assert(VT == N1.getValueType() && "Not an inreg round!");
2877 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2878 "Cannot FP_ROUND_INREG integer types");
2879 assert(EVT.isVector() == VT.isVector() &&
2880 "FP_ROUND_INREG type should be vector iff the operand "
2882 assert((!EVT.isVector() ||
2883 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2884 "Vector element counts must match in FP_ROUND_INREG");
2885 assert(EVT.bitsLE(VT) && "Not rounding down!");
2887 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2891 assert(VT.isFloatingPoint() &&
2892 N1.getValueType().isFloatingPoint() &&
2893 VT.bitsLE(N1.getValueType()) &&
2894 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2895 if (N1.getValueType() == VT) return N1; // noop conversion.
2897 case ISD::AssertSext:
2898 case ISD::AssertZext: {
2899 EVT EVT = cast<VTSDNode>(N2)->getVT();
2900 assert(VT == N1.getValueType() && "Not an inreg extend!");
2901 assert(VT.isInteger() && EVT.isInteger() &&
2902 "Cannot *_EXTEND_INREG FP types");
2903 assert(!EVT.isVector() &&
2904 "AssertSExt/AssertZExt type should be the vector element type "
2905 "rather than the vector type!");
2906 assert(EVT.bitsLE(VT) && "Not extending!");
2907 if (VT == EVT) return N1; // noop assertion.
2910 case ISD::SIGN_EXTEND_INREG: {
2911 EVT EVT = cast<VTSDNode>(N2)->getVT();
2912 assert(VT == N1.getValueType() && "Not an inreg extend!");
2913 assert(VT.isInteger() && EVT.isInteger() &&
2914 "Cannot *_EXTEND_INREG FP types");
2915 assert(EVT.isVector() == VT.isVector() &&
2916 "SIGN_EXTEND_INREG type should be vector iff the operand "
2918 assert((!EVT.isVector() ||
2919 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2920 "Vector element counts must match in SIGN_EXTEND_INREG");
2921 assert(EVT.bitsLE(VT) && "Not extending!");
2922 if (EVT == VT) return N1; // Not actually extending
2925 APInt Val = N1C->getAPIntValue();
2926 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2927 Val <<= Val.getBitWidth()-FromBits;
2928 Val = Val.ashr(Val.getBitWidth()-FromBits);
2929 return getConstant(Val, VT);
2933 case ISD::EXTRACT_VECTOR_ELT:
2934 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2935 if (N1.getOpcode() == ISD::UNDEF)
2936 return getUNDEF(VT);
2938 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2939 // expanding copies of large vectors from registers.
2941 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2942 N1.getNumOperands() > 0) {
2944 N1.getOperand(0).getValueType().getVectorNumElements();
2945 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2946 N1.getOperand(N2C->getZExtValue() / Factor),
2947 getConstant(N2C->getZExtValue() % Factor,
2948 N2.getValueType()));
2951 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2952 // expanding large vector constants.
2953 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2954 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2956 if (VT != Elt.getValueType())
2957 // If the vector element type is not legal, the BUILD_VECTOR operands
2958 // are promoted and implicitly truncated, and the result implicitly
2959 // extended. Make that explicit here.
2960 Elt = getAnyExtOrTrunc(Elt, DL, VT);
2965 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2966 // operations are lowered to scalars.
2967 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2968 // If the indices are the same, return the inserted element else
2969 // if the indices are known different, extract the element from
2970 // the original vector.
2971 SDValue N1Op2 = N1.getOperand(2);
2972 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2974 if (N1Op2C && N2C) {
2975 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2976 if (VT == N1.getOperand(1).getValueType())
2977 return N1.getOperand(1);
2979 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2982 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2986 case ISD::EXTRACT_ELEMENT:
2987 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2988 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2989 (N1.getValueType().isInteger() == VT.isInteger()) &&
2990 N1.getValueType() != VT &&
2991 "Wrong types for EXTRACT_ELEMENT!");
2993 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2994 // 64-bit integers into 32-bit parts. Instead of building the extract of
2995 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2996 if (N1.getOpcode() == ISD::BUILD_PAIR)
2997 return N1.getOperand(N2C->getZExtValue());
2999 // EXTRACT_ELEMENT of a constant int is also very common.
3000 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3001 unsigned ElementSize = VT.getSizeInBits();
3002 unsigned Shift = ElementSize * N2C->getZExtValue();
3003 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3004 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3007 case ISD::EXTRACT_SUBVECTOR: {
3009 if (VT.isSimple() && N1.getValueType().isSimple()) {
3010 assert(VT.isVector() && N1.getValueType().isVector() &&
3011 "Extract subvector VTs must be a vectors!");
3012 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
3013 "Extract subvector VTs must have the same element type!");
3014 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3015 "Extract subvector must be from larger vector to smaller vector!");
3017 if (isa<ConstantSDNode>(Index.getNode())) {
3018 assert((VT.getVectorNumElements() +
3019 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3020 <= N1.getValueType().getVectorNumElements())
3021 && "Extract subvector overflow!");
3024 // Trivial extraction.
3025 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
3034 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
3035 if (SV.getNode()) return SV;
3036 } else { // Cannonicalize constant to RHS if commutative
3037 if (isCommutativeBinOp(Opcode)) {
3038 std::swap(N1C, N2C);
3044 // Constant fold FP operations.
3045 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3046 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3048 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3049 // Cannonicalize constant to RHS if commutative
3050 std::swap(N1CFP, N2CFP);
3052 } else if (N2CFP && VT != MVT::ppcf128) {
3053 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3054 APFloat::opStatus s;
3057 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3058 if (s != APFloat::opInvalidOp)
3059 return getConstantFP(V1, VT);
3062 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3063 if (s!=APFloat::opInvalidOp)
3064 return getConstantFP(V1, VT);
3067 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3068 if (s!=APFloat::opInvalidOp)
3069 return getConstantFP(V1, VT);
3072 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3073 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3074 return getConstantFP(V1, VT);
3077 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3078 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3079 return getConstantFP(V1, VT);
3081 case ISD::FCOPYSIGN:
3083 return getConstantFP(V1, VT);
3088 if (Opcode == ISD::FP_ROUND) {
3089 APFloat V = N1CFP->getValueAPF(); // make copy
3091 // This can return overflow, underflow, or inexact; we don't care.
3092 // FIXME need to be more flexible about rounding mode.
3093 (void)V.convert(*EVTToAPFloatSemantics(VT),
3094 APFloat::rmNearestTiesToEven, &ignored);
3095 return getConstantFP(V, VT);
3099 // Canonicalize an UNDEF to the RHS, even over a constant.
3100 if (N1.getOpcode() == ISD::UNDEF) {
3101 if (isCommutativeBinOp(Opcode)) {
3105 case ISD::FP_ROUND_INREG:
3106 case ISD::SIGN_EXTEND_INREG:
3112 return N1; // fold op(undef, arg2) -> undef
3120 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3121 // For vectors, we can't easily build an all zero vector, just return
3128 // Fold a bunch of operators when the RHS is undef.
3129 if (N2.getOpcode() == ISD::UNDEF) {
3132 if (N1.getOpcode() == ISD::UNDEF)
3133 // Handle undef ^ undef -> 0 special case. This is a common
3135 return getConstant(0, VT);
3145 return N2; // fold op(arg1, undef) -> undef
3151 if (getTarget().Options.UnsafeFPMath)
3159 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3160 // For vectors, we can't easily build an all zero vector, just return
3165 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3166 // For vectors, we can't easily build an all one vector, just return
3174 // Memoize this node if possible.
3176 SDVTList VTs = getVTList(VT);
3177 if (VT != MVT::Glue) {
3178 SDValue Ops[] = { N1, N2 };
3179 FoldingSetNodeID ID;
3180 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3182 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3183 return SDValue(E, 0);
3185 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3186 CSEMap.InsertNode(N, IP);
3188 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3191 AllNodes.push_back(N);
3195 return SDValue(N, 0);
3198 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3199 SDValue N1, SDValue N2, SDValue N3) {
3200 // Perform various simplifications.
3201 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3203 case ISD::CONCAT_VECTORS:
3204 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3205 // one big BUILD_VECTOR.
3206 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3207 N2.getOpcode() == ISD::BUILD_VECTOR &&
3208 N3.getOpcode() == ISD::BUILD_VECTOR) {
3209 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3210 N1.getNode()->op_end());
3211 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3212 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3213 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3217 // Use FoldSetCC to simplify SETCC's.
3218 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3219 if (Simp.getNode()) return Simp;
3224 if (N1C->getZExtValue())
3225 return N2; // select true, X, Y -> X
3226 return N3; // select false, X, Y -> Y
3229 if (N2 == N3) return N2; // select C, X, X -> X
3231 case ISD::VECTOR_SHUFFLE:
3232 llvm_unreachable("should use getVectorShuffle constructor!");
3233 case ISD::INSERT_SUBVECTOR: {
3235 if (VT.isSimple() && N1.getValueType().isSimple()
3236 && N2.getValueType().isSimple()) {
3237 assert(VT.isVector() && N1.getValueType().isVector() &&
3238 N2.getValueType().isVector() &&
3239 "Insert subvector VTs must be a vectors");
3240 assert(VT == N1.getValueType() &&
3241 "Dest and insert subvector source types must match!");
3242 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3243 "Insert subvector must be from smaller vector to larger vector!");
3244 if (isa<ConstantSDNode>(Index.getNode())) {
3245 assert((N2.getValueType().getVectorNumElements() +
3246 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3247 <= VT.getVectorNumElements())
3248 && "Insert subvector overflow!");
3251 // Trivial insertion.
3252 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3258 // Fold bit_convert nodes from a type to themselves.
3259 if (N1.getValueType() == VT)
3264 // Memoize node if it doesn't produce a flag.
3266 SDVTList VTs = getVTList(VT);
3267 if (VT != MVT::Glue) {
3268 SDValue Ops[] = { N1, N2, N3 };
3269 FoldingSetNodeID ID;
3270 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3272 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3273 return SDValue(E, 0);
3275 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3276 CSEMap.InsertNode(N, IP);
3278 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3281 AllNodes.push_back(N);
3285 return SDValue(N, 0);
3288 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3289 SDValue N1, SDValue N2, SDValue N3,
3291 SDValue Ops[] = { N1, N2, N3, N4 };
3292 return getNode(Opcode, DL, VT, Ops, 4);
3295 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3296 SDValue N1, SDValue N2, SDValue N3,
3297 SDValue N4, SDValue N5) {
3298 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3299 return getNode(Opcode, DL, VT, Ops, 5);
3302 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3303 /// the incoming stack arguments to be loaded from the stack.
3304 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3305 SmallVector<SDValue, 8> ArgChains;
3307 // Include the original chain at the beginning of the list. When this is
3308 // used by target LowerCall hooks, this helps legalize find the
3309 // CALLSEQ_BEGIN node.
3310 ArgChains.push_back(Chain);
3312 // Add a chain value for each stack argument.
3313 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3314 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3315 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3316 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3317 if (FI->getIndex() < 0)
3318 ArgChains.push_back(SDValue(L, 1));
3320 // Build a tokenfactor for all the chains.
3321 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3322 &ArgChains[0], ArgChains.size());
3325 /// SplatByte - Distribute ByteVal over NumBits bits.
3326 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3327 APInt Val = APInt(NumBits, ByteVal);
3329 for (unsigned i = NumBits; i > 8; i >>= 1) {
3330 Val = (Val << Shift) | Val;
3336 /// getMemsetValue - Vectorized representation of the memset value
3338 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3340 assert(Value.getOpcode() != ISD::UNDEF);
3342 unsigned NumBits = VT.getScalarType().getSizeInBits();
3343 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3344 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3346 return DAG.getConstant(Val, VT);
3347 return DAG.getConstantFP(APFloat(Val), VT);
3350 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3352 // Use a multiplication with 0x010101... to extend the input to the
3354 APInt Magic = SplatByte(NumBits, 0x01);
3355 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3361 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3362 /// used when a memcpy is turned into a memset when the source is a constant
3364 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3365 const TargetLowering &TLI, StringRef Str) {
3366 // Handle vector with all elements zero.
3369 return DAG.getConstant(0, VT);
3370 else if (VT == MVT::f32 || VT == MVT::f64)
3371 return DAG.getConstantFP(0.0, VT);
3372 else if (VT.isVector()) {
3373 unsigned NumElts = VT.getVectorNumElements();
3374 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3375 return DAG.getNode(ISD::BITCAST, dl, VT,
3376 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3379 llvm_unreachable("Expected type!");
3382 assert(!VT.isVector() && "Can't handle vector type here!");
3383 unsigned NumVTBytes = VT.getSizeInBits() / 8;
3384 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3387 if (TLI.isLittleEndian()) {
3388 for (unsigned i = 0; i != NumBytes; ++i)
3389 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3391 for (unsigned i = 0; i != NumBytes; ++i)
3392 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3395 return DAG.getConstant(Val, VT);
3398 /// getMemBasePlusOffset - Returns base and offset node for the
3400 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3401 SelectionDAG &DAG) {
3402 EVT VT = Base.getValueType();
3403 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3404 VT, Base, DAG.getConstant(Offset, VT));
3407 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3409 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3410 unsigned SrcDelta = 0;
3411 GlobalAddressSDNode *G = NULL;
3412 if (Src.getOpcode() == ISD::GlobalAddress)
3413 G = cast<GlobalAddressSDNode>(Src);
3414 else if (Src.getOpcode() == ISD::ADD &&
3415 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3416 Src.getOperand(1).getOpcode() == ISD::Constant) {
3417 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3418 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3423 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3426 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3427 /// to replace the memset / memcpy. Return true if the number of memory ops
3428 /// is below the threshold. It returns the types of the sequence of
3429 /// memory ops to perform memset / memcpy by reference.
3430 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3431 unsigned Limit, uint64_t Size,
3432 unsigned DstAlign, unsigned SrcAlign,
3436 const TargetLowering &TLI) {
3437 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3438 "Expecting memcpy / memset source to meet alignment requirement!");
3439 // If 'SrcAlign' is zero, that means the memory operation does not need to
3440 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3441 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3442 // is the specified alignment of the memory operation. If it is zero, that
3443 // means it's possible to change the alignment of the destination.
3444 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3445 // not need to be loaded.
3446 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3447 IsZeroVal, MemcpyStrSrc,
3448 DAG.getMachineFunction());
3450 if (VT == MVT::Other) {
3451 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3452 TLI.allowsUnalignedMemoryAccesses(VT)) {
3453 VT = TLI.getPointerTy();
3455 switch (DstAlign & 7) {
3456 case 0: VT = MVT::i64; break;
3457 case 4: VT = MVT::i32; break;
3458 case 2: VT = MVT::i16; break;
3459 default: VT = MVT::i8; break;
3464 while (!TLI.isTypeLegal(LVT))
3465 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3466 assert(LVT.isInteger());
3472 unsigned NumMemOps = 0;
3474 unsigned VTSize = VT.getSizeInBits() / 8;
3475 while (VTSize > Size) {
3476 // For now, only use non-vector load / store's for the left-over pieces.
3477 if (VT.isVector() || VT.isFloatingPoint()) {
3479 while (!TLI.isTypeLegal(VT))
3480 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3481 VTSize = VT.getSizeInBits() / 8;
3483 // This can result in a type that is not legal on the target, e.g.
3484 // 1 or 2 bytes on PPC.
3485 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3490 if (++NumMemOps > Limit)
3492 MemOps.push_back(VT);
3499 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3500 SDValue Chain, SDValue Dst,
3501 SDValue Src, uint64_t Size,
3502 unsigned Align, bool isVol,
3504 MachinePointerInfo DstPtrInfo,
3505 MachinePointerInfo SrcPtrInfo) {
3506 // Turn a memcpy of undef to nop.
3507 if (Src.getOpcode() == ISD::UNDEF)
3510 // Expand memcpy to a series of load and store ops if the size operand falls
3511 // below a certain threshold.
3512 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3513 // rather than maybe a humongous number of loads and stores.
3514 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3515 std::vector<EVT> MemOps;
3516 bool DstAlignCanChange = false;
3517 MachineFunction &MF = DAG.getMachineFunction();
3518 MachineFrameInfo *MFI = MF.getFrameInfo();
3519 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3520 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3521 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3522 DstAlignCanChange = true;
3523 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3524 if (Align > SrcAlign)
3527 bool CopyFromStr = isMemSrcFromString(Src, Str);
3528 bool isZeroStr = CopyFromStr && Str.empty();
3529 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3531 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3532 (DstAlignCanChange ? 0 : Align),
3533 (isZeroStr ? 0 : SrcAlign),
3534 true, CopyFromStr, DAG, TLI))
3537 if (DstAlignCanChange) {
3538 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3539 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3540 if (NewAlign > Align) {
3541 // Give the stack frame object a larger alignment if needed.
3542 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3543 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3548 SmallVector<SDValue, 8> OutChains;
3549 unsigned NumMemOps = MemOps.size();
3550 uint64_t SrcOff = 0, DstOff = 0;
3551 for (unsigned i = 0; i != NumMemOps; ++i) {
3553 unsigned VTSize = VT.getSizeInBits() / 8;
3554 SDValue Value, Store;
3557 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3558 // It's unlikely a store of a vector immediate can be done in a single
3559 // instruction. It would require a load from a constantpool first.
3560 // We only handle zero vectors here.
3561 // FIXME: Handle other cases where store of vector immediate is done in
3562 // a single instruction.
3563 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3564 Store = DAG.getStore(Chain, dl, Value,
3565 getMemBasePlusOffset(Dst, DstOff, DAG),
3566 DstPtrInfo.getWithOffset(DstOff), isVol,
3569 // The type might not be legal for the target. This should only happen
3570 // if the type is smaller than a legal type, as on PPC, so the right
3571 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3572 // to Load/Store if NVT==VT.
3573 // FIXME does the case above also need this?
3574 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3575 assert(NVT.bitsGE(VT));
3576 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3577 getMemBasePlusOffset(Src, SrcOff, DAG),
3578 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3579 MinAlign(SrcAlign, SrcOff));
3580 Store = DAG.getTruncStore(Chain, dl, Value,
3581 getMemBasePlusOffset(Dst, DstOff, DAG),
3582 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3585 OutChains.push_back(Store);
3590 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3591 &OutChains[0], OutChains.size());
3594 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3595 SDValue Chain, SDValue Dst,
3596 SDValue Src, uint64_t Size,
3597 unsigned Align, bool isVol,
3599 MachinePointerInfo DstPtrInfo,
3600 MachinePointerInfo SrcPtrInfo) {
3601 // Turn a memmove of undef to nop.
3602 if (Src.getOpcode() == ISD::UNDEF)
3605 // Expand memmove to a series of load and store ops if the size operand falls
3606 // below a certain threshold.
3607 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3608 std::vector<EVT> MemOps;
3609 bool DstAlignCanChange = false;
3610 MachineFunction &MF = DAG.getMachineFunction();
3611 MachineFrameInfo *MFI = MF.getFrameInfo();
3612 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3613 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3614 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3615 DstAlignCanChange = true;
3616 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3617 if (Align > SrcAlign)
3619 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3621 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3622 (DstAlignCanChange ? 0 : Align),
3623 SrcAlign, true, false, DAG, TLI))
3626 if (DstAlignCanChange) {
3627 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3628 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3629 if (NewAlign > Align) {
3630 // Give the stack frame object a larger alignment if needed.
3631 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3632 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3637 uint64_t SrcOff = 0, DstOff = 0;
3638 SmallVector<SDValue, 8> LoadValues;
3639 SmallVector<SDValue, 8> LoadChains;
3640 SmallVector<SDValue, 8> OutChains;
3641 unsigned NumMemOps = MemOps.size();
3642 for (unsigned i = 0; i < NumMemOps; i++) {
3644 unsigned VTSize = VT.getSizeInBits() / 8;
3645 SDValue Value, Store;
3647 Value = DAG.getLoad(VT, dl, Chain,
3648 getMemBasePlusOffset(Src, SrcOff, DAG),
3649 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3650 false, false, SrcAlign);
3651 LoadValues.push_back(Value);
3652 LoadChains.push_back(Value.getValue(1));
3655 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3656 &LoadChains[0], LoadChains.size());
3658 for (unsigned i = 0; i < NumMemOps; i++) {
3660 unsigned VTSize = VT.getSizeInBits() / 8;
3661 SDValue Value, Store;
3663 Store = DAG.getStore(Chain, dl, LoadValues[i],
3664 getMemBasePlusOffset(Dst, DstOff, DAG),
3665 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3666 OutChains.push_back(Store);
3670 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3671 &OutChains[0], OutChains.size());
3674 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3675 SDValue Chain, SDValue Dst,
3676 SDValue Src, uint64_t Size,
3677 unsigned Align, bool isVol,
3678 MachinePointerInfo DstPtrInfo) {
3679 // Turn a memset of undef to nop.
3680 if (Src.getOpcode() == ISD::UNDEF)
3683 // Expand memset to a series of load/store ops if the size operand
3684 // falls below a certain threshold.
3685 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3686 std::vector<EVT> MemOps;
3687 bool DstAlignCanChange = false;
3688 MachineFunction &MF = DAG.getMachineFunction();
3689 MachineFrameInfo *MFI = MF.getFrameInfo();
3690 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3691 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3692 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3693 DstAlignCanChange = true;
3695 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3696 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3697 Size, (DstAlignCanChange ? 0 : Align), 0,
3698 IsZeroVal, false, DAG, TLI))
3701 if (DstAlignCanChange) {
3702 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3703 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3704 if (NewAlign > Align) {
3705 // Give the stack frame object a larger alignment if needed.
3706 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3707 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3712 SmallVector<SDValue, 8> OutChains;
3713 uint64_t DstOff = 0;
3714 unsigned NumMemOps = MemOps.size();
3716 // Find the largest store and generate the bit pattern for it.
3717 EVT LargestVT = MemOps[0];
3718 for (unsigned i = 1; i < NumMemOps; i++)
3719 if (MemOps[i].bitsGT(LargestVT))
3720 LargestVT = MemOps[i];
3721 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3723 for (unsigned i = 0; i < NumMemOps; i++) {
3726 // If this store is smaller than the largest store see whether we can get
3727 // the smaller value for free with a truncate.
3728 SDValue Value = MemSetValue;
3729 if (VT.bitsLT(LargestVT)) {
3730 if (!LargestVT.isVector() && !VT.isVector() &&
3731 TLI.isTruncateFree(LargestVT, VT))
3732 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3734 Value = getMemsetValue(Src, VT, DAG, dl);
3736 assert(Value.getValueType() == VT && "Value with wrong type.");
3737 SDValue Store = DAG.getStore(Chain, dl, Value,
3738 getMemBasePlusOffset(Dst, DstOff, DAG),
3739 DstPtrInfo.getWithOffset(DstOff),
3740 isVol, false, Align);
3741 OutChains.push_back(Store);
3742 DstOff += VT.getSizeInBits() / 8;
3745 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3746 &OutChains[0], OutChains.size());
3749 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3750 SDValue Src, SDValue Size,
3751 unsigned Align, bool isVol, bool AlwaysInline,
3752 MachinePointerInfo DstPtrInfo,
3753 MachinePointerInfo SrcPtrInfo) {
3755 // Check to see if we should lower the memcpy to loads and stores first.
3756 // For cases within the target-specified limits, this is the best choice.
3757 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3759 // Memcpy with size zero? Just return the original chain.
3760 if (ConstantSize->isNullValue())
3763 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3764 ConstantSize->getZExtValue(),Align,
3765 isVol, false, DstPtrInfo, SrcPtrInfo);
3766 if (Result.getNode())
3770 // Then check to see if we should lower the memcpy with target-specific
3771 // code. If the target chooses to do this, this is the next best.
3773 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3774 isVol, AlwaysInline,
3775 DstPtrInfo, SrcPtrInfo);
3776 if (Result.getNode())
3779 // If we really need inline code and the target declined to provide it,
3780 // use a (potentially long) sequence of loads and stores.
3782 assert(ConstantSize && "AlwaysInline requires a constant size!");
3783 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3784 ConstantSize->getZExtValue(), Align, isVol,
3785 true, DstPtrInfo, SrcPtrInfo);
3788 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3789 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3790 // respect volatile, so they may do things like read or write memory
3791 // beyond the given memory regions. But fixing this isn't easy, and most
3792 // people don't care.
3794 // Emit a library call.
3795 TargetLowering::ArgListTy Args;
3796 TargetLowering::ArgListEntry Entry;
3797 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3798 Entry.Node = Dst; Args.push_back(Entry);
3799 Entry.Node = Src; Args.push_back(Entry);
3800 Entry.Node = Size; Args.push_back(Entry);
3801 // FIXME: pass in DebugLoc
3803 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3804 false, false, false, false, 0,
3805 TLI.getLibcallCallingConv(RTLIB::MEMCPY),
3806 /*isTailCall=*/false,
3807 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3808 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3809 TLI.getPointerTy()),
3811 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3813 return CallResult.second;
3816 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3817 SDValue Src, SDValue Size,
3818 unsigned Align, bool isVol,
3819 MachinePointerInfo DstPtrInfo,
3820 MachinePointerInfo SrcPtrInfo) {
3822 // Check to see if we should lower the memmove to loads and stores first.
3823 // For cases within the target-specified limits, this is the best choice.
3824 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3826 // Memmove with size zero? Just return the original chain.
3827 if (ConstantSize->isNullValue())
3831 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3832 ConstantSize->getZExtValue(), Align, isVol,
3833 false, DstPtrInfo, SrcPtrInfo);
3834 if (Result.getNode())
3838 // Then check to see if we should lower the memmove with target-specific
3839 // code. If the target chooses to do this, this is the next best.
3841 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3842 DstPtrInfo, SrcPtrInfo);
3843 if (Result.getNode())
3846 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3847 // not be safe. See memcpy above for more details.
3849 // Emit a library call.
3850 TargetLowering::ArgListTy Args;
3851 TargetLowering::ArgListEntry Entry;
3852 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3853 Entry.Node = Dst; Args.push_back(Entry);
3854 Entry.Node = Src; Args.push_back(Entry);
3855 Entry.Node = Size; Args.push_back(Entry);
3856 // FIXME: pass in DebugLoc
3858 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3859 false, false, false, false, 0,
3860 TLI.getLibcallCallingConv(RTLIB::MEMMOVE),
3861 /*isTailCall=*/false,
3862 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3863 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3864 TLI.getPointerTy()),
3866 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3868 return CallResult.second;
3871 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3872 SDValue Src, SDValue Size,
3873 unsigned Align, bool isVol,
3874 MachinePointerInfo DstPtrInfo) {
3876 // Check to see if we should lower the memset to stores first.
3877 // For cases within the target-specified limits, this is the best choice.
3878 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3880 // Memset with size zero? Just return the original chain.
3881 if (ConstantSize->isNullValue())
3885 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3886 Align, isVol, DstPtrInfo);
3888 if (Result.getNode())
3892 // Then check to see if we should lower the memset with target-specific
3893 // code. If the target chooses to do this, this is the next best.
3895 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3897 if (Result.getNode())
3900 // Emit a library call.
3901 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3902 TargetLowering::ArgListTy Args;
3903 TargetLowering::ArgListEntry Entry;
3904 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3905 Args.push_back(Entry);
3906 // Extend or truncate the argument to be an i32 value for the call.
3907 if (Src.getValueType().bitsGT(MVT::i32))
3908 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3910 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3912 Entry.Ty = Type::getInt32Ty(*getContext());
3913 Entry.isSExt = true;
3914 Args.push_back(Entry);
3916 Entry.Ty = IntPtrTy;
3917 Entry.isSExt = false;
3918 Args.push_back(Entry);
3919 // FIXME: pass in DebugLoc
3921 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
3922 false, false, false, false, 0,
3923 TLI.getLibcallCallingConv(RTLIB::MEMSET),
3924 /*isTailCall=*/false,
3925 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3926 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3927 TLI.getPointerTy()),
3929 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI);
3931 return CallResult.second;
3934 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3935 SDValue Chain, SDValue Ptr, SDValue Cmp,
3936 SDValue Swp, MachinePointerInfo PtrInfo,
3938 AtomicOrdering Ordering,
3939 SynchronizationScope SynchScope) {
3940 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3941 Alignment = getEVTAlignment(MemVT);
3943 MachineFunction &MF = getMachineFunction();
3945 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
3946 // For now, atomics are considered to be volatile always.
3947 // FIXME: Volatile isn't really correct; we should keep track of atomic
3948 // orderings in the memoperand.
3949 unsigned Flags = MachineMemOperand::MOVolatile;
3950 if (Opcode != ISD::ATOMIC_STORE)
3951 Flags |= MachineMemOperand::MOLoad;
3952 if (Opcode != ISD::ATOMIC_LOAD)
3953 Flags |= MachineMemOperand::MOStore;
3955 MachineMemOperand *MMO =
3956 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3958 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3959 Ordering, SynchScope);
3962 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3964 SDValue Ptr, SDValue Cmp,
3965 SDValue Swp, MachineMemOperand *MMO,
3966 AtomicOrdering Ordering,
3967 SynchronizationScope SynchScope) {
3968 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3969 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3971 EVT VT = Cmp.getValueType();
3973 SDVTList VTs = getVTList(VT, MVT::Other);
3974 FoldingSetNodeID ID;
3975 ID.AddInteger(MemVT.getRawBits());
3976 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3977 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3978 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
3980 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3981 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3982 return SDValue(E, 0);
3984 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3985 Ptr, Cmp, Swp, MMO, Ordering,
3987 CSEMap.InsertNode(N, IP);
3988 AllNodes.push_back(N);
3989 return SDValue(N, 0);
3992 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3994 SDValue Ptr, SDValue Val,
3995 const Value* PtrVal,
3997 AtomicOrdering Ordering,
3998 SynchronizationScope SynchScope) {
3999 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4000 Alignment = getEVTAlignment(MemVT);
4002 MachineFunction &MF = getMachineFunction();
4003 // An atomic store does not load. An atomic load does not store.
4004 // (An atomicrmw obviously both loads and stores.)
4005 // For now, atomics are considered to be volatile always, and they are
4007 // FIXME: Volatile isn't really correct; we should keep track of atomic
4008 // orderings in the memoperand.
4009 unsigned Flags = MachineMemOperand::MOVolatile;
4010 if (Opcode != ISD::ATOMIC_STORE)
4011 Flags |= MachineMemOperand::MOLoad;
4012 if (Opcode != ISD::ATOMIC_LOAD)
4013 Flags |= MachineMemOperand::MOStore;
4015 MachineMemOperand *MMO =
4016 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4017 MemVT.getStoreSize(), Alignment);
4019 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4020 Ordering, SynchScope);
4023 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4025 SDValue Ptr, SDValue Val,
4026 MachineMemOperand *MMO,
4027 AtomicOrdering Ordering,
4028 SynchronizationScope SynchScope) {
4029 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4030 Opcode == ISD::ATOMIC_LOAD_SUB ||
4031 Opcode == ISD::ATOMIC_LOAD_AND ||
4032 Opcode == ISD::ATOMIC_LOAD_OR ||
4033 Opcode == ISD::ATOMIC_LOAD_XOR ||
4034 Opcode == ISD::ATOMIC_LOAD_NAND ||
4035 Opcode == ISD::ATOMIC_LOAD_MIN ||
4036 Opcode == ISD::ATOMIC_LOAD_MAX ||
4037 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4038 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4039 Opcode == ISD::ATOMIC_SWAP ||
4040 Opcode == ISD::ATOMIC_STORE) &&
4041 "Invalid Atomic Op");
4043 EVT VT = Val.getValueType();
4045 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4046 getVTList(VT, MVT::Other);
4047 FoldingSetNodeID ID;
4048 ID.AddInteger(MemVT.getRawBits());
4049 SDValue Ops[] = {Chain, Ptr, Val};
4050 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
4051 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4053 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4054 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4055 return SDValue(E, 0);
4057 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4059 Ordering, SynchScope);
4060 CSEMap.InsertNode(N, IP);
4061 AllNodes.push_back(N);
4062 return SDValue(N, 0);
4065 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4066 EVT VT, SDValue Chain,
4068 const Value* PtrVal,
4070 AtomicOrdering Ordering,
4071 SynchronizationScope SynchScope) {
4072 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4073 Alignment = getEVTAlignment(MemVT);
4075 MachineFunction &MF = getMachineFunction();
4076 // An atomic store does not load. An atomic load does not store.
4077 // (An atomicrmw obviously both loads and stores.)
4078 // For now, atomics are considered to be volatile always, and they are
4080 // FIXME: Volatile isn't really correct; we should keep track of atomic
4081 // orderings in the memoperand.
4082 unsigned Flags = MachineMemOperand::MOVolatile;
4083 if (Opcode != ISD::ATOMIC_STORE)
4084 Flags |= MachineMemOperand::MOLoad;
4085 if (Opcode != ISD::ATOMIC_LOAD)
4086 Flags |= MachineMemOperand::MOStore;
4088 MachineMemOperand *MMO =
4089 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4090 MemVT.getStoreSize(), Alignment);
4092 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4093 Ordering, SynchScope);
4096 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4097 EVT VT, SDValue Chain,
4099 MachineMemOperand *MMO,
4100 AtomicOrdering Ordering,
4101 SynchronizationScope SynchScope) {
4102 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4104 SDVTList VTs = getVTList(VT, MVT::Other);
4105 FoldingSetNodeID ID;
4106 ID.AddInteger(MemVT.getRawBits());
4107 SDValue Ops[] = {Chain, Ptr};
4108 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4109 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4111 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4112 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4113 return SDValue(E, 0);
4115 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4116 Ptr, MMO, Ordering, SynchScope);
4117 CSEMap.InsertNode(N, IP);
4118 AllNodes.push_back(N);
4119 return SDValue(N, 0);
4122 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4123 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4128 SmallVector<EVT, 4> VTs;
4129 VTs.reserve(NumOps);
4130 for (unsigned i = 0; i < NumOps; ++i)
4131 VTs.push_back(Ops[i].getValueType());
4132 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4137 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4138 const EVT *VTs, unsigned NumVTs,
4139 const SDValue *Ops, unsigned NumOps,
4140 EVT MemVT, MachinePointerInfo PtrInfo,
4141 unsigned Align, bool Vol,
4142 bool ReadMem, bool WriteMem) {
4143 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4144 MemVT, PtrInfo, Align, Vol,
4149 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4150 const SDValue *Ops, unsigned NumOps,
4151 EVT MemVT, MachinePointerInfo PtrInfo,
4152 unsigned Align, bool Vol,
4153 bool ReadMem, bool WriteMem) {
4154 if (Align == 0) // Ensure that codegen never sees alignment 0
4155 Align = getEVTAlignment(MemVT);
4157 MachineFunction &MF = getMachineFunction();
4160 Flags |= MachineMemOperand::MOStore;
4162 Flags |= MachineMemOperand::MOLoad;
4164 Flags |= MachineMemOperand::MOVolatile;
4165 MachineMemOperand *MMO =
4166 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4168 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4172 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4173 const SDValue *Ops, unsigned NumOps,
4174 EVT MemVT, MachineMemOperand *MMO) {
4175 assert((Opcode == ISD::INTRINSIC_VOID ||
4176 Opcode == ISD::INTRINSIC_W_CHAIN ||
4177 Opcode == ISD::PREFETCH ||
4178 Opcode == ISD::LIFETIME_START ||
4179 Opcode == ISD::LIFETIME_END ||
4180 (Opcode <= INT_MAX &&
4181 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4182 "Opcode is not a memory-accessing opcode!");
4184 // Memoize the node unless it returns a flag.
4185 MemIntrinsicSDNode *N;
4186 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4187 FoldingSetNodeID ID;
4188 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4189 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4191 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4192 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4193 return SDValue(E, 0);
4196 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4198 CSEMap.InsertNode(N, IP);
4200 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4203 AllNodes.push_back(N);
4204 return SDValue(N, 0);
4207 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4208 /// MachinePointerInfo record from it. This is particularly useful because the
4209 /// code generator has many cases where it doesn't bother passing in a
4210 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4211 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4212 // If this is FI+Offset, we can model it.
4213 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4214 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4216 // If this is (FI+Offset1)+Offset2, we can model it.
4217 if (Ptr.getOpcode() != ISD::ADD ||
4218 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4219 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4220 return MachinePointerInfo();
4222 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4223 return MachinePointerInfo::getFixedStack(FI, Offset+
4224 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4227 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4228 /// MachinePointerInfo record from it. This is particularly useful because the
4229 /// code generator has many cases where it doesn't bother passing in a
4230 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4231 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4232 // If the 'Offset' value isn't a constant, we can't handle this.
4233 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4234 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4235 if (OffsetOp.getOpcode() == ISD::UNDEF)
4236 return InferPointerInfo(Ptr);
4237 return MachinePointerInfo();
4242 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4243 EVT VT, DebugLoc dl, SDValue Chain,
4244 SDValue Ptr, SDValue Offset,
4245 MachinePointerInfo PtrInfo, EVT MemVT,
4246 bool isVolatile, bool isNonTemporal, bool isInvariant,
4247 unsigned Alignment, const MDNode *TBAAInfo,
4248 const MDNode *Ranges) {
4249 assert(Chain.getValueType() == MVT::Other &&
4250 "Invalid chain type");
4251 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4252 Alignment = getEVTAlignment(VT);
4254 unsigned Flags = MachineMemOperand::MOLoad;
4256 Flags |= MachineMemOperand::MOVolatile;
4258 Flags |= MachineMemOperand::MONonTemporal;
4260 Flags |= MachineMemOperand::MOInvariant;
4262 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4265 PtrInfo = InferPointerInfo(Ptr, Offset);
4267 MachineFunction &MF = getMachineFunction();
4268 MachineMemOperand *MMO =
4269 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4271 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4275 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4276 EVT VT, DebugLoc dl, SDValue Chain,
4277 SDValue Ptr, SDValue Offset, EVT MemVT,
4278 MachineMemOperand *MMO) {
4280 ExtType = ISD::NON_EXTLOAD;
4281 } else if (ExtType == ISD::NON_EXTLOAD) {
4282 assert(VT == MemVT && "Non-extending load from different memory type!");
4285 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4286 "Should only be an extending load, not truncating!");
4287 assert(VT.isInteger() == MemVT.isInteger() &&
4288 "Cannot convert from FP to Int or Int -> FP!");
4289 assert(VT.isVector() == MemVT.isVector() &&
4290 "Cannot use trunc store to convert to or from a vector!");
4291 assert((!VT.isVector() ||
4292 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4293 "Cannot use trunc store to change the number of vector elements!");
4296 bool Indexed = AM != ISD::UNINDEXED;
4297 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4298 "Unindexed load with an offset!");
4300 SDVTList VTs = Indexed ?
4301 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4302 SDValue Ops[] = { Chain, Ptr, Offset };
4303 FoldingSetNodeID ID;
4304 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4305 ID.AddInteger(MemVT.getRawBits());
4306 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4307 MMO->isNonTemporal(),
4308 MMO->isInvariant()));
4309 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4311 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4312 cast<LoadSDNode>(E)->refineAlignment(MMO);
4313 return SDValue(E, 0);
4315 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4317 CSEMap.InsertNode(N, IP);
4318 AllNodes.push_back(N);
4319 return SDValue(N, 0);
4322 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4323 SDValue Chain, SDValue Ptr,
4324 MachinePointerInfo PtrInfo,
4325 bool isVolatile, bool isNonTemporal,
4326 bool isInvariant, unsigned Alignment,
4327 const MDNode *TBAAInfo,
4328 const MDNode *Ranges) {
4329 SDValue Undef = getUNDEF(Ptr.getValueType());
4330 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4331 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4335 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4336 SDValue Chain, SDValue Ptr,
4337 MachinePointerInfo PtrInfo, EVT MemVT,
4338 bool isVolatile, bool isNonTemporal,
4339 unsigned Alignment, const MDNode *TBAAInfo) {
4340 SDValue Undef = getUNDEF(Ptr.getValueType());
4341 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4342 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4348 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4349 SDValue Offset, ISD::MemIndexedMode AM) {
4350 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4351 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4352 "Load is already a indexed load!");
4353 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4354 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4355 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4356 false, LD->getAlignment());
4359 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4360 SDValue Ptr, MachinePointerInfo PtrInfo,
4361 bool isVolatile, bool isNonTemporal,
4362 unsigned Alignment, const MDNode *TBAAInfo) {
4363 assert(Chain.getValueType() == MVT::Other &&
4364 "Invalid chain type");
4365 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4366 Alignment = getEVTAlignment(Val.getValueType());
4368 unsigned Flags = MachineMemOperand::MOStore;
4370 Flags |= MachineMemOperand::MOVolatile;
4372 Flags |= MachineMemOperand::MONonTemporal;
4375 PtrInfo = InferPointerInfo(Ptr);
4377 MachineFunction &MF = getMachineFunction();
4378 MachineMemOperand *MMO =
4379 MF.getMachineMemOperand(PtrInfo, Flags,
4380 Val.getValueType().getStoreSize(), Alignment,
4383 return getStore(Chain, dl, Val, Ptr, MMO);
4386 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4387 SDValue Ptr, MachineMemOperand *MMO) {
4388 assert(Chain.getValueType() == MVT::Other &&
4389 "Invalid chain type");
4390 EVT VT = Val.getValueType();
4391 SDVTList VTs = getVTList(MVT::Other);
4392 SDValue Undef = getUNDEF(Ptr.getValueType());
4393 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4394 FoldingSetNodeID ID;
4395 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4396 ID.AddInteger(VT.getRawBits());
4397 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4398 MMO->isNonTemporal(), MMO->isInvariant()));
4399 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4401 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4402 cast<StoreSDNode>(E)->refineAlignment(MMO);
4403 return SDValue(E, 0);
4405 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4407 CSEMap.InsertNode(N, IP);
4408 AllNodes.push_back(N);
4409 return SDValue(N, 0);
4412 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4413 SDValue Ptr, MachinePointerInfo PtrInfo,
4414 EVT SVT,bool isVolatile, bool isNonTemporal,
4416 const MDNode *TBAAInfo) {
4417 assert(Chain.getValueType() == MVT::Other &&
4418 "Invalid chain type");
4419 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4420 Alignment = getEVTAlignment(SVT);
4422 unsigned Flags = MachineMemOperand::MOStore;
4424 Flags |= MachineMemOperand::MOVolatile;
4426 Flags |= MachineMemOperand::MONonTemporal;
4429 PtrInfo = InferPointerInfo(Ptr);
4431 MachineFunction &MF = getMachineFunction();
4432 MachineMemOperand *MMO =
4433 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4436 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4439 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4440 SDValue Ptr, EVT SVT,
4441 MachineMemOperand *MMO) {
4442 EVT VT = Val.getValueType();
4444 assert(Chain.getValueType() == MVT::Other &&
4445 "Invalid chain type");
4447 return getStore(Chain, dl, Val, Ptr, MMO);
4449 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4450 "Should only be a truncating store, not extending!");
4451 assert(VT.isInteger() == SVT.isInteger() &&
4452 "Can't do FP-INT conversion!");
4453 assert(VT.isVector() == SVT.isVector() &&
4454 "Cannot use trunc store to convert to or from a vector!");
4455 assert((!VT.isVector() ||
4456 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4457 "Cannot use trunc store to change the number of vector elements!");
4459 SDVTList VTs = getVTList(MVT::Other);
4460 SDValue Undef = getUNDEF(Ptr.getValueType());
4461 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4462 FoldingSetNodeID ID;
4463 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4464 ID.AddInteger(SVT.getRawBits());
4465 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4466 MMO->isNonTemporal(), MMO->isInvariant()));
4467 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4469 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4470 cast<StoreSDNode>(E)->refineAlignment(MMO);
4471 return SDValue(E, 0);
4473 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4475 CSEMap.InsertNode(N, IP);
4476 AllNodes.push_back(N);
4477 return SDValue(N, 0);
4481 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4482 SDValue Offset, ISD::MemIndexedMode AM) {
4483 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4484 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4485 "Store is already a indexed store!");
4486 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4487 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4488 FoldingSetNodeID ID;
4489 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4490 ID.AddInteger(ST->getMemoryVT().getRawBits());
4491 ID.AddInteger(ST->getRawSubclassData());
4492 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4494 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4495 return SDValue(E, 0);
4497 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4498 ST->isTruncatingStore(),
4500 ST->getMemOperand());
4501 CSEMap.InsertNode(N, IP);
4502 AllNodes.push_back(N);
4503 return SDValue(N, 0);
4506 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4507 SDValue Chain, SDValue Ptr,
4510 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4511 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4514 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4515 const SDUse *Ops, unsigned NumOps) {
4517 case 0: return getNode(Opcode, DL, VT);
4518 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4519 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4520 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4524 // Copy from an SDUse array into an SDValue array for use with
4525 // the regular getNode logic.
4526 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4527 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4530 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4531 const SDValue *Ops, unsigned NumOps) {
4533 case 0: return getNode(Opcode, DL, VT);
4534 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4535 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4536 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4542 case ISD::SELECT_CC: {
4543 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4544 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4545 "LHS and RHS of condition must have same type!");
4546 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4547 "True and False arms of SelectCC must have same type!");
4548 assert(Ops[2].getValueType() == VT &&
4549 "select_cc node must be of same type as true and false value!");
4553 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4554 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4555 "LHS/RHS of comparison should match types!");
4562 SDVTList VTs = getVTList(VT);
4564 if (VT != MVT::Glue) {
4565 FoldingSetNodeID ID;
4566 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4569 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4570 return SDValue(E, 0);
4572 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4573 CSEMap.InsertNode(N, IP);
4575 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4578 AllNodes.push_back(N);
4582 return SDValue(N, 0);
4585 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4586 const std::vector<EVT> &ResultTys,
4587 const SDValue *Ops, unsigned NumOps) {
4588 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4592 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4593 const EVT *VTs, unsigned NumVTs,
4594 const SDValue *Ops, unsigned NumOps) {
4596 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4597 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4600 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4601 const SDValue *Ops, unsigned NumOps) {
4602 if (VTList.NumVTs == 1)
4603 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4607 // FIXME: figure out how to safely handle things like
4608 // int foo(int x) { return 1 << (x & 255); }
4609 // int bar() { return foo(256); }
4610 case ISD::SRA_PARTS:
4611 case ISD::SRL_PARTS:
4612 case ISD::SHL_PARTS:
4613 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4614 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4615 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4616 else if (N3.getOpcode() == ISD::AND)
4617 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4618 // If the and is only masking out bits that cannot effect the shift,
4619 // eliminate the and.
4620 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4621 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4622 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4628 // Memoize the node unless it returns a flag.
4630 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4631 FoldingSetNodeID ID;
4632 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4634 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4635 return SDValue(E, 0);
4638 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4639 } else if (NumOps == 2) {
4640 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4641 } else if (NumOps == 3) {
4642 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4645 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4647 CSEMap.InsertNode(N, IP);
4650 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4651 } else if (NumOps == 2) {
4652 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4653 } else if (NumOps == 3) {
4654 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4657 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4660 AllNodes.push_back(N);
4664 return SDValue(N, 0);
4667 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4668 return getNode(Opcode, DL, VTList, 0, 0);
4671 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4673 SDValue Ops[] = { N1 };
4674 return getNode(Opcode, DL, VTList, Ops, 1);
4677 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4678 SDValue N1, SDValue N2) {
4679 SDValue Ops[] = { N1, N2 };
4680 return getNode(Opcode, DL, VTList, Ops, 2);
4683 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4684 SDValue N1, SDValue N2, SDValue N3) {
4685 SDValue Ops[] = { N1, N2, N3 };
4686 return getNode(Opcode, DL, VTList, Ops, 3);
4689 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4690 SDValue N1, SDValue N2, SDValue N3,
4692 SDValue Ops[] = { N1, N2, N3, N4 };
4693 return getNode(Opcode, DL, VTList, Ops, 4);
4696 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4697 SDValue N1, SDValue N2, SDValue N3,
4698 SDValue N4, SDValue N5) {
4699 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4700 return getNode(Opcode, DL, VTList, Ops, 5);
4703 SDVTList SelectionDAG::getVTList(EVT VT) {
4704 return makeVTList(SDNode::getValueTypeList(VT), 1);
4707 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4708 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4709 E = VTList.rend(); I != E; ++I)
4710 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4713 EVT *Array = Allocator.Allocate<EVT>(2);
4716 SDVTList Result = makeVTList(Array, 2);
4717 VTList.push_back(Result);
4721 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4722 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4723 E = VTList.rend(); I != E; ++I)
4724 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4728 EVT *Array = Allocator.Allocate<EVT>(3);
4732 SDVTList Result = makeVTList(Array, 3);
4733 VTList.push_back(Result);
4737 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4738 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4739 E = VTList.rend(); I != E; ++I)
4740 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4741 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4744 EVT *Array = Allocator.Allocate<EVT>(4);
4749 SDVTList Result = makeVTList(Array, 4);
4750 VTList.push_back(Result);
4754 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4756 case 0: llvm_unreachable("Cannot have nodes without results!");
4757 case 1: return getVTList(VTs[0]);
4758 case 2: return getVTList(VTs[0], VTs[1]);
4759 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4760 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4764 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4765 E = VTList.rend(); I != E; ++I) {
4766 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4769 if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2]))
4773 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4774 std::copy(VTs, VTs+NumVTs, Array);
4775 SDVTList Result = makeVTList(Array, NumVTs);
4776 VTList.push_back(Result);
4781 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4782 /// specified operands. If the resultant node already exists in the DAG,
4783 /// this does not modify the specified node, instead it returns the node that
4784 /// already exists. If the resultant node does not exist in the DAG, the
4785 /// input node is returned. As a degenerate case, if you specify the same
4786 /// input operands as the node already has, the input node is returned.
4787 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4788 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4790 // Check to see if there is no change.
4791 if (Op == N->getOperand(0)) return N;
4793 // See if the modified node already exists.
4794 void *InsertPos = 0;
4795 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4798 // Nope it doesn't. Remove the node from its current place in the maps.
4800 if (!RemoveNodeFromCSEMaps(N))
4803 // Now we update the operands.
4804 N->OperandList[0].set(Op);
4806 // If this gets put into a CSE map, add it.
4807 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4811 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4812 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4814 // Check to see if there is no change.
4815 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4816 return N; // No operands changed, just return the input node.
4818 // See if the modified node already exists.
4819 void *InsertPos = 0;
4820 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4823 // Nope it doesn't. Remove the node from its current place in the maps.
4825 if (!RemoveNodeFromCSEMaps(N))
4828 // Now we update the operands.
4829 if (N->OperandList[0] != Op1)
4830 N->OperandList[0].set(Op1);
4831 if (N->OperandList[1] != Op2)
4832 N->OperandList[1].set(Op2);
4834 // If this gets put into a CSE map, add it.
4835 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4839 SDNode *SelectionDAG::
4840 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4841 SDValue Ops[] = { Op1, Op2, Op3 };
4842 return UpdateNodeOperands(N, Ops, 3);
4845 SDNode *SelectionDAG::
4846 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4847 SDValue Op3, SDValue Op4) {
4848 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4849 return UpdateNodeOperands(N, Ops, 4);
4852 SDNode *SelectionDAG::
4853 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4854 SDValue Op3, SDValue Op4, SDValue Op5) {
4855 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4856 return UpdateNodeOperands(N, Ops, 5);
4859 SDNode *SelectionDAG::
4860 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4861 assert(N->getNumOperands() == NumOps &&
4862 "Update with wrong number of operands");
4864 // Check to see if there is no change.
4865 bool AnyChange = false;
4866 for (unsigned i = 0; i != NumOps; ++i) {
4867 if (Ops[i] != N->getOperand(i)) {
4873 // No operands changed, just return the input node.
4874 if (!AnyChange) return N;
4876 // See if the modified node already exists.
4877 void *InsertPos = 0;
4878 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4881 // Nope it doesn't. Remove the node from its current place in the maps.
4883 if (!RemoveNodeFromCSEMaps(N))
4886 // Now we update the operands.
4887 for (unsigned i = 0; i != NumOps; ++i)
4888 if (N->OperandList[i] != Ops[i])
4889 N->OperandList[i].set(Ops[i]);
4891 // If this gets put into a CSE map, add it.
4892 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4896 /// DropOperands - Release the operands and set this node to have
4898 void SDNode::DropOperands() {
4899 // Unlike the code in MorphNodeTo that does this, we don't need to
4900 // watch for dead nodes here.
4901 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4907 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4910 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4912 SDVTList VTs = getVTList(VT);
4913 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4916 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4917 EVT VT, SDValue Op1) {
4918 SDVTList VTs = getVTList(VT);
4919 SDValue Ops[] = { Op1 };
4920 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4923 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4924 EVT VT, SDValue Op1,
4926 SDVTList VTs = getVTList(VT);
4927 SDValue Ops[] = { Op1, Op2 };
4928 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4931 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4932 EVT VT, SDValue Op1,
4933 SDValue Op2, SDValue Op3) {
4934 SDVTList VTs = getVTList(VT);
4935 SDValue Ops[] = { Op1, Op2, Op3 };
4936 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4939 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4940 EVT VT, const SDValue *Ops,
4942 SDVTList VTs = getVTList(VT);
4943 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4946 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4947 EVT VT1, EVT VT2, const SDValue *Ops,
4949 SDVTList VTs = getVTList(VT1, VT2);
4950 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4953 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4955 SDVTList VTs = getVTList(VT1, VT2);
4956 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4959 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4960 EVT VT1, EVT VT2, EVT VT3,
4961 const SDValue *Ops, unsigned NumOps) {
4962 SDVTList VTs = getVTList(VT1, VT2, VT3);
4963 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4966 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4967 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4968 const SDValue *Ops, unsigned NumOps) {
4969 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4970 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4973 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4976 SDVTList VTs = getVTList(VT1, VT2);
4977 SDValue Ops[] = { Op1 };
4978 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4981 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4983 SDValue Op1, SDValue Op2) {
4984 SDVTList VTs = getVTList(VT1, VT2);
4985 SDValue Ops[] = { Op1, Op2 };
4986 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4989 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4991 SDValue Op1, SDValue Op2,
4993 SDVTList VTs = getVTList(VT1, VT2);
4994 SDValue Ops[] = { Op1, Op2, Op3 };
4995 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4998 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4999 EVT VT1, EVT VT2, EVT VT3,
5000 SDValue Op1, SDValue Op2,
5002 SDVTList VTs = getVTList(VT1, VT2, VT3);
5003 SDValue Ops[] = { Op1, Op2, Op3 };
5004 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5007 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5008 SDVTList VTs, const SDValue *Ops,
5010 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5011 // Reset the NodeID to -1.
5016 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
5017 /// the line number information on the merged node since it is not possible to
5018 /// preserve the information that operation is associated with multiple lines.
5019 /// This will make the debugger working better at -O0, were there is a higher
5020 /// probability having other instructions associated with that line.
5022 SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) {
5023 DebugLoc NLoc = N->getDebugLoc();
5024 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) {
5025 N->setDebugLoc(DebugLoc());
5030 /// MorphNodeTo - This *mutates* the specified node to have the specified
5031 /// return type, opcode, and operands.
5033 /// Note that MorphNodeTo returns the resultant node. If there is already a
5034 /// node of the specified opcode and operands, it returns that node instead of
5035 /// the current one. Note that the DebugLoc need not be the same.
5037 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5038 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5039 /// node, and because it doesn't require CSE recalculation for any of
5040 /// the node's users.
5042 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5043 SDVTList VTs, const SDValue *Ops,
5045 // If an identical node already exists, use it.
5047 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5048 FoldingSetNodeID ID;
5049 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5050 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5051 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc());
5054 if (!RemoveNodeFromCSEMaps(N))
5057 // Start the morphing.
5059 N->ValueList = VTs.VTs;
5060 N->NumValues = VTs.NumVTs;
5062 // Clear the operands list, updating used nodes to remove this from their
5063 // use list. Keep track of any operands that become dead as a result.
5064 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5065 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5067 SDNode *Used = Use.getNode();
5069 if (Used->use_empty())
5070 DeadNodeSet.insert(Used);
5073 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5074 // Initialize the memory references information.
5075 MN->setMemRefs(0, 0);
5076 // If NumOps is larger than the # of operands we can have in a
5077 // MachineSDNode, reallocate the operand list.
5078 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5079 if (MN->OperandsNeedDelete)
5080 delete[] MN->OperandList;
5081 if (NumOps > array_lengthof(MN->LocalOperands))
5082 // We're creating a final node that will live unmorphed for the
5083 // remainder of the current SelectionDAG iteration, so we can allocate
5084 // the operands directly out of a pool with no recycling metadata.
5085 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5088 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5089 MN->OperandsNeedDelete = false;
5091 MN->InitOperands(MN->OperandList, Ops, NumOps);
5093 // If NumOps is larger than the # of operands we currently have, reallocate
5094 // the operand list.
5095 if (NumOps > N->NumOperands) {
5096 if (N->OperandsNeedDelete)
5097 delete[] N->OperandList;
5098 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5099 N->OperandsNeedDelete = true;
5101 N->InitOperands(N->OperandList, Ops, NumOps);
5104 // Delete any nodes that are still dead after adding the uses for the
5106 if (!DeadNodeSet.empty()) {
5107 SmallVector<SDNode *, 16> DeadNodes;
5108 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5109 E = DeadNodeSet.end(); I != E; ++I)
5110 if ((*I)->use_empty())
5111 DeadNodes.push_back(*I);
5112 RemoveDeadNodes(DeadNodes);
5116 CSEMap.InsertNode(N, IP); // Memoize the new node.
5121 /// getMachineNode - These are used for target selectors to create a new node
5122 /// with specified return type(s), MachineInstr opcode, and operands.
5124 /// Note that getMachineNode returns the resultant node. If there is already a
5125 /// node of the specified opcode and operands, it returns that node instead of
5126 /// the current one.
5128 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5129 SDVTList VTs = getVTList(VT);
5130 return getMachineNode(Opcode, dl, VTs, 0, 0);
5134 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5135 SDVTList VTs = getVTList(VT);
5136 SDValue Ops[] = { Op1 };
5137 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5141 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5142 SDValue Op1, SDValue Op2) {
5143 SDVTList VTs = getVTList(VT);
5144 SDValue Ops[] = { Op1, Op2 };
5145 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5149 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5150 SDValue Op1, SDValue Op2, SDValue Op3) {
5151 SDVTList VTs = getVTList(VT);
5152 SDValue Ops[] = { Op1, Op2, Op3 };
5153 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5157 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5158 const SDValue *Ops, unsigned NumOps) {
5159 SDVTList VTs = getVTList(VT);
5160 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5164 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5165 SDVTList VTs = getVTList(VT1, VT2);
5166 return getMachineNode(Opcode, dl, VTs, 0, 0);
5170 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5171 EVT VT1, EVT VT2, SDValue Op1) {
5172 SDVTList VTs = getVTList(VT1, VT2);
5173 SDValue Ops[] = { Op1 };
5174 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5178 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5179 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5180 SDVTList VTs = getVTList(VT1, VT2);
5181 SDValue Ops[] = { Op1, Op2 };
5182 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5186 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5187 EVT VT1, EVT VT2, SDValue Op1,
5188 SDValue Op2, SDValue Op3) {
5189 SDVTList VTs = getVTList(VT1, VT2);
5190 SDValue Ops[] = { Op1, Op2, Op3 };
5191 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5195 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5197 const SDValue *Ops, unsigned NumOps) {
5198 SDVTList VTs = getVTList(VT1, VT2);
5199 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5203 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5204 EVT VT1, EVT VT2, EVT VT3,
5205 SDValue Op1, SDValue Op2) {
5206 SDVTList VTs = getVTList(VT1, VT2, VT3);
5207 SDValue Ops[] = { Op1, Op2 };
5208 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5212 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5213 EVT VT1, EVT VT2, EVT VT3,
5214 SDValue Op1, SDValue Op2, SDValue Op3) {
5215 SDVTList VTs = getVTList(VT1, VT2, VT3);
5216 SDValue Ops[] = { Op1, Op2, Op3 };
5217 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5221 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5222 EVT VT1, EVT VT2, EVT VT3,
5223 const SDValue *Ops, unsigned NumOps) {
5224 SDVTList VTs = getVTList(VT1, VT2, VT3);
5225 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5229 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5230 EVT VT2, EVT VT3, EVT VT4,
5231 const SDValue *Ops, unsigned NumOps) {
5232 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5233 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5237 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5238 const std::vector<EVT> &ResultTys,
5239 const SDValue *Ops, unsigned NumOps) {
5240 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5241 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5245 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5246 const SDValue *Ops, unsigned NumOps) {
5247 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5252 FoldingSetNodeID ID;
5253 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5255 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5256 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL));
5260 // Allocate a new MachineSDNode.
5261 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5263 // Initialize the operands list.
5264 if (NumOps > array_lengthof(N->LocalOperands))
5265 // We're creating a final node that will live unmorphed for the
5266 // remainder of the current SelectionDAG iteration, so we can allocate
5267 // the operands directly out of a pool with no recycling metadata.
5268 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5271 N->InitOperands(N->LocalOperands, Ops, NumOps);
5272 N->OperandsNeedDelete = false;
5275 CSEMap.InsertNode(N, IP);
5277 AllNodes.push_back(N);
5279 VerifyMachineNode(N);
5284 /// getTargetExtractSubreg - A convenience function for creating
5285 /// TargetOpcode::EXTRACT_SUBREG nodes.
5287 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5289 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5290 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5291 VT, Operand, SRIdxVal);
5292 return SDValue(Subreg, 0);
5295 /// getTargetInsertSubreg - A convenience function for creating
5296 /// TargetOpcode::INSERT_SUBREG nodes.
5298 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5299 SDValue Operand, SDValue Subreg) {
5300 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5301 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5302 VT, Operand, Subreg, SRIdxVal);
5303 return SDValue(Result, 0);
5306 /// getNodeIfExists - Get the specified node if it's already available, or
5307 /// else return NULL.
5308 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5309 const SDValue *Ops, unsigned NumOps) {
5310 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5311 FoldingSetNodeID ID;
5312 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5314 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5320 /// getDbgValue - Creates a SDDbgValue node.
5323 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5324 DebugLoc DL, unsigned O) {
5325 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5329 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5330 DebugLoc DL, unsigned O) {
5331 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5335 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5336 DebugLoc DL, unsigned O) {
5337 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5342 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5343 /// pointed to by a use iterator is deleted, increment the use iterator
5344 /// so that it doesn't dangle.
5346 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5347 SDNode::use_iterator &UI;
5348 SDNode::use_iterator &UE;
5350 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5351 // Increment the iterator as needed.
5352 while (UI != UE && N == *UI)
5357 RAUWUpdateListener(SelectionDAG &d,
5358 SDNode::use_iterator &ui,
5359 SDNode::use_iterator &ue)
5360 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5365 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5366 /// This can cause recursive merging of nodes in the DAG.
5368 /// This version assumes From has a single result value.
5370 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5371 SDNode *From = FromN.getNode();
5372 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5373 "Cannot replace with this method!");
5374 assert(From != To.getNode() && "Cannot replace uses of with self");
5376 // Iterate over all the existing uses of From. New uses will be added
5377 // to the beginning of the use list, which we avoid visiting.
5378 // This specifically avoids visiting uses of From that arise while the
5379 // replacement is happening, because any such uses would be the result
5380 // of CSE: If an existing node looks like From after one of its operands
5381 // is replaced by To, we don't want to replace of all its users with To
5382 // too. See PR3018 for more info.
5383 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5384 RAUWUpdateListener Listener(*this, UI, UE);
5388 // This node is about to morph, remove its old self from the CSE maps.
5389 RemoveNodeFromCSEMaps(User);
5391 // A user can appear in a use list multiple times, and when this
5392 // happens the uses are usually next to each other in the list.
5393 // To help reduce the number of CSE recomputations, process all
5394 // the uses of this user that we can find this way.
5396 SDUse &Use = UI.getUse();
5399 } while (UI != UE && *UI == User);
5401 // Now that we have modified User, add it back to the CSE maps. If it
5402 // already exists there, recursively merge the results together.
5403 AddModifiedNodeToCSEMaps(User);
5406 // If we just RAUW'd the root, take note.
5407 if (FromN == getRoot())
5411 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5412 /// This can cause recursive merging of nodes in the DAG.
5414 /// This version assumes that for each value of From, there is a
5415 /// corresponding value in To in the same position with the same type.
5417 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5419 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5420 assert((!From->hasAnyUseOfValue(i) ||
5421 From->getValueType(i) == To->getValueType(i)) &&
5422 "Cannot use this version of ReplaceAllUsesWith!");
5425 // Handle the trivial case.
5429 // Iterate over just the existing users of From. See the comments in
5430 // the ReplaceAllUsesWith above.
5431 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5432 RAUWUpdateListener Listener(*this, UI, UE);
5436 // This node is about to morph, remove its old self from the CSE maps.
5437 RemoveNodeFromCSEMaps(User);
5439 // A user can appear in a use list multiple times, and when this
5440 // happens the uses are usually next to each other in the list.
5441 // To help reduce the number of CSE recomputations, process all
5442 // the uses of this user that we can find this way.
5444 SDUse &Use = UI.getUse();
5447 } while (UI != UE && *UI == User);
5449 // Now that we have modified User, add it back to the CSE maps. If it
5450 // already exists there, recursively merge the results together.
5451 AddModifiedNodeToCSEMaps(User);
5454 // If we just RAUW'd the root, take note.
5455 if (From == getRoot().getNode())
5456 setRoot(SDValue(To, getRoot().getResNo()));
5459 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5460 /// This can cause recursive merging of nodes in the DAG.
5462 /// This version can replace From with any result values. To must match the
5463 /// number and types of values returned by From.
5464 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5465 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5466 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5468 // Iterate over just the existing users of From. See the comments in
5469 // the ReplaceAllUsesWith above.
5470 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5471 RAUWUpdateListener Listener(*this, UI, UE);
5475 // This node is about to morph, remove its old self from the CSE maps.
5476 RemoveNodeFromCSEMaps(User);
5478 // A user can appear in a use list multiple times, and when this
5479 // happens the uses are usually next to each other in the list.
5480 // To help reduce the number of CSE recomputations, process all
5481 // the uses of this user that we can find this way.
5483 SDUse &Use = UI.getUse();
5484 const SDValue &ToOp = To[Use.getResNo()];
5487 } while (UI != UE && *UI == User);
5489 // Now that we have modified User, add it back to the CSE maps. If it
5490 // already exists there, recursively merge the results together.
5491 AddModifiedNodeToCSEMaps(User);
5494 // If we just RAUW'd the root, take note.
5495 if (From == getRoot().getNode())
5496 setRoot(SDValue(To[getRoot().getResNo()]));
5499 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5500 /// uses of other values produced by From.getNode() alone. The Deleted
5501 /// vector is handled the same way as for ReplaceAllUsesWith.
5502 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5503 // Handle the really simple, really trivial case efficiently.
5504 if (From == To) return;
5506 // Handle the simple, trivial, case efficiently.
5507 if (From.getNode()->getNumValues() == 1) {
5508 ReplaceAllUsesWith(From, To);
5512 // Iterate over just the existing users of From. See the comments in
5513 // the ReplaceAllUsesWith above.
5514 SDNode::use_iterator UI = From.getNode()->use_begin(),
5515 UE = From.getNode()->use_end();
5516 RAUWUpdateListener Listener(*this, UI, UE);
5519 bool UserRemovedFromCSEMaps = false;
5521 // A user can appear in a use list multiple times, and when this
5522 // happens the uses are usually next to each other in the list.
5523 // To help reduce the number of CSE recomputations, process all
5524 // the uses of this user that we can find this way.
5526 SDUse &Use = UI.getUse();
5528 // Skip uses of different values from the same node.
5529 if (Use.getResNo() != From.getResNo()) {
5534 // If this node hasn't been modified yet, it's still in the CSE maps,
5535 // so remove its old self from the CSE maps.
5536 if (!UserRemovedFromCSEMaps) {
5537 RemoveNodeFromCSEMaps(User);
5538 UserRemovedFromCSEMaps = true;
5543 } while (UI != UE && *UI == User);
5545 // We are iterating over all uses of the From node, so if a use
5546 // doesn't use the specific value, no changes are made.
5547 if (!UserRemovedFromCSEMaps)
5550 // Now that we have modified User, add it back to the CSE maps. If it
5551 // already exists there, recursively merge the results together.
5552 AddModifiedNodeToCSEMaps(User);
5555 // If we just RAUW'd the root, take note.
5556 if (From == getRoot())
5561 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5562 /// to record information about a use.
5569 /// operator< - Sort Memos by User.
5570 bool operator<(const UseMemo &L, const UseMemo &R) {
5571 return (intptr_t)L.User < (intptr_t)R.User;
5575 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5576 /// uses of other values produced by From.getNode() alone. The same value
5577 /// may appear in both the From and To list. The Deleted vector is
5578 /// handled the same way as for ReplaceAllUsesWith.
5579 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5582 // Handle the simple, trivial case efficiently.
5584 return ReplaceAllUsesOfValueWith(*From, *To);
5586 // Read up all the uses and make records of them. This helps
5587 // processing new uses that are introduced during the
5588 // replacement process.
5589 SmallVector<UseMemo, 4> Uses;
5590 for (unsigned i = 0; i != Num; ++i) {
5591 unsigned FromResNo = From[i].getResNo();
5592 SDNode *FromNode = From[i].getNode();
5593 for (SDNode::use_iterator UI = FromNode->use_begin(),
5594 E = FromNode->use_end(); UI != E; ++UI) {
5595 SDUse &Use = UI.getUse();
5596 if (Use.getResNo() == FromResNo) {
5597 UseMemo Memo = { *UI, i, &Use };
5598 Uses.push_back(Memo);
5603 // Sort the uses, so that all the uses from a given User are together.
5604 std::sort(Uses.begin(), Uses.end());
5606 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5607 UseIndex != UseIndexEnd; ) {
5608 // We know that this user uses some value of From. If it is the right
5609 // value, update it.
5610 SDNode *User = Uses[UseIndex].User;
5612 // This node is about to morph, remove its old self from the CSE maps.
5613 RemoveNodeFromCSEMaps(User);
5615 // The Uses array is sorted, so all the uses for a given User
5616 // are next to each other in the list.
5617 // To help reduce the number of CSE recomputations, process all
5618 // the uses of this user that we can find this way.
5620 unsigned i = Uses[UseIndex].Index;
5621 SDUse &Use = *Uses[UseIndex].Use;
5625 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5627 // Now that we have modified User, add it back to the CSE maps. If it
5628 // already exists there, recursively merge the results together.
5629 AddModifiedNodeToCSEMaps(User);
5633 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5634 /// based on their topological order. It returns the maximum id and a vector
5635 /// of the SDNodes* in assigned order by reference.
5636 unsigned SelectionDAG::AssignTopologicalOrder() {
5638 unsigned DAGSize = 0;
5640 // SortedPos tracks the progress of the algorithm. Nodes before it are
5641 // sorted, nodes after it are unsorted. When the algorithm completes
5642 // it is at the end of the list.
5643 allnodes_iterator SortedPos = allnodes_begin();
5645 // Visit all the nodes. Move nodes with no operands to the front of
5646 // the list immediately. Annotate nodes that do have operands with their
5647 // operand count. Before we do this, the Node Id fields of the nodes
5648 // may contain arbitrary values. After, the Node Id fields for nodes
5649 // before SortedPos will contain the topological sort index, and the
5650 // Node Id fields for nodes At SortedPos and after will contain the
5651 // count of outstanding operands.
5652 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5655 unsigned Degree = N->getNumOperands();
5657 // A node with no uses, add it to the result array immediately.
5658 N->setNodeId(DAGSize++);
5659 allnodes_iterator Q = N;
5661 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5662 assert(SortedPos != AllNodes.end() && "Overran node list");
5665 // Temporarily use the Node Id as scratch space for the degree count.
5666 N->setNodeId(Degree);
5670 // Visit all the nodes. As we iterate, move nodes into sorted order,
5671 // such that by the time the end is reached all nodes will be sorted.
5672 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5675 // N is in sorted position, so all its uses have one less operand
5676 // that needs to be sorted.
5677 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5680 unsigned Degree = P->getNodeId();
5681 assert(Degree != 0 && "Invalid node degree");
5684 // All of P's operands are sorted, so P may sorted now.
5685 P->setNodeId(DAGSize++);
5687 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5688 assert(SortedPos != AllNodes.end() && "Overran node list");
5691 // Update P's outstanding operand count.
5692 P->setNodeId(Degree);
5695 if (I == SortedPos) {
5698 dbgs() << "Overran sorted position:\n";
5701 llvm_unreachable(0);
5705 assert(SortedPos == AllNodes.end() &&
5706 "Topological sort incomplete!");
5707 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5708 "First node in topological sort is not the entry token!");
5709 assert(AllNodes.front().getNodeId() == 0 &&
5710 "First node in topological sort has non-zero id!");
5711 assert(AllNodes.front().getNumOperands() == 0 &&
5712 "First node in topological sort has operands!");
5713 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5714 "Last node in topologic sort has unexpected id!");
5715 assert(AllNodes.back().use_empty() &&
5716 "Last node in topologic sort has users!");
5717 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5721 /// AssignOrdering - Assign an order to the SDNode.
5722 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5723 assert(SD && "Trying to assign an order to a null node!");
5724 Ordering->add(SD, Order);
5727 /// GetOrdering - Get the order for the SDNode.
5728 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5729 assert(SD && "Trying to get the order of a null node!");
5730 return Ordering->getOrder(SD);
5733 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5734 /// value is produced by SD.
5735 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5736 DbgInfo->add(DB, SD, isParameter);
5738 SD->setHasDebugValue(true);
5741 /// TransferDbgValues - Transfer SDDbgValues.
5742 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5743 if (From == To || !From.getNode()->getHasDebugValue())
5745 SDNode *FromNode = From.getNode();
5746 SDNode *ToNode = To.getNode();
5747 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5748 SmallVector<SDDbgValue *, 2> ClonedDVs;
5749 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5751 SDDbgValue *Dbg = *I;
5752 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5753 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5754 Dbg->getOffset(), Dbg->getDebugLoc(),
5756 ClonedDVs.push_back(Clone);
5759 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5760 E = ClonedDVs.end(); I != E; ++I)
5761 AddDbgValue(*I, ToNode, false);
5764 //===----------------------------------------------------------------------===//
5766 //===----------------------------------------------------------------------===//
5768 HandleSDNode::~HandleSDNode() {
5772 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5773 const GlobalValue *GA,
5774 EVT VT, int64_t o, unsigned char TF)
5775 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5779 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5780 MachineMemOperand *mmo)
5781 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5782 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5783 MMO->isNonTemporal(), MMO->isInvariant());
5784 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5785 assert(isNonTemporal() == MMO->isNonTemporal() &&
5786 "Non-temporal encoding error!");
5787 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5790 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5791 const SDValue *Ops, unsigned NumOps, EVT memvt,
5792 MachineMemOperand *mmo)
5793 : SDNode(Opc, dl, VTs, Ops, NumOps),
5794 MemoryVT(memvt), MMO(mmo) {
5795 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5796 MMO->isNonTemporal(), MMO->isInvariant());
5797 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5798 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5801 /// Profile - Gather unique data for the node.
5803 void SDNode::Profile(FoldingSetNodeID &ID) const {
5804 AddNodeIDNode(ID, this);
5809 std::vector<EVT> VTs;
5812 VTs.reserve(MVT::LAST_VALUETYPE);
5813 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5814 VTs.push_back(MVT((MVT::SimpleValueType)i));
5819 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5820 static ManagedStatic<EVTArray> SimpleVTArray;
5821 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5823 /// getValueTypeList - Return a pointer to the specified value type.
5825 const EVT *SDNode::getValueTypeList(EVT VT) {
5826 if (VT.isExtended()) {
5827 sys::SmartScopedLock<true> Lock(*VTMutex);
5828 return &(*EVTs->insert(VT).first);
5830 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5831 "Value type out of range!");
5832 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5836 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5837 /// indicated value. This method ignores uses of other values defined by this
5839 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5840 assert(Value < getNumValues() && "Bad value!");
5842 // TODO: Only iterate over uses of a given value of the node
5843 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5844 if (UI.getUse().getResNo() == Value) {
5851 // Found exactly the right number of uses?
5856 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5857 /// value. This method ignores uses of other values defined by this operation.
5858 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5859 assert(Value < getNumValues() && "Bad value!");
5861 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5862 if (UI.getUse().getResNo() == Value)
5869 /// isOnlyUserOf - Return true if this node is the only use of N.
5871 bool SDNode::isOnlyUserOf(SDNode *N) const {
5873 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5884 /// isOperand - Return true if this node is an operand of N.
5886 bool SDValue::isOperandOf(SDNode *N) const {
5887 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5888 if (*this == N->getOperand(i))
5893 bool SDNode::isOperandOf(SDNode *N) const {
5894 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5895 if (this == N->OperandList[i].getNode())
5900 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5901 /// be a chain) reaches the specified operand without crossing any
5902 /// side-effecting instructions on any chain path. In practice, this looks
5903 /// through token factors and non-volatile loads. In order to remain efficient,
5904 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5905 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5906 unsigned Depth) const {
5907 if (*this == Dest) return true;
5909 // Don't search too deeply, we just want to be able to see through
5910 // TokenFactor's etc.
5911 if (Depth == 0) return false;
5913 // If this is a token factor, all inputs to the TF happen in parallel. If any
5914 // of the operands of the TF does not reach dest, then we cannot do the xform.
5915 if (getOpcode() == ISD::TokenFactor) {
5916 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5917 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5922 // Loads don't have side effects, look through them.
5923 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5924 if (!Ld->isVolatile())
5925 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5930 /// hasPredecessor - Return true if N is a predecessor of this node.
5931 /// N is either an operand of this node, or can be reached by recursively
5932 /// traversing up the operands.
5933 /// NOTE: This is an expensive method. Use it carefully.
5934 bool SDNode::hasPredecessor(const SDNode *N) const {
5935 SmallPtrSet<const SDNode *, 32> Visited;
5936 SmallVector<const SDNode *, 16> Worklist;
5937 return hasPredecessorHelper(N, Visited, Worklist);
5940 bool SDNode::hasPredecessorHelper(const SDNode *N,
5941 SmallPtrSet<const SDNode *, 32> &Visited,
5942 SmallVector<const SDNode *, 16> &Worklist) const {
5943 if (Visited.empty()) {
5944 Worklist.push_back(this);
5946 // Take a look in the visited set. If we've already encountered this node
5947 // we needn't search further.
5948 if (Visited.count(N))
5952 // Haven't visited N yet. Continue the search.
5953 while (!Worklist.empty()) {
5954 const SDNode *M = Worklist.pop_back_val();
5955 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5956 SDNode *Op = M->getOperand(i).getNode();
5957 if (Visited.insert(Op))
5958 Worklist.push_back(Op);
5967 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5968 assert(Num < NumOperands && "Invalid child # of SDNode!");
5969 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5972 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
5973 assert(N->getNumValues() == 1 &&
5974 "Can't unroll a vector with multiple results!");
5976 EVT VT = N->getValueType(0);
5977 unsigned NE = VT.getVectorNumElements();
5978 EVT EltVT = VT.getVectorElementType();
5979 DebugLoc dl = N->getDebugLoc();
5981 SmallVector<SDValue, 8> Scalars;
5982 SmallVector<SDValue, 4> Operands(N->getNumOperands());
5984 // If ResNE is 0, fully unroll the vector op.
5987 else if (NE > ResNE)
5991 for (i= 0; i != NE; ++i) {
5992 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
5993 SDValue Operand = N->getOperand(j);
5994 EVT OperandVT = Operand.getValueType();
5995 if (OperandVT.isVector()) {
5996 // A vector operand; extract a single element.
5997 EVT OperandEltVT = OperandVT.getVectorElementType();
5998 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6001 getConstant(i, TLI.getPointerTy()));
6003 // A scalar operand; just use it as is.
6004 Operands[j] = Operand;
6008 switch (N->getOpcode()) {
6010 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6011 &Operands[0], Operands.size()));
6014 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6015 &Operands[0], Operands.size()));
6022 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6023 getShiftAmountOperand(Operands[0].getValueType(),
6026 case ISD::SIGN_EXTEND_INREG:
6027 case ISD::FP_ROUND_INREG: {
6028 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6029 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6031 getValueType(ExtVT)));
6036 for (; i < ResNE; ++i)
6037 Scalars.push_back(getUNDEF(EltVT));
6039 return getNode(ISD::BUILD_VECTOR, dl,
6040 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6041 &Scalars[0], Scalars.size());
6045 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6046 /// location that is 'Dist' units away from the location that the 'Base' load
6047 /// is loading from.
6048 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6049 unsigned Bytes, int Dist) const {
6050 if (LD->getChain() != Base->getChain())
6052 EVT VT = LD->getValueType(0);
6053 if (VT.getSizeInBits() / 8 != Bytes)
6056 SDValue Loc = LD->getOperand(1);
6057 SDValue BaseLoc = Base->getOperand(1);
6058 if (Loc.getOpcode() == ISD::FrameIndex) {
6059 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6061 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6062 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6063 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6064 int FS = MFI->getObjectSize(FI);
6065 int BFS = MFI->getObjectSize(BFI);
6066 if (FS != BFS || FS != (int)Bytes) return false;
6067 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6071 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6072 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6075 const GlobalValue *GV1 = NULL;
6076 const GlobalValue *GV2 = NULL;
6077 int64_t Offset1 = 0;
6078 int64_t Offset2 = 0;
6079 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6080 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6081 if (isGA1 && isGA2 && GV1 == GV2)
6082 return Offset1 == (Offset2 + Dist*Bytes);
6087 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6088 /// it cannot be inferred.
6089 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6090 // If this is a GlobalAddress + cst, return the alignment.
6091 const GlobalValue *GV;
6092 int64_t GVOffset = 0;
6093 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6094 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6095 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6096 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6097 TLI.getTargetData());
6098 unsigned AlignBits = KnownZero.countTrailingOnes();
6099 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6101 return MinAlign(Align, GVOffset);
6104 // If this is a direct reference to a stack slot, use information about the
6105 // stack slot's alignment.
6106 int FrameIdx = 1 << 31;
6107 int64_t FrameOffset = 0;
6108 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6109 FrameIdx = FI->getIndex();
6110 } else if (isBaseWithConstantOffset(Ptr) &&
6111 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6113 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6114 FrameOffset = Ptr.getConstantOperandVal(1);
6117 if (FrameIdx != (1 << 31)) {
6118 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6119 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6127 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6128 unsigned GlobalAddressSDNode::getAddressSpace() const {
6129 return getGlobal()->getType()->getAddressSpace();
6133 Type *ConstantPoolSDNode::getType() const {
6134 if (isMachineConstantPoolEntry())
6135 return Val.MachineCPVal->getType();
6136 return Val.ConstVal->getType();
6139 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6141 unsigned &SplatBitSize,
6143 unsigned MinSplatBits,
6145 EVT VT = getValueType(0);
6146 assert(VT.isVector() && "Expected a vector type");
6147 unsigned sz = VT.getSizeInBits();
6148 if (MinSplatBits > sz)
6151 SplatValue = APInt(sz, 0);
6152 SplatUndef = APInt(sz, 0);
6154 // Get the bits. Bits with undefined values (when the corresponding element
6155 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6156 // in SplatValue. If any of the values are not constant, give up and return
6158 unsigned int nOps = getNumOperands();
6159 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6160 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6162 for (unsigned j = 0; j < nOps; ++j) {
6163 unsigned i = isBigEndian ? nOps-1-j : j;
6164 SDValue OpVal = getOperand(i);
6165 unsigned BitPos = j * EltBitSize;
6167 if (OpVal.getOpcode() == ISD::UNDEF)
6168 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6169 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6170 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6171 zextOrTrunc(sz) << BitPos;
6172 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6173 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6178 // The build_vector is all constants or undefs. Find the smallest element
6179 // size that splats the vector.
6181 HasAnyUndefs = (SplatUndef != 0);
6184 unsigned HalfSize = sz / 2;
6185 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6186 APInt LowValue = SplatValue.trunc(HalfSize);
6187 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6188 APInt LowUndef = SplatUndef.trunc(HalfSize);
6190 // If the two halves do not match (ignoring undef bits), stop here.
6191 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6192 MinSplatBits > HalfSize)
6195 SplatValue = HighValue | LowValue;
6196 SplatUndef = HighUndef & LowUndef;
6205 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6206 // Find the first non-undef value in the shuffle mask.
6208 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6211 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6213 // Make sure all remaining elements are either undef or the same as the first
6215 for (int Idx = Mask[i]; i != e; ++i)
6216 if (Mask[i] >= 0 && Mask[i] != Idx)
6222 static void checkForCyclesHelper(const SDNode *N,
6223 SmallPtrSet<const SDNode*, 32> &Visited,
6224 SmallPtrSet<const SDNode*, 32> &Checked) {
6225 // If this node has already been checked, don't check it again.
6226 if (Checked.count(N))
6229 // If a node has already been visited on this depth-first walk, reject it as
6231 if (!Visited.insert(N)) {
6232 dbgs() << "Offending node:\n";
6234 errs() << "Detected cycle in SelectionDAG\n";
6238 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6239 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6246 void llvm::checkForCycles(const llvm::SDNode *N) {
6248 assert(N && "Checking nonexistant SDNode");
6249 SmallPtrSet<const SDNode*, 32> visited;
6250 SmallPtrSet<const SDNode*, 32> checked;
6251 checkForCyclesHelper(N, visited, checked);
6255 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6256 checkForCycles(DAG->getRoot().getNode());