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