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/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
53 /// makeVTList - Return an instance of the SDVTList struct initialized with the
54 /// specified members.
55 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
56 SDVTList Res = {VTs, NumVTs};
60 // Default null implementations of the callbacks.
61 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
62 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
64 //===----------------------------------------------------------------------===//
65 // ConstantFPSDNode Class
66 //===----------------------------------------------------------------------===//
68 /// isExactlyValue - We don't rely on operator== working on double values, as
69 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
70 /// As such, this method can be used to do an exact bit-for-bit comparison of
71 /// two floating point values.
72 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
73 return getValueAPF().bitwiseIsEqual(V);
76 bool ConstantFPSDNode::isValueValidForType(EVT VT,
78 assert(VT.isFloatingPoint() && "Can only convert between FP types");
80 // convert modifies in place, so make a copy.
81 APFloat Val2 = APFloat(Val);
83 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
84 APFloat::rmNearestTiesToEven,
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 /// isBuildVectorAllOnes - Return true if the specified node is a
94 /// BUILD_VECTOR where all of the elements are ~0 or undef.
95 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96 // Look through a bit convert.
97 if (N->getOpcode() == ISD::BITCAST)
98 N = N->getOperand(0).getNode();
100 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
102 unsigned i = 0, e = N->getNumOperands();
104 // Skip over all of the undef values.
105 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 // Do not accept an all-undef vector.
109 if (i == e) return false;
111 // Do not accept build_vectors that aren't all constants or which have non-~0
112 // elements. We have to be a bit careful here, as the type of the constant
113 // may not be the same as the type of the vector elements due to type
114 // legalization (the elements are promoted to a legal type for the target and
115 // a vector of a type may be legal when the base element type is not).
116 // We only want to check enough bits to cover the vector elements, because
117 // we care if the resultant vector is all ones, not whether the individual
119 SDValue NotZero = N->getOperand(i);
120 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
121 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
122 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
124 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
125 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
130 // Okay, we have at least one ~0 value, check to see if the rest match or are
131 // undefs. Even with the above element type twiddling, this should be OK, as
132 // the same type legalization should have applied to all the elements.
133 for (++i; i != e; ++i)
134 if (N->getOperand(i) != NotZero &&
135 N->getOperand(i).getOpcode() != ISD::UNDEF)
141 /// isBuildVectorAllZeros - Return true if the specified node is a
142 /// BUILD_VECTOR where all of the elements are 0 or undef.
143 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
144 // Look through a bit convert.
145 if (N->getOpcode() == ISD::BITCAST)
146 N = N->getOperand(0).getNode();
148 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
150 unsigned i = 0, e = N->getNumOperands();
152 // Skip over all of the undef values.
153 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept an all-undef vector.
157 if (i == e) return false;
159 // Do not accept build_vectors that aren't all constants or which have non-0
161 SDValue Zero = N->getOperand(i);
162 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
163 if (!CN->isNullValue())
165 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
166 if (!CFPN->getValueAPF().isPosZero())
171 // Okay, we have at least one 0 value, check to see if the rest match or are
173 for (++i; i != e; ++i)
174 if (N->getOperand(i) != Zero &&
175 N->getOperand(i).getOpcode() != ISD::UNDEF)
180 /// \brief Return true if the specified node is a BUILD_VECTOR node of
181 /// all ConstantSDNode or undef.
182 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
183 if (N->getOpcode() != ISD::BUILD_VECTOR)
186 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
187 SDValue Op = N->getOperand(i);
188 if (Op.getOpcode() == ISD::UNDEF)
190 if (!isa<ConstantSDNode>(Op))
196 /// isScalarToVector - Return true if the specified node is a
197 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
198 /// element is not an undef.
199 bool ISD::isScalarToVector(const SDNode *N) {
200 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
207 unsigned NumElems = N->getNumOperands();
210 for (unsigned i = 1; i < NumElems; ++i) {
211 SDValue V = N->getOperand(i);
212 if (V.getOpcode() != ISD::UNDEF)
218 /// allOperandsUndef - Return true if the node has at least one operand
219 /// and all operands of the specified node are ISD::UNDEF.
220 bool ISD::allOperandsUndef(const SDNode *N) {
221 // Return false if the node has no operands.
222 // This is "logically inconsistent" with the definition of "all" but
223 // is probably the desired behavior.
224 if (N->getNumOperands() == 0)
227 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
228 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
234 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
237 return ISD::ANY_EXTEND;
239 return ISD::SIGN_EXTEND;
241 return ISD::ZERO_EXTEND;
246 llvm_unreachable("Invalid LoadExtType");
249 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
250 /// when given the operation for (X op Y).
251 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
252 // To perform this operation, we just need to swap the L and G bits of the
254 unsigned OldL = (Operation >> 2) & 1;
255 unsigned OldG = (Operation >> 1) & 1;
256 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
257 (OldL << 1) | // New G bit
258 (OldG << 2)); // New L bit.
261 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
262 /// 'op' is a valid SetCC operation.
263 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
264 unsigned Operation = Op;
266 Operation ^= 7; // Flip L, G, E bits, but not U.
268 Operation ^= 15; // Flip all of the condition bits.
270 if (Operation > ISD::SETTRUE2)
271 Operation &= ~8; // Don't let N and U bits get set.
273 return ISD::CondCode(Operation);
277 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
278 /// signed operation and 2 if the result is an unsigned comparison. Return zero
279 /// if the operation does not depend on the sign of the input (setne and seteq).
280 static int isSignedOp(ISD::CondCode Opcode) {
282 default: llvm_unreachable("Illegal integer setcc operation!");
284 case ISD::SETNE: return 0;
288 case ISD::SETGE: return 1;
292 case ISD::SETUGE: return 2;
296 /// getSetCCOrOperation - Return the result of a logical OR between different
297 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
298 /// returns SETCC_INVALID if it is not possible to represent the resultant
300 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
302 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
303 // Cannot fold a signed integer setcc with an unsigned integer setcc.
304 return ISD::SETCC_INVALID;
306 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
308 // If the N and U bits get set then the resultant comparison DOES suddenly
309 // care about orderedness, and is true when ordered.
310 if (Op > ISD::SETTRUE2)
311 Op &= ~16; // Clear the U bit if the N bit is set.
313 // Canonicalize illegal integer setcc's.
314 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
317 return ISD::CondCode(Op);
320 /// getSetCCAndOperation - Return the result of a logical AND between different
321 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
322 /// function returns zero if it is not possible to represent the resultant
324 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
326 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
327 // Cannot fold a signed setcc with an unsigned setcc.
328 return ISD::SETCC_INVALID;
330 // Combine all of the condition bits.
331 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
333 // Canonicalize illegal integer setcc's.
337 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
338 case ISD::SETOEQ: // SETEQ & SETU[LG]E
339 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
340 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
341 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
348 //===----------------------------------------------------------------------===//
349 // SDNode Profile Support
350 //===----------------------------------------------------------------------===//
352 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
354 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
359 /// solely with their pointer.
360 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
361 ID.AddPointer(VTList.VTs);
364 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
366 static void AddNodeIDOperands(FoldingSetNodeID &ID,
367 const SDValue *Ops, unsigned NumOps) {
368 for (; NumOps; --NumOps, ++Ops) {
369 ID.AddPointer(Ops->getNode());
370 ID.AddInteger(Ops->getResNo());
374 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
376 static void AddNodeIDOperands(FoldingSetNodeID &ID,
377 const SDUse *Ops, unsigned NumOps) {
378 for (; NumOps; --NumOps, ++Ops) {
379 ID.AddPointer(Ops->getNode());
380 ID.AddInteger(Ops->getResNo());
384 static void AddNodeIDNode(FoldingSetNodeID &ID,
385 unsigned short OpC, SDVTList VTList,
386 const SDValue *OpList, unsigned N) {
387 AddNodeIDOpcode(ID, OpC);
388 AddNodeIDValueTypes(ID, VTList);
389 AddNodeIDOperands(ID, OpList, N);
392 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
394 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
395 switch (N->getOpcode()) {
396 case ISD::TargetExternalSymbol:
397 case ISD::ExternalSymbol:
398 llvm_unreachable("Should only be used on nodes with operands");
399 default: break; // Normal nodes don't need extra info.
400 case ISD::TargetConstant:
401 case ISD::Constant: {
402 const ConstantSDNode *C = cast<ConstantSDNode>(N);
403 ID.AddPointer(C->getConstantIntValue());
404 ID.AddBoolean(C->isOpaque());
407 case ISD::TargetConstantFP:
408 case ISD::ConstantFP: {
409 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
412 case ISD::TargetGlobalAddress:
413 case ISD::GlobalAddress:
414 case ISD::TargetGlobalTLSAddress:
415 case ISD::GlobalTLSAddress: {
416 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
417 ID.AddPointer(GA->getGlobal());
418 ID.AddInteger(GA->getOffset());
419 ID.AddInteger(GA->getTargetFlags());
420 ID.AddInteger(GA->getAddressSpace());
423 case ISD::BasicBlock:
424 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
427 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
429 case ISD::RegisterMask:
430 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
433 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
435 case ISD::FrameIndex:
436 case ISD::TargetFrameIndex:
437 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
440 case ISD::TargetJumpTable:
441 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
442 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
444 case ISD::ConstantPool:
445 case ISD::TargetConstantPool: {
446 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
447 ID.AddInteger(CP->getAlignment());
448 ID.AddInteger(CP->getOffset());
449 if (CP->isMachineConstantPoolEntry())
450 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
452 ID.AddPointer(CP->getConstVal());
453 ID.AddInteger(CP->getTargetFlags());
456 case ISD::TargetIndex: {
457 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
458 ID.AddInteger(TI->getIndex());
459 ID.AddInteger(TI->getOffset());
460 ID.AddInteger(TI->getTargetFlags());
464 const LoadSDNode *LD = cast<LoadSDNode>(N);
465 ID.AddInteger(LD->getMemoryVT().getRawBits());
466 ID.AddInteger(LD->getRawSubclassData());
467 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
471 const StoreSDNode *ST = cast<StoreSDNode>(N);
472 ID.AddInteger(ST->getMemoryVT().getRawBits());
473 ID.AddInteger(ST->getRawSubclassData());
474 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
477 case ISD::ATOMIC_CMP_SWAP:
478 case ISD::ATOMIC_SWAP:
479 case ISD::ATOMIC_LOAD_ADD:
480 case ISD::ATOMIC_LOAD_SUB:
481 case ISD::ATOMIC_LOAD_AND:
482 case ISD::ATOMIC_LOAD_OR:
483 case ISD::ATOMIC_LOAD_XOR:
484 case ISD::ATOMIC_LOAD_NAND:
485 case ISD::ATOMIC_LOAD_MIN:
486 case ISD::ATOMIC_LOAD_MAX:
487 case ISD::ATOMIC_LOAD_UMIN:
488 case ISD::ATOMIC_LOAD_UMAX:
489 case ISD::ATOMIC_LOAD:
490 case ISD::ATOMIC_STORE: {
491 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
492 ID.AddInteger(AT->getMemoryVT().getRawBits());
493 ID.AddInteger(AT->getRawSubclassData());
494 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
497 case ISD::PREFETCH: {
498 const MemSDNode *PF = cast<MemSDNode>(N);
499 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
502 case ISD::VECTOR_SHUFFLE: {
503 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
504 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
506 ID.AddInteger(SVN->getMaskElt(i));
509 case ISD::TargetBlockAddress:
510 case ISD::BlockAddress: {
511 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
512 ID.AddPointer(BA->getBlockAddress());
513 ID.AddInteger(BA->getOffset());
514 ID.AddInteger(BA->getTargetFlags());
517 } // end switch (N->getOpcode())
519 // Target specific memory nodes could also have address spaces to check.
520 if (N->isTargetMemoryOpcode())
521 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
524 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
526 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
527 AddNodeIDOpcode(ID, N->getOpcode());
528 // Add the return value info.
529 AddNodeIDValueTypes(ID, N->getVTList());
530 // Add the operand info.
531 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
533 // Handle SDNode leafs with special info.
534 AddNodeIDCustom(ID, N);
537 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
538 /// the CSE map that carries volatility, temporalness, indexing mode, and
539 /// extension/truncation information.
541 static inline unsigned
542 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
543 bool isNonTemporal, bool isInvariant) {
544 assert((ConvType & 3) == ConvType &&
545 "ConvType may not require more than 2 bits!");
546 assert((AM & 7) == AM &&
547 "AM may not require more than 3 bits!");
551 (isNonTemporal << 6) |
555 //===----------------------------------------------------------------------===//
556 // SelectionDAG Class
557 //===----------------------------------------------------------------------===//
559 /// doNotCSE - Return true if CSE should not be performed for this node.
560 static bool doNotCSE(SDNode *N) {
561 if (N->getValueType(0) == MVT::Glue)
562 return true; // Never CSE anything that produces a flag.
564 switch (N->getOpcode()) {
566 case ISD::HANDLENODE:
568 return true; // Never CSE these nodes.
571 // Check that remaining values produced are not flags.
572 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
573 if (N->getValueType(i) == MVT::Glue)
574 return true; // Never CSE anything that produces a flag.
579 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
581 void SelectionDAG::RemoveDeadNodes() {
582 // Create a dummy node (which is not added to allnodes), that adds a reference
583 // to the root node, preventing it from being deleted.
584 HandleSDNode Dummy(getRoot());
586 SmallVector<SDNode*, 128> DeadNodes;
588 // Add all obviously-dead nodes to the DeadNodes worklist.
589 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
591 DeadNodes.push_back(I);
593 RemoveDeadNodes(DeadNodes);
595 // If the root changed (e.g. it was a dead load, update the root).
596 setRoot(Dummy.getValue());
599 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
600 /// given list, and any nodes that become unreachable as a result.
601 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
603 // Process the worklist, deleting the nodes and adding their uses to the
605 while (!DeadNodes.empty()) {
606 SDNode *N = DeadNodes.pop_back_val();
608 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
609 DUL->NodeDeleted(N, 0);
611 // Take the node out of the appropriate CSE map.
612 RemoveNodeFromCSEMaps(N);
614 // Next, brutally remove the operand list. This is safe to do, as there are
615 // no cycles in the graph.
616 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
618 SDNode *Operand = Use.getNode();
621 // Now that we removed this operand, see if there are no uses of it left.
622 if (Operand->use_empty())
623 DeadNodes.push_back(Operand);
630 void SelectionDAG::RemoveDeadNode(SDNode *N){
631 SmallVector<SDNode*, 16> DeadNodes(1, N);
633 // Create a dummy node that adds a reference to the root node, preventing
634 // it from being deleted. (This matters if the root is an operand of the
636 HandleSDNode Dummy(getRoot());
638 RemoveDeadNodes(DeadNodes);
641 void SelectionDAG::DeleteNode(SDNode *N) {
642 // First take this out of the appropriate CSE map.
643 RemoveNodeFromCSEMaps(N);
645 // Finally, remove uses due to operands of this node, remove from the
646 // AllNodes list, and delete the node.
647 DeleteNodeNotInCSEMaps(N);
650 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
651 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
652 assert(N->use_empty() && "Cannot delete a node that is not dead!");
654 // Drop all of the operands and decrement used node's use counts.
660 void SelectionDAG::DeallocateNode(SDNode *N) {
661 if (N->OperandsNeedDelete)
662 delete[] N->OperandList;
664 // Set the opcode to DELETED_NODE to help catch bugs when node
665 // memory is reallocated.
666 N->NodeType = ISD::DELETED_NODE;
668 NodeAllocator.Deallocate(AllNodes.remove(N));
670 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
671 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
672 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
673 DbgVals[i]->setIsInvalidated();
676 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
677 /// correspond to it. This is useful when we're about to delete or repurpose
678 /// the node. We don't want future request for structurally identical nodes
679 /// to return N anymore.
680 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
682 switch (N->getOpcode()) {
683 case ISD::HANDLENODE: return false; // noop.
685 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
686 "Cond code doesn't exist!");
687 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
688 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
690 case ISD::ExternalSymbol:
691 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
693 case ISD::TargetExternalSymbol: {
694 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
695 Erased = TargetExternalSymbols.erase(
696 std::pair<std::string,unsigned char>(ESN->getSymbol(),
697 ESN->getTargetFlags()));
700 case ISD::VALUETYPE: {
701 EVT VT = cast<VTSDNode>(N)->getVT();
702 if (VT.isExtended()) {
703 Erased = ExtendedValueTypeNodes.erase(VT);
705 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
706 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
711 // Remove it from the CSE Map.
712 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
713 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
714 Erased = CSEMap.RemoveNode(N);
718 // Verify that the node was actually in one of the CSE maps, unless it has a
719 // flag result (which cannot be CSE'd) or is one of the special cases that are
720 // not subject to CSE.
721 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
722 !N->isMachineOpcode() && !doNotCSE(N)) {
725 llvm_unreachable("Node is not in map!");
731 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
732 /// maps and modified in place. Add it back to the CSE maps, unless an identical
733 /// node already exists, in which case transfer all its users to the existing
734 /// node. This transfer can potentially trigger recursive merging.
737 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
738 // For node types that aren't CSE'd, just act as if no identical node
741 SDNode *Existing = CSEMap.GetOrInsertNode(N);
743 // If there was already an existing matching node, use ReplaceAllUsesWith
744 // to replace the dead one with the existing one. This can cause
745 // recursive merging of other unrelated nodes down the line.
746 ReplaceAllUsesWith(N, Existing);
748 // N is now dead. Inform the listeners and delete it.
749 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
750 DUL->NodeDeleted(N, Existing);
751 DeleteNodeNotInCSEMaps(N);
756 // If the node doesn't already exist, we updated it. Inform listeners.
757 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
761 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
762 /// were replaced with those specified. If this node is never memoized,
763 /// return null, otherwise return a pointer to the slot it would take. If a
764 /// node already exists with these operands, the slot will be non-null.
765 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
770 SDValue Ops[] = { Op };
772 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
773 AddNodeIDCustom(ID, N);
774 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
778 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
779 /// were replaced with those specified. If this node is never memoized,
780 /// return null, otherwise return a pointer to the slot it would take. If a
781 /// node already exists with these operands, the slot will be non-null.
782 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
783 SDValue Op1, SDValue Op2,
788 SDValue Ops[] = { Op1, Op2 };
790 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
791 AddNodeIDCustom(ID, N);
792 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
797 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
798 /// were replaced with those specified. If this node is never memoized,
799 /// return null, otherwise return a pointer to the slot it would take. If a
800 /// node already exists with these operands, the slot will be non-null.
801 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
802 const SDValue *Ops,unsigned NumOps,
808 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
809 AddNodeIDCustom(ID, N);
810 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
815 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
816 static void VerifyNodeCommon(SDNode *N) {
817 switch (N->getOpcode()) {
820 case ISD::BUILD_PAIR: {
821 EVT VT = N->getValueType(0);
822 assert(N->getNumValues() == 1 && "Too many results!");
823 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
824 "Wrong return type!");
825 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
826 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
827 "Mismatched operand types!");
828 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
829 "Wrong operand type!");
830 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
831 "Wrong return type size");
834 case ISD::BUILD_VECTOR: {
835 assert(N->getNumValues() == 1 && "Too many results!");
836 assert(N->getValueType(0).isVector() && "Wrong return type!");
837 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
838 "Wrong number of operands!");
839 EVT EltVT = N->getValueType(0).getVectorElementType();
840 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
841 assert((I->getValueType() == EltVT ||
842 (EltVT.isInteger() && I->getValueType().isInteger() &&
843 EltVT.bitsLE(I->getValueType()))) &&
844 "Wrong operand type!");
845 assert(I->getValueType() == N->getOperand(0).getValueType() &&
846 "Operands must all have the same type");
853 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
854 static void VerifySDNode(SDNode *N) {
855 // The SDNode allocators cannot be used to allocate nodes with fields that are
856 // not present in an SDNode!
857 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
858 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
859 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
860 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
861 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
862 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
863 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
864 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
865 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
866 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
867 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
868 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
869 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
870 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
871 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
872 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
873 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
874 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
875 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
880 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
882 static void VerifyMachineNode(SDNode *N) {
883 // The MachineNode allocators cannot be used to allocate nodes with fields
884 // that are not present in a MachineNode!
885 // Currently there are no such nodes.
891 /// getEVTAlignment - Compute the default alignment value for the
894 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
895 Type *Ty = VT == MVT::iPTR ?
896 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
897 VT.getTypeForEVT(*getContext());
899 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
902 // EntryNode could meaningfully have debug info if we can find it...
903 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
904 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(0), OptLevel(OL),
905 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
906 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
908 AllNodes.push_back(&EntryNode);
909 DbgInfo = new SDDbgInfo();
912 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
915 Context = &mf.getFunction()->getContext();
918 SelectionDAG::~SelectionDAG() {
919 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
924 void SelectionDAG::allnodes_clear() {
925 assert(&*AllNodes.begin() == &EntryNode);
926 AllNodes.remove(AllNodes.begin());
927 while (!AllNodes.empty())
928 DeallocateNode(AllNodes.begin());
931 void SelectionDAG::clear() {
933 OperandAllocator.Reset();
936 ExtendedValueTypeNodes.clear();
937 ExternalSymbols.clear();
938 TargetExternalSymbols.clear();
939 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
940 static_cast<CondCodeSDNode*>(0));
941 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
942 static_cast<SDNode*>(0));
944 EntryNode.UseList = 0;
945 AllNodes.push_back(&EntryNode);
946 Root = getEntryNode();
950 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
951 return VT.bitsGT(Op.getValueType()) ?
952 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
953 getNode(ISD::TRUNCATE, DL, VT, Op);
956 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
957 return VT.bitsGT(Op.getValueType()) ?
958 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
959 getNode(ISD::TRUNCATE, DL, VT, Op);
962 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
963 return VT.bitsGT(Op.getValueType()) ?
964 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
965 getNode(ISD::TRUNCATE, DL, VT, Op);
968 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
969 assert(!VT.isVector() &&
970 "getZeroExtendInReg should use the vector element type instead of "
972 if (Op.getValueType() == VT) return Op;
973 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
974 APInt Imm = APInt::getLowBitsSet(BitWidth,
976 return getNode(ISD::AND, DL, Op.getValueType(), Op,
977 getConstant(Imm, Op.getValueType()));
980 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
982 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
983 EVT EltVT = VT.getScalarType();
985 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
986 return getNode(ISD::XOR, DL, VT, Val, NegOne);
989 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
990 EVT EltVT = VT.getScalarType();
991 assert((EltVT.getSizeInBits() >= 64 ||
992 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
993 "getConstant with a uint64_t value that doesn't fit in the type!");
994 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
997 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
999 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1002 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1004 assert(VT.isInteger() && "Cannot create FP integer constant!");
1006 EVT EltVT = VT.getScalarType();
1007 const ConstantInt *Elt = &Val;
1009 const TargetLowering *TLI = TM.getTargetLowering();
1011 // In some cases the vector type is legal but the element type is illegal and
1012 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1013 // inserted value (the type does not need to match the vector element type).
1014 // Any extra bits introduced will be truncated away.
1015 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1016 TargetLowering::TypePromoteInteger) {
1017 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1018 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1019 Elt = ConstantInt::get(*getContext(), NewVal);
1021 // In other cases the element type is illegal and needs to be expanded, for
1022 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1023 // the value into n parts and use a vector type with n-times the elements.
1024 // Then bitcast to the type requested.
1025 // Legalizing constants too early makes the DAGCombiner's job harder so we
1026 // only legalize if the DAG tells us we must produce legal types.
1027 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1028 TLI->getTypeAction(*getContext(), EltVT) ==
1029 TargetLowering::TypeExpandInteger) {
1030 APInt NewVal = Elt->getValue();
1031 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1032 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1033 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1034 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1036 // Check the temporary vector is the correct size. If this fails then
1037 // getTypeToTransformTo() probably returned a type whose size (in bits)
1038 // isn't a power-of-2 factor of the requested type size.
1039 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1041 SmallVector<SDValue, 2> EltParts;
1042 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1043 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1044 .trunc(ViaEltSizeInBits),
1045 ViaEltVT, isT, isO));
1048 // EltParts is currently in little endian order. If we actually want
1049 // big-endian order then reverse it now.
1050 if (TLI->isBigEndian())
1051 std::reverse(EltParts.begin(), EltParts.end());
1053 // The elements must be reversed when the element order is different
1054 // to the endianness of the elements (because the BITCAST is itself a
1055 // vector shuffle in this situation). However, we do not need any code to
1056 // perform this reversal because getConstant() is producing a vector
1058 // This situation occurs in MIPS MSA.
1060 SmallVector<SDValue, 8> Ops;
1061 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1062 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1064 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1065 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1066 &Ops[0], Ops.size()));
1070 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1071 "APInt size does not match type size!");
1072 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1073 FoldingSetNodeID ID;
1074 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1079 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1081 return SDValue(N, 0);
1084 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1085 CSEMap.InsertNode(N, IP);
1086 AllNodes.push_back(N);
1089 SDValue Result(N, 0);
1090 if (VT.isVector()) {
1091 SmallVector<SDValue, 8> Ops;
1092 Ops.assign(VT.getVectorNumElements(), Result);
1093 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1098 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1099 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1103 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1104 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1107 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1108 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1110 EVT EltVT = VT.getScalarType();
1112 // Do the map lookup using the actual bit pattern for the floating point
1113 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1114 // we don't have issues with SNANs.
1115 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1116 FoldingSetNodeID ID;
1117 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1121 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1123 return SDValue(N, 0);
1126 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1127 CSEMap.InsertNode(N, IP);
1128 AllNodes.push_back(N);
1131 SDValue Result(N, 0);
1132 if (VT.isVector()) {
1133 SmallVector<SDValue, 8> Ops;
1134 Ops.assign(VT.getVectorNumElements(), Result);
1135 // FIXME SDLoc info might be appropriate here
1136 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1141 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1142 EVT EltVT = VT.getScalarType();
1143 if (EltVT==MVT::f32)
1144 return getConstantFP(APFloat((float)Val), VT, isTarget);
1145 else if (EltVT==MVT::f64)
1146 return getConstantFP(APFloat(Val), VT, isTarget);
1147 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1150 APFloat apf = APFloat(Val);
1151 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1153 return getConstantFP(apf, VT, isTarget);
1155 llvm_unreachable("Unsupported type in getConstantFP");
1158 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1159 EVT VT, int64_t Offset,
1161 unsigned char TargetFlags) {
1162 assert((TargetFlags == 0 || isTargetGA) &&
1163 "Cannot set target flags on target-independent globals");
1164 const TargetLowering *TLI = TM.getTargetLowering();
1166 // Truncate (with sign-extension) the offset value to the pointer size.
1167 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1169 Offset = SignExtend64(Offset, BitWidth);
1171 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1173 // If GV is an alias then use the aliasee for determining thread-localness.
1174 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1175 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1179 if (GVar && GVar->isThreadLocal())
1180 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1182 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1184 FoldingSetNodeID ID;
1185 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1187 ID.AddInteger(Offset);
1188 ID.AddInteger(TargetFlags);
1189 ID.AddInteger(GV->getType()->getAddressSpace());
1191 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1192 return SDValue(E, 0);
1194 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1195 DL.getDebugLoc(), GV, VT,
1196 Offset, TargetFlags);
1197 CSEMap.InsertNode(N, IP);
1198 AllNodes.push_back(N);
1199 return SDValue(N, 0);
1202 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1203 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1204 FoldingSetNodeID ID;
1205 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1208 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1209 return SDValue(E, 0);
1211 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1212 CSEMap.InsertNode(N, IP);
1213 AllNodes.push_back(N);
1214 return SDValue(N, 0);
1217 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1218 unsigned char TargetFlags) {
1219 assert((TargetFlags == 0 || isTarget) &&
1220 "Cannot set target flags on target-independent jump tables");
1221 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1222 FoldingSetNodeID ID;
1223 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1225 ID.AddInteger(TargetFlags);
1227 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1228 return SDValue(E, 0);
1230 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1232 CSEMap.InsertNode(N, IP);
1233 AllNodes.push_back(N);
1234 return SDValue(N, 0);
1237 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1238 unsigned Alignment, int Offset,
1240 unsigned char TargetFlags) {
1241 assert((TargetFlags == 0 || isTarget) &&
1242 "Cannot set target flags on target-independent globals");
1245 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1246 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1247 FoldingSetNodeID ID;
1248 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1249 ID.AddInteger(Alignment);
1250 ID.AddInteger(Offset);
1252 ID.AddInteger(TargetFlags);
1254 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1255 return SDValue(E, 0);
1257 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1258 Alignment, TargetFlags);
1259 CSEMap.InsertNode(N, IP);
1260 AllNodes.push_back(N);
1261 return SDValue(N, 0);
1265 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1266 unsigned Alignment, int Offset,
1268 unsigned char TargetFlags) {
1269 assert((TargetFlags == 0 || isTarget) &&
1270 "Cannot set target flags on target-independent globals");
1273 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1274 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1275 FoldingSetNodeID ID;
1276 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1277 ID.AddInteger(Alignment);
1278 ID.AddInteger(Offset);
1279 C->addSelectionDAGCSEId(ID);
1280 ID.AddInteger(TargetFlags);
1282 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1283 return SDValue(E, 0);
1285 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1286 Alignment, TargetFlags);
1287 CSEMap.InsertNode(N, IP);
1288 AllNodes.push_back(N);
1289 return SDValue(N, 0);
1292 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1293 unsigned char TargetFlags) {
1294 FoldingSetNodeID ID;
1295 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1296 ID.AddInteger(Index);
1297 ID.AddInteger(Offset);
1298 ID.AddInteger(TargetFlags);
1300 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1301 return SDValue(E, 0);
1303 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1305 CSEMap.InsertNode(N, IP);
1306 AllNodes.push_back(N);
1307 return SDValue(N, 0);
1310 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1311 FoldingSetNodeID ID;
1312 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1315 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1316 return SDValue(E, 0);
1318 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1319 CSEMap.InsertNode(N, IP);
1320 AllNodes.push_back(N);
1321 return SDValue(N, 0);
1324 SDValue SelectionDAG::getValueType(EVT VT) {
1325 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1326 ValueTypeNodes.size())
1327 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1329 SDNode *&N = VT.isExtended() ?
1330 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1332 if (N) return SDValue(N, 0);
1333 N = new (NodeAllocator) VTSDNode(VT);
1334 AllNodes.push_back(N);
1335 return SDValue(N, 0);
1338 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1339 SDNode *&N = ExternalSymbols[Sym];
1340 if (N) return SDValue(N, 0);
1341 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1342 AllNodes.push_back(N);
1343 return SDValue(N, 0);
1346 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1347 unsigned char TargetFlags) {
1349 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1351 if (N) return SDValue(N, 0);
1352 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1353 AllNodes.push_back(N);
1354 return SDValue(N, 0);
1357 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1358 if ((unsigned)Cond >= CondCodeNodes.size())
1359 CondCodeNodes.resize(Cond+1);
1361 if (CondCodeNodes[Cond] == 0) {
1362 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1363 CondCodeNodes[Cond] = N;
1364 AllNodes.push_back(N);
1367 return SDValue(CondCodeNodes[Cond], 0);
1370 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1371 // the shuffle mask M that point at N1 to point at N2, and indices that point
1372 // N2 to point at N1.
1373 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1375 int NElts = M.size();
1376 for (int i = 0; i != NElts; ++i) {
1384 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1385 SDValue N2, const int *Mask) {
1386 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1387 "Invalid VECTOR_SHUFFLE");
1389 // Canonicalize shuffle undef, undef -> undef
1390 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1391 return getUNDEF(VT);
1393 // Validate that all indices in Mask are within the range of the elements
1394 // input to the shuffle.
1395 unsigned NElts = VT.getVectorNumElements();
1396 SmallVector<int, 8> MaskVec;
1397 for (unsigned i = 0; i != NElts; ++i) {
1398 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1399 MaskVec.push_back(Mask[i]);
1402 // Canonicalize shuffle v, v -> v, undef
1405 for (unsigned i = 0; i != NElts; ++i)
1406 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1409 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1410 if (N1.getOpcode() == ISD::UNDEF)
1411 commuteShuffle(N1, N2, MaskVec);
1413 // Canonicalize all index into lhs, -> shuffle lhs, undef
1414 // Canonicalize all index into rhs, -> shuffle rhs, undef
1415 bool AllLHS = true, AllRHS = true;
1416 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1417 for (unsigned i = 0; i != NElts; ++i) {
1418 if (MaskVec[i] >= (int)NElts) {
1423 } else if (MaskVec[i] >= 0) {
1427 if (AllLHS && AllRHS)
1428 return getUNDEF(VT);
1429 if (AllLHS && !N2Undef)
1433 commuteShuffle(N1, N2, MaskVec);
1436 // If Identity shuffle return that node.
1437 bool Identity = true;
1438 for (unsigned i = 0; i != NElts; ++i) {
1439 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1441 if (Identity && NElts)
1444 FoldingSetNodeID ID;
1445 SDValue Ops[2] = { N1, N2 };
1446 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1447 for (unsigned i = 0; i != NElts; ++i)
1448 ID.AddInteger(MaskVec[i]);
1451 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1452 return SDValue(E, 0);
1454 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1455 // SDNode doesn't have access to it. This memory will be "leaked" when
1456 // the node is deallocated, but recovered when the NodeAllocator is released.
1457 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1458 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1460 ShuffleVectorSDNode *N =
1461 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1462 dl.getDebugLoc(), N1, N2,
1464 CSEMap.InsertNode(N, IP);
1465 AllNodes.push_back(N);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1470 SDValue Val, SDValue DTy,
1471 SDValue STy, SDValue Rnd, SDValue Sat,
1472 ISD::CvtCode Code) {
1473 // If the src and dest types are the same and the conversion is between
1474 // integer types of the same sign or two floats, no conversion is necessary.
1476 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1479 FoldingSetNodeID ID;
1480 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1481 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1483 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1484 return SDValue(E, 0);
1486 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1489 CSEMap.InsertNode(N, IP);
1490 AllNodes.push_back(N);
1491 return SDValue(N, 0);
1494 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1495 FoldingSetNodeID ID;
1496 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1497 ID.AddInteger(RegNo);
1499 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1500 return SDValue(E, 0);
1502 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1503 CSEMap.InsertNode(N, IP);
1504 AllNodes.push_back(N);
1505 return SDValue(N, 0);
1508 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1509 FoldingSetNodeID ID;
1510 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1511 ID.AddPointer(RegMask);
1513 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1514 return SDValue(E, 0);
1516 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1517 CSEMap.InsertNode(N, IP);
1518 AllNodes.push_back(N);
1519 return SDValue(N, 0);
1522 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1523 FoldingSetNodeID ID;
1524 SDValue Ops[] = { Root };
1525 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1526 ID.AddPointer(Label);
1528 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1529 return SDValue(E, 0);
1531 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1532 dl.getDebugLoc(), Root, Label);
1533 CSEMap.InsertNode(N, IP);
1534 AllNodes.push_back(N);
1535 return SDValue(N, 0);
1539 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1542 unsigned char TargetFlags) {
1543 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1545 FoldingSetNodeID ID;
1546 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1548 ID.AddInteger(Offset);
1549 ID.AddInteger(TargetFlags);
1551 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1552 return SDValue(E, 0);
1554 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1556 CSEMap.InsertNode(N, IP);
1557 AllNodes.push_back(N);
1558 return SDValue(N, 0);
1561 SDValue SelectionDAG::getSrcValue(const Value *V) {
1562 assert((!V || V->getType()->isPointerTy()) &&
1563 "SrcValue is not a pointer?");
1565 FoldingSetNodeID ID;
1566 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1570 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1571 return SDValue(E, 0);
1573 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1574 CSEMap.InsertNode(N, IP);
1575 AllNodes.push_back(N);
1576 return SDValue(N, 0);
1579 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1580 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1581 FoldingSetNodeID ID;
1582 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1586 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1587 return SDValue(E, 0);
1589 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1590 CSEMap.InsertNode(N, IP);
1591 AllNodes.push_back(N);
1592 return SDValue(N, 0);
1595 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1596 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1597 unsigned SrcAS, unsigned DestAS) {
1598 SDValue Ops[] = {Ptr};
1599 FoldingSetNodeID ID;
1600 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1601 ID.AddInteger(SrcAS);
1602 ID.AddInteger(DestAS);
1605 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1606 return SDValue(E, 0);
1608 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1610 VT, Ptr, SrcAS, DestAS);
1611 CSEMap.InsertNode(N, IP);
1612 AllNodes.push_back(N);
1613 return SDValue(N, 0);
1616 /// getShiftAmountOperand - Return the specified value casted to
1617 /// the target's desired shift amount type.
1618 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1619 EVT OpTy = Op.getValueType();
1620 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1621 if (OpTy == ShTy || OpTy.isVector()) return Op;
1623 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1624 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1627 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1628 /// specified value type.
1629 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1630 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1631 unsigned ByteSize = VT.getStoreSize();
1632 Type *Ty = VT.getTypeForEVT(*getContext());
1633 const TargetLowering *TLI = TM.getTargetLowering();
1634 unsigned StackAlign =
1635 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1637 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1638 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1641 /// CreateStackTemporary - Create a stack temporary suitable for holding
1642 /// either of the specified value types.
1643 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1644 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1645 VT2.getStoreSizeInBits())/8;
1646 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1647 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1648 const TargetLowering *TLI = TM.getTargetLowering();
1649 const DataLayout *TD = TLI->getDataLayout();
1650 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1651 TD->getPrefTypeAlignment(Ty2));
1653 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1654 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1655 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1658 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1659 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1660 // These setcc operations always fold.
1664 case ISD::SETFALSE2: return getConstant(0, VT);
1666 case ISD::SETTRUE2: {
1667 const TargetLowering *TLI = TM.getTargetLowering();
1668 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1670 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1683 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1687 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1688 const APInt &C2 = N2C->getAPIntValue();
1689 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1690 const APInt &C1 = N1C->getAPIntValue();
1693 default: llvm_unreachable("Unknown integer setcc!");
1694 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1695 case ISD::SETNE: return getConstant(C1 != C2, VT);
1696 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1697 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1698 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1699 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1700 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1701 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1702 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1703 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1707 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1708 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1709 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1712 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1713 return getUNDEF(VT);
1715 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1716 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1717 return getUNDEF(VT);
1719 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1720 R==APFloat::cmpLessThan, VT);
1721 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1722 return getUNDEF(VT);
1724 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1725 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1726 return getUNDEF(VT);
1728 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1729 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1730 return getUNDEF(VT);
1732 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1733 R==APFloat::cmpEqual, VT);
1734 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1735 return getUNDEF(VT);
1737 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1738 R==APFloat::cmpEqual, VT);
1739 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1740 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1741 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1742 R==APFloat::cmpEqual, VT);
1743 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1744 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1745 R==APFloat::cmpLessThan, VT);
1746 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1747 R==APFloat::cmpUnordered, VT);
1748 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1749 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1752 // Ensure that the constant occurs on the RHS.
1753 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1754 MVT CompVT = N1.getValueType().getSimpleVT();
1755 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1758 return getSetCC(dl, VT, N2, N1, SwappedCond);
1762 // Could not fold it.
1766 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1767 /// use this predicate to simplify operations downstream.
1768 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1769 // This predicate is not safe for vector operations.
1770 if (Op.getValueType().isVector())
1773 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1774 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1777 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1778 /// this predicate to simplify operations downstream. Mask is known to be zero
1779 /// for bits that V cannot have.
1780 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1781 unsigned Depth) const {
1782 APInt KnownZero, KnownOne;
1783 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1784 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1785 return (KnownZero & Mask) == Mask;
1788 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1789 /// known to be either zero or one and return them in the KnownZero/KnownOne
1790 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1792 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1793 APInt &KnownOne, unsigned Depth) const {
1794 const TargetLowering *TLI = TM.getTargetLowering();
1795 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1797 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1799 return; // Limit search depth.
1801 APInt KnownZero2, KnownOne2;
1803 switch (Op.getOpcode()) {
1805 // We know all of the bits for a constant!
1806 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1807 KnownZero = ~KnownOne;
1810 // If either the LHS or the RHS are Zero, the result is zero.
1811 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1812 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1813 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1814 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1816 // Output known-1 bits are only known if set in both the LHS & RHS.
1817 KnownOne &= KnownOne2;
1818 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1819 KnownZero |= KnownZero2;
1822 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1823 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1824 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1825 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1827 // Output known-0 bits are only known if clear in both the LHS & RHS.
1828 KnownZero &= KnownZero2;
1829 // Output known-1 are known to be set if set in either the LHS | RHS.
1830 KnownOne |= KnownOne2;
1833 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1834 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1835 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1836 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1838 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1839 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1840 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1841 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1842 KnownZero = KnownZeroOut;
1846 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1847 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1848 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1849 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1851 // If low bits are zero in either operand, output low known-0 bits.
1852 // Also compute a conserative estimate for high known-0 bits.
1853 // More trickiness is possible, but this is sufficient for the
1854 // interesting case of alignment computation.
1855 KnownOne.clearAllBits();
1856 unsigned TrailZ = KnownZero.countTrailingOnes() +
1857 KnownZero2.countTrailingOnes();
1858 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1859 KnownZero2.countLeadingOnes(),
1860 BitWidth) - BitWidth;
1862 TrailZ = std::min(TrailZ, BitWidth);
1863 LeadZ = std::min(LeadZ, BitWidth);
1864 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1865 APInt::getHighBitsSet(BitWidth, LeadZ);
1869 // For the purposes of computing leading zeros we can conservatively
1870 // treat a udiv as a logical right shift by the power of 2 known to
1871 // be less than the denominator.
1872 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1873 unsigned LeadZ = KnownZero2.countLeadingOnes();
1875 KnownOne2.clearAllBits();
1876 KnownZero2.clearAllBits();
1877 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1878 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1879 if (RHSUnknownLeadingOnes != BitWidth)
1880 LeadZ = std::min(BitWidth,
1881 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1883 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1887 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1888 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1889 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1890 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1892 // Only known if known in both the LHS and RHS.
1893 KnownOne &= KnownOne2;
1894 KnownZero &= KnownZero2;
1896 case ISD::SELECT_CC:
1897 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1898 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1899 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1900 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1902 // Only known if known in both the LHS and RHS.
1903 KnownOne &= KnownOne2;
1904 KnownZero &= KnownZero2;
1912 if (Op.getResNo() != 1)
1914 // The boolean result conforms to getBooleanContents. Fall through.
1916 // If we know the result of a setcc has the top bits zero, use this info.
1917 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1918 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1919 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1922 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 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 <<= ShAmt;
1934 // low bits known zero.
1935 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1939 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
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 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1948 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1949 KnownZero = KnownZero.lshr(ShAmt);
1950 KnownOne = KnownOne.lshr(ShAmt);
1952 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1953 KnownZero |= HighBits; // High bits known zero.
1957 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1958 unsigned ShAmt = SA->getZExtValue();
1960 // If the shift count is an invalid immediate, don't do anything.
1961 if (ShAmt >= BitWidth)
1964 // If any of the demanded bits are produced by the sign extension, we also
1965 // demand the input sign bit.
1966 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1968 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1969 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1970 KnownZero = KnownZero.lshr(ShAmt);
1971 KnownOne = KnownOne.lshr(ShAmt);
1973 // Handle the sign bits.
1974 APInt SignBit = APInt::getSignBit(BitWidth);
1975 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1977 if (KnownZero.intersects(SignBit)) {
1978 KnownZero |= HighBits; // New bits are known zero.
1979 } else if (KnownOne.intersects(SignBit)) {
1980 KnownOne |= HighBits; // New bits are known one.
1984 case ISD::SIGN_EXTEND_INREG: {
1985 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1986 unsigned EBits = EVT.getScalarType().getSizeInBits();
1988 // Sign extension. Compute the demanded bits in the result that are not
1989 // present in the input.
1990 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1992 APInt InSignBit = APInt::getSignBit(EBits);
1993 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1995 // If the sign extended bits are demanded, we know that the sign
1997 InSignBit = InSignBit.zext(BitWidth);
1998 if (NewBits.getBoolValue())
1999 InputDemandedBits |= InSignBit;
2001 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2002 KnownOne &= InputDemandedBits;
2003 KnownZero &= InputDemandedBits;
2004 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2006 // If the sign bit of the input is known set or clear, then we know the
2007 // top bits of the result.
2008 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2009 KnownZero |= NewBits;
2010 KnownOne &= ~NewBits;
2011 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2012 KnownOne |= NewBits;
2013 KnownZero &= ~NewBits;
2014 } else { // Input sign bit unknown
2015 KnownZero &= ~NewBits;
2016 KnownOne &= ~NewBits;
2021 case ISD::CTTZ_ZERO_UNDEF:
2023 case ISD::CTLZ_ZERO_UNDEF:
2025 unsigned LowBits = Log2_32(BitWidth)+1;
2026 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2027 KnownOne.clearAllBits();
2031 LoadSDNode *LD = cast<LoadSDNode>(Op);
2032 // If this is a ZEXTLoad and we are looking at the loaded value.
2033 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2034 EVT VT = LD->getMemoryVT();
2035 unsigned MemBits = VT.getScalarType().getSizeInBits();
2036 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2037 } else if (const MDNode *Ranges = LD->getRanges()) {
2038 computeMaskedBitsLoad(*Ranges, KnownZero);
2042 case ISD::ZERO_EXTEND: {
2043 EVT InVT = Op.getOperand(0).getValueType();
2044 unsigned InBits = InVT.getScalarType().getSizeInBits();
2045 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2046 KnownZero = KnownZero.trunc(InBits);
2047 KnownOne = KnownOne.trunc(InBits);
2048 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2049 KnownZero = KnownZero.zext(BitWidth);
2050 KnownOne = KnownOne.zext(BitWidth);
2051 KnownZero |= NewBits;
2054 case ISD::SIGN_EXTEND: {
2055 EVT InVT = Op.getOperand(0).getValueType();
2056 unsigned InBits = InVT.getScalarType().getSizeInBits();
2057 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2059 KnownZero = KnownZero.trunc(InBits);
2060 KnownOne = KnownOne.trunc(InBits);
2061 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2063 // Note if the sign bit is known to be zero or one.
2064 bool SignBitKnownZero = KnownZero.isNegative();
2065 bool SignBitKnownOne = KnownOne.isNegative();
2066 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2067 "Sign bit can't be known to be both zero and one!");
2069 KnownZero = KnownZero.zext(BitWidth);
2070 KnownOne = KnownOne.zext(BitWidth);
2072 // If the sign bit is known zero or one, the top bits match.
2073 if (SignBitKnownZero)
2074 KnownZero |= NewBits;
2075 else if (SignBitKnownOne)
2076 KnownOne |= NewBits;
2079 case ISD::ANY_EXTEND: {
2080 EVT InVT = Op.getOperand(0).getValueType();
2081 unsigned InBits = InVT.getScalarType().getSizeInBits();
2082 KnownZero = KnownZero.trunc(InBits);
2083 KnownOne = KnownOne.trunc(InBits);
2084 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2085 KnownZero = KnownZero.zext(BitWidth);
2086 KnownOne = KnownOne.zext(BitWidth);
2089 case ISD::TRUNCATE: {
2090 EVT InVT = Op.getOperand(0).getValueType();
2091 unsigned InBits = InVT.getScalarType().getSizeInBits();
2092 KnownZero = KnownZero.zext(InBits);
2093 KnownOne = KnownOne.zext(InBits);
2094 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2095 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2096 KnownZero = KnownZero.trunc(BitWidth);
2097 KnownOne = KnownOne.trunc(BitWidth);
2100 case ISD::AssertZext: {
2101 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2102 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2103 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2104 KnownZero |= (~InMask);
2105 KnownOne &= (~KnownZero);
2109 // All bits are zero except the low bit.
2110 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2114 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2115 // We know that the top bits of C-X are clear if X contains less bits
2116 // than C (i.e. no wrap-around can happen). For example, 20-X is
2117 // positive if we can prove that X is >= 0 and < 16.
2118 if (CLHS->getAPIntValue().isNonNegative()) {
2119 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2120 // NLZ can't be BitWidth with no sign bit
2121 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2122 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2124 // If all of the MaskV bits are known to be zero, then we know the
2125 // output top bits are zero, because we now know that the output is
2127 if ((KnownZero2 & MaskV) == MaskV) {
2128 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2129 // Top bits known zero.
2130 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2138 // Output known-0 bits are known if clear or set in both the low clear bits
2139 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2140 // low 3 bits clear.
2141 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2142 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2143 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2145 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2146 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2147 KnownZeroOut = std::min(KnownZeroOut,
2148 KnownZero2.countTrailingOnes());
2150 if (Op.getOpcode() == ISD::ADD) {
2151 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2155 // With ADDE, a carry bit may be added in, so we can only use this
2156 // information if we know (at least) that the low two bits are clear. We
2157 // then return to the caller that the low bit is unknown but that other bits
2159 if (KnownZeroOut >= 2) // ADDE
2160 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2164 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2165 const APInt &RA = Rem->getAPIntValue().abs();
2166 if (RA.isPowerOf2()) {
2167 APInt LowBits = RA - 1;
2168 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2170 // The low bits of the first operand are unchanged by the srem.
2171 KnownZero = KnownZero2 & LowBits;
2172 KnownOne = KnownOne2 & LowBits;
2174 // If the first operand is non-negative or has all low bits zero, then
2175 // the upper bits are all zero.
2176 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2177 KnownZero |= ~LowBits;
2179 // If the first operand is negative and not all low bits are zero, then
2180 // the upper bits are all one.
2181 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2182 KnownOne |= ~LowBits;
2183 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2188 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2189 const APInt &RA = Rem->getAPIntValue();
2190 if (RA.isPowerOf2()) {
2191 APInt LowBits = (RA - 1);
2192 KnownZero |= ~LowBits;
2193 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2194 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2199 // Since the result is less than or equal to either operand, any leading
2200 // zero bits in either operand must also exist in the result.
2201 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2202 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2204 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2205 KnownZero2.countLeadingOnes());
2206 KnownOne.clearAllBits();
2207 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2210 case ISD::FrameIndex:
2211 case ISD::TargetFrameIndex:
2212 if (unsigned Align = InferPtrAlignment(Op)) {
2213 // The low bits are known zero if the pointer is aligned.
2214 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2220 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2223 case ISD::INTRINSIC_WO_CHAIN:
2224 case ISD::INTRINSIC_W_CHAIN:
2225 case ISD::INTRINSIC_VOID:
2226 // Allow the target to implement this method for its nodes.
2227 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2232 /// ComputeNumSignBits - Return the number of times the sign bit of the
2233 /// register is replicated into the other bits. We know that at least 1 bit
2234 /// is always equal to the sign bit (itself), but other cases can give us
2235 /// information. For example, immediately after an "SRA X, 2", we know that
2236 /// the top 3 bits are all equal to each other, so we return 3.
2237 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2238 const TargetLowering *TLI = TM.getTargetLowering();
2239 EVT VT = Op.getValueType();
2240 assert(VT.isInteger() && "Invalid VT!");
2241 unsigned VTBits = VT.getScalarType().getSizeInBits();
2243 unsigned FirstAnswer = 1;
2246 return 1; // Limit search depth.
2248 switch (Op.getOpcode()) {
2250 case ISD::AssertSext:
2251 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2252 return VTBits-Tmp+1;
2253 case ISD::AssertZext:
2254 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2257 case ISD::Constant: {
2258 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2259 return Val.getNumSignBits();
2262 case ISD::SIGN_EXTEND:
2264 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2265 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2267 case ISD::SIGN_EXTEND_INREG:
2268 // Max of the input and what this extends.
2270 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2273 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2274 return std::max(Tmp, Tmp2);
2277 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2278 // SRA X, C -> adds C sign bits.
2279 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2280 Tmp += C->getZExtValue();
2281 if (Tmp > VTBits) Tmp = VTBits;
2285 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2286 // shl destroys sign bits.
2287 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2288 if (C->getZExtValue() >= VTBits || // Bad shift.
2289 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2290 return Tmp - C->getZExtValue();
2295 case ISD::XOR: // NOT is handled here.
2296 // Logical binary ops preserve the number of sign bits at the worst.
2297 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2299 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2300 FirstAnswer = std::min(Tmp, Tmp2);
2301 // We computed what we know about the sign bits as our first
2302 // answer. Now proceed to the generic code that uses
2303 // ComputeMaskedBits, and pick whichever answer is better.
2308 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2309 if (Tmp == 1) return 1; // Early out.
2310 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2311 return std::min(Tmp, Tmp2);
2319 if (Op.getResNo() != 1)
2321 // The boolean result conforms to getBooleanContents. Fall through.
2323 // If setcc returns 0/-1, all bits are sign bits.
2324 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2325 TargetLowering::ZeroOrNegativeOneBooleanContent)
2330 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2331 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2333 // Handle rotate right by N like a rotate left by 32-N.
2334 if (Op.getOpcode() == ISD::ROTR)
2335 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2337 // If we aren't rotating out all of the known-in sign bits, return the
2338 // number that are left. This handles rotl(sext(x), 1) for example.
2339 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2340 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2344 // Add can have at most one carry bit. Thus we know that the output
2345 // is, at worst, one more bit than the inputs.
2346 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2347 if (Tmp == 1) return 1; // Early out.
2349 // Special case decrementing a value (ADD X, -1):
2350 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2351 if (CRHS->isAllOnesValue()) {
2352 APInt KnownZero, KnownOne;
2353 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2355 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2357 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2360 // If we are subtracting one from a positive number, there is no carry
2361 // out of the result.
2362 if (KnownZero.isNegative())
2366 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2367 if (Tmp2 == 1) return 1;
2368 return std::min(Tmp, Tmp2)-1;
2371 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2372 if (Tmp2 == 1) return 1;
2375 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2376 if (CLHS->isNullValue()) {
2377 APInt KnownZero, KnownOne;
2378 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2379 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2381 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2384 // If the input is known to be positive (the sign bit is known clear),
2385 // the output of the NEG has the same number of sign bits as the input.
2386 if (KnownZero.isNegative())
2389 // Otherwise, we treat this like a SUB.
2392 // Sub can have at most one carry bit. Thus we know that the output
2393 // is, at worst, one more bit than the inputs.
2394 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395 if (Tmp == 1) return 1; // Early out.
2396 return std::min(Tmp, Tmp2)-1;
2398 // FIXME: it's tricky to do anything useful for this, but it is an important
2399 // case for targets like X86.
2403 // If we are looking at the loaded value of the SDNode.
2404 if (Op.getResNo() == 0) {
2405 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2406 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2407 unsigned ExtType = LD->getExtensionType();
2410 case ISD::SEXTLOAD: // '17' bits known
2411 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2412 return VTBits-Tmp+1;
2413 case ISD::ZEXTLOAD: // '16' bits known
2414 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2420 // Allow the target to implement this method for its nodes.
2421 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2422 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2423 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2424 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2425 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2426 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2429 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2430 // use this information.
2431 APInt KnownZero, KnownOne;
2432 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2435 if (KnownZero.isNegative()) { // sign bit is 0
2437 } else if (KnownOne.isNegative()) { // sign bit is 1;
2444 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2445 // the number of identical bits in the top of the input value.
2447 Mask <<= Mask.getBitWidth()-VTBits;
2448 // Return # leading zeros. We use 'min' here in case Val was zero before
2449 // shifting. We don't want to return '64' as for an i32 "0".
2450 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2453 /// isBaseWithConstantOffset - Return true if the specified operand is an
2454 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2455 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2456 /// semantics as an ADD. This handles the equivalence:
2457 /// X|Cst == X+Cst iff X&Cst = 0.
2458 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2459 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2460 !isa<ConstantSDNode>(Op.getOperand(1)))
2463 if (Op.getOpcode() == ISD::OR &&
2464 !MaskedValueIsZero(Op.getOperand(0),
2465 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2472 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2473 // If we're told that NaNs won't happen, assume they won't.
2474 if (getTarget().Options.NoNaNsFPMath)
2477 // If the value is a constant, we can obviously see if it is a NaN or not.
2478 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2479 return !C->getValueAPF().isNaN();
2481 // TODO: Recognize more cases here.
2486 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2487 // If the value is a constant, we can obviously see if it is a zero or not.
2488 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2489 return !C->isZero();
2491 // TODO: Recognize more cases here.
2492 switch (Op.getOpcode()) {
2495 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2496 return !C->isNullValue();
2503 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2504 // Check the obvious case.
2505 if (A == B) return true;
2507 // For for negative and positive zero.
2508 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2509 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2510 if (CA->isZero() && CB->isZero()) return true;
2512 // Otherwise they may not be equal.
2516 /// getNode - Gets or creates the specified node.
2518 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2519 FoldingSetNodeID ID;
2520 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2522 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2523 return SDValue(E, 0);
2525 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2526 DL.getDebugLoc(), getVTList(VT));
2527 CSEMap.InsertNode(N, IP);
2529 AllNodes.push_back(N);
2533 return SDValue(N, 0);
2536 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2537 EVT VT, SDValue Operand) {
2538 // Constant fold unary operations with an integer constant operand.
2539 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2540 const APInt &Val = C->getAPIntValue();
2543 case ISD::SIGN_EXTEND:
2544 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2545 C->isTargetOpcode(), C->isOpaque());
2546 case ISD::ANY_EXTEND:
2547 case ISD::ZERO_EXTEND:
2549 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2550 C->isTargetOpcode(), C->isOpaque());
2551 case ISD::UINT_TO_FP:
2552 case ISD::SINT_TO_FP: {
2553 APFloat apf(EVTToAPFloatSemantics(VT),
2554 APInt::getNullValue(VT.getSizeInBits()));
2555 (void)apf.convertFromAPInt(Val,
2556 Opcode==ISD::SINT_TO_FP,
2557 APFloat::rmNearestTiesToEven);
2558 return getConstantFP(apf, VT);
2561 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2562 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2563 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2564 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2567 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2570 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2573 case ISD::CTLZ_ZERO_UNDEF:
2574 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2577 case ISD::CTTZ_ZERO_UNDEF:
2578 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2583 // Constant fold unary operations with a floating point constant operand.
2584 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2585 APFloat V = C->getValueAPF(); // make copy
2589 return getConstantFP(V, VT);
2592 return getConstantFP(V, VT);
2594 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2595 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2596 return getConstantFP(V, VT);
2600 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2601 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2602 return getConstantFP(V, VT);
2606 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2607 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2608 return getConstantFP(V, VT);
2611 case ISD::FP_EXTEND: {
2613 // This can return overflow, underflow, or inexact; we don't care.
2614 // FIXME need to be more flexible about rounding mode.
2615 (void)V.convert(EVTToAPFloatSemantics(VT),
2616 APFloat::rmNearestTiesToEven, &ignored);
2617 return getConstantFP(V, VT);
2619 case ISD::FP_TO_SINT:
2620 case ISD::FP_TO_UINT: {
2623 assert(integerPartWidth >= 64);
2624 // FIXME need to be more flexible about rounding mode.
2625 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2626 Opcode==ISD::FP_TO_SINT,
2627 APFloat::rmTowardZero, &ignored);
2628 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2630 APInt api(VT.getSizeInBits(), x);
2631 return getConstant(api, VT);
2634 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2635 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2636 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2637 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2642 unsigned OpOpcode = Operand.getNode()->getOpcode();
2644 case ISD::TokenFactor:
2645 case ISD::MERGE_VALUES:
2646 case ISD::CONCAT_VECTORS:
2647 return Operand; // Factor, merge or concat of one node? No need.
2648 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2649 case ISD::FP_EXTEND:
2650 assert(VT.isFloatingPoint() &&
2651 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2652 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2653 assert((!VT.isVector() ||
2654 VT.getVectorNumElements() ==
2655 Operand.getValueType().getVectorNumElements()) &&
2656 "Vector element count mismatch!");
2657 if (Operand.getOpcode() == ISD::UNDEF)
2658 return getUNDEF(VT);
2660 case ISD::SIGN_EXTEND:
2661 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2662 "Invalid SIGN_EXTEND!");
2663 if (Operand.getValueType() == VT) return Operand; // noop extension
2664 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2665 "Invalid sext node, dst < src!");
2666 assert((!VT.isVector() ||
2667 VT.getVectorNumElements() ==
2668 Operand.getValueType().getVectorNumElements()) &&
2669 "Vector element count mismatch!");
2670 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2671 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2672 else if (OpOpcode == ISD::UNDEF)
2673 // sext(undef) = 0, because the top bits will all be the same.
2674 return getConstant(0, VT);
2676 case ISD::ZERO_EXTEND:
2677 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2678 "Invalid ZERO_EXTEND!");
2679 if (Operand.getValueType() == VT) return Operand; // noop extension
2680 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2681 "Invalid zext node, dst < src!");
2682 assert((!VT.isVector() ||
2683 VT.getVectorNumElements() ==
2684 Operand.getValueType().getVectorNumElements()) &&
2685 "Vector element count mismatch!");
2686 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2687 return getNode(ISD::ZERO_EXTEND, DL, VT,
2688 Operand.getNode()->getOperand(0));
2689 else if (OpOpcode == ISD::UNDEF)
2690 // zext(undef) = 0, because the top bits will be zero.
2691 return getConstant(0, VT);
2693 case ISD::ANY_EXTEND:
2694 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2695 "Invalid ANY_EXTEND!");
2696 if (Operand.getValueType() == VT) return Operand; // noop extension
2697 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2698 "Invalid anyext node, dst < src!");
2699 assert((!VT.isVector() ||
2700 VT.getVectorNumElements() ==
2701 Operand.getValueType().getVectorNumElements()) &&
2702 "Vector element count mismatch!");
2704 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2705 OpOpcode == ISD::ANY_EXTEND)
2706 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2707 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2708 else if (OpOpcode == ISD::UNDEF)
2709 return getUNDEF(VT);
2711 // (ext (trunx x)) -> x
2712 if (OpOpcode == ISD::TRUNCATE) {
2713 SDValue OpOp = Operand.getNode()->getOperand(0);
2714 if (OpOp.getValueType() == VT)
2719 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2720 "Invalid TRUNCATE!");
2721 if (Operand.getValueType() == VT) return Operand; // noop truncate
2722 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2723 "Invalid truncate node, src < dst!");
2724 assert((!VT.isVector() ||
2725 VT.getVectorNumElements() ==
2726 Operand.getValueType().getVectorNumElements()) &&
2727 "Vector element count mismatch!");
2728 if (OpOpcode == ISD::TRUNCATE)
2729 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2730 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2731 OpOpcode == ISD::ANY_EXTEND) {
2732 // If the source is smaller than the dest, we still need an extend.
2733 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2734 .bitsLT(VT.getScalarType()))
2735 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2736 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2737 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2738 return Operand.getNode()->getOperand(0);
2740 if (OpOpcode == ISD::UNDEF)
2741 return getUNDEF(VT);
2744 // Basic sanity checking.
2745 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2746 && "Cannot BITCAST between types of different sizes!");
2747 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2748 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2749 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2750 if (OpOpcode == ISD::UNDEF)
2751 return getUNDEF(VT);
2753 case ISD::SCALAR_TO_VECTOR:
2754 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2755 (VT.getVectorElementType() == Operand.getValueType() ||
2756 (VT.getVectorElementType().isInteger() &&
2757 Operand.getValueType().isInteger() &&
2758 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2759 "Illegal SCALAR_TO_VECTOR node!");
2760 if (OpOpcode == ISD::UNDEF)
2761 return getUNDEF(VT);
2762 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2763 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2764 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2765 Operand.getConstantOperandVal(1) == 0 &&
2766 Operand.getOperand(0).getValueType() == VT)
2767 return Operand.getOperand(0);
2770 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2771 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2772 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2773 Operand.getNode()->getOperand(0));
2774 if (OpOpcode == ISD::FNEG) // --X -> X
2775 return Operand.getNode()->getOperand(0);
2778 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2779 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2784 SDVTList VTs = getVTList(VT);
2785 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2786 FoldingSetNodeID ID;
2787 SDValue Ops[1] = { Operand };
2788 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2790 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2791 return SDValue(E, 0);
2793 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2794 DL.getDebugLoc(), VTs, Operand);
2795 CSEMap.InsertNode(N, IP);
2797 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2798 DL.getDebugLoc(), VTs, Operand);
2801 AllNodes.push_back(N);
2805 return SDValue(N, 0);
2808 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2809 SDNode *Cst1, SDNode *Cst2) {
2810 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2811 SmallVector<SDValue, 4> Outputs;
2812 EVT SVT = VT.getScalarType();
2814 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2815 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2816 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2819 if (Scalar1 && Scalar2)
2820 // Scalar instruction.
2821 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2823 // For vectors extract each constant element into Inputs so we can constant
2824 // fold them individually.
2825 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2826 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2830 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2832 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2833 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2834 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2835 if (!V1 || !V2) // Not a constant, bail.
2838 if (V1->isOpaque() || V2->isOpaque())
2841 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2842 // FIXME: This is valid and could be handled by truncating the APInts.
2843 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2846 Inputs.push_back(std::make_pair(V1, V2));
2850 // We have a number of constant values, constant fold them element by element.
2851 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2852 const APInt &C1 = Inputs[I].first->getAPIntValue();
2853 const APInt &C2 = Inputs[I].second->getAPIntValue();
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 if (!C2.getBoolValue())
2868 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2871 if (!C2.getBoolValue())
2873 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2876 if (!C2.getBoolValue())
2878 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2881 if (!C2.getBoolValue())
2883 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2886 Outputs.push_back(getConstant(C1 & C2, SVT));
2889 Outputs.push_back(getConstant(C1 | C2, SVT));
2892 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2895 Outputs.push_back(getConstant(C1 << C2, SVT));
2898 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2901 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2904 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2907 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2914 // Handle the scalar case first.
2915 if (Scalar1 && Scalar2)
2916 return Outputs.back();
2918 // Otherwise build a big vector out of the scalar elements we generated.
2919 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2923 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2925 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2926 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2929 case ISD::TokenFactor:
2930 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2931 N2.getValueType() == MVT::Other && "Invalid token factor!");
2932 // Fold trivial token factors.
2933 if (N1.getOpcode() == ISD::EntryToken) return N2;
2934 if (N2.getOpcode() == ISD::EntryToken) return N1;
2935 if (N1 == N2) return N1;
2937 case ISD::CONCAT_VECTORS:
2938 // Concat of UNDEFs is UNDEF.
2939 if (N1.getOpcode() == ISD::UNDEF &&
2940 N2.getOpcode() == ISD::UNDEF)
2941 return getUNDEF(VT);
2943 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2944 // one big BUILD_VECTOR.
2945 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2946 N2.getOpcode() == ISD::BUILD_VECTOR) {
2947 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2948 N1.getNode()->op_end());
2949 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2950 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
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!");
2957 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2958 // worth handling here.
2959 if (N2C && N2C->isNullValue())
2961 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2968 assert(VT.isInteger() && "This operator does not apply to FP types!");
2969 assert(N1.getValueType() == N2.getValueType() &&
2970 N1.getValueType() == VT && "Binary operator types must match!");
2971 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2972 // it's worth handling here.
2973 if (N2C && N2C->isNullValue())
2983 assert(VT.isInteger() && "This operator does not apply to FP types!");
2984 assert(N1.getValueType() == N2.getValueType() &&
2985 N1.getValueType() == VT && "Binary operator types must match!");
2992 if (getTarget().Options.UnsafeFPMath) {
2993 if (Opcode == ISD::FADD) {
2995 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2996 if (CFP->getValueAPF().isZero())
2999 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3000 if (CFP->getValueAPF().isZero())
3002 } else if (Opcode == ISD::FSUB) {
3004 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3005 if (CFP->getValueAPF().isZero())
3007 } else if (Opcode == ISD::FMUL) {
3008 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3011 // If the first operand isn't the constant, try the second
3013 CFP = dyn_cast<ConstantFPSDNode>(N2);
3020 return SDValue(CFP,0);
3022 if (CFP->isExactlyValue(1.0))
3027 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3028 assert(N1.getValueType() == N2.getValueType() &&
3029 N1.getValueType() == VT && "Binary operator types must match!");
3031 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3032 assert(N1.getValueType() == VT &&
3033 N1.getValueType().isFloatingPoint() &&
3034 N2.getValueType().isFloatingPoint() &&
3035 "Invalid FCOPYSIGN!");
3042 assert(VT == N1.getValueType() &&
3043 "Shift operators return type must be the same as their first arg");
3044 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3045 "Shifts only work on integers");
3046 assert((!VT.isVector() || VT == N2.getValueType()) &&
3047 "Vector shift amounts must be in the same as their first arg");
3048 // Verify that the shift amount VT is bit enough to hold valid shift
3049 // amounts. This catches things like trying to shift an i1024 value by an
3050 // i8, which is easy to fall into in generic code that uses
3051 // TLI.getShiftAmount().
3052 assert(N2.getValueType().getSizeInBits() >=
3053 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3054 "Invalid use of small shift amount with oversized value!");
3056 // Always fold shifts of i1 values so the code generator doesn't need to
3057 // handle them. Since we know the size of the shift has to be less than the
3058 // size of the value, the shift/rotate count is guaranteed to be zero.
3061 if (N2C && N2C->isNullValue())
3064 case ISD::FP_ROUND_INREG: {
3065 EVT EVT = cast<VTSDNode>(N2)->getVT();
3066 assert(VT == N1.getValueType() && "Not an inreg round!");
3067 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3068 "Cannot FP_ROUND_INREG integer types");
3069 assert(EVT.isVector() == VT.isVector() &&
3070 "FP_ROUND_INREG type should be vector iff the operand "
3072 assert((!EVT.isVector() ||
3073 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3074 "Vector element counts must match in FP_ROUND_INREG");
3075 assert(EVT.bitsLE(VT) && "Not rounding down!");
3077 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3081 assert(VT.isFloatingPoint() &&
3082 N1.getValueType().isFloatingPoint() &&
3083 VT.bitsLE(N1.getValueType()) &&
3084 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3085 if (N1.getValueType() == VT) return N1; // noop conversion.
3087 case ISD::AssertSext:
3088 case ISD::AssertZext: {
3089 EVT EVT = cast<VTSDNode>(N2)->getVT();
3090 assert(VT == N1.getValueType() && "Not an inreg extend!");
3091 assert(VT.isInteger() && EVT.isInteger() &&
3092 "Cannot *_EXTEND_INREG FP types");
3093 assert(!EVT.isVector() &&
3094 "AssertSExt/AssertZExt type should be the vector element type "
3095 "rather than the vector type!");
3096 assert(EVT.bitsLE(VT) && "Not extending!");
3097 if (VT == EVT) return N1; // noop assertion.
3100 case ISD::SIGN_EXTEND_INREG: {
3101 EVT EVT = cast<VTSDNode>(N2)->getVT();
3102 assert(VT == N1.getValueType() && "Not an inreg extend!");
3103 assert(VT.isInteger() && EVT.isInteger() &&
3104 "Cannot *_EXTEND_INREG FP types");
3105 assert(EVT.isVector() == VT.isVector() &&
3106 "SIGN_EXTEND_INREG type should be vector iff the operand "
3108 assert((!EVT.isVector() ||
3109 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3110 "Vector element counts must match in SIGN_EXTEND_INREG");
3111 assert(EVT.bitsLE(VT) && "Not extending!");
3112 if (EVT == VT) return N1; // Not actually extending
3115 APInt Val = N1C->getAPIntValue();
3116 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3117 Val <<= Val.getBitWidth()-FromBits;
3118 Val = Val.ashr(Val.getBitWidth()-FromBits);
3119 return getConstant(Val, VT);
3123 case ISD::EXTRACT_VECTOR_ELT:
3124 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3125 if (N1.getOpcode() == ISD::UNDEF)
3126 return getUNDEF(VT);
3128 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3129 // expanding copies of large vectors from registers.
3131 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3132 N1.getNumOperands() > 0) {
3134 N1.getOperand(0).getValueType().getVectorNumElements();
3135 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3136 N1.getOperand(N2C->getZExtValue() / Factor),
3137 getConstant(N2C->getZExtValue() % Factor,
3138 N2.getValueType()));
3141 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3142 // expanding large vector constants.
3143 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3144 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3146 if (VT != Elt.getValueType())
3147 // If the vector element type is not legal, the BUILD_VECTOR operands
3148 // are promoted and implicitly truncated, and the result implicitly
3149 // extended. Make that explicit here.
3150 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3155 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3156 // operations are lowered to scalars.
3157 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3158 // If the indices are the same, return the inserted element else
3159 // if the indices are known different, extract the element from
3160 // the original vector.
3161 SDValue N1Op2 = N1.getOperand(2);
3162 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3164 if (N1Op2C && N2C) {
3165 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3166 if (VT == N1.getOperand(1).getValueType())
3167 return N1.getOperand(1);
3169 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3172 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3176 case ISD::EXTRACT_ELEMENT:
3177 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3178 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3179 (N1.getValueType().isInteger() == VT.isInteger()) &&
3180 N1.getValueType() != VT &&
3181 "Wrong types for EXTRACT_ELEMENT!");
3183 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3184 // 64-bit integers into 32-bit parts. Instead of building the extract of
3185 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3186 if (N1.getOpcode() == ISD::BUILD_PAIR)
3187 return N1.getOperand(N2C->getZExtValue());
3189 // EXTRACT_ELEMENT of a constant int is also very common.
3190 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3191 unsigned ElementSize = VT.getSizeInBits();
3192 unsigned Shift = ElementSize * N2C->getZExtValue();
3193 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3194 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3197 case ISD::EXTRACT_SUBVECTOR: {
3199 if (VT.isSimple() && N1.getValueType().isSimple()) {
3200 assert(VT.isVector() && N1.getValueType().isVector() &&
3201 "Extract subvector VTs must be a vectors!");
3202 assert(VT.getVectorElementType() ==
3203 N1.getValueType().getVectorElementType() &&
3204 "Extract subvector VTs must have the same element type!");
3205 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3206 "Extract subvector must be from larger vector to smaller vector!");
3208 if (isa<ConstantSDNode>(Index.getNode())) {
3209 assert((VT.getVectorNumElements() +
3210 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3211 <= N1.getValueType().getVectorNumElements())
3212 && "Extract subvector overflow!");
3215 // Trivial extraction.
3216 if (VT.getSimpleVT() == N1.getSimpleValueType())
3223 // Perform trivial constant folding.
3224 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3225 if (SV.getNode()) return SV;
3227 // Canonicalize constant to RHS if commutative.
3228 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3229 std::swap(N1C, N2C);
3233 // Constant fold FP operations.
3234 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3235 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3237 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3238 // Canonicalize constant to RHS if commutative.
3239 std::swap(N1CFP, N2CFP);
3242 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3243 APFloat::opStatus s;
3246 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3247 if (s != APFloat::opInvalidOp)
3248 return getConstantFP(V1, VT);
3251 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3252 if (s!=APFloat::opInvalidOp)
3253 return getConstantFP(V1, VT);
3256 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3257 if (s!=APFloat::opInvalidOp)
3258 return getConstantFP(V1, VT);
3261 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3262 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3263 return getConstantFP(V1, VT);
3266 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3267 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3268 return getConstantFP(V1, VT);
3270 case ISD::FCOPYSIGN:
3272 return getConstantFP(V1, VT);
3277 if (Opcode == ISD::FP_ROUND) {
3278 APFloat V = N1CFP->getValueAPF(); // make copy
3280 // This can return overflow, underflow, or inexact; we don't care.
3281 // FIXME need to be more flexible about rounding mode.
3282 (void)V.convert(EVTToAPFloatSemantics(VT),
3283 APFloat::rmNearestTiesToEven, &ignored);
3284 return getConstantFP(V, VT);
3288 // Canonicalize an UNDEF to the RHS, even over a constant.
3289 if (N1.getOpcode() == ISD::UNDEF) {
3290 if (isCommutativeBinOp(Opcode)) {
3294 case ISD::FP_ROUND_INREG:
3295 case ISD::SIGN_EXTEND_INREG:
3301 return N1; // fold op(undef, arg2) -> undef
3309 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3310 // For vectors, we can't easily build an all zero vector, just return
3317 // Fold a bunch of operators when the RHS is undef.
3318 if (N2.getOpcode() == ISD::UNDEF) {
3321 if (N1.getOpcode() == ISD::UNDEF)
3322 // Handle undef ^ undef -> 0 special case. This is a common
3324 return getConstant(0, VT);
3334 return N2; // fold op(arg1, undef) -> undef
3340 if (getTarget().Options.UnsafeFPMath)
3348 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3349 // For vectors, we can't easily build an all zero vector, just return
3354 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3355 // For vectors, we can't easily build an all one vector, just return
3363 // Memoize this node if possible.
3365 SDVTList VTs = getVTList(VT);
3366 if (VT != MVT::Glue) {
3367 SDValue Ops[] = { N1, N2 };
3368 FoldingSetNodeID ID;
3369 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3371 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3372 return SDValue(E, 0);
3374 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3375 DL.getDebugLoc(), VTs, N1, N2);
3376 CSEMap.InsertNode(N, IP);
3378 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3379 DL.getDebugLoc(), VTs, N1, N2);
3382 AllNodes.push_back(N);
3386 return SDValue(N, 0);
3389 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3390 SDValue N1, SDValue N2, SDValue N3) {
3391 // Perform various simplifications.
3392 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3395 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3396 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3397 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3398 if (N1CFP && N2CFP && N3CFP) {
3399 APFloat V1 = N1CFP->getValueAPF();
3400 const APFloat &V2 = N2CFP->getValueAPF();
3401 const APFloat &V3 = N3CFP->getValueAPF();
3402 APFloat::opStatus s =
3403 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3404 if (s != APFloat::opInvalidOp)
3405 return getConstantFP(V1, VT);
3409 case ISD::CONCAT_VECTORS:
3410 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3411 // one big BUILD_VECTOR.
3412 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3413 N2.getOpcode() == ISD::BUILD_VECTOR &&
3414 N3.getOpcode() == ISD::BUILD_VECTOR) {
3415 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3416 N1.getNode()->op_end());
3417 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3418 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3419 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3423 // Use FoldSetCC to simplify SETCC's.
3424 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3425 if (Simp.getNode()) return Simp;
3430 if (N1C->getZExtValue())
3431 return N2; // select true, X, Y -> X
3432 return N3; // select false, X, Y -> Y
3435 if (N2 == N3) return N2; // select C, X, X -> X
3437 case ISD::VECTOR_SHUFFLE:
3438 llvm_unreachable("should use getVectorShuffle constructor!");
3439 case ISD::INSERT_SUBVECTOR: {
3441 if (VT.isSimple() && N1.getValueType().isSimple()
3442 && N2.getValueType().isSimple()) {
3443 assert(VT.isVector() && N1.getValueType().isVector() &&
3444 N2.getValueType().isVector() &&
3445 "Insert subvector VTs must be a vectors");
3446 assert(VT == N1.getValueType() &&
3447 "Dest and insert subvector source types must match!");
3448 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3449 "Insert subvector must be from smaller vector to larger vector!");
3450 if (isa<ConstantSDNode>(Index.getNode())) {
3451 assert((N2.getValueType().getVectorNumElements() +
3452 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3453 <= VT.getVectorNumElements())
3454 && "Insert subvector overflow!");
3457 // Trivial insertion.
3458 if (VT.getSimpleVT() == N2.getSimpleValueType())
3464 // Fold bit_convert nodes from a type to themselves.
3465 if (N1.getValueType() == VT)
3470 // Memoize node if it doesn't produce a flag.
3472 SDVTList VTs = getVTList(VT);
3473 if (VT != MVT::Glue) {
3474 SDValue Ops[] = { N1, N2, N3 };
3475 FoldingSetNodeID ID;
3476 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3478 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3479 return SDValue(E, 0);
3481 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3482 DL.getDebugLoc(), VTs, N1, N2, N3);
3483 CSEMap.InsertNode(N, IP);
3485 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3486 DL.getDebugLoc(), VTs, N1, N2, N3);
3489 AllNodes.push_back(N);
3493 return SDValue(N, 0);
3496 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3497 SDValue N1, SDValue N2, SDValue N3,
3499 SDValue Ops[] = { N1, N2, N3, N4 };
3500 return getNode(Opcode, DL, VT, Ops, 4);
3503 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3504 SDValue N1, SDValue N2, SDValue N3,
3505 SDValue N4, SDValue N5) {
3506 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3507 return getNode(Opcode, DL, VT, Ops, 5);
3510 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3511 /// the incoming stack arguments to be loaded from the stack.
3512 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3513 SmallVector<SDValue, 8> ArgChains;
3515 // Include the original chain at the beginning of the list. When this is
3516 // used by target LowerCall hooks, this helps legalize find the
3517 // CALLSEQ_BEGIN node.
3518 ArgChains.push_back(Chain);
3520 // Add a chain value for each stack argument.
3521 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3522 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3523 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3524 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3525 if (FI->getIndex() < 0)
3526 ArgChains.push_back(SDValue(L, 1));
3528 // Build a tokenfactor for all the chains.
3529 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3530 &ArgChains[0], ArgChains.size());
3533 /// getMemsetValue - Vectorized representation of the memset value
3535 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3537 assert(Value.getOpcode() != ISD::UNDEF);
3539 unsigned NumBits = VT.getScalarType().getSizeInBits();
3540 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3541 assert(C->getAPIntValue().getBitWidth() == 8);
3542 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3544 return DAG.getConstant(Val, VT);
3545 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3548 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3550 // Use a multiplication with 0x010101... to extend the input to the
3552 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3553 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3559 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3560 /// used when a memcpy is turned into a memset when the source is a constant
3562 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3563 const TargetLowering &TLI, StringRef Str) {
3564 // Handle vector with all elements zero.
3567 return DAG.getConstant(0, VT);
3568 else if (VT == MVT::f32 || VT == MVT::f64)
3569 return DAG.getConstantFP(0.0, VT);
3570 else if (VT.isVector()) {
3571 unsigned NumElts = VT.getVectorNumElements();
3572 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3573 return DAG.getNode(ISD::BITCAST, dl, VT,
3574 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3577 llvm_unreachable("Expected type!");
3580 assert(!VT.isVector() && "Can't handle vector type here!");
3581 unsigned NumVTBits = VT.getSizeInBits();
3582 unsigned NumVTBytes = NumVTBits / 8;
3583 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3585 APInt Val(NumVTBits, 0);
3586 if (TLI.isLittleEndian()) {
3587 for (unsigned i = 0; i != NumBytes; ++i)
3588 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3590 for (unsigned i = 0; i != NumBytes; ++i)
3591 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3594 // If the "cost" of materializing the integer immediate is less than the cost
3595 // of a load, then it is cost effective to turn the load into the immediate.
3596 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3597 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3598 return DAG.getConstant(Val, VT);
3599 return SDValue(0, 0);
3602 /// getMemBasePlusOffset - Returns base and offset node for the
3604 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3605 SelectionDAG &DAG) {
3606 EVT VT = Base.getValueType();
3607 return DAG.getNode(ISD::ADD, dl,
3608 VT, Base, DAG.getConstant(Offset, VT));
3611 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3613 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3614 unsigned SrcDelta = 0;
3615 GlobalAddressSDNode *G = NULL;
3616 if (Src.getOpcode() == ISD::GlobalAddress)
3617 G = cast<GlobalAddressSDNode>(Src);
3618 else if (Src.getOpcode() == ISD::ADD &&
3619 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3620 Src.getOperand(1).getOpcode() == ISD::Constant) {
3621 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3622 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3627 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3630 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3631 /// to replace the memset / memcpy. Return true if the number of memory ops
3632 /// is below the threshold. It returns the types of the sequence of
3633 /// memory ops to perform memset / memcpy by reference.
3634 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3635 unsigned Limit, uint64_t Size,
3636 unsigned DstAlign, unsigned SrcAlign,
3642 const TargetLowering &TLI) {
3643 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3644 "Expecting memcpy / memset source to meet alignment requirement!");
3645 // If 'SrcAlign' is zero, that means the memory operation does not need to
3646 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3647 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3648 // is the specified alignment of the memory operation. If it is zero, that
3649 // means it's possible to change the alignment of the destination.
3650 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3651 // not need to be loaded.
3652 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3653 IsMemset, ZeroMemset, MemcpyStrSrc,
3654 DAG.getMachineFunction());
3656 if (VT == MVT::Other) {
3658 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3659 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3660 VT = TLI.getPointerTy();
3662 switch (DstAlign & 7) {
3663 case 0: VT = MVT::i64; break;
3664 case 4: VT = MVT::i32; break;
3665 case 2: VT = MVT::i16; break;
3666 default: VT = MVT::i8; break;
3671 while (!TLI.isTypeLegal(LVT))
3672 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3673 assert(LVT.isInteger());
3679 unsigned NumMemOps = 0;
3681 unsigned VTSize = VT.getSizeInBits() / 8;
3682 while (VTSize > Size) {
3683 // For now, only use non-vector load / store's for the left-over pieces.
3688 if (VT.isVector() || VT.isFloatingPoint()) {
3689 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3690 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3691 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3693 else if (NewVT == MVT::i64 &&
3694 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3695 TLI.isSafeMemOpType(MVT::f64)) {
3696 // i64 is usually not legal on 32-bit targets, but f64 may be.
3704 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3705 if (NewVT == MVT::i8)
3707 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3709 NewVTSize = NewVT.getSizeInBits() / 8;
3711 // If the new VT cannot cover all of the remaining bits, then consider
3712 // issuing a (or a pair of) unaligned and overlapping load / store.
3713 // FIXME: Only does this for 64-bit or more since we don't have proper
3714 // cost model for unaligned load / store.
3717 if (NumMemOps && AllowOverlap &&
3718 VTSize >= 8 && NewVTSize < Size &&
3719 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3727 if (++NumMemOps > Limit)
3730 MemOps.push_back(VT);
3737 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3738 SDValue Chain, SDValue Dst,
3739 SDValue Src, uint64_t Size,
3740 unsigned Align, bool isVol,
3742 MachinePointerInfo DstPtrInfo,
3743 MachinePointerInfo SrcPtrInfo) {
3744 // Turn a memcpy of undef to nop.
3745 if (Src.getOpcode() == ISD::UNDEF)
3748 // Expand memcpy to a series of load and store ops if the size operand falls
3749 // below a certain threshold.
3750 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3751 // rather than maybe a humongous number of loads and stores.
3752 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3753 std::vector<EVT> MemOps;
3754 bool DstAlignCanChange = false;
3755 MachineFunction &MF = DAG.getMachineFunction();
3756 MachineFrameInfo *MFI = MF.getFrameInfo();
3758 MF.getFunction()->getAttributes().
3759 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3760 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3761 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3762 DstAlignCanChange = true;
3763 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3764 if (Align > SrcAlign)
3767 bool CopyFromStr = isMemSrcFromString(Src, Str);
3768 bool isZeroStr = CopyFromStr && Str.empty();
3769 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3771 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3772 (DstAlignCanChange ? 0 : Align),
3773 (isZeroStr ? 0 : SrcAlign),
3774 false, false, CopyFromStr, true, DAG, TLI))
3777 if (DstAlignCanChange) {
3778 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3779 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3781 // Don't promote to an alignment that would require dynamic stack
3783 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3784 if (!TRI->needsStackRealignment(MF))
3785 while (NewAlign > Align &&
3786 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3789 if (NewAlign > Align) {
3790 // Give the stack frame object a larger alignment if needed.
3791 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3792 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3797 SmallVector<SDValue, 8> OutChains;
3798 unsigned NumMemOps = MemOps.size();
3799 uint64_t SrcOff = 0, DstOff = 0;
3800 for (unsigned i = 0; i != NumMemOps; ++i) {
3802 unsigned VTSize = VT.getSizeInBits() / 8;
3803 SDValue Value, Store;
3805 if (VTSize > Size) {
3806 // Issuing an unaligned load / store pair that overlaps with the previous
3807 // pair. Adjust the offset accordingly.
3808 assert(i == NumMemOps-1 && i != 0);
3809 SrcOff -= VTSize - Size;
3810 DstOff -= VTSize - Size;
3814 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3815 // It's unlikely a store of a vector immediate can be done in a single
3816 // instruction. It would require a load from a constantpool first.
3817 // We only handle zero vectors here.
3818 // FIXME: Handle other cases where store of vector immediate is done in
3819 // a single instruction.
3820 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3821 if (Value.getNode())
3822 Store = DAG.getStore(Chain, dl, Value,
3823 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3824 DstPtrInfo.getWithOffset(DstOff), isVol,
3828 if (!Store.getNode()) {
3829 // The type might not be legal for the target. This should only happen
3830 // if the type is smaller than a legal type, as on PPC, so the right
3831 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3832 // to Load/Store if NVT==VT.
3833 // FIXME does the case above also need this?
3834 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3835 assert(NVT.bitsGE(VT));
3836 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3837 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3838 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3839 MinAlign(SrcAlign, SrcOff));
3840 Store = DAG.getTruncStore(Chain, dl, Value,
3841 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3842 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3845 OutChains.push_back(Store);
3851 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3852 &OutChains[0], OutChains.size());
3855 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3856 SDValue Chain, SDValue Dst,
3857 SDValue Src, uint64_t Size,
3858 unsigned Align, bool isVol,
3860 MachinePointerInfo DstPtrInfo,
3861 MachinePointerInfo SrcPtrInfo) {
3862 // Turn a memmove of undef to nop.
3863 if (Src.getOpcode() == ISD::UNDEF)
3866 // Expand memmove to a series of load and store ops if the size operand falls
3867 // below a certain threshold.
3868 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3869 std::vector<EVT> MemOps;
3870 bool DstAlignCanChange = false;
3871 MachineFunction &MF = DAG.getMachineFunction();
3872 MachineFrameInfo *MFI = MF.getFrameInfo();
3873 bool OptSize = MF.getFunction()->getAttributes().
3874 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3875 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3876 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3877 DstAlignCanChange = true;
3878 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3879 if (Align > SrcAlign)
3881 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3883 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3884 (DstAlignCanChange ? 0 : Align), SrcAlign,
3885 false, false, false, false, DAG, TLI))
3888 if (DstAlignCanChange) {
3889 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3890 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3891 if (NewAlign > Align) {
3892 // Give the stack frame object a larger alignment if needed.
3893 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3894 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3899 uint64_t SrcOff = 0, DstOff = 0;
3900 SmallVector<SDValue, 8> LoadValues;
3901 SmallVector<SDValue, 8> LoadChains;
3902 SmallVector<SDValue, 8> OutChains;
3903 unsigned NumMemOps = MemOps.size();
3904 for (unsigned i = 0; i < NumMemOps; i++) {
3906 unsigned VTSize = VT.getSizeInBits() / 8;
3909 Value = DAG.getLoad(VT, dl, Chain,
3910 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3911 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3912 false, false, SrcAlign);
3913 LoadValues.push_back(Value);
3914 LoadChains.push_back(Value.getValue(1));
3917 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3918 &LoadChains[0], LoadChains.size());
3920 for (unsigned i = 0; i < NumMemOps; i++) {
3922 unsigned VTSize = VT.getSizeInBits() / 8;
3925 Store = DAG.getStore(Chain, dl, LoadValues[i],
3926 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3927 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3928 OutChains.push_back(Store);
3932 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3933 &OutChains[0], OutChains.size());
3936 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3939 /// \param DAG Selection DAG where lowered code is placed.
3940 /// \param dl Link to corresponding IR location.
3941 /// \param Chain Control flow dependency.
3942 /// \param Dst Pointer to destination memory location.
3943 /// \param Src Value of byte to write into the memory.
3944 /// \param Size Number of bytes to write.
3945 /// \param Align Alignment of the destination in bytes.
3946 /// \param isVol True if destination is volatile.
3947 /// \param DstPtrInfo IR information on the memory pointer.
3948 /// \returns New head in the control flow, if lowering was successful, empty
3949 /// SDValue otherwise.
3951 /// The function tries to replace 'llvm.memset' intrinsic with several store
3952 /// operations and value calculation code. This is usually profitable for small
3954 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3955 SDValue Chain, SDValue Dst,
3956 SDValue Src, uint64_t Size,
3957 unsigned Align, bool isVol,
3958 MachinePointerInfo DstPtrInfo) {
3959 // Turn a memset of undef to nop.
3960 if (Src.getOpcode() == ISD::UNDEF)
3963 // Expand memset to a series of load/store ops if the size operand
3964 // falls below a certain threshold.
3965 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3966 std::vector<EVT> MemOps;
3967 bool DstAlignCanChange = false;
3968 MachineFunction &MF = DAG.getMachineFunction();
3969 MachineFrameInfo *MFI = MF.getFrameInfo();
3970 bool OptSize = MF.getFunction()->getAttributes().
3971 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3972 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3973 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3974 DstAlignCanChange = true;
3976 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3977 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3978 Size, (DstAlignCanChange ? 0 : Align), 0,
3979 true, IsZeroVal, false, true, DAG, TLI))
3982 if (DstAlignCanChange) {
3983 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3984 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3985 if (NewAlign > Align) {
3986 // Give the stack frame object a larger alignment if needed.
3987 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3988 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3993 SmallVector<SDValue, 8> OutChains;
3994 uint64_t DstOff = 0;
3995 unsigned NumMemOps = MemOps.size();
3997 // Find the largest store and generate the bit pattern for it.
3998 EVT LargestVT = MemOps[0];
3999 for (unsigned i = 1; i < NumMemOps; i++)
4000 if (MemOps[i].bitsGT(LargestVT))
4001 LargestVT = MemOps[i];
4002 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4004 for (unsigned i = 0; i < NumMemOps; i++) {
4006 unsigned VTSize = VT.getSizeInBits() / 8;
4007 if (VTSize > Size) {
4008 // Issuing an unaligned load / store pair that overlaps with the previous
4009 // pair. Adjust the offset accordingly.
4010 assert(i == NumMemOps-1 && i != 0);
4011 DstOff -= VTSize - Size;
4014 // If this store is smaller than the largest store see whether we can get
4015 // the smaller value for free with a truncate.
4016 SDValue Value = MemSetValue;
4017 if (VT.bitsLT(LargestVT)) {
4018 if (!LargestVT.isVector() && !VT.isVector() &&
4019 TLI.isTruncateFree(LargestVT, VT))
4020 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4022 Value = getMemsetValue(Src, VT, DAG, dl);
4024 assert(Value.getValueType() == VT && "Value with wrong type.");
4025 SDValue Store = DAG.getStore(Chain, dl, Value,
4026 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4027 DstPtrInfo.getWithOffset(DstOff),
4028 isVol, false, Align);
4029 OutChains.push_back(Store);
4030 DstOff += VT.getSizeInBits() / 8;
4034 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4035 &OutChains[0], OutChains.size());
4038 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4039 SDValue Src, SDValue Size,
4040 unsigned Align, bool isVol, bool AlwaysInline,
4041 MachinePointerInfo DstPtrInfo,
4042 MachinePointerInfo SrcPtrInfo) {
4043 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4045 // Check to see if we should lower the memcpy to loads and stores first.
4046 // For cases within the target-specified limits, this is the best choice.
4047 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4049 // Memcpy with size zero? Just return the original chain.
4050 if (ConstantSize->isNullValue())
4053 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4054 ConstantSize->getZExtValue(),Align,
4055 isVol, false, DstPtrInfo, SrcPtrInfo);
4056 if (Result.getNode())
4060 // Then check to see if we should lower the memcpy with target-specific
4061 // code. If the target chooses to do this, this is the next best.
4063 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4064 isVol, AlwaysInline,
4065 DstPtrInfo, SrcPtrInfo);
4066 if (Result.getNode())
4069 // If we really need inline code and the target declined to provide it,
4070 // use a (potentially long) sequence of loads and stores.
4072 assert(ConstantSize && "AlwaysInline requires a constant size!");
4073 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4074 ConstantSize->getZExtValue(), Align, isVol,
4075 true, DstPtrInfo, SrcPtrInfo);
4078 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4079 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4080 // respect volatile, so they may do things like read or write memory
4081 // beyond the given memory regions. But fixing this isn't easy, and most
4082 // people don't care.
4084 const TargetLowering *TLI = TM.getTargetLowering();
4086 // Emit a library call.
4087 TargetLowering::ArgListTy Args;
4088 TargetLowering::ArgListEntry Entry;
4089 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4090 Entry.Node = Dst; Args.push_back(Entry);
4091 Entry.Node = Src; Args.push_back(Entry);
4092 Entry.Node = Size; Args.push_back(Entry);
4093 // FIXME: pass in SDLoc
4095 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4096 false, false, false, false, 0,
4097 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4098 /*isTailCall=*/false,
4099 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4100 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4101 TLI->getPointerTy()),
4103 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4105 return CallResult.second;
4108 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4109 SDValue Src, SDValue Size,
4110 unsigned Align, bool isVol,
4111 MachinePointerInfo DstPtrInfo,
4112 MachinePointerInfo SrcPtrInfo) {
4113 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4115 // Check to see if we should lower the memmove to loads and stores first.
4116 // For cases within the target-specified limits, this is the best choice.
4117 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4119 // Memmove with size zero? Just return the original chain.
4120 if (ConstantSize->isNullValue())
4124 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4125 ConstantSize->getZExtValue(), Align, isVol,
4126 false, DstPtrInfo, SrcPtrInfo);
4127 if (Result.getNode())
4131 // Then check to see if we should lower the memmove with target-specific
4132 // code. If the target chooses to do this, this is the next best.
4134 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4135 DstPtrInfo, SrcPtrInfo);
4136 if (Result.getNode())
4139 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4140 // not be safe. See memcpy above for more details.
4142 const TargetLowering *TLI = TM.getTargetLowering();
4144 // Emit a library call.
4145 TargetLowering::ArgListTy Args;
4146 TargetLowering::ArgListEntry Entry;
4147 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4148 Entry.Node = Dst; Args.push_back(Entry);
4149 Entry.Node = Src; Args.push_back(Entry);
4150 Entry.Node = Size; Args.push_back(Entry);
4151 // FIXME: pass in SDLoc
4153 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4154 false, false, false, false, 0,
4155 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4156 /*isTailCall=*/false,
4157 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4158 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4159 TLI->getPointerTy()),
4161 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4163 return CallResult.second;
4166 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4167 SDValue Src, SDValue Size,
4168 unsigned Align, bool isVol,
4169 MachinePointerInfo DstPtrInfo) {
4170 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4172 // Check to see if we should lower the memset to stores first.
4173 // For cases within the target-specified limits, this is the best choice.
4174 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4176 // Memset with size zero? Just return the original chain.
4177 if (ConstantSize->isNullValue())
4181 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4182 Align, isVol, DstPtrInfo);
4184 if (Result.getNode())
4188 // Then check to see if we should lower the memset with target-specific
4189 // code. If the target chooses to do this, this is the next best.
4191 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4193 if (Result.getNode())
4196 // Emit a library call.
4197 const TargetLowering *TLI = TM.getTargetLowering();
4198 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4199 TargetLowering::ArgListTy Args;
4200 TargetLowering::ArgListEntry Entry;
4201 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4202 Args.push_back(Entry);
4203 // Extend or truncate the argument to be an i32 value for the call.
4204 if (Src.getValueType().bitsGT(MVT::i32))
4205 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4207 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4209 Entry.Ty = Type::getInt32Ty(*getContext());
4210 Entry.isSExt = true;
4211 Args.push_back(Entry);
4213 Entry.Ty = IntPtrTy;
4214 Entry.isSExt = false;
4215 Args.push_back(Entry);
4216 // FIXME: pass in SDLoc
4218 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4219 false, false, false, false, 0,
4220 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4221 /*isTailCall=*/false,
4222 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4223 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4224 TLI->getPointerTy()),
4226 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4228 return CallResult.second;
4231 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4232 SDVTList VTList, SDValue *Ops, unsigned NumOps,
4233 MachineMemOperand *MMO,
4234 AtomicOrdering SuccessOrdering,
4235 AtomicOrdering FailureOrdering,
4236 SynchronizationScope SynchScope) {
4237 FoldingSetNodeID ID;
4238 ID.AddInteger(MemVT.getRawBits());
4239 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4240 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4242 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4243 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4244 return SDValue(E, 0);
4247 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4248 // SDNode doesn't have access to it. This memory will be "leaked" when
4249 // the node is deallocated, but recovered when the allocator is released.
4250 // If the number of operands is less than 5 we use AtomicSDNode's internal
4252 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4254 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4255 dl.getDebugLoc(), VTList, MemVT,
4256 Ops, DynOps, NumOps, MMO,
4257 SuccessOrdering, FailureOrdering,
4259 CSEMap.InsertNode(N, IP);
4260 AllNodes.push_back(N);
4261 return SDValue(N, 0);
4264 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4265 SDVTList VTList, SDValue *Ops, unsigned NumOps,
4266 MachineMemOperand *MMO,
4267 AtomicOrdering Ordering,
4268 SynchronizationScope SynchScope) {
4269 return getAtomic(Opcode, dl, MemVT, VTList, Ops, NumOps, MMO, Ordering,
4270 Ordering, SynchScope);
4273 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4274 SDValue Chain, SDValue Ptr, SDValue Cmp,
4275 SDValue Swp, MachinePointerInfo PtrInfo,
4277 AtomicOrdering SuccessOrdering,
4278 AtomicOrdering FailureOrdering,
4279 SynchronizationScope SynchScope) {
4280 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4281 Alignment = getEVTAlignment(MemVT);
4283 MachineFunction &MF = getMachineFunction();
4285 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4286 // For now, atomics are considered to be volatile always.
4287 // FIXME: Volatile isn't really correct; we should keep track of atomic
4288 // orderings in the memoperand.
4289 unsigned Flags = MachineMemOperand::MOVolatile;
4290 if (Opcode != ISD::ATOMIC_STORE)
4291 Flags |= MachineMemOperand::MOLoad;
4292 if (Opcode != ISD::ATOMIC_LOAD)
4293 Flags |= MachineMemOperand::MOStore;
4295 MachineMemOperand *MMO =
4296 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4298 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4299 SuccessOrdering, FailureOrdering, SynchScope);
4302 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4304 SDValue Ptr, SDValue Cmp,
4305 SDValue Swp, MachineMemOperand *MMO,
4306 AtomicOrdering SuccessOrdering,
4307 AtomicOrdering FailureOrdering,
4308 SynchronizationScope SynchScope) {
4309 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4310 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4312 EVT VT = Cmp.getValueType();
4314 SDVTList VTs = getVTList(VT, MVT::Other);
4315 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4316 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, SuccessOrdering,
4317 FailureOrdering, SynchScope);
4320 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4322 SDValue Ptr, SDValue Val,
4323 const Value* PtrVal,
4325 AtomicOrdering Ordering,
4326 SynchronizationScope SynchScope) {
4327 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4328 Alignment = getEVTAlignment(MemVT);
4330 MachineFunction &MF = getMachineFunction();
4331 // An atomic store does not load. An atomic load does not store.
4332 // (An atomicrmw obviously both loads and stores.)
4333 // For now, atomics are considered to be volatile always, and they are
4335 // FIXME: Volatile isn't really correct; we should keep track of atomic
4336 // orderings in the memoperand.
4337 unsigned Flags = MachineMemOperand::MOVolatile;
4338 if (Opcode != ISD::ATOMIC_STORE)
4339 Flags |= MachineMemOperand::MOLoad;
4340 if (Opcode != ISD::ATOMIC_LOAD)
4341 Flags |= MachineMemOperand::MOStore;
4343 MachineMemOperand *MMO =
4344 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4345 MemVT.getStoreSize(), Alignment);
4347 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4348 Ordering, SynchScope);
4351 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4353 SDValue Ptr, SDValue Val,
4354 MachineMemOperand *MMO,
4355 AtomicOrdering Ordering,
4356 SynchronizationScope SynchScope) {
4357 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4358 Opcode == ISD::ATOMIC_LOAD_SUB ||
4359 Opcode == ISD::ATOMIC_LOAD_AND ||
4360 Opcode == ISD::ATOMIC_LOAD_OR ||
4361 Opcode == ISD::ATOMIC_LOAD_XOR ||
4362 Opcode == ISD::ATOMIC_LOAD_NAND ||
4363 Opcode == ISD::ATOMIC_LOAD_MIN ||
4364 Opcode == ISD::ATOMIC_LOAD_MAX ||
4365 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4366 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4367 Opcode == ISD::ATOMIC_SWAP ||
4368 Opcode == ISD::ATOMIC_STORE) &&
4369 "Invalid Atomic Op");
4371 EVT VT = Val.getValueType();
4373 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4374 getVTList(VT, MVT::Other);
4375 SDValue Ops[] = {Chain, Ptr, Val};
4376 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4379 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4380 EVT VT, SDValue Chain,
4382 const Value* PtrVal,
4384 AtomicOrdering Ordering,
4385 SynchronizationScope SynchScope) {
4386 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4387 Alignment = getEVTAlignment(MemVT);
4389 MachineFunction &MF = getMachineFunction();
4390 // An atomic store does not load. An atomic load does not store.
4391 // (An atomicrmw obviously both loads and stores.)
4392 // For now, atomics are considered to be volatile always, and they are
4394 // FIXME: Volatile isn't really correct; we should keep track of atomic
4395 // orderings in the memoperand.
4396 unsigned Flags = MachineMemOperand::MOVolatile;
4397 if (Opcode != ISD::ATOMIC_STORE)
4398 Flags |= MachineMemOperand::MOLoad;
4399 if (Opcode != ISD::ATOMIC_LOAD)
4400 Flags |= MachineMemOperand::MOStore;
4402 MachineMemOperand *MMO =
4403 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4404 MemVT.getStoreSize(), Alignment);
4406 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4407 Ordering, SynchScope);
4410 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4411 EVT VT, SDValue Chain,
4413 MachineMemOperand *MMO,
4414 AtomicOrdering Ordering,
4415 SynchronizationScope SynchScope) {
4416 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4418 SDVTList VTs = getVTList(VT, MVT::Other);
4419 SDValue Ops[] = {Chain, Ptr};
4420 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4423 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4424 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4429 SmallVector<EVT, 4> VTs;
4430 VTs.reserve(NumOps);
4431 for (unsigned i = 0; i < NumOps; ++i)
4432 VTs.push_back(Ops[i].getValueType());
4433 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4438 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4439 const EVT *VTs, unsigned NumVTs,
4440 const SDValue *Ops, unsigned NumOps,
4441 EVT MemVT, MachinePointerInfo PtrInfo,
4442 unsigned Align, bool Vol,
4443 bool ReadMem, bool WriteMem) {
4444 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4445 MemVT, PtrInfo, Align, Vol,
4450 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4451 const SDValue *Ops, unsigned NumOps,
4452 EVT MemVT, MachinePointerInfo PtrInfo,
4453 unsigned Align, bool Vol,
4454 bool ReadMem, bool WriteMem) {
4455 if (Align == 0) // Ensure that codegen never sees alignment 0
4456 Align = getEVTAlignment(MemVT);
4458 MachineFunction &MF = getMachineFunction();
4461 Flags |= MachineMemOperand::MOStore;
4463 Flags |= MachineMemOperand::MOLoad;
4465 Flags |= MachineMemOperand::MOVolatile;
4466 MachineMemOperand *MMO =
4467 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4469 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4473 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4474 const SDValue *Ops, unsigned NumOps,
4475 EVT MemVT, MachineMemOperand *MMO) {
4476 assert((Opcode == ISD::INTRINSIC_VOID ||
4477 Opcode == ISD::INTRINSIC_W_CHAIN ||
4478 Opcode == ISD::PREFETCH ||
4479 Opcode == ISD::LIFETIME_START ||
4480 Opcode == ISD::LIFETIME_END ||
4481 (Opcode <= INT_MAX &&
4482 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4483 "Opcode is not a memory-accessing opcode!");
4485 // Memoize the node unless it returns a flag.
4486 MemIntrinsicSDNode *N;
4487 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4488 FoldingSetNodeID ID;
4489 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4490 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4492 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4493 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4494 return SDValue(E, 0);
4497 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4498 dl.getDebugLoc(), VTList, Ops,
4499 NumOps, MemVT, MMO);
4500 CSEMap.InsertNode(N, IP);
4502 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4503 dl.getDebugLoc(), VTList, Ops,
4504 NumOps, MemVT, MMO);
4506 AllNodes.push_back(N);
4507 return SDValue(N, 0);
4510 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4511 /// MachinePointerInfo record from it. This is particularly useful because the
4512 /// code generator has many cases where it doesn't bother passing in a
4513 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4514 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4515 // If this is FI+Offset, we can model it.
4516 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4517 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4519 // If this is (FI+Offset1)+Offset2, we can model it.
4520 if (Ptr.getOpcode() != ISD::ADD ||
4521 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4522 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4523 return MachinePointerInfo();
4525 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4526 return MachinePointerInfo::getFixedStack(FI, Offset+
4527 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4530 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4531 /// MachinePointerInfo record from it. This is particularly useful because the
4532 /// code generator has many cases where it doesn't bother passing in a
4533 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4534 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4535 // If the 'Offset' value isn't a constant, we can't handle this.
4536 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4537 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4538 if (OffsetOp.getOpcode() == ISD::UNDEF)
4539 return InferPointerInfo(Ptr);
4540 return MachinePointerInfo();
4545 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4546 EVT VT, SDLoc dl, SDValue Chain,
4547 SDValue Ptr, SDValue Offset,
4548 MachinePointerInfo PtrInfo, EVT MemVT,
4549 bool isVolatile, bool isNonTemporal, bool isInvariant,
4550 unsigned Alignment, const MDNode *TBAAInfo,
4551 const MDNode *Ranges) {
4552 assert(Chain.getValueType() == MVT::Other &&
4553 "Invalid chain type");
4554 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4555 Alignment = getEVTAlignment(VT);
4557 unsigned Flags = MachineMemOperand::MOLoad;
4559 Flags |= MachineMemOperand::MOVolatile;
4561 Flags |= MachineMemOperand::MONonTemporal;
4563 Flags |= MachineMemOperand::MOInvariant;
4565 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4568 PtrInfo = InferPointerInfo(Ptr, Offset);
4570 MachineFunction &MF = getMachineFunction();
4571 MachineMemOperand *MMO =
4572 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4574 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4578 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4579 EVT VT, SDLoc dl, SDValue Chain,
4580 SDValue Ptr, SDValue Offset, EVT MemVT,
4581 MachineMemOperand *MMO) {
4583 ExtType = ISD::NON_EXTLOAD;
4584 } else if (ExtType == ISD::NON_EXTLOAD) {
4585 assert(VT == MemVT && "Non-extending load from different memory type!");
4588 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4589 "Should only be an extending load, not truncating!");
4590 assert(VT.isInteger() == MemVT.isInteger() &&
4591 "Cannot convert from FP to Int or Int -> FP!");
4592 assert(VT.isVector() == MemVT.isVector() &&
4593 "Cannot use trunc store to convert to or from a vector!");
4594 assert((!VT.isVector() ||
4595 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4596 "Cannot use trunc store to change the number of vector elements!");
4599 bool Indexed = AM != ISD::UNINDEXED;
4600 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4601 "Unindexed load with an offset!");
4603 SDVTList VTs = Indexed ?
4604 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4605 SDValue Ops[] = { Chain, Ptr, Offset };
4606 FoldingSetNodeID ID;
4607 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4608 ID.AddInteger(MemVT.getRawBits());
4609 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4610 MMO->isNonTemporal(),
4611 MMO->isInvariant()));
4612 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4614 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4615 cast<LoadSDNode>(E)->refineAlignment(MMO);
4616 return SDValue(E, 0);
4618 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4619 dl.getDebugLoc(), VTs, AM, ExtType,
4621 CSEMap.InsertNode(N, IP);
4622 AllNodes.push_back(N);
4623 return SDValue(N, 0);
4626 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4627 SDValue Chain, SDValue Ptr,
4628 MachinePointerInfo PtrInfo,
4629 bool isVolatile, bool isNonTemporal,
4630 bool isInvariant, unsigned Alignment,
4631 const MDNode *TBAAInfo,
4632 const MDNode *Ranges) {
4633 SDValue Undef = getUNDEF(Ptr.getValueType());
4634 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4635 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4639 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4640 SDValue Chain, SDValue Ptr,
4641 MachineMemOperand *MMO) {
4642 SDValue Undef = getUNDEF(Ptr.getValueType());
4643 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4647 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4648 SDValue Chain, SDValue Ptr,
4649 MachinePointerInfo PtrInfo, EVT MemVT,
4650 bool isVolatile, bool isNonTemporal,
4651 unsigned Alignment, const MDNode *TBAAInfo) {
4652 SDValue Undef = getUNDEF(Ptr.getValueType());
4653 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4654 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4659 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4660 SDValue Chain, SDValue Ptr, EVT MemVT,
4661 MachineMemOperand *MMO) {
4662 SDValue Undef = getUNDEF(Ptr.getValueType());
4663 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4668 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4669 SDValue Offset, ISD::MemIndexedMode AM) {
4670 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4671 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4672 "Load is already a indexed load!");
4673 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4674 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4675 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4676 false, LD->getAlignment());
4679 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4680 SDValue Ptr, MachinePointerInfo PtrInfo,
4681 bool isVolatile, bool isNonTemporal,
4682 unsigned Alignment, const MDNode *TBAAInfo) {
4683 assert(Chain.getValueType() == MVT::Other &&
4684 "Invalid chain type");
4685 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4686 Alignment = getEVTAlignment(Val.getValueType());
4688 unsigned Flags = MachineMemOperand::MOStore;
4690 Flags |= MachineMemOperand::MOVolatile;
4692 Flags |= MachineMemOperand::MONonTemporal;
4695 PtrInfo = InferPointerInfo(Ptr);
4697 MachineFunction &MF = getMachineFunction();
4698 MachineMemOperand *MMO =
4699 MF.getMachineMemOperand(PtrInfo, Flags,
4700 Val.getValueType().getStoreSize(), Alignment,
4703 return getStore(Chain, dl, Val, Ptr, MMO);
4706 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4707 SDValue Ptr, MachineMemOperand *MMO) {
4708 assert(Chain.getValueType() == MVT::Other &&
4709 "Invalid chain type");
4710 EVT VT = Val.getValueType();
4711 SDVTList VTs = getVTList(MVT::Other);
4712 SDValue Undef = getUNDEF(Ptr.getValueType());
4713 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4714 FoldingSetNodeID ID;
4715 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4716 ID.AddInteger(VT.getRawBits());
4717 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4718 MMO->isNonTemporal(), MMO->isInvariant()));
4719 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4721 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4722 cast<StoreSDNode>(E)->refineAlignment(MMO);
4723 return SDValue(E, 0);
4725 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4726 dl.getDebugLoc(), VTs,
4727 ISD::UNINDEXED, false, VT, MMO);
4728 CSEMap.InsertNode(N, IP);
4729 AllNodes.push_back(N);
4730 return SDValue(N, 0);
4733 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4734 SDValue Ptr, MachinePointerInfo PtrInfo,
4735 EVT SVT,bool isVolatile, bool isNonTemporal,
4737 const MDNode *TBAAInfo) {
4738 assert(Chain.getValueType() == MVT::Other &&
4739 "Invalid chain type");
4740 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4741 Alignment = getEVTAlignment(SVT);
4743 unsigned Flags = MachineMemOperand::MOStore;
4745 Flags |= MachineMemOperand::MOVolatile;
4747 Flags |= MachineMemOperand::MONonTemporal;
4750 PtrInfo = InferPointerInfo(Ptr);
4752 MachineFunction &MF = getMachineFunction();
4753 MachineMemOperand *MMO =
4754 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4757 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4760 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4761 SDValue Ptr, EVT SVT,
4762 MachineMemOperand *MMO) {
4763 EVT VT = Val.getValueType();
4765 assert(Chain.getValueType() == MVT::Other &&
4766 "Invalid chain type");
4768 return getStore(Chain, dl, Val, Ptr, MMO);
4770 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4771 "Should only be a truncating store, not extending!");
4772 assert(VT.isInteger() == SVT.isInteger() &&
4773 "Can't do FP-INT conversion!");
4774 assert(VT.isVector() == SVT.isVector() &&
4775 "Cannot use trunc store to convert to or from a vector!");
4776 assert((!VT.isVector() ||
4777 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4778 "Cannot use trunc store to change the number of vector elements!");
4780 SDVTList VTs = getVTList(MVT::Other);
4781 SDValue Undef = getUNDEF(Ptr.getValueType());
4782 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4783 FoldingSetNodeID ID;
4784 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4785 ID.AddInteger(SVT.getRawBits());
4786 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4787 MMO->isNonTemporal(), MMO->isInvariant()));
4788 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4790 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4791 cast<StoreSDNode>(E)->refineAlignment(MMO);
4792 return SDValue(E, 0);
4794 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4795 dl.getDebugLoc(), VTs,
4796 ISD::UNINDEXED, true, SVT, MMO);
4797 CSEMap.InsertNode(N, IP);
4798 AllNodes.push_back(N);
4799 return SDValue(N, 0);
4803 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4804 SDValue Offset, ISD::MemIndexedMode AM) {
4805 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4806 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4807 "Store is already a indexed store!");
4808 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4809 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4810 FoldingSetNodeID ID;
4811 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4812 ID.AddInteger(ST->getMemoryVT().getRawBits());
4813 ID.AddInteger(ST->getRawSubclassData());
4814 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4816 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4817 return SDValue(E, 0);
4819 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4820 dl.getDebugLoc(), VTs, AM,
4821 ST->isTruncatingStore(),
4823 ST->getMemOperand());
4824 CSEMap.InsertNode(N, IP);
4825 AllNodes.push_back(N);
4826 return SDValue(N, 0);
4829 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4830 SDValue Chain, SDValue Ptr,
4833 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4834 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4837 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4838 const SDUse *Ops, unsigned NumOps) {
4840 case 0: return getNode(Opcode, DL, VT);
4841 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4842 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4843 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4847 // Copy from an SDUse array into an SDValue array for use with
4848 // the regular getNode logic.
4849 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4850 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4853 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4854 const SDValue *Ops, unsigned NumOps) {
4856 case 0: return getNode(Opcode, DL, VT);
4857 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4858 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4859 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4865 case ISD::SELECT_CC: {
4866 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4867 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4868 "LHS and RHS of condition must have same type!");
4869 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4870 "True and False arms of SelectCC must have same type!");
4871 assert(Ops[2].getValueType() == VT &&
4872 "select_cc node must be of same type as true and false value!");
4876 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4877 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4878 "LHS/RHS of comparison should match types!");
4885 SDVTList VTs = getVTList(VT);
4887 if (VT != MVT::Glue) {
4888 FoldingSetNodeID ID;
4889 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4892 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4893 return SDValue(E, 0);
4895 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4897 CSEMap.InsertNode(N, IP);
4899 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4903 AllNodes.push_back(N);
4907 return SDValue(N, 0);
4910 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4911 ArrayRef<EVT> ResultTys,
4912 const SDValue *Ops, unsigned NumOps) {
4913 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4917 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4918 const EVT *VTs, unsigned NumVTs,
4919 const SDValue *Ops, unsigned NumOps) {
4921 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4922 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4925 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4926 const SDValue *Ops, unsigned NumOps) {
4927 if (VTList.NumVTs == 1)
4928 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4932 // FIXME: figure out how to safely handle things like
4933 // int foo(int x) { return 1 << (x & 255); }
4934 // int bar() { return foo(256); }
4935 case ISD::SRA_PARTS:
4936 case ISD::SRL_PARTS:
4937 case ISD::SHL_PARTS:
4938 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4939 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4940 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4941 else if (N3.getOpcode() == ISD::AND)
4942 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4943 // If the and is only masking out bits that cannot effect the shift,
4944 // eliminate the and.
4945 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4946 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4947 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4953 // Memoize the node unless it returns a flag.
4955 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4956 FoldingSetNodeID ID;
4957 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4959 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4960 return SDValue(E, 0);
4963 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4964 DL.getDebugLoc(), VTList, Ops[0]);
4965 } else if (NumOps == 2) {
4966 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4967 DL.getDebugLoc(), VTList, Ops[0],
4969 } else if (NumOps == 3) {
4970 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4971 DL.getDebugLoc(), VTList, Ops[0],
4974 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4975 VTList, Ops, NumOps);
4977 CSEMap.InsertNode(N, IP);
4980 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4981 DL.getDebugLoc(), VTList, Ops[0]);
4982 } else if (NumOps == 2) {
4983 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4984 DL.getDebugLoc(), VTList, Ops[0],
4986 } else if (NumOps == 3) {
4987 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4988 DL.getDebugLoc(), VTList, Ops[0],
4991 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4992 VTList, Ops, NumOps);
4995 AllNodes.push_back(N);
4999 return SDValue(N, 0);
5002 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5003 return getNode(Opcode, DL, VTList, 0, 0);
5006 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5008 SDValue Ops[] = { N1 };
5009 return getNode(Opcode, DL, VTList, Ops, 1);
5012 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5013 SDValue N1, SDValue N2) {
5014 SDValue Ops[] = { N1, N2 };
5015 return getNode(Opcode, DL, VTList, Ops, 2);
5018 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5019 SDValue N1, SDValue N2, SDValue N3) {
5020 SDValue Ops[] = { N1, N2, N3 };
5021 return getNode(Opcode, DL, VTList, Ops, 3);
5024 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5025 SDValue N1, SDValue N2, SDValue N3,
5027 SDValue Ops[] = { N1, N2, N3, N4 };
5028 return getNode(Opcode, DL, VTList, Ops, 4);
5031 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5032 SDValue N1, SDValue N2, SDValue N3,
5033 SDValue N4, SDValue N5) {
5034 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5035 return getNode(Opcode, DL, VTList, Ops, 5);
5038 SDVTList SelectionDAG::getVTList(EVT VT) {
5039 return makeVTList(SDNode::getValueTypeList(VT), 1);
5042 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5043 FoldingSetNodeID ID;
5045 ID.AddInteger(VT1.getRawBits());
5046 ID.AddInteger(VT2.getRawBits());
5049 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5050 if (Result == NULL) {
5051 EVT *Array = Allocator.Allocate<EVT>(2);
5054 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5055 VTListMap.InsertNode(Result, IP);
5057 return Result->getSDVTList();
5060 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5061 FoldingSetNodeID ID;
5063 ID.AddInteger(VT1.getRawBits());
5064 ID.AddInteger(VT2.getRawBits());
5065 ID.AddInteger(VT3.getRawBits());
5068 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5069 if (Result == NULL) {
5070 EVT *Array = Allocator.Allocate<EVT>(3);
5074 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5075 VTListMap.InsertNode(Result, IP);
5077 return Result->getSDVTList();
5080 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5081 FoldingSetNodeID ID;
5083 ID.AddInteger(VT1.getRawBits());
5084 ID.AddInteger(VT2.getRawBits());
5085 ID.AddInteger(VT3.getRawBits());
5086 ID.AddInteger(VT4.getRawBits());
5089 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5090 if (Result == NULL) {
5091 EVT *Array = Allocator.Allocate<EVT>(4);
5096 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5097 VTListMap.InsertNode(Result, IP);
5099 return Result->getSDVTList();
5102 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5103 FoldingSetNodeID ID;
5104 ID.AddInteger(NumVTs);
5105 for (unsigned index = 0; index < NumVTs; index++) {
5106 ID.AddInteger(VTs[index].getRawBits());
5110 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5111 if (Result == NULL) {
5112 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5113 std::copy(VTs, VTs + NumVTs, Array);
5114 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5115 VTListMap.InsertNode(Result, IP);
5117 return Result->getSDVTList();
5121 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5122 /// specified operands. If the resultant node already exists in the DAG,
5123 /// this does not modify the specified node, instead it returns the node that
5124 /// already exists. If the resultant node does not exist in the DAG, the
5125 /// input node is returned. As a degenerate case, if you specify the same
5126 /// input operands as the node already has, the input node is returned.
5127 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5128 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5130 // Check to see if there is no change.
5131 if (Op == N->getOperand(0)) return N;
5133 // See if the modified node already exists.
5134 void *InsertPos = 0;
5135 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5138 // Nope it doesn't. Remove the node from its current place in the maps.
5140 if (!RemoveNodeFromCSEMaps(N))
5143 // Now we update the operands.
5144 N->OperandList[0].set(Op);
5146 // If this gets put into a CSE map, add it.
5147 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5151 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5152 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5154 // Check to see if there is no change.
5155 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5156 return N; // No operands changed, just return the input node.
5158 // See if the modified node already exists.
5159 void *InsertPos = 0;
5160 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5163 // Nope it doesn't. Remove the node from its current place in the maps.
5165 if (!RemoveNodeFromCSEMaps(N))
5168 // Now we update the operands.
5169 if (N->OperandList[0] != Op1)
5170 N->OperandList[0].set(Op1);
5171 if (N->OperandList[1] != Op2)
5172 N->OperandList[1].set(Op2);
5174 // If this gets put into a CSE map, add it.
5175 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5179 SDNode *SelectionDAG::
5180 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5181 SDValue Ops[] = { Op1, Op2, Op3 };
5182 return UpdateNodeOperands(N, Ops, 3);
5185 SDNode *SelectionDAG::
5186 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5187 SDValue Op3, SDValue Op4) {
5188 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5189 return UpdateNodeOperands(N, Ops, 4);
5192 SDNode *SelectionDAG::
5193 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5194 SDValue Op3, SDValue Op4, SDValue Op5) {
5195 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5196 return UpdateNodeOperands(N, Ops, 5);
5199 SDNode *SelectionDAG::
5200 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5201 assert(N->getNumOperands() == NumOps &&
5202 "Update with wrong number of operands");
5204 // Check to see if there is no change.
5205 bool AnyChange = false;
5206 for (unsigned i = 0; i != NumOps; ++i) {
5207 if (Ops[i] != N->getOperand(i)) {
5213 // No operands changed, just return the input node.
5214 if (!AnyChange) return N;
5216 // See if the modified node already exists.
5217 void *InsertPos = 0;
5218 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5221 // Nope it doesn't. Remove the node from its current place in the maps.
5223 if (!RemoveNodeFromCSEMaps(N))
5226 // Now we update the operands.
5227 for (unsigned i = 0; i != NumOps; ++i)
5228 if (N->OperandList[i] != Ops[i])
5229 N->OperandList[i].set(Ops[i]);
5231 // If this gets put into a CSE map, add it.
5232 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5236 /// DropOperands - Release the operands and set this node to have
5238 void SDNode::DropOperands() {
5239 // Unlike the code in MorphNodeTo that does this, we don't need to
5240 // watch for dead nodes here.
5241 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5247 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5250 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5252 SDVTList VTs = getVTList(VT);
5253 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5256 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5257 EVT VT, SDValue Op1) {
5258 SDVTList VTs = getVTList(VT);
5259 SDValue Ops[] = { Op1 };
5260 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5263 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5264 EVT VT, SDValue Op1,
5266 SDVTList VTs = getVTList(VT);
5267 SDValue Ops[] = { Op1, Op2 };
5268 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5271 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5272 EVT VT, SDValue Op1,
5273 SDValue Op2, SDValue Op3) {
5274 SDVTList VTs = getVTList(VT);
5275 SDValue Ops[] = { Op1, Op2, Op3 };
5276 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5279 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5280 EVT VT, const SDValue *Ops,
5282 SDVTList VTs = getVTList(VT);
5283 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5286 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5287 EVT VT1, EVT VT2, const SDValue *Ops,
5289 SDVTList VTs = getVTList(VT1, VT2);
5290 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5293 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5295 SDVTList VTs = getVTList(VT1, VT2);
5296 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5299 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5300 EVT VT1, EVT VT2, EVT VT3,
5301 const SDValue *Ops, unsigned NumOps) {
5302 SDVTList VTs = getVTList(VT1, VT2, VT3);
5303 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5306 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5307 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5308 const SDValue *Ops, unsigned NumOps) {
5309 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5310 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5313 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5316 SDVTList VTs = getVTList(VT1, VT2);
5317 SDValue Ops[] = { Op1 };
5318 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5321 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5323 SDValue Op1, SDValue Op2) {
5324 SDVTList VTs = getVTList(VT1, VT2);
5325 SDValue Ops[] = { Op1, Op2 };
5326 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5329 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5331 SDValue Op1, SDValue Op2,
5333 SDVTList VTs = getVTList(VT1, VT2);
5334 SDValue Ops[] = { Op1, Op2, Op3 };
5335 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5338 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5339 EVT VT1, EVT VT2, EVT VT3,
5340 SDValue Op1, SDValue Op2,
5342 SDVTList VTs = getVTList(VT1, VT2, VT3);
5343 SDValue Ops[] = { Op1, Op2, Op3 };
5344 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5347 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5348 SDVTList VTs, const SDValue *Ops,
5350 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5351 // Reset the NodeID to -1.
5356 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5357 /// the line number information on the merged node since it is not possible to
5358 /// preserve the information that operation is associated with multiple lines.
5359 /// This will make the debugger working better at -O0, were there is a higher
5360 /// probability having other instructions associated with that line.
5362 /// For IROrder, we keep the smaller of the two
5363 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5364 DebugLoc NLoc = N->getDebugLoc();
5365 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5366 (OLoc.getDebugLoc() != NLoc)) {
5367 N->setDebugLoc(DebugLoc());
5369 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5370 N->setIROrder(Order);
5374 /// MorphNodeTo - This *mutates* the specified node to have the specified
5375 /// return type, opcode, and operands.
5377 /// Note that MorphNodeTo returns the resultant node. If there is already a
5378 /// node of the specified opcode and operands, it returns that node instead of
5379 /// the current one. Note that the SDLoc need not be the same.
5381 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5382 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5383 /// node, and because it doesn't require CSE recalculation for any of
5384 /// the node's users.
5386 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5387 SDVTList VTs, const SDValue *Ops,
5389 // If an identical node already exists, use it.
5391 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5392 FoldingSetNodeID ID;
5393 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5394 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5395 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5398 if (!RemoveNodeFromCSEMaps(N))
5401 // Start the morphing.
5403 N->ValueList = VTs.VTs;
5404 N->NumValues = VTs.NumVTs;
5406 // Clear the operands list, updating used nodes to remove this from their
5407 // use list. Keep track of any operands that become dead as a result.
5408 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5409 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5411 SDNode *Used = Use.getNode();
5413 if (Used->use_empty())
5414 DeadNodeSet.insert(Used);
5417 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5418 // Initialize the memory references information.
5419 MN->setMemRefs(0, 0);
5420 // If NumOps is larger than the # of operands we can have in a
5421 // MachineSDNode, reallocate the operand list.
5422 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5423 if (MN->OperandsNeedDelete)
5424 delete[] MN->OperandList;
5425 if (NumOps > array_lengthof(MN->LocalOperands))
5426 // We're creating a final node that will live unmorphed for the
5427 // remainder of the current SelectionDAG iteration, so we can allocate
5428 // the operands directly out of a pool with no recycling metadata.
5429 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5432 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5433 MN->OperandsNeedDelete = false;
5435 MN->InitOperands(MN->OperandList, Ops, NumOps);
5437 // If NumOps is larger than the # of operands we currently have, reallocate
5438 // the operand list.
5439 if (NumOps > N->NumOperands) {
5440 if (N->OperandsNeedDelete)
5441 delete[] N->OperandList;
5442 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5443 N->OperandsNeedDelete = true;
5445 N->InitOperands(N->OperandList, Ops, NumOps);
5448 // Delete any nodes that are still dead after adding the uses for the
5450 if (!DeadNodeSet.empty()) {
5451 SmallVector<SDNode *, 16> DeadNodes;
5452 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5453 E = DeadNodeSet.end(); I != E; ++I)
5454 if ((*I)->use_empty())
5455 DeadNodes.push_back(*I);
5456 RemoveDeadNodes(DeadNodes);
5460 CSEMap.InsertNode(N, IP); // Memoize the new node.
5465 /// getMachineNode - These are used for target selectors to create a new node
5466 /// with specified return type(s), MachineInstr opcode, and operands.
5468 /// Note that getMachineNode returns the resultant node. If there is already a
5469 /// node of the specified opcode and operands, it returns that node instead of
5470 /// the current one.
5472 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5473 SDVTList VTs = getVTList(VT);
5474 return getMachineNode(Opcode, dl, VTs, None);
5478 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5479 SDVTList VTs = getVTList(VT);
5480 SDValue Ops[] = { Op1 };
5481 return getMachineNode(Opcode, dl, VTs, Ops);
5485 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5486 SDValue Op1, SDValue Op2) {
5487 SDVTList VTs = getVTList(VT);
5488 SDValue Ops[] = { Op1, Op2 };
5489 return getMachineNode(Opcode, dl, VTs, Ops);
5493 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5494 SDValue Op1, SDValue Op2, SDValue Op3) {
5495 SDVTList VTs = getVTList(VT);
5496 SDValue Ops[] = { Op1, Op2, Op3 };
5497 return getMachineNode(Opcode, dl, VTs, Ops);
5501 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5502 ArrayRef<SDValue> Ops) {
5503 SDVTList VTs = getVTList(VT);
5504 return getMachineNode(Opcode, dl, VTs, Ops);
5508 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5509 SDVTList VTs = getVTList(VT1, VT2);
5510 return getMachineNode(Opcode, dl, VTs, None);
5514 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5515 EVT VT1, EVT VT2, SDValue Op1) {
5516 SDVTList VTs = getVTList(VT1, VT2);
5517 SDValue Ops[] = { Op1 };
5518 return getMachineNode(Opcode, dl, VTs, Ops);
5522 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5523 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5524 SDVTList VTs = getVTList(VT1, VT2);
5525 SDValue Ops[] = { Op1, Op2 };
5526 return getMachineNode(Opcode, dl, VTs, Ops);
5530 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5531 EVT VT1, EVT VT2, SDValue Op1,
5532 SDValue Op2, SDValue Op3) {
5533 SDVTList VTs = getVTList(VT1, VT2);
5534 SDValue Ops[] = { Op1, Op2, Op3 };
5535 return getMachineNode(Opcode, dl, VTs, Ops);
5539 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5541 ArrayRef<SDValue> Ops) {
5542 SDVTList VTs = getVTList(VT1, VT2);
5543 return getMachineNode(Opcode, dl, VTs, Ops);
5547 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5548 EVT VT1, EVT VT2, EVT VT3,
5549 SDValue Op1, SDValue Op2) {
5550 SDVTList VTs = getVTList(VT1, VT2, VT3);
5551 SDValue Ops[] = { Op1, Op2 };
5552 return getMachineNode(Opcode, dl, VTs, Ops);
5556 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5557 EVT VT1, EVT VT2, EVT VT3,
5558 SDValue Op1, SDValue Op2, SDValue Op3) {
5559 SDVTList VTs = getVTList(VT1, VT2, VT3);
5560 SDValue Ops[] = { Op1, Op2, Op3 };
5561 return getMachineNode(Opcode, dl, VTs, Ops);
5565 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5566 EVT VT1, EVT VT2, EVT VT3,
5567 ArrayRef<SDValue> Ops) {
5568 SDVTList VTs = getVTList(VT1, VT2, VT3);
5569 return getMachineNode(Opcode, dl, VTs, Ops);
5573 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5574 EVT VT2, EVT VT3, EVT VT4,
5575 ArrayRef<SDValue> Ops) {
5576 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5577 return getMachineNode(Opcode, dl, VTs, Ops);
5581 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5582 ArrayRef<EVT> ResultTys,
5583 ArrayRef<SDValue> Ops) {
5584 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5585 return getMachineNode(Opcode, dl, VTs, Ops);
5589 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5590 ArrayRef<SDValue> OpsArray) {
5591 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5594 const SDValue *Ops = OpsArray.data();
5595 unsigned NumOps = OpsArray.size();
5598 FoldingSetNodeID ID;
5599 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5601 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5602 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5606 // Allocate a new MachineSDNode.
5607 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5608 DL.getDebugLoc(), VTs);
5610 // Initialize the operands list.
5611 if (NumOps > array_lengthof(N->LocalOperands))
5612 // We're creating a final node that will live unmorphed for the
5613 // remainder of the current SelectionDAG iteration, so we can allocate
5614 // the operands directly out of a pool with no recycling metadata.
5615 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5618 N->InitOperands(N->LocalOperands, Ops, NumOps);
5619 N->OperandsNeedDelete = false;
5622 CSEMap.InsertNode(N, IP);
5624 AllNodes.push_back(N);
5626 VerifyMachineNode(N);
5631 /// getTargetExtractSubreg - A convenience function for creating
5632 /// TargetOpcode::EXTRACT_SUBREG nodes.
5634 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5636 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5637 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5638 VT, Operand, SRIdxVal);
5639 return SDValue(Subreg, 0);
5642 /// getTargetInsertSubreg - A convenience function for creating
5643 /// TargetOpcode::INSERT_SUBREG nodes.
5645 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5646 SDValue Operand, SDValue Subreg) {
5647 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5648 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5649 VT, Operand, Subreg, SRIdxVal);
5650 return SDValue(Result, 0);
5653 /// getNodeIfExists - Get the specified node if it's already available, or
5654 /// else return NULL.
5655 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5656 const SDValue *Ops, unsigned NumOps) {
5657 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5658 FoldingSetNodeID ID;
5659 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5661 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5667 /// getDbgValue - Creates a SDDbgValue node.
5670 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5671 DebugLoc DL, unsigned O) {
5672 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5676 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5677 DebugLoc DL, unsigned O) {
5678 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5682 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5683 DebugLoc DL, unsigned O) {
5684 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5689 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5690 /// pointed to by a use iterator is deleted, increment the use iterator
5691 /// so that it doesn't dangle.
5693 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5694 SDNode::use_iterator &UI;
5695 SDNode::use_iterator &UE;
5697 void NodeDeleted(SDNode *N, SDNode *E) override {
5698 // Increment the iterator as needed.
5699 while (UI != UE && N == *UI)
5704 RAUWUpdateListener(SelectionDAG &d,
5705 SDNode::use_iterator &ui,
5706 SDNode::use_iterator &ue)
5707 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5712 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5713 /// This can cause recursive merging of nodes in the DAG.
5715 /// This version assumes From has a single result value.
5717 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5718 SDNode *From = FromN.getNode();
5719 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5720 "Cannot replace with this method!");
5721 assert(From != To.getNode() && "Cannot replace uses of with self");
5723 // Iterate over all the existing uses of From. New uses will be added
5724 // to the beginning of the use list, which we avoid visiting.
5725 // This specifically avoids visiting uses of From that arise while the
5726 // replacement is happening, because any such uses would be the result
5727 // of CSE: If an existing node looks like From after one of its operands
5728 // is replaced by To, we don't want to replace of all its users with To
5729 // too. See PR3018 for more info.
5730 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5731 RAUWUpdateListener Listener(*this, UI, UE);
5735 // This node is about to morph, remove its old self from the CSE maps.
5736 RemoveNodeFromCSEMaps(User);
5738 // A user can appear in a use list multiple times, and when this
5739 // happens the uses are usually next to each other in the list.
5740 // To help reduce the number of CSE recomputations, process all
5741 // the uses of this user that we can find this way.
5743 SDUse &Use = UI.getUse();
5746 } while (UI != UE && *UI == User);
5748 // Now that we have modified User, add it back to the CSE maps. If it
5749 // already exists there, recursively merge the results together.
5750 AddModifiedNodeToCSEMaps(User);
5753 // If we just RAUW'd the root, take note.
5754 if (FromN == getRoot())
5758 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5759 /// This can cause recursive merging of nodes in the DAG.
5761 /// This version assumes that for each value of From, there is a
5762 /// corresponding value in To in the same position with the same type.
5764 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5766 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5767 assert((!From->hasAnyUseOfValue(i) ||
5768 From->getValueType(i) == To->getValueType(i)) &&
5769 "Cannot use this version of ReplaceAllUsesWith!");
5772 // Handle the trivial case.
5776 // Iterate over just the existing users of From. See the comments in
5777 // the ReplaceAllUsesWith above.
5778 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5779 RAUWUpdateListener Listener(*this, UI, UE);
5783 // This node is about to morph, remove its old self from the CSE maps.
5784 RemoveNodeFromCSEMaps(User);
5786 // A user can appear in a use list multiple times, and when this
5787 // happens the uses are usually next to each other in the list.
5788 // To help reduce the number of CSE recomputations, process all
5789 // the uses of this user that we can find this way.
5791 SDUse &Use = UI.getUse();
5794 } while (UI != UE && *UI == User);
5796 // Now that we have modified User, add it back to the CSE maps. If it
5797 // already exists there, recursively merge the results together.
5798 AddModifiedNodeToCSEMaps(User);
5801 // If we just RAUW'd the root, take note.
5802 if (From == getRoot().getNode())
5803 setRoot(SDValue(To, getRoot().getResNo()));
5806 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5807 /// This can cause recursive merging of nodes in the DAG.
5809 /// This version can replace From with any result values. To must match the
5810 /// number and types of values returned by From.
5811 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5812 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5813 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5815 // Iterate over just the existing users of From. See the comments in
5816 // the ReplaceAllUsesWith above.
5817 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5818 RAUWUpdateListener Listener(*this, UI, UE);
5822 // This node is about to morph, remove its old self from the CSE maps.
5823 RemoveNodeFromCSEMaps(User);
5825 // A user can appear in a use list multiple times, and when this
5826 // happens the uses are usually next to each other in the list.
5827 // To help reduce the number of CSE recomputations, process all
5828 // the uses of this user that we can find this way.
5830 SDUse &Use = UI.getUse();
5831 const SDValue &ToOp = To[Use.getResNo()];
5834 } while (UI != UE && *UI == User);
5836 // Now that we have modified User, add it back to the CSE maps. If it
5837 // already exists there, recursively merge the results together.
5838 AddModifiedNodeToCSEMaps(User);
5841 // If we just RAUW'd the root, take note.
5842 if (From == getRoot().getNode())
5843 setRoot(SDValue(To[getRoot().getResNo()]));
5846 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5847 /// uses of other values produced by From.getNode() alone. The Deleted
5848 /// vector is handled the same way as for ReplaceAllUsesWith.
5849 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5850 // Handle the really simple, really trivial case efficiently.
5851 if (From == To) return;
5853 // Handle the simple, trivial, case efficiently.
5854 if (From.getNode()->getNumValues() == 1) {
5855 ReplaceAllUsesWith(From, To);
5859 // Iterate over just the existing users of From. See the comments in
5860 // the ReplaceAllUsesWith above.
5861 SDNode::use_iterator UI = From.getNode()->use_begin(),
5862 UE = From.getNode()->use_end();
5863 RAUWUpdateListener Listener(*this, UI, UE);
5866 bool UserRemovedFromCSEMaps = false;
5868 // A user can appear in a use list multiple times, and when this
5869 // happens the uses are usually next to each other in the list.
5870 // To help reduce the number of CSE recomputations, process all
5871 // the uses of this user that we can find this way.
5873 SDUse &Use = UI.getUse();
5875 // Skip uses of different values from the same node.
5876 if (Use.getResNo() != From.getResNo()) {
5881 // If this node hasn't been modified yet, it's still in the CSE maps,
5882 // so remove its old self from the CSE maps.
5883 if (!UserRemovedFromCSEMaps) {
5884 RemoveNodeFromCSEMaps(User);
5885 UserRemovedFromCSEMaps = true;
5890 } while (UI != UE && *UI == User);
5892 // We are iterating over all uses of the From node, so if a use
5893 // doesn't use the specific value, no changes are made.
5894 if (!UserRemovedFromCSEMaps)
5897 // Now that we have modified User, add it back to the CSE maps. If it
5898 // already exists there, recursively merge the results together.
5899 AddModifiedNodeToCSEMaps(User);
5902 // If we just RAUW'd the root, take note.
5903 if (From == getRoot())
5908 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5909 /// to record information about a use.
5916 /// operator< - Sort Memos by User.
5917 bool operator<(const UseMemo &L, const UseMemo &R) {
5918 return (intptr_t)L.User < (intptr_t)R.User;
5922 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5923 /// uses of other values produced by From.getNode() alone. The same value
5924 /// may appear in both the From and To list. The Deleted vector is
5925 /// handled the same way as for ReplaceAllUsesWith.
5926 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5929 // Handle the simple, trivial case efficiently.
5931 return ReplaceAllUsesOfValueWith(*From, *To);
5933 // Read up all the uses and make records of them. This helps
5934 // processing new uses that are introduced during the
5935 // replacement process.
5936 SmallVector<UseMemo, 4> Uses;
5937 for (unsigned i = 0; i != Num; ++i) {
5938 unsigned FromResNo = From[i].getResNo();
5939 SDNode *FromNode = From[i].getNode();
5940 for (SDNode::use_iterator UI = FromNode->use_begin(),
5941 E = FromNode->use_end(); UI != E; ++UI) {
5942 SDUse &Use = UI.getUse();
5943 if (Use.getResNo() == FromResNo) {
5944 UseMemo Memo = { *UI, i, &Use };
5945 Uses.push_back(Memo);
5950 // Sort the uses, so that all the uses from a given User are together.
5951 std::sort(Uses.begin(), Uses.end());
5953 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5954 UseIndex != UseIndexEnd; ) {
5955 // We know that this user uses some value of From. If it is the right
5956 // value, update it.
5957 SDNode *User = Uses[UseIndex].User;
5959 // This node is about to morph, remove its old self from the CSE maps.
5960 RemoveNodeFromCSEMaps(User);
5962 // The Uses array is sorted, so all the uses for a given User
5963 // are next to each other in the list.
5964 // To help reduce the number of CSE recomputations, process all
5965 // the uses of this user that we can find this way.
5967 unsigned i = Uses[UseIndex].Index;
5968 SDUse &Use = *Uses[UseIndex].Use;
5972 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5974 // Now that we have modified User, add it back to the CSE maps. If it
5975 // already exists there, recursively merge the results together.
5976 AddModifiedNodeToCSEMaps(User);
5980 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5981 /// based on their topological order. It returns the maximum id and a vector
5982 /// of the SDNodes* in assigned order by reference.
5983 unsigned SelectionDAG::AssignTopologicalOrder() {
5985 unsigned DAGSize = 0;
5987 // SortedPos tracks the progress of the algorithm. Nodes before it are
5988 // sorted, nodes after it are unsorted. When the algorithm completes
5989 // it is at the end of the list.
5990 allnodes_iterator SortedPos = allnodes_begin();
5992 // Visit all the nodes. Move nodes with no operands to the front of
5993 // the list immediately. Annotate nodes that do have operands with their
5994 // operand count. Before we do this, the Node Id fields of the nodes
5995 // may contain arbitrary values. After, the Node Id fields for nodes
5996 // before SortedPos will contain the topological sort index, and the
5997 // Node Id fields for nodes At SortedPos and after will contain the
5998 // count of outstanding operands.
5999 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6002 unsigned Degree = N->getNumOperands();
6004 // A node with no uses, add it to the result array immediately.
6005 N->setNodeId(DAGSize++);
6006 allnodes_iterator Q = N;
6008 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6009 assert(SortedPos != AllNodes.end() && "Overran node list");
6012 // Temporarily use the Node Id as scratch space for the degree count.
6013 N->setNodeId(Degree);
6017 // Visit all the nodes. As we iterate, move nodes into sorted order,
6018 // such that by the time the end is reached all nodes will be sorted.
6019 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6022 // N is in sorted position, so all its uses have one less operand
6023 // that needs to be sorted.
6024 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6027 unsigned Degree = P->getNodeId();
6028 assert(Degree != 0 && "Invalid node degree");
6031 // All of P's operands are sorted, so P may sorted now.
6032 P->setNodeId(DAGSize++);
6034 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6035 assert(SortedPos != AllNodes.end() && "Overran node list");
6038 // Update P's outstanding operand count.
6039 P->setNodeId(Degree);
6042 if (I == SortedPos) {
6045 dbgs() << "Overran sorted position:\n";
6048 llvm_unreachable(0);
6052 assert(SortedPos == AllNodes.end() &&
6053 "Topological sort incomplete!");
6054 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6055 "First node in topological sort is not the entry token!");
6056 assert(AllNodes.front().getNodeId() == 0 &&
6057 "First node in topological sort has non-zero id!");
6058 assert(AllNodes.front().getNumOperands() == 0 &&
6059 "First node in topological sort has operands!");
6060 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6061 "Last node in topologic sort has unexpected id!");
6062 assert(AllNodes.back().use_empty() &&
6063 "Last node in topologic sort has users!");
6064 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6068 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6069 /// value is produced by SD.
6070 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6071 DbgInfo->add(DB, SD, isParameter);
6073 SD->setHasDebugValue(true);
6076 /// TransferDbgValues - Transfer SDDbgValues.
6077 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6078 if (From == To || !From.getNode()->getHasDebugValue())
6080 SDNode *FromNode = From.getNode();
6081 SDNode *ToNode = To.getNode();
6082 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6083 SmallVector<SDDbgValue *, 2> ClonedDVs;
6084 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6086 SDDbgValue *Dbg = *I;
6087 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6088 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6089 Dbg->getOffset(), Dbg->getDebugLoc(),
6091 ClonedDVs.push_back(Clone);
6094 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6095 E = ClonedDVs.end(); I != E; ++I)
6096 AddDbgValue(*I, ToNode, false);
6099 //===----------------------------------------------------------------------===//
6101 //===----------------------------------------------------------------------===//
6103 HandleSDNode::~HandleSDNode() {
6107 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6108 DebugLoc DL, const GlobalValue *GA,
6109 EVT VT, int64_t o, unsigned char TF)
6110 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6114 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6115 SDValue X, unsigned SrcAS,
6117 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6118 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6120 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6121 EVT memvt, MachineMemOperand *mmo)
6122 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6123 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6124 MMO->isNonTemporal(), MMO->isInvariant());
6125 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6126 assert(isNonTemporal() == MMO->isNonTemporal() &&
6127 "Non-temporal encoding error!");
6128 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6131 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6132 const SDValue *Ops, unsigned NumOps, EVT memvt,
6133 MachineMemOperand *mmo)
6134 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6135 MemoryVT(memvt), MMO(mmo) {
6136 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6137 MMO->isNonTemporal(), MMO->isInvariant());
6138 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6139 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6142 /// Profile - Gather unique data for the node.
6144 void SDNode::Profile(FoldingSetNodeID &ID) const {
6145 AddNodeIDNode(ID, this);
6150 std::vector<EVT> VTs;
6153 VTs.reserve(MVT::LAST_VALUETYPE);
6154 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6155 VTs.push_back(MVT((MVT::SimpleValueType)i));
6160 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6161 static ManagedStatic<EVTArray> SimpleVTArray;
6162 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6164 /// getValueTypeList - Return a pointer to the specified value type.
6166 const EVT *SDNode::getValueTypeList(EVT VT) {
6167 if (VT.isExtended()) {
6168 sys::SmartScopedLock<true> Lock(*VTMutex);
6169 return &(*EVTs->insert(VT).first);
6171 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6172 "Value type out of range!");
6173 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6177 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6178 /// indicated value. This method ignores uses of other values defined by this
6180 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6181 assert(Value < getNumValues() && "Bad value!");
6183 // TODO: Only iterate over uses of a given value of the node
6184 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6185 if (UI.getUse().getResNo() == Value) {
6192 // Found exactly the right number of uses?
6197 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6198 /// value. This method ignores uses of other values defined by this operation.
6199 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6200 assert(Value < getNumValues() && "Bad value!");
6202 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6203 if (UI.getUse().getResNo() == Value)
6210 /// isOnlyUserOf - Return true if this node is the only use of N.
6212 bool SDNode::isOnlyUserOf(SDNode *N) const {
6214 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6225 /// isOperand - Return true if this node is an operand of N.
6227 bool SDValue::isOperandOf(SDNode *N) const {
6228 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6229 if (*this == N->getOperand(i))
6234 bool SDNode::isOperandOf(SDNode *N) const {
6235 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6236 if (this == N->OperandList[i].getNode())
6241 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6242 /// be a chain) reaches the specified operand without crossing any
6243 /// side-effecting instructions on any chain path. In practice, this looks
6244 /// through token factors and non-volatile loads. In order to remain efficient,
6245 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6246 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6247 unsigned Depth) const {
6248 if (*this == Dest) return true;
6250 // Don't search too deeply, we just want to be able to see through
6251 // TokenFactor's etc.
6252 if (Depth == 0) return false;
6254 // If this is a token factor, all inputs to the TF happen in parallel. If any
6255 // of the operands of the TF does not reach dest, then we cannot do the xform.
6256 if (getOpcode() == ISD::TokenFactor) {
6257 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6258 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6263 // Loads don't have side effects, look through them.
6264 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6265 if (!Ld->isVolatile())
6266 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6271 /// hasPredecessor - Return true if N is a predecessor of this node.
6272 /// N is either an operand of this node, or can be reached by recursively
6273 /// traversing up the operands.
6274 /// NOTE: This is an expensive method. Use it carefully.
6275 bool SDNode::hasPredecessor(const SDNode *N) const {
6276 SmallPtrSet<const SDNode *, 32> Visited;
6277 SmallVector<const SDNode *, 16> Worklist;
6278 return hasPredecessorHelper(N, Visited, Worklist);
6282 SDNode::hasPredecessorHelper(const SDNode *N,
6283 SmallPtrSet<const SDNode *, 32> &Visited,
6284 SmallVectorImpl<const SDNode *> &Worklist) const {
6285 if (Visited.empty()) {
6286 Worklist.push_back(this);
6288 // Take a look in the visited set. If we've already encountered this node
6289 // we needn't search further.
6290 if (Visited.count(N))
6294 // Haven't visited N yet. Continue the search.
6295 while (!Worklist.empty()) {
6296 const SDNode *M = Worklist.pop_back_val();
6297 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6298 SDNode *Op = M->getOperand(i).getNode();
6299 if (Visited.insert(Op))
6300 Worklist.push_back(Op);
6309 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6310 assert(Num < NumOperands && "Invalid child # of SDNode!");
6311 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6314 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6315 assert(N->getNumValues() == 1 &&
6316 "Can't unroll a vector with multiple results!");
6318 EVT VT = N->getValueType(0);
6319 unsigned NE = VT.getVectorNumElements();
6320 EVT EltVT = VT.getVectorElementType();
6323 SmallVector<SDValue, 8> Scalars;
6324 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6326 // If ResNE is 0, fully unroll the vector op.
6329 else if (NE > ResNE)
6333 for (i= 0; i != NE; ++i) {
6334 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6335 SDValue Operand = N->getOperand(j);
6336 EVT OperandVT = Operand.getValueType();
6337 if (OperandVT.isVector()) {
6338 // A vector operand; extract a single element.
6339 const TargetLowering *TLI = TM.getTargetLowering();
6340 EVT OperandEltVT = OperandVT.getVectorElementType();
6341 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6344 getConstant(i, TLI->getVectorIdxTy()));
6346 // A scalar operand; just use it as is.
6347 Operands[j] = Operand;
6351 switch (N->getOpcode()) {
6353 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6354 &Operands[0], Operands.size()));
6357 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6358 &Operands[0], Operands.size()));
6365 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6366 getShiftAmountOperand(Operands[0].getValueType(),
6369 case ISD::SIGN_EXTEND_INREG:
6370 case ISD::FP_ROUND_INREG: {
6371 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6372 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6374 getValueType(ExtVT)));
6379 for (; i < ResNE; ++i)
6380 Scalars.push_back(getUNDEF(EltVT));
6382 return getNode(ISD::BUILD_VECTOR, dl,
6383 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6384 &Scalars[0], Scalars.size());
6388 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6389 /// location that is 'Dist' units away from the location that the 'Base' load
6390 /// is loading from.
6391 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6392 unsigned Bytes, int Dist) const {
6393 if (LD->getChain() != Base->getChain())
6395 EVT VT = LD->getValueType(0);
6396 if (VT.getSizeInBits() / 8 != Bytes)
6399 SDValue Loc = LD->getOperand(1);
6400 SDValue BaseLoc = Base->getOperand(1);
6401 if (Loc.getOpcode() == ISD::FrameIndex) {
6402 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6404 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6405 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6406 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6407 int FS = MFI->getObjectSize(FI);
6408 int BFS = MFI->getObjectSize(BFI);
6409 if (FS != BFS || FS != (int)Bytes) return false;
6410 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6414 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6415 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6418 const GlobalValue *GV1 = NULL;
6419 const GlobalValue *GV2 = NULL;
6420 int64_t Offset1 = 0;
6421 int64_t Offset2 = 0;
6422 const TargetLowering *TLI = TM.getTargetLowering();
6423 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6424 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6425 if (isGA1 && isGA2 && GV1 == GV2)
6426 return Offset1 == (Offset2 + Dist*Bytes);
6431 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6432 /// it cannot be inferred.
6433 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6434 // If this is a GlobalAddress + cst, return the alignment.
6435 const GlobalValue *GV;
6436 int64_t GVOffset = 0;
6437 const TargetLowering *TLI = TM.getTargetLowering();
6438 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6439 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6440 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6441 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6442 TLI->getDataLayout());
6443 unsigned AlignBits = KnownZero.countTrailingOnes();
6444 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6446 return MinAlign(Align, GVOffset);
6449 // If this is a direct reference to a stack slot, use information about the
6450 // stack slot's alignment.
6451 int FrameIdx = 1 << 31;
6452 int64_t FrameOffset = 0;
6453 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6454 FrameIdx = FI->getIndex();
6455 } else if (isBaseWithConstantOffset(Ptr) &&
6456 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6458 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6459 FrameOffset = Ptr.getConstantOperandVal(1);
6462 if (FrameIdx != (1 << 31)) {
6463 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6464 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6472 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6473 /// which is split (or expanded) into two not necessarily identical pieces.
6474 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6475 // Currently all types are split in half.
6477 if (!VT.isVector()) {
6478 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6480 unsigned NumElements = VT.getVectorNumElements();
6481 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6482 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6485 return std::make_pair(LoVT, HiVT);
6488 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6490 std::pair<SDValue, SDValue>
6491 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6493 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6494 N.getValueType().getVectorNumElements() &&
6495 "More vector elements requested than available!");
6497 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6498 getConstant(0, TLI->getVectorIdxTy()));
6499 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6500 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6501 return std::make_pair(Lo, Hi);
6504 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6505 unsigned GlobalAddressSDNode::getAddressSpace() const {
6506 return getGlobal()->getType()->getAddressSpace();
6510 Type *ConstantPoolSDNode::getType() const {
6511 if (isMachineConstantPoolEntry())
6512 return Val.MachineCPVal->getType();
6513 return Val.ConstVal->getType();
6516 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6518 unsigned &SplatBitSize,
6520 unsigned MinSplatBits,
6521 bool isBigEndian) const {
6522 EVT VT = getValueType(0);
6523 assert(VT.isVector() && "Expected a vector type");
6524 unsigned sz = VT.getSizeInBits();
6525 if (MinSplatBits > sz)
6528 SplatValue = APInt(sz, 0);
6529 SplatUndef = APInt(sz, 0);
6531 // Get the bits. Bits with undefined values (when the corresponding element
6532 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6533 // in SplatValue. If any of the values are not constant, give up and return
6535 unsigned int nOps = getNumOperands();
6536 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6537 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6539 for (unsigned j = 0; j < nOps; ++j) {
6540 unsigned i = isBigEndian ? nOps-1-j : j;
6541 SDValue OpVal = getOperand(i);
6542 unsigned BitPos = j * EltBitSize;
6544 if (OpVal.getOpcode() == ISD::UNDEF)
6545 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6546 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6547 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6548 zextOrTrunc(sz) << BitPos;
6549 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6550 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6555 // The build_vector is all constants or undefs. Find the smallest element
6556 // size that splats the vector.
6558 HasAnyUndefs = (SplatUndef != 0);
6561 unsigned HalfSize = sz / 2;
6562 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6563 APInt LowValue = SplatValue.trunc(HalfSize);
6564 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6565 APInt LowUndef = SplatUndef.trunc(HalfSize);
6567 // If the two halves do not match (ignoring undef bits), stop here.
6568 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6569 MinSplatBits > HalfSize)
6572 SplatValue = HighValue | LowValue;
6573 SplatUndef = HighUndef & LowUndef;
6582 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6583 SDValue Op0 = getOperand(0);
6584 if (Op0.getOpcode() != ISD::Constant)
6587 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6588 if (getOperand(i) != Op0)
6591 return cast<ConstantSDNode>(Op0);
6594 bool BuildVectorSDNode::isConstant() const {
6595 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6596 unsigned Opc = getOperand(i).getOpcode();
6597 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6603 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6604 // Find the first non-undef value in the shuffle mask.
6606 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6609 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6611 // Make sure all remaining elements are either undef or the same as the first
6613 for (int Idx = Mask[i]; i != e; ++i)
6614 if (Mask[i] >= 0 && Mask[i] != Idx)
6620 static void checkForCyclesHelper(const SDNode *N,
6621 SmallPtrSet<const SDNode*, 32> &Visited,
6622 SmallPtrSet<const SDNode*, 32> &Checked) {
6623 // If this node has already been checked, don't check it again.
6624 if (Checked.count(N))
6627 // If a node has already been visited on this depth-first walk, reject it as
6629 if (!Visited.insert(N)) {
6630 dbgs() << "Offending node:\n";
6632 errs() << "Detected cycle in SelectionDAG\n";
6636 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6637 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6644 void llvm::checkForCycles(const llvm::SDNode *N) {
6646 assert(N && "Checking nonexistent SDNode");
6647 SmallPtrSet<const SDNode*, 32> visited;
6648 SmallPtrSet<const SDNode*, 32> checked;
6649 checkForCyclesHelper(N, visited, checked);
6653 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6654 checkForCycles(DAG->getRoot().getNode());