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