1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeOrdering.h"
16 #include "SDNodeDbgValue.h"
17 #include "llvm/Constants.h"
18 #include "llvm/Analysis/DebugInfo.h"
19 #include "llvm/Analysis/ValueTracking.h"
20 #include "llvm/Function.h"
21 #include "llvm/GlobalAlias.h"
22 #include "llvm/GlobalVariable.h"
23 #include "llvm/Intrinsics.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/Assembly/Writer.h"
26 #include "llvm/CallingConv.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineConstantPool.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineModuleInfo.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetData.h"
33 #include "llvm/Target/TargetLowering.h"
34 #include "llvm/Target/TargetSelectionDAGInfo.h"
35 #include "llvm/Target/TargetOptions.h"
36 #include "llvm/Target/TargetInstrInfo.h"
37 #include "llvm/Target/TargetIntrinsicInfo.h"
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/ErrorHandling.h"
42 #include "llvm/Support/ManagedStatic.h"
43 #include "llvm/Support/MathExtras.h"
44 #include "llvm/Support/raw_ostream.h"
45 #include "llvm/Support/Mutex.h"
46 #include "llvm/ADT/SetVector.h"
47 #include "llvm/ADT/SmallPtrSet.h"
48 #include "llvm/ADT/SmallSet.h"
49 #include "llvm/ADT/SmallVector.h"
50 #include "llvm/ADT/StringExtras.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 static const fltSemantics *EVTToAPFloatSemantics(EVT VT) {
63 switch (VT.getSimpleVT().SimpleTy) {
64 default: llvm_unreachable("Unknown FP format");
65 case MVT::f32: return &APFloat::IEEEsingle;
66 case MVT::f64: return &APFloat::IEEEdouble;
67 case MVT::f80: return &APFloat::x87DoubleExtended;
68 case MVT::f128: return &APFloat::IEEEquad;
69 case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
73 SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
75 //===----------------------------------------------------------------------===//
76 // ConstantFPSDNode Class
77 //===----------------------------------------------------------------------===//
79 /// isExactlyValue - We don't rely on operator== working on double values, as
80 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
81 /// As such, this method can be used to do an exact bit-for-bit comparison of
82 /// two floating point values.
83 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
84 return getValueAPF().bitwiseIsEqual(V);
87 bool ConstantFPSDNode::isValueValidForType(EVT VT,
89 assert(VT.isFloatingPoint() && "Can only convert between FP types");
91 // PPC long double cannot be converted to any other type.
92 if (VT == MVT::ppcf128 ||
93 &Val.getSemantics() == &APFloat::PPCDoubleDouble)
96 // convert modifies in place, so make a copy.
97 APFloat Val2 = APFloat(Val);
99 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven,
104 //===----------------------------------------------------------------------===//
106 //===----------------------------------------------------------------------===//
108 /// isBuildVectorAllOnes - Return true if the specified node is a
109 /// BUILD_VECTOR where all of the elements are ~0 or undef.
110 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
111 // Look through a bit convert.
112 if (N->getOpcode() == ISD::BITCAST)
113 N = N->getOperand(0).getNode();
115 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
117 unsigned i = 0, e = N->getNumOperands();
119 // Skip over all of the undef values.
120 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
123 // Do not accept an all-undef vector.
124 if (i == e) return false;
126 // Do not accept build_vectors that aren't all constants or which have non-~0
128 SDValue NotZero = N->getOperand(i);
129 if (isa<ConstantSDNode>(NotZero)) {
130 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
132 } else if (isa<ConstantFPSDNode>(NotZero)) {
133 if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF().
134 bitcastToAPInt().isAllOnesValue())
139 // Okay, we have at least one ~0 value, check to see if the rest match or are
141 for (++i; i != e; ++i)
142 if (N->getOperand(i) != NotZero &&
143 N->getOperand(i).getOpcode() != ISD::UNDEF)
149 /// isBuildVectorAllZeros - Return true if the specified node is a
150 /// BUILD_VECTOR where all of the elements are 0 or undef.
151 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
152 // Look through a bit convert.
153 if (N->getOpcode() == ISD::BITCAST)
154 N = N->getOperand(0).getNode();
156 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
158 unsigned i = 0, e = N->getNumOperands();
160 // Skip over all of the undef values.
161 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
164 // Do not accept an all-undef vector.
165 if (i == e) return false;
167 // Do not accept build_vectors that aren't all constants or which have non-0
169 SDValue Zero = N->getOperand(i);
170 if (isa<ConstantSDNode>(Zero)) {
171 if (!cast<ConstantSDNode>(Zero)->isNullValue())
173 } else if (isa<ConstantFPSDNode>(Zero)) {
174 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
179 // Okay, we have at least one 0 value, check to see if the rest match or are
181 for (++i; i != e; ++i)
182 if (N->getOperand(i) != Zero &&
183 N->getOperand(i).getOpcode() != ISD::UNDEF)
188 /// isScalarToVector - Return true if the specified node is a
189 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
190 /// element is not an undef.
191 bool ISD::isScalarToVector(const SDNode *N) {
192 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
195 if (N->getOpcode() != ISD::BUILD_VECTOR)
197 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
199 unsigned NumElems = N->getNumOperands();
202 for (unsigned i = 1; i < NumElems; ++i) {
203 SDValue V = N->getOperand(i);
204 if (V.getOpcode() != ISD::UNDEF)
210 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
211 /// when given the operation for (X op Y).
212 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
213 // To perform this operation, we just need to swap the L and G bits of the
215 unsigned OldL = (Operation >> 2) & 1;
216 unsigned OldG = (Operation >> 1) & 1;
217 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
218 (OldL << 1) | // New G bit
219 (OldG << 2)); // New L bit.
222 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
223 /// 'op' is a valid SetCC operation.
224 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
225 unsigned Operation = Op;
227 Operation ^= 7; // Flip L, G, E bits, but not U.
229 Operation ^= 15; // Flip all of the condition bits.
231 if (Operation > ISD::SETTRUE2)
232 Operation &= ~8; // Don't let N and U bits get set.
234 return ISD::CondCode(Operation);
238 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
239 /// signed operation and 2 if the result is an unsigned comparison. Return zero
240 /// if the operation does not depend on the sign of the input (setne and seteq).
241 static int isSignedOp(ISD::CondCode Opcode) {
243 default: llvm_unreachable("Illegal integer setcc operation!");
245 case ISD::SETNE: return 0;
249 case ISD::SETGE: return 1;
253 case ISD::SETUGE: return 2;
257 /// getSetCCOrOperation - Return the result of a logical OR between different
258 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
259 /// returns SETCC_INVALID if it is not possible to represent the resultant
261 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
263 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
264 // Cannot fold a signed integer setcc with an unsigned integer setcc.
265 return ISD::SETCC_INVALID;
267 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
269 // If the N and U bits get set then the resultant comparison DOES suddenly
270 // care about orderedness, and is true when ordered.
271 if (Op > ISD::SETTRUE2)
272 Op &= ~16; // Clear the U bit if the N bit is set.
274 // Canonicalize illegal integer setcc's.
275 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
278 return ISD::CondCode(Op);
281 /// getSetCCAndOperation - Return the result of a logical AND between different
282 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
283 /// function returns zero if it is not possible to represent the resultant
285 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
287 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
288 // Cannot fold a signed setcc with an unsigned setcc.
289 return ISD::SETCC_INVALID;
291 // Combine all of the condition bits.
292 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
294 // Canonicalize illegal integer setcc's.
298 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
299 case ISD::SETOEQ: // SETEQ & SETU[LG]E
300 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
301 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
302 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
309 //===----------------------------------------------------------------------===//
310 // SDNode Profile Support
311 //===----------------------------------------------------------------------===//
313 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
315 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
319 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
320 /// solely with their pointer.
321 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
322 ID.AddPointer(VTList.VTs);
325 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
327 static void AddNodeIDOperands(FoldingSetNodeID &ID,
328 const SDValue *Ops, unsigned NumOps) {
329 for (; NumOps; --NumOps, ++Ops) {
330 ID.AddPointer(Ops->getNode());
331 ID.AddInteger(Ops->getResNo());
335 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
337 static void AddNodeIDOperands(FoldingSetNodeID &ID,
338 const SDUse *Ops, unsigned NumOps) {
339 for (; NumOps; --NumOps, ++Ops) {
340 ID.AddPointer(Ops->getNode());
341 ID.AddInteger(Ops->getResNo());
345 static void AddNodeIDNode(FoldingSetNodeID &ID,
346 unsigned short OpC, SDVTList VTList,
347 const SDValue *OpList, unsigned N) {
348 AddNodeIDOpcode(ID, OpC);
349 AddNodeIDValueTypes(ID, VTList);
350 AddNodeIDOperands(ID, OpList, N);
353 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
355 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
356 switch (N->getOpcode()) {
357 case ISD::TargetExternalSymbol:
358 case ISD::ExternalSymbol:
359 llvm_unreachable("Should only be used on nodes with operands");
360 default: break; // Normal nodes don't need extra info.
361 case ISD::TargetConstant:
363 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue());
365 case ISD::TargetConstantFP:
366 case ISD::ConstantFP: {
367 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
370 case ISD::TargetGlobalAddress:
371 case ISD::GlobalAddress:
372 case ISD::TargetGlobalTLSAddress:
373 case ISD::GlobalTLSAddress: {
374 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
375 ID.AddPointer(GA->getGlobal());
376 ID.AddInteger(GA->getOffset());
377 ID.AddInteger(GA->getTargetFlags());
380 case ISD::BasicBlock:
381 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
384 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
388 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
390 case ISD::FrameIndex:
391 case ISD::TargetFrameIndex:
392 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
395 case ISD::TargetJumpTable:
396 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
397 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
399 case ISD::ConstantPool:
400 case ISD::TargetConstantPool: {
401 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
402 ID.AddInteger(CP->getAlignment());
403 ID.AddInteger(CP->getOffset());
404 if (CP->isMachineConstantPoolEntry())
405 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
407 ID.AddPointer(CP->getConstVal());
408 ID.AddInteger(CP->getTargetFlags());
412 const LoadSDNode *LD = cast<LoadSDNode>(N);
413 ID.AddInteger(LD->getMemoryVT().getRawBits());
414 ID.AddInteger(LD->getRawSubclassData());
418 const StoreSDNode *ST = cast<StoreSDNode>(N);
419 ID.AddInteger(ST->getMemoryVT().getRawBits());
420 ID.AddInteger(ST->getRawSubclassData());
423 case ISD::ATOMIC_CMP_SWAP:
424 case ISD::ATOMIC_SWAP:
425 case ISD::ATOMIC_LOAD_ADD:
426 case ISD::ATOMIC_LOAD_SUB:
427 case ISD::ATOMIC_LOAD_AND:
428 case ISD::ATOMIC_LOAD_OR:
429 case ISD::ATOMIC_LOAD_XOR:
430 case ISD::ATOMIC_LOAD_NAND:
431 case ISD::ATOMIC_LOAD_MIN:
432 case ISD::ATOMIC_LOAD_MAX:
433 case ISD::ATOMIC_LOAD_UMIN:
434 case ISD::ATOMIC_LOAD_UMAX:
435 case ISD::ATOMIC_LOAD:
436 case ISD::ATOMIC_STORE: {
437 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
438 ID.AddInteger(AT->getMemoryVT().getRawBits());
439 ID.AddInteger(AT->getRawSubclassData());
442 case ISD::VECTOR_SHUFFLE: {
443 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
444 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
446 ID.AddInteger(SVN->getMaskElt(i));
449 case ISD::TargetBlockAddress:
450 case ISD::BlockAddress: {
451 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress());
452 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags());
455 } // end switch (N->getOpcode())
458 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
460 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
461 AddNodeIDOpcode(ID, N->getOpcode());
462 // Add the return value info.
463 AddNodeIDValueTypes(ID, N->getVTList());
464 // Add the operand info.
465 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
467 // Handle SDNode leafs with special info.
468 AddNodeIDCustom(ID, N);
471 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
472 /// the CSE map that carries volatility, temporalness, indexing mode, and
473 /// extension/truncation information.
475 static inline unsigned
476 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
477 bool isNonTemporal, bool isInvariant) {
478 assert((ConvType & 3) == ConvType &&
479 "ConvType may not require more than 2 bits!");
480 assert((AM & 7) == AM &&
481 "AM may not require more than 3 bits!");
485 (isNonTemporal << 6) |
489 //===----------------------------------------------------------------------===//
490 // SelectionDAG Class
491 //===----------------------------------------------------------------------===//
493 /// doNotCSE - Return true if CSE should not be performed for this node.
494 static bool doNotCSE(SDNode *N) {
495 if (N->getValueType(0) == MVT::Glue)
496 return true; // Never CSE anything that produces a flag.
498 switch (N->getOpcode()) {
500 case ISD::HANDLENODE:
502 return true; // Never CSE these nodes.
505 // Check that remaining values produced are not flags.
506 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
507 if (N->getValueType(i) == MVT::Glue)
508 return true; // Never CSE anything that produces a flag.
513 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
515 void SelectionDAG::RemoveDeadNodes() {
516 // Create a dummy node (which is not added to allnodes), that adds a reference
517 // to the root node, preventing it from being deleted.
518 HandleSDNode Dummy(getRoot());
520 SmallVector<SDNode*, 128> DeadNodes;
522 // Add all obviously-dead nodes to the DeadNodes worklist.
523 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
525 DeadNodes.push_back(I);
527 RemoveDeadNodes(DeadNodes);
529 // If the root changed (e.g. it was a dead load, update the root).
530 setRoot(Dummy.getValue());
533 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
534 /// given list, and any nodes that become unreachable as a result.
535 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
536 DAGUpdateListener *UpdateListener) {
538 // Process the worklist, deleting the nodes and adding their uses to the
540 while (!DeadNodes.empty()) {
541 SDNode *N = DeadNodes.pop_back_val();
544 UpdateListener->NodeDeleted(N, 0);
546 // Take the node out of the appropriate CSE map.
547 RemoveNodeFromCSEMaps(N);
549 // Next, brutally remove the operand list. This is safe to do, as there are
550 // no cycles in the graph.
551 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
553 SDNode *Operand = Use.getNode();
556 // Now that we removed this operand, see if there are no uses of it left.
557 if (Operand->use_empty())
558 DeadNodes.push_back(Operand);
565 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
566 SmallVector<SDNode*, 16> DeadNodes(1, N);
568 // Create a dummy node that adds a reference to the root node, preventing
569 // it from being deleted. (This matters if the root is an operand of the
571 HandleSDNode Dummy(getRoot());
573 RemoveDeadNodes(DeadNodes, UpdateListener);
576 void SelectionDAG::DeleteNode(SDNode *N) {
577 // First take this out of the appropriate CSE map.
578 RemoveNodeFromCSEMaps(N);
580 // Finally, remove uses due to operands of this node, remove from the
581 // AllNodes list, and delete the node.
582 DeleteNodeNotInCSEMaps(N);
585 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
586 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
587 assert(N->use_empty() && "Cannot delete a node that is not dead!");
589 // Drop all of the operands and decrement used node's use counts.
595 void SelectionDAG::DeallocateNode(SDNode *N) {
596 if (N->OperandsNeedDelete)
597 delete[] N->OperandList;
599 // Set the opcode to DELETED_NODE to help catch bugs when node
600 // memory is reallocated.
601 N->NodeType = ISD::DELETED_NODE;
603 NodeAllocator.Deallocate(AllNodes.remove(N));
605 // Remove the ordering of this node.
608 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
609 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
610 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
611 DbgVals[i]->setIsInvalidated();
614 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
615 /// correspond to it. This is useful when we're about to delete or repurpose
616 /// the node. We don't want future request for structurally identical nodes
617 /// to return N anymore.
618 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
620 switch (N->getOpcode()) {
621 case ISD::HANDLENODE: return false; // noop.
623 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
624 "Cond code doesn't exist!");
625 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
626 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
628 case ISD::ExternalSymbol:
629 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
631 case ISD::TargetExternalSymbol: {
632 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
633 Erased = TargetExternalSymbols.erase(
634 std::pair<std::string,unsigned char>(ESN->getSymbol(),
635 ESN->getTargetFlags()));
638 case ISD::VALUETYPE: {
639 EVT VT = cast<VTSDNode>(N)->getVT();
640 if (VT.isExtended()) {
641 Erased = ExtendedValueTypeNodes.erase(VT);
643 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0;
644 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0;
649 // Remove it from the CSE Map.
650 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
651 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
652 Erased = CSEMap.RemoveNode(N);
656 // Verify that the node was actually in one of the CSE maps, unless it has a
657 // flag result (which cannot be CSE'd) or is one of the special cases that are
658 // not subject to CSE.
659 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
660 !N->isMachineOpcode() && !doNotCSE(N)) {
663 llvm_unreachable("Node is not in map!");
669 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
670 /// maps and modified in place. Add it back to the CSE maps, unless an identical
671 /// node already exists, in which case transfer all its users to the existing
672 /// node. This transfer can potentially trigger recursive merging.
675 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N,
676 DAGUpdateListener *UpdateListener) {
677 // For node types that aren't CSE'd, just act as if no identical node
680 SDNode *Existing = CSEMap.GetOrInsertNode(N);
682 // If there was already an existing matching node, use ReplaceAllUsesWith
683 // to replace the dead one with the existing one. This can cause
684 // recursive merging of other unrelated nodes down the line.
685 ReplaceAllUsesWith(N, Existing, UpdateListener);
687 // N is now dead. Inform the listener if it exists and delete it.
689 UpdateListener->NodeDeleted(N, Existing);
690 DeleteNodeNotInCSEMaps(N);
695 // If the node doesn't already exist, we updated it. Inform a listener if
698 UpdateListener->NodeUpdated(N);
701 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
702 /// were replaced with those specified. If this node is never memoized,
703 /// return null, otherwise return a pointer to the slot it would take. If a
704 /// node already exists with these operands, the slot will be non-null.
705 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
710 SDValue Ops[] = { Op };
712 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
713 AddNodeIDCustom(ID, N);
714 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
718 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
719 /// were replaced with those specified. If this node is never memoized,
720 /// return null, otherwise return a pointer to the slot it would take. If a
721 /// node already exists with these operands, the slot will be non-null.
722 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
723 SDValue Op1, SDValue Op2,
728 SDValue Ops[] = { Op1, Op2 };
730 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
731 AddNodeIDCustom(ID, N);
732 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
737 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
738 /// were replaced with those specified. If this node is never memoized,
739 /// return null, otherwise return a pointer to the slot it would take. If a
740 /// node already exists with these operands, the slot will be non-null.
741 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
742 const SDValue *Ops,unsigned NumOps,
748 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
749 AddNodeIDCustom(ID, N);
750 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
755 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
756 static void VerifyNodeCommon(SDNode *N) {
757 switch (N->getOpcode()) {
760 case ISD::BUILD_PAIR: {
761 EVT VT = N->getValueType(0);
762 assert(N->getNumValues() == 1 && "Too many results!");
763 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
764 "Wrong return type!");
765 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
766 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
767 "Mismatched operand types!");
768 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
769 "Wrong operand type!");
770 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
771 "Wrong return type size");
774 case ISD::BUILD_VECTOR: {
775 assert(N->getNumValues() == 1 && "Too many results!");
776 assert(N->getValueType(0).isVector() && "Wrong return type!");
777 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
778 "Wrong number of operands!");
779 EVT EltVT = N->getValueType(0).getVectorElementType();
780 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
781 assert((I->getValueType() == EltVT ||
782 (EltVT.isInteger() && I->getValueType().isInteger() &&
783 EltVT.bitsLE(I->getValueType()))) &&
784 "Wrong operand type!");
785 assert(I->getValueType() == N->getOperand(0).getValueType() &&
786 "Operands must all have the same type");
793 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
794 static void VerifySDNode(SDNode *N) {
795 // The SDNode allocators cannot be used to allocate nodes with fields that are
796 // not present in an SDNode!
797 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
798 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
799 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
800 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
801 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
802 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
803 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
804 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
805 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
806 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
807 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
808 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
809 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
810 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
811 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
812 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
813 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
814 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
815 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
820 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
822 static void VerifyMachineNode(SDNode *N) {
823 // The MachineNode allocators cannot be used to allocate nodes with fields
824 // that are not present in a MachineNode!
825 // Currently there are no such nodes.
831 /// getEVTAlignment - Compute the default alignment value for the
834 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
835 Type *Ty = VT == MVT::iPTR ?
836 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
837 VT.getTypeForEVT(*getContext());
839 return TLI.getTargetData()->getABITypeAlignment(Ty);
842 // EntryNode could meaningfully have debug info if we can find it...
843 SelectionDAG::SelectionDAG(const TargetMachine &tm)
844 : TM(tm), TLI(*tm.getTargetLowering()), TSI(*tm.getSelectionDAGInfo()),
845 EntryNode(ISD::EntryToken, DebugLoc(), getVTList(MVT::Other)),
846 Root(getEntryNode()), Ordering(0) {
847 AllNodes.push_back(&EntryNode);
848 Ordering = new SDNodeOrdering();
849 DbgInfo = new SDDbgInfo();
852 void SelectionDAG::init(MachineFunction &mf) {
854 Context = &mf.getFunction()->getContext();
857 SelectionDAG::~SelectionDAG() {
863 void SelectionDAG::allnodes_clear() {
864 assert(&*AllNodes.begin() == &EntryNode);
865 AllNodes.remove(AllNodes.begin());
866 while (!AllNodes.empty())
867 DeallocateNode(AllNodes.begin());
870 void SelectionDAG::clear() {
872 OperandAllocator.Reset();
875 ExtendedValueTypeNodes.clear();
876 ExternalSymbols.clear();
877 TargetExternalSymbols.clear();
878 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
879 static_cast<CondCodeSDNode*>(0));
880 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
881 static_cast<SDNode*>(0));
883 EntryNode.UseList = 0;
884 AllNodes.push_back(&EntryNode);
885 Root = getEntryNode();
890 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
891 return VT.bitsGT(Op.getValueType()) ?
892 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
893 getNode(ISD::TRUNCATE, DL, VT, Op);
896 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
897 return VT.bitsGT(Op.getValueType()) ?
898 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
899 getNode(ISD::TRUNCATE, DL, VT, Op);
902 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) {
903 return VT.bitsGT(Op.getValueType()) ?
904 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
905 getNode(ISD::TRUNCATE, DL, VT, Op);
908 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) {
909 assert(!VT.isVector() &&
910 "getZeroExtendInReg should use the vector element type instead of "
912 if (Op.getValueType() == VT) return Op;
913 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
914 APInt Imm = APInt::getLowBitsSet(BitWidth,
916 return getNode(ISD::AND, DL, Op.getValueType(), Op,
917 getConstant(Imm, Op.getValueType()));
920 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
922 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) {
923 EVT EltVT = VT.getScalarType();
925 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
926 return getNode(ISD::XOR, DL, VT, Val, NegOne);
929 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) {
930 EVT EltVT = VT.getScalarType();
931 assert((EltVT.getSizeInBits() >= 64 ||
932 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
933 "getConstant with a uint64_t value that doesn't fit in the type!");
934 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT);
937 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) {
938 return getConstant(*ConstantInt::get(*Context, Val), VT, isT);
941 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) {
942 assert(VT.isInteger() && "Cannot create FP integer constant!");
944 EVT EltVT = VT.getScalarType();
945 const ConstantInt *Elt = &Val;
947 // In some cases the vector type is legal but the element type is illegal and
948 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
949 // inserted value (the type does not need to match the vector element type).
950 // Any extra bits introduced will be truncated away.
951 if (VT.isVector() && TLI.getTypeAction(*getContext(), EltVT) ==
952 TargetLowering::TypePromoteInteger) {
953 EltVT = TLI.getTypeToTransformTo(*getContext(), EltVT);
954 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
955 Elt = ConstantInt::get(*getContext(), NewVal);
958 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
959 "APInt size does not match type size!");
960 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
962 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
966 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
968 return SDValue(N, 0);
971 N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
972 CSEMap.InsertNode(N, IP);
973 AllNodes.push_back(N);
976 SDValue Result(N, 0);
978 SmallVector<SDValue, 8> Ops;
979 Ops.assign(VT.getVectorNumElements(), Result);
980 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
985 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
986 return getConstant(Val, TLI.getPointerTy(), isTarget);
990 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
991 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
994 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
995 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
997 EVT EltVT = VT.getScalarType();
999 // Do the map lookup using the actual bit pattern for the floating point
1000 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1001 // we don't have issues with SNANs.
1002 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1003 FoldingSetNodeID ID;
1004 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0);
1008 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1010 return SDValue(N, 0);
1013 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1014 CSEMap.InsertNode(N, IP);
1015 AllNodes.push_back(N);
1018 SDValue Result(N, 0);
1019 if (VT.isVector()) {
1020 SmallVector<SDValue, 8> Ops;
1021 Ops.assign(VT.getVectorNumElements(), Result);
1022 // FIXME DebugLoc info might be appropriate here
1023 Result = getNode(ISD::BUILD_VECTOR, DebugLoc(), VT, &Ops[0], Ops.size());
1028 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1029 EVT EltVT = VT.getScalarType();
1030 if (EltVT==MVT::f32)
1031 return getConstantFP(APFloat((float)Val), VT, isTarget);
1032 else if (EltVT==MVT::f64)
1033 return getConstantFP(APFloat(Val), VT, isTarget);
1034 else if (EltVT==MVT::f80 || EltVT==MVT::f128) {
1036 APFloat apf = APFloat(Val);
1037 apf.convert(*EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1039 return getConstantFP(apf, VT, isTarget);
1041 assert(0 && "Unsupported type in getConstantFP");
1046 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, DebugLoc DL,
1047 EVT VT, int64_t Offset,
1049 unsigned char TargetFlags) {
1050 assert((TargetFlags == 0 || isTargetGA) &&
1051 "Cannot set target flags on target-independent globals");
1053 // Truncate (with sign-extension) the offset value to the pointer size.
1054 EVT PTy = TLI.getPointerTy();
1055 unsigned BitWidth = PTy.getSizeInBits();
1057 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth));
1059 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1061 // If GV is an alias then use the aliasee for determining thread-localness.
1062 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1063 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false));
1067 if (GVar && GVar->isThreadLocal())
1068 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1070 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1072 FoldingSetNodeID ID;
1073 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1075 ID.AddInteger(Offset);
1076 ID.AddInteger(TargetFlags);
1078 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1079 return SDValue(E, 0);
1081 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL, GV, VT,
1082 Offset, TargetFlags);
1083 CSEMap.InsertNode(N, IP);
1084 AllNodes.push_back(N);
1085 return SDValue(N, 0);
1088 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1089 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1090 FoldingSetNodeID ID;
1091 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1094 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1095 return SDValue(E, 0);
1097 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1098 CSEMap.InsertNode(N, IP);
1099 AllNodes.push_back(N);
1100 return SDValue(N, 0);
1103 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1104 unsigned char TargetFlags) {
1105 assert((TargetFlags == 0 || isTarget) &&
1106 "Cannot set target flags on target-independent jump tables");
1107 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1108 FoldingSetNodeID ID;
1109 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1111 ID.AddInteger(TargetFlags);
1113 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1114 return SDValue(E, 0);
1116 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1118 CSEMap.InsertNode(N, IP);
1119 AllNodes.push_back(N);
1120 return SDValue(N, 0);
1123 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1124 unsigned Alignment, int Offset,
1126 unsigned char TargetFlags) {
1127 assert((TargetFlags == 0 || isTarget) &&
1128 "Cannot set target flags on target-independent globals");
1130 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1131 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1132 FoldingSetNodeID ID;
1133 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1134 ID.AddInteger(Alignment);
1135 ID.AddInteger(Offset);
1137 ID.AddInteger(TargetFlags);
1139 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1140 return SDValue(E, 0);
1142 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1143 Alignment, TargetFlags);
1144 CSEMap.InsertNode(N, IP);
1145 AllNodes.push_back(N);
1146 return SDValue(N, 0);
1150 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1151 unsigned Alignment, int Offset,
1153 unsigned char TargetFlags) {
1154 assert((TargetFlags == 0 || isTarget) &&
1155 "Cannot set target flags on target-independent globals");
1157 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType());
1158 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1159 FoldingSetNodeID ID;
1160 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1161 ID.AddInteger(Alignment);
1162 ID.AddInteger(Offset);
1163 C->addSelectionDAGCSEId(ID);
1164 ID.AddInteger(TargetFlags);
1166 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1167 return SDValue(E, 0);
1169 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1170 Alignment, TargetFlags);
1171 CSEMap.InsertNode(N, IP);
1172 AllNodes.push_back(N);
1173 return SDValue(N, 0);
1176 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1177 FoldingSetNodeID ID;
1178 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0);
1181 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1182 return SDValue(E, 0);
1184 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1185 CSEMap.InsertNode(N, IP);
1186 AllNodes.push_back(N);
1187 return SDValue(N, 0);
1190 SDValue SelectionDAG::getValueType(EVT VT) {
1191 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1192 ValueTypeNodes.size())
1193 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1195 SDNode *&N = VT.isExtended() ?
1196 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1198 if (N) return SDValue(N, 0);
1199 N = new (NodeAllocator) VTSDNode(VT);
1200 AllNodes.push_back(N);
1201 return SDValue(N, 0);
1204 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1205 SDNode *&N = ExternalSymbols[Sym];
1206 if (N) return SDValue(N, 0);
1207 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1208 AllNodes.push_back(N);
1209 return SDValue(N, 0);
1212 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1213 unsigned char TargetFlags) {
1215 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1217 if (N) return SDValue(N, 0);
1218 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1219 AllNodes.push_back(N);
1220 return SDValue(N, 0);
1223 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1224 if ((unsigned)Cond >= CondCodeNodes.size())
1225 CondCodeNodes.resize(Cond+1);
1227 if (CondCodeNodes[Cond] == 0) {
1228 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1229 CondCodeNodes[Cond] = N;
1230 AllNodes.push_back(N);
1233 return SDValue(CondCodeNodes[Cond], 0);
1236 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1237 // the shuffle mask M that point at N1 to point at N2, and indices that point
1238 // N2 to point at N1.
1239 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1241 int NElts = M.size();
1242 for (int i = 0; i != NElts; ++i) {
1250 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1,
1251 SDValue N2, const int *Mask) {
1252 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE");
1253 assert(VT.isVector() && N1.getValueType().isVector() &&
1254 "Vector Shuffle VTs must be a vectors");
1255 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType()
1256 && "Vector Shuffle VTs must have same element type");
1258 // Canonicalize shuffle undef, undef -> undef
1259 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1260 return getUNDEF(VT);
1262 // Validate that all indices in Mask are within the range of the elements
1263 // input to the shuffle.
1264 unsigned NElts = VT.getVectorNumElements();
1265 SmallVector<int, 8> MaskVec;
1266 for (unsigned i = 0; i != NElts; ++i) {
1267 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1268 MaskVec.push_back(Mask[i]);
1271 // Canonicalize shuffle v, v -> v, undef
1274 for (unsigned i = 0; i != NElts; ++i)
1275 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1278 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1279 if (N1.getOpcode() == ISD::UNDEF)
1280 commuteShuffle(N1, N2, MaskVec);
1282 // Canonicalize all index into lhs, -> shuffle lhs, undef
1283 // Canonicalize all index into rhs, -> shuffle rhs, undef
1284 bool AllLHS = true, AllRHS = true;
1285 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1286 for (unsigned i = 0; i != NElts; ++i) {
1287 if (MaskVec[i] >= (int)NElts) {
1292 } else if (MaskVec[i] >= 0) {
1296 if (AllLHS && AllRHS)
1297 return getUNDEF(VT);
1298 if (AllLHS && !N2Undef)
1302 commuteShuffle(N1, N2, MaskVec);
1305 // If Identity shuffle, or all shuffle in to undef, return that node.
1306 bool AllUndef = true;
1307 bool Identity = true;
1308 for (unsigned i = 0; i != NElts; ++i) {
1309 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1310 if (MaskVec[i] >= 0) AllUndef = false;
1312 if (Identity && NElts == N1.getValueType().getVectorNumElements())
1315 return getUNDEF(VT);
1317 FoldingSetNodeID ID;
1318 SDValue Ops[2] = { N1, N2 };
1319 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2);
1320 for (unsigned i = 0; i != NElts; ++i)
1321 ID.AddInteger(MaskVec[i]);
1324 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1325 return SDValue(E, 0);
1327 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1328 // SDNode doesn't have access to it. This memory will be "leaked" when
1329 // the node is deallocated, but recovered when the NodeAllocator is released.
1330 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1331 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1333 ShuffleVectorSDNode *N =
1334 new (NodeAllocator) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc);
1335 CSEMap.InsertNode(N, IP);
1336 AllNodes.push_back(N);
1337 return SDValue(N, 0);
1340 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl,
1341 SDValue Val, SDValue DTy,
1342 SDValue STy, SDValue Rnd, SDValue Sat,
1343 ISD::CvtCode Code) {
1344 // If the src and dest types are the same and the conversion is between
1345 // integer types of the same sign or two floats, no conversion is necessary.
1347 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1350 FoldingSetNodeID ID;
1351 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1352 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5);
1354 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1355 return SDValue(E, 0);
1357 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl, Ops, 5,
1359 CSEMap.InsertNode(N, IP);
1360 AllNodes.push_back(N);
1361 return SDValue(N, 0);
1364 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1365 FoldingSetNodeID ID;
1366 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0);
1367 ID.AddInteger(RegNo);
1369 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1370 return SDValue(E, 0);
1372 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1373 CSEMap.InsertNode(N, IP);
1374 AllNodes.push_back(N);
1375 return SDValue(N, 0);
1378 SDValue SelectionDAG::getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label) {
1379 FoldingSetNodeID ID;
1380 SDValue Ops[] = { Root };
1381 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), &Ops[0], 1);
1382 ID.AddPointer(Label);
1384 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1385 return SDValue(E, 0);
1387 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl, Root, Label);
1388 CSEMap.InsertNode(N, IP);
1389 AllNodes.push_back(N);
1390 return SDValue(N, 0);
1394 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1396 unsigned char TargetFlags) {
1397 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1399 FoldingSetNodeID ID;
1400 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0);
1402 ID.AddInteger(TargetFlags);
1404 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1405 return SDValue(E, 0);
1407 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, TargetFlags);
1408 CSEMap.InsertNode(N, IP);
1409 AllNodes.push_back(N);
1410 return SDValue(N, 0);
1413 SDValue SelectionDAG::getSrcValue(const Value *V) {
1414 assert((!V || V->getType()->isPointerTy()) &&
1415 "SrcValue is not a pointer?");
1417 FoldingSetNodeID ID;
1418 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0);
1422 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1423 return SDValue(E, 0);
1425 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1426 CSEMap.InsertNode(N, IP);
1427 AllNodes.push_back(N);
1428 return SDValue(N, 0);
1431 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1432 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1433 FoldingSetNodeID ID;
1434 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), 0, 0);
1438 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1439 return SDValue(E, 0);
1441 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1442 CSEMap.InsertNode(N, IP);
1443 AllNodes.push_back(N);
1444 return SDValue(N, 0);
1448 /// getShiftAmountOperand - Return the specified value casted to
1449 /// the target's desired shift amount type.
1450 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1451 EVT OpTy = Op.getValueType();
1452 MVT ShTy = TLI.getShiftAmountTy(LHSTy);
1453 if (OpTy == ShTy || OpTy.isVector()) return Op;
1455 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1456 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op);
1459 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1460 /// specified value type.
1461 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1462 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1463 unsigned ByteSize = VT.getStoreSize();
1464 Type *Ty = VT.getTypeForEVT(*getContext());
1465 unsigned StackAlign =
1466 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign);
1468 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1469 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1472 /// CreateStackTemporary - Create a stack temporary suitable for holding
1473 /// either of the specified value types.
1474 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1475 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1476 VT2.getStoreSizeInBits())/8;
1477 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1478 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1479 const TargetData *TD = TLI.getTargetData();
1480 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1481 TD->getPrefTypeAlignment(Ty2));
1483 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1484 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1485 return getFrameIndex(FrameIdx, TLI.getPointerTy());
1488 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1489 SDValue N2, ISD::CondCode Cond, DebugLoc dl) {
1490 // These setcc operations always fold.
1494 case ISD::SETFALSE2: return getConstant(0, VT);
1496 case ISD::SETTRUE2: return getConstant(1, VT);
1508 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1512 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1513 const APInt &C2 = N2C->getAPIntValue();
1514 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1515 const APInt &C1 = N1C->getAPIntValue();
1518 default: llvm_unreachable("Unknown integer setcc!");
1519 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1520 case ISD::SETNE: return getConstant(C1 != C2, VT);
1521 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1522 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1523 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1524 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1525 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1526 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1527 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1528 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1532 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1533 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1534 // No compile time operations on this type yet.
1535 if (N1C->getValueType(0) == MVT::ppcf128)
1538 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1541 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1542 return getUNDEF(VT);
1544 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1545 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1546 return getUNDEF(VT);
1548 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1549 R==APFloat::cmpLessThan, VT);
1550 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1551 return getUNDEF(VT);
1553 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1554 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1555 return getUNDEF(VT);
1557 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1558 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1559 return getUNDEF(VT);
1561 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1562 R==APFloat::cmpEqual, VT);
1563 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1564 return getUNDEF(VT);
1566 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1567 R==APFloat::cmpEqual, VT);
1568 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1569 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1570 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1571 R==APFloat::cmpEqual, VT);
1572 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1573 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1574 R==APFloat::cmpLessThan, VT);
1575 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1576 R==APFloat::cmpUnordered, VT);
1577 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1578 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1581 // Ensure that the constant occurs on the RHS.
1582 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1586 // Could not fold it.
1590 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1591 /// use this predicate to simplify operations downstream.
1592 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1593 // This predicate is not safe for vector operations.
1594 if (Op.getValueType().isVector())
1597 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1598 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1601 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1602 /// this predicate to simplify operations downstream. Mask is known to be zero
1603 /// for bits that V cannot have.
1604 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1605 unsigned Depth) const {
1606 APInt KnownZero, KnownOne;
1607 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1608 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1609 return (KnownZero & Mask) == Mask;
1612 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1613 /// known to be either zero or one and return them in the KnownZero/KnownOne
1614 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1616 void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask,
1617 APInt &KnownZero, APInt &KnownOne,
1618 unsigned Depth) const {
1619 unsigned BitWidth = Mask.getBitWidth();
1620 assert(BitWidth == Op.getValueType().getScalarType().getSizeInBits() &&
1621 "Mask size mismatches value type size!");
1623 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1624 if (Depth == 6 || Mask == 0)
1625 return; // Limit search depth.
1627 APInt KnownZero2, KnownOne2;
1629 switch (Op.getOpcode()) {
1631 // We know all of the bits for a constant!
1632 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask;
1633 KnownZero = ~KnownOne & Mask;
1636 // If either the LHS or the RHS are Zero, the result is zero.
1637 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1638 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero,
1639 KnownZero2, KnownOne2, Depth+1);
1640 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1641 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1643 // Output known-1 bits are only known if set in both the LHS & RHS.
1644 KnownOne &= KnownOne2;
1645 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1646 KnownZero |= KnownZero2;
1649 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1650 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne,
1651 KnownZero2, KnownOne2, Depth+1);
1652 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1653 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1655 // Output known-0 bits are only known if clear in both the LHS & RHS.
1656 KnownZero &= KnownZero2;
1657 // Output known-1 are known to be set if set in either the LHS | RHS.
1658 KnownOne |= KnownOne2;
1661 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1662 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1663 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1664 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1666 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1667 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1668 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1669 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1670 KnownZero = KnownZeroOut;
1674 APInt Mask2 = APInt::getAllOnesValue(BitWidth);
1675 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1);
1676 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1677 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1678 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1680 // If low bits are zero in either operand, output low known-0 bits.
1681 // Also compute a conserative estimate for high known-0 bits.
1682 // More trickiness is possible, but this is sufficient for the
1683 // interesting case of alignment computation.
1684 KnownOne.clearAllBits();
1685 unsigned TrailZ = KnownZero.countTrailingOnes() +
1686 KnownZero2.countTrailingOnes();
1687 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1688 KnownZero2.countLeadingOnes(),
1689 BitWidth) - BitWidth;
1691 TrailZ = std::min(TrailZ, BitWidth);
1692 LeadZ = std::min(LeadZ, BitWidth);
1693 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1694 APInt::getHighBitsSet(BitWidth, LeadZ);
1699 // For the purposes of computing leading zeros we can conservatively
1700 // treat a udiv as a logical right shift by the power of 2 known to
1701 // be less than the denominator.
1702 APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1703 ComputeMaskedBits(Op.getOperand(0),
1704 AllOnes, KnownZero2, KnownOne2, Depth+1);
1705 unsigned LeadZ = KnownZero2.countLeadingOnes();
1707 KnownOne2.clearAllBits();
1708 KnownZero2.clearAllBits();
1709 ComputeMaskedBits(Op.getOperand(1),
1710 AllOnes, KnownZero2, KnownOne2, Depth+1);
1711 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1712 if (RHSUnknownLeadingOnes != BitWidth)
1713 LeadZ = std::min(BitWidth,
1714 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1716 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
1720 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1721 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1722 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1723 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1725 // Only known if known in both the LHS and RHS.
1726 KnownOne &= KnownOne2;
1727 KnownZero &= KnownZero2;
1729 case ISD::SELECT_CC:
1730 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1731 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1732 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1733 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1735 // Only known if known in both the LHS and RHS.
1736 KnownOne &= KnownOne2;
1737 KnownZero &= KnownZero2;
1745 if (Op.getResNo() != 1)
1747 // The boolean result conforms to getBooleanContents. Fall through.
1749 // If we know the result of a setcc has the top bits zero, use this info.
1750 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
1751 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1752 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1755 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1756 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1757 unsigned ShAmt = SA->getZExtValue();
1759 // If the shift count is an invalid immediate, don't do anything.
1760 if (ShAmt >= BitWidth)
1763 ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1764 KnownZero, KnownOne, Depth+1);
1765 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1766 KnownZero <<= ShAmt;
1768 // low bits known zero.
1769 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1773 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1774 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1775 unsigned ShAmt = SA->getZExtValue();
1777 // If the shift count is an invalid immediate, don't do anything.
1778 if (ShAmt >= BitWidth)
1781 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1782 KnownZero, KnownOne, Depth+1);
1783 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1784 KnownZero = KnownZero.lshr(ShAmt);
1785 KnownOne = KnownOne.lshr(ShAmt);
1787 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1788 KnownZero |= HighBits; // High bits known zero.
1792 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1793 unsigned ShAmt = SA->getZExtValue();
1795 // If the shift count is an invalid immediate, don't do anything.
1796 if (ShAmt >= BitWidth)
1799 APInt InDemandedMask = (Mask << ShAmt);
1800 // If any of the demanded bits are produced by the sign extension, we also
1801 // demand the input sign bit.
1802 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1803 if (HighBits.getBoolValue())
1804 InDemandedMask |= APInt::getSignBit(BitWidth);
1806 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1808 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1809 KnownZero = KnownZero.lshr(ShAmt);
1810 KnownOne = KnownOne.lshr(ShAmt);
1812 // Handle the sign bits.
1813 APInt SignBit = APInt::getSignBit(BitWidth);
1814 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1816 if (KnownZero.intersects(SignBit)) {
1817 KnownZero |= HighBits; // New bits are known zero.
1818 } else if (KnownOne.intersects(SignBit)) {
1819 KnownOne |= HighBits; // New bits are known one.
1823 case ISD::SIGN_EXTEND_INREG: {
1824 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1825 unsigned EBits = EVT.getScalarType().getSizeInBits();
1827 // Sign extension. Compute the demanded bits in the result that are not
1828 // present in the input.
1829 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1831 APInt InSignBit = APInt::getSignBit(EBits);
1832 APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1834 // If the sign extended bits are demanded, we know that the sign
1836 InSignBit = InSignBit.zext(BitWidth);
1837 if (NewBits.getBoolValue())
1838 InputDemandedBits |= InSignBit;
1840 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1841 KnownZero, KnownOne, Depth+1);
1842 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1844 // If the sign bit of the input is known set or clear, then we know the
1845 // top bits of the result.
1846 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
1847 KnownZero |= NewBits;
1848 KnownOne &= ~NewBits;
1849 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
1850 KnownOne |= NewBits;
1851 KnownZero &= ~NewBits;
1852 } else { // Input sign bit unknown
1853 KnownZero &= ~NewBits;
1854 KnownOne &= ~NewBits;
1861 unsigned LowBits = Log2_32(BitWidth)+1;
1862 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1863 KnownOne.clearAllBits();
1867 if (ISD::isZEXTLoad(Op.getNode())) {
1868 LoadSDNode *LD = cast<LoadSDNode>(Op);
1869 EVT VT = LD->getMemoryVT();
1870 unsigned MemBits = VT.getScalarType().getSizeInBits();
1871 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1875 case ISD::ZERO_EXTEND: {
1876 EVT InVT = Op.getOperand(0).getValueType();
1877 unsigned InBits = InVT.getScalarType().getSizeInBits();
1878 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1879 APInt InMask = Mask.trunc(InBits);
1880 KnownZero = KnownZero.trunc(InBits);
1881 KnownOne = KnownOne.trunc(InBits);
1882 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1883 KnownZero = KnownZero.zext(BitWidth);
1884 KnownOne = KnownOne.zext(BitWidth);
1885 KnownZero |= NewBits;
1888 case ISD::SIGN_EXTEND: {
1889 EVT InVT = Op.getOperand(0).getValueType();
1890 unsigned InBits = InVT.getScalarType().getSizeInBits();
1891 APInt InSignBit = APInt::getSignBit(InBits);
1892 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1893 APInt InMask = Mask.trunc(InBits);
1895 // If any of the sign extended bits are demanded, we know that the sign
1896 // bit is demanded. Temporarily set this bit in the mask for our callee.
1897 if (NewBits.getBoolValue())
1898 InMask |= InSignBit;
1900 KnownZero = KnownZero.trunc(InBits);
1901 KnownOne = KnownOne.trunc(InBits);
1902 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1904 // Note if the sign bit is known to be zero or one.
1905 bool SignBitKnownZero = KnownZero.isNegative();
1906 bool SignBitKnownOne = KnownOne.isNegative();
1907 assert(!(SignBitKnownZero && SignBitKnownOne) &&
1908 "Sign bit can't be known to be both zero and one!");
1910 // If the sign bit wasn't actually demanded by our caller, we don't
1911 // want it set in the KnownZero and KnownOne result values. Reset the
1912 // mask and reapply it to the result values.
1913 InMask = Mask.trunc(InBits);
1914 KnownZero &= InMask;
1917 KnownZero = KnownZero.zext(BitWidth);
1918 KnownOne = KnownOne.zext(BitWidth);
1920 // If the sign bit is known zero or one, the top bits match.
1921 if (SignBitKnownZero)
1922 KnownZero |= NewBits;
1923 else if (SignBitKnownOne)
1924 KnownOne |= NewBits;
1927 case ISD::ANY_EXTEND: {
1928 EVT InVT = Op.getOperand(0).getValueType();
1929 unsigned InBits = InVT.getScalarType().getSizeInBits();
1930 APInt InMask = Mask.trunc(InBits);
1931 KnownZero = KnownZero.trunc(InBits);
1932 KnownOne = KnownOne.trunc(InBits);
1933 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1934 KnownZero = KnownZero.zext(BitWidth);
1935 KnownOne = KnownOne.zext(BitWidth);
1938 case ISD::TRUNCATE: {
1939 EVT InVT = Op.getOperand(0).getValueType();
1940 unsigned InBits = InVT.getScalarType().getSizeInBits();
1941 APInt InMask = Mask.zext(InBits);
1942 KnownZero = KnownZero.zext(InBits);
1943 KnownOne = KnownOne.zext(InBits);
1944 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1945 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1946 KnownZero = KnownZero.trunc(BitWidth);
1947 KnownOne = KnownOne.trunc(BitWidth);
1950 case ISD::AssertZext: {
1951 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1952 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
1953 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1955 KnownZero |= (~InMask) & Mask;
1959 // All bits are zero except the low bit.
1960 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1964 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1965 // We know that the top bits of C-X are clear if X contains less bits
1966 // than C (i.e. no wrap-around can happen). For example, 20-X is
1967 // positive if we can prove that X is >= 0 and < 16.
1968 if (CLHS->getAPIntValue().isNonNegative()) {
1969 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1970 // NLZ can't be BitWidth with no sign bit
1971 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1972 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2,
1975 // If all of the MaskV bits are known to be zero, then we know the
1976 // output top bits are zero, because we now know that the output is
1978 if ((KnownZero2 & MaskV) == MaskV) {
1979 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1980 // Top bits known zero.
1981 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
1989 // Output known-0 bits are known if clear or set in both the low clear bits
1990 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
1991 // low 3 bits clear.
1992 APInt Mask2 = APInt::getLowBitsSet(BitWidth,
1993 BitWidth - Mask.countLeadingZeros());
1994 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1995 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1996 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
1998 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
1999 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2000 KnownZeroOut = std::min(KnownZeroOut,
2001 KnownZero2.countTrailingOnes());
2003 if (Op.getOpcode() == ISD::ADD) {
2004 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2008 // With ADDE, a carry bit may be added in, so we can only use this
2009 // information if we know (at least) that the low two bits are clear. We
2010 // then return to the caller that the low bit is unknown but that other bits
2012 if (KnownZeroOut >= 2) // ADDE
2013 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2017 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2018 const APInt &RA = Rem->getAPIntValue().abs();
2019 if (RA.isPowerOf2()) {
2020 APInt LowBits = RA - 1;
2021 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
2022 ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1);
2024 // The low bits of the first operand are unchanged by the srem.
2025 KnownZero = KnownZero2 & LowBits;
2026 KnownOne = KnownOne2 & LowBits;
2028 // If the first operand is non-negative or has all low bits zero, then
2029 // the upper bits are all zero.
2030 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2031 KnownZero |= ~LowBits;
2033 // If the first operand is negative and not all low bits are zero, then
2034 // the upper bits are all one.
2035 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2036 KnownOne |= ~LowBits;
2041 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2046 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2047 const APInt &RA = Rem->getAPIntValue();
2048 if (RA.isPowerOf2()) {
2049 APInt LowBits = (RA - 1);
2050 APInt Mask2 = LowBits & Mask;
2051 KnownZero |= ~LowBits & Mask;
2052 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
2053 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2058 // Since the result is less than or equal to either operand, any leading
2059 // zero bits in either operand must also exist in the result.
2060 APInt AllOnes = APInt::getAllOnesValue(BitWidth);
2061 ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne,
2063 ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2,
2066 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2067 KnownZero2.countLeadingOnes());
2068 KnownOne.clearAllBits();
2069 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
2072 case ISD::FrameIndex:
2073 case ISD::TargetFrameIndex:
2074 if (unsigned Align = InferPtrAlignment(Op)) {
2075 // The low bits are known zero if the pointer is aligned.
2076 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2082 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2085 case ISD::INTRINSIC_WO_CHAIN:
2086 case ISD::INTRINSIC_W_CHAIN:
2087 case ISD::INTRINSIC_VOID:
2088 // Allow the target to implement this method for its nodes.
2089 TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this,
2095 /// ComputeNumSignBits - Return the number of times the sign bit of the
2096 /// register is replicated into the other bits. We know that at least 1 bit
2097 /// is always equal to the sign bit (itself), but other cases can give us
2098 /// information. For example, immediately after an "SRA X, 2", we know that
2099 /// the top 3 bits are all equal to each other, so we return 3.
2100 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2101 EVT VT = Op.getValueType();
2102 assert(VT.isInteger() && "Invalid VT!");
2103 unsigned VTBits = VT.getScalarType().getSizeInBits();
2105 unsigned FirstAnswer = 1;
2108 return 1; // Limit search depth.
2110 switch (Op.getOpcode()) {
2112 case ISD::AssertSext:
2113 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2114 return VTBits-Tmp+1;
2115 case ISD::AssertZext:
2116 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2119 case ISD::Constant: {
2120 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2121 return Val.getNumSignBits();
2124 case ISD::SIGN_EXTEND:
2125 Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2126 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2128 case ISD::SIGN_EXTEND_INREG:
2129 // Max of the input and what this extends.
2131 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2134 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2135 return std::max(Tmp, Tmp2);
2138 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2139 // SRA X, C -> adds C sign bits.
2140 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2141 Tmp += C->getZExtValue();
2142 if (Tmp > VTBits) Tmp = VTBits;
2146 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2147 // shl destroys sign bits.
2148 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2149 if (C->getZExtValue() >= VTBits || // Bad shift.
2150 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2151 return Tmp - C->getZExtValue();
2156 case ISD::XOR: // NOT is handled here.
2157 // Logical binary ops preserve the number of sign bits at the worst.
2158 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2160 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2161 FirstAnswer = std::min(Tmp, Tmp2);
2162 // We computed what we know about the sign bits as our first
2163 // answer. Now proceed to the generic code that uses
2164 // ComputeMaskedBits, and pick whichever answer is better.
2169 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2170 if (Tmp == 1) return 1; // Early out.
2171 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2172 return std::min(Tmp, Tmp2);
2180 if (Op.getResNo() != 1)
2182 // The boolean result conforms to getBooleanContents. Fall through.
2184 // If setcc returns 0/-1, all bits are sign bits.
2185 if (TLI.getBooleanContents(Op.getValueType().isVector()) ==
2186 TargetLowering::ZeroOrNegativeOneBooleanContent)
2191 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2194 // Handle rotate right by N like a rotate left by 32-N.
2195 if (Op.getOpcode() == ISD::ROTR)
2196 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2198 // If we aren't rotating out all of the known-in sign bits, return the
2199 // number that are left. This handles rotl(sext(x), 1) for example.
2200 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2201 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2205 // Add can have at most one carry bit. Thus we know that the output
2206 // is, at worst, one more bit than the inputs.
2207 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2208 if (Tmp == 1) return 1; // Early out.
2210 // Special case decrementing a value (ADD X, -1):
2211 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2212 if (CRHS->isAllOnesValue()) {
2213 APInt KnownZero, KnownOne;
2214 APInt Mask = APInt::getAllOnesValue(VTBits);
2215 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
2217 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2219 if ((KnownZero | APInt(VTBits, 1)) == Mask)
2222 // If we are subtracting one from a positive number, there is no carry
2223 // out of the result.
2224 if (KnownZero.isNegative())
2228 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2229 if (Tmp2 == 1) return 1;
2230 return std::min(Tmp, Tmp2)-1;
2234 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2235 if (Tmp2 == 1) return 1;
2238 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2239 if (CLHS->isNullValue()) {
2240 APInt KnownZero, KnownOne;
2241 APInt Mask = APInt::getAllOnesValue(VTBits);
2242 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
2243 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2245 if ((KnownZero | APInt(VTBits, 1)) == Mask)
2248 // If the input is known to be positive (the sign bit is known clear),
2249 // the output of the NEG has the same number of sign bits as the input.
2250 if (KnownZero.isNegative())
2253 // Otherwise, we treat this like a SUB.
2256 // Sub can have at most one carry bit. Thus we know that the output
2257 // is, at worst, one more bit than the inputs.
2258 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2259 if (Tmp == 1) return 1; // Early out.
2260 return std::min(Tmp, Tmp2)-1;
2263 // FIXME: it's tricky to do anything useful for this, but it is an important
2264 // case for targets like X86.
2268 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2269 if (Op.getOpcode() == ISD::LOAD) {
2270 LoadSDNode *LD = cast<LoadSDNode>(Op);
2271 unsigned ExtType = LD->getExtensionType();
2274 case ISD::SEXTLOAD: // '17' bits known
2275 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2276 return VTBits-Tmp+1;
2277 case ISD::ZEXTLOAD: // '16' bits known
2278 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2283 // Allow the target to implement this method for its nodes.
2284 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2285 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2286 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2287 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2288 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
2289 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2292 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2293 // use this information.
2294 APInt KnownZero, KnownOne;
2295 APInt Mask = APInt::getAllOnesValue(VTBits);
2296 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
2298 if (KnownZero.isNegative()) { // sign bit is 0
2300 } else if (KnownOne.isNegative()) { // sign bit is 1;
2307 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2308 // the number of identical bits in the top of the input value.
2310 Mask <<= Mask.getBitWidth()-VTBits;
2311 // Return # leading zeros. We use 'min' here in case Val was zero before
2312 // shifting. We don't want to return '64' as for an i32 "0".
2313 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2316 /// isBaseWithConstantOffset - Return true if the specified operand is an
2317 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2318 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2319 /// semantics as an ADD. This handles the equivalence:
2320 /// X|Cst == X+Cst iff X&Cst = 0.
2321 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2322 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2323 !isa<ConstantSDNode>(Op.getOperand(1)))
2326 if (Op.getOpcode() == ISD::OR &&
2327 !MaskedValueIsZero(Op.getOperand(0),
2328 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2335 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2336 // If we're told that NaNs won't happen, assume they won't.
2337 if (getTarget().Options.NoNaNsFPMath)
2340 // If the value is a constant, we can obviously see if it is a NaN or not.
2341 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2342 return !C->getValueAPF().isNaN();
2344 // TODO: Recognize more cases here.
2349 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2350 // If the value is a constant, we can obviously see if it is a zero or not.
2351 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2352 return !C->isZero();
2354 // TODO: Recognize more cases here.
2355 switch (Op.getOpcode()) {
2358 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2359 return !C->isNullValue();
2366 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2367 // Check the obvious case.
2368 if (A == B) return true;
2370 // For for negative and positive zero.
2371 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2372 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2373 if (CA->isZero() && CB->isZero()) return true;
2375 // Otherwise they may not be equal.
2379 /// getNode - Gets or creates the specified node.
2381 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) {
2382 FoldingSetNodeID ID;
2383 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0);
2385 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2386 return SDValue(E, 0);
2388 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL, getVTList(VT));
2389 CSEMap.InsertNode(N, IP);
2391 AllNodes.push_back(N);
2395 return SDValue(N, 0);
2398 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
2399 EVT VT, SDValue Operand) {
2400 // Constant fold unary operations with an integer constant operand.
2401 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2402 const APInt &Val = C->getAPIntValue();
2405 case ISD::SIGN_EXTEND:
2406 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT);
2407 case ISD::ANY_EXTEND:
2408 case ISD::ZERO_EXTEND:
2410 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT);
2411 case ISD::UINT_TO_FP:
2412 case ISD::SINT_TO_FP: {
2413 // No compile time operations on ppcf128.
2414 if (VT == MVT::ppcf128) break;
2415 APFloat apf(APInt::getNullValue(VT.getSizeInBits()));
2416 (void)apf.convertFromAPInt(Val,
2417 Opcode==ISD::SINT_TO_FP,
2418 APFloat::rmNearestTiesToEven);
2419 return getConstantFP(apf, VT);
2422 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2423 return getConstantFP(Val.bitsToFloat(), VT);
2424 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2425 return getConstantFP(Val.bitsToDouble(), VT);
2428 return getConstant(Val.byteSwap(), VT);
2430 return getConstant(Val.countPopulation(), VT);
2432 return getConstant(Val.countLeadingZeros(), VT);
2434 return getConstant(Val.countTrailingZeros(), VT);
2438 // Constant fold unary operations with a floating point constant operand.
2439 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2440 APFloat V = C->getValueAPF(); // make copy
2441 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
2445 return getConstantFP(V, VT);
2448 return getConstantFP(V, VT);
2450 case ISD::FP_EXTEND: {
2452 // This can return overflow, underflow, or inexact; we don't care.
2453 // FIXME need to be more flexible about rounding mode.
2454 (void)V.convert(*EVTToAPFloatSemantics(VT),
2455 APFloat::rmNearestTiesToEven, &ignored);
2456 return getConstantFP(V, VT);
2458 case ISD::FP_TO_SINT:
2459 case ISD::FP_TO_UINT: {
2462 assert(integerPartWidth >= 64);
2463 // FIXME need to be more flexible about rounding mode.
2464 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2465 Opcode==ISD::FP_TO_SINT,
2466 APFloat::rmTowardZero, &ignored);
2467 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2469 APInt api(VT.getSizeInBits(), x);
2470 return getConstant(api, VT);
2473 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2474 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2475 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2476 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2482 unsigned OpOpcode = Operand.getNode()->getOpcode();
2484 case ISD::TokenFactor:
2485 case ISD::MERGE_VALUES:
2486 case ISD::CONCAT_VECTORS:
2487 return Operand; // Factor, merge or concat of one node? No need.
2488 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2489 case ISD::FP_EXTEND:
2490 assert(VT.isFloatingPoint() &&
2491 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2492 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2493 assert((!VT.isVector() ||
2494 VT.getVectorNumElements() ==
2495 Operand.getValueType().getVectorNumElements()) &&
2496 "Vector element count mismatch!");
2497 if (Operand.getOpcode() == ISD::UNDEF)
2498 return getUNDEF(VT);
2500 case ISD::SIGN_EXTEND:
2501 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2502 "Invalid SIGN_EXTEND!");
2503 if (Operand.getValueType() == VT) return Operand; // noop extension
2504 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2505 "Invalid sext node, dst < src!");
2506 assert((!VT.isVector() ||
2507 VT.getVectorNumElements() ==
2508 Operand.getValueType().getVectorNumElements()) &&
2509 "Vector element count mismatch!");
2510 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2511 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2512 else if (OpOpcode == ISD::UNDEF)
2513 // sext(undef) = 0, because the top bits will all be the same.
2514 return getConstant(0, VT);
2516 case ISD::ZERO_EXTEND:
2517 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2518 "Invalid ZERO_EXTEND!");
2519 if (Operand.getValueType() == VT) return Operand; // noop extension
2520 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2521 "Invalid zext node, dst < src!");
2522 assert((!VT.isVector() ||
2523 VT.getVectorNumElements() ==
2524 Operand.getValueType().getVectorNumElements()) &&
2525 "Vector element count mismatch!");
2526 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2527 return getNode(ISD::ZERO_EXTEND, DL, VT,
2528 Operand.getNode()->getOperand(0));
2529 else if (OpOpcode == ISD::UNDEF)
2530 // zext(undef) = 0, because the top bits will be zero.
2531 return getConstant(0, VT);
2533 case ISD::ANY_EXTEND:
2534 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2535 "Invalid ANY_EXTEND!");
2536 if (Operand.getValueType() == VT) return Operand; // noop extension
2537 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2538 "Invalid anyext node, dst < src!");
2539 assert((!VT.isVector() ||
2540 VT.getVectorNumElements() ==
2541 Operand.getValueType().getVectorNumElements()) &&
2542 "Vector element count mismatch!");
2544 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2545 OpOpcode == ISD::ANY_EXTEND)
2546 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2547 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2548 else if (OpOpcode == ISD::UNDEF)
2549 return getUNDEF(VT);
2551 // (ext (trunx x)) -> x
2552 if (OpOpcode == ISD::TRUNCATE) {
2553 SDValue OpOp = Operand.getNode()->getOperand(0);
2554 if (OpOp.getValueType() == VT)
2559 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2560 "Invalid TRUNCATE!");
2561 if (Operand.getValueType() == VT) return Operand; // noop truncate
2562 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2563 "Invalid truncate node, src < dst!");
2564 assert((!VT.isVector() ||
2565 VT.getVectorNumElements() ==
2566 Operand.getValueType().getVectorNumElements()) &&
2567 "Vector element count mismatch!");
2568 if (OpOpcode == ISD::TRUNCATE)
2569 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2570 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2571 OpOpcode == ISD::ANY_EXTEND) {
2572 // If the source is smaller than the dest, we still need an extend.
2573 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2574 .bitsLT(VT.getScalarType()))
2575 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2576 else if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2577 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2579 return Operand.getNode()->getOperand(0);
2583 // Basic sanity checking.
2584 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2585 && "Cannot BITCAST between types of different sizes!");
2586 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2587 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2588 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2589 if (OpOpcode == ISD::UNDEF)
2590 return getUNDEF(VT);
2592 case ISD::SCALAR_TO_VECTOR:
2593 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2594 (VT.getVectorElementType() == Operand.getValueType() ||
2595 (VT.getVectorElementType().isInteger() &&
2596 Operand.getValueType().isInteger() &&
2597 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2598 "Illegal SCALAR_TO_VECTOR node!");
2599 if (OpOpcode == ISD::UNDEF)
2600 return getUNDEF(VT);
2601 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2602 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2603 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2604 Operand.getConstantOperandVal(1) == 0 &&
2605 Operand.getOperand(0).getValueType() == VT)
2606 return Operand.getOperand(0);
2609 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2610 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2611 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2612 Operand.getNode()->getOperand(0));
2613 if (OpOpcode == ISD::FNEG) // --X -> X
2614 return Operand.getNode()->getOperand(0);
2617 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2618 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2623 SDVTList VTs = getVTList(VT);
2624 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2625 FoldingSetNodeID ID;
2626 SDValue Ops[1] = { Operand };
2627 AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2629 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2630 return SDValue(E, 0);
2632 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2633 CSEMap.InsertNode(N, IP);
2635 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTs, Operand);
2638 AllNodes.push_back(N);
2642 return SDValue(N, 0);
2645 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode,
2647 ConstantSDNode *Cst1,
2648 ConstantSDNode *Cst2) {
2649 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue();
2652 case ISD::ADD: return getConstant(C1 + C2, VT);
2653 case ISD::SUB: return getConstant(C1 - C2, VT);
2654 case ISD::MUL: return getConstant(C1 * C2, VT);
2656 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2659 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2662 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2665 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2667 case ISD::AND: return getConstant(C1 & C2, VT);
2668 case ISD::OR: return getConstant(C1 | C2, VT);
2669 case ISD::XOR: return getConstant(C1 ^ C2, VT);
2670 case ISD::SHL: return getConstant(C1 << C2, VT);
2671 case ISD::SRL: return getConstant(C1.lshr(C2), VT);
2672 case ISD::SRA: return getConstant(C1.ashr(C2), VT);
2673 case ISD::ROTL: return getConstant(C1.rotl(C2), VT);
2674 case ISD::ROTR: return getConstant(C1.rotr(C2), VT);
2681 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
2682 SDValue N1, SDValue N2) {
2683 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2684 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2687 case ISD::TokenFactor:
2688 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2689 N2.getValueType() == MVT::Other && "Invalid token factor!");
2690 // Fold trivial token factors.
2691 if (N1.getOpcode() == ISD::EntryToken) return N2;
2692 if (N2.getOpcode() == ISD::EntryToken) return N1;
2693 if (N1 == N2) return N1;
2695 case ISD::CONCAT_VECTORS:
2696 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2697 // one big BUILD_VECTOR.
2698 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2699 N2.getOpcode() == ISD::BUILD_VECTOR) {
2700 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2701 N1.getNode()->op_end());
2702 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2703 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
2707 assert(VT.isInteger() && "This operator does not apply to FP types!");
2708 assert(N1.getValueType() == N2.getValueType() &&
2709 N1.getValueType() == VT && "Binary operator types must match!");
2710 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2711 // worth handling here.
2712 if (N2C && N2C->isNullValue())
2714 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2721 assert(VT.isInteger() && "This operator does not apply to FP types!");
2722 assert(N1.getValueType() == N2.getValueType() &&
2723 N1.getValueType() == VT && "Binary operator types must match!");
2724 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2725 // it's worth handling here.
2726 if (N2C && N2C->isNullValue())
2736 assert(VT.isInteger() && "This operator does not apply to FP types!");
2737 assert(N1.getValueType() == N2.getValueType() &&
2738 N1.getValueType() == VT && "Binary operator types must match!");
2745 if (getTarget().Options.UnsafeFPMath) {
2746 if (Opcode == ISD::FADD) {
2748 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
2749 if (CFP->getValueAPF().isZero())
2752 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2753 if (CFP->getValueAPF().isZero())
2755 } else if (Opcode == ISD::FSUB) {
2757 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
2758 if (CFP->getValueAPF().isZero())
2762 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
2763 assert(N1.getValueType() == N2.getValueType() &&
2764 N1.getValueType() == VT && "Binary operator types must match!");
2766 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
2767 assert(N1.getValueType() == VT &&
2768 N1.getValueType().isFloatingPoint() &&
2769 N2.getValueType().isFloatingPoint() &&
2770 "Invalid FCOPYSIGN!");
2777 assert(VT == N1.getValueType() &&
2778 "Shift operators return type must be the same as their first arg");
2779 assert(VT.isInteger() && N2.getValueType().isInteger() &&
2780 "Shifts only work on integers");
2781 // Verify that the shift amount VT is bit enough to hold valid shift
2782 // amounts. This catches things like trying to shift an i1024 value by an
2783 // i8, which is easy to fall into in generic code that uses
2784 // TLI.getShiftAmount().
2785 assert(N2.getValueType().getSizeInBits() >=
2786 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
2787 "Invalid use of small shift amount with oversized value!");
2789 // Always fold shifts of i1 values so the code generator doesn't need to
2790 // handle them. Since we know the size of the shift has to be less than the
2791 // size of the value, the shift/rotate count is guaranteed to be zero.
2794 if (N2C && N2C->isNullValue())
2797 case ISD::FP_ROUND_INREG: {
2798 EVT EVT = cast<VTSDNode>(N2)->getVT();
2799 assert(VT == N1.getValueType() && "Not an inreg round!");
2800 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
2801 "Cannot FP_ROUND_INREG integer types");
2802 assert(EVT.isVector() == VT.isVector() &&
2803 "FP_ROUND_INREG type should be vector iff the operand "
2805 assert((!EVT.isVector() ||
2806 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2807 "Vector element counts must match in FP_ROUND_INREG");
2808 assert(EVT.bitsLE(VT) && "Not rounding down!");
2810 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
2814 assert(VT.isFloatingPoint() &&
2815 N1.getValueType().isFloatingPoint() &&
2816 VT.bitsLE(N1.getValueType()) &&
2817 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2818 if (N1.getValueType() == VT) return N1; // noop conversion.
2820 case ISD::AssertSext:
2821 case ISD::AssertZext: {
2822 EVT EVT = cast<VTSDNode>(N2)->getVT();
2823 assert(VT == N1.getValueType() && "Not an inreg extend!");
2824 assert(VT.isInteger() && EVT.isInteger() &&
2825 "Cannot *_EXTEND_INREG FP types");
2826 assert(!EVT.isVector() &&
2827 "AssertSExt/AssertZExt type should be the vector element type "
2828 "rather than the vector type!");
2829 assert(EVT.bitsLE(VT) && "Not extending!");
2830 if (VT == EVT) return N1; // noop assertion.
2833 case ISD::SIGN_EXTEND_INREG: {
2834 EVT EVT = cast<VTSDNode>(N2)->getVT();
2835 assert(VT == N1.getValueType() && "Not an inreg extend!");
2836 assert(VT.isInteger() && EVT.isInteger() &&
2837 "Cannot *_EXTEND_INREG FP types");
2838 assert(EVT.isVector() == VT.isVector() &&
2839 "SIGN_EXTEND_INREG type should be vector iff the operand "
2841 assert((!EVT.isVector() ||
2842 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
2843 "Vector element counts must match in SIGN_EXTEND_INREG");
2844 assert(EVT.bitsLE(VT) && "Not extending!");
2845 if (EVT == VT) return N1; // Not actually extending
2848 APInt Val = N1C->getAPIntValue();
2849 unsigned FromBits = EVT.getScalarType().getSizeInBits();
2850 Val <<= Val.getBitWidth()-FromBits;
2851 Val = Val.ashr(Val.getBitWidth()-FromBits);
2852 return getConstant(Val, VT);
2856 case ISD::EXTRACT_VECTOR_ELT:
2857 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2858 if (N1.getOpcode() == ISD::UNDEF)
2859 return getUNDEF(VT);
2861 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2862 // expanding copies of large vectors from registers.
2864 N1.getOpcode() == ISD::CONCAT_VECTORS &&
2865 N1.getNumOperands() > 0) {
2867 N1.getOperand(0).getValueType().getVectorNumElements();
2868 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
2869 N1.getOperand(N2C->getZExtValue() / Factor),
2870 getConstant(N2C->getZExtValue() % Factor,
2871 N2.getValueType()));
2874 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2875 // expanding large vector constants.
2876 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
2877 SDValue Elt = N1.getOperand(N2C->getZExtValue());
2878 EVT VEltTy = N1.getValueType().getVectorElementType();
2879 if (Elt.getValueType() != VEltTy) {
2880 // If the vector element type is not legal, the BUILD_VECTOR operands
2881 // are promoted and implicitly truncated. Make that explicit here.
2882 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt);
2885 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT
2886 // result is implicitly extended.
2887 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt);
2892 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2893 // operations are lowered to scalars.
2894 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
2895 // If the indices are the same, return the inserted element else
2896 // if the indices are known different, extract the element from
2897 // the original vector.
2898 SDValue N1Op2 = N1.getOperand(2);
2899 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
2901 if (N1Op2C && N2C) {
2902 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
2903 if (VT == N1.getOperand(1).getValueType())
2904 return N1.getOperand(1);
2906 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
2909 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
2913 case ISD::EXTRACT_ELEMENT:
2914 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2915 assert(!N1.getValueType().isVector() && !VT.isVector() &&
2916 (N1.getValueType().isInteger() == VT.isInteger()) &&
2917 N1.getValueType() != VT &&
2918 "Wrong types for EXTRACT_ELEMENT!");
2920 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2921 // 64-bit integers into 32-bit parts. Instead of building the extract of
2922 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2923 if (N1.getOpcode() == ISD::BUILD_PAIR)
2924 return N1.getOperand(N2C->getZExtValue());
2926 // EXTRACT_ELEMENT of a constant int is also very common.
2927 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2928 unsigned ElementSize = VT.getSizeInBits();
2929 unsigned Shift = ElementSize * N2C->getZExtValue();
2930 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2931 return getConstant(ShiftedVal.trunc(ElementSize), VT);
2934 case ISD::EXTRACT_SUBVECTOR: {
2936 if (VT.isSimple() && N1.getValueType().isSimple()) {
2937 assert(VT.isVector() && N1.getValueType().isVector() &&
2938 "Extract subvector VTs must be a vectors!");
2939 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() &&
2940 "Extract subvector VTs must have the same element type!");
2941 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() &&
2942 "Extract subvector must be from larger vector to smaller vector!");
2944 if (isa<ConstantSDNode>(Index.getNode())) {
2945 assert((VT.getVectorNumElements() +
2946 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
2947 <= N1.getValueType().getVectorNumElements())
2948 && "Extract subvector overflow!");
2951 // Trivial extraction.
2952 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT())
2961 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C);
2962 if (SV.getNode()) return SV;
2963 } else { // Cannonicalize constant to RHS if commutative
2964 if (isCommutativeBinOp(Opcode)) {
2965 std::swap(N1C, N2C);
2971 // Constant fold FP operations.
2972 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
2973 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
2975 if (!N2CFP && isCommutativeBinOp(Opcode)) {
2976 // Cannonicalize constant to RHS if commutative
2977 std::swap(N1CFP, N2CFP);
2979 } else if (N2CFP && VT != MVT::ppcf128) {
2980 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2981 APFloat::opStatus s;
2984 s = V1.add(V2, APFloat::rmNearestTiesToEven);
2985 if (s != APFloat::opInvalidOp)
2986 return getConstantFP(V1, VT);
2989 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2990 if (s!=APFloat::opInvalidOp)
2991 return getConstantFP(V1, VT);
2994 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2995 if (s!=APFloat::opInvalidOp)
2996 return getConstantFP(V1, VT);
2999 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3000 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3001 return getConstantFP(V1, VT);
3004 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3005 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3006 return getConstantFP(V1, VT);
3008 case ISD::FCOPYSIGN:
3010 return getConstantFP(V1, VT);
3016 // Canonicalize an UNDEF to the RHS, even over a constant.
3017 if (N1.getOpcode() == ISD::UNDEF) {
3018 if (isCommutativeBinOp(Opcode)) {
3022 case ISD::FP_ROUND_INREG:
3023 case ISD::SIGN_EXTEND_INREG:
3029 return N1; // fold op(undef, arg2) -> undef
3037 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3038 // For vectors, we can't easily build an all zero vector, just return
3045 // Fold a bunch of operators when the RHS is undef.
3046 if (N2.getOpcode() == ISD::UNDEF) {
3049 if (N1.getOpcode() == ISD::UNDEF)
3050 // Handle undef ^ undef -> 0 special case. This is a common
3052 return getConstant(0, VT);
3062 return N2; // fold op(arg1, undef) -> undef
3068 if (getTarget().Options.UnsafeFPMath)
3076 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3077 // For vectors, we can't easily build an all zero vector, just return
3082 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3083 // For vectors, we can't easily build an all one vector, just return
3091 // Memoize this node if possible.
3093 SDVTList VTs = getVTList(VT);
3094 if (VT != MVT::Glue) {
3095 SDValue Ops[] = { N1, N2 };
3096 FoldingSetNodeID ID;
3097 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
3099 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3100 return SDValue(E, 0);
3102 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3103 CSEMap.InsertNode(N, IP);
3105 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2);
3108 AllNodes.push_back(N);
3112 return SDValue(N, 0);
3115 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3116 SDValue N1, SDValue N2, SDValue N3) {
3117 // Perform various simplifications.
3118 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3120 case ISD::CONCAT_VECTORS:
3121 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3122 // one big BUILD_VECTOR.
3123 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3124 N2.getOpcode() == ISD::BUILD_VECTOR &&
3125 N3.getOpcode() == ISD::BUILD_VECTOR) {
3126 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3127 N1.getNode()->op_end());
3128 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3129 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3130 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size());
3134 // Use FoldSetCC to simplify SETCC's.
3135 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3136 if (Simp.getNode()) return Simp;
3141 if (N1C->getZExtValue())
3142 return N2; // select true, X, Y -> X
3144 return N3; // select false, X, Y -> Y
3147 if (N2 == N3) return N2; // select C, X, X -> X
3149 case ISD::VECTOR_SHUFFLE:
3150 llvm_unreachable("should use getVectorShuffle constructor!");
3152 case ISD::INSERT_SUBVECTOR: {
3154 if (VT.isSimple() && N1.getValueType().isSimple()
3155 && N2.getValueType().isSimple()) {
3156 assert(VT.isVector() && N1.getValueType().isVector() &&
3157 N2.getValueType().isVector() &&
3158 "Insert subvector VTs must be a vectors");
3159 assert(VT == N1.getValueType() &&
3160 "Dest and insert subvector source types must match!");
3161 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() &&
3162 "Insert subvector must be from smaller vector to larger vector!");
3163 if (isa<ConstantSDNode>(Index.getNode())) {
3164 assert((N2.getValueType().getVectorNumElements() +
3165 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3166 <= VT.getVectorNumElements())
3167 && "Insert subvector overflow!");
3170 // Trivial insertion.
3171 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT())
3177 // Fold bit_convert nodes from a type to themselves.
3178 if (N1.getValueType() == VT)
3183 // Memoize node if it doesn't produce a flag.
3185 SDVTList VTs = getVTList(VT);
3186 if (VT != MVT::Glue) {
3187 SDValue Ops[] = { N1, N2, N3 };
3188 FoldingSetNodeID ID;
3189 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3191 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3192 return SDValue(E, 0);
3194 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3195 CSEMap.InsertNode(N, IP);
3197 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3);
3200 AllNodes.push_back(N);
3204 return SDValue(N, 0);
3207 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3208 SDValue N1, SDValue N2, SDValue N3,
3210 SDValue Ops[] = { N1, N2, N3, N4 };
3211 return getNode(Opcode, DL, VT, Ops, 4);
3214 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
3215 SDValue N1, SDValue N2, SDValue N3,
3216 SDValue N4, SDValue N5) {
3217 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3218 return getNode(Opcode, DL, VT, Ops, 5);
3221 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3222 /// the incoming stack arguments to be loaded from the stack.
3223 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3224 SmallVector<SDValue, 8> ArgChains;
3226 // Include the original chain at the beginning of the list. When this is
3227 // used by target LowerCall hooks, this helps legalize find the
3228 // CALLSEQ_BEGIN node.
3229 ArgChains.push_back(Chain);
3231 // Add a chain value for each stack argument.
3232 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3233 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3234 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3235 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3236 if (FI->getIndex() < 0)
3237 ArgChains.push_back(SDValue(L, 1));
3239 // Build a tokenfactor for all the chains.
3240 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other,
3241 &ArgChains[0], ArgChains.size());
3244 /// SplatByte - Distribute ByteVal over NumBits bits.
3245 static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) {
3246 APInt Val = APInt(NumBits, ByteVal);
3248 for (unsigned i = NumBits; i > 8; i >>= 1) {
3249 Val = (Val << Shift) | Val;
3255 /// getMemsetValue - Vectorized representation of the memset value
3257 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3259 assert(Value.getOpcode() != ISD::UNDEF);
3261 unsigned NumBits = VT.getScalarType().getSizeInBits();
3262 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3263 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255);
3265 return DAG.getConstant(Val, VT);
3266 return DAG.getConstantFP(APFloat(Val), VT);
3269 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3271 // Use a multiplication with 0x010101... to extend the input to the
3273 APInt Magic = SplatByte(NumBits, 0x01);
3274 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3280 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3281 /// used when a memcpy is turned into a memset when the source is a constant
3283 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG,
3284 const TargetLowering &TLI,
3285 std::string &Str, unsigned Offset) {
3286 // Handle vector with all elements zero.
3289 return DAG.getConstant(0, VT);
3290 else if (VT == MVT::f32 || VT == MVT::f64)
3291 return DAG.getConstantFP(0.0, VT);
3292 else if (VT.isVector()) {
3293 unsigned NumElts = VT.getVectorNumElements();
3294 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3295 return DAG.getNode(ISD::BITCAST, dl, VT,
3296 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3299 llvm_unreachable("Expected type!");
3302 assert(!VT.isVector() && "Can't handle vector type here!");
3303 unsigned NumBits = VT.getSizeInBits();
3304 unsigned MSB = NumBits / 8;
3306 if (TLI.isLittleEndian())
3307 Offset = Offset + MSB - 1;
3308 for (unsigned i = 0; i != MSB; ++i) {
3309 Val = (Val << 8) | (unsigned char)Str[Offset];
3310 Offset += TLI.isLittleEndian() ? -1 : 1;
3312 return DAG.getConstant(Val, VT);
3315 /// getMemBasePlusOffset - Returns base and offset node for the
3317 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset,
3318 SelectionDAG &DAG) {
3319 EVT VT = Base.getValueType();
3320 return DAG.getNode(ISD::ADD, Base.getDebugLoc(),
3321 VT, Base, DAG.getConstant(Offset, VT));
3324 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3326 static bool isMemSrcFromString(SDValue Src, std::string &Str) {
3327 unsigned SrcDelta = 0;
3328 GlobalAddressSDNode *G = NULL;
3329 if (Src.getOpcode() == ISD::GlobalAddress)
3330 G = cast<GlobalAddressSDNode>(Src);
3331 else if (Src.getOpcode() == ISD::ADD &&
3332 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3333 Src.getOperand(1).getOpcode() == ISD::Constant) {
3334 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3335 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3340 const GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
3341 if (GV && GetConstantStringInfo(GV, Str, SrcDelta, false))
3347 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3348 /// to replace the memset / memcpy. Return true if the number of memory ops
3349 /// is below the threshold. It returns the types of the sequence of
3350 /// memory ops to perform memset / memcpy by reference.
3351 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3352 unsigned Limit, uint64_t Size,
3353 unsigned DstAlign, unsigned SrcAlign,
3357 const TargetLowering &TLI) {
3358 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3359 "Expecting memcpy / memset source to meet alignment requirement!");
3360 // If 'SrcAlign' is zero, that means the memory operation does not need to
3361 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3362 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3363 // is the specified alignment of the memory operation. If it is zero, that
3364 // means it's possible to change the alignment of the destination.
3365 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3366 // not need to be loaded.
3367 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3368 IsZeroVal, MemcpyStrSrc,
3369 DAG.getMachineFunction());
3371 if (VT == MVT::Other) {
3372 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() ||
3373 TLI.allowsUnalignedMemoryAccesses(VT)) {
3374 VT = TLI.getPointerTy();
3376 switch (DstAlign & 7) {
3377 case 0: VT = MVT::i64; break;
3378 case 4: VT = MVT::i32; break;
3379 case 2: VT = MVT::i16; break;
3380 default: VT = MVT::i8; break;
3385 while (!TLI.isTypeLegal(LVT))
3386 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3387 assert(LVT.isInteger());
3393 unsigned NumMemOps = 0;
3395 unsigned VTSize = VT.getSizeInBits() / 8;
3396 while (VTSize > Size) {
3397 // For now, only use non-vector load / store's for the left-over pieces.
3398 if (VT.isVector() || VT.isFloatingPoint()) {
3400 while (!TLI.isTypeLegal(VT))
3401 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3402 VTSize = VT.getSizeInBits() / 8;
3404 // This can result in a type that is not legal on the target, e.g.
3405 // 1 or 2 bytes on PPC.
3406 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
3411 if (++NumMemOps > Limit)
3413 MemOps.push_back(VT);
3420 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3421 SDValue Chain, SDValue Dst,
3422 SDValue Src, uint64_t Size,
3423 unsigned Align, bool isVol,
3425 MachinePointerInfo DstPtrInfo,
3426 MachinePointerInfo SrcPtrInfo) {
3427 // Turn a memcpy of undef to nop.
3428 if (Src.getOpcode() == ISD::UNDEF)
3431 // Expand memcpy to a series of load and store ops if the size operand falls
3432 // below a certain threshold.
3433 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3434 // rather than maybe a humongous number of loads and stores.
3435 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3436 std::vector<EVT> MemOps;
3437 bool DstAlignCanChange = false;
3438 MachineFunction &MF = DAG.getMachineFunction();
3439 MachineFrameInfo *MFI = MF.getFrameInfo();
3440 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3441 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3442 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3443 DstAlignCanChange = true;
3444 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3445 if (Align > SrcAlign)
3448 bool CopyFromStr = isMemSrcFromString(Src, Str);
3449 bool isZeroStr = CopyFromStr && Str.empty();
3450 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3452 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3453 (DstAlignCanChange ? 0 : Align),
3454 (isZeroStr ? 0 : SrcAlign),
3455 true, CopyFromStr, DAG, TLI))
3458 if (DstAlignCanChange) {
3459 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3460 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3461 if (NewAlign > Align) {
3462 // Give the stack frame object a larger alignment if needed.
3463 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3464 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3469 SmallVector<SDValue, 8> OutChains;
3470 unsigned NumMemOps = MemOps.size();
3471 uint64_t SrcOff = 0, DstOff = 0;
3472 for (unsigned i = 0; i != NumMemOps; ++i) {
3474 unsigned VTSize = VT.getSizeInBits() / 8;
3475 SDValue Value, Store;
3478 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3479 // It's unlikely a store of a vector immediate can be done in a single
3480 // instruction. It would require a load from a constantpool first.
3481 // We only handle zero vectors here.
3482 // FIXME: Handle other cases where store of vector immediate is done in
3483 // a single instruction.
3484 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str, SrcOff);
3485 Store = DAG.getStore(Chain, dl, Value,
3486 getMemBasePlusOffset(Dst, DstOff, DAG),
3487 DstPtrInfo.getWithOffset(DstOff), isVol,
3490 // The type might not be legal for the target. This should only happen
3491 // if the type is smaller than a legal type, as on PPC, so the right
3492 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3493 // to Load/Store if NVT==VT.
3494 // FIXME does the case above also need this?
3495 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3496 assert(NVT.bitsGE(VT));
3497 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3498 getMemBasePlusOffset(Src, SrcOff, DAG),
3499 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3500 MinAlign(SrcAlign, SrcOff));
3501 Store = DAG.getTruncStore(Chain, dl, Value,
3502 getMemBasePlusOffset(Dst, DstOff, DAG),
3503 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3506 OutChains.push_back(Store);
3511 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3512 &OutChains[0], OutChains.size());
3515 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl,
3516 SDValue Chain, SDValue Dst,
3517 SDValue Src, uint64_t Size,
3518 unsigned Align, bool isVol,
3520 MachinePointerInfo DstPtrInfo,
3521 MachinePointerInfo SrcPtrInfo) {
3522 // Turn a memmove of undef to nop.
3523 if (Src.getOpcode() == ISD::UNDEF)
3526 // Expand memmove to a series of load and store ops if the size operand falls
3527 // below a certain threshold.
3528 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3529 std::vector<EVT> MemOps;
3530 bool DstAlignCanChange = false;
3531 MachineFunction &MF = DAG.getMachineFunction();
3532 MachineFrameInfo *MFI = MF.getFrameInfo();
3533 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3534 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3535 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3536 DstAlignCanChange = true;
3537 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3538 if (Align > SrcAlign)
3540 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3542 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3543 (DstAlignCanChange ? 0 : Align),
3544 SrcAlign, true, false, DAG, TLI))
3547 if (DstAlignCanChange) {
3548 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3549 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3550 if (NewAlign > Align) {
3551 // Give the stack frame object a larger alignment if needed.
3552 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3553 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3558 uint64_t SrcOff = 0, DstOff = 0;
3559 SmallVector<SDValue, 8> LoadValues;
3560 SmallVector<SDValue, 8> LoadChains;
3561 SmallVector<SDValue, 8> OutChains;
3562 unsigned NumMemOps = MemOps.size();
3563 for (unsigned i = 0; i < NumMemOps; i++) {
3565 unsigned VTSize = VT.getSizeInBits() / 8;
3566 SDValue Value, Store;
3568 Value = DAG.getLoad(VT, dl, Chain,
3569 getMemBasePlusOffset(Src, SrcOff, DAG),
3570 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3571 false, false, SrcAlign);
3572 LoadValues.push_back(Value);
3573 LoadChains.push_back(Value.getValue(1));
3576 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3577 &LoadChains[0], LoadChains.size());
3579 for (unsigned i = 0; i < NumMemOps; i++) {
3581 unsigned VTSize = VT.getSizeInBits() / 8;
3582 SDValue Value, Store;
3584 Store = DAG.getStore(Chain, dl, LoadValues[i],
3585 getMemBasePlusOffset(Dst, DstOff, DAG),
3586 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3587 OutChains.push_back(Store);
3591 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3592 &OutChains[0], OutChains.size());
3595 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl,
3596 SDValue Chain, SDValue Dst,
3597 SDValue Src, uint64_t Size,
3598 unsigned Align, bool isVol,
3599 MachinePointerInfo DstPtrInfo) {
3600 // Turn a memset of undef to nop.
3601 if (Src.getOpcode() == ISD::UNDEF)
3604 // Expand memset to a series of load/store ops if the size operand
3605 // falls below a certain threshold.
3606 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3607 std::vector<EVT> MemOps;
3608 bool DstAlignCanChange = false;
3609 MachineFunction &MF = DAG.getMachineFunction();
3610 MachineFrameInfo *MFI = MF.getFrameInfo();
3611 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize);
3612 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3613 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3614 DstAlignCanChange = true;
3616 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3617 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3618 Size, (DstAlignCanChange ? 0 : Align), 0,
3619 IsZeroVal, false, DAG, TLI))
3622 if (DstAlignCanChange) {
3623 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3624 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty);
3625 if (NewAlign > Align) {
3626 // Give the stack frame object a larger alignment if needed.
3627 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3628 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3633 SmallVector<SDValue, 8> OutChains;
3634 uint64_t DstOff = 0;
3635 unsigned NumMemOps = MemOps.size();
3637 // Find the largest store and generate the bit pattern for it.
3638 EVT LargestVT = MemOps[0];
3639 for (unsigned i = 1; i < NumMemOps; i++)
3640 if (MemOps[i].bitsGT(LargestVT))
3641 LargestVT = MemOps[i];
3642 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
3644 for (unsigned i = 0; i < NumMemOps; i++) {
3647 // If this store is smaller than the largest store see whether we can get
3648 // the smaller value for free with a truncate.
3649 SDValue Value = MemSetValue;
3650 if (VT.bitsLT(LargestVT)) {
3651 if (!LargestVT.isVector() && !VT.isVector() &&
3652 TLI.isTruncateFree(LargestVT, VT))
3653 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
3655 Value = getMemsetValue(Src, VT, DAG, dl);
3657 assert(Value.getValueType() == VT && "Value with wrong type.");
3658 SDValue Store = DAG.getStore(Chain, dl, Value,
3659 getMemBasePlusOffset(Dst, DstOff, DAG),
3660 DstPtrInfo.getWithOffset(DstOff),
3661 isVol, false, Align);
3662 OutChains.push_back(Store);
3663 DstOff += VT.getSizeInBits() / 8;
3666 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other,
3667 &OutChains[0], OutChains.size());
3670 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst,
3671 SDValue Src, SDValue Size,
3672 unsigned Align, bool isVol, bool AlwaysInline,
3673 MachinePointerInfo DstPtrInfo,
3674 MachinePointerInfo SrcPtrInfo) {
3676 // Check to see if we should lower the memcpy to loads and stores first.
3677 // For cases within the target-specified limits, this is the best choice.
3678 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3680 // Memcpy with size zero? Just return the original chain.
3681 if (ConstantSize->isNullValue())
3684 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3685 ConstantSize->getZExtValue(),Align,
3686 isVol, false, DstPtrInfo, SrcPtrInfo);
3687 if (Result.getNode())
3691 // Then check to see if we should lower the memcpy with target-specific
3692 // code. If the target chooses to do this, this is the next best.
3694 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
3695 isVol, AlwaysInline,
3696 DstPtrInfo, SrcPtrInfo);
3697 if (Result.getNode())
3700 // If we really need inline code and the target declined to provide it,
3701 // use a (potentially long) sequence of loads and stores.
3703 assert(ConstantSize && "AlwaysInline requires a constant size!");
3704 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
3705 ConstantSize->getZExtValue(), Align, isVol,
3706 true, DstPtrInfo, SrcPtrInfo);
3709 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3710 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3711 // respect volatile, so they may do things like read or write memory
3712 // beyond the given memory regions. But fixing this isn't easy, and most
3713 // people don't care.
3715 // Emit a library call.
3716 TargetLowering::ArgListTy Args;
3717 TargetLowering::ArgListEntry Entry;
3718 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3719 Entry.Node = Dst; Args.push_back(Entry);
3720 Entry.Node = Src; Args.push_back(Entry);
3721 Entry.Node = Size; Args.push_back(Entry);
3722 // FIXME: pass in DebugLoc
3723 std::pair<SDValue,SDValue> CallResult =
3724 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3725 false, false, false, false, 0,
3726 TLI.getLibcallCallingConv(RTLIB::MEMCPY), false,
3727 /*isReturnValueUsed=*/false,
3728 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY),
3729 TLI.getPointerTy()),
3731 return CallResult.second;
3734 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst,
3735 SDValue Src, SDValue Size,
3736 unsigned Align, bool isVol,
3737 MachinePointerInfo DstPtrInfo,
3738 MachinePointerInfo SrcPtrInfo) {
3740 // Check to see if we should lower the memmove to loads and stores first.
3741 // For cases within the target-specified limits, this is the best choice.
3742 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3744 // Memmove with size zero? Just return the original chain.
3745 if (ConstantSize->isNullValue())
3749 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
3750 ConstantSize->getZExtValue(), Align, isVol,
3751 false, DstPtrInfo, SrcPtrInfo);
3752 if (Result.getNode())
3756 // Then check to see if we should lower the memmove with target-specific
3757 // code. If the target chooses to do this, this is the next best.
3759 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3760 DstPtrInfo, SrcPtrInfo);
3761 if (Result.getNode())
3764 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3765 // not be safe. See memcpy above for more details.
3767 // Emit a library call.
3768 TargetLowering::ArgListTy Args;
3769 TargetLowering::ArgListEntry Entry;
3770 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext());
3771 Entry.Node = Dst; Args.push_back(Entry);
3772 Entry.Node = Src; Args.push_back(Entry);
3773 Entry.Node = Size; Args.push_back(Entry);
3774 // FIXME: pass in DebugLoc
3775 std::pair<SDValue,SDValue> CallResult =
3776 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3777 false, false, false, false, 0,
3778 TLI.getLibcallCallingConv(RTLIB::MEMMOVE), false,
3779 /*isReturnValueUsed=*/false,
3780 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE),
3781 TLI.getPointerTy()),
3783 return CallResult.second;
3786 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst,
3787 SDValue Src, SDValue Size,
3788 unsigned Align, bool isVol,
3789 MachinePointerInfo DstPtrInfo) {
3791 // Check to see if we should lower the memset to stores first.
3792 // For cases within the target-specified limits, this is the best choice.
3793 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
3795 // Memset with size zero? Just return the original chain.
3796 if (ConstantSize->isNullValue())
3800 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
3801 Align, isVol, DstPtrInfo);
3803 if (Result.getNode())
3807 // Then check to see if we should lower the memset with target-specific
3808 // code. If the target chooses to do this, this is the next best.
3810 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
3812 if (Result.getNode())
3815 // Emit a library call.
3816 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext());
3817 TargetLowering::ArgListTy Args;
3818 TargetLowering::ArgListEntry Entry;
3819 Entry.Node = Dst; Entry.Ty = IntPtrTy;
3820 Args.push_back(Entry);
3821 // Extend or truncate the argument to be an i32 value for the call.
3822 if (Src.getValueType().bitsGT(MVT::i32))
3823 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
3825 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
3827 Entry.Ty = Type::getInt32Ty(*getContext());
3828 Entry.isSExt = true;
3829 Args.push_back(Entry);
3831 Entry.Ty = IntPtrTy;
3832 Entry.isSExt = false;
3833 Args.push_back(Entry);
3834 // FIXME: pass in DebugLoc
3835 std::pair<SDValue,SDValue> CallResult =
3836 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()),
3837 false, false, false, false, 0,
3838 TLI.getLibcallCallingConv(RTLIB::MEMSET), false,
3839 /*isReturnValueUsed=*/false,
3840 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET),
3841 TLI.getPointerTy()),
3843 return CallResult.second;
3846 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3847 SDValue Chain, SDValue Ptr, SDValue Cmp,
3848 SDValue Swp, MachinePointerInfo PtrInfo,
3850 AtomicOrdering Ordering,
3851 SynchronizationScope SynchScope) {
3852 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3853 Alignment = getEVTAlignment(MemVT);
3855 MachineFunction &MF = getMachineFunction();
3856 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore;
3858 // For now, atomics are considered to be volatile always.
3859 // FIXME: Volatile isn't really correct; we should keep track of atomic
3860 // orderings in the memoperand.
3861 Flags |= MachineMemOperand::MOVolatile;
3863 MachineMemOperand *MMO =
3864 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
3866 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
3867 Ordering, SynchScope);
3870 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3872 SDValue Ptr, SDValue Cmp,
3873 SDValue Swp, MachineMemOperand *MMO,
3874 AtomicOrdering Ordering,
3875 SynchronizationScope SynchScope) {
3876 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
3877 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
3879 EVT VT = Cmp.getValueType();
3881 SDVTList VTs = getVTList(VT, MVT::Other);
3882 FoldingSetNodeID ID;
3883 ID.AddInteger(MemVT.getRawBits());
3884 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
3885 AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
3887 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3888 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3889 return SDValue(E, 0);
3891 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3892 Ptr, Cmp, Swp, MMO, Ordering,
3894 CSEMap.InsertNode(N, IP);
3895 AllNodes.push_back(N);
3896 return SDValue(N, 0);
3899 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3901 SDValue Ptr, SDValue Val,
3902 const Value* PtrVal,
3904 AtomicOrdering Ordering,
3905 SynchronizationScope SynchScope) {
3906 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3907 Alignment = getEVTAlignment(MemVT);
3909 MachineFunction &MF = getMachineFunction();
3910 // A monotonic store does not load; a release store "loads" in the sense
3911 // that other stores cannot be sunk past it.
3912 // (An atomicrmw obviously both loads and stores.)
3913 unsigned Flags = MachineMemOperand::MOStore;
3914 if (Opcode != ISD::ATOMIC_STORE || Ordering > Monotonic)
3915 Flags |= MachineMemOperand::MOLoad;
3917 // For now, atomics are considered to be volatile always.
3918 // FIXME: Volatile isn't really correct; we should keep track of atomic
3919 // orderings in the memoperand.
3920 Flags |= MachineMemOperand::MOVolatile;
3922 MachineMemOperand *MMO =
3923 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3924 MemVT.getStoreSize(), Alignment);
3926 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
3927 Ordering, SynchScope);
3930 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3932 SDValue Ptr, SDValue Val,
3933 MachineMemOperand *MMO,
3934 AtomicOrdering Ordering,
3935 SynchronizationScope SynchScope) {
3936 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
3937 Opcode == ISD::ATOMIC_LOAD_SUB ||
3938 Opcode == ISD::ATOMIC_LOAD_AND ||
3939 Opcode == ISD::ATOMIC_LOAD_OR ||
3940 Opcode == ISD::ATOMIC_LOAD_XOR ||
3941 Opcode == ISD::ATOMIC_LOAD_NAND ||
3942 Opcode == ISD::ATOMIC_LOAD_MIN ||
3943 Opcode == ISD::ATOMIC_LOAD_MAX ||
3944 Opcode == ISD::ATOMIC_LOAD_UMIN ||
3945 Opcode == ISD::ATOMIC_LOAD_UMAX ||
3946 Opcode == ISD::ATOMIC_SWAP ||
3947 Opcode == ISD::ATOMIC_STORE) &&
3948 "Invalid Atomic Op");
3950 EVT VT = Val.getValueType();
3952 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
3953 getVTList(VT, MVT::Other);
3954 FoldingSetNodeID ID;
3955 ID.AddInteger(MemVT.getRawBits());
3956 SDValue Ops[] = {Chain, Ptr, Val};
3957 AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
3959 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
3960 cast<AtomicSDNode>(E)->refineAlignment(MMO);
3961 return SDValue(E, 0);
3963 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
3965 Ordering, SynchScope);
3966 CSEMap.InsertNode(N, IP);
3967 AllNodes.push_back(N);
3968 return SDValue(N, 0);
3971 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
3972 EVT VT, SDValue Chain,
3974 const Value* PtrVal,
3976 AtomicOrdering Ordering,
3977 SynchronizationScope SynchScope) {
3978 if (Alignment == 0) // Ensure that codegen never sees alignment 0
3979 Alignment = getEVTAlignment(MemVT);
3981 MachineFunction &MF = getMachineFunction();
3982 // A monotonic load does not store; an acquire load "stores" in the sense
3983 // that other loads cannot be hoisted past it.
3984 unsigned Flags = MachineMemOperand::MOLoad;
3985 if (Ordering > Monotonic)
3986 Flags |= MachineMemOperand::MOStore;
3988 // For now, atomics are considered to be volatile always.
3989 // FIXME: Volatile isn't really correct; we should keep track of atomic
3990 // orderings in the memoperand.
3991 Flags |= MachineMemOperand::MOVolatile;
3993 MachineMemOperand *MMO =
3994 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
3995 MemVT.getStoreSize(), Alignment);
3997 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO,
3998 Ordering, SynchScope);
4001 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT,
4002 EVT VT, SDValue Chain,
4004 MachineMemOperand *MMO,
4005 AtomicOrdering Ordering,
4006 SynchronizationScope SynchScope) {
4007 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4009 SDVTList VTs = getVTList(VT, MVT::Other);
4010 FoldingSetNodeID ID;
4011 ID.AddInteger(MemVT.getRawBits());
4012 SDValue Ops[] = {Chain, Ptr};
4013 AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
4015 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4016 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4017 return SDValue(E, 0);
4019 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain,
4020 Ptr, MMO, Ordering, SynchScope);
4021 CSEMap.InsertNode(N, IP);
4022 AllNodes.push_back(N);
4023 return SDValue(N, 0);
4026 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4027 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps,
4032 SmallVector<EVT, 4> VTs;
4033 VTs.reserve(NumOps);
4034 for (unsigned i = 0; i < NumOps; ++i)
4035 VTs.push_back(Ops[i].getValueType());
4036 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps),
4041 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
4042 const EVT *VTs, unsigned NumVTs,
4043 const SDValue *Ops, unsigned NumOps,
4044 EVT MemVT, MachinePointerInfo PtrInfo,
4045 unsigned Align, bool Vol,
4046 bool ReadMem, bool WriteMem) {
4047 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps,
4048 MemVT, PtrInfo, Align, Vol,
4053 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4054 const SDValue *Ops, unsigned NumOps,
4055 EVT MemVT, MachinePointerInfo PtrInfo,
4056 unsigned Align, bool Vol,
4057 bool ReadMem, bool WriteMem) {
4058 if (Align == 0) // Ensure that codegen never sees alignment 0
4059 Align = getEVTAlignment(MemVT);
4061 MachineFunction &MF = getMachineFunction();
4064 Flags |= MachineMemOperand::MOStore;
4066 Flags |= MachineMemOperand::MOLoad;
4068 Flags |= MachineMemOperand::MOVolatile;
4069 MachineMemOperand *MMO =
4070 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4072 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO);
4076 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
4077 const SDValue *Ops, unsigned NumOps,
4078 EVT MemVT, MachineMemOperand *MMO) {
4079 assert((Opcode == ISD::INTRINSIC_VOID ||
4080 Opcode == ISD::INTRINSIC_W_CHAIN ||
4081 Opcode == ISD::PREFETCH ||
4082 (Opcode <= INT_MAX &&
4083 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4084 "Opcode is not a memory-accessing opcode!");
4086 // Memoize the node unless it returns a flag.
4087 MemIntrinsicSDNode *N;
4088 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4089 FoldingSetNodeID ID;
4090 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4092 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4093 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4094 return SDValue(E, 0);
4097 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4099 CSEMap.InsertNode(N, IP);
4101 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps,
4104 AllNodes.push_back(N);
4105 return SDValue(N, 0);
4108 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4109 /// MachinePointerInfo record from it. This is particularly useful because the
4110 /// code generator has many cases where it doesn't bother passing in a
4111 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4112 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4113 // If this is FI+Offset, we can model it.
4114 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4115 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4117 // If this is (FI+Offset1)+Offset2, we can model it.
4118 if (Ptr.getOpcode() != ISD::ADD ||
4119 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4120 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4121 return MachinePointerInfo();
4123 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4124 return MachinePointerInfo::getFixedStack(FI, Offset+
4125 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4128 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4129 /// MachinePointerInfo record from it. This is particularly useful because the
4130 /// code generator has many cases where it doesn't bother passing in a
4131 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4132 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4133 // If the 'Offset' value isn't a constant, we can't handle this.
4134 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4135 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4136 if (OffsetOp.getOpcode() == ISD::UNDEF)
4137 return InferPointerInfo(Ptr);
4138 return MachinePointerInfo();
4143 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4144 EVT VT, DebugLoc dl, SDValue Chain,
4145 SDValue Ptr, SDValue Offset,
4146 MachinePointerInfo PtrInfo, EVT MemVT,
4147 bool isVolatile, bool isNonTemporal, bool isInvariant,
4148 unsigned Alignment, const MDNode *TBAAInfo) {
4149 assert(Chain.getValueType() == MVT::Other &&
4150 "Invalid chain type");
4151 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4152 Alignment = getEVTAlignment(VT);
4154 unsigned Flags = MachineMemOperand::MOLoad;
4156 Flags |= MachineMemOperand::MOVolatile;
4158 Flags |= MachineMemOperand::MONonTemporal;
4160 Flags |= MachineMemOperand::MOInvariant;
4162 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4165 PtrInfo = InferPointerInfo(Ptr, Offset);
4167 MachineFunction &MF = getMachineFunction();
4168 MachineMemOperand *MMO =
4169 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4171 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4175 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4176 EVT VT, DebugLoc dl, SDValue Chain,
4177 SDValue Ptr, SDValue Offset, EVT MemVT,
4178 MachineMemOperand *MMO) {
4180 ExtType = ISD::NON_EXTLOAD;
4181 } else if (ExtType == ISD::NON_EXTLOAD) {
4182 assert(VT == MemVT && "Non-extending load from different memory type!");
4185 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4186 "Should only be an extending load, not truncating!");
4187 assert(VT.isInteger() == MemVT.isInteger() &&
4188 "Cannot convert from FP to Int or Int -> FP!");
4189 assert(VT.isVector() == MemVT.isVector() &&
4190 "Cannot use trunc store to convert to or from a vector!");
4191 assert((!VT.isVector() ||
4192 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4193 "Cannot use trunc store to change the number of vector elements!");
4196 bool Indexed = AM != ISD::UNINDEXED;
4197 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4198 "Unindexed load with an offset!");
4200 SDVTList VTs = Indexed ?
4201 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4202 SDValue Ops[] = { Chain, Ptr, Offset };
4203 FoldingSetNodeID ID;
4204 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
4205 ID.AddInteger(MemVT.getRawBits());
4206 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4207 MMO->isNonTemporal(),
4208 MMO->isInvariant()));
4210 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4211 cast<LoadSDNode>(E)->refineAlignment(MMO);
4212 return SDValue(E, 0);
4214 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType,
4216 CSEMap.InsertNode(N, IP);
4217 AllNodes.push_back(N);
4218 return SDValue(N, 0);
4221 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl,
4222 SDValue Chain, SDValue Ptr,
4223 MachinePointerInfo PtrInfo,
4224 bool isVolatile, bool isNonTemporal,
4225 bool isInvariant, unsigned Alignment,
4226 const MDNode *TBAAInfo) {
4227 SDValue Undef = getUNDEF(Ptr.getValueType());
4228 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4229 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4233 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
4234 SDValue Chain, SDValue Ptr,
4235 MachinePointerInfo PtrInfo, EVT MemVT,
4236 bool isVolatile, bool isNonTemporal,
4237 unsigned Alignment, const MDNode *TBAAInfo) {
4238 SDValue Undef = getUNDEF(Ptr.getValueType());
4239 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4240 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4246 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
4247 SDValue Offset, ISD::MemIndexedMode AM) {
4248 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4249 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4250 "Load is already a indexed load!");
4251 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4252 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4253 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4254 false, LD->getAlignment());
4257 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4258 SDValue Ptr, MachinePointerInfo PtrInfo,
4259 bool isVolatile, bool isNonTemporal,
4260 unsigned Alignment, const MDNode *TBAAInfo) {
4261 assert(Chain.getValueType() == MVT::Other &&
4262 "Invalid chain type");
4263 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4264 Alignment = getEVTAlignment(Val.getValueType());
4266 unsigned Flags = MachineMemOperand::MOStore;
4268 Flags |= MachineMemOperand::MOVolatile;
4270 Flags |= MachineMemOperand::MONonTemporal;
4273 PtrInfo = InferPointerInfo(Ptr);
4275 MachineFunction &MF = getMachineFunction();
4276 MachineMemOperand *MMO =
4277 MF.getMachineMemOperand(PtrInfo, Flags,
4278 Val.getValueType().getStoreSize(), Alignment,
4281 return getStore(Chain, dl, Val, Ptr, MMO);
4284 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val,
4285 SDValue Ptr, MachineMemOperand *MMO) {
4286 assert(Chain.getValueType() == MVT::Other &&
4287 "Invalid chain type");
4288 EVT VT = Val.getValueType();
4289 SDVTList VTs = getVTList(MVT::Other);
4290 SDValue Undef = getUNDEF(Ptr.getValueType());
4291 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4292 FoldingSetNodeID ID;
4293 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4294 ID.AddInteger(VT.getRawBits());
4295 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4296 MMO->isNonTemporal(), MMO->isInvariant()));
4298 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4299 cast<StoreSDNode>(E)->refineAlignment(MMO);
4300 return SDValue(E, 0);
4302 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4304 CSEMap.InsertNode(N, IP);
4305 AllNodes.push_back(N);
4306 return SDValue(N, 0);
4309 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4310 SDValue Ptr, MachinePointerInfo PtrInfo,
4311 EVT SVT,bool isVolatile, bool isNonTemporal,
4313 const MDNode *TBAAInfo) {
4314 assert(Chain.getValueType() == MVT::Other &&
4315 "Invalid chain type");
4316 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4317 Alignment = getEVTAlignment(SVT);
4319 unsigned Flags = MachineMemOperand::MOStore;
4321 Flags |= MachineMemOperand::MOVolatile;
4323 Flags |= MachineMemOperand::MONonTemporal;
4326 PtrInfo = InferPointerInfo(Ptr);
4328 MachineFunction &MF = getMachineFunction();
4329 MachineMemOperand *MMO =
4330 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4333 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4336 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val,
4337 SDValue Ptr, EVT SVT,
4338 MachineMemOperand *MMO) {
4339 EVT VT = Val.getValueType();
4341 assert(Chain.getValueType() == MVT::Other &&
4342 "Invalid chain type");
4344 return getStore(Chain, dl, Val, Ptr, MMO);
4346 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4347 "Should only be a truncating store, not extending!");
4348 assert(VT.isInteger() == SVT.isInteger() &&
4349 "Can't do FP-INT conversion!");
4350 assert(VT.isVector() == SVT.isVector() &&
4351 "Cannot use trunc store to convert to or from a vector!");
4352 assert((!VT.isVector() ||
4353 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4354 "Cannot use trunc store to change the number of vector elements!");
4356 SDVTList VTs = getVTList(MVT::Other);
4357 SDValue Undef = getUNDEF(Ptr.getValueType());
4358 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4359 FoldingSetNodeID ID;
4360 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4361 ID.AddInteger(SVT.getRawBits());
4362 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4363 MMO->isNonTemporal(), MMO->isInvariant()));
4365 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4366 cast<StoreSDNode>(E)->refineAlignment(MMO);
4367 return SDValue(E, 0);
4369 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED,
4371 CSEMap.InsertNode(N, IP);
4372 AllNodes.push_back(N);
4373 return SDValue(N, 0);
4377 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base,
4378 SDValue Offset, ISD::MemIndexedMode AM) {
4379 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4380 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4381 "Store is already a indexed store!");
4382 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4383 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4384 FoldingSetNodeID ID;
4385 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
4386 ID.AddInteger(ST->getMemoryVT().getRawBits());
4387 ID.AddInteger(ST->getRawSubclassData());
4389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4390 return SDValue(E, 0);
4392 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM,
4393 ST->isTruncatingStore(),
4395 ST->getMemOperand());
4396 CSEMap.InsertNode(N, IP);
4397 AllNodes.push_back(N);
4398 return SDValue(N, 0);
4401 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl,
4402 SDValue Chain, SDValue Ptr,
4405 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4406 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4);
4409 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4410 const SDUse *Ops, unsigned NumOps) {
4412 case 0: return getNode(Opcode, DL, VT);
4413 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4414 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4415 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4419 // Copy from an SDUse array into an SDValue array for use with
4420 // the regular getNode logic.
4421 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps);
4422 return getNode(Opcode, DL, VT, &NewOps[0], NumOps);
4425 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT,
4426 const SDValue *Ops, unsigned NumOps) {
4428 case 0: return getNode(Opcode, DL, VT);
4429 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4430 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4431 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4437 case ISD::SELECT_CC: {
4438 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4439 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4440 "LHS and RHS of condition must have same type!");
4441 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4442 "True and False arms of SelectCC must have same type!");
4443 assert(Ops[2].getValueType() == VT &&
4444 "select_cc node must be of same type as true and false value!");
4448 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4449 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4450 "LHS/RHS of comparison should match types!");
4457 SDVTList VTs = getVTList(VT);
4459 if (VT != MVT::Glue) {
4460 FoldingSetNodeID ID;
4461 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
4464 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4465 return SDValue(E, 0);
4467 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4468 CSEMap.InsertNode(N, IP);
4470 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps);
4473 AllNodes.push_back(N);
4477 return SDValue(N, 0);
4480 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4481 const std::vector<EVT> &ResultTys,
4482 const SDValue *Ops, unsigned NumOps) {
4483 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()),
4487 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL,
4488 const EVT *VTs, unsigned NumVTs,
4489 const SDValue *Ops, unsigned NumOps) {
4491 return getNode(Opcode, DL, VTs[0], Ops, NumOps);
4492 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps);
4495 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4496 const SDValue *Ops, unsigned NumOps) {
4497 if (VTList.NumVTs == 1)
4498 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps);
4502 // FIXME: figure out how to safely handle things like
4503 // int foo(int x) { return 1 << (x & 255); }
4504 // int bar() { return foo(256); }
4505 case ISD::SRA_PARTS:
4506 case ISD::SRL_PARTS:
4507 case ISD::SHL_PARTS:
4508 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4509 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4510 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4511 else if (N3.getOpcode() == ISD::AND)
4512 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4513 // If the and is only masking out bits that cannot effect the shift,
4514 // eliminate the and.
4515 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4516 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4517 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4523 // Memoize the node unless it returns a flag.
4525 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4526 FoldingSetNodeID ID;
4527 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
4529 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4530 return SDValue(E, 0);
4533 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4534 } else if (NumOps == 2) {
4535 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4536 } else if (NumOps == 3) {
4537 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4540 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4542 CSEMap.InsertNode(N, IP);
4545 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]);
4546 } else if (NumOps == 2) {
4547 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]);
4548 } else if (NumOps == 3) {
4549 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1],
4552 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps);
4555 AllNodes.push_back(N);
4559 return SDValue(N, 0);
4562 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) {
4563 return getNode(Opcode, DL, VTList, 0, 0);
4566 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4568 SDValue Ops[] = { N1 };
4569 return getNode(Opcode, DL, VTList, Ops, 1);
4572 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4573 SDValue N1, SDValue N2) {
4574 SDValue Ops[] = { N1, N2 };
4575 return getNode(Opcode, DL, VTList, Ops, 2);
4578 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4579 SDValue N1, SDValue N2, SDValue N3) {
4580 SDValue Ops[] = { N1, N2, N3 };
4581 return getNode(Opcode, DL, VTList, Ops, 3);
4584 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4585 SDValue N1, SDValue N2, SDValue N3,
4587 SDValue Ops[] = { N1, N2, N3, N4 };
4588 return getNode(Opcode, DL, VTList, Ops, 4);
4591 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList,
4592 SDValue N1, SDValue N2, SDValue N3,
4593 SDValue N4, SDValue N5) {
4594 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4595 return getNode(Opcode, DL, VTList, Ops, 5);
4598 SDVTList SelectionDAG::getVTList(EVT VT) {
4599 return makeVTList(SDNode::getValueTypeList(VT), 1);
4602 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4603 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4604 E = VTList.rend(); I != E; ++I)
4605 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
4608 EVT *Array = Allocator.Allocate<EVT>(2);
4611 SDVTList Result = makeVTList(Array, 2);
4612 VTList.push_back(Result);
4616 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
4617 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4618 E = VTList.rend(); I != E; ++I)
4619 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4623 EVT *Array = Allocator.Allocate<EVT>(3);
4627 SDVTList Result = makeVTList(Array, 3);
4628 VTList.push_back(Result);
4632 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
4633 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4634 E = VTList.rend(); I != E; ++I)
4635 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
4636 I->VTs[2] == VT3 && I->VTs[3] == VT4)
4639 EVT *Array = Allocator.Allocate<EVT>(4);
4644 SDVTList Result = makeVTList(Array, 4);
4645 VTList.push_back(Result);
4649 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) {
4651 case 0: llvm_unreachable("Cannot have nodes without results!");
4652 case 1: return getVTList(VTs[0]);
4653 case 2: return getVTList(VTs[0], VTs[1]);
4654 case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
4655 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]);
4659 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
4660 E = VTList.rend(); I != E; ++I) {
4661 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
4664 bool NoMatch = false;
4665 for (unsigned i = 2; i != NumVTs; ++i)
4666 if (VTs[i] != I->VTs[i]) {
4674 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
4675 std::copy(VTs, VTs+NumVTs, Array);
4676 SDVTList Result = makeVTList(Array, NumVTs);
4677 VTList.push_back(Result);
4682 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4683 /// specified operands. If the resultant node already exists in the DAG,
4684 /// this does not modify the specified node, instead it returns the node that
4685 /// already exists. If the resultant node does not exist in the DAG, the
4686 /// input node is returned. As a degenerate case, if you specify the same
4687 /// input operands as the node already has, the input node is returned.
4688 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
4689 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
4691 // Check to see if there is no change.
4692 if (Op == N->getOperand(0)) return N;
4694 // See if the modified node already exists.
4695 void *InsertPos = 0;
4696 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
4699 // Nope it doesn't. Remove the node from its current place in the maps.
4701 if (!RemoveNodeFromCSEMaps(N))
4704 // Now we update the operands.
4705 N->OperandList[0].set(Op);
4707 // If this gets put into a CSE map, add it.
4708 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4712 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
4713 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
4715 // Check to see if there is no change.
4716 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
4717 return N; // No operands changed, just return the input node.
4719 // See if the modified node already exists.
4720 void *InsertPos = 0;
4721 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
4724 // Nope it doesn't. Remove the node from its current place in the maps.
4726 if (!RemoveNodeFromCSEMaps(N))
4729 // Now we update the operands.
4730 if (N->OperandList[0] != Op1)
4731 N->OperandList[0].set(Op1);
4732 if (N->OperandList[1] != Op2)
4733 N->OperandList[1].set(Op2);
4735 // If this gets put into a CSE map, add it.
4736 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4740 SDNode *SelectionDAG::
4741 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
4742 SDValue Ops[] = { Op1, Op2, Op3 };
4743 return UpdateNodeOperands(N, Ops, 3);
4746 SDNode *SelectionDAG::
4747 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4748 SDValue Op3, SDValue Op4) {
4749 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
4750 return UpdateNodeOperands(N, Ops, 4);
4753 SDNode *SelectionDAG::
4754 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
4755 SDValue Op3, SDValue Op4, SDValue Op5) {
4756 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
4757 return UpdateNodeOperands(N, Ops, 5);
4760 SDNode *SelectionDAG::
4761 UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) {
4762 assert(N->getNumOperands() == NumOps &&
4763 "Update with wrong number of operands");
4765 // Check to see if there is no change.
4766 bool AnyChange = false;
4767 for (unsigned i = 0; i != NumOps; ++i) {
4768 if (Ops[i] != N->getOperand(i)) {
4774 // No operands changed, just return the input node.
4775 if (!AnyChange) return N;
4777 // See if the modified node already exists.
4778 void *InsertPos = 0;
4779 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
4782 // Nope it doesn't. Remove the node from its current place in the maps.
4784 if (!RemoveNodeFromCSEMaps(N))
4787 // Now we update the operands.
4788 for (unsigned i = 0; i != NumOps; ++i)
4789 if (N->OperandList[i] != Ops[i])
4790 N->OperandList[i].set(Ops[i]);
4792 // If this gets put into a CSE map, add it.
4793 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
4797 /// DropOperands - Release the operands and set this node to have
4799 void SDNode::DropOperands() {
4800 // Unlike the code in MorphNodeTo that does this, we don't need to
4801 // watch for dead nodes here.
4802 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
4808 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4811 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4813 SDVTList VTs = getVTList(VT);
4814 return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
4817 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4818 EVT VT, SDValue Op1) {
4819 SDVTList VTs = getVTList(VT);
4820 SDValue Ops[] = { Op1 };
4821 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4824 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4825 EVT VT, SDValue Op1,
4827 SDVTList VTs = getVTList(VT);
4828 SDValue Ops[] = { Op1, Op2 };
4829 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4832 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4833 EVT VT, SDValue Op1,
4834 SDValue Op2, SDValue Op3) {
4835 SDVTList VTs = getVTList(VT);
4836 SDValue Ops[] = { Op1, Op2, Op3 };
4837 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4840 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4841 EVT VT, const SDValue *Ops,
4843 SDVTList VTs = getVTList(VT);
4844 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4847 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4848 EVT VT1, EVT VT2, const SDValue *Ops,
4850 SDVTList VTs = getVTList(VT1, VT2);
4851 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4854 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4856 SDVTList VTs = getVTList(VT1, VT2);
4857 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0);
4860 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4861 EVT VT1, EVT VT2, EVT VT3,
4862 const SDValue *Ops, unsigned NumOps) {
4863 SDVTList VTs = getVTList(VT1, VT2, VT3);
4864 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4867 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4868 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
4869 const SDValue *Ops, unsigned NumOps) {
4870 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
4871 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
4874 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4877 SDVTList VTs = getVTList(VT1, VT2);
4878 SDValue Ops[] = { Op1 };
4879 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
4882 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4884 SDValue Op1, SDValue Op2) {
4885 SDVTList VTs = getVTList(VT1, VT2);
4886 SDValue Ops[] = { Op1, Op2 };
4887 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
4890 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4892 SDValue Op1, SDValue Op2,
4894 SDVTList VTs = getVTList(VT1, VT2);
4895 SDValue Ops[] = { Op1, Op2, Op3 };
4896 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4899 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4900 EVT VT1, EVT VT2, EVT VT3,
4901 SDValue Op1, SDValue Op2,
4903 SDVTList VTs = getVTList(VT1, VT2, VT3);
4904 SDValue Ops[] = { Op1, Op2, Op3 };
4905 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
4908 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
4909 SDVTList VTs, const SDValue *Ops,
4911 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
4912 // Reset the NodeID to -1.
4917 /// MorphNodeTo - This *mutates* the specified node to have the specified
4918 /// return type, opcode, and operands.
4920 /// Note that MorphNodeTo returns the resultant node. If there is already a
4921 /// node of the specified opcode and operands, it returns that node instead of
4922 /// the current one. Note that the DebugLoc need not be the same.
4924 /// Using MorphNodeTo is faster than creating a new node and swapping it in
4925 /// with ReplaceAllUsesWith both because it often avoids allocating a new
4926 /// node, and because it doesn't require CSE recalculation for any of
4927 /// the node's users.
4929 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
4930 SDVTList VTs, const SDValue *Ops,
4932 // If an identical node already exists, use it.
4934 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
4935 FoldingSetNodeID ID;
4936 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
4937 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
4941 if (!RemoveNodeFromCSEMaps(N))
4944 // Start the morphing.
4946 N->ValueList = VTs.VTs;
4947 N->NumValues = VTs.NumVTs;
4949 // Clear the operands list, updating used nodes to remove this from their
4950 // use list. Keep track of any operands that become dead as a result.
4951 SmallPtrSet<SDNode*, 16> DeadNodeSet;
4952 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
4954 SDNode *Used = Use.getNode();
4956 if (Used->use_empty())
4957 DeadNodeSet.insert(Used);
4960 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
4961 // Initialize the memory references information.
4962 MN->setMemRefs(0, 0);
4963 // If NumOps is larger than the # of operands we can have in a
4964 // MachineSDNode, reallocate the operand list.
4965 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
4966 if (MN->OperandsNeedDelete)
4967 delete[] MN->OperandList;
4968 if (NumOps > array_lengthof(MN->LocalOperands))
4969 // We're creating a final node that will live unmorphed for the
4970 // remainder of the current SelectionDAG iteration, so we can allocate
4971 // the operands directly out of a pool with no recycling metadata.
4972 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
4975 MN->InitOperands(MN->LocalOperands, Ops, NumOps);
4976 MN->OperandsNeedDelete = false;
4978 MN->InitOperands(MN->OperandList, Ops, NumOps);
4980 // If NumOps is larger than the # of operands we currently have, reallocate
4981 // the operand list.
4982 if (NumOps > N->NumOperands) {
4983 if (N->OperandsNeedDelete)
4984 delete[] N->OperandList;
4985 N->InitOperands(new SDUse[NumOps], Ops, NumOps);
4986 N->OperandsNeedDelete = true;
4988 N->InitOperands(N->OperandList, Ops, NumOps);
4991 // Delete any nodes that are still dead after adding the uses for the
4993 if (!DeadNodeSet.empty()) {
4994 SmallVector<SDNode *, 16> DeadNodes;
4995 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
4996 E = DeadNodeSet.end(); I != E; ++I)
4997 if ((*I)->use_empty())
4998 DeadNodes.push_back(*I);
4999 RemoveDeadNodes(DeadNodes);
5003 CSEMap.InsertNode(N, IP); // Memoize the new node.
5008 /// getMachineNode - These are used for target selectors to create a new node
5009 /// with specified return type(s), MachineInstr opcode, and operands.
5011 /// Note that getMachineNode returns the resultant node. If there is already a
5012 /// node of the specified opcode and operands, it returns that node instead of
5013 /// the current one.
5015 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) {
5016 SDVTList VTs = getVTList(VT);
5017 return getMachineNode(Opcode, dl, VTs, 0, 0);
5021 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) {
5022 SDVTList VTs = getVTList(VT);
5023 SDValue Ops[] = { Op1 };
5024 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5028 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5029 SDValue Op1, SDValue Op2) {
5030 SDVTList VTs = getVTList(VT);
5031 SDValue Ops[] = { Op1, Op2 };
5032 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5036 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5037 SDValue Op1, SDValue Op2, SDValue Op3) {
5038 SDVTList VTs = getVTList(VT);
5039 SDValue Ops[] = { Op1, Op2, Op3 };
5040 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5044 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
5045 const SDValue *Ops, unsigned NumOps) {
5046 SDVTList VTs = getVTList(VT);
5047 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5051 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) {
5052 SDVTList VTs = getVTList(VT1, VT2);
5053 return getMachineNode(Opcode, dl, VTs, 0, 0);
5057 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5058 EVT VT1, EVT VT2, SDValue Op1) {
5059 SDVTList VTs = getVTList(VT1, VT2);
5060 SDValue Ops[] = { Op1 };
5061 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5065 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5066 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5067 SDVTList VTs = getVTList(VT1, VT2);
5068 SDValue Ops[] = { Op1, Op2 };
5069 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5073 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5074 EVT VT1, EVT VT2, SDValue Op1,
5075 SDValue Op2, SDValue Op3) {
5076 SDVTList VTs = getVTList(VT1, VT2);
5077 SDValue Ops[] = { Op1, Op2, Op3 };
5078 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5082 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5084 const SDValue *Ops, unsigned NumOps) {
5085 SDVTList VTs = getVTList(VT1, VT2);
5086 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5090 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5091 EVT VT1, EVT VT2, EVT VT3,
5092 SDValue Op1, SDValue Op2) {
5093 SDVTList VTs = getVTList(VT1, VT2, VT3);
5094 SDValue Ops[] = { Op1, Op2 };
5095 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5099 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5100 EVT VT1, EVT VT2, EVT VT3,
5101 SDValue Op1, SDValue Op2, SDValue Op3) {
5102 SDVTList VTs = getVTList(VT1, VT2, VT3);
5103 SDValue Ops[] = { Op1, Op2, Op3 };
5104 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops));
5108 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5109 EVT VT1, EVT VT2, EVT VT3,
5110 const SDValue *Ops, unsigned NumOps) {
5111 SDVTList VTs = getVTList(VT1, VT2, VT3);
5112 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5116 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
5117 EVT VT2, EVT VT3, EVT VT4,
5118 const SDValue *Ops, unsigned NumOps) {
5119 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5120 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5124 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl,
5125 const std::vector<EVT> &ResultTys,
5126 const SDValue *Ops, unsigned NumOps) {
5127 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size());
5128 return getMachineNode(Opcode, dl, VTs, Ops, NumOps);
5132 SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
5133 const SDValue *Ops, unsigned NumOps) {
5134 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5139 FoldingSetNodeID ID;
5140 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps);
5142 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5143 return cast<MachineSDNode>(E);
5146 // Allocate a new MachineSDNode.
5147 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs);
5149 // Initialize the operands list.
5150 if (NumOps > array_lengthof(N->LocalOperands))
5151 // We're creating a final node that will live unmorphed for the
5152 // remainder of the current SelectionDAG iteration, so we can allocate
5153 // the operands directly out of a pool with no recycling metadata.
5154 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5157 N->InitOperands(N->LocalOperands, Ops, NumOps);
5158 N->OperandsNeedDelete = false;
5161 CSEMap.InsertNode(N, IP);
5163 AllNodes.push_back(N);
5165 VerifyMachineNode(N);
5170 /// getTargetExtractSubreg - A convenience function for creating
5171 /// TargetOpcode::EXTRACT_SUBREG nodes.
5173 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
5175 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5176 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5177 VT, Operand, SRIdxVal);
5178 return SDValue(Subreg, 0);
5181 /// getTargetInsertSubreg - A convenience function for creating
5182 /// TargetOpcode::INSERT_SUBREG nodes.
5184 SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
5185 SDValue Operand, SDValue Subreg) {
5186 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5187 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5188 VT, Operand, Subreg, SRIdxVal);
5189 return SDValue(Result, 0);
5192 /// getNodeIfExists - Get the specified node if it's already available, or
5193 /// else return NULL.
5194 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5195 const SDValue *Ops, unsigned NumOps) {
5196 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5197 FoldingSetNodeID ID;
5198 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
5200 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5206 /// getDbgValue - Creates a SDDbgValue node.
5209 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
5210 DebugLoc DL, unsigned O) {
5211 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O);
5215 SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
5216 DebugLoc DL, unsigned O) {
5217 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5221 SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5222 DebugLoc DL, unsigned O) {
5223 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5228 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5229 /// pointed to by a use iterator is deleted, increment the use iterator
5230 /// so that it doesn't dangle.
5232 /// This class also manages a "downlink" DAGUpdateListener, to forward
5233 /// messages to ReplaceAllUsesWith's callers.
5235 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5236 SelectionDAG::DAGUpdateListener *DownLink;
5237 SDNode::use_iterator &UI;
5238 SDNode::use_iterator &UE;
5240 virtual void NodeDeleted(SDNode *N, SDNode *E) {
5241 // Increment the iterator as needed.
5242 while (UI != UE && N == *UI)
5245 // Then forward the message.
5246 if (DownLink) DownLink->NodeDeleted(N, E);
5249 virtual void NodeUpdated(SDNode *N) {
5250 // Just forward the message.
5251 if (DownLink) DownLink->NodeUpdated(N);
5255 RAUWUpdateListener(SelectionDAG::DAGUpdateListener *dl,
5256 SDNode::use_iterator &ui,
5257 SDNode::use_iterator &ue)
5258 : DownLink(dl), UI(ui), UE(ue) {}
5263 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5264 /// This can cause recursive merging of nodes in the DAG.
5266 /// This version assumes From has a single result value.
5268 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To,
5269 DAGUpdateListener *UpdateListener) {
5270 SDNode *From = FromN.getNode();
5271 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5272 "Cannot replace with this method!");
5273 assert(From != To.getNode() && "Cannot replace uses of with self");
5275 // Iterate over all the existing uses of From. New uses will be added
5276 // to the beginning of the use list, which we avoid visiting.
5277 // This specifically avoids visiting uses of From that arise while the
5278 // replacement is happening, because any such uses would be the result
5279 // of CSE: If an existing node looks like From after one of its operands
5280 // is replaced by To, we don't want to replace of all its users with To
5281 // too. See PR3018 for more info.
5282 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5283 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5287 // This node is about to morph, remove its old self from the CSE maps.
5288 RemoveNodeFromCSEMaps(User);
5290 // A user can appear in a use list multiple times, and when this
5291 // happens the uses are usually next to each other in the list.
5292 // To help reduce the number of CSE recomputations, process all
5293 // the uses of this user that we can find this way.
5295 SDUse &Use = UI.getUse();
5298 } while (UI != UE && *UI == User);
5300 // Now that we have modified User, add it back to the CSE maps. If it
5301 // already exists there, recursively merge the results together.
5302 AddModifiedNodeToCSEMaps(User, &Listener);
5305 // If we just RAUW'd the root, take note.
5306 if (FromN == getRoot())
5310 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5311 /// This can cause recursive merging of nodes in the DAG.
5313 /// This version assumes that for each value of From, there is a
5314 /// corresponding value in To in the same position with the same type.
5316 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
5317 DAGUpdateListener *UpdateListener) {
5319 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5320 assert((!From->hasAnyUseOfValue(i) ||
5321 From->getValueType(i) == To->getValueType(i)) &&
5322 "Cannot use this version of ReplaceAllUsesWith!");
5325 // Handle the trivial case.
5329 // Iterate over just the existing users of From. See the comments in
5330 // the ReplaceAllUsesWith above.
5331 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5332 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5336 // This node is about to morph, remove its old self from the CSE maps.
5337 RemoveNodeFromCSEMaps(User);
5339 // A user can appear in a use list multiple times, and when this
5340 // happens the uses are usually next to each other in the list.
5341 // To help reduce the number of CSE recomputations, process all
5342 // the uses of this user that we can find this way.
5344 SDUse &Use = UI.getUse();
5347 } while (UI != UE && *UI == User);
5349 // Now that we have modified User, add it back to the CSE maps. If it
5350 // already exists there, recursively merge the results together.
5351 AddModifiedNodeToCSEMaps(User, &Listener);
5354 // If we just RAUW'd the root, take note.
5355 if (From == getRoot().getNode())
5356 setRoot(SDValue(To, getRoot().getResNo()));
5359 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5360 /// This can cause recursive merging of nodes in the DAG.
5362 /// This version can replace From with any result values. To must match the
5363 /// number and types of values returned by From.
5364 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
5366 DAGUpdateListener *UpdateListener) {
5367 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5368 return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener);
5370 // Iterate over just the existing users of From. See the comments in
5371 // the ReplaceAllUsesWith above.
5372 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5373 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5377 // This node is about to morph, remove its old self from the CSE maps.
5378 RemoveNodeFromCSEMaps(User);
5380 // A user can appear in a use list multiple times, and when this
5381 // happens the uses are usually next to each other in the list.
5382 // To help reduce the number of CSE recomputations, process all
5383 // the uses of this user that we can find this way.
5385 SDUse &Use = UI.getUse();
5386 const SDValue &ToOp = To[Use.getResNo()];
5389 } while (UI != UE && *UI == User);
5391 // Now that we have modified User, add it back to the CSE maps. If it
5392 // already exists there, recursively merge the results together.
5393 AddModifiedNodeToCSEMaps(User, &Listener);
5396 // If we just RAUW'd the root, take note.
5397 if (From == getRoot().getNode())
5398 setRoot(SDValue(To[getRoot().getResNo()]));
5401 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5402 /// uses of other values produced by From.getNode() alone. The Deleted
5403 /// vector is handled the same way as for ReplaceAllUsesWith.
5404 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
5405 DAGUpdateListener *UpdateListener){
5406 // Handle the really simple, really trivial case efficiently.
5407 if (From == To) return;
5409 // Handle the simple, trivial, case efficiently.
5410 if (From.getNode()->getNumValues() == 1) {
5411 ReplaceAllUsesWith(From, To, UpdateListener);
5415 // Iterate over just the existing users of From. See the comments in
5416 // the ReplaceAllUsesWith above.
5417 SDNode::use_iterator UI = From.getNode()->use_begin(),
5418 UE = From.getNode()->use_end();
5419 RAUWUpdateListener Listener(UpdateListener, UI, UE);
5422 bool UserRemovedFromCSEMaps = false;
5424 // A user can appear in a use list multiple times, and when this
5425 // happens the uses are usually next to each other in the list.
5426 // To help reduce the number of CSE recomputations, process all
5427 // the uses of this user that we can find this way.
5429 SDUse &Use = UI.getUse();
5431 // Skip uses of different values from the same node.
5432 if (Use.getResNo() != From.getResNo()) {
5437 // If this node hasn't been modified yet, it's still in the CSE maps,
5438 // so remove its old self from the CSE maps.
5439 if (!UserRemovedFromCSEMaps) {
5440 RemoveNodeFromCSEMaps(User);
5441 UserRemovedFromCSEMaps = true;
5446 } while (UI != UE && *UI == User);
5448 // We are iterating over all uses of the From node, so if a use
5449 // doesn't use the specific value, no changes are made.
5450 if (!UserRemovedFromCSEMaps)
5453 // Now that we have modified User, add it back to the CSE maps. If it
5454 // already exists there, recursively merge the results together.
5455 AddModifiedNodeToCSEMaps(User, &Listener);
5458 // If we just RAUW'd the root, take note.
5459 if (From == getRoot())
5464 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5465 /// to record information about a use.
5472 /// operator< - Sort Memos by User.
5473 bool operator<(const UseMemo &L, const UseMemo &R) {
5474 return (intptr_t)L.User < (intptr_t)R.User;
5478 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5479 /// uses of other values produced by From.getNode() alone. The same value
5480 /// may appear in both the From and To list. The Deleted vector is
5481 /// handled the same way as for ReplaceAllUsesWith.
5482 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5485 DAGUpdateListener *UpdateListener){
5486 // Handle the simple, trivial case efficiently.
5488 return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener);
5490 // Read up all the uses and make records of them. This helps
5491 // processing new uses that are introduced during the
5492 // replacement process.
5493 SmallVector<UseMemo, 4> Uses;
5494 for (unsigned i = 0; i != Num; ++i) {
5495 unsigned FromResNo = From[i].getResNo();
5496 SDNode *FromNode = From[i].getNode();
5497 for (SDNode::use_iterator UI = FromNode->use_begin(),
5498 E = FromNode->use_end(); UI != E; ++UI) {
5499 SDUse &Use = UI.getUse();
5500 if (Use.getResNo() == FromResNo) {
5501 UseMemo Memo = { *UI, i, &Use };
5502 Uses.push_back(Memo);
5507 // Sort the uses, so that all the uses from a given User are together.
5508 std::sort(Uses.begin(), Uses.end());
5510 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5511 UseIndex != UseIndexEnd; ) {
5512 // We know that this user uses some value of From. If it is the right
5513 // value, update it.
5514 SDNode *User = Uses[UseIndex].User;
5516 // This node is about to morph, remove its old self from the CSE maps.
5517 RemoveNodeFromCSEMaps(User);
5519 // The Uses array is sorted, so all the uses for a given User
5520 // are next to each other in the list.
5521 // To help reduce the number of CSE recomputations, process all
5522 // the uses of this user that we can find this way.
5524 unsigned i = Uses[UseIndex].Index;
5525 SDUse &Use = *Uses[UseIndex].Use;
5529 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5531 // Now that we have modified User, add it back to the CSE maps. If it
5532 // already exists there, recursively merge the results together.
5533 AddModifiedNodeToCSEMaps(User, UpdateListener);
5537 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5538 /// based on their topological order. It returns the maximum id and a vector
5539 /// of the SDNodes* in assigned order by reference.
5540 unsigned SelectionDAG::AssignTopologicalOrder() {
5542 unsigned DAGSize = 0;
5544 // SortedPos tracks the progress of the algorithm. Nodes before it are
5545 // sorted, nodes after it are unsorted. When the algorithm completes
5546 // it is at the end of the list.
5547 allnodes_iterator SortedPos = allnodes_begin();
5549 // Visit all the nodes. Move nodes with no operands to the front of
5550 // the list immediately. Annotate nodes that do have operands with their
5551 // operand count. Before we do this, the Node Id fields of the nodes
5552 // may contain arbitrary values. After, the Node Id fields for nodes
5553 // before SortedPos will contain the topological sort index, and the
5554 // Node Id fields for nodes At SortedPos and after will contain the
5555 // count of outstanding operands.
5556 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5559 unsigned Degree = N->getNumOperands();
5561 // A node with no uses, add it to the result array immediately.
5562 N->setNodeId(DAGSize++);
5563 allnodes_iterator Q = N;
5565 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5566 assert(SortedPos != AllNodes.end() && "Overran node list");
5569 // Temporarily use the Node Id as scratch space for the degree count.
5570 N->setNodeId(Degree);
5574 // Visit all the nodes. As we iterate, moves nodes into sorted order,
5575 // such that by the time the end is reached all nodes will be sorted.
5576 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5579 // N is in sorted position, so all its uses have one less operand
5580 // that needs to be sorted.
5581 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5584 unsigned Degree = P->getNodeId();
5585 assert(Degree != 0 && "Invalid node degree");
5588 // All of P's operands are sorted, so P may sorted now.
5589 P->setNodeId(DAGSize++);
5591 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5592 assert(SortedPos != AllNodes.end() && "Overran node list");
5595 // Update P's outstanding operand count.
5596 P->setNodeId(Degree);
5599 if (I == SortedPos) {
5602 dbgs() << "Overran sorted position:\n";
5605 llvm_unreachable(0);
5609 assert(SortedPos == AllNodes.end() &&
5610 "Topological sort incomplete!");
5611 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
5612 "First node in topological sort is not the entry token!");
5613 assert(AllNodes.front().getNodeId() == 0 &&
5614 "First node in topological sort has non-zero id!");
5615 assert(AllNodes.front().getNumOperands() == 0 &&
5616 "First node in topological sort has operands!");
5617 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
5618 "Last node in topologic sort has unexpected id!");
5619 assert(AllNodes.back().use_empty() &&
5620 "Last node in topologic sort has users!");
5621 assert(DAGSize == allnodes_size() && "Node count mismatch!");
5625 /// AssignOrdering - Assign an order to the SDNode.
5626 void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) {
5627 assert(SD && "Trying to assign an order to a null node!");
5628 Ordering->add(SD, Order);
5631 /// GetOrdering - Get the order for the SDNode.
5632 unsigned SelectionDAG::GetOrdering(const SDNode *SD) const {
5633 assert(SD && "Trying to get the order of a null node!");
5634 return Ordering->getOrder(SD);
5637 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5638 /// value is produced by SD.
5639 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
5640 DbgInfo->add(DB, SD, isParameter);
5642 SD->setHasDebugValue(true);
5645 /// TransferDbgValues - Transfer SDDbgValues.
5646 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
5647 if (From == To || !From.getNode()->getHasDebugValue())
5649 SDNode *FromNode = From.getNode();
5650 SDNode *ToNode = To.getNode();
5651 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
5652 SmallVector<SDDbgValue *, 2> ClonedDVs;
5653 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
5655 SDDbgValue *Dbg = *I;
5656 if (Dbg->getKind() == SDDbgValue::SDNODE) {
5657 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
5658 Dbg->getOffset(), Dbg->getDebugLoc(),
5660 ClonedDVs.push_back(Clone);
5663 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(),
5664 E = ClonedDVs.end(); I != E; ++I)
5665 AddDbgValue(*I, ToNode, false);
5668 //===----------------------------------------------------------------------===//
5670 //===----------------------------------------------------------------------===//
5672 HandleSDNode::~HandleSDNode() {
5676 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL,
5677 const GlobalValue *GA,
5678 EVT VT, int64_t o, unsigned char TF)
5679 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
5683 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt,
5684 MachineMemOperand *mmo)
5685 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) {
5686 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5687 MMO->isNonTemporal(), MMO->isInvariant());
5688 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5689 assert(isNonTemporal() == MMO->isNonTemporal() &&
5690 "Non-temporal encoding error!");
5691 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5694 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs,
5695 const SDValue *Ops, unsigned NumOps, EVT memvt,
5696 MachineMemOperand *mmo)
5697 : SDNode(Opc, dl, VTs, Ops, NumOps),
5698 MemoryVT(memvt), MMO(mmo) {
5699 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
5700 MMO->isNonTemporal(), MMO->isInvariant());
5701 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
5702 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
5705 /// Profile - Gather unique data for the node.
5707 void SDNode::Profile(FoldingSetNodeID &ID) const {
5708 AddNodeIDNode(ID, this);
5713 std::vector<EVT> VTs;
5716 VTs.reserve(MVT::LAST_VALUETYPE);
5717 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
5718 VTs.push_back(MVT((MVT::SimpleValueType)i));
5723 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
5724 static ManagedStatic<EVTArray> SimpleVTArray;
5725 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
5727 /// getValueTypeList - Return a pointer to the specified value type.
5729 const EVT *SDNode::getValueTypeList(EVT VT) {
5730 if (VT.isExtended()) {
5731 sys::SmartScopedLock<true> Lock(*VTMutex);
5732 return &(*EVTs->insert(VT).first);
5734 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
5735 "Value type out of range!");
5736 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
5740 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5741 /// indicated value. This method ignores uses of other values defined by this
5743 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
5744 assert(Value < getNumValues() && "Bad value!");
5746 // TODO: Only iterate over uses of a given value of the node
5747 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
5748 if (UI.getUse().getResNo() == Value) {
5755 // Found exactly the right number of uses?
5760 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5761 /// value. This method ignores uses of other values defined by this operation.
5762 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
5763 assert(Value < getNumValues() && "Bad value!");
5765 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
5766 if (UI.getUse().getResNo() == Value)
5773 /// isOnlyUserOf - Return true if this node is the only use of N.
5775 bool SDNode::isOnlyUserOf(SDNode *N) const {
5777 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
5788 /// isOperand - Return true if this node is an operand of N.
5790 bool SDValue::isOperandOf(SDNode *N) const {
5791 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
5792 if (*this == N->getOperand(i))
5797 bool SDNode::isOperandOf(SDNode *N) const {
5798 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
5799 if (this == N->OperandList[i].getNode())
5804 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5805 /// be a chain) reaches the specified operand without crossing any
5806 /// side-effecting instructions on any chain path. In practice, this looks
5807 /// through token factors and non-volatile loads. In order to remain efficient,
5808 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5809 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
5810 unsigned Depth) const {
5811 if (*this == Dest) return true;
5813 // Don't search too deeply, we just want to be able to see through
5814 // TokenFactor's etc.
5815 if (Depth == 0) return false;
5817 // If this is a token factor, all inputs to the TF happen in parallel. If any
5818 // of the operands of the TF does not reach dest, then we cannot do the xform.
5819 if (getOpcode() == ISD::TokenFactor) {
5820 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5821 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
5826 // Loads don't have side effects, look through them.
5827 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
5828 if (!Ld->isVolatile())
5829 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
5834 /// hasPredecessor - Return true if N is a predecessor of this node.
5835 /// N is either an operand of this node, or can be reached by recursively
5836 /// traversing up the operands.
5837 /// NOTE: This is an expensive method. Use it carefully.
5838 bool SDNode::hasPredecessor(const SDNode *N) const {
5839 SmallPtrSet<const SDNode *, 32> Visited;
5840 SmallVector<const SDNode *, 16> Worklist;
5841 return hasPredecessorHelper(N, Visited, Worklist);
5844 bool SDNode::hasPredecessorHelper(const SDNode *N,
5845 SmallPtrSet<const SDNode *, 32> &Visited,
5846 SmallVector<const SDNode *, 16> &Worklist) const {
5847 if (Visited.empty()) {
5848 Worklist.push_back(this);
5850 // Take a look in the visited set. If we've already encountered this node
5851 // we needn't search further.
5852 if (Visited.count(N))
5856 // Haven't visited N yet. Continue the search.
5857 while (!Worklist.empty()) {
5858 const SDNode *M = Worklist.pop_back_val();
5859 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
5860 SDNode *Op = M->getOperand(i).getNode();
5861 if (Visited.insert(Op))
5862 Worklist.push_back(Op);
5871 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
5872 assert(Num < NumOperands && "Invalid child # of SDNode!");
5873 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
5876 std::string SDNode::getOperationName(const SelectionDAG *G) const {
5877 switch (getOpcode()) {
5879 if (getOpcode() < ISD::BUILTIN_OP_END)
5880 return "<<Unknown DAG Node>>";
5881 if (isMachineOpcode()) {
5883 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
5884 if (getMachineOpcode() < TII->getNumOpcodes())
5885 return TII->get(getMachineOpcode()).getName();
5886 return "<<Unknown Machine Node #" + utostr(getOpcode()) + ">>";
5889 const TargetLowering &TLI = G->getTargetLoweringInfo();
5890 const char *Name = TLI.getTargetNodeName(getOpcode());
5891 if (Name) return Name;
5892 return "<<Unknown Target Node #" + utostr(getOpcode()) + ">>";
5894 return "<<Unknown Node #" + utostr(getOpcode()) + ">>";
5897 case ISD::DELETED_NODE:
5898 return "<<Deleted Node!>>";
5900 case ISD::PREFETCH: return "Prefetch";
5901 case ISD::MEMBARRIER: return "MemBarrier";
5902 case ISD::ATOMIC_FENCE: return "AtomicFence";
5903 case ISD::ATOMIC_CMP_SWAP: return "AtomicCmpSwap";
5904 case ISD::ATOMIC_SWAP: return "AtomicSwap";
5905 case ISD::ATOMIC_LOAD_ADD: return "AtomicLoadAdd";
5906 case ISD::ATOMIC_LOAD_SUB: return "AtomicLoadSub";
5907 case ISD::ATOMIC_LOAD_AND: return "AtomicLoadAnd";
5908 case ISD::ATOMIC_LOAD_OR: return "AtomicLoadOr";
5909 case ISD::ATOMIC_LOAD_XOR: return "AtomicLoadXor";
5910 case ISD::ATOMIC_LOAD_NAND: return "AtomicLoadNand";
5911 case ISD::ATOMIC_LOAD_MIN: return "AtomicLoadMin";
5912 case ISD::ATOMIC_LOAD_MAX: return "AtomicLoadMax";
5913 case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin";
5914 case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax";
5915 case ISD::ATOMIC_LOAD: return "AtomicLoad";
5916 case ISD::ATOMIC_STORE: return "AtomicStore";
5917 case ISD::PCMARKER: return "PCMarker";
5918 case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
5919 case ISD::SRCVALUE: return "SrcValue";
5920 case ISD::MDNODE_SDNODE: return "MDNode";
5921 case ISD::EntryToken: return "EntryToken";
5922 case ISD::TokenFactor: return "TokenFactor";
5923 case ISD::AssertSext: return "AssertSext";
5924 case ISD::AssertZext: return "AssertZext";
5926 case ISD::BasicBlock: return "BasicBlock";
5927 case ISD::VALUETYPE: return "ValueType";
5928 case ISD::Register: return "Register";
5930 case ISD::Constant: return "Constant";
5931 case ISD::ConstantFP: return "ConstantFP";
5932 case ISD::GlobalAddress: return "GlobalAddress";
5933 case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
5934 case ISD::FrameIndex: return "FrameIndex";
5935 case ISD::JumpTable: return "JumpTable";
5936 case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
5937 case ISD::RETURNADDR: return "RETURNADDR";
5938 case ISD::FRAMEADDR: return "FRAMEADDR";
5939 case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET";
5940 case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR";
5941 case ISD::LSDAADDR: return "LSDAADDR";
5942 case ISD::EHSELECTION: return "EHSELECTION";
5943 case ISD::EH_RETURN: return "EH_RETURN";
5944 case ISD::EH_SJLJ_SETJMP: return "EH_SJLJ_SETJMP";
5945 case ISD::EH_SJLJ_LONGJMP: return "EH_SJLJ_LONGJMP";
5946 case ISD::ConstantPool: return "ConstantPool";
5947 case ISD::ExternalSymbol: return "ExternalSymbol";
5948 case ISD::BlockAddress: return "BlockAddress";
5949 case ISD::INTRINSIC_WO_CHAIN:
5950 case ISD::INTRINSIC_VOID:
5951 case ISD::INTRINSIC_W_CHAIN: {
5952 unsigned OpNo = getOpcode() == ISD::INTRINSIC_WO_CHAIN ? 0 : 1;
5953 unsigned IID = cast<ConstantSDNode>(getOperand(OpNo))->getZExtValue();
5954 if (IID < Intrinsic::num_intrinsics)
5955 return Intrinsic::getName((Intrinsic::ID)IID);
5956 else if (const TargetIntrinsicInfo *TII = G->getTarget().getIntrinsicInfo())
5957 return TII->getName(IID);
5958 llvm_unreachable("Invalid intrinsic ID");
5961 case ISD::BUILD_VECTOR: return "BUILD_VECTOR";
5962 case ISD::TargetConstant: return "TargetConstant";
5963 case ISD::TargetConstantFP:return "TargetConstantFP";
5964 case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
5965 case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
5966 case ISD::TargetFrameIndex: return "TargetFrameIndex";
5967 case ISD::TargetJumpTable: return "TargetJumpTable";
5968 case ISD::TargetConstantPool: return "TargetConstantPool";
5969 case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
5970 case ISD::TargetBlockAddress: return "TargetBlockAddress";
5972 case ISD::CopyToReg: return "CopyToReg";
5973 case ISD::CopyFromReg: return "CopyFromReg";
5974 case ISD::UNDEF: return "undef";
5975 case ISD::MERGE_VALUES: return "merge_values";
5976 case ISD::INLINEASM: return "inlineasm";
5977 case ISD::EH_LABEL: return "eh_label";
5978 case ISD::HANDLENODE: return "handlenode";
5981 case ISD::FABS: return "fabs";
5982 case ISD::FNEG: return "fneg";
5983 case ISD::FSQRT: return "fsqrt";
5984 case ISD::FSIN: return "fsin";
5985 case ISD::FCOS: return "fcos";
5986 case ISD::FTRUNC: return "ftrunc";
5987 case ISD::FFLOOR: return "ffloor";
5988 case ISD::FCEIL: return "fceil";
5989 case ISD::FRINT: return "frint";
5990 case ISD::FNEARBYINT: return "fnearbyint";
5991 case ISD::FEXP: return "fexp";
5992 case ISD::FEXP2: return "fexp2";
5993 case ISD::FLOG: return "flog";
5994 case ISD::FLOG2: return "flog2";
5995 case ISD::FLOG10: return "flog10";
5998 case ISD::ADD: return "add";
5999 case ISD::SUB: return "sub";
6000 case ISD::MUL: return "mul";
6001 case ISD::MULHU: return "mulhu";
6002 case ISD::MULHS: return "mulhs";
6003 case ISD::SDIV: return "sdiv";
6004 case ISD::UDIV: return "udiv";
6005 case ISD::SREM: return "srem";
6006 case ISD::UREM: return "urem";
6007 case ISD::SMUL_LOHI: return "smul_lohi";
6008 case ISD::UMUL_LOHI: return "umul_lohi";
6009 case ISD::SDIVREM: return "sdivrem";
6010 case ISD::UDIVREM: return "udivrem";
6011 case ISD::AND: return "and";
6012 case ISD::OR: return "or";
6013 case ISD::XOR: return "xor";
6014 case ISD::SHL: return "shl";
6015 case ISD::SRA: return "sra";
6016 case ISD::SRL: return "srl";
6017 case ISD::ROTL: return "rotl";
6018 case ISD::ROTR: return "rotr";
6019 case ISD::FADD: return "fadd";
6020 case ISD::FSUB: return "fsub";
6021 case ISD::FMUL: return "fmul";
6022 case ISD::FDIV: return "fdiv";
6023 case ISD::FMA: return "fma";
6024 case ISD::FREM: return "frem";
6025 case ISD::FCOPYSIGN: return "fcopysign";
6026 case ISD::FGETSIGN: return "fgetsign";
6027 case ISD::FPOW: return "fpow";
6029 case ISD::FPOWI: return "fpowi";
6030 case ISD::SETCC: return "setcc";
6031 case ISD::SELECT: return "select";
6032 case ISD::VSELECT: return "vselect";
6033 case ISD::SELECT_CC: return "select_cc";
6034 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt";
6035 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt";
6036 case ISD::CONCAT_VECTORS: return "concat_vectors";
6037 case ISD::INSERT_SUBVECTOR: return "insert_subvector";
6038 case ISD::EXTRACT_SUBVECTOR: return "extract_subvector";
6039 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector";
6040 case ISD::VECTOR_SHUFFLE: return "vector_shuffle";
6041 case ISD::CARRY_FALSE: return "carry_false";
6042 case ISD::ADDC: return "addc";
6043 case ISD::ADDE: return "adde";
6044 case ISD::SADDO: return "saddo";
6045 case ISD::UADDO: return "uaddo";
6046 case ISD::SSUBO: return "ssubo";
6047 case ISD::USUBO: return "usubo";
6048 case ISD::SMULO: return "smulo";
6049 case ISD::UMULO: return "umulo";
6050 case ISD::SUBC: return "subc";
6051 case ISD::SUBE: return "sube";
6052 case ISD::SHL_PARTS: return "shl_parts";
6053 case ISD::SRA_PARTS: return "sra_parts";
6054 case ISD::SRL_PARTS: return "srl_parts";
6056 // Conversion operators.
6057 case ISD::SIGN_EXTEND: return "sign_extend";
6058 case ISD::ZERO_EXTEND: return "zero_extend";
6059 case ISD::ANY_EXTEND: return "any_extend";
6060 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
6061 case ISD::TRUNCATE: return "truncate";
6062 case ISD::FP_ROUND: return "fp_round";
6063 case ISD::FLT_ROUNDS_: return "flt_rounds";
6064 case ISD::FP_ROUND_INREG: return "fp_round_inreg";
6065 case ISD::FP_EXTEND: return "fp_extend";
6067 case ISD::SINT_TO_FP: return "sint_to_fp";
6068 case ISD::UINT_TO_FP: return "uint_to_fp";
6069 case ISD::FP_TO_SINT: return "fp_to_sint";
6070 case ISD::FP_TO_UINT: return "fp_to_uint";
6071 case ISD::BITCAST: return "bitcast";
6072 case ISD::FP16_TO_FP32: return "fp16_to_fp32";
6073 case ISD::FP32_TO_FP16: return "fp32_to_fp16";
6075 case ISD::CONVERT_RNDSAT: {
6076 switch (cast<CvtRndSatSDNode>(this)->getCvtCode()) {
6077 default: llvm_unreachable("Unknown cvt code!");
6078 case ISD::CVT_FF: return "cvt_ff";
6079 case ISD::CVT_FS: return "cvt_fs";
6080 case ISD::CVT_FU: return "cvt_fu";
6081 case ISD::CVT_SF: return "cvt_sf";
6082 case ISD::CVT_UF: return "cvt_uf";
6083 case ISD::CVT_SS: return "cvt_ss";
6084 case ISD::CVT_SU: return "cvt_su";
6085 case ISD::CVT_US: return "cvt_us";
6086 case ISD::CVT_UU: return "cvt_uu";
6090 // Control flow instructions
6091 case ISD::BR: return "br";
6092 case ISD::BRIND: return "brind";
6093 case ISD::BR_JT: return "br_jt";
6094 case ISD::BRCOND: return "brcond";
6095 case ISD::BR_CC: return "br_cc";
6096 case ISD::CALLSEQ_START: return "callseq_start";
6097 case ISD::CALLSEQ_END: return "callseq_end";
6100 case ISD::LOAD: return "load";
6101 case ISD::STORE: return "store";
6102 case ISD::VAARG: return "vaarg";
6103 case ISD::VACOPY: return "vacopy";
6104 case ISD::VAEND: return "vaend";
6105 case ISD::VASTART: return "vastart";
6106 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
6107 case ISD::EXTRACT_ELEMENT: return "extract_element";
6108 case ISD::BUILD_PAIR: return "build_pair";
6109 case ISD::STACKSAVE: return "stacksave";
6110 case ISD::STACKRESTORE: return "stackrestore";
6111 case ISD::TRAP: return "trap";
6114 case ISD::BSWAP: return "bswap";
6115 case ISD::CTPOP: return "ctpop";
6116 case ISD::CTTZ: return "cttz";
6117 case ISD::CTLZ: return "ctlz";
6120 case ISD::INIT_TRAMPOLINE: return "init_trampoline";
6121 case ISD::ADJUST_TRAMPOLINE: return "adjust_trampoline";
6124 switch (cast<CondCodeSDNode>(this)->get()) {
6125 default: llvm_unreachable("Unknown setcc condition!");
6126 case ISD::SETOEQ: return "setoeq";
6127 case ISD::SETOGT: return "setogt";
6128 case ISD::SETOGE: return "setoge";
6129 case ISD::SETOLT: return "setolt";
6130 case ISD::SETOLE: return "setole";
6131 case ISD::SETONE: return "setone";
6133 case ISD::SETO: return "seto";
6134 case ISD::SETUO: return "setuo";
6135 case ISD::SETUEQ: return "setue";
6136 case ISD::SETUGT: return "setugt";
6137 case ISD::SETUGE: return "setuge";
6138 case ISD::SETULT: return "setult";
6139 case ISD::SETULE: return "setule";
6140 case ISD::SETUNE: return "setune";
6142 case ISD::SETEQ: return "seteq";
6143 case ISD::SETGT: return "setgt";
6144 case ISD::SETGE: return "setge";
6145 case ISD::SETLT: return "setlt";
6146 case ISD::SETLE: return "setle";
6147 case ISD::SETNE: return "setne";
6152 const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) {
6161 return "<post-inc>";
6163 return "<post-dec>";
6167 std::string ISD::ArgFlagsTy::getArgFlagsString() {
6168 std::string S = "< ";
6182 if (getByValAlign())
6183 S += "byval-align:" + utostr(getByValAlign()) + " ";
6185 S += "orig-align:" + utostr(getOrigAlign()) + " ";
6187 S += "byval-size:" + utostr(getByValSize()) + " ";
6191 void SDNode::dump() const { dump(0); }
6192 void SDNode::dump(const SelectionDAG *G) const {
6197 void SDNode::print_types(raw_ostream &OS, const SelectionDAG *G) const {
6198 OS << (void*)this << ": ";
6200 for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
6202 if (getValueType(i) == MVT::Other)
6205 OS << getValueType(i).getEVTString();
6207 OS << " = " << getOperationName(G);
6210 void SDNode::print_details(raw_ostream &OS, const SelectionDAG *G) const {
6211 if (const MachineSDNode *MN = dyn_cast<MachineSDNode>(this)) {
6212 if (!MN->memoperands_empty()) {
6215 for (MachineSDNode::mmo_iterator i = MN->memoperands_begin(),
6216 e = MN->memoperands_end(); i != e; ++i) {
6218 if (llvm::next(i) != e)
6223 } else if (const ShuffleVectorSDNode *SVN =
6224 dyn_cast<ShuffleVectorSDNode>(this)) {
6226 for (unsigned i = 0, e = ValueList[0].getVectorNumElements(); i != e; ++i) {
6227 int Idx = SVN->getMaskElt(i);
6235 } else if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
6236 OS << '<' << CSDN->getAPIntValue() << '>';
6237 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
6238 if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
6239 OS << '<' << CSDN->getValueAPF().convertToFloat() << '>';
6240 else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble)
6241 OS << '<' << CSDN->getValueAPF().convertToDouble() << '>';
6244 CSDN->getValueAPF().bitcastToAPInt().dump();
6247 } else if (const GlobalAddressSDNode *GADN =
6248 dyn_cast<GlobalAddressSDNode>(this)) {
6249 int64_t offset = GADN->getOffset();
6251 WriteAsOperand(OS, GADN->getGlobal());
6254 OS << " + " << offset;
6256 OS << " " << offset;
6257 if (unsigned int TF = GADN->getTargetFlags())
6258 OS << " [TF=" << TF << ']';
6259 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
6260 OS << "<" << FIDN->getIndex() << ">";
6261 } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
6262 OS << "<" << JTDN->getIndex() << ">";
6263 if (unsigned int TF = JTDN->getTargetFlags())
6264 OS << " [TF=" << TF << ']';
6265 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
6266 int offset = CP->getOffset();
6267 if (CP->isMachineConstantPoolEntry())
6268 OS << "<" << *CP->getMachineCPVal() << ">";
6270 OS << "<" << *CP->getConstVal() << ">";
6272 OS << " + " << offset;
6274 OS << " " << offset;
6275 if (unsigned int TF = CP->getTargetFlags())
6276 OS << " [TF=" << TF << ']';
6277 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
6279 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
6281 OS << LBB->getName() << " ";
6282 OS << (const void*)BBDN->getBasicBlock() << ">";
6283 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
6284 OS << ' ' << PrintReg(R->getReg(), G ? G->getTarget().getRegisterInfo() :0);
6285 } else if (const ExternalSymbolSDNode *ES =
6286 dyn_cast<ExternalSymbolSDNode>(this)) {
6287 OS << "'" << ES->getSymbol() << "'";
6288 if (unsigned int TF = ES->getTargetFlags())
6289 OS << " [TF=" << TF << ']';
6290 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
6292 OS << "<" << M->getValue() << ">";
6295 } else if (const MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(this)) {
6297 OS << "<" << MD->getMD() << ">";
6300 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
6301 OS << ":" << N->getVT().getEVTString();
6303 else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
6304 OS << "<" << *LD->getMemOperand();
6307 switch (LD->getExtensionType()) {
6308 default: doExt = false; break;
6309 case ISD::EXTLOAD: OS << ", anyext"; break;
6310 case ISD::SEXTLOAD: OS << ", sext"; break;
6311 case ISD::ZEXTLOAD: OS << ", zext"; break;
6314 OS << " from " << LD->getMemoryVT().getEVTString();
6316 const char *AM = getIndexedModeName(LD->getAddressingMode());
6321 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
6322 OS << "<" << *ST->getMemOperand();
6324 if (ST->isTruncatingStore())
6325 OS << ", trunc to " << ST->getMemoryVT().getEVTString();
6327 const char *AM = getIndexedModeName(ST->getAddressingMode());
6332 } else if (const MemSDNode* M = dyn_cast<MemSDNode>(this)) {
6333 OS << "<" << *M->getMemOperand() << ">";
6334 } else if (const BlockAddressSDNode *BA =
6335 dyn_cast<BlockAddressSDNode>(this)) {
6337 WriteAsOperand(OS, BA->getBlockAddress()->getFunction(), false);
6339 WriteAsOperand(OS, BA->getBlockAddress()->getBasicBlock(), false);
6341 if (unsigned int TF = BA->getTargetFlags())
6342 OS << " [TF=" << TF << ']';
6346 if (unsigned Order = G->GetOrdering(this))
6347 OS << " [ORD=" << Order << ']';
6349 if (getNodeId() != -1)
6350 OS << " [ID=" << getNodeId() << ']';
6352 DebugLoc dl = getDebugLoc();
6353 if (G && !dl.isUnknown()) {
6355 Scope(dl.getScope(G->getMachineFunction().getFunction()->getContext()));
6357 // Omit the directory, since it's usually long and uninteresting.
6359 OS << Scope.getFilename();
6362 OS << ':' << dl.getLine();
6363 if (dl.getCol() != 0)
6364 OS << ':' << dl.getCol();
6368 void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const {
6370 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6371 if (i) OS << ", "; else OS << " ";
6372 OS << (void*)getOperand(i).getNode();
6373 if (unsigned RN = getOperand(i).getResNo())
6376 print_details(OS, G);
6379 static void printrWithDepthHelper(raw_ostream &OS, const SDNode *N,
6380 const SelectionDAG *G, unsigned depth,
6392 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
6393 // Don't follow chain operands.
6394 if (N->getOperand(i).getValueType() == MVT::Other)
6397 printrWithDepthHelper(OS, N->getOperand(i).getNode(), G, depth-1, indent+2);
6401 void SDNode::printrWithDepth(raw_ostream &OS, const SelectionDAG *G,
6402 unsigned depth) const {
6403 printrWithDepthHelper(OS, this, G, depth, 0);
6406 void SDNode::printrFull(raw_ostream &OS, const SelectionDAG *G) const {
6407 // Don't print impossibly deep things.
6408 printrWithDepth(OS, G, 10);
6411 void SDNode::dumprWithDepth(const SelectionDAG *G, unsigned depth) const {
6412 printrWithDepth(dbgs(), G, depth);
6415 void SDNode::dumprFull(const SelectionDAG *G) const {
6416 // Don't print impossibly deep things.
6417 dumprWithDepth(G, 10);
6420 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
6421 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6422 if (N->getOperand(i).getNode()->hasOneUse())
6423 DumpNodes(N->getOperand(i).getNode(), indent+2, G);
6425 dbgs() << "\n" << std::string(indent+2, ' ')
6426 << (void*)N->getOperand(i).getNode() << ": <multiple use>";
6430 dbgs().indent(indent);
6434 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6435 assert(N->getNumValues() == 1 &&
6436 "Can't unroll a vector with multiple results!");
6438 EVT VT = N->getValueType(0);
6439 unsigned NE = VT.getVectorNumElements();
6440 EVT EltVT = VT.getVectorElementType();
6441 DebugLoc dl = N->getDebugLoc();
6443 SmallVector<SDValue, 8> Scalars;
6444 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6446 // If ResNE is 0, fully unroll the vector op.
6449 else if (NE > ResNE)
6453 for (i= 0; i != NE; ++i) {
6454 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6455 SDValue Operand = N->getOperand(j);
6456 EVT OperandVT = Operand.getValueType();
6457 if (OperandVT.isVector()) {
6458 // A vector operand; extract a single element.
6459 EVT OperandEltVT = OperandVT.getVectorElementType();
6460 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6463 getConstant(i, TLI.getPointerTy()));
6465 // A scalar operand; just use it as is.
6466 Operands[j] = Operand;
6470 switch (N->getOpcode()) {
6472 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6473 &Operands[0], Operands.size()));
6476 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT,
6477 &Operands[0], Operands.size()));
6484 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6485 getShiftAmountOperand(Operands[0].getValueType(),
6488 case ISD::SIGN_EXTEND_INREG:
6489 case ISD::FP_ROUND_INREG: {
6490 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6491 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6493 getValueType(ExtVT)));
6498 for (; i < ResNE; ++i)
6499 Scalars.push_back(getUNDEF(EltVT));
6501 return getNode(ISD::BUILD_VECTOR, dl,
6502 EVT::getVectorVT(*getContext(), EltVT, ResNE),
6503 &Scalars[0], Scalars.size());
6507 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6508 /// location that is 'Dist' units away from the location that the 'Base' load
6509 /// is loading from.
6510 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6511 unsigned Bytes, int Dist) const {
6512 if (LD->getChain() != Base->getChain())
6514 EVT VT = LD->getValueType(0);
6515 if (VT.getSizeInBits() / 8 != Bytes)
6518 SDValue Loc = LD->getOperand(1);
6519 SDValue BaseLoc = Base->getOperand(1);
6520 if (Loc.getOpcode() == ISD::FrameIndex) {
6521 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6523 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6524 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6525 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6526 int FS = MFI->getObjectSize(FI);
6527 int BFS = MFI->getObjectSize(BFI);
6528 if (FS != BFS || FS != (int)Bytes) return false;
6529 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6533 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6534 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6537 const GlobalValue *GV1 = NULL;
6538 const GlobalValue *GV2 = NULL;
6539 int64_t Offset1 = 0;
6540 int64_t Offset2 = 0;
6541 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6542 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6543 if (isGA1 && isGA2 && GV1 == GV2)
6544 return Offset1 == (Offset2 + Dist*Bytes);
6549 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6550 /// it cannot be inferred.
6551 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6552 // If this is a GlobalAddress + cst, return the alignment.
6553 const GlobalValue *GV;
6554 int64_t GVOffset = 0;
6555 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6556 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits();
6557 APInt AllOnes = APInt::getAllOnesValue(PtrWidth);
6558 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6559 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), AllOnes,
6560 KnownZero, KnownOne, TLI.getTargetData());
6561 unsigned AlignBits = KnownZero.countTrailingOnes();
6562 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6564 return MinAlign(Align, GVOffset);
6567 // If this is a direct reference to a stack slot, use information about the
6568 // stack slot's alignment.
6569 int FrameIdx = 1 << 31;
6570 int64_t FrameOffset = 0;
6571 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6572 FrameIdx = FI->getIndex();
6573 } else if (isBaseWithConstantOffset(Ptr) &&
6574 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6576 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6577 FrameOffset = Ptr.getConstantOperandVal(1);
6580 if (FrameIdx != (1 << 31)) {
6581 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6582 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6590 void SelectionDAG::dump() const {
6591 dbgs() << "SelectionDAG has " << AllNodes.size() << " nodes:";
6593 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
6595 const SDNode *N = I;
6596 if (!N->hasOneUse() && N != getRoot().getNode())
6597 DumpNodes(N, 2, this);
6600 if (getRoot().getNode()) DumpNodes(getRoot().getNode(), 2, this);
6605 void SDNode::printr(raw_ostream &OS, const SelectionDAG *G) const {
6607 print_details(OS, G);
6610 typedef SmallPtrSet<const SDNode *, 128> VisitedSDNodeSet;
6611 static void DumpNodesr(raw_ostream &OS, const SDNode *N, unsigned indent,
6612 const SelectionDAG *G, VisitedSDNodeSet &once) {
6613 if (!once.insert(N)) // If we've been here before, return now.
6616 // Dump the current SDNode, but don't end the line yet.
6620 // Having printed this SDNode, walk the children:
6621 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
6622 const SDNode *child = N->getOperand(i).getNode();
6627 if (child->getNumOperands() == 0) {
6628 // This child has no grandchildren; print it inline right here.
6629 child->printr(OS, G);
6631 } else { // Just the address. FIXME: also print the child's opcode.
6633 if (unsigned RN = N->getOperand(i).getResNo())
6640 // Dump children that have grandchildren on their own line(s).
6641 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
6642 const SDNode *child = N->getOperand(i).getNode();
6643 DumpNodesr(OS, child, indent+2, G, once);
6647 void SDNode::dumpr() const {
6648 VisitedSDNodeSet once;
6649 DumpNodesr(dbgs(), this, 0, 0, once);
6652 void SDNode::dumpr(const SelectionDAG *G) const {
6653 VisitedSDNodeSet once;
6654 DumpNodesr(dbgs(), this, 0, G, once);
6658 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6659 unsigned GlobalAddressSDNode::getAddressSpace() const {
6660 return getGlobal()->getType()->getAddressSpace();
6664 Type *ConstantPoolSDNode::getType() const {
6665 if (isMachineConstantPoolEntry())
6666 return Val.MachineCPVal->getType();
6667 return Val.ConstVal->getType();
6670 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6672 unsigned &SplatBitSize,
6674 unsigned MinSplatBits,
6676 EVT VT = getValueType(0);
6677 assert(VT.isVector() && "Expected a vector type");
6678 unsigned sz = VT.getSizeInBits();
6679 if (MinSplatBits > sz)
6682 SplatValue = APInt(sz, 0);
6683 SplatUndef = APInt(sz, 0);
6685 // Get the bits. Bits with undefined values (when the corresponding element
6686 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6687 // in SplatValue. If any of the values are not constant, give up and return
6689 unsigned int nOps = getNumOperands();
6690 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6691 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6693 for (unsigned j = 0; j < nOps; ++j) {
6694 unsigned i = isBigEndian ? nOps-1-j : j;
6695 SDValue OpVal = getOperand(i);
6696 unsigned BitPos = j * EltBitSize;
6698 if (OpVal.getOpcode() == ISD::UNDEF)
6699 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6700 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6701 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6702 zextOrTrunc(sz) << BitPos;
6703 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6704 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6709 // The build_vector is all constants or undefs. Find the smallest element
6710 // size that splats the vector.
6712 HasAnyUndefs = (SplatUndef != 0);
6715 unsigned HalfSize = sz / 2;
6716 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6717 APInt LowValue = SplatValue.trunc(HalfSize);
6718 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6719 APInt LowUndef = SplatUndef.trunc(HalfSize);
6721 // If the two halves do not match (ignoring undef bits), stop here.
6722 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6723 MinSplatBits > HalfSize)
6726 SplatValue = HighValue | LowValue;
6727 SplatUndef = HighUndef & LowUndef;
6736 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6737 // Find the first non-undef value in the shuffle mask.
6739 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6742 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6744 // Make sure all remaining elements are either undef or the same as the first
6746 for (int Idx = Mask[i]; i != e; ++i)
6747 if (Mask[i] >= 0 && Mask[i] != Idx)
6753 static void checkForCyclesHelper(const SDNode *N,
6754 SmallPtrSet<const SDNode*, 32> &Visited,
6755 SmallPtrSet<const SDNode*, 32> &Checked) {
6756 // If this node has already been checked, don't check it again.
6757 if (Checked.count(N))
6760 // If a node has already been visited on this depth-first walk, reject it as
6762 if (!Visited.insert(N)) {
6763 dbgs() << "Offending node:\n";
6765 errs() << "Detected cycle in SelectionDAG\n";
6769 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6770 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6777 void llvm::checkForCycles(const llvm::SDNode *N) {
6779 assert(N && "Checking nonexistant SDNode");
6780 SmallPtrSet<const SDNode*, 32> visited;
6781 SmallPtrSet<const SDNode*, 32> checked;
6782 checkForCyclesHelper(N, visited, checked);
6786 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6787 checkForCycles(DAG->getRoot().getNode());