lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   1 //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SelectionDAG::Legalize method.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/ADT/SetVector.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/SmallSet.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Triple.h"
  20 #include "llvm/CodeGen/Analysis.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  23 #include "llvm/IR/CallingConv.h"
  24 #include "llvm/IR/Constants.h"
  25 #include "llvm/IR/DataLayout.h"
  26 #include "llvm/IR/DebugInfo.h"
  27 #include "llvm/IR/DerivedTypes.h"
  28 #include "llvm/IR/Function.h"
  29 #include "llvm/IR/LLVMContext.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Target/TargetFrameLowering.h"
  35 #include "llvm/Target/TargetLowering.h"
  36 #include "llvm/Target/TargetMachine.h"
  37 #include "llvm/Target/TargetSubtargetInfo.h"
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "legalizedag"
  41
  42 namespace {
  43
  44 struct FloatSignAsInt;
  45
  46 //===----------------------------------------------------------------------===//
  47 /// This takes an arbitrary SelectionDAG as input and
  48 /// hacks on it until the target machine can handle it.  This involves
  49 /// eliminating value sizes the machine cannot handle (promoting small sizes to
  50 /// large sizes or splitting up large values into small values) as well as
  51 /// eliminating operations the machine cannot handle.
  52 ///
  53 /// This code also does a small amount of optimization and recognition of idioms
  54 /// as part of its processing.  For example, if a target does not support a
  55 /// 'setcc' instruction efficiently, but does support 'brcc' instruction, this
  56 /// will attempt merge setcc and brc instructions into brcc's.
  57 ///
  58 class SelectionDAGLegalize {
  59   const TargetMachine &TM;
  60   const TargetLowering &TLI;
  61   SelectionDAG &DAG;
  62
  63   /// \brief The set of nodes which have already been legalized. We hold a
  64   /// reference to it in order to update as necessary on node deletion.
  65   SmallPtrSetImpl<SDNode *> &LegalizedNodes;
  66
  67   /// \brief A set of all the nodes updated during legalization.
  68   SmallSetVector<SDNode *, 16> *UpdatedNodes;
  69
  70   EVT getSetCCResultType(EVT VT) const {
  71     return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
  72   }
  73
  74   // Libcall insertion helpers.
  75
  76 public:
  77   SelectionDAGLegalize(SelectionDAG &DAG,
  78                        SmallPtrSetImpl<SDNode *> &LegalizedNodes,
  79                        SmallSetVector<SDNode *, 16> *UpdatedNodes = nullptr)
  80       : TM(DAG.getTarget()), TLI(DAG.getTargetLoweringInfo()), DAG(DAG),
  81         LegalizedNodes(LegalizedNodes), UpdatedNodes(UpdatedNodes) {}
  82
  83   /// \brief Legalizes the given operation.
  84   void LegalizeOp(SDNode *Node);
  85
  86 private:
  87   SDValue OptimizeFloatStore(StoreSDNode *ST);
  88
  89   void LegalizeLoadOps(SDNode *Node);
  90   void LegalizeStoreOps(SDNode *Node);
  91
  92   /// Some targets cannot handle a variable
  93   /// insertion index for the INSERT_VECTOR_ELT instruction.  In this case, it
  94   /// is necessary to spill the vector being inserted into to memory, perform
  95   /// the insert there, and then read the result back.
  96   SDValue PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val,
  97                                          SDValue Idx, SDLoc dl);
  98   SDValue ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val,
  99                                   SDValue Idx, SDLoc dl);
 100
 101   /// Return a vector shuffle operation which
 102   /// performs the same shuffe in terms of order or result bytes, but on a type
 103   /// whose vector element type is narrower than the original shuffle type.
 104   /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3>
 105   SDValue ShuffleWithNarrowerEltType(EVT NVT, EVT VT, SDLoc dl,
 106                                      SDValue N1, SDValue N2,
 107                                      ArrayRef<int> Mask) const;
 108
 109   bool LegalizeSetCCCondCode(EVT VT, SDValue &LHS, SDValue &RHS, SDValue &CC,
 110                              bool &NeedInvert, SDLoc dl);
 111
 112   SDValue ExpandLibCall(RTLIB::Libcall LC, SDNode *Node, bool isSigned);
 113   SDValue ExpandLibCall(RTLIB::Libcall LC, EVT RetVT, const SDValue *Ops,
 114                         unsigned NumOps, bool isSigned, SDLoc dl);
 115
 116   std::pair<SDValue, SDValue> ExpandChainLibCall(RTLIB::Libcall LC,
 117                                                  SDNode *Node, bool isSigned);
 118   SDValue ExpandFPLibCall(SDNode *Node, RTLIB::Libcall Call_F32,
 119                           RTLIB::Libcall Call_F64, RTLIB::Libcall Call_F80,
 120                           RTLIB::Libcall Call_F128,
 121                           RTLIB::Libcall Call_PPCF128);
 122   SDValue ExpandIntLibCall(SDNode *Node, bool isSigned,
 123                            RTLIB::Libcall Call_I8,
 124                            RTLIB::Libcall Call_I16,
 125                            RTLIB::Libcall Call_I32,
 126                            RTLIB::Libcall Call_I64,
 127                            RTLIB::Libcall Call_I128);
 128   void ExpandDivRemLibCall(SDNode *Node, SmallVectorImpl<SDValue> &Results);
 129   void ExpandSinCosLibCall(SDNode *Node, SmallVectorImpl<SDValue> &Results);
 130
 131   SDValue EmitStackConvert(SDValue SrcOp, EVT SlotVT, EVT DestVT, SDLoc dl);
 132   SDValue ExpandBUILD_VECTOR(SDNode *Node);
 133   SDValue ExpandSCALAR_TO_VECTOR(SDNode *Node);
 134   void ExpandDYNAMIC_STACKALLOC(SDNode *Node,
 135                                 SmallVectorImpl<SDValue> &Results);
 136   void getSignAsIntValue(FloatSignAsInt &State, SDLoc DL, SDValue Value) const;
 137   SDValue modifySignAsInt(const FloatSignAsInt &State, SDLoc DL,
 138                           SDValue NewIntValue) const;
 139   SDValue ExpandFCOPYSIGN(SDNode *Node) const;
 140   SDValue ExpandFABS(SDNode *Node) const;
 141   SDValue ExpandLegalINT_TO_FP(bool isSigned, SDValue LegalOp, EVT DestVT,
 142                                SDLoc dl);
 143   SDValue PromoteLegalINT_TO_FP(SDValue LegalOp, EVT DestVT, bool isSigned,
 144                                 SDLoc dl);
 145   SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT, bool isSigned,
 146                                 SDLoc dl);
 147
 148   SDValue ExpandBSWAP(SDValue Op, SDLoc dl);
 149   SDValue ExpandBitCount(unsigned Opc, SDValue Op, SDLoc dl);
 150
 151   SDValue ExpandExtractFromVectorThroughStack(SDValue Op);
 152   SDValue ExpandInsertToVectorThroughStack(SDValue Op);
 153   SDValue ExpandVectorBuildThroughStack(SDNode* Node);
 154
 155   SDValue ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP);
 156
 157   std::pair<SDValue, SDValue> ExpandAtomic(SDNode *Node);
 158
 159   void ExpandNode(SDNode *Node);
 160   void PromoteNode(SDNode *Node);
 161
 162 public:
 163   // Node replacement helpers
 164   void ReplacedNode(SDNode *N) {
 165     LegalizedNodes.erase(N);
 166     if (UpdatedNodes)
 167       UpdatedNodes->insert(N);
 168   }
 169   void ReplaceNode(SDNode *Old, SDNode *New) {
 170     DEBUG(dbgs() << " ... replacing: "; Old->dump(&DAG);
 171           dbgs() << "     with:      "; New->dump(&DAG));
 172
 173     assert(Old->getNumValues() == New->getNumValues() &&
 174            "Replacing one node with another that produces a different number "
 175            "of values!");
 176     DAG.ReplaceAllUsesWith(Old, New);
 177     for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i)
 178       DAG.TransferDbgValues(SDValue(Old, i), SDValue(New, i));
 179     if (UpdatedNodes)
 180       UpdatedNodes->insert(New);
 181     ReplacedNode(Old);
 182   }
 183   void ReplaceNode(SDValue Old, SDValue New) {
 184     DEBUG(dbgs() << " ... replacing: "; Old->dump(&DAG);
 185           dbgs() << "     with:      "; New->dump(&DAG));
 186
 187     DAG.ReplaceAllUsesWith(Old, New);
 188     DAG.TransferDbgValues(Old, New);
 189     if (UpdatedNodes)
 190       UpdatedNodes->insert(New.getNode());
 191     ReplacedNode(Old.getNode());
 192   }
 193   void ReplaceNode(SDNode *Old, const SDValue *New) {
 194     DEBUG(dbgs() << " ... replacing: "; Old->dump(&DAG));
 195
 196     DAG.ReplaceAllUsesWith(Old, New);
 197     for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i) {
 198       DEBUG(dbgs() << (i == 0 ? "     with:      "
 199                               : "      and:      ");
 200             New[i]->dump(&DAG));
 201       DAG.TransferDbgValues(SDValue(Old, i), New[i]);
 202       if (UpdatedNodes)
 203         UpdatedNodes->insert(New[i].getNode());
 204     }
 205     ReplacedNode(Old);
 206   }
 207 };
 208 }
 209
 210 /// Return a vector shuffle operation which
 211 /// performs the same shuffe in terms of order or result bytes, but on a type
 212 /// whose vector element type is narrower than the original shuffle type.
 213 /// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3>
 214 SDValue
 215 SelectionDAGLegalize::ShuffleWithNarrowerEltType(EVT NVT, EVT VT,  SDLoc dl,
 216                                                  SDValue N1, SDValue N2,
 217                                                  ArrayRef<int> Mask) const {
 218   unsigned NumMaskElts = VT.getVectorNumElements();
 219   unsigned NumDestElts = NVT.getVectorNumElements();
 220   unsigned NumEltsGrowth = NumDestElts / NumMaskElts;
 221
 222   assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!");
 223
 224   if (NumEltsGrowth == 1)
 225     return DAG.getVectorShuffle(NVT, dl, N1, N2, &Mask[0]);
 226
 227   SmallVector<int, 8> NewMask;
 228   for (unsigned i = 0; i != NumMaskElts; ++i) {
 229     int Idx = Mask[i];
 230     for (unsigned j = 0; j != NumEltsGrowth; ++j) {
 231       if (Idx < 0)
 232         NewMask.push_back(-1);
 233       else
 234         NewMask.push_back(Idx * NumEltsGrowth + j);
 235     }
 236   }
 237   assert(NewMask.size() == NumDestElts && "Non-integer NumEltsGrowth?");
 238   assert(TLI.isShuffleMaskLegal(NewMask, NVT) && "Shuffle not legal?");
 239   return DAG.getVectorShuffle(NVT, dl, N1, N2, &NewMask[0]);
 240 }
 241
 242 /// Expands the ConstantFP node to an integer constant or
 243 /// a load from the constant pool.
 244 SDValue
 245 SelectionDAGLegalize::ExpandConstantFP(ConstantFPSDNode *CFP, bool UseCP) {
 246   bool Extend = false;
 247   SDLoc dl(CFP);
 248
 249   // If a FP immediate is precise when represented as a float and if the
 250   // target can do an extending load from float to double, we put it into
 251   // the constant pool as a float, even if it's is statically typed as a
 252   // double.  This shrinks FP constants and canonicalizes them for targets where
 253   // an FP extending load is the same cost as a normal load (such as on the x87
 254   // fp stack or PPC FP unit).
 255   EVT VT = CFP->getValueType(0);
 256   ConstantFP *LLVMC = const_cast<ConstantFP*>(CFP->getConstantFPValue());
 257   if (!UseCP) {
 258     assert((VT == MVT::f64 || VT == MVT::f32) && "Invalid type expansion");
 259     return DAG.getConstant(LLVMC->getValueAPF().bitcastToAPInt(), dl,
 260                            (VT == MVT::f64) ? MVT::i64 : MVT::i32);
 261   }
 262
 263   EVT OrigVT = VT;
 264   EVT SVT = VT;
 265   while (SVT != MVT::f32 && SVT != MVT::f16) {
 266     SVT = (MVT::SimpleValueType)(SVT.getSimpleVT().SimpleTy - 1);
 267     if (ConstantFPSDNode::isValueValidForType(SVT, CFP->getValueAPF()) &&
 268         // Only do this if the target has a native EXTLOAD instruction from
 269         // smaller type.
 270         TLI.isLoadExtLegal(ISD::EXTLOAD, OrigVT, SVT) &&
 271         TLI.ShouldShrinkFPConstant(OrigVT)) {
 272       Type *SType = SVT.getTypeForEVT(*DAG.getContext());
 273       LLVMC = cast<ConstantFP>(ConstantExpr::getFPTrunc(LLVMC, SType));
 274       VT = SVT;
 275       Extend = true;
 276     }
 277   }
 278
 279   SDValue CPIdx =
 280       DAG.getConstantPool(LLVMC, TLI.getPointerTy(DAG.getDataLayout()));
 281   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
 282   if (Extend) {
 283     SDValue Result =
 284       DAG.getExtLoad(ISD::EXTLOAD, dl, OrigVT,
 285                      DAG.getEntryNode(),
 286                      CPIdx, MachinePointerInfo::getConstantPool(),
 287                      VT, false, false, false, Alignment);
 288     return Result;
 289   }
 290   SDValue Result =
 291     DAG.getLoad(OrigVT, dl, DAG.getEntryNode(), CPIdx,
 292                 MachinePointerInfo::getConstantPool(), false, false, false,
 293                 Alignment);
 294   return Result;
 295 }
 296
 297 /// Expands an unaligned store to 2 half-size stores.
 298 static void ExpandUnalignedStore(StoreSDNode *ST, SelectionDAG &DAG,
 299                                  const TargetLowering &TLI,
 300                                  SelectionDAGLegalize *DAGLegalize) {
 301   assert(ST->getAddressingMode() == ISD::UNINDEXED &&
 302          "unaligned indexed stores not implemented!");
 303   SDValue Chain = ST->getChain();
 304   SDValue Ptr = ST->getBasePtr();
 305   SDValue Val = ST->getValue();
 306   EVT VT = Val.getValueType();
 307   int Alignment = ST->getAlignment();
 308   unsigned AS = ST->getAddressSpace();
 309
 310   SDLoc dl(ST);
 311   if (ST->getMemoryVT().isFloatingPoint() ||
 312       ST->getMemoryVT().isVector()) {
 313     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits());
 314     if (TLI.isTypeLegal(intVT)) {
 315       // Expand to a bitconvert of the value to the integer type of the
 316       // same size, then a (misaligned) int store.
 317       // FIXME: Does not handle truncating floating point stores!
 318       SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
 319       Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
 320                            ST->isVolatile(), ST->isNonTemporal(), Alignment);
 321       DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 322       return;
 323     }
 324     // Do a (aligned) store to a stack slot, then copy from the stack slot
 325     // to the final destination using (unaligned) integer loads and stores.
 326     EVT StoredVT = ST->getMemoryVT();
 327     MVT RegVT =
 328       TLI.getRegisterType(*DAG.getContext(),
 329                           EVT::getIntegerVT(*DAG.getContext(),
 330                                             StoredVT.getSizeInBits()));
 331     unsigned StoredBytes = StoredVT.getSizeInBits() / 8;
 332     unsigned RegBytes = RegVT.getSizeInBits() / 8;
 333     unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes;
 334
 335     // Make sure the stack slot is also aligned for the register type.
 336     SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT);
 337
 338     // Perform the original store, only redirected to the stack slot.
 339     SDValue Store = DAG.getTruncStore(Chain, dl,
 340                                       Val, StackPtr, MachinePointerInfo(),
 341                                       StoredVT, false, false, 0);
 342     SDValue Increment = DAG.getConstant(
 343         RegBytes, dl, TLI.getPointerTy(DAG.getDataLayout(), AS));
 344     SmallVector<SDValue, 8> Stores;
 345     unsigned Offset = 0;
 346
 347     // Do all but one copies using the full register width.
 348     for (unsigned i = 1; i < NumRegs; i++) {
 349       // Load one integer register's worth from the stack slot.
 350       SDValue Load = DAG.getLoad(RegVT, dl, Store, StackPtr,
 351                                  MachinePointerInfo(),
 352                                  false, false, false, 0);
 353       // Store it to the final location.  Remember the store.
 354       Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr,
 355                                   ST->getPointerInfo().getWithOffset(Offset),
 356                                     ST->isVolatile(), ST->isNonTemporal(),
 357                                     MinAlign(ST->getAlignment(), Offset)));
 358       // Increment the pointers.
 359       Offset += RegBytes;
 360       StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 361                              Increment);
 362       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment);
 363     }
 364
 365     // The last store may be partial.  Do a truncating store.  On big-endian
 366     // machines this requires an extending load from the stack slot to ensure
 367     // that the bits are in the right place.
 368     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
 369                                   8 * (StoredBytes - Offset));
 370
 371     // Load from the stack slot.
 372     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Store, StackPtr,
 373                                   MachinePointerInfo(),
 374                                   MemVT, false, false, false, 0);
 375
 376     Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr,
 377                                        ST->getPointerInfo()
 378                                          .getWithOffset(Offset),
 379                                        MemVT, ST->isVolatile(),
 380                                        ST->isNonTemporal(),
 381                                        MinAlign(ST->getAlignment(), Offset),
 382                                        ST->getAAInfo()));
 383     // The order of the stores doesn't matter - say it with a TokenFactor.
 384     SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
 385     DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 386     return;
 387   }
 388   assert(ST->getMemoryVT().isInteger() &&
 389          !ST->getMemoryVT().isVector() &&
 390          "Unaligned store of unknown type.");
 391   // Get the half-size VT
 392   EVT NewStoredVT = ST->getMemoryVT().getHalfSizedIntegerVT(*DAG.getContext());
 393   int NumBits = NewStoredVT.getSizeInBits();
 394   int IncrementSize = NumBits / 8;
 395
 396   // Divide the stored value in two parts.
 397   SDValue ShiftAmount =
 398       DAG.getConstant(NumBits, dl, TLI.getShiftAmountTy(Val.getValueType(),
 399                                                         DAG.getDataLayout()));
 400   SDValue Lo = Val;
 401   SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount);
 402
 403   // Store the two parts
 404   SDValue Store1, Store2;
 405   Store1 = DAG.getTruncStore(Chain, dl,
 406                              DAG.getDataLayout().isLittleEndian() ? Lo : Hi,
 407                              Ptr, ST->getPointerInfo(), NewStoredVT,
 408                              ST->isVolatile(), ST->isNonTemporal(), Alignment);
 409
 410   Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 411                     DAG.getConstant(IncrementSize, dl,
 412                                     TLI.getPointerTy(DAG.getDataLayout(), AS)));
 413   Alignment = MinAlign(Alignment, IncrementSize);
 414   Store2 = DAG.getTruncStore(
 415       Chain, dl, DAG.getDataLayout().isLittleEndian() ? Hi : Lo, Ptr,
 416       ST->getPointerInfo().getWithOffset(IncrementSize), NewStoredVT,
 417       ST->isVolatile(), ST->isNonTemporal(), Alignment, ST->getAAInfo());
 418
 419   SDValue Result =
 420     DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
 421   DAGLegalize->ReplaceNode(SDValue(ST, 0), Result);
 422 }
 423
 424 /// Expands an unaligned load to 2 half-size loads.
 425 static void
 426 ExpandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG,
 427                     const TargetLowering &TLI,
 428                     SDValue &ValResult, SDValue &ChainResult) {
 429   assert(LD->getAddressingMode() == ISD::UNINDEXED &&
 430          "unaligned indexed loads not implemented!");
 431   SDValue Chain = LD->getChain();
 432   SDValue Ptr = LD->getBasePtr();
 433   EVT VT = LD->getValueType(0);
 434   EVT LoadedVT = LD->getMemoryVT();
 435   SDLoc dl(LD);
 436   if (VT.isFloatingPoint() || VT.isVector()) {
 437     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits());
 438     if (TLI.isTypeLegal(intVT) && TLI.isTypeLegal(LoadedVT)) {
 439       // Expand to a (misaligned) integer load of the same size,
 440       // then bitconvert to floating point or vector.
 441       SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr,
 442                                     LD->getMemOperand());
 443       SDValue Result = DAG.getNode(ISD::BITCAST, dl, LoadedVT, newLoad);
 444       if (LoadedVT != VT)
 445         Result = DAG.getNode(VT.isFloatingPoint() ? ISD::FP_EXTEND :
 446                              ISD::ANY_EXTEND, dl, VT, Result);
 447
 448       ValResult = Result;
 449       ChainResult = Chain;
 450       return;
 451     }
 452
 453     // Copy the value to a (aligned) stack slot using (unaligned) integer
 454     // loads and stores, then do a (aligned) load from the stack slot.
 455     MVT RegVT = TLI.getRegisterType(*DAG.getContext(), intVT);
 456     unsigned LoadedBytes = LoadedVT.getSizeInBits() / 8;
 457     unsigned RegBytes = RegVT.getSizeInBits() / 8;
 458     unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes;
 459
 460     // Make sure the stack slot is also aligned for the register type.
 461     SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT);
 462
 463     SDValue Increment =
 464         DAG.getConstant(RegBytes, dl, TLI.getPointerTy(DAG.getDataLayout()));
 465     SmallVector<SDValue, 8> Stores;
 466     SDValue StackPtr = StackBase;
 467     unsigned Offset = 0;
 468
 469     // Do all but one copies using the full register width.
 470     for (unsigned i = 1; i < NumRegs; i++) {
 471       // Load one integer register's worth from the original location.
 472       SDValue Load = DAG.getLoad(RegVT, dl, Chain, Ptr,
 473                                  LD->getPointerInfo().getWithOffset(Offset),
 474                                  LD->isVolatile(), LD->isNonTemporal(),
 475                                  LD->isInvariant(),
 476                                  MinAlign(LD->getAlignment(), Offset),
 477                                  LD->getAAInfo());
 478       // Follow the load with a store to the stack slot.  Remember the store.
 479       Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, StackPtr,
 480                                     MachinePointerInfo(), false, false, 0));
 481       // Increment the pointers.
 482       Offset += RegBytes;
 483       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr, Increment);
 484       StackPtr = DAG.getNode(ISD::ADD, dl, StackPtr.getValueType(), StackPtr,
 485                              Increment);
 486     }
 487
 488     // The last copy may be partial.  Do an extending load.
 489     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
 490                                   8 * (LoadedBytes - Offset));
 491     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr,
 492                                   LD->getPointerInfo().getWithOffset(Offset),
 493                                   MemVT, LD->isVolatile(),
 494                                   LD->isNonTemporal(),
 495                                   LD->isInvariant(),
 496                                   MinAlign(LD->getAlignment(), Offset),
 497                                   LD->getAAInfo());
 498     // Follow the load with a store to the stack slot.  Remember the store.
 499     // On big-endian machines this requires a truncating store to ensure
 500     // that the bits end up in the right place.
 501     Stores.push_back(DAG.getTruncStore(Load.getValue(1), dl, Load, StackPtr,
 502                                        MachinePointerInfo(), MemVT,
 503                                        false, false, 0));
 504
 505     // The order of the stores doesn't matter - say it with a TokenFactor.
 506     SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
 507
 508     // Finally, perform the original load only redirected to the stack slot.
 509     Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase,
 510                           MachinePointerInfo(), LoadedVT, false,false, false,
 511                           0);
 512
 513     // Callers expect a MERGE_VALUES node.
 514     ValResult = Load;
 515     ChainResult = TF;
 516     return;
 517   }
 518   assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
 519          "Unaligned load of unsupported type.");
 520
 521   // Compute the new VT that is half the size of the old one.  This is an
 522   // integer MVT.
 523   unsigned NumBits = LoadedVT.getSizeInBits();
 524   EVT NewLoadedVT;
 525   NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2);
 526   NumBits >>= 1;
 527
 528   unsigned Alignment = LD->getAlignment();
 529   unsigned IncrementSize = NumBits / 8;
 530   ISD::LoadExtType HiExtType = LD->getExtensionType();
 531
 532   // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD.
 533   if (HiExtType == ISD::NON_EXTLOAD)
 534     HiExtType = ISD::ZEXTLOAD;
 535
 536   // Load the value in two parts
 537   SDValue Lo, Hi;
 538   if (DAG.getDataLayout().isLittleEndian()) {
 539     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getPointerInfo(),
 540                         NewLoadedVT, LD->isVolatile(),
 541                         LD->isNonTemporal(), LD->isInvariant(), Alignment,
 542                         LD->getAAInfo());
 543     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 544                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
 545     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr,
 546                         LD->getPointerInfo().getWithOffset(IncrementSize),
 547                         NewLoadedVT, LD->isVolatile(),
 548                         LD->isNonTemporal(),LD->isInvariant(),
 549                         MinAlign(Alignment, IncrementSize), LD->getAAInfo());
 550   } else {
 551     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getPointerInfo(),
 552                         NewLoadedVT, LD->isVolatile(),
 553                         LD->isNonTemporal(), LD->isInvariant(), Alignment,
 554                         LD->getAAInfo());
 555     Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 556                       DAG.getConstant(IncrementSize, dl, Ptr.getValueType()));
 557     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr,
 558                         LD->getPointerInfo().getWithOffset(IncrementSize),
 559                         NewLoadedVT, LD->isVolatile(),
 560                         LD->isNonTemporal(), LD->isInvariant(),
 561                         MinAlign(Alignment, IncrementSize), LD->getAAInfo());
 562   }
 563
 564   // aggregate the two parts
 565   SDValue ShiftAmount =
 566       DAG.getConstant(NumBits, dl, TLI.getShiftAmountTy(Hi.getValueType(),
 567                                                         DAG.getDataLayout()));
 568   SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount);
 569   Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo);
 570
 571   SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
 572                              Hi.getValue(1));
 573
 574   ValResult = Result;
 575   ChainResult = TF;
 576 }
 577
 578 /// Some target cannot handle a variable insertion index for the
 579 /// INSERT_VECTOR_ELT instruction.  In this case, it
 580 /// is necessary to spill the vector being inserted into to memory, perform
 581 /// the insert there, and then read the result back.
 582 SDValue SelectionDAGLegalize::
 583 PerformInsertVectorEltInMemory(SDValue Vec, SDValue Val, SDValue Idx,
 584                                SDLoc dl) {
 585   SDValue Tmp1 = Vec;
 586   SDValue Tmp2 = Val;
 587   SDValue Tmp3 = Idx;
 588
 589   // If the target doesn't support this, we have to spill the input vector
 590   // to a temporary stack slot, update the element, then reload it.  This is
 591   // badness.  We could also load the value into a vector register (either
 592   // with a "move to register" or "extload into register" instruction, then
 593   // permute it into place, if the idx is a constant and if the idx is
 594   // supported by the target.
 595   EVT VT    = Tmp1.getValueType();
 596   EVT EltVT = VT.getVectorElementType();
 597   EVT IdxVT = Tmp3.getValueType();
 598   EVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
 599   SDValue StackPtr = DAG.CreateStackTemporary(VT);
 600
 601   int SPFI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
 602
 603   // Store the vector.
 604   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Tmp1, StackPtr,
 605                             MachinePointerInfo::getFixedStack(SPFI),
 606                             false, false, 0);
 607
 608   // Truncate or zero extend offset to target pointer type.
 609   unsigned CastOpc = IdxVT.bitsGT(PtrVT) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
 610   Tmp3 = DAG.getNode(CastOpc, dl, PtrVT, Tmp3);
 611   // Add the offset to the index.
 612   unsigned EltSize = EltVT.getSizeInBits()/8;
 613   Tmp3 = DAG.getNode(ISD::MUL, dl, IdxVT, Tmp3,
 614                      DAG.getConstant(EltSize, dl, IdxVT));
 615   SDValue StackPtr2 = DAG.getNode(ISD::ADD, dl, IdxVT, Tmp3, StackPtr);
 616   // Store the scalar value.
 617   Ch = DAG.getTruncStore(Ch, dl, Tmp2, StackPtr2, MachinePointerInfo(), EltVT,
 618                          false, false, 0);
 619   // Load the updated vector.
 620   return DAG.getLoad(VT, dl, Ch, StackPtr,
 621                      MachinePointerInfo::getFixedStack(SPFI), false, false,
 622                      false, 0);
 623 }
 624
 625
 626 SDValue SelectionDAGLegalize::
 627 ExpandINSERT_VECTOR_ELT(SDValue Vec, SDValue Val, SDValue Idx, SDLoc dl) {
 628   if (ConstantSDNode *InsertPos = dyn_cast<ConstantSDNode>(Idx)) {
 629     // SCALAR_TO_VECTOR requires that the type of the value being inserted
 630     // match the element type of the vector being created, except for
 631     // integers in which case the inserted value can be over width.
 632     EVT EltVT = Vec.getValueType().getVectorElementType();
 633     if (Val.getValueType() == EltVT ||
 634         (EltVT.isInteger() && Val.getValueType().bitsGE(EltVT))) {
 635       SDValue ScVec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl,
 636                                   Vec.getValueType(), Val);
 637
 638       unsigned NumElts = Vec.getValueType().getVectorNumElements();
 639       // We generate a shuffle of InVec and ScVec, so the shuffle mask
 640       // should be 0,1,2,3,4,5... with the appropriate element replaced with
 641       // elt 0 of the RHS.
 642       SmallVector<int, 8> ShufOps;
 643       for (unsigned i = 0; i != NumElts; ++i)
 644         ShufOps.push_back(i != InsertPos->getZExtValue() ? i : NumElts);
 645
 646       return DAG.getVectorShuffle(Vec.getValueType(), dl, Vec, ScVec,
 647                                   &ShufOps[0]);
 648     }
 649   }
 650   return PerformInsertVectorEltInMemory(Vec, Val, Idx, dl);
 651 }
 652
 653 SDValue SelectionDAGLegalize::OptimizeFloatStore(StoreSDNode* ST) {
 654   // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
 655   // FIXME: We shouldn't do this for TargetConstantFP's.
 656   // FIXME: move this to the DAG Combiner!  Note that we can't regress due
 657   // to phase ordering between legalized code and the dag combiner.  This
 658   // probably means that we need to integrate dag combiner and legalizer
 659   // together.
 660   // We generally can't do this one for long doubles.
 661   SDValue Chain = ST->getChain();
 662   SDValue Ptr = ST->getBasePtr();
 663   unsigned Alignment = ST->getAlignment();
 664   bool isVolatile = ST->isVolatile();
 665   bool isNonTemporal = ST->isNonTemporal();
 666   AAMDNodes AAInfo = ST->getAAInfo();
 667   SDLoc dl(ST);
 668   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(ST->getValue())) {
 669     if (CFP->getValueType(0) == MVT::f32 &&
 670         TLI.isTypeLegal(MVT::i32)) {
 671       SDValue Con = DAG.getConstant(CFP->getValueAPF().
 672                                       bitcastToAPInt().zextOrTrunc(32),
 673                                     SDLoc(CFP), MVT::i32);
 674       return DAG.getStore(Chain, dl, Con, Ptr, ST->getPointerInfo(),
 675                           isVolatile, isNonTemporal, Alignment, AAInfo);
 676     }
 677
 678     if (CFP->getValueType(0) == MVT::f64) {
 679       // If this target supports 64-bit registers, do a single 64-bit store.
 680       if (TLI.isTypeLegal(MVT::i64)) {
 681         SDValue Con = DAG.getConstant(CFP->getValueAPF().bitcastToAPInt().
 682                                       zextOrTrunc(64), SDLoc(CFP), MVT::i64);
 683         return DAG.getStore(Chain, dl, Con, Ptr, ST->getPointerInfo(),
 684                             isVolatile, isNonTemporal, Alignment, AAInfo);
 685       }
 686
 687       if (TLI.isTypeLegal(MVT::i32) && !ST->isVolatile()) {
 688         // Otherwise, if the target supports 32-bit registers, use 2 32-bit
 689         // stores.  If the target supports neither 32- nor 64-bits, this
 690         // xform is certainly not worth it.
 691         const APInt &IntVal = CFP->getValueAPF().bitcastToAPInt();
 692         SDValue Lo = DAG.getConstant(IntVal.trunc(32), dl, MVT::i32);
 693         SDValue Hi = DAG.getConstant(IntVal.lshr(32).trunc(32), dl, MVT::i32);
 694         if (DAG.getDataLayout().isBigEndian())
 695           std::swap(Lo, Hi);
 696
 697         Lo = DAG.getStore(Chain, dl, Lo, Ptr, ST->getPointerInfo(), isVolatile,
 698                           isNonTemporal, Alignment, AAInfo);
 699         Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 700                           DAG.getConstant(4, dl, Ptr.getValueType()));
 701         Hi = DAG.getStore(Chain, dl, Hi, Ptr,
 702                           ST->getPointerInfo().getWithOffset(4),
 703                           isVolatile, isNonTemporal, MinAlign(Alignment, 4U),
 704                           AAInfo);
 705
 706         return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
 707       }
 708     }
 709   }
 710   return SDValue(nullptr, 0);
 711 }
 712
 713 void SelectionDAGLegalize::LegalizeStoreOps(SDNode *Node) {
 714     StoreSDNode *ST = cast<StoreSDNode>(Node);
 715     SDValue Chain = ST->getChain();
 716     SDValue Ptr = ST->getBasePtr();
 717     SDLoc dl(Node);
 718
 719     unsigned Alignment = ST->getAlignment();
 720     bool isVolatile = ST->isVolatile();
 721     bool isNonTemporal = ST->isNonTemporal();
 722     AAMDNodes AAInfo = ST->getAAInfo();
 723
 724     if (!ST->isTruncatingStore()) {
 725       if (SDNode *OptStore = OptimizeFloatStore(ST).getNode()) {
 726         ReplaceNode(ST, OptStore);
 727         return;
 728       }
 729
 730       {
 731         SDValue Value = ST->getValue();
 732         MVT VT = Value.getSimpleValueType();
 733         switch (TLI.getOperationAction(ISD::STORE, VT)) {
 734         default: llvm_unreachable("This action is not supported yet!");
 735         case TargetLowering::Legal: {
 736           // If this is an unaligned store and the target doesn't support it,
 737           // expand it.
 738           unsigned AS = ST->getAddressSpace();
 739           unsigned Align = ST->getAlignment();
 740           if (!TLI.allowsMisalignedMemoryAccesses(ST->getMemoryVT(), AS, Align)) {
 741             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
 742             unsigned ABIAlignment = DAG.getDataLayout().getABITypeAlignment(Ty);
 743             if (Align < ABIAlignment)
 744               ExpandUnalignedStore(cast<StoreSDNode>(Node), DAG, TLI, this);
 745           }
 746           break;
 747         }
 748         case TargetLowering::Custom: {
 749           SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
 750           if (Res && Res != SDValue(Node, 0))
 751             ReplaceNode(SDValue(Node, 0), Res);
 752           return;
 753         }
 754         case TargetLowering::Promote: {
 755           MVT NVT = TLI.getTypeToPromoteTo(ISD::STORE, VT);
 756           assert(NVT.getSizeInBits() == VT.getSizeInBits() &&
 757                  "Can only promote stores to same size type");
 758           Value = DAG.getNode(ISD::BITCAST, dl, NVT, Value);
 759           SDValue Result =
 760             DAG.getStore(Chain, dl, Value, Ptr,
 761                          ST->getPointerInfo(), isVolatile,
 762                          isNonTemporal, Alignment, AAInfo);
 763           ReplaceNode(SDValue(Node, 0), Result);
 764           break;
 765         }
 766         }
 767         return;
 768       }
 769     } else {
 770       SDValue Value = ST->getValue();
 771
 772       EVT StVT = ST->getMemoryVT();
 773       unsigned StWidth = StVT.getSizeInBits();
 774       auto &DL = DAG.getDataLayout();
 775
 776       if (StWidth != StVT.getStoreSizeInBits()) {
 777         // Promote to a byte-sized store with upper bits zero if not
 778         // storing an integral number of bytes.  For example, promote
 779         // TRUNCSTORE:i1 X -> TRUNCSTORE:i8 (and X, 1)
 780         EVT NVT = EVT::getIntegerVT(*DAG.getContext(),
 781                                     StVT.getStoreSizeInBits());
 782         Value = DAG.getZeroExtendInReg(Value, dl, StVT);
 783         SDValue Result =
 784           DAG.getTruncStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 785                             NVT, isVolatile, isNonTemporal, Alignment, AAInfo);
 786         ReplaceNode(SDValue(Node, 0), Result);
 787       } else if (StWidth & (StWidth - 1)) {
 788         // If not storing a power-of-2 number of bits, expand as two stores.
 789         assert(!StVT.isVector() && "Unsupported truncstore!");
 790         unsigned RoundWidth = 1 << Log2_32(StWidth);
 791         assert(RoundWidth < StWidth);
 792         unsigned ExtraWidth = StWidth - RoundWidth;
 793         assert(ExtraWidth < RoundWidth);
 794         assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
 795                "Store size not an integral number of bytes!");
 796         EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth);
 797         EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth);
 798         SDValue Lo, Hi;
 799         unsigned IncrementSize;
 800
 801         if (DL.isLittleEndian()) {
 802           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 X, TRUNCSTORE@+2:i8 (srl X, 16)
 803           // Store the bottom RoundWidth bits.
 804           Lo = DAG.getTruncStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 805                                  RoundVT,
 806                                  isVolatile, isNonTemporal, Alignment,
 807                                  AAInfo);
 808
 809           // Store the remaining ExtraWidth bits.
 810           IncrementSize = RoundWidth / 8;
 811           Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 812                             DAG.getConstant(IncrementSize, dl,
 813                                             Ptr.getValueType()));
 814           Hi = DAG.getNode(
 815               ISD::SRL, dl, Value.getValueType(), Value,
 816               DAG.getConstant(RoundWidth, dl,
 817                               TLI.getShiftAmountTy(Value.getValueType(), DL)));
 818           Hi = DAG.getTruncStore(Chain, dl, Hi, Ptr,
 819                              ST->getPointerInfo().getWithOffset(IncrementSize),
 820                                  ExtraVT, isVolatile, isNonTemporal,
 821                                  MinAlign(Alignment, IncrementSize), AAInfo);
 822         } else {
 823           // Big endian - avoid unaligned stores.
 824           // TRUNCSTORE:i24 X -> TRUNCSTORE:i16 (srl X, 8), TRUNCSTORE@+2:i8 X
 825           // Store the top RoundWidth bits.
 826           Hi = DAG.getNode(
 827               ISD::SRL, dl, Value.getValueType(), Value,
 828               DAG.getConstant(ExtraWidth, dl,
 829                               TLI.getShiftAmountTy(Value.getValueType(), DL)));
 830           Hi = DAG.getTruncStore(Chain, dl, Hi, Ptr, ST->getPointerInfo(),
 831                                  RoundVT, isVolatile, isNonTemporal, Alignment,
 832                                  AAInfo);
 833
 834           // Store the remaining ExtraWidth bits.
 835           IncrementSize = RoundWidth / 8;
 836           Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
 837                             DAG.getConstant(IncrementSize, dl,
 838                                             Ptr.getValueType()));
 839           Lo = DAG.getTruncStore(Chain, dl, Value, Ptr,
 840                               ST->getPointerInfo().getWithOffset(IncrementSize),
 841                                  ExtraVT, isVolatile, isNonTemporal,
 842                                  MinAlign(Alignment, IncrementSize), AAInfo);
 843         }
 844
 845         // The order of the stores doesn't matter.
 846         SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo, Hi);
 847         ReplaceNode(SDValue(Node, 0), Result);
 848       } else {
 849         switch (TLI.getTruncStoreAction(ST->getValue().getSimpleValueType(),
 850                                         StVT.getSimpleVT())) {
 851         default: llvm_unreachable("This action is not supported yet!");
 852         case TargetLowering::Legal: {
 853           unsigned AS = ST->getAddressSpace();
 854           unsigned Align = ST->getAlignment();
 855           // If this is an unaligned store and the target doesn't support it,
 856           // expand it.
 857           if (!TLI.allowsMisalignedMemoryAccesses(ST->getMemoryVT(), AS, Align)) {
 858             Type *Ty = ST->getMemoryVT().getTypeForEVT(*DAG.getContext());
 859             unsigned ABIAlignment = DL.getABITypeAlignment(Ty);
 860             if (Align < ABIAlignment)
 861               ExpandUnalignedStore(cast<StoreSDNode>(Node), DAG, TLI, this);
 862           }
 863           break;
 864         }
 865         case TargetLowering::Custom: {
 866           SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
 867           if (Res && Res != SDValue(Node, 0))
 868             ReplaceNode(SDValue(Node, 0), Res);
 869           return;
 870         }
 871         case TargetLowering::Expand:
 872           assert(!StVT.isVector() &&
 873                  "Vector Stores are handled in LegalizeVectorOps");
 874
 875           // TRUNCSTORE:i16 i32 -> STORE i16
 876           assert(TLI.isTypeLegal(StVT) &&
 877                  "Do not know how to expand this store!");
 878           Value = DAG.getNode(ISD::TRUNCATE, dl, StVT, Value);
 879           SDValue Result =
 880             DAG.getStore(Chain, dl, Value, Ptr, ST->getPointerInfo(),
 881                          isVolatile, isNonTemporal, Alignment, AAInfo);
 882           ReplaceNode(SDValue(Node, 0), Result);
 883           break;
 884         }
 885       }
 886     }
 887 }
 888
 889 void SelectionDAGLegalize::LegalizeLoadOps(SDNode *Node) {
 890   LoadSDNode *LD = cast<LoadSDNode>(Node);
 891   SDValue Chain = LD->getChain();  // The chain.
 892   SDValue Ptr = LD->getBasePtr();  // The base pointer.
 893   SDValue Value;                   // The value returned by the load op.
 894   SDLoc dl(Node);
 895
 896   ISD::LoadExtType ExtType = LD->getExtensionType();
 897   if (ExtType == ISD::NON_EXTLOAD) {
 898     MVT VT = Node->getSimpleValueType(0);
 899     SDValue RVal = SDValue(Node, 0);
 900     SDValue RChain = SDValue(Node, 1);
 901
 902     switch (TLI.getOperationAction(Node->getOpcode(), VT)) {
 903     default: llvm_unreachable("This action is not supported yet!");
 904     case TargetLowering::Legal: {
 905       unsigned AS = LD->getAddressSpace();
 906       unsigned Align = LD->getAlignment();
 907       // If this is an unaligned load and the target doesn't support it,
 908       // expand it.
 909       if (!TLI.allowsMisalignedMemoryAccesses(LD->getMemoryVT(), AS, Align)) {
 910         Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext());
 911         unsigned ABIAlignment = DAG.getDataLayout().getABITypeAlignment(Ty);
 912         if (Align < ABIAlignment){
 913           ExpandUnalignedLoad(cast<LoadSDNode>(Node), DAG, TLI, RVal, RChain);
 914         }
 915       }
 916       break;
 917     }
 918     case TargetLowering::Custom: {
 919       SDValue Res = TLI.LowerOperation(RVal, DAG);
 920       if (Res.getNode()) {
 921         RVal = Res;
 922         RChain = Res.getValue(1);
 923       }
 924       break;
 925     }
 926     case TargetLowering::Promote: {
 927       MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), VT);
 928       assert(NVT.getSizeInBits() == VT.getSizeInBits() &&
 929              "Can only promote loads to same size type");
 930
 931       SDValue Res = DAG.getLoad(NVT, dl, Chain, Ptr, LD->getMemOperand());
 932       RVal = DAG.getNode(ISD::BITCAST, dl, VT, Res);
 933       RChain = Res.getValue(1);
 934       break;
 935     }
 936     }
 937     if (RChain.getNode() != Node) {
 938       assert(RVal.getNode() != Node && "Load must be completely replaced");
 939       DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), RVal);
 940       DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), RChain);
 941       if (UpdatedNodes) {
 942         UpdatedNodes->insert(RVal.getNode());
 943         UpdatedNodes->insert(RChain.getNode());
 944       }
 945       ReplacedNode(Node);
 946     }
 947     return;
 948   }
 949
 950   EVT SrcVT = LD->getMemoryVT();
 951   unsigned SrcWidth = SrcVT.getSizeInBits();
 952   unsigned Alignment = LD->getAlignment();
 953   bool isVolatile = LD->isVolatile();
 954   bool isNonTemporal = LD->isNonTemporal();
 955   bool isInvariant = LD->isInvariant();
 956   AAMDNodes AAInfo = LD->getAAInfo();
 957
 958   if (SrcWidth != SrcVT.getStoreSizeInBits() &&
 959       // Some targets pretend to have an i1 loading operation, and actually
 960       // load an i8.  This trick is correct for ZEXTLOAD because the top 7
 961       // bits are guaranteed to be zero; it helps the optimizers understand
 962       // that these bits are zero.  It is also useful for EXTLOAD, since it
 963       // tells the optimizers that those bits are undefined.  It would be
 964       // nice to have an effective generic way of getting these benefits...
 965       // Until such a way is found, don't insist on promoting i1 here.
 966       (SrcVT != MVT::i1 ||
 967        TLI.getLoadExtAction(ExtType, Node->getValueType(0), MVT::i1) ==
 968          TargetLowering::Promote)) {
 969     // Promote to a byte-sized load if not loading an integral number of
 970     // bytes.  For example, promote EXTLOAD:i20 -> EXTLOAD:i24.
 971     unsigned NewWidth = SrcVT.getStoreSizeInBits();
 972     EVT NVT = EVT::getIntegerVT(*DAG.getContext(), NewWidth);
 973     SDValue Ch;
 974
 975     // The extra bits are guaranteed to be zero, since we stored them that
 976     // way.  A zext load from NVT thus automatically gives zext from SrcVT.
 977
 978     ISD::LoadExtType NewExtType =
 979       ExtType == ISD::ZEXTLOAD ? ISD::ZEXTLOAD : ISD::EXTLOAD;
 980
 981     SDValue Result =
 982       DAG.getExtLoad(NewExtType, dl, Node->getValueType(0),
 983                      Chain, Ptr, LD->getPointerInfo(),
 984                      NVT, isVolatile, isNonTemporal, isInvariant, Alignment,
 985                      AAInfo);
 986
 987     Ch = Result.getValue(1); // The chain.
 988
 989     if (ExtType == ISD::SEXTLOAD)
 990       // Having the top bits zero doesn't help when sign extending.
 991       Result = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
 992                            Result.getValueType(),
 993                            Result, DAG.getValueType(SrcVT));
 994     else if (ExtType == ISD::ZEXTLOAD || NVT == Result.getValueType())
 995       // All the top bits are guaranteed to be zero - inform the optimizers.
 996       Result = DAG.getNode(ISD::AssertZext, dl,
 997                            Result.getValueType(), Result,
 998                            DAG.getValueType(SrcVT));
 999
1000     Value = Result;
1001     Chain = Ch;
1002   } else if (SrcWidth & (SrcWidth - 1)) {
1003     // If not loading a power-of-2 number of bits, expand as two loads.
1004     assert(!SrcVT.isVector() && "Unsupported extload!");
1005     unsigned RoundWidth = 1 << Log2_32(SrcWidth);
1006     assert(RoundWidth < SrcWidth);
1007     unsigned ExtraWidth = SrcWidth - RoundWidth;
1008     assert(ExtraWidth < RoundWidth);
1009     assert(!(RoundWidth % 8) && !(ExtraWidth % 8) &&
1010            "Load size not an integral number of bytes!");
1011     EVT RoundVT = EVT::getIntegerVT(*DAG.getContext(), RoundWidth);
1012     EVT ExtraVT = EVT::getIntegerVT(*DAG.getContext(), ExtraWidth);
1013     SDValue Lo, Hi, Ch;
1014     unsigned IncrementSize;
1015     auto &DL = DAG.getDataLayout();
1016
1017     if (DL.isLittleEndian()) {
1018       // EXTLOAD:i24 -> ZEXTLOAD:i16 | (shl EXTLOAD@+2:i8, 16)
1019       // Load the bottom RoundWidth bits.
1020       Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, Node->getValueType(0),
1021                           Chain, Ptr,
1022                           LD->getPointerInfo(), RoundVT, isVolatile,
1023                           isNonTemporal, isInvariant, Alignment, AAInfo);
1024
1025       // Load the remaining ExtraWidth bits.
1026       IncrementSize = RoundWidth / 8;
1027       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
1028                          DAG.getConstant(IncrementSize, dl,
1029                                          Ptr.getValueType()));
1030       Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Chain, Ptr,
1031                           LD->getPointerInfo().getWithOffset(IncrementSize),
1032                           ExtraVT, isVolatile, isNonTemporal, isInvariant,
1033                           MinAlign(Alignment, IncrementSize), AAInfo);
1034
1035       // Build a factor node to remember that this load is independent of
1036       // the other one.
1037       Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1038                        Hi.getValue(1));
1039
1040       // Move the top bits to the right place.
1041       Hi = DAG.getNode(
1042           ISD::SHL, dl, Hi.getValueType(), Hi,
1043           DAG.getConstant(RoundWidth, dl,
1044                           TLI.getShiftAmountTy(Hi.getValueType(), DL)));
1045
1046       // Join the hi and lo parts.
1047       Value = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1048     } else {
1049       // Big endian - avoid unaligned loads.
1050       // EXTLOAD:i24 -> (shl EXTLOAD:i16, 8) | ZEXTLOAD@+2:i8
1051       // Load the top RoundWidth bits.
1052       Hi = DAG.getExtLoad(ExtType, dl, Node->getValueType(0), Chain, Ptr,
1053                           LD->getPointerInfo(), RoundVT, isVolatile,
1054                           isNonTemporal, isInvariant, Alignment, AAInfo);
1055
1056       // Load the remaining ExtraWidth bits.
1057       IncrementSize = RoundWidth / 8;
1058       Ptr = DAG.getNode(ISD::ADD, dl, Ptr.getValueType(), Ptr,
1059                          DAG.getConstant(IncrementSize, dl,
1060                                          Ptr.getValueType()));
1061       Lo = DAG.getExtLoad(ISD::ZEXTLOAD,
1062                           dl, Node->getValueType(0), Chain, Ptr,
1063                           LD->getPointerInfo().getWithOffset(IncrementSize),
1064                           ExtraVT, isVolatile, isNonTemporal, isInvariant,
1065                           MinAlign(Alignment, IncrementSize), AAInfo);
1066
1067       // Build a factor node to remember that this load is independent of
1068       // the other one.
1069       Ch = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
1070                        Hi.getValue(1));
1071
1072       // Move the top bits to the right place.
1073       Hi = DAG.getNode(
1074           ISD::SHL, dl, Hi.getValueType(), Hi,
1075           DAG.getConstant(ExtraWidth, dl,
1076                           TLI.getShiftAmountTy(Hi.getValueType(), DL)));
1077
1078       // Join the hi and lo parts.
1079       Value = DAG.getNode(ISD::OR, dl, Node->getValueType(0), Lo, Hi);
1080     }
1081
1082     Chain = Ch;
1083   } else {
1084     bool isCustom = false;
1085     switch (TLI.getLoadExtAction(ExtType, Node->getValueType(0),
1086                                  SrcVT.getSimpleVT())) {
1087     default: llvm_unreachable("This action is not supported yet!");
1088     case TargetLowering::Custom:
1089       isCustom = true;
1090       // FALLTHROUGH
1091     case TargetLowering::Legal: {
1092       Value = SDValue(Node, 0);
1093       Chain = SDValue(Node, 1);
1094
1095       if (isCustom) {
1096         SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
1097         if (Res.getNode()) {
1098           Value = Res;
1099           Chain = Res.getValue(1);
1100         }
1101       } else {
1102         // If this is an unaligned load and the target doesn't support
1103         // it, expand it.
1104         EVT MemVT = LD->getMemoryVT();
1105         unsigned AS = LD->getAddressSpace();
1106         unsigned Align = LD->getAlignment();
1107         if (!TLI.allowsMisalignedMemoryAccesses(MemVT, AS, Align)) {
1108           Type *Ty = LD->getMemoryVT().getTypeForEVT(*DAG.getContext());
1109           unsigned ABIAlignment = DAG.getDataLayout().getABITypeAlignment(Ty);
1110           if (Align < ABIAlignment){
1111             ExpandUnalignedLoad(cast<LoadSDNode>(Node), DAG, TLI, Value, Chain);
1112           }
1113         }
1114       }
1115       break;
1116     }
1117     case TargetLowering::Expand:
1118       if (!TLI.isLoadExtLegal(ISD::EXTLOAD, Node->getValueType(0), SrcVT)) {
1119         // If the source type is not legal, see if there is a legal extload to
1120         // an intermediate type that we can then extend further.
1121         EVT LoadVT = TLI.getRegisterType(SrcVT.getSimpleVT());
1122         if (TLI.isTypeLegal(SrcVT) || // Same as SrcVT == LoadVT?
1123             TLI.isLoadExtLegal(ExtType, LoadVT, SrcVT)) {
1124           // If we are loading a legal type, this is a non-extload followed by a
1125           // full extend.
1126           ISD::LoadExtType MidExtType =
1127               (LoadVT == SrcVT) ? ISD::NON_EXTLOAD : ExtType;
1128
1129           SDValue Load = DAG.getExtLoad(MidExtType, dl, LoadVT, Chain, Ptr,
1130                                         SrcVT, LD->getMemOperand());
1131           unsigned ExtendOp =
1132               ISD::getExtForLoadExtType(SrcVT.isFloatingPoint(), ExtType);
1133           Value = DAG.getNode(ExtendOp, dl, Node->getValueType(0), Load);
1134           Chain = Load.getValue(1);
1135           break;
1136         }
1137       }
1138
1139       assert(!SrcVT.isVector() &&
1140              "Vector Loads are handled in LegalizeVectorOps");
1141
1142       // FIXME: This does not work for vectors on most targets.  Sign-
1143       // and zero-extend operations are currently folded into extending
1144       // loads, whether they are legal or not, and then we end up here
1145       // without any support for legalizing them.
1146       assert(ExtType != ISD::EXTLOAD &&
1147              "EXTLOAD should always be supported!");
1148       // Turn the unsupported load into an EXTLOAD followed by an
1149       // explicit zero/sign extend inreg.
1150       SDValue Result = DAG.getExtLoad(ISD::EXTLOAD, dl,
1151                                       Node->getValueType(0),
1152                                       Chain, Ptr, SrcVT,
1153                                       LD->getMemOperand());
1154       SDValue ValRes;
1155       if (ExtType == ISD::SEXTLOAD)
1156         ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, dl,
1157                              Result.getValueType(),
1158                              Result, DAG.getValueType(SrcVT));
1159       else
1160         ValRes = DAG.getZeroExtendInReg(Result, dl, SrcVT.getScalarType());
1161       Value = ValRes;
1162       Chain = Result.getValue(1);
1163       break;
1164     }
1165   }
1166
1167   // Since loads produce two values, make sure to remember that we legalized
1168   // both of them.
1169   if (Chain.getNode() != Node) {
1170     assert(Value.getNode() != Node && "Load must be completely replaced");
1171     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Value);
1172     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Chain);
1173     if (UpdatedNodes) {
1174       UpdatedNodes->insert(Value.getNode());
1175       UpdatedNodes->insert(Chain.getNode());
1176     }
1177     ReplacedNode(Node);
1178   }
1179 }
1180
1181 /// Return a legal replacement for the given operation, with all legal operands.
1182 void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
1183   DEBUG(dbgs() << "\nLegalizing: "; Node->dump(&DAG));
1184
1185   if (Node->getOpcode() == ISD::TargetConstant) // Allow illegal target nodes.
1186     return;
1187
1188 #ifndef NDEBUG
1189   for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1190     assert(TLI.getTypeAction(*DAG.getContext(), Node->getValueType(i)) ==
1191              TargetLowering::TypeLegal &&
1192            "Unexpected illegal type!");
1193
1194   for (const SDValue &Op : Node->op_values())
1195     assert((TLI.getTypeAction(*DAG.getContext(),
1196                               Op.getValueType()) == TargetLowering::TypeLegal ||
1197                               Op.getOpcode() == ISD::TargetConstant) &&
1198                               "Unexpected illegal type!");
1199 #endif
1200
1201   // Figure out the correct action; the way to query this varies by opcode
1202   TargetLowering::LegalizeAction Action = TargetLowering::Legal;
1203   bool SimpleFinishLegalizing = true;
1204   switch (Node->getOpcode()) {
1205   case ISD::INTRINSIC_W_CHAIN:
1206   case ISD::INTRINSIC_WO_CHAIN:
1207   case ISD::INTRINSIC_VOID:
1208   case ISD::STACKSAVE:
1209     Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other);
1210     break;
1211   case ISD::VAARG:
1212     Action = TLI.getOperationAction(Node->getOpcode(),
1213                                     Node->getValueType(0));
1214     if (Action != TargetLowering::Promote)
1215       Action = TLI.getOperationAction(Node->getOpcode(), MVT::Other);
1216     break;
1217   case ISD::FP_TO_FP16:
1218   case ISD::SINT_TO_FP:
1219   case ISD::UINT_TO_FP:
1220   case ISD::EXTRACT_VECTOR_ELT:
1221     Action = TLI.getOperationAction(Node->getOpcode(),
1222                                     Node->getOperand(0).getValueType());
1223     break;
1224   case ISD::FP_ROUND_INREG:
1225   case ISD::SIGN_EXTEND_INREG: {
1226     EVT InnerType = cast<VTSDNode>(Node->getOperand(1))->getVT();
1227     Action = TLI.getOperationAction(Node->getOpcode(), InnerType);
1228     break;
1229   }
1230   case ISD::ATOMIC_STORE: {
1231     Action = TLI.getOperationAction(Node->getOpcode(),
1232                                     Node->getOperand(2).getValueType());
1233     break;
1234   }
1235   case ISD::SELECT_CC:
1236   case ISD::SETCC:
1237   case ISD::BR_CC: {
1238     unsigned CCOperand = Node->getOpcode() == ISD::SELECT_CC ? 4 :
1239                          Node->getOpcode() == ISD::SETCC ? 2 : 1;
1240     unsigned CompareOperand = Node->getOpcode() == ISD::BR_CC ? 2 : 0;
1241     MVT OpVT = Node->getOperand(CompareOperand).getSimpleValueType();
1242     ISD::CondCode CCCode =
1243         cast<CondCodeSDNode>(Node->getOperand(CCOperand))->get();
1244     Action = TLI.getCondCodeAction(CCCode, OpVT);
1245     if (Action == TargetLowering::Legal) {
1246       if (Node->getOpcode() == ISD::SELECT_CC)
1247         Action = TLI.getOperationAction(Node->getOpcode(),
1248                                         Node->getValueType(0));
1249       else
1250         Action = TLI.getOperationAction(Node->getOpcode(), OpVT);
1251     }
1252     break;
1253   }
1254   case ISD::LOAD:
1255   case ISD::STORE:
1256     // FIXME: Model these properly.  LOAD and STORE are complicated, and
1257     // STORE expects the unlegalized operand in some cases.
1258     SimpleFinishLegalizing = false;
1259     break;
1260   case ISD::CALLSEQ_START:
1261   case ISD::CALLSEQ_END:
1262     // FIXME: This shouldn't be necessary.  These nodes have special properties
1263     // dealing with the recursive nature of legalization.  Removing this
1264     // special case should be done as part of making LegalizeDAG non-recursive.
1265     SimpleFinishLegalizing = false;
1266     break;
1267   case ISD::EXTRACT_ELEMENT:
1268   case ISD::FLT_ROUNDS_:
1269   case ISD::FPOWI:
1270   case ISD::MERGE_VALUES:
1271   case ISD::EH_RETURN:
1272   case ISD::FRAME_TO_ARGS_OFFSET:
1273   case ISD::EH_SJLJ_SETJMP:
1274   case ISD::EH_SJLJ_LONGJMP:
1275     // These operations lie about being legal: when they claim to be legal,
1276     // they should actually be expanded.
1277     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1278     if (Action == TargetLowering::Legal)
1279       Action = TargetLowering::Expand;
1280     break;
1281   case ISD::INIT_TRAMPOLINE:
1282   case ISD::ADJUST_TRAMPOLINE:
1283   case ISD::FRAMEADDR:
1284   case ISD::RETURNADDR:
1285     // These operations lie about being legal: when they claim to be legal,
1286     // they should actually be custom-lowered.
1287     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1288     if (Action == TargetLowering::Legal)
1289       Action = TargetLowering::Custom;
1290     break;
1291   case ISD::READ_REGISTER:
1292   case ISD::WRITE_REGISTER:
1293     // Named register is legal in the DAG, but blocked by register name
1294     // selection if not implemented by target (to chose the correct register)
1295     // They'll be converted to Copy(To/From)Reg.
1296     Action = TargetLowering::Legal;
1297     break;
1298   case ISD::DEBUGTRAP:
1299     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1300     if (Action == TargetLowering::Expand) {
1301       // replace ISD::DEBUGTRAP with ISD::TRAP
1302       SDValue NewVal;
1303       NewVal = DAG.getNode(ISD::TRAP, SDLoc(Node), Node->getVTList(),
1304                            Node->getOperand(0));
1305       ReplaceNode(Node, NewVal.getNode());
1306       LegalizeOp(NewVal.getNode());
1307       return;
1308     }
1309     break;
1310
1311   default:
1312     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
1313       Action = TargetLowering::Legal;
1314     } else {
1315       Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
1316     }
1317     break;
1318   }
1319
1320   if (SimpleFinishLegalizing) {
1321     SDNode *NewNode = Node;
1322     switch (Node->getOpcode()) {
1323     default: break;
1324     case ISD::SHL:
1325     case ISD::SRL:
1326     case ISD::SRA:
1327     case ISD::ROTL:
1328     case ISD::ROTR:
1329       // Legalizing shifts/rotates requires adjusting the shift amount
1330       // to the appropriate width.
1331       if (!Node->getOperand(1).getValueType().isVector()) {
1332         SDValue SAO =
1333           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
1334                                     Node->getOperand(1));
1335         HandleSDNode Handle(SAO);
1336         LegalizeOp(SAO.getNode());
1337         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
1338                                          Handle.getValue());
1339       }
1340       break;
1341     case ISD::SRL_PARTS:
1342     case ISD::SRA_PARTS:
1343     case ISD::SHL_PARTS:
1344       // Legalizing shifts/rotates requires adjusting the shift amount
1345       // to the appropriate width.
1346       if (!Node->getOperand(2).getValueType().isVector()) {
1347         SDValue SAO =
1348           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
1349                                     Node->getOperand(2));
1350         HandleSDNode Handle(SAO);
1351         LegalizeOp(SAO.getNode());
1352         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
1353                                          Node->getOperand(1),
1354                                          Handle.getValue());
1355       }
1356       break;
1357     }
1358
1359     if (NewNode != Node) {
1360       ReplaceNode(Node, NewNode);
1361       Node = NewNode;
1362     }
1363     switch (Action) {
1364     case TargetLowering::Legal:
1365       return;
1366     case TargetLowering::Custom: {
1367       // FIXME: The handling for custom lowering with multiple results is
1368       // a complete mess.
1369       SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG);
1370       if (Res.getNode()) {
1371         if (!(Res.getNode() != Node || Res.getResNo() != 0))
1372           return;
1373
1374         if (Node->getNumValues() == 1) {
1375           // We can just directly replace this node with the lowered value.
1376           ReplaceNode(SDValue(Node, 0), Res);
1377           return;
1378         }
1379
1380         SmallVector<SDValue, 8> ResultVals;
1381         for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i)
1382           ResultVals.push_back(Res.getValue(i));
1383         ReplaceNode(Node, ResultVals.data());
1384         return;
1385       }
1386     }
1387       // FALL THROUGH
1388     case TargetLowering::Expand:
1389       ExpandNode(Node);
1390       return;
1391     case TargetLowering::Promote:
1392       PromoteNode(Node);
1393       return;
1394     }
1395   }
1396
1397   switch (Node->getOpcode()) {
1398   default:
1399 #ifndef NDEBUG
1400     dbgs() << "NODE: ";
1401     Node->dump( &DAG);
1402     dbgs() << "\n";
1403 #endif
1404     llvm_unreachable("Do not know how to legalize this operator!");
1405
1406   case ISD::CALLSEQ_START:
1407   case ISD::CALLSEQ_END:
1408     break;
1409   case ISD::LOAD: {
1410     return LegalizeLoadOps(Node);
1411   }
1412   case ISD::STORE: {
1413     return LegalizeStoreOps(Node);
1414   }
1415   }
1416 }
1417
1418 SDValue SelectionDAGLegalize::ExpandExtractFromVectorThroughStack(SDValue Op) {
1419   SDValue Vec = Op.getOperand(0);
1420   SDValue Idx = Op.getOperand(1);
1421   SDLoc dl(Op);
1422
1423   // Before we generate a new store to a temporary stack slot, see if there is
1424   // already one that we can use. There often is because when we scalarize
1425   // vector operations (using SelectionDAG::UnrollVectorOp for example) a whole
1426   // series of EXTRACT_VECTOR_ELT nodes are generated, one for each element in
1427   // the vector. If all are expanded here, we don't want one store per vector
1428   // element.
1429   SDValue StackPtr, Ch;
1430   for (SDNode::use_iterator UI = Vec.getNode()->use_begin(),
1431        UE = Vec.getNode()->use_end(); UI != UE; ++UI) {
1432     SDNode *User = *UI;
1433     if (StoreSDNode *ST = dyn_cast<StoreSDNode>(User)) {
1434       if (ST->isIndexed() || ST->isTruncatingStore() ||
1435           ST->getValue() != Vec)
1436         continue;
1437
1438       // Make sure that nothing else could have stored into the destination of
1439       // this store.
1440       if (!ST->getChain().reachesChainWithoutSideEffects(DAG.getEntryNode()))
1441         continue;
1442
1443       StackPtr = ST->getBasePtr();
1444       Ch = SDValue(ST, 0);
1445       break;
1446     }
1447   }
1448
1449   if (!Ch.getNode()) {
1450     // Store the value to a temporary stack slot, then LOAD the returned part.
1451     StackPtr = DAG.CreateStackTemporary(Vec.getValueType());
1452     Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr,
1453                       MachinePointerInfo(), false, false, 0);
1454   }
1455
1456   // Add the offset to the index.
1457   unsigned EltSize =
1458       Vec.getValueType().getVectorElementType().getSizeInBits()/8;
1459   Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx,
1460                     DAG.getConstant(EltSize, SDLoc(Vec), Idx.getValueType()));
1461
1462   Idx = DAG.getZExtOrTrunc(Idx, dl, TLI.getPointerTy(DAG.getDataLayout()));
1463   StackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx, StackPtr);
1464
1465   SDValue NewLoad;
1466
1467   if (Op.getValueType().isVector())
1468     NewLoad = DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr,
1469                           MachinePointerInfo(), false, false, false, 0);
1470   else
1471     NewLoad = DAG.getExtLoad(
1472         ISD::EXTLOAD, dl, Op.getValueType(), Ch, StackPtr, MachinePointerInfo(),
1473         Vec.getValueType().getVectorElementType(), false, false, false, 0);
1474
1475   // Replace the chain going out of the store, by the one out of the load.
1476   DAG.ReplaceAllUsesOfValueWith(Ch, SDValue(NewLoad.getNode(), 1));
1477
1478   // We introduced a cycle though, so update the loads operands, making sure
1479   // to use the original store's chain as an incoming chain.
1480   SmallVector<SDValue, 6> NewLoadOperands(NewLoad->op_begin(),
1481                                           NewLoad->op_end());
1482   NewLoadOperands[0] = Ch;
1483   NewLoad =
1484       SDValue(DAG.UpdateNodeOperands(NewLoad.getNode(), NewLoadOperands), 0);
1485   return NewLoad;
1486 }
1487
1488 SDValue SelectionDAGLegalize::ExpandInsertToVectorThroughStack(SDValue Op) {
1489   assert(Op.getValueType().isVector() && "Non-vector insert subvector!");
1490
1491   SDValue Vec  = Op.getOperand(0);
1492   SDValue Part = Op.getOperand(1);
1493   SDValue Idx  = Op.getOperand(2);
1494   SDLoc dl(Op);
1495
1496   // Store the value to a temporary stack slot, then LOAD the returned part.
1497
1498   SDValue StackPtr = DAG.CreateStackTemporary(Vec.getValueType());
1499   int FI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
1500   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(FI);
1501
1502   // First store the whole vector.
1503   SDValue Ch = DAG.getStore(DAG.getEntryNode(), dl, Vec, StackPtr, PtrInfo,
1504                             false, false, 0);
1505
1506   // Then store the inserted part.
1507
1508   // Add the offset to the index.
1509   unsigned EltSize =
1510       Vec.getValueType().getVectorElementType().getSizeInBits()/8;
1511
1512   Idx = DAG.getNode(ISD::MUL, dl, Idx.getValueType(), Idx,
1513                     DAG.getConstant(EltSize, SDLoc(Vec), Idx.getValueType()));
1514   Idx = DAG.getZExtOrTrunc(Idx, dl, TLI.getPointerTy(DAG.getDataLayout()));
1515
1516   SDValue SubStackPtr = DAG.getNode(ISD::ADD, dl, Idx.getValueType(), Idx,
1517                                     StackPtr);
1518
1519   // Store the subvector.
1520   Ch = DAG.getStore(Ch, dl, Part, SubStackPtr,
1521                     MachinePointerInfo(), false, false, 0);
1522
1523   // Finally, load the updated vector.
1524   return DAG.getLoad(Op.getValueType(), dl, Ch, StackPtr, PtrInfo,
1525                      false, false, false, 0);
1526 }
1527
1528 SDValue SelectionDAGLegalize::ExpandVectorBuildThroughStack(SDNode* Node) {
1529   // We can't handle this case efficiently.  Allocate a sufficiently
1530   // aligned object on the stack, store each element into it, then load
1531   // the result as a vector.
1532   // Create the stack frame object.
1533   EVT VT = Node->getValueType(0);
1534   EVT EltVT = VT.getVectorElementType();
1535   SDLoc dl(Node);
1536   SDValue FIPtr = DAG.CreateStackTemporary(VT);
1537   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
1538   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(FI);
1539
1540   // Emit a store of each element to the stack slot.
1541   SmallVector<SDValue, 8> Stores;
1542   unsigned TypeByteSize = EltVT.getSizeInBits() / 8;
1543   // Store (in the right endianness) the elements to memory.
1544   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) {
1545     // Ignore undef elements.
1546     if (Node->getOperand(i).getOpcode() == ISD::UNDEF) continue;
1547
1548     unsigned Offset = TypeByteSize*i;
1549
1550     SDValue Idx = DAG.getConstant(Offset, dl, FIPtr.getValueType());
1551     Idx = DAG.getNode(ISD::ADD, dl, FIPtr.getValueType(), FIPtr, Idx);
1552
1553     // If the destination vector element type is narrower than the source
1554     // element type, only store the bits necessary.
1555     if (EltVT.bitsLT(Node->getOperand(i).getValueType().getScalarType())) {
1556       Stores.push_back(DAG.getTruncStore(DAG.getEntryNode(), dl,
1557                                          Node->getOperand(i), Idx,
1558                                          PtrInfo.getWithOffset(Offset),
1559                                          EltVT, false, false, 0));
1560     } else
1561       Stores.push_back(DAG.getStore(DAG.getEntryNode(), dl,
1562                                     Node->getOperand(i), Idx,
1563                                     PtrInfo.getWithOffset(Offset),
1564                                     false, false, 0));
1565   }
1566
1567   SDValue StoreChain;
1568   if (!Stores.empty())    // Not all undef elements?
1569     StoreChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
1570   else
1571     StoreChain = DAG.getEntryNode();
1572
1573   // Result is a load from the stack slot.
1574   return DAG.getLoad(VT, dl, StoreChain, FIPtr, PtrInfo,
1575                      false, false, false, 0);
1576 }
1577
1578 namespace {
1579 /// Keeps track of state when getting the sign of a floatingpoint value as an
1580 /// integer.
1581 struct FloatSignAsInt {
1582   EVT FloatVT;
1583   SDValue Chain;
1584   SDValue FloatPtr;
1585   SDValue IntPtr;
1586   MachinePointerInfo IntPointerInfo;
1587   MachinePointerInfo FloatPointerInfo;
1588   SDValue IntValue;
1589   APInt SignMask;
1590 };
1591 }
1592
1593 /// Bitcast a floatingpoint value to an integer value. Only bitcast the part
1594 /// containing the sign bit if the target has no integer value capable of
1595 /// holding all bits of the floatingpoint value.
1596 void SelectionDAGLegalize::getSignAsIntValue(FloatSignAsInt &State,
1597                                              SDLoc DL, SDValue Value) const {
1598   EVT FloatVT = Value.getValueType();
1599   unsigned NumBits = FloatVT.getSizeInBits();
1600   State.FloatVT = FloatVT;
1601   EVT IVT = EVT::getIntegerVT(*DAG.getContext(), NumBits);
1602   // Convert to an integer of the same size.
1603   if (TLI.isTypeLegal(IVT)) {
1604     State.IntValue = DAG.getNode(ISD::BITCAST, DL, IVT, Value);
1605     State.SignMask = APInt::getSignBit(NumBits);
1606     return;
1607   }
1608
1609   auto &DataLayout = DAG.getDataLayout();
1610   // Store the float to memory, then load the sign part out as an integer.
1611   MVT LoadTy = TLI.getPointerTy(DataLayout);
1612   // First create a temporary that is aligned for both the load and store.
1613   SDValue StackPtr = DAG.CreateStackTemporary(FloatVT, LoadTy);
1614   int FI = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
1615   // Then store the float to it.
1616   State.FloatPtr = StackPtr;
1617   State.FloatPointerInfo = MachinePointerInfo::getFixedStack(FI);
1618   State.Chain = DAG.getStore(DAG.getEntryNode(), DL, Value, State.FloatPtr,
1619                              State.FloatPointerInfo, false, false, 0);
1620
1621   if (DataLayout.isBigEndian()) {
1622     assert(FloatVT.isByteSized() && "Unsupported floating point type!");
1623     // Load out a legal integer with the same sign bit as the float.
1624     State.IntPtr = StackPtr;
1625     State.IntPointerInfo = State.FloatPointerInfo;
1626     State.IntValue = DAG.getLoad(LoadTy, DL, State.Chain, StackPtr,
1627                                  State.IntPointerInfo, false, false, false, 0);
1628     State.SignMask = APInt::getSignBit(LoadTy.getSizeInBits());
1629   } else { // Little endian
1630     // The float may be wider than the integer we are going to load.  Advance
1631     // the pointer so that the loaded integer will contain the sign bit.
1632     unsigned Strides = (FloatVT.getSizeInBits()-1)/LoadTy.getSizeInBits();
1633     unsigned ByteOffset = (Strides * LoadTy.getSizeInBits()) / 8;
1634     SDValue LoadPtr
1635       = DAG.getNode(ISD::ADD, DL, StackPtr.getValueType(), StackPtr,
1636                     DAG.getConstant(ByteOffset, DL, StackPtr.getValueType()));
1637     // Load a legal integer containing the sign bit.
1638     State.IntPtr = LoadPtr;
1639     State.IntPointerInfo = MachinePointerInfo::getFixedStack(FI, ByteOffset);
1640     State.IntValue = DAG.getLoad(LoadTy, DL, State.Chain, LoadPtr,
1641                                  State.IntPointerInfo, false, false, false, 0);
1642     unsigned NumBits = LoadTy.getSizeInBits();
1643     unsigned SignBit = (FloatVT.getSizeInBits()-1) - 8*ByteOffset;
1644     State.SignMask = APInt::getOneBitSet(NumBits, SignBit);
1645   }
1646 }
1647
1648 /// Replace the integer value produced by getSignAsIntValue() with a new value
1649 /// and cast the result back to a floatingpoint type.
1650 SDValue SelectionDAGLegalize::modifySignAsInt(const FloatSignAsInt &State,
1651                                           SDLoc DL, SDValue NewIntValue) const {
1652   if (!State.Chain) {
1653     return DAG.getNode(ISD::BITCAST, DL, State.FloatVT, NewIntValue);
1654   }
1655
1656   // Override the part containing the sign bit in the value stored on the stack.
1657   SDValue Chain = DAG.getStore(State.Chain, DL, NewIntValue, State.IntPtr,
1658                                State.IntPointerInfo, false, false, 0);
1659   return DAG.getLoad(State.FloatVT, DL, Chain, State.FloatPtr,
1660                      State.FloatPointerInfo, false, false, false, 0);
1661 }
1662
1663 SDValue SelectionDAGLegalize::ExpandFCOPYSIGN(SDNode *Node) const {
1664   SDLoc DL(Node);
1665   SDValue Mag = Node->getOperand(0);
1666   SDValue Sign = Node->getOperand(1);
1667
1668   // Get sign bit into an integer value.
1669   FloatSignAsInt SignAsInt;
1670   getSignAsIntValue(SignAsInt, DL, Sign);
1671
1672   EVT IntVT = SignAsInt.IntValue.getValueType();
1673   SDValue SignMask = DAG.getConstant(SignAsInt.SignMask, DL, IntVT);
1674   SDValue SignBit = DAG.getNode(ISD::AND, DL, IntVT, SignAsInt.IntValue,
1675                                 SignMask);
1676
1677   // Transform FCOPYSIGN(x, y) => sign(x) ? -FABS(x) : FABS(X) if FABS is legal.
1678   EVT FloatVT = Mag.getValueType();
1679   if (TLI.isOperationLegalOrCustom(ISD::FABS, FloatVT) &&
1680       TLI.isOperationLegalOrCustom(ISD::FNEG, FloatVT)) {
1681     SDValue AbsValue = DAG.getNode(ISD::FABS, DL, FloatVT, Mag);
1682     SDValue NegValue = DAG.getNode(ISD::FNEG, DL, FloatVT, AbsValue);
1683     SDValue Cond = DAG.getSetCC(DL, getSetCCResultType(IntVT), SignBit,
1684                                 DAG.getConstant(0, DL, IntVT), ISD::SETNE);
1685     return DAG.getSelect(DL, FloatVT, Cond, NegValue, AbsValue);
1686   }
1687
1688   // Transform values to integer, copy the sign bit and transform back.
1689   FloatSignAsInt MagAsInt;
1690   getSignAsIntValue(MagAsInt, DL, Mag);
1691   assert(SignAsInt.SignMask == MagAsInt.SignMask);
1692   SDValue ClearSignMask = DAG.getConstant(~SignAsInt.SignMask, DL, IntVT);
1693   SDValue ClearedSign = DAG.getNode(ISD::AND, DL, IntVT, MagAsInt.IntValue,
1694                                     ClearSignMask);
1695   SDValue CopiedSign = DAG.getNode(ISD::OR, DL, IntVT, ClearedSign, SignBit);
1696
1697   return modifySignAsInt(MagAsInt, DL, CopiedSign);
1698 }
1699
1700 SDValue SelectionDAGLegalize::ExpandFABS(SDNode *Node) const {
1701   SDLoc DL(Node);
1702   SDValue Value = Node->getOperand(0);
1703
1704   // Transform FABS(x) => FCOPYSIGN(x, 0.0) if FCOPYSIGN is legal.
1705   EVT FloatVT = Value.getValueType();
1706   if (TLI.isOperationLegalOrCustom(ISD::FCOPYSIGN, FloatVT)) {
1707     SDValue Zero = DAG.getConstantFP(0.0, DL, FloatVT);
1708     return DAG.getNode(ISD::FCOPYSIGN, DL, FloatVT, Value, Zero);
1709   }
1710
1711   // Transform value to integer, clear the sign bit and transform back.
1712   FloatSignAsInt ValueAsInt;
1713   getSignAsIntValue(ValueAsInt, DL, Value);
1714   EVT IntVT = ValueAsInt.IntValue.getValueType();
1715   SDValue ClearSignMask = DAG.getConstant(~ValueAsInt.SignMask, DL, IntVT);
1716   SDValue ClearedSign = DAG.getNode(ISD::AND, DL, IntVT, ValueAsInt.IntValue,
1717                                     ClearSignMask);
1718   return modifySignAsInt(ValueAsInt, DL, ClearedSign);
1719 }
1720
1721 void SelectionDAGLegalize::ExpandDYNAMIC_STACKALLOC(SDNode* Node,
1722                                            SmallVectorImpl<SDValue> &Results) {
1723   unsigned SPReg = TLI.getStackPointerRegisterToSaveRestore();
1724   assert(SPReg && "Target cannot require DYNAMIC_STACKALLOC expansion and"
1725           " not tell us which reg is the stack pointer!");
1726   SDLoc dl(Node);
1727   EVT VT = Node->getValueType(0);
1728   SDValue Tmp1 = SDValue(Node, 0);
1729   SDValue Tmp2 = SDValue(Node, 1);
1730   SDValue Tmp3 = Node->getOperand(2);
1731   SDValue Chain = Tmp1.getOperand(0);
1732
1733   // Chain the dynamic stack allocation so that it doesn't modify the stack
1734   // pointer when other instructions are using the stack.
1735   Chain = DAG.getCALLSEQ_START(Chain, DAG.getIntPtrConstant(0, dl, true), dl);
1736
1737   SDValue Size  = Tmp2.getOperand(1);
1738   SDValue SP = DAG.getCopyFromReg(Chain, dl, SPReg, VT);
1739   Chain = SP.getValue(1);
1740   unsigned Align = cast<ConstantSDNode>(Tmp3)->getZExtValue();
1741   unsigned StackAlign =
1742       DAG.getSubtarget().getFrameLowering()->getStackAlignment();
1743   Tmp1 = DAG.getNode(ISD::SUB, dl, VT, SP, Size);       // Value
1744   if (Align > StackAlign)
1745     Tmp1 = DAG.getNode(ISD::AND, dl, VT, Tmp1,
1746                        DAG.getConstant(-(uint64_t)Align, dl, VT));
1747   Chain = DAG.getCopyToReg(Chain, dl, SPReg, Tmp1);     // Output chain
1748
1749   Tmp2 = DAG.getCALLSEQ_END(Chain, DAG.getIntPtrConstant(0, dl, true),
1750                             DAG.getIntPtrConstant(0, dl, true), SDValue(), dl);
1751
1752   Results.push_back(Tmp1);
1753   Results.push_back(Tmp2);
1754 }
1755
1756 /// Legalize a SETCC with given LHS and RHS and condition code CC on the current
1757 /// target.
1758 ///
1759 /// If the SETCC has been legalized using AND / OR, then the legalized node
1760 /// will be stored in LHS. RHS and CC will be set to SDValue(). NeedInvert
1761 /// will be set to false.
1762 ///
1763 /// If the SETCC has been legalized by using getSetCCSwappedOperands(),
1764 /// then the values of LHS and RHS will be swapped, CC will be set to the
1765 /// new condition, and NeedInvert will be set to false.
1766 ///
1767 /// If the SETCC has been legalized using the inverse condcode, then LHS and
1768 /// RHS will be unchanged, CC will set to the inverted condcode, and NeedInvert
1769 /// will be set to true. The caller must invert the result of the SETCC with
1770 /// SelectionDAG::getLogicalNOT() or take equivalent action to swap the effect
1771 /// of a true/false result.
1772 ///
1773 /// \returns true if the SetCC has been legalized, false if it hasn't.
1774 bool SelectionDAGLegalize::LegalizeSetCCCondCode(EVT VT,
1775                                                  SDValue &LHS, SDValue &RHS,
1776                                                  SDValue &CC,
1777                                                  bool &NeedInvert,
1778                                                  SDLoc dl) {
1779   MVT OpVT = LHS.getSimpleValueType();
1780   ISD::CondCode CCCode = cast<CondCodeSDNode>(CC)->get();
1781   NeedInvert = false;
1782   switch (TLI.getCondCodeAction(CCCode, OpVT)) {
1783   default: llvm_unreachable("Unknown condition code action!");
1784   case TargetLowering::Legal:
1785     // Nothing to do.
1786     break;
1787   case TargetLowering::Expand: {
1788     ISD::CondCode InvCC = ISD::getSetCCSwappedOperands(CCCode);
1789     if (TLI.isCondCodeLegal(InvCC, OpVT)) {
1790       std::swap(LHS, RHS);
1791       CC = DAG.getCondCode(InvCC);
1792       return true;
1793     }
1794     ISD::CondCode CC1 = ISD::SETCC_INVALID, CC2 = ISD::SETCC_INVALID;
1795     unsigned Opc = 0;
1796     switch (CCCode) {
1797     default: llvm_unreachable("Don't know how to expand this condition!");
1798     case ISD::SETO:
1799         assert(TLI.getCondCodeAction(ISD::SETOEQ, OpVT)
1800             == TargetLowering::Legal
1801             && "If SETO is expanded, SETOEQ must be legal!");
1802         CC1 = ISD::SETOEQ; CC2 = ISD::SETOEQ; Opc = ISD::AND; break;
1803     case ISD::SETUO:
1804         assert(TLI.getCondCodeAction(ISD::SETUNE, OpVT)
1805             == TargetLowering::Legal
1806             && "If SETUO is expanded, SETUNE must be legal!");
1807         CC1 = ISD::SETUNE; CC2 = ISD::SETUNE; Opc = ISD::OR;  break;
1808     case ISD::SETOEQ:
1809     case ISD::SETOGT:
1810     case ISD::SETOGE:
1811     case ISD::SETOLT:
1812     case ISD::SETOLE:
1813     case ISD::SETONE:
1814     case ISD::SETUEQ:
1815     case ISD::SETUNE:
1816     case ISD::SETUGT:
1817     case ISD::SETUGE:
1818     case ISD::SETULT:
1819     case ISD::SETULE:
1820         // If we are floating point, assign and break, otherwise fall through.
1821         if (!OpVT.isInteger()) {
1822           // We can use the 4th bit to tell if we are the unordered
1823           // or ordered version of the opcode.
1824           CC2 = ((unsigned)CCCode & 0x8U) ? ISD::SETUO : ISD::SETO;
1825           Opc = ((unsigned)CCCode & 0x8U) ? ISD::OR : ISD::AND;
1826           CC1 = (ISD::CondCode)(((int)CCCode & 0x7) | 0x10);
1827           break;
1828         }
1829         // Fallthrough if we are unsigned integer.
1830     case ISD::SETLE:
1831     case ISD::SETGT:
1832     case ISD::SETGE:
1833     case ISD::SETLT:
1834       // We only support using the inverted operation, which is computed above
1835       // and not a different manner of supporting expanding these cases.
1836       llvm_unreachable("Don't know how to expand this condition!");
1837     case ISD::SETNE:
1838     case ISD::SETEQ:
1839       // Try inverting the result of the inverse condition.
1840       InvCC = CCCode == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ;
1841       if (TLI.isCondCodeLegal(InvCC, OpVT)) {
1842         CC = DAG.getCondCode(InvCC);
1843         NeedInvert = true;
1844         return true;
1845       }
1846       // If inverting the condition didn't work then we have no means to expand
1847       // the condition.
1848       llvm_unreachable("Don't know how to expand this condition!");
1849     }
1850
1851     SDValue SetCC1, SetCC2;
1852     if (CCCode != ISD::SETO && CCCode != ISD::SETUO) {
1853       // If we aren't the ordered or unorder operation,
1854       // then the pattern is (LHS CC1 RHS) Opc (LHS CC2 RHS).
1855       SetCC1 = DAG.getSetCC(dl, VT, LHS, RHS, CC1);
1856       SetCC2 = DAG.getSetCC(dl, VT, LHS, RHS, CC2);
1857     } else {
1858       // Otherwise, the pattern is (LHS CC1 LHS) Opc (RHS CC2 RHS)
1859       SetCC1 = DAG.getSetCC(dl, VT, LHS, LHS, CC1);
1860       SetCC2 = DAG.getSetCC(dl, VT, RHS, RHS, CC2);
1861     }
1862     LHS = DAG.getNode(Opc, dl, VT, SetCC1, SetCC2);
1863     RHS = SDValue();
1864     CC  = SDValue();
1865     return true;
1866   }
1867   }
1868   return false;
1869 }
1870
1871 /// Emit a store/load combination to the stack.  This stores
1872 /// SrcOp to a stack slot of type SlotVT, truncating it if needed.  It then does
1873 /// a load from the stack slot to DestVT, extending it if needed.
1874 /// The resultant code need not be legal.
1875 SDValue SelectionDAGLegalize::EmitStackConvert(SDValue SrcOp,
1876                                                EVT SlotVT,
1877                                                EVT DestVT,
1878                                                SDLoc dl) {
1879   // Create the stack frame object.
1880   unsigned SrcAlign = DAG.getDataLayout().getPrefTypeAlignment(
1881       SrcOp.getValueType().getTypeForEVT(*DAG.getContext()));
1882   SDValue FIPtr = DAG.CreateStackTemporary(SlotVT, SrcAlign);
1883
1884   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(FIPtr);
1885   int SPFI = StackPtrFI->getIndex();
1886   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(SPFI);
1887
1888   unsigned SrcSize = SrcOp.getValueType().getSizeInBits();
1889   unsigned SlotSize = SlotVT.getSizeInBits();
1890   unsigned DestSize = DestVT.getSizeInBits();
1891   Type *DestType = DestVT.getTypeForEVT(*DAG.getContext());
1892   unsigned DestAlign = DAG.getDataLayout().getPrefTypeAlignment(DestType);
1893
1894   // Emit a store to the stack slot.  Use a truncstore if the input value is
1895   // later than DestVT.
1896   SDValue Store;
1897
1898   if (SrcSize > SlotSize)
1899     Store = DAG.getTruncStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
1900                               PtrInfo, SlotVT, false, false, SrcAlign);
1901   else {
1902     assert(SrcSize == SlotSize && "Invalid store");
1903     Store = DAG.getStore(DAG.getEntryNode(), dl, SrcOp, FIPtr,
1904                          PtrInfo, false, false, SrcAlign);
1905   }
1906
1907   // Result is a load from the stack slot.
1908   if (SlotSize == DestSize)
1909     return DAG.getLoad(DestVT, dl, Store, FIPtr, PtrInfo,
1910                        false, false, false, DestAlign);
1911
1912   assert(SlotSize < DestSize && "Unknown extension!");
1913   return DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT, Store, FIPtr,
1914                         PtrInfo, SlotVT, false, false, false, DestAlign);
1915 }
1916
1917 SDValue SelectionDAGLegalize::ExpandSCALAR_TO_VECTOR(SDNode *Node) {
1918   SDLoc dl(Node);
1919   // Create a vector sized/aligned stack slot, store the value to element #0,
1920   // then load the whole vector back out.
1921   SDValue StackPtr = DAG.CreateStackTemporary(Node->getValueType(0));
1922
1923   FrameIndexSDNode *StackPtrFI = cast<FrameIndexSDNode>(StackPtr);
1924   int SPFI = StackPtrFI->getIndex();
1925
1926   SDValue Ch = DAG.getTruncStore(DAG.getEntryNode(), dl, Node->getOperand(0),
1927                                  StackPtr,
1928                                  MachinePointerInfo::getFixedStack(SPFI),
1929                                  Node->getValueType(0).getVectorElementType(),
1930                                  false, false, 0);
1931   return DAG.getLoad(Node->getValueType(0), dl, Ch, StackPtr,
1932                      MachinePointerInfo::getFixedStack(SPFI),
1933                      false, false, false, 0);
1934 }
1935
1936 static bool
1937 ExpandBVWithShuffles(SDNode *Node, SelectionDAG &DAG,
1938                      const TargetLowering &TLI, SDValue &Res) {
1939   unsigned NumElems = Node->getNumOperands();
1940   SDLoc dl(Node);
1941   EVT VT = Node->getValueType(0);
1942
1943   // Try to group the scalars into pairs, shuffle the pairs together, then
1944   // shuffle the pairs of pairs together, etc. until the vector has
1945   // been built. This will work only if all of the necessary shuffle masks
1946   // are legal.
1947
1948   // We do this in two phases; first to check the legality of the shuffles,
1949   // and next, assuming that all shuffles are legal, to create the new nodes.
1950   for (int Phase = 0; Phase < 2; ++Phase) {
1951     SmallVector<std::pair<SDValue, SmallVector<int, 16> >, 16> IntermedVals,
1952                                                                NewIntermedVals;
1953     for (unsigned i = 0; i < NumElems; ++i) {
1954       SDValue V = Node->getOperand(i);
1955       if (V.getOpcode() == ISD::UNDEF)
1956         continue;
1957
1958       SDValue Vec;
1959       if (Phase)
1960         Vec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, V);
1961       IntermedVals.push_back(std::make_pair(Vec, SmallVector<int, 16>(1, i)));
1962     }
1963
1964     while (IntermedVals.size() > 2) {
1965       NewIntermedVals.clear();
1966       for (unsigned i = 0, e = (IntermedVals.size() & ~1u); i < e; i += 2) {
1967         // This vector and the next vector are shuffled together (simply to
1968         // append the one to the other).
1969         SmallVector<int, 16> ShuffleVec(NumElems, -1);
1970
1971         SmallVector<int, 16> FinalIndices;
1972         FinalIndices.reserve(IntermedVals[i].second.size() +
1973                              IntermedVals[i+1].second.size());
1974
1975         int k = 0;
1976         for (unsigned j = 0, f = IntermedVals[i].second.size(); j != f;
1977              ++j, ++k) {
1978           ShuffleVec[k] = j;
1979           FinalIndices.push_back(IntermedVals[i].second[j]);
1980         }
1981         for (unsigned j = 0, f = IntermedVals[i+1].second.size(); j != f;
1982              ++j, ++k) {
1983           ShuffleVec[k] = NumElems + j;
1984           FinalIndices.push_back(IntermedVals[i+1].second[j]);
1985         }
1986
1987         SDValue Shuffle;
1988         if (Phase)
1989           Shuffle = DAG.getVectorShuffle(VT, dl, IntermedVals[i].first,
1990                                          IntermedVals[i+1].first,
1991                                          ShuffleVec.data());
1992         else if (!TLI.isShuffleMaskLegal(ShuffleVec, VT))
1993           return false;
1994         NewIntermedVals.push_back(
1995             std::make_pair(Shuffle, std::move(FinalIndices)));
1996       }
1997
1998       // If we had an odd number of defined values, then append the last
1999       // element to the array of new vectors.
2000       if ((IntermedVals.size() & 1) != 0)
2001         NewIntermedVals.push_back(IntermedVals.back());
2002
2003       IntermedVals.swap(NewIntermedVals);
2004     }
2005
2006     assert(IntermedVals.size() <= 2 && IntermedVals.size() > 0 &&
2007            "Invalid number of intermediate vectors");
2008     SDValue Vec1 = IntermedVals[0].first;
2009     SDValue Vec2;
2010     if (IntermedVals.size() > 1)
2011       Vec2 = IntermedVals[1].first;
2012     else if (Phase)
2013       Vec2 = DAG.getUNDEF(VT);
2014
2015     SmallVector<int, 16> ShuffleVec(NumElems, -1);
2016     for (unsigned i = 0, e = IntermedVals[0].second.size(); i != e; ++i)
2017       ShuffleVec[IntermedVals[0].second[i]] = i;
2018     for (unsigned i = 0, e = IntermedVals[1].second.size(); i != e; ++i)
2019       ShuffleVec[IntermedVals[1].second[i]] = NumElems + i;
2020
2021     if (Phase)
2022       Res = DAG.getVectorShuffle(VT, dl, Vec1, Vec2, ShuffleVec.data());
2023     else if (!TLI.isShuffleMaskLegal(ShuffleVec, VT))
2024       return false;
2025   }
2026
2027   return true;
2028 }
2029
2030 /// Expand a BUILD_VECTOR node on targets that don't
2031 /// support the operation, but do support the resultant vector type.
2032 SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
2033   unsigned NumElems = Node->getNumOperands();
2034   SDValue Value1, Value2;
2035   SDLoc dl(Node);
2036   EVT VT = Node->getValueType(0);
2037   EVT OpVT = Node->getOperand(0).getValueType();
2038   EVT EltVT = VT.getVectorElementType();
2039
2040   // If the only non-undef value is the low element, turn this into a
2041   // SCALAR_TO_VECTOR node.  If this is { X, X, X, X }, determine X.
2042   bool isOnlyLowElement = true;
2043   bool MoreThanTwoValues = false;
2044   bool isConstant = true;
2045   for (unsigned i = 0; i < NumElems; ++i) {
2046     SDValue V = Node->getOperand(i);
2047     if (V.getOpcode() == ISD::UNDEF)
2048       continue;
2049     if (i > 0)
2050       isOnlyLowElement = false;
2051     if (!isa<ConstantFPSDNode>(V) && !isa<ConstantSDNode>(V))
2052       isConstant = false;
2053
2054     if (!Value1.getNode()) {
2055       Value1 = V;
2056     } else if (!Value2.getNode()) {
2057       if (V != Value1)
2058         Value2 = V;
2059     } else if (V != Value1 && V != Value2) {
2060       MoreThanTwoValues = true;
2061     }
2062   }
2063
2064   if (!Value1.getNode())
2065     return DAG.getUNDEF(VT);
2066
2067   if (isOnlyLowElement)
2068     return DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Node->getOperand(0));
2069
2070   // If all elements are constants, create a load from the constant pool.
2071   if (isConstant) {
2072     SmallVector<Constant*, 16> CV;
2073     for (unsigned i = 0, e = NumElems; i != e; ++i) {
2074       if (ConstantFPSDNode *V =
2075           dyn_cast<ConstantFPSDNode>(Node->getOperand(i))) {
2076         CV.push_back(const_cast<ConstantFP *>(V->getConstantFPValue()));
2077       } else if (ConstantSDNode *V =
2078                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
2079         if (OpVT==EltVT)
2080           CV.push_back(const_cast<ConstantInt *>(V->getConstantIntValue()));
2081         else {
2082           // If OpVT and EltVT don't match, EltVT is not legal and the
2083           // element values have been promoted/truncated earlier.  Undo this;
2084           // we don't want a v16i8 to become a v16i32 for example.
2085           const ConstantInt *CI = V->getConstantIntValue();
2086           CV.push_back(ConstantInt::get(EltVT.getTypeForEVT(*DAG.getContext()),
2087                                         CI->getZExtValue()));
2088         }
2089       } else {
2090         assert(Node->getOperand(i).getOpcode() == ISD::UNDEF);
2091         Type *OpNTy = EltVT.getTypeForEVT(*DAG.getContext());
2092         CV.push_back(UndefValue::get(OpNTy));
2093       }
2094     }
2095     Constant *CP = ConstantVector::get(CV);
2096     SDValue CPIdx =
2097         DAG.getConstantPool(CP, TLI.getPointerTy(DAG.getDataLayout()));
2098     unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
2099     return DAG.getLoad(VT, dl, DAG.getEntryNode(), CPIdx,
2100                        MachinePointerInfo::getConstantPool(),
2101                        false, false, false, Alignment);
2102   }
2103
2104   SmallSet<SDValue, 16> DefinedValues;
2105   for (unsigned i = 0; i < NumElems; ++i) {
2106     if (Node->getOperand(i).getOpcode() == ISD::UNDEF)
2107       continue;
2108     DefinedValues.insert(Node->getOperand(i));
2109   }
2110
2111   if (TLI.shouldExpandBuildVectorWithShuffles(VT, DefinedValues.size())) {
2112     if (!MoreThanTwoValues) {
2113       SmallVector<int, 8> ShuffleVec(NumElems, -1);
2114       for (unsigned i = 0; i < NumElems; ++i) {
2115         SDValue V = Node->getOperand(i);
2116         if (V.getOpcode() == ISD::UNDEF)
2117           continue;
2118         ShuffleVec[i] = V == Value1 ? 0 : NumElems;
2119       }
2120       if (TLI.isShuffleMaskLegal(ShuffleVec, Node->getValueType(0))) {
2121         // Get the splatted value into the low element of a vector register.
2122         SDValue Vec1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value1);
2123         SDValue Vec2;
2124         if (Value2.getNode())
2125           Vec2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Value2);
2126         else
2127           Vec2 = DAG.getUNDEF(VT);
2128
2129         // Return shuffle(LowValVec, undef, <0,0,0,0>)
2130         return DAG.getVectorShuffle(VT, dl, Vec1, Vec2, ShuffleVec.data());
2131       }
2132     } else {
2133       SDValue Res;
2134       if (ExpandBVWithShuffles(Node, DAG, TLI, Res))
2135         return Res;
2136     }
2137   }
2138
2139   // Otherwise, we can't handle this case efficiently.
2140   return ExpandVectorBuildThroughStack(Node);
2141 }
2142
2143 // Expand a node into a call to a libcall.  If the result value
2144 // does not fit into a register, return the lo part and set the hi part to the
2145 // by-reg argument.  If it does fit into a single register, return the result
2146 // and leave the Hi part unset.
2147 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, SDNode *Node,
2148                                             bool isSigned) {
2149   TargetLowering::ArgListTy Args;
2150   TargetLowering::ArgListEntry Entry;
2151   for (const SDValue &Op : Node->op_values()) {
2152     EVT ArgVT = Op.getValueType();
2153     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2154     Entry.Node = Op;
2155     Entry.Ty = ArgTy;
2156     Entry.isSExt = isSigned;
2157     Entry.isZExt = !isSigned;
2158     Args.push_back(Entry);
2159   }
2160   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2161                                          TLI.getPointerTy(DAG.getDataLayout()));
2162
2163   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
2164
2165   // By default, the input chain to this libcall is the entry node of the
2166   // function. If the libcall is going to be emitted as a tail call then
2167   // TLI.isUsedByReturnOnly will change it to the right chain if the return
2168   // node which is being folded has a non-entry input chain.
2169   SDValue InChain = DAG.getEntryNode();
2170
2171   // isTailCall may be true since the callee does not reference caller stack
2172   // frame. Check if it's in the right position.
2173   SDValue TCChain = InChain;
2174   bool isTailCall = TLI.isInTailCallPosition(DAG, Node, TCChain);
2175   if (isTailCall)
2176     InChain = TCChain;
2177
2178   TargetLowering::CallLoweringInfo CLI(DAG);
2179   CLI.setDebugLoc(SDLoc(Node)).setChain(InChain)
2180     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, std::move(Args), 0)
2181     .setTailCall(isTailCall).setSExtResult(isSigned).setZExtResult(!isSigned);
2182
2183   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2184
2185   if (!CallInfo.second.getNode())
2186     // It's a tailcall, return the chain (which is the DAG root).
2187     return DAG.getRoot();
2188
2189   return CallInfo.first;
2190 }
2191
2192 /// Generate a libcall taking the given operands as arguments
2193 /// and returning a result of type RetVT.
2194 SDValue SelectionDAGLegalize::ExpandLibCall(RTLIB::Libcall LC, EVT RetVT,
2195                                             const SDValue *Ops, unsigned NumOps,
2196                                             bool isSigned, SDLoc dl) {
2197   TargetLowering::ArgListTy Args;
2198   Args.reserve(NumOps);
2199
2200   TargetLowering::ArgListEntry Entry;
2201   for (unsigned i = 0; i != NumOps; ++i) {
2202     Entry.Node = Ops[i];
2203     Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
2204     Entry.isSExt = isSigned;
2205     Entry.isZExt = !isSigned;
2206     Args.push_back(Entry);
2207   }
2208   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2209                                          TLI.getPointerTy(DAG.getDataLayout()));
2210
2211   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
2212
2213   TargetLowering::CallLoweringInfo CLI(DAG);
2214   CLI.setDebugLoc(dl).setChain(DAG.getEntryNode())
2215     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, std::move(Args), 0)
2216     .setSExtResult(isSigned).setZExtResult(!isSigned);
2217
2218   std::pair<SDValue,SDValue> CallInfo = TLI.LowerCallTo(CLI);
2219
2220   return CallInfo.first;
2221 }
2222
2223 // Expand a node into a call to a libcall. Similar to
2224 // ExpandLibCall except that the first operand is the in-chain.
2225 std::pair<SDValue, SDValue>
2226 SelectionDAGLegalize::ExpandChainLibCall(RTLIB::Libcall LC,
2227                                          SDNode *Node,
2228                                          bool isSigned) {
2229   SDValue InChain = Node->getOperand(0);
2230
2231   TargetLowering::ArgListTy Args;
2232   TargetLowering::ArgListEntry Entry;
2233   for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) {
2234     EVT ArgVT = Node->getOperand(i).getValueType();
2235     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2236     Entry.Node = Node->getOperand(i);
2237     Entry.Ty = ArgTy;
2238     Entry.isSExt = isSigned;
2239     Entry.isZExt = !isSigned;
2240     Args.push_back(Entry);
2241   }
2242   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2243                                          TLI.getPointerTy(DAG.getDataLayout()));
2244
2245   Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext());
2246
2247   TargetLowering::CallLoweringInfo CLI(DAG);
2248   CLI.setDebugLoc(SDLoc(Node)).setChain(InChain)
2249     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, std::move(Args), 0)
2250     .setSExtResult(isSigned).setZExtResult(!isSigned);
2251
2252   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2253
2254   return CallInfo;
2255 }
2256
2257 SDValue SelectionDAGLegalize::ExpandFPLibCall(SDNode* Node,
2258                                               RTLIB::Libcall Call_F32,
2259                                               RTLIB::Libcall Call_F64,
2260                                               RTLIB::Libcall Call_F80,
2261                                               RTLIB::Libcall Call_F128,
2262                                               RTLIB::Libcall Call_PPCF128) {
2263   RTLIB::Libcall LC;
2264   switch (Node->getSimpleValueType(0).SimpleTy) {
2265   default: llvm_unreachable("Unexpected request for libcall!");
2266   case MVT::f32: LC = Call_F32; break;
2267   case MVT::f64: LC = Call_F64; break;
2268   case MVT::f80: LC = Call_F80; break;
2269   case MVT::f128: LC = Call_F128; break;
2270   case MVT::ppcf128: LC = Call_PPCF128; break;
2271   }
2272   return ExpandLibCall(LC, Node, false);
2273 }
2274
2275 SDValue SelectionDAGLegalize::ExpandIntLibCall(SDNode* Node, bool isSigned,
2276                                                RTLIB::Libcall Call_I8,
2277                                                RTLIB::Libcall Call_I16,
2278                                                RTLIB::Libcall Call_I32,
2279                                                RTLIB::Libcall Call_I64,
2280                                                RTLIB::Libcall Call_I128) {
2281   RTLIB::Libcall LC;
2282   switch (Node->getSimpleValueType(0).SimpleTy) {
2283   default: llvm_unreachable("Unexpected request for libcall!");
2284   case MVT::i8:   LC = Call_I8; break;
2285   case MVT::i16:  LC = Call_I16; break;
2286   case MVT::i32:  LC = Call_I32; break;
2287   case MVT::i64:  LC = Call_I64; break;
2288   case MVT::i128: LC = Call_I128; break;
2289   }
2290   return ExpandLibCall(LC, Node, isSigned);
2291 }
2292
2293 /// Return true if divmod libcall is available.
2294 static bool isDivRemLibcallAvailable(SDNode *Node, bool isSigned,
2295                                      const TargetLowering &TLI) {
2296   RTLIB::Libcall LC;
2297   switch (Node->getSimpleValueType(0).SimpleTy) {
2298   default: llvm_unreachable("Unexpected request for libcall!");
2299   case MVT::i8:   LC= isSigned ? RTLIB::SDIVREM_I8  : RTLIB::UDIVREM_I8;  break;
2300   case MVT::i16:  LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
2301   case MVT::i32:  LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
2302   case MVT::i64:  LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
2303   case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
2304   }
2305
2306   return TLI.getLibcallName(LC) != nullptr;
2307 }
2308
2309 /// Only issue divrem libcall if both quotient and remainder are needed.
2310 static bool useDivRem(SDNode *Node, bool isSigned, bool isDIV) {
2311   // The other use might have been replaced with a divrem already.
2312   unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
2313   unsigned OtherOpcode = 0;
2314   if (isSigned)
2315     OtherOpcode = isDIV ? ISD::SREM : ISD::SDIV;
2316   else
2317     OtherOpcode = isDIV ? ISD::UREM : ISD::UDIV;
2318
2319   SDValue Op0 = Node->getOperand(0);
2320   SDValue Op1 = Node->getOperand(1);
2321   for (SDNode::use_iterator UI = Op0.getNode()->use_begin(),
2322          UE = Op0.getNode()->use_end(); UI != UE; ++UI) {
2323     SDNode *User = *UI;
2324     if (User == Node)
2325       continue;
2326     if ((User->getOpcode() == OtherOpcode || User->getOpcode() == DivRemOpc) &&
2327         User->getOperand(0) == Op0 &&
2328         User->getOperand(1) == Op1)
2329       return true;
2330   }
2331   return false;
2332 }
2333
2334 /// Issue libcalls to __{u}divmod to compute div / rem pairs.
2335 void
2336 SelectionDAGLegalize::ExpandDivRemLibCall(SDNode *Node,
2337                                           SmallVectorImpl<SDValue> &Results) {
2338   unsigned Opcode = Node->getOpcode();
2339   bool isSigned = Opcode == ISD::SDIVREM;
2340
2341   RTLIB::Libcall LC;
2342   switch (Node->getSimpleValueType(0).SimpleTy) {
2343   default: llvm_unreachable("Unexpected request for libcall!");
2344   case MVT::i8:   LC= isSigned ? RTLIB::SDIVREM_I8  : RTLIB::UDIVREM_I8;  break;
2345   case MVT::i16:  LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
2346   case MVT::i32:  LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
2347   case MVT::i64:  LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
2348   case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
2349   }
2350
2351   // The input chain to this libcall is the entry node of the function.
2352   // Legalizing the call will automatically add the previous call to the
2353   // dependence.
2354   SDValue InChain = DAG.getEntryNode();
2355
2356   EVT RetVT = Node->getValueType(0);
2357   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
2358
2359   TargetLowering::ArgListTy Args;
2360   TargetLowering::ArgListEntry Entry;
2361   for (const SDValue &Op : Node->op_values()) {
2362     EVT ArgVT = Op.getValueType();
2363     Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext());
2364     Entry.Node = Op;
2365     Entry.Ty = ArgTy;
2366     Entry.isSExt = isSigned;
2367     Entry.isZExt = !isSigned;
2368     Args.push_back(Entry);
2369   }
2370
2371   // Also pass the return address of the remainder.
2372   SDValue FIPtr = DAG.CreateStackTemporary(RetVT);
2373   Entry.Node = FIPtr;
2374   Entry.Ty = RetTy->getPointerTo();
2375   Entry.isSExt = isSigned;
2376   Entry.isZExt = !isSigned;
2377   Args.push_back(Entry);
2378
2379   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2380                                          TLI.getPointerTy(DAG.getDataLayout()));
2381
2382   SDLoc dl(Node);
2383   TargetLowering::CallLoweringInfo CLI(DAG);
2384   CLI.setDebugLoc(dl).setChain(InChain)
2385     .setCallee(TLI.getLibcallCallingConv(LC), RetTy, Callee, std::move(Args), 0)
2386     .setSExtResult(isSigned).setZExtResult(!isSigned);
2387
2388   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2389
2390   // Remainder is loaded back from the stack frame.
2391   SDValue Rem = DAG.getLoad(RetVT, dl, CallInfo.second, FIPtr,
2392                             MachinePointerInfo(), false, false, false, 0);
2393   Results.push_back(CallInfo.first);
2394   Results.push_back(Rem);
2395 }
2396
2397 /// Return true if sincos libcall is available.
2398 static bool isSinCosLibcallAvailable(SDNode *Node, const TargetLowering &TLI) {
2399   RTLIB::Libcall LC;
2400   switch (Node->getSimpleValueType(0).SimpleTy) {
2401   default: llvm_unreachable("Unexpected request for libcall!");
2402   case MVT::f32:     LC = RTLIB::SINCOS_F32; break;
2403   case MVT::f64:     LC = RTLIB::SINCOS_F64; break;
2404   case MVT::f80:     LC = RTLIB::SINCOS_F80; break;
2405   case MVT::f128:    LC = RTLIB::SINCOS_F128; break;
2406   case MVT::ppcf128: LC = RTLIB::SINCOS_PPCF128; break;
2407   }
2408   return TLI.getLibcallName(LC) != nullptr;
2409 }
2410
2411 /// Return true if sincos libcall is available and can be used to combine sin
2412 /// and cos.
2413 static bool canCombineSinCosLibcall(SDNode *Node, const TargetLowering &TLI,
2414                                     const TargetMachine &TM) {
2415   if (!isSinCosLibcallAvailable(Node, TLI))
2416     return false;
2417   // GNU sin/cos functions set errno while sincos does not. Therefore
2418   // combining sin and cos is only safe if unsafe-fpmath is enabled.
2419   bool isGNU = Triple(TM.getTargetTriple()).getEnvironment() == Triple::GNU;
2420   if (isGNU && !TM.Options.UnsafeFPMath)
2421     return false;
2422   return true;
2423 }
2424
2425 /// Only issue sincos libcall if both sin and cos are needed.
2426 static bool useSinCos(SDNode *Node) {
2427   unsigned OtherOpcode = Node->getOpcode() == ISD::FSIN
2428     ? ISD::FCOS : ISD::FSIN;
2429
2430   SDValue Op0 = Node->getOperand(0);
2431   for (SDNode::use_iterator UI = Op0.getNode()->use_begin(),
2432        UE = Op0.getNode()->use_end(); UI != UE; ++UI) {
2433     SDNode *User = *UI;
2434     if (User == Node)
2435       continue;
2436     // The other user might have been turned into sincos already.
2437     if (User->getOpcode() == OtherOpcode || User->getOpcode() == ISD::FSINCOS)
2438       return true;
2439   }
2440   return false;
2441 }
2442
2443 /// Issue libcalls to sincos to compute sin / cos pairs.
2444 void
2445 SelectionDAGLegalize::ExpandSinCosLibCall(SDNode *Node,
2446                                           SmallVectorImpl<SDValue> &Results) {
2447   RTLIB::Libcall LC;
2448   switch (Node->getSimpleValueType(0).SimpleTy) {
2449   default: llvm_unreachable("Unexpected request for libcall!");
2450   case MVT::f32:     LC = RTLIB::SINCOS_F32; break;
2451   case MVT::f64:     LC = RTLIB::SINCOS_F64; break;
2452   case MVT::f80:     LC = RTLIB::SINCOS_F80; break;
2453   case MVT::f128:    LC = RTLIB::SINCOS_F128; break;
2454   case MVT::ppcf128: LC = RTLIB::SINCOS_PPCF128; break;
2455   }
2456
2457   // The input chain to this libcall is the entry node of the function.
2458   // Legalizing the call will automatically add the previous call to the
2459   // dependence.
2460   SDValue InChain = DAG.getEntryNode();
2461
2462   EVT RetVT = Node->getValueType(0);
2463   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
2464
2465   TargetLowering::ArgListTy Args;
2466   TargetLowering::ArgListEntry Entry;
2467
2468   // Pass the argument.
2469   Entry.Node = Node->getOperand(0);
2470   Entry.Ty = RetTy;
2471   Entry.isSExt = false;
2472   Entry.isZExt = false;
2473   Args.push_back(Entry);
2474
2475   // Pass the return address of sin.
2476   SDValue SinPtr = DAG.CreateStackTemporary(RetVT);
2477   Entry.Node = SinPtr;
2478   Entry.Ty = RetTy->getPointerTo();
2479   Entry.isSExt = false;
2480   Entry.isZExt = false;
2481   Args.push_back(Entry);
2482
2483   // Also pass the return address of the cos.
2484   SDValue CosPtr = DAG.CreateStackTemporary(RetVT);
2485   Entry.Node = CosPtr;
2486   Entry.Ty = RetTy->getPointerTo();
2487   Entry.isSExt = false;
2488   Entry.isZExt = false;
2489   Args.push_back(Entry);
2490
2491   SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
2492                                          TLI.getPointerTy(DAG.getDataLayout()));
2493
2494   SDLoc dl(Node);
2495   TargetLowering::CallLoweringInfo CLI(DAG);
2496   CLI.setDebugLoc(dl).setChain(InChain)
2497     .setCallee(TLI.getLibcallCallingConv(LC),
2498                Type::getVoidTy(*DAG.getContext()), Callee, std::move(Args), 0);
2499
2500   std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI);
2501
2502   Results.push_back(DAG.getLoad(RetVT, dl, CallInfo.second, SinPtr,
2503                                 MachinePointerInfo(), false, false, false, 0));
2504   Results.push_back(DAG.getLoad(RetVT, dl, CallInfo.second, CosPtr,
2505                                 MachinePointerInfo(), false, false, false, 0));
2506 }
2507
2508 /// This function is responsible for legalizing a
2509 /// INT_TO_FP operation of the specified operand when the target requests that
2510 /// we expand it.  At this point, we know that the result and operand types are
2511 /// legal for the target.
2512 SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned,
2513                                                    SDValue Op0,
2514                                                    EVT DestVT,
2515                                                    SDLoc dl) {
2516   if (Op0.getValueType() == MVT::i32 && TLI.isTypeLegal(MVT::f64)) {
2517     // simple 32-bit [signed|unsigned] integer to float/double expansion
2518
2519     // Get the stack frame index of a 8 byte buffer.
2520     SDValue StackSlot = DAG.CreateStackTemporary(MVT::f64);
2521
2522     // word offset constant for Hi/Lo address computation
2523     SDValue WordOff = DAG.getConstant(sizeof(int), dl,
2524                                       StackSlot.getValueType());
2525     // set up Hi and Lo (into buffer) address based on endian
2526     SDValue Hi = StackSlot;
2527     SDValue Lo = DAG.getNode(ISD::ADD, dl, StackSlot.getValueType(),
2528                              StackSlot, WordOff);
2529     if (DAG.getDataLayout().isLittleEndian())
2530       std::swap(Hi, Lo);
2531
2532     // if signed map to unsigned space
2533     SDValue Op0Mapped;
2534     if (isSigned) {
2535       // constant used to invert sign bit (signed to unsigned mapping)
2536       SDValue SignBit = DAG.getConstant(0x80000000u, dl, MVT::i32);
2537       Op0Mapped = DAG.getNode(ISD::XOR, dl, MVT::i32, Op0, SignBit);
2538     } else {
2539       Op0Mapped = Op0;
2540     }
2541     // store the lo of the constructed double - based on integer input
2542     SDValue Store1 = DAG.getStore(DAG.getEntryNode(), dl,
2543                                   Op0Mapped, Lo, MachinePointerInfo(),
2544                                   false, false, 0);
2545     // initial hi portion of constructed double
2546     SDValue InitialHi = DAG.getConstant(0x43300000u, dl, MVT::i32);
2547     // store the hi of the constructed double - biased exponent
2548     SDValue Store2 = DAG.getStore(Store1, dl, InitialHi, Hi,
2549                                   MachinePointerInfo(),
2550                                   false, false, 0);
2551     // load the constructed double
2552     SDValue Load = DAG.getLoad(MVT::f64, dl, Store2, StackSlot,
2553                                MachinePointerInfo(), false, false, false, 0);
2554     // FP constant to bias correct the final result
2555     SDValue Bias = DAG.getConstantFP(isSigned ?
2556                                      BitsToDouble(0x4330000080000000ULL) :
2557                                      BitsToDouble(0x4330000000000000ULL),
2558                                      dl, MVT::f64);
2559     // subtract the bias
2560     SDValue Sub = DAG.getNode(ISD::FSUB, dl, MVT::f64, Load, Bias);
2561     // final result
2562     SDValue Result;
2563     // handle final rounding
2564     if (DestVT == MVT::f64) {
2565       // do nothing
2566       Result = Sub;
2567     } else if (DestVT.bitsLT(MVT::f64)) {
2568       Result = DAG.getNode(ISD::FP_ROUND, dl, DestVT, Sub,
2569                            DAG.getIntPtrConstant(0, dl));
2570     } else if (DestVT.bitsGT(MVT::f64)) {
2571       Result = DAG.getNode(ISD::FP_EXTEND, dl, DestVT, Sub);
2572     }
2573     return Result;
2574   }
2575   assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet");
2576   // Code below here assumes !isSigned without checking again.
2577
2578   // Implementation of unsigned i64 to f64 following the algorithm in
2579   // __floatundidf in compiler_rt. This implementation has the advantage
2580   // of performing rounding correctly, both in the default rounding mode
2581   // and in all alternate rounding modes.
2582   // TODO: Generalize this for use with other types.
2583   if (Op0.getValueType() == MVT::i64 && DestVT == MVT::f64) {
2584     SDValue TwoP52 =
2585       DAG.getConstant(UINT64_C(0x4330000000000000), dl, MVT::i64);
2586     SDValue TwoP84PlusTwoP52 =
2587       DAG.getConstantFP(BitsToDouble(UINT64_C(0x4530000000100000)), dl,
2588                         MVT::f64);
2589     SDValue TwoP84 =
2590       DAG.getConstant(UINT64_C(0x4530000000000000), dl, MVT::i64);
2591
2592     SDValue Lo = DAG.getZeroExtendInReg(Op0, dl, MVT::i32);
2593     SDValue Hi = DAG.getNode(ISD::SRL, dl, MVT::i64, Op0,
2594                              DAG.getConstant(32, dl, MVT::i64));
2595     SDValue LoOr = DAG.getNode(ISD::OR, dl, MVT::i64, Lo, TwoP52);
2596     SDValue HiOr = DAG.getNode(ISD::OR, dl, MVT::i64, Hi, TwoP84);
2597     SDValue LoFlt = DAG.getNode(ISD::BITCAST, dl, MVT::f64, LoOr);
2598     SDValue HiFlt = DAG.getNode(ISD::BITCAST, dl, MVT::f64, HiOr);
2599     SDValue HiSub = DAG.getNode(ISD::FSUB, dl, MVT::f64, HiFlt,
2600                                 TwoP84PlusTwoP52);
2601     return DAG.getNode(ISD::FADD, dl, MVT::f64, LoFlt, HiSub);
2602   }
2603
2604   // Implementation of unsigned i64 to f32.
2605   // TODO: Generalize this for use with other types.
2606   if (Op0.getValueType() == MVT::i64 && DestVT == MVT::f32) {
2607     // For unsigned conversions, convert them to signed conversions using the
2608     // algorithm from the x86_64 __floatundidf in compiler_rt.
2609     if (!isSigned) {
2610       SDValue Fast = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, Op0);
2611
2612       SDValue ShiftConst = DAG.getConstant(
2613           1, dl, TLI.getShiftAmountTy(Op0.getValueType(), DAG.getDataLayout()));
2614       SDValue Shr = DAG.getNode(ISD::SRL, dl, MVT::i64, Op0, ShiftConst);
2615       SDValue AndConst = DAG.getConstant(1, dl, MVT::i64);
2616       SDValue And = DAG.getNode(ISD::AND, dl, MVT::i64, Op0, AndConst);
2617       SDValue Or = DAG.getNode(ISD::OR, dl, MVT::i64, And, Shr);
2618
2619       SDValue SignCvt = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, Or);
2620       SDValue Slow = DAG.getNode(ISD::FADD, dl, MVT::f32, SignCvt, SignCvt);
2621
2622       // TODO: This really should be implemented using a branch rather than a
2623       // select.  We happen to get lucky and machinesink does the right
2624       // thing most of the time.  This would be a good candidate for a
2625       //pseudo-op, or, even better, for whole-function isel.
2626       SDValue SignBitTest = DAG.getSetCC(dl, getSetCCResultType(MVT::i64),
2627         Op0, DAG.getConstant(0, dl, MVT::i64), ISD::SETLT);
2628       return DAG.getSelect(dl, MVT::f32, SignBitTest, Slow, Fast);
2629     }
2630
2631     // Otherwise, implement the fully general conversion.
2632
2633     SDValue And = DAG.getNode(ISD::AND, dl, MVT::i64, Op0,
2634          DAG.getConstant(UINT64_C(0xfffffffffffff800), dl, MVT::i64));
2635     SDValue Or = DAG.getNode(ISD::OR, dl, MVT::i64, And,
2636          DAG.getConstant(UINT64_C(0x800), dl, MVT::i64));
2637     SDValue And2 = DAG.getNode(ISD::AND, dl, MVT::i64, Op0,
2638          DAG.getConstant(UINT64_C(0x7ff), dl, MVT::i64));
2639     SDValue Ne = DAG.getSetCC(dl, getSetCCResultType(MVT::i64), And2,
2640                               DAG.getConstant(UINT64_C(0), dl, MVT::i64),
2641                               ISD::SETNE);
2642     SDValue Sel = DAG.getSelect(dl, MVT::i64, Ne, Or, Op0);
2643     SDValue Ge = DAG.getSetCC(dl, getSetCCResultType(MVT::i64), Op0,
2644                               DAG.getConstant(UINT64_C(0x0020000000000000), dl,
2645                                               MVT::i64),
2646                               ISD::SETUGE);
2647     SDValue Sel2 = DAG.getSelect(dl, MVT::i64, Ge, Sel, Op0);
2648     EVT SHVT = TLI.getShiftAmountTy(Sel2.getValueType(), DAG.getDataLayout());
2649
2650     SDValue Sh = DAG.getNode(ISD::SRL, dl, MVT::i64, Sel2,
2651                              DAG.getConstant(32, dl, SHVT));
2652     SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Sh);
2653     SDValue Fcvt = DAG.getNode(ISD::UINT_TO_FP, dl, MVT::f64, Trunc);
2654     SDValue TwoP32 =
2655       DAG.getConstantFP(BitsToDouble(UINT64_C(0x41f0000000000000)), dl,
2656                         MVT::f64);
2657     SDValue Fmul = DAG.getNode(ISD::FMUL, dl, MVT::f64, TwoP32, Fcvt);
2658     SDValue Lo = DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Sel2);
2659     SDValue Fcvt2 = DAG.getNode(ISD::UINT_TO_FP, dl, MVT::f64, Lo);
2660     SDValue Fadd = DAG.getNode(ISD::FADD, dl, MVT::f64, Fmul, Fcvt2);
2661     return DAG.getNode(ISD::FP_ROUND, dl, MVT::f32, Fadd,
2662                        DAG.getIntPtrConstant(0, dl));
2663   }
2664
2665   SDValue Tmp1 = DAG.getNode(ISD::SINT_TO_FP, dl, DestVT, Op0);
2666
2667   SDValue SignSet = DAG.getSetCC(dl, getSetCCResultType(Op0.getValueType()),
2668                                  Op0,
2669                                  DAG.getConstant(0, dl, Op0.getValueType()),
2670                                  ISD::SETLT);
2671   SDValue Zero = DAG.getIntPtrConstant(0, dl),
2672           Four = DAG.getIntPtrConstant(4, dl);
2673   SDValue CstOffset = DAG.getSelect(dl, Zero.getValueType(),
2674                                     SignSet, Four, Zero);
2675
2676   // If the sign bit of the integer is set, the large number will be treated
2677   // as a negative number.  To counteract this, the dynamic code adds an
2678   // offset depending on the data type.
2679   uint64_t FF;
2680   switch (Op0.getSimpleValueType().SimpleTy) {
2681   default: llvm_unreachable("Unsupported integer type!");
2682   case MVT::i8 : FF = 0x43800000ULL; break;  // 2^8  (as a float)
2683   case MVT::i16: FF = 0x47800000ULL; break;  // 2^16 (as a float)
2684   case MVT::i32: FF = 0x4F800000ULL; break;  // 2^32 (as a float)
2685   case MVT::i64: FF = 0x5F800000ULL; break;  // 2^64 (as a float)
2686   }
2687   if (DAG.getDataLayout().isLittleEndian())
2688     FF <<= 32;
2689   Constant *FudgeFactor = ConstantInt::get(
2690                                        Type::getInt64Ty(*DAG.getContext()), FF);
2691
2692   SDValue CPIdx =
2693       DAG.getConstantPool(FudgeFactor, TLI.getPointerTy(DAG.getDataLayout()));
2694   unsigned Alignment = cast<ConstantPoolSDNode>(CPIdx)->getAlignment();
2695   CPIdx = DAG.getNode(ISD::ADD, dl, CPIdx.getValueType(), CPIdx, CstOffset);
2696   Alignment = std::min(Alignment, 4u);
2697   SDValue FudgeInReg;
2698   if (DestVT == MVT::f32)
2699     FudgeInReg = DAG.getLoad(MVT::f32, dl, DAG.getEntryNode(), CPIdx,
2700                              MachinePointerInfo::getConstantPool(),
2701                              false, false, false, Alignment);
2702   else {
2703     SDValue Load = DAG.getExtLoad(ISD::EXTLOAD, dl, DestVT,
2704                                   DAG.getEntryNode(), CPIdx,
2705                                   MachinePointerInfo::getConstantPool(),
2706                                   MVT::f32, false, false, false, Alignment);
2707     HandleSDNode Handle(Load);
2708     LegalizeOp(Load.getNode());
2709     FudgeInReg = Handle.getValue();
2710   }
2711
2712   return DAG.getNode(ISD::FADD, dl, DestVT, Tmp1, FudgeInReg);
2713 }
2714
2715 /// This function is responsible for legalizing a
2716 /// *INT_TO_FP operation of the specified operand when the target requests that
2717 /// we promote it.  At this point, we know that the result and operand types are
2718 /// legal for the target, and that there is a legal UINT_TO_FP or SINT_TO_FP
2719 /// operation that takes a larger input.
2720 SDValue SelectionDAGLegalize::PromoteLegalINT_TO_FP(SDValue LegalOp,
2721                                                     EVT DestVT,
2722                                                     bool isSigned,
2723                                                     SDLoc dl) {
2724   // First step, figure out the appropriate *INT_TO_FP operation to use.
2725   EVT NewInTy = LegalOp.getValueType();
2726
2727   unsigned OpToUse = 0;
2728
2729   // Scan for the appropriate larger type to use.
2730   while (1) {
2731     NewInTy = (MVT::SimpleValueType)(NewInTy.getSimpleVT().SimpleTy+1);
2732     assert(NewInTy.isInteger() && "Ran out of possibilities!");
2733
2734     // If the target supports SINT_TO_FP of this type, use it.
2735     if (TLI.isOperationLegalOrCustom(ISD::SINT_TO_FP, NewInTy)) {
2736       OpToUse = ISD::SINT_TO_FP;
2737       break;
2738     }
2739     if (isSigned) continue;
2740
2741     // If the target supports UINT_TO_FP of this type, use it.
2742     if (TLI.isOperationLegalOrCustom(ISD::UINT_TO_FP, NewInTy)) {
2743       OpToUse = ISD::UINT_TO_FP;
2744       break;
2745     }
2746
2747     // Otherwise, try a larger type.
2748   }
2749
2750   // Okay, we found the operation and type to use.  Zero extend our input to the
2751   // desired type then run the operation on it.
2752   return DAG.getNode(OpToUse, dl, DestVT,
2753                      DAG.getNode(isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND,
2754                                  dl, NewInTy, LegalOp));
2755 }
2756
2757 /// This function is responsible for legalizing a
2758 /// FP_TO_*INT operation of the specified operand when the target requests that
2759 /// we promote it.  At this point, we know that the result and operand types are
2760 /// legal for the target, and that there is a legal FP_TO_UINT or FP_TO_SINT
2761 /// operation that returns a larger result.
2762 SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp,
2763                                                     EVT DestVT,
2764                                                     bool isSigned,
2765                                                     SDLoc dl) {
2766   // First step, figure out the appropriate FP_TO*INT operation to use.
2767   EVT NewOutTy = DestVT;
2768
2769   unsigned OpToUse = 0;
2770
2771   // Scan for the appropriate larger type to use.
2772   while (1) {
2773     NewOutTy = (MVT::SimpleValueType)(NewOutTy.getSimpleVT().SimpleTy+1);
2774     assert(NewOutTy.isInteger() && "Ran out of possibilities!");
2775
2776     // A larger signed type can hold all unsigned values of the requested type,
2777     // so using FP_TO_SINT is valid
2778     if (TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NewOutTy)) {
2779       OpToUse = ISD::FP_TO_SINT;
2780       break;
2781     }
2782
2783     // However, if the value may be < 0.0, we *must* use some FP_TO_SINT.
2784     if (!isSigned && TLI.isOperationLegalOrCustom(ISD::FP_TO_UINT, NewOutTy)) {
2785       OpToUse = ISD::FP_TO_UINT;
2786       break;
2787     }
2788
2789     // Otherwise, try a larger type.
2790   }
2791
2792
2793   // Okay, we found the operation and type to use.
2794   SDValue Operation = DAG.getNode(OpToUse, dl, NewOutTy, LegalOp);
2795
2796   // Truncate the result of the extended FP_TO_*INT operation to the desired
2797   // size.
2798   return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation);
2799 }
2800
2801 /// Open code the operations for BSWAP of the specified operation.
2802 SDValue SelectionDAGLegalize::ExpandBSWAP(SDValue Op, SDLoc dl) {
2803   EVT VT = Op.getValueType();
2804   EVT SHVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
2805   SDValue Tmp1, Tmp2, Tmp3, Tmp4, Tmp5, Tmp6, Tmp7, Tmp8;
2806   switch (VT.getSimpleVT().SimpleTy) {
2807   default: llvm_unreachable("Unhandled Expand type in BSWAP!");
2808   case MVT::i16:
2809     Tmp2 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2810     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2811     return DAG.getNode(ISD::OR, dl, VT, Tmp1, Tmp2);
2812   case MVT::i32:
2813     Tmp4 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, dl, SHVT));
2814     Tmp3 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2815     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2816     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, dl, SHVT));
2817     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3,
2818                        DAG.getConstant(0xFF0000, dl, VT));
2819     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(0xFF00, dl, VT));
2820     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
2821     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
2822     return DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
2823   case MVT::i64:
2824     Tmp8 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(56, dl, SHVT));
2825     Tmp7 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(40, dl, SHVT));
2826     Tmp6 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(24, dl, SHVT));
2827     Tmp5 = DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2828     Tmp4 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(8, dl, SHVT));
2829     Tmp3 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(24, dl, SHVT));
2830     Tmp2 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(40, dl, SHVT));
2831     Tmp1 = DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(56, dl, SHVT));
2832     Tmp7 = DAG.getNode(ISD::AND, dl, VT, Tmp7,
2833                        DAG.getConstant(255ULL<<48, dl, VT));
2834     Tmp6 = DAG.getNode(ISD::AND, dl, VT, Tmp6,
2835                        DAG.getConstant(255ULL<<40, dl, VT));
2836     Tmp5 = DAG.getNode(ISD::AND, dl, VT, Tmp5,
2837                        DAG.getConstant(255ULL<<32, dl, VT));
2838     Tmp4 = DAG.getNode(ISD::AND, dl, VT, Tmp4,
2839                        DAG.getConstant(255ULL<<24, dl, VT));
2840     Tmp3 = DAG.getNode(ISD::AND, dl, VT, Tmp3,
2841                        DAG.getConstant(255ULL<<16, dl, VT));
2842     Tmp2 = DAG.getNode(ISD::AND, dl, VT, Tmp2,
2843                        DAG.getConstant(255ULL<<8 , dl, VT));
2844     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp7);
2845     Tmp6 = DAG.getNode(ISD::OR, dl, VT, Tmp6, Tmp5);
2846     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp3);
2847     Tmp2 = DAG.getNode(ISD::OR, dl, VT, Tmp2, Tmp1);
2848     Tmp8 = DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp6);
2849     Tmp4 = DAG.getNode(ISD::OR, dl, VT, Tmp4, Tmp2);
2850     return DAG.getNode(ISD::OR, dl, VT, Tmp8, Tmp4);
2851   }
2852 }
2853
2854 /// Expand the specified bitcount instruction into operations.
2855 SDValue SelectionDAGLegalize::ExpandBitCount(unsigned Opc, SDValue Op,
2856                                              SDLoc dl) {
2857   switch (Opc) {
2858   default: llvm_unreachable("Cannot expand this yet!");
2859   case ISD::CTPOP: {
2860     EVT VT = Op.getValueType();
2861     EVT ShVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
2862     unsigned Len = VT.getSizeInBits();
2863
2864     assert(VT.isInteger() && Len <= 128 && Len % 8 == 0 &&
2865            "CTPOP not implemented for this type.");
2866
2867     // This is the "best" algorithm from
2868     // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
2869
2870     SDValue Mask55 = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)),
2871                                      dl, VT);
2872     SDValue Mask33 = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)),
2873                                      dl, VT);
2874     SDValue Mask0F = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)),
2875                                      dl, VT);
2876     SDValue Mask01 = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x01)),
2877                                      dl, VT);
2878
2879     // v = v - ((v >> 1) & 0x55555555...)
2880     Op = DAG.getNode(ISD::SUB, dl, VT, Op,
2881                      DAG.getNode(ISD::AND, dl, VT,
2882                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2883                                              DAG.getConstant(1, dl, ShVT)),
2884                                  Mask55));
2885     // v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
2886     Op = DAG.getNode(ISD::ADD, dl, VT,
2887                      DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
2888                      DAG.getNode(ISD::AND, dl, VT,
2889                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2890                                              DAG.getConstant(2, dl, ShVT)),
2891                                  Mask33));
2892     // v = (v + (v >> 4)) & 0x0F0F0F0F...
2893     Op = DAG.getNode(ISD::AND, dl, VT,
2894                      DAG.getNode(ISD::ADD, dl, VT, Op,
2895                                  DAG.getNode(ISD::SRL, dl, VT, Op,
2896                                              DAG.getConstant(4, dl, ShVT))),
2897                      Mask0F);
2898     // v = (v * 0x01010101...) >> (Len - 8)
2899     Op = DAG.getNode(ISD::SRL, dl, VT,
2900                      DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
2901                      DAG.getConstant(Len - 8, dl, ShVT));
2902
2903     return Op;
2904   }
2905   case ISD::CTLZ_ZERO_UNDEF:
2906     // This trivially expands to CTLZ.
2907     return DAG.getNode(ISD::CTLZ, dl, Op.getValueType(), Op);
2908   case ISD::CTLZ: {
2909     // for now, we do this:
2910     // x = x | (x >> 1);
2911     // x = x | (x >> 2);
2912     // ...
2913     // x = x | (x >>16);
2914     // x = x | (x >>32); // for 64-bit input
2915     // return popcount(~x);
2916     //
2917     // Ref: "Hacker's Delight" by Henry Warren
2918     EVT VT = Op.getValueType();
2919     EVT ShVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
2920     unsigned len = VT.getSizeInBits();
2921     for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
2922       SDValue Tmp3 = DAG.getConstant(1ULL << i, dl, ShVT);
2923       Op = DAG.getNode(ISD::OR, dl, VT, Op,
2924                        DAG.getNode(ISD::SRL, dl, VT, Op, Tmp3));
2925     }
2926     Op = DAG.getNOT(dl, Op, VT);
2927     return DAG.getNode(ISD::CTPOP, dl, VT, Op);
2928   }
2929   case ISD::CTTZ_ZERO_UNDEF:
2930     // This trivially expands to CTTZ.
2931     return DAG.getNode(ISD::CTTZ, dl, Op.getValueType(), Op);
2932   case ISD::CTTZ: {
2933     // for now, we use: { return popcount(~x & (x - 1)); }
2934     // unless the target has ctlz but not ctpop, in which case we use:
2935     // { return 32 - nlz(~x & (x-1)); }
2936     // Ref: "Hacker's Delight" by Henry Warren
2937     EVT VT = Op.getValueType();
2938     SDValue Tmp3 = DAG.getNode(ISD::AND, dl, VT,
2939                                DAG.getNOT(dl, Op, VT),
2940                                DAG.getNode(ISD::SUB, dl, VT, Op,
2941                                            DAG.getConstant(1, dl, VT)));
2942     // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
2943     if (!TLI.isOperationLegalOrCustom(ISD::CTPOP, VT) &&
2944         TLI.isOperationLegalOrCustom(ISD::CTLZ, VT))
2945       return DAG.getNode(ISD::SUB, dl, VT,
2946                          DAG.getConstant(VT.getSizeInBits(), dl, VT),
2947                          DAG.getNode(ISD::CTLZ, dl, VT, Tmp3));
2948     return DAG.getNode(ISD::CTPOP, dl, VT, Tmp3);
2949   }
2950   }
2951 }
2952
2953 std::pair <SDValue, SDValue> SelectionDAGLegalize::ExpandAtomic(SDNode *Node) {
2954   unsigned Opc = Node->getOpcode();
2955   MVT VT = cast<AtomicSDNode>(Node)->getMemoryVT().getSimpleVT();
2956   RTLIB::Libcall LC = RTLIB::getATOMIC(Opc, VT);
2957   assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unexpected atomic op or value type!");
2958
2959   return ExpandChainLibCall(LC, Node, false);
2960 }
2961
2962 void SelectionDAGLegalize::ExpandNode(SDNode *Node) {
2963   SmallVector<SDValue, 8> Results;
2964   SDLoc dl(Node);
2965   SDValue Tmp1, Tmp2, Tmp3, Tmp4;
2966   bool NeedInvert;
2967   switch (Node->getOpcode()) {
2968   case ISD::CTPOP:
2969   case ISD::CTLZ:
2970   case ISD::CTLZ_ZERO_UNDEF:
2971   case ISD::CTTZ:
2972   case ISD::CTTZ_ZERO_UNDEF:
2973     Tmp1 = ExpandBitCount(Node->getOpcode(), Node->getOperand(0), dl);
2974     Results.push_back(Tmp1);
2975     break;
2976   case ISD::BSWAP:
2977     Results.push_back(ExpandBSWAP(Node->getOperand(0), dl));
2978     break;
2979   case ISD::FRAMEADDR:
2980   case ISD::RETURNADDR:
2981   case ISD::FRAME_TO_ARGS_OFFSET:
2982     Results.push_back(DAG.getConstant(0, dl, Node->getValueType(0)));
2983     break;
2984   case ISD::FLT_ROUNDS_:
2985     Results.push_back(DAG.getConstant(1, dl, Node->getValueType(0)));
2986     break;
2987   case ISD::EH_RETURN:
2988   case ISD::EH_LABEL:
2989   case ISD::PREFETCH:
2990   case ISD::VAEND:
2991   case ISD::EH_SJLJ_LONGJMP:
2992     // If the target didn't expand these, there's nothing to do, so just
2993     // preserve the chain and be done.
2994     Results.push_back(Node->getOperand(0));
2995     break;
2996   case ISD::EH_SJLJ_SETJMP:
2997     // If the target didn't expand this, just return 'zero' and preserve the
2998     // chain.
2999     Results.push_back(DAG.getConstant(0, dl, MVT::i32));
3000     Results.push_back(Node->getOperand(0));
3001     break;
3002   case ISD::ATOMIC_FENCE: {
3003     // If the target didn't lower this, lower it to '__sync_synchronize()' call
3004     // FIXME: handle "fence singlethread" more efficiently.
3005     TargetLowering::ArgListTy Args;
3006
3007     TargetLowering::CallLoweringInfo CLI(DAG);
3008     CLI.setDebugLoc(dl)
3009         .setChain(Node->getOperand(0))
3010         .setCallee(CallingConv::C, Type::getVoidTy(*DAG.getContext()),
3011                    DAG.getExternalSymbol("__sync_synchronize",
3012                                          TLI.getPointerTy(DAG.getDataLayout())),
3013                    std::move(Args), 0);
3014
3015     std::pair<SDValue, SDValue> CallResult = TLI.LowerCallTo(CLI);
3016
3017     Results.push_back(CallResult.second);
3018     break;
3019   }
3020   case ISD::ATOMIC_LOAD: {
3021     // There is no libcall for atomic load; fake it with ATOMIC_CMP_SWAP.
3022     SDValue Zero = DAG.getConstant(0, dl, Node->getValueType(0));
3023     SDVTList VTs = DAG.getVTList(Node->getValueType(0), MVT::Other);
3024     SDValue Swap = DAG.getAtomicCmpSwap(
3025         ISD::ATOMIC_CMP_SWAP, dl, cast<AtomicSDNode>(Node)->getMemoryVT(), VTs,
3026         Node->getOperand(0), Node->getOperand(1), Zero, Zero,
3027         cast<AtomicSDNode>(Node)->getMemOperand(),
3028         cast<AtomicSDNode>(Node)->getOrdering(),
3029         cast<AtomicSDNode>(Node)->getOrdering(),
3030         cast<AtomicSDNode>(Node)->getSynchScope());
3031     Results.push_back(Swap.getValue(0));
3032     Results.push_back(Swap.getValue(1));
3033     break;
3034   }
3035   case ISD::ATOMIC_STORE: {
3036     // There is no libcall for atomic store; fake it with ATOMIC_SWAP.
3037     SDValue Swap = DAG.getAtomic(ISD::ATOMIC_SWAP, dl,
3038                                  cast<AtomicSDNode>(Node)->getMemoryVT(),
3039                                  Node->getOperand(0),
3040                                  Node->getOperand(1), Node->getOperand(2),
3041                                  cast<AtomicSDNode>(Node)->getMemOperand(),
3042                                  cast<AtomicSDNode>(Node)->getOrdering(),
3043                                  cast<AtomicSDNode>(Node)->getSynchScope());
3044     Results.push_back(Swap.getValue(1));
3045     break;
3046   }
3047   // By default, atomic intrinsics are marked Legal and lowered. Targets
3048   // which don't support them directly, however, may want libcalls, in which
3049   // case they mark them Expand, and we get here.
3050   case ISD::ATOMIC_SWAP:
3051   case ISD::ATOMIC_LOAD_ADD:
3052   case ISD::ATOMIC_LOAD_SUB:
3053   case ISD::ATOMIC_LOAD_AND:
3054   case ISD::ATOMIC_LOAD_OR:
3055   case ISD::ATOMIC_LOAD_XOR:
3056   case ISD::ATOMIC_LOAD_NAND:
3057   case ISD::ATOMIC_LOAD_MIN:
3058   case ISD::ATOMIC_LOAD_MAX:
3059   case ISD::ATOMIC_LOAD_UMIN:
3060   case ISD::ATOMIC_LOAD_UMAX:
3061   case ISD::ATOMIC_CMP_SWAP: {
3062     std::pair<SDValue, SDValue> Tmp = ExpandAtomic(Node);
3063     Results.push_back(Tmp.first);
3064     Results.push_back(Tmp.second);
3065     break;
3066   }
3067   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS: {
3068     // Expanding an ATOMIC_CMP_SWAP_WITH_SUCCESS produces an ATOMIC_CMP_SWAP and
3069     // splits out the success value as a comparison. Expanding the resulting
3070     // ATOMIC_CMP_SWAP will produce a libcall.
3071     SDVTList VTs = DAG.getVTList(Node->getValueType(0), MVT::Other);
3072     SDValue Res = DAG.getAtomicCmpSwap(
3073         ISD::ATOMIC_CMP_SWAP, dl, cast<AtomicSDNode>(Node)->getMemoryVT(), VTs,
3074         Node->getOperand(0), Node->getOperand(1), Node->getOperand(2),
3075         Node->getOperand(3), cast<MemSDNode>(Node)->getMemOperand(),
3076         cast<AtomicSDNode>(Node)->getSuccessOrdering(),
3077         cast<AtomicSDNode>(Node)->getFailureOrdering(),
3078         cast<AtomicSDNode>(Node)->getSynchScope());
3079
3080     SDValue Success = DAG.getSetCC(SDLoc(Node), Node->getValueType(1),
3081                                    Res, Node->getOperand(2), ISD::SETEQ);
3082
3083     Results.push_back(Res.getValue(0));
3084     Results.push_back(Success);
3085     Results.push_back(Res.getValue(1));
3086     break;
3087   }
3088   case ISD::DYNAMIC_STACKALLOC:
3089     ExpandDYNAMIC_STACKALLOC(Node, Results);
3090     break;
3091   case ISD::MERGE_VALUES:
3092     for (unsigned i = 0; i < Node->getNumValues(); i++)
3093       Results.push_back(Node->getOperand(i));
3094     break;
3095   case ISD::UNDEF: {
3096     EVT VT = Node->getValueType(0);
3097     if (VT.isInteger())
3098       Results.push_back(DAG.getConstant(0, dl, VT));
3099     else {
3100       assert(VT.isFloatingPoint() && "Unknown value type!");
3101       Results.push_back(DAG.getConstantFP(0, dl, VT));
3102     }
3103     break;
3104   }
3105   case ISD::TRAP: {
3106     // If this operation is not supported, lower it to 'abort()' call
3107     TargetLowering::ArgListTy Args;
3108     TargetLowering::CallLoweringInfo CLI(DAG);
3109     CLI.setDebugLoc(dl)
3110         .setChain(Node->getOperand(0))
3111         .setCallee(CallingConv::C, Type::getVoidTy(*DAG.getContext()),
3112                    DAG.getExternalSymbol("abort",
3113                                          TLI.getPointerTy(DAG.getDataLayout())),
3114                    std::move(Args), 0);
3115     std::pair<SDValue, SDValue> CallResult = TLI.LowerCallTo(CLI);
3116
3117     Results.push_back(CallResult.second);
3118     break;
3119   }
3120   case ISD::FP_ROUND:
3121   case ISD::BITCAST:
3122     Tmp1 = EmitStackConvert(Node->getOperand(0), Node->getValueType(0),
3123                             Node->getValueType(0), dl);
3124     Results.push_back(Tmp1);
3125     break;
3126   case ISD::FP_EXTEND:
3127     Tmp1 = EmitStackConvert(Node->getOperand(0),
3128                             Node->getOperand(0).getValueType(),
3129                             Node->getValueType(0), dl);
3130     Results.push_back(Tmp1);
3131     break;
3132   case ISD::SIGN_EXTEND_INREG: {
3133     // NOTE: we could fall back on load/store here too for targets without
3134     // SAR.  However, it is doubtful that any exist.
3135     EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
3136     EVT VT = Node->getValueType(0);
3137     EVT ShiftAmountTy = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
3138     if (VT.isVector())
3139       ShiftAmountTy = VT;
3140     unsigned BitsDiff = VT.getScalarType().getSizeInBits() -
3141                         ExtraVT.getScalarType().getSizeInBits();
3142     SDValue ShiftCst = DAG.getConstant(BitsDiff, dl, ShiftAmountTy);
3143     Tmp1 = DAG.getNode(ISD::SHL, dl, Node->getValueType(0),
3144                        Node->getOperand(0), ShiftCst);
3145     Tmp1 = DAG.getNode(ISD::SRA, dl, Node->getValueType(0), Tmp1, ShiftCst);
3146     Results.push_back(Tmp1);
3147     break;
3148   }
3149   case ISD::FP_ROUND_INREG: {
3150     // The only way we can lower this is to turn it into a TRUNCSTORE,
3151     // EXTLOAD pair, targeting a temporary location (a stack slot).
3152
3153     // NOTE: there is a choice here between constantly creating new stack
3154     // slots and always reusing the same one.  We currently always create
3155     // new ones, as reuse may inhibit scheduling.
3156     EVT ExtraVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
3157     Tmp1 = EmitStackConvert(Node->getOperand(0), ExtraVT,
3158                             Node->getValueType(0), dl);
3159     Results.push_back(Tmp1);
3160     break;
3161   }
3162   case ISD::SINT_TO_FP:
3163   case ISD::UINT_TO_FP:
3164     Tmp1 = ExpandLegalINT_TO_FP(Node->getOpcode() == ISD::SINT_TO_FP,
3165                                 Node->getOperand(0), Node->getValueType(0), dl);
3166     Results.push_back(Tmp1);
3167     break;
3168   case ISD::FP_TO_SINT:
3169     if (TLI.expandFP_TO_SINT(Node, Tmp1, DAG))
3170       Results.push_back(Tmp1);
3171     break;
3172   case ISD::FP_TO_UINT: {
3173     SDValue True, False;
3174     EVT VT =  Node->getOperand(0).getValueType();
3175     EVT NVT = Node->getValueType(0);
3176     APFloat apf(DAG.EVTToAPFloatSemantics(VT),
3177                 APInt::getNullValue(VT.getSizeInBits()));
3178     APInt x = APInt::getSignBit(NVT.getSizeInBits());
3179     (void)apf.convertFromAPInt(x, false, APFloat::rmNearestTiesToEven);
3180     Tmp1 = DAG.getConstantFP(apf, dl, VT);
3181     Tmp2 = DAG.getSetCC(dl, getSetCCResultType(VT),
3182                         Node->getOperand(0),
3183                         Tmp1, ISD::SETLT);
3184     True = DAG.getNode(ISD::FP_TO_SINT, dl, NVT, Node->getOperand(0));
3185     False = DAG.getNode(ISD::FP_TO_SINT, dl, NVT,
3186                         DAG.getNode(ISD::FSUB, dl, VT,
3187                                     Node->getOperand(0), Tmp1));
3188     False = DAG.getNode(ISD::XOR, dl, NVT, False,
3189                         DAG.getConstant(x, dl, NVT));
3190     Tmp1 = DAG.getSelect(dl, NVT, Tmp2, True, False);
3191     Results.push_back(Tmp1);
3192     break;
3193   }
3194   case ISD::VAARG: {
3195     const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
3196     EVT VT = Node->getValueType(0);
3197     Tmp1 = Node->getOperand(0);
3198     Tmp2 = Node->getOperand(1);
3199     unsigned Align = Node->getConstantOperandVal(3);
3200
3201     SDValue VAListLoad =
3202         DAG.getLoad(TLI.getPointerTy(DAG.getDataLayout()), dl, Tmp1, Tmp2,
3203                     MachinePointerInfo(V), false, false, false, 0);
3204     SDValue VAList = VAListLoad;
3205
3206     if (Align > TLI.getMinStackArgumentAlignment()) {
3207       assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
3208
3209       VAList = DAG.getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
3210                            DAG.getConstant(Align - 1, dl,
3211                                            VAList.getValueType()));
3212
3213       VAList = DAG.getNode(ISD::AND, dl, VAList.getValueType(), VAList,
3214                            DAG.getConstant(-(int64_t)Align, dl,
3215                                            VAList.getValueType()));
3216     }
3217
3218     // Increment the pointer, VAList, to the next vaarg
3219     Tmp3 = DAG.getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
3220                        DAG.getConstant(DAG.getDataLayout().getTypeAllocSize(
3221                                            VT.getTypeForEVT(*DAG.getContext())),
3222                                        dl, VAList.getValueType()));
3223     // Store the incremented VAList to the legalized pointer
3224     Tmp3 = DAG.getStore(VAListLoad.getValue(1), dl, Tmp3, Tmp2,
3225                         MachinePointerInfo(V), false, false, 0);
3226     // Load the actual argument out of the pointer VAList
3227     Results.push_back(DAG.getLoad(VT, dl, Tmp3, VAList, MachinePointerInfo(),
3228                                   false, false, false, 0));
3229     Results.push_back(Results[0].getValue(1));
3230     break;
3231   }
3232   case ISD::VACOPY: {
3233     // This defaults to loading a pointer from the input and storing it to the
3234     // output, returning the chain.
3235     const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
3236     const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
3237     Tmp1 = DAG.getLoad(TLI.getPointerTy(DAG.getDataLayout()), dl,
3238                        Node->getOperand(0), Node->getOperand(2),
3239                        MachinePointerInfo(VS), false, false, false, 0);
3240     Tmp1 = DAG.getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
3241                         MachinePointerInfo(VD), false, false, 0);
3242     Results.push_back(Tmp1);
3243     break;
3244   }
3245   case ISD::EXTRACT_VECTOR_ELT:
3246     if (Node->getOperand(0).getValueType().getVectorNumElements() == 1)
3247       // This must be an access of the only element.  Return it.
3248       Tmp1 = DAG.getNode(ISD::BITCAST, dl, Node->getValueType(0),
3249                          Node->getOperand(0));
3250     else
3251       Tmp1 = ExpandExtractFromVectorThroughStack(SDValue(Node, 0));
3252     Results.push_back(Tmp1);
3253     break;
3254   case ISD::EXTRACT_SUBVECTOR:
3255     Results.push_back(ExpandExtractFromVectorThroughStack(SDValue(Node, 0)));
3256     break;
3257   case ISD::INSERT_SUBVECTOR:
3258     Results.push_back(ExpandInsertToVectorThroughStack(SDValue(Node, 0)));
3259     break;
3260   case ISD::CONCAT_VECTORS: {
3261     Results.push_back(ExpandVectorBuildThroughStack(Node));
3262     break;
3263   }
3264   case ISD::SCALAR_TO_VECTOR:
3265     Results.push_back(ExpandSCALAR_TO_VECTOR(Node));
3266     break;
3267   case ISD::INSERT_VECTOR_ELT:
3268     Results.push_back(ExpandINSERT_VECTOR_ELT(Node->getOperand(0),
3269                                               Node->getOperand(1),
3270                                               Node->getOperand(2), dl));
3271     break;
3272   case ISD::VECTOR_SHUFFLE: {
3273     SmallVector<int, 32> NewMask;
3274     ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
3275
3276     EVT VT = Node->getValueType(0);
3277     EVT EltVT = VT.getVectorElementType();
3278     SDValue Op0 = Node->getOperand(0);
3279     SDValue Op1 = Node->getOperand(1);
3280     if (!TLI.isTypeLegal(EltVT)) {
3281
3282       EVT NewEltVT = TLI.getTypeToTransformTo(*DAG.getContext(), EltVT);
3283
3284       // BUILD_VECTOR operands are allowed to be wider than the element type.
3285       // But if NewEltVT is smaller that EltVT the BUILD_VECTOR does not accept
3286       // it.
3287       if (NewEltVT.bitsLT(EltVT)) {
3288
3289         // Convert shuffle node.
3290         // If original node was v4i64 and the new EltVT is i32,
3291         // cast operands to v8i32 and re-build the mask.
3292
3293         // Calculate new VT, the size of the new VT should be equal to original.
3294         EVT NewVT =
3295             EVT::getVectorVT(*DAG.getContext(), NewEltVT,
3296                              VT.getSizeInBits() / NewEltVT.getSizeInBits());
3297         assert(NewVT.bitsEq(VT));
3298
3299         // cast operands to new VT
3300         Op0 = DAG.getNode(ISD::BITCAST, dl, NewVT, Op0);
3301         Op1 = DAG.getNode(ISD::BITCAST, dl, NewVT, Op1);
3302
3303         // Convert the shuffle mask
3304         unsigned int factor =
3305                          NewVT.getVectorNumElements()/VT.getVectorNumElements();
3306
3307         // EltVT gets smaller
3308         assert(factor > 0);
3309
3310         for (unsigned i = 0; i < VT.getVectorNumElements(); ++i) {
3311           if (Mask[i] < 0) {
3312             for (unsigned fi = 0; fi < factor; ++fi)
3313               NewMask.push_back(Mask[i]);
3314           }
3315           else {
3316             for (unsigned fi = 0; fi < factor; ++fi)
3317               NewMask.push_back(Mask[i]*factor+fi);
3318           }
3319         }
3320         Mask = NewMask;
3321         VT = NewVT;
3322       }
3323       EltVT = NewEltVT;
3324     }
3325     unsigned NumElems = VT.getVectorNumElements();
3326     SmallVector<SDValue, 16> Ops;
3327     for (unsigned i = 0; i != NumElems; ++i) {
3328       if (Mask[i] < 0) {
3329         Ops.push_back(DAG.getUNDEF(EltVT));
3330         continue;
3331       }
3332       unsigned Idx = Mask[i];
3333       if (Idx < NumElems)
3334         Ops.push_back(DAG.getNode(
3335             ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Op0,
3336             DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout()))));
3337       else
3338         Ops.push_back(DAG.getNode(
3339             ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Op1,
3340             DAG.getConstant(Idx - NumElems, dl,
3341                             TLI.getVectorIdxTy(DAG.getDataLayout()))));
3342     }
3343
3344     Tmp1 = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ops);
3345     // We may have changed the BUILD_VECTOR type. Cast it back to the Node type.
3346     Tmp1 = DAG.getNode(ISD::BITCAST, dl, Node->getValueType(0), Tmp1);
3347     Results.push_back(Tmp1);
3348     break;
3349   }
3350   case ISD::EXTRACT_ELEMENT: {
3351     EVT OpTy = Node->getOperand(0).getValueType();
3352     if (cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue()) {
3353       // 1 -> Hi
3354       Tmp1 = DAG.getNode(ISD::SRL, dl, OpTy, Node->getOperand(0),
3355                          DAG.getConstant(OpTy.getSizeInBits() / 2, dl,
3356                                          TLI.getShiftAmountTy(
3357                                              Node->getOperand(0).getValueType(),
3358                                              DAG.getDataLayout())));
3359       Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0), Tmp1);
3360     } else {
3361       // 0 -> Lo
3362       Tmp1 = DAG.getNode(ISD::TRUNCATE, dl, Node->getValueType(0),
3363                          Node->getOperand(0));
3364     }
3365     Results.push_back(Tmp1);
3366     break;
3367   }
3368   case ISD::STACKSAVE:
3369     // Expand to CopyFromReg if the target set
3370     // StackPointerRegisterToSaveRestore.
3371     if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
3372       Results.push_back(DAG.getCopyFromReg(Node->getOperand(0), dl, SP,
3373                                            Node->getValueType(0)));
3374       Results.push_back(Results[0].getValue(1));
3375     } else {
3376       Results.push_back(DAG.getUNDEF(Node->getValueType(0)));
3377       Results.push_back(Node->getOperand(0));
3378     }
3379     break;
3380   case ISD::STACKRESTORE:
3381     // Expand to CopyToReg if the target set
3382     // StackPointerRegisterToSaveRestore.
3383     if (unsigned SP = TLI.getStackPointerRegisterToSaveRestore()) {
3384       Results.push_back(DAG.getCopyToReg(Node->getOperand(0), dl, SP,
3385                                          Node->getOperand(1)));
3386     } else {
3387       Results.push_back(Node->getOperand(0));
3388     }
3389     break;
3390   case ISD::FCOPYSIGN:
3391     Results.push_back(ExpandFCOPYSIGN(Node));
3392     break;
3393   case ISD::FNEG:
3394     // Expand Y = FNEG(X) ->  Y = SUB -0.0, X
3395     Tmp1 = DAG.getConstantFP(-0.0, dl, Node->getValueType(0));
3396     Tmp1 = DAG.getNode(ISD::FSUB, dl, Node->getValueType(0), Tmp1,
3397                        Node->getOperand(0));
3398     Results.push_back(Tmp1);
3399     break;
3400   case ISD::FABS:
3401     Results.push_back(ExpandFABS(Node));
3402     break;
3403   case ISD::SMIN:
3404   case ISD::SMAX:
3405   case ISD::UMIN:
3406   case ISD::UMAX: {
3407     // Expand Y = MAX(A, B) -> Y = (A > B) ? A : B
3408     ISD::CondCode Pred;
3409     switch (Node->getOpcode()) {
3410     default: llvm_unreachable("How did we get here?");
3411     case ISD::SMAX: Pred = ISD::SETGT; break;
3412     case ISD::SMIN: Pred = ISD::SETLT; break;
3413     case ISD::UMAX: Pred = ISD::SETUGT; break;
3414     case ISD::UMIN: Pred = ISD::SETULT; break;
3415     }
3416     Tmp1 = Node->getOperand(0);
3417     Tmp2 = Node->getOperand(1);
3418     Tmp1 = DAG.getSelectCC(dl, Tmp1, Tmp2, Tmp1, Tmp2, Pred);
3419     Results.push_back(Tmp1);
3420     break;
3421   }
3422
3423   case ISD::FMINNUM:
3424     Results.push_back(ExpandFPLibCall(Node, RTLIB::FMIN_F32, RTLIB::FMIN_F64,
3425                                       RTLIB::FMIN_F80, RTLIB::FMIN_F128,
3426                                       RTLIB::FMIN_PPCF128));
3427     break;
3428   case ISD::FMAXNUM:
3429     Results.push_back(ExpandFPLibCall(Node, RTLIB::FMAX_F32, RTLIB::FMAX_F64,
3430                                       RTLIB::FMAX_F80, RTLIB::FMAX_F128,
3431                                       RTLIB::FMAX_PPCF128));
3432     break;
3433   case ISD::FSQRT:
3434     Results.push_back(ExpandFPLibCall(Node, RTLIB::SQRT_F32, RTLIB::SQRT_F64,
3435                                       RTLIB::SQRT_F80, RTLIB::SQRT_F128,
3436                                       RTLIB::SQRT_PPCF128));
3437     break;
3438   case ISD::FSIN:
3439   case ISD::FCOS: {
3440     EVT VT = Node->getValueType(0);
3441     bool isSIN = Node->getOpcode() == ISD::FSIN;
3442     // Turn fsin / fcos into ISD::FSINCOS node if there are a pair of fsin /
3443     // fcos which share the same operand and both are used.
3444     if ((TLI.isOperationLegalOrCustom(ISD::FSINCOS, VT) ||
3445          canCombineSinCosLibcall(Node, TLI, TM))
3446         && useSinCos(Node)) {
3447       SDVTList VTs = DAG.getVTList(VT, VT);
3448       Tmp1 = DAG.getNode(ISD::FSINCOS, dl, VTs, Node->getOperand(0));
3449       if (!isSIN)
3450         Tmp1 = Tmp1.getValue(1);
3451       Results.push_back(Tmp1);
3452     } else if (isSIN) {
3453       Results.push_back(ExpandFPLibCall(Node, RTLIB::SIN_F32, RTLIB::SIN_F64,
3454                                         RTLIB::SIN_F80, RTLIB::SIN_F128,
3455                                         RTLIB::SIN_PPCF128));
3456     } else {
3457       Results.push_back(ExpandFPLibCall(Node, RTLIB::COS_F32, RTLIB::COS_F64,
3458                                         RTLIB::COS_F80, RTLIB::COS_F128,
3459                                         RTLIB::COS_PPCF128));
3460     }
3461     break;
3462   }
3463   case ISD::FSINCOS:
3464     // Expand into sincos libcall.
3465     ExpandSinCosLibCall(Node, Results);
3466     break;
3467   case ISD::FLOG:
3468     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG_F32, RTLIB::LOG_F64,
3469                                       RTLIB::LOG_F80, RTLIB::LOG_F128,
3470                                       RTLIB::LOG_PPCF128));
3471     break;
3472   case ISD::FLOG2:
3473     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG2_F32, RTLIB::LOG2_F64,
3474                                       RTLIB::LOG2_F80, RTLIB::LOG2_F128,
3475                                       RTLIB::LOG2_PPCF128));
3476     break;
3477   case ISD::FLOG10:
3478     Results.push_back(ExpandFPLibCall(Node, RTLIB::LOG10_F32, RTLIB::LOG10_F64,
3479                                       RTLIB::LOG10_F80, RTLIB::LOG10_F128,
3480                                       RTLIB::LOG10_PPCF128));
3481     break;
3482   case ISD::FEXP:
3483     Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP_F32, RTLIB::EXP_F64,
3484                                       RTLIB::EXP_F80, RTLIB::EXP_F128,
3485                                       RTLIB::EXP_PPCF128));
3486     break;
3487   case ISD::FEXP2:
3488     Results.push_back(ExpandFPLibCall(Node, RTLIB::EXP2_F32, RTLIB::EXP2_F64,
3489                                       RTLIB::EXP2_F80, RTLIB::EXP2_F128,
3490                                       RTLIB::EXP2_PPCF128));
3491     break;
3492   case ISD::FTRUNC:
3493     Results.push_back(ExpandFPLibCall(Node, RTLIB::TRUNC_F32, RTLIB::TRUNC_F64,
3494                                       RTLIB::TRUNC_F80, RTLIB::TRUNC_F128,
3495                                       RTLIB::TRUNC_PPCF128));
3496     break;
3497   case ISD::FFLOOR:
3498     Results.push_back(ExpandFPLibCall(Node, RTLIB::FLOOR_F32, RTLIB::FLOOR_F64,
3499                                       RTLIB::FLOOR_F80, RTLIB::FLOOR_F128,
3500                                       RTLIB::FLOOR_PPCF128));
3501     break;
3502   case ISD::FCEIL:
3503     Results.push_back(ExpandFPLibCall(Node, RTLIB::CEIL_F32, RTLIB::CEIL_F64,
3504                                       RTLIB::CEIL_F80, RTLIB::CEIL_F128,
3505                                       RTLIB::CEIL_PPCF128));
3506     break;
3507   case ISD::FRINT:
3508     Results.push_back(ExpandFPLibCall(Node, RTLIB::RINT_F32, RTLIB::RINT_F64,
3509                                       RTLIB::RINT_F80, RTLIB::RINT_F128,
3510                                       RTLIB::RINT_PPCF128));
3511     break;
3512   case ISD::FNEARBYINT:
3513     Results.push_back(ExpandFPLibCall(Node, RTLIB::NEARBYINT_F32,
3514                                       RTLIB::NEARBYINT_F64,
3515                                       RTLIB::NEARBYINT_F80,
3516                                       RTLIB::NEARBYINT_F128,
3517                                       RTLIB::NEARBYINT_PPCF128));
3518     break;
3519   case ISD::FROUND:
3520     Results.push_back(ExpandFPLibCall(Node, RTLIB::ROUND_F32,
3521                                       RTLIB::ROUND_F64,
3522                                       RTLIB::ROUND_F80,
3523                                       RTLIB::ROUND_F128,
3524                                       RTLIB::ROUND_PPCF128));
3525     break;
3526   case ISD::FPOWI:
3527     Results.push_back(ExpandFPLibCall(Node, RTLIB::POWI_F32, RTLIB::POWI_F64,
3528                                       RTLIB::POWI_F80, RTLIB::POWI_F128,
3529                                       RTLIB::POWI_PPCF128));
3530     break;
3531   case ISD::FPOW:
3532     Results.push_back(ExpandFPLibCall(Node, RTLIB::POW_F32, RTLIB::POW_F64,
3533                                       RTLIB::POW_F80, RTLIB::POW_F128,
3534                                       RTLIB::POW_PPCF128));
3535     break;
3536   case ISD::FDIV:
3537     Results.push_back(ExpandFPLibCall(Node, RTLIB::DIV_F32, RTLIB::DIV_F64,
3538                                       RTLIB::DIV_F80, RTLIB::DIV_F128,
3539                                       RTLIB::DIV_PPCF128));
3540     break;
3541   case ISD::FREM:
3542     Results.push_back(ExpandFPLibCall(Node, RTLIB::REM_F32, RTLIB::REM_F64,
3543                                       RTLIB::REM_F80, RTLIB::REM_F128,
3544                                       RTLIB::REM_PPCF128));
3545     break;
3546   case ISD::FMA:
3547     Results.push_back(ExpandFPLibCall(Node, RTLIB::FMA_F32, RTLIB::FMA_F64,
3548                                       RTLIB::FMA_F80, RTLIB::FMA_F128,
3549                                       RTLIB::FMA_PPCF128));
3550     break;
3551   case ISD::FMAD:
3552     llvm_unreachable("Illegal fmad should never be formed");
3553
3554   case ISD::FADD:
3555     Results.push_back(ExpandFPLibCall(Node, RTLIB::ADD_F32, RTLIB::ADD_F64,
3556                                       RTLIB::ADD_F80, RTLIB::ADD_F128,
3557                                       RTLIB::ADD_PPCF128));
3558     break;
3559   case ISD::FMUL:
3560     Results.push_back(ExpandFPLibCall(Node, RTLIB::MUL_F32, RTLIB::MUL_F64,
3561                                       RTLIB::MUL_F80, RTLIB::MUL_F128,
3562                                       RTLIB::MUL_PPCF128));
3563     break;
3564   case ISD::FP16_TO_FP: {
3565     if (Node->getValueType(0) == MVT::f32) {
3566       Results.push_back(ExpandLibCall(RTLIB::FPEXT_F16_F32, Node, false));
3567       break;
3568     }
3569
3570     // We can extend to types bigger than f32 in two steps without changing the
3571     // result. Since "f16 -> f32" is much more commonly available, give CodeGen
3572     // the option of emitting that before resorting to a libcall.
3573     SDValue Res =
3574         DAG.getNode(ISD::FP16_TO_FP, dl, MVT::f32, Node->getOperand(0));
3575     Results.push_back(
3576         DAG.getNode(ISD::FP_EXTEND, dl, Node->getValueType(0), Res));
3577     break;
3578   }
3579   case ISD::FP_TO_FP16: {
3580     if (!TLI.useSoftFloat() && TM.Options.UnsafeFPMath) {
3581       SDValue Op = Node->getOperand(0);
3582       MVT SVT = Op.getSimpleValueType();
3583       if ((SVT == MVT::f64 || SVT == MVT::f80) &&
3584           TLI.isOperationLegalOrCustom(ISD::FP_TO_FP16, MVT::f32)) {
3585         // Under fastmath, we can expand this node into a fround followed by
3586         // a float-half conversion.
3587         SDValue FloatVal = DAG.getNode(ISD::FP_ROUND, dl, MVT::f32, Op,
3588                                        DAG.getIntPtrConstant(0, dl));
3589         Results.push_back(
3590             DAG.getNode(ISD::FP_TO_FP16, dl, MVT::i16, FloatVal));
3591         break;
3592       }
3593     }
3594
3595     RTLIB::Libcall LC =
3596         RTLIB::getFPROUND(Node->getOperand(0).getValueType(), MVT::f16);
3597     assert(LC != RTLIB::UNKNOWN_LIBCALL && "Unable to expand fp_to_fp16");
3598     Results.push_back(ExpandLibCall(LC, Node, false));
3599     break;
3600   }
3601   case ISD::ConstantFP: {
3602     ConstantFPSDNode *CFP = cast<ConstantFPSDNode>(Node);
3603     // Check to see if this FP immediate is already legal.
3604     // If this is a legal constant, turn it into a TargetConstantFP node.
3605     if (!TLI.isFPImmLegal(CFP->getValueAPF(), Node->getValueType(0)))
3606       Results.push_back(ExpandConstantFP(CFP, true));
3607     break;
3608   }
3609   case ISD::FSUB: {
3610     EVT VT = Node->getValueType(0);
3611     if (TLI.isOperationLegalOrCustom(ISD::FADD, VT) &&
3612         TLI.isOperationLegalOrCustom(ISD::FNEG, VT)) {
3613       Tmp1 = DAG.getNode(ISD::FNEG, dl, VT, Node->getOperand(1));
3614       Tmp1 = DAG.getNode(ISD::FADD, dl, VT, Node->getOperand(0), Tmp1);
3615       Results.push_back(Tmp1);
3616     } else {
3617       Results.push_back(ExpandFPLibCall(Node, RTLIB::SUB_F32, RTLIB::SUB_F64,
3618                                         RTLIB::SUB_F80, RTLIB::SUB_F128,
3619                                         RTLIB::SUB_PPCF128));
3620     }
3621     break;
3622   }
3623   case ISD::SUB: {
3624     EVT VT = Node->getValueType(0);
3625     assert(TLI.isOperationLegalOrCustom(ISD::ADD, VT) &&
3626            TLI.isOperationLegalOrCustom(ISD::XOR, VT) &&
3627            "Don't know how to expand this subtraction!");
3628     Tmp1 = DAG.getNode(ISD::XOR, dl, VT, Node->getOperand(1),
3629                DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), dl,
3630                                VT));
3631     Tmp1 = DAG.getNode(ISD::ADD, dl, VT, Tmp1, DAG.getConstant(1, dl, VT));
3632     Results.push_back(DAG.getNode(ISD::ADD, dl, VT, Node->getOperand(0), Tmp1));
3633     break;
3634   }
3635   case ISD::UREM:
3636   case ISD::SREM: {
3637     EVT VT = Node->getValueType(0);
3638     bool isSigned = Node->getOpcode() == ISD::SREM;
3639     unsigned DivOpc = isSigned ? ISD::SDIV : ISD::UDIV;
3640     unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
3641     Tmp2 = Node->getOperand(0);
3642     Tmp3 = Node->getOperand(1);
3643     if (TLI.isOperationLegalOrCustom(DivRemOpc, VT) ||
3644         (isDivRemLibcallAvailable(Node, isSigned, TLI) &&
3645          // If div is legal, it's better to do the normal expansion
3646          !TLI.isOperationLegalOrCustom(DivOpc, Node->getValueType(0)) &&
3647          useDivRem(Node, isSigned, false))) {
3648       SDVTList VTs = DAG.getVTList(VT, VT);
3649       Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Tmp2, Tmp3).getValue(1);
3650     } else if (TLI.isOperationLegalOrCustom(DivOpc, VT)) {
3651       // X % Y -> X-X/Y*Y
3652       Tmp1 = DAG.getNode(DivOpc, dl, VT, Tmp2, Tmp3);
3653       Tmp1 = DAG.getNode(ISD::MUL, dl, VT, Tmp1, Tmp3);
3654       Tmp1 = DAG.getNode(ISD::SUB, dl, VT, Tmp2, Tmp1);
3655     } else if (isSigned)
3656       Tmp1 = ExpandIntLibCall(Node, true,
3657                               RTLIB::SREM_I8,
3658                               RTLIB::SREM_I16, RTLIB::SREM_I32,
3659                               RTLIB::SREM_I64, RTLIB::SREM_I128);
3660     else
3661       Tmp1 = ExpandIntLibCall(Node, false,
3662                               RTLIB::UREM_I8,
3663                               RTLIB::UREM_I16, RTLIB::UREM_I32,
3664                               RTLIB::UREM_I64, RTLIB::UREM_I128);
3665     Results.push_back(Tmp1);
3666     break;
3667   }
3668   case ISD::UDIV:
3669   case ISD::SDIV: {
3670     bool isSigned = Node->getOpcode() == ISD::SDIV;
3671     unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
3672     EVT VT = Node->getValueType(0);
3673     SDVTList VTs = DAG.getVTList(VT, VT);
3674     if (TLI.isOperationLegalOrCustom(DivRemOpc, VT) ||
3675         (isDivRemLibcallAvailable(Node, isSigned, TLI) &&
3676          useDivRem(Node, isSigned, true)))
3677       Tmp1 = DAG.getNode(DivRemOpc, dl, VTs, Node->getOperand(0),
3678                          Node->getOperand(1));
3679     else if (isSigned)
3680       Tmp1 = ExpandIntLibCall(Node, true,
3681                               RTLIB::SDIV_I8,
3682                               RTLIB::SDIV_I16, RTLIB::SDIV_I32,
3683                               RTLIB::SDIV_I64, RTLIB::SDIV_I128);
3684     else
3685       Tmp1 = ExpandIntLibCall(Node, false,
3686                               RTLIB::UDIV_I8,
3687                               RTLIB::UDIV_I16, RTLIB::UDIV_I32,
3688                               RTLIB::UDIV_I64, RTLIB::UDIV_I128);
3689     Results.push_back(Tmp1);
3690     break;
3691   }
3692   case ISD::MULHU:
3693   case ISD::MULHS: {
3694     unsigned ExpandOpcode = Node->getOpcode() == ISD::MULHU ? ISD::UMUL_LOHI :
3695                                                               ISD::SMUL_LOHI;
3696     EVT VT = Node->getValueType(0);
3697     SDVTList VTs = DAG.getVTList(VT, VT);
3698     assert(TLI.isOperationLegalOrCustom(ExpandOpcode, VT) &&
3699            "If this wasn't legal, it shouldn't have been created!");
3700     Tmp1 = DAG.getNode(ExpandOpcode, dl, VTs, Node->getOperand(0),
3701                        Node->getOperand(1));
3702     Results.push_back(Tmp1.getValue(1));
3703     break;
3704   }
3705   case ISD::SDIVREM:
3706   case ISD::UDIVREM:
3707     // Expand into divrem libcall
3708     ExpandDivRemLibCall(Node, Results);
3709     break;
3710   case ISD::MUL: {
3711     EVT VT = Node->getValueType(0);
3712     SDVTList VTs = DAG.getVTList(VT, VT);
3713     // See if multiply or divide can be lowered using two-result operations.
3714     // We just need the low half of the multiply; try both the signed
3715     // and unsigned forms. If the target supports both SMUL_LOHI and
3716     // UMUL_LOHI, form a preference by checking which forms of plain
3717     // MULH it supports.
3718     bool HasSMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::SMUL_LOHI, VT);
3719     bool HasUMUL_LOHI = TLI.isOperationLegalOrCustom(ISD::UMUL_LOHI, VT);
3720     bool HasMULHS = TLI.isOperationLegalOrCustom(ISD::MULHS, VT);
3721     bool HasMULHU = TLI.isOperationLegalOrCustom(ISD::MULHU, VT);
3722     unsigned OpToUse = 0;
3723     if (HasSMUL_LOHI && !HasMULHS) {
3724       OpToUse = ISD::SMUL_LOHI;
3725     } else if (HasUMUL_LOHI && !HasMULHU) {
3726       OpToUse = ISD::UMUL_LOHI;
3727     } else if (HasSMUL_LOHI) {
3728       OpToUse = ISD::SMUL_LOHI;
3729     } else if (HasUMUL_LOHI) {
3730       OpToUse = ISD::UMUL_LOHI;
3731     }
3732     if (OpToUse) {
3733       Results.push_back(DAG.getNode(OpToUse, dl, VTs, Node->getOperand(0),
3734                                     Node->getOperand(1)));
3735       break;
3736     }
3737
3738     SDValue Lo, Hi;
3739     EVT HalfType = VT.getHalfSizedIntegerVT(*DAG.getContext());
3740     if (TLI.isOperationLegalOrCustom(ISD::ZERO_EXTEND, VT) &&
3741         TLI.isOperationLegalOrCustom(ISD::ANY_EXTEND, VT) &&
3742         TLI.isOperationLegalOrCustom(ISD::SHL, VT) &&
3743         TLI.isOperationLegalOrCustom(ISD::OR, VT) &&
3744         TLI.expandMUL(Node, Lo, Hi, HalfType, DAG)) {
3745       Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Lo);
3746       Hi = DAG.getNode(ISD::ANY_EXTEND, dl, VT, Hi);
3747       SDValue Shift =
3748           DAG.getConstant(HalfType.getSizeInBits(), dl,
3749                           TLI.getShiftAmountTy(HalfType, DAG.getDataLayout()));
3750       Hi = DAG.getNode(ISD::SHL, dl, VT, Hi, Shift);
3751       Results.push_back(DAG.getNode(ISD::OR, dl, VT, Lo, Hi));
3752       break;
3753     }
3754
3755     Tmp1 = ExpandIntLibCall(Node, false,
3756                             RTLIB::MUL_I8,
3757                             RTLIB::MUL_I16, RTLIB::MUL_I32,
3758                             RTLIB::MUL_I64, RTLIB::MUL_I128);
3759     Results.push_back(Tmp1);
3760     break;
3761   }
3762   case ISD::SADDO:
3763   case ISD::SSUBO: {
3764     SDValue LHS = Node->getOperand(0);
3765     SDValue RHS = Node->getOperand(1);
3766     SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::SADDO ?
3767                               ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3768                               LHS, RHS);
3769     Results.push_back(Sum);
3770     EVT ResultType = Node->getValueType(1);
3771     EVT OType = getSetCCResultType(Node->getValueType(0));
3772
3773     SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
3774
3775     //   LHSSign -> LHS >= 0
3776     //   RHSSign -> RHS >= 0
3777     //   SumSign -> Sum >= 0
3778     //
3779     //   Add:
3780     //   Overflow -> (LHSSign == RHSSign) && (LHSSign != SumSign)
3781     //   Sub:
3782     //   Overflow -> (LHSSign != RHSSign) && (LHSSign != SumSign)
3783     //
3784     SDValue LHSSign = DAG.getSetCC(dl, OType, LHS, Zero, ISD::SETGE);
3785     SDValue RHSSign = DAG.getSetCC(dl, OType, RHS, Zero, ISD::SETGE);
3786     SDValue SignsMatch = DAG.getSetCC(dl, OType, LHSSign, RHSSign,
3787                                       Node->getOpcode() == ISD::SADDO ?
3788                                       ISD::SETEQ : ISD::SETNE);
3789
3790     SDValue SumSign = DAG.getSetCC(dl, OType, Sum, Zero, ISD::SETGE);
3791     SDValue SumSignNE = DAG.getSetCC(dl, OType, LHSSign, SumSign, ISD::SETNE);
3792
3793     SDValue Cmp = DAG.getNode(ISD::AND, dl, OType, SignsMatch, SumSignNE);
3794     Results.push_back(DAG.getBoolExtOrTrunc(Cmp, dl, ResultType, ResultType));
3795     break;
3796   }
3797   case ISD::UADDO:
3798   case ISD::USUBO: {
3799     SDValue LHS = Node->getOperand(0);
3800     SDValue RHS = Node->getOperand(1);
3801     SDValue Sum = DAG.getNode(Node->getOpcode() == ISD::UADDO ?
3802                               ISD::ADD : ISD::SUB, dl, LHS.getValueType(),
3803                               LHS, RHS);
3804     Results.push_back(Sum);
3805
3806     EVT ResultType = Node->getValueType(1);
3807     EVT SetCCType = getSetCCResultType(Node->getValueType(0));
3808     ISD::CondCode CC
3809       = Node->getOpcode() == ISD::UADDO ? ISD::SETULT : ISD::SETUGT;
3810     SDValue SetCC = DAG.getSetCC(dl, SetCCType, Sum, LHS, CC);
3811
3812     Results.push_back(DAG.getBoolExtOrTrunc(SetCC, dl, ResultType, ResultType));
3813     break;
3814   }
3815   case ISD::UMULO:
3816   case ISD::SMULO: {
3817     EVT VT = Node->getValueType(0);
3818     EVT WideVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits() * 2);
3819     SDValue LHS = Node->getOperand(0);
3820     SDValue RHS = Node->getOperand(1);
3821     SDValue BottomHalf;
3822     SDValue TopHalf;
3823     static const unsigned Ops[2][3] =
3824         { { ISD::MULHU, ISD::UMUL_LOHI, ISD::ZERO_EXTEND },
3825           { ISD::MULHS, ISD::SMUL_LOHI, ISD::SIGN_EXTEND }};
3826     bool isSigned = Node->getOpcode() == ISD::SMULO;
3827     if (TLI.isOperationLegalOrCustom(Ops[isSigned][0], VT)) {
3828       BottomHalf = DAG.getNode(ISD::MUL, dl, VT, LHS, RHS);
3829       TopHalf = DAG.getNode(Ops[isSigned][0], dl, VT, LHS, RHS);
3830     } else if (TLI.isOperationLegalOrCustom(Ops[isSigned][1], VT)) {
3831       BottomHalf = DAG.getNode(Ops[isSigned][1], dl, DAG.getVTList(VT, VT), LHS,
3832                                RHS);
3833       TopHalf = BottomHalf.getValue(1);
3834     } else if (TLI.isTypeLegal(WideVT)) {
3835       LHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, LHS);
3836       RHS = DAG.getNode(Ops[isSigned][2], dl, WideVT, RHS);
3837       Tmp1 = DAG.getNode(ISD::MUL, dl, WideVT, LHS, RHS);
3838       BottomHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1,
3839                                DAG.getIntPtrConstant(0, dl));
3840       TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Tmp1,
3841                             DAG.getIntPtrConstant(1, dl));
3842     } else {
3843       // We can fall back to a libcall with an illegal type for the MUL if we
3844       // have a libcall big enough.
3845       // Also, we can fall back to a division in some cases, but that's a big
3846       // performance hit in the general case.
3847       RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
3848       if (WideVT == MVT::i16)
3849         LC = RTLIB::MUL_I16;
3850       else if (WideVT == MVT::i32)
3851         LC = RTLIB::MUL_I32;
3852       else if (WideVT == MVT::i64)
3853         LC = RTLIB::MUL_I64;
3854       else if (WideVT == MVT::i128)
3855         LC = RTLIB::MUL_I128;
3856       assert(LC != RTLIB::UNKNOWN_LIBCALL && "Cannot expand this operation!");
3857
3858       // The high part is obtained by SRA'ing all but one of the bits of low
3859       // part.
3860       unsigned LoSize = VT.getSizeInBits();
3861       SDValue HiLHS =
3862           DAG.getNode(ISD::SRA, dl, VT, RHS,
3863                       DAG.getConstant(LoSize - 1, dl,
3864                                       TLI.getPointerTy(DAG.getDataLayout())));
3865       SDValue HiRHS =
3866           DAG.getNode(ISD::SRA, dl, VT, LHS,
3867                       DAG.getConstant(LoSize - 1, dl,
3868                                       TLI.getPointerTy(DAG.getDataLayout())));
3869
3870       // Here we're passing the 2 arguments explicitly as 4 arguments that are
3871       // pre-lowered to the correct types. This all depends upon WideVT not
3872       // being a legal type for the architecture and thus has to be split to
3873       // two arguments.
3874       SDValue Args[] = { LHS, HiLHS, RHS, HiRHS };
3875       SDValue Ret = ExpandLibCall(LC, WideVT, Args, 4, isSigned, dl);
3876       BottomHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Ret,
3877                                DAG.getIntPtrConstant(0, dl));
3878       TopHalf = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VT, Ret,
3879                             DAG.getIntPtrConstant(1, dl));
3880       // Ret is a node with an illegal type. Because such things are not
3881       // generally permitted during this phase of legalization, make sure the
3882       // node has no more uses. The above EXTRACT_ELEMENT nodes should have been
3883       // folded.
3884       assert(Ret->use_empty() &&
3885              "Unexpected uses of illegally type from expanded lib call.");
3886     }
3887
3888     if (isSigned) {
3889       Tmp1 = DAG.getConstant(
3890           VT.getSizeInBits() - 1, dl,
3891           TLI.getShiftAmountTy(BottomHalf.getValueType(), DAG.getDataLayout()));
3892       Tmp1 = DAG.getNode(ISD::SRA, dl, VT, BottomHalf, Tmp1);
3893       TopHalf = DAG.getSetCC(dl, getSetCCResultType(VT), TopHalf, Tmp1,
3894                              ISD::SETNE);
3895     } else {
3896       TopHalf = DAG.getSetCC(dl, getSetCCResultType(VT), TopHalf,
3897                              DAG.getConstant(0, dl, VT), ISD::SETNE);
3898     }
3899     Results.push_back(BottomHalf);
3900     Results.push_back(TopHalf);
3901     break;
3902   }
3903   case ISD::BUILD_PAIR: {
3904     EVT PairTy = Node->getValueType(0);
3905     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, PairTy, Node->getOperand(0));
3906     Tmp2 = DAG.getNode(ISD::ANY_EXTEND, dl, PairTy, Node->getOperand(1));
3907     Tmp2 = DAG.getNode(
3908         ISD::SHL, dl, PairTy, Tmp2,
3909         DAG.getConstant(PairTy.getSizeInBits() / 2, dl,
3910                         TLI.getShiftAmountTy(PairTy, DAG.getDataLayout())));
3911     Results.push_back(DAG.getNode(ISD::OR, dl, PairTy, Tmp1, Tmp2));
3912     break;
3913   }
3914   case ISD::SELECT:
3915     Tmp1 = Node->getOperand(0);
3916     Tmp2 = Node->getOperand(1);
3917     Tmp3 = Node->getOperand(2);
3918     if (Tmp1.getOpcode() == ISD::SETCC) {
3919       Tmp1 = DAG.getSelectCC(dl, Tmp1.getOperand(0), Tmp1.getOperand(1),
3920                              Tmp2, Tmp3,
3921                              cast<CondCodeSDNode>(Tmp1.getOperand(2))->get());
3922     } else {
3923       Tmp1 = DAG.getSelectCC(dl, Tmp1,
3924                              DAG.getConstant(0, dl, Tmp1.getValueType()),
3925                              Tmp2, Tmp3, ISD::SETNE);
3926     }
3927     Results.push_back(Tmp1);
3928     break;
3929   case ISD::BR_JT: {
3930     SDValue Chain = Node->getOperand(0);
3931     SDValue Table = Node->getOperand(1);
3932     SDValue Index = Node->getOperand(2);
3933
3934     EVT PTy = TLI.getPointerTy(DAG.getDataLayout());
3935
3936     const DataLayout &TD = DAG.getDataLayout();
3937     unsigned EntrySize =
3938       DAG.getMachineFunction().getJumpTableInfo()->getEntrySize(TD);
3939
3940     Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index,
3941                         DAG.getConstant(EntrySize, dl, Index.getValueType()));
3942     SDValue Addr = DAG.getNode(ISD::ADD, dl, Index.getValueType(),
3943                                Index, Table);
3944
3945     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), EntrySize * 8);
3946     SDValue LD = DAG.getExtLoad(ISD::SEXTLOAD, dl, PTy, Chain, Addr,
3947                                 MachinePointerInfo::getJumpTable(), MemVT,
3948                                 false, false, false, 0);
3949     Addr = LD;
3950     if (TM.getRelocationModel() == Reloc::PIC_) {
3951       // For PIC, the sequence is:
3952       // BRIND(load(Jumptable + index) + RelocBase)
3953       // RelocBase can be JumpTable, GOT or some sort of global base.
3954       Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr,
3955                           TLI.getPICJumpTableRelocBase(Table, DAG));
3956     }
3957     Tmp1 = DAG.getNode(ISD::BRIND, dl, MVT::Other, LD.getValue(1), Addr);
3958     Results.push_back(Tmp1);
3959     break;
3960   }
3961   case ISD::BRCOND:
3962     // Expand brcond's setcc into its constituent parts and create a BR_CC
3963     // Node.
3964     Tmp1 = Node->getOperand(0);
3965     Tmp2 = Node->getOperand(1);
3966     if (Tmp2.getOpcode() == ISD::SETCC) {
3967       Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other,
3968                          Tmp1, Tmp2.getOperand(2),
3969                          Tmp2.getOperand(0), Tmp2.getOperand(1),
3970                          Node->getOperand(2));
3971     } else {
3972       // We test only the i1 bit.  Skip the AND if UNDEF.
3973       Tmp3 = (Tmp2.getOpcode() == ISD::UNDEF) ? Tmp2 :
3974         DAG.getNode(ISD::AND, dl, Tmp2.getValueType(), Tmp2,
3975                     DAG.getConstant(1, dl, Tmp2.getValueType()));
3976       Tmp1 = DAG.getNode(ISD::BR_CC, dl, MVT::Other, Tmp1,
3977                          DAG.getCondCode(ISD::SETNE), Tmp3,
3978                          DAG.getConstant(0, dl, Tmp3.getValueType()),
3979                          Node->getOperand(2));
3980     }
3981     Results.push_back(Tmp1);
3982     break;
3983   case ISD::SETCC: {
3984     Tmp1 = Node->getOperand(0);
3985     Tmp2 = Node->getOperand(1);
3986     Tmp3 = Node->getOperand(2);
3987     bool Legalized = LegalizeSetCCCondCode(Node->getValueType(0), Tmp1, Tmp2,
3988                                            Tmp3, NeedInvert, dl);
3989
3990     if (Legalized) {
3991       // If we expanded the SETCC by swapping LHS and RHS, or by inverting the
3992       // condition code, create a new SETCC node.
3993       if (Tmp3.getNode())
3994         Tmp1 = DAG.getNode(ISD::SETCC, dl, Node->getValueType(0),
3995                            Tmp1, Tmp2, Tmp3);
3996
3997       // If we expanded the SETCC by inverting the condition code, then wrap
3998       // the existing SETCC in a NOT to restore the intended condition.
3999       if (NeedInvert)
4000         Tmp1 = DAG.getLogicalNOT(dl, Tmp1, Tmp1->getValueType(0));
4001
4002       Results.push_back(Tmp1);
4003       break;
4004     }
4005
4006     // Otherwise, SETCC for the given comparison type must be completely
4007     // illegal; expand it into a SELECT_CC.
4008     EVT VT = Node->getValueType(0);
4009     int TrueValue;
4010     switch (TLI.getBooleanContents(Tmp1->getValueType(0))) {
4011     case TargetLowering::ZeroOrOneBooleanContent:
4012     case TargetLowering::UndefinedBooleanContent:
4013       TrueValue = 1;
4014       break;
4015     case TargetLowering::ZeroOrNegativeOneBooleanContent:
4016       TrueValue = -1;
4017       break;
4018     }
4019     Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, VT, Tmp1, Tmp2,
4020                        DAG.getConstant(TrueValue, dl, VT),
4021                        DAG.getConstant(0, dl, VT),
4022                        Tmp3);
4023     Results.push_back(Tmp1);
4024     break;
4025   }
4026   case ISD::SELECT_CC: {
4027     Tmp1 = Node->getOperand(0);   // LHS
4028     Tmp2 = Node->getOperand(1);   // RHS
4029     Tmp3 = Node->getOperand(2);   // True
4030     Tmp4 = Node->getOperand(3);   // False
4031     EVT VT = Node->getValueType(0);
4032     SDValue CC = Node->getOperand(4);
4033     ISD::CondCode CCOp = cast<CondCodeSDNode>(CC)->get();
4034
4035     if (TLI.isCondCodeLegal(CCOp, Tmp1.getSimpleValueType())) {
4036       // If the condition code is legal, then we need to expand this
4037       // node using SETCC and SELECT.
4038       EVT CmpVT = Tmp1.getValueType();
4039       assert(!TLI.isOperationExpand(ISD::SELECT, VT) &&
4040              "Cannot expand ISD::SELECT_CC when ISD::SELECT also needs to be "
4041              "expanded.");
4042       EVT CCVT =
4043           TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), CmpVT);
4044       SDValue Cond = DAG.getNode(ISD::SETCC, dl, CCVT, Tmp1, Tmp2, CC);
4045       Results.push_back(DAG.getSelect(dl, VT, Cond, Tmp3, Tmp4));
4046       break;
4047     }
4048
4049     // SELECT_CC is legal, so the condition code must not be.
4050     bool Legalized = false;
4051     // Try to legalize by inverting the condition.  This is for targets that
4052     // might support an ordered version of a condition, but not the unordered
4053     // version (or vice versa).
4054     ISD::CondCode InvCC = ISD::getSetCCInverse(CCOp,
4055                                                Tmp1.getValueType().isInteger());
4056     if (TLI.isCondCodeLegal(InvCC, Tmp1.getSimpleValueType())) {
4057       // Use the new condition code and swap true and false
4058       Legalized = true;
4059       Tmp1 = DAG.getSelectCC(dl, Tmp1, Tmp2, Tmp4, Tmp3, InvCC);
4060     } else {
4061       // If The inverse is not legal, then try to swap the arguments using
4062       // the inverse condition code.
4063       ISD::CondCode SwapInvCC = ISD::getSetCCSwappedOperands(InvCC);
4064       if (TLI.isCondCodeLegal(SwapInvCC, Tmp1.getSimpleValueType())) {
4065         // The swapped inverse condition is legal, so swap true and false,
4066         // lhs and rhs.
4067         Legalized = true;
4068         Tmp1 = DAG.getSelectCC(dl, Tmp2, Tmp1, Tmp4, Tmp3, SwapInvCC);
4069       }
4070     }
4071
4072     if (!Legalized) {
4073       Legalized = LegalizeSetCCCondCode(
4074           getSetCCResultType(Tmp1.getValueType()), Tmp1, Tmp2, CC, NeedInvert,
4075           dl);
4076
4077       assert(Legalized && "Can't legalize SELECT_CC with legal condition!");
4078
4079       // If we expanded the SETCC by inverting the condition code, then swap
4080       // the True/False operands to match.
4081       if (NeedInvert)
4082         std::swap(Tmp3, Tmp4);
4083
4084       // If we expanded the SETCC by swapping LHS and RHS, or by inverting the
4085       // condition code, create a new SELECT_CC node.
4086       if (CC.getNode()) {
4087         Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, Node->getValueType(0),
4088                            Tmp1, Tmp2, Tmp3, Tmp4, CC);
4089       } else {
4090         Tmp2 = DAG.getConstant(0, dl, Tmp1.getValueType());
4091         CC = DAG.getCondCode(ISD::SETNE);
4092         Tmp1 = DAG.getNode(ISD::SELECT_CC, dl, Node->getValueType(0), Tmp1,
4093                            Tmp2, Tmp3, Tmp4, CC);
4094       }
4095     }
4096     Results.push_back(Tmp1);
4097     break;
4098   }
4099   case ISD::BR_CC: {
4100     Tmp1 = Node->getOperand(0);              // Chain
4101     Tmp2 = Node->getOperand(2);              // LHS
4102     Tmp3 = Node->getOperand(3);              // RHS
4103     Tmp4 = Node->getOperand(1);              // CC
4104
4105     bool Legalized = LegalizeSetCCCondCode(getSetCCResultType(
4106         Tmp2.getValueType()), Tmp2, Tmp3, Tmp4, NeedInvert, dl);
4107     (void)Legalized;
4108     assert(Legalized && "Can't legalize BR_CC with legal condition!");
4109
4110     // If we expanded the SETCC by inverting the condition code, then wrap
4111     // the existing SETCC in a NOT to restore the intended condition.
4112     if (NeedInvert)
4113       Tmp4 = DAG.getNOT(dl, Tmp4, Tmp4->getValueType(0));
4114
4115     // If we expanded the SETCC by swapping LHS and RHS, create a new BR_CC
4116     // node.
4117     if (Tmp4.getNode()) {
4118       Tmp1 = DAG.getNode(ISD::BR_CC, dl, Node->getValueType(0), Tmp1,
4119                          Tmp4, Tmp2, Tmp3, Node->getOperand(4));
4120     } else {
4121       Tmp3 = DAG.getConstant(0, dl, Tmp2.getValueType());
4122       Tmp4 = DAG.getCondCode(ISD::SETNE);
4123       Tmp1 = DAG.getNode(ISD::BR_CC, dl, Node->getValueType(0), Tmp1, Tmp4,
4124                          Tmp2, Tmp3, Node->getOperand(4));
4125     }
4126     Results.push_back(Tmp1);
4127     break;
4128   }
4129   case ISD::BUILD_VECTOR:
4130     Results.push_back(ExpandBUILD_VECTOR(Node));
4131     break;
4132   case ISD::SRA:
4133   case ISD::SRL:
4134   case ISD::SHL: {
4135     // Scalarize vector SRA/SRL/SHL.
4136     EVT VT = Node->getValueType(0);
4137     assert(VT.isVector() && "Unable to legalize non-vector shift");
4138     assert(TLI.isTypeLegal(VT.getScalarType())&& "Element type must be legal");
4139     unsigned NumElem = VT.getVectorNumElements();
4140
4141     SmallVector<SDValue, 8> Scalars;
4142     for (unsigned Idx = 0; Idx < NumElem; Idx++) {
4143       SDValue Ex = DAG.getNode(
4144           ISD::EXTRACT_VECTOR_ELT, dl, VT.getScalarType(), Node->getOperand(0),
4145           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4146       SDValue Sh = DAG.getNode(
4147           ISD::EXTRACT_VECTOR_ELT, dl, VT.getScalarType(), Node->getOperand(1),
4148           DAG.getConstant(Idx, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
4149       Scalars.push_back(DAG.getNode(Node->getOpcode(), dl,
4150                                     VT.getScalarType(), Ex, Sh));
4151     }
4152     SDValue Result =
4153       DAG.getNode(ISD::BUILD_VECTOR, dl, Node->getValueType(0), Scalars);
4154     ReplaceNode(SDValue(Node, 0), Result);
4155     break;
4156   }
4157   case ISD::GLOBAL_OFFSET_TABLE:
4158   case ISD::GlobalAddress:
4159   case ISD::GlobalTLSAddress:
4160   case ISD::ExternalSymbol:
4161   case ISD::ConstantPool:
4162   case ISD::JumpTable:
4163   case ISD::INTRINSIC_W_CHAIN:
4164   case ISD::INTRINSIC_WO_CHAIN:
4165   case ISD::INTRINSIC_VOID:
4166     // FIXME: Custom lowering for these operations shouldn't return null!
4167     break;
4168   }
4169
4170   // Replace the original node with the legalized result.
4171   if (!Results.empty())
4172     ReplaceNode(Node, Results.data());
4173 }
4174
4175 void SelectionDAGLegalize::PromoteNode(SDNode *Node) {
4176   SmallVector<SDValue, 8> Results;
4177   MVT OVT = Node->getSimpleValueType(0);
4178   if (Node->getOpcode() == ISD::UINT_TO_FP ||
4179       Node->getOpcode() == ISD::SINT_TO_FP ||
4180       Node->getOpcode() == ISD::SETCC) {
4181     OVT = Node->getOperand(0).getSimpleValueType();
4182   }
4183   if (Node->getOpcode() == ISD::BR_CC)
4184     OVT = Node->getOperand(2).getSimpleValueType();
4185   MVT NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
4186   SDLoc dl(Node);
4187   SDValue Tmp1, Tmp2, Tmp3;
4188   switch (Node->getOpcode()) {
4189   case ISD::CTTZ:
4190   case ISD::CTTZ_ZERO_UNDEF:
4191   case ISD::CTLZ:
4192   case ISD::CTLZ_ZERO_UNDEF:
4193   case ISD::CTPOP:
4194     // Zero extend the argument.
4195     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0));
4196     // Perform the larger operation. For CTPOP and CTTZ_ZERO_UNDEF, this is
4197     // already the correct result.
4198     Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1);
4199     if (Node->getOpcode() == ISD::CTTZ) {
4200       // FIXME: This should set a bit in the zero extended value instead.
4201       Tmp2 = DAG.getSetCC(dl, getSetCCResultType(NVT),
4202                           Tmp1, DAG.getConstant(NVT.getSizeInBits(), dl, NVT),
4203                           ISD::SETEQ);
4204       Tmp1 = DAG.getSelect(dl, NVT, Tmp2,
4205                            DAG.getConstant(OVT.getSizeInBits(), dl, NVT), Tmp1);
4206     } else if (Node->getOpcode() == ISD::CTLZ ||
4207                Node->getOpcode() == ISD::CTLZ_ZERO_UNDEF) {
4208       // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
4209       Tmp1 = DAG.getNode(ISD::SUB, dl, NVT, Tmp1,
4210                           DAG.getConstant(NVT.getSizeInBits() -
4211                                           OVT.getSizeInBits(), dl, NVT));
4212     }
4213     Results.push_back(DAG.getNode(ISD::TRUNCATE, dl, OVT, Tmp1));
4214     break;
4215   case ISD::BSWAP: {
4216     unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits();
4217     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0));
4218     Tmp1 = DAG.getNode(ISD::BSWAP, dl, NVT, Tmp1);
4219     Tmp1 = DAG.getNode(
4220         ISD::SRL, dl, NVT, Tmp1,
4221         DAG.getConstant(DiffBits, dl,
4222                         TLI.getShiftAmountTy(NVT, DAG.getDataLayout())));
4223     Results.push_back(Tmp1);
4224     break;
4225   }
4226   case ISD::FP_TO_UINT:
4227   case ISD::FP_TO_SINT:
4228     Tmp1 = PromoteLegalFP_TO_INT(Node->getOperand(0), Node->getValueType(0),
4229                                  Node->getOpcode() == ISD::FP_TO_SINT, dl);
4230     Results.push_back(Tmp1);
4231     break;
4232   case ISD::UINT_TO_FP:
4233   case ISD::SINT_TO_FP:
4234     Tmp1 = PromoteLegalINT_TO_FP(Node->getOperand(0), Node->getValueType(0),
4235                                  Node->getOpcode() == ISD::SINT_TO_FP, dl);
4236     Results.push_back(Tmp1);
4237     break;
4238   case ISD::VAARG: {
4239     SDValue Chain = Node->getOperand(0); // Get the chain.
4240     SDValue Ptr = Node->getOperand(1); // Get the pointer.
4241
4242     unsigned TruncOp;
4243     if (OVT.isVector()) {
4244       TruncOp = ISD::BITCAST;
4245     } else {
4246       assert(OVT.isInteger()
4247         && "VAARG promotion is supported only for vectors or integer types");
4248       TruncOp = ISD::TRUNCATE;
4249     }
4250
4251     // Perform the larger operation, then convert back
4252     Tmp1 = DAG.getVAArg(NVT, dl, Chain, Ptr, Node->getOperand(2),
4253              Node->getConstantOperandVal(3));
4254     Chain = Tmp1.getValue(1);
4255
4256     Tmp2 = DAG.getNode(TruncOp, dl, OVT, Tmp1);
4257
4258     // Modified the chain result - switch anything that used the old chain to
4259     // use the new one.
4260     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 0), Tmp2);
4261     DAG.ReplaceAllUsesOfValueWith(SDValue(Node, 1), Chain);
4262     if (UpdatedNodes) {
4263       UpdatedNodes->insert(Tmp2.getNode());
4264       UpdatedNodes->insert(Chain.getNode());
4265     }
4266     ReplacedNode(Node);
4267     break;
4268   }
4269   case ISD::AND:
4270   case ISD::OR:
4271   case ISD::XOR: {
4272     unsigned ExtOp, TruncOp;
4273     if (OVT.isVector()) {
4274       ExtOp   = ISD::BITCAST;
4275       TruncOp = ISD::BITCAST;
4276     } else {
4277       assert(OVT.isInteger() && "Cannot promote logic operation");
4278       ExtOp   = ISD::ANY_EXTEND;
4279       TruncOp = ISD::TRUNCATE;
4280     }
4281     // Promote each of the values to the new type.
4282     Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0));
4283     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
4284     // Perform the larger operation, then convert back
4285     Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
4286     Results.push_back(DAG.getNode(TruncOp, dl, OVT, Tmp1));
4287     break;
4288   }
4289   case ISD::SELECT: {
4290     unsigned ExtOp, TruncOp;
4291     if (Node->getValueType(0).isVector() ||
4292         Node->getValueType(0).getSizeInBits() == NVT.getSizeInBits()) {
4293       ExtOp   = ISD::BITCAST;
4294       TruncOp = ISD::BITCAST;
4295     } else if (Node->getValueType(0).isInteger()) {
4296       ExtOp   = ISD::ANY_EXTEND;
4297       TruncOp = ISD::TRUNCATE;
4298     } else {
4299       ExtOp   = ISD::FP_EXTEND;
4300       TruncOp = ISD::FP_ROUND;
4301     }
4302     Tmp1 = Node->getOperand(0);
4303     // Promote each of the values to the new type.
4304     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
4305     Tmp3 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(2));
4306     // Perform the larger operation, then round down.
4307     Tmp1 = DAG.getSelect(dl, NVT, Tmp1, Tmp2, Tmp3);
4308     if (TruncOp != ISD::FP_ROUND)
4309       Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1);
4310     else
4311       Tmp1 = DAG.getNode(TruncOp, dl, Node->getValueType(0), Tmp1,
4312                          DAG.getIntPtrConstant(0, dl));
4313     Results.push_back(Tmp1);
4314     break;
4315   }
4316   case ISD::VECTOR_SHUFFLE: {
4317     ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
4318
4319     // Cast the two input vectors.
4320     Tmp1 = DAG.getNode(ISD::BITCAST, dl, NVT, Node->getOperand(0));
4321     Tmp2 = DAG.getNode(ISD::BITCAST, dl, NVT, Node->getOperand(1));
4322
4323     // Convert the shuffle mask to the right # elements.
4324     Tmp1 = ShuffleWithNarrowerEltType(NVT, OVT, dl, Tmp1, Tmp2, Mask);
4325     Tmp1 = DAG.getNode(ISD::BITCAST, dl, OVT, Tmp1);
4326     Results.push_back(Tmp1);
4327     break;
4328   }
4329   case ISD::SETCC: {
4330     unsigned ExtOp = ISD::FP_EXTEND;
4331     if (NVT.isInteger()) {
4332       ISD::CondCode CCCode =
4333         cast<CondCodeSDNode>(Node->getOperand(2))->get();
4334       ExtOp = isSignedIntSetCC(CCCode) ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
4335     }
4336     Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(0));
4337     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(1));
4338     Results.push_back(DAG.getNode(ISD::SETCC, dl, Node->getValueType(0),
4339                                   Tmp1, Tmp2, Node->getOperand(2)));
4340     break;
4341   }
4342   case ISD::BR_CC: {
4343     unsigned ExtOp = ISD::FP_EXTEND;
4344     if (NVT.isInteger()) {
4345       ISD::CondCode CCCode =
4346         cast<CondCodeSDNode>(Node->getOperand(1))->get();
4347       ExtOp = isSignedIntSetCC(CCCode) ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
4348     }
4349     Tmp1 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(2));
4350     Tmp2 = DAG.getNode(ExtOp, dl, NVT, Node->getOperand(3));
4351     Results.push_back(DAG.getNode(ISD::BR_CC, dl, Node->getValueType(0),
4352                                   Node->getOperand(0), Node->getOperand(1),
4353                                   Tmp1, Tmp2, Node->getOperand(4)));
4354     break;
4355   }
4356   case ISD::FADD:
4357   case ISD::FSUB:
4358   case ISD::FMUL:
4359   case ISD::FDIV:
4360   case ISD::FREM:
4361   case ISD::FMINNUM:
4362   case ISD::FMAXNUM:
4363   case ISD::FCOPYSIGN:
4364   case ISD::FPOW: {
4365     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
4366     Tmp2 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(1));
4367     Tmp3 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
4368     Results.push_back(DAG.getNode(ISD::FP_ROUND, dl, OVT,
4369                                   Tmp3, DAG.getIntPtrConstant(0, dl)));
4370     break;
4371   }
4372   case ISD::FMA: {
4373     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
4374     Tmp2 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(1));
4375     Tmp3 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(2));
4376     Results.push_back(
4377         DAG.getNode(ISD::FP_ROUND, dl, OVT,
4378                     DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2, Tmp3),
4379                     DAG.getIntPtrConstant(0, dl)));
4380     break;
4381   }
4382   case ISD::FPOWI: {
4383     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
4384     Tmp2 = Node->getOperand(1);
4385     Tmp3 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1, Tmp2);
4386     Results.push_back(DAG.getNode(ISD::FP_ROUND, dl, OVT,
4387                                   Tmp3, DAG.getIntPtrConstant(0, dl)));
4388     break;
4389   }
4390   case ISD::FFLOOR:
4391   case ISD::FCEIL:
4392   case ISD::FRINT:
4393   case ISD::FNEARBYINT:
4394   case ISD::FROUND:
4395   case ISD::FTRUNC:
4396   case ISD::FNEG:
4397   case ISD::FSQRT:
4398   case ISD::FSIN:
4399   case ISD::FCOS:
4400   case ISD::FLOG:
4401   case ISD::FLOG2:
4402   case ISD::FLOG10:
4403   case ISD::FABS:
4404   case ISD::FEXP:
4405   case ISD::FEXP2: {
4406     Tmp1 = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Node->getOperand(0));
4407     Tmp2 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1);
4408     Results.push_back(DAG.getNode(ISD::FP_ROUND, dl, OVT,
4409                                   Tmp2, DAG.getIntPtrConstant(0, dl)));
4410     break;
4411   }
4412   }
4413
4414   // Replace the original node with the legalized result.
4415   if (!Results.empty())
4416     ReplaceNode(Node, Results.data());
4417 }
4418
4419 /// This is the entry point for the file.
4420 void SelectionDAG::Legalize() {
4421   AssignTopologicalOrder();
4422
4423   SmallPtrSet<SDNode *, 16> LegalizedNodes;
4424   SelectionDAGLegalize Legalizer(*this, LegalizedNodes);
4425
4426   // Visit all the nodes. We start in topological order, so that we see
4427   // nodes with their original operands intact. Legalization can produce
4428   // new nodes which may themselves need to be legalized. Iterate until all
4429   // nodes have been legalized.
4430   for (;;) {
4431     bool AnyLegalized = false;
4432     for (auto NI = allnodes_end(); NI != allnodes_begin();) {
4433       --NI;
4434
4435       SDNode *N = NI;
4436       if (N->use_empty() && N != getRoot().getNode()) {
4437         ++NI;
4438         DeleteNode(N);
4439         continue;
4440       }
4441
4442       if (LegalizedNodes.insert(N).second) {
4443         AnyLegalized = true;
4444         Legalizer.LegalizeOp(N);
4445
4446         if (N->use_empty() && N != getRoot().getNode()) {
4447           ++NI;
4448           DeleteNode(N);
4449         }
4450       }
4451     }
4452     if (!AnyLegalized)
4453       break;
4454
4455   }
4456
4457   // Remove dead nodes now.
4458   RemoveDeadNodes();
4459 }
4460
4461 bool SelectionDAG::LegalizeOp(SDNode *N,
4462                               SmallSetVector<SDNode *, 16> &UpdatedNodes) {
4463   SmallPtrSet<SDNode *, 16> LegalizedNodes;
4464   SelectionDAGLegalize Legalizer(*this, LegalizedNodes, &UpdatedNodes);
4465
4466   // Directly insert the node in question, and legalize it. This will recurse
4467   // as needed through operands.
4468   LegalizedNodes.insert(N);
4469   Legalizer.LegalizeOp(N);
4470
4471   return LegalizedNodes.count(N);
4472 }