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