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) {
3637 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3638 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3639 VT = TLI.getPointerTy();
3641 switch (DstAlign & 7) {
3642 case 0: VT = MVT::i64; break;
3643 case 4: VT = MVT::i32; break;
3644 case 2: VT = MVT::i16; break;
3645 default: VT = MVT::i8; break;
3650 while (!TLI.isTypeLegal(LVT))
3651 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3652 assert(LVT.isInteger());
3658 unsigned NumMemOps = 0;
3660 unsigned VTSize = VT.getSizeInBits() / 8;
3661 while (VTSize > Size) {
3662 // For now, only use non-vector load / store's for the left-over pieces.
3667 if (VT.isVector() || VT.isFloatingPoint()) {
3668 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3669 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3670 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3672 else if (NewVT == MVT::i64 &&
3673 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3674 TLI.isSafeMemOpType(MVT::f64)) {
3675 // i64 is usually not legal on 32-bit targets, but f64 may be.
3683 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3684 if (NewVT == MVT::i8)
3686 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3688 NewVTSize = NewVT.getSizeInBits() / 8;
3690 // If the new VT cannot cover all of the remaining bits, then consider
3691 // issuing a (or a pair of) unaligned and overlapping load / store.
3692 // FIXME: Only does this for 64-bit or more since we don't have proper
3693 // cost model for unaligned load / store.
3696 if (NumMemOps && AllowOverlap &&
3697 VTSize >= 8 && NewVTSize < Size &&
3698 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3706 if (++NumMemOps > Limit)
3709 MemOps.push_back(VT);
3716 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3717 SDValue Chain, SDValue Dst,
3718 SDValue Src, uint64_t Size,
3719 unsigned Align, bool isVol,
3721 MachinePointerInfo DstPtrInfo,
3722 MachinePointerInfo SrcPtrInfo) {
3723 // Turn a memcpy of undef to nop.
3724 if (Src.getOpcode() == ISD::UNDEF)
3727 // Expand memcpy to a series of load and store ops if the size operand falls
3728 // below a certain threshold.
3729 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3730 // rather than maybe a humongous number of loads and stores.
3731 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3732 std::vector<EVT> MemOps;
3733 bool DstAlignCanChange = false;
3734 MachineFunction &MF = DAG.getMachineFunction();
3735 MachineFrameInfo *MFI = MF.getFrameInfo();
3737 MF.getFunction()->getAttributes().
3738 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3739 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3740 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3741 DstAlignCanChange = true;
3742 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3743 if (Align > SrcAlign)
3746 bool CopyFromStr = isMemSrcFromString(Src, Str);
3747 bool isZeroStr = CopyFromStr && Str.empty();
3748 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3750 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3751 (DstAlignCanChange ? 0 : Align),
3752 (isZeroStr ? 0 : SrcAlign),
3753 false, false, CopyFromStr, true, DAG, TLI))
3756 if (DstAlignCanChange) {
3757 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3758 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3760 // Don't promote to an alignment that would require dynamic stack
3762 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3763 if (!TRI->needsStackRealignment(MF))
3764 while (NewAlign > Align &&
3765 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3768 if (NewAlign > Align) {
3769 // Give the stack frame object a larger alignment if needed.
3770 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3771 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3776 SmallVector<SDValue, 8> OutChains;
3777 unsigned NumMemOps = MemOps.size();
3778 uint64_t SrcOff = 0, DstOff = 0;
3779 for (unsigned i = 0; i != NumMemOps; ++i) {
3781 unsigned VTSize = VT.getSizeInBits() / 8;
3782 SDValue Value, Store;
3784 if (VTSize > Size) {
3785 // Issuing an unaligned load / store pair that overlaps with the previous
3786 // pair. Adjust the offset accordingly.
3787 assert(i == NumMemOps-1 && i != 0);
3788 SrcOff -= VTSize - Size;
3789 DstOff -= VTSize - Size;
3793 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3794 // It's unlikely a store of a vector immediate can be done in a single
3795 // instruction. It would require a load from a constantpool first.
3796 // We only handle zero vectors here.
3797 // FIXME: Handle other cases where store of vector immediate is done in
3798 // a single instruction.
3799 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3800 if (Value.getNode())
3801 Store = DAG.getStore(Chain, dl, Value,
3802 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3803 DstPtrInfo.getWithOffset(DstOff), isVol,
3807 if (!Store.getNode()) {
3808 // The type might not be legal for the target. This should only happen
3809 // if the type is smaller than a legal type, as on PPC, so the right
3810 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3811 // to Load/Store if NVT==VT.
3812 // FIXME does the case above also need this?
3813 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3814 assert(NVT.bitsGE(VT));
3815 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3816 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3817 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3818 MinAlign(SrcAlign, SrcOff));
3819 Store = DAG.getTruncStore(Chain, dl, Value,
3820 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3821 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3824 OutChains.push_back(Store);
3830 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3831 &OutChains[0], OutChains.size());
3834 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3835 SDValue Chain, SDValue Dst,
3836 SDValue Src, uint64_t Size,
3837 unsigned Align, bool isVol,
3839 MachinePointerInfo DstPtrInfo,
3840 MachinePointerInfo SrcPtrInfo) {
3841 // Turn a memmove of undef to nop.
3842 if (Src.getOpcode() == ISD::UNDEF)
3845 // Expand memmove to a series of load and store ops if the size operand falls
3846 // below a certain threshold.
3847 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3848 std::vector<EVT> MemOps;
3849 bool DstAlignCanChange = false;
3850 MachineFunction &MF = DAG.getMachineFunction();
3851 MachineFrameInfo *MFI = MF.getFrameInfo();
3852 bool OptSize = MF.getFunction()->getAttributes().
3853 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3854 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3855 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3856 DstAlignCanChange = true;
3857 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3858 if (Align > SrcAlign)
3860 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3862 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3863 (DstAlignCanChange ? 0 : Align), SrcAlign,
3864 false, false, false, false, DAG, TLI))
3867 if (DstAlignCanChange) {
3868 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3869 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3870 if (NewAlign > Align) {
3871 // Give the stack frame object a larger alignment if needed.
3872 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3873 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3878 uint64_t SrcOff = 0, DstOff = 0;
3879 SmallVector<SDValue, 8> LoadValues;
3880 SmallVector<SDValue, 8> LoadChains;
3881 SmallVector<SDValue, 8> OutChains;
3882 unsigned NumMemOps = MemOps.size();
3883 for (unsigned i = 0; i < NumMemOps; i++) {
3885 unsigned VTSize = VT.getSizeInBits() / 8;
3888 Value = DAG.getLoad(VT, dl, Chain,
3889 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3890 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3891 false, false, SrcAlign);
3892 LoadValues.push_back(Value);
3893 LoadChains.push_back(Value.getValue(1));
3896 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3897 &LoadChains[0], LoadChains.size());
3899 for (unsigned i = 0; i < NumMemOps; i++) {
3901 unsigned VTSize = VT.getSizeInBits() / 8;
3904 Store = DAG.getStore(Chain, dl, LoadValues[i],
3905 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3906 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3907 OutChains.push_back(Store);
3911 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3912 &OutChains[0], OutChains.size());
3915 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3918 /// \param DAG Selection DAG where lowered code is placed.
3919 /// \param dl Link to corresponding IR location.
3920 /// \param Chain Control flow dependency.
3921 /// \param Dst Pointer to destination memory location.
3922 /// \param Src Value of byte to write into the memory.
3923 /// \param Size Number of bytes to write.
3924 /// \param Align Alignment of the destination in bytes.
3925 /// \param isVol True if destination is volatile.
3926 /// \param DstPtrInfo IR information on the memory pointer.
3927 /// \returns New head in the control flow, if lowering was successful, empty
3928 /// SDValue otherwise.
3930 /// The function tries to replace 'llvm.memset' intrinsic with several store
3931 /// operations and value calculation code. This is usually profitable for small
3933 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3934 SDValue Chain, SDValue Dst,
3935 SDValue Src, uint64_t Size,
3936 unsigned Align, bool isVol,
3937 MachinePointerInfo DstPtrInfo) {
3938 // Turn a memset of undef to nop.
3939 if (Src.getOpcode() == ISD::UNDEF)
3942 // Expand memset to a series of load/store ops if the size operand
3943 // falls below a certain threshold.
3944 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3945 std::vector<EVT> MemOps;
3946 bool DstAlignCanChange = false;
3947 MachineFunction &MF = DAG.getMachineFunction();
3948 MachineFrameInfo *MFI = MF.getFrameInfo();
3949 bool OptSize = MF.getFunction()->getAttributes().
3950 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3951 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3952 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3953 DstAlignCanChange = true;
3955 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3956 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3957 Size, (DstAlignCanChange ? 0 : Align), 0,
3958 true, IsZeroVal, false, true, DAG, TLI))
3961 if (DstAlignCanChange) {
3962 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3963 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3964 if (NewAlign > Align) {
3965 // Give the stack frame object a larger alignment if needed.
3966 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3967 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3972 SmallVector<SDValue, 8> OutChains;
3973 uint64_t DstOff = 0;
3974 unsigned NumMemOps = MemOps.size();
3976 // Find the largest store and generate the bit pattern for it.
3977 EVT LargestVT = MemOps[0];
3978 for (unsigned i = 1; i < NumMemOps; i++)
3979 if (MemOps[i].bitsGT(LargestVT))
3980 LargestVT = MemOps[i];
3981 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3983 for (unsigned i = 0; i < NumMemOps; i++) {
3985 unsigned VTSize = VT.getSizeInBits() / 8;
3986 if (VTSize > Size) {
3987 // Issuing an unaligned load / store pair that overlaps with the previous
3988 // pair. Adjust the offset accordingly.
3989 assert(i == NumMemOps-1 && i != 0);
3990 DstOff -= VTSize - Size;
3993 // If this store is smaller than the largest store see whether we can get
3994 // the smaller value for free with a truncate.
3995 SDValue Value = MemSetValue;
3996 if (VT.bitsLT(LargestVT)) {
3997 if (!LargestVT.isVector() && !VT.isVector() &&
3998 TLI.isTruncateFree(LargestVT, VT))
3999 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4001 Value = getMemsetValue(Src, VT, DAG, dl);
4003 assert(Value.getValueType() == VT && "Value with wrong type.");
4004 SDValue Store = DAG.getStore(Chain, dl, Value,
4005 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4006 DstPtrInfo.getWithOffset(DstOff),
4007 isVol, false, Align);
4008 OutChains.push_back(Store);
4009 DstOff += VT.getSizeInBits() / 8;
4013 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
4014 &OutChains[0], OutChains.size());
4017 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4018 SDValue Src, SDValue Size,
4019 unsigned Align, bool isVol, bool AlwaysInline,
4020 MachinePointerInfo DstPtrInfo,
4021 MachinePointerInfo SrcPtrInfo) {
4022 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4024 // Check to see if we should lower the memcpy to loads and stores first.
4025 // For cases within the target-specified limits, this is the best choice.
4026 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4028 // Memcpy with size zero? Just return the original chain.
4029 if (ConstantSize->isNullValue())
4032 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4033 ConstantSize->getZExtValue(),Align,
4034 isVol, false, DstPtrInfo, SrcPtrInfo);
4035 if (Result.getNode())
4039 // Then check to see if we should lower the memcpy with target-specific
4040 // code. If the target chooses to do this, this is the next best.
4042 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4043 isVol, AlwaysInline,
4044 DstPtrInfo, SrcPtrInfo);
4045 if (Result.getNode())
4048 // If we really need inline code and the target declined to provide it,
4049 // use a (potentially long) sequence of loads and stores.
4051 assert(ConstantSize && "AlwaysInline requires a constant size!");
4052 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4053 ConstantSize->getZExtValue(), Align, isVol,
4054 true, DstPtrInfo, SrcPtrInfo);
4057 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4058 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4059 // respect volatile, so they may do things like read or write memory
4060 // beyond the given memory regions. But fixing this isn't easy, and most
4061 // people don't care.
4063 const TargetLowering *TLI = TM.getTargetLowering();
4065 // Emit a library call.
4066 TargetLowering::ArgListTy Args;
4067 TargetLowering::ArgListEntry Entry;
4068 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4069 Entry.Node = Dst; Args.push_back(Entry);
4070 Entry.Node = Src; Args.push_back(Entry);
4071 Entry.Node = Size; Args.push_back(Entry);
4072 // FIXME: pass in SDLoc
4074 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4075 false, false, false, false, 0,
4076 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4077 /*isTailCall=*/false,
4078 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4079 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4080 TLI->getPointerTy()),
4082 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4084 return CallResult.second;
4087 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4088 SDValue Src, SDValue Size,
4089 unsigned Align, bool isVol,
4090 MachinePointerInfo DstPtrInfo,
4091 MachinePointerInfo SrcPtrInfo) {
4092 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4094 // Check to see if we should lower the memmove to loads and stores first.
4095 // For cases within the target-specified limits, this is the best choice.
4096 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4098 // Memmove with size zero? Just return the original chain.
4099 if (ConstantSize->isNullValue())
4103 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4104 ConstantSize->getZExtValue(), Align, isVol,
4105 false, DstPtrInfo, SrcPtrInfo);
4106 if (Result.getNode())
4110 // Then check to see if we should lower the memmove with target-specific
4111 // code. If the target chooses to do this, this is the next best.
4113 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4114 DstPtrInfo, SrcPtrInfo);
4115 if (Result.getNode())
4118 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4119 // not be safe. See memcpy above for more details.
4121 const TargetLowering *TLI = TM.getTargetLowering();
4123 // Emit a library call.
4124 TargetLowering::ArgListTy Args;
4125 TargetLowering::ArgListEntry Entry;
4126 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4127 Entry.Node = Dst; Args.push_back(Entry);
4128 Entry.Node = Src; Args.push_back(Entry);
4129 Entry.Node = Size; Args.push_back(Entry);
4130 // FIXME: pass in SDLoc
4132 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4133 false, false, false, false, 0,
4134 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4135 /*isTailCall=*/false,
4136 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4137 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4138 TLI->getPointerTy()),
4140 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4142 return CallResult.second;
4145 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4146 SDValue Src, SDValue Size,
4147 unsigned Align, bool isVol,
4148 MachinePointerInfo DstPtrInfo) {
4149 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4151 // Check to see if we should lower the memset to stores first.
4152 // For cases within the target-specified limits, this is the best choice.
4153 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4155 // Memset with size zero? Just return the original chain.
4156 if (ConstantSize->isNullValue())
4160 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4161 Align, isVol, DstPtrInfo);
4163 if (Result.getNode())
4167 // Then check to see if we should lower the memset with target-specific
4168 // code. If the target chooses to do this, this is the next best.
4170 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4172 if (Result.getNode())
4175 // Emit a library call.
4176 const TargetLowering *TLI = TM.getTargetLowering();
4177 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4178 TargetLowering::ArgListTy Args;
4179 TargetLowering::ArgListEntry Entry;
4180 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4181 Args.push_back(Entry);
4182 // Extend or truncate the argument to be an i32 value for the call.
4183 if (Src.getValueType().bitsGT(MVT::i32))
4184 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4186 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4188 Entry.Ty = Type::getInt32Ty(*getContext());
4189 Entry.isSExt = true;
4190 Args.push_back(Entry);
4192 Entry.Ty = IntPtrTy;
4193 Entry.isSExt = false;
4194 Args.push_back(Entry);
4195 // FIXME: pass in SDLoc
4197 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4198 false, false, false, false, 0,
4199 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4200 /*isTailCall=*/false,
4201 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4202 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4203 TLI->getPointerTy()),
4205 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4207 return CallResult.second;
4210 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4211 SDVTList VTList, SDValue* Ops, unsigned NumOps,
4212 MachineMemOperand *MMO,
4213 AtomicOrdering Ordering,
4214 SynchronizationScope SynchScope) {
4215 FoldingSetNodeID ID;
4216 ID.AddInteger(MemVT.getRawBits());
4217 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4218 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4220 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4221 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4222 return SDValue(E, 0);
4225 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4226 // SDNode doesn't have access to it. This memory will be "leaked" when
4227 // the node is deallocated, but recovered when the allocator is released.
4228 // If the number of operands is less than 5 we use AtomicSDNode's internal
4230 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps) : 0;
4232 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4233 dl.getDebugLoc(), VTList, MemVT,
4234 Ops, DynOps, NumOps, MMO,
4235 Ordering, SynchScope);
4236 CSEMap.InsertNode(N, IP);
4237 AllNodes.push_back(N);
4238 return SDValue(N, 0);
4241 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4242 SDValue Chain, SDValue Ptr, SDValue Cmp,
4243 SDValue Swp, MachinePointerInfo PtrInfo,
4245 AtomicOrdering Ordering,
4246 SynchronizationScope SynchScope) {
4247 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4248 Alignment = getEVTAlignment(MemVT);
4250 MachineFunction &MF = getMachineFunction();
4252 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4253 // For now, atomics are considered to be volatile always.
4254 // FIXME: Volatile isn't really correct; we should keep track of atomic
4255 // orderings in the memoperand.
4256 unsigned Flags = MachineMemOperand::MOVolatile;
4257 if (Opcode != ISD::ATOMIC_STORE)
4258 Flags |= MachineMemOperand::MOLoad;
4259 if (Opcode != ISD::ATOMIC_LOAD)
4260 Flags |= MachineMemOperand::MOStore;
4262 MachineMemOperand *MMO =
4263 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4265 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4266 Ordering, SynchScope);
4269 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4271 SDValue Ptr, SDValue Cmp,
4272 SDValue Swp, MachineMemOperand *MMO,
4273 AtomicOrdering Ordering,
4274 SynchronizationScope SynchScope) {
4275 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4276 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4278 EVT VT = Cmp.getValueType();
4280 SDVTList VTs = getVTList(VT, MVT::Other);
4281 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4282 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 4, MMO, Ordering, SynchScope);
4285 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4287 SDValue Ptr, SDValue Val,
4288 const Value* PtrVal,
4290 AtomicOrdering Ordering,
4291 SynchronizationScope SynchScope) {
4292 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4293 Alignment = getEVTAlignment(MemVT);
4295 MachineFunction &MF = getMachineFunction();
4296 // An atomic store does not load. An atomic load does not store.
4297 // (An atomicrmw obviously both loads and stores.)
4298 // For now, atomics are considered to be volatile always, and they are
4300 // FIXME: Volatile isn't really correct; we should keep track of atomic
4301 // orderings in the memoperand.
4302 unsigned Flags = MachineMemOperand::MOVolatile;
4303 if (Opcode != ISD::ATOMIC_STORE)
4304 Flags |= MachineMemOperand::MOLoad;
4305 if (Opcode != ISD::ATOMIC_LOAD)
4306 Flags |= MachineMemOperand::MOStore;
4308 MachineMemOperand *MMO =
4309 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4310 MemVT.getStoreSize(), Alignment);
4312 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4313 Ordering, SynchScope);
4316 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4318 SDValue Ptr, SDValue Val,
4319 MachineMemOperand *MMO,
4320 AtomicOrdering Ordering,
4321 SynchronizationScope SynchScope) {
4322 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4323 Opcode == ISD::ATOMIC_LOAD_SUB ||
4324 Opcode == ISD::ATOMIC_LOAD_AND ||
4325 Opcode == ISD::ATOMIC_LOAD_OR ||
4326 Opcode == ISD::ATOMIC_LOAD_XOR ||
4327 Opcode == ISD::ATOMIC_LOAD_NAND ||
4328 Opcode == ISD::ATOMIC_LOAD_MIN ||
4329 Opcode == ISD::ATOMIC_LOAD_MAX ||
4330 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4331 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4332 Opcode == ISD::ATOMIC_SWAP ||
4333 Opcode == ISD::ATOMIC_STORE) &&
4334 "Invalid Atomic Op");
4336 EVT VT = Val.getValueType();
4338 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4339 getVTList(VT, MVT::Other);
4340 SDValue Ops[] = {Chain, Ptr, Val};
4341 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 3, MMO, Ordering, SynchScope);
4344 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4345 EVT VT, SDValue Chain,
4347 const Value* PtrVal,
4349 AtomicOrdering Ordering,
4350 SynchronizationScope SynchScope) {
4351 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4352 Alignment = getEVTAlignment(MemVT);
4354 MachineFunction &MF = getMachineFunction();
4355 // An atomic store does not load. An atomic load does not store.
4356 // (An atomicrmw obviously both loads and stores.)
4357 // For now, atomics are considered to be volatile always, and they are
4359 // FIXME: Volatile isn't really correct; we should keep track of atomic
4360 // orderings in the memoperand.
4361 unsigned Flags = MachineMemOperand::MOVolatile;
4362 if (Opcode != ISD::ATOMIC_STORE)
4363 Flags |= MachineMemOperand::MOLoad;
4364 if (Opcode != ISD::ATOMIC_LOAD)
4365 Flags |= MachineMemOperand::MOStore;
4367 MachineMemOperand *MMO =
4368 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4369 MemVT.getStoreSize(), Alignment);
4371 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
4372 Ordering, SynchScope);
4375 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4376 EVT VT, SDValue Chain,
4378 MachineMemOperand *MMO,
4379 AtomicOrdering Ordering,
4380 SynchronizationScope SynchScope) {
4381 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4383 SDVTList VTs = getVTList(VT, MVT::Other);
4384 SDValue Ops[] = {Chain, Ptr};
4385 return getAtomic(Opcode, dl, MemVT, VTs, Ops, 2, MMO, Ordering, SynchScope);
4388 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4389 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4394 SmallVector<EVT, 4> VTs;
4395 VTs.reserve(NumOps);
4396 for (unsigned i = 0; i < NumOps; ++i)
4397 VTs.push_back(Ops[i].getValueType());
4398 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4403 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
4404 const EVT *VTs, unsigned NumVTs,
4405 const SDValue *Ops, unsigned NumOps,
4406 EVT MemVT, MachinePointerInfo PtrInfo,
4407 unsigned Align, bool Vol,
4408 bool ReadMem, bool WriteMem) {
4409 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4410 MemVT, PtrInfo, Align, Vol,
4415 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4416 const SDValue *Ops, unsigned NumOps,
4417 EVT MemVT, MachinePointerInfo PtrInfo,
4418 unsigned Align, bool Vol,
4419 bool ReadMem, bool WriteMem) {
4420 if (Align == 0) // Ensure that codegen never sees alignment 0
4421 Align = getEVTAlignment(MemVT);
4423 MachineFunction &MF = getMachineFunction();
4426 Flags |= MachineMemOperand::MOStore;
4428 Flags |= MachineMemOperand::MOLoad;
4430 Flags |= MachineMemOperand::MOVolatile;
4431 MachineMemOperand *MMO =
4432 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4434 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4438 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4439 const SDValue *Ops, unsigned NumOps,
4440 EVT MemVT, MachineMemOperand *MMO) {
4441 assert((Opcode == ISD::INTRINSIC_VOID ||
4442 Opcode == ISD::INTRINSIC_W_CHAIN ||
4443 Opcode == ISD::PREFETCH ||
4444 Opcode == ISD::LIFETIME_START ||
4445 Opcode == ISD::LIFETIME_END ||
4446 (Opcode <= INT_MAX &&
4447 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4448 "Opcode is not a memory-accessing opcode!");
4450 // Memoize the node unless it returns a flag.
4451 MemIntrinsicSDNode *N;
4452 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4453 FoldingSetNodeID ID;
4454 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4455 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4457 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4458 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4459 return SDValue(E, 0);
4462 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4463 dl.getDebugLoc(), VTList, Ops,
4464 NumOps, MemVT, MMO);
4465 CSEMap.InsertNode(N, IP);
4467 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4468 dl.getDebugLoc(), VTList, Ops,
4469 NumOps, MemVT, MMO);
4471 AllNodes.push_back(N);
4472 return SDValue(N, 0);
4475 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4476 /// MachinePointerInfo record from it. This is particularly useful because the
4477 /// code generator has many cases where it doesn't bother passing in a
4478 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4479 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4480 // If this is FI+Offset, we can model it.
4481 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4482 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4484 // If this is (FI+Offset1)+Offset2, we can model it.
4485 if (Ptr.getOpcode() != ISD::ADD ||
4486 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4487 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4488 return MachinePointerInfo();
4490 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4491 return MachinePointerInfo::getFixedStack(FI, Offset+
4492 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4495 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4496 /// MachinePointerInfo record from it. This is particularly useful because the
4497 /// code generator has many cases where it doesn't bother passing in a
4498 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4499 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4500 // If the 'Offset' value isn't a constant, we can't handle this.
4501 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4502 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4503 if (OffsetOp.getOpcode() == ISD::UNDEF)
4504 return InferPointerInfo(Ptr);
4505 return MachinePointerInfo();
4510 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4511 EVT VT, SDLoc dl, SDValue Chain,
4512 SDValue Ptr, SDValue Offset,
4513 MachinePointerInfo PtrInfo, EVT MemVT,
4514 bool isVolatile, bool isNonTemporal, bool isInvariant,
4515 unsigned Alignment, const MDNode *TBAAInfo,
4516 const MDNode *Ranges) {
4517 assert(Chain.getValueType() == MVT::Other &&
4518 "Invalid chain type");
4519 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4520 Alignment = getEVTAlignment(VT);
4522 unsigned Flags = MachineMemOperand::MOLoad;
4524 Flags |= MachineMemOperand::MOVolatile;
4526 Flags |= MachineMemOperand::MONonTemporal;
4528 Flags |= MachineMemOperand::MOInvariant;
4530 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4533 PtrInfo = InferPointerInfo(Ptr, Offset);
4535 MachineFunction &MF = getMachineFunction();
4536 MachineMemOperand *MMO =
4537 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4539 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4543 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4544 EVT VT, SDLoc dl, SDValue Chain,
4545 SDValue Ptr, SDValue Offset, EVT MemVT,
4546 MachineMemOperand *MMO) {
4548 ExtType = ISD::NON_EXTLOAD;
4549 } else if (ExtType == ISD::NON_EXTLOAD) {
4550 assert(VT == MemVT && "Non-extending load from different memory type!");
4553 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4554 "Should only be an extending load, not truncating!");
4555 assert(VT.isInteger() == MemVT.isInteger() &&
4556 "Cannot convert from FP to Int or Int -> FP!");
4557 assert(VT.isVector() == MemVT.isVector() &&
4558 "Cannot use trunc store to convert to or from a vector!");
4559 assert((!VT.isVector() ||
4560 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4561 "Cannot use trunc store to change the number of vector elements!");
4564 bool Indexed = AM != ISD::UNINDEXED;
4565 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4566 "Unindexed load with an offset!");
4568 SDVTList VTs = Indexed ?
4569 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4570 SDValue Ops[] = { Chain, Ptr, Offset };
4571 FoldingSetNodeID ID;
4572 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4573 ID.AddInteger(MemVT.getRawBits());
4574 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4575 MMO->isNonTemporal(),
4576 MMO->isInvariant()));
4577 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4579 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4580 cast<LoadSDNode>(E)->refineAlignment(MMO);
4581 return SDValue(E, 0);
4583 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4584 dl.getDebugLoc(), VTs, AM, ExtType,
4586 CSEMap.InsertNode(N, IP);
4587 AllNodes.push_back(N);
4588 return SDValue(N, 0);
4591 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4592 SDValue Chain, SDValue Ptr,
4593 MachinePointerInfo PtrInfo,
4594 bool isVolatile, bool isNonTemporal,
4595 bool isInvariant, unsigned Alignment,
4596 const MDNode *TBAAInfo,
4597 const MDNode *Ranges) {
4598 SDValue Undef = getUNDEF(Ptr.getValueType());
4599 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4600 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4604 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4605 SDValue Chain, SDValue Ptr,
4606 MachineMemOperand *MMO) {
4607 SDValue Undef = getUNDEF(Ptr.getValueType());
4608 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4612 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4613 SDValue Chain, SDValue Ptr,
4614 MachinePointerInfo PtrInfo, EVT MemVT,
4615 bool isVolatile, bool isNonTemporal,
4616 unsigned Alignment, const MDNode *TBAAInfo) {
4617 SDValue Undef = getUNDEF(Ptr.getValueType());
4618 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4619 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4624 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4625 SDValue Chain, SDValue Ptr, EVT MemVT,
4626 MachineMemOperand *MMO) {
4627 SDValue Undef = getUNDEF(Ptr.getValueType());
4628 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4633 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4634 SDValue Offset, ISD::MemIndexedMode AM) {
4635 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4636 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4637 "Load is already a indexed load!");
4638 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4639 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4640 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4641 false, LD->getAlignment());
4644 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4645 SDValue Ptr, MachinePointerInfo PtrInfo,
4646 bool isVolatile, bool isNonTemporal,
4647 unsigned Alignment, const MDNode *TBAAInfo) {
4648 assert(Chain.getValueType() == MVT::Other &&
4649 "Invalid chain type");
4650 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4651 Alignment = getEVTAlignment(Val.getValueType());
4653 unsigned Flags = MachineMemOperand::MOStore;
4655 Flags |= MachineMemOperand::MOVolatile;
4657 Flags |= MachineMemOperand::MONonTemporal;
4660 PtrInfo = InferPointerInfo(Ptr);
4662 MachineFunction &MF = getMachineFunction();
4663 MachineMemOperand *MMO =
4664 MF.getMachineMemOperand(PtrInfo, Flags,
4665 Val.getValueType().getStoreSize(), Alignment,
4668 return getStore(Chain, dl, Val, Ptr, MMO);
4671 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4672 SDValue Ptr, MachineMemOperand *MMO) {
4673 assert(Chain.getValueType() == MVT::Other &&
4674 "Invalid chain type");
4675 EVT VT = Val.getValueType();
4676 SDVTList VTs = getVTList(MVT::Other);
4677 SDValue Undef = getUNDEF(Ptr.getValueType());
4678 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4679 FoldingSetNodeID ID;
4680 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4681 ID.AddInteger(VT.getRawBits());
4682 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4683 MMO->isNonTemporal(), MMO->isInvariant()));
4684 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4686 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4687 cast<StoreSDNode>(E)->refineAlignment(MMO);
4688 return SDValue(E, 0);
4690 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4691 dl.getDebugLoc(), VTs,
4692 ISD::UNINDEXED, false, VT, MMO);
4693 CSEMap.InsertNode(N, IP);
4694 AllNodes.push_back(N);
4695 return SDValue(N, 0);
4698 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4699 SDValue Ptr, MachinePointerInfo PtrInfo,
4700 EVT SVT,bool isVolatile, bool isNonTemporal,
4702 const MDNode *TBAAInfo) {
4703 assert(Chain.getValueType() == MVT::Other &&
4704 "Invalid chain type");
4705 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4706 Alignment = getEVTAlignment(SVT);
4708 unsigned Flags = MachineMemOperand::MOStore;
4710 Flags |= MachineMemOperand::MOVolatile;
4712 Flags |= MachineMemOperand::MONonTemporal;
4715 PtrInfo = InferPointerInfo(Ptr);
4717 MachineFunction &MF = getMachineFunction();
4718 MachineMemOperand *MMO =
4719 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4722 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4725 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4726 SDValue Ptr, EVT SVT,
4727 MachineMemOperand *MMO) {
4728 EVT VT = Val.getValueType();
4730 assert(Chain.getValueType() == MVT::Other &&
4731 "Invalid chain type");
4733 return getStore(Chain, dl, Val, Ptr, MMO);
4735 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4736 "Should only be a truncating store, not extending!");
4737 assert(VT.isInteger() == SVT.isInteger() &&
4738 "Can't do FP-INT conversion!");
4739 assert(VT.isVector() == SVT.isVector() &&
4740 "Cannot use trunc store to convert to or from a vector!");
4741 assert((!VT.isVector() ||
4742 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4743 "Cannot use trunc store to change the number of vector elements!");
4745 SDVTList VTs = getVTList(MVT::Other);
4746 SDValue Undef = getUNDEF(Ptr.getValueType());
4747 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4748 FoldingSetNodeID ID;
4749 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4750 ID.AddInteger(SVT.getRawBits());
4751 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4752 MMO->isNonTemporal(), MMO->isInvariant()));
4753 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4755 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4756 cast<StoreSDNode>(E)->refineAlignment(MMO);
4757 return SDValue(E, 0);
4759 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4760 dl.getDebugLoc(), VTs,
4761 ISD::UNINDEXED, true, SVT, MMO);
4762 CSEMap.InsertNode(N, IP);
4763 AllNodes.push_back(N);
4764 return SDValue(N, 0);
4768 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4769 SDValue Offset, ISD::MemIndexedMode AM) {
4770 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4771 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4772 "Store is already a indexed store!");
4773 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4774 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4775 FoldingSetNodeID ID;
4776 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4777 ID.AddInteger(ST->getMemoryVT().getRawBits());
4778 ID.AddInteger(ST->getRawSubclassData());
4779 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4781 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4782 return SDValue(E, 0);
4784 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4785 dl.getDebugLoc(), VTs, AM,
4786 ST->isTruncatingStore(),
4788 ST->getMemOperand());
4789 CSEMap.InsertNode(N, IP);
4790 AllNodes.push_back(N);
4791 return SDValue(N, 0);
4794 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4795 SDValue Chain, SDValue Ptr,
4798 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4799 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4802 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4803 const SDUse *Ops, unsigned NumOps) {
4805 case 0: return getNode(Opcode, DL, VT);
4806 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4807 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4808 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4812 // Copy from an SDUse array into an SDValue array for use with
4813 // the regular getNode logic.
4814 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4815 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4818 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4819 const SDValue *Ops, unsigned NumOps) {
4821 case 0: return getNode(Opcode, DL, VT);
4822 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4823 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4824 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4830 case ISD::SELECT_CC: {
4831 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4832 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4833 "LHS and RHS of condition must have same type!");
4834 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4835 "True and False arms of SelectCC must have same type!");
4836 assert(Ops[2].getValueType() == VT &&
4837 "select_cc node must be of same type as true and false value!");
4841 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4842 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4843 "LHS/RHS of comparison should match types!");
4850 SDVTList VTs = getVTList(VT);
4852 if (VT != MVT::Glue) {
4853 FoldingSetNodeID ID;
4854 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4857 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4858 return SDValue(E, 0);
4860 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4862 CSEMap.InsertNode(N, IP);
4864 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4868 AllNodes.push_back(N);
4872 return SDValue(N, 0);
4875 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4876 ArrayRef<EVT> ResultTys,
4877 const SDValue *Ops, unsigned NumOps) {
4878 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4882 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4883 const EVT *VTs, unsigned NumVTs,
4884 const SDValue *Ops, unsigned NumOps) {
4886 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4887 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4890 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4891 const SDValue *Ops, unsigned NumOps) {
4892 if (VTList.NumVTs == 1)
4893 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4897 // FIXME: figure out how to safely handle things like
4898 // int foo(int x) { return 1 << (x & 255); }
4899 // int bar() { return foo(256); }
4900 case ISD::SRA_PARTS:
4901 case ISD::SRL_PARTS:
4902 case ISD::SHL_PARTS:
4903 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4904 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4905 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4906 else if (N3.getOpcode() == ISD::AND)
4907 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4908 // If the and is only masking out bits that cannot effect the shift,
4909 // eliminate the and.
4910 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4911 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4912 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4918 // Memoize the node unless it returns a flag.
4920 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4921 FoldingSetNodeID ID;
4922 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4924 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4925 return SDValue(E, 0);
4928 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4929 DL.getDebugLoc(), VTList, Ops[0]);
4930 } else if (NumOps == 2) {
4931 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4932 DL.getDebugLoc(), VTList, Ops[0],
4934 } else if (NumOps == 3) {
4935 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4936 DL.getDebugLoc(), VTList, Ops[0],
4939 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4940 VTList, Ops, NumOps);
4942 CSEMap.InsertNode(N, IP);
4945 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4946 DL.getDebugLoc(), VTList, Ops[0]);
4947 } else if (NumOps == 2) {
4948 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4949 DL.getDebugLoc(), VTList, Ops[0],
4951 } else if (NumOps == 3) {
4952 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4953 DL.getDebugLoc(), VTList, Ops[0],
4956 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4957 VTList, Ops, NumOps);
4960 AllNodes.push_back(N);
4964 return SDValue(N, 0);
4967 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4968 return getNode(Opcode, DL, VTList, 0, 0);
4971 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4973 SDValue Ops[] = { N1 };
4974 return getNode(Opcode, DL, VTList, Ops, 1);
4977 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4978 SDValue N1, SDValue N2) {
4979 SDValue Ops[] = { N1, N2 };
4980 return getNode(Opcode, DL, VTList, Ops, 2);
4983 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4984 SDValue N1, SDValue N2, SDValue N3) {
4985 SDValue Ops[] = { N1, N2, N3 };
4986 return getNode(Opcode, DL, VTList, Ops, 3);
4989 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4990 SDValue N1, SDValue N2, SDValue N3,
4992 SDValue Ops[] = { N1, N2, N3, N4 };
4993 return getNode(Opcode, DL, VTList, Ops, 4);
4996 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4997 SDValue N1, SDValue N2, SDValue N3,
4998 SDValue N4, SDValue N5) {
4999 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5000 return getNode(Opcode, DL, VTList, Ops, 5);
5003 SDVTList SelectionDAG::getVTList(EVT VT) {
5004 return makeVTList(SDNode::getValueTypeList(VT), 1);
5007 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5008 FoldingSetNodeID ID;
5010 ID.AddInteger(VT1.getRawBits());
5011 ID.AddInteger(VT2.getRawBits());
5014 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5015 if (Result == NULL) {
5016 EVT *Array = Allocator.Allocate<EVT>(2);
5019 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5020 VTListMap.InsertNode(Result, IP);
5022 return Result->getSDVTList();
5025 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5026 FoldingSetNodeID ID;
5028 ID.AddInteger(VT1.getRawBits());
5029 ID.AddInteger(VT2.getRawBits());
5030 ID.AddInteger(VT3.getRawBits());
5033 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5034 if (Result == NULL) {
5035 EVT *Array = Allocator.Allocate<EVT>(3);
5039 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5040 VTListMap.InsertNode(Result, IP);
5042 return Result->getSDVTList();
5045 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5046 FoldingSetNodeID ID;
5048 ID.AddInteger(VT1.getRawBits());
5049 ID.AddInteger(VT2.getRawBits());
5050 ID.AddInteger(VT3.getRawBits());
5051 ID.AddInteger(VT4.getRawBits());
5054 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5055 if (Result == NULL) {
5056 EVT *Array = Allocator.Allocate<EVT>(4);
5061 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5062 VTListMap.InsertNode(Result, IP);
5064 return Result->getSDVTList();
5067 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
5068 FoldingSetNodeID ID;
5069 ID.AddInteger(NumVTs);
5070 for (unsigned index = 0; index < NumVTs; index++) {
5071 ID.AddInteger(VTs[index].getRawBits());
5075 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5076 if (Result == NULL) {
5077 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5078 std::copy(VTs, VTs + NumVTs, Array);
5079 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5080 VTListMap.InsertNode(Result, IP);
5082 return Result->getSDVTList();
5086 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5087 /// specified operands. If the resultant node already exists in the DAG,
5088 /// this does not modify the specified node, instead it returns the node that
5089 /// already exists. If the resultant node does not exist in the DAG, the
5090 /// input node is returned. As a degenerate case, if you specify the same
5091 /// input operands as the node already has, the input node is returned.
5092 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5093 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5095 // Check to see if there is no change.
5096 if (Op == N->getOperand(0)) return N;
5098 // See if the modified node already exists.
5099 void *InsertPos = 0;
5100 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5103 // Nope it doesn't. Remove the node from its current place in the maps.
5105 if (!RemoveNodeFromCSEMaps(N))
5108 // Now we update the operands.
5109 N->OperandList[0].set(Op);
5111 // If this gets put into a CSE map, add it.
5112 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5116 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5117 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5119 // Check to see if there is no change.
5120 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5121 return N; // No operands changed, just return the input node.
5123 // See if the modified node already exists.
5124 void *InsertPos = 0;
5125 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5128 // Nope it doesn't. Remove the node from its current place in the maps.
5130 if (!RemoveNodeFromCSEMaps(N))
5133 // Now we update the operands.
5134 if (N->OperandList[0] != Op1)
5135 N->OperandList[0].set(Op1);
5136 if (N->OperandList[1] != Op2)
5137 N->OperandList[1].set(Op2);
5139 // If this gets put into a CSE map, add it.
5140 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5144 SDNode *SelectionDAG::
5145 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5146 SDValue Ops[] = { Op1, Op2, Op3 };
5147 return UpdateNodeOperands(N, Ops, 3);
5150 SDNode *SelectionDAG::
5151 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5152 SDValue Op3, SDValue Op4) {
5153 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5154 return UpdateNodeOperands(N, Ops, 4);
5157 SDNode *SelectionDAG::
5158 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5159 SDValue Op3, SDValue Op4, SDValue Op5) {
5160 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5161 return UpdateNodeOperands(N, Ops, 5);
5164 SDNode *SelectionDAG::
5165 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
5166 assert(N->getNumOperands() == NumOps &&
5167 "Update with wrong number of operands");
5169 // Check to see if there is no change.
5170 bool AnyChange = false;
5171 for (unsigned i = 0; i != NumOps; ++i) {
5172 if (Ops[i] != N->getOperand(i)) {
5178 // No operands changed, just return the input node.
5179 if (!AnyChange) return N;
5181 // See if the modified node already exists.
5182 void *InsertPos = 0;
5183 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
5186 // Nope it doesn't. Remove the node from its current place in the maps.
5188 if (!RemoveNodeFromCSEMaps(N))
5191 // Now we update the operands.
5192 for (unsigned i = 0; i != NumOps; ++i)
5193 if (N->OperandList[i] != Ops[i])
5194 N->OperandList[i].set(Ops[i]);
5196 // If this gets put into a CSE map, add it.
5197 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5201 /// DropOperands - Release the operands and set this node to have
5203 void SDNode::DropOperands() {
5204 // Unlike the code in MorphNodeTo that does this, we don't need to
5205 // watch for dead nodes here.
5206 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5212 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5215 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5217 SDVTList VTs = getVTList(VT);
5218 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
5221 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5222 EVT VT, SDValue Op1) {
5223 SDVTList VTs = getVTList(VT);
5224 SDValue Ops[] = { Op1 };
5225 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5228 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5229 EVT VT, SDValue Op1,
5231 SDVTList VTs = getVTList(VT);
5232 SDValue Ops[] = { Op1, Op2 };
5233 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5236 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5237 EVT VT, SDValue Op1,
5238 SDValue Op2, SDValue Op3) {
5239 SDVTList VTs = getVTList(VT);
5240 SDValue Ops[] = { Op1, Op2, Op3 };
5241 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5244 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5245 EVT VT, const SDValue *Ops,
5247 SDVTList VTs = getVTList(VT);
5248 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5251 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5252 EVT VT1, EVT VT2, const SDValue *Ops,
5254 SDVTList VTs = getVTList(VT1, VT2);
5255 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5258 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5260 SDVTList VTs = getVTList(VT1, VT2);
5261 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
5264 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5265 EVT VT1, EVT VT2, EVT VT3,
5266 const SDValue *Ops, unsigned NumOps) {
5267 SDVTList VTs = getVTList(VT1, VT2, VT3);
5268 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5271 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5272 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5273 const SDValue *Ops, unsigned NumOps) {
5274 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5275 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
5278 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5281 SDVTList VTs = getVTList(VT1, VT2);
5282 SDValue Ops[] = { Op1 };
5283 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
5286 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5288 SDValue Op1, SDValue Op2) {
5289 SDVTList VTs = getVTList(VT1, VT2);
5290 SDValue Ops[] = { Op1, Op2 };
5291 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
5294 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5296 SDValue Op1, SDValue Op2,
5298 SDVTList VTs = getVTList(VT1, VT2);
5299 SDValue Ops[] = { Op1, Op2, Op3 };
5300 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5303 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5304 EVT VT1, EVT VT2, EVT VT3,
5305 SDValue Op1, SDValue Op2,
5307 SDVTList VTs = getVTList(VT1, VT2, VT3);
5308 SDValue Ops[] = { Op1, Op2, Op3 };
5309 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
5312 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5313 SDVTList VTs, const SDValue *Ops,
5315 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
5316 // Reset the NodeID to -1.
5321 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5322 /// the line number information on the merged node since it is not possible to
5323 /// preserve the information that operation is associated with multiple lines.
5324 /// This will make the debugger working better at -O0, were there is a higher
5325 /// probability having other instructions associated with that line.
5327 /// For IROrder, we keep the smaller of the two
5328 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5329 DebugLoc NLoc = N->getDebugLoc();
5330 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5331 (OLoc.getDebugLoc() != NLoc)) {
5332 N->setDebugLoc(DebugLoc());
5334 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5335 N->setIROrder(Order);
5339 /// MorphNodeTo - This *mutates* the specified node to have the specified
5340 /// return type, opcode, and operands.
5342 /// Note that MorphNodeTo returns the resultant node. If there is already a
5343 /// node of the specified opcode and operands, it returns that node instead of
5344 /// the current one. Note that the SDLoc need not be the same.
5346 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5347 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5348 /// node, and because it doesn't require CSE recalculation for any of
5349 /// the node's users.
5351 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5352 SDVTList VTs, const SDValue *Ops,
5354 // If an identical node already exists, use it.
5356 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5357 FoldingSetNodeID ID;
5358 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
5359 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5360 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5363 if (!RemoveNodeFromCSEMaps(N))
5366 // Start the morphing.
5368 N->ValueList = VTs.VTs;
5369 N->NumValues = VTs.NumVTs;
5371 // Clear the operands list, updating used nodes to remove this from their
5372 // use list. Keep track of any operands that become dead as a result.
5373 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5374 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5376 SDNode *Used = Use.getNode();
5378 if (Used->use_empty())
5379 DeadNodeSet.insert(Used);
5382 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5383 // Initialize the memory references information.
5384 MN->setMemRefs(0, 0);
5385 // If NumOps is larger than the # of operands we can have in a
5386 // MachineSDNode, reallocate the operand list.
5387 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5388 if (MN->OperandsNeedDelete)
5389 delete[] MN->OperandList;
5390 if (NumOps > array_lengthof(MN->LocalOperands))
5391 // We're creating a final node that will live unmorphed for the
5392 // remainder of the current SelectionDAG iteration, so we can allocate
5393 // the operands directly out of a pool with no recycling metadata.
5394 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5397 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
5398 MN->OperandsNeedDelete = false;
5400 MN->InitOperands(MN->OperandList, Ops, NumOps);
5402 // If NumOps is larger than the # of operands we currently have, reallocate
5403 // the operand list.
5404 if (NumOps > N->NumOperands) {
5405 if (N->OperandsNeedDelete)
5406 delete[] N->OperandList;
5407 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
5408 N->OperandsNeedDelete = true;
5410 N->InitOperands(N->OperandList, Ops, NumOps);
5413 // Delete any nodes that are still dead after adding the uses for the
5415 if (!DeadNodeSet.empty()) {
5416 SmallVector<SDNode *, 16> DeadNodes;
5417 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5418 E = DeadNodeSet.end(); I != E; ++I)
5419 if ((*I)->use_empty())
5420 DeadNodes.push_back(*I);
5421 RemoveDeadNodes(DeadNodes);
5425 CSEMap.InsertNode(N, IP); // Memoize the new node.
5430 /// getMachineNode - These are used for target selectors to create a new node
5431 /// with specified return type(s), MachineInstr opcode, and operands.
5433 /// Note that getMachineNode returns the resultant node. If there is already a
5434 /// node of the specified opcode and operands, it returns that node instead of
5435 /// the current one.
5437 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5438 SDVTList VTs = getVTList(VT);
5439 return getMachineNode(Opcode, dl, VTs, None);
5443 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5444 SDVTList VTs = getVTList(VT);
5445 SDValue Ops[] = { Op1 };
5446 return getMachineNode(Opcode, dl, VTs, Ops);
5450 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5451 SDValue Op1, SDValue Op2) {
5452 SDVTList VTs = getVTList(VT);
5453 SDValue Ops[] = { Op1, Op2 };
5454 return getMachineNode(Opcode, dl, VTs, Ops);
5458 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5459 SDValue Op1, SDValue Op2, SDValue Op3) {
5460 SDVTList VTs = getVTList(VT);
5461 SDValue Ops[] = { Op1, Op2, Op3 };
5462 return getMachineNode(Opcode, dl, VTs, Ops);
5466 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5467 ArrayRef<SDValue> Ops) {
5468 SDVTList VTs = getVTList(VT);
5469 return getMachineNode(Opcode, dl, VTs, Ops);
5473 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5474 SDVTList VTs = getVTList(VT1, VT2);
5475 return getMachineNode(Opcode, dl, VTs, None);
5479 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5480 EVT VT1, EVT VT2, SDValue Op1) {
5481 SDVTList VTs = getVTList(VT1, VT2);
5482 SDValue Ops[] = { Op1 };
5483 return getMachineNode(Opcode, dl, VTs, Ops);
5487 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5488 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5489 SDVTList VTs = getVTList(VT1, VT2);
5490 SDValue Ops[] = { Op1, Op2 };
5491 return getMachineNode(Opcode, dl, VTs, Ops);
5495 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5496 EVT VT1, EVT VT2, SDValue Op1,
5497 SDValue Op2, SDValue Op3) {
5498 SDVTList VTs = getVTList(VT1, VT2);
5499 SDValue Ops[] = { Op1, Op2, Op3 };
5500 return getMachineNode(Opcode, dl, VTs, Ops);
5504 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5506 ArrayRef<SDValue> Ops) {
5507 SDVTList VTs = getVTList(VT1, VT2);
5508 return getMachineNode(Opcode, dl, VTs, Ops);
5512 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5513 EVT VT1, EVT VT2, EVT VT3,
5514 SDValue Op1, SDValue Op2) {
5515 SDVTList VTs = getVTList(VT1, VT2, VT3);
5516 SDValue Ops[] = { Op1, Op2 };
5517 return getMachineNode(Opcode, dl, VTs, Ops);
5521 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5522 EVT VT1, EVT VT2, EVT VT3,
5523 SDValue Op1, SDValue Op2, SDValue Op3) {
5524 SDVTList VTs = getVTList(VT1, VT2, VT3);
5525 SDValue Ops[] = { Op1, Op2, Op3 };
5526 return getMachineNode(Opcode, dl, VTs, Ops);
5530 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5531 EVT VT1, EVT VT2, EVT VT3,
5532 ArrayRef<SDValue> Ops) {
5533 SDVTList VTs = getVTList(VT1, VT2, VT3);
5534 return getMachineNode(Opcode, dl, VTs, Ops);
5538 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5539 EVT VT2, EVT VT3, EVT VT4,
5540 ArrayRef<SDValue> Ops) {
5541 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5542 return getMachineNode(Opcode, dl, VTs, Ops);
5546 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5547 ArrayRef<EVT> ResultTys,
5548 ArrayRef<SDValue> Ops) {
5549 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5550 return getMachineNode(Opcode, dl, VTs, Ops);
5554 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5555 ArrayRef<SDValue> OpsArray) {
5556 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5559 const SDValue *Ops = OpsArray.data();
5560 unsigned NumOps = OpsArray.size();
5563 FoldingSetNodeID ID;
5564 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5566 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5567 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5571 // Allocate a new MachineSDNode.
5572 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5573 DL.getDebugLoc(), VTs);
5575 // Initialize the operands list.
5576 if (NumOps > array_lengthof(N->LocalOperands))
5577 // We're creating a final node that will live unmorphed for the
5578 // remainder of the current SelectionDAG iteration, so we can allocate
5579 // the operands directly out of a pool with no recycling metadata.
5580 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5583 N->InitOperands(N->LocalOperands, Ops, NumOps);
5584 N->OperandsNeedDelete = false;
5587 CSEMap.InsertNode(N, IP);
5589 AllNodes.push_back(N);
5591 VerifyMachineNode(N);
5596 /// getTargetExtractSubreg - A convenience function for creating
5597 /// TargetOpcode::EXTRACT_SUBREG nodes.
5599 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5601 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5602 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5603 VT, Operand, SRIdxVal);
5604 return SDValue(Subreg, 0);
5607 /// getTargetInsertSubreg - A convenience function for creating
5608 /// TargetOpcode::INSERT_SUBREG nodes.
5610 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5611 SDValue Operand, SDValue Subreg) {
5612 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5613 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5614 VT, Operand, Subreg, SRIdxVal);
5615 return SDValue(Result, 0);
5618 /// getNodeIfExists - Get the specified node if it's already available, or
5619 /// else return NULL.
5620 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5621 const SDValue *Ops, unsigned NumOps) {
5622 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5623 FoldingSetNodeID ID;
5624 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5632 /// getDbgValue - Creates a SDDbgValue node.
5635 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5636 DebugLoc DL, unsigned O) {
5637 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5641 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5642 DebugLoc DL, unsigned O) {
5643 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5647 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5648 DebugLoc DL, unsigned O) {
5649 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5654 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5655 /// pointed to by a use iterator is deleted, increment the use iterator
5656 /// so that it doesn't dangle.
5658 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5659 SDNode::use_iterator &UI;
5660 SDNode::use_iterator &UE;
5662 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5663 // Increment the iterator as needed.
5664 while (UI != UE && N == *UI)
5669 RAUWUpdateListener(SelectionDAG &d,
5670 SDNode::use_iterator &ui,
5671 SDNode::use_iterator &ue)
5672 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5677 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5678 /// This can cause recursive merging of nodes in the DAG.
5680 /// This version assumes From has a single result value.
5682 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5683 SDNode *From = FromN.getNode();
5684 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5685 "Cannot replace with this method!");
5686 assert(From != To.getNode() && "Cannot replace uses of with self");
5688 // Iterate over all the existing uses of From. New uses will be added
5689 // to the beginning of the use list, which we avoid visiting.
5690 // This specifically avoids visiting uses of From that arise while the
5691 // replacement is happening, because any such uses would be the result
5692 // of CSE: If an existing node looks like From after one of its operands
5693 // is replaced by To, we don't want to replace of all its users with To
5694 // too. See PR3018 for more info.
5695 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5696 RAUWUpdateListener Listener(*this, UI, UE);
5700 // This node is about to morph, remove its old self from the CSE maps.
5701 RemoveNodeFromCSEMaps(User);
5703 // A user can appear in a use list multiple times, and when this
5704 // happens the uses are usually next to each other in the list.
5705 // To help reduce the number of CSE recomputations, process all
5706 // the uses of this user that we can find this way.
5708 SDUse &Use = UI.getUse();
5711 } while (UI != UE && *UI == User);
5713 // Now that we have modified User, add it back to the CSE maps. If it
5714 // already exists there, recursively merge the results together.
5715 AddModifiedNodeToCSEMaps(User);
5718 // If we just RAUW'd the root, take note.
5719 if (FromN == getRoot())
5723 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5724 /// This can cause recursive merging of nodes in the DAG.
5726 /// This version assumes that for each value of From, there is a
5727 /// corresponding value in To in the same position with the same type.
5729 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5731 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5732 assert((!From->hasAnyUseOfValue(i) ||
5733 From->getValueType(i) == To->getValueType(i)) &&
5734 "Cannot use this version of ReplaceAllUsesWith!");
5737 // Handle the trivial case.
5741 // Iterate over just the existing users of From. See the comments in
5742 // the ReplaceAllUsesWith above.
5743 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5744 RAUWUpdateListener Listener(*this, UI, UE);
5748 // This node is about to morph, remove its old self from the CSE maps.
5749 RemoveNodeFromCSEMaps(User);
5751 // A user can appear in a use list multiple times, and when this
5752 // happens the uses are usually next to each other in the list.
5753 // To help reduce the number of CSE recomputations, process all
5754 // the uses of this user that we can find this way.
5756 SDUse &Use = UI.getUse();
5759 } while (UI != UE && *UI == User);
5761 // Now that we have modified User, add it back to the CSE maps. If it
5762 // already exists there, recursively merge the results together.
5763 AddModifiedNodeToCSEMaps(User);
5766 // If we just RAUW'd the root, take note.
5767 if (From == getRoot().getNode())
5768 setRoot(SDValue(To, getRoot().getResNo()));
5771 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5772 /// This can cause recursive merging of nodes in the DAG.
5774 /// This version can replace From with any result values. To must match the
5775 /// number and types of values returned by From.
5776 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5777 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5778 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5780 // Iterate over just the existing users of From. See the comments in
5781 // the ReplaceAllUsesWith above.
5782 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5783 RAUWUpdateListener Listener(*this, UI, UE);
5787 // This node is about to morph, remove its old self from the CSE maps.
5788 RemoveNodeFromCSEMaps(User);
5790 // A user can appear in a use list multiple times, and when this
5791 // happens the uses are usually next to each other in the list.
5792 // To help reduce the number of CSE recomputations, process all
5793 // the uses of this user that we can find this way.
5795 SDUse &Use = UI.getUse();
5796 const SDValue &ToOp = To[Use.getResNo()];
5799 } while (UI != UE && *UI == User);
5801 // Now that we have modified User, add it back to the CSE maps. If it
5802 // already exists there, recursively merge the results together.
5803 AddModifiedNodeToCSEMaps(User);
5806 // If we just RAUW'd the root, take note.
5807 if (From == getRoot().getNode())
5808 setRoot(SDValue(To[getRoot().getResNo()]));
5811 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5812 /// uses of other values produced by From.getNode() alone. The Deleted
5813 /// vector is handled the same way as for ReplaceAllUsesWith.
5814 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5815 // Handle the really simple, really trivial case efficiently.
5816 if (From == To) return;
5818 // Handle the simple, trivial, case efficiently.
5819 if (From.getNode()->getNumValues() == 1) {
5820 ReplaceAllUsesWith(From, To);
5824 // Iterate over just the existing users of From. See the comments in
5825 // the ReplaceAllUsesWith above.
5826 SDNode::use_iterator UI = From.getNode()->use_begin(),
5827 UE = From.getNode()->use_end();
5828 RAUWUpdateListener Listener(*this, UI, UE);
5831 bool UserRemovedFromCSEMaps = false;
5833 // A user can appear in a use list multiple times, and when this
5834 // happens the uses are usually next to each other in the list.
5835 // To help reduce the number of CSE recomputations, process all
5836 // the uses of this user that we can find this way.
5838 SDUse &Use = UI.getUse();
5840 // Skip uses of different values from the same node.
5841 if (Use.getResNo() != From.getResNo()) {
5846 // If this node hasn't been modified yet, it's still in the CSE maps,
5847 // so remove its old self from the CSE maps.
5848 if (!UserRemovedFromCSEMaps) {
5849 RemoveNodeFromCSEMaps(User);
5850 UserRemovedFromCSEMaps = true;
5855 } while (UI != UE && *UI == User);
5857 // We are iterating over all uses of the From node, so if a use
5858 // doesn't use the specific value, no changes are made.
5859 if (!UserRemovedFromCSEMaps)
5862 // Now that we have modified User, add it back to the CSE maps. If it
5863 // already exists there, recursively merge the results together.
5864 AddModifiedNodeToCSEMaps(User);
5867 // If we just RAUW'd the root, take note.
5868 if (From == getRoot())
5873 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5874 /// to record information about a use.
5881 /// operator< - Sort Memos by User.
5882 bool operator<(const UseMemo &L, const UseMemo &R) {
5883 return (intptr_t)L.User < (intptr_t)R.User;
5887 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5888 /// uses of other values produced by From.getNode() alone. The same value
5889 /// may appear in both the From and To list. The Deleted vector is
5890 /// handled the same way as for ReplaceAllUsesWith.
5891 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5894 // Handle the simple, trivial case efficiently.
5896 return ReplaceAllUsesOfValueWith(*From, *To);
5898 // Read up all the uses and make records of them. This helps
5899 // processing new uses that are introduced during the
5900 // replacement process.
5901 SmallVector<UseMemo, 4> Uses;
5902 for (unsigned i = 0; i != Num; ++i) {
5903 unsigned FromResNo = From[i].getResNo();
5904 SDNode *FromNode = From[i].getNode();
5905 for (SDNode::use_iterator UI = FromNode->use_begin(),
5906 E = FromNode->use_end(); UI != E; ++UI) {
5907 SDUse &Use = UI.getUse();
5908 if (Use.getResNo() == FromResNo) {
5909 UseMemo Memo = { *UI, i, &Use };
5910 Uses.push_back(Memo);
5915 // Sort the uses, so that all the uses from a given User are together.
5916 std::sort(Uses.begin(), Uses.end());
5918 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5919 UseIndex != UseIndexEnd; ) {
5920 // We know that this user uses some value of From. If it is the right
5921 // value, update it.
5922 SDNode *User = Uses[UseIndex].User;
5924 // This node is about to morph, remove its old self from the CSE maps.
5925 RemoveNodeFromCSEMaps(User);
5927 // The Uses array is sorted, so all the uses for a given User
5928 // are next to each other in the list.
5929 // To help reduce the number of CSE recomputations, process all
5930 // the uses of this user that we can find this way.
5932 unsigned i = Uses[UseIndex].Index;
5933 SDUse &Use = *Uses[UseIndex].Use;
5937 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5939 // Now that we have modified User, add it back to the CSE maps. If it
5940 // already exists there, recursively merge the results together.
5941 AddModifiedNodeToCSEMaps(User);
5945 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5946 /// based on their topological order. It returns the maximum id and a vector
5947 /// of the SDNodes* in assigned order by reference.
5948 unsigned SelectionDAG::AssignTopologicalOrder() {
5950 unsigned DAGSize = 0;
5952 // SortedPos tracks the progress of the algorithm. Nodes before it are
5953 // sorted, nodes after it are unsorted. When the algorithm completes
5954 // it is at the end of the list.
5955 allnodes_iterator SortedPos = allnodes_begin();
5957 // Visit all the nodes. Move nodes with no operands to the front of
5958 // the list immediately. Annotate nodes that do have operands with their
5959 // operand count. Before we do this, the Node Id fields of the nodes
5960 // may contain arbitrary values. After, the Node Id fields for nodes
5961 // before SortedPos will contain the topological sort index, and the
5962 // Node Id fields for nodes At SortedPos and after will contain the
5963 // count of outstanding operands.
5964 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5967 unsigned Degree = N->getNumOperands();
5969 // A node with no uses, add it to the result array immediately.
5970 N->setNodeId(DAGSize++);
5971 allnodes_iterator Q = N;
5973 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5974 assert(SortedPos != AllNodes.end() && "Overran node list");
5977 // Temporarily use the Node Id as scratch space for the degree count.
5978 N->setNodeId(Degree);
5982 // Visit all the nodes. As we iterate, move nodes into sorted order,
5983 // such that by the time the end is reached all nodes will be sorted.
5984 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5987 // N is in sorted position, so all its uses have one less operand
5988 // that needs to be sorted.
5989 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5992 unsigned Degree = P->getNodeId();
5993 assert(Degree != 0 && "Invalid node degree");
5996 // All of P's operands are sorted, so P may sorted now.
5997 P->setNodeId(DAGSize++);
5999 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6000 assert(SortedPos != AllNodes.end() && "Overran node list");
6003 // Update P's outstanding operand count.
6004 P->setNodeId(Degree);
6007 if (I == SortedPos) {
6010 dbgs() << "Overran sorted position:\n";
6013 llvm_unreachable(0);
6017 assert(SortedPos == AllNodes.end() &&
6018 "Topological sort incomplete!");
6019 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6020 "First node in topological sort is not the entry token!");
6021 assert(AllNodes.front().getNodeId() == 0 &&
6022 "First node in topological sort has non-zero id!");
6023 assert(AllNodes.front().getNumOperands() == 0 &&
6024 "First node in topological sort has operands!");
6025 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6026 "Last node in topologic sort has unexpected id!");
6027 assert(AllNodes.back().use_empty() &&
6028 "Last node in topologic sort has users!");
6029 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6033 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6034 /// value is produced by SD.
6035 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6036 DbgInfo->add(DB, SD, isParameter);
6038 SD->setHasDebugValue(true);
6041 /// TransferDbgValues - Transfer SDDbgValues.
6042 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6043 if (From == To || !From.getNode()->getHasDebugValue())
6045 SDNode *FromNode = From.getNode();
6046 SDNode *ToNode = To.getNode();
6047 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6048 SmallVector<SDDbgValue *, 2> ClonedDVs;
6049 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6051 SDDbgValue *Dbg = *I;
6052 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6053 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6054 Dbg->getOffset(), Dbg->getDebugLoc(),
6056 ClonedDVs.push_back(Clone);
6059 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6060 E = ClonedDVs.end(); I != E; ++I)
6061 AddDbgValue(*I, ToNode, false);
6064 //===----------------------------------------------------------------------===//
6066 //===----------------------------------------------------------------------===//
6068 HandleSDNode::~HandleSDNode() {
6072 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6073 DebugLoc DL, const GlobalValue *GA,
6074 EVT VT, int64_t o, unsigned char TF)
6075 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6079 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6080 SDValue X, unsigned SrcAS,
6082 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6083 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6085 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6086 EVT memvt, MachineMemOperand *mmo)
6087 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6088 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6089 MMO->isNonTemporal(), MMO->isInvariant());
6090 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6091 assert(isNonTemporal() == MMO->isNonTemporal() &&
6092 "Non-temporal encoding error!");
6093 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6096 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6097 const SDValue *Ops, unsigned NumOps, EVT memvt,
6098 MachineMemOperand *mmo)
6099 : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
6100 MemoryVT(memvt), MMO(mmo) {
6101 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6102 MMO->isNonTemporal(), MMO->isInvariant());
6103 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6104 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6107 /// Profile - Gather unique data for the node.
6109 void SDNode::Profile(FoldingSetNodeID &ID) const {
6110 AddNodeIDNode(ID, this);
6115 std::vector<EVT> VTs;
6118 VTs.reserve(MVT::LAST_VALUETYPE);
6119 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6120 VTs.push_back(MVT((MVT::SimpleValueType)i));
6125 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6126 static ManagedStatic<EVTArray> SimpleVTArray;
6127 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6129 /// getValueTypeList - Return a pointer to the specified value type.
6131 const EVT *SDNode::getValueTypeList(EVT VT) {
6132 if (VT.isExtended()) {
6133 sys::SmartScopedLock<true> Lock(*VTMutex);
6134 return &(*EVTs->insert(VT).first);
6136 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6137 "Value type out of range!");
6138 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6142 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6143 /// indicated value. This method ignores uses of other values defined by this
6145 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6146 assert(Value < getNumValues() && "Bad value!");
6148 // TODO: Only iterate over uses of a given value of the node
6149 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6150 if (UI.getUse().getResNo() == Value) {
6157 // Found exactly the right number of uses?
6162 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6163 /// value. This method ignores uses of other values defined by this operation.
6164 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6165 assert(Value < getNumValues() && "Bad value!");
6167 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6168 if (UI.getUse().getResNo() == Value)
6175 /// isOnlyUserOf - Return true if this node is the only use of N.
6177 bool SDNode::isOnlyUserOf(SDNode *N) const {
6179 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6190 /// isOperand - Return true if this node is an operand of N.
6192 bool SDValue::isOperandOf(SDNode *N) const {
6193 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6194 if (*this == N->getOperand(i))
6199 bool SDNode::isOperandOf(SDNode *N) const {
6200 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6201 if (this == N->OperandList[i].getNode())
6206 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6207 /// be a chain) reaches the specified operand without crossing any
6208 /// side-effecting instructions on any chain path. In practice, this looks
6209 /// through token factors and non-volatile loads. In order to remain efficient,
6210 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6211 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6212 unsigned Depth) const {
6213 if (*this == Dest) return true;
6215 // Don't search too deeply, we just want to be able to see through
6216 // TokenFactor's etc.
6217 if (Depth == 0) return false;
6219 // If this is a token factor, all inputs to the TF happen in parallel. If any
6220 // of the operands of the TF does not reach dest, then we cannot do the xform.
6221 if (getOpcode() == ISD::TokenFactor) {
6222 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6223 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6228 // Loads don't have side effects, look through them.
6229 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6230 if (!Ld->isVolatile())
6231 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6236 /// hasPredecessor - Return true if N is a predecessor of this node.
6237 /// N is either an operand of this node, or can be reached by recursively
6238 /// traversing up the operands.
6239 /// NOTE: This is an expensive method. Use it carefully.
6240 bool SDNode::hasPredecessor(const SDNode *N) const {
6241 SmallPtrSet<const SDNode *, 32> Visited;
6242 SmallVector<const SDNode *, 16> Worklist;
6243 return hasPredecessorHelper(N, Visited, Worklist);
6247 SDNode::hasPredecessorHelper(const SDNode *N,
6248 SmallPtrSet<const SDNode *, 32> &Visited,
6249 SmallVectorImpl<const SDNode *> &Worklist) const {
6250 if (Visited.empty()) {
6251 Worklist.push_back(this);
6253 // Take a look in the visited set. If we've already encountered this node
6254 // we needn't search further.
6255 if (Visited.count(N))
6259 // Haven't visited N yet. Continue the search.
6260 while (!Worklist.empty()) {
6261 const SDNode *M = Worklist.pop_back_val();
6262 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6263 SDNode *Op = M->getOperand(i).getNode();
6264 if (Visited.insert(Op))
6265 Worklist.push_back(Op);
6274 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6275 assert(Num < NumOperands && "Invalid child # of SDNode!");
6276 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6279 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6280 assert(N->getNumValues() == 1 &&
6281 "Can't unroll a vector with multiple results!");
6283 EVT VT = N->getValueType(0);
6284 unsigned NE = VT.getVectorNumElements();
6285 EVT EltVT = VT.getVectorElementType();
6288 SmallVector<SDValue, 8> Scalars;
6289 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6291 // If ResNE is 0, fully unroll the vector op.
6294 else if (NE > ResNE)
6298 for (i= 0; i != NE; ++i) {
6299 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6300 SDValue Operand = N->getOperand(j);
6301 EVT OperandVT = Operand.getValueType();
6302 if (OperandVT.isVector()) {
6303 // A vector operand; extract a single element.
6304 const TargetLowering *TLI = TM.getTargetLowering();
6305 EVT OperandEltVT = OperandVT.getVectorElementType();
6306 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6309 getConstant(i, TLI->getVectorIdxTy()));
6311 // A scalar operand; just use it as is.
6312 Operands[j] = Operand;
6316 switch (N->getOpcode()) {
6318 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6319 &Operands[0], Operands.size()));
6322 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6323 &Operands[0], Operands.size()));
6330 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6331 getShiftAmountOperand(Operands[0].getValueType(),
6334 case ISD::SIGN_EXTEND_INREG:
6335 case ISD::FP_ROUND_INREG: {
6336 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6337 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6339 getValueType(ExtVT)));
6344 for (; i < ResNE; ++i)
6345 Scalars.push_back(getUNDEF(EltVT));
6347 return getNode(ISD::BUILD_VECTOR, dl,
6348 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6349 &Scalars[0], Scalars.size());
6353 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6354 /// location that is 'Dist' units away from the location that the 'Base' load
6355 /// is loading from.
6356 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6357 unsigned Bytes, int Dist) const {
6358 if (LD->getChain() != Base->getChain())
6360 EVT VT = LD->getValueType(0);
6361 if (VT.getSizeInBits() / 8 != Bytes)
6364 SDValue Loc = LD->getOperand(1);
6365 SDValue BaseLoc = Base->getOperand(1);
6366 if (Loc.getOpcode() == ISD::FrameIndex) {
6367 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6369 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6370 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6371 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6372 int FS = MFI->getObjectSize(FI);
6373 int BFS = MFI->getObjectSize(BFI);
6374 if (FS != BFS || FS != (int)Bytes) return false;
6375 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6379 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6380 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6383 const GlobalValue *GV1 = NULL;
6384 const GlobalValue *GV2 = NULL;
6385 int64_t Offset1 = 0;
6386 int64_t Offset2 = 0;
6387 const TargetLowering *TLI = TM.getTargetLowering();
6388 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6389 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6390 if (isGA1 && isGA2 && GV1 == GV2)
6391 return Offset1 == (Offset2 + Dist*Bytes);
6396 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6397 /// it cannot be inferred.
6398 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6399 // If this is a GlobalAddress + cst, return the alignment.
6400 const GlobalValue *GV;
6401 int64_t GVOffset = 0;
6402 const TargetLowering *TLI = TM.getTargetLowering();
6403 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6404 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6405 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6406 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6407 TLI->getDataLayout());
6408 unsigned AlignBits = KnownZero.countTrailingOnes();
6409 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6411 return MinAlign(Align, GVOffset);
6414 // If this is a direct reference to a stack slot, use information about the
6415 // stack slot's alignment.
6416 int FrameIdx = 1 << 31;
6417 int64_t FrameOffset = 0;
6418 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6419 FrameIdx = FI->getIndex();
6420 } else if (isBaseWithConstantOffset(Ptr) &&
6421 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6423 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6424 FrameOffset = Ptr.getConstantOperandVal(1);
6427 if (FrameIdx != (1 << 31)) {
6428 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6429 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6437 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6438 /// which is split (or expanded) into two not necessarily identical pieces.
6439 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6440 // Currently all types are split in half.
6442 if (!VT.isVector()) {
6443 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6445 unsigned NumElements = VT.getVectorNumElements();
6446 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6447 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6450 return std::make_pair(LoVT, HiVT);
6453 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6455 std::pair<SDValue, SDValue>
6456 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6458 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6459 N.getValueType().getVectorNumElements() &&
6460 "More vector elements requested than available!");
6462 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6463 getConstant(0, TLI->getVectorIdxTy()));
6464 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6465 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6466 return std::make_pair(Lo, Hi);
6469 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6470 unsigned GlobalAddressSDNode::getAddressSpace() const {
6471 return getGlobal()->getType()->getAddressSpace();
6475 Type *ConstantPoolSDNode::getType() const {
6476 if (isMachineConstantPoolEntry())
6477 return Val.MachineCPVal->getType();
6478 return Val.ConstVal->getType();
6481 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6483 unsigned &SplatBitSize,
6485 unsigned MinSplatBits,
6486 bool isBigEndian) const {
6487 EVT VT = getValueType(0);
6488 assert(VT.isVector() && "Expected a vector type");
6489 unsigned sz = VT.getSizeInBits();
6490 if (MinSplatBits > sz)
6493 SplatValue = APInt(sz, 0);
6494 SplatUndef = APInt(sz, 0);
6496 // Get the bits. Bits with undefined values (when the corresponding element
6497 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6498 // in SplatValue. If any of the values are not constant, give up and return
6500 unsigned int nOps = getNumOperands();
6501 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6502 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6504 for (unsigned j = 0; j < nOps; ++j) {
6505 unsigned i = isBigEndian ? nOps-1-j : j;
6506 SDValue OpVal = getOperand(i);
6507 unsigned BitPos = j * EltBitSize;
6509 if (OpVal.getOpcode() == ISD::UNDEF)
6510 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6511 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6512 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6513 zextOrTrunc(sz) << BitPos;
6514 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6515 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6520 // The build_vector is all constants or undefs. Find the smallest element
6521 // size that splats the vector.
6523 HasAnyUndefs = (SplatUndef != 0);
6526 unsigned HalfSize = sz / 2;
6527 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6528 APInt LowValue = SplatValue.trunc(HalfSize);
6529 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6530 APInt LowUndef = SplatUndef.trunc(HalfSize);
6532 // If the two halves do not match (ignoring undef bits), stop here.
6533 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6534 MinSplatBits > HalfSize)
6537 SplatValue = HighValue | LowValue;
6538 SplatUndef = HighUndef & LowUndef;
6547 bool BuildVectorSDNode::isConstant() const {
6548 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6549 unsigned Opc = getOperand(i).getOpcode();
6550 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6556 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6557 // Find the first non-undef value in the shuffle mask.
6559 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6562 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6564 // Make sure all remaining elements are either undef or the same as the first
6566 for (int Idx = Mask[i]; i != e; ++i)
6567 if (Mask[i] >= 0 && Mask[i] != Idx)
6573 static void checkForCyclesHelper(const SDNode *N,
6574 SmallPtrSet<const SDNode*, 32> &Visited,
6575 SmallPtrSet<const SDNode*, 32> &Checked) {
6576 // If this node has already been checked, don't check it again.
6577 if (Checked.count(N))
6580 // If a node has already been visited on this depth-first walk, reject it as
6582 if (!Visited.insert(N)) {
6583 dbgs() << "Offending node:\n";
6585 errs() << "Detected cycle in SelectionDAG\n";
6589 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6590 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6597 void llvm::checkForCycles(const llvm::SDNode *N) {
6599 assert(N && "Checking nonexistent SDNode");
6600 SmallPtrSet<const SDNode*, 32> visited;
6601 SmallPtrSet<const SDNode*, 32> checked;
6602 checkForCyclesHelper(N, visited, checked);
6606 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6607 checkForCycles(DAG->getRoot().getNode());