File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp |
Warning: | line 742, column 5 Value stored to 'Pred' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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" "instcombine" |
50 | |
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")((void)0); |
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. |
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. |
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?")((void)0); |
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")__builtin_unreachable(); |
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. |
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. |
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")__builtin_unreachable(); |
419 | return nullptr; |
420 | } |
421 | |
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. |
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. |
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) |
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 |
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. |
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. |
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); |
Value stored to 'Pred' is never read | |
743 | } |
744 | |
745 | assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&((void)0) |
746 | "Unexpected isUnsigned predicate!")((void)0); |
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 | |
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) |
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) |
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. |
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. |
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 &&((void)0) |
1074 | "Unexpected results from matchSelectPattern")((void)0); |
1075 | Sel.swapValues(); |
1076 | Sel.swapProfMetadata(); |
1077 | return &Sel; |
1078 | } |
1079 | |
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. |
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.) |
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[[gnu::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 * |
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. |
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. |
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) |
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. |
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 * |
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 | |
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. |
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. |
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)) |
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 | /// |
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 | |
2147 | static Instruction *moveAddAfterMinMax(SelectPatternFlavor SPF, Value *X, |
2148 | Value *Y, |
2149 | InstCombiner::BuilderTy &Builder) { |
2150 | assert(SelectPatternResult::isMinOrMax(SPF) && "Expected min/max pattern")((void)0); |
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. |
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. |
2250 | static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS, |
2251 | Value *RHS, |
2252 | InstCombiner::BuilderTy &Builder) { |
2253 | assert(SelectPatternResult::isMinOrMax(SPF) && "Expected a min/max")((void)0); |
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) |
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 &&((void)0) |
2340 | Or1->getOpcode() == BinaryOperator::LShr &&((void)0) |
2341 | "Illegal or(shift,shift) pair")((void)0); |
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 | |
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")((void)0); |
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 | |
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 | |
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 | |
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 | |
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 | |
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) &&((void)0) |
2592 | "Op must be either i1 or vector of i1.")((void)0); |
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 | |
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 | |
2764 | // select (select a, true, b), c, false -> select a, c, false |
2765 | // select c, (select a, true, b), false -> select c, a, false |
2766 | // if c implies that b is false. |
2767 | if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) && |
2768 | match(FalseVal, m_Zero())) { |
2769 | Optional<bool> Res = isImpliedCondition(TrueVal, B, DL); |
2770 | if (Res && *Res == false) |
2771 | return replaceOperand(SI, 0, A); |
2772 | } |
2773 | if (match(TrueVal, m_Select(m_Value(A), m_One(), m_Value(B))) && |
2774 | match(FalseVal, m_Zero())) { |
2775 | Optional<bool> Res = isImpliedCondition(CondVal, B, DL); |
2776 | if (Res && *Res == false) |
2777 | return replaceOperand(SI, 1, A); |
2778 | } |
2779 | // select c, true, (select a, b, false) -> select c, true, a |
2780 | // select (select a, b, false), true, c -> select a, true, c |
2781 | // if c = false implies that b = true |
2782 | if (match(TrueVal, m_One()) && |
2783 | match(FalseVal, m_Select(m_Value(A), m_Value(B), m_Zero()))) { |
2784 | Optional<bool> Res = isImpliedCondition(CondVal, B, DL, false); |
2785 | if (Res && *Res == true) |
2786 | return replaceOperand(SI, 2, A); |
2787 | } |
2788 | if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) && |
2789 | match(TrueVal, m_One())) { |
2790 | Optional<bool> Res = isImpliedCondition(FalseVal, B, DL, false); |
2791 | if (Res && *Res == true) |
2792 | return replaceOperand(SI, 0, A); |
2793 | } |
2794 | |
2795 | // sel (sel c, a, false), true, (sel !c, b, false) -> sel c, a, b |
2796 | // sel (sel !c, a, false), true, (sel c, b, false) -> sel c, b, a |
2797 | Value *C1, *C2; |
2798 | if (match(CondVal, m_Select(m_Value(C1), m_Value(A), m_Zero())) && |
2799 | match(TrueVal, m_One()) && |
2800 | match(FalseVal, m_Select(m_Value(C2), m_Value(B), m_Zero()))) { |
2801 | if (match(C2, m_Not(m_Specific(C1)))) // first case |
2802 | return SelectInst::Create(C1, A, B); |
2803 | else if (match(C1, m_Not(m_Specific(C2)))) // second case |
2804 | return SelectInst::Create(C2, B, A); |
2805 | } |
2806 | } |
2807 | |
2808 | // Selecting between two integer or vector splat integer constants? |
2809 | // |
2810 | // Note that we don't handle a scalar select of vectors: |
2811 | // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0> |
2812 | // because that may need 3 instructions to splat the condition value: |
2813 | // extend, insertelement, shufflevector. |
2814 | // |
2815 | // Do not handle i1 TrueVal and FalseVal otherwise would result in |
2816 | // zext/sext i1 to i1. |
2817 | if (SelType->isIntOrIntVectorTy() && !SelType->isIntOrIntVectorTy(1) && |
2818 | CondVal->getType()->isVectorTy() == SelType->isVectorTy()) { |
2819 | // select C, 1, 0 -> zext C to int |
2820 | if (match(TrueVal, m_One()) && match(FalseVal, m_Zero())) |
2821 | return new ZExtInst(CondVal, SelType); |
2822 | |
2823 | // select C, -1, 0 -> sext C to int |
2824 | if (match(TrueVal, m_AllOnes()) && match(FalseVal, m_Zero())) |
2825 | return new SExtInst(CondVal, SelType); |
2826 | |
2827 | // select C, 0, 1 -> zext !C to int |
2828 | if (match(TrueVal, m_Zero()) && match(FalseVal, m_One())) { |
2829 | Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); |
2830 | return new ZExtInst(NotCond, SelType); |
2831 | } |
2832 | |
2833 | // select C, 0, -1 -> sext !C to int |
2834 | if (match(TrueVal, m_Zero()) && match(FalseVal, m_AllOnes())) { |
2835 | Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName()); |
2836 | return new SExtInst(NotCond, SelType); |
2837 | } |
2838 | } |
2839 | |
2840 | if (auto *FCmp = dyn_cast<FCmpInst>(CondVal)) { |
2841 | Value *Cmp0 = FCmp->getOperand(0), *Cmp1 = FCmp->getOperand(1); |
2842 | // Are we selecting a value based on a comparison of the two values? |
2843 | if ((Cmp0 == TrueVal && Cmp1 == FalseVal) || |
2844 | (Cmp0 == FalseVal && Cmp1 == TrueVal)) { |
2845 | // Canonicalize to use ordered comparisons by swapping the select |
2846 | // operands. |
2847 | // |
2848 | // e.g. |
2849 | // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X |
2850 | if (FCmp->hasOneUse() && FCmpInst::isUnordered(FCmp->getPredicate())) { |
2851 | FCmpInst::Predicate InvPred = FCmp->getInversePredicate(); |
2852 | IRBuilder<>::FastMathFlagGuard FMFG(Builder); |
2853 | // FIXME: The FMF should propagate from the select, not the fcmp. |
2854 | Builder.setFastMathFlags(FCmp->getFastMathFlags()); |
2855 | Value *NewCond = Builder.CreateFCmp(InvPred, Cmp0, Cmp1, |
2856 | FCmp->getName() + ".inv"); |
2857 | Value *NewSel = Builder.CreateSelect(NewCond, FalseVal, TrueVal); |
2858 | return replaceInstUsesWith(SI, NewSel); |
2859 | } |
2860 | |
2861 | // NOTE: if we wanted to, this is where to detect MIN/MAX |
2862 | } |
2863 | } |
2864 | |
2865 | // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need |
2866 | // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We |
2867 | // also require nnan because we do not want to unintentionally change the |
2868 | // sign of a NaN value. |
2869 | // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X) |
2870 | Instruction *FSub; |
2871 | if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) && |
2872 | match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(FalseVal))) && |
2873 | match(TrueVal, m_Instruction(FSub)) && FSub->hasNoNaNs() && |
2874 | (Pred == FCmpInst::FCMP_OLE || Pred == FCmpInst::FCMP_ULE)) { |
2875 | Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, &SI); |
2876 | return replaceInstUsesWith(SI, Fabs); |
2877 | } |
2878 | // (X > +/-0.0) ? X : (0.0 - X) --> fabs(X) |
2879 | if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) && |
2880 | match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(TrueVal))) && |
2881 | match(FalseVal, m_Instruction(FSub)) && FSub->hasNoNaNs() && |
2882 | (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_UGT)) { |
2883 | Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, &SI); |
2884 | return replaceInstUsesWith(SI, Fabs); |
2885 | } |
2886 | // With nnan and nsz: |
2887 | // (X < +/-0.0) ? -X : X --> fabs(X) |
2888 | // (X <= +/-0.0) ? -X : X --> fabs(X) |
2889 | Instruction *FNeg; |
2890 | if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) && |
2891 | match(TrueVal, m_FNeg(m_Specific(FalseVal))) && |
2892 | match(TrueVal, m_Instruction(FNeg)) && FNeg->hasNoNaNs() && |
2893 | FNeg->hasNoSignedZeros() && SI.hasNoSignedZeros() && |
2894 | (Pred == FCmpInst::FCMP_OLT || Pred == FCmpInst::FCMP_OLE || |
2895 | Pred == FCmpInst::FCMP_ULT || Pred == FCmpInst::FCMP_ULE)) { |
2896 | Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, &SI); |
2897 | return replaceInstUsesWith(SI, Fabs); |
2898 | } |
2899 | // With nnan and nsz: |
2900 | // (X > +/-0.0) ? X : -X --> fabs(X) |
2901 | // (X >= +/-0.0) ? X : -X --> fabs(X) |
2902 | if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) && |
2903 | match(FalseVal, m_FNeg(m_Specific(TrueVal))) && |
2904 | match(FalseVal, m_Instruction(FNeg)) && FNeg->hasNoNaNs() && |
2905 | FNeg->hasNoSignedZeros() && SI.hasNoSignedZeros() && |
2906 | (Pred == FCmpInst::FCMP_OGT || Pred == FCmpInst::FCMP_OGE || |
2907 | Pred == FCmpInst::FCMP_UGT || Pred == FCmpInst::FCMP_UGE)) { |
2908 | Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, &SI); |
2909 | return replaceInstUsesWith(SI, Fabs); |
2910 | } |
2911 | |
2912 | // See if we are selecting two values based on a comparison of the two values. |
2913 | if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal)) |
2914 | if (Instruction *Result = foldSelectInstWithICmp(SI, ICI)) |
2915 | return Result; |
2916 | |
2917 | if (Instruction *Add = foldAddSubSelect(SI, Builder)) |
2918 | return Add; |
2919 | if (Instruction *Add = foldOverflowingAddSubSelect(SI, Builder)) |
2920 | return Add; |
2921 | if (Instruction *Or = foldSetClearBits(SI, Builder)) |
2922 | return Or; |
2923 | |
2924 | // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z)) |
2925 | auto *TI = dyn_cast<Instruction>(TrueVal); |
2926 | auto *FI = dyn_cast<Instruction>(FalseVal); |
2927 | if (TI && FI && TI->getOpcode() == FI->getOpcode()) |
2928 | if (Instruction *IV = foldSelectOpOp(SI, TI, FI)) |
2929 | return IV; |
2930 | |
2931 | if (Instruction *I = foldSelectExtConst(SI)) |
2932 | return I; |
2933 | |
2934 | // Fold (select C, (gep Ptr, Idx), Ptr) -> (gep Ptr, (select C, Idx, 0)) |
2935 | // Fold (select C, Ptr, (gep Ptr, Idx)) -> (gep Ptr, (select C, 0, Idx)) |
2936 | auto SelectGepWithBase = [&](GetElementPtrInst *Gep, Value *Base, |
2937 | bool Swap) -> GetElementPtrInst * { |
2938 | Value *Ptr = Gep->getPointerOperand(); |
2939 | if (Gep->getNumOperands() != 2 || Gep->getPointerOperand() != Base || |
2940 | !Gep->hasOneUse()) |
2941 | return nullptr; |
2942 | Type *ElementType = Gep->getResultElementType(); |
2943 | Value *Idx = Gep->getOperand(1); |
2944 | Value *NewT = Idx; |
2945 | Value *NewF = Constant::getNullValue(Idx->getType()); |
2946 | if (Swap) |
2947 | std::swap(NewT, NewF); |
2948 | Value *NewSI = |
2949 | Builder.CreateSelect(CondVal, NewT, NewF, SI.getName() + ".idx", &SI); |
2950 | return GetElementPtrInst::Create(ElementType, Ptr, {NewSI}); |
2951 | }; |
2952 | if (auto *TrueGep = dyn_cast<GetElementPtrInst>(TrueVal)) |
2953 | if (auto *NewGep = SelectGepWithBase(TrueGep, FalseVal, false)) |
2954 | return NewGep; |
2955 | if (auto *FalseGep = dyn_cast<GetElementPtrInst>(FalseVal)) |
2956 | if (auto *NewGep = SelectGepWithBase(FalseGep, TrueVal, true)) |
2957 | return NewGep; |
2958 | |
2959 | // See if we can fold the select into one of our operands. |
2960 | if (SelType->isIntOrIntVectorTy() || SelType->isFPOrFPVectorTy()) { |
2961 | if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal)) |
2962 | return FoldI; |
2963 | |
2964 | Value *LHS, *RHS; |
2965 | Instruction::CastOps CastOp; |
2966 | SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp); |
2967 | auto SPF = SPR.Flavor; |
2968 | if (SPF) { |
2969 | Value *LHS2, *RHS2; |
2970 | if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor) |
2971 | if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2, |
2972 | RHS2, SI, SPF, RHS)) |
2973 | return R; |
2974 | if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor) |
2975 | if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2, |
2976 | RHS2, SI, SPF, LHS)) |
2977 | return R; |
2978 | // TODO. |
2979 | // ABS(-X) -> ABS(X) |
2980 | } |
2981 | |
2982 | if (SelectPatternResult::isMinOrMax(SPF)) { |
2983 | // Canonicalize so that |
2984 | // - type casts are outside select patterns. |
2985 | // - float clamp is transformed to min/max pattern |
2986 | |
2987 | bool IsCastNeeded = LHS->getType() != SelType; |
2988 | Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0); |
2989 | Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1); |
2990 | if (IsCastNeeded || |
2991 | (LHS->getType()->isFPOrFPVectorTy() && |
2992 | ((CmpLHS != LHS && CmpLHS != RHS) || |
2993 | (CmpRHS != LHS && CmpRHS != RHS)))) { |
2994 | CmpInst::Predicate MinMaxPred = getMinMaxPred(SPF, SPR.Ordered); |
2995 | |
2996 | Value *Cmp; |
2997 | if (CmpInst::isIntPredicate(MinMaxPred)) { |
2998 | Cmp = Builder.CreateICmp(MinMaxPred, LHS, RHS); |
2999 | } else { |
3000 | IRBuilder<>::FastMathFlagGuard FMFG(Builder); |
3001 | auto FMF = |
3002 | cast<FPMathOperator>(SI.getCondition())->getFastMathFlags(); |
3003 | Builder.setFastMathFlags(FMF); |
3004 | Cmp = Builder.CreateFCmp(MinMaxPred, LHS, RHS); |
3005 | } |
3006 | |
3007 | Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI); |
3008 | if (!IsCastNeeded) |
3009 | return replaceInstUsesWith(SI, NewSI); |
3010 | |
3011 | Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType); |
3012 | return replaceInstUsesWith(SI, NewCast); |
3013 | } |
3014 | |
3015 | // MAX(~a, ~b) -> ~MIN(a, b) |
3016 | // MAX(~a, C) -> ~MIN(a, ~C) |
3017 | // MIN(~a, ~b) -> ~MAX(a, b) |
3018 | // MIN(~a, C) -> ~MAX(a, ~C) |
3019 | auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * { |
3020 | Value *A; |
3021 | if (match(X, m_Not(m_Value(A))) && !X->hasNUsesOrMore(3) && |
3022 | !isFreeToInvert(A, A->hasOneUse()) && |
3023 | // Passing false to only consider m_Not and constants. |
3024 | isFreeToInvert(Y, false)) { |
3025 | Value *B = Builder.CreateNot(Y); |
3026 | Value *NewMinMax = createMinMax(Builder, getInverseMinMaxFlavor(SPF), |
3027 | A, B); |
3028 | // Copy the profile metadata. |
3029 | if (MDNode *MD = SI.getMetadata(LLVMContext::MD_prof)) { |
3030 | cast<SelectInst>(NewMinMax)->setMetadata(LLVMContext::MD_prof, MD); |
3031 | // Swap the metadata if the operands are swapped. |
3032 | if (X == SI.getFalseValue() && Y == SI.getTrueValue()) |
3033 | cast<SelectInst>(NewMinMax)->swapProfMetadata(); |
3034 | } |
3035 | |
3036 | return BinaryOperator::CreateNot(NewMinMax); |
3037 | } |
3038 | |
3039 | return nullptr; |
3040 | }; |
3041 | |
3042 | if (Instruction *I = moveNotAfterMinMax(LHS, RHS)) |
3043 | return I; |
3044 | if (Instruction *I = moveNotAfterMinMax(RHS, LHS)) |
3045 | return I; |
3046 | |
3047 | if (Instruction *I = moveAddAfterMinMax(SPF, LHS, RHS, Builder)) |
3048 | return I; |
3049 | |
3050 | if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder)) |
3051 | return I; |
3052 | if (Instruction *I = matchSAddSubSat(SI)) |
3053 | return I; |
3054 | } |
3055 | } |
3056 | |
3057 | // Canonicalize select of FP values where NaN and -0.0 are not valid as |
3058 | // minnum/maxnum intrinsics. |
3059 | if (isa<FPMathOperator>(SI) && SI.hasNoNaNs() && SI.hasNoSignedZeros()) { |
3060 | Value *X, *Y; |
3061 | if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y)))) |
3062 | return replaceInstUsesWith( |
3063 | SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI)); |
3064 | |
3065 | if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y)))) |
3066 | return replaceInstUsesWith( |
3067 | SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI)); |
3068 | } |
3069 | |
3070 | // See if we can fold the select into a phi node if the condition is a select. |
3071 | if (auto *PN = dyn_cast<PHINode>(SI.getCondition())) |
3072 | // The true/false values have to be live in the PHI predecessor's blocks. |
3073 | if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) && |
3074 | canSelectOperandBeMappingIntoPredBlock(FalseVal, SI)) |
3075 | if (Instruction *NV = foldOpIntoPhi(SI, PN)) |
3076 | return NV; |
3077 | |
3078 | if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) { |
3079 | if (TrueSI->getCondition()->getType() == CondVal->getType()) { |
3080 | // select(C, select(C, a, b), c) -> select(C, a, c) |
3081 | if (TrueSI->getCondition() == CondVal) { |
3082 | if (SI.getTrueValue() == TrueSI->getTrueValue()) |
3083 | return nullptr; |
3084 | return replaceOperand(SI, 1, TrueSI->getTrueValue()); |
3085 | } |
3086 | // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b) |
3087 | // We choose this as normal form to enable folding on the And and |
3088 | // shortening paths for the values (this helps getUnderlyingObjects() for |
3089 | // example). |
3090 | if (TrueSI->getFalseValue() == FalseVal && TrueSI->hasOneUse()) { |
3091 | Value *And = Builder.CreateLogicalAnd(CondVal, TrueSI->getCondition()); |
3092 | replaceOperand(SI, 0, And); |
3093 | replaceOperand(SI, 1, TrueSI->getTrueValue()); |
3094 | return &SI; |
3095 | } |
3096 | } |
3097 | } |
3098 | if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) { |
3099 | if (FalseSI->getCondition()->getType() == CondVal->getType()) { |
3100 | // select(C, a, select(C, b, c)) -> select(C, a, c) |
3101 | if (FalseSI->getCondition() == CondVal) { |
3102 | if (SI.getFalseValue() == FalseSI->getFalseValue()) |
3103 | return nullptr; |
3104 | return replaceOperand(SI, 2, FalseSI->getFalseValue()); |
3105 | } |
3106 | // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b) |
3107 | if (FalseSI->getTrueValue() == TrueVal && FalseSI->hasOneUse()) { |
3108 | Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition()); |
3109 | replaceOperand(SI, 0, Or); |
3110 | replaceOperand(SI, 2, FalseSI->getFalseValue()); |
3111 | return &SI; |
3112 | } |
3113 | } |
3114 | } |
3115 | |
3116 | auto canMergeSelectThroughBinop = [](BinaryOperator *BO) { |
3117 | // The select might be preventing a division by 0. |
3118 | switch (BO->getOpcode()) { |
3119 | default: |
3120 | return true; |
3121 | case Instruction::SRem: |
3122 | case Instruction::URem: |
3123 | case Instruction::SDiv: |
3124 | case Instruction::UDiv: |
3125 | return false; |
3126 | } |
3127 | }; |
3128 | |
3129 | // Try to simplify a binop sandwiched between 2 selects with the same |
3130 | // condition. |
3131 | // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z) |
3132 | BinaryOperator *TrueBO; |
3133 | if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && |
3134 | canMergeSelectThroughBinop(TrueBO)) { |
3135 | if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) { |
3136 | if (TrueBOSI->getCondition() == CondVal) { |
3137 | replaceOperand(*TrueBO, 0, TrueBOSI->getTrueValue()); |
3138 | Worklist.push(TrueBO); |
3139 | return &SI; |
3140 | } |
3141 | } |
3142 | if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) { |
3143 | if (TrueBOSI->getCondition() == CondVal) { |
3144 | replaceOperand(*TrueBO, 1, TrueBOSI->getTrueValue()); |
3145 | Worklist.push(TrueBO); |
3146 | return &SI; |
3147 | } |
3148 | } |
3149 | } |
3150 | |
3151 | // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W)) |
3152 | BinaryOperator *FalseBO; |
3153 | if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) && |
3154 | canMergeSelectThroughBinop(FalseBO)) { |
3155 | if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) { |
3156 | if (FalseBOSI->getCondition() == CondVal) { |
3157 | replaceOperand(*FalseBO, 0, FalseBOSI->getFalseValue()); |
3158 | Worklist.push(FalseBO); |
3159 | return &SI; |
3160 | } |
3161 | } |
3162 | if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) { |
3163 | if (FalseBOSI->getCondition() == CondVal) { |
3164 | replaceOperand(*FalseBO, 1, FalseBOSI->getFalseValue()); |
3165 | Worklist.push(FalseBO); |
3166 | return &SI; |
3167 | } |
3168 | } |
3169 | } |
3170 | |
3171 | Value *NotCond; |
3172 | if (match(CondVal, m_Not(m_Value(NotCond))) && |
3173 | !InstCombiner::shouldAvoidAbsorbingNotIntoSelect(SI)) { |
3174 | replaceOperand(SI, 0, NotCond); |
3175 | SI.swapValues(); |
3176 | SI.swapProfMetadata(); |
3177 | return &SI; |
3178 | } |
3179 | |
3180 | if (Instruction *I = foldVectorSelect(SI)) |
3181 | return I; |
3182 | |
3183 | // If we can compute the condition, there's no need for a select. |
3184 | // Like the above fold, we are attempting to reduce compile-time cost by |
3185 | // putting this fold here with limitations rather than in InstSimplify. |
3186 | // The motivation for this call into value tracking is to take advantage of |
3187 | // the assumption cache, so make sure that is populated. |
3188 | if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) { |
3189 | KnownBits Known(1); |
3190 | computeKnownBits(CondVal, Known, 0, &SI); |
3191 | if (Known.One.isOneValue()) |
3192 | return replaceInstUsesWith(SI, TrueVal); |
3193 | if (Known.Zero.isOneValue()) |
3194 | return replaceInstUsesWith(SI, FalseVal); |
3195 | } |
3196 | |
3197 | if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder)) |
3198 | return BitCastSel; |
3199 | |
3200 | // Simplify selects that test the returned flag of cmpxchg instructions. |
3201 | if (Value *V = foldSelectCmpXchg(SI)) |
3202 | return replaceInstUsesWith(SI, V); |
3203 | |
3204 | if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI, *this)) |
3205 | return Select; |
3206 | |
3207 | if (Instruction *Funnel = foldSelectFunnelShift(SI, Builder)) |
3208 | return Funnel; |
3209 | |
3210 | if (Instruction *Copysign = foldSelectToCopysign(SI, Builder)) |
3211 | return Copysign; |
3212 | |
3213 | if (Instruction *PN = foldSelectToPhi(SI, DT, Builder)) |
3214 | return replaceInstUsesWith(SI, PN); |
3215 | |
3216 | if (Value *Fr = foldSelectWithFrozenICmp(SI, Builder)) |
3217 | return replaceInstUsesWith(SI, Fr); |
3218 | |
3219 | // select(mask, mload(,,mask,0), 0) -> mload(,,mask,0) |
3220 | // Load inst is intentionally not checked for hasOneUse() |
3221 | if (match(FalseVal, m_Zero()) && |
3222 | match(TrueVal, m_MaskedLoad(m_Value(), m_Value(), m_Specific(CondVal), |
3223 | m_CombineOr(m_Undef(), m_Zero())))) { |
3224 | auto *MaskedLoad = cast<IntrinsicInst>(TrueVal); |
3225 | if (isa<UndefValue>(MaskedLoad->getArgOperand(3))) |
3226 | MaskedLoad->setArgOperand(3, FalseVal /* Zero */); |
3227 | return replaceInstUsesWith(SI, MaskedLoad); |
3228 | } |
3229 | |
3230 | Value *Mask; |
3231 | if (match(TrueVal, m_Zero()) && |
3232 | match(FalseVal, m_MaskedLoad(m_Value(), m_Value(), m_Value(Mask), |
3233 | m_CombineOr(m_Undef(), m_Zero()))) && |
3234 | (CondVal->getType() == Mask->getType())) { |
3235 | // We can remove the select by ensuring the load zeros all lanes the |
3236 | // select would have. We determine this by proving there is no overlap |
3237 | // between the load and select masks. |
3238 | // (i.e (load_mask & select_mask) == 0 == no overlap) |
3239 | bool CanMergeSelectIntoLoad = false; |
3240 | if (Value *V = SimplifyAndInst(CondVal, Mask, SQ.getWithInstruction(&SI))) |
3241 | CanMergeSelectIntoLoad = match(V, m_Zero()); |
3242 | |
3243 | if (CanMergeSelectIntoLoad) { |
3244 | auto *MaskedLoad = cast<IntrinsicInst>(FalseVal); |
3245 | if (isa<UndefValue>(MaskedLoad->getArgOperand(3))) |
3246 | MaskedLoad->setArgOperand(3, TrueVal /* Zero */); |
3247 | return replaceInstUsesWith(SI, MaskedLoad); |
3248 | } |
3249 | } |
3250 | |
3251 | return nullptr; |
3252 | } |