Bug Summary

File:llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
Warning:line 196, column 39
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InstCombineVectorOps.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/lib/Transforms/InstCombine -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/lib/Transforms/InstCombine -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-01-13-084841-49055-1 -x c++ /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1//===- InstCombineVectorOps.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 instcombine for ExtractElement, InsertElement and
10// ShuffleVector.
11//
12//===----------------------------------------------------------------------===//
13
14#include "InstCombineInternal.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/VectorUtils.h"
22#include "llvm/IR/BasicBlock.h"
23#include "llvm/IR/Constant.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/DerivedTypes.h"
26#include "llvm/IR/InstrTypes.h"
27#include "llvm/IR/Instruction.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/Operator.h"
30#include "llvm/IR/PatternMatch.h"
31#include "llvm/IR/Type.h"
32#include "llvm/IR/User.h"
33#include "llvm/IR/Value.h"
34#include "llvm/Support/Casting.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
37#include <cassert>
38#include <cstdint>
39#include <iterator>
40#include <utility>
41
42using namespace llvm;
43using namespace PatternMatch;
44
45#define DEBUG_TYPE"instcombine" "instcombine"
46
47/// Return true if the value is cheaper to scalarize than it is to leave as a
48/// vector operation. IsConstantExtractIndex indicates whether we are extracting
49/// one known element from a vector constant.
50///
51/// FIXME: It's possible to create more instructions than previously existed.
52static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex) {
53 // If we can pick a scalar constant value out of a vector, that is free.
54 if (auto *C = dyn_cast<Constant>(V))
55 return IsConstantExtractIndex || C->getSplatValue();
56
57 // An insertelement to the same constant index as our extract will simplify
58 // to the scalar inserted element. An insertelement to a different constant
59 // index is irrelevant to our extract.
60 if (match(V, m_InsertElement(m_Value(), m_Value(), m_ConstantInt())))
61 return IsConstantExtractIndex;
62
63 if (match(V, m_OneUse(m_Load(m_Value()))))
64 return true;
65
66 Value *V0, *V1;
67 if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1)))))
68 if (cheapToScalarize(V0, IsConstantExtractIndex) ||
69 cheapToScalarize(V1, IsConstantExtractIndex))
70 return true;
71
72 CmpInst::Predicate UnusedPred;
73 if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1)))))
74 if (cheapToScalarize(V0, IsConstantExtractIndex) ||
75 cheapToScalarize(V1, IsConstantExtractIndex))
76 return true;
77
78 return false;
79}
80
81// If we have a PHI node with a vector type that is only used to feed
82// itself and be an operand of extractelement at a constant location,
83// try to replace the PHI of the vector type with a PHI of a scalar type.
84Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
85 SmallVector<Instruction *, 2> Extracts;
86 // The users we want the PHI to have are:
87 // 1) The EI ExtractElement (we already know this)
88 // 2) Possibly more ExtractElements with the same index.
89 // 3) Another operand, which will feed back into the PHI.
90 Instruction *PHIUser = nullptr;
91 for (auto U : PN->users()) {
92 if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
93 if (EI.getIndexOperand() == EU->getIndexOperand())
94 Extracts.push_back(EU);
95 else
96 return nullptr;
97 } else if (!PHIUser) {
98 PHIUser = cast<Instruction>(U);
99 } else {
100 return nullptr;
101 }
102 }
103
104 if (!PHIUser)
105 return nullptr;
106
107 // Verify that this PHI user has one use, which is the PHI itself,
108 // and that it is a binary operation which is cheap to scalarize.
109 // otherwise return nullptr.
110 if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
111 !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
112 return nullptr;
113
114 // Create a scalar PHI node that will replace the vector PHI node
115 // just before the current PHI node.
116 PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
117 PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
118 // Scalarize each PHI operand.
119 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
120 Value *PHIInVal = PN->getIncomingValue(i);
121 BasicBlock *inBB = PN->getIncomingBlock(i);
122 Value *Elt = EI.getIndexOperand();
123 // If the operand is the PHI induction variable:
124 if (PHIInVal == PHIUser) {
125 // Scalarize the binary operation. Its first operand is the
126 // scalar PHI, and the second operand is extracted from the other
127 // vector operand.
128 BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
129 unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
130 Value *Op = InsertNewInstWith(
131 ExtractElementInst::Create(B0->getOperand(opId), Elt,
132 B0->getOperand(opId)->getName() + ".Elt"),
133 *B0);
134 Value *newPHIUser = InsertNewInstWith(
135 BinaryOperator::CreateWithCopiedFlags(B0->getOpcode(),
136 scalarPHI, Op, B0), *B0);
137 scalarPHI->addIncoming(newPHIUser, inBB);
138 } else {
139 // Scalarize PHI input:
140 Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
141 // Insert the new instruction into the predecessor basic block.
142 Instruction *pos = dyn_cast<Instruction>(PHIInVal);
143 BasicBlock::iterator InsertPos;
144 if (pos && !isa<PHINode>(pos)) {
145 InsertPos = ++pos->getIterator();
146 } else {
147 InsertPos = inBB->getFirstInsertionPt();
148 }
149
150 InsertNewInstWith(newEI, *InsertPos);
151
152 scalarPHI->addIncoming(newEI, inBB);
153 }
154 }
155
156 for (auto E : Extracts)
157 replaceInstUsesWith(*E, scalarPHI);
158
159 return &EI;
160}
161
162static Instruction *foldBitcastExtElt(ExtractElementInst &Ext,
163 InstCombiner::BuilderTy &Builder,
164 bool IsBigEndian) {
165 Value *X;
166 uint64_t ExtIndexC;
167 if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
9
Taking false branch
168 !X->getType()->isVectorTy() ||
169 !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
170 return nullptr;
171
172 // If this extractelement is using a bitcast from a vector of the same number
173 // of elements, see if we can find the source element from the source vector:
174 // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
175 Type *SrcTy = X->getType();
176 Type *DestTy = Ext.getType();
177 unsigned NumSrcElts = SrcTy->getVectorNumElements();
10
'NumSrcElts' initialized here
178 unsigned NumElts = Ext.getVectorOperandType()->getNumElements();
179 if (NumSrcElts == NumElts)
11
Assuming 'NumSrcElts' is not equal to 'NumElts'
12
Taking false branch
180 if (Value *Elt = findScalarElement(X, ExtIndexC))
181 return new BitCastInst(Elt, DestTy);
182
183 // If the source elements are wider than the destination, try to shift and
184 // truncate a subset of scalar bits of an insert op.
185 if (NumSrcElts < NumElts) {
13
Assuming 'NumSrcElts' is < 'NumElts'
14
Taking true branch
186 Value *Scalar;
187 uint64_t InsIndexC;
188 if (!match(X, m_InsertElement(m_Value(), m_Value(Scalar),
15
Calling 'match<llvm::Value, llvm::PatternMatch::ThreeOps_match<llvm::PatternMatch::class_match<llvm::Value>, llvm::PatternMatch::bind_ty<llvm::Value>, llvm::PatternMatch::bind_const_intval_ty, 62>>'
23
Returning from 'match<llvm::Value, llvm::PatternMatch::ThreeOps_match<llvm::PatternMatch::class_match<llvm::Value>, llvm::PatternMatch::bind_ty<llvm::Value>, llvm::PatternMatch::bind_const_intval_ty, 62>>'
24
Taking false branch
189 m_ConstantInt(InsIndexC))))
190 return nullptr;
191
192 // The extract must be from the subset of vector elements that we inserted
193 // into. Example: if we inserted element 1 of a <2 x i64> and we are
194 // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
195 // of elements 4-7 of the bitcasted vector.
196 unsigned NarrowingRatio = NumElts / NumSrcElts;
25
Division by zero
197 if (ExtIndexC / NarrowingRatio != InsIndexC)
198 return nullptr;
199
200 // We are extracting part of the original scalar. How that scalar is
201 // inserted into the vector depends on the endian-ness. Example:
202 // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
203 // +--+--+--+--+--+--+--+--+
204 // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
205 // extelt <4 x i16> V', 3: | |S2|S3|
206 // +--+--+--+--+--+--+--+--+
207 // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
208 // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
209 // In this example, we must right-shift little-endian. Big-endian is just a
210 // truncate.
211 unsigned Chunk = ExtIndexC % NarrowingRatio;
212 if (IsBigEndian)
213 Chunk = NarrowingRatio - 1 - Chunk;
214
215 // Bail out if this is an FP vector to FP vector sequence. That would take
216 // more instructions than we started with unless there is no shift, and it
217 // may not be handled as well in the backend.
218 bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
219 bool NeedDestBitcast = DestTy->isFloatingPointTy();
220 if (NeedSrcBitcast && NeedDestBitcast)
221 return nullptr;
222
223 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
224 unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
225 unsigned ShAmt = Chunk * DestWidth;
226
227 // TODO: This limitation is more strict than necessary. We could sum the
228 // number of new instructions and subtract the number eliminated to know if
229 // we can proceed.
230 if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
231 if (NeedSrcBitcast || NeedDestBitcast)
232 return nullptr;
233
234 if (NeedSrcBitcast) {
235 Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
236 Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
237 }
238
239 if (ShAmt) {
240 // Bail out if we could end with more instructions than we started with.
241 if (!Ext.getVectorOperand()->hasOneUse())
242 return nullptr;
243 Scalar = Builder.CreateLShr(Scalar, ShAmt);
244 }
245
246 if (NeedDestBitcast) {
247 Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
248 return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
249 }
250 return new TruncInst(Scalar, DestTy);
251 }
252
253 return nullptr;
254}
255
256/// Find elements of V demanded by UserInstr.
257static APInt findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr) {
258 unsigned VWidth = V->getType()->getVectorNumElements();
259
260 // Conservatively assume that all elements are needed.
261 APInt UsedElts(APInt::getAllOnesValue(VWidth));
262
263 switch (UserInstr->getOpcode()) {
264 case Instruction::ExtractElement: {
265 ExtractElementInst *EEI = cast<ExtractElementInst>(UserInstr);
266 assert(EEI->getVectorOperand() == V)((EEI->getVectorOperand() == V) ? static_cast<void> (
0) : __assert_fail ("EEI->getVectorOperand() == V", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 266, __PRETTY_FUNCTION__))
;
267 ConstantInt *EEIIndexC = dyn_cast<ConstantInt>(EEI->getIndexOperand());
268 if (EEIIndexC && EEIIndexC->getValue().ult(VWidth)) {
269 UsedElts = APInt::getOneBitSet(VWidth, EEIIndexC->getZExtValue());
270 }
271 break;
272 }
273 case Instruction::ShuffleVector: {
274 ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(UserInstr);
275 unsigned MaskNumElts = UserInstr->getType()->getVectorNumElements();
276
277 UsedElts = APInt(VWidth, 0);
278 for (unsigned i = 0; i < MaskNumElts; i++) {
279 unsigned MaskVal = Shuffle->getMaskValue(i);
280 if (MaskVal == -1u || MaskVal >= 2 * VWidth)
281 continue;
282 if (Shuffle->getOperand(0) == V && (MaskVal < VWidth))
283 UsedElts.setBit(MaskVal);
284 if (Shuffle->getOperand(1) == V &&
285 ((MaskVal >= VWidth) && (MaskVal < 2 * VWidth)))
286 UsedElts.setBit(MaskVal - VWidth);
287 }
288 break;
289 }
290 default:
291 break;
292 }
293 return UsedElts;
294}
295
296/// Find union of elements of V demanded by all its users.
297/// If it is known by querying findDemandedEltsBySingleUser that
298/// no user demands an element of V, then the corresponding bit
299/// remains unset in the returned value.
300static APInt findDemandedEltsByAllUsers(Value *V) {
301 unsigned VWidth = V->getType()->getVectorNumElements();
302
303 APInt UnionUsedElts(VWidth, 0);
304 for (const Use &U : V->uses()) {
305 if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
306 UnionUsedElts |= findDemandedEltsBySingleUser(V, I);
307 } else {
308 UnionUsedElts = APInt::getAllOnesValue(VWidth);
309 break;
310 }
311
312 if (UnionUsedElts.isAllOnesValue())
313 break;
314 }
315
316 return UnionUsedElts;
317}
318
319Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
320 Value *SrcVec = EI.getVectorOperand();
321 Value *Index = EI.getIndexOperand();
322 if (Value *V = SimplifyExtractElementInst(SrcVec, Index,
1
Assuming 'V' is null
2
Taking false branch
323 SQ.getWithInstruction(&EI)))
324 return replaceInstUsesWith(EI, V);
325
326 // If extracting a specified index from the vector, see if we can recursively
327 // find a previously computed scalar that was inserted into the vector.
328 auto *IndexC = dyn_cast<ConstantInt>(Index);
3
Assuming 'Index' is a 'ConstantInt'
329 if (IndexC
3.1
'IndexC' is non-null
3.1
'IndexC' is non-null
) {
4
Taking true branch
330 unsigned NumElts = EI.getVectorOperandType()->getNumElements();
331
332 // InstSimplify should handle cases where the index is invalid.
333 if (!IndexC->getValue().ule(NumElts))
5
Taking false branch
334 return nullptr;
335
336 // This instruction only demands the single element from the input vector.
337 if (NumElts != 1) {
6
Assuming 'NumElts' is equal to 1
7
Taking false branch
338 // If the input vector has a single use, simplify it based on this use
339 // property.
340 if (SrcVec->hasOneUse()) {
341 APInt UndefElts(NumElts, 0);
342 APInt DemandedElts(NumElts, 0);
343 DemandedElts.setBit(IndexC->getZExtValue());
344 if (Value *V =
345 SimplifyDemandedVectorElts(SrcVec, DemandedElts, UndefElts)) {
346 EI.setOperand(0, V);
347 return &EI;
348 }
349 } else {
350 // If the input vector has multiple uses, simplify it based on a union
351 // of all elements used.
352 APInt DemandedElts = findDemandedEltsByAllUsers(SrcVec);
353 if (!DemandedElts.isAllOnesValue()) {
354 APInt UndefElts(NumElts, 0);
355 if (Value *V = SimplifyDemandedVectorElts(
356 SrcVec, DemandedElts, UndefElts, 0 /* Depth */,
357 true /* AllowMultipleUsers */)) {
358 if (V != SrcVec) {
359 SrcVec->replaceAllUsesWith(V);
360 return &EI;
361 }
362 }
363 }
364 }
365 }
366 if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
8
Calling 'foldBitcastExtElt'
367 return I;
368
369 // If there's a vector PHI feeding a scalar use through this extractelement
370 // instruction, try to scalarize the PHI.
371 if (auto *Phi = dyn_cast<PHINode>(SrcVec))
372 if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
373 return ScalarPHI;
374 }
375
376 BinaryOperator *BO;
377 if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
378 // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
379 Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
380 Value *E0 = Builder.CreateExtractElement(X, Index);
381 Value *E1 = Builder.CreateExtractElement(Y, Index);
382 return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
383 }
384
385 Value *X, *Y;
386 CmpInst::Predicate Pred;
387 if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
388 cheapToScalarize(SrcVec, IndexC)) {
389 // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
390 Value *E0 = Builder.CreateExtractElement(X, Index);
391 Value *E1 = Builder.CreateExtractElement(Y, Index);
392 return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
393 }
394
395 if (auto *I = dyn_cast<Instruction>(SrcVec)) {
396 if (auto *IE = dyn_cast<InsertElementInst>(I)) {
397 // Extracting the inserted element?
398 if (IE->getOperand(2) == Index)
399 return replaceInstUsesWith(EI, IE->getOperand(1));
400 // If the inserted and extracted elements are constants, they must not
401 // be the same value, extract from the pre-inserted value instead.
402 if (isa<Constant>(IE->getOperand(2)) && IndexC) {
403 Worklist.AddValue(SrcVec);
404 EI.setOperand(0, IE->getOperand(0));
405 return &EI;
406 }
407 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
408 // If this is extracting an element from a shufflevector, figure out where
409 // it came from and extract from the appropriate input element instead.
410 if (auto *Elt = dyn_cast<ConstantInt>(Index)) {
411 int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
412 Value *Src;
413 unsigned LHSWidth =
414 SVI->getOperand(0)->getType()->getVectorNumElements();
415
416 if (SrcIdx < 0)
417 return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
418 if (SrcIdx < (int)LHSWidth)
419 Src = SVI->getOperand(0);
420 else {
421 SrcIdx -= LHSWidth;
422 Src = SVI->getOperand(1);
423 }
424 Type *Int32Ty = Type::getInt32Ty(EI.getContext());
425 return ExtractElementInst::Create(Src,
426 ConstantInt::get(Int32Ty,
427 SrcIdx, false));
428 }
429 } else if (auto *CI = dyn_cast<CastInst>(I)) {
430 // Canonicalize extractelement(cast) -> cast(extractelement).
431 // Bitcasts can change the number of vector elements, and they cost
432 // nothing.
433 if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
434 Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index);
435 Worklist.AddValue(EE);
436 return CastInst::Create(CI->getOpcode(), EE, EI.getType());
437 }
438 }
439 }
440 return nullptr;
441}
442
443/// If V is a shuffle of values that ONLY returns elements from either LHS or
444/// RHS, return the shuffle mask and true. Otherwise, return false.
445static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
446 SmallVectorImpl<Constant*> &Mask) {
447 assert(LHS->getType() == RHS->getType() &&((LHS->getType() == RHS->getType() && "Invalid CollectSingleShuffleElements"
) ? static_cast<void> (0) : __assert_fail ("LHS->getType() == RHS->getType() && \"Invalid CollectSingleShuffleElements\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 448, __PRETTY_FUNCTION__))
448 "Invalid CollectSingleShuffleElements")((LHS->getType() == RHS->getType() && "Invalid CollectSingleShuffleElements"
) ? static_cast<void> (0) : __assert_fail ("LHS->getType() == RHS->getType() && \"Invalid CollectSingleShuffleElements\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 448, __PRETTY_FUNCTION__))
;
449 unsigned NumElts = V->getType()->getVectorNumElements();
450
451 if (isa<UndefValue>(V)) {
452 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
453 return true;
454 }
455
456 if (V == LHS) {
457 for (unsigned i = 0; i != NumElts; ++i)
458 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
459 return true;
460 }
461
462 if (V == RHS) {
463 for (unsigned i = 0; i != NumElts; ++i)
464 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
465 i+NumElts));
466 return true;
467 }
468
469 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
470 // If this is an insert of an extract from some other vector, include it.
471 Value *VecOp = IEI->getOperand(0);
472 Value *ScalarOp = IEI->getOperand(1);
473 Value *IdxOp = IEI->getOperand(2);
474
475 if (!isa<ConstantInt>(IdxOp))
476 return false;
477 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
478
479 if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
480 // We can handle this if the vector we are inserting into is
481 // transitively ok.
482 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
483 // If so, update the mask to reflect the inserted undef.
484 Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
485 return true;
486 }
487 } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
488 if (isa<ConstantInt>(EI->getOperand(1))) {
489 unsigned ExtractedIdx =
490 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
491 unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
492
493 // This must be extracting from either LHS or RHS.
494 if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
495 // We can handle this if the vector we are inserting into is
496 // transitively ok.
497 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
498 // If so, update the mask to reflect the inserted value.
499 if (EI->getOperand(0) == LHS) {
500 Mask[InsertedIdx % NumElts] =
501 ConstantInt::get(Type::getInt32Ty(V->getContext()),
502 ExtractedIdx);
503 } else {
504 assert(EI->getOperand(0) == RHS)((EI->getOperand(0) == RHS) ? static_cast<void> (0) :
__assert_fail ("EI->getOperand(0) == RHS", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 504, __PRETTY_FUNCTION__))
;
505 Mask[InsertedIdx % NumElts] =
506 ConstantInt::get(Type::getInt32Ty(V->getContext()),
507 ExtractedIdx + NumLHSElts);
508 }
509 return true;
510 }
511 }
512 }
513 }
514 }
515
516 return false;
517}
518
519/// If we have insertion into a vector that is wider than the vector that we
520/// are extracting from, try to widen the source vector to allow a single
521/// shufflevector to replace one or more insert/extract pairs.
522static void replaceExtractElements(InsertElementInst *InsElt,
523 ExtractElementInst *ExtElt,
524 InstCombiner &IC) {
525 VectorType *InsVecType = InsElt->getType();
526 VectorType *ExtVecType = ExtElt->getVectorOperandType();
527 unsigned NumInsElts = InsVecType->getVectorNumElements();
528 unsigned NumExtElts = ExtVecType->getVectorNumElements();
529
530 // The inserted-to vector must be wider than the extracted-from vector.
531 if (InsVecType->getElementType() != ExtVecType->getElementType() ||
532 NumExtElts >= NumInsElts)
533 return;
534
535 // Create a shuffle mask to widen the extended-from vector using undefined
536 // values. The mask selects all of the values of the original vector followed
537 // by as many undefined values as needed to create a vector of the same length
538 // as the inserted-to vector.
539 SmallVector<Constant *, 16> ExtendMask;
540 IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
541 for (unsigned i = 0; i < NumExtElts; ++i)
542 ExtendMask.push_back(ConstantInt::get(IntType, i));
543 for (unsigned i = NumExtElts; i < NumInsElts; ++i)
544 ExtendMask.push_back(UndefValue::get(IntType));
545
546 Value *ExtVecOp = ExtElt->getVectorOperand();
547 auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
548 BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
549 ? ExtVecOpInst->getParent()
550 : ExtElt->getParent();
551
552 // TODO: This restriction matches the basic block check below when creating
553 // new extractelement instructions. If that limitation is removed, this one
554 // could also be removed. But for now, we just bail out to ensure that we
555 // will replace the extractelement instruction that is feeding our
556 // insertelement instruction. This allows the insertelement to then be
557 // replaced by a shufflevector. If the insertelement is not replaced, we can
558 // induce infinite looping because there's an optimization for extractelement
559 // that will delete our widening shuffle. This would trigger another attempt
560 // here to create that shuffle, and we spin forever.
561 if (InsertionBlock != InsElt->getParent())
562 return;
563
564 // TODO: This restriction matches the check in visitInsertElementInst() and
565 // prevents an infinite loop caused by not turning the extract/insert pair
566 // into a shuffle. We really should not need either check, but we're lacking
567 // folds for shufflevectors because we're afraid to generate shuffle masks
568 // that the backend can't handle.
569 if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
570 return;
571
572 auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
573 ConstantVector::get(ExtendMask));
574
575 // Insert the new shuffle after the vector operand of the extract is defined
576 // (as long as it's not a PHI) or at the start of the basic block of the
577 // extract, so any subsequent extracts in the same basic block can use it.
578 // TODO: Insert before the earliest ExtractElementInst that is replaced.
579 if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
580 WideVec->insertAfter(ExtVecOpInst);
581 else
582 IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
583
584 // Replace extracts from the original narrow vector with extracts from the new
585 // wide vector.
586 for (User *U : ExtVecOp->users()) {
587 ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
588 if (!OldExt || OldExt->getParent() != WideVec->getParent())
589 continue;
590 auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
591 NewExt->insertAfter(OldExt);
592 IC.replaceInstUsesWith(*OldExt, NewExt);
593 }
594}
595
596/// We are building a shuffle to create V, which is a sequence of insertelement,
597/// extractelement pairs. If PermittedRHS is set, then we must either use it or
598/// not rely on the second vector source. Return a std::pair containing the
599/// left and right vectors of the proposed shuffle (or 0), and set the Mask
600/// parameter as required.
601///
602/// Note: we intentionally don't try to fold earlier shuffles since they have
603/// often been chosen carefully to be efficiently implementable on the target.
604using ShuffleOps = std::pair<Value *, Value *>;
605
606static ShuffleOps collectShuffleElements(Value *V,
607 SmallVectorImpl<Constant *> &Mask,
608 Value *PermittedRHS,
609 InstCombiner &IC) {
610 assert(V->getType()->isVectorTy() && "Invalid shuffle!")((V->getType()->isVectorTy() && "Invalid shuffle!"
) ? static_cast<void> (0) : __assert_fail ("V->getType()->isVectorTy() && \"Invalid shuffle!\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 610, __PRETTY_FUNCTION__))
;
611 unsigned NumElts = V->getType()->getVectorNumElements();
612
613 if (isa<UndefValue>(V)) {
614 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
615 return std::make_pair(
616 PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
617 }
618
619 if (isa<ConstantAggregateZero>(V)) {
620 Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
621 return std::make_pair(V, nullptr);
622 }
623
624 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
625 // If this is an insert of an extract from some other vector, include it.
626 Value *VecOp = IEI->getOperand(0);
627 Value *ScalarOp = IEI->getOperand(1);
628 Value *IdxOp = IEI->getOperand(2);
629
630 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
631 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
632 unsigned ExtractedIdx =
633 cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
634 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
635
636 // Either the extracted from or inserted into vector must be RHSVec,
637 // otherwise we'd end up with a shuffle of three inputs.
638 if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
639 Value *RHS = EI->getOperand(0);
640 ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
641 assert(LR.second == nullptr || LR.second == RHS)((LR.second == nullptr || LR.second == RHS) ? static_cast<
void> (0) : __assert_fail ("LR.second == nullptr || LR.second == RHS"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 641, __PRETTY_FUNCTION__))
;
642
643 if (LR.first->getType() != RHS->getType()) {
644 // Although we are giving up for now, see if we can create extracts
645 // that match the inserts for another round of combining.
646 replaceExtractElements(IEI, EI, IC);
647
648 // We tried our best, but we can't find anything compatible with RHS
649 // further up the chain. Return a trivial shuffle.
650 for (unsigned i = 0; i < NumElts; ++i)
651 Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
652 return std::make_pair(V, nullptr);
653 }
654
655 unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
656 Mask[InsertedIdx % NumElts] =
657 ConstantInt::get(Type::getInt32Ty(V->getContext()),
658 NumLHSElts+ExtractedIdx);
659 return std::make_pair(LR.first, RHS);
660 }
661
662 if (VecOp == PermittedRHS) {
663 // We've gone as far as we can: anything on the other side of the
664 // extractelement will already have been converted into a shuffle.
665 unsigned NumLHSElts =
666 EI->getOperand(0)->getType()->getVectorNumElements();
667 for (unsigned i = 0; i != NumElts; ++i)
668 Mask.push_back(ConstantInt::get(
669 Type::getInt32Ty(V->getContext()),
670 i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
671 return std::make_pair(EI->getOperand(0), PermittedRHS);
672 }
673
674 // If this insertelement is a chain that comes from exactly these two
675 // vectors, return the vector and the effective shuffle.
676 if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
677 collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
678 Mask))
679 return std::make_pair(EI->getOperand(0), PermittedRHS);
680 }
681 }
682 }
683
684 // Otherwise, we can't do anything fancy. Return an identity vector.
685 for (unsigned i = 0; i != NumElts; ++i)
686 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
687 return std::make_pair(V, nullptr);
688}
689
690/// Try to find redundant insertvalue instructions, like the following ones:
691/// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
692/// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
693/// Here the second instruction inserts values at the same indices, as the
694/// first one, making the first one redundant.
695/// It should be transformed to:
696/// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
697Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) {
698 bool IsRedundant = false;
699 ArrayRef<unsigned int> FirstIndices = I.getIndices();
700
701 // If there is a chain of insertvalue instructions (each of them except the
702 // last one has only one use and it's another insertvalue insn from this
703 // chain), check if any of the 'children' uses the same indices as the first
704 // instruction. In this case, the first one is redundant.
705 Value *V = &I;
706 unsigned Depth = 0;
707 while (V->hasOneUse() && Depth < 10) {
708 User *U = V->user_back();
709 auto UserInsInst = dyn_cast<InsertValueInst>(U);
710 if (!UserInsInst || U->getOperand(0) != V)
711 break;
712 if (UserInsInst->getIndices() == FirstIndices) {
713 IsRedundant = true;
714 break;
715 }
716 V = UserInsInst;
717 Depth++;
718 }
719
720 if (IsRedundant)
721 return replaceInstUsesWith(I, I.getOperand(0));
722 return nullptr;
723}
724
725static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
726 int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
727 int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
728
729 // A vector select does not change the size of the operands.
730 if (MaskSize != VecSize)
731 return false;
732
733 // Each mask element must be undefined or choose a vector element from one of
734 // the source operands without crossing vector lanes.
735 for (int i = 0; i != MaskSize; ++i) {
736 int Elt = Shuf.getMaskValue(i);
737 if (Elt != -1 && Elt != i && Elt != i + VecSize)
738 return false;
739 }
740
741 return true;
742}
743
744/// Turn a chain of inserts that splats a value into an insert + shuffle:
745/// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
746/// shufflevector(insertelt(X, %k, 0), undef, zero)
747static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) {
748 // We are interested in the last insert in a chain. So if this insert has a
749 // single user and that user is an insert, bail.
750 if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
751 return nullptr;
752
753 auto *VecTy = cast<VectorType>(InsElt.getType());
754 unsigned NumElements = VecTy->getNumElements();
755
756 // Do not try to do this for a one-element vector, since that's a nop,
757 // and will cause an inf-loop.
758 if (NumElements == 1)
759 return nullptr;
760
761 Value *SplatVal = InsElt.getOperand(1);
762 InsertElementInst *CurrIE = &InsElt;
763 SmallVector<bool, 16> ElementPresent(NumElements, false);
764 InsertElementInst *FirstIE = nullptr;
765
766 // Walk the chain backwards, keeping track of which indices we inserted into,
767 // until we hit something that isn't an insert of the splatted value.
768 while (CurrIE) {
769 auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
770 if (!Idx || CurrIE->getOperand(1) != SplatVal)
771 return nullptr;
772
773 auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
774 // Check none of the intermediate steps have any additional uses, except
775 // for the root insertelement instruction, which can be re-used, if it
776 // inserts at position 0.
777 if (CurrIE != &InsElt &&
778 (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
779 return nullptr;
780
781 ElementPresent[Idx->getZExtValue()] = true;
782 FirstIE = CurrIE;
783 CurrIE = NextIE;
784 }
785
786 // If this is just a single insertelement (not a sequence), we are done.
787 if (FirstIE == &InsElt)
788 return nullptr;
789
790 // If we are not inserting into an undef vector, make sure we've seen an
791 // insert into every element.
792 // TODO: If the base vector is not undef, it might be better to create a splat
793 // and then a select-shuffle (blend) with the base vector.
794 if (!isa<UndefValue>(FirstIE->getOperand(0)))
795 if (any_of(ElementPresent, [](bool Present) { return !Present; }))
796 return nullptr;
797
798 // Create the insert + shuffle.
799 Type *Int32Ty = Type::getInt32Ty(InsElt.getContext());
800 UndefValue *UndefVec = UndefValue::get(VecTy);
801 Constant *Zero = ConstantInt::get(Int32Ty, 0);
802 if (!cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
803 FirstIE = InsertElementInst::Create(UndefVec, SplatVal, Zero, "", &InsElt);
804
805 // Splat from element 0, but replace absent elements with undef in the mask.
806 SmallVector<Constant *, 16> Mask(NumElements, Zero);
807 for (unsigned i = 0; i != NumElements; ++i)
808 if (!ElementPresent[i])
809 Mask[i] = UndefValue::get(Int32Ty);
810
811 return new ShuffleVectorInst(FirstIE, UndefVec, ConstantVector::get(Mask));
812}
813
814/// Try to fold an insert element into an existing splat shuffle by changing
815/// the shuffle's mask to include the index of this insert element.
816static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) {
817 // Check if the vector operand of this insert is a canonical splat shuffle.
818 auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
819 if (!Shuf || !Shuf->isZeroEltSplat())
820 return nullptr;
821
822 // Check for a constant insertion index.
823 uint64_t IdxC;
824 if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
825 return nullptr;
826
827 // Check if the splat shuffle's input is the same as this insert's scalar op.
828 Value *X = InsElt.getOperand(1);
829 Value *Op0 = Shuf->getOperand(0);
830 if (!match(Op0, m_InsertElement(m_Undef(), m_Specific(X), m_ZeroInt())))
831 return nullptr;
832
833 // Replace the shuffle mask element at the index of this insert with a zero.
834 // For example:
835 // inselt (shuf (inselt undef, X, 0), undef, <0,undef,0,undef>), X, 1
836 // --> shuf (inselt undef, X, 0), undef, <0,0,0,undef>
837 unsigned NumMaskElts = Shuf->getType()->getVectorNumElements();
838 SmallVector<Constant *, 16> NewMaskVec(NumMaskElts);
839 Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext());
840 Constant *Zero = ConstantInt::getNullValue(I32Ty);
841 for (unsigned i = 0; i != NumMaskElts; ++i)
842 NewMaskVec[i] = i == IdxC ? Zero : Shuf->getMask()->getAggregateElement(i);
843
844 Constant *NewMask = ConstantVector::get(NewMaskVec);
845 return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask);
846}
847
848/// Try to fold an extract+insert element into an existing identity shuffle by
849/// changing the shuffle's mask to include the index of this insert element.
850static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) {
851 // Check if the vector operand of this insert is an identity shuffle.
852 auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
853 if (!Shuf || !isa<UndefValue>(Shuf->getOperand(1)) ||
854 !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding()))
855 return nullptr;
856
857 // Check for a constant insertion index.
858 uint64_t IdxC;
859 if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
860 return nullptr;
861
862 // Check if this insert's scalar op is extracted from the identity shuffle's
863 // input vector.
864 Value *Scalar = InsElt.getOperand(1);
865 Value *X = Shuf->getOperand(0);
866 if (!match(Scalar, m_ExtractElement(m_Specific(X), m_SpecificInt(IdxC))))
867 return nullptr;
868
869 // Replace the shuffle mask element at the index of this extract+insert with
870 // that same index value.
871 // For example:
872 // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask'
873 unsigned NumMaskElts = Shuf->getType()->getVectorNumElements();
874 SmallVector<Constant *, 16> NewMaskVec(NumMaskElts);
875 Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext());
876 Constant *NewMaskEltC = ConstantInt::get(I32Ty, IdxC);
877 Constant *OldMask = Shuf->getMask();
878 for (unsigned i = 0; i != NumMaskElts; ++i) {
879 if (i != IdxC) {
880 // All mask elements besides the inserted element remain the same.
881 NewMaskVec[i] = OldMask->getAggregateElement(i);
882 } else if (OldMask->getAggregateElement(i) == NewMaskEltC) {
883 // If the mask element was already set, there's nothing to do
884 // (demanded elements analysis may unset it later).
885 return nullptr;
886 } else {
887 assert(isa<UndefValue>(OldMask->getAggregateElement(i)) &&((isa<UndefValue>(OldMask->getAggregateElement(i)) &&
"Unexpected shuffle mask element for identity shuffle") ? static_cast
<void> (0) : __assert_fail ("isa<UndefValue>(OldMask->getAggregateElement(i)) && \"Unexpected shuffle mask element for identity shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 888, __PRETTY_FUNCTION__))
888 "Unexpected shuffle mask element for identity shuffle")((isa<UndefValue>(OldMask->getAggregateElement(i)) &&
"Unexpected shuffle mask element for identity shuffle") ? static_cast
<void> (0) : __assert_fail ("isa<UndefValue>(OldMask->getAggregateElement(i)) && \"Unexpected shuffle mask element for identity shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 888, __PRETTY_FUNCTION__))
;
889 NewMaskVec[i] = NewMaskEltC;
890 }
891 }
892
893 Constant *NewMask = ConstantVector::get(NewMaskVec);
894 return new ShuffleVectorInst(X, Shuf->getOperand(1), NewMask);
895}
896
897/// If we have an insertelement instruction feeding into another insertelement
898/// and the 2nd is inserting a constant into the vector, canonicalize that
899/// constant insertion before the insertion of a variable:
900///
901/// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
902/// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
903///
904/// This has the potential of eliminating the 2nd insertelement instruction
905/// via constant folding of the scalar constant into a vector constant.
906static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
907 InstCombiner::BuilderTy &Builder) {
908 auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
909 if (!InsElt1 || !InsElt1->hasOneUse())
910 return nullptr;
911
912 Value *X, *Y;
913 Constant *ScalarC;
914 ConstantInt *IdxC1, *IdxC2;
915 if (match(InsElt1->getOperand(0), m_Value(X)) &&
916 match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
917 match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
918 match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
919 match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
920 Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
921 return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
922 }
923
924 return nullptr;
925}
926
927/// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
928/// --> shufflevector X, CVec', Mask'
929static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
930 auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
931 // Bail out if the parent has more than one use. In that case, we'd be
932 // replacing the insertelt with a shuffle, and that's not a clear win.
933 if (!Inst || !Inst->hasOneUse())
934 return nullptr;
935 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
936 // The shuffle must have a constant vector operand. The insertelt must have
937 // a constant scalar being inserted at a constant position in the vector.
938 Constant *ShufConstVec, *InsEltScalar;
939 uint64_t InsEltIndex;
940 if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
941 !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
942 !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
943 return nullptr;
944
945 // Adding an element to an arbitrary shuffle could be expensive, but a
946 // shuffle that selects elements from vectors without crossing lanes is
947 // assumed cheap.
948 // If we're just adding a constant into that shuffle, it will still be
949 // cheap.
950 if (!isShuffleEquivalentToSelect(*Shuf))
951 return nullptr;
952
953 // From the above 'select' check, we know that the mask has the same number
954 // of elements as the vector input operands. We also know that each constant
955 // input element is used in its lane and can not be used more than once by
956 // the shuffle. Therefore, replace the constant in the shuffle's constant
957 // vector with the insertelt constant. Replace the constant in the shuffle's
958 // mask vector with the insertelt index plus the length of the vector
959 // (because the constant vector operand of a shuffle is always the 2nd
960 // operand).
961 Constant *Mask = Shuf->getMask();
962 unsigned NumElts = Mask->getType()->getVectorNumElements();
963 SmallVector<Constant *, 16> NewShufElts(NumElts);
964 SmallVector<Constant *, 16> NewMaskElts(NumElts);
965 for (unsigned I = 0; I != NumElts; ++I) {
966 if (I == InsEltIndex) {
967 NewShufElts[I] = InsEltScalar;
968 Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
969 NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
970 } else {
971 // Copy over the existing values.
972 NewShufElts[I] = ShufConstVec->getAggregateElement(I);
973 NewMaskElts[I] = Mask->getAggregateElement(I);
974 }
975 }
976
977 // Create new operands for a shuffle that includes the constant of the
978 // original insertelt. The old shuffle will be dead now.
979 return new ShuffleVectorInst(Shuf->getOperand(0),
980 ConstantVector::get(NewShufElts),
981 ConstantVector::get(NewMaskElts));
982 } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
983 // Transform sequences of insertelements ops with constant data/indexes into
984 // a single shuffle op.
985 unsigned NumElts = InsElt.getType()->getNumElements();
986
987 uint64_t InsertIdx[2];
988 Constant *Val[2];
989 if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
990 !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
991 !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
992 !match(IEI->getOperand(1), m_Constant(Val[1])))
993 return nullptr;
994 SmallVector<Constant *, 16> Values(NumElts);
995 SmallVector<Constant *, 16> Mask(NumElts);
996 auto ValI = std::begin(Val);
997 // Generate new constant vector and mask.
998 // We have 2 values/masks from the insertelements instructions. Insert them
999 // into new value/mask vectors.
1000 for (uint64_t I : InsertIdx) {
1001 if (!Values[I]) {
1002 assert(!Mask[I])((!Mask[I]) ? static_cast<void> (0) : __assert_fail ("!Mask[I]"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1002, __PRETTY_FUNCTION__))
;
1003 Values[I] = *ValI;
1004 Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
1005 NumElts + I);
1006 }
1007 ++ValI;
1008 }
1009 // Remaining values are filled with 'undef' values.
1010 for (unsigned I = 0; I < NumElts; ++I) {
1011 if (!Values[I]) {
1012 assert(!Mask[I])((!Mask[I]) ? static_cast<void> (0) : __assert_fail ("!Mask[I]"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1012, __PRETTY_FUNCTION__))
;
1013 Values[I] = UndefValue::get(InsElt.getType()->getElementType());
1014 Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
1015 }
1016 }
1017 // Create new operands for a shuffle that includes the constant of the
1018 // original insertelt.
1019 return new ShuffleVectorInst(IEI->getOperand(0),
1020 ConstantVector::get(Values),
1021 ConstantVector::get(Mask));
1022 }
1023 return nullptr;
1024}
1025
1026Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
1027 Value *VecOp = IE.getOperand(0);
1028 Value *ScalarOp = IE.getOperand(1);
1029 Value *IdxOp = IE.getOperand(2);
1030
1031 if (auto *V = SimplifyInsertElementInst(
1032 VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
1033 return replaceInstUsesWith(IE, V);
1034
1035 // If the vector and scalar are both bitcast from the same element type, do
1036 // the insert in that source type followed by bitcast.
1037 Value *VecSrc, *ScalarSrc;
1038 if (match(VecOp, m_BitCast(m_Value(VecSrc))) &&
1039 match(ScalarOp, m_BitCast(m_Value(ScalarSrc))) &&
1040 (VecOp->hasOneUse() || ScalarOp->hasOneUse()) &&
1041 VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() &&
1042 VecSrc->getType()->getVectorElementType() == ScalarSrc->getType()) {
1043 // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp -->
1044 // bitcast (inselt VecSrc, ScalarSrc, IdxOp)
1045 Value *NewInsElt = Builder.CreateInsertElement(VecSrc, ScalarSrc, IdxOp);
1046 return new BitCastInst(NewInsElt, IE.getType());
1047 }
1048
1049 // If the inserted element was extracted from some other vector and both
1050 // indexes are valid constants, try to turn this into a shuffle.
1051 uint64_t InsertedIdx, ExtractedIdx;
1052 Value *ExtVecOp;
1053 if (match(IdxOp, m_ConstantInt(InsertedIdx)) &&
1054 match(ScalarOp, m_ExtractElement(m_Value(ExtVecOp),
1055 m_ConstantInt(ExtractedIdx))) &&
1056 ExtractedIdx < ExtVecOp->getType()->getVectorNumElements()) {
1057 // TODO: Looking at the user(s) to determine if this insert is a
1058 // fold-to-shuffle opportunity does not match the usual instcombine
1059 // constraints. We should decide if the transform is worthy based only
1060 // on this instruction and its operands, but that may not work currently.
1061 //
1062 // Here, we are trying to avoid creating shuffles before reaching
1063 // the end of a chain of extract-insert pairs. This is complicated because
1064 // we do not generally form arbitrary shuffle masks in instcombine
1065 // (because those may codegen poorly), but collectShuffleElements() does
1066 // exactly that.
1067 //
1068 // The rules for determining what is an acceptable target-independent
1069 // shuffle mask are fuzzy because they evolve based on the backend's
1070 // capabilities and real-world impact.
1071 auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
1072 if (!Insert.hasOneUse())
1073 return true;
1074 auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back());
1075 if (!InsertUser)
1076 return true;
1077 return false;
1078 };
1079
1080 // Try to form a shuffle from a chain of extract-insert ops.
1081 if (isShuffleRootCandidate(IE)) {
1082 SmallVector<Constant*, 16> Mask;
1083 ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
1084
1085 // The proposed shuffle may be trivial, in which case we shouldn't
1086 // perform the combine.
1087 if (LR.first != &IE && LR.second != &IE) {
1088 // We now have a shuffle of LHS, RHS, Mask.
1089 if (LR.second == nullptr)
1090 LR.second = UndefValue::get(LR.first->getType());
1091 return new ShuffleVectorInst(LR.first, LR.second,
1092 ConstantVector::get(Mask));
1093 }
1094 }
1095 }
1096
1097 unsigned VWidth = VecOp->getType()->getVectorNumElements();
1098 APInt UndefElts(VWidth, 0);
1099 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1100 if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
1101 if (V != &IE)
1102 return replaceInstUsesWith(IE, V);
1103 return &IE;
1104 }
1105
1106 if (Instruction *Shuf = foldConstantInsEltIntoShuffle(IE))
1107 return Shuf;
1108
1109 if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
1110 return NewInsElt;
1111
1112 if (Instruction *Broadcast = foldInsSequenceIntoSplat(IE))
1113 return Broadcast;
1114
1115 if (Instruction *Splat = foldInsEltIntoSplat(IE))
1116 return Splat;
1117
1118 if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(IE))
1119 return IdentityShuf;
1120
1121 return nullptr;
1122}
1123
1124/// Return true if we can evaluate the specified expression tree if the vector
1125/// elements were shuffled in a different order.
1126static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
1127 unsigned Depth = 5) {
1128 // We can always reorder the elements of a constant.
1129 if (isa<Constant>(V))
1130 return true;
1131
1132 // We won't reorder vector arguments. No IPO here.
1133 Instruction *I = dyn_cast<Instruction>(V);
1134 if (!I) return false;
1135
1136 // Two users may expect different orders of the elements. Don't try it.
1137 if (!I->hasOneUse())
1138 return false;
1139
1140 if (Depth == 0) return false;
1141
1142 switch (I->getOpcode()) {
1143 case Instruction::UDiv:
1144 case Instruction::SDiv:
1145 case Instruction::URem:
1146 case Instruction::SRem:
1147 // Propagating an undefined shuffle mask element to integer div/rem is not
1148 // allowed because those opcodes can create immediate undefined behavior
1149 // from an undefined element in an operand.
1150 if (llvm::any_of(Mask, [](int M){ return M == -1; }))
1151 return false;
1152 LLVM_FALLTHROUGH[[gnu::fallthrough]];
1153 case Instruction::Add:
1154 case Instruction::FAdd:
1155 case Instruction::Sub:
1156 case Instruction::FSub:
1157 case Instruction::Mul:
1158 case Instruction::FMul:
1159 case Instruction::FDiv:
1160 case Instruction::FRem:
1161 case Instruction::Shl:
1162 case Instruction::LShr:
1163 case Instruction::AShr:
1164 case Instruction::And:
1165 case Instruction::Or:
1166 case Instruction::Xor:
1167 case Instruction::ICmp:
1168 case Instruction::FCmp:
1169 case Instruction::Trunc:
1170 case Instruction::ZExt:
1171 case Instruction::SExt:
1172 case Instruction::FPToUI:
1173 case Instruction::FPToSI:
1174 case Instruction::UIToFP:
1175 case Instruction::SIToFP:
1176 case Instruction::FPTrunc:
1177 case Instruction::FPExt:
1178 case Instruction::GetElementPtr: {
1179 // Bail out if we would create longer vector ops. We could allow creating
1180 // longer vector ops, but that may result in more expensive codegen.
1181 Type *ITy = I->getType();
1182 if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements())
1183 return false;
1184 for (Value *Operand : I->operands()) {
1185 if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1186 return false;
1187 }
1188 return true;
1189 }
1190 case Instruction::InsertElement: {
1191 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
1192 if (!CI) return false;
1193 int ElementNumber = CI->getLimitedValue();
1194
1195 // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1196 // can't put an element into multiple indices.
1197 bool SeenOnce = false;
1198 for (int i = 0, e = Mask.size(); i != e; ++i) {
1199 if (Mask[i] == ElementNumber) {
1200 if (SeenOnce)
1201 return false;
1202 SeenOnce = true;
1203 }
1204 }
1205 return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1206 }
1207 }
1208 return false;
1209}
1210
1211/// Rebuild a new instruction just like 'I' but with the new operands given.
1212/// In the event of type mismatch, the type of the operands is correct.
1213static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) {
1214 // We don't want to use the IRBuilder here because we want the replacement
1215 // instructions to appear next to 'I', not the builder's insertion point.
1216 switch (I->getOpcode()) {
1217 case Instruction::Add:
1218 case Instruction::FAdd:
1219 case Instruction::Sub:
1220 case Instruction::FSub:
1221 case Instruction::Mul:
1222 case Instruction::FMul:
1223 case Instruction::UDiv:
1224 case Instruction::SDiv:
1225 case Instruction::FDiv:
1226 case Instruction::URem:
1227 case Instruction::SRem:
1228 case Instruction::FRem:
1229 case Instruction::Shl:
1230 case Instruction::LShr:
1231 case Instruction::AShr:
1232 case Instruction::And:
1233 case Instruction::Or:
1234 case Instruction::Xor: {
1235 BinaryOperator *BO = cast<BinaryOperator>(I);
1236 assert(NewOps.size() == 2 && "binary operator with #ops != 2")((NewOps.size() == 2 && "binary operator with #ops != 2"
) ? static_cast<void> (0) : __assert_fail ("NewOps.size() == 2 && \"binary operator with #ops != 2\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1236, __PRETTY_FUNCTION__))
;
1237 BinaryOperator *New =
1238 BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1239 NewOps[0], NewOps[1], "", BO);
1240 if (isa<OverflowingBinaryOperator>(BO)) {
1241 New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1242 New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1243 }
1244 if (isa<PossiblyExactOperator>(BO)) {
1245 New->setIsExact(BO->isExact());
1246 }
1247 if (isa<FPMathOperator>(BO))
1248 New->copyFastMathFlags(I);
1249 return New;
1250 }
1251 case Instruction::ICmp:
1252 assert(NewOps.size() == 2 && "icmp with #ops != 2")((NewOps.size() == 2 && "icmp with #ops != 2") ? static_cast
<void> (0) : __assert_fail ("NewOps.size() == 2 && \"icmp with #ops != 2\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1252, __PRETTY_FUNCTION__))
;
1253 return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1254 NewOps[0], NewOps[1]);
1255 case Instruction::FCmp:
1256 assert(NewOps.size() == 2 && "fcmp with #ops != 2")((NewOps.size() == 2 && "fcmp with #ops != 2") ? static_cast
<void> (0) : __assert_fail ("NewOps.size() == 2 && \"fcmp with #ops != 2\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1256, __PRETTY_FUNCTION__))
;
1257 return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1258 NewOps[0], NewOps[1]);
1259 case Instruction::Trunc:
1260 case Instruction::ZExt:
1261 case Instruction::SExt:
1262 case Instruction::FPToUI:
1263 case Instruction::FPToSI:
1264 case Instruction::UIToFP:
1265 case Instruction::SIToFP:
1266 case Instruction::FPTrunc:
1267 case Instruction::FPExt: {
1268 // It's possible that the mask has a different number of elements from
1269 // the original cast. We recompute the destination type to match the mask.
1270 Type *DestTy =
1271 VectorType::get(I->getType()->getScalarType(),
1272 NewOps[0]->getType()->getVectorNumElements());
1273 assert(NewOps.size() == 1 && "cast with #ops != 1")((NewOps.size() == 1 && "cast with #ops != 1") ? static_cast
<void> (0) : __assert_fail ("NewOps.size() == 1 && \"cast with #ops != 1\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1273, __PRETTY_FUNCTION__))
;
1274 return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1275 "", I);
1276 }
1277 case Instruction::GetElementPtr: {
1278 Value *Ptr = NewOps[0];
1279 ArrayRef<Value*> Idx = NewOps.slice(1);
1280 GetElementPtrInst *GEP = GetElementPtrInst::Create(
1281 cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1282 GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1283 return GEP;
1284 }
1285 }
1286 llvm_unreachable("failed to rebuild vector instructions")::llvm::llvm_unreachable_internal("failed to rebuild vector instructions"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1286)
;
1287}
1288
1289static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1290 // Mask.size() does not need to be equal to the number of vector elements.
1291
1292 assert(V->getType()->isVectorTy() && "can't reorder non-vector elements")((V->getType()->isVectorTy() && "can't reorder non-vector elements"
) ? static_cast<void> (0) : __assert_fail ("V->getType()->isVectorTy() && \"can't reorder non-vector elements\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1292, __PRETTY_FUNCTION__))
;
1293 Type *EltTy = V->getType()->getScalarType();
1294 Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1295 if (isa<UndefValue>(V))
1296 return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1297
1298 if (isa<ConstantAggregateZero>(V))
1299 return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1300
1301 if (Constant *C = dyn_cast<Constant>(V)) {
1302 SmallVector<Constant *, 16> MaskValues;
1303 for (int i = 0, e = Mask.size(); i != e; ++i) {
1304 if (Mask[i] == -1)
1305 MaskValues.push_back(UndefValue::get(I32Ty));
1306 else
1307 MaskValues.push_back(ConstantInt::get(I32Ty, Mask[i]));
1308 }
1309 return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()),
1310 ConstantVector::get(MaskValues));
1311 }
1312
1313 Instruction *I = cast<Instruction>(V);
1314 switch (I->getOpcode()) {
1315 case Instruction::Add:
1316 case Instruction::FAdd:
1317 case Instruction::Sub:
1318 case Instruction::FSub:
1319 case Instruction::Mul:
1320 case Instruction::FMul:
1321 case Instruction::UDiv:
1322 case Instruction::SDiv:
1323 case Instruction::FDiv:
1324 case Instruction::URem:
1325 case Instruction::SRem:
1326 case Instruction::FRem:
1327 case Instruction::Shl:
1328 case Instruction::LShr:
1329 case Instruction::AShr:
1330 case Instruction::And:
1331 case Instruction::Or:
1332 case Instruction::Xor:
1333 case Instruction::ICmp:
1334 case Instruction::FCmp:
1335 case Instruction::Trunc:
1336 case Instruction::ZExt:
1337 case Instruction::SExt:
1338 case Instruction::FPToUI:
1339 case Instruction::FPToSI:
1340 case Instruction::UIToFP:
1341 case Instruction::SIToFP:
1342 case Instruction::FPTrunc:
1343 case Instruction::FPExt:
1344 case Instruction::Select:
1345 case Instruction::GetElementPtr: {
1346 SmallVector<Value*, 8> NewOps;
1347 bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1348 for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1349 Value *V;
1350 // Recursively call evaluateInDifferentElementOrder on vector arguments
1351 // as well. E.g. GetElementPtr may have scalar operands even if the
1352 // return value is a vector, so we need to examine the operand type.
1353 if (I->getOperand(i)->getType()->isVectorTy())
1354 V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1355 else
1356 V = I->getOperand(i);
1357 NewOps.push_back(V);
1358 NeedsRebuild |= (V != I->getOperand(i));
1359 }
1360 if (NeedsRebuild) {
1361 return buildNew(I, NewOps);
1362 }
1363 return I;
1364 }
1365 case Instruction::InsertElement: {
1366 int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1367
1368 // The insertelement was inserting at Element. Figure out which element
1369 // that becomes after shuffling. The answer is guaranteed to be unique
1370 // by CanEvaluateShuffled.
1371 bool Found = false;
1372 int Index = 0;
1373 for (int e = Mask.size(); Index != e; ++Index) {
1374 if (Mask[Index] == Element) {
1375 Found = true;
1376 break;
1377 }
1378 }
1379
1380 // If element is not in Mask, no need to handle the operand 1 (element to
1381 // be inserted). Just evaluate values in operand 0 according to Mask.
1382 if (!Found)
1383 return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1384
1385 Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1386 return InsertElementInst::Create(V, I->getOperand(1),
1387 ConstantInt::get(I32Ty, Index), "", I);
1388 }
1389 }
1390 llvm_unreachable("failed to reorder elements of vector instruction!")::llvm::llvm_unreachable_internal("failed to reorder elements of vector instruction!"
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1390)
;
1391}
1392
1393// Returns true if the shuffle is extracting a contiguous range of values from
1394// LHS, for example:
1395// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1396// Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1397// Shuffles to: |EE|FF|GG|HH|
1398// +--+--+--+--+
1399static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
1400 SmallVector<int, 16> &Mask) {
1401 unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1402 unsigned MaskElems = Mask.size();
1403 unsigned BegIdx = Mask.front();
1404 unsigned EndIdx = Mask.back();
1405 if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1406 return false;
1407 for (unsigned I = 0; I != MaskElems; ++I)
1408 if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1409 return false;
1410 return true;
1411}
1412
1413/// These are the ingredients in an alternate form binary operator as described
1414/// below.
1415struct BinopElts {
1416 BinaryOperator::BinaryOps Opcode;
1417 Value *Op0;
1418 Value *Op1;
1419 BinopElts(BinaryOperator::BinaryOps Opc = (BinaryOperator::BinaryOps)0,
1420 Value *V0 = nullptr, Value *V1 = nullptr) :
1421 Opcode(Opc), Op0(V0), Op1(V1) {}
1422 operator bool() const { return Opcode != 0; }
1423};
1424
1425/// Binops may be transformed into binops with different opcodes and operands.
1426/// Reverse the usual canonicalization to enable folds with the non-canonical
1427/// form of the binop. If a transform is possible, return the elements of the
1428/// new binop. If not, return invalid elements.
1429static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) {
1430 Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1431 Type *Ty = BO->getType();
1432 switch (BO->getOpcode()) {
1433 case Instruction::Shl: {
1434 // shl X, C --> mul X, (1 << C)
1435 Constant *C;
1436 if (match(BO1, m_Constant(C))) {
1437 Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1438 return { Instruction::Mul, BO0, ShlOne };
1439 }
1440 break;
1441 }
1442 case Instruction::Or: {
1443 // or X, C --> add X, C (when X and C have no common bits set)
1444 const APInt *C;
1445 if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1446 return { Instruction::Add, BO0, BO1 };
1447 break;
1448 }
1449 default:
1450 break;
1451 }
1452 return {};
1453}
1454
1455static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf) {
1456 assert(Shuf.isSelect() && "Must have select-equivalent shuffle")((Shuf.isSelect() && "Must have select-equivalent shuffle"
) ? static_cast<void> (0) : __assert_fail ("Shuf.isSelect() && \"Must have select-equivalent shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1456, __PRETTY_FUNCTION__))
;
1457
1458 // Are we shuffling together some value and that same value after it has been
1459 // modified by a binop with a constant?
1460 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1461 Constant *C;
1462 bool Op0IsBinop;
1463 if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1464 Op0IsBinop = true;
1465 else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1466 Op0IsBinop = false;
1467 else
1468 return nullptr;
1469
1470 // The identity constant for a binop leaves a variable operand unchanged. For
1471 // a vector, this is a splat of something like 0, -1, or 1.
1472 // If there's no identity constant for this binop, we're done.
1473 auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1474 BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1475 Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1476 if (!IdC)
1477 return nullptr;
1478
1479 // Shuffle identity constants into the lanes that return the original value.
1480 // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1481 // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1482 // The existing binop constant vector remains in the same operand position.
1483 Constant *Mask = Shuf.getMask();
1484 Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1485 ConstantExpr::getShuffleVector(IdC, C, Mask);
1486
1487 bool MightCreatePoisonOrUB =
1488 Mask->containsUndefElement() &&
1489 (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1490 if (MightCreatePoisonOrUB)
1491 NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1492
1493 // shuf (bop X, C), X, M --> bop X, C'
1494 // shuf X, (bop X, C), M --> bop X, C'
1495 Value *X = Op0IsBinop ? Op1 : Op0;
1496 Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1497 NewBO->copyIRFlags(BO);
1498
1499 // An undef shuffle mask element may propagate as an undef constant element in
1500 // the new binop. That would produce poison where the original code might not.
1501 // If we already made a safe constant, then there's no danger.
1502 if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1503 NewBO->dropPoisonGeneratingFlags();
1504 return NewBO;
1505}
1506
1507/// If we have an insert of a scalar to a non-zero element of an undefined
1508/// vector and then shuffle that value, that's the same as inserting to the zero
1509/// element and shuffling. Splatting from the zero element is recognized as the
1510/// canonical form of splat.
1511static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf,
1512 InstCombiner::BuilderTy &Builder) {
1513 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1514 Constant *Mask = Shuf.getMask();
1515 Value *X;
1516 uint64_t IndexC;
1517
1518 // Match a shuffle that is a splat to a non-zero element.
1519 if (!match(Op0, m_OneUse(m_InsertElement(m_Undef(), m_Value(X),
1520 m_ConstantInt(IndexC)))) ||
1521 !match(Op1, m_Undef()) || match(Mask, m_ZeroInt()) || IndexC == 0)
1522 return nullptr;
1523
1524 // Insert into element 0 of an undef vector.
1525 UndefValue *UndefVec = UndefValue::get(Shuf.getType());
1526 Constant *Zero = Builder.getInt32(0);
1527 Value *NewIns = Builder.CreateInsertElement(UndefVec, X, Zero);
1528
1529 // Splat from element 0. Any mask element that is undefined remains undefined.
1530 // For example:
1531 // shuf (inselt undef, X, 2), undef, <2,2,undef>
1532 // --> shuf (inselt undef, X, 0), undef, <0,0,undef>
1533 unsigned NumMaskElts = Shuf.getType()->getVectorNumElements();
1534 SmallVector<Constant *, 16> NewMask(NumMaskElts, Zero);
1535 for (unsigned i = 0; i != NumMaskElts; ++i)
1536 if (isa<UndefValue>(Mask->getAggregateElement(i)))
1537 NewMask[i] = Mask->getAggregateElement(i);
1538
1539 return new ShuffleVectorInst(NewIns, UndefVec, ConstantVector::get(NewMask));
1540}
1541
1542/// Try to fold shuffles that are the equivalent of a vector select.
1543static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf,
1544 InstCombiner::BuilderTy &Builder,
1545 const DataLayout &DL) {
1546 if (!Shuf.isSelect())
1547 return nullptr;
1548
1549 // Canonicalize to choose from operand 0 first unless operand 1 is undefined.
1550 // Commuting undef to operand 0 conflicts with another canonicalization.
1551 unsigned NumElts = Shuf.getType()->getVectorNumElements();
1552 if (!isa<UndefValue>(Shuf.getOperand(1)) &&
1553 Shuf.getMaskValue(0) >= (int)NumElts) {
1554 // TODO: Can we assert that both operands of a shuffle-select are not undef
1555 // (otherwise, it would have been folded by instsimplify?
1556 Shuf.commute();
1557 return &Shuf;
1558 }
1559
1560 if (Instruction *I = foldSelectShuffleWith1Binop(Shuf))
1561 return I;
1562
1563 BinaryOperator *B0, *B1;
1564 if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1565 !match(Shuf.getOperand(1), m_BinOp(B1)))
1566 return nullptr;
1567
1568 Value *X, *Y;
1569 Constant *C0, *C1;
1570 bool ConstantsAreOp1;
1571 if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1572 match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1573 ConstantsAreOp1 = true;
1574 else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1575 match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1576 ConstantsAreOp1 = false;
1577 else
1578 return nullptr;
1579
1580 // We need matching binops to fold the lanes together.
1581 BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1582 BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1583 bool DropNSW = false;
1584 if (ConstantsAreOp1 && Opc0 != Opc1) {
1585 // TODO: We drop "nsw" if shift is converted into multiply because it may
1586 // not be correct when the shift amount is BitWidth - 1. We could examine
1587 // each vector element to determine if it is safe to keep that flag.
1588 if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1589 DropNSW = true;
1590 if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1591 assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop")((isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop"
) ? static_cast<void> (0) : __assert_fail ("isa<Constant>(AltB0.Op1) && \"Expecting constant with alt binop\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1591, __PRETTY_FUNCTION__))
;
1592 Opc0 = AltB0.Opcode;
1593 C0 = cast<Constant>(AltB0.Op1);
1594 } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1595 assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop")((isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop"
) ? static_cast<void> (0) : __assert_fail ("isa<Constant>(AltB1.Op1) && \"Expecting constant with alt binop\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1595, __PRETTY_FUNCTION__))
;
1596 Opc1 = AltB1.Opcode;
1597 C1 = cast<Constant>(AltB1.Op1);
1598 }
1599 }
1600
1601 if (Opc0 != Opc1)
1602 return nullptr;
1603
1604 // The opcodes must be the same. Use a new name to make that clear.
1605 BinaryOperator::BinaryOps BOpc = Opc0;
1606
1607 // Select the constant elements needed for the single binop.
1608 Constant *Mask = Shuf.getMask();
1609 Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1610
1611 // We are moving a binop after a shuffle. When a shuffle has an undefined
1612 // mask element, the result is undefined, but it is not poison or undefined
1613 // behavior. That is not necessarily true for div/rem/shift.
1614 bool MightCreatePoisonOrUB =
1615 Mask->containsUndefElement() &&
1616 (Instruction::isIntDivRem(BOpc) || Instruction::isShift(BOpc));
1617 if (MightCreatePoisonOrUB)
1618 NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1619
1620 Value *V;
1621 if (X == Y) {
1622 // Remove a binop and the shuffle by rearranging the constant:
1623 // shuffle (op V, C0), (op V, C1), M --> op V, C'
1624 // shuffle (op C0, V), (op C1, V), M --> op C', V
1625 V = X;
1626 } else {
1627 // If there are 2 different variable operands, we must create a new shuffle
1628 // (select) first, so check uses to ensure that we don't end up with more
1629 // instructions than we started with.
1630 if (!B0->hasOneUse() && !B1->hasOneUse())
1631 return nullptr;
1632
1633 // If we use the original shuffle mask and op1 is *variable*, we would be
1634 // putting an undef into operand 1 of div/rem/shift. This is either UB or
1635 // poison. We do not have to guard against UB when *constants* are op1
1636 // because safe constants guarantee that we do not overflow sdiv/srem (and
1637 // there's no danger for other opcodes).
1638 // TODO: To allow this case, create a new shuffle mask with no undefs.
1639 if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1640 return nullptr;
1641
1642 // Note: In general, we do not create new shuffles in InstCombine because we
1643 // do not know if a target can lower an arbitrary shuffle optimally. In this
1644 // case, the shuffle uses the existing mask, so there is no additional risk.
1645
1646 // Select the variable vectors first, then perform the binop:
1647 // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1648 // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1649 V = Builder.CreateShuffleVector(X, Y, Mask);
1650 }
1651
1652 Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1653 BinaryOperator::Create(BOpc, NewC, V);
1654
1655 // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1656 // 1. If we changed an opcode, poison conditions might have changed.
1657 // 2. If the shuffle had undef mask elements, the new binop might have undefs
1658 // where the original code did not. But if we already made a safe constant,
1659 // then there's no danger.
1660 NewBO->copyIRFlags(B0);
1661 NewBO->andIRFlags(B1);
1662 if (DropNSW)
1663 NewBO->setHasNoSignedWrap(false);
1664 if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1665 NewBO->dropPoisonGeneratingFlags();
1666 return NewBO;
1667}
1668
1669/// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1670/// narrowing (concatenating with undef and extracting back to the original
1671/// length). This allows replacing the wide select with a narrow select.
1672static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf,
1673 InstCombiner::BuilderTy &Builder) {
1674 // This must be a narrowing identity shuffle. It extracts the 1st N elements
1675 // of the 1st vector operand of a shuffle.
1676 if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1677 return nullptr;
1678
1679 // The vector being shuffled must be a vector select that we can eliminate.
1680 // TODO: The one-use requirement could be eased if X and/or Y are constants.
1681 Value *Cond, *X, *Y;
1682 if (!match(Shuf.getOperand(0),
1683 m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1684 return nullptr;
1685
1686 // We need a narrow condition value. It must be extended with undef elements
1687 // and have the same number of elements as this shuffle.
1688 unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements();
1689 Value *NarrowCond;
1690 if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(),
1691 m_Constant()))) ||
1692 NarrowCond->getType()->getVectorNumElements() != NarrowNumElts ||
1693 !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1694 return nullptr;
1695
1696 // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1697 // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1698 Value *Undef = UndefValue::get(X->getType());
1699 Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask());
1700 Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask());
1701 return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1702}
1703
1704/// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
1705static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) {
1706 Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1707 if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1708 return nullptr;
1709
1710 Value *X, *Y;
1711 Constant *Mask;
1712 if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask))))
1713 return nullptr;
1714
1715 // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
1716 // then combining may result in worse codegen.
1717 if (!Op0->hasOneUse())
1718 return nullptr;
1719
1720 // We are extracting a subvector from a shuffle. Remove excess elements from
1721 // the 1st shuffle mask to eliminate the extract.
1722 //
1723 // This transform is conservatively limited to identity extracts because we do
1724 // not allow arbitrary shuffle mask creation as a target-independent transform
1725 // (because we can't guarantee that will lower efficiently).
1726 //
1727 // If the extracting shuffle has an undef mask element, it transfers to the
1728 // new shuffle mask. Otherwise, copy the original mask element. Example:
1729 // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1730 // shuf X, Y, <C0, undef, C2, undef>
1731 unsigned NumElts = Shuf.getType()->getVectorNumElements();
1732 SmallVector<Constant *, 16> NewMask(NumElts);
1733 assert(NumElts < Mask->getType()->getVectorNumElements() &&((NumElts < Mask->getType()->getVectorNumElements() &&
"Identity with extract must have less elements than its inputs"
) ? static_cast<void> (0) : __assert_fail ("NumElts < Mask->getType()->getVectorNumElements() && \"Identity with extract must have less elements than its inputs\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1734, __PRETTY_FUNCTION__))
1734 "Identity with extract must have less elements than its inputs")((NumElts < Mask->getType()->getVectorNumElements() &&
"Identity with extract must have less elements than its inputs"
) ? static_cast<void> (0) : __assert_fail ("NumElts < Mask->getType()->getVectorNumElements() && \"Identity with extract must have less elements than its inputs\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1734, __PRETTY_FUNCTION__))
;
1735
1736 for (unsigned i = 0; i != NumElts; ++i) {
1737 Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i);
1738 Constant *MaskElt = Mask->getAggregateElement(i);
1739 NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt;
1740 }
1741 return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1742}
1743
1744/// Try to replace a shuffle with an insertelement or try to replace a shuffle
1745/// operand with the operand of an insertelement.
1746static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf) {
1747 Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
1748 SmallVector<int, 16> Mask = Shuf.getShuffleMask();
1749
1750 // The shuffle must not change vector sizes.
1751 // TODO: This restriction could be removed if the insert has only one use
1752 // (because the transform would require a new length-changing shuffle).
1753 int NumElts = Mask.size();
1754 if (NumElts != (int)(V0->getType()->getVectorNumElements()))
1755 return nullptr;
1756
1757 // This is a specialization of a fold in SimplifyDemandedVectorElts. We may
1758 // not be able to handle it there if the insertelement has >1 use.
1759 // If the shuffle has an insertelement operand but does not choose the
1760 // inserted scalar element from that value, then we can replace that shuffle
1761 // operand with the source vector of the insertelement.
1762 Value *X;
1763 uint64_t IdxC;
1764 if (match(V0, m_InsertElement(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
1765 // shuf (inselt X, ?, IdxC), ?, Mask --> shuf X, ?, Mask
1766 if (none_of(Mask, [IdxC](int MaskElt) { return MaskElt == (int)IdxC; })) {
1767 Shuf.setOperand(0, X);
1768 return &Shuf;
1769 }
1770 }
1771 if (match(V1, m_InsertElement(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
1772 // Offset the index constant by the vector width because we are checking for
1773 // accesses to the 2nd vector input of the shuffle.
1774 IdxC += NumElts;
1775 // shuf ?, (inselt X, ?, IdxC), Mask --> shuf ?, X, Mask
1776 if (none_of(Mask, [IdxC](int MaskElt) { return MaskElt == (int)IdxC; })) {
1777 Shuf.setOperand(1, X);
1778 return &Shuf;
1779 }
1780 }
1781
1782 // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
1783 auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
1784 // We need an insertelement with a constant index.
1785 if (!match(V0, m_InsertElement(m_Value(), m_Value(Scalar),
1786 m_ConstantInt(IndexC))))
1787 return false;
1788
1789 // Test the shuffle mask to see if it splices the inserted scalar into the
1790 // operand 1 vector of the shuffle.
1791 int NewInsIndex = -1;
1792 for (int i = 0; i != NumElts; ++i) {
1793 // Ignore undef mask elements.
1794 if (Mask[i] == -1)
1795 continue;
1796
1797 // The shuffle takes elements of operand 1 without lane changes.
1798 if (Mask[i] == NumElts + i)
1799 continue;
1800
1801 // The shuffle must choose the inserted scalar exactly once.
1802 if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
1803 return false;
1804
1805 // The shuffle is placing the inserted scalar into element i.
1806 NewInsIndex = i;
1807 }
1808
1809 assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?")((NewInsIndex != -1 && "Did not fold shuffle with unused operand?"
) ? static_cast<void> (0) : __assert_fail ("NewInsIndex != -1 && \"Did not fold shuffle with unused operand?\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1809, __PRETTY_FUNCTION__))
;
1810
1811 // Index is updated to the potentially translated insertion lane.
1812 IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
1813 return true;
1814 };
1815
1816 // If the shuffle is unnecessary, insert the scalar operand directly into
1817 // operand 1 of the shuffle. Example:
1818 // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
1819 Value *Scalar;
1820 ConstantInt *IndexC;
1821 if (isShufflingScalarIntoOp1(Scalar, IndexC))
1822 return InsertElementInst::Create(V1, Scalar, IndexC);
1823
1824 // Try again after commuting shuffle. Example:
1825 // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
1826 // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
1827 std::swap(V0, V1);
1828 ShuffleVectorInst::commuteShuffleMask(Mask, NumElts);
1829 if (isShufflingScalarIntoOp1(Scalar, IndexC))
1830 return InsertElementInst::Create(V1, Scalar, IndexC);
1831
1832 return nullptr;
1833}
1834
1835static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) {
1836 // Match the operands as identity with padding (also known as concatenation
1837 // with undef) shuffles of the same source type. The backend is expected to
1838 // recreate these concatenations from a shuffle of narrow operands.
1839 auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(0));
1840 auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(1));
1841 if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() ||
1842 !Shuffle1 || !Shuffle1->isIdentityWithPadding())
1843 return nullptr;
1844
1845 // We limit this transform to power-of-2 types because we expect that the
1846 // backend can convert the simplified IR patterns to identical nodes as the
1847 // original IR.
1848 // TODO: If we can verify the same behavior for arbitrary types, the
1849 // power-of-2 checks can be removed.
1850 Value *X = Shuffle0->getOperand(0);
1851 Value *Y = Shuffle1->getOperand(0);
1852 if (X->getType() != Y->getType() ||
1853 !isPowerOf2_32(Shuf.getType()->getVectorNumElements()) ||
1854 !isPowerOf2_32(Shuffle0->getType()->getVectorNumElements()) ||
1855 !isPowerOf2_32(X->getType()->getVectorNumElements()) ||
1856 isa<UndefValue>(X) || isa<UndefValue>(Y))
1857 return nullptr;
1858 assert(isa<UndefValue>(Shuffle0->getOperand(1)) &&((isa<UndefValue>(Shuffle0->getOperand(1)) &&
isa<UndefValue>(Shuffle1->getOperand(1)) &&
"Unexpected operand for identity shuffle") ? static_cast<
void> (0) : __assert_fail ("isa<UndefValue>(Shuffle0->getOperand(1)) && isa<UndefValue>(Shuffle1->getOperand(1)) && \"Unexpected operand for identity shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1860, __PRETTY_FUNCTION__))
1859 isa<UndefValue>(Shuffle1->getOperand(1)) &&((isa<UndefValue>(Shuffle0->getOperand(1)) &&
isa<UndefValue>(Shuffle1->getOperand(1)) &&
"Unexpected operand for identity shuffle") ? static_cast<
void> (0) : __assert_fail ("isa<UndefValue>(Shuffle0->getOperand(1)) && isa<UndefValue>(Shuffle1->getOperand(1)) && \"Unexpected operand for identity shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1860, __PRETTY_FUNCTION__))
1860 "Unexpected operand for identity shuffle")((isa<UndefValue>(Shuffle0->getOperand(1)) &&
isa<UndefValue>(Shuffle1->getOperand(1)) &&
"Unexpected operand for identity shuffle") ? static_cast<
void> (0) : __assert_fail ("isa<UndefValue>(Shuffle0->getOperand(1)) && isa<UndefValue>(Shuffle1->getOperand(1)) && \"Unexpected operand for identity shuffle\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1860, __PRETTY_FUNCTION__))
;
1861
1862 // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source
1863 // operands directly by adjusting the shuffle mask to account for the narrower
1864 // types:
1865 // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask'
1866 int NarrowElts = X->getType()->getVectorNumElements();
1867 int WideElts = Shuffle0->getType()->getVectorNumElements();
1868 assert(WideElts > NarrowElts && "Unexpected types for identity with padding")((WideElts > NarrowElts && "Unexpected types for identity with padding"
) ? static_cast<void> (0) : __assert_fail ("WideElts > NarrowElts && \"Unexpected types for identity with padding\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1868, __PRETTY_FUNCTION__))
;
1869
1870 Type *I32Ty = IntegerType::getInt32Ty(Shuf.getContext());
1871 SmallVector<int, 16> Mask = Shuf.getShuffleMask();
1872 SmallVector<Constant *, 16> NewMask(Mask.size(), UndefValue::get(I32Ty));
1873 for (int i = 0, e = Mask.size(); i != e; ++i) {
1874 if (Mask[i] == -1)
1875 continue;
1876
1877 // If this shuffle is choosing an undef element from 1 of the sources, that
1878 // element is undef.
1879 if (Mask[i] < WideElts) {
1880 if (Shuffle0->getMaskValue(Mask[i]) == -1)
1881 continue;
1882 } else {
1883 if (Shuffle1->getMaskValue(Mask[i] - WideElts) == -1)
1884 continue;
1885 }
1886
1887 // If this shuffle is choosing from the 1st narrow op, the mask element is
1888 // the same. If this shuffle is choosing from the 2nd narrow op, the mask
1889 // element is offset down to adjust for the narrow vector widths.
1890 if (Mask[i] < WideElts) {
1891 assert(Mask[i] < NarrowElts && "Unexpected shuffle mask")((Mask[i] < NarrowElts && "Unexpected shuffle mask"
) ? static_cast<void> (0) : __assert_fail ("Mask[i] < NarrowElts && \"Unexpected shuffle mask\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1891, __PRETTY_FUNCTION__))
;
1892 NewMask[i] = ConstantInt::get(I32Ty, Mask[i]);
1893 } else {
1894 assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask")((Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask"
) ? static_cast<void> (0) : __assert_fail ("Mask[i] < (WideElts + NarrowElts) && \"Unexpected shuffle mask\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1894, __PRETTY_FUNCTION__))
;
1895 NewMask[i] = ConstantInt::get(I32Ty, Mask[i] - (WideElts - NarrowElts));
1896 }
1897 }
1898 return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1899}
1900
1901Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1902 Value *LHS = SVI.getOperand(0);
1903 Value *RHS = SVI.getOperand(1);
1904 if (auto *V = SimplifyShuffleVectorInst(
1905 LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1906 return replaceInstUsesWith(SVI, V);
1907
1908 // shuffle x, x, mask --> shuffle x, undef, mask'
1909 unsigned VWidth = SVI.getType()->getVectorNumElements();
1910 unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1911 SmallVector<int, 16> Mask = SVI.getShuffleMask();
1912 Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
1913 if (LHS == RHS) {
1914 assert(!isa<UndefValue>(RHS) && "Shuffle with 2 undef ops not simplified?")((!isa<UndefValue>(RHS) && "Shuffle with 2 undef ops not simplified?"
) ? static_cast<void> (0) : __assert_fail ("!isa<UndefValue>(RHS) && \"Shuffle with 2 undef ops not simplified?\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 1914, __PRETTY_FUNCTION__))
;
1915 // Remap any references to RHS to use LHS.
1916 SmallVector<Constant*, 16> Elts;
1917 for (unsigned i = 0; i != VWidth; ++i) {
1918 // Propagate undef elements or force mask to LHS.
1919 if (Mask[i] < 0)
1920 Elts.push_back(UndefValue::get(Int32Ty));
1921 else
1922 Elts.push_back(ConstantInt::get(Int32Ty, Mask[i] % LHSWidth));
1923 }
1924 SVI.setOperand(0, SVI.getOperand(1));
1925 SVI.setOperand(1, UndefValue::get(RHS->getType()));
1926 SVI.setOperand(2, ConstantVector::get(Elts));
1927 return &SVI;
1928 }
1929
1930 // shuffle undef, x, mask --> shuffle x, undef, mask'
1931 if (isa<UndefValue>(LHS)) {
1932 SVI.commute();
1933 return &SVI;
1934 }
1935
1936 if (Instruction *I = canonicalizeInsertSplat(SVI, Builder))
1937 return I;
1938
1939 if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1940 return I;
1941
1942 if (Instruction *I = narrowVectorSelect(SVI, Builder))
1943 return I;
1944
1945 APInt UndefElts(VWidth, 0);
1946 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1947 if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1948 if (V != &SVI)
1949 return replaceInstUsesWith(SVI, V);
1950 return &SVI;
1951 }
1952
1953 if (Instruction *I = foldIdentityExtractShuffle(SVI))
1954 return I;
1955
1956 // These transforms have the potential to lose undef knowledge, so they are
1957 // intentionally placed after SimplifyDemandedVectorElts().
1958 if (Instruction *I = foldShuffleWithInsert(SVI))
1959 return I;
1960 if (Instruction *I = foldIdentityPaddedShuffles(SVI))
1961 return I;
1962
1963 if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
1964 Value *V = evaluateInDifferentElementOrder(LHS, Mask);
1965 return replaceInstUsesWith(SVI, V);
1966 }
1967
1968 // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1969 // a non-vector type. We can instead bitcast the original vector followed by
1970 // an extract of the desired element:
1971 //
1972 // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1973 // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1974 // %1 = bitcast <4 x i8> %sroa to i32
1975 // Becomes:
1976 // %bc = bitcast <16 x i8> %in to <4 x i32>
1977 // %ext = extractelement <4 x i32> %bc, i32 0
1978 //
1979 // If the shuffle is extracting a contiguous range of values from the input
1980 // vector then each use which is a bitcast of the extracted size can be
1981 // replaced. This will work if the vector types are compatible, and the begin
1982 // index is aligned to a value in the casted vector type. If the begin index
1983 // isn't aligned then we can shuffle the original vector (keeping the same
1984 // vector type) before extracting.
1985 //
1986 // This code will bail out if the target type is fundamentally incompatible
1987 // with vectors of the source type.
1988 //
1989 // Example of <16 x i8>, target type i32:
1990 // Index range [4,8): v-----------v Will work.
1991 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1992 // <16 x i8>: | | | | | | | | | | | | | | | | |
1993 // <4 x i32>: | | | | |
1994 // +-----------+-----------+-----------+-----------+
1995 // Index range [6,10): ^-----------^ Needs an extra shuffle.
1996 // Target type i40: ^--------------^ Won't work, bail.
1997 bool MadeChange = false;
1998 if (isShuffleExtractingFromLHS(SVI, Mask)) {
1999 Value *V = LHS;
2000 unsigned MaskElems = Mask.size();
2001 VectorType *SrcTy = cast<VectorType>(V->getType());
2002 unsigned VecBitWidth = SrcTy->getBitWidth();
2003 unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
2004 assert(SrcElemBitWidth && "vector elements must have a bitwidth")((SrcElemBitWidth && "vector elements must have a bitwidth"
) ? static_cast<void> (0) : __assert_fail ("SrcElemBitWidth && \"vector elements must have a bitwidth\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 2004, __PRETTY_FUNCTION__))
;
2005 unsigned SrcNumElems = SrcTy->getNumElements();
2006 SmallVector<BitCastInst *, 8> BCs;
2007 DenseMap<Type *, Value *> NewBCs;
2008 for (User *U : SVI.users())
2009 if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
2010 if (!BC->use_empty())
2011 // Only visit bitcasts that weren't previously handled.
2012 BCs.push_back(BC);
2013 for (BitCastInst *BC : BCs) {
2014 unsigned BegIdx = Mask.front();
2015 Type *TgtTy = BC->getDestTy();
2016 unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
2017 if (!TgtElemBitWidth)
2018 continue;
2019 unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
2020 bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
2021 bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
2022 if (!VecBitWidthsEqual)
2023 continue;
2024 if (!VectorType::isValidElementType(TgtTy))
2025 continue;
2026 VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
2027 if (!BegIsAligned) {
2028 // Shuffle the input so [0,NumElements) contains the output, and
2029 // [NumElems,SrcNumElems) is undef.
2030 SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
2031 UndefValue::get(Int32Ty));
2032 for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
2033 ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
2034 V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
2035 ConstantVector::get(ShuffleMask),
2036 SVI.getName() + ".extract");
2037 BegIdx = 0;
2038 }
2039 unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
2040 assert(SrcElemsPerTgtElem)((SrcElemsPerTgtElem) ? static_cast<void> (0) : __assert_fail
("SrcElemsPerTgtElem", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 2040, __PRETTY_FUNCTION__))
;
2041 BegIdx /= SrcElemsPerTgtElem;
2042 bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
2043 auto *NewBC =
2044 BCAlreadyExists
2045 ? NewBCs[CastSrcTy]
2046 : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
2047 if (!BCAlreadyExists)
2048 NewBCs[CastSrcTy] = NewBC;
2049 auto *Ext = Builder.CreateExtractElement(
2050 NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
2051 // The shufflevector isn't being replaced: the bitcast that used it
2052 // is. InstCombine will visit the newly-created instructions.
2053 replaceInstUsesWith(*BC, Ext);
2054 MadeChange = true;
2055 }
2056 }
2057
2058 // If the LHS is a shufflevector itself, see if we can combine it with this
2059 // one without producing an unusual shuffle.
2060 // Cases that might be simplified:
2061 // 1.
2062 // x1=shuffle(v1,v2,mask1)
2063 // x=shuffle(x1,undef,mask)
2064 // ==>
2065 // x=shuffle(v1,undef,newMask)
2066 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
2067 // 2.
2068 // x1=shuffle(v1,undef,mask1)
2069 // x=shuffle(x1,x2,mask)
2070 // where v1.size() == mask1.size()
2071 // ==>
2072 // x=shuffle(v1,x2,newMask)
2073 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
2074 // 3.
2075 // x2=shuffle(v2,undef,mask2)
2076 // x=shuffle(x1,x2,mask)
2077 // where v2.size() == mask2.size()
2078 // ==>
2079 // x=shuffle(x1,v2,newMask)
2080 // newMask[i] = (mask[i] < x1.size())
2081 // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
2082 // 4.
2083 // x1=shuffle(v1,undef,mask1)
2084 // x2=shuffle(v2,undef,mask2)
2085 // x=shuffle(x1,x2,mask)
2086 // where v1.size() == v2.size()
2087 // ==>
2088 // x=shuffle(v1,v2,newMask)
2089 // newMask[i] = (mask[i] < x1.size())
2090 // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
2091 //
2092 // Here we are really conservative:
2093 // we are absolutely afraid of producing a shuffle mask not in the input
2094 // program, because the code gen may not be smart enough to turn a merged
2095 // shuffle into two specific shuffles: it may produce worse code. As such,
2096 // we only merge two shuffles if the result is either a splat or one of the
2097 // input shuffle masks. In this case, merging the shuffles just removes
2098 // one instruction, which we know is safe. This is good for things like
2099 // turning: (splat(splat)) -> splat, or
2100 // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
2101 ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
2102 ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
2103 if (LHSShuffle)
2104 if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
2105 LHSShuffle = nullptr;
2106 if (RHSShuffle)
2107 if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
2108 RHSShuffle = nullptr;
2109 if (!LHSShuffle && !RHSShuffle)
2110 return MadeChange ? &SVI : nullptr;
2111
2112 Value* LHSOp0 = nullptr;
2113 Value* LHSOp1 = nullptr;
2114 Value* RHSOp0 = nullptr;
2115 unsigned LHSOp0Width = 0;
2116 unsigned RHSOp0Width = 0;
2117 if (LHSShuffle) {
2118 LHSOp0 = LHSShuffle->getOperand(0);
2119 LHSOp1 = LHSShuffle->getOperand(1);
2120 LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
2121 }
2122 if (RHSShuffle) {
2123 RHSOp0 = RHSShuffle->getOperand(0);
2124 RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
2125 }
2126 Value* newLHS = LHS;
2127 Value* newRHS = RHS;
2128 if (LHSShuffle) {
2129 // case 1
2130 if (isa<UndefValue>(RHS)) {
2131 newLHS = LHSOp0;
2132 newRHS = LHSOp1;
2133 }
2134 // case 2 or 4
2135 else if (LHSOp0Width == LHSWidth) {
2136 newLHS = LHSOp0;
2137 }
2138 }
2139 // case 3 or 4
2140 if (RHSShuffle && RHSOp0Width == LHSWidth) {
2141 newRHS = RHSOp0;
2142 }
2143 // case 4
2144 if (LHSOp0 == RHSOp0) {
2145 newLHS = LHSOp0;
2146 newRHS = nullptr;
2147 }
2148
2149 if (newLHS == LHS && newRHS == RHS)
2150 return MadeChange ? &SVI : nullptr;
2151
2152 SmallVector<int, 16> LHSMask;
2153 SmallVector<int, 16> RHSMask;
2154 if (newLHS != LHS)
2155 LHSMask = LHSShuffle->getShuffleMask();
2156 if (RHSShuffle && newRHS != RHS)
2157 RHSMask = RHSShuffle->getShuffleMask();
2158
2159 unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
2160 SmallVector<int, 16> newMask;
2161 bool isSplat = true;
2162 int SplatElt = -1;
2163 // Create a new mask for the new ShuffleVectorInst so that the new
2164 // ShuffleVectorInst is equivalent to the original one.
2165 for (unsigned i = 0; i < VWidth; ++i) {
2166 int eltMask;
2167 if (Mask[i] < 0) {
2168 // This element is an undef value.
2169 eltMask = -1;
2170 } else if (Mask[i] < (int)LHSWidth) {
2171 // This element is from left hand side vector operand.
2172 //
2173 // If LHS is going to be replaced (case 1, 2, or 4), calculate the
2174 // new mask value for the element.
2175 if (newLHS != LHS) {
2176 eltMask = LHSMask[Mask[i]];
2177 // If the value selected is an undef value, explicitly specify it
2178 // with a -1 mask value.
2179 if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
2180 eltMask = -1;
2181 } else
2182 eltMask = Mask[i];
2183 } else {
2184 // This element is from right hand side vector operand
2185 //
2186 // If the value selected is an undef value, explicitly specify it
2187 // with a -1 mask value. (case 1)
2188 if (isa<UndefValue>(RHS))
2189 eltMask = -1;
2190 // If RHS is going to be replaced (case 3 or 4), calculate the
2191 // new mask value for the element.
2192 else if (newRHS != RHS) {
2193 eltMask = RHSMask[Mask[i]-LHSWidth];
2194 // If the value selected is an undef value, explicitly specify it
2195 // with a -1 mask value.
2196 if (eltMask >= (int)RHSOp0Width) {
2197 assert(isa<UndefValue>(RHSShuffle->getOperand(1))((isa<UndefValue>(RHSShuffle->getOperand(1)) &&
"should have been check above") ? static_cast<void> (0
) : __assert_fail ("isa<UndefValue>(RHSShuffle->getOperand(1)) && \"should have been check above\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 2198, __PRETTY_FUNCTION__))
2198 && "should have been check above")((isa<UndefValue>(RHSShuffle->getOperand(1)) &&
"should have been check above") ? static_cast<void> (0
) : __assert_fail ("isa<UndefValue>(RHSShuffle->getOperand(1)) && \"should have been check above\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp"
, 2198, __PRETTY_FUNCTION__))
;
2199 eltMask = -1;
2200 }
2201 } else
2202 eltMask = Mask[i]-LHSWidth;
2203
2204 // If LHS's width is changed, shift the mask value accordingly.
2205 // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
2206 // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
2207 // If newRHS == newLHS, we want to remap any references from newRHS to
2208 // newLHS so that we can properly identify splats that may occur due to
2209 // obfuscation across the two vectors.
2210 if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
2211 eltMask += newLHSWidth;
2212 }
2213
2214 // Check if this could still be a splat.
2215 if (eltMask >= 0) {
2216 if (SplatElt >= 0 && SplatElt != eltMask)
2217 isSplat = false;
2218 SplatElt = eltMask;
2219 }
2220
2221 newMask.push_back(eltMask);
2222 }
2223
2224 // If the result mask is equal to one of the original shuffle masks,
2225 // or is a splat, do the replacement.
2226 if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
2227 SmallVector<Constant*, 16> Elts;
2228 for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
2229 if (newMask[i] < 0) {
2230 Elts.push_back(UndefValue::get(Int32Ty));
2231 } else {
2232 Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
2233 }
2234 }
2235 if (!newRHS)
2236 newRHS = UndefValue::get(newLHS->getType());
2237 return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
2238 }
2239
2240 return MadeChange ? &SVI : nullptr;
2241}

/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- 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//
9// This file provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16// Value *Exp = ...
17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19// m_And(m_Value(Y), m_ConstantInt(C2))))) {
20// ... Pattern is matched and variables are bound ...
21// }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/InstrTypes.h"
36#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/IntrinsicInst.h"
39#include "llvm/IR/Intrinsics.h"
40#include "llvm/IR/Operator.h"
41#include "llvm/IR/Value.h"
42#include "llvm/Support/Casting.h"
43#include <cstdint>
44
45namespace llvm {
46namespace PatternMatch {
47
48template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
49 return const_cast<Pattern &>(P).match(V);
16
Calling 'ThreeOps_match::match'
21
Returning from 'ThreeOps_match::match'
22
Returning the value 1, which participates in a condition later
50}
51
52template <typename SubPattern_t> struct OneUse_match {
53 SubPattern_t SubPattern;
54
55 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
56
57 template <typename OpTy> bool match(OpTy *V) {
58 return V->hasOneUse() && SubPattern.match(V);
59 }
60};
61
62template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
63 return SubPattern;
64}
65
66template <typename Class> struct class_match {
67 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
68};
69
70/// Match an arbitrary value and ignore it.
71inline class_match<Value> m_Value() { return class_match<Value>(); }
72
73/// Match an arbitrary binary operation and ignore it.
74inline class_match<BinaryOperator> m_BinOp() {
75 return class_match<BinaryOperator>();
76}
77
78/// Matches any compare instruction and ignore it.
79inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
80
81/// Match an arbitrary ConstantInt and ignore it.
82inline class_match<ConstantInt> m_ConstantInt() {
83 return class_match<ConstantInt>();
84}
85
86/// Match an arbitrary undef constant.
87inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
88
89/// Match an arbitrary Constant and ignore it.
90inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
91
92/// Match an arbitrary basic block value and ignore it.
93inline class_match<BasicBlock> m_BasicBlock() {
94 return class_match<BasicBlock>();
95}
96
97/// Inverting matcher
98template <typename Ty> struct match_unless {
99 Ty M;
100
101 match_unless(const Ty &Matcher) : M(Matcher) {}
102
103 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
104};
105
106/// Match if the inner matcher does *NOT* match.
107template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
108 return match_unless<Ty>(M);
109}
110
111/// Matching combinators
112template <typename LTy, typename RTy> struct match_combine_or {
113 LTy L;
114 RTy R;
115
116 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
117
118 template <typename ITy> bool match(ITy *V) {
119 if (L.match(V))
120 return true;
121 if (R.match(V))
122 return true;
123 return false;
124 }
125};
126
127template <typename LTy, typename RTy> struct match_combine_and {
128 LTy L;
129 RTy R;
130
131 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
132
133 template <typename ITy> bool match(ITy *V) {
134 if (L.match(V))
135 if (R.match(V))
136 return true;
137 return false;
138 }
139};
140
141/// Combine two pattern matchers matching L || R
142template <typename LTy, typename RTy>
143inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
144 return match_combine_or<LTy, RTy>(L, R);
145}
146
147/// Combine two pattern matchers matching L && R
148template <typename LTy, typename RTy>
149inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
150 return match_combine_and<LTy, RTy>(L, R);
151}
152
153struct apint_match {
154 const APInt *&Res;
155
156 apint_match(const APInt *&R) : Res(R) {}
157
158 template <typename ITy> bool match(ITy *V) {
159 if (auto *CI = dyn_cast<ConstantInt>(V)) {
160 Res = &CI->getValue();
161 return true;
162 }
163 if (V->getType()->isVectorTy())
164 if (const auto *C = dyn_cast<Constant>(V))
165 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) {
166 Res = &CI->getValue();
167 return true;
168 }
169 return false;
170 }
171};
172// Either constexpr if or renaming ConstantFP::getValueAPF to
173// ConstantFP::getValue is needed to do it via single template
174// function for both apint/apfloat.
175struct apfloat_match {
176 const APFloat *&Res;
177 apfloat_match(const APFloat *&R) : Res(R) {}
178 template <typename ITy> bool match(ITy *V) {
179 if (auto *CI = dyn_cast<ConstantFP>(V)) {
180 Res = &CI->getValueAPF();
181 return true;
182 }
183 if (V->getType()->isVectorTy())
184 if (const auto *C = dyn_cast<Constant>(V))
185 if (auto *CI = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) {
186 Res = &CI->getValueAPF();
187 return true;
188 }
189 return false;
190 }
191};
192
193/// Match a ConstantInt or splatted ConstantVector, binding the
194/// specified pointer to the contained APInt.
195inline apint_match m_APInt(const APInt *&Res) { return Res; }
196
197/// Match a ConstantFP or splatted ConstantVector, binding the
198/// specified pointer to the contained APFloat.
199inline apfloat_match m_APFloat(const APFloat *&Res) { return Res; }
200
201template <int64_t Val> struct constantint_match {
202 template <typename ITy> bool match(ITy *V) {
203 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
204 const APInt &CIV = CI->getValue();
205 if (Val >= 0)
206 return CIV == static_cast<uint64_t>(Val);
207 // If Val is negative, and CI is shorter than it, truncate to the right
208 // number of bits. If it is larger, then we have to sign extend. Just
209 // compare their negated values.
210 return -CIV == -Val;
211 }
212 return false;
213 }
214};
215
216/// Match a ConstantInt with a specific value.
217template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
218 return constantint_match<Val>();
219}
220
221/// This helper class is used to match scalar and vector integer constants that
222/// satisfy a specified predicate.
223/// For vector constants, undefined elements are ignored.
224template <typename Predicate> struct cst_pred_ty : public Predicate {
225 template <typename ITy> bool match(ITy *V) {
226 if (const auto *CI = dyn_cast<ConstantInt>(V))
227 return this->isValue(CI->getValue());
228 if (V->getType()->isVectorTy()) {
229 if (const auto *C = dyn_cast<Constant>(V)) {
230 if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
231 return this->isValue(CI->getValue());
232
233 // Non-splat vector constant: check each element for a match.
234 unsigned NumElts = V->getType()->getVectorNumElements();
235 assert(NumElts != 0 && "Constant vector with no elements?")((NumElts != 0 && "Constant vector with no elements?"
) ? static_cast<void> (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/IR/PatternMatch.h"
, 235, __PRETTY_FUNCTION__))
;
236 bool HasNonUndefElements = false;
237 for (unsigned i = 0; i != NumElts; ++i) {
238 Constant *Elt = C->getAggregateElement(i);
239 if (!Elt)
240 return false;
241 if (isa<UndefValue>(Elt))
242 continue;
243 auto *CI = dyn_cast<ConstantInt>(Elt);
244 if (!CI || !this->isValue(CI->getValue()))
245 return false;
246 HasNonUndefElements = true;
247 }
248 return HasNonUndefElements;
249 }
250 }
251 return false;
252 }
253};
254
255/// This helper class is used to match scalar and vector constants that
256/// satisfy a specified predicate, and bind them to an APInt.
257template <typename Predicate> struct api_pred_ty : public Predicate {
258 const APInt *&Res;
259
260 api_pred_ty(const APInt *&R) : Res(R) {}
261
262 template <typename ITy> bool match(ITy *V) {
263 if (const auto *CI = dyn_cast<ConstantInt>(V))
264 if (this->isValue(CI->getValue())) {
265 Res = &CI->getValue();
266 return true;
267 }
268 if (V->getType()->isVectorTy())
269 if (const auto *C = dyn_cast<Constant>(V))
270 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
271 if (this->isValue(CI->getValue())) {
272 Res = &CI->getValue();
273 return true;
274 }
275
276 return false;
277 }
278};
279
280/// This helper class is used to match scalar and vector floating-point
281/// constants that satisfy a specified predicate.
282/// For vector constants, undefined elements are ignored.
283template <typename Predicate> struct cstfp_pred_ty : public Predicate {
284 template <typename ITy> bool match(ITy *V) {
285 if (const auto *CF = dyn_cast<ConstantFP>(V))
286 return this->isValue(CF->getValueAPF());
287 if (V->getType()->isVectorTy()) {
288 if (const auto *C = dyn_cast<Constant>(V)) {
289 if (const auto *CF = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
290 return this->isValue(CF->getValueAPF());
291
292 // Non-splat vector constant: check each element for a match.
293 unsigned NumElts = V->getType()->getVectorNumElements();
294 assert(NumElts != 0 && "Constant vector with no elements?")((NumElts != 0 && "Constant vector with no elements?"
) ? static_cast<void> (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/IR/PatternMatch.h"
, 294, __PRETTY_FUNCTION__))
;
295 bool HasNonUndefElements = false;
296 for (unsigned i = 0; i != NumElts; ++i) {
297 Constant *Elt = C->getAggregateElement(i);
298 if (!Elt)
299 return false;
300 if (isa<UndefValue>(Elt))
301 continue;
302 auto *CF = dyn_cast<ConstantFP>(Elt);
303 if (!CF || !this->isValue(CF->getValueAPF()))
304 return false;
305 HasNonUndefElements = true;
306 }
307 return HasNonUndefElements;
308 }
309 }
310 return false;
311 }
312};
313
314///////////////////////////////////////////////////////////////////////////////
315//
316// Encapsulate constant value queries for use in templated predicate matchers.
317// This allows checking if constants match using compound predicates and works
318// with vector constants, possibly with relaxed constraints. For example, ignore
319// undef values.
320//
321///////////////////////////////////////////////////////////////////////////////
322
323struct is_any_apint {
324 bool isValue(const APInt &C) { return true; }
325};
326/// Match an integer or vector with any integral constant.
327/// For vectors, this includes constants with undefined elements.
328inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
329 return cst_pred_ty<is_any_apint>();
330}
331
332struct is_all_ones {
333 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
334};
335/// Match an integer or vector with all bits set.
336/// For vectors, this includes constants with undefined elements.
337inline cst_pred_ty<is_all_ones> m_AllOnes() {
338 return cst_pred_ty<is_all_ones>();
339}
340
341struct is_maxsignedvalue {
342 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
343};
344/// Match an integer or vector with values having all bits except for the high
345/// bit set (0x7f...).
346/// For vectors, this includes constants with undefined elements.
347inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
348 return cst_pred_ty<is_maxsignedvalue>();
349}
350inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
351 return V;
352}
353
354struct is_negative {
355 bool isValue(const APInt &C) { return C.isNegative(); }
356};
357/// Match an integer or vector of negative values.
358/// For vectors, this includes constants with undefined elements.
359inline cst_pred_ty<is_negative> m_Negative() {
360 return cst_pred_ty<is_negative>();
361}
362inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
363 return V;
364}
365
366struct is_nonnegative {
367 bool isValue(const APInt &C) { return C.isNonNegative(); }
368};
369/// Match an integer or vector of non-negative values.
370/// For vectors, this includes constants with undefined elements.
371inline cst_pred_ty<is_nonnegative> m_NonNegative() {
372 return cst_pred_ty<is_nonnegative>();
373}
374inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
375 return V;
376}
377
378struct is_strictlypositive {
379 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
380};
381/// Match an integer or vector of strictly positive values.
382/// For vectors, this includes constants with undefined elements.
383inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
384 return cst_pred_ty<is_strictlypositive>();
385}
386inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
387 return V;
388}
389
390struct is_nonpositive {
391 bool isValue(const APInt &C) { return C.isNonPositive(); }
392};
393/// Match an integer or vector of non-positive values.
394/// For vectors, this includes constants with undefined elements.
395inline cst_pred_ty<is_nonpositive> m_NonPositive() {
396 return cst_pred_ty<is_nonpositive>();
397}
398inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
399
400struct is_one {
401 bool isValue(const APInt &C) { return C.isOneValue(); }
402};
403/// Match an integer 1 or a vector with all elements equal to 1.
404/// For vectors, this includes constants with undefined elements.
405inline cst_pred_ty<is_one> m_One() {
406 return cst_pred_ty<is_one>();
407}
408
409struct is_zero_int {
410 bool isValue(const APInt &C) { return C.isNullValue(); }
411};
412/// Match an integer 0 or a vector with all elements equal to 0.
413/// For vectors, this includes constants with undefined elements.
414inline cst_pred_ty<is_zero_int> m_ZeroInt() {
415 return cst_pred_ty<is_zero_int>();
416}
417
418struct is_zero {
419 template <typename ITy> bool match(ITy *V) {
420 auto *C = dyn_cast<Constant>(V);
421 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
422 }
423};
424/// Match any null constant or a vector with all elements equal to 0.
425/// For vectors, this includes constants with undefined elements.
426inline is_zero m_Zero() {
427 return is_zero();
428}
429
430struct is_power2 {
431 bool isValue(const APInt &C) { return C.isPowerOf2(); }
432};
433/// Match an integer or vector power-of-2.
434/// For vectors, this includes constants with undefined elements.
435inline cst_pred_ty<is_power2> m_Power2() {
436 return cst_pred_ty<is_power2>();
437}
438inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
439 return V;
440}
441
442struct is_negated_power2 {
443 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
444};
445/// Match a integer or vector negated power-of-2.
446/// For vectors, this includes constants with undefined elements.
447inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
448 return cst_pred_ty<is_negated_power2>();
449}
450inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
451 return V;
452}
453
454struct is_power2_or_zero {
455 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
456};
457/// Match an integer or vector of 0 or power-of-2 values.
458/// For vectors, this includes constants with undefined elements.
459inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
460 return cst_pred_ty<is_power2_or_zero>();
461}
462inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
463 return V;
464}
465
466struct is_sign_mask {
467 bool isValue(const APInt &C) { return C.isSignMask(); }
468};
469/// Match an integer or vector with only the sign bit(s) set.
470/// For vectors, this includes constants with undefined elements.
471inline cst_pred_ty<is_sign_mask> m_SignMask() {
472 return cst_pred_ty<is_sign_mask>();
473}
474
475struct is_lowbit_mask {
476 bool isValue(const APInt &C) { return C.isMask(); }
477};
478/// Match an integer or vector with only the low bit(s) set.
479/// For vectors, this includes constants with undefined elements.
480inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
481 return cst_pred_ty<is_lowbit_mask>();
482}
483
484struct icmp_pred_with_threshold {
485 ICmpInst::Predicate Pred;
486 const APInt *Thr;
487 bool isValue(const APInt &C) {
488 switch (Pred) {
489 case ICmpInst::Predicate::ICMP_EQ:
490 return C.eq(*Thr);
491 case ICmpInst::Predicate::ICMP_NE:
492 return C.ne(*Thr);
493 case ICmpInst::Predicate::ICMP_UGT:
494 return C.ugt(*Thr);
495 case ICmpInst::Predicate::ICMP_UGE:
496 return C.uge(*Thr);
497 case ICmpInst::Predicate::ICMP_ULT:
498 return C.ult(*Thr);
499 case ICmpInst::Predicate::ICMP_ULE:
500 return C.ule(*Thr);
501 case ICmpInst::Predicate::ICMP_SGT:
502 return C.sgt(*Thr);
503 case ICmpInst::Predicate::ICMP_SGE:
504 return C.sge(*Thr);
505 case ICmpInst::Predicate::ICMP_SLT:
506 return C.slt(*Thr);
507 case ICmpInst::Predicate::ICMP_SLE:
508 return C.sle(*Thr);
509 default:
510 llvm_unreachable("Unhandled ICmp predicate")::llvm::llvm_unreachable_internal("Unhandled ICmp predicate",
"/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/include/llvm/IR/PatternMatch.h"
, 510)
;
511 }
512 }
513};
514/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
515/// to Threshold. For vectors, this includes constants with undefined elements.
516inline cst_pred_ty<icmp_pred_with_threshold>
517m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
518 cst_pred_ty<icmp_pred_with_threshold> P;
519 P.Pred = Predicate;
520 P.Thr = &Threshold;
521 return P;
522}
523
524struct is_nan {
525 bool isValue(const APFloat &C) { return C.isNaN(); }
526};
527/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
528/// For vectors, this includes constants with undefined elements.
529inline cstfp_pred_ty<is_nan> m_NaN() {
530 return cstfp_pred_ty<is_nan>();
531}
532
533struct is_any_zero_fp {
534 bool isValue(const APFloat &C) { return C.isZero(); }
535};
536/// Match a floating-point negative zero or positive zero.
537/// For vectors, this includes constants with undefined elements.
538inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
539 return cstfp_pred_ty<is_any_zero_fp>();
540}
541
542struct is_pos_zero_fp {
543 bool isValue(const APFloat &C) { return C.isPosZero(); }
544};
545/// Match a floating-point positive zero.
546/// For vectors, this includes constants with undefined elements.
547inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
548 return cstfp_pred_ty<is_pos_zero_fp>();
549}
550
551struct is_neg_zero_fp {
552 bool isValue(const APFloat &C) { return C.isNegZero(); }
553};
554/// Match a floating-point negative zero.
555/// For vectors, this includes constants with undefined elements.
556inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
557 return cstfp_pred_ty<is_neg_zero_fp>();
558}
559
560///////////////////////////////////////////////////////////////////////////////
561
562template <typename Class> struct bind_ty {
563 Class *&VR;
564
565 bind_ty(Class *&V) : VR(V) {}
566
567 template <typename ITy> bool match(ITy *V) {
568 if (auto *CV = dyn_cast<Class>(V)) {
569 VR = CV;
570 return true;
571 }
572 return false;
573 }
574};
575
576/// Match a value, capturing it if we match.
577inline bind_ty<Value> m_Value(Value *&V) { return V; }
578inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
579
580/// Match an instruction, capturing it if we match.
581inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
582/// Match a binary operator, capturing it if we match.
583inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
584/// Match a with overflow intrinsic, capturing it if we match.
585inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
586
587/// Match a ConstantInt, capturing the value if we match.
588inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
589
590/// Match a Constant, capturing the value if we match.
591inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
592
593/// Match a ConstantFP, capturing the value if we match.
594inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
595
596/// Match a basic block value, capturing it if we match.
597inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
598inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
599 return V;
600}
601
602/// Match a specified Value*.
603struct specificval_ty {
604 const Value *Val;
605
606 specificval_ty(const Value *V) : Val(V) {}
607
608 template <typename ITy> bool match(ITy *V) { return V == Val; }
609};
610
611/// Match if we have a specific specified value.
612inline specificval_ty m_Specific(const Value *V) { return V; }
613
614/// Stores a reference to the Value *, not the Value * itself,
615/// thus can be used in commutative matchers.
616template <typename Class> struct deferredval_ty {
617 Class *const &Val;
618
619 deferredval_ty(Class *const &V) : Val(V) {}
620
621 template <typename ITy> bool match(ITy *const V) { return V == Val; }
622};
623
624/// A commutative-friendly version of m_Specific().
625inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
626inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
627 return V;
628}
629
630/// Match a specified floating point value or vector of all elements of
631/// that value.
632struct specific_fpval {
633 double Val;
634
635 specific_fpval(double V) : Val(V) {}
636
637 template <typename ITy> bool match(ITy *V) {
638 if (const auto *CFP = dyn_cast<ConstantFP>(V))
639 return CFP->isExactlyValue(Val);
640 if (V->getType()->isVectorTy())
641 if (const auto *C = dyn_cast<Constant>(V))
642 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
643 return CFP->isExactlyValue(Val);
644 return false;
645 }
646};
647
648/// Match a specific floating point value or vector with all elements
649/// equal to the value.
650inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
651
652/// Match a float 1.0 or vector with all elements equal to 1.0.
653inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
654
655struct bind_const_intval_ty {
656 uint64_t &VR;
657
658 bind_const_intval_ty(uint64_t &V) : VR(V) {}
659
660 template <typename ITy> bool match(ITy *V) {
661 if (const auto *CV = dyn_cast<ConstantInt>(V))
662 if (CV->getValue().ule(UINT64_MAX(18446744073709551615UL))) {
663 VR = CV->getZExtValue();
664 return true;
665 }
666 return false;
667 }
668};
669
670/// Match a specified integer value or vector of all elements of that
671/// value.
672struct specific_intval {
673 APInt Val;
674
675 specific_intval(APInt V) : Val(std::move(V)) {}
676
677 template <typename ITy> bool match(ITy *V) {
678 const auto *CI = dyn_cast<ConstantInt>(V);
679 if (!CI && V->getType()->isVectorTy())
680 if (const auto *C = dyn_cast<Constant>(V))
681 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
682
683 return CI && APInt::isSameValue(CI->getValue(), Val);
684 }
685};
686
687/// Match a specific integer value or vector with all elements equal to
688/// the value.
689inline specific_intval m_SpecificInt(APInt V) {
690 return specific_intval(std::move(V));
691}
692
693inline specific_intval m_SpecificInt(uint64_t V) {
694 return m_SpecificInt(APInt(64, V));
695}
696
697/// Match a ConstantInt and bind to its value. This does not match
698/// ConstantInts wider than 64-bits.
699inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
700
701/// Match a specified basic block value.
702struct specific_bbval {
703 BasicBlock *Val;
704
705 specific_bbval(BasicBlock *Val) : Val(Val) {}
706
707 template <typename ITy> bool match(ITy *V) {
708 const auto *BB = dyn_cast<BasicBlock>(V);
709 return BB && BB == Val;
710 }
711};
712
713/// Match a specific basic block value.
714inline specific_bbval m_SpecificBB(BasicBlock *BB) {
715 return specific_bbval(BB);
716}
717
718/// A commutative-friendly version of m_Specific().
719inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
720 return BB;
721}
722inline deferredval_ty<const BasicBlock>
723m_Deferred(const BasicBlock *const &BB) {
724 return BB;
725}
726
727//===----------------------------------------------------------------------===//
728// Matcher for any binary operator.
729//
730template <typename LHS_t, typename RHS_t, bool Commutable = false>
731struct AnyBinaryOp_match {
732 LHS_t L;
733 RHS_t R;
734
735 // The evaluation order is always stable, regardless of Commutability.
736 // The LHS is always matched first.
737 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
738
739 template <typename OpTy> bool match(OpTy *V) {
740 if (auto *I = dyn_cast<BinaryOperator>(V))
741 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
742 (Commutable && L.match(I->getOperand(1)) &&
743 R.match(I->getOperand(0)));
744 return false;
745 }
746};
747
748template <typename LHS, typename RHS>
749inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
750 return AnyBinaryOp_match<LHS, RHS>(L, R);
751}
752
753//===----------------------------------------------------------------------===//
754// Matchers for specific binary operators.
755//
756
757template <typename LHS_t, typename RHS_t, unsigned Opcode,
758 bool Commutable = false>
759struct BinaryOp_match {
760 LHS_t L;
761 RHS_t R;
762
763 // The evaluation order is always stable, regardless of Commutability.
764 // The LHS is always matched first.
765 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
766
767 template <typename OpTy> bool match(OpTy *V) {
768 if (V->getValueID() == Value::InstructionVal + Opcode) {
769 auto *I = cast<BinaryOperator>(V);
770 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
771 (Commutable && L.match(I->getOperand(1)) &&
772 R.match(I->getOperand(0)));
773 }
774 if (auto *CE = dyn_cast<ConstantExpr>(V))
775 return CE->getOpcode() == Opcode &&
776 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
777 (Commutable && L.match(CE->getOperand(1)) &&
778 R.match(CE->getOperand(0))));
779 return false;
780 }
781};
782
783template <typename LHS, typename RHS>
784inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
785 const RHS &R) {
786 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
787}
788
789template <typename LHS, typename RHS>
790inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
791 const RHS &R) {
792 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
793}
794
795template <typename LHS, typename RHS>
796inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
797 const RHS &R) {
798 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
799}
800
801template <typename LHS, typename RHS>
802inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
803 const RHS &R) {
804 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
805}
806
807template <typename Op_t> struct FNeg_match {
808 Op_t X;
809
810 FNeg_match(const Op_t &Op) : X(Op) {}
811 template <typename OpTy> bool match(OpTy *V) {
812 auto *FPMO = dyn_cast<FPMathOperator>(V);
813 if (!FPMO) return false;
814
815 if (FPMO->getOpcode() == Instruction::FNeg)
816 return X.match(FPMO->getOperand(0));
817
818 if (FPMO->getOpcode() == Instruction::FSub) {
819 if (FPMO->hasNoSignedZeros()) {
820 // With 'nsz', any zero goes.
821 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
822 return false;
823 } else {
824 // Without 'nsz', we need fsub -0.0, X exactly.
825 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
826 return false;
827 }
828
829 return X.match(FPMO->getOperand(1));
830 }
831
832 return false;
833 }
834};
835
836/// Match 'fneg X' as 'fsub -0.0, X'.
837template <typename OpTy>
838inline FNeg_match<OpTy>
839m_FNeg(const OpTy &X) {
840 return FNeg_match<OpTy>(X);
841}
842
843/// Match 'fneg X' as 'fsub +-0.0, X'.
844template <typename RHS>
845inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
846m_FNegNSZ(const RHS &X) {
847 return m_FSub(m_AnyZeroFP(), X);
848}
849
850template <typename LHS, typename RHS>
851inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
852 const RHS &R) {
853 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
854}
855
856template <typename LHS, typename RHS>
857inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
858 const RHS &R) {
859 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
860}
861
862template <typename LHS, typename RHS>
863inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
864 const RHS &R) {
865 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
866}
867
868template <typename LHS, typename RHS>
869inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
870 const RHS &R) {
871 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
872}
873
874template <typename LHS, typename RHS>
875inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
876 const RHS &R) {
877 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
878}
879
880template <typename LHS, typename RHS>
881inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
882 const RHS &R) {
883 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
884}
885
886template <typename LHS, typename RHS>
887inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
888 const RHS &R) {
889 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
890}
891
892template <typename LHS, typename RHS>
893inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
894 const RHS &R) {
895 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
896}
897
898template <typename LHS, typename RHS>
899inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
900 const RHS &R) {
901 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
902}
903
904template <typename LHS, typename RHS>
905inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
906 const RHS &R) {
907 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
908}
909
910template <typename LHS, typename RHS>
911inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
912 const RHS &R) {
913 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
914}
915
916template <typename LHS, typename RHS>
917inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
918 const RHS &R) {
919 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
920}
921
922template <typename LHS, typename RHS>
923inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
924 const RHS &R) {
925 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
926}
927
928template <typename LHS, typename RHS>
929inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
930 const RHS &R) {
931 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
932}
933
934template <typename LHS_t, typename RHS_t, unsigned Opcode,
935 unsigned WrapFlags = 0>
936struct OverflowingBinaryOp_match {
937 LHS_t L;
938 RHS_t R;
939
940 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
941 : L(LHS), R(RHS) {}
942
943 template <typename OpTy> bool match(OpTy *V) {
944 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
945 if (Op->getOpcode() != Opcode)
946 return false;
947 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap &&
948 !Op->hasNoUnsignedWrap())
949 return false;
950 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
951 !Op->hasNoSignedWrap())
952 return false;
953 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
954 }
955 return false;
956 }
957};
958
959template <typename LHS, typename RHS>
960inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
961 OverflowingBinaryOperator::NoSignedWrap>
962m_NSWAdd(const LHS &L, const RHS &R) {
963 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
964 OverflowingBinaryOperator::NoSignedWrap>(
965 L, R);
966}
967template <typename LHS, typename RHS>
968inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
969 OverflowingBinaryOperator::NoSignedWrap>
970m_NSWSub(const LHS &L, const RHS &R) {
971 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
972 OverflowingBinaryOperator::NoSignedWrap>(
973 L, R);
974}
975template <typename LHS, typename RHS>
976inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
977 OverflowingBinaryOperator::NoSignedWrap>
978m_NSWMul(const LHS &L, const RHS &R) {
979 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
980 OverflowingBinaryOperator::NoSignedWrap>(
981 L, R);
982}
983template <typename LHS, typename RHS>
984inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
985 OverflowingBinaryOperator::NoSignedWrap>
986m_NSWShl(const LHS &L, const RHS &R) {
987 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
988 OverflowingBinaryOperator::NoSignedWrap>(
989 L, R);
990}
991
992template <typename LHS, typename RHS>
993inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
994 OverflowingBinaryOperator::NoUnsignedWrap>
995m_NUWAdd(const LHS &L, const RHS &R) {
996 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
997 OverflowingBinaryOperator::NoUnsignedWrap>(
998 L, R);
999}
1000template <typename LHS, typename RHS>
1001inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1002 OverflowingBinaryOperator::NoUnsignedWrap>
1003m_NUWSub(const LHS &L, const RHS &R) {
1004 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1005 OverflowingBinaryOperator::NoUnsignedWrap>(
1006 L, R);
1007}
1008template <typename LHS, typename RHS>
1009inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1010 OverflowingBinaryOperator::NoUnsignedWrap>
1011m_NUWMul(const LHS &L, const RHS &R) {
1012 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1013 OverflowingBinaryOperator::NoUnsignedWrap>(
1014 L, R);
1015}
1016template <typename LHS, typename RHS>
1017inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1018 OverflowingBinaryOperator::NoUnsignedWrap>
1019m_NUWShl(const LHS &L, const RHS &R) {
1020 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1021 OverflowingBinaryOperator::NoUnsignedWrap>(
1022 L, R);
1023}
1024
1025//===----------------------------------------------------------------------===//
1026// Class that matches a group of binary opcodes.
1027//
1028template <typename LHS_t, typename RHS_t, typename Predicate>
1029struct BinOpPred_match : Predicate {
1030 LHS_t L;
1031 RHS_t R;
1032
1033 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1034
1035 template <typename OpTy> bool match(OpTy *V) {
1036 if (auto *I = dyn_cast<Instruction>(V))
1037 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1038 R.match(I->getOperand(1));
1039 if (auto *CE = dyn_cast<ConstantExpr>(V))
1040 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1041 R.match(CE->getOperand(1));
1042 return false;
1043 }
1044};
1045
1046struct is_shift_op {
1047 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1048};
1049
1050struct is_right_shift_op {
1051 bool isOpType(unsigned Opcode) {
1052 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1053 }
1054};
1055
1056struct is_logical_shift_op {
1057 bool isOpType(unsigned Opcode) {
1058 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1059 }
1060};
1061
1062struct is_bitwiselogic_op {
1063 bool isOpType(unsigned Opcode) {
1064 return Instruction::isBitwiseLogicOp(Opcode);
1065 }
1066};
1067
1068struct is_idiv_op {
1069 bool isOpType(unsigned Opcode) {
1070 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1071 }
1072};
1073
1074struct is_irem_op {
1075 bool isOpType(unsigned Opcode) {
1076 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1077 }
1078};
1079
1080/// Matches shift operations.
1081template <typename LHS, typename RHS>
1082inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1083 const RHS &R) {
1084 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1085}
1086
1087/// Matches logical shift operations.
1088template <typename LHS, typename RHS>
1089inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1090 const RHS &R) {
1091 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1092}
1093
1094/// Matches logical shift operations.
1095template <typename LHS, typename RHS>
1096inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
1097m_LogicalShift(const LHS &L, const RHS &R) {
1098 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1099}
1100
1101/// Matches bitwise logic operations.
1102template <typename LHS, typename RHS>
1103inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
1104m_BitwiseLogic(const LHS &L, const RHS &R) {
1105 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1106}
1107
1108/// Matches integer division operations.
1109template <typename LHS, typename RHS>
1110inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1111 const RHS &R) {
1112 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1113}
1114
1115/// Matches integer remainder operations.
1116template <typename LHS, typename RHS>
1117inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1118 const RHS &R) {
1119 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1120}
1121
1122//===----------------------------------------------------------------------===//
1123// Class that matches exact binary ops.
1124//
1125template <typename SubPattern_t> struct Exact_match {
1126 SubPattern_t SubPattern;
1127
1128 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1129
1130 template <typename OpTy> bool match(OpTy *V) {
1131 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1132 return PEO->isExact() && SubPattern.match(V);
1133 return false;
1134 }
1135};
1136
1137template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1138 return SubPattern;
1139}
1140
1141//===----------------------------------------------------------------------===//
1142// Matchers for CmpInst classes
1143//
1144
1145template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1146 bool Commutable = false>
1147struct CmpClass_match {
1148 PredicateTy &Predicate;
1149 LHS_t L;
1150 RHS_t R;
1151
1152 // The evaluation order is always stable, regardless of Commutability.
1153 // The LHS is always matched first.
1154 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1155 : Predicate(Pred), L(LHS), R(RHS) {}
1156
1157 template <typename OpTy> bool match(OpTy *V) {
1158 if (auto *I = dyn_cast<Class>(V))
1159 if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
1160 (Commutable && L.match(I->getOperand(1)) &&
1161 R.match(I->getOperand(0)))) {
1162 Predicate = I->getPredicate();
1163 return true;
1164 }
1165 return false;
1166 }
1167};
1168
1169template <typename LHS, typename RHS>
1170inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
1171m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1172 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1173}
1174
1175template <typename LHS, typename RHS>
1176inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
1177m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1178 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1179}
1180
1181template <typename LHS, typename RHS>
1182inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
1183m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1184 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1185}
1186
1187//===----------------------------------------------------------------------===//
1188// Matchers for instructions with a given opcode and number of operands.
1189//
1190
1191/// Matches instructions with Opcode and three operands.
1192template <typename T0, unsigned Opcode> struct OneOps_match {
1193 T0 Op1;
1194
1195 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1196
1197 template <typename OpTy> bool match(OpTy *V) {
1198 if (V->getValueID() == Value::InstructionVal + Opcode) {
1199 auto *I = cast<Instruction>(V);
1200 return Op1.match(I->getOperand(0));
1201 }
1202 return false;
1203 }
1204};
1205
1206/// Matches instructions with Opcode and three operands.
1207template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1208 T0 Op1;
1209 T1 Op2;
1210
1211 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1212
1213 template <typename OpTy> bool match(OpTy *V) {
1214 if (V->getValueID() == Value::InstructionVal + Opcode) {
1215 auto *I = cast<Instruction>(V);
1216 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1217 }
1218 return false;
1219 }
1220};
1221
1222/// Matches instructions with Opcode and three operands.
1223template <typename T0, typename T1, typename T2, unsigned Opcode>
1224struct ThreeOps_match {
1225 T0 Op1;
1226 T1 Op2;
1227 T2 Op3;
1228
1229 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1230 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1231
1232 template <typename OpTy> bool match(OpTy *V) {
1233 if (V->getValueID() == Value::InstructionVal + Opcode) {
17
Assuming the condition is true
18
Taking true branch
1234 auto *I = cast<Instruction>(V);
19
'V' is a 'Instruction'
1235 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
20
Returning the value 1, which participates in a condition later
1236 Op3.match(I->getOperand(2));
1237 }
1238 return false;
1239 }
1240};
1241
1242/// Matches SelectInst.
1243template <typename Cond, typename LHS, typename RHS>
1244inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1245m_Select(const Cond &C, const LHS &L, const RHS &R) {
1246 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1247}
1248
1249/// This matches a select of two constants, e.g.:
1250/// m_SelectCst<-1, 0>(m_Value(V))
1251template <int64_t L, int64_t R, typename Cond>
1252inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1253 Instruction::Select>
1254m_SelectCst(const Cond &C) {
1255 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1256}
1257
1258/// Matches FreezeInst.
1259template <typename OpTy>
1260inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1261 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1262}
1263
1264/// Matches InsertElementInst.
1265template <typename Val_t, typename Elt_t, typename Idx_t>
1266inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1267m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1268 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1269 Val, Elt, Idx);
1270}
1271
1272/// Matches ExtractElementInst.
1273template <typename Val_t, typename Idx_t>
1274inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1275m_ExtractElement(const Val_t &Val, const Idx_t &Idx) {
1276 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1277}
1278
1279/// Matches ShuffleVectorInst.
1280template <typename V1_t, typename V2_t, typename Mask_t>
1281inline ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>
1282m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m) {
1283 return ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>(v1, v2,
1284 m);
1285}
1286
1287/// Matches LoadInst.
1288template <typename OpTy>
1289inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1290 return OneOps_match<OpTy, Instruction::Load>(Op);
1291}
1292
1293/// Matches StoreInst.
1294template <typename ValueOpTy, typename PointerOpTy>
1295inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1296m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1297 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1298 PointerOp);
1299}
1300
1301//===----------------------------------------------------------------------===//
1302// Matchers for CastInst classes
1303//
1304
1305template <typename Op_t, unsigned Opcode> struct CastClass_match {
1306 Op_t Op;
1307
1308 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1309
1310 template <typename OpTy> bool match(OpTy *V) {
1311 if (auto *O = dyn_cast<Operator>(V))
1312 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1313 return false;
1314 }
1315};
1316
1317/// Matches BitCast.
1318template <typename OpTy>
1319inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1320 return CastClass_match<OpTy, Instruction::BitCast>(Op);
1321}
1322
1323/// Matches PtrToInt.
1324template <typename OpTy>
1325inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1326 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1327}
1328
1329/// Matches Trunc.
1330template <typename OpTy>
1331inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1332 return CastClass_match<OpTy, Instruction::Trunc>(Op);
1333}
1334
1335template <typename OpTy>
1336inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
1337m_TruncOrSelf(const OpTy &Op) {
1338 return m_CombineOr(m_Trunc(Op), Op);
1339}
1340
1341/// Matches SExt.
1342template <typename OpTy>
1343inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1344 return CastClass_match<OpTy, Instruction::SExt>(Op);
1345}
1346
1347/// Matches ZExt.
1348template <typename OpTy>
1349inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1350 return CastClass_match<OpTy, Instruction::ZExt>(Op);
1351}
1352
1353template <typename OpTy>
1354inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
1355m_ZExtOrSelf(const OpTy &Op) {
1356 return m_CombineOr(m_ZExt(Op), Op);
1357}
1358
1359template <typename OpTy>
1360inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
1361m_SExtOrSelf(const OpTy &Op) {
1362 return m_CombineOr(m_SExt(Op), Op);
1363}
1364
1365template <typename OpTy>
1366inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1367 CastClass_match<OpTy, Instruction::SExt>>
1368m_ZExtOrSExt(const OpTy &Op) {
1369 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1370}
1371
1372template <typename OpTy>
1373inline match_combine_or<
1374 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1375 CastClass_match<OpTy, Instruction::SExt>>,
1376 OpTy>
1377m_ZExtOrSExtOrSelf(const OpTy &Op) {
1378 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1379}
1380
1381/// Matches UIToFP.
1382template <typename OpTy>
1383inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1384 return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1385}
1386
1387/// Matches SIToFP.
1388template <typename OpTy>
1389inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1390 return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1391}
1392
1393/// Matches FPTrunc
1394template <typename OpTy>
1395inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1396 return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1397}
1398
1399/// Matches FPExt
1400template <typename OpTy>
1401inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1402 return CastClass_match<OpTy, Instruction::FPExt>(Op);
1403}
1404
1405//===----------------------------------------------------------------------===//
1406// Matchers for control flow.
1407//
1408
1409struct br_match {
1410 BasicBlock *&Succ;
1411
1412 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1413
1414 template <typename OpTy> bool match(OpTy *V) {
1415 if (auto *BI = dyn_cast<BranchInst>(V))
1416 if (BI->isUnconditional()) {
1417 Succ = BI->getSuccessor(0);
1418 return true;
1419 }
1420 return false;
1421 }
1422};
1423
1424inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1425
1426template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1427struct brc_match {
1428 Cond_t Cond;
1429 TrueBlock_t T;
1430 FalseBlock_t F;
1431
1432 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1433 : Cond(C), T(t), F(f) {}
1434
1435 template <typename OpTy> bool match(OpTy *V) {
1436 if (auto *BI = dyn_cast<BranchInst>(V))
1437 if (BI->isConditional() && Cond.match(BI->getCondition()))
1438 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1439 return false;
1440 }
1441};
1442
1443template <typename Cond_t>
1444inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
1445m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1446 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1447 C, m_BasicBlock(T), m_BasicBlock(F));
1448}
1449
1450template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1451inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
1452m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1453 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1454}
1455
1456//===----------------------------------------------------------------------===//
1457// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1458//
1459
1460template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1461 bool Commutable = false>
1462struct MaxMin_match {
1463 LHS_t L;
1464 RHS_t R;
1465
1466 // The evaluation order is always stable, regardless of Commutability.
1467 // The LHS is always matched first.
1468 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1469
1470 template <typename OpTy> bool match(OpTy *V) {
1471 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1472 auto *SI = dyn_cast<SelectInst>(V);
1473 if (!SI)
1474 return false;
1475 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1476 if (!Cmp)
1477 return false;
1478 // At this point we have a select conditioned on a comparison. Check that
1479 // it is the values returned by the select that are being compared.
1480 Value *TrueVal = SI->getTrueValue();
1481 Value *FalseVal = SI->getFalseValue();
1482 Value *LHS = Cmp->getOperand(0);
1483 Value *RHS = Cmp->getOperand(1);
1484 if ((TrueVal != LHS || FalseVal != RHS) &&
1485 (TrueVal != RHS || FalseVal != LHS))
1486 return false;
1487 typename CmpInst_t::Predicate Pred =
1488 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1489 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1490 if (!Pred_t::match(Pred))
1491 return false;
1492 // It does! Bind the operands.
1493 return (L.match(LHS) && R.match(RHS)) ||
1494 (Commutable && L.match(RHS) && R.match(LHS));
1495 }
1496};
1497
1498/// Helper class for identifying signed max predicates.
1499struct smax_pred_ty {
1500 static bool match(ICmpInst::Predicate Pred) {
1501 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1502 }
1503};
1504
1505/// Helper class for identifying signed min predicates.
1506struct smin_pred_ty {
1507 static bool match(ICmpInst::Predicate Pred) {
1508 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1509 }
1510};
1511
1512/// Helper class for identifying unsigned max predicates.
1513struct umax_pred_ty {
1514 static bool match(ICmpInst::Predicate Pred) {
1515 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1516 }
1517};
1518
1519/// Helper class for identifying unsigned min predicates.
1520struct umin_pred_ty {
1521 static bool match(ICmpInst::Predicate Pred) {
1522 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1523 }
1524};
1525
1526/// Helper class for identifying ordered max predicates.
1527struct ofmax_pred_ty {
1528 static bool match(FCmpInst::Predicate Pred) {
1529 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1530 }
1531};
1532
1533/// Helper class for identifying ordered min predicates.
1534struct ofmin_pred_ty {
1535 static bool match(FCmpInst::Predicate Pred) {
1536 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1537 }
1538};
1539
1540/// Helper class for identifying unordered max predicates.
1541struct ufmax_pred_ty {
1542 static bool match(FCmpInst::Predicate Pred) {
1543 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1544 }
1545};
1546
1547/// Helper class for identifying unordered min predicates.
1548struct ufmin_pred_ty {
1549 static bool match(FCmpInst::Predicate Pred) {
1550 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1551 }
1552};
1553
1554template <typename LHS, typename RHS>
1555inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1556 const RHS &R) {
1557 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1558}
1559
1560template <typename LHS, typename RHS>
1561inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1562 const RHS &R) {
1563 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1564}
1565
1566template <typename LHS, typename RHS>
1567inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1568 const RHS &R) {
1569 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1570}
1571
1572template <typename LHS, typename RHS>
1573inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1574 const RHS &R) {
1575 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1576}
1577
1578/// Match an 'ordered' floating point maximum function.
1579/// Floating point has one special value 'NaN'. Therefore, there is no total
1580/// order. However, if we can ignore the 'NaN' value (for example, because of a
1581/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1582/// semantics. In the presence of 'NaN' we have to preserve the original
1583/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1584///
1585/// max(L, R) iff L and R are not NaN
1586/// m_OrdFMax(L, R) = R iff L or R are NaN
1587template <typename LHS, typename RHS>
1588inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1589 const RHS &R) {
1590 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1591}
1592
1593/// Match an 'ordered' floating point minimum function.
1594/// Floating point has one special value 'NaN'. Therefore, there is no total
1595/// order. However, if we can ignore the 'NaN' value (for example, because of a
1596/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1597/// semantics. In the presence of 'NaN' we have to preserve the original
1598/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1599///
1600/// min(L, R) iff L and R are not NaN
1601/// m_OrdFMin(L, R) = R iff L or R are NaN
1602template <typename LHS, typename RHS>
1603inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1604 const RHS &R) {
1605 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1606}
1607
1608/// Match an 'unordered' floating point maximum function.
1609/// Floating point has one special value 'NaN'. Therefore, there is no total
1610/// order. However, if we can ignore the 'NaN' value (for example, because of a
1611/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1612/// semantics. In the presence of 'NaN' we have to preserve the original
1613/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1614///
1615/// max(L, R) iff L and R are not NaN
1616/// m_UnordFMax(L, R) = L iff L or R are NaN
1617template <typename LHS, typename RHS>
1618inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
1619m_UnordFMax(const LHS &L, const RHS &R) {
1620 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1621}
1622
1623/// Match an 'unordered' floating point minimum function.
1624/// Floating point has one special value 'NaN'. Therefore, there is no total
1625/// order. However, if we can ignore the 'NaN' value (for example, because of a
1626/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1627/// semantics. In the presence of 'NaN' we have to preserve the original
1628/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1629///
1630/// min(L, R) iff L and R are not NaN
1631/// m_UnordFMin(L, R) = L iff L or R are NaN
1632template <typename LHS, typename RHS>
1633inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
1634m_UnordFMin(const LHS &L, const RHS &R) {
1635 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1636}
1637
1638//===----------------------------------------------------------------------===//
1639// Matchers for overflow check patterns: e.g. (a + b) u< a
1640//
1641
1642template <typename LHS_t, typename RHS_t, typename Sum_t>
1643struct UAddWithOverflow_match {
1644 LHS_t L;
1645 RHS_t R;
1646 Sum_t S;
1647
1648 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1649 : L(L), R(R), S(S) {}
1650
1651 template <typename OpTy> bool match(OpTy *V) {
1652 Value *ICmpLHS, *ICmpRHS;
1653 ICmpInst::Predicate Pred;
1654 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1655 return false;
1656
1657 Value *AddLHS, *AddRHS;
1658 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1659
1660 // (a + b) u< a, (a + b) u< b
1661 if (Pred == ICmpInst::ICMP_ULT)
1662 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1663 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1664
1665 // a >u (a + b), b >u (a + b)
1666 if (Pred == ICmpInst::ICMP_UGT)
1667 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1668 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1669
1670 // Match special-case for increment-by-1.
1671 if (Pred == ICmpInst::ICMP_EQ) {
1672 // (a + 1) == 0
1673 // (1 + a) == 0
1674 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
1675 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1676 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1677 // 0 == (a + 1)
1678 // 0 == (1 + a)
1679 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
1680 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1681 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1682 }
1683
1684 return false;
1685 }
1686};
1687
1688/// Match an icmp instruction checking for unsigned overflow on addition.
1689///
1690/// S is matched to the addition whose result is being checked for overflow, and
1691/// L and R are matched to the LHS and RHS of S.
1692template <typename LHS_t, typename RHS_t, typename Sum_t>
1693UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
1694m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1695 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
1696}
1697
1698template <typename Opnd_t> struct Argument_match {
1699 unsigned OpI;
1700 Opnd_t Val;
1701
1702 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1703
1704 template <typename OpTy> bool match(OpTy *V) {
1705 // FIXME: Should likely be switched to use `CallBase`.
1706 if (const auto *CI = dyn_cast<CallInst>(V))
1707 return Val.match(CI->getArgOperand(OpI));
1708 return false;
1709 }
1710};
1711
1712/// Match an argument.
1713template <unsigned OpI, typename Opnd_t>
1714inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1715 return Argument_match<Opnd_t>(OpI, Op);
1716}
1717
1718/// Intrinsic matchers.
1719struct IntrinsicID_match {
1720 unsigned ID;
1721
1722 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1723
1724 template <typename OpTy> bool match(OpTy *V) {
1725 if (const auto *CI = dyn_cast<CallInst>(V))
1726 if (const auto *F = CI->getCalledFunction())
1727 return F->getIntrinsicID() == ID;
1728 return false;
1729 }
1730};
1731
1732/// Intrinsic matches are combinations of ID matchers, and argument
1733/// matchers. Higher arity matcher are defined recursively in terms of and-ing
1734/// them with lower arity matchers. Here's some convenient typedefs for up to
1735/// several arguments, and more can be added as needed
1736template <typename T0 = void, typename T1 = void, typename T2 = void,
1737 typename T3 = void, typename T4 = void, typename T5 = void,
1738 typename T6 = void, typename T7 = void, typename T8 = void,
1739 typename T9 = void, typename T10 = void>
1740struct m_Intrinsic_Ty;
1741template <typename T0> struct m_Intrinsic_Ty<T0> {
1742 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
1743};
1744template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1745 using Ty =
1746 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
1747};
1748template <typename T0, typename T1, typename T2>
1749struct m_Intrinsic_Ty<T0, T1, T2> {
1750 using Ty =
1751 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
1752 Argument_match<T2>>;
1753};
1754template <typename T0, typename T1, typename T2, typename T3>
1755struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1756 using Ty =
1757 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
1758 Argument_match<T3>>;
1759};
1760
1761template <typename T0, typename T1, typename T2, typename T3, typename T4>
1762struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
1763 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
1764 Argument_match<T4>>;
1765};
1766
1767/// Match intrinsic calls like this:
1768/// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1769template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1770 return IntrinsicID_match(IntrID);
1771}
1772
1773template <Intrinsic::ID IntrID, typename T0>
1774inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1775 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1776}
1777
1778template <Intrinsic::ID IntrID, typename T0, typename T1>
1779inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1780 const T1 &Op1) {
1781 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1782}
1783
1784template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1785inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1786m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1787 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1788}
1789
1790template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1791 typename T3>
1792inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1793m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1794 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1795}
1796
1797template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1798 typename T3, typename T4>
1799inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
1800m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
1801 const T4 &Op4) {
1802 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
1803 m_Argument<4>(Op4));
1804}
1805
1806// Helper intrinsic matching specializations.
1807template <typename Opnd0>
1808inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1809 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1810}
1811
1812template <typename Opnd0>
1813inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1814 return m_Intrinsic<Intrinsic::bswap>(Op0);
1815}
1816
1817template <typename Opnd0>
1818inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
1819 return m_Intrinsic<Intrinsic::fabs>(Op0);
1820}
1821
1822template <typename Opnd0>
1823inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
1824 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
1825}
1826
1827template <typename Opnd0, typename Opnd1>
1828inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1829 const Opnd1 &Op1) {
1830 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1831}
1832
1833template <typename Opnd0, typename Opnd1>
1834inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1835 const Opnd1 &Op1) {
1836 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1837}
1838
1839//===----------------------------------------------------------------------===//
1840// Matchers for two-operands operators with the operators in either order
1841//
1842
1843/// Matches a BinaryOperator with LHS and RHS in either order.
1844template <typename LHS, typename RHS>
1845inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1846 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1847}
1848
1849/// Matches an ICmp with a predicate over LHS and RHS in either order.
1850/// Does not swap the predicate.
1851template <typename LHS, typename RHS>
1852inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
1853m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1854 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
1855 R);
1856}
1857
1858/// Matches a Add with LHS and RHS in either order.
1859template <typename LHS, typename RHS>
1860inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
1861 const RHS &R) {
1862 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
1863}
1864
1865/// Matches a Mul with LHS and RHS in either order.
1866template <typename LHS, typename RHS>
1867inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
1868 const RHS &R) {
1869 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
1870}
1871
1872/// Matches an And with LHS and RHS in either order.
1873template <typename LHS, typename RHS>
1874inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
1875 const RHS &R) {
1876 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
1877}
1878
1879/// Matches an Or with LHS and RHS in either order.
1880template <typename LHS, typename RHS>
1881inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
1882 const RHS &R) {
1883 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
1884}
1885
1886/// Matches an Xor with LHS and RHS in either order.
1887template <typename LHS, typename RHS>
1888inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
1889 const RHS &R) {
1890 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
1891}
1892
1893/// Matches a 'Neg' as 'sub 0, V'.
1894template <typename ValTy>
1895inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
1896m_Neg(const ValTy &V) {
1897 return m_Sub(m_ZeroInt(), V);
1898}
1899
1900/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
1901template <typename ValTy>
1902inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
1903m_Not(const ValTy &V) {
1904 return m_c_Xor(V, m_AllOnes());
1905}
1906
1907/// Matches an SMin with LHS and RHS in either order.
1908template <typename LHS, typename RHS>
1909inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
1910m_c_SMin(const LHS &L, const RHS &R) {
1911 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
1912}
1913/// Matches an SMax with LHS and RHS in either order.
1914template <typename LHS, typename RHS>
1915inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
1916m_c_SMax(const LHS &L, const RHS &R) {
1917 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
1918}
1919/// Matches a UMin with LHS and RHS in either order.
1920template <typename LHS, typename RHS>
1921inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
1922m_c_UMin(const LHS &L, const RHS &R) {
1923 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
1924}
1925/// Matches a UMax with LHS and RHS in either order.
1926template <typename LHS, typename RHS>
1927inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
1928m_c_UMax(const LHS &L, const RHS &R) {
1929 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
1930}
1931
1932/// Matches FAdd with LHS and RHS in either order.
1933template <typename LHS, typename RHS>
1934inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
1935m_c_FAdd(const LHS &L, const RHS &R) {
1936 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
1937}
1938
1939/// Matches FMul with LHS and RHS in either order.
1940template <typename LHS, typename RHS>
1941inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
1942m_c_FMul(const LHS &L, const RHS &R) {
1943 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
1944}
1945
1946template <typename Opnd_t> struct Signum_match {
1947 Opnd_t Val;
1948 Signum_match(const Opnd_t &V) : Val(V) {}
1949
1950 template <typename OpTy> bool match(OpTy *V) {
1951 unsigned TypeSize = V->getType()->getScalarSizeInBits();
1952 if (TypeSize == 0)
1953 return false;
1954
1955 unsigned ShiftWidth = TypeSize - 1;
1956 Value *OpL = nullptr, *OpR = nullptr;
1957
1958 // This is the representation of signum we match:
1959 //
1960 // signum(x) == (x >> 63) | (-x >>u 63)
1961 //
1962 // An i1 value is its own signum, so it's correct to match
1963 //
1964 // signum(x) == (x >> 0) | (-x >>u 0)
1965 //
1966 // for i1 values.
1967
1968 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
1969 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
1970 auto Signum = m_Or(LHS, RHS);
1971
1972 return Signum.match(V) && OpL == OpR && Val.match(OpL);
1973 }
1974};
1975
1976/// Matches a signum pattern.
1977///
1978/// signum(x) =
1979/// x > 0 -> 1
1980/// x == 0 -> 0
1981/// x < 0 -> -1
1982template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
1983 return Signum_match<Val_t>(V);
1984}
1985
1986template <int Ind, typename Opnd_t> struct ExtractValue_match {
1987 Opnd_t Val;
1988 ExtractValue_match(const Opnd_t &V) : Val(V) {}
1989
1990 template <typename OpTy> bool match(OpTy *V) {
1991 if (auto *I = dyn_cast<ExtractValueInst>(V))
1992 return I->getNumIndices() == 1 && I->getIndices()[0] == Ind &&
1993 Val.match(I->getAggregateOperand());
1994 return false;
1995 }
1996};
1997
1998/// Match a single index ExtractValue instruction.
1999/// For example m_ExtractValue<1>(...)
2000template <int Ind, typename Val_t>
2001inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2002 return ExtractValue_match<Ind, Val_t>(V);
2003}
2004
2005} // end namespace PatternMatch
2006} // end namespace llvm
2007
2008#endif // LLVM_IR_PATTERNMATCH_H