LLVM  8.0.0svn
LegalizerHelper.cpp
Go to the documentation of this file.
1 //===-- llvm/CodeGen/GlobalISel/LegalizerHelper.cpp -----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file This file implements the LegalizerHelper class to legalize
11 /// individual instructions and the LegalizeMachineIR wrapper pass for the
12 /// primary legalization.
13 //
14 //===----------------------------------------------------------------------===//
15 
23 #include "llvm/Support/Debug.h"
26 
27 #define DEBUG_TYPE "legalizer"
28 
29 using namespace llvm;
30 using namespace LegalizeActions;
31 
33  : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()) {
34  MIRBuilder.setMF(MF);
35 }
36 
38  : MRI(MF.getRegInfo()), LI(LI) {
39  MIRBuilder.setMF(MF);
40 }
43  LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
44 
45  auto Step = LI.getAction(MI, MRI);
46  switch (Step.Action) {
47  case Legal:
48  LLVM_DEBUG(dbgs() << ".. Already legal\n");
49  return AlreadyLegal;
50  case Libcall:
51  LLVM_DEBUG(dbgs() << ".. Convert to libcall\n");
52  return libcall(MI);
53  case NarrowScalar:
54  LLVM_DEBUG(dbgs() << ".. Narrow scalar\n");
55  return narrowScalar(MI, Step.TypeIdx, Step.NewType);
56  case WidenScalar:
57  LLVM_DEBUG(dbgs() << ".. Widen scalar\n");
58  return widenScalar(MI, Step.TypeIdx, Step.NewType);
59  case Lower:
60  LLVM_DEBUG(dbgs() << ".. Lower\n");
61  return lower(MI, Step.TypeIdx, Step.NewType);
62  case FewerElements:
63  LLVM_DEBUG(dbgs() << ".. Reduce number of elements\n");
64  return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
65  case Custom:
66  LLVM_DEBUG(dbgs() << ".. Custom legalization\n");
67  return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
69  default:
70  LLVM_DEBUG(dbgs() << ".. Unable to legalize\n");
71  return UnableToLegalize;
72  }
73 }
74 
75 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
77  for (int i = 0; i < NumParts; ++i)
79  MIRBuilder.buildUnmerge(VRegs, Reg);
80 }
81 
82 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
83  switch (Opcode) {
84  case TargetOpcode::G_SDIV:
85  assert(Size == 32 && "Unsupported size");
86  return RTLIB::SDIV_I32;
87  case TargetOpcode::G_UDIV:
88  assert(Size == 32 && "Unsupported size");
89  return RTLIB::UDIV_I32;
90  case TargetOpcode::G_SREM:
91  assert(Size == 32 && "Unsupported size");
92  return RTLIB::SREM_I32;
93  case TargetOpcode::G_UREM:
94  assert(Size == 32 && "Unsupported size");
95  return RTLIB::UREM_I32;
96  case TargetOpcode::G_FADD:
97  assert((Size == 32 || Size == 64) && "Unsupported size");
98  return Size == 64 ? RTLIB::ADD_F64 : RTLIB::ADD_F32;
99  case TargetOpcode::G_FSUB:
100  assert((Size == 32 || Size == 64) && "Unsupported size");
101  return Size == 64 ? RTLIB::SUB_F64 : RTLIB::SUB_F32;
102  case TargetOpcode::G_FMUL:
103  assert((Size == 32 || Size == 64) && "Unsupported size");
104  return Size == 64 ? RTLIB::MUL_F64 : RTLIB::MUL_F32;
105  case TargetOpcode::G_FDIV:
106  assert((Size == 32 || Size == 64) && "Unsupported size");
107  return Size == 64 ? RTLIB::DIV_F64 : RTLIB::DIV_F32;
108  case TargetOpcode::G_FREM:
109  return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32;
110  case TargetOpcode::G_FPOW:
111  return Size == 64 ? RTLIB::POW_F64 : RTLIB::POW_F32;
112  case TargetOpcode::G_FMA:
113  assert((Size == 32 || Size == 64) && "Unsupported size");
114  return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32;
115  }
116  llvm_unreachable("Unknown libcall function");
117 }
118 
121  const CallLowering::ArgInfo &Result,
123  auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
124  auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
125  const char *Name = TLI.getLibcallName(Libcall);
126 
127  MIRBuilder.getMF().getFrameInfo().setHasCalls(true);
128  if (!CLI.lowerCall(MIRBuilder, TLI.getLibcallCallingConv(Libcall),
129  MachineOperand::CreateES(Name), Result, Args))
131 
133 }
134 
135 // Useful for libcalls where all operands have the same type.
138  Type *OpType) {
139  auto Libcall = getRTLibDesc(MI.getOpcode(), Size);
140 
142  for (unsigned i = 1; i < MI.getNumOperands(); i++)
143  Args.push_back({MI.getOperand(i).getReg(), OpType});
144  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType},
145  Args);
146 }
147 
148 static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType,
149  Type *FromType) {
150  auto ToMVT = MVT::getVT(ToType);
151  auto FromMVT = MVT::getVT(FromType);
152 
153  switch (Opcode) {
154  case TargetOpcode::G_FPEXT:
155  return RTLIB::getFPEXT(FromMVT, ToMVT);
156  case TargetOpcode::G_FPTRUNC:
157  return RTLIB::getFPROUND(FromMVT, ToMVT);
158  case TargetOpcode::G_FPTOSI:
159  return RTLIB::getFPTOSINT(FromMVT, ToMVT);
160  case TargetOpcode::G_FPTOUI:
161  return RTLIB::getFPTOUINT(FromMVT, ToMVT);
162  case TargetOpcode::G_SITOFP:
163  return RTLIB::getSINTTOFP(FromMVT, ToMVT);
164  case TargetOpcode::G_UITOFP:
165  return RTLIB::getUINTTOFP(FromMVT, ToMVT);
166  }
167  llvm_unreachable("Unsupported libcall function");
168 }
169 
172  Type *FromType) {
174  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), ToType},
175  {{MI.getOperand(1).getReg(), FromType}});
176 }
177 
180  LLT LLTy = MRI.getType(MI.getOperand(0).getReg());
181  unsigned Size = LLTy.getSizeInBits();
182  auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
183 
184  MIRBuilder.setInstr(MI);
185 
186  switch (MI.getOpcode()) {
187  default:
188  return UnableToLegalize;
189  case TargetOpcode::G_SDIV:
190  case TargetOpcode::G_UDIV:
191  case TargetOpcode::G_SREM:
192  case TargetOpcode::G_UREM: {
193  Type *HLTy = Type::getInt32Ty(Ctx);
194  auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
195  if (Status != Legalized)
196  return Status;
197  break;
198  }
199  case TargetOpcode::G_FADD:
200  case TargetOpcode::G_FSUB:
201  case TargetOpcode::G_FMUL:
202  case TargetOpcode::G_FDIV:
203  case TargetOpcode::G_FMA:
204  case TargetOpcode::G_FPOW:
205  case TargetOpcode::G_FREM: {
206  Type *HLTy = Size == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx);
207  auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
208  if (Status != Legalized)
209  return Status;
210  break;
211  }
212  case TargetOpcode::G_FPEXT: {
213  // FIXME: Support other floating point types (half, fp128 etc)
214  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
215  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
216  if (ToSize != 64 || FromSize != 32)
217  return UnableToLegalize;
220  if (Status != Legalized)
221  return Status;
222  break;
223  }
224  case TargetOpcode::G_FPTRUNC: {
225  // FIXME: Support other floating point types (half, fp128 etc)
226  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
227  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
228  if (ToSize != 32 || FromSize != 64)
229  return UnableToLegalize;
232  if (Status != Legalized)
233  return Status;
234  break;
235  }
236  case TargetOpcode::G_FPTOSI:
237  case TargetOpcode::G_FPTOUI: {
238  // FIXME: Support other types
239  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
240  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
241  if (ToSize != 32 || (FromSize != 32 && FromSize != 64))
242  return UnableToLegalize;
244  MI, MIRBuilder, Type::getInt32Ty(Ctx),
245  FromSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx));
246  if (Status != Legalized)
247  return Status;
248  break;
249  }
250  case TargetOpcode::G_SITOFP:
251  case TargetOpcode::G_UITOFP: {
252  // FIXME: Support other types
253  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
254  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
255  if (FromSize != 32 || (ToSize != 32 && ToSize != 64))
256  return UnableToLegalize;
258  MI, MIRBuilder,
259  ToSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx),
260  Type::getInt32Ty(Ctx));
261  if (Status != Legalized)
262  return Status;
263  break;
264  }
265  }
266 
267  MI.eraseFromParent();
268  return Legalized;
269 }
270 
272  unsigned TypeIdx,
273  LLT NarrowTy) {
274  // FIXME: Don't know how to handle secondary types yet.
275  if (TypeIdx != 0 && MI.getOpcode() != TargetOpcode::G_EXTRACT)
276  return UnableToLegalize;
277 
278  MIRBuilder.setInstr(MI);
279 
280  uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
281  uint64_t NarrowSize = NarrowTy.getSizeInBits();
282 
283  switch (MI.getOpcode()) {
284  default:
285  return UnableToLegalize;
286  case TargetOpcode::G_IMPLICIT_DEF: {
287  // FIXME: add support for when SizeOp0 isn't an exact multiple of
288  // NarrowSize.
289  if (SizeOp0 % NarrowSize != 0)
290  return UnableToLegalize;
291  int NumParts = SizeOp0 / NarrowSize;
292 
293  SmallVector<unsigned, 2> DstRegs;
294  for (int i = 0; i < NumParts; ++i)
295  DstRegs.push_back(
296  MIRBuilder.buildUndef(NarrowTy)->getOperand(0).getReg());
297  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
298  MI.eraseFromParent();
299  return Legalized;
300  }
301  case TargetOpcode::G_ADD: {
302  // FIXME: add support for when SizeOp0 isn't an exact multiple of
303  // NarrowSize.
304  if (SizeOp0 % NarrowSize != 0)
305  return UnableToLegalize;
306  // Expand in terms of carry-setting/consuming G_ADDE instructions.
307  int NumParts = SizeOp0 / NarrowTy.getSizeInBits();
308 
309  SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
310  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
311  extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
312 
313  unsigned CarryIn = MRI.createGenericVirtualRegister(LLT::scalar(1));
314  MIRBuilder.buildConstant(CarryIn, 0);
315 
316  for (int i = 0; i < NumParts; ++i) {
317  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
318  unsigned CarryOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
319 
320  MIRBuilder.buildUAdde(DstReg, CarryOut, Src1Regs[i],
321  Src2Regs[i], CarryIn);
322 
323  DstRegs.push_back(DstReg);
324  CarryIn = CarryOut;
325  }
326  unsigned DstReg = MI.getOperand(0).getReg();
327  MIRBuilder.buildMerge(DstReg, DstRegs);
328  MI.eraseFromParent();
329  return Legalized;
330  }
331  case TargetOpcode::G_EXTRACT: {
332  if (TypeIdx != 1)
333  return UnableToLegalize;
334 
335  int64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
336  // FIXME: add support for when SizeOp1 isn't an exact multiple of
337  // NarrowSize.
338  if (SizeOp1 % NarrowSize != 0)
339  return UnableToLegalize;
340  int NumParts = SizeOp1 / NarrowSize;
341 
342  SmallVector<unsigned, 2> SrcRegs, DstRegs;
343  SmallVector<uint64_t, 2> Indexes;
344  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
345 
346  unsigned OpReg = MI.getOperand(0).getReg();
347  uint64_t OpStart = MI.getOperand(2).getImm();
348  uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
349  for (int i = 0; i < NumParts; ++i) {
350  unsigned SrcStart = i * NarrowSize;
351 
352  if (SrcStart + NarrowSize <= OpStart || SrcStart >= OpStart + OpSize) {
353  // No part of the extract uses this subregister, ignore it.
354  continue;
355  } else if (SrcStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
356  // The entire subregister is extracted, forward the value.
357  DstRegs.push_back(SrcRegs[i]);
358  continue;
359  }
360 
361  // OpSegStart is where this destination segment would start in OpReg if it
362  // extended infinitely in both directions.
363  int64_t ExtractOffset;
364  uint64_t SegSize;
365  if (OpStart < SrcStart) {
366  ExtractOffset = 0;
367  SegSize = std::min(NarrowSize, OpStart + OpSize - SrcStart);
368  } else {
369  ExtractOffset = OpStart - SrcStart;
370  SegSize = std::min(SrcStart + NarrowSize - OpStart, OpSize);
371  }
372 
373  unsigned SegReg = SrcRegs[i];
374  if (ExtractOffset != 0 || SegSize != NarrowSize) {
375  // A genuine extract is needed.
376  SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
377  MIRBuilder.buildExtract(SegReg, SrcRegs[i], ExtractOffset);
378  }
379 
380  DstRegs.push_back(SegReg);
381  }
382 
383  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
384  MI.eraseFromParent();
385  return Legalized;
386  }
387  case TargetOpcode::G_INSERT: {
388  // FIXME: add support for when SizeOp0 isn't an exact multiple of
389  // NarrowSize.
390  if (SizeOp0 % NarrowSize != 0)
391  return UnableToLegalize;
392 
393  int NumParts = SizeOp0 / NarrowSize;
394 
395  SmallVector<unsigned, 2> SrcRegs, DstRegs;
396  SmallVector<uint64_t, 2> Indexes;
397  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
398 
399  unsigned OpReg = MI.getOperand(2).getReg();
400  uint64_t OpStart = MI.getOperand(3).getImm();
401  uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
402  for (int i = 0; i < NumParts; ++i) {
403  unsigned DstStart = i * NarrowSize;
404 
405  if (DstStart + NarrowSize <= OpStart || DstStart >= OpStart + OpSize) {
406  // No part of the insert affects this subregister, forward the original.
407  DstRegs.push_back(SrcRegs[i]);
408  continue;
409  } else if (DstStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
410  // The entire subregister is defined by this insert, forward the new
411  // value.
412  DstRegs.push_back(OpReg);
413  continue;
414  }
415 
416  // OpSegStart is where this destination segment would start in OpReg if it
417  // extended infinitely in both directions.
418  int64_t ExtractOffset, InsertOffset;
419  uint64_t SegSize;
420  if (OpStart < DstStart) {
421  InsertOffset = 0;
422  ExtractOffset = DstStart - OpStart;
423  SegSize = std::min(NarrowSize, OpStart + OpSize - DstStart);
424  } else {
425  InsertOffset = OpStart - DstStart;
426  ExtractOffset = 0;
427  SegSize =
428  std::min(NarrowSize - InsertOffset, OpStart + OpSize - DstStart);
429  }
430 
431  unsigned SegReg = OpReg;
432  if (ExtractOffset != 0 || SegSize != OpSize) {
433  // A genuine extract is needed.
434  SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
435  MIRBuilder.buildExtract(SegReg, OpReg, ExtractOffset);
436  }
437 
438  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
439  MIRBuilder.buildInsert(DstReg, SrcRegs[i], SegReg, InsertOffset);
440  DstRegs.push_back(DstReg);
441  }
442 
443  assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered");
444  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
445  MI.eraseFromParent();
446  return Legalized;
447  }
448  case TargetOpcode::G_LOAD: {
449  // FIXME: add support for when SizeOp0 isn't an exact multiple of
450  // NarrowSize.
451  if (SizeOp0 % NarrowSize != 0)
452  return UnableToLegalize;
453 
454  const auto &MMO = **MI.memoperands_begin();
455  // This implementation doesn't work for atomics. Give up instead of doing
456  // something invalid.
457  if (MMO.getOrdering() != AtomicOrdering::NotAtomic ||
458  MMO.getFailureOrdering() != AtomicOrdering::NotAtomic)
459  return UnableToLegalize;
460 
461  int NumParts = SizeOp0 / NarrowSize;
462  LLT OffsetTy = LLT::scalar(
463  MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
464 
465  SmallVector<unsigned, 2> DstRegs;
466  for (int i = 0; i < NumParts; ++i) {
467  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
468  unsigned SrcReg = 0;
469  unsigned Adjustment = i * NarrowSize / 8;
470 
472  MMO.getPointerInfo().getWithOffset(Adjustment), MMO.getFlags(),
473  NarrowSize / 8, i == 0 ? MMO.getAlignment() : NarrowSize / 8,
474  MMO.getAAInfo(), MMO.getRanges(), MMO.getSyncScopeID(),
475  MMO.getOrdering(), MMO.getFailureOrdering());
476 
477  MIRBuilder.materializeGEP(SrcReg, MI.getOperand(1).getReg(), OffsetTy,
478  Adjustment);
479 
480  MIRBuilder.buildLoad(DstReg, SrcReg, *SplitMMO);
481 
482  DstRegs.push_back(DstReg);
483  }
484  unsigned DstReg = MI.getOperand(0).getReg();
485  MIRBuilder.buildMerge(DstReg, DstRegs);
486  MI.eraseFromParent();
487  return Legalized;
488  }
489  case TargetOpcode::G_STORE: {
490  // FIXME: add support for when SizeOp0 isn't an exact multiple of
491  // NarrowSize.
492  if (SizeOp0 % NarrowSize != 0)
493  return UnableToLegalize;
494 
495  const auto &MMO = **MI.memoperands_begin();
496  // This implementation doesn't work for atomics. Give up instead of doing
497  // something invalid.
498  if (MMO.getOrdering() != AtomicOrdering::NotAtomic ||
499  MMO.getFailureOrdering() != AtomicOrdering::NotAtomic)
500  return UnableToLegalize;
501 
502  int NumParts = SizeOp0 / NarrowSize;
503  LLT OffsetTy = LLT::scalar(
504  MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
505 
506  SmallVector<unsigned, 2> SrcRegs;
507  extractParts(MI.getOperand(0).getReg(), NarrowTy, NumParts, SrcRegs);
508 
509  for (int i = 0; i < NumParts; ++i) {
510  unsigned DstReg = 0;
511  unsigned Adjustment = i * NarrowSize / 8;
512 
514  MMO.getPointerInfo().getWithOffset(Adjustment), MMO.getFlags(),
515  NarrowSize / 8, i == 0 ? MMO.getAlignment() : NarrowSize / 8,
516  MMO.getAAInfo(), MMO.getRanges(), MMO.getSyncScopeID(),
517  MMO.getOrdering(), MMO.getFailureOrdering());
518 
519  MIRBuilder.materializeGEP(DstReg, MI.getOperand(1).getReg(), OffsetTy,
520  Adjustment);
521 
522  MIRBuilder.buildStore(SrcRegs[i], DstReg, *SplitMMO);
523  }
524  MI.eraseFromParent();
525  return Legalized;
526  }
527  case TargetOpcode::G_CONSTANT: {
528  // FIXME: add support for when SizeOp0 isn't an exact multiple of
529  // NarrowSize.
530  if (SizeOp0 % NarrowSize != 0)
531  return UnableToLegalize;
532  int NumParts = SizeOp0 / NarrowSize;
533  const APInt &Cst = MI.getOperand(1).getCImm()->getValue();
535 
536  SmallVector<unsigned, 2> DstRegs;
537  for (int i = 0; i < NumParts; ++i) {
538  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
539  ConstantInt *CI =
540  ConstantInt::get(Ctx, Cst.lshr(NarrowSize * i).trunc(NarrowSize));
541  MIRBuilder.buildConstant(DstReg, *CI);
542  DstRegs.push_back(DstReg);
543  }
544  unsigned DstReg = MI.getOperand(0).getReg();
545  MIRBuilder.buildMerge(DstReg, DstRegs);
546  MI.eraseFromParent();
547  return Legalized;
548  }
549  case TargetOpcode::G_OR: {
550  // Legalize bitwise operation:
551  // A = BinOp<Ty> B, C
552  // into:
553  // B1, ..., BN = G_UNMERGE_VALUES B
554  // C1, ..., CN = G_UNMERGE_VALUES C
555  // A1 = BinOp<Ty/N> B1, C2
556  // ...
557  // AN = BinOp<Ty/N> BN, CN
558  // A = G_MERGE_VALUES A1, ..., AN
559 
560  // FIXME: add support for when SizeOp0 isn't an exact multiple of
561  // NarrowSize.
562  if (SizeOp0 % NarrowSize != 0)
563  return UnableToLegalize;
564  int NumParts = SizeOp0 / NarrowSize;
565 
566  // List the registers where the destination will be scattered.
567  SmallVector<unsigned, 2> DstRegs;
568  // List the registers where the first argument will be split.
569  SmallVector<unsigned, 2> SrcsReg1;
570  // List the registers where the second argument will be split.
571  SmallVector<unsigned, 2> SrcsReg2;
572  // Create all the temporary registers.
573  for (int i = 0; i < NumParts; ++i) {
574  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
575  unsigned SrcReg1 = MRI.createGenericVirtualRegister(NarrowTy);
576  unsigned SrcReg2 = MRI.createGenericVirtualRegister(NarrowTy);
577 
578  DstRegs.push_back(DstReg);
579  SrcsReg1.push_back(SrcReg1);
580  SrcsReg2.push_back(SrcReg2);
581  }
582  // Explode the big arguments into smaller chunks.
583  MIRBuilder.buildUnmerge(SrcsReg1, MI.getOperand(1).getReg());
584  MIRBuilder.buildUnmerge(SrcsReg2, MI.getOperand(2).getReg());
585 
586  // Do the operation on each small part.
587  for (int i = 0; i < NumParts; ++i)
588  MIRBuilder.buildOr(DstRegs[i], SrcsReg1[i], SrcsReg2[i]);
589 
590  // Gather the destination registers into the final destination.
591  unsigned DstReg = MI.getOperand(0).getReg();
592  MIRBuilder.buildMerge(DstReg, DstRegs);
593  MI.eraseFromParent();
594  return Legalized;
595  }
596  }
597 }
598 
599 void LegalizerHelper::widenScalarSrc(MachineInstr &MI, LLT WideTy,
600  unsigned OpIdx, unsigned ExtOpcode) {
601  MachineOperand &MO = MI.getOperand(OpIdx);
602  auto ExtB = MIRBuilder.buildInstr(ExtOpcode, WideTy, MO.getReg());
603  MO.setReg(ExtB->getOperand(0).getReg());
604 }
605 
606 void LegalizerHelper::widenScalarDst(MachineInstr &MI, LLT WideTy,
607  unsigned OpIdx, unsigned TruncOpcode) {
608  MachineOperand &MO = MI.getOperand(OpIdx);
609  unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
611  MIRBuilder.buildInstr(TruncOpcode, MO.getReg(), DstExt);
612  MO.setReg(DstExt);
613 }
614 
616 LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) {
617  MIRBuilder.setInstr(MI);
618 
619  switch (MI.getOpcode()) {
620  default:
621  return UnableToLegalize;
622  case TargetOpcode::G_UADDO:
623  case TargetOpcode::G_USUBO: {
624  if (TypeIdx == 1)
625  return UnableToLegalize; // TODO
626  auto LHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, WideTy,
627  MI.getOperand(2).getReg());
628  auto RHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, WideTy,
629  MI.getOperand(3).getReg());
630  unsigned Opcode = MI.getOpcode() == TargetOpcode::G_UADDO
631  ? TargetOpcode::G_ADD
632  : TargetOpcode::G_SUB;
633  // Do the arithmetic in the larger type.
634  auto NewOp = MIRBuilder.buildInstr(Opcode, WideTy, LHSZext, RHSZext);
635  LLT OrigTy = MRI.getType(MI.getOperand(0).getReg());
637  auto AndOp = MIRBuilder.buildInstr(
638  TargetOpcode::G_AND, WideTy, NewOp,
639  MIRBuilder.buildConstant(WideTy, Mask.getZExtValue()));
640  // There is no overflow if the AndOp is the same as NewOp.
642  AndOp);
643  // Now trunc the NewOp to the original result.
644  MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), NewOp);
645  MI.eraseFromParent();
646  return Legalized;
647  }
648  case TargetOpcode::G_CTTZ:
649  case TargetOpcode::G_CTTZ_ZERO_UNDEF:
650  case TargetOpcode::G_CTLZ:
651  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
652  case TargetOpcode::G_CTPOP: {
653  // First ZEXT the input.
654  auto MIBSrc = MIRBuilder.buildZExt(WideTy, MI.getOperand(1).getReg());
655  LLT CurTy = MRI.getType(MI.getOperand(0).getReg());
656  if (MI.getOpcode() == TargetOpcode::G_CTTZ) {
657  // The count is the same in the larger type except if the original
658  // value was zero. This can be handled by setting the bit just off
659  // the top of the original type.
660  auto TopBit =
662  MIBSrc = MIRBuilder.buildInstr(
663  TargetOpcode::G_OR, WideTy, MIBSrc,
664  MIRBuilder.buildConstant(WideTy, TopBit.getSExtValue()));
665  }
666  // Perform the operation at the larger size.
667  auto MIBNewOp = MIRBuilder.buildInstr(MI.getOpcode(), WideTy, MIBSrc);
668  // This is already the correct result for CTPOP and CTTZs
669  if (MI.getOpcode() == TargetOpcode::G_CTLZ ||
670  MI.getOpcode() == TargetOpcode::G_CTLZ_ZERO_UNDEF) {
671  // The correct result is NewOp - (Difference in widety and current ty).
672  unsigned SizeDiff = WideTy.getSizeInBits() - CurTy.getSizeInBits();
673  MIBNewOp =
674  MIRBuilder.buildInstr(TargetOpcode::G_SUB, WideTy, MIBNewOp,
675  MIRBuilder.buildConstant(WideTy, SizeDiff));
676  }
677  auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
678  // Make the original instruction a trunc now, and update it's source.
679  MI.setDesc(TII.get(TargetOpcode::G_TRUNC));
680  MI.getOperand(1).setReg(MIBNewOp->getOperand(0).getReg());
682  return Legalized;
683  }
684 
685  case TargetOpcode::G_ADD:
686  case TargetOpcode::G_AND:
687  case TargetOpcode::G_MUL:
688  case TargetOpcode::G_OR:
689  case TargetOpcode::G_XOR:
690  case TargetOpcode::G_SUB:
691  // Perform operation at larger width (any extension is fine here, high bits
692  // don't affect the result) and then truncate the result back to the
693  // original type.
694  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
695  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
696  widenScalarDst(MI, WideTy);
698  return Legalized;
699 
700  case TargetOpcode::G_SHL:
701  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
702  // The "number of bits to shift" operand must preserve its value as an
703  // unsigned integer:
704  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
705  widenScalarDst(MI, WideTy);
707  return Legalized;
708 
709  case TargetOpcode::G_SDIV:
710  case TargetOpcode::G_SREM:
711  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
712  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
713  widenScalarDst(MI, WideTy);
715  return Legalized;
716 
717  case TargetOpcode::G_ASHR:
718  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
719  // The "number of bits to shift" operand must preserve its value as an
720  // unsigned integer:
721  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
722  widenScalarDst(MI, WideTy);
724  return Legalized;
725 
726  case TargetOpcode::G_UDIV:
727  case TargetOpcode::G_UREM:
728  case TargetOpcode::G_LSHR:
729  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
730  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
731  widenScalarDst(MI, WideTy);
733  return Legalized;
734 
735  case TargetOpcode::G_SELECT:
736  if (TypeIdx != 0)
737  return UnableToLegalize;
738  // Perform operation at larger width (any extension is fine here, high bits
739  // don't affect the result) and then truncate the result back to the
740  // original type.
741  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
742  widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_ANYEXT);
743  widenScalarDst(MI, WideTy);
745  return Legalized;
746 
747  case TargetOpcode::G_FPTOSI:
748  case TargetOpcode::G_FPTOUI:
749  if (TypeIdx != 0)
750  return UnableToLegalize;
751  widenScalarDst(MI, WideTy);
753  return Legalized;
754 
755  case TargetOpcode::G_SITOFP:
756  if (TypeIdx != 1)
757  return UnableToLegalize;
758  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
760  return Legalized;
761 
762  case TargetOpcode::G_UITOFP:
763  if (TypeIdx != 1)
764  return UnableToLegalize;
765  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
767  return Legalized;
768 
769  case TargetOpcode::G_INSERT:
770  if (TypeIdx != 0)
771  return UnableToLegalize;
772  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
773  widenScalarDst(MI, WideTy);
775  return Legalized;
776 
777  case TargetOpcode::G_LOAD:
778  // For some types like i24, we might try to widen to i32. To properly handle
779  // this we should be using a dedicated extending load, until then avoid
780  // trying to legalize.
781  if (alignTo(MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(), 8) !=
782  WideTy.getSizeInBits())
783  return UnableToLegalize;
785  case TargetOpcode::G_SEXTLOAD:
786  case TargetOpcode::G_ZEXTLOAD:
787  widenScalarDst(MI, WideTy);
789  return Legalized;
790 
791  case TargetOpcode::G_STORE: {
792  if (MRI.getType(MI.getOperand(0).getReg()) != LLT::scalar(1) ||
793  WideTy != LLT::scalar(8))
794  return UnableToLegalize;
795 
796  widenScalarSrc(MI, WideTy, 0, TargetOpcode::G_ZEXT);
798  return Legalized;
799  }
800  case TargetOpcode::G_CONSTANT: {
801  MachineOperand &SrcMO = MI.getOperand(1);
803  const APInt &Val = SrcMO.getCImm()->getValue().sext(WideTy.getSizeInBits());
804  SrcMO.setCImm(ConstantInt::get(Ctx, Val));
805 
806  widenScalarDst(MI, WideTy);
808  return Legalized;
809  }
810  case TargetOpcode::G_FCONSTANT: {
811  MachineOperand &SrcMO = MI.getOperand(1);
813  APFloat Val = SrcMO.getFPImm()->getValueAPF();
814  bool LosesInfo;
815  switch (WideTy.getSizeInBits()) {
816  case 32:
818  break;
819  case 64:
821  break;
822  default:
823  llvm_unreachable("Unhandled fp widen type");
824  }
825  SrcMO.setFPImm(ConstantFP::get(Ctx, Val));
826 
827  widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC);
829  return Legalized;
830  }
831  case TargetOpcode::G_BRCOND:
832  widenScalarSrc(MI, WideTy, 0, TargetOpcode::G_ANYEXT);
834  return Legalized;
835 
836  case TargetOpcode::G_FCMP:
837  if (TypeIdx == 0)
838  widenScalarDst(MI, WideTy);
839  else {
840  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_FPEXT);
841  widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_FPEXT);
842  }
844  return Legalized;
845 
846  case TargetOpcode::G_ICMP:
847  if (TypeIdx == 0)
848  widenScalarDst(MI, WideTy);
849  else {
850  unsigned ExtOpcode = CmpInst::isSigned(static_cast<CmpInst::Predicate>(
851  MI.getOperand(1).getPredicate()))
852  ? TargetOpcode::G_SEXT
853  : TargetOpcode::G_ZEXT;
854  widenScalarSrc(MI, WideTy, 2, ExtOpcode);
855  widenScalarSrc(MI, WideTy, 3, ExtOpcode);
856  }
858  return Legalized;
859 
860  case TargetOpcode::G_GEP:
861  assert(TypeIdx == 1 && "unable to legalize pointer of GEP");
862  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
864  return Legalized;
865 
866  case TargetOpcode::G_PHI: {
867  assert(TypeIdx == 0 && "Expecting only Idx 0");
868 
869  for (unsigned I = 1; I < MI.getNumOperands(); I += 2) {
870  MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB();
871  MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
872  widenScalarSrc(MI, WideTy, I, TargetOpcode::G_ANYEXT);
873  }
874 
875  MachineBasicBlock &MBB = *MI.getParent();
876  MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI());
877  widenScalarDst(MI, WideTy);
879  return Legalized;
880  }
881  }
882 }
883 
885 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
886  using namespace TargetOpcode;
887  MIRBuilder.setInstr(MI);
888 
889  switch(MI.getOpcode()) {
890  default:
891  return UnableToLegalize;
892  case TargetOpcode::G_SREM:
893  case TargetOpcode::G_UREM: {
894  unsigned QuotReg = MRI.createGenericVirtualRegister(Ty);
895  MIRBuilder.buildInstr(MI.getOpcode() == G_SREM ? G_SDIV : G_UDIV)
896  .addDef(QuotReg)
897  .addUse(MI.getOperand(1).getReg())
898  .addUse(MI.getOperand(2).getReg());
899 
900  unsigned ProdReg = MRI.createGenericVirtualRegister(Ty);
901  MIRBuilder.buildMul(ProdReg, QuotReg, MI.getOperand(2).getReg());
903  ProdReg);
904  MI.eraseFromParent();
905  return Legalized;
906  }
907  case TargetOpcode::G_SMULO:
908  case TargetOpcode::G_UMULO: {
909  // Generate G_UMULH/G_SMULH to check for overflow and a normal G_MUL for the
910  // result.
911  unsigned Res = MI.getOperand(0).getReg();
912  unsigned Overflow = MI.getOperand(1).getReg();
913  unsigned LHS = MI.getOperand(2).getReg();
914  unsigned RHS = MI.getOperand(3).getReg();
915 
916  MIRBuilder.buildMul(Res, LHS, RHS);
917 
918  unsigned Opcode = MI.getOpcode() == TargetOpcode::G_SMULO
919  ? TargetOpcode::G_SMULH
920  : TargetOpcode::G_UMULH;
921 
922  unsigned HiPart = MRI.createGenericVirtualRegister(Ty);
923  MIRBuilder.buildInstr(Opcode)
924  .addDef(HiPart)
925  .addUse(LHS)
926  .addUse(RHS);
927 
928  unsigned Zero = MRI.createGenericVirtualRegister(Ty);
929  MIRBuilder.buildConstant(Zero, 0);
930 
931  // For *signed* multiply, overflow is detected by checking:
932  // (hi != (lo >> bitwidth-1))
933  if (Opcode == TargetOpcode::G_SMULH) {
934  unsigned Shifted = MRI.createGenericVirtualRegister(Ty);
935  unsigned ShiftAmt = MRI.createGenericVirtualRegister(Ty);
936  MIRBuilder.buildConstant(ShiftAmt, Ty.getSizeInBits() - 1);
937  MIRBuilder.buildInstr(TargetOpcode::G_ASHR)
938  .addDef(Shifted)
939  .addUse(Res)
940  .addUse(ShiftAmt);
941  MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Shifted);
942  } else {
943  MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Zero);
944  }
945  MI.eraseFromParent();
946  return Legalized;
947  }
948  case TargetOpcode::G_FNEG: {
949  // TODO: Handle vector types once we are able to
950  // represent them.
951  if (Ty.isVector())
952  return UnableToLegalize;
953  unsigned Res = MI.getOperand(0).getReg();
954  Type *ZeroTy;
956  switch (Ty.getSizeInBits()) {
957  case 16:
958  ZeroTy = Type::getHalfTy(Ctx);
959  break;
960  case 32:
961  ZeroTy = Type::getFloatTy(Ctx);
962  break;
963  case 64:
964  ZeroTy = Type::getDoubleTy(Ctx);
965  break;
966  case 128:
967  ZeroTy = Type::getFP128Ty(Ctx);
968  break;
969  default:
970  llvm_unreachable("unexpected floating-point type");
971  }
972  ConstantFP &ZeroForNegation =
973  *cast<ConstantFP>(ConstantFP::getZeroValueForNegation(ZeroTy));
974  auto Zero = MIRBuilder.buildFConstant(Ty, ZeroForNegation);
975  MIRBuilder.buildInstr(TargetOpcode::G_FSUB)
976  .addDef(Res)
977  .addUse(Zero->getOperand(0).getReg())
978  .addUse(MI.getOperand(1).getReg());
979  MI.eraseFromParent();
980  return Legalized;
981  }
982  case TargetOpcode::G_FSUB: {
983  // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)).
984  // First, check if G_FNEG is marked as Lower. If so, we may
985  // end up with an infinite loop as G_FSUB is used to legalize G_FNEG.
986  if (LI.getAction({G_FNEG, {Ty}}).Action == Lower)
987  return UnableToLegalize;
988  unsigned Res = MI.getOperand(0).getReg();
989  unsigned LHS = MI.getOperand(1).getReg();
990  unsigned RHS = MI.getOperand(2).getReg();
991  unsigned Neg = MRI.createGenericVirtualRegister(Ty);
992  MIRBuilder.buildInstr(TargetOpcode::G_FNEG).addDef(Neg).addUse(RHS);
993  MIRBuilder.buildInstr(TargetOpcode::G_FADD)
994  .addDef(Res)
995  .addUse(LHS)
996  .addUse(Neg);
997  MI.eraseFromParent();
998  return Legalized;
999  }
1000  case TargetOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: {
1001  unsigned OldValRes = MI.getOperand(0).getReg();
1002  unsigned SuccessRes = MI.getOperand(1).getReg();
1003  unsigned Addr = MI.getOperand(2).getReg();
1004  unsigned CmpVal = MI.getOperand(3).getReg();
1005  unsigned NewVal = MI.getOperand(4).getReg();
1006  MIRBuilder.buildAtomicCmpXchg(OldValRes, Addr, CmpVal, NewVal,
1007  **MI.memoperands_begin());
1008  MIRBuilder.buildICmp(CmpInst::ICMP_EQ, SuccessRes, OldValRes, CmpVal);
1009  MI.eraseFromParent();
1010  return Legalized;
1011  }
1012  case TargetOpcode::G_LOAD:
1013  case TargetOpcode::G_SEXTLOAD:
1014  case TargetOpcode::G_ZEXTLOAD: {
1015  // Lower to a memory-width G_LOAD and a G_SEXT/G_ZEXT/G_ANYEXT
1016  unsigned DstReg = MI.getOperand(0).getReg();
1017  unsigned PtrReg = MI.getOperand(1).getReg();
1018  LLT DstTy = MRI.getType(DstReg);
1019  auto &MMO = **MI.memoperands_begin();
1020 
1021  if (DstTy.getSizeInBits() == MMO.getSize() /* in bytes */ * 8) {
1022  // In the case of G_LOAD, this was a non-extending load already and we're
1023  // about to lower to the same instruction.
1024  if (MI.getOpcode() == TargetOpcode::G_LOAD)
1025  return UnableToLegalize;
1026  MIRBuilder.buildLoad(DstReg, PtrReg, MMO);
1027  MI.eraseFromParent();
1028  return Legalized;
1029  }
1030 
1031  if (DstTy.isScalar()) {
1032  unsigned TmpReg = MRI.createGenericVirtualRegister(
1033  LLT::scalar(MMO.getSize() /* in bytes */ * 8));
1034  MIRBuilder.buildLoad(TmpReg, PtrReg, MMO);
1035  switch (MI.getOpcode()) {
1036  default:
1037  llvm_unreachable("Unexpected opcode");
1038  case TargetOpcode::G_LOAD:
1039  MIRBuilder.buildAnyExt(DstReg, TmpReg);
1040  break;
1041  case TargetOpcode::G_SEXTLOAD:
1042  MIRBuilder.buildSExt(DstReg, TmpReg);
1043  break;
1044  case TargetOpcode::G_ZEXTLOAD:
1045  MIRBuilder.buildZExt(DstReg, TmpReg);
1046  break;
1047  }
1048  MI.eraseFromParent();
1049  return Legalized;
1050  }
1051 
1052  return UnableToLegalize;
1053  }
1054  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
1055  case TargetOpcode::G_CTTZ_ZERO_UNDEF:
1056  case TargetOpcode::G_CTLZ:
1057  case TargetOpcode::G_CTTZ:
1058  case TargetOpcode::G_CTPOP:
1059  return lowerBitCount(MI, TypeIdx, Ty);
1060  }
1061 }
1062 
1065  LLT NarrowTy) {
1066  // FIXME: Don't know how to handle secondary types yet.
1067  if (TypeIdx != 0)
1068  return UnableToLegalize;
1069  switch (MI.getOpcode()) {
1070  default:
1071  return UnableToLegalize;
1072  case TargetOpcode::G_ADD: {
1073  unsigned NarrowSize = NarrowTy.getSizeInBits();
1074  unsigned DstReg = MI.getOperand(0).getReg();
1075  unsigned Size = MRI.getType(DstReg).getSizeInBits();
1076  int NumParts = Size / NarrowSize;
1077  // FIXME: Don't know how to handle the situation where the small vectors
1078  // aren't all the same size yet.
1079  if (Size % NarrowSize != 0)
1080  return UnableToLegalize;
1081 
1082  MIRBuilder.setInstr(MI);
1083 
1084  SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
1085  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
1086  extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
1087 
1088  for (int i = 0; i < NumParts; ++i) {
1089  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
1090  MIRBuilder.buildAdd(DstReg, Src1Regs[i], Src2Regs[i]);
1091  DstRegs.push_back(DstReg);
1092  }
1093 
1094  MIRBuilder.buildMerge(DstReg, DstRegs);
1095  MI.eraseFromParent();
1096  return Legalized;
1097  }
1098  }
1099 }
1100 
1102 LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
1103  unsigned Opc = MI.getOpcode();
1104  auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
1105  auto isLegalOrCustom = [this](const LegalityQuery &Q) {
1106  auto QAction = LI.getAction(Q).Action;
1107  return QAction == Legal || QAction == Custom;
1108  };
1109  switch (Opc) {
1110  default:
1111  return UnableToLegalize;
1112  case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
1113  // This trivially expands to CTLZ.
1114  MI.setDesc(TII.get(TargetOpcode::G_CTLZ));
1116  return Legalized;
1117  }
1118  case TargetOpcode::G_CTLZ: {
1119  unsigned SrcReg = MI.getOperand(1).getReg();
1120  unsigned Len = Ty.getSizeInBits();
1121  if (isLegalOrCustom({TargetOpcode::G_CTLZ_ZERO_UNDEF, {Ty}})) {
1122  // If CTLZ_ZERO_UNDEF is legal or custom, emit that and a select with
1123  // zero.
1124  auto MIBCtlzZU =
1125  MIRBuilder.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, Ty, SrcReg);
1126  auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
1127  auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
1128  auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
1129  SrcReg, MIBZero);
1130  MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
1131  MIBCtlzZU);
1132  MI.eraseFromParent();
1133  return Legalized;
1134  }
1135  // for now, we do this:
1136  // NewLen = NextPowerOf2(Len);
1137  // x = x | (x >> 1);
1138  // x = x | (x >> 2);
1139  // ...
1140  // x = x | (x >>16);
1141  // x = x | (x >>32); // for 64-bit input
1142  // Upto NewLen/2
1143  // return Len - popcount(x);
1144  //
1145  // Ref: "Hacker's Delight" by Henry Warren
1146  unsigned Op = SrcReg;
1147  unsigned NewLen = PowerOf2Ceil(Len);
1148  for (unsigned i = 0; (1U << i) <= (NewLen / 2); ++i) {
1149  auto MIBShiftAmt = MIRBuilder.buildConstant(Ty, 1ULL << i);
1150  auto MIBOp = MIRBuilder.buildInstr(
1151  TargetOpcode::G_OR, Ty, Op,
1152  MIRBuilder.buildInstr(TargetOpcode::G_LSHR, Ty, Op, MIBShiftAmt));
1153  Op = MIBOp->getOperand(0).getReg();
1154  }
1155  auto MIBPop = MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, Ty, Op);
1156  MIRBuilder.buildInstr(TargetOpcode::G_SUB, MI.getOperand(0).getReg(),
1157  MIRBuilder.buildConstant(Ty, Len), MIBPop);
1158  MI.eraseFromParent();
1159  return Legalized;
1160  }
1161  case TargetOpcode::G_CTTZ_ZERO_UNDEF: {
1162  // This trivially expands to CTTZ.
1163  MI.setDesc(TII.get(TargetOpcode::G_CTTZ));
1165  return Legalized;
1166  }
1167  case TargetOpcode::G_CTTZ: {
1168  unsigned SrcReg = MI.getOperand(1).getReg();
1169  unsigned Len = Ty.getSizeInBits();
1170  if (isLegalOrCustom({TargetOpcode::G_CTTZ_ZERO_UNDEF, {Ty}})) {
1171  // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with
1172  // zero.
1173  auto MIBCttzZU =
1174  MIRBuilder.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, Ty, SrcReg);
1175  auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
1176  auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
1177  auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
1178  SrcReg, MIBZero);
1179  MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
1180  MIBCttzZU);
1181  MI.eraseFromParent();
1182  return Legalized;
1183  }
1184  // for now, we use: { return popcount(~x & (x - 1)); }
1185  // unless the target has ctlz but not ctpop, in which case we use:
1186  // { return 32 - nlz(~x & (x-1)); }
1187  // Ref: "Hacker's Delight" by Henry Warren
1188  auto MIBCstNeg1 = MIRBuilder.buildConstant(Ty, -1);
1189  auto MIBNot =
1190  MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, SrcReg, MIBCstNeg1);
1191  auto MIBTmp = MIRBuilder.buildInstr(
1192  TargetOpcode::G_AND, Ty, MIBNot,
1193  MIRBuilder.buildInstr(TargetOpcode::G_ADD, Ty, SrcReg, MIBCstNeg1));
1194  if (!isLegalOrCustom({TargetOpcode::G_CTPOP, {Ty}}) &&
1195  isLegalOrCustom({TargetOpcode::G_CTLZ, {Ty}})) {
1196  auto MIBCstLen = MIRBuilder.buildConstant(Ty, Len);
1198  TargetOpcode::G_SUB, MI.getOperand(0).getReg(),
1199  MIBCstLen,
1200  MIRBuilder.buildInstr(TargetOpcode::G_CTLZ, Ty, MIBTmp));
1201  MI.eraseFromParent();
1202  return Legalized;
1203  }
1204  MI.setDesc(TII.get(TargetOpcode::G_CTPOP));
1205  MI.getOperand(1).setReg(MIBTmp->getOperand(0).getReg());
1206  return Legalized;
1207  }
1208  }
1209 }
static LegalizerHelper::LegalizeResult simpleLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, unsigned Size, Type *OpType)
MachineInstrBuilder buildOr(unsigned Dst, unsigned Src0, unsigned Src1)
Build and insert Res = G_OR Op0, Op1.
void push_back(const T &Elt)
Definition: SmallVector.h:218
MachineIRBuilder MIRBuilder
Expose MIRBuilder so clients can set their own RecordInsertInstruction functions. ...
static Type * getDoubleTy(LLVMContext &C)
Definition: Type.cpp:165
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1557
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:834
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:562
MachineBasicBlock * getMBB() const
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
The operation should be implemented in terms of a wider scalar base-type.
Definition: LegalizerInfo.h:57
void setFPImm(const ConstantFP *CFP)
MachineInstrBuilder buildStore(unsigned Val, unsigned Addr, MachineMemOperand &MMO)
Build and insert G_STORE Val, Addr, MMO.
The LegalityQuery object bundles together all the information that&#39;s needed to decide whether a given...
bool isScalar() const
MachineInstrBuilder buildFConstant(DstType &&Res, const ConstantFP &Val)
Build and insert Res = G_FCONSTANT Val.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
MachineInstrBuilder buildUndef(DstType &&Res)
Build and insert Res = IMPLICIT_DEF.
unsigned getReg() const
getReg - Returns the register number.
MachineInstrBuilder buildSExt(DstType &&Res, ArgType &&Arg)
Build and insert Res = G_SEXT Op.
MachineInstrBuilder buildUnmerge(ArrayRef< unsigned > Res, unsigned Op)
Build and insert Res0, ...
unsigned Reg
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
Definition: LegalizerInfo.h:62
Libcall
RTLIB::Libcall enum - This enum defines all of the runtime library calls the backend can emit...
virtual const TargetLowering * getTargetLowering() const
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
static const MCPhysReg VRegs[32]
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:811
MachineInstrBuilder buildAnyExt(unsigned Res, unsigned Op)
Build and insert Res = G_ANYEXT Op0.
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:685
Libcall getFPROUND(EVT OpVT, EVT RetVT)
getFPROUND - Return the FPROUND_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
MachineInstrBuilder buildAtomicCmpXchg(unsigned OldValRes, unsigned Addr, unsigned CmpVal, unsigned NewVal, MachineMemOperand &MMO)
Build and insert OldValRes<def> = G_ATOMIC_CMPXCHG Addr, CmpVal, NewVal, MMO.
Libcall getUINTTOFP(EVT OpVT, EVT RetVT)
getUINTTOFP - Return the UINTTOFP_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
LegalizerHelper(MachineFunction &MF)
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type...
Definition: LegalizerInfo.h:52
bool isVector() const
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
void recordInsertion(MachineInstr *InsertedInstr) const
A description of a memory reference used in the backend.
bool isSigned() const
Definition: InstrTypes.h:854
LegalizeResult widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy)
Legalize an instruction by performing the operation on a wider scalar type (for example a 16-bit addi...
const HexagonInstrInfo * TII
static Type * getFloatTy(LLVMContext &C)
Definition: Type.cpp:164
const ConstantFP * getFPImm() const
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:412
void setMF(MachineFunction &)
const MachineInstrBuilder & addUse(unsigned RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
MachineMemOperand * getMachineMemOperand(MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s, unsigned base_alignment, const AAMDNodes &AAInfo=AAMDNodes(), const MDNode *Ranges=nullptr, SyncScope::ID SSID=SyncScope::System, AtomicOrdering Ordering=AtomicOrdering::NotAtomic, AtomicOrdering FailureOrdering=AtomicOrdering::NotAtomic)
getMachineMemOperand - Allocate a new MachineMemOperand.
LegalizerHelper::LegalizeResult createLibcall(MachineIRBuilder &MIRBuilder, RTLIB::Libcall Libcall, const CallLowering::ArgInfo &Result, ArrayRef< CallLowering::ArgInfo > Args)
Helper function that creates the given libcall.
opStatus convert(const fltSemantics &ToSemantics, roundingMode RM, bool *losesInfo)
Definition: APFloat.cpp:4444
MachineInstrBuilder buildSub(unsigned Dst, unsigned Src0, unsigned Src1)
Build and insert Res = G_SUB Op0, Op1.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
virtual const TargetInstrInfo * getInstrInfo() const
static const fltSemantics & IEEEdouble() LLVM_READNONE
Definition: APFloat.cpp:123
static LLT scalar(unsigned SizeInBits)
Get a low-level scalar or aggregate "bag of bits".
MachineInstrBuilder buildZExt(DstType &&Res, ArgType &&Arg)
Build and insert Res = G_ZEXT Op.
unsigned const MachineRegisterInfo * MRI
LegalizeResult legalizeInstrStep(MachineInstr &MI)
Replace MI by a sequence of legal instructions that can implement the same operation.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:264
Libcall getFPTOSINT(EVT OpVT, EVT RetVT)
getFPTOSINT - Return the FPTOSINT_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:588
MachineInstrBuilder buildUAdde(unsigned Res, unsigned CarryOut, unsigned Op0, unsigned Op1, unsigned CarryIn)
Build and insert Res, CarryOut = G_UADDE Op0, Op1, CarryIn.
MachineInstrBuilder buildExtract(unsigned Res, unsigned Src, uint64_t Index)
Build and insert `Res0, ...
virtual const CallLowering * getCallLowering() const
void setInstr(MachineInstr &MI)
Set the insertion point to before MI.
static MVT getVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
Definition: ValueTypes.cpp:281
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
Some kind of error has occurred and we could not legalize this instruction.
Instruction was already legal and no change was made to the MachineFunction.
MachineBasicBlock::iterator getInsertPt()
Current insertion point for new instructions.
size_t size() const
Definition: SmallVector.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:971
static Type * getFP128Ty(LLVMContext &C)
Definition: Type.cpp:169
const APFloat & getValueAPF() const
Definition: Constants.h:299
Libcall getFPEXT(EVT OpVT, EVT RetVT)
getFPEXT - Return the FPEXT_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
unsigned createGenericVirtualRegister(LLT Ty, StringRef Name="")
Create and return a new generic virtual register with low-level type Ty.
static Type * getHalfTy(LLVMContext &C)
Definition: Type.cpp:163
static const fltSemantics & IEEEsingle() LLVM_READNONE
Definition: APFloat.cpp:120
void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
LegalizeResult libcall(MachineInstr &MI)
Legalize an instruction by emiting a runtime library call instead.
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:534
static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size)
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
The target wants to do something special with this combination of operand and type.
Definition: LegalizerInfo.h:81
LegalizeResult lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty)
Legalize an instruction by splitting it into simpler parts, hopefully understood by the target...
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:684
LegalizeResult fewerElementsVector(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy)
Legalize a vector instruction by splitting into multiple components, each acting on the same scalar t...
int64_t getImm() const
MachineInstrBuilder buildAdd(unsigned Dst, unsigned Src0, unsigned Src1)
Build and insert Res = G_ADD Op0, Op1.
MachineInstrBuilder buildSelect(unsigned Res, unsigned Tst, unsigned Op0, unsigned Op1)
Build and insert a Res = G_SELECT Tst, Op0, Op1.
MachineInstrBuilder buildTrunc(unsigned Res, unsigned Op)
Build and insert Res = G_TRUNC Op.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Class for arbitrary precision integers.
Definition: APInt.h:70
static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType, Type *FromType)
static MachineOperand CreateES(const char *SymName, unsigned char TargetFlags=0)
static LegalizerHelper::LegalizeResult conversionLibcall(MachineInstr &MI, MachineIRBuilder &MIRBuilder, Type *ToType, Type *FromType)
MachineInstrBuilder buildConstant(unsigned Res, const ConstantInt &Val)
Build and insert Res = G_CONSTANT Val.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineInstrBuilder buildMerge(unsigned Res, ArrayRef< unsigned > Ops)
Build and insert Res = G_MERGE_VALUES Op0, ...
virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder) const
Representation of each machine instruction.
Definition: MachineInstr.h:64
Instruction has been legalized and the MachineFunction changed.
Libcall getFPTOUINT(EVT OpVT, EVT RetVT)
getFPTOUINT - Return the FPTOUINT_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
MachineInstrBuilder buildLoad(unsigned Res, unsigned Addr, MachineMemOperand &MMO)
Build and insert Res = G_LOAD Addr, MMO.
static Constant * getZeroValueForNegation(Type *Ty)
Floating point negation must be implemented with f(x) = -0.0 - x.
Definition: Constants.cpp:748
MachineFunction & getMF()
Getter for the function we currently build.
uint32_t Size
Definition: Profile.cpp:47
void setCImm(const ConstantInt *CI)
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Optional< MachineInstrBuilder > materializeGEP(unsigned &Res, unsigned Op0, const LLT &ValueTy, uint64_t Value)
Materialize and insert Res = G_GEP Op0, (G_CONSTANT Value)
Libcall getSINTTOFP(EVT OpVT, EVT RetVT)
getSINTTOFP - Return the SINTTOFP_*_* value for the given types, or UNKNOWN_LIBCALL if there is none...
LegalizeResult narrowScalar(MachineInstr &MI, unsigned TypeIdx, LLT NarrowTy)
Legalize an instruction by reducing the width of the underlying scalar type.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getSizeInBits(unsigned Reg, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI) const
Get the size in bits of Reg.
This file describes how to lower LLVM calls to machine code calls.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
MachineBasicBlock & getMBB()
Getter for the basic block we currently build.
MachineInstrBuilder buildInstr(unsigned Opc, DstTy &&Ty, UseArgsTy &&... Args)
DAG like Generic method for building arbitrary instructions as above.
IRTranslator LLVM IR MI
MachineInstrBuilder buildMul(unsigned Dst, unsigned Src0, unsigned Src1)
Build and insert Res = G_MUL Op0, Op1.
const MachineInstrBuilder & addDef(unsigned RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
MachineInstrBuilder buildInsert(unsigned Res, unsigned Src, unsigned Op, unsigned Index)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
const ConstantInt * getCImm() const
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:47
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
MachineInstrBuilder buildICmp(CmpInst::Predicate Pred, unsigned Res, unsigned Op0, unsigned Op1)
Build and insert a Res = G_ICMP Pred, Op0, Op1.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:659
This file describes how to lower LLVM code to machine code.
unsigned getPredicate() const