lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

   1 //===- LegalizeVectorOps.cpp - Implement SelectionDAG::LegalizeVectors ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SelectionDAG::LegalizeVectors method.
  11 //
  12 // The vector legalizer looks for vector operations which might need to be
  13 // scalarized and legalizes them. This is a separate step from Legalize because
  14 // scalarizing can introduce illegal types.  For example, suppose we have an
  15 // ISD::SDIV of type v2i64 on x86-32.  The type is legal (for example, addition
  16 // on a v2i64 is legal), but ISD::SDIV isn't legal, so we have to unroll the
  17 // operation, which introduces nodes with the illegal type i64 which must be
  18 // expanded.  Similarly, suppose we have an ISD::SRA of type v16i8 on PowerPC;
  19 // the operation must be unrolled, which introduces nodes with the illegal
  20 // type i8 which must be promoted.
  21 //
  22 // This does not legalize vector manipulations like ISD::BUILD_VECTOR,
  23 // or operations that happen to take a vector which are custom-lowered;
  24 // the legalization for such operations never produces nodes
  25 // with illegal types, so it's okay to put off legalizing them until
  26 // SelectionDAG::Legalize runs.
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #include "llvm/ADT/APInt.h"
  31 #include "llvm/ADT/DenseMap.h"
  32 #include "llvm/ADT/SmallVector.h"
  33 #include "llvm/CodeGen/ISDOpcodes.h"
  34 #include "llvm/CodeGen/MachineMemOperand.h"
  35 #include "llvm/CodeGen/SelectionDAG.h"
  36 #include "llvm/CodeGen/SelectionDAGNodes.h"
  37 #include "llvm/CodeGen/TargetLowering.h"
  38 #include "llvm/CodeGen/ValueTypes.h"
  39 #include "llvm/IR/DataLayout.h"
  40 #include "llvm/Support/Casting.h"
  41 #include "llvm/Support/Compiler.h"
  42 #include "llvm/Support/ErrorHandling.h"
  43 #include "llvm/Support/MachineValueType.h"
  44 #include "llvm/Support/MathExtras.h"
  45 #include <cassert>
  46 #include <cstdint>
  47 #include <iterator>
  48 #include <utility>
  49
  50 using namespace llvm;
  51
  52 #define DEBUG_TYPE "legalizevectorops"
  53
  54 namespace {
  55
  56 class VectorLegalizer {
  57   SelectionDAG& DAG;
  58   const TargetLowering &TLI;
  59   bool Changed = false; // Keep track of whether anything changed
  60
  61   /// For nodes that are of legal width, and that have more than one use, this
  62   /// map indicates what regularized operand to use.  This allows us to avoid
  63   /// legalizing the same thing more than once.
  64   SmallDenseMap<SDValue, SDValue, 64> LegalizedNodes;
  65
  66   /// Adds a node to the translation cache.
  67   void AddLegalizedOperand(SDValue From, SDValue To) {
  68     LegalizedNodes.insert(std::make_pair(From, To));
  69     // If someone requests legalization of the new node, return itself.
  70     if (From != To)
  71       LegalizedNodes.insert(std::make_pair(To, To));
  72   }
  73
  74   /// Legalizes the given node.
  75   SDValue LegalizeOp(SDValue Op);
  76
  77   /// Assuming the node is legal, "legalize" the results.
  78   SDValue TranslateLegalizeResults(SDValue Op, SDValue Result);
  79
  80   /// Implements unrolling a VSETCC.
  81   SDValue UnrollVSETCC(SDValue Op);
  82
  83   /// Implement expand-based legalization of vector operations.
  84   ///
  85   /// This is just a high-level routine to dispatch to specific code paths for
  86   /// operations to legalize them.
  87   SDValue Expand(SDValue Op);
  88
  89   /// Implements expansion for FP_TO_UINT; falls back to UnrollVectorOp if
  90   /// FP_TO_SINT isn't legal.
  91   SDValue ExpandFP_TO_UINT(SDValue Op);
  92
  93   /// Implements expansion for UINT_TO_FLOAT; falls back to UnrollVectorOp if
  94   /// SINT_TO_FLOAT and SHR on vectors isn't legal.
  95   SDValue ExpandUINT_TO_FLOAT(SDValue Op);
  96
  97   /// Implement expansion for SIGN_EXTEND_INREG using SRL and SRA.
  98   SDValue ExpandSEXTINREG(SDValue Op);
  99
 100   /// Implement expansion for ANY_EXTEND_VECTOR_INREG.
 101   ///
 102   /// Shuffles the low lanes of the operand into place and bitcasts to the proper
 103   /// type. The contents of the bits in the extended part of each element are
 104   /// undef.
 105   SDValue ExpandANY_EXTEND_VECTOR_INREG(SDValue Op);
 106
 107   /// Implement expansion for SIGN_EXTEND_VECTOR_INREG.
 108   ///
 109   /// Shuffles the low lanes of the operand into place, bitcasts to the proper
 110   /// type, then shifts left and arithmetic shifts right to introduce a sign
 111   /// extension.
 112   SDValue ExpandSIGN_EXTEND_VECTOR_INREG(SDValue Op);
 113
 114   /// Implement expansion for ZERO_EXTEND_VECTOR_INREG.
 115   ///
 116   /// Shuffles the low lanes of the operand into place and blends zeros into
 117   /// the remaining lanes, finally bitcasting to the proper type.
 118   SDValue ExpandZERO_EXTEND_VECTOR_INREG(SDValue Op);
 119
 120   /// Expand bswap of vectors into a shuffle if legal.
 121   SDValue ExpandBSWAP(SDValue Op);
 122
 123   /// Implement vselect in terms of XOR, AND, OR when blend is not
 124   /// supported by the target.
 125   SDValue ExpandVSELECT(SDValue Op);
 126   SDValue ExpandSELECT(SDValue Op);
 127   SDValue ExpandLoad(SDValue Op);
 128   SDValue ExpandStore(SDValue Op);
 129   SDValue ExpandFNEG(SDValue Op);
 130   SDValue ExpandFSUB(SDValue Op);
 131   SDValue ExpandBITREVERSE(SDValue Op);
 132   SDValue ExpandCTPOP(SDValue Op);
 133   SDValue ExpandCTLZ(SDValue Op);
 134   SDValue ExpandCTTZ(SDValue Op);
 135   SDValue ExpandFunnelShift(SDValue Op);
 136   SDValue ExpandFMINNUM_FMAXNUM(SDValue Op);
 137   SDValue ExpandStrictFPOp(SDValue Op);
 138
 139   /// Implements vector promotion.
 140   ///
 141   /// This is essentially just bitcasting the operands to a different type and
 142   /// bitcasting the result back to the original type.
 143   SDValue Promote(SDValue Op);
 144
 145   /// Implements [SU]INT_TO_FP vector promotion.
 146   ///
 147   /// This is a [zs]ext of the input operand to a larger integer type.
 148   SDValue PromoteINT_TO_FP(SDValue Op);
 149
 150   /// Implements FP_TO_[SU]INT vector promotion of the result type.
 151   ///
 152   /// It is promoted to a larger integer type.  The result is then
 153   /// truncated back to the original type.
 154   SDValue PromoteFP_TO_INT(SDValue Op);
 155
 156 public:
 157   VectorLegalizer(SelectionDAG& dag) :
 158       DAG(dag), TLI(dag.getTargetLoweringInfo()) {}
 159
 160   /// Begin legalizer the vector operations in the DAG.
 161   bool Run();
 162 };
 163
 164 } // end anonymous namespace
 165
 166 bool VectorLegalizer::Run() {
 167   // Before we start legalizing vector nodes, check if there are any vectors.
 168   bool HasVectors = false;
 169   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 170        E = std::prev(DAG.allnodes_end()); I != std::next(E); ++I) {
 171     // Check if the values of the nodes contain vectors. We don't need to check
 172     // the operands because we are going to check their values at some point.
 173     for (SDNode::value_iterator J = I->value_begin(), E = I->value_end();
 174          J != E; ++J)
 175       HasVectors |= J->isVector();
 176
 177     // If we found a vector node we can start the legalization.
 178     if (HasVectors)
 179       break;
 180   }
 181
 182   // If this basic block has no vectors then no need to legalize vectors.
 183   if (!HasVectors)
 184     return false;
 185
 186   // The legalize process is inherently a bottom-up recursive process (users
 187   // legalize their uses before themselves).  Given infinite stack space, we
 188   // could just start legalizing on the root and traverse the whole graph.  In
 189   // practice however, this causes us to run out of stack space on large basic
 190   // blocks.  To avoid this problem, compute an ordering of the nodes where each
 191   // node is only legalized after all of its operands are legalized.
 192   DAG.AssignTopologicalOrder();
 193   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 194        E = std::prev(DAG.allnodes_end()); I != std::next(E); ++I)
 195     LegalizeOp(SDValue(&*I, 0));
 196
 197   // Finally, it's possible the root changed.  Get the new root.
 198   SDValue OldRoot = DAG.getRoot();
 199   assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
 200   DAG.setRoot(LegalizedNodes[OldRoot]);
 201
 202   LegalizedNodes.clear();
 203
 204   // Remove dead nodes now.
 205   DAG.RemoveDeadNodes();
 206
 207   return Changed;
 208 }
 209
 210 SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) {
 211   // Generic legalization: just pass the operand through.
 212   for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i)
 213     AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 214   return Result.getValue(Op.getResNo());
 215 }
 216
 217 SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
 218   // Note that LegalizeOp may be reentered even from single-use nodes, which
 219   // means that we always must cache transformed nodes.
 220   DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
 221   if (I != LegalizedNodes.end()) return I->second;
 222
 223   SDNode* Node = Op.getNode();
 224
 225   // Legalize the operands
 226   SmallVector<SDValue, 8> Ops;
 227   for (const SDValue &Op : Node->op_values())
 228     Ops.push_back(LegalizeOp(Op));
 229
 230   SDValue Result = SDValue(DAG.UpdateNodeOperands(Op.getNode(), Ops),
 231                            Op.getResNo());
 232
 233   if (Op.getOpcode() == ISD::LOAD) {
 234     LoadSDNode *LD = cast<LoadSDNode>(Op.getNode());
 235     ISD::LoadExtType ExtType = LD->getExtensionType();
 236     if (LD->getMemoryVT().isVector() && ExtType != ISD::NON_EXTLOAD) {
 237       LLVM_DEBUG(dbgs() << "\nLegalizing extending vector load: ";
 238                  Node->dump(&DAG));
 239       switch (TLI.getLoadExtAction(LD->getExtensionType(), LD->getValueType(0),
 240                                    LD->getMemoryVT())) {
 241       default: llvm_unreachable("This action is not supported yet!");
 242       case TargetLowering::Legal:
 243         return TranslateLegalizeResults(Op, Result);
 244       case TargetLowering::Custom:
 245         if (SDValue Lowered = TLI.LowerOperation(Result, DAG)) {
 246           assert(Lowered->getNumValues() == Op->getNumValues() &&
 247                  "Unexpected number of results");
 248           if (Lowered != Result) {
 249             // Make sure the new code is also legal.
 250             Lowered = LegalizeOp(Lowered);
 251             Changed = true;
 252           }
 253           return TranslateLegalizeResults(Op, Lowered);
 254         }
 255         LLVM_FALLTHROUGH;
 256       case TargetLowering::Expand:
 257         Changed = true;
 258         return LegalizeOp(ExpandLoad(Op));
 259       }
 260     }
 261   } else if (Op.getOpcode() == ISD::STORE) {
 262     StoreSDNode *ST = cast<StoreSDNode>(Op.getNode());
 263     EVT StVT = ST->getMemoryVT();
 264     MVT ValVT = ST->getValue().getSimpleValueType();
 265     if (StVT.isVector() && ST->isTruncatingStore()) {
 266       LLVM_DEBUG(dbgs() << "\nLegalizing truncating vector store: ";
 267                  Node->dump(&DAG));
 268       switch (TLI.getTruncStoreAction(ValVT, StVT)) {
 269       default: llvm_unreachable("This action is not supported yet!");
 270       case TargetLowering::Legal:
 271         return TranslateLegalizeResults(Op, Result);
 272       case TargetLowering::Custom: {
 273         SDValue Lowered = TLI.LowerOperation(Result, DAG);
 274         if (Lowered != Result) {
 275           // Make sure the new code is also legal.
 276           Lowered = LegalizeOp(Lowered);
 277           Changed = true;
 278         }
 279         return TranslateLegalizeResults(Op, Lowered);
 280       }
 281       case TargetLowering::Expand:
 282         Changed = true;
 283         return LegalizeOp(ExpandStore(Op));
 284       }
 285     }
 286   }
 287
 288   bool HasVectorValue = false;
 289   for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end();
 290        J != E;
 291        ++J)
 292     HasVectorValue |= J->isVector();
 293   if (!HasVectorValue)
 294     return TranslateLegalizeResults(Op, Result);
 295
 296   TargetLowering::LegalizeAction Action = TargetLowering::Legal;
 297   switch (Op.getOpcode()) {
 298   default:
 299     return TranslateLegalizeResults(Op, Result);
 300   case ISD::STRICT_FADD:
 301   case ISD::STRICT_FSUB:
 302   case ISD::STRICT_FMUL:
 303   case ISD::STRICT_FDIV:
 304   case ISD::STRICT_FREM:
 305   case ISD::STRICT_FSQRT:
 306   case ISD::STRICT_FMA:
 307   case ISD::STRICT_FPOW:
 308   case ISD::STRICT_FPOWI:
 309   case ISD::STRICT_FSIN:
 310   case ISD::STRICT_FCOS:
 311   case ISD::STRICT_FEXP:
 312   case ISD::STRICT_FEXP2:
 313   case ISD::STRICT_FLOG:
 314   case ISD::STRICT_FLOG10:
 315   case ISD::STRICT_FLOG2:
 316   case ISD::STRICT_FRINT:
 317   case ISD::STRICT_FNEARBYINT:
 318   case ISD::STRICT_FMAXNUM:
 319   case ISD::STRICT_FMINNUM:
 320   case ISD::STRICT_FCEIL:
 321   case ISD::STRICT_FFLOOR:
 322   case ISD::STRICT_FROUND:
 323   case ISD::STRICT_FTRUNC:
 324     // These pseudo-ops get legalized as if they were their non-strict
 325     // equivalent.  For instance, if ISD::FSQRT is legal then ISD::STRICT_FSQRT
 326     // is also legal, but if ISD::FSQRT requires expansion then so does
 327     // ISD::STRICT_FSQRT.
 328     Action = TLI.getStrictFPOperationAction(Node->getOpcode(),
 329                                             Node->getValueType(0));
 330     break;
 331   case ISD::ADD:
 332   case ISD::SUB:
 333   case ISD::MUL:
 334   case ISD::MULHS:
 335   case ISD::MULHU:
 336   case ISD::SDIV:
 337   case ISD::UDIV:
 338   case ISD::SREM:
 339   case ISD::UREM:
 340   case ISD::SDIVREM:
 341   case ISD::UDIVREM:
 342   case ISD::FADD:
 343   case ISD::FSUB:
 344   case ISD::FMUL:
 345   case ISD::FDIV:
 346   case ISD::FREM:
 347   case ISD::AND:
 348   case ISD::OR:
 349   case ISD::XOR:
 350   case ISD::SHL:
 351   case ISD::SRA:
 352   case ISD::SRL:
 353   case ISD::ROTL:
 354   case ISD::ROTR:
 355   case ISD::BSWAP:
 356   case ISD::BITREVERSE:
 357   case ISD::CTLZ:
 358   case ISD::CTTZ:
 359   case ISD::CTLZ_ZERO_UNDEF:
 360   case ISD::CTTZ_ZERO_UNDEF:
 361   case ISD::CTPOP:
 362   case ISD::SELECT:
 363   case ISD::VSELECT:
 364   case ISD::SELECT_CC:
 365   case ISD::SETCC:
 366   case ISD::ZERO_EXTEND:
 367   case ISD::ANY_EXTEND:
 368   case ISD::TRUNCATE:
 369   case ISD::SIGN_EXTEND:
 370   case ISD::FP_TO_SINT:
 371   case ISD::FP_TO_UINT:
 372   case ISD::FNEG:
 373   case ISD::FABS:
 374   case ISD::FMINNUM:
 375   case ISD::FMAXNUM:
 376   case ISD::FMINNUM_IEEE:
 377   case ISD::FMAXNUM_IEEE:
 378   case ISD::FMINIMUM:
 379   case ISD::FMAXIMUM:
 380   case ISD::FCOPYSIGN:
 381   case ISD::FSQRT:
 382   case ISD::FSIN:
 383   case ISD::FCOS:
 384   case ISD::FPOWI:
 385   case ISD::FPOW:
 386   case ISD::FLOG:
 387   case ISD::FLOG2:
 388   case ISD::FLOG10:
 389   case ISD::FEXP:
 390   case ISD::FEXP2:
 391   case ISD::FCEIL:
 392   case ISD::FTRUNC:
 393   case ISD::FRINT:
 394   case ISD::FNEARBYINT:
 395   case ISD::FROUND:
 396   case ISD::FFLOOR:
 397   case ISD::FP_ROUND:
 398   case ISD::FP_EXTEND:
 399   case ISD::FMA:
 400   case ISD::SIGN_EXTEND_INREG:
 401   case ISD::ANY_EXTEND_VECTOR_INREG:
 402   case ISD::SIGN_EXTEND_VECTOR_INREG:
 403   case ISD::ZERO_EXTEND_VECTOR_INREG:
 404   case ISD::SMIN:
 405   case ISD::SMAX:
 406   case ISD::UMIN:
 407   case ISD::UMAX:
 408   case ISD::SMUL_LOHI:
 409   case ISD::UMUL_LOHI:
 410   case ISD::FCANONICALIZE:
 411   case ISD::SADDSAT:
 412   case ISD::UADDSAT:
 413   case ISD::SSUBSAT:
 414   case ISD::USUBSAT:
 415     Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
 416     break;
 417   case ISD::SMULFIX: {
 418     unsigned Scale = Node->getConstantOperandVal(2);
 419     Action = TLI.getFixedPointOperationAction(Node->getOpcode(),
 420                                               Node->getValueType(0), Scale);
 421     break;
 422   }
 423   case ISD::FP_ROUND_INREG:
 424     Action = TLI.getOperationAction(Node->getOpcode(),
 425                cast<VTSDNode>(Node->getOperand(1))->getVT());
 426     break;
 427   case ISD::SINT_TO_FP:
 428   case ISD::UINT_TO_FP:
 429     Action = TLI.getOperationAction(Node->getOpcode(),
 430                                     Node->getOperand(0).getValueType());
 431     break;
 432   }
 433
 434   LLVM_DEBUG(dbgs() << "\nLegalizing vector op: "; Node->dump(&DAG));
 435
 436   switch (Action) {
 437   default: llvm_unreachable("This action is not supported yet!");
 438   case TargetLowering::Promote:
 439     Result = Promote(Op);
 440     Changed = true;
 441     break;
 442   case TargetLowering::Legal:
 443     LLVM_DEBUG(dbgs() << "Legal node: nothing to do\n");
 444     break;
 445   case TargetLowering::Custom: {
 446     LLVM_DEBUG(dbgs() << "Trying custom legalization\n");
 447     if (SDValue Tmp1 = TLI.LowerOperation(Op, DAG)) {
 448       LLVM_DEBUG(dbgs() << "Successfully custom legalized node\n");
 449       Result = Tmp1;
 450       break;
 451     }
 452     LLVM_DEBUG(dbgs() << "Could not custom legalize node\n");
 453     LLVM_FALLTHROUGH;
 454   }
 455   case TargetLowering::Expand:
 456     Result = Expand(Op);
 457   }
 458
 459   // Make sure that the generated code is itself legal.
 460   if (Result != Op) {
 461     Result = LegalizeOp(Result);
 462     Changed = true;
 463   }
 464
 465   // Note that LegalizeOp may be reentered even from single-use nodes, which
 466   // means that we always must cache transformed nodes.
 467   AddLegalizedOperand(Op, Result);
 468   return Result;
 469 }
 470
 471 SDValue VectorLegalizer::Promote(SDValue Op) {
 472   // For a few operations there is a specific concept for promotion based on
 473   // the operand's type.
 474   switch (Op.getOpcode()) {
 475   case ISD::SINT_TO_FP:
 476   case ISD::UINT_TO_FP:
 477     // "Promote" the operation by extending the operand.
 478     return PromoteINT_TO_FP(Op);
 479   case ISD::FP_TO_UINT:
 480   case ISD::FP_TO_SINT:
 481     // Promote the operation by extending the operand.
 482     return PromoteFP_TO_INT(Op);
 483   }
 484
 485   // There are currently two cases of vector promotion:
 486   // 1) Bitcasting a vector of integers to a different type to a vector of the
 487   //    same overall length. For example, x86 promotes ISD::AND v2i32 to v1i64.
 488   // 2) Extending a vector of floats to a vector of the same number of larger
 489   //    floats. For example, AArch64 promotes ISD::FADD on v4f16 to v4f32.
 490   MVT VT = Op.getSimpleValueType();
 491   assert(Op.getNode()->getNumValues() == 1 &&
 492          "Can't promote a vector with multiple results!");
 493   MVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
 494   SDLoc dl(Op);
 495   SmallVector<SDValue, 4> Operands(Op.getNumOperands());
 496
 497   for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
 498     if (Op.getOperand(j).getValueType().isVector())
 499       if (Op.getOperand(j)
 500               .getValueType()
 501               .getVectorElementType()
 502               .isFloatingPoint() &&
 503           NVT.isVector() && NVT.getVectorElementType().isFloatingPoint())
 504         Operands[j] = DAG.getNode(ISD::FP_EXTEND, dl, NVT, Op.getOperand(j));
 505       else
 506         Operands[j] = DAG.getNode(ISD::BITCAST, dl, NVT, Op.getOperand(j));
 507     else
 508       Operands[j] = Op.getOperand(j);
 509   }
 510
 511   Op = DAG.getNode(Op.getOpcode(), dl, NVT, Operands, Op.getNode()->getFlags());
 512   if ((VT.isFloatingPoint() && NVT.isFloatingPoint()) ||
 513       (VT.isVector() && VT.getVectorElementType().isFloatingPoint() &&
 514        NVT.isVector() && NVT.getVectorElementType().isFloatingPoint()))
 515     return DAG.getNode(ISD::FP_ROUND, dl, VT, Op, DAG.getIntPtrConstant(0, dl));
 516   else
 517     return DAG.getNode(ISD::BITCAST, dl, VT, Op);
 518 }
 519
 520 SDValue VectorLegalizer::PromoteINT_TO_FP(SDValue Op) {
 521   // INT_TO_FP operations may require the input operand be promoted even
 522   // when the type is otherwise legal.
 523   MVT VT = Op.getOperand(0).getSimpleValueType();
 524   MVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
 525   assert(NVT.getVectorNumElements() == VT.getVectorNumElements() &&
 526          "Vectors have different number of elements!");
 527
 528   SDLoc dl(Op);
 529   SmallVector<SDValue, 4> Operands(Op.getNumOperands());
 530
 531   unsigned Opc = Op.getOpcode() == ISD::UINT_TO_FP ? ISD::ZERO_EXTEND :
 532     ISD::SIGN_EXTEND;
 533   for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
 534     if (Op.getOperand(j).getValueType().isVector())
 535       Operands[j] = DAG.getNode(Opc, dl, NVT, Op.getOperand(j));
 536     else
 537       Operands[j] = Op.getOperand(j);
 538   }
 539
 540   return DAG.getNode(Op.getOpcode(), dl, Op.getValueType(), Operands);
 541 }
 542
 543 // For FP_TO_INT we promote the result type to a vector type with wider
 544 // elements and then truncate the result.  This is different from the default
 545 // PromoteVector which uses bitcast to promote thus assumning that the
 546 // promoted vector type has the same overall size.
 547 SDValue VectorLegalizer::PromoteFP_TO_INT(SDValue Op) {
 548   MVT VT = Op.getSimpleValueType();
 549   MVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
 550   assert(NVT.getVectorNumElements() == VT.getVectorNumElements() &&
 551          "Vectors have different number of elements!");
 552
 553   unsigned NewOpc = Op->getOpcode();
 554   // Change FP_TO_UINT to FP_TO_SINT if possible.
 555   // TODO: Should we only do this if FP_TO_UINT itself isn't legal?
 556   if (NewOpc == ISD::FP_TO_UINT &&
 557       TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NVT))
 558     NewOpc = ISD::FP_TO_SINT;
 559
 560   SDLoc dl(Op);
 561   SDValue Promoted  = DAG.getNode(NewOpc, dl, NVT, Op.getOperand(0));
 562
 563   // Assert that the converted value fits in the original type.  If it doesn't
 564   // (eg: because the value being converted is too big), then the result of the
 565   // original operation was undefined anyway, so the assert is still correct.
 566   Promoted = DAG.getNode(Op->getOpcode() == ISD::FP_TO_UINT ? ISD::AssertZext
 567                                                             : ISD::AssertSext,
 568                          dl, NVT, Promoted,
 569                          DAG.getValueType(VT.getScalarType()));
 570   return DAG.getNode(ISD::TRUNCATE, dl, VT, Promoted);
 571 }
 572
 573 SDValue VectorLegalizer::ExpandLoad(SDValue Op) {
 574   LoadSDNode *LD = cast<LoadSDNode>(Op.getNode());
 575
 576   EVT SrcVT = LD->getMemoryVT();
 577   EVT SrcEltVT = SrcVT.getScalarType();
 578   unsigned NumElem = SrcVT.getVectorNumElements();
 579
 580   SDValue NewChain;
 581   SDValue Value;
 582   if (SrcVT.getVectorNumElements() > 1 && !SrcEltVT.isByteSized()) {
 583     SDLoc dl(Op);
 584
 585     SmallVector<SDValue, 8> Vals;
 586     SmallVector<SDValue, 8> LoadChains;
 587
 588     EVT DstEltVT = LD->getValueType(0).getScalarType();
 589     SDValue Chain = LD->getChain();
 590     SDValue BasePTR = LD->getBasePtr();
 591     ISD::LoadExtType ExtType = LD->getExtensionType();
 592
 593     // When elements in a vector is not byte-addressable, we cannot directly
 594     // load each element by advancing pointer, which could only address bytes.
 595     // Instead, we load all significant words, mask bits off, and concatenate
 596     // them to form each element. Finally, they are extended to destination
 597     // scalar type to build the destination vector.
 598     EVT WideVT = TLI.getPointerTy(DAG.getDataLayout());
 599
 600     assert(WideVT.isRound() &&
 601            "Could not handle the sophisticated case when the widest integer is"
 602            " not power of 2.");
 603     assert(WideVT.bitsGE(SrcEltVT) &&
 604            "Type is not legalized?");
 605
 606     unsigned WideBytes = WideVT.getStoreSize();
 607     unsigned Offset = 0;
 608     unsigned RemainingBytes = SrcVT.getStoreSize();
 609     SmallVector<SDValue, 8> LoadVals;
 610     while (RemainingBytes > 0) {
 611       SDValue ScalarLoad;
 612       unsigned LoadBytes = WideBytes;
 613
 614       if (RemainingBytes >= LoadBytes) {
 615         ScalarLoad =
 616             DAG.getLoad(WideVT, dl, Chain, BasePTR,
 617                         LD->getPointerInfo().getWithOffset(Offset),
 618                         MinAlign(LD->getAlignment(), Offset),
 619                         LD->getMemOperand()->getFlags(), LD->getAAInfo());
 620       } else {
 621         EVT LoadVT = WideVT;
 622         while (RemainingBytes < LoadBytes) {
 623           LoadBytes >>= 1; // Reduce the load size by half.
 624           LoadVT = EVT::getIntegerVT(*DAG.getContext(), LoadBytes << 3);
 625         }
 626         ScalarLoad =
 627             DAG.getExtLoad(ISD::EXTLOAD, dl, WideVT, Chain, BasePTR,
 628                            LD->getPointerInfo().getWithOffset(Offset), LoadVT,
 629                            MinAlign(LD->getAlignment(), Offset),
 630                            LD->getMemOperand()->getFlags(), LD->getAAInfo());
 631       }
 632
 633       RemainingBytes -= LoadBytes;
 634       Offset += LoadBytes;
 635
 636       BasePTR = DAG.getObjectPtrOffset(dl, BasePTR, LoadBytes);
 637
 638       LoadVals.push_back(ScalarLoad.getValue(0));
 639       LoadChains.push_back(ScalarLoad.getValue(1));
 640     }
 641
 642     // Extract bits, pack and extend/trunc them into destination type.
 643     unsigned SrcEltBits = SrcEltVT.getSizeInBits();
 644     SDValue SrcEltBitMask = DAG.getConstant((1U << SrcEltBits) - 1, dl, WideVT);
 645
 646     unsigned BitOffset = 0;
 647     unsigned WideIdx = 0;
 648     unsigned WideBits = WideVT.getSizeInBits();
 649
 650     for (unsigned Idx = 0; Idx != NumElem; ++Idx) {
 651       SDValue Lo, Hi, ShAmt;
 652
 653       if (BitOffset < WideBits) {
 654         ShAmt = DAG.getConstant(
 655             BitOffset, dl, TLI.getShiftAmountTy(WideVT, DAG.getDataLayout()));
 656         Lo = DAG.getNode(ISD::SRL, dl, WideVT, LoadVals[WideIdx], ShAmt);
 657         Lo = DAG.getNode(ISD::AND, dl, WideVT, Lo, SrcEltBitMask);
 658       }
 659
 660       BitOffset += SrcEltBits;
 661       if (BitOffset >= WideBits) {
 662         WideIdx++;
 663         BitOffset -= WideBits;
 664         if (BitOffset > 0) {
 665           ShAmt = DAG.getConstant(
 666               SrcEltBits - BitOffset, dl,
 667               TLI.getShiftAmountTy(WideVT, DAG.getDataLayout()));
 668           Hi = DAG.getNode(ISD::SHL, dl, WideVT, LoadVals[WideIdx], ShAmt);
 669           Hi = DAG.getNode(ISD::AND, dl, WideVT, Hi, SrcEltBitMask);
 670         }
 671       }
 672
 673       if (Hi.getNode())
 674         Lo = DAG.getNode(ISD::OR, dl, WideVT, Lo, Hi);
 675
 676       switch (ExtType) {
 677       default: llvm_unreachable("Unknown extended-load op!");
 678       case ISD::EXTLOAD:
 679         Lo = DAG.getAnyExtOrTrunc(Lo, dl, DstEltVT);
 680         break;
 681       case ISD::ZEXTLOAD:
 682         Lo = DAG.getZExtOrTrunc(Lo, dl, DstEltVT);
 683         break;
 684       case ISD::SEXTLOAD:
 685         ShAmt =
 686             DAG.getConstant(WideBits - SrcEltBits, dl,
 687                             TLI.getShiftAmountTy(WideVT, DAG.getDataLayout()));
 688         Lo = DAG.getNode(ISD::SHL, dl, WideVT, Lo, ShAmt);
 689         Lo = DAG.getNode(ISD::SRA, dl, WideVT, Lo, ShAmt);
 690         Lo = DAG.getSExtOrTrunc(Lo, dl, DstEltVT);
 691         break;
 692       }
 693       Vals.push_back(Lo);
 694     }
 695
 696     NewChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
 697     Value = DAG.getBuildVector(Op.getNode()->getValueType(0), dl, Vals);
 698   } else {
 699     SDValue Scalarized = TLI.scalarizeVectorLoad(LD, DAG);
 700     // Skip past MERGE_VALUE node if known.
 701     if (Scalarized->getOpcode() == ISD::MERGE_VALUES) {
 702       NewChain = Scalarized.getOperand(1);
 703       Value = Scalarized.getOperand(0);
 704     } else {
 705       NewChain = Scalarized.getValue(1);
 706       Value = Scalarized.getValue(0);
 707     }
 708   }
 709
 710   AddLegalizedOperand(Op.getValue(0), Value);
 711   AddLegalizedOperand(Op.getValue(1), NewChain);
 712
 713   return (Op.getResNo() ? NewChain : Value);
 714 }
 715
 716 SDValue VectorLegalizer::ExpandStore(SDValue Op) {
 717   StoreSDNode *ST = cast<StoreSDNode>(Op.getNode());
 718   SDValue TF = TLI.scalarizeVectorStore(ST, DAG);
 719   AddLegalizedOperand(Op, TF);
 720   return TF;
 721 }
 722
 723 SDValue VectorLegalizer::Expand(SDValue Op) {
 724   switch (Op->getOpcode()) {
 725   case ISD::SIGN_EXTEND_INREG:
 726     return ExpandSEXTINREG(Op);
 727   case ISD::ANY_EXTEND_VECTOR_INREG:
 728     return ExpandANY_EXTEND_VECTOR_INREG(Op);
 729   case ISD::SIGN_EXTEND_VECTOR_INREG:
 730     return ExpandSIGN_EXTEND_VECTOR_INREG(Op);
 731   case ISD::ZERO_EXTEND_VECTOR_INREG:
 732     return ExpandZERO_EXTEND_VECTOR_INREG(Op);
 733   case ISD::BSWAP:
 734     return ExpandBSWAP(Op);
 735   case ISD::VSELECT:
 736     return ExpandVSELECT(Op);
 737   case ISD::SELECT:
 738     return ExpandSELECT(Op);
 739   case ISD::FP_TO_UINT:
 740     return ExpandFP_TO_UINT(Op);
 741   case ISD::UINT_TO_FP:
 742     return ExpandUINT_TO_FLOAT(Op);
 743   case ISD::FNEG:
 744     return ExpandFNEG(Op);
 745   case ISD::FSUB:
 746     return ExpandFSUB(Op);
 747   case ISD::SETCC:
 748     return UnrollVSETCC(Op);
 749   case ISD::BITREVERSE:
 750     return ExpandBITREVERSE(Op);
 751   case ISD::CTPOP:
 752     return ExpandCTPOP(Op);
 753   case ISD::CTLZ:
 754   case ISD::CTLZ_ZERO_UNDEF:
 755     return ExpandCTLZ(Op);
 756   case ISD::CTTZ:
 757   case ISD::CTTZ_ZERO_UNDEF:
 758     return ExpandCTTZ(Op);
 759   case ISD::FSHL:
 760   case ISD::FSHR:
 761     return ExpandFunnelShift(Op);
 762   case ISD::FMINNUM:
 763   case ISD::FMAXNUM:
 764     return ExpandFMINNUM_FMAXNUM(Op);
 765   case ISD::STRICT_FADD:
 766   case ISD::STRICT_FSUB:
 767   case ISD::STRICT_FMUL:
 768   case ISD::STRICT_FDIV:
 769   case ISD::STRICT_FREM:
 770   case ISD::STRICT_FSQRT:
 771   case ISD::STRICT_FMA:
 772   case ISD::STRICT_FPOW:
 773   case ISD::STRICT_FPOWI:
 774   case ISD::STRICT_FSIN:
 775   case ISD::STRICT_FCOS:
 776   case ISD::STRICT_FEXP:
 777   case ISD::STRICT_FEXP2:
 778   case ISD::STRICT_FLOG:
 779   case ISD::STRICT_FLOG10:
 780   case ISD::STRICT_FLOG2:
 781   case ISD::STRICT_FRINT:
 782   case ISD::STRICT_FNEARBYINT:
 783   case ISD::STRICT_FMAXNUM:
 784   case ISD::STRICT_FMINNUM:
 785   case ISD::STRICT_FCEIL:
 786   case ISD::STRICT_FFLOOR:
 787   case ISD::STRICT_FROUND:
 788   case ISD::STRICT_FTRUNC:
 789     return ExpandStrictFPOp(Op);
 790   default:
 791     return DAG.UnrollVectorOp(Op.getNode());
 792   }
 793 }
 794
 795 SDValue VectorLegalizer::ExpandSELECT(SDValue Op) {
 796   // Lower a select instruction where the condition is a scalar and the
 797   // operands are vectors. Lower this select to VSELECT and implement it
 798   // using XOR AND OR. The selector bit is broadcasted.
 799   EVT VT = Op.getValueType();
 800   SDLoc DL(Op);
 801
 802   SDValue Mask = Op.getOperand(0);
 803   SDValue Op1 = Op.getOperand(1);
 804   SDValue Op2 = Op.getOperand(2);
 805
 806   assert(VT.isVector() && !Mask.getValueType().isVector()
 807          && Op1.getValueType() == Op2.getValueType() && "Invalid type");
 808
 809   // If we can't even use the basic vector operations of
 810   // AND,OR,XOR, we will have to scalarize the op.
 811   // Notice that the operation may be 'promoted' which means that it is
 812   // 'bitcasted' to another type which is handled.
 813   // Also, we need to be able to construct a splat vector using BUILD_VECTOR.
 814   if (TLI.getOperationAction(ISD::AND, VT) == TargetLowering::Expand ||
 815       TLI.getOperationAction(ISD::XOR, VT) == TargetLowering::Expand ||
 816       TLI.getOperationAction(ISD::OR,  VT) == TargetLowering::Expand ||
 817       TLI.getOperationAction(ISD::BUILD_VECTOR,  VT) == TargetLowering::Expand)
 818     return DAG.UnrollVectorOp(Op.getNode());
 819
 820   // Generate a mask operand.
 821   EVT MaskTy = VT.changeVectorElementTypeToInteger();
 822
 823   // What is the size of each element in the vector mask.
 824   EVT BitTy = MaskTy.getScalarType();
 825
 826   Mask = DAG.getSelect(DL, BitTy, Mask,
 827           DAG.getConstant(APInt::getAllOnesValue(BitTy.getSizeInBits()), DL,
 828                           BitTy),
 829           DAG.getConstant(0, DL, BitTy));
 830
 831   // Broadcast the mask so that the entire vector is all-one or all zero.
 832   Mask = DAG.getSplatBuildVector(MaskTy, DL, Mask);
 833
 834   // Bitcast the operands to be the same type as the mask.
 835   // This is needed when we select between FP types because
 836   // the mask is a vector of integers.
 837   Op1 = DAG.getNode(ISD::BITCAST, DL, MaskTy, Op1);
 838   Op2 = DAG.getNode(ISD::BITCAST, DL, MaskTy, Op2);
 839
 840   SDValue AllOnes = DAG.getConstant(
 841             APInt::getAllOnesValue(BitTy.getSizeInBits()), DL, MaskTy);
 842   SDValue NotMask = DAG.getNode(ISD::XOR, DL, MaskTy, Mask, AllOnes);
 843
 844   Op1 = DAG.getNode(ISD::AND, DL, MaskTy, Op1, Mask);
 845   Op2 = DAG.getNode(ISD::AND, DL, MaskTy, Op2, NotMask);
 846   SDValue Val = DAG.getNode(ISD::OR, DL, MaskTy, Op1, Op2);
 847   return DAG.getNode(ISD::BITCAST, DL, Op.getValueType(), Val);
 848 }
 849
 850 SDValue VectorLegalizer::ExpandSEXTINREG(SDValue Op) {
 851   EVT VT = Op.getValueType();
 852
 853   // Make sure that the SRA and SHL instructions are available.
 854   if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Expand ||
 855       TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Expand)
 856     return DAG.UnrollVectorOp(Op.getNode());
 857
 858   SDLoc DL(Op);
 859   EVT OrigTy = cast<VTSDNode>(Op->getOperand(1))->getVT();
 860
 861   unsigned BW = VT.getScalarSizeInBits();
 862   unsigned OrigBW = OrigTy.getScalarSizeInBits();
 863   SDValue ShiftSz = DAG.getConstant(BW - OrigBW, DL, VT);
 864
 865   Op = Op.getOperand(0);
 866   Op =   DAG.getNode(ISD::SHL, DL, VT, Op, ShiftSz);
 867   return DAG.getNode(ISD::SRA, DL, VT, Op, ShiftSz);
 868 }
 869
 870 // Generically expand a vector anyext in register to a shuffle of the relevant
 871 // lanes into the appropriate locations, with other lanes left undef.
 872 SDValue VectorLegalizer::ExpandANY_EXTEND_VECTOR_INREG(SDValue Op) {
 873   SDLoc DL(Op);
 874   EVT VT = Op.getValueType();
 875   int NumElements = VT.getVectorNumElements();
 876   SDValue Src = Op.getOperand(0);
 877   EVT SrcVT = Src.getValueType();
 878   int NumSrcElements = SrcVT.getVectorNumElements();
 879
 880   // Build a base mask of undef shuffles.
 881   SmallVector<int, 16> ShuffleMask;
 882   ShuffleMask.resize(NumSrcElements, -1);
 883
 884   // Place the extended lanes into the correct locations.
 885   int ExtLaneScale = NumSrcElements / NumElements;
 886   int EndianOffset = DAG.getDataLayout().isBigEndian() ? ExtLaneScale - 1 : 0;
 887   for (int i = 0; i < NumElements; ++i)
 888     ShuffleMask[i * ExtLaneScale + EndianOffset] = i;
 889
 890   return DAG.getNode(
 891       ISD::BITCAST, DL, VT,
 892       DAG.getVectorShuffle(SrcVT, DL, Src, DAG.getUNDEF(SrcVT), ShuffleMask));
 893 }
 894
 895 SDValue VectorLegalizer::ExpandSIGN_EXTEND_VECTOR_INREG(SDValue Op) {
 896   SDLoc DL(Op);
 897   EVT VT = Op.getValueType();
 898   SDValue Src = Op.getOperand(0);
 899   EVT SrcVT = Src.getValueType();
 900
 901   // First build an any-extend node which can be legalized above when we
 902   // recurse through it.
 903   Op = DAG.getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Src);
 904
 905   // Now we need sign extend. Do this by shifting the elements. Even if these
 906   // aren't legal operations, they have a better chance of being legalized
 907   // without full scalarization than the sign extension does.
 908   unsigned EltWidth = VT.getScalarSizeInBits();
 909   unsigned SrcEltWidth = SrcVT.getScalarSizeInBits();
 910   SDValue ShiftAmount = DAG.getConstant(EltWidth - SrcEltWidth, DL, VT);
 911   return DAG.getNode(ISD::SRA, DL, VT,
 912                      DAG.getNode(ISD::SHL, DL, VT, Op, ShiftAmount),
 913                      ShiftAmount);
 914 }
 915
 916 // Generically expand a vector zext in register to a shuffle of the relevant
 917 // lanes into the appropriate locations, a blend of zero into the high bits,
 918 // and a bitcast to the wider element type.
 919 SDValue VectorLegalizer::ExpandZERO_EXTEND_VECTOR_INREG(SDValue Op) {
 920   SDLoc DL(Op);
 921   EVT VT = Op.getValueType();
 922   int NumElements = VT.getVectorNumElements();
 923   SDValue Src = Op.getOperand(0);
 924   EVT SrcVT = Src.getValueType();
 925   int NumSrcElements = SrcVT.getVectorNumElements();
 926
 927   // Build up a zero vector to blend into this one.
 928   SDValue Zero = DAG.getConstant(0, DL, SrcVT);
 929
 930   // Shuffle the incoming lanes into the correct position, and pull all other
 931   // lanes from the zero vector.
 932   SmallVector<int, 16> ShuffleMask;
 933   ShuffleMask.reserve(NumSrcElements);
 934   for (int i = 0; i < NumSrcElements; ++i)
 935     ShuffleMask.push_back(i);
 936
 937   int ExtLaneScale = NumSrcElements / NumElements;
 938   int EndianOffset = DAG.getDataLayout().isBigEndian() ? ExtLaneScale - 1 : 0;
 939   for (int i = 0; i < NumElements; ++i)
 940     ShuffleMask[i * ExtLaneScale + EndianOffset] = NumSrcElements + i;
 941
 942   return DAG.getNode(ISD::BITCAST, DL, VT,
 943                      DAG.getVectorShuffle(SrcVT, DL, Zero, Src, ShuffleMask));
 944 }
 945
 946 static void createBSWAPShuffleMask(EVT VT, SmallVectorImpl<int> &ShuffleMask) {
 947   int ScalarSizeInBytes = VT.getScalarSizeInBits() / 8;
 948   for (int I = 0, E = VT.getVectorNumElements(); I != E; ++I)
 949     for (int J = ScalarSizeInBytes - 1; J >= 0; --J)
 950       ShuffleMask.push_back((I * ScalarSizeInBytes) + J);
 951 }
 952
 953 SDValue VectorLegalizer::ExpandBSWAP(SDValue Op) {
 954   EVT VT = Op.getValueType();
 955
 956   // Generate a byte wise shuffle mask for the BSWAP.
 957   SmallVector<int, 16> ShuffleMask;
 958   createBSWAPShuffleMask(VT, ShuffleMask);
 959   EVT ByteVT = EVT::getVectorVT(*DAG.getContext(), MVT::i8, ShuffleMask.size());
 960
 961   // Only emit a shuffle if the mask is legal.
 962   if (!TLI.isShuffleMaskLegal(ShuffleMask, ByteVT))
 963     return DAG.UnrollVectorOp(Op.getNode());
 964
 965   SDLoc DL(Op);
 966   Op = DAG.getNode(ISD::BITCAST, DL, ByteVT, Op.getOperand(0));
 967   Op = DAG.getVectorShuffle(ByteVT, DL, Op, DAG.getUNDEF(ByteVT), ShuffleMask);
 968   return DAG.getNode(ISD::BITCAST, DL, VT, Op);
 969 }
 970
 971 SDValue VectorLegalizer::ExpandBITREVERSE(SDValue Op) {
 972   EVT VT = Op.getValueType();
 973
 974   // If we have the scalar operation, it's probably cheaper to unroll it.
 975   if (TLI.isOperationLegalOrCustom(ISD::BITREVERSE, VT.getScalarType()))
 976     return DAG.UnrollVectorOp(Op.getNode());
 977
 978   // If the vector element width is a whole number of bytes, test if its legal
 979   // to BSWAP shuffle the bytes and then perform the BITREVERSE on the byte
 980   // vector. This greatly reduces the number of bit shifts necessary.
 981   unsigned ScalarSizeInBits = VT.getScalarSizeInBits();
 982   if (ScalarSizeInBits > 8 && (ScalarSizeInBits % 8) == 0) {
 983     SmallVector<int, 16> BSWAPMask;
 984     createBSWAPShuffleMask(VT, BSWAPMask);
 985
 986     EVT ByteVT = EVT::getVectorVT(*DAG.getContext(), MVT::i8, BSWAPMask.size());
 987     if (TLI.isShuffleMaskLegal(BSWAPMask, ByteVT) &&
 988         (TLI.isOperationLegalOrCustom(ISD::BITREVERSE, ByteVT) ||
 989          (TLI.isOperationLegalOrCustom(ISD::SHL, ByteVT) &&
 990           TLI.isOperationLegalOrCustom(ISD::SRL, ByteVT) &&
 991           TLI.isOperationLegalOrCustomOrPromote(ISD::AND, ByteVT) &&
 992           TLI.isOperationLegalOrCustomOrPromote(ISD::OR, ByteVT)))) {
 993       SDLoc DL(Op);
 994       Op = DAG.getNode(ISD::BITCAST, DL, ByteVT, Op.getOperand(0));
 995       Op = DAG.getVectorShuffle(ByteVT, DL, Op, DAG.getUNDEF(ByteVT),
 996                                 BSWAPMask);
 997       Op = DAG.getNode(ISD::BITREVERSE, DL, ByteVT, Op);
 998       return DAG.getNode(ISD::BITCAST, DL, VT, Op);
 999     }
1000   }
1001
1002   // If we have the appropriate vector bit operations, it is better to use them
1003   // than unrolling and expanding each component.
1004   if (!TLI.isOperationLegalOrCustom(ISD::SHL, VT) ||
1005       !TLI.isOperationLegalOrCustom(ISD::SRL, VT) ||
1006       !TLI.isOperationLegalOrCustomOrPromote(ISD::AND, VT) ||
1007       !TLI.isOperationLegalOrCustomOrPromote(ISD::OR, VT))
1008     return DAG.UnrollVectorOp(Op.getNode());
1009
1010   // Let LegalizeDAG handle this later.
1011   return Op;
1012 }
1013
1014 SDValue VectorLegalizer::ExpandVSELECT(SDValue Op) {
1015   // Implement VSELECT in terms of XOR, AND, OR
1016   // on platforms which do not support blend natively.
1017   SDLoc DL(Op);
1018
1019   SDValue Mask = Op.getOperand(0);
1020   SDValue Op1 = Op.getOperand(1);
1021   SDValue Op2 = Op.getOperand(2);
1022
1023   EVT VT = Mask.getValueType();
1024
1025   // If we can't even use the basic vector operations of
1026   // AND,OR,XOR, we will have to scalarize the op.
1027   // Notice that the operation may be 'promoted' which means that it is
1028   // 'bitcasted' to another type which is handled.
1029   // This operation also isn't safe with AND, OR, XOR when the boolean
1030   // type is 0/1 as we need an all ones vector constant to mask with.
1031   // FIXME: Sign extend 1 to all ones if thats legal on the target.
1032   if (TLI.getOperationAction(ISD::AND, VT) == TargetLowering::Expand ||
1033       TLI.getOperationAction(ISD::XOR, VT) == TargetLowering::Expand ||
1034       TLI.getOperationAction(ISD::OR, VT) == TargetLowering::Expand ||
1035       TLI.getBooleanContents(Op1.getValueType()) !=
1036           TargetLowering::ZeroOrNegativeOneBooleanContent)
1037     return DAG.UnrollVectorOp(Op.getNode());
1038
1039   // If the mask and the type are different sizes, unroll the vector op. This
1040   // can occur when getSetCCResultType returns something that is different in
1041   // size from the operand types. For example, v4i8 = select v4i32, v4i8, v4i8.
1042   if (VT.getSizeInBits() != Op1.getValueSizeInBits())
1043     return DAG.UnrollVectorOp(Op.getNode());
1044
1045   // Bitcast the operands to be the same type as the mask.
1046   // This is needed when we select between FP types because
1047   // the mask is a vector of integers.
1048   Op1 = DAG.getNode(ISD::BITCAST, DL, VT, Op1);
1049   Op2 = DAG.getNode(ISD::BITCAST, DL, VT, Op2);
1050
1051   SDValue AllOnes = DAG.getConstant(
1052     APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL, VT);
1053   SDValue NotMask = DAG.getNode(ISD::XOR, DL, VT, Mask, AllOnes);
1054
1055   Op1 = DAG.getNode(ISD::AND, DL, VT, Op1, Mask);
1056   Op2 = DAG.getNode(ISD::AND, DL, VT, Op2, NotMask);
1057   SDValue Val = DAG.getNode(ISD::OR, DL, VT, Op1, Op2);
1058   return DAG.getNode(ISD::BITCAST, DL, Op.getValueType(), Val);
1059 }
1060
1061 SDValue VectorLegalizer::ExpandFP_TO_UINT(SDValue Op) {
1062   // Attempt to expand using TargetLowering.
1063   SDValue Result;
1064   if (TLI.expandFP_TO_UINT(Op.getNode(), Result, DAG))
1065     return Result;
1066
1067   // Otherwise go ahead and unroll.
1068   return DAG.UnrollVectorOp(Op.getNode());
1069 }
1070
1071 SDValue VectorLegalizer::ExpandUINT_TO_FLOAT(SDValue Op) {
1072   EVT VT = Op.getOperand(0).getValueType();
1073   SDLoc DL(Op);
1074
1075   // Attempt to expand using TargetLowering.
1076   SDValue Result;
1077   if (TLI.expandUINT_TO_FP(Op.getNode(), Result, DAG))
1078     return Result;
1079
1080   // Make sure that the SINT_TO_FP and SRL instructions are available.
1081   if (TLI.getOperationAction(ISD::SINT_TO_FP, VT) == TargetLowering::Expand ||
1082       TLI.getOperationAction(ISD::SRL,        VT) == TargetLowering::Expand)
1083     return DAG.UnrollVectorOp(Op.getNode());
1084
1085   unsigned BW = VT.getScalarSizeInBits();
1086   assert((BW == 64 || BW == 32) &&
1087          "Elements in vector-UINT_TO_FP must be 32 or 64 bits wide");
1088
1089   SDValue HalfWord = DAG.getConstant(BW / 2, DL, VT);
1090
1091   // Constants to clear the upper part of the word.
1092   // Notice that we can also use SHL+SHR, but using a constant is slightly
1093   // faster on x86.
1094   uint64_t HWMask = (BW == 64) ? 0x00000000FFFFFFFF : 0x0000FFFF;
1095   SDValue HalfWordMask = DAG.getConstant(HWMask, DL, VT);
1096
1097   // Two to the power of half-word-size.
1098   SDValue TWOHW = DAG.getConstantFP(1ULL << (BW / 2), DL, Op.getValueType());
1099
1100   // Clear upper part of LO, lower HI
1101   SDValue HI = DAG.getNode(ISD::SRL, DL, VT, Op.getOperand(0), HalfWord);
1102   SDValue LO = DAG.getNode(ISD::AND, DL, VT, Op.getOperand(0), HalfWordMask);
1103
1104   // Convert hi and lo to floats
1105   // Convert the hi part back to the upper values
1106   // TODO: Can any fast-math-flags be set on these nodes?
1107   SDValue fHI = DAG.getNode(ISD::SINT_TO_FP, DL, Op.getValueType(), HI);
1108           fHI = DAG.getNode(ISD::FMUL, DL, Op.getValueType(), fHI, TWOHW);
1109   SDValue fLO = DAG.getNode(ISD::SINT_TO_FP, DL, Op.getValueType(), LO);
1110
1111   // Add the two halves
1112   return DAG.getNode(ISD::FADD, DL, Op.getValueType(), fHI, fLO);
1113 }
1114
1115 SDValue VectorLegalizer::ExpandFNEG(SDValue Op) {
1116   if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) {
1117     SDLoc DL(Op);
1118     SDValue Zero = DAG.getConstantFP(-0.0, DL, Op.getValueType());
1119     // TODO: If FNEG had fast-math-flags, they'd get propagated to this FSUB.
1120     return DAG.getNode(ISD::FSUB, DL, Op.getValueType(),
1121                        Zero, Op.getOperand(0));
1122   }
1123   return DAG.UnrollVectorOp(Op.getNode());
1124 }
1125
1126 SDValue VectorLegalizer::ExpandFSUB(SDValue Op) {
1127   // For floating-point values, (a-b) is the same as a+(-b). If FNEG is legal,
1128   // we can defer this to operation legalization where it will be lowered as
1129   // a+(-b).
1130   EVT VT = Op.getValueType();
1131   if (TLI.isOperationLegalOrCustom(ISD::FNEG, VT) &&
1132       TLI.isOperationLegalOrCustom(ISD::FADD, VT))
1133     return Op; // Defer to LegalizeDAG
1134
1135   return DAG.UnrollVectorOp(Op.getNode());
1136 }
1137
1138 SDValue VectorLegalizer::ExpandCTPOP(SDValue Op) {
1139   SDValue Result;
1140   if (TLI.expandCTPOP(Op.getNode(), Result, DAG))
1141     return Result;
1142
1143   return DAG.UnrollVectorOp(Op.getNode());
1144 }
1145
1146 SDValue VectorLegalizer::ExpandCTLZ(SDValue Op) {
1147   SDValue Result;
1148   if (TLI.expandCTLZ(Op.getNode(), Result, DAG))
1149     return Result;
1150
1151   return DAG.UnrollVectorOp(Op.getNode());
1152 }
1153
1154 SDValue VectorLegalizer::ExpandCTTZ(SDValue Op) {
1155   SDValue Result;
1156   if (TLI.expandCTTZ(Op.getNode(), Result, DAG))
1157     return Result;
1158
1159   return DAG.UnrollVectorOp(Op.getNode());
1160 }
1161
1162 SDValue VectorLegalizer::ExpandFunnelShift(SDValue Op) {
1163   SDValue Result;
1164   if (TLI.expandFunnelShift(Op.getNode(), Result, DAG))
1165     return Result;
1166
1167   return DAG.UnrollVectorOp(Op.getNode());
1168 }
1169
1170 SDValue VectorLegalizer::ExpandFMINNUM_FMAXNUM(SDValue Op) {
1171   if (SDValue Expanded = TLI.expandFMINNUM_FMAXNUM(Op.getNode(), DAG))
1172     return Expanded;
1173   return DAG.UnrollVectorOp(Op.getNode());
1174 }
1175
1176 SDValue VectorLegalizer::ExpandStrictFPOp(SDValue Op) {
1177   EVT VT = Op.getValueType();
1178   EVT EltVT = VT.getVectorElementType();
1179   unsigned NumElems = VT.getVectorNumElements();
1180   unsigned NumOpers = Op.getNumOperands();
1181   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1182   EVT ValueVTs[] = {EltVT, MVT::Other};
1183   SDValue Chain = Op.getOperand(0);
1184   SDLoc dl(Op);
1185
1186   SmallVector<SDValue, 32> OpValues;
1187   SmallVector<SDValue, 32> OpChains;
1188   for (unsigned i = 0; i < NumElems; ++i) {
1189     SmallVector<SDValue, 4> Opers;
1190     SDValue Idx = DAG.getConstant(i, dl,
1191                                   TLI.getVectorIdxTy(DAG.getDataLayout()));
1192
1193     // The Chain is the first operand.
1194     Opers.push_back(Chain);
1195
1196     // Now process the remaining operands.
1197     for (unsigned j = 1; j < NumOpers; ++j) {
1198       SDValue Oper = Op.getOperand(j);
1199       EVT OperVT = Oper.getValueType();
1200
1201       if (OperVT.isVector())
1202         Oper = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
1203                            EltVT, Oper, Idx);
1204
1205       Opers.push_back(Oper);
1206     }
1207
1208     SDValue ScalarOp = DAG.getNode(Op->getOpcode(), dl, ValueVTs, Opers);
1209
1210     OpValues.push_back(ScalarOp.getValue(0));
1211     OpChains.push_back(ScalarOp.getValue(1));
1212   }
1213
1214   SDValue Result = DAG.getBuildVector(VT, dl, OpValues);
1215   SDValue NewChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OpChains);
1216
1217   AddLegalizedOperand(Op.getValue(0), Result);
1218   AddLegalizedOperand(Op.getValue(1), NewChain);
1219
1220   return Op.getResNo() ? NewChain : Result;
1221 }
1222
1223 SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) {
1224   EVT VT = Op.getValueType();
1225   unsigned NumElems = VT.getVectorNumElements();
1226   EVT EltVT = VT.getVectorElementType();
1227   SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2);
1228   EVT TmpEltVT = LHS.getValueType().getVectorElementType();
1229   SDLoc dl(Op);
1230   SmallVector<SDValue, 8> Ops(NumElems);
1231   for (unsigned i = 0; i < NumElems; ++i) {
1232     SDValue LHSElem = DAG.getNode(
1233         ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS,
1234         DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
1235     SDValue RHSElem = DAG.getNode(
1236         ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS,
1237         DAG.getConstant(i, dl, TLI.getVectorIdxTy(DAG.getDataLayout())));
1238     Ops[i] = DAG.getNode(ISD::SETCC, dl,
1239                          TLI.getSetCCResultType(DAG.getDataLayout(),
1240                                                 *DAG.getContext(), TmpEltVT),
1241                          LHSElem, RHSElem, CC);
1242     Ops[i] = DAG.getSelect(dl, EltVT, Ops[i],
1243                            DAG.getConstant(APInt::getAllOnesValue
1244                                            (EltVT.getSizeInBits()), dl, EltVT),
1245                            DAG.getConstant(0, dl, EltVT));
1246   }
1247   return DAG.getBuildVector(VT, dl, Ops);
1248 }
1249
1250 bool SelectionDAG::LegalizeVectors() {
1251   return VectorLegalizer(*this).Run();
1252 }