1 //===-- llvm/CodeGen/GlobalISel/LegalizerHelper.cpp -----------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file This file implements the LegalizerHelper class to legalize 10 /// individual instructions and the LegalizeMachineIR wrapper pass for the 11 /// primary legalization. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h" 16 #include "llvm/CodeGen/GlobalISel/CallLowering.h" 17 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 18 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" 19 #include "llvm/CodeGen/MachineRegisterInfo.h" 20 #include "llvm/CodeGen/TargetInstrInfo.h" 21 #include "llvm/CodeGen/TargetLowering.h" 22 #include "llvm/CodeGen/TargetSubtargetInfo.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/MathExtras.h" 25 #include "llvm/Support/raw_ostream.h" 26 27 #define DEBUG_TYPE "legalizer" 28 29 using namespace llvm; 30 using namespace LegalizeActions; 31 32 /// Try to break down \p OrigTy into \p NarrowTy sized pieces. 33 /// 34 /// Returns the number of \p NarrowTy elements needed to reconstruct \p OrigTy, 35 /// with any leftover piece as type \p LeftoverTy 36 /// 37 /// Returns -1 in the first element of the pair if the breakdown is not 38 /// satisfiable. 39 static std::pair<int, int> 40 getNarrowTypeBreakDown(LLT OrigTy, LLT NarrowTy, LLT &LeftoverTy) { 41 assert(!LeftoverTy.isValid() && "this is an out argument"); 42 43 unsigned Size = OrigTy.getSizeInBits(); 44 unsigned NarrowSize = NarrowTy.getSizeInBits(); 45 unsigned NumParts = Size / NarrowSize; 46 unsigned LeftoverSize = Size - NumParts * NarrowSize; 47 assert(Size > NarrowSize); 48 49 if (LeftoverSize == 0) 50 return {NumParts, 0}; 51 52 if (NarrowTy.isVector()) { 53 unsigned EltSize = OrigTy.getScalarSizeInBits(); 54 if (LeftoverSize % EltSize != 0) 55 return {-1, -1}; 56 LeftoverTy = LLT::scalarOrVector(LeftoverSize / EltSize, EltSize); 57 } else { 58 LeftoverTy = LLT::scalar(LeftoverSize); 59 } 60 61 int NumLeftover = LeftoverSize / LeftoverTy.getSizeInBits(); 62 return std::make_pair(NumParts, NumLeftover); 63 } 64 65 LegalizerHelper::LegalizerHelper(MachineFunction &MF, 66 GISelChangeObserver &Observer, 67 MachineIRBuilder &Builder) 68 : MIRBuilder(Builder), MRI(MF.getRegInfo()), 69 LI(*MF.getSubtarget().getLegalizerInfo()), Observer(Observer) { 70 MIRBuilder.setMF(MF); 71 MIRBuilder.setChangeObserver(Observer); 72 } 73 74 LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI, 75 GISelChangeObserver &Observer, 76 MachineIRBuilder &B) 77 : MIRBuilder(B), MRI(MF.getRegInfo()), LI(LI), Observer(Observer) { 78 MIRBuilder.setMF(MF); 79 MIRBuilder.setChangeObserver(Observer); 80 } 81 LegalizerHelper::LegalizeResult 82 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) { 83 LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs())); 84 85 auto Step = LI.getAction(MI, MRI); 86 switch (Step.Action) { 87 case Legal: 88 LLVM_DEBUG(dbgs() << ".. Already legal\n"); 89 return AlreadyLegal; 90 case Libcall: 91 LLVM_DEBUG(dbgs() << ".. Convert to libcall\n"); 92 return libcall(MI); 93 case NarrowScalar: 94 LLVM_DEBUG(dbgs() << ".. Narrow scalar\n"); 95 return narrowScalar(MI, Step.TypeIdx, Step.NewType); 96 case WidenScalar: 97 LLVM_DEBUG(dbgs() << ".. Widen scalar\n"); 98 return widenScalar(MI, Step.TypeIdx, Step.NewType); 99 case Lower: 100 LLVM_DEBUG(dbgs() << ".. Lower\n"); 101 return lower(MI, Step.TypeIdx, Step.NewType); 102 case FewerElements: 103 LLVM_DEBUG(dbgs() << ".. Reduce number of elements\n"); 104 return fewerElementsVector(MI, Step.TypeIdx, Step.NewType); 105 case MoreElements: 106 LLVM_DEBUG(dbgs() << ".. Increase number of elements\n"); 107 return moreElementsVector(MI, Step.TypeIdx, Step.NewType); 108 case Custom: 109 LLVM_DEBUG(dbgs() << ".. Custom legalization\n"); 110 return LI.legalizeCustom(MI, MRI, MIRBuilder, Observer) ? Legalized 111 : UnableToLegalize; 112 default: 113 LLVM_DEBUG(dbgs() << ".. Unable to legalize\n"); 114 return UnableToLegalize; 115 } 116 } 117 118 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts, 119 SmallVectorImpl<unsigned> &VRegs) { 120 for (int i = 0; i < NumParts; ++i) 121 VRegs.push_back(MRI.createGenericVirtualRegister(Ty)); 122 MIRBuilder.buildUnmerge(VRegs, Reg); 123 } 124 125 bool LegalizerHelper::extractParts(unsigned Reg, LLT RegTy, 126 LLT MainTy, LLT &LeftoverTy, 127 SmallVectorImpl<unsigned> &VRegs, 128 SmallVectorImpl<unsigned> &LeftoverRegs) { 129 assert(!LeftoverTy.isValid() && "this is an out argument"); 130 131 unsigned RegSize = RegTy.getSizeInBits(); 132 unsigned MainSize = MainTy.getSizeInBits(); 133 unsigned NumParts = RegSize / MainSize; 134 unsigned LeftoverSize = RegSize - NumParts * MainSize; 135 136 // Use an unmerge when possible. 137 if (LeftoverSize == 0) { 138 for (unsigned I = 0; I < NumParts; ++I) 139 VRegs.push_back(MRI.createGenericVirtualRegister(MainTy)); 140 MIRBuilder.buildUnmerge(VRegs, Reg); 141 return true; 142 } 143 144 if (MainTy.isVector()) { 145 unsigned EltSize = MainTy.getScalarSizeInBits(); 146 if (LeftoverSize % EltSize != 0) 147 return false; 148 LeftoverTy = LLT::scalarOrVector(LeftoverSize / EltSize, EltSize); 149 } else { 150 LeftoverTy = LLT::scalar(LeftoverSize); 151 } 152 153 // For irregular sizes, extract the individual parts. 154 for (unsigned I = 0; I != NumParts; ++I) { 155 unsigned NewReg = MRI.createGenericVirtualRegister(MainTy); 156 VRegs.push_back(NewReg); 157 MIRBuilder.buildExtract(NewReg, Reg, MainSize * I); 158 } 159 160 for (unsigned Offset = MainSize * NumParts; Offset < RegSize; 161 Offset += LeftoverSize) { 162 unsigned NewReg = MRI.createGenericVirtualRegister(LeftoverTy); 163 LeftoverRegs.push_back(NewReg); 164 MIRBuilder.buildExtract(NewReg, Reg, Offset); 165 } 166 167 return true; 168 } 169 170 void LegalizerHelper::insertParts(unsigned DstReg, 171 LLT ResultTy, LLT PartTy, 172 ArrayRef<unsigned> PartRegs, 173 LLT LeftoverTy, 174 ArrayRef<unsigned> LeftoverRegs) { 175 if (!LeftoverTy.isValid()) { 176 assert(LeftoverRegs.empty()); 177 178 if (!ResultTy.isVector()) { 179 MIRBuilder.buildMerge(DstReg, PartRegs); 180 return; 181 } 182 183 if (PartTy.isVector()) 184 MIRBuilder.buildConcatVectors(DstReg, PartRegs); 185 else 186 MIRBuilder.buildBuildVector(DstReg, PartRegs); 187 return; 188 } 189 190 unsigned PartSize = PartTy.getSizeInBits(); 191 unsigned LeftoverPartSize = LeftoverTy.getSizeInBits(); 192 193 unsigned CurResultReg = MRI.createGenericVirtualRegister(ResultTy); 194 MIRBuilder.buildUndef(CurResultReg); 195 196 unsigned Offset = 0; 197 for (unsigned PartReg : PartRegs) { 198 unsigned NewResultReg = MRI.createGenericVirtualRegister(ResultTy); 199 MIRBuilder.buildInsert(NewResultReg, CurResultReg, PartReg, Offset); 200 CurResultReg = NewResultReg; 201 Offset += PartSize; 202 } 203 204 for (unsigned I = 0, E = LeftoverRegs.size(); I != E; ++I) { 205 // Use the original output register for the final insert to avoid a copy. 206 unsigned NewResultReg = (I + 1 == E) ? 207 DstReg : MRI.createGenericVirtualRegister(ResultTy); 208 209 MIRBuilder.buildInsert(NewResultReg, CurResultReg, LeftoverRegs[I], Offset); 210 CurResultReg = NewResultReg; 211 Offset += LeftoverPartSize; 212 } 213 } 214 215 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) { 216 switch (Opcode) { 217 case TargetOpcode::G_SDIV: 218 assert((Size == 32 || Size == 64) && "Unsupported size"); 219 return Size == 64 ? RTLIB::SDIV_I64 : RTLIB::SDIV_I32; 220 case TargetOpcode::G_UDIV: 221 assert((Size == 32 || Size == 64) && "Unsupported size"); 222 return Size == 64 ? RTLIB::UDIV_I64 : RTLIB::UDIV_I32; 223 case TargetOpcode::G_SREM: 224 assert((Size == 32 || Size == 64) && "Unsupported size"); 225 return Size == 64 ? RTLIB::SREM_I64 : RTLIB::SREM_I32; 226 case TargetOpcode::G_UREM: 227 assert((Size == 32 || Size == 64) && "Unsupported size"); 228 return Size == 64 ? RTLIB::UREM_I64 : RTLIB::UREM_I32; 229 case TargetOpcode::G_CTLZ_ZERO_UNDEF: 230 assert(Size == 32 && "Unsupported size"); 231 return RTLIB::CTLZ_I32; 232 case TargetOpcode::G_FADD: 233 assert((Size == 32 || Size == 64) && "Unsupported size"); 234 return Size == 64 ? RTLIB::ADD_F64 : RTLIB::ADD_F32; 235 case TargetOpcode::G_FSUB: 236 assert((Size == 32 || Size == 64) && "Unsupported size"); 237 return Size == 64 ? RTLIB::SUB_F64 : RTLIB::SUB_F32; 238 case TargetOpcode::G_FMUL: 239 assert((Size == 32 || Size == 64) && "Unsupported size"); 240 return Size == 64 ? RTLIB::MUL_F64 : RTLIB::MUL_F32; 241 case TargetOpcode::G_FDIV: 242 assert((Size == 32 || Size == 64) && "Unsupported size"); 243 return Size == 64 ? RTLIB::DIV_F64 : RTLIB::DIV_F32; 244 case TargetOpcode::G_FEXP: 245 assert((Size == 32 || Size == 64) && "Unsupported size"); 246 return Size == 64 ? RTLIB::EXP_F64 : RTLIB::EXP_F32; 247 case TargetOpcode::G_FEXP2: 248 assert((Size == 32 || Size == 64) && "Unsupported size"); 249 return Size == 64 ? RTLIB::EXP2_F64 : RTLIB::EXP2_F32; 250 case TargetOpcode::G_FREM: 251 return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32; 252 case TargetOpcode::G_FPOW: 253 return Size == 64 ? RTLIB::POW_F64 : RTLIB::POW_F32; 254 case TargetOpcode::G_FMA: 255 assert((Size == 32 || Size == 64) && "Unsupported size"); 256 return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32; 257 case TargetOpcode::G_FSIN: 258 assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size"); 259 return Size == 128 ? RTLIB::SIN_F128 260 : Size == 64 ? RTLIB::SIN_F64 : RTLIB::SIN_F32; 261 case TargetOpcode::G_FCOS: 262 assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size"); 263 return Size == 128 ? RTLIB::COS_F128 264 : Size == 64 ? RTLIB::COS_F64 : RTLIB::COS_F32; 265 case TargetOpcode::G_FLOG10: 266 assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size"); 267 return Size == 128 ? RTLIB::LOG10_F128 268 : Size == 64 ? RTLIB::LOG10_F64 : RTLIB::LOG10_F32; 269 case TargetOpcode::G_FLOG: 270 assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size"); 271 return Size == 128 ? RTLIB::LOG_F128 272 : Size == 64 ? RTLIB::LOG_F64 : RTLIB::LOG_F32; 273 case TargetOpcode::G_FLOG2: 274 assert((Size == 32 || Size == 64 || Size == 128) && "Unsupported size"); 275 return Size == 128 ? RTLIB::LOG2_F128 276 : Size == 64 ? RTLIB::LOG2_F64 : RTLIB::LOG2_F32; 277 } 278 llvm_unreachable("Unknown libcall function"); 279 } 280 281 LegalizerHelper::LegalizeResult 282 llvm::createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall, 283 const CallLowering::ArgInfo &Result, 284 ArrayRef<CallLowering::ArgInfo> Args) { 285 auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering(); 286 auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering(); 287 const char *Name = TLI.getLibcallName(Libcall); 288 289 MIRBuilder.getMF().getFrameInfo().setHasCalls(true); 290 if (!CLI.lowerCall(MIRBuilder, TLI.getLibcallCallingConv(Libcall), 291 MachineOperand::CreateES(Name), Result, Args)) 292 return LegalizerHelper::UnableToLegalize; 293 294 return LegalizerHelper::Legalized; 295 } 296 297 // Useful for libcalls where all operands have the same type. 298 static LegalizerHelper::LegalizeResult 299 simpleLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, unsigned Size, 300 Type *OpType) { 301 auto Libcall = getRTLibDesc(MI.getOpcode(), Size); 302 303 SmallVector<CallLowering::ArgInfo, 3> Args; 304 for (unsigned i = 1; i < MI.getNumOperands(); i++) 305 Args.push_back({MI.getOperand(i).getReg(), OpType}); 306 return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType}, 307 Args); 308 } 309 310 static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType, 311 Type *FromType) { 312 auto ToMVT = MVT::getVT(ToType); 313 auto FromMVT = MVT::getVT(FromType); 314 315 switch (Opcode) { 316 case TargetOpcode::G_FPEXT: 317 return RTLIB::getFPEXT(FromMVT, ToMVT); 318 case TargetOpcode::G_FPTRUNC: 319 return RTLIB::getFPROUND(FromMVT, ToMVT); 320 case TargetOpcode::G_FPTOSI: 321 return RTLIB::getFPTOSINT(FromMVT, ToMVT); 322 case TargetOpcode::G_FPTOUI: 323 return RTLIB::getFPTOUINT(FromMVT, ToMVT); 324 case TargetOpcode::G_SITOFP: 325 return RTLIB::getSINTTOFP(FromMVT, ToMVT); 326 case TargetOpcode::G_UITOFP: 327 return RTLIB::getUINTTOFP(FromMVT, ToMVT); 328 } 329 llvm_unreachable("Unsupported libcall function"); 330 } 331 332 static LegalizerHelper::LegalizeResult 333 conversionLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, Type *ToType, 334 Type *FromType) { 335 RTLIB::Libcall Libcall = getConvRTLibDesc(MI.getOpcode(), ToType, FromType); 336 return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), ToType}, 337 {{MI.getOperand(1).getReg(), FromType}}); 338 } 339 340 LegalizerHelper::LegalizeResult 341 LegalizerHelper::libcall(MachineInstr &MI) { 342 LLT LLTy = MRI.getType(MI.getOperand(0).getReg()); 343 unsigned Size = LLTy.getSizeInBits(); 344 auto &Ctx = MIRBuilder.getMF().getFunction().getContext(); 345 346 MIRBuilder.setInstr(MI); 347 348 switch (MI.getOpcode()) { 349 default: 350 return UnableToLegalize; 351 case TargetOpcode::G_SDIV: 352 case TargetOpcode::G_UDIV: 353 case TargetOpcode::G_SREM: 354 case TargetOpcode::G_UREM: 355 case TargetOpcode::G_CTLZ_ZERO_UNDEF: { 356 Type *HLTy = IntegerType::get(Ctx, Size); 357 auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy); 358 if (Status != Legalized) 359 return Status; 360 break; 361 } 362 case TargetOpcode::G_FADD: 363 case TargetOpcode::G_FSUB: 364 case TargetOpcode::G_FMUL: 365 case TargetOpcode::G_FDIV: 366 case TargetOpcode::G_FMA: 367 case TargetOpcode::G_FPOW: 368 case TargetOpcode::G_FREM: 369 case TargetOpcode::G_FCOS: 370 case TargetOpcode::G_FSIN: 371 case TargetOpcode::G_FLOG10: 372 case TargetOpcode::G_FLOG: 373 case TargetOpcode::G_FLOG2: 374 case TargetOpcode::G_FEXP: 375 case TargetOpcode::G_FEXP2: { 376 if (Size > 64) { 377 LLVM_DEBUG(dbgs() << "Size " << Size << " too large to legalize.\n"); 378 return UnableToLegalize; 379 } 380 Type *HLTy = Size == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx); 381 auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy); 382 if (Status != Legalized) 383 return Status; 384 break; 385 } 386 case TargetOpcode::G_FPEXT: { 387 // FIXME: Support other floating point types (half, fp128 etc) 388 unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits(); 389 unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 390 if (ToSize != 64 || FromSize != 32) 391 return UnableToLegalize; 392 LegalizeResult Status = conversionLibcall( 393 MI, MIRBuilder, Type::getDoubleTy(Ctx), Type::getFloatTy(Ctx)); 394 if (Status != Legalized) 395 return Status; 396 break; 397 } 398 case TargetOpcode::G_FPTRUNC: { 399 // FIXME: Support other floating point types (half, fp128 etc) 400 unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits(); 401 unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 402 if (ToSize != 32 || FromSize != 64) 403 return UnableToLegalize; 404 LegalizeResult Status = conversionLibcall( 405 MI, MIRBuilder, Type::getFloatTy(Ctx), Type::getDoubleTy(Ctx)); 406 if (Status != Legalized) 407 return Status; 408 break; 409 } 410 case TargetOpcode::G_FPTOSI: 411 case TargetOpcode::G_FPTOUI: { 412 // FIXME: Support other types 413 unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits(); 414 unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 415 if (ToSize != 32 || (FromSize != 32 && FromSize != 64)) 416 return UnableToLegalize; 417 LegalizeResult Status = conversionLibcall( 418 MI, MIRBuilder, Type::getInt32Ty(Ctx), 419 FromSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx)); 420 if (Status != Legalized) 421 return Status; 422 break; 423 } 424 case TargetOpcode::G_SITOFP: 425 case TargetOpcode::G_UITOFP: { 426 // FIXME: Support other types 427 unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits(); 428 unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 429 if (FromSize != 32 || (ToSize != 32 && ToSize != 64)) 430 return UnableToLegalize; 431 LegalizeResult Status = conversionLibcall( 432 MI, MIRBuilder, 433 ToSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx), 434 Type::getInt32Ty(Ctx)); 435 if (Status != Legalized) 436 return Status; 437 break; 438 } 439 } 440 441 MI.eraseFromParent(); 442 return Legalized; 443 } 444 445 LegalizerHelper::LegalizeResult LegalizerHelper::narrowScalar(MachineInstr &MI, 446 unsigned TypeIdx, 447 LLT NarrowTy) { 448 MIRBuilder.setInstr(MI); 449 450 uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 451 uint64_t NarrowSize = NarrowTy.getSizeInBits(); 452 453 switch (MI.getOpcode()) { 454 default: 455 return UnableToLegalize; 456 case TargetOpcode::G_IMPLICIT_DEF: { 457 // FIXME: add support for when SizeOp0 isn't an exact multiple of 458 // NarrowSize. 459 if (SizeOp0 % NarrowSize != 0) 460 return UnableToLegalize; 461 int NumParts = SizeOp0 / NarrowSize; 462 463 SmallVector<unsigned, 2> DstRegs; 464 for (int i = 0; i < NumParts; ++i) 465 DstRegs.push_back( 466 MIRBuilder.buildUndef(NarrowTy)->getOperand(0).getReg()); 467 468 unsigned DstReg = MI.getOperand(0).getReg(); 469 if(MRI.getType(DstReg).isVector()) 470 MIRBuilder.buildBuildVector(DstReg, DstRegs); 471 else 472 MIRBuilder.buildMerge(DstReg, DstRegs); 473 MI.eraseFromParent(); 474 return Legalized; 475 } 476 case TargetOpcode::G_ADD: { 477 // FIXME: add support for when SizeOp0 isn't an exact multiple of 478 // NarrowSize. 479 if (SizeOp0 % NarrowSize != 0) 480 return UnableToLegalize; 481 // Expand in terms of carry-setting/consuming G_ADDE instructions. 482 int NumParts = SizeOp0 / NarrowTy.getSizeInBits(); 483 484 SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs; 485 extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs); 486 extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs); 487 488 unsigned CarryIn = MRI.createGenericVirtualRegister(LLT::scalar(1)); 489 MIRBuilder.buildConstant(CarryIn, 0); 490 491 for (int i = 0; i < NumParts; ++i) { 492 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 493 unsigned CarryOut = MRI.createGenericVirtualRegister(LLT::scalar(1)); 494 495 MIRBuilder.buildUAdde(DstReg, CarryOut, Src1Regs[i], 496 Src2Regs[i], CarryIn); 497 498 DstRegs.push_back(DstReg); 499 CarryIn = CarryOut; 500 } 501 unsigned DstReg = MI.getOperand(0).getReg(); 502 if(MRI.getType(DstReg).isVector()) 503 MIRBuilder.buildBuildVector(DstReg, DstRegs); 504 else 505 MIRBuilder.buildMerge(DstReg, DstRegs); 506 MI.eraseFromParent(); 507 return Legalized; 508 } 509 case TargetOpcode::G_SUB: { 510 // FIXME: add support for when SizeOp0 isn't an exact multiple of 511 // NarrowSize. 512 if (SizeOp0 % NarrowSize != 0) 513 return UnableToLegalize; 514 515 int NumParts = SizeOp0 / NarrowTy.getSizeInBits(); 516 517 SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs; 518 extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs); 519 extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs); 520 521 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 522 unsigned BorrowOut = MRI.createGenericVirtualRegister(LLT::scalar(1)); 523 MIRBuilder.buildInstr(TargetOpcode::G_USUBO, {DstReg, BorrowOut}, 524 {Src1Regs[0], Src2Regs[0]}); 525 DstRegs.push_back(DstReg); 526 unsigned BorrowIn = BorrowOut; 527 for (int i = 1; i < NumParts; ++i) { 528 DstReg = MRI.createGenericVirtualRegister(NarrowTy); 529 BorrowOut = MRI.createGenericVirtualRegister(LLT::scalar(1)); 530 531 MIRBuilder.buildInstr(TargetOpcode::G_USUBE, {DstReg, BorrowOut}, 532 {Src1Regs[i], Src2Regs[i], BorrowIn}); 533 534 DstRegs.push_back(DstReg); 535 BorrowIn = BorrowOut; 536 } 537 MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs); 538 MI.eraseFromParent(); 539 return Legalized; 540 } 541 case TargetOpcode::G_MUL: 542 case TargetOpcode::G_UMULH: 543 return narrowScalarMul(MI, NarrowTy); 544 case TargetOpcode::G_EXTRACT: 545 return narrowScalarExtract(MI, TypeIdx, NarrowTy); 546 case TargetOpcode::G_INSERT: 547 return narrowScalarInsert(MI, TypeIdx, NarrowTy); 548 case TargetOpcode::G_LOAD: { 549 const auto &MMO = **MI.memoperands_begin(); 550 unsigned DstReg = MI.getOperand(0).getReg(); 551 LLT DstTy = MRI.getType(DstReg); 552 if (DstTy.isVector()) 553 return UnableToLegalize; 554 555 if (8 * MMO.getSize() != DstTy.getSizeInBits()) { 556 unsigned TmpReg = MRI.createGenericVirtualRegister(NarrowTy); 557 auto &MMO = **MI.memoperands_begin(); 558 MIRBuilder.buildLoad(TmpReg, MI.getOperand(1).getReg(), MMO); 559 MIRBuilder.buildAnyExt(DstReg, TmpReg); 560 MI.eraseFromParent(); 561 return Legalized; 562 } 563 564 return reduceLoadStoreWidth(MI, TypeIdx, NarrowTy); 565 } 566 case TargetOpcode::G_ZEXTLOAD: 567 case TargetOpcode::G_SEXTLOAD: { 568 bool ZExt = MI.getOpcode() == TargetOpcode::G_ZEXTLOAD; 569 unsigned DstReg = MI.getOperand(0).getReg(); 570 unsigned PtrReg = MI.getOperand(1).getReg(); 571 572 unsigned TmpReg = MRI.createGenericVirtualRegister(NarrowTy); 573 auto &MMO = **MI.memoperands_begin(); 574 if (MMO.getSize() * 8 == NarrowSize) { 575 MIRBuilder.buildLoad(TmpReg, PtrReg, MMO); 576 } else { 577 unsigned ExtLoad = ZExt ? TargetOpcode::G_ZEXTLOAD 578 : TargetOpcode::G_SEXTLOAD; 579 MIRBuilder.buildInstr(ExtLoad) 580 .addDef(TmpReg) 581 .addUse(PtrReg) 582 .addMemOperand(&MMO); 583 } 584 585 if (ZExt) 586 MIRBuilder.buildZExt(DstReg, TmpReg); 587 else 588 MIRBuilder.buildSExt(DstReg, TmpReg); 589 590 MI.eraseFromParent(); 591 return Legalized; 592 } 593 case TargetOpcode::G_STORE: { 594 const auto &MMO = **MI.memoperands_begin(); 595 596 unsigned SrcReg = MI.getOperand(0).getReg(); 597 LLT SrcTy = MRI.getType(SrcReg); 598 if (SrcTy.isVector()) 599 return UnableToLegalize; 600 601 int NumParts = SizeOp0 / NarrowSize; 602 unsigned HandledSize = NumParts * NarrowTy.getSizeInBits(); 603 unsigned LeftoverBits = SrcTy.getSizeInBits() - HandledSize; 604 if (SrcTy.isVector() && LeftoverBits != 0) 605 return UnableToLegalize; 606 607 if (8 * MMO.getSize() != SrcTy.getSizeInBits()) { 608 unsigned TmpReg = MRI.createGenericVirtualRegister(NarrowTy); 609 auto &MMO = **MI.memoperands_begin(); 610 MIRBuilder.buildTrunc(TmpReg, SrcReg); 611 MIRBuilder.buildStore(TmpReg, MI.getOperand(1).getReg(), MMO); 612 MI.eraseFromParent(); 613 return Legalized; 614 } 615 616 return reduceLoadStoreWidth(MI, 0, NarrowTy); 617 } 618 case TargetOpcode::G_CONSTANT: { 619 // FIXME: add support for when SizeOp0 isn't an exact multiple of 620 // NarrowSize. 621 if (SizeOp0 % NarrowSize != 0) 622 return UnableToLegalize; 623 int NumParts = SizeOp0 / NarrowSize; 624 const APInt &Cst = MI.getOperand(1).getCImm()->getValue(); 625 LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext(); 626 627 SmallVector<unsigned, 2> DstRegs; 628 for (int i = 0; i < NumParts; ++i) { 629 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 630 ConstantInt *CI = 631 ConstantInt::get(Ctx, Cst.lshr(NarrowSize * i).trunc(NarrowSize)); 632 MIRBuilder.buildConstant(DstReg, *CI); 633 DstRegs.push_back(DstReg); 634 } 635 unsigned DstReg = MI.getOperand(0).getReg(); 636 if(MRI.getType(DstReg).isVector()) 637 MIRBuilder.buildBuildVector(DstReg, DstRegs); 638 else 639 MIRBuilder.buildMerge(DstReg, DstRegs); 640 MI.eraseFromParent(); 641 return Legalized; 642 } 643 case TargetOpcode::G_SELECT: 644 return narrowScalarSelect(MI, TypeIdx, NarrowTy); 645 case TargetOpcode::G_AND: 646 case TargetOpcode::G_OR: 647 case TargetOpcode::G_XOR: { 648 // Legalize bitwise operation: 649 // A = BinOp<Ty> B, C 650 // into: 651 // B1, ..., BN = G_UNMERGE_VALUES B 652 // C1, ..., CN = G_UNMERGE_VALUES C 653 // A1 = BinOp<Ty/N> B1, C2 654 // ... 655 // AN = BinOp<Ty/N> BN, CN 656 // A = G_MERGE_VALUES A1, ..., AN 657 658 // FIXME: add support for when SizeOp0 isn't an exact multiple of 659 // NarrowSize. 660 if (SizeOp0 % NarrowSize != 0) 661 return UnableToLegalize; 662 int NumParts = SizeOp0 / NarrowSize; 663 664 // List the registers where the destination will be scattered. 665 SmallVector<unsigned, 2> DstRegs; 666 // List the registers where the first argument will be split. 667 SmallVector<unsigned, 2> SrcsReg1; 668 // List the registers where the second argument will be split. 669 SmallVector<unsigned, 2> SrcsReg2; 670 // Create all the temporary registers. 671 for (int i = 0; i < NumParts; ++i) { 672 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 673 unsigned SrcReg1 = MRI.createGenericVirtualRegister(NarrowTy); 674 unsigned SrcReg2 = MRI.createGenericVirtualRegister(NarrowTy); 675 676 DstRegs.push_back(DstReg); 677 SrcsReg1.push_back(SrcReg1); 678 SrcsReg2.push_back(SrcReg2); 679 } 680 // Explode the big arguments into smaller chunks. 681 MIRBuilder.buildUnmerge(SrcsReg1, MI.getOperand(1).getReg()); 682 MIRBuilder.buildUnmerge(SrcsReg2, MI.getOperand(2).getReg()); 683 684 // Do the operation on each small part. 685 for (int i = 0; i < NumParts; ++i) 686 MIRBuilder.buildInstr(MI.getOpcode(), {DstRegs[i]}, 687 {SrcsReg1[i], SrcsReg2[i]}); 688 689 // Gather the destination registers into the final destination. 690 unsigned DstReg = MI.getOperand(0).getReg(); 691 if(MRI.getType(DstReg).isVector()) 692 MIRBuilder.buildBuildVector(DstReg, DstRegs); 693 else 694 MIRBuilder.buildMerge(DstReg, DstRegs); 695 MI.eraseFromParent(); 696 return Legalized; 697 } 698 case TargetOpcode::G_SHL: 699 case TargetOpcode::G_LSHR: 700 case TargetOpcode::G_ASHR: 701 return narrowScalarShift(MI, TypeIdx, NarrowTy); 702 case TargetOpcode::G_CTLZ: 703 case TargetOpcode::G_CTLZ_ZERO_UNDEF: 704 case TargetOpcode::G_CTTZ: 705 case TargetOpcode::G_CTTZ_ZERO_UNDEF: 706 case TargetOpcode::G_CTPOP: 707 if (TypeIdx != 0) 708 return UnableToLegalize; // TODO 709 710 Observer.changingInstr(MI); 711 narrowScalarDst(MI, NarrowTy, 0, TargetOpcode::G_ZEXT); 712 Observer.changedInstr(MI); 713 return Legalized; 714 case TargetOpcode::G_INTTOPTR: 715 if (TypeIdx != 1) 716 return UnableToLegalize; 717 718 Observer.changingInstr(MI); 719 narrowScalarSrc(MI, NarrowTy, 1); 720 Observer.changedInstr(MI); 721 return Legalized; 722 case TargetOpcode::G_PTRTOINT: 723 if (TypeIdx != 0) 724 return UnableToLegalize; 725 726 Observer.changingInstr(MI); 727 narrowScalarDst(MI, NarrowTy, 0, TargetOpcode::G_ZEXT); 728 Observer.changedInstr(MI); 729 return Legalized; 730 } 731 } 732 733 void LegalizerHelper::widenScalarSrc(MachineInstr &MI, LLT WideTy, 734 unsigned OpIdx, unsigned ExtOpcode) { 735 MachineOperand &MO = MI.getOperand(OpIdx); 736 auto ExtB = MIRBuilder.buildInstr(ExtOpcode, {WideTy}, {MO.getReg()}); 737 MO.setReg(ExtB->getOperand(0).getReg()); 738 } 739 740 void LegalizerHelper::narrowScalarSrc(MachineInstr &MI, LLT NarrowTy, 741 unsigned OpIdx) { 742 MachineOperand &MO = MI.getOperand(OpIdx); 743 auto ExtB = MIRBuilder.buildInstr(TargetOpcode::G_TRUNC, {NarrowTy}, 744 {MO.getReg()}); 745 MO.setReg(ExtB->getOperand(0).getReg()); 746 } 747 748 void LegalizerHelper::widenScalarDst(MachineInstr &MI, LLT WideTy, 749 unsigned OpIdx, unsigned TruncOpcode) { 750 MachineOperand &MO = MI.getOperand(OpIdx); 751 unsigned DstExt = MRI.createGenericVirtualRegister(WideTy); 752 MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt()); 753 MIRBuilder.buildInstr(TruncOpcode, {MO.getReg()}, {DstExt}); 754 MO.setReg(DstExt); 755 } 756 757 void LegalizerHelper::narrowScalarDst(MachineInstr &MI, LLT NarrowTy, 758 unsigned OpIdx, unsigned ExtOpcode) { 759 MachineOperand &MO = MI.getOperand(OpIdx); 760 unsigned DstTrunc = MRI.createGenericVirtualRegister(NarrowTy); 761 MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt()); 762 MIRBuilder.buildInstr(ExtOpcode, {MO.getReg()}, {DstTrunc}); 763 MO.setReg(DstTrunc); 764 } 765 766 void LegalizerHelper::moreElementsVectorDst(MachineInstr &MI, LLT WideTy, 767 unsigned OpIdx) { 768 MachineOperand &MO = MI.getOperand(OpIdx); 769 unsigned DstExt = MRI.createGenericVirtualRegister(WideTy); 770 MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt()); 771 MIRBuilder.buildExtract(MO.getReg(), DstExt, 0); 772 MO.setReg(DstExt); 773 } 774 775 void LegalizerHelper::moreElementsVectorSrc(MachineInstr &MI, LLT MoreTy, 776 unsigned OpIdx) { 777 MachineOperand &MO = MI.getOperand(OpIdx); 778 779 LLT OldTy = MRI.getType(MO.getReg()); 780 unsigned OldElts = OldTy.getNumElements(); 781 unsigned NewElts = MoreTy.getNumElements(); 782 783 unsigned NumParts = NewElts / OldElts; 784 785 // Use concat_vectors if the result is a multiple of the number of elements. 786 if (NumParts * OldElts == NewElts) { 787 SmallVector<unsigned, 8> Parts; 788 Parts.push_back(MO.getReg()); 789 790 unsigned ImpDef = MIRBuilder.buildUndef(OldTy).getReg(0); 791 for (unsigned I = 1; I != NumParts; ++I) 792 Parts.push_back(ImpDef); 793 794 auto Concat = MIRBuilder.buildConcatVectors(MoreTy, Parts); 795 MO.setReg(Concat.getReg(0)); 796 return; 797 } 798 799 unsigned MoreReg = MRI.createGenericVirtualRegister(MoreTy); 800 unsigned ImpDef = MIRBuilder.buildUndef(MoreTy).getReg(0); 801 MIRBuilder.buildInsert(MoreReg, ImpDef, MO.getReg(), 0); 802 MO.setReg(MoreReg); 803 } 804 805 LegalizerHelper::LegalizeResult 806 LegalizerHelper::widenScalarMergeValues(MachineInstr &MI, unsigned TypeIdx, 807 LLT WideTy) { 808 if (TypeIdx != 1) 809 return UnableToLegalize; 810 811 unsigned DstReg = MI.getOperand(0).getReg(); 812 LLT DstTy = MRI.getType(DstReg); 813 if (!DstTy.isScalar()) 814 return UnableToLegalize; 815 816 unsigned NumOps = MI.getNumOperands(); 817 unsigned NumSrc = MI.getNumOperands() - 1; 818 unsigned PartSize = DstTy.getSizeInBits() / NumSrc; 819 820 unsigned Src1 = MI.getOperand(1).getReg(); 821 unsigned ResultReg = MIRBuilder.buildZExt(DstTy, Src1)->getOperand(0).getReg(); 822 823 for (unsigned I = 2; I != NumOps; ++I) { 824 const unsigned Offset = (I - 1) * PartSize; 825 826 unsigned SrcReg = MI.getOperand(I).getReg(); 827 assert(MRI.getType(SrcReg) == LLT::scalar(PartSize)); 828 829 auto ZextInput = MIRBuilder.buildZExt(DstTy, SrcReg); 830 831 unsigned NextResult = I + 1 == NumOps ? DstReg : 832 MRI.createGenericVirtualRegister(DstTy); 833 834 auto ShiftAmt = MIRBuilder.buildConstant(DstTy, Offset); 835 auto Shl = MIRBuilder.buildShl(DstTy, ZextInput, ShiftAmt); 836 MIRBuilder.buildOr(NextResult, ResultReg, Shl); 837 ResultReg = NextResult; 838 } 839 840 MI.eraseFromParent(); 841 return Legalized; 842 } 843 844 LegalizerHelper::LegalizeResult 845 LegalizerHelper::widenScalarUnmergeValues(MachineInstr &MI, unsigned TypeIdx, 846 LLT WideTy) { 847 if (TypeIdx != 0) 848 return UnableToLegalize; 849 850 unsigned NumDst = MI.getNumOperands() - 1; 851 unsigned SrcReg = MI.getOperand(NumDst).getReg(); 852 LLT SrcTy = MRI.getType(SrcReg); 853 if (!SrcTy.isScalar()) 854 return UnableToLegalize; 855 856 unsigned Dst0Reg = MI.getOperand(0).getReg(); 857 LLT DstTy = MRI.getType(Dst0Reg); 858 if (!DstTy.isScalar()) 859 return UnableToLegalize; 860 861 unsigned NewSrcSize = NumDst * WideTy.getSizeInBits(); 862 LLT NewSrcTy = LLT::scalar(NewSrcSize); 863 unsigned SizeDiff = WideTy.getSizeInBits() - DstTy.getSizeInBits(); 864 865 auto WideSrc = MIRBuilder.buildZExt(NewSrcTy, SrcReg); 866 867 for (unsigned I = 1; I != NumDst; ++I) { 868 auto ShiftAmt = MIRBuilder.buildConstant(NewSrcTy, SizeDiff * I); 869 auto Shl = MIRBuilder.buildShl(NewSrcTy, WideSrc, ShiftAmt); 870 WideSrc = MIRBuilder.buildOr(NewSrcTy, WideSrc, Shl); 871 } 872 873 Observer.changingInstr(MI); 874 875 MI.getOperand(NumDst).setReg(WideSrc->getOperand(0).getReg()); 876 for (unsigned I = 0; I != NumDst; ++I) 877 widenScalarDst(MI, WideTy, I); 878 879 Observer.changedInstr(MI); 880 881 return Legalized; 882 } 883 884 LegalizerHelper::LegalizeResult 885 LegalizerHelper::widenScalarExtract(MachineInstr &MI, unsigned TypeIdx, 886 LLT WideTy) { 887 unsigned DstReg = MI.getOperand(0).getReg(); 888 unsigned SrcReg = MI.getOperand(1).getReg(); 889 LLT SrcTy = MRI.getType(SrcReg); 890 891 LLT DstTy = MRI.getType(DstReg); 892 unsigned Offset = MI.getOperand(2).getImm(); 893 894 if (TypeIdx == 0) { 895 if (SrcTy.isVector() || DstTy.isVector()) 896 return UnableToLegalize; 897 898 SrcOp Src(SrcReg); 899 if (SrcTy.isPointer()) { 900 // Extracts from pointers can be handled only if they are really just 901 // simple integers. 902 const DataLayout &DL = MIRBuilder.getDataLayout(); 903 if (DL.isNonIntegralAddressSpace(SrcTy.getAddressSpace())) 904 return UnableToLegalize; 905 906 LLT SrcAsIntTy = LLT::scalar(SrcTy.getSizeInBits()); 907 Src = MIRBuilder.buildPtrToInt(SrcAsIntTy, Src); 908 SrcTy = SrcAsIntTy; 909 } 910 911 if (DstTy.isPointer()) 912 return UnableToLegalize; 913 914 if (Offset == 0) { 915 // Avoid a shift in the degenerate case. 916 MIRBuilder.buildTrunc(DstReg, 917 MIRBuilder.buildAnyExtOrTrunc(WideTy, Src)); 918 MI.eraseFromParent(); 919 return Legalized; 920 } 921 922 // Do a shift in the source type. 923 LLT ShiftTy = SrcTy; 924 if (WideTy.getSizeInBits() > SrcTy.getSizeInBits()) { 925 Src = MIRBuilder.buildAnyExt(WideTy, Src); 926 ShiftTy = WideTy; 927 } else if (WideTy.getSizeInBits() > SrcTy.getSizeInBits()) 928 return UnableToLegalize; 929 930 auto LShr = MIRBuilder.buildLShr( 931 ShiftTy, Src, MIRBuilder.buildConstant(ShiftTy, Offset)); 932 MIRBuilder.buildTrunc(DstReg, LShr); 933 MI.eraseFromParent(); 934 return Legalized; 935 } 936 937 if (!SrcTy.isVector()) 938 return UnableToLegalize; 939 940 if (DstTy != SrcTy.getElementType()) 941 return UnableToLegalize; 942 943 if (Offset % SrcTy.getScalarSizeInBits() != 0) 944 return UnableToLegalize; 945 946 Observer.changingInstr(MI); 947 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT); 948 949 MI.getOperand(2).setImm((WideTy.getSizeInBits() / SrcTy.getSizeInBits()) * 950 Offset); 951 widenScalarDst(MI, WideTy.getScalarType(), 0); 952 Observer.changedInstr(MI); 953 return Legalized; 954 } 955 956 LegalizerHelper::LegalizeResult 957 LegalizerHelper::widenScalarInsert(MachineInstr &MI, unsigned TypeIdx, 958 LLT WideTy) { 959 if (TypeIdx != 0) 960 return UnableToLegalize; 961 Observer.changingInstr(MI); 962 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT); 963 widenScalarDst(MI, WideTy); 964 Observer.changedInstr(MI); 965 return Legalized; 966 } 967 968 LegalizerHelper::LegalizeResult 969 LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) { 970 MIRBuilder.setInstr(MI); 971 972 switch (MI.getOpcode()) { 973 default: 974 return UnableToLegalize; 975 case TargetOpcode::G_EXTRACT: 976 return widenScalarExtract(MI, TypeIdx, WideTy); 977 case TargetOpcode::G_INSERT: 978 return widenScalarInsert(MI, TypeIdx, WideTy); 979 case TargetOpcode::G_MERGE_VALUES: 980 return widenScalarMergeValues(MI, TypeIdx, WideTy); 981 case TargetOpcode::G_UNMERGE_VALUES: 982 return widenScalarUnmergeValues(MI, TypeIdx, WideTy); 983 case TargetOpcode::G_UADDO: 984 case TargetOpcode::G_USUBO: { 985 if (TypeIdx == 1) 986 return UnableToLegalize; // TODO 987 auto LHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, {WideTy}, 988 {MI.getOperand(2).getReg()}); 989 auto RHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, {WideTy}, 990 {MI.getOperand(3).getReg()}); 991 unsigned Opcode = MI.getOpcode() == TargetOpcode::G_UADDO 992 ? TargetOpcode::G_ADD 993 : TargetOpcode::G_SUB; 994 // Do the arithmetic in the larger type. 995 auto NewOp = MIRBuilder.buildInstr(Opcode, {WideTy}, {LHSZext, RHSZext}); 996 LLT OrigTy = MRI.getType(MI.getOperand(0).getReg()); 997 APInt Mask = APInt::getAllOnesValue(OrigTy.getSizeInBits()); 998 auto AndOp = MIRBuilder.buildInstr( 999 TargetOpcode::G_AND, {WideTy}, 1000 {NewOp, MIRBuilder.buildConstant(WideTy, Mask.getZExtValue())}); 1001 // There is no overflow if the AndOp is the same as NewOp. 1002 MIRBuilder.buildICmp(CmpInst::ICMP_NE, MI.getOperand(1).getReg(), NewOp, 1003 AndOp); 1004 // Now trunc the NewOp to the original result. 1005 MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), NewOp); 1006 MI.eraseFromParent(); 1007 return Legalized; 1008 } 1009 case TargetOpcode::G_CTTZ: 1010 case TargetOpcode::G_CTTZ_ZERO_UNDEF: 1011 case TargetOpcode::G_CTLZ: 1012 case TargetOpcode::G_CTLZ_ZERO_UNDEF: 1013 case TargetOpcode::G_CTPOP: { 1014 if (TypeIdx == 0) { 1015 Observer.changingInstr(MI); 1016 widenScalarDst(MI, WideTy, 0); 1017 Observer.changedInstr(MI); 1018 return Legalized; 1019 } 1020 1021 unsigned SrcReg = MI.getOperand(1).getReg(); 1022 1023 // First ZEXT the input. 1024 auto MIBSrc = MIRBuilder.buildZExt(WideTy, SrcReg); 1025 LLT CurTy = MRI.getType(SrcReg); 1026 if (MI.getOpcode() == TargetOpcode::G_CTTZ) { 1027 // The count is the same in the larger type except if the original 1028 // value was zero. This can be handled by setting the bit just off 1029 // the top of the original type. 1030 auto TopBit = 1031 APInt::getOneBitSet(WideTy.getSizeInBits(), CurTy.getSizeInBits()); 1032 MIBSrc = MIRBuilder.buildOr( 1033 WideTy, MIBSrc, MIRBuilder.buildConstant(WideTy, TopBit)); 1034 } 1035 1036 // Perform the operation at the larger size. 1037 auto MIBNewOp = MIRBuilder.buildInstr(MI.getOpcode(), {WideTy}, {MIBSrc}); 1038 // This is already the correct result for CTPOP and CTTZs 1039 if (MI.getOpcode() == TargetOpcode::G_CTLZ || 1040 MI.getOpcode() == TargetOpcode::G_CTLZ_ZERO_UNDEF) { 1041 // The correct result is NewOp - (Difference in widety and current ty). 1042 unsigned SizeDiff = WideTy.getSizeInBits() - CurTy.getSizeInBits(); 1043 MIBNewOp = MIRBuilder.buildInstr( 1044 TargetOpcode::G_SUB, {WideTy}, 1045 {MIBNewOp, MIRBuilder.buildConstant(WideTy, SizeDiff)}); 1046 } 1047 1048 MIRBuilder.buildZExtOrTrunc(MI.getOperand(0), MIBNewOp); 1049 MI.eraseFromParent(); 1050 return Legalized; 1051 } 1052 case TargetOpcode::G_BSWAP: { 1053 Observer.changingInstr(MI); 1054 unsigned DstReg = MI.getOperand(0).getReg(); 1055 1056 unsigned ShrReg = MRI.createGenericVirtualRegister(WideTy); 1057 unsigned DstExt = MRI.createGenericVirtualRegister(WideTy); 1058 unsigned ShiftAmtReg = MRI.createGenericVirtualRegister(WideTy); 1059 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT); 1060 1061 MI.getOperand(0).setReg(DstExt); 1062 1063 MIRBuilder.setInsertPt(MIRBuilder.getMBB(), ++MIRBuilder.getInsertPt()); 1064 1065 LLT Ty = MRI.getType(DstReg); 1066 unsigned DiffBits = WideTy.getScalarSizeInBits() - Ty.getScalarSizeInBits(); 1067 MIRBuilder.buildConstant(ShiftAmtReg, DiffBits); 1068 MIRBuilder.buildInstr(TargetOpcode::G_LSHR) 1069 .addDef(ShrReg) 1070 .addUse(DstExt) 1071 .addUse(ShiftAmtReg); 1072 1073 MIRBuilder.buildTrunc(DstReg, ShrReg); 1074 Observer.changedInstr(MI); 1075 return Legalized; 1076 } 1077 case TargetOpcode::G_ADD: 1078 case TargetOpcode::G_AND: 1079 case TargetOpcode::G_MUL: 1080 case TargetOpcode::G_OR: 1081 case TargetOpcode::G_XOR: 1082 case TargetOpcode::G_SUB: 1083 // Perform operation at larger width (any extension is fines here, high bits 1084 // don't affect the result) and then truncate the result back to the 1085 // original type. 1086 Observer.changingInstr(MI); 1087 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT); 1088 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT); 1089 widenScalarDst(MI, WideTy); 1090 Observer.changedInstr(MI); 1091 return Legalized; 1092 1093 case TargetOpcode::G_SHL: 1094 Observer.changingInstr(MI); 1095 1096 if (TypeIdx == 0) { 1097 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT); 1098 widenScalarDst(MI, WideTy); 1099 } else { 1100 assert(TypeIdx == 1); 1101 // The "number of bits to shift" operand must preserve its value as an 1102 // unsigned integer: 1103 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT); 1104 } 1105 1106 Observer.changedInstr(MI); 1107 return Legalized; 1108 1109 case TargetOpcode::G_SDIV: 1110 case TargetOpcode::G_SREM: 1111 Observer.changingInstr(MI); 1112 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT); 1113 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT); 1114 widenScalarDst(MI, WideTy); 1115 Observer.changedInstr(MI); 1116 return Legalized; 1117 1118 case TargetOpcode::G_ASHR: 1119 case TargetOpcode::G_LSHR: 1120 Observer.changingInstr(MI); 1121 1122 if (TypeIdx == 0) { 1123 unsigned CvtOp = MI.getOpcode() == TargetOpcode::G_ASHR ? 1124 TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT; 1125 1126 widenScalarSrc(MI, WideTy, 1, CvtOp); 1127 widenScalarDst(MI, WideTy); 1128 } else { 1129 assert(TypeIdx == 1); 1130 // The "number of bits to shift" operand must preserve its value as an 1131 // unsigned integer: 1132 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT); 1133 } 1134 1135 Observer.changedInstr(MI); 1136 return Legalized; 1137 case TargetOpcode::G_UDIV: 1138 case TargetOpcode::G_UREM: 1139 Observer.changingInstr(MI); 1140 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT); 1141 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT); 1142 widenScalarDst(MI, WideTy); 1143 Observer.changedInstr(MI); 1144 return Legalized; 1145 1146 case TargetOpcode::G_SELECT: 1147 Observer.changingInstr(MI); 1148 if (TypeIdx == 0) { 1149 // Perform operation at larger width (any extension is fine here, high 1150 // bits don't affect the result) and then truncate the result back to the 1151 // original type. 1152 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT); 1153 widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_ANYEXT); 1154 widenScalarDst(MI, WideTy); 1155 } else { 1156 bool IsVec = MRI.getType(MI.getOperand(1).getReg()).isVector(); 1157 // Explicit extension is required here since high bits affect the result. 1158 widenScalarSrc(MI, WideTy, 1, MIRBuilder.getBoolExtOp(IsVec, false)); 1159 } 1160 Observer.changedInstr(MI); 1161 return Legalized; 1162 1163 case TargetOpcode::G_FPTOSI: 1164 case TargetOpcode::G_FPTOUI: 1165 if (TypeIdx != 0) 1166 return UnableToLegalize; 1167 Observer.changingInstr(MI); 1168 widenScalarDst(MI, WideTy); 1169 Observer.changedInstr(MI); 1170 return Legalized; 1171 1172 case TargetOpcode::G_SITOFP: 1173 if (TypeIdx != 1) 1174 return UnableToLegalize; 1175 Observer.changingInstr(MI); 1176 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT); 1177 Observer.changedInstr(MI); 1178 return Legalized; 1179 1180 case TargetOpcode::G_UITOFP: 1181 if (TypeIdx != 1) 1182 return UnableToLegalize; 1183 Observer.changingInstr(MI); 1184 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT); 1185 Observer.changedInstr(MI); 1186 return Legalized; 1187 1188 case TargetOpcode::G_LOAD: 1189 case TargetOpcode::G_SEXTLOAD: 1190 case TargetOpcode::G_ZEXTLOAD: 1191 Observer.changingInstr(MI); 1192 widenScalarDst(MI, WideTy); 1193 Observer.changedInstr(MI); 1194 return Legalized; 1195 1196 case TargetOpcode::G_STORE: { 1197 if (TypeIdx != 0) 1198 return UnableToLegalize; 1199 1200 LLT Ty = MRI.getType(MI.getOperand(0).getReg()); 1201 if (!isPowerOf2_32(Ty.getSizeInBits())) 1202 return UnableToLegalize; 1203 1204 Observer.changingInstr(MI); 1205 1206 unsigned ExtType = Ty.getScalarSizeInBits() == 1 ? 1207 TargetOpcode::G_ZEXT : TargetOpcode::G_ANYEXT; 1208 widenScalarSrc(MI, WideTy, 0, ExtType); 1209 1210 Observer.changedInstr(MI); 1211 return Legalized; 1212 } 1213 case TargetOpcode::G_CONSTANT: { 1214 MachineOperand &SrcMO = MI.getOperand(1); 1215 LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext(); 1216 const APInt &Val = SrcMO.getCImm()->getValue().sext(WideTy.getSizeInBits()); 1217 Observer.changingInstr(MI); 1218 SrcMO.setCImm(ConstantInt::get(Ctx, Val)); 1219 1220 widenScalarDst(MI, WideTy); 1221 Observer.changedInstr(MI); 1222 return Legalized; 1223 } 1224 case TargetOpcode::G_FCONSTANT: { 1225 MachineOperand &SrcMO = MI.getOperand(1); 1226 LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext(); 1227 APFloat Val = SrcMO.getFPImm()->getValueAPF(); 1228 bool LosesInfo; 1229 switch (WideTy.getSizeInBits()) { 1230 case 32: 1231 Val.convert(APFloat::IEEEsingle(), APFloat::rmNearestTiesToEven, 1232 &LosesInfo); 1233 break; 1234 case 64: 1235 Val.convert(APFloat::IEEEdouble(), APFloat::rmNearestTiesToEven, 1236 &LosesInfo); 1237 break; 1238 default: 1239 return UnableToLegalize; 1240 } 1241 1242 assert(!LosesInfo && "extend should always be lossless"); 1243 1244 Observer.changingInstr(MI); 1245 SrcMO.setFPImm(ConstantFP::get(Ctx, Val)); 1246 1247 widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC); 1248 Observer.changedInstr(MI); 1249 return Legalized; 1250 } 1251 case TargetOpcode::G_IMPLICIT_DEF: { 1252 Observer.changingInstr(MI); 1253 widenScalarDst(MI, WideTy); 1254 Observer.changedInstr(MI); 1255 return Legalized; 1256 } 1257 case TargetOpcode::G_BRCOND: 1258 Observer.changingInstr(MI); 1259 widenScalarSrc(MI, WideTy, 0, MIRBuilder.getBoolExtOp(false, false)); 1260 Observer.changedInstr(MI); 1261 return Legalized; 1262 1263 case TargetOpcode::G_FCMP: 1264 Observer.changingInstr(MI); 1265 if (TypeIdx == 0) 1266 widenScalarDst(MI, WideTy); 1267 else { 1268 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_FPEXT); 1269 widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_FPEXT); 1270 } 1271 Observer.changedInstr(MI); 1272 return Legalized; 1273 1274 case TargetOpcode::G_ICMP: 1275 Observer.changingInstr(MI); 1276 if (TypeIdx == 0) 1277 widenScalarDst(MI, WideTy); 1278 else { 1279 unsigned ExtOpcode = CmpInst::isSigned(static_cast<CmpInst::Predicate>( 1280 MI.getOperand(1).getPredicate())) 1281 ? TargetOpcode::G_SEXT 1282 : TargetOpcode::G_ZEXT; 1283 widenScalarSrc(MI, WideTy, 2, ExtOpcode); 1284 widenScalarSrc(MI, WideTy, 3, ExtOpcode); 1285 } 1286 Observer.changedInstr(MI); 1287 return Legalized; 1288 1289 case TargetOpcode::G_GEP: 1290 assert(TypeIdx == 1 && "unable to legalize pointer of GEP"); 1291 Observer.changingInstr(MI); 1292 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT); 1293 Observer.changedInstr(MI); 1294 return Legalized; 1295 1296 case TargetOpcode::G_PHI: { 1297 assert(TypeIdx == 0 && "Expecting only Idx 0"); 1298 1299 Observer.changingInstr(MI); 1300 for (unsigned I = 1; I < MI.getNumOperands(); I += 2) { 1301 MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB(); 1302 MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator()); 1303 widenScalarSrc(MI, WideTy, I, TargetOpcode::G_ANYEXT); 1304 } 1305 1306 MachineBasicBlock &MBB = *MI.getParent(); 1307 MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI()); 1308 widenScalarDst(MI, WideTy); 1309 Observer.changedInstr(MI); 1310 return Legalized; 1311 } 1312 case TargetOpcode::G_EXTRACT_VECTOR_ELT: { 1313 if (TypeIdx == 0) { 1314 unsigned VecReg = MI.getOperand(1).getReg(); 1315 LLT VecTy = MRI.getType(VecReg); 1316 Observer.changingInstr(MI); 1317 1318 widenScalarSrc(MI, LLT::vector(VecTy.getNumElements(), 1319 WideTy.getSizeInBits()), 1320 1, TargetOpcode::G_SEXT); 1321 1322 widenScalarDst(MI, WideTy, 0); 1323 Observer.changedInstr(MI); 1324 return Legalized; 1325 } 1326 1327 if (TypeIdx != 2) 1328 return UnableToLegalize; 1329 Observer.changingInstr(MI); 1330 widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT); 1331 Observer.changedInstr(MI); 1332 return Legalized; 1333 } 1334 case TargetOpcode::G_FADD: 1335 case TargetOpcode::G_FMUL: 1336 case TargetOpcode::G_FSUB: 1337 case TargetOpcode::G_FMA: 1338 case TargetOpcode::G_FNEG: 1339 case TargetOpcode::G_FABS: 1340 case TargetOpcode::G_FCANONICALIZE: 1341 case TargetOpcode::G_FDIV: 1342 case TargetOpcode::G_FREM: 1343 case TargetOpcode::G_FCEIL: 1344 case TargetOpcode::G_FFLOOR: 1345 case TargetOpcode::G_FCOS: 1346 case TargetOpcode::G_FSIN: 1347 case TargetOpcode::G_FLOG10: 1348 case TargetOpcode::G_FLOG: 1349 case TargetOpcode::G_FLOG2: 1350 case TargetOpcode::G_FSQRT: 1351 case TargetOpcode::G_FEXP: 1352 case TargetOpcode::G_FEXP2: 1353 assert(TypeIdx == 0); 1354 Observer.changingInstr(MI); 1355 1356 for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) 1357 widenScalarSrc(MI, WideTy, I, TargetOpcode::G_FPEXT); 1358 1359 widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC); 1360 Observer.changedInstr(MI); 1361 return Legalized; 1362 case TargetOpcode::G_INTTOPTR: 1363 if (TypeIdx != 1) 1364 return UnableToLegalize; 1365 1366 Observer.changingInstr(MI); 1367 widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT); 1368 Observer.changedInstr(MI); 1369 return Legalized; 1370 case TargetOpcode::G_PTRTOINT: 1371 if (TypeIdx != 0) 1372 return UnableToLegalize; 1373 1374 Observer.changingInstr(MI); 1375 widenScalarDst(MI, WideTy, 0); 1376 Observer.changedInstr(MI); 1377 return Legalized; 1378 } 1379 } 1380 1381 LegalizerHelper::LegalizeResult 1382 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) { 1383 using namespace TargetOpcode; 1384 MIRBuilder.setInstr(MI); 1385 1386 switch(MI.getOpcode()) { 1387 default: 1388 return UnableToLegalize; 1389 case TargetOpcode::G_SREM: 1390 case TargetOpcode::G_UREM: { 1391 unsigned QuotReg = MRI.createGenericVirtualRegister(Ty); 1392 MIRBuilder.buildInstr(MI.getOpcode() == G_SREM ? G_SDIV : G_UDIV) 1393 .addDef(QuotReg) 1394 .addUse(MI.getOperand(1).getReg()) 1395 .addUse(MI.getOperand(2).getReg()); 1396 1397 unsigned ProdReg = MRI.createGenericVirtualRegister(Ty); 1398 MIRBuilder.buildMul(ProdReg, QuotReg, MI.getOperand(2).getReg()); 1399 MIRBuilder.buildSub(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(), 1400 ProdReg); 1401 MI.eraseFromParent(); 1402 return Legalized; 1403 } 1404 case TargetOpcode::G_SMULO: 1405 case TargetOpcode::G_UMULO: { 1406 // Generate G_UMULH/G_SMULH to check for overflow and a normal G_MUL for the 1407 // result. 1408 unsigned Res = MI.getOperand(0).getReg(); 1409 unsigned Overflow = MI.getOperand(1).getReg(); 1410 unsigned LHS = MI.getOperand(2).getReg(); 1411 unsigned RHS = MI.getOperand(3).getReg(); 1412 1413 MIRBuilder.buildMul(Res, LHS, RHS); 1414 1415 unsigned Opcode = MI.getOpcode() == TargetOpcode::G_SMULO 1416 ? TargetOpcode::G_SMULH 1417 : TargetOpcode::G_UMULH; 1418 1419 unsigned HiPart = MRI.createGenericVirtualRegister(Ty); 1420 MIRBuilder.buildInstr(Opcode) 1421 .addDef(HiPart) 1422 .addUse(LHS) 1423 .addUse(RHS); 1424 1425 unsigned Zero = MRI.createGenericVirtualRegister(Ty); 1426 MIRBuilder.buildConstant(Zero, 0); 1427 1428 // For *signed* multiply, overflow is detected by checking: 1429 // (hi != (lo >> bitwidth-1)) 1430 if (Opcode == TargetOpcode::G_SMULH) { 1431 unsigned Shifted = MRI.createGenericVirtualRegister(Ty); 1432 unsigned ShiftAmt = MRI.createGenericVirtualRegister(Ty); 1433 MIRBuilder.buildConstant(ShiftAmt, Ty.getSizeInBits() - 1); 1434 MIRBuilder.buildInstr(TargetOpcode::G_ASHR) 1435 .addDef(Shifted) 1436 .addUse(Res) 1437 .addUse(ShiftAmt); 1438 MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Shifted); 1439 } else { 1440 MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Zero); 1441 } 1442 MI.eraseFromParent(); 1443 return Legalized; 1444 } 1445 case TargetOpcode::G_FNEG: { 1446 // TODO: Handle vector types once we are able to 1447 // represent them. 1448 if (Ty.isVector()) 1449 return UnableToLegalize; 1450 unsigned Res = MI.getOperand(0).getReg(); 1451 Type *ZeroTy; 1452 LLVMContext &Ctx = MIRBuilder.getMF().getFunction().getContext(); 1453 switch (Ty.getSizeInBits()) { 1454 case 16: 1455 ZeroTy = Type::getHalfTy(Ctx); 1456 break; 1457 case 32: 1458 ZeroTy = Type::getFloatTy(Ctx); 1459 break; 1460 case 64: 1461 ZeroTy = Type::getDoubleTy(Ctx); 1462 break; 1463 case 128: 1464 ZeroTy = Type::getFP128Ty(Ctx); 1465 break; 1466 default: 1467 llvm_unreachable("unexpected floating-point type"); 1468 } 1469 ConstantFP &ZeroForNegation = 1470 *cast<ConstantFP>(ConstantFP::getZeroValueForNegation(ZeroTy)); 1471 auto Zero = MIRBuilder.buildFConstant(Ty, ZeroForNegation); 1472 MIRBuilder.buildInstr(TargetOpcode::G_FSUB) 1473 .addDef(Res) 1474 .addUse(Zero->getOperand(0).getReg()) 1475 .addUse(MI.getOperand(1).getReg()); 1476 MI.eraseFromParent(); 1477 return Legalized; 1478 } 1479 case TargetOpcode::G_FSUB: { 1480 // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)). 1481 // First, check if G_FNEG is marked as Lower. If so, we may 1482 // end up with an infinite loop as G_FSUB is used to legalize G_FNEG. 1483 if (LI.getAction({G_FNEG, {Ty}}).Action == Lower) 1484 return UnableToLegalize; 1485 unsigned Res = MI.getOperand(0).getReg(); 1486 unsigned LHS = MI.getOperand(1).getReg(); 1487 unsigned RHS = MI.getOperand(2).getReg(); 1488 unsigned Neg = MRI.createGenericVirtualRegister(Ty); 1489 MIRBuilder.buildInstr(TargetOpcode::G_FNEG).addDef(Neg).addUse(RHS); 1490 MIRBuilder.buildInstr(TargetOpcode::G_FADD) 1491 .addDef(Res) 1492 .addUse(LHS) 1493 .addUse(Neg); 1494 MI.eraseFromParent(); 1495 return Legalized; 1496 } 1497 case TargetOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: { 1498 unsigned OldValRes = MI.getOperand(0).getReg(); 1499 unsigned SuccessRes = MI.getOperand(1).getReg(); 1500 unsigned Addr = MI.getOperand(2).getReg(); 1501 unsigned CmpVal = MI.getOperand(3).getReg(); 1502 unsigned NewVal = MI.getOperand(4).getReg(); 1503 MIRBuilder.buildAtomicCmpXchg(OldValRes, Addr, CmpVal, NewVal, 1504 **MI.memoperands_begin()); 1505 MIRBuilder.buildICmp(CmpInst::ICMP_EQ, SuccessRes, OldValRes, CmpVal); 1506 MI.eraseFromParent(); 1507 return Legalized; 1508 } 1509 case TargetOpcode::G_LOAD: 1510 case TargetOpcode::G_SEXTLOAD: 1511 case TargetOpcode::G_ZEXTLOAD: { 1512 // Lower to a memory-width G_LOAD and a G_SEXT/G_ZEXT/G_ANYEXT 1513 unsigned DstReg = MI.getOperand(0).getReg(); 1514 unsigned PtrReg = MI.getOperand(1).getReg(); 1515 LLT DstTy = MRI.getType(DstReg); 1516 auto &MMO = **MI.memoperands_begin(); 1517 1518 if (DstTy.getSizeInBits() == MMO.getSize() /* in bytes */ * 8) { 1519 // In the case of G_LOAD, this was a non-extending load already and we're 1520 // about to lower to the same instruction. 1521 if (MI.getOpcode() == TargetOpcode::G_LOAD) 1522 return UnableToLegalize; 1523 MIRBuilder.buildLoad(DstReg, PtrReg, MMO); 1524 MI.eraseFromParent(); 1525 return Legalized; 1526 } 1527 1528 if (DstTy.isScalar()) { 1529 unsigned TmpReg = MRI.createGenericVirtualRegister( 1530 LLT::scalar(MMO.getSize() /* in bytes */ * 8)); 1531 MIRBuilder.buildLoad(TmpReg, PtrReg, MMO); 1532 switch (MI.getOpcode()) { 1533 default: 1534 llvm_unreachable("Unexpected opcode"); 1535 case TargetOpcode::G_LOAD: 1536 MIRBuilder.buildAnyExt(DstReg, TmpReg); 1537 break; 1538 case TargetOpcode::G_SEXTLOAD: 1539 MIRBuilder.buildSExt(DstReg, TmpReg); 1540 break; 1541 case TargetOpcode::G_ZEXTLOAD: 1542 MIRBuilder.buildZExt(DstReg, TmpReg); 1543 break; 1544 } 1545 MI.eraseFromParent(); 1546 return Legalized; 1547 } 1548 1549 return UnableToLegalize; 1550 } 1551 case TargetOpcode::G_CTLZ_ZERO_UNDEF: 1552 case TargetOpcode::G_CTTZ_ZERO_UNDEF: 1553 case TargetOpcode::G_CTLZ: 1554 case TargetOpcode::G_CTTZ: 1555 case TargetOpcode::G_CTPOP: 1556 return lowerBitCount(MI, TypeIdx, Ty); 1557 case G_UADDO: { 1558 unsigned Res = MI.getOperand(0).getReg(); 1559 unsigned CarryOut = MI.getOperand(1).getReg(); 1560 unsigned LHS = MI.getOperand(2).getReg(); 1561 unsigned RHS = MI.getOperand(3).getReg(); 1562 1563 MIRBuilder.buildAdd(Res, LHS, RHS); 1564 MIRBuilder.buildICmp(CmpInst::ICMP_ULT, CarryOut, Res, RHS); 1565 1566 MI.eraseFromParent(); 1567 return Legalized; 1568 } 1569 case G_UADDE: { 1570 unsigned Res = MI.getOperand(0).getReg(); 1571 unsigned CarryOut = MI.getOperand(1).getReg(); 1572 unsigned LHS = MI.getOperand(2).getReg(); 1573 unsigned RHS = MI.getOperand(3).getReg(); 1574 unsigned CarryIn = MI.getOperand(4).getReg(); 1575 1576 unsigned TmpRes = MRI.createGenericVirtualRegister(Ty); 1577 unsigned ZExtCarryIn = MRI.createGenericVirtualRegister(Ty); 1578 1579 MIRBuilder.buildAdd(TmpRes, LHS, RHS); 1580 MIRBuilder.buildZExt(ZExtCarryIn, CarryIn); 1581 MIRBuilder.buildAdd(Res, TmpRes, ZExtCarryIn); 1582 MIRBuilder.buildICmp(CmpInst::ICMP_ULT, CarryOut, Res, LHS); 1583 1584 MI.eraseFromParent(); 1585 return Legalized; 1586 } 1587 case G_USUBO: { 1588 unsigned Res = MI.getOperand(0).getReg(); 1589 unsigned BorrowOut = MI.getOperand(1).getReg(); 1590 unsigned LHS = MI.getOperand(2).getReg(); 1591 unsigned RHS = MI.getOperand(3).getReg(); 1592 1593 MIRBuilder.buildSub(Res, LHS, RHS); 1594 MIRBuilder.buildICmp(CmpInst::ICMP_ULT, BorrowOut, LHS, RHS); 1595 1596 MI.eraseFromParent(); 1597 return Legalized; 1598 } 1599 case G_USUBE: { 1600 unsigned Res = MI.getOperand(0).getReg(); 1601 unsigned BorrowOut = MI.getOperand(1).getReg(); 1602 unsigned LHS = MI.getOperand(2).getReg(); 1603 unsigned RHS = MI.getOperand(3).getReg(); 1604 unsigned BorrowIn = MI.getOperand(4).getReg(); 1605 1606 unsigned TmpRes = MRI.createGenericVirtualRegister(Ty); 1607 unsigned ZExtBorrowIn = MRI.createGenericVirtualRegister(Ty); 1608 unsigned LHS_EQ_RHS = MRI.createGenericVirtualRegister(LLT::scalar(1)); 1609 unsigned LHS_ULT_RHS = MRI.createGenericVirtualRegister(LLT::scalar(1)); 1610 1611 MIRBuilder.buildSub(TmpRes, LHS, RHS); 1612 MIRBuilder.buildZExt(ZExtBorrowIn, BorrowIn); 1613 MIRBuilder.buildSub(Res, TmpRes, ZExtBorrowIn); 1614 MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LHS_EQ_RHS, LHS, RHS); 1615 MIRBuilder.buildICmp(CmpInst::ICMP_ULT, LHS_ULT_RHS, LHS, RHS); 1616 MIRBuilder.buildSelect(BorrowOut, LHS_EQ_RHS, BorrowIn, LHS_ULT_RHS); 1617 1618 MI.eraseFromParent(); 1619 return Legalized; 1620 } 1621 } 1622 } 1623 1624 LegalizerHelper::LegalizeResult LegalizerHelper::fewerElementsVectorImplicitDef( 1625 MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy) { 1626 SmallVector<unsigned, 2> DstRegs; 1627 1628 unsigned NarrowSize = NarrowTy.getSizeInBits(); 1629 unsigned DstReg = MI.getOperand(0).getReg(); 1630 unsigned Size = MRI.getType(DstReg).getSizeInBits(); 1631 int NumParts = Size / NarrowSize; 1632 // FIXME: Don't know how to handle the situation where the small vectors 1633 // aren't all the same size yet. 1634 if (Size % NarrowSize != 0) 1635 return UnableToLegalize; 1636 1637 for (int i = 0; i < NumParts; ++i) { 1638 unsigned TmpReg = MRI.createGenericVirtualRegister(NarrowTy); 1639 MIRBuilder.buildUndef(TmpReg); 1640 DstRegs.push_back(TmpReg); 1641 } 1642 1643 if (NarrowTy.isVector()) 1644 MIRBuilder.buildConcatVectors(DstReg, DstRegs); 1645 else 1646 MIRBuilder.buildBuildVector(DstReg, DstRegs); 1647 1648 MI.eraseFromParent(); 1649 return Legalized; 1650 } 1651 1652 LegalizerHelper::LegalizeResult 1653 LegalizerHelper::fewerElementsVectorBasic(MachineInstr &MI, unsigned TypeIdx, 1654 LLT NarrowTy) { 1655 const unsigned Opc = MI.getOpcode(); 1656 const unsigned NumOps = MI.getNumOperands() - 1; 1657 const unsigned NarrowSize = NarrowTy.getSizeInBits(); 1658 const unsigned DstReg = MI.getOperand(0).getReg(); 1659 const unsigned Flags = MI.getFlags(); 1660 const LLT DstTy = MRI.getType(DstReg); 1661 const unsigned Size = DstTy.getSizeInBits(); 1662 const int NumParts = Size / NarrowSize; 1663 const LLT EltTy = DstTy.getElementType(); 1664 const unsigned EltSize = EltTy.getSizeInBits(); 1665 const unsigned BitsForNumParts = NarrowSize * NumParts; 1666 1667 // Check if we have any leftovers. If we do, then only handle the case where 1668 // the leftover is one element. 1669 if (BitsForNumParts != Size && BitsForNumParts + EltSize != Size) 1670 return UnableToLegalize; 1671 1672 if (BitsForNumParts != Size) { 1673 unsigned AccumDstReg = MRI.createGenericVirtualRegister(DstTy); 1674 MIRBuilder.buildUndef(AccumDstReg); 1675 1676 // Handle the pieces which evenly divide into the requested type with 1677 // extract/op/insert sequence. 1678 for (unsigned Offset = 0; Offset < BitsForNumParts; Offset += NarrowSize) { 1679 SmallVector<SrcOp, 4> SrcOps; 1680 for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) { 1681 unsigned PartOpReg = MRI.createGenericVirtualRegister(NarrowTy); 1682 MIRBuilder.buildExtract(PartOpReg, MI.getOperand(I).getReg(), Offset); 1683 SrcOps.push_back(PartOpReg); 1684 } 1685 1686 unsigned PartDstReg = MRI.createGenericVirtualRegister(NarrowTy); 1687 MIRBuilder.buildInstr(Opc, {PartDstReg}, SrcOps, Flags); 1688 1689 unsigned PartInsertReg = MRI.createGenericVirtualRegister(DstTy); 1690 MIRBuilder.buildInsert(PartInsertReg, AccumDstReg, PartDstReg, Offset); 1691 AccumDstReg = PartInsertReg; 1692 } 1693 1694 // Handle the remaining element sized leftover piece. 1695 SmallVector<SrcOp, 4> SrcOps; 1696 for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) { 1697 unsigned PartOpReg = MRI.createGenericVirtualRegister(EltTy); 1698 MIRBuilder.buildExtract(PartOpReg, MI.getOperand(I).getReg(), 1699 BitsForNumParts); 1700 SrcOps.push_back(PartOpReg); 1701 } 1702 1703 unsigned PartDstReg = MRI.createGenericVirtualRegister(EltTy); 1704 MIRBuilder.buildInstr(Opc, {PartDstReg}, SrcOps, Flags); 1705 MIRBuilder.buildInsert(DstReg, AccumDstReg, PartDstReg, BitsForNumParts); 1706 MI.eraseFromParent(); 1707 1708 return Legalized; 1709 } 1710 1711 SmallVector<unsigned, 2> DstRegs, Src0Regs, Src1Regs, Src2Regs; 1712 1713 extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src0Regs); 1714 1715 if (NumOps >= 2) 1716 extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src1Regs); 1717 1718 if (NumOps >= 3) 1719 extractParts(MI.getOperand(3).getReg(), NarrowTy, NumParts, Src2Regs); 1720 1721 for (int i = 0; i < NumParts; ++i) { 1722 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 1723 1724 if (NumOps == 1) 1725 MIRBuilder.buildInstr(Opc, {DstReg}, {Src0Regs[i]}, Flags); 1726 else if (NumOps == 2) { 1727 MIRBuilder.buildInstr(Opc, {DstReg}, {Src0Regs[i], Src1Regs[i]}, Flags); 1728 } else if (NumOps == 3) { 1729 MIRBuilder.buildInstr(Opc, {DstReg}, 1730 {Src0Regs[i], Src1Regs[i], Src2Regs[i]}, Flags); 1731 } 1732 1733 DstRegs.push_back(DstReg); 1734 } 1735 1736 if (NarrowTy.isVector()) 1737 MIRBuilder.buildConcatVectors(DstReg, DstRegs); 1738 else 1739 MIRBuilder.buildBuildVector(DstReg, DstRegs); 1740 1741 MI.eraseFromParent(); 1742 return Legalized; 1743 } 1744 1745 // Handle splitting vector operations which need to have the same number of 1746 // elements in each type index, but each type index may have a different element 1747 // type. 1748 // 1749 // e.g. <4 x s64> = G_SHL <4 x s64>, <4 x s32> -> 1750 // <2 x s64> = G_SHL <2 x s64>, <2 x s32> 1751 // <2 x s64> = G_SHL <2 x s64>, <2 x s32> 1752 // 1753 // Also handles some irregular breakdown cases, e.g. 1754 // e.g. <3 x s64> = G_SHL <3 x s64>, <3 x s32> -> 1755 // <2 x s64> = G_SHL <2 x s64>, <2 x s32> 1756 // s64 = G_SHL s64, s32 1757 LegalizerHelper::LegalizeResult 1758 LegalizerHelper::fewerElementsVectorMultiEltType( 1759 MachineInstr &MI, unsigned TypeIdx, LLT NarrowTyArg) { 1760 if (TypeIdx != 0) 1761 return UnableToLegalize; 1762 1763 const LLT NarrowTy0 = NarrowTyArg; 1764 const unsigned NewNumElts = 1765 NarrowTy0.isVector() ? NarrowTy0.getNumElements() : 1; 1766 1767 const unsigned DstReg = MI.getOperand(0).getReg(); 1768 LLT DstTy = MRI.getType(DstReg); 1769 LLT LeftoverTy0; 1770 1771 int NumParts, NumLeftover; 1772 // All of the operands need to have the same number of elements, so if we can 1773 // determine a type breakdown for the result type, we can for all of the 1774 // source types. 1775 std::tie(NumParts, NumLeftover) 1776 = getNarrowTypeBreakDown(DstTy, NarrowTy0, LeftoverTy0); 1777 if (NumParts < 0) 1778 return UnableToLegalize; 1779 1780 SmallVector<MachineInstrBuilder, 4> NewInsts; 1781 1782 SmallVector<unsigned, 4> DstRegs, LeftoverDstRegs; 1783 SmallVector<unsigned, 4> PartRegs, LeftoverRegs; 1784 1785 for (unsigned I = 1, E = MI.getNumOperands(); I != E; ++I) { 1786 LLT LeftoverTy; 1787 unsigned SrcReg = MI.getOperand(I).getReg(); 1788 LLT SrcTyI = MRI.getType(SrcReg); 1789 LLT NarrowTyI = LLT::scalarOrVector(NewNumElts, SrcTyI.getScalarType()); 1790 LLT LeftoverTyI; 1791 1792 // Split this operand into the requested typed registers, and any leftover 1793 // required to reproduce the original type. 1794 if (!extractParts(SrcReg, SrcTyI, NarrowTyI, LeftoverTyI, PartRegs, 1795 LeftoverRegs)) 1796 return UnableToLegalize; 1797 1798 if (I == 1) { 1799 // For the first operand, create an instruction for each part and setup 1800 // the result. 1801 for (unsigned PartReg : PartRegs) { 1802 unsigned PartDstReg = MRI.createGenericVirtualRegister(NarrowTy0); 1803 NewInsts.push_back(MIRBuilder.buildInstrNoInsert(MI.getOpcode()) 1804 .addDef(PartDstReg) 1805 .addUse(PartReg)); 1806 DstRegs.push_back(PartDstReg); 1807 } 1808 1809 for (unsigned LeftoverReg : LeftoverRegs) { 1810 unsigned PartDstReg = MRI.createGenericVirtualRegister(LeftoverTy0); 1811 NewInsts.push_back(MIRBuilder.buildInstrNoInsert(MI.getOpcode()) 1812 .addDef(PartDstReg) 1813 .addUse(LeftoverReg)); 1814 LeftoverDstRegs.push_back(PartDstReg); 1815 } 1816 } else { 1817 assert(NewInsts.size() == PartRegs.size() + LeftoverRegs.size()); 1818 1819 // Add the newly created operand splits to the existing instructions. The 1820 // odd-sized pieces are ordered after the requested NarrowTyArg sized 1821 // pieces. 1822 unsigned InstCount = 0; 1823 for (unsigned J = 0, JE = PartRegs.size(); J != JE; ++J) 1824 NewInsts[InstCount++].addUse(PartRegs[J]); 1825 for (unsigned J = 0, JE = LeftoverRegs.size(); J != JE; ++J) 1826 NewInsts[InstCount++].addUse(LeftoverRegs[J]); 1827 } 1828 1829 PartRegs.clear(); 1830 LeftoverRegs.clear(); 1831 } 1832 1833 // Insert the newly built operations and rebuild the result register. 1834 for (auto &MIB : NewInsts) 1835 MIRBuilder.insertInstr(MIB); 1836 1837 insertParts(DstReg, DstTy, NarrowTy0, DstRegs, LeftoverTy0, LeftoverDstRegs); 1838 1839 MI.eraseFromParent(); 1840 return Legalized; 1841 } 1842 1843 LegalizerHelper::LegalizeResult 1844 LegalizerHelper::fewerElementsVectorCasts(MachineInstr &MI, unsigned TypeIdx, 1845 LLT NarrowTy) { 1846 if (TypeIdx != 0) 1847 return UnableToLegalize; 1848 1849 unsigned DstReg = MI.getOperand(0).getReg(); 1850 unsigned SrcReg = MI.getOperand(1).getReg(); 1851 LLT DstTy = MRI.getType(DstReg); 1852 LLT SrcTy = MRI.getType(SrcReg); 1853 1854 LLT NarrowTy0 = NarrowTy; 1855 LLT NarrowTy1; 1856 unsigned NumParts; 1857 1858 if (NarrowTy.isVector()) { 1859 // Uneven breakdown not handled. 1860 NumParts = DstTy.getNumElements() / NarrowTy.getNumElements(); 1861 if (NumParts * NarrowTy.getNumElements() != DstTy.getNumElements()) 1862 return UnableToLegalize; 1863 1864 NarrowTy1 = LLT::vector(NumParts, SrcTy.getElementType().getSizeInBits()); 1865 } else { 1866 NumParts = DstTy.getNumElements(); 1867 NarrowTy1 = SrcTy.getElementType(); 1868 } 1869 1870 SmallVector<unsigned, 4> SrcRegs, DstRegs; 1871 extractParts(SrcReg, NarrowTy1, NumParts, SrcRegs); 1872 1873 for (unsigned I = 0; I < NumParts; ++I) { 1874 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy0); 1875 MachineInstr *NewInst = MIRBuilder.buildInstr(MI.getOpcode()) 1876 .addDef(DstReg) 1877 .addUse(SrcRegs[I]); 1878 1879 NewInst->setFlags(MI.getFlags()); 1880 DstRegs.push_back(DstReg); 1881 } 1882 1883 if (NarrowTy.isVector()) 1884 MIRBuilder.buildConcatVectors(DstReg, DstRegs); 1885 else 1886 MIRBuilder.buildBuildVector(DstReg, DstRegs); 1887 1888 MI.eraseFromParent(); 1889 return Legalized; 1890 } 1891 1892 LegalizerHelper::LegalizeResult 1893 LegalizerHelper::fewerElementsVectorCmp(MachineInstr &MI, unsigned TypeIdx, 1894 LLT NarrowTy) { 1895 unsigned DstReg = MI.getOperand(0).getReg(); 1896 unsigned Src0Reg = MI.getOperand(2).getReg(); 1897 LLT DstTy = MRI.getType(DstReg); 1898 LLT SrcTy = MRI.getType(Src0Reg); 1899 1900 unsigned NumParts; 1901 LLT NarrowTy0, NarrowTy1; 1902 1903 if (TypeIdx == 0) { 1904 unsigned NewElts = NarrowTy.isVector() ? NarrowTy.getNumElements() : 1; 1905 unsigned OldElts = DstTy.getNumElements(); 1906 1907 NarrowTy0 = NarrowTy; 1908 NumParts = NarrowTy.isVector() ? (OldElts / NewElts) : DstTy.getNumElements(); 1909 NarrowTy1 = NarrowTy.isVector() ? 1910 LLT::vector(NarrowTy.getNumElements(), SrcTy.getScalarSizeInBits()) : 1911 SrcTy.getElementType(); 1912 1913 } else { 1914 unsigned NewElts = NarrowTy.isVector() ? NarrowTy.getNumElements() : 1; 1915 unsigned OldElts = SrcTy.getNumElements(); 1916 1917 NumParts = NarrowTy.isVector() ? (OldElts / NewElts) : 1918 NarrowTy.getNumElements(); 1919 NarrowTy0 = LLT::vector(NarrowTy.getNumElements(), 1920 DstTy.getScalarSizeInBits()); 1921 NarrowTy1 = NarrowTy; 1922 } 1923 1924 // FIXME: Don't know how to handle the situation where the small vectors 1925 // aren't all the same size yet. 1926 if (NarrowTy1.isVector() && 1927 NarrowTy1.getNumElements() * NumParts != DstTy.getNumElements()) 1928 return UnableToLegalize; 1929 1930 CmpInst::Predicate Pred 1931 = static_cast<CmpInst::Predicate>(MI.getOperand(1).getPredicate()); 1932 1933 SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs; 1934 extractParts(MI.getOperand(2).getReg(), NarrowTy1, NumParts, Src1Regs); 1935 extractParts(MI.getOperand(3).getReg(), NarrowTy1, NumParts, Src2Regs); 1936 1937 for (unsigned I = 0; I < NumParts; ++I) { 1938 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy0); 1939 DstRegs.push_back(DstReg); 1940 1941 if (MI.getOpcode() == TargetOpcode::G_ICMP) 1942 MIRBuilder.buildICmp(Pred, DstReg, Src1Regs[I], Src2Regs[I]); 1943 else { 1944 MachineInstr *NewCmp 1945 = MIRBuilder.buildFCmp(Pred, DstReg, Src1Regs[I], Src2Regs[I]); 1946 NewCmp->setFlags(MI.getFlags()); 1947 } 1948 } 1949 1950 if (NarrowTy1.isVector()) 1951 MIRBuilder.buildConcatVectors(DstReg, DstRegs); 1952 else 1953 MIRBuilder.buildBuildVector(DstReg, DstRegs); 1954 1955 MI.eraseFromParent(); 1956 return Legalized; 1957 } 1958 1959 LegalizerHelper::LegalizeResult 1960 LegalizerHelper::fewerElementsVectorSelect(MachineInstr &MI, unsigned TypeIdx, 1961 LLT NarrowTy) { 1962 unsigned DstReg = MI.getOperand(0).getReg(); 1963 unsigned CondReg = MI.getOperand(1).getReg(); 1964 1965 unsigned NumParts = 0; 1966 LLT NarrowTy0, NarrowTy1; 1967 1968 LLT DstTy = MRI.getType(DstReg); 1969 LLT CondTy = MRI.getType(CondReg); 1970 unsigned Size = DstTy.getSizeInBits(); 1971 1972 assert(TypeIdx == 0 || CondTy.isVector()); 1973 1974 if (TypeIdx == 0) { 1975 NarrowTy0 = NarrowTy; 1976 NarrowTy1 = CondTy; 1977 1978 unsigned NarrowSize = NarrowTy0.getSizeInBits(); 1979 // FIXME: Don't know how to handle the situation where the small vectors 1980 // aren't all the same size yet. 1981 if (Size % NarrowSize != 0) 1982 return UnableToLegalize; 1983 1984 NumParts = Size / NarrowSize; 1985 1986 // Need to break down the condition type 1987 if (CondTy.isVector()) { 1988 if (CondTy.getNumElements() == NumParts) 1989 NarrowTy1 = CondTy.getElementType(); 1990 else 1991 NarrowTy1 = LLT::vector(CondTy.getNumElements() / NumParts, 1992 CondTy.getScalarSizeInBits()); 1993 } 1994 } else { 1995 NumParts = CondTy.getNumElements(); 1996 if (NarrowTy.isVector()) { 1997 // TODO: Handle uneven breakdown. 1998 if (NumParts * NarrowTy.getNumElements() != CondTy.getNumElements()) 1999 return UnableToLegalize; 2000 2001 return UnableToLegalize; 2002 } else { 2003 NarrowTy0 = DstTy.getElementType(); 2004 NarrowTy1 = NarrowTy; 2005 } 2006 } 2007 2008 SmallVector<unsigned, 2> DstRegs, Src0Regs, Src1Regs, Src2Regs; 2009 if (CondTy.isVector()) 2010 extractParts(MI.getOperand(1).getReg(), NarrowTy1, NumParts, Src0Regs); 2011 2012 extractParts(MI.getOperand(2).getReg(), NarrowTy0, NumParts, Src1Regs); 2013 extractParts(MI.getOperand(3).getReg(), NarrowTy0, NumParts, Src2Regs); 2014 2015 for (unsigned i = 0; i < NumParts; ++i) { 2016 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy0); 2017 MIRBuilder.buildSelect(DstReg, CondTy.isVector() ? Src0Regs[i] : CondReg, 2018 Src1Regs[i], Src2Regs[i]); 2019 DstRegs.push_back(DstReg); 2020 } 2021 2022 if (NarrowTy0.isVector()) 2023 MIRBuilder.buildConcatVectors(DstReg, DstRegs); 2024 else 2025 MIRBuilder.buildBuildVector(DstReg, DstRegs); 2026 2027 MI.eraseFromParent(); 2028 return Legalized; 2029 } 2030 2031 LegalizerHelper::LegalizeResult 2032 LegalizerHelper::fewerElementsVectorPhi(MachineInstr &MI, unsigned TypeIdx, 2033 LLT NarrowTy) { 2034 const unsigned DstReg = MI.getOperand(0).getReg(); 2035 LLT PhiTy = MRI.getType(DstReg); 2036 LLT LeftoverTy; 2037 2038 // All of the operands need to have the same number of elements, so if we can 2039 // determine a type breakdown for the result type, we can for all of the 2040 // source types. 2041 int NumParts, NumLeftover; 2042 std::tie(NumParts, NumLeftover) 2043 = getNarrowTypeBreakDown(PhiTy, NarrowTy, LeftoverTy); 2044 if (NumParts < 0) 2045 return UnableToLegalize; 2046 2047 SmallVector<unsigned, 4> DstRegs, LeftoverDstRegs; 2048 SmallVector<MachineInstrBuilder, 4> NewInsts; 2049 2050 const int TotalNumParts = NumParts + NumLeftover; 2051 2052 // Insert the new phis in the result block first. 2053 for (int I = 0; I != TotalNumParts; ++I) { 2054 LLT Ty = I < NumParts ? NarrowTy : LeftoverTy; 2055 unsigned PartDstReg = MRI.createGenericVirtualRegister(Ty); 2056 NewInsts.push_back(MIRBuilder.buildInstr(TargetOpcode::G_PHI) 2057 .addDef(PartDstReg)); 2058 if (I < NumParts) 2059 DstRegs.push_back(PartDstReg); 2060 else 2061 LeftoverDstRegs.push_back(PartDstReg); 2062 } 2063 2064 MachineBasicBlock *MBB = MI.getParent(); 2065 MIRBuilder.setInsertPt(*MBB, MBB->getFirstNonPHI()); 2066 insertParts(DstReg, PhiTy, NarrowTy, DstRegs, LeftoverTy, LeftoverDstRegs); 2067 2068 SmallVector<unsigned, 4> PartRegs, LeftoverRegs; 2069 2070 // Insert code to extract the incoming values in each predecessor block. 2071 for (unsigned I = 1, E = MI.getNumOperands(); I != E; I += 2) { 2072 PartRegs.clear(); 2073 LeftoverRegs.clear(); 2074 2075 unsigned SrcReg = MI.getOperand(I).getReg(); 2076 MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB(); 2077 MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator()); 2078 2079 LLT Unused; 2080 if (!extractParts(SrcReg, PhiTy, NarrowTy, Unused, PartRegs, 2081 LeftoverRegs)) 2082 return UnableToLegalize; 2083 2084 // Add the newly created operand splits to the existing instructions. The 2085 // odd-sized pieces are ordered after the requested NarrowTyArg sized 2086 // pieces. 2087 for (int J = 0; J != TotalNumParts; ++J) { 2088 MachineInstrBuilder MIB = NewInsts[J]; 2089 MIB.addUse(J < NumParts ? PartRegs[J] : LeftoverRegs[J - NumParts]); 2090 MIB.addMBB(&OpMBB); 2091 } 2092 } 2093 2094 MI.eraseFromParent(); 2095 return Legalized; 2096 } 2097 2098 LegalizerHelper::LegalizeResult 2099 LegalizerHelper::reduceLoadStoreWidth(MachineInstr &MI, unsigned TypeIdx, 2100 LLT NarrowTy) { 2101 // FIXME: Don't know how to handle secondary types yet. 2102 if (TypeIdx != 0) 2103 return UnableToLegalize; 2104 2105 MachineMemOperand *MMO = *MI.memoperands_begin(); 2106 2107 // This implementation doesn't work for atomics. Give up instead of doing 2108 // something invalid. 2109 if (MMO->getOrdering() != AtomicOrdering::NotAtomic || 2110 MMO->getFailureOrdering() != AtomicOrdering::NotAtomic) 2111 return UnableToLegalize; 2112 2113 bool IsLoad = MI.getOpcode() == TargetOpcode::G_LOAD; 2114 unsigned ValReg = MI.getOperand(0).getReg(); 2115 unsigned AddrReg = MI.getOperand(1).getReg(); 2116 LLT ValTy = MRI.getType(ValReg); 2117 2118 int NumParts = -1; 2119 int NumLeftover = -1; 2120 LLT LeftoverTy; 2121 SmallVector<unsigned, 8> NarrowRegs, NarrowLeftoverRegs; 2122 if (IsLoad) { 2123 std::tie(NumParts, NumLeftover) = getNarrowTypeBreakDown(ValTy, NarrowTy, LeftoverTy); 2124 } else { 2125 if (extractParts(ValReg, ValTy, NarrowTy, LeftoverTy, NarrowRegs, 2126 NarrowLeftoverRegs)) { 2127 NumParts = NarrowRegs.size(); 2128 NumLeftover = NarrowLeftoverRegs.size(); 2129 } 2130 } 2131 2132 if (NumParts == -1) 2133 return UnableToLegalize; 2134 2135 const LLT OffsetTy = LLT::scalar(MRI.getType(AddrReg).getScalarSizeInBits()); 2136 2137 unsigned TotalSize = ValTy.getSizeInBits(); 2138 2139 // Split the load/store into PartTy sized pieces starting at Offset. If this 2140 // is a load, return the new registers in ValRegs. For a store, each elements 2141 // of ValRegs should be PartTy. Returns the next offset that needs to be 2142 // handled. 2143 auto splitTypePieces = [=](LLT PartTy, SmallVectorImpl<unsigned> &ValRegs, 2144 unsigned Offset) -> unsigned { 2145 MachineFunction &MF = MIRBuilder.getMF(); 2146 unsigned PartSize = PartTy.getSizeInBits(); 2147 for (unsigned Idx = 0, E = NumParts; Idx != E && Offset < TotalSize; 2148 Offset += PartSize, ++Idx) { 2149 unsigned ByteSize = PartSize / 8; 2150 unsigned ByteOffset = Offset / 8; 2151 unsigned NewAddrReg = 0; 2152 2153 MIRBuilder.materializeGEP(NewAddrReg, AddrReg, OffsetTy, ByteOffset); 2154 2155 MachineMemOperand *NewMMO = 2156 MF.getMachineMemOperand(MMO, ByteOffset, ByteSize); 2157 2158 if (IsLoad) { 2159 unsigned Dst = MRI.createGenericVirtualRegister(PartTy); 2160 ValRegs.push_back(Dst); 2161 MIRBuilder.buildLoad(Dst, NewAddrReg, *NewMMO); 2162 } else { 2163 MIRBuilder.buildStore(ValRegs[Idx], NewAddrReg, *NewMMO); 2164 } 2165 } 2166 2167 return Offset; 2168 }; 2169 2170 unsigned HandledOffset = splitTypePieces(NarrowTy, NarrowRegs, 0); 2171 2172 // Handle the rest of the register if this isn't an even type breakdown. 2173 if (LeftoverTy.isValid()) 2174 splitTypePieces(LeftoverTy, NarrowLeftoverRegs, HandledOffset); 2175 2176 if (IsLoad) { 2177 insertParts(ValReg, ValTy, NarrowTy, NarrowRegs, 2178 LeftoverTy, NarrowLeftoverRegs); 2179 } 2180 2181 MI.eraseFromParent(); 2182 return Legalized; 2183 } 2184 2185 LegalizerHelper::LegalizeResult 2186 LegalizerHelper::fewerElementsVector(MachineInstr &MI, unsigned TypeIdx, 2187 LLT NarrowTy) { 2188 using namespace TargetOpcode; 2189 2190 MIRBuilder.setInstr(MI); 2191 switch (MI.getOpcode()) { 2192 case G_IMPLICIT_DEF: 2193 return fewerElementsVectorImplicitDef(MI, TypeIdx, NarrowTy); 2194 case G_AND: 2195 case G_OR: 2196 case G_XOR: 2197 case G_ADD: 2198 case G_SUB: 2199 case G_MUL: 2200 case G_SMULH: 2201 case G_UMULH: 2202 case G_FADD: 2203 case G_FMUL: 2204 case G_FSUB: 2205 case G_FNEG: 2206 case G_FABS: 2207 case G_FCANONICALIZE: 2208 case G_FDIV: 2209 case G_FREM: 2210 case G_FMA: 2211 case G_FPOW: 2212 case G_FEXP: 2213 case G_FEXP2: 2214 case G_FLOG: 2215 case G_FLOG2: 2216 case G_FLOG10: 2217 case G_FCEIL: 2218 case G_FFLOOR: 2219 case G_INTRINSIC_ROUND: 2220 case G_INTRINSIC_TRUNC: 2221 case G_FCOS: 2222 case G_FSIN: 2223 case G_FSQRT: 2224 case G_BSWAP: 2225 return fewerElementsVectorBasic(MI, TypeIdx, NarrowTy); 2226 case G_SHL: 2227 case G_LSHR: 2228 case G_ASHR: 2229 case G_CTLZ: 2230 case G_CTLZ_ZERO_UNDEF: 2231 case G_CTTZ: 2232 case G_CTTZ_ZERO_UNDEF: 2233 case G_CTPOP: 2234 return fewerElementsVectorMultiEltType(MI, TypeIdx, NarrowTy); 2235 case G_ZEXT: 2236 case G_SEXT: 2237 case G_ANYEXT: 2238 case G_FPEXT: 2239 case G_FPTRUNC: 2240 case G_SITOFP: 2241 case G_UITOFP: 2242 case G_FPTOSI: 2243 case G_FPTOUI: 2244 case G_INTTOPTR: 2245 case G_PTRTOINT: 2246 case G_ADDRSPACE_CAST: 2247 return fewerElementsVectorCasts(MI, TypeIdx, NarrowTy); 2248 case G_ICMP: 2249 case G_FCMP: 2250 return fewerElementsVectorCmp(MI, TypeIdx, NarrowTy); 2251 case G_SELECT: 2252 return fewerElementsVectorSelect(MI, TypeIdx, NarrowTy); 2253 case G_PHI: 2254 return fewerElementsVectorPhi(MI, TypeIdx, NarrowTy); 2255 case G_LOAD: 2256 case G_STORE: 2257 return reduceLoadStoreWidth(MI, TypeIdx, NarrowTy); 2258 default: 2259 return UnableToLegalize; 2260 } 2261 } 2262 2263 LegalizerHelper::LegalizeResult 2264 LegalizerHelper::narrowScalarShiftByConstant(MachineInstr &MI, const APInt &Amt, 2265 const LLT HalfTy, const LLT AmtTy) { 2266 2267 unsigned InL = MRI.createGenericVirtualRegister(HalfTy); 2268 unsigned InH = MRI.createGenericVirtualRegister(HalfTy); 2269 MIRBuilder.buildUnmerge({InL, InH}, MI.getOperand(1).getReg()); 2270 2271 if (Amt.isNullValue()) { 2272 MIRBuilder.buildMerge(MI.getOperand(0).getReg(), {InL, InH}); 2273 MI.eraseFromParent(); 2274 return Legalized; 2275 } 2276 2277 LLT NVT = HalfTy; 2278 unsigned NVTBits = HalfTy.getSizeInBits(); 2279 unsigned VTBits = 2 * NVTBits; 2280 2281 SrcOp Lo(0), Hi(0); 2282 if (MI.getOpcode() == TargetOpcode::G_SHL) { 2283 if (Amt.ugt(VTBits)) { 2284 Lo = Hi = MIRBuilder.buildConstant(NVT, 0); 2285 } else if (Amt.ugt(NVTBits)) { 2286 Lo = MIRBuilder.buildConstant(NVT, 0); 2287 Hi = MIRBuilder.buildShl(NVT, InL, 2288 MIRBuilder.buildConstant(AmtTy, Amt - NVTBits)); 2289 } else if (Amt == NVTBits) { 2290 Lo = MIRBuilder.buildConstant(NVT, 0); 2291 Hi = InL; 2292 } else { 2293 Lo = MIRBuilder.buildShl(NVT, InL, MIRBuilder.buildConstant(AmtTy, Amt)); 2294 auto OrLHS = 2295 MIRBuilder.buildShl(NVT, InH, MIRBuilder.buildConstant(AmtTy, Amt)); 2296 auto OrRHS = MIRBuilder.buildLShr( 2297 NVT, InL, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits)); 2298 Hi = MIRBuilder.buildOr(NVT, OrLHS, OrRHS); 2299 } 2300 } else if (MI.getOpcode() == TargetOpcode::G_LSHR) { 2301 if (Amt.ugt(VTBits)) { 2302 Lo = Hi = MIRBuilder.buildConstant(NVT, 0); 2303 } else if (Amt.ugt(NVTBits)) { 2304 Lo = MIRBuilder.buildLShr(NVT, InH, 2305 MIRBuilder.buildConstant(AmtTy, Amt - NVTBits)); 2306 Hi = MIRBuilder.buildConstant(NVT, 0); 2307 } else if (Amt == NVTBits) { 2308 Lo = InH; 2309 Hi = MIRBuilder.buildConstant(NVT, 0); 2310 } else { 2311 auto ShiftAmtConst = MIRBuilder.buildConstant(AmtTy, Amt); 2312 2313 auto OrLHS = MIRBuilder.buildLShr(NVT, InL, ShiftAmtConst); 2314 auto OrRHS = MIRBuilder.buildShl( 2315 NVT, InH, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits)); 2316 2317 Lo = MIRBuilder.buildOr(NVT, OrLHS, OrRHS); 2318 Hi = MIRBuilder.buildLShr(NVT, InH, ShiftAmtConst); 2319 } 2320 } else { 2321 if (Amt.ugt(VTBits)) { 2322 Hi = Lo = MIRBuilder.buildAShr( 2323 NVT, InH, MIRBuilder.buildConstant(AmtTy, NVTBits - 1)); 2324 } else if (Amt.ugt(NVTBits)) { 2325 Lo = MIRBuilder.buildAShr(NVT, InH, 2326 MIRBuilder.buildConstant(AmtTy, Amt - NVTBits)); 2327 Hi = MIRBuilder.buildAShr(NVT, InH, 2328 MIRBuilder.buildConstant(AmtTy, NVTBits - 1)); 2329 } else if (Amt == NVTBits) { 2330 Lo = InH; 2331 Hi = MIRBuilder.buildAShr(NVT, InH, 2332 MIRBuilder.buildConstant(AmtTy, NVTBits - 1)); 2333 } else { 2334 auto ShiftAmtConst = MIRBuilder.buildConstant(AmtTy, Amt); 2335 2336 auto OrLHS = MIRBuilder.buildLShr(NVT, InL, ShiftAmtConst); 2337 auto OrRHS = MIRBuilder.buildShl( 2338 NVT, InH, MIRBuilder.buildConstant(AmtTy, -Amt + NVTBits)); 2339 2340 Lo = MIRBuilder.buildOr(NVT, OrLHS, OrRHS); 2341 Hi = MIRBuilder.buildAShr(NVT, InH, ShiftAmtConst); 2342 } 2343 } 2344 2345 MIRBuilder.buildMerge(MI.getOperand(0).getReg(), {Lo.getReg(), Hi.getReg()}); 2346 MI.eraseFromParent(); 2347 2348 return Legalized; 2349 } 2350 2351 // TODO: Optimize if constant shift amount. 2352 LegalizerHelper::LegalizeResult 2353 LegalizerHelper::narrowScalarShift(MachineInstr &MI, unsigned TypeIdx, 2354 LLT RequestedTy) { 2355 if (TypeIdx == 1) { 2356 Observer.changingInstr(MI); 2357 narrowScalarSrc(MI, RequestedTy, 2); 2358 Observer.changedInstr(MI); 2359 return Legalized; 2360 } 2361 2362 unsigned DstReg = MI.getOperand(0).getReg(); 2363 LLT DstTy = MRI.getType(DstReg); 2364 if (DstTy.isVector()) 2365 return UnableToLegalize; 2366 2367 unsigned Amt = MI.getOperand(2).getReg(); 2368 LLT ShiftAmtTy = MRI.getType(Amt); 2369 const unsigned DstEltSize = DstTy.getScalarSizeInBits(); 2370 if (DstEltSize % 2 != 0) 2371 return UnableToLegalize; 2372 2373 // Ignore the input type. We can only go to exactly half the size of the 2374 // input. If that isn't small enough, the resulting pieces will be further 2375 // legalized. 2376 const unsigned NewBitSize = DstEltSize / 2; 2377 const LLT HalfTy = LLT::scalar(NewBitSize); 2378 const LLT CondTy = LLT::scalar(1); 2379 2380 if (const MachineInstr *KShiftAmt = 2381 getOpcodeDef(TargetOpcode::G_CONSTANT, Amt, MRI)) { 2382 return narrowScalarShiftByConstant( 2383 MI, KShiftAmt->getOperand(1).getCImm()->getValue(), HalfTy, ShiftAmtTy); 2384 } 2385 2386 // TODO: Expand with known bits. 2387 2388 // Handle the fully general expansion by an unknown amount. 2389 auto NewBits = MIRBuilder.buildConstant(ShiftAmtTy, NewBitSize); 2390 2391 unsigned InL = MRI.createGenericVirtualRegister(HalfTy); 2392 unsigned InH = MRI.createGenericVirtualRegister(HalfTy); 2393 MIRBuilder.buildUnmerge({InL, InH}, MI.getOperand(1).getReg()); 2394 2395 auto AmtExcess = MIRBuilder.buildSub(ShiftAmtTy, Amt, NewBits); 2396 auto AmtLack = MIRBuilder.buildSub(ShiftAmtTy, NewBits, Amt); 2397 2398 auto Zero = MIRBuilder.buildConstant(ShiftAmtTy, 0); 2399 auto IsShort = MIRBuilder.buildICmp(ICmpInst::ICMP_ULT, CondTy, Amt, NewBits); 2400 auto IsZero = MIRBuilder.buildICmp(ICmpInst::ICMP_EQ, CondTy, Amt, Zero); 2401 2402 unsigned ResultRegs[2]; 2403 switch (MI.getOpcode()) { 2404 case TargetOpcode::G_SHL: { 2405 // Short: ShAmt < NewBitSize 2406 auto LoS = MIRBuilder.buildShl(HalfTy, InH, Amt); 2407 2408 auto OrLHS = MIRBuilder.buildShl(HalfTy, InH, Amt); 2409 auto OrRHS = MIRBuilder.buildLShr(HalfTy, InL, AmtLack); 2410 auto HiS = MIRBuilder.buildOr(HalfTy, OrLHS, OrRHS); 2411 2412 // Long: ShAmt >= NewBitSize 2413 auto LoL = MIRBuilder.buildConstant(HalfTy, 0); // Lo part is zero. 2414 auto HiL = MIRBuilder.buildShl(HalfTy, InL, AmtExcess); // Hi from Lo part. 2415 2416 auto Lo = MIRBuilder.buildSelect(HalfTy, IsShort, LoS, LoL); 2417 auto Hi = MIRBuilder.buildSelect( 2418 HalfTy, IsZero, InH, MIRBuilder.buildSelect(HalfTy, IsShort, HiS, HiL)); 2419 2420 ResultRegs[0] = Lo.getReg(0); 2421 ResultRegs[1] = Hi.getReg(0); 2422 break; 2423 } 2424 case TargetOpcode::G_LSHR: { 2425 // Short: ShAmt < NewBitSize 2426 auto HiS = MIRBuilder.buildLShr(HalfTy, InH, Amt); 2427 2428 auto OrLHS = MIRBuilder.buildLShr(HalfTy, InL, Amt); 2429 auto OrRHS = MIRBuilder.buildShl(HalfTy, InH, AmtLack); 2430 auto LoS = MIRBuilder.buildOr(HalfTy, OrLHS, OrRHS); 2431 2432 // Long: ShAmt >= NewBitSize 2433 auto HiL = MIRBuilder.buildConstant(HalfTy, 0); // Hi part is zero. 2434 auto LoL = MIRBuilder.buildLShr(HalfTy, InH, AmtExcess); // Lo from Hi part. 2435 2436 auto Lo = MIRBuilder.buildSelect( 2437 HalfTy, IsZero, InL, MIRBuilder.buildSelect(HalfTy, IsShort, LoS, LoL)); 2438 auto Hi = MIRBuilder.buildSelect(HalfTy, IsShort, HiS, HiL); 2439 2440 ResultRegs[0] = Lo.getReg(0); 2441 ResultRegs[1] = Hi.getReg(0); 2442 break; 2443 } 2444 case TargetOpcode::G_ASHR: { 2445 // Short: ShAmt < NewBitSize 2446 auto HiS = MIRBuilder.buildAShr(HalfTy, InH, Amt); 2447 2448 auto OrLHS = MIRBuilder.buildLShr(HalfTy, InL, Amt); 2449 auto OrRHS = MIRBuilder.buildLShr(HalfTy, InH, AmtLack); 2450 auto LoS = MIRBuilder.buildOr(HalfTy, OrLHS, OrRHS); 2451 2452 // Long: ShAmt >= NewBitSize 2453 2454 // Sign of Hi part. 2455 auto HiL = MIRBuilder.buildAShr( 2456 HalfTy, InH, MIRBuilder.buildConstant(ShiftAmtTy, NewBitSize - 1)); 2457 2458 auto LoL = MIRBuilder.buildAShr(HalfTy, InH, AmtExcess); // Lo from Hi part. 2459 2460 auto Lo = MIRBuilder.buildSelect( 2461 HalfTy, IsZero, InL, MIRBuilder.buildSelect(HalfTy, IsShort, LoS, LoL)); 2462 2463 auto Hi = MIRBuilder.buildSelect(HalfTy, IsShort, HiS, HiL); 2464 2465 ResultRegs[0] = Lo.getReg(0); 2466 ResultRegs[1] = Hi.getReg(0); 2467 break; 2468 } 2469 default: 2470 llvm_unreachable("not a shift"); 2471 } 2472 2473 MIRBuilder.buildMerge(DstReg, ResultRegs); 2474 MI.eraseFromParent(); 2475 return Legalized; 2476 } 2477 2478 LegalizerHelper::LegalizeResult 2479 LegalizerHelper::moreElementsVectorPhi(MachineInstr &MI, unsigned TypeIdx, 2480 LLT MoreTy) { 2481 assert(TypeIdx == 0 && "Expecting only Idx 0"); 2482 2483 Observer.changingInstr(MI); 2484 for (unsigned I = 1, E = MI.getNumOperands(); I != E; I += 2) { 2485 MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB(); 2486 MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator()); 2487 moreElementsVectorSrc(MI, MoreTy, I); 2488 } 2489 2490 MachineBasicBlock &MBB = *MI.getParent(); 2491 MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI()); 2492 moreElementsVectorDst(MI, MoreTy, 0); 2493 Observer.changedInstr(MI); 2494 return Legalized; 2495 } 2496 2497 LegalizerHelper::LegalizeResult 2498 LegalizerHelper::moreElementsVector(MachineInstr &MI, unsigned TypeIdx, 2499 LLT MoreTy) { 2500 MIRBuilder.setInstr(MI); 2501 unsigned Opc = MI.getOpcode(); 2502 switch (Opc) { 2503 case TargetOpcode::G_IMPLICIT_DEF: { 2504 Observer.changingInstr(MI); 2505 moreElementsVectorDst(MI, MoreTy, 0); 2506 Observer.changedInstr(MI); 2507 return Legalized; 2508 } 2509 case TargetOpcode::G_AND: 2510 case TargetOpcode::G_OR: 2511 case TargetOpcode::G_XOR: { 2512 Observer.changingInstr(MI); 2513 moreElementsVectorSrc(MI, MoreTy, 1); 2514 moreElementsVectorSrc(MI, MoreTy, 2); 2515 moreElementsVectorDst(MI, MoreTy, 0); 2516 Observer.changedInstr(MI); 2517 return Legalized; 2518 } 2519 case TargetOpcode::G_EXTRACT: 2520 if (TypeIdx != 1) 2521 return UnableToLegalize; 2522 Observer.changingInstr(MI); 2523 moreElementsVectorSrc(MI, MoreTy, 1); 2524 Observer.changedInstr(MI); 2525 return Legalized; 2526 case TargetOpcode::G_INSERT: 2527 if (TypeIdx != 0) 2528 return UnableToLegalize; 2529 Observer.changingInstr(MI); 2530 moreElementsVectorSrc(MI, MoreTy, 1); 2531 moreElementsVectorDst(MI, MoreTy, 0); 2532 Observer.changedInstr(MI); 2533 return Legalized; 2534 case TargetOpcode::G_SELECT: 2535 if (TypeIdx != 0) 2536 return UnableToLegalize; 2537 if (MRI.getType(MI.getOperand(1).getReg()).isVector()) 2538 return UnableToLegalize; 2539 2540 Observer.changingInstr(MI); 2541 moreElementsVectorSrc(MI, MoreTy, 2); 2542 moreElementsVectorSrc(MI, MoreTy, 3); 2543 moreElementsVectorDst(MI, MoreTy, 0); 2544 Observer.changedInstr(MI); 2545 return Legalized; 2546 case TargetOpcode::G_PHI: 2547 return moreElementsVectorPhi(MI, TypeIdx, MoreTy); 2548 default: 2549 return UnableToLegalize; 2550 } 2551 } 2552 2553 void LegalizerHelper::multiplyRegisters(SmallVectorImpl<unsigned> &DstRegs, 2554 ArrayRef<unsigned> Src1Regs, 2555 ArrayRef<unsigned> Src2Regs, 2556 LLT NarrowTy) { 2557 MachineIRBuilder &B = MIRBuilder; 2558 unsigned SrcParts = Src1Regs.size(); 2559 unsigned DstParts = DstRegs.size(); 2560 2561 unsigned DstIdx = 0; // Low bits of the result. 2562 unsigned FactorSum = 2563 B.buildMul(NarrowTy, Src1Regs[DstIdx], Src2Regs[DstIdx]).getReg(0); 2564 DstRegs[DstIdx] = FactorSum; 2565 2566 unsigned CarrySumPrevDstIdx; 2567 SmallVector<unsigned, 4> Factors; 2568 2569 for (DstIdx = 1; DstIdx < DstParts; DstIdx++) { 2570 // Collect low parts of muls for DstIdx. 2571 for (unsigned i = DstIdx + 1 < SrcParts ? 0 : DstIdx - SrcParts + 1; 2572 i <= std::min(DstIdx, SrcParts - 1); ++i) { 2573 MachineInstrBuilder Mul = 2574 B.buildMul(NarrowTy, Src1Regs[DstIdx - i], Src2Regs[i]); 2575 Factors.push_back(Mul.getReg(0)); 2576 } 2577 // Collect high parts of muls from previous DstIdx. 2578 for (unsigned i = DstIdx < SrcParts ? 0 : DstIdx - SrcParts; 2579 i <= std::min(DstIdx - 1, SrcParts - 1); ++i) { 2580 MachineInstrBuilder Umulh = 2581 B.buildUMulH(NarrowTy, Src1Regs[DstIdx - 1 - i], Src2Regs[i]); 2582 Factors.push_back(Umulh.getReg(0)); 2583 } 2584 // Add CarrySum from additons calculated for previous DstIdx. 2585 if (DstIdx != 1) { 2586 Factors.push_back(CarrySumPrevDstIdx); 2587 } 2588 2589 unsigned CarrySum = 0; 2590 // Add all factors and accumulate all carries into CarrySum. 2591 if (DstIdx != DstParts - 1) { 2592 MachineInstrBuilder Uaddo = 2593 B.buildUAddo(NarrowTy, LLT::scalar(1), Factors[0], Factors[1]); 2594 FactorSum = Uaddo.getReg(0); 2595 CarrySum = B.buildZExt(NarrowTy, Uaddo.getReg(1)).getReg(0); 2596 for (unsigned i = 2; i < Factors.size(); ++i) { 2597 MachineInstrBuilder Uaddo = 2598 B.buildUAddo(NarrowTy, LLT::scalar(1), FactorSum, Factors[i]); 2599 FactorSum = Uaddo.getReg(0); 2600 MachineInstrBuilder Carry = B.buildZExt(NarrowTy, Uaddo.getReg(1)); 2601 CarrySum = B.buildAdd(NarrowTy, CarrySum, Carry).getReg(0); 2602 } 2603 } else { 2604 // Since value for the next index is not calculated, neither is CarrySum. 2605 FactorSum = B.buildAdd(NarrowTy, Factors[0], Factors[1]).getReg(0); 2606 for (unsigned i = 2; i < Factors.size(); ++i) 2607 FactorSum = B.buildAdd(NarrowTy, FactorSum, Factors[i]).getReg(0); 2608 } 2609 2610 CarrySumPrevDstIdx = CarrySum; 2611 DstRegs[DstIdx] = FactorSum; 2612 Factors.clear(); 2613 } 2614 } 2615 2616 LegalizerHelper::LegalizeResult 2617 LegalizerHelper::narrowScalarMul(MachineInstr &MI, LLT NarrowTy) { 2618 unsigned DstReg = MI.getOperand(0).getReg(); 2619 unsigned Src1 = MI.getOperand(1).getReg(); 2620 unsigned Src2 = MI.getOperand(2).getReg(); 2621 2622 LLT Ty = MRI.getType(DstReg); 2623 if (Ty.isVector()) 2624 return UnableToLegalize; 2625 2626 unsigned SrcSize = MRI.getType(Src1).getSizeInBits(); 2627 unsigned DstSize = Ty.getSizeInBits(); 2628 unsigned NarrowSize = NarrowTy.getSizeInBits(); 2629 if (DstSize % NarrowSize != 0 || SrcSize % NarrowSize != 0) 2630 return UnableToLegalize; 2631 2632 unsigned NumDstParts = DstSize / NarrowSize; 2633 unsigned NumSrcParts = SrcSize / NarrowSize; 2634 bool IsMulHigh = MI.getOpcode() == TargetOpcode::G_UMULH; 2635 unsigned DstTmpParts = NumDstParts * (IsMulHigh ? 2 : 1); 2636 2637 SmallVector<unsigned, 2> Src1Parts, Src2Parts, DstTmpRegs; 2638 extractParts(Src1, NarrowTy, NumSrcParts, Src1Parts); 2639 extractParts(Src2, NarrowTy, NumSrcParts, Src2Parts); 2640 DstTmpRegs.resize(DstTmpParts); 2641 multiplyRegisters(DstTmpRegs, Src1Parts, Src2Parts, NarrowTy); 2642 2643 // Take only high half of registers if this is high mul. 2644 ArrayRef<unsigned> DstRegs( 2645 IsMulHigh ? &DstTmpRegs[DstTmpParts / 2] : &DstTmpRegs[0], NumDstParts); 2646 MIRBuilder.buildMerge(DstReg, DstRegs); 2647 MI.eraseFromParent(); 2648 return Legalized; 2649 } 2650 2651 LegalizerHelper::LegalizeResult 2652 LegalizerHelper::narrowScalarExtract(MachineInstr &MI, unsigned TypeIdx, 2653 LLT NarrowTy) { 2654 if (TypeIdx != 1) 2655 return UnableToLegalize; 2656 2657 uint64_t NarrowSize = NarrowTy.getSizeInBits(); 2658 2659 int64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits(); 2660 // FIXME: add support for when SizeOp1 isn't an exact multiple of 2661 // NarrowSize. 2662 if (SizeOp1 % NarrowSize != 0) 2663 return UnableToLegalize; 2664 int NumParts = SizeOp1 / NarrowSize; 2665 2666 SmallVector<unsigned, 2> SrcRegs, DstRegs; 2667 SmallVector<uint64_t, 2> Indexes; 2668 extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs); 2669 2670 unsigned OpReg = MI.getOperand(0).getReg(); 2671 uint64_t OpStart = MI.getOperand(2).getImm(); 2672 uint64_t OpSize = MRI.getType(OpReg).getSizeInBits(); 2673 for (int i = 0; i < NumParts; ++i) { 2674 unsigned SrcStart = i * NarrowSize; 2675 2676 if (SrcStart + NarrowSize <= OpStart || SrcStart >= OpStart + OpSize) { 2677 // No part of the extract uses this subregister, ignore it. 2678 continue; 2679 } else if (SrcStart == OpStart && NarrowTy == MRI.getType(OpReg)) { 2680 // The entire subregister is extracted, forward the value. 2681 DstRegs.push_back(SrcRegs[i]); 2682 continue; 2683 } 2684 2685 // OpSegStart is where this destination segment would start in OpReg if it 2686 // extended infinitely in both directions. 2687 int64_t ExtractOffset; 2688 uint64_t SegSize; 2689 if (OpStart < SrcStart) { 2690 ExtractOffset = 0; 2691 SegSize = std::min(NarrowSize, OpStart + OpSize - SrcStart); 2692 } else { 2693 ExtractOffset = OpStart - SrcStart; 2694 SegSize = std::min(SrcStart + NarrowSize - OpStart, OpSize); 2695 } 2696 2697 unsigned SegReg = SrcRegs[i]; 2698 if (ExtractOffset != 0 || SegSize != NarrowSize) { 2699 // A genuine extract is needed. 2700 SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize)); 2701 MIRBuilder.buildExtract(SegReg, SrcRegs[i], ExtractOffset); 2702 } 2703 2704 DstRegs.push_back(SegReg); 2705 } 2706 2707 unsigned DstReg = MI.getOperand(0).getReg(); 2708 if(MRI.getType(DstReg).isVector()) 2709 MIRBuilder.buildBuildVector(DstReg, DstRegs); 2710 else 2711 MIRBuilder.buildMerge(DstReg, DstRegs); 2712 MI.eraseFromParent(); 2713 return Legalized; 2714 } 2715 2716 LegalizerHelper::LegalizeResult 2717 LegalizerHelper::narrowScalarInsert(MachineInstr &MI, unsigned TypeIdx, 2718 LLT NarrowTy) { 2719 // FIXME: Don't know how to handle secondary types yet. 2720 if (TypeIdx != 0) 2721 return UnableToLegalize; 2722 2723 uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(); 2724 uint64_t NarrowSize = NarrowTy.getSizeInBits(); 2725 2726 // FIXME: add support for when SizeOp0 isn't an exact multiple of 2727 // NarrowSize. 2728 if (SizeOp0 % NarrowSize != 0) 2729 return UnableToLegalize; 2730 2731 int NumParts = SizeOp0 / NarrowSize; 2732 2733 SmallVector<unsigned, 2> SrcRegs, DstRegs; 2734 SmallVector<uint64_t, 2> Indexes; 2735 extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs); 2736 2737 unsigned OpReg = MI.getOperand(2).getReg(); 2738 uint64_t OpStart = MI.getOperand(3).getImm(); 2739 uint64_t OpSize = MRI.getType(OpReg).getSizeInBits(); 2740 for (int i = 0; i < NumParts; ++i) { 2741 unsigned DstStart = i * NarrowSize; 2742 2743 if (DstStart + NarrowSize <= OpStart || DstStart >= OpStart + OpSize) { 2744 // No part of the insert affects this subregister, forward the original. 2745 DstRegs.push_back(SrcRegs[i]); 2746 continue; 2747 } else if (DstStart == OpStart && NarrowTy == MRI.getType(OpReg)) { 2748 // The entire subregister is defined by this insert, forward the new 2749 // value. 2750 DstRegs.push_back(OpReg); 2751 continue; 2752 } 2753 2754 // OpSegStart is where this destination segment would start in OpReg if it 2755 // extended infinitely in both directions. 2756 int64_t ExtractOffset, InsertOffset; 2757 uint64_t SegSize; 2758 if (OpStart < DstStart) { 2759 InsertOffset = 0; 2760 ExtractOffset = DstStart - OpStart; 2761 SegSize = std::min(NarrowSize, OpStart + OpSize - DstStart); 2762 } else { 2763 InsertOffset = OpStart - DstStart; 2764 ExtractOffset = 0; 2765 SegSize = 2766 std::min(NarrowSize - InsertOffset, OpStart + OpSize - DstStart); 2767 } 2768 2769 unsigned SegReg = OpReg; 2770 if (ExtractOffset != 0 || SegSize != OpSize) { 2771 // A genuine extract is needed. 2772 SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize)); 2773 MIRBuilder.buildExtract(SegReg, OpReg, ExtractOffset); 2774 } 2775 2776 unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy); 2777 MIRBuilder.buildInsert(DstReg, SrcRegs[i], SegReg, InsertOffset); 2778 DstRegs.push_back(DstReg); 2779 } 2780 2781 assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered"); 2782 unsigned DstReg = MI.getOperand(0).getReg(); 2783 if(MRI.getType(DstReg).isVector()) 2784 MIRBuilder.buildBuildVector(DstReg, DstRegs); 2785 else 2786 MIRBuilder.buildMerge(DstReg, DstRegs); 2787 MI.eraseFromParent(); 2788 return Legalized; 2789 } 2790 2791 LegalizerHelper::LegalizeResult 2792 LegalizerHelper::narrowScalarSelect(MachineInstr &MI, unsigned TypeIdx, 2793 LLT NarrowTy) { 2794 if (TypeIdx != 0) 2795 return UnableToLegalize; 2796 2797 unsigned CondReg = MI.getOperand(1).getReg(); 2798 LLT CondTy = MRI.getType(CondReg); 2799 if (CondTy.isVector()) // TODO: Handle vselect 2800 return UnableToLegalize; 2801 2802 unsigned DstReg = MI.getOperand(0).getReg(); 2803 LLT DstTy = MRI.getType(DstReg); 2804 2805 SmallVector<unsigned, 4> DstRegs, DstLeftoverRegs; 2806 SmallVector<unsigned, 4> Src1Regs, Src1LeftoverRegs; 2807 SmallVector<unsigned, 4> Src2Regs, Src2LeftoverRegs; 2808 LLT LeftoverTy; 2809 if (!extractParts(MI.getOperand(2).getReg(), DstTy, NarrowTy, LeftoverTy, 2810 Src1Regs, Src1LeftoverRegs)) 2811 return UnableToLegalize; 2812 2813 LLT Unused; 2814 if (!extractParts(MI.getOperand(3).getReg(), DstTy, NarrowTy, Unused, 2815 Src2Regs, Src2LeftoverRegs)) 2816 llvm_unreachable("inconsistent extractParts result"); 2817 2818 for (unsigned I = 0, E = Src1Regs.size(); I != E; ++I) { 2819 auto Select = MIRBuilder.buildSelect(NarrowTy, 2820 CondReg, Src1Regs[I], Src2Regs[I]); 2821 DstRegs.push_back(Select->getOperand(0).getReg()); 2822 } 2823 2824 for (unsigned I = 0, E = Src1LeftoverRegs.size(); I != E; ++I) { 2825 auto Select = MIRBuilder.buildSelect( 2826 LeftoverTy, CondReg, Src1LeftoverRegs[I], Src2LeftoverRegs[I]); 2827 DstLeftoverRegs.push_back(Select->getOperand(0).getReg()); 2828 } 2829 2830 insertParts(DstReg, DstTy, NarrowTy, DstRegs, 2831 LeftoverTy, DstLeftoverRegs); 2832 2833 MI.eraseFromParent(); 2834 return Legalized; 2835 } 2836 2837 LegalizerHelper::LegalizeResult 2838 LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) { 2839 unsigned Opc = MI.getOpcode(); 2840 auto &TII = *MI.getMF()->getSubtarget().getInstrInfo(); 2841 auto isSupported = [this](const LegalityQuery &Q) { 2842 auto QAction = LI.getAction(Q).Action; 2843 return QAction == Legal || QAction == Libcall || QAction == Custom; 2844 }; 2845 switch (Opc) { 2846 default: 2847 return UnableToLegalize; 2848 case TargetOpcode::G_CTLZ_ZERO_UNDEF: { 2849 // This trivially expands to CTLZ. 2850 Observer.changingInstr(MI); 2851 MI.setDesc(TII.get(TargetOpcode::G_CTLZ)); 2852 Observer.changedInstr(MI); 2853 return Legalized; 2854 } 2855 case TargetOpcode::G_CTLZ: { 2856 unsigned SrcReg = MI.getOperand(1).getReg(); 2857 unsigned Len = Ty.getSizeInBits(); 2858 if (isSupported({TargetOpcode::G_CTLZ_ZERO_UNDEF, {Ty, Ty}})) { 2859 // If CTLZ_ZERO_UNDEF is supported, emit that and a select for zero. 2860 auto MIBCtlzZU = MIRBuilder.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, 2861 {Ty}, {SrcReg}); 2862 auto MIBZero = MIRBuilder.buildConstant(Ty, 0); 2863 auto MIBLen = MIRBuilder.buildConstant(Ty, Len); 2864 auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1), 2865 SrcReg, MIBZero); 2866 MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen, 2867 MIBCtlzZU); 2868 MI.eraseFromParent(); 2869 return Legalized; 2870 } 2871 // for now, we do this: 2872 // NewLen = NextPowerOf2(Len); 2873 // x = x | (x >> 1); 2874 // x = x | (x >> 2); 2875 // ... 2876 // x = x | (x >>16); 2877 // x = x | (x >>32); // for 64-bit input 2878 // Upto NewLen/2 2879 // return Len - popcount(x); 2880 // 2881 // Ref: "Hacker's Delight" by Henry Warren 2882 unsigned Op = SrcReg; 2883 unsigned NewLen = PowerOf2Ceil(Len); 2884 for (unsigned i = 0; (1U << i) <= (NewLen / 2); ++i) { 2885 auto MIBShiftAmt = MIRBuilder.buildConstant(Ty, 1ULL << i); 2886 auto MIBOp = MIRBuilder.buildInstr( 2887 TargetOpcode::G_OR, {Ty}, 2888 {Op, MIRBuilder.buildInstr(TargetOpcode::G_LSHR, {Ty}, 2889 {Op, MIBShiftAmt})}); 2890 Op = MIBOp->getOperand(0).getReg(); 2891 } 2892 auto MIBPop = MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, {Ty}, {Op}); 2893 MIRBuilder.buildInstr(TargetOpcode::G_SUB, {MI.getOperand(0).getReg()}, 2894 {MIRBuilder.buildConstant(Ty, Len), MIBPop}); 2895 MI.eraseFromParent(); 2896 return Legalized; 2897 } 2898 case TargetOpcode::G_CTTZ_ZERO_UNDEF: { 2899 // This trivially expands to CTTZ. 2900 Observer.changingInstr(MI); 2901 MI.setDesc(TII.get(TargetOpcode::G_CTTZ)); 2902 Observer.changedInstr(MI); 2903 return Legalized; 2904 } 2905 case TargetOpcode::G_CTTZ: { 2906 unsigned SrcReg = MI.getOperand(1).getReg(); 2907 unsigned Len = Ty.getSizeInBits(); 2908 if (isSupported({TargetOpcode::G_CTTZ_ZERO_UNDEF, {Ty, Ty}})) { 2909 // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with 2910 // zero. 2911 auto MIBCttzZU = MIRBuilder.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, 2912 {Ty}, {SrcReg}); 2913 auto MIBZero = MIRBuilder.buildConstant(Ty, 0); 2914 auto MIBLen = MIRBuilder.buildConstant(Ty, Len); 2915 auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1), 2916 SrcReg, MIBZero); 2917 MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen, 2918 MIBCttzZU); 2919 MI.eraseFromParent(); 2920 return Legalized; 2921 } 2922 // for now, we use: { return popcount(~x & (x - 1)); } 2923 // unless the target has ctlz but not ctpop, in which case we use: 2924 // { return 32 - nlz(~x & (x-1)); } 2925 // Ref: "Hacker's Delight" by Henry Warren 2926 auto MIBCstNeg1 = MIRBuilder.buildConstant(Ty, -1); 2927 auto MIBNot = 2928 MIRBuilder.buildInstr(TargetOpcode::G_XOR, {Ty}, {SrcReg, MIBCstNeg1}); 2929 auto MIBTmp = MIRBuilder.buildInstr( 2930 TargetOpcode::G_AND, {Ty}, 2931 {MIBNot, MIRBuilder.buildInstr(TargetOpcode::G_ADD, {Ty}, 2932 {SrcReg, MIBCstNeg1})}); 2933 if (!isSupported({TargetOpcode::G_CTPOP, {Ty, Ty}}) && 2934 isSupported({TargetOpcode::G_CTLZ, {Ty, Ty}})) { 2935 auto MIBCstLen = MIRBuilder.buildConstant(Ty, Len); 2936 MIRBuilder.buildInstr( 2937 TargetOpcode::G_SUB, {MI.getOperand(0).getReg()}, 2938 {MIBCstLen, 2939 MIRBuilder.buildInstr(TargetOpcode::G_CTLZ, {Ty}, {MIBTmp})}); 2940 MI.eraseFromParent(); 2941 return Legalized; 2942 } 2943 MI.setDesc(TII.get(TargetOpcode::G_CTPOP)); 2944 MI.getOperand(1).setReg(MIBTmp->getOperand(0).getReg()); 2945 return Legalized; 2946 } 2947 } 2948 } 2949