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/CodeGen/SelectionDAG.h"
  31 #include "llvm/Target/TargetLowering.h"
  32 using namespace llvm;
  33
  34 namespace {
  35 class VectorLegalizer {
  36   SelectionDAG& DAG;
  37   const TargetLowering &TLI;
  38   bool Changed; // Keep track of whether anything changed
  39
  40   /// LegalizedNodes - For nodes that are of legal width, and that have more
  41   /// than one use, this map indicates what regularized operand to use.  This
  42   /// allows us to avoid legalizing the same thing more than once.
  43   SmallDenseMap<SDValue, SDValue, 64> LegalizedNodes;
  44
  45   // Adds a node to the translation cache
  46   void AddLegalizedOperand(SDValue From, SDValue To) {
  47     LegalizedNodes.insert(std::make_pair(From, To));
  48     // If someone requests legalization of the new node, return itself.
  49     if (From != To)
  50       LegalizedNodes.insert(std::make_pair(To, To));
  51   }
  52
  53   // Legalizes the given node
  54   SDValue LegalizeOp(SDValue Op);
  55   // Assuming the node is legal, "legalize" the results
  56   SDValue TranslateLegalizeResults(SDValue Op, SDValue Result);
  57   // Implements unrolling a VSETCC.
  58   SDValue UnrollVSETCC(SDValue Op);
  59   // Implements expansion for FNEG; falls back to UnrollVectorOp if FSUB
  60   // isn't legal.
  61   // Implements expansion for UINT_TO_FLOAT; falls back to UnrollVectorOp if
  62   // SINT_TO_FLOAT and SHR on vectors isn't legal.
  63   SDValue ExpandUINT_TO_FLOAT(SDValue Op);
  64   // Implement expansion for SIGN_EXTEND_INREG using SRL and SRA.
  65   SDValue ExpandSEXTINREG(SDValue Op);
  66   // Expand bswap of vectors into a shuffle if legal.
  67   SDValue ExpandBSWAP(SDValue Op);
  68   // Implement vselect in terms of XOR, AND, OR when blend is not supported
  69   // by the target.
  70   SDValue ExpandVSELECT(SDValue Op);
  71   SDValue ExpandSELECT(SDValue Op);
  72   SDValue ExpandLoad(SDValue Op);
  73   SDValue ExpandStore(SDValue Op);
  74   SDValue ExpandFNEG(SDValue Op);
  75   // Implements vector promotion; this is essentially just bitcasting the
  76   // operands to a different type and bitcasting the result back to the
  77   // original type.
  78   SDValue PromoteVectorOp(SDValue Op);
  79   // Implements [SU]INT_TO_FP vector promotion; this is a [zs]ext of the input
  80   // operand to the next size up.
  81   SDValue PromoteVectorOpINT_TO_FP(SDValue Op);
  82   // Implements FP_TO_[SU]INT vector promotion of the result type; it is
  83   // promoted to the next size up integer type.  The result is then truncated
  84   // back to the original type.
  85   SDValue PromoteVectorOpFP_TO_INT(SDValue Op, bool isSigned);
  86
  87   public:
  88   bool Run();
  89   VectorLegalizer(SelectionDAG& dag) :
  90       DAG(dag), TLI(dag.getTargetLoweringInfo()), Changed(false) {}
  91 };
  92
  93 bool VectorLegalizer::Run() {
  94   // Before we start legalizing vector nodes, check if there are any vectors.
  95   bool HasVectors = false;
  96   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
  97        E = std::prev(DAG.allnodes_end()); I != std::next(E); ++I) {
  98     // Check if the values of the nodes contain vectors. We don't need to check
  99     // the operands because we are going to check their values at some point.
 100     for (SDNode::value_iterator J = I->value_begin(), E = I->value_end();
 101          J != E; ++J)
 102       HasVectors |= J->isVector();
 103
 104     // If we found a vector node we can start the legalization.
 105     if (HasVectors)
 106       break;
 107   }
 108
 109   // If this basic block has no vectors then no need to legalize vectors.
 110   if (!HasVectors)
 111     return false;
 112
 113   // The legalize process is inherently a bottom-up recursive process (users
 114   // legalize their uses before themselves).  Given infinite stack space, we
 115   // could just start legalizing on the root and traverse the whole graph.  In
 116   // practice however, this causes us to run out of stack space on large basic
 117   // blocks.  To avoid this problem, compute an ordering of the nodes where each
 118   // node is only legalized after all of its operands are legalized.
 119   DAG.AssignTopologicalOrder();
 120   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 121        E = std::prev(DAG.allnodes_end()); I != std::next(E); ++I)
 122     LegalizeOp(SDValue(I, 0));
 123
 124   // Finally, it's possible the root changed.  Get the new root.
 125   SDValue OldRoot = DAG.getRoot();
 126   assert(LegalizedNodes.count(OldRoot) && "Root didn't get legalized?");
 127   DAG.setRoot(LegalizedNodes[OldRoot]);
 128
 129   LegalizedNodes.clear();
 130
 131   // Remove dead nodes now.
 132   DAG.RemoveDeadNodes();
 133
 134   return Changed;
 135 }
 136
 137 SDValue VectorLegalizer::TranslateLegalizeResults(SDValue Op, SDValue Result) {
 138   // Generic legalization: just pass the operand through.
 139   for (unsigned i = 0, e = Op.getNode()->getNumValues(); i != e; ++i)
 140     AddLegalizedOperand(Op.getValue(i), Result.getValue(i));
 141   return Result.getValue(Op.getResNo());
 142 }
 143
 144 SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
 145   // Note that LegalizeOp may be reentered even from single-use nodes, which
 146   // means that we always must cache transformed nodes.
 147   DenseMap<SDValue, SDValue>::iterator I = LegalizedNodes.find(Op);
 148   if (I != LegalizedNodes.end()) return I->second;
 149
 150   SDNode* Node = Op.getNode();
 151
 152   // Legalize the operands
 153   SmallVector<SDValue, 8> Ops;
 154   for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
 155     Ops.push_back(LegalizeOp(Node->getOperand(i)));
 156
 157   SDValue Result = SDValue(DAG.UpdateNodeOperands(Op.getNode(), Ops), 0);
 158
 159   if (Op.getOpcode() == ISD::LOAD) {
 160     LoadSDNode *LD = cast<LoadSDNode>(Op.getNode());
 161     ISD::LoadExtType ExtType = LD->getExtensionType();
 162     if (LD->getMemoryVT().isVector() && ExtType != ISD::NON_EXTLOAD) {
 163       if (TLI.isLoadExtLegal(LD->getExtensionType(), LD->getMemoryVT()))
 164         return TranslateLegalizeResults(Op, Result);
 165       Changed = true;
 166       return LegalizeOp(ExpandLoad(Op));
 167     }
 168   } else if (Op.getOpcode() == ISD::STORE) {
 169     StoreSDNode *ST = cast<StoreSDNode>(Op.getNode());
 170     EVT StVT = ST->getMemoryVT();
 171     MVT ValVT = ST->getValue().getSimpleValueType();
 172     if (StVT.isVector() && ST->isTruncatingStore())
 173       switch (TLI.getTruncStoreAction(ValVT, StVT.getSimpleVT())) {
 174       default: llvm_unreachable("This action is not supported yet!");
 175       case TargetLowering::Legal:
 176         return TranslateLegalizeResults(Op, Result);
 177       case TargetLowering::Custom:
 178         Changed = true;
 179         return TranslateLegalizeResults(Op, TLI.LowerOperation(Result, DAG));
 180       case TargetLowering::Expand:
 181         Changed = true;
 182         return LegalizeOp(ExpandStore(Op));
 183       }
 184   }
 185
 186   bool HasVectorValue = false;
 187   for (SDNode::value_iterator J = Node->value_begin(), E = Node->value_end();
 188        J != E;
 189        ++J)
 190     HasVectorValue |= J->isVector();
 191   if (!HasVectorValue)
 192     return TranslateLegalizeResults(Op, Result);
 193
 194   EVT QueryType;
 195   switch (Op.getOpcode()) {
 196   default:
 197     return TranslateLegalizeResults(Op, Result);
 198   case ISD::ADD:
 199   case ISD::SUB:
 200   case ISD::MUL:
 201   case ISD::SDIV:
 202   case ISD::UDIV:
 203   case ISD::SREM:
 204   case ISD::UREM:
 205   case ISD::FADD:
 206   case ISD::FSUB:
 207   case ISD::FMUL:
 208   case ISD::FDIV:
 209   case ISD::FREM:
 210   case ISD::AND:
 211   case ISD::OR:
 212   case ISD::XOR:
 213   case ISD::SHL:
 214   case ISD::SRA:
 215   case ISD::SRL:
 216   case ISD::ROTL:
 217   case ISD::ROTR:
 218   case ISD::BSWAP:
 219   case ISD::CTLZ:
 220   case ISD::CTTZ:
 221   case ISD::CTLZ_ZERO_UNDEF:
 222   case ISD::CTTZ_ZERO_UNDEF:
 223   case ISD::CTPOP:
 224   case ISD::SELECT:
 225   case ISD::VSELECT:
 226   case ISD::SELECT_CC:
 227   case ISD::SETCC:
 228   case ISD::ZERO_EXTEND:
 229   case ISD::ANY_EXTEND:
 230   case ISD::TRUNCATE:
 231   case ISD::SIGN_EXTEND:
 232   case ISD::FP_TO_SINT:
 233   case ISD::FP_TO_UINT:
 234   case ISD::FNEG:
 235   case ISD::FABS:
 236   case ISD::FCOPYSIGN:
 237   case ISD::FSQRT:
 238   case ISD::FSIN:
 239   case ISD::FCOS:
 240   case ISD::FPOWI:
 241   case ISD::FPOW:
 242   case ISD::FLOG:
 243   case ISD::FLOG2:
 244   case ISD::FLOG10:
 245   case ISD::FEXP:
 246   case ISD::FEXP2:
 247   case ISD::FCEIL:
 248   case ISD::FTRUNC:
 249   case ISD::FRINT:
 250   case ISD::FNEARBYINT:
 251   case ISD::FROUND:
 252   case ISD::FFLOOR:
 253   case ISD::FP_ROUND:
 254   case ISD::FP_EXTEND:
 255   case ISD::FMA:
 256   case ISD::SIGN_EXTEND_INREG:
 257     QueryType = Node->getValueType(0);
 258     break;
 259   case ISD::FP_ROUND_INREG:
 260     QueryType = cast<VTSDNode>(Node->getOperand(1))->getVT();
 261     break;
 262   case ISD::SINT_TO_FP:
 263   case ISD::UINT_TO_FP:
 264     QueryType = Node->getOperand(0).getValueType();
 265     break;
 266   }
 267
 268   switch (TLI.getOperationAction(Node->getOpcode(), QueryType)) {
 269   case TargetLowering::Promote:
 270     switch (Op.getOpcode()) {
 271     default:
 272       // "Promote" the operation by bitcasting
 273       Result = PromoteVectorOp(Op);
 274       Changed = true;
 275       break;
 276     case ISD::SINT_TO_FP:
 277     case ISD::UINT_TO_FP:
 278       // "Promote" the operation by extending the operand.
 279       Result = PromoteVectorOpINT_TO_FP(Op);
 280       Changed = true;
 281       break;
 282     case ISD::FP_TO_UINT:
 283     case ISD::FP_TO_SINT:
 284       // Promote the operation by extending the operand.
 285       Result = PromoteVectorOpFP_TO_INT(Op, Op->getOpcode() == ISD::FP_TO_SINT);
 286       Changed = true;
 287       break;
 288     }
 289     break;
 290   case TargetLowering::Legal: break;
 291   case TargetLowering::Custom: {
 292     SDValue Tmp1 = TLI.LowerOperation(Op, DAG);
 293     if (Tmp1.getNode()) {
 294       Result = Tmp1;
 295       break;
 296     }
 297     // FALL THROUGH
 298   }
 299   case TargetLowering::Expand:
 300     if (Node->getOpcode() == ISD::SIGN_EXTEND_INREG)
 301       Result = ExpandSEXTINREG(Op);
 302     else if (Node->getOpcode() == ISD::BSWAP)
 303       Result = ExpandBSWAP(Op);
 304     else if (Node->getOpcode() == ISD::VSELECT)
 305       Result = ExpandVSELECT(Op);
 306     else if (Node->getOpcode() == ISD::SELECT)
 307       Result = ExpandSELECT(Op);
 308     else if (Node->getOpcode() == ISD::UINT_TO_FP)
 309       Result = ExpandUINT_TO_FLOAT(Op);
 310     else if (Node->getOpcode() == ISD::FNEG)
 311       Result = ExpandFNEG(Op);
 312     else if (Node->getOpcode() == ISD::SETCC)
 313       Result = UnrollVSETCC(Op);
 314     else
 315       Result = DAG.UnrollVectorOp(Op.getNode());
 316     break;
 317   }
 318
 319   // Make sure that the generated code is itself legal.
 320   if (Result != Op) {
 321     Result = LegalizeOp(Result);
 322     Changed = true;
 323   }
 324
 325   // Note that LegalizeOp may be reentered even from single-use nodes, which
 326   // means that we always must cache transformed nodes.
 327   AddLegalizedOperand(Op, Result);
 328   return Result;
 329 }
 330
 331 SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
 332   // Vector "promotion" is basically just bitcasting and doing the operation
 333   // in a different type.  For example, x86 promotes ISD::AND on v2i32 to
 334   // v1i64.
 335   MVT VT = Op.getSimpleValueType();
 336   assert(Op.getNode()->getNumValues() == 1 &&
 337          "Can't promote a vector with multiple results!");
 338   MVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
 339   SDLoc dl(Op);
 340   SmallVector<SDValue, 4> Operands(Op.getNumOperands());
 341
 342   for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
 343     if (Op.getOperand(j).getValueType().isVector())
 344       Operands[j] = DAG.getNode(ISD::BITCAST, dl, NVT, Op.getOperand(j));
 345     else
 346       Operands[j] = Op.getOperand(j);
 347   }
 348
 349   Op = DAG.getNode(Op.getOpcode(), dl, NVT, Operands);
 350
 351   return DAG.getNode(ISD::BITCAST, dl, VT, Op);
 352 }
 353
 354 SDValue VectorLegalizer::PromoteVectorOpINT_TO_FP(SDValue Op) {
 355   // INT_TO_FP operations may require the input operand be promoted even
 356   // when the type is otherwise legal.
 357   EVT VT = Op.getOperand(0).getValueType();
 358   assert(Op.getNode()->getNumValues() == 1 &&
 359          "Can't promote a vector with multiple results!");
 360
 361   // Normal getTypeToPromoteTo() doesn't work here, as that will promote
 362   // by widening the vector w/ the same element width and twice the number
 363   // of elements. We want the other way around, the same number of elements,
 364   // each twice the width.
 365   //
 366   // Increase the bitwidth of the element to the next pow-of-two
 367   // (which is greater than 8 bits).
 368
 369   EVT NVT = VT.widenIntegerVectorElementType(*DAG.getContext());
 370   assert(NVT.isSimple() && "Promoting to a non-simple vector type!");
 371   SDLoc dl(Op);
 372   SmallVector<SDValue, 4> Operands(Op.getNumOperands());
 373
 374   unsigned Opc = Op.getOpcode() == ISD::UINT_TO_FP ? ISD::ZERO_EXTEND :
 375     ISD::SIGN_EXTEND;
 376   for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
 377     if (Op.getOperand(j).getValueType().isVector())
 378       Operands[j] = DAG.getNode(Opc, dl, NVT, Op.getOperand(j));
 379     else
 380       Operands[j] = Op.getOperand(j);
 381   }
 382
 383   return DAG.getNode(Op.getOpcode(), dl, Op.getValueType(), Operands);
 384 }
 385
 386 // For FP_TO_INT we promote the result type to a vector type with wider
 387 // elements and then truncate the result.  This is different from the default
 388 // PromoteVector which uses bitcast to promote thus assumning that the
 389 // promoted vector type has the same overall size.
 390 SDValue VectorLegalizer::PromoteVectorOpFP_TO_INT(SDValue Op, bool isSigned) {
 391   assert(Op.getNode()->getNumValues() == 1 &&
 392          "Can't promote a vector with multiple results!");
 393   EVT VT = Op.getValueType();
 394
 395   EVT NewVT;
 396   unsigned NewOpc;
 397   while (1) {
 398     NewVT = VT.widenIntegerVectorElementType(*DAG.getContext());
 399     assert(NewVT.isSimple() && "Promoting to a non-simple vector type!");
 400     if (TLI.isOperationLegalOrCustom(ISD::FP_TO_SINT, NewVT)) {
 401       NewOpc = ISD::FP_TO_SINT;
 402       break;
 403     }
 404     if (!isSigned && TLI.isOperationLegalOrCustom(ISD::FP_TO_UINT, NewVT)) {
 405       NewOpc = ISD::FP_TO_UINT;
 406       break;
 407     }
 408   }
 409
 410   SDLoc loc(Op);
 411   SDValue promoted  = DAG.getNode(NewOpc, SDLoc(Op), NewVT, Op.getOperand(0));
 412   return DAG.getNode(ISD::TRUNCATE, SDLoc(Op), VT, promoted);
 413 }
 414
 415
 416 SDValue VectorLegalizer::ExpandLoad(SDValue Op) {
 417   SDLoc dl(Op);
 418   LoadSDNode *LD = cast<LoadSDNode>(Op.getNode());
 419   SDValue Chain = LD->getChain();
 420   SDValue BasePTR = LD->getBasePtr();
 421   EVT SrcVT = LD->getMemoryVT();
 422   ISD::LoadExtType ExtType = LD->getExtensionType();
 423
 424   SmallVector<SDValue, 8> Vals;
 425   SmallVector<SDValue, 8> LoadChains;
 426   unsigned NumElem = SrcVT.getVectorNumElements();
 427
 428   EVT SrcEltVT = SrcVT.getScalarType();
 429   EVT DstEltVT = Op.getNode()->getValueType(0).getScalarType();
 430
 431   if (SrcVT.getVectorNumElements() > 1 && !SrcEltVT.isByteSized()) {
 432     // When elements in a vector is not byte-addressable, we cannot directly
 433     // load each element by advancing pointer, which could only address bytes.
 434     // Instead, we load all significant words, mask bits off, and concatenate
 435     // them to form each element. Finally, they are extended to destination
 436     // scalar type to build the destination vector.
 437     EVT WideVT = TLI.getPointerTy();
 438
 439     assert(WideVT.isRound() &&
 440            "Could not handle the sophisticated case when the widest integer is"
 441            " not power of 2.");
 442     assert(WideVT.bitsGE(SrcEltVT) &&
 443            "Type is not legalized?");
 444
 445     unsigned WideBytes = WideVT.getStoreSize();
 446     unsigned Offset = 0;
 447     unsigned RemainingBytes = SrcVT.getStoreSize();
 448     SmallVector<SDValue, 8> LoadVals;
 449
 450     while (RemainingBytes > 0) {
 451       SDValue ScalarLoad;
 452       unsigned LoadBytes = WideBytes;
 453
 454       if (RemainingBytes >= LoadBytes) {
 455         ScalarLoad = DAG.getLoad(WideVT, dl, Chain, BasePTR,
 456                                  LD->getPointerInfo().getWithOffset(Offset),
 457                                  LD->isVolatile(), LD->isNonTemporal(),
 458                                  LD->isInvariant(), LD->getAlignment(),
 459                                  LD->getTBAAInfo());
 460       } else {
 461         EVT LoadVT = WideVT;
 462         while (RemainingBytes < LoadBytes) {
 463           LoadBytes >>= 1; // Reduce the load size by half.
 464           LoadVT = EVT::getIntegerVT(*DAG.getContext(), LoadBytes << 3);
 465         }
 466         ScalarLoad = DAG.getExtLoad(ISD::EXTLOAD, dl, WideVT, Chain, BasePTR,
 467                                     LD->getPointerInfo().getWithOffset(Offset),
 468                                     LoadVT, LD->isVolatile(),
 469                                     LD->isNonTemporal(), LD->getAlignment(),
 470                                     LD->getTBAAInfo());
 471       }
 472
 473       RemainingBytes -= LoadBytes;
 474       Offset += LoadBytes;
 475       BasePTR = DAG.getNode(ISD::ADD, dl, BasePTR.getValueType(), BasePTR,
 476                             DAG.getConstant(LoadBytes, BasePTR.getValueType()));
 477
 478       LoadVals.push_back(ScalarLoad.getValue(0));
 479       LoadChains.push_back(ScalarLoad.getValue(1));
 480     }
 481
 482     // Extract bits, pack and extend/trunc them into destination type.
 483     unsigned SrcEltBits = SrcEltVT.getSizeInBits();
 484     SDValue SrcEltBitMask = DAG.getConstant((1U << SrcEltBits) - 1, WideVT);
 485
 486     unsigned BitOffset = 0;
 487     unsigned WideIdx = 0;
 488     unsigned WideBits = WideVT.getSizeInBits();
 489
 490     for (unsigned Idx = 0; Idx != NumElem; ++Idx) {
 491       SDValue Lo, Hi, ShAmt;
 492
 493       if (BitOffset < WideBits) {
 494         ShAmt = DAG.getConstant(BitOffset, TLI.getShiftAmountTy(WideVT));
 495         Lo = DAG.getNode(ISD::SRL, dl, WideVT, LoadVals[WideIdx], ShAmt);
 496         Lo = DAG.getNode(ISD::AND, dl, WideVT, Lo, SrcEltBitMask);
 497       }
 498
 499       BitOffset += SrcEltBits;
 500       if (BitOffset >= WideBits) {
 501         WideIdx++;
 502         Offset -= WideBits;
 503         if (Offset > 0) {
 504           ShAmt = DAG.getConstant(SrcEltBits - Offset,
 505                                   TLI.getShiftAmountTy(WideVT));
 506           Hi = DAG.getNode(ISD::SHL, dl, WideVT, LoadVals[WideIdx], ShAmt);
 507           Hi = DAG.getNode(ISD::AND, dl, WideVT, Hi, SrcEltBitMask);
 508         }
 509       }
 510
 511       if (Hi.getNode())
 512         Lo = DAG.getNode(ISD::OR, dl, WideVT, Lo, Hi);
 513
 514       switch (ExtType) {
 515       default: llvm_unreachable("Unknown extended-load op!");
 516       case ISD::EXTLOAD:
 517         Lo = DAG.getAnyExtOrTrunc(Lo, dl, DstEltVT);
 518         break;
 519       case ISD::ZEXTLOAD:
 520         Lo = DAG.getZExtOrTrunc(Lo, dl, DstEltVT);
 521         break;
 522       case ISD::SEXTLOAD:
 523         ShAmt = DAG.getConstant(WideBits - SrcEltBits,
 524                                 TLI.getShiftAmountTy(WideVT));
 525         Lo = DAG.getNode(ISD::SHL, dl, WideVT, Lo, ShAmt);
 526         Lo = DAG.getNode(ISD::SRA, dl, WideVT, Lo, ShAmt);
 527         Lo = DAG.getSExtOrTrunc(Lo, dl, DstEltVT);
 528         break;
 529       }
 530       Vals.push_back(Lo);
 531     }
 532   } else {
 533     unsigned Stride = SrcVT.getScalarType().getSizeInBits()/8;
 534
 535     for (unsigned Idx=0; Idx<NumElem; Idx++) {
 536       SDValue ScalarLoad = DAG.getExtLoad(ExtType, dl,
 537                 Op.getNode()->getValueType(0).getScalarType(),
 538                 Chain, BasePTR, LD->getPointerInfo().getWithOffset(Idx * Stride),
 539                 SrcVT.getScalarType(),
 540                 LD->isVolatile(), LD->isNonTemporal(),
 541                 LD->getAlignment(), LD->getTBAAInfo());
 542
 543       BasePTR = DAG.getNode(ISD::ADD, dl, BasePTR.getValueType(), BasePTR,
 544                          DAG.getConstant(Stride, BasePTR.getValueType()));
 545
 546       Vals.push_back(ScalarLoad.getValue(0));
 547       LoadChains.push_back(ScalarLoad.getValue(1));
 548     }
 549   }
 550
 551   SDValue NewChain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
 552   SDValue Value = DAG.getNode(ISD::BUILD_VECTOR, dl,
 553                               Op.getNode()->getValueType(0), Vals);
 554
 555   AddLegalizedOperand(Op.getValue(0), Value);
 556   AddLegalizedOperand(Op.getValue(1), NewChain);
 557
 558   return (Op.getResNo() ? NewChain : Value);
 559 }
 560
 561 SDValue VectorLegalizer::ExpandStore(SDValue Op) {
 562   SDLoc dl(Op);
 563   StoreSDNode *ST = cast<StoreSDNode>(Op.getNode());
 564   SDValue Chain = ST->getChain();
 565   SDValue BasePTR = ST->getBasePtr();
 566   SDValue Value = ST->getValue();
 567   EVT StVT = ST->getMemoryVT();
 568
 569   unsigned Alignment = ST->getAlignment();
 570   bool isVolatile = ST->isVolatile();
 571   bool isNonTemporal = ST->isNonTemporal();
 572   const MDNode *TBAAInfo = ST->getTBAAInfo();
 573
 574   unsigned NumElem = StVT.getVectorNumElements();
 575   // The type of the data we want to save
 576   EVT RegVT = Value.getValueType();
 577   EVT RegSclVT = RegVT.getScalarType();
 578   // The type of data as saved in memory.
 579   EVT MemSclVT = StVT.getScalarType();
 580
 581   // Cast floats into integers
 582   unsigned ScalarSize = MemSclVT.getSizeInBits();
 583
 584   // Round odd types to the next pow of two.
 585   if (!isPowerOf2_32(ScalarSize))
 586     ScalarSize = NextPowerOf2(ScalarSize);
 587
 588   // Store Stride in bytes
 589   unsigned Stride = ScalarSize/8;
 590   // Extract each of the elements from the original vector
 591   // and save them into memory individually.
 592   SmallVector<SDValue, 8> Stores;
 593   for (unsigned Idx = 0; Idx < NumElem; Idx++) {
 594     SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
 595                RegSclVT, Value, DAG.getConstant(Idx, TLI.getVectorIdxTy()));
 596
 597     // This scalar TruncStore may be illegal, but we legalize it later.
 598     SDValue Store = DAG.getTruncStore(Chain, dl, Ex, BasePTR,
 599                ST->getPointerInfo().getWithOffset(Idx*Stride), MemSclVT,
 600                isVolatile, isNonTemporal, Alignment, TBAAInfo);
 601
 602     BasePTR = DAG.getNode(ISD::ADD, dl, BasePTR.getValueType(), BasePTR,
 603                                DAG.getConstant(Stride, BasePTR.getValueType()));
 604
 605     Stores.push_back(Store);
 606   }
 607   SDValue TF =  DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
 608   AddLegalizedOperand(Op, TF);
 609   return TF;
 610 }
 611
 612 SDValue VectorLegalizer::ExpandSELECT(SDValue Op) {
 613   // Lower a select instruction where the condition is a scalar and the
 614   // operands are vectors. Lower this select to VSELECT and implement it
 615   // using XOR AND OR. The selector bit is broadcasted.
 616   EVT VT = Op.getValueType();
 617   SDLoc DL(Op);
 618
 619   SDValue Mask = Op.getOperand(0);
 620   SDValue Op1 = Op.getOperand(1);
 621   SDValue Op2 = Op.getOperand(2);
 622
 623   assert(VT.isVector() && !Mask.getValueType().isVector()
 624          && Op1.getValueType() == Op2.getValueType() && "Invalid type");
 625
 626   unsigned NumElem = VT.getVectorNumElements();
 627
 628   // If we can't even use the basic vector operations of
 629   // AND,OR,XOR, we will have to scalarize the op.
 630   // Notice that the operation may be 'promoted' which means that it is
 631   // 'bitcasted' to another type which is handled.
 632   // Also, we need to be able to construct a splat vector using BUILD_VECTOR.
 633   if (TLI.getOperationAction(ISD::AND, VT) == TargetLowering::Expand ||
 634       TLI.getOperationAction(ISD::XOR, VT) == TargetLowering::Expand ||
 635       TLI.getOperationAction(ISD::OR,  VT) == TargetLowering::Expand ||
 636       TLI.getOperationAction(ISD::BUILD_VECTOR,  VT) == TargetLowering::Expand)
 637     return DAG.UnrollVectorOp(Op.getNode());
 638
 639   // Generate a mask operand.
 640   EVT MaskTy = VT.changeVectorElementTypeToInteger();
 641
 642   // What is the size of each element in the vector mask.
 643   EVT BitTy = MaskTy.getScalarType();
 644
 645   Mask = DAG.getSelect(DL, BitTy, Mask,
 646           DAG.getConstant(APInt::getAllOnesValue(BitTy.getSizeInBits()), BitTy),
 647           DAG.getConstant(0, BitTy));
 648
 649   // Broadcast the mask so that the entire vector is all-one or all zero.
 650   SmallVector<SDValue, 8> Ops(NumElem, Mask);
 651   Mask = DAG.getNode(ISD::BUILD_VECTOR, DL, MaskTy, Ops);
 652
 653   // Bitcast the operands to be the same type as the mask.
 654   // This is needed when we select between FP types because
 655   // the mask is a vector of integers.
 656   Op1 = DAG.getNode(ISD::BITCAST, DL, MaskTy, Op1);
 657   Op2 = DAG.getNode(ISD::BITCAST, DL, MaskTy, Op2);
 658
 659   SDValue AllOnes = DAG.getConstant(
 660             APInt::getAllOnesValue(BitTy.getSizeInBits()), MaskTy);
 661   SDValue NotMask = DAG.getNode(ISD::XOR, DL, MaskTy, Mask, AllOnes);
 662
 663   Op1 = DAG.getNode(ISD::AND, DL, MaskTy, Op1, Mask);
 664   Op2 = DAG.getNode(ISD::AND, DL, MaskTy, Op2, NotMask);
 665   SDValue Val = DAG.getNode(ISD::OR, DL, MaskTy, Op1, Op2);
 666   return DAG.getNode(ISD::BITCAST, DL, Op.getValueType(), Val);
 667 }
 668
 669 SDValue VectorLegalizer::ExpandSEXTINREG(SDValue Op) {
 670   EVT VT = Op.getValueType();
 671
 672   // Make sure that the SRA and SHL instructions are available.
 673   if (TLI.getOperationAction(ISD::SRA, VT) == TargetLowering::Expand ||
 674       TLI.getOperationAction(ISD::SHL, VT) == TargetLowering::Expand)
 675     return DAG.UnrollVectorOp(Op.getNode());
 676
 677   SDLoc DL(Op);
 678   EVT OrigTy = cast<VTSDNode>(Op->getOperand(1))->getVT();
 679
 680   unsigned BW = VT.getScalarType().getSizeInBits();
 681   unsigned OrigBW = OrigTy.getScalarType().getSizeInBits();
 682   SDValue ShiftSz = DAG.getConstant(BW - OrigBW, VT);
 683
 684   Op = Op.getOperand(0);
 685   Op =   DAG.getNode(ISD::SHL, DL, VT, Op, ShiftSz);
 686   return DAG.getNode(ISD::SRA, DL, VT, Op, ShiftSz);
 687 }
 688
 689 SDValue VectorLegalizer::ExpandBSWAP(SDValue Op) {
 690   EVT VT = Op.getValueType();
 691
 692   // Generate a byte wise shuffle mask for the BSWAP.
 693   SmallVector<int, 16> ShuffleMask;
 694   int ScalarSizeInBytes = VT.getScalarSizeInBits() / 8;
 695   for (int I = 0, E = VT.getVectorNumElements(); I != E; ++I)
 696     for (int J = ScalarSizeInBytes - 1; J >= 0; --J)
 697       ShuffleMask.push_back((I * ScalarSizeInBytes) + J);
 698
 699   EVT ByteVT = EVT::getVectorVT(*DAG.getContext(), MVT::i8, ShuffleMask.size());
 700
 701   // Only emit a shuffle if the mask is legal.
 702   if (!TLI.isShuffleMaskLegal(ShuffleMask, ByteVT))
 703     return DAG.UnrollVectorOp(Op.getNode());
 704
 705   SDLoc DL(Op);
 706   Op = DAG.getNode(ISD::BITCAST, DL, ByteVT, Op.getOperand(0));
 707   Op = DAG.getVectorShuffle(ByteVT, DL, Op, DAG.getUNDEF(ByteVT),
 708                             ShuffleMask.data());
 709   return DAG.getNode(ISD::BITCAST, DL, VT, Op);
 710 }
 711
 712 SDValue VectorLegalizer::ExpandVSELECT(SDValue Op) {
 713   // Implement VSELECT in terms of XOR, AND, OR
 714   // on platforms which do not support blend natively.
 715   SDLoc DL(Op);
 716
 717   SDValue Mask = Op.getOperand(0);
 718   SDValue Op1 = Op.getOperand(1);
 719   SDValue Op2 = Op.getOperand(2);
 720
 721   EVT VT = Mask.getValueType();
 722
 723   // If we can't even use the basic vector operations of
 724   // AND,OR,XOR, we will have to scalarize the op.
 725   // Notice that the operation may be 'promoted' which means that it is
 726   // 'bitcasted' to another type which is handled.
 727   // This operation also isn't safe with AND, OR, XOR when the boolean
 728   // type is 0/1 as we need an all ones vector constant to mask with.
 729   // FIXME: Sign extend 1 to all ones if thats legal on the target.
 730   if (TLI.getOperationAction(ISD::AND, VT) == TargetLowering::Expand ||
 731       TLI.getOperationAction(ISD::XOR, VT) == TargetLowering::Expand ||
 732       TLI.getOperationAction(ISD::OR,  VT) == TargetLowering::Expand ||
 733       TLI.getBooleanContents(true) !=
 734       TargetLowering::ZeroOrNegativeOneBooleanContent)
 735     return DAG.UnrollVectorOp(Op.getNode());
 736
 737   // If the mask and the type are different sizes, unroll the vector op. This
 738   // can occur when getSetCCResultType returns something that is different in
 739   // size from the operand types. For example, v4i8 = select v4i32, v4i8, v4i8.
 740   if (VT.getSizeInBits() != Op1.getValueType().getSizeInBits())
 741     return DAG.UnrollVectorOp(Op.getNode());
 742
 743   // Bitcast the operands to be the same type as the mask.
 744   // This is needed when we select between FP types because
 745   // the mask is a vector of integers.
 746   Op1 = DAG.getNode(ISD::BITCAST, DL, VT, Op1);
 747   Op2 = DAG.getNode(ISD::BITCAST, DL, VT, Op2);
 748
 749   SDValue AllOnes = DAG.getConstant(
 750     APInt::getAllOnesValue(VT.getScalarType().getSizeInBits()), VT);
 751   SDValue NotMask = DAG.getNode(ISD::XOR, DL, VT, Mask, AllOnes);
 752
 753   Op1 = DAG.getNode(ISD::AND, DL, VT, Op1, Mask);
 754   Op2 = DAG.getNode(ISD::AND, DL, VT, Op2, NotMask);
 755   SDValue Val = DAG.getNode(ISD::OR, DL, VT, Op1, Op2);
 756   return DAG.getNode(ISD::BITCAST, DL, Op.getValueType(), Val);
 757 }
 758
 759 SDValue VectorLegalizer::ExpandUINT_TO_FLOAT(SDValue Op) {
 760   EVT VT = Op.getOperand(0).getValueType();
 761   SDLoc DL(Op);
 762
 763   // Make sure that the SINT_TO_FP and SRL instructions are available.
 764   if (TLI.getOperationAction(ISD::SINT_TO_FP, VT) == TargetLowering::Expand ||
 765       TLI.getOperationAction(ISD::SRL,        VT) == TargetLowering::Expand)
 766     return DAG.UnrollVectorOp(Op.getNode());
 767
 768  EVT SVT = VT.getScalarType();
 769   assert((SVT.getSizeInBits() == 64 || SVT.getSizeInBits() == 32) &&
 770       "Elements in vector-UINT_TO_FP must be 32 or 64 bits wide");
 771
 772   unsigned BW = SVT.getSizeInBits();
 773   SDValue HalfWord = DAG.getConstant(BW/2, VT);
 774
 775   // Constants to clear the upper part of the word.
 776   // Notice that we can also use SHL+SHR, but using a constant is slightly
 777   // faster on x86.
 778   uint64_t HWMask = (SVT.getSizeInBits()==64)?0x00000000FFFFFFFF:0x0000FFFF;
 779   SDValue HalfWordMask = DAG.getConstant(HWMask, VT);
 780
 781   // Two to the power of half-word-size.
 782   SDValue TWOHW = DAG.getConstantFP((1<<(BW/2)), Op.getValueType());
 783
 784   // Clear upper part of LO, lower HI
 785   SDValue HI = DAG.getNode(ISD::SRL, DL, VT, Op.getOperand(0), HalfWord);
 786   SDValue LO = DAG.getNode(ISD::AND, DL, VT, Op.getOperand(0), HalfWordMask);
 787
 788   // Convert hi and lo to floats
 789   // Convert the hi part back to the upper values
 790   SDValue fHI = DAG.getNode(ISD::SINT_TO_FP, DL, Op.getValueType(), HI);
 791           fHI = DAG.getNode(ISD::FMUL, DL, Op.getValueType(), fHI, TWOHW);
 792   SDValue fLO = DAG.getNode(ISD::SINT_TO_FP, DL, Op.getValueType(), LO);
 793
 794   // Add the two halves
 795   return DAG.getNode(ISD::FADD, DL, Op.getValueType(), fHI, fLO);
 796 }
 797
 798
 799 SDValue VectorLegalizer::ExpandFNEG(SDValue Op) {
 800   if (TLI.isOperationLegalOrCustom(ISD::FSUB, Op.getValueType())) {
 801     SDValue Zero = DAG.getConstantFP(-0.0, Op.getValueType());
 802     return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
 803                        Zero, Op.getOperand(0));
 804   }
 805   return DAG.UnrollVectorOp(Op.getNode());
 806 }
 807
 808 SDValue VectorLegalizer::UnrollVSETCC(SDValue Op) {
 809   EVT VT = Op.getValueType();
 810   unsigned NumElems = VT.getVectorNumElements();
 811   EVT EltVT = VT.getVectorElementType();
 812   SDValue LHS = Op.getOperand(0), RHS = Op.getOperand(1), CC = Op.getOperand(2);
 813   EVT TmpEltVT = LHS.getValueType().getVectorElementType();
 814   SDLoc dl(Op);
 815   SmallVector<SDValue, 8> Ops(NumElems);
 816   for (unsigned i = 0; i < NumElems; ++i) {
 817     SDValue LHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, LHS,
 818                                   DAG.getConstant(i, TLI.getVectorIdxTy()));
 819     SDValue RHSElem = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, TmpEltVT, RHS,
 820                                   DAG.getConstant(i, TLI.getVectorIdxTy()));
 821     Ops[i] = DAG.getNode(ISD::SETCC, dl,
 822                          TLI.getSetCCResultType(*DAG.getContext(), TmpEltVT),
 823                          LHSElem, RHSElem, CC);
 824     Ops[i] = DAG.getSelect(dl, EltVT, Ops[i],
 825                            DAG.getConstant(APInt::getAllOnesValue
 826                                            (EltVT.getSizeInBits()), EltVT),
 827                            DAG.getConstant(0, EltVT));
 828   }
 829   return DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ops);
 830 }
 831
 832 }
 833
 834 bool SelectionDAG::LegalizeVectors() {
 835   return VectorLegalizer(*this).Run();
 836 }