1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/TargetTransformInfo.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/Assembly/Writer.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineConstantPool.h"
26 #include "llvm/CodeGen/MachineFrameInfo.h"
27 #include "llvm/CodeGen/MachineModuleInfo.h"
28 #include "llvm/DebugInfo.h"
29 #include "llvm/IR/CallingConv.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/IR/DerivedTypes.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/IR/GlobalAlias.h"
35 #include "llvm/IR/GlobalVariable.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/ErrorHandling.h"
40 #include "llvm/Support/ManagedStatic.h"
41 #include "llvm/Support/MathExtras.h"
42 #include "llvm/Support/Mutex.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "llvm/Target/TargetInstrInfo.h"
45 #include "llvm/Target/TargetIntrinsicInfo.h"
46 #include "llvm/Target/TargetLowering.h"
47 #include "llvm/Target/TargetMachine.h"
48 #include "llvm/Target/TargetOptions.h"
49 #include "llvm/Target/TargetRegisterInfo.h"
50 #include "llvm/Target/TargetSelectionDAGInfo.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 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 if (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 if (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 unsigned i = 0, e = N->getNumOperands();
154 // Skip over all of the undef values.
155 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept an all-undef vector.
159 if (i == e) return false;
161 // Do not accept build_vectors that aren't all constants or which have non-0
163 SDValue Zero = N->getOperand(i);
164 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
165 if (!CN->isNullValue())
167 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
168 if (!CFPN->getValueAPF().isPosZero())
173 // Okay, we have at least one 0 value, check to see if the rest match or are
175 for (++i; i != e; ++i)
176 if (N->getOperand(i) != Zero &&
177 N->getOperand(i).getOpcode() != ISD::UNDEF)
182 /// \brief Return true if the specified node is a BUILD_VECTOR node of
183 /// all ConstantSDNode or undef.
184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
185 if (N->getOpcode() != ISD::BUILD_VECTOR)
188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
189 SDValue Op = N->getOperand(i);
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// isScalarToVector - Return true if the specified node is a
199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
200 /// element is not an undef.
201 bool ISD::isScalarToVector(const SDNode *N) {
202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
205 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 unsigned NumElems = N->getNumOperands();
212 for (unsigned i = 1; i < NumElems; ++i) {
213 SDValue V = N->getOperand(i);
214 if (V.getOpcode() != ISD::UNDEF)
220 /// allOperandsUndef - Return true if the node has at least one operand
221 /// and all operands of the specified node are ISD::UNDEF.
222 bool ISD::allOperandsUndef(const SDNode *N) {
223 // Return false if the node has no operands.
224 // This is "logically inconsistent" with the definition of "all" but
225 // is probably the desired behavior.
226 if (N->getNumOperands() == 0)
229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
230 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
236 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
237 /// when given the operation for (X op Y).
238 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
239 // To perform this operation, we just need to swap the L and G bits of the
241 unsigned OldL = (Operation >> 2) & 1;
242 unsigned OldG = (Operation >> 1) & 1;
243 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
244 (OldL << 1) | // New G bit
245 (OldG << 2)); // New L bit.
248 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
249 /// 'op' is a valid SetCC operation.
250 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
251 unsigned Operation = Op;
253 Operation ^= 7; // Flip L, G, E bits, but not U.
255 Operation ^= 15; // Flip all of the condition bits.
257 if (Operation > ISD::SETTRUE2)
258 Operation &= ~8; // Don't let N and U bits get set.
260 return ISD::CondCode(Operation);
264 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
265 /// signed operation and 2 if the result is an unsigned comparison. Return zero
266 /// if the operation does not depend on the sign of the input (setne and seteq).
267 static int isSignedOp(ISD::CondCode Opcode) {
269 default: llvm_unreachable("Illegal integer setcc operation!");
271 case ISD::SETNE: return 0;
275 case ISD::SETGE: return 1;
279 case ISD::SETUGE: return 2;
283 /// getSetCCOrOperation - Return the result of a logical OR between different
284 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
285 /// returns SETCC_INVALID if it is not possible to represent the resultant
287 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
289 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
290 // Cannot fold a signed integer setcc with an unsigned integer setcc.
291 return ISD::SETCC_INVALID;
293 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
295 // If the N and U bits get set then the resultant comparison DOES suddenly
296 // care about orderedness, and is true when ordered.
297 if (Op > ISD::SETTRUE2)
298 Op &= ~16; // Clear the U bit if the N bit is set.
300 // Canonicalize illegal integer setcc's.
301 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
304 return ISD::CondCode(Op);
307 /// getSetCCAndOperation - Return the result of a logical AND between different
308 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
309 /// function returns zero if it is not possible to represent the resultant
311 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
313 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
314 // Cannot fold a signed setcc with an unsigned setcc.
315 return ISD::SETCC_INVALID;
317 // Combine all of the condition bits.
318 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
320 // Canonicalize illegal integer setcc's.
324 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
325 case ISD::SETOEQ: // SETEQ & SETU[LG]E
326 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
327 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
328 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
335 //===----------------------------------------------------------------------===//
336 // SDNode Profile Support
337 //===----------------------------------------------------------------------===//
339 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
341 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
345 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
346 /// solely with their pointer.
347 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
348 ID.AddPointer(VTList.VTs);
351 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
353 static void AddNodeIDOperands(FoldingSetNodeID &ID,
354 const SDValue *Ops, unsigned NumOps) {
355 for (; NumOps; --NumOps, ++Ops) {
356 ID.AddPointer(Ops->getNode());
357 ID.AddInteger(Ops->getResNo());
361 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
363 static void AddNodeIDOperands(FoldingSetNodeID &ID,
364 const SDUse *Ops, unsigned NumOps) {
365 for (; NumOps; --NumOps, ++Ops) {
366 ID.AddPointer(Ops->getNode());
367 ID.AddInteger(Ops->getResNo());
371 static void AddNodeIDNode(FoldingSetNodeID &ID,
372 unsigned short OpC, SDVTList VTList,
373 const SDValue *OpList, unsigned N) {
374 AddNodeIDOpcode(ID, OpC);
375 AddNodeIDValueTypes(ID, VTList);
376 AddNodeIDOperands(ID, OpList, N);
379 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
381 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
382 switch (N->getOpcode()) {
383 case ISD::TargetExternalSymbol:
384 case ISD::ExternalSymbol:
385 llvm_unreachable("Should only be used on nodes with operands");
386 default: break; // Normal nodes don't need extra info.
387 case ISD::TargetConstant:
389 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
391 case ISD::TargetConstantFP:
392 case ISD::ConstantFP: {
393 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
396 case ISD::TargetGlobalAddress:
397 case ISD::GlobalAddress:
398 case ISD::TargetGlobalTLSAddress:
399 case ISD::GlobalTLSAddress: {
400 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
401 ID.AddPointer(GA->getGlobal());
402 ID.AddInteger(GA->getOffset());
403 ID.AddInteger(GA->getTargetFlags());
404 ID.AddInteger(GA->getAddressSpace());
407 case ISD::BasicBlock:
408 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
411 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
413 case ISD::RegisterMask:
414 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
417 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
419 case ISD::FrameIndex:
420 case ISD::TargetFrameIndex:
421 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
424 case ISD::TargetJumpTable:
425 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
426 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
428 case ISD::ConstantPool:
429 case ISD::TargetConstantPool: {
430 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
431 ID.AddInteger(CP->getAlignment());
432 ID.AddInteger(CP->getOffset());
433 if (CP->isMachineConstantPoolEntry())
434 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
436 ID.AddPointer(CP->getConstVal());
437 ID.AddInteger(CP->getTargetFlags());
440 case ISD::TargetIndex: {
441 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
442 ID.AddInteger(TI->getIndex());
443 ID.AddInteger(TI->getOffset());
444 ID.AddInteger(TI->getTargetFlags());
448 const LoadSDNode *LD = cast<LoadSDNode>(N);
449 ID.AddInteger(LD->getMemoryVT().getRawBits());
450 ID.AddInteger(LD->getRawSubclassData());
451 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
455 const StoreSDNode *ST = cast<StoreSDNode>(N);
456 ID.AddInteger(ST->getMemoryVT().getRawBits());
457 ID.AddInteger(ST->getRawSubclassData());
458 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
461 case ISD::ATOMIC_CMP_SWAP:
462 case ISD::ATOMIC_SWAP:
463 case ISD::ATOMIC_LOAD_ADD:
464 case ISD::ATOMIC_LOAD_SUB:
465 case ISD::ATOMIC_LOAD_AND:
466 case ISD::ATOMIC_LOAD_OR:
467 case ISD::ATOMIC_LOAD_XOR:
468 case ISD::ATOMIC_LOAD_NAND:
469 case ISD::ATOMIC_LOAD_MIN:
470 case ISD::ATOMIC_LOAD_MAX:
471 case ISD::ATOMIC_LOAD_UMIN:
472 case ISD::ATOMIC_LOAD_UMAX:
473 case ISD::ATOMIC_LOAD:
474 case ISD::ATOMIC_STORE: {
475 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
476 ID.AddInteger(AT->getMemoryVT().getRawBits());
477 ID.AddInteger(AT->getRawSubclassData());
478 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
481 case ISD::PREFETCH: {
482 const MemSDNode *PF = cast<MemSDNode>(N);
483 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
486 case ISD::VECTOR_SHUFFLE: {
487 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
488 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
490 ID.AddInteger(SVN->getMaskElt(i));
493 case ISD::TargetBlockAddress:
494 case ISD::BlockAddress: {
495 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
496 ID.AddPointer(BA->getBlockAddress());
497 ID.AddInteger(BA->getOffset());
498 ID.AddInteger(BA->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 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
655 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
656 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
657 DbgVals[i]->setIsInvalidated();
660 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
661 /// correspond to it. This is useful when we're about to delete or repurpose
662 /// the node. We don't want future request for structurally identical nodes
663 /// to return N anymore.
664 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
666 switch (N->getOpcode()) {
667 case ISD::HANDLENODE: return false; // noop.
669 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
670 "Cond code doesn't exist!");
671 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
672 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
674 case ISD::ExternalSymbol:
675 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
677 case ISD::TargetExternalSymbol: {
678 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
679 Erased = TargetExternalSymbols.erase(
680 std::pair<std::string,unsigned char>(ESN->getSymbol(),
681 ESN->getTargetFlags()));
684 case ISD::VALUETYPE: {
685 EVT VT = cast<VTSDNode>(N)->getVT();
686 if (VT.isExtended()) {
687 Erased = ExtendedValueTypeNodes.erase(VT);
689 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
690 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
695 // Remove it from the CSE Map.
696 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
697 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
698 Erased = CSEMap.RemoveNode(N);
702 // Verify that the node was actually in one of the CSE maps, unless it has a
703 // flag result (which cannot be CSE'd) or is one of the special cases that are
704 // not subject to CSE.
705 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
706 !N->isMachineOpcode() && !doNotCSE(N)) {
709 llvm_unreachable("Node is not in map!");
715 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
716 /// maps and modified in place. Add it back to the CSE maps, unless an identical
717 /// node already exists, in which case transfer all its users to the existing
718 /// node. This transfer can potentially trigger recursive merging.
721 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
722 // For node types that aren't CSE'd, just act as if no identical node
725 SDNode *Existing = CSEMap.GetOrInsertNode(N);
727 // If there was already an existing matching node, use ReplaceAllUsesWith
728 // to replace the dead one with the existing one. This can cause
729 // recursive merging of other unrelated nodes down the line.
730 ReplaceAllUsesWith(N, Existing);
732 // N is now dead. Inform the listeners and delete it.
733 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
734 DUL->NodeDeleted(N, Existing);
735 DeleteNodeNotInCSEMaps(N);
740 // If the node doesn't already exist, we updated it. Inform listeners.
741 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
745 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
746 /// were replaced with those specified. If this node is never memoized,
747 /// return null, otherwise return a pointer to the slot it would take. If a
748 /// node already exists with these operands, the slot will be non-null.
749 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
754 SDValue Ops[] = { Op };
756 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
757 AddNodeIDCustom(ID, N);
758 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
762 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
763 /// were replaced with those specified. If this node is never memoized,
764 /// return null, otherwise return a pointer to the slot it would take. If a
765 /// node already exists with these operands, the slot will be non-null.
766 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
767 SDValue Op1, SDValue Op2,
772 SDValue Ops[] = { Op1, Op2 };
774 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
775 AddNodeIDCustom(ID, N);
776 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
781 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
782 /// were replaced with those specified. If this node is never memoized,
783 /// return null, otherwise return a pointer to the slot it would take. If a
784 /// node already exists with these operands, the slot will be non-null.
785 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
786 const SDValue *Ops,unsigned NumOps,
792 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
793 AddNodeIDCustom(ID, N);
794 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
799 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
800 static void VerifyNodeCommon(SDNode *N) {
801 switch (N->getOpcode()) {
804 case ISD::BUILD_PAIR: {
805 EVT VT = N->getValueType(0);
806 assert(N->getNumValues() == 1 && "Too many results!");
807 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
808 "Wrong return type!");
809 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
810 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
811 "Mismatched operand types!");
812 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
813 "Wrong operand type!");
814 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
815 "Wrong return type size");
818 case ISD::BUILD_VECTOR: {
819 assert(N->getNumValues() == 1 && "Too many results!");
820 assert(N->getValueType(0).isVector() && "Wrong return type!");
821 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
822 "Wrong number of operands!");
823 EVT EltVT = N->getValueType(0).getVectorElementType();
824 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
825 assert((I->getValueType() == EltVT ||
826 (EltVT.isInteger() && I->getValueType().isInteger() &&
827 EltVT.bitsLE(I->getValueType()))) &&
828 "Wrong operand type!");
829 assert(I->getValueType() == N->getOperand(0).getValueType() &&
830 "Operands must all have the same type");
837 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
838 static void VerifySDNode(SDNode *N) {
839 // The SDNode allocators cannot be used to allocate nodes with fields that are
840 // not present in an SDNode!
841 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
842 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
843 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
844 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
845 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
846 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
847 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
848 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
849 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
850 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
851 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
852 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
853 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
854 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
855 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
856 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
857 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
858 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
859 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
864 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
866 static void VerifyMachineNode(SDNode *N) {
867 // The MachineNode allocators cannot be used to allocate nodes with fields
868 // that are not present in a MachineNode!
869 // Currently there are no such nodes.
875 /// getEVTAlignment - Compute the default alignment value for the
878 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
879 Type *Ty = VT == MVT::iPTR ?
880 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
881 VT.getTypeForEVT(*getContext());
883 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
886 // EntryNode could meaningfully have debug info if we can find it...
887 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
888 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TTI(0), TLI(0), OptLevel(OL),
889 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
890 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
892 AllNodes.push_back(&EntryNode);
893 DbgInfo = new SDDbgInfo();
896 void SelectionDAG::init(MachineFunction &mf, const TargetTransformInfo *tti,
897 const TargetLowering *tli) {
901 Context = &mf.getFunction()->getContext();
904 SelectionDAG::~SelectionDAG() {
905 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
910 void SelectionDAG::allnodes_clear() {
911 assert(&*AllNodes.begin() == &EntryNode);
912 AllNodes.remove(AllNodes.begin());
913 while (!AllNodes.empty())
914 DeallocateNode(AllNodes.begin());
917 void SelectionDAG::clear() {
919 OperandAllocator.Reset();
922 ExtendedValueTypeNodes.clear();
923 ExternalSymbols.clear();
924 TargetExternalSymbols.clear();
925 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
926 static_cast<CondCodeSDNode*>(0));
927 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
928 static_cast<SDNode*>(0));
930 EntryNode.UseList = 0;
931 AllNodes.push_back(&EntryNode);
932 Root = getEntryNode();
936 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
937 return VT.bitsGT(Op.getValueType()) ?
938 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
939 getNode(ISD::TRUNCATE, DL, VT, Op);
942 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
943 return VT.bitsGT(Op.getValueType()) ?
944 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
945 getNode(ISD::TRUNCATE, DL, VT, Op);
948 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
949 return VT.bitsGT(Op.getValueType()) ?
950 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
951 getNode(ISD::TRUNCATE, DL, VT, Op);
954 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
955 assert(!VT.isVector() &&
956 "getZeroExtendInReg should use the vector element type instead of "
958 if (Op.getValueType() == VT) return Op;
959 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
960 APInt Imm = APInt::getLowBitsSet(BitWidth,
962 return getNode(ISD::AND, DL, Op.getValueType(), Op,
963 getConstant(Imm, Op.getValueType()));
966 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
968 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
969 EVT EltVT = VT.getScalarType();
971 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
972 return getNode(ISD::XOR, DL, VT, Val, NegOne);
975 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
976 EVT EltVT = VT.getScalarType();
977 assert((EltVT.getSizeInBits() >= 64 ||
978 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
979 "getConstant with a uint64_t value that doesn't fit in the type!");
980 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
983 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
984 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
987 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
988 assert(VT.isInteger() && "Cannot create FP integer constant!");
990 EVT EltVT = VT.getScalarType();
991 const ConstantInt *Elt = &Val;
993 const TargetLowering *TLI = TM.getTargetLowering();
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);
1005 // In other cases the element type is illegal and needs to be expanded, for
1006 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1007 // the value into n parts and use a vector type with n-times the elements.
1008 // Then bitcast to the type requested.
1009 // Legalizing constants too early makes the DAGCombiner's job harder so we
1010 // only legalize if the DAG tells us we must produce legal types.
1011 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1012 TLI->getTypeAction(*getContext(), EltVT) ==
1013 TargetLowering::TypeExpandInteger) {
1014 APInt NewVal = Elt->getValue();
1015 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1016 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1017 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1018 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1020 // Check the temporary vector is the correct size. If this fails then
1021 // getTypeToTransformTo() probably returned a type whose size (in bits)
1022 // isn't a power-of-2 factor of the requested type size.
1023 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1025 SmallVector<SDValue, 2> EltParts;
1026 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1027 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1028 .trunc(ViaEltSizeInBits),
1032 // EltParts is currently in little endian order. If we actually want
1033 // big-endian order then reverse it now.
1034 if (TLI->isBigEndian())
1035 std::reverse(EltParts.begin(), EltParts.end());
1037 // The elements must be reversed when the element order is different
1038 // to the endianness of the elements (because the BITCAST is itself a
1039 // vector shuffle in this situation). However, we do not need any code to
1040 // perform this reversal because getConstant() is producing a vector
1042 // This situation occurs in MIPS MSA.
1044 SmallVector<SDValue, 8> Ops;
1045 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1046 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1048 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1049 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1050 &Ops[0], Ops.size()));
1054 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1055 "APInt size does not match type size!");
1056 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1057 FoldingSetNodeID ID;
1058 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1062 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1064 return SDValue(N, 0);
1067 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
1068 CSEMap.InsertNode(N, IP);
1069 AllNodes.push_back(N);
1072 SDValue Result(N, 0);
1073 if (VT.isVector()) {
1074 SmallVector<SDValue, 8> Ops;
1075 Ops.assign(VT.getVectorNumElements(), Result);
1076 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1081 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1082 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1086 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1087 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1090 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1091 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1093 EVT EltVT = VT.getScalarType();
1095 // Do the map lookup using the actual bit pattern for the floating point
1096 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1097 // we don't have issues with SNANs.
1098 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1099 FoldingSetNodeID ID;
1100 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1104 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1106 return SDValue(N, 0);
1109 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1110 CSEMap.InsertNode(N, IP);
1111 AllNodes.push_back(N);
1114 SDValue Result(N, 0);
1115 if (VT.isVector()) {
1116 SmallVector<SDValue, 8> Ops;
1117 Ops.assign(VT.getVectorNumElements(), Result);
1118 // FIXME SDLoc info might be appropriate here
1119 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1124 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1125 EVT EltVT = VT.getScalarType();
1126 if (EltVT==MVT::f32)
1127 return getConstantFP(APFloat((float)Val), VT, isTarget);
1128 else if (EltVT==MVT::f64)
1129 return getConstantFP(APFloat(Val), VT, isTarget);
1130 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1133 APFloat apf = APFloat(Val);
1134 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1136 return getConstantFP(apf, VT, isTarget);
1138 llvm_unreachable("Unsupported type in getConstantFP");
1141 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1142 EVT VT, int64_t Offset,
1144 unsigned char TargetFlags) {
1145 assert((TargetFlags == 0 || isTargetGA) &&
1146 "Cannot set target flags on target-independent globals");
1147 const TargetLowering *TLI = TM.getTargetLowering();
1149 // Truncate (with sign-extension) the offset value to the pointer size.
1150 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1152 Offset = SignExtend64(Offset, BitWidth);
1154 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1156 // If GV is an alias then use the aliasee for determining thread-localness.
1157 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1158 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1162 if (GVar && GVar->isThreadLocal())
1163 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1165 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1167 FoldingSetNodeID ID;
1168 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1170 ID.AddInteger(Offset);
1171 ID.AddInteger(TargetFlags);
1172 ID.AddInteger(GV->getType()->getAddressSpace());
1174 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1175 return SDValue(E, 0);
1177 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1178 DL.getDebugLoc(), GV, VT,
1179 Offset, TargetFlags);
1180 CSEMap.InsertNode(N, IP);
1181 AllNodes.push_back(N);
1182 return SDValue(N, 0);
1185 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1186 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1187 FoldingSetNodeID ID;
1188 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1191 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1192 return SDValue(E, 0);
1194 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1195 CSEMap.InsertNode(N, IP);
1196 AllNodes.push_back(N);
1197 return SDValue(N, 0);
1200 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1201 unsigned char TargetFlags) {
1202 assert((TargetFlags == 0 || isTarget) &&
1203 "Cannot set target flags on target-independent jump tables");
1204 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1205 FoldingSetNodeID ID;
1206 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1208 ID.AddInteger(TargetFlags);
1210 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1211 return SDValue(E, 0);
1213 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1215 CSEMap.InsertNode(N, IP);
1216 AllNodes.push_back(N);
1217 return SDValue(N, 0);
1220 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1221 unsigned Alignment, int Offset,
1223 unsigned char TargetFlags) {
1224 assert((TargetFlags == 0 || isTarget) &&
1225 "Cannot set target flags on target-independent globals");
1228 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1229 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1230 FoldingSetNodeID ID;
1231 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1232 ID.AddInteger(Alignment);
1233 ID.AddInteger(Offset);
1235 ID.AddInteger(TargetFlags);
1237 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1238 return SDValue(E, 0);
1240 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1241 Alignment, TargetFlags);
1242 CSEMap.InsertNode(N, IP);
1243 AllNodes.push_back(N);
1244 return SDValue(N, 0);
1248 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1249 unsigned Alignment, int Offset,
1251 unsigned char TargetFlags) {
1252 assert((TargetFlags == 0 || isTarget) &&
1253 "Cannot set target flags on target-independent globals");
1256 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1257 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1258 FoldingSetNodeID ID;
1259 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1260 ID.AddInteger(Alignment);
1261 ID.AddInteger(Offset);
1262 C->addSelectionDAGCSEId(ID);
1263 ID.AddInteger(TargetFlags);
1265 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1266 return SDValue(E, 0);
1268 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1269 Alignment, TargetFlags);
1270 CSEMap.InsertNode(N, IP);
1271 AllNodes.push_back(N);
1272 return SDValue(N, 0);
1275 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1276 unsigned char TargetFlags) {
1277 FoldingSetNodeID ID;
1278 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1279 ID.AddInteger(Index);
1280 ID.AddInteger(Offset);
1281 ID.AddInteger(TargetFlags);
1283 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1284 return SDValue(E, 0);
1286 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1288 CSEMap.InsertNode(N, IP);
1289 AllNodes.push_back(N);
1290 return SDValue(N, 0);
1293 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1294 FoldingSetNodeID ID;
1295 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1298 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1299 return SDValue(E, 0);
1301 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1302 CSEMap.InsertNode(N, IP);
1303 AllNodes.push_back(N);
1304 return SDValue(N, 0);
1307 SDValue SelectionDAG::getValueType(EVT VT) {
1308 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1309 ValueTypeNodes.size())
1310 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1312 SDNode *&N = VT.isExtended() ?
1313 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1315 if (N) return SDValue(N, 0);
1316 N = new (NodeAllocator) VTSDNode(VT);
1317 AllNodes.push_back(N);
1318 return SDValue(N, 0);
1321 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1322 SDNode *&N = ExternalSymbols[Sym];
1323 if (N) return SDValue(N, 0);
1324 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1325 AllNodes.push_back(N);
1326 return SDValue(N, 0);
1329 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1330 unsigned char TargetFlags) {
1332 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1334 if (N) return SDValue(N, 0);
1335 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1336 AllNodes.push_back(N);
1337 return SDValue(N, 0);
1340 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1341 if ((unsigned)Cond >= CondCodeNodes.size())
1342 CondCodeNodes.resize(Cond+1);
1344 if (CondCodeNodes[Cond] == 0) {
1345 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1346 CondCodeNodes[Cond] = N;
1347 AllNodes.push_back(N);
1350 return SDValue(CondCodeNodes[Cond], 0);
1353 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1354 // the shuffle mask M that point at N1 to point at N2, and indices that point
1355 // N2 to point at N1.
1356 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1358 int NElts = M.size();
1359 for (int i = 0; i != NElts; ++i) {
1367 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1368 SDValue N2, const int *Mask) {
1369 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1370 "Invalid VECTOR_SHUFFLE");
1372 // Canonicalize shuffle undef, undef -> undef
1373 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1374 return getUNDEF(VT);
1376 // Validate that all indices in Mask are within the range of the elements
1377 // input to the shuffle.
1378 unsigned NElts = VT.getVectorNumElements();
1379 SmallVector<int, 8> MaskVec;
1380 for (unsigned i = 0; i != NElts; ++i) {
1381 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1382 MaskVec.push_back(Mask[i]);
1385 // Canonicalize shuffle v, v -> v, undef
1388 for (unsigned i = 0; i != NElts; ++i)
1389 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1392 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1393 if (N1.getOpcode() == ISD::UNDEF)
1394 commuteShuffle(N1, N2, MaskVec);
1396 // Canonicalize all index into lhs, -> shuffle lhs, undef
1397 // Canonicalize all index into rhs, -> shuffle rhs, undef
1398 bool AllLHS = true, AllRHS = true;
1399 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1400 for (unsigned i = 0; i != NElts; ++i) {
1401 if (MaskVec[i] >= (int)NElts) {
1406 } else if (MaskVec[i] >= 0) {
1410 if (AllLHS && AllRHS)
1411 return getUNDEF(VT);
1412 if (AllLHS && !N2Undef)
1416 commuteShuffle(N1, N2, MaskVec);
1419 // If Identity shuffle return that node.
1420 bool Identity = true;
1421 for (unsigned i = 0; i != NElts; ++i) {
1422 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1424 if (Identity && NElts)
1427 FoldingSetNodeID ID;
1428 SDValue Ops[2] = { N1, N2 };
1429 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1430 for (unsigned i = 0; i != NElts; ++i)
1431 ID.AddInteger(MaskVec[i]);
1434 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1435 return SDValue(E, 0);
1437 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1438 // SDNode doesn't have access to it. This memory will be "leaked" when
1439 // the node is deallocated, but recovered when the NodeAllocator is released.
1440 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1441 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1443 ShuffleVectorSDNode *N =
1444 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1445 dl.getDebugLoc(), N1, N2,
1447 CSEMap.InsertNode(N, IP);
1448 AllNodes.push_back(N);
1449 return SDValue(N, 0);
1452 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1453 SDValue Val, SDValue DTy,
1454 SDValue STy, SDValue Rnd, SDValue Sat,
1455 ISD::CvtCode Code) {
1456 // If the src and dest types are the same and the conversion is between
1457 // integer types of the same sign or two floats, no conversion is necessary.
1459 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1462 FoldingSetNodeID ID;
1463 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1464 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1466 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1467 return SDValue(E, 0);
1469 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1472 CSEMap.InsertNode(N, IP);
1473 AllNodes.push_back(N);
1474 return SDValue(N, 0);
1477 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1478 FoldingSetNodeID ID;
1479 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1480 ID.AddInteger(RegNo);
1482 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1483 return SDValue(E, 0);
1485 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1486 CSEMap.InsertNode(N, IP);
1487 AllNodes.push_back(N);
1488 return SDValue(N, 0);
1491 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1492 FoldingSetNodeID ID;
1493 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1494 ID.AddPointer(RegMask);
1496 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1497 return SDValue(E, 0);
1499 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1500 CSEMap.InsertNode(N, IP);
1501 AllNodes.push_back(N);
1502 return SDValue(N, 0);
1505 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1506 FoldingSetNodeID ID;
1507 SDValue Ops[] = { Root };
1508 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1509 ID.AddPointer(Label);
1511 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1512 return SDValue(E, 0);
1514 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1515 dl.getDebugLoc(), Root, Label);
1516 CSEMap.InsertNode(N, IP);
1517 AllNodes.push_back(N);
1518 return SDValue(N, 0);
1522 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1525 unsigned char TargetFlags) {
1526 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1528 FoldingSetNodeID ID;
1529 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1531 ID.AddInteger(Offset);
1532 ID.AddInteger(TargetFlags);
1534 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1535 return SDValue(E, 0);
1537 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1539 CSEMap.InsertNode(N, IP);
1540 AllNodes.push_back(N);
1541 return SDValue(N, 0);
1544 SDValue SelectionDAG::getSrcValue(const Value *V) {
1545 assert((!V || V->getType()->isPointerTy()) &&
1546 "SrcValue is not a pointer?");
1548 FoldingSetNodeID ID;
1549 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1553 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1554 return SDValue(E, 0);
1556 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1557 CSEMap.InsertNode(N, IP);
1558 AllNodes.push_back(N);
1559 return SDValue(N, 0);
1562 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1563 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1564 FoldingSetNodeID ID;
1565 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1569 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1570 return SDValue(E, 0);
1572 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1573 CSEMap.InsertNode(N, IP);
1574 AllNodes.push_back(N);
1575 return SDValue(N, 0);
1578 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1579 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1580 unsigned SrcAS, unsigned DestAS) {
1581 SDValue Ops[] = {Ptr};
1582 FoldingSetNodeID ID;
1583 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1584 ID.AddInteger(SrcAS);
1585 ID.AddInteger(DestAS);
1588 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1589 return SDValue(E, 0);
1591 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1593 VT, Ptr, SrcAS, DestAS);
1594 CSEMap.InsertNode(N, IP);
1595 AllNodes.push_back(N);
1596 return SDValue(N, 0);
1599 /// getShiftAmountOperand - Return the specified value casted to
1600 /// the target's desired shift amount type.
1601 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1602 EVT OpTy = Op.getValueType();
1603 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1604 if (OpTy == ShTy || OpTy.isVector()) return Op;
1606 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1607 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1610 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1611 /// specified value type.
1612 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1613 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1614 unsigned ByteSize = VT.getStoreSize();
1615 Type *Ty = VT.getTypeForEVT(*getContext());
1616 const TargetLowering *TLI = TM.getTargetLowering();
1617 unsigned StackAlign =
1618 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1620 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1621 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1624 /// CreateStackTemporary - Create a stack temporary suitable for holding
1625 /// either of the specified value types.
1626 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1627 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1628 VT2.getStoreSizeInBits())/8;
1629 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1630 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1631 const TargetLowering *TLI = TM.getTargetLowering();
1632 const DataLayout *TD = TLI->getDataLayout();
1633 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1634 TD->getPrefTypeAlignment(Ty2));
1636 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1637 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1638 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1641 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1642 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1643 // These setcc operations always fold.
1647 case ISD::SETFALSE2: return getConstant(0, VT);
1649 case ISD::SETTRUE2: {
1650 const TargetLowering *TLI = TM.getTargetLowering();
1651 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1653 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1666 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1670 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1671 const APInt &C2 = N2C->getAPIntValue();
1672 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1673 const APInt &C1 = N1C->getAPIntValue();
1676 default: llvm_unreachable("Unknown integer setcc!");
1677 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1678 case ISD::SETNE: return getConstant(C1 != C2, VT);
1679 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1680 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1681 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1682 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1683 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1684 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1685 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1686 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1690 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1691 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1692 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1695 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1696 return getUNDEF(VT);
1698 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1699 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1700 return getUNDEF(VT);
1702 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1703 R==APFloat::cmpLessThan, VT);
1704 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1705 return getUNDEF(VT);
1707 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1708 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1709 return getUNDEF(VT);
1711 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1712 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1713 return getUNDEF(VT);
1715 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1716 R==APFloat::cmpEqual, VT);
1717 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1718 return getUNDEF(VT);
1720 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1721 R==APFloat::cmpEqual, VT);
1722 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1723 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1724 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1725 R==APFloat::cmpEqual, VT);
1726 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1727 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1728 R==APFloat::cmpLessThan, VT);
1729 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1730 R==APFloat::cmpUnordered, VT);
1731 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1732 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1735 // Ensure that the constant occurs on the RHS.
1736 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1737 MVT CompVT = N1.getValueType().getSimpleVT();
1738 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1741 return getSetCC(dl, VT, N2, N1, SwappedCond);
1745 // Could not fold it.
1749 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1750 /// use this predicate to simplify operations downstream.
1751 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1752 // This predicate is not safe for vector operations.
1753 if (Op.getValueType().isVector())
1756 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1757 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1760 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1761 /// this predicate to simplify operations downstream. Mask is known to be zero
1762 /// for bits that V cannot have.
1763 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1764 unsigned Depth) const {
1765 APInt KnownZero, KnownOne;
1766 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1767 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1768 return (KnownZero & Mask) == Mask;
1771 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1772 /// known to be either zero or one and return them in the KnownZero/KnownOne
1773 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1775 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1776 APInt &KnownOne, unsigned Depth) const {
1777 const TargetLowering *TLI = TM.getTargetLowering();
1778 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1780 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1782 return; // Limit search depth.
1784 APInt KnownZero2, KnownOne2;
1786 switch (Op.getOpcode()) {
1788 // We know all of the bits for a constant!
1789 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1790 KnownZero = ~KnownOne;
1793 // If either the LHS or the RHS are Zero, the result is zero.
1794 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1795 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1796 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1797 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1799 // Output known-1 bits are only known if set in both the LHS & RHS.
1800 KnownOne &= KnownOne2;
1801 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1802 KnownZero |= KnownZero2;
1805 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1806 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1807 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1808 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1810 // Output known-0 bits are only known if clear in both the LHS & RHS.
1811 KnownZero &= KnownZero2;
1812 // Output known-1 are known to be set if set in either the LHS | RHS.
1813 KnownOne |= KnownOne2;
1816 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1817 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1818 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1819 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1821 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1822 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1823 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1824 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1825 KnownZero = KnownZeroOut;
1829 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1830 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1831 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1832 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1834 // If low bits are zero in either operand, output low known-0 bits.
1835 // Also compute a conserative estimate for high known-0 bits.
1836 // More trickiness is possible, but this is sufficient for the
1837 // interesting case of alignment computation.
1838 KnownOne.clearAllBits();
1839 unsigned TrailZ = KnownZero.countTrailingOnes() +
1840 KnownZero2.countTrailingOnes();
1841 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1842 KnownZero2.countLeadingOnes(),
1843 BitWidth) - BitWidth;
1845 TrailZ = std::min(TrailZ, BitWidth);
1846 LeadZ = std::min(LeadZ, BitWidth);
1847 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1848 APInt::getHighBitsSet(BitWidth, LeadZ);
1852 // For the purposes of computing leading zeros we can conservatively
1853 // treat a udiv as a logical right shift by the power of 2 known to
1854 // be less than the denominator.
1855 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1856 unsigned LeadZ = KnownZero2.countLeadingOnes();
1858 KnownOne2.clearAllBits();
1859 KnownZero2.clearAllBits();
1860 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1861 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1862 if (RHSUnknownLeadingOnes != BitWidth)
1863 LeadZ = std::min(BitWidth,
1864 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1866 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1870 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1871 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1872 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1873 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1875 // Only known if known in both the LHS and RHS.
1876 KnownOne &= KnownOne2;
1877 KnownZero &= KnownZero2;
1879 case ISD::SELECT_CC:
1880 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1881 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1882 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1883 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1885 // Only known if known in both the LHS and RHS.
1886 KnownOne &= KnownOne2;
1887 KnownZero &= KnownZero2;
1895 if (Op.getResNo() != 1)
1897 // The boolean result conforms to getBooleanContents. Fall through.
1899 // If we know the result of a setcc has the top bits zero, use this info.
1900 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1901 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1902 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1905 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1906 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1907 unsigned ShAmt = SA->getZExtValue();
1909 // If the shift count is an invalid immediate, don't do anything.
1910 if (ShAmt >= BitWidth)
1913 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1914 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1915 KnownZero <<= ShAmt;
1917 // low bits known zero.
1918 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1922 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1923 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1924 unsigned ShAmt = SA->getZExtValue();
1926 // If the shift count is an invalid immediate, don't do anything.
1927 if (ShAmt >= BitWidth)
1930 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1931 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1932 KnownZero = KnownZero.lshr(ShAmt);
1933 KnownOne = KnownOne.lshr(ShAmt);
1935 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1936 KnownZero |= HighBits; // High bits known zero.
1940 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1941 unsigned ShAmt = SA->getZExtValue();
1943 // If the shift count is an invalid immediate, don't do anything.
1944 if (ShAmt >= BitWidth)
1947 // If any of the demanded bits are produced by the sign extension, we also
1948 // demand the input sign bit.
1949 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1951 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1952 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1953 KnownZero = KnownZero.lshr(ShAmt);
1954 KnownOne = KnownOne.lshr(ShAmt);
1956 // Handle the sign bits.
1957 APInt SignBit = APInt::getSignBit(BitWidth);
1958 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1960 if (KnownZero.intersects(SignBit)) {
1961 KnownZero |= HighBits; // New bits are known zero.
1962 } else if (KnownOne.intersects(SignBit)) {
1963 KnownOne |= HighBits; // New bits are known one.
1967 case ISD::SIGN_EXTEND_INREG: {
1968 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1969 unsigned EBits = EVT.getScalarType().getSizeInBits();
1971 // Sign extension. Compute the demanded bits in the result that are not
1972 // present in the input.
1973 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1975 APInt InSignBit = APInt::getSignBit(EBits);
1976 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1978 // If the sign extended bits are demanded, we know that the sign
1980 InSignBit = InSignBit.zext(BitWidth);
1981 if (NewBits.getBoolValue())
1982 InputDemandedBits |= InSignBit;
1984 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1985 KnownOne &= InputDemandedBits;
1986 KnownZero &= InputDemandedBits;
1987 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1989 // If the sign bit of the input is known set or clear, then we know the
1990 // top bits of the result.
1991 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1992 KnownZero |= NewBits;
1993 KnownOne &= ~NewBits;
1994 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1995 KnownOne |= NewBits;
1996 KnownZero &= ~NewBits;
1997 } else { // Input sign bit unknown
1998 KnownZero &= ~NewBits;
1999 KnownOne &= ~NewBits;
2004 case ISD::CTTZ_ZERO_UNDEF:
2006 case ISD::CTLZ_ZERO_UNDEF:
2008 unsigned LowBits = Log2_32(BitWidth)+1;
2009 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2010 KnownOne.clearAllBits();
2014 LoadSDNode *LD = cast<LoadSDNode>(Op);
2015 // If this is a ZEXTLoad and we are looking at the loaded value.
2016 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2017 EVT VT = LD->getMemoryVT();
2018 unsigned MemBits = VT.getScalarType().getSizeInBits();
2019 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2020 } else if (const MDNode *Ranges = LD->getRanges()) {
2021 computeMaskedBitsLoad(*Ranges, KnownZero);
2025 case ISD::ZERO_EXTEND: {
2026 EVT InVT = Op.getOperand(0).getValueType();
2027 unsigned InBits = InVT.getScalarType().getSizeInBits();
2028 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2029 KnownZero = KnownZero.trunc(InBits);
2030 KnownOne = KnownOne.trunc(InBits);
2031 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2032 KnownZero = KnownZero.zext(BitWidth);
2033 KnownOne = KnownOne.zext(BitWidth);
2034 KnownZero |= NewBits;
2037 case ISD::SIGN_EXTEND: {
2038 EVT InVT = Op.getOperand(0).getValueType();
2039 unsigned InBits = InVT.getScalarType().getSizeInBits();
2040 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2042 KnownZero = KnownZero.trunc(InBits);
2043 KnownOne = KnownOne.trunc(InBits);
2044 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2046 // Note if the sign bit is known to be zero or one.
2047 bool SignBitKnownZero = KnownZero.isNegative();
2048 bool SignBitKnownOne = KnownOne.isNegative();
2049 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2050 "Sign bit can't be known to be both zero and one!");
2052 KnownZero = KnownZero.zext(BitWidth);
2053 KnownOne = KnownOne.zext(BitWidth);
2055 // If the sign bit is known zero or one, the top bits match.
2056 if (SignBitKnownZero)
2057 KnownZero |= NewBits;
2058 else if (SignBitKnownOne)
2059 KnownOne |= NewBits;
2062 case ISD::ANY_EXTEND: {
2063 EVT InVT = Op.getOperand(0).getValueType();
2064 unsigned InBits = InVT.getScalarType().getSizeInBits();
2065 KnownZero = KnownZero.trunc(InBits);
2066 KnownOne = KnownOne.trunc(InBits);
2067 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2068 KnownZero = KnownZero.zext(BitWidth);
2069 KnownOne = KnownOne.zext(BitWidth);
2072 case ISD::TRUNCATE: {
2073 EVT InVT = Op.getOperand(0).getValueType();
2074 unsigned InBits = InVT.getScalarType().getSizeInBits();
2075 KnownZero = KnownZero.zext(InBits);
2076 KnownOne = KnownOne.zext(InBits);
2077 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2078 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2079 KnownZero = KnownZero.trunc(BitWidth);
2080 KnownOne = KnownOne.trunc(BitWidth);
2083 case ISD::AssertZext: {
2084 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2085 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2086 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2087 KnownZero |= (~InMask);
2088 KnownOne &= (~KnownZero);
2092 // All bits are zero except the low bit.
2093 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2097 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2098 // We know that the top bits of C-X are clear if X contains less bits
2099 // than C (i.e. no wrap-around can happen). For example, 20-X is
2100 // positive if we can prove that X is >= 0 and < 16.
2101 if (CLHS->getAPIntValue().isNonNegative()) {
2102 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2103 // NLZ can't be BitWidth with no sign bit
2104 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2105 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2107 // If all of the MaskV bits are known to be zero, then we know the
2108 // output top bits are zero, because we now know that the output is
2110 if ((KnownZero2 & MaskV) == MaskV) {
2111 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2112 // Top bits known zero.
2113 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2121 // Output known-0 bits are known if clear or set in both the low clear bits
2122 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2123 // low 3 bits clear.
2124 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2125 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2126 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2128 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2129 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2130 KnownZeroOut = std::min(KnownZeroOut,
2131 KnownZero2.countTrailingOnes());
2133 if (Op.getOpcode() == ISD::ADD) {
2134 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2138 // With ADDE, a carry bit may be added in, so we can only use this
2139 // information if we know (at least) that the low two bits are clear. We
2140 // then return to the caller that the low bit is unknown but that other bits
2142 if (KnownZeroOut >= 2) // ADDE
2143 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2147 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2148 const APInt &RA = Rem->getAPIntValue().abs();
2149 if (RA.isPowerOf2()) {
2150 APInt LowBits = RA - 1;
2151 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2153 // The low bits of the first operand are unchanged by the srem.
2154 KnownZero = KnownZero2 & LowBits;
2155 KnownOne = KnownOne2 & LowBits;
2157 // If the first operand is non-negative or has all low bits zero, then
2158 // the upper bits are all zero.
2159 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2160 KnownZero |= ~LowBits;
2162 // If the first operand is negative and not all low bits are zero, then
2163 // the upper bits are all one.
2164 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2165 KnownOne |= ~LowBits;
2166 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2171 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2172 const APInt &RA = Rem->getAPIntValue();
2173 if (RA.isPowerOf2()) {
2174 APInt LowBits = (RA - 1);
2175 KnownZero |= ~LowBits;
2176 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2177 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2182 // Since the result is less than or equal to either operand, any leading
2183 // zero bits in either operand must also exist in the result.
2184 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2185 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2187 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2188 KnownZero2.countLeadingOnes());
2189 KnownOne.clearAllBits();
2190 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2193 case ISD::FrameIndex:
2194 case ISD::TargetFrameIndex:
2195 if (unsigned Align = InferPtrAlignment(Op)) {
2196 // The low bits are known zero if the pointer is aligned.
2197 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2203 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2206 case ISD::INTRINSIC_WO_CHAIN:
2207 case ISD::INTRINSIC_W_CHAIN:
2208 case ISD::INTRINSIC_VOID:
2209 // Allow the target to implement this method for its nodes.
2210 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2215 /// ComputeNumSignBits - Return the number of times the sign bit of the
2216 /// register is replicated into the other bits. We know that at least 1 bit
2217 /// is always equal to the sign bit (itself), but other cases can give us
2218 /// information. For example, immediately after an "SRA X, 2", we know that
2219 /// the top 3 bits are all equal to each other, so we return 3.
2220 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2221 const TargetLowering *TLI = TM.getTargetLowering();
2222 EVT VT = Op.getValueType();
2223 assert(VT.isInteger() && "Invalid VT!");
2224 unsigned VTBits = VT.getScalarType().getSizeInBits();
2226 unsigned FirstAnswer = 1;
2229 return 1; // Limit search depth.
2231 switch (Op.getOpcode()) {
2233 case ISD::AssertSext:
2234 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2235 return VTBits-Tmp+1;
2236 case ISD::AssertZext:
2237 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2240 case ISD::Constant: {
2241 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2242 return Val.getNumSignBits();
2245 case ISD::SIGN_EXTEND:
2247 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2248 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2250 case ISD::SIGN_EXTEND_INREG:
2251 // Max of the input and what this extends.
2253 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2256 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2257 return std::max(Tmp, Tmp2);
2260 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2261 // SRA X, C -> adds C sign bits.
2262 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2263 Tmp += C->getZExtValue();
2264 if (Tmp > VTBits) Tmp = VTBits;
2268 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2269 // shl destroys sign bits.
2270 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2271 if (C->getZExtValue() >= VTBits || // Bad shift.
2272 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2273 return Tmp - C->getZExtValue();
2278 case ISD::XOR: // NOT is handled here.
2279 // Logical binary ops preserve the number of sign bits at the worst.
2280 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2282 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2283 FirstAnswer = std::min(Tmp, Tmp2);
2284 // We computed what we know about the sign bits as our first
2285 // answer. Now proceed to the generic code that uses
2286 // ComputeMaskedBits, and pick whichever answer is better.
2291 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2292 if (Tmp == 1) return 1; // Early out.
2293 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2294 return std::min(Tmp, Tmp2);
2302 if (Op.getResNo() != 1)
2304 // The boolean result conforms to getBooleanContents. Fall through.
2306 // If setcc returns 0/-1, all bits are sign bits.
2307 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2308 TargetLowering::ZeroOrNegativeOneBooleanContent)
2313 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2314 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2316 // Handle rotate right by N like a rotate left by 32-N.
2317 if (Op.getOpcode() == ISD::ROTR)
2318 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2320 // If we aren't rotating out all of the known-in sign bits, return the
2321 // number that are left. This handles rotl(sext(x), 1) for example.
2322 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2323 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2327 // Add can have at most one carry bit. Thus we know that the output
2328 // is, at worst, one more bit than the inputs.
2329 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2330 if (Tmp == 1) return 1; // Early out.
2332 // Special case decrementing a value (ADD X, -1):
2333 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2334 if (CRHS->isAllOnesValue()) {
2335 APInt KnownZero, KnownOne;
2336 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2338 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2340 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2343 // If we are subtracting one from a positive number, there is no carry
2344 // out of the result.
2345 if (KnownZero.isNegative())
2349 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2350 if (Tmp2 == 1) return 1;
2351 return std::min(Tmp, Tmp2)-1;
2354 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2355 if (Tmp2 == 1) return 1;
2358 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2359 if (CLHS->isNullValue()) {
2360 APInt KnownZero, KnownOne;
2361 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2362 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2364 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2367 // If the input is known to be positive (the sign bit is known clear),
2368 // the output of the NEG has the same number of sign bits as the input.
2369 if (KnownZero.isNegative())
2372 // Otherwise, we treat this like a SUB.
2375 // Sub can have at most one carry bit. Thus we know that the output
2376 // is, at worst, one more bit than the inputs.
2377 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2378 if (Tmp == 1) return 1; // Early out.
2379 return std::min(Tmp, Tmp2)-1;
2381 // FIXME: it's tricky to do anything useful for this, but it is an important
2382 // case for targets like X86.
2386 // If we are looking at the loaded value of the SDNode.
2387 if (Op.getResNo() == 0) {
2388 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2389 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2390 unsigned ExtType = LD->getExtensionType();
2393 case ISD::SEXTLOAD: // '17' bits known
2394 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2395 return VTBits-Tmp+1;
2396 case ISD::ZEXTLOAD: // '16' bits known
2397 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2403 // Allow the target to implement this method for its nodes.
2404 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2405 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2406 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2407 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2408 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2409 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2412 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2413 // use this information.
2414 APInt KnownZero, KnownOne;
2415 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2418 if (KnownZero.isNegative()) { // sign bit is 0
2420 } else if (KnownOne.isNegative()) { // sign bit is 1;
2427 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2428 // the number of identical bits in the top of the input value.
2430 Mask <<= Mask.getBitWidth()-VTBits;
2431 // Return # leading zeros. We use 'min' here in case Val was zero before
2432 // shifting. We don't want to return '64' as for an i32 "0".
2433 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2436 /// isBaseWithConstantOffset - Return true if the specified operand is an
2437 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2438 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2439 /// semantics as an ADD. This handles the equivalence:
2440 /// X|Cst == X+Cst iff X&Cst = 0.
2441 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2442 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2443 !isa<ConstantSDNode>(Op.getOperand(1)))
2446 if (Op.getOpcode() == ISD::OR &&
2447 !MaskedValueIsZero(Op.getOperand(0),
2448 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2455 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2456 // If we're told that NaNs won't happen, assume they won't.
2457 if (getTarget().Options.NoNaNsFPMath)
2460 // If the value is a constant, we can obviously see if it is a NaN or not.
2461 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2462 return !C->getValueAPF().isNaN();
2464 // TODO: Recognize more cases here.
2469 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2470 // If the value is a constant, we can obviously see if it is a zero or not.
2471 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2472 return !C->isZero();
2474 // TODO: Recognize more cases here.
2475 switch (Op.getOpcode()) {
2478 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2479 return !C->isNullValue();
2486 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2487 // Check the obvious case.
2488 if (A == B) return true;
2490 // For for negative and positive zero.
2491 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2492 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2493 if (CA->isZero() && CB->isZero()) return true;
2495 // Otherwise they may not be equal.
2499 /// getNode - Gets or creates the specified node.
2501 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2502 FoldingSetNodeID ID;
2503 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2505 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2506 return SDValue(E, 0);
2508 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2509 DL.getDebugLoc(), getVTList(VT));
2510 CSEMap.InsertNode(N, IP);
2512 AllNodes.push_back(N);
2516 return SDValue(N, 0);
2519 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2520 EVT VT, SDValue Operand) {
2521 // Constant fold unary operations with an integer constant operand.
2522 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2523 const APInt &Val = C->getAPIntValue();
2526 case ISD::SIGN_EXTEND:
2527 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2528 case ISD::ANY_EXTEND:
2529 case ISD::ZERO_EXTEND:
2531 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2532 case ISD::UINT_TO_FP:
2533 case ISD::SINT_TO_FP: {
2534 APFloat apf(EVTToAPFloatSemantics(VT),
2535 APInt::getNullValue(VT.getSizeInBits()));
2536 (void)apf.convertFromAPInt(Val,
2537 Opcode==ISD::SINT_TO_FP,
2538 APFloat::rmNearestTiesToEven);
2539 return getConstantFP(apf, VT);
2542 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2543 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2544 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2545 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2548 return getConstant(Val.byteSwap(), VT);
2550 return getConstant(Val.countPopulation(), VT);
2552 case ISD::CTLZ_ZERO_UNDEF:
2553 return getConstant(Val.countLeadingZeros(), VT);
2555 case ISD::CTTZ_ZERO_UNDEF:
2556 return getConstant(Val.countTrailingZeros(), VT);
2560 // Constant fold unary operations with a floating point constant operand.
2561 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2562 APFloat V = C->getValueAPF(); // make copy
2566 return getConstantFP(V, VT);
2569 return getConstantFP(V, VT);
2571 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2572 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2573 return getConstantFP(V, VT);
2577 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2578 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2579 return getConstantFP(V, VT);
2583 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2584 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2585 return getConstantFP(V, VT);
2588 case ISD::FP_EXTEND: {
2590 // This can return overflow, underflow, or inexact; we don't care.
2591 // FIXME need to be more flexible about rounding mode.
2592 (void)V.convert(EVTToAPFloatSemantics(VT),
2593 APFloat::rmNearestTiesToEven, &ignored);
2594 return getConstantFP(V, VT);
2596 case ISD::FP_TO_SINT:
2597 case ISD::FP_TO_UINT: {
2600 assert(integerPartWidth >= 64);
2601 // FIXME need to be more flexible about rounding mode.
2602 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2603 Opcode==ISD::FP_TO_SINT,
2604 APFloat::rmTowardZero, &ignored);
2605 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2607 APInt api(VT.getSizeInBits(), x);
2608 return getConstant(api, VT);
2611 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2612 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2613 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2614 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2619 unsigned OpOpcode = Operand.getNode()->getOpcode();
2621 case ISD::TokenFactor:
2622 case ISD::MERGE_VALUES:
2623 case ISD::CONCAT_VECTORS:
2624 return Operand; // Factor, merge or concat of one node? No need.
2625 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2626 case ISD::FP_EXTEND:
2627 assert(VT.isFloatingPoint() &&
2628 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2629 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2630 assert((!VT.isVector() ||
2631 VT.getVectorNumElements() ==
2632 Operand.getValueType().getVectorNumElements()) &&
2633 "Vector element count mismatch!");
2634 if (Operand.getOpcode() == ISD::UNDEF)
2635 return getUNDEF(VT);
2637 case ISD::SIGN_EXTEND:
2638 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2639 "Invalid SIGN_EXTEND!");
2640 if (Operand.getValueType() == VT) return Operand; // noop extension
2641 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2642 "Invalid sext node, dst < src!");
2643 assert((!VT.isVector() ||
2644 VT.getVectorNumElements() ==
2645 Operand.getValueType().getVectorNumElements()) &&
2646 "Vector element count mismatch!");
2647 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2648 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2649 else if (OpOpcode == ISD::UNDEF)
2650 // sext(undef) = 0, because the top bits will all be the same.
2651 return getConstant(0, VT);
2653 case ISD::ZERO_EXTEND:
2654 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2655 "Invalid ZERO_EXTEND!");
2656 if (Operand.getValueType() == VT) return Operand; // noop extension
2657 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2658 "Invalid zext node, dst < src!");
2659 assert((!VT.isVector() ||
2660 VT.getVectorNumElements() ==
2661 Operand.getValueType().getVectorNumElements()) &&
2662 "Vector element count mismatch!");
2663 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2664 return getNode(ISD::ZERO_EXTEND, DL, VT,
2665 Operand.getNode()->getOperand(0));
2666 else if (OpOpcode == ISD::UNDEF)
2667 // zext(undef) = 0, because the top bits will be zero.
2668 return getConstant(0, VT);
2670 case ISD::ANY_EXTEND:
2671 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2672 "Invalid ANY_EXTEND!");
2673 if (Operand.getValueType() == VT) return Operand; // noop extension
2674 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2675 "Invalid anyext node, dst < src!");
2676 assert((!VT.isVector() ||
2677 VT.getVectorNumElements() ==
2678 Operand.getValueType().getVectorNumElements()) &&
2679 "Vector element count mismatch!");
2681 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2682 OpOpcode == ISD::ANY_EXTEND)
2683 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2684 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2685 else if (OpOpcode == ISD::UNDEF)
2686 return getUNDEF(VT);
2688 // (ext (trunx x)) -> x
2689 if (OpOpcode == ISD::TRUNCATE) {
2690 SDValue OpOp = Operand.getNode()->getOperand(0);
2691 if (OpOp.getValueType() == VT)
2696 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2697 "Invalid TRUNCATE!");
2698 if (Operand.getValueType() == VT) return Operand; // noop truncate
2699 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2700 "Invalid truncate node, src < dst!");
2701 assert((!VT.isVector() ||
2702 VT.getVectorNumElements() ==
2703 Operand.getValueType().getVectorNumElements()) &&
2704 "Vector element count mismatch!");
2705 if (OpOpcode == ISD::TRUNCATE)
2706 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2707 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2708 OpOpcode == ISD::ANY_EXTEND) {
2709 // If the source is smaller than the dest, we still need an extend.
2710 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2711 .bitsLT(VT.getScalarType()))
2712 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2713 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2714 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2715 return Operand.getNode()->getOperand(0);
2717 if (OpOpcode == ISD::UNDEF)
2718 return getUNDEF(VT);
2721 // Basic sanity checking.
2722 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2723 && "Cannot BITCAST between types of different sizes!");
2724 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2725 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2726 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2727 if (OpOpcode == ISD::UNDEF)
2728 return getUNDEF(VT);
2730 case ISD::SCALAR_TO_VECTOR:
2731 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2732 (VT.getVectorElementType() == Operand.getValueType() ||
2733 (VT.getVectorElementType().isInteger() &&
2734 Operand.getValueType().isInteger() &&
2735 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2736 "Illegal SCALAR_TO_VECTOR node!");
2737 if (OpOpcode == ISD::UNDEF)
2738 return getUNDEF(VT);
2739 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2740 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2741 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2742 Operand.getConstantOperandVal(1) == 0 &&
2743 Operand.getOperand(0).getValueType() == VT)
2744 return Operand.getOperand(0);
2747 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2748 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2749 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2750 Operand.getNode()->getOperand(0));
2751 if (OpOpcode == ISD::FNEG) // --X -> X
2752 return Operand.getNode()->getOperand(0);
2755 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2756 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2761 SDVTList VTs = getVTList(VT);
2762 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2763 FoldingSetNodeID ID;
2764 SDValue Ops[1] = { Operand };
2765 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2767 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2768 return SDValue(E, 0);
2770 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2771 DL.getDebugLoc(), VTs, Operand);
2772 CSEMap.InsertNode(N, IP);
2774 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2775 DL.getDebugLoc(), VTs, Operand);
2778 AllNodes.push_back(N);
2782 return SDValue(N, 0);
2785 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2786 SDNode *Cst1, SDNode *Cst2) {
2787 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2788 SmallVector<SDValue, 4> Outputs;
2789 EVT SVT = VT.getScalarType();
2791 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2792 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2793 if (Scalar1 && Scalar2) {
2794 // Scalar instruction.
2795 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2797 // For vectors extract each constant element into Inputs so we can constant
2798 // fold them individually.
2799 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2800 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2804 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2806 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2807 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2808 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2809 if (!V1 || !V2) // Not a constant, bail.
2812 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2813 // FIXME: This is valid and could be handled by truncating the APInts.
2814 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2817 Inputs.push_back(std::make_pair(V1, V2));
2821 // We have a number of constant values, constant fold them element by element.
2822 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2823 const APInt &C1 = Inputs[I].first->getAPIntValue();
2824 const APInt &C2 = Inputs[I].second->getAPIntValue();
2828 Outputs.push_back(getConstant(C1 + C2, SVT));
2831 Outputs.push_back(getConstant(C1 - C2, SVT));
2834 Outputs.push_back(getConstant(C1 * C2, SVT));
2837 if (!C2.getBoolValue())
2839 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2842 if (!C2.getBoolValue())
2844 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2847 if (!C2.getBoolValue())
2849 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2852 if (!C2.getBoolValue())
2854 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2857 Outputs.push_back(getConstant(C1 & C2, SVT));
2860 Outputs.push_back(getConstant(C1 | C2, SVT));
2863 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2866 Outputs.push_back(getConstant(C1 << C2, SVT));
2869 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2872 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2875 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2878 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2885 // Handle the scalar case first.
2886 if (Scalar1 && Scalar2)
2887 return Outputs.back();
2889 // Otherwise build a big vector out of the scalar elements we generated.
2890 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2894 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2896 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2897 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2900 case ISD::TokenFactor:
2901 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2902 N2.getValueType() == MVT::Other && "Invalid token factor!");
2903 // Fold trivial token factors.
2904 if (N1.getOpcode() == ISD::EntryToken) return N2;
2905 if (N2.getOpcode() == ISD::EntryToken) return N1;
2906 if (N1 == N2) return N1;
2908 case ISD::CONCAT_VECTORS:
2909 // Concat of UNDEFs is UNDEF.
2910 if (N1.getOpcode() == ISD::UNDEF &&
2911 N2.getOpcode() == ISD::UNDEF)
2912 return getUNDEF(VT);
2914 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2915 // one big BUILD_VECTOR.
2916 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2917 N2.getOpcode() == ISD::BUILD_VECTOR) {
2918 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2919 N1.getNode()->op_end());
2920 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2921 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2925 assert(VT.isInteger() && "This operator does not apply to FP types!");
2926 assert(N1.getValueType() == N2.getValueType() &&
2927 N1.getValueType() == VT && "Binary operator types must match!");
2928 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2929 // worth handling here.
2930 if (N2C && N2C->isNullValue())
2932 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2939 assert(VT.isInteger() && "This operator does not apply to FP types!");
2940 assert(N1.getValueType() == N2.getValueType() &&
2941 N1.getValueType() == VT && "Binary operator types must match!");
2942 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2943 // it's worth handling here.
2944 if (N2C && N2C->isNullValue())
2954 assert(VT.isInteger() && "This operator does not apply to FP types!");
2955 assert(N1.getValueType() == N2.getValueType() &&
2956 N1.getValueType() == VT && "Binary operator types must match!");
2963 if (getTarget().Options.UnsafeFPMath) {
2964 if (Opcode == ISD::FADD) {
2966 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2967 if (CFP->getValueAPF().isZero())
2970 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2971 if (CFP->getValueAPF().isZero())
2973 } else if (Opcode == ISD::FSUB) {
2975 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2976 if (CFP->getValueAPF().isZero())
2978 } else if (Opcode == ISD::FMUL) {
2979 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2982 // If the first operand isn't the constant, try the second
2984 CFP = dyn_cast<ConstantFPSDNode>(N2);
2991 return SDValue(CFP,0);
2993 if (CFP->isExactlyValue(1.0))
2998 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2999 assert(N1.getValueType() == N2.getValueType() &&
3000 N1.getValueType() == VT && "Binary operator types must match!");
3002 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3003 assert(N1.getValueType() == VT &&
3004 N1.getValueType().isFloatingPoint() &&
3005 N2.getValueType().isFloatingPoint() &&
3006 "Invalid FCOPYSIGN!");
3013 assert(VT == N1.getValueType() &&
3014 "Shift operators return type must be the same as their first arg");
3015 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3016 "Shifts only work on integers");
3017 assert((!VT.isVector() || VT == N2.getValueType()) &&
3018 "Vector shift amounts must be in the same as their first arg");
3019 // Verify that the shift amount VT is bit enough to hold valid shift
3020 // amounts. This catches things like trying to shift an i1024 value by an
3021 // i8, which is easy to fall into in generic code that uses
3022 // TLI.getShiftAmount().
3023 assert(N2.getValueType().getSizeInBits() >=
3024 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3025 "Invalid use of small shift amount with oversized value!");
3027 // Always fold shifts of i1 values so the code generator doesn't need to
3028 // handle them. Since we know the size of the shift has to be less than the
3029 // size of the value, the shift/rotate count is guaranteed to be zero.
3032 if (N2C && N2C->isNullValue())
3035 case ISD::FP_ROUND_INREG: {
3036 EVT EVT = cast<VTSDNode>(N2)->getVT();
3037 assert(VT == N1.getValueType() && "Not an inreg round!");
3038 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3039 "Cannot FP_ROUND_INREG integer types");
3040 assert(EVT.isVector() == VT.isVector() &&
3041 "FP_ROUND_INREG type should be vector iff the operand "
3043 assert((!EVT.isVector() ||
3044 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3045 "Vector element counts must match in FP_ROUND_INREG");
3046 assert(EVT.bitsLE(VT) && "Not rounding down!");
3048 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3052 assert(VT.isFloatingPoint() &&
3053 N1.getValueType().isFloatingPoint() &&
3054 VT.bitsLE(N1.getValueType()) &&
3055 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3056 if (N1.getValueType() == VT) return N1; // noop conversion.
3058 case ISD::AssertSext:
3059 case ISD::AssertZext: {
3060 EVT EVT = cast<VTSDNode>(N2)->getVT();
3061 assert(VT == N1.getValueType() && "Not an inreg extend!");
3062 assert(VT.isInteger() && EVT.isInteger() &&
3063 "Cannot *_EXTEND_INREG FP types");
3064 assert(!EVT.isVector() &&
3065 "AssertSExt/AssertZExt type should be the vector element type "
3066 "rather than the vector type!");
3067 assert(EVT.bitsLE(VT) && "Not extending!");
3068 if (VT == EVT) return N1; // noop assertion.
3071 case ISD::SIGN_EXTEND_INREG: {
3072 EVT EVT = cast<VTSDNode>(N2)->getVT();
3073 assert(VT == N1.getValueType() && "Not an inreg extend!");
3074 assert(VT.isInteger() && EVT.isInteger() &&
3075 "Cannot *_EXTEND_INREG FP types");
3076 assert(EVT.isVector() == VT.isVector() &&
3077 "SIGN_EXTEND_INREG type should be vector iff the operand "
3079 assert((!EVT.isVector() ||
3080 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3081 "Vector element counts must match in SIGN_EXTEND_INREG");
3082 assert(EVT.bitsLE(VT) && "Not extending!");
3083 if (EVT == VT) return N1; // Not actually extending
3086 APInt Val = N1C->getAPIntValue();
3087 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3088 Val <<= Val.getBitWidth()-FromBits;
3089 Val = Val.ashr(Val.getBitWidth()-FromBits);
3090 return getConstant(Val, VT);
3094 case ISD::EXTRACT_VECTOR_ELT:
3095 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3096 if (N1.getOpcode() == ISD::UNDEF)
3097 return getUNDEF(VT);
3099 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3100 // expanding copies of large vectors from registers.
3102 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3103 N1.getNumOperands() > 0) {
3105 N1.getOperand(0).getValueType().getVectorNumElements();
3106 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3107 N1.getOperand(N2C->getZExtValue() / Factor),
3108 getConstant(N2C->getZExtValue() % Factor,
3109 N2.getValueType()));
3112 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3113 // expanding large vector constants.
3114 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3115 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3117 if (VT != Elt.getValueType())
3118 // If the vector element type is not legal, the BUILD_VECTOR operands
3119 // are promoted and implicitly truncated, and the result implicitly
3120 // extended. Make that explicit here.
3121 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3126 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3127 // operations are lowered to scalars.
3128 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3129 // If the indices are the same, return the inserted element else
3130 // if the indices are known different, extract the element from
3131 // the original vector.
3132 SDValue N1Op2 = N1.getOperand(2);
3133 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3135 if (N1Op2C && N2C) {
3136 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3137 if (VT == N1.getOperand(1).getValueType())
3138 return N1.getOperand(1);
3140 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3143 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3147 case ISD::EXTRACT_ELEMENT:
3148 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3149 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3150 (N1.getValueType().isInteger() == VT.isInteger()) &&
3151 N1.getValueType() != VT &&
3152 "Wrong types for EXTRACT_ELEMENT!");
3154 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3155 // 64-bit integers into 32-bit parts. Instead of building the extract of
3156 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3157 if (N1.getOpcode() == ISD::BUILD_PAIR)
3158 return N1.getOperand(N2C->getZExtValue());
3160 // EXTRACT_ELEMENT of a constant int is also very common.
3161 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3162 unsigned ElementSize = VT.getSizeInBits();
3163 unsigned Shift = ElementSize * N2C->getZExtValue();
3164 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3165 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3168 case ISD::EXTRACT_SUBVECTOR: {
3170 if (VT.isSimple() && N1.getValueType().isSimple()) {
3171 assert(VT.isVector() && N1.getValueType().isVector() &&
3172 "Extract subvector VTs must be a vectors!");
3173 assert(VT.getVectorElementType() ==
3174 N1.getValueType().getVectorElementType() &&
3175 "Extract subvector VTs must have the same element type!");
3176 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3177 "Extract subvector must be from larger vector to smaller vector!");
3179 if (isa<ConstantSDNode>(Index.getNode())) {
3180 assert((VT.getVectorNumElements() +
3181 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3182 <= N1.getValueType().getVectorNumElements())
3183 && "Extract subvector overflow!");
3186 // Trivial extraction.
3187 if (VT.getSimpleVT() == N1.getSimpleValueType())
3194 // Perform trivial constant folding.
3195 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3196 if (SV.getNode()) return SV;
3198 // Canonicalize constant to RHS if commutative.
3199 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3200 std::swap(N1C, N2C);
3204 // Constant fold FP operations.
3205 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3206 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3208 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3209 // Canonicalize constant to RHS if commutative.
3210 std::swap(N1CFP, N2CFP);
3213 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3214 APFloat::opStatus s;
3217 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3218 if (s != APFloat::opInvalidOp)
3219 return getConstantFP(V1, VT);
3222 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3223 if (s!=APFloat::opInvalidOp)
3224 return getConstantFP(V1, VT);
3227 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3228 if (s!=APFloat::opInvalidOp)
3229 return getConstantFP(V1, VT);
3232 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3233 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3234 return getConstantFP(V1, VT);
3237 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3238 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3239 return getConstantFP(V1, VT);
3241 case ISD::FCOPYSIGN:
3243 return getConstantFP(V1, VT);
3248 if (Opcode == ISD::FP_ROUND) {
3249 APFloat V = N1CFP->getValueAPF(); // make copy
3251 // This can return overflow, underflow, or inexact; we don't care.
3252 // FIXME need to be more flexible about rounding mode.
3253 (void)V.convert(EVTToAPFloatSemantics(VT),
3254 APFloat::rmNearestTiesToEven, &ignored);
3255 return getConstantFP(V, VT);
3259 // Canonicalize an UNDEF to the RHS, even over a constant.
3260 if (N1.getOpcode() == ISD::UNDEF) {
3261 if (isCommutativeBinOp(Opcode)) {
3265 case ISD::FP_ROUND_INREG:
3266 case ISD::SIGN_EXTEND_INREG:
3272 return N1; // fold op(undef, arg2) -> undef
3280 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3281 // For vectors, we can't easily build an all zero vector, just return
3288 // Fold a bunch of operators when the RHS is undef.
3289 if (N2.getOpcode() == ISD::UNDEF) {
3292 if (N1.getOpcode() == ISD::UNDEF)
3293 // Handle undef ^ undef -> 0 special case. This is a common
3295 return getConstant(0, VT);
3305 return N2; // fold op(arg1, undef) -> undef
3311 if (getTarget().Options.UnsafeFPMath)
3319 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3320 // For vectors, we can't easily build an all zero vector, just return
3325 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3326 // For vectors, we can't easily build an all one vector, just return
3334 // Memoize this node if possible.
3336 SDVTList VTs = getVTList(VT);
3337 if (VT != MVT::Glue) {
3338 SDValue Ops[] = { N1, N2 };
3339 FoldingSetNodeID ID;
3340 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3342 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3343 return SDValue(E, 0);
3345 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3346 DL.getDebugLoc(), VTs, N1, N2);
3347 CSEMap.InsertNode(N, IP);
3349 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3350 DL.getDebugLoc(), VTs, N1, N2);
3353 AllNodes.push_back(N);
3357 return SDValue(N, 0);
3360 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3361 SDValue N1, SDValue N2, SDValue N3) {
3362 // Perform various simplifications.
3363 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3366 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3367 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3368 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3369 if (N1CFP && N2CFP && N3CFP) {
3370 APFloat V1 = N1CFP->getValueAPF();
3371 const APFloat &V2 = N2CFP->getValueAPF();
3372 const APFloat &V3 = N3CFP->getValueAPF();
3373 APFloat::opStatus s =
3374 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3375 if (s != APFloat::opInvalidOp)
3376 return getConstantFP(V1, VT);
3380 case ISD::CONCAT_VECTORS:
3381 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3382 // one big BUILD_VECTOR.
3383 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3384 N2.getOpcode() == ISD::BUILD_VECTOR &&
3385 N3.getOpcode() == ISD::BUILD_VECTOR) {
3386 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3387 N1.getNode()->op_end());
3388 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3389 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3390 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3394 // Use FoldSetCC to simplify SETCC's.
3395 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3396 if (Simp.getNode()) return Simp;
3401 if (N1C->getZExtValue())
3402 return N2; // select true, X, Y -> X
3403 return N3; // select false, X, Y -> Y
3406 if (N2 == N3) return N2; // select C, X, X -> X
3408 case ISD::VECTOR_SHUFFLE:
3409 llvm_unreachable("should use getVectorShuffle constructor!");
3410 case ISD::INSERT_SUBVECTOR: {
3412 if (VT.isSimple() && N1.getValueType().isSimple()
3413 && N2.getValueType().isSimple()) {
3414 assert(VT.isVector() && N1.getValueType().isVector() &&
3415 N2.getValueType().isVector() &&
3416 "Insert subvector VTs must be a vectors");
3417 assert(VT == N1.getValueType() &&
3418 "Dest and insert subvector source types must match!");
3419 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3420 "Insert subvector must be from smaller vector to larger vector!");
3421 if (isa<ConstantSDNode>(Index.getNode())) {
3422 assert((N2.getValueType().getVectorNumElements() +
3423 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3424 <= VT.getVectorNumElements())
3425 && "Insert subvector overflow!");
3428 // Trivial insertion.
3429 if (VT.getSimpleVT() == N2.getSimpleValueType())
3435 // Fold bit_convert nodes from a type to themselves.
3436 if (N1.getValueType() == VT)
3441 // Memoize node if it doesn't produce a flag.
3443 SDVTList VTs = getVTList(VT);
3444 if (VT != MVT::Glue) {
3445 SDValue Ops[] = { N1, N2, N3 };
3446 FoldingSetNodeID ID;
3447 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3449 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3450 return SDValue(E, 0);
3452 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3453 DL.getDebugLoc(), VTs, N1, N2, N3);
3454 CSEMap.InsertNode(N, IP);
3456 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3457 DL.getDebugLoc(), VTs, N1, N2, N3);
3460 AllNodes.push_back(N);
3464 return SDValue(N, 0);
3467 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3468 SDValue N1, SDValue N2, SDValue N3,
3470 SDValue Ops[] = { N1, N2, N3, N4 };
3471 return getNode(Opcode, DL, VT, Ops, 4);
3474 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3475 SDValue N1, SDValue N2, SDValue N3,
3476 SDValue N4, SDValue N5) {
3477 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3478 return getNode(Opcode, DL, VT, Ops, 5);
3481 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3482 /// the incoming stack arguments to be loaded from the stack.
3483 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3484 SmallVector<SDValue, 8> ArgChains;
3486 // Include the original chain at the beginning of the list. When this is
3487 // used by target LowerCall hooks, this helps legalize find the
3488 // CALLSEQ_BEGIN node.
3489 ArgChains.push_back(Chain);
3491 // Add a chain value for each stack argument.
3492 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3493 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3494 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3495 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3496 if (FI->getIndex() < 0)
3497 ArgChains.push_back(SDValue(L, 1));
3499 // Build a tokenfactor for all the chains.
3500 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3501 &ArgChains[0], ArgChains.size());
3504 /// getMemsetValue - Vectorized representation of the memset value
3506 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3508 assert(Value.getOpcode() != ISD::UNDEF);
3510 unsigned NumBits = VT.getScalarType().getSizeInBits();
3511 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3512 assert(C->getAPIntValue().getBitWidth() == 8);
3513 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3515 return DAG.getConstant(Val, VT);
3516 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3519 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3521 // Use a multiplication with 0x010101... to extend the input to the
3523 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3524 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3530 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3531 /// used when a memcpy is turned into a memset when the source is a constant
3533 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3534 const TargetLowering &TLI, StringRef Str) {
3535 // Handle vector with all elements zero.
3538 return DAG.getConstant(0, VT);
3539 else if (VT == MVT::f32 || VT == MVT::f64)
3540 return DAG.getConstantFP(0.0, VT);
3541 else if (VT.isVector()) {
3542 unsigned NumElts = VT.getVectorNumElements();
3543 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3544 return DAG.getNode(ISD::BITCAST, dl, VT,
3545 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3548 llvm_unreachable("Expected type!");
3551 assert(!VT.isVector() && "Can't handle vector type here!");
3552 unsigned NumVTBits = VT.getSizeInBits();
3553 unsigned NumVTBytes = NumVTBits / 8;
3554 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3556 APInt Val(NumVTBits, 0);
3557 if (TLI.isLittleEndian()) {
3558 for (unsigned i = 0; i != NumBytes; ++i)
3559 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3561 for (unsigned i = 0; i != NumBytes; ++i)
3562 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3565 // If the "cost" of materializing the integer immediate is 1 or free, then
3566 // it is cost effective to turn the load into the immediate.
3567 const TargetTransformInfo *TTI = DAG.getTargetTransformInfo();
3568 if (TTI->getIntImmCost(Val, VT.getTypeForEVT(*DAG.getContext())) < 2)
3569 return DAG.getConstant(Val, VT);
3570 return SDValue(0, 0);
3573 /// getMemBasePlusOffset - Returns base and offset node for the
3575 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3576 SelectionDAG &DAG) {
3577 EVT VT = Base.getValueType();
3578 return DAG.getNode(ISD::ADD, dl,
3579 VT, Base, DAG.getConstant(Offset, VT));
3582 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3584 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3585 unsigned SrcDelta = 0;
3586 GlobalAddressSDNode *G = NULL;
3587 if (Src.getOpcode() == ISD::GlobalAddress)
3588 G = cast<GlobalAddressSDNode>(Src);
3589 else if (Src.getOpcode() == ISD::ADD &&
3590 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3591 Src.getOperand(1).getOpcode() == ISD::Constant) {
3592 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3593 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3598 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3601 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3602 /// to replace the memset / memcpy. Return true if the number of memory ops
3603 /// is below the threshold. It returns the types of the sequence of
3604 /// memory ops to perform memset / memcpy by reference.
3605 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3606 unsigned Limit, uint64_t Size,
3607 unsigned DstAlign, unsigned SrcAlign,
3613 const TargetLowering &TLI) {
3614 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3615 "Expecting memcpy / memset source to meet alignment requirement!");
3616 // If 'SrcAlign' is zero, that means the memory operation does not need to
3617 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3618 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3619 // is the specified alignment of the memory operation. If it is zero, that
3620 // means it's possible to change the alignment of the destination.
3621 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3622 // not need to be loaded.
3623 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3624 IsMemset, ZeroMemset, MemcpyStrSrc,
3625 DAG.getMachineFunction());
3627 if (VT == MVT::Other) {
3628 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3629 TLI.allowsUnalignedMemoryAccesses(VT)) {
3630 VT = TLI.getPointerTy();
3632 switch (DstAlign & 7) {
3633 case 0: VT = MVT::i64; break;
3634 case 4: VT = MVT::i32; break;
3635 case 2: VT = MVT::i16; break;
3636 default: VT = MVT::i8; break;
3641 while (!TLI.isTypeLegal(LVT))
3642 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3643 assert(LVT.isInteger());
3649 unsigned NumMemOps = 0;
3651 unsigned VTSize = VT.getSizeInBits() / 8;
3652 while (VTSize > Size) {
3653 // For now, only use non-vector load / store's for the left-over pieces.
3658 if (VT.isVector() || VT.isFloatingPoint()) {
3659 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3660 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3661 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3663 else if (NewVT == MVT::i64 &&
3664 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3665 TLI.isSafeMemOpType(MVT::f64)) {
3666 // i64 is usually not legal on 32-bit targets, but f64 may be.
3674 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3675 if (NewVT == MVT::i8)
3677 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3679 NewVTSize = NewVT.getSizeInBits() / 8;
3681 // If the new VT cannot cover all of the remaining bits, then consider
3682 // issuing a (or a pair of) unaligned and overlapping load / store.
3683 // FIXME: Only does this for 64-bit or more since we don't have proper
3684 // cost model for unaligned load / store.
3686 if (NumMemOps && AllowOverlap &&
3687 VTSize >= 8 && NewVTSize < Size &&
3688 TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3696 if (++NumMemOps > Limit)
3699 MemOps.push_back(VT);
3706 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3707 SDValue Chain, SDValue Dst,
3708 SDValue Src, uint64_t Size,
3709 unsigned Align, bool isVol,
3711 MachinePointerInfo DstPtrInfo,
3712 MachinePointerInfo SrcPtrInfo) {
3713 // Turn a memcpy of undef to nop.
3714 if (Src.getOpcode() == ISD::UNDEF)
3717 // Expand memcpy to a series of load and store ops if the size operand falls
3718 // below a certain threshold.
3719 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3720 // rather than maybe a humongous number of loads and stores.
3721 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3722 std::vector<EVT> MemOps;
3723 bool DstAlignCanChange = false;
3724 MachineFunction &MF = DAG.getMachineFunction();
3725 MachineFrameInfo *MFI = MF.getFrameInfo();
3727 MF.getFunction()->getAttributes().
3728 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3729 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3730 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3731 DstAlignCanChange = true;
3732 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3733 if (Align > SrcAlign)
3736 bool CopyFromStr = isMemSrcFromString(Src, Str);
3737 bool isZeroStr = CopyFromStr && Str.empty();
3738 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3740 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3741 (DstAlignCanChange ? 0 : Align),
3742 (isZeroStr ? 0 : SrcAlign),
3743 false, false, CopyFromStr, true, DAG, TLI))
3746 if (DstAlignCanChange) {
3747 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3748 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3750 // Don't promote to an alignment that would require dynamic stack
3752 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3753 if (!TRI->needsStackRealignment(MF))
3754 while (NewAlign > Align &&
3755 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3758 if (NewAlign > Align) {
3759 // Give the stack frame object a larger alignment if needed.
3760 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3761 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3766 SmallVector<SDValue, 8> OutChains;
3767 unsigned NumMemOps = MemOps.size();
3768 uint64_t SrcOff = 0, DstOff = 0;
3769 for (unsigned i = 0; i != NumMemOps; ++i) {
3771 unsigned VTSize = VT.getSizeInBits() / 8;
3772 SDValue Value, Store;
3774 if (VTSize > Size) {
3775 // Issuing an unaligned load / store pair that overlaps with the previous
3776 // pair. Adjust the offset accordingly.
3777 assert(i == NumMemOps-1 && i != 0);
3778 SrcOff -= VTSize - Size;
3779 DstOff -= VTSize - Size;
3783 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3784 // It's unlikely a store of a vector immediate can be done in a single
3785 // instruction. It would require a load from a constantpool first.
3786 // We only handle zero vectors here.
3787 // FIXME: Handle other cases where store of vector immediate is done in
3788 // a single instruction.
3789 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3790 if (Value.getNode())
3791 Store = DAG.getStore(Chain, dl, Value,
3792 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3793 DstPtrInfo.getWithOffset(DstOff), isVol,
3797 if (!Store.getNode()) {
3798 // The type might not be legal for the target. This should only happen
3799 // if the type is smaller than a legal type, as on PPC, so the right
3800 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3801 // to Load/Store if NVT==VT.
3802 // FIXME does the case above also need this?
3803 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3804 assert(NVT.bitsGE(VT));
3805 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3806 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3807 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3808 MinAlign(SrcAlign, SrcOff));
3809 Store = DAG.getTruncStore(Chain, dl, Value,
3810 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3811 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3814 OutChains.push_back(Store);
3820 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3821 &OutChains[0], OutChains.size());
3824 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3825 SDValue Chain, SDValue Dst,
3826 SDValue Src, uint64_t Size,
3827 unsigned Align, bool isVol,
3829 MachinePointerInfo DstPtrInfo,
3830 MachinePointerInfo SrcPtrInfo) {
3831 // Turn a memmove of undef to nop.
3832 if (Src.getOpcode() == ISD::UNDEF)
3835 // Expand memmove to a series of load and store ops if the size operand falls
3836 // below a certain threshold.
3837 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3838 std::vector<EVT> MemOps;
3839 bool DstAlignCanChange = false;
3840 MachineFunction &MF = DAG.getMachineFunction();
3841 MachineFrameInfo *MFI = MF.getFrameInfo();
3842 bool OptSize = MF.getFunction()->getAttributes().
3843 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3844 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3845 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3846 DstAlignCanChange = true;
3847 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3848 if (Align > SrcAlign)
3850 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3852 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3853 (DstAlignCanChange ? 0 : Align), SrcAlign,
3854 false, false, false, false, DAG, TLI))
3857 if (DstAlignCanChange) {
3858 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3859 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3860 if (NewAlign > Align) {
3861 // Give the stack frame object a larger alignment if needed.
3862 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3863 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3868 uint64_t SrcOff = 0, DstOff = 0;
3869 SmallVector<SDValue, 8> LoadValues;
3870 SmallVector<SDValue, 8> LoadChains;
3871 SmallVector<SDValue, 8> OutChains;
3872 unsigned NumMemOps = MemOps.size();
3873 for (unsigned i = 0; i < NumMemOps; i++) {
3875 unsigned VTSize = VT.getSizeInBits() / 8;
3878 Value = DAG.getLoad(VT, dl, Chain,
3879 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3880 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3881 false, false, SrcAlign);
3882 LoadValues.push_back(Value);
3883 LoadChains.push_back(Value.getValue(1));
3886 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3887 &LoadChains[0], LoadChains.size());
3889 for (unsigned i = 0; i < NumMemOps; i++) {
3891 unsigned VTSize = VT.getSizeInBits() / 8;
3894 Store = DAG.getStore(Chain, dl, LoadValues[i],
3895 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3896 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3897 OutChains.push_back(Store);
3901 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3902 &OutChains[0], OutChains.size());
3905 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3908 /// \param DAG Selection DAG where lowered code is placed.
3909 /// \param dl Link to corresponding IR location.
3910 /// \param Chain Control flow dependency.
3911 /// \param Dst Pointer to destination memory location.
3912 /// \param Src Value of byte to write into the memory.
3913 /// \param Size Number of bytes to write.
3914 /// \param Align Alignment of the destination in bytes.
3915 /// \param isVol True if destination is volatile.
3916 /// \param DstPtrInfo IR information on the memory pointer.
3917 /// \returns New head in the control flow, if lowering was successful, empty
3918 /// SDValue otherwise.
3920 /// The function tries to replace 'llvm.memset' intrinsic with several store
3921 /// operations and value calculation code. This is usually profitable for small
3923 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3924 SDValue Chain, SDValue Dst,
3925 SDValue Src, uint64_t Size,
3926 unsigned Align, bool isVol,
3927 MachinePointerInfo DstPtrInfo) {
3928 // Turn a memset of undef to nop.
3929 if (Src.getOpcode() == ISD::UNDEF)
3932 // Expand memset to a series of load/store ops if the size operand
3933 // falls below a certain threshold.
3934 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3935 std::vector<EVT> MemOps;
3936 bool DstAlignCanChange = false;
3937 MachineFunction &MF = DAG.getMachineFunction();
3938 MachineFrameInfo *MFI = MF.getFrameInfo();
3939 bool OptSize = MF.getFunction()->getAttributes().
3940 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3941 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3942 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3943 DstAlignCanChange = true;
3945 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3946 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3947 Size, (DstAlignCanChange ? 0 : Align), 0,
3948 true, IsZeroVal, false, true, DAG, TLI))
3951 if (DstAlignCanChange) {
3952 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3953 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3954 if (NewAlign > Align) {
3955 // Give the stack frame object a larger alignment if needed.
3956 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3957 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3962 SmallVector<SDValue, 8> OutChains;
3963 uint64_t DstOff = 0;
3964 unsigned NumMemOps = MemOps.size();
3966 // Find the largest store and generate the bit pattern for it.
3967 EVT LargestVT = MemOps[0];
3968 for (unsigned i = 1; i < NumMemOps; i++)
3969 if (MemOps[i].bitsGT(LargestVT))
3970 LargestVT = MemOps[i];
3971 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3973 for (unsigned i = 0; i < NumMemOps; i++) {
3975 unsigned VTSize = VT.getSizeInBits() / 8;
3976 if (VTSize > Size) {
3977 // Issuing an unaligned load / store pair that overlaps with the previous
3978 // pair. Adjust the offset accordingly.
3979 assert(i == NumMemOps-1 && i != 0);
3980 DstOff -= VTSize - Size;
3983 // If this store is smaller than the largest store see whether we can get
3984 // the smaller value for free with a truncate.
3985 SDValue Value = MemSetValue;
3986 if (VT.bitsLT(LargestVT)) {
3987 if (!LargestVT.isVector() && !VT.isVector() &&
3988 TLI.isTruncateFree(LargestVT, VT))
3989 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3991 Value = getMemsetValue(Src, VT, DAG, dl);
3993 assert(Value.getValueType() == VT && "Value with wrong type.");
3994 SDValue Store = DAG.getStore(Chain, dl, Value,
3995 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3996 DstPtrInfo.getWithOffset(DstOff),
3997 isVol, false, Align);
3998 OutChains.push_back(Store);
3999 DstOff += VT.getSizeInBits() / 8;
4003 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4004 &OutChains[0], OutChains.size());
4007 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4008 SDValue Src, SDValue Size,
4009 unsigned Align, bool isVol, bool AlwaysInline,
4010 MachinePointerInfo DstPtrInfo,
4011 MachinePointerInfo SrcPtrInfo) {
4012 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4014 // Check to see if we should lower the memcpy to loads and stores first.
4015 // For cases within the target-specified limits, this is the best choice.
4016 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4018 // Memcpy with size zero? Just return the original chain.
4019 if (ConstantSize->isNullValue())
4022 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4023 ConstantSize->getZExtValue(),Align,
4024 isVol, false, DstPtrInfo, SrcPtrInfo);
4025 if (Result.getNode())
4029 // Then check to see if we should lower the memcpy with target-specific
4030 // code. If the target chooses to do this, this is the next best.
4032 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4033 isVol, AlwaysInline,
4034 DstPtrInfo, SrcPtrInfo);
4035 if (Result.getNode())
4038 // If we really need inline code and the target declined to provide it,
4039 // use a (potentially long) sequence of loads and stores.
4041 assert(ConstantSize && "AlwaysInline requires a constant size!");
4042 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4043 ConstantSize->getZExtValue(), Align, isVol,
4044 true, DstPtrInfo, SrcPtrInfo);
4047 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4048 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4049 // respect volatile, so they may do things like read or write memory
4050 // beyond the given memory regions. But fixing this isn't easy, and most
4051 // people don't care.
4053 const TargetLowering *TLI = TM.getTargetLowering();
4055 // Emit a library call.
4056 TargetLowering::ArgListTy Args;
4057 TargetLowering::ArgListEntry Entry;
4058 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4059 Entry.Node = Dst; Args.push_back(Entry);
4060 Entry.Node = Src; Args.push_back(Entry);
4061 Entry.Node = Size; Args.push_back(Entry);
4062 // FIXME: pass in SDLoc
4064 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4065 false, false, false, false, 0,
4066 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4067 /*isTailCall=*/false,
4068 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4069 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4070 TLI->getPointerTy()),
4072 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4074 return CallResult.second;
4077 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4078 SDValue Src, SDValue Size,
4079 unsigned Align, bool isVol,
4080 MachinePointerInfo DstPtrInfo,
4081 MachinePointerInfo SrcPtrInfo) {
4082 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4084 // Check to see if we should lower the memmove to loads and stores first.
4085 // For cases within the target-specified limits, this is the best choice.
4086 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4088 // Memmove with size zero? Just return the original chain.
4089 if (ConstantSize->isNullValue())
4093 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4094 ConstantSize->getZExtValue(), Align, isVol,
4095 false, DstPtrInfo, SrcPtrInfo);
4096 if (Result.getNode())
4100 // Then check to see if we should lower the memmove with target-specific
4101 // code. If the target chooses to do this, this is the next best.
4103 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4104 DstPtrInfo, SrcPtrInfo);
4105 if (Result.getNode())
4108 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4109 // not be safe. See memcpy above for more details.
4111 const TargetLowering *TLI = TM.getTargetLowering();
4113 // Emit a library call.
4114 TargetLowering::ArgListTy Args;
4115 TargetLowering::ArgListEntry Entry;
4116 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4117 Entry.Node = Dst; Args.push_back(Entry);
4118 Entry.Node = Src; Args.push_back(Entry);
4119 Entry.Node = Size; Args.push_back(Entry);
4120 // FIXME: pass in SDLoc
4122 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4123 false, false, false, false, 0,
4124 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4125 /*isTailCall=*/false,
4126 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4127 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4128 TLI->getPointerTy()),
4130 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4132 return CallResult.second;
4135 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4136 SDValue Src, SDValue Size,
4137 unsigned Align, bool isVol,
4138 MachinePointerInfo DstPtrInfo) {
4139 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4141 // Check to see if we should lower the memset to stores first.
4142 // For cases within the target-specified limits, this is the best choice.
4143 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4145 // Memset with size zero? Just return the original chain.
4146 if (ConstantSize->isNullValue())
4150 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4151 Align, isVol, DstPtrInfo);
4153 if (Result.getNode())
4157 // Then check to see if we should lower the memset with target-specific
4158 // code. If the target chooses to do this, this is the next best.
4160 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4162 if (Result.getNode())
4165 // Emit a library call.
4166 const TargetLowering *TLI = TM.getTargetLowering();
4167 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4168 TargetLowering::ArgListTy Args;
4169 TargetLowering::ArgListEntry Entry;
4170 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4171 Args.push_back(Entry);
4172 // Extend or truncate the argument to be an i32 value for the call.
4173 if (Src.getValueType().bitsGT(MVT::i32))
4174 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4176 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4178 Entry.Ty = Type::getInt32Ty(*getContext());
4179 Entry.isSExt = true;
4180 Args.push_back(Entry);
4182 Entry.Ty = IntPtrTy;
4183 Entry.isSExt = false;
4184 Args.push_back(Entry);
4185 // FIXME: pass in SDLoc
4187 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4188 false, false, false, false, 0,
4189 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4190 /*isTailCall=*/false,
4191 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4192 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4193 TLI->getPointerTy()),
4195 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4197 return CallResult.second;
4200 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4201 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4202 MachineMemOperand *MMO,
4203 AtomicOrdering Ordering,
4204 SynchronizationScope SynchScope) {
4205 FoldingSetNodeID ID;
4206 ID.AddInteger(MemVT.getRawBits());
4207 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4208 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4210 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4211 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4212 return SDValue(E, 0);
4215 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4216 // SDNode doesn't have access to it. This memory will be "leaked" when
4217 // the node is deallocated, but recovered when the allocator is released.
4218 // If the number of operands is less than 5 we use AtomicSDNode's internal
4220 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4222 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4223 dl.getDebugLoc(), VTList, MemVT,
4224 Ops, DynOps, NumOps, MMO,
4225 Ordering, SynchScope);
4226 CSEMap.InsertNode(N, IP);
4227 AllNodes.push_back(N);
4228 return SDValue(N, 0);
4231 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4232 SDValue Chain, SDValue Ptr, SDValue Cmp,
4233 SDValue Swp, MachinePointerInfo PtrInfo,
4235 AtomicOrdering Ordering,
4236 SynchronizationScope SynchScope) {
4237 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4238 Alignment = getEVTAlignment(MemVT);
4240 MachineFunction &MF = getMachineFunction();
4242 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4243 // For now, atomics are considered to be volatile always.
4244 // FIXME: Volatile isn't really correct; we should keep track of atomic
4245 // orderings in the memoperand.
4246 unsigned Flags = MachineMemOperand::MOVolatile;
4247 if (Opcode != ISD::ATOMIC_STORE)
4248 Flags |= MachineMemOperand::MOLoad;
4249 if (Opcode != ISD::ATOMIC_LOAD)
4250 Flags |= MachineMemOperand::MOStore;
4252 MachineMemOperand *MMO =
4253 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4255 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4256 Ordering, SynchScope);
4259 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4261 SDValue Ptr, SDValue Cmp,
4262 SDValue Swp, MachineMemOperand *MMO,
4263 AtomicOrdering Ordering,
4264 SynchronizationScope SynchScope) {
4265 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4266 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4268 EVT VT = Cmp.getValueType();
4270 SDVTList VTs = getVTList(VT, MVT::Other);
4271 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4272 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4275 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4277 SDValue Ptr, SDValue Val,
4278 const Value* PtrVal,
4280 AtomicOrdering Ordering,
4281 SynchronizationScope SynchScope) {
4282 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4283 Alignment = getEVTAlignment(MemVT);
4285 MachineFunction &MF = getMachineFunction();
4286 // An atomic store does not load. An atomic load does not store.
4287 // (An atomicrmw obviously both loads and stores.)
4288 // For now, atomics are considered to be volatile always, and they are
4290 // FIXME: Volatile isn't really correct; we should keep track of atomic
4291 // orderings in the memoperand.
4292 unsigned Flags = MachineMemOperand::MOVolatile;
4293 if (Opcode != ISD::ATOMIC_STORE)
4294 Flags |= MachineMemOperand::MOLoad;
4295 if (Opcode != ISD::ATOMIC_LOAD)
4296 Flags |= MachineMemOperand::MOStore;
4298 MachineMemOperand *MMO =
4299 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4300 MemVT.getStoreSize(), Alignment);
4302 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4303 Ordering, SynchScope);
4306 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4308 SDValue Ptr, SDValue Val,
4309 MachineMemOperand *MMO,
4310 AtomicOrdering Ordering,
4311 SynchronizationScope SynchScope) {
4312 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4313 Opcode == ISD::ATOMIC_LOAD_SUB ||
4314 Opcode == ISD::ATOMIC_LOAD_AND ||
4315 Opcode == ISD::ATOMIC_LOAD_OR ||
4316 Opcode == ISD::ATOMIC_LOAD_XOR ||
4317 Opcode == ISD::ATOMIC_LOAD_NAND ||
4318 Opcode == ISD::ATOMIC_LOAD_MIN ||
4319 Opcode == ISD::ATOMIC_LOAD_MAX ||
4320 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4321 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4322 Opcode == ISD::ATOMIC_SWAP ||
4323 Opcode == ISD::ATOMIC_STORE) &&
4324 "Invalid Atomic Op");
4326 EVT VT = Val.getValueType();
4328 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4329 getVTList(VT, MVT::Other);
4330 SDValue Ops[] = {Chain, Ptr, Val};
4331 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4334 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4335 EVT VT, SDValue Chain,
4337 const Value* PtrVal,
4339 AtomicOrdering Ordering,
4340 SynchronizationScope SynchScope) {
4341 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4342 Alignment = getEVTAlignment(MemVT);
4344 MachineFunction &MF = getMachineFunction();
4345 // An atomic store does not load. An atomic load does not store.
4346 // (An atomicrmw obviously both loads and stores.)
4347 // For now, atomics are considered to be volatile always, and they are
4349 // FIXME: Volatile isn't really correct; we should keep track of atomic
4350 // orderings in the memoperand.
4351 unsigned Flags = MachineMemOperand::MOVolatile;
4352 if (Opcode != ISD::ATOMIC_STORE)
4353 Flags |= MachineMemOperand::MOLoad;
4354 if (Opcode != ISD::ATOMIC_LOAD)
4355 Flags |= MachineMemOperand::MOStore;
4357 MachineMemOperand *MMO =
4358 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4359 MemVT.getStoreSize(), Alignment);
4361 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4362 Ordering, SynchScope);
4365 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4366 EVT VT, SDValue Chain,
4368 MachineMemOperand *MMO,
4369 AtomicOrdering Ordering,
4370 SynchronizationScope SynchScope) {
4371 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4373 SDVTList VTs = getVTList(VT, MVT::Other);
4374 SDValue Ops[] = {Chain, Ptr};
4375 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4378 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4379 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4384 SmallVector<EVT, 4> VTs;
4385 VTs.reserve(NumOps);
4386 for (unsigned i = 0; i < NumOps; ++i)
4387 VTs.push_back(Ops[i].getValueType());
4388 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4393 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4394 const EVT *VTs, unsigned NumVTs,
4395 const SDValue *Ops, unsigned NumOps,
4396 EVT MemVT, MachinePointerInfo PtrInfo,
4397 unsigned Align, bool Vol,
4398 bool ReadMem, bool WriteMem) {
4399 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4400 MemVT, PtrInfo, Align, Vol,
4405 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4406 const SDValue *Ops, unsigned NumOps,
4407 EVT MemVT, MachinePointerInfo PtrInfo,
4408 unsigned Align, bool Vol,
4409 bool ReadMem, bool WriteMem) {
4410 if (Align == 0) // Ensure that codegen never sees alignment 0
4411 Align = getEVTAlignment(MemVT);
4413 MachineFunction &MF = getMachineFunction();
4416 Flags |= MachineMemOperand::MOStore;
4418 Flags |= MachineMemOperand::MOLoad;
4420 Flags |= MachineMemOperand::MOVolatile;
4421 MachineMemOperand *MMO =
4422 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4424 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4428 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4429 const SDValue *Ops, unsigned NumOps,
4430 EVT MemVT, MachineMemOperand *MMO) {
4431 assert((Opcode == ISD::INTRINSIC_VOID ||
4432 Opcode == ISD::INTRINSIC_W_CHAIN ||
4433 Opcode == ISD::PREFETCH ||
4434 Opcode == ISD::LIFETIME_START ||
4435 Opcode == ISD::LIFETIME_END ||
4436 (Opcode <= INT_MAX &&
4437 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4438 "Opcode is not a memory-accessing opcode!");
4440 // Memoize the node unless it returns a flag.
4441 MemIntrinsicSDNode *N;
4442 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4443 FoldingSetNodeID ID;
4444 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4445 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4447 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4448 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4449 return SDValue(E, 0);
4452 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4453 dl.getDebugLoc(), VTList, Ops,
4454 NumOps, MemVT, MMO);
4455 CSEMap.InsertNode(N, IP);
4457 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4458 dl.getDebugLoc(), VTList, Ops,
4459 NumOps, MemVT, MMO);
4461 AllNodes.push_back(N);
4462 return SDValue(N, 0);
4465 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4466 /// MachinePointerInfo record from it. This is particularly useful because the
4467 /// code generator has many cases where it doesn't bother passing in a
4468 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4469 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4470 // If this is FI+Offset, we can model it.
4471 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4472 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4474 // If this is (FI+Offset1)+Offset2, we can model it.
4475 if (Ptr.getOpcode() != ISD::ADD ||
4476 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4477 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4478 return MachinePointerInfo();
4480 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4481 return MachinePointerInfo::getFixedStack(FI, Offset+
4482 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4485 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4486 /// MachinePointerInfo record from it. This is particularly useful because the
4487 /// code generator has many cases where it doesn't bother passing in a
4488 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4489 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4490 // If the 'Offset' value isn't a constant, we can't handle this.
4491 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4492 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4493 if (OffsetOp.getOpcode() == ISD::UNDEF)
4494 return InferPointerInfo(Ptr);
4495 return MachinePointerInfo();
4500 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4501 EVT VT, SDLoc dl, SDValue Chain,
4502 SDValue Ptr, SDValue Offset,
4503 MachinePointerInfo PtrInfo, EVT MemVT,
4504 bool isVolatile, bool isNonTemporal, bool isInvariant,
4505 unsigned Alignment, const MDNode *TBAAInfo,
4506 const MDNode *Ranges) {
4507 assert(Chain.getValueType() == MVT::Other &&
4508 "Invalid chain type");
4509 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4510 Alignment = getEVTAlignment(VT);
4512 unsigned Flags = MachineMemOperand::MOLoad;
4514 Flags |= MachineMemOperand::MOVolatile;
4516 Flags |= MachineMemOperand::MONonTemporal;
4518 Flags |= MachineMemOperand::MOInvariant;
4520 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4523 PtrInfo = InferPointerInfo(Ptr, Offset);
4525 MachineFunction &MF = getMachineFunction();
4526 MachineMemOperand *MMO =
4527 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4529 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4533 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4534 EVT VT, SDLoc dl, SDValue Chain,
4535 SDValue Ptr, SDValue Offset, EVT MemVT,
4536 MachineMemOperand *MMO) {
4538 ExtType = ISD::NON_EXTLOAD;
4539 } else if (ExtType == ISD::NON_EXTLOAD) {
4540 assert(VT == MemVT && "Non-extending load from different memory type!");
4543 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4544 "Should only be an extending load, not truncating!");
4545 assert(VT.isInteger() == MemVT.isInteger() &&
4546 "Cannot convert from FP to Int or Int -> FP!");
4547 assert(VT.isVector() == MemVT.isVector() &&
4548 "Cannot use trunc store to convert to or from a vector!");
4549 assert((!VT.isVector() ||
4550 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4551 "Cannot use trunc store to change the number of vector elements!");
4554 bool Indexed = AM != ISD::UNINDEXED;
4555 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4556 "Unindexed load with an offset!");
4558 SDVTList VTs = Indexed ?
4559 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4560 SDValue Ops[] = { Chain, Ptr, Offset };
4561 FoldingSetNodeID ID;
4562 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4563 ID.AddInteger(MemVT.getRawBits());
4564 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4565 MMO->isNonTemporal(),
4566 MMO->isInvariant()));
4567 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4569 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4570 cast<LoadSDNode>(E)->refineAlignment(MMO);
4571 return SDValue(E, 0);
4573 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4574 dl.getDebugLoc(), VTs, AM, ExtType,
4576 CSEMap.InsertNode(N, IP);
4577 AllNodes.push_back(N);
4578 return SDValue(N, 0);
4581 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4582 SDValue Chain, SDValue Ptr,
4583 MachinePointerInfo PtrInfo,
4584 bool isVolatile, bool isNonTemporal,
4585 bool isInvariant, unsigned Alignment,
4586 const MDNode *TBAAInfo,
4587 const MDNode *Ranges) {
4588 SDValue Undef = getUNDEF(Ptr.getValueType());
4589 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4590 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4594 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4595 SDValue Chain, SDValue Ptr,
4596 MachineMemOperand *MMO) {
4597 SDValue Undef = getUNDEF(Ptr.getValueType());
4598 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4602 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4603 SDValue Chain, SDValue Ptr,
4604 MachinePointerInfo PtrInfo, EVT MemVT,
4605 bool isVolatile, bool isNonTemporal,
4606 unsigned Alignment, const MDNode *TBAAInfo) {
4607 SDValue Undef = getUNDEF(Ptr.getValueType());
4608 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4609 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4614 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4615 SDValue Chain, SDValue Ptr, EVT MemVT,
4616 MachineMemOperand *MMO) {
4617 SDValue Undef = getUNDEF(Ptr.getValueType());
4618 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4623 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4624 SDValue Offset, ISD::MemIndexedMode AM) {
4625 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4626 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4627 "Load is already a indexed load!");
4628 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4629 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4630 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4631 false, LD->getAlignment());
4634 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4635 SDValue Ptr, MachinePointerInfo PtrInfo,
4636 bool isVolatile, bool isNonTemporal,
4637 unsigned Alignment, const MDNode *TBAAInfo) {
4638 assert(Chain.getValueType() == MVT::Other &&
4639 "Invalid chain type");
4640 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4641 Alignment = getEVTAlignment(Val.getValueType());
4643 unsigned Flags = MachineMemOperand::MOStore;
4645 Flags |= MachineMemOperand::MOVolatile;
4647 Flags |= MachineMemOperand::MONonTemporal;
4650 PtrInfo = InferPointerInfo(Ptr);
4652 MachineFunction &MF = getMachineFunction();
4653 MachineMemOperand *MMO =
4654 MF.getMachineMemOperand(PtrInfo, Flags,
4655 Val.getValueType().getStoreSize(), Alignment,
4658 return getStore(Chain, dl, Val, Ptr, MMO);
4661 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4662 SDValue Ptr, MachineMemOperand *MMO) {
4663 assert(Chain.getValueType() == MVT::Other &&
4664 "Invalid chain type");
4665 EVT VT = Val.getValueType();
4666 SDVTList VTs = getVTList(MVT::Other);
4667 SDValue Undef = getUNDEF(Ptr.getValueType());
4668 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4669 FoldingSetNodeID ID;
4670 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4671 ID.AddInteger(VT.getRawBits());
4672 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4673 MMO->isNonTemporal(), MMO->isInvariant()));
4674 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4676 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4677 cast<StoreSDNode>(E)->refineAlignment(MMO);
4678 return SDValue(E, 0);
4680 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4681 dl.getDebugLoc(), VTs,
4682 ISD::UNINDEXED, false, VT, MMO);
4683 CSEMap.InsertNode(N, IP);
4684 AllNodes.push_back(N);
4685 return SDValue(N, 0);
4688 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4689 SDValue Ptr, MachinePointerInfo PtrInfo,
4690 EVT SVT,bool isVolatile, bool isNonTemporal,
4692 const MDNode *TBAAInfo) {
4693 assert(Chain.getValueType() == MVT::Other &&
4694 "Invalid chain type");
4695 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4696 Alignment = getEVTAlignment(SVT);
4698 unsigned Flags = MachineMemOperand::MOStore;
4700 Flags |= MachineMemOperand::MOVolatile;
4702 Flags |= MachineMemOperand::MONonTemporal;
4705 PtrInfo = InferPointerInfo(Ptr);
4707 MachineFunction &MF = getMachineFunction();
4708 MachineMemOperand *MMO =
4709 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4712 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4715 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4716 SDValue Ptr, EVT SVT,
4717 MachineMemOperand *MMO) {
4718 EVT VT = Val.getValueType();
4720 assert(Chain.getValueType() == MVT::Other &&
4721 "Invalid chain type");
4723 return getStore(Chain, dl, Val, Ptr, MMO);
4725 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4726 "Should only be a truncating store, not extending!");
4727 assert(VT.isInteger() == SVT.isInteger() &&
4728 "Can't do FP-INT conversion!");
4729 assert(VT.isVector() == SVT.isVector() &&
4730 "Cannot use trunc store to convert to or from a vector!");
4731 assert((!VT.isVector() ||
4732 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4733 "Cannot use trunc store to change the number of vector elements!");
4735 SDVTList VTs = getVTList(MVT::Other);
4736 SDValue Undef = getUNDEF(Ptr.getValueType());
4737 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4738 FoldingSetNodeID ID;
4739 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4740 ID.AddInteger(SVT.getRawBits());
4741 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4742 MMO->isNonTemporal(), MMO->isInvariant()));
4743 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4745 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4746 cast<StoreSDNode>(E)->refineAlignment(MMO);
4747 return SDValue(E, 0);
4749 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4750 dl.getDebugLoc(), VTs,
4751 ISD::UNINDEXED, true, SVT, MMO);
4752 CSEMap.InsertNode(N, IP);
4753 AllNodes.push_back(N);
4754 return SDValue(N, 0);
4758 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4759 SDValue Offset, ISD::MemIndexedMode AM) {
4760 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4761 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4762 "Store is already a indexed store!");
4763 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4764 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4765 FoldingSetNodeID ID;
4766 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4767 ID.AddInteger(ST->getMemoryVT().getRawBits());
4768 ID.AddInteger(ST->getRawSubclassData());
4769 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4771 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4772 return SDValue(E, 0);
4774 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4775 dl.getDebugLoc(), VTs, AM,
4776 ST->isTruncatingStore(),
4778 ST->getMemOperand());
4779 CSEMap.InsertNode(N, IP);
4780 AllNodes.push_back(N);
4781 return SDValue(N, 0);
4784 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4785 SDValue Chain, SDValue Ptr,
4788 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4789 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4792 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4793 const SDUse *Ops, unsigned NumOps) {
4795 case 0: return getNode(Opcode, DL, VT);
4796 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4797 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4798 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4802 // Copy from an SDUse array into an SDValue array for use with
4803 // the regular getNode logic.
4804 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4805 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4808 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4809 const SDValue *Ops, unsigned NumOps) {
4811 case 0: return getNode(Opcode, DL, VT);
4812 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4813 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4814 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4820 case ISD::SELECT_CC: {
4821 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4822 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4823 "LHS and RHS of condition must have same type!");
4824 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4825 "True and False arms of SelectCC must have same type!");
4826 assert(Ops[2].getValueType() == VT &&
4827 "select_cc node must be of same type as true and false value!");
4831 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4832 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4833 "LHS/RHS of comparison should match types!");
4840 SDVTList VTs = getVTList(VT);
4842 if (VT != MVT::Glue) {
4843 FoldingSetNodeID ID;
4844 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4847 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4848 return SDValue(E, 0);
4850 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4852 CSEMap.InsertNode(N, IP);
4854 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4858 AllNodes.push_back(N);
4862 return SDValue(N, 0);
4865 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4866 ArrayRef<EVT> ResultTys,
4867 const SDValue *Ops, unsigned NumOps) {
4868 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4872 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4873 const EVT *VTs, unsigned NumVTs,
4874 const SDValue *Ops, unsigned NumOps) {
4876 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4877 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4880 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4881 const SDValue *Ops, unsigned NumOps) {
4882 if (VTList.NumVTs == 1)
4883 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4887 // FIXME: figure out how to safely handle things like
4888 // int foo(int x) { return 1 << (x & 255); }
4889 // int bar() { return foo(256); }
4890 case ISD::SRA_PARTS:
4891 case ISD::SRL_PARTS:
4892 case ISD::SHL_PARTS:
4893 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4894 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4895 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4896 else if (N3.getOpcode() == ISD::AND)
4897 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4898 // If the and is only masking out bits that cannot effect the shift,
4899 // eliminate the and.
4900 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4901 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4902 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4908 // Memoize the node unless it returns a flag.
4910 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4911 FoldingSetNodeID ID;
4912 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4914 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4915 return SDValue(E, 0);
4918 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4919 DL.getDebugLoc(), VTList, Ops[0]);
4920 } else if (NumOps == 2) {
4921 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4922 DL.getDebugLoc(), VTList, Ops[0],
4924 } else if (NumOps == 3) {
4925 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4926 DL.getDebugLoc(), VTList, Ops[0],
4929 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4930 VTList, Ops, NumOps);
4932 CSEMap.InsertNode(N, IP);
4935 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4936 DL.getDebugLoc(), VTList, Ops[0]);
4937 } else if (NumOps == 2) {
4938 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4939 DL.getDebugLoc(), VTList, Ops[0],
4941 } else if (NumOps == 3) {
4942 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4943 DL.getDebugLoc(), VTList, Ops[0],
4946 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4947 VTList, Ops, NumOps);
4950 AllNodes.push_back(N);
4954 return SDValue(N, 0);
4957 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4958 return getNode(Opcode, DL, VTList, 0, 0);
4961 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4963 SDValue Ops[] = { N1 };
4964 return getNode(Opcode, DL, VTList, Ops, 1);
4967 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4968 SDValue N1, SDValue N2) {
4969 SDValue Ops[] = { N1, N2 };
4970 return getNode(Opcode, DL, VTList, Ops, 2);
4973 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4974 SDValue N1, SDValue N2, SDValue N3) {
4975 SDValue Ops[] = { N1, N2, N3 };
4976 return getNode(Opcode, DL, VTList, Ops, 3);
4979 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4980 SDValue N1, SDValue N2, SDValue N3,
4982 SDValue Ops[] = { N1, N2, N3, N4 };
4983 return getNode(Opcode, DL, VTList, Ops, 4);
4986 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4987 SDValue N1, SDValue N2, SDValue N3,
4988 SDValue N4, SDValue N5) {
4989 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4990 return getNode(Opcode, DL, VTList, Ops, 5);
4993 SDVTList SelectionDAG::getVTList(EVT VT) {
4994 return makeVTList(SDNode::getValueTypeList(VT), 1);
4997 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4998 FoldingSetNodeID ID;
5000 ID.AddInteger(VT1.getRawBits());
5001 ID.AddInteger(VT2.getRawBits());
5004 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5005 if (Result == NULL) {
5006 EVT *Array = Allocator.Allocate<EVT>(2);
5009 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5010 VTListMap.InsertNode(Result, IP);
5012 return Result->getSDVTList();
5015 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5016 FoldingSetNodeID ID;
5018 ID.AddInteger(VT1.getRawBits());
5019 ID.AddInteger(VT2.getRawBits());
5020 ID.AddInteger(VT3.getRawBits());
5023 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5024 if (Result == NULL) {
5025 EVT *Array = Allocator.Allocate<EVT>(3);
5029 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5030 VTListMap.InsertNode(Result, IP);
5032 return Result->getSDVTList();
5035 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5036 FoldingSetNodeID ID;
5038 ID.AddInteger(VT1.getRawBits());
5039 ID.AddInteger(VT2.getRawBits());
5040 ID.AddInteger(VT3.getRawBits());
5041 ID.AddInteger(VT4.getRawBits());
5044 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5045 if (Result == NULL) {
5046 EVT *Array = Allocator.Allocate<EVT>(4);
5051 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5052 VTListMap.InsertNode(Result, IP);
5054 return Result->getSDVTList();
5057 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5058 FoldingSetNodeID ID;
5059 ID.AddInteger(NumVTs);
5060 for (unsigned index = 0; index < NumVTs; index++) {
5061 ID.AddInteger(VTs[index].getRawBits());
5065 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5066 if (Result == NULL) {
5067 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5068 std::copy(VTs, VTs + NumVTs, Array);
5069 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5070 VTListMap.InsertNode(Result, IP);
5072 return Result->getSDVTList();
5076 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5077 /// specified operands. If the resultant node already exists in the DAG,
5078 /// this does not modify the specified node, instead it returns the node that
5079 /// already exists. If the resultant node does not exist in the DAG, the
5080 /// input node is returned. As a degenerate case, if you specify the same
5081 /// input operands as the node already has, the input node is returned.
5082 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5083 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5085 // Check to see if there is no change.
5086 if (Op == N->getOperand(0)) return N;
5088 // See if the modified node already exists.
5089 void *InsertPos = 0;
5090 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5093 // Nope it doesn't. Remove the node from its current place in the maps.
5095 if (!RemoveNodeFromCSEMaps(N))
5098 // Now we update the operands.
5099 N->OperandList[0].set(Op);
5101 // If this gets put into a CSE map, add it.
5102 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5106 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5107 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5109 // Check to see if there is no change.
5110 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5111 return N; // No operands changed, just return the input node.
5113 // See if the modified node already exists.
5114 void *InsertPos = 0;
5115 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5118 // Nope it doesn't. Remove the node from its current place in the maps.
5120 if (!RemoveNodeFromCSEMaps(N))
5123 // Now we update the operands.
5124 if (N->OperandList[0] != Op1)
5125 N->OperandList[0].set(Op1);
5126 if (N->OperandList[1] != Op2)
5127 N->OperandList[1].set(Op2);
5129 // If this gets put into a CSE map, add it.
5130 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5134 SDNode *SelectionDAG::
5135 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5136 SDValue Ops[] = { Op1, Op2, Op3 };
5137 return UpdateNodeOperands(N, Ops, 3);
5140 SDNode *SelectionDAG::
5141 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5142 SDValue Op3, SDValue Op4) {
5143 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5144 return UpdateNodeOperands(N, Ops, 4);
5147 SDNode *SelectionDAG::
5148 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5149 SDValue Op3, SDValue Op4, SDValue Op5) {
5150 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5151 return UpdateNodeOperands(N, Ops, 5);
5154 SDNode *SelectionDAG::
5155 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5156 assert(N->getNumOperands() == NumOps &&
5157 "Update with wrong number of operands");
5159 // Check to see if there is no change.
5160 bool AnyChange = false;
5161 for (unsigned i = 0; i != NumOps; ++i) {
5162 if (Ops[i] != N->getOperand(i)) {
5168 // No operands changed, just return the input node.
5169 if (!AnyChange) return N;
5171 // See if the modified node already exists.
5172 void *InsertPos = 0;
5173 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5176 // Nope it doesn't. Remove the node from its current place in the maps.
5178 if (!RemoveNodeFromCSEMaps(N))
5181 // Now we update the operands.
5182 for (unsigned i = 0; i != NumOps; ++i)
5183 if (N->OperandList[i] != Ops[i])
5184 N->OperandList[i].set(Ops[i]);
5186 // If this gets put into a CSE map, add it.
5187 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5191 /// DropOperands - Release the operands and set this node to have
5193 void SDNode::DropOperands() {
5194 // Unlike the code in MorphNodeTo that does this, we don't need to
5195 // watch for dead nodes here.
5196 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5202 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5205 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5207 SDVTList VTs = getVTList(VT);
5208 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5211 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5212 EVT VT, SDValue Op1) {
5213 SDVTList VTs = getVTList(VT);
5214 SDValue Ops[] = { Op1 };
5215 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5218 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5219 EVT VT, SDValue Op1,
5221 SDVTList VTs = getVTList(VT);
5222 SDValue Ops[] = { Op1, Op2 };
5223 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5226 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5227 EVT VT, SDValue Op1,
5228 SDValue Op2, SDValue Op3) {
5229 SDVTList VTs = getVTList(VT);
5230 SDValue Ops[] = { Op1, Op2, Op3 };
5231 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5234 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5235 EVT VT, const SDValue *Ops,
5237 SDVTList VTs = getVTList(VT);
5238 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5241 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5242 EVT VT1, EVT VT2, const SDValue *Ops,
5244 SDVTList VTs = getVTList(VT1, VT2);
5245 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5248 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5250 SDVTList VTs = getVTList(VT1, VT2);
5251 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5254 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5255 EVT VT1, EVT VT2, EVT VT3,
5256 const SDValue *Ops, unsigned NumOps) {
5257 SDVTList VTs = getVTList(VT1, VT2, VT3);
5258 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5261 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5262 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5263 const SDValue *Ops, unsigned NumOps) {
5264 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5265 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5268 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5271 SDVTList VTs = getVTList(VT1, VT2);
5272 SDValue Ops[] = { Op1 };
5273 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5276 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5278 SDValue Op1, SDValue Op2) {
5279 SDVTList VTs = getVTList(VT1, VT2);
5280 SDValue Ops[] = { Op1, Op2 };
5281 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5284 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 SDValue Op1, SDValue Op2,
5288 SDVTList VTs = getVTList(VT1, VT2);
5289 SDValue Ops[] = { Op1, Op2, Op3 };
5290 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5293 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5294 EVT VT1, EVT VT2, EVT VT3,
5295 SDValue Op1, SDValue Op2,
5297 SDVTList VTs = getVTList(VT1, VT2, VT3);
5298 SDValue Ops[] = { Op1, Op2, Op3 };
5299 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5302 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5303 SDVTList VTs, const SDValue *Ops,
5305 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5306 // Reset the NodeID to -1.
5311 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5312 /// the line number information on the merged node since it is not possible to
5313 /// preserve the information that operation is associated with multiple lines.
5314 /// This will make the debugger working better at -O0, were there is a higher
5315 /// probability having other instructions associated with that line.
5317 /// For IROrder, we keep the smaller of the two
5318 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5319 DebugLoc NLoc = N->getDebugLoc();
5320 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5321 (OLoc.getDebugLoc() != NLoc)) {
5322 N->setDebugLoc(DebugLoc());
5324 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5325 N->setIROrder(Order);
5329 /// MorphNodeTo - This *mutates* the specified node to have the specified
5330 /// return type, opcode, and operands.
5332 /// Note that MorphNodeTo returns the resultant node. If there is already a
5333 /// node of the specified opcode and operands, it returns that node instead of
5334 /// the current one. Note that the SDLoc need not be the same.
5336 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5337 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5338 /// node, and because it doesn't require CSE recalculation for any of
5339 /// the node's users.
5341 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5342 SDVTList VTs, const SDValue *Ops,
5344 // If an identical node already exists, use it.
5346 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5347 FoldingSetNodeID ID;
5348 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5349 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5350 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5353 if (!RemoveNodeFromCSEMaps(N))
5356 // Start the morphing.
5358 N->ValueList = VTs.VTs;
5359 N->NumValues = VTs.NumVTs;
5361 // Clear the operands list, updating used nodes to remove this from their
5362 // use list. Keep track of any operands that become dead as a result.
5363 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5364 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5366 SDNode *Used = Use.getNode();
5368 if (Used->use_empty())
5369 DeadNodeSet.insert(Used);
5372 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5373 // Initialize the memory references information.
5374 MN->setMemRefs(0, 0);
5375 // If NumOps is larger than the # of operands we can have in a
5376 // MachineSDNode, reallocate the operand list.
5377 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5378 if (MN->OperandsNeedDelete)
5379 delete[] MN->OperandList;
5380 if (NumOps > array_lengthof(MN->LocalOperands))
5381 // We're creating a final node that will live unmorphed for the
5382 // remainder of the current SelectionDAG iteration, so we can allocate
5383 // the operands directly out of a pool with no recycling metadata.
5384 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5387 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5388 MN->OperandsNeedDelete = false;
5390 MN->InitOperands(MN->OperandList, Ops, NumOps);
5392 // If NumOps is larger than the # of operands we currently have, reallocate
5393 // the operand list.
5394 if (NumOps > N->NumOperands) {
5395 if (N->OperandsNeedDelete)
5396 delete[] N->OperandList;
5397 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5398 N->OperandsNeedDelete = true;
5400 N->InitOperands(N->OperandList, Ops, NumOps);
5403 // Delete any nodes that are still dead after adding the uses for the
5405 if (!DeadNodeSet.empty()) {
5406 SmallVector<SDNode *, 16> DeadNodes;
5407 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5408 E = DeadNodeSet.end(); I != E; ++I)
5409 if ((*I)->use_empty())
5410 DeadNodes.push_back(*I);
5411 RemoveDeadNodes(DeadNodes);
5415 CSEMap.InsertNode(N, IP); // Memoize the new node.
5420 /// getMachineNode - These are used for target selectors to create a new node
5421 /// with specified return type(s), MachineInstr opcode, and operands.
5423 /// Note that getMachineNode returns the resultant node. If there is already a
5424 /// node of the specified opcode and operands, it returns that node instead of
5425 /// the current one.
5427 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5428 SDVTList VTs = getVTList(VT);
5429 return getMachineNode(Opcode, dl, VTs, None);
5433 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5434 SDVTList VTs = getVTList(VT);
5435 SDValue Ops[] = { Op1 };
5436 return getMachineNode(Opcode, dl, VTs, Ops);
5440 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5441 SDValue Op1, SDValue Op2) {
5442 SDVTList VTs = getVTList(VT);
5443 SDValue Ops[] = { Op1, Op2 };
5444 return getMachineNode(Opcode, dl, VTs, Ops);
5448 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5449 SDValue Op1, SDValue Op2, SDValue Op3) {
5450 SDVTList VTs = getVTList(VT);
5451 SDValue Ops[] = { Op1, Op2, Op3 };
5452 return getMachineNode(Opcode, dl, VTs, Ops);
5456 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5457 ArrayRef<SDValue> Ops) {
5458 SDVTList VTs = getVTList(VT);
5459 return getMachineNode(Opcode, dl, VTs, Ops);
5463 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5464 SDVTList VTs = getVTList(VT1, VT2);
5465 return getMachineNode(Opcode, dl, VTs, None);
5469 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5470 EVT VT1, EVT VT2, SDValue Op1) {
5471 SDVTList VTs = getVTList(VT1, VT2);
5472 SDValue Ops[] = { Op1 };
5473 return getMachineNode(Opcode, dl, VTs, Ops);
5477 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5478 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5479 SDVTList VTs = getVTList(VT1, VT2);
5480 SDValue Ops[] = { Op1, Op2 };
5481 return getMachineNode(Opcode, dl, VTs, Ops);
5485 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5486 EVT VT1, EVT VT2, SDValue Op1,
5487 SDValue Op2, SDValue Op3) {
5488 SDVTList VTs = getVTList(VT1, VT2);
5489 SDValue Ops[] = { Op1, Op2, Op3 };
5490 return getMachineNode(Opcode, dl, VTs, Ops);
5494 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5496 ArrayRef<SDValue> Ops) {
5497 SDVTList VTs = getVTList(VT1, VT2);
5498 return getMachineNode(Opcode, dl, VTs, Ops);
5502 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5503 EVT VT1, EVT VT2, EVT VT3,
5504 SDValue Op1, SDValue Op2) {
5505 SDVTList VTs = getVTList(VT1, VT2, VT3);
5506 SDValue Ops[] = { Op1, Op2 };
5507 return getMachineNode(Opcode, dl, VTs, Ops);
5511 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5512 EVT VT1, EVT VT2, EVT VT3,
5513 SDValue Op1, SDValue Op2, SDValue Op3) {
5514 SDVTList VTs = getVTList(VT1, VT2, VT3);
5515 SDValue Ops[] = { Op1, Op2, Op3 };
5516 return getMachineNode(Opcode, dl, VTs, Ops);
5520 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5521 EVT VT1, EVT VT2, EVT VT3,
5522 ArrayRef<SDValue> Ops) {
5523 SDVTList VTs = getVTList(VT1, VT2, VT3);
5524 return getMachineNode(Opcode, dl, VTs, Ops);
5528 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5529 EVT VT2, EVT VT3, EVT VT4,
5530 ArrayRef<SDValue> Ops) {
5531 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5532 return getMachineNode(Opcode, dl, VTs, Ops);
5536 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5537 ArrayRef<EVT> ResultTys,
5538 ArrayRef<SDValue> Ops) {
5539 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5540 return getMachineNode(Opcode, dl, VTs, Ops);
5544 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5545 ArrayRef<SDValue> OpsArray) {
5546 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5549 const SDValue *Ops = OpsArray.data();
5550 unsigned NumOps = OpsArray.size();
5553 FoldingSetNodeID ID;
5554 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5556 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5557 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5561 // Allocate a new MachineSDNode.
5562 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5563 DL.getDebugLoc(), VTs);
5565 // Initialize the operands list.
5566 if (NumOps > array_lengthof(N->LocalOperands))
5567 // We're creating a final node that will live unmorphed for the
5568 // remainder of the current SelectionDAG iteration, so we can allocate
5569 // the operands directly out of a pool with no recycling metadata.
5570 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5573 N->InitOperands(N->LocalOperands, Ops, NumOps);
5574 N->OperandsNeedDelete = false;
5577 CSEMap.InsertNode(N, IP);
5579 AllNodes.push_back(N);
5581 VerifyMachineNode(N);
5586 /// getTargetExtractSubreg - A convenience function for creating
5587 /// TargetOpcode::EXTRACT_SUBREG nodes.
5589 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5591 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5592 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5593 VT, Operand, SRIdxVal);
5594 return SDValue(Subreg, 0);
5597 /// getTargetInsertSubreg - A convenience function for creating
5598 /// TargetOpcode::INSERT_SUBREG nodes.
5600 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5601 SDValue Operand, SDValue Subreg) {
5602 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5603 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5604 VT, Operand, Subreg, SRIdxVal);
5605 return SDValue(Result, 0);
5608 /// getNodeIfExists - Get the specified node if it's already available, or
5609 /// else return NULL.
5610 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5611 const SDValue *Ops, unsigned NumOps) {
5612 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5613 FoldingSetNodeID ID;
5614 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5616 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5622 /// getDbgValue - Creates a SDDbgValue node.
5625 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5626 DebugLoc DL, unsigned O) {
5627 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5631 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5632 DebugLoc DL, unsigned O) {
5633 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5637 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5638 DebugLoc DL, unsigned O) {
5639 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5644 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5645 /// pointed to by a use iterator is deleted, increment the use iterator
5646 /// so that it doesn't dangle.
5648 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5649 SDNode::use_iterator &UI;
5650 SDNode::use_iterator &UE;
5652 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5653 // Increment the iterator as needed.
5654 while (UI != UE && N == *UI)
5659 RAUWUpdateListener(SelectionDAG &d,
5660 SDNode::use_iterator &ui,
5661 SDNode::use_iterator &ue)
5662 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5667 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5668 /// This can cause recursive merging of nodes in the DAG.
5670 /// This version assumes From has a single result value.
5672 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5673 SDNode *From = FromN.getNode();
5674 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5675 "Cannot replace with this method!");
5676 assert(From != To.getNode() && "Cannot replace uses of with self");
5678 // Iterate over all the existing uses of From. New uses will be added
5679 // to the beginning of the use list, which we avoid visiting.
5680 // This specifically avoids visiting uses of From that arise while the
5681 // replacement is happening, because any such uses would be the result
5682 // of CSE: If an existing node looks like From after one of its operands
5683 // is replaced by To, we don't want to replace of all its users with To
5684 // too. See PR3018 for more info.
5685 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5686 RAUWUpdateListener Listener(*this, UI, UE);
5690 // This node is about to morph, remove its old self from the CSE maps.
5691 RemoveNodeFromCSEMaps(User);
5693 // A user can appear in a use list multiple times, and when this
5694 // happens the uses are usually next to each other in the list.
5695 // To help reduce the number of CSE recomputations, process all
5696 // the uses of this user that we can find this way.
5698 SDUse &Use = UI.getUse();
5701 } while (UI != UE && *UI == User);
5703 // Now that we have modified User, add it back to the CSE maps. If it
5704 // already exists there, recursively merge the results together.
5705 AddModifiedNodeToCSEMaps(User);
5708 // If we just RAUW'd the root, take note.
5709 if (FromN == getRoot())
5713 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5714 /// This can cause recursive merging of nodes in the DAG.
5716 /// This version assumes that for each value of From, there is a
5717 /// corresponding value in To in the same position with the same type.
5719 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5721 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5722 assert((!From->hasAnyUseOfValue(i) ||
5723 From->getValueType(i) == To->getValueType(i)) &&
5724 "Cannot use this version of ReplaceAllUsesWith!");
5727 // Handle the trivial case.
5731 // Iterate over just the existing users of From. See the comments in
5732 // the ReplaceAllUsesWith above.
5733 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5734 RAUWUpdateListener Listener(*this, UI, UE);
5738 // This node is about to morph, remove its old self from the CSE maps.
5739 RemoveNodeFromCSEMaps(User);
5741 // A user can appear in a use list multiple times, and when this
5742 // happens the uses are usually next to each other in the list.
5743 // To help reduce the number of CSE recomputations, process all
5744 // the uses of this user that we can find this way.
5746 SDUse &Use = UI.getUse();
5749 } while (UI != UE && *UI == User);
5751 // Now that we have modified User, add it back to the CSE maps. If it
5752 // already exists there, recursively merge the results together.
5753 AddModifiedNodeToCSEMaps(User);
5756 // If we just RAUW'd the root, take note.
5757 if (From == getRoot().getNode())
5758 setRoot(SDValue(To, getRoot().getResNo()));
5761 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5762 /// This can cause recursive merging of nodes in the DAG.
5764 /// This version can replace From with any result values. To must match the
5765 /// number and types of values returned by From.
5766 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5767 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5768 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5770 // Iterate over just the existing users of From. See the comments in
5771 // the ReplaceAllUsesWith above.
5772 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5773 RAUWUpdateListener Listener(*this, UI, UE);
5777 // This node is about to morph, remove its old self from the CSE maps.
5778 RemoveNodeFromCSEMaps(User);
5780 // A user can appear in a use list multiple times, and when this
5781 // happens the uses are usually next to each other in the list.
5782 // To help reduce the number of CSE recomputations, process all
5783 // the uses of this user that we can find this way.
5785 SDUse &Use = UI.getUse();
5786 const SDValue &ToOp = To[Use.getResNo()];
5789 } while (UI != UE && *UI == User);
5791 // Now that we have modified User, add it back to the CSE maps. If it
5792 // already exists there, recursively merge the results together.
5793 AddModifiedNodeToCSEMaps(User);
5796 // If we just RAUW'd the root, take note.
5797 if (From == getRoot().getNode())
5798 setRoot(SDValue(To[getRoot().getResNo()]));
5801 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5802 /// uses of other values produced by From.getNode() alone. The Deleted
5803 /// vector is handled the same way as for ReplaceAllUsesWith.
5804 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5805 // Handle the really simple, really trivial case efficiently.
5806 if (From == To) return;
5808 // Handle the simple, trivial, case efficiently.
5809 if (From.getNode()->getNumValues() == 1) {
5810 ReplaceAllUsesWith(From, To);
5814 // Iterate over just the existing users of From. See the comments in
5815 // the ReplaceAllUsesWith above.
5816 SDNode::use_iterator UI = From.getNode()->use_begin(),
5817 UE = From.getNode()->use_end();
5818 RAUWUpdateListener Listener(*this, UI, UE);
5821 bool UserRemovedFromCSEMaps = false;
5823 // A user can appear in a use list multiple times, and when this
5824 // happens the uses are usually next to each other in the list.
5825 // To help reduce the number of CSE recomputations, process all
5826 // the uses of this user that we can find this way.
5828 SDUse &Use = UI.getUse();
5830 // Skip uses of different values from the same node.
5831 if (Use.getResNo() != From.getResNo()) {
5836 // If this node hasn't been modified yet, it's still in the CSE maps,
5837 // so remove its old self from the CSE maps.
5838 if (!UserRemovedFromCSEMaps) {
5839 RemoveNodeFromCSEMaps(User);
5840 UserRemovedFromCSEMaps = true;
5845 } while (UI != UE && *UI == User);
5847 // We are iterating over all uses of the From node, so if a use
5848 // doesn't use the specific value, no changes are made.
5849 if (!UserRemovedFromCSEMaps)
5852 // Now that we have modified User, add it back to the CSE maps. If it
5853 // already exists there, recursively merge the results together.
5854 AddModifiedNodeToCSEMaps(User);
5857 // If we just RAUW'd the root, take note.
5858 if (From == getRoot())
5863 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5864 /// to record information about a use.
5871 /// operator< - Sort Memos by User.
5872 bool operator<(const UseMemo &L, const UseMemo &R) {
5873 return (intptr_t)L.User < (intptr_t)R.User;
5877 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5878 /// uses of other values produced by From.getNode() alone. The same value
5879 /// may appear in both the From and To list. The Deleted vector is
5880 /// handled the same way as for ReplaceAllUsesWith.
5881 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5884 // Handle the simple, trivial case efficiently.
5886 return ReplaceAllUsesOfValueWith(*From, *To);
5888 // Read up all the uses and make records of them. This helps
5889 // processing new uses that are introduced during the
5890 // replacement process.
5891 SmallVector<UseMemo, 4> Uses;
5892 for (unsigned i = 0; i != Num; ++i) {
5893 unsigned FromResNo = From[i].getResNo();
5894 SDNode *FromNode = From[i].getNode();
5895 for (SDNode::use_iterator UI = FromNode->use_begin(),
5896 E = FromNode->use_end(); UI != E; ++UI) {
5897 SDUse &Use = UI.getUse();
5898 if (Use.getResNo() == FromResNo) {
5899 UseMemo Memo = { *UI, i, &Use };
5900 Uses.push_back(Memo);
5905 // Sort the uses, so that all the uses from a given User are together.
5906 std::sort(Uses.begin(), Uses.end());
5908 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5909 UseIndex != UseIndexEnd; ) {
5910 // We know that this user uses some value of From. If it is the right
5911 // value, update it.
5912 SDNode *User = Uses[UseIndex].User;
5914 // This node is about to morph, remove its old self from the CSE maps.
5915 RemoveNodeFromCSEMaps(User);
5917 // The Uses array is sorted, so all the uses for a given User
5918 // are next to each other in the list.
5919 // To help reduce the number of CSE recomputations, process all
5920 // the uses of this user that we can find this way.
5922 unsigned i = Uses[UseIndex].Index;
5923 SDUse &Use = *Uses[UseIndex].Use;
5927 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5929 // Now that we have modified User, add it back to the CSE maps. If it
5930 // already exists there, recursively merge the results together.
5931 AddModifiedNodeToCSEMaps(User);
5935 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5936 /// based on their topological order. It returns the maximum id and a vector
5937 /// of the SDNodes* in assigned order by reference.
5938 unsigned SelectionDAG::AssignTopologicalOrder() {
5940 unsigned DAGSize = 0;
5942 // SortedPos tracks the progress of the algorithm. Nodes before it are
5943 // sorted, nodes after it are unsorted. When the algorithm completes
5944 // it is at the end of the list.
5945 allnodes_iterator SortedPos = allnodes_begin();
5947 // Visit all the nodes. Move nodes with no operands to the front of
5948 // the list immediately. Annotate nodes that do have operands with their
5949 // operand count. Before we do this, the Node Id fields of the nodes
5950 // may contain arbitrary values. After, the Node Id fields for nodes
5951 // before SortedPos will contain the topological sort index, and the
5952 // Node Id fields for nodes At SortedPos and after will contain the
5953 // count of outstanding operands.
5954 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5957 unsigned Degree = N->getNumOperands();
5959 // A node with no uses, add it to the result array immediately.
5960 N->setNodeId(DAGSize++);
5961 allnodes_iterator Q = N;
5963 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5964 assert(SortedPos != AllNodes.end() && "Overran node list");
5967 // Temporarily use the Node Id as scratch space for the degree count.
5968 N->setNodeId(Degree);
5972 // Visit all the nodes. As we iterate, move nodes into sorted order,
5973 // such that by the time the end is reached all nodes will be sorted.
5974 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5977 // N is in sorted position, so all its uses have one less operand
5978 // that needs to be sorted.
5979 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5982 unsigned Degree = P->getNodeId();
5983 assert(Degree != 0 && "Invalid node degree");
5986 // All of P's operands are sorted, so P may sorted now.
5987 P->setNodeId(DAGSize++);
5989 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5990 assert(SortedPos != AllNodes.end() && "Overran node list");
5993 // Update P's outstanding operand count.
5994 P->setNodeId(Degree);
5997 if (I == SortedPos) {
6000 dbgs() << "Overran sorted position:\n";
6003 llvm_unreachable(0);
6007 assert(SortedPos == AllNodes.end() &&
6008 "Topological sort incomplete!");
6009 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6010 "First node in topological sort is not the entry token!");
6011 assert(AllNodes.front().getNodeId() == 0 &&
6012 "First node in topological sort has non-zero id!");
6013 assert(AllNodes.front().getNumOperands() == 0 &&
6014 "First node in topological sort has operands!");
6015 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6016 "Last node in topologic sort has unexpected id!");
6017 assert(AllNodes.back().use_empty() &&
6018 "Last node in topologic sort has users!");
6019 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6023 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6024 /// value is produced by SD.
6025 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6026 DbgInfo->add(DB, SD, isParameter);
6028 SD->setHasDebugValue(true);
6031 /// TransferDbgValues - Transfer SDDbgValues.
6032 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6033 if (From == To || !From.getNode()->getHasDebugValue())
6035 SDNode *FromNode = From.getNode();
6036 SDNode *ToNode = To.getNode();
6037 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6038 SmallVector<SDDbgValue *, 2> ClonedDVs;
6039 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6041 SDDbgValue *Dbg = *I;
6042 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6043 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6044 Dbg->getOffset(), Dbg->getDebugLoc(),
6046 ClonedDVs.push_back(Clone);
6049 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6050 E = ClonedDVs.end(); I != E; ++I)
6051 AddDbgValue(*I, ToNode, false);
6054 //===----------------------------------------------------------------------===//
6056 //===----------------------------------------------------------------------===//
6058 HandleSDNode::~HandleSDNode() {
6062 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6063 DebugLoc DL, const GlobalValue *GA,
6064 EVT VT, int64_t o, unsigned char TF)
6065 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6069 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6070 SDValue X, unsigned SrcAS,
6072 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6073 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6075 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6076 EVT memvt, MachineMemOperand *mmo)
6077 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6078 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6079 MMO->isNonTemporal(), MMO->isInvariant());
6080 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6081 assert(isNonTemporal() == MMO->isNonTemporal() &&
6082 "Non-temporal encoding error!");
6083 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6086 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6087 const SDValue *Ops, unsigned NumOps, EVT memvt,
6088 MachineMemOperand *mmo)
6089 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6090 MemoryVT(memvt), MMO(mmo) {
6091 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6092 MMO->isNonTemporal(), MMO->isInvariant());
6093 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6094 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6097 /// Profile - Gather unique data for the node.
6099 void SDNode::Profile(FoldingSetNodeID &ID) const {
6100 AddNodeIDNode(ID, this);
6105 std::vector<EVT> VTs;
6108 VTs.reserve(MVT::LAST_VALUETYPE);
6109 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6110 VTs.push_back(MVT((MVT::SimpleValueType)i));
6115 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6116 static ManagedStatic<EVTArray> SimpleVTArray;
6117 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6119 /// getValueTypeList - Return a pointer to the specified value type.
6121 const EVT *SDNode::getValueTypeList(EVT VT) {
6122 if (VT.isExtended()) {
6123 sys::SmartScopedLock<true> Lock(*VTMutex);
6124 return &(*EVTs->insert(VT).first);
6126 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6127 "Value type out of range!");
6128 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6132 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6133 /// indicated value. This method ignores uses of other values defined by this
6135 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6136 assert(Value < getNumValues() && "Bad value!");
6138 // TODO: Only iterate over uses of a given value of the node
6139 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6140 if (UI.getUse().getResNo() == Value) {
6147 // Found exactly the right number of uses?
6152 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6153 /// value. This method ignores uses of other values defined by this operation.
6154 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6155 assert(Value < getNumValues() && "Bad value!");
6157 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6158 if (UI.getUse().getResNo() == Value)
6165 /// isOnlyUserOf - Return true if this node is the only use of N.
6167 bool SDNode::isOnlyUserOf(SDNode *N) const {
6169 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6180 /// isOperand - Return true if this node is an operand of N.
6182 bool SDValue::isOperandOf(SDNode *N) const {
6183 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6184 if (*this == N->getOperand(i))
6189 bool SDNode::isOperandOf(SDNode *N) const {
6190 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6191 if (this == N->OperandList[i].getNode())
6196 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6197 /// be a chain) reaches the specified operand without crossing any
6198 /// side-effecting instructions on any chain path. In practice, this looks
6199 /// through token factors and non-volatile loads. In order to remain efficient,
6200 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6201 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6202 unsigned Depth) const {
6203 if (*this == Dest) return true;
6205 // Don't search too deeply, we just want to be able to see through
6206 // TokenFactor's etc.
6207 if (Depth == 0) return false;
6209 // If this is a token factor, all inputs to the TF happen in parallel. If any
6210 // of the operands of the TF does not reach dest, then we cannot do the xform.
6211 if (getOpcode() == ISD::TokenFactor) {
6212 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6213 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6218 // Loads don't have side effects, look through them.
6219 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6220 if (!Ld->isVolatile())
6221 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6226 /// hasPredecessor - Return true if N is a predecessor of this node.
6227 /// N is either an operand of this node, or can be reached by recursively
6228 /// traversing up the operands.
6229 /// NOTE: This is an expensive method. Use it carefully.
6230 bool SDNode::hasPredecessor(const SDNode *N) const {
6231 SmallPtrSet<const SDNode *, 32> Visited;
6232 SmallVector<const SDNode *, 16> Worklist;
6233 return hasPredecessorHelper(N, Visited, Worklist);
6237 SDNode::hasPredecessorHelper(const SDNode *N,
6238 SmallPtrSet<const SDNode *, 32> &Visited,
6239 SmallVectorImpl<const SDNode *> &Worklist) const {
6240 if (Visited.empty()) {
6241 Worklist.push_back(this);
6243 // Take a look in the visited set. If we've already encountered this node
6244 // we needn't search further.
6245 if (Visited.count(N))
6249 // Haven't visited N yet. Continue the search.
6250 while (!Worklist.empty()) {
6251 const SDNode *M = Worklist.pop_back_val();
6252 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6253 SDNode *Op = M->getOperand(i).getNode();
6254 if (Visited.insert(Op))
6255 Worklist.push_back(Op);
6264 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6265 assert(Num < NumOperands && "Invalid child # of SDNode!");
6266 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6269 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6270 assert(N->getNumValues() == 1 &&
6271 "Can't unroll a vector with multiple results!");
6273 EVT VT = N->getValueType(0);
6274 unsigned NE = VT.getVectorNumElements();
6275 EVT EltVT = VT.getVectorElementType();
6278 SmallVector<SDValue, 8> Scalars;
6279 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6281 // If ResNE is 0, fully unroll the vector op.
6284 else if (NE > ResNE)
6288 for (i= 0; i != NE; ++i) {
6289 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6290 SDValue Operand = N->getOperand(j);
6291 EVT OperandVT = Operand.getValueType();
6292 if (OperandVT.isVector()) {
6293 // A vector operand; extract a single element.
6294 const TargetLowering *TLI = TM.getTargetLowering();
6295 EVT OperandEltVT = OperandVT.getVectorElementType();
6296 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6299 getConstant(i, TLI->getVectorIdxTy()));
6301 // A scalar operand; just use it as is.
6302 Operands[j] = Operand;
6306 switch (N->getOpcode()) {
6308 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6309 &Operands[0], Operands.size()));
6312 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6313 &Operands[0], Operands.size()));
6320 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6321 getShiftAmountOperand(Operands[0].getValueType(),
6324 case ISD::SIGN_EXTEND_INREG:
6325 case ISD::FP_ROUND_INREG: {
6326 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6327 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6329 getValueType(ExtVT)));
6334 for (; i < ResNE; ++i)
6335 Scalars.push_back(getUNDEF(EltVT));
6337 return getNode(ISD::BUILD_VECTOR, dl,
6338 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6339 &Scalars[0], Scalars.size());
6343 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6344 /// location that is 'Dist' units away from the location that the 'Base' load
6345 /// is loading from.
6346 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6347 unsigned Bytes, int Dist) const {
6348 if (LD->getChain() != Base->getChain())
6350 EVT VT = LD->getValueType(0);
6351 if (VT.getSizeInBits() / 8 != Bytes)
6354 SDValue Loc = LD->getOperand(1);
6355 SDValue BaseLoc = Base->getOperand(1);
6356 if (Loc.getOpcode() == ISD::FrameIndex) {
6357 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6359 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6360 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6361 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6362 int FS = MFI->getObjectSize(FI);
6363 int BFS = MFI->getObjectSize(BFI);
6364 if (FS != BFS || FS != (int)Bytes) return false;
6365 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6369 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6370 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6373 const GlobalValue *GV1 = NULL;
6374 const GlobalValue *GV2 = NULL;
6375 int64_t Offset1 = 0;
6376 int64_t Offset2 = 0;
6377 const TargetLowering *TLI = TM.getTargetLowering();
6378 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6379 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6380 if (isGA1 && isGA2 && GV1 == GV2)
6381 return Offset1 == (Offset2 + Dist*Bytes);
6386 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6387 /// it cannot be inferred.
6388 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6389 // If this is a GlobalAddress + cst, return the alignment.
6390 const GlobalValue *GV;
6391 int64_t GVOffset = 0;
6392 const TargetLowering *TLI = TM.getTargetLowering();
6393 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6394 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6395 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6396 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6397 TLI->getDataLayout());
6398 unsigned AlignBits = KnownZero.countTrailingOnes();
6399 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6401 return MinAlign(Align, GVOffset);
6404 // If this is a direct reference to a stack slot, use information about the
6405 // stack slot's alignment.
6406 int FrameIdx = 1 << 31;
6407 int64_t FrameOffset = 0;
6408 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6409 FrameIdx = FI->getIndex();
6410 } else if (isBaseWithConstantOffset(Ptr) &&
6411 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6413 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6414 FrameOffset = Ptr.getConstantOperandVal(1);
6417 if (FrameIdx != (1 << 31)) {
6418 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6419 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6427 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6428 /// which is split (or expanded) into two not necessarily identical pieces.
6429 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6430 // Currently all types are split in half.
6432 if (!VT.isVector()) {
6433 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6435 unsigned NumElements = VT.getVectorNumElements();
6436 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6437 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6440 return std::make_pair(LoVT, HiVT);
6443 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6445 std::pair<SDValue, SDValue>
6446 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6448 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6449 N.getValueType().getVectorNumElements() &&
6450 "More vector elements requested than available!");
6452 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6453 getConstant(0, TLI->getVectorIdxTy()));
6454 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6455 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6456 return std::make_pair(Lo, Hi);
6459 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6460 unsigned GlobalAddressSDNode::getAddressSpace() const {
6461 return getGlobal()->getType()->getAddressSpace();
6465 Type *ConstantPoolSDNode::getType() const {
6466 if (isMachineConstantPoolEntry())
6467 return Val.MachineCPVal->getType();
6468 return Val.ConstVal->getType();
6471 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6473 unsigned &SplatBitSize,
6475 unsigned MinSplatBits,
6477 EVT VT = getValueType(0);
6478 assert(VT.isVector() && "Expected a vector type");
6479 unsigned sz = VT.getSizeInBits();
6480 if (MinSplatBits > sz)
6483 SplatValue = APInt(sz, 0);
6484 SplatUndef = APInt(sz, 0);
6486 // Get the bits. Bits with undefined values (when the corresponding element
6487 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6488 // in SplatValue. If any of the values are not constant, give up and return
6490 unsigned int nOps = getNumOperands();
6491 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6492 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6494 for (unsigned j = 0; j < nOps; ++j) {
6495 unsigned i = isBigEndian ? nOps-1-j : j;
6496 SDValue OpVal = getOperand(i);
6497 unsigned BitPos = j * EltBitSize;
6499 if (OpVal.getOpcode() == ISD::UNDEF)
6500 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6501 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6502 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6503 zextOrTrunc(sz) << BitPos;
6504 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6505 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6510 // The build_vector is all constants or undefs. Find the smallest element
6511 // size that splats the vector.
6513 HasAnyUndefs = (SplatUndef != 0);
6516 unsigned HalfSize = sz / 2;
6517 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6518 APInt LowValue = SplatValue.trunc(HalfSize);
6519 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6520 APInt LowUndef = SplatUndef.trunc(HalfSize);
6522 // If the two halves do not match (ignoring undef bits), stop here.
6523 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6524 MinSplatBits > HalfSize)
6527 SplatValue = HighValue | LowValue;
6528 SplatUndef = HighUndef & LowUndef;
6537 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6538 // Find the first non-undef value in the shuffle mask.
6540 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6543 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6545 // Make sure all remaining elements are either undef or the same as the first
6547 for (int Idx = Mask[i]; i != e; ++i)
6548 if (Mask[i] >= 0 && Mask[i] != Idx)
6554 static void checkForCyclesHelper(const SDNode *N,
6555 SmallPtrSet<const SDNode*, 32> &Visited,
6556 SmallPtrSet<const SDNode*, 32> &Checked) {
6557 // If this node has already been checked, don't check it again.
6558 if (Checked.count(N))
6561 // If a node has already been visited on this depth-first walk, reject it as
6563 if (!Visited.insert(N)) {
6564 dbgs() << "Offending node:\n";
6566 errs() << "Detected cycle in SelectionDAG\n";
6570 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6571 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6578 void llvm::checkForCycles(const llvm::SDNode *N) {
6580 assert(N && "Checking nonexistent SDNode");
6581 SmallPtrSet<const SDNode*, 32> visited;
6582 SmallPtrSet<const SDNode*, 32> checked;
6583 checkForCyclesHelper(N, visited, checked);
6587 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6588 checkForCycles(DAG->getRoot().getNode());