1
//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This implements the SelectionDAG class.
12
//===----------------------------------------------------------------------===//
14
#include "llvm/CodeGen/SelectionDAG.h"
15
#include "SDNodeDbgValue.h"
16
#include "llvm/ADT/SetVector.h"
17
#include "llvm/ADT/SmallPtrSet.h"
18
#include "llvm/ADT/SmallSet.h"
19
#include "llvm/ADT/SmallVector.h"
20
#include "llvm/ADT/StringExtras.h"
21
#include "llvm/Analysis/ValueTracking.h"
22
#include "llvm/CodeGen/MachineBasicBlock.h"
23
#include "llvm/CodeGen/MachineConstantPool.h"
24
#include "llvm/CodeGen/MachineFrameInfo.h"
25
#include "llvm/CodeGen/MachineModuleInfo.h"
26
#include "llvm/IR/CallingConv.h"
27
#include "llvm/IR/Constants.h"
28
#include "llvm/IR/DataLayout.h"
29
#include "llvm/IR/DebugInfo.h"
30
#include "llvm/IR/DerivedTypes.h"
31
#include "llvm/IR/Function.h"
32
#include "llvm/IR/GlobalAlias.h"
33
#include "llvm/IR/GlobalVariable.h"
34
#include "llvm/IR/Intrinsics.h"
35
#include "llvm/Support/CommandLine.h"
36
#include "llvm/Support/Debug.h"
37
#include "llvm/Support/ErrorHandling.h"
38
#include "llvm/Support/ManagedStatic.h"
39
#include "llvm/Support/MathExtras.h"
40
#include "llvm/Support/Mutex.h"
41
#include "llvm/Support/raw_ostream.h"
42
#include "llvm/Target/TargetInstrInfo.h"
43
#include "llvm/Target/TargetIntrinsicInfo.h"
44
#include "llvm/Target/TargetLowering.h"
45
#include "llvm/Target/TargetMachine.h"
46
#include "llvm/Target/TargetOptions.h"
47
#include "llvm/Target/TargetRegisterInfo.h"
48
#include "llvm/Target/TargetSelectionDAGInfo.h"
49
#include "llvm/Target/TargetSubtargetInfo.h"
56
/// makeVTList - Return an instance of the SDVTList struct initialized with the
57
/// specified members.
58
static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59
SDVTList Res = {VTs, NumVTs};
63
// Default null implementations of the callbacks.
64
void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65
void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67
//===----------------------------------------------------------------------===//
68
// ConstantFPSDNode Class
69
//===----------------------------------------------------------------------===//
71
/// isExactlyValue - We don't rely on operator== working on double values, as
72
/// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73
/// As such, this method can be used to do an exact bit-for-bit comparison of
74
/// two floating point values.
75
bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76
return getValueAPF().bitwiseIsEqual(V);
79
bool ConstantFPSDNode::isValueValidForType(EVT VT,
81
assert(VT.isFloatingPoint() && "Can only convert between FP types");
83
// convert modifies in place, so make a copy.
84
APFloat Val2 = APFloat(Val);
86
(void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87
APFloat::rmNearestTiesToEven,
92
//===----------------------------------------------------------------------===//
94
//===----------------------------------------------------------------------===//
96
/// isBuildVectorAllOnes - Return true if the specified node is a
97
/// BUILD_VECTOR where all of the elements are ~0 or undef.
98
bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99
// Look through a bit convert.
100
while (N->getOpcode() == ISD::BITCAST)
101
N = N->getOperand(0).getNode();
103
if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105
unsigned i = 0, e = N->getNumOperands();
107
// Skip over all of the undef values.
108
while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111
// Do not accept an all-undef vector.
112
if (i == e) return false;
114
// Do not accept build_vectors that aren't all constants or which have non-~0
115
// elements. We have to be a bit careful here, as the type of the constant
116
// may not be the same as the type of the vector elements due to type
117
// legalization (the elements are promoted to a legal type for the target and
118
// a vector of a type may be legal when the base element type is not).
119
// We only want to check enough bits to cover the vector elements, because
120
// we care if the resultant vector is all ones, not whether the individual
122
SDValue NotZero = N->getOperand(i);
123
unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124
if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125
if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127
} else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128
if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133
// Okay, we have at least one ~0 value, check to see if the rest match or are
134
// undefs. Even with the above element type twiddling, this should be OK, as
135
// the same type legalization should have applied to all the elements.
136
for (++i; i != e; ++i)
137
if (N->getOperand(i) != NotZero &&
138
N->getOperand(i).getOpcode() != ISD::UNDEF)
144
/// isBuildVectorAllZeros - Return true if the specified node is a
145
/// BUILD_VECTOR where all of the elements are 0 or undef.
146
bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147
// Look through a bit convert.
148
while (N->getOpcode() == ISD::BITCAST)
149
N = N->getOperand(0).getNode();
151
if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153
bool IsAllUndef = true;
154
for (const SDValue &Op : N->op_values()) {
155
if (Op.getOpcode() == ISD::UNDEF)
158
// Do not accept build_vectors that aren't all constants or which have non-0
159
// elements. We have to be a bit careful here, as the type of the constant
160
// may not be the same as the type of the vector elements due to type
161
// legalization (the elements are promoted to a legal type for the target
162
// and a vector of a type may be legal when the base element type is not).
163
// We only want to check enough bits to cover the vector elements, because
164
// we care if the resultant vector is all zeros, not whether the individual
166
unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167
if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
168
if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170
} else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
171
if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177
// Do not accept an all-undef vector.
183
/// \brief Return true if the specified node is a BUILD_VECTOR node of
184
/// all ConstantSDNode or undef.
185
bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186
if (N->getOpcode() != ISD::BUILD_VECTOR)
189
for (const SDValue &Op : N->op_values()) {
190
if (Op.getOpcode() == ISD::UNDEF)
192
if (!isa<ConstantSDNode>(Op))
198
/// \brief Return true if the specified node is a BUILD_VECTOR node of
199
/// all ConstantFPSDNode or undef.
200
bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
201
if (N->getOpcode() != ISD::BUILD_VECTOR)
204
for (const SDValue &Op : N->op_values()) {
205
if (Op.getOpcode() == ISD::UNDEF)
207
if (!isa<ConstantFPSDNode>(Op))
213
/// isScalarToVector - Return true if the specified node is a
214
/// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
215
/// element is not an undef.
216
bool ISD::isScalarToVector(const SDNode *N) {
217
if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
220
if (N->getOpcode() != ISD::BUILD_VECTOR)
222
if (N->getOperand(0).getOpcode() == ISD::UNDEF)
224
unsigned NumElems = N->getNumOperands();
227
for (unsigned i = 1; i < NumElems; ++i) {
228
SDValue V = N->getOperand(i);
229
if (V.getOpcode() != ISD::UNDEF)
235
/// allOperandsUndef - Return true if the node has at least one operand
236
/// and all operands of the specified node are ISD::UNDEF.
237
bool ISD::allOperandsUndef(const SDNode *N) {
238
// Return false if the node has no operands.
239
// This is "logically inconsistent" with the definition of "all" but
240
// is probably the desired behavior.
241
if (N->getNumOperands() == 0)
244
for (const SDValue &Op : N->op_values())
245
if (Op.getOpcode() != ISD::UNDEF)
251
ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
254
return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
256
return ISD::SIGN_EXTEND;
258
return ISD::ZERO_EXTEND;
263
llvm_unreachable("Invalid LoadExtType");
266
/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
267
/// when given the operation for (X op Y).
268
ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
269
// To perform this operation, we just need to swap the L and G bits of the
271
unsigned OldL = (Operation >> 2) & 1;
272
unsigned OldG = (Operation >> 1) & 1;
273
return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
274
(OldL << 1) | // New G bit
275
(OldG << 2)); // New L bit.
278
/// getSetCCInverse - Return the operation corresponding to !(X op Y), where
279
/// 'op' is a valid SetCC operation.
280
ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
281
unsigned Operation = Op;
283
Operation ^= 7; // Flip L, G, E bits, but not U.
285
Operation ^= 15; // Flip all of the condition bits.
287
if (Operation > ISD::SETTRUE2)
288
Operation &= ~8; // Don't let N and U bits get set.
290
return ISD::CondCode(Operation);
294
/// isSignedOp - For an integer comparison, return 1 if the comparison is a
295
/// signed operation and 2 if the result is an unsigned comparison. Return zero
296
/// if the operation does not depend on the sign of the input (setne and seteq).
297
static int isSignedOp(ISD::CondCode Opcode) {
299
default: llvm_unreachable("Illegal integer setcc operation!");
301
case ISD::SETNE: return 0;
305
case ISD::SETGE: return 1;
309
case ISD::SETUGE: return 2;
313
/// getSetCCOrOperation - Return the result of a logical OR between different
314
/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
315
/// returns SETCC_INVALID if it is not possible to represent the resultant
317
ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
319
if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
320
// Cannot fold a signed integer setcc with an unsigned integer setcc.
321
return ISD::SETCC_INVALID;
323
unsigned Op = Op1 | Op2; // Combine all of the condition bits.
325
// If the N and U bits get set then the resultant comparison DOES suddenly
326
// care about orderedness, and is true when ordered.
327
if (Op > ISD::SETTRUE2)
328
Op &= ~16; // Clear the U bit if the N bit is set.
330
// Canonicalize illegal integer setcc's.
331
if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
334
return ISD::CondCode(Op);
337
/// getSetCCAndOperation - Return the result of a logical AND between different
338
/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
339
/// function returns zero if it is not possible to represent the resultant
341
ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
343
if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
344
// Cannot fold a signed setcc with an unsigned setcc.
345
return ISD::SETCC_INVALID;
347
// Combine all of the condition bits.
348
ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
350
// Canonicalize illegal integer setcc's.
354
case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
355
case ISD::SETOEQ: // SETEQ & SETU[LG]E
356
case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
357
case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
358
case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
365
//===----------------------------------------------------------------------===//
366
// SDNode Profile Support
367
//===----------------------------------------------------------------------===//
369
/// AddNodeIDOpcode - Add the node opcode to the NodeID data.
371
static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
375
/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
376
/// solely with their pointer.
377
static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
378
ID.AddPointer(VTList.VTs);
381
/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
383
static void AddNodeIDOperands(FoldingSetNodeID &ID,
384
ArrayRef<SDValue> Ops) {
385
for (auto& Op : Ops) {
386
ID.AddPointer(Op.getNode());
387
ID.AddInteger(Op.getResNo());
391
/// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
393
static void AddNodeIDOperands(FoldingSetNodeID &ID,
394
ArrayRef<SDUse> Ops) {
395
for (auto& Op : Ops) {
396
ID.AddPointer(Op.getNode());
397
ID.AddInteger(Op.getResNo());
400
/// Add logical or fast math flag values to FoldingSetNodeID value.
401
static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
402
const SDNodeFlags *Flags) {
403
if (!Flags || !isBinOpWithFlags(Opcode))
406
unsigned RawFlags = Flags->getRawFlags();
407
// If no flags are set, do not alter the ID. We must match the ID of nodes
408
// that were created without explicitly specifying flags. This also saves time
409
// and allows a gradual increase in API usage of the optional optimization
412
ID.AddInteger(RawFlags);
415
static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
416
if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
417
AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
420
static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
421
SDVTList VTList, ArrayRef<SDValue> OpList) {
422
AddNodeIDOpcode(ID, OpC);
423
AddNodeIDValueTypes(ID, VTList);
424
AddNodeIDOperands(ID, OpList);
427
/// If this is an SDNode with special info, add this info to the NodeID data.
428
static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
429
switch (N->getOpcode()) {
430
case ISD::TargetExternalSymbol:
431
case ISD::ExternalSymbol:
433
llvm_unreachable("Should only be used on nodes with operands");
434
default: break; // Normal nodes don't need extra info.
435
case ISD::TargetConstant:
436
case ISD::Constant: {
437
const ConstantSDNode *C = cast<ConstantSDNode>(N);
438
ID.AddPointer(C->getConstantIntValue());
439
ID.AddBoolean(C->isOpaque());
442
case ISD::TargetConstantFP:
443
case ISD::ConstantFP: {
444
ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
447
case ISD::TargetGlobalAddress:
448
case ISD::GlobalAddress:
449
case ISD::TargetGlobalTLSAddress:
450
case ISD::GlobalTLSAddress: {
451
const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
452
ID.AddPointer(GA->getGlobal());
453
ID.AddInteger(GA->getOffset());
454
ID.AddInteger(GA->getTargetFlags());
455
ID.AddInteger(GA->getAddressSpace());
458
case ISD::BasicBlock:
459
ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
462
ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
464
case ISD::RegisterMask:
465
ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
468
ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
470
case ISD::FrameIndex:
471
case ISD::TargetFrameIndex:
472
ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
475
case ISD::TargetJumpTable:
476
ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
477
ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
479
case ISD::ConstantPool:
480
case ISD::TargetConstantPool: {
481
const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
482
ID.AddInteger(CP->getAlignment());
483
ID.AddInteger(CP->getOffset());
484
if (CP->isMachineConstantPoolEntry())
485
CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
487
ID.AddPointer(CP->getConstVal());
488
ID.AddInteger(CP->getTargetFlags());
491
case ISD::TargetIndex: {
492
const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
493
ID.AddInteger(TI->getIndex());
494
ID.AddInteger(TI->getOffset());
495
ID.AddInteger(TI->getTargetFlags());
499
const LoadSDNode *LD = cast<LoadSDNode>(N);
500
ID.AddInteger(LD->getMemoryVT().getRawBits());
501
ID.AddInteger(LD->getRawSubclassData());
502
ID.AddInteger(LD->getPointerInfo().getAddrSpace());
506
const StoreSDNode *ST = cast<StoreSDNode>(N);
507
ID.AddInteger(ST->getMemoryVT().getRawBits());
508
ID.AddInteger(ST->getRawSubclassData());
509
ID.AddInteger(ST->getPointerInfo().getAddrSpace());
512
case ISD::ATOMIC_CMP_SWAP:
513
case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
514
case ISD::ATOMIC_SWAP:
515
case ISD::ATOMIC_LOAD_ADD:
516
case ISD::ATOMIC_LOAD_SUB:
517
case ISD::ATOMIC_LOAD_AND:
518
case ISD::ATOMIC_LOAD_OR:
519
case ISD::ATOMIC_LOAD_XOR:
520
case ISD::ATOMIC_LOAD_NAND:
521
case ISD::ATOMIC_LOAD_MIN:
522
case ISD::ATOMIC_LOAD_MAX:
523
case ISD::ATOMIC_LOAD_UMIN:
524
case ISD::ATOMIC_LOAD_UMAX:
525
case ISD::ATOMIC_LOAD:
526
case ISD::ATOMIC_STORE: {
527
const AtomicSDNode *AT = cast<AtomicSDNode>(N);
528
ID.AddInteger(AT->getMemoryVT().getRawBits());
529
ID.AddInteger(AT->getRawSubclassData());
530
ID.AddInteger(AT->getPointerInfo().getAddrSpace());
533
case ISD::PREFETCH: {
534
const MemSDNode *PF = cast<MemSDNode>(N);
535
ID.AddInteger(PF->getPointerInfo().getAddrSpace());
538
case ISD::VECTOR_SHUFFLE: {
539
const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
540
for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
542
ID.AddInteger(SVN->getMaskElt(i));
545
case ISD::TargetBlockAddress:
546
case ISD::BlockAddress: {
547
const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
548
ID.AddPointer(BA->getBlockAddress());
549
ID.AddInteger(BA->getOffset());
550
ID.AddInteger(BA->getTargetFlags());
553
} // end switch (N->getOpcode())
555
AddNodeIDFlags(ID, N);
557
// Target specific memory nodes could also have address spaces to check.
558
if (N->isTargetMemoryOpcode())
559
ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
562
/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
564
static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
565
AddNodeIDOpcode(ID, N->getOpcode());
566
// Add the return value info.
567
AddNodeIDValueTypes(ID, N->getVTList());
568
// Add the operand info.
569
AddNodeIDOperands(ID, N->ops());
571
// Handle SDNode leafs with special info.
572
AddNodeIDCustom(ID, N);
575
/// encodeMemSDNodeFlags - Generic routine for computing a value for use in
576
/// the CSE map that carries volatility, temporalness, indexing mode, and
577
/// extension/truncation information.
579
static inline unsigned
580
encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
581
bool isNonTemporal, bool isInvariant) {
582
assert((ConvType & 3) == ConvType &&
583
"ConvType may not require more than 2 bits!");
584
assert((AM & 7) == AM &&
585
"AM may not require more than 3 bits!");
589
(isNonTemporal << 6) |
593
//===----------------------------------------------------------------------===//
594
// SelectionDAG Class
595
//===----------------------------------------------------------------------===//
597
/// doNotCSE - Return true if CSE should not be performed for this node.
598
static bool doNotCSE(SDNode *N) {
599
if (N->getValueType(0) == MVT::Glue)
600
return true; // Never CSE anything that produces a flag.
602
switch (N->getOpcode()) {
604
case ISD::HANDLENODE:
606
return true; // Never CSE these nodes.
609
// Check that remaining values produced are not flags.
610
for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
611
if (N->getValueType(i) == MVT::Glue)
612
return true; // Never CSE anything that produces a flag.
617
/// RemoveDeadNodes - This method deletes all unreachable nodes in the
619
void SelectionDAG::RemoveDeadNodes() {
620
// Create a dummy node (which is not added to allnodes), that adds a reference
621
// to the root node, preventing it from being deleted.
622
HandleSDNode Dummy(getRoot());
624
SmallVector<SDNode*, 128> DeadNodes;
626
// Add all obviously-dead nodes to the DeadNodes worklist.
627
for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
629
DeadNodes.push_back(I);
631
RemoveDeadNodes(DeadNodes);
633
// If the root changed (e.g. it was a dead load, update the root).
634
setRoot(Dummy.getValue());
637
/// RemoveDeadNodes - This method deletes the unreachable nodes in the
638
/// given list, and any nodes that become unreachable as a result.
639
void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
641
// Process the worklist, deleting the nodes and adding their uses to the
643
while (!DeadNodes.empty()) {
644
SDNode *N = DeadNodes.pop_back_val();
646
for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
647
DUL->NodeDeleted(N, nullptr);
649
// Take the node out of the appropriate CSE map.
650
RemoveNodeFromCSEMaps(N);
652
// Next, brutally remove the operand list. This is safe to do, as there are
653
// no cycles in the graph.
654
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
656
SDNode *Operand = Use.getNode();
659
// Now that we removed this operand, see if there are no uses of it left.
660
if (Operand->use_empty())
661
DeadNodes.push_back(Operand);
668
void SelectionDAG::RemoveDeadNode(SDNode *N){
669
SmallVector<SDNode*, 16> DeadNodes(1, N);
671
// Create a dummy node that adds a reference to the root node, preventing
672
// it from being deleted. (This matters if the root is an operand of the
674
HandleSDNode Dummy(getRoot());
676
RemoveDeadNodes(DeadNodes);
679
void SelectionDAG::DeleteNode(SDNode *N) {
680
// First take this out of the appropriate CSE map.
681
RemoveNodeFromCSEMaps(N);
683
// Finally, remove uses due to operands of this node, remove from the
684
// AllNodes list, and delete the node.
685
DeleteNodeNotInCSEMaps(N);
688
void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
689
assert(N != AllNodes.begin() && "Cannot delete the entry node!");
690
assert(N->use_empty() && "Cannot delete a node that is not dead!");
692
// Drop all of the operands and decrement used node's use counts.
698
void SDDbgInfo::erase(const SDNode *Node) {
699
DbgValMapType::iterator I = DbgValMap.find(Node);
700
if (I == DbgValMap.end())
702
for (auto &Val: I->second)
703
Val->setIsInvalidated();
707
void SelectionDAG::DeallocateNode(SDNode *N) {
708
if (N->OperandsNeedDelete)
709
delete[] N->OperandList;
711
// Set the opcode to DELETED_NODE to help catch bugs when node
712
// memory is reallocated.
713
N->NodeType = ISD::DELETED_NODE;
715
NodeAllocator.Deallocate(AllNodes.remove(N));
717
// If any of the SDDbgValue nodes refer to this SDNode, invalidate
718
// them and forget about that node.
723
/// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
724
static void VerifySDNode(SDNode *N) {
725
switch (N->getOpcode()) {
728
case ISD::BUILD_PAIR: {
729
EVT VT = N->getValueType(0);
730
assert(N->getNumValues() == 1 && "Too many results!");
731
assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
732
"Wrong return type!");
733
assert(N->getNumOperands() == 2 && "Wrong number of operands!");
734
assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
735
"Mismatched operand types!");
736
assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
737
"Wrong operand type!");
738
assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
739
"Wrong return type size");
742
case ISD::BUILD_VECTOR: {
743
assert(N->getNumValues() == 1 && "Too many results!");
744
assert(N->getValueType(0).isVector() && "Wrong return type!");
745
assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
746
"Wrong number of operands!");
747
EVT EltVT = N->getValueType(0).getVectorElementType();
748
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
749
assert((I->getValueType() == EltVT ||
750
(EltVT.isInteger() && I->getValueType().isInteger() &&
751
EltVT.bitsLE(I->getValueType()))) &&
752
"Wrong operand type!");
753
assert(I->getValueType() == N->getOperand(0).getValueType() &&
754
"Operands must all have the same type");
762
/// \brief Insert a newly allocated node into the DAG.
764
/// Handles insertion into the all nodes list and CSE map, as well as
765
/// verification and other common operations when a new node is allocated.
766
void SelectionDAG::InsertNode(SDNode *N) {
767
AllNodes.push_back(N);
773
/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
774
/// correspond to it. This is useful when we're about to delete or repurpose
775
/// the node. We don't want future request for structurally identical nodes
776
/// to return N anymore.
777
bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
779
switch (N->getOpcode()) {
780
case ISD::HANDLENODE: return false; // noop.
782
assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
783
"Cond code doesn't exist!");
784
Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
785
CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
787
case ISD::ExternalSymbol:
788
Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
790
case ISD::TargetExternalSymbol: {
791
ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
792
Erased = TargetExternalSymbols.erase(
793
std::pair<std::string,unsigned char>(ESN->getSymbol(),
794
ESN->getTargetFlags()));
797
case ISD::MCSymbol: {
798
auto *MCSN = cast<MCSymbolSDNode>(N);
799
Erased = MCSymbols.erase(MCSN->getMCSymbol());
802
case ISD::VALUETYPE: {
803
EVT VT = cast<VTSDNode>(N)->getVT();
804
if (VT.isExtended()) {
805
Erased = ExtendedValueTypeNodes.erase(VT);
807
Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
808
ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
813
// Remove it from the CSE Map.
814
assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
815
assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
816
Erased = CSEMap.RemoveNode(N);
820
// Verify that the node was actually in one of the CSE maps, unless it has a
821
// flag result (which cannot be CSE'd) or is one of the special cases that are
822
// not subject to CSE.
823
if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
824
!N->isMachineOpcode() && !doNotCSE(N)) {
827
llvm_unreachable("Node is not in map!");
833
/// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
834
/// maps and modified in place. Add it back to the CSE maps, unless an identical
835
/// node already exists, in which case transfer all its users to the existing
836
/// node. This transfer can potentially trigger recursive merging.
839
SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
840
// For node types that aren't CSE'd, just act as if no identical node
843
SDNode *Existing = CSEMap.GetOrInsertNode(N);
845
// If there was already an existing matching node, use ReplaceAllUsesWith
846
// to replace the dead one with the existing one. This can cause
847
// recursive merging of other unrelated nodes down the line.
848
ReplaceAllUsesWith(N, Existing);
850
// N is now dead. Inform the listeners and delete it.
851
for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
852
DUL->NodeDeleted(N, Existing);
853
DeleteNodeNotInCSEMaps(N);
858
// If the node doesn't already exist, we updated it. Inform listeners.
859
for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
863
/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
864
/// were replaced with those specified. If this node is never memoized,
865
/// return null, otherwise return a pointer to the slot it would take. If a
866
/// node already exists with these operands, the slot will be non-null.
867
SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
872
SDValue Ops[] = { Op };
874
AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
875
AddNodeIDCustom(ID, N);
876
SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
880
/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
881
/// were replaced with those specified. If this node is never memoized,
882
/// return null, otherwise return a pointer to the slot it would take. If a
883
/// node already exists with these operands, the slot will be non-null.
884
SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
885
SDValue Op1, SDValue Op2,
890
SDValue Ops[] = { Op1, Op2 };
892
AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
893
AddNodeIDCustom(ID, N);
894
SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
899
/// FindModifiedNodeSlot - Find a slot for the specified node if its operands
900
/// were replaced with those specified. If this node is never memoized,
901
/// return null, otherwise return a pointer to the slot it would take. If a
902
/// node already exists with these operands, the slot will be non-null.
903
SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
909
AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
910
AddNodeIDCustom(ID, N);
911
SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
915
/// getEVTAlignment - Compute the default alignment value for the
918
unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
919
Type *Ty = VT == MVT::iPTR ?
920
PointerType::get(Type::getInt8Ty(*getContext()), 0) :
921
VT.getTypeForEVT(*getContext());
923
return getDataLayout().getABITypeAlignment(Ty);
926
// EntryNode could meaningfully have debug info if we can find it...
927
SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
928
: TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
929
EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
930
Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
931
UpdateListeners(nullptr) {
932
AllNodes.push_back(&EntryNode);
933
DbgInfo = new SDDbgInfo();
936
void SelectionDAG::init(MachineFunction &mf) {
938
TLI = getSubtarget().getTargetLowering();
939
TSI = getSubtarget().getSelectionDAGInfo();
940
Context = &mf.getFunction()->getContext();
943
SelectionDAG::~SelectionDAG() {
944
assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
949
void SelectionDAG::allnodes_clear() {
950
assert(&*AllNodes.begin() == &EntryNode);
951
AllNodes.remove(AllNodes.begin());
952
while (!AllNodes.empty())
953
DeallocateNode(AllNodes.begin());
956
BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
957
SDVTList VTs, SDValue N1,
959
const SDNodeFlags *Flags) {
960
if (isBinOpWithFlags(Opcode)) {
961
// If no flags were passed in, use a default flags object.
963
if (Flags == nullptr)
966
BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967
Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
972
BinarySDNode *N = new (NodeAllocator)
973
BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
977
SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
979
SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
981
switch (N->getOpcode()) {
984
case ISD::ConstantFP:
985
llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
986
"debug location. Use another overload.");
992
SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
993
DebugLoc DL, void *&InsertPos) {
994
SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
996
switch (N->getOpcode()) {
997
default: break; // Process only regular (non-target) constant nodes.
999
case ISD::ConstantFP:
1000
// Erase debug location from the node if the node is used at several
1001
// different places to do not propagate one location to all uses as it
1002
// leads to incorrect debug info.
1003
if (N->getDebugLoc() != DL)
1004
N->setDebugLoc(DebugLoc());
1011
void SelectionDAG::clear() {
1013
OperandAllocator.Reset();
1016
ExtendedValueTypeNodes.clear();
1017
ExternalSymbols.clear();
1018
TargetExternalSymbols.clear();
1020
std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1021
static_cast<CondCodeSDNode*>(nullptr));
1022
std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1023
static_cast<SDNode*>(nullptr));
1025
EntryNode.UseList = nullptr;
1026
AllNodes.push_back(&EntryNode);
1027
Root = getEntryNode();
1031
SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1032
return VT.bitsGT(Op.getValueType()) ?
1033
getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1034
getNode(ISD::TRUNCATE, DL, VT, Op);
1037
SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1038
return VT.bitsGT(Op.getValueType()) ?
1039
getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1040
getNode(ISD::TRUNCATE, DL, VT, Op);
1043
SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1044
return VT.bitsGT(Op.getValueType()) ?
1045
getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1046
getNode(ISD::TRUNCATE, DL, VT, Op);
1049
SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1051
if (VT.bitsLE(Op.getValueType()))
1052
return getNode(ISD::TRUNCATE, SL, VT, Op);
1054
TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1055
return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1058
SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1059
assert(!VT.isVector() &&
1060
"getZeroExtendInReg should use the vector element type instead of "
1061
"the vector type!");
1062
if (Op.getValueType() == VT) return Op;
1063
unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1064
APInt Imm = APInt::getLowBitsSet(BitWidth,
1065
VT.getSizeInBits());
1066
return getNode(ISD::AND, DL, Op.getValueType(), Op,
1067
getConstant(Imm, DL, Op.getValueType()));
1070
SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1071
assert(VT.isVector() && "This DAG node is restricted to vector types.");
1072
assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1073
"The sizes of the input and result must match in order to perform the "
1074
"extend in-register.");
1075
assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1076
"The destination vector type must have fewer lanes than the input.");
1077
return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1080
SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1081
assert(VT.isVector() && "This DAG node is restricted to vector types.");
1082
assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1083
"The sizes of the input and result must match in order to perform the "
1084
"extend in-register.");
1085
assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1086
"The destination vector type must have fewer lanes than the input.");
1087
return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1090
SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1091
assert(VT.isVector() && "This DAG node is restricted to vector types.");
1092
assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1093
"The sizes of the input and result must match in order to perform the "
1094
"extend in-register.");
1095
assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1096
"The destination vector type must have fewer lanes than the input.");
1097
return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1100
/// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1102
SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1103
EVT EltVT = VT.getScalarType();
1105
getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1106
return getNode(ISD::XOR, DL, VT, Val, NegOne);
1109
SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1110
EVT EltVT = VT.getScalarType();
1112
switch (TLI->getBooleanContents(VT)) {
1113
case TargetLowering::ZeroOrOneBooleanContent:
1114
case TargetLowering::UndefinedBooleanContent:
1115
TrueValue = getConstant(1, DL, VT);
1117
case TargetLowering::ZeroOrNegativeOneBooleanContent:
1118
TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1122
return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1125
SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1127
EVT EltVT = VT.getScalarType();
1128
assert((EltVT.getSizeInBits() >= 64 ||
1129
(uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1130
"getConstant with a uint64_t value that doesn't fit in the type!");
1131
return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1134
SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1137
return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1140
SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1141
bool isT, bool isO) {
1142
assert(VT.isInteger() && "Cannot create FP integer constant!");
1144
EVT EltVT = VT.getScalarType();
1145
const ConstantInt *Elt = &Val;
1147
// In some cases the vector type is legal but the element type is illegal and
1148
// needs to be promoted, for example v8i8 on ARM. In this case, promote the
1149
// inserted value (the type does not need to match the vector element type).
1150
// Any extra bits introduced will be truncated away.
1151
if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1152
TargetLowering::TypePromoteInteger) {
1153
EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1154
APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1155
Elt = ConstantInt::get(*getContext(), NewVal);
1157
// In other cases the element type is illegal and needs to be expanded, for
1158
// example v2i64 on MIPS32. In this case, find the nearest legal type, split
1159
// the value into n parts and use a vector type with n-times the elements.
1160
// Then bitcast to the type requested.
1161
// Legalizing constants too early makes the DAGCombiner's job harder so we
1162
// only legalize if the DAG tells us we must produce legal types.
1163
else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1164
TLI->getTypeAction(*getContext(), EltVT) ==
1165
TargetLowering::TypeExpandInteger) {
1166
APInt NewVal = Elt->getValue();
1167
EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1168
unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1169
unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1170
EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1172
// Check the temporary vector is the correct size. If this fails then
1173
// getTypeToTransformTo() probably returned a type whose size (in bits)
1174
// isn't a power-of-2 factor of the requested type size.
1175
assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1177
SmallVector<SDValue, 2> EltParts;
1178
for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1179
EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1180
.trunc(ViaEltSizeInBits), DL,
1181
ViaEltVT, isT, isO));
1184
// EltParts is currently in little endian order. If we actually want
1185
// big-endian order then reverse it now.
1186
if (getDataLayout().isBigEndian())
1187
std::reverse(EltParts.begin(), EltParts.end());
1189
// The elements must be reversed when the element order is different
1190
// to the endianness of the elements (because the BITCAST is itself a
1191
// vector shuffle in this situation). However, we do not need any code to
1192
// perform this reversal because getConstant() is producing a vector
1194
// This situation occurs in MIPS MSA.
1196
SmallVector<SDValue, 8> Ops;
1197
for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1198
Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1200
SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1201
getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1206
assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1207
"APInt size does not match type size!");
1208
unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1209
FoldingSetNodeID ID;
1210
AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1214
SDNode *N = nullptr;
1215
if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1217
return SDValue(N, 0);
1220
N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1222
CSEMap.InsertNode(N, IP);
1226
SDValue Result(N, 0);
1227
if (VT.isVector()) {
1228
SmallVector<SDValue, 8> Ops;
1229
Ops.assign(VT.getVectorNumElements(), Result);
1230
Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1235
SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1236
return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1239
SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1241
return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1244
SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1246
assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1248
EVT EltVT = VT.getScalarType();
1250
// Do the map lookup using the actual bit pattern for the floating point
1251
// value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1252
// we don't have issues with SNANs.
1253
unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1254
FoldingSetNodeID ID;
1255
AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1258
SDNode *N = nullptr;
1259
if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1261
return SDValue(N, 0);
1264
N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1266
CSEMap.InsertNode(N, IP);
1270
SDValue Result(N, 0);
1271
if (VT.isVector()) {
1272
SmallVector<SDValue, 8> Ops;
1273
Ops.assign(VT.getVectorNumElements(), Result);
1274
Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1279
SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1281
EVT EltVT = VT.getScalarType();
1282
if (EltVT==MVT::f32)
1283
return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1284
else if (EltVT==MVT::f64)
1285
return getConstantFP(APFloat(Val), DL, VT, isTarget);
1286
else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1289
APFloat apf = APFloat(Val);
1290
apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1292
return getConstantFP(apf, DL, VT, isTarget);
1294
llvm_unreachable("Unsupported type in getConstantFP");
1297
SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1298
EVT VT, int64_t Offset,
1300
unsigned char TargetFlags) {
1301
assert((TargetFlags == 0 || isTargetGA) &&
1302
"Cannot set target flags on target-independent globals");
1304
// Truncate (with sign-extension) the offset value to the pointer size.
1305
unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1307
Offset = SignExtend64(Offset, BitWidth);
1310
if (GV->isThreadLocal())
1311
Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1313
Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1315
FoldingSetNodeID ID;
1316
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1318
ID.AddInteger(Offset);
1319
ID.AddInteger(TargetFlags);
1320
ID.AddInteger(GV->getType()->getAddressSpace());
1322
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1323
return SDValue(E, 0);
1325
SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1326
DL.getDebugLoc(), GV, VT,
1327
Offset, TargetFlags);
1328
CSEMap.InsertNode(N, IP);
1330
return SDValue(N, 0);
1333
SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1334
unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1335
FoldingSetNodeID ID;
1336
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1339
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1340
return SDValue(E, 0);
1342
SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1343
CSEMap.InsertNode(N, IP);
1345
return SDValue(N, 0);
1348
SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1349
unsigned char TargetFlags) {
1350
assert((TargetFlags == 0 || isTarget) &&
1351
"Cannot set target flags on target-independent jump tables");
1352
unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1353
FoldingSetNodeID ID;
1354
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1356
ID.AddInteger(TargetFlags);
1358
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1359
return SDValue(E, 0);
1361
SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1363
CSEMap.InsertNode(N, IP);
1365
return SDValue(N, 0);
1368
SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1369
unsigned Alignment, int Offset,
1371
unsigned char TargetFlags) {
1372
assert((TargetFlags == 0 || isTarget) &&
1373
"Cannot set target flags on target-independent globals");
1375
Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1376
unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1377
FoldingSetNodeID ID;
1378
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1379
ID.AddInteger(Alignment);
1380
ID.AddInteger(Offset);
1382
ID.AddInteger(TargetFlags);
1384
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1385
return SDValue(E, 0);
1387
SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1388
Alignment, TargetFlags);
1389
CSEMap.InsertNode(N, IP);
1391
return SDValue(N, 0);
1395
SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1396
unsigned Alignment, int Offset,
1398
unsigned char TargetFlags) {
1399
assert((TargetFlags == 0 || isTarget) &&
1400
"Cannot set target flags on target-independent globals");
1402
Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1403
unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1404
FoldingSetNodeID ID;
1405
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1406
ID.AddInteger(Alignment);
1407
ID.AddInteger(Offset);
1408
C->addSelectionDAGCSEId(ID);
1409
ID.AddInteger(TargetFlags);
1411
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1412
return SDValue(E, 0);
1414
SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1415
Alignment, TargetFlags);
1416
CSEMap.InsertNode(N, IP);
1418
return SDValue(N, 0);
1421
SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1422
unsigned char TargetFlags) {
1423
FoldingSetNodeID ID;
1424
AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1425
ID.AddInteger(Index);
1426
ID.AddInteger(Offset);
1427
ID.AddInteger(TargetFlags);
1429
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1430
return SDValue(E, 0);
1432
SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1434
CSEMap.InsertNode(N, IP);
1436
return SDValue(N, 0);
1439
SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1440
FoldingSetNodeID ID;
1441
AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1444
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1445
return SDValue(E, 0);
1447
SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1448
CSEMap.InsertNode(N, IP);
1450
return SDValue(N, 0);
1453
SDValue SelectionDAG::getValueType(EVT VT) {
1454
if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1455
ValueTypeNodes.size())
1456
ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1458
SDNode *&N = VT.isExtended() ?
1459
ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1461
if (N) return SDValue(N, 0);
1462
N = new (NodeAllocator) VTSDNode(VT);
1464
return SDValue(N, 0);
1467
SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1468
SDNode *&N = ExternalSymbols[Sym];
1469
if (N) return SDValue(N, 0);
1470
N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1472
return SDValue(N, 0);
1475
SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1476
SDNode *&N = MCSymbols[Sym];
1478
return SDValue(N, 0);
1479
N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1481
return SDValue(N, 0);
1484
SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1485
unsigned char TargetFlags) {
1487
TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1489
if (N) return SDValue(N, 0);
1490
N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1492
return SDValue(N, 0);
1495
SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1496
if ((unsigned)Cond >= CondCodeNodes.size())
1497
CondCodeNodes.resize(Cond+1);
1499
if (!CondCodeNodes[Cond]) {
1500
CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1501
CondCodeNodes[Cond] = N;
1505
return SDValue(CondCodeNodes[Cond], 0);
1508
// commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1509
// the shuffle mask M that point at N1 to point at N2, and indices that point
1510
// N2 to point at N1.
1511
static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1513
ShuffleVectorSDNode::commuteMask(M);
1516
SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1517
SDValue N2, const int *Mask) {
1518
assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1519
"Invalid VECTOR_SHUFFLE");
1521
// Canonicalize shuffle undef, undef -> undef
1522
if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1523
return getUNDEF(VT);
1525
// Validate that all indices in Mask are within the range of the elements
1526
// input to the shuffle.
1527
unsigned NElts = VT.getVectorNumElements();
1528
SmallVector<int, 8> MaskVec;
1529
for (unsigned i = 0; i != NElts; ++i) {
1530
assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1531
MaskVec.push_back(Mask[i]);
1534
// Canonicalize shuffle v, v -> v, undef
1537
for (unsigned i = 0; i != NElts; ++i)
1538
if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1541
// Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1542
if (N1.getOpcode() == ISD::UNDEF)
1543
commuteShuffle(N1, N2, MaskVec);
1545
// If shuffling a splat, try to blend the splat instead. We do this here so
1546
// that even when this arises during lowering we don't have to re-handle it.
1547
auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1548
BitVector UndefElements;
1549
SDValue Splat = BV->getSplatValue(&UndefElements);
1553
for (int i = 0; i < (int)NElts; ++i) {
1554
if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1557
// If this input comes from undef, mark it as such.
1558
if (UndefElements[MaskVec[i] - Offset]) {
1563
// If we can blend a non-undef lane, use that instead.
1564
if (!UndefElements[i])
1565
MaskVec[i] = i + Offset;
1568
if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1569
BlendSplat(N1BV, 0);
1570
if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1571
BlendSplat(N2BV, NElts);
1573
// Canonicalize all index into lhs, -> shuffle lhs, undef
1574
// Canonicalize all index into rhs, -> shuffle rhs, undef
1575
bool AllLHS = true, AllRHS = true;
1576
bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1577
for (unsigned i = 0; i != NElts; ++i) {
1578
if (MaskVec[i] >= (int)NElts) {
1583
} else if (MaskVec[i] >= 0) {
1587
if (AllLHS && AllRHS)
1588
return getUNDEF(VT);
1589
if (AllLHS && !N2Undef)
1593
commuteShuffle(N1, N2, MaskVec);
1595
// Reset our undef status after accounting for the mask.
1596
N2Undef = N2.getOpcode() == ISD::UNDEF;
1597
// Re-check whether both sides ended up undef.
1598
if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1599
return getUNDEF(VT);
1601
// If Identity shuffle return that node.
1602
bool Identity = true, AllSame = true;
1603
for (unsigned i = 0; i != NElts; ++i) {
1604
if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1605
if (MaskVec[i] != MaskVec[0]) AllSame = false;
1607
if (Identity && NElts)
1610
// Shuffling a constant splat doesn't change the result.
1614
// Look through any bitcasts. We check that these don't change the number
1615
// (and size) of elements and just changes their types.
1616
while (V.getOpcode() == ISD::BITCAST)
1617
V = V->getOperand(0);
1619
// A splat should always show up as a build vector node.
1620
if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1621
BitVector UndefElements;
1622
SDValue Splat = BV->getSplatValue(&UndefElements);
1623
// If this is a splat of an undef, shuffling it is also undef.
1624
if (Splat && Splat.getOpcode() == ISD::UNDEF)
1625
return getUNDEF(VT);
1628
V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1630
// We only have a splat which can skip shuffles if there is a splatted
1631
// value and no undef lanes rearranged by the shuffle.
1632
if (Splat && UndefElements.none()) {
1633
// Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1634
// number of elements match or the value splatted is a zero constant.
1637
if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1638
if (C->isNullValue())
1642
// If the shuffle itself creates a splat, build the vector directly.
1643
if (AllSame && SameNumElts) {
1644
const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1645
SmallVector<SDValue, 8> Ops(NElts, Splatted);
1647
EVT BuildVT = BV->getValueType(0);
1648
SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1650
// We may have jumped through bitcasts, so the type of the
1651
// BUILD_VECTOR may not match the type of the shuffle.
1653
NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1659
FoldingSetNodeID ID;
1660
SDValue Ops[2] = { N1, N2 };
1661
AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1662
for (unsigned i = 0; i != NElts; ++i)
1663
ID.AddInteger(MaskVec[i]);
1666
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1667
return SDValue(E, 0);
1669
// Allocate the mask array for the node out of the BumpPtrAllocator, since
1670
// SDNode doesn't have access to it. This memory will be "leaked" when
1671
// the node is deallocated, but recovered when the NodeAllocator is released.
1672
int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1673
memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1675
ShuffleVectorSDNode *N =
1676
new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1677
dl.getDebugLoc(), N1, N2,
1679
CSEMap.InsertNode(N, IP);
1681
return SDValue(N, 0);
1684
SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1685
MVT VT = SV.getSimpleValueType(0);
1686
SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1687
ShuffleVectorSDNode::commuteMask(MaskVec);
1689
SDValue Op0 = SV.getOperand(0);
1690
SDValue Op1 = SV.getOperand(1);
1691
return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1694
SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1695
SDValue Val, SDValue DTy,
1696
SDValue STy, SDValue Rnd, SDValue Sat,
1697
ISD::CvtCode Code) {
1698
// If the src and dest types are the same and the conversion is between
1699
// integer types of the same sign or two floats, no conversion is necessary.
1701
(Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1704
FoldingSetNodeID ID;
1705
SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1706
AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1708
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1709
return SDValue(E, 0);
1711
CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1714
CSEMap.InsertNode(N, IP);
1716
return SDValue(N, 0);
1719
SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1720
FoldingSetNodeID ID;
1721
AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1722
ID.AddInteger(RegNo);
1724
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1725
return SDValue(E, 0);
1727
SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1728
CSEMap.InsertNode(N, IP);
1730
return SDValue(N, 0);
1733
SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1734
FoldingSetNodeID ID;
1735
AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1736
ID.AddPointer(RegMask);
1738
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1739
return SDValue(E, 0);
1741
SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1742
CSEMap.InsertNode(N, IP);
1744
return SDValue(N, 0);
1747
SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1748
FoldingSetNodeID ID;
1749
SDValue Ops[] = { Root };
1750
AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1751
ID.AddPointer(Label);
1753
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1754
return SDValue(E, 0);
1756
SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1757
dl.getDebugLoc(), Root, Label);
1758
CSEMap.InsertNode(N, IP);
1760
return SDValue(N, 0);
1764
SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1767
unsigned char TargetFlags) {
1768
unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1770
FoldingSetNodeID ID;
1771
AddNodeIDNode(ID, Opc, getVTList(VT), None);
1773
ID.AddInteger(Offset);
1774
ID.AddInteger(TargetFlags);
1776
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1777
return SDValue(E, 0);
1779
SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1781
CSEMap.InsertNode(N, IP);
1783
return SDValue(N, 0);
1786
SDValue SelectionDAG::getSrcValue(const Value *V) {
1787
assert((!V || V->getType()->isPointerTy()) &&
1788
"SrcValue is not a pointer?");
1790
FoldingSetNodeID ID;
1791
AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1795
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1796
return SDValue(E, 0);
1798
SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1799
CSEMap.InsertNode(N, IP);
1801
return SDValue(N, 0);
1804
/// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1805
SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1806
FoldingSetNodeID ID;
1807
AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1811
if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1812
return SDValue(E, 0);
1814
SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1815
CSEMap.InsertNode(N, IP);
1817
return SDValue(N, 0);
1820
SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1821
if (VT == V.getValueType())
1824
return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1827
/// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1828
SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1829
unsigned SrcAS, unsigned DestAS) {
1830
SDValue Ops[] = {Ptr};
1831
FoldingSetNodeID ID;
1832
AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1833
ID.AddInteger(SrcAS);
1834
ID.AddInteger(DestAS);
1837
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1838
return SDValue(E, 0);
1840
SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1842
VT, Ptr, SrcAS, DestAS);
1843
CSEMap.InsertNode(N, IP);
1845
return SDValue(N, 0);
1848
/// getShiftAmountOperand - Return the specified value casted to
1849
/// the target's desired shift amount type.
1850
SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1851
EVT OpTy = Op.getValueType();
1852
EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1853
if (OpTy == ShTy || OpTy.isVector()) return Op;
1855
ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1856
return getNode(Opcode, SDLoc(Op), ShTy, Op);
1859
/// CreateStackTemporary - Create a stack temporary, suitable for holding the
1860
/// specified value type.
1861
SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1862
MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1863
unsigned ByteSize = VT.getStoreSize();
1864
Type *Ty = VT.getTypeForEVT(*getContext());
1865
unsigned StackAlign =
1866
std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1868
int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1869
return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1872
/// CreateStackTemporary - Create a stack temporary suitable for holding
1873
/// either of the specified value types.
1874
SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1875
unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1876
VT2.getStoreSizeInBits())/8;
1877
Type *Ty1 = VT1.getTypeForEVT(*getContext());
1878
Type *Ty2 = VT2.getTypeForEVT(*getContext());
1879
const DataLayout &DL = getDataLayout();
1881
std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1883
MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1884
int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1885
return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1888
SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1889
SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1890
// These setcc operations always fold.
1894
case ISD::SETFALSE2: return getConstant(0, dl, VT);
1896
case ISD::SETTRUE2: {
1897
TargetLowering::BooleanContent Cnt =
1898
TLI->getBooleanContents(N1->getValueType(0));
1900
Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1914
assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1918
if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1919
const APInt &C2 = N2C->getAPIntValue();
1920
if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1921
const APInt &C1 = N1C->getAPIntValue();
1924
default: llvm_unreachable("Unknown integer setcc!");
1925
case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1926
case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1927
case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1928
case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1929
case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1930
case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1931
case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1932
case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1933
case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1934
case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1938
if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1939
if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1940
APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1943
case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1944
return getUNDEF(VT);
1946
case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1947
case ISD::SETNE: if (R==APFloat::cmpUnordered)
1948
return getUNDEF(VT);
1950
case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1951
R==APFloat::cmpLessThan, dl, VT);
1952
case ISD::SETLT: if (R==APFloat::cmpUnordered)
1953
return getUNDEF(VT);
1955
case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1956
case ISD::SETGT: if (R==APFloat::cmpUnordered)
1957
return getUNDEF(VT);
1959
case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1960
case ISD::SETLE: if (R==APFloat::cmpUnordered)
1961
return getUNDEF(VT);
1963
case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1964
R==APFloat::cmpEqual, dl, VT);
1965
case ISD::SETGE: if (R==APFloat::cmpUnordered)
1966
return getUNDEF(VT);
1968
case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1969
R==APFloat::cmpEqual, dl, VT);
1970
case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1971
case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1972
case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1973
R==APFloat::cmpEqual, dl, VT);
1974
case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1975
case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1976
R==APFloat::cmpLessThan, dl, VT);
1977
case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1978
R==APFloat::cmpUnordered, dl, VT);
1979
case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1980
case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1983
// Ensure that the constant occurs on the RHS.
1984
ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1985
MVT CompVT = N1.getValueType().getSimpleVT();
1986
if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1989
return getSetCC(dl, VT, N2, N1, SwappedCond);
1993
// Could not fold it.
1997
/// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1998
/// use this predicate to simplify operations downstream.
1999
bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2000
// This predicate is not safe for vector operations.
2001
if (Op.getValueType().isVector())
2004
unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2005
return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2008
/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2009
/// this predicate to simplify operations downstream. Mask is known to be zero
2010
/// for bits that V cannot have.
2011
bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2012
unsigned Depth) const {
2013
APInt KnownZero, KnownOne;
2014
computeKnownBits(Op, KnownZero, KnownOne, Depth);
2015
return (KnownZero & Mask) == Mask;
2018
/// Determine which bits of Op are known to be either zero or one and return
2019
/// them in the KnownZero/KnownOne bitsets.
2020
void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2021
APInt &KnownOne, unsigned Depth) const {
2022
unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2024
KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2026
return; // Limit search depth.
2028
APInt KnownZero2, KnownOne2;
2030
switch (Op.getOpcode()) {
2032
// We know all of the bits for a constant!
2033
KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2034
KnownZero = ~KnownOne;
2037
// If either the LHS or the RHS are Zero, the result is zero.
2038
computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2039
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2041
// Output known-1 bits are only known if set in both the LHS & RHS.
2042
KnownOne &= KnownOne2;
2043
// Output known-0 are known to be clear if zero in either the LHS | RHS.
2044
KnownZero |= KnownZero2;
2047
computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2048
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2050
// Output known-0 bits are only known if clear in both the LHS & RHS.
2051
KnownZero &= KnownZero2;
2052
// Output known-1 are known to be set if set in either the LHS | RHS.
2053
KnownOne |= KnownOne2;
2056
computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2057
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2059
// Output known-0 bits are known if clear or set in both the LHS & RHS.
2060
APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2061
// Output known-1 are known to be set if set in only one of the LHS, RHS.
2062
KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2063
KnownZero = KnownZeroOut;
2067
computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2068
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2070
// If low bits are zero in either operand, output low known-0 bits.
2071
// Also compute a conserative estimate for high known-0 bits.
2072
// More trickiness is possible, but this is sufficient for the
2073
// interesting case of alignment computation.
2074
KnownOne.clearAllBits();
2075
unsigned TrailZ = KnownZero.countTrailingOnes() +
2076
KnownZero2.countTrailingOnes();
2077
unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2078
KnownZero2.countLeadingOnes(),
2079
BitWidth) - BitWidth;
2081
TrailZ = std::min(TrailZ, BitWidth);
2082
LeadZ = std::min(LeadZ, BitWidth);
2083
KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2084
APInt::getHighBitsSet(BitWidth, LeadZ);
2088
// For the purposes of computing leading zeros we can conservatively
2089
// treat a udiv as a logical right shift by the power of 2 known to
2090
// be less than the denominator.
2091
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2092
unsigned LeadZ = KnownZero2.countLeadingOnes();
2094
KnownOne2.clearAllBits();
2095
KnownZero2.clearAllBits();
2096
computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2097
unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2098
if (RHSUnknownLeadingOnes != BitWidth)
2099
LeadZ = std::min(BitWidth,
2100
LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2102
KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2106
computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2107
computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2109
// Only known if known in both the LHS and RHS.
2110
KnownOne &= KnownOne2;
2111
KnownZero &= KnownZero2;
2113
case ISD::SELECT_CC:
2114
computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2115
computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2117
// Only known if known in both the LHS and RHS.
2118
KnownOne &= KnownOne2;
2119
KnownZero &= KnownZero2;
2127
if (Op.getResNo() != 1)
2129
// The boolean result conforms to getBooleanContents.
2130
// If we know the result of a setcc has the top bits zero, use this info.
2131
// We know that we have an integer-based boolean since these operations
2132
// are only available for integer.
2133
if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2134
TargetLowering::ZeroOrOneBooleanContent &&
2136
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2139
// If we know the result of a setcc has the top bits zero, use this info.
2140
if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2141
TargetLowering::ZeroOrOneBooleanContent &&
2143
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2146
// (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2147
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2148
unsigned ShAmt = SA->getZExtValue();
2150
// If the shift count is an invalid immediate, don't do anything.
2151
if (ShAmt >= BitWidth)
2154
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2155
KnownZero <<= ShAmt;
2157
// low bits known zero.
2158
KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2162
// (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2163
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2164
unsigned ShAmt = SA->getZExtValue();
2166
// If the shift count is an invalid immediate, don't do anything.
2167
if (ShAmt >= BitWidth)
2170
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2171
KnownZero = KnownZero.lshr(ShAmt);
2172
KnownOne = KnownOne.lshr(ShAmt);
2174
APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2175
KnownZero |= HighBits; // High bits known zero.
2179
if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2180
unsigned ShAmt = SA->getZExtValue();
2182
// If the shift count is an invalid immediate, don't do anything.
2183
if (ShAmt >= BitWidth)
2186
// If any of the demanded bits are produced by the sign extension, we also
2187
// demand the input sign bit.
2188
APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2190
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2191
KnownZero = KnownZero.lshr(ShAmt);
2192
KnownOne = KnownOne.lshr(ShAmt);
2194
// Handle the sign bits.
2195
APInt SignBit = APInt::getSignBit(BitWidth);
2196
SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2198
if (KnownZero.intersects(SignBit)) {
2199
KnownZero |= HighBits; // New bits are known zero.
2200
} else if (KnownOne.intersects(SignBit)) {
2201
KnownOne |= HighBits; // New bits are known one.
2205
case ISD::SIGN_EXTEND_INREG: {
2206
EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2207
unsigned EBits = EVT.getScalarType().getSizeInBits();
2209
// Sign extension. Compute the demanded bits in the result that are not
2210
// present in the input.
2211
APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2213
APInt InSignBit = APInt::getSignBit(EBits);
2214
APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2216
// If the sign extended bits are demanded, we know that the sign
2218
InSignBit = InSignBit.zext(BitWidth);
2219
if (NewBits.getBoolValue())
2220
InputDemandedBits |= InSignBit;
2222
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2223
KnownOne &= InputDemandedBits;
2224
KnownZero &= InputDemandedBits;
2226
// If the sign bit of the input is known set or clear, then we know the
2227
// top bits of the result.
2228
if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2229
KnownZero |= NewBits;
2230
KnownOne &= ~NewBits;
2231
} else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2232
KnownOne |= NewBits;
2233
KnownZero &= ~NewBits;
2234
} else { // Input sign bit unknown
2235
KnownZero &= ~NewBits;
2236
KnownOne &= ~NewBits;
2241
case ISD::CTTZ_ZERO_UNDEF:
2243
case ISD::CTLZ_ZERO_UNDEF:
2245
unsigned LowBits = Log2_32(BitWidth)+1;
2246
KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2247
KnownOne.clearAllBits();
2251
LoadSDNode *LD = cast<LoadSDNode>(Op);
2252
// If this is a ZEXTLoad and we are looking at the loaded value.
2253
if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2254
EVT VT = LD->getMemoryVT();
2255
unsigned MemBits = VT.getScalarType().getSizeInBits();
2256
KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2257
} else if (const MDNode *Ranges = LD->getRanges()) {
2258
computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2262
case ISD::ZERO_EXTEND: {
2263
EVT InVT = Op.getOperand(0).getValueType();
2264
unsigned InBits = InVT.getScalarType().getSizeInBits();
2265
APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2266
KnownZero = KnownZero.trunc(InBits);
2267
KnownOne = KnownOne.trunc(InBits);
2268
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2269
KnownZero = KnownZero.zext(BitWidth);
2270
KnownOne = KnownOne.zext(BitWidth);
2271
KnownZero |= NewBits;
2274
case ISD::SIGN_EXTEND: {
2275
EVT InVT = Op.getOperand(0).getValueType();
2276
unsigned InBits = InVT.getScalarType().getSizeInBits();
2277
APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2279
KnownZero = KnownZero.trunc(InBits);
2280
KnownOne = KnownOne.trunc(InBits);
2281
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2283
// Note if the sign bit is known to be zero or one.
2284
bool SignBitKnownZero = KnownZero.isNegative();
2285
bool SignBitKnownOne = KnownOne.isNegative();
2287
KnownZero = KnownZero.zext(BitWidth);
2288
KnownOne = KnownOne.zext(BitWidth);
2290
// If the sign bit is known zero or one, the top bits match.
2291
if (SignBitKnownZero)
2292
KnownZero |= NewBits;
2293
else if (SignBitKnownOne)
2294
KnownOne |= NewBits;
2297
case ISD::ANY_EXTEND: {
2298
EVT InVT = Op.getOperand(0).getValueType();
2299
unsigned InBits = InVT.getScalarType().getSizeInBits();
2300
KnownZero = KnownZero.trunc(InBits);
2301
KnownOne = KnownOne.trunc(InBits);
2302
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2303
KnownZero = KnownZero.zext(BitWidth);
2304
KnownOne = KnownOne.zext(BitWidth);
2307
case ISD::TRUNCATE: {
2308
EVT InVT = Op.getOperand(0).getValueType();
2309
unsigned InBits = InVT.getScalarType().getSizeInBits();
2310
KnownZero = KnownZero.zext(InBits);
2311
KnownOne = KnownOne.zext(InBits);
2312
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2313
KnownZero = KnownZero.trunc(BitWidth);
2314
KnownOne = KnownOne.trunc(BitWidth);
2317
case ISD::AssertZext: {
2318
EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2319
APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2320
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2321
KnownZero |= (~InMask);
2322
KnownOne &= (~KnownZero);
2326
// All bits are zero except the low bit.
2327
KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2331
if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2332
// We know that the top bits of C-X are clear if X contains less bits
2333
// than C (i.e. no wrap-around can happen). For example, 20-X is
2334
// positive if we can prove that X is >= 0 and < 16.
2335
if (CLHS->getAPIntValue().isNonNegative()) {
2336
unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2337
// NLZ can't be BitWidth with no sign bit
2338
APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2339
computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2341
// If all of the MaskV bits are known to be zero, then we know the
2342
// output top bits are zero, because we now know that the output is
2344
if ((KnownZero2 & MaskV) == MaskV) {
2345
unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2346
// Top bits known zero.
2347
KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2355
// Output known-0 bits are known if clear or set in both the low clear bits
2356
// common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2357
// low 3 bits clear.
2358
// Output known-0 bits are also known if the top bits of each input are
2359
// known to be clear. For example, if one input has the top 10 bits clear
2360
// and the other has the top 8 bits clear, we know the top 7 bits of the
2361
// output must be clear.
2362
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2363
unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2364
unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2366
computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2367
KnownZeroHigh = std::min(KnownZeroHigh,
2368
KnownZero2.countLeadingOnes());
2369
KnownZeroLow = std::min(KnownZeroLow,
2370
KnownZero2.countTrailingOnes());
2372
if (Op.getOpcode() == ISD::ADD) {
2373
KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2374
if (KnownZeroHigh > 1)
2375
KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2379
// With ADDE, a carry bit may be added in, so we can only use this
2380
// information if we know (at least) that the low two bits are clear. We
2381
// then return to the caller that the low bit is unknown but that other bits
2383
if (KnownZeroLow >= 2) // ADDE
2384
KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2388
if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2389
const APInt &RA = Rem->getAPIntValue().abs();
2390
if (RA.isPowerOf2()) {
2391
APInt LowBits = RA - 1;
2392
computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2394
// The low bits of the first operand are unchanged by the srem.
2395
KnownZero = KnownZero2 & LowBits;
2396
KnownOne = KnownOne2 & LowBits;
2398
// If the first operand is non-negative or has all low bits zero, then
2399
// the upper bits are all zero.
2400
if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2401
KnownZero |= ~LowBits;
2403
// If the first operand is negative and not all low bits are zero, then
2404
// the upper bits are all one.
2405
if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2406
KnownOne |= ~LowBits;
2407
assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2412
if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2413
const APInt &RA = Rem->getAPIntValue();
2414
if (RA.isPowerOf2()) {
2415
APInt LowBits = (RA - 1);
2416
computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2418
// The upper bits are all zero, the lower ones are unchanged.
2419
KnownZero = KnownZero2 | ~LowBits;
2420
KnownOne = KnownOne2 & LowBits;
2425
// Since the result is less than or equal to either operand, any leading
2426
// zero bits in either operand must also exist in the result.
2427
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2428
computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2430
uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2431
KnownZero2.countLeadingOnes());
2432
KnownOne.clearAllBits();
2433
KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2436
case ISD::EXTRACT_ELEMENT: {
2437
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2438
const unsigned Index =
2439
cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2440
const unsigned BitWidth = Op.getValueType().getSizeInBits();
2442
// Remove low part of known bits mask
2443
KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2444
KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2446
// Remove high part of known bit mask
2447
KnownZero = KnownZero.trunc(BitWidth);
2448
KnownOne = KnownOne.trunc(BitWidth);
2455
APInt Op0Zero, Op0One;
2456
APInt Op1Zero, Op1One;
2457
computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2458
computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2460
KnownZero = Op0Zero & Op1Zero;
2461
KnownOne = Op0One & Op1One;
2464
case ISD::FrameIndex:
2465
case ISD::TargetFrameIndex:
2466
if (unsigned Align = InferPtrAlignment(Op)) {
2467
// The low bits are known zero if the pointer is aligned.
2468
KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2474
if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2477
case ISD::INTRINSIC_WO_CHAIN:
2478
case ISD::INTRINSIC_W_CHAIN:
2479
case ISD::INTRINSIC_VOID:
2480
// Allow the target to implement this method for its nodes.
2481
TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2485
assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2488
/// ComputeNumSignBits - Return the number of times the sign bit of the
2489
/// register is replicated into the other bits. We know that at least 1 bit
2490
/// is always equal to the sign bit (itself), but other cases can give us
2491
/// information. For example, immediately after an "SRA X, 2", we know that
2492
/// the top 3 bits are all equal to each other, so we return 3.
2493
unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2494
EVT VT = Op.getValueType();
2495
assert(VT.isInteger() && "Invalid VT!");
2496
unsigned VTBits = VT.getScalarType().getSizeInBits();
2498
unsigned FirstAnswer = 1;
2501
return 1; // Limit search depth.
2503
switch (Op.getOpcode()) {
2505
case ISD::AssertSext:
2506
Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2507
return VTBits-Tmp+1;
2508
case ISD::AssertZext:
2509
Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2512
case ISD::Constant: {
2513
const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2514
return Val.getNumSignBits();
2517
case ISD::SIGN_EXTEND:
2519
VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2520
return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2522
case ISD::SIGN_EXTEND_INREG:
2523
// Max of the input and what this extends.
2525
cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2528
Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2529
return std::max(Tmp, Tmp2);
2532
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2533
// SRA X, C -> adds C sign bits.
2534
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2535
Tmp += C->getZExtValue();
2536
if (Tmp > VTBits) Tmp = VTBits;
2540
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2541
// shl destroys sign bits.
2542
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2543
if (C->getZExtValue() >= VTBits || // Bad shift.
2544
C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2545
return Tmp - C->getZExtValue();
2550
case ISD::XOR: // NOT is handled here.
2551
// Logical binary ops preserve the number of sign bits at the worst.
2552
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2554
Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2555
FirstAnswer = std::min(Tmp, Tmp2);
2556
// We computed what we know about the sign bits as our first
2557
// answer. Now proceed to the generic code that uses
2558
// computeKnownBits, and pick whichever answer is better.
2563
Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2564
if (Tmp == 1) return 1; // Early out.
2565
Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2566
return std::min(Tmp, Tmp2);
2571
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2573
return 1; // Early out.
2574
Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2575
return std::min(Tmp, Tmp2);
2582
if (Op.getResNo() != 1)
2584
// The boolean result conforms to getBooleanContents. Fall through.
2585
// If setcc returns 0/-1, all bits are sign bits.
2586
// We know that we have an integer-based boolean since these operations
2587
// are only available for integer.
2588
if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2589
TargetLowering::ZeroOrNegativeOneBooleanContent)
2593
// If setcc returns 0/-1, all bits are sign bits.
2594
if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2595
TargetLowering::ZeroOrNegativeOneBooleanContent)
2600
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2601
unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2603
// Handle rotate right by N like a rotate left by 32-N.
2604
if (Op.getOpcode() == ISD::ROTR)
2605
RotAmt = (VTBits-RotAmt) & (VTBits-1);
2607
// If we aren't rotating out all of the known-in sign bits, return the
2608
// number that are left. This handles rotl(sext(x), 1) for example.
2609
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2610
if (Tmp > RotAmt+1) return Tmp-RotAmt;
2614
// Add can have at most one carry bit. Thus we know that the output
2615
// is, at worst, one more bit than the inputs.
2616
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2617
if (Tmp == 1) return 1; // Early out.
2619
// Special case decrementing a value (ADD X, -1):
2620
if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2621
if (CRHS->isAllOnesValue()) {
2622
APInt KnownZero, KnownOne;
2623
computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2625
// If the input is known to be 0 or 1, the output is 0/-1, which is all
2627
if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2630
// If we are subtracting one from a positive number, there is no carry
2631
// out of the result.
2632
if (KnownZero.isNegative())
2636
Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2637
if (Tmp2 == 1) return 1;
2638
return std::min(Tmp, Tmp2)-1;
2641
Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2642
if (Tmp2 == 1) return 1;
2645
if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2646
if (CLHS->isNullValue()) {
2647
APInt KnownZero, KnownOne;
2648
computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2649
// If the input is known to be 0 or 1, the output is 0/-1, which is all
2651
if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2654
// If the input is known to be positive (the sign bit is known clear),
2655
// the output of the NEG has the same number of sign bits as the input.
2656
if (KnownZero.isNegative())
2659
// Otherwise, we treat this like a SUB.
2662
// Sub can have at most one carry bit. Thus we know that the output
2663
// is, at worst, one more bit than the inputs.
2664
Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2665
if (Tmp == 1) return 1; // Early out.
2666
return std::min(Tmp, Tmp2)-1;
2668
// FIXME: it's tricky to do anything useful for this, but it is an important
2669
// case for targets like X86.
2671
case ISD::EXTRACT_ELEMENT: {
2672
const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2673
const int BitWidth = Op.getValueType().getSizeInBits();
2675
Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2677
// Get reverse index (starting from 1), Op1 value indexes elements from
2678
// little end. Sign starts at big end.
2679
const int rIndex = Items - 1 -
2680
cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2682
// If the sign portion ends in our element the substraction gives correct
2683
// result. Otherwise it gives either negative or > bitwidth result
2684
return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2688
// If we are looking at the loaded value of the SDNode.
2689
if (Op.getResNo() == 0) {
2690
// Handle LOADX separately here. EXTLOAD case will fallthrough.
2691
if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2692
unsigned ExtType = LD->getExtensionType();
2695
case ISD::SEXTLOAD: // '17' bits known
2696
Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2697
return VTBits-Tmp+1;
2698
case ISD::ZEXTLOAD: // '16' bits known
2699
Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2705
// Allow the target to implement this method for its nodes.
2706
if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2707
Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2708
Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2709
Op.getOpcode() == ISD::INTRINSIC_VOID) {
2710
unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2711
if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2714
// Finally, if we can prove that the top bits of the result are 0's or 1's,
2715
// use this information.
2716
APInt KnownZero, KnownOne;
2717
computeKnownBits(Op, KnownZero, KnownOne, Depth);
2720
if (KnownZero.isNegative()) { // sign bit is 0
2722
} else if (KnownOne.isNegative()) { // sign bit is 1;
2729
// Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2730
// the number of identical bits in the top of the input value.
2732
Mask <<= Mask.getBitWidth()-VTBits;
2733
// Return # leading zeros. We use 'min' here in case Val was zero before
2734
// shifting. We don't want to return '64' as for an i32 "0".
2735
return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2738
/// isBaseWithConstantOffset - Return true if the specified operand is an
2739
/// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2740
/// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2741
/// semantics as an ADD. This handles the equivalence:
2742
/// X|Cst == X+Cst iff X&Cst = 0.
2743
bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2744
if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2745
!isa<ConstantSDNode>(Op.getOperand(1)))
2748
if (Op.getOpcode() == ISD::OR &&
2749
!MaskedValueIsZero(Op.getOperand(0),
2750
cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2757
bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2758
// If we're told that NaNs won't happen, assume they won't.
2759
if (getTarget().Options.NoNaNsFPMath)
2762
// If the value is a constant, we can obviously see if it is a NaN or not.
2763
if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2764
return !C->getValueAPF().isNaN();
2766
// TODO: Recognize more cases here.
2771
bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2772
// If the value is a constant, we can obviously see if it is a zero or not.
2773
if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2774
return !C->isZero();
2776
// TODO: Recognize more cases here.
2777
switch (Op.getOpcode()) {
2780
if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2781
return !C->isNullValue();
2788
bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2789
// Check the obvious case.
2790
if (A == B) return true;
2792
// For for negative and positive zero.
2793
if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2794
if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2795
if (CA->isZero() && CB->isZero()) return true;
2797
// Otherwise they may not be equal.
2801
/// getNode - Gets or creates the specified node.
2803
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2804
FoldingSetNodeID ID;
2805
AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2807
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2808
return SDValue(E, 0);
2810
SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2811
DL.getDebugLoc(), getVTList(VT));
2812
CSEMap.InsertNode(N, IP);
2815
return SDValue(N, 0);
2818
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2819
EVT VT, SDValue Operand) {
2820
// Constant fold unary operations with an integer constant operand. Even
2821
// opaque constant will be folded, because the folding of unary operations
2822
// doesn't create new constants with different values. Nevertheless, the
2823
// opaque flag is preserved during folding to prevent future folding with
2825
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2826
const APInt &Val = C->getAPIntValue();
2829
case ISD::SIGN_EXTEND:
2830
return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2831
C->isTargetOpcode(), C->isOpaque());
2832
case ISD::ANY_EXTEND:
2833
case ISD::ZERO_EXTEND:
2835
return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2836
C->isTargetOpcode(), C->isOpaque());
2837
case ISD::UINT_TO_FP:
2838
case ISD::SINT_TO_FP: {
2839
APFloat apf(EVTToAPFloatSemantics(VT),
2840
APInt::getNullValue(VT.getSizeInBits()));
2841
(void)apf.convertFromAPInt(Val,
2842
Opcode==ISD::SINT_TO_FP,
2843
APFloat::rmNearestTiesToEven);
2844
return getConstantFP(apf, DL, VT);
2847
if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2848
return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2849
if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2850
return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2851
else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2852
return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2855
return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2858
return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2861
case ISD::CTLZ_ZERO_UNDEF:
2862
return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2865
case ISD::CTTZ_ZERO_UNDEF:
2866
return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2871
// Constant fold unary operations with a floating point constant operand.
2872
if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2873
APFloat V = C->getValueAPF(); // make copy
2877
return getConstantFP(V, DL, VT);
2880
return getConstantFP(V, DL, VT);
2882
APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2883
if (fs == APFloat::opOK || fs == APFloat::opInexact)
2884
return getConstantFP(V, DL, VT);
2888
APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2889
if (fs == APFloat::opOK || fs == APFloat::opInexact)
2890
return getConstantFP(V, DL, VT);
2894
APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2895
if (fs == APFloat::opOK || fs == APFloat::opInexact)
2896
return getConstantFP(V, DL, VT);
2899
case ISD::FP_EXTEND: {
2901
// This can return overflow, underflow, or inexact; we don't care.
2902
// FIXME need to be more flexible about rounding mode.
2903
(void)V.convert(EVTToAPFloatSemantics(VT),
2904
APFloat::rmNearestTiesToEven, &ignored);
2905
return getConstantFP(V, DL, VT);
2907
case ISD::FP_TO_SINT:
2908
case ISD::FP_TO_UINT: {
2911
static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2912
// FIXME need to be more flexible about rounding mode.
2913
APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2914
Opcode==ISD::FP_TO_SINT,
2915
APFloat::rmTowardZero, &ignored);
2916
if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2918
APInt api(VT.getSizeInBits(), x);
2919
return getConstant(api, DL, VT);
2922
if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2923
return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2924
else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2925
return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2926
else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2927
return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2932
// Constant fold unary operations with a vector integer or float operand.
2933
if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2934
if (BV->isConstant()) {
2937
// FIXME: Entirely reasonable to perform folding of other unary
2938
// operations here as the need arises.
2945
case ISD::FP_EXTEND:
2946
case ISD::FP_TO_SINT:
2947
case ISD::FP_TO_UINT:
2949
case ISD::UINT_TO_FP:
2950
case ISD::SINT_TO_FP:
2953
case ISD::CTLZ_ZERO_UNDEF:
2955
case ISD::CTTZ_ZERO_UNDEF:
2957
EVT SVT = VT.getScalarType();
2958
EVT InVT = BV->getValueType(0);
2959
EVT InSVT = InVT.getScalarType();
2961
// Find legal integer scalar type for constant promotion and
2962
// ensure that its scalar size is at least as large as source.
2964
if (SVT.isInteger()) {
2965
LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2966
if (LegalSVT.bitsLT(SVT)) break;
2969
// Let the above scalar folding handle the folding of each element.
2970
SmallVector<SDValue, 8> Ops;
2971
for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2972
SDValue OpN = BV->getOperand(i);
2973
EVT OpVT = OpN.getValueType();
2975
// Build vector (integer) scalar operands may need implicit
2976
// truncation - do this before constant folding.
2977
if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2978
OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2980
OpN = getNode(Opcode, DL, SVT, OpN);
2982
// Legalize the (integer) scalar constant if necessary.
2983
if (LegalSVT != SVT)
2984
OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2986
if (OpN.getOpcode() != ISD::UNDEF &&
2987
OpN.getOpcode() != ISD::Constant &&
2988
OpN.getOpcode() != ISD::ConstantFP)
2992
if (Ops.size() == VT.getVectorNumElements())
2993
return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3000
unsigned OpOpcode = Operand.getNode()->getOpcode();
3002
case ISD::TokenFactor:
3003
case ISD::MERGE_VALUES:
3004
case ISD::CONCAT_VECTORS:
3005
return Operand; // Factor, merge or concat of one node? No need.
3006
case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3007
case ISD::FP_EXTEND:
3008
assert(VT.isFloatingPoint() &&
3009
Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3010
if (Operand.getValueType() == VT) return Operand; // noop conversion.
3011
assert((!VT.isVector() ||
3012
VT.getVectorNumElements() ==
3013
Operand.getValueType().getVectorNumElements()) &&
3014
"Vector element count mismatch!");
3015
if (Operand.getOpcode() == ISD::UNDEF)
3016
return getUNDEF(VT);
3018
case ISD::SIGN_EXTEND:
3019
assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3020
"Invalid SIGN_EXTEND!");
3021
if (Operand.getValueType() == VT) return Operand; // noop extension
3022
assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3023
"Invalid sext node, dst < src!");
3024
assert((!VT.isVector() ||
3025
VT.getVectorNumElements() ==
3026
Operand.getValueType().getVectorNumElements()) &&
3027
"Vector element count mismatch!");
3028
if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3029
return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3030
else if (OpOpcode == ISD::UNDEF)
3031
// sext(undef) = 0, because the top bits will all be the same.
3032
return getConstant(0, DL, VT);
3034
case ISD::ZERO_EXTEND:
3035
assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3036
"Invalid ZERO_EXTEND!");
3037
if (Operand.getValueType() == VT) return Operand; // noop extension
3038
assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3039
"Invalid zext node, dst < src!");
3040
assert((!VT.isVector() ||
3041
VT.getVectorNumElements() ==
3042
Operand.getValueType().getVectorNumElements()) &&
3043
"Vector element count mismatch!");
3044
if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3045
return getNode(ISD::ZERO_EXTEND, DL, VT,
3046
Operand.getNode()->getOperand(0));
3047
else if (OpOpcode == ISD::UNDEF)
3048
// zext(undef) = 0, because the top bits will be zero.
3049
return getConstant(0, DL, VT);
3051
case ISD::ANY_EXTEND:
3052
assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3053
"Invalid ANY_EXTEND!");
3054
if (Operand.getValueType() == VT) return Operand; // noop extension
3055
assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3056
"Invalid anyext node, dst < src!");
3057
assert((!VT.isVector() ||
3058
VT.getVectorNumElements() ==
3059
Operand.getValueType().getVectorNumElements()) &&
3060
"Vector element count mismatch!");
3062
if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3063
OpOpcode == ISD::ANY_EXTEND)
3064
// (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3065
return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3066
else if (OpOpcode == ISD::UNDEF)
3067
return getUNDEF(VT);
3069
// (ext (trunx x)) -> x
3070
if (OpOpcode == ISD::TRUNCATE) {
3071
SDValue OpOp = Operand.getNode()->getOperand(0);
3072
if (OpOp.getValueType() == VT)
3077
assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3078
"Invalid TRUNCATE!");
3079
if (Operand.getValueType() == VT) return Operand; // noop truncate
3080
assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3081
"Invalid truncate node, src < dst!");
3082
assert((!VT.isVector() ||
3083
VT.getVectorNumElements() ==
3084
Operand.getValueType().getVectorNumElements()) &&
3085
"Vector element count mismatch!");
3086
if (OpOpcode == ISD::TRUNCATE)
3087
return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3088
if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3089
OpOpcode == ISD::ANY_EXTEND) {
3090
// If the source is smaller than the dest, we still need an extend.
3091
if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3092
.bitsLT(VT.getScalarType()))
3093
return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3094
if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3095
return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3096
return Operand.getNode()->getOperand(0);
3098
if (OpOpcode == ISD::UNDEF)
3099
return getUNDEF(VT);
3102
assert(VT.isInteger() && VT == Operand.getValueType() &&
3104
assert((VT.getScalarSizeInBits() % 16 == 0) &&
3105
"BSWAP types must be a multiple of 16 bits!");
3106
if (OpOpcode == ISD::UNDEF)
3107
return getUNDEF(VT);
3110
// Basic sanity checking.
3111
assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3112
&& "Cannot BITCAST between types of different sizes!");
3113
if (VT == Operand.getValueType()) return Operand; // noop conversion.
3114
if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3115
return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3116
if (OpOpcode == ISD::UNDEF)
3117
return getUNDEF(VT);
3119
case ISD::SCALAR_TO_VECTOR:
3120
assert(VT.isVector() && !Operand.getValueType().isVector() &&
3121
(VT.getVectorElementType() == Operand.getValueType() ||
3122
(VT.getVectorElementType().isInteger() &&
3123
Operand.getValueType().isInteger() &&
3124
VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3125
"Illegal SCALAR_TO_VECTOR node!");
3126
if (OpOpcode == ISD::UNDEF)
3127
return getUNDEF(VT);
3128
// scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3129
if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3130
isa<ConstantSDNode>(Operand.getOperand(1)) &&
3131
Operand.getConstantOperandVal(1) == 0 &&
3132
Operand.getOperand(0).getValueType() == VT)
3133
return Operand.getOperand(0);
3136
// -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3137
if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3138
return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3139
Operand.getNode()->getOperand(0));
3140
if (OpOpcode == ISD::FNEG) // --X -> X
3141
return Operand.getNode()->getOperand(0);
3144
if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3145
return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3150
SDVTList VTs = getVTList(VT);
3151
if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3152
FoldingSetNodeID ID;
3153
SDValue Ops[1] = { Operand };
3154
AddNodeIDNode(ID, Opcode, VTs, Ops);
3156
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3157
return SDValue(E, 0);
3159
N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3160
DL.getDebugLoc(), VTs, Operand);
3161
CSEMap.InsertNode(N, IP);
3163
N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3164
DL.getDebugLoc(), VTs, Operand);
3168
return SDValue(N, 0);
3171
static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3174
case ISD::ADD: return std::make_pair(C1 + C2, true);
3175
case ISD::SUB: return std::make_pair(C1 - C2, true);
3176
case ISD::MUL: return std::make_pair(C1 * C2, true);
3177
case ISD::AND: return std::make_pair(C1 & C2, true);
3178
case ISD::OR: return std::make_pair(C1 | C2, true);
3179
case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3180
case ISD::SHL: return std::make_pair(C1 << C2, true);
3181
case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3182
case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3183
case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3184
case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3186
if (!C2.getBoolValue())
3188
return std::make_pair(C1.udiv(C2), true);
3190
if (!C2.getBoolValue())
3192
return std::make_pair(C1.urem(C2), true);
3194
if (!C2.getBoolValue())
3196
return std::make_pair(C1.sdiv(C2), true);
3198
if (!C2.getBoolValue())
3200
return std::make_pair(C1.srem(C2), true);
3202
return std::make_pair(APInt(1, 0), false);
3205
SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3206
const ConstantSDNode *Cst1,
3207
const ConstantSDNode *Cst2) {
3208
if (Cst1->isOpaque() || Cst2->isOpaque())
3211
std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3212
Cst2->getAPIntValue());
3215
return getConstant(Folded.first, DL, VT);
3218
SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3219
SDNode *Cst1, SDNode *Cst2) {
3220
// If the opcode is a target-specific ISD node, there's nothing we can
3221
// do here and the operand rules may not line up with the below, so
3223
if (Opcode >= ISD::BUILTIN_OP_END)
3226
// Handle the case of two scalars.
3227
if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3228
if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3229
if (SDValue Folded =
3230
FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3233
SmallVector<SDValue, 4> Outputs;
3234
// We may have a vector type but a scalar result. Create a splat.
3235
Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3236
// Build a big vector out of the scalar elements we generated.
3237
return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3244
// For vectors extract each constant element into Inputs so we can constant
3245
// fold them individually.
3246
BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3247
BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3251
assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3253
EVT SVT = VT.getScalarType();
3254
SmallVector<SDValue, 4> Outputs;
3255
for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3256
ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3257
ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3258
if (!V1 || !V2) // Not a constant, bail.
3261
if (V1->isOpaque() || V2->isOpaque())
3264
// Avoid BUILD_VECTOR nodes that perform implicit truncation.
3265
// FIXME: This is valid and could be handled by truncating the APInts.
3266
if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3269
// Fold one vector element.
3270
std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3271
V2->getAPIntValue());
3274
Outputs.push_back(getConstant(Folded.first, DL, SVT));
3277
assert(VT.getVectorNumElements() == Outputs.size() &&
3278
"Vector size mismatch!");
3280
// We may have a vector type but a scalar result. Create a splat.
3281
Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3283
// Build a big vector out of the scalar elements we generated.
3284
return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3287
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3288
SDValue N2, const SDNodeFlags *Flags) {
3289
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3290
ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3293
case ISD::TokenFactor:
3294
assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3295
N2.getValueType() == MVT::Other && "Invalid token factor!");
3296
// Fold trivial token factors.
3297
if (N1.getOpcode() == ISD::EntryToken) return N2;
3298
if (N2.getOpcode() == ISD::EntryToken) return N1;
3299
if (N1 == N2) return N1;
3301
case ISD::CONCAT_VECTORS:
3302
// Concat of UNDEFs is UNDEF.
3303
if (N1.getOpcode() == ISD::UNDEF &&
3304
N2.getOpcode() == ISD::UNDEF)
3305
return getUNDEF(VT);
3307
// A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3308
// one big BUILD_VECTOR.
3309
if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3310
N2.getOpcode() == ISD::BUILD_VECTOR) {
3311
SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3312
N1.getNode()->op_end());
3313
Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3315
// BUILD_VECTOR requires all inputs to be of the same type, find the
3316
// maximum type and extend them all.
3317
EVT SVT = VT.getScalarType();
3318
for (SDValue Op : Elts)
3319
SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3320
if (SVT.bitsGT(VT.getScalarType()))
3321
for (SDValue &Op : Elts)
3322
Op = TLI->isZExtFree(Op.getValueType(), SVT)
3323
? getZExtOrTrunc(Op, DL, SVT)
3324
: getSExtOrTrunc(Op, DL, SVT);
3326
return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3330
assert(VT.isInteger() && "This operator does not apply to FP types!");
3331
assert(N1.getValueType() == N2.getValueType() &&
3332
N1.getValueType() == VT && "Binary operator types must match!");
3333
// (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3334
// worth handling here.
3335
if (N2C && N2C->isNullValue())
3337
if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3344
assert(VT.isInteger() && "This operator does not apply to FP types!");
3345
assert(N1.getValueType() == N2.getValueType() &&
3346
N1.getValueType() == VT && "Binary operator types must match!");
3347
// (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3348
// it's worth handling here.
3349
if (N2C && N2C->isNullValue())
3359
assert(VT.isInteger() && "This operator does not apply to FP types!");
3360
assert(N1.getValueType() == N2.getValueType() &&
3361
N1.getValueType() == VT && "Binary operator types must match!");
3368
if (getTarget().Options.UnsafeFPMath) {
3369
if (Opcode == ISD::FADD) {
3371
if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3372
if (CFP->getValueAPF().isZero())
3375
if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3376
if (CFP->getValueAPF().isZero())
3378
} else if (Opcode == ISD::FSUB) {
3380
if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3381
if (CFP->getValueAPF().isZero())
3383
} else if (Opcode == ISD::FMUL) {
3384
ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3387
// If the first operand isn't the constant, try the second
3389
CFP = dyn_cast<ConstantFPSDNode>(N2);
3396
return SDValue(CFP,0);
3398
if (CFP->isExactlyValue(1.0))
3403
assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3404
assert(N1.getValueType() == N2.getValueType() &&
3405
N1.getValueType() == VT && "Binary operator types must match!");
3407
case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3408
assert(N1.getValueType() == VT &&
3409
N1.getValueType().isFloatingPoint() &&
3410
N2.getValueType().isFloatingPoint() &&
3411
"Invalid FCOPYSIGN!");
3418
assert(VT == N1.getValueType() &&
3419
"Shift operators return type must be the same as their first arg");
3420
assert(VT.isInteger() && N2.getValueType().isInteger() &&
3421
"Shifts only work on integers");
3422
assert((!VT.isVector() || VT == N2.getValueType()) &&
3423
"Vector shift amounts must be in the same as their first arg");
3424
// Verify that the shift amount VT is bit enough to hold valid shift
3425
// amounts. This catches things like trying to shift an i1024 value by an
3426
// i8, which is easy to fall into in generic code that uses
3427
// TLI.getShiftAmount().
3428
assert(N2.getValueType().getSizeInBits() >=
3429
Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3430
"Invalid use of small shift amount with oversized value!");
3432
// Always fold shifts of i1 values so the code generator doesn't need to
3433
// handle them. Since we know the size of the shift has to be less than the
3434
// size of the value, the shift/rotate count is guaranteed to be zero.
3437
if (N2C && N2C->isNullValue())
3440
case ISD::FP_ROUND_INREG: {
3441
EVT EVT = cast<VTSDNode>(N2)->getVT();
3442
assert(VT == N1.getValueType() && "Not an inreg round!");
3443
assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3444
"Cannot FP_ROUND_INREG integer types");
3445
assert(EVT.isVector() == VT.isVector() &&
3446
"FP_ROUND_INREG type should be vector iff the operand "
3448
assert((!EVT.isVector() ||
3449
EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3450
"Vector element counts must match in FP_ROUND_INREG");
3451
assert(EVT.bitsLE(VT) && "Not rounding down!");
3453
if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3457
assert(VT.isFloatingPoint() &&
3458
N1.getValueType().isFloatingPoint() &&
3459
VT.bitsLE(N1.getValueType()) &&
3460
isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3461
if (N1.getValueType() == VT) return N1; // noop conversion.
3463
case ISD::AssertSext:
3464
case ISD::AssertZext: {
3465
EVT EVT = cast<VTSDNode>(N2)->getVT();
3466
assert(VT == N1.getValueType() && "Not an inreg extend!");
3467
assert(VT.isInteger() && EVT.isInteger() &&
3468
"Cannot *_EXTEND_INREG FP types");
3469
assert(!EVT.isVector() &&
3470
"AssertSExt/AssertZExt type should be the vector element type "
3471
"rather than the vector type!");
3472
assert(EVT.bitsLE(VT) && "Not extending!");
3473
if (VT == EVT) return N1; // noop assertion.
3476
case ISD::SIGN_EXTEND_INREG: {
3477
EVT EVT = cast<VTSDNode>(N2)->getVT();
3478
assert(VT == N1.getValueType() && "Not an inreg extend!");
3479
assert(VT.isInteger() && EVT.isInteger() &&
3480
"Cannot *_EXTEND_INREG FP types");
3481
assert(EVT.isVector() == VT.isVector() &&
3482
"SIGN_EXTEND_INREG type should be vector iff the operand "
3484
assert((!EVT.isVector() ||
3485
EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3486
"Vector element counts must match in SIGN_EXTEND_INREG");
3487
assert(EVT.bitsLE(VT) && "Not extending!");
3488
if (EVT == VT) return N1; // Not actually extending
3490
auto SignExtendInReg = [&](APInt Val) {
3491
unsigned FromBits = EVT.getScalarType().getSizeInBits();
3492
Val <<= Val.getBitWidth() - FromBits;
3493
Val = Val.ashr(Val.getBitWidth() - FromBits);
3494
return getConstant(Val, DL, VT.getScalarType());
3498
APInt Val = N1C->getAPIntValue();
3499
return SignExtendInReg(Val);
3501
if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3502
SmallVector<SDValue, 8> Ops;
3503
for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3504
SDValue Op = N1.getOperand(i);
3505
if (Op.getValueType() != VT.getScalarType()) break;
3506
if (Op.getOpcode() == ISD::UNDEF) {
3510
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3511
APInt Val = C->getAPIntValue();
3512
Ops.push_back(SignExtendInReg(Val));
3517
if (Ops.size() == VT.getVectorNumElements())
3518
return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3522
case ISD::EXTRACT_VECTOR_ELT:
3523
// EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3524
if (N1.getOpcode() == ISD::UNDEF)
3525
return getUNDEF(VT);
3527
// EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3528
if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3529
return getUNDEF(VT);
3531
// EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3532
// expanding copies of large vectors from registers.
3534
N1.getOpcode() == ISD::CONCAT_VECTORS &&
3535
N1.getNumOperands() > 0) {
3537
N1.getOperand(0).getValueType().getVectorNumElements();
3538
return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3539
N1.getOperand(N2C->getZExtValue() / Factor),
3540
getConstant(N2C->getZExtValue() % Factor, DL,
3541
N2.getValueType()));
3544
// EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3545
// expanding large vector constants.
3546
if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3547
SDValue Elt = N1.getOperand(N2C->getZExtValue());
3549
if (VT != Elt.getValueType())
3550
// If the vector element type is not legal, the BUILD_VECTOR operands
3551
// are promoted and implicitly truncated, and the result implicitly
3552
// extended. Make that explicit here.
3553
Elt = getAnyExtOrTrunc(Elt, DL, VT);
3558
// EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3559
// operations are lowered to scalars.
3560
if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3561
// If the indices are the same, return the inserted element else
3562
// if the indices are known different, extract the element from
3563
// the original vector.
3564
SDValue N1Op2 = N1.getOperand(2);
3565
ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3567
if (N1Op2C && N2C) {
3568
if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3569
if (VT == N1.getOperand(1).getValueType())
3570
return N1.getOperand(1);
3572
return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3575
return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3579
case ISD::EXTRACT_ELEMENT:
3580
assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3581
assert(!N1.getValueType().isVector() && !VT.isVector() &&
3582
(N1.getValueType().isInteger() == VT.isInteger()) &&
3583
N1.getValueType() != VT &&
3584
"Wrong types for EXTRACT_ELEMENT!");
3586
// EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3587
// 64-bit integers into 32-bit parts. Instead of building the extract of
3588
// the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3589
if (N1.getOpcode() == ISD::BUILD_PAIR)
3590
return N1.getOperand(N2C->getZExtValue());
3592
// EXTRACT_ELEMENT of a constant int is also very common.
3593
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3594
unsigned ElementSize = VT.getSizeInBits();
3595
unsigned Shift = ElementSize * N2C->getZExtValue();
3596
APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3597
return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3600
case ISD::EXTRACT_SUBVECTOR: {
3602
if (VT.isSimple() && N1.getValueType().isSimple()) {
3603
assert(VT.isVector() && N1.getValueType().isVector() &&
3604
"Extract subvector VTs must be a vectors!");
3605
assert(VT.getVectorElementType() ==
3606
N1.getValueType().getVectorElementType() &&
3607
"Extract subvector VTs must have the same element type!");
3608
assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3609
"Extract subvector must be from larger vector to smaller vector!");
3611
if (isa<ConstantSDNode>(Index)) {
3612
assert((VT.getVectorNumElements() +
3613
cast<ConstantSDNode>(Index)->getZExtValue()
3614
<= N1.getValueType().getVectorNumElements())
3615
&& "Extract subvector overflow!");
3618
// Trivial extraction.
3619
if (VT.getSimpleVT() == N1.getSimpleValueType())
3626
// Perform trivial constant folding.
3628
FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3631
// Canonicalize constant to RHS if commutative.
3632
if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3633
std::swap(N1C, N2C);
3637
// Constant fold FP operations.
3638
bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3639
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3640
ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3642
if (!N2CFP && isCommutativeBinOp(Opcode)) {
3643
// Canonicalize constant to RHS if commutative.
3644
std::swap(N1CFP, N2CFP);
3647
APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3648
APFloat::opStatus s;
3651
s = V1.add(V2, APFloat::rmNearestTiesToEven);
3652
if (!HasFPExceptions || s != APFloat::opInvalidOp)
3653
return getConstantFP(V1, DL, VT);
3656
s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3657
if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3658
return getConstantFP(V1, DL, VT);
3661
s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3662
if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3663
return getConstantFP(V1, DL, VT);
3666
s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3667
if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3668
s!=APFloat::opDivByZero)) {
3669
return getConstantFP(V1, DL, VT);
3673
s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3674
if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3675
s!=APFloat::opDivByZero)) {
3676
return getConstantFP(V1, DL, VT);
3679
case ISD::FCOPYSIGN:
3681
return getConstantFP(V1, DL, VT);
3686
if (Opcode == ISD::FP_ROUND) {
3687
APFloat V = N1CFP->getValueAPF(); // make copy
3689
// This can return overflow, underflow, or inexact; we don't care.
3690
// FIXME need to be more flexible about rounding mode.
3691
(void)V.convert(EVTToAPFloatSemantics(VT),
3692
APFloat::rmNearestTiesToEven, &ignored);
3693
return getConstantFP(V, DL, VT);
3697
// Canonicalize an UNDEF to the RHS, even over a constant.
3698
if (N1.getOpcode() == ISD::UNDEF) {
3699
if (isCommutativeBinOp(Opcode)) {
3703
case ISD::FP_ROUND_INREG:
3704
case ISD::SIGN_EXTEND_INREG:
3710
return N1; // fold op(undef, arg2) -> undef
3718
return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3719
// For vectors, we can't easily build an all zero vector, just return
3726
// Fold a bunch of operators when the RHS is undef.
3727
if (N2.getOpcode() == ISD::UNDEF) {
3730
if (N1.getOpcode() == ISD::UNDEF)
3731
// Handle undef ^ undef -> 0 special case. This is a common
3733
return getConstant(0, DL, VT);
3743
return N2; // fold op(arg1, undef) -> undef
3749
if (getTarget().Options.UnsafeFPMath)
3757
return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3758
// For vectors, we can't easily build an all zero vector, just return
3763
return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3764
// For vectors, we can't easily build an all one vector, just return
3772
// Memoize this node if possible.
3774
SDVTList VTs = getVTList(VT);
3775
if (VT != MVT::Glue) {
3776
SDValue Ops[] = {N1, N2};
3777
FoldingSetNodeID ID;
3778
AddNodeIDNode(ID, Opcode, VTs, Ops);
3779
AddNodeIDFlags(ID, Opcode, Flags);
3781
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3782
return SDValue(E, 0);
3784
N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3786
CSEMap.InsertNode(N, IP);
3788
N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3792
return SDValue(N, 0);
3795
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3796
SDValue N1, SDValue N2, SDValue N3) {
3797
// Perform various simplifications.
3798
ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3801
ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3802
ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3803
ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3804
if (N1CFP && N2CFP && N3CFP) {
3805
APFloat V1 = N1CFP->getValueAPF();
3806
const APFloat &V2 = N2CFP->getValueAPF();
3807
const APFloat &V3 = N3CFP->getValueAPF();
3808
APFloat::opStatus s =
3809
V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3810
if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3811
return getConstantFP(V1, DL, VT);
3815
case ISD::CONCAT_VECTORS:
3816
// A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3817
// one big BUILD_VECTOR.
3818
if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3819
N2.getOpcode() == ISD::BUILD_VECTOR &&
3820
N3.getOpcode() == ISD::BUILD_VECTOR) {
3821
SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3822
N1.getNode()->op_end());
3823
Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3824
Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3825
return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3829
// Use FoldSetCC to simplify SETCC's.
3830
SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3831
if (Simp.getNode()) return Simp;
3836
if (N1C->getZExtValue())
3837
return N2; // select true, X, Y -> X
3838
return N3; // select false, X, Y -> Y
3841
if (N2 == N3) return N2; // select C, X, X -> X
3843
case ISD::VECTOR_SHUFFLE:
3844
llvm_unreachable("should use getVectorShuffle constructor!");
3845
case ISD::INSERT_SUBVECTOR: {
3847
if (VT.isSimple() && N1.getValueType().isSimple()
3848
&& N2.getValueType().isSimple()) {
3849
assert(VT.isVector() && N1.getValueType().isVector() &&
3850
N2.getValueType().isVector() &&
3851
"Insert subvector VTs must be a vectors");
3852
assert(VT == N1.getValueType() &&
3853
"Dest and insert subvector source types must match!");
3854
assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3855
"Insert subvector must be from smaller vector to larger vector!");
3856
if (isa<ConstantSDNode>(Index)) {
3857
assert((N2.getValueType().getVectorNumElements() +
3858
cast<ConstantSDNode>(Index)->getZExtValue()
3859
<= VT.getVectorNumElements())
3860
&& "Insert subvector overflow!");
3863
// Trivial insertion.
3864
if (VT.getSimpleVT() == N2.getSimpleValueType())
3870
// Fold bit_convert nodes from a type to themselves.
3871
if (N1.getValueType() == VT)
3876
// Memoize node if it doesn't produce a flag.
3878
SDVTList VTs = getVTList(VT);
3879
if (VT != MVT::Glue) {
3880
SDValue Ops[] = { N1, N2, N3 };
3881
FoldingSetNodeID ID;
3882
AddNodeIDNode(ID, Opcode, VTs, Ops);
3884
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3885
return SDValue(E, 0);
3887
N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3888
DL.getDebugLoc(), VTs, N1, N2, N3);
3889
CSEMap.InsertNode(N, IP);
3891
N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3892
DL.getDebugLoc(), VTs, N1, N2, N3);
3896
return SDValue(N, 0);
3899
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3900
SDValue N1, SDValue N2, SDValue N3,
3902
SDValue Ops[] = { N1, N2, N3, N4 };
3903
return getNode(Opcode, DL, VT, Ops);
3906
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3907
SDValue N1, SDValue N2, SDValue N3,
3908
SDValue N4, SDValue N5) {
3909
SDValue Ops[] = { N1, N2, N3, N4, N5 };
3910
return getNode(Opcode, DL, VT, Ops);
3913
/// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3914
/// the incoming stack arguments to be loaded from the stack.
3915
SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3916
SmallVector<SDValue, 8> ArgChains;
3918
// Include the original chain at the beginning of the list. When this is
3919
// used by target LowerCall hooks, this helps legalize find the
3920
// CALLSEQ_BEGIN node.
3921
ArgChains.push_back(Chain);
3923
// Add a chain value for each stack argument.
3924
for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3925
UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3926
if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3927
if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3928
if (FI->getIndex() < 0)
3929
ArgChains.push_back(SDValue(L, 1));
3931
// Build a tokenfactor for all the chains.
3932
return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3935
/// getMemsetValue - Vectorized representation of the memset value
3937
static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3939
assert(Value.getOpcode() != ISD::UNDEF);
3941
unsigned NumBits = VT.getScalarType().getSizeInBits();
3942
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3943
assert(C->getAPIntValue().getBitWidth() == 8);
3944
APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3946
return DAG.getConstant(Val, dl, VT);
3947
return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3951
assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3952
EVT IntVT = VT.getScalarType();
3953
if (!IntVT.isInteger())
3954
IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3956
Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3958
// Use a multiplication with 0x010101... to extend the input to the
3960
APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3961
Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3962
DAG.getConstant(Magic, dl, IntVT));
3965
if (VT != Value.getValueType() && !VT.isInteger())
3966
Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3967
if (VT != Value.getValueType()) {
3968
assert(VT.getVectorElementType() == Value.getValueType() &&
3969
"value type should be one vector element here");
3970
SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3971
Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3977
/// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3978
/// used when a memcpy is turned into a memset when the source is a constant
3980
static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3981
const TargetLowering &TLI, StringRef Str) {
3982
// Handle vector with all elements zero.
3985
return DAG.getConstant(0, dl, VT);
3986
else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3987
return DAG.getConstantFP(0.0, dl, VT);
3988
else if (VT.isVector()) {
3989
unsigned NumElts = VT.getVectorNumElements();
3990
MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3991
return DAG.getNode(ISD::BITCAST, dl, VT,
3992
DAG.getConstant(0, dl,
3993
EVT::getVectorVT(*DAG.getContext(),
3996
llvm_unreachable("Expected type!");
3999
assert(!VT.isVector() && "Can't handle vector type here!");
4000
unsigned NumVTBits = VT.getSizeInBits();
4001
unsigned NumVTBytes = NumVTBits / 8;
4002
unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4004
APInt Val(NumVTBits, 0);
4005
if (DAG.getDataLayout().isLittleEndian()) {
4006
for (unsigned i = 0; i != NumBytes; ++i)
4007
Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4009
for (unsigned i = 0; i != NumBytes; ++i)
4010
Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4013
// If the "cost" of materializing the integer immediate is less than the cost
4014
// of a load, then it is cost effective to turn the load into the immediate.
4015
Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4016
if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4017
return DAG.getConstant(Val, dl, VT);
4018
return SDValue(nullptr, 0);
4021
/// getMemBasePlusOffset - Returns base and offset node for the
4023
static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4024
SelectionDAG &DAG) {
4025
EVT VT = Base.getValueType();
4026
return DAG.getNode(ISD::ADD, dl,
4027
VT, Base, DAG.getConstant(Offset, dl, VT));
4030
/// isMemSrcFromString - Returns true if memcpy source is a string constant.
4032
static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4033
unsigned SrcDelta = 0;
4034
GlobalAddressSDNode *G = nullptr;
4035
if (Src.getOpcode() == ISD::GlobalAddress)
4036
G = cast<GlobalAddressSDNode>(Src);
4037
else if (Src.getOpcode() == ISD::ADD &&
4038
Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4039
Src.getOperand(1).getOpcode() == ISD::Constant) {
4040
G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4041
SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4046
return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4049
/// Determines the optimal series of memory ops to replace the memset / memcpy.
4050
/// Return true if the number of memory ops is below the threshold (Limit).
4051
/// It returns the types of the sequence of memory ops to perform
4052
/// memset / memcpy by reference.
4053
static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4054
unsigned Limit, uint64_t Size,
4055
unsigned DstAlign, unsigned SrcAlign,
4061
const TargetLowering &TLI) {
4062
assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4063
"Expecting memcpy / memset source to meet alignment requirement!");
4064
// If 'SrcAlign' is zero, that means the memory operation does not need to
4065
// load the value, i.e. memset or memcpy from constant string. Otherwise,
4066
// it's the inferred alignment of the source. 'DstAlign', on the other hand,
4067
// is the specified alignment of the memory operation. If it is zero, that
4068
// means it's possible to change the alignment of the destination.
4069
// 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4070
// not need to be loaded.
4071
EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4072
IsMemset, ZeroMemset, MemcpyStrSrc,
4073
DAG.getMachineFunction());
4075
if (VT == MVT::Other) {
4077
if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4078
TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4079
VT = TLI.getPointerTy(DAG.getDataLayout());
4081
switch (DstAlign & 7) {
4082
case 0: VT = MVT::i64; break;
4083
case 4: VT = MVT::i32; break;
4084
case 2: VT = MVT::i16; break;
4085
default: VT = MVT::i8; break;
4090
while (!TLI.isTypeLegal(LVT))
4091
LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4092
assert(LVT.isInteger());
4098
unsigned NumMemOps = 0;
4100
unsigned VTSize = VT.getSizeInBits() / 8;
4101
while (VTSize > Size) {
4102
// For now, only use non-vector load / store's for the left-over pieces.
4107
if (VT.isVector() || VT.isFloatingPoint()) {
4108
NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4109
if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4110
TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4112
else if (NewVT == MVT::i64 &&
4113
TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4114
TLI.isSafeMemOpType(MVT::f64)) {
4115
// i64 is usually not legal on 32-bit targets, but f64 may be.
4123
NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4124
if (NewVT == MVT::i8)
4126
} while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4128
NewVTSize = NewVT.getSizeInBits() / 8;
4130
// If the new VT cannot cover all of the remaining bits, then consider
4131
// issuing a (or a pair of) unaligned and overlapping load / store.
4132
// FIXME: Only does this for 64-bit or more since we don't have proper
4133
// cost model for unaligned load / store.
4136
if (NumMemOps && AllowOverlap &&
4137
VTSize >= 8 && NewVTSize < Size &&
4138
TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4146
if (++NumMemOps > Limit)
4149
MemOps.push_back(VT);
4156
static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4157
SDValue Chain, SDValue Dst,
4158
SDValue Src, uint64_t Size,
4159
unsigned Align, bool isVol,
4161
MachinePointerInfo DstPtrInfo,
4162
MachinePointerInfo SrcPtrInfo) {
4163
// Turn a memcpy of undef to nop.
4164
if (Src.getOpcode() == ISD::UNDEF)
4167
// Expand memcpy to a series of load and store ops if the size operand falls
4168
// below a certain threshold.
4169
// TODO: In the AlwaysInline case, if the size is big then generate a loop
4170
// rather than maybe a humongous number of loads and stores.
4171
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4172
std::vector<EVT> MemOps;
4173
bool DstAlignCanChange = false;
4174
MachineFunction &MF = DAG.getMachineFunction();
4175
MachineFrameInfo *MFI = MF.getFrameInfo();
4176
bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4177
FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4178
if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4179
DstAlignCanChange = true;
4180
unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4181
if (Align > SrcAlign)
4184
bool CopyFromStr = isMemSrcFromString(Src, Str);
4185
bool isZeroStr = CopyFromStr && Str.empty();
4186
unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4188
if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4189
(DstAlignCanChange ? 0 : Align),
4190
(isZeroStr ? 0 : SrcAlign),
4191
false, false, CopyFromStr, true, DAG, TLI))
4194
if (DstAlignCanChange) {
4195
Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4196
unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4198
// Don't promote to an alignment that would require dynamic stack
4200
const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4201
if (!TRI->needsStackRealignment(MF))
4202
while (NewAlign > Align &&
4203
DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4206
if (NewAlign > Align) {
4207
// Give the stack frame object a larger alignment if needed.
4208
if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4209
MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4214
SmallVector<SDValue, 8> OutChains;
4215
unsigned NumMemOps = MemOps.size();
4216
uint64_t SrcOff = 0, DstOff = 0;
4217
for (unsigned i = 0; i != NumMemOps; ++i) {
4219
unsigned VTSize = VT.getSizeInBits() / 8;
4220
SDValue Value, Store;
4222
if (VTSize > Size) {
4223
// Issuing an unaligned load / store pair that overlaps with the previous
4224
// pair. Adjust the offset accordingly.
4225
assert(i == NumMemOps-1 && i != 0);
4226
SrcOff -= VTSize - Size;
4227
DstOff -= VTSize - Size;
4231
(isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4232
// It's unlikely a store of a vector immediate can be done in a single
4233
// instruction. It would require a load from a constantpool first.
4234
// We only handle zero vectors here.
4235
// FIXME: Handle other cases where store of vector immediate is done in
4236
// a single instruction.
4237
Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4238
if (Value.getNode())
4239
Store = DAG.getStore(Chain, dl, Value,
4240
getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4241
DstPtrInfo.getWithOffset(DstOff), isVol,
4245
if (!Store.getNode()) {
4246
// The type might not be legal for the target. This should only happen
4247
// if the type is smaller than a legal type, as on PPC, so the right
4248
// thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4249
// to Load/Store if NVT==VT.
4250
// FIXME does the case above also need this?
4251
EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4252
assert(NVT.bitsGE(VT));
4253
Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4254
getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4255
SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4256
false, MinAlign(SrcAlign, SrcOff));
4257
Store = DAG.getTruncStore(Chain, dl, Value,
4258
getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4259
DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4262
OutChains.push_back(Store);
4268
return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4271
static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4272
SDValue Chain, SDValue Dst,
4273
SDValue Src, uint64_t Size,
4274
unsigned Align, bool isVol,
4276
MachinePointerInfo DstPtrInfo,
4277
MachinePointerInfo SrcPtrInfo) {
4278
// Turn a memmove of undef to nop.
4279
if (Src.getOpcode() == ISD::UNDEF)
4282
// Expand memmove to a series of load and store ops if the size operand falls
4283
// below a certain threshold.
4284
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4285
std::vector<EVT> MemOps;
4286
bool DstAlignCanChange = false;
4287
MachineFunction &MF = DAG.getMachineFunction();
4288
MachineFrameInfo *MFI = MF.getFrameInfo();
4289
bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4290
FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4291
if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4292
DstAlignCanChange = true;
4293
unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4294
if (Align > SrcAlign)
4296
unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4298
if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4299
(DstAlignCanChange ? 0 : Align), SrcAlign,
4300
false, false, false, false, DAG, TLI))
4303
if (DstAlignCanChange) {
4304
Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4305
unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4306
if (NewAlign > Align) {
4307
// Give the stack frame object a larger alignment if needed.
4308
if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4309
MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4314
uint64_t SrcOff = 0, DstOff = 0;
4315
SmallVector<SDValue, 8> LoadValues;
4316
SmallVector<SDValue, 8> LoadChains;
4317
SmallVector<SDValue, 8> OutChains;
4318
unsigned NumMemOps = MemOps.size();
4319
for (unsigned i = 0; i < NumMemOps; i++) {
4321
unsigned VTSize = VT.getSizeInBits() / 8;
4324
Value = DAG.getLoad(VT, dl, Chain,
4325
getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4326
SrcPtrInfo.getWithOffset(SrcOff), isVol,
4327
false, false, SrcAlign);
4328
LoadValues.push_back(Value);
4329
LoadChains.push_back(Value.getValue(1));
4332
Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4334
for (unsigned i = 0; i < NumMemOps; i++) {
4336
unsigned VTSize = VT.getSizeInBits() / 8;
4339
Store = DAG.getStore(Chain, dl, LoadValues[i],
4340
getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4341
DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4342
OutChains.push_back(Store);
4346
return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4349
/// \brief Lower the call to 'memset' intrinsic function into a series of store
4352
/// \param DAG Selection DAG where lowered code is placed.
4353
/// \param dl Link to corresponding IR location.
4354
/// \param Chain Control flow dependency.
4355
/// \param Dst Pointer to destination memory location.
4356
/// \param Src Value of byte to write into the memory.
4357
/// \param Size Number of bytes to write.
4358
/// \param Align Alignment of the destination in bytes.
4359
/// \param isVol True if destination is volatile.
4360
/// \param DstPtrInfo IR information on the memory pointer.
4361
/// \returns New head in the control flow, if lowering was successful, empty
4362
/// SDValue otherwise.
4364
/// The function tries to replace 'llvm.memset' intrinsic with several store
4365
/// operations and value calculation code. This is usually profitable for small
4367
static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4368
SDValue Chain, SDValue Dst,
4369
SDValue Src, uint64_t Size,
4370
unsigned Align, bool isVol,
4371
MachinePointerInfo DstPtrInfo) {
4372
// Turn a memset of undef to nop.
4373
if (Src.getOpcode() == ISD::UNDEF)
4376
// Expand memset to a series of load/store ops if the size operand
4377
// falls below a certain threshold.
4378
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4379
std::vector<EVT> MemOps;
4380
bool DstAlignCanChange = false;
4381
MachineFunction &MF = DAG.getMachineFunction();
4382
MachineFrameInfo *MFI = MF.getFrameInfo();
4383
bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4384
FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4385
if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4386
DstAlignCanChange = true;
4388
isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4389
if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4390
Size, (DstAlignCanChange ? 0 : Align), 0,
4391
true, IsZeroVal, false, true, DAG, TLI))
4394
if (DstAlignCanChange) {
4395
Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4396
unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4397
if (NewAlign > Align) {
4398
// Give the stack frame object a larger alignment if needed.
4399
if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4400
MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4405
SmallVector<SDValue, 8> OutChains;
4406
uint64_t DstOff = 0;
4407
unsigned NumMemOps = MemOps.size();
4409
// Find the largest store and generate the bit pattern for it.
4410
EVT LargestVT = MemOps[0];
4411
for (unsigned i = 1; i < NumMemOps; i++)
4412
if (MemOps[i].bitsGT(LargestVT))
4413
LargestVT = MemOps[i];
4414
SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4416
for (unsigned i = 0; i < NumMemOps; i++) {
4418
unsigned VTSize = VT.getSizeInBits() / 8;
4419
if (VTSize > Size) {
4420
// Issuing an unaligned load / store pair that overlaps with the previous
4421
// pair. Adjust the offset accordingly.
4422
assert(i == NumMemOps-1 && i != 0);
4423
DstOff -= VTSize - Size;
4426
// If this store is smaller than the largest store see whether we can get
4427
// the smaller value for free with a truncate.
4428
SDValue Value = MemSetValue;
4429
if (VT.bitsLT(LargestVT)) {
4430
if (!LargestVT.isVector() && !VT.isVector() &&
4431
TLI.isTruncateFree(LargestVT, VT))
4432
Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4434
Value = getMemsetValue(Src, VT, DAG, dl);
4436
assert(Value.getValueType() == VT && "Value with wrong type.");
4437
SDValue Store = DAG.getStore(Chain, dl, Value,
4438
getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4439
DstPtrInfo.getWithOffset(DstOff),
4440
isVol, false, Align);
4441
OutChains.push_back(Store);
4442
DstOff += VT.getSizeInBits() / 8;
4446
return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4449
SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4450
SDValue Src, SDValue Size,
4451
unsigned Align, bool isVol, bool AlwaysInline,
4452
bool isTailCall, MachinePointerInfo DstPtrInfo,
4453
MachinePointerInfo SrcPtrInfo) {
4454
assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4456
// Check to see if we should lower the memcpy to loads and stores first.
4457
// For cases within the target-specified limits, this is the best choice.
4458
ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4460
// Memcpy with size zero? Just return the original chain.
4461
if (ConstantSize->isNullValue())
4464
SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4465
ConstantSize->getZExtValue(),Align,
4466
isVol, false, DstPtrInfo, SrcPtrInfo);
4467
if (Result.getNode())
4471
// Then check to see if we should lower the memcpy with target-specific
4472
// code. If the target chooses to do this, this is the next best.
4474
SDValue Result = TSI->EmitTargetCodeForMemcpy(
4475
*this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4476
DstPtrInfo, SrcPtrInfo);
4477
if (Result.getNode())
4481
// If we really need inline code and the target declined to provide it,
4482
// use a (potentially long) sequence of loads and stores.
4484
assert(ConstantSize && "AlwaysInline requires a constant size!");
4485
return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4486
ConstantSize->getZExtValue(), Align, isVol,
4487
true, DstPtrInfo, SrcPtrInfo);
4490
// FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4491
// memcpy is not guaranteed to be safe. libc memcpys aren't required to
4492
// respect volatile, so they may do things like read or write memory
4493
// beyond the given memory regions. But fixing this isn't easy, and most
4494
// people don't care.
4496
// Emit a library call.
4497
TargetLowering::ArgListTy Args;
4498
TargetLowering::ArgListEntry Entry;
4499
Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4500
Entry.Node = Dst; Args.push_back(Entry);
4501
Entry.Node = Src; Args.push_back(Entry);
4502
Entry.Node = Size; Args.push_back(Entry);
4503
// FIXME: pass in SDLoc
4504
TargetLowering::CallLoweringInfo CLI(*this);
4507
.setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4508
Type::getVoidTy(*getContext()),
4509
getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4510
TLI->getPointerTy(getDataLayout())),
4513
.setTailCall(isTailCall);
4515
std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4516
return CallResult.second;
4519
SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4520
SDValue Src, SDValue Size,
4521
unsigned Align, bool isVol, bool isTailCall,
4522
MachinePointerInfo DstPtrInfo,
4523
MachinePointerInfo SrcPtrInfo) {
4524
assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4526
// Check to see if we should lower the memmove to loads and stores first.
4527
// For cases within the target-specified limits, this is the best choice.
4528
ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4530
// Memmove with size zero? Just return the original chain.
4531
if (ConstantSize->isNullValue())
4535
getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4536
ConstantSize->getZExtValue(), Align, isVol,
4537
false, DstPtrInfo, SrcPtrInfo);
4538
if (Result.getNode())
4542
// Then check to see if we should lower the memmove with target-specific
4543
// code. If the target chooses to do this, this is the next best.
4545
SDValue Result = TSI->EmitTargetCodeForMemmove(
4546
*this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4547
if (Result.getNode())
4551
// FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4552
// not be safe. See memcpy above for more details.
4554
// Emit a library call.
4555
TargetLowering::ArgListTy Args;
4556
TargetLowering::ArgListEntry Entry;
4557
Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4558
Entry.Node = Dst; Args.push_back(Entry);
4559
Entry.Node = Src; Args.push_back(Entry);
4560
Entry.Node = Size; Args.push_back(Entry);
4561
// FIXME: pass in SDLoc
4562
TargetLowering::CallLoweringInfo CLI(*this);
4565
.setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4566
Type::getVoidTy(*getContext()),
4567
getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4568
TLI->getPointerTy(getDataLayout())),
4571
.setTailCall(isTailCall);
4573
std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4574
return CallResult.second;
4577
SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4578
SDValue Src, SDValue Size,
4579
unsigned Align, bool isVol, bool isTailCall,
4580
MachinePointerInfo DstPtrInfo) {
4581
assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4583
// Check to see if we should lower the memset to stores first.
4584
// For cases within the target-specified limits, this is the best choice.
4585
ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4587
// Memset with size zero? Just return the original chain.
4588
if (ConstantSize->isNullValue())
4592
getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4593
Align, isVol, DstPtrInfo);
4595
if (Result.getNode())
4599
// Then check to see if we should lower the memset with target-specific
4600
// code. If the target chooses to do this, this is the next best.
4602
SDValue Result = TSI->EmitTargetCodeForMemset(
4603
*this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4604
if (Result.getNode())
4608
// Emit a library call.
4609
Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4610
TargetLowering::ArgListTy Args;
4611
TargetLowering::ArgListEntry Entry;
4612
Entry.Node = Dst; Entry.Ty = IntPtrTy;
4613
Args.push_back(Entry);
4615
Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4616
Args.push_back(Entry);
4618
Entry.Ty = IntPtrTy;
4619
Args.push_back(Entry);
4621
// FIXME: pass in SDLoc
4622
TargetLowering::CallLoweringInfo CLI(*this);
4625
.setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4626
Type::getVoidTy(*getContext()),
4627
getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4628
TLI->getPointerTy(getDataLayout())),
4631
.setTailCall(isTailCall);
4633
std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4634
return CallResult.second;
4637
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4638
SDVTList VTList, ArrayRef<SDValue> Ops,
4639
MachineMemOperand *MMO,
4640
AtomicOrdering SuccessOrdering,
4641
AtomicOrdering FailureOrdering,
4642
SynchronizationScope SynchScope) {
4643
FoldingSetNodeID ID;
4644
ID.AddInteger(MemVT.getRawBits());
4645
AddNodeIDNode(ID, Opcode, VTList, Ops);
4646
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4648
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4649
cast<AtomicSDNode>(E)->refineAlignment(MMO);
4650
return SDValue(E, 0);
4653
// Allocate the operands array for the node out of the BumpPtrAllocator, since
4654
// SDNode doesn't have access to it. This memory will be "leaked" when
4655
// the node is deallocated, but recovered when the allocator is released.
4656
// If the number of operands is less than 5 we use AtomicSDNode's internal
4658
unsigned NumOps = Ops.size();
4659
SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4662
SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4663
dl.getDebugLoc(), VTList, MemVT,
4664
Ops.data(), DynOps, NumOps, MMO,
4665
SuccessOrdering, FailureOrdering,
4667
CSEMap.InsertNode(N, IP);
4669
return SDValue(N, 0);
4672
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4673
SDVTList VTList, ArrayRef<SDValue> Ops,
4674
MachineMemOperand *MMO,
4675
AtomicOrdering Ordering,
4676
SynchronizationScope SynchScope) {
4677
return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4678
Ordering, SynchScope);
4681
SDValue SelectionDAG::getAtomicCmpSwap(
4682
unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4683
SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4684
unsigned Alignment, AtomicOrdering SuccessOrdering,
4685
AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4686
assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4687
Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4688
assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4690
if (Alignment == 0) // Ensure that codegen never sees alignment 0
4691
Alignment = getEVTAlignment(MemVT);
4693
MachineFunction &MF = getMachineFunction();
4695
// FIXME: Volatile isn't really correct; we should keep track of atomic
4696
// orderings in the memoperand.
4697
unsigned Flags = MachineMemOperand::MOVolatile;
4698
Flags |= MachineMemOperand::MOLoad;
4699
Flags |= MachineMemOperand::MOStore;
4701
MachineMemOperand *MMO =
4702
MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4704
return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4705
SuccessOrdering, FailureOrdering, SynchScope);
4708
SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4709
SDVTList VTs, SDValue Chain, SDValue Ptr,
4710
SDValue Cmp, SDValue Swp,
4711
MachineMemOperand *MMO,
4712
AtomicOrdering SuccessOrdering,
4713
AtomicOrdering FailureOrdering,
4714
SynchronizationScope SynchScope) {
4715
assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4716
Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4717
assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4719
SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4720
return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4721
SuccessOrdering, FailureOrdering, SynchScope);
4724
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4726
SDValue Ptr, SDValue Val,
4727
const Value* PtrVal,
4729
AtomicOrdering Ordering,
4730
SynchronizationScope SynchScope) {
4731
if (Alignment == 0) // Ensure that codegen never sees alignment 0
4732
Alignment = getEVTAlignment(MemVT);
4734
MachineFunction &MF = getMachineFunction();
4735
// An atomic store does not load. An atomic load does not store.
4736
// (An atomicrmw obviously both loads and stores.)
4737
// For now, atomics are considered to be volatile always, and they are
4739
// FIXME: Volatile isn't really correct; we should keep track of atomic
4740
// orderings in the memoperand.
4741
unsigned Flags = MachineMemOperand::MOVolatile;
4742
if (Opcode != ISD::ATOMIC_STORE)
4743
Flags |= MachineMemOperand::MOLoad;
4744
if (Opcode != ISD::ATOMIC_LOAD)
4745
Flags |= MachineMemOperand::MOStore;
4747
MachineMemOperand *MMO =
4748
MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4749
MemVT.getStoreSize(), Alignment);
4751
return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4752
Ordering, SynchScope);
4755
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4757
SDValue Ptr, SDValue Val,
4758
MachineMemOperand *MMO,
4759
AtomicOrdering Ordering,
4760
SynchronizationScope SynchScope) {
4761
assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4762
Opcode == ISD::ATOMIC_LOAD_SUB ||
4763
Opcode == ISD::ATOMIC_LOAD_AND ||
4764
Opcode == ISD::ATOMIC_LOAD_OR ||
4765
Opcode == ISD::ATOMIC_LOAD_XOR ||
4766
Opcode == ISD::ATOMIC_LOAD_NAND ||
4767
Opcode == ISD::ATOMIC_LOAD_MIN ||
4768
Opcode == ISD::ATOMIC_LOAD_MAX ||
4769
Opcode == ISD::ATOMIC_LOAD_UMIN ||
4770
Opcode == ISD::ATOMIC_LOAD_UMAX ||
4771
Opcode == ISD::ATOMIC_SWAP ||
4772
Opcode == ISD::ATOMIC_STORE) &&
4773
"Invalid Atomic Op");
4775
EVT VT = Val.getValueType();
4777
SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4778
getVTList(VT, MVT::Other);
4779
SDValue Ops[] = {Chain, Ptr, Val};
4780
return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4783
SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4784
EVT VT, SDValue Chain,
4786
MachineMemOperand *MMO,
4787
AtomicOrdering Ordering,
4788
SynchronizationScope SynchScope) {
4789
assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4791
SDVTList VTs = getVTList(VT, MVT::Other);
4792
SDValue Ops[] = {Chain, Ptr};
4793
return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4796
/// getMergeValues - Create a MERGE_VALUES node from the given operands.
4797
SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4798
if (Ops.size() == 1)
4801
SmallVector<EVT, 4> VTs;
4802
VTs.reserve(Ops.size());
4803
for (unsigned i = 0; i < Ops.size(); ++i)
4804
VTs.push_back(Ops[i].getValueType());
4805
return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4809
SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4810
ArrayRef<SDValue> Ops,
4811
EVT MemVT, MachinePointerInfo PtrInfo,
4812
unsigned Align, bool Vol,
4813
bool ReadMem, bool WriteMem, unsigned Size) {
4814
if (Align == 0) // Ensure that codegen never sees alignment 0
4815
Align = getEVTAlignment(MemVT);
4817
MachineFunction &MF = getMachineFunction();
4820
Flags |= MachineMemOperand::MOStore;
4822
Flags |= MachineMemOperand::MOLoad;
4824
Flags |= MachineMemOperand::MOVolatile;
4826
Size = MemVT.getStoreSize();
4827
MachineMemOperand *MMO =
4828
MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4830
return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4834
SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4835
ArrayRef<SDValue> Ops, EVT MemVT,
4836
MachineMemOperand *MMO) {
4837
assert((Opcode == ISD::INTRINSIC_VOID ||
4838
Opcode == ISD::INTRINSIC_W_CHAIN ||
4839
Opcode == ISD::PREFETCH ||
4840
Opcode == ISD::LIFETIME_START ||
4841
Opcode == ISD::LIFETIME_END ||
4842
(Opcode <= INT_MAX &&
4843
(int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4844
"Opcode is not a memory-accessing opcode!");
4846
// Memoize the node unless it returns a flag.
4847
MemIntrinsicSDNode *N;
4848
if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4849
FoldingSetNodeID ID;
4850
AddNodeIDNode(ID, Opcode, VTList, Ops);
4851
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4853
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4854
cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4855
return SDValue(E, 0);
4858
N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4859
dl.getDebugLoc(), VTList, Ops,
4861
CSEMap.InsertNode(N, IP);
4863
N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4864
dl.getDebugLoc(), VTList, Ops,
4868
return SDValue(N, 0);
4871
/// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4872
/// MachinePointerInfo record from it. This is particularly useful because the
4873
/// code generator has many cases where it doesn't bother passing in a
4874
/// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4875
static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4876
// If this is FI+Offset, we can model it.
4877
if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4878
return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4880
// If this is (FI+Offset1)+Offset2, we can model it.
4881
if (Ptr.getOpcode() != ISD::ADD ||
4882
!isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4883
!isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4884
return MachinePointerInfo();
4886
int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4887
return MachinePointerInfo::getFixedStack(FI, Offset+
4888
cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4891
/// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4892
/// MachinePointerInfo record from it. This is particularly useful because the
4893
/// code generator has many cases where it doesn't bother passing in a
4894
/// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4895
static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4896
// If the 'Offset' value isn't a constant, we can't handle this.
4897
if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4898
return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4899
if (OffsetOp.getOpcode() == ISD::UNDEF)
4900
return InferPointerInfo(Ptr);
4901
return MachinePointerInfo();
4906
SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4907
EVT VT, SDLoc dl, SDValue Chain,
4908
SDValue Ptr, SDValue Offset,
4909
MachinePointerInfo PtrInfo, EVT MemVT,
4910
bool isVolatile, bool isNonTemporal, bool isInvariant,
4911
unsigned Alignment, const AAMDNodes &AAInfo,
4912
const MDNode *Ranges) {
4913
assert(Chain.getValueType() == MVT::Other &&
4914
"Invalid chain type");
4915
if (Alignment == 0) // Ensure that codegen never sees alignment 0
4916
Alignment = getEVTAlignment(VT);
4918
unsigned Flags = MachineMemOperand::MOLoad;
4920
Flags |= MachineMemOperand::MOVolatile;
4922
Flags |= MachineMemOperand::MONonTemporal;
4924
Flags |= MachineMemOperand::MOInvariant;
4926
// If we don't have a PtrInfo, infer the trivial frame index case to simplify
4928
if (PtrInfo.V.isNull())
4929
PtrInfo = InferPointerInfo(Ptr, Offset);
4931
MachineFunction &MF = getMachineFunction();
4932
MachineMemOperand *MMO =
4933
MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4935
return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4939
SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4940
EVT VT, SDLoc dl, SDValue Chain,
4941
SDValue Ptr, SDValue Offset, EVT MemVT,
4942
MachineMemOperand *MMO) {
4944
ExtType = ISD::NON_EXTLOAD;
4945
} else if (ExtType == ISD::NON_EXTLOAD) {
4946
assert(VT == MemVT && "Non-extending load from different memory type!");
4949
assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4950
"Should only be an extending load, not truncating!");
4951
assert(VT.isInteger() == MemVT.isInteger() &&
4952
"Cannot convert from FP to Int or Int -> FP!");
4953
assert(VT.isVector() == MemVT.isVector() &&
4954
"Cannot use an ext load to convert to or from a vector!");
4955
assert((!VT.isVector() ||
4956
VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4957
"Cannot use an ext load to change the number of vector elements!");
4960
bool Indexed = AM != ISD::UNINDEXED;
4961
assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4962
"Unindexed load with an offset!");
4964
SDVTList VTs = Indexed ?
4965
getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4966
SDValue Ops[] = { Chain, Ptr, Offset };
4967
FoldingSetNodeID ID;
4968
AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4969
ID.AddInteger(MemVT.getRawBits());
4970
ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4971
MMO->isNonTemporal(),
4972
MMO->isInvariant()));
4973
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4975
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4976
cast<LoadSDNode>(E)->refineAlignment(MMO);
4977
return SDValue(E, 0);
4979
SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4980
dl.getDebugLoc(), VTs, AM, ExtType,
4982
CSEMap.InsertNode(N, IP);
4984
return SDValue(N, 0);
4987
SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4988
SDValue Chain, SDValue Ptr,
4989
MachinePointerInfo PtrInfo,
4990
bool isVolatile, bool isNonTemporal,
4991
bool isInvariant, unsigned Alignment,
4992
const AAMDNodes &AAInfo,
4993
const MDNode *Ranges) {
4994
SDValue Undef = getUNDEF(Ptr.getValueType());
4995
return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4996
PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5000
SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5001
SDValue Chain, SDValue Ptr,
5002
MachineMemOperand *MMO) {
5003
SDValue Undef = getUNDEF(Ptr.getValueType());
5004
return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5008
SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5009
SDValue Chain, SDValue Ptr,
5010
MachinePointerInfo PtrInfo, EVT MemVT,
5011
bool isVolatile, bool isNonTemporal,
5012
bool isInvariant, unsigned Alignment,
5013
const AAMDNodes &AAInfo) {
5014
SDValue Undef = getUNDEF(Ptr.getValueType());
5015
return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5016
PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5021
SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5022
SDValue Chain, SDValue Ptr, EVT MemVT,
5023
MachineMemOperand *MMO) {
5024
SDValue Undef = getUNDEF(Ptr.getValueType());
5025
return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5030
SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5031
SDValue Offset, ISD::MemIndexedMode AM) {
5032
LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5033
assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5034
"Load is already a indexed load!");
5035
return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5036
LD->getChain(), Base, Offset, LD->getPointerInfo(),
5037
LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5038
false, LD->getAlignment());
5041
SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5042
SDValue Ptr, MachinePointerInfo PtrInfo,
5043
bool isVolatile, bool isNonTemporal,
5044
unsigned Alignment, const AAMDNodes &AAInfo) {
5045
assert(Chain.getValueType() == MVT::Other &&
5046
"Invalid chain type");
5047
if (Alignment == 0) // Ensure that codegen never sees alignment 0
5048
Alignment = getEVTAlignment(Val.getValueType());
5050
unsigned Flags = MachineMemOperand::MOStore;
5052
Flags |= MachineMemOperand::MOVolatile;
5054
Flags |= MachineMemOperand::MONonTemporal;
5056
if (PtrInfo.V.isNull())
5057
PtrInfo = InferPointerInfo(Ptr);
5059
MachineFunction &MF = getMachineFunction();
5060
MachineMemOperand *MMO =
5061
MF.getMachineMemOperand(PtrInfo, Flags,
5062
Val.getValueType().getStoreSize(), Alignment,
5065
return getStore(Chain, dl, Val, Ptr, MMO);
5068
SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5069
SDValue Ptr, MachineMemOperand *MMO) {
5070
assert(Chain.getValueType() == MVT::Other &&
5071
"Invalid chain type");
5072
EVT VT = Val.getValueType();
5073
SDVTList VTs = getVTList(MVT::Other);
5074
SDValue Undef = getUNDEF(Ptr.getValueType());
5075
SDValue Ops[] = { Chain, Val, Ptr, Undef };
5076
FoldingSetNodeID ID;
5077
AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5078
ID.AddInteger(VT.getRawBits());
5079
ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5080
MMO->isNonTemporal(), MMO->isInvariant()));
5081
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5083
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5084
cast<StoreSDNode>(E)->refineAlignment(MMO);
5085
return SDValue(E, 0);
5087
SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5088
dl.getDebugLoc(), VTs,
5089
ISD::UNINDEXED, false, VT, MMO);
5090
CSEMap.InsertNode(N, IP);
5092
return SDValue(N, 0);
5095
SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5096
SDValue Ptr, MachinePointerInfo PtrInfo,
5097
EVT SVT,bool isVolatile, bool isNonTemporal,
5099
const AAMDNodes &AAInfo) {
5100
assert(Chain.getValueType() == MVT::Other &&
5101
"Invalid chain type");
5102
if (Alignment == 0) // Ensure that codegen never sees alignment 0
5103
Alignment = getEVTAlignment(SVT);
5105
unsigned Flags = MachineMemOperand::MOStore;
5107
Flags |= MachineMemOperand::MOVolatile;
5109
Flags |= MachineMemOperand::MONonTemporal;
5111
if (PtrInfo.V.isNull())
5112
PtrInfo = InferPointerInfo(Ptr);
5114
MachineFunction &MF = getMachineFunction();
5115
MachineMemOperand *MMO =
5116
MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5119
return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5122
SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5123
SDValue Ptr, EVT SVT,
5124
MachineMemOperand *MMO) {
5125
EVT VT = Val.getValueType();
5127
assert(Chain.getValueType() == MVT::Other &&
5128
"Invalid chain type");
5130
return getStore(Chain, dl, Val, Ptr, MMO);
5132
assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5133
"Should only be a truncating store, not extending!");
5134
assert(VT.isInteger() == SVT.isInteger() &&
5135
"Can't do FP-INT conversion!");
5136
assert(VT.isVector() == SVT.isVector() &&
5137
"Cannot use trunc store to convert to or from a vector!");
5138
assert((!VT.isVector() ||
5139
VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5140
"Cannot use trunc store to change the number of vector elements!");
5142
SDVTList VTs = getVTList(MVT::Other);
5143
SDValue Undef = getUNDEF(Ptr.getValueType());
5144
SDValue Ops[] = { Chain, Val, Ptr, Undef };
5145
FoldingSetNodeID ID;
5146
AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5147
ID.AddInteger(SVT.getRawBits());
5148
ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5149
MMO->isNonTemporal(), MMO->isInvariant()));
5150
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5152
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5153
cast<StoreSDNode>(E)->refineAlignment(MMO);
5154
return SDValue(E, 0);
5156
SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5157
dl.getDebugLoc(), VTs,
5158
ISD::UNINDEXED, true, SVT, MMO);
5159
CSEMap.InsertNode(N, IP);
5161
return SDValue(N, 0);
5165
SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5166
SDValue Offset, ISD::MemIndexedMode AM) {
5167
StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5168
assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5169
"Store is already a indexed store!");
5170
SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5171
SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5172
FoldingSetNodeID ID;
5173
AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5174
ID.AddInteger(ST->getMemoryVT().getRawBits());
5175
ID.AddInteger(ST->getRawSubclassData());
5176
ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5178
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5179
return SDValue(E, 0);
5181
SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5182
dl.getDebugLoc(), VTs, AM,
5183
ST->isTruncatingStore(),
5185
ST->getMemOperand());
5186
CSEMap.InsertNode(N, IP);
5188
return SDValue(N, 0);
5192
SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5193
SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5194
MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5196
SDVTList VTs = getVTList(VT, MVT::Other);
5197
SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5198
FoldingSetNodeID ID;
5199
AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5200
ID.AddInteger(VT.getRawBits());
5201
ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5203
MMO->isNonTemporal(),
5204
MMO->isInvariant()));
5205
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5207
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5208
cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5209
return SDValue(E, 0);
5211
SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5212
dl.getDebugLoc(), Ops, 4, VTs,
5214
CSEMap.InsertNode(N, IP);
5216
return SDValue(N, 0);
5219
SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5220
SDValue Ptr, SDValue Mask, EVT MemVT,
5221
MachineMemOperand *MMO, bool isTrunc) {
5222
assert(Chain.getValueType() == MVT::Other &&
5223
"Invalid chain type");
5224
EVT VT = Val.getValueType();
5225
SDVTList VTs = getVTList(MVT::Other);
5226
SDValue Ops[] = { Chain, Ptr, Mask, Val };
5227
FoldingSetNodeID ID;
5228
AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5229
ID.AddInteger(VT.getRawBits());
5230
ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5231
MMO->isNonTemporal(), MMO->isInvariant()));
5232
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5234
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5235
cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5236
return SDValue(E, 0);
5238
SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5239
dl.getDebugLoc(), Ops, 4,
5240
VTs, isTrunc, MemVT, MMO);
5241
CSEMap.InsertNode(N, IP);
5243
return SDValue(N, 0);
5247
SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5248
ArrayRef<SDValue> Ops,
5249
MachineMemOperand *MMO) {
5251
FoldingSetNodeID ID;
5252
AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5253
ID.AddInteger(VT.getRawBits());
5254
ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5256
MMO->isNonTemporal(),
5257
MMO->isInvariant()));
5258
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5260
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5261
cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5262
return SDValue(E, 0);
5264
MaskedGatherSDNode *N =
5265
new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5267
CSEMap.InsertNode(N, IP);
5269
return SDValue(N, 0);
5272
SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5273
ArrayRef<SDValue> Ops,
5274
MachineMemOperand *MMO) {
5275
FoldingSetNodeID ID;
5276
AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5277
ID.AddInteger(VT.getRawBits());
5278
ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5279
MMO->isNonTemporal(),
5280
MMO->isInvariant()));
5281
ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5283
if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5284
cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5285
return SDValue(E, 0);
5288
new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5290
CSEMap.InsertNode(N, IP);
5292
return SDValue(N, 0);
5295
SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5296
SDValue Chain, SDValue Ptr,
5299
SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5300
return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5303
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5304
ArrayRef<SDUse> Ops) {
5305
switch (Ops.size()) {
5306
case 0: return getNode(Opcode, DL, VT);
5307
case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5308
case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5309
case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5313
// Copy from an SDUse array into an SDValue array for use with
5314
// the regular getNode logic.
5315
SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5316
return getNode(Opcode, DL, VT, NewOps);
5319
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5320
ArrayRef<SDValue> Ops) {
5321
unsigned NumOps = Ops.size();
5323
case 0: return getNode(Opcode, DL, VT);
5324
case 1: return getNode(Opcode, DL, VT, Ops[0]);
5325
case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5326
case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5332
case ISD::SELECT_CC: {
5333
assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5334
assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5335
"LHS and RHS of condition must have same type!");
5336
assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5337
"True and False arms of SelectCC must have same type!");
5338
assert(Ops[2].getValueType() == VT &&
5339
"select_cc node must be of same type as true and false value!");
5343
assert(NumOps == 5 && "BR_CC takes 5 operands!");
5344
assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5345
"LHS/RHS of comparison should match types!");
5352
SDVTList VTs = getVTList(VT);
5354
if (VT != MVT::Glue) {
5355
FoldingSetNodeID ID;
5356
AddNodeIDNode(ID, Opcode, VTs, Ops);
5359
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5360
return SDValue(E, 0);
5362
N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5364
CSEMap.InsertNode(N, IP);
5366
N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5371
return SDValue(N, 0);
5374
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5375
ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5376
return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5379
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5380
ArrayRef<SDValue> Ops) {
5381
if (VTList.NumVTs == 1)
5382
return getNode(Opcode, DL, VTList.VTs[0], Ops);
5386
// FIXME: figure out how to safely handle things like
5387
// int foo(int x) { return 1 << (x & 255); }
5388
// int bar() { return foo(256); }
5389
case ISD::SRA_PARTS:
5390
case ISD::SRL_PARTS:
5391
case ISD::SHL_PARTS:
5392
if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5393
cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5394
return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5395
else if (N3.getOpcode() == ISD::AND)
5396
if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5397
// If the and is only masking out bits that cannot effect the shift,
5398
// eliminate the and.
5399
unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5400
if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5401
return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5407
// Memoize the node unless it returns a flag.
5409
unsigned NumOps = Ops.size();
5410
if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5411
FoldingSetNodeID ID;
5412
AddNodeIDNode(ID, Opcode, VTList, Ops);
5414
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5415
return SDValue(E, 0);
5418
N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5419
DL.getDebugLoc(), VTList, Ops[0]);
5420
} else if (NumOps == 2) {
5421
N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5422
DL.getDebugLoc(), VTList, Ops[0],
5424
} else if (NumOps == 3) {
5425
N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5426
DL.getDebugLoc(), VTList, Ops[0],
5429
N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5432
CSEMap.InsertNode(N, IP);
5435
N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5436
DL.getDebugLoc(), VTList, Ops[0]);
5437
} else if (NumOps == 2) {
5438
N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5439
DL.getDebugLoc(), VTList, Ops[0],
5441
} else if (NumOps == 3) {
5442
N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5443
DL.getDebugLoc(), VTList, Ops[0],
5446
N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5451
return SDValue(N, 0);
5454
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5455
return getNode(Opcode, DL, VTList, None);
5458
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5460
SDValue Ops[] = { N1 };
5461
return getNode(Opcode, DL, VTList, Ops);
5464
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5465
SDValue N1, SDValue N2) {
5466
SDValue Ops[] = { N1, N2 };
5467
return getNode(Opcode, DL, VTList, Ops);
5470
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5471
SDValue N1, SDValue N2, SDValue N3) {
5472
SDValue Ops[] = { N1, N2, N3 };
5473
return getNode(Opcode, DL, VTList, Ops);
5476
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5477
SDValue N1, SDValue N2, SDValue N3,
5479
SDValue Ops[] = { N1, N2, N3, N4 };
5480
return getNode(Opcode, DL, VTList, Ops);
5483
SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5484
SDValue N1, SDValue N2, SDValue N3,
5485
SDValue N4, SDValue N5) {
5486
SDValue Ops[] = { N1, N2, N3, N4, N5 };
5487
return getNode(Opcode, DL, VTList, Ops);
5490
SDVTList SelectionDAG::getVTList(EVT VT) {
5491
return makeVTList(SDNode::getValueTypeList(VT), 1);
5494
SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5495
FoldingSetNodeID ID;
5497
ID.AddInteger(VT1.getRawBits());
5498
ID.AddInteger(VT2.getRawBits());
5501
SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5503
EVT *Array = Allocator.Allocate<EVT>(2);
5506
Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5507
VTListMap.InsertNode(Result, IP);
5509
return Result->getSDVTList();
5512
SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5513
FoldingSetNodeID ID;
5515
ID.AddInteger(VT1.getRawBits());
5516
ID.AddInteger(VT2.getRawBits());
5517
ID.AddInteger(VT3.getRawBits());
5520
SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5522
EVT *Array = Allocator.Allocate<EVT>(3);
5526
Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5527
VTListMap.InsertNode(Result, IP);
5529
return Result->getSDVTList();
5532
SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5533
FoldingSetNodeID ID;
5535
ID.AddInteger(VT1.getRawBits());
5536
ID.AddInteger(VT2.getRawBits());
5537
ID.AddInteger(VT3.getRawBits());
5538
ID.AddInteger(VT4.getRawBits());
5541
SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5543
EVT *Array = Allocator.Allocate<EVT>(4);
5548
Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5549
VTListMap.InsertNode(Result, IP);
5551
return Result->getSDVTList();
5554
SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5555
unsigned NumVTs = VTs.size();
5556
FoldingSetNodeID ID;
5557
ID.AddInteger(NumVTs);
5558
for (unsigned index = 0; index < NumVTs; index++) {
5559
ID.AddInteger(VTs[index].getRawBits());
5563
SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5565
EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5566
std::copy(VTs.begin(), VTs.end(), Array);
5567
Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5568
VTListMap.InsertNode(Result, IP);
5570
return Result->getSDVTList();
5574
/// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5575
/// specified operands. If the resultant node already exists in the DAG,
5576
/// this does not modify the specified node, instead it returns the node that
5577
/// already exists. If the resultant node does not exist in the DAG, the
5578
/// input node is returned. As a degenerate case, if you specify the same
5579
/// input operands as the node already has, the input node is returned.
5580
SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5581
assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5583
// Check to see if there is no change.
5584
if (Op == N->getOperand(0)) return N;
5586
// See if the modified node already exists.
5587
void *InsertPos = nullptr;
5588
if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5591
// Nope it doesn't. Remove the node from its current place in the maps.
5593
if (!RemoveNodeFromCSEMaps(N))
5594
InsertPos = nullptr;
5596
// Now we update the operands.
5597
N->OperandList[0].set(Op);
5599
// If this gets put into a CSE map, add it.
5600
if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5604
SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5605
assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5607
// Check to see if there is no change.
5608
if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5609
return N; // No operands changed, just return the input node.
5611
// See if the modified node already exists.
5612
void *InsertPos = nullptr;
5613
if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5616
// Nope it doesn't. Remove the node from its current place in the maps.
5618
if (!RemoveNodeFromCSEMaps(N))
5619
InsertPos = nullptr;
5621
// Now we update the operands.
5622
if (N->OperandList[0] != Op1)
5623
N->OperandList[0].set(Op1);
5624
if (N->OperandList[1] != Op2)
5625
N->OperandList[1].set(Op2);
5627
// If this gets put into a CSE map, add it.
5628
if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5632
SDNode *SelectionDAG::
5633
UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5634
SDValue Ops[] = { Op1, Op2, Op3 };
5635
return UpdateNodeOperands(N, Ops);
5638
SDNode *SelectionDAG::
5639
UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5640
SDValue Op3, SDValue Op4) {
5641
SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5642
return UpdateNodeOperands(N, Ops);
5645
SDNode *SelectionDAG::
5646
UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5647
SDValue Op3, SDValue Op4, SDValue Op5) {
5648
SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5649
return UpdateNodeOperands(N, Ops);
5652
SDNode *SelectionDAG::
5653
UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5654
unsigned NumOps = Ops.size();
5655
assert(N->getNumOperands() == NumOps &&
5656
"Update with wrong number of operands");
5658
// If no operands changed just return the input node.
5659
if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5662
// See if the modified node already exists.
5663
void *InsertPos = nullptr;
5664
if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5667
// Nope it doesn't. Remove the node from its current place in the maps.
5669
if (!RemoveNodeFromCSEMaps(N))
5670
InsertPos = nullptr;
5672
// Now we update the operands.
5673
for (unsigned i = 0; i != NumOps; ++i)
5674
if (N->OperandList[i] != Ops[i])
5675
N->OperandList[i].set(Ops[i]);
5677
// If this gets put into a CSE map, add it.
5678
if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5682
/// DropOperands - Release the operands and set this node to have
5684
void SDNode::DropOperands() {
5685
// Unlike the code in MorphNodeTo that does this, we don't need to
5686
// watch for dead nodes here.
5687
for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5693
/// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5696
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698
SDVTList VTs = getVTList(VT);
5699
return SelectNodeTo(N, MachineOpc, VTs, None);
5702
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5703
EVT VT, SDValue Op1) {
5704
SDVTList VTs = getVTList(VT);
5705
SDValue Ops[] = { Op1 };
5706
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5709
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5710
EVT VT, SDValue Op1,
5712
SDVTList VTs = getVTList(VT);
5713
SDValue Ops[] = { Op1, Op2 };
5714
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5717
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5718
EVT VT, SDValue Op1,
5719
SDValue Op2, SDValue Op3) {
5720
SDVTList VTs = getVTList(VT);
5721
SDValue Ops[] = { Op1, Op2, Op3 };
5722
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5725
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5726
EVT VT, ArrayRef<SDValue> Ops) {
5727
SDVTList VTs = getVTList(VT);
5728
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5731
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5732
EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5733
SDVTList VTs = getVTList(VT1, VT2);
5734
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5737
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5739
SDVTList VTs = getVTList(VT1, VT2);
5740
return SelectNodeTo(N, MachineOpc, VTs, None);
5743
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5744
EVT VT1, EVT VT2, EVT VT3,
5745
ArrayRef<SDValue> Ops) {
5746
SDVTList VTs = getVTList(VT1, VT2, VT3);
5747
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5750
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5751
EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5752
ArrayRef<SDValue> Ops) {
5753
SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5754
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5757
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5760
SDVTList VTs = getVTList(VT1, VT2);
5761
SDValue Ops[] = { Op1 };
5762
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5765
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5767
SDValue Op1, SDValue Op2) {
5768
SDVTList VTs = getVTList(VT1, VT2);
5769
SDValue Ops[] = { Op1, Op2 };
5770
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5773
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5775
SDValue Op1, SDValue Op2,
5777
SDVTList VTs = getVTList(VT1, VT2);
5778
SDValue Ops[] = { Op1, Op2, Op3 };
5779
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5782
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5783
EVT VT1, EVT VT2, EVT VT3,
5784
SDValue Op1, SDValue Op2,
5786
SDVTList VTs = getVTList(VT1, VT2, VT3);
5787
SDValue Ops[] = { Op1, Op2, Op3 };
5788
return SelectNodeTo(N, MachineOpc, VTs, Ops);
5791
SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5792
SDVTList VTs,ArrayRef<SDValue> Ops) {
5793
N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5794
// Reset the NodeID to -1.
5799
/// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5800
/// the line number information on the merged node since it is not possible to
5801
/// preserve the information that operation is associated with multiple lines.
5802
/// This will make the debugger working better at -O0, were there is a higher
5803
/// probability having other instructions associated with that line.
5805
/// For IROrder, we keep the smaller of the two
5806
SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5807
DebugLoc NLoc = N->getDebugLoc();
5808
if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5809
N->setDebugLoc(DebugLoc());
5811
unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5812
N->setIROrder(Order);
5816
/// MorphNodeTo - This *mutates* the specified node to have the specified
5817
/// return type, opcode, and operands.
5819
/// Note that MorphNodeTo returns the resultant node. If there is already a
5820
/// node of the specified opcode and operands, it returns that node instead of
5821
/// the current one. Note that the SDLoc need not be the same.
5823
/// Using MorphNodeTo is faster than creating a new node and swapping it in
5824
/// with ReplaceAllUsesWith both because it often avoids allocating a new
5825
/// node, and because it doesn't require CSE recalculation for any of
5826
/// the node's users.
5828
/// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5829
/// As a consequence it isn't appropriate to use from within the DAG combiner or
5830
/// the legalizer which maintain worklists that would need to be updated when
5831
/// deleting things.
5832
SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5833
SDVTList VTs, ArrayRef<SDValue> Ops) {
5834
unsigned NumOps = Ops.size();
5835
// If an identical node already exists, use it.
5837
if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5838
FoldingSetNodeID ID;
5839
AddNodeIDNode(ID, Opc, VTs, Ops);
5840
if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5841
return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5844
if (!RemoveNodeFromCSEMaps(N))
5847
// Start the morphing.
5849
N->ValueList = VTs.VTs;
5850
N->NumValues = VTs.NumVTs;
5852
// Clear the operands list, updating used nodes to remove this from their
5853
// use list. Keep track of any operands that become dead as a result.
5854
SmallPtrSet<SDNode*, 16> DeadNodeSet;
5855
for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5857
SDNode *Used = Use.getNode();
5859
if (Used->use_empty())
5860
DeadNodeSet.insert(Used);
5863
if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5864
// Initialize the memory references information.
5865
MN->setMemRefs(nullptr, nullptr);
5866
// If NumOps is larger than the # of operands we can have in a
5867
// MachineSDNode, reallocate the operand list.
5868
if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5869
if (MN->OperandsNeedDelete)
5870
delete[] MN->OperandList;
5871
if (NumOps > array_lengthof(MN->LocalOperands))
5872
// We're creating a final node that will live unmorphed for the
5873
// remainder of the current SelectionDAG iteration, so we can allocate
5874
// the operands directly out of a pool with no recycling metadata.
5875
MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5876
Ops.data(), NumOps);
5878
MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5879
MN->OperandsNeedDelete = false;
5881
MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5883
// If NumOps is larger than the # of operands we currently have, reallocate
5884
// the operand list.
5885
if (NumOps > N->NumOperands) {
5886
if (N->OperandsNeedDelete)
5887
delete[] N->OperandList;
5888
N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5889
N->OperandsNeedDelete = true;
5891
N->InitOperands(N->OperandList, Ops.data(), NumOps);
5894
// Delete any nodes that are still dead after adding the uses for the
5896
if (!DeadNodeSet.empty()) {
5897
SmallVector<SDNode *, 16> DeadNodes;
5898
for (SDNode *N : DeadNodeSet)
5900
DeadNodes.push_back(N);
5901
RemoveDeadNodes(DeadNodes);
5905
CSEMap.InsertNode(N, IP); // Memoize the new node.
5910
/// getMachineNode - These are used for target selectors to create a new node
5911
/// with specified return type(s), MachineInstr opcode, and operands.
5913
/// Note that getMachineNode returns the resultant node. If there is already a
5914
/// node of the specified opcode and operands, it returns that node instead of
5915
/// the current one.
5917
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5918
SDVTList VTs = getVTList(VT);
5919
return getMachineNode(Opcode, dl, VTs, None);
5923
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5924
SDVTList VTs = getVTList(VT);
5925
SDValue Ops[] = { Op1 };
5926
return getMachineNode(Opcode, dl, VTs, Ops);
5930
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5931
SDValue Op1, SDValue Op2) {
5932
SDVTList VTs = getVTList(VT);
5933
SDValue Ops[] = { Op1, Op2 };
5934
return getMachineNode(Opcode, dl, VTs, Ops);
5938
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5939
SDValue Op1, SDValue Op2, SDValue Op3) {
5940
SDVTList VTs = getVTList(VT);
5941
SDValue Ops[] = { Op1, Op2, Op3 };
5942
return getMachineNode(Opcode, dl, VTs, Ops);
5946
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5947
ArrayRef<SDValue> Ops) {
5948
SDVTList VTs = getVTList(VT);
5949
return getMachineNode(Opcode, dl, VTs, Ops);
5953
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5954
SDVTList VTs = getVTList(VT1, VT2);
5955
return getMachineNode(Opcode, dl, VTs, None);
5959
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5960
EVT VT1, EVT VT2, SDValue Op1) {
5961
SDVTList VTs = getVTList(VT1, VT2);
5962
SDValue Ops[] = { Op1 };
5963
return getMachineNode(Opcode, dl, VTs, Ops);
5967
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5968
EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5969
SDVTList VTs = getVTList(VT1, VT2);
5970
SDValue Ops[] = { Op1, Op2 };
5971
return getMachineNode(Opcode, dl, VTs, Ops);
5975
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5976
EVT VT1, EVT VT2, SDValue Op1,
5977
SDValue Op2, SDValue Op3) {
5978
SDVTList VTs = getVTList(VT1, VT2);
5979
SDValue Ops[] = { Op1, Op2, Op3 };
5980
return getMachineNode(Opcode, dl, VTs, Ops);
5984
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5986
ArrayRef<SDValue> Ops) {
5987
SDVTList VTs = getVTList(VT1, VT2);
5988
return getMachineNode(Opcode, dl, VTs, Ops);
5992
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5993
EVT VT1, EVT VT2, EVT VT3,
5994
SDValue Op1, SDValue Op2) {
5995
SDVTList VTs = getVTList(VT1, VT2, VT3);
5996
SDValue Ops[] = { Op1, Op2 };
5997
return getMachineNode(Opcode, dl, VTs, Ops);
6001
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6002
EVT VT1, EVT VT2, EVT VT3,
6003
SDValue Op1, SDValue Op2, SDValue Op3) {
6004
SDVTList VTs = getVTList(VT1, VT2, VT3);
6005
SDValue Ops[] = { Op1, Op2, Op3 };
6006
return getMachineNode(Opcode, dl, VTs, Ops);
6010
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6011
EVT VT1, EVT VT2, EVT VT3,
6012
ArrayRef<SDValue> Ops) {
6013
SDVTList VTs = getVTList(VT1, VT2, VT3);
6014
return getMachineNode(Opcode, dl, VTs, Ops);
6018
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6019
EVT VT2, EVT VT3, EVT VT4,
6020
ArrayRef<SDValue> Ops) {
6021
SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6022
return getMachineNode(Opcode, dl, VTs, Ops);
6026
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6027
ArrayRef<EVT> ResultTys,
6028
ArrayRef<SDValue> Ops) {
6029
SDVTList VTs = getVTList(ResultTys);
6030
return getMachineNode(Opcode, dl, VTs, Ops);
6034
SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6035
ArrayRef<SDValue> OpsArray) {
6036
bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6039
const SDValue *Ops = OpsArray.data();
6040
unsigned NumOps = OpsArray.size();
6043
FoldingSetNodeID ID;
6044
AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6046
if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6047
return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6051
// Allocate a new MachineSDNode.
6052
N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6053
DL.getDebugLoc(), VTs);
6055
// Initialize the operands list.
6056
if (NumOps > array_lengthof(N->LocalOperands))
6057
// We're creating a final node that will live unmorphed for the
6058
// remainder of the current SelectionDAG iteration, so we can allocate
6059
// the operands directly out of a pool with no recycling metadata.
6060
N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6063
N->InitOperands(N->LocalOperands, Ops, NumOps);
6064
N->OperandsNeedDelete = false;
6067
CSEMap.InsertNode(N, IP);
6073
/// getTargetExtractSubreg - A convenience function for creating
6074
/// TargetOpcode::EXTRACT_SUBREG nodes.
6076
SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6078
SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6079
SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6080
VT, Operand, SRIdxVal);
6081
return SDValue(Subreg, 0);
6084
/// getTargetInsertSubreg - A convenience function for creating
6085
/// TargetOpcode::INSERT_SUBREG nodes.
6087
SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6088
SDValue Operand, SDValue Subreg) {
6089
SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6090
SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6091
VT, Operand, Subreg, SRIdxVal);
6092
return SDValue(Result, 0);
6095
/// getNodeIfExists - Get the specified node if it's already available, or
6096
/// else return NULL.
6097
SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6098
ArrayRef<SDValue> Ops,
6099
const SDNodeFlags *Flags) {
6100
if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6101
FoldingSetNodeID ID;
6102
AddNodeIDNode(ID, Opcode, VTList, Ops);
6103
AddNodeIDFlags(ID, Opcode, Flags);
6105
if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6111
/// getDbgValue - Creates a SDDbgValue node.
6114
SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6115
unsigned R, bool IsIndirect, uint64_t Off,
6116
DebugLoc DL, unsigned O) {
6117
assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6118
"Expected inlined-at fields to agree");
6119
return new (DbgInfo->getAlloc())
6120
SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6124
SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6125
const Value *C, uint64_t Off,
6126
DebugLoc DL, unsigned O) {
6127
assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6128
"Expected inlined-at fields to agree");
6129
return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6133
SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6134
unsigned FI, uint64_t Off,
6135
DebugLoc DL, unsigned O) {
6136
assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6137
"Expected inlined-at fields to agree");
6138
return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6143
/// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6144
/// pointed to by a use iterator is deleted, increment the use iterator
6145
/// so that it doesn't dangle.
6147
class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6148
SDNode::use_iterator &UI;
6149
SDNode::use_iterator &UE;
6151
void NodeDeleted(SDNode *N, SDNode *E) override {
6152
// Increment the iterator as needed.
6153
while (UI != UE && N == *UI)
6158
RAUWUpdateListener(SelectionDAG &d,
6159
SDNode::use_iterator &ui,
6160
SDNode::use_iterator &ue)
6161
: SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6166
/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6167
/// This can cause recursive merging of nodes in the DAG.
6169
/// This version assumes From has a single result value.
6171
void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6172
SDNode *From = FromN.getNode();
6173
assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6174
"Cannot replace with this method!");
6175
assert(From != To.getNode() && "Cannot replace uses of with self");
6177
// Iterate over all the existing uses of From. New uses will be added
6178
// to the beginning of the use list, which we avoid visiting.
6179
// This specifically avoids visiting uses of From that arise while the
6180
// replacement is happening, because any such uses would be the result
6181
// of CSE: If an existing node looks like From after one of its operands
6182
// is replaced by To, we don't want to replace of all its users with To
6183
// too. See PR3018 for more info.
6184
SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6185
RAUWUpdateListener Listener(*this, UI, UE);
6189
// This node is about to morph, remove its old self from the CSE maps.
6190
RemoveNodeFromCSEMaps(User);
6192
// A user can appear in a use list multiple times, and when this
6193
// happens the uses are usually next to each other in the list.
6194
// To help reduce the number of CSE recomputations, process all
6195
// the uses of this user that we can find this way.
6197
SDUse &Use = UI.getUse();
6200
} while (UI != UE && *UI == User);
6202
// Now that we have modified User, add it back to the CSE maps. If it
6203
// already exists there, recursively merge the results together.
6204
AddModifiedNodeToCSEMaps(User);
6207
// If we just RAUW'd the root, take note.
6208
if (FromN == getRoot())
6212
/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6213
/// This can cause recursive merging of nodes in the DAG.
6215
/// This version assumes that for each value of From, there is a
6216
/// corresponding value in To in the same position with the same type.
6218
void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6220
for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6221
assert((!From->hasAnyUseOfValue(i) ||
6222
From->getValueType(i) == To->getValueType(i)) &&
6223
"Cannot use this version of ReplaceAllUsesWith!");
6226
// Handle the trivial case.
6230
// Iterate over just the existing users of From. See the comments in
6231
// the ReplaceAllUsesWith above.
6232
SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6233
RAUWUpdateListener Listener(*this, UI, UE);
6237
// This node is about to morph, remove its old self from the CSE maps.
6238
RemoveNodeFromCSEMaps(User);
6240
// A user can appear in a use list multiple times, and when this
6241
// happens the uses are usually next to each other in the list.
6242
// To help reduce the number of CSE recomputations, process all
6243
// the uses of this user that we can find this way.
6245
SDUse &Use = UI.getUse();
6248
} while (UI != UE && *UI == User);
6250
// Now that we have modified User, add it back to the CSE maps. If it
6251
// already exists there, recursively merge the results together.
6252
AddModifiedNodeToCSEMaps(User);
6255
// If we just RAUW'd the root, take note.
6256
if (From == getRoot().getNode())
6257
setRoot(SDValue(To, getRoot().getResNo()));
6260
/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6261
/// This can cause recursive merging of nodes in the DAG.
6263
/// This version can replace From with any result values. To must match the
6264
/// number and types of values returned by From.
6265
void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6266
if (From->getNumValues() == 1) // Handle the simple case efficiently.
6267
return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6269
// Iterate over just the existing users of From. See the comments in
6270
// the ReplaceAllUsesWith above.
6271
SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6272
RAUWUpdateListener Listener(*this, UI, UE);
6276
// This node is about to morph, remove its old self from the CSE maps.
6277
RemoveNodeFromCSEMaps(User);
6279
// A user can appear in a use list multiple times, and when this
6280
// happens the uses are usually next to each other in the list.
6281
// To help reduce the number of CSE recomputations, process all
6282
// the uses of this user that we can find this way.
6284
SDUse &Use = UI.getUse();
6285
const SDValue &ToOp = To[Use.getResNo()];
6288
} while (UI != UE && *UI == User);
6290
// Now that we have modified User, add it back to the CSE maps. If it
6291
// already exists there, recursively merge the results together.
6292
AddModifiedNodeToCSEMaps(User);
6295
// If we just RAUW'd the root, take note.
6296
if (From == getRoot().getNode())
6297
setRoot(SDValue(To[getRoot().getResNo()]));
6300
/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6301
/// uses of other values produced by From.getNode() alone. The Deleted
6302
/// vector is handled the same way as for ReplaceAllUsesWith.
6303
void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6304
// Handle the really simple, really trivial case efficiently.
6305
if (From == To) return;
6307
// Handle the simple, trivial, case efficiently.
6308
if (From.getNode()->getNumValues() == 1) {
6309
ReplaceAllUsesWith(From, To);
6313
// Iterate over just the existing users of From. See the comments in
6314
// the ReplaceAllUsesWith above.
6315
SDNode::use_iterator UI = From.getNode()->use_begin(),
6316
UE = From.getNode()->use_end();
6317
RAUWUpdateListener Listener(*this, UI, UE);
6320
bool UserRemovedFromCSEMaps = false;
6322
// A user can appear in a use list multiple times, and when this
6323
// happens the uses are usually next to each other in the list.
6324
// To help reduce the number of CSE recomputations, process all
6325
// the uses of this user that we can find this way.
6327
SDUse &Use = UI.getUse();
6329
// Skip uses of different values from the same node.
6330
if (Use.getResNo() != From.getResNo()) {
6335
// If this node hasn't been modified yet, it's still in the CSE maps,
6336
// so remove its old self from the CSE maps.
6337
if (!UserRemovedFromCSEMaps) {
6338
RemoveNodeFromCSEMaps(User);
6339
UserRemovedFromCSEMaps = true;
6344
} while (UI != UE && *UI == User);
6346
// We are iterating over all uses of the From node, so if a use
6347
// doesn't use the specific value, no changes are made.
6348
if (!UserRemovedFromCSEMaps)
6351
// Now that we have modified User, add it back to the CSE maps. If it
6352
// already exists there, recursively merge the results together.
6353
AddModifiedNodeToCSEMaps(User);
6356
// If we just RAUW'd the root, take note.
6357
if (From == getRoot())
6362
/// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6363
/// to record information about a use.
6370
/// operator< - Sort Memos by User.
6371
bool operator<(const UseMemo &L, const UseMemo &R) {
6372
return (intptr_t)L.User < (intptr_t)R.User;
6376
/// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6377
/// uses of other values produced by From.getNode() alone. The same value
6378
/// may appear in both the From and To list. The Deleted vector is
6379
/// handled the same way as for ReplaceAllUsesWith.
6380
void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6383
// Handle the simple, trivial case efficiently.
6385
return ReplaceAllUsesOfValueWith(*From, *To);
6387
// Read up all the uses and make records of them. This helps
6388
// processing new uses that are introduced during the
6389
// replacement process.
6390
SmallVector<UseMemo, 4> Uses;
6391
for (unsigned i = 0; i != Num; ++i) {
6392
unsigned FromResNo = From[i].getResNo();
6393
SDNode *FromNode = From[i].getNode();
6394
for (SDNode::use_iterator UI = FromNode->use_begin(),
6395
E = FromNode->use_end(); UI != E; ++UI) {
6396
SDUse &Use = UI.getUse();
6397
if (Use.getResNo() == FromResNo) {
6398
UseMemo Memo = { *UI, i, &Use };
6399
Uses.push_back(Memo);
6404
// Sort the uses, so that all the uses from a given User are together.
6405
std::sort(Uses.begin(), Uses.end());
6407
for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6408
UseIndex != UseIndexEnd; ) {
6409
// We know that this user uses some value of From. If it is the right
6410
// value, update it.
6411
SDNode *User = Uses[UseIndex].User;
6413
// This node is about to morph, remove its old self from the CSE maps.
6414
RemoveNodeFromCSEMaps(User);
6416
// The Uses array is sorted, so all the uses for a given User
6417
// are next to each other in the list.
6418
// To help reduce the number of CSE recomputations, process all
6419
// the uses of this user that we can find this way.
6421
unsigned i = Uses[UseIndex].Index;
6422
SDUse &Use = *Uses[UseIndex].Use;
6426
} while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6428
// Now that we have modified User, add it back to the CSE maps. If it
6429
// already exists there, recursively merge the results together.
6430
AddModifiedNodeToCSEMaps(User);
6434
/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6435
/// based on their topological order. It returns the maximum id and a vector
6436
/// of the SDNodes* in assigned order by reference.
6437
unsigned SelectionDAG::AssignTopologicalOrder() {
6439
unsigned DAGSize = 0;
6441
// SortedPos tracks the progress of the algorithm. Nodes before it are
6442
// sorted, nodes after it are unsorted. When the algorithm completes
6443
// it is at the end of the list.
6444
allnodes_iterator SortedPos = allnodes_begin();
6446
// Visit all the nodes. Move nodes with no operands to the front of
6447
// the list immediately. Annotate nodes that do have operands with their
6448
// operand count. Before we do this, the Node Id fields of the nodes
6449
// may contain arbitrary values. After, the Node Id fields for nodes
6450
// before SortedPos will contain the topological sort index, and the
6451
// Node Id fields for nodes At SortedPos and after will contain the
6452
// count of outstanding operands.
6453
for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6455
checkForCycles(N, this);
6456
unsigned Degree = N->getNumOperands();
6458
// A node with no uses, add it to the result array immediately.
6459
N->setNodeId(DAGSize++);
6460
allnodes_iterator Q = N;
6462
SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6463
assert(SortedPos != AllNodes.end() && "Overran node list");
6466
// Temporarily use the Node Id as scratch space for the degree count.
6467
N->setNodeId(Degree);
6471
// Visit all the nodes. As we iterate, move nodes into sorted order,
6472
// such that by the time the end is reached all nodes will be sorted.
6473
for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6475
checkForCycles(N, this);
6476
// N is in sorted position, so all its uses have one less operand
6477
// that needs to be sorted.
6478
for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6481
unsigned Degree = P->getNodeId();
6482
assert(Degree != 0 && "Invalid node degree");
6485
// All of P's operands are sorted, so P may sorted now.
6486
P->setNodeId(DAGSize++);
6488
SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6489
assert(SortedPos != AllNodes.end() && "Overran node list");
6492
// Update P's outstanding operand count.
6493
P->setNodeId(Degree);
6496
if (I == SortedPos) {
6499
dbgs() << "Overran sorted position:\n";
6500
S->dumprFull(this); dbgs() << "\n";
6501
dbgs() << "Checking if this is due to cycles\n";
6502
checkForCycles(this, true);
6504
llvm_unreachable(nullptr);
6508
assert(SortedPos == AllNodes.end() &&
6509
"Topological sort incomplete!");
6510
assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6511
"First node in topological sort is not the entry token!");
6512
assert(AllNodes.front().getNodeId() == 0 &&
6513
"First node in topological sort has non-zero id!");
6514
assert(AllNodes.front().getNumOperands() == 0 &&
6515
"First node in topological sort has operands!");
6516
assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6517
"Last node in topologic sort has unexpected id!");
6518
assert(AllNodes.back().use_empty() &&
6519
"Last node in topologic sort has users!");
6520
assert(DAGSize == allnodes_size() && "Node count mismatch!");
6524
/// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6525
/// value is produced by SD.
6526
void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6528
assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6529
SD->setHasDebugValue(true);
6531
DbgInfo->add(DB, SD, isParameter);
6534
/// TransferDbgValues - Transfer SDDbgValues.
6535
void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6536
if (From == To || !From.getNode()->getHasDebugValue())
6538
SDNode *FromNode = From.getNode();
6539
SDNode *ToNode = To.getNode();
6540
ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6541
SmallVector<SDDbgValue *, 2> ClonedDVs;
6542
for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6544
SDDbgValue *Dbg = *I;
6545
if (Dbg->getKind() == SDDbgValue::SDNODE) {
6547
getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6548
To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6549
Dbg->getDebugLoc(), Dbg->getOrder());
6550
ClonedDVs.push_back(Clone);
6553
for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6554
E = ClonedDVs.end(); I != E; ++I)
6555
AddDbgValue(*I, ToNode, false);
6558
//===----------------------------------------------------------------------===//
6560
//===----------------------------------------------------------------------===//
6562
HandleSDNode::~HandleSDNode() {
6566
GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6567
DebugLoc DL, const GlobalValue *GA,
6568
EVT VT, int64_t o, unsigned char TF)
6569
: SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6573
AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6574
SDValue X, unsigned SrcAS,
6576
: UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6577
SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6579
MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6580
EVT memvt, MachineMemOperand *mmo)
6581
: SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6582
SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6583
MMO->isNonTemporal(), MMO->isInvariant());
6584
assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6585
assert(isNonTemporal() == MMO->isNonTemporal() &&
6586
"Non-temporal encoding error!");
6587
// We check here that the size of the memory operand fits within the size of
6588
// the MMO. This is because the MMO might indicate only a possible address
6589
// range instead of specifying the affected memory addresses precisely.
6590
assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6593
MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6594
ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6595
: SDNode(Opc, Order, dl, VTs, Ops),
6596
MemoryVT(memvt), MMO(mmo) {
6597
SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6598
MMO->isNonTemporal(), MMO->isInvariant());
6599
assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6600
assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6603
/// Profile - Gather unique data for the node.
6605
void SDNode::Profile(FoldingSetNodeID &ID) const {
6606
AddNodeIDNode(ID, this);
6611
std::vector<EVT> VTs;
6614
VTs.reserve(MVT::LAST_VALUETYPE);
6615
for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6616
VTs.push_back(MVT((MVT::SimpleValueType)i));
6621
static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6622
static ManagedStatic<EVTArray> SimpleVTArray;
6623
static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6625
/// getValueTypeList - Return a pointer to the specified value type.
6627
const EVT *SDNode::getValueTypeList(EVT VT) {
6628
if (VT.isExtended()) {
6629
sys::SmartScopedLock<true> Lock(*VTMutex);
6630
return &(*EVTs->insert(VT).first);
6632
assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6633
"Value type out of range!");
6634
return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6638
/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6639
/// indicated value. This method ignores uses of other values defined by this
6641
bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6642
assert(Value < getNumValues() && "Bad value!");
6644
// TODO: Only iterate over uses of a given value of the node
6645
for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6646
if (UI.getUse().getResNo() == Value) {
6653
// Found exactly the right number of uses?
6658
/// hasAnyUseOfValue - Return true if there are any use of the indicated
6659
/// value. This method ignores uses of other values defined by this operation.
6660
bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6661
assert(Value < getNumValues() && "Bad value!");
6663
for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6664
if (UI.getUse().getResNo() == Value)
6671
/// isOnlyUserOf - Return true if this node is the only use of N.
6673
bool SDNode::isOnlyUserOf(const SDNode *N) const {
6675
for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6686
/// isOperand - Return true if this node is an operand of N.
6688
bool SDValue::isOperandOf(const SDNode *N) const {
6689
for (const SDValue &Op : N->op_values())
6695
bool SDNode::isOperandOf(const SDNode *N) const {
6696
for (const SDValue &Op : N->op_values())
6697
if (this == Op.getNode())
6702
/// reachesChainWithoutSideEffects - Return true if this operand (which must
6703
/// be a chain) reaches the specified operand without crossing any
6704
/// side-effecting instructions on any chain path. In practice, this looks
6705
/// through token factors and non-volatile loads. In order to remain efficient,
6706
/// this only looks a couple of nodes in, it does not do an exhaustive search.
6707
bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6708
unsigned Depth) const {
6709
if (*this == Dest) return true;
6711
// Don't search too deeply, we just want to be able to see through
6712
// TokenFactor's etc.
6713
if (Depth == 0) return false;
6715
// If this is a token factor, all inputs to the TF happen in parallel. If any
6716
// of the operands of the TF does not reach dest, then we cannot do the xform.
6717
if (getOpcode() == ISD::TokenFactor) {
6718
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6719
if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6724
// Loads don't have side effects, look through them.
6725
if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6726
if (!Ld->isVolatile())
6727
return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6732
/// hasPredecessor - Return true if N is a predecessor of this node.
6733
/// N is either an operand of this node, or can be reached by recursively
6734
/// traversing up the operands.
6735
/// NOTE: This is an expensive method. Use it carefully.
6736
bool SDNode::hasPredecessor(const SDNode *N) const {
6737
SmallPtrSet<const SDNode *, 32> Visited;
6738
SmallVector<const SDNode *, 16> Worklist;
6739
return hasPredecessorHelper(N, Visited, Worklist);
6743
SDNode::hasPredecessorHelper(const SDNode *N,
6744
SmallPtrSetImpl<const SDNode *> &Visited,
6745
SmallVectorImpl<const SDNode *> &Worklist) const {
6746
if (Visited.empty()) {
6747
Worklist.push_back(this);
6749
// Take a look in the visited set. If we've already encountered this node
6750
// we needn't search further.
6751
if (Visited.count(N))
6755
// Haven't visited N yet. Continue the search.
6756
while (!Worklist.empty()) {
6757
const SDNode *M = Worklist.pop_back_val();
6758
for (const SDValue &OpV : M->op_values()) {
6759
SDNode *Op = OpV.getNode();
6760
if (Visited.insert(Op).second)
6761
Worklist.push_back(Op);
6770
uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6771
assert(Num < NumOperands && "Invalid child # of SDNode!");
6772
return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6775
SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6776
assert(N->getNumValues() == 1 &&
6777
"Can't unroll a vector with multiple results!");
6779
EVT VT = N->getValueType(0);
6780
unsigned NE = VT.getVectorNumElements();
6781
EVT EltVT = VT.getVectorElementType();
6784
SmallVector<SDValue, 8> Scalars;
6785
SmallVector<SDValue, 4> Operands(N->getNumOperands());
6787
// If ResNE is 0, fully unroll the vector op.
6790
else if (NE > ResNE)
6794
for (i= 0; i != NE; ++i) {
6795
for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6796
SDValue Operand = N->getOperand(j);
6797
EVT OperandVT = Operand.getValueType();
6798
if (OperandVT.isVector()) {
6799
// A vector operand; extract a single element.
6800
EVT OperandEltVT = OperandVT.getVectorElementType();
6802
getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6803
getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6805
// A scalar operand; just use it as is.
6806
Operands[j] = Operand;
6810
switch (N->getOpcode()) {
6812
Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6815
Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6822
Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6823
getShiftAmountOperand(Operands[0].getValueType(),
6826
case ISD::SIGN_EXTEND_INREG:
6827
case ISD::FP_ROUND_INREG: {
6828
EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6829
Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6831
getValueType(ExtVT)));
6836
for (; i < ResNE; ++i)
6837
Scalars.push_back(getUNDEF(EltVT));
6839
return getNode(ISD::BUILD_VECTOR, dl,
6840
EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6844
/// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6845
/// location that is 'Dist' units away from the location that the 'Base' load
6846
/// is loading from.
6847
bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6848
unsigned Bytes, int Dist) const {
6849
if (LD->getChain() != Base->getChain())
6851
EVT VT = LD->getValueType(0);
6852
if (VT.getSizeInBits() / 8 != Bytes)
6855
SDValue Loc = LD->getOperand(1);
6856
SDValue BaseLoc = Base->getOperand(1);
6857
if (Loc.getOpcode() == ISD::FrameIndex) {
6858
if (BaseLoc.getOpcode() != ISD::FrameIndex)
6860
const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6861
int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6862
int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6863
int FS = MFI->getObjectSize(FI);
6864
int BFS = MFI->getObjectSize(BFI);
6865
if (FS != BFS || FS != (int)Bytes) return false;
6866
return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6870
if (isBaseWithConstantOffset(Loc)) {
6871
int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6872
if (Loc.getOperand(0) == BaseLoc) {
6873
// If the base location is a simple address with no offset itself, then
6874
// the second load's first add operand should be the base address.
6875
if (LocOffset == Dist * (int)Bytes)
6877
} else if (isBaseWithConstantOffset(BaseLoc)) {
6878
// The base location itself has an offset, so subtract that value from the
6879
// second load's offset before comparing to distance * size.
6881
cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6882
if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6883
if ((LocOffset - BOffset) == Dist * (int)Bytes)
6888
const GlobalValue *GV1 = nullptr;
6889
const GlobalValue *GV2 = nullptr;
6890
int64_t Offset1 = 0;
6891
int64_t Offset2 = 0;
6892
bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6893
bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6894
if (isGA1 && isGA2 && GV1 == GV2)
6895
return Offset1 == (Offset2 + Dist*Bytes);
6900
/// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6901
/// it cannot be inferred.
6902
unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6903
// If this is a GlobalAddress + cst, return the alignment.
6904
const GlobalValue *GV;
6905
int64_t GVOffset = 0;
6906
if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6907
unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6908
APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6909
llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6911
unsigned AlignBits = KnownZero.countTrailingOnes();
6912
unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6914
return MinAlign(Align, GVOffset);
6917
// If this is a direct reference to a stack slot, use information about the
6918
// stack slot's alignment.
6919
int FrameIdx = 1 << 31;
6920
int64_t FrameOffset = 0;
6921
if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6922
FrameIdx = FI->getIndex();
6923
} else if (isBaseWithConstantOffset(Ptr) &&
6924
isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6926
FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6927
FrameOffset = Ptr.getConstantOperandVal(1);
6930
if (FrameIdx != (1 << 31)) {
6931
const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6932
unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6940
/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6941
/// which is split (or expanded) into two not necessarily identical pieces.
6942
std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6943
// Currently all types are split in half.
6945
if (!VT.isVector()) {
6946
LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6948
unsigned NumElements = VT.getVectorNumElements();
6949
assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6950
LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6953
return std::make_pair(LoVT, HiVT);
6956
/// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6958
std::pair<SDValue, SDValue>
6959
SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6961
assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6962
N.getValueType().getVectorNumElements() &&
6963
"More vector elements requested than available!");
6965
Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6966
getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
6967
Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6968
getConstant(LoVT.getVectorNumElements(), DL,
6969
TLI->getVectorIdxTy(getDataLayout())));
6970
return std::make_pair(Lo, Hi);
6973
void SelectionDAG::ExtractVectorElements(SDValue Op,
6974
SmallVectorImpl<SDValue> &Args,
6975
unsigned Start, unsigned Count) {
6976
EVT VT = Op.getValueType();
6978
Count = VT.getVectorNumElements();
6980
EVT EltVT = VT.getVectorElementType();
6981
EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
6983
for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6984
Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6985
Op, getConstant(i, SL, IdxTy)));
6989
// getAddressSpace - Return the address space this GlobalAddress belongs to.
6990
unsigned GlobalAddressSDNode::getAddressSpace() const {
6991
return getGlobal()->getType()->getAddressSpace();
6995
Type *ConstantPoolSDNode::getType() const {
6996
if (isMachineConstantPoolEntry())
6997
return Val.MachineCPVal->getType();
6998
return Val.ConstVal->getType();
7001
bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7003
unsigned &SplatBitSize,
7005
unsigned MinSplatBits,
7006
bool isBigEndian) const {
7007
EVT VT = getValueType(0);
7008
assert(VT.isVector() && "Expected a vector type");
7009
unsigned sz = VT.getSizeInBits();
7010
if (MinSplatBits > sz)
7013
SplatValue = APInt(sz, 0);
7014
SplatUndef = APInt(sz, 0);
7016
// Get the bits. Bits with undefined values (when the corresponding element
7017
// of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7018
// in SplatValue. If any of the values are not constant, give up and return
7020
unsigned int nOps = getNumOperands();
7021
assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7022
unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7024
for (unsigned j = 0; j < nOps; ++j) {
7025
unsigned i = isBigEndian ? nOps-1-j : j;
7026
SDValue OpVal = getOperand(i);
7027
unsigned BitPos = j * EltBitSize;
7029
if (OpVal.getOpcode() == ISD::UNDEF)
7030
SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7031
else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7032
SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7033
zextOrTrunc(sz) << BitPos;
7034
else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7035
SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7040
// The build_vector is all constants or undefs. Find the smallest element
7041
// size that splats the vector.
7043
HasAnyUndefs = (SplatUndef != 0);
7046
unsigned HalfSize = sz / 2;
7047
APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7048
APInt LowValue = SplatValue.trunc(HalfSize);
7049
APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7050
APInt LowUndef = SplatUndef.trunc(HalfSize);
7052
// If the two halves do not match (ignoring undef bits), stop here.
7053
if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7054
MinSplatBits > HalfSize)
7057
SplatValue = HighValue | LowValue;
7058
SplatUndef = HighUndef & LowUndef;
7067
SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7068
if (UndefElements) {
7069
UndefElements->clear();
7070
UndefElements->resize(getNumOperands());
7073
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7074
SDValue Op = getOperand(i);
7075
if (Op.getOpcode() == ISD::UNDEF) {
7077
(*UndefElements)[i] = true;
7078
} else if (!Splatted) {
7080
} else if (Splatted != Op) {
7086
assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7087
"Can only have a splat without a constant for all undefs.");
7088
return getOperand(0);
7095
BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7096
return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7100
BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7101
return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7104
bool BuildVectorSDNode::isConstant() const {
7105
for (const SDValue &Op : op_values()) {
7106
unsigned Opc = Op.getOpcode();
7107
if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7113
bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7114
// Find the first non-undef value in the shuffle mask.
7116
for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7119
assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7121
// Make sure all remaining elements are either undef or the same as the first
7123
for (int Idx = Mask[i]; i != e; ++i)
7124
if (Mask[i] >= 0 && Mask[i] != Idx)
7130
static void checkForCyclesHelper(const SDNode *N,
7131
SmallPtrSetImpl<const SDNode*> &Visited,
7132
SmallPtrSetImpl<const SDNode*> &Checked,
7133
const llvm::SelectionDAG *DAG) {
7134
// If this node has already been checked, don't check it again.
7135
if (Checked.count(N))
7138
// If a node has already been visited on this depth-first walk, reject it as
7140
if (!Visited.insert(N).second) {
7141
errs() << "Detected cycle in SelectionDAG\n";
7142
dbgs() << "Offending node:\n";
7143
N->dumprFull(DAG); dbgs() << "\n";
7147
for (const SDValue &Op : N->op_values())
7148
checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7155
void llvm::checkForCycles(const llvm::SDNode *N,
7156
const llvm::SelectionDAG *DAG,
7164
assert(N && "Checking nonexistent SDNode");
7165
SmallPtrSet<const SDNode*, 32> visited;
7166
SmallPtrSet<const SDNode*, 32> checked;
7167
checkForCyclesHelper(N, visited, checked, DAG);
7172
void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7173
checkForCycles(DAG->getRoot().getNode(), DAG, force);
added
removed
lib/CodeGen/SelectionDAG/SelectionDAG.cpp
