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