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