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/DebugInfo.h"
27 #include "llvm/IR/CallingConv.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.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 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
235 /// when given the operation for (X op Y).
236 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
237 // To perform this operation, we just need to swap the L and G bits of the
239 unsigned OldL = (Operation >> 2) & 1;
240 unsigned OldG = (Operation >> 1) & 1;
241 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
242 (OldL << 1) | // New G bit
243 (OldG << 2)); // New L bit.
246 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
247 /// 'op' is a valid SetCC operation.
248 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
249 unsigned Operation = Op;
251 Operation ^= 7; // Flip L, G, E bits, but not U.
253 Operation ^= 15; // Flip all of the condition bits.
255 if (Operation > ISD::SETTRUE2)
256 Operation &= ~8; // Don't let N and U bits get set.
258 return ISD::CondCode(Operation);
262 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
263 /// signed operation and 2 if the result is an unsigned comparison. Return zero
264 /// if the operation does not depend on the sign of the input (setne and seteq).
265 static int isSignedOp(ISD::CondCode Opcode) {
267 default: llvm_unreachable("Illegal integer setcc operation!");
269 case ISD::SETNE: return 0;
273 case ISD::SETGE: return 1;
277 case ISD::SETUGE: return 2;
281 /// getSetCCOrOperation - Return the result of a logical OR between different
282 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
283 /// returns SETCC_INVALID if it is not possible to represent the resultant
285 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
287 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
288 // Cannot fold a signed integer setcc with an unsigned integer setcc.
289 return ISD::SETCC_INVALID;
291 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
293 // If the N and U bits get set then the resultant comparison DOES suddenly
294 // care about orderedness, and is true when ordered.
295 if (Op > ISD::SETTRUE2)
296 Op &= ~16; // Clear the U bit if the N bit is set.
298 // Canonicalize illegal integer setcc's.
299 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
302 return ISD::CondCode(Op);
305 /// getSetCCAndOperation - Return the result of a logical AND between different
306 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
307 /// function returns zero if it is not possible to represent the resultant
309 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
311 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
312 // Cannot fold a signed setcc with an unsigned setcc.
313 return ISD::SETCC_INVALID;
315 // Combine all of the condition bits.
316 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
318 // Canonicalize illegal integer setcc's.
322 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
323 case ISD::SETOEQ: // SETEQ & SETU[LG]E
324 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
325 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
326 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
333 //===----------------------------------------------------------------------===//
334 // SDNode Profile Support
335 //===----------------------------------------------------------------------===//
337 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
339 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
343 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
344 /// solely with their pointer.
345 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
346 ID.AddPointer(VTList.VTs);
349 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
351 static void AddNodeIDOperands(FoldingSetNodeID &ID,
352 const SDValue *Ops, unsigned NumOps) {
353 for (; NumOps; --NumOps, ++Ops) {
354 ID.AddPointer(Ops->getNode());
355 ID.AddInteger(Ops->getResNo());
359 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
361 static void AddNodeIDOperands(FoldingSetNodeID &ID,
362 const SDUse *Ops, unsigned NumOps) {
363 for (; NumOps; --NumOps, ++Ops) {
364 ID.AddPointer(Ops->getNode());
365 ID.AddInteger(Ops->getResNo());
369 static void AddNodeIDNode(FoldingSetNodeID &ID,
370 unsigned short OpC, SDVTList VTList,
371 const SDValue *OpList, unsigned N) {
372 AddNodeIDOpcode(ID, OpC);
373 AddNodeIDValueTypes(ID, VTList);
374 AddNodeIDOperands(ID, OpList, N);
377 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
379 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
380 switch (N->getOpcode()) {
381 case ISD::TargetExternalSymbol:
382 case ISD::ExternalSymbol:
383 llvm_unreachable("Should only be used on nodes with operands");
384 default: break; // Normal nodes don't need extra info.
385 case ISD::TargetConstant:
386 case ISD::Constant: {
387 const ConstantSDNode *C = cast<ConstantSDNode>(N);
388 ID.AddPointer(C->getConstantIntValue());
389 ID.AddBoolean(C->isOpaque());
392 case ISD::TargetConstantFP:
393 case ISD::ConstantFP: {
394 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
397 case ISD::TargetGlobalAddress:
398 case ISD::GlobalAddress:
399 case ISD::TargetGlobalTLSAddress:
400 case ISD::GlobalTLSAddress: {
401 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
402 ID.AddPointer(GA->getGlobal());
403 ID.AddInteger(GA->getOffset());
404 ID.AddInteger(GA->getTargetFlags());
405 ID.AddInteger(GA->getAddressSpace());
408 case ISD::BasicBlock:
409 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
412 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
414 case ISD::RegisterMask:
415 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
418 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
420 case ISD::FrameIndex:
421 case ISD::TargetFrameIndex:
422 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
425 case ISD::TargetJumpTable:
426 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
427 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
429 case ISD::ConstantPool:
430 case ISD::TargetConstantPool: {
431 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
432 ID.AddInteger(CP->getAlignment());
433 ID.AddInteger(CP->getOffset());
434 if (CP->isMachineConstantPoolEntry())
435 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
437 ID.AddPointer(CP->getConstVal());
438 ID.AddInteger(CP->getTargetFlags());
441 case ISD::TargetIndex: {
442 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
443 ID.AddInteger(TI->getIndex());
444 ID.AddInteger(TI->getOffset());
445 ID.AddInteger(TI->getTargetFlags());
449 const LoadSDNode *LD = cast<LoadSDNode>(N);
450 ID.AddInteger(LD->getMemoryVT().getRawBits());
451 ID.AddInteger(LD->getRawSubclassData());
452 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
456 const StoreSDNode *ST = cast<StoreSDNode>(N);
457 ID.AddInteger(ST->getMemoryVT().getRawBits());
458 ID.AddInteger(ST->getRawSubclassData());
459 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
462 case ISD::ATOMIC_CMP_SWAP:
463 case ISD::ATOMIC_SWAP:
464 case ISD::ATOMIC_LOAD_ADD:
465 case ISD::ATOMIC_LOAD_SUB:
466 case ISD::ATOMIC_LOAD_AND:
467 case ISD::ATOMIC_LOAD_OR:
468 case ISD::ATOMIC_LOAD_XOR:
469 case ISD::ATOMIC_LOAD_NAND:
470 case ISD::ATOMIC_LOAD_MIN:
471 case ISD::ATOMIC_LOAD_MAX:
472 case ISD::ATOMIC_LOAD_UMIN:
473 case ISD::ATOMIC_LOAD_UMAX:
474 case ISD::ATOMIC_LOAD:
475 case ISD::ATOMIC_STORE: {
476 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
477 ID.AddInteger(AT->getMemoryVT().getRawBits());
478 ID.AddInteger(AT->getRawSubclassData());
479 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
482 case ISD::PREFETCH: {
483 const MemSDNode *PF = cast<MemSDNode>(N);
484 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
487 case ISD::VECTOR_SHUFFLE: {
488 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
489 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
491 ID.AddInteger(SVN->getMaskElt(i));
494 case ISD::TargetBlockAddress:
495 case ISD::BlockAddress: {
496 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
497 ID.AddPointer(BA->getBlockAddress());
498 ID.AddInteger(BA->getOffset());
499 ID.AddInteger(BA->getTargetFlags());
502 } // end switch (N->getOpcode())
504 // Target specific memory nodes could also have address spaces to check.
505 if (N->isTargetMemoryOpcode())
506 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
509 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
511 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
512 AddNodeIDOpcode(ID, N->getOpcode());
513 // Add the return value info.
514 AddNodeIDValueTypes(ID, N->getVTList());
515 // Add the operand info.
516 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
518 // Handle SDNode leafs with special info.
519 AddNodeIDCustom(ID, N);
522 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
523 /// the CSE map that carries volatility, temporalness, indexing mode, and
524 /// extension/truncation information.
526 static inline unsigned
527 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
528 bool isNonTemporal, bool isInvariant) {
529 assert((ConvType & 3) == ConvType &&
530 "ConvType may not require more than 2 bits!");
531 assert((AM & 7) == AM &&
532 "AM may not require more than 3 bits!");
536 (isNonTemporal << 6) |
540 //===----------------------------------------------------------------------===//
541 // SelectionDAG Class
542 //===----------------------------------------------------------------------===//
544 /// doNotCSE - Return true if CSE should not be performed for this node.
545 static bool doNotCSE(SDNode *N) {
546 if (N->getValueType(0) == MVT::Glue)
547 return true; // Never CSE anything that produces a flag.
549 switch (N->getOpcode()) {
551 case ISD::HANDLENODE:
553 return true; // Never CSE these nodes.
556 // Check that remaining values produced are not flags.
557 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
558 if (N->getValueType(i) == MVT::Glue)
559 return true; // Never CSE anything that produces a flag.
564 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
566 void SelectionDAG::RemoveDeadNodes() {
567 // Create a dummy node (which is not added to allnodes), that adds a reference
568 // to the root node, preventing it from being deleted.
569 HandleSDNode Dummy(getRoot());
571 SmallVector<SDNode*, 128> DeadNodes;
573 // Add all obviously-dead nodes to the DeadNodes worklist.
574 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
576 DeadNodes.push_back(I);
578 RemoveDeadNodes(DeadNodes);
580 // If the root changed (e.g. it was a dead load, update the root).
581 setRoot(Dummy.getValue());
584 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
585 /// given list, and any nodes that become unreachable as a result.
586 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
588 // Process the worklist, deleting the nodes and adding their uses to the
590 while (!DeadNodes.empty()) {
591 SDNode *N = DeadNodes.pop_back_val();
593 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
594 DUL->NodeDeleted(N, 0);
596 // Take the node out of the appropriate CSE map.
597 RemoveNodeFromCSEMaps(N);
599 // Next, brutally remove the operand list. This is safe to do, as there are
600 // no cycles in the graph.
601 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
603 SDNode *Operand = Use.getNode();
606 // Now that we removed this operand, see if there are no uses of it left.
607 if (Operand->use_empty())
608 DeadNodes.push_back(Operand);
615 void SelectionDAG::RemoveDeadNode(SDNode *N){
616 SmallVector<SDNode*, 16> DeadNodes(1, N);
618 // Create a dummy node that adds a reference to the root node, preventing
619 // it from being deleted. (This matters if the root is an operand of the
621 HandleSDNode Dummy(getRoot());
623 RemoveDeadNodes(DeadNodes);
626 void SelectionDAG::DeleteNode(SDNode *N) {
627 // First take this out of the appropriate CSE map.
628 RemoveNodeFromCSEMaps(N);
630 // Finally, remove uses due to operands of this node, remove from the
631 // AllNodes list, and delete the node.
632 DeleteNodeNotInCSEMaps(N);
635 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
636 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
637 assert(N->use_empty() && "Cannot delete a node that is not dead!");
639 // Drop all of the operands and decrement used node's use counts.
645 void SelectionDAG::DeallocateNode(SDNode *N) {
646 if (N->OperandsNeedDelete)
647 delete[] N->OperandList;
649 // Set the opcode to DELETED_NODE to help catch bugs when node
650 // memory is reallocated.
651 N->NodeType = ISD::DELETED_NODE;
653 NodeAllocator.Deallocate(AllNodes.remove(N));
655 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
656 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
657 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
658 DbgVals[i]->setIsInvalidated();
661 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
662 /// correspond to it. This is useful when we're about to delete or repurpose
663 /// the node. We don't want future request for structurally identical nodes
664 /// to return N anymore.
665 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
667 switch (N->getOpcode()) {
668 case ISD::HANDLENODE: return false; // noop.
670 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
671 "Cond code doesn't exist!");
672 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
673 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
675 case ISD::ExternalSymbol:
676 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
678 case ISD::TargetExternalSymbol: {
679 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
680 Erased = TargetExternalSymbols.erase(
681 std::pair<std::string,unsigned char>(ESN->getSymbol(),
682 ESN->getTargetFlags()));
685 case ISD::VALUETYPE: {
686 EVT VT = cast<VTSDNode>(N)->getVT();
687 if (VT.isExtended()) {
688 Erased = ExtendedValueTypeNodes.erase(VT);
690 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
691 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
696 // Remove it from the CSE Map.
697 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
698 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
699 Erased = CSEMap.RemoveNode(N);
703 // Verify that the node was actually in one of the CSE maps, unless it has a
704 // flag result (which cannot be CSE'd) or is one of the special cases that are
705 // not subject to CSE.
706 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
707 !N->isMachineOpcode() && !doNotCSE(N)) {
710 llvm_unreachable("Node is not in map!");
716 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
717 /// maps and modified in place. Add it back to the CSE maps, unless an identical
718 /// node already exists, in which case transfer all its users to the existing
719 /// node. This transfer can potentially trigger recursive merging.
722 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
723 // For node types that aren't CSE'd, just act as if no identical node
726 SDNode *Existing = CSEMap.GetOrInsertNode(N);
728 // If there was already an existing matching node, use ReplaceAllUsesWith
729 // to replace the dead one with the existing one. This can cause
730 // recursive merging of other unrelated nodes down the line.
731 ReplaceAllUsesWith(N, Existing);
733 // N is now dead. Inform the listeners and delete it.
734 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
735 DUL->NodeDeleted(N, Existing);
736 DeleteNodeNotInCSEMaps(N);
741 // If the node doesn't already exist, we updated it. Inform listeners.
742 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
746 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
747 /// were replaced with those specified. If this node is never memoized,
748 /// return null, otherwise return a pointer to the slot it would take. If a
749 /// node already exists with these operands, the slot will be non-null.
750 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
755 SDValue Ops[] = { Op };
757 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
758 AddNodeIDCustom(ID, N);
759 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
763 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
764 /// were replaced with those specified. If this node is never memoized,
765 /// return null, otherwise return a pointer to the slot it would take. If a
766 /// node already exists with these operands, the slot will be non-null.
767 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
768 SDValue Op1, SDValue Op2,
773 SDValue Ops[] = { Op1, Op2 };
775 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
776 AddNodeIDCustom(ID, N);
777 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
782 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
783 /// were replaced with those specified. If this node is never memoized,
784 /// return null, otherwise return a pointer to the slot it would take. If a
785 /// node already exists with these operands, the slot will be non-null.
786 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
787 const SDValue *Ops,unsigned NumOps,
793 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
794 AddNodeIDCustom(ID, N);
795 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
800 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
801 static void VerifyNodeCommon(SDNode *N) {
802 switch (N->getOpcode()) {
805 case ISD::BUILD_PAIR: {
806 EVT VT = N->getValueType(0);
807 assert(N->getNumValues() == 1 && "Too many results!");
808 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
809 "Wrong return type!");
810 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
811 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
812 "Mismatched operand types!");
813 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
814 "Wrong operand type!");
815 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
816 "Wrong return type size");
819 case ISD::BUILD_VECTOR: {
820 assert(N->getNumValues() == 1 && "Too many results!");
821 assert(N->getValueType(0).isVector() && "Wrong return type!");
822 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
823 "Wrong number of operands!");
824 EVT EltVT = N->getValueType(0).getVectorElementType();
825 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
826 assert((I->getValueType() == EltVT ||
827 (EltVT.isInteger() && I->getValueType().isInteger() &&
828 EltVT.bitsLE(I->getValueType()))) &&
829 "Wrong operand type!");
830 assert(I->getValueType() == N->getOperand(0).getValueType() &&
831 "Operands must all have the same type");
838 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
839 static void VerifySDNode(SDNode *N) {
840 // The SDNode allocators cannot be used to allocate nodes with fields that are
841 // not present in an SDNode!
842 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
843 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
844 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
845 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
846 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
847 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
848 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
849 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
850 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
851 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
852 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
853 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
854 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
855 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
856 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
857 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
858 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
859 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
860 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
865 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
867 static void VerifyMachineNode(SDNode *N) {
868 // The MachineNode allocators cannot be used to allocate nodes with fields
869 // that are not present in a MachineNode!
870 // Currently there are no such nodes.
876 /// getEVTAlignment - Compute the default alignment value for the
879 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
880 Type *Ty = VT == MVT::iPTR ?
881 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
882 VT.getTypeForEVT(*getContext());
884 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
887 // EntryNode could meaningfully have debug info if we can find it...
888 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
889 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(0), OptLevel(OL),
890 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
891 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
893 AllNodes.push_back(&EntryNode);
894 DbgInfo = new SDDbgInfo();
897 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
900 Context = &mf.getFunction()->getContext();
903 SelectionDAG::~SelectionDAG() {
904 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
909 void SelectionDAG::allnodes_clear() {
910 assert(&*AllNodes.begin() == &EntryNode);
911 AllNodes.remove(AllNodes.begin());
912 while (!AllNodes.empty())
913 DeallocateNode(AllNodes.begin());
916 void SelectionDAG::clear() {
918 OperandAllocator.Reset();
921 ExtendedValueTypeNodes.clear();
922 ExternalSymbols.clear();
923 TargetExternalSymbols.clear();
924 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
925 static_cast<CondCodeSDNode*>(0));
926 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
927 static_cast<SDNode*>(0));
929 EntryNode.UseList = 0;
930 AllNodes.push_back(&EntryNode);
931 Root = getEntryNode();
935 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
936 return VT.bitsGT(Op.getValueType()) ?
937 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
938 getNode(ISD::TRUNCATE, DL, VT, Op);
941 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
942 return VT.bitsGT(Op.getValueType()) ?
943 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
944 getNode(ISD::TRUNCATE, DL, VT, Op);
947 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
948 return VT.bitsGT(Op.getValueType()) ?
949 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
950 getNode(ISD::TRUNCATE, DL, VT, Op);
953 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
954 assert(!VT.isVector() &&
955 "getZeroExtendInReg should use the vector element type instead of "
957 if (Op.getValueType() == VT) return Op;
958 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
959 APInt Imm = APInt::getLowBitsSet(BitWidth,
961 return getNode(ISD::AND, DL, Op.getValueType(), Op,
962 getConstant(Imm, Op.getValueType()));
965 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
967 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
968 EVT EltVT = VT.getScalarType();
970 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
971 return getNode(ISD::XOR, DL, VT, Val, NegOne);
974 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
975 EVT EltVT = VT.getScalarType();
976 assert((EltVT.getSizeInBits() >= 64 ||
977 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
978 "getConstant with a uint64_t value that doesn't fit in the type!");
979 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
982 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
984 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
987 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
989 assert(VT.isInteger() && "Cannot create FP integer constant!");
991 EVT EltVT = VT.getScalarType();
992 const ConstantInt *Elt = &Val;
994 const TargetLowering *TLI = TM.getTargetLowering();
996 // In some cases the vector type is legal but the element type is illegal and
997 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
998 // inserted value (the type does not need to match the vector element type).
999 // Any extra bits introduced will be truncated away.
1000 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1001 TargetLowering::TypePromoteInteger) {
1002 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1003 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1004 Elt = ConstantInt::get(*getContext(), NewVal);
1006 // In other cases the element type is illegal and needs to be expanded, for
1007 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1008 // the value into n parts and use a vector type with n-times the elements.
1009 // Then bitcast to the type requested.
1010 // Legalizing constants too early makes the DAGCombiner's job harder so we
1011 // only legalize if the DAG tells us we must produce legal types.
1012 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1013 TLI->getTypeAction(*getContext(), EltVT) ==
1014 TargetLowering::TypeExpandInteger) {
1015 APInt NewVal = Elt->getValue();
1016 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1017 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1018 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1019 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1021 // Check the temporary vector is the correct size. If this fails then
1022 // getTypeToTransformTo() probably returned a type whose size (in bits)
1023 // isn't a power-of-2 factor of the requested type size.
1024 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1026 SmallVector<SDValue, 2> EltParts;
1027 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1028 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1029 .trunc(ViaEltSizeInBits),
1030 ViaEltVT, isT, isO));
1033 // EltParts is currently in little endian order. If we actually want
1034 // big-endian order then reverse it now.
1035 if (TLI->isBigEndian())
1036 std::reverse(EltParts.begin(), EltParts.end());
1038 // The elements must be reversed when the element order is different
1039 // to the endianness of the elements (because the BITCAST is itself a
1040 // vector shuffle in this situation). However, we do not need any code to
1041 // perform this reversal because getConstant() is producing a vector
1043 // This situation occurs in MIPS MSA.
1045 SmallVector<SDValue, 8> Ops;
1046 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1047 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1049 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1050 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1051 &Ops[0], Ops.size()));
1055 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1056 "APInt size does not match type size!");
1057 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1058 FoldingSetNodeID ID;
1059 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1064 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1066 return SDValue(N, 0);
1069 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1070 CSEMap.InsertNode(N, IP);
1071 AllNodes.push_back(N);
1074 SDValue Result(N, 0);
1075 if (VT.isVector()) {
1076 SmallVector<SDValue, 8> Ops;
1077 Ops.assign(VT.getVectorNumElements(), Result);
1078 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1083 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1084 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1088 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1089 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1092 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1093 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1095 EVT EltVT = VT.getScalarType();
1097 // Do the map lookup using the actual bit pattern for the floating point
1098 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1099 // we don't have issues with SNANs.
1100 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1101 FoldingSetNodeID ID;
1102 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1106 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1108 return SDValue(N, 0);
1111 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1112 CSEMap.InsertNode(N, IP);
1113 AllNodes.push_back(N);
1116 SDValue Result(N, 0);
1117 if (VT.isVector()) {
1118 SmallVector<SDValue, 8> Ops;
1119 Ops.assign(VT.getVectorNumElements(), Result);
1120 // FIXME SDLoc info might be appropriate here
1121 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, &Ops[0], Ops.size());
1126 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1127 EVT EltVT = VT.getScalarType();
1128 if (EltVT==MVT::f32)
1129 return getConstantFP(APFloat((float)Val), VT, isTarget);
1130 else if (EltVT==MVT::f64)
1131 return getConstantFP(APFloat(Val), VT, isTarget);
1132 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1135 APFloat apf = APFloat(Val);
1136 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1138 return getConstantFP(apf, VT, isTarget);
1140 llvm_unreachable("Unsupported type in getConstantFP");
1143 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1144 EVT VT, int64_t Offset,
1146 unsigned char TargetFlags) {
1147 assert((TargetFlags == 0 || isTargetGA) &&
1148 "Cannot set target flags on target-independent globals");
1149 const TargetLowering *TLI = TM.getTargetLowering();
1151 // Truncate (with sign-extension) the offset value to the pointer size.
1152 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1154 Offset = SignExtend64(Offset, BitWidth);
1156 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1158 // If GV is an alias then use the aliasee for determining thread-localness.
1159 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1160 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1164 if (GVar && GVar->isThreadLocal())
1165 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1167 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1169 FoldingSetNodeID ID;
1170 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1172 ID.AddInteger(Offset);
1173 ID.AddInteger(TargetFlags);
1174 ID.AddInteger(GV->getType()->getAddressSpace());
1176 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1177 return SDValue(E, 0);
1179 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1180 DL.getDebugLoc(), GV, VT,
1181 Offset, TargetFlags);
1182 CSEMap.InsertNode(N, IP);
1183 AllNodes.push_back(N);
1184 return SDValue(N, 0);
1187 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1188 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1189 FoldingSetNodeID ID;
1190 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1193 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1194 return SDValue(E, 0);
1196 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1197 CSEMap.InsertNode(N, IP);
1198 AllNodes.push_back(N);
1199 return SDValue(N, 0);
1202 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1203 unsigned char TargetFlags) {
1204 assert((TargetFlags == 0 || isTarget) &&
1205 "Cannot set target flags on target-independent jump tables");
1206 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1207 FoldingSetNodeID ID;
1208 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1210 ID.AddInteger(TargetFlags);
1212 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1213 return SDValue(E, 0);
1215 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1217 CSEMap.InsertNode(N, IP);
1218 AllNodes.push_back(N);
1219 return SDValue(N, 0);
1222 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1223 unsigned Alignment, int Offset,
1225 unsigned char TargetFlags) {
1226 assert((TargetFlags == 0 || isTarget) &&
1227 "Cannot set target flags on target-independent globals");
1230 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1231 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1232 FoldingSetNodeID ID;
1233 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1234 ID.AddInteger(Alignment);
1235 ID.AddInteger(Offset);
1237 ID.AddInteger(TargetFlags);
1239 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1240 return SDValue(E, 0);
1242 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1243 Alignment, TargetFlags);
1244 CSEMap.InsertNode(N, IP);
1245 AllNodes.push_back(N);
1246 return SDValue(N, 0);
1250 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1251 unsigned Alignment, int Offset,
1253 unsigned char TargetFlags) {
1254 assert((TargetFlags == 0 || isTarget) &&
1255 "Cannot set target flags on target-independent globals");
1258 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1259 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1260 FoldingSetNodeID ID;
1261 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1262 ID.AddInteger(Alignment);
1263 ID.AddInteger(Offset);
1264 C->addSelectionDAGCSEId(ID);
1265 ID.AddInteger(TargetFlags);
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1271 Alignment, TargetFlags);
1272 CSEMap.InsertNode(N, IP);
1273 AllNodes.push_back(N);
1274 return SDValue(N, 0);
1277 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1278 unsigned char TargetFlags) {
1279 FoldingSetNodeID ID;
1280 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), 0, 0);
1281 ID.AddInteger(Index);
1282 ID.AddInteger(Offset);
1283 ID.AddInteger(TargetFlags);
1285 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1286 return SDValue(E, 0);
1288 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1290 CSEMap.InsertNode(N, IP);
1291 AllNodes.push_back(N);
1292 return SDValue(N, 0);
1295 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1296 FoldingSetNodeID ID;
1297 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1300 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1301 return SDValue(E, 0);
1303 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1304 CSEMap.InsertNode(N, IP);
1305 AllNodes.push_back(N);
1306 return SDValue(N, 0);
1309 SDValue SelectionDAG::getValueType(EVT VT) {
1310 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1311 ValueTypeNodes.size())
1312 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1314 SDNode *&N = VT.isExtended() ?
1315 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1317 if (N) return SDValue(N, 0);
1318 N = new (NodeAllocator) VTSDNode(VT);
1319 AllNodes.push_back(N);
1320 return SDValue(N, 0);
1323 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1324 SDNode *&N = ExternalSymbols[Sym];
1325 if (N) return SDValue(N, 0);
1326 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1327 AllNodes.push_back(N);
1328 return SDValue(N, 0);
1331 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1332 unsigned char TargetFlags) {
1334 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1336 if (N) return SDValue(N, 0);
1337 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1338 AllNodes.push_back(N);
1339 return SDValue(N, 0);
1342 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1343 if ((unsigned)Cond >= CondCodeNodes.size())
1344 CondCodeNodes.resize(Cond+1);
1346 if (CondCodeNodes[Cond] == 0) {
1347 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1348 CondCodeNodes[Cond] = N;
1349 AllNodes.push_back(N);
1352 return SDValue(CondCodeNodes[Cond], 0);
1355 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1356 // the shuffle mask M that point at N1 to point at N2, and indices that point
1357 // N2 to point at N1.
1358 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1360 int NElts = M.size();
1361 for (int i = 0; i != NElts; ++i) {
1369 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1370 SDValue N2, const int *Mask) {
1371 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1372 "Invalid VECTOR_SHUFFLE");
1374 // Canonicalize shuffle undef, undef -> undef
1375 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1376 return getUNDEF(VT);
1378 // Validate that all indices in Mask are within the range of the elements
1379 // input to the shuffle.
1380 unsigned NElts = VT.getVectorNumElements();
1381 SmallVector<int, 8> MaskVec;
1382 for (unsigned i = 0; i != NElts; ++i) {
1383 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1384 MaskVec.push_back(Mask[i]);
1387 // Canonicalize shuffle v, v -> v, undef
1390 for (unsigned i = 0; i != NElts; ++i)
1391 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1394 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1395 if (N1.getOpcode() == ISD::UNDEF)
1396 commuteShuffle(N1, N2, MaskVec);
1398 // Canonicalize all index into lhs, -> shuffle lhs, undef
1399 // Canonicalize all index into rhs, -> shuffle rhs, undef
1400 bool AllLHS = true, AllRHS = true;
1401 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1402 for (unsigned i = 0; i != NElts; ++i) {
1403 if (MaskVec[i] >= (int)NElts) {
1408 } else if (MaskVec[i] >= 0) {
1412 if (AllLHS && AllRHS)
1413 return getUNDEF(VT);
1414 if (AllLHS && !N2Undef)
1418 commuteShuffle(N1, N2, MaskVec);
1421 // If Identity shuffle return that node.
1422 bool Identity = true;
1423 for (unsigned i = 0; i != NElts; ++i) {
1424 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1426 if (Identity && NElts)
1429 FoldingSetNodeID ID;
1430 SDValue Ops[2] = { N1, N2 };
1431 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1432 for (unsigned i = 0; i != NElts; ++i)
1433 ID.AddInteger(MaskVec[i]);
1436 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1437 return SDValue(E, 0);
1439 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1440 // SDNode doesn't have access to it. This memory will be "leaked" when
1441 // the node is deallocated, but recovered when the NodeAllocator is released.
1442 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1443 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1445 ShuffleVectorSDNode *N =
1446 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1447 dl.getDebugLoc(), N1, N2,
1449 CSEMap.InsertNode(N, IP);
1450 AllNodes.push_back(N);
1451 return SDValue(N, 0);
1454 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1455 SDValue Val, SDValue DTy,
1456 SDValue STy, SDValue Rnd, SDValue Sat,
1457 ISD::CvtCode Code) {
1458 // If the src and dest types are the same and the conversion is between
1459 // integer types of the same sign or two floats, no conversion is necessary.
1461 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1464 FoldingSetNodeID ID;
1465 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1466 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1468 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1469 return SDValue(E, 0);
1471 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1474 CSEMap.InsertNode(N, IP);
1475 AllNodes.push_back(N);
1476 return SDValue(N, 0);
1479 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1480 FoldingSetNodeID ID;
1481 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1482 ID.AddInteger(RegNo);
1484 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1485 return SDValue(E, 0);
1487 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1488 CSEMap.InsertNode(N, IP);
1489 AllNodes.push_back(N);
1490 return SDValue(N, 0);
1493 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1494 FoldingSetNodeID ID;
1495 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), 0, 0);
1496 ID.AddPointer(RegMask);
1498 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1499 return SDValue(E, 0);
1501 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1502 CSEMap.InsertNode(N, IP);
1503 AllNodes.push_back(N);
1504 return SDValue(N, 0);
1507 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1508 FoldingSetNodeID ID;
1509 SDValue Ops[] = { Root };
1510 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1511 ID.AddPointer(Label);
1513 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1514 return SDValue(E, 0);
1516 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1517 dl.getDebugLoc(), Root, Label);
1518 CSEMap.InsertNode(N, IP);
1519 AllNodes.push_back(N);
1520 return SDValue(N, 0);
1524 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1527 unsigned char TargetFlags) {
1528 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1530 FoldingSetNodeID ID;
1531 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1533 ID.AddInteger(Offset);
1534 ID.AddInteger(TargetFlags);
1536 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1537 return SDValue(E, 0);
1539 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1541 CSEMap.InsertNode(N, IP);
1542 AllNodes.push_back(N);
1543 return SDValue(N, 0);
1546 SDValue SelectionDAG::getSrcValue(const Value *V) {
1547 assert((!V || V->getType()->isPointerTy()) &&
1548 "SrcValue is not a pointer?");
1550 FoldingSetNodeID ID;
1551 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1555 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1556 return SDValue(E, 0);
1558 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1559 CSEMap.InsertNode(N, IP);
1560 AllNodes.push_back(N);
1561 return SDValue(N, 0);
1564 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1565 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1566 FoldingSetNodeID ID;
1567 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1571 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1572 return SDValue(E, 0);
1574 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1575 CSEMap.InsertNode(N, IP);
1576 AllNodes.push_back(N);
1577 return SDValue(N, 0);
1580 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1581 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1582 unsigned SrcAS, unsigned DestAS) {
1583 SDValue Ops[] = {Ptr};
1584 FoldingSetNodeID ID;
1585 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), &Ops[0], 1);
1586 ID.AddInteger(SrcAS);
1587 ID.AddInteger(DestAS);
1590 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1591 return SDValue(E, 0);
1593 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1595 VT, Ptr, SrcAS, DestAS);
1596 CSEMap.InsertNode(N, IP);
1597 AllNodes.push_back(N);
1598 return SDValue(N, 0);
1601 /// getShiftAmountOperand - Return the specified value casted to
1602 /// the target's desired shift amount type.
1603 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1604 EVT OpTy = Op.getValueType();
1605 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1606 if (OpTy == ShTy || OpTy.isVector()) return Op;
1608 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1609 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1612 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1613 /// specified value type.
1614 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1615 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1616 unsigned ByteSize = VT.getStoreSize();
1617 Type *Ty = VT.getTypeForEVT(*getContext());
1618 const TargetLowering *TLI = TM.getTargetLowering();
1619 unsigned StackAlign =
1620 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1622 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1623 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1626 /// CreateStackTemporary - Create a stack temporary suitable for holding
1627 /// either of the specified value types.
1628 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1629 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1630 VT2.getStoreSizeInBits())/8;
1631 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1632 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1633 const TargetLowering *TLI = TM.getTargetLowering();
1634 const DataLayout *TD = TLI->getDataLayout();
1635 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1636 TD->getPrefTypeAlignment(Ty2));
1638 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1639 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1640 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1643 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1644 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1645 // These setcc operations always fold.
1649 case ISD::SETFALSE2: return getConstant(0, VT);
1651 case ISD::SETTRUE2: {
1652 const TargetLowering *TLI = TM.getTargetLowering();
1653 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1655 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1668 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1672 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1673 const APInt &C2 = N2C->getAPIntValue();
1674 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1675 const APInt &C1 = N1C->getAPIntValue();
1678 default: llvm_unreachable("Unknown integer setcc!");
1679 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1680 case ISD::SETNE: return getConstant(C1 != C2, VT);
1681 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1682 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1683 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1684 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1685 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1686 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1687 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1688 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1692 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1693 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1694 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1697 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1698 return getUNDEF(VT);
1700 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1701 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1702 return getUNDEF(VT);
1704 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1705 R==APFloat::cmpLessThan, VT);
1706 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1707 return getUNDEF(VT);
1709 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1710 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1711 return getUNDEF(VT);
1713 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1714 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1715 return getUNDEF(VT);
1717 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1718 R==APFloat::cmpEqual, VT);
1719 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1720 return getUNDEF(VT);
1722 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1723 R==APFloat::cmpEqual, VT);
1724 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1725 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1726 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1727 R==APFloat::cmpEqual, VT);
1728 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1729 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1730 R==APFloat::cmpLessThan, VT);
1731 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1732 R==APFloat::cmpUnordered, VT);
1733 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1734 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1737 // Ensure that the constant occurs on the RHS.
1738 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1739 MVT CompVT = N1.getValueType().getSimpleVT();
1740 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1743 return getSetCC(dl, VT, N2, N1, SwappedCond);
1747 // Could not fold it.
1751 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1752 /// use this predicate to simplify operations downstream.
1753 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1754 // This predicate is not safe for vector operations.
1755 if (Op.getValueType().isVector())
1758 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1759 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1762 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1763 /// this predicate to simplify operations downstream. Mask is known to be zero
1764 /// for bits that V cannot have.
1765 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1766 unsigned Depth) const {
1767 APInt KnownZero, KnownOne;
1768 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1769 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1770 return (KnownZero & Mask) == Mask;
1773 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1774 /// known to be either zero or one and return them in the KnownZero/KnownOne
1775 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1777 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1778 APInt &KnownOne, unsigned Depth) const {
1779 const TargetLowering *TLI = TM.getTargetLowering();
1780 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1782 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1784 return; // Limit search depth.
1786 APInt KnownZero2, KnownOne2;
1788 switch (Op.getOpcode()) {
1790 // We know all of the bits for a constant!
1791 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1792 KnownZero = ~KnownOne;
1795 // If either the LHS or the RHS are Zero, the result is zero.
1796 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1797 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1798 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1799 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1801 // Output known-1 bits are only known if set in both the LHS & RHS.
1802 KnownOne &= KnownOne2;
1803 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1804 KnownZero |= KnownZero2;
1807 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1808 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1809 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1810 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1812 // Output known-0 bits are only known if clear in both the LHS & RHS.
1813 KnownZero &= KnownZero2;
1814 // Output known-1 are known to be set if set in either the LHS | RHS.
1815 KnownOne |= KnownOne2;
1818 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1819 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1820 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1821 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1823 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1824 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1825 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1826 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1827 KnownZero = KnownZeroOut;
1831 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1832 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1833 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1834 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1836 // If low bits are zero in either operand, output low known-0 bits.
1837 // Also compute a conserative estimate for high known-0 bits.
1838 // More trickiness is possible, but this is sufficient for the
1839 // interesting case of alignment computation.
1840 KnownOne.clearAllBits();
1841 unsigned TrailZ = KnownZero.countTrailingOnes() +
1842 KnownZero2.countTrailingOnes();
1843 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1844 KnownZero2.countLeadingOnes(),
1845 BitWidth) - BitWidth;
1847 TrailZ = std::min(TrailZ, BitWidth);
1848 LeadZ = std::min(LeadZ, BitWidth);
1849 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1850 APInt::getHighBitsSet(BitWidth, LeadZ);
1854 // For the purposes of computing leading zeros we can conservatively
1855 // treat a udiv as a logical right shift by the power of 2 known to
1856 // be less than the denominator.
1857 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1858 unsigned LeadZ = KnownZero2.countLeadingOnes();
1860 KnownOne2.clearAllBits();
1861 KnownZero2.clearAllBits();
1862 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1863 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1864 if (RHSUnknownLeadingOnes != BitWidth)
1865 LeadZ = std::min(BitWidth,
1866 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1868 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1872 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1873 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1874 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1875 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1877 // Only known if known in both the LHS and RHS.
1878 KnownOne &= KnownOne2;
1879 KnownZero &= KnownZero2;
1881 case ISD::SELECT_CC:
1882 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1883 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1884 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1885 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1887 // Only known if known in both the LHS and RHS.
1888 KnownOne &= KnownOne2;
1889 KnownZero &= KnownZero2;
1897 if (Op.getResNo() != 1)
1899 // The boolean result conforms to getBooleanContents. Fall through.
1901 // If we know the result of a setcc has the top bits zero, use this info.
1902 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1903 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1904 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1907 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1908 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1909 unsigned ShAmt = SA->getZExtValue();
1911 // If the shift count is an invalid immediate, don't do anything.
1912 if (ShAmt >= BitWidth)
1915 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1916 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1917 KnownZero <<= ShAmt;
1919 // low bits known zero.
1920 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1924 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1925 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1926 unsigned ShAmt = SA->getZExtValue();
1928 // If the shift count is an invalid immediate, don't do anything.
1929 if (ShAmt >= BitWidth)
1932 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1933 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1934 KnownZero = KnownZero.lshr(ShAmt);
1935 KnownOne = KnownOne.lshr(ShAmt);
1937 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1938 KnownZero |= HighBits; // High bits known zero.
1942 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1943 unsigned ShAmt = SA->getZExtValue();
1945 // If the shift count is an invalid immediate, don't do anything.
1946 if (ShAmt >= BitWidth)
1949 // If any of the demanded bits are produced by the sign extension, we also
1950 // demand the input sign bit.
1951 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1953 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1954 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1955 KnownZero = KnownZero.lshr(ShAmt);
1956 KnownOne = KnownOne.lshr(ShAmt);
1958 // Handle the sign bits.
1959 APInt SignBit = APInt::getSignBit(BitWidth);
1960 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1962 if (KnownZero.intersects(SignBit)) {
1963 KnownZero |= HighBits; // New bits are known zero.
1964 } else if (KnownOne.intersects(SignBit)) {
1965 KnownOne |= HighBits; // New bits are known one.
1969 case ISD::SIGN_EXTEND_INREG: {
1970 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1971 unsigned EBits = EVT.getScalarType().getSizeInBits();
1973 // Sign extension. Compute the demanded bits in the result that are not
1974 // present in the input.
1975 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1977 APInt InSignBit = APInt::getSignBit(EBits);
1978 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1980 // If the sign extended bits are demanded, we know that the sign
1982 InSignBit = InSignBit.zext(BitWidth);
1983 if (NewBits.getBoolValue())
1984 InputDemandedBits |= InSignBit;
1986 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1987 KnownOne &= InputDemandedBits;
1988 KnownZero &= InputDemandedBits;
1989 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1991 // If the sign bit of the input is known set or clear, then we know the
1992 // top bits of the result.
1993 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1994 KnownZero |= NewBits;
1995 KnownOne &= ~NewBits;
1996 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1997 KnownOne |= NewBits;
1998 KnownZero &= ~NewBits;
1999 } else { // Input sign bit unknown
2000 KnownZero &= ~NewBits;
2001 KnownOne &= ~NewBits;
2006 case ISD::CTTZ_ZERO_UNDEF:
2008 case ISD::CTLZ_ZERO_UNDEF:
2010 unsigned LowBits = Log2_32(BitWidth)+1;
2011 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2012 KnownOne.clearAllBits();
2016 LoadSDNode *LD = cast<LoadSDNode>(Op);
2017 // If this is a ZEXTLoad and we are looking at the loaded value.
2018 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2019 EVT VT = LD->getMemoryVT();
2020 unsigned MemBits = VT.getScalarType().getSizeInBits();
2021 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2022 } else if (const MDNode *Ranges = LD->getRanges()) {
2023 computeMaskedBitsLoad(*Ranges, KnownZero);
2027 case ISD::ZERO_EXTEND: {
2028 EVT InVT = Op.getOperand(0).getValueType();
2029 unsigned InBits = InVT.getScalarType().getSizeInBits();
2030 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2031 KnownZero = KnownZero.trunc(InBits);
2032 KnownOne = KnownOne.trunc(InBits);
2033 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2034 KnownZero = KnownZero.zext(BitWidth);
2035 KnownOne = KnownOne.zext(BitWidth);
2036 KnownZero |= NewBits;
2039 case ISD::SIGN_EXTEND: {
2040 EVT InVT = Op.getOperand(0).getValueType();
2041 unsigned InBits = InVT.getScalarType().getSizeInBits();
2042 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2044 KnownZero = KnownZero.trunc(InBits);
2045 KnownOne = KnownOne.trunc(InBits);
2046 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2048 // Note if the sign bit is known to be zero or one.
2049 bool SignBitKnownZero = KnownZero.isNegative();
2050 bool SignBitKnownOne = KnownOne.isNegative();
2051 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2052 "Sign bit can't be known to be both zero and one!");
2054 KnownZero = KnownZero.zext(BitWidth);
2055 KnownOne = KnownOne.zext(BitWidth);
2057 // If the sign bit is known zero or one, the top bits match.
2058 if (SignBitKnownZero)
2059 KnownZero |= NewBits;
2060 else if (SignBitKnownOne)
2061 KnownOne |= NewBits;
2064 case ISD::ANY_EXTEND: {
2065 EVT InVT = Op.getOperand(0).getValueType();
2066 unsigned InBits = InVT.getScalarType().getSizeInBits();
2067 KnownZero = KnownZero.trunc(InBits);
2068 KnownOne = KnownOne.trunc(InBits);
2069 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2070 KnownZero = KnownZero.zext(BitWidth);
2071 KnownOne = KnownOne.zext(BitWidth);
2074 case ISD::TRUNCATE: {
2075 EVT InVT = Op.getOperand(0).getValueType();
2076 unsigned InBits = InVT.getScalarType().getSizeInBits();
2077 KnownZero = KnownZero.zext(InBits);
2078 KnownOne = KnownOne.zext(InBits);
2079 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2080 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2081 KnownZero = KnownZero.trunc(BitWidth);
2082 KnownOne = KnownOne.trunc(BitWidth);
2085 case ISD::AssertZext: {
2086 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2087 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2088 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2089 KnownZero |= (~InMask);
2090 KnownOne &= (~KnownZero);
2094 // All bits are zero except the low bit.
2095 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2099 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2100 // We know that the top bits of C-X are clear if X contains less bits
2101 // than C (i.e. no wrap-around can happen). For example, 20-X is
2102 // positive if we can prove that X is >= 0 and < 16.
2103 if (CLHS->getAPIntValue().isNonNegative()) {
2104 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2105 // NLZ can't be BitWidth with no sign bit
2106 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2107 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2109 // If all of the MaskV bits are known to be zero, then we know the
2110 // output top bits are zero, because we now know that the output is
2112 if ((KnownZero2 & MaskV) == MaskV) {
2113 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2114 // Top bits known zero.
2115 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2123 // Output known-0 bits are known if clear or set in both the low clear bits
2124 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2125 // low 3 bits clear.
2126 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2127 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2128 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2130 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2131 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2132 KnownZeroOut = std::min(KnownZeroOut,
2133 KnownZero2.countTrailingOnes());
2135 if (Op.getOpcode() == ISD::ADD) {
2136 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2140 // With ADDE, a carry bit may be added in, so we can only use this
2141 // information if we know (at least) that the low two bits are clear. We
2142 // then return to the caller that the low bit is unknown but that other bits
2144 if (KnownZeroOut >= 2) // ADDE
2145 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2149 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2150 const APInt &RA = Rem->getAPIntValue().abs();
2151 if (RA.isPowerOf2()) {
2152 APInt LowBits = RA - 1;
2153 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2155 // The low bits of the first operand are unchanged by the srem.
2156 KnownZero = KnownZero2 & LowBits;
2157 KnownOne = KnownOne2 & LowBits;
2159 // If the first operand is non-negative or has all low bits zero, then
2160 // the upper bits are all zero.
2161 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2162 KnownZero |= ~LowBits;
2164 // If the first operand is negative and not all low bits are zero, then
2165 // the upper bits are all one.
2166 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2167 KnownOne |= ~LowBits;
2168 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2173 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2174 const APInt &RA = Rem->getAPIntValue();
2175 if (RA.isPowerOf2()) {
2176 APInt LowBits = (RA - 1);
2177 KnownZero |= ~LowBits;
2178 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2179 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2184 // Since the result is less than or equal to either operand, any leading
2185 // zero bits in either operand must also exist in the result.
2186 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2187 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2189 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2190 KnownZero2.countLeadingOnes());
2191 KnownOne.clearAllBits();
2192 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2195 case ISD::FrameIndex:
2196 case ISD::TargetFrameIndex:
2197 if (unsigned Align = InferPtrAlignment(Op)) {
2198 // The low bits are known zero if the pointer is aligned.
2199 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2205 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2208 case ISD::INTRINSIC_WO_CHAIN:
2209 case ISD::INTRINSIC_W_CHAIN:
2210 case ISD::INTRINSIC_VOID:
2211 // Allow the target to implement this method for its nodes.
2212 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2217 /// ComputeNumSignBits - Return the number of times the sign bit of the
2218 /// register is replicated into the other bits. We know that at least 1 bit
2219 /// is always equal to the sign bit (itself), but other cases can give us
2220 /// information. For example, immediately after an "SRA X, 2", we know that
2221 /// the top 3 bits are all equal to each other, so we return 3.
2222 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2223 const TargetLowering *TLI = TM.getTargetLowering();
2224 EVT VT = Op.getValueType();
2225 assert(VT.isInteger() && "Invalid VT!");
2226 unsigned VTBits = VT.getScalarType().getSizeInBits();
2228 unsigned FirstAnswer = 1;
2231 return 1; // Limit search depth.
2233 switch (Op.getOpcode()) {
2235 case ISD::AssertSext:
2236 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2237 return VTBits-Tmp+1;
2238 case ISD::AssertZext:
2239 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2242 case ISD::Constant: {
2243 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2244 return Val.getNumSignBits();
2247 case ISD::SIGN_EXTEND:
2249 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2250 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2252 case ISD::SIGN_EXTEND_INREG:
2253 // Max of the input and what this extends.
2255 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2258 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2259 return std::max(Tmp, Tmp2);
2262 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2263 // SRA X, C -> adds C sign bits.
2264 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2265 Tmp += C->getZExtValue();
2266 if (Tmp > VTBits) Tmp = VTBits;
2270 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2271 // shl destroys sign bits.
2272 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2273 if (C->getZExtValue() >= VTBits || // Bad shift.
2274 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2275 return Tmp - C->getZExtValue();
2280 case ISD::XOR: // NOT is handled here.
2281 // Logical binary ops preserve the number of sign bits at the worst.
2282 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2284 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2285 FirstAnswer = std::min(Tmp, Tmp2);
2286 // We computed what we know about the sign bits as our first
2287 // answer. Now proceed to the generic code that uses
2288 // ComputeMaskedBits, and pick whichever answer is better.
2293 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2294 if (Tmp == 1) return 1; // Early out.
2295 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2296 return std::min(Tmp, Tmp2);
2304 if (Op.getResNo() != 1)
2306 // The boolean result conforms to getBooleanContents. Fall through.
2308 // If setcc returns 0/-1, all bits are sign bits.
2309 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2310 TargetLowering::ZeroOrNegativeOneBooleanContent)
2315 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2316 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2318 // Handle rotate right by N like a rotate left by 32-N.
2319 if (Op.getOpcode() == ISD::ROTR)
2320 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2322 // If we aren't rotating out all of the known-in sign bits, return the
2323 // number that are left. This handles rotl(sext(x), 1) for example.
2324 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2325 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2329 // Add can have at most one carry bit. Thus we know that the output
2330 // is, at worst, one more bit than the inputs.
2331 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2332 if (Tmp == 1) return 1; // Early out.
2334 // Special case decrementing a value (ADD X, -1):
2335 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2336 if (CRHS->isAllOnesValue()) {
2337 APInt KnownZero, KnownOne;
2338 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2340 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2342 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2345 // If we are subtracting one from a positive number, there is no carry
2346 // out of the result.
2347 if (KnownZero.isNegative())
2351 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2352 if (Tmp2 == 1) return 1;
2353 return std::min(Tmp, Tmp2)-1;
2356 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2357 if (Tmp2 == 1) return 1;
2360 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2361 if (CLHS->isNullValue()) {
2362 APInt KnownZero, KnownOne;
2363 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2364 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2366 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2369 // If the input is known to be positive (the sign bit is known clear),
2370 // the output of the NEG has the same number of sign bits as the input.
2371 if (KnownZero.isNegative())
2374 // Otherwise, we treat this like a SUB.
2377 // Sub can have at most one carry bit. Thus we know that the output
2378 // is, at worst, one more bit than the inputs.
2379 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2380 if (Tmp == 1) return 1; // Early out.
2381 return std::min(Tmp, Tmp2)-1;
2383 // FIXME: it's tricky to do anything useful for this, but it is an important
2384 // case for targets like X86.
2388 // If we are looking at the loaded value of the SDNode.
2389 if (Op.getResNo() == 0) {
2390 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2391 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2392 unsigned ExtType = LD->getExtensionType();
2395 case ISD::SEXTLOAD: // '17' bits known
2396 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2397 return VTBits-Tmp+1;
2398 case ISD::ZEXTLOAD: // '16' bits known
2399 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2405 // Allow the target to implement this method for its nodes.
2406 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2407 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2408 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2409 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2410 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, Depth);
2411 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2414 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2415 // use this information.
2416 APInt KnownZero, KnownOne;
2417 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2420 if (KnownZero.isNegative()) { // sign bit is 0
2422 } else if (KnownOne.isNegative()) { // sign bit is 1;
2429 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2430 // the number of identical bits in the top of the input value.
2432 Mask <<= Mask.getBitWidth()-VTBits;
2433 // Return # leading zeros. We use 'min' here in case Val was zero before
2434 // shifting. We don't want to return '64' as for an i32 "0".
2435 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2438 /// isBaseWithConstantOffset - Return true if the specified operand is an
2439 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2440 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2441 /// semantics as an ADD. This handles the equivalence:
2442 /// X|Cst == X+Cst iff X&Cst = 0.
2443 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2444 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2445 !isa<ConstantSDNode>(Op.getOperand(1)))
2448 if (Op.getOpcode() == ISD::OR &&
2449 !MaskedValueIsZero(Op.getOperand(0),
2450 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2457 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2458 // If we're told that NaNs won't happen, assume they won't.
2459 if (getTarget().Options.NoNaNsFPMath)
2462 // If the value is a constant, we can obviously see if it is a NaN or not.
2463 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2464 return !C->getValueAPF().isNaN();
2466 // TODO: Recognize more cases here.
2471 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2472 // If the value is a constant, we can obviously see if it is a zero or not.
2473 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2474 return !C->isZero();
2476 // TODO: Recognize more cases here.
2477 switch (Op.getOpcode()) {
2480 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2481 return !C->isNullValue();
2488 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2489 // Check the obvious case.
2490 if (A == B) return true;
2492 // For for negative and positive zero.
2493 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2494 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2495 if (CA->isZero() && CB->isZero()) return true;
2497 // Otherwise they may not be equal.
2501 /// getNode - Gets or creates the specified node.
2503 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2504 FoldingSetNodeID ID;
2505 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2507 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2508 return SDValue(E, 0);
2510 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2511 DL.getDebugLoc(), getVTList(VT));
2512 CSEMap.InsertNode(N, IP);
2514 AllNodes.push_back(N);
2518 return SDValue(N, 0);
2521 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2522 EVT VT, SDValue Operand) {
2523 // Constant fold unary operations with an integer constant operand.
2524 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2525 const APInt &Val = C->getAPIntValue();
2528 case ISD::SIGN_EXTEND:
2529 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2530 case ISD::ANY_EXTEND:
2531 case ISD::ZERO_EXTEND:
2533 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2534 case ISD::UINT_TO_FP:
2535 case ISD::SINT_TO_FP: {
2536 APFloat apf(EVTToAPFloatSemantics(VT),
2537 APInt::getNullValue(VT.getSizeInBits()));
2538 (void)apf.convertFromAPInt(Val,
2539 Opcode==ISD::SINT_TO_FP,
2540 APFloat::rmNearestTiesToEven);
2541 return getConstantFP(apf, VT);
2544 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2545 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2546 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2547 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2550 return getConstant(Val.byteSwap(), VT);
2552 return getConstant(Val.countPopulation(), VT);
2554 case ISD::CTLZ_ZERO_UNDEF:
2555 return getConstant(Val.countLeadingZeros(), VT);
2557 case ISD::CTTZ_ZERO_UNDEF:
2558 return getConstant(Val.countTrailingZeros(), VT);
2562 // Constant fold unary operations with a floating point constant operand.
2563 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2564 APFloat V = C->getValueAPF(); // make copy
2568 return getConstantFP(V, VT);
2571 return getConstantFP(V, VT);
2573 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2574 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2575 return getConstantFP(V, VT);
2579 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2580 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2581 return getConstantFP(V, VT);
2585 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2586 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2587 return getConstantFP(V, VT);
2590 case ISD::FP_EXTEND: {
2592 // This can return overflow, underflow, or inexact; we don't care.
2593 // FIXME need to be more flexible about rounding mode.
2594 (void)V.convert(EVTToAPFloatSemantics(VT),
2595 APFloat::rmNearestTiesToEven, &ignored);
2596 return getConstantFP(V, VT);
2598 case ISD::FP_TO_SINT:
2599 case ISD::FP_TO_UINT: {
2602 assert(integerPartWidth >= 64);
2603 // FIXME need to be more flexible about rounding mode.
2604 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2605 Opcode==ISD::FP_TO_SINT,
2606 APFloat::rmTowardZero, &ignored);
2607 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2609 APInt api(VT.getSizeInBits(), x);
2610 return getConstant(api, VT);
2613 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2614 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2615 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2616 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2621 unsigned OpOpcode = Operand.getNode()->getOpcode();
2623 case ISD::TokenFactor:
2624 case ISD::MERGE_VALUES:
2625 case ISD::CONCAT_VECTORS:
2626 return Operand; // Factor, merge or concat of one node? No need.
2627 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2628 case ISD::FP_EXTEND:
2629 assert(VT.isFloatingPoint() &&
2630 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2631 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2632 assert((!VT.isVector() ||
2633 VT.getVectorNumElements() ==
2634 Operand.getValueType().getVectorNumElements()) &&
2635 "Vector element count mismatch!");
2636 if (Operand.getOpcode() == ISD::UNDEF)
2637 return getUNDEF(VT);
2639 case ISD::SIGN_EXTEND:
2640 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2641 "Invalid SIGN_EXTEND!");
2642 if (Operand.getValueType() == VT) return Operand; // noop extension
2643 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2644 "Invalid sext node, dst < src!");
2645 assert((!VT.isVector() ||
2646 VT.getVectorNumElements() ==
2647 Operand.getValueType().getVectorNumElements()) &&
2648 "Vector element count mismatch!");
2649 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2650 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2651 else if (OpOpcode == ISD::UNDEF)
2652 // sext(undef) = 0, because the top bits will all be the same.
2653 return getConstant(0, VT);
2655 case ISD::ZERO_EXTEND:
2656 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2657 "Invalid ZERO_EXTEND!");
2658 if (Operand.getValueType() == VT) return Operand; // noop extension
2659 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2660 "Invalid zext node, dst < src!");
2661 assert((!VT.isVector() ||
2662 VT.getVectorNumElements() ==
2663 Operand.getValueType().getVectorNumElements()) &&
2664 "Vector element count mismatch!");
2665 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2666 return getNode(ISD::ZERO_EXTEND, DL, VT,
2667 Operand.getNode()->getOperand(0));
2668 else if (OpOpcode == ISD::UNDEF)
2669 // zext(undef) = 0, because the top bits will be zero.
2670 return getConstant(0, VT);
2672 case ISD::ANY_EXTEND:
2673 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2674 "Invalid ANY_EXTEND!");
2675 if (Operand.getValueType() == VT) return Operand; // noop extension
2676 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2677 "Invalid anyext node, dst < src!");
2678 assert((!VT.isVector() ||
2679 VT.getVectorNumElements() ==
2680 Operand.getValueType().getVectorNumElements()) &&
2681 "Vector element count mismatch!");
2683 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2684 OpOpcode == ISD::ANY_EXTEND)
2685 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2686 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2687 else if (OpOpcode == ISD::UNDEF)
2688 return getUNDEF(VT);
2690 // (ext (trunx x)) -> x
2691 if (OpOpcode == ISD::TRUNCATE) {
2692 SDValue OpOp = Operand.getNode()->getOperand(0);
2693 if (OpOp.getValueType() == VT)
2698 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2699 "Invalid TRUNCATE!");
2700 if (Operand.getValueType() == VT) return Operand; // noop truncate
2701 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2702 "Invalid truncate node, src < dst!");
2703 assert((!VT.isVector() ||
2704 VT.getVectorNumElements() ==
2705 Operand.getValueType().getVectorNumElements()) &&
2706 "Vector element count mismatch!");
2707 if (OpOpcode == ISD::TRUNCATE)
2708 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2709 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2710 OpOpcode == ISD::ANY_EXTEND) {
2711 // If the source is smaller than the dest, we still need an extend.
2712 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2713 .bitsLT(VT.getScalarType()))
2714 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2715 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2716 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2717 return Operand.getNode()->getOperand(0);
2719 if (OpOpcode == ISD::UNDEF)
2720 return getUNDEF(VT);
2723 // Basic sanity checking.
2724 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2725 && "Cannot BITCAST between types of different sizes!");
2726 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2727 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2728 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2729 if (OpOpcode == ISD::UNDEF)
2730 return getUNDEF(VT);
2732 case ISD::SCALAR_TO_VECTOR:
2733 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2734 (VT.getVectorElementType() == Operand.getValueType() ||
2735 (VT.getVectorElementType().isInteger() &&
2736 Operand.getValueType().isInteger() &&
2737 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2738 "Illegal SCALAR_TO_VECTOR node!");
2739 if (OpOpcode == ISD::UNDEF)
2740 return getUNDEF(VT);
2741 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2742 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2743 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2744 Operand.getConstantOperandVal(1) == 0 &&
2745 Operand.getOperand(0).getValueType() == VT)
2746 return Operand.getOperand(0);
2749 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2750 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2751 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2752 Operand.getNode()->getOperand(0));
2753 if (OpOpcode == ISD::FNEG) // --X -> X
2754 return Operand.getNode()->getOperand(0);
2757 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2758 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2763 SDVTList VTs = getVTList(VT);
2764 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2765 FoldingSetNodeID ID;
2766 SDValue Ops[1] = { Operand };
2767 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2769 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2770 return SDValue(E, 0);
2772 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2773 DL.getDebugLoc(), VTs, Operand);
2774 CSEMap.InsertNode(N, IP);
2776 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2777 DL.getDebugLoc(), VTs, Operand);
2780 AllNodes.push_back(N);
2784 return SDValue(N, 0);
2787 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2788 SDNode *Cst1, SDNode *Cst2) {
2789 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2790 SmallVector<SDValue, 4> Outputs;
2791 EVT SVT = VT.getScalarType();
2793 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2794 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2795 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2798 if (Scalar1 && Scalar2)
2799 // Scalar instruction.
2800 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2802 // For vectors extract each constant element into Inputs so we can constant
2803 // fold them individually.
2804 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2805 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2809 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2811 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2812 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2813 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2814 if (!V1 || !V2) // Not a constant, bail.
2817 if (V1->isOpaque() || V2->isOpaque())
2820 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2821 // FIXME: This is valid and could be handled by truncating the APInts.
2822 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2825 Inputs.push_back(std::make_pair(V1, V2));
2829 // We have a number of constant values, constant fold them element by element.
2830 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2831 const APInt &C1 = Inputs[I].first->getAPIntValue();
2832 const APInt &C2 = Inputs[I].second->getAPIntValue();
2836 Outputs.push_back(getConstant(C1 + C2, SVT));
2839 Outputs.push_back(getConstant(C1 - C2, SVT));
2842 Outputs.push_back(getConstant(C1 * C2, SVT));
2845 if (!C2.getBoolValue())
2847 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2850 if (!C2.getBoolValue())
2852 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2855 if (!C2.getBoolValue())
2857 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2860 if (!C2.getBoolValue())
2862 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2865 Outputs.push_back(getConstant(C1 & C2, SVT));
2868 Outputs.push_back(getConstant(C1 | C2, SVT));
2871 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2874 Outputs.push_back(getConstant(C1 << C2, SVT));
2877 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2880 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2883 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2886 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2893 // Handle the scalar case first.
2894 if (Scalar1 && Scalar2)
2895 return Outputs.back();
2897 // Otherwise build a big vector out of the scalar elements we generated.
2898 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs.data(),
2902 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2904 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2905 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2908 case ISD::TokenFactor:
2909 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2910 N2.getValueType() == MVT::Other && "Invalid token factor!");
2911 // Fold trivial token factors.
2912 if (N1.getOpcode() == ISD::EntryToken) return N2;
2913 if (N2.getOpcode() == ISD::EntryToken) return N1;
2914 if (N1 == N2) return N1;
2916 case ISD::CONCAT_VECTORS:
2917 // Concat of UNDEFs is UNDEF.
2918 if (N1.getOpcode() == ISD::UNDEF &&
2919 N2.getOpcode() == ISD::UNDEF)
2920 return getUNDEF(VT);
2922 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2923 // one big BUILD_VECTOR.
2924 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2925 N2.getOpcode() == ISD::BUILD_VECTOR) {
2926 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2927 N1.getNode()->op_end());
2928 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2929 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2933 assert(VT.isInteger() && "This operator does not apply to FP types!");
2934 assert(N1.getValueType() == N2.getValueType() &&
2935 N1.getValueType() == VT && "Binary operator types must match!");
2936 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2937 // worth handling here.
2938 if (N2C && N2C->isNullValue())
2940 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2947 assert(VT.isInteger() && "This operator does not apply to FP types!");
2948 assert(N1.getValueType() == N2.getValueType() &&
2949 N1.getValueType() == VT && "Binary operator types must match!");
2950 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2951 // it's worth handling here.
2952 if (N2C && N2C->isNullValue())
2962 assert(VT.isInteger() && "This operator does not apply to FP types!");
2963 assert(N1.getValueType() == N2.getValueType() &&
2964 N1.getValueType() == VT && "Binary operator types must match!");
2971 if (getTarget().Options.UnsafeFPMath) {
2972 if (Opcode == ISD::FADD) {
2974 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2975 if (CFP->getValueAPF().isZero())
2978 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2979 if (CFP->getValueAPF().isZero())
2981 } else if (Opcode == ISD::FSUB) {
2983 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2984 if (CFP->getValueAPF().isZero())
2986 } else if (Opcode == ISD::FMUL) {
2987 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
2990 // If the first operand isn't the constant, try the second
2992 CFP = dyn_cast<ConstantFPSDNode>(N2);
2999 return SDValue(CFP,0);
3001 if (CFP->isExactlyValue(1.0))
3006 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3007 assert(N1.getValueType() == N2.getValueType() &&
3008 N1.getValueType() == VT && "Binary operator types must match!");
3010 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3011 assert(N1.getValueType() == VT &&
3012 N1.getValueType().isFloatingPoint() &&
3013 N2.getValueType().isFloatingPoint() &&
3014 "Invalid FCOPYSIGN!");
3021 assert(VT == N1.getValueType() &&
3022 "Shift operators return type must be the same as their first arg");
3023 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3024 "Shifts only work on integers");
3025 assert((!VT.isVector() || VT == N2.getValueType()) &&
3026 "Vector shift amounts must be in the same as their first arg");
3027 // Verify that the shift amount VT is bit enough to hold valid shift
3028 // amounts. This catches things like trying to shift an i1024 value by an
3029 // i8, which is easy to fall into in generic code that uses
3030 // TLI.getShiftAmount().
3031 assert(N2.getValueType().getSizeInBits() >=
3032 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3033 "Invalid use of small shift amount with oversized value!");
3035 // Always fold shifts of i1 values so the code generator doesn't need to
3036 // handle them. Since we know the size of the shift has to be less than the
3037 // size of the value, the shift/rotate count is guaranteed to be zero.
3040 if (N2C && N2C->isNullValue())
3043 case ISD::FP_ROUND_INREG: {
3044 EVT EVT = cast<VTSDNode>(N2)->getVT();
3045 assert(VT == N1.getValueType() && "Not an inreg round!");
3046 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3047 "Cannot FP_ROUND_INREG integer types");
3048 assert(EVT.isVector() == VT.isVector() &&
3049 "FP_ROUND_INREG type should be vector iff the operand "
3051 assert((!EVT.isVector() ||
3052 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3053 "Vector element counts must match in FP_ROUND_INREG");
3054 assert(EVT.bitsLE(VT) && "Not rounding down!");
3056 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3060 assert(VT.isFloatingPoint() &&
3061 N1.getValueType().isFloatingPoint() &&
3062 VT.bitsLE(N1.getValueType()) &&
3063 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3064 if (N1.getValueType() == VT) return N1; // noop conversion.
3066 case ISD::AssertSext:
3067 case ISD::AssertZext: {
3068 EVT EVT = cast<VTSDNode>(N2)->getVT();
3069 assert(VT == N1.getValueType() && "Not an inreg extend!");
3070 assert(VT.isInteger() && EVT.isInteger() &&
3071 "Cannot *_EXTEND_INREG FP types");
3072 assert(!EVT.isVector() &&
3073 "AssertSExt/AssertZExt type should be the vector element type "
3074 "rather than the vector type!");
3075 assert(EVT.bitsLE(VT) && "Not extending!");
3076 if (VT == EVT) return N1; // noop assertion.
3079 case ISD::SIGN_EXTEND_INREG: {
3080 EVT EVT = cast<VTSDNode>(N2)->getVT();
3081 assert(VT == N1.getValueType() && "Not an inreg extend!");
3082 assert(VT.isInteger() && EVT.isInteger() &&
3083 "Cannot *_EXTEND_INREG FP types");
3084 assert(EVT.isVector() == VT.isVector() &&
3085 "SIGN_EXTEND_INREG type should be vector iff the operand "
3087 assert((!EVT.isVector() ||
3088 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3089 "Vector element counts must match in SIGN_EXTEND_INREG");
3090 assert(EVT.bitsLE(VT) && "Not extending!");
3091 if (EVT == VT) return N1; // Not actually extending
3094 APInt Val = N1C->getAPIntValue();
3095 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3096 Val <<= Val.getBitWidth()-FromBits;
3097 Val = Val.ashr(Val.getBitWidth()-FromBits);
3098 return getConstant(Val, VT);
3102 case ISD::EXTRACT_VECTOR_ELT:
3103 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3104 if (N1.getOpcode() == ISD::UNDEF)
3105 return getUNDEF(VT);
3107 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3108 // expanding copies of large vectors from registers.
3110 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3111 N1.getNumOperands() > 0) {
3113 N1.getOperand(0).getValueType().getVectorNumElements();
3114 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3115 N1.getOperand(N2C->getZExtValue() / Factor),
3116 getConstant(N2C->getZExtValue() % Factor,
3117 N2.getValueType()));
3120 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3121 // expanding large vector constants.
3122 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3123 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3125 if (VT != Elt.getValueType())
3126 // If the vector element type is not legal, the BUILD_VECTOR operands
3127 // are promoted and implicitly truncated, and the result implicitly
3128 // extended. Make that explicit here.
3129 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3134 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3135 // operations are lowered to scalars.
3136 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3137 // If the indices are the same, return the inserted element else
3138 // if the indices are known different, extract the element from
3139 // the original vector.
3140 SDValue N1Op2 = N1.getOperand(2);
3141 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3143 if (N1Op2C && N2C) {
3144 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3145 if (VT == N1.getOperand(1).getValueType())
3146 return N1.getOperand(1);
3148 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3151 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3155 case ISD::EXTRACT_ELEMENT:
3156 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3157 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3158 (N1.getValueType().isInteger() == VT.isInteger()) &&
3159 N1.getValueType() != VT &&
3160 "Wrong types for EXTRACT_ELEMENT!");
3162 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3163 // 64-bit integers into 32-bit parts. Instead of building the extract of
3164 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3165 if (N1.getOpcode() == ISD::BUILD_PAIR)
3166 return N1.getOperand(N2C->getZExtValue());
3168 // EXTRACT_ELEMENT of a constant int is also very common.
3169 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3170 unsigned ElementSize = VT.getSizeInBits();
3171 unsigned Shift = ElementSize * N2C->getZExtValue();
3172 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3173 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3176 case ISD::EXTRACT_SUBVECTOR: {
3178 if (VT.isSimple() && N1.getValueType().isSimple()) {
3179 assert(VT.isVector() && N1.getValueType().isVector() &&
3180 "Extract subvector VTs must be a vectors!");
3181 assert(VT.getVectorElementType() ==
3182 N1.getValueType().getVectorElementType() &&
3183 "Extract subvector VTs must have the same element type!");
3184 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3185 "Extract subvector must be from larger vector to smaller vector!");
3187 if (isa<ConstantSDNode>(Index.getNode())) {
3188 assert((VT.getVectorNumElements() +
3189 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3190 <= N1.getValueType().getVectorNumElements())
3191 && "Extract subvector overflow!");
3194 // Trivial extraction.
3195 if (VT.getSimpleVT() == N1.getSimpleValueType())
3202 // Perform trivial constant folding.
3203 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3204 if (SV.getNode()) return SV;
3206 // Canonicalize constant to RHS if commutative.
3207 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3208 std::swap(N1C, N2C);
3212 // Constant fold FP operations.
3213 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3214 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3216 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3217 // Canonicalize constant to RHS if commutative.
3218 std::swap(N1CFP, N2CFP);
3221 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3222 APFloat::opStatus s;
3225 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3226 if (s != APFloat::opInvalidOp)
3227 return getConstantFP(V1, VT);
3230 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3231 if (s!=APFloat::opInvalidOp)
3232 return getConstantFP(V1, VT);
3235 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3236 if (s!=APFloat::opInvalidOp)
3237 return getConstantFP(V1, VT);
3240 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3241 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3242 return getConstantFP(V1, VT);
3245 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3246 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3247 return getConstantFP(V1, VT);
3249 case ISD::FCOPYSIGN:
3251 return getConstantFP(V1, VT);
3256 if (Opcode == ISD::FP_ROUND) {
3257 APFloat V = N1CFP->getValueAPF(); // make copy
3259 // This can return overflow, underflow, or inexact; we don't care.
3260 // FIXME need to be more flexible about rounding mode.
3261 (void)V.convert(EVTToAPFloatSemantics(VT),
3262 APFloat::rmNearestTiesToEven, &ignored);
3263 return getConstantFP(V, VT);
3267 // Canonicalize an UNDEF to the RHS, even over a constant.
3268 if (N1.getOpcode() == ISD::UNDEF) {
3269 if (isCommutativeBinOp(Opcode)) {
3273 case ISD::FP_ROUND_INREG:
3274 case ISD::SIGN_EXTEND_INREG:
3280 return N1; // fold op(undef, arg2) -> undef
3288 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3289 // For vectors, we can't easily build an all zero vector, just return
3296 // Fold a bunch of operators when the RHS is undef.
3297 if (N2.getOpcode() == ISD::UNDEF) {
3300 if (N1.getOpcode() == ISD::UNDEF)
3301 // Handle undef ^ undef -> 0 special case. This is a common
3303 return getConstant(0, VT);
3313 return N2; // fold op(arg1, undef) -> undef
3319 if (getTarget().Options.UnsafeFPMath)
3327 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3328 // For vectors, we can't easily build an all zero vector, just return
3333 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3334 // For vectors, we can't easily build an all one vector, just return
3342 // Memoize this node if possible.
3344 SDVTList VTs = getVTList(VT);
3345 if (VT != MVT::Glue) {
3346 SDValue Ops[] = { N1, N2 };
3347 FoldingSetNodeID ID;
3348 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3350 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3351 return SDValue(E, 0);
3353 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3354 DL.getDebugLoc(), VTs, N1, N2);
3355 CSEMap.InsertNode(N, IP);
3357 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3358 DL.getDebugLoc(), VTs, N1, N2);
3361 AllNodes.push_back(N);
3365 return SDValue(N, 0);
3368 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3369 SDValue N1, SDValue N2, SDValue N3) {
3370 // Perform various simplifications.
3371 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3374 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3375 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3376 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3377 if (N1CFP && N2CFP && N3CFP) {
3378 APFloat V1 = N1CFP->getValueAPF();
3379 const APFloat &V2 = N2CFP->getValueAPF();
3380 const APFloat &V3 = N3CFP->getValueAPF();
3381 APFloat::opStatus s =
3382 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3383 if (s != APFloat::opInvalidOp)
3384 return getConstantFP(V1, VT);
3388 case ISD::CONCAT_VECTORS:
3389 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3390 // one big BUILD_VECTOR.
3391 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3392 N2.getOpcode() == ISD::BUILD_VECTOR &&
3393 N3.getOpcode() == ISD::BUILD_VECTOR) {
3394 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3395 N1.getNode()->op_end());
3396 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3397 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3398 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3402 // Use FoldSetCC to simplify SETCC's.
3403 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3404 if (Simp.getNode()) return Simp;
3409 if (N1C->getZExtValue())
3410 return N2; // select true, X, Y -> X
3411 return N3; // select false, X, Y -> Y
3414 if (N2 == N3) return N2; // select C, X, X -> X
3416 case ISD::VECTOR_SHUFFLE:
3417 llvm_unreachable("should use getVectorShuffle constructor!");
3418 case ISD::INSERT_SUBVECTOR: {
3420 if (VT.isSimple() && N1.getValueType().isSimple()
3421 && N2.getValueType().isSimple()) {
3422 assert(VT.isVector() && N1.getValueType().isVector() &&
3423 N2.getValueType().isVector() &&
3424 "Insert subvector VTs must be a vectors");
3425 assert(VT == N1.getValueType() &&
3426 "Dest and insert subvector source types must match!");
3427 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3428 "Insert subvector must be from smaller vector to larger vector!");
3429 if (isa<ConstantSDNode>(Index.getNode())) {
3430 assert((N2.getValueType().getVectorNumElements() +
3431 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3432 <= VT.getVectorNumElements())
3433 && "Insert subvector overflow!");
3436 // Trivial insertion.
3437 if (VT.getSimpleVT() == N2.getSimpleValueType())
3443 // Fold bit_convert nodes from a type to themselves.
3444 if (N1.getValueType() == VT)
3449 // Memoize node if it doesn't produce a flag.
3451 SDVTList VTs = getVTList(VT);
3452 if (VT != MVT::Glue) {
3453 SDValue Ops[] = { N1, N2, N3 };
3454 FoldingSetNodeID ID;
3455 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3457 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3458 return SDValue(E, 0);
3460 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3461 DL.getDebugLoc(), VTs, N1, N2, N3);
3462 CSEMap.InsertNode(N, IP);
3464 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3465 DL.getDebugLoc(), VTs, N1, N2, N3);
3468 AllNodes.push_back(N);
3472 return SDValue(N, 0);
3475 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3476 SDValue N1, SDValue N2, SDValue N3,
3478 SDValue Ops[] = { N1, N2, N3, N4 };
3479 return getNode(Opcode, DL, VT, Ops, 4);
3482 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3483 SDValue N1, SDValue N2, SDValue N3,
3484 SDValue N4, SDValue N5) {
3485 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3486 return getNode(Opcode, DL, VT, Ops, 5);
3489 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3490 /// the incoming stack arguments to be loaded from the stack.
3491 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3492 SmallVector<SDValue, 8> ArgChains;
3494 // Include the original chain at the beginning of the list. When this is
3495 // used by target LowerCall hooks, this helps legalize find the
3496 // CALLSEQ_BEGIN node.
3497 ArgChains.push_back(Chain);
3499 // Add a chain value for each stack argument.
3500 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3501 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3502 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3503 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3504 if (FI->getIndex() < 0)
3505 ArgChains.push_back(SDValue(L, 1));
3507 // Build a tokenfactor for all the chains.
3508 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other,
3509 &ArgChains[0], ArgChains.size());
3512 /// getMemsetValue - Vectorized representation of the memset value
3514 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3516 assert(Value.getOpcode() != ISD::UNDEF);
3518 unsigned NumBits = VT.getScalarType().getSizeInBits();
3519 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3520 assert(C->getAPIntValue().getBitWidth() == 8);
3521 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3523 return DAG.getConstant(Val, VT);
3524 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3527 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3529 // Use a multiplication with 0x010101... to extend the input to the
3531 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3532 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3538 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3539 /// used when a memcpy is turned into a memset when the source is a constant
3541 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3542 const TargetLowering &TLI, StringRef Str) {
3543 // Handle vector with all elements zero.
3546 return DAG.getConstant(0, VT);
3547 else if (VT == MVT::f32 || VT == MVT::f64)
3548 return DAG.getConstantFP(0.0, VT);
3549 else if (VT.isVector()) {
3550 unsigned NumElts = VT.getVectorNumElements();
3551 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3552 return DAG.getNode(ISD::BITCAST, dl, VT,
3553 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3556 llvm_unreachable("Expected type!");
3559 assert(!VT.isVector() && "Can't handle vector type here!");
3560 unsigned NumVTBits = VT.getSizeInBits();
3561 unsigned NumVTBytes = NumVTBits / 8;
3562 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3564 APInt Val(NumVTBits, 0);
3565 if (TLI.isLittleEndian()) {
3566 for (unsigned i = 0; i != NumBytes; ++i)
3567 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3569 for (unsigned i = 0; i != NumBytes; ++i)
3570 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3573 // If the "cost" of materializing the integer immediate is less than the cost
3574 // of a load, then it is cost effective to turn the load into the immediate.
3575 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3576 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3577 return DAG.getConstant(Val, VT);
3578 return SDValue(0, 0);
3581 /// getMemBasePlusOffset - Returns base and offset node for the
3583 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3584 SelectionDAG &DAG) {
3585 EVT VT = Base.getValueType();
3586 return DAG.getNode(ISD::ADD, dl,
3587 VT, Base, DAG.getConstant(Offset, VT));
3590 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3592 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3593 unsigned SrcDelta = 0;
3594 GlobalAddressSDNode *G = NULL;
3595 if (Src.getOpcode() == ISD::GlobalAddress)
3596 G = cast<GlobalAddressSDNode>(Src);
3597 else if (Src.getOpcode() == ISD::ADD &&
3598 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3599 Src.getOperand(1).getOpcode() == ISD::Constant) {
3600 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3601 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3606 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3609 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3610 /// to replace the memset / memcpy. Return true if the number of memory ops
3611 /// is below the threshold. It returns the types of the sequence of
3612 /// memory ops to perform memset / memcpy by reference.
3613 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3614 unsigned Limit, uint64_t Size,
3615 unsigned DstAlign, unsigned SrcAlign,
3621 const TargetLowering &TLI) {
3622 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3623 "Expecting memcpy / memset source to meet alignment requirement!");
3624 // If 'SrcAlign' is zero, that means the memory operation does not need to
3625 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3626 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3627 // is the specified alignment of the memory operation. If it is zero, that
3628 // means it's possible to change the alignment of the destination.
3629 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3630 // not need to be loaded.
3631 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3632 IsMemset, ZeroMemset, MemcpyStrSrc,
3633 DAG.getMachineFunction());
3635 if (VT == MVT::Other) {
3636 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment() ||
3637 TLI.allowsUnalignedMemoryAccesses(VT)) {
3638 VT = TLI.getPointerTy();
3640 switch (DstAlign & 7) {
3641 case 0: VT = MVT::i64; break;
3642 case 4: VT = MVT::i32; break;
3643 case 2: VT = MVT::i16; break;
3644 default: VT = MVT::i8; break;
3649 while (!TLI.isTypeLegal(LVT))
3650 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3651 assert(LVT.isInteger());
3657 unsigned NumMemOps = 0;
3659 unsigned VTSize = VT.getSizeInBits() / 8;
3660 while (VTSize > Size) {
3661 // For now, only use non-vector load / store's for the left-over pieces.
3666 if (VT.isVector() || VT.isFloatingPoint()) {
3667 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3668 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3669 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3671 else if (NewVT == MVT::i64 &&
3672 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3673 TLI.isSafeMemOpType(MVT::f64)) {
3674 // i64 is usually not legal on 32-bit targets, but f64 may be.
3682 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3683 if (NewVT == MVT::i8)
3685 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3687 NewVTSize = NewVT.getSizeInBits() / 8;
3689 // If the new VT cannot cover all of the remaining bits, then consider
3690 // issuing a (or a pair of) unaligned and overlapping load / store.
3691 // FIXME: Only does this for 64-bit or more since we don't have proper
3692 // cost model for unaligned load / store.
3694 if (NumMemOps && AllowOverlap &&
3695 VTSize >= 8 && NewVTSize < Size &&
3696 TLI.allowsUnalignedMemoryAccesses(VT, &Fast) && Fast)
3704 if (++NumMemOps > Limit)
3707 MemOps.push_back(VT);
3714 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3715 SDValue Chain, SDValue Dst,
3716 SDValue Src, uint64_t Size,
3717 unsigned Align, bool isVol,
3719 MachinePointerInfo DstPtrInfo,
3720 MachinePointerInfo SrcPtrInfo) {
3721 // Turn a memcpy of undef to nop.
3722 if (Src.getOpcode() == ISD::UNDEF)
3725 // Expand memcpy to a series of load and store ops if the size operand falls
3726 // below a certain threshold.
3727 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3728 // rather than maybe a humongous number of loads and stores.
3729 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3730 std::vector<EVT> MemOps;
3731 bool DstAlignCanChange = false;
3732 MachineFunction &MF = DAG.getMachineFunction();
3733 MachineFrameInfo *MFI = MF.getFrameInfo();
3735 MF.getFunction()->getAttributes().
3736 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3737 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3738 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3739 DstAlignCanChange = true;
3740 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3741 if (Align > SrcAlign)
3744 bool CopyFromStr = isMemSrcFromString(Src, Str);
3745 bool isZeroStr = CopyFromStr && Str.empty();
3746 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3748 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3749 (DstAlignCanChange ? 0 : Align),
3750 (isZeroStr ? 0 : SrcAlign),
3751 false, false, CopyFromStr, true, DAG, TLI))
3754 if (DstAlignCanChange) {
3755 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3756 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3758 // Don't promote to an alignment that would require dynamic stack
3760 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3761 if (!TRI->needsStackRealignment(MF))
3762 while (NewAlign > Align &&
3763 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3766 if (NewAlign > Align) {
3767 // Give the stack frame object a larger alignment if needed.
3768 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3769 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3774 SmallVector<SDValue, 8> OutChains;
3775 unsigned NumMemOps = MemOps.size();
3776 uint64_t SrcOff = 0, DstOff = 0;
3777 for (unsigned i = 0; i != NumMemOps; ++i) {
3779 unsigned VTSize = VT.getSizeInBits() / 8;
3780 SDValue Value, Store;
3782 if (VTSize > Size) {
3783 // Issuing an unaligned load / store pair that overlaps with the previous
3784 // pair. Adjust the offset accordingly.
3785 assert(i == NumMemOps-1 && i != 0);
3786 SrcOff -= VTSize - Size;
3787 DstOff -= VTSize - Size;
3791 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3792 // It's unlikely a store of a vector immediate can be done in a single
3793 // instruction. It would require a load from a constantpool first.
3794 // We only handle zero vectors here.
3795 // FIXME: Handle other cases where store of vector immediate is done in
3796 // a single instruction.
3797 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3798 if (Value.getNode())
3799 Store = DAG.getStore(Chain, dl, Value,
3800 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3801 DstPtrInfo.getWithOffset(DstOff), isVol,
3805 if (!Store.getNode()) {
3806 // The type might not be legal for the target. This should only happen
3807 // if the type is smaller than a legal type, as on PPC, so the right
3808 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3809 // to Load/Store if NVT==VT.
3810 // FIXME does the case above also need this?
3811 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3812 assert(NVT.bitsGE(VT));
3813 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3814 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3815 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3816 MinAlign(SrcAlign, SrcOff));
3817 Store = DAG.getTruncStore(Chain, dl, Value,
3818 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3819 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3822 OutChains.push_back(Store);
3828 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3829 &OutChains[0], OutChains.size());
3832 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3833 SDValue Chain, SDValue Dst,
3834 SDValue Src, uint64_t Size,
3835 unsigned Align, bool isVol,
3837 MachinePointerInfo DstPtrInfo,
3838 MachinePointerInfo SrcPtrInfo) {
3839 // Turn a memmove of undef to nop.
3840 if (Src.getOpcode() == ISD::UNDEF)
3843 // Expand memmove to a series of load and store ops if the size operand falls
3844 // below a certain threshold.
3845 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3846 std::vector<EVT> MemOps;
3847 bool DstAlignCanChange = false;
3848 MachineFunction &MF = DAG.getMachineFunction();
3849 MachineFrameInfo *MFI = MF.getFrameInfo();
3850 bool OptSize = MF.getFunction()->getAttributes().
3851 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3852 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3853 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3854 DstAlignCanChange = true;
3855 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3856 if (Align > SrcAlign)
3858 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3860 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3861 (DstAlignCanChange ? 0 : Align), SrcAlign,
3862 false, false, false, false, DAG, TLI))
3865 if (DstAlignCanChange) {
3866 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3867 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3868 if (NewAlign > Align) {
3869 // Give the stack frame object a larger alignment if needed.
3870 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3871 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3876 uint64_t SrcOff = 0, DstOff = 0;
3877 SmallVector<SDValue, 8> LoadValues;
3878 SmallVector<SDValue, 8> LoadChains;
3879 SmallVector<SDValue, 8> OutChains;
3880 unsigned NumMemOps = MemOps.size();
3881 for (unsigned i = 0; i < NumMemOps; i++) {
3883 unsigned VTSize = VT.getSizeInBits() / 8;
3886 Value = DAG.getLoad(VT, dl, Chain,
3887 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3888 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3889 false, false, SrcAlign);
3890 LoadValues.push_back(Value);
3891 LoadChains.push_back(Value.getValue(1));
3894 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3895 &LoadChains[0], LoadChains.size());
3897 for (unsigned i = 0; i < NumMemOps; i++) {
3899 unsigned VTSize = VT.getSizeInBits() / 8;
3902 Store = DAG.getStore(Chain, dl, LoadValues[i],
3903 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3904 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3905 OutChains.push_back(Store);
3909 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3910 &OutChains[0], OutChains.size());
3913 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3916 /// \param DAG Selection DAG where lowered code is placed.
3917 /// \param dl Link to corresponding IR location.
3918 /// \param Chain Control flow dependency.
3919 /// \param Dst Pointer to destination memory location.
3920 /// \param Src Value of byte to write into the memory.
3921 /// \param Size Number of bytes to write.
3922 /// \param Align Alignment of the destination in bytes.
3923 /// \param isVol True if destination is volatile.
3924 /// \param DstPtrInfo IR information on the memory pointer.
3925 /// \returns New head in the control flow, if lowering was successful, empty
3926 /// SDValue otherwise.
3928 /// The function tries to replace 'llvm.memset' intrinsic with several store
3929 /// operations and value calculation code. This is usually profitable for small
3931 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3932 SDValue Chain, SDValue Dst,
3933 SDValue Src, uint64_t Size,
3934 unsigned Align, bool isVol,
3935 MachinePointerInfo DstPtrInfo) {
3936 // Turn a memset of undef to nop.
3937 if (Src.getOpcode() == ISD::UNDEF)
3940 // Expand memset to a series of load/store ops if the size operand
3941 // falls below a certain threshold.
3942 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3943 std::vector<EVT> MemOps;
3944 bool DstAlignCanChange = false;
3945 MachineFunction &MF = DAG.getMachineFunction();
3946 MachineFrameInfo *MFI = MF.getFrameInfo();
3947 bool OptSize = MF.getFunction()->getAttributes().
3948 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3949 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3950 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3951 DstAlignCanChange = true;
3953 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3954 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3955 Size, (DstAlignCanChange ? 0 : Align), 0,
3956 true, IsZeroVal, false, true, DAG, TLI))
3959 if (DstAlignCanChange) {
3960 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3961 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3962 if (NewAlign > Align) {
3963 // Give the stack frame object a larger alignment if needed.
3964 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3965 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3970 SmallVector<SDValue, 8> OutChains;
3971 uint64_t DstOff = 0;
3972 unsigned NumMemOps = MemOps.size();
3974 // Find the largest store and generate the bit pattern for it.
3975 EVT LargestVT = MemOps[0];
3976 for (unsigned i = 1; i < NumMemOps; i++)
3977 if (MemOps[i].bitsGT(LargestVT))
3978 LargestVT = MemOps[i];
3979 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3981 for (unsigned i = 0; i < NumMemOps; i++) {
3983 unsigned VTSize = VT.getSizeInBits() / 8;
3984 if (VTSize > Size) {
3985 // Issuing an unaligned load / store pair that overlaps with the previous
3986 // pair. Adjust the offset accordingly.
3987 assert(i == NumMemOps-1 && i != 0);
3988 DstOff -= VTSize - Size;
3991 // If this store is smaller than the largest store see whether we can get
3992 // the smaller value for free with a truncate.
3993 SDValue Value = MemSetValue;
3994 if (VT.bitsLT(LargestVT)) {
3995 if (!LargestVT.isVector() && !VT.isVector() &&
3996 TLI.isTruncateFree(LargestVT, VT))
3997 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3999 Value = getMemsetValue(Src, VT, DAG, dl);
4001 assert(Value.getValueType() == VT && "Value with wrong type.");
4002 SDValue Store = DAG.getStore(Chain, dl, Value,
4003 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4004 DstPtrInfo.getWithOffset(DstOff),
4005 isVol, false, Align);
4006 OutChains.push_back(Store);
4007 DstOff += VT.getSizeInBits() / 8;
4011 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4012 &OutChains[0], OutChains.size());
4015 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4016 SDValue Src, SDValue Size,
4017 unsigned Align, bool isVol, bool AlwaysInline,
4018 MachinePointerInfo DstPtrInfo,
4019 MachinePointerInfo SrcPtrInfo) {
4020 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4022 // Check to see if we should lower the memcpy to loads and stores first.
4023 // For cases within the target-specified limits, this is the best choice.
4024 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4026 // Memcpy with size zero? Just return the original chain.
4027 if (ConstantSize->isNullValue())
4030 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4031 ConstantSize->getZExtValue(),Align,
4032 isVol, false, DstPtrInfo, SrcPtrInfo);
4033 if (Result.getNode())
4037 // Then check to see if we should lower the memcpy with target-specific
4038 // code. If the target chooses to do this, this is the next best.
4040 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4041 isVol, AlwaysInline,
4042 DstPtrInfo, SrcPtrInfo);
4043 if (Result.getNode())
4046 // If we really need inline code and the target declined to provide it,
4047 // use a (potentially long) sequence of loads and stores.
4049 assert(ConstantSize && "AlwaysInline requires a constant size!");
4050 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4051 ConstantSize->getZExtValue(), Align, isVol,
4052 true, DstPtrInfo, SrcPtrInfo);
4055 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4056 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4057 // respect volatile, so they may do things like read or write memory
4058 // beyond the given memory regions. But fixing this isn't easy, and most
4059 // people don't care.
4061 const TargetLowering *TLI = TM.getTargetLowering();
4063 // Emit a library call.
4064 TargetLowering::ArgListTy Args;
4065 TargetLowering::ArgListEntry Entry;
4066 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4067 Entry.Node = Dst; Args.push_back(Entry);
4068 Entry.Node = Src; Args.push_back(Entry);
4069 Entry.Node = Size; Args.push_back(Entry);
4070 // FIXME: pass in SDLoc
4072 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4073 false, false, false, false, 0,
4074 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4075 /*isTailCall=*/false,
4076 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4077 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4078 TLI->getPointerTy()),
4080 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4082 return CallResult.second;
4085 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4086 SDValue Src, SDValue Size,
4087 unsigned Align, bool isVol,
4088 MachinePointerInfo DstPtrInfo,
4089 MachinePointerInfo SrcPtrInfo) {
4090 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4092 // Check to see if we should lower the memmove to loads and stores first.
4093 // For cases within the target-specified limits, this is the best choice.
4094 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4096 // Memmove with size zero? Just return the original chain.
4097 if (ConstantSize->isNullValue())
4101 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4102 ConstantSize->getZExtValue(), Align, isVol,
4103 false, DstPtrInfo, SrcPtrInfo);
4104 if (Result.getNode())
4108 // Then check to see if we should lower the memmove with target-specific
4109 // code. If the target chooses to do this, this is the next best.
4111 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4112 DstPtrInfo, SrcPtrInfo);
4113 if (Result.getNode())
4116 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4117 // not be safe. See memcpy above for more details.
4119 const TargetLowering *TLI = TM.getTargetLowering();
4121 // Emit a library call.
4122 TargetLowering::ArgListTy Args;
4123 TargetLowering::ArgListEntry Entry;
4124 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4125 Entry.Node = Dst; Args.push_back(Entry);
4126 Entry.Node = Src; Args.push_back(Entry);
4127 Entry.Node = Size; Args.push_back(Entry);
4128 // FIXME: pass in SDLoc
4130 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4131 false, false, false, false, 0,
4132 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4133 /*isTailCall=*/false,
4134 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4135 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4136 TLI->getPointerTy()),
4138 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4140 return CallResult.second;
4143 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4144 SDValue Src, SDValue Size,
4145 unsigned Align, bool isVol,
4146 MachinePointerInfo DstPtrInfo) {
4147 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4149 // Check to see if we should lower the memset to stores first.
4150 // For cases within the target-specified limits, this is the best choice.
4151 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4153 // Memset with size zero? Just return the original chain.
4154 if (ConstantSize->isNullValue())
4158 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4159 Align, isVol, DstPtrInfo);
4161 if (Result.getNode())
4165 // Then check to see if we should lower the memset with target-specific
4166 // code. If the target chooses to do this, this is the next best.
4168 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4170 if (Result.getNode())
4173 // Emit a library call.
4174 const TargetLowering *TLI = TM.getTargetLowering();
4175 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4176 TargetLowering::ArgListTy Args;
4177 TargetLowering::ArgListEntry Entry;
4178 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4179 Args.push_back(Entry);
4180 // Extend or truncate the argument to be an i32 value for the call.
4181 if (Src.getValueType().bitsGT(MVT::i32))
4182 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4184 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4186 Entry.Ty = Type::getInt32Ty(*getContext());
4187 Entry.isSExt = true;
4188 Args.push_back(Entry);
4190 Entry.Ty = IntPtrTy;
4191 Entry.isSExt = false;
4192 Args.push_back(Entry);
4193 // FIXME: pass in SDLoc
4195 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4196 false, false, false, false, 0,
4197 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4198 /*isTailCall=*/false,
4199 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4200 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4201 TLI->getPointerTy()),
4203 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4205 return CallResult.second;
4208 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4209 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4210 MachineMemOperand *MMO,
4211 AtomicOrdering Ordering,
4212 SynchronizationScope SynchScope) {
4213 FoldingSetNodeID ID;
4214 ID.AddInteger(MemVT.getRawBits());
4215 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4216 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4218 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4219 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4220 return SDValue(E, 0);
4223 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4224 // SDNode doesn't have access to it. This memory will be "leaked" when
4225 // the node is deallocated, but recovered when the allocator is released.
4226 // If the number of operands is less than 5 we use AtomicSDNode's internal
4228 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4230 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4231 dl.getDebugLoc(), VTList, MemVT,
4232 Ops, DynOps, NumOps, MMO,
4233 Ordering, SynchScope);
4234 CSEMap.InsertNode(N, IP);
4235 AllNodes.push_back(N);
4236 return SDValue(N, 0);
4239 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4240 SDValue Chain, SDValue Ptr, SDValue Cmp,
4241 SDValue Swp, MachinePointerInfo PtrInfo,
4243 AtomicOrdering Ordering,
4244 SynchronizationScope SynchScope) {
4245 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4246 Alignment = getEVTAlignment(MemVT);
4248 MachineFunction &MF = getMachineFunction();
4250 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4251 // For now, atomics are considered to be volatile always.
4252 // FIXME: Volatile isn't really correct; we should keep track of atomic
4253 // orderings in the memoperand.
4254 unsigned Flags = MachineMemOperand::MOVolatile;
4255 if (Opcode != ISD::ATOMIC_STORE)
4256 Flags |= MachineMemOperand::MOLoad;
4257 if (Opcode != ISD::ATOMIC_LOAD)
4258 Flags |= MachineMemOperand::MOStore;
4260 MachineMemOperand *MMO =
4261 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4263 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4264 Ordering, SynchScope);
4267 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4269 SDValue Ptr, SDValue Cmp,
4270 SDValue Swp, MachineMemOperand *MMO,
4271 AtomicOrdering Ordering,
4272 SynchronizationScope SynchScope) {
4273 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4274 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4276 EVT VT = Cmp.getValueType();
4278 SDVTList VTs = getVTList(VT, MVT::Other);
4279 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4280 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4283 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4285 SDValue Ptr, SDValue Val,
4286 const Value* PtrVal,
4288 AtomicOrdering Ordering,
4289 SynchronizationScope SynchScope) {
4290 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4291 Alignment = getEVTAlignment(MemVT);
4293 MachineFunction &MF = getMachineFunction();
4294 // An atomic store does not load. An atomic load does not store.
4295 // (An atomicrmw obviously both loads and stores.)
4296 // For now, atomics are considered to be volatile always, and they are
4298 // FIXME: Volatile isn't really correct; we should keep track of atomic
4299 // orderings in the memoperand.
4300 unsigned Flags = MachineMemOperand::MOVolatile;
4301 if (Opcode != ISD::ATOMIC_STORE)
4302 Flags |= MachineMemOperand::MOLoad;
4303 if (Opcode != ISD::ATOMIC_LOAD)
4304 Flags |= MachineMemOperand::MOStore;
4306 MachineMemOperand *MMO =
4307 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4308 MemVT.getStoreSize(), Alignment);
4310 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4311 Ordering, SynchScope);
4314 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4316 SDValue Ptr, SDValue Val,
4317 MachineMemOperand *MMO,
4318 AtomicOrdering Ordering,
4319 SynchronizationScope SynchScope) {
4320 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4321 Opcode == ISD::ATOMIC_LOAD_SUB ||
4322 Opcode == ISD::ATOMIC_LOAD_AND ||
4323 Opcode == ISD::ATOMIC_LOAD_OR ||
4324 Opcode == ISD::ATOMIC_LOAD_XOR ||
4325 Opcode == ISD::ATOMIC_LOAD_NAND ||
4326 Opcode == ISD::ATOMIC_LOAD_MIN ||
4327 Opcode == ISD::ATOMIC_LOAD_MAX ||
4328 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4329 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4330 Opcode == ISD::ATOMIC_SWAP ||
4331 Opcode == ISD::ATOMIC_STORE) &&
4332 "Invalid Atomic Op");
4334 EVT VT = Val.getValueType();
4336 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4337 getVTList(VT, MVT::Other);
4338 SDValue Ops[] = {Chain, Ptr, Val};
4339 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4342 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4343 EVT VT, SDValue Chain,
4345 const Value* PtrVal,
4347 AtomicOrdering Ordering,
4348 SynchronizationScope SynchScope) {
4349 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4350 Alignment = getEVTAlignment(MemVT);
4352 MachineFunction &MF = getMachineFunction();
4353 // An atomic store does not load. An atomic load does not store.
4354 // (An atomicrmw obviously both loads and stores.)
4355 // For now, atomics are considered to be volatile always, and they are
4357 // FIXME: Volatile isn't really correct; we should keep track of atomic
4358 // orderings in the memoperand.
4359 unsigned Flags = MachineMemOperand::MOVolatile;
4360 if (Opcode != ISD::ATOMIC_STORE)
4361 Flags |= MachineMemOperand::MOLoad;
4362 if (Opcode != ISD::ATOMIC_LOAD)
4363 Flags |= MachineMemOperand::MOStore;
4365 MachineMemOperand *MMO =
4366 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4367 MemVT.getStoreSize(), Alignment);
4369 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4370 Ordering, SynchScope);
4373 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4374 EVT VT, SDValue Chain,
4376 MachineMemOperand *MMO,
4377 AtomicOrdering Ordering,
4378 SynchronizationScope SynchScope) {
4379 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4381 SDVTList VTs = getVTList(VT, MVT::Other);
4382 SDValue Ops[] = {Chain, Ptr};
4383 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4386 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4387 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4392 SmallVector<EVT, 4> VTs;
4393 VTs.reserve(NumOps);
4394 for (unsigned i = 0; i < NumOps; ++i)
4395 VTs.push_back(Ops[i].getValueType());
4396 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4401 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4402 const EVT *VTs, unsigned NumVTs,
4403 const SDValue *Ops, unsigned NumOps,
4404 EVT MemVT, MachinePointerInfo PtrInfo,
4405 unsigned Align, bool Vol,
4406 bool ReadMem, bool WriteMem) {
4407 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4408 MemVT, PtrInfo, Align, Vol,
4413 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4414 const SDValue *Ops, unsigned NumOps,
4415 EVT MemVT, MachinePointerInfo PtrInfo,
4416 unsigned Align, bool Vol,
4417 bool ReadMem, bool WriteMem) {
4418 if (Align == 0) // Ensure that codegen never sees alignment 0
4419 Align = getEVTAlignment(MemVT);
4421 MachineFunction &MF = getMachineFunction();
4424 Flags |= MachineMemOperand::MOStore;
4426 Flags |= MachineMemOperand::MOLoad;
4428 Flags |= MachineMemOperand::MOVolatile;
4429 MachineMemOperand *MMO =
4430 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4432 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4436 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4437 const SDValue *Ops, unsigned NumOps,
4438 EVT MemVT, MachineMemOperand *MMO) {
4439 assert((Opcode == ISD::INTRINSIC_VOID ||
4440 Opcode == ISD::INTRINSIC_W_CHAIN ||
4441 Opcode == ISD::PREFETCH ||
4442 Opcode == ISD::LIFETIME_START ||
4443 Opcode == ISD::LIFETIME_END ||
4444 (Opcode <= INT_MAX &&
4445 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4446 "Opcode is not a memory-accessing opcode!");
4448 // Memoize the node unless it returns a flag.
4449 MemIntrinsicSDNode *N;
4450 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4451 FoldingSetNodeID ID;
4452 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4453 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4455 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4456 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4457 return SDValue(E, 0);
4460 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4461 dl.getDebugLoc(), VTList, Ops,
4462 NumOps, MemVT, MMO);
4463 CSEMap.InsertNode(N, IP);
4465 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4466 dl.getDebugLoc(), VTList, Ops,
4467 NumOps, MemVT, MMO);
4469 AllNodes.push_back(N);
4470 return SDValue(N, 0);
4473 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4474 /// MachinePointerInfo record from it. This is particularly useful because the
4475 /// code generator has many cases where it doesn't bother passing in a
4476 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4477 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4478 // If this is FI+Offset, we can model it.
4479 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4480 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4482 // If this is (FI+Offset1)+Offset2, we can model it.
4483 if (Ptr.getOpcode() != ISD::ADD ||
4484 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4485 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4486 return MachinePointerInfo();
4488 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4489 return MachinePointerInfo::getFixedStack(FI, Offset+
4490 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4493 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4494 /// MachinePointerInfo record from it. This is particularly useful because the
4495 /// code generator has many cases where it doesn't bother passing in a
4496 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4497 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4498 // If the 'Offset' value isn't a constant, we can't handle this.
4499 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4500 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4501 if (OffsetOp.getOpcode() == ISD::UNDEF)
4502 return InferPointerInfo(Ptr);
4503 return MachinePointerInfo();
4508 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4509 EVT VT, SDLoc dl, SDValue Chain,
4510 SDValue Ptr, SDValue Offset,
4511 MachinePointerInfo PtrInfo, EVT MemVT,
4512 bool isVolatile, bool isNonTemporal, bool isInvariant,
4513 unsigned Alignment, const MDNode *TBAAInfo,
4514 const MDNode *Ranges) {
4515 assert(Chain.getValueType() == MVT::Other &&
4516 "Invalid chain type");
4517 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4518 Alignment = getEVTAlignment(VT);
4520 unsigned Flags = MachineMemOperand::MOLoad;
4522 Flags |= MachineMemOperand::MOVolatile;
4524 Flags |= MachineMemOperand::MONonTemporal;
4526 Flags |= MachineMemOperand::MOInvariant;
4528 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4531 PtrInfo = InferPointerInfo(Ptr, Offset);
4533 MachineFunction &MF = getMachineFunction();
4534 MachineMemOperand *MMO =
4535 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4537 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4541 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4542 EVT VT, SDLoc dl, SDValue Chain,
4543 SDValue Ptr, SDValue Offset, EVT MemVT,
4544 MachineMemOperand *MMO) {
4546 ExtType = ISD::NON_EXTLOAD;
4547 } else if (ExtType == ISD::NON_EXTLOAD) {
4548 assert(VT == MemVT && "Non-extending load from different memory type!");
4551 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4552 "Should only be an extending load, not truncating!");
4553 assert(VT.isInteger() == MemVT.isInteger() &&
4554 "Cannot convert from FP to Int or Int -> FP!");
4555 assert(VT.isVector() == MemVT.isVector() &&
4556 "Cannot use trunc store to convert to or from a vector!");
4557 assert((!VT.isVector() ||
4558 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4559 "Cannot use trunc store to change the number of vector elements!");
4562 bool Indexed = AM != ISD::UNINDEXED;
4563 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4564 "Unindexed load with an offset!");
4566 SDVTList VTs = Indexed ?
4567 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4568 SDValue Ops[] = { Chain, Ptr, Offset };
4569 FoldingSetNodeID ID;
4570 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4571 ID.AddInteger(MemVT.getRawBits());
4572 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4573 MMO->isNonTemporal(),
4574 MMO->isInvariant()));
4575 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4577 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4578 cast<LoadSDNode>(E)->refineAlignment(MMO);
4579 return SDValue(E, 0);
4581 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4582 dl.getDebugLoc(), VTs, AM, ExtType,
4584 CSEMap.InsertNode(N, IP);
4585 AllNodes.push_back(N);
4586 return SDValue(N, 0);
4589 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4590 SDValue Chain, SDValue Ptr,
4591 MachinePointerInfo PtrInfo,
4592 bool isVolatile, bool isNonTemporal,
4593 bool isInvariant, unsigned Alignment,
4594 const MDNode *TBAAInfo,
4595 const MDNode *Ranges) {
4596 SDValue Undef = getUNDEF(Ptr.getValueType());
4597 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4598 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4602 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4603 SDValue Chain, SDValue Ptr,
4604 MachineMemOperand *MMO) {
4605 SDValue Undef = getUNDEF(Ptr.getValueType());
4606 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4610 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4611 SDValue Chain, SDValue Ptr,
4612 MachinePointerInfo PtrInfo, EVT MemVT,
4613 bool isVolatile, bool isNonTemporal,
4614 unsigned Alignment, const MDNode *TBAAInfo) {
4615 SDValue Undef = getUNDEF(Ptr.getValueType());
4616 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4617 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4622 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4623 SDValue Chain, SDValue Ptr, EVT MemVT,
4624 MachineMemOperand *MMO) {
4625 SDValue Undef = getUNDEF(Ptr.getValueType());
4626 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4631 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4632 SDValue Offset, ISD::MemIndexedMode AM) {
4633 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4634 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4635 "Load is already a indexed load!");
4636 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4637 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4638 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4639 false, LD->getAlignment());
4642 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4643 SDValue Ptr, MachinePointerInfo PtrInfo,
4644 bool isVolatile, bool isNonTemporal,
4645 unsigned Alignment, const MDNode *TBAAInfo) {
4646 assert(Chain.getValueType() == MVT::Other &&
4647 "Invalid chain type");
4648 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4649 Alignment = getEVTAlignment(Val.getValueType());
4651 unsigned Flags = MachineMemOperand::MOStore;
4653 Flags |= MachineMemOperand::MOVolatile;
4655 Flags |= MachineMemOperand::MONonTemporal;
4658 PtrInfo = InferPointerInfo(Ptr);
4660 MachineFunction &MF = getMachineFunction();
4661 MachineMemOperand *MMO =
4662 MF.getMachineMemOperand(PtrInfo, Flags,
4663 Val.getValueType().getStoreSize(), Alignment,
4666 return getStore(Chain, dl, Val, Ptr, MMO);
4669 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4670 SDValue Ptr, MachineMemOperand *MMO) {
4671 assert(Chain.getValueType() == MVT::Other &&
4672 "Invalid chain type");
4673 EVT VT = Val.getValueType();
4674 SDVTList VTs = getVTList(MVT::Other);
4675 SDValue Undef = getUNDEF(Ptr.getValueType());
4676 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4677 FoldingSetNodeID ID;
4678 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4679 ID.AddInteger(VT.getRawBits());
4680 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4681 MMO->isNonTemporal(), MMO->isInvariant()));
4682 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4684 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4685 cast<StoreSDNode>(E)->refineAlignment(MMO);
4686 return SDValue(E, 0);
4688 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4689 dl.getDebugLoc(), VTs,
4690 ISD::UNINDEXED, false, VT, MMO);
4691 CSEMap.InsertNode(N, IP);
4692 AllNodes.push_back(N);
4693 return SDValue(N, 0);
4696 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4697 SDValue Ptr, MachinePointerInfo PtrInfo,
4698 EVT SVT,bool isVolatile, bool isNonTemporal,
4700 const MDNode *TBAAInfo) {
4701 assert(Chain.getValueType() == MVT::Other &&
4702 "Invalid chain type");
4703 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4704 Alignment = getEVTAlignment(SVT);
4706 unsigned Flags = MachineMemOperand::MOStore;
4708 Flags |= MachineMemOperand::MOVolatile;
4710 Flags |= MachineMemOperand::MONonTemporal;
4713 PtrInfo = InferPointerInfo(Ptr);
4715 MachineFunction &MF = getMachineFunction();
4716 MachineMemOperand *MMO =
4717 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4720 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4723 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4724 SDValue Ptr, EVT SVT,
4725 MachineMemOperand *MMO) {
4726 EVT VT = Val.getValueType();
4728 assert(Chain.getValueType() == MVT::Other &&
4729 "Invalid chain type");
4731 return getStore(Chain, dl, Val, Ptr, MMO);
4733 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4734 "Should only be a truncating store, not extending!");
4735 assert(VT.isInteger() == SVT.isInteger() &&
4736 "Can't do FP-INT conversion!");
4737 assert(VT.isVector() == SVT.isVector() &&
4738 "Cannot use trunc store to convert to or from a vector!");
4739 assert((!VT.isVector() ||
4740 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4741 "Cannot use trunc store to change the number of vector elements!");
4743 SDVTList VTs = getVTList(MVT::Other);
4744 SDValue Undef = getUNDEF(Ptr.getValueType());
4745 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4746 FoldingSetNodeID ID;
4747 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4748 ID.AddInteger(SVT.getRawBits());
4749 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4750 MMO->isNonTemporal(), MMO->isInvariant()));
4751 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4753 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4754 cast<StoreSDNode>(E)->refineAlignment(MMO);
4755 return SDValue(E, 0);
4757 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4758 dl.getDebugLoc(), VTs,
4759 ISD::UNINDEXED, true, SVT, MMO);
4760 CSEMap.InsertNode(N, IP);
4761 AllNodes.push_back(N);
4762 return SDValue(N, 0);
4766 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4767 SDValue Offset, ISD::MemIndexedMode AM) {
4768 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4769 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4770 "Store is already a indexed store!");
4771 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4772 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4773 FoldingSetNodeID ID;
4774 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4775 ID.AddInteger(ST->getMemoryVT().getRawBits());
4776 ID.AddInteger(ST->getRawSubclassData());
4777 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4779 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4780 return SDValue(E, 0);
4782 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4783 dl.getDebugLoc(), VTs, AM,
4784 ST->isTruncatingStore(),
4786 ST->getMemOperand());
4787 CSEMap.InsertNode(N, IP);
4788 AllNodes.push_back(N);
4789 return SDValue(N, 0);
4792 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4793 SDValue Chain, SDValue Ptr,
4796 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4797 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4800 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4801 const SDUse *Ops, unsigned NumOps) {
4803 case 0: return getNode(Opcode, DL, VT);
4804 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4805 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4806 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4810 // Copy from an SDUse array into an SDValue array for use with
4811 // the regular getNode logic.
4812 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4813 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4816 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4817 const SDValue *Ops, unsigned NumOps) {
4819 case 0: return getNode(Opcode, DL, VT);
4820 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4821 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4822 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4828 case ISD::SELECT_CC: {
4829 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4830 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4831 "LHS and RHS of condition must have same type!");
4832 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4833 "True and False arms of SelectCC must have same type!");
4834 assert(Ops[2].getValueType() == VT &&
4835 "select_cc node must be of same type as true and false value!");
4839 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4840 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4841 "LHS/RHS of comparison should match types!");
4848 SDVTList VTs = getVTList(VT);
4850 if (VT != MVT::Glue) {
4851 FoldingSetNodeID ID;
4852 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4855 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4856 return SDValue(E, 0);
4858 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4860 CSEMap.InsertNode(N, IP);
4862 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4866 AllNodes.push_back(N);
4870 return SDValue(N, 0);
4873 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4874 ArrayRef<EVT> ResultTys,
4875 const SDValue *Ops, unsigned NumOps) {
4876 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4880 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4881 const EVT *VTs, unsigned NumVTs,
4882 const SDValue *Ops, unsigned NumOps) {
4884 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4885 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4888 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4889 const SDValue *Ops, unsigned NumOps) {
4890 if (VTList.NumVTs == 1)
4891 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4895 // FIXME: figure out how to safely handle things like
4896 // int foo(int x) { return 1 << (x & 255); }
4897 // int bar() { return foo(256); }
4898 case ISD::SRA_PARTS:
4899 case ISD::SRL_PARTS:
4900 case ISD::SHL_PARTS:
4901 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4902 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4903 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4904 else if (N3.getOpcode() == ISD::AND)
4905 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4906 // If the and is only masking out bits that cannot effect the shift,
4907 // eliminate the and.
4908 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4909 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4910 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4916 // Memoize the node unless it returns a flag.
4918 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4919 FoldingSetNodeID ID;
4920 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4922 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4923 return SDValue(E, 0);
4926 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4927 DL.getDebugLoc(), VTList, Ops[0]);
4928 } else if (NumOps == 2) {
4929 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4930 DL.getDebugLoc(), VTList, Ops[0],
4932 } else if (NumOps == 3) {
4933 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4934 DL.getDebugLoc(), VTList, Ops[0],
4937 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4938 VTList, Ops, NumOps);
4940 CSEMap.InsertNode(N, IP);
4943 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4944 DL.getDebugLoc(), VTList, Ops[0]);
4945 } else if (NumOps == 2) {
4946 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4947 DL.getDebugLoc(), VTList, Ops[0],
4949 } else if (NumOps == 3) {
4950 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4951 DL.getDebugLoc(), VTList, Ops[0],
4954 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4955 VTList, Ops, NumOps);
4958 AllNodes.push_back(N);
4962 return SDValue(N, 0);
4965 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4966 return getNode(Opcode, DL, VTList, 0, 0);
4969 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4971 SDValue Ops[] = { N1 };
4972 return getNode(Opcode, DL, VTList, Ops, 1);
4975 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4976 SDValue N1, SDValue N2) {
4977 SDValue Ops[] = { N1, N2 };
4978 return getNode(Opcode, DL, VTList, Ops, 2);
4981 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4982 SDValue N1, SDValue N2, SDValue N3) {
4983 SDValue Ops[] = { N1, N2, N3 };
4984 return getNode(Opcode, DL, VTList, Ops, 3);
4987 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4988 SDValue N1, SDValue N2, SDValue N3,
4990 SDValue Ops[] = { N1, N2, N3, N4 };
4991 return getNode(Opcode, DL, VTList, Ops, 4);
4994 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4995 SDValue N1, SDValue N2, SDValue N3,
4996 SDValue N4, SDValue N5) {
4997 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4998 return getNode(Opcode, DL, VTList, Ops, 5);
5001 SDVTList SelectionDAG::getVTList(EVT VT) {
5002 return makeVTList(SDNode::getValueTypeList(VT), 1);
5005 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5006 FoldingSetNodeID ID;
5008 ID.AddInteger(VT1.getRawBits());
5009 ID.AddInteger(VT2.getRawBits());
5012 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5013 if (Result == NULL) {
5014 EVT *Array = Allocator.Allocate<EVT>(2);
5017 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5018 VTListMap.InsertNode(Result, IP);
5020 return Result->getSDVTList();
5023 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5024 FoldingSetNodeID ID;
5026 ID.AddInteger(VT1.getRawBits());
5027 ID.AddInteger(VT2.getRawBits());
5028 ID.AddInteger(VT3.getRawBits());
5031 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5032 if (Result == NULL) {
5033 EVT *Array = Allocator.Allocate<EVT>(3);
5037 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5038 VTListMap.InsertNode(Result, IP);
5040 return Result->getSDVTList();
5043 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5044 FoldingSetNodeID ID;
5046 ID.AddInteger(VT1.getRawBits());
5047 ID.AddInteger(VT2.getRawBits());
5048 ID.AddInteger(VT3.getRawBits());
5049 ID.AddInteger(VT4.getRawBits());
5052 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5053 if (Result == NULL) {
5054 EVT *Array = Allocator.Allocate<EVT>(4);
5059 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5060 VTListMap.InsertNode(Result, IP);
5062 return Result->getSDVTList();
5065 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5066 FoldingSetNodeID ID;
5067 ID.AddInteger(NumVTs);
5068 for (unsigned index = 0; index < NumVTs; index++) {
5069 ID.AddInteger(VTs[index].getRawBits());
5073 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5074 if (Result == NULL) {
5075 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5076 std::copy(VTs, VTs + NumVTs, Array);
5077 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5078 VTListMap.InsertNode(Result, IP);
5080 return Result->getSDVTList();
5084 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5085 /// specified operands. If the resultant node already exists in the DAG,
5086 /// this does not modify the specified node, instead it returns the node that
5087 /// already exists. If the resultant node does not exist in the DAG, the
5088 /// input node is returned. As a degenerate case, if you specify the same
5089 /// input operands as the node already has, the input node is returned.
5090 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5091 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5093 // Check to see if there is no change.
5094 if (Op == N->getOperand(0)) return N;
5096 // See if the modified node already exists.
5097 void *InsertPos = 0;
5098 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5101 // Nope it doesn't. Remove the node from its current place in the maps.
5103 if (!RemoveNodeFromCSEMaps(N))
5106 // Now we update the operands.
5107 N->OperandList[0].set(Op);
5109 // If this gets put into a CSE map, add it.
5110 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5114 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5115 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5117 // Check to see if there is no change.
5118 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5119 return N; // No operands changed, just return the input node.
5121 // See if the modified node already exists.
5122 void *InsertPos = 0;
5123 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5126 // Nope it doesn't. Remove the node from its current place in the maps.
5128 if (!RemoveNodeFromCSEMaps(N))
5131 // Now we update the operands.
5132 if (N->OperandList[0] != Op1)
5133 N->OperandList[0].set(Op1);
5134 if (N->OperandList[1] != Op2)
5135 N->OperandList[1].set(Op2);
5137 // If this gets put into a CSE map, add it.
5138 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5142 SDNode *SelectionDAG::
5143 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5144 SDValue Ops[] = { Op1, Op2, Op3 };
5145 return UpdateNodeOperands(N, Ops, 3);
5148 SDNode *SelectionDAG::
5149 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5150 SDValue Op3, SDValue Op4) {
5151 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5152 return UpdateNodeOperands(N, Ops, 4);
5155 SDNode *SelectionDAG::
5156 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5157 SDValue Op3, SDValue Op4, SDValue Op5) {
5158 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5159 return UpdateNodeOperands(N, Ops, 5);
5162 SDNode *SelectionDAG::
5163 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5164 assert(N->getNumOperands() == NumOps &&
5165 "Update with wrong number of operands");
5167 // Check to see if there is no change.
5168 bool AnyChange = false;
5169 for (unsigned i = 0; i != NumOps; ++i) {
5170 if (Ops[i] != N->getOperand(i)) {
5176 // No operands changed, just return the input node.
5177 if (!AnyChange) return N;
5179 // See if the modified node already exists.
5180 void *InsertPos = 0;
5181 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5184 // Nope it doesn't. Remove the node from its current place in the maps.
5186 if (!RemoveNodeFromCSEMaps(N))
5189 // Now we update the operands.
5190 for (unsigned i = 0; i != NumOps; ++i)
5191 if (N->OperandList[i] != Ops[i])
5192 N->OperandList[i].set(Ops[i]);
5194 // If this gets put into a CSE map, add it.
5195 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5199 /// DropOperands - Release the operands and set this node to have
5201 void SDNode::DropOperands() {
5202 // Unlike the code in MorphNodeTo that does this, we don't need to
5203 // watch for dead nodes here.
5204 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5210 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5213 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5215 SDVTList VTs = getVTList(VT);
5216 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5219 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5220 EVT VT, SDValue Op1) {
5221 SDVTList VTs = getVTList(VT);
5222 SDValue Ops[] = { Op1 };
5223 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5226 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5227 EVT VT, SDValue Op1,
5229 SDVTList VTs = getVTList(VT);
5230 SDValue Ops[] = { Op1, Op2 };
5231 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5234 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5235 EVT VT, SDValue Op1,
5236 SDValue Op2, SDValue Op3) {
5237 SDVTList VTs = getVTList(VT);
5238 SDValue Ops[] = { Op1, Op2, Op3 };
5239 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5242 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5243 EVT VT, const SDValue *Ops,
5245 SDVTList VTs = getVTList(VT);
5246 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5249 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5250 EVT VT1, EVT VT2, const SDValue *Ops,
5252 SDVTList VTs = getVTList(VT1, VT2);
5253 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5256 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 SDVTList VTs = getVTList(VT1, VT2);
5259 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5262 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5263 EVT VT1, EVT VT2, EVT VT3,
5264 const SDValue *Ops, unsigned NumOps) {
5265 SDVTList VTs = getVTList(VT1, VT2, VT3);
5266 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5271 const SDValue *Ops, unsigned NumOps) {
5272 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5273 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5276 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5279 SDVTList VTs = getVTList(VT1, VT2);
5280 SDValue Ops[] = { Op1 };
5281 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5284 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 SDValue Op1, SDValue Op2) {
5287 SDVTList VTs = getVTList(VT1, VT2);
5288 SDValue Ops[] = { Op1, Op2 };
5289 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5294 SDValue Op1, SDValue Op2,
5296 SDVTList VTs = getVTList(VT1, VT2);
5297 SDValue Ops[] = { Op1, Op2, Op3 };
5298 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5301 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 EVT VT1, EVT VT2, EVT VT3,
5303 SDValue Op1, SDValue Op2,
5305 SDVTList VTs = getVTList(VT1, VT2, VT3);
5306 SDValue Ops[] = { Op1, Op2, Op3 };
5307 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5310 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5311 SDVTList VTs, const SDValue *Ops,
5313 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5314 // Reset the NodeID to -1.
5319 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5320 /// the line number information on the merged node since it is not possible to
5321 /// preserve the information that operation is associated with multiple lines.
5322 /// This will make the debugger working better at -O0, were there is a higher
5323 /// probability having other instructions associated with that line.
5325 /// For IROrder, we keep the smaller of the two
5326 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5327 DebugLoc NLoc = N->getDebugLoc();
5328 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5329 (OLoc.getDebugLoc() != NLoc)) {
5330 N->setDebugLoc(DebugLoc());
5332 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5333 N->setIROrder(Order);
5337 /// MorphNodeTo - This *mutates* the specified node to have the specified
5338 /// return type, opcode, and operands.
5340 /// Note that MorphNodeTo returns the resultant node. If there is already a
5341 /// node of the specified opcode and operands, it returns that node instead of
5342 /// the current one. Note that the SDLoc need not be the same.
5344 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5345 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5346 /// node, and because it doesn't require CSE recalculation for any of
5347 /// the node's users.
5349 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5350 SDVTList VTs, const SDValue *Ops,
5352 // If an identical node already exists, use it.
5354 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5355 FoldingSetNodeID ID;
5356 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5357 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5358 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5361 if (!RemoveNodeFromCSEMaps(N))
5364 // Start the morphing.
5366 N->ValueList = VTs.VTs;
5367 N->NumValues = VTs.NumVTs;
5369 // Clear the operands list, updating used nodes to remove this from their
5370 // use list. Keep track of any operands that become dead as a result.
5371 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5372 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5374 SDNode *Used = Use.getNode();
5376 if (Used->use_empty())
5377 DeadNodeSet.insert(Used);
5380 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5381 // Initialize the memory references information.
5382 MN->setMemRefs(0, 0);
5383 // If NumOps is larger than the # of operands we can have in a
5384 // MachineSDNode, reallocate the operand list.
5385 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5386 if (MN->OperandsNeedDelete)
5387 delete[] MN->OperandList;
5388 if (NumOps > array_lengthof(MN->LocalOperands))
5389 // We're creating a final node that will live unmorphed for the
5390 // remainder of the current SelectionDAG iteration, so we can allocate
5391 // the operands directly out of a pool with no recycling metadata.
5392 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5395 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5396 MN->OperandsNeedDelete = false;
5398 MN->InitOperands(MN->OperandList, Ops, NumOps);
5400 // If NumOps is larger than the # of operands we currently have, reallocate
5401 // the operand list.
5402 if (NumOps > N->NumOperands) {
5403 if (N->OperandsNeedDelete)
5404 delete[] N->OperandList;
5405 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5406 N->OperandsNeedDelete = true;
5408 N->InitOperands(N->OperandList, Ops, NumOps);
5411 // Delete any nodes that are still dead after adding the uses for the
5413 if (!DeadNodeSet.empty()) {
5414 SmallVector<SDNode *, 16> DeadNodes;
5415 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5416 E = DeadNodeSet.end(); I != E; ++I)
5417 if ((*I)->use_empty())
5418 DeadNodes.push_back(*I);
5419 RemoveDeadNodes(DeadNodes);
5423 CSEMap.InsertNode(N, IP); // Memoize the new node.
5428 /// getMachineNode - These are used for target selectors to create a new node
5429 /// with specified return type(s), MachineInstr opcode, and operands.
5431 /// Note that getMachineNode returns the resultant node. If there is already a
5432 /// node of the specified opcode and operands, it returns that node instead of
5433 /// the current one.
5435 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5436 SDVTList VTs = getVTList(VT);
5437 return getMachineNode(Opcode, dl, VTs, None);
5441 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5442 SDVTList VTs = getVTList(VT);
5443 SDValue Ops[] = { Op1 };
5444 return getMachineNode(Opcode, dl, VTs, Ops);
5448 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5449 SDValue Op1, SDValue Op2) {
5450 SDVTList VTs = getVTList(VT);
5451 SDValue Ops[] = { Op1, Op2 };
5452 return getMachineNode(Opcode, dl, VTs, Ops);
5456 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5457 SDValue Op1, SDValue Op2, SDValue Op3) {
5458 SDVTList VTs = getVTList(VT);
5459 SDValue Ops[] = { Op1, Op2, Op3 };
5460 return getMachineNode(Opcode, dl, VTs, Ops);
5464 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5465 ArrayRef<SDValue> Ops) {
5466 SDVTList VTs = getVTList(VT);
5467 return getMachineNode(Opcode, dl, VTs, Ops);
5471 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5472 SDVTList VTs = getVTList(VT1, VT2);
5473 return getMachineNode(Opcode, dl, VTs, None);
5477 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5478 EVT VT1, EVT VT2, SDValue Op1) {
5479 SDVTList VTs = getVTList(VT1, VT2);
5480 SDValue Ops[] = { Op1 };
5481 return getMachineNode(Opcode, dl, VTs, Ops);
5485 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5486 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5487 SDVTList VTs = getVTList(VT1, VT2);
5488 SDValue Ops[] = { Op1, Op2 };
5489 return getMachineNode(Opcode, dl, VTs, Ops);
5493 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5494 EVT VT1, EVT VT2, SDValue Op1,
5495 SDValue Op2, SDValue Op3) {
5496 SDVTList VTs = getVTList(VT1, VT2);
5497 SDValue Ops[] = { Op1, Op2, Op3 };
5498 return getMachineNode(Opcode, dl, VTs, Ops);
5502 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5504 ArrayRef<SDValue> Ops) {
5505 SDVTList VTs = getVTList(VT1, VT2);
5506 return getMachineNode(Opcode, dl, VTs, Ops);
5510 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5511 EVT VT1, EVT VT2, EVT VT3,
5512 SDValue Op1, SDValue Op2) {
5513 SDVTList VTs = getVTList(VT1, VT2, VT3);
5514 SDValue Ops[] = { Op1, Op2 };
5515 return getMachineNode(Opcode, dl, VTs, Ops);
5519 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5520 EVT VT1, EVT VT2, EVT VT3,
5521 SDValue Op1, SDValue Op2, SDValue Op3) {
5522 SDVTList VTs = getVTList(VT1, VT2, VT3);
5523 SDValue Ops[] = { Op1, Op2, Op3 };
5524 return getMachineNode(Opcode, dl, VTs, Ops);
5528 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5529 EVT VT1, EVT VT2, EVT VT3,
5530 ArrayRef<SDValue> Ops) {
5531 SDVTList VTs = getVTList(VT1, VT2, VT3);
5532 return getMachineNode(Opcode, dl, VTs, Ops);
5536 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5537 EVT VT2, EVT VT3, EVT VT4,
5538 ArrayRef<SDValue> Ops) {
5539 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5540 return getMachineNode(Opcode, dl, VTs, Ops);
5544 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5545 ArrayRef<EVT> ResultTys,
5546 ArrayRef<SDValue> Ops) {
5547 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5548 return getMachineNode(Opcode, dl, VTs, Ops);
5552 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5553 ArrayRef<SDValue> OpsArray) {
5554 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5557 const SDValue *Ops = OpsArray.data();
5558 unsigned NumOps = OpsArray.size();
5561 FoldingSetNodeID ID;
5562 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5564 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5565 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5569 // Allocate a new MachineSDNode.
5570 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5571 DL.getDebugLoc(), VTs);
5573 // Initialize the operands list.
5574 if (NumOps > array_lengthof(N->LocalOperands))
5575 // We're creating a final node that will live unmorphed for the
5576 // remainder of the current SelectionDAG iteration, so we can allocate
5577 // the operands directly out of a pool with no recycling metadata.
5578 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5581 N->InitOperands(N->LocalOperands, Ops, NumOps);
5582 N->OperandsNeedDelete = false;
5585 CSEMap.InsertNode(N, IP);
5587 AllNodes.push_back(N);
5589 VerifyMachineNode(N);
5594 /// getTargetExtractSubreg - A convenience function for creating
5595 /// TargetOpcode::EXTRACT_SUBREG nodes.
5597 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5599 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5600 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5601 VT, Operand, SRIdxVal);
5602 return SDValue(Subreg, 0);
5605 /// getTargetInsertSubreg - A convenience function for creating
5606 /// TargetOpcode::INSERT_SUBREG nodes.
5608 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5609 SDValue Operand, SDValue Subreg) {
5610 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5611 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5612 VT, Operand, Subreg, SRIdxVal);
5613 return SDValue(Result, 0);
5616 /// getNodeIfExists - Get the specified node if it's already available, or
5617 /// else return NULL.
5618 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5619 const SDValue *Ops, unsigned NumOps) {
5620 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5621 FoldingSetNodeID ID;
5622 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5624 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5630 /// getDbgValue - Creates a SDDbgValue node.
5633 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5634 DebugLoc DL, unsigned O) {
5635 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5639 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5640 DebugLoc DL, unsigned O) {
5641 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5645 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5646 DebugLoc DL, unsigned O) {
5647 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5652 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5653 /// pointed to by a use iterator is deleted, increment the use iterator
5654 /// so that it doesn't dangle.
5656 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5657 SDNode::use_iterator &UI;
5658 SDNode::use_iterator &UE;
5660 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5661 // Increment the iterator as needed.
5662 while (UI != UE && N == *UI)
5667 RAUWUpdateListener(SelectionDAG &d,
5668 SDNode::use_iterator &ui,
5669 SDNode::use_iterator &ue)
5670 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5675 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5676 /// This can cause recursive merging of nodes in the DAG.
5678 /// This version assumes From has a single result value.
5680 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5681 SDNode *From = FromN.getNode();
5682 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5683 "Cannot replace with this method!");
5684 assert(From != To.getNode() && "Cannot replace uses of with self");
5686 // Iterate over all the existing uses of From. New uses will be added
5687 // to the beginning of the use list, which we avoid visiting.
5688 // This specifically avoids visiting uses of From that arise while the
5689 // replacement is happening, because any such uses would be the result
5690 // of CSE: If an existing node looks like From after one of its operands
5691 // is replaced by To, we don't want to replace of all its users with To
5692 // too. See PR3018 for more info.
5693 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5694 RAUWUpdateListener Listener(*this, UI, UE);
5698 // This node is about to morph, remove its old self from the CSE maps.
5699 RemoveNodeFromCSEMaps(User);
5701 // A user can appear in a use list multiple times, and when this
5702 // happens the uses are usually next to each other in the list.
5703 // To help reduce the number of CSE recomputations, process all
5704 // the uses of this user that we can find this way.
5706 SDUse &Use = UI.getUse();
5709 } while (UI != UE && *UI == User);
5711 // Now that we have modified User, add it back to the CSE maps. If it
5712 // already exists there, recursively merge the results together.
5713 AddModifiedNodeToCSEMaps(User);
5716 // If we just RAUW'd the root, take note.
5717 if (FromN == getRoot())
5721 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5722 /// This can cause recursive merging of nodes in the DAG.
5724 /// This version assumes that for each value of From, there is a
5725 /// corresponding value in To in the same position with the same type.
5727 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5729 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5730 assert((!From->hasAnyUseOfValue(i) ||
5731 From->getValueType(i) == To->getValueType(i)) &&
5732 "Cannot use this version of ReplaceAllUsesWith!");
5735 // Handle the trivial case.
5739 // Iterate over just the existing users of From. See the comments in
5740 // the ReplaceAllUsesWith above.
5741 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5742 RAUWUpdateListener Listener(*this, UI, UE);
5746 // This node is about to morph, remove its old self from the CSE maps.
5747 RemoveNodeFromCSEMaps(User);
5749 // A user can appear in a use list multiple times, and when this
5750 // happens the uses are usually next to each other in the list.
5751 // To help reduce the number of CSE recomputations, process all
5752 // the uses of this user that we can find this way.
5754 SDUse &Use = UI.getUse();
5757 } while (UI != UE && *UI == User);
5759 // Now that we have modified User, add it back to the CSE maps. If it
5760 // already exists there, recursively merge the results together.
5761 AddModifiedNodeToCSEMaps(User);
5764 // If we just RAUW'd the root, take note.
5765 if (From == getRoot().getNode())
5766 setRoot(SDValue(To, getRoot().getResNo()));
5769 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5770 /// This can cause recursive merging of nodes in the DAG.
5772 /// This version can replace From with any result values. To must match the
5773 /// number and types of values returned by From.
5774 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5775 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5776 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5778 // Iterate over just the existing users of From. See the comments in
5779 // the ReplaceAllUsesWith above.
5780 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5781 RAUWUpdateListener Listener(*this, UI, UE);
5785 // This node is about to morph, remove its old self from the CSE maps.
5786 RemoveNodeFromCSEMaps(User);
5788 // A user can appear in a use list multiple times, and when this
5789 // happens the uses are usually next to each other in the list.
5790 // To help reduce the number of CSE recomputations, process all
5791 // the uses of this user that we can find this way.
5793 SDUse &Use = UI.getUse();
5794 const SDValue &ToOp = To[Use.getResNo()];
5797 } while (UI != UE && *UI == User);
5799 // Now that we have modified User, add it back to the CSE maps. If it
5800 // already exists there, recursively merge the results together.
5801 AddModifiedNodeToCSEMaps(User);
5804 // If we just RAUW'd the root, take note.
5805 if (From == getRoot().getNode())
5806 setRoot(SDValue(To[getRoot().getResNo()]));
5809 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5810 /// uses of other values produced by From.getNode() alone. The Deleted
5811 /// vector is handled the same way as for ReplaceAllUsesWith.
5812 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5813 // Handle the really simple, really trivial case efficiently.
5814 if (From == To) return;
5816 // Handle the simple, trivial, case efficiently.
5817 if (From.getNode()->getNumValues() == 1) {
5818 ReplaceAllUsesWith(From, To);
5822 // Iterate over just the existing users of From. See the comments in
5823 // the ReplaceAllUsesWith above.
5824 SDNode::use_iterator UI = From.getNode()->use_begin(),
5825 UE = From.getNode()->use_end();
5826 RAUWUpdateListener Listener(*this, UI, UE);
5829 bool UserRemovedFromCSEMaps = false;
5831 // A user can appear in a use list multiple times, and when this
5832 // happens the uses are usually next to each other in the list.
5833 // To help reduce the number of CSE recomputations, process all
5834 // the uses of this user that we can find this way.
5836 SDUse &Use = UI.getUse();
5838 // Skip uses of different values from the same node.
5839 if (Use.getResNo() != From.getResNo()) {
5844 // If this node hasn't been modified yet, it's still in the CSE maps,
5845 // so remove its old self from the CSE maps.
5846 if (!UserRemovedFromCSEMaps) {
5847 RemoveNodeFromCSEMaps(User);
5848 UserRemovedFromCSEMaps = true;
5853 } while (UI != UE && *UI == User);
5855 // We are iterating over all uses of the From node, so if a use
5856 // doesn't use the specific value, no changes are made.
5857 if (!UserRemovedFromCSEMaps)
5860 // Now that we have modified User, add it back to the CSE maps. If it
5861 // already exists there, recursively merge the results together.
5862 AddModifiedNodeToCSEMaps(User);
5865 // If we just RAUW'd the root, take note.
5866 if (From == getRoot())
5871 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5872 /// to record information about a use.
5879 /// operator< - Sort Memos by User.
5880 bool operator<(const UseMemo &L, const UseMemo &R) {
5881 return (intptr_t)L.User < (intptr_t)R.User;
5885 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5886 /// uses of other values produced by From.getNode() alone. The same value
5887 /// may appear in both the From and To list. The Deleted vector is
5888 /// handled the same way as for ReplaceAllUsesWith.
5889 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5892 // Handle the simple, trivial case efficiently.
5894 return ReplaceAllUsesOfValueWith(*From, *To);
5896 // Read up all the uses and make records of them. This helps
5897 // processing new uses that are introduced during the
5898 // replacement process.
5899 SmallVector<UseMemo, 4> Uses;
5900 for (unsigned i = 0; i != Num; ++i) {
5901 unsigned FromResNo = From[i].getResNo();
5902 SDNode *FromNode = From[i].getNode();
5903 for (SDNode::use_iterator UI = FromNode->use_begin(),
5904 E = FromNode->use_end(); UI != E; ++UI) {
5905 SDUse &Use = UI.getUse();
5906 if (Use.getResNo() == FromResNo) {
5907 UseMemo Memo = { *UI, i, &Use };
5908 Uses.push_back(Memo);
5913 // Sort the uses, so that all the uses from a given User are together.
5914 std::sort(Uses.begin(), Uses.end());
5916 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5917 UseIndex != UseIndexEnd; ) {
5918 // We know that this user uses some value of From. If it is the right
5919 // value, update it.
5920 SDNode *User = Uses[UseIndex].User;
5922 // This node is about to morph, remove its old self from the CSE maps.
5923 RemoveNodeFromCSEMaps(User);
5925 // The Uses array is sorted, so all the uses for a given User
5926 // are next to each other in the list.
5927 // To help reduce the number of CSE recomputations, process all
5928 // the uses of this user that we can find this way.
5930 unsigned i = Uses[UseIndex].Index;
5931 SDUse &Use = *Uses[UseIndex].Use;
5935 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5937 // Now that we have modified User, add it back to the CSE maps. If it
5938 // already exists there, recursively merge the results together.
5939 AddModifiedNodeToCSEMaps(User);
5943 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5944 /// based on their topological order. It returns the maximum id and a vector
5945 /// of the SDNodes* in assigned order by reference.
5946 unsigned SelectionDAG::AssignTopologicalOrder() {
5948 unsigned DAGSize = 0;
5950 // SortedPos tracks the progress of the algorithm. Nodes before it are
5951 // sorted, nodes after it are unsorted. When the algorithm completes
5952 // it is at the end of the list.
5953 allnodes_iterator SortedPos = allnodes_begin();
5955 // Visit all the nodes. Move nodes with no operands to the front of
5956 // the list immediately. Annotate nodes that do have operands with their
5957 // operand count. Before we do this, the Node Id fields of the nodes
5958 // may contain arbitrary values. After, the Node Id fields for nodes
5959 // before SortedPos will contain the topological sort index, and the
5960 // Node Id fields for nodes At SortedPos and after will contain the
5961 // count of outstanding operands.
5962 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5965 unsigned Degree = N->getNumOperands();
5967 // A node with no uses, add it to the result array immediately.
5968 N->setNodeId(DAGSize++);
5969 allnodes_iterator Q = N;
5971 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5972 assert(SortedPos != AllNodes.end() && "Overran node list");
5975 // Temporarily use the Node Id as scratch space for the degree count.
5976 N->setNodeId(Degree);
5980 // Visit all the nodes. As we iterate, move nodes into sorted order,
5981 // such that by the time the end is reached all nodes will be sorted.
5982 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5985 // N is in sorted position, so all its uses have one less operand
5986 // that needs to be sorted.
5987 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5990 unsigned Degree = P->getNodeId();
5991 assert(Degree != 0 && "Invalid node degree");
5994 // All of P's operands are sorted, so P may sorted now.
5995 P->setNodeId(DAGSize++);
5997 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5998 assert(SortedPos != AllNodes.end() && "Overran node list");
6001 // Update P's outstanding operand count.
6002 P->setNodeId(Degree);
6005 if (I == SortedPos) {
6008 dbgs() << "Overran sorted position:\n";
6011 llvm_unreachable(0);
6015 assert(SortedPos == AllNodes.end() &&
6016 "Topological sort incomplete!");
6017 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6018 "First node in topological sort is not the entry token!");
6019 assert(AllNodes.front().getNodeId() == 0 &&
6020 "First node in topological sort has non-zero id!");
6021 assert(AllNodes.front().getNumOperands() == 0 &&
6022 "First node in topological sort has operands!");
6023 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6024 "Last node in topologic sort has unexpected id!");
6025 assert(AllNodes.back().use_empty() &&
6026 "Last node in topologic sort has users!");
6027 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6031 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6032 /// value is produced by SD.
6033 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6034 DbgInfo->add(DB, SD, isParameter);
6036 SD->setHasDebugValue(true);
6039 /// TransferDbgValues - Transfer SDDbgValues.
6040 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6041 if (From == To || !From.getNode()->getHasDebugValue())
6043 SDNode *FromNode = From.getNode();
6044 SDNode *ToNode = To.getNode();
6045 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6046 SmallVector<SDDbgValue *, 2> ClonedDVs;
6047 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6049 SDDbgValue *Dbg = *I;
6050 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6051 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6052 Dbg->getOffset(), Dbg->getDebugLoc(),
6054 ClonedDVs.push_back(Clone);
6057 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6058 E = ClonedDVs.end(); I != E; ++I)
6059 AddDbgValue(*I, ToNode, false);
6062 //===----------------------------------------------------------------------===//
6064 //===----------------------------------------------------------------------===//
6066 HandleSDNode::~HandleSDNode() {
6070 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6071 DebugLoc DL, const GlobalValue *GA,
6072 EVT VT, int64_t o, unsigned char TF)
6073 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6077 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6078 SDValue X, unsigned SrcAS,
6080 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6081 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6083 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6084 EVT memvt, MachineMemOperand *mmo)
6085 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6086 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6087 MMO->isNonTemporal(), MMO->isInvariant());
6088 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6089 assert(isNonTemporal() == MMO->isNonTemporal() &&
6090 "Non-temporal encoding error!");
6091 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6094 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6095 const SDValue *Ops, unsigned NumOps, EVT memvt,
6096 MachineMemOperand *mmo)
6097 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6098 MemoryVT(memvt), MMO(mmo) {
6099 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6100 MMO->isNonTemporal(), MMO->isInvariant());
6101 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6102 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6105 /// Profile - Gather unique data for the node.
6107 void SDNode::Profile(FoldingSetNodeID &ID) const {
6108 AddNodeIDNode(ID, this);
6113 std::vector<EVT> VTs;
6116 VTs.reserve(MVT::LAST_VALUETYPE);
6117 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6118 VTs.push_back(MVT((MVT::SimpleValueType)i));
6123 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6124 static ManagedStatic<EVTArray> SimpleVTArray;
6125 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6127 /// getValueTypeList - Return a pointer to the specified value type.
6129 const EVT *SDNode::getValueTypeList(EVT VT) {
6130 if (VT.isExtended()) {
6131 sys::SmartScopedLock<true> Lock(*VTMutex);
6132 return &(*EVTs->insert(VT).first);
6134 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6135 "Value type out of range!");
6136 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6140 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6141 /// indicated value. This method ignores uses of other values defined by this
6143 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6144 assert(Value < getNumValues() && "Bad value!");
6146 // TODO: Only iterate over uses of a given value of the node
6147 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6148 if (UI.getUse().getResNo() == Value) {
6155 // Found exactly the right number of uses?
6160 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6161 /// value. This method ignores uses of other values defined by this operation.
6162 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6163 assert(Value < getNumValues() && "Bad value!");
6165 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6166 if (UI.getUse().getResNo() == Value)
6173 /// isOnlyUserOf - Return true if this node is the only use of N.
6175 bool SDNode::isOnlyUserOf(SDNode *N) const {
6177 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6188 /// isOperand - Return true if this node is an operand of N.
6190 bool SDValue::isOperandOf(SDNode *N) const {
6191 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6192 if (*this == N->getOperand(i))
6197 bool SDNode::isOperandOf(SDNode *N) const {
6198 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6199 if (this == N->OperandList[i].getNode())
6204 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6205 /// be a chain) reaches the specified operand without crossing any
6206 /// side-effecting instructions on any chain path. In practice, this looks
6207 /// through token factors and non-volatile loads. In order to remain efficient,
6208 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6209 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6210 unsigned Depth) const {
6211 if (*this == Dest) return true;
6213 // Don't search too deeply, we just want to be able to see through
6214 // TokenFactor's etc.
6215 if (Depth == 0) return false;
6217 // If this is a token factor, all inputs to the TF happen in parallel. If any
6218 // of the operands of the TF does not reach dest, then we cannot do the xform.
6219 if (getOpcode() == ISD::TokenFactor) {
6220 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6221 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6226 // Loads don't have side effects, look through them.
6227 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6228 if (!Ld->isVolatile())
6229 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6234 /// hasPredecessor - Return true if N is a predecessor of this node.
6235 /// N is either an operand of this node, or can be reached by recursively
6236 /// traversing up the operands.
6237 /// NOTE: This is an expensive method. Use it carefully.
6238 bool SDNode::hasPredecessor(const SDNode *N) const {
6239 SmallPtrSet<const SDNode *, 32> Visited;
6240 SmallVector<const SDNode *, 16> Worklist;
6241 return hasPredecessorHelper(N, Visited, Worklist);
6245 SDNode::hasPredecessorHelper(const SDNode *N,
6246 SmallPtrSet<const SDNode *, 32> &Visited,
6247 SmallVectorImpl<const SDNode *> &Worklist) const {
6248 if (Visited.empty()) {
6249 Worklist.push_back(this);
6251 // Take a look in the visited set. If we've already encountered this node
6252 // we needn't search further.
6253 if (Visited.count(N))
6257 // Haven't visited N yet. Continue the search.
6258 while (!Worklist.empty()) {
6259 const SDNode *M = Worklist.pop_back_val();
6260 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6261 SDNode *Op = M->getOperand(i).getNode();
6262 if (Visited.insert(Op))
6263 Worklist.push_back(Op);
6272 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6273 assert(Num < NumOperands && "Invalid child # of SDNode!");
6274 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6277 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6278 assert(N->getNumValues() == 1 &&
6279 "Can't unroll a vector with multiple results!");
6281 EVT VT = N->getValueType(0);
6282 unsigned NE = VT.getVectorNumElements();
6283 EVT EltVT = VT.getVectorElementType();
6286 SmallVector<SDValue, 8> Scalars;
6287 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6289 // If ResNE is 0, fully unroll the vector op.
6292 else if (NE > ResNE)
6296 for (i= 0; i != NE; ++i) {
6297 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6298 SDValue Operand = N->getOperand(j);
6299 EVT OperandVT = Operand.getValueType();
6300 if (OperandVT.isVector()) {
6301 // A vector operand; extract a single element.
6302 const TargetLowering *TLI = TM.getTargetLowering();
6303 EVT OperandEltVT = OperandVT.getVectorElementType();
6304 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6307 getConstant(i, TLI->getVectorIdxTy()));
6309 // A scalar operand; just use it as is.
6310 Operands[j] = Operand;
6314 switch (N->getOpcode()) {
6316 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6317 &Operands[0], Operands.size()));
6320 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6321 &Operands[0], Operands.size()));
6328 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6329 getShiftAmountOperand(Operands[0].getValueType(),
6332 case ISD::SIGN_EXTEND_INREG:
6333 case ISD::FP_ROUND_INREG: {
6334 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6335 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6337 getValueType(ExtVT)));
6342 for (; i < ResNE; ++i)
6343 Scalars.push_back(getUNDEF(EltVT));
6345 return getNode(ISD::BUILD_VECTOR, dl,
6346 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6347 &Scalars[0], Scalars.size());
6351 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6352 /// location that is 'Dist' units away from the location that the 'Base' load
6353 /// is loading from.
6354 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6355 unsigned Bytes, int Dist) const {
6356 if (LD->getChain() != Base->getChain())
6358 EVT VT = LD->getValueType(0);
6359 if (VT.getSizeInBits() / 8 != Bytes)
6362 SDValue Loc = LD->getOperand(1);
6363 SDValue BaseLoc = Base->getOperand(1);
6364 if (Loc.getOpcode() == ISD::FrameIndex) {
6365 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6367 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6368 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6369 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6370 int FS = MFI->getObjectSize(FI);
6371 int BFS = MFI->getObjectSize(BFI);
6372 if (FS != BFS || FS != (int)Bytes) return false;
6373 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6377 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6378 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6381 const GlobalValue *GV1 = NULL;
6382 const GlobalValue *GV2 = NULL;
6383 int64_t Offset1 = 0;
6384 int64_t Offset2 = 0;
6385 const TargetLowering *TLI = TM.getTargetLowering();
6386 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6387 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6388 if (isGA1 && isGA2 && GV1 == GV2)
6389 return Offset1 == (Offset2 + Dist*Bytes);
6394 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6395 /// it cannot be inferred.
6396 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6397 // If this is a GlobalAddress + cst, return the alignment.
6398 const GlobalValue *GV;
6399 int64_t GVOffset = 0;
6400 const TargetLowering *TLI = TM.getTargetLowering();
6401 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6402 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6403 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6404 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6405 TLI->getDataLayout());
6406 unsigned AlignBits = KnownZero.countTrailingOnes();
6407 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6409 return MinAlign(Align, GVOffset);
6412 // If this is a direct reference to a stack slot, use information about the
6413 // stack slot's alignment.
6414 int FrameIdx = 1 << 31;
6415 int64_t FrameOffset = 0;
6416 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6417 FrameIdx = FI->getIndex();
6418 } else if (isBaseWithConstantOffset(Ptr) &&
6419 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6421 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6422 FrameOffset = Ptr.getConstantOperandVal(1);
6425 if (FrameIdx != (1 << 31)) {
6426 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6427 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6435 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6436 /// which is split (or expanded) into two not necessarily identical pieces.
6437 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6438 // Currently all types are split in half.
6440 if (!VT.isVector()) {
6441 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6443 unsigned NumElements = VT.getVectorNumElements();
6444 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6445 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6448 return std::make_pair(LoVT, HiVT);
6451 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6453 std::pair<SDValue, SDValue>
6454 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6456 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6457 N.getValueType().getVectorNumElements() &&
6458 "More vector elements requested than available!");
6460 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6461 getConstant(0, TLI->getVectorIdxTy()));
6462 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6463 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6464 return std::make_pair(Lo, Hi);
6467 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6468 unsigned GlobalAddressSDNode::getAddressSpace() const {
6469 return getGlobal()->getType()->getAddressSpace();
6473 Type *ConstantPoolSDNode::getType() const {
6474 if (isMachineConstantPoolEntry())
6475 return Val.MachineCPVal->getType();
6476 return Val.ConstVal->getType();
6479 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6481 unsigned &SplatBitSize,
6483 unsigned MinSplatBits,
6485 EVT VT = getValueType(0);
6486 assert(VT.isVector() && "Expected a vector type");
6487 unsigned sz = VT.getSizeInBits();
6488 if (MinSplatBits > sz)
6491 SplatValue = APInt(sz, 0);
6492 SplatUndef = APInt(sz, 0);
6494 // Get the bits. Bits with undefined values (when the corresponding element
6495 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6496 // in SplatValue. If any of the values are not constant, give up and return
6498 unsigned int nOps = getNumOperands();
6499 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6500 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6502 for (unsigned j = 0; j < nOps; ++j) {
6503 unsigned i = isBigEndian ? nOps-1-j : j;
6504 SDValue OpVal = getOperand(i);
6505 unsigned BitPos = j * EltBitSize;
6507 if (OpVal.getOpcode() == ISD::UNDEF)
6508 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6509 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6510 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6511 zextOrTrunc(sz) << BitPos;
6512 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6513 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6518 // The build_vector is all constants or undefs. Find the smallest element
6519 // size that splats the vector.
6521 HasAnyUndefs = (SplatUndef != 0);
6524 unsigned HalfSize = sz / 2;
6525 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6526 APInt LowValue = SplatValue.trunc(HalfSize);
6527 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6528 APInt LowUndef = SplatUndef.trunc(HalfSize);
6530 // If the two halves do not match (ignoring undef bits), stop here.
6531 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6532 MinSplatBits > HalfSize)
6535 SplatValue = HighValue | LowValue;
6536 SplatUndef = HighUndef & LowUndef;
6545 bool BuildVectorSDNode::isConstant() const {
6546 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6547 unsigned Opc = getOperand(i).getOpcode();
6548 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6554 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6555 // Find the first non-undef value in the shuffle mask.
6557 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6560 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6562 // Make sure all remaining elements are either undef or the same as the first
6564 for (int Idx = Mask[i]; i != e; ++i)
6565 if (Mask[i] >= 0 && Mask[i] != Idx)
6571 static void checkForCyclesHelper(const SDNode *N,
6572 SmallPtrSet<const SDNode*, 32> &Visited,
6573 SmallPtrSet<const SDNode*, 32> &Checked) {
6574 // If this node has already been checked, don't check it again.
6575 if (Checked.count(N))
6578 // If a node has already been visited on this depth-first walk, reject it as
6580 if (!Visited.insert(N)) {
6581 dbgs() << "Offending node:\n";
6583 errs() << "Detected cycle in SelectionDAG\n";
6587 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6588 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6595 void llvm::checkForCycles(const llvm::SDNode *N) {
6597 assert(N && "Checking nonexistent SDNode");
6598 SmallPtrSet<const SDNode*, 32> visited;
6599 SmallPtrSet<const SDNode*, 32> checked;
6600 checkForCyclesHelper(N, visited, checked);
6604 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6605 checkForCycles(DAG->getRoot().getNode());