1 //===- InstCombineSelect.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 the visitSelect function.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "InstCombineInternal.h"
14 #include "llvm/ADT/APInt.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/CmpInstAnalysis.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/OverflowInstAnalysis.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/Constant.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/InstrTypes.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/Intrinsics.h"
33 #include "llvm/IR/Operator.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/IR/Type.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/ErrorHandling.h"
40 #include "llvm/Support/KnownBits.h"
41 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
42 #include "llvm/Transforms/InstCombine/InstCombiner.h"
43 #include <cassert>
44 #include <utility>
45
46 using namespace llvm;
47 using namespace PatternMatch;
48
49 #define DEBUG_TYPE "instcombine"
50
createMinMax(InstCombiner::BuilderTy & Builder,SelectPatternFlavor SPF,Value * A,Value * B)51 static Value *createMinMax(InstCombiner::BuilderTy &Builder,
52 SelectPatternFlavor SPF, Value *A, Value *B) {
53 CmpInst::Predicate Pred = getMinMaxPred(SPF);
54 assert(CmpInst::isIntPredicate(Pred) && "Expected integer predicate");
55 return Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B);
56 }
57
58 /// Replace a select operand based on an equality comparison with the identity
59 /// constant of a binop.
foldSelectBinOpIdentity(SelectInst & Sel,const TargetLibraryInfo & TLI,InstCombinerImpl & IC)60 static Instruction *foldSelectBinOpIdentity(SelectInst &Sel,
61 const TargetLibraryInfo &TLI,
62 InstCombinerImpl &IC) {
63 // The select condition must be an equality compare with a constant operand.
64 Value *X;
65 Constant *C;
66 CmpInst::Predicate Pred;
67 if (!match(Sel.getCondition(), m_Cmp(Pred, m_Value(X), m_Constant(C))))
68 return nullptr;
69
70 bool IsEq;
71 if (ICmpInst::isEquality(Pred))
72 IsEq = Pred == ICmpInst::ICMP_EQ;
73 else if (Pred == FCmpInst::FCMP_OEQ)
74 IsEq = true;
75 else if (Pred == FCmpInst::FCMP_UNE)
76 IsEq = false;
77 else
78 return nullptr;
79
80 // A select operand must be a binop.
81 BinaryOperator *BO;
82 if (!match(Sel.getOperand(IsEq ? 1 : 2), m_BinOp(BO)))
83 return nullptr;
84
85 // The compare constant must be the identity constant for that binop.
86 // If this a floating-point compare with 0.0, any zero constant will do.
87 Type *Ty = BO->getType();
88 Constant *IdC = ConstantExpr::getBinOpIdentity(BO->getOpcode(), Ty, true);
89 if (IdC != C) {
90 if (!IdC || !CmpInst::isFPPredicate(Pred))
91 return nullptr;
92 if (!match(IdC, m_AnyZeroFP()) || !match(C, m_AnyZeroFP()))
93 return nullptr;
94 }
95
96 // Last, match the compare variable operand with a binop operand.
97 Value *Y;
98 if (!BO->isCommutative() && !match(BO, m_BinOp(m_Value(Y), m_Specific(X))))
99 return nullptr;
100 if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))
101 return nullptr;
102
103 // +0.0 compares equal to -0.0, and so it does not behave as required for this
104 // transform. Bail out if we can not exclude that possibility.
105 if (isa<FPMathOperator>(BO))
106 if (!BO->hasNoSignedZeros() && !CannotBeNegativeZero(Y, &TLI))
107 return nullptr;
108
109 // BO = binop Y, X
110 // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
111 // =>
112 // S = { select (cmp eq X, C), Y, ? } or { select (cmp ne X, C), ?, Y }
113 return IC.replaceOperand(Sel, IsEq ? 1 : 2, Y);
114 }
115
116 /// This folds:
117 /// select (icmp eq (and X, C1)), TC, FC
118 /// iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
119 /// To something like:
120 /// (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
121 /// Or:
122 /// (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
123 /// With some variations depending if FC is larger than TC, or the shift
124 /// isn't needed, or the bit widths don't match.
foldSelectICmpAnd(SelectInst & Sel,ICmpInst * Cmp,InstCombiner::BuilderTy & Builder)125 static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp,
126 InstCombiner::BuilderTy &Builder) {
127 const APInt *SelTC, *SelFC;
128 if (!match(Sel.getTrueValue(), m_APInt(SelTC)) ||
129 !match(Sel.getFalseValue(), m_APInt(SelFC)))
130 return nullptr;
131
132 // If this is a vector select, we need a vector compare.
133 Type *SelType = Sel.getType();
134 if (SelType->isVectorTy() != Cmp->getType()->isVectorTy())
135 return nullptr;
136
137 Value *V;
138 APInt AndMask;
139 bool CreateAnd = false;
140 ICmpInst::Predicate Pred = Cmp->getPredicate();
141 if (ICmpInst::isEquality(Pred)) {
142 if (!match(Cmp->getOperand(1), m_Zero()))
143 return nullptr;
144
145 V = Cmp->getOperand(0);
146 const APInt *AndRHS;
147 if (!match(V, m_And(m_Value(), m_Power2(AndRHS))))
148 return nullptr;
149
150 AndMask = *AndRHS;
151 } else if (decomposeBitTestICmp(Cmp->getOperand(0), Cmp->getOperand(1),
152 Pred, V, AndMask)) {
153 assert(ICmpInst::isEquality(Pred) && "Not equality test?");
154 if (!AndMask.isPowerOf2())
155 return nullptr;
156
157 CreateAnd = true;
158 } else {
159 return nullptr;
160 }
161
162 // In general, when both constants are non-zero, we would need an offset to
163 // replace the select. This would require more instructions than we started
164 // with. But there's one special-case that we handle here because it can
165 // simplify/reduce the instructions.
166 APInt TC = *SelTC;
167 APInt FC = *SelFC;
168 if (!TC.isNullValue() && !FC.isNullValue()) {
169 // If the select constants differ by exactly one bit and that's the same
170 // bit that is masked and checked by the select condition, the select can
171 // be replaced by bitwise logic to set/clear one bit of the constant result.
172 if (TC.getBitWidth() != AndMask.getBitWidth() || (TC ^ FC) != AndMask)
173 return nullptr;
174 if (CreateAnd) {
175 // If we have to create an 'and', then we must kill the cmp to not
176 // increase the instruction count.
177 if (!Cmp->hasOneUse())
178 return nullptr;
179 V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask));
180 }
181 bool ExtraBitInTC = TC.ugt(FC);
182 if (Pred == ICmpInst::ICMP_EQ) {
183 // If the masked bit in V is clear, clear or set the bit in the result:
184 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
185 // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
186 Constant *C = ConstantInt::get(SelType, TC);
187 return ExtraBitInTC ? Builder.CreateXor(V, C) : Builder.CreateOr(V, C);
188 }
189 if (Pred == ICmpInst::ICMP_NE) {
190 // If the masked bit in V is set, set or clear the bit in the result:
191 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
192 // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
193 Constant *C = ConstantInt::get(SelType, FC);
194 return ExtraBitInTC ? Builder.CreateOr(V, C) : Builder.CreateXor(V, C);
195 }
196 llvm_unreachable("Only expecting equality predicates");
197 }
198
199 // Make sure one of the select arms is a power-of-2.
200 if (!TC.isPowerOf2() && !FC.isPowerOf2())
201 return nullptr;
202
203 // Determine which shift is needed to transform result of the 'and' into the
204 // desired result.
205 const APInt &ValC = !TC.isNullValue() ? TC : FC;
206 unsigned ValZeros = ValC.logBase2();
207 unsigned AndZeros = AndMask.logBase2();
208
209 // Insert the 'and' instruction on the input to the truncate.
210 if (CreateAnd)
211 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));
212
213 // If types don't match, we can still convert the select by introducing a zext
214 // or a trunc of the 'and'.
215 if (ValZeros > AndZeros) {
216 V = Builder.CreateZExtOrTrunc(V, SelType);
217 V = Builder.CreateShl(V, ValZeros - AndZeros);
218 } else if (ValZeros < AndZeros) {
219 V = Builder.CreateLShr(V, AndZeros - ValZeros);
220 V = Builder.CreateZExtOrTrunc(V, SelType);
221 } else {
222 V = Builder.CreateZExtOrTrunc(V, SelType);
223 }
224
225 // Okay, now we know that everything is set up, we just don't know whether we
226 // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
227 bool ShouldNotVal = !TC.isNullValue();
228 ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
229 if (ShouldNotVal)
230 V = Builder.CreateXor(V, ValC);
231
232 return V;
233 }
234
235 /// We want to turn code that looks like this:
236 /// %C = or %A, %B
237 /// %D = select %cond, %C, %A
238 /// into:
239 /// %C = select %cond, %B, 0
240 /// %D = or %A, %C
241 ///
242 /// Assuming that the specified instruction is an operand to the select, return
243 /// a bitmask indicating which operands of this instruction are foldable if they
244 /// equal the other incoming value of the select.
getSelectFoldableOperands(BinaryOperator * I)245 static unsigned getSelectFoldableOperands(BinaryOperator *I) {
246 switch (I->getOpcode()) {
247 case Instruction::Add:
248 case Instruction::Mul:
249 case Instruction::And:
250 case Instruction::Or:
251 case Instruction::Xor:
252 return 3; // Can fold through either operand.
253 case Instruction::Sub: // Can only fold on the amount subtracted.
254 case Instruction::Shl: // Can only fold on the shift amount.
255 case Instruction::LShr:
256 case Instruction::AShr:
257 return 1;
258 default:
259 return 0; // Cannot fold
260 }
261 }
262
263 /// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
foldSelectOpOp(SelectInst & SI,Instruction * TI,Instruction * FI)264 Instruction *InstCombinerImpl::foldSelectOpOp(SelectInst &SI, Instruction *TI,
265 Instruction *FI) {
266 // Don't break up min/max patterns. The hasOneUse checks below prevent that
267 // for most cases, but vector min/max with bitcasts can be transformed. If the
268 // one-use restrictions are eased for other patterns, we still don't want to
269 // obfuscate min/max.
270 if ((match(&SI, m_SMin(m_Value(), m_Value())) ||
271 match(&SI, m_SMax(m_Value(), m_Value())) ||
272 match(&SI, m_UMin(m_Value(), m_Value())) ||
273 match(&SI, m_UMax(m_Value(), m_Value()))))
274 return nullptr;
275
276 // If this is a cast from the same type, merge.
277 Value *Cond = SI.getCondition();
278 Type *CondTy = Cond->getType();
279 if (TI->getNumOperands() == 1 && TI->isCast()) {
280 Type *FIOpndTy = FI->getOperand(0)->getType();
281 if (TI->getOperand(0)->getType() != FIOpndTy)
282 return nullptr;
283
284 // The select condition may be a vector. We may only change the operand
285 // type if the vector width remains the same (and matches the condition).
286 if (auto *CondVTy = dyn_cast<VectorType>(CondTy)) {
287 if (!FIOpndTy->isVectorTy() ||
288 CondVTy->getElementCount() !=
289 cast<VectorType>(FIOpndTy)->getElementCount())
290 return nullptr;
291
292 // TODO: If the backend knew how to deal with casts better, we could
293 // remove this limitation. For now, there's too much potential to create
294 // worse codegen by promoting the select ahead of size-altering casts
295 // (PR28160).
296 //
297 // Note that ValueTracking's matchSelectPattern() looks through casts
298 // without checking 'hasOneUse' when it matches min/max patterns, so this
299 // transform may end up happening anyway.
300 if (TI->getOpcode() != Instruction::BitCast &&
301 (!TI->hasOneUse() || !FI->hasOneUse()))
302 return nullptr;
303 } else if (!TI->hasOneUse() || !FI->hasOneUse()) {
304 // TODO: The one-use restrictions for a scalar select could be eased if
305 // the fold of a select in visitLoadInst() was enhanced to match a pattern
306 // that includes a cast.
307 return nullptr;
308 }
309
310 // Fold this by inserting a select from the input values.
311 Value *NewSI =
312 Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0),
313 SI.getName() + ".v", &SI);
314 return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,
315 TI->getType());
316 }
317
318 // Cond ? -X : -Y --> -(Cond ? X : Y)
319 Value *X, *Y;
320 if (match(TI, m_FNeg(m_Value(X))) && match(FI, m_FNeg(m_Value(Y))) &&
321 (TI->hasOneUse() || FI->hasOneUse())) {
322 Value *NewSel = Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI);
323 return UnaryOperator::CreateFNegFMF(NewSel, TI);
324 }
325
326 // Min/max intrinsic with a common operand can have the common operand pulled
327 // after the select. This is the same transform as below for binops, but
328 // specialized for intrinsic matching and without the restrictive uses clause.
329 auto *TII = dyn_cast<IntrinsicInst>(TI);
330 auto *FII = dyn_cast<IntrinsicInst>(FI);
331 if (TII && FII && TII->getIntrinsicID() == FII->getIntrinsicID() &&
332 (TII->hasOneUse() || FII->hasOneUse())) {
333 Value *T0, *T1, *F0, *F1;
334 if (match(TII, m_MaxOrMin(m_Value(T0), m_Value(T1))) &&
335 match(FII, m_MaxOrMin(m_Value(F0), m_Value(F1)))) {
336 if (T0 == F0) {
337 Value *NewSel = Builder.CreateSelect(Cond, T1, F1, "minmaxop", &SI);
338 return CallInst::Create(TII->getCalledFunction(), {NewSel, T0});
339 }
340 if (T0 == F1) {
341 Value *NewSel = Builder.CreateSelect(Cond, T1, F0, "minmaxop", &SI);
342 return CallInst::Create(TII->getCalledFunction(), {NewSel, T0});
343 }
344 if (T1 == F0) {
345 Value *NewSel = Builder.CreateSelect(Cond, T0, F1, "minmaxop", &SI);
346 return CallInst::Create(TII->getCalledFunction(), {NewSel, T1});
347 }
348 if (T1 == F1) {
349 Value *NewSel = Builder.CreateSelect(Cond, T0, F0, "minmaxop", &SI);
350 return CallInst::Create(TII->getCalledFunction(), {NewSel, T1});
351 }
352 }
353 }
354
355 // Only handle binary operators (including two-operand getelementptr) with
356 // one-use here. As with the cast case above, it may be possible to relax the
357 // one-use constraint, but that needs be examined carefully since it may not
358 // reduce the total number of instructions.
359 if (TI->getNumOperands() != 2 || FI->getNumOperands() != 2 ||
360 (!isa<BinaryOperator>(TI) && !isa<GetElementPtrInst>(TI)) ||
361 !TI->hasOneUse() || !FI->hasOneUse())
362 return nullptr;
363
364 // Figure out if the operations have any operands in common.
365 Value *MatchOp, *OtherOpT, *OtherOpF;
366 bool MatchIsOpZero;
367 if (TI->getOperand(0) == FI->getOperand(0)) {
368 MatchOp = TI->getOperand(0);
369 OtherOpT = TI->getOperand(1);
370 OtherOpF = FI->getOperand(1);
371 MatchIsOpZero = true;
372 } else if (TI->getOperand(1) == FI->getOperand(1)) {
373 MatchOp = TI->getOperand(1);
374 OtherOpT = TI->getOperand(0);
375 OtherOpF = FI->getOperand(0);
376 MatchIsOpZero = false;
377 } else if (!TI->isCommutative()) {
378 return nullptr;
379 } else if (TI->getOperand(0) == FI->getOperand(1)) {
380 MatchOp = TI->getOperand(0);
381 OtherOpT = TI->getOperand(1);
382 OtherOpF = FI->getOperand(0);
383 MatchIsOpZero = true;
384 } else if (TI->getOperand(1) == FI->getOperand(0)) {
385 MatchOp = TI->getOperand(1);
386 OtherOpT = TI->getOperand(0);
387 OtherOpF = FI->getOperand(1);
388 MatchIsOpZero = true;
389 } else {
390 return nullptr;
391 }
392
393 // If the select condition is a vector, the operands of the original select's
394 // operands also must be vectors. This may not be the case for getelementptr
395 // for example.
396 if (CondTy->isVectorTy() && (!OtherOpT->getType()->isVectorTy() ||
397 !OtherOpF->getType()->isVectorTy()))
398 return nullptr;
399
400 // If we reach here, they do have operations in common.
401 Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
402 SI.getName() + ".v", &SI);
403 Value *Op0 = MatchIsOpZero ? MatchOp : NewSI;
404 Value *Op1 = MatchIsOpZero ? NewSI : MatchOp;
405 if (auto *BO = dyn_cast<BinaryOperator>(TI)) {
406 BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
407 NewBO->copyIRFlags(TI);
408 NewBO->andIRFlags(FI);
409 return NewBO;
410 }
411 if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
412 auto *FGEP = cast<GetElementPtrInst>(FI);
413 Type *ElementType = TGEP->getResultElementType();
414 return TGEP->isInBounds() && FGEP->isInBounds()
415 ? GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1})
416 : GetElementPtrInst::Create(ElementType, Op0, {Op1});
417 }
418 llvm_unreachable("Expected BinaryOperator or GEP");
419 return nullptr;
420 }
421
isSelect01(const APInt & C1I,const APInt & C2I)422 static bool isSelect01(const APInt &C1I, const APInt &C2I) {
423 if (!C1I.isNullValue() && !C2I.isNullValue()) // One side must be zero.
424 return false;
425 return C1I.isOneValue() || C1I.isAllOnesValue() ||
426 C2I.isOneValue() || C2I.isAllOnesValue();
427 }
428
429 /// Try to fold the select into one of the operands to allow further
430 /// optimization.
foldSelectIntoOp(SelectInst & SI,Value * TrueVal,Value * FalseVal)431 Instruction *InstCombinerImpl::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,
432 Value *FalseVal) {
433 // See the comment above GetSelectFoldableOperands for a description of the
434 // transformation we are doing here.
435 if (auto *TVI = dyn_cast<BinaryOperator>(TrueVal)) {
436 if (TVI->hasOneUse() && !isa<Constant>(FalseVal)) {
437 if (unsigned SFO = getSelectFoldableOperands(TVI)) {
438 unsigned OpToFold = 0;
439 if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
440 OpToFold = 1;
441 } else if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
442 OpToFold = 2;
443 }
444
445 if (OpToFold) {
446 Constant *C = ConstantExpr::getBinOpIdentity(TVI->getOpcode(),
447 TVI->getType(), true);
448 Value *OOp = TVI->getOperand(2-OpToFold);
449 // Avoid creating select between 2 constants unless it's selecting
450 // between 0, 1 and -1.
451 const APInt *OOpC;
452 bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
453 if (!isa<Constant>(OOp) ||
454 (OOpIsAPInt && isSelect01(C->getUniqueInteger(), *OOpC))) {
455 Value *NewSel = Builder.CreateSelect(SI.getCondition(), OOp, C);
456 NewSel->takeName(TVI);
457 BinaryOperator *BO = BinaryOperator::Create(TVI->getOpcode(),
458 FalseVal, NewSel);
459 BO->copyIRFlags(TVI);
460 return BO;
461 }
462 }
463 }
464 }
465 }
466
467 if (auto *FVI = dyn_cast<BinaryOperator>(FalseVal)) {
468 if (FVI->hasOneUse() && !isa<Constant>(TrueVal)) {
469 if (unsigned SFO = getSelectFoldableOperands(FVI)) {
470 unsigned OpToFold = 0;
471 if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
472 OpToFold = 1;
473 } else if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
474 OpToFold = 2;
475 }
476
477 if (OpToFold) {
478 Constant *C = ConstantExpr::getBinOpIdentity(FVI->getOpcode(),
479 FVI->getType(), true);
480 Value *OOp = FVI->getOperand(2-OpToFold);
481 // Avoid creating select between 2 constants unless it's selecting
482 // between 0, 1 and -1.
483 const APInt *OOpC;
484 bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
485 if (!isa<Constant>(OOp) ||
486 (OOpIsAPInt && isSelect01(C->getUniqueInteger(), *OOpC))) {
487 Value *NewSel = Builder.CreateSelect(SI.getCondition(), C, OOp);
488 NewSel->takeName(FVI);
489 BinaryOperator *BO = BinaryOperator::Create(FVI->getOpcode(),
490 TrueVal, NewSel);
491 BO->copyIRFlags(FVI);
492 return BO;
493 }
494 }
495 }
496 }
497 }
498
499 return nullptr;
500 }
501
502 /// We want to turn:
503 /// (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
504 /// into:
505 /// zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
506 /// Note:
507 /// Z may be 0 if lshr is missing.
508 /// Worst-case scenario is that we will replace 5 instructions with 5 different
509 /// instructions, but we got rid of select.
foldSelectICmpAndAnd(Type * SelType,const ICmpInst * Cmp,Value * TVal,Value * FVal,InstCombiner::BuilderTy & Builder)510 static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
511 Value *TVal, Value *FVal,
512 InstCombiner::BuilderTy &Builder) {
513 if (!(Cmp->hasOneUse() && Cmp->getOperand(0)->hasOneUse() &&
514 Cmp->getPredicate() == ICmpInst::ICMP_EQ &&
515 match(Cmp->getOperand(1), m_Zero()) && match(FVal, m_One())))
516 return nullptr;
517
518 // The TrueVal has general form of: and %B, 1
519 Value *B;
520 if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))
521 return nullptr;
522
523 // Where %B may be optionally shifted: lshr %X, %Z.
524 Value *X, *Z;
525 const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));
526 if (!HasShift)
527 X = B;
528
529 Value *Y;
530 if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
531 return nullptr;
532
533 // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
534 // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
535 Constant *One = ConstantInt::get(SelType, 1);
536 Value *MaskB = HasShift ? Builder.CreateShl(One, Z) : One;
537 Value *FullMask = Builder.CreateOr(Y, MaskB);
538 Value *MaskedX = Builder.CreateAnd(X, FullMask);
539 Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
540 return new ZExtInst(ICmpNeZero, SelType);
541 }
542
543 /// We want to turn:
544 /// (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
545 /// (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
546 /// into:
547 /// ashr (X, Y)
foldSelectICmpLshrAshr(const ICmpInst * IC,Value * TrueVal,Value * FalseVal,InstCombiner::BuilderTy & Builder)548 static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,
549 Value *FalseVal,
550 InstCombiner::BuilderTy &Builder) {
551 ICmpInst::Predicate Pred = IC->getPredicate();
552 Value *CmpLHS = IC->getOperand(0);
553 Value *CmpRHS = IC->getOperand(1);
554 if (!CmpRHS->getType()->isIntOrIntVectorTy())
555 return nullptr;
556
557 Value *X, *Y;
558 unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
559 if ((Pred != ICmpInst::ICMP_SGT ||
560 !match(CmpRHS,
561 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
562 (Pred != ICmpInst::ICMP_SLT ||
563 !match(CmpRHS,
564 m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, 0)))))
565 return nullptr;
566
567 // Canonicalize so that ashr is in FalseVal.
568 if (Pred == ICmpInst::ICMP_SLT)
569 std::swap(TrueVal, FalseVal);
570
571 if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
572 match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y))) &&
573 match(CmpLHS, m_Specific(X))) {
574 const auto *Ashr = cast<Instruction>(FalseVal);
575 // if lshr is not exact and ashr is, this new ashr must not be exact.
576 bool IsExact = Ashr->isExact() && cast<Instruction>(TrueVal)->isExact();
577 return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
578 }
579
580 return nullptr;
581 }
582
583 /// We want to turn:
584 /// (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
585 /// into:
586 /// (or (shl (and X, C1), C3), Y)
587 /// iff:
588 /// C1 and C2 are both powers of 2
589 /// where:
590 /// C3 = Log(C2) - Log(C1)
591 ///
592 /// This transform handles cases where:
593 /// 1. The icmp predicate is inverted
594 /// 2. The select operands are reversed
595 /// 3. The magnitude of C2 and C1 are flipped
foldSelectICmpAndOr(const ICmpInst * IC,Value * TrueVal,Value * FalseVal,InstCombiner::BuilderTy & Builder)596 static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal,
597 Value *FalseVal,
598 InstCombiner::BuilderTy &Builder) {
599 // Only handle integer compares. Also, if this is a vector select, we need a
600 // vector compare.
601 if (!TrueVal->getType()->isIntOrIntVectorTy() ||
602 TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy())
603 return nullptr;
604
605 Value *CmpLHS = IC->getOperand(0);
606 Value *CmpRHS = IC->getOperand(1);
607
608 Value *V;
609 unsigned C1Log;
610 bool IsEqualZero;
611 bool NeedAnd = false;
612 if (IC->isEquality()) {
613 if (!match(CmpRHS, m_Zero()))
614 return nullptr;
615
616 const APInt *C1;
617 if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
618 return nullptr;
619
620 V = CmpLHS;
621 C1Log = C1->logBase2();
622 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
623 } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
624 IC->getPredicate() == ICmpInst::ICMP_SGT) {
625 // We also need to recognize (icmp slt (trunc (X)), 0) and
626 // (icmp sgt (trunc (X)), -1).
627 IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
628 if ((IsEqualZero && !match(CmpRHS, m_AllOnes())) ||
629 (!IsEqualZero && !match(CmpRHS, m_Zero())))
630 return nullptr;
631
632 if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
633 return nullptr;
634
635 C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
636 NeedAnd = true;
637 } else {
638 return nullptr;
639 }
640
641 const APInt *C2;
642 bool OrOnTrueVal = false;
643 bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
644 if (!OrOnFalseVal)
645 OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
646
647 if (!OrOnFalseVal && !OrOnTrueVal)
648 return nullptr;
649
650 Value *Y = OrOnFalseVal ? TrueVal : FalseVal;
651
652 unsigned C2Log = C2->logBase2();
653
654 bool NeedXor = (!IsEqualZero && OrOnFalseVal) || (IsEqualZero && OrOnTrueVal);
655 bool NeedShift = C1Log != C2Log;
656 bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
657 V->getType()->getScalarSizeInBits();
658
659 // Make sure we don't create more instructions than we save.
660 Value *Or = OrOnFalseVal ? FalseVal : TrueVal;
661 if ((NeedShift + NeedXor + NeedZExtTrunc) >
662 (IC->hasOneUse() + Or->hasOneUse()))
663 return nullptr;
664
665 if (NeedAnd) {
666 // Insert the AND instruction on the input to the truncate.
667 APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log);
668 V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
669 }
670
671 if (C2Log > C1Log) {
672 V = Builder.CreateZExtOrTrunc(V, Y->getType());
673 V = Builder.CreateShl(V, C2Log - C1Log);
674 } else if (C1Log > C2Log) {
675 V = Builder.CreateLShr(V, C1Log - C2Log);
676 V = Builder.CreateZExtOrTrunc(V, Y->getType());
677 } else
678 V = Builder.CreateZExtOrTrunc(V, Y->getType());
679
680 if (NeedXor)
681 V = Builder.CreateXor(V, *C2);
682
683 return Builder.CreateOr(V, Y);
684 }
685
686 /// Canonicalize a set or clear of a masked set of constant bits to
687 /// select-of-constants form.
foldSetClearBits(SelectInst & Sel,InstCombiner::BuilderTy & Builder)688 static Instruction *foldSetClearBits(SelectInst &Sel,
689 InstCombiner::BuilderTy &Builder) {
690 Value *Cond = Sel.getCondition();
691 Value *T = Sel.getTrueValue();
692 Value *F = Sel.getFalseValue();
693 Type *Ty = Sel.getType();
694 Value *X;
695 const APInt *NotC, *C;
696
697 // Cond ? (X & ~C) : (X | C) --> (X & ~C) | (Cond ? 0 : C)
698 if (match(T, m_And(m_Value(X), m_APInt(NotC))) &&
699 match(F, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
700 Constant *Zero = ConstantInt::getNullValue(Ty);
701 Constant *OrC = ConstantInt::get(Ty, *C);
702 Value *NewSel = Builder.CreateSelect(Cond, Zero, OrC, "masksel", &Sel);
703 return BinaryOperator::CreateOr(T, NewSel);
704 }
705
706 // Cond ? (X | C) : (X & ~C) --> (X & ~C) | (Cond ? C : 0)
707 if (match(F, m_And(m_Value(X), m_APInt(NotC))) &&
708 match(T, m_OneUse(m_Or(m_Specific(X), m_APInt(C)))) && *NotC == ~(*C)) {
709 Constant *Zero = ConstantInt::getNullValue(Ty);
710 Constant *OrC = ConstantInt::get(Ty, *C);
711 Value *NewSel = Builder.CreateSelect(Cond, OrC, Zero, "masksel", &Sel);
712 return BinaryOperator::CreateOr(F, NewSel);
713 }
714
715 return nullptr;
716 }
717
718 /// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
719 /// There are 8 commuted/swapped variants of this pattern.
720 /// TODO: Also support a - UMIN(a,b) patterns.
canonicalizeSaturatedSubtract(const ICmpInst * ICI,const Value * TrueVal,const Value * FalseVal,InstCombiner::BuilderTy & Builder)721 static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,
722 const Value *TrueVal,
723 const Value *FalseVal,
724 InstCombiner::BuilderTy &Builder) {
725 ICmpInst::Predicate Pred = ICI->getPredicate();
726 if (!ICmpInst::isUnsigned(Pred))
727 return nullptr;
728
729 // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
730 if (match(TrueVal, m_Zero())) {
731 Pred = ICmpInst::getInversePredicate(Pred);
732 std::swap(TrueVal, FalseVal);
733 }
734 if (!match(FalseVal, m_Zero()))
735 return nullptr;
736
737 Value *A = ICI->getOperand(0);
738 Value *B = ICI->getOperand(1);
739 if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
740 // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
741 std::swap(A, B);
742 Pred = ICmpInst::getSwappedPredicate(Pred);
743 }
744
745 assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
746 "Unexpected isUnsigned predicate!");
747
748 // Ensure the sub is of the form:
749 // (a > b) ? a - b : 0 -> usub.sat(a, b)
750 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
751 // Checking for both a-b and a+(-b) as a constant.
752 bool IsNegative = false;
753 const APInt *C;
754 if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))) ||
755 (match(A, m_APInt(C)) &&
756 match(TrueVal, m_Add(m_Specific(B), m_SpecificInt(-*C)))))
757 IsNegative = true;
758 else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))) &&
759 !(match(B, m_APInt(C)) &&
760 match(TrueVal, m_Add(m_Specific(A), m_SpecificInt(-*C)))))
761 return nullptr;
762
763 // If we are adding a negate and the sub and icmp are used anywhere else, we
764 // would end up with more instructions.
765 if (IsNegative && !TrueVal->hasOneUse() && !ICI->hasOneUse())
766 return nullptr;
767
768 // (a > b) ? a - b : 0 -> usub.sat(a, b)
769 // (a > b) ? b - a : 0 -> -usub.sat(a, b)
770 Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
771 if (IsNegative)
772 Result = Builder.CreateNeg(Result);
773 return Result;
774 }
775
canonicalizeSaturatedAdd(ICmpInst * Cmp,Value * TVal,Value * FVal,InstCombiner::BuilderTy & Builder)776 static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
777 InstCombiner::BuilderTy &Builder) {
778 if (!Cmp->hasOneUse())
779 return nullptr;
780
781 // Match unsigned saturated add with constant.
782 Value *Cmp0 = Cmp->getOperand(0);
783 Value *Cmp1 = Cmp->getOperand(1);
784 ICmpInst::Predicate Pred = Cmp->getPredicate();
785 Value *X;
786 const APInt *C, *CmpC;
787 if (Pred == ICmpInst::ICMP_ULT &&
788 match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
789 match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
790 // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
791 return Builder.CreateBinaryIntrinsic(
792 Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
793 }
794
795 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
796 // There are 8 commuted variants.
797 // Canonicalize -1 (saturated result) to true value of the select.
798 if (match(FVal, m_AllOnes())) {
799 std::swap(TVal, FVal);
800 Pred = CmpInst::getInversePredicate(Pred);
801 }
802 if (!match(TVal, m_AllOnes()))
803 return nullptr;
804
805 // Canonicalize predicate to less-than or less-or-equal-than.
806 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
807 std::swap(Cmp0, Cmp1);
808 Pred = CmpInst::getSwappedPredicate(Pred);
809 }
810 if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
811 return nullptr;
812
813 // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
814 // Strictness of the comparison is irrelevant.
815 Value *Y;
816 if (match(Cmp0, m_Not(m_Value(X))) &&
817 match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
818 // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
819 // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
820 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
821 }
822 // The 'not' op may be included in the sum but not the compare.
823 // Strictness of the comparison is irrelevant.
824 X = Cmp0;
825 Y = Cmp1;
826 if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
827 // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
828 // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
829 BinaryOperator *BO = cast<BinaryOperator>(FVal);
830 return Builder.CreateBinaryIntrinsic(
831 Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
832 }
833 // The overflow may be detected via the add wrapping round.
834 // This is only valid for strict comparison!
835 if (Pred == ICmpInst::ICMP_ULT &&
836 match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
837 match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
838 // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
839 // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
840 return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
841 }
842
843 return nullptr;
844 }
845
846 /// Fold the following code sequence:
847 /// \code
848 /// int a = ctlz(x & -x);
849 // x ? 31 - a : a;
850 /// \code
851 ///
852 /// into:
853 /// cttz(x)
foldSelectCtlzToCttz(ICmpInst * ICI,Value * TrueVal,Value * FalseVal,InstCombiner::BuilderTy & Builder)854 static Instruction *foldSelectCtlzToCttz(ICmpInst *ICI, Value *TrueVal,
855 Value *FalseVal,
856 InstCombiner::BuilderTy &Builder) {
857 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
858 if (!ICI->isEquality() || !match(ICI->getOperand(1), m_Zero()))
859 return nullptr;
860
861 if (ICI->getPredicate() == ICmpInst::ICMP_NE)
862 std::swap(TrueVal, FalseVal);
863
864 if (!match(FalseVal,
865 m_Xor(m_Deferred(TrueVal), m_SpecificInt(BitWidth - 1))))
866 return nullptr;
867
868 if (!match(TrueVal, m_Intrinsic<Intrinsic::ctlz>()))
869 return nullptr;
870
871 Value *X = ICI->getOperand(0);
872 auto *II = cast<IntrinsicInst>(TrueVal);
873 if (!match(II->getOperand(0), m_c_And(m_Specific(X), m_Neg(m_Specific(X)))))
874 return nullptr;
875
876 Function *F = Intrinsic::getDeclaration(II->getModule(), Intrinsic::cttz,
877 II->getType());
878 return CallInst::Create(F, {X, II->getArgOperand(1)});
879 }
880
881 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
882 /// call to cttz/ctlz with flag 'is_zero_undef' cleared.
883 ///
884 /// For example, we can fold the following code sequence:
885 /// \code
886 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
887 /// %1 = icmp ne i32 %x, 0
888 /// %2 = select i1 %1, i32 %0, i32 32
889 /// \code
890 ///
891 /// into:
892 /// %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
foldSelectCttzCtlz(ICmpInst * ICI,Value * TrueVal,Value * FalseVal,InstCombiner::BuilderTy & Builder)893 static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
894 InstCombiner::BuilderTy &Builder) {
895 ICmpInst::Predicate Pred = ICI->getPredicate();
896 Value *CmpLHS = ICI->getOperand(0);
897 Value *CmpRHS = ICI->getOperand(1);
898
899 // Check if the condition value compares a value for equality against zero.
900 if (!ICI->isEquality() || !match(CmpRHS, m_Zero()))
901 return nullptr;
902
903 Value *SelectArg = FalseVal;
904 Value *ValueOnZero = TrueVal;
905 if (Pred == ICmpInst::ICMP_NE)
906 std::swap(SelectArg, ValueOnZero);
907
908 // Skip zero extend/truncate.
909 Value *Count = nullptr;
910 if (!match(SelectArg, m_ZExt(m_Value(Count))) &&
911 !match(SelectArg, m_Trunc(m_Value(Count))))
912 Count = SelectArg;
913
914 // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
915 // input to the cttz/ctlz is used as LHS for the compare instruction.
916 if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) &&
917 !match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS))))
918 return nullptr;
919
920 IntrinsicInst *II = cast<IntrinsicInst>(Count);
921
922 // Check if the value propagated on zero is a constant number equal to the
923 // sizeof in bits of 'Count'.
924 unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
925 if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
926 // Explicitly clear the 'undef_on_zero' flag. It's always valid to go from
927 // true to false on this flag, so we can replace it for all users.
928 II->setArgOperand(1, ConstantInt::getFalse(II->getContext()));
929 return SelectArg;
930 }
931
932 // The ValueOnZero is not the bitwidth. But if the cttz/ctlz (and optional
933 // zext/trunc) have one use (ending at the select), the cttz/ctlz result will
934 // not be used if the input is zero. Relax to 'undef_on_zero' for that case.
935 if (II->hasOneUse() && SelectArg->hasOneUse() &&
936 !match(II->getArgOperand(1), m_One()))
937 II->setArgOperand(1, ConstantInt::getTrue(II->getContext()));
938
939 return nullptr;
940 }
941
942 /// Return true if we find and adjust an icmp+select pattern where the compare
943 /// is with a constant that can be incremented or decremented to match the
944 /// minimum or maximum idiom.
adjustMinMax(SelectInst & Sel,ICmpInst & Cmp)945 static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) {
946 ICmpInst::Predicate Pred = Cmp.getPredicate();
947 Value *CmpLHS = Cmp.getOperand(0);
948 Value *CmpRHS = Cmp.getOperand(1);
949 Value *TrueVal = Sel.getTrueValue();
950 Value *FalseVal = Sel.getFalseValue();
951
952 // We may move or edit the compare, so make sure the select is the only user.
953 const APInt *CmpC;
954 if (!Cmp.hasOneUse() || !match(CmpRHS, m_APInt(CmpC)))
955 return false;
956
957 // These transforms only work for selects of integers or vector selects of
958 // integer vectors.
959 Type *SelTy = Sel.getType();
960 auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType());
961 if (!SelEltTy || SelTy->isVectorTy() != Cmp.getType()->isVectorTy())
962 return false;
963
964 Constant *AdjustedRHS;
965 if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SGT)
966 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1);
967 else if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT)
968 AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1);
969 else
970 return false;
971
972 // X > C ? X : C+1 --> X < C+1 ? C+1 : X
973 // X < C ? X : C-1 --> X > C-1 ? C-1 : X
974 if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
975 (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
976 ; // Nothing to do here. Values match without any sign/zero extension.
977 }
978 // Types do not match. Instead of calculating this with mixed types, promote
979 // all to the larger type. This enables scalar evolution to analyze this
980 // expression.
981 else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) {
982 Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy);
983
984 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
985 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
986 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
987 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
988 if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && SextRHS == FalseVal) {
989 CmpLHS = TrueVal;
990 AdjustedRHS = SextRHS;
991 } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) &&
992 SextRHS == TrueVal) {
993 CmpLHS = FalseVal;
994 AdjustedRHS = SextRHS;
995 } else if (Cmp.isUnsigned()) {
996 Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy);
997 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
998 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
999 // zext + signed compare cannot be changed:
1000 // 0xff <s 0x00, but 0x00ff >s 0x0000
1001 if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && ZextRHS == FalseVal) {
1002 CmpLHS = TrueVal;
1003 AdjustedRHS = ZextRHS;
1004 } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) &&
1005 ZextRHS == TrueVal) {
1006 CmpLHS = FalseVal;
1007 AdjustedRHS = ZextRHS;
1008 } else {
1009 return false;
1010 }
1011 } else {
1012 return false;
1013 }
1014 } else {
1015 return false;
1016 }
1017
1018 Pred = ICmpInst::getSwappedPredicate(Pred);
1019 CmpRHS = AdjustedRHS;
1020 std::swap(FalseVal, TrueVal);
1021 Cmp.setPredicate(Pred);
1022 Cmp.setOperand(0, CmpLHS);
1023 Cmp.setOperand(1, CmpRHS);
1024 Sel.setOperand(1, TrueVal);
1025 Sel.setOperand(2, FalseVal);
1026 Sel.swapProfMetadata();
1027
1028 // Move the compare instruction right before the select instruction. Otherwise
1029 // the sext/zext value may be defined after the compare instruction uses it.
1030 Cmp.moveBefore(&Sel);
1031
1032 return true;
1033 }
1034
1035 /// If this is an integer min/max (icmp + select) with a constant operand,
1036 /// create the canonical icmp for the min/max operation and canonicalize the
1037 /// constant to the 'false' operand of the select:
1038 /// select (icmp Pred X, C1), C2, X --> select (icmp Pred' X, C2), X, C2
1039 /// Note: if C1 != C2, this will change the icmp constant to the existing
1040 /// constant operand of the select.
canonicalizeMinMaxWithConstant(SelectInst & Sel,ICmpInst & Cmp,InstCombinerImpl & IC)1041 static Instruction *canonicalizeMinMaxWithConstant(SelectInst &Sel,
1042 ICmpInst &Cmp,
1043 InstCombinerImpl &IC) {
1044 if (!Cmp.hasOneUse() || !isa<Constant>(Cmp.getOperand(1)))
1045 return nullptr;
1046
1047 // Canonicalize the compare predicate based on whether we have min or max.
1048 Value *LHS, *RHS;
1049 SelectPatternResult SPR = matchSelectPattern(&Sel, LHS, RHS);
1050 if (!SelectPatternResult::isMinOrMax(SPR.Flavor))
1051 return nullptr;
1052
1053 // Is this already canonical?
1054 ICmpInst::Predicate CanonicalPred = getMinMaxPred(SPR.Flavor);
1055 if (Cmp.getOperand(0) == LHS && Cmp.getOperand(1) == RHS &&
1056 Cmp.getPredicate() == CanonicalPred)
1057 return nullptr;
1058
1059 // Bail out on unsimplified X-0 operand (due to some worklist management bug),
1060 // as this may cause an infinite combine loop. Let the sub be folded first.
1061 if (match(LHS, m_Sub(m_Value(), m_Zero())) ||
1062 match(RHS, m_Sub(m_Value(), m_Zero())))
1063 return nullptr;
1064
1065 // Create the canonical compare and plug it into the select.
1066 IC.replaceOperand(Sel, 0, IC.Builder.CreateICmp(CanonicalPred, LHS, RHS));
1067
1068 // If the select operands did not change, we're done.
1069 if (Sel.getTrueValue() == LHS && Sel.getFalseValue() == RHS)
1070 return &Sel;
1071
1072 // If we are swapping the select operands, swap the metadata too.
1073 assert(Sel.getTrueValue() == RHS && Sel.getFalseValue() == LHS &&
1074 "Unexpected results from matchSelectPattern");
1075 Sel.swapValues();
1076 Sel.swapProfMetadata();
1077 return &Sel;
1078 }
1079
canonicalizeAbsNabs(SelectInst & Sel,ICmpInst & Cmp,InstCombinerImpl & IC)1080 static Instruction *canonicalizeAbsNabs(SelectInst &Sel, ICmpInst &Cmp,
1081 InstCombinerImpl &IC) {
1082 if (!Cmp.hasOneUse() || !isa<Constant>(Cmp.getOperand(1)))
1083 return nullptr;
1084
1085 Value *LHS, *RHS;
1086 SelectPatternFlavor SPF = matchSelectPattern(&Sel, LHS, RHS).Flavor;
1087 if (SPF != SelectPatternFlavor::SPF_ABS &&
1088 SPF != SelectPatternFlavor::SPF_NABS)
1089 return nullptr;
1090
1091 // Note that NSW flag can only be propagated for normal, non-negated abs!
1092 bool IntMinIsPoison = SPF == SelectPatternFlavor::SPF_ABS &&
1093 match(RHS, m_NSWNeg(m_Specific(LHS)));
1094 Constant *IntMinIsPoisonC =
1095 ConstantInt::get(Type::getInt1Ty(Sel.getContext()), IntMinIsPoison);
1096 Instruction *Abs =
1097 IC.Builder.CreateBinaryIntrinsic(Intrinsic::abs, LHS, IntMinIsPoisonC);
1098
1099 if (SPF == SelectPatternFlavor::SPF_NABS)
1100 return BinaryOperator::CreateNeg(Abs); // Always without NSW flag!
1101
1102 return IC.replaceInstUsesWith(Sel, Abs);
1103 }
1104
1105 /// If we have a select with an equality comparison, then we know the value in
1106 /// one of the arms of the select. See if substituting this value into an arm
1107 /// and simplifying the result yields the same value as the other arm.
1108 ///
1109 /// To make this transform safe, we must drop poison-generating flags
1110 /// (nsw, etc) if we simplified to a binop because the select may be guarding
1111 /// that poison from propagating. If the existing binop already had no
1112 /// poison-generating flags, then this transform can be done by instsimplify.
1113 ///
1114 /// Consider:
1115 /// %cmp = icmp eq i32 %x, 2147483647
1116 /// %add = add nsw i32 %x, 1
1117 /// %sel = select i1 %cmp, i32 -2147483648, i32 %add
1118 ///
1119 /// We can't replace %sel with %add unless we strip away the flags.
1120 /// TODO: Wrapping flags could be preserved in some cases with better analysis.
foldSelectValueEquivalence(SelectInst & Sel,ICmpInst & Cmp)1121 Instruction *InstCombinerImpl::foldSelectValueEquivalence(SelectInst &Sel,
1122 ICmpInst &Cmp) {
1123 // Value equivalence substitution requires an all-or-nothing replacement.
1124 // It does not make sense for a vector compare where each lane is chosen
1125 // independently.
1126 if (!Cmp.isEquality() || Cmp.getType()->isVectorTy())
1127 return nullptr;
1128
1129 // Canonicalize the pattern to ICMP_EQ by swapping the select operands.
1130 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
1131 bool Swapped = false;
1132 if (Cmp.getPredicate() == ICmpInst::ICMP_NE) {
1133 std::swap(TrueVal, FalseVal);
1134 Swapped = true;
1135 }
1136
1137 // In X == Y ? f(X) : Z, try to evaluate f(Y) and replace the operand.
1138 // Make sure Y cannot be undef though, as we might pick different values for
1139 // undef in the icmp and in f(Y). Additionally, take care to avoid replacing
1140 // X == Y ? X : Z with X == Y ? Y : Z, as that would lead to an infinite
1141 // replacement cycle.
1142 Value *CmpLHS = Cmp.getOperand(0), *CmpRHS = Cmp.getOperand(1);
1143 if (TrueVal != CmpLHS &&
1144 isGuaranteedNotToBeUndefOrPoison(CmpRHS, SQ.AC, &Sel, &DT)) {
1145 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, SQ,
1146 /* AllowRefinement */ true))
1147 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1148
1149 // Even if TrueVal does not simplify, we can directly replace a use of
1150 // CmpLHS with CmpRHS, as long as the instruction is not used anywhere
1151 // else and is safe to speculatively execute (we may end up executing it
1152 // with different operands, which should not cause side-effects or trigger
1153 // undefined behavior). Only do this if CmpRHS is a constant, as
1154 // profitability is not clear for other cases.
1155 // FIXME: The replacement could be performed recursively.
1156 if (match(CmpRHS, m_ImmConstant()) && !match(CmpLHS, m_ImmConstant()))
1157 if (auto *I = dyn_cast<Instruction>(TrueVal))
1158 if (I->hasOneUse() && isSafeToSpeculativelyExecute(I))
1159 for (Use &U : I->operands())
1160 if (U == CmpLHS) {
1161 replaceUse(U, CmpRHS);
1162 return &Sel;
1163 }
1164 }
1165 if (TrueVal != CmpRHS &&
1166 isGuaranteedNotToBeUndefOrPoison(CmpLHS, SQ.AC, &Sel, &DT))
1167 if (Value *V = simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, SQ,
1168 /* AllowRefinement */ true))
1169 return replaceOperand(Sel, Swapped ? 2 : 1, V);
1170
1171 auto *FalseInst = dyn_cast<Instruction>(FalseVal);
1172 if (!FalseInst)
1173 return nullptr;
1174
1175 // InstSimplify already performed this fold if it was possible subject to
1176 // current poison-generating flags. Try the transform again with
1177 // poison-generating flags temporarily dropped.
1178 bool WasNUW = false, WasNSW = false, WasExact = false, WasInBounds = false;
1179 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(FalseVal)) {
1180 WasNUW = OBO->hasNoUnsignedWrap();
1181 WasNSW = OBO->hasNoSignedWrap();
1182 FalseInst->setHasNoUnsignedWrap(false);
1183 FalseInst->setHasNoSignedWrap(false);
1184 }
1185 if (auto *PEO = dyn_cast<PossiblyExactOperator>(FalseVal)) {
1186 WasExact = PEO->isExact();
1187 FalseInst->setIsExact(false);
1188 }
1189 if (auto *GEP = dyn_cast<GetElementPtrInst>(FalseVal)) {
1190 WasInBounds = GEP->isInBounds();
1191 GEP->setIsInBounds(false);
1192 }
1193
1194 // Try each equivalence substitution possibility.
1195 // We have an 'EQ' comparison, so the select's false value will propagate.
1196 // Example:
1197 // (X == 42) ? 43 : (X + 1) --> (X == 42) ? (X + 1) : (X + 1) --> X + 1
1198 if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, SQ,
1199 /* AllowRefinement */ false) == TrueVal ||
1200 simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, SQ,
1201 /* AllowRefinement */ false) == TrueVal) {
1202 return replaceInstUsesWith(Sel, FalseVal);
1203 }
1204
1205 // Restore poison-generating flags if the transform did not apply.
1206 if (WasNUW)
1207 FalseInst->setHasNoUnsignedWrap();
1208 if (WasNSW)
1209 FalseInst->setHasNoSignedWrap();
1210 if (WasExact)
1211 FalseInst->setIsExact();
1212 if (WasInBounds)
1213 cast<GetElementPtrInst>(FalseInst)->setIsInBounds();
1214
1215 return nullptr;
1216 }
1217
1218 // See if this is a pattern like:
1219 // %old_cmp1 = icmp slt i32 %x, C2
1220 // %old_replacement = select i1 %old_cmp1, i32 %target_low, i32 %target_high
1221 // %old_x_offseted = add i32 %x, C1
1222 // %old_cmp0 = icmp ult i32 %old_x_offseted, C0
1223 // %r = select i1 %old_cmp0, i32 %x, i32 %old_replacement
1224 // This can be rewritten as more canonical pattern:
1225 // %new_cmp1 = icmp slt i32 %x, -C1
1226 // %new_cmp2 = icmp sge i32 %x, C0-C1
1227 // %new_clamped_low = select i1 %new_cmp1, i32 %target_low, i32 %x
1228 // %r = select i1 %new_cmp2, i32 %target_high, i32 %new_clamped_low
1229 // Iff -C1 s<= C2 s<= C0-C1
1230 // Also ULT predicate can also be UGT iff C0 != -1 (+invert result)
1231 // SLT predicate can also be SGT iff C2 != INT_MAX (+invert res.)
canonicalizeClampLike(SelectInst & Sel0,ICmpInst & Cmp0,InstCombiner::BuilderTy & Builder)1232 static Instruction *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
1233 InstCombiner::BuilderTy &Builder) {
1234 Value *X = Sel0.getTrueValue();
1235 Value *Sel1 = Sel0.getFalseValue();
1236
1237 // First match the condition of the outermost select.
1238 // Said condition must be one-use.
1239 if (!Cmp0.hasOneUse())
1240 return nullptr;
1241 Value *Cmp00 = Cmp0.getOperand(0);
1242 Constant *C0;
1243 if (!match(Cmp0.getOperand(1),
1244 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0))))
1245 return nullptr;
1246 // Canonicalize Cmp0 into the form we expect.
1247 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1248 switch (Cmp0.getPredicate()) {
1249 case ICmpInst::Predicate::ICMP_ULT:
1250 break; // Great!
1251 case ICmpInst::Predicate::ICMP_ULE:
1252 // We'd have to increment C0 by one, and for that it must not have all-ones
1253 // element, but then it would have been canonicalized to 'ult' before
1254 // we get here. So we can't do anything useful with 'ule'.
1255 return nullptr;
1256 case ICmpInst::Predicate::ICMP_UGT:
1257 // We want to canonicalize it to 'ult', so we'll need to increment C0,
1258 // which again means it must not have any all-ones elements.
1259 if (!match(C0,
1260 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE,
1261 APInt::getAllOnesValue(
1262 C0->getType()->getScalarSizeInBits()))))
1263 return nullptr; // Can't do, have all-ones element[s].
1264 C0 = InstCombiner::AddOne(C0);
1265 std::swap(X, Sel1);
1266 break;
1267 case ICmpInst::Predicate::ICMP_UGE:
1268 // The only way we'd get this predicate if this `icmp` has extra uses,
1269 // but then we won't be able to do this fold.
1270 return nullptr;
1271 default:
1272 return nullptr; // Unknown predicate.
1273 }
1274
1275 // Now that we've canonicalized the ICmp, we know the X we expect;
1276 // the select in other hand should be one-use.
1277 if (!Sel1->hasOneUse())
1278 return nullptr;
1279
1280 // We now can finish matching the condition of the outermost select:
1281 // it should either be the X itself, or an addition of some constant to X.
1282 Constant *C1;
1283 if (Cmp00 == X)
1284 C1 = ConstantInt::getNullValue(Sel0.getType());
1285 else if (!match(Cmp00,
1286 m_Add(m_Specific(X),
1287 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C1)))))
1288 return nullptr;
1289
1290 Value *Cmp1;
1291 ICmpInst::Predicate Pred1;
1292 Constant *C2;
1293 Value *ReplacementLow, *ReplacementHigh;
1294 if (!match(Sel1, m_Select(m_Value(Cmp1), m_Value(ReplacementLow),
1295 m_Value(ReplacementHigh))) ||
1296 !match(Cmp1,
1297 m_ICmp(Pred1, m_Specific(X),
1298 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C2)))))
1299 return nullptr;
1300
1301 if (!Cmp1->hasOneUse() && (Cmp00 == X || !Cmp00->hasOneUse()))
1302 return nullptr; // Not enough one-use instructions for the fold.
1303 // FIXME: this restriction could be relaxed if Cmp1 can be reused as one of
1304 // two comparisons we'll need to build.
1305
1306 // Canonicalize Cmp1 into the form we expect.
1307 // FIXME: we shouldn't care about lanes that are 'undef' in the end?
1308 switch (Pred1) {
1309 case ICmpInst::Predicate::ICMP_SLT:
1310 break;
1311 case ICmpInst::Predicate::ICMP_SLE:
1312 // We'd have to increment C2 by one, and for that it must not have signed
1313 // max element, but then it would have been canonicalized to 'slt' before
1314 // we get here. So we can't do anything useful with 'sle'.
1315 return nullptr;
1316 case ICmpInst::Predicate::ICMP_SGT:
1317 // We want to canonicalize it to 'slt', so we'll need to increment C2,
1318 // which again means it must not have any signed max elements.
1319 if (!match(C2,
1320 m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE,
1321 APInt::getSignedMaxValue(
1322 C2->getType()->getScalarSizeInBits()))))
1323 return nullptr; // Can't do, have signed max element[s].
1324 C2 = InstCombiner::AddOne(C2);
1325 LLVM_FALLTHROUGH;
1326 case ICmpInst::Predicate::ICMP_SGE:
1327 // Also non-canonical, but here we don't need to change C2,
1328 // so we don't have any restrictions on C2, so we can just handle it.
1329 std::swap(ReplacementLow, ReplacementHigh);
1330 break;
1331 default:
1332 return nullptr; // Unknown predicate.
1333 }
1334
1335 // The thresholds of this clamp-like pattern.
1336 auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
1337 auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
1338
1339 // The fold has a precondition 1: C2 s>= ThresholdLow
1340 auto *Precond1 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SGE, C2,
1341 ThresholdLowIncl);
1342 if (!match(Precond1, m_One()))
1343 return nullptr;
1344 // The fold has a precondition 2: C2 s<= ThresholdHigh
1345 auto *Precond2 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SLE, C2,
1346 ThresholdHighExcl);
1347 if (!match(Precond2, m_One()))
1348 return nullptr;
1349
1350 // All good, finally emit the new pattern.
1351 Value *ShouldReplaceLow = Builder.CreateICmpSLT(X, ThresholdLowIncl);
1352 Value *ShouldReplaceHigh = Builder.CreateICmpSGE(X, ThresholdHighExcl);
1353 Value *MaybeReplacedLow =
1354 Builder.CreateSelect(ShouldReplaceLow, ReplacementLow, X);
1355 Instruction *MaybeReplacedHigh =
1356 SelectInst::Create(ShouldReplaceHigh, ReplacementHigh, MaybeReplacedLow);
1357
1358 return MaybeReplacedHigh;
1359 }
1360
1361 // If we have
1362 // %cmp = icmp [canonical predicate] i32 %x, C0
1363 // %r = select i1 %cmp, i32 %y, i32 C1
1364 // Where C0 != C1 and %x may be different from %y, see if the constant that we
1365 // will have if we flip the strictness of the predicate (i.e. without changing
1366 // the result) is identical to the C1 in select. If it matches we can change
1367 // original comparison to one with swapped predicate, reuse the constant,
1368 // and swap the hands of select.
1369 static Instruction *
tryToReuseConstantFromSelectInComparison(SelectInst & Sel,ICmpInst & Cmp,InstCombinerImpl & IC)1370 tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
1371 InstCombinerImpl &IC) {
1372 ICmpInst::Predicate Pred;
1373 Value *X;
1374 Constant *C0;
1375 if (!match(&Cmp, m_OneUse(m_ICmp(
1376 Pred, m_Value(X),
1377 m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0))))))
1378 return nullptr;
1379
1380 // If comparison predicate is non-relational, we won't be able to do anything.
1381 if (ICmpInst::isEquality(Pred))
1382 return nullptr;
1383
1384 // If comparison predicate is non-canonical, then we certainly won't be able
1385 // to make it canonical; canonicalizeCmpWithConstant() already tried.
1386 if (!InstCombiner::isCanonicalPredicate(Pred))
1387 return nullptr;
1388
1389 // If the [input] type of comparison and select type are different, lets abort
1390 // for now. We could try to compare constants with trunc/[zs]ext though.
1391 if (C0->getType() != Sel.getType())
1392 return nullptr;
1393
1394 // FIXME: are there any magic icmp predicate+constant pairs we must not touch?
1395
1396 Value *SelVal0, *SelVal1; // We do not care which one is from where.
1397 match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));
1398 // At least one of these values we are selecting between must be a constant
1399 // else we'll never succeed.
1400 if (!match(SelVal0, m_AnyIntegralConstant()) &&
1401 !match(SelVal1, m_AnyIntegralConstant()))
1402 return nullptr;
1403
1404 // Does this constant C match any of the `select` values?
1405 auto MatchesSelectValue = [SelVal0, SelVal1](Constant *C) {
1406 return C->isElementWiseEqual(SelVal0) || C->isElementWiseEqual(SelVal1);
1407 };
1408
1409 // If C0 *already* matches true/false value of select, we are done.
1410 if (MatchesSelectValue(C0))
1411 return nullptr;
1412
1413 // Check the constant we'd have with flipped-strictness predicate.
1414 auto FlippedStrictness =
1415 InstCombiner::getFlippedStrictnessPredicateAndConstant(Pred, C0);
1416 if (!FlippedStrictness)
1417 return nullptr;
1418
1419 // If said constant doesn't match either, then there is no hope,
1420 if (!MatchesSelectValue(FlippedStrictness->second))
1421 return nullptr;
1422
1423 // It matched! Lets insert the new comparison just before select.
1424 InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
1425 IC.Builder.SetInsertPoint(&Sel);
1426
1427 Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
1428 Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
1429 Cmp.getName() + ".inv");
1430 IC.replaceOperand(Sel, 0, NewCmp);
1431 Sel.swapValues();
1432 Sel.swapProfMetadata();
1433
1434 return &Sel;
1435 }
1436
1437 /// Visit a SelectInst that has an ICmpInst as its first operand.
foldSelectInstWithICmp(SelectInst & SI,ICmpInst * ICI)1438 Instruction *InstCombinerImpl::foldSelectInstWithICmp(SelectInst &SI,
1439 ICmpInst *ICI) {
1440 if (Instruction *NewSel = foldSelectValueEquivalence(SI, *ICI))
1441 return NewSel;
1442
1443 if (Instruction *NewSel = canonicalizeMinMaxWithConstant(SI, *ICI, *this))
1444 return NewSel;
1445
1446 if (Instruction *NewAbs = canonicalizeAbsNabs(SI, *ICI, *this))
1447 return NewAbs;
1448
1449 if (Instruction *NewAbs = canonicalizeClampLike(SI, *ICI, Builder))
1450 return NewAbs;
1451
1452 if (Instruction *NewSel =
1453 tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
1454 return NewSel;
1455
1456 bool Changed = adjustMinMax(SI, *ICI);
1457
1458 if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1459 return replaceInstUsesWith(SI, V);
1460
1461 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1462 Value *TrueVal = SI.getTrueValue();
1463 Value *FalseVal = SI.getFalseValue();
1464 ICmpInst::Predicate Pred = ICI->getPredicate();
1465 Value *CmpLHS = ICI->getOperand(0);
1466 Value *CmpRHS = ICI->getOperand(1);
1467 if (CmpRHS != CmpLHS && isa<Constant>(CmpRHS)) {
1468 if (CmpLHS == TrueVal && Pred == ICmpInst::ICMP_EQ) {
1469 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1470 SI.setOperand(1, CmpRHS);
1471 Changed = true;
1472 } else if (CmpLHS == FalseVal && Pred == ICmpInst::ICMP_NE) {
1473 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1474 SI.setOperand(2, CmpRHS);
1475 Changed = true;
1476 }
1477 }
1478
1479 // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1480 // decomposeBitTestICmp() might help.
1481 {
1482 unsigned BitWidth =
1483 DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1484 APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1485 Value *X;
1486 const APInt *Y, *C;
1487 bool TrueWhenUnset;
1488 bool IsBitTest = false;
1489 if (ICmpInst::isEquality(Pred) &&
1490 match(CmpLHS, m_And(m_Value(X), m_Power2(Y))) &&
1491 match(CmpRHS, m_Zero())) {
1492 IsBitTest = true;
1493 TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1494 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
1495 X = CmpLHS;
1496 Y = &MinSignedValue;
1497 IsBitTest = true;
1498 TrueWhenUnset = false;
1499 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
1500 X = CmpLHS;
1501 Y = &MinSignedValue;
1502 IsBitTest = true;
1503 TrueWhenUnset = true;
1504 }
1505 if (IsBitTest) {
1506 Value *V = nullptr;
1507 // (X & Y) == 0 ? X : X ^ Y --> X & ~Y
1508 if (TrueWhenUnset && TrueVal == X &&
1509 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1510 V = Builder.CreateAnd(X, ~(*Y));
1511 // (X & Y) != 0 ? X ^ Y : X --> X & ~Y
1512 else if (!TrueWhenUnset && FalseVal == X &&
1513 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1514 V = Builder.CreateAnd(X, ~(*Y));
1515 // (X & Y) == 0 ? X ^ Y : X --> X | Y
1516 else if (TrueWhenUnset && FalseVal == X &&
1517 match(TrueVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1518 V = Builder.CreateOr(X, *Y);
1519 // (X & Y) != 0 ? X : X ^ Y --> X | Y
1520 else if (!TrueWhenUnset && TrueVal == X &&
1521 match(FalseVal, m_Xor(m_Specific(X), m_APInt(C))) && *Y == *C)
1522 V = Builder.CreateOr(X, *Y);
1523
1524 if (V)
1525 return replaceInstUsesWith(SI, V);
1526 }
1527 }
1528
1529 if (Instruction *V =
1530 foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1531 return V;
1532
1533 if (Instruction *V = foldSelectCtlzToCttz(ICI, TrueVal, FalseVal, Builder))
1534 return V;
1535
1536 if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
1537 return replaceInstUsesWith(SI, V);
1538
1539 if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
1540 return replaceInstUsesWith(SI, V);
1541
1542 if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1543 return replaceInstUsesWith(SI, V);
1544
1545 if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1546 return replaceInstUsesWith(SI, V);
1547
1548 if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))
1549 return replaceInstUsesWith(SI, V);
1550
1551 return Changed ? &SI : nullptr;
1552 }
1553
1554 /// SI is a select whose condition is a PHI node (but the two may be in
1555 /// different blocks). See if the true/false values (V) are live in all of the
1556 /// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1557 ///
1558 /// X = phi [ C1, BB1], [C2, BB2]
1559 /// Y = add
1560 /// Z = select X, Y, 0
1561 ///
1562 /// because Y is not live in BB1/BB2.
canSelectOperandBeMappingIntoPredBlock(const Value * V,const SelectInst & SI)1563 static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1564 const SelectInst &SI) {
1565 // If the value is a non-instruction value like a constant or argument, it
1566 // can always be mapped.
1567 const Instruction *I = dyn_cast<Instruction>(V);
1568 if (!I) return true;
1569
1570 // If V is a PHI node defined in the same block as the condition PHI, we can
1571 // map the arguments.
1572 const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1573
1574 if (const PHINode *VP = dyn_cast<PHINode>(I))
1575 if (VP->getParent() == CondPHI->getParent())
1576 return true;
1577
1578 // Otherwise, if the PHI and select are defined in the same block and if V is
1579 // defined in a different block, then we can transform it.
1580 if (SI.getParent() == CondPHI->getParent() &&
1581 I->getParent() != CondPHI->getParent())
1582 return true;
1583
1584 // Otherwise we have a 'hard' case and we can't tell without doing more
1585 // detailed dominator based analysis, punt.
1586 return false;
1587 }
1588
1589 /// We have an SPF (e.g. a min or max) of an SPF of the form:
1590 /// SPF2(SPF1(A, B), C)
foldSPFofSPF(Instruction * Inner,SelectPatternFlavor SPF1,Value * A,Value * B,Instruction & Outer,SelectPatternFlavor SPF2,Value * C)1591 Instruction *InstCombinerImpl::foldSPFofSPF(Instruction *Inner,
1592 SelectPatternFlavor SPF1, Value *A,
1593 Value *B, Instruction &Outer,
1594 SelectPatternFlavor SPF2,
1595 Value *C) {
1596 if (Outer.getType() != Inner->getType())
1597 return nullptr;
1598
1599 if (C == A || C == B) {
1600 // MAX(MAX(A, B), B) -> MAX(A, B)
1601 // MIN(MIN(a, b), a) -> MIN(a, b)
1602 // TODO: This could be done in instsimplify.
1603 if (SPF1 == SPF2 && SelectPatternResult::isMinOrMax(SPF1))
1604 return replaceInstUsesWith(Outer, Inner);
1605
1606 // MAX(MIN(a, b), a) -> a
1607 // MIN(MAX(a, b), a) -> a
1608 // TODO: This could be done in instsimplify.
1609 if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) ||
1610 (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) ||
1611 (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) ||
1612 (SPF1 == SPF_UMAX && SPF2 == SPF_UMIN))
1613 return replaceInstUsesWith(Outer, C);
1614 }
1615
1616 if (SPF1 == SPF2) {
1617 const APInt *CB, *CC;
1618 if (match(B, m_APInt(CB)) && match(C, m_APInt(CC))) {
1619 // MIN(MIN(A, 23), 97) -> MIN(A, 23)
1620 // MAX(MAX(A, 97), 23) -> MAX(A, 97)
1621 // TODO: This could be done in instsimplify.
1622 if ((SPF1 == SPF_UMIN && CB->ule(*CC)) ||
1623 (SPF1 == SPF_SMIN && CB->sle(*CC)) ||
1624 (SPF1 == SPF_UMAX && CB->uge(*CC)) ||
1625 (SPF1 == SPF_SMAX && CB->sge(*CC)))
1626 return replaceInstUsesWith(Outer, Inner);
1627
1628 // MIN(MIN(A, 97), 23) -> MIN(A, 23)
1629 // MAX(MAX(A, 23), 97) -> MAX(A, 97)
1630 if ((SPF1 == SPF_UMIN && CB->ugt(*CC)) ||
1631 (SPF1 == SPF_SMIN && CB->sgt(*CC)) ||
1632 (SPF1 == SPF_UMAX && CB->ult(*CC)) ||
1633 (SPF1 == SPF_SMAX && CB->slt(*CC))) {
1634 Outer.replaceUsesOfWith(Inner, A);
1635 return &Outer;
1636 }
1637 }
1638 }
1639
1640 // max(max(A, B), min(A, B)) --> max(A, B)
1641 // min(min(A, B), max(A, B)) --> min(A, B)
1642 // TODO: This could be done in instsimplify.
1643 if (SPF1 == SPF2 &&
1644 ((SPF1 == SPF_UMIN && match(C, m_c_UMax(m_Specific(A), m_Specific(B)))) ||
1645 (SPF1 == SPF_SMIN && match(C, m_c_SMax(m_Specific(A), m_Specific(B)))) ||
1646 (SPF1 == SPF_UMAX && match(C, m_c_UMin(m_Specific(A), m_Specific(B)))) ||
1647 (SPF1 == SPF_SMAX && match(C, m_c_SMin(m_Specific(A), m_Specific(B))))))
1648 return replaceInstUsesWith(Outer, Inner);
1649
1650 // ABS(ABS(X)) -> ABS(X)
1651 // NABS(NABS(X)) -> NABS(X)
1652 // TODO: This could be done in instsimplify.
1653 if (SPF1 == SPF2 && (SPF1 == SPF_ABS || SPF1 == SPF_NABS)) {
1654 return replaceInstUsesWith(Outer, Inner);
1655 }
1656
1657 // ABS(NABS(X)) -> ABS(X)
1658 // NABS(ABS(X)) -> NABS(X)
1659 if ((SPF1 == SPF_ABS && SPF2 == SPF_NABS) ||
1660 (SPF1 == SPF_NABS && SPF2 == SPF_ABS)) {
1661 SelectInst *SI = cast<SelectInst>(Inner);
1662 Value *NewSI =
1663 Builder.CreateSelect(SI->getCondition(), SI->getFalseValue(),
1664 SI->getTrueValue(), SI->getName(), SI);
1665 return replaceInstUsesWith(Outer, NewSI);
1666 }
1667
1668 auto IsFreeOrProfitableToInvert =
1669 [&](Value *V, Value *&NotV, bool &ElidesXor) {
1670 if (match(V, m_Not(m_Value(NotV)))) {
1671 // If V has at most 2 uses then we can get rid of the xor operation
1672 // entirely.
1673 ElidesXor |= !V->hasNUsesOrMore(3);
1674 return true;
1675 }
1676
1677 if (isFreeToInvert(V, !V->hasNUsesOrMore(3))) {
1678 NotV = nullptr;
1679 return true;
1680 }
1681
1682 return false;
1683 };
1684
1685 Value *NotA, *NotB, *NotC;
1686 bool ElidesXor = false;
1687
1688 // MIN(MIN(~A, ~B), ~C) == ~MAX(MAX(A, B), C)
1689 // MIN(MAX(~A, ~B), ~C) == ~MAX(MIN(A, B), C)
1690 // MAX(MIN(~A, ~B), ~C) == ~MIN(MAX(A, B), C)
1691 // MAX(MAX(~A, ~B), ~C) == ~MIN(MIN(A, B), C)
1692 //
1693 // This transform is performance neutral if we can elide at least one xor from
1694 // the set of three operands, since we'll be tacking on an xor at the very
1695 // end.
1696 if (SelectPatternResult::isMinOrMax(SPF1) &&
1697 SelectPatternResult::isMinOrMax(SPF2) &&
1698 IsFreeOrProfitableToInvert(A, NotA, ElidesXor) &&
1699 IsFreeOrProfitableToInvert(B, NotB, ElidesXor) &&
1700 IsFreeOrProfitableToInvert(C, NotC, ElidesXor) && ElidesXor) {
1701 if (!NotA)
1702 NotA = Builder.CreateNot(A);
1703 if (!NotB)
1704 NotB = Builder.CreateNot(B);
1705 if (!NotC)
1706 NotC = Builder.CreateNot(C);
1707
1708 Value *NewInner = createMinMax(Builder, getInverseMinMaxFlavor(SPF1), NotA,
1709 NotB);
1710 Value *NewOuter = Builder.CreateNot(
1711 createMinMax(Builder, getInverseMinMaxFlavor(SPF2), NewInner, NotC));
1712 return replaceInstUsesWith(Outer, NewOuter);
1713 }
1714
1715 return nullptr;
1716 }
1717
1718 /// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1719 /// This is even legal for FP.
foldAddSubSelect(SelectInst & SI,InstCombiner::BuilderTy & Builder)1720 static Instruction *foldAddSubSelect(SelectInst &SI,
1721 InstCombiner::BuilderTy &Builder) {
1722 Value *CondVal = SI.getCondition();
1723 Value *TrueVal = SI.getTrueValue();
1724 Value *FalseVal = SI.getFalseValue();
1725 auto *TI = dyn_cast<Instruction>(TrueVal);
1726 auto *FI = dyn_cast<Instruction>(FalseVal);
1727 if (!TI || !FI || !TI->hasOneUse() || !FI->hasOneUse())
1728 return nullptr;
1729
1730 Instruction *AddOp = nullptr, *SubOp = nullptr;
1731 if ((TI->getOpcode() == Instruction::Sub &&
1732 FI->getOpcode() == Instruction::Add) ||
1733 (TI->getOpcode() == Instruction::FSub &&
1734 FI->getOpcode() == Instruction::FAdd)) {
1735 AddOp = FI;
1736 SubOp = TI;
1737 } else if ((FI->getOpcode() == Instruction::Sub &&
1738 TI->getOpcode() == Instruction::Add) ||
1739 (FI->getOpcode() == Instruction::FSub &&
1740 TI->getOpcode() == Instruction::FAdd)) {
1741 AddOp = TI;
1742 SubOp = FI;
1743 }
1744
1745 if (AddOp) {
1746 Value *OtherAddOp = nullptr;
1747 if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1748 OtherAddOp = AddOp->getOperand(1);
1749 } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1750 OtherAddOp = AddOp->getOperand(0);
1751 }
1752
1753 if (OtherAddOp) {
1754 // So at this point we know we have (Y -> OtherAddOp):
1755 // select C, (add X, Y), (sub X, Z)
1756 Value *NegVal; // Compute -Z
1757 if (SI.getType()->isFPOrFPVectorTy()) {
1758 NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1759 if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1760 FastMathFlags Flags = AddOp->getFastMathFlags();
1761 Flags &= SubOp->getFastMathFlags();
1762 NegInst->setFastMathFlags(Flags);
1763 }
1764 } else {
1765 NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1766 }
1767
1768 Value *NewTrueOp = OtherAddOp;
1769 Value *NewFalseOp = NegVal;
1770 if (AddOp != TI)
1771 std::swap(NewTrueOp, NewFalseOp);
1772 Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1773 SI.getName() + ".p", &SI);
1774
1775 if (SI.getType()->isFPOrFPVectorTy()) {
1776 Instruction *RI =
1777 BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1778
1779 FastMathFlags Flags = AddOp->getFastMathFlags();
1780 Flags &= SubOp->getFastMathFlags();
1781 RI->setFastMathFlags(Flags);
1782 return RI;
1783 } else
1784 return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1785 }
1786 }
1787 return nullptr;
1788 }
1789
1790 /// Turn X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1791 /// And X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1792 /// Along with a number of patterns similar to:
1793 /// X + Y overflows ? (X < 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1794 /// X - Y overflows ? (X > 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1795 static Instruction *
foldOverflowingAddSubSelect(SelectInst & SI,InstCombiner::BuilderTy & Builder)1796 foldOverflowingAddSubSelect(SelectInst &SI, InstCombiner::BuilderTy &Builder) {
1797 Value *CondVal = SI.getCondition();
1798 Value *TrueVal = SI.getTrueValue();
1799 Value *FalseVal = SI.getFalseValue();
1800
1801 WithOverflowInst *II;
1802 if (!match(CondVal, m_ExtractValue<1>(m_WithOverflowInst(II))) ||
1803 !match(FalseVal, m_ExtractValue<0>(m_Specific(II))))
1804 return nullptr;
1805
1806 Value *X = II->getLHS();
1807 Value *Y = II->getRHS();
1808
1809 auto IsSignedSaturateLimit = [&](Value *Limit, bool IsAdd) {
1810 Type *Ty = Limit->getType();
1811
1812 ICmpInst::Predicate Pred;
1813 Value *TrueVal, *FalseVal, *Op;
1814 const APInt *C;
1815 if (!match(Limit, m_Select(m_ICmp(Pred, m_Value(Op), m_APInt(C)),
1816 m_Value(TrueVal), m_Value(FalseVal))))
1817 return false;
1818
1819 auto IsZeroOrOne = [](const APInt &C) {
1820 return C.isNullValue() || C.isOneValue();
1821 };
1822 auto IsMinMax = [&](Value *Min, Value *Max) {
1823 APInt MinVal = APInt::getSignedMinValue(Ty->getScalarSizeInBits());
1824 APInt MaxVal = APInt::getSignedMaxValue(Ty->getScalarSizeInBits());
1825 return match(Min, m_SpecificInt(MinVal)) &&
1826 match(Max, m_SpecificInt(MaxVal));
1827 };
1828
1829 if (Op != X && Op != Y)
1830 return false;
1831
1832 if (IsAdd) {
1833 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1834 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1835 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1836 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1837 if (Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1838 IsMinMax(TrueVal, FalseVal))
1839 return true;
1840 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1841 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1842 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1843 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1844 if (Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1845 IsMinMax(FalseVal, TrueVal))
1846 return true;
1847 } else {
1848 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1849 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1850 if (Op == X && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C + 1) &&
1851 IsMinMax(TrueVal, FalseVal))
1852 return true;
1853 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1854 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1855 if (Op == X && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 2) &&
1856 IsMinMax(FalseVal, TrueVal))
1857 return true;
1858 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1859 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1860 if (Op == Y && Pred == ICmpInst::ICMP_SLT && IsZeroOrOne(*C) &&
1861 IsMinMax(FalseVal, TrueVal))
1862 return true;
1863 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1864 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1865 if (Op == Y && Pred == ICmpInst::ICMP_SGT && IsZeroOrOne(*C + 1) &&
1866 IsMinMax(TrueVal, FalseVal))
1867 return true;
1868 }
1869
1870 return false;
1871 };
1872
1873 Intrinsic::ID NewIntrinsicID;
1874 if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow &&
1875 match(TrueVal, m_AllOnes()))
1876 // X + Y overflows ? -1 : X + Y -> uadd_sat X, Y
1877 NewIntrinsicID = Intrinsic::uadd_sat;
1878 else if (II->getIntrinsicID() == Intrinsic::usub_with_overflow &&
1879 match(TrueVal, m_Zero()))
1880 // X - Y overflows ? 0 : X - Y -> usub_sat X, Y
1881 NewIntrinsicID = Intrinsic::usub_sat;
1882 else if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow &&
1883 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/true))
1884 // X + Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1885 // X + Y overflows ? (X <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1886 // X + Y overflows ? (X >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1887 // X + Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1888 // X + Y overflows ? (Y <s 0 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1889 // X + Y overflows ? (Y <s 1 ? INTMIN : INTMAX) : X + Y --> sadd_sat X, Y
1890 // X + Y overflows ? (Y >s 0 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1891 // X + Y overflows ? (Y >s -1 ? INTMAX : INTMIN) : X + Y --> sadd_sat X, Y
1892 NewIntrinsicID = Intrinsic::sadd_sat;
1893 else if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow &&
1894 IsSignedSaturateLimit(TrueVal, /*IsAdd=*/false))
1895 // X - Y overflows ? (X <s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1896 // X - Y overflows ? (X <s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1897 // X - Y overflows ? (X >s -1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1898 // X - Y overflows ? (X >s -2 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1899 // X - Y overflows ? (Y <s 0 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1900 // X - Y overflows ? (Y <s 1 ? INTMAX : INTMIN) : X - Y --> ssub_sat X, Y
1901 // X - Y overflows ? (Y >s 0 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1902 // X - Y overflows ? (Y >s -1 ? INTMIN : INTMAX) : X - Y --> ssub_sat X, Y
1903 NewIntrinsicID = Intrinsic::ssub_sat;
1904 else
1905 return nullptr;
1906
1907 Function *F =
1908 Intrinsic::getDeclaration(SI.getModule(), NewIntrinsicID, SI.getType());
1909 return CallInst::Create(F, {X, Y});
1910 }
1911
foldSelectExtConst(SelectInst & Sel)1912 Instruction *InstCombinerImpl::foldSelectExtConst(SelectInst &Sel) {
1913 Constant *C;
1914 if (!match(Sel.getTrueValue(), m_Constant(C)) &&
1915 !match(Sel.getFalseValue(), m_Constant(C)))
1916 return nullptr;
1917
1918 Instruction *ExtInst;
1919 if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
1920 !match(Sel.getFalseValue(), m_Instruction(ExtInst)))
1921 return nullptr;
1922
1923 auto ExtOpcode = ExtInst->getOpcode();
1924 if (ExtOpcode != Instruction::ZExt && ExtOpcode != Instruction::SExt)
1925 return nullptr;
1926
1927 // If we are extending from a boolean type or if we can create a select that
1928 // has the same size operands as its condition, try to narrow the select.
1929 Value *X = ExtInst->getOperand(0);
1930 Type *SmallType = X->getType();
1931 Value *Cond = Sel.getCondition();
1932 auto *Cmp = dyn_cast<CmpInst>(Cond);
1933 if (!SmallType->isIntOrIntVectorTy(1) &&
1934 (!Cmp || Cmp->getOperand(0)->getType() != SmallType))
1935 return nullptr;
1936
1937 // If the constant is the same after truncation to the smaller type and
1938 // extension to the original type, we can narrow the select.
1939 Type *SelType = Sel.getType();
1940 Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
1941 Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
1942 if (ExtC == C && ExtInst->hasOneUse()) {
1943 Value *TruncCVal = cast<Value>(TruncC);
1944 if (ExtInst == Sel.getFalseValue())
1945 std::swap(X, TruncCVal);
1946
1947 // select Cond, (ext X), C --> ext(select Cond, X, C')
1948 // select Cond, C, (ext X) --> ext(select Cond, C', X)
1949 Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
1950 return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
1951 }
1952
1953 // If one arm of the select is the extend of the condition, replace that arm
1954 // with the extension of the appropriate known bool value.
1955 if (Cond == X) {
1956 if (ExtInst == Sel.getTrueValue()) {
1957 // select X, (sext X), C --> select X, -1, C
1958 // select X, (zext X), C --> select X, 1, C
1959 Constant *One = ConstantInt::getTrue(SmallType);
1960 Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
1961 return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
1962 } else {
1963 // select X, C, (sext X) --> select X, C, 0
1964 // select X, C, (zext X) --> select X, C, 0
1965 Constant *Zero = ConstantInt::getNullValue(SelType);
1966 return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
1967 }
1968 }
1969
1970 return nullptr;
1971 }
1972
1973 /// Try to transform a vector select with a constant condition vector into a
1974 /// shuffle for easier combining with other shuffles and insert/extract.
canonicalizeSelectToShuffle(SelectInst & SI)1975 static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
1976 Value *CondVal = SI.getCondition();
1977 Constant *CondC;
1978 auto *CondValTy = dyn_cast<FixedVectorType>(CondVal->getType());
1979 if (!CondValTy || !match(CondVal, m_Constant(CondC)))
1980 return nullptr;
1981
1982 unsigned NumElts = CondValTy->getNumElements();
1983 SmallVector<int, 16> Mask;
1984 Mask.reserve(NumElts);
1985 for (unsigned i = 0; i != NumElts; ++i) {
1986 Constant *Elt = CondC->getAggregateElement(i);
1987 if (!Elt)
1988 return nullptr;
1989
1990 if (Elt->isOneValue()) {
1991 // If the select condition element is true, choose from the 1st vector.
1992 Mask.push_back(i);
1993 } else if (Elt->isNullValue()) {
1994 // If the select condition element is false, choose from the 2nd vector.
1995 Mask.push_back(i + NumElts);
1996 } else if (isa<UndefValue>(Elt)) {
1997 // Undef in a select condition (choose one of the operands) does not mean
1998 // the same thing as undef in a shuffle mask (any value is acceptable), so
1999 // give up.
2000 return nullptr;
2001 } else {
2002 // Bail out on a constant expression.
2003 return nullptr;
2004 }
2005 }
2006
2007 return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(), Mask);
2008 }
2009
2010 /// If we have a select of vectors with a scalar condition, try to convert that
2011 /// to a vector select by splatting the condition. A splat may get folded with
2012 /// other operations in IR and having all operands of a select be vector types
2013 /// is likely better for vector codegen.
canonicalizeScalarSelectOfVecs(SelectInst & Sel,InstCombinerImpl & IC)2014 static Instruction *canonicalizeScalarSelectOfVecs(SelectInst &Sel,
2015 InstCombinerImpl &IC) {
2016 auto *Ty = dyn_cast<VectorType>(Sel.getType());
2017 if (!Ty)
2018 return nullptr;
2019
2020 // We can replace a single-use extract with constant index.
2021 Value *Cond = Sel.getCondition();
2022 if (!match(Cond, m_OneUse(m_ExtractElt(m_Value(), m_ConstantInt()))))
2023 return nullptr;
2024
2025 // select (extelt V, Index), T, F --> select (splat V, Index), T, F
2026 // Splatting the extracted condition reduces code (we could directly create a
2027 // splat shuffle of the source vector to eliminate the intermediate step).
2028 return IC.replaceOperand(
2029 Sel, 0, IC.Builder.CreateVectorSplat(Ty->getElementCount(), Cond));
2030 }
2031
2032 /// Reuse bitcasted operands between a compare and select:
2033 /// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2034 /// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
foldSelectCmpBitcasts(SelectInst & Sel,InstCombiner::BuilderTy & Builder)2035 static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
2036 InstCombiner::BuilderTy &Builder) {
2037 Value *Cond = Sel.getCondition();
2038 Value *TVal = Sel.getTrueValue();
2039 Value *FVal = Sel.getFalseValue();
2040
2041 CmpInst::Predicate Pred;
2042 Value *A, *B;
2043 if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
2044 return nullptr;
2045
2046 // The select condition is a compare instruction. If the select's true/false
2047 // values are already the same as the compare operands, there's nothing to do.
2048 if (TVal == A || TVal == B || FVal == A || FVal == B)
2049 return nullptr;
2050
2051 Value *C, *D;
2052 if (!match(A, m_BitCast(m_Value(C))) || !match(B, m_BitCast(m_Value(D))))
2053 return nullptr;
2054
2055 // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
2056 Value *TSrc, *FSrc;
2057 if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
2058 !match(FVal, m_BitCast(m_Value(FSrc))))
2059 return nullptr;
2060
2061 // If the select true/false values are *different bitcasts* of the same source
2062 // operands, make the select operands the same as the compare operands and
2063 // cast the result. This is the canonical select form for min/max.
2064 Value *NewSel;
2065 if (TSrc == C && FSrc == D) {
2066 // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
2067 // bitcast (select (cmp A, B), A, B)
2068 NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
2069 } else if (TSrc == D && FSrc == C) {
2070 // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
2071 // bitcast (select (cmp A, B), B, A)
2072 NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
2073 } else {
2074 return nullptr;
2075 }
2076 return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
2077 }
2078
2079 /// Try to eliminate select instructions that test the returned flag of cmpxchg
2080 /// instructions.
2081 ///
2082 /// If a select instruction tests the returned flag of a cmpxchg instruction and
2083 /// selects between the returned value of the cmpxchg instruction its compare
2084 /// operand, the result of the select will always be equal to its false value.
2085 /// For example:
2086 ///
2087 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2088 /// %1 = extractvalue { i64, i1 } %0, 1
2089 /// %2 = extractvalue { i64, i1 } %0, 0
2090 /// %3 = select i1 %1, i64 %compare, i64 %2
2091 /// ret i64 %3
2092 ///
2093 /// The returned value of the cmpxchg instruction (%2) is the original value
2094 /// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
2095 /// must have been equal to %compare. Thus, the result of the select is always
2096 /// equal to %2, and the code can be simplified to:
2097 ///
2098 /// %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
2099 /// %1 = extractvalue { i64, i1 } %0, 0
2100 /// ret i64 %1
2101 ///
foldSelectCmpXchg(SelectInst & SI)2102 static Value *foldSelectCmpXchg(SelectInst &SI) {
2103 // A helper that determines if V is an extractvalue instruction whose
2104 // aggregate operand is a cmpxchg instruction and whose single index is equal
2105 // to I. If such conditions are true, the helper returns the cmpxchg
2106 // instruction; otherwise, a nullptr is returned.
2107 auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
2108 auto *Extract = dyn_cast<ExtractValueInst>(V);
2109 if (!Extract)
2110 return nullptr;
2111 if (Extract->getIndices()[0] != I)
2112 return nullptr;
2113 return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
2114 };
2115
2116 // If the select has a single user, and this user is a select instruction that
2117 // we can simplify, skip the cmpxchg simplification for now.
2118 if (SI.hasOneUse())
2119 if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
2120 if (Select->getCondition() == SI.getCondition())
2121 if (Select->getFalseValue() == SI.getTrueValue() ||
2122 Select->getTrueValue() == SI.getFalseValue())
2123 return nullptr;
2124
2125 // Ensure the select condition is the returned flag of a cmpxchg instruction.
2126 auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
2127 if (!CmpXchg)
2128 return nullptr;
2129
2130 // Check the true value case: The true value of the select is the returned
2131 // value of the same cmpxchg used by the condition, and the false value is the
2132 // cmpxchg instruction's compare operand.
2133 if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
2134 if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue())
2135 return SI.getFalseValue();
2136
2137 // Check the false value case: The false value of the select is the returned
2138 // value of the same cmpxchg used by the condition, and the true value is the
2139 // cmpxchg instruction's compare operand.
2140 if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
2141 if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue())
2142 return SI.getFalseValue();
2143
2144 return nullptr;
2145 }
2146
moveAddAfterMinMax(SelectPatternFlavor SPF,Value * X,Value * Y,InstCombiner::BuilderTy & Builder)2147 static Instruction *moveAddAfterMinMax(SelectPatternFlavor SPF, Value *X,
2148 Value *Y,
2149 InstCombiner::BuilderTy &Builder) {
2150 assert(SelectPatternResult::isMinOrMax(SPF) && "Expected min/max pattern");
2151 bool IsUnsigned = SPF == SelectPatternFlavor::SPF_UMIN ||
2152 SPF == SelectPatternFlavor::SPF_UMAX;
2153 // TODO: If InstSimplify could fold all cases where C2 <= C1, we could change
2154 // the constant value check to an assert.
2155 Value *A;
2156 const APInt *C1, *C2;
2157 if (IsUnsigned && match(X, m_NUWAdd(m_Value(A), m_APInt(C1))) &&
2158 match(Y, m_APInt(C2)) && C2->uge(*C1) && X->hasNUses(2)) {
2159 // umin (add nuw A, C1), C2 --> add nuw (umin A, C2 - C1), C1
2160 // umax (add nuw A, C1), C2 --> add nuw (umax A, C2 - C1), C1
2161 Value *NewMinMax = createMinMax(Builder, SPF, A,
2162 ConstantInt::get(X->getType(), *C2 - *C1));
2163 return BinaryOperator::CreateNUW(BinaryOperator::Add, NewMinMax,
2164 ConstantInt::get(X->getType(), *C1));
2165 }
2166
2167 if (!IsUnsigned && match(X, m_NSWAdd(m_Value(A), m_APInt(C1))) &&
2168 match(Y, m_APInt(C2)) && X->hasNUses(2)) {
2169 bool Overflow;
2170 APInt Diff = C2->ssub_ov(*C1, Overflow);
2171 if (!Overflow) {
2172 // smin (add nsw A, C1), C2 --> add nsw (smin A, C2 - C1), C1
2173 // smax (add nsw A, C1), C2 --> add nsw (smax A, C2 - C1), C1
2174 Value *NewMinMax = createMinMax(Builder, SPF, A,
2175 ConstantInt::get(X->getType(), Diff));
2176 return BinaryOperator::CreateNSW(BinaryOperator::Add, NewMinMax,
2177 ConstantInt::get(X->getType(), *C1));
2178 }
2179 }
2180
2181 return nullptr;
2182 }
2183
2184 /// Match a sadd_sat or ssub_sat which is using min/max to clamp the value.
matchSAddSubSat(SelectInst & MinMax1)2185 Instruction *InstCombinerImpl::matchSAddSubSat(SelectInst &MinMax1) {
2186 Type *Ty = MinMax1.getType();
2187
2188 // We are looking for a tree of:
2189 // max(INT_MIN, min(INT_MAX, add(sext(A), sext(B))))
2190 // Where the min and max could be reversed
2191 Instruction *MinMax2;
2192 BinaryOperator *AddSub;
2193 const APInt *MinValue, *MaxValue;
2194 if (match(&MinMax1, m_SMin(m_Instruction(MinMax2), m_APInt(MaxValue)))) {
2195 if (!match(MinMax2, m_SMax(m_BinOp(AddSub), m_APInt(MinValue))))
2196 return nullptr;
2197 } else if (match(&MinMax1,
2198 m_SMax(m_Instruction(MinMax2), m_APInt(MinValue)))) {
2199 if (!match(MinMax2, m_SMin(m_BinOp(AddSub), m_APInt(MaxValue))))
2200 return nullptr;
2201 } else
2202 return nullptr;
2203
2204 // Check that the constants clamp a saturate, and that the new type would be
2205 // sensible to convert to.
2206 if (!(*MaxValue + 1).isPowerOf2() || -*MinValue != *MaxValue + 1)
2207 return nullptr;
2208 // In what bitwidth can this be treated as saturating arithmetics?
2209 unsigned NewBitWidth = (*MaxValue + 1).logBase2() + 1;
2210 // FIXME: This isn't quite right for vectors, but using the scalar type is a
2211 // good first approximation for what should be done there.
2212 if (!shouldChangeType(Ty->getScalarType()->getIntegerBitWidth(), NewBitWidth))
2213 return nullptr;
2214
2215 // Also make sure that the number of uses is as expected. The "3"s are for the
2216 // the two items of min/max (the compare and the select).
2217 if (MinMax2->hasNUsesOrMore(3) || AddSub->hasNUsesOrMore(3))
2218 return nullptr;
2219
2220 // Create the new type (which can be a vector type)
2221 Type *NewTy = Ty->getWithNewBitWidth(NewBitWidth);
2222 // Match the two extends from the add/sub
2223 Value *A, *B;
2224 if(!match(AddSub, m_BinOp(m_SExt(m_Value(A)), m_SExt(m_Value(B)))))
2225 return nullptr;
2226 // And check the incoming values are of a type smaller than or equal to the
2227 // size of the saturation. Otherwise the higher bits can cause different
2228 // results.
2229 if (A->getType()->getScalarSizeInBits() > NewBitWidth ||
2230 B->getType()->getScalarSizeInBits() > NewBitWidth)
2231 return nullptr;
2232
2233 Intrinsic::ID IntrinsicID;
2234 if (AddSub->getOpcode() == Instruction::Add)
2235 IntrinsicID = Intrinsic::sadd_sat;
2236 else if (AddSub->getOpcode() == Instruction::Sub)
2237 IntrinsicID = Intrinsic::ssub_sat;
2238 else
2239 return nullptr;
2240
2241 // Finally create and return the sat intrinsic, truncated to the new type
2242 Function *F = Intrinsic::getDeclaration(MinMax1.getModule(), IntrinsicID, NewTy);
2243 Value *AT = Builder.CreateSExt(A, NewTy);
2244 Value *BT = Builder.CreateSExt(B, NewTy);
2245 Value *Sat = Builder.CreateCall(F, {AT, BT});
2246 return CastInst::Create(Instruction::SExt, Sat, Ty);
2247 }
2248
2249 /// Reduce a sequence of min/max with a common operand.
factorizeMinMaxTree(SelectPatternFlavor SPF,Value * LHS,Value * RHS,InstCombiner::BuilderTy & Builder)2250 static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS,
2251 Value *RHS,
2252 InstCombiner::BuilderTy &Builder) {
2253 assert(SelectPatternResult::isMinOrMax(SPF) && "Expected a min/max");
2254 // TODO: Allow FP min/max with nnan/nsz.
2255 if (!LHS->getType()->isIntOrIntVectorTy())
2256 return nullptr;
2257
2258 // Match 3 of the same min/max ops. Example: umin(umin(), umin()).
2259 Value *A, *B, *C, *D;
2260 SelectPatternResult L = matchSelectPattern(LHS, A, B);
2261 SelectPatternResult R = matchSelectPattern(RHS, C, D);
2262 if (SPF != L.Flavor || L.Flavor != R.Flavor)
2263 return nullptr;
2264
2265 // Look for a common operand. The use checks are different than usual because
2266 // a min/max pattern typically has 2 uses of each op: 1 by the cmp and 1 by
2267 // the select.
2268 Value *MinMaxOp = nullptr;
2269 Value *ThirdOp = nullptr;
2270 if (!LHS->hasNUsesOrMore(3) && RHS->hasNUsesOrMore(3)) {
2271 // If the LHS is only used in this chain and the RHS is used outside of it,
2272 // reuse the RHS min/max because that will eliminate the LHS.
2273 if (D == A || C == A) {
2274 // min(min(a, b), min(c, a)) --> min(min(c, a), b)
2275 // min(min(a, b), min(a, d)) --> min(min(a, d), b)
2276 MinMaxOp = RHS;
2277 ThirdOp = B;
2278 } else if (D == B || C == B) {
2279 // min(min(a, b), min(c, b)) --> min(min(c, b), a)
2280 // min(min(a, b), min(b, d)) --> min(min(b, d), a)
2281 MinMaxOp = RHS;
2282 ThirdOp = A;
2283 }
2284 } else if (!RHS->hasNUsesOrMore(3)) {
2285 // Reuse the LHS. This will eliminate the RHS.
2286 if (D == A || D == B) {
2287 // min(min(a, b), min(c, a)) --> min(min(a, b), c)
2288 // min(min(a, b), min(c, b)) --> min(min(a, b), c)
2289 MinMaxOp = LHS;
2290 ThirdOp = C;
2291 } else if (C == A || C == B) {
2292 // min(min(a, b), min(b, d)) --> min(min(a, b), d)
2293 // min(min(a, b), min(c, b)) --> min(min(a, b), d)
2294 MinMaxOp = LHS;
2295 ThirdOp = D;
2296 }
2297 }
2298 if (!MinMaxOp || !ThirdOp)
2299 return nullptr;
2300
2301 CmpInst::Predicate P = getMinMaxPred(SPF);
2302 Value *CmpABC = Builder.CreateICmp(P, MinMaxOp, ThirdOp);
2303 return SelectInst::Create(CmpABC, MinMaxOp, ThirdOp);
2304 }
2305
2306 /// Try to reduce a funnel/rotate pattern that includes a compare and select
2307 /// into a funnel shift intrinsic. Example:
2308 /// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
2309 /// --> call llvm.fshl.i32(a, a, b)
2310 /// fshl32(a, b, c) --> (c == 0 ? a : ((b >> (32 - c)) | (a << c)))
2311 /// --> call llvm.fshl.i32(a, b, c)
2312 /// fshr32(a, b, c) --> (c == 0 ? b : ((a >> (32 - c)) | (b << c)))
2313 /// --> call llvm.fshr.i32(a, b, c)
foldSelectFunnelShift(SelectInst & Sel,InstCombiner::BuilderTy & Builder)2314 static Instruction *foldSelectFunnelShift(SelectInst &Sel,
2315 InstCombiner::BuilderTy &Builder) {
2316 // This must be a power-of-2 type for a bitmasking transform to be valid.
2317 unsigned Width = Sel.getType()->getScalarSizeInBits();
2318 if (!isPowerOf2_32(Width))
2319 return nullptr;
2320
2321 BinaryOperator *Or0, *Or1;
2322 if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
2323 return nullptr;
2324
2325 Value *SV0, *SV1, *SA0, *SA1;
2326 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(SV0),
2327 m_ZExtOrSelf(m_Value(SA0))))) ||
2328 !match(Or1, m_OneUse(m_LogicalShift(m_Value(SV1),
2329 m_ZExtOrSelf(m_Value(SA1))))) ||
2330 Or0->getOpcode() == Or1->getOpcode())
2331 return nullptr;
2332
2333 // Canonicalize to or(shl(SV0, SA0), lshr(SV1, SA1)).
2334 if (Or0->getOpcode() == BinaryOperator::LShr) {
2335 std::swap(Or0, Or1);
2336 std::swap(SV0, SV1);
2337 std::swap(SA0, SA1);
2338 }
2339 assert(Or0->getOpcode() == BinaryOperator::Shl &&
2340 Or1->getOpcode() == BinaryOperator::LShr &&
2341 "Illegal or(shift,shift) pair");
2342
2343 // Check the shift amounts to see if they are an opposite pair.
2344 Value *ShAmt;
2345 if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
2346 ShAmt = SA0;
2347 else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
2348 ShAmt = SA1;
2349 else
2350 return nullptr;
2351
2352 // We should now have this pattern:
2353 // select ?, TVal, (or (shl SV0, SA0), (lshr SV1, SA1))
2354 // The false value of the select must be a funnel-shift of the true value:
2355 // IsFShl -> TVal must be SV0 else TVal must be SV1.
2356 bool IsFshl = (ShAmt == SA0);
2357 Value *TVal = Sel.getTrueValue();
2358 if ((IsFshl && TVal != SV0) || (!IsFshl && TVal != SV1))
2359 return nullptr;
2360
2361 // Finally, see if the select is filtering out a shift-by-zero.
2362 Value *Cond = Sel.getCondition();
2363 ICmpInst::Predicate Pred;
2364 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
2365 Pred != ICmpInst::ICMP_EQ)
2366 return nullptr;
2367
2368 // If this is not a rotate then the select was blocking poison from the
2369 // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it.
2370 if (SV0 != SV1) {
2371 if (IsFshl && !llvm::isGuaranteedNotToBePoison(SV1))
2372 SV1 = Builder.CreateFreeze(SV1);
2373 else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(SV0))
2374 SV0 = Builder.CreateFreeze(SV0);
2375 }
2376
2377 // This is a funnel/rotate that avoids shift-by-bitwidth UB in a suboptimal way.
2378 // Convert to funnel shift intrinsic.
2379 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2380 Function *F = Intrinsic::getDeclaration(Sel.getModule(), IID, Sel.getType());
2381 ShAmt = Builder.CreateZExt(ShAmt, Sel.getType());
2382 return CallInst::Create(F, { SV0, SV1, ShAmt });
2383 }
2384
foldSelectToCopysign(SelectInst & Sel,InstCombiner::BuilderTy & Builder)2385 static Instruction *foldSelectToCopysign(SelectInst &Sel,
2386 InstCombiner::BuilderTy &Builder) {
2387 Value *Cond = Sel.getCondition();
2388 Value *TVal = Sel.getTrueValue();
2389 Value *FVal = Sel.getFalseValue();
2390 Type *SelType = Sel.getType();
2391
2392 // Match select ?, TC, FC where the constants are equal but negated.
2393 // TODO: Generalize to handle a negated variable operand?
2394 const APFloat *TC, *FC;
2395 if (!match(TVal, m_APFloat(TC)) || !match(FVal, m_APFloat(FC)) ||
2396 !abs(*TC).bitwiseIsEqual(abs(*FC)))
2397 return nullptr;
2398
2399 assert(TC != FC && "Expected equal select arms to simplify");
2400
2401 Value *X;
2402 const APInt *C;
2403 bool IsTrueIfSignSet;
2404 ICmpInst::Predicate Pred;
2405 if (!match(Cond, m_OneUse(m_ICmp(Pred, m_BitCast(m_Value(X)), m_APInt(C)))) ||
2406 !InstCombiner::isSignBitCheck(Pred, *C, IsTrueIfSignSet) ||
2407 X->getType() != SelType)
2408 return nullptr;
2409
2410 // If needed, negate the value that will be the sign argument of the copysign:
2411 // (bitcast X) < 0 ? -TC : TC --> copysign(TC, X)
2412 // (bitcast X) < 0 ? TC : -TC --> copysign(TC, -X)
2413 // (bitcast X) >= 0 ? -TC : TC --> copysign(TC, -X)
2414 // (bitcast X) >= 0 ? TC : -TC --> copysign(TC, X)
2415 if (IsTrueIfSignSet ^ TC->isNegative())
2416 X = Builder.CreateFNegFMF(X, &Sel);
2417
2418 // Canonicalize the magnitude argument as the positive constant since we do
2419 // not care about its sign.
2420 Value *MagArg = TC->isNegative() ? FVal : TVal;
2421 Function *F = Intrinsic::getDeclaration(Sel.getModule(), Intrinsic::copysign,
2422 Sel.getType());
2423 Instruction *CopySign = CallInst::Create(F, { MagArg, X });
2424 CopySign->setFastMathFlags(Sel.getFastMathFlags());
2425 return CopySign;
2426 }
2427
foldVectorSelect(SelectInst & Sel)2428 Instruction *InstCombinerImpl::foldVectorSelect(SelectInst &Sel) {
2429 auto *VecTy = dyn_cast<FixedVectorType>(Sel.getType());
2430 if (!VecTy)
2431 return nullptr;
2432
2433 unsigned NumElts = VecTy->getNumElements();
2434 APInt UndefElts(NumElts, 0);
2435 APInt AllOnesEltMask(APInt::getAllOnesValue(NumElts));
2436 if (Value *V = SimplifyDemandedVectorElts(&Sel, AllOnesEltMask, UndefElts)) {
2437 if (V != &Sel)
2438 return replaceInstUsesWith(Sel, V);
2439 return &Sel;
2440 }
2441
2442 // A select of a "select shuffle" with a common operand can be rearranged
2443 // to select followed by "select shuffle". Because of poison, this only works
2444 // in the case of a shuffle with no undefined mask elements.
2445 Value *Cond = Sel.getCondition();
2446 Value *TVal = Sel.getTrueValue();
2447 Value *FVal = Sel.getFalseValue();
2448 Value *X, *Y;
2449 ArrayRef<int> Mask;
2450 if (match(TVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2451 !is_contained(Mask, UndefMaskElem) &&
2452 cast<ShuffleVectorInst>(TVal)->isSelect()) {
2453 if (X == FVal) {
2454 // select Cond, (shuf_sel X, Y), X --> shuf_sel X, (select Cond, Y, X)
2455 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2456 return new ShuffleVectorInst(X, NewSel, Mask);
2457 }
2458 if (Y == FVal) {
2459 // select Cond, (shuf_sel X, Y), Y --> shuf_sel (select Cond, X, Y), Y
2460 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2461 return new ShuffleVectorInst(NewSel, Y, Mask);
2462 }
2463 }
2464 if (match(FVal, m_OneUse(m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask)))) &&
2465 !is_contained(Mask, UndefMaskElem) &&
2466 cast<ShuffleVectorInst>(FVal)->isSelect()) {
2467 if (X == TVal) {
2468 // select Cond, X, (shuf_sel X, Y) --> shuf_sel X, (select Cond, X, Y)
2469 Value *NewSel = Builder.CreateSelect(Cond, X, Y, "sel", &Sel);
2470 return new ShuffleVectorInst(X, NewSel, Mask);
2471 }
2472 if (Y == TVal) {
2473 // select Cond, Y, (shuf_sel X, Y) --> shuf_sel (select Cond, Y, X), Y
2474 Value *NewSel = Builder.CreateSelect(Cond, Y, X, "sel", &Sel);
2475 return new ShuffleVectorInst(NewSel, Y, Mask);
2476 }
2477 }
2478
2479 return nullptr;
2480 }
2481
foldSelectToPhiImpl(SelectInst & Sel,BasicBlock * BB,const DominatorTree & DT,InstCombiner::BuilderTy & Builder)2482 static Instruction *foldSelectToPhiImpl(SelectInst &Sel, BasicBlock *BB,
2483 const DominatorTree &DT,
2484 InstCombiner::BuilderTy &Builder) {
2485 // Find the block's immediate dominator that ends with a conditional branch
2486 // that matches select's condition (maybe inverted).
2487 auto *IDomNode = DT[BB]->getIDom();
2488 if (!IDomNode)
2489 return nullptr;
2490 BasicBlock *IDom = IDomNode->getBlock();
2491
2492 Value *Cond = Sel.getCondition();
2493 Value *IfTrue, *IfFalse;
2494 BasicBlock *TrueSucc, *FalseSucc;
2495 if (match(IDom->getTerminator(),
2496 m_Br(m_Specific(Cond), m_BasicBlock(TrueSucc),
2497 m_BasicBlock(FalseSucc)))) {
2498 IfTrue = Sel.getTrueValue();
2499 IfFalse = Sel.getFalseValue();
2500 } else if (match(IDom->getTerminator(),
2501 m_Br(m_Not(m_Specific(Cond)), m_BasicBlock(TrueSucc),
2502 m_BasicBlock(FalseSucc)))) {
2503 IfTrue = Sel.getFalseValue();
2504 IfFalse = Sel.getTrueValue();
2505 } else
2506 return nullptr;
2507
2508 // Make sure the branches are actually different.
2509 if (TrueSucc == FalseSucc)
2510 return nullptr;
2511
2512 // We want to replace select %cond, %a, %b with a phi that takes value %a
2513 // for all incoming edges that are dominated by condition `%cond == true`,
2514 // and value %b for edges dominated by condition `%cond == false`. If %a
2515 // or %b are also phis from the same basic block, we can go further and take
2516 // their incoming values from the corresponding blocks.
2517 BasicBlockEdge TrueEdge(IDom, TrueSucc);
2518 BasicBlockEdge FalseEdge(IDom, FalseSucc);
2519 DenseMap<BasicBlock *, Value *> Inputs;
2520 for (auto *Pred : predecessors(BB)) {
2521 // Check implication.
2522 BasicBlockEdge Incoming(Pred, BB);
2523 if (DT.dominates(TrueEdge, Incoming))
2524 Inputs[Pred] = IfTrue->DoPHITranslation(BB, Pred);
2525 else if (DT.dominates(FalseEdge, Incoming))
2526 Inputs[Pred] = IfFalse->DoPHITranslation(BB, Pred);
2527 else
2528 return nullptr;
2529 // Check availability.
2530 if (auto *Insn = dyn_cast<Instruction>(Inputs[Pred]))
2531 if (!DT.dominates(Insn, Pred->getTerminator()))
2532 return nullptr;
2533 }
2534
2535 Builder.SetInsertPoint(&*BB->begin());
2536 auto *PN = Builder.CreatePHI(Sel.getType(), Inputs.size());
2537 for (auto *Pred : predecessors(BB))
2538 PN->addIncoming(Inputs[Pred], Pred);
2539 PN->takeName(&Sel);
2540 return PN;
2541 }
2542
foldSelectToPhi(SelectInst & Sel,const DominatorTree & DT,InstCombiner::BuilderTy & Builder)2543 static Instruction *foldSelectToPhi(SelectInst &Sel, const DominatorTree &DT,
2544 InstCombiner::BuilderTy &Builder) {
2545 // Try to replace this select with Phi in one of these blocks.
2546 SmallSetVector<BasicBlock *, 4> CandidateBlocks;
2547 CandidateBlocks.insert(Sel.getParent());
2548 for (Value *V : Sel.operands())
2549 if (auto *I = dyn_cast<Instruction>(V))
2550 CandidateBlocks.insert(I->getParent());
2551
2552 for (BasicBlock *BB : CandidateBlocks)
2553 if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
2554 return PN;
2555 return nullptr;
2556 }
2557
foldSelectWithFrozenICmp(SelectInst & Sel,InstCombiner::BuilderTy & Builder)2558 static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy &Builder) {
2559 FreezeInst *FI = dyn_cast<FreezeInst>(Sel.getCondition());
2560 if (!FI)
2561 return nullptr;
2562
2563 Value *Cond = FI->getOperand(0);
2564 Value *TrueVal = Sel.getTrueValue(), *FalseVal = Sel.getFalseValue();
2565
2566 // select (freeze(x == y)), x, y --> y
2567 // select (freeze(x != y)), x, y --> x
2568 // The freeze should be only used by this select. Otherwise, remaining uses of
2569 // the freeze can observe a contradictory value.
2570 // c = freeze(x == y) ; Let's assume that y = poison & x = 42; c is 0 or 1
2571 // a = select c, x, y ;
2572 // f(a, c) ; f(poison, 1) cannot happen, but if a is folded
2573 // ; to y, this can happen.
2574 CmpInst::Predicate Pred;
2575 if (FI->hasOneUse() &&
2576 match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
2577 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
2578 return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
2579 }
2580
2581 return nullptr;
2582 }
2583
foldAndOrOfSelectUsingImpliedCond(Value * Op,SelectInst & SI,bool IsAnd)2584 Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
2585 SelectInst &SI,
2586 bool IsAnd) {
2587 Value *CondVal = SI.getCondition();
2588 Value *A = SI.getTrueValue();
2589 Value *B = SI.getFalseValue();
2590
2591 assert(Op->getType()->isIntOrIntVectorTy(1) &&
2592 "Op must be either i1 or vector of i1.");
2593
2594 Optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
2595 if (!Res)
2596 return nullptr;
2597
2598 Value *Zero = Constant::getNullValue(A->getType());
2599 Value *One = Constant::getAllOnesValue(A->getType());
2600
2601 if (*Res == true) {
2602 if (IsAnd)
2603 // select op, (select cond, A, B), false => select op, A, false
2604 // and op, (select cond, A, B) => select op, A, false
2605 // if op = true implies condval = true.
2606 return SelectInst::Create(Op, A, Zero);
2607 else
2608 // select op, true, (select cond, A, B) => select op, true, A
2609 // or op, (select cond, A, B) => select op, true, A
2610 // if op = false implies condval = true.
2611 return SelectInst::Create(Op, One, A);
2612 } else {
2613 if (IsAnd)
2614 // select op, (select cond, A, B), false => select op, B, false
2615 // and op, (select cond, A, B) => select op, B, false
2616 // if op = true implies condval = false.
2617 return SelectInst::Create(Op, B, Zero);
2618 else
2619 // select op, true, (select cond, A, B) => select op, true, B
2620 // or op, (select cond, A, B) => select op, true, B
2621 // if op = false implies condval = false.
2622 return SelectInst::Create(Op, One, B);
2623 }
2624 }
2625
visitSelectInst(SelectInst & SI)2626 Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
2627 Value *CondVal = SI.getCondition();
2628 Value *TrueVal = SI.getTrueValue();
2629 Value *FalseVal = SI.getFalseValue();
2630 Type *SelType = SI.getType();
2631
2632 // FIXME: Remove this workaround when freeze related patches are done.
2633 // For select with undef operand which feeds into an equality comparison,
2634 // don't simplify it so loop unswitch can know the equality comparison
2635 // may have an undef operand. This is a workaround for PR31652 caused by
2636 // descrepancy about branch on undef between LoopUnswitch and GVN.
2637 if (match(TrueVal, m_Undef()) || match(FalseVal, m_Undef())) {
2638 if (llvm::any_of(SI.users(), [&](User *U) {
2639 ICmpInst *CI = dyn_cast<ICmpInst>(U);
2640 if (CI && CI->isEquality())
2641 return true;
2642 return false;
2643 })) {
2644 return nullptr;
2645 }
2646 }
2647
2648 if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal,
2649 SQ.getWithInstruction(&SI)))
2650 return replaceInstUsesWith(SI, V);
2651
2652 if (Instruction *I = canonicalizeSelectToShuffle(SI))
2653 return I;
2654
2655 if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
2656 return I;
2657
2658 CmpInst::Predicate Pred;
2659
2660 // Avoid potential infinite loops by checking for non-constant condition.
2661 // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
2662 // Scalar select must have simplified?
2663 if (SelType->isIntOrIntVectorTy(1) && !isa<Constant>(CondVal) &&
2664 TrueVal->getType() == CondVal->getType()) {
2665 // Folding select to and/or i1 isn't poison safe in general. impliesPoison
2666 // checks whether folding it does not convert a well-defined value into
2667 // poison.
2668 if (match(TrueVal, m_One()) && impliesPoison(FalseVal, CondVal)) {
2669 // Change: A = select B, true, C --> A = or B, C
2670 return BinaryOperator::CreateOr(CondVal, FalseVal);
2671 }
2672 if (match(FalseVal, m_Zero()) && impliesPoison(TrueVal, CondVal)) {
2673 // Change: A = select B, C, false --> A = and B, C
2674 return BinaryOperator::CreateAnd(CondVal, TrueVal);
2675 }
2676
2677 auto *One = ConstantInt::getTrue(SelType);
2678 auto *Zero = ConstantInt::getFalse(SelType);
2679
2680 // We match the "full" 0 or 1 constant here to avoid a potential infinite
2681 // loop with vectors that may have undefined/poison elements.
2682 // select a, false, b -> select !a, b, false
2683 if (match(TrueVal, m_Specific(Zero))) {
2684 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2685 return SelectInst::Create(NotCond, FalseVal, Zero);
2686 }
2687 // select a, b, true -> select !a, true, b
2688 if (match(FalseVal, m_Specific(One))) {
2689 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2690 return SelectInst::Create(NotCond, One, TrueVal);
2691 }
2692
2693 // select a, a, b -> select a, true, b
2694 if (CondVal == TrueVal)
2695 return replaceOperand(SI, 1, One);
2696 // select a, b, a -> select a, b, false
2697 if (CondVal == FalseVal)
2698 return replaceOperand(SI, 2, Zero);
2699
2700 // select a, !a, b -> select !a, b, false
2701 if (match(TrueVal, m_Not(m_Specific(CondVal))))
2702 return SelectInst::Create(TrueVal, FalseVal, Zero);
2703 // select a, b, !a -> select !a, true, b
2704 if (match(FalseVal, m_Not(m_Specific(CondVal))))
2705 return SelectInst::Create(FalseVal, One, TrueVal);
2706
2707 Value *A, *B;
2708
2709 // DeMorgan in select form: !a && !b --> !(a || b)
2710 // select !a, !b, false --> not (select a, true, b)
2711 if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2712 (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
2713 !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2714 return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
2715
2716 // DeMorgan in select form: !a || !b --> !(a && b)
2717 // select !a, true, !b --> not (select a, b, false)
2718 if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
2719 (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
2720 !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
2721 return BinaryOperator::CreateNot(Builder.CreateSelect(A, B, Zero));
2722
2723 // select (select a, true, b), true, b -> select a, true, b
2724 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2725 match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
2726 return replaceOperand(SI, 0, A);
2727 // select (select a, b, false), b, false -> select a, b, false
2728 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2729 match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
2730 return replaceOperand(SI, 0, A);
2731
2732 if (!SelType->isVectorTy()) {
2733 if (Value *S = simplifyWithOpReplaced(TrueVal, CondVal, One, SQ,
2734 /* AllowRefinement */ true))
2735 return replaceOperand(SI, 1, S);
2736 if (Value *S = simplifyWithOpReplaced(FalseVal, CondVal, Zero, SQ,
2737 /* AllowRefinement */ true))
2738 return replaceOperand(SI, 2, S);
2739 }
2740
2741 if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
2742 Use *Y = nullptr;
2743 bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
2744 Value *Op1 = IsAnd ? TrueVal : FalseVal;
2745 if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
2746 auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
2747 InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
2748 replaceUse(*Y, FI);
2749 return replaceInstUsesWith(SI, Op1);
2750 }
2751
2752 if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
2753 if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
2754 /* IsAnd */ IsAnd))
2755 return I;
2756
2757 if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal)) {
2758 if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1)) {
2759 if (auto *V = foldAndOrOfICmpsOfAndWithPow2(ICmp0, ICmp1, &SI, IsAnd,
2760 /* IsLogical */ true))
2761 return replaceInstUsesWith(SI, V);
2762
2763 if (auto *V = foldEqOfParts(ICmp0, ICmp1, IsAnd))
2764 return replaceInstUsesWith(SI, V);
2765 }
2766 }
2767 }
2768
2769 // select (select a, true, b), c, false -> select a, c, false
2770 // select c, (select a, true, b), false -> select c, a, false
2771 // if c implies that b is false.
2772 if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2773 match(FalseVal, m_Zero())) {
2774 Optional<bool> Res = isImpliedCondition(TrueVal, B, DL);
2775 if (Res && *Res == false)
2776 return replaceOperand(SI, 0, A);
2777 }
2778 if (match(TrueVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
2779 match(FalseVal, m_Zero())) {
2780 Optional<bool> Res = isImpliedCondition(CondVal, B, DL);
2781 if (Res && *Res == false)
2782 return replaceOperand(SI, 1, A);
2783 }
2784 // select c, true, (select a, b, false) -> select c, true, a
2785 // select (select a, b, false), true, c -> select a, true, c
2786 // if c = false implies that b = true
2787 if (match(TrueVal, m_One()) &&
2788 match(FalseVal, m_Select(m_Value(A), m_Value(B), m_Zero()))) {
2789 Optional<bool> Res = isImpliedCondition(CondVal, B, DL, false);
2790 if (Res && *Res == true)
2791 return replaceOperand(SI, 2, A);
2792 }
2793 if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
2794 match(TrueVal, m_One())) {
2795 Optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false);
2796 if (Res && *Res == true)
2797 return replaceOperand(SI, 0, A);
2798 }
2799
2800 // sel (sel c, a, false), true, (sel !c, b, false) -> sel c, a, b
2801 // sel (sel !c, a, false), true, (sel c, b, false) -> sel c, b, a
2802 Value *C1, *C2;
2803 if (match(CondVal, m_Select(m_Value(C1), m_Value(A), m_Zero())) &&
2804 match(TrueVal, m_One()) &&
2805 match(FalseVal, m_Select(m_Value(C2), m_Value(B), m_Zero()))) {
2806 if (match(C2, m_Not(m_Specific(C1)))) // first case
2807 return SelectInst::Create(C1, A, B);
2808 else if (match(C1, m_Not(m_Specific(C2)))) // second case
2809 return SelectInst::Create(C2, B, A);
2810 }
2811 }
2812
2813 // Selecting between two integer or vector splat integer constants?
2814 //
2815 // Note that we don't handle a scalar select of vectors:
2816 // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
2817 // because that may need 3 instructions to splat the condition value:
2818 // extend, insertelement, shufflevector.
2819 //
2820 // Do not handle i1 TrueVal and FalseVal otherwise would result in
2821 // zext/sext i1 to i1.
2822 if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) &&
2823 CondVal->getType()->isVectorTy() == SelType->isVectorTy()) {
2824 // select C, 1, 0 -> zext C to int
2825 if (match(TrueVal, m_One()) && match(FalseVal, m_Zero()))
2826 return new ZExtInst(CondVal, SelType);
2827
2828 // select C, -1, 0 -> sext C to int
2829 if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero()))
2830 return new SExtInst(CondVal, SelType);
2831
2832 // select C, 0, 1 -> zext !C to int
2833 if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) {
2834 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2835 return new ZExtInst(NotCond, SelType);
2836 }
2837
2838 // select C, 0, -1 -> sext !C to int
2839 if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) {
2840 Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
2841 return new SExtInst(NotCond, SelType);
2842 }
2843 }
2844
2845 if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) {
2846 Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1);
2847 // Are we selecting a value based on a comparison of the two values?
2848 if ((Cmp0 == TrueVal && Cmp1 == FalseVal) ||
2849 (Cmp0 == FalseVal && Cmp1 == TrueVal)) {
2850 // Canonicalize to use ordered comparisons by swapping the select
2851 // operands.
2852 //
2853 // e.g.
2854 // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
2855 if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) {
2856 FCmpInst::Predicate InvPred = FCmp->getInversePredicate();
2857 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
2858 // FIXME: The FMF should propagate from the select, not the fcmp.
2859 Builder.setFastMathFlags(FCmp->getFastMathFlags());
2860 Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1,
2861 FCmp->getName() + ".inv");
2862 Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal);
2863 return replaceInstUsesWith(SI, NewSel);
2864 }
2865
2866 // NOTE: if we wanted to, this is where to detect MIN/MAX
2867 }
2868 }
2869
2870 // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
2871 // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We
2872 // also require nnan because we do not want to unintentionally change the
2873 // sign of a NaN value.
2874 // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X)
2875 Instruction *FSub;
2876 if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) &&
2877 match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(FalseVal))) &&
2878 match(TrueVal, m_Instruction(FSub)) && FSub->hasNoNaNs() &&
2879 (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) {
2880 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, &SI);
2881 return replaceInstUsesWith(SI, Fabs);
2882 }
2883 // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X)
2884 if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) &&
2885 match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(TrueVal))) &&
2886 match(FalseVal, m_Instruction(FSub)) && FSub->hasNoNaNs() &&
2887 (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) {
2888 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, &SI);
2889 return replaceInstUsesWith(SI, Fabs);
2890 }
2891 // With nnan and nsz:
2892 // (X < +/-0.0) ? -X : X --> fabs(X)
2893 // (X <= +/-0.0) ? -X : X --> fabs(X)
2894 Instruction *FNeg;
2895 if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) &&
2896 match(TrueVal, m_FNeg(m_Specific(FalseVal))) &&
2897 match(TrueVal, m_Instruction(FNeg)) && FNeg->hasNoNaNs() &&
2898 FNeg->hasNoSignedZeros() && SI.hasNoSignedZeros() &&
2899 (Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE ||
2900 Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE)) {
2901 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, &SI);
2902 return replaceInstUsesWith(SI, Fabs);
2903 }
2904 // With nnan and nsz:
2905 // (X > +/-0.0) ? X : -X --> fabs(X)
2906 // (X >= +/-0.0) ? X : -X --> fabs(X)
2907 if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) &&
2908 match(FalseVal, m_FNeg(m_Specific(TrueVal))) &&
2909 match(FalseVal, m_Instruction(FNeg)) && FNeg->hasNoNaNs() &&
2910 FNeg->hasNoSignedZeros() && SI.hasNoSignedZeros() &&
2911 (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE ||
2912 Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE)) {
2913 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, &SI);
2914 return replaceInstUsesWith(SI, Fabs);
2915 }
2916
2917 // See if we are selecting two values based on a comparison of the two values.
2918 if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
2919 if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
2920 return Result;
2921
2922 if (Instruction *Add = foldAddSubSelect(SI, Builder))
2923 return Add;
2924 if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder))
2925 return Add;
2926 if (Instruction *Or = foldSetClearBits(SI, Builder))
2927 return Or;
2928
2929 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
2930 auto *TI = dyn_cast<Instruction>(TrueVal);
2931 auto *FI = dyn_cast<Instruction>(FalseVal);
2932 if (TI && FI && TI->getOpcode() == FI->getOpcode())
2933 if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
2934 return IV;
2935
2936 if (Instruction *I = foldSelectExtConst(SI))
2937 return I;
2938
2939 // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0))
2940 // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx))
2941 auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base,
2942 bool Swap) -> GetElementPtrInst * {
2943 Value *Ptr = Gep->getPointerOperand();
2944 if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base ||
2945 !Gep->hasOneUse())
2946 return nullptr;
2947 Type *ElementType = Gep->getResultElementType();
2948 Value *Idx = Gep->getOperand(1);
2949 Value *NewT = Idx;
2950 Value *NewF = Constant::getNullValue(Idx->getType());
2951 if (Swap)
2952 std::swap(NewT, NewF);
2953 Value *NewSI =
2954 Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI);
2955 return GetElementPtrInst::Create(ElementType, Ptr, {NewSI});
2956 };
2957 if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal))
2958 if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false))
2959 return NewGep;
2960 if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal))
2961 if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true))
2962 return NewGep;
2963
2964 // See if we can fold the select into one of our operands.
2965 if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) {
2966 if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
2967 return FoldI;
2968
2969 Value *LHS, *RHS;
2970 Instruction::CastOps CastOp;
2971 SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
2972 auto SPF = SPR.Flavor;
2973 if (SPF) {
2974 Value *LHS2, *RHS2;
2975 if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
2976 if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
2977 RHS2, SI, SPF, RHS))
2978 return R;
2979 if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
2980 if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
2981 RHS2, SI, SPF, LHS))
2982 return R;
2983 // TODO.
2984 // ABS(-X) -> ABS(X)
2985 }
2986
2987 if (SelectPatternResult::isMinOrMax(SPF)) {
2988 // Canonicalize so that
2989 // - type casts are outside select patterns.
2990 // - float clamp is transformed to min/max pattern
2991
2992 bool IsCastNeeded = LHS->getType() != SelType;
2993 Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
2994 Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
2995 if (IsCastNeeded ||
2996 (LHS->getType()->isFPOrFPVectorTy() &&
2997 ((CmpLHS != LHS && CmpLHS != RHS) ||
2998 (CmpRHS != LHS && CmpRHS != RHS)))) {
2999 CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered);
3000
3001 Value *Cmp;
3002 if (CmpInst::isIntPredicate(MinMaxPred)) {
3003 Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS);
3004 } else {
3005 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
3006 auto FMF =
3007 cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
3008 Builder.setFastMathFlags(FMF);
3009 Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS);
3010 }
3011
3012 Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
3013 if (!IsCastNeeded)
3014 return replaceInstUsesWith(SI, NewSI);
3015
3016 Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
3017 return replaceInstUsesWith(SI, NewCast);
3018 }
3019
3020 // MAX(~a, ~b) -> ~MIN(a, b)
3021 // MAX(~a, C) -> ~MIN(a, ~C)
3022 // MIN(~a, ~b) -> ~MAX(a, b)
3023 // MIN(~a, C) -> ~MAX(a, ~C)
3024 auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * {
3025 Value *A;
3026 if (match(X, m_Not(m_Value(A))) && !X->hasNUsesOrMore(3) &&
3027 !isFreeToInvert(A, A->hasOneUse()) &&
3028 // Passing false to only consider m_Not and constants.
3029 isFreeToInvert(Y, false)) {
3030 Value *B = Builder.CreateNot(Y);
3031 Value *NewMinMax = createMinMax(Builder, getInverseMinMaxFlavor(SPF),
3032 A, B);
3033 // Copy the profile metadata.
3034 if (MDNode *MD = SI.getMetadata(LLVMContext::MD_prof)) {
3035 cast<SelectInst>(NewMinMax)->setMetadata(LLVMContext::MD_prof, MD);
3036 // Swap the metadata if the operands are swapped.
3037 if (X == SI.getFalseValue() && Y == SI.getTrueValue())
3038 cast<SelectInst>(NewMinMax)->swapProfMetadata();
3039 }
3040
3041 return BinaryOperator::CreateNot(NewMinMax);
3042 }
3043
3044 return nullptr;
3045 };
3046
3047 if (Instruction *I = moveNotAfterMinMax(LHS, RHS))
3048 return I;
3049 if (Instruction *I = moveNotAfterMinMax(RHS, LHS))
3050 return I;
3051
3052 if (Instruction *I = moveAddAfterMinMax(SPF, LHS, RHS, Builder))
3053 return I;
3054
3055 if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder))
3056 return I;
3057 if (Instruction *I = matchSAddSubSat(SI))
3058 return I;
3059 }
3060 }
3061
3062 // Canonicalize select of FP values where NaN and -0.0 are not valid as
3063 // minnum/maxnum intrinsics.
3064 if (isa<FPMathOperator>(SI) && SI.hasNoNaNs() && SI.hasNoSignedZeros()) {
3065 Value *X, *Y;
3066 if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
3067 return replaceInstUsesWith(
3068 SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
3069
3070 if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
3071 return replaceInstUsesWith(
3072 SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
3073 }
3074
3075 // See if we can fold the select into a phi node if the condition is a select.
3076 if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
3077 // The true/false values have to be live in the PHI predecessor's blocks.
3078 if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
3079 canSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
3080 if (Instruction *NV = foldOpIntoPhi(SI, PN))
3081 return NV;
3082
3083 if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
3084 if (TrueSI->getCondition()->getType() == CondVal->getType()) {
3085 // select(C, select(C, a, b), c) -> select(C, a, c)
3086 if (TrueSI->getCondition() == CondVal) {
3087 if (SI.getTrueValue() == TrueSI->getTrueValue())
3088 return nullptr;
3089 return replaceOperand(SI, 1, TrueSI->getTrueValue());
3090 }
3091 // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
3092 // We choose this as normal form to enable folding on the And and
3093 // shortening paths for the values (this helps getUnderlyingObjects() for
3094 // example).
3095 if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) {
3096 Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition());
3097 replaceOperand(SI, 0, And);
3098 replaceOperand(SI, 1, TrueSI->getTrueValue());
3099 return &SI;
3100 }
3101 }
3102 }
3103 if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
3104 if (FalseSI->getCondition()->getType() == CondVal->getType()) {
3105 // select(C, a, select(C, b, c)) -> select(C, a, c)
3106 if (FalseSI->getCondition() == CondVal) {
3107 if (SI.getFalseValue() == FalseSI->getFalseValue())
3108 return nullptr;
3109 return replaceOperand(SI, 2, FalseSI->getFalseValue());
3110 }
3111 // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
3112 if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) {
3113 Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
3114 replaceOperand(SI, 0, Or);
3115 replaceOperand(SI, 2, FalseSI->getFalseValue());
3116 return &SI;
3117 }
3118 }
3119 }
3120
3121 auto canMergeSelectThroughBinop = [](BinaryOperator *BO) {
3122 // The select might be preventing a division by 0.
3123 switch (BO->getOpcode()) {
3124 default:
3125 return true;
3126 case Instruction::SRem:
3127 case Instruction::URem:
3128 case Instruction::SDiv:
3129 case Instruction::UDiv:
3130 return false;
3131 }
3132 };
3133
3134 // Try to simplify a binop sandwiched between 2 selects with the same
3135 // condition.
3136 // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
3137 BinaryOperator *TrueBO;
3138 if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) &&
3139 canMergeSelectThroughBinop(TrueBO)) {
3140 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
3141 if (TrueBOSI->getCondition() == CondVal) {
3142 replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue());
3143 Worklist.push(TrueBO);
3144 return &SI;
3145 }
3146 }
3147 if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
3148 if (TrueBOSI->getCondition() == CondVal) {
3149 replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue());
3150 Worklist.push(TrueBO);
3151 return &SI;
3152 }
3153 }
3154 }
3155
3156 // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
3157 BinaryOperator *FalseBO;
3158 if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) &&
3159 canMergeSelectThroughBinop(FalseBO)) {
3160 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
3161 if (FalseBOSI->getCondition() == CondVal) {
3162 replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue());
3163 Worklist.push(FalseBO);
3164 return &SI;
3165 }
3166 }
3167 if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
3168 if (FalseBOSI->getCondition() == CondVal) {
3169 replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue());
3170 Worklist.push(FalseBO);
3171 return &SI;
3172 }
3173 }
3174 }
3175
3176 Value *NotCond;
3177 if (match(CondVal, m_Not(m_Value(NotCond))) &&
3178 !InstCombiner::shouldAvoidAbsorbingNotIntoSelect(SI)) {
3179 replaceOperand(SI, 0, NotCond);
3180 SI.swapValues();
3181 SI.swapProfMetadata();
3182 return &SI;
3183 }
3184
3185 if (Instruction *I = foldVectorSelect(SI))
3186 return I;
3187
3188 // If we can compute the condition, there's no need for a select.
3189 // Like the above fold, we are attempting to reduce compile-time cost by
3190 // putting this fold here with limitations rather than in InstSimplify.
3191 // The motivation for this call into value tracking is to take advantage of
3192 // the assumption cache, so make sure that is populated.
3193 if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
3194 KnownBits Known(1);
3195 computeKnownBits(CondVal, Known, 0, &SI);
3196 if (Known.One.isOneValue())
3197 return replaceInstUsesWith(SI, TrueVal);
3198 if (Known.Zero.isOneValue())
3199 return replaceInstUsesWith(SI, FalseVal);
3200 }
3201
3202 if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
3203 return BitCastSel;
3204
3205 // Simplify selects that test the returned flag of cmpxchg instructions.
3206 if (Value *V = foldSelectCmpXchg(SI))
3207 return replaceInstUsesWith(SI, V);
3208
3209 if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this))
3210 return Select;
3211
3212 if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder))
3213 return Funnel;
3214
3215 if (Instruction *Copysign = foldSelectToCopysign(SI, Builder))
3216 return Copysign;
3217
3218 if (Instruction *PN = foldSelectToPhi(SI, DT, Builder))
3219 return replaceInstUsesWith(SI, PN);
3220
3221 if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder))
3222 return replaceInstUsesWith(SI, Fr);
3223
3224 // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0)
3225 // Load inst is intentionally not checked for hasOneUse()
3226 if (match(FalseVal, m_Zero()) &&
3227 match(TrueVal, m_MaskedLoad(m_Value(), m_Value(), m_Specific(CondVal),
3228 m_CombineOr(m_Undef(), m_Zero())))) {
3229 auto *MaskedLoad = cast<IntrinsicInst>(TrueVal);
3230 if (isa<UndefValue>(MaskedLoad->getArgOperand(3)))
3231 MaskedLoad->setArgOperand(3, FalseVal /* Zero */);
3232 return replaceInstUsesWith(SI, MaskedLoad);
3233 }
3234
3235 Value *Mask;
3236 if (match(TrueVal, m_Zero()) &&
3237 match(FalseVal, m_MaskedLoad(m_Value(), m_Value(), m_Value(Mask),
3238 m_CombineOr(m_Undef(), m_Zero()))) &&
3239 (CondVal->getType() == Mask->getType())) {
3240 // We can remove the select by ensuring the load zeros all lanes the
3241 // select would have. We determine this by proving there is no overlap
3242 // between the load and select masks.
3243 // (i.e (load_mask & select_mask) == 0 == no overlap)
3244 bool CanMergeSelectIntoLoad = false;
3245 if (Value *V = SimplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI)))
3246 CanMergeSelectIntoLoad = match(V, m_Zero());
3247
3248 if (CanMergeSelectIntoLoad) {
3249 auto *MaskedLoad = cast<IntrinsicInst>(FalseVal);
3250 if (isa<UndefValue>(MaskedLoad->getArgOperand(3)))
3251 MaskedLoad->setArgOperand(3, TrueVal /* Zero */);
3252 return replaceInstUsesWith(SI, MaskedLoad);
3253 }
3254 }
3255
3256 return nullptr;
3257 }
3258