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/CallingConv.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DebugInfo.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/GlobalAlias.h"
23 #include "llvm/GlobalVariable.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Assembly/Writer.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::f16
: return &APFloat::IEEEhalf
;
66 case MVT::f32
: return &APFloat::IEEEsingle
;
67 case MVT::f64
: return &APFloat::IEEEdouble
;
68 case MVT::f80
: return &APFloat::x87DoubleExtended
;
69 case MVT::f128
: return &APFloat::IEEEquad
;
70 case MVT::ppcf128
: return &APFloat::PPCDoubleDouble
;
74 // Default null implementations of the callbacks.
75 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode
*, SDNode
*) {}
76 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode
*) {}
78 //===----------------------------------------------------------------------===//
79 // ConstantFPSDNode Class
80 //===----------------------------------------------------------------------===//
82 /// isExactlyValue - We don't rely on operator== working on double values, as
83 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
84 /// As such, this method can be used to do an exact bit-for-bit comparison of
85 /// two floating point values.
86 bool ConstantFPSDNode::isExactlyValue(const APFloat
& V
) const {
87 return getValueAPF().bitwiseIsEqual(V
);
90 bool ConstantFPSDNode::isValueValidForType(EVT VT
,
92 assert(VT
.isFloatingPoint() && "Can only convert between FP types");
94 // PPC long double cannot be converted to any other type.
95 if (VT
== MVT::ppcf128
||
96 &Val
.getSemantics() == &APFloat::PPCDoubleDouble
)
99 // convert modifies in place, so make a copy.
100 APFloat Val2
= APFloat(Val
);
102 (void) Val2
.convert(*EVTToAPFloatSemantics(VT
), APFloat::rmNearestTiesToEven
,
107 //===----------------------------------------------------------------------===//
109 //===----------------------------------------------------------------------===//
111 /// isBuildVectorAllOnes - Return true if the specified node is a
112 /// BUILD_VECTOR where all of the elements are ~0 or undef.
113 bool ISD::isBuildVectorAllOnes(const SDNode
*N
) {
114 // Look through a bit convert.
115 if (N
->getOpcode() == ISD::BITCAST
)
116 N
= N
->getOperand(0).getNode();
118 if (N
->getOpcode() != ISD::BUILD_VECTOR
) return false;
120 unsigned i
= 0, e
= N
->getNumOperands();
122 // Skip over all of the undef values.
123 while (i
!= e
&& N
->getOperand(i
).getOpcode() == ISD::UNDEF
)
126 // Do not accept an all-undef vector.
127 if (i
== e
) return false;
129 // Do not accept build_vectors that aren't all constants or which have non-~0
130 // elements. We have to be a bit careful here, as the type of the constant
131 // may not be the same as the type of the vector elements due to type
132 // legalization (the elements are promoted to a legal type for the target and
133 // a vector of a type may be legal when the base element type is not).
134 // We only want to check enough bits to cover the vector elements, because
135 // we care if the resultant vector is all ones, not whether the individual
137 SDValue NotZero
= N
->getOperand(i
);
138 unsigned EltSize
= N
->getValueType(0).getVectorElementType().getSizeInBits();
139 if (isa
<ConstantSDNode
>(NotZero
)) {
140 if (cast
<ConstantSDNode
>(NotZero
)->getAPIntValue().countTrailingOnes() <
143 } else if (isa
<ConstantFPSDNode
>(NotZero
)) {
144 if (cast
<ConstantFPSDNode
>(NotZero
)->getValueAPF()
145 .bitcastToAPInt().countTrailingOnes() < EltSize
)
150 // Okay, we have at least one ~0 value, check to see if the rest match or are
151 // undefs. Even with the above element type twiddling, this should be OK, as
152 // the same type legalization should have applied to all the elements.
153 for (++i
; i
!= e
; ++i
)
154 if (N
->getOperand(i
) != NotZero
&&
155 N
->getOperand(i
).getOpcode() != ISD::UNDEF
)
161 /// isBuildVectorAllZeros - Return true if the specified node is a
162 /// BUILD_VECTOR where all of the elements are 0 or undef.
163 bool ISD::isBuildVectorAllZeros(const SDNode
*N
) {
164 // Look through a bit convert.
165 if (N
->getOpcode() == ISD::BITCAST
)
166 N
= N
->getOperand(0).getNode();
168 if (N
->getOpcode() != ISD::BUILD_VECTOR
) return false;
170 unsigned i
= 0, e
= N
->getNumOperands();
172 // Skip over all of the undef values.
173 while (i
!= e
&& N
->getOperand(i
).getOpcode() == ISD::UNDEF
)
176 // Do not accept an all-undef vector.
177 if (i
== e
) return false;
179 // Do not accept build_vectors that aren't all constants or which have non-0
181 SDValue Zero
= N
->getOperand(i
);
182 if (isa
<ConstantSDNode
>(Zero
)) {
183 if (!cast
<ConstantSDNode
>(Zero
)->isNullValue())
185 } else if (isa
<ConstantFPSDNode
>(Zero
)) {
186 if (!cast
<ConstantFPSDNode
>(Zero
)->getValueAPF().isPosZero())
191 // Okay, we have at least one 0 value, check to see if the rest match or are
193 for (++i
; i
!= e
; ++i
)
194 if (N
->getOperand(i
) != Zero
&&
195 N
->getOperand(i
).getOpcode() != ISD::UNDEF
)
200 /// isScalarToVector - Return true if the specified node is a
201 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
202 /// element is not an undef.
203 bool ISD::isScalarToVector(const SDNode
*N
) {
204 if (N
->getOpcode() == ISD::SCALAR_TO_VECTOR
)
207 if (N
->getOpcode() != ISD::BUILD_VECTOR
)
209 if (N
->getOperand(0).getOpcode() == ISD::UNDEF
)
211 unsigned NumElems
= N
->getNumOperands();
214 for (unsigned i
= 1; i
< NumElems
; ++i
) {
215 SDValue V
= N
->getOperand(i
);
216 if (V
.getOpcode() != ISD::UNDEF
)
222 /// allOperandsUndef - Return true if the node has at least one operand
223 /// and all operands of the specified node are ISD::UNDEF.
224 bool ISD::allOperandsUndef(const SDNode
*N
) {
225 // Return false if the node has no operands.
226 // This is "logically inconsistent" with the definition of "all" but
227 // is probably the desired behavior.
228 if (N
->getNumOperands() == 0)
231 for (unsigned i
= 0, e
= N
->getNumOperands(); i
!= e
; ++i
)
232 if (N
->getOperand(i
).getOpcode() != ISD::UNDEF
)
238 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
239 /// when given the operation for (X op Y).
240 ISD::CondCode
ISD::getSetCCSwappedOperands(ISD::CondCode Operation
) {
241 // To perform this operation, we just need to swap the L and G bits of the
243 unsigned OldL
= (Operation
>> 2) & 1;
244 unsigned OldG
= (Operation
>> 1) & 1;
245 return ISD::CondCode((Operation
& ~6) | // Keep the N, U, E bits
246 (OldL
<< 1) | // New G bit
247 (OldG
<< 2)); // New L bit.
250 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
251 /// 'op' is a valid SetCC operation.
252 ISD::CondCode
ISD::getSetCCInverse(ISD::CondCode Op
, bool isInteger
) {
253 unsigned Operation
= Op
;
255 Operation
^= 7; // Flip L, G, E bits, but not U.
257 Operation
^= 15; // Flip all of the condition bits.
259 if (Operation
> ISD::SETTRUE2
)
260 Operation
&= ~8; // Don't let N and U bits get set.
262 return ISD::CondCode(Operation
);
266 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
267 /// signed operation and 2 if the result is an unsigned comparison. Return zero
268 /// if the operation does not depend on the sign of the input (setne and seteq).
269 static int isSignedOp(ISD::CondCode Opcode
) {
271 default: llvm_unreachable("Illegal integer setcc operation!");
273 case ISD::SETNE
: return 0;
277 case ISD::SETGE
: return 1;
281 case ISD::SETUGE
: return 2;
285 /// getSetCCOrOperation - Return the result of a logical OR between different
286 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
287 /// returns SETCC_INVALID if it is not possible to represent the resultant
289 ISD::CondCode
ISD::getSetCCOrOperation(ISD::CondCode Op1
, ISD::CondCode Op2
,
291 if (isInteger
&& (isSignedOp(Op1
) | isSignedOp(Op2
)) == 3)
292 // Cannot fold a signed integer setcc with an unsigned integer setcc.
293 return ISD::SETCC_INVALID
;
295 unsigned Op
= Op1
| Op2
; // Combine all of the condition bits.
297 // If the N and U bits get set then the resultant comparison DOES suddenly
298 // care about orderedness, and is true when ordered.
299 if (Op
> ISD::SETTRUE2
)
300 Op
&= ~16; // Clear the U bit if the N bit is set.
302 // Canonicalize illegal integer setcc's.
303 if (isInteger
&& Op
== ISD::SETUNE
) // e.g. SETUGT | SETULT
306 return ISD::CondCode(Op
);
309 /// getSetCCAndOperation - Return the result of a logical AND between different
310 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
311 /// function returns zero if it is not possible to represent the resultant
313 ISD::CondCode
ISD::getSetCCAndOperation(ISD::CondCode Op1
, ISD::CondCode Op2
,
315 if (isInteger
&& (isSignedOp(Op1
) | isSignedOp(Op2
)) == 3)
316 // Cannot fold a signed setcc with an unsigned setcc.
317 return ISD::SETCC_INVALID
;
319 // Combine all of the condition bits.
320 ISD::CondCode Result
= ISD::CondCode(Op1
& Op2
);
322 // Canonicalize illegal integer setcc's.
326 case ISD::SETUO
: Result
= ISD::SETFALSE
; break; // SETUGT & SETULT
327 case ISD::SETOEQ
: // SETEQ & SETU[LG]E
328 case ISD::SETUEQ
: Result
= ISD::SETEQ
; break; // SETUGE & SETULE
329 case ISD::SETOLT
: Result
= ISD::SETULT
; break; // SETULT & SETNE
330 case ISD::SETOGT
: Result
= ISD::SETUGT
; break; // SETUGT & SETNE
337 //===----------------------------------------------------------------------===//
338 // SDNode Profile Support
339 //===----------------------------------------------------------------------===//
341 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
343 static void AddNodeIDOpcode(FoldingSetNodeID
&ID
, unsigned OpC
) {
347 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
348 /// solely with their pointer.
349 static void AddNodeIDValueTypes(FoldingSetNodeID
&ID
, SDVTList VTList
) {
350 ID
.AddPointer(VTList
.VTs
);
353 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
355 static void AddNodeIDOperands(FoldingSetNodeID
&ID
,
356 const SDValue
*Ops
, unsigned NumOps
) {
357 for (; NumOps
; --NumOps
, ++Ops
) {
358 ID
.AddPointer(Ops
->getNode());
359 ID
.AddInteger(Ops
->getResNo());
363 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
365 static void AddNodeIDOperands(FoldingSetNodeID
&ID
,
366 const SDUse
*Ops
, unsigned NumOps
) {
367 for (; NumOps
; --NumOps
, ++Ops
) {
368 ID
.AddPointer(Ops
->getNode());
369 ID
.AddInteger(Ops
->getResNo());
373 static void AddNodeIDNode(FoldingSetNodeID
&ID
,
374 unsigned short OpC
, SDVTList VTList
,
375 const SDValue
*OpList
, unsigned N
) {
376 AddNodeIDOpcode(ID
, OpC
);
377 AddNodeIDValueTypes(ID
, VTList
);
378 AddNodeIDOperands(ID
, OpList
, N
);
381 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
383 static void AddNodeIDCustom(FoldingSetNodeID
&ID
, const SDNode
*N
) {
384 switch (N
->getOpcode()) {
385 case ISD::TargetExternalSymbol
:
386 case ISD::ExternalSymbol
:
387 llvm_unreachable("Should only be used on nodes with operands");
388 default: break; // Normal nodes don't need extra info.
389 case ISD::TargetConstant
:
391 ID
.AddPointer(cast
<ConstantSDNode
>(N
)->getConstantIntValue());
393 case ISD::TargetConstantFP
:
394 case ISD::ConstantFP
: {
395 ID
.AddPointer(cast
<ConstantFPSDNode
>(N
)->getConstantFPValue());
398 case ISD::TargetGlobalAddress
:
399 case ISD::GlobalAddress
:
400 case ISD::TargetGlobalTLSAddress
:
401 case ISD::GlobalTLSAddress
: {
402 const GlobalAddressSDNode
*GA
= cast
<GlobalAddressSDNode
>(N
);
403 ID
.AddPointer(GA
->getGlobal());
404 ID
.AddInteger(GA
->getOffset());
405 ID
.AddInteger(GA
->getTargetFlags());
406 ID
.AddInteger(GA
->getAddressSpace());
409 case ISD::BasicBlock
:
410 ID
.AddPointer(cast
<BasicBlockSDNode
>(N
)->getBasicBlock());
413 ID
.AddInteger(cast
<RegisterSDNode
>(N
)->getReg());
415 case ISD::RegisterMask
:
416 ID
.AddPointer(cast
<RegisterMaskSDNode
>(N
)->getRegMask());
419 ID
.AddPointer(cast
<SrcValueSDNode
>(N
)->getValue());
421 case ISD::FrameIndex
:
422 case ISD::TargetFrameIndex
:
423 ID
.AddInteger(cast
<FrameIndexSDNode
>(N
)->getIndex());
426 case ISD::TargetJumpTable
:
427 ID
.AddInteger(cast
<JumpTableSDNode
>(N
)->getIndex());
428 ID
.AddInteger(cast
<JumpTableSDNode
>(N
)->getTargetFlags());
430 case ISD::ConstantPool
:
431 case ISD::TargetConstantPool
: {
432 const ConstantPoolSDNode
*CP
= cast
<ConstantPoolSDNode
>(N
);
433 ID
.AddInteger(CP
->getAlignment());
434 ID
.AddInteger(CP
->getOffset());
435 if (CP
->isMachineConstantPoolEntry())
436 CP
->getMachineCPVal()->addSelectionDAGCSEId(ID
);
438 ID
.AddPointer(CP
->getConstVal());
439 ID
.AddInteger(CP
->getTargetFlags());
442 case ISD::TargetIndex
: {
443 const TargetIndexSDNode
*TI
= cast
<TargetIndexSDNode
>(N
);
444 ID
.AddInteger(TI
->getIndex());
445 ID
.AddInteger(TI
->getOffset());
446 ID
.AddInteger(TI
->getTargetFlags());
450 const LoadSDNode
*LD
= cast
<LoadSDNode
>(N
);
451 ID
.AddInteger(LD
->getMemoryVT().getRawBits());
452 ID
.AddInteger(LD
->getRawSubclassData());
453 ID
.AddInteger(LD
->getPointerInfo().getAddrSpace());
457 const StoreSDNode
*ST
= cast
<StoreSDNode
>(N
);
458 ID
.AddInteger(ST
->getMemoryVT().getRawBits());
459 ID
.AddInteger(ST
->getRawSubclassData());
460 ID
.AddInteger(ST
->getPointerInfo().getAddrSpace());
463 case ISD::ATOMIC_CMP_SWAP
:
464 case ISD::ATOMIC_SWAP
:
465 case ISD::ATOMIC_LOAD_ADD
:
466 case ISD::ATOMIC_LOAD_SUB
:
467 case ISD::ATOMIC_LOAD_AND
:
468 case ISD::ATOMIC_LOAD_OR
:
469 case ISD::ATOMIC_LOAD_XOR
:
470 case ISD::ATOMIC_LOAD_NAND
:
471 case ISD::ATOMIC_LOAD_MIN
:
472 case ISD::ATOMIC_LOAD_MAX
:
473 case ISD::ATOMIC_LOAD_UMIN
:
474 case ISD::ATOMIC_LOAD_UMAX
:
475 case ISD::ATOMIC_LOAD
:
476 case ISD::ATOMIC_STORE
: {
477 const AtomicSDNode
*AT
= cast
<AtomicSDNode
>(N
);
478 ID
.AddInteger(AT
->getMemoryVT().getRawBits());
479 ID
.AddInteger(AT
->getRawSubclassData());
480 ID
.AddInteger(AT
->getPointerInfo().getAddrSpace());
483 case ISD::PREFETCH
: {
484 const MemSDNode
*PF
= cast
<MemSDNode
>(N
);
485 ID
.AddInteger(PF
->getPointerInfo().getAddrSpace());
488 case ISD::VECTOR_SHUFFLE
: {
489 const ShuffleVectorSDNode
*SVN
= cast
<ShuffleVectorSDNode
>(N
);
490 for (unsigned i
= 0, e
= N
->getValueType(0).getVectorNumElements();
492 ID
.AddInteger(SVN
->getMaskElt(i
));
495 case ISD::TargetBlockAddress
:
496 case ISD::BlockAddress
: {
497 const BlockAddressSDNode
*BA
= cast
<BlockAddressSDNode
>(N
);
498 ID
.AddPointer(BA
->getBlockAddress());
499 ID
.AddInteger(BA
->getOffset());
500 ID
.AddInteger(BA
->getTargetFlags());
503 } // end switch (N->getOpcode())
505 // Target specific memory nodes could also have address spaces to check.
506 if (N
->isTargetMemoryOpcode())
507 ID
.AddInteger(cast
<MemSDNode
>(N
)->getPointerInfo().getAddrSpace());
510 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
512 static void AddNodeIDNode(FoldingSetNodeID
&ID
, const SDNode
*N
) {
513 AddNodeIDOpcode(ID
, N
->getOpcode());
514 // Add the return value info.
515 AddNodeIDValueTypes(ID
, N
->getVTList());
516 // Add the operand info.
517 AddNodeIDOperands(ID
, N
->op_begin(), N
->getNumOperands());
519 // Handle SDNode leafs with special info.
520 AddNodeIDCustom(ID
, N
);
523 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
524 /// the CSE map that carries volatility, temporalness, indexing mode, and
525 /// extension/truncation information.
527 static inline unsigned
528 encodeMemSDNodeFlags(int ConvType
, ISD::MemIndexedMode AM
, bool isVolatile
,
529 bool isNonTemporal
, bool isInvariant
) {
530 assert((ConvType
& 3) == ConvType
&&
531 "ConvType may not require more than 2 bits!");
532 assert((AM
& 7) == AM
&&
533 "AM may not require more than 3 bits!");
537 (isNonTemporal
<< 6) |
541 //===----------------------------------------------------------------------===//
542 // SelectionDAG Class
543 //===----------------------------------------------------------------------===//
545 /// doNotCSE - Return true if CSE should not be performed for this node.
546 static bool doNotCSE(SDNode
*N
) {
547 if (N
->getValueType(0) == MVT::Glue
)
548 return true; // Never CSE anything that produces a flag.
550 switch (N
->getOpcode()) {
552 case ISD::HANDLENODE
:
554 return true; // Never CSE these nodes.
557 // Check that remaining values produced are not flags.
558 for (unsigned i
= 1, e
= N
->getNumValues(); i
!= e
; ++i
)
559 if (N
->getValueType(i
) == MVT::Glue
)
560 return true; // Never CSE anything that produces a flag.
565 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
567 void SelectionDAG::RemoveDeadNodes() {
568 // Create a dummy node (which is not added to allnodes), that adds a reference
569 // to the root node, preventing it from being deleted.
570 HandleSDNode
Dummy(getRoot());
572 SmallVector
<SDNode
*, 128> DeadNodes
;
574 // Add all obviously-dead nodes to the DeadNodes worklist.
575 for (allnodes_iterator I
= allnodes_begin(), E
= allnodes_end(); I
!= E
; ++I
)
577 DeadNodes
.push_back(I
);
579 RemoveDeadNodes(DeadNodes
);
581 // If the root changed (e.g. it was a dead load, update the root).
582 setRoot(Dummy
.getValue());
585 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
586 /// given list, and any nodes that become unreachable as a result.
587 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl
<SDNode
*> &DeadNodes
) {
589 // Process the worklist, deleting the nodes and adding their uses to the
591 while (!DeadNodes
.empty()) {
592 SDNode
*N
= DeadNodes
.pop_back_val();
594 for (DAGUpdateListener
*DUL
= UpdateListeners
; DUL
; DUL
= DUL
->Next
)
595 DUL
->NodeDeleted(N
, 0);
597 // Take the node out of the appropriate CSE map.
598 RemoveNodeFromCSEMaps(N
);
600 // Next, brutally remove the operand list. This is safe to do, as there are
601 // no cycles in the graph.
602 for (SDNode::op_iterator I
= N
->op_begin(), E
= N
->op_end(); I
!= E
; ) {
604 SDNode
*Operand
= Use
.getNode();
607 // Now that we removed this operand, see if there are no uses of it left.
608 if (Operand
->use_empty())
609 DeadNodes
.push_back(Operand
);
616 void SelectionDAG::RemoveDeadNode(SDNode
*N
){
617 SmallVector
<SDNode
*, 16> DeadNodes(1, N
);
619 // Create a dummy node that adds a reference to the root node, preventing
620 // it from being deleted. (This matters if the root is an operand of the
622 HandleSDNode
Dummy(getRoot());
624 RemoveDeadNodes(DeadNodes
);
627 void SelectionDAG::DeleteNode(SDNode
*N
) {
628 // First take this out of the appropriate CSE map.
629 RemoveNodeFromCSEMaps(N
);
631 // Finally, remove uses due to operands of this node, remove from the
632 // AllNodes list, and delete the node.
633 DeleteNodeNotInCSEMaps(N
);
636 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode
*N
) {
637 assert(N
!= AllNodes
.begin() && "Cannot delete the entry node!");
638 assert(N
->use_empty() && "Cannot delete a node that is not dead!");
640 // Drop all of the operands and decrement used node's use counts.
646 void SelectionDAG::DeallocateNode(SDNode
*N
) {
647 if (N
->OperandsNeedDelete
)
648 delete[] N
->OperandList
;
650 // Set the opcode to DELETED_NODE to help catch bugs when node
651 // memory is reallocated.
652 N
->NodeType
= ISD::DELETED_NODE
;
654 NodeAllocator
.Deallocate(AllNodes
.remove(N
));
656 // Remove the ordering of this node.
659 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
660 ArrayRef
<SDDbgValue
*> DbgVals
= DbgInfo
->getSDDbgValues(N
);
661 for (unsigned i
= 0, e
= DbgVals
.size(); i
!= e
; ++i
)
662 DbgVals
[i
]->setIsInvalidated();
665 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
666 /// correspond to it. This is useful when we're about to delete or repurpose
667 /// the node. We don't want future request for structurally identical nodes
668 /// to return N anymore.
669 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode
*N
) {
671 switch (N
->getOpcode()) {
672 case ISD::HANDLENODE
: return false; // noop.
674 assert(CondCodeNodes
[cast
<CondCodeSDNode
>(N
)->get()] &&
675 "Cond code doesn't exist!");
676 Erased
= CondCodeNodes
[cast
<CondCodeSDNode
>(N
)->get()] != 0;
677 CondCodeNodes
[cast
<CondCodeSDNode
>(N
)->get()] = 0;
679 case ISD::ExternalSymbol
:
680 Erased
= ExternalSymbols
.erase(cast
<ExternalSymbolSDNode
>(N
)->getSymbol());
682 case ISD::TargetExternalSymbol
: {
683 ExternalSymbolSDNode
*ESN
= cast
<ExternalSymbolSDNode
>(N
);
684 Erased
= TargetExternalSymbols
.erase(
685 std::pair
<std::string
,unsigned char>(ESN
->getSymbol(),
686 ESN
->getTargetFlags()));
689 case ISD::VALUETYPE
: {
690 EVT VT
= cast
<VTSDNode
>(N
)->getVT();
691 if (VT
.isExtended()) {
692 Erased
= ExtendedValueTypeNodes
.erase(VT
);
694 Erased
= ValueTypeNodes
[VT
.getSimpleVT().SimpleTy
] != 0;
695 ValueTypeNodes
[VT
.getSimpleVT().SimpleTy
] = 0;
700 // Remove it from the CSE Map.
701 assert(N
->getOpcode() != ISD::DELETED_NODE
&& "DELETED_NODE in CSEMap!");
702 assert(N
->getOpcode() != ISD::EntryToken
&& "EntryToken in CSEMap!");
703 Erased
= CSEMap
.RemoveNode(N
);
707 // Verify that the node was actually in one of the CSE maps, unless it has a
708 // flag result (which cannot be CSE'd) or is one of the special cases that are
709 // not subject to CSE.
710 if (!Erased
&& N
->getValueType(N
->getNumValues()-1) != MVT::Glue
&&
711 !N
->isMachineOpcode() && !doNotCSE(N
)) {
714 llvm_unreachable("Node is not in map!");
720 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
721 /// maps and modified in place. Add it back to the CSE maps, unless an identical
722 /// node already exists, in which case transfer all its users to the existing
723 /// node. This transfer can potentially trigger recursive merging.
726 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode
*N
) {
727 // For node types that aren't CSE'd, just act as if no identical node
730 SDNode
*Existing
= CSEMap
.GetOrInsertNode(N
);
732 // If there was already an existing matching node, use ReplaceAllUsesWith
733 // to replace the dead one with the existing one. This can cause
734 // recursive merging of other unrelated nodes down the line.
735 ReplaceAllUsesWith(N
, Existing
);
737 // N is now dead. Inform the listeners and delete it.
738 for (DAGUpdateListener
*DUL
= UpdateListeners
; DUL
; DUL
= DUL
->Next
)
739 DUL
->NodeDeleted(N
, Existing
);
740 DeleteNodeNotInCSEMaps(N
);
745 // If the node doesn't already exist, we updated it. Inform listeners.
746 for (DAGUpdateListener
*DUL
= UpdateListeners
; DUL
; DUL
= DUL
->Next
)
750 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
751 /// were replaced with those specified. If this node is never memoized,
752 /// return null, otherwise return a pointer to the slot it would take. If a
753 /// node already exists with these operands, the slot will be non-null.
754 SDNode
*SelectionDAG::FindModifiedNodeSlot(SDNode
*N
, SDValue Op
,
759 SDValue Ops
[] = { Op
};
761 AddNodeIDNode(ID
, N
->getOpcode(), N
->getVTList(), Ops
, 1);
762 AddNodeIDCustom(ID
, N
);
763 SDNode
*Node
= CSEMap
.FindNodeOrInsertPos(ID
, InsertPos
);
767 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
768 /// were replaced with those specified. If this node is never memoized,
769 /// return null, otherwise return a pointer to the slot it would take. If a
770 /// node already exists with these operands, the slot will be non-null.
771 SDNode
*SelectionDAG::FindModifiedNodeSlot(SDNode
*N
,
772 SDValue Op1
, SDValue Op2
,
777 SDValue Ops
[] = { Op1
, Op2
};
779 AddNodeIDNode(ID
, N
->getOpcode(), N
->getVTList(), Ops
, 2);
780 AddNodeIDCustom(ID
, N
);
781 SDNode
*Node
= CSEMap
.FindNodeOrInsertPos(ID
, InsertPos
);
786 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
787 /// were replaced with those specified. If this node is never memoized,
788 /// return null, otherwise return a pointer to the slot it would take. If a
789 /// node already exists with these operands, the slot will be non-null.
790 SDNode
*SelectionDAG::FindModifiedNodeSlot(SDNode
*N
,
791 const SDValue
*Ops
,unsigned NumOps
,
797 AddNodeIDNode(ID
, N
->getOpcode(), N
->getVTList(), Ops
, NumOps
);
798 AddNodeIDCustom(ID
, N
);
799 SDNode
*Node
= CSEMap
.FindNodeOrInsertPos(ID
, InsertPos
);
804 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
805 static void VerifyNodeCommon(SDNode
*N
) {
806 switch (N
->getOpcode()) {
809 case ISD::BUILD_PAIR
: {
810 EVT VT
= N
->getValueType(0);
811 assert(N
->getNumValues() == 1 && "Too many results!");
812 assert(!VT
.isVector() && (VT
.isInteger() || VT
.isFloatingPoint()) &&
813 "Wrong return type!");
814 assert(N
->getNumOperands() == 2 && "Wrong number of operands!");
815 assert(N
->getOperand(0).getValueType() == N
->getOperand(1).getValueType() &&
816 "Mismatched operand types!");
817 assert(N
->getOperand(0).getValueType().isInteger() == VT
.isInteger() &&
818 "Wrong operand type!");
819 assert(VT
.getSizeInBits() == 2 * N
->getOperand(0).getValueSizeInBits() &&
820 "Wrong return type size");
823 case ISD::BUILD_VECTOR
: {
824 assert(N
->getNumValues() == 1 && "Too many results!");
825 assert(N
->getValueType(0).isVector() && "Wrong return type!");
826 assert(N
->getNumOperands() == N
->getValueType(0).getVectorNumElements() &&
827 "Wrong number of operands!");
828 EVT EltVT
= N
->getValueType(0).getVectorElementType();
829 for (SDNode::op_iterator I
= N
->op_begin(), E
= N
->op_end(); I
!= E
; ++I
) {
830 assert((I
->getValueType() == EltVT
||
831 (EltVT
.isInteger() && I
->getValueType().isInteger() &&
832 EltVT
.bitsLE(I
->getValueType()))) &&
833 "Wrong operand type!");
834 assert(I
->getValueType() == N
->getOperand(0).getValueType() &&
835 "Operands must all have the same type");
842 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
843 static void VerifySDNode(SDNode
*N
) {
844 // The SDNode allocators cannot be used to allocate nodes with fields that are
845 // not present in an SDNode!
846 assert(!isa
<MemSDNode
>(N
) && "Bad MemSDNode!");
847 assert(!isa
<ShuffleVectorSDNode
>(N
) && "Bad ShuffleVectorSDNode!");
848 assert(!isa
<ConstantSDNode
>(N
) && "Bad ConstantSDNode!");
849 assert(!isa
<ConstantFPSDNode
>(N
) && "Bad ConstantFPSDNode!");
850 assert(!isa
<GlobalAddressSDNode
>(N
) && "Bad GlobalAddressSDNode!");
851 assert(!isa
<FrameIndexSDNode
>(N
) && "Bad FrameIndexSDNode!");
852 assert(!isa
<JumpTableSDNode
>(N
) && "Bad JumpTableSDNode!");
853 assert(!isa
<ConstantPoolSDNode
>(N
) && "Bad ConstantPoolSDNode!");
854 assert(!isa
<BasicBlockSDNode
>(N
) && "Bad BasicBlockSDNode!");
855 assert(!isa
<SrcValueSDNode
>(N
) && "Bad SrcValueSDNode!");
856 assert(!isa
<MDNodeSDNode
>(N
) && "Bad MDNodeSDNode!");
857 assert(!isa
<RegisterSDNode
>(N
) && "Bad RegisterSDNode!");
858 assert(!isa
<BlockAddressSDNode
>(N
) && "Bad BlockAddressSDNode!");
859 assert(!isa
<EHLabelSDNode
>(N
) && "Bad EHLabelSDNode!");
860 assert(!isa
<ExternalSymbolSDNode
>(N
) && "Bad ExternalSymbolSDNode!");
861 assert(!isa
<CondCodeSDNode
>(N
) && "Bad CondCodeSDNode!");
862 assert(!isa
<CvtRndSatSDNode
>(N
) && "Bad CvtRndSatSDNode!");
863 assert(!isa
<VTSDNode
>(N
) && "Bad VTSDNode!");
864 assert(!isa
<MachineSDNode
>(N
) && "Bad MachineSDNode!");
869 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
871 static void VerifyMachineNode(SDNode
*N
) {
872 // The MachineNode allocators cannot be used to allocate nodes with fields
873 // that are not present in a MachineNode!
874 // Currently there are no such nodes.
880 /// getEVTAlignment - Compute the default alignment value for the
883 unsigned SelectionDAG::getEVTAlignment(EVT VT
) const {
884 Type
*Ty
= VT
== MVT::iPTR
?
885 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
886 VT
.getTypeForEVT(*getContext());
888 return TLI
.getTargetData()->getABITypeAlignment(Ty
);
891 // EntryNode could meaningfully have debug info if we can find it...
892 SelectionDAG::SelectionDAG(const TargetMachine
&tm
, CodeGenOpt::Level OL
)
893 : TM(tm
), TLI(*tm
.getTargetLowering()), TSI(*tm
.getSelectionDAGInfo()),
894 OptLevel(OL
), EntryNode(ISD::EntryToken
, DebugLoc(), getVTList(MVT::Other
)),
895 Root(getEntryNode()), Ordering(0), UpdateListeners(0) {
896 AllNodes
.push_back(&EntryNode
);
897 Ordering
= new SDNodeOrdering();
898 DbgInfo
= new SDDbgInfo();
901 void SelectionDAG::init(MachineFunction
&mf
) {
903 Context
= &mf
.getFunction()->getContext();
906 SelectionDAG::~SelectionDAG() {
907 assert(!UpdateListeners
&& "Dangling registered DAGUpdateListeners");
913 void SelectionDAG::allnodes_clear() {
914 assert(&*AllNodes
.begin() == &EntryNode
);
915 AllNodes
.remove(AllNodes
.begin());
916 while (!AllNodes
.empty())
917 DeallocateNode(AllNodes
.begin());
920 void SelectionDAG::clear() {
922 OperandAllocator
.Reset();
925 ExtendedValueTypeNodes
.clear();
926 ExternalSymbols
.clear();
927 TargetExternalSymbols
.clear();
928 std::fill(CondCodeNodes
.begin(), CondCodeNodes
.end(),
929 static_cast<CondCodeSDNode
*>(0));
930 std::fill(ValueTypeNodes
.begin(), ValueTypeNodes
.end(),
931 static_cast<SDNode
*>(0));
933 EntryNode
.UseList
= 0;
934 AllNodes
.push_back(&EntryNode
);
935 Root
= getEntryNode();
940 SDValue
SelectionDAG::getAnyExtOrTrunc(SDValue Op
, DebugLoc DL
, EVT VT
) {
941 return VT
.bitsGT(Op
.getValueType()) ?
942 getNode(ISD::ANY_EXTEND
, DL
, VT
, Op
) :
943 getNode(ISD::TRUNCATE
, DL
, VT
, Op
);
946 SDValue
SelectionDAG::getSExtOrTrunc(SDValue Op
, DebugLoc DL
, EVT VT
) {
947 return VT
.bitsGT(Op
.getValueType()) ?
948 getNode(ISD::SIGN_EXTEND
, DL
, VT
, Op
) :
949 getNode(ISD::TRUNCATE
, DL
, VT
, Op
);
952 SDValue
SelectionDAG::getZExtOrTrunc(SDValue Op
, DebugLoc DL
, EVT VT
) {
953 return VT
.bitsGT(Op
.getValueType()) ?
954 getNode(ISD::ZERO_EXTEND
, DL
, VT
, Op
) :
955 getNode(ISD::TRUNCATE
, DL
, VT
, Op
);
958 SDValue
SelectionDAG::getZeroExtendInReg(SDValue Op
, DebugLoc DL
, EVT VT
) {
959 assert(!VT
.isVector() &&
960 "getZeroExtendInReg should use the vector element type instead of "
962 if (Op
.getValueType() == VT
) return Op
;
963 unsigned BitWidth
= Op
.getValueType().getScalarType().getSizeInBits();
964 APInt Imm
= APInt::getLowBitsSet(BitWidth
,
966 return getNode(ISD::AND
, DL
, Op
.getValueType(), Op
,
967 getConstant(Imm
, Op
.getValueType()));
970 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
972 SDValue
SelectionDAG::getNOT(DebugLoc DL
, SDValue Val
, EVT VT
) {
973 EVT EltVT
= VT
.getScalarType();
975 getConstant(APInt::getAllOnesValue(EltVT
.getSizeInBits()), VT
);
976 return getNode(ISD::XOR
, DL
, VT
, Val
, NegOne
);
979 SDValue
SelectionDAG::getConstant(uint64_t Val
, EVT VT
, bool isT
) {
980 EVT EltVT
= VT
.getScalarType();
981 assert((EltVT
.getSizeInBits() >= 64 ||
982 (uint64_t)((int64_t)Val
>> EltVT
.getSizeInBits()) + 1 < 2) &&
983 "getConstant with a uint64_t value that doesn't fit in the type!");
984 return getConstant(APInt(EltVT
.getSizeInBits(), Val
), VT
, isT
);
987 SDValue
SelectionDAG::getConstant(const APInt
&Val
, EVT VT
, bool isT
) {
988 return getConstant(*ConstantInt::get(*Context
, Val
), VT
, isT
);
991 SDValue
SelectionDAG::getConstant(const ConstantInt
&Val
, EVT VT
, bool isT
) {
992 assert(VT
.isInteger() && "Cannot create FP integer constant!");
994 EVT EltVT
= VT
.getScalarType();
995 const ConstantInt
*Elt
= &Val
;
997 // In some cases the vector type is legal but the element type is illegal and
998 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
999 // inserted value (the type does not need to match the vector element type).
1000 // Any extra bits introduced will be truncated away.
1001 if (VT
.isVector() && TLI
.getTypeAction(*getContext(), EltVT
) ==
1002 TargetLowering::TypePromoteInteger
) {
1003 EltVT
= TLI
.getTypeToTransformTo(*getContext(), EltVT
);
1004 APInt NewVal
= Elt
->getValue().zext(EltVT
.getSizeInBits());
1005 Elt
= ConstantInt::get(*getContext(), NewVal
);
1008 assert(Elt
->getBitWidth() == EltVT
.getSizeInBits() &&
1009 "APInt size does not match type size!");
1010 unsigned Opc
= isT
? ISD::TargetConstant
: ISD::Constant
;
1011 FoldingSetNodeID ID
;
1012 AddNodeIDNode(ID
, Opc
, getVTList(EltVT
), 0, 0);
1016 if ((N
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)))
1018 return SDValue(N
, 0);
1021 N
= new (NodeAllocator
) ConstantSDNode(isT
, Elt
, EltVT
);
1022 CSEMap
.InsertNode(N
, IP
);
1023 AllNodes
.push_back(N
);
1026 SDValue
Result(N
, 0);
1027 if (VT
.isVector()) {
1028 SmallVector
<SDValue
, 8> Ops
;
1029 Ops
.assign(VT
.getVectorNumElements(), Result
);
1030 Result
= getNode(ISD::BUILD_VECTOR
, DebugLoc(), VT
, &Ops
[0], Ops
.size());
1035 SDValue
SelectionDAG::getIntPtrConstant(uint64_t Val
, bool isTarget
) {
1036 return getConstant(Val
, TLI
.getPointerTy(), isTarget
);
1040 SDValue
SelectionDAG::getConstantFP(const APFloat
& V
, EVT VT
, bool isTarget
) {
1041 return getConstantFP(*ConstantFP::get(*getContext(), V
), VT
, isTarget
);
1044 SDValue
SelectionDAG::getConstantFP(const ConstantFP
& V
, EVT VT
, bool isTarget
){
1045 assert(VT
.isFloatingPoint() && "Cannot create integer FP constant!");
1047 EVT EltVT
= VT
.getScalarType();
1049 // Do the map lookup using the actual bit pattern for the floating point
1050 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1051 // we don't have issues with SNANs.
1052 unsigned Opc
= isTarget
? ISD::TargetConstantFP
: ISD::ConstantFP
;
1053 FoldingSetNodeID ID
;
1054 AddNodeIDNode(ID
, Opc
, getVTList(EltVT
), 0, 0);
1058 if ((N
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)))
1060 return SDValue(N
, 0);
1063 N
= new (NodeAllocator
) ConstantFPSDNode(isTarget
, &V
, EltVT
);
1064 CSEMap
.InsertNode(N
, IP
);
1065 AllNodes
.push_back(N
);
1068 SDValue
Result(N
, 0);
1069 if (VT
.isVector()) {
1070 SmallVector
<SDValue
, 8> Ops
;
1071 Ops
.assign(VT
.getVectorNumElements(), Result
);
1072 // FIXME DebugLoc info might be appropriate here
1073 Result
= getNode(ISD::BUILD_VECTOR
, DebugLoc(), VT
, &Ops
[0], Ops
.size());
1078 SDValue
SelectionDAG::getConstantFP(double Val
, EVT VT
, bool isTarget
) {
1079 EVT EltVT
= VT
.getScalarType();
1080 if (EltVT
==MVT::f32
)
1081 return getConstantFP(APFloat((float)Val
), VT
, isTarget
);
1082 else if (EltVT
==MVT::f64
)
1083 return getConstantFP(APFloat(Val
), VT
, isTarget
);
1084 else if (EltVT
==MVT::f80
|| EltVT
==MVT::f128
|| EltVT
==MVT::f16
) {
1086 APFloat apf
= APFloat(Val
);
1087 apf
.convert(*EVTToAPFloatSemantics(EltVT
), APFloat::rmNearestTiesToEven
,
1089 return getConstantFP(apf
, VT
, isTarget
);
1091 llvm_unreachable("Unsupported type in getConstantFP");
1094 SDValue
SelectionDAG::getGlobalAddress(const GlobalValue
*GV
, DebugLoc DL
,
1095 EVT VT
, int64_t Offset
,
1097 unsigned char TargetFlags
) {
1098 assert((TargetFlags
== 0 || isTargetGA
) &&
1099 "Cannot set target flags on target-independent globals");
1101 // Truncate (with sign-extension) the offset value to the pointer size.
1102 unsigned BitWidth
= TLI
.getPointerTy().getSizeInBits();
1104 Offset
= SignExtend64(Offset
, BitWidth
);
1106 const GlobalVariable
*GVar
= dyn_cast
<GlobalVariable
>(GV
);
1108 // If GV is an alias then use the aliasee for determining thread-localness.
1109 if (const GlobalAlias
*GA
= dyn_cast
<GlobalAlias
>(GV
))
1110 GVar
= dyn_cast_or_null
<GlobalVariable
>(GA
->resolveAliasedGlobal(false));
1114 if (GVar
&& GVar
->isThreadLocal())
1115 Opc
= isTargetGA
? ISD::TargetGlobalTLSAddress
: ISD::GlobalTLSAddress
;
1117 Opc
= isTargetGA
? ISD::TargetGlobalAddress
: ISD::GlobalAddress
;
1119 FoldingSetNodeID ID
;
1120 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1122 ID
.AddInteger(Offset
);
1123 ID
.AddInteger(TargetFlags
);
1124 ID
.AddInteger(GV
->getType()->getAddressSpace());
1126 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1127 return SDValue(E
, 0);
1129 SDNode
*N
= new (NodeAllocator
) GlobalAddressSDNode(Opc
, DL
, GV
, VT
,
1130 Offset
, TargetFlags
);
1131 CSEMap
.InsertNode(N
, IP
);
1132 AllNodes
.push_back(N
);
1133 return SDValue(N
, 0);
1136 SDValue
SelectionDAG::getFrameIndex(int FI
, EVT VT
, bool isTarget
) {
1137 unsigned Opc
= isTarget
? ISD::TargetFrameIndex
: ISD::FrameIndex
;
1138 FoldingSetNodeID ID
;
1139 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1142 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1143 return SDValue(E
, 0);
1145 SDNode
*N
= new (NodeAllocator
) FrameIndexSDNode(FI
, VT
, isTarget
);
1146 CSEMap
.InsertNode(N
, IP
);
1147 AllNodes
.push_back(N
);
1148 return SDValue(N
, 0);
1151 SDValue
SelectionDAG::getJumpTable(int JTI
, EVT VT
, bool isTarget
,
1152 unsigned char TargetFlags
) {
1153 assert((TargetFlags
== 0 || isTarget
) &&
1154 "Cannot set target flags on target-independent jump tables");
1155 unsigned Opc
= isTarget
? ISD::TargetJumpTable
: ISD::JumpTable
;
1156 FoldingSetNodeID ID
;
1157 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1159 ID
.AddInteger(TargetFlags
);
1161 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1162 return SDValue(E
, 0);
1164 SDNode
*N
= new (NodeAllocator
) JumpTableSDNode(JTI
, VT
, isTarget
,
1166 CSEMap
.InsertNode(N
, IP
);
1167 AllNodes
.push_back(N
);
1168 return SDValue(N
, 0);
1171 SDValue
SelectionDAG::getConstantPool(const Constant
*C
, EVT VT
,
1172 unsigned Alignment
, int Offset
,
1174 unsigned char TargetFlags
) {
1175 assert((TargetFlags
== 0 || isTarget
) &&
1176 "Cannot set target flags on target-independent globals");
1178 Alignment
= TLI
.getTargetData()->getPrefTypeAlignment(C
->getType());
1179 unsigned Opc
= isTarget
? ISD::TargetConstantPool
: ISD::ConstantPool
;
1180 FoldingSetNodeID ID
;
1181 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1182 ID
.AddInteger(Alignment
);
1183 ID
.AddInteger(Offset
);
1185 ID
.AddInteger(TargetFlags
);
1187 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1188 return SDValue(E
, 0);
1190 SDNode
*N
= new (NodeAllocator
) ConstantPoolSDNode(isTarget
, C
, VT
, Offset
,
1191 Alignment
, TargetFlags
);
1192 CSEMap
.InsertNode(N
, IP
);
1193 AllNodes
.push_back(N
);
1194 return SDValue(N
, 0);
1198 SDValue
SelectionDAG::getConstantPool(MachineConstantPoolValue
*C
, EVT VT
,
1199 unsigned Alignment
, int Offset
,
1201 unsigned char TargetFlags
) {
1202 assert((TargetFlags
== 0 || isTarget
) &&
1203 "Cannot set target flags on target-independent globals");
1205 Alignment
= TLI
.getTargetData()->getPrefTypeAlignment(C
->getType());
1206 unsigned Opc
= isTarget
? ISD::TargetConstantPool
: ISD::ConstantPool
;
1207 FoldingSetNodeID ID
;
1208 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1209 ID
.AddInteger(Alignment
);
1210 ID
.AddInteger(Offset
);
1211 C
->addSelectionDAGCSEId(ID
);
1212 ID
.AddInteger(TargetFlags
);
1214 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1215 return SDValue(E
, 0);
1217 SDNode
*N
= new (NodeAllocator
) ConstantPoolSDNode(isTarget
, C
, VT
, Offset
,
1218 Alignment
, TargetFlags
);
1219 CSEMap
.InsertNode(N
, IP
);
1220 AllNodes
.push_back(N
);
1221 return SDValue(N
, 0);
1224 SDValue
SelectionDAG::getTargetIndex(int Index
, EVT VT
, int64_t Offset
,
1225 unsigned char TargetFlags
) {
1226 FoldingSetNodeID ID
;
1227 AddNodeIDNode(ID
, ISD::TargetIndex
, getVTList(VT
), 0, 0);
1228 ID
.AddInteger(Index
);
1229 ID
.AddInteger(Offset
);
1230 ID
.AddInteger(TargetFlags
);
1232 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1233 return SDValue(E
, 0);
1235 SDNode
*N
= new (NodeAllocator
) TargetIndexSDNode(Index
, VT
, Offset
,
1237 CSEMap
.InsertNode(N
, IP
);
1238 AllNodes
.push_back(N
);
1239 return SDValue(N
, 0);
1242 SDValue
SelectionDAG::getBasicBlock(MachineBasicBlock
*MBB
) {
1243 FoldingSetNodeID ID
;
1244 AddNodeIDNode(ID
, ISD::BasicBlock
, getVTList(MVT::Other
), 0, 0);
1247 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1248 return SDValue(E
, 0);
1250 SDNode
*N
= new (NodeAllocator
) BasicBlockSDNode(MBB
);
1251 CSEMap
.InsertNode(N
, IP
);
1252 AllNodes
.push_back(N
);
1253 return SDValue(N
, 0);
1256 SDValue
SelectionDAG::getValueType(EVT VT
) {
1257 if (VT
.isSimple() && (unsigned)VT
.getSimpleVT().SimpleTy
>=
1258 ValueTypeNodes
.size())
1259 ValueTypeNodes
.resize(VT
.getSimpleVT().SimpleTy
+1);
1261 SDNode
*&N
= VT
.isExtended() ?
1262 ExtendedValueTypeNodes
[VT
] : ValueTypeNodes
[VT
.getSimpleVT().SimpleTy
];
1264 if (N
) return SDValue(N
, 0);
1265 N
= new (NodeAllocator
) VTSDNode(VT
);
1266 AllNodes
.push_back(N
);
1267 return SDValue(N
, 0);
1270 SDValue
SelectionDAG::getExternalSymbol(const char *Sym
, EVT VT
) {
1271 SDNode
*&N
= ExternalSymbols
[Sym
];
1272 if (N
) return SDValue(N
, 0);
1273 N
= new (NodeAllocator
) ExternalSymbolSDNode(false, Sym
, 0, VT
);
1274 AllNodes
.push_back(N
);
1275 return SDValue(N
, 0);
1278 SDValue
SelectionDAG::getTargetExternalSymbol(const char *Sym
, EVT VT
,
1279 unsigned char TargetFlags
) {
1281 TargetExternalSymbols
[std::pair
<std::string
,unsigned char>(Sym
,
1283 if (N
) return SDValue(N
, 0);
1284 N
= new (NodeAllocator
) ExternalSymbolSDNode(true, Sym
, TargetFlags
, VT
);
1285 AllNodes
.push_back(N
);
1286 return SDValue(N
, 0);
1289 SDValue
SelectionDAG::getCondCode(ISD::CondCode Cond
) {
1290 if ((unsigned)Cond
>= CondCodeNodes
.size())
1291 CondCodeNodes
.resize(Cond
+1);
1293 if (CondCodeNodes
[Cond
] == 0) {
1294 CondCodeSDNode
*N
= new (NodeAllocator
) CondCodeSDNode(Cond
);
1295 CondCodeNodes
[Cond
] = N
;
1296 AllNodes
.push_back(N
);
1299 return SDValue(CondCodeNodes
[Cond
], 0);
1302 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1303 // the shuffle mask M that point at N1 to point at N2, and indices that point
1304 // N2 to point at N1.
1305 static void commuteShuffle(SDValue
&N1
, SDValue
&N2
, SmallVectorImpl
<int> &M
) {
1307 int NElts
= M
.size();
1308 for (int i
= 0; i
!= NElts
; ++i
) {
1316 SDValue
SelectionDAG::getVectorShuffle(EVT VT
, DebugLoc dl
, SDValue N1
,
1317 SDValue N2
, const int *Mask
) {
1318 assert(N1
.getValueType() == N2
.getValueType() && "Invalid VECTOR_SHUFFLE");
1319 assert(VT
.isVector() && N1
.getValueType().isVector() &&
1320 "Vector Shuffle VTs must be a vectors");
1321 assert(VT
.getVectorElementType() == N1
.getValueType().getVectorElementType()
1322 && "Vector Shuffle VTs must have same element type");
1324 // Canonicalize shuffle undef, undef -> undef
1325 if (N1
.getOpcode() == ISD::UNDEF
&& N2
.getOpcode() == ISD::UNDEF
)
1326 return getUNDEF(VT
);
1328 // Validate that all indices in Mask are within the range of the elements
1329 // input to the shuffle.
1330 unsigned NElts
= VT
.getVectorNumElements();
1331 SmallVector
<int, 8> MaskVec
;
1332 for (unsigned i
= 0; i
!= NElts
; ++i
) {
1333 assert(Mask
[i
] < (int)(NElts
* 2) && "Index out of range");
1334 MaskVec
.push_back(Mask
[i
]);
1337 // Canonicalize shuffle v, v -> v, undef
1340 for (unsigned i
= 0; i
!= NElts
; ++i
)
1341 if (MaskVec
[i
] >= (int)NElts
) MaskVec
[i
] -= NElts
;
1344 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1345 if (N1
.getOpcode() == ISD::UNDEF
)
1346 commuteShuffle(N1
, N2
, MaskVec
);
1348 // Canonicalize all index into lhs, -> shuffle lhs, undef
1349 // Canonicalize all index into rhs, -> shuffle rhs, undef
1350 bool AllLHS
= true, AllRHS
= true;
1351 bool N2Undef
= N2
.getOpcode() == ISD::UNDEF
;
1352 for (unsigned i
= 0; i
!= NElts
; ++i
) {
1353 if (MaskVec
[i
] >= (int)NElts
) {
1358 } else if (MaskVec
[i
] >= 0) {
1362 if (AllLHS
&& AllRHS
)
1363 return getUNDEF(VT
);
1364 if (AllLHS
&& !N2Undef
)
1368 commuteShuffle(N1
, N2
, MaskVec
);
1371 // If Identity shuffle, or all shuffle in to undef, return that node.
1372 bool AllUndef
= true;
1373 bool Identity
= true;
1374 for (unsigned i
= 0; i
!= NElts
; ++i
) {
1375 if (MaskVec
[i
] >= 0 && MaskVec
[i
] != (int)i
) Identity
= false;
1376 if (MaskVec
[i
] >= 0) AllUndef
= false;
1378 if (Identity
&& NElts
== N1
.getValueType().getVectorNumElements())
1381 return getUNDEF(VT
);
1383 FoldingSetNodeID ID
;
1384 SDValue Ops
[2] = { N1
, N2
};
1385 AddNodeIDNode(ID
, ISD::VECTOR_SHUFFLE
, getVTList(VT
), Ops
, 2);
1386 for (unsigned i
= 0; i
!= NElts
; ++i
)
1387 ID
.AddInteger(MaskVec
[i
]);
1390 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1391 return SDValue(E
, 0);
1393 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1394 // SDNode doesn't have access to it. This memory will be "leaked" when
1395 // the node is deallocated, but recovered when the NodeAllocator is released.
1396 int *MaskAlloc
= OperandAllocator
.Allocate
<int>(NElts
);
1397 memcpy(MaskAlloc
, &MaskVec
[0], NElts
* sizeof(int));
1399 ShuffleVectorSDNode
*N
=
1400 new (NodeAllocator
) ShuffleVectorSDNode(VT
, dl
, N1
, N2
, MaskAlloc
);
1401 CSEMap
.InsertNode(N
, IP
);
1402 AllNodes
.push_back(N
);
1403 return SDValue(N
, 0);
1406 SDValue
SelectionDAG::getConvertRndSat(EVT VT
, DebugLoc dl
,
1407 SDValue Val
, SDValue DTy
,
1408 SDValue STy
, SDValue Rnd
, SDValue Sat
,
1409 ISD::CvtCode Code
) {
1410 // If the src and dest types are the same and the conversion is between
1411 // integer types of the same sign or two floats, no conversion is necessary.
1413 (Code
== ISD::CVT_UU
|| Code
== ISD::CVT_SS
|| Code
== ISD::CVT_FF
))
1416 FoldingSetNodeID ID
;
1417 SDValue Ops
[] = { Val
, DTy
, STy
, Rnd
, Sat
};
1418 AddNodeIDNode(ID
, ISD::CONVERT_RNDSAT
, getVTList(VT
), &Ops
[0], 5);
1420 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1421 return SDValue(E
, 0);
1423 CvtRndSatSDNode
*N
= new (NodeAllocator
) CvtRndSatSDNode(VT
, dl
, Ops
, 5,
1425 CSEMap
.InsertNode(N
, IP
);
1426 AllNodes
.push_back(N
);
1427 return SDValue(N
, 0);
1430 SDValue
SelectionDAG::getRegister(unsigned RegNo
, EVT VT
) {
1431 FoldingSetNodeID ID
;
1432 AddNodeIDNode(ID
, ISD::Register
, getVTList(VT
), 0, 0);
1433 ID
.AddInteger(RegNo
);
1435 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1436 return SDValue(E
, 0);
1438 SDNode
*N
= new (NodeAllocator
) RegisterSDNode(RegNo
, VT
);
1439 CSEMap
.InsertNode(N
, IP
);
1440 AllNodes
.push_back(N
);
1441 return SDValue(N
, 0);
1444 SDValue
SelectionDAG::getRegisterMask(const uint32_t *RegMask
) {
1445 FoldingSetNodeID ID
;
1446 AddNodeIDNode(ID
, ISD::RegisterMask
, getVTList(MVT::Untyped
), 0, 0);
1447 ID
.AddPointer(RegMask
);
1449 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1450 return SDValue(E
, 0);
1452 SDNode
*N
= new (NodeAllocator
) RegisterMaskSDNode(RegMask
);
1453 CSEMap
.InsertNode(N
, IP
);
1454 AllNodes
.push_back(N
);
1455 return SDValue(N
, 0);
1458 SDValue
SelectionDAG::getEHLabel(DebugLoc dl
, SDValue Root
, MCSymbol
*Label
) {
1459 FoldingSetNodeID ID
;
1460 SDValue Ops
[] = { Root
};
1461 AddNodeIDNode(ID
, ISD::EH_LABEL
, getVTList(MVT::Other
), &Ops
[0], 1);
1462 ID
.AddPointer(Label
);
1464 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1465 return SDValue(E
, 0);
1467 SDNode
*N
= new (NodeAllocator
) EHLabelSDNode(dl
, Root
, Label
);
1468 CSEMap
.InsertNode(N
, IP
);
1469 AllNodes
.push_back(N
);
1470 return SDValue(N
, 0);
1474 SDValue
SelectionDAG::getBlockAddress(const BlockAddress
*BA
, EVT VT
,
1477 unsigned char TargetFlags
) {
1478 unsigned Opc
= isTarget
? ISD::TargetBlockAddress
: ISD::BlockAddress
;
1480 FoldingSetNodeID ID
;
1481 AddNodeIDNode(ID
, Opc
, getVTList(VT
), 0, 0);
1483 ID
.AddInteger(Offset
);
1484 ID
.AddInteger(TargetFlags
);
1486 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1487 return SDValue(E
, 0);
1489 SDNode
*N
= new (NodeAllocator
) BlockAddressSDNode(Opc
, VT
, BA
, Offset
,
1491 CSEMap
.InsertNode(N
, IP
);
1492 AllNodes
.push_back(N
);
1493 return SDValue(N
, 0);
1496 SDValue
SelectionDAG::getSrcValue(const Value
*V
) {
1497 assert((!V
|| V
->getType()->isPointerTy()) &&
1498 "SrcValue is not a pointer?");
1500 FoldingSetNodeID ID
;
1501 AddNodeIDNode(ID
, ISD::SRCVALUE
, getVTList(MVT::Other
), 0, 0);
1505 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1506 return SDValue(E
, 0);
1508 SDNode
*N
= new (NodeAllocator
) SrcValueSDNode(V
);
1509 CSEMap
.InsertNode(N
, IP
);
1510 AllNodes
.push_back(N
);
1511 return SDValue(N
, 0);
1514 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1515 SDValue
SelectionDAG::getMDNode(const MDNode
*MD
) {
1516 FoldingSetNodeID ID
;
1517 AddNodeIDNode(ID
, ISD::MDNODE_SDNODE
, getVTList(MVT::Other
), 0, 0);
1521 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
1522 return SDValue(E
, 0);
1524 SDNode
*N
= new (NodeAllocator
) MDNodeSDNode(MD
);
1525 CSEMap
.InsertNode(N
, IP
);
1526 AllNodes
.push_back(N
);
1527 return SDValue(N
, 0);
1531 /// getShiftAmountOperand - Return the specified value casted to
1532 /// the target's desired shift amount type.
1533 SDValue
SelectionDAG::getShiftAmountOperand(EVT LHSTy
, SDValue Op
) {
1534 EVT OpTy
= Op
.getValueType();
1535 MVT ShTy
= TLI
.getShiftAmountTy(LHSTy
);
1536 if (OpTy
== ShTy
|| OpTy
.isVector()) return Op
;
1538 ISD::NodeType Opcode
= OpTy
.bitsGT(ShTy
) ? ISD::TRUNCATE
: ISD::ZERO_EXTEND
;
1539 return getNode(Opcode
, Op
.getDebugLoc(), ShTy
, Op
);
1542 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1543 /// specified value type.
1544 SDValue
SelectionDAG::CreateStackTemporary(EVT VT
, unsigned minAlign
) {
1545 MachineFrameInfo
*FrameInfo
= getMachineFunction().getFrameInfo();
1546 unsigned ByteSize
= VT
.getStoreSize();
1547 Type
*Ty
= VT
.getTypeForEVT(*getContext());
1548 unsigned StackAlign
=
1549 std::max((unsigned)TLI
.getTargetData()->getPrefTypeAlignment(Ty
), minAlign
);
1551 int FrameIdx
= FrameInfo
->CreateStackObject(ByteSize
, StackAlign
, false);
1552 return getFrameIndex(FrameIdx
, TLI
.getPointerTy());
1555 /// CreateStackTemporary - Create a stack temporary suitable for holding
1556 /// either of the specified value types.
1557 SDValue
SelectionDAG::CreateStackTemporary(EVT VT1
, EVT VT2
) {
1558 unsigned Bytes
= std::max(VT1
.getStoreSizeInBits(),
1559 VT2
.getStoreSizeInBits())/8;
1560 Type
*Ty1
= VT1
.getTypeForEVT(*getContext());
1561 Type
*Ty2
= VT2
.getTypeForEVT(*getContext());
1562 const TargetData
*TD
= TLI
.getTargetData();
1563 unsigned Align
= std::max(TD
->getPrefTypeAlignment(Ty1
),
1564 TD
->getPrefTypeAlignment(Ty2
));
1566 MachineFrameInfo
*FrameInfo
= getMachineFunction().getFrameInfo();
1567 int FrameIdx
= FrameInfo
->CreateStackObject(Bytes
, Align
, false);
1568 return getFrameIndex(FrameIdx
, TLI
.getPointerTy());
1571 SDValue
SelectionDAG::FoldSetCC(EVT VT
, SDValue N1
,
1572 SDValue N2
, ISD::CondCode Cond
, DebugLoc dl
) {
1573 // These setcc operations always fold.
1577 case ISD::SETFALSE2
: return getConstant(0, VT
);
1579 case ISD::SETTRUE2
: return getConstant(1, VT
);
1591 assert(!N1
.getValueType().isInteger() && "Illegal setcc for integer!");
1595 if (ConstantSDNode
*N2C
= dyn_cast
<ConstantSDNode
>(N2
.getNode())) {
1596 const APInt
&C2
= N2C
->getAPIntValue();
1597 if (ConstantSDNode
*N1C
= dyn_cast
<ConstantSDNode
>(N1
.getNode())) {
1598 const APInt
&C1
= N1C
->getAPIntValue();
1601 default: llvm_unreachable("Unknown integer setcc!");
1602 case ISD::SETEQ
: return getConstant(C1
== C2
, VT
);
1603 case ISD::SETNE
: return getConstant(C1
!= C2
, VT
);
1604 case ISD::SETULT
: return getConstant(C1
.ult(C2
), VT
);
1605 case ISD::SETUGT
: return getConstant(C1
.ugt(C2
), VT
);
1606 case ISD::SETULE
: return getConstant(C1
.ule(C2
), VT
);
1607 case ISD::SETUGE
: return getConstant(C1
.uge(C2
), VT
);
1608 case ISD::SETLT
: return getConstant(C1
.slt(C2
), VT
);
1609 case ISD::SETGT
: return getConstant(C1
.sgt(C2
), VT
);
1610 case ISD::SETLE
: return getConstant(C1
.sle(C2
), VT
);
1611 case ISD::SETGE
: return getConstant(C1
.sge(C2
), VT
);
1615 if (ConstantFPSDNode
*N1C
= dyn_cast
<ConstantFPSDNode
>(N1
.getNode())) {
1616 if (ConstantFPSDNode
*N2C
= dyn_cast
<ConstantFPSDNode
>(N2
.getNode())) {
1617 // No compile time operations on this type yet.
1618 if (N1C
->getValueType(0) == MVT::ppcf128
)
1621 APFloat::cmpResult R
= N1C
->getValueAPF().compare(N2C
->getValueAPF());
1624 case ISD::SETEQ
: if (R
==APFloat::cmpUnordered
)
1625 return getUNDEF(VT
);
1627 case ISD::SETOEQ
: return getConstant(R
==APFloat::cmpEqual
, VT
);
1628 case ISD::SETNE
: if (R
==APFloat::cmpUnordered
)
1629 return getUNDEF(VT
);
1631 case ISD::SETONE
: return getConstant(R
==APFloat::cmpGreaterThan
||
1632 R
==APFloat::cmpLessThan
, VT
);
1633 case ISD::SETLT
: if (R
==APFloat::cmpUnordered
)
1634 return getUNDEF(VT
);
1636 case ISD::SETOLT
: return getConstant(R
==APFloat::cmpLessThan
, VT
);
1637 case ISD::SETGT
: if (R
==APFloat::cmpUnordered
)
1638 return getUNDEF(VT
);
1640 case ISD::SETOGT
: return getConstant(R
==APFloat::cmpGreaterThan
, VT
);
1641 case ISD::SETLE
: if (R
==APFloat::cmpUnordered
)
1642 return getUNDEF(VT
);
1644 case ISD::SETOLE
: return getConstant(R
==APFloat::cmpLessThan
||
1645 R
==APFloat::cmpEqual
, VT
);
1646 case ISD::SETGE
: if (R
==APFloat::cmpUnordered
)
1647 return getUNDEF(VT
);
1649 case ISD::SETOGE
: return getConstant(R
==APFloat::cmpGreaterThan
||
1650 R
==APFloat::cmpEqual
, VT
);
1651 case ISD::SETO
: return getConstant(R
!=APFloat::cmpUnordered
, VT
);
1652 case ISD::SETUO
: return getConstant(R
==APFloat::cmpUnordered
, VT
);
1653 case ISD::SETUEQ
: return getConstant(R
==APFloat::cmpUnordered
||
1654 R
==APFloat::cmpEqual
, VT
);
1655 case ISD::SETUNE
: return getConstant(R
!=APFloat::cmpEqual
, VT
);
1656 case ISD::SETULT
: return getConstant(R
==APFloat::cmpUnordered
||
1657 R
==APFloat::cmpLessThan
, VT
);
1658 case ISD::SETUGT
: return getConstant(R
==APFloat::cmpGreaterThan
||
1659 R
==APFloat::cmpUnordered
, VT
);
1660 case ISD::SETULE
: return getConstant(R
!=APFloat::cmpGreaterThan
, VT
);
1661 case ISD::SETUGE
: return getConstant(R
!=APFloat::cmpLessThan
, VT
);
1664 // Ensure that the constant occurs on the RHS.
1665 return getSetCC(dl
, VT
, N2
, N1
, ISD::getSetCCSwappedOperands(Cond
));
1669 // Could not fold it.
1673 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1674 /// use this predicate to simplify operations downstream.
1675 bool SelectionDAG::SignBitIsZero(SDValue Op
, unsigned Depth
) const {
1676 // This predicate is not safe for vector operations.
1677 if (Op
.getValueType().isVector())
1680 unsigned BitWidth
= Op
.getValueType().getScalarType().getSizeInBits();
1681 return MaskedValueIsZero(Op
, APInt::getSignBit(BitWidth
), Depth
);
1684 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1685 /// this predicate to simplify operations downstream. Mask is known to be zero
1686 /// for bits that V cannot have.
1687 bool SelectionDAG::MaskedValueIsZero(SDValue Op
, const APInt
&Mask
,
1688 unsigned Depth
) const {
1689 APInt KnownZero
, KnownOne
;
1690 ComputeMaskedBits(Op
, KnownZero
, KnownOne
, Depth
);
1691 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1692 return (KnownZero
& Mask
) == Mask
;
1695 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1696 /// known to be either zero or one and return them in the KnownZero/KnownOne
1697 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1699 void SelectionDAG::ComputeMaskedBits(SDValue Op
, APInt
&KnownZero
,
1700 APInt
&KnownOne
, unsigned Depth
) const {
1701 unsigned BitWidth
= Op
.getValueType().getScalarType().getSizeInBits();
1703 KnownZero
= KnownOne
= APInt(BitWidth
, 0); // Don't know anything.
1705 return; // Limit search depth.
1707 APInt KnownZero2
, KnownOne2
;
1709 switch (Op
.getOpcode()) {
1711 // We know all of the bits for a constant!
1712 KnownOne
= cast
<ConstantSDNode
>(Op
)->getAPIntValue();
1713 KnownZero
= ~KnownOne
;
1716 // If either the LHS or the RHS are Zero, the result is zero.
1717 ComputeMaskedBits(Op
.getOperand(1), KnownZero
, KnownOne
, Depth
+1);
1718 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
1719 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1720 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1722 // Output known-1 bits are only known if set in both the LHS & RHS.
1723 KnownOne
&= KnownOne2
;
1724 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1725 KnownZero
|= KnownZero2
;
1728 ComputeMaskedBits(Op
.getOperand(1), KnownZero
, KnownOne
, Depth
+1);
1729 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
1730 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1731 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1733 // Output known-0 bits are only known if clear in both the LHS & RHS.
1734 KnownZero
&= KnownZero2
;
1735 // Output known-1 are known to be set if set in either the LHS | RHS.
1736 KnownOne
|= KnownOne2
;
1739 ComputeMaskedBits(Op
.getOperand(1), KnownZero
, KnownOne
, Depth
+1);
1740 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
1741 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1742 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1744 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1745 APInt KnownZeroOut
= (KnownZero
& KnownZero2
) | (KnownOne
& KnownOne2
);
1746 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1747 KnownOne
= (KnownZero
& KnownOne2
) | (KnownOne
& KnownZero2
);
1748 KnownZero
= KnownZeroOut
;
1752 ComputeMaskedBits(Op
.getOperand(1), KnownZero
, KnownOne
, Depth
+1);
1753 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
1754 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1755 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1757 // If low bits are zero in either operand, output low known-0 bits.
1758 // Also compute a conserative estimate for high known-0 bits.
1759 // More trickiness is possible, but this is sufficient for the
1760 // interesting case of alignment computation.
1761 KnownOne
.clearAllBits();
1762 unsigned TrailZ
= KnownZero
.countTrailingOnes() +
1763 KnownZero2
.countTrailingOnes();
1764 unsigned LeadZ
= std::max(KnownZero
.countLeadingOnes() +
1765 KnownZero2
.countLeadingOnes(),
1766 BitWidth
) - BitWidth
;
1768 TrailZ
= std::min(TrailZ
, BitWidth
);
1769 LeadZ
= std::min(LeadZ
, BitWidth
);
1770 KnownZero
= APInt::getLowBitsSet(BitWidth
, TrailZ
) |
1771 APInt::getHighBitsSet(BitWidth
, LeadZ
);
1775 // For the purposes of computing leading zeros we can conservatively
1776 // treat a udiv as a logical right shift by the power of 2 known to
1777 // be less than the denominator.
1778 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
1779 unsigned LeadZ
= KnownZero2
.countLeadingOnes();
1781 KnownOne2
.clearAllBits();
1782 KnownZero2
.clearAllBits();
1783 ComputeMaskedBits(Op
.getOperand(1), KnownZero2
, KnownOne2
, Depth
+1);
1784 unsigned RHSUnknownLeadingOnes
= KnownOne2
.countLeadingZeros();
1785 if (RHSUnknownLeadingOnes
!= BitWidth
)
1786 LeadZ
= std::min(BitWidth
,
1787 LeadZ
+ BitWidth
- RHSUnknownLeadingOnes
- 1);
1789 KnownZero
= APInt::getHighBitsSet(BitWidth
, LeadZ
);
1793 ComputeMaskedBits(Op
.getOperand(2), KnownZero
, KnownOne
, Depth
+1);
1794 ComputeMaskedBits(Op
.getOperand(1), KnownZero2
, KnownOne2
, Depth
+1);
1795 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1796 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1798 // Only known if known in both the LHS and RHS.
1799 KnownOne
&= KnownOne2
;
1800 KnownZero
&= KnownZero2
;
1802 case ISD::SELECT_CC
:
1803 ComputeMaskedBits(Op
.getOperand(3), KnownZero
, KnownOne
, Depth
+1);
1804 ComputeMaskedBits(Op
.getOperand(2), KnownZero2
, KnownOne2
, Depth
+1);
1805 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1806 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
1808 // Only known if known in both the LHS and RHS.
1809 KnownOne
&= KnownOne2
;
1810 KnownZero
&= KnownZero2
;
1818 if (Op
.getResNo() != 1)
1820 // The boolean result conforms to getBooleanContents. Fall through.
1822 // If we know the result of a setcc has the top bits zero, use this info.
1823 if (TLI
.getBooleanContents(Op
.getValueType().isVector()) ==
1824 TargetLowering::ZeroOrOneBooleanContent
&& BitWidth
> 1)
1825 KnownZero
|= APInt::getHighBitsSet(BitWidth
, BitWidth
- 1);
1828 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1829 if (ConstantSDNode
*SA
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
1830 unsigned ShAmt
= SA
->getZExtValue();
1832 // If the shift count is an invalid immediate, don't do anything.
1833 if (ShAmt
>= BitWidth
)
1836 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1837 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1838 KnownZero
<<= ShAmt
;
1840 // low bits known zero.
1841 KnownZero
|= APInt::getLowBitsSet(BitWidth
, ShAmt
);
1845 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1846 if (ConstantSDNode
*SA
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
1847 unsigned ShAmt
= SA
->getZExtValue();
1849 // If the shift count is an invalid immediate, don't do anything.
1850 if (ShAmt
>= BitWidth
)
1853 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1854 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1855 KnownZero
= KnownZero
.lshr(ShAmt
);
1856 KnownOne
= KnownOne
.lshr(ShAmt
);
1858 APInt HighBits
= APInt::getHighBitsSet(BitWidth
, ShAmt
);
1859 KnownZero
|= HighBits
; // High bits known zero.
1863 if (ConstantSDNode
*SA
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
1864 unsigned ShAmt
= SA
->getZExtValue();
1866 // If the shift count is an invalid immediate, don't do anything.
1867 if (ShAmt
>= BitWidth
)
1870 // If any of the demanded bits are produced by the sign extension, we also
1871 // demand the input sign bit.
1872 APInt HighBits
= APInt::getHighBitsSet(BitWidth
, ShAmt
);
1874 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1875 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1876 KnownZero
= KnownZero
.lshr(ShAmt
);
1877 KnownOne
= KnownOne
.lshr(ShAmt
);
1879 // Handle the sign bits.
1880 APInt SignBit
= APInt::getSignBit(BitWidth
);
1881 SignBit
= SignBit
.lshr(ShAmt
); // Adjust to where it is now in the mask.
1883 if (KnownZero
.intersects(SignBit
)) {
1884 KnownZero
|= HighBits
; // New bits are known zero.
1885 } else if (KnownOne
.intersects(SignBit
)) {
1886 KnownOne
|= HighBits
; // New bits are known one.
1890 case ISD::SIGN_EXTEND_INREG
: {
1891 EVT EVT
= cast
<VTSDNode
>(Op
.getOperand(1))->getVT();
1892 unsigned EBits
= EVT
.getScalarType().getSizeInBits();
1894 // Sign extension. Compute the demanded bits in the result that are not
1895 // present in the input.
1896 APInt NewBits
= APInt::getHighBitsSet(BitWidth
, BitWidth
- EBits
);
1898 APInt InSignBit
= APInt::getSignBit(EBits
);
1899 APInt InputDemandedBits
= APInt::getLowBitsSet(BitWidth
, EBits
);
1901 // If the sign extended bits are demanded, we know that the sign
1903 InSignBit
= InSignBit
.zext(BitWidth
);
1904 if (NewBits
.getBoolValue())
1905 InputDemandedBits
|= InSignBit
;
1907 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1908 KnownOne
&= InputDemandedBits
;
1909 KnownZero
&= InputDemandedBits
;
1910 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
1912 // If the sign bit of the input is known set or clear, then we know the
1913 // top bits of the result.
1914 if (KnownZero
.intersects(InSignBit
)) { // Input sign bit known clear
1915 KnownZero
|= NewBits
;
1916 KnownOne
&= ~NewBits
;
1917 } else if (KnownOne
.intersects(InSignBit
)) { // Input sign bit known set
1918 KnownOne
|= NewBits
;
1919 KnownZero
&= ~NewBits
;
1920 } else { // Input sign bit unknown
1921 KnownZero
&= ~NewBits
;
1922 KnownOne
&= ~NewBits
;
1927 case ISD::CTTZ_ZERO_UNDEF
:
1929 case ISD::CTLZ_ZERO_UNDEF
:
1931 unsigned LowBits
= Log2_32(BitWidth
)+1;
1932 KnownZero
= APInt::getHighBitsSet(BitWidth
, BitWidth
- LowBits
);
1933 KnownOne
.clearAllBits();
1937 LoadSDNode
*LD
= cast
<LoadSDNode
>(Op
);
1938 if (ISD::isZEXTLoad(Op
.getNode())) {
1939 EVT VT
= LD
->getMemoryVT();
1940 unsigned MemBits
= VT
.getScalarType().getSizeInBits();
1941 KnownZero
|= APInt::getHighBitsSet(BitWidth
, BitWidth
- MemBits
);
1942 } else if (const MDNode
*Ranges
= LD
->getRanges()) {
1943 computeMaskedBitsLoad(*Ranges
, KnownZero
);
1947 case ISD::ZERO_EXTEND
: {
1948 EVT InVT
= Op
.getOperand(0).getValueType();
1949 unsigned InBits
= InVT
.getScalarType().getSizeInBits();
1950 APInt NewBits
= APInt::getHighBitsSet(BitWidth
, BitWidth
- InBits
);
1951 KnownZero
= KnownZero
.trunc(InBits
);
1952 KnownOne
= KnownOne
.trunc(InBits
);
1953 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1954 KnownZero
= KnownZero
.zext(BitWidth
);
1955 KnownOne
= KnownOne
.zext(BitWidth
);
1956 KnownZero
|= NewBits
;
1959 case ISD::SIGN_EXTEND
: {
1960 EVT InVT
= Op
.getOperand(0).getValueType();
1961 unsigned InBits
= InVT
.getScalarType().getSizeInBits();
1962 APInt InSignBit
= APInt::getSignBit(InBits
);
1963 APInt NewBits
= APInt::getHighBitsSet(BitWidth
, BitWidth
- InBits
);
1965 KnownZero
= KnownZero
.trunc(InBits
);
1966 KnownOne
= KnownOne
.trunc(InBits
);
1967 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1969 // Note if the sign bit is known to be zero or one.
1970 bool SignBitKnownZero
= KnownZero
.isNegative();
1971 bool SignBitKnownOne
= KnownOne
.isNegative();
1972 assert(!(SignBitKnownZero
&& SignBitKnownOne
) &&
1973 "Sign bit can't be known to be both zero and one!");
1975 KnownZero
= KnownZero
.zext(BitWidth
);
1976 KnownOne
= KnownOne
.zext(BitWidth
);
1978 // If the sign bit is known zero or one, the top bits match.
1979 if (SignBitKnownZero
)
1980 KnownZero
|= NewBits
;
1981 else if (SignBitKnownOne
)
1982 KnownOne
|= NewBits
;
1985 case ISD::ANY_EXTEND
: {
1986 EVT InVT
= Op
.getOperand(0).getValueType();
1987 unsigned InBits
= InVT
.getScalarType().getSizeInBits();
1988 KnownZero
= KnownZero
.trunc(InBits
);
1989 KnownOne
= KnownOne
.trunc(InBits
);
1990 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
1991 KnownZero
= KnownZero
.zext(BitWidth
);
1992 KnownOne
= KnownOne
.zext(BitWidth
);
1995 case ISD::TRUNCATE
: {
1996 EVT InVT
= Op
.getOperand(0).getValueType();
1997 unsigned InBits
= InVT
.getScalarType().getSizeInBits();
1998 KnownZero
= KnownZero
.zext(InBits
);
1999 KnownOne
= KnownOne
.zext(InBits
);
2000 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
2001 assert((KnownZero
& KnownOne
) == 0 && "Bits known to be one AND zero?");
2002 KnownZero
= KnownZero
.trunc(BitWidth
);
2003 KnownOne
= KnownOne
.trunc(BitWidth
);
2006 case ISD::AssertZext
: {
2007 EVT VT
= cast
<VTSDNode
>(Op
.getOperand(1))->getVT();
2008 APInt InMask
= APInt::getLowBitsSet(BitWidth
, VT
.getSizeInBits());
2009 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
2010 KnownZero
|= (~InMask
);
2011 KnownOne
&= (~KnownZero
);
2015 // All bits are zero except the low bit.
2016 KnownZero
= APInt::getHighBitsSet(BitWidth
, BitWidth
- 1);
2020 if (ConstantSDNode
*CLHS
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(0))) {
2021 // We know that the top bits of C-X are clear if X contains less bits
2022 // than C (i.e. no wrap-around can happen). For example, 20-X is
2023 // positive if we can prove that X is >= 0 and < 16.
2024 if (CLHS
->getAPIntValue().isNonNegative()) {
2025 unsigned NLZ
= (CLHS
->getAPIntValue()+1).countLeadingZeros();
2026 // NLZ can't be BitWidth with no sign bit
2027 APInt MaskV
= APInt::getHighBitsSet(BitWidth
, NLZ
+1);
2028 ComputeMaskedBits(Op
.getOperand(1), KnownZero2
, KnownOne2
, Depth
+1);
2030 // If all of the MaskV bits are known to be zero, then we know the
2031 // output top bits are zero, because we now know that the output is
2033 if ((KnownZero2
& MaskV
) == MaskV
) {
2034 unsigned NLZ2
= CLHS
->getAPIntValue().countLeadingZeros();
2035 // Top bits known zero.
2036 KnownZero
= APInt::getHighBitsSet(BitWidth
, NLZ2
);
2044 // Output known-0 bits are known if clear or set in both the low clear bits
2045 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2046 // low 3 bits clear.
2047 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
, KnownOne2
, Depth
+1);
2048 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
2049 unsigned KnownZeroOut
= KnownZero2
.countTrailingOnes();
2051 ComputeMaskedBits(Op
.getOperand(1), KnownZero2
, KnownOne2
, Depth
+1);
2052 assert((KnownZero2
& KnownOne2
) == 0 && "Bits known to be one AND zero?");
2053 KnownZeroOut
= std::min(KnownZeroOut
,
2054 KnownZero2
.countTrailingOnes());
2056 if (Op
.getOpcode() == ISD::ADD
) {
2057 KnownZero
|= APInt::getLowBitsSet(BitWidth
, KnownZeroOut
);
2061 // With ADDE, a carry bit may be added in, so we can only use this
2062 // information if we know (at least) that the low two bits are clear. We
2063 // then return to the caller that the low bit is unknown but that other bits
2065 if (KnownZeroOut
>= 2) // ADDE
2066 KnownZero
|= APInt::getBitsSet(BitWidth
, 1, KnownZeroOut
);
2070 if (ConstantSDNode
*Rem
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
2071 const APInt
&RA
= Rem
->getAPIntValue().abs();
2072 if (RA
.isPowerOf2()) {
2073 APInt LowBits
= RA
- 1;
2074 APInt Mask2
= LowBits
| APInt::getSignBit(BitWidth
);
2075 ComputeMaskedBits(Op
.getOperand(0), KnownZero2
,KnownOne2
,Depth
+1);
2077 // The low bits of the first operand are unchanged by the srem.
2078 KnownZero
= KnownZero2
& LowBits
;
2079 KnownOne
= KnownOne2
& LowBits
;
2081 // If the first operand is non-negative or has all low bits zero, then
2082 // the upper bits are all zero.
2083 if (KnownZero2
[BitWidth
-1] || ((KnownZero2
& LowBits
) == LowBits
))
2084 KnownZero
|= ~LowBits
;
2086 // If the first operand is negative and not all low bits are zero, then
2087 // the upper bits are all one.
2088 if (KnownOne2
[BitWidth
-1] && ((KnownOne2
& LowBits
) != 0))
2089 KnownOne
|= ~LowBits
;
2090 assert((KnownZero
& KnownOne
) == 0&&"Bits known to be one AND zero?");
2095 if (ConstantSDNode
*Rem
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
2096 const APInt
&RA
= Rem
->getAPIntValue();
2097 if (RA
.isPowerOf2()) {
2098 APInt LowBits
= (RA
- 1);
2099 KnownZero
|= ~LowBits
;
2100 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
,Depth
+1);
2101 assert((KnownZero
& KnownOne
) == 0&&"Bits known to be one AND zero?");
2106 // Since the result is less than or equal to either operand, any leading
2107 // zero bits in either operand must also exist in the result.
2108 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
2109 ComputeMaskedBits(Op
.getOperand(1), KnownZero2
, KnownOne2
, Depth
+1);
2111 uint32_t Leaders
= std::max(KnownZero
.countLeadingOnes(),
2112 KnownZero2
.countLeadingOnes());
2113 KnownOne
.clearAllBits();
2114 KnownZero
= APInt::getHighBitsSet(BitWidth
, Leaders
);
2117 case ISD::FrameIndex
:
2118 case ISD::TargetFrameIndex
:
2119 if (unsigned Align
= InferPtrAlignment(Op
)) {
2120 // The low bits are known zero if the pointer is aligned.
2121 KnownZero
= APInt::getLowBitsSet(BitWidth
, Log2_32(Align
));
2127 if (Op
.getOpcode() < ISD::BUILTIN_OP_END
)
2130 case ISD::INTRINSIC_WO_CHAIN
:
2131 case ISD::INTRINSIC_W_CHAIN
:
2132 case ISD::INTRINSIC_VOID
:
2133 // Allow the target to implement this method for its nodes.
2134 TLI
.computeMaskedBitsForTargetNode(Op
, KnownZero
, KnownOne
, *this, Depth
);
2139 /// ComputeNumSignBits - Return the number of times the sign bit of the
2140 /// register is replicated into the other bits. We know that at least 1 bit
2141 /// is always equal to the sign bit (itself), but other cases can give us
2142 /// information. For example, immediately after an "SRA X, 2", we know that
2143 /// the top 3 bits are all equal to each other, so we return 3.
2144 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op
, unsigned Depth
) const{
2145 EVT VT
= Op
.getValueType();
2146 assert(VT
.isInteger() && "Invalid VT!");
2147 unsigned VTBits
= VT
.getScalarType().getSizeInBits();
2149 unsigned FirstAnswer
= 1;
2152 return 1; // Limit search depth.
2154 switch (Op
.getOpcode()) {
2156 case ISD::AssertSext
:
2157 Tmp
= cast
<VTSDNode
>(Op
.getOperand(1))->getVT().getSizeInBits();
2158 return VTBits
-Tmp
+1;
2159 case ISD::AssertZext
:
2160 Tmp
= cast
<VTSDNode
>(Op
.getOperand(1))->getVT().getSizeInBits();
2163 case ISD::Constant
: {
2164 const APInt
&Val
= cast
<ConstantSDNode
>(Op
)->getAPIntValue();
2165 return Val
.getNumSignBits();
2168 case ISD::SIGN_EXTEND
:
2169 Tmp
= VTBits
-Op
.getOperand(0).getValueType().getScalarType().getSizeInBits();
2170 return ComputeNumSignBits(Op
.getOperand(0), Depth
+1) + Tmp
;
2172 case ISD::SIGN_EXTEND_INREG
:
2173 // Max of the input and what this extends.
2175 cast
<VTSDNode
>(Op
.getOperand(1))->getVT().getScalarType().getSizeInBits();
2178 Tmp2
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2179 return std::max(Tmp
, Tmp2
);
2182 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2183 // SRA X, C -> adds C sign bits.
2184 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
2185 Tmp
+= C
->getZExtValue();
2186 if (Tmp
> VTBits
) Tmp
= VTBits
;
2190 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
2191 // shl destroys sign bits.
2192 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2193 if (C
->getZExtValue() >= VTBits
|| // Bad shift.
2194 C
->getZExtValue() >= Tmp
) break; // Shifted all sign bits out.
2195 return Tmp
- C
->getZExtValue();
2200 case ISD::XOR
: // NOT is handled here.
2201 // Logical binary ops preserve the number of sign bits at the worst.
2202 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2204 Tmp2
= ComputeNumSignBits(Op
.getOperand(1), Depth
+1);
2205 FirstAnswer
= std::min(Tmp
, Tmp2
);
2206 // We computed what we know about the sign bits as our first
2207 // answer. Now proceed to the generic code that uses
2208 // ComputeMaskedBits, and pick whichever answer is better.
2213 Tmp
= ComputeNumSignBits(Op
.getOperand(1), Depth
+1);
2214 if (Tmp
== 1) return 1; // Early out.
2215 Tmp2
= ComputeNumSignBits(Op
.getOperand(2), Depth
+1);
2216 return std::min(Tmp
, Tmp2
);
2224 if (Op
.getResNo() != 1)
2226 // The boolean result conforms to getBooleanContents. Fall through.
2228 // If setcc returns 0/-1, all bits are sign bits.
2229 if (TLI
.getBooleanContents(Op
.getValueType().isVector()) ==
2230 TargetLowering::ZeroOrNegativeOneBooleanContent
)
2235 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1))) {
2236 unsigned RotAmt
= C
->getZExtValue() & (VTBits
-1);
2238 // Handle rotate right by N like a rotate left by 32-N.
2239 if (Op
.getOpcode() == ISD::ROTR
)
2240 RotAmt
= (VTBits
-RotAmt
) & (VTBits
-1);
2242 // If we aren't rotating out all of the known-in sign bits, return the
2243 // number that are left. This handles rotl(sext(x), 1) for example.
2244 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2245 if (Tmp
> RotAmt
+1) return Tmp
-RotAmt
;
2249 // Add can have at most one carry bit. Thus we know that the output
2250 // is, at worst, one more bit than the inputs.
2251 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2252 if (Tmp
== 1) return 1; // Early out.
2254 // Special case decrementing a value (ADD X, -1):
2255 if (ConstantSDNode
*CRHS
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1)))
2256 if (CRHS
->isAllOnesValue()) {
2257 APInt KnownZero
, KnownOne
;
2258 ComputeMaskedBits(Op
.getOperand(0), KnownZero
, KnownOne
, Depth
+1);
2260 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2262 if ((KnownZero
| APInt(VTBits
, 1)).isAllOnesValue())
2265 // If we are subtracting one from a positive number, there is no carry
2266 // out of the result.
2267 if (KnownZero
.isNegative())
2271 Tmp2
= ComputeNumSignBits(Op
.getOperand(1), Depth
+1);
2272 if (Tmp2
== 1) return 1;
2273 return std::min(Tmp
, Tmp2
)-1;
2276 Tmp2
= ComputeNumSignBits(Op
.getOperand(1), Depth
+1);
2277 if (Tmp2
== 1) return 1;
2280 if (ConstantSDNode
*CLHS
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(0)))
2281 if (CLHS
->isNullValue()) {
2282 APInt KnownZero
, KnownOne
;
2283 ComputeMaskedBits(Op
.getOperand(1), KnownZero
, KnownOne
, Depth
+1);
2284 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2286 if ((KnownZero
| APInt(VTBits
, 1)).isAllOnesValue())
2289 // If the input is known to be positive (the sign bit is known clear),
2290 // the output of the NEG has the same number of sign bits as the input.
2291 if (KnownZero
.isNegative())
2294 // Otherwise, we treat this like a SUB.
2297 // Sub can have at most one carry bit. Thus we know that the output
2298 // is, at worst, one more bit than the inputs.
2299 Tmp
= ComputeNumSignBits(Op
.getOperand(0), Depth
+1);
2300 if (Tmp
== 1) return 1; // Early out.
2301 return std::min(Tmp
, Tmp2
)-1;
2303 // FIXME: it's tricky to do anything useful for this, but it is an important
2304 // case for targets like X86.
2308 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2309 if (LoadSDNode
*LD
= dyn_cast
<LoadSDNode
>(Op
)) {
2310 unsigned ExtType
= LD
->getExtensionType();
2313 case ISD::SEXTLOAD
: // '17' bits known
2314 Tmp
= LD
->getMemoryVT().getScalarType().getSizeInBits();
2315 return VTBits
-Tmp
+1;
2316 case ISD::ZEXTLOAD
: // '16' bits known
2317 Tmp
= LD
->getMemoryVT().getScalarType().getSizeInBits();
2322 // Allow the target to implement this method for its nodes.
2323 if (Op
.getOpcode() >= ISD::BUILTIN_OP_END
||
2324 Op
.getOpcode() == ISD::INTRINSIC_WO_CHAIN
||
2325 Op
.getOpcode() == ISD::INTRINSIC_W_CHAIN
||
2326 Op
.getOpcode() == ISD::INTRINSIC_VOID
) {
2327 unsigned NumBits
= TLI
.ComputeNumSignBitsForTargetNode(Op
, Depth
);
2328 if (NumBits
> 1) FirstAnswer
= std::max(FirstAnswer
, NumBits
);
2331 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2332 // use this information.
2333 APInt KnownZero
, KnownOne
;
2334 ComputeMaskedBits(Op
, KnownZero
, KnownOne
, Depth
);
2337 if (KnownZero
.isNegative()) { // sign bit is 0
2339 } else if (KnownOne
.isNegative()) { // sign bit is 1;
2346 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2347 // the number of identical bits in the top of the input value.
2349 Mask
<<= Mask
.getBitWidth()-VTBits
;
2350 // Return # leading zeros. We use 'min' here in case Val was zero before
2351 // shifting. We don't want to return '64' as for an i32 "0".
2352 return std::max(FirstAnswer
, std::min(VTBits
, Mask
.countLeadingZeros()));
2355 /// isBaseWithConstantOffset - Return true if the specified operand is an
2356 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2357 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2358 /// semantics as an ADD. This handles the equivalence:
2359 /// X|Cst == X+Cst iff X&Cst = 0.
2360 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op
) const {
2361 if ((Op
.getOpcode() != ISD::ADD
&& Op
.getOpcode() != ISD::OR
) ||
2362 !isa
<ConstantSDNode
>(Op
.getOperand(1)))
2365 if (Op
.getOpcode() == ISD::OR
&&
2366 !MaskedValueIsZero(Op
.getOperand(0),
2367 cast
<ConstantSDNode
>(Op
.getOperand(1))->getAPIntValue()))
2374 bool SelectionDAG::isKnownNeverNaN(SDValue Op
) const {
2375 // If we're told that NaNs won't happen, assume they won't.
2376 if (getTarget().Options
.NoNaNsFPMath
)
2379 // If the value is a constant, we can obviously see if it is a NaN or not.
2380 if (const ConstantFPSDNode
*C
= dyn_cast
<ConstantFPSDNode
>(Op
))
2381 return !C
->getValueAPF().isNaN();
2383 // TODO: Recognize more cases here.
2388 bool SelectionDAG::isKnownNeverZero(SDValue Op
) const {
2389 // If the value is a constant, we can obviously see if it is a zero or not.
2390 if (const ConstantFPSDNode
*C
= dyn_cast
<ConstantFPSDNode
>(Op
))
2391 return !C
->isZero();
2393 // TODO: Recognize more cases here.
2394 switch (Op
.getOpcode()) {
2397 if (const ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Op
.getOperand(1)))
2398 return !C
->isNullValue();
2405 bool SelectionDAG::isEqualTo(SDValue A
, SDValue B
) const {
2406 // Check the obvious case.
2407 if (A
== B
) return true;
2409 // For for negative and positive zero.
2410 if (const ConstantFPSDNode
*CA
= dyn_cast
<ConstantFPSDNode
>(A
))
2411 if (const ConstantFPSDNode
*CB
= dyn_cast
<ConstantFPSDNode
>(B
))
2412 if (CA
->isZero() && CB
->isZero()) return true;
2414 // Otherwise they may not be equal.
2418 /// getNode - Gets or creates the specified node.
2420 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
) {
2421 FoldingSetNodeID ID
;
2422 AddNodeIDNode(ID
, Opcode
, getVTList(VT
), 0, 0);
2424 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
2425 return SDValue(E
, 0);
2427 SDNode
*N
= new (NodeAllocator
) SDNode(Opcode
, DL
, getVTList(VT
));
2428 CSEMap
.InsertNode(N
, IP
);
2430 AllNodes
.push_back(N
);
2434 return SDValue(N
, 0);
2437 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
,
2438 EVT VT
, SDValue Operand
) {
2439 // Constant fold unary operations with an integer constant operand.
2440 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Operand
.getNode())) {
2441 const APInt
&Val
= C
->getAPIntValue();
2444 case ISD::SIGN_EXTEND
:
2445 return getConstant(Val
.sextOrTrunc(VT
.getSizeInBits()), VT
);
2446 case ISD::ANY_EXTEND
:
2447 case ISD::ZERO_EXTEND
:
2449 return getConstant(Val
.zextOrTrunc(VT
.getSizeInBits()), VT
);
2450 case ISD::UINT_TO_FP
:
2451 case ISD::SINT_TO_FP
: {
2452 // No compile time operations on ppcf128.
2453 if (VT
== MVT::ppcf128
) break;
2454 APFloat
apf(APInt::getNullValue(VT
.getSizeInBits()));
2455 (void)apf
.convertFromAPInt(Val
,
2456 Opcode
==ISD::SINT_TO_FP
,
2457 APFloat::rmNearestTiesToEven
);
2458 return getConstantFP(apf
, VT
);
2461 if (VT
== MVT::f32
&& C
->getValueType(0) == MVT::i32
)
2462 return getConstantFP(APFloat(Val
), VT
);
2463 else if (VT
== MVT::f64
&& C
->getValueType(0) == MVT::i64
)
2464 return getConstantFP(APFloat(Val
), VT
);
2467 return getConstant(Val
.byteSwap(), VT
);
2469 return getConstant(Val
.countPopulation(), VT
);
2471 case ISD::CTLZ_ZERO_UNDEF
:
2472 return getConstant(Val
.countLeadingZeros(), VT
);
2474 case ISD::CTTZ_ZERO_UNDEF
:
2475 return getConstant(Val
.countTrailingZeros(), VT
);
2479 // Constant fold unary operations with a floating point constant operand.
2480 if (ConstantFPSDNode
*C
= dyn_cast
<ConstantFPSDNode
>(Operand
.getNode())) {
2481 APFloat V
= C
->getValueAPF(); // make copy
2482 if (VT
!= MVT::ppcf128
&& Operand
.getValueType() != MVT::ppcf128
) {
2486 return getConstantFP(V
, VT
);
2489 return getConstantFP(V
, VT
);
2491 APFloat::opStatus fs
= V
.roundToIntegral(APFloat::rmTowardPositive
);
2492 if (fs
== APFloat::opOK
|| fs
== APFloat::opInexact
)
2493 return getConstantFP(V
, VT
);
2497 APFloat::opStatus fs
= V
.roundToIntegral(APFloat::rmTowardZero
);
2498 if (fs
== APFloat::opOK
|| fs
== APFloat::opInexact
)
2499 return getConstantFP(V
, VT
);
2503 APFloat::opStatus fs
= V
.roundToIntegral(APFloat::rmTowardNegative
);
2504 if (fs
== APFloat::opOK
|| fs
== APFloat::opInexact
)
2505 return getConstantFP(V
, VT
);
2508 case ISD::FP_EXTEND
: {
2510 // This can return overflow, underflow, or inexact; we don't care.
2511 // FIXME need to be more flexible about rounding mode.
2512 (void)V
.convert(*EVTToAPFloatSemantics(VT
),
2513 APFloat::rmNearestTiesToEven
, &ignored
);
2514 return getConstantFP(V
, VT
);
2516 case ISD::FP_TO_SINT
:
2517 case ISD::FP_TO_UINT
: {
2520 assert(integerPartWidth
>= 64);
2521 // FIXME need to be more flexible about rounding mode.
2522 APFloat::opStatus s
= V
.convertToInteger(x
, VT
.getSizeInBits(),
2523 Opcode
==ISD::FP_TO_SINT
,
2524 APFloat::rmTowardZero
, &ignored
);
2525 if (s
==APFloat::opInvalidOp
) // inexact is OK, in fact usual
2527 APInt
api(VT
.getSizeInBits(), x
);
2528 return getConstant(api
, VT
);
2531 if (VT
== MVT::i32
&& C
->getValueType(0) == MVT::f32
)
2532 return getConstant((uint32_t)V
.bitcastToAPInt().getZExtValue(), VT
);
2533 else if (VT
== MVT::i64
&& C
->getValueType(0) == MVT::f64
)
2534 return getConstant(V
.bitcastToAPInt().getZExtValue(), VT
);
2540 unsigned OpOpcode
= Operand
.getNode()->getOpcode();
2542 case ISD::TokenFactor
:
2543 case ISD::MERGE_VALUES
:
2544 case ISD::CONCAT_VECTORS
:
2545 return Operand
; // Factor, merge or concat of one node? No need.
2546 case ISD::FP_ROUND
: llvm_unreachable("Invalid method to make FP_ROUND node");
2547 case ISD::FP_EXTEND
:
2548 assert(VT
.isFloatingPoint() &&
2549 Operand
.getValueType().isFloatingPoint() && "Invalid FP cast!");
2550 if (Operand
.getValueType() == VT
) return Operand
; // noop conversion.
2551 assert((!VT
.isVector() ||
2552 VT
.getVectorNumElements() ==
2553 Operand
.getValueType().getVectorNumElements()) &&
2554 "Vector element count mismatch!");
2555 if (Operand
.getOpcode() == ISD::UNDEF
)
2556 return getUNDEF(VT
);
2558 case ISD::SIGN_EXTEND
:
2559 assert(VT
.isInteger() && Operand
.getValueType().isInteger() &&
2560 "Invalid SIGN_EXTEND!");
2561 if (Operand
.getValueType() == VT
) return Operand
; // noop extension
2562 assert(Operand
.getValueType().getScalarType().bitsLT(VT
.getScalarType()) &&
2563 "Invalid sext node, dst < src!");
2564 assert((!VT
.isVector() ||
2565 VT
.getVectorNumElements() ==
2566 Operand
.getValueType().getVectorNumElements()) &&
2567 "Vector element count mismatch!");
2568 if (OpOpcode
== ISD::SIGN_EXTEND
|| OpOpcode
== ISD::ZERO_EXTEND
)
2569 return getNode(OpOpcode
, DL
, VT
, Operand
.getNode()->getOperand(0));
2570 else if (OpOpcode
== ISD::UNDEF
)
2571 // sext(undef) = 0, because the top bits will all be the same.
2572 return getConstant(0, VT
);
2574 case ISD::ZERO_EXTEND
:
2575 assert(VT
.isInteger() && Operand
.getValueType().isInteger() &&
2576 "Invalid ZERO_EXTEND!");
2577 if (Operand
.getValueType() == VT
) return Operand
; // noop extension
2578 assert(Operand
.getValueType().getScalarType().bitsLT(VT
.getScalarType()) &&
2579 "Invalid zext node, dst < src!");
2580 assert((!VT
.isVector() ||
2581 VT
.getVectorNumElements() ==
2582 Operand
.getValueType().getVectorNumElements()) &&
2583 "Vector element count mismatch!");
2584 if (OpOpcode
== ISD::ZERO_EXTEND
) // (zext (zext x)) -> (zext x)
2585 return getNode(ISD::ZERO_EXTEND
, DL
, VT
,
2586 Operand
.getNode()->getOperand(0));
2587 else if (OpOpcode
== ISD::UNDEF
)
2588 // zext(undef) = 0, because the top bits will be zero.
2589 return getConstant(0, VT
);
2591 case ISD::ANY_EXTEND
:
2592 assert(VT
.isInteger() && Operand
.getValueType().isInteger() &&
2593 "Invalid ANY_EXTEND!");
2594 if (Operand
.getValueType() == VT
) return Operand
; // noop extension
2595 assert(Operand
.getValueType().getScalarType().bitsLT(VT
.getScalarType()) &&
2596 "Invalid anyext node, dst < src!");
2597 assert((!VT
.isVector() ||
2598 VT
.getVectorNumElements() ==
2599 Operand
.getValueType().getVectorNumElements()) &&
2600 "Vector element count mismatch!");
2602 if (OpOpcode
== ISD::ZERO_EXTEND
|| OpOpcode
== ISD::SIGN_EXTEND
||
2603 OpOpcode
== ISD::ANY_EXTEND
)
2604 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2605 return getNode(OpOpcode
, DL
, VT
, Operand
.getNode()->getOperand(0));
2606 else if (OpOpcode
== ISD::UNDEF
)
2607 return getUNDEF(VT
);
2609 // (ext (trunx x)) -> x
2610 if (OpOpcode
== ISD::TRUNCATE
) {
2611 SDValue OpOp
= Operand
.getNode()->getOperand(0);
2612 if (OpOp
.getValueType() == VT
)
2617 assert(VT
.isInteger() && Operand
.getValueType().isInteger() &&
2618 "Invalid TRUNCATE!");
2619 if (Operand
.getValueType() == VT
) return Operand
; // noop truncate
2620 assert(Operand
.getValueType().getScalarType().bitsGT(VT
.getScalarType()) &&
2621 "Invalid truncate node, src < dst!");
2622 assert((!VT
.isVector() ||
2623 VT
.getVectorNumElements() ==
2624 Operand
.getValueType().getVectorNumElements()) &&
2625 "Vector element count mismatch!");
2626 if (OpOpcode
== ISD::TRUNCATE
)
2627 return getNode(ISD::TRUNCATE
, DL
, VT
, Operand
.getNode()->getOperand(0));
2628 if (OpOpcode
== ISD::ZERO_EXTEND
|| OpOpcode
== ISD::SIGN_EXTEND
||
2629 OpOpcode
== ISD::ANY_EXTEND
) {
2630 // If the source is smaller than the dest, we still need an extend.
2631 if (Operand
.getNode()->getOperand(0).getValueType().getScalarType()
2632 .bitsLT(VT
.getScalarType()))
2633 return getNode(OpOpcode
, DL
, VT
, Operand
.getNode()->getOperand(0));
2634 if (Operand
.getNode()->getOperand(0).getValueType().bitsGT(VT
))
2635 return getNode(ISD::TRUNCATE
, DL
, VT
, Operand
.getNode()->getOperand(0));
2636 return Operand
.getNode()->getOperand(0);
2638 if (OpOpcode
== ISD::UNDEF
)
2639 return getUNDEF(VT
);
2642 // Basic sanity checking.
2643 assert(VT
.getSizeInBits() == Operand
.getValueType().getSizeInBits()
2644 && "Cannot BITCAST between types of different sizes!");
2645 if (VT
== Operand
.getValueType()) return Operand
; // noop conversion.
2646 if (OpOpcode
== ISD::BITCAST
) // bitconv(bitconv(x)) -> bitconv(x)
2647 return getNode(ISD::BITCAST
, DL
, VT
, Operand
.getOperand(0));
2648 if (OpOpcode
== ISD::UNDEF
)
2649 return getUNDEF(VT
);
2651 case ISD::SCALAR_TO_VECTOR
:
2652 assert(VT
.isVector() && !Operand
.getValueType().isVector() &&
2653 (VT
.getVectorElementType() == Operand
.getValueType() ||
2654 (VT
.getVectorElementType().isInteger() &&
2655 Operand
.getValueType().isInteger() &&
2656 VT
.getVectorElementType().bitsLE(Operand
.getValueType()))) &&
2657 "Illegal SCALAR_TO_VECTOR node!");
2658 if (OpOpcode
== ISD::UNDEF
)
2659 return getUNDEF(VT
);
2660 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2661 if (OpOpcode
== ISD::EXTRACT_VECTOR_ELT
&&
2662 isa
<ConstantSDNode
>(Operand
.getOperand(1)) &&
2663 Operand
.getConstantOperandVal(1) == 0 &&
2664 Operand
.getOperand(0).getValueType() == VT
)
2665 return Operand
.getOperand(0);
2668 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2669 if (getTarget().Options
.UnsafeFPMath
&& OpOpcode
== ISD::FSUB
)
2670 return getNode(ISD::FSUB
, DL
, VT
, Operand
.getNode()->getOperand(1),
2671 Operand
.getNode()->getOperand(0));
2672 if (OpOpcode
== ISD::FNEG
) // --X -> X
2673 return Operand
.getNode()->getOperand(0);
2676 if (OpOpcode
== ISD::FNEG
) // abs(-X) -> abs(X)
2677 return getNode(ISD::FABS
, DL
, VT
, Operand
.getNode()->getOperand(0));
2682 SDVTList VTs
= getVTList(VT
);
2683 if (VT
!= MVT::Glue
) { // Don't CSE flag producing nodes
2684 FoldingSetNodeID ID
;
2685 SDValue Ops
[1] = { Operand
};
2686 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 1);
2688 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
2689 return SDValue(E
, 0);
2691 N
= new (NodeAllocator
) UnarySDNode(Opcode
, DL
, VTs
, Operand
);
2692 CSEMap
.InsertNode(N
, IP
);
2694 N
= new (NodeAllocator
) UnarySDNode(Opcode
, DL
, VTs
, Operand
);
2697 AllNodes
.push_back(N
);
2701 return SDValue(N
, 0);
2704 SDValue
SelectionDAG::FoldConstantArithmetic(unsigned Opcode
,
2706 ConstantSDNode
*Cst1
,
2707 ConstantSDNode
*Cst2
) {
2708 const APInt
&C1
= Cst1
->getAPIntValue(), &C2
= Cst2
->getAPIntValue();
2711 case ISD::ADD
: return getConstant(C1
+ C2
, VT
);
2712 case ISD::SUB
: return getConstant(C1
- C2
, VT
);
2713 case ISD::MUL
: return getConstant(C1
* C2
, VT
);
2715 if (C2
.getBoolValue()) return getConstant(C1
.udiv(C2
), VT
);
2718 if (C2
.getBoolValue()) return getConstant(C1
.urem(C2
), VT
);
2721 if (C2
.getBoolValue()) return getConstant(C1
.sdiv(C2
), VT
);
2724 if (C2
.getBoolValue()) return getConstant(C1
.srem(C2
), VT
);
2726 case ISD::AND
: return getConstant(C1
& C2
, VT
);
2727 case ISD::OR
: return getConstant(C1
| C2
, VT
);
2728 case ISD::XOR
: return getConstant(C1
^ C2
, VT
);
2729 case ISD::SHL
: return getConstant(C1
<< C2
, VT
);
2730 case ISD::SRL
: return getConstant(C1
.lshr(C2
), VT
);
2731 case ISD::SRA
: return getConstant(C1
.ashr(C2
), VT
);
2732 case ISD::ROTL
: return getConstant(C1
.rotl(C2
), VT
);
2733 case ISD::ROTR
: return getConstant(C1
.rotr(C2
), VT
);
2740 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
2741 SDValue N1
, SDValue N2
) {
2742 ConstantSDNode
*N1C
= dyn_cast
<ConstantSDNode
>(N1
.getNode());
2743 ConstantSDNode
*N2C
= dyn_cast
<ConstantSDNode
>(N2
.getNode());
2746 case ISD::TokenFactor
:
2747 assert(VT
== MVT::Other
&& N1
.getValueType() == MVT::Other
&&
2748 N2
.getValueType() == MVT::Other
&& "Invalid token factor!");
2749 // Fold trivial token factors.
2750 if (N1
.getOpcode() == ISD::EntryToken
) return N2
;
2751 if (N2
.getOpcode() == ISD::EntryToken
) return N1
;
2752 if (N1
== N2
) return N1
;
2754 case ISD::CONCAT_VECTORS
:
2755 // Concat of UNDEFs is UNDEF.
2756 if (N1
.getOpcode() == ISD::UNDEF
&&
2757 N2
.getOpcode() == ISD::UNDEF
)
2758 return getUNDEF(VT
);
2760 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2761 // one big BUILD_VECTOR.
2762 if (N1
.getOpcode() == ISD::BUILD_VECTOR
&&
2763 N2
.getOpcode() == ISD::BUILD_VECTOR
) {
2764 SmallVector
<SDValue
, 16> Elts(N1
.getNode()->op_begin(),
2765 N1
.getNode()->op_end());
2766 Elts
.append(N2
.getNode()->op_begin(), N2
.getNode()->op_end());
2767 return getNode(ISD::BUILD_VECTOR
, DL
, VT
, &Elts
[0], Elts
.size());
2771 assert(VT
.isInteger() && "This operator does not apply to FP types!");
2772 assert(N1
.getValueType() == N2
.getValueType() &&
2773 N1
.getValueType() == VT
&& "Binary operator types must match!");
2774 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2775 // worth handling here.
2776 if (N2C
&& N2C
->isNullValue())
2778 if (N2C
&& N2C
->isAllOnesValue()) // X & -1 -> X
2785 assert(VT
.isInteger() && "This operator does not apply to FP types!");
2786 assert(N1
.getValueType() == N2
.getValueType() &&
2787 N1
.getValueType() == VT
&& "Binary operator types must match!");
2788 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2789 // it's worth handling here.
2790 if (N2C
&& N2C
->isNullValue())
2800 assert(VT
.isInteger() && "This operator does not apply to FP types!");
2801 assert(N1
.getValueType() == N2
.getValueType() &&
2802 N1
.getValueType() == VT
&& "Binary operator types must match!");
2809 if (getTarget().Options
.UnsafeFPMath
) {
2810 if (Opcode
== ISD::FADD
) {
2812 if (ConstantFPSDNode
*CFP
= dyn_cast
<ConstantFPSDNode
>(N1
))
2813 if (CFP
->getValueAPF().isZero())
2816 if (ConstantFPSDNode
*CFP
= dyn_cast
<ConstantFPSDNode
>(N2
))
2817 if (CFP
->getValueAPF().isZero())
2819 } else if (Opcode
== ISD::FSUB
) {
2821 if (ConstantFPSDNode
*CFP
= dyn_cast
<ConstantFPSDNode
>(N2
))
2822 if (CFP
->getValueAPF().isZero())
2824 } else if (Opcode
== ISD::FMUL
) {
2825 ConstantFPSDNode
*CFP
= dyn_cast
<ConstantFPSDNode
>(N1
);
2828 // If the first operand isn't the constant, try the second
2830 CFP
= dyn_cast
<ConstantFPSDNode
>(N2
);
2837 return SDValue(CFP
,0);
2839 if (CFP
->isExactlyValue(1.0))
2844 assert(VT
.isFloatingPoint() && "This operator only applies to FP types!");
2845 assert(N1
.getValueType() == N2
.getValueType() &&
2846 N1
.getValueType() == VT
&& "Binary operator types must match!");
2848 case ISD::FCOPYSIGN
: // N1 and result must match. N1/N2 need not match.
2849 assert(N1
.getValueType() == VT
&&
2850 N1
.getValueType().isFloatingPoint() &&
2851 N2
.getValueType().isFloatingPoint() &&
2852 "Invalid FCOPYSIGN!");
2859 assert(VT
== N1
.getValueType() &&
2860 "Shift operators return type must be the same as their first arg");
2861 assert(VT
.isInteger() && N2
.getValueType().isInteger() &&
2862 "Shifts only work on integers");
2863 // Verify that the shift amount VT is bit enough to hold valid shift
2864 // amounts. This catches things like trying to shift an i1024 value by an
2865 // i8, which is easy to fall into in generic code that uses
2866 // TLI.getShiftAmount().
2867 assert(N2
.getValueType().getSizeInBits() >=
2868 Log2_32_Ceil(N1
.getValueType().getSizeInBits()) &&
2869 "Invalid use of small shift amount with oversized value!");
2871 // Always fold shifts of i1 values so the code generator doesn't need to
2872 // handle them. Since we know the size of the shift has to be less than the
2873 // size of the value, the shift/rotate count is guaranteed to be zero.
2876 if (N2C
&& N2C
->isNullValue())
2879 case ISD::FP_ROUND_INREG
: {
2880 EVT EVT
= cast
<VTSDNode
>(N2
)->getVT();
2881 assert(VT
== N1
.getValueType() && "Not an inreg round!");
2882 assert(VT
.isFloatingPoint() && EVT
.isFloatingPoint() &&
2883 "Cannot FP_ROUND_INREG integer types");
2884 assert(EVT
.isVector() == VT
.isVector() &&
2885 "FP_ROUND_INREG type should be vector iff the operand "
2887 assert((!EVT
.isVector() ||
2888 EVT
.getVectorNumElements() == VT
.getVectorNumElements()) &&
2889 "Vector element counts must match in FP_ROUND_INREG");
2890 assert(EVT
.bitsLE(VT
) && "Not rounding down!");
2892 if (cast
<VTSDNode
>(N2
)->getVT() == VT
) return N1
; // Not actually rounding.
2896 assert(VT
.isFloatingPoint() &&
2897 N1
.getValueType().isFloatingPoint() &&
2898 VT
.bitsLE(N1
.getValueType()) &&
2899 isa
<ConstantSDNode
>(N2
) && "Invalid FP_ROUND!");
2900 if (N1
.getValueType() == VT
) return N1
; // noop conversion.
2902 case ISD::AssertSext
:
2903 case ISD::AssertZext
: {
2904 EVT EVT
= cast
<VTSDNode
>(N2
)->getVT();
2905 assert(VT
== N1
.getValueType() && "Not an inreg extend!");
2906 assert(VT
.isInteger() && EVT
.isInteger() &&
2907 "Cannot *_EXTEND_INREG FP types");
2908 assert(!EVT
.isVector() &&
2909 "AssertSExt/AssertZExt type should be the vector element type "
2910 "rather than the vector type!");
2911 assert(EVT
.bitsLE(VT
) && "Not extending!");
2912 if (VT
== EVT
) return N1
; // noop assertion.
2915 case ISD::SIGN_EXTEND_INREG
: {
2916 EVT EVT
= cast
<VTSDNode
>(N2
)->getVT();
2917 assert(VT
== N1
.getValueType() && "Not an inreg extend!");
2918 assert(VT
.isInteger() && EVT
.isInteger() &&
2919 "Cannot *_EXTEND_INREG FP types");
2920 assert(EVT
.isVector() == VT
.isVector() &&
2921 "SIGN_EXTEND_INREG type should be vector iff the operand "
2923 assert((!EVT
.isVector() ||
2924 EVT
.getVectorNumElements() == VT
.getVectorNumElements()) &&
2925 "Vector element counts must match in SIGN_EXTEND_INREG");
2926 assert(EVT
.bitsLE(VT
) && "Not extending!");
2927 if (EVT
== VT
) return N1
; // Not actually extending
2930 APInt Val
= N1C
->getAPIntValue();
2931 unsigned FromBits
= EVT
.getScalarType().getSizeInBits();
2932 Val
<<= Val
.getBitWidth()-FromBits
;
2933 Val
= Val
.ashr(Val
.getBitWidth()-FromBits
);
2934 return getConstant(Val
, VT
);
2938 case ISD::EXTRACT_VECTOR_ELT
:
2939 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2940 if (N1
.getOpcode() == ISD::UNDEF
)
2941 return getUNDEF(VT
);
2943 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2944 // expanding copies of large vectors from registers.
2946 N1
.getOpcode() == ISD::CONCAT_VECTORS
&&
2947 N1
.getNumOperands() > 0) {
2949 N1
.getOperand(0).getValueType().getVectorNumElements();
2950 return getNode(ISD::EXTRACT_VECTOR_ELT
, DL
, VT
,
2951 N1
.getOperand(N2C
->getZExtValue() / Factor
),
2952 getConstant(N2C
->getZExtValue() % Factor
,
2953 N2
.getValueType()));
2956 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2957 // expanding large vector constants.
2958 if (N2C
&& N1
.getOpcode() == ISD::BUILD_VECTOR
) {
2959 SDValue Elt
= N1
.getOperand(N2C
->getZExtValue());
2961 if (VT
!= Elt
.getValueType())
2962 // If the vector element type is not legal, the BUILD_VECTOR operands
2963 // are promoted and implicitly truncated, and the result implicitly
2964 // extended. Make that explicit here.
2965 Elt
= getAnyExtOrTrunc(Elt
, DL
, VT
);
2970 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2971 // operations are lowered to scalars.
2972 if (N1
.getOpcode() == ISD::INSERT_VECTOR_ELT
) {
2973 // If the indices are the same, return the inserted element else
2974 // if the indices are known different, extract the element from
2975 // the original vector.
2976 SDValue N1Op2
= N1
.getOperand(2);
2977 ConstantSDNode
*N1Op2C
= dyn_cast
<ConstantSDNode
>(N1Op2
.getNode());
2979 if (N1Op2C
&& N2C
) {
2980 if (N1Op2C
->getZExtValue() == N2C
->getZExtValue()) {
2981 if (VT
== N1
.getOperand(1).getValueType())
2982 return N1
.getOperand(1);
2984 return getSExtOrTrunc(N1
.getOperand(1), DL
, VT
);
2987 return getNode(ISD::EXTRACT_VECTOR_ELT
, DL
, VT
, N1
.getOperand(0), N2
);
2991 case ISD::EXTRACT_ELEMENT
:
2992 assert(N2C
&& (unsigned)N2C
->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
2993 assert(!N1
.getValueType().isVector() && !VT
.isVector() &&
2994 (N1
.getValueType().isInteger() == VT
.isInteger()) &&
2995 N1
.getValueType() != VT
&&
2996 "Wrong types for EXTRACT_ELEMENT!");
2998 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2999 // 64-bit integers into 32-bit parts. Instead of building the extract of
3000 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3001 if (N1
.getOpcode() == ISD::BUILD_PAIR
)
3002 return N1
.getOperand(N2C
->getZExtValue());
3004 // EXTRACT_ELEMENT of a constant int is also very common.
3005 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(N1
)) {
3006 unsigned ElementSize
= VT
.getSizeInBits();
3007 unsigned Shift
= ElementSize
* N2C
->getZExtValue();
3008 APInt ShiftedVal
= C
->getAPIntValue().lshr(Shift
);
3009 return getConstant(ShiftedVal
.trunc(ElementSize
), VT
);
3012 case ISD::EXTRACT_SUBVECTOR
: {
3014 if (VT
.isSimple() && N1
.getValueType().isSimple()) {
3015 assert(VT
.isVector() && N1
.getValueType().isVector() &&
3016 "Extract subvector VTs must be a vectors!");
3017 assert(VT
.getVectorElementType() == N1
.getValueType().getVectorElementType() &&
3018 "Extract subvector VTs must have the same element type!");
3019 assert(VT
.getSimpleVT() <= N1
.getValueType().getSimpleVT() &&
3020 "Extract subvector must be from larger vector to smaller vector!");
3022 if (isa
<ConstantSDNode
>(Index
.getNode())) {
3023 assert((VT
.getVectorNumElements() +
3024 cast
<ConstantSDNode
>(Index
.getNode())->getZExtValue()
3025 <= N1
.getValueType().getVectorNumElements())
3026 && "Extract subvector overflow!");
3029 // Trivial extraction.
3030 if (VT
.getSimpleVT() == N1
.getValueType().getSimpleVT())
3039 SDValue SV
= FoldConstantArithmetic(Opcode
, VT
, N1C
, N2C
);
3040 if (SV
.getNode()) return SV
;
3041 } else { // Cannonicalize constant to RHS if commutative
3042 if (isCommutativeBinOp(Opcode
)) {
3043 std::swap(N1C
, N2C
);
3049 // Constant fold FP operations.
3050 ConstantFPSDNode
*N1CFP
= dyn_cast
<ConstantFPSDNode
>(N1
.getNode());
3051 ConstantFPSDNode
*N2CFP
= dyn_cast
<ConstantFPSDNode
>(N2
.getNode());
3053 if (!N2CFP
&& isCommutativeBinOp(Opcode
)) {
3054 // Cannonicalize constant to RHS if commutative
3055 std::swap(N1CFP
, N2CFP
);
3057 } else if (N2CFP
&& VT
!= MVT::ppcf128
) {
3058 APFloat V1
= N1CFP
->getValueAPF(), V2
= N2CFP
->getValueAPF();
3059 APFloat::opStatus s
;
3062 s
= V1
.add(V2
, APFloat::rmNearestTiesToEven
);
3063 if (s
!= APFloat::opInvalidOp
)
3064 return getConstantFP(V1
, VT
);
3067 s
= V1
.subtract(V2
, APFloat::rmNearestTiesToEven
);
3068 if (s
!=APFloat::opInvalidOp
)
3069 return getConstantFP(V1
, VT
);
3072 s
= V1
.multiply(V2
, APFloat::rmNearestTiesToEven
);
3073 if (s
!=APFloat::opInvalidOp
)
3074 return getConstantFP(V1
, VT
);
3077 s
= V1
.divide(V2
, APFloat::rmNearestTiesToEven
);
3078 if (s
!=APFloat::opInvalidOp
&& s
!=APFloat::opDivByZero
)
3079 return getConstantFP(V1
, VT
);
3082 s
= V1
.mod(V2
, APFloat::rmNearestTiesToEven
);
3083 if (s
!=APFloat::opInvalidOp
&& s
!=APFloat::opDivByZero
)
3084 return getConstantFP(V1
, VT
);
3086 case ISD::FCOPYSIGN
:
3088 return getConstantFP(V1
, VT
);
3093 if (Opcode
== ISD::FP_ROUND
) {
3094 APFloat V
= N1CFP
->getValueAPF(); // make copy
3096 // This can return overflow, underflow, or inexact; we don't care.
3097 // FIXME need to be more flexible about rounding mode.
3098 (void)V
.convert(*EVTToAPFloatSemantics(VT
),
3099 APFloat::rmNearestTiesToEven
, &ignored
);
3100 return getConstantFP(V
, VT
);
3104 // Canonicalize an UNDEF to the RHS, even over a constant.
3105 if (N1
.getOpcode() == ISD::UNDEF
) {
3106 if (isCommutativeBinOp(Opcode
)) {
3110 case ISD::FP_ROUND_INREG
:
3111 case ISD::SIGN_EXTEND_INREG
:
3117 return N1
; // fold op(undef, arg2) -> undef
3125 return getConstant(0, VT
); // fold op(undef, arg2) -> 0
3126 // For vectors, we can't easily build an all zero vector, just return
3133 // Fold a bunch of operators when the RHS is undef.
3134 if (N2
.getOpcode() == ISD::UNDEF
) {
3137 if (N1
.getOpcode() == ISD::UNDEF
)
3138 // Handle undef ^ undef -> 0 special case. This is a common
3140 return getConstant(0, VT
);
3150 return N2
; // fold op(arg1, undef) -> undef
3156 if (getTarget().Options
.UnsafeFPMath
)
3164 return getConstant(0, VT
); // fold op(arg1, undef) -> 0
3165 // For vectors, we can't easily build an all zero vector, just return
3170 return getConstant(APInt::getAllOnesValue(VT
.getSizeInBits()), VT
);
3171 // For vectors, we can't easily build an all one vector, just return
3179 // Memoize this node if possible.
3181 SDVTList VTs
= getVTList(VT
);
3182 if (VT
!= MVT::Glue
) {
3183 SDValue Ops
[] = { N1
, N2
};
3184 FoldingSetNodeID ID
;
3185 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 2);
3187 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
3188 return SDValue(E
, 0);
3190 N
= new (NodeAllocator
) BinarySDNode(Opcode
, DL
, VTs
, N1
, N2
);
3191 CSEMap
.InsertNode(N
, IP
);
3193 N
= new (NodeAllocator
) BinarySDNode(Opcode
, DL
, VTs
, N1
, N2
);
3196 AllNodes
.push_back(N
);
3200 return SDValue(N
, 0);
3203 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
3204 SDValue N1
, SDValue N2
, SDValue N3
) {
3205 // Perform various simplifications.
3206 ConstantSDNode
*N1C
= dyn_cast
<ConstantSDNode
>(N1
.getNode());
3208 case ISD::CONCAT_VECTORS
:
3209 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3210 // one big BUILD_VECTOR.
3211 if (N1
.getOpcode() == ISD::BUILD_VECTOR
&&
3212 N2
.getOpcode() == ISD::BUILD_VECTOR
&&
3213 N3
.getOpcode() == ISD::BUILD_VECTOR
) {
3214 SmallVector
<SDValue
, 16> Elts(N1
.getNode()->op_begin(),
3215 N1
.getNode()->op_end());
3216 Elts
.append(N2
.getNode()->op_begin(), N2
.getNode()->op_end());
3217 Elts
.append(N3
.getNode()->op_begin(), N3
.getNode()->op_end());
3218 return getNode(ISD::BUILD_VECTOR
, DL
, VT
, &Elts
[0], Elts
.size());
3222 // Use FoldSetCC to simplify SETCC's.
3223 SDValue Simp
= FoldSetCC(VT
, N1
, N2
, cast
<CondCodeSDNode
>(N3
)->get(), DL
);
3224 if (Simp
.getNode()) return Simp
;
3229 if (N1C
->getZExtValue())
3230 return N2
; // select true, X, Y -> X
3231 return N3
; // select false, X, Y -> Y
3234 if (N2
== N3
) return N2
; // select C, X, X -> X
3236 case ISD::VECTOR_SHUFFLE
:
3237 llvm_unreachable("should use getVectorShuffle constructor!");
3238 case ISD::INSERT_SUBVECTOR
: {
3240 if (VT
.isSimple() && N1
.getValueType().isSimple()
3241 && N2
.getValueType().isSimple()) {
3242 assert(VT
.isVector() && N1
.getValueType().isVector() &&
3243 N2
.getValueType().isVector() &&
3244 "Insert subvector VTs must be a vectors");
3245 assert(VT
== N1
.getValueType() &&
3246 "Dest and insert subvector source types must match!");
3247 assert(N2
.getValueType().getSimpleVT() <= N1
.getValueType().getSimpleVT() &&
3248 "Insert subvector must be from smaller vector to larger vector!");
3249 if (isa
<ConstantSDNode
>(Index
.getNode())) {
3250 assert((N2
.getValueType().getVectorNumElements() +
3251 cast
<ConstantSDNode
>(Index
.getNode())->getZExtValue()
3252 <= VT
.getVectorNumElements())
3253 && "Insert subvector overflow!");
3256 // Trivial insertion.
3257 if (VT
.getSimpleVT() == N2
.getValueType().getSimpleVT())
3263 // Fold bit_convert nodes from a type to themselves.
3264 if (N1
.getValueType() == VT
)
3269 // Memoize node if it doesn't produce a flag.
3271 SDVTList VTs
= getVTList(VT
);
3272 if (VT
!= MVT::Glue
) {
3273 SDValue Ops
[] = { N1
, N2
, N3
};
3274 FoldingSetNodeID ID
;
3275 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 3);
3277 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
3278 return SDValue(E
, 0);
3280 N
= new (NodeAllocator
) TernarySDNode(Opcode
, DL
, VTs
, N1
, N2
, N3
);
3281 CSEMap
.InsertNode(N
, IP
);
3283 N
= new (NodeAllocator
) TernarySDNode(Opcode
, DL
, VTs
, N1
, N2
, N3
);
3286 AllNodes
.push_back(N
);
3290 return SDValue(N
, 0);
3293 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
3294 SDValue N1
, SDValue N2
, SDValue N3
,
3296 SDValue Ops
[] = { N1
, N2
, N3
, N4
};
3297 return getNode(Opcode
, DL
, VT
, Ops
, 4);
3300 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
3301 SDValue N1
, SDValue N2
, SDValue N3
,
3302 SDValue N4
, SDValue N5
) {
3303 SDValue Ops
[] = { N1
, N2
, N3
, N4
, N5
};
3304 return getNode(Opcode
, DL
, VT
, Ops
, 5);
3307 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3308 /// the incoming stack arguments to be loaded from the stack.
3309 SDValue
SelectionDAG::getStackArgumentTokenFactor(SDValue Chain
) {
3310 SmallVector
<SDValue
, 8> ArgChains
;
3312 // Include the original chain at the beginning of the list. When this is
3313 // used by target LowerCall hooks, this helps legalize find the
3314 // CALLSEQ_BEGIN node.
3315 ArgChains
.push_back(Chain
);
3317 // Add a chain value for each stack argument.
3318 for (SDNode::use_iterator U
= getEntryNode().getNode()->use_begin(),
3319 UE
= getEntryNode().getNode()->use_end(); U
!= UE
; ++U
)
3320 if (LoadSDNode
*L
= dyn_cast
<LoadSDNode
>(*U
))
3321 if (FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(L
->getBasePtr()))
3322 if (FI
->getIndex() < 0)
3323 ArgChains
.push_back(SDValue(L
, 1));
3325 // Build a tokenfactor for all the chains.
3326 return getNode(ISD::TokenFactor
, Chain
.getDebugLoc(), MVT::Other
,
3327 &ArgChains
[0], ArgChains
.size());
3330 /// SplatByte - Distribute ByteVal over NumBits bits.
3331 static APInt
SplatByte(unsigned NumBits
, uint8_t ByteVal
) {
3332 APInt Val
= APInt(NumBits
, ByteVal
);
3334 for (unsigned i
= NumBits
; i
> 8; i
>>= 1) {
3335 Val
= (Val
<< Shift
) | Val
;
3341 /// getMemsetValue - Vectorized representation of the memset value
3343 static SDValue
getMemsetValue(SDValue Value
, EVT VT
, SelectionDAG
&DAG
,
3345 assert(Value
.getOpcode() != ISD::UNDEF
);
3347 unsigned NumBits
= VT
.getScalarType().getSizeInBits();
3348 if (ConstantSDNode
*C
= dyn_cast
<ConstantSDNode
>(Value
)) {
3349 APInt Val
= SplatByte(NumBits
, C
->getZExtValue() & 255);
3351 return DAG
.getConstant(Val
, VT
);
3352 return DAG
.getConstantFP(APFloat(Val
), VT
);
3355 Value
= DAG
.getNode(ISD::ZERO_EXTEND
, dl
, VT
, Value
);
3357 // Use a multiplication with 0x010101... to extend the input to the
3359 APInt Magic
= SplatByte(NumBits
, 0x01);
3360 Value
= DAG
.getNode(ISD::MUL
, dl
, VT
, Value
, DAG
.getConstant(Magic
, VT
));
3366 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3367 /// used when a memcpy is turned into a memset when the source is a constant
3369 static SDValue
getMemsetStringVal(EVT VT
, DebugLoc dl
, SelectionDAG
&DAG
,
3370 const TargetLowering
&TLI
, StringRef Str
) {
3371 // Handle vector with all elements zero.
3374 return DAG
.getConstant(0, VT
);
3375 else if (VT
== MVT::f32
|| VT
== MVT::f64
)
3376 return DAG
.getConstantFP(0.0, VT
);
3377 else if (VT
.isVector()) {
3378 unsigned NumElts
= VT
.getVectorNumElements();
3379 MVT EltVT
= (VT
.getVectorElementType() == MVT::f32
) ? MVT::i32
: MVT::i64
;
3380 return DAG
.getNode(ISD::BITCAST
, dl
, VT
,
3381 DAG
.getConstant(0, EVT::getVectorVT(*DAG
.getContext(),
3384 llvm_unreachable("Expected type!");
3387 assert(!VT
.isVector() && "Can't handle vector type here!");
3388 unsigned NumVTBytes
= VT
.getSizeInBits() / 8;
3389 unsigned NumBytes
= std::min(NumVTBytes
, unsigned(Str
.size()));
3392 if (TLI
.isLittleEndian()) {
3393 for (unsigned i
= 0; i
!= NumBytes
; ++i
)
3394 Val
|= (uint64_t)(unsigned char)Str
[i
] << i
*8;
3396 for (unsigned i
= 0; i
!= NumBytes
; ++i
)
3397 Val
|= (uint64_t)(unsigned char)Str
[i
] << (NumVTBytes
-i
-1)*8;
3400 return DAG
.getConstant(Val
, VT
);
3403 /// getMemBasePlusOffset - Returns base and offset node for the
3405 static SDValue
getMemBasePlusOffset(SDValue Base
, unsigned Offset
,
3406 SelectionDAG
&DAG
) {
3407 EVT VT
= Base
.getValueType();
3408 return DAG
.getNode(ISD::ADD
, Base
.getDebugLoc(),
3409 VT
, Base
, DAG
.getConstant(Offset
, VT
));
3412 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3414 static bool isMemSrcFromString(SDValue Src
, StringRef
&Str
) {
3415 unsigned SrcDelta
= 0;
3416 GlobalAddressSDNode
*G
= NULL
;
3417 if (Src
.getOpcode() == ISD::GlobalAddress
)
3418 G
= cast
<GlobalAddressSDNode
>(Src
);
3419 else if (Src
.getOpcode() == ISD::ADD
&&
3420 Src
.getOperand(0).getOpcode() == ISD::GlobalAddress
&&
3421 Src
.getOperand(1).getOpcode() == ISD::Constant
) {
3422 G
= cast
<GlobalAddressSDNode
>(Src
.getOperand(0));
3423 SrcDelta
= cast
<ConstantSDNode
>(Src
.getOperand(1))->getZExtValue();
3428 return getConstantStringInfo(G
->getGlobal(), Str
, SrcDelta
, false);
3431 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3432 /// to replace the memset / memcpy. Return true if the number of memory ops
3433 /// is below the threshold. It returns the types of the sequence of
3434 /// memory ops to perform memset / memcpy by reference.
3435 static bool FindOptimalMemOpLowering(std::vector
<EVT
> &MemOps
,
3436 unsigned Limit
, uint64_t Size
,
3437 unsigned DstAlign
, unsigned SrcAlign
,
3441 const TargetLowering
&TLI
) {
3442 assert((SrcAlign
== 0 || SrcAlign
>= DstAlign
) &&
3443 "Expecting memcpy / memset source to meet alignment requirement!");
3444 // If 'SrcAlign' is zero, that means the memory operation does not need to
3445 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3446 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3447 // is the specified alignment of the memory operation. If it is zero, that
3448 // means it's possible to change the alignment of the destination.
3449 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3450 // not need to be loaded.
3451 EVT VT
= TLI
.getOptimalMemOpType(Size
, DstAlign
, SrcAlign
,
3452 IsZeroVal
, MemcpyStrSrc
,
3453 DAG
.getMachineFunction());
3455 if (VT
== MVT::Other
) {
3456 if (DstAlign
>= TLI
.getTargetData()->getPointerPrefAlignment() ||
3457 TLI
.allowsUnalignedMemoryAccesses(VT
)) {
3458 VT
= TLI
.getPointerTy();
3460 switch (DstAlign
& 7) {
3461 case 0: VT
= MVT::i64
; break;
3462 case 4: VT
= MVT::i32
; break;
3463 case 2: VT
= MVT::i16
; break;
3464 default: VT
= MVT::i8
; break;
3469 while (!TLI
.isTypeLegal(LVT
))
3470 LVT
= (MVT::SimpleValueType
)(LVT
.SimpleTy
- 1);
3471 assert(LVT
.isInteger());
3477 unsigned NumMemOps
= 0;
3479 unsigned VTSize
= VT
.getSizeInBits() / 8;
3480 while (VTSize
> Size
) {
3481 // For now, only use non-vector load / store's for the left-over pieces.
3482 if (VT
.isVector() || VT
.isFloatingPoint()) {
3484 while (!TLI
.isTypeLegal(VT
))
3485 VT
= (MVT::SimpleValueType
)(VT
.getSimpleVT().SimpleTy
- 1);
3486 VTSize
= VT
.getSizeInBits() / 8;
3488 // This can result in a type that is not legal on the target, e.g.
3489 // 1 or 2 bytes on PPC.
3490 VT
= (MVT::SimpleValueType
)(VT
.getSimpleVT().SimpleTy
- 1);
3495 if (++NumMemOps
> Limit
)
3497 MemOps
.push_back(VT
);
3504 static SDValue
getMemcpyLoadsAndStores(SelectionDAG
&DAG
, DebugLoc dl
,
3505 SDValue Chain
, SDValue Dst
,
3506 SDValue Src
, uint64_t Size
,
3507 unsigned Align
, bool isVol
,
3509 MachinePointerInfo DstPtrInfo
,
3510 MachinePointerInfo SrcPtrInfo
) {
3511 // Turn a memcpy of undef to nop.
3512 if (Src
.getOpcode() == ISD::UNDEF
)
3515 // Expand memcpy to a series of load and store ops if the size operand falls
3516 // below a certain threshold.
3517 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3518 // rather than maybe a humongous number of loads and stores.
3519 const TargetLowering
&TLI
= DAG
.getTargetLoweringInfo();
3520 std::vector
<EVT
> MemOps
;
3521 bool DstAlignCanChange
= false;
3522 MachineFunction
&MF
= DAG
.getMachineFunction();
3523 MachineFrameInfo
*MFI
= MF
.getFrameInfo();
3524 bool OptSize
= MF
.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3525 FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(Dst
);
3526 if (FI
&& !MFI
->isFixedObjectIndex(FI
->getIndex()))
3527 DstAlignCanChange
= true;
3528 unsigned SrcAlign
= DAG
.InferPtrAlignment(Src
);
3529 if (Align
> SrcAlign
)
3532 bool CopyFromStr
= isMemSrcFromString(Src
, Str
);
3533 bool isZeroStr
= CopyFromStr
&& Str
.empty();
3534 unsigned Limit
= AlwaysInline
? ~0U : TLI
.getMaxStoresPerMemcpy(OptSize
);
3536 if (!FindOptimalMemOpLowering(MemOps
, Limit
, Size
,
3537 (DstAlignCanChange
? 0 : Align
),
3538 (isZeroStr
? 0 : SrcAlign
),
3539 true, CopyFromStr
, DAG
, TLI
))
3542 if (DstAlignCanChange
) {
3543 Type
*Ty
= MemOps
[0].getTypeForEVT(*DAG
.getContext());
3544 unsigned NewAlign
= (unsigned) TLI
.getTargetData()->getABITypeAlignment(Ty
);
3545 if (NewAlign
> Align
) {
3546 // Give the stack frame object a larger alignment if needed.
3547 if (MFI
->getObjectAlignment(FI
->getIndex()) < NewAlign
)
3548 MFI
->setObjectAlignment(FI
->getIndex(), NewAlign
);
3553 SmallVector
<SDValue
, 8> OutChains
;
3554 unsigned NumMemOps
= MemOps
.size();
3555 uint64_t SrcOff
= 0, DstOff
= 0;
3556 for (unsigned i
= 0; i
!= NumMemOps
; ++i
) {
3558 unsigned VTSize
= VT
.getSizeInBits() / 8;
3559 SDValue Value
, Store
;
3562 (isZeroStr
|| (VT
.isInteger() && !VT
.isVector()))) {
3563 // It's unlikely a store of a vector immediate can be done in a single
3564 // instruction. It would require a load from a constantpool first.
3565 // We only handle zero vectors here.
3566 // FIXME: Handle other cases where store of vector immediate is done in
3567 // a single instruction.
3568 Value
= getMemsetStringVal(VT
, dl
, DAG
, TLI
, Str
.substr(SrcOff
));
3569 Store
= DAG
.getStore(Chain
, dl
, Value
,
3570 getMemBasePlusOffset(Dst
, DstOff
, DAG
),
3571 DstPtrInfo
.getWithOffset(DstOff
), isVol
,
3574 // The type might not be legal for the target. This should only happen
3575 // if the type is smaller than a legal type, as on PPC, so the right
3576 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3577 // to Load/Store if NVT==VT.
3578 // FIXME does the case above also need this?
3579 EVT NVT
= TLI
.getTypeToTransformTo(*DAG
.getContext(), VT
);
3580 assert(NVT
.bitsGE(VT
));
3581 Value
= DAG
.getExtLoad(ISD::EXTLOAD
, dl
, NVT
, Chain
,
3582 getMemBasePlusOffset(Src
, SrcOff
, DAG
),
3583 SrcPtrInfo
.getWithOffset(SrcOff
), VT
, isVol
, false,
3584 MinAlign(SrcAlign
, SrcOff
));
3585 Store
= DAG
.getTruncStore(Chain
, dl
, Value
,
3586 getMemBasePlusOffset(Dst
, DstOff
, DAG
),
3587 DstPtrInfo
.getWithOffset(DstOff
), VT
, isVol
,
3590 OutChains
.push_back(Store
);
3595 return DAG
.getNode(ISD::TokenFactor
, dl
, MVT::Other
,
3596 &OutChains
[0], OutChains
.size());
3599 static SDValue
getMemmoveLoadsAndStores(SelectionDAG
&DAG
, DebugLoc dl
,
3600 SDValue Chain
, SDValue Dst
,
3601 SDValue Src
, uint64_t Size
,
3602 unsigned Align
, bool isVol
,
3604 MachinePointerInfo DstPtrInfo
,
3605 MachinePointerInfo SrcPtrInfo
) {
3606 // Turn a memmove of undef to nop.
3607 if (Src
.getOpcode() == ISD::UNDEF
)
3610 // Expand memmove to a series of load and store ops if the size operand falls
3611 // below a certain threshold.
3612 const TargetLowering
&TLI
= DAG
.getTargetLoweringInfo();
3613 std::vector
<EVT
> MemOps
;
3614 bool DstAlignCanChange
= false;
3615 MachineFunction
&MF
= DAG
.getMachineFunction();
3616 MachineFrameInfo
*MFI
= MF
.getFrameInfo();
3617 bool OptSize
= MF
.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3618 FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(Dst
);
3619 if (FI
&& !MFI
->isFixedObjectIndex(FI
->getIndex()))
3620 DstAlignCanChange
= true;
3621 unsigned SrcAlign
= DAG
.InferPtrAlignment(Src
);
3622 if (Align
> SrcAlign
)
3624 unsigned Limit
= AlwaysInline
? ~0U : TLI
.getMaxStoresPerMemmove(OptSize
);
3626 if (!FindOptimalMemOpLowering(MemOps
, Limit
, Size
,
3627 (DstAlignCanChange
? 0 : Align
),
3628 SrcAlign
, true, false, DAG
, TLI
))
3631 if (DstAlignCanChange
) {
3632 Type
*Ty
= MemOps
[0].getTypeForEVT(*DAG
.getContext());
3633 unsigned NewAlign
= (unsigned) TLI
.getTargetData()->getABITypeAlignment(Ty
);
3634 if (NewAlign
> Align
) {
3635 // Give the stack frame object a larger alignment if needed.
3636 if (MFI
->getObjectAlignment(FI
->getIndex()) < NewAlign
)
3637 MFI
->setObjectAlignment(FI
->getIndex(), NewAlign
);
3642 uint64_t SrcOff
= 0, DstOff
= 0;
3643 SmallVector
<SDValue
, 8> LoadValues
;
3644 SmallVector
<SDValue
, 8> LoadChains
;
3645 SmallVector
<SDValue
, 8> OutChains
;
3646 unsigned NumMemOps
= MemOps
.size();
3647 for (unsigned i
= 0; i
< NumMemOps
; i
++) {
3649 unsigned VTSize
= VT
.getSizeInBits() / 8;
3650 SDValue Value
, Store
;
3652 Value
= DAG
.getLoad(VT
, dl
, Chain
,
3653 getMemBasePlusOffset(Src
, SrcOff
, DAG
),
3654 SrcPtrInfo
.getWithOffset(SrcOff
), isVol
,
3655 false, false, SrcAlign
);
3656 LoadValues
.push_back(Value
);
3657 LoadChains
.push_back(Value
.getValue(1));
3660 Chain
= DAG
.getNode(ISD::TokenFactor
, dl
, MVT::Other
,
3661 &LoadChains
[0], LoadChains
.size());
3663 for (unsigned i
= 0; i
< NumMemOps
; i
++) {
3665 unsigned VTSize
= VT
.getSizeInBits() / 8;
3666 SDValue Value
, Store
;
3668 Store
= DAG
.getStore(Chain
, dl
, LoadValues
[i
],
3669 getMemBasePlusOffset(Dst
, DstOff
, DAG
),
3670 DstPtrInfo
.getWithOffset(DstOff
), isVol
, false, Align
);
3671 OutChains
.push_back(Store
);
3675 return DAG
.getNode(ISD::TokenFactor
, dl
, MVT::Other
,
3676 &OutChains
[0], OutChains
.size());
3679 static SDValue
getMemsetStores(SelectionDAG
&DAG
, DebugLoc dl
,
3680 SDValue Chain
, SDValue Dst
,
3681 SDValue Src
, uint64_t Size
,
3682 unsigned Align
, bool isVol
,
3683 MachinePointerInfo DstPtrInfo
) {
3684 // Turn a memset of undef to nop.
3685 if (Src
.getOpcode() == ISD::UNDEF
)
3688 // Expand memset to a series of load/store ops if the size operand
3689 // falls below a certain threshold.
3690 const TargetLowering
&TLI
= DAG
.getTargetLoweringInfo();
3691 std::vector
<EVT
> MemOps
;
3692 bool DstAlignCanChange
= false;
3693 MachineFunction
&MF
= DAG
.getMachineFunction();
3694 MachineFrameInfo
*MFI
= MF
.getFrameInfo();
3695 bool OptSize
= MF
.getFunction()->getFnAttributes().hasOptimizeForSizeAttr();
3696 FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(Dst
);
3697 if (FI
&& !MFI
->isFixedObjectIndex(FI
->getIndex()))
3698 DstAlignCanChange
= true;
3700 isa
<ConstantSDNode
>(Src
) && cast
<ConstantSDNode
>(Src
)->isNullValue();
3701 if (!FindOptimalMemOpLowering(MemOps
, TLI
.getMaxStoresPerMemset(OptSize
),
3702 Size
, (DstAlignCanChange
? 0 : Align
), 0,
3703 IsZeroVal
, false, DAG
, TLI
))
3706 if (DstAlignCanChange
) {
3707 Type
*Ty
= MemOps
[0].getTypeForEVT(*DAG
.getContext());
3708 unsigned NewAlign
= (unsigned) TLI
.getTargetData()->getABITypeAlignment(Ty
);
3709 if (NewAlign
> Align
) {
3710 // Give the stack frame object a larger alignment if needed.
3711 if (MFI
->getObjectAlignment(FI
->getIndex()) < NewAlign
)
3712 MFI
->setObjectAlignment(FI
->getIndex(), NewAlign
);
3717 SmallVector
<SDValue
, 8> OutChains
;
3718 uint64_t DstOff
= 0;
3719 unsigned NumMemOps
= MemOps
.size();
3721 // Find the largest store and generate the bit pattern for it.
3722 EVT LargestVT
= MemOps
[0];
3723 for (unsigned i
= 1; i
< NumMemOps
; i
++)
3724 if (MemOps
[i
].bitsGT(LargestVT
))
3725 LargestVT
= MemOps
[i
];
3726 SDValue MemSetValue
= getMemsetValue(Src
, LargestVT
, DAG
, dl
);
3728 for (unsigned i
= 0; i
< NumMemOps
; i
++) {
3731 // If this store is smaller than the largest store see whether we can get
3732 // the smaller value for free with a truncate.
3733 SDValue Value
= MemSetValue
;
3734 if (VT
.bitsLT(LargestVT
)) {
3735 if (!LargestVT
.isVector() && !VT
.isVector() &&
3736 TLI
.isTruncateFree(LargestVT
, VT
))
3737 Value
= DAG
.getNode(ISD::TRUNCATE
, dl
, VT
, MemSetValue
);
3739 Value
= getMemsetValue(Src
, VT
, DAG
, dl
);
3741 assert(Value
.getValueType() == VT
&& "Value with wrong type.");
3742 SDValue Store
= DAG
.getStore(Chain
, dl
, Value
,
3743 getMemBasePlusOffset(Dst
, DstOff
, DAG
),
3744 DstPtrInfo
.getWithOffset(DstOff
),
3745 isVol
, false, Align
);
3746 OutChains
.push_back(Store
);
3747 DstOff
+= VT
.getSizeInBits() / 8;
3750 return DAG
.getNode(ISD::TokenFactor
, dl
, MVT::Other
,
3751 &OutChains
[0], OutChains
.size());
3754 SDValue
SelectionDAG::getMemcpy(SDValue Chain
, DebugLoc dl
, SDValue Dst
,
3755 SDValue Src
, SDValue Size
,
3756 unsigned Align
, bool isVol
, bool AlwaysInline
,
3757 MachinePointerInfo DstPtrInfo
,
3758 MachinePointerInfo SrcPtrInfo
) {
3760 // Check to see if we should lower the memcpy to loads and stores first.
3761 // For cases within the target-specified limits, this is the best choice.
3762 ConstantSDNode
*ConstantSize
= dyn_cast
<ConstantSDNode
>(Size
);
3764 // Memcpy with size zero? Just return the original chain.
3765 if (ConstantSize
->isNullValue())
3768 SDValue Result
= getMemcpyLoadsAndStores(*this, dl
, Chain
, Dst
, Src
,
3769 ConstantSize
->getZExtValue(),Align
,
3770 isVol
, false, DstPtrInfo
, SrcPtrInfo
);
3771 if (Result
.getNode())
3775 // Then check to see if we should lower the memcpy with target-specific
3776 // code. If the target chooses to do this, this is the next best.
3778 TSI
.EmitTargetCodeForMemcpy(*this, dl
, Chain
, Dst
, Src
, Size
, Align
,
3779 isVol
, AlwaysInline
,
3780 DstPtrInfo
, SrcPtrInfo
);
3781 if (Result
.getNode())
3784 // If we really need inline code and the target declined to provide it,
3785 // use a (potentially long) sequence of loads and stores.
3787 assert(ConstantSize
&& "AlwaysInline requires a constant size!");
3788 return getMemcpyLoadsAndStores(*this, dl
, Chain
, Dst
, Src
,
3789 ConstantSize
->getZExtValue(), Align
, isVol
,
3790 true, DstPtrInfo
, SrcPtrInfo
);
3793 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
3794 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
3795 // respect volatile, so they may do things like read or write memory
3796 // beyond the given memory regions. But fixing this isn't easy, and most
3797 // people don't care.
3799 // Emit a library call.
3800 TargetLowering::ArgListTy Args
;
3801 TargetLowering::ArgListEntry Entry
;
3802 Entry
.Ty
= TLI
.getTargetData()->getIntPtrType(*getContext());
3803 Entry
.Node
= Dst
; Args
.push_back(Entry
);
3804 Entry
.Node
= Src
; Args
.push_back(Entry
);
3805 Entry
.Node
= Size
; Args
.push_back(Entry
);
3806 // FIXME: pass in DebugLoc
3808 CallLoweringInfo
CLI(Chain
, Type::getVoidTy(*getContext()),
3809 false, false, false, false, 0,
3810 TLI
.getLibcallCallingConv(RTLIB::MEMCPY
),
3811 /*isTailCall=*/false,
3812 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3813 getExternalSymbol(TLI
.getLibcallName(RTLIB::MEMCPY
),
3814 TLI
.getPointerTy()),
3816 std::pair
<SDValue
,SDValue
> CallResult
= TLI
.LowerCallTo(CLI
);
3818 return CallResult
.second
;
3821 SDValue
SelectionDAG::getMemmove(SDValue Chain
, DebugLoc dl
, SDValue Dst
,
3822 SDValue Src
, SDValue Size
,
3823 unsigned Align
, bool isVol
,
3824 MachinePointerInfo DstPtrInfo
,
3825 MachinePointerInfo SrcPtrInfo
) {
3827 // Check to see if we should lower the memmove to loads and stores first.
3828 // For cases within the target-specified limits, this is the best choice.
3829 ConstantSDNode
*ConstantSize
= dyn_cast
<ConstantSDNode
>(Size
);
3831 // Memmove with size zero? Just return the original chain.
3832 if (ConstantSize
->isNullValue())
3836 getMemmoveLoadsAndStores(*this, dl
, Chain
, Dst
, Src
,
3837 ConstantSize
->getZExtValue(), Align
, isVol
,
3838 false, DstPtrInfo
, SrcPtrInfo
);
3839 if (Result
.getNode())
3843 // Then check to see if we should lower the memmove with target-specific
3844 // code. If the target chooses to do this, this is the next best.
3846 TSI
.EmitTargetCodeForMemmove(*this, dl
, Chain
, Dst
, Src
, Size
, Align
, isVol
,
3847 DstPtrInfo
, SrcPtrInfo
);
3848 if (Result
.getNode())
3851 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
3852 // not be safe. See memcpy above for more details.
3854 // Emit a library call.
3855 TargetLowering::ArgListTy Args
;
3856 TargetLowering::ArgListEntry Entry
;
3857 Entry
.Ty
= TLI
.getTargetData()->getIntPtrType(*getContext());
3858 Entry
.Node
= Dst
; Args
.push_back(Entry
);
3859 Entry
.Node
= Src
; Args
.push_back(Entry
);
3860 Entry
.Node
= Size
; Args
.push_back(Entry
);
3861 // FIXME: pass in DebugLoc
3863 CallLoweringInfo
CLI(Chain
, Type::getVoidTy(*getContext()),
3864 false, false, false, false, 0,
3865 TLI
.getLibcallCallingConv(RTLIB::MEMMOVE
),
3866 /*isTailCall=*/false,
3867 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
3868 getExternalSymbol(TLI
.getLibcallName(RTLIB::MEMMOVE
),
3869 TLI
.getPointerTy()),
3871 std::pair
<SDValue
,SDValue
> CallResult
= TLI
.LowerCallTo(CLI
);
3873 return CallResult
.second
;
3876 SDValue
SelectionDAG::getMemset(SDValue Chain
, DebugLoc dl
, SDValue Dst
,
3877 SDValue Src
, SDValue Size
,
3878 unsigned Align
, bool isVol
,
3879 MachinePointerInfo DstPtrInfo
) {
3881 // Check to see if we should lower the memset to stores first.
3882 // For cases within the target-specified limits, this is the best choice.
3883 ConstantSDNode
*ConstantSize
= dyn_cast
<ConstantSDNode
>(Size
);
3885 // Memset with size zero? Just return the original chain.
3886 if (ConstantSize
->isNullValue())
3890 getMemsetStores(*this, dl
, Chain
, Dst
, Src
, ConstantSize
->getZExtValue(),
3891 Align
, isVol
, DstPtrInfo
);
3893 if (Result
.getNode())
3897 // Then check to see if we should lower the memset with target-specific
3898 // code. If the target chooses to do this, this is the next best.
3900 TSI
.EmitTargetCodeForMemset(*this, dl
, Chain
, Dst
, Src
, Size
, Align
, isVol
,
3902 if (Result
.getNode())
3905 // Emit a library call.
3906 Type
*IntPtrTy
= TLI
.getTargetData()->getIntPtrType(*getContext());
3907 TargetLowering::ArgListTy Args
;
3908 TargetLowering::ArgListEntry Entry
;
3909 Entry
.Node
= Dst
; Entry
.Ty
= IntPtrTy
;
3910 Args
.push_back(Entry
);
3911 // Extend or truncate the argument to be an i32 value for the call.
3912 if (Src
.getValueType().bitsGT(MVT::i32
))
3913 Src
= getNode(ISD::TRUNCATE
, dl
, MVT::i32
, Src
);
3915 Src
= getNode(ISD::ZERO_EXTEND
, dl
, MVT::i32
, Src
);
3917 Entry
.Ty
= Type::getInt32Ty(*getContext());
3918 Entry
.isSExt
= true;
3919 Args
.push_back(Entry
);
3921 Entry
.Ty
= IntPtrTy
;
3922 Entry
.isSExt
= false;
3923 Args
.push_back(Entry
);
3924 // FIXME: pass in DebugLoc
3926 CallLoweringInfo
CLI(Chain
, Type::getVoidTy(*getContext()),
3927 false, false, false, false, 0,
3928 TLI
.getLibcallCallingConv(RTLIB::MEMSET
),
3929 /*isTailCall=*/false,
3930 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
3931 getExternalSymbol(TLI
.getLibcallName(RTLIB::MEMSET
),
3932 TLI
.getPointerTy()),
3934 std::pair
<SDValue
,SDValue
> CallResult
= TLI
.LowerCallTo(CLI
);
3936 return CallResult
.second
;
3939 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
3940 SDValue Chain
, SDValue Ptr
, SDValue Cmp
,
3941 SDValue Swp
, MachinePointerInfo PtrInfo
,
3943 AtomicOrdering Ordering
,
3944 SynchronizationScope SynchScope
) {
3945 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
3946 Alignment
= getEVTAlignment(MemVT
);
3948 MachineFunction
&MF
= getMachineFunction();
3950 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
3951 // For now, atomics are considered to be volatile always.
3952 // FIXME: Volatile isn't really correct; we should keep track of atomic
3953 // orderings in the memoperand.
3954 unsigned Flags
= MachineMemOperand::MOVolatile
;
3955 if (Opcode
!= ISD::ATOMIC_STORE
)
3956 Flags
|= MachineMemOperand::MOLoad
;
3957 if (Opcode
!= ISD::ATOMIC_LOAD
)
3958 Flags
|= MachineMemOperand::MOStore
;
3960 MachineMemOperand
*MMO
=
3961 MF
.getMachineMemOperand(PtrInfo
, Flags
, MemVT
.getStoreSize(), Alignment
);
3963 return getAtomic(Opcode
, dl
, MemVT
, Chain
, Ptr
, Cmp
, Swp
, MMO
,
3964 Ordering
, SynchScope
);
3967 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
3969 SDValue Ptr
, SDValue Cmp
,
3970 SDValue Swp
, MachineMemOperand
*MMO
,
3971 AtomicOrdering Ordering
,
3972 SynchronizationScope SynchScope
) {
3973 assert(Opcode
== ISD::ATOMIC_CMP_SWAP
&& "Invalid Atomic Op");
3974 assert(Cmp
.getValueType() == Swp
.getValueType() && "Invalid Atomic Op Types");
3976 EVT VT
= Cmp
.getValueType();
3978 SDVTList VTs
= getVTList(VT
, MVT::Other
);
3979 FoldingSetNodeID ID
;
3980 ID
.AddInteger(MemVT
.getRawBits());
3981 SDValue Ops
[] = {Chain
, Ptr
, Cmp
, Swp
};
3982 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 4);
3983 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
3985 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
3986 cast
<AtomicSDNode
>(E
)->refineAlignment(MMO
);
3987 return SDValue(E
, 0);
3989 SDNode
*N
= new (NodeAllocator
) AtomicSDNode(Opcode
, dl
, VTs
, MemVT
, Chain
,
3990 Ptr
, Cmp
, Swp
, MMO
, Ordering
,
3992 CSEMap
.InsertNode(N
, IP
);
3993 AllNodes
.push_back(N
);
3994 return SDValue(N
, 0);
3997 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
3999 SDValue Ptr
, SDValue Val
,
4000 const Value
* PtrVal
,
4002 AtomicOrdering Ordering
,
4003 SynchronizationScope SynchScope
) {
4004 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
4005 Alignment
= getEVTAlignment(MemVT
);
4007 MachineFunction
&MF
= getMachineFunction();
4008 // An atomic store does not load. An atomic load does not store.
4009 // (An atomicrmw obviously both loads and stores.)
4010 // For now, atomics are considered to be volatile always, and they are
4012 // FIXME: Volatile isn't really correct; we should keep track of atomic
4013 // orderings in the memoperand.
4014 unsigned Flags
= MachineMemOperand::MOVolatile
;
4015 if (Opcode
!= ISD::ATOMIC_STORE
)
4016 Flags
|= MachineMemOperand::MOLoad
;
4017 if (Opcode
!= ISD::ATOMIC_LOAD
)
4018 Flags
|= MachineMemOperand::MOStore
;
4020 MachineMemOperand
*MMO
=
4021 MF
.getMachineMemOperand(MachinePointerInfo(PtrVal
), Flags
,
4022 MemVT
.getStoreSize(), Alignment
);
4024 return getAtomic(Opcode
, dl
, MemVT
, Chain
, Ptr
, Val
, MMO
,
4025 Ordering
, SynchScope
);
4028 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
4030 SDValue Ptr
, SDValue Val
,
4031 MachineMemOperand
*MMO
,
4032 AtomicOrdering Ordering
,
4033 SynchronizationScope SynchScope
) {
4034 assert((Opcode
== ISD::ATOMIC_LOAD_ADD
||
4035 Opcode
== ISD::ATOMIC_LOAD_SUB
||
4036 Opcode
== ISD::ATOMIC_LOAD_AND
||
4037 Opcode
== ISD::ATOMIC_LOAD_OR
||
4038 Opcode
== ISD::ATOMIC_LOAD_XOR
||
4039 Opcode
== ISD::ATOMIC_LOAD_NAND
||
4040 Opcode
== ISD::ATOMIC_LOAD_MIN
||
4041 Opcode
== ISD::ATOMIC_LOAD_MAX
||
4042 Opcode
== ISD::ATOMIC_LOAD_UMIN
||
4043 Opcode
== ISD::ATOMIC_LOAD_UMAX
||
4044 Opcode
== ISD::ATOMIC_SWAP
||
4045 Opcode
== ISD::ATOMIC_STORE
) &&
4046 "Invalid Atomic Op");
4048 EVT VT
= Val
.getValueType();
4050 SDVTList VTs
= Opcode
== ISD::ATOMIC_STORE
? getVTList(MVT::Other
) :
4051 getVTList(VT
, MVT::Other
);
4052 FoldingSetNodeID ID
;
4053 ID
.AddInteger(MemVT
.getRawBits());
4054 SDValue Ops
[] = {Chain
, Ptr
, Val
};
4055 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 3);
4056 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4058 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4059 cast
<AtomicSDNode
>(E
)->refineAlignment(MMO
);
4060 return SDValue(E
, 0);
4062 SDNode
*N
= new (NodeAllocator
) AtomicSDNode(Opcode
, dl
, VTs
, MemVT
, Chain
,
4064 Ordering
, SynchScope
);
4065 CSEMap
.InsertNode(N
, IP
);
4066 AllNodes
.push_back(N
);
4067 return SDValue(N
, 0);
4070 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
4071 EVT VT
, SDValue Chain
,
4073 const Value
* PtrVal
,
4075 AtomicOrdering Ordering
,
4076 SynchronizationScope SynchScope
) {
4077 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
4078 Alignment
= getEVTAlignment(MemVT
);
4080 MachineFunction
&MF
= getMachineFunction();
4081 // An atomic store does not load. An atomic load does not store.
4082 // (An atomicrmw obviously both loads and stores.)
4083 // For now, atomics are considered to be volatile always, and they are
4085 // FIXME: Volatile isn't really correct; we should keep track of atomic
4086 // orderings in the memoperand.
4087 unsigned Flags
= MachineMemOperand::MOVolatile
;
4088 if (Opcode
!= ISD::ATOMIC_STORE
)
4089 Flags
|= MachineMemOperand::MOLoad
;
4090 if (Opcode
!= ISD::ATOMIC_LOAD
)
4091 Flags
|= MachineMemOperand::MOStore
;
4093 MachineMemOperand
*MMO
=
4094 MF
.getMachineMemOperand(MachinePointerInfo(PtrVal
), Flags
,
4095 MemVT
.getStoreSize(), Alignment
);
4097 return getAtomic(Opcode
, dl
, MemVT
, VT
, Chain
, Ptr
, MMO
,
4098 Ordering
, SynchScope
);
4101 SDValue
SelectionDAG::getAtomic(unsigned Opcode
, DebugLoc dl
, EVT MemVT
,
4102 EVT VT
, SDValue Chain
,
4104 MachineMemOperand
*MMO
,
4105 AtomicOrdering Ordering
,
4106 SynchronizationScope SynchScope
) {
4107 assert(Opcode
== ISD::ATOMIC_LOAD
&& "Invalid Atomic Op");
4109 SDVTList VTs
= getVTList(VT
, MVT::Other
);
4110 FoldingSetNodeID ID
;
4111 ID
.AddInteger(MemVT
.getRawBits());
4112 SDValue Ops
[] = {Chain
, Ptr
};
4113 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, 2);
4114 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4116 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4117 cast
<AtomicSDNode
>(E
)->refineAlignment(MMO
);
4118 return SDValue(E
, 0);
4120 SDNode
*N
= new (NodeAllocator
) AtomicSDNode(Opcode
, dl
, VTs
, MemVT
, Chain
,
4121 Ptr
, MMO
, Ordering
, SynchScope
);
4122 CSEMap
.InsertNode(N
, IP
);
4123 AllNodes
.push_back(N
);
4124 return SDValue(N
, 0);
4127 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4128 SDValue
SelectionDAG::getMergeValues(const SDValue
*Ops
, unsigned NumOps
,
4133 SmallVector
<EVT
, 4> VTs
;
4134 VTs
.reserve(NumOps
);
4135 for (unsigned i
= 0; i
< NumOps
; ++i
)
4136 VTs
.push_back(Ops
[i
].getValueType());
4137 return getNode(ISD::MERGE_VALUES
, dl
, getVTList(&VTs
[0], NumOps
),
4142 SelectionDAG::getMemIntrinsicNode(unsigned Opcode
, DebugLoc dl
,
4143 const EVT
*VTs
, unsigned NumVTs
,
4144 const SDValue
*Ops
, unsigned NumOps
,
4145 EVT MemVT
, MachinePointerInfo PtrInfo
,
4146 unsigned Align
, bool Vol
,
4147 bool ReadMem
, bool WriteMem
) {
4148 return getMemIntrinsicNode(Opcode
, dl
, makeVTList(VTs
, NumVTs
), Ops
, NumOps
,
4149 MemVT
, PtrInfo
, Align
, Vol
,
4154 SelectionDAG::getMemIntrinsicNode(unsigned Opcode
, DebugLoc dl
, SDVTList VTList
,
4155 const SDValue
*Ops
, unsigned NumOps
,
4156 EVT MemVT
, MachinePointerInfo PtrInfo
,
4157 unsigned Align
, bool Vol
,
4158 bool ReadMem
, bool WriteMem
) {
4159 if (Align
== 0) // Ensure that codegen never sees alignment 0
4160 Align
= getEVTAlignment(MemVT
);
4162 MachineFunction
&MF
= getMachineFunction();
4165 Flags
|= MachineMemOperand::MOStore
;
4167 Flags
|= MachineMemOperand::MOLoad
;
4169 Flags
|= MachineMemOperand::MOVolatile
;
4170 MachineMemOperand
*MMO
=
4171 MF
.getMachineMemOperand(PtrInfo
, Flags
, MemVT
.getStoreSize(), Align
);
4173 return getMemIntrinsicNode(Opcode
, dl
, VTList
, Ops
, NumOps
, MemVT
, MMO
);
4177 SelectionDAG::getMemIntrinsicNode(unsigned Opcode
, DebugLoc dl
, SDVTList VTList
,
4178 const SDValue
*Ops
, unsigned NumOps
,
4179 EVT MemVT
, MachineMemOperand
*MMO
) {
4180 assert((Opcode
== ISD::INTRINSIC_VOID
||
4181 Opcode
== ISD::INTRINSIC_W_CHAIN
||
4182 Opcode
== ISD::PREFETCH
||
4183 Opcode
== ISD::LIFETIME_START
||
4184 Opcode
== ISD::LIFETIME_END
||
4185 (Opcode
<= INT_MAX
&&
4186 (int)Opcode
>= ISD::FIRST_TARGET_MEMORY_OPCODE
)) &&
4187 "Opcode is not a memory-accessing opcode!");
4189 // Memoize the node unless it returns a flag.
4190 MemIntrinsicSDNode
*N
;
4191 if (VTList
.VTs
[VTList
.NumVTs
-1] != MVT::Glue
) {
4192 FoldingSetNodeID ID
;
4193 AddNodeIDNode(ID
, Opcode
, VTList
, Ops
, NumOps
);
4194 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4196 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4197 cast
<MemIntrinsicSDNode
>(E
)->refineAlignment(MMO
);
4198 return SDValue(E
, 0);
4201 N
= new (NodeAllocator
) MemIntrinsicSDNode(Opcode
, dl
, VTList
, Ops
, NumOps
,
4203 CSEMap
.InsertNode(N
, IP
);
4205 N
= new (NodeAllocator
) MemIntrinsicSDNode(Opcode
, dl
, VTList
, Ops
, NumOps
,
4208 AllNodes
.push_back(N
);
4209 return SDValue(N
, 0);
4212 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4213 /// MachinePointerInfo record from it. This is particularly useful because the
4214 /// code generator has many cases where it doesn't bother passing in a
4215 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4216 static MachinePointerInfo
InferPointerInfo(SDValue Ptr
, int64_t Offset
= 0) {
4217 // If this is FI+Offset, we can model it.
4218 if (const FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(Ptr
))
4219 return MachinePointerInfo::getFixedStack(FI
->getIndex(), Offset
);
4221 // If this is (FI+Offset1)+Offset2, we can model it.
4222 if (Ptr
.getOpcode() != ISD::ADD
||
4223 !isa
<ConstantSDNode
>(Ptr
.getOperand(1)) ||
4224 !isa
<FrameIndexSDNode
>(Ptr
.getOperand(0)))
4225 return MachinePointerInfo();
4227 int FI
= cast
<FrameIndexSDNode
>(Ptr
.getOperand(0))->getIndex();
4228 return MachinePointerInfo::getFixedStack(FI
, Offset
+
4229 cast
<ConstantSDNode
>(Ptr
.getOperand(1))->getSExtValue());
4232 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4233 /// MachinePointerInfo record from it. This is particularly useful because the
4234 /// code generator has many cases where it doesn't bother passing in a
4235 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4236 static MachinePointerInfo
InferPointerInfo(SDValue Ptr
, SDValue OffsetOp
) {
4237 // If the 'Offset' value isn't a constant, we can't handle this.
4238 if (ConstantSDNode
*OffsetNode
= dyn_cast
<ConstantSDNode
>(OffsetOp
))
4239 return InferPointerInfo(Ptr
, OffsetNode
->getSExtValue());
4240 if (OffsetOp
.getOpcode() == ISD::UNDEF
)
4241 return InferPointerInfo(Ptr
);
4242 return MachinePointerInfo();
4247 SelectionDAG::getLoad(ISD::MemIndexedMode AM
, ISD::LoadExtType ExtType
,
4248 EVT VT
, DebugLoc dl
, SDValue Chain
,
4249 SDValue Ptr
, SDValue Offset
,
4250 MachinePointerInfo PtrInfo
, EVT MemVT
,
4251 bool isVolatile
, bool isNonTemporal
, bool isInvariant
,
4252 unsigned Alignment
, const MDNode
*TBAAInfo
,
4253 const MDNode
*Ranges
) {
4254 assert(Chain
.getValueType() == MVT::Other
&&
4255 "Invalid chain type");
4256 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
4257 Alignment
= getEVTAlignment(VT
);
4259 unsigned Flags
= MachineMemOperand::MOLoad
;
4261 Flags
|= MachineMemOperand::MOVolatile
;
4263 Flags
|= MachineMemOperand::MONonTemporal
;
4265 Flags
|= MachineMemOperand::MOInvariant
;
4267 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4270 PtrInfo
= InferPointerInfo(Ptr
, Offset
);
4272 MachineFunction
&MF
= getMachineFunction();
4273 MachineMemOperand
*MMO
=
4274 MF
.getMachineMemOperand(PtrInfo
, Flags
, MemVT
.getStoreSize(), Alignment
,
4276 return getLoad(AM
, ExtType
, VT
, dl
, Chain
, Ptr
, Offset
, MemVT
, MMO
);
4280 SelectionDAG::getLoad(ISD::MemIndexedMode AM
, ISD::LoadExtType ExtType
,
4281 EVT VT
, DebugLoc dl
, SDValue Chain
,
4282 SDValue Ptr
, SDValue Offset
, EVT MemVT
,
4283 MachineMemOperand
*MMO
) {
4285 ExtType
= ISD::NON_EXTLOAD
;
4286 } else if (ExtType
== ISD::NON_EXTLOAD
) {
4287 assert(VT
== MemVT
&& "Non-extending load from different memory type!");
4290 assert(MemVT
.getScalarType().bitsLT(VT
.getScalarType()) &&
4291 "Should only be an extending load, not truncating!");
4292 assert(VT
.isInteger() == MemVT
.isInteger() &&
4293 "Cannot convert from FP to Int or Int -> FP!");
4294 assert(VT
.isVector() == MemVT
.isVector() &&
4295 "Cannot use trunc store to convert to or from a vector!");
4296 assert((!VT
.isVector() ||
4297 VT
.getVectorNumElements() == MemVT
.getVectorNumElements()) &&
4298 "Cannot use trunc store to change the number of vector elements!");
4301 bool Indexed
= AM
!= ISD::UNINDEXED
;
4302 assert((Indexed
|| Offset
.getOpcode() == ISD::UNDEF
) &&
4303 "Unindexed load with an offset!");
4305 SDVTList VTs
= Indexed
?
4306 getVTList(VT
, Ptr
.getValueType(), MVT::Other
) : getVTList(VT
, MVT::Other
);
4307 SDValue Ops
[] = { Chain
, Ptr
, Offset
};
4308 FoldingSetNodeID ID
;
4309 AddNodeIDNode(ID
, ISD::LOAD
, VTs
, Ops
, 3);
4310 ID
.AddInteger(MemVT
.getRawBits());
4311 ID
.AddInteger(encodeMemSDNodeFlags(ExtType
, AM
, MMO
->isVolatile(),
4312 MMO
->isNonTemporal(),
4313 MMO
->isInvariant()));
4314 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4316 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4317 cast
<LoadSDNode
>(E
)->refineAlignment(MMO
);
4318 return SDValue(E
, 0);
4320 SDNode
*N
= new (NodeAllocator
) LoadSDNode(Ops
, dl
, VTs
, AM
, ExtType
,
4322 CSEMap
.InsertNode(N
, IP
);
4323 AllNodes
.push_back(N
);
4324 return SDValue(N
, 0);
4327 SDValue
SelectionDAG::getLoad(EVT VT
, DebugLoc dl
,
4328 SDValue Chain
, SDValue Ptr
,
4329 MachinePointerInfo PtrInfo
,
4330 bool isVolatile
, bool isNonTemporal
,
4331 bool isInvariant
, unsigned Alignment
,
4332 const MDNode
*TBAAInfo
,
4333 const MDNode
*Ranges
) {
4334 SDValue Undef
= getUNDEF(Ptr
.getValueType());
4335 return getLoad(ISD::UNINDEXED
, ISD::NON_EXTLOAD
, VT
, dl
, Chain
, Ptr
, Undef
,
4336 PtrInfo
, VT
, isVolatile
, isNonTemporal
, isInvariant
, Alignment
,
4340 SDValue
SelectionDAG::getExtLoad(ISD::LoadExtType ExtType
, DebugLoc dl
, EVT VT
,
4341 SDValue Chain
, SDValue Ptr
,
4342 MachinePointerInfo PtrInfo
, EVT MemVT
,
4343 bool isVolatile
, bool isNonTemporal
,
4344 unsigned Alignment
, const MDNode
*TBAAInfo
) {
4345 SDValue Undef
= getUNDEF(Ptr
.getValueType());
4346 return getLoad(ISD::UNINDEXED
, ExtType
, VT
, dl
, Chain
, Ptr
, Undef
,
4347 PtrInfo
, MemVT
, isVolatile
, isNonTemporal
, false, Alignment
,
4353 SelectionDAG::getIndexedLoad(SDValue OrigLoad
, DebugLoc dl
, SDValue Base
,
4354 SDValue Offset
, ISD::MemIndexedMode AM
) {
4355 LoadSDNode
*LD
= cast
<LoadSDNode
>(OrigLoad
);
4356 assert(LD
->getOffset().getOpcode() == ISD::UNDEF
&&
4357 "Load is already a indexed load!");
4358 return getLoad(AM
, LD
->getExtensionType(), OrigLoad
.getValueType(), dl
,
4359 LD
->getChain(), Base
, Offset
, LD
->getPointerInfo(),
4360 LD
->getMemoryVT(), LD
->isVolatile(), LD
->isNonTemporal(),
4361 false, LD
->getAlignment());
4364 SDValue
SelectionDAG::getStore(SDValue Chain
, DebugLoc dl
, SDValue Val
,
4365 SDValue Ptr
, MachinePointerInfo PtrInfo
,
4366 bool isVolatile
, bool isNonTemporal
,
4367 unsigned Alignment
, const MDNode
*TBAAInfo
) {
4368 assert(Chain
.getValueType() == MVT::Other
&&
4369 "Invalid chain type");
4370 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
4371 Alignment
= getEVTAlignment(Val
.getValueType());
4373 unsigned Flags
= MachineMemOperand::MOStore
;
4375 Flags
|= MachineMemOperand::MOVolatile
;
4377 Flags
|= MachineMemOperand::MONonTemporal
;
4380 PtrInfo
= InferPointerInfo(Ptr
);
4382 MachineFunction
&MF
= getMachineFunction();
4383 MachineMemOperand
*MMO
=
4384 MF
.getMachineMemOperand(PtrInfo
, Flags
,
4385 Val
.getValueType().getStoreSize(), Alignment
,
4388 return getStore(Chain
, dl
, Val
, Ptr
, MMO
);
4391 SDValue
SelectionDAG::getStore(SDValue Chain
, DebugLoc dl
, SDValue Val
,
4392 SDValue Ptr
, MachineMemOperand
*MMO
) {
4393 assert(Chain
.getValueType() == MVT::Other
&&
4394 "Invalid chain type");
4395 EVT VT
= Val
.getValueType();
4396 SDVTList VTs
= getVTList(MVT::Other
);
4397 SDValue Undef
= getUNDEF(Ptr
.getValueType());
4398 SDValue Ops
[] = { Chain
, Val
, Ptr
, Undef
};
4399 FoldingSetNodeID ID
;
4400 AddNodeIDNode(ID
, ISD::STORE
, VTs
, Ops
, 4);
4401 ID
.AddInteger(VT
.getRawBits());
4402 ID
.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED
, MMO
->isVolatile(),
4403 MMO
->isNonTemporal(), MMO
->isInvariant()));
4404 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4406 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4407 cast
<StoreSDNode
>(E
)->refineAlignment(MMO
);
4408 return SDValue(E
, 0);
4410 SDNode
*N
= new (NodeAllocator
) StoreSDNode(Ops
, dl
, VTs
, ISD::UNINDEXED
,
4412 CSEMap
.InsertNode(N
, IP
);
4413 AllNodes
.push_back(N
);
4414 return SDValue(N
, 0);
4417 SDValue
SelectionDAG::getTruncStore(SDValue Chain
, DebugLoc dl
, SDValue Val
,
4418 SDValue Ptr
, MachinePointerInfo PtrInfo
,
4419 EVT SVT
,bool isVolatile
, bool isNonTemporal
,
4421 const MDNode
*TBAAInfo
) {
4422 assert(Chain
.getValueType() == MVT::Other
&&
4423 "Invalid chain type");
4424 if (Alignment
== 0) // Ensure that codegen never sees alignment 0
4425 Alignment
= getEVTAlignment(SVT
);
4427 unsigned Flags
= MachineMemOperand::MOStore
;
4429 Flags
|= MachineMemOperand::MOVolatile
;
4431 Flags
|= MachineMemOperand::MONonTemporal
;
4434 PtrInfo
= InferPointerInfo(Ptr
);
4436 MachineFunction
&MF
= getMachineFunction();
4437 MachineMemOperand
*MMO
=
4438 MF
.getMachineMemOperand(PtrInfo
, Flags
, SVT
.getStoreSize(), Alignment
,
4441 return getTruncStore(Chain
, dl
, Val
, Ptr
, SVT
, MMO
);
4444 SDValue
SelectionDAG::getTruncStore(SDValue Chain
, DebugLoc dl
, SDValue Val
,
4445 SDValue Ptr
, EVT SVT
,
4446 MachineMemOperand
*MMO
) {
4447 EVT VT
= Val
.getValueType();
4449 assert(Chain
.getValueType() == MVT::Other
&&
4450 "Invalid chain type");
4452 return getStore(Chain
, dl
, Val
, Ptr
, MMO
);
4454 assert(SVT
.getScalarType().bitsLT(VT
.getScalarType()) &&
4455 "Should only be a truncating store, not extending!");
4456 assert(VT
.isInteger() == SVT
.isInteger() &&
4457 "Can't do FP-INT conversion!");
4458 assert(VT
.isVector() == SVT
.isVector() &&
4459 "Cannot use trunc store to convert to or from a vector!");
4460 assert((!VT
.isVector() ||
4461 VT
.getVectorNumElements() == SVT
.getVectorNumElements()) &&
4462 "Cannot use trunc store to change the number of vector elements!");
4464 SDVTList VTs
= getVTList(MVT::Other
);
4465 SDValue Undef
= getUNDEF(Ptr
.getValueType());
4466 SDValue Ops
[] = { Chain
, Val
, Ptr
, Undef
};
4467 FoldingSetNodeID ID
;
4468 AddNodeIDNode(ID
, ISD::STORE
, VTs
, Ops
, 4);
4469 ID
.AddInteger(SVT
.getRawBits());
4470 ID
.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED
, MMO
->isVolatile(),
4471 MMO
->isNonTemporal(), MMO
->isInvariant()));
4472 ID
.AddInteger(MMO
->getPointerInfo().getAddrSpace());
4474 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
4475 cast
<StoreSDNode
>(E
)->refineAlignment(MMO
);
4476 return SDValue(E
, 0);
4478 SDNode
*N
= new (NodeAllocator
) StoreSDNode(Ops
, dl
, VTs
, ISD::UNINDEXED
,
4480 CSEMap
.InsertNode(N
, IP
);
4481 AllNodes
.push_back(N
);
4482 return SDValue(N
, 0);
4486 SelectionDAG::getIndexedStore(SDValue OrigStore
, DebugLoc dl
, SDValue Base
,
4487 SDValue Offset
, ISD::MemIndexedMode AM
) {
4488 StoreSDNode
*ST
= cast
<StoreSDNode
>(OrigStore
);
4489 assert(ST
->getOffset().getOpcode() == ISD::UNDEF
&&
4490 "Store is already a indexed store!");
4491 SDVTList VTs
= getVTList(Base
.getValueType(), MVT::Other
);
4492 SDValue Ops
[] = { ST
->getChain(), ST
->getValue(), Base
, Offset
};
4493 FoldingSetNodeID ID
;
4494 AddNodeIDNode(ID
, ISD::STORE
, VTs
, Ops
, 4);
4495 ID
.AddInteger(ST
->getMemoryVT().getRawBits());
4496 ID
.AddInteger(ST
->getRawSubclassData());
4497 ID
.AddInteger(ST
->getPointerInfo().getAddrSpace());
4499 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
4500 return SDValue(E
, 0);
4502 SDNode
*N
= new (NodeAllocator
) StoreSDNode(Ops
, dl
, VTs
, AM
,
4503 ST
->isTruncatingStore(),
4505 ST
->getMemOperand());
4506 CSEMap
.InsertNode(N
, IP
);
4507 AllNodes
.push_back(N
);
4508 return SDValue(N
, 0);
4511 SDValue
SelectionDAG::getVAArg(EVT VT
, DebugLoc dl
,
4512 SDValue Chain
, SDValue Ptr
,
4515 SDValue Ops
[] = { Chain
, Ptr
, SV
, getTargetConstant(Align
, MVT::i32
) };
4516 return getNode(ISD::VAARG
, dl
, getVTList(VT
, MVT::Other
), Ops
, 4);
4519 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
4520 const SDUse
*Ops
, unsigned NumOps
) {
4522 case 0: return getNode(Opcode
, DL
, VT
);
4523 case 1: return getNode(Opcode
, DL
, VT
, Ops
[0]);
4524 case 2: return getNode(Opcode
, DL
, VT
, Ops
[0], Ops
[1]);
4525 case 3: return getNode(Opcode
, DL
, VT
, Ops
[0], Ops
[1], Ops
[2]);
4529 // Copy from an SDUse array into an SDValue array for use with
4530 // the regular getNode logic.
4531 SmallVector
<SDValue
, 8> NewOps(Ops
, Ops
+ NumOps
);
4532 return getNode(Opcode
, DL
, VT
, &NewOps
[0], NumOps
);
4535 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, EVT VT
,
4536 const SDValue
*Ops
, unsigned NumOps
) {
4538 case 0: return getNode(Opcode
, DL
, VT
);
4539 case 1: return getNode(Opcode
, DL
, VT
, Ops
[0]);
4540 case 2: return getNode(Opcode
, DL
, VT
, Ops
[0], Ops
[1]);
4541 case 3: return getNode(Opcode
, DL
, VT
, Ops
[0], Ops
[1], Ops
[2]);
4547 case ISD::SELECT_CC
: {
4548 assert(NumOps
== 5 && "SELECT_CC takes 5 operands!");
4549 assert(Ops
[0].getValueType() == Ops
[1].getValueType() &&
4550 "LHS and RHS of condition must have same type!");
4551 assert(Ops
[2].getValueType() == Ops
[3].getValueType() &&
4552 "True and False arms of SelectCC must have same type!");
4553 assert(Ops
[2].getValueType() == VT
&&
4554 "select_cc node must be of same type as true and false value!");
4558 assert(NumOps
== 5 && "BR_CC takes 5 operands!");
4559 assert(Ops
[2].getValueType() == Ops
[3].getValueType() &&
4560 "LHS/RHS of comparison should match types!");
4567 SDVTList VTs
= getVTList(VT
);
4569 if (VT
!= MVT::Glue
) {
4570 FoldingSetNodeID ID
;
4571 AddNodeIDNode(ID
, Opcode
, VTs
, Ops
, NumOps
);
4574 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
4575 return SDValue(E
, 0);
4577 N
= new (NodeAllocator
) SDNode(Opcode
, DL
, VTs
, Ops
, NumOps
);
4578 CSEMap
.InsertNode(N
, IP
);
4580 N
= new (NodeAllocator
) SDNode(Opcode
, DL
, VTs
, Ops
, NumOps
);
4583 AllNodes
.push_back(N
);
4587 return SDValue(N
, 0);
4590 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
,
4591 const std::vector
<EVT
> &ResultTys
,
4592 const SDValue
*Ops
, unsigned NumOps
) {
4593 return getNode(Opcode
, DL
, getVTList(&ResultTys
[0], ResultTys
.size()),
4597 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
,
4598 const EVT
*VTs
, unsigned NumVTs
,
4599 const SDValue
*Ops
, unsigned NumOps
) {
4601 return getNode(Opcode
, DL
, VTs
[0], Ops
, NumOps
);
4602 return getNode(Opcode
, DL
, makeVTList(VTs
, NumVTs
), Ops
, NumOps
);
4605 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4606 const SDValue
*Ops
, unsigned NumOps
) {
4607 if (VTList
.NumVTs
== 1)
4608 return getNode(Opcode
, DL
, VTList
.VTs
[0], Ops
, NumOps
);
4612 // FIXME: figure out how to safely handle things like
4613 // int foo(int x) { return 1 << (x & 255); }
4614 // int bar() { return foo(256); }
4615 case ISD::SRA_PARTS
:
4616 case ISD::SRL_PARTS
:
4617 case ISD::SHL_PARTS
:
4618 if (N3
.getOpcode() == ISD::SIGN_EXTEND_INREG
&&
4619 cast
<VTSDNode
>(N3
.getOperand(1))->getVT() != MVT::i1
)
4620 return getNode(Opcode
, DL
, VT
, N1
, N2
, N3
.getOperand(0));
4621 else if (N3
.getOpcode() == ISD::AND
)
4622 if (ConstantSDNode
*AndRHS
= dyn_cast
<ConstantSDNode
>(N3
.getOperand(1))) {
4623 // If the and is only masking out bits that cannot effect the shift,
4624 // eliminate the and.
4625 unsigned NumBits
= VT
.getScalarType().getSizeInBits()*2;
4626 if ((AndRHS
->getValue() & (NumBits
-1)) == NumBits
-1)
4627 return getNode(Opcode
, DL
, VT
, N1
, N2
, N3
.getOperand(0));
4633 // Memoize the node unless it returns a flag.
4635 if (VTList
.VTs
[VTList
.NumVTs
-1] != MVT::Glue
) {
4636 FoldingSetNodeID ID
;
4637 AddNodeIDNode(ID
, Opcode
, VTList
, Ops
, NumOps
);
4639 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
4640 return SDValue(E
, 0);
4643 N
= new (NodeAllocator
) UnarySDNode(Opcode
, DL
, VTList
, Ops
[0]);
4644 } else if (NumOps
== 2) {
4645 N
= new (NodeAllocator
) BinarySDNode(Opcode
, DL
, VTList
, Ops
[0], Ops
[1]);
4646 } else if (NumOps
== 3) {
4647 N
= new (NodeAllocator
) TernarySDNode(Opcode
, DL
, VTList
, Ops
[0], Ops
[1],
4650 N
= new (NodeAllocator
) SDNode(Opcode
, DL
, VTList
, Ops
, NumOps
);
4652 CSEMap
.InsertNode(N
, IP
);
4655 N
= new (NodeAllocator
) UnarySDNode(Opcode
, DL
, VTList
, Ops
[0]);
4656 } else if (NumOps
== 2) {
4657 N
= new (NodeAllocator
) BinarySDNode(Opcode
, DL
, VTList
, Ops
[0], Ops
[1]);
4658 } else if (NumOps
== 3) {
4659 N
= new (NodeAllocator
) TernarySDNode(Opcode
, DL
, VTList
, Ops
[0], Ops
[1],
4662 N
= new (NodeAllocator
) SDNode(Opcode
, DL
, VTList
, Ops
, NumOps
);
4665 AllNodes
.push_back(N
);
4669 return SDValue(N
, 0);
4672 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
) {
4673 return getNode(Opcode
, DL
, VTList
, 0, 0);
4676 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4678 SDValue Ops
[] = { N1
};
4679 return getNode(Opcode
, DL
, VTList
, Ops
, 1);
4682 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4683 SDValue N1
, SDValue N2
) {
4684 SDValue Ops
[] = { N1
, N2
};
4685 return getNode(Opcode
, DL
, VTList
, Ops
, 2);
4688 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4689 SDValue N1
, SDValue N2
, SDValue N3
) {
4690 SDValue Ops
[] = { N1
, N2
, N3
};
4691 return getNode(Opcode
, DL
, VTList
, Ops
, 3);
4694 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4695 SDValue N1
, SDValue N2
, SDValue N3
,
4697 SDValue Ops
[] = { N1
, N2
, N3
, N4
};
4698 return getNode(Opcode
, DL
, VTList
, Ops
, 4);
4701 SDValue
SelectionDAG::getNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTList
,
4702 SDValue N1
, SDValue N2
, SDValue N3
,
4703 SDValue N4
, SDValue N5
) {
4704 SDValue Ops
[] = { N1
, N2
, N3
, N4
, N5
};
4705 return getNode(Opcode
, DL
, VTList
, Ops
, 5);
4708 SDVTList
SelectionDAG::getVTList(EVT VT
) {
4709 return makeVTList(SDNode::getValueTypeList(VT
), 1);
4712 SDVTList
SelectionDAG::getVTList(EVT VT1
, EVT VT2
) {
4713 for (std::vector
<SDVTList
>::reverse_iterator I
= VTList
.rbegin(),
4714 E
= VTList
.rend(); I
!= E
; ++I
)
4715 if (I
->NumVTs
== 2 && I
->VTs
[0] == VT1
&& I
->VTs
[1] == VT2
)
4718 EVT
*Array
= Allocator
.Allocate
<EVT
>(2);
4721 SDVTList Result
= makeVTList(Array
, 2);
4722 VTList
.push_back(Result
);
4726 SDVTList
SelectionDAG::getVTList(EVT VT1
, EVT VT2
, EVT VT3
) {
4727 for (std::vector
<SDVTList
>::reverse_iterator I
= VTList
.rbegin(),
4728 E
= VTList
.rend(); I
!= E
; ++I
)
4729 if (I
->NumVTs
== 3 && I
->VTs
[0] == VT1
&& I
->VTs
[1] == VT2
&&
4733 EVT
*Array
= Allocator
.Allocate
<EVT
>(3);
4737 SDVTList Result
= makeVTList(Array
, 3);
4738 VTList
.push_back(Result
);
4742 SDVTList
SelectionDAG::getVTList(EVT VT1
, EVT VT2
, EVT VT3
, EVT VT4
) {
4743 for (std::vector
<SDVTList
>::reverse_iterator I
= VTList
.rbegin(),
4744 E
= VTList
.rend(); I
!= E
; ++I
)
4745 if (I
->NumVTs
== 4 && I
->VTs
[0] == VT1
&& I
->VTs
[1] == VT2
&&
4746 I
->VTs
[2] == VT3
&& I
->VTs
[3] == VT4
)
4749 EVT
*Array
= Allocator
.Allocate
<EVT
>(4);
4754 SDVTList Result
= makeVTList(Array
, 4);
4755 VTList
.push_back(Result
);
4759 SDVTList
SelectionDAG::getVTList(const EVT
*VTs
, unsigned NumVTs
) {
4761 case 0: llvm_unreachable("Cannot have nodes without results!");
4762 case 1: return getVTList(VTs
[0]);
4763 case 2: return getVTList(VTs
[0], VTs
[1]);
4764 case 3: return getVTList(VTs
[0], VTs
[1], VTs
[2]);
4765 case 4: return getVTList(VTs
[0], VTs
[1], VTs
[2], VTs
[3]);
4769 for (std::vector
<SDVTList
>::reverse_iterator I
= VTList
.rbegin(),
4770 E
= VTList
.rend(); I
!= E
; ++I
) {
4771 if (I
->NumVTs
!= NumVTs
|| VTs
[0] != I
->VTs
[0] || VTs
[1] != I
->VTs
[1])
4774 if (std::equal(&VTs
[2], &VTs
[NumVTs
], &I
->VTs
[2]))
4778 EVT
*Array
= Allocator
.Allocate
<EVT
>(NumVTs
);
4779 std::copy(VTs
, VTs
+NumVTs
, Array
);
4780 SDVTList Result
= makeVTList(Array
, NumVTs
);
4781 VTList
.push_back(Result
);
4786 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
4787 /// specified operands. If the resultant node already exists in the DAG,
4788 /// this does not modify the specified node, instead it returns the node that
4789 /// already exists. If the resultant node does not exist in the DAG, the
4790 /// input node is returned. As a degenerate case, if you specify the same
4791 /// input operands as the node already has, the input node is returned.
4792 SDNode
*SelectionDAG::UpdateNodeOperands(SDNode
*N
, SDValue Op
) {
4793 assert(N
->getNumOperands() == 1 && "Update with wrong number of operands");
4795 // Check to see if there is no change.
4796 if (Op
== N
->getOperand(0)) return N
;
4798 // See if the modified node already exists.
4799 void *InsertPos
= 0;
4800 if (SDNode
*Existing
= FindModifiedNodeSlot(N
, Op
, InsertPos
))
4803 // Nope it doesn't. Remove the node from its current place in the maps.
4805 if (!RemoveNodeFromCSEMaps(N
))
4808 // Now we update the operands.
4809 N
->OperandList
[0].set(Op
);
4811 // If this gets put into a CSE map, add it.
4812 if (InsertPos
) CSEMap
.InsertNode(N
, InsertPos
);
4816 SDNode
*SelectionDAG::UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
) {
4817 assert(N
->getNumOperands() == 2 && "Update with wrong number of operands");
4819 // Check to see if there is no change.
4820 if (Op1
== N
->getOperand(0) && Op2
== N
->getOperand(1))
4821 return N
; // No operands changed, just return the input node.
4823 // See if the modified node already exists.
4824 void *InsertPos
= 0;
4825 if (SDNode
*Existing
= FindModifiedNodeSlot(N
, Op1
, Op2
, InsertPos
))
4828 // Nope it doesn't. Remove the node from its current place in the maps.
4830 if (!RemoveNodeFromCSEMaps(N
))
4833 // Now we update the operands.
4834 if (N
->OperandList
[0] != Op1
)
4835 N
->OperandList
[0].set(Op1
);
4836 if (N
->OperandList
[1] != Op2
)
4837 N
->OperandList
[1].set(Op2
);
4839 // If this gets put into a CSE map, add it.
4840 if (InsertPos
) CSEMap
.InsertNode(N
, InsertPos
);
4844 SDNode
*SelectionDAG::
4845 UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
, SDValue Op3
) {
4846 SDValue Ops
[] = { Op1
, Op2
, Op3
};
4847 return UpdateNodeOperands(N
, Ops
, 3);
4850 SDNode
*SelectionDAG::
4851 UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
,
4852 SDValue Op3
, SDValue Op4
) {
4853 SDValue Ops
[] = { Op1
, Op2
, Op3
, Op4
};
4854 return UpdateNodeOperands(N
, Ops
, 4);
4857 SDNode
*SelectionDAG::
4858 UpdateNodeOperands(SDNode
*N
, SDValue Op1
, SDValue Op2
,
4859 SDValue Op3
, SDValue Op4
, SDValue Op5
) {
4860 SDValue Ops
[] = { Op1
, Op2
, Op3
, Op4
, Op5
};
4861 return UpdateNodeOperands(N
, Ops
, 5);
4864 SDNode
*SelectionDAG::
4865 UpdateNodeOperands(SDNode
*N
, const SDValue
*Ops
, unsigned NumOps
) {
4866 assert(N
->getNumOperands() == NumOps
&&
4867 "Update with wrong number of operands");
4869 // Check to see if there is no change.
4870 bool AnyChange
= false;
4871 for (unsigned i
= 0; i
!= NumOps
; ++i
) {
4872 if (Ops
[i
] != N
->getOperand(i
)) {
4878 // No operands changed, just return the input node.
4879 if (!AnyChange
) return N
;
4881 // See if the modified node already exists.
4882 void *InsertPos
= 0;
4883 if (SDNode
*Existing
= FindModifiedNodeSlot(N
, Ops
, NumOps
, InsertPos
))
4886 // Nope it doesn't. Remove the node from its current place in the maps.
4888 if (!RemoveNodeFromCSEMaps(N
))
4891 // Now we update the operands.
4892 for (unsigned i
= 0; i
!= NumOps
; ++i
)
4893 if (N
->OperandList
[i
] != Ops
[i
])
4894 N
->OperandList
[i
].set(Ops
[i
]);
4896 // If this gets put into a CSE map, add it.
4897 if (InsertPos
) CSEMap
.InsertNode(N
, InsertPos
);
4901 /// DropOperands - Release the operands and set this node to have
4903 void SDNode::DropOperands() {
4904 // Unlike the code in MorphNodeTo that does this, we don't need to
4905 // watch for dead nodes here.
4906 for (op_iterator I
= op_begin(), E
= op_end(); I
!= E
; ) {
4912 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
4915 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4917 SDVTList VTs
= getVTList(VT
);
4918 return SelectNodeTo(N
, MachineOpc
, VTs
, 0, 0);
4921 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4922 EVT VT
, SDValue Op1
) {
4923 SDVTList VTs
= getVTList(VT
);
4924 SDValue Ops
[] = { Op1
};
4925 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 1);
4928 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4929 EVT VT
, SDValue Op1
,
4931 SDVTList VTs
= getVTList(VT
);
4932 SDValue Ops
[] = { Op1
, Op2
};
4933 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 2);
4936 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4937 EVT VT
, SDValue Op1
,
4938 SDValue Op2
, SDValue Op3
) {
4939 SDVTList VTs
= getVTList(VT
);
4940 SDValue Ops
[] = { Op1
, Op2
, Op3
};
4941 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 3);
4944 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4945 EVT VT
, const SDValue
*Ops
,
4947 SDVTList VTs
= getVTList(VT
);
4948 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, NumOps
);
4951 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4952 EVT VT1
, EVT VT2
, const SDValue
*Ops
,
4954 SDVTList VTs
= getVTList(VT1
, VT2
);
4955 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, NumOps
);
4958 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4960 SDVTList VTs
= getVTList(VT1
, VT2
);
4961 return SelectNodeTo(N
, MachineOpc
, VTs
, (SDValue
*)0, 0);
4964 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4965 EVT VT1
, EVT VT2
, EVT VT3
,
4966 const SDValue
*Ops
, unsigned NumOps
) {
4967 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
);
4968 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, NumOps
);
4971 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4972 EVT VT1
, EVT VT2
, EVT VT3
, EVT VT4
,
4973 const SDValue
*Ops
, unsigned NumOps
) {
4974 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
, VT4
);
4975 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, NumOps
);
4978 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4981 SDVTList VTs
= getVTList(VT1
, VT2
);
4982 SDValue Ops
[] = { Op1
};
4983 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 1);
4986 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4988 SDValue Op1
, SDValue Op2
) {
4989 SDVTList VTs
= getVTList(VT1
, VT2
);
4990 SDValue Ops
[] = { Op1
, Op2
};
4991 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 2);
4994 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
4996 SDValue Op1
, SDValue Op2
,
4998 SDVTList VTs
= getVTList(VT1
, VT2
);
4999 SDValue Ops
[] = { Op1
, Op2
, Op3
};
5000 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 3);
5003 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
5004 EVT VT1
, EVT VT2
, EVT VT3
,
5005 SDValue Op1
, SDValue Op2
,
5007 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
);
5008 SDValue Ops
[] = { Op1
, Op2
, Op3
};
5009 return SelectNodeTo(N
, MachineOpc
, VTs
, Ops
, 3);
5012 SDNode
*SelectionDAG::SelectNodeTo(SDNode
*N
, unsigned MachineOpc
,
5013 SDVTList VTs
, const SDValue
*Ops
,
5015 N
= MorphNodeTo(N
, ~MachineOpc
, VTs
, Ops
, NumOps
);
5016 // Reset the NodeID to -1.
5021 /// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away
5022 /// the line number information on the merged node since it is not possible to
5023 /// preserve the information that operation is associated with multiple lines.
5024 /// This will make the debugger working better at -O0, were there is a higher
5025 /// probability having other instructions associated with that line.
5027 SDNode
*SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode
*N
, DebugLoc OLoc
) {
5028 DebugLoc NLoc
= N
->getDebugLoc();
5029 if (!(NLoc
.isUnknown()) && (OptLevel
== CodeGenOpt::None
) && (OLoc
!= NLoc
)) {
5030 N
->setDebugLoc(DebugLoc());
5035 /// MorphNodeTo - This *mutates* the specified node to have the specified
5036 /// return type, opcode, and operands.
5038 /// Note that MorphNodeTo returns the resultant node. If there is already a
5039 /// node of the specified opcode and operands, it returns that node instead of
5040 /// the current one. Note that the DebugLoc need not be the same.
5042 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5043 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5044 /// node, and because it doesn't require CSE recalculation for any of
5045 /// the node's users.
5047 SDNode
*SelectionDAG::MorphNodeTo(SDNode
*N
, unsigned Opc
,
5048 SDVTList VTs
, const SDValue
*Ops
,
5050 // If an identical node already exists, use it.
5052 if (VTs
.VTs
[VTs
.NumVTs
-1] != MVT::Glue
) {
5053 FoldingSetNodeID ID
;
5054 AddNodeIDNode(ID
, Opc
, VTs
, Ops
, NumOps
);
5055 if (SDNode
*ON
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
5056 return UpdadeDebugLocOnMergedSDNode(ON
, N
->getDebugLoc());
5059 if (!RemoveNodeFromCSEMaps(N
))
5062 // Start the morphing.
5064 N
->ValueList
= VTs
.VTs
;
5065 N
->NumValues
= VTs
.NumVTs
;
5067 // Clear the operands list, updating used nodes to remove this from their
5068 // use list. Keep track of any operands that become dead as a result.
5069 SmallPtrSet
<SDNode
*, 16> DeadNodeSet
;
5070 for (SDNode::op_iterator I
= N
->op_begin(), E
= N
->op_end(); I
!= E
; ) {
5072 SDNode
*Used
= Use
.getNode();
5074 if (Used
->use_empty())
5075 DeadNodeSet
.insert(Used
);
5078 if (MachineSDNode
*MN
= dyn_cast
<MachineSDNode
>(N
)) {
5079 // Initialize the memory references information.
5080 MN
->setMemRefs(0, 0);
5081 // If NumOps is larger than the # of operands we can have in a
5082 // MachineSDNode, reallocate the operand list.
5083 if (NumOps
> MN
->NumOperands
|| !MN
->OperandsNeedDelete
) {
5084 if (MN
->OperandsNeedDelete
)
5085 delete[] MN
->OperandList
;
5086 if (NumOps
> array_lengthof(MN
->LocalOperands
))
5087 // We're creating a final node that will live unmorphed for the
5088 // remainder of the current SelectionDAG iteration, so we can allocate
5089 // the operands directly out of a pool with no recycling metadata.
5090 MN
->InitOperands(OperandAllocator
.Allocate
<SDUse
>(NumOps
),
5093 MN
->InitOperands(MN
->LocalOperands
, Ops
, NumOps
);
5094 MN
->OperandsNeedDelete
= false;
5096 MN
->InitOperands(MN
->OperandList
, Ops
, NumOps
);
5098 // If NumOps is larger than the # of operands we currently have, reallocate
5099 // the operand list.
5100 if (NumOps
> N
->NumOperands
) {
5101 if (N
->OperandsNeedDelete
)
5102 delete[] N
->OperandList
;
5103 N
->InitOperands(new SDUse
[NumOps
], Ops
, NumOps
);
5104 N
->OperandsNeedDelete
= true;
5106 N
->InitOperands(N
->OperandList
, Ops
, NumOps
);
5109 // Delete any nodes that are still dead after adding the uses for the
5111 if (!DeadNodeSet
.empty()) {
5112 SmallVector
<SDNode
*, 16> DeadNodes
;
5113 for (SmallPtrSet
<SDNode
*, 16>::iterator I
= DeadNodeSet
.begin(),
5114 E
= DeadNodeSet
.end(); I
!= E
; ++I
)
5115 if ((*I
)->use_empty())
5116 DeadNodes
.push_back(*I
);
5117 RemoveDeadNodes(DeadNodes
);
5121 CSEMap
.InsertNode(N
, IP
); // Memoize the new node.
5126 /// getMachineNode - These are used for target selectors to create a new node
5127 /// with specified return type(s), MachineInstr opcode, and operands.
5129 /// Note that getMachineNode returns the resultant node. If there is already a
5130 /// node of the specified opcode and operands, it returns that node instead of
5131 /// the current one.
5133 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT
) {
5134 SDVTList VTs
= getVTList(VT
);
5135 return getMachineNode(Opcode
, dl
, VTs
, 0, 0);
5139 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT
, SDValue Op1
) {
5140 SDVTList VTs
= getVTList(VT
);
5141 SDValue Ops
[] = { Op1
};
5142 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5146 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT
,
5147 SDValue Op1
, SDValue Op2
) {
5148 SDVTList VTs
= getVTList(VT
);
5149 SDValue Ops
[] = { Op1
, Op2
};
5150 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5154 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT
,
5155 SDValue Op1
, SDValue Op2
, SDValue Op3
) {
5156 SDVTList VTs
= getVTList(VT
);
5157 SDValue Ops
[] = { Op1
, Op2
, Op3
};
5158 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5162 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT
,
5163 const SDValue
*Ops
, unsigned NumOps
) {
5164 SDVTList VTs
= getVTList(VT
);
5165 return getMachineNode(Opcode
, dl
, VTs
, Ops
, NumOps
);
5169 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT1
, EVT VT2
) {
5170 SDVTList VTs
= getVTList(VT1
, VT2
);
5171 return getMachineNode(Opcode
, dl
, VTs
, 0, 0);
5175 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5176 EVT VT1
, EVT VT2
, SDValue Op1
) {
5177 SDVTList VTs
= getVTList(VT1
, VT2
);
5178 SDValue Ops
[] = { Op1
};
5179 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5183 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5184 EVT VT1
, EVT VT2
, SDValue Op1
, SDValue Op2
) {
5185 SDVTList VTs
= getVTList(VT1
, VT2
);
5186 SDValue Ops
[] = { Op1
, Op2
};
5187 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5191 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5192 EVT VT1
, EVT VT2
, SDValue Op1
,
5193 SDValue Op2
, SDValue Op3
) {
5194 SDVTList VTs
= getVTList(VT1
, VT2
);
5195 SDValue Ops
[] = { Op1
, Op2
, Op3
};
5196 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5200 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5202 const SDValue
*Ops
, unsigned NumOps
) {
5203 SDVTList VTs
= getVTList(VT1
, VT2
);
5204 return getMachineNode(Opcode
, dl
, VTs
, Ops
, NumOps
);
5208 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5209 EVT VT1
, EVT VT2
, EVT VT3
,
5210 SDValue Op1
, SDValue Op2
) {
5211 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
);
5212 SDValue Ops
[] = { Op1
, Op2
};
5213 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5217 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5218 EVT VT1
, EVT VT2
, EVT VT3
,
5219 SDValue Op1
, SDValue Op2
, SDValue Op3
) {
5220 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
);
5221 SDValue Ops
[] = { Op1
, Op2
, Op3
};
5222 return getMachineNode(Opcode
, dl
, VTs
, Ops
, array_lengthof(Ops
));
5226 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5227 EVT VT1
, EVT VT2
, EVT VT3
,
5228 const SDValue
*Ops
, unsigned NumOps
) {
5229 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
);
5230 return getMachineNode(Opcode
, dl
, VTs
, Ops
, NumOps
);
5234 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
, EVT VT1
,
5235 EVT VT2
, EVT VT3
, EVT VT4
,
5236 const SDValue
*Ops
, unsigned NumOps
) {
5237 SDVTList VTs
= getVTList(VT1
, VT2
, VT3
, VT4
);
5238 return getMachineNode(Opcode
, dl
, VTs
, Ops
, NumOps
);
5242 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc dl
,
5243 const std::vector
<EVT
> &ResultTys
,
5244 const SDValue
*Ops
, unsigned NumOps
) {
5245 SDVTList VTs
= getVTList(&ResultTys
[0], ResultTys
.size());
5246 return getMachineNode(Opcode
, dl
, VTs
, Ops
, NumOps
);
5250 SelectionDAG::getMachineNode(unsigned Opcode
, DebugLoc DL
, SDVTList VTs
,
5251 const SDValue
*Ops
, unsigned NumOps
) {
5252 bool DoCSE
= VTs
.VTs
[VTs
.NumVTs
-1] != MVT::Glue
;
5257 FoldingSetNodeID ID
;
5258 AddNodeIDNode(ID
, ~Opcode
, VTs
, Ops
, NumOps
);
5260 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
)) {
5261 return cast
<MachineSDNode
>(UpdadeDebugLocOnMergedSDNode(E
, DL
));
5265 // Allocate a new MachineSDNode.
5266 N
= new (NodeAllocator
) MachineSDNode(~Opcode
, DL
, VTs
);
5268 // Initialize the operands list.
5269 if (NumOps
> array_lengthof(N
->LocalOperands
))
5270 // We're creating a final node that will live unmorphed for the
5271 // remainder of the current SelectionDAG iteration, so we can allocate
5272 // the operands directly out of a pool with no recycling metadata.
5273 N
->InitOperands(OperandAllocator
.Allocate
<SDUse
>(NumOps
),
5276 N
->InitOperands(N
->LocalOperands
, Ops
, NumOps
);
5277 N
->OperandsNeedDelete
= false;
5280 CSEMap
.InsertNode(N
, IP
);
5282 AllNodes
.push_back(N
);
5284 VerifyMachineNode(N
);
5289 /// getTargetExtractSubreg - A convenience function for creating
5290 /// TargetOpcode::EXTRACT_SUBREG nodes.
5292 SelectionDAG::getTargetExtractSubreg(int SRIdx
, DebugLoc DL
, EVT VT
,
5294 SDValue SRIdxVal
= getTargetConstant(SRIdx
, MVT::i32
);
5295 SDNode
*Subreg
= getMachineNode(TargetOpcode::EXTRACT_SUBREG
, DL
,
5296 VT
, Operand
, SRIdxVal
);
5297 return SDValue(Subreg
, 0);
5300 /// getTargetInsertSubreg - A convenience function for creating
5301 /// TargetOpcode::INSERT_SUBREG nodes.
5303 SelectionDAG::getTargetInsertSubreg(int SRIdx
, DebugLoc DL
, EVT VT
,
5304 SDValue Operand
, SDValue Subreg
) {
5305 SDValue SRIdxVal
= getTargetConstant(SRIdx
, MVT::i32
);
5306 SDNode
*Result
= getMachineNode(TargetOpcode::INSERT_SUBREG
, DL
,
5307 VT
, Operand
, Subreg
, SRIdxVal
);
5308 return SDValue(Result
, 0);
5311 /// getNodeIfExists - Get the specified node if it's already available, or
5312 /// else return NULL.
5313 SDNode
*SelectionDAG::getNodeIfExists(unsigned Opcode
, SDVTList VTList
,
5314 const SDValue
*Ops
, unsigned NumOps
) {
5315 if (VTList
.VTs
[VTList
.NumVTs
-1] != MVT::Glue
) {
5316 FoldingSetNodeID ID
;
5317 AddNodeIDNode(ID
, Opcode
, VTList
, Ops
, NumOps
);
5319 if (SDNode
*E
= CSEMap
.FindNodeOrInsertPos(ID
, IP
))
5325 /// getDbgValue - Creates a SDDbgValue node.
5328 SelectionDAG::getDbgValue(MDNode
*MDPtr
, SDNode
*N
, unsigned R
, uint64_t Off
,
5329 DebugLoc DL
, unsigned O
) {
5330 return new (Allocator
) SDDbgValue(MDPtr
, N
, R
, Off
, DL
, O
);
5334 SelectionDAG::getDbgValue(MDNode
*MDPtr
, const Value
*C
, uint64_t Off
,
5335 DebugLoc DL
, unsigned O
) {
5336 return new (Allocator
) SDDbgValue(MDPtr
, C
, Off
, DL
, O
);
5340 SelectionDAG::getDbgValue(MDNode
*MDPtr
, unsigned FI
, uint64_t Off
,
5341 DebugLoc DL
, unsigned O
) {
5342 return new (Allocator
) SDDbgValue(MDPtr
, FI
, Off
, DL
, O
);
5347 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5348 /// pointed to by a use iterator is deleted, increment the use iterator
5349 /// so that it doesn't dangle.
5351 class RAUWUpdateListener
: public SelectionDAG::DAGUpdateListener
{
5352 SDNode::use_iterator
&UI
;
5353 SDNode::use_iterator
&UE
;
5355 virtual void NodeDeleted(SDNode
*N
, SDNode
*E
) {
5356 // Increment the iterator as needed.
5357 while (UI
!= UE
&& N
== *UI
)
5362 RAUWUpdateListener(SelectionDAG
&d
,
5363 SDNode::use_iterator
&ui
,
5364 SDNode::use_iterator
&ue
)
5365 : SelectionDAG::DAGUpdateListener(d
), UI(ui
), UE(ue
) {}
5370 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5371 /// This can cause recursive merging of nodes in the DAG.
5373 /// This version assumes From has a single result value.
5375 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN
, SDValue To
) {
5376 SDNode
*From
= FromN
.getNode();
5377 assert(From
->getNumValues() == 1 && FromN
.getResNo() == 0 &&
5378 "Cannot replace with this method!");
5379 assert(From
!= To
.getNode() && "Cannot replace uses of with self");
5381 // Iterate over all the existing uses of From. New uses will be added
5382 // to the beginning of the use list, which we avoid visiting.
5383 // This specifically avoids visiting uses of From that arise while the
5384 // replacement is happening, because any such uses would be the result
5385 // of CSE: If an existing node looks like From after one of its operands
5386 // is replaced by To, we don't want to replace of all its users with To
5387 // too. See PR3018 for more info.
5388 SDNode::use_iterator UI
= From
->use_begin(), UE
= From
->use_end();
5389 RAUWUpdateListener
Listener(*this, UI
, UE
);
5393 // This node is about to morph, remove its old self from the CSE maps.
5394 RemoveNodeFromCSEMaps(User
);
5396 // A user can appear in a use list multiple times, and when this
5397 // happens the uses are usually next to each other in the list.
5398 // To help reduce the number of CSE recomputations, process all
5399 // the uses of this user that we can find this way.
5401 SDUse
&Use
= UI
.getUse();
5404 } while (UI
!= UE
&& *UI
== User
);
5406 // Now that we have modified User, add it back to the CSE maps. If it
5407 // already exists there, recursively merge the results together.
5408 AddModifiedNodeToCSEMaps(User
);
5411 // If we just RAUW'd the root, take note.
5412 if (FromN
== getRoot())
5416 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5417 /// This can cause recursive merging of nodes in the DAG.
5419 /// This version assumes that for each value of From, there is a
5420 /// corresponding value in To in the same position with the same type.
5422 void SelectionDAG::ReplaceAllUsesWith(SDNode
*From
, SDNode
*To
) {
5424 for (unsigned i
= 0, e
= From
->getNumValues(); i
!= e
; ++i
)
5425 assert((!From
->hasAnyUseOfValue(i
) ||
5426 From
->getValueType(i
) == To
->getValueType(i
)) &&
5427 "Cannot use this version of ReplaceAllUsesWith!");
5430 // Handle the trivial case.
5434 // Iterate over just the existing users of From. See the comments in
5435 // the ReplaceAllUsesWith above.
5436 SDNode::use_iterator UI
= From
->use_begin(), UE
= From
->use_end();
5437 RAUWUpdateListener
Listener(*this, UI
, UE
);
5441 // This node is about to morph, remove its old self from the CSE maps.
5442 RemoveNodeFromCSEMaps(User
);
5444 // A user can appear in a use list multiple times, and when this
5445 // happens the uses are usually next to each other in the list.
5446 // To help reduce the number of CSE recomputations, process all
5447 // the uses of this user that we can find this way.
5449 SDUse
&Use
= UI
.getUse();
5452 } while (UI
!= UE
&& *UI
== User
);
5454 // Now that we have modified User, add it back to the CSE maps. If it
5455 // already exists there, recursively merge the results together.
5456 AddModifiedNodeToCSEMaps(User
);
5459 // If we just RAUW'd the root, take note.
5460 if (From
== getRoot().getNode())
5461 setRoot(SDValue(To
, getRoot().getResNo()));
5464 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5465 /// This can cause recursive merging of nodes in the DAG.
5467 /// This version can replace From with any result values. To must match the
5468 /// number and types of values returned by From.
5469 void SelectionDAG::ReplaceAllUsesWith(SDNode
*From
, const SDValue
*To
) {
5470 if (From
->getNumValues() == 1) // Handle the simple case efficiently.
5471 return ReplaceAllUsesWith(SDValue(From
, 0), To
[0]);
5473 // Iterate over just the existing users of From. See the comments in
5474 // the ReplaceAllUsesWith above.
5475 SDNode::use_iterator UI
= From
->use_begin(), UE
= From
->use_end();
5476 RAUWUpdateListener
Listener(*this, UI
, UE
);
5480 // This node is about to morph, remove its old self from the CSE maps.
5481 RemoveNodeFromCSEMaps(User
);
5483 // A user can appear in a use list multiple times, and when this
5484 // happens the uses are usually next to each other in the list.
5485 // To help reduce the number of CSE recomputations, process all
5486 // the uses of this user that we can find this way.
5488 SDUse
&Use
= UI
.getUse();
5489 const SDValue
&ToOp
= To
[Use
.getResNo()];
5492 } while (UI
!= UE
&& *UI
== User
);
5494 // Now that we have modified User, add it back to the CSE maps. If it
5495 // already exists there, recursively merge the results together.
5496 AddModifiedNodeToCSEMaps(User
);
5499 // If we just RAUW'd the root, take note.
5500 if (From
== getRoot().getNode())
5501 setRoot(SDValue(To
[getRoot().getResNo()]));
5504 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5505 /// uses of other values produced by From.getNode() alone. The Deleted
5506 /// vector is handled the same way as for ReplaceAllUsesWith.
5507 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From
, SDValue To
){
5508 // Handle the really simple, really trivial case efficiently.
5509 if (From
== To
) return;
5511 // Handle the simple, trivial, case efficiently.
5512 if (From
.getNode()->getNumValues() == 1) {
5513 ReplaceAllUsesWith(From
, To
);
5517 // Iterate over just the existing users of From. See the comments in
5518 // the ReplaceAllUsesWith above.
5519 SDNode::use_iterator UI
= From
.getNode()->use_begin(),
5520 UE
= From
.getNode()->use_end();
5521 RAUWUpdateListener
Listener(*this, UI
, UE
);
5524 bool UserRemovedFromCSEMaps
= false;
5526 // A user can appear in a use list multiple times, and when this
5527 // happens the uses are usually next to each other in the list.
5528 // To help reduce the number of CSE recomputations, process all
5529 // the uses of this user that we can find this way.
5531 SDUse
&Use
= UI
.getUse();
5533 // Skip uses of different values from the same node.
5534 if (Use
.getResNo() != From
.getResNo()) {
5539 // If this node hasn't been modified yet, it's still in the CSE maps,
5540 // so remove its old self from the CSE maps.
5541 if (!UserRemovedFromCSEMaps
) {
5542 RemoveNodeFromCSEMaps(User
);
5543 UserRemovedFromCSEMaps
= true;
5548 } while (UI
!= UE
&& *UI
== User
);
5550 // We are iterating over all uses of the From node, so if a use
5551 // doesn't use the specific value, no changes are made.
5552 if (!UserRemovedFromCSEMaps
)
5555 // Now that we have modified User, add it back to the CSE maps. If it
5556 // already exists there, recursively merge the results together.
5557 AddModifiedNodeToCSEMaps(User
);
5560 // If we just RAUW'd the root, take note.
5561 if (From
== getRoot())
5566 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5567 /// to record information about a use.
5574 /// operator< - Sort Memos by User.
5575 bool operator<(const UseMemo
&L
, const UseMemo
&R
) {
5576 return (intptr_t)L
.User
< (intptr_t)R
.User
;
5580 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5581 /// uses of other values produced by From.getNode() alone. The same value
5582 /// may appear in both the From and To list. The Deleted vector is
5583 /// handled the same way as for ReplaceAllUsesWith.
5584 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue
*From
,
5587 // Handle the simple, trivial case efficiently.
5589 return ReplaceAllUsesOfValueWith(*From
, *To
);
5591 // Read up all the uses and make records of them. This helps
5592 // processing new uses that are introduced during the
5593 // replacement process.
5594 SmallVector
<UseMemo
, 4> Uses
;
5595 for (unsigned i
= 0; i
!= Num
; ++i
) {
5596 unsigned FromResNo
= From
[i
].getResNo();
5597 SDNode
*FromNode
= From
[i
].getNode();
5598 for (SDNode::use_iterator UI
= FromNode
->use_begin(),
5599 E
= FromNode
->use_end(); UI
!= E
; ++UI
) {
5600 SDUse
&Use
= UI
.getUse();
5601 if (Use
.getResNo() == FromResNo
) {
5602 UseMemo Memo
= { *UI
, i
, &Use
};
5603 Uses
.push_back(Memo
);
5608 // Sort the uses, so that all the uses from a given User are together.
5609 std::sort(Uses
.begin(), Uses
.end());
5611 for (unsigned UseIndex
= 0, UseIndexEnd
= Uses
.size();
5612 UseIndex
!= UseIndexEnd
; ) {
5613 // We know that this user uses some value of From. If it is the right
5614 // value, update it.
5615 SDNode
*User
= Uses
[UseIndex
].User
;
5617 // This node is about to morph, remove its old self from the CSE maps.
5618 RemoveNodeFromCSEMaps(User
);
5620 // The Uses array is sorted, so all the uses for a given User
5621 // are next to each other in the list.
5622 // To help reduce the number of CSE recomputations, process all
5623 // the uses of this user that we can find this way.
5625 unsigned i
= Uses
[UseIndex
].Index
;
5626 SDUse
&Use
= *Uses
[UseIndex
].Use
;
5630 } while (UseIndex
!= UseIndexEnd
&& Uses
[UseIndex
].User
== User
);
5632 // Now that we have modified User, add it back to the CSE maps. If it
5633 // already exists there, recursively merge the results together.
5634 AddModifiedNodeToCSEMaps(User
);
5638 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5639 /// based on their topological order. It returns the maximum id and a vector
5640 /// of the SDNodes* in assigned order by reference.
5641 unsigned SelectionDAG::AssignTopologicalOrder() {
5643 unsigned DAGSize
= 0;
5645 // SortedPos tracks the progress of the algorithm. Nodes before it are
5646 // sorted, nodes after it are unsorted. When the algorithm completes
5647 // it is at the end of the list.
5648 allnodes_iterator SortedPos
= allnodes_begin();
5650 // Visit all the nodes. Move nodes with no operands to the front of
5651 // the list immediately. Annotate nodes that do have operands with their
5652 // operand count. Before we do this, the Node Id fields of the nodes
5653 // may contain arbitrary values. After, the Node Id fields for nodes
5654 // before SortedPos will contain the topological sort index, and the
5655 // Node Id fields for nodes At SortedPos and after will contain the
5656 // count of outstanding operands.
5657 for (allnodes_iterator I
= allnodes_begin(),E
= allnodes_end(); I
!= E
; ) {
5660 unsigned Degree
= N
->getNumOperands();
5662 // A node with no uses, add it to the result array immediately.
5663 N
->setNodeId(DAGSize
++);
5664 allnodes_iterator Q
= N
;
5666 SortedPos
= AllNodes
.insert(SortedPos
, AllNodes
.remove(Q
));
5667 assert(SortedPos
!= AllNodes
.end() && "Overran node list");
5670 // Temporarily use the Node Id as scratch space for the degree count.
5671 N
->setNodeId(Degree
);
5675 // Visit all the nodes. As we iterate, move nodes into sorted order,
5676 // such that by the time the end is reached all nodes will be sorted.
5677 for (allnodes_iterator I
= allnodes_begin(),E
= allnodes_end(); I
!= E
; ++I
) {
5680 // N is in sorted position, so all its uses have one less operand
5681 // that needs to be sorted.
5682 for (SDNode::use_iterator UI
= N
->use_begin(), UE
= N
->use_end();
5685 unsigned Degree
= P
->getNodeId();
5686 assert(Degree
!= 0 && "Invalid node degree");
5689 // All of P's operands are sorted, so P may sorted now.
5690 P
->setNodeId(DAGSize
++);
5692 SortedPos
= AllNodes
.insert(SortedPos
, AllNodes
.remove(P
));
5693 assert(SortedPos
!= AllNodes
.end() && "Overran node list");
5696 // Update P's outstanding operand count.
5697 P
->setNodeId(Degree
);
5700 if (I
== SortedPos
) {
5703 dbgs() << "Overran sorted position:\n";
5706 llvm_unreachable(0);
5710 assert(SortedPos
== AllNodes
.end() &&
5711 "Topological sort incomplete!");
5712 assert(AllNodes
.front().getOpcode() == ISD::EntryToken
&&
5713 "First node in topological sort is not the entry token!");
5714 assert(AllNodes
.front().getNodeId() == 0 &&
5715 "First node in topological sort has non-zero id!");
5716 assert(AllNodes
.front().getNumOperands() == 0 &&
5717 "First node in topological sort has operands!");
5718 assert(AllNodes
.back().getNodeId() == (int)DAGSize
-1 &&
5719 "Last node in topologic sort has unexpected id!");
5720 assert(AllNodes
.back().use_empty() &&
5721 "Last node in topologic sort has users!");
5722 assert(DAGSize
== allnodes_size() && "Node count mismatch!");
5726 /// AssignOrdering - Assign an order to the SDNode.
5727 void SelectionDAG::AssignOrdering(const SDNode
*SD
, unsigned Order
) {
5728 assert(SD
&& "Trying to assign an order to a null node!");
5729 Ordering
->add(SD
, Order
);
5732 /// GetOrdering - Get the order for the SDNode.
5733 unsigned SelectionDAG::GetOrdering(const SDNode
*SD
) const {
5734 assert(SD
&& "Trying to get the order of a null node!");
5735 return Ordering
->getOrder(SD
);
5738 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
5739 /// value is produced by SD.
5740 void SelectionDAG::AddDbgValue(SDDbgValue
*DB
, SDNode
*SD
, bool isParameter
) {
5741 DbgInfo
->add(DB
, SD
, isParameter
);
5743 SD
->setHasDebugValue(true);
5746 /// TransferDbgValues - Transfer SDDbgValues.
5747 void SelectionDAG::TransferDbgValues(SDValue From
, SDValue To
) {
5748 if (From
== To
|| !From
.getNode()->getHasDebugValue())
5750 SDNode
*FromNode
= From
.getNode();
5751 SDNode
*ToNode
= To
.getNode();
5752 ArrayRef
<SDDbgValue
*> DVs
= GetDbgValues(FromNode
);
5753 SmallVector
<SDDbgValue
*, 2> ClonedDVs
;
5754 for (ArrayRef
<SDDbgValue
*>::iterator I
= DVs
.begin(), E
= DVs
.end();
5756 SDDbgValue
*Dbg
= *I
;
5757 if (Dbg
->getKind() == SDDbgValue::SDNODE
) {
5758 SDDbgValue
*Clone
= getDbgValue(Dbg
->getMDPtr(), ToNode
, To
.getResNo(),
5759 Dbg
->getOffset(), Dbg
->getDebugLoc(),
5761 ClonedDVs
.push_back(Clone
);
5764 for (SmallVector
<SDDbgValue
*, 2>::iterator I
= ClonedDVs
.begin(),
5765 E
= ClonedDVs
.end(); I
!= E
; ++I
)
5766 AddDbgValue(*I
, ToNode
, false);
5769 //===----------------------------------------------------------------------===//
5771 //===----------------------------------------------------------------------===//
5773 HandleSDNode::~HandleSDNode() {
5777 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc
, DebugLoc DL
,
5778 const GlobalValue
*GA
,
5779 EVT VT
, int64_t o
, unsigned char TF
)
5780 : SDNode(Opc
, DL
, getSDVTList(VT
)), Offset(o
), TargetFlags(TF
) {
5784 MemSDNode::MemSDNode(unsigned Opc
, DebugLoc dl
, SDVTList VTs
, EVT memvt
,
5785 MachineMemOperand
*mmo
)
5786 : SDNode(Opc
, dl
, VTs
), MemoryVT(memvt
), MMO(mmo
) {
5787 SubclassData
= encodeMemSDNodeFlags(0, ISD::UNINDEXED
, MMO
->isVolatile(),
5788 MMO
->isNonTemporal(), MMO
->isInvariant());
5789 assert(isVolatile() == MMO
->isVolatile() && "Volatile encoding error!");
5790 assert(isNonTemporal() == MMO
->isNonTemporal() &&
5791 "Non-temporal encoding error!");
5792 assert(memvt
.getStoreSize() == MMO
->getSize() && "Size mismatch!");
5795 MemSDNode::MemSDNode(unsigned Opc
, DebugLoc dl
, SDVTList VTs
,
5796 const SDValue
*Ops
, unsigned NumOps
, EVT memvt
,
5797 MachineMemOperand
*mmo
)
5798 : SDNode(Opc
, dl
, VTs
, Ops
, NumOps
),
5799 MemoryVT(memvt
), MMO(mmo
) {
5800 SubclassData
= encodeMemSDNodeFlags(0, ISD::UNINDEXED
, MMO
->isVolatile(),
5801 MMO
->isNonTemporal(), MMO
->isInvariant());
5802 assert(isVolatile() == MMO
->isVolatile() && "Volatile encoding error!");
5803 assert(memvt
.getStoreSize() == MMO
->getSize() && "Size mismatch!");
5806 /// Profile - Gather unique data for the node.
5808 void SDNode::Profile(FoldingSetNodeID
&ID
) const {
5809 AddNodeIDNode(ID
, this);
5814 std::vector
<EVT
> VTs
;
5817 VTs
.reserve(MVT::LAST_VALUETYPE
);
5818 for (unsigned i
= 0; i
< MVT::LAST_VALUETYPE
; ++i
)
5819 VTs
.push_back(MVT((MVT::SimpleValueType
)i
));
5824 static ManagedStatic
<std::set
<EVT
, EVT::compareRawBits
> > EVTs
;
5825 static ManagedStatic
<EVTArray
> SimpleVTArray
;
5826 static ManagedStatic
<sys::SmartMutex
<true> > VTMutex
;
5828 /// getValueTypeList - Return a pointer to the specified value type.
5830 const EVT
*SDNode::getValueTypeList(EVT VT
) {
5831 if (VT
.isExtended()) {
5832 sys::SmartScopedLock
<true> Lock(*VTMutex
);
5833 return &(*EVTs
->insert(VT
).first
);
5835 assert(VT
.getSimpleVT() < MVT::LAST_VALUETYPE
&&
5836 "Value type out of range!");
5837 return &SimpleVTArray
->VTs
[VT
.getSimpleVT().SimpleTy
];
5841 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
5842 /// indicated value. This method ignores uses of other values defined by this
5844 bool SDNode::hasNUsesOfValue(unsigned NUses
, unsigned Value
) const {
5845 assert(Value
< getNumValues() && "Bad value!");
5847 // TODO: Only iterate over uses of a given value of the node
5848 for (SDNode::use_iterator UI
= use_begin(), E
= use_end(); UI
!= E
; ++UI
) {
5849 if (UI
.getUse().getResNo() == Value
) {
5856 // Found exactly the right number of uses?
5861 /// hasAnyUseOfValue - Return true if there are any use of the indicated
5862 /// value. This method ignores uses of other values defined by this operation.
5863 bool SDNode::hasAnyUseOfValue(unsigned Value
) const {
5864 assert(Value
< getNumValues() && "Bad value!");
5866 for (SDNode::use_iterator UI
= use_begin(), E
= use_end(); UI
!= E
; ++UI
)
5867 if (UI
.getUse().getResNo() == Value
)
5874 /// isOnlyUserOf - Return true if this node is the only use of N.
5876 bool SDNode::isOnlyUserOf(SDNode
*N
) const {
5878 for (SDNode::use_iterator I
= N
->use_begin(), E
= N
->use_end(); I
!= E
; ++I
) {
5889 /// isOperand - Return true if this node is an operand of N.
5891 bool SDValue::isOperandOf(SDNode
*N
) const {
5892 for (unsigned i
= 0, e
= N
->getNumOperands(); i
!= e
; ++i
)
5893 if (*this == N
->getOperand(i
))
5898 bool SDNode::isOperandOf(SDNode
*N
) const {
5899 for (unsigned i
= 0, e
= N
->NumOperands
; i
!= e
; ++i
)
5900 if (this == N
->OperandList
[i
].getNode())
5905 /// reachesChainWithoutSideEffects - Return true if this operand (which must
5906 /// be a chain) reaches the specified operand without crossing any
5907 /// side-effecting instructions on any chain path. In practice, this looks
5908 /// through token factors and non-volatile loads. In order to remain efficient,
5909 /// this only looks a couple of nodes in, it does not do an exhaustive search.
5910 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest
,
5911 unsigned Depth
) const {
5912 if (*this == Dest
) return true;
5914 // Don't search too deeply, we just want to be able to see through
5915 // TokenFactor's etc.
5916 if (Depth
== 0) return false;
5918 // If this is a token factor, all inputs to the TF happen in parallel. If any
5919 // of the operands of the TF does not reach dest, then we cannot do the xform.
5920 if (getOpcode() == ISD::TokenFactor
) {
5921 for (unsigned i
= 0, e
= getNumOperands(); i
!= e
; ++i
)
5922 if (!getOperand(i
).reachesChainWithoutSideEffects(Dest
, Depth
-1))
5927 // Loads don't have side effects, look through them.
5928 if (LoadSDNode
*Ld
= dyn_cast
<LoadSDNode
>(*this)) {
5929 if (!Ld
->isVolatile())
5930 return Ld
->getChain().reachesChainWithoutSideEffects(Dest
, Depth
-1);
5935 /// hasPredecessor - Return true if N is a predecessor of this node.
5936 /// N is either an operand of this node, or can be reached by recursively
5937 /// traversing up the operands.
5938 /// NOTE: This is an expensive method. Use it carefully.
5939 bool SDNode::hasPredecessor(const SDNode
*N
) const {
5940 SmallPtrSet
<const SDNode
*, 32> Visited
;
5941 SmallVector
<const SDNode
*, 16> Worklist
;
5942 return hasPredecessorHelper(N
, Visited
, Worklist
);
5945 bool SDNode::hasPredecessorHelper(const SDNode
*N
,
5946 SmallPtrSet
<const SDNode
*, 32> &Visited
,
5947 SmallVector
<const SDNode
*, 16> &Worklist
) const {
5948 if (Visited
.empty()) {
5949 Worklist
.push_back(this);
5951 // Take a look in the visited set. If we've already encountered this node
5952 // we needn't search further.
5953 if (Visited
.count(N
))
5957 // Haven't visited N yet. Continue the search.
5958 while (!Worklist
.empty()) {
5959 const SDNode
*M
= Worklist
.pop_back_val();
5960 for (unsigned i
= 0, e
= M
->getNumOperands(); i
!= e
; ++i
) {
5961 SDNode
*Op
= M
->getOperand(i
).getNode();
5962 if (Visited
.insert(Op
))
5963 Worklist
.push_back(Op
);
5972 uint64_t SDNode::getConstantOperandVal(unsigned Num
) const {
5973 assert(Num
< NumOperands
&& "Invalid child # of SDNode!");
5974 return cast
<ConstantSDNode
>(OperandList
[Num
])->getZExtValue();
5977 SDValue
SelectionDAG::UnrollVectorOp(SDNode
*N
, unsigned ResNE
) {
5978 assert(N
->getNumValues() == 1 &&
5979 "Can't unroll a vector with multiple results!");
5981 EVT VT
= N
->getValueType(0);
5982 unsigned NE
= VT
.getVectorNumElements();
5983 EVT EltVT
= VT
.getVectorElementType();
5984 DebugLoc dl
= N
->getDebugLoc();
5986 SmallVector
<SDValue
, 8> Scalars
;
5987 SmallVector
<SDValue
, 4> Operands(N
->getNumOperands());
5989 // If ResNE is 0, fully unroll the vector op.
5992 else if (NE
> ResNE
)
5996 for (i
= 0; i
!= NE
; ++i
) {
5997 for (unsigned j
= 0, e
= N
->getNumOperands(); j
!= e
; ++j
) {
5998 SDValue Operand
= N
->getOperand(j
);
5999 EVT OperandVT
= Operand
.getValueType();
6000 if (OperandVT
.isVector()) {
6001 // A vector operand; extract a single element.
6002 EVT OperandEltVT
= OperandVT
.getVectorElementType();
6003 Operands
[j
] = getNode(ISD::EXTRACT_VECTOR_ELT
, dl
,
6006 getConstant(i
, TLI
.getPointerTy()));
6008 // A scalar operand; just use it as is.
6009 Operands
[j
] = Operand
;
6013 switch (N
->getOpcode()) {
6015 Scalars
.push_back(getNode(N
->getOpcode(), dl
, EltVT
,
6016 &Operands
[0], Operands
.size()));
6019 Scalars
.push_back(getNode(ISD::SELECT
, dl
, EltVT
,
6020 &Operands
[0], Operands
.size()));
6027 Scalars
.push_back(getNode(N
->getOpcode(), dl
, EltVT
, Operands
[0],
6028 getShiftAmountOperand(Operands
[0].getValueType(),
6031 case ISD::SIGN_EXTEND_INREG
:
6032 case ISD::FP_ROUND_INREG
: {
6033 EVT ExtVT
= cast
<VTSDNode
>(Operands
[1])->getVT().getVectorElementType();
6034 Scalars
.push_back(getNode(N
->getOpcode(), dl
, EltVT
,
6036 getValueType(ExtVT
)));
6041 for (; i
< ResNE
; ++i
)
6042 Scalars
.push_back(getUNDEF(EltVT
));
6044 return getNode(ISD::BUILD_VECTOR
, dl
,
6045 EVT::getVectorVT(*getContext(), EltVT
, ResNE
),
6046 &Scalars
[0], Scalars
.size());
6050 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6051 /// location that is 'Dist' units away from the location that the 'Base' load
6052 /// is loading from.
6053 bool SelectionDAG::isConsecutiveLoad(LoadSDNode
*LD
, LoadSDNode
*Base
,
6054 unsigned Bytes
, int Dist
) const {
6055 if (LD
->getChain() != Base
->getChain())
6057 EVT VT
= LD
->getValueType(0);
6058 if (VT
.getSizeInBits() / 8 != Bytes
)
6061 SDValue Loc
= LD
->getOperand(1);
6062 SDValue BaseLoc
= Base
->getOperand(1);
6063 if (Loc
.getOpcode() == ISD::FrameIndex
) {
6064 if (BaseLoc
.getOpcode() != ISD::FrameIndex
)
6066 const MachineFrameInfo
*MFI
= getMachineFunction().getFrameInfo();
6067 int FI
= cast
<FrameIndexSDNode
>(Loc
)->getIndex();
6068 int BFI
= cast
<FrameIndexSDNode
>(BaseLoc
)->getIndex();
6069 int FS
= MFI
->getObjectSize(FI
);
6070 int BFS
= MFI
->getObjectSize(BFI
);
6071 if (FS
!= BFS
|| FS
!= (int)Bytes
) return false;
6072 return MFI
->getObjectOffset(FI
) == (MFI
->getObjectOffset(BFI
) + Dist
*Bytes
);
6076 if (isBaseWithConstantOffset(Loc
) && Loc
.getOperand(0) == BaseLoc
&&
6077 cast
<ConstantSDNode
>(Loc
.getOperand(1))->getSExtValue() == Dist
*Bytes
)
6080 const GlobalValue
*GV1
= NULL
;
6081 const GlobalValue
*GV2
= NULL
;
6082 int64_t Offset1
= 0;
6083 int64_t Offset2
= 0;
6084 bool isGA1
= TLI
.isGAPlusOffset(Loc
.getNode(), GV1
, Offset1
);
6085 bool isGA2
= TLI
.isGAPlusOffset(BaseLoc
.getNode(), GV2
, Offset2
);
6086 if (isGA1
&& isGA2
&& GV1
== GV2
)
6087 return Offset1
== (Offset2
+ Dist
*Bytes
);
6092 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6093 /// it cannot be inferred.
6094 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr
) const {
6095 // If this is a GlobalAddress + cst, return the alignment.
6096 const GlobalValue
*GV
;
6097 int64_t GVOffset
= 0;
6098 if (TLI
.isGAPlusOffset(Ptr
.getNode(), GV
, GVOffset
)) {
6099 unsigned PtrWidth
= TLI
.getPointerTy().getSizeInBits();
6100 APInt
KnownZero(PtrWidth
, 0), KnownOne(PtrWidth
, 0);
6101 llvm::ComputeMaskedBits(const_cast<GlobalValue
*>(GV
), KnownZero
, KnownOne
,
6102 TLI
.getTargetData());
6103 unsigned AlignBits
= KnownZero
.countTrailingOnes();
6104 unsigned Align
= AlignBits
? 1 << std::min(31U, AlignBits
) : 0;
6106 return MinAlign(Align
, GVOffset
);
6109 // If this is a direct reference to a stack slot, use information about the
6110 // stack slot's alignment.
6111 int FrameIdx
= 1 << 31;
6112 int64_t FrameOffset
= 0;
6113 if (FrameIndexSDNode
*FI
= dyn_cast
<FrameIndexSDNode
>(Ptr
)) {
6114 FrameIdx
= FI
->getIndex();
6115 } else if (isBaseWithConstantOffset(Ptr
) &&
6116 isa
<FrameIndexSDNode
>(Ptr
.getOperand(0))) {
6118 FrameIdx
= cast
<FrameIndexSDNode
>(Ptr
.getOperand(0))->getIndex();
6119 FrameOffset
= Ptr
.getConstantOperandVal(1);
6122 if (FrameIdx
!= (1 << 31)) {
6123 const MachineFrameInfo
&MFI
= *getMachineFunction().getFrameInfo();
6124 unsigned FIInfoAlign
= MinAlign(MFI
.getObjectAlignment(FrameIdx
),
6132 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6133 unsigned GlobalAddressSDNode::getAddressSpace() const {
6134 return getGlobal()->getType()->getAddressSpace();
6138 Type
*ConstantPoolSDNode::getType() const {
6139 if (isMachineConstantPoolEntry())
6140 return Val
.MachineCPVal
->getType();
6141 return Val
.ConstVal
->getType();
6144 bool BuildVectorSDNode::isConstantSplat(APInt
&SplatValue
,
6146 unsigned &SplatBitSize
,
6148 unsigned MinSplatBits
,
6150 EVT VT
= getValueType(0);
6151 assert(VT
.isVector() && "Expected a vector type");
6152 unsigned sz
= VT
.getSizeInBits();
6153 if (MinSplatBits
> sz
)
6156 SplatValue
= APInt(sz
, 0);
6157 SplatUndef
= APInt(sz
, 0);
6159 // Get the bits. Bits with undefined values (when the corresponding element
6160 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6161 // in SplatValue. If any of the values are not constant, give up and return
6163 unsigned int nOps
= getNumOperands();
6164 assert(nOps
> 0 && "isConstantSplat has 0-size build vector");
6165 unsigned EltBitSize
= VT
.getVectorElementType().getSizeInBits();
6167 for (unsigned j
= 0; j
< nOps
; ++j
) {
6168 unsigned i
= isBigEndian
? nOps
-1-j
: j
;
6169 SDValue OpVal
= getOperand(i
);
6170 unsigned BitPos
= j
* EltBitSize
;
6172 if (OpVal
.getOpcode() == ISD::UNDEF
)
6173 SplatUndef
|= APInt::getBitsSet(sz
, BitPos
, BitPos
+ EltBitSize
);
6174 else if (ConstantSDNode
*CN
= dyn_cast
<ConstantSDNode
>(OpVal
))
6175 SplatValue
|= CN
->getAPIntValue().zextOrTrunc(EltBitSize
).
6176 zextOrTrunc(sz
) << BitPos
;
6177 else if (ConstantFPSDNode
*CN
= dyn_cast
<ConstantFPSDNode
>(OpVal
))
6178 SplatValue
|= CN
->getValueAPF().bitcastToAPInt().zextOrTrunc(sz
) <<BitPos
;
6183 // The build_vector is all constants or undefs. Find the smallest element
6184 // size that splats the vector.
6186 HasAnyUndefs
= (SplatUndef
!= 0);
6189 unsigned HalfSize
= sz
/ 2;
6190 APInt HighValue
= SplatValue
.lshr(HalfSize
).trunc(HalfSize
);
6191 APInt LowValue
= SplatValue
.trunc(HalfSize
);
6192 APInt HighUndef
= SplatUndef
.lshr(HalfSize
).trunc(HalfSize
);
6193 APInt LowUndef
= SplatUndef
.trunc(HalfSize
);
6195 // If the two halves do not match (ignoring undef bits), stop here.
6196 if ((HighValue
& ~LowUndef
) != (LowValue
& ~HighUndef
) ||
6197 MinSplatBits
> HalfSize
)
6200 SplatValue
= HighValue
| LowValue
;
6201 SplatUndef
= HighUndef
& LowUndef
;
6210 bool ShuffleVectorSDNode::isSplatMask(const int *Mask
, EVT VT
) {
6211 // Find the first non-undef value in the shuffle mask.
6213 for (i
= 0, e
= VT
.getVectorNumElements(); i
!= e
&& Mask
[i
] < 0; ++i
)
6216 assert(i
!= e
&& "VECTOR_SHUFFLE node with all undef indices!");
6218 // Make sure all remaining elements are either undef or the same as the first
6220 for (int Idx
= Mask
[i
]; i
!= e
; ++i
)
6221 if (Mask
[i
] >= 0 && Mask
[i
] != Idx
)
6227 static void checkForCyclesHelper(const SDNode
*N
,
6228 SmallPtrSet
<const SDNode
*, 32> &Visited
,
6229 SmallPtrSet
<const SDNode
*, 32> &Checked
) {
6230 // If this node has already been checked, don't check it again.
6231 if (Checked
.count(N
))
6234 // If a node has already been visited on this depth-first walk, reject it as
6236 if (!Visited
.insert(N
)) {
6237 dbgs() << "Offending node:\n";
6239 errs() << "Detected cycle in SelectionDAG\n";
6243 for(unsigned i
= 0, e
= N
->getNumOperands(); i
!= e
; ++i
)
6244 checkForCyclesHelper(N
->getOperand(i
).getNode(), Visited
, Checked
);
6251 void llvm::checkForCycles(const llvm::SDNode
*N
) {
6253 assert(N
&& "Checking nonexistant SDNode");
6254 SmallPtrSet
<const SDNode
*, 32> visited
;
6255 SmallPtrSet
<const SDNode
*, 32> checked
;
6256 checkForCyclesHelper(N
, visited
, checked
);
6260 void llvm::checkForCycles(const llvm::SelectionDAG
*DAG
) {
6261 checkForCycles(DAG
->getRoot().getNode());