1//===- CombinerHelperVectorOps.cpp-----------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements CombinerHelper for G_EXTRACT_VECTOR_ELT,
10// G_INSERT_VECTOR_ELT, and G_VSCALE
11//
12//===----------------------------------------------------------------------===//
13#include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
14#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
15#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
16#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
17#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
18#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
19#include "llvm/CodeGen/GlobalISel/Utils.h"
20#include "llvm/CodeGen/LowLevelTypeUtils.h"
21#include "llvm/CodeGen/MachineOperand.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/CodeGen/TargetLowering.h"
24#include "llvm/CodeGen/TargetOpcodes.h"
25#include "llvm/Support/Casting.h"
26#include <optional>
27
28#define DEBUG_TYPE "gi-combiner"
29
30using namespace llvm;
31using namespace MIPatternMatch;
32
33bool CombinerHelper::matchExtractVectorElement(MachineInstr &MI) const {
34 GExtractVectorElement *Extract = cast<GExtractVectorElement>(Val: &MI);
35
36 Register Dst = Extract->getReg(Idx: 0);
37 Register Vector = Extract->getVectorReg();
38 Register Index = Extract->getIndexReg();
39 LLT DstTy = MRI.getType(Reg: Dst);
40 LLT VectorTy = MRI.getType(Reg: Vector);
41
42 // The vector register can be def'd by various ops that have vector as its
43 // type. They can all be used for constant folding, scalarizing,
44 // canonicalization, or combining based on symmetry.
45 //
46 // vector like ops
47 // * build vector
48 // * build vector trunc
49 // * shuffle vector
50 // * splat vector
51 // * concat vectors
52 // * insert/extract vector element
53 // * insert/extract subvector
54 // * vector loads
55 // * scalable vector loads
56 //
57 // compute like ops
58 // * binary ops
59 // * unary ops
60 // * exts and truncs
61 // * casts
62 // * fneg
63 // * select
64 // * phis
65 // * cmps
66 // * freeze
67 // * bitcast
68 // * undef
69
70 // We try to get the value of the Index register.
71 std::optional<ValueAndVReg> MaybeIndex =
72 getIConstantVRegValWithLookThrough(VReg: Index, MRI);
73 std::optional<APInt> IndexC = std::nullopt;
74
75 if (MaybeIndex)
76 IndexC = MaybeIndex->Value;
77
78 // Fold extractVectorElement(Vector, TOOLARGE) -> undef
79 if (IndexC && VectorTy.isFixedVector() &&
80 IndexC->uge(RHS: VectorTy.getNumElements()) &&
81 isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
82 return true;
83
84 return false;
85}
86
87bool CombinerHelper::matchExtractVectorElementWithDifferentIndices(
88 const MachineOperand &MO, BuildFnTy &MatchInfo) const {
89 MachineInstr *Root = getDefIgnoringCopies(Reg: MO.getReg(), MRI);
90 GExtractVectorElement *Extract = cast<GExtractVectorElement>(Val: Root);
91
92 //
93 // %idx1:_(s64) = G_CONSTANT i64 1
94 // %idx2:_(s64) = G_CONSTANT i64 2
95 // %insert:_(<2 x s32>) = G_INSERT_VECTOR_ELT_ELT %bv(<2 x s32>),
96 // %value(s32), %idx2(s64) %extract:_(s32) = G_EXTRACT_VECTOR_ELT %insert(<2
97 // x s32>), %idx1(s64)
98 //
99 // -->
100 //
101 // %insert:_(<2 x s32>) = G_INSERT_VECTOR_ELT_ELT %bv(<2 x s32>),
102 // %value(s32), %idx2(s64) %extract:_(s32) = G_EXTRACT_VECTOR_ELT %bv(<2 x
103 // s32>), %idx1(s64)
104 //
105 //
106
107 Register Index = Extract->getIndexReg();
108
109 // We try to get the value of the Index register.
110 std::optional<ValueAndVReg> MaybeIndex =
111 getIConstantVRegValWithLookThrough(VReg: Index, MRI);
112 std::optional<APInt> IndexC = std::nullopt;
113
114 if (!MaybeIndex)
115 return false;
116 else
117 IndexC = MaybeIndex->Value;
118
119 Register Vector = Extract->getVectorReg();
120
121 GInsertVectorElement *Insert =
122 getOpcodeDef<GInsertVectorElement>(Reg: Vector, MRI);
123 if (!Insert)
124 return false;
125
126 Register Dst = Extract->getReg(Idx: 0);
127
128 std::optional<ValueAndVReg> MaybeInsertIndex =
129 getIConstantVRegValWithLookThrough(VReg: Insert->getIndexReg(), MRI);
130
131 if (MaybeInsertIndex && MaybeInsertIndex->Value != *IndexC) {
132 // There is no one-use check. We have to keep the insert. When both Index
133 // registers are constants and not equal, we can look into the Vector
134 // register of the insert.
135 MatchInfo = [=](MachineIRBuilder &B) {
136 B.buildExtractVectorElement(Res: Dst, Val: Insert->getVectorReg(), Idx: Index);
137 };
138 return true;
139 }
140
141 return false;
142}
143
144bool CombinerHelper::matchExtractVectorElementWithBuildVector(
145 const MachineInstr &MI, const MachineInstr &MI2,
146 BuildFnTy &MatchInfo) const {
147 const GExtractVectorElement *Extract = cast<GExtractVectorElement>(Val: &MI);
148 const GBuildVector *Build = cast<GBuildVector>(Val: &MI2);
149
150 //
151 // %zero:_(s64) = G_CONSTANT i64 0
152 // %bv:_(<2 x s32>) = G_BUILD_VECTOR %arg1(s32), %arg2(s32)
153 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %bv(<2 x s32>), %zero(s64)
154 //
155 // -->
156 //
157 // %extract:_(32) = COPY %arg1(s32)
158 //
159 //
160
161 Register Vector = Extract->getVectorReg();
162 LLT VectorTy = MRI.getType(Reg: Vector);
163
164 // There is a one-use check. There are more combines on build vectors.
165 EVT Ty(getMVTForLLT(Ty: VectorTy));
166 if (!MRI.hasOneNonDBGUse(RegNo: Build->getReg(Idx: 0)) ||
167 !getTargetLowering().aggressivelyPreferBuildVectorSources(VecVT: Ty))
168 return false;
169
170 APInt Index = getIConstantFromReg(VReg: Extract->getIndexReg(), MRI);
171
172 // An out-of-bounds constant index extracts undef; it is handled by
173 // extract_vec_elt_out_of_bounds. Bail out here so we never read past the
174 // G_BUILD_VECTOR's sources.
175 if (Index.uge(RHS: Build->getNumSources()))
176 return false;
177
178 // We now know that there is a buildVector def'd on the Vector register and
179 // the index is const. The combine will succeed.
180
181 Register Dst = Extract->getReg(Idx: 0);
182
183 MatchInfo = [=](MachineIRBuilder &B) {
184 B.buildCopy(Res: Dst, Op: Build->getSourceReg(I: Index.getZExtValue()));
185 };
186
187 return true;
188}
189
190bool CombinerHelper::matchExtractVectorElementWithBuildVectorTrunc(
191 const MachineOperand &MO, BuildFnTy &MatchInfo) const {
192 MachineInstr *Root = getDefIgnoringCopies(Reg: MO.getReg(), MRI);
193 GExtractVectorElement *Extract = cast<GExtractVectorElement>(Val: Root);
194
195 //
196 // %zero:_(s64) = G_CONSTANT i64 0
197 // %bv:_(<2 x s32>) = G_BUILD_VECTOR_TRUNC %arg1(s64), %arg2(s64)
198 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %bv(<2 x s32>), %zero(s64)
199 //
200 // -->
201 //
202 // %extract:_(32) = G_TRUNC %arg1(s64)
203 //
204 //
205 //
206 // %bv:_(<2 x s32>) = G_BUILD_VECTOR_TRUNC %arg1(s64), %arg2(s64)
207 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %bv(<2 x s32>), %opaque(s64)
208 //
209 // -->
210 //
211 // %bv:_(<2 x s32>) = G_BUILD_VECTOR_TRUNC %arg1(s64), %arg2(s64)
212 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %bv(<2 x s32>), %opaque(s64)
213 //
214
215 Register Vector = Extract->getVectorReg();
216
217 // We expect a buildVectorTrunc on the Vector register.
218 GBuildVectorTrunc *Build = getOpcodeDef<GBuildVectorTrunc>(Reg: Vector, MRI);
219 if (!Build)
220 return false;
221
222 LLT VectorTy = MRI.getType(Reg: Vector);
223
224 // There is a one-use check. There are more combines on build vectors.
225 EVT Ty(getMVTForLLT(Ty: VectorTy));
226 if (!MRI.hasOneNonDBGUse(RegNo: Build->getReg(Idx: 0)) ||
227 !getTargetLowering().aggressivelyPreferBuildVectorSources(VecVT: Ty))
228 return false;
229
230 Register Index = Extract->getIndexReg();
231
232 // If the Index is constant, then we can extract the element from the given
233 // offset.
234 std::optional<ValueAndVReg> MaybeIndex =
235 getIConstantVRegValWithLookThrough(VReg: Index, MRI);
236 if (!MaybeIndex)
237 return false;
238
239 // An out-of-bounds constant index extracts undef; it is handled by
240 // extract_vec_elt_out_of_bounds. Bail out so we never read past the
241 // G_BUILD_VECTOR_TRUNC's sources.
242 if (MaybeIndex->Value.uge(RHS: Build->getNumSources()))
243 return false;
244
245 // We now know that there is a buildVectorTrunc def'd on the Vector register
246 // and the index is const. The combine will succeed.
247
248 Register Dst = Extract->getReg(Idx: 0);
249 LLT DstTy = MRI.getType(Reg: Dst);
250 LLT SrcTy = MRI.getType(Reg: Build->getSourceReg(I: 0));
251
252 // For buildVectorTrunc, the inputs are truncated.
253 if (!isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_TRUNC, {DstTy, SrcTy}}))
254 return false;
255
256 MatchInfo = [=](MachineIRBuilder &B) {
257 B.buildTrunc(Res: Dst, Op: Build->getSourceReg(I: MaybeIndex->Value.getZExtValue()));
258 };
259
260 return true;
261}
262
263bool CombinerHelper::matchExtractVectorElementWithShuffleVector(
264 const MachineInstr &MI, const MachineInstr &MI2,
265 BuildFnTy &MatchInfo) const {
266 const GExtractVectorElement *Extract = cast<GExtractVectorElement>(Val: &MI);
267 const GShuffleVector *Shuffle = cast<GShuffleVector>(Val: &MI2);
268
269 //
270 // %zero:_(s64) = G_CONSTANT i64 0
271 // %sv:_(<4 x s32>) = G_SHUFFLE_SHUFFLE %arg1(<4 x s32>), %arg2(<4 x s32>),
272 // shufflemask(0, 0, 0, 0)
273 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %sv(<4 x s32>), %zero(s64)
274 //
275 // -->
276 //
277 // %zero1:_(s64) = G_CONSTANT i64 0
278 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %arg1(<4 x s32>), %zero1(s64)
279 //
280 //
281 //
282 //
283 // %three:_(s64) = G_CONSTANT i64 3
284 // %sv:_(<4 x s32>) = G_SHUFFLE_SHUFFLE %arg1(<4 x s32>), %arg2(<4 x s32>),
285 // shufflemask(0, 0, 0, -1)
286 // %extract:_(s32) = G_EXTRACT_VECTOR_ELT %sv(<4 x s32>), %three(s64)
287 //
288 // -->
289 //
290 // %extract:_(s32) = G_IMPLICIT_DEF
291 //
292 //
293
294 APInt Index = getIConstantFromReg(VReg: Extract->getIndexReg(), MRI);
295
296 ArrayRef<int> Mask = Shuffle->getMask();
297
298 unsigned Offset = Index.getZExtValue();
299 int SrcIdx = Mask[Offset];
300
301 LLT Src1Type = MRI.getType(Reg: Shuffle->getSrc1Reg());
302 // At the IR level a <1 x ty> shuffle vector is valid, but we want to extract
303 // from a vector.
304 assert(Src1Type.isVector() && "expected to extract from a vector");
305 unsigned LHSWidth = Src1Type.isVector() ? Src1Type.getNumElements() : 1;
306
307 // Note that there is no one use check.
308 Register Dst = Extract->getReg(Idx: 0);
309 LLT DstTy = MRI.getType(Reg: Dst);
310
311 if (SrcIdx < 0 &&
312 isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_IMPLICIT_DEF, {DstTy}})) {
313 MatchInfo = [=](MachineIRBuilder &B) { B.buildUndef(Res: Dst); };
314 return true;
315 }
316
317 // If the legality check failed, then we still have to abort.
318 if (SrcIdx < 0)
319 return false;
320
321 Register NewVector;
322
323 // We check in which vector and at what offset to look through.
324 if (SrcIdx < (int)LHSWidth) {
325 NewVector = Shuffle->getSrc1Reg();
326 // SrcIdx unchanged
327 } else { // SrcIdx >= LHSWidth
328 NewVector = Shuffle->getSrc2Reg();
329 SrcIdx -= LHSWidth;
330 }
331
332 LLT IdxTy = MRI.getType(Reg: Extract->getIndexReg());
333 LLT NewVectorTy = MRI.getType(Reg: NewVector);
334
335 // We check the legality of the look through.
336 if (!isLegalOrBeforeLegalizer(
337 Query: {TargetOpcode::G_EXTRACT_VECTOR_ELT, {DstTy, NewVectorTy, IdxTy}}) ||
338 !isConstantLegalOrBeforeLegalizer(Ty: {IdxTy}))
339 return false;
340
341 // We look through the shuffle vector.
342 MatchInfo = [=](MachineIRBuilder &B) {
343 auto Idx = B.buildConstant(Res: IdxTy, Val: SrcIdx);
344 B.buildExtractVectorElement(Res: Dst, Val: NewVector, Idx);
345 };
346
347 return true;
348}
349
350bool CombinerHelper::matchInsertVectorElementOOB(MachineInstr &MI) const {
351 GInsertVectorElement *Insert = cast<GInsertVectorElement>(Val: &MI);
352
353 Register Dst = Insert->getReg(Idx: 0);
354 LLT DstTy = MRI.getType(Reg: Dst);
355 Register Index = Insert->getIndexReg();
356
357 if (!DstTy.isFixedVector())
358 return false;
359
360 std::optional<ValueAndVReg> MaybeIndex =
361 getIConstantVRegValWithLookThrough(VReg: Index, MRI);
362
363 if (MaybeIndex && MaybeIndex->Value.uge(RHS: DstTy.getNumElements()) &&
364 isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
365 return true;
366
367 return false;
368}
369
370bool CombinerHelper::matchAddOfVScale(const MachineOperand &MO,
371 BuildFnTy &MatchInfo) const {
372 Register Dst = MO.getReg();
373 GVScale *LHSVScale, *RHSVScale;
374 if (!mi_match(R: Dst, MRI, P: m_GAdd(L: m_GVScale(Inst&: LHSVScale), R: m_GVScale(Inst&: RHSVScale))))
375 return false;
376
377 if (!MRI.hasOneNonDBGUse(RegNo: LHSVScale->getReg(Idx: 0)) ||
378 !MRI.hasOneNonDBGUse(RegNo: RHSVScale->getReg(Idx: 0)))
379 return false;
380
381 MatchInfo = [=](MachineIRBuilder &B) {
382 B.buildVScale(Res: Dst, MinElts: LHSVScale->getSrc() + RHSVScale->getSrc());
383 };
384
385 return true;
386}
387
388bool CombinerHelper::matchMulOfVScale(const MachineOperand &MO,
389 BuildFnTy &MatchInfo) const {
390 Register Dst = MO.getReg();
391 GVScale *LHSVScale;
392 Register RHSReg;
393 if (!mi_match(R: Dst, MRI, P: m_GMul(L: m_GVScale(Inst&: LHSVScale), R: m_Reg(R&: RHSReg))))
394 return false;
395
396 std::optional<APInt> MaybeRHS = getIConstantVRegVal(VReg: RHSReg, MRI);
397 if (!MaybeRHS)
398 return false;
399
400 if (!MRI.hasOneNonDBGUse(RegNo: LHSVScale->getReg(Idx: 0)))
401 return false;
402
403 MatchInfo = [=](MachineIRBuilder &B) {
404 B.buildVScale(Res: Dst, MinElts: LHSVScale->getSrc() * *MaybeRHS);
405 };
406
407 return true;
408}
409
410bool CombinerHelper::matchSubOfVScale(const MachineOperand &MO,
411 BuildFnTy &MatchInfo) const {
412 Register Dst = MO.getReg();
413 Register SubLHS;
414 GVScale *RHSVScale;
415 uint32_t Flags;
416 if (!mi_match(R: Dst, MRI,
417 P: m_GSub(L: m_Reg(R&: SubLHS), R: m_GVScale(Inst&: RHSVScale), Flags: m_MIFlags(Flags))))
418 return false;
419
420 LLT DstTy = MRI.getType(Reg: Dst);
421
422 if (!MRI.hasOneNonDBGUse(RegNo: RHSVScale->getReg(Idx: 0)) ||
423 !isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_ADD, DstTy}))
424 return false;
425
426 MatchInfo = [=](MachineIRBuilder &B) {
427 auto VScale = B.buildVScale(Res: DstTy, MinElts: -RHSVScale->getSrc());
428 B.buildAdd(Dst, Src0: SubLHS, Src1: VScale, Flags);
429 };
430
431 return true;
432}
433
434bool CombinerHelper::matchShlOfVScale(const MachineOperand &MO,
435 BuildFnTy &MatchInfo) const {
436 Register Dst = MO.getReg();
437 GVScale *LHSVScale;
438 Register ShiftReg;
439 if (!mi_match(R: Dst, MRI, P: m_GShl(L: m_GVScale(Inst&: LHSVScale), R: m_Reg(R&: ShiftReg))))
440 return false;
441
442 std::optional<APInt> MaybeRHS = getIConstantVRegVal(VReg: ShiftReg, MRI);
443 if (!MaybeRHS)
444 return false;
445
446 LLT DstTy = MRI.getType(Reg: Dst);
447
448 if (!MRI.hasOneNonDBGUse(RegNo: LHSVScale->getReg(Idx: 0)) ||
449 !isLegalOrBeforeLegalizer(Query: {TargetOpcode::G_VSCALE, DstTy}))
450 return false;
451
452 MatchInfo = [=](MachineIRBuilder &B) {
453 B.buildVScale(Res: Dst, MinElts: LHSVScale->getSrc().shl(ShiftAmt: *MaybeRHS));
454 };
455
456 return true;
457}
458