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