LLVM  mainline
SelectionDAG.cpp
Go to the documentation of this file.
00001 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the SelectionDAG class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/CodeGen/SelectionDAG.h"
00015 #include "SDNodeDbgValue.h"
00016 #include "llvm/ADT/SetVector.h"
00017 #include "llvm/ADT/SmallPtrSet.h"
00018 #include "llvm/ADT/SmallSet.h"
00019 #include "llvm/ADT/SmallVector.h"
00020 #include "llvm/ADT/StringExtras.h"
00021 #include "llvm/Analysis/ValueTracking.h"
00022 #include "llvm/CodeGen/MachineBasicBlock.h"
00023 #include "llvm/CodeGen/MachineConstantPool.h"
00024 #include "llvm/CodeGen/MachineFrameInfo.h"
00025 #include "llvm/CodeGen/MachineModuleInfo.h"
00026 #include "llvm/IR/CallingConv.h"
00027 #include "llvm/IR/Constants.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/DebugInfo.h"
00030 #include "llvm/IR/DerivedTypes.h"
00031 #include "llvm/IR/Function.h"
00032 #include "llvm/IR/GlobalAlias.h"
00033 #include "llvm/IR/GlobalVariable.h"
00034 #include "llvm/IR/Intrinsics.h"
00035 #include "llvm/Support/CommandLine.h"
00036 #include "llvm/Support/Debug.h"
00037 #include "llvm/Support/ErrorHandling.h"
00038 #include "llvm/Support/ManagedStatic.h"
00039 #include "llvm/Support/MathExtras.h"
00040 #include "llvm/Support/Mutex.h"
00041 #include "llvm/Support/raw_ostream.h"
00042 #include "llvm/Target/TargetInstrInfo.h"
00043 #include "llvm/Target/TargetIntrinsicInfo.h"
00044 #include "llvm/Target/TargetLowering.h"
00045 #include "llvm/Target/TargetMachine.h"
00046 #include "llvm/Target/TargetOptions.h"
00047 #include "llvm/Target/TargetRegisterInfo.h"
00048 #include "llvm/Target/TargetSelectionDAGInfo.h"
00049 #include "llvm/Target/TargetSubtargetInfo.h"
00050 #include <algorithm>
00051 #include <cmath>
00052 #include <utility>
00053 
00054 using namespace llvm;
00055 
00056 /// makeVTList - Return an instance of the SDVTList struct initialized with the
00057 /// specified members.
00058 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
00059   SDVTList Res = {VTs, NumVTs};
00060   return Res;
00061 }
00062 
00063 // Default null implementations of the callbacks.
00064 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
00065 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
00066 
00067 //===----------------------------------------------------------------------===//
00068 //                              ConstantFPSDNode Class
00069 //===----------------------------------------------------------------------===//
00070 
00071 /// isExactlyValue - We don't rely on operator== working on double values, as
00072 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
00073 /// As such, this method can be used to do an exact bit-for-bit comparison of
00074 /// two floating point values.
00075 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
00076   return getValueAPF().bitwiseIsEqual(V);
00077 }
00078 
00079 bool ConstantFPSDNode::isValueValidForType(EVT VT,
00080                                            const APFloat& Val) {
00081   assert(VT.isFloatingPoint() && "Can only convert between FP types");
00082 
00083   // convert modifies in place, so make a copy.
00084   APFloat Val2 = APFloat(Val);
00085   bool losesInfo;
00086   (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
00087                       APFloat::rmNearestTiesToEven,
00088                       &losesInfo);
00089   return !losesInfo;
00090 }
00091 
00092 //===----------------------------------------------------------------------===//
00093 //                              ISD Namespace
00094 //===----------------------------------------------------------------------===//
00095 
00096 /// isBuildVectorAllOnes - Return true if the specified node is a
00097 /// BUILD_VECTOR where all of the elements are ~0 or undef.
00098 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
00099   // Look through a bit convert.
00100   while (N->getOpcode() == ISD::BITCAST)
00101     N = N->getOperand(0).getNode();
00102 
00103   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
00104 
00105   unsigned i = 0, e = N->getNumOperands();
00106 
00107   // Skip over all of the undef values.
00108   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
00109     ++i;
00110 
00111   // Do not accept an all-undef vector.
00112   if (i == e) return false;
00113 
00114   // Do not accept build_vectors that aren't all constants or which have non-~0
00115   // elements. We have to be a bit careful here, as the type of the constant
00116   // may not be the same as the type of the vector elements due to type
00117   // legalization (the elements are promoted to a legal type for the target and
00118   // a vector of a type may be legal when the base element type is not).
00119   // We only want to check enough bits to cover the vector elements, because
00120   // we care if the resultant vector is all ones, not whether the individual
00121   // constants are.
00122   SDValue NotZero = N->getOperand(i);
00123   unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
00124   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
00125     if (CN->getAPIntValue().countTrailingOnes() < EltSize)
00126       return false;
00127   } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
00128     if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
00129       return false;
00130   } else
00131     return false;
00132 
00133   // Okay, we have at least one ~0 value, check to see if the rest match or are
00134   // undefs. Even with the above element type twiddling, this should be OK, as
00135   // the same type legalization should have applied to all the elements.
00136   for (++i; i != e; ++i)
00137     if (N->getOperand(i) != NotZero &&
00138         N->getOperand(i).getOpcode() != ISD::UNDEF)
00139       return false;
00140   return true;
00141 }
00142 
00143 
00144 /// isBuildVectorAllZeros - Return true if the specified node is a
00145 /// BUILD_VECTOR where all of the elements are 0 or undef.
00146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
00147   // Look through a bit convert.
00148   while (N->getOpcode() == ISD::BITCAST)
00149     N = N->getOperand(0).getNode();
00150 
00151   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
00152 
00153   bool IsAllUndef = true;
00154   for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
00155     if (N->getOperand(i).getOpcode() == ISD::UNDEF)
00156       continue;
00157     IsAllUndef = false;
00158     // Do not accept build_vectors that aren't all constants or which have non-0
00159     // elements. We have to be a bit careful here, as the type of the constant
00160     // may not be the same as the type of the vector elements due to type
00161     // legalization (the elements are promoted to a legal type for the target
00162     // and a vector of a type may be legal when the base element type is not).
00163     // We only want to check enough bits to cover the vector elements, because
00164     // we care if the resultant vector is all zeros, not whether the individual
00165     // constants are.
00166     SDValue Zero = N->getOperand(i);
00167     unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
00168     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
00169       if (CN->getAPIntValue().countTrailingZeros() < EltSize)
00170         return false;
00171     } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
00172       if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
00173         return false;
00174     } else
00175       return false;
00176   }
00177 
00178   // Do not accept an all-undef vector.
00179   if (IsAllUndef)
00180     return false;
00181   return true;
00182 }
00183 
00184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
00185 /// all ConstantSDNode or undef.
00186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
00187   if (N->getOpcode() != ISD::BUILD_VECTOR)
00188     return false;
00189 
00190   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00191     SDValue Op = N->getOperand(i);
00192     if (Op.getOpcode() == ISD::UNDEF)
00193       continue;
00194     if (!isa<ConstantSDNode>(Op))
00195       return false;
00196   }
00197   return true;
00198 }
00199 
00200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
00201 /// all ConstantFPSDNode or undef.
00202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
00203   if (N->getOpcode() != ISD::BUILD_VECTOR)
00204     return false;
00205 
00206   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00207     SDValue Op = N->getOperand(i);
00208     if (Op.getOpcode() == ISD::UNDEF)
00209       continue;
00210     if (!isa<ConstantFPSDNode>(Op))
00211       return false;
00212   }
00213   return true;
00214 }
00215 
00216 /// isScalarToVector - Return true if the specified node is a
00217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
00218 /// element is not an undef.
00219 bool ISD::isScalarToVector(const SDNode *N) {
00220   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
00221     return true;
00222 
00223   if (N->getOpcode() != ISD::BUILD_VECTOR)
00224     return false;
00225   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
00226     return false;
00227   unsigned NumElems = N->getNumOperands();
00228   if (NumElems == 1)
00229     return false;
00230   for (unsigned i = 1; i < NumElems; ++i) {
00231     SDValue V = N->getOperand(i);
00232     if (V.getOpcode() != ISD::UNDEF)
00233       return false;
00234   }
00235   return true;
00236 }
00237 
00238 /// allOperandsUndef - Return true if the node has at least one operand
00239 /// and all operands of the specified node are ISD::UNDEF.
00240 bool ISD::allOperandsUndef(const SDNode *N) {
00241   // Return false if the node has no operands.
00242   // This is "logically inconsistent" with the definition of "all" but
00243   // is probably the desired behavior.
00244   if (N->getNumOperands() == 0)
00245     return false;
00246 
00247   for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
00248     if (N->getOperand(i).getOpcode() != ISD::UNDEF)
00249       return false;
00250 
00251   return true;
00252 }
00253 
00254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
00255   switch (ExtType) {
00256   case ISD::EXTLOAD:
00257     return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
00258   case ISD::SEXTLOAD:
00259     return ISD::SIGN_EXTEND;
00260   case ISD::ZEXTLOAD:
00261     return ISD::ZERO_EXTEND;
00262   default:
00263     break;
00264   }
00265 
00266   llvm_unreachable("Invalid LoadExtType");
00267 }
00268 
00269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
00270 /// when given the operation for (X op Y).
00271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
00272   // To perform this operation, we just need to swap the L and G bits of the
00273   // operation.
00274   unsigned OldL = (Operation >> 2) & 1;
00275   unsigned OldG = (Operation >> 1) & 1;
00276   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
00277                        (OldL << 1) |       // New G bit
00278                        (OldG << 2));       // New L bit.
00279 }
00280 
00281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
00282 /// 'op' is a valid SetCC operation.
00283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
00284   unsigned Operation = Op;
00285   if (isInteger)
00286     Operation ^= 7;   // Flip L, G, E bits, but not U.
00287   else
00288     Operation ^= 15;  // Flip all of the condition bits.
00289 
00290   if (Operation > ISD::SETTRUE2)
00291     Operation &= ~8;  // Don't let N and U bits get set.
00292 
00293   return ISD::CondCode(Operation);
00294 }
00295 
00296 
00297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
00298 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
00299 /// if the operation does not depend on the sign of the input (setne and seteq).
00300 static int isSignedOp(ISD::CondCode Opcode) {
00301   switch (Opcode) {
00302   default: llvm_unreachable("Illegal integer setcc operation!");
00303   case ISD::SETEQ:
00304   case ISD::SETNE: return 0;
00305   case ISD::SETLT:
00306   case ISD::SETLE:
00307   case ISD::SETGT:
00308   case ISD::SETGE: return 1;
00309   case ISD::SETULT:
00310   case ISD::SETULE:
00311   case ISD::SETUGT:
00312   case ISD::SETUGE: return 2;
00313   }
00314 }
00315 
00316 /// getSetCCOrOperation - Return the result of a logical OR between different
00317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
00318 /// returns SETCC_INVALID if it is not possible to represent the resultant
00319 /// comparison.
00320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
00321                                        bool isInteger) {
00322   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
00323     // Cannot fold a signed integer setcc with an unsigned integer setcc.
00324     return ISD::SETCC_INVALID;
00325 
00326   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
00327 
00328   // If the N and U bits get set then the resultant comparison DOES suddenly
00329   // care about orderedness, and is true when ordered.
00330   if (Op > ISD::SETTRUE2)
00331     Op &= ~16;     // Clear the U bit if the N bit is set.
00332 
00333   // Canonicalize illegal integer setcc's.
00334   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
00335     Op = ISD::SETNE;
00336 
00337   return ISD::CondCode(Op);
00338 }
00339 
00340 /// getSetCCAndOperation - Return the result of a logical AND between different
00341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
00342 /// function returns zero if it is not possible to represent the resultant
00343 /// comparison.
00344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
00345                                         bool isInteger) {
00346   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
00347     // Cannot fold a signed setcc with an unsigned setcc.
00348     return ISD::SETCC_INVALID;
00349 
00350   // Combine all of the condition bits.
00351   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
00352 
00353   // Canonicalize illegal integer setcc's.
00354   if (isInteger) {
00355     switch (Result) {
00356     default: break;
00357     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
00358     case ISD::SETOEQ:                                 // SETEQ  & SETU[LG]E
00359     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
00360     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
00361     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
00362     }
00363   }
00364 
00365   return Result;
00366 }
00367 
00368 //===----------------------------------------------------------------------===//
00369 //                           SDNode Profile Support
00370 //===----------------------------------------------------------------------===//
00371 
00372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
00373 ///
00374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
00375   ID.AddInteger(OpC);
00376 }
00377 
00378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
00379 /// solely with their pointer.
00380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
00381   ID.AddPointer(VTList.VTs);
00382 }
00383 
00384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
00385 ///
00386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
00387                               ArrayRef<SDValue> Ops) {
00388   for (auto& Op : Ops) {
00389     ID.AddPointer(Op.getNode());
00390     ID.AddInteger(Op.getResNo());
00391   }
00392 }
00393 
00394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
00395 ///
00396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
00397                               ArrayRef<SDUse> Ops) {
00398   for (auto& Op : Ops) {
00399     ID.AddPointer(Op.getNode());
00400     ID.AddInteger(Op.getResNo());
00401   }
00402 }
00403 
00404 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
00405                                   bool exact) {
00406   ID.AddBoolean(nuw);
00407   ID.AddBoolean(nsw);
00408   ID.AddBoolean(exact);
00409 }
00410 
00411 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
00412 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
00413                                   bool nuw, bool nsw, bool exact) {
00414   if (isBinOpWithFlags(Opcode))
00415     AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
00416 }
00417 
00418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
00419                           SDVTList VTList, ArrayRef<SDValue> OpList) {
00420   AddNodeIDOpcode(ID, OpC);
00421   AddNodeIDValueTypes(ID, VTList);
00422   AddNodeIDOperands(ID, OpList);
00423 }
00424 
00425 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
00426 /// the NodeID data.
00427 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
00428   switch (N->getOpcode()) {
00429   case ISD::TargetExternalSymbol:
00430   case ISD::ExternalSymbol:
00431     llvm_unreachable("Should only be used on nodes with operands");
00432   default: break;  // Normal nodes don't need extra info.
00433   case ISD::TargetConstant:
00434   case ISD::Constant: {
00435     const ConstantSDNode *C = cast<ConstantSDNode>(N);
00436     ID.AddPointer(C->getConstantIntValue());
00437     ID.AddBoolean(C->isOpaque());
00438     break;
00439   }
00440   case ISD::TargetConstantFP:
00441   case ISD::ConstantFP: {
00442     ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
00443     break;
00444   }
00445   case ISD::TargetGlobalAddress:
00446   case ISD::GlobalAddress:
00447   case ISD::TargetGlobalTLSAddress:
00448   case ISD::GlobalTLSAddress: {
00449     const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
00450     ID.AddPointer(GA->getGlobal());
00451     ID.AddInteger(GA->getOffset());
00452     ID.AddInteger(GA->getTargetFlags());
00453     ID.AddInteger(GA->getAddressSpace());
00454     break;
00455   }
00456   case ISD::BasicBlock:
00457     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
00458     break;
00459   case ISD::Register:
00460     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
00461     break;
00462   case ISD::RegisterMask:
00463     ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
00464     break;
00465   case ISD::SRCVALUE:
00466     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
00467     break;
00468   case ISD::FrameIndex:
00469   case ISD::TargetFrameIndex:
00470     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
00471     break;
00472   case ISD::JumpTable:
00473   case ISD::TargetJumpTable:
00474     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
00475     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
00476     break;
00477   case ISD::ConstantPool:
00478   case ISD::TargetConstantPool: {
00479     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
00480     ID.AddInteger(CP->getAlignment());
00481     ID.AddInteger(CP->getOffset());
00482     if (CP->isMachineConstantPoolEntry())
00483       CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
00484     else
00485       ID.AddPointer(CP->getConstVal());
00486     ID.AddInteger(CP->getTargetFlags());
00487     break;
00488   }
00489   case ISD::TargetIndex: {
00490     const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
00491     ID.AddInteger(TI->getIndex());
00492     ID.AddInteger(TI->getOffset());
00493     ID.AddInteger(TI->getTargetFlags());
00494     break;
00495   }
00496   case ISD::LOAD: {
00497     const LoadSDNode *LD = cast<LoadSDNode>(N);
00498     ID.AddInteger(LD->getMemoryVT().getRawBits());
00499     ID.AddInteger(LD->getRawSubclassData());
00500     ID.AddInteger(LD->getPointerInfo().getAddrSpace());
00501     break;
00502   }
00503   case ISD::STORE: {
00504     const StoreSDNode *ST = cast<StoreSDNode>(N);
00505     ID.AddInteger(ST->getMemoryVT().getRawBits());
00506     ID.AddInteger(ST->getRawSubclassData());
00507     ID.AddInteger(ST->getPointerInfo().getAddrSpace());
00508     break;
00509   }
00510   case ISD::SDIV:
00511   case ISD::UDIV:
00512   case ISD::SRA:
00513   case ISD::SRL:
00514   case ISD::MUL:
00515   case ISD::ADD:
00516   case ISD::SUB:
00517   case ISD::SHL: {
00518     const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
00519     AddBinaryNodeIDCustom(
00520         ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
00521         BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
00522     break;
00523   }
00524   case ISD::ATOMIC_CMP_SWAP:
00525   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
00526   case ISD::ATOMIC_SWAP:
00527   case ISD::ATOMIC_LOAD_ADD:
00528   case ISD::ATOMIC_LOAD_SUB:
00529   case ISD::ATOMIC_LOAD_AND:
00530   case ISD::ATOMIC_LOAD_OR:
00531   case ISD::ATOMIC_LOAD_XOR:
00532   case ISD::ATOMIC_LOAD_NAND:
00533   case ISD::ATOMIC_LOAD_MIN:
00534   case ISD::ATOMIC_LOAD_MAX:
00535   case ISD::ATOMIC_LOAD_UMIN:
00536   case ISD::ATOMIC_LOAD_UMAX:
00537   case ISD::ATOMIC_LOAD:
00538   case ISD::ATOMIC_STORE: {
00539     const AtomicSDNode *AT = cast<AtomicSDNode>(N);
00540     ID.AddInteger(AT->getMemoryVT().getRawBits());
00541     ID.AddInteger(AT->getRawSubclassData());
00542     ID.AddInteger(AT->getPointerInfo().getAddrSpace());
00543     break;
00544   }
00545   case ISD::PREFETCH: {
00546     const MemSDNode *PF = cast<MemSDNode>(N);
00547     ID.AddInteger(PF->getPointerInfo().getAddrSpace());
00548     break;
00549   }
00550   case ISD::VECTOR_SHUFFLE: {
00551     const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
00552     for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
00553          i != e; ++i)
00554       ID.AddInteger(SVN->getMaskElt(i));
00555     break;
00556   }
00557   case ISD::TargetBlockAddress:
00558   case ISD::BlockAddress: {
00559     const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
00560     ID.AddPointer(BA->getBlockAddress());
00561     ID.AddInteger(BA->getOffset());
00562     ID.AddInteger(BA->getTargetFlags());
00563     break;
00564   }
00565   } // end switch (N->getOpcode())
00566 
00567   // Target specific memory nodes could also have address spaces to check.
00568   if (N->isTargetMemoryOpcode())
00569     ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
00570 }
00571 
00572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
00573 /// data.
00574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
00575   AddNodeIDOpcode(ID, N->getOpcode());
00576   // Add the return value info.
00577   AddNodeIDValueTypes(ID, N->getVTList());
00578   // Add the operand info.
00579   AddNodeIDOperands(ID, N->ops());
00580 
00581   // Handle SDNode leafs with special info.
00582   AddNodeIDCustom(ID, N);
00583 }
00584 
00585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
00586 /// the CSE map that carries volatility, temporalness, indexing mode, and
00587 /// extension/truncation information.
00588 ///
00589 static inline unsigned
00590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
00591                      bool isNonTemporal, bool isInvariant) {
00592   assert((ConvType & 3) == ConvType &&
00593          "ConvType may not require more than 2 bits!");
00594   assert((AM & 7) == AM &&
00595          "AM may not require more than 3 bits!");
00596   return ConvType |
00597          (AM << 2) |
00598          (isVolatile << 5) |
00599          (isNonTemporal << 6) |
00600          (isInvariant << 7);
00601 }
00602 
00603 //===----------------------------------------------------------------------===//
00604 //                              SelectionDAG Class
00605 //===----------------------------------------------------------------------===//
00606 
00607 /// doNotCSE - Return true if CSE should not be performed for this node.
00608 static bool doNotCSE(SDNode *N) {
00609   if (N->getValueType(0) == MVT::Glue)
00610     return true; // Never CSE anything that produces a flag.
00611 
00612   switch (N->getOpcode()) {
00613   default: break;
00614   case ISD::HANDLENODE:
00615   case ISD::EH_LABEL:
00616     return true;   // Never CSE these nodes.
00617   }
00618 
00619   // Check that remaining values produced are not flags.
00620   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
00621     if (N->getValueType(i) == MVT::Glue)
00622       return true; // Never CSE anything that produces a flag.
00623 
00624   return false;
00625 }
00626 
00627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
00628 /// SelectionDAG.
00629 void SelectionDAG::RemoveDeadNodes() {
00630   // Create a dummy node (which is not added to allnodes), that adds a reference
00631   // to the root node, preventing it from being deleted.
00632   HandleSDNode Dummy(getRoot());
00633 
00634   SmallVector<SDNode*, 128> DeadNodes;
00635 
00636   // Add all obviously-dead nodes to the DeadNodes worklist.
00637   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
00638     if (I->use_empty())
00639       DeadNodes.push_back(I);
00640 
00641   RemoveDeadNodes(DeadNodes);
00642 
00643   // If the root changed (e.g. it was a dead load, update the root).
00644   setRoot(Dummy.getValue());
00645 }
00646 
00647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
00648 /// given list, and any nodes that become unreachable as a result.
00649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
00650 
00651   // Process the worklist, deleting the nodes and adding their uses to the
00652   // worklist.
00653   while (!DeadNodes.empty()) {
00654     SDNode *N = DeadNodes.pop_back_val();
00655 
00656     for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
00657       DUL->NodeDeleted(N, nullptr);
00658 
00659     // Take the node out of the appropriate CSE map.
00660     RemoveNodeFromCSEMaps(N);
00661 
00662     // Next, brutally remove the operand list.  This is safe to do, as there are
00663     // no cycles in the graph.
00664     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
00665       SDUse &Use = *I++;
00666       SDNode *Operand = Use.getNode();
00667       Use.set(SDValue());
00668 
00669       // Now that we removed this operand, see if there are no uses of it left.
00670       if (Operand->use_empty())
00671         DeadNodes.push_back(Operand);
00672     }
00673 
00674     DeallocateNode(N);
00675   }
00676 }
00677 
00678 void SelectionDAG::RemoveDeadNode(SDNode *N){
00679   SmallVector<SDNode*, 16> DeadNodes(1, N);
00680 
00681   // Create a dummy node that adds a reference to the root node, preventing
00682   // it from being deleted.  (This matters if the root is an operand of the
00683   // dead node.)
00684   HandleSDNode Dummy(getRoot());
00685 
00686   RemoveDeadNodes(DeadNodes);
00687 }
00688 
00689 void SelectionDAG::DeleteNode(SDNode *N) {
00690   // First take this out of the appropriate CSE map.
00691   RemoveNodeFromCSEMaps(N);
00692 
00693   // Finally, remove uses due to operands of this node, remove from the
00694   // AllNodes list, and delete the node.
00695   DeleteNodeNotInCSEMaps(N);
00696 }
00697 
00698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
00699   assert(N != AllNodes.begin() && "Cannot delete the entry node!");
00700   assert(N->use_empty() && "Cannot delete a node that is not dead!");
00701 
00702   // Drop all of the operands and decrement used node's use counts.
00703   N->DropOperands();
00704 
00705   DeallocateNode(N);
00706 }
00707 
00708 void SDDbgInfo::erase(const SDNode *Node) {
00709   DbgValMapType::iterator I = DbgValMap.find(Node);
00710   if (I == DbgValMap.end())
00711     return;
00712   for (auto &Val: I->second)
00713     Val->setIsInvalidated();
00714   DbgValMap.erase(I);
00715 }
00716 
00717 void SelectionDAG::DeallocateNode(SDNode *N) {
00718   if (N->OperandsNeedDelete)
00719     delete[] N->OperandList;
00720 
00721   // Set the opcode to DELETED_NODE to help catch bugs when node
00722   // memory is reallocated.
00723   N->NodeType = ISD::DELETED_NODE;
00724 
00725   NodeAllocator.Deallocate(AllNodes.remove(N));
00726 
00727   // If any of the SDDbgValue nodes refer to this SDNode, invalidate
00728   // them and forget about that node.
00729   DbgInfo->erase(N);
00730 }
00731 
00732 #ifndef NDEBUG
00733 /// VerifySDNode - Sanity check the given SDNode.  Aborts if it is invalid.
00734 static void VerifySDNode(SDNode *N) {
00735   switch (N->getOpcode()) {
00736   default:
00737     break;
00738   case ISD::BUILD_PAIR: {
00739     EVT VT = N->getValueType(0);
00740     assert(N->getNumValues() == 1 && "Too many results!");
00741     assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
00742            "Wrong return type!");
00743     assert(N->getNumOperands() == 2 && "Wrong number of operands!");
00744     assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
00745            "Mismatched operand types!");
00746     assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
00747            "Wrong operand type!");
00748     assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
00749            "Wrong return type size");
00750     break;
00751   }
00752   case ISD::BUILD_VECTOR: {
00753     assert(N->getNumValues() == 1 && "Too many results!");
00754     assert(N->getValueType(0).isVector() && "Wrong return type!");
00755     assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
00756            "Wrong number of operands!");
00757     EVT EltVT = N->getValueType(0).getVectorElementType();
00758     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
00759       assert((I->getValueType() == EltVT ||
00760              (EltVT.isInteger() && I->getValueType().isInteger() &&
00761               EltVT.bitsLE(I->getValueType()))) &&
00762             "Wrong operand type!");
00763       assert(I->getValueType() == N->getOperand(0).getValueType() &&
00764              "Operands must all have the same type");
00765     }
00766     break;
00767   }
00768   }
00769 }
00770 #endif // NDEBUG
00771 
00772 /// \brief Insert a newly allocated node into the DAG.
00773 ///
00774 /// Handles insertion into the all nodes list and CSE map, as well as
00775 /// verification and other common operations when a new node is allocated.
00776 void SelectionDAG::InsertNode(SDNode *N) {
00777   AllNodes.push_back(N);
00778 #ifndef NDEBUG
00779   VerifySDNode(N);
00780 #endif
00781 }
00782 
00783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
00784 /// correspond to it.  This is useful when we're about to delete or repurpose
00785 /// the node.  We don't want future request for structurally identical nodes
00786 /// to return N anymore.
00787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
00788   bool Erased = false;
00789   switch (N->getOpcode()) {
00790   case ISD::HANDLENODE: return false;  // noop.
00791   case ISD::CONDCODE:
00792     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
00793            "Cond code doesn't exist!");
00794     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
00795     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
00796     break;
00797   case ISD::ExternalSymbol:
00798     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
00799     break;
00800   case ISD::TargetExternalSymbol: {
00801     ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
00802     Erased = TargetExternalSymbols.erase(
00803                std::pair<std::string,unsigned char>(ESN->getSymbol(),
00804                                                     ESN->getTargetFlags()));
00805     break;
00806   }
00807   case ISD::VALUETYPE: {
00808     EVT VT = cast<VTSDNode>(N)->getVT();
00809     if (VT.isExtended()) {
00810       Erased = ExtendedValueTypeNodes.erase(VT);
00811     } else {
00812       Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
00813       ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
00814     }
00815     break;
00816   }
00817   default:
00818     // Remove it from the CSE Map.
00819     assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
00820     assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
00821     Erased = CSEMap.RemoveNode(N);
00822     break;
00823   }
00824 #ifndef NDEBUG
00825   // Verify that the node was actually in one of the CSE maps, unless it has a
00826   // flag result (which cannot be CSE'd) or is one of the special cases that are
00827   // not subject to CSE.
00828   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
00829       !N->isMachineOpcode() && !doNotCSE(N)) {
00830     N->dump(this);
00831     dbgs() << "\n";
00832     llvm_unreachable("Node is not in map!");
00833   }
00834 #endif
00835   return Erased;
00836 }
00837 
00838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
00839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
00840 /// node already exists, in which case transfer all its users to the existing
00841 /// node. This transfer can potentially trigger recursive merging.
00842 ///
00843 void
00844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
00845   // For node types that aren't CSE'd, just act as if no identical node
00846   // already exists.
00847   if (!doNotCSE(N)) {
00848     SDNode *Existing = CSEMap.GetOrInsertNode(N);
00849     if (Existing != N) {
00850       // If there was already an existing matching node, use ReplaceAllUsesWith
00851       // to replace the dead one with the existing one.  This can cause
00852       // recursive merging of other unrelated nodes down the line.
00853       ReplaceAllUsesWith(N, Existing);
00854 
00855       // N is now dead. Inform the listeners and delete it.
00856       for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
00857         DUL->NodeDeleted(N, Existing);
00858       DeleteNodeNotInCSEMaps(N);
00859       return;
00860     }
00861   }
00862 
00863   // If the node doesn't already exist, we updated it.  Inform listeners.
00864   for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
00865     DUL->NodeUpdated(N);
00866 }
00867 
00868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00869 /// were replaced with those specified.  If this node is never memoized,
00870 /// return null, otherwise return a pointer to the slot it would take.  If a
00871 /// node already exists with these operands, the slot will be non-null.
00872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
00873                                            void *&InsertPos) {
00874   if (doNotCSE(N))
00875     return nullptr;
00876 
00877   SDValue Ops[] = { Op };
00878   FoldingSetNodeID ID;
00879   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
00880   AddNodeIDCustom(ID, N);
00881   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
00882   return Node;
00883 }
00884 
00885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00886 /// were replaced with those specified.  If this node is never memoized,
00887 /// return null, otherwise return a pointer to the slot it would take.  If a
00888 /// node already exists with these operands, the slot will be non-null.
00889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
00890                                            SDValue Op1, SDValue Op2,
00891                                            void *&InsertPos) {
00892   if (doNotCSE(N))
00893     return nullptr;
00894 
00895   SDValue Ops[] = { Op1, Op2 };
00896   FoldingSetNodeID ID;
00897   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
00898   AddNodeIDCustom(ID, N);
00899   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
00900   return Node;
00901 }
00902 
00903 
00904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
00905 /// were replaced with those specified.  If this node is never memoized,
00906 /// return null, otherwise return a pointer to the slot it would take.  If a
00907 /// node already exists with these operands, the slot will be non-null.
00908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
00909                                            void *&InsertPos) {
00910   if (doNotCSE(N))
00911     return nullptr;
00912 
00913   FoldingSetNodeID ID;
00914   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
00915   AddNodeIDCustom(ID, N);
00916   SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
00917   return Node;
00918 }
00919 
00920 /// getEVTAlignment - Compute the default alignment value for the
00921 /// given type.
00922 ///
00923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
00924   Type *Ty = VT == MVT::iPTR ?
00925                    PointerType::get(Type::getInt8Ty(*getContext()), 0) :
00926                    VT.getTypeForEVT(*getContext());
00927 
00928   return TLI->getDataLayout()->getABITypeAlignment(Ty);
00929 }
00930 
00931 // EntryNode could meaningfully have debug info if we can find it...
00932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
00933     : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
00934       EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
00935       Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
00936       UpdateListeners(nullptr) {
00937   AllNodes.push_back(&EntryNode);
00938   DbgInfo = new SDDbgInfo();
00939 }
00940 
00941 void SelectionDAG::init(MachineFunction &mf) {
00942   MF = &mf;
00943   TLI = getSubtarget().getTargetLowering();
00944   TSI = getSubtarget().getSelectionDAGInfo();
00945   Context = &mf.getFunction()->getContext();
00946 }
00947 
00948 SelectionDAG::~SelectionDAG() {
00949   assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
00950   allnodes_clear();
00951   delete DbgInfo;
00952 }
00953 
00954 void SelectionDAG::allnodes_clear() {
00955   assert(&*AllNodes.begin() == &EntryNode);
00956   AllNodes.remove(AllNodes.begin());
00957   while (!AllNodes.empty())
00958     DeallocateNode(AllNodes.begin());
00959 }
00960 
00961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
00962                                             SDVTList VTs, SDValue N1,
00963                                             SDValue N2, bool nuw, bool nsw,
00964                                             bool exact) {
00965   if (isBinOpWithFlags(Opcode)) {
00966     BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
00967         Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
00968     FN->Flags.setNoUnsignedWrap(nuw);
00969     FN->Flags.setNoSignedWrap(nsw);
00970     FN->Flags.setExact(exact);
00971 
00972     return FN;
00973   }
00974 
00975   BinarySDNode *N = new (NodeAllocator)
00976       BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
00977   return N;
00978 }
00979 
00980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
00981                                           void *&InsertPos) {
00982   SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
00983   if (N) {
00984     switch (N->getOpcode()) {
00985     default: break;
00986     case ISD::Constant:
00987     case ISD::ConstantFP:
00988       llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
00989                        "debug location.  Use another overload.");
00990     }
00991   }
00992   return N;
00993 }
00994 
00995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
00996                                           DebugLoc DL, void *&InsertPos) {
00997   SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
00998   if (N) {
00999     switch (N->getOpcode()) {
01000     default: break; // Process only regular (non-target) constant nodes.
01001     case ISD::Constant:
01002     case ISD::ConstantFP:
01003       // Erase debug location from the node if the node is used at several
01004       // different places to do not propagate one location to all uses as it
01005       // leads to incorrect debug info.
01006       if (N->getDebugLoc() != DL)
01007         N->setDebugLoc(DebugLoc());
01008       break;
01009     }
01010   }
01011   return N;
01012 }
01013 
01014 void SelectionDAG::clear() {
01015   allnodes_clear();
01016   OperandAllocator.Reset();
01017   CSEMap.clear();
01018 
01019   ExtendedValueTypeNodes.clear();
01020   ExternalSymbols.clear();
01021   TargetExternalSymbols.clear();
01022   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
01023             static_cast<CondCodeSDNode*>(nullptr));
01024   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
01025             static_cast<SDNode*>(nullptr));
01026 
01027   EntryNode.UseList = nullptr;
01028   AllNodes.push_back(&EntryNode);
01029   Root = getEntryNode();
01030   DbgInfo->clear();
01031 }
01032 
01033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
01034   return VT.bitsGT(Op.getValueType()) ?
01035     getNode(ISD::ANY_EXTEND, DL, VT, Op) :
01036     getNode(ISD::TRUNCATE, DL, VT, Op);
01037 }
01038 
01039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
01040   return VT.bitsGT(Op.getValueType()) ?
01041     getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
01042     getNode(ISD::TRUNCATE, DL, VT, Op);
01043 }
01044 
01045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
01046   return VT.bitsGT(Op.getValueType()) ?
01047     getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
01048     getNode(ISD::TRUNCATE, DL, VT, Op);
01049 }
01050 
01051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
01052                                         EVT OpVT) {
01053   if (VT.bitsLE(Op.getValueType()))
01054     return getNode(ISD::TRUNCATE, SL, VT, Op);
01055 
01056   TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
01057   return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
01058 }
01059 
01060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
01061   assert(!VT.isVector() &&
01062          "getZeroExtendInReg should use the vector element type instead of "
01063          "the vector type!");
01064   if (Op.getValueType() == VT) return Op;
01065   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
01066   APInt Imm = APInt::getLowBitsSet(BitWidth,
01067                                    VT.getSizeInBits());
01068   return getNode(ISD::AND, DL, Op.getValueType(), Op,
01069                  getConstant(Imm, DL, Op.getValueType()));
01070 }
01071 
01072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
01073   assert(VT.isVector() && "This DAG node is restricted to vector types.");
01074   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
01075          "The sizes of the input and result must match in order to perform the "
01076          "extend in-register.");
01077   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
01078          "The destination vector type must have fewer lanes than the input.");
01079   return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
01080 }
01081 
01082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
01083   assert(VT.isVector() && "This DAG node is restricted to vector types.");
01084   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
01085          "The sizes of the input and result must match in order to perform the "
01086          "extend in-register.");
01087   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
01088          "The destination vector type must have fewer lanes than the input.");
01089   return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
01090 }
01091 
01092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
01093   assert(VT.isVector() && "This DAG node is restricted to vector types.");
01094   assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
01095          "The sizes of the input and result must match in order to perform the "
01096          "extend in-register.");
01097   assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
01098          "The destination vector type must have fewer lanes than the input.");
01099   return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
01100 }
01101 
01102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
01103 ///
01104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
01105   EVT EltVT = VT.getScalarType();
01106   SDValue NegOne =
01107     getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
01108   return getNode(ISD::XOR, DL, VT, Val, NegOne);
01109 }
01110 
01111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
01112   EVT EltVT = VT.getScalarType();
01113   SDValue TrueValue;
01114   switch (TLI->getBooleanContents(VT)) {
01115     case TargetLowering::ZeroOrOneBooleanContent:
01116     case TargetLowering::UndefinedBooleanContent:
01117       TrueValue = getConstant(1, DL, VT);
01118       break;
01119     case TargetLowering::ZeroOrNegativeOneBooleanContent:
01120       TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
01121                               VT);
01122       break;
01123   }
01124   return getNode(ISD::XOR, DL, VT, Val, TrueValue);
01125 }
01126 
01127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
01128                                   bool isO) {
01129   EVT EltVT = VT.getScalarType();
01130   assert((EltVT.getSizeInBits() >= 64 ||
01131          (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
01132          "getConstant with a uint64_t value that doesn't fit in the type!");
01133   return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
01134 }
01135 
01136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
01137                                   bool isO)
01138 {
01139   return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
01140 }
01141 
01142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
01143                                   bool isT, bool isO) {
01144   assert(VT.isInteger() && "Cannot create FP integer constant!");
01145 
01146   EVT EltVT = VT.getScalarType();
01147   const ConstantInt *Elt = &Val;
01148 
01149   // In some cases the vector type is legal but the element type is illegal and
01150   // needs to be promoted, for example v8i8 on ARM.  In this case, promote the
01151   // inserted value (the type does not need to match the vector element type).
01152   // Any extra bits introduced will be truncated away.
01153   if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
01154       TargetLowering::TypePromoteInteger) {
01155    EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
01156    APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
01157    Elt = ConstantInt::get(*getContext(), NewVal);
01158   }
01159   // In other cases the element type is illegal and needs to be expanded, for
01160   // example v2i64 on MIPS32. In this case, find the nearest legal type, split
01161   // the value into n parts and use a vector type with n-times the elements.
01162   // Then bitcast to the type requested.
01163   // Legalizing constants too early makes the DAGCombiner's job harder so we
01164   // only legalize if the DAG tells us we must produce legal types.
01165   else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
01166            TLI->getTypeAction(*getContext(), EltVT) ==
01167            TargetLowering::TypeExpandInteger) {
01168     APInt NewVal = Elt->getValue();
01169     EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
01170     unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
01171     unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
01172     EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
01173 
01174     // Check the temporary vector is the correct size. If this fails then
01175     // getTypeToTransformTo() probably returned a type whose size (in bits)
01176     // isn't a power-of-2 factor of the requested type size.
01177     assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
01178 
01179     SmallVector<SDValue, 2> EltParts;
01180     for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
01181       EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
01182                                            .trunc(ViaEltSizeInBits), DL,
01183                                      ViaEltVT, isT, isO));
01184     }
01185 
01186     // EltParts is currently in little endian order. If we actually want
01187     // big-endian order then reverse it now.
01188     if (TLI->isBigEndian())
01189       std::reverse(EltParts.begin(), EltParts.end());
01190 
01191     // The elements must be reversed when the element order is different
01192     // to the endianness of the elements (because the BITCAST is itself a
01193     // vector shuffle in this situation). However, we do not need any code to
01194     // perform this reversal because getConstant() is producing a vector
01195     // splat.
01196     // This situation occurs in MIPS MSA.
01197 
01198     SmallVector<SDValue, 8> Ops;
01199     for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
01200       Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
01201 
01202     SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
01203                              getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
01204                                      Ops));
01205     return Result;
01206   }
01207 
01208   assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
01209          "APInt size does not match type size!");
01210   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
01211   FoldingSetNodeID ID;
01212   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
01213   ID.AddPointer(Elt);
01214   ID.AddBoolean(isO);
01215   void *IP = nullptr;
01216   SDNode *N = nullptr;
01217   if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
01218     if (!VT.isVector())
01219       return SDValue(N, 0);
01220 
01221   if (!N) {
01222     N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
01223                                            EltVT);
01224     CSEMap.InsertNode(N, IP);
01225     InsertNode(N);
01226   }
01227 
01228   SDValue Result(N, 0);
01229   if (VT.isVector()) {
01230     SmallVector<SDValue, 8> Ops;
01231     Ops.assign(VT.getVectorNumElements(), Result);
01232     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
01233   }
01234   return Result;
01235 }
01236 
01237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
01238   return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
01239 }
01240 
01241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
01242                                     bool isTarget) {
01243   return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
01244 }
01245 
01246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
01247                                     bool isTarget){
01248   assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
01249 
01250   EVT EltVT = VT.getScalarType();
01251 
01252   // Do the map lookup using the actual bit pattern for the floating point
01253   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
01254   // we don't have issues with SNANs.
01255   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
01256   FoldingSetNodeID ID;
01257   AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
01258   ID.AddPointer(&V);
01259   void *IP = nullptr;
01260   SDNode *N = nullptr;
01261   if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
01262     if (!VT.isVector())
01263       return SDValue(N, 0);
01264 
01265   if (!N) {
01266     N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
01267                                              EltVT);
01268     CSEMap.InsertNode(N, IP);
01269     InsertNode(N);
01270   }
01271 
01272   SDValue Result(N, 0);
01273   if (VT.isVector()) {
01274     SmallVector<SDValue, 8> Ops;
01275     Ops.assign(VT.getVectorNumElements(), Result);
01276     Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
01277   }
01278   return Result;
01279 }
01280 
01281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
01282                                     bool isTarget) {
01283   EVT EltVT = VT.getScalarType();
01284   if (EltVT==MVT::f32)
01285     return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
01286   else if (EltVT==MVT::f64)
01287     return getConstantFP(APFloat(Val), DL, VT, isTarget);
01288   else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
01289            EltVT==MVT::f16) {
01290     bool ignored;
01291     APFloat apf = APFloat(Val);
01292     apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
01293                 &ignored);
01294     return getConstantFP(apf, DL, VT, isTarget);
01295   } else
01296     llvm_unreachable("Unsupported type in getConstantFP");
01297 }
01298 
01299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
01300                                        EVT VT, int64_t Offset,
01301                                        bool isTargetGA,
01302                                        unsigned char TargetFlags) {
01303   assert((TargetFlags == 0 || isTargetGA) &&
01304          "Cannot set target flags on target-independent globals");
01305 
01306   // Truncate (with sign-extension) the offset value to the pointer size.
01307   unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
01308   if (BitWidth < 64)
01309     Offset = SignExtend64(Offset, BitWidth);
01310 
01311   unsigned Opc;
01312   if (GV->isThreadLocal())
01313     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
01314   else
01315     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
01316 
01317   FoldingSetNodeID ID;
01318   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01319   ID.AddPointer(GV);
01320   ID.AddInteger(Offset);
01321   ID.AddInteger(TargetFlags);
01322   ID.AddInteger(GV->getType()->getAddressSpace());
01323   void *IP = nullptr;
01324   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
01325     return SDValue(E, 0);
01326 
01327   SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
01328                                                       DL.getDebugLoc(), GV, VT,
01329                                                       Offset, TargetFlags);
01330   CSEMap.InsertNode(N, IP);
01331     InsertNode(N);
01332   return SDValue(N, 0);
01333 }
01334 
01335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
01336   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
01337   FoldingSetNodeID ID;
01338   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01339   ID.AddInteger(FI);
01340   void *IP = nullptr;
01341   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01342     return SDValue(E, 0);
01343 
01344   SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
01345   CSEMap.InsertNode(N, IP);
01346   InsertNode(N);
01347   return SDValue(N, 0);
01348 }
01349 
01350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
01351                                    unsigned char TargetFlags) {
01352   assert((TargetFlags == 0 || isTarget) &&
01353          "Cannot set target flags on target-independent jump tables");
01354   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
01355   FoldingSetNodeID ID;
01356   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01357   ID.AddInteger(JTI);
01358   ID.AddInteger(TargetFlags);
01359   void *IP = nullptr;
01360   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01361     return SDValue(E, 0);
01362 
01363   SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
01364                                                   TargetFlags);
01365   CSEMap.InsertNode(N, IP);
01366   InsertNode(N);
01367   return SDValue(N, 0);
01368 }
01369 
01370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
01371                                       unsigned Alignment, int Offset,
01372                                       bool isTarget,
01373                                       unsigned char TargetFlags) {
01374   assert((TargetFlags == 0 || isTarget) &&
01375          "Cannot set target flags on target-independent globals");
01376   if (Alignment == 0)
01377     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
01378   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
01379   FoldingSetNodeID ID;
01380   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01381   ID.AddInteger(Alignment);
01382   ID.AddInteger(Offset);
01383   ID.AddPointer(C);
01384   ID.AddInteger(TargetFlags);
01385   void *IP = nullptr;
01386   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01387     return SDValue(E, 0);
01388 
01389   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
01390                                                      Alignment, TargetFlags);
01391   CSEMap.InsertNode(N, IP);
01392   InsertNode(N);
01393   return SDValue(N, 0);
01394 }
01395 
01396 
01397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
01398                                       unsigned Alignment, int Offset,
01399                                       bool isTarget,
01400                                       unsigned char TargetFlags) {
01401   assert((TargetFlags == 0 || isTarget) &&
01402          "Cannot set target flags on target-independent globals");
01403   if (Alignment == 0)
01404     Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
01405   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
01406   FoldingSetNodeID ID;
01407   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01408   ID.AddInteger(Alignment);
01409   ID.AddInteger(Offset);
01410   C->addSelectionDAGCSEId(ID);
01411   ID.AddInteger(TargetFlags);
01412   void *IP = nullptr;
01413   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01414     return SDValue(E, 0);
01415 
01416   SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
01417                                                      Alignment, TargetFlags);
01418   CSEMap.InsertNode(N, IP);
01419   InsertNode(N);
01420   return SDValue(N, 0);
01421 }
01422 
01423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
01424                                      unsigned char TargetFlags) {
01425   FoldingSetNodeID ID;
01426   AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
01427   ID.AddInteger(Index);
01428   ID.AddInteger(Offset);
01429   ID.AddInteger(TargetFlags);
01430   void *IP = nullptr;
01431   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01432     return SDValue(E, 0);
01433 
01434   SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
01435                                                     TargetFlags);
01436   CSEMap.InsertNode(N, IP);
01437   InsertNode(N);
01438   return SDValue(N, 0);
01439 }
01440 
01441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
01442   FoldingSetNodeID ID;
01443   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
01444   ID.AddPointer(MBB);
01445   void *IP = nullptr;
01446   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01447     return SDValue(E, 0);
01448 
01449   SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
01450   CSEMap.InsertNode(N, IP);
01451   InsertNode(N);
01452   return SDValue(N, 0);
01453 }
01454 
01455 SDValue SelectionDAG::getValueType(EVT VT) {
01456   if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
01457       ValueTypeNodes.size())
01458     ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
01459 
01460   SDNode *&N = VT.isExtended() ?
01461     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
01462 
01463   if (N) return SDValue(N, 0);
01464   N = new (NodeAllocator) VTSDNode(VT);
01465   InsertNode(N);
01466   return SDValue(N, 0);
01467 }
01468 
01469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
01470   SDNode *&N = ExternalSymbols[Sym];
01471   if (N) return SDValue(N, 0);
01472   N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
01473   InsertNode(N);
01474   return SDValue(N, 0);
01475 }
01476 
01477 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
01478                                               unsigned char TargetFlags) {
01479   SDNode *&N =
01480     TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
01481                                                                TargetFlags)];
01482   if (N) return SDValue(N, 0);
01483   N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
01484   InsertNode(N);
01485   return SDValue(N, 0);
01486 }
01487 
01488 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
01489   if ((unsigned)Cond >= CondCodeNodes.size())
01490     CondCodeNodes.resize(Cond+1);
01491 
01492   if (!CondCodeNodes[Cond]) {
01493     CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
01494     CondCodeNodes[Cond] = N;
01495     InsertNode(N);
01496   }
01497 
01498   return SDValue(CondCodeNodes[Cond], 0);
01499 }
01500 
01501 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
01502 // the shuffle mask M that point at N1 to point at N2, and indices that point
01503 // N2 to point at N1.
01504 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
01505   std::swap(N1, N2);
01506   ShuffleVectorSDNode::commuteMask(M);
01507 }
01508 
01509 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
01510                                        SDValue N2, const int *Mask) {
01511   assert(VT == N1.getValueType() && VT == N2.getValueType() &&
01512          "Invalid VECTOR_SHUFFLE");
01513 
01514   // Canonicalize shuffle undef, undef -> undef
01515   if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
01516     return getUNDEF(VT);
01517 
01518   // Validate that all indices in Mask are within the range of the elements
01519   // input to the shuffle.
01520   unsigned NElts = VT.getVectorNumElements();
01521   SmallVector<int, 8> MaskVec;
01522   for (unsigned i = 0; i != NElts; ++i) {
01523     assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
01524     MaskVec.push_back(Mask[i]);
01525   }
01526 
01527   // Canonicalize shuffle v, v -> v, undef
01528   if (N1 == N2) {
01529     N2 = getUNDEF(VT);
01530     for (unsigned i = 0; i != NElts; ++i)
01531       if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
01532   }
01533 
01534   // Canonicalize shuffle undef, v -> v, undef.  Commute the shuffle mask.
01535   if (N1.getOpcode() == ISD::UNDEF)
01536     commuteShuffle(N1, N2, MaskVec);
01537 
01538   // If shuffling a splat, try to blend the splat instead. We do this here so
01539   // that even when this arises during lowering we don't have to re-handle it.
01540   auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
01541     BitVector UndefElements;
01542     SDValue Splat = BV->getSplatValue(&UndefElements);
01543     if (!Splat)
01544       return;
01545 
01546     for (int i = 0; i < (int)NElts; ++i) {
01547       if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
01548         continue;
01549 
01550       // If this input comes from undef, mark it as such.
01551       if (UndefElements[MaskVec[i] - Offset]) {
01552         MaskVec[i] = -1;
01553         continue;
01554       }
01555 
01556       // If we can blend a non-undef lane, use that instead.
01557       if (!UndefElements[i])
01558         MaskVec[i] = i + Offset;
01559     }
01560   };
01561   if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
01562     BlendSplat(N1BV, 0);
01563   if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
01564     BlendSplat(N2BV, NElts);
01565 
01566   // Canonicalize all index into lhs, -> shuffle lhs, undef
01567   // Canonicalize all index into rhs, -> shuffle rhs, undef
01568   bool AllLHS = true, AllRHS = true;
01569   bool N2Undef = N2.getOpcode() == ISD::UNDEF;
01570   for (unsigned i = 0; i != NElts; ++i) {
01571     if (MaskVec[i] >= (int)NElts) {
01572       if (N2Undef)
01573         MaskVec[i] = -1;
01574       else
01575         AllLHS = false;
01576     } else if (MaskVec[i] >= 0) {
01577       AllRHS = false;
01578     }
01579   }
01580   if (AllLHS && AllRHS)
01581     return getUNDEF(VT);
01582   if (AllLHS && !N2Undef)
01583     N2 = getUNDEF(VT);
01584   if (AllRHS) {
01585     N1 = getUNDEF(VT);
01586     commuteShuffle(N1, N2, MaskVec);
01587   }
01588   // Reset our undef status after accounting for the mask.
01589   N2Undef = N2.getOpcode() == ISD::UNDEF;
01590   // Re-check whether both sides ended up undef.
01591   if (N1.getOpcode() == ISD::UNDEF && N2Undef)
01592     return getUNDEF(VT);
01593 
01594   // If Identity shuffle return that node.
01595   bool Identity = true, AllSame = true;
01596   for (unsigned i = 0; i != NElts; ++i) {
01597     if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
01598     if (MaskVec[i] != MaskVec[0]) AllSame = false;
01599   }
01600   if (Identity && NElts)
01601     return N1;
01602 
01603   // Shuffling a constant splat doesn't change the result.
01604   if (N2Undef) {
01605     SDValue V = N1;
01606 
01607     // Look through any bitcasts. We check that these don't change the number
01608     // (and size) of elements and just changes their types.
01609     while (V.getOpcode() == ISD::BITCAST)
01610       V = V->getOperand(0);
01611 
01612     // A splat should always show up as a build vector node.
01613     if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
01614       BitVector UndefElements;
01615       SDValue Splat = BV->getSplatValue(&UndefElements);
01616       // If this is a splat of an undef, shuffling it is also undef.
01617       if (Splat && Splat.getOpcode() == ISD::UNDEF)
01618         return getUNDEF(VT);
01619 
01620       bool SameNumElts =
01621           V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
01622 
01623       // We only have a splat which can skip shuffles if there is a splatted
01624       // value and no undef lanes rearranged by the shuffle.
01625       if (Splat && UndefElements.none()) {
01626         // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
01627         // number of elements match or the value splatted is a zero constant.
01628         if (SameNumElts)
01629           return N1;
01630         if (auto *C = dyn_cast<ConstantSDNode>(Splat))
01631           if (C->isNullValue())
01632             return N1;
01633       }
01634 
01635       // If the shuffle itself creates a splat, build the vector directly.
01636       if (AllSame && SameNumElts) {
01637         const SDValue &Splatted = BV->getOperand(MaskVec[0]);
01638         SmallVector<SDValue, 8> Ops(NElts, Splatted);
01639 
01640         EVT BuildVT = BV->getValueType(0);
01641         SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
01642 
01643         // We may have jumped through bitcasts, so the type of the
01644         // BUILD_VECTOR may not match the type of the shuffle.
01645         if (BuildVT != VT)
01646           NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
01647         return NewBV;
01648       }
01649     }
01650   }
01651 
01652   FoldingSetNodeID ID;
01653   SDValue Ops[2] = { N1, N2 };
01654   AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
01655   for (unsigned i = 0; i != NElts; ++i)
01656     ID.AddInteger(MaskVec[i]);
01657 
01658   void* IP = nullptr;
01659   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
01660     return SDValue(E, 0);
01661 
01662   // Allocate the mask array for the node out of the BumpPtrAllocator, since
01663   // SDNode doesn't have access to it.  This memory will be "leaked" when
01664   // the node is deallocated, but recovered when the NodeAllocator is released.
01665   int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
01666   memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
01667 
01668   ShuffleVectorSDNode *N =
01669     new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
01670                                             dl.getDebugLoc(), N1, N2,
01671                                             MaskAlloc);
01672   CSEMap.InsertNode(N, IP);
01673   InsertNode(N);
01674   return SDValue(N, 0);
01675 }
01676 
01677 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
01678   MVT VT = SV.getSimpleValueType(0);
01679   SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
01680   ShuffleVectorSDNode::commuteMask(MaskVec);
01681 
01682   SDValue Op0 = SV.getOperand(0);
01683   SDValue Op1 = SV.getOperand(1);
01684   return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
01685 }
01686 
01687 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
01688                                        SDValue Val, SDValue DTy,
01689                                        SDValue STy, SDValue Rnd, SDValue Sat,
01690                                        ISD::CvtCode Code) {
01691   // If the src and dest types are the same and the conversion is between
01692   // integer types of the same sign or two floats, no conversion is necessary.
01693   if (DTy == STy &&
01694       (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
01695     return Val;
01696 
01697   FoldingSetNodeID ID;
01698   SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
01699   AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
01700   void* IP = nullptr;
01701   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
01702     return SDValue(E, 0);
01703 
01704   CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
01705                                                            dl.getDebugLoc(),
01706                                                            Ops, Code);
01707   CSEMap.InsertNode(N, IP);
01708   InsertNode(N);
01709   return SDValue(N, 0);
01710 }
01711 
01712 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
01713   FoldingSetNodeID ID;
01714   AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
01715   ID.AddInteger(RegNo);
01716   void *IP = nullptr;
01717   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01718     return SDValue(E, 0);
01719 
01720   SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
01721   CSEMap.InsertNode(N, IP);
01722   InsertNode(N);
01723   return SDValue(N, 0);
01724 }
01725 
01726 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
01727   FoldingSetNodeID ID;
01728   AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
01729   ID.AddPointer(RegMask);
01730   void *IP = nullptr;
01731   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01732     return SDValue(E, 0);
01733 
01734   SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
01735   CSEMap.InsertNode(N, IP);
01736   InsertNode(N);
01737   return SDValue(N, 0);
01738 }
01739 
01740 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
01741   FoldingSetNodeID ID;
01742   SDValue Ops[] = { Root };
01743   AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
01744   ID.AddPointer(Label);
01745   void *IP = nullptr;
01746   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01747     return SDValue(E, 0);
01748 
01749   SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
01750                                                 dl.getDebugLoc(), Root, Label);
01751   CSEMap.InsertNode(N, IP);
01752   InsertNode(N);
01753   return SDValue(N, 0);
01754 }
01755 
01756 
01757 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
01758                                       int64_t Offset,
01759                                       bool isTarget,
01760                                       unsigned char TargetFlags) {
01761   unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
01762 
01763   FoldingSetNodeID ID;
01764   AddNodeIDNode(ID, Opc, getVTList(VT), None);
01765   ID.AddPointer(BA);
01766   ID.AddInteger(Offset);
01767   ID.AddInteger(TargetFlags);
01768   void *IP = nullptr;
01769   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01770     return SDValue(E, 0);
01771 
01772   SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
01773                                                      TargetFlags);
01774   CSEMap.InsertNode(N, IP);
01775   InsertNode(N);
01776   return SDValue(N, 0);
01777 }
01778 
01779 SDValue SelectionDAG::getSrcValue(const Value *V) {
01780   assert((!V || V->getType()->isPointerTy()) &&
01781          "SrcValue is not a pointer?");
01782 
01783   FoldingSetNodeID ID;
01784   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
01785   ID.AddPointer(V);
01786 
01787   void *IP = nullptr;
01788   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01789     return SDValue(E, 0);
01790 
01791   SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
01792   CSEMap.InsertNode(N, IP);
01793   InsertNode(N);
01794   return SDValue(N, 0);
01795 }
01796 
01797 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
01798 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
01799   FoldingSetNodeID ID;
01800   AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
01801   ID.AddPointer(MD);
01802 
01803   void *IP = nullptr;
01804   if (SDNode *E = FindNodeOrInsertPos(ID, IP))
01805     return SDValue(E, 0);
01806 
01807   SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
01808   CSEMap.InsertNode(N, IP);
01809   InsertNode(N);
01810   return SDValue(N, 0);
01811 }
01812 
01813 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
01814 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
01815                                        unsigned SrcAS, unsigned DestAS) {
01816   SDValue Ops[] = {Ptr};
01817   FoldingSetNodeID ID;
01818   AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
01819   ID.AddInteger(SrcAS);
01820   ID.AddInteger(DestAS);
01821 
01822   void *IP = nullptr;
01823   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
01824     return SDValue(E, 0);
01825 
01826   SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
01827                                                       dl.getDebugLoc(),
01828                                                       VT, Ptr, SrcAS, DestAS);
01829   CSEMap.InsertNode(N, IP);
01830   InsertNode(N);
01831   return SDValue(N, 0);
01832 }
01833 
01834 /// getShiftAmountOperand - Return the specified value casted to
01835 /// the target's desired shift amount type.
01836 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
01837   EVT OpTy = Op.getValueType();
01838   EVT ShTy = TLI->getShiftAmountTy(LHSTy);
01839   if (OpTy == ShTy || OpTy.isVector()) return Op;
01840 
01841   ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ?  ISD::TRUNCATE : ISD::ZERO_EXTEND;
01842   return getNode(Opcode, SDLoc(Op), ShTy, Op);
01843 }
01844 
01845 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
01846 /// specified value type.
01847 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
01848   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
01849   unsigned ByteSize = VT.getStoreSize();
01850   Type *Ty = VT.getTypeForEVT(*getContext());
01851   unsigned StackAlign =
01852   std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
01853 
01854   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
01855   return getFrameIndex(FrameIdx, TLI->getPointerTy());
01856 }
01857 
01858 /// CreateStackTemporary - Create a stack temporary suitable for holding
01859 /// either of the specified value types.
01860 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
01861   unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
01862                             VT2.getStoreSizeInBits())/8;
01863   Type *Ty1 = VT1.getTypeForEVT(*getContext());
01864   Type *Ty2 = VT2.getTypeForEVT(*getContext());
01865   const DataLayout *TD = TLI->getDataLayout();
01866   unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
01867                             TD->getPrefTypeAlignment(Ty2));
01868 
01869   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
01870   int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
01871   return getFrameIndex(FrameIdx, TLI->getPointerTy());
01872 }
01873 
01874 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
01875                                 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
01876   // These setcc operations always fold.
01877   switch (Cond) {
01878   default: break;
01879   case ISD::SETFALSE:
01880   case ISD::SETFALSE2: return getConstant(0, dl, VT);
01881   case ISD::SETTRUE:
01882   case ISD::SETTRUE2: {
01883     TargetLowering::BooleanContent Cnt =
01884         TLI->getBooleanContents(N1->getValueType(0));
01885     return getConstant(
01886         Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
01887         VT);
01888   }
01889 
01890   case ISD::SETOEQ:
01891   case ISD::SETOGT:
01892   case ISD::SETOGE:
01893   case ISD::SETOLT:
01894   case ISD::SETOLE:
01895   case ISD::SETONE:
01896   case ISD::SETO:
01897   case ISD::SETUO:
01898   case ISD::SETUEQ:
01899   case ISD::SETUNE:
01900     assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
01901     break;
01902   }
01903 
01904   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
01905     const APInt &C2 = N2C->getAPIntValue();
01906     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
01907       const APInt &C1 = N1C->getAPIntValue();
01908 
01909       switch (Cond) {
01910       default: llvm_unreachable("Unknown integer setcc!");
01911       case ISD::SETEQ:  return getConstant(C1 == C2, dl, VT);
01912       case ISD::SETNE:  return getConstant(C1 != C2, dl, VT);
01913       case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
01914       case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
01915       case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
01916       case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
01917       case ISD::SETLT:  return getConstant(C1.slt(C2), dl, VT);
01918       case ISD::SETGT:  return getConstant(C1.sgt(C2), dl, VT);
01919       case ISD::SETLE:  return getConstant(C1.sle(C2), dl, VT);
01920       case ISD::SETGE:  return getConstant(C1.sge(C2), dl, VT);
01921       }
01922     }
01923   }
01924   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
01925     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
01926       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
01927       switch (Cond) {
01928       default: break;
01929       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
01930                           return getUNDEF(VT);
01931                         // fall through
01932       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
01933       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
01934                           return getUNDEF(VT);
01935                         // fall through
01936       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
01937                                            R==APFloat::cmpLessThan, dl, VT);
01938       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
01939                           return getUNDEF(VT);
01940                         // fall through
01941       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
01942       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
01943                           return getUNDEF(VT);
01944                         // fall through
01945       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
01946       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
01947                           return getUNDEF(VT);
01948                         // fall through
01949       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
01950                                            R==APFloat::cmpEqual, dl, VT);
01951       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
01952                           return getUNDEF(VT);
01953                         // fall through
01954       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
01955                                            R==APFloat::cmpEqual, dl, VT);
01956       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, dl, VT);
01957       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, dl, VT);
01958       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
01959                                            R==APFloat::cmpEqual, dl, VT);
01960       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
01961       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
01962                                            R==APFloat::cmpLessThan, dl, VT);
01963       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
01964                                            R==APFloat::cmpUnordered, dl, VT);
01965       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
01966       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
01967       }
01968     } else {
01969       // Ensure that the constant occurs on the RHS.
01970       ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
01971       MVT CompVT = N1.getValueType().getSimpleVT();
01972       if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
01973         return SDValue();
01974 
01975       return getSetCC(dl, VT, N2, N1, SwappedCond);
01976     }
01977   }
01978 
01979   // Could not fold it.
01980   return SDValue();
01981 }
01982 
01983 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
01984 /// use this predicate to simplify operations downstream.
01985 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
01986   // This predicate is not safe for vector operations.
01987   if (Op.getValueType().isVector())
01988     return false;
01989 
01990   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
01991   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
01992 }
01993 
01994 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
01995 /// this predicate to simplify operations downstream.  Mask is known to be zero
01996 /// for bits that V cannot have.
01997 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
01998                                      unsigned Depth) const {
01999   APInt KnownZero, KnownOne;
02000   computeKnownBits(Op, KnownZero, KnownOne, Depth);
02001   return (KnownZero & Mask) == Mask;
02002 }
02003 
02004 /// Determine which bits of Op are known to be either zero or one and return
02005 /// them in the KnownZero/KnownOne bitsets.
02006 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
02007                                     APInt &KnownOne, unsigned Depth) const {
02008   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
02009 
02010   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
02011   if (Depth == 6)
02012     return;  // Limit search depth.
02013 
02014   APInt KnownZero2, KnownOne2;
02015 
02016   switch (Op.getOpcode()) {
02017   case ISD::Constant:
02018     // We know all of the bits for a constant!
02019     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
02020     KnownZero = ~KnownOne;
02021     break;
02022   case ISD::AND:
02023     // If either the LHS or the RHS are Zero, the result is zero.
02024     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
02025     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02026 
02027     // Output known-1 bits are only known if set in both the LHS & RHS.
02028     KnownOne &= KnownOne2;
02029     // Output known-0 are known to be clear if zero in either the LHS | RHS.
02030     KnownZero |= KnownZero2;
02031     break;
02032   case ISD::OR:
02033     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
02034     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02035 
02036     // Output known-0 bits are only known if clear in both the LHS & RHS.
02037     KnownZero &= KnownZero2;
02038     // Output known-1 are known to be set if set in either the LHS | RHS.
02039     KnownOne |= KnownOne2;
02040     break;
02041   case ISD::XOR: {
02042     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
02043     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02044 
02045     // Output known-0 bits are known if clear or set in both the LHS & RHS.
02046     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
02047     // Output known-1 are known to be set if set in only one of the LHS, RHS.
02048     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
02049     KnownZero = KnownZeroOut;
02050     break;
02051   }
02052   case ISD::MUL: {
02053     computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
02054     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02055 
02056     // If low bits are zero in either operand, output low known-0 bits.
02057     // Also compute a conserative estimate for high known-0 bits.
02058     // More trickiness is possible, but this is sufficient for the
02059     // interesting case of alignment computation.
02060     KnownOne.clearAllBits();
02061     unsigned TrailZ = KnownZero.countTrailingOnes() +
02062                       KnownZero2.countTrailingOnes();
02063     unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
02064                                KnownZero2.countLeadingOnes(),
02065                                BitWidth) - BitWidth;
02066 
02067     TrailZ = std::min(TrailZ, BitWidth);
02068     LeadZ = std::min(LeadZ, BitWidth);
02069     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
02070                 APInt::getHighBitsSet(BitWidth, LeadZ);
02071     break;
02072   }
02073   case ISD::UDIV: {
02074     // For the purposes of computing leading zeros we can conservatively
02075     // treat a udiv as a logical right shift by the power of 2 known to
02076     // be less than the denominator.
02077     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02078     unsigned LeadZ = KnownZero2.countLeadingOnes();
02079 
02080     KnownOne2.clearAllBits();
02081     KnownZero2.clearAllBits();
02082     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
02083     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
02084     if (RHSUnknownLeadingOnes != BitWidth)
02085       LeadZ = std::min(BitWidth,
02086                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
02087 
02088     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
02089     break;
02090   }
02091   case ISD::SELECT:
02092     computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
02093     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
02094 
02095     // Only known if known in both the LHS and RHS.
02096     KnownOne &= KnownOne2;
02097     KnownZero &= KnownZero2;
02098     break;
02099   case ISD::SELECT_CC:
02100     computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
02101     computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
02102 
02103     // Only known if known in both the LHS and RHS.
02104     KnownOne &= KnownOne2;
02105     KnownZero &= KnownZero2;
02106     break;
02107   case ISD::SADDO:
02108   case ISD::UADDO:
02109   case ISD::SSUBO:
02110   case ISD::USUBO:
02111   case ISD::SMULO:
02112   case ISD::UMULO:
02113     if (Op.getResNo() != 1)
02114       break;
02115     // The boolean result conforms to getBooleanContents.
02116     // If we know the result of a setcc has the top bits zero, use this info.
02117     // We know that we have an integer-based boolean since these operations
02118     // are only available for integer.
02119     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
02120             TargetLowering::ZeroOrOneBooleanContent &&
02121         BitWidth > 1)
02122       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
02123     break;
02124   case ISD::SETCC:
02125     // If we know the result of a setcc has the top bits zero, use this info.
02126     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
02127             TargetLowering::ZeroOrOneBooleanContent &&
02128         BitWidth > 1)
02129       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
02130     break;
02131   case ISD::SHL:
02132     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
02133     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02134       unsigned ShAmt = SA->getZExtValue();
02135 
02136       // If the shift count is an invalid immediate, don't do anything.
02137       if (ShAmt >= BitWidth)
02138         break;
02139 
02140       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02141       KnownZero <<= ShAmt;
02142       KnownOne  <<= ShAmt;
02143       // low bits known zero.
02144       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
02145     }
02146     break;
02147   case ISD::SRL:
02148     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
02149     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02150       unsigned ShAmt = SA->getZExtValue();
02151 
02152       // If the shift count is an invalid immediate, don't do anything.
02153       if (ShAmt >= BitWidth)
02154         break;
02155 
02156       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02157       KnownZero = KnownZero.lshr(ShAmt);
02158       KnownOne  = KnownOne.lshr(ShAmt);
02159 
02160       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
02161       KnownZero |= HighBits;  // High bits known zero.
02162     }
02163     break;
02164   case ISD::SRA:
02165     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02166       unsigned ShAmt = SA->getZExtValue();
02167 
02168       // If the shift count is an invalid immediate, don't do anything.
02169       if (ShAmt >= BitWidth)
02170         break;
02171 
02172       // If any of the demanded bits are produced by the sign extension, we also
02173       // demand the input sign bit.
02174       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
02175 
02176       computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02177       KnownZero = KnownZero.lshr(ShAmt);
02178       KnownOne  = KnownOne.lshr(ShAmt);
02179 
02180       // Handle the sign bits.
02181       APInt SignBit = APInt::getSignBit(BitWidth);
02182       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
02183 
02184       if (KnownZero.intersects(SignBit)) {
02185         KnownZero |= HighBits;  // New bits are known zero.
02186       } else if (KnownOne.intersects(SignBit)) {
02187         KnownOne  |= HighBits;  // New bits are known one.
02188       }
02189     }
02190     break;
02191   case ISD::SIGN_EXTEND_INREG: {
02192     EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
02193     unsigned EBits = EVT.getScalarType().getSizeInBits();
02194 
02195     // Sign extension.  Compute the demanded bits in the result that are not
02196     // present in the input.
02197     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
02198 
02199     APInt InSignBit = APInt::getSignBit(EBits);
02200     APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
02201 
02202     // If the sign extended bits are demanded, we know that the sign
02203     // bit is demanded.
02204     InSignBit = InSignBit.zext(BitWidth);
02205     if (NewBits.getBoolValue())
02206       InputDemandedBits |= InSignBit;
02207 
02208     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02209     KnownOne &= InputDemandedBits;
02210     KnownZero &= InputDemandedBits;
02211 
02212     // If the sign bit of the input is known set or clear, then we know the
02213     // top bits of the result.
02214     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
02215       KnownZero |= NewBits;
02216       KnownOne  &= ~NewBits;
02217     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
02218       KnownOne  |= NewBits;
02219       KnownZero &= ~NewBits;
02220     } else {                              // Input sign bit unknown
02221       KnownZero &= ~NewBits;
02222       KnownOne  &= ~NewBits;
02223     }
02224     break;
02225   }
02226   case ISD::CTTZ:
02227   case ISD::CTTZ_ZERO_UNDEF:
02228   case ISD::CTLZ:
02229   case ISD::CTLZ_ZERO_UNDEF:
02230   case ISD::CTPOP: {
02231     unsigned LowBits = Log2_32(BitWidth)+1;
02232     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
02233     KnownOne.clearAllBits();
02234     break;
02235   }
02236   case ISD::LOAD: {
02237     LoadSDNode *LD = cast<LoadSDNode>(Op);
02238     // If this is a ZEXTLoad and we are looking at the loaded value.
02239     if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
02240       EVT VT = LD->getMemoryVT();
02241       unsigned MemBits = VT.getScalarType().getSizeInBits();
02242       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
02243     } else if (const MDNode *Ranges = LD->getRanges()) {
02244       computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
02245     }
02246     break;
02247   }
02248   case ISD::ZERO_EXTEND: {
02249     EVT InVT = Op.getOperand(0).getValueType();
02250     unsigned InBits = InVT.getScalarType().getSizeInBits();
02251     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
02252     KnownZero = KnownZero.trunc(InBits);
02253     KnownOne = KnownOne.trunc(InBits);
02254     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02255     KnownZero = KnownZero.zext(BitWidth);
02256     KnownOne = KnownOne.zext(BitWidth);
02257     KnownZero |= NewBits;
02258     break;
02259   }
02260   case ISD::SIGN_EXTEND: {
02261     EVT InVT = Op.getOperand(0).getValueType();
02262     unsigned InBits = InVT.getScalarType().getSizeInBits();
02263     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
02264 
02265     KnownZero = KnownZero.trunc(InBits);
02266     KnownOne = KnownOne.trunc(InBits);
02267     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02268 
02269     // Note if the sign bit is known to be zero or one.
02270     bool SignBitKnownZero = KnownZero.isNegative();
02271     bool SignBitKnownOne  = KnownOne.isNegative();
02272 
02273     KnownZero = KnownZero.zext(BitWidth);
02274     KnownOne = KnownOne.zext(BitWidth);
02275 
02276     // If the sign bit is known zero or one, the top bits match.
02277     if (SignBitKnownZero)
02278       KnownZero |= NewBits;
02279     else if (SignBitKnownOne)
02280       KnownOne  |= NewBits;
02281     break;
02282   }
02283   case ISD::ANY_EXTEND: {
02284     EVT InVT = Op.getOperand(0).getValueType();
02285     unsigned InBits = InVT.getScalarType().getSizeInBits();
02286     KnownZero = KnownZero.trunc(InBits);
02287     KnownOne = KnownOne.trunc(InBits);
02288     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02289     KnownZero = KnownZero.zext(BitWidth);
02290     KnownOne = KnownOne.zext(BitWidth);
02291     break;
02292   }
02293   case ISD::TRUNCATE: {
02294     EVT InVT = Op.getOperand(0).getValueType();
02295     unsigned InBits = InVT.getScalarType().getSizeInBits();
02296     KnownZero = KnownZero.zext(InBits);
02297     KnownOne = KnownOne.zext(InBits);
02298     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02299     KnownZero = KnownZero.trunc(BitWidth);
02300     KnownOne = KnownOne.trunc(BitWidth);
02301     break;
02302   }
02303   case ISD::AssertZext: {
02304     EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
02305     APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
02306     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02307     KnownZero |= (~InMask);
02308     KnownOne  &= (~KnownZero);
02309     break;
02310   }
02311   case ISD::FGETSIGN:
02312     // All bits are zero except the low bit.
02313     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
02314     break;
02315 
02316   case ISD::SUB: {
02317     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
02318       // We know that the top bits of C-X are clear if X contains less bits
02319       // than C (i.e. no wrap-around can happen).  For example, 20-X is
02320       // positive if we can prove that X is >= 0 and < 16.
02321       if (CLHS->getAPIntValue().isNonNegative()) {
02322         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
02323         // NLZ can't be BitWidth with no sign bit
02324         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
02325         computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
02326 
02327         // If all of the MaskV bits are known to be zero, then we know the
02328         // output top bits are zero, because we now know that the output is
02329         // from [0-C].
02330         if ((KnownZero2 & MaskV) == MaskV) {
02331           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
02332           // Top bits known zero.
02333           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
02334         }
02335       }
02336     }
02337   }
02338   // fall through
02339   case ISD::ADD:
02340   case ISD::ADDE: {
02341     // Output known-0 bits are known if clear or set in both the low clear bits
02342     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
02343     // low 3 bits clear.
02344     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
02345     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
02346 
02347     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
02348     KnownZeroOut = std::min(KnownZeroOut,
02349                             KnownZero2.countTrailingOnes());
02350 
02351     if (Op.getOpcode() == ISD::ADD) {
02352       KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
02353       break;
02354     }
02355 
02356     // With ADDE, a carry bit may be added in, so we can only use this
02357     // information if we know (at least) that the low two bits are clear.  We
02358     // then return to the caller that the low bit is unknown but that other bits
02359     // are known zero.
02360     if (KnownZeroOut >= 2) // ADDE
02361       KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
02362     break;
02363   }
02364   case ISD::SREM:
02365     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02366       const APInt &RA = Rem->getAPIntValue().abs();
02367       if (RA.isPowerOf2()) {
02368         APInt LowBits = RA - 1;
02369         computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
02370 
02371         // The low bits of the first operand are unchanged by the srem.
02372         KnownZero = KnownZero2 & LowBits;
02373         KnownOne = KnownOne2 & LowBits;
02374 
02375         // If the first operand is non-negative or has all low bits zero, then
02376         // the upper bits are all zero.
02377         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
02378           KnownZero |= ~LowBits;
02379 
02380         // If the first operand is negative and not all low bits are zero, then
02381         // the upper bits are all one.
02382         if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
02383           KnownOne |= ~LowBits;
02384         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
02385       }
02386     }
02387     break;
02388   case ISD::UREM: {
02389     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02390       const APInt &RA = Rem->getAPIntValue();
02391       if (RA.isPowerOf2()) {
02392         APInt LowBits = (RA - 1);
02393         computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
02394 
02395         // The upper bits are all zero, the lower ones are unchanged.
02396         KnownZero = KnownZero2 | ~LowBits;
02397         KnownOne = KnownOne2 & LowBits;
02398         break;
02399       }
02400     }
02401 
02402     // Since the result is less than or equal to either operand, any leading
02403     // zero bits in either operand must also exist in the result.
02404     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02405     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
02406 
02407     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
02408                                 KnownZero2.countLeadingOnes());
02409     KnownOne.clearAllBits();
02410     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
02411     break;
02412   }
02413   case ISD::EXTRACT_ELEMENT: {
02414     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02415     const unsigned Index =
02416       cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
02417     const unsigned BitWidth = Op.getValueType().getSizeInBits();
02418 
02419     // Remove low part of known bits mask
02420     KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
02421     KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
02422 
02423     // Remove high part of known bit mask
02424     KnownZero = KnownZero.trunc(BitWidth);
02425     KnownOne = KnownOne.trunc(BitWidth);
02426     break;
02427   }
02428   case ISD::FrameIndex:
02429   case ISD::TargetFrameIndex:
02430     if (unsigned Align = InferPtrAlignment(Op)) {
02431       // The low bits are known zero if the pointer is aligned.
02432       KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
02433       break;
02434     }
02435     break;
02436 
02437   default:
02438     if (Op.getOpcode() < ISD::BUILTIN_OP_END)
02439       break;
02440     // Fallthrough
02441   case ISD::INTRINSIC_WO_CHAIN:
02442   case ISD::INTRINSIC_W_CHAIN:
02443   case ISD::INTRINSIC_VOID:
02444     // Allow the target to implement this method for its nodes.
02445     TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
02446     break;
02447   }
02448 
02449   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
02450 }
02451 
02452 /// ComputeNumSignBits - Return the number of times the sign bit of the
02453 /// register is replicated into the other bits.  We know that at least 1 bit
02454 /// is always equal to the sign bit (itself), but other cases can give us
02455 /// information.  For example, immediately after an "SRA X, 2", we know that
02456 /// the top 3 bits are all equal to each other, so we return 3.
02457 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
02458   EVT VT = Op.getValueType();
02459   assert(VT.isInteger() && "Invalid VT!");
02460   unsigned VTBits = VT.getScalarType().getSizeInBits();
02461   unsigned Tmp, Tmp2;
02462   unsigned FirstAnswer = 1;
02463 
02464   if (Depth == 6)
02465     return 1;  // Limit search depth.
02466 
02467   switch (Op.getOpcode()) {
02468   default: break;
02469   case ISD::AssertSext:
02470     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
02471     return VTBits-Tmp+1;
02472   case ISD::AssertZext:
02473     Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
02474     return VTBits-Tmp;
02475 
02476   case ISD::Constant: {
02477     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
02478     return Val.getNumSignBits();
02479   }
02480 
02481   case ISD::SIGN_EXTEND:
02482     Tmp =
02483         VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
02484     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
02485 
02486   case ISD::SIGN_EXTEND_INREG:
02487     // Max of the input and what this extends.
02488     Tmp =
02489       cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
02490     Tmp = VTBits-Tmp+1;
02491 
02492     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02493     return std::max(Tmp, Tmp2);
02494 
02495   case ISD::SRA:
02496     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02497     // SRA X, C   -> adds C sign bits.
02498     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02499       Tmp += C->getZExtValue();
02500       if (Tmp > VTBits) Tmp = VTBits;
02501     }
02502     return Tmp;
02503   case ISD::SHL:
02504     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02505       // shl destroys sign bits.
02506       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02507       if (C->getZExtValue() >= VTBits ||      // Bad shift.
02508           C->getZExtValue() >= Tmp) break;    // Shifted all sign bits out.
02509       return Tmp - C->getZExtValue();
02510     }
02511     break;
02512   case ISD::AND:
02513   case ISD::OR:
02514   case ISD::XOR:    // NOT is handled here.
02515     // Logical binary ops preserve the number of sign bits at the worst.
02516     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02517     if (Tmp != 1) {
02518       Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
02519       FirstAnswer = std::min(Tmp, Tmp2);
02520       // We computed what we know about the sign bits as our first
02521       // answer. Now proceed to the generic code that uses
02522       // computeKnownBits, and pick whichever answer is better.
02523     }
02524     break;
02525 
02526   case ISD::SELECT:
02527     Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
02528     if (Tmp == 1) return 1;  // Early out.
02529     Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
02530     return std::min(Tmp, Tmp2);
02531 
02532   case ISD::SADDO:
02533   case ISD::UADDO:
02534   case ISD::SSUBO:
02535   case ISD::USUBO:
02536   case ISD::SMULO:
02537   case ISD::UMULO:
02538     if (Op.getResNo() != 1)
02539       break;
02540     // The boolean result conforms to getBooleanContents.  Fall through.
02541     // If setcc returns 0/-1, all bits are sign bits.
02542     // We know that we have an integer-based boolean since these operations
02543     // are only available for integer.
02544     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
02545         TargetLowering::ZeroOrNegativeOneBooleanContent)
02546       return VTBits;
02547     break;
02548   case ISD::SETCC:
02549     // If setcc returns 0/-1, all bits are sign bits.
02550     if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
02551         TargetLowering::ZeroOrNegativeOneBooleanContent)
02552       return VTBits;
02553     break;
02554   case ISD::ROTL:
02555   case ISD::ROTR:
02556     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
02557       unsigned RotAmt = C->getZExtValue() & (VTBits-1);
02558 
02559       // Handle rotate right by N like a rotate left by 32-N.
02560       if (Op.getOpcode() == ISD::ROTR)
02561         RotAmt = (VTBits-RotAmt) & (VTBits-1);
02562 
02563       // If we aren't rotating out all of the known-in sign bits, return the
02564       // number that are left.  This handles rotl(sext(x), 1) for example.
02565       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02566       if (Tmp > RotAmt+1) return Tmp-RotAmt;
02567     }
02568     break;
02569   case ISD::ADD:
02570     // Add can have at most one carry bit.  Thus we know that the output
02571     // is, at worst, one more bit than the inputs.
02572     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02573     if (Tmp == 1) return 1;  // Early out.
02574 
02575     // Special case decrementing a value (ADD X, -1):
02576     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
02577       if (CRHS->isAllOnesValue()) {
02578         APInt KnownZero, KnownOne;
02579         computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
02580 
02581         // If the input is known to be 0 or 1, the output is 0/-1, which is all
02582         // sign bits set.
02583         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
02584           return VTBits;
02585 
02586         // If we are subtracting one from a positive number, there is no carry
02587         // out of the result.
02588         if (KnownZero.isNegative())
02589           return Tmp;
02590       }
02591 
02592     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
02593     if (Tmp2 == 1) return 1;
02594     return std::min(Tmp, Tmp2)-1;
02595 
02596   case ISD::SUB:
02597     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
02598     if (Tmp2 == 1) return 1;
02599 
02600     // Handle NEG.
02601     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
02602       if (CLHS->isNullValue()) {
02603         APInt KnownZero, KnownOne;
02604         computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
02605         // If the input is known to be 0 or 1, the output is 0/-1, which is all
02606         // sign bits set.
02607         if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
02608           return VTBits;
02609 
02610         // If the input is known to be positive (the sign bit is known clear),
02611         // the output of the NEG has the same number of sign bits as the input.
02612         if (KnownZero.isNegative())
02613           return Tmp2;
02614 
02615         // Otherwise, we treat this like a SUB.
02616       }
02617 
02618     // Sub can have at most one carry bit.  Thus we know that the output
02619     // is, at worst, one more bit than the inputs.
02620     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02621     if (Tmp == 1) return 1;  // Early out.
02622     return std::min(Tmp, Tmp2)-1;
02623   case ISD::TRUNCATE:
02624     // FIXME: it's tricky to do anything useful for this, but it is an important
02625     // case for targets like X86.
02626     break;
02627   case ISD::EXTRACT_ELEMENT: {
02628     const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
02629     const int BitWidth = Op.getValueType().getSizeInBits();
02630     const int Items =
02631       Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
02632 
02633     // Get reverse index (starting from 1), Op1 value indexes elements from
02634     // little end. Sign starts at big end.
02635     const int rIndex = Items - 1 -
02636       cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
02637 
02638     // If the sign portion ends in our element the substraction gives correct
02639     // result. Otherwise it gives either negative or > bitwidth result
02640     return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
02641   }
02642   }
02643 
02644   // If we are looking at the loaded value of the SDNode.
02645   if (Op.getResNo() == 0) {
02646     // Handle LOADX separately here. EXTLOAD case will fallthrough.
02647     if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
02648       unsigned ExtType = LD->getExtensionType();
02649       switch (ExtType) {
02650         default: break;
02651         case ISD::SEXTLOAD:    // '17' bits known
02652           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
02653           return VTBits-Tmp+1;
02654         case ISD::ZEXTLOAD:    // '16' bits known
02655           Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
02656           return VTBits-Tmp;
02657       }
02658     }
02659   }
02660 
02661   // Allow the target to implement this method for its nodes.
02662   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
02663       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
02664       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
02665       Op.getOpcode() == ISD::INTRINSIC_VOID) {
02666     unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
02667     if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
02668   }
02669 
02670   // Finally, if we can prove that the top bits of the result are 0's or 1's,
02671   // use this information.
02672   APInt KnownZero, KnownOne;
02673   computeKnownBits(Op, KnownZero, KnownOne, Depth);
02674 
02675   APInt Mask;
02676   if (KnownZero.isNegative()) {        // sign bit is 0
02677     Mask = KnownZero;
02678   } else if (KnownOne.isNegative()) {  // sign bit is 1;
02679     Mask = KnownOne;
02680   } else {
02681     // Nothing known.
02682     return FirstAnswer;
02683   }
02684 
02685   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
02686   // the number of identical bits in the top of the input value.
02687   Mask = ~Mask;
02688   Mask <<= Mask.getBitWidth()-VTBits;
02689   // Return # leading zeros.  We use 'min' here in case Val was zero before
02690   // shifting.  We don't want to return '64' as for an i32 "0".
02691   return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
02692 }
02693 
02694 /// isBaseWithConstantOffset - Return true if the specified operand is an
02695 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
02696 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
02697 /// semantics as an ADD.  This handles the equivalence:
02698 ///     X|Cst == X+Cst iff X&Cst = 0.
02699 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
02700   if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
02701       !isa<ConstantSDNode>(Op.getOperand(1)))
02702     return false;
02703 
02704   if (Op.getOpcode() == ISD::OR &&
02705       !MaskedValueIsZero(Op.getOperand(0),
02706                      cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
02707     return false;
02708 
02709   return true;
02710 }
02711 
02712 
02713 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
02714   // If we're told that NaNs won't happen, assume they won't.
02715   if (getTarget().Options.NoNaNsFPMath)
02716     return true;
02717 
02718   // If the value is a constant, we can obviously see if it is a NaN or not.
02719   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
02720     return !C->getValueAPF().isNaN();
02721 
02722   // TODO: Recognize more cases here.
02723 
02724   return false;
02725 }
02726 
02727 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
02728   // If the value is a constant, we can obviously see if it is a zero or not.
02729   if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
02730     return !C->isZero();
02731 
02732   // TODO: Recognize more cases here.
02733   switch (Op.getOpcode()) {
02734   default: break;
02735   case ISD::OR:
02736     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
02737       return !C->isNullValue();
02738     break;
02739   }
02740 
02741   return false;
02742 }
02743 
02744 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
02745   // Check the obvious case.
02746   if (A == B) return true;
02747 
02748   // For for negative and positive zero.
02749   if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
02750     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
02751       if (CA->isZero() && CB->isZero()) return true;
02752 
02753   // Otherwise they may not be equal.
02754   return false;
02755 }
02756 
02757 /// getNode - Gets or creates the specified node.
02758 ///
02759 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
02760   FoldingSetNodeID ID;
02761   AddNodeIDNode(ID, Opcode, getVTList(VT), None);
02762   void *IP = nullptr;
02763   if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
02764     return SDValue(E, 0);
02765 
02766   SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
02767                                          DL.getDebugLoc(), getVTList(VT));
02768   CSEMap.InsertNode(N, IP);
02769 
02770   InsertNode(N);
02771   return SDValue(N, 0);
02772 }
02773 
02774 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
02775                               EVT VT, SDValue Operand) {
02776   // Constant fold unary operations with an integer constant operand. Even
02777   // opaque constant will be folded, because the folding of unary operations
02778   // doesn't create new constants with different values. Nevertheless, the
02779   // opaque flag is preserved during folding to prevent future folding with
02780   // other constants.
02781   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
02782     const APInt &Val = C->getAPIntValue();
02783     switch (Opcode) {
02784     default: break;
02785     case ISD::SIGN_EXTEND:
02786       return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
02787                          C->isTargetOpcode(), C->isOpaque());
02788     case ISD::ANY_EXTEND:
02789     case ISD::ZERO_EXTEND:
02790     case ISD::TRUNCATE:
02791       return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
02792                          C->isTargetOpcode(), C->isOpaque());
02793     case ISD::UINT_TO_FP:
02794     case ISD::SINT_TO_FP: {
02795       APFloat apf(EVTToAPFloatSemantics(VT),
02796                   APInt::getNullValue(VT.getSizeInBits()));
02797       (void)apf.convertFromAPInt(Val,
02798                                  Opcode==ISD::SINT_TO_FP,
02799                                  APFloat::rmNearestTiesToEven);
02800       return getConstantFP(apf, DL, VT);
02801     }
02802     case ISD::BITCAST:
02803       if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
02804         return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
02805       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
02806         return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
02807       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
02808         return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
02809       break;
02810     case ISD::BSWAP:
02811       return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
02812                          C->isOpaque());
02813     case ISD::CTPOP:
02814       return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
02815                          C->isOpaque());
02816     case ISD::CTLZ:
02817     case ISD::CTLZ_ZERO_UNDEF:
02818       return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
02819                          C->isOpaque());
02820     case ISD::CTTZ:
02821     case ISD::CTTZ_ZERO_UNDEF:
02822       return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
02823                          C->isOpaque());
02824     }
02825   }
02826 
02827   // Constant fold unary operations with a floating point constant operand.
02828   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
02829     APFloat V = C->getValueAPF();    // make copy
02830     switch (Opcode) {
02831     case ISD::FNEG:
02832       V.changeSign();
02833       return getConstantFP(V, DL, VT);
02834     case ISD::FABS:
02835       V.clearSign();
02836       return getConstantFP(V, DL, VT);
02837     case ISD::FCEIL: {
02838       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
02839       if (fs == APFloat::opOK || fs == APFloat::opInexact)
02840         return getConstantFP(V, DL, VT);
02841       break;
02842     }
02843     case ISD::FTRUNC: {
02844       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
02845       if (fs == APFloat::opOK || fs == APFloat::opInexact)
02846         return getConstantFP(V, DL, VT);
02847       break;
02848     }
02849     case ISD::FFLOOR: {
02850       APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
02851       if (fs == APFloat::opOK || fs == APFloat::opInexact)
02852         return getConstantFP(V, DL, VT);
02853       break;
02854     }
02855     case ISD::FP_EXTEND: {
02856       bool ignored;
02857       // This can return overflow, underflow, or inexact; we don't care.
02858       // FIXME need to be more flexible about rounding mode.
02859       (void)V.convert(EVTToAPFloatSemantics(VT),
02860                       APFloat::rmNearestTiesToEven, &ignored);
02861       return getConstantFP(V, DL, VT);
02862     }
02863     case ISD::FP_TO_SINT:
02864     case ISD::FP_TO_UINT: {
02865       integerPart x[2];
02866       bool ignored;
02867       static_assert(integerPartWidth >= 64, "APFloat parts too small!");
02868       // FIXME need to be more flexible about rounding mode.
02869       APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
02870                             Opcode==ISD::FP_TO_SINT,
02871                             APFloat::rmTowardZero, &ignored);
02872       if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
02873         break;
02874       APInt api(VT.getSizeInBits(), x);
02875       return getConstant(api, DL, VT);
02876     }
02877     case ISD::BITCAST:
02878       if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
02879         return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
02880       else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
02881         return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
02882       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
02883         return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
02884       break;
02885     }
02886   }
02887 
02888   // Constant fold unary operations with a vector integer or float operand.
02889   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
02890     if (BV->isConstant()) {
02891       switch (Opcode) {
02892       default:
02893         // FIXME: Entirely reasonable to perform folding of other unary
02894         // operations here as the need arises.
02895         break;
02896       case ISD::FNEG:
02897       case ISD::FABS:
02898       case ISD::FCEIL:
02899       case ISD::FTRUNC:
02900       case ISD::FFLOOR:
02901       case ISD::FP_EXTEND:
02902       case ISD::FP_TO_SINT:
02903       case ISD::FP_TO_UINT:
02904       case ISD::TRUNCATE:
02905       case ISD::UINT_TO_FP:
02906       case ISD::SINT_TO_FP: {
02907         EVT SVT = VT.getScalarType();
02908         EVT InVT = BV->getValueType(0);
02909         EVT InSVT = InVT.getScalarType();
02910 
02911         // Find legal integer scalar type for constant promotion and
02912         // ensure that its scalar size is at least as large as source.
02913         EVT LegalSVT = SVT;
02914         if (SVT.isInteger()) {
02915           LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
02916           if (LegalSVT.bitsLT(SVT)) break;
02917         }
02918 
02919         // Let the above scalar folding handle the folding of each element.
02920         SmallVector<SDValue, 8> Ops;
02921         for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
02922           SDValue OpN = BV->getOperand(i);
02923           EVT OpVT = OpN.getValueType();
02924 
02925           // Build vector (integer) scalar operands may need implicit
02926           // truncation - do this before constant folding.
02927           if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
02928             OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
02929 
02930           OpN = getNode(Opcode, DL, SVT, OpN);
02931 
02932           // Legalize the (integer) scalar constant if necessary.
02933           if (LegalSVT != SVT)
02934             OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
02935 
02936           if (OpN.getOpcode() != ISD::UNDEF &&
02937               OpN.getOpcode() != ISD::Constant &&
02938               OpN.getOpcode() != ISD::ConstantFP)
02939             break;
02940           Ops.push_back(OpN);
02941         }
02942         if (Ops.size() == VT.getVectorNumElements())
02943           return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
02944         break;
02945       }
02946       }
02947     }
02948   }
02949 
02950   unsigned OpOpcode = Operand.getNode()->getOpcode();
02951   switch (Opcode) {
02952   case ISD::TokenFactor:
02953   case ISD::MERGE_VALUES:
02954   case ISD::CONCAT_VECTORS:
02955     return Operand;         // Factor, merge or concat of one node?  No need.
02956   case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
02957   case ISD::FP_EXTEND:
02958     assert(VT.isFloatingPoint() &&
02959            Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
02960     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
02961     assert((!VT.isVector() ||
02962             VT.getVectorNumElements() ==
02963             Operand.getValueType().getVectorNumElements()) &&
02964            "Vector element count mismatch!");
02965     if (Operand.getOpcode() == ISD::UNDEF)
02966       return getUNDEF(VT);
02967     break;
02968   case ISD::SIGN_EXTEND:
02969     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
02970            "Invalid SIGN_EXTEND!");
02971     if (Operand.getValueType() == VT) return Operand;   // noop extension
02972     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
02973            "Invalid sext node, dst < src!");
02974     assert((!VT.isVector() ||
02975             VT.getVectorNumElements() ==
02976             Operand.getValueType().getVectorNumElements()) &&
02977            "Vector element count mismatch!");
02978     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
02979       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
02980     else if (OpOpcode == ISD::UNDEF)
02981       // sext(undef) = 0, because the top bits will all be the same.
02982       return getConstant(0, DL, VT);
02983     break;
02984   case ISD::ZERO_EXTEND:
02985     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
02986            "Invalid ZERO_EXTEND!");
02987     if (Operand.getValueType() == VT) return Operand;   // noop extension
02988     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
02989            "Invalid zext node, dst < src!");
02990     assert((!VT.isVector() ||
02991             VT.getVectorNumElements() ==
02992             Operand.getValueType().getVectorNumElements()) &&
02993            "Vector element count mismatch!");
02994     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
02995       return getNode(ISD::ZERO_EXTEND, DL, VT,
02996                      Operand.getNode()->getOperand(0));
02997     else if (OpOpcode == ISD::UNDEF)
02998       // zext(undef) = 0, because the top bits will be zero.
02999       return getConstant(0, DL, VT);
03000     break;
03001   case ISD::ANY_EXTEND:
03002     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
03003            "Invalid ANY_EXTEND!");
03004     if (Operand.getValueType() == VT) return Operand;   // noop extension
03005     assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
03006            "Invalid anyext node, dst < src!");
03007     assert((!VT.isVector() ||
03008             VT.getVectorNumElements() ==
03009             Operand.getValueType().getVectorNumElements()) &&
03010            "Vector element count mismatch!");
03011 
03012     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
03013         OpOpcode == ISD::ANY_EXTEND)
03014       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
03015       return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
03016     else if (OpOpcode == ISD::UNDEF)
03017       return getUNDEF(VT);
03018 
03019     // (ext (trunx x)) -> x
03020     if (OpOpcode == ISD::TRUNCATE) {
03021       SDValue OpOp = Operand.getNode()->getOperand(0);
03022       if (OpOp.getValueType() == VT)
03023         return OpOp;
03024     }
03025     break;
03026   case ISD::TRUNCATE:
03027     assert(VT.isInteger() && Operand.getValueType().isInteger() &&
03028            "Invalid TRUNCATE!");
03029     if (Operand.getValueType() == VT) return Operand;   // noop truncate
03030     assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
03031            "Invalid truncate node, src < dst!");
03032     assert((!VT.isVector() ||
03033             VT.getVectorNumElements() ==
03034             Operand.getValueType().getVectorNumElements()) &&
03035            "Vector element count mismatch!");
03036     if (OpOpcode == ISD::TRUNCATE)
03037       return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
03038     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
03039         OpOpcode == ISD::ANY_EXTEND) {
03040       // If the source is smaller than the dest, we still need an extend.
03041       if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
03042             .bitsLT(VT.getScalarType()))
03043         return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
03044       if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
03045         return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
03046       return Operand.getNode()->getOperand(0);
03047     }
03048     if (OpOpcode == ISD::UNDEF)
03049       return getUNDEF(VT);
03050     break;
03051   case ISD::BITCAST:
03052     // Basic sanity checking.
03053     assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
03054            && "Cannot BITCAST between types of different sizes!");
03055     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
03056     if (OpOpcode == ISD::BITCAST)  // bitconv(bitconv(x)) -> bitconv(x)
03057       return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
03058     if (OpOpcode == ISD::UNDEF)
03059       return getUNDEF(VT);
03060     break;
03061   case ISD::SCALAR_TO_VECTOR:
03062     assert(VT.isVector() && !Operand.getValueType().isVector() &&
03063            (VT.getVectorElementType() == Operand.getValueType() ||
03064             (VT.getVectorElementType().isInteger() &&
03065              Operand.getValueType().isInteger() &&
03066              VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
03067            "Illegal SCALAR_TO_VECTOR node!");
03068     if (OpOpcode == ISD::UNDEF)
03069       return getUNDEF(VT);
03070     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
03071     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
03072         isa<ConstantSDNode>(Operand.getOperand(1)) &&
03073         Operand.getConstantOperandVal(1) == 0 &&
03074         Operand.getOperand(0).getValueType() == VT)
03075       return Operand.getOperand(0);
03076     break;
03077   case ISD::FNEG:
03078     // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
03079     if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
03080       return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
03081                      Operand.getNode()->getOperand(0));
03082     if (OpOpcode == ISD::FNEG)  // --X -> X
03083       return Operand.getNode()->getOperand(0);
03084     break;
03085   case ISD::FABS:
03086     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
03087       return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
03088     break;
03089   }
03090 
03091   SDNode *N;
03092   SDVTList VTs = getVTList(VT);
03093   if (VT != MVT::Glue) { // Don't CSE flag producing nodes
03094     FoldingSetNodeID ID;
03095     SDValue Ops[1] = { Operand };
03096     AddNodeIDNode(ID, Opcode, VTs, Ops);
03097     void *IP = nullptr;
03098     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
03099       return SDValue(E, 0);
03100 
03101     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
03102                                         DL.getDebugLoc(), VTs, Operand);
03103     CSEMap.InsertNode(N, IP);
03104   } else {
03105     N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
03106                                         DL.getDebugLoc(), VTs, Operand);
03107   }
03108 
03109   InsertNode(N);
03110   return SDValue(N, 0);
03111 }
03112 
03113 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
03114                                         const APInt &C2) {
03115   switch (Opcode) {
03116   case ISD::ADD:  return std::make_pair(C1 + C2, true);
03117   case ISD::SUB:  return std::make_pair(C1 - C2, true);
03118   case ISD::MUL:  return std::make_pair(C1 * C2, true);
03119   case ISD::AND:  return std::make_pair(C1 & C2, true);
03120   case ISD::OR:   return std::make_pair(C1 | C2, true);
03121   case ISD::XOR:  return std::make_pair(C1 ^ C2, true);
03122   case ISD::SHL:  return std::make_pair(C1 << C2, true);
03123   case ISD::SRL:  return std::make_pair(C1.lshr(C2), true);
03124   case ISD::SRA:  return std::make_pair(C1.ashr(C2), true);
03125   case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
03126   case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
03127   case ISD::UDIV:
03128     if (!C2.getBoolValue())
03129       break;
03130     return std::make_pair(C1.udiv(C2), true);
03131   case ISD::UREM:
03132     if (!C2.getBoolValue())
03133       break;
03134     return std::make_pair(C1.urem(C2), true);
03135   case ISD::SDIV:
03136     if (!C2.getBoolValue())
03137       break;
03138     return std::make_pair(C1.sdiv(C2), true);
03139   case ISD::SREM:
03140     if (!C2.getBoolValue())
03141       break;
03142     return std::make_pair(C1.srem(C2), true);
03143   }
03144   return std::make_pair(APInt(1, 0), false);
03145 }
03146 
03147 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
03148                                              const ConstantSDNode *Cst1,
03149                                              const ConstantSDNode *Cst2) {
03150   if (Cst1->isOpaque() || Cst2->isOpaque())
03151     return SDValue();
03152 
03153   std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
03154                                             Cst2->getAPIntValue());
03155   if (!Folded.second)
03156     return SDValue();
03157   return getConstant(Folded.first, DL, VT);
03158 }
03159 
03160 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
03161                                              SDNode *Cst1, SDNode *Cst2) {
03162   // If the opcode is a target-specific ISD node, there's nothing we can
03163   // do here and the operand rules may not line up with the below, so
03164   // bail early.
03165   if (Opcode >= ISD::BUILTIN_OP_END)
03166     return SDValue();
03167 
03168   // Handle the case of two scalars.
03169   if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
03170     if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
03171       if (SDValue Folded =
03172           FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
03173         if (!VT.isVector())
03174           return Folded;
03175         SmallVector<SDValue, 4> Outputs;
03176         // We may have a vector type but a scalar result. Create a splat.
03177         Outputs.resize(VT.getVectorNumElements(), Outputs.back());
03178         // Build a big vector out of the scalar elements we generated.
03179         return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
03180       } else {
03181         return SDValue();
03182       }
03183     }
03184   }
03185 
03186   // For vectors extract each constant element into Inputs so we can constant
03187   // fold them individually.
03188   BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
03189   BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
03190   if (!BV1 || !BV2)
03191     return SDValue();
03192 
03193   assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
03194 
03195   EVT SVT = VT.getScalarType();
03196   SmallVector<SDValue, 4> Outputs;
03197   for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
03198     ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
03199     ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
03200     if (!V1 || !V2) // Not a constant, bail.
03201       return SDValue();
03202 
03203     if (V1->isOpaque() || V2->isOpaque())
03204       return SDValue();
03205 
03206     // Avoid BUILD_VECTOR nodes that perform implicit truncation.
03207     // FIXME: This is valid and could be handled by truncating the APInts.
03208     if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
03209       return SDValue();
03210 
03211     // Fold one vector element.
03212     std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
03213                                               V2->getAPIntValue());
03214     if (!Folded.second)
03215       return SDValue();
03216     Outputs.push_back(getConstant(Folded.first, DL, SVT));
03217   }
03218 
03219   assert(VT.getVectorNumElements() == Outputs.size() &&
03220          "Vector size mismatch!");
03221 
03222   // We may have a vector type but a scalar result. Create a splat.
03223   Outputs.resize(VT.getVectorNumElements(), Outputs.back());
03224 
03225   // Build a big vector out of the scalar elements we generated.
03226   return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
03227 }
03228 
03229 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
03230                               SDValue N2, bool nuw, bool nsw, bool exact) {
03231   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
03232   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
03233   switch (Opcode) {
03234   default: break;
03235   case ISD::TokenFactor:
03236     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
03237            N2.getValueType() == MVT::Other && "Invalid token factor!");
03238     // Fold trivial token factors.
03239     if (N1.getOpcode() == ISD::EntryToken) return N2;
03240     if (N2.getOpcode() == ISD::EntryToken) return N1;
03241     if (N1 == N2) return N1;
03242     break;
03243   case ISD::CONCAT_VECTORS:
03244     // Concat of UNDEFs is UNDEF.
03245     if (N1.getOpcode() == ISD::UNDEF &&
03246         N2.getOpcode() == ISD::UNDEF)
03247       return getUNDEF(VT);
03248 
03249     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
03250     // one big BUILD_VECTOR.
03251     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
03252         N2.getOpcode() == ISD::BUILD_VECTOR) {
03253       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
03254                                     N1.getNode()->op_end());
03255       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
03256 
03257       // BUILD_VECTOR requires all inputs to be of the same type, find the
03258       // maximum type and extend them all.
03259       EVT SVT = VT.getScalarType();
03260       for (SDValue Op : Elts)
03261         SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
03262       if (SVT.bitsGT(VT.getScalarType()))
03263         for (SDValue &Op : Elts)
03264           Op = TLI->isZExtFree(Op.getValueType(), SVT)
03265              ? getZExtOrTrunc(Op, DL, SVT)
03266              : getSExtOrTrunc(Op, DL, SVT);
03267 
03268       return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
03269     }
03270     break;
03271   case ISD::AND:
03272     assert(VT.isInteger() && "This operator does not apply to FP types!");
03273     assert(N1.getValueType() == N2.getValueType() &&
03274            N1.getValueType() == VT && "Binary operator types must match!");
03275     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
03276     // worth handling here.
03277     if (N2C && N2C->isNullValue())
03278       return N2;
03279     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
03280       return N1;
03281     break;
03282   case ISD::OR:
03283   case ISD::XOR:
03284   case ISD::ADD:
03285   case ISD::SUB:
03286     assert(VT.isInteger() && "This operator does not apply to FP types!");
03287     assert(N1.getValueType() == N2.getValueType() &&
03288            N1.getValueType() == VT && "Binary operator types must match!");
03289     // (X ^|+- 0) -> X.  This commonly occurs when legalizing i64 values, so
03290     // it's worth handling here.
03291     if (N2C && N2C->isNullValue())
03292       return N1;
03293     break;
03294   case ISD::UDIV:
03295   case ISD::UREM:
03296   case ISD::MULHU:
03297   case ISD::MULHS:
03298   case ISD::MUL:
03299   case ISD::SDIV:
03300   case ISD::SREM:
03301     assert(VT.isInteger() && "This operator does not apply to FP types!");
03302     assert(N1.getValueType() == N2.getValueType() &&
03303            N1.getValueType() == VT && "Binary operator types must match!");
03304     break;
03305   case ISD::FADD:
03306   case ISD::FSUB:
03307   case ISD::FMUL:
03308   case ISD::FDIV:
03309   case ISD::FREM:
03310     if (getTarget().Options.UnsafeFPMath) {
03311       if (Opcode == ISD::FADD) {
03312         // 0+x --> x
03313         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
03314           if (CFP->getValueAPF().isZero())
03315             return N2;
03316         // x+0 --> x
03317         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
03318           if (CFP->getValueAPF().isZero())
03319             return N1;
03320       } else if (Opcode == ISD::FSUB) {
03321         // x-0 --> x
03322         if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
03323           if (CFP->getValueAPF().isZero())
03324             return N1;
03325       } else if (Opcode == ISD::FMUL) {
03326         ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
03327         SDValue V = N2;
03328 
03329         // If the first operand isn't the constant, try the second
03330         if (!CFP) {
03331           CFP = dyn_cast<ConstantFPSDNode>(N2);
03332           V = N1;
03333         }
03334 
03335         if (CFP) {
03336           // 0*x --> 0
03337           if (CFP->isZero())
03338             return SDValue(CFP,0);
03339           // 1*x --> x
03340           if (CFP->isExactlyValue(1.0))
03341             return V;
03342         }
03343       }
03344     }
03345     assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
03346     assert(N1.getValueType() == N2.getValueType() &&
03347            N1.getValueType() == VT && "Binary operator types must match!");
03348     break;
03349   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
03350     assert(N1.getValueType() == VT &&
03351            N1.getValueType().isFloatingPoint() &&
03352            N2.getValueType().isFloatingPoint() &&
03353            "Invalid FCOPYSIGN!");
03354     break;
03355   case ISD::SHL:
03356   case ISD::SRA:
03357   case ISD::SRL:
03358   case ISD::ROTL:
03359   case ISD::ROTR:
03360     assert(VT == N1.getValueType() &&
03361            "Shift operators return type must be the same as their first arg");
03362     assert(VT.isInteger() && N2.getValueType().isInteger() &&
03363            "Shifts only work on integers");
03364     assert((!VT.isVector() || VT == N2.getValueType()) &&
03365            "Vector shift amounts must be in the same as their first arg");
03366     // Verify that the shift amount VT is bit enough to hold valid shift
03367     // amounts.  This catches things like trying to shift an i1024 value by an
03368     // i8, which is easy to fall into in generic code that uses
03369     // TLI.getShiftAmount().
03370     assert(N2.getValueType().getSizeInBits() >=
03371                    Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
03372            "Invalid use of small shift amount with oversized value!");
03373 
03374     // Always fold shifts of i1 values so the code generator doesn't need to
03375     // handle them.  Since we know the size of the shift has to be less than the
03376     // size of the value, the shift/rotate count is guaranteed to be zero.
03377     if (VT == MVT::i1)
03378       return N1;
03379     if (N2C && N2C->isNullValue())
03380       return N1;
03381     break;
03382   case ISD::FP_ROUND_INREG: {
03383     EVT EVT = cast<VTSDNode>(N2)->getVT();
03384     assert(VT == N1.getValueType() && "Not an inreg round!");
03385     assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
03386            "Cannot FP_ROUND_INREG integer types");
03387     assert(EVT.isVector() == VT.isVector() &&
03388            "FP_ROUND_INREG type should be vector iff the operand "
03389            "type is vector!");
03390     assert((!EVT.isVector() ||
03391             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
03392            "Vector element counts must match in FP_ROUND_INREG");
03393     assert(EVT.bitsLE(VT) && "Not rounding down!");
03394     (void)EVT;
03395     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
03396     break;
03397   }
03398   case ISD::FP_ROUND:
03399     assert(VT.isFloatingPoint() &&
03400            N1.getValueType().isFloatingPoint() &&
03401            VT.bitsLE(N1.getValueType()) &&
03402            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
03403     if (N1.getValueType() == VT) return N1;  // noop conversion.
03404     break;
03405   case ISD::AssertSext:
03406   case ISD::AssertZext: {
03407     EVT EVT = cast<VTSDNode>(N2)->getVT();
03408     assert(VT == N1.getValueType() && "Not an inreg extend!");
03409     assert(VT.isInteger() && EVT.isInteger() &&
03410            "Cannot *_EXTEND_INREG FP types");
03411     assert(!EVT.isVector() &&
03412            "AssertSExt/AssertZExt type should be the vector element type "
03413            "rather than the vector type!");
03414     assert(EVT.bitsLE(VT) && "Not extending!");
03415     if (VT == EVT) return N1; // noop assertion.
03416     break;
03417   }
03418   case ISD::SIGN_EXTEND_INREG: {
03419     EVT EVT = cast<VTSDNode>(N2)->getVT();
03420     assert(VT == N1.getValueType() && "Not an inreg extend!");
03421     assert(VT.isInteger() && EVT.isInteger() &&
03422            "Cannot *_EXTEND_INREG FP types");
03423     assert(EVT.isVector() == VT.isVector() &&
03424            "SIGN_EXTEND_INREG type should be vector iff the operand "
03425            "type is vector!");
03426     assert((!EVT.isVector() ||
03427             EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
03428            "Vector element counts must match in SIGN_EXTEND_INREG");
03429     assert(EVT.bitsLE(VT) && "Not extending!");
03430     if (EVT == VT) return N1;  // Not actually extending
03431 
03432     auto SignExtendInReg = [&](APInt Val) {
03433       unsigned FromBits = EVT.getScalarType().getSizeInBits();
03434       Val <<= Val.getBitWidth() - FromBits;
03435       Val = Val.ashr(Val.getBitWidth() - FromBits);
03436       return getConstant(Val, DL, VT.getScalarType());
03437     };
03438 
03439     if (N1C) {
03440       APInt Val = N1C->getAPIntValue();
03441       return SignExtendInReg(Val);
03442     }
03443     if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
03444       SmallVector<SDValue, 8> Ops;
03445       for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
03446         SDValue Op = N1.getOperand(i);
03447         if (Op.getValueType() != VT.getScalarType()) break;
03448         if (Op.getOpcode() == ISD::UNDEF) {
03449           Ops.push_back(Op);
03450           continue;
03451         }
03452         if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
03453           APInt Val = C->getAPIntValue();
03454           Ops.push_back(SignExtendInReg(Val));
03455           continue;
03456         }
03457         break;
03458       }
03459       if (Ops.size() == VT.getVectorNumElements())
03460         return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
03461     }
03462     break;
03463   }
03464   case ISD::EXTRACT_VECTOR_ELT:
03465     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
03466     if (N1.getOpcode() == ISD::UNDEF)
03467       return getUNDEF(VT);
03468 
03469     // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
03470     if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
03471       return getUNDEF(VT);
03472 
03473     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
03474     // expanding copies of large vectors from registers.
03475     if (N2C &&
03476         N1.getOpcode() == ISD::CONCAT_VECTORS &&
03477         N1.getNumOperands() > 0) {
03478       unsigned Factor =
03479         N1.getOperand(0).getValueType().getVectorNumElements();
03480       return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
03481                      N1.getOperand(N2C->getZExtValue() / Factor),
03482                      getConstant(N2C->getZExtValue() % Factor, DL,
03483                                  N2.getValueType()));
03484     }
03485 
03486     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
03487     // expanding large vector constants.
03488     if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
03489       SDValue Elt = N1.getOperand(N2C->getZExtValue());
03490 
03491       if (VT != Elt.getValueType())
03492         // If the vector element type is not legal, the BUILD_VECTOR operands
03493         // are promoted and implicitly truncated, and the result implicitly
03494         // extended. Make that explicit here.
03495         Elt = getAnyExtOrTrunc(Elt, DL, VT);
03496 
03497       return Elt;
03498     }
03499 
03500     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
03501     // operations are lowered to scalars.
03502     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
03503       // If the indices are the same, return the inserted element else
03504       // if the indices are known different, extract the element from
03505       // the original vector.
03506       SDValue N1Op2 = N1.getOperand(2);
03507       ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
03508 
03509       if (N1Op2C && N2C) {
03510         if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
03511           if (VT == N1.getOperand(1).getValueType())
03512             return N1.getOperand(1);
03513           else
03514             return getSExtOrTrunc(N1.getOperand(1), DL, VT);
03515         }
03516 
03517         return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
03518       }
03519     }
03520     break;
03521   case ISD::EXTRACT_ELEMENT:
03522     assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
03523     assert(!N1.getValueType().isVector() && !VT.isVector() &&
03524            (N1.getValueType().isInteger() == VT.isInteger()) &&
03525            N1.getValueType() != VT &&
03526            "Wrong types for EXTRACT_ELEMENT!");
03527 
03528     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
03529     // 64-bit integers into 32-bit parts.  Instead of building the extract of
03530     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
03531     if (N1.getOpcode() == ISD::BUILD_PAIR)
03532       return N1.getOperand(N2C->getZExtValue());
03533 
03534     // EXTRACT_ELEMENT of a constant int is also very common.
03535     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
03536       unsigned ElementSize = VT.getSizeInBits();
03537       unsigned Shift = ElementSize * N2C->getZExtValue();
03538       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
03539       return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
03540     }
03541     break;
03542   case ISD::EXTRACT_SUBVECTOR: {
03543     SDValue Index = N2;
03544     if (VT.isSimple() && N1.getValueType().isSimple()) {
03545       assert(VT.isVector() && N1.getValueType().isVector() &&
03546              "Extract subvector VTs must be a vectors!");
03547       assert(VT.getVectorElementType() ==
03548              N1.getValueType().getVectorElementType() &&
03549              "Extract subvector VTs must have the same element type!");
03550       assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
03551              "Extract subvector must be from larger vector to smaller vector!");
03552 
03553       if (isa<ConstantSDNode>(Index.getNode())) {
03554         assert((VT.getVectorNumElements() +
03555                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
03556                 <= N1.getValueType().getVectorNumElements())
03557                && "Extract subvector overflow!");
03558       }
03559 
03560       // Trivial extraction.
03561       if (VT.getSimpleVT() == N1.getSimpleValueType())
03562         return N1;
03563     }
03564     break;
03565   }
03566   }
03567 
03568   // Perform trivial constant folding.
03569   if (SDValue SV =
03570           FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
03571     return SV;
03572 
03573   // Canonicalize constant to RHS if commutative.
03574   if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
03575     std::swap(N1C, N2C);
03576     std::swap(N1, N2);
03577   }
03578 
03579   // Constant fold FP operations.
03580   bool HasFPExceptions = TLI->hasFloatingPointExceptions();
03581   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
03582   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
03583   if (N1CFP) {
03584     if (!N2CFP && isCommutativeBinOp(Opcode)) {
03585       // Canonicalize constant to RHS if commutative.
03586       std::swap(N1CFP, N2CFP);
03587       std::swap(N1, N2);
03588     } else if (N2CFP) {
03589       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
03590       APFloat::opStatus s;
03591       switch (Opcode) {
03592       case ISD::FADD:
03593         s = V1.add(V2, APFloat::rmNearestTiesToEven);
03594         if (!HasFPExceptions || s != APFloat::opInvalidOp)
03595           return getConstantFP(V1, DL, VT);
03596         break;
03597       case ISD::FSUB:
03598         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
03599         if (!HasFPExceptions || s!=APFloat::opInvalidOp)
03600           return getConstantFP(V1, DL, VT);
03601         break;
03602       case ISD::FMUL:
03603         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
03604         if (!HasFPExceptions || s!=APFloat::opInvalidOp)
03605           return getConstantFP(V1, DL, VT);
03606         break;
03607       case ISD::FDIV:
03608         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
03609         if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
03610                                  s!=APFloat::opDivByZero)) {
03611           return getConstantFP(V1, DL, VT);
03612         }
03613         break;
03614       case ISD::FREM :
03615         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
03616         if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
03617                                  s!=APFloat::opDivByZero)) {
03618           return getConstantFP(V1, DL, VT);
03619         }
03620         break;
03621       case ISD::FCOPYSIGN:
03622         V1.copySign(V2);
03623         return getConstantFP(V1, DL, VT);
03624       default: break;
03625       }
03626     }
03627 
03628     if (Opcode == ISD::FP_ROUND) {
03629       APFloat V = N1CFP->getValueAPF();    // make copy
03630       bool ignored;
03631       // This can return overflow, underflow, or inexact; we don't care.
03632       // FIXME need to be more flexible about rounding mode.
03633       (void)V.convert(EVTToAPFloatSemantics(VT),
03634                       APFloat::rmNearestTiesToEven, &ignored);
03635       return getConstantFP(V, DL, VT);
03636     }
03637   }
03638 
03639   // Canonicalize an UNDEF to the RHS, even over a constant.
03640   if (N1.getOpcode() == ISD::UNDEF) {
03641     if (isCommutativeBinOp(Opcode)) {
03642       std::swap(N1, N2);
03643     } else {
03644       switch (Opcode) {
03645       case ISD::FP_ROUND_INREG:
03646       case ISD::SIGN_EXTEND_INREG:
03647       case ISD::SUB:
03648       case ISD::FSUB:
03649       case ISD::FDIV:
03650       case ISD::FREM:
03651       case ISD::SRA:
03652         return N1;     // fold op(undef, arg2) -> undef
03653       case ISD::UDIV:
03654       case ISD::SDIV:
03655       case ISD::UREM:
03656       case ISD::SREM:
03657       case ISD::SRL:
03658       case ISD::SHL:
03659         if (!VT.isVector())
03660           return getConstant(0, DL, VT);    // fold op(undef, arg2) -> 0
03661         // For vectors, we can't easily build an all zero vector, just return
03662         // the LHS.
03663         return N2;
03664       }
03665     }
03666   }
03667 
03668   // Fold a bunch of operators when the RHS is undef.
03669   if (N2.getOpcode() == ISD::UNDEF) {
03670     switch (Opcode) {
03671     case ISD::XOR:
03672       if (N1.getOpcode() == ISD::UNDEF)
03673         // Handle undef ^ undef -> 0 special case. This is a common
03674         // idiom (misuse).
03675         return getConstant(0, DL, VT);
03676       // fallthrough
03677     case ISD::ADD:
03678     case ISD::ADDC:
03679     case ISD::ADDE:
03680     case ISD::SUB:
03681     case ISD::UDIV:
03682     case ISD::SDIV:
03683     case ISD::UREM:
03684     case ISD::SREM:
03685       return N2;       // fold op(arg1, undef) -> undef
03686     case ISD::FADD:
03687     case ISD::FSUB:
03688     case ISD::FMUL:
03689     case ISD::FDIV:
03690     case ISD::FREM:
03691       if (getTarget().Options.UnsafeFPMath)
03692         return N2;
03693       break;
03694     case ISD::MUL:
03695     case ISD::AND:
03696     case ISD::SRL:
03697     case ISD::SHL:
03698       if (!VT.isVector())
03699         return getConstant(0, DL, VT);  // fold op(arg1, undef) -> 0
03700       // For vectors, we can't easily build an all zero vector, just return
03701       // the LHS.
03702       return N1;
03703     case ISD::OR:
03704       if (!VT.isVector())
03705         return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
03706       // For vectors, we can't easily build an all one vector, just return
03707       // the LHS.
03708       return N1;
03709     case ISD::SRA:
03710       return N1;
03711     }
03712   }
03713 
03714   // Memoize this node if possible.
03715   BinarySDNode *N;
03716   SDVTList VTs = getVTList(VT);
03717   const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
03718   if (VT != MVT::Glue) {
03719     SDValue Ops[] = {N1, N2};
03720     FoldingSetNodeID ID;
03721     AddNodeIDNode(ID, Opcode, VTs, Ops);
03722     if (BinOpHasFlags)
03723       AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
03724     void *IP = nullptr;
03725     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
03726       return SDValue(E, 0);
03727 
03728     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
03729 
03730     CSEMap.InsertNode(N, IP);
03731   } else {
03732     N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
03733   }
03734 
03735   InsertNode(N);
03736   return SDValue(N, 0);
03737 }
03738 
03739 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
03740                               SDValue N1, SDValue N2, SDValue N3) {
03741   // Perform various simplifications.
03742   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
03743   switch (Opcode) {
03744   case ISD::FMA: {
03745     ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
03746     ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
03747     ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
03748     if (N1CFP && N2CFP && N3CFP) {
03749       APFloat  V1 = N1CFP->getValueAPF();
03750       const APFloat &V2 = N2CFP->getValueAPF();
03751       const APFloat &V3 = N3CFP->getValueAPF();
03752       APFloat::opStatus s =
03753         V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
03754       if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
03755         return getConstantFP(V1, DL, VT);
03756     }
03757     break;
03758   }
03759   case ISD::CONCAT_VECTORS:
03760     // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
03761     // one big BUILD_VECTOR.
03762     if (N1.getOpcode() == ISD::BUILD_VECTOR &&
03763         N2.getOpcode() == ISD::BUILD_VECTOR &&
03764         N3.getOpcode() == ISD::BUILD_VECTOR) {
03765       SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
03766                                     N1.getNode()->op_end());
03767       Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
03768       Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
03769       return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
03770     }
03771     break;
03772   case ISD::SETCC: {
03773     // Use FoldSetCC to simplify SETCC's.
03774     SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
03775     if (Simp.getNode()) return Simp;
03776     break;
03777   }
03778   case ISD::SELECT:
03779     if (N1C) {
03780      if (N1C->getZExtValue())
03781        return N2;             // select true, X, Y -> X
03782      return N3;             // select false, X, Y -> Y
03783     }
03784 
03785     if (N2 == N3) return N2;   // select C, X, X -> X
03786     break;
03787   case ISD::VECTOR_SHUFFLE:
03788     llvm_unreachable("should use getVectorShuffle constructor!");
03789   case ISD::INSERT_SUBVECTOR: {
03790     SDValue Index = N3;
03791     if (VT.isSimple() && N1.getValueType().isSimple()
03792         && N2.getValueType().isSimple()) {
03793       assert(VT.isVector() && N1.getValueType().isVector() &&
03794              N2.getValueType().isVector() &&
03795              "Insert subvector VTs must be a vectors");
03796       assert(VT == N1.getValueType() &&
03797              "Dest and insert subvector source types must match!");
03798       assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
03799              "Insert subvector must be from smaller vector to larger vector!");
03800       if (isa<ConstantSDNode>(Index.getNode())) {
03801         assert((N2.getValueType().getVectorNumElements() +
03802                 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
03803                 <= VT.getVectorNumElements())
03804                && "Insert subvector overflow!");
03805       }
03806 
03807       // Trivial insertion.
03808       if (VT.getSimpleVT() == N2.getSimpleValueType())
03809         return N2;
03810     }
03811     break;
03812   }
03813   case ISD::BITCAST:
03814     // Fold bit_convert nodes from a type to themselves.
03815     if (N1.getValueType() == VT)
03816       return N1;
03817     break;
03818   }
03819 
03820   // Memoize node if it doesn't produce a flag.
03821   SDNode *N;
03822   SDVTList VTs = getVTList(VT);
03823   if (VT != MVT::Glue) {
03824     SDValue Ops[] = { N1, N2, N3 };
03825     FoldingSetNodeID ID;
03826     AddNodeIDNode(ID, Opcode, VTs, Ops);
03827     void *IP = nullptr;
03828     if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
03829       return SDValue(E, 0);
03830 
03831     N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
03832                                           DL.getDebugLoc(), VTs, N1, N2, N3);
03833     CSEMap.InsertNode(N, IP);
03834   } else {
03835     N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
03836                                           DL.getDebugLoc(), VTs, N1, N2, N3);
03837   }
03838 
03839   InsertNode(N);
03840   return SDValue(N, 0);
03841 }
03842 
03843 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
03844                               SDValue N1, SDValue N2, SDValue N3,
03845                               SDValue N4) {
03846   SDValue Ops[] = { N1, N2, N3, N4 };
03847   return getNode(Opcode, DL, VT, Ops);
03848 }
03849 
03850 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
03851                               SDValue N1, SDValue N2, SDValue N3,
03852                               SDValue N4, SDValue N5) {
03853   SDValue Ops[] = { N1, N2, N3, N4, N5 };
03854   return getNode(Opcode, DL, VT, Ops);
03855 }
03856 
03857 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
03858 /// the incoming stack arguments to be loaded from the stack.
03859 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
03860   SmallVector<SDValue, 8> ArgChains;
03861 
03862   // Include the original chain at the beginning of the list. When this is
03863   // used by target LowerCall hooks, this helps legalize find the
03864   // CALLSEQ_BEGIN node.
03865   ArgChains.push_back(Chain);
03866 
03867   // Add a chain value for each stack argument.
03868   for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
03869        UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
03870     if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
03871       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
03872         if (FI->getIndex() < 0)
03873           ArgChains.push_back(SDValue(L, 1));
03874 
03875   // Build a tokenfactor for all the chains.
03876   return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
03877 }
03878 
03879 /// getMemsetValue - Vectorized representation of the memset value
03880 /// operand.
03881 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
03882                               SDLoc dl) {
03883   assert(Value.getOpcode() != ISD::UNDEF);
03884 
03885   unsigned NumBits = VT.getScalarType().getSizeInBits();
03886   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
03887     assert(C->getAPIntValue().getBitWidth() == 8);
03888     APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
03889     if (VT.isInteger())
03890       return DAG.getConstant(Val, dl, VT);
03891     return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
03892                              VT);
03893   }
03894 
03895   assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
03896   EVT IntVT = VT.getScalarType();
03897   if (!IntVT.isInteger())
03898     IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
03899 
03900   Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
03901   if (NumBits > 8) {
03902     // Use a multiplication with 0x010101... to extend the input to the
03903     // required length.
03904     APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
03905     Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
03906                         DAG.getConstant(Magic, dl, IntVT));
03907   }
03908 
03909   if (VT != Value.getValueType() && !VT.isInteger())
03910     Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
03911   if (VT != Value.getValueType()) {
03912     assert(VT.getVectorElementType() == Value.getValueType() &&
03913            "value type should be one vector element here");
03914     SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
03915     Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
03916   }
03917 
03918   return Value;
03919 }
03920 
03921 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
03922 /// used when a memcpy is turned into a memset when the source is a constant
03923 /// string ptr.
03924 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
03925                                   const TargetLowering &TLI, StringRef Str) {
03926   // Handle vector with all elements zero.
03927   if (Str.empty()) {
03928     if (VT.isInteger())
03929       return DAG.getConstant(0, dl, VT);
03930     else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
03931       return DAG.getConstantFP(0.0, dl, VT);
03932     else if (VT.isVector()) {
03933       unsigned NumElts = VT.getVectorNumElements();
03934       MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
03935       return DAG.getNode(ISD::BITCAST, dl, VT,
03936                          DAG.getConstant(0, dl,
03937                                          EVT::getVectorVT(*DAG.getContext(),
03938                                                           EltVT, NumElts)));
03939     } else
03940       llvm_unreachable("Expected type!");
03941   }
03942 
03943   assert(!VT.isVector() && "Can't handle vector type here!");
03944   unsigned NumVTBits = VT.getSizeInBits();
03945   unsigned NumVTBytes = NumVTBits / 8;
03946   unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
03947 
03948   APInt Val(NumVTBits, 0);
03949   if (TLI.isLittleEndian()) {
03950     for (unsigned i = 0; i != NumBytes; ++i)
03951       Val |= (uint64_t)(unsigned char)Str[i] << i*8;
03952   } else {
03953     for (unsigned i = 0; i != NumBytes; ++i)
03954       Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
03955   }
03956 
03957   // If the "cost" of materializing the integer immediate is less than the cost
03958   // of a load, then it is cost effective to turn the load into the immediate.
03959   Type *Ty = VT.getTypeForEVT(*DAG.getContext());
03960   if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
03961     return DAG.getConstant(Val, dl, VT);
03962   return SDValue(nullptr, 0);
03963 }
03964 
03965 /// getMemBasePlusOffset - Returns base and offset node for the
03966 ///
03967 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
03968                                       SelectionDAG &DAG) {
03969   EVT VT = Base.getValueType();
03970   return DAG.getNode(ISD::ADD, dl,
03971                      VT, Base, DAG.getConstant(Offset, dl, VT));
03972 }
03973 
03974 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
03975 ///
03976 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
03977   unsigned SrcDelta = 0;
03978   GlobalAddressSDNode *G = nullptr;
03979   if (Src.getOpcode() == ISD::GlobalAddress)
03980     G = cast<GlobalAddressSDNode>(Src);
03981   else if (Src.getOpcode() == ISD::ADD &&
03982            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
03983            Src.getOperand(1).getOpcode() == ISD::Constant) {
03984     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
03985     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
03986   }
03987   if (!G)
03988     return false;
03989 
03990   return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
03991 }
03992 
03993 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
03994 /// to replace the memset / memcpy. Return true if the number of memory ops
03995 /// is below the threshold. It returns the types of the sequence of
03996 /// memory ops to perform memset / memcpy by reference.
03997 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
03998                                      unsigned Limit, uint64_t Size,
03999                                      unsigned DstAlign, unsigned SrcAlign,
04000                                      bool IsMemset,
04001                                      bool ZeroMemset,
04002                                      bool MemcpyStrSrc,
04003                                      bool AllowOverlap,
04004                                      SelectionDAG &DAG,
04005                                      const TargetLowering &TLI) {
04006   assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
04007          "Expecting memcpy / memset source to meet alignment requirement!");
04008   // If 'SrcAlign' is zero, that means the memory operation does not need to
04009   // load the value, i.e. memset or memcpy from constant string. Otherwise,
04010   // it's the inferred alignment of the source. 'DstAlign', on the other hand,
04011   // is the specified alignment of the memory operation. If it is zero, that
04012   // means it's possible to change the alignment of the destination.
04013   // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
04014   // not need to be loaded.
04015   EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
04016                                    IsMemset, ZeroMemset, MemcpyStrSrc,
04017                                    DAG.getMachineFunction());
04018 
04019   if (VT == MVT::Other) {
04020     unsigned AS = 0;
04021     if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
04022         TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
04023       VT = TLI.getPointerTy();
04024     } else {
04025       switch (DstAlign & 7) {
04026       case 0:  VT = MVT::i64; break;
04027       case 4:  VT = MVT::i32; break;
04028       case 2:  VT = MVT::i16; break;
04029       default: VT = MVT::i8;  break;
04030       }
04031     }
04032 
04033     MVT LVT = MVT::i64;
04034     while (!TLI.isTypeLegal(LVT))
04035       LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
04036     assert(LVT.isInteger());
04037 
04038     if (VT.bitsGT(LVT))
04039       VT = LVT;
04040   }
04041 
04042   unsigned NumMemOps = 0;
04043   while (Size != 0) {
04044     unsigned VTSize = VT.getSizeInBits() / 8;
04045     while (VTSize > Size) {
04046       // For now, only use non-vector load / store's for the left-over pieces.
04047       EVT NewVT = VT;
04048       unsigned NewVTSize;
04049 
04050       bool Found = false;
04051       if (VT.isVector() || VT.isFloatingPoint()) {
04052         NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
04053         if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
04054             TLI.isSafeMemOpType(NewVT.getSimpleVT()))
04055           Found = true;
04056         else if (NewVT == MVT::i64 &&
04057                  TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
04058                  TLI.isSafeMemOpType(MVT::f64)) {
04059           // i64 is usually not legal on 32-bit targets, but f64 may be.
04060           NewVT = MVT::f64;
04061           Found = true;
04062         }
04063       }
04064 
04065       if (!Found) {
04066         do {
04067           NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
04068           if (NewVT == MVT::i8)
04069             break;
04070         } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
04071       }
04072       NewVTSize = NewVT.getSizeInBits() / 8;
04073 
04074       // If the new VT cannot cover all of the remaining bits, then consider
04075       // issuing a (or a pair of) unaligned and overlapping load / store.
04076       // FIXME: Only does this for 64-bit or more since we don't have proper
04077       // cost model for unaligned load / store.
04078       bool Fast;
04079       unsigned AS = 0;
04080       if (NumMemOps && AllowOverlap &&
04081           VTSize >= 8 && NewVTSize < Size &&
04082           TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
04083         VTSize = Size;
04084       else {
04085         VT = NewVT;
04086         VTSize = NewVTSize;
04087       }
04088     }
04089 
04090     if (++NumMemOps > Limit)
04091       return false;
04092 
04093     MemOps.push_back(VT);
04094     Size -= VTSize;
04095   }
04096 
04097   return true;
04098 }
04099 
04100 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
04101                                        SDValue Chain, SDValue Dst,
04102                                        SDValue Src, uint64_t Size,
04103                                        unsigned Align, bool isVol,
04104                                        bool AlwaysInline,
04105                                        MachinePointerInfo DstPtrInfo,
04106                                        MachinePointerInfo SrcPtrInfo) {
04107   // Turn a memcpy of undef to nop.
04108   if (Src.getOpcode() == ISD::UNDEF)
04109     return Chain;
04110 
04111   // Expand memcpy to a series of load and store ops if the size operand falls
04112   // below a certain threshold.
04113   // TODO: In the AlwaysInline case, if the size is big then generate a loop
04114   // rather than maybe a humongous number of loads and stores.
04115   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
04116   std::vector<EVT> MemOps;
04117   bool DstAlignCanChange = false;
04118   MachineFunction &MF = DAG.getMachineFunction();
04119   MachineFrameInfo *MFI = MF.getFrameInfo();
04120   bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
04121   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
04122   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
04123     DstAlignCanChange = true;
04124   unsigned SrcAlign = DAG.InferPtrAlignment(Src);
04125   if (Align > SrcAlign)
04126     SrcAlign = Align;
04127   StringRef Str;
04128   bool CopyFromStr = isMemSrcFromString(Src, Str);
04129   bool isZeroStr = CopyFromStr && Str.empty();
04130   unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
04131 
04132   if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
04133                                 (DstAlignCanChange ? 0 : Align),
04134                                 (isZeroStr ? 0 : SrcAlign),
04135                                 false, false, CopyFromStr, true, DAG, TLI))
04136     return SDValue();
04137 
04138   if (DstAlignCanChange) {
04139     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
04140     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
04141 
04142     // Don't promote to an alignment that would require dynamic stack
04143     // realignment.
04144     const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
04145     if (!TRI->needsStackRealignment(MF))
04146        while (NewAlign > Align &&
04147              TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
04148           NewAlign /= 2;
04149 
04150     if (NewAlign > Align) {
04151       // Give the stack frame object a larger alignment if needed.
04152       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
04153         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
04154       Align = NewAlign;
04155     }
04156   }
04157 
04158   SmallVector<SDValue, 8> OutChains;
04159   unsigned NumMemOps = MemOps.size();
04160   uint64_t SrcOff = 0, DstOff = 0;
04161   for (unsigned i = 0; i != NumMemOps; ++i) {
04162     EVT VT = MemOps[i];
04163     unsigned VTSize = VT.getSizeInBits() / 8;
04164     SDValue Value, Store;
04165 
04166     if (VTSize > Size) {
04167       // Issuing an unaligned load / store pair  that overlaps with the previous
04168       // pair. Adjust the offset accordingly.
04169       assert(i == NumMemOps-1 && i != 0);
04170       SrcOff -= VTSize - Size;
04171       DstOff -= VTSize - Size;
04172     }
04173 
04174     if (CopyFromStr &&
04175         (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
04176       // It's unlikely a store of a vector immediate can be done in a single
04177       // instruction. It would require a load from a constantpool first.
04178       // We only handle zero vectors here.
04179       // FIXME: Handle other cases where store of vector immediate is done in
04180       // a single instruction.
04181       Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
04182       if (Value.getNode())
04183         Store = DAG.getStore(Chain, dl, Value,
04184                              getMemBasePlusOffset(Dst, DstOff, dl, DAG),
04185                              DstPtrInfo.getWithOffset(DstOff), isVol,
04186                              false, Align);
04187     }
04188 
04189     if (!Store.getNode()) {
04190       // The type might not be legal for the target.  This should only happen
04191       // if the type is smaller than a legal type, as on PPC, so the right
04192       // thing to do is generate a LoadExt/StoreTrunc pair.  These simplify
04193       // to Load/Store if NVT==VT.
04194       // FIXME does the case above also need this?
04195       EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
04196       assert(NVT.bitsGE(VT));
04197       Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
04198                              getMemBasePlusOffset(Src, SrcOff, dl, DAG),
04199                              SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
04200                              false, MinAlign(SrcAlign, SrcOff));
04201       Store = DAG.getTruncStore(Chain, dl, Value,
04202                                 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
04203                                 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
04204                                 false, Align);
04205     }
04206     OutChains.push_back(Store);
04207     SrcOff += VTSize;
04208     DstOff += VTSize;
04209     Size -= VTSize;
04210   }
04211 
04212   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
04213 }
04214 
04215 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
04216                                         SDValue Chain, SDValue Dst,
04217                                         SDValue Src, uint64_t Size,
04218                                         unsigned Align,  bool isVol,
04219                                         bool AlwaysInline,
04220                                         MachinePointerInfo DstPtrInfo,
04221                                         MachinePointerInfo SrcPtrInfo) {
04222   // Turn a memmove of undef to nop.
04223   if (Src.getOpcode() == ISD::UNDEF)
04224     return Chain;
04225 
04226   // Expand memmove to a series of load and store ops if the size operand falls
04227   // below a certain threshold.
04228   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
04229   std::vector<EVT> MemOps;
04230   bool DstAlignCanChange = false;
04231   MachineFunction &MF = DAG.getMachineFunction();
04232   MachineFrameInfo *MFI = MF.getFrameInfo();
04233   bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
04234   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
04235   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
04236     DstAlignCanChange = true;
04237   unsigned SrcAlign = DAG.InferPtrAlignment(Src);
04238   if (Align > SrcAlign)
04239     SrcAlign = Align;
04240   unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
04241 
04242   if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
04243                                 (DstAlignCanChange ? 0 : Align), SrcAlign,
04244                                 false, false, false, false, DAG, TLI))
04245     return SDValue();
04246 
04247   if (DstAlignCanChange) {
04248     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
04249     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
04250     if (NewAlign > Align) {
04251       // Give the stack frame object a larger alignment if needed.
04252       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
04253         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
04254       Align = NewAlign;
04255     }
04256   }
04257 
04258   uint64_t SrcOff = 0, DstOff = 0;
04259   SmallVector<SDValue, 8> LoadValues;
04260   SmallVector<SDValue, 8> LoadChains;
04261   SmallVector<SDValue, 8> OutChains;
04262   unsigned NumMemOps = MemOps.size();
04263   for (unsigned i = 0; i < NumMemOps; i++) {
04264     EVT VT = MemOps[i];
04265     unsigned VTSize = VT.getSizeInBits() / 8;
04266     SDValue Value;
04267 
04268     Value = DAG.getLoad(VT, dl, Chain,
04269                         getMemBasePlusOffset(Src, SrcOff, dl, DAG),
04270                         SrcPtrInfo.getWithOffset(SrcOff), isVol,
04271                         false, false, SrcAlign);
04272     LoadValues.push_back(Value);
04273     LoadChains.push_back(Value.getValue(1));
04274     SrcOff += VTSize;
04275   }
04276   Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
04277   OutChains.clear();
04278   for (unsigned i = 0; i < NumMemOps; i++) {
04279     EVT VT = MemOps[i];
04280     unsigned VTSize = VT.getSizeInBits() / 8;
04281     SDValue Store;
04282 
04283     Store = DAG.getStore(Chain, dl, LoadValues[i],
04284                          getMemBasePlusOffset(Dst, DstOff, dl, DAG),
04285                          DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
04286     OutChains.push_back(Store);
04287     DstOff += VTSize;
04288   }
04289 
04290   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
04291 }
04292 
04293 /// \brief Lower the call to 'memset' intrinsic function into a series of store
04294 /// operations.
04295 ///
04296 /// \param DAG Selection DAG where lowered code is placed.
04297 /// \param dl Link to corresponding IR location.
04298 /// \param Chain Control flow dependency.
04299 /// \param Dst Pointer to destination memory location.
04300 /// \param Src Value of byte to write into the memory.
04301 /// \param Size Number of bytes to write.
04302 /// \param Align Alignment of the destination in bytes.
04303 /// \param isVol True if destination is volatile.
04304 /// \param DstPtrInfo IR information on the memory pointer.
04305 /// \returns New head in the control flow, if lowering was successful, empty
04306 /// SDValue otherwise.
04307 ///
04308 /// The function tries to replace 'llvm.memset' intrinsic with several store
04309 /// operations and value calculation code. This is usually profitable for small
04310 /// memory size.
04311 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
04312                                SDValue Chain, SDValue Dst,
04313                                SDValue Src, uint64_t Size,
04314                                unsigned Align, bool isVol,
04315                                MachinePointerInfo DstPtrInfo) {
04316   // Turn a memset of undef to nop.
04317   if (Src.getOpcode() == ISD::UNDEF)
04318     return Chain;
04319 
04320   // Expand memset to a series of load/store ops if the size operand
04321   // falls below a certain threshold.
04322   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
04323   std::vector<EVT> MemOps;
04324   bool DstAlignCanChange = false;
04325   MachineFunction &MF = DAG.getMachineFunction();
04326   MachineFrameInfo *MFI = MF.getFrameInfo();
04327   bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
04328   FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
04329   if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
04330     DstAlignCanChange = true;
04331   bool IsZeroVal =
04332     isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
04333   if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
04334                                 Size, (DstAlignCanChange ? 0 : Align), 0,
04335                                 true, IsZeroVal, false, true, DAG, TLI))
04336     return SDValue();
04337 
04338   if (DstAlignCanChange) {
04339     Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
04340     unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
04341     if (NewAlign > Align) {
04342       // Give the stack frame object a larger alignment if needed.
04343       if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
04344         MFI->setObjectAlignment(FI->getIndex(), NewAlign);
04345       Align = NewAlign;
04346     }
04347   }
04348 
04349   SmallVector<SDValue, 8> OutChains;
04350   uint64_t DstOff = 0;
04351   unsigned NumMemOps = MemOps.size();
04352 
04353   // Find the largest store and generate the bit pattern for it.
04354   EVT LargestVT = MemOps[0];
04355   for (unsigned i = 1; i < NumMemOps; i++)
04356     if (MemOps[i].bitsGT(LargestVT))
04357       LargestVT = MemOps[i];
04358   SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
04359 
04360   for (unsigned i = 0; i < NumMemOps; i++) {
04361     EVT VT = MemOps[i];
04362     unsigned VTSize = VT.getSizeInBits() / 8;
04363     if (VTSize > Size) {
04364       // Issuing an unaligned load / store pair  that overlaps with the previous
04365       // pair. Adjust the offset accordingly.
04366       assert(i == NumMemOps-1 && i != 0);
04367       DstOff -= VTSize - Size;
04368     }
04369 
04370     // If this store is smaller than the largest store see whether we can get
04371     // the smaller value for free with a truncate.
04372     SDValue Value = MemSetValue;
04373     if (VT.bitsLT(LargestVT)) {
04374       if (!LargestVT.isVector() && !VT.isVector() &&
04375           TLI.isTruncateFree(LargestVT, VT))
04376         Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
04377       else
04378         Value = getMemsetValue(Src, VT, DAG, dl);
04379     }
04380     assert(Value.getValueType() == VT && "Value with wrong type.");
04381     SDValue Store = DAG.getStore(Chain, dl, Value,
04382                                  getMemBasePlusOffset(Dst, DstOff, dl, DAG),
04383                                  DstPtrInfo.getWithOffset(DstOff),
04384                                  isVol, false, Align);
04385     OutChains.push_back(Store);
04386     DstOff += VT.getSizeInBits() / 8;
04387     Size -= VTSize;
04388   }
04389 
04390   return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
04391 }
04392 
04393 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
04394                                 SDValue Src, SDValue Size,
04395                                 unsigned Align, bool isVol, bool AlwaysInline,
04396                                 bool isTailCall, MachinePointerInfo DstPtrInfo,
04397                                 MachinePointerInfo SrcPtrInfo) {
04398   assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
04399 
04400   // Check to see if we should lower the memcpy to loads and stores first.
04401   // For cases within the target-specified limits, this is the best choice.
04402   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
04403   if (ConstantSize) {
04404     // Memcpy with size zero? Just return the original chain.
04405     if (ConstantSize->isNullValue())
04406       return Chain;
04407 
04408     SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
04409                                              ConstantSize->getZExtValue(),Align,
04410                                 isVol, false, DstPtrInfo, SrcPtrInfo);
04411     if (Result.getNode())
04412       return Result;
04413   }
04414 
04415   // Then check to see if we should lower the memcpy with target-specific
04416   // code. If the target chooses to do this, this is the next best.
04417   if (TSI) {
04418     SDValue Result = TSI->EmitTargetCodeForMemcpy(
04419         *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
04420         DstPtrInfo, SrcPtrInfo);
04421     if (Result.getNode())
04422       return Result;
04423   }
04424 
04425   // If we really need inline code and the target declined to provide it,
04426   // use a (potentially long) sequence of loads and stores.
04427   if (AlwaysInline) {
04428     assert(ConstantSize && "AlwaysInline requires a constant size!");
04429     return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
04430                                    ConstantSize->getZExtValue(), Align, isVol,
04431                                    true, DstPtrInfo, SrcPtrInfo);
04432   }
04433 
04434   // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
04435   // memcpy is not guaranteed to be safe. libc memcpys aren't required to
04436   // respect volatile, so they may do things like read or write memory
04437   // beyond the given memory regions. But fixing this isn't easy, and most
04438   // people don't care.
04439 
04440   // Emit a library call.
04441   TargetLowering::ArgListTy Args;
04442   TargetLowering::ArgListEntry Entry;
04443   Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
04444   Entry.Node = Dst; Args.push_back(Entry);
04445   Entry.Node = Src; Args.push_back(Entry);
04446   Entry.Node = Size; Args.push_back(Entry);
04447   // FIXME: pass in SDLoc
04448   TargetLowering::CallLoweringInfo CLI(*this);
04449   CLI.setDebugLoc(dl).setChain(Chain)
04450     .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
04451                Type::getVoidTy(*getContext()),
04452                getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
04453                                  TLI->getPointerTy()), std::move(Args), 0)
04454     .setDiscardResult()
04455     .setTailCall(isTailCall);
04456 
04457   std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
04458   return CallResult.second;
04459 }
04460 
04461 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
04462                                  SDValue Src, SDValue Size,
04463                                  unsigned Align, bool isVol, bool isTailCall,
04464                                  MachinePointerInfo DstPtrInfo,
04465                                  MachinePointerInfo SrcPtrInfo) {
04466   assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
04467 
04468   // Check to see if we should lower the memmove to loads and stores first.
04469   // For cases within the target-specified limits, this is the best choice.
04470   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
04471   if (ConstantSize) {
04472     // Memmove with size zero? Just return the original chain.
04473     if (ConstantSize->isNullValue())
04474       return Chain;
04475 
04476     SDValue Result =
04477       getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
04478                                ConstantSize->getZExtValue(), Align, isVol,
04479                                false, DstPtrInfo, SrcPtrInfo);
04480     if (Result.getNode())
04481       return Result;
04482   }
04483 
04484   // Then check to see if we should lower the memmove with target-specific
04485   // code. If the target chooses to do this, this is the next best.
04486   if (TSI) {
04487     SDValue Result = TSI->EmitTargetCodeForMemmove(
04488         *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
04489     if (Result.getNode())
04490       return Result;
04491   }
04492 
04493   // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
04494   // not be safe.  See memcpy above for more details.
04495 
04496   // Emit a library call.
04497   TargetLowering::ArgListTy Args;
04498   TargetLowering::ArgListEntry Entry;
04499   Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
04500   Entry.Node = Dst; Args.push_back(Entry);
04501   Entry.Node = Src; Args.push_back(Entry);
04502   Entry.Node = Size; Args.push_back(Entry);
04503   // FIXME:  pass in SDLoc
04504   TargetLowering::CallLoweringInfo CLI(*this);
04505   CLI.setDebugLoc(dl).setChain(Chain)
04506     .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
04507                Type::getVoidTy(*getContext()),
04508                getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
04509                                  TLI->getPointerTy()), std::move(Args), 0)
04510     .setDiscardResult()
04511     .setTailCall(isTailCall);
04512 
04513   std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
04514   return CallResult.second;
04515 }
04516 
04517 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
04518                                 SDValue Src, SDValue Size,
04519                                 unsigned Align, bool isVol, bool isTailCall,
04520                                 MachinePointerInfo DstPtrInfo) {
04521   assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
04522 
04523   // Check to see if we should lower the memset to stores first.
04524   // For cases within the target-specified limits, this is the best choice.
04525   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
04526   if (ConstantSize) {
04527     // Memset with size zero? Just return the original chain.
04528     if (ConstantSize->isNullValue())
04529       return Chain;
04530 
04531     SDValue Result =
04532       getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
04533                       Align, isVol, DstPtrInfo);
04534 
04535     if (Result.getNode())
04536       return Result;
04537   }
04538 
04539   // Then check to see if we should lower the memset with target-specific
04540   // code. If the target chooses to do this, this is the next best.
04541   if (TSI) {
04542     SDValue Result = TSI->EmitTargetCodeForMemset(
04543         *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
04544     if (Result.getNode())
04545       return Result;
04546   }
04547 
04548   // Emit a library call.
04549   Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
04550   TargetLowering::ArgListTy Args;
04551   TargetLowering::ArgListEntry Entry;
04552   Entry.Node = Dst; Entry.Ty = IntPtrTy;
04553   Args.push_back(Entry);
04554   Entry.Node = Src;
04555   Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
04556   Args.push_back(Entry);
04557   Entry.Node = Size;
04558   Entry.Ty = IntPtrTy;
04559   Args.push_back(Entry);
04560 
04561   // FIXME: pass in SDLoc
04562   TargetLowering::CallLoweringInfo CLI(*this);
04563   CLI.setDebugLoc(dl).setChain(Chain)
04564     .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
04565                Type::getVoidTy(*getContext()),
04566                getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
04567                                  TLI->getPointerTy()), std::move(Args), 0)
04568     .setDiscardResult()
04569     .setTailCall(isTailCall);
04570 
04571   std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
04572   return CallResult.second;
04573 }
04574 
04575 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
04576                                 SDVTList VTList, ArrayRef<SDValue> Ops,
04577                                 MachineMemOperand *MMO,
04578                                 AtomicOrdering SuccessOrdering,
04579                                 AtomicOrdering FailureOrdering,
04580                                 SynchronizationScope SynchScope) {
04581   FoldingSetNodeID ID;
04582   ID.AddInteger(MemVT.getRawBits());
04583   AddNodeIDNode(ID, Opcode, VTList, Ops);
04584   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
04585   void* IP = nullptr;
04586   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
04587     cast<AtomicSDNode>(E)->refineAlignment(MMO);
04588     return SDValue(E, 0);
04589   }
04590 
04591   // Allocate the operands array for the node out of the BumpPtrAllocator, since
04592   // SDNode doesn't have access to it.  This memory will be "leaked" when
04593   // the node is deallocated, but recovered when the allocator is released.
04594   // If the number of operands is less than 5 we use AtomicSDNode's internal
04595   // storage.
04596   unsigned NumOps = Ops.size();
04597   SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
04598                              : nullptr;
04599 
04600   SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
04601                                                dl.getDebugLoc(), VTList, MemVT,
04602                                                Ops.data(), DynOps, NumOps, MMO,
04603                                                SuccessOrdering, FailureOrdering,
04604                                                SynchScope);
04605   CSEMap.InsertNode(N, IP);
04606   InsertNode(N);
04607   return SDValue(N, 0);
04608 }
04609 
04610 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
04611                                 SDVTList VTList, ArrayRef<SDValue> Ops,
04612                                 MachineMemOperand *MMO,
04613                                 AtomicOrdering Ordering,
04614                                 SynchronizationScope SynchScope) {
04615   return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
04616                    Ordering, SynchScope);
04617 }
04618 
04619 SDValue SelectionDAG::getAtomicCmpSwap(
04620     unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
04621     SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
04622     unsigned Alignment, AtomicOrdering SuccessOrdering,
04623     AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
04624   assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
04625          Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
04626   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
04627 
04628   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
04629     Alignment = getEVTAlignment(MemVT);
04630 
04631   MachineFunction &MF = getMachineFunction();
04632 
04633   // FIXME: Volatile isn't really correct; we should keep track of atomic
04634   // orderings in the memoperand.
04635   unsigned Flags = MachineMemOperand::MOVolatile;
04636   Flags |= MachineMemOperand::MOLoad;
04637   Flags |= MachineMemOperand::MOStore;
04638 
04639   MachineMemOperand *MMO =
04640     MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
04641 
04642   return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
04643                           SuccessOrdering, FailureOrdering, SynchScope);
04644 }
04645 
04646 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
04647                                        SDVTList VTs, SDValue Chain, SDValue Ptr,
04648                                        SDValue Cmp, SDValue Swp,
04649                                        MachineMemOperand *MMO,
04650                                        AtomicOrdering SuccessOrdering,
04651                                        AtomicOrdering FailureOrdering,
04652                                        SynchronizationScope SynchScope) {
04653   assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
04654          Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
04655   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
04656 
04657   SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
04658   return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
04659                    SuccessOrdering, FailureOrdering, SynchScope);
04660 }
04661 
04662 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
04663                                 SDValue Chain,
04664                                 SDValue Ptr, SDValue Val,
04665                                 const Value* PtrVal,
04666                                 unsigned Alignment,
04667                                 AtomicOrdering Ordering,
04668                                 SynchronizationScope SynchScope) {
04669   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
04670     Alignment = getEVTAlignment(MemVT);
04671 
04672   MachineFunction &MF = getMachineFunction();
04673   // An atomic store does not load. An atomic load does not store.
04674   // (An atomicrmw obviously both loads and stores.)
04675   // For now, atomics are considered to be volatile always, and they are
04676   // chained as such.
04677   // FIXME: Volatile isn't really correct; we should keep track of atomic
04678   // orderings in the memoperand.
04679   unsigned Flags = MachineMemOperand::MOVolatile;
04680   if (Opcode != ISD::ATOMIC_STORE)
04681     Flags |= MachineMemOperand::MOLoad;
04682   if (Opcode != ISD::ATOMIC_LOAD)
04683     Flags |= MachineMemOperand::MOStore;
04684 
04685   MachineMemOperand *MMO =
04686     MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
04687                             MemVT.getStoreSize(), Alignment);
04688 
04689   return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
04690                    Ordering, SynchScope);
04691 }
04692 
04693 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
04694                                 SDValue Chain,
04695                                 SDValue Ptr, SDValue Val,
04696                                 MachineMemOperand *MMO,
04697                                 AtomicOrdering Ordering,
04698                                 SynchronizationScope SynchScope) {
04699   assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
04700           Opcode == ISD::ATOMIC_LOAD_SUB ||
04701           Opcode == ISD::ATOMIC_LOAD_AND ||
04702           Opcode == ISD::ATOMIC_LOAD_OR ||
04703           Opcode == ISD::ATOMIC_LOAD_XOR ||
04704           Opcode == ISD::ATOMIC_LOAD_NAND ||
04705           Opcode == ISD::ATOMIC_LOAD_MIN ||
04706           Opcode == ISD::ATOMIC_LOAD_MAX ||
04707           Opcode == ISD::ATOMIC_LOAD_UMIN ||
04708           Opcode == ISD::ATOMIC_LOAD_UMAX ||
04709           Opcode == ISD::ATOMIC_SWAP ||
04710           Opcode == ISD::ATOMIC_STORE) &&
04711          "Invalid Atomic Op");
04712 
04713   EVT VT = Val.getValueType();
04714 
04715   SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
04716                                                getVTList(VT, MVT::Other);
04717   SDValue Ops[] = {Chain, Ptr, Val};
04718   return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
04719 }
04720 
04721 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
04722                                 EVT VT, SDValue Chain,
04723                                 SDValue Ptr,
04724                                 MachineMemOperand *MMO,
04725                                 AtomicOrdering Ordering,
04726                                 SynchronizationScope SynchScope) {
04727   assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
04728 
04729   SDVTList VTs = getVTList(VT, MVT::Other);
04730   SDValue Ops[] = {Chain, Ptr};
04731   return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
04732 }
04733 
04734 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
04735 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
04736   if (Ops.size() == 1)
04737     return Ops[0];
04738 
04739   SmallVector<EVT, 4> VTs;
04740   VTs.reserve(Ops.size());
04741   for (unsigned i = 0; i < Ops.size(); ++i)
04742     VTs.push_back(Ops[i].getValueType());
04743   return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
04744 }
04745 
04746 SDValue
04747 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
04748                                   ArrayRef<SDValue> Ops,
04749                                   EVT MemVT, MachinePointerInfo PtrInfo,
04750                                   unsigned Align, bool Vol,
04751                                   bool ReadMem, bool WriteMem, unsigned Size) {
04752   if (Align == 0)  // Ensure that codegen never sees alignment 0
04753     Align = getEVTAlignment(MemVT);
04754 
04755   MachineFunction &MF = getMachineFunction();
04756   unsigned Flags = 0;
04757   if (WriteMem)
04758     Flags |= MachineMemOperand::MOStore;
04759   if (ReadMem)
04760     Flags |= MachineMemOperand::MOLoad;
04761   if (Vol)
04762     Flags |= MachineMemOperand::MOVolatile;
04763   if (!Size)
04764     Size = MemVT.getStoreSize();
04765   MachineMemOperand *MMO =
04766     MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
04767 
04768   return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
04769 }
04770 
04771 SDValue
04772 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
04773                                   ArrayRef<SDValue> Ops, EVT MemVT,
04774                                   MachineMemOperand *MMO) {
04775   assert((Opcode == ISD::INTRINSIC_VOID ||
04776           Opcode == ISD::INTRINSIC_W_CHAIN ||
04777           Opcode == ISD::PREFETCH ||
04778           Opcode == ISD::LIFETIME_START ||
04779           Opcode == ISD::LIFETIME_END ||
04780           (Opcode <= INT_MAX &&
04781            (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
04782          "Opcode is not a memory-accessing opcode!");
04783 
04784   // Memoize the node unless it returns a flag.
04785   MemIntrinsicSDNode *N;
04786   if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
04787     FoldingSetNodeID ID;
04788     AddNodeIDNode(ID, Opcode, VTList, Ops);
04789     ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
04790     void *IP = nullptr;
04791     if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
04792       cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
04793       return SDValue(E, 0);
04794     }
04795 
04796     N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
04797                                                dl.getDebugLoc(), VTList, Ops,
04798                                                MemVT, MMO);
04799     CSEMap.InsertNode(N, IP);
04800   } else {
04801     N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
04802                                                dl.getDebugLoc(), VTList, Ops,
04803                                                MemVT, MMO);
04804   }
04805   InsertNode(N);
04806   return SDValue(N, 0);
04807 }
04808 
04809 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
04810 /// MachinePointerInfo record from it.  This is particularly useful because the
04811 /// code generator has many cases where it doesn't bother passing in a
04812 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
04813 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
04814   // If this is FI+Offset, we can model it.
04815   if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
04816     return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
04817 
04818   // If this is (FI+Offset1)+Offset2, we can model it.
04819   if (Ptr.getOpcode() != ISD::ADD ||
04820       !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
04821       !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
04822     return MachinePointerInfo();
04823 
04824   int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
04825   return MachinePointerInfo::getFixedStack(FI, Offset+
04826                        cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
04827 }
04828 
04829 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
04830 /// MachinePointerInfo record from it.  This is particularly useful because the
04831 /// code generator has many cases where it doesn't bother passing in a
04832 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
04833 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
04834   // If the 'Offset' value isn't a constant, we can't handle this.
04835   if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
04836     return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
04837   if (OffsetOp.getOpcode() == ISD::UNDEF)
04838     return InferPointerInfo(Ptr);
04839   return MachinePointerInfo();
04840 }
04841 
04842 
04843 SDValue
04844 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
04845                       EVT VT, SDLoc dl, SDValue Chain,
04846                       SDValue Ptr, SDValue Offset,
04847                       MachinePointerInfo PtrInfo, EVT MemVT,
04848                       bool isVolatile, bool isNonTemporal, bool isInvariant,
04849                       unsigned Alignment, const AAMDNodes &AAInfo,
04850                       const MDNode *Ranges) {
04851   assert(Chain.getValueType() == MVT::Other &&
04852         "Invalid chain type");
04853   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
04854     Alignment = getEVTAlignment(VT);
04855 
04856   unsigned Flags = MachineMemOperand::MOLoad;
04857   if (isVolatile)
04858     Flags |= MachineMemOperand::MOVolatile;
04859   if (isNonTemporal)
04860     Flags |= MachineMemOperand::MONonTemporal;
04861   if (isInvariant)
04862     Flags |= MachineMemOperand::MOInvariant;
04863 
04864   // If we don't have a PtrInfo, infer the trivial frame index case to simplify
04865   // clients.
04866   if (PtrInfo.V.isNull())
04867     PtrInfo = InferPointerInfo(Ptr, Offset);
04868 
04869   MachineFunction &MF = getMachineFunction();
04870   MachineMemOperand *MMO =
04871     MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
04872                             AAInfo, Ranges);
04873   return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
04874 }
04875 
04876 SDValue
04877 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
04878                       EVT VT, SDLoc dl, SDValue Chain,
04879                       SDValue Ptr, SDValue Offset, EVT MemVT,
04880                       MachineMemOperand *MMO) {
04881   if (VT == MemVT) {
04882     ExtType = ISD::NON_EXTLOAD;
04883   } else if (ExtType == ISD::NON_EXTLOAD) {
04884     assert(VT == MemVT && "Non-extending load from different memory type!");
04885   } else {
04886     // Extending load.
04887     assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
04888            "Should only be an extending load, not truncating!");
04889     assert(VT.isInteger() == MemVT.isInteger() &&
04890            "Cannot convert from FP to Int or Int -> FP!");
04891     assert(VT.isVector() == MemVT.isVector() &&
04892            "Cannot use an ext load to convert to or from a vector!");
04893     assert((!VT.isVector() ||
04894             VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
04895            "Cannot use an ext load to change the number of vector elements!");
04896   }
04897 
04898   bool Indexed = AM != ISD::UNINDEXED;
04899   assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
04900          "Unindexed load with an offset!");
04901 
04902   SDVTList VTs = Indexed ?
04903     getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
04904   SDValue Ops[] = { Chain, Ptr, Offset };
04905   FoldingSetNodeID ID;
04906   AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
04907   ID.AddInteger(MemVT.getRawBits());
04908   ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
04909                                      MMO->isNonTemporal(),
04910                                      MMO->isInvariant()));
04911   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
04912   void *IP = nullptr;
04913   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
04914     cast<LoadSDNode>(E)->refineAlignment(MMO);
04915     return SDValue(E, 0);
04916   }
04917   SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
04918                                              dl.getDebugLoc(), VTs, AM, ExtType,
04919                                              MemVT, MMO);
04920   CSEMap.InsertNode(N, IP);
04921   InsertNode(N);
04922   return SDValue(N, 0);
04923 }
04924 
04925 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
04926                               SDValue Chain, SDValue Ptr,
04927                               MachinePointerInfo PtrInfo,
04928                               bool isVolatile, bool isNonTemporal,
04929                               bool isInvariant, unsigned Alignment,
04930                               const AAMDNodes &AAInfo,
04931                               const MDNode *Ranges) {
04932   SDValue Undef = getUNDEF(Ptr.getValueType());
04933   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
04934                  PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
04935                  AAInfo, Ranges);
04936 }
04937 
04938 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
04939                               SDValue Chain, SDValue Ptr,
04940                               MachineMemOperand *MMO) {
04941   SDValue Undef = getUNDEF(Ptr.getValueType());
04942   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
04943                  VT, MMO);
04944 }
04945 
04946 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
04947                                  SDValue Chain, SDValue Ptr,
04948                                  MachinePointerInfo PtrInfo, EVT MemVT,
04949                                  bool isVolatile, bool isNonTemporal,
04950                                  bool isInvariant, unsigned Alignment,
04951                                  const AAMDNodes &AAInfo) {
04952   SDValue Undef = getUNDEF(Ptr.getValueType());
04953   return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
04954                  PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
04955                  Alignment, AAInfo);
04956 }
04957 
04958 
04959 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
04960                                  SDValue Chain, SDValue Ptr, EVT MemVT,
04961                                  MachineMemOperand *MMO) {
04962   SDValue Undef = getUNDEF(Ptr.getValueType());
04963   return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
04964                  MemVT, MMO);
04965 }
04966 
04967 SDValue
04968 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
04969                              SDValue Offset, ISD::MemIndexedMode AM) {
04970   LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
04971   assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
04972          "Load is already a indexed load!");
04973   return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
04974                  LD->getChain(), Base, Offset, LD->getPointerInfo(),
04975                  LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
04976                  false, LD->getAlignment());
04977 }
04978 
04979 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
04980                                SDValue Ptr, MachinePointerInfo PtrInfo,
04981                                bool isVolatile, bool isNonTemporal,
04982                                unsigned Alignment, const AAMDNodes &AAInfo) {
04983   assert(Chain.getValueType() == MVT::Other &&
04984         "Invalid chain type");
04985   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
04986     Alignment = getEVTAlignment(Val.getValueType());
04987 
04988   unsigned Flags = MachineMemOperand::MOStore;
04989   if (isVolatile)
04990     Flags |= MachineMemOperand::MOVolatile;
04991   if (isNonTemporal)
04992     Flags |= MachineMemOperand::MONonTemporal;
04993 
04994   if (PtrInfo.V.isNull())
04995     PtrInfo = InferPointerInfo(Ptr);
04996 
04997   MachineFunction &MF = getMachineFunction();
04998   MachineMemOperand *MMO =
04999     MF.getMachineMemOperand(PtrInfo, Flags,
05000                             Val.getValueType().getStoreSize(), Alignment,
05001                             AAInfo);
05002 
05003   return getStore(Chain, dl, Val, Ptr, MMO);
05004 }
05005 
05006 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
05007                                SDValue Ptr, MachineMemOperand *MMO) {
05008   assert(Chain.getValueType() == MVT::Other &&
05009         "Invalid chain type");
05010   EVT VT = Val.getValueType();
05011   SDVTList VTs = getVTList(MVT::Other);
05012   SDValue Undef = getUNDEF(Ptr.getValueType());
05013   SDValue Ops[] = { Chain, Val, Ptr, Undef };
05014   FoldingSetNodeID ID;
05015   AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
05016   ID.AddInteger(VT.getRawBits());
05017   ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
05018                                      MMO->isNonTemporal(), MMO->isInvariant()));
05019   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
05020   void *IP = nullptr;
05021   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
05022     cast<StoreSDNode>(E)->refineAlignment(MMO);
05023     return SDValue(E, 0);
05024   }
05025   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
05026                                               dl.getDebugLoc(), VTs,
05027                                               ISD::UNINDEXED, false, VT, MMO);
05028   CSEMap.InsertNode(N, IP);
05029   InsertNode(N);
05030   return SDValue(N, 0);
05031 }
05032 
05033 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
05034                                     SDValue Ptr, MachinePointerInfo PtrInfo,
05035                                     EVT SVT,bool isVolatile, bool isNonTemporal,
05036                                     unsigned Alignment,
05037                                     const AAMDNodes &AAInfo) {
05038   assert(Chain.getValueType() == MVT::Other &&
05039         "Invalid chain type");
05040   if (Alignment == 0)  // Ensure that codegen never sees alignment 0
05041     Alignment = getEVTAlignment(SVT);
05042 
05043   unsigned Flags = MachineMemOperand::MOStore;
05044   if (isVolatile)
05045     Flags |= MachineMemOperand::MOVolatile;
05046   if (isNonTemporal)
05047     Flags |= MachineMemOperand::MONonTemporal;
05048 
05049   if (PtrInfo.V.isNull())
05050     PtrInfo = InferPointerInfo(Ptr);
05051 
05052   MachineFunction &MF = getMachineFunction();
05053   MachineMemOperand *MMO =
05054     MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
05055                             AAInfo);
05056 
05057   return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
05058 }
05059 
05060 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
05061                                     SDValue Ptr, EVT SVT,
05062                                     MachineMemOperand *MMO) {
05063   EVT VT = Val.getValueType();
05064 
05065   assert(Chain.getValueType() == MVT::Other &&
05066         "Invalid chain type");
05067   if (VT == SVT)
05068     return getStore(Chain, dl, Val, Ptr, MMO);
05069 
05070   assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
05071          "Should only be a truncating store, not extending!");
05072   assert(VT.isInteger() == SVT.isInteger() &&
05073          "Can't do FP-INT conversion!");
05074   assert(VT.isVector() == SVT.isVector() &&
05075          "Cannot use trunc store to convert to or from a vector!");
05076   assert((!VT.isVector() ||
05077           VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
05078          "Cannot use trunc store to change the number of vector elements!");
05079 
05080   SDVTList VTs = getVTList(MVT::Other);
05081   SDValue Undef = getUNDEF(Ptr.getValueType());
05082   SDValue Ops[] = { Chain, Val, Ptr, Undef };
05083   FoldingSetNodeID ID;
05084   AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
05085   ID.AddInteger(SVT.getRawBits());
05086   ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
05087                                      MMO->isNonTemporal(), MMO->isInvariant()));
05088   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
05089   void *IP = nullptr;
05090   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
05091     cast<StoreSDNode>(E)->refineAlignment(MMO);
05092     return SDValue(E, 0);
05093   }
05094   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
05095                                               dl.getDebugLoc(), VTs,
05096                                               ISD::UNINDEXED, true, SVT, MMO);
05097   CSEMap.InsertNode(N, IP);
05098   InsertNode(N);
05099   return SDValue(N, 0);
05100 }
05101 
05102 SDValue
05103 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
05104                               SDValue Offset, ISD::MemIndexedMode AM) {
05105   StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
05106   assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
05107          "Store is already a indexed store!");
05108   SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
05109   SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
05110   FoldingSetNodeID ID;
05111   AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
05112   ID.AddInteger(ST->getMemoryVT().getRawBits());
05113   ID.AddInteger(ST->getRawSubclassData());
05114   ID.AddInteger(ST->getPointerInfo().getAddrSpace());
05115   void *IP = nullptr;
05116   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
05117     return SDValue(E, 0);
05118 
05119   SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
05120                                               dl.getDebugLoc(), VTs, AM,
05121                                               ST->isTruncatingStore(),
05122                                               ST->getMemoryVT(),
05123                                               ST->getMemOperand());
05124   CSEMap.InsertNode(N, IP);
05125   InsertNode(N);
05126   return SDValue(N, 0);
05127 }
05128 
05129 SDValue
05130 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
05131                             SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
05132                             MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
05133 
05134   SDVTList VTs = getVTList(VT, MVT::Other);
05135   SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
05136   FoldingSetNodeID ID;
05137   AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
05138   ID.AddInteger(VT.getRawBits());
05139   ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
05140                                      MMO->isVolatile(),
05141                                      MMO->isNonTemporal(),
05142                                      MMO->isInvariant()));
05143   ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
05144   void *IP = nullptr;
05145   if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
05146     cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
05147     return SDValue(E, 0);
05148   }
05149   SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
05150                                              dl.getDebugLoc(), Ops, 4, VTs,
05151                                              ExtTy, MemVT, MMO);
05152   CSEMap.InsertNode(N, IP);
05153   InsertNode(N);
05154   return SDValue(N, 0);
05155 }
05156 
05157 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
05158                                      SDValue Ptr, SDValue Mask, EVT MemVT,
05159                                      MachineMemOperand *MMO, bool isTrunc) {
05160   assert(Chain.getValueType() == MVT::Other &&
05161         "Invalid chain type");
05162   EVT VT = Val.getValueType();
05163   SDVTList VTs = getVTList(MVT::Other);
05164   SDValue Ops[] = { Chain, Ptr, Mask, Val };
05165