1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This implements the SelectionDAG class.
11 //
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"
50 #include <algorithm>
51 #include <cmath>
53 using namespace llvm;
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
59 return Res;
60 }
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
76 }
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 const APFloat& Val) {
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
84 bool losesInfo;
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
87 &losesInfo);
88 return !losesInfo;
89 }
91 //===----------------------------------------------------------------------===//
92 // ISD Namespace
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 ++i;
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
120 // constants are.
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 return false;
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
128 return false;
129 } else
130 return false;
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
138 return false;
139 return true;
140 }
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
155 continue;
156 IsAllUndef = false;
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
164 // constants are.
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169 return false;
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
172 return false;
173 } else
174 return false;
175 }
177 // Do not accept an all-undef vector.
178 if (IsAllUndef)
179 return false;
180 return true;
181 }
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)
187 return false;
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
192 continue;
193 if (!isa<ConstantSDNode>(Op))
194 return false;
195 }
196 return true;
197 }
199 /// isScalarToVector - Return true if the specified node is a
200 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
201 /// element is not an undef.
202 bool ISD::isScalarToVector(const SDNode *N) {
203 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
204 return true;
206 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 return false;
208 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 return false;
210 unsigned NumElems = N->getNumOperands();
211 if (NumElems == 1)
212 return false;
213 for (unsigned i = 1; i < NumElems; ++i) {
214 SDValue V = N->getOperand(i);
215 if (V.getOpcode() != ISD::UNDEF)
216 return false;
217 }
218 return true;
219 }
221 /// allOperandsUndef - Return true if the node has at least one operand
222 /// and all operands of the specified node are ISD::UNDEF.
223 bool ISD::allOperandsUndef(const SDNode *N) {
224 // Return false if the node has no operands.
225 // This is "logically inconsistent" with the definition of "all" but
226 // is probably the desired behavior.
227 if (N->getNumOperands() == 0)
228 return false;
230 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
231 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
232 return false;
234 return true;
235 }
237 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
238 switch (ExtType) {
239 case ISD::EXTLOAD:
240 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
241 case ISD::SEXTLOAD:
242 return ISD::SIGN_EXTEND;
243 case ISD::ZEXTLOAD:
244 return ISD::ZERO_EXTEND;
245 default:
246 break;
247 }
249 llvm_unreachable("Invalid LoadExtType");
250 }
252 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
253 /// when given the operation for (X op Y).
254 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
255 // To perform this operation, we just need to swap the L and G bits of the
256 // operation.
257 unsigned OldL = (Operation >> 2) & 1;
258 unsigned OldG = (Operation >> 1) & 1;
259 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
260 (OldL << 1) | // New G bit
261 (OldG << 2)); // New L bit.
262 }
264 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
265 /// 'op' is a valid SetCC operation.
266 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
267 unsigned Operation = Op;
268 if (isInteger)
269 Operation ^= 7; // Flip L, G, E bits, but not U.
270 else
271 Operation ^= 15; // Flip all of the condition bits.
273 if (Operation > ISD::SETTRUE2)
274 Operation &= ~8; // Don't let N and U bits get set.
276 return ISD::CondCode(Operation);
277 }
280 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
281 /// signed operation and 2 if the result is an unsigned comparison. Return zero
282 /// if the operation does not depend on the sign of the input (setne and seteq).
283 static int isSignedOp(ISD::CondCode Opcode) {
284 switch (Opcode) {
285 default: llvm_unreachable("Illegal integer setcc operation!");
286 case ISD::SETEQ:
287 case ISD::SETNE: return 0;
288 case ISD::SETLT:
289 case ISD::SETLE:
290 case ISD::SETGT:
291 case ISD::SETGE: return 1;
292 case ISD::SETULT:
293 case ISD::SETULE:
294 case ISD::SETUGT:
295 case ISD::SETUGE: return 2;
296 }
297 }
299 /// getSetCCOrOperation - Return the result of a logical OR between different
300 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
301 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 /// comparison.
303 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304 bool isInteger) {
305 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
306 // Cannot fold a signed integer setcc with an unsigned integer setcc.
307 return ISD::SETCC_INVALID;
309 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
311 // If the N and U bits get set then the resultant comparison DOES suddenly
312 // care about orderedness, and is true when ordered.
313 if (Op > ISD::SETTRUE2)
314 Op &= ~16; // Clear the U bit if the N bit is set.
316 // Canonicalize illegal integer setcc's.
317 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
318 Op = ISD::SETNE;
320 return ISD::CondCode(Op);
321 }
323 /// getSetCCAndOperation - Return the result of a logical AND between different
324 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
325 /// function returns zero if it is not possible to represent the resultant
326 /// comparison.
327 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328 bool isInteger) {
329 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
330 // Cannot fold a signed setcc with an unsigned setcc.
331 return ISD::SETCC_INVALID;
333 // Combine all of the condition bits.
334 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
336 // Canonicalize illegal integer setcc's.
337 if (isInteger) {
338 switch (Result) {
339 default: break;
340 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
341 case ISD::SETOEQ: // SETEQ & SETU[LG]E
342 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
343 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
344 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
345 }
346 }
348 return Result;
349 }
351 //===----------------------------------------------------------------------===//
352 // SDNode Profile Support
353 //===----------------------------------------------------------------------===//
355 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 ///
357 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 ID.AddInteger(OpC);
359 }
361 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
362 /// solely with their pointer.
363 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
364 ID.AddPointer(VTList.VTs);
365 }
367 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 ///
369 static void AddNodeIDOperands(FoldingSetNodeID &ID,
370 ArrayRef<SDValue> Ops) {
371 for (auto& Op : Ops) {
372 ID.AddPointer(Op.getNode());
373 ID.AddInteger(Op.getResNo());
374 }
375 }
377 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 ///
379 static void AddNodeIDOperands(FoldingSetNodeID &ID,
380 ArrayRef<SDUse> Ops) {
381 for (auto& Op : Ops) {
382 ID.AddPointer(Op.getNode());
383 ID.AddInteger(Op.getResNo());
384 }
385 }
387 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
388 bool exact) {
389 ID.AddBoolean(nuw);
390 ID.AddBoolean(nsw);
391 ID.AddBoolean(exact);
392 }
394 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
395 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
396 bool nuw, bool nsw, bool exact) {
397 if (isBinOpWithFlags(Opcode))
398 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
399 }
401 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
402 SDVTList VTList, ArrayRef<SDValue> OpList) {
403 AddNodeIDOpcode(ID, OpC);
404 AddNodeIDValueTypes(ID, VTList);
405 AddNodeIDOperands(ID, OpList);
406 }
408 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 /// the NodeID data.
410 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
411 switch (N->getOpcode()) {
412 case ISD::TargetExternalSymbol:
413 case ISD::ExternalSymbol:
414 llvm_unreachable("Should only be used on nodes with operands");
415 default: break; // Normal nodes don't need extra info.
416 case ISD::TargetConstant:
417 case ISD::Constant: {
418 const ConstantSDNode *C = cast<ConstantSDNode>(N);
419 ID.AddPointer(C->getConstantIntValue());
420 ID.AddBoolean(C->isOpaque());
421 break;
422 }
423 case ISD::TargetConstantFP:
424 case ISD::ConstantFP: {
425 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
426 break;
427 }
428 case ISD::TargetGlobalAddress:
429 case ISD::GlobalAddress:
430 case ISD::TargetGlobalTLSAddress:
431 case ISD::GlobalTLSAddress: {
432 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
433 ID.AddPointer(GA->getGlobal());
434 ID.AddInteger(GA->getOffset());
435 ID.AddInteger(GA->getTargetFlags());
436 ID.AddInteger(GA->getAddressSpace());
437 break;
438 }
439 case ISD::BasicBlock:
440 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
441 break;
442 case ISD::Register:
443 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444 break;
445 case ISD::RegisterMask:
446 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
447 break;
448 case ISD::SRCVALUE:
449 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450 break;
451 case ISD::FrameIndex:
452 case ISD::TargetFrameIndex:
453 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
454 break;
455 case ISD::JumpTable:
456 case ISD::TargetJumpTable:
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
458 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459 break;
460 case ISD::ConstantPool:
461 case ISD::TargetConstantPool: {
462 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
463 ID.AddInteger(CP->getAlignment());
464 ID.AddInteger(CP->getOffset());
465 if (CP->isMachineConstantPoolEntry())
466 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467 else
468 ID.AddPointer(CP->getConstVal());
469 ID.AddInteger(CP->getTargetFlags());
470 break;
471 }
472 case ISD::TargetIndex: {
473 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
474 ID.AddInteger(TI->getIndex());
475 ID.AddInteger(TI->getOffset());
476 ID.AddInteger(TI->getTargetFlags());
477 break;
478 }
479 case ISD::LOAD: {
480 const LoadSDNode *LD = cast<LoadSDNode>(N);
481 ID.AddInteger(LD->getMemoryVT().getRawBits());
482 ID.AddInteger(LD->getRawSubclassData());
483 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
484 break;
485 }
486 case ISD::STORE: {
487 const StoreSDNode *ST = cast<StoreSDNode>(N);
488 ID.AddInteger(ST->getMemoryVT().getRawBits());
489 ID.AddInteger(ST->getRawSubclassData());
490 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
491 break;
492 }
493 case ISD::SDIV:
494 case ISD::UDIV:
495 case ISD::SRA:
496 case ISD::SRL:
497 case ISD::MUL:
498 case ISD::ADD:
499 case ISD::SUB:
500 case ISD::SHL: {
501 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
502 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
503 BinNode->hasNoSignedWrap(), BinNode->isExact());
504 break;
505 }
506 case ISD::ATOMIC_CMP_SWAP:
507 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
508 case ISD::ATOMIC_SWAP:
509 case ISD::ATOMIC_LOAD_ADD:
510 case ISD::ATOMIC_LOAD_SUB:
511 case ISD::ATOMIC_LOAD_AND:
512 case ISD::ATOMIC_LOAD_OR:
513 case ISD::ATOMIC_LOAD_XOR:
514 case ISD::ATOMIC_LOAD_NAND:
515 case ISD::ATOMIC_LOAD_MIN:
516 case ISD::ATOMIC_LOAD_MAX:
517 case ISD::ATOMIC_LOAD_UMIN:
518 case ISD::ATOMIC_LOAD_UMAX:
519 case ISD::ATOMIC_LOAD:
520 case ISD::ATOMIC_STORE: {
521 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
522 ID.AddInteger(AT->getMemoryVT().getRawBits());
523 ID.AddInteger(AT->getRawSubclassData());
524 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
525 break;
526 }
527 case ISD::PREFETCH: {
528 const MemSDNode *PF = cast<MemSDNode>(N);
529 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
530 break;
531 }
532 case ISD::VECTOR_SHUFFLE: {
533 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
534 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535 i != e; ++i)
536 ID.AddInteger(SVN->getMaskElt(i));
537 break;
538 }
539 case ISD::TargetBlockAddress:
540 case ISD::BlockAddress: {
541 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
542 ID.AddPointer(BA->getBlockAddress());
543 ID.AddInteger(BA->getOffset());
544 ID.AddInteger(BA->getTargetFlags());
545 break;
546 }
547 } // end switch (N->getOpcode())
549 // Target specific memory nodes could also have address spaces to check.
550 if (N->isTargetMemoryOpcode())
551 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
552 }
554 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 /// data.
556 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
557 AddNodeIDOpcode(ID, N->getOpcode());
558 // Add the return value info.
559 AddNodeIDValueTypes(ID, N->getVTList());
560 // Add the operand info.
561 AddNodeIDOperands(ID, N->ops());
563 // Handle SDNode leafs with special info.
564 AddNodeIDCustom(ID, N);
565 }
567 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
568 /// the CSE map that carries volatility, temporalness, indexing mode, and
569 /// extension/truncation information.
570 ///
571 static inline unsigned
572 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
573 bool isNonTemporal, bool isInvariant) {
574 assert((ConvType & 3) == ConvType &&
575 "ConvType may not require more than 2 bits!");
576 assert((AM & 7) == AM &&
577 "AM may not require more than 3 bits!");
578 return ConvType |
579 (AM << 2) |
580 (isVolatile << 5) |
581 (isNonTemporal << 6) |
582 (isInvariant << 7);
583 }
585 //===----------------------------------------------------------------------===//
586 // SelectionDAG Class
587 //===----------------------------------------------------------------------===//
589 /// doNotCSE - Return true if CSE should not be performed for this node.
590 static bool doNotCSE(SDNode *N) {
591 if (N->getValueType(0) == MVT::Glue)
592 return true; // Never CSE anything that produces a flag.
594 switch (N->getOpcode()) {
595 default: break;
596 case ISD::HANDLENODE:
597 case ISD::EH_LABEL:
598 return true; // Never CSE these nodes.
599 }
601 // Check that remaining values produced are not flags.
602 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
603 if (N->getValueType(i) == MVT::Glue)
604 return true; // Never CSE anything that produces a flag.
606 return false;
607 }
609 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 /// SelectionDAG.
611 void SelectionDAG::RemoveDeadNodes() {
612 // Create a dummy node (which is not added to allnodes), that adds a reference
613 // to the root node, preventing it from being deleted.
614 HandleSDNode Dummy(getRoot());
616 SmallVector<SDNode*, 128> DeadNodes;
618 // Add all obviously-dead nodes to the DeadNodes worklist.
619 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620 if (I->use_empty())
621 DeadNodes.push_back(I);
623 RemoveDeadNodes(DeadNodes);
625 // If the root changed (e.g. it was a dead load, update the root).
626 setRoot(Dummy.getValue());
627 }
629 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
630 /// given list, and any nodes that become unreachable as a result.
631 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
633 // Process the worklist, deleting the nodes and adding their uses to the
634 // worklist.
635 while (!DeadNodes.empty()) {
636 SDNode *N = DeadNodes.pop_back_val();
638 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
639 DUL->NodeDeleted(N, nullptr);
641 // Take the node out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Next, brutally remove the operand list. This is safe to do, as there are
645 // no cycles in the graph.
646 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647 SDUse &Use = *I++;
648 SDNode *Operand = Use.getNode();
649 Use.set(SDValue());
651 // Now that we removed this operand, see if there are no uses of it left.
652 if (Operand->use_empty())
653 DeadNodes.push_back(Operand);
654 }
656 DeallocateNode(N);
657 }
658 }
660 void SelectionDAG::RemoveDeadNode(SDNode *N){
661 SmallVector<SDNode*, 16> DeadNodes(1, N);
663 // Create a dummy node that adds a reference to the root node, preventing
664 // it from being deleted. (This matters if the root is an operand of the
665 // dead node.)
666 HandleSDNode Dummy(getRoot());
668 RemoveDeadNodes(DeadNodes);
669 }
671 void SelectionDAG::DeleteNode(SDNode *N) {
672 // First take this out of the appropriate CSE map.
673 RemoveNodeFromCSEMaps(N);
675 // Finally, remove uses due to operands of this node, remove from the
676 // AllNodes list, and delete the node.
677 DeleteNodeNotInCSEMaps(N);
678 }
680 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
681 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
682 assert(N->use_empty() && "Cannot delete a node that is not dead!");
684 // Drop all of the operands and decrement used node's use counts.
685 N->DropOperands();
687 DeallocateNode(N);
688 }
690 void SDDbgInfo::erase(const SDNode *Node) {
691 DbgValMapType::iterator I = DbgValMap.find(Node);
692 if (I == DbgValMap.end())
693 return;
694 for (auto &Val: I->second)
695 Val->setIsInvalidated();
696 DbgValMap.erase(I);
697 }
699 void SelectionDAG::DeallocateNode(SDNode *N) {
700 if (N->OperandsNeedDelete)
701 delete[] N->OperandList;
703 // Set the opcode to DELETED_NODE to help catch bugs when node
704 // memory is reallocated.
705 N->NodeType = ISD::DELETED_NODE;
707 NodeAllocator.Deallocate(AllNodes.remove(N));
709 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
710 // them and forget about that node.
711 DbgInfo->erase(N);
712 }
714 #ifndef NDEBUG
715 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
716 static void VerifySDNode(SDNode *N) {
717 switch (N->getOpcode()) {
718 default:
719 break;
720 case ISD::BUILD_PAIR: {
721 EVT VT = N->getValueType(0);
722 assert(N->getNumValues() == 1 && "Too many results!");
723 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
724 "Wrong return type!");
725 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
726 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
727 "Mismatched operand types!");
728 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
729 "Wrong operand type!");
730 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
731 "Wrong return type size");
732 break;
733 }
734 case ISD::BUILD_VECTOR: {
735 assert(N->getNumValues() == 1 && "Too many results!");
736 assert(N->getValueType(0).isVector() && "Wrong return type!");
737 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
738 "Wrong number of operands!");
739 EVT EltVT = N->getValueType(0).getVectorElementType();
740 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
741 assert((I->getValueType() == EltVT ||
742 (EltVT.isInteger() && I->getValueType().isInteger() &&
743 EltVT.bitsLE(I->getValueType()))) &&
744 "Wrong operand type!");
745 assert(I->getValueType() == N->getOperand(0).getValueType() &&
746 "Operands must all have the same type");
747 }
748 break;
749 }
750 }
751 }
752 #endif // NDEBUG
754 /// \brief Insert a newly allocated node into the DAG.
755 ///
756 /// Handles insertion into the all nodes list and CSE map, as well as
757 /// verification and other common operations when a new node is allocated.
758 void SelectionDAG::InsertNode(SDNode *N) {
759 AllNodes.push_back(N);
760 #ifndef NDEBUG
761 VerifySDNode(N);
762 #endif
763 }
765 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
766 /// correspond to it. This is useful when we're about to delete or repurpose
767 /// the node. We don't want future request for structurally identical nodes
768 /// to return N anymore.
769 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
770 bool Erased = false;
771 switch (N->getOpcode()) {
772 case ISD::HANDLENODE: return false; // noop.
773 case ISD::CONDCODE:
774 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
775 "Cond code doesn't exist!");
776 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
777 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
778 break;
779 case ISD::ExternalSymbol:
780 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
781 break;
782 case ISD::TargetExternalSymbol: {
783 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
784 Erased = TargetExternalSymbols.erase(
785 std::pair<std::string,unsigned char>(ESN->getSymbol(),
786 ESN->getTargetFlags()));
787 break;
788 }
789 case ISD::VALUETYPE: {
790 EVT VT = cast<VTSDNode>(N)->getVT();
791 if (VT.isExtended()) {
792 Erased = ExtendedValueTypeNodes.erase(VT);
793 } else {
794 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
795 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
796 }
797 break;
798 }
799 default:
800 // Remove it from the CSE Map.
801 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
802 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
803 Erased = CSEMap.RemoveNode(N);
804 break;
805 }
806 #ifndef NDEBUG
807 // Verify that the node was actually in one of the CSE maps, unless it has a
808 // flag result (which cannot be CSE'd) or is one of the special cases that are
809 // not subject to CSE.
810 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
811 !N->isMachineOpcode() && !doNotCSE(N)) {
812 N->dump(this);
813 dbgs() << "\n";
814 llvm_unreachable("Node is not in map!");
815 }
816 #endif
817 return Erased;
818 }
820 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
821 /// maps and modified in place. Add it back to the CSE maps, unless an identical
822 /// node already exists, in which case transfer all its users to the existing
823 /// node. This transfer can potentially trigger recursive merging.
824 ///
825 void
826 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
827 // For node types that aren't CSE'd, just act as if no identical node
828 // already exists.
829 if (!doNotCSE(N)) {
830 SDNode *Existing = CSEMap.GetOrInsertNode(N);
831 if (Existing != N) {
832 // If there was already an existing matching node, use ReplaceAllUsesWith
833 // to replace the dead one with the existing one. This can cause
834 // recursive merging of other unrelated nodes down the line.
835 ReplaceAllUsesWith(N, Existing);
837 // N is now dead. Inform the listeners and delete it.
838 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
839 DUL->NodeDeleted(N, Existing);
840 DeleteNodeNotInCSEMaps(N);
841 return;
842 }
843 }
845 // If the node doesn't already exist, we updated it. Inform listeners.
846 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
847 DUL->NodeUpdated(N);
848 }
850 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
851 /// were replaced with those specified. If this node is never memoized,
852 /// return null, otherwise return a pointer to the slot it would take. If a
853 /// node already exists with these operands, the slot will be non-null.
854 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
855 void *&InsertPos) {
856 if (doNotCSE(N))
857 return nullptr;
859 SDValue Ops[] = { Op };
860 FoldingSetNodeID ID;
861 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
862 AddNodeIDCustom(ID, N);
863 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
864 return Node;
865 }
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified. If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take. If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
872 SDValue Op1, SDValue Op2,
873 void *&InsertPos) {
874 if (doNotCSE(N))
875 return nullptr;
877 SDValue Ops[] = { Op1, Op2 };
878 FoldingSetNodeID ID;
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
882 return Node;
883 }
886 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
887 /// were replaced with those specified. If this node is never memoized,
888 /// return null, otherwise return a pointer to the slot it would take. If a
889 /// node already exists with these operands, the slot will be non-null.
890 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
891 void *&InsertPos) {
892 if (doNotCSE(N))
893 return nullptr;
895 FoldingSetNodeID ID;
896 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897 AddNodeIDCustom(ID, N);
898 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
899 return Node;
900 }
902 /// getEVTAlignment - Compute the default alignment value for the
903 /// given type.
904 ///
905 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
906 Type *Ty = VT == MVT::iPTR ?
907 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
908 VT.getTypeForEVT(*getContext());
910 return TLI->getDataLayout()->getABITypeAlignment(Ty);
911 }
913 // EntryNode could meaningfully have debug info if we can find it...
914 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
915 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
916 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
917 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
918 UpdateListeners(nullptr) {
919 AllNodes.push_back(&EntryNode);
920 DbgInfo = new SDDbgInfo();
921 }
923 void SelectionDAG::init(MachineFunction &mf) {
924 MF = &mf;
925 TLI = getSubtarget().getTargetLowering();
926 TSI = getSubtarget().getSelectionDAGInfo();
927 Context = &mf.getFunction()->getContext();
928 }
930 SelectionDAG::~SelectionDAG() {
931 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
932 allnodes_clear();
933 delete DbgInfo;
934 }
936 void SelectionDAG::allnodes_clear() {
937 assert(&*AllNodes.begin() == &EntryNode);
938 AllNodes.remove(AllNodes.begin());
939 while (!AllNodes.empty())
940 DeallocateNode(AllNodes.begin());
941 }
943 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
944 SDVTList VTs, SDValue N1,
945 SDValue N2, bool nuw, bool nsw,
946 bool exact) {
947 if (isBinOpWithFlags(Opcode)) {
948 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
949 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
950 FN->setHasNoUnsignedWrap(nuw);
951 FN->setHasNoSignedWrap(nsw);
952 FN->setIsExact(exact);
954 return FN;
955 }
957 BinarySDNode *N = new (NodeAllocator)
958 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
959 return N;
960 }
962 void SelectionDAG::clear() {
963 allnodes_clear();
964 OperandAllocator.Reset();
965 CSEMap.clear();
967 ExtendedValueTypeNodes.clear();
968 ExternalSymbols.clear();
969 TargetExternalSymbols.clear();
970 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
971 static_cast<CondCodeSDNode*>(nullptr));
972 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
973 static_cast<SDNode*>(nullptr));
975 EntryNode.UseList = nullptr;
976 AllNodes.push_back(&EntryNode);
977 Root = getEntryNode();
978 DbgInfo->clear();
979 }
981 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
982 return VT.bitsGT(Op.getValueType()) ?
983 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
984 getNode(ISD::TRUNCATE, DL, VT, Op);
985 }
987 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
988 return VT.bitsGT(Op.getValueType()) ?
989 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
990 getNode(ISD::TRUNCATE, DL, VT, Op);
991 }
993 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
994 return VT.bitsGT(Op.getValueType()) ?
995 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
996 getNode(ISD::TRUNCATE, DL, VT, Op);
997 }
999 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1000 EVT OpVT) {
1001 if (VT.bitsLE(Op.getValueType()))
1002 return getNode(ISD::TRUNCATE, SL, VT, Op);
1004 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1005 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1006 }
1008 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1009 assert(!VT.isVector() &&
1010 "getZeroExtendInReg should use the vector element type instead of "
1011 "the vector type!");
1012 if (Op.getValueType() == VT) return Op;
1013 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1014 APInt Imm = APInt::getLowBitsSet(BitWidth,
1015 VT.getSizeInBits());
1016 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1017 getConstant(Imm, Op.getValueType()));
1018 }
1020 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1021 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1022 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1023 "The sizes of the input and result must match in order to perform the "
1024 "extend in-register.");
1025 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1026 "The destination vector type must have fewer lanes than the input.");
1027 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1028 }
1030 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1031 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1032 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1033 "The sizes of the input and result must match in order to perform the "
1034 "extend in-register.");
1035 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1036 "The destination vector type must have fewer lanes than the input.");
1037 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1038 }
1040 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1041 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1042 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1043 "The sizes of the input and result must match in order to perform the "
1044 "extend in-register.");
1045 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1046 "The destination vector type must have fewer lanes than the input.");
1047 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1048 }
1050 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1051 ///
1052 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1053 EVT EltVT = VT.getScalarType();
1054 SDValue NegOne =
1055 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1056 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1057 }
1059 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1060 EVT EltVT = VT.getScalarType();
1061 SDValue TrueValue;
1062 switch (TLI->getBooleanContents(VT)) {
1063 case TargetLowering::ZeroOrOneBooleanContent:
1064 case TargetLowering::UndefinedBooleanContent:
1065 TrueValue = getConstant(1, VT);
1066 break;
1067 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1068 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1069 VT);
1070 break;
1071 }
1072 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1073 }
1075 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1076 EVT EltVT = VT.getScalarType();
1077 assert((EltVT.getSizeInBits() >= 64 ||
1078 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1079 "getConstant with a uint64_t value that doesn't fit in the type!");
1080 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1081 }
1083 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1084 {
1085 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1086 }
1088 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1089 bool isO) {
1090 assert(VT.isInteger() && "Cannot create FP integer constant!");
1092 EVT EltVT = VT.getScalarType();
1093 const ConstantInt *Elt = &Val;
1095 // In some cases the vector type is legal but the element type is illegal and
1096 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1097 // inserted value (the type does not need to match the vector element type).
1098 // Any extra bits introduced will be truncated away.
1099 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1100 TargetLowering::TypePromoteInteger) {
1101 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1102 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1103 Elt = ConstantInt::get(*getContext(), NewVal);
1104 }
1105 // In other cases the element type is illegal and needs to be expanded, for
1106 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1107 // the value into n parts and use a vector type with n-times the elements.
1108 // Then bitcast to the type requested.
1109 // Legalizing constants too early makes the DAGCombiner's job harder so we
1110 // only legalize if the DAG tells us we must produce legal types.
1111 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1112 TLI->getTypeAction(*getContext(), EltVT) ==
1113 TargetLowering::TypeExpandInteger) {
1114 APInt NewVal = Elt->getValue();
1115 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1116 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1117 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1118 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1120 // Check the temporary vector is the correct size. If this fails then
1121 // getTypeToTransformTo() probably returned a type whose size (in bits)
1122 // isn't a power-of-2 factor of the requested type size.
1123 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1125 SmallVector<SDValue, 2> EltParts;
1126 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1127 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1128 .trunc(ViaEltSizeInBits),
1129 ViaEltVT, isT, isO));
1130 }
1132 // EltParts is currently in little endian order. If we actually want
1133 // big-endian order then reverse it now.
1134 if (TLI->isBigEndian())
1135 std::reverse(EltParts.begin(), EltParts.end());
1137 // The elements must be reversed when the element order is different
1138 // to the endianness of the elements (because the BITCAST is itself a
1139 // vector shuffle in this situation). However, we do not need any code to
1140 // perform this reversal because getConstant() is producing a vector
1141 // splat.
1142 // This situation occurs in MIPS MSA.
1144 SmallVector<SDValue, 8> Ops;
1145 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1146 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1148 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1149 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1150 Ops));
1151 return Result;
1152 }
1154 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1155 "APInt size does not match type size!");
1156 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1157 FoldingSetNodeID ID;
1158 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1159 ID.AddPointer(Elt);
1160 ID.AddBoolean(isO);
1161 void *IP = nullptr;
1162 SDNode *N = nullptr;
1163 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1164 if (!VT.isVector())
1165 return SDValue(N, 0);
1167 if (!N) {
1168 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1169 CSEMap.InsertNode(N, IP);
1170 InsertNode(N);
1171 }
1173 SDValue Result(N, 0);
1174 if (VT.isVector()) {
1175 SmallVector<SDValue, 8> Ops;
1176 Ops.assign(VT.getVectorNumElements(), Result);
1177 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1178 }
1179 return Result;
1180 }
1182 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1183 return getConstant(Val, TLI->getPointerTy(), isTarget);
1184 }
1187 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1188 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1189 }
1191 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1192 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1194 EVT EltVT = VT.getScalarType();
1196 // Do the map lookup using the actual bit pattern for the floating point
1197 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1198 // we don't have issues with SNANs.
1199 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1200 FoldingSetNodeID ID;
1201 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1202 ID.AddPointer(&V);
1203 void *IP = nullptr;
1204 SDNode *N = nullptr;
1205 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1206 if (!VT.isVector())
1207 return SDValue(N, 0);
1209 if (!N) {
1210 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1211 CSEMap.InsertNode(N, IP);
1212 InsertNode(N);
1213 }
1215 SDValue Result(N, 0);
1216 if (VT.isVector()) {
1217 SmallVector<SDValue, 8> Ops;
1218 Ops.assign(VT.getVectorNumElements(), Result);
1219 // FIXME SDLoc info might be appropriate here
1220 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1221 }
1222 return Result;
1223 }
1225 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1226 EVT EltVT = VT.getScalarType();
1227 if (EltVT==MVT::f32)
1228 return getConstantFP(APFloat((float)Val), VT, isTarget);
1229 else if (EltVT==MVT::f64)
1230 return getConstantFP(APFloat(Val), VT, isTarget);
1231 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1232 EltVT==MVT::f16) {
1233 bool ignored;
1234 APFloat apf = APFloat(Val);
1235 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1236 &ignored);
1237 return getConstantFP(apf, VT, isTarget);
1238 } else
1239 llvm_unreachable("Unsupported type in getConstantFP");
1240 }
1242 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1243 EVT VT, int64_t Offset,
1244 bool isTargetGA,
1245 unsigned char TargetFlags) {
1246 assert((TargetFlags == 0 || isTargetGA) &&
1247 "Cannot set target flags on target-independent globals");
1249 // Truncate (with sign-extension) the offset value to the pointer size.
1250 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1251 if (BitWidth < 64)
1252 Offset = SignExtend64(Offset, BitWidth);
1254 unsigned Opc;
1255 if (GV->isThreadLocal())
1256 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1257 else
1258 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1260 FoldingSetNodeID ID;
1261 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1262 ID.AddPointer(GV);
1263 ID.AddInteger(Offset);
1264 ID.AddInteger(TargetFlags);
1265 ID.AddInteger(GV->getType()->getAddressSpace());
1266 void *IP = nullptr;
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1271 DL.getDebugLoc(), GV, VT,
1272 Offset, TargetFlags);
1273 CSEMap.InsertNode(N, IP);
1274 InsertNode(N);
1275 return SDValue(N, 0);
1276 }
1278 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1279 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1282 ID.AddInteger(FI);
1283 void *IP = nullptr;
1284 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1285 return SDValue(E, 0);
1287 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1288 CSEMap.InsertNode(N, IP);
1289 InsertNode(N);
1290 return SDValue(N, 0);
1291 }
1293 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1294 unsigned char TargetFlags) {
1295 assert((TargetFlags == 0 || isTarget) &&
1296 "Cannot set target flags on target-independent jump tables");
1297 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1298 FoldingSetNodeID ID;
1299 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1300 ID.AddInteger(JTI);
1301 ID.AddInteger(TargetFlags);
1302 void *IP = nullptr;
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1307 TargetFlags);
1308 CSEMap.InsertNode(N, IP);
1309 InsertNode(N);
1310 return SDValue(N, 0);
1311 }
1313 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1314 unsigned Alignment, int Offset,
1315 bool isTarget,
1316 unsigned char TargetFlags) {
1317 assert((TargetFlags == 0 || isTarget) &&
1318 "Cannot set target flags on target-independent globals");
1319 if (Alignment == 0)
1320 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1321 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1322 FoldingSetNodeID ID;
1323 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1324 ID.AddInteger(Alignment);
1325 ID.AddInteger(Offset);
1326 ID.AddPointer(C);
1327 ID.AddInteger(TargetFlags);
1328 void *IP = nullptr;
1329 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1330 return SDValue(E, 0);
1332 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1333 Alignment, TargetFlags);
1334 CSEMap.InsertNode(N, IP);
1335 InsertNode(N);
1336 return SDValue(N, 0);
1337 }
1340 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1341 unsigned Alignment, int Offset,
1342 bool isTarget,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent globals");
1346 if (Alignment == 0)
1347 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1348 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1349 FoldingSetNodeID ID;
1350 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1351 ID.AddInteger(Alignment);
1352 ID.AddInteger(Offset);
1353 C->addSelectionDAGCSEId(ID);
1354 ID.AddInteger(TargetFlags);
1355 void *IP = nullptr;
1356 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1357 return SDValue(E, 0);
1359 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1360 Alignment, TargetFlags);
1361 CSEMap.InsertNode(N, IP);
1362 InsertNode(N);
1363 return SDValue(N, 0);
1364 }
1366 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1367 unsigned char TargetFlags) {
1368 FoldingSetNodeID ID;
1369 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1370 ID.AddInteger(Index);
1371 ID.AddInteger(Offset);
1372 ID.AddInteger(TargetFlags);
1373 void *IP = nullptr;
1374 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1375 return SDValue(E, 0);
1377 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1378 TargetFlags);
1379 CSEMap.InsertNode(N, IP);
1380 InsertNode(N);
1381 return SDValue(N, 0);
1382 }
1384 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1385 FoldingSetNodeID ID;
1386 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1387 ID.AddPointer(MBB);
1388 void *IP = nullptr;
1389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1390 return SDValue(E, 0);
1392 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1393 CSEMap.InsertNode(N, IP);
1394 InsertNode(N);
1395 return SDValue(N, 0);
1396 }
1398 SDValue SelectionDAG::getValueType(EVT VT) {
1399 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1400 ValueTypeNodes.size())
1401 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1403 SDNode *&N = VT.isExtended() ?
1404 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1406 if (N) return SDValue(N, 0);
1407 N = new (NodeAllocator) VTSDNode(VT);
1408 InsertNode(N);
1409 return SDValue(N, 0);
1410 }
1412 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1413 SDNode *&N = ExternalSymbols[Sym];
1414 if (N) return SDValue(N, 0);
1415 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1416 InsertNode(N);
1417 return SDValue(N, 0);
1418 }
1420 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1421 unsigned char TargetFlags) {
1422 SDNode *&N =
1423 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1424 TargetFlags)];
1425 if (N) return SDValue(N, 0);
1426 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1427 InsertNode(N);
1428 return SDValue(N, 0);
1429 }
1431 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1432 if ((unsigned)Cond >= CondCodeNodes.size())
1433 CondCodeNodes.resize(Cond+1);
1435 if (!CondCodeNodes[Cond]) {
1436 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1437 CondCodeNodes[Cond] = N;
1438 InsertNode(N);
1439 }
1441 return SDValue(CondCodeNodes[Cond], 0);
1442 }
1444 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1445 // the shuffle mask M that point at N1 to point at N2, and indices that point
1446 // N2 to point at N1.
1447 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1448 std::swap(N1, N2);
1449 int NElts = M.size();
1450 for (int i = 0; i != NElts; ++i) {
1451 if (M[i] >= NElts)
1452 M[i] -= NElts;
1453 else if (M[i] >= 0)
1454 M[i] += NElts;
1455 }
1456 }
1458 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1459 SDValue N2, const int *Mask) {
1460 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1461 "Invalid VECTOR_SHUFFLE");
1463 // Canonicalize shuffle undef, undef -> undef
1464 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1465 return getUNDEF(VT);
1467 // Validate that all indices in Mask are within the range of the elements
1468 // input to the shuffle.
1469 unsigned NElts = VT.getVectorNumElements();
1470 SmallVector<int, 8> MaskVec;
1471 for (unsigned i = 0; i != NElts; ++i) {
1472 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1473 MaskVec.push_back(Mask[i]);
1474 }
1476 // Canonicalize shuffle v, v -> v, undef
1477 if (N1 == N2) {
1478 N2 = getUNDEF(VT);
1479 for (unsigned i = 0; i != NElts; ++i)
1480 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1481 }
1483 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1484 if (N1.getOpcode() == ISD::UNDEF)
1485 commuteShuffle(N1, N2, MaskVec);
1487 // Canonicalize all index into lhs, -> shuffle lhs, undef
1488 // Canonicalize all index into rhs, -> shuffle rhs, undef
1489 bool AllLHS = true, AllRHS = true;
1490 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1491 for (unsigned i = 0; i != NElts; ++i) {
1492 if (MaskVec[i] >= (int)NElts) {
1493 if (N2Undef)
1494 MaskVec[i] = -1;
1495 else
1496 AllLHS = false;
1497 } else if (MaskVec[i] >= 0) {
1498 AllRHS = false;
1499 }
1500 }
1501 if (AllLHS && AllRHS)
1502 return getUNDEF(VT);
1503 if (AllLHS && !N2Undef)
1504 N2 = getUNDEF(VT);
1505 if (AllRHS) {
1506 N1 = getUNDEF(VT);
1507 commuteShuffle(N1, N2, MaskVec);
1508 }
1509 // Reset our undef status after accounting for the mask.
1510 N2Undef = N2.getOpcode() == ISD::UNDEF;
1511 // Re-check whether both sides ended up undef.
1512 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1513 return getUNDEF(VT);
1515 // If Identity shuffle return that node.
1516 bool Identity = true;
1517 for (unsigned i = 0; i != NElts; ++i) {
1518 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1519 }
1520 if (Identity && NElts)
1521 return N1;
1523 // Shuffling a constant splat doesn't change the result.
1524 if (N2Undef) {
1525 SDValue V = N1;
1527 // Look through any bitcasts. We check that these don't change the number
1528 // (and size) of elements and just changes their types.
1529 while (V.getOpcode() == ISD::BITCAST)
1530 V = V->getOperand(0);
1532 // A splat should always show up as a build vector node.
1533 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1534 BitVector UndefElements;
1535 SDValue Splat = BV->getSplatValue(&UndefElements);
1536 // If this is a splat of an undef, shuffling it is also undef.
1537 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1538 return getUNDEF(VT);
1540 // We only have a splat which can skip shuffles if there is a splatted
1541 // value and no undef lanes rearranged by the shuffle.
1542 if (Splat && UndefElements.none()) {
1543 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1544 // number of elements match or the value splatted is a zero constant.
1545 if (V.getValueType().getVectorNumElements() ==
1546 VT.getVectorNumElements())
1547 return N1;
1548 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1549 if (C->isNullValue())
1550 return N1;
1551 }
1552 }
1553 }
1555 FoldingSetNodeID ID;
1556 SDValue Ops[2] = { N1, N2 };
1557 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1558 for (unsigned i = 0; i != NElts; ++i)
1559 ID.AddInteger(MaskVec[i]);
1561 void* IP = nullptr;
1562 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1563 return SDValue(E, 0);
1565 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1566 // SDNode doesn't have access to it. This memory will be "leaked" when
1567 // the node is deallocated, but recovered when the NodeAllocator is released.
1568 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1569 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1571 ShuffleVectorSDNode *N =
1572 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1573 dl.getDebugLoc(), N1, N2,
1574 MaskAlloc);
1575 CSEMap.InsertNode(N, IP);
1576 InsertNode(N);
1577 return SDValue(N, 0);
1578 }
1580 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1581 MVT VT = SV.getSimpleValueType(0);
1582 unsigned NumElems = VT.getVectorNumElements();
1583 SmallVector<int, 8> MaskVec;
1585 for (unsigned i = 0; i != NumElems; ++i) {
1586 int Idx = SV.getMaskElt(i);
1587 if (Idx >= 0) {
1588 if (Idx < (int)NumElems)
1589 Idx += NumElems;
1590 else
1591 Idx -= NumElems;
1592 }
1593 MaskVec.push_back(Idx);
1594 }
1596 SDValue Op0 = SV.getOperand(0);
1597 SDValue Op1 = SV.getOperand(1);
1598 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1599 }
1601 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1602 SDValue Val, SDValue DTy,
1603 SDValue STy, SDValue Rnd, SDValue Sat,
1604 ISD::CvtCode Code) {
1605 // If the src and dest types are the same and the conversion is between
1606 // integer types of the same sign or two floats, no conversion is necessary.
1607 if (DTy == STy &&
1608 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1609 return Val;
1611 FoldingSetNodeID ID;
1612 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1613 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1614 void* IP = nullptr;
1615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1616 return SDValue(E, 0);
1618 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1619 dl.getDebugLoc(),
1620 Ops, Code);
1621 CSEMap.InsertNode(N, IP);
1622 InsertNode(N);
1623 return SDValue(N, 0);
1624 }
1626 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1627 FoldingSetNodeID ID;
1628 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1629 ID.AddInteger(RegNo);
1630 void *IP = nullptr;
1631 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1632 return SDValue(E, 0);
1634 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1635 CSEMap.InsertNode(N, IP);
1636 InsertNode(N);
1637 return SDValue(N, 0);
1638 }
1640 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1641 FoldingSetNodeID ID;
1642 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1643 ID.AddPointer(RegMask);
1644 void *IP = nullptr;
1645 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1646 return SDValue(E, 0);
1648 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1649 CSEMap.InsertNode(N, IP);
1650 InsertNode(N);
1651 return SDValue(N, 0);
1652 }
1654 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1655 FoldingSetNodeID ID;
1656 SDValue Ops[] = { Root };
1657 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1658 ID.AddPointer(Label);
1659 void *IP = nullptr;
1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661 return SDValue(E, 0);
1663 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1664 dl.getDebugLoc(), Root, Label);
1665 CSEMap.InsertNode(N, IP);
1666 InsertNode(N);
1667 return SDValue(N, 0);
1668 }
1671 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1672 int64_t Offset,
1673 bool isTarget,
1674 unsigned char TargetFlags) {
1675 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1677 FoldingSetNodeID ID;
1678 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1679 ID.AddPointer(BA);
1680 ID.AddInteger(Offset);
1681 ID.AddInteger(TargetFlags);
1682 void *IP = nullptr;
1683 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1684 return SDValue(E, 0);
1686 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1687 TargetFlags);
1688 CSEMap.InsertNode(N, IP);
1689 InsertNode(N);
1690 return SDValue(N, 0);
1691 }
1693 SDValue SelectionDAG::getSrcValue(const Value *V) {
1694 assert((!V || V->getType()->isPointerTy()) &&
1695 "SrcValue is not a pointer?");
1697 FoldingSetNodeID ID;
1698 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1699 ID.AddPointer(V);
1701 void *IP = nullptr;
1702 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1703 return SDValue(E, 0);
1705 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1706 CSEMap.InsertNode(N, IP);
1707 InsertNode(N);
1708 return SDValue(N, 0);
1709 }
1711 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1712 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1713 FoldingSetNodeID ID;
1714 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1715 ID.AddPointer(MD);
1717 void *IP = nullptr;
1718 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1719 return SDValue(E, 0);
1721 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1722 CSEMap.InsertNode(N, IP);
1723 InsertNode(N);
1724 return SDValue(N, 0);
1725 }
1727 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1728 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1729 unsigned SrcAS, unsigned DestAS) {
1730 SDValue Ops[] = {Ptr};
1731 FoldingSetNodeID ID;
1732 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1733 ID.AddInteger(SrcAS);
1734 ID.AddInteger(DestAS);
1736 void *IP = nullptr;
1737 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1738 return SDValue(E, 0);
1740 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1741 dl.getDebugLoc(),
1742 VT, Ptr, SrcAS, DestAS);
1743 CSEMap.InsertNode(N, IP);
1744 InsertNode(N);
1745 return SDValue(N, 0);
1746 }
1748 /// getShiftAmountOperand - Return the specified value casted to
1749 /// the target's desired shift amount type.
1750 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1751 EVT OpTy = Op.getValueType();
1752 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1753 if (OpTy == ShTy || OpTy.isVector()) return Op;
1755 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1756 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1757 }
1759 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1760 /// specified value type.
1761 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1762 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1763 unsigned ByteSize = VT.getStoreSize();
1764 Type *Ty = VT.getTypeForEVT(*getContext());
1765 unsigned StackAlign =
1766 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1768 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1769 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1770 }
1772 /// CreateStackTemporary - Create a stack temporary suitable for holding
1773 /// either of the specified value types.
1774 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1775 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1776 VT2.getStoreSizeInBits())/8;
1777 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1778 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1779 const DataLayout *TD = TLI->getDataLayout();
1780 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1781 TD->getPrefTypeAlignment(Ty2));
1783 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1784 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1785 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1786 }
1788 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1789 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1790 // These setcc operations always fold.
1791 switch (Cond) {
1792 default: break;
1793 case ISD::SETFALSE:
1794 case ISD::SETFALSE2: return getConstant(0, VT);
1795 case ISD::SETTRUE:
1796 case ISD::SETTRUE2: {
1797 TargetLowering::BooleanContent Cnt =
1798 TLI->getBooleanContents(N1->getValueType(0));
1799 return getConstant(
1800 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1801 }
1803 case ISD::SETOEQ:
1804 case ISD::SETOGT:
1805 case ISD::SETOGE:
1806 case ISD::SETOLT:
1807 case ISD::SETOLE:
1808 case ISD::SETONE:
1809 case ISD::SETO:
1810 case ISD::SETUO:
1811 case ISD::SETUEQ:
1812 case ISD::SETUNE:
1813 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1814 break;
1815 }
1817 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1818 const APInt &C2 = N2C->getAPIntValue();
1819 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1820 const APInt &C1 = N1C->getAPIntValue();
1822 switch (Cond) {
1823 default: llvm_unreachable("Unknown integer setcc!");
1824 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1825 case ISD::SETNE: return getConstant(C1 != C2, VT);
1826 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1827 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1828 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1829 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1830 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1831 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1832 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1833 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1834 }
1835 }
1836 }
1837 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1838 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1839 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1840 switch (Cond) {
1841 default: break;
1842 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1843 return getUNDEF(VT);
1844 // fall through
1845 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1846 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1847 return getUNDEF(VT);
1848 // fall through
1849 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1850 R==APFloat::cmpLessThan, VT);
1851 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1852 return getUNDEF(VT);
1853 // fall through
1854 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1855 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1856 return getUNDEF(VT);
1857 // fall through
1858 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1859 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1860 return getUNDEF(VT);
1861 // fall through
1862 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1863 R==APFloat::cmpEqual, VT);
1864 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1865 return getUNDEF(VT);
1866 // fall through
1867 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1868 R==APFloat::cmpEqual, VT);
1869 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1870 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1871 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1872 R==APFloat::cmpEqual, VT);
1873 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1874 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1875 R==APFloat::cmpLessThan, VT);
1876 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1877 R==APFloat::cmpUnordered, VT);
1878 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1879 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1880 }
1881 } else {
1882 // Ensure that the constant occurs on the RHS.
1883 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1884 MVT CompVT = N1.getValueType().getSimpleVT();
1885 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1886 return SDValue();
1888 return getSetCC(dl, VT, N2, N1, SwappedCond);
1889 }
1890 }
1892 // Could not fold it.
1893 return SDValue();
1894 }
1896 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1897 /// use this predicate to simplify operations downstream.
1898 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1899 // This predicate is not safe for vector operations.
1900 if (Op.getValueType().isVector())
1901 return false;
1903 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1904 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1905 }
1907 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1908 /// this predicate to simplify operations downstream. Mask is known to be zero
1909 /// for bits that V cannot have.
1910 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1911 unsigned Depth) const {
1912 APInt KnownZero, KnownOne;
1913 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1914 return (KnownZero & Mask) == Mask;
1915 }
1917 /// Determine which bits of Op are known to be either zero or one and return
1918 /// them in the KnownZero/KnownOne bitsets.
1919 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1920 APInt &KnownOne, unsigned Depth) const {
1921 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1923 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1924 if (Depth == 6)
1925 return; // Limit search depth.
1927 APInt KnownZero2, KnownOne2;
1929 switch (Op.getOpcode()) {
1930 case ISD::Constant:
1931 // We know all of the bits for a constant!
1932 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1933 KnownZero = ~KnownOne;
1934 break;
1935 case ISD::AND:
1936 // If either the LHS or the RHS are Zero, the result is zero.
1937 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1938 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1940 // Output known-1 bits are only known if set in both the LHS & RHS.
1941 KnownOne &= KnownOne2;
1942 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1943 KnownZero |= KnownZero2;
1944 break;
1945 case ISD::OR:
1946 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1947 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1949 // Output known-0 bits are only known if clear in both the LHS & RHS.
1950 KnownZero &= KnownZero2;
1951 // Output known-1 are known to be set if set in either the LHS | RHS.
1952 KnownOne |= KnownOne2;
1953 break;
1954 case ISD::XOR: {
1955 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1956 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1958 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1959 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1960 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1961 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1962 KnownZero = KnownZeroOut;
1963 break;
1964 }
1965 case ISD::MUL: {
1966 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1967 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1969 // If low bits are zero in either operand, output low known-0 bits.
1970 // Also compute a conserative estimate for high known-0 bits.
1971 // More trickiness is possible, but this is sufficient for the
1972 // interesting case of alignment computation.
1973 KnownOne.clearAllBits();
1974 unsigned TrailZ = KnownZero.countTrailingOnes() +
1975 KnownZero2.countTrailingOnes();
1976 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1977 KnownZero2.countLeadingOnes(),
1978 BitWidth) - BitWidth;
1980 TrailZ = std::min(TrailZ, BitWidth);
1981 LeadZ = std::min(LeadZ, BitWidth);
1982 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1983 APInt::getHighBitsSet(BitWidth, LeadZ);
1984 break;
1985 }
1986 case ISD::UDIV: {
1987 // For the purposes of computing leading zeros we can conservatively
1988 // treat a udiv as a logical right shift by the power of 2 known to
1989 // be less than the denominator.
1990 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1991 unsigned LeadZ = KnownZero2.countLeadingOnes();
1993 KnownOne2.clearAllBits();
1994 KnownZero2.clearAllBits();
1995 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1996 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1997 if (RHSUnknownLeadingOnes != BitWidth)
1998 LeadZ = std::min(BitWidth,
1999 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2001 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2002 break;
2003 }
2004 case ISD::SELECT:
2005 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2006 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2008 // Only known if known in both the LHS and RHS.
2009 KnownOne &= KnownOne2;
2010 KnownZero &= KnownZero2;
2011 break;
2012 case ISD::SELECT_CC:
2013 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2014 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2016 // Only known if known in both the LHS and RHS.
2017 KnownOne &= KnownOne2;
2018 KnownZero &= KnownZero2;
2019 break;
2020 case ISD::SADDO:
2021 case ISD::UADDO:
2022 case ISD::SSUBO:
2023 case ISD::USUBO:
2024 case ISD::SMULO:
2025 case ISD::UMULO:
2026 if (Op.getResNo() != 1)
2027 break;
2028 // The boolean result conforms to getBooleanContents.
2029 // If we know the result of a setcc has the top bits zero, use this info.
2030 // We know that we have an integer-based boolean since these operations
2031 // are only available for integer.
2032 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2033 TargetLowering::ZeroOrOneBooleanContent &&
2034 BitWidth > 1)
2035 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2036 break;
2037 case ISD::SETCC:
2038 // If we know the result of a setcc has the top bits zero, use this info.
2039 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2040 TargetLowering::ZeroOrOneBooleanContent &&
2041 BitWidth > 1)
2042 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2043 break;
2044 case ISD::SHL:
2045 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2046 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2047 unsigned ShAmt = SA->getZExtValue();
2049 // If the shift count is an invalid immediate, don't do anything.
2050 if (ShAmt >= BitWidth)
2051 break;
2053 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2054 KnownZero <<= ShAmt;
2055 KnownOne <<= ShAmt;
2056 // low bits known zero.
2057 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2058 }
2059 break;
2060 case ISD::SRL:
2061 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2062 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2063 unsigned ShAmt = SA->getZExtValue();
2065 // If the shift count is an invalid immediate, don't do anything.
2066 if (ShAmt >= BitWidth)
2067 break;
2069 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2070 KnownZero = KnownZero.lshr(ShAmt);
2071 KnownOne = KnownOne.lshr(ShAmt);
2073 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2074 KnownZero |= HighBits; // High bits known zero.
2075 }
2076 break;
2077 case ISD::SRA:
2078 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2079 unsigned ShAmt = SA->getZExtValue();
2081 // If the shift count is an invalid immediate, don't do anything.
2082 if (ShAmt >= BitWidth)
2083 break;
2085 // If any of the demanded bits are produced by the sign extension, we also
2086 // demand the input sign bit.
2087 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2089 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2090 KnownZero = KnownZero.lshr(ShAmt);
2091 KnownOne = KnownOne.lshr(ShAmt);
2093 // Handle the sign bits.
2094 APInt SignBit = APInt::getSignBit(BitWidth);
2095 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2097 if (KnownZero.intersects(SignBit)) {
2098 KnownZero |= HighBits; // New bits are known zero.
2099 } else if (KnownOne.intersects(SignBit)) {
2100 KnownOne |= HighBits; // New bits are known one.
2101 }
2102 }
2103 break;
2104 case ISD::SIGN_EXTEND_INREG: {
2105 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2106 unsigned EBits = EVT.getScalarType().getSizeInBits();
2108 // Sign extension. Compute the demanded bits in the result that are not
2109 // present in the input.
2110 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2112 APInt InSignBit = APInt::getSignBit(EBits);
2113 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2115 // If the sign extended bits are demanded, we know that the sign
2116 // bit is demanded.
2117 InSignBit = InSignBit.zext(BitWidth);
2118 if (NewBits.getBoolValue())
2119 InputDemandedBits |= InSignBit;
2121 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2122 KnownOne &= InputDemandedBits;
2123 KnownZero &= InputDemandedBits;
2125 // If the sign bit of the input is known set or clear, then we know the
2126 // top bits of the result.
2127 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2128 KnownZero |= NewBits;
2129 KnownOne &= ~NewBits;
2130 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2131 KnownOne |= NewBits;
2132 KnownZero &= ~NewBits;
2133 } else { // Input sign bit unknown
2134 KnownZero &= ~NewBits;
2135 KnownOne &= ~NewBits;
2136 }
2137 break;
2138 }
2139 case ISD::CTTZ:
2140 case ISD::CTTZ_ZERO_UNDEF:
2141 case ISD::CTLZ:
2142 case ISD::CTLZ_ZERO_UNDEF:
2143 case ISD::CTPOP: {
2144 unsigned LowBits = Log2_32(BitWidth)+1;
2145 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2146 KnownOne.clearAllBits();
2147 break;
2148 }
2149 case ISD::LOAD: {
2150 LoadSDNode *LD = cast<LoadSDNode>(Op);
2151 // If this is a ZEXTLoad and we are looking at the loaded value.
2152 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2153 EVT VT = LD->getMemoryVT();
2154 unsigned MemBits = VT.getScalarType().getSizeInBits();
2155 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2156 } else if (const MDNode *Ranges = LD->getRanges()) {
2157 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2158 }
2159 break;
2160 }
2161 case ISD::ZERO_EXTEND: {
2162 EVT InVT = Op.getOperand(0).getValueType();
2163 unsigned InBits = InVT.getScalarType().getSizeInBits();
2164 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2165 KnownZero = KnownZero.trunc(InBits);
2166 KnownOne = KnownOne.trunc(InBits);
2167 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2168 KnownZero = KnownZero.zext(BitWidth);
2169 KnownOne = KnownOne.zext(BitWidth);
2170 KnownZero |= NewBits;
2171 break;
2172 }
2173 case ISD::SIGN_EXTEND: {
2174 EVT InVT = Op.getOperand(0).getValueType();
2175 unsigned InBits = InVT.getScalarType().getSizeInBits();
2176 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2178 KnownZero = KnownZero.trunc(InBits);
2179 KnownOne = KnownOne.trunc(InBits);
2180 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2182 // Note if the sign bit is known to be zero or one.
2183 bool SignBitKnownZero = KnownZero.isNegative();
2184 bool SignBitKnownOne = KnownOne.isNegative();
2186 KnownZero = KnownZero.zext(BitWidth);
2187 KnownOne = KnownOne.zext(BitWidth);
2189 // If the sign bit is known zero or one, the top bits match.
2190 if (SignBitKnownZero)
2191 KnownZero |= NewBits;
2192 else if (SignBitKnownOne)
2193 KnownOne |= NewBits;
2194 break;
2195 }
2196 case ISD::ANY_EXTEND: {
2197 EVT InVT = Op.getOperand(0).getValueType();
2198 unsigned InBits = InVT.getScalarType().getSizeInBits();
2199 KnownZero = KnownZero.trunc(InBits);
2200 KnownOne = KnownOne.trunc(InBits);
2201 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2202 KnownZero = KnownZero.zext(BitWidth);
2203 KnownOne = KnownOne.zext(BitWidth);
2204 break;
2205 }
2206 case ISD::TRUNCATE: {
2207 EVT InVT = Op.getOperand(0).getValueType();
2208 unsigned InBits = InVT.getScalarType().getSizeInBits();
2209 KnownZero = KnownZero.zext(InBits);
2210 KnownOne = KnownOne.zext(InBits);
2211 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2212 KnownZero = KnownZero.trunc(BitWidth);
2213 KnownOne = KnownOne.trunc(BitWidth);
2214 break;
2215 }
2216 case ISD::AssertZext: {
2217 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2218 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2219 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2220 KnownZero |= (~InMask);
2221 KnownOne &= (~KnownZero);
2222 break;
2223 }
2224 case ISD::FGETSIGN:
2225 // All bits are zero except the low bit.
2226 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2227 break;
2229 case ISD::SUB: {
2230 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2231 // We know that the top bits of C-X are clear if X contains less bits
2232 // than C (i.e. no wrap-around can happen). For example, 20-X is
2233 // positive if we can prove that X is >= 0 and < 16.
2234 if (CLHS->getAPIntValue().isNonNegative()) {
2235 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2236 // NLZ can't be BitWidth with no sign bit
2237 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2238 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2240 // If all of the MaskV bits are known to be zero, then we know the
2241 // output top bits are zero, because we now know that the output is
2242 // from [0-C].
2243 if ((KnownZero2 & MaskV) == MaskV) {
2244 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2245 // Top bits known zero.
2246 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2247 }
2248 }
2249 }
2250 }
2251 // fall through
2252 case ISD::ADD:
2253 case ISD::ADDE: {
2254 // Output known-0 bits are known if clear or set in both the low clear bits
2255 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2256 // low 3 bits clear.
2257 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2258 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2260 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2261 KnownZeroOut = std::min(KnownZeroOut,
2262 KnownZero2.countTrailingOnes());
2264 if (Op.getOpcode() == ISD::ADD) {
2265 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2266 break;
2267 }
2269 // With ADDE, a carry bit may be added in, so we can only use this
2270 // information if we know (at least) that the low two bits are clear. We
2271 // then return to the caller that the low bit is unknown but that other bits
2272 // are known zero.
2273 if (KnownZeroOut >= 2) // ADDE
2274 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2275 break;
2276 }
2277 case ISD::SREM:
2278 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2279 const APInt &RA = Rem->getAPIntValue().abs();
2280 if (RA.isPowerOf2()) {
2281 APInt LowBits = RA - 1;
2282 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2284 // The low bits of the first operand are unchanged by the srem.
2285 KnownZero = KnownZero2 & LowBits;
2286 KnownOne = KnownOne2 & LowBits;
2288 // If the first operand is non-negative or has all low bits zero, then
2289 // the upper bits are all zero.
2290 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2291 KnownZero |= ~LowBits;
2293 // If the first operand is negative and not all low bits are zero, then
2294 // the upper bits are all one.
2295 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2296 KnownOne |= ~LowBits;
2297 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2298 }
2299 }
2300 break;
2301 case ISD::UREM: {
2302 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2303 const APInt &RA = Rem->getAPIntValue();
2304 if (RA.isPowerOf2()) {
2305 APInt LowBits = (RA - 1);
2306 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2308 // The upper bits are all zero, the lower ones are unchanged.
2309 KnownZero = KnownZero2 | ~LowBits;
2310 KnownOne = KnownOne2 & LowBits;
2311 break;
2312 }
2313 }
2315 // Since the result is less than or equal to either operand, any leading
2316 // zero bits in either operand must also exist in the result.
2317 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2318 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2320 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2321 KnownZero2.countLeadingOnes());
2322 KnownOne.clearAllBits();
2323 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2324 break;
2325 }
2326 case ISD::FrameIndex:
2327 case ISD::TargetFrameIndex:
2328 if (unsigned Align = InferPtrAlignment(Op)) {
2329 // The low bits are known zero if the pointer is aligned.
2330 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2331 break;
2332 }
2333 break;
2335 default:
2336 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2337 break;
2338 // Fallthrough
2339 case ISD::INTRINSIC_WO_CHAIN:
2340 case ISD::INTRINSIC_W_CHAIN:
2341 case ISD::INTRINSIC_VOID:
2342 // Allow the target to implement this method for its nodes.
2343 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2344 break;
2345 }
2347 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2348 }
2350 /// ComputeNumSignBits - Return the number of times the sign bit of the
2351 /// register is replicated into the other bits. We know that at least 1 bit
2352 /// is always equal to the sign bit (itself), but other cases can give us
2353 /// information. For example, immediately after an "SRA X, 2", we know that
2354 /// the top 3 bits are all equal to each other, so we return 3.
2355 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2356 EVT VT = Op.getValueType();
2357 assert(VT.isInteger() && "Invalid VT!");
2358 unsigned VTBits = VT.getScalarType().getSizeInBits();
2359 unsigned Tmp, Tmp2;
2360 unsigned FirstAnswer = 1;
2362 if (Depth == 6)
2363 return 1; // Limit search depth.
2365 switch (Op.getOpcode()) {
2366 default: break;
2367 case ISD::AssertSext:
2368 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2369 return VTBits-Tmp+1;
2370 case ISD::AssertZext:
2371 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2372 return VTBits-Tmp;
2374 case ISD::Constant: {
2375 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2376 return Val.getNumSignBits();
2377 }
2379 case ISD::SIGN_EXTEND:
2380 Tmp =
2381 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2382 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2384 case ISD::SIGN_EXTEND_INREG:
2385 // Max of the input and what this extends.
2386 Tmp =
2387 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2388 Tmp = VTBits-Tmp+1;
2390 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2391 return std::max(Tmp, Tmp2);
2393 case ISD::SRA:
2394 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395 // SRA X, C -> adds C sign bits.
2396 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397 Tmp += C->getZExtValue();
2398 if (Tmp > VTBits) Tmp = VTBits;
2399 }
2400 return Tmp;
2401 case ISD::SHL:
2402 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2403 // shl destroys sign bits.
2404 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2405 if (C->getZExtValue() >= VTBits || // Bad shift.
2406 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2407 return Tmp - C->getZExtValue();
2408 }
2409 break;
2410 case ISD::AND:
2411 case ISD::OR:
2412 case ISD::XOR: // NOT is handled here.
2413 // Logical binary ops preserve the number of sign bits at the worst.
2414 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2415 if (Tmp != 1) {
2416 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2417 FirstAnswer = std::min(Tmp, Tmp2);
2418 // We computed what we know about the sign bits as our first
2419 // answer. Now proceed to the generic code that uses
2420 // computeKnownBits, and pick whichever answer is better.
2421 }
2422 break;
2424 case ISD::SELECT:
2425 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2426 if (Tmp == 1) return 1; // Early out.
2427 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2428 return std::min(Tmp, Tmp2);
2430 case ISD::SADDO:
2431 case ISD::UADDO:
2432 case ISD::SSUBO:
2433 case ISD::USUBO:
2434 case ISD::SMULO:
2435 case ISD::UMULO:
2436 if (Op.getResNo() != 1)
2437 break;
2438 // The boolean result conforms to getBooleanContents. Fall through.
2439 // If setcc returns 0/-1, all bits are sign bits.
2440 // We know that we have an integer-based boolean since these operations
2441 // are only available for integer.
2442 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2443 TargetLowering::ZeroOrNegativeOneBooleanContent)
2444 return VTBits;
2445 break;
2446 case ISD::SETCC:
2447 // If setcc returns 0/-1, all bits are sign bits.
2448 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2449 TargetLowering::ZeroOrNegativeOneBooleanContent)
2450 return VTBits;
2451 break;
2452 case ISD::ROTL:
2453 case ISD::ROTR:
2454 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2455 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2457 // Handle rotate right by N like a rotate left by 32-N.
2458 if (Op.getOpcode() == ISD::ROTR)
2459 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2461 // If we aren't rotating out all of the known-in sign bits, return the
2462 // number that are left. This handles rotl(sext(x), 1) for example.
2463 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2464 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2465 }
2466 break;
2467 case ISD::ADD:
2468 // Add can have at most one carry bit. Thus we know that the output
2469 // is, at worst, one more bit than the inputs.
2470 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471 if (Tmp == 1) return 1; // Early out.
2473 // Special case decrementing a value (ADD X, -1):
2474 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2475 if (CRHS->isAllOnesValue()) {
2476 APInt KnownZero, KnownOne;
2477 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2479 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2480 // sign bits set.
2481 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2482 return VTBits;
2484 // If we are subtracting one from a positive number, there is no carry
2485 // out of the result.
2486 if (KnownZero.isNegative())
2487 return Tmp;
2488 }
2490 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2491 if (Tmp2 == 1) return 1;
2492 return std::min(Tmp, Tmp2)-1;
2494 case ISD::SUB:
2495 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2496 if (Tmp2 == 1) return 1;
2498 // Handle NEG.
2499 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2500 if (CLHS->isNullValue()) {
2501 APInt KnownZero, KnownOne;
2502 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2503 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2504 // sign bits set.
2505 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2506 return VTBits;
2508 // If the input is known to be positive (the sign bit is known clear),
2509 // the output of the NEG has the same number of sign bits as the input.
2510 if (KnownZero.isNegative())
2511 return Tmp2;
2513 // Otherwise, we treat this like a SUB.
2514 }
2516 // Sub can have at most one carry bit. Thus we know that the output
2517 // is, at worst, one more bit than the inputs.
2518 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2519 if (Tmp == 1) return 1; // Early out.
2520 return std::min(Tmp, Tmp2)-1;
2521 case ISD::TRUNCATE:
2522 // FIXME: it's tricky to do anything useful for this, but it is an important
2523 // case for targets like X86.
2524 break;
2525 }
2527 // If we are looking at the loaded value of the SDNode.
2528 if (Op.getResNo() == 0) {
2529 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2530 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2531 unsigned ExtType = LD->getExtensionType();
2532 switch (ExtType) {
2533 default: break;
2534 case ISD::SEXTLOAD: // '17' bits known
2535 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2536 return VTBits-Tmp+1;
2537 case ISD::ZEXTLOAD: // '16' bits known
2538 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2539 return VTBits-Tmp;
2540 }
2541 }
2542 }
2544 // Allow the target to implement this method for its nodes.
2545 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2546 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2547 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2548 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2549 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2550 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2551 }
2553 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2554 // use this information.
2555 APInt KnownZero, KnownOne;
2556 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2558 APInt Mask;
2559 if (KnownZero.isNegative()) { // sign bit is 0
2560 Mask = KnownZero;
2561 } else if (KnownOne.isNegative()) { // sign bit is 1;
2562 Mask = KnownOne;
2563 } else {
2564 // Nothing known.
2565 return FirstAnswer;
2566 }
2568 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2569 // the number of identical bits in the top of the input value.
2570 Mask = ~Mask;
2571 Mask <<= Mask.getBitWidth()-VTBits;
2572 // Return # leading zeros. We use 'min' here in case Val was zero before
2573 // shifting. We don't want to return '64' as for an i32 "0".
2574 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2575 }
2577 /// isBaseWithConstantOffset - Return true if the specified operand is an
2578 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2579 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2580 /// semantics as an ADD. This handles the equivalence:
2581 /// X|Cst == X+Cst iff X&Cst = 0.
2582 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2583 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2584 !isa<ConstantSDNode>(Op.getOperand(1)))
2585 return false;
2587 if (Op.getOpcode() == ISD::OR &&
2588 !MaskedValueIsZero(Op.getOperand(0),
2589 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2590 return false;
2592 return true;
2593 }
2596 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2597 // If we're told that NaNs won't happen, assume they won't.
2598 if (getTarget().Options.NoNaNsFPMath)
2599 return true;
2601 // If the value is a constant, we can obviously see if it is a NaN or not.
2602 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2603 return !C->getValueAPF().isNaN();
2605 // TODO: Recognize more cases here.
2607 return false;
2608 }
2610 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2611 // If the value is a constant, we can obviously see if it is a zero or not.
2612 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2613 return !C->isZero();
2615 // TODO: Recognize more cases here.
2616 switch (Op.getOpcode()) {
2617 default: break;
2618 case ISD::OR:
2619 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2620 return !C->isNullValue();
2621 break;
2622 }
2624 return false;
2625 }
2627 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2628 // Check the obvious case.
2629 if (A == B) return true;
2631 // For for negative and positive zero.
2632 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2633 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2634 if (CA->isZero() && CB->isZero()) return true;
2636 // Otherwise they may not be equal.
2637 return false;
2638 }
2640 /// getNode - Gets or creates the specified node.
2641 ///
2642 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2643 FoldingSetNodeID ID;
2644 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2645 void *IP = nullptr;
2646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2647 return SDValue(E, 0);
2649 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2650 DL.getDebugLoc(), getVTList(VT));
2651 CSEMap.InsertNode(N, IP);
2653 InsertNode(N);
2654 return SDValue(N, 0);
2655 }
2657 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2658 EVT VT, SDValue Operand) {
2659 // Constant fold unary operations with an integer constant operand. Even
2660 // opaque constant will be folded, because the folding of unary operations
2661 // doesn't create new constants with different values. Nevertheless, the
2662 // opaque flag is preserved during folding to prevent future folding with
2663 // other constants.
2664 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2665 const APInt &Val = C->getAPIntValue();
2666 switch (Opcode) {
2667 default: break;
2668 case ISD::SIGN_EXTEND:
2669 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2670 C->isTargetOpcode(), C->isOpaque());
2671 case ISD::ANY_EXTEND:
2672 case ISD::ZERO_EXTEND:
2673 case ISD::TRUNCATE:
2674 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2675 C->isTargetOpcode(), C->isOpaque());
2676 case ISD::UINT_TO_FP:
2677 case ISD::SINT_TO_FP: {
2678 APFloat apf(EVTToAPFloatSemantics(VT),
2679 APInt::getNullValue(VT.getSizeInBits()));
2680 (void)apf.convertFromAPInt(Val,
2681 Opcode==ISD::SINT_TO_FP,
2682 APFloat::rmNearestTiesToEven);
2683 return getConstantFP(apf, VT);
2684 }
2685 case ISD::BITCAST:
2686 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2687 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2688 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2689 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2690 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2691 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2692 break;
2693 case ISD::BSWAP:
2694 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2695 C->isOpaque());
2696 case ISD::CTPOP:
2697 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2698 C->isOpaque());
2699 case ISD::CTLZ:
2700 case ISD::CTLZ_ZERO_UNDEF:
2701 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2702 C->isOpaque());
2703 case ISD::CTTZ:
2704 case ISD::CTTZ_ZERO_UNDEF:
2705 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2706 C->isOpaque());
2707 }
2708 }
2710 // Constant fold unary operations with a floating point constant operand.
2711 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2712 APFloat V = C->getValueAPF(); // make copy
2713 switch (Opcode) {
2714 case ISD::FNEG:
2715 V.changeSign();
2716 return getConstantFP(V, VT);
2717 case ISD::FABS:
2718 V.clearSign();
2719 return getConstantFP(V, VT);
2720 case ISD::FCEIL: {
2721 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2722 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2723 return getConstantFP(V, VT);
2724 break;
2725 }
2726 case ISD::FTRUNC: {
2727 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2728 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2729 return getConstantFP(V, VT);
2730 break;
2731 }
2732 case ISD::FFLOOR: {
2733 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2734 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2735 return getConstantFP(V, VT);
2736 break;
2737 }
2738 case ISD::FP_EXTEND: {
2739 bool ignored;
2740 // This can return overflow, underflow, or inexact; we don't care.
2741 // FIXME need to be more flexible about rounding mode.
2742 (void)V.convert(EVTToAPFloatSemantics(VT),
2743 APFloat::rmNearestTiesToEven, &ignored);
2744 return getConstantFP(V, VT);
2745 }
2746 case ISD::FP_TO_SINT:
2747 case ISD::FP_TO_UINT: {
2748 integerPart x[2];
2749 bool ignored;
2750 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2751 // FIXME need to be more flexible about rounding mode.
2752 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2753 Opcode==ISD::FP_TO_SINT,
2754 APFloat::rmTowardZero, &ignored);
2755 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2756 break;
2757 APInt api(VT.getSizeInBits(), x);
2758 return getConstant(api, VT);
2759 }
2760 case ISD::BITCAST:
2761 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2762 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2763 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2764 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2765 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2766 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2767 break;
2768 }
2769 }
2771 // Constant fold unary operations with a vector integer operand.
2772 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2773 if (BV->isConstant()) {
2774 switch (Opcode) {
2775 default:
2776 // FIXME: Entirely reasonable to perform folding of other unary
2777 // operations here as the need arises.
2778 break;
2779 case ISD::UINT_TO_FP:
2780 case ISD::SINT_TO_FP: {
2781 SmallVector<SDValue, 8> Ops;
2782 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2783 SDValue OpN = BV->getOperand(i);
2784 // Let the above scalar folding handle the conversion of each
2785 // element.
2786 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2787 OpN);
2788 Ops.push_back(OpN);
2789 }
2790 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2791 }
2792 }
2793 }
2794 }
2796 unsigned OpOpcode = Operand.getNode()->getOpcode();
2797 switch (Opcode) {
2798 case ISD::TokenFactor:
2799 case ISD::MERGE_VALUES:
2800 case ISD::CONCAT_VECTORS:
2801 return Operand; // Factor, merge or concat of one node? No need.
2802 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2803 case ISD::FP_EXTEND:
2804 assert(VT.isFloatingPoint() &&
2805 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2806 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2807 assert((!VT.isVector() ||
2808 VT.getVectorNumElements() ==
2809 Operand.getValueType().getVectorNumElements()) &&
2810 "Vector element count mismatch!");
2811 if (Operand.getOpcode() == ISD::UNDEF)
2812 return getUNDEF(VT);
2813 break;
2814 case ISD::SIGN_EXTEND:
2815 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2816 "Invalid SIGN_EXTEND!");
2817 if (Operand.getValueType() == VT) return Operand; // noop extension
2818 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2819 "Invalid sext node, dst < src!");
2820 assert((!VT.isVector() ||
2821 VT.getVectorNumElements() ==
2822 Operand.getValueType().getVectorNumElements()) &&
2823 "Vector element count mismatch!");
2824 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2825 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2826 else if (OpOpcode == ISD::UNDEF)
2827 // sext(undef) = 0, because the top bits will all be the same.
2828 return getConstant(0, VT);
2829 break;
2830 case ISD::ZERO_EXTEND:
2831 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2832 "Invalid ZERO_EXTEND!");
2833 if (Operand.getValueType() == VT) return Operand; // noop extension
2834 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2835 "Invalid zext node, dst < src!");
2836 assert((!VT.isVector() ||
2837 VT.getVectorNumElements() ==
2838 Operand.getValueType().getVectorNumElements()) &&
2839 "Vector element count mismatch!");
2840 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2841 return getNode(ISD::ZERO_EXTEND, DL, VT,
2842 Operand.getNode()->getOperand(0));
2843 else if (OpOpcode == ISD::UNDEF)
2844 // zext(undef) = 0, because the top bits will be zero.
2845 return getConstant(0, VT);
2846 break;
2847 case ISD::ANY_EXTEND:
2848 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2849 "Invalid ANY_EXTEND!");
2850 if (Operand.getValueType() == VT) return Operand; // noop extension
2851 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2852 "Invalid anyext node, dst < src!");
2853 assert((!VT.isVector() ||
2854 VT.getVectorNumElements() ==
2855 Operand.getValueType().getVectorNumElements()) &&
2856 "Vector element count mismatch!");
2858 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2859 OpOpcode == ISD::ANY_EXTEND)
2860 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2861 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2862 else if (OpOpcode == ISD::UNDEF)
2863 return getUNDEF(VT);
2865 // (ext (trunx x)) -> x
2866 if (OpOpcode == ISD::TRUNCATE) {
2867 SDValue OpOp = Operand.getNode()->getOperand(0);
2868 if (OpOp.getValueType() == VT)
2869 return OpOp;
2870 }
2871 break;
2872 case ISD::TRUNCATE:
2873 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2874 "Invalid TRUNCATE!");
2875 if (Operand.getValueType() == VT) return Operand; // noop truncate
2876 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2877 "Invalid truncate node, src < dst!");
2878 assert((!VT.isVector() ||
2879 VT.getVectorNumElements() ==
2880 Operand.getValueType().getVectorNumElements()) &&
2881 "Vector element count mismatch!");
2882 if (OpOpcode == ISD::TRUNCATE)
2883 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2884 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2885 OpOpcode == ISD::ANY_EXTEND) {
2886 // If the source is smaller than the dest, we still need an extend.
2887 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2888 .bitsLT(VT.getScalarType()))
2889 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2890 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2891 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2892 return Operand.getNode()->getOperand(0);
2893 }
2894 if (OpOpcode == ISD::UNDEF)
2895 return getUNDEF(VT);
2896 break;
2897 case ISD::BITCAST:
2898 // Basic sanity checking.
2899 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2900 && "Cannot BITCAST between types of different sizes!");
2901 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2902 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2903 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2904 if (OpOpcode == ISD::UNDEF)
2905 return getUNDEF(VT);
2906 break;
2907 case ISD::SCALAR_TO_VECTOR:
2908 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2909 (VT.getVectorElementType() == Operand.getValueType() ||
2910 (VT.getVectorElementType().isInteger() &&
2911 Operand.getValueType().isInteger() &&
2912 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2913 "Illegal SCALAR_TO_VECTOR node!");
2914 if (OpOpcode == ISD::UNDEF)
2915 return getUNDEF(VT);
2916 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2917 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2918 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2919 Operand.getConstantOperandVal(1) == 0 &&
2920 Operand.getOperand(0).getValueType() == VT)
2921 return Operand.getOperand(0);
2922 break;
2923 case ISD::FNEG:
2924 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2925 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2926 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2927 Operand.getNode()->getOperand(0));
2928 if (OpOpcode == ISD::FNEG) // --X -> X
2929 return Operand.getNode()->getOperand(0);
2930 break;
2931 case ISD::FABS:
2932 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2933 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2934 break;
2935 }
2937 SDNode *N;
2938 SDVTList VTs = getVTList(VT);
2939 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2940 FoldingSetNodeID ID;
2941 SDValue Ops[1] = { Operand };
2942 AddNodeIDNode(ID, Opcode, VTs, Ops);
2943 void *IP = nullptr;
2944 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2945 return SDValue(E, 0);
2947 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2948 DL.getDebugLoc(), VTs, Operand);
2949 CSEMap.InsertNode(N, IP);
2950 } else {
2951 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2952 DL.getDebugLoc(), VTs, Operand);
2953 }
2955 InsertNode(N);
2956 return SDValue(N, 0);
2957 }
2959 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2960 SDNode *Cst1, SDNode *Cst2) {
2961 // If the opcode is a target-specific ISD node, there's nothing we can
2962 // do here and the operand rules may not line up with the below, so
2963 // bail early.
2964 if (Opcode >= ISD::BUILTIN_OP_END)
2965 return SDValue();
2967 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2968 SmallVector<SDValue, 4> Outputs;
2969 EVT SVT = VT.getScalarType();
2971 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2972 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2973 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2974 return SDValue();
2976 if (Scalar1 && Scalar2)
2977 // Scalar instruction.
2978 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2979 else {
2980 // For vectors extract each constant element into Inputs so we can constant
2981 // fold them individually.
2982 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2983 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2984 if (!BV1 || !BV2)
2985 return SDValue();
2987 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2989 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2990 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2991 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2992 if (!V1 || !V2) // Not a constant, bail.
2993 return SDValue();
2995 if (V1->isOpaque() || V2->isOpaque())
2996 return SDValue();
2998 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2999 // FIXME: This is valid and could be handled by truncating the APInts.
3000 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3001 return SDValue();
3003 Inputs.push_back(std::make_pair(V1, V2));
3004 }
3005 }
3007 // We have a number of constant values, constant fold them element by element.
3008 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3009 const APInt &C1 = Inputs[I].first->getAPIntValue();
3010 const APInt &C2 = Inputs[I].second->getAPIntValue();
3012 switch (Opcode) {
3013 case ISD::ADD:
3014 Outputs.push_back(getConstant(C1 + C2, SVT));
3015 break;
3016 case ISD::SUB:
3017 Outputs.push_back(getConstant(C1 - C2, SVT));
3018 break;
3019 case ISD::MUL:
3020 Outputs.push_back(getConstant(C1 * C2, SVT));
3021 break;
3022 case ISD::UDIV:
3023 if (!C2.getBoolValue())
3024 return SDValue();
3025 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3026 break;
3027 case ISD::UREM:
3028 if (!C2.getBoolValue())
3029 return SDValue();
3030 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3031 break;
3032 case ISD::SDIV:
3033 if (!C2.getBoolValue())
3034 return SDValue();
3035 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3036 break;
3037 case ISD::SREM:
3038 if (!C2.getBoolValue())
3039 return SDValue();
3040 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3041 break;
3042 case ISD::AND:
3043 Outputs.push_back(getConstant(C1 & C2, SVT));
3044 break;
3045 case ISD::OR:
3046 Outputs.push_back(getConstant(C1 | C2, SVT));
3047 break;
3048 case ISD::XOR:
3049 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3050 break;
3051 case ISD::SHL:
3052 Outputs.push_back(getConstant(C1 << C2, SVT));
3053 break;
3054 case ISD::SRL:
3055 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3056 break;
3057 case ISD::SRA:
3058 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3059 break;
3060 case ISD::ROTL:
3061 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3062 break;
3063 case ISD::ROTR:
3064 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3065 break;
3066 default:
3067 return SDValue();
3068 }
3069 }
3071 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3072 "Expected a scalar or vector!"));
3074 // Handle the scalar case first.
3075 if (!VT.isVector())
3076 return Outputs.back();
3078 // We may have a vector type but a scalar result. Create a splat.
3079 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3081 // Build a big vector out of the scalar elements we generated.
3082 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3083 }
3085 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3086 SDValue N2, bool nuw, bool nsw, bool exact) {
3087 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3088 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3089 switch (Opcode) {
3090 default: break;
3091 case ISD::TokenFactor:
3092 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3093 N2.getValueType() == MVT::Other && "Invalid token factor!");
3094 // Fold trivial token factors.
3095 if (N1.getOpcode() == ISD::EntryToken) return N2;
3096 if (N2.getOpcode() == ISD::EntryToken) return N1;
3097 if (N1 == N2) return N1;
3098 break;
3099 case ISD::CONCAT_VECTORS:
3100 // Concat of UNDEFs is UNDEF.
3101 if (N1.getOpcode() == ISD::UNDEF &&
3102 N2.getOpcode() == ISD::UNDEF)
3103 return getUNDEF(VT);
3105 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3106 // one big BUILD_VECTOR.
3107 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3108 N2.getOpcode() == ISD::BUILD_VECTOR) {
3109 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3110 N1.getNode()->op_end());
3111 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3112 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3113 }
3114 break;
3115 case ISD::AND:
3116 assert(VT.isInteger() && "This operator does not apply to FP types!");
3117 assert(N1.getValueType() == N2.getValueType() &&
3118 N1.getValueType() == VT && "Binary operator types must match!");
3119 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3120 // worth handling here.
3121 if (N2C && N2C->isNullValue())
3122 return N2;
3123 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3124 return N1;
3125 break;
3126 case ISD::OR:
3127 case ISD::XOR:
3128 case ISD::ADD:
3129 case ISD::SUB:
3130 assert(VT.isInteger() && "This operator does not apply to FP types!");
3131 assert(N1.getValueType() == N2.getValueType() &&
3132 N1.getValueType() == VT && "Binary operator types must match!");
3133 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3134 // it's worth handling here.
3135 if (N2C && N2C->isNullValue())
3136 return N1;
3137 break;
3138 case ISD::UDIV:
3139 case ISD::UREM:
3140 case ISD::MULHU:
3141 case ISD::MULHS:
3142 case ISD::MUL:
3143 case ISD::SDIV:
3144 case ISD::SREM:
3145 assert(VT.isInteger() && "This operator does not apply to FP types!");
3146 assert(N1.getValueType() == N2.getValueType() &&
3147 N1.getValueType() == VT && "Binary operator types must match!");
3148 break;
3149 case ISD::FADD:
3150 case ISD::FSUB:
3151 case ISD::FMUL:
3152 case ISD::FDIV:
3153 case ISD::FREM:
3154 if (getTarget().Options.UnsafeFPMath) {
3155 if (Opcode == ISD::FADD) {
3156 // 0+x --> x
3157 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3158 if (CFP->getValueAPF().isZero())
3159 return N2;
3160 // x+0 --> x
3161 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3162 if (CFP->getValueAPF().isZero())
3163 return N1;
3164 } else if (Opcode == ISD::FSUB) {
3165 // x-0 --> x
3166 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3167 if (CFP->getValueAPF().isZero())
3168 return N1;
3169 } else if (Opcode == ISD::FMUL) {
3170 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3171 SDValue V = N2;
3173 // If the first operand isn't the constant, try the second
3174 if (!CFP) {
3175 CFP = dyn_cast<ConstantFPSDNode>(N2);
3176 V = N1;
3177 }
3179 if (CFP) {
3180 // 0*x --> 0
3181 if (CFP->isZero())
3182 return SDValue(CFP,0);
3183 // 1*x --> x
3184 if (CFP->isExactlyValue(1.0))
3185 return V;
3186 }
3187 }
3188 }
3189 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3190 assert(N1.getValueType() == N2.getValueType() &&
3191 N1.getValueType() == VT && "Binary operator types must match!");
3192 break;
3193 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3194 assert(N1.getValueType() == VT &&
3195 N1.getValueType().isFloatingPoint() &&
3196 N2.getValueType().isFloatingPoint() &&
3197 "Invalid FCOPYSIGN!");
3198 break;
3199 case ISD::SHL:
3200 case ISD::SRA:
3201 case ISD::SRL:
3202 case ISD::ROTL:
3203 case ISD::ROTR:
3204 assert(VT == N1.getValueType() &&
3205 "Shift operators return type must be the same as their first arg");
3206 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3207 "Shifts only work on integers");
3208 assert((!VT.isVector() || VT == N2.getValueType()) &&
3209 "Vector shift amounts must be in the same as their first arg");
3210 // Verify that the shift amount VT is bit enough to hold valid shift
3211 // amounts. This catches things like trying to shift an i1024 value by an
3212 // i8, which is easy to fall into in generic code that uses
3213 // TLI.getShiftAmount().
3214 assert(N2.getValueType().getSizeInBits() >=
3215 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3216 "Invalid use of small shift amount with oversized value!");
3218 // Always fold shifts of i1 values so the code generator doesn't need to
3219 // handle them. Since we know the size of the shift has to be less than the
3220 // size of the value, the shift/rotate count is guaranteed to be zero.
3221 if (VT == MVT::i1)
3222 return N1;
3223 if (N2C && N2C->isNullValue())
3224 return N1;
3225 break;
3226 case ISD::FP_ROUND_INREG: {
3227 EVT EVT = cast<VTSDNode>(N2)->getVT();
3228 assert(VT == N1.getValueType() && "Not an inreg round!");
3229 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3230 "Cannot FP_ROUND_INREG integer types");
3231 assert(EVT.isVector() == VT.isVector() &&
3232 "FP_ROUND_INREG type should be vector iff the operand "
3233 "type is vector!");
3234 assert((!EVT.isVector() ||
3235 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3236 "Vector element counts must match in FP_ROUND_INREG");
3237 assert(EVT.bitsLE(VT) && "Not rounding down!");
3238 (void)EVT;
3239 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3240 break;
3241 }
3242 case ISD::FP_ROUND:
3243 assert(VT.isFloatingPoint() &&
3244 N1.getValueType().isFloatingPoint() &&
3245 VT.bitsLE(N1.getValueType()) &&
3246 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3247 if (N1.getValueType() == VT) return N1; // noop conversion.
3248 break;
3249 case ISD::AssertSext:
3250 case ISD::AssertZext: {
3251 EVT EVT = cast<VTSDNode>(N2)->getVT();
3252 assert(VT == N1.getValueType() && "Not an inreg extend!");
3253 assert(VT.isInteger() && EVT.isInteger() &&
3254 "Cannot *_EXTEND_INREG FP types");
3255 assert(!EVT.isVector() &&
3256 "AssertSExt/AssertZExt type should be the vector element type "
3257 "rather than the vector type!");
3258 assert(EVT.bitsLE(VT) && "Not extending!");
3259 if (VT == EVT) return N1; // noop assertion.
3260 break;
3261 }
3262 case ISD::SIGN_EXTEND_INREG: {
3263 EVT EVT = cast<VTSDNode>(N2)->getVT();
3264 assert(VT == N1.getValueType() && "Not an inreg extend!");
3265 assert(VT.isInteger() && EVT.isInteger() &&
3266 "Cannot *_EXTEND_INREG FP types");
3267 assert(EVT.isVector() == VT.isVector() &&
3268 "SIGN_EXTEND_INREG type should be vector iff the operand "
3269 "type is vector!");
3270 assert((!EVT.isVector() ||
3271 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3272 "Vector element counts must match in SIGN_EXTEND_INREG");
3273 assert(EVT.bitsLE(VT) && "Not extending!");
3274 if (EVT == VT) return N1; // Not actually extending
3276 if (N1C) {
3277 APInt Val = N1C->getAPIntValue();
3278 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3279 Val <<= Val.getBitWidth()-FromBits;
3280 Val = Val.ashr(Val.getBitWidth()-FromBits);
3281 return getConstant(Val, VT);
3282 }
3283 break;
3284 }
3285 case ISD::EXTRACT_VECTOR_ELT:
3286 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3287 if (N1.getOpcode() == ISD::UNDEF)
3288 return getUNDEF(VT);
3290 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3291 // expanding copies of large vectors from registers.
3292 if (N2C &&
3293 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3294 N1.getNumOperands() > 0) {
3295 unsigned Factor =
3296 N1.getOperand(0).getValueType().getVectorNumElements();
3297 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3298 N1.getOperand(N2C->getZExtValue() / Factor),
3299 getConstant(N2C->getZExtValue() % Factor,
3300 N2.getValueType()));
3301 }
3303 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3304 // expanding large vector constants.
3305 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3306 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3308 if (VT != Elt.getValueType())
3309 // If the vector element type is not legal, the BUILD_VECTOR operands
3310 // are promoted and implicitly truncated, and the result implicitly
3311 // extended. Make that explicit here.
3312 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3314 return Elt;
3315 }
3317 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3318 // operations are lowered to scalars.
3319 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3320 // If the indices are the same, return the inserted element else
3321 // if the indices are known different, extract the element from
3322 // the original vector.
3323 SDValue N1Op2 = N1.getOperand(2);
3324 &nb