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