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 
24 #include "llvm/Support/Debug.h"
27 
28 #define DEBUG_TYPE "legalizer"
29 
30 using namespace llvm;
31 using namespace LegalizeActions;
32 
34  GISelChangeObserver &Observer)
35  : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()),
36  Observer(Observer) {
37  MIRBuilder.setMF(MF);
38  MIRBuilder.setChangeObserver(Observer);
39 }
40 
42  GISelChangeObserver &Observer)
43  : MRI(MF.getRegInfo()), LI(LI), Observer(Observer) {
44  MIRBuilder.setMF(MF);
45  MIRBuilder.setChangeObserver(Observer);
46 }
49  LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
50 
51  auto Step = LI.getAction(MI, MRI);
52  switch (Step.Action) {
53  case Legal:
54  LLVM_DEBUG(dbgs() << ".. Already legal\n");
55  return AlreadyLegal;
56  case Libcall:
57  LLVM_DEBUG(dbgs() << ".. Convert to libcall\n");
58  return libcall(MI);
59  case NarrowScalar:
60  LLVM_DEBUG(dbgs() << ".. Narrow scalar\n");
61  return narrowScalar(MI, Step.TypeIdx, Step.NewType);
62  case WidenScalar:
63  LLVM_DEBUG(dbgs() << ".. Widen scalar\n");
64  return widenScalar(MI, Step.TypeIdx, Step.NewType);
65  case Lower:
66  LLVM_DEBUG(dbgs() << ".. Lower\n");
67  return lower(MI, Step.TypeIdx, Step.NewType);
68  case FewerElements:
69  LLVM_DEBUG(dbgs() << ".. Reduce number of elements\n");
70  return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
71  case Custom:
72  LLVM_DEBUG(dbgs() << ".. Custom legalization\n");
73  return LI.legalizeCustom(MI, MRI, MIRBuilder, Observer) ? Legalized
75  default:
76  LLVM_DEBUG(dbgs() << ".. Unable to legalize\n");
77  return UnableToLegalize;
78  }
79 }
80 
81 void LegalizerHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
83  for (int i = 0; i < NumParts; ++i)
85  MIRBuilder.buildUnmerge(VRegs, Reg);
86 }
87 
88 static RTLIB::Libcall getRTLibDesc(unsigned Opcode, unsigned Size) {
89  switch (Opcode) {
90  case TargetOpcode::G_SDIV:
91  assert(Size == 32 && "Unsupported size");
92  return RTLIB::SDIV_I32;
93  case TargetOpcode::G_UDIV:
94  assert(Size == 32 && "Unsupported size");
95  return RTLIB::UDIV_I32;
96  case TargetOpcode::G_SREM:
97  assert(Size == 32 && "Unsupported size");
98  return RTLIB::SREM_I32;
99  case TargetOpcode::G_UREM:
100  assert(Size == 32 && "Unsupported size");
101  return RTLIB::UREM_I32;
102  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
103  assert(Size == 32 && "Unsupported size");
104  return RTLIB::CTLZ_I32;
105  case TargetOpcode::G_FADD:
106  assert((Size == 32 || Size == 64) && "Unsupported size");
107  return Size == 64 ? RTLIB::ADD_F64 : RTLIB::ADD_F32;
108  case TargetOpcode::G_FSUB:
109  assert((Size == 32 || Size == 64) && "Unsupported size");
110  return Size == 64 ? RTLIB::SUB_F64 : RTLIB::SUB_F32;
111  case TargetOpcode::G_FMUL:
112  assert((Size == 32 || Size == 64) && "Unsupported size");
113  return Size == 64 ? RTLIB::MUL_F64 : RTLIB::MUL_F32;
114  case TargetOpcode::G_FDIV:
115  assert((Size == 32 || Size == 64) && "Unsupported size");
116  return Size == 64 ? RTLIB::DIV_F64 : RTLIB::DIV_F32;
117  case TargetOpcode::G_FREM:
118  return Size == 64 ? RTLIB::REM_F64 : RTLIB::REM_F32;
119  case TargetOpcode::G_FPOW:
120  return Size == 64 ? RTLIB::POW_F64 : RTLIB::POW_F32;
121  case TargetOpcode::G_FMA:
122  assert((Size == 32 || Size == 64) && "Unsupported size");
123  return Size == 64 ? RTLIB::FMA_F64 : RTLIB::FMA_F32;
124  }
125  llvm_unreachable("Unknown libcall function");
126 }
127 
130  const CallLowering::ArgInfo &Result,
132  auto &CLI = *MIRBuilder.getMF().getSubtarget().getCallLowering();
133  auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
134  const char *Name = TLI.getLibcallName(Libcall);
135 
136  MIRBuilder.getMF().getFrameInfo().setHasCalls(true);
137  if (!CLI.lowerCall(MIRBuilder, TLI.getLibcallCallingConv(Libcall),
138  MachineOperand::CreateES(Name), Result, Args))
140 
142 }
143 
144 // Useful for libcalls where all operands have the same type.
147  Type *OpType) {
148  auto Libcall = getRTLibDesc(MI.getOpcode(), Size);
149 
151  for (unsigned i = 1; i < MI.getNumOperands(); i++)
152  Args.push_back({MI.getOperand(i).getReg(), OpType});
153  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), OpType},
154  Args);
155 }
156 
157 static RTLIB::Libcall getConvRTLibDesc(unsigned Opcode, Type *ToType,
158  Type *FromType) {
159  auto ToMVT = MVT::getVT(ToType);
160  auto FromMVT = MVT::getVT(FromType);
161 
162  switch (Opcode) {
163  case TargetOpcode::G_FPEXT:
164  return RTLIB::getFPEXT(FromMVT, ToMVT);
165  case TargetOpcode::G_FPTRUNC:
166  return RTLIB::getFPROUND(FromMVT, ToMVT);
167  case TargetOpcode::G_FPTOSI:
168  return RTLIB::getFPTOSINT(FromMVT, ToMVT);
169  case TargetOpcode::G_FPTOUI:
170  return RTLIB::getFPTOUINT(FromMVT, ToMVT);
171  case TargetOpcode::G_SITOFP:
172  return RTLIB::getSINTTOFP(FromMVT, ToMVT);
173  case TargetOpcode::G_UITOFP:
174  return RTLIB::getUINTTOFP(FromMVT, ToMVT);
175  }
176  llvm_unreachable("Unsupported libcall function");
177 }
178 
181  Type *FromType) {
183  return createLibcall(MIRBuilder, Libcall, {MI.getOperand(0).getReg(), ToType},
184  {{MI.getOperand(1).getReg(), FromType}});
185 }
186 
189  LLT LLTy = MRI.getType(MI.getOperand(0).getReg());
190  unsigned Size = LLTy.getSizeInBits();
191  auto &Ctx = MIRBuilder.getMF().getFunction().getContext();
192 
193  MIRBuilder.setInstr(MI);
194 
195  switch (MI.getOpcode()) {
196  default:
197  return UnableToLegalize;
198  case TargetOpcode::G_SDIV:
199  case TargetOpcode::G_UDIV:
200  case TargetOpcode::G_SREM:
201  case TargetOpcode::G_UREM:
202  case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
203  Type *HLTy = Type::getInt32Ty(Ctx);
204  auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
205  if (Status != Legalized)
206  return Status;
207  break;
208  }
209  case TargetOpcode::G_FADD:
210  case TargetOpcode::G_FSUB:
211  case TargetOpcode::G_FMUL:
212  case TargetOpcode::G_FDIV:
213  case TargetOpcode::G_FMA:
214  case TargetOpcode::G_FPOW:
215  case TargetOpcode::G_FREM: {
216  Type *HLTy = Size == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx);
217  auto Status = simpleLibcall(MI, MIRBuilder, Size, HLTy);
218  if (Status != Legalized)
219  return Status;
220  break;
221  }
222  case TargetOpcode::G_FPEXT: {
223  // FIXME: Support other floating point types (half, fp128 etc)
224  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
225  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
226  if (ToSize != 64 || FromSize != 32)
227  return UnableToLegalize;
230  if (Status != Legalized)
231  return Status;
232  break;
233  }
234  case TargetOpcode::G_FPTRUNC: {
235  // FIXME: Support other floating point types (half, fp128 etc)
236  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
237  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
238  if (ToSize != 32 || FromSize != 64)
239  return UnableToLegalize;
242  if (Status != Legalized)
243  return Status;
244  break;
245  }
246  case TargetOpcode::G_FPTOSI:
247  case TargetOpcode::G_FPTOUI: {
248  // FIXME: Support other types
249  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
250  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
251  if (ToSize != 32 || (FromSize != 32 && FromSize != 64))
252  return UnableToLegalize;
254  MI, MIRBuilder, Type::getInt32Ty(Ctx),
255  FromSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx));
256  if (Status != Legalized)
257  return Status;
258  break;
259  }
260  case TargetOpcode::G_SITOFP:
261  case TargetOpcode::G_UITOFP: {
262  // FIXME: Support other types
263  unsigned FromSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
264  unsigned ToSize = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
265  if (FromSize != 32 || (ToSize != 32 && ToSize != 64))
266  return UnableToLegalize;
268  MI, MIRBuilder,
269  ToSize == 64 ? Type::getDoubleTy(Ctx) : Type::getFloatTy(Ctx),
270  Type::getInt32Ty(Ctx));
271  if (Status != Legalized)
272  return Status;
273  break;
274  }
275  }
276 
277  MI.eraseFromParent();
278  return Legalized;
279 }
280 
282  unsigned TypeIdx,
283  LLT NarrowTy) {
284  // FIXME: Don't know how to handle secondary types yet.
285  if (TypeIdx != 0 && MI.getOpcode() != TargetOpcode::G_EXTRACT)
286  return UnableToLegalize;
287 
288  MIRBuilder.setInstr(MI);
289 
290  uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
291  uint64_t NarrowSize = NarrowTy.getSizeInBits();
292 
293  switch (MI.getOpcode()) {
294  default:
295  return UnableToLegalize;
296  case TargetOpcode::G_IMPLICIT_DEF: {
297  // FIXME: add support for when SizeOp0 isn't an exact multiple of
298  // NarrowSize.
299  if (SizeOp0 % NarrowSize != 0)
300  return UnableToLegalize;
301  int NumParts = SizeOp0 / NarrowSize;
302 
303  SmallVector<unsigned, 2> DstRegs;
304  for (int i = 0; i < NumParts; ++i)
305  DstRegs.push_back(
306  MIRBuilder.buildUndef(NarrowTy)->getOperand(0).getReg());
307  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
308  MI.eraseFromParent();
309  return Legalized;
310  }
311  case TargetOpcode::G_ADD: {
312  // FIXME: add support for when SizeOp0 isn't an exact multiple of
313  // NarrowSize.
314  if (SizeOp0 % NarrowSize != 0)
315  return UnableToLegalize;
316  // Expand in terms of carry-setting/consuming G_ADDE instructions.
317  int NumParts = SizeOp0 / NarrowTy.getSizeInBits();
318 
319  SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
320  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
321  extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
322 
323  unsigned CarryIn = MRI.createGenericVirtualRegister(LLT::scalar(1));
324  MIRBuilder.buildConstant(CarryIn, 0);
325 
326  for (int i = 0; i < NumParts; ++i) {
327  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
328  unsigned CarryOut = MRI.createGenericVirtualRegister(LLT::scalar(1));
329 
330  MIRBuilder.buildUAdde(DstReg, CarryOut, Src1Regs[i],
331  Src2Regs[i], CarryIn);
332 
333  DstRegs.push_back(DstReg);
334  CarryIn = CarryOut;
335  }
336  unsigned DstReg = MI.getOperand(0).getReg();
337  MIRBuilder.buildMerge(DstReg, DstRegs);
338  MI.eraseFromParent();
339  return Legalized;
340  }
341  case TargetOpcode::G_EXTRACT: {
342  if (TypeIdx != 1)
343  return UnableToLegalize;
344 
345  int64_t SizeOp1 = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
346  // FIXME: add support for when SizeOp1 isn't an exact multiple of
347  // NarrowSize.
348  if (SizeOp1 % NarrowSize != 0)
349  return UnableToLegalize;
350  int NumParts = SizeOp1 / NarrowSize;
351 
352  SmallVector<unsigned, 2> SrcRegs, DstRegs;
353  SmallVector<uint64_t, 2> Indexes;
354  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
355 
356  unsigned OpReg = MI.getOperand(0).getReg();
357  uint64_t OpStart = MI.getOperand(2).getImm();
358  uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
359  for (int i = 0; i < NumParts; ++i) {
360  unsigned SrcStart = i * NarrowSize;
361 
362  if (SrcStart + NarrowSize <= OpStart || SrcStart >= OpStart + OpSize) {
363  // No part of the extract uses this subregister, ignore it.
364  continue;
365  } else if (SrcStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
366  // The entire subregister is extracted, forward the value.
367  DstRegs.push_back(SrcRegs[i]);
368  continue;
369  }
370 
371  // OpSegStart is where this destination segment would start in OpReg if it
372  // extended infinitely in both directions.
373  int64_t ExtractOffset;
374  uint64_t SegSize;
375  if (OpStart < SrcStart) {
376  ExtractOffset = 0;
377  SegSize = std::min(NarrowSize, OpStart + OpSize - SrcStart);
378  } else {
379  ExtractOffset = OpStart - SrcStart;
380  SegSize = std::min(SrcStart + NarrowSize - OpStart, OpSize);
381  }
382 
383  unsigned SegReg = SrcRegs[i];
384  if (ExtractOffset != 0 || SegSize != NarrowSize) {
385  // A genuine extract is needed.
386  SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
387  MIRBuilder.buildExtract(SegReg, SrcRegs[i], ExtractOffset);
388  }
389 
390  DstRegs.push_back(SegReg);
391  }
392 
393  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
394  MI.eraseFromParent();
395  return Legalized;
396  }
397  case TargetOpcode::G_INSERT: {
398  // FIXME: add support for when SizeOp0 isn't an exact multiple of
399  // NarrowSize.
400  if (SizeOp0 % NarrowSize != 0)
401  return UnableToLegalize;
402 
403  int NumParts = SizeOp0 / NarrowSize;
404 
405  SmallVector<unsigned, 2> SrcRegs, DstRegs;
406  SmallVector<uint64_t, 2> Indexes;
407  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
408 
409  unsigned OpReg = MI.getOperand(2).getReg();
410  uint64_t OpStart = MI.getOperand(3).getImm();
411  uint64_t OpSize = MRI.getType(OpReg).getSizeInBits();
412  for (int i = 0; i < NumParts; ++i) {
413  unsigned DstStart = i * NarrowSize;
414 
415  if (DstStart + NarrowSize <= OpStart || DstStart >= OpStart + OpSize) {
416  // No part of the insert affects this subregister, forward the original.
417  DstRegs.push_back(SrcRegs[i]);
418  continue;
419  } else if (DstStart == OpStart && NarrowTy == MRI.getType(OpReg)) {
420  // The entire subregister is defined by this insert, forward the new
421  // value.
422  DstRegs.push_back(OpReg);
423  continue;
424  }
425 
426  // OpSegStart is where this destination segment would start in OpReg if it
427  // extended infinitely in both directions.
428  int64_t ExtractOffset, InsertOffset;
429  uint64_t SegSize;
430  if (OpStart < DstStart) {
431  InsertOffset = 0;
432  ExtractOffset = DstStart - OpStart;
433  SegSize = std::min(NarrowSize, OpStart + OpSize - DstStart);
434  } else {
435  InsertOffset = OpStart - DstStart;
436  ExtractOffset = 0;
437  SegSize =
438  std::min(NarrowSize - InsertOffset, OpStart + OpSize - DstStart);
439  }
440 
441  unsigned SegReg = OpReg;
442  if (ExtractOffset != 0 || SegSize != OpSize) {
443  // A genuine extract is needed.
444  SegReg = MRI.createGenericVirtualRegister(LLT::scalar(SegSize));
445  MIRBuilder.buildExtract(SegReg, OpReg, ExtractOffset);
446  }
447 
448  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
449  MIRBuilder.buildInsert(DstReg, SrcRegs[i], SegReg, InsertOffset);
450  DstRegs.push_back(DstReg);
451  }
452 
453  assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered");
454  MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
455  MI.eraseFromParent();
456  return Legalized;
457  }
458  case TargetOpcode::G_LOAD: {
459  // FIXME: add support for when SizeOp0 isn't an exact multiple of
460  // NarrowSize.
461  if (SizeOp0 % NarrowSize != 0)
462  return UnableToLegalize;
463 
464  const auto &MMO = **MI.memoperands_begin();
465  // This implementation doesn't work for atomics. Give up instead of doing
466  // something invalid.
467  if (MMO.getOrdering() != AtomicOrdering::NotAtomic ||
468  MMO.getFailureOrdering() != AtomicOrdering::NotAtomic)
469  return UnableToLegalize;
470 
471  int NumParts = SizeOp0 / NarrowSize;
472  LLT OffsetTy = LLT::scalar(
474 
475  SmallVector<unsigned, 2> DstRegs;
476  for (int i = 0; i < NumParts; ++i) {
477  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
478  unsigned SrcReg = 0;
479  unsigned Adjustment = i * NarrowSize / 8;
480  unsigned Alignment = MinAlign(MMO.getAlignment(), Adjustment);
481 
483  MMO.getPointerInfo().getWithOffset(Adjustment), MMO.getFlags(),
484  NarrowSize / 8, Alignment, MMO.getAAInfo(), MMO.getRanges(),
485  MMO.getSyncScopeID(), MMO.getOrdering(), MMO.getFailureOrdering());
486 
487  MIRBuilder.materializeGEP(SrcReg, MI.getOperand(1).getReg(), OffsetTy,
488  Adjustment);
489 
490  MIRBuilder.buildLoad(DstReg, SrcReg, *SplitMMO);
491 
492  DstRegs.push_back(DstReg);
493  }
494  unsigned DstReg = MI.getOperand(0).getReg();
495  MIRBuilder.buildMerge(DstReg, DstRegs);
496  MI.eraseFromParent();
497  return Legalized;
498  }
499  case TargetOpcode::G_STORE: {
500  // FIXME: add support for when SizeOp0 isn't an exact multiple of
501  // NarrowSize.
502  if (SizeOp0 % NarrowSize != 0)
503  return UnableToLegalize;
504 
505  const auto &MMO = **MI.memoperands_begin();
506  // This implementation doesn't work for atomics. Give up instead of doing
507  // something invalid.
508  if (MMO.getOrdering() != AtomicOrdering::NotAtomic ||
509  MMO.getFailureOrdering() != AtomicOrdering::NotAtomic)
510  return UnableToLegalize;
511 
512  int NumParts = SizeOp0 / NarrowSize;
513  LLT OffsetTy = LLT::scalar(
515 
516  SmallVector<unsigned, 2> SrcRegs;
517  extractParts(MI.getOperand(0).getReg(), NarrowTy, NumParts, SrcRegs);
518 
519  for (int i = 0; i < NumParts; ++i) {
520  unsigned DstReg = 0;
521  unsigned Adjustment = i * NarrowSize / 8;
522  unsigned Alignment = MinAlign(MMO.getAlignment(), Adjustment);
523 
525  MMO.getPointerInfo().getWithOffset(Adjustment), MMO.getFlags(),
526  NarrowSize / 8, Alignment, MMO.getAAInfo(), MMO.getRanges(),
527  MMO.getSyncScopeID(), MMO.getOrdering(), MMO.getFailureOrdering());
528 
529  MIRBuilder.materializeGEP(DstReg, MI.getOperand(1).getReg(), OffsetTy,
530  Adjustment);
531 
532  MIRBuilder.buildStore(SrcRegs[i], DstReg, *SplitMMO);
533  }
534  MI.eraseFromParent();
535  return Legalized;
536  }
537  case TargetOpcode::G_CONSTANT: {
538  // FIXME: add support for when SizeOp0 isn't an exact multiple of
539  // NarrowSize.
540  if (SizeOp0 % NarrowSize != 0)
541  return UnableToLegalize;
542  int NumParts = SizeOp0 / NarrowSize;
543  const APInt &Cst = MI.getOperand(1).getCImm()->getValue();
545 
546  SmallVector<unsigned, 2> DstRegs;
547  for (int i = 0; i < NumParts; ++i) {
548  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
549  ConstantInt *CI =
550  ConstantInt::get(Ctx, Cst.lshr(NarrowSize * i).trunc(NarrowSize));
551  MIRBuilder.buildConstant(DstReg, *CI);
552  DstRegs.push_back(DstReg);
553  }
554  unsigned DstReg = MI.getOperand(0).getReg();
555  MIRBuilder.buildMerge(DstReg, DstRegs);
556  MI.eraseFromParent();
557  return Legalized;
558  }
559  case TargetOpcode::G_OR: {
560  // Legalize bitwise operation:
561  // A = BinOp<Ty> B, C
562  // into:
563  // B1, ..., BN = G_UNMERGE_VALUES B
564  // C1, ..., CN = G_UNMERGE_VALUES C
565  // A1 = BinOp<Ty/N> B1, C2
566  // ...
567  // AN = BinOp<Ty/N> BN, CN
568  // A = G_MERGE_VALUES A1, ..., AN
569 
570  // FIXME: add support for when SizeOp0 isn't an exact multiple of
571  // NarrowSize.
572  if (SizeOp0 % NarrowSize != 0)
573  return UnableToLegalize;
574  int NumParts = SizeOp0 / NarrowSize;
575 
576  // List the registers where the destination will be scattered.
577  SmallVector<unsigned, 2> DstRegs;
578  // List the registers where the first argument will be split.
579  SmallVector<unsigned, 2> SrcsReg1;
580  // List the registers where the second argument will be split.
581  SmallVector<unsigned, 2> SrcsReg2;
582  // Create all the temporary registers.
583  for (int i = 0; i < NumParts; ++i) {
584  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
585  unsigned SrcReg1 = MRI.createGenericVirtualRegister(NarrowTy);
586  unsigned SrcReg2 = MRI.createGenericVirtualRegister(NarrowTy);
587 
588  DstRegs.push_back(DstReg);
589  SrcsReg1.push_back(SrcReg1);
590  SrcsReg2.push_back(SrcReg2);
591  }
592  // Explode the big arguments into smaller chunks.
593  MIRBuilder.buildUnmerge(SrcsReg1, MI.getOperand(1).getReg());
594  MIRBuilder.buildUnmerge(SrcsReg2, MI.getOperand(2).getReg());
595 
596  // Do the operation on each small part.
597  for (int i = 0; i < NumParts; ++i)
598  MIRBuilder.buildOr(DstRegs[i], SrcsReg1[i], SrcsReg2[i]);
599 
600  // Gather the destination registers into the final destination.
601  unsigned DstReg = MI.getOperand(0).getReg();
602  MIRBuilder.buildMerge(DstReg, DstRegs);
603  MI.eraseFromParent();
604  return Legalized;
605  }
606  }
607 }
608 
609 void LegalizerHelper::widenScalarSrc(MachineInstr &MI, LLT WideTy,
610  unsigned OpIdx, unsigned ExtOpcode) {
611  MachineOperand &MO = MI.getOperand(OpIdx);
612  auto ExtB = MIRBuilder.buildInstr(ExtOpcode, WideTy, MO.getReg());
613  MO.setReg(ExtB->getOperand(0).getReg());
614 }
615 
616 void LegalizerHelper::widenScalarDst(MachineInstr &MI, LLT WideTy,
617  unsigned OpIdx, unsigned TruncOpcode) {
618  MachineOperand &MO = MI.getOperand(OpIdx);
619  unsigned DstExt = MRI.createGenericVirtualRegister(WideTy);
621  MIRBuilder.buildInstr(TruncOpcode, MO.getReg(), DstExt);
622  MO.setReg(DstExt);
623 }
624 
626 LegalizerHelper::widenScalar(MachineInstr &MI, unsigned TypeIdx, LLT WideTy) {
627  MIRBuilder.setInstr(MI);
628 
629  switch (MI.getOpcode()) {
630  default:
631  return UnableToLegalize;
632  case TargetOpcode::G_UADDO:
633  case TargetOpcode::G_USUBO: {
634  if (TypeIdx == 1)
635  return UnableToLegalize; // TODO
636  auto LHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, WideTy,
637  MI.getOperand(2).getReg());
638  auto RHSZext = MIRBuilder.buildInstr(TargetOpcode::G_ZEXT, WideTy,
639  MI.getOperand(3).getReg());
640  unsigned Opcode = MI.getOpcode() == TargetOpcode::G_UADDO
641  ? TargetOpcode::G_ADD
642  : TargetOpcode::G_SUB;
643  // Do the arithmetic in the larger type.
644  auto NewOp = MIRBuilder.buildInstr(Opcode, WideTy, LHSZext, RHSZext);
645  LLT OrigTy = MRI.getType(MI.getOperand(0).getReg());
647  auto AndOp = MIRBuilder.buildInstr(
648  TargetOpcode::G_AND, WideTy, NewOp,
649  MIRBuilder.buildConstant(WideTy, Mask.getZExtValue()));
650  // There is no overflow if the AndOp is the same as NewOp.
652  AndOp);
653  // Now trunc the NewOp to the original result.
654  MIRBuilder.buildTrunc(MI.getOperand(0).getReg(), NewOp);
655  MI.eraseFromParent();
656  return Legalized;
657  }
658  case TargetOpcode::G_CTTZ:
659  case TargetOpcode::G_CTTZ_ZERO_UNDEF:
660  case TargetOpcode::G_CTLZ:
661  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
662  case TargetOpcode::G_CTPOP: {
663  // First ZEXT the input.
664  auto MIBSrc = MIRBuilder.buildZExt(WideTy, MI.getOperand(1).getReg());
665  LLT CurTy = MRI.getType(MI.getOperand(0).getReg());
666  if (MI.getOpcode() == TargetOpcode::G_CTTZ) {
667  // The count is the same in the larger type except if the original
668  // value was zero. This can be handled by setting the bit just off
669  // the top of the original type.
670  auto TopBit =
672  MIBSrc = MIRBuilder.buildInstr(
673  TargetOpcode::G_OR, WideTy, MIBSrc,
674  MIRBuilder.buildConstant(WideTy, TopBit.getSExtValue()));
675  }
676  // Perform the operation at the larger size.
677  auto MIBNewOp = MIRBuilder.buildInstr(MI.getOpcode(), WideTy, MIBSrc);
678  // This is already the correct result for CTPOP and CTTZs
679  if (MI.getOpcode() == TargetOpcode::G_CTLZ ||
680  MI.getOpcode() == TargetOpcode::G_CTLZ_ZERO_UNDEF) {
681  // The correct result is NewOp - (Difference in widety and current ty).
682  unsigned SizeDiff = WideTy.getSizeInBits() - CurTy.getSizeInBits();
683  MIBNewOp =
684  MIRBuilder.buildInstr(TargetOpcode::G_SUB, WideTy, MIBNewOp,
685  MIRBuilder.buildConstant(WideTy, SizeDiff));
686  }
687  auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
688  // Make the original instruction a trunc now, and update its source.
689  MI.setDesc(TII.get(TargetOpcode::G_TRUNC));
690  MI.getOperand(1).setReg(MIBNewOp->getOperand(0).getReg());
691  Observer.changedInstr(MI);
692  return Legalized;
693  }
694 
695  case TargetOpcode::G_ADD:
696  case TargetOpcode::G_AND:
697  case TargetOpcode::G_MUL:
698  case TargetOpcode::G_OR:
699  case TargetOpcode::G_XOR:
700  case TargetOpcode::G_SUB:
701  // Perform operation at larger width (any extension is fine here, high bits
702  // don't affect the result) and then truncate the result back to the
703  // original type.
704  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
705  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
706  widenScalarDst(MI, WideTy);
707  Observer.changedInstr(MI);
708  return Legalized;
709 
710  case TargetOpcode::G_SHL:
711  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
712  // The "number of bits to shift" operand must preserve its value as an
713  // unsigned integer:
714  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
715  widenScalarDst(MI, WideTy);
716  Observer.changedInstr(MI);
717  return Legalized;
718 
719  case TargetOpcode::G_SDIV:
720  case TargetOpcode::G_SREM:
721  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
722  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
723  widenScalarDst(MI, WideTy);
724  Observer.changedInstr(MI);
725  return Legalized;
726 
727  case TargetOpcode::G_ASHR:
728  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
729  // The "number of bits to shift" operand must preserve its value as an
730  // unsigned integer:
731  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
732  widenScalarDst(MI, WideTy);
733  Observer.changedInstr(MI);
734  return Legalized;
735 
736  case TargetOpcode::G_UDIV:
737  case TargetOpcode::G_UREM:
738  case TargetOpcode::G_LSHR:
739  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
740  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ZEXT);
741  widenScalarDst(MI, WideTy);
742  Observer.changedInstr(MI);
743  return Legalized;
744 
745  case TargetOpcode::G_SELECT:
746  if (TypeIdx != 0)
747  return UnableToLegalize;
748  // Perform operation at larger width (any extension is fine here, high bits
749  // don't affect the result) and then truncate the result back to the
750  // original type.
751  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_ANYEXT);
752  widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_ANYEXT);
753  widenScalarDst(MI, WideTy);
754  Observer.changedInstr(MI);
755  return Legalized;
756 
757  case TargetOpcode::G_FPTOSI:
758  case TargetOpcode::G_FPTOUI:
759  if (TypeIdx != 0)
760  return UnableToLegalize;
761  widenScalarDst(MI, WideTy);
762  Observer.changedInstr(MI);
763  return Legalized;
764 
765  case TargetOpcode::G_SITOFP:
766  if (TypeIdx != 1)
767  return UnableToLegalize;
768  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_SEXT);
769  Observer.changedInstr(MI);
770  return Legalized;
771 
772  case TargetOpcode::G_UITOFP:
773  if (TypeIdx != 1)
774  return UnableToLegalize;
775  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ZEXT);
776  Observer.changedInstr(MI);
777  return Legalized;
778 
779  case TargetOpcode::G_INSERT:
780  if (TypeIdx != 0)
781  return UnableToLegalize;
782  widenScalarSrc(MI, WideTy, 1, TargetOpcode::G_ANYEXT);
783  widenScalarDst(MI, WideTy);
784  Observer.changedInstr(MI);
785  return Legalized;
786 
787  case TargetOpcode::G_LOAD:
788  // For some types like i24, we might try to widen to i32. To properly handle
789  // this we should be using a dedicated extending load, until then avoid
790  // trying to legalize.
791  if (alignTo(MRI.getType(MI.getOperand(0).getReg()).getSizeInBits(), 8) !=
792  WideTy.getSizeInBits())
793  return UnableToLegalize;
795  case TargetOpcode::G_SEXTLOAD:
796  case TargetOpcode::G_ZEXTLOAD:
797  widenScalarDst(MI, WideTy);
798  Observer.changedInstr(MI);
799  return Legalized;
800 
801  case TargetOpcode::G_STORE: {
802  if (MRI.getType(MI.getOperand(0).getReg()) != LLT::scalar(1) ||
803  WideTy != LLT::scalar(8))
804  return UnableToLegalize;
805 
806  widenScalarSrc(MI, WideTy, 0, TargetOpcode::G_ZEXT);
807  Observer.changedInstr(MI);
808  return Legalized;
809  }
810  case TargetOpcode::G_CONSTANT: {
811  MachineOperand &SrcMO = MI.getOperand(1);
813  const APInt &Val = SrcMO.getCImm()->getValue().sext(WideTy.getSizeInBits());
814  SrcMO.setCImm(ConstantInt::get(Ctx, Val));
815 
816  widenScalarDst(MI, WideTy);
817  Observer.changedInstr(MI);
818  return Legalized;
819  }
820  case TargetOpcode::G_FCONSTANT: {
821  MachineOperand &SrcMO = MI.getOperand(1);
823  APFloat Val = SrcMO.getFPImm()->getValueAPF();
824  bool LosesInfo;
825  switch (WideTy.getSizeInBits()) {
826  case 32:
828  break;
829  case 64:
831  break;
832  default:
833  llvm_unreachable("Unhandled fp widen type");
834  }
835  SrcMO.setFPImm(ConstantFP::get(Ctx, Val));
836 
837  widenScalarDst(MI, WideTy, 0, TargetOpcode::G_FPTRUNC);
838  Observer.changedInstr(MI);
839  return Legalized;
840  }
841  case TargetOpcode::G_BRCOND:
842  widenScalarSrc(MI, WideTy, 0, TargetOpcode::G_ANYEXT);
843  Observer.changedInstr(MI);
844  return Legalized;
845 
846  case TargetOpcode::G_FCMP:
847  if (TypeIdx == 0)
848  widenScalarDst(MI, WideTy);
849  else {
850  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_FPEXT);
851  widenScalarSrc(MI, WideTy, 3, TargetOpcode::G_FPEXT);
852  }
853  Observer.changedInstr(MI);
854  return Legalized;
855 
856  case TargetOpcode::G_ICMP:
857  if (TypeIdx == 0)
858  widenScalarDst(MI, WideTy);
859  else {
860  unsigned ExtOpcode = CmpInst::isSigned(static_cast<CmpInst::Predicate>(
861  MI.getOperand(1).getPredicate()))
862  ? TargetOpcode::G_SEXT
863  : TargetOpcode::G_ZEXT;
864  widenScalarSrc(MI, WideTy, 2, ExtOpcode);
865  widenScalarSrc(MI, WideTy, 3, ExtOpcode);
866  }
867  Observer.changedInstr(MI);
868  return Legalized;
869 
870  case TargetOpcode::G_GEP:
871  assert(TypeIdx == 1 && "unable to legalize pointer of GEP");
872  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
873  Observer.changedInstr(MI);
874  return Legalized;
875 
876  case TargetOpcode::G_PHI: {
877  assert(TypeIdx == 0 && "Expecting only Idx 0");
878 
879  for (unsigned I = 1; I < MI.getNumOperands(); I += 2) {
880  MachineBasicBlock &OpMBB = *MI.getOperand(I + 1).getMBB();
881  MIRBuilder.setInsertPt(OpMBB, OpMBB.getFirstTerminator());
882  widenScalarSrc(MI, WideTy, I, TargetOpcode::G_ANYEXT);
883  }
884 
885  MachineBasicBlock &MBB = *MI.getParent();
886  MIRBuilder.setInsertPt(MBB, --MBB.getFirstNonPHI());
887  widenScalarDst(MI, WideTy);
888  Observer.changedInstr(MI);
889  return Legalized;
890  }
891  case TargetOpcode::G_EXTRACT_VECTOR_ELT:
892  if (TypeIdx != 2)
893  return UnableToLegalize;
894  widenScalarSrc(MI, WideTy, 2, TargetOpcode::G_SEXT);
895  Observer.changedInstr(MI);
896  return Legalized;
897  }
898 }
899 
901 LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
902  using namespace TargetOpcode;
903  MIRBuilder.setInstr(MI);
904 
905  switch(MI.getOpcode()) {
906  default:
907  return UnableToLegalize;
908  case TargetOpcode::G_SREM:
909  case TargetOpcode::G_UREM: {
910  unsigned QuotReg = MRI.createGenericVirtualRegister(Ty);
911  MIRBuilder.buildInstr(MI.getOpcode() == G_SREM ? G_SDIV : G_UDIV)
912  .addDef(QuotReg)
913  .addUse(MI.getOperand(1).getReg())
914  .addUse(MI.getOperand(2).getReg());
915 
916  unsigned ProdReg = MRI.createGenericVirtualRegister(Ty);
917  MIRBuilder.buildMul(ProdReg, QuotReg, MI.getOperand(2).getReg());
919  ProdReg);
920  MI.eraseFromParent();
921  return Legalized;
922  }
923  case TargetOpcode::G_SMULO:
924  case TargetOpcode::G_UMULO: {
925  // Generate G_UMULH/G_SMULH to check for overflow and a normal G_MUL for the
926  // result.
927  unsigned Res = MI.getOperand(0).getReg();
928  unsigned Overflow = MI.getOperand(1).getReg();
929  unsigned LHS = MI.getOperand(2).getReg();
930  unsigned RHS = MI.getOperand(3).getReg();
931 
932  MIRBuilder.buildMul(Res, LHS, RHS);
933 
934  unsigned Opcode = MI.getOpcode() == TargetOpcode::G_SMULO
935  ? TargetOpcode::G_SMULH
936  : TargetOpcode::G_UMULH;
937 
938  unsigned HiPart = MRI.createGenericVirtualRegister(Ty);
939  MIRBuilder.buildInstr(Opcode)
940  .addDef(HiPart)
941  .addUse(LHS)
942  .addUse(RHS);
943 
944  unsigned Zero = MRI.createGenericVirtualRegister(Ty);
945  MIRBuilder.buildConstant(Zero, 0);
946 
947  // For *signed* multiply, overflow is detected by checking:
948  // (hi != (lo >> bitwidth-1))
949  if (Opcode == TargetOpcode::G_SMULH) {
950  unsigned Shifted = MRI.createGenericVirtualRegister(Ty);
951  unsigned ShiftAmt = MRI.createGenericVirtualRegister(Ty);
952  MIRBuilder.buildConstant(ShiftAmt, Ty.getSizeInBits() - 1);
953  MIRBuilder.buildInstr(TargetOpcode::G_ASHR)
954  .addDef(Shifted)
955  .addUse(Res)
956  .addUse(ShiftAmt);
957  MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Shifted);
958  } else {
959  MIRBuilder.buildICmp(CmpInst::ICMP_NE, Overflow, HiPart, Zero);
960  }
961  MI.eraseFromParent();
962  return Legalized;
963  }
964  case TargetOpcode::G_FNEG: {
965  // TODO: Handle vector types once we are able to
966  // represent them.
967  if (Ty.isVector())
968  return UnableToLegalize;
969  unsigned Res = MI.getOperand(0).getReg();
970  Type *ZeroTy;
972  switch (Ty.getSizeInBits()) {
973  case 16:
974  ZeroTy = Type::getHalfTy(Ctx);
975  break;
976  case 32:
977  ZeroTy = Type::getFloatTy(Ctx);
978  break;
979  case 64:
980  ZeroTy = Type::getDoubleTy(Ctx);
981  break;
982  case 128:
983  ZeroTy = Type::getFP128Ty(Ctx);
984  break;
985  default:
986  llvm_unreachable("unexpected floating-point type");
987  }
988  ConstantFP &ZeroForNegation =
989  *cast<ConstantFP>(ConstantFP::getZeroValueForNegation(ZeroTy));
990  auto Zero = MIRBuilder.buildFConstant(Ty, ZeroForNegation);
991  MIRBuilder.buildInstr(TargetOpcode::G_FSUB)
992  .addDef(Res)
993  .addUse(Zero->getOperand(0).getReg())
994  .addUse(MI.getOperand(1).getReg());
995  MI.eraseFromParent();
996  return Legalized;
997  }
998  case TargetOpcode::G_FSUB: {
999  // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)).
1000  // First, check if G_FNEG is marked as Lower. If so, we may
1001  // end up with an infinite loop as G_FSUB is used to legalize G_FNEG.
1002  if (LI.getAction({G_FNEG, {Ty}}).Action == Lower)
1003  return UnableToLegalize;
1004  unsigned Res = MI.getOperand(0).getReg();
1005  unsigned LHS = MI.getOperand(1).getReg();
1006  unsigned RHS = MI.getOperand(2).getReg();
1007  unsigned Neg = MRI.createGenericVirtualRegister(Ty);
1008  MIRBuilder.buildInstr(TargetOpcode::G_FNEG).addDef(Neg).addUse(RHS);
1009  MIRBuilder.buildInstr(TargetOpcode::G_FADD)
1010  .addDef(Res)
1011  .addUse(LHS)
1012  .addUse(Neg);
1013  MI.eraseFromParent();
1014  return Legalized;
1015  }
1016  case TargetOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: {
1017  unsigned OldValRes = MI.getOperand(0).getReg();
1018  unsigned SuccessRes = MI.getOperand(1).getReg();
1019  unsigned Addr = MI.getOperand(2).getReg();
1020  unsigned CmpVal = MI.getOperand(3).getReg();
1021  unsigned NewVal = MI.getOperand(4).getReg();
1022  MIRBuilder.buildAtomicCmpXchg(OldValRes, Addr, CmpVal, NewVal,
1023  **MI.memoperands_begin());
1024  MIRBuilder.buildICmp(CmpInst::ICMP_EQ, SuccessRes, OldValRes, CmpVal);
1025  MI.eraseFromParent();
1026  return Legalized;
1027  }
1028  case TargetOpcode::G_LOAD:
1029  case TargetOpcode::G_SEXTLOAD:
1030  case TargetOpcode::G_ZEXTLOAD: {
1031  // Lower to a memory-width G_LOAD and a G_SEXT/G_ZEXT/G_ANYEXT
1032  unsigned DstReg = MI.getOperand(0).getReg();
1033  unsigned PtrReg = MI.getOperand(1).getReg();
1034  LLT DstTy = MRI.getType(DstReg);
1035  auto &MMO = **MI.memoperands_begin();
1036 
1037  if (DstTy.getSizeInBits() == MMO.getSize() /* in bytes */ * 8) {
1038  // In the case of G_LOAD, this was a non-extending load already and we're
1039  // about to lower to the same instruction.
1040  if (MI.getOpcode() == TargetOpcode::G_LOAD)
1041  return UnableToLegalize;
1042  MIRBuilder.buildLoad(DstReg, PtrReg, MMO);
1043  MI.eraseFromParent();
1044  return Legalized;
1045  }
1046 
1047  if (DstTy.isScalar()) {
1048  unsigned TmpReg = MRI.createGenericVirtualRegister(
1049  LLT::scalar(MMO.getSize() /* in bytes */ * 8));
1050  MIRBuilder.buildLoad(TmpReg, PtrReg, MMO);
1051  switch (MI.getOpcode()) {
1052  default:
1053  llvm_unreachable("Unexpected opcode");
1054  case TargetOpcode::G_LOAD:
1055  MIRBuilder.buildAnyExt(DstReg, TmpReg);
1056  break;
1057  case TargetOpcode::G_SEXTLOAD:
1058  MIRBuilder.buildSExt(DstReg, TmpReg);
1059  break;
1060  case TargetOpcode::G_ZEXTLOAD:
1061  MIRBuilder.buildZExt(DstReg, TmpReg);
1062  break;
1063  }
1064  MI.eraseFromParent();
1065  return Legalized;
1066  }
1067 
1068  return UnableToLegalize;
1069  }
1070  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
1071  case TargetOpcode::G_CTTZ_ZERO_UNDEF:
1072  case TargetOpcode::G_CTLZ:
1073  case TargetOpcode::G_CTTZ:
1074  case TargetOpcode::G_CTPOP:
1075  return lowerBitCount(MI, TypeIdx, Ty);
1076  }
1077 }
1078 
1081  LLT NarrowTy) {
1082  // FIXME: Don't know how to handle secondary types yet.
1083  if (TypeIdx != 0)
1084  return UnableToLegalize;
1085  switch (MI.getOpcode()) {
1086  default:
1087  return UnableToLegalize;
1088  case TargetOpcode::G_ADD: {
1089  unsigned NarrowSize = NarrowTy.getSizeInBits();
1090  unsigned DstReg = MI.getOperand(0).getReg();
1091  unsigned Size = MRI.getType(DstReg).getSizeInBits();
1092  int NumParts = Size / NarrowSize;
1093  // FIXME: Don't know how to handle the situation where the small vectors
1094  // aren't all the same size yet.
1095  if (Size % NarrowSize != 0)
1096  return UnableToLegalize;
1097 
1098  MIRBuilder.setInstr(MI);
1099 
1100  SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
1101  extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
1102  extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
1103 
1104  for (int i = 0; i < NumParts; ++i) {
1105  unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
1106  MIRBuilder.buildAdd(DstReg, Src1Regs[i], Src2Regs[i]);
1107  DstRegs.push_back(DstReg);
1108  }
1109 
1110  MIRBuilder.buildMerge(DstReg, DstRegs);
1111  MI.eraseFromParent();
1112  return Legalized;
1113  }
1114  }
1115 }
1116 
1118 LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
1119  unsigned Opc = MI.getOpcode();
1120  auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
1121  auto isSupported = [this](const LegalityQuery &Q) {
1122  auto QAction = LI.getAction(Q).Action;
1123  return QAction == Legal || QAction == Libcall || QAction == Custom;
1124  };
1125  switch (Opc) {
1126  default:
1127  return UnableToLegalize;
1128  case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
1129  // This trivially expands to CTLZ.
1130  MI.setDesc(TII.get(TargetOpcode::G_CTLZ));
1131  Observer.changedInstr(MI);
1132  return Legalized;
1133  }
1134  case TargetOpcode::G_CTLZ: {
1135  unsigned SrcReg = MI.getOperand(1).getReg();
1136  unsigned Len = Ty.getSizeInBits();
1137  if (isSupported({TargetOpcode::G_CTLZ_ZERO_UNDEF, {Ty}})) {
1138  // If CTLZ_ZERO_UNDEF is supported, emit that and a select for zero.
1139  auto MIBCtlzZU =
1140  MIRBuilder.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, Ty, SrcReg);
1141  auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
1142  auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
1143  auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
1144  SrcReg, MIBZero);
1145  MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
1146  MIBCtlzZU);
1147  MI.eraseFromParent();
1148  return Legalized;
1149  }
1150  // for now, we do this:
1151  // NewLen = NextPowerOf2(Len);
1152  // x = x | (x >> 1);
1153  // x = x | (x >> 2);
1154  // ...
1155  // x = x | (x >>16);
1156  // x = x | (x >>32); // for 64-bit input
1157  // Upto NewLen/2
1158  // return Len - popcount(x);
1159  //
1160  // Ref: "Hacker's Delight" by Henry Warren
1161  unsigned Op = SrcReg;
1162  unsigned NewLen = PowerOf2Ceil(Len);
1163  for (unsigned i = 0; (1U << i) <= (NewLen / 2); ++i) {
1164  auto MIBShiftAmt = MIRBuilder.buildConstant(Ty, 1ULL << i);
1165  auto MIBOp = MIRBuilder.buildInstr(
1166  TargetOpcode::G_OR, Ty, Op,
1167  MIRBuilder.buildInstr(TargetOpcode::G_LSHR, Ty, Op, MIBShiftAmt));
1168  Op = MIBOp->getOperand(0).getReg();
1169  }
1170  auto MIBPop = MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, Ty, Op);
1171  MIRBuilder.buildInstr(TargetOpcode::G_SUB, MI.getOperand(0).getReg(),
1172  MIRBuilder.buildConstant(Ty, Len), MIBPop);
1173  MI.eraseFromParent();
1174  return Legalized;
1175  }
1176  case TargetOpcode::G_CTTZ_ZERO_UNDEF: {
1177  // This trivially expands to CTTZ.
1178  MI.setDesc(TII.get(TargetOpcode::G_CTTZ));
1179  Observer.changedInstr(MI);
1180  return Legalized;
1181  }
1182  case TargetOpcode::G_CTTZ: {
1183  unsigned SrcReg = MI.getOperand(1).getReg();
1184  unsigned Len = Ty.getSizeInBits();
1185  if (isSupported({TargetOpcode::G_CTTZ_ZERO_UNDEF, {Ty}})) {
1186  // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with
1187  // zero.
1188  auto MIBCttzZU =
1189  MIRBuilder.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, Ty, SrcReg);
1190  auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
1191  auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
1192  auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
1193  SrcReg, MIBZero);
1194  MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
1195  MIBCttzZU);
1196  MI.eraseFromParent();
1197  return Legalized;
1198  }
1199  // for now, we use: { return popcount(~x & (x - 1)); }
1200  // unless the target has ctlz but not ctpop, in which case we use:
1201  // { return 32 - nlz(~x & (x-1)); }
1202  // Ref: "Hacker's Delight" by Henry Warren
1203  auto MIBCstNeg1 = MIRBuilder.buildConstant(Ty, -1);
1204  auto MIBNot =
1205  MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, SrcReg, MIBCstNeg1);
1206  auto MIBTmp = MIRBuilder.buildInstr(
1207  TargetOpcode::G_AND, Ty, MIBNot,
1208  MIRBuilder.buildInstr(TargetOpcode::G_ADD, Ty, SrcReg, MIBCstNeg1));
1209  if (!isSupported({TargetOpcode::G_CTPOP, {Ty}}) &&
1210  isSupported({TargetOpcode::G_CTLZ, {Ty}})) {
1211  auto MIBCstLen = MIRBuilder.buildConstant(Ty, Len);
1213  TargetOpcode::G_SUB, MI.getOperand(0).getReg(),
1214  MIBCstLen,
1215  MIRBuilder.buildInstr(TargetOpcode::G_CTLZ, Ty, MIBTmp));
1216  MI.eraseFromParent();
1217  return Legalized;
1218  }
1219  MI.setDesc(TII.get(TargetOpcode::G_CTPOP));
1220  MI.getOperand(1).setReg(MIBTmp->getOperand(0).getReg());
1221  return Legalized;
1222  }
1223  }
1224 }
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.
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:1563
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
void setChangeObserver(GISelChangeObserver &Observer)
MachineBasicBlock * getMBB() const
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
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:58
void setFPImm(const ConstantFP *CFP)
MachineInstrBuilder buildStore(unsigned Val, unsigned Addr, MachineMemOperand &MMO)
Build and insert G_STORE Val, Addr, MMO.
void push_back(const T &Elt)
Definition: SmallVector.h:218
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:63
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...
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type...
Definition: LegalizerInfo.h:53
bool isVector() const
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
A description of a memory reference used in the backend.
amdgpu Simplify well known AMD library false Value Value const Twine & Name
bool isSigned() const
Definition: InstrTypes.h:812
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
Retuns the total number of operands.
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.
LegalizerHelper(MachineFunction &MF, GISelChangeObserver &Observer)
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:610
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
static unsigned getScalarSizeInBits(Type *Ty)
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:82
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:618
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:681
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.
virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder, GISelChangeObserver &Observer) const
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, ...
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:745
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:48
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
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