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