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