LLVM 24.0.0git
LegalizationArtifactCombiner.h
Go to the documentation of this file.
1//===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// This file contains some helper functions which try to cleanup artifacts
9// such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
10// the types match. This file also contains some combines of merges that happens
11// at the end of the legalization.
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H
15#define LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H
16
28#include "llvm/IR/Constants.h"
30#include "llvm/Support/Debug.h"
31
32#define DEBUG_TYPE "legalizer"
33
34namespace llvm {
36 MachineIRBuilder &Builder;
38 const LegalizerInfo &LI;
40
41 static bool isArtifactCast(unsigned Opc) {
42 switch (Opc) {
43 case TargetOpcode::G_TRUNC:
44 case TargetOpcode::G_SEXT:
45 case TargetOpcode::G_ZEXT:
46 case TargetOpcode::G_ANYEXT:
47 return true;
48 default:
49 return false;
50 }
51 }
52
53public:
55 const LegalizerInfo &LI,
56 GISelValueTracking *VT = nullptr)
57 : Builder(B), MRI(MRI), LI(LI), VT(VT) {}
58
61 SmallVectorImpl<Register> &UpdatedDefs,
62 GISelObserverWrapper &Observer) {
63 using namespace llvm::MIPatternMatch;
64 assert(MI.getOpcode() == TargetOpcode::G_ANYEXT);
65
66 Builder.setInstrAndDebugLoc(MI);
67 Register DstReg = MI.getOperand(0).getReg();
68 Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
69
70 // aext(trunc x) - > aext/copy/trunc x
71 Register TruncSrc;
72 if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
73 LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);
74 if (MRI.getType(DstReg) == MRI.getType(TruncSrc))
75 replaceRegOrBuildCopy(DstReg, TruncSrc, MRI, Builder, UpdatedDefs,
76 Observer);
77 else
78 Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
79 UpdatedDefs.push_back(DstReg);
80 markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
81 return true;
82 }
83
84 // aext([asz]ext x) -> [asz]ext x
85 Register ExtSrc;
86 MachineInstr *ExtMI;
87 if (mi_match(SrcReg, MRI,
88 m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
89 m_GSExt(m_Reg(ExtSrc)),
90 m_GZExt(m_Reg(ExtSrc)))))) {
91 Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
92 UpdatedDefs.push_back(DstReg);
93 markInstAndDefDead(MI, *ExtMI, DeadInsts);
94 return true;
95 }
96
97 // Try to fold aext(g_constant) when the larger constant type is legal.
98 GConstant *SrcCst;
99 if (mi_match(SrcReg, MRI, m_GConstant(SrcCst))) {
100 const LLT DstTy = MRI.getType(DstReg);
101 if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
102 auto MergedLocation = DebugLoc::getMergedLocation(
103 MI.getDebugLoc(), SrcCst->getDebugLoc());
104 // Set the debug location to the merged location of the SrcCst and the
105 // MI if the aext fold is successful.
106 Builder.setDebugLoc(MergedLocation);
107 Builder.buildConstant(DstReg,
108 SrcCst->getValue().sext(DstTy.getSizeInBits()));
109 UpdatedDefs.push_back(DstReg);
110 markInstAndDefDead(MI, *SrcCst, DeadInsts);
111 return true;
112 }
113 }
114 return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs, Observer);
115 }
116
119 SmallVectorImpl<Register> &UpdatedDefs,
120 GISelObserverWrapper &Observer) {
121 using namespace llvm::MIPatternMatch;
122 assert(MI.getOpcode() == TargetOpcode::G_ZEXT);
123
124 Builder.setInstrAndDebugLoc(MI);
125 Register DstReg = MI.getOperand(0).getReg();
126 Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
127
128 // zext(trunc x) - > and (aext/copy/trunc x), mask
129 // zext(sext x) -> and (sext x), mask
130 Register TruncSrc;
131 Register SextSrc;
132 if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc))) ||
133 mi_match(SrcReg, MRI, m_GSExt(m_Reg(SextSrc)))) {
134 LLT DstTy = MRI.getType(DstReg);
135 if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
136 isConstantUnsupported(DstTy))
137 return false;
138 LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);
139 LLT SrcTy = MRI.getType(SrcReg);
140 APInt MaskVal = APInt::getAllOnes(SrcTy.getScalarSizeInBits());
141 if (SextSrc && (DstTy != MRI.getType(SextSrc)))
142 SextSrc = Builder.buildSExtOrTrunc(DstTy, SextSrc).getReg(0);
143 if (TruncSrc && (DstTy != MRI.getType(TruncSrc)))
144 TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);
145 APInt ExtMaskVal = MaskVal.zext(DstTy.getScalarSizeInBits());
146 Register AndSrc = SextSrc ? SextSrc : TruncSrc;
147 // Elide G_AND and mask constant if possible.
148 // The G_AND would also be removed by the post-legalize redundant_and
149 // combine, but in this very common case, eliding early and regardless of
150 // OptLevel results in significant compile-time and O0 code-size
151 // improvements. Inserting unnecessary instructions between boolean defs
152 // and uses hinders a lot of folding during ISel.
153 if (VT && (VT->getKnownZeroes(AndSrc) | ExtMaskVal).isAllOnes()) {
154 replaceRegOrBuildCopy(DstReg, AndSrc, MRI, Builder, UpdatedDefs,
155 Observer);
156 } else {
157 auto Mask = Builder.buildConstant(DstTy, ExtMaskVal);
158 Builder.buildAnd(DstReg, AndSrc, Mask);
159 }
160 markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
161 return true;
162 }
163
164 // zext(zext x) -> (zext x)
165 Register ZextSrc;
166 if (mi_match(SrcReg, MRI, m_GZExt(m_Reg(ZextSrc)))) {
167 LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);
168 Observer.changingInstr(MI);
169 MI.getOperand(1).setReg(ZextSrc);
170 Observer.changedInstr(MI);
171 UpdatedDefs.push_back(DstReg);
172 markDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
173 return true;
174 }
175
176 // Try to fold zext(g_constant) when the larger constant type is legal.
177 GConstant *SrcCst;
178 if (mi_match(SrcReg, MRI, m_GConstant(SrcCst))) {
179 const LLT DstTy = MRI.getType(DstReg);
180 if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
181 Builder.buildConstant(DstReg,
182 SrcCst->getValue().zext(DstTy.getSizeInBits()));
183 UpdatedDefs.push_back(DstReg);
184 markInstAndDefDead(MI, *SrcCst, DeadInsts);
185 return true;
186 }
187 }
188 return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs, Observer);
189 }
190
193 SmallVectorImpl<Register> &UpdatedDefs,
194 GISelObserverWrapper &Observer) {
195 using namespace llvm::MIPatternMatch;
196 assert(MI.getOpcode() == TargetOpcode::G_SEXT);
197
198 Builder.setInstrAndDebugLoc(MI);
199 Register DstReg = MI.getOperand(0).getReg();
200 Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
201
202 // sext(trunc x) - > (sext_inreg (aext/copy/trunc x), c)
203 Register TruncSrc;
204 if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
205 LLT DstTy = MRI.getType(DstReg);
206 LLT SrcTy = MRI.getType(SrcReg);
207 uint64_t SizeInBits = SrcTy.getScalarSizeInBits();
208 if (isInstUnsupported({TargetOpcode::G_SEXT_INREG,
209 {DstTy},
210 {},
211 {static_cast<int64_t>(SizeInBits)}}))
212 return false;
213 LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);
214 if (DstTy != MRI.getType(TruncSrc))
215 TruncSrc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc).getReg(0);
216 // Elide G_SEXT_INREG if possible. This is similar to eliding G_AND in
217 // tryCombineZExt. Refer to the comment in tryCombineZExt for rationale.
218 if (VT && VT->computeNumSignBits(TruncSrc) >
219 DstTy.getScalarSizeInBits() - SizeInBits)
220 replaceRegOrBuildCopy(DstReg, TruncSrc, MRI, Builder, UpdatedDefs,
221 Observer);
222 else
223 Builder.buildSExtInReg(DstReg, TruncSrc, SizeInBits);
224 markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
225 return true;
226 }
227
228 // sext(zext x) -> (zext x)
229 // sext(sext x) -> (sext x)
230 Register ExtSrc;
231 MachineInstr *ExtMI;
232 if (mi_match(SrcReg, MRI,
233 m_all_of(m_MInstr(ExtMI), m_any_of(m_GZExt(m_Reg(ExtSrc)),
234 m_GSExt(m_Reg(ExtSrc)))))) {
235 LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI);
236 Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
237 UpdatedDefs.push_back(DstReg);
238 markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
239 return true;
240 }
241
242 // Try to fold sext(g_constant) when the larger constant type is legal.
243 GConstant *SrcCst;
244 if (mi_match(SrcReg, MRI, m_GConstant(SrcCst))) {
245 const LLT DstTy = MRI.getType(DstReg);
246 if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
247 Builder.buildConstant(DstReg,
248 SrcCst->getValue().sext(DstTy.getSizeInBits()));
249 UpdatedDefs.push_back(DstReg);
250 markInstAndDefDead(MI, *SrcCst, DeadInsts);
251 return true;
252 }
253 }
254
255 return tryFoldImplicitDef(MI, DeadInsts, UpdatedDefs, Observer);
256 }
257
260 SmallVectorImpl<Register> &UpdatedDefs,
261 GISelObserverWrapper &Observer) {
262 using namespace llvm::MIPatternMatch;
263 assert(MI.getOpcode() == TargetOpcode::G_TRUNC);
264
265 Builder.setInstrAndDebugLoc(MI);
266 Register DstReg = MI.getOperand(0).getReg();
267 const LLT DstTy = MRI.getType(DstReg);
268 Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
269
270 // Try to fold trunc(g_constant) when the smaller constant type is legal.
271 GConstant *SrcCst;
272 if (mi_match(SrcReg, MRI, m_GConstant(SrcCst))) {
273 if (isInstLegal({TargetOpcode::G_CONSTANT, {DstTy}})) {
274 Builder.buildConstant(DstReg,
275 SrcCst->getValue().trunc(DstTy.getSizeInBits()));
276 UpdatedDefs.push_back(DstReg);
277 markInstAndDefDead(MI, *SrcCst, DeadInsts);
278 return true;
279 }
280 }
281
282 // Try to fold trunc(merge) to directly use the source of the merge.
283 // This gets rid of large, difficult to legalize, merges
284 MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
285 if (auto *SrcMerge = dyn_cast<GMerge>(SrcMI)) {
286 const Register MergeSrcReg = SrcMerge->getSourceReg(0);
287 const LLT MergeSrcTy = MRI.getType(MergeSrcReg);
288
289 // We can only fold if the types are scalar
290 const unsigned DstSize = DstTy.getSizeInBits();
291 const unsigned MergeSrcSize = MergeSrcTy.getSizeInBits();
292 if (!DstTy.isScalar() || !MergeSrcTy.isScalar())
293 return false;
294
295 // G_TRUNC/G_MERGE_VALUES operate on the raw bit pattern - if the merge
296 // feeds us float sources, reinterpret them as integers of the same size
297 // so we never emit a G_TRUNC or G_MERGE_VALUES with a floating-point
298 // source operand.
299 const LLT WorkTy =
300 MergeSrcTy.isFloat() ? LLT::integer(MergeSrcSize) : MergeSrcTy;
301 auto AsInt = [&](Register R) {
302 if (MergeSrcTy != WorkTy)
303 return Builder.buildBitcast(WorkTy, R).getReg(0);
304 return R;
305 };
306
307 if (DstSize < MergeSrcSize) {
308 // When the merge source is larger than the destination, we can just
309 // truncate the merge source directly
310 if (isInstUnsupported({TargetOpcode::G_TRUNC, {DstTy, WorkTy}}))
311 return false;
312
313 LLVM_DEBUG(dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_TRUNC: "
314 << MI);
315
316 Builder.buildTrunc(DstReg, AsInt(MergeSrcReg));
317 UpdatedDefs.push_back(DstReg);
318 } else if (DstSize == MergeSrcSize) {
319 // If the sizes match we can simply try to replace the register
321 dbgs() << "Replacing G_TRUNC(G_MERGE_VALUES) with merge input: "
322 << MI);
323 replaceRegOrBuildCopy(DstReg, AsInt(MergeSrcReg), MRI, Builder,
324 UpdatedDefs, Observer);
325 } else if (DstSize % MergeSrcSize == 0) {
326 // If the trunc size is a multiple of the merge source size we can use
327 // a smaller merge instead
328 if (isInstUnsupported({TargetOpcode::G_MERGE_VALUES, {DstTy, WorkTy}}))
329 return false;
330
332 dbgs() << "Combining G_TRUNC(G_MERGE_VALUES) to G_MERGE_VALUES: "
333 << MI);
334
335 const unsigned NumSrcs = DstSize / MergeSrcSize;
336 assert(NumSrcs < SrcMI->getNumOperands() - 1 &&
337 "trunc(merge) should require less inputs than merge");
338 SmallVector<Register, 8> SrcRegs(NumSrcs);
339 for (unsigned i = 0; i < NumSrcs; ++i)
340 SrcRegs[i] = AsInt(SrcMerge->getSourceReg(i));
341
342 Builder.buildMergeValues(DstReg, SrcRegs);
343 UpdatedDefs.push_back(DstReg);
344 } else {
345 // Unable to combine
346 return false;
347 }
348
349 markInstAndDefDead(MI, *SrcMerge, DeadInsts);
350 return true;
351 }
352
353 // trunc(trunc) -> trunc
354 Register TruncSrc;
355 if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
356 // Always combine trunc(trunc) since the eventual resulting trunc must be
357 // legal anyway as it must be legal for all outputs of the consumer type
358 // set.
359 LLVM_DEBUG(dbgs() << ".. Combine G_TRUNC(G_TRUNC): " << MI);
360
361 Builder.buildTrunc(DstReg, TruncSrc);
362 UpdatedDefs.push_back(DstReg);
363 markInstAndDefDead(MI, *MRI.getVRegDef(TruncSrc), DeadInsts);
364 return true;
365 }
366
367 // trunc(ext x) -> x
368 ArtifactValueFinder Finder(MRI, Builder, LI);
369 if (Register FoundReg =
370 Finder.findValueFromDef(DstReg, 0, DstTy.getSizeInBits(), DstTy)) {
371 LLT FoundRegTy = MRI.getType(FoundReg);
372 if (DstTy == FoundRegTy) {
373 LLVM_DEBUG(dbgs() << ".. Combine G_TRUNC(G_[S,Z,ANY]EXT/G_TRUNC...): "
374 << MI);
375
376 replaceRegOrBuildCopy(DstReg, FoundReg, MRI, Builder, UpdatedDefs,
377 Observer);
378 UpdatedDefs.push_back(DstReg);
379 markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
380 return true;
381 }
382 }
383
384 return false;
385 }
386
387 /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
390 SmallVectorImpl<Register> &UpdatedDefs,
391 GISelObserverWrapper &Observer) {
392 unsigned Opcode = MI.getOpcode();
393 assert(Opcode == TargetOpcode::G_ANYEXT || Opcode == TargetOpcode::G_ZEXT ||
394 Opcode == TargetOpcode::G_SEXT);
395
396 if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
397 MI.getOperand(1).getReg(), MRI)) {
398 Builder.setInstrAndDebugLoc(MI);
399 Register DstReg = MI.getOperand(0).getReg();
400 LLT DstTy = MRI.getType(DstReg);
401
402 if (Opcode == TargetOpcode::G_ANYEXT) {
403 // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
404 if (!isInstLegal({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
405 return false;
406 LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI);
407 auto Impl = Builder.buildUndef(DstTy);
408 replaceRegOrBuildCopy(DstReg, Impl.getReg(0), MRI, Builder, UpdatedDefs,
409 Observer);
410 UpdatedDefs.push_back(DstReg);
411 } else {
412 // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
413 // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
414 if (isConstantUnsupported(DstTy))
415 return false;
416 LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI);
417 auto Cnst = Builder.buildConstant(DstTy, 0);
418 replaceRegOrBuildCopy(DstReg, Cnst.getReg(0), MRI, Builder, UpdatedDefs,
419 Observer);
420 UpdatedDefs.push_back(DstReg);
421 }
422
423 markInstAndDefDead(MI, *DefMI, DeadInsts);
424 return true;
425 }
426 return false;
427 }
428
431 SmallVectorImpl<Register> &UpdatedDefs) {
432
433 assert(MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES);
434
435 const unsigned CastOpc = CastMI.getOpcode();
436
437 if (!isArtifactCast(CastOpc))
438 return false;
439
440 const unsigned NumDefs = MI.getNumOperands() - 1;
441
442 const Register CastSrcReg = CastMI.getOperand(1).getReg();
443 const LLT CastSrcTy = MRI.getType(CastSrcReg);
444 const LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
445 const LLT SrcTy = MRI.getType(MI.getOperand(NumDefs).getReg());
446
447 const unsigned CastSrcSize = CastSrcTy.getSizeInBits();
448 const unsigned DestSize = DestTy.getSizeInBits();
449
450 if (CastOpc == TargetOpcode::G_TRUNC) {
451 if (SrcTy.isVector() && SrcTy.getScalarType() == DestTy.getScalarType()) {
452 // %1:_(<4 x s8>) = G_TRUNC %0(<4 x s32>)
453 // %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %1
454 // =>
455 // %6:_(s32), %7:_(s32), %8:_(s32), %9:_(s32) = G_UNMERGE_VALUES %0
456 // %2:_(s8) = G_TRUNC %6
457 // %3:_(s8) = G_TRUNC %7
458 // %4:_(s8) = G_TRUNC %8
459 // %5:_(s8) = G_TRUNC %9
460
461 unsigned UnmergeNumElts =
462 DestTy.isVector() ? CastSrcTy.getNumElements() / NumDefs : 1;
463 LLT UnmergeTy = CastSrcTy.changeElementCount(
464 ElementCount::getFixed(UnmergeNumElts));
465 LLT SrcWideTy =
466 SrcTy.changeElementCount(ElementCount::getFixed(UnmergeNumElts));
467
468 if (isInstUnsupported(
469 {TargetOpcode::G_UNMERGE_VALUES, {UnmergeTy, CastSrcTy}}) ||
470 LI.getAction({TargetOpcode::G_TRUNC, {SrcWideTy, UnmergeTy}})
472 return false;
473
474 Builder.setInstrAndDebugLoc(MI);
475 auto NewUnmerge = Builder.buildUnmerge(UnmergeTy, CastSrcReg);
476
477 for (unsigned I = 0; I != NumDefs; ++I) {
478 Register DefReg = MI.getOperand(I).getReg();
479 UpdatedDefs.push_back(DefReg);
480 Builder.buildTrunc(DefReg, NewUnmerge.getReg(I));
481 }
482
483 markInstAndDefDead(MI, CastMI, DeadInsts);
484 return true;
485 }
486
487 if (CastSrcTy.isScalar() && SrcTy.isScalar() && !DestTy.isVector()) {
488 // %1:_(s16) = G_TRUNC %0(s32)
489 // %2:_(s8), %3:_(s8) = G_UNMERGE_VALUES %1
490 // =>
491 // %2:_(s8), %3:_(s8), %4:_(s8), %5:_(s8) = G_UNMERGE_VALUES %0
492
493 // Unmerge(trunc) can be combined if the trunc source size is a multiple
494 // of the unmerge destination size
495 if (CastSrcSize % DestSize != 0)
496 return false;
497
498 // Check if the new unmerge is supported
499 if (isInstUnsupported(
500 {TargetOpcode::G_UNMERGE_VALUES, {DestTy, CastSrcTy}}))
501 return false;
502
503 // Gather the original destination registers and create new ones for the
504 // unused bits
505 const unsigned NewNumDefs = CastSrcSize / DestSize;
506 SmallVector<Register, 8> DstRegs(NewNumDefs);
507 for (unsigned Idx = 0; Idx < NewNumDefs; ++Idx) {
508 if (Idx < NumDefs)
509 DstRegs[Idx] = MI.getOperand(Idx).getReg();
510 else
511 DstRegs[Idx] = MRI.createGenericVirtualRegister(DestTy);
512 }
513
514 // Build new unmerge
515 Builder.setInstrAndDebugLoc(MI);
516 Builder.buildUnmerge(DstRegs, CastSrcReg);
517 UpdatedDefs.append(DstRegs.begin(), DstRegs.begin() + NewNumDefs);
518 markInstAndDefDead(MI, CastMI, DeadInsts);
519 return true;
520 }
521 }
522
523 // TODO: support combines with other casts as well
524 return false;
525 }
526
527 static bool canFoldMergeOpcode(unsigned MergeOp, unsigned ConvertOp,
528 LLT OpTy, LLT DestTy) {
529 // Check if we found a definition that is like G_MERGE_VALUES.
530 switch (MergeOp) {
531 default:
532 return false;
533 case TargetOpcode::G_BUILD_VECTOR:
534 case TargetOpcode::G_MERGE_VALUES:
535 // The convert operation that we will need to insert is
536 // going to convert the input of that type of instruction (scalar)
537 // to the destination type (DestTy).
538 // The conversion needs to stay in the same domain (scalar to scalar
539 // and vector to vector), so if we were to allow to fold the merge
540 // we would need to insert some bitcasts.
541 // E.g.,
542 // <2 x s16> = build_vector s16, s16
543 // <2 x s32> = zext <2 x s16>
544 // <2 x s16>, <2 x s16> = unmerge <2 x s32>
545 //
546 // As is the folding would produce:
547 // <2 x s16> = zext s16 <-- scalar to vector
548 // <2 x s16> = zext s16 <-- scalar to vector
549 // Which is invalid.
550 // Instead we would want to generate:
551 // s32 = zext s16
552 // <2 x s16> = bitcast s32
553 // s32 = zext s16
554 // <2 x s16> = bitcast s32
555 //
556 // That is not done yet.
557 if (ConvertOp == 0)
558 return true;
559 return !DestTy.isVector() && OpTy.isVector() &&
560 DestTy == OpTy.getElementType();
561 case TargetOpcode::G_CONCAT_VECTORS: {
562 if (ConvertOp == 0)
563 return true;
564 if (!DestTy.isVector())
565 return false;
566
567 const unsigned OpEltSize = OpTy.getElementType().getSizeInBits();
568
569 // Don't handle scalarization with a cast that isn't in the same
570 // direction as the vector cast. This could be handled, but it would
571 // require more intermediate unmerges.
572 if (ConvertOp == TargetOpcode::G_TRUNC)
573 return DestTy.getSizeInBits() <= OpEltSize;
574 return DestTy.getSizeInBits() >= OpEltSize;
575 }
576 }
577 }
578
579 /// Try to replace DstReg with SrcReg or build a COPY instruction
580 /// depending on the register constraints.
581 static void replaceRegOrBuildCopy(Register DstReg, Register SrcReg,
583 MachineIRBuilder &Builder,
584 SmallVectorImpl<Register> &UpdatedDefs,
585 GISelChangeObserver &Observer) {
586 if (!llvm::canReplaceReg(DstReg, SrcReg, MRI)) {
587 // Move the def of DstReg to the COPY, so that DstReg does not get a
588 // second def either.
589 MachineOperand &DefMO = *MRI.def_begin(DstReg);
590 MachineInstr &DefMI = *DefMO.getParent();
591 Observer.changingInstr(DefMI);
592 DefMO.setReg(MRI.createGenericVirtualRegister(MRI.getType(DstReg)));
593 Observer.changedInstr(DefMI);
594 Builder.buildCopy(DstReg, SrcReg);
595 UpdatedDefs.push_back(DstReg);
596 return;
597 }
599 // Get the users and notify the observer before replacing.
600 for (auto &UseMI : MRI.use_instructions(DstReg)) {
601 UseMIs.push_back(&UseMI);
602 Observer.changingInstr(UseMI);
603 }
604 // Replace the uses only, so that SrcReg does not get a second def.
605 for (MachineOperand &MO :
606 llvm::make_early_inc_range(MRI.use_operands(DstReg)))
607 MO.setReg(SrcReg);
608 UpdatedDefs.push_back(SrcReg);
609 // Notify the observer that we changed the instructions.
610 for (auto *UseMI : UseMIs)
611 Observer.changedInstr(*UseMI);
612 }
613
614 /// Return the operand index in \p MI that defines \p Def
615 static unsigned getDefIndex(const MachineInstr &MI, Register SearchDef) {
616 unsigned DefIdx = 0;
617 for (const MachineOperand &Def : MI.defs()) {
618 if (Def.getReg() == SearchDef)
619 break;
620 ++DefIdx;
621 }
622
623 return DefIdx;
624 }
625
626 /// This class provides utilities for finding source registers of specific
627 /// bit ranges in an artifact. The routines can look through the source
628 /// registers if they're other artifacts to try to find a non-artifact source
629 /// of a value.
632 MachineIRBuilder &MIB;
633 const LegalizerInfo &LI;
634
635 // Stores the best register found in the current query so far.
636 Register CurrentBest = Register();
637
638 /// Given an concat_vector op \p Concat and a start bit and size, try to
639 /// find the origin of the value defined by that start position and size.
640 ///
641 /// \returns a register with the requested size, or the current best
642 /// register found during the current query.
643 Register findValueFromConcat(GConcatVectors &Concat, unsigned StartBit,
644 unsigned Size) {
645 assert(Size > 0);
646
647 // Find the source operand that provides the bits requested.
648 Register Src1Reg = Concat.getSourceReg(0);
649 unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();
650
651 // Operand index of the source that provides the start of the bit range.
652 unsigned StartSrcIdx = (StartBit / SrcSize) + 1;
653 // Offset into the source at which the bit range starts.
654 unsigned InRegOffset = StartBit % SrcSize;
655 // Check that the bits don't span multiple sources.
656 // FIXME: we might be able return multiple sources? Or create an
657 // appropriate concat to make it fit.
658 if (InRegOffset + Size > SrcSize)
659 return CurrentBest;
660
661 Register SrcReg = Concat.getReg(StartSrcIdx);
662 if (InRegOffset == 0 && Size == SrcSize) {
663 CurrentBest = SrcReg;
664 return findValueFromDefImpl(SrcReg, 0, Size, MRI.getType(SrcReg));
665 }
666
667 return findValueFromDefImpl(SrcReg, InRegOffset, Size,
668 MRI.getType(SrcReg));
669 }
670
671 /// Given an build_vector op \p BV and a start bit and size, try to find
672 /// the origin of the value defined by that start position and size.
673 ///
674 /// \returns a register with the requested size, or the current best
675 /// register found during the current query.
676 Register findValueFromBuildVector(GBuildVector &BV, unsigned StartBit,
677 unsigned Size) {
678 assert(Size > 0);
679
680 // Find the source operand that provides the bits requested.
681 Register Src1Reg = BV.getSourceReg(0);
682 unsigned SrcSize = MRI.getType(Src1Reg).getSizeInBits();
683
684 // Operand index of the source that provides the start of the bit range.
685 unsigned StartSrcIdx = (StartBit / SrcSize) + 1;
686 // Offset into the source at which the bit range starts.
687 unsigned InRegOffset = StartBit % SrcSize;
688
689 if (InRegOffset != 0)
690 return CurrentBest; // Give up, bits don't start at a scalar source.
691 if (Size < SrcSize)
692 return CurrentBest; // Scalar source is too large for requested bits.
693
694 // If the bits cover multiple sources evenly, then create a new
695 // build_vector to synthesize the required size, if that's been requested.
696 if (Size > SrcSize) {
697 if (Size % SrcSize > 0)
698 return CurrentBest; // Isn't covered exactly by sources.
699
700 unsigned NumSrcsUsed = Size / SrcSize;
701 // If we're requesting all of the sources, just return this def.
702 if (NumSrcsUsed == BV.getNumSources())
703 return BV.getReg(0);
704
705 LLT SrcTy = MRI.getType(Src1Reg);
706 LLT NewBVTy = LLT::fixed_vector(NumSrcsUsed, SrcTy);
707
708 // Check if the resulting build vector would be legal.
709 LegalizeActionStep ActionStep =
710 LI.getAction({TargetOpcode::G_BUILD_VECTOR, {NewBVTy, SrcTy}});
711 if (ActionStep.Action != LegalizeActions::Legal)
712 return CurrentBest;
713
714 SmallVector<Register> NewSrcs;
715 for (unsigned SrcIdx = StartSrcIdx; SrcIdx < StartSrcIdx + NumSrcsUsed;
716 ++SrcIdx)
717 NewSrcs.push_back(BV.getReg(SrcIdx));
718 MIB.setInstrAndDebugLoc(BV);
719 return MIB.buildBuildVector(NewBVTy, NewSrcs).getReg(0);
720 }
721 // A single source is requested, just return it.
722 return BV.getReg(StartSrcIdx);
723 }
724
725 /// Given an G_INSERT op \p MI and a start bit and size, try to find
726 /// the origin of the value defined by that start position and size.
727 ///
728 /// \returns a register with the requested size, or the current best
729 /// register found during the current query.
730 Register findValueFromInsert(MachineInstr &MI, unsigned StartBit,
731 unsigned Size) {
732 assert(MI.getOpcode() == TargetOpcode::G_INSERT);
733 assert(Size > 0);
734
735 Register ContainerSrcReg = MI.getOperand(1).getReg();
736 Register InsertedReg = MI.getOperand(2).getReg();
737 LLT InsertedRegTy = MRI.getType(InsertedReg);
738 unsigned InsertOffset = MI.getOperand(3).getImm();
739
740 // There are 4 possible container/insertreg + requested bit-range layouts
741 // that the instruction and query could be representing.
742 // For: %_ = G_INSERT %CONTAINER, %INS, InsOff (abbrev. to 'IO')
743 // and a start bit 'SB', with size S, giving an end bit 'EB', we could
744 // have...
745 // Scenario A:
746 // --------------------------
747 // | INS | CONTAINER |
748 // --------------------------
749 // | |
750 // SB EB
751 //
752 // Scenario B:
753 // --------------------------
754 // | INS | CONTAINER |
755 // --------------------------
756 // | |
757 // SB EB
758 //
759 // Scenario C:
760 // --------------------------
761 // | CONTAINER | INS |
762 // --------------------------
763 // | |
764 // SB EB
765 //
766 // Scenario D:
767 // --------------------------
768 // | CONTAINER | INS |
769 // --------------------------
770 // | |
771 // SB EB
772 //
773 // So therefore, A and D are requesting data from the INS operand, while
774 // B and C are requesting from the container operand.
775
776 unsigned InsertedEndBit = InsertOffset + InsertedRegTy.getSizeInBits();
777 unsigned EndBit = StartBit + Size;
778 unsigned NewStartBit;
779 Register SrcRegToUse;
780 if (EndBit <= InsertOffset || InsertedEndBit <= StartBit) {
781 SrcRegToUse = ContainerSrcReg;
782 NewStartBit = StartBit;
783 return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size,
784 MRI.getType(SrcRegToUse));
785 }
786 if (InsertOffset <= StartBit && EndBit <= InsertedEndBit) {
787 SrcRegToUse = InsertedReg;
788 NewStartBit = StartBit - InsertOffset;
789 if (NewStartBit == 0 &&
790 Size == MRI.getType(SrcRegToUse).getSizeInBits())
791 CurrentBest = SrcRegToUse;
792 return findValueFromDefImpl(SrcRegToUse, NewStartBit, Size,
793 MRI.getType(SrcRegToUse));
794 }
795 // The bit range spans both the inserted and container regions.
796 return Register();
797 }
798
799 /// Given an G_SEXT, G_ZEXT, G_ANYEXT op \p MI and a start bit and
800 /// size, try to find the origin of the value defined by that start
801 /// position and size.
802 ///
803 /// \returns a register with the requested size, or the current best
804 /// register found during the current query.
805 Register findValueFromExt(MachineInstr &MI, unsigned StartBit,
806 unsigned Size) {
807 assert(MI.getOpcode() == TargetOpcode::G_SEXT ||
808 MI.getOpcode() == TargetOpcode::G_ZEXT ||
809 MI.getOpcode() == TargetOpcode::G_ANYEXT);
810 assert(Size > 0);
811
812 Register SrcReg = MI.getOperand(1).getReg();
813 LLT SrcType = MRI.getType(SrcReg);
814 unsigned SrcSize = SrcType.getSizeInBits();
815
816 // Currently we don't go into vectors.
817 if (!SrcType.isScalar())
818 return CurrentBest;
819
820 if (StartBit + Size > SrcSize)
821 return CurrentBest;
822
823 if (StartBit == 0 && SrcType.getSizeInBits() == Size)
824 CurrentBest = SrcReg;
825 return findValueFromDefImpl(SrcReg, StartBit, Size, SrcType);
826 }
827
828 /// Given an G_TRUNC op \p MI and a start bit and size, try to find
829 /// the origin of the value defined by that start position and size.
830 ///
831 /// \returns a register with the requested size, or the current best
832 /// register found during the current query.
833 Register findValueFromTrunc(MachineInstr &MI, unsigned StartBit,
834 unsigned Size) {
835 assert(MI.getOpcode() == TargetOpcode::G_TRUNC);
836 assert(Size > 0);
837
838 Register SrcReg = MI.getOperand(1).getReg();
839 LLT SrcType = MRI.getType(SrcReg);
840
841 // Currently we don't go into vectors.
842 if (!SrcType.isScalar())
843 return CurrentBest;
844
845 return findValueFromDefImpl(SrcReg, StartBit, Size, SrcType);
846 }
847
848 /// Internal implementation for findValueFromDef(). findValueFromDef()
849 /// initializes some data like the CurrentBest register, which this method
850 /// and its callees rely upon.
851 Register findValueFromDefImpl(Register DefReg, unsigned StartBit,
852 unsigned Size, LLT DstTy) {
853 std::optional<DefinitionAndSourceRegister> DefSrcReg =
854 getDefSrcRegIgnoringCopies(DefReg, MRI);
855 MachineInstr *Def = DefSrcReg->MI;
856 DefReg = DefSrcReg->Reg;
857 // If the instruction has a single def, then simply delegate the search.
858 // For unmerge however with multiple defs, we need to compute the offset
859 // into the source of the unmerge.
860 switch (Def->getOpcode()) {
861 case TargetOpcode::G_CONCAT_VECTORS:
862 return findValueFromConcat(cast<GConcatVectors>(*Def), StartBit, Size);
863 case TargetOpcode::G_UNMERGE_VALUES: {
864 unsigned DefStartBit = 0;
865 unsigned DefSize = MRI.getType(DefReg).getSizeInBits();
866 for (const auto &MO : Def->defs()) {
867 if (MO.getReg() == DefReg)
868 break;
869 DefStartBit += DefSize;
870 }
871 Register SrcReg = Def->getOperand(Def->getNumOperands() - 1).getReg();
872 Register SrcOriginReg =
873 findValueFromDefImpl(SrcReg, StartBit + DefStartBit, Size, DstTy);
874 if (SrcOriginReg)
875 return SrcOriginReg;
876 // Failed to find a further value. If the StartBit and Size perfectly
877 // covered the requested DefReg, return that since it's better than
878 // nothing.
879 if (StartBit == 0 && Size == DefSize)
880 return DefReg;
881 return CurrentBest;
882 }
883 case TargetOpcode::G_BUILD_VECTOR:
884 return findValueFromBuildVector(cast<GBuildVector>(*Def), StartBit,
885 Size);
886 case TargetOpcode::G_INSERT:
887 return findValueFromInsert(*Def, StartBit, Size);
888 case TargetOpcode::G_TRUNC:
889 return findValueFromTrunc(*Def, StartBit, Size);
890 case TargetOpcode::G_SEXT:
891 case TargetOpcode::G_ZEXT:
892 case TargetOpcode::G_ANYEXT:
893 return findValueFromExt(*Def, StartBit, Size);
894 case TargetOpcode::G_IMPLICIT_DEF: {
895 if (MRI.getType(DefReg) == DstTy)
896 return DefReg;
897 MIB.setInstrAndDebugLoc(*Def);
898 return MIB.buildUndef(DstTy).getReg(0);
899 }
900 default:
901 return CurrentBest;
902 }
903 }
904
905 public:
907 const LegalizerInfo &Info)
908 : MRI(Mri), MIB(Builder), LI(Info) {}
909
910 /// Try to find a source of the value defined in the def \p DefReg, starting
911 /// at position \p StartBit with size \p Size.
912 /// \returns a register with the requested size, or an empty Register if no
913 /// better value could be found.
914 Register findValueFromDef(Register DefReg, unsigned StartBit, unsigned Size,
915 LLT DstTy) {
916 CurrentBest = Register();
917 Register FoundReg = findValueFromDefImpl(DefReg, StartBit, Size, DstTy);
918 return FoundReg != DefReg ? FoundReg : Register();
919 }
920
921 /// Try to combine the defs of an unmerge \p MI by attempting to find
922 /// values that provides the bits for each def reg.
923 /// \returns true if all the defs of the unmerge have been made dead.
925 SmallVectorImpl<Register> &UpdatedDefs) {
926 unsigned NumDefs = MI.getNumDefs();
927 LLT DestTy = MRI.getType(MI.getReg(0));
928
929 SmallBitVector DeadDefs(NumDefs);
930 for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
931 Register DefReg = MI.getReg(DefIdx);
932 if (MRI.use_nodbg_empty(DefReg)) {
933 DeadDefs[DefIdx] = true;
934 continue;
935 }
936 Register FoundVal =
937 findValueFromDef(DefReg, 0, DestTy.getSizeInBits(), DestTy);
938 if (!FoundVal)
939 continue;
940 if (MRI.getType(FoundVal) != DestTy)
941 continue;
942
943 replaceRegOrBuildCopy(DefReg, FoundVal, MRI, MIB, UpdatedDefs,
944 Observer);
945 DeadDefs[DefIdx] = true;
946 }
947 return DeadDefs.all();
948 }
949
951 unsigned &DefOperandIdx) {
952 if (Register Def = findValueFromDefImpl(Reg, 0, Size, MRI.getType(Reg))) {
953 if (auto *Unmerge = dyn_cast<GUnmerge>(MRI.getVRegDef(Def))) {
954 DefOperandIdx =
955 Unmerge->findRegisterDefOperandIdx(Def, /*TRI=*/nullptr);
956 return Unmerge;
957 }
958 }
959 return nullptr;
960 }
961
962 // Check if sequence of elements from merge-like instruction is defined by
963 // another sequence of elements defined by unmerge. Most often this is the
964 // same sequence. Search for elements using findValueFromDefImpl.
965 bool isSequenceFromUnmerge(GMergeLikeInstr &MI, unsigned MergeStartIdx,
966 GUnmerge *Unmerge, unsigned UnmergeIdxStart,
967 unsigned NumElts, unsigned EltSize,
968 bool AllowUndef) {
969 using namespace llvm::MIPatternMatch;
970 assert(MergeStartIdx + NumElts <= MI.getNumSources());
971 for (unsigned i = MergeStartIdx; i < MergeStartIdx + NumElts; ++i) {
972 unsigned EltUnmergeIdx;
974 MI.getSourceReg(i), EltSize, EltUnmergeIdx);
975 // Check if source i comes from the same Unmerge.
976 if (EltUnmerge == Unmerge) {
977 // Check that source i's def has same index in sequence in Unmerge.
978 if (i - MergeStartIdx != EltUnmergeIdx - UnmergeIdxStart)
979 return false;
980 } else if (!AllowUndef ||
981 !mi_match(MI.getSourceReg(i), MRI, m_GImplicitDef()))
982 return false;
983 }
984 return true;
985 }
986
989 SmallVectorImpl<Register> &UpdatedDefs,
990 GISelChangeObserver &Observer) {
991 Register Elt0 = MI.getSourceReg(0);
992 LLT EltTy = MRI.getType(Elt0);
993 unsigned EltSize = EltTy.getSizeInBits();
994
995 unsigned Elt0UnmergeIdx;
996 // Search for unmerge that will be candidate for combine.
997 auto *Unmerge = findUnmergeThatDefinesReg(Elt0, EltSize, Elt0UnmergeIdx);
998 if (!Unmerge)
999 return false;
1000
1001 unsigned NumMIElts = MI.getNumSources();
1002 Register Dst = MI.getReg(0);
1003 LLT DstTy = MRI.getType(Dst);
1004 Register UnmergeSrc = Unmerge->getSourceReg();
1005 LLT UnmergeSrcTy = MRI.getType(UnmergeSrc);
1006 unsigned DstSize = DstTy.getSizeInBits();
1007 unsigned UnmergeSrcSize = UnmergeSrcTy.getSizeInBits();
1008
1009 // Recognize copy of UnmergeSrc to Dst.
1010 // Unmerge UnmergeSrc and reassemble it using merge-like opcode into Dst.
1011 //
1012 // %0:_(EltTy), %1, ... = G_UNMERGE_VALUES %UnmergeSrc:_(Ty)
1013 // %Dst:_(Ty) = G_merge_like_opcode %0:_(EltTy), %1, ...
1014 //
1015 // %Dst:_(Ty) = COPY %UnmergeSrc:_(Ty)
1016 if ((DstSize == UnmergeSrcSize) && (DstTy == UnmergeSrcTy) &&
1017 (Elt0UnmergeIdx == 0)) {
1018 if (!isSequenceFromUnmerge(MI, 0, Unmerge, 0, NumMIElts, EltSize,
1019 /*AllowUndef=*/DstTy.isVector()))
1020 return false;
1021
1022 replaceRegOrBuildCopy(Dst, UnmergeSrc, MRI, MIB, UpdatedDefs, Observer);
1023 DeadInsts.push_back(&MI);
1024 return true;
1025 }
1026
1027 // Recognize UnmergeSrc that can be unmerged to DstTy directly.
1028 // Types have to be either both vector or both non-vector types.
1029 // In case of vector types, the scalar elements need to match.
1030 // Merge-like opcodes are combined one at the time. First one creates new
1031 // unmerge, following should use the same unmerge (builder performs CSE).
1032 //
1033 // %0:_(EltTy), %1, %2, %3 = G_UNMERGE_VALUES %UnmergeSrc:_(UnmergeSrcTy)
1034 // %Dst:_(DstTy) = G_merge_like_opcode %0:_(EltTy), %1
1035 // %AnotherDst:_(DstTy) = G_merge_like_opcode %2:_(EltTy), %3
1036 //
1037 // %Dst:_(DstTy), %AnotherDst = G_UNMERGE_VALUES %UnmergeSrc
1038 if ((DstSize < UnmergeSrcSize) &&
1039 ((!DstTy.isVector() && !UnmergeSrcTy.isVector()) ||
1040 (DstTy.isVector() && UnmergeSrcTy.isVector() &&
1041 DstTy.getScalarType() == UnmergeSrcTy.getScalarType())) &&
1042 (Elt0UnmergeIdx % NumMIElts == 0) &&
1043 getCoverTy(UnmergeSrcTy, DstTy) == UnmergeSrcTy) {
1044 if (!isSequenceFromUnmerge(MI, 0, Unmerge, Elt0UnmergeIdx, NumMIElts,
1045 EltSize, false))
1046 return false;
1047 MIB.setInstrAndDebugLoc(MI);
1048 auto NewUnmerge = MIB.buildUnmerge(DstTy, Unmerge->getSourceReg());
1049 unsigned DstIdx = (Elt0UnmergeIdx * EltSize) / DstTy.getSizeInBits();
1050 replaceRegOrBuildCopy(Dst, NewUnmerge.getReg(DstIdx), MRI, MIB,
1051 UpdatedDefs, Observer);
1052 DeadInsts.push_back(&MI);
1053 return true;
1054 }
1055
1056 // Recognize when multiple unmerged sources with UnmergeSrcTy type
1057 // can be merged into Dst with DstTy type directly.
1058 // Types have to be either both vector or both non-vector types.
1059
1060 // %0:_(EltTy), %1 = G_UNMERGE_VALUES %UnmergeSrc:_(UnmergeSrcTy)
1061 // %2:_(EltTy), %3 = G_UNMERGE_VALUES %AnotherUnmergeSrc:_(UnmergeSrcTy)
1062 // %Dst:_(DstTy) = G_merge_like_opcode %0:_(EltTy), %1, %2, %3
1063 //
1064 // %Dst:_(DstTy) = G_merge_like_opcode %UnmergeSrc, %AnotherUnmergeSrc
1065
1066 if ((DstSize > UnmergeSrcSize) &&
1067 (DstTy.isVector() == UnmergeSrcTy.isVector()) &&
1068 getCoverTy(DstTy, UnmergeSrcTy) == DstTy) {
1069 SmallVector<Register, 4> ConcatSources;
1070 unsigned NumElts = Unmerge->getNumDefs();
1071 for (unsigned i = 0; i < MI.getNumSources(); i += NumElts) {
1072 unsigned EltUnmergeIdx;
1073 auto *UnmergeI = findUnmergeThatDefinesReg(MI.getSourceReg(i),
1074 EltSize, EltUnmergeIdx);
1075 // All unmerges have to be the same size.
1076 if ((!UnmergeI) || (UnmergeI->getNumDefs() != NumElts) ||
1077 (EltUnmergeIdx != 0))
1078 return false;
1079 if (!isSequenceFromUnmerge(MI, i, UnmergeI, 0, NumElts, EltSize,
1080 false))
1081 return false;
1082 ConcatSources.push_back(UnmergeI->getSourceReg());
1083 }
1084
1085 MIB.setInstrAndDebugLoc(MI);
1086 MIB.buildMergeLikeInstr(Dst, ConcatSources);
1087 DeadInsts.push_back(&MI);
1088 return true;
1089 }
1090
1091 return false;
1092 }
1093 };
1094
1097 SmallVectorImpl<Register> &UpdatedDefs,
1098 GISelChangeObserver &Observer) {
1099 unsigned NumDefs = MI.getNumDefs();
1100 Register SrcReg = MI.getSourceReg();
1101 std::optional<DefinitionAndSourceRegister> DefSrcReg =
1102 getDefSrcRegIgnoringCopies(SrcReg, MRI);
1103 if (!DefSrcReg)
1104 return false;
1105 MachineInstr *SrcDef = DefSrcReg->MI;
1106
1107 LLT OpTy = MRI.getType(SrcReg);
1108 LLT DestTy = MRI.getType(MI.getReg(0));
1109 unsigned SrcDefIdx = getDefIndex(*SrcDef, DefSrcReg->Reg);
1110
1111 Builder.setInstrAndDebugLoc(MI);
1112
1113 ArtifactValueFinder Finder(MRI, Builder, LI);
1114 if (Finder.tryCombineUnmergeDefs(MI, Observer, UpdatedDefs)) {
1115 markInstAndDefDead(MI, *SrcDef, DeadInsts, SrcDefIdx);
1116 return true;
1117 }
1118
1119 if (auto *SrcUnmerge = dyn_cast<GUnmerge>(SrcDef)) {
1120 // %0:_(<4 x s16>) = G_FOO
1121 // %1:_(<2 x s16>), %2:_(<2 x s16>) = G_UNMERGE_VALUES %0
1122 // %3:_(s16), %4:_(s16) = G_UNMERGE_VALUES %1
1123 //
1124 // %3:_(s16), %4:_(s16), %5:_(s16), %6:_(s16) = G_UNMERGE_VALUES %0
1125 Register SrcUnmergeSrc = SrcUnmerge->getSourceReg();
1126 LLT SrcUnmergeSrcTy = MRI.getType(SrcUnmergeSrc);
1127
1128 // If we need to decrease the number of vector elements in the result type
1129 // of an unmerge, this would involve the creation of an equivalent unmerge
1130 // to copy back to the original result registers.
1131 LegalizeActionStep ActionStep = LI.getAction(
1132 {TargetOpcode::G_UNMERGE_VALUES, {OpTy, SrcUnmergeSrcTy}});
1133 switch (ActionStep.Action) {
1135 if (!OpTy.isVector() || !LI.isLegal({TargetOpcode::G_UNMERGE_VALUES,
1136 {DestTy, SrcUnmergeSrcTy}}))
1137 return false;
1138 break;
1141 break;
1144 if (ActionStep.TypeIdx == 1)
1145 return false;
1146 break;
1147 default:
1148 return false;
1149 }
1150
1151 auto NewUnmerge = Builder.buildUnmerge(DestTy, SrcUnmergeSrc);
1152
1153 // TODO: Should we try to process out the other defs now? If the other
1154 // defs of the source unmerge are also unmerged, we end up with a separate
1155 // unmerge for each one.
1156 for (unsigned I = 0; I != NumDefs; ++I) {
1157 Register Def = MI.getReg(I);
1158 replaceRegOrBuildCopy(Def, NewUnmerge.getReg(SrcDefIdx * NumDefs + I),
1159 MRI, Builder, UpdatedDefs, Observer);
1160 }
1161
1162 markInstAndDefDead(MI, *SrcUnmerge, DeadInsts, SrcDefIdx);
1163 return true;
1164 }
1165
1166 MachineInstr *MergeI = SrcDef;
1167 unsigned ConvertOp = 0;
1168
1169 // Handle intermediate conversions
1170 unsigned SrcOp = SrcDef->getOpcode();
1171 if (isArtifactCast(SrcOp)) {
1172 ConvertOp = SrcOp;
1173 MergeI = getDefIgnoringCopies(SrcDef->getOperand(1).getReg(), MRI);
1174 }
1175
1176 if (!MergeI || !canFoldMergeOpcode(MergeI->getOpcode(),
1177 ConvertOp, OpTy, DestTy)) {
1178 // We might have a chance to combine later by trying to combine
1179 // unmerge(cast) first
1180 return tryFoldUnmergeCast(MI, *SrcDef, DeadInsts, UpdatedDefs);
1181 }
1182
1183 const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
1184
1185 if (NumMergeRegs < NumDefs) {
1186 if (NumDefs % NumMergeRegs != 0)
1187 return false;
1188
1189 Builder.setInstrAndDebugLoc(MI);
1190 // Transform to UNMERGEs, for example
1191 // %1 = G_MERGE_VALUES %4, %5
1192 // %9, %10, %11, %12 = G_UNMERGE_VALUES %1
1193 // to
1194 // %9, %10 = G_UNMERGE_VALUES %4
1195 // %11, %12 = G_UNMERGE_VALUES %5
1196
1197 const unsigned NewNumDefs = NumDefs / NumMergeRegs;
1198 for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
1200 for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
1201 ++j, ++DefIdx)
1202 DstRegs.push_back(MI.getReg(DefIdx));
1203
1204 if (ConvertOp) {
1205 LLT MergeDstTy = MRI.getType(SrcDef->getOperand(0).getReg());
1206
1207 // This is a vector that is being split and casted. Extract to the
1208 // element type, and do the conversion on the scalars (or smaller
1209 // vectors).
1210 LLT MergeEltTy = MergeDstTy.divide(NumMergeRegs);
1211
1212 // Handle split to smaller vectors, with conversions.
1213 // %2(<8 x s8>) = G_CONCAT_VECTORS %0(<4 x s8>), %1(<4 x s8>)
1214 // %3(<8 x s16>) = G_SEXT %2
1215 // %4(<2 x s16>), %5(<2 x s16>), %6(<2 x s16>), %7(<2 x s16>) =
1216 // G_UNMERGE_VALUES %3
1217 //
1218 // =>
1219 //
1220 // %8(<4 x s16>) = G_SEXT %0
1221 // %9(<4 x s16>) = G_SEXT %1
1222 // %4(<2 x s16>), %5(<2 x s16>) = G_UNMERGE_VALUES %8
1223 // %7(<2 x s16>), %7(<2 x s16>) = G_UNMERGE_VALUES %9
1224
1225 Register TmpReg = MRI.createGenericVirtualRegister(MergeEltTy);
1226 Builder.buildInstr(ConvertOp, {TmpReg},
1227 {MergeI->getOperand(Idx + 1).getReg()});
1228 Builder.buildUnmerge(DstRegs, TmpReg);
1229 } else {
1230 Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
1231 }
1232 UpdatedDefs.append(DstRegs.begin(), DstRegs.end());
1233 }
1234
1235 } else if (NumMergeRegs > NumDefs) {
1236 if (ConvertOp != 0 || NumMergeRegs % NumDefs != 0)
1237 return false;
1238
1239 Builder.setInstrAndDebugLoc(MI);
1240 // Transform to MERGEs
1241 // %6 = G_MERGE_VALUES %17, %18, %19, %20
1242 // %7, %8 = G_UNMERGE_VALUES %6
1243 // to
1244 // %7 = G_MERGE_VALUES %17, %18
1245 // %8 = G_MERGE_VALUES %19, %20
1246
1247 const unsigned NumRegs = NumMergeRegs / NumDefs;
1248 for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
1250 for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
1251 ++j, ++Idx)
1252 Regs.push_back(MergeI->getOperand(Idx).getReg());
1253
1254 Register DefReg = MI.getReg(DefIdx);
1255 Builder.buildMergeLikeInstr(DefReg, Regs);
1256 UpdatedDefs.push_back(DefReg);
1257 }
1258
1259 } else {
1260 LLT MergeSrcTy = MRI.getType(MergeI->getOperand(1).getReg());
1261
1262 if (!ConvertOp && DestTy != MergeSrcTy) {
1263 if (DestTy.isPointer())
1264 ConvertOp = TargetOpcode::G_INTTOPTR;
1265 else if (MergeSrcTy.isPointer())
1266 ConvertOp = TargetOpcode::G_PTRTOINT;
1267 else
1268 ConvertOp = TargetOpcode::G_BITCAST;
1269 }
1270
1271 if (ConvertOp) {
1272 Builder.setInstrAndDebugLoc(MI);
1273
1274 for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
1275 Register DefReg = MI.getOperand(Idx).getReg();
1276 Register MergeSrc = MergeI->getOperand(Idx + 1).getReg();
1277
1278 if (!MRI.use_empty(DefReg)) {
1279 Builder.buildInstr(ConvertOp, {DefReg}, {MergeSrc});
1280 UpdatedDefs.push_back(DefReg);
1281 }
1282 }
1283
1284 markInstAndDefDead(MI, *MergeI, DeadInsts);
1285 return true;
1286 }
1287
1288 assert(DestTy == MergeSrcTy &&
1289 "Bitcast and the other kinds of conversions should "
1290 "have happened earlier");
1291
1292 Builder.setInstrAndDebugLoc(MI);
1293 for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
1294 Register DstReg = MI.getOperand(Idx).getReg();
1295 Register SrcReg = MergeI->getOperand(Idx + 1).getReg();
1296 replaceRegOrBuildCopy(DstReg, SrcReg, MRI, Builder, UpdatedDefs,
1297 Observer);
1298 }
1299 }
1300
1301 markInstAndDefDead(MI, *MergeI, DeadInsts);
1302 return true;
1303 }
1304
1307 SmallVectorImpl<Register> &UpdatedDefs) {
1308 assert(MI.getOpcode() == TargetOpcode::G_EXTRACT);
1309
1310 // Try to use the source registers from a G_MERGE_VALUES
1311 //
1312 // %2 = G_MERGE_VALUES %0, %1
1313 // %3 = G_EXTRACT %2, N
1314 // =>
1315 //
1316 // for N < %2.getSizeInBits() / 2
1317 // %3 = G_EXTRACT %0, N
1318 //
1319 // for N >= %2.getSizeInBits() / 2
1320 // %3 = G_EXTRACT %1, (N - %0.getSizeInBits()
1321
1322 Register DstReg = MI.getOperand(0).getReg();
1323 Register SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
1324 MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
1325 if (MergeI && MergeI->getOpcode() == TargetOpcode::G_IMPLICIT_DEF) {
1326 Builder.setInstrAndDebugLoc(MI);
1327 Builder.buildUndef(DstReg);
1328 UpdatedDefs.push_back(DstReg);
1329 markInstAndDefDead(MI, *MergeI, DeadInsts);
1330 return true;
1331 }
1332 if (!MergeI || !isa<GMergeLikeInstr>(MergeI))
1333 return false;
1334
1335 LLT DstTy = MRI.getType(DstReg);
1336 LLT SrcTy = MRI.getType(SrcReg);
1337
1338 // TODO: Do we need to check if the resulting extract is supported?
1339 unsigned ExtractDstSize = DstTy.getSizeInBits();
1340 unsigned Offset = MI.getOperand(2).getImm();
1341 unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
1342 unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
1343 unsigned MergeSrcIdx = Offset / MergeSrcSize;
1344
1345 // Compute the offset of the last bit the extract needs.
1346 unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;
1347
1348 // Can't handle the case where the extract spans multiple inputs.
1349 if (MergeSrcIdx != EndMergeSrcIdx)
1350 return false;
1351
1352 // TODO: We could modify MI in place in most cases.
1353 Builder.setInstrAndDebugLoc(MI);
1354 Builder.buildExtract(DstReg, MergeI->getOperand(MergeSrcIdx + 1).getReg(),
1355 Offset - MergeSrcIdx * MergeSrcSize);
1356 UpdatedDefs.push_back(DstReg);
1357 markInstAndDefDead(MI, *MergeI, DeadInsts);
1358 return true;
1359 }
1360
1361 /// Try to combine away MI.
1362 /// Returns true if it combined away the MI.
1363 /// Adds instructions that are dead as a result of the combine
1364 /// into DeadInsts, which can include MI.
1367 GISelObserverWrapper &WrapperObserver) {
1368 ArtifactValueFinder Finder(MRI, Builder, LI);
1369
1370 // This might be a recursive call, and we might have DeadInsts already
1371 // populated. To avoid bad things happening later with multiple vreg defs
1372 // etc, process the dead instructions now if any.
1373 if (!DeadInsts.empty())
1374 deleteMarkedDeadInsts(DeadInsts, WrapperObserver);
1375
1376 // Put here every vreg that was redefined in such a way that it's at least
1377 // possible that one (or more) of its users (immediate or COPY-separated)
1378 // could become artifact combinable with the new definition (or the
1379 // instruction reachable from it through a chain of copies if any).
1380 SmallVector<Register, 4> UpdatedDefs;
1381 bool Changed = false;
1382 switch (MI.getOpcode()) {
1383 default:
1384 return false;
1385 case TargetOpcode::G_ANYEXT:
1386 Changed = tryCombineAnyExt(MI, DeadInsts, UpdatedDefs, WrapperObserver);
1387 break;
1388 case TargetOpcode::G_ZEXT:
1389 Changed = tryCombineZExt(MI, DeadInsts, UpdatedDefs, WrapperObserver);
1390 break;
1391 case TargetOpcode::G_SEXT:
1392 Changed = tryCombineSExt(MI, DeadInsts, UpdatedDefs, WrapperObserver);
1393 break;
1394 case TargetOpcode::G_UNMERGE_VALUES:
1396 UpdatedDefs, WrapperObserver);
1397 break;
1398 case TargetOpcode::G_MERGE_VALUES:
1399 case TargetOpcode::G_BUILD_VECTOR:
1400 case TargetOpcode::G_CONCAT_VECTORS:
1401 // If any of the users of this merge are an unmerge, then add them to the
1402 // artifact worklist in case there's folding that can be done looking up.
1403 for (MachineInstr &U : MRI.use_instructions(MI.getOperand(0).getReg())) {
1404 if (U.getOpcode() == TargetOpcode::G_UNMERGE_VALUES ||
1405 U.getOpcode() == TargetOpcode::G_TRUNC) {
1406 UpdatedDefs.push_back(MI.getOperand(0).getReg());
1407 break;
1408 }
1409 }
1411 UpdatedDefs, WrapperObserver);
1412 break;
1413 case TargetOpcode::G_EXTRACT:
1414 Changed = tryCombineExtract(MI, DeadInsts, UpdatedDefs);
1415 break;
1416 case TargetOpcode::G_TRUNC:
1417 Changed = tryCombineTrunc(MI, DeadInsts, UpdatedDefs, WrapperObserver);
1418 if (!Changed) {
1419 // Try to combine truncates away even if they are legal. As all artifact
1420 // combines at the moment look only "up" the def-use chains, we achieve
1421 // that by throwing truncates' users (with look through copies) into the
1422 // ArtifactList again.
1423 UpdatedDefs.push_back(MI.getOperand(0).getReg());
1424 }
1425 break;
1426 }
1427 // If the main loop through the ArtifactList found at least one combinable
1428 // pair of artifacts, not only combine it away (as done above), but also
1429 // follow the def-use chain from there to combine everything that can be
1430 // combined within this def-use chain of artifacts.
1431 while (!UpdatedDefs.empty()) {
1432 Register NewDef = UpdatedDefs.pop_back_val();
1433 assert(NewDef.isVirtual() && "Unexpected redefinition of a physreg");
1434 for (MachineInstr &Use : MRI.use_instructions(NewDef)) {
1435 switch (Use.getOpcode()) {
1436 // Keep this list in sync with the list of all artifact combines.
1437 case TargetOpcode::G_ANYEXT:
1438 case TargetOpcode::G_ZEXT:
1439 case TargetOpcode::G_SEXT:
1440 case TargetOpcode::G_UNMERGE_VALUES:
1441 case TargetOpcode::G_EXTRACT:
1442 case TargetOpcode::G_TRUNC:
1443 case TargetOpcode::G_BUILD_VECTOR:
1444 // Adding Use to ArtifactList.
1445 WrapperObserver.changedInstr(Use);
1446 break;
1447 case TargetOpcode::G_ASSERT_SEXT:
1448 case TargetOpcode::G_ASSERT_ZEXT:
1449 case TargetOpcode::G_ASSERT_ALIGN:
1450 case TargetOpcode::COPY: {
1451 Register Copy = Use.getOperand(0).getReg();
1452 if (Copy.isVirtual())
1453 UpdatedDefs.push_back(Copy);
1454 break;
1455 }
1456 default:
1457 // If we do not have an artifact combine for the opcode, there is no
1458 // point in adding it to the ArtifactList as nothing interesting will
1459 // be done to it anyway.
1460 break;
1461 }
1462 }
1463 }
1464 return Changed;
1465 }
1466
1467private:
1468 static Register getArtifactSrcReg(const MachineInstr &MI) {
1469 switch (MI.getOpcode()) {
1470 case TargetOpcode::COPY:
1471 case TargetOpcode::G_TRUNC:
1472 case TargetOpcode::G_ZEXT:
1473 case TargetOpcode::G_ANYEXT:
1474 case TargetOpcode::G_SEXT:
1475 case TargetOpcode::G_EXTRACT:
1476 case TargetOpcode::G_ASSERT_SEXT:
1477 case TargetOpcode::G_ASSERT_ZEXT:
1478 case TargetOpcode::G_ASSERT_ALIGN:
1479 return MI.getOperand(1).getReg();
1480 case TargetOpcode::G_UNMERGE_VALUES:
1481 return MI.getOperand(MI.getNumOperands() - 1).getReg();
1482 default:
1483 llvm_unreachable("Not a legalization artifact happen");
1484 }
1485 }
1486
1487 /// Mark a def of one of MI's original operands, DefMI, as dead if changing MI
1488 /// (either by killing it or changing operands) results in DefMI being dead
1489 /// too. In-between COPYs or artifact-casts are also collected if they are
1490 /// dead.
1491 /// MI is not marked dead.
1492 void markDefDead(MachineInstr &MI, MachineInstr &DefMI,
1494 unsigned DefIdx = 0) {
1495 // Collect all the copy instructions that are made dead, due to deleting
1496 // this instruction. Collect all of them until the Trunc(DefMI).
1497 // Eg,
1498 // %1(s1) = G_TRUNC %0(s32)
1499 // %2(s1) = COPY %1(s1)
1500 // %3(s1) = COPY %2(s1)
1501 // %4(s32) = G_ANYEXT %3(s1)
1502 // In this case, we would have replaced %4 with a copy of %0,
1503 // and as a result, %3, %2, %1 are dead.
1504 MachineInstr *PrevMI = &MI;
1505 while (PrevMI != &DefMI) {
1506 Register PrevRegSrc = getArtifactSrcReg(*PrevMI);
1507
1508 MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
1509 if (MRI.hasOneUse(PrevRegSrc)) {
1510 if (TmpDef != &DefMI) {
1511 assert((TmpDef->getOpcode() == TargetOpcode::COPY ||
1512 isArtifactCast(TmpDef->getOpcode()) ||
1514 "Expecting copy or artifact cast here");
1515
1516 DeadInsts.push_back(TmpDef);
1517 }
1518 } else
1519 break;
1520 PrevMI = TmpDef;
1521 }
1522
1523 if (PrevMI == &DefMI) {
1524 unsigned I = 0;
1525 bool IsDead = true;
1526 for (MachineOperand &Def : DefMI.defs()) {
1527 if (I != DefIdx) {
1528 if (!MRI.use_empty(Def.getReg())) {
1529 IsDead = false;
1530 break;
1531 }
1532 } else {
1533 if (!MRI.hasOneUse(DefMI.getOperand(DefIdx).getReg()))
1534 break;
1535 }
1536
1537 ++I;
1538 }
1539
1540 if (IsDead)
1541 DeadInsts.push_back(&DefMI);
1542 }
1543 }
1544
1545 /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
1546 /// dead due to MI being killed, then mark DefMI as dead too.
1547 /// Some of the combines (extends(trunc)), try to walk through redundant
1548 /// copies in between the extends and the truncs, and this attempts to collect
1549 /// the in between copies if they're dead.
1550 void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
1552 unsigned DefIdx = 0) {
1553 DeadInsts.push_back(&MI);
1554 markDefDead(MI, DefMI, DeadInsts, DefIdx);
1555 }
1556
1557 /// Erase the dead instructions in the list and call the observer hooks.
1558 /// Normally the Legalizer will deal with erasing instructions that have been
1559 /// marked dead. However, for the trunc(ext(x)) cases we can end up trying to
1560 /// process instructions which have been marked dead, but otherwise break the
1561 /// MIR by introducing multiple vreg defs. For those cases, allow the combines
1562 /// to explicitly delete the instructions before we run into trouble.
1563 void deleteMarkedDeadInsts(SmallVectorImpl<MachineInstr *> &DeadInsts,
1564 GISelObserverWrapper &WrapperObserver) {
1565 for (auto *DeadMI : DeadInsts) {
1566 LLVM_DEBUG(dbgs() << *DeadMI << "Is dead, eagerly deleting\n");
1567 WrapperObserver.erasingInstr(*DeadMI);
1568 DeadMI->eraseFromParent();
1569 }
1570 DeadInsts.clear();
1571 }
1572
1573 /// Checks if the target legalizer info has specified anything about the
1574 /// instruction, or if unsupported.
1575 bool isInstUnsupported(const LegalityQuery &Query) const {
1576 using namespace LegalizeActions;
1577 auto Step = LI.getAction(Query);
1578 return Step.Action == Unsupported;
1579 }
1580
1581 bool isInstLegal(const LegalityQuery &Query) const {
1582 return LI.getAction(Query).Action == LegalizeActions::Legal;
1583 }
1584
1585 bool isConstantUnsupported(LLT Ty) const {
1586 if (!Ty.isVector())
1587 return isInstUnsupported({TargetOpcode::G_CONSTANT, {Ty}});
1588
1589 LLT EltTy = Ty.getElementType();
1590 return isInstUnsupported({TargetOpcode::G_CONSTANT, {EltTy}}) ||
1591 isInstUnsupported({TargetOpcode::G_BUILD_VECTOR, {Ty, EltTy}});
1592 }
1593
1594 /// Looks through copy instructions and returns the actual
1595 /// source register.
1596 Register lookThroughCopyInstrs(Register Reg) {
1598 return TmpReg.isValid() ? TmpReg : Reg;
1599 }
1600};
1601
1602} // namespace llvm
1603
1604#endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This contains common code to allow clients to notify changes to machine instr.
Declares convenience wrapper classes for interpreting MachineInstr instances as specific generic oper...
IRTranslator LLVM IR MI
Interface for Targets to specify which operations they can successfully select and how the others sho...
#define I(x, y, z)
Definition MD5.cpp:57
Contains matchers for matching SSA Machine Instructions.
This file declares the MachineIRBuilder class.
Register Reg
Promote Memory to Register
Definition Mem2Reg.cpp:110
MachineRegisterInfo & MRI
bool IsDead
This file implements the SmallBitVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
static constexpr int Concat[]
Class for arbitrary precision integers.
Definition APInt.h:78
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition APInt.h:230
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
Definition APInt.cpp:1057
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
Definition APInt.cpp:970
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
Definition APInt.cpp:1030
static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Definition DebugLoc.cpp:186
static constexpr ElementCount getFixed(ScalarTy MinVal)
Definition TypeSize.h:306
Represents a G_BUILD_VECTOR.
Represents a G_CONCAT_VECTORS.
Represents a G_CONSTANT.
const APInt & getValue() const
Abstract class that contains various methods for clients to notify about changes.
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
Simple wrapper observer that takes several observers, and calls each one for each event.
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
Represents G_BUILD_VECTOR, G_CONCAT_VECTORS or G_MERGE_VALUES.
Register getSourceReg(unsigned I) const
Returns the I'th source register.
unsigned getNumSources() const
Returns the number of source registers.
Represents a G_UNMERGE_VALUES.
Register getReg(unsigned Idx) const
Access the Idx'th operand as a register and return it.
LLT changeElementCount(ElementCount EC) const
Return a vector or scalar with the same element type and the new element count.
constexpr unsigned getScalarSizeInBits() const
constexpr bool isScalar() const
LLT getScalarType() const
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
constexpr bool isFloat() const
constexpr bool isVector() const
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
constexpr bool isPointer() const
LLT divide(int Factor) const
Return a type that is Factor times smaller.
static constexpr LLT fixed_vector(unsigned NumElements, unsigned ScalarSizeInBits)
Get a low-level fixed-width vector of some number of elements and element width.
static LLT integer(unsigned SizeInBits)
LLT getElementType() const
Returns the vector's element type. Only valid for vector types.
This class provides utilities for finding source registers of specific bit ranges in an artifact.
Register findValueFromDef(Register DefReg, unsigned StartBit, unsigned Size, LLT DstTy)
Try to find a source of the value defined in the def DefReg, starting at position StartBit with size ...
bool tryCombineUnmergeDefs(GUnmerge &MI, GISelChangeObserver &Observer, SmallVectorImpl< Register > &UpdatedDefs)
Try to combine the defs of an unmerge MI by attempting to find values that provides the bits for each...
bool isSequenceFromUnmerge(GMergeLikeInstr &MI, unsigned MergeStartIdx, GUnmerge *Unmerge, unsigned UnmergeIdxStart, unsigned NumElts, unsigned EltSize, bool AllowUndef)
GUnmerge * findUnmergeThatDefinesReg(Register Reg, unsigned Size, unsigned &DefOperandIdx)
bool tryCombineMergeLike(GMergeLikeInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelChangeObserver &Observer)
ArtifactValueFinder(MachineRegisterInfo &Mri, MachineIRBuilder &Builder, const LegalizerInfo &Info)
bool tryFoldUnmergeCast(MachineInstr &MI, MachineInstr &CastMI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs)
bool tryFoldImplicitDef(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelObserverWrapper &Observer)
Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
bool tryCombineZExt(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelObserverWrapper &Observer)
bool tryCombineInstruction(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, GISelObserverWrapper &WrapperObserver)
Try to combine away MI.
bool tryCombineTrunc(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelObserverWrapper &Observer)
LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI, const LegalizerInfo &LI, GISelValueTracking *VT=nullptr)
bool tryCombineSExt(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelObserverWrapper &Observer)
static bool canFoldMergeOpcode(unsigned MergeOp, unsigned ConvertOp, LLT OpTy, LLT DestTy)
static unsigned getDefIndex(const MachineInstr &MI, Register SearchDef)
Return the operand index in MI that defines Def.
static void replaceRegOrBuildCopy(Register DstReg, Register SrcReg, MachineRegisterInfo &MRI, MachineIRBuilder &Builder, SmallVectorImpl< Register > &UpdatedDefs, GISelChangeObserver &Observer)
Try to replace DstReg with SrcReg or build a COPY instruction depending on the register constraints.
bool tryCombineUnmergeValues(GUnmerge &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelChangeObserver &Observer)
bool tryCombineExtract(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs)
bool tryCombineAnyExt(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, SmallVectorImpl< Register > &UpdatedDefs, GISelObserverWrapper &Observer)
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
Helper class to build MachineInstr.
Register getReg(unsigned Idx) const
Get the register for the operand index.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
unsigned getNumOperands() const
Retuns the total number of operands.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
Wrapper class representing virtual and physical registers.
Definition Register.h:20
constexpr bool isValid() const
Definition Register.h:112
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
bool all() const
Returns true if all bits are set.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ FewerElements
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
@ Legal
The operation is expected to be selectable directly by the target, and no transformation is necessary...
@ Unsupported
This operation is completely unsupported on the target.
@ Lower
The operation itself must be expressed in terms of simpler actions on this target.
@ NarrowScalar
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type.
@ MoreElements
The (vector) operation should be implemented by widening the input vector and ignoring the lanes adde...
operand_type_match m_Reg()
GInstrBind< GConstant > m_GConstant(GConstant *&Inst)
Match a literal G_CONSTANT instruction (no look-through of splats or copies).
UnaryOp_match< SrcTy, TargetOpcode::G_ZEXT > m_GZExt(const SrcTy &Src)
UnaryOp_match< SrcTy, TargetOpcode::G_SEXT > m_GSExt(const SrcTy &Src)
ImplicitDefMatch m_GImplicitDef()
bool mi_match(Reg R, const MachineRegisterInfo &MRI, Pattern &&P)
Or< Preds... > m_any_of(Preds &&... preds)
bind_ty< MachineInstr * > m_MInstr(MachineInstr *&MI)
And< Preds... > m_all_of(Preds &&... preds)
UnaryOp_match< SrcTy, TargetOpcode::G_ANYEXT > m_GAnyExt(const SrcTy &Src)
UnaryOp_match< SrcTy, TargetOpcode::G_TRUNC > m_GTrunc(const SrcTy &Src)
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
LLVM_ABI MachineInstr * getOpcodeDef(unsigned Opcode, Register Reg, const MachineRegisterInfo &MRI)
See if Reg is defined by an single def instruction that is Opcode.
Definition Utils.cpp:679
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
LLVM_ABI MachineInstr * getDefIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI)
Find the def instruction for Reg, folding away any trivial copies.
Definition Utils.cpp:520
bool isPreISelGenericOptimizationHint(unsigned Opcode)
LLVM_ABI bool canReplaceReg(Register DstReg, Register SrcReg, MachineRegisterInfo &MRI)
Check if DstReg can be replaced with SrcReg depending on the register constraints.
Definition Utils.cpp:207
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI LLVM_READNONE LLT getCoverTy(LLT OrigTy, LLT TargetTy)
Return smallest type that covers both OrigTy and TargetTy and is multiple of TargetTy.
Definition Utils.cpp:1367
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
LLVM_ABI std::optional< DefinitionAndSourceRegister > getDefSrcRegIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI)
Find the def instruction for Reg, and underlying value Register folding away any copies.
Definition Utils.cpp:495
LLVM_ABI Register getSrcRegIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI)
Find the source register for Reg, folding away any trivial copies.
Definition Utils.cpp:527
The LegalityQuery object bundles together all the information that's needed to decide whether a given...
The result of a query.
LegalizeAction Action
The action to take or the final answer.
unsigned TypeIdx
If describing an action, the type index to change. Otherwise zero.