Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
Line
Count
Source (jump to first uncovered line)
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/ValueTracking.h"
22
#include "llvm/IR/BasicBlock.h"
23
#include "llvm/IR/Constant.h"
24
#include "llvm/IR/Constants.h"
25
#include "llvm/IR/DerivedTypes.h"
26
#include "llvm/IR/IRBuilder.h"
27
#include "llvm/IR/InstrTypes.h"
28
#include "llvm/IR/Instruction.h"
29
#include "llvm/IR/Instructions.h"
30
#include "llvm/IR/IntrinsicInst.h"
31
#include "llvm/IR/Intrinsics.h"
32
#include "llvm/IR/Operator.h"
33
#include "llvm/IR/PatternMatch.h"
34
#include "llvm/IR/Type.h"
35
#include "llvm/IR/User.h"
36
#include "llvm/IR/Value.h"
37
#include "llvm/Support/Casting.h"
38
#include "llvm/Support/ErrorHandling.h"
39
#include "llvm/Support/KnownBits.h"
40
#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
41
#include <cassert>
42
#include <utility>
43
44
using namespace llvm;
45
using namespace PatternMatch;
46
47
#define DEBUG_TYPE "instcombine"
48
49
static Value *createMinMax(InstCombiner::BuilderTy &Builder,
50
391
                           SelectPatternFlavor SPF, Value *A, Value *B) {
51
391
  CmpInst::Predicate Pred = getMinMaxPred(SPF);
52
391
  assert(CmpInst::isIntPredicate(Pred) && "Expected integer predicate");
53
391
  return Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B);
54
391
}
55
56
/// Replace a select operand based on an equality comparison with the identity
57
/// constant of a binop.
58
static Instruction *foldSelectBinOpIdentity(SelectInst &Sel,
59
1.16M
                                            const TargetLibraryInfo &TLI) {
60
1.16M
  // The select condition must be an equality compare with a constant operand.
61
1.16M
  Value *X;
62
1.16M
  Constant *C;
63
1.16M
  CmpInst::Predicate Pred;
64
1.16M
  if (!match(Sel.getCondition(), m_Cmp(Pred, m_Value(X), m_Constant(C))))
65
416k
    return nullptr;
66
751k
67
751k
  bool IsEq;
68
751k
  if (ICmpInst::isEquality(Pred))
69
291k
    IsEq = Pred == ICmpInst::ICMP_EQ;
70
460k
  else if (Pred == FCmpInst::FCMP_OEQ)
71
2.59k
    IsEq = true;
72
457k
  else if (Pred == FCmpInst::FCMP_UNE)
73
121
    IsEq = false;
74
457k
  else
75
457k
    return nullptr;
76
293k
77
293k
  // A select operand must be a binop.
78
293k
  BinaryOperator *BO;
79
293k
  if (!match(Sel.getOperand(IsEq ? 
1286k
:
26.91k
), m_BinOp(BO)))
80
257k
    return nullptr;
81
36.3k
82
36.3k
  // The compare constant must be the identity constant for that binop.
83
36.3k
  // If this a floating-point compare with 0.0, any zero constant will do.
84
36.3k
  Type *Ty = BO->getType();
85
36.3k
  Constant *IdC = ConstantExpr::getBinOpIdentity(BO->getOpcode(), Ty, true);
86
36.3k
  if (IdC != C) {
87
11.5k
    if (!IdC || 
!CmpInst::isFPPredicate(Pred)11.5k
)
88
11.4k
      return nullptr;
89
75
    if (!match(IdC, m_AnyZeroFP()) || 
!match(C, m_AnyZeroFP())72
)
90
48
      return nullptr;
91
24.8k
  }
92
24.8k
93
24.8k
  // Last, match the compare variable operand with a binop operand.
94
24.8k
  Value *Y;
95
24.8k
  if (!BO->isCommutative() && 
!match(BO, m_BinOp(m_Value(Y), m_Specific(X)))4.20k
)
96
4.19k
    return nullptr;
97
20.6k
  if (!match(BO, m_c_BinOp(m_Value(Y), m_Specific(X))))
98
20.6k
    return nullptr;
99
45
100
45
  // +0.0 compares equal to -0.0, and so it does not behave as required for this
101
45
  // transform. Bail out if we can not exclude that possibility.
102
45
  if (isa<FPMathOperator>(BO))
103
23
    if (!BO->hasNoSignedZeros() && 
!CannotBeNegativeZero(Y, &TLI)14
)
104
6
      return nullptr;
105
39
106
39
  // BO = binop Y, X
107
39
  // S = { select (cmp eq X, C), BO, ? } or { select (cmp ne X, C), ?, BO }
108
39
  // =>
109
39
  // S = { select (cmp eq X, C),  Y, ? } or { select (cmp ne X, C), ?,  Y }
110
39
  Sel.setOperand(IsEq ? 
126
:
213
, Y);
111
39
  return &Sel;
112
39
}
113
114
/// This folds:
115
///  select (icmp eq (and X, C1)), TC, FC
116
///    iff C1 is a power 2 and the difference between TC and FC is a power-of-2.
117
/// To something like:
118
///  (shr (and (X, C1)), (log2(C1) - log2(TC-FC))) + FC
119
/// Or:
120
///  (shl (and (X, C1)), (log2(TC-FC) - log2(C1))) + FC
121
/// With some variations depending if FC is larger than TC, or the shift
122
/// isn't needed, or the bit widths don't match.
123
static Value *foldSelectICmpAnd(SelectInst &Sel, ICmpInst *Cmp,
124
1.02M
                                InstCombiner::BuilderTy &Builder) {
125
1.02M
  const APInt *SelTC, *SelFC;
126
1.02M
  if (!match(Sel.getTrueValue(), m_APInt(SelTC)) ||
127
1.02M
      
!match(Sel.getFalseValue(), m_APInt(SelFC))243k
)
128
893k
    return nullptr;
129
130k
130
130k
  // If this is a vector select, we need a vector compare.
131
130k
  Type *SelType = Sel.getType();
132
130k
  if (SelType->isVectorTy() != Cmp->getType()->isVectorTy())
133
2
    return nullptr;
134
130k
135
130k
  Value *V;
136
130k
  APInt AndMask;
137
130k
  bool CreateAnd = false;
138
130k
  ICmpInst::Predicate Pred = Cmp->getPredicate();
139
130k
  if (ICmpInst::isEquality(Pred)) {
140
87.8k
    if (!match(Cmp->getOperand(1), m_Zero()))
141
8.05k
      return nullptr;
142
79.7k
143
79.7k
    V = Cmp->getOperand(0);
144
79.7k
    const APInt *AndRHS;
145
79.7k
    if (!match(V, m_And(m_Value(), m_Power2(AndRHS))))
146
78.2k
      return nullptr;
147
1.51k
148
1.51k
    AndMask = *AndRHS;
149
43.1k
  } else if (decomposeBitTestICmp(Cmp->getOperand(0), Cmp->getOperand(1),
150
43.1k
                                  Pred, V, AndMask)) {
151
3.73k
    assert(ICmpInst::isEquality(Pred) && "Not equality test?");
152
3.73k
    if (!AndMask.isPowerOf2())
153
917
      return nullptr;
154
2.81k
155
2.81k
    CreateAnd = true;
156
39.4k
  } else {
157
39.4k
    return nullptr;
158
39.4k
  }
159
4.33k
160
4.33k
  // In general, when both constants are non-zero, we would need an offset to
161
4.33k
  // replace the select. This would require more instructions than we started
162
4.33k
  // with. But there's one special-case that we handle here because it can
163
4.33k
  // simplify/reduce the instructions.
164
4.33k
  APInt TC = *SelTC;
165
4.33k
  APInt FC = *SelFC;
166
4.33k
  if (!TC.isNullValue() && 
!FC.isNullValue()4.22k
) {
167
4.15k
    // If the select constants differ by exactly one bit and that's the same
168
4.15k
    // bit that is masked and checked by the select condition, the select can
169
4.15k
    // be replaced by bitwise logic to set/clear one bit of the constant result.
170
4.15k
    if (TC.getBitWidth() != AndMask.getBitWidth() || 
(TC ^ FC) != AndMask2.10k
)
171
4.13k
      return nullptr;
172
19
    if (CreateAnd) {
173
8
      // If we have to create an 'and', then we must kill the cmp to not
174
8
      // increase the instruction count.
175
8
      if (!Cmp->hasOneUse())
176
4
        return nullptr;
177
4
      V = Builder.CreateAnd(V, ConstantInt::get(SelType, AndMask));
178
4
    }
179
19
    bool ExtraBitInTC = TC.ugt(FC);
180
15
    if (Pred == ICmpInst::ICMP_EQ) {
181
11
      // If the masked bit in V is clear, clear or set the bit in the result:
182
11
      // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) ^ TC
183
11
      // (V & AndMaskC) == 0 ? TC : FC --> (V & AndMaskC) | TC
184
11
      Constant *C = ConstantInt::get(SelType, TC);
185
11
      return ExtraBitInTC ? 
Builder.CreateXor(V, C)4
:
Builder.CreateOr(V, C)7
;
186
11
    }
187
4
    if (Pred == ICmpInst::ICMP_NE) {
188
4
      // If the masked bit in V is set, set or clear the bit in the result:
189
4
      // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) | FC
190
4
      // (V & AndMaskC) != 0 ? TC : FC --> (V & AndMaskC) ^ FC
191
4
      Constant *C = ConstantInt::get(SelType, FC);
192
4
      return ExtraBitInTC ? 
Builder.CreateOr(V, C)2
:
Builder.CreateXor(V, C)2
;
193
4
    }
194
0
    llvm_unreachable("Only expecting equality predicates");
195
0
  }
196
179
197
179
  // Make sure one of the select arms is a power-of-2.
198
179
  if (!TC.isPowerOf2() && 
!FC.isPowerOf2()109
)
199
82
    return nullptr;
200
97
201
97
  // Determine which shift is needed to transform result of the 'and' into the
202
97
  // desired result.
203
97
  const APInt &ValC = !TC.isNullValue() ? 
TC70
:
FC27
;
204
97
  unsigned ValZeros = ValC.logBase2();
205
97
  unsigned AndZeros = AndMask.logBase2();
206
97
207
97
  // Insert the 'and' instruction on the input to the truncate.
208
97
  if (CreateAnd)
209
67
    V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), AndMask));
210
97
211
97
  // If types don't match, we can still convert the select by introducing a zext
212
97
  // or a trunc of the 'and'.
213
97
  if (ValZeros > AndZeros) {
214
39
    V = Builder.CreateZExtOrTrunc(V, SelType);
215
39
    V = Builder.CreateShl(V, ValZeros - AndZeros);
216
58
  } else if (ValZeros < AndZeros) {
217
20
    V = Builder.CreateLShr(V, AndZeros - ValZeros);
218
20
    V = Builder.CreateZExtOrTrunc(V, SelType);
219
38
  } else {
220
38
    V = Builder.CreateZExtOrTrunc(V, SelType);
221
38
  }
222
97
223
97
  // Okay, now we know that everything is set up, we just don't know whether we
224
97
  // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
225
97
  bool ShouldNotVal = !TC.isNullValue();
226
97
  ShouldNotVal ^= Pred == ICmpInst::ICMP_NE;
227
97
  if (ShouldNotVal)
228
2
    V = Builder.CreateXor(V, ValC);
229
97
230
97
  return V;
231
97
}
232
233
/// We want to turn code that looks like this:
234
///   %C = or %A, %B
235
///   %D = select %cond, %C, %A
236
/// into:
237
///   %C = select %cond, %B, 0
238
///   %D = or %A, %C
239
///
240
/// Assuming that the specified instruction is an operand to the select, return
241
/// a bitmask indicating which operands of this instruction are foldable if they
242
/// equal the other incoming value of the select.
243
186k
static unsigned getSelectFoldableOperands(BinaryOperator *I) {
244
186k
  switch (I->getOpcode()) {
245
186k
  case Instruction::Add:
246
85.9k
  case Instruction::Mul:
247
85.9k
  case Instruction::And:
248
85.9k
  case Instruction::Or:
249
85.9k
  case Instruction::Xor:
250
85.9k
    return 3;              // Can fold through either operand.
251
89.0k
  case Instruction::Sub:   // Can only fold on the amount subtracted.
252
89.0k
  case Instruction::Shl:   // Can only fold on the shift amount.
253
89.0k
  case Instruction::LShr:
254
89.0k
  case Instruction::AShr:
255
89.0k
    return 1;
256
89.0k
  default:
257
11.4k
    return 0;              // Cannot fold
258
186k
  }
259
186k
}
260
261
/// For the same transformation as the previous function, return the identity
262
/// constant that goes into the select.
263
35.2k
static APInt getSelectFoldableConstant(BinaryOperator *I) {
264
35.2k
  switch (I->getOpcode()) {
265
35.2k
  
default: 0
llvm_unreachable0
("This cannot happen!");
266
35.2k
  case Instruction::Add:
267
34.9k
  case Instruction::Sub:
268
34.9k
  case Instruction::Or:
269
34.9k
  case Instruction::Xor:
270
34.9k
  case Instruction::Shl:
271
34.9k
  case Instruction::LShr:
272
34.9k
  case Instruction::AShr:
273
34.9k
    return APInt::getNullValue(I->getType()->getScalarSizeInBits());
274
34.9k
  case Instruction::And:
275
173
    return APInt::getAllOnesValue(I->getType()->getScalarSizeInBits());
276
34.9k
  case Instruction::Mul:
277
34
    return APInt(I->getType()->getScalarSizeInBits(), 1);
278
35.2k
  }
279
35.2k
}
280
281
/// We have (select c, TI, FI), and we know that TI and FI have the same opcode.
282
Instruction *InstCombiner::foldSelectOpOp(SelectInst &SI, Instruction *TI,
283
141k
                                          Instruction *FI) {
284
141k
  // Don't break up min/max patterns. The hasOneUse checks below prevent that
285
141k
  // for most cases, but vector min/max with bitcasts can be transformed. If the
286
141k
  // one-use restrictions are eased for other patterns, we still don't want to
287
141k
  // obfuscate min/max.
288
141k
  if ((match(&SI, m_SMin(m_Value(), m_Value())) ||
289
141k
       
match(&SI, m_SMax(m_Value(), m_Value()))135k
||
290
141k
       
match(&SI, m_UMin(m_Value(), m_Value()))127k
||
291
141k
       
match(&SI, m_UMax(m_Value(), m_Value()))121k
))
292
63.3k
    return nullptr;
293
77.7k
294
77.7k
  // If this is a cast from the same type, merge.
295
77.7k
  Value *Cond = SI.getCondition();
296
77.7k
  Type *CondTy = Cond->getType();
297
77.7k
  if (TI->getNumOperands() == 1 && 
TI->isCast()9.38k
) {
298
4.93k
    Type *FIOpndTy = FI->getOperand(0)->getType();
299
4.93k
    if (TI->getOperand(0)->getType() != FIOpndTy)
300
1.64k
      return nullptr;
301
3.29k
302
3.29k
    // The select condition may be a vector. We may only change the operand
303
3.29k
    // type if the vector width remains the same (and matches the condition).
304
3.29k
    if (CondTy->isVectorTy()) {
305
41
      if (!FIOpndTy->isVectorTy())
306
5
        return nullptr;
307
36
      if (CondTy->getVectorNumElements() != FIOpndTy->getVectorNumElements())
308
25
        return nullptr;
309
11
310
11
      // TODO: If the backend knew how to deal with casts better, we could
311
11
      // remove this limitation. For now, there's too much potential to create
312
11
      // worse codegen by promoting the select ahead of size-altering casts
313
11
      // (PR28160).
314
11
      //
315
11
      // Note that ValueTracking's matchSelectPattern() looks through casts
316
11
      // without checking 'hasOneUse' when it matches min/max patterns, so this
317
11
      // transform may end up happening anyway.
318
11
      if (TI->getOpcode() != Instruction::BitCast &&
319
11
          
(2
!TI->hasOneUse()2
||
!FI->hasOneUse()0
))
320
2
        return nullptr;
321
3.25k
    } else if (!TI->hasOneUse() || 
!FI->hasOneUse()493
) {
322
3.21k
      // TODO: The one-use restrictions for a scalar select could be eased if
323
3.21k
      // the fold of a select in visitLoadInst() was enhanced to match a pattern
324
3.21k
      // that includes a cast.
325
3.21k
      return nullptr;
326
3.21k
    }
327
49
328
49
    // Fold this by inserting a select from the input values.
329
49
    Value *NewSI =
330
49
        Builder.CreateSelect(Cond, TI->getOperand(0), FI->getOperand(0),
331
49
                             SI.getName() + ".v", &SI);
332
49
    return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI,
333
49
                            TI->getType());
334
49
  }
335
72.8k
336
72.8k
  // Cond ? -X : -Y --> -(Cond ? X : Y)
337
72.8k
  Value *X, *Y;
338
72.8k
  if (match(TI, m_FNeg(m_Value(X))) && 
match(FI, m_FNeg(m_Value(Y)))81
&&
339
72.8k
      
(9
TI->hasOneUse()9
||
FI->hasOneUse()3
)) {
340
8
    Value *NewSel = Builder.CreateSelect(Cond, X, Y, SI.getName() + ".v", &SI);
341
8
    // TODO: Remove the hack for the binop form when the unary op is optimized
342
8
    //       properly with all IR passes.
343
8
    if (TI->getOpcode() != Instruction::FNeg)
344
3
      return BinaryOperator::CreateFNegFMF(NewSel, cast<BinaryOperator>(TI));
345
5
    return UnaryOperator::CreateFNeg(NewSel);
346
5
  }
347
72.8k
348
72.8k
  // Only handle binary operators (including two-operand getelementptr) with
349
72.8k
  // one-use here. As with the cast case above, it may be possible to relax the
350
72.8k
  // one-use constraint, but that needs be examined carefully since it may not
351
72.8k
  // reduce the total number of instructions.
352
72.8k
  if (TI->getNumOperands() != 2 || 
FI->getNumOperands() != 228.3k
||
353
72.8k
      
(27.8k
!isa<BinaryOperator>(TI)27.8k
&&
!isa<GetElementPtrInst>(TI)14.0k
) ||
354
72.8k
      
!TI->hasOneUse()18.5k
||
!FI->hasOneUse()13.5k
)
355
69.1k
    return nullptr;
356
3.65k
357
3.65k
  // Figure out if the operations have any operands in common.
358
3.65k
  Value *MatchOp, *OtherOpT, *OtherOpF;
359
3.65k
  bool MatchIsOpZero;
360
3.65k
  if (TI->getOperand(0) == FI->getOperand(0)) {
361
185
    MatchOp  = TI->getOperand(0);
362
185
    OtherOpT = TI->getOperand(1);
363
185
    OtherOpF = FI->getOperand(1);
364
185
    MatchIsOpZero = true;
365
3.47k
  } else if (TI->getOperand(1) == FI->getOperand(1)) {
366
30
    MatchOp  = TI->getOperand(1);
367
30
    OtherOpT = TI->getOperand(0);
368
30
    OtherOpF = FI->getOperand(0);
369
30
    MatchIsOpZero = false;
370
3.44k
  } else if (!TI->isCommutative()) {
371
3.23k
    return nullptr;
372
3.23k
  } else 
if (208
TI->getOperand(0) == FI->getOperand(1)208
) {
373
25
    MatchOp  = TI->getOperand(0);
374
25
    OtherOpT = TI->getOperand(1);
375
25
    OtherOpF = FI->getOperand(0);
376
25
    MatchIsOpZero = true;
377
183
  } else if (TI->getOperand(1) == FI->getOperand(0)) {
378
1
    MatchOp  = TI->getOperand(1);
379
1
    OtherOpT = TI->getOperand(0);
380
1
    OtherOpF = FI->getOperand(1);
381
1
    MatchIsOpZero = true;
382
182
  } else {
383
182
    return nullptr;
384
182
  }
385
241
386
241
  // If the select condition is a vector, the operands of the original select's
387
241
  // operands also must be vectors. This may not be the case for getelementptr
388
241
  // for example.
389
241
  if (CondTy->isVectorTy() && 
(4
!OtherOpT->getType()->isVectorTy()4
||
390
4
                               
!OtherOpF->getType()->isVectorTy()3
))
391
1
    return nullptr;
392
240
393
240
  // If we reach here, they do have operations in common.
394
240
  Value *NewSI = Builder.CreateSelect(Cond, OtherOpT, OtherOpF,
395
240
                                      SI.getName() + ".v", &SI);
396
240
  Value *Op0 = MatchIsOpZero ? 
MatchOp211
:
NewSI29
;
397
240
  Value *Op1 = MatchIsOpZero ? 
NewSI211
:
MatchOp29
;
398
240
  if (auto *BO = dyn_cast<BinaryOperator>(TI)) {
399
224
    BinaryOperator *NewBO = BinaryOperator::Create(BO->getOpcode(), Op0, Op1);
400
224
    NewBO->copyIRFlags(TI);
401
224
    NewBO->andIRFlags(FI);
402
224
    return NewBO;
403
224
  }
404
16
  if (auto *TGEP = dyn_cast<GetElementPtrInst>(TI)) {
405
16
    auto *FGEP = cast<GetElementPtrInst>(FI);
406
16
    Type *ElementType = TGEP->getResultElementType();
407
16
    return TGEP->isInBounds() && 
FGEP->isInBounds()14
408
16
               ? 
GetElementPtrInst::CreateInBounds(ElementType, Op0, {Op1})13
409
16
               : 
GetElementPtrInst::Create(ElementType, Op0, {Op1})3
;
410
16
  }
411
0
  llvm_unreachable("Expected BinaryOperator or GEP");
412
0
  return nullptr;
413
0
}
414
415
34.6k
static bool isSelect01(const APInt &C1I, const APInt &C2I) {
416
34.6k
  if (!C1I.isNullValue() && 
!C2I.isNullValue()198
) // One side must be zero.
417
198
    return false;
418
34.4k
  return C1I.isOneValue() || C1I.isAllOnesValue() ||
419
34.4k
         C2I.isOneValue() || 
C2I.isAllOnesValue()33.5k
;
420
34.4k
}
421
422
/// Try to fold the select into one of the operands to allow further
423
/// optimization.
424
Instruction *InstCombiner::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,
425
991k
                                            Value *FalseVal) {
426
991k
  // See the comment above GetSelectFoldableOperands for a description of the
427
991k
  // transformation we are doing here.
428
991k
  if (auto *TVI = dyn_cast<BinaryOperator>(TrueVal)) {
429
286k
    if (TVI->hasOneUse() && 
!isa<Constant>(FalseVal)163k
) {
430
145k
      if (unsigned SFO = getSelectFoldableOperands(TVI)) {
431
137k
        unsigned OpToFold = 0;
432
137k
        if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
433
28.5k
          OpToFold = 1;
434
108k
        } else if ((SFO & 2) && 
FalseVal == TVI->getOperand(1)25.3k
) {
435
10
          OpToFold = 2;
436
10
        }
437
137k
438
137k
        if (OpToFold) {
439
28.6k
          APInt CI = getSelectFoldableConstant(TVI);
440
28.6k
          Value *OOp = TVI->getOperand(2-OpToFold);
441
28.6k
          // Avoid creating select between 2 constants unless it's selecting
442
28.6k
          // between 0, 1 and -1.
443
28.6k
          const APInt *OOpC;
444
28.6k
          bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
445
28.6k
          if (!isa<Constant>(OOp) || 
(28.3k
OOpIsAPInt28.3k
&&
isSelect01(CI, *OOpC)28.3k
)) {
446
896
            Value *C = ConstantInt::get(OOp->getType(), CI);
447
896
            Value *NewSel = Builder.CreateSelect(SI.getCondition(), OOp, C);
448
896
            NewSel->takeName(TVI);
449
896
            BinaryOperator *BO = BinaryOperator::Create(TVI->getOpcode(),
450
896
                                                        FalseVal, NewSel);
451
896
            BO->copyIRFlags(TVI);
452
896
            return BO;
453
896
          }
454
990k
        }
455
137k
      }
456
145k
    }
457
286k
  }
458
990k
459
990k
  if (auto *FVI = dyn_cast<BinaryOperator>(FalseVal)) {
460
169k
    if (FVI->hasOneUse() && 
!isa<Constant>(TrueVal)68.2k
) {
461
41.3k
      if (unsigned SFO = getSelectFoldableOperands(FVI)) {
462
37.9k
        unsigned OpToFold = 0;
463
37.9k
        if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
464
6.51k
          OpToFold = 1;
465
31.4k
        } else if ((SFO & 2) && 
TrueVal == FVI->getOperand(1)25.7k
) {
466
91
          OpToFold = 2;
467
91
        }
468
37.9k
469
37.9k
        if (OpToFold) {
470
6.60k
          APInt CI = getSelectFoldableConstant(FVI);
471
6.60k
          Value *OOp = FVI->getOperand(2-OpToFold);
472
6.60k
          // Avoid creating select between 2 constants unless it's selecting
473
6.60k
          // between 0, 1 and -1.
474
6.60k
          const APInt *OOpC;
475
6.60k
          bool OOpIsAPInt = match(OOp, m_APInt(OOpC));
476
6.60k
          if (!isa<Constant>(OOp) || 
(6.26k
OOpIsAPInt6.26k
&&
isSelect01(CI, *OOpC)6.26k
)) {
477
707
            Value *C = ConstantInt::get(OOp->getType(), CI);
478
707
            Value *NewSel = Builder.CreateSelect(SI.getCondition(), C, OOp);
479
707
            NewSel->takeName(FVI);
480
707
            BinaryOperator *BO = BinaryOperator::Create(FVI->getOpcode(),
481
707
                                                        TrueVal, NewSel);
482
707
            BO->copyIRFlags(FVI);
483
707
            return BO;
484
707
          }
485
989k
        }
486
37.9k
      }
487
41.3k
    }
488
169k
  }
489
989k
490
989k
  return nullptr;
491
989k
}
492
493
/// We want to turn:
494
///   (select (icmp eq (and X, Y), 0), (and (lshr X, Z), 1), 1)
495
/// into:
496
///   zext (icmp ne i32 (and X, (or Y, (shl 1, Z))), 0)
497
/// Note:
498
///   Z may be 0 if lshr is missing.
499
/// Worst-case scenario is that we will replace 5 instructions with 5 different
500
/// instructions, but we got rid of select.
501
static Instruction *foldSelectICmpAndAnd(Type *SelType, const ICmpInst *Cmp,
502
                                         Value *TVal, Value *FVal,
503
1.02M
                                         InstCombiner::BuilderTy &Builder) {
504
1.02M
  if (!(Cmp->hasOneUse() && 
Cmp->getOperand(0)->hasOneUse()839k
&&
505
1.02M
        
Cmp->getPredicate() == ICmpInst::ICMP_EQ208k
&&
506
1.02M
        
match(Cmp->getOperand(1), m_Zero())167k
&&
match(FVal, m_One())123k
))
507
1.02M
    return nullptr;
508
1.24k
509
1.24k
  // The TrueVal has general form of:  and %B, 1
510
1.24k
  Value *B;
511
1.24k
  if (!match(TVal, m_OneUse(m_And(m_Value(B), m_One()))))
512
1.21k
    return nullptr;
513
29
514
29
  // Where %B may be optionally shifted:  lshr %X, %Z.
515
29
  Value *X, *Z;
516
29
  const bool HasShift = match(B, m_OneUse(m_LShr(m_Value(X), m_Value(Z))));
517
29
  if (!HasShift)
518
9
    X = B;
519
29
520
29
  Value *Y;
521
29
  if (!match(Cmp->getOperand(0), m_c_And(m_Specific(X), m_Value(Y))))
522
2
    return nullptr;
523
27
524
27
  // ((X & Y) == 0) ? ((X >> Z) & 1) : 1 --> (X & (Y | (1 << Z))) != 0
525
27
  // ((X & Y) == 0) ? (X & 1) : 1 --> (X & (Y | 1)) != 0
526
27
  Constant *One = ConstantInt::get(SelType, 1);
527
27
  Value *MaskB = HasShift ? 
Builder.CreateShl(One, Z)19
:
One8
;
528
27
  Value *FullMask = Builder.CreateOr(Y, MaskB);
529
27
  Value *MaskedX = Builder.CreateAnd(X, FullMask);
530
27
  Value *ICmpNeZero = Builder.CreateIsNotNull(MaskedX);
531
27
  return new ZExtInst(ICmpNeZero, SelType);
532
27
}
533
534
/// We want to turn:
535
///   (select (icmp sgt x, C), lshr (X, Y), ashr (X, Y)); iff C s>= -1
536
///   (select (icmp slt x, C), ashr (X, Y), lshr (X, Y)); iff C s>= 0
537
/// into:
538
///   ashr (X, Y)
539
static Value *foldSelectICmpLshrAshr(const ICmpInst *IC, Value *TrueVal,
540
                                     Value *FalseVal,
541
1.02M
                                     InstCombiner::BuilderTy &Builder) {
542
1.02M
  ICmpInst::Predicate Pred = IC->getPredicate();
543
1.02M
  Value *CmpLHS = IC->getOperand(0);
544
1.02M
  Value *CmpRHS = IC->getOperand(1);
545
1.02M
  if (!CmpRHS->getType()->isIntOrIntVectorTy())
546
94.3k
    return nullptr;
547
929k
548
929k
  Value *X, *Y;
549
929k
  unsigned Bitwidth = CmpRHS->getType()->getScalarSizeInBits();
550
929k
  if ((Pred != ICmpInst::ICMP_SGT ||
551
929k
       !match(CmpRHS,
552
184k
              m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, -1)))) &&
553
929k
      
(775k
Pred != ICmpInst::ICMP_SLT775k
||
554
775k
       !match(CmpRHS,
555
216k
              m_SpecificInt_ICMP(ICmpInst::ICMP_SGE, APInt(Bitwidth, 0)))))
556
598k
    return nullptr;
557
330k
558
330k
  // Canonicalize so that ashr is in FalseVal.
559
330k
  if (Pred == ICmpInst::ICMP_SLT)
560
176k
    std::swap(TrueVal, FalseVal);
561
330k
562
330k
  if (match(TrueVal, m_LShr(m_Value(X), m_Value(Y))) &&
563
330k
      
match(FalseVal, m_AShr(m_Specific(X), m_Specific(Y)))63
&&
564
330k
      
match(CmpLHS, m_Specific(X))23
) {
565
21
    const auto *Ashr = cast<Instruction>(FalseVal);
566
21
    // if lshr is not exact and ashr is, this new ashr must not be exact.
567
21
    bool IsExact = Ashr->isExact() && 
cast<Instruction>(TrueVal)->isExact()15
;
568
21
    return Builder.CreateAShr(X, Y, IC->getName(), IsExact);
569
21
  }
570
330k
571
330k
  return nullptr;
572
330k
}
573
574
/// We want to turn:
575
///   (select (icmp eq (and X, C1), 0), Y, (or Y, C2))
576
/// into:
577
///   (or (shl (and X, C1), C3), Y)
578
/// iff:
579
///   C1 and C2 are both powers of 2
580
/// where:
581
///   C3 = Log(C2) - Log(C1)
582
///
583
/// This transform handles cases where:
584
/// 1. The icmp predicate is inverted
585
/// 2. The select operands are reversed
586
/// 3. The magnitude of C2 and C1 are flipped
587
static Value *foldSelectICmpAndOr(const ICmpInst *IC, Value *TrueVal,
588
                                  Value *FalseVal,
589
1.02M
                                  InstCombiner::BuilderTy &Builder) {
590
1.02M
  // Only handle integer compares. Also, if this is a vector select, we need a
591
1.02M
  // vector compare.
592
1.02M
  if (!TrueVal->getType()->isIntOrIntVectorTy() ||
593
1.02M
      
TrueVal->getType()->isVectorTy() != IC->getType()->isVectorTy()834k
)
594
189k
    return nullptr;
595
834k
596
834k
  Value *CmpLHS = IC->getOperand(0);
597
834k
  Value *CmpRHS = IC->getOperand(1);
598
834k
599
834k
  Value *V;
600
834k
  unsigned C1Log;
601
834k
  bool IsEqualZero;
602
834k
  bool NeedAnd = false;
603
834k
  if (IC->isEquality()) {
604
251k
    if (!match(CmpRHS, m_Zero()))
605
92.4k
      return nullptr;
606
159k
607
159k
    const APInt *C1;
608
159k
    if (!match(CmpLHS, m_And(m_Value(), m_Power2(C1))))
609
144k
      return nullptr;
610
14.7k
611
14.7k
    V = CmpLHS;
612
14.7k
    C1Log = C1->logBase2();
613
14.7k
    IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_EQ;
614
582k
  } else if (IC->getPredicate() == ICmpInst::ICMP_SLT ||
615
582k
             
IC->getPredicate() == ICmpInst::ICMP_SGT399k
) {
616
364k
    // We also need to recognize (icmp slt (trunc (X)), 0) and
617
364k
    // (icmp sgt (trunc (X)), -1).
618
364k
    IsEqualZero = IC->getPredicate() == ICmpInst::ICMP_SGT;
619
364k
    if ((IsEqualZero && 
!match(CmpRHS, m_AllOnes())181k
) ||
620
364k
        
(191k
!IsEqualZero191k
&&
!match(CmpRHS, m_Zero())183k
))
621
246k
      return nullptr;
622
117k
623
117k
    if (!match(CmpLHS, m_OneUse(m_Trunc(m_Value(V)))))
624
117k
      return nullptr;
625
218
626
218
    C1Log = CmpLHS->getType()->getScalarSizeInBits() - 1;
627
218
    NeedAnd = true;
628
218k
  } else {
629
218k
    return nullptr;
630
218k
  }
631
15.0k
632
15.0k
  const APInt *C2;
633
15.0k
  bool OrOnTrueVal = false;
634
15.0k
  bool OrOnFalseVal = match(FalseVal, m_Or(m_Specific(TrueVal), m_Power2(C2)));
635
15.0k
  if (!OrOnFalseVal)
636
14.8k
    OrOnTrueVal = match(TrueVal, m_Or(m_Specific(FalseVal), m_Power2(C2)));
637
15.0k
638
15.0k
  if (!OrOnFalseVal && 
!OrOnTrueVal14.8k
)
639
14.8k
    return nullptr;
640
172
641
172
  Value *Y = OrOnFalseVal ? 
TrueVal143
:
FalseVal29
;
642
172
643
172
  unsigned C2Log = C2->logBase2();
644
172
645
172
  bool NeedXor = (!IsEqualZero && 
OrOnFalseVal10
) ||
(163
IsEqualZero163
&&
OrOnTrueVal162
);
646
172
  bool NeedShift = C1Log != C2Log;
647
172
  bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
648
172
                       V->getType()->getScalarSizeInBits();
649
172
650
172
  // Make sure we don't create more instructions than we save.
651
172
  Value *Or = OrOnFalseVal ? 
FalseVal143
:
TrueVal29
;
652
172
  if ((NeedShift + NeedXor + NeedZExtTrunc) >
653
172
      (IC->hasOneUse() + Or->hasOneUse()))
654
27
    return nullptr;
655
145
656
145
  if (NeedAnd) {
657
4
    // Insert the AND instruction on the input to the truncate.
658
4
    APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log);
659
4
    V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
660
4
  }
661
145
662
145
  if (C2Log > C1Log) {
663
66
    V = Builder.CreateZExtOrTrunc(V, Y->getType());
664
66
    V = Builder.CreateShl(V, C2Log - C1Log);
665
79
  } else if (C1Log > C2Log) {
666
63
    V = Builder.CreateLShr(V, C1Log - C2Log);
667
63
    V = Builder.CreateZExtOrTrunc(V, Y->getType());
668
63
  } else
669
16
    V = Builder.CreateZExtOrTrunc(V, Y->getType());
670
145
671
145
  if (NeedXor)
672
12
    V = Builder.CreateXor(V, *C2);
673
145
674
145
  return Builder.CreateOr(V, Y);
675
145
}
676
677
/// Transform patterns such as (a > b) ? a - b : 0 into usub.sat(a, b).
678
/// There are 8 commuted/swapped variants of this pattern.
679
/// TODO: Also support a - UMIN(a,b) patterns.
680
static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,
681
                                            const Value *TrueVal,
682
                                            const Value *FalseVal,
683
1.02M
                                            InstCombiner::BuilderTy &Builder) {
684
1.02M
  ICmpInst::Predicate Pred = ICI->getPredicate();
685
1.02M
  if (!ICmpInst::isUnsigned(Pred))
686
741k
    return nullptr;
687
282k
688
282k
  // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
689
282k
  if (match(TrueVal, m_Zero())) {
690
2.25k
    Pred = ICmpInst::getInversePredicate(Pred);
691
2.25k
    std::swap(TrueVal, FalseVal);
692
2.25k
  }
693
282k
  if (!match(FalseVal, m_Zero()))
694
269k
    return nullptr;
695
13.1k
696
13.1k
  Value *A = ICI->getOperand(0);
697
13.1k
  Value *B = ICI->getOperand(1);
698
13.1k
  if (Pred == ICmpInst::ICMP_ULE || 
Pred == ICmpInst::ICMP_ULT12.6k
) {
699
9.93k
    // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
700
9.93k
    std::swap(A, B);
701
9.93k
    Pred = ICmpInst::getSwappedPredicate(Pred);
702
9.93k
  }
703
13.1k
704
13.1k
  assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
705
13.1k
         "Unexpected isUnsigned predicate!");
706
13.1k
707
13.1k
  // Account for swapped form of subtraction: ((a > b) ? b - a : 0).
708
13.1k
  bool IsNegative = false;
709
13.1k
  if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A))))
710
4
    IsNegative = true;
711
13.1k
  else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))))
712
13.1k
    return nullptr;
713
45
714
45
  // If sub is used anywhere else, we wouldn't be able to eliminate it
715
45
  // afterwards.
716
45
  if (!TrueVal->hasOneUse())
717
0
    return nullptr;
718
45
719
45
  // (a > b) ? a - b : 0 -> usub.sat(a, b)
720
45
  // (a > b) ? b - a : 0 -> -usub.sat(a, b)
721
45
  Value *Result = Builder.CreateBinaryIntrinsic(Intrinsic::usub_sat, A, B);
722
45
  if (IsNegative)
723
4
    Result = Builder.CreateNeg(Result);
724
45
  return Result;
725
45
}
726
727
static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
728
1.02M
                                       InstCombiner::BuilderTy &Builder) {
729
1.02M
  if (!Cmp->hasOneUse())
730
184k
    return nullptr;
731
839k
732
839k
  // Match unsigned saturated add with constant.
733
839k
  Value *Cmp0 = Cmp->getOperand(0);
734
839k
  Value *Cmp1 = Cmp->getOperand(1);
735
839k
  ICmpInst::Predicate Pred = Cmp->getPredicate();
736
839k
  Value *X;
737
839k
  const APInt *C, *CmpC;
738
839k
  if (Pred == ICmpInst::ICMP_ULT &&
739
839k
      
match(TVal, m_Add(m_Value(X), m_APInt(C)))142k
&&
X == Cmp017.7k
&&
740
839k
      
match(FVal, m_AllOnes())119
&&
match(Cmp1, m_APInt(CmpC))2
&&
*CmpC == ~*C2
) {
741
2
    // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
742
2
    return Builder.CreateBinaryIntrinsic(
743
2
        Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
744
2
  }
745
839k
746
839k
  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
747
839k
  // There are 8 commuted variants.
748
839k
  // Canonicalize -1 (saturated result) to true value of the select. Just
749
839k
  // swapping the compare operands is legal, because the selected value is the
750
839k
  // same in case of equality, so we can interchange u< and u<=.
751
839k
  if (match(FVal, m_AllOnes())) {
752
46.6k
    std::swap(TVal, FVal);
753
46.6k
    std::swap(Cmp0, Cmp1);
754
46.6k
  }
755
839k
  if (!match(TVal, m_AllOnes()))
756
784k
    return nullptr;
757
55.1k
758
55.1k
  // Canonicalize predicate to 'ULT'.
759
55.1k
  if (Pred == ICmpInst::ICMP_UGT) {
760
489
    Pred = ICmpInst::ICMP_ULT;
761
489
    std::swap(Cmp0, Cmp1);
762
489
  }
763
55.1k
  if (Pred != ICmpInst::ICMP_ULT)
764
29.5k
    return nullptr;
765
25.6k
766
25.6k
  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
767
25.6k
  Value *Y;
768
25.6k
  if (match(Cmp0, m_Not(m_Value(X))) &&
769
25.6k
      
match(FVal, m_c_Add(m_Specific(X), m_Value(Y)))28
&&
Y == Cmp128
) {
770
28
    // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
771
28
    // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
772
28
    return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
773
28
  }
774
25.5k
  // The 'not' op may be included in the sum but not the compare.
775
25.5k
  X = Cmp0;
776
25.5k
  Y = Cmp1;
777
25.5k
  if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
778
8
    // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
779
8
    // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
780
8
    BinaryOperator *BO = cast<BinaryOperator>(FVal);
781
8
    return Builder.CreateBinaryIntrinsic(
782
8
        Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
783
8
  }
784
25.5k
785
25.5k
  return nullptr;
786
25.5k
}
787
788
/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
789
/// call to cttz/ctlz with flag 'is_zero_undef' cleared.
790
///
791
/// For example, we can fold the following code sequence:
792
/// \code
793
///   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
794
///   %1 = icmp ne i32 %x, 0
795
///   %2 = select i1 %1, i32 %0, i32 32
796
/// \code
797
///
798
/// into:
799
///   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
800
static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
801
1.02M
                                 InstCombiner::BuilderTy &Builder) {
802
1.02M
  ICmpInst::Predicate Pred = ICI->getPredicate();
803
1.02M
  Value *CmpLHS = ICI->getOperand(0);
804
1.02M
  Value *CmpRHS = ICI->getOperand(1);
805
1.02M
806
1.02M
  // Check if the condition value compares a value for equality against zero.
807
1.02M
  if (!ICI->isEquality() || 
!match(CmpRHS, m_Zero())340k
)
808
799k
    return nullptr;
809
224k
810
224k
  Value *Count = FalseVal;
811
224k
  Value *ValueOnZero = TrueVal;
812
224k
  if (Pred == ICmpInst::ICMP_NE)
813
6.74k
    std::swap(Count, ValueOnZero);
814
224k
815
224k
  // Skip zero extend/truncate.
816
224k
  Value *V = nullptr;
817
224k
  if (match(Count, m_ZExt(m_Value(V))) ||
818
224k
      
match(Count, m_Trunc(m_Value(V)))223k
)
819
1.26k
    Count = V;
820
224k
821
224k
  // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
822
224k
  // input to the cttz/ctlz is used as LHS for the compare instruction.
823
224k
  if (!match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) &&
824
224k
      
!match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))224k
)
825
224k
    return nullptr;
826
46
827
46
  IntrinsicInst *II = cast<IntrinsicInst>(Count);
828
46
829
46
  // Check if the value propagated on zero is a constant number equal to the
830
46
  // sizeof in bits of 'Count'.
831
46
  unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
832
46
  if (match(ValueOnZero, m_SpecificInt(SizeOfInBits))) {
833
34
    // Explicitly clear the 'undef_on_zero' flag.
834
34
    IntrinsicInst *NewI = cast<IntrinsicInst>(II->clone());
835
34
    NewI->setArgOperand(1, ConstantInt::getFalse(NewI->getContext()));
836
34
    Builder.Insert(NewI);
837
34
    return Builder.CreateZExtOrTrunc(NewI, ValueOnZero->getType());
838
34
  }
839
12
840
12
  // If the ValueOnZero is not the bitwidth, we can at least make use of the
841
12
  // fact that the cttz/ctlz result will not be used if the input is zero, so
842
12
  // it's okay to relax it to undef for that case.
843
12
  if (II->hasOneUse() && 
!match(II->getArgOperand(1), m_One())8
)
844
4
    II->setArgOperand(1, ConstantInt::getTrue(II->getContext()));
845
12
846
12
  return nullptr;
847
12
}
848
849
/// Return true if we find and adjust an icmp+select pattern where the compare
850
/// is with a constant that can be incremented or decremented to match the
851
/// minimum or maximum idiom.
852
1.02M
static bool adjustMinMax(SelectInst &Sel, ICmpInst &Cmp) {
853
1.02M
  ICmpInst::Predicate Pred = Cmp.getPredicate();
854
1.02M
  Value *CmpLHS = Cmp.getOperand(0);
855
1.02M
  Value *CmpRHS = Cmp.getOperand(1);
856
1.02M
  Value *TrueVal = Sel.getTrueValue();
857
1.02M
  Value *FalseVal = Sel.getFalseValue();
858
1.02M
859
1.02M
  // We may move or edit the compare, so make sure the select is the only user.
860
1.02M
  const APInt *CmpC;
861
1.02M
  if (!Cmp.hasOneUse() || 
!match(CmpRHS, m_APInt(CmpC))839k
)
862
441k
    return false;
863
582k
864
582k
  // These transforms only work for selects of integers or vector selects of
865
582k
  // integer vectors.
866
582k
  Type *SelTy = Sel.getType();
867
582k
  auto *SelEltTy = dyn_cast<IntegerType>(SelTy->getScalarType());
868
582k
  if (!SelEltTy || 
SelTy->isVectorTy() != Cmp.getType()->isVectorTy()512k
)
869
70.7k
    return false;
870
512k
871
512k
  Constant *AdjustedRHS;
872
512k
  if (Pred == ICmpInst::ICMP_UGT || 
Pred == ICmpInst::ICMP_SGT462k
)
873
184k
    AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC + 1);
874
327k
  else if (Pred == ICmpInst::ICMP_ULT || 
Pred == ICmpInst::ICMP_SLT287k
)
875
158k
    AdjustedRHS = ConstantInt::get(CmpRHS->getType(), *CmpC - 1);
876
169k
  else
877
169k
    return false;
878
342k
879
342k
  // X > C ? X : C+1  -->  X < C+1 ? C+1 : X
880
342k
  // X < C ? X : C-1  -->  X > C-1 ? C-1 : X
881
342k
  if ((CmpLHS == TrueVal && 
AdjustedRHS == FalseVal163k
) ||
882
342k
      
(342k
CmpLHS == FalseVal342k
&&
AdjustedRHS == TrueVal72.3k
)) {
883
78
    ; // Nothing to do here. Values match without any sign/zero extension.
884
78
  }
885
342k
  // Types do not match. Instead of calculating this with mixed types, promote
886
342k
  // all to the larger type. This enables scalar evolution to analyze this
887
342k
  // expression.
888
342k
  else if (CmpRHS->getType()->getScalarSizeInBits() < SelEltTy->getBitWidth()) {
889
8.95k
    Constant *SextRHS = ConstantExpr::getSExt(AdjustedRHS, SelTy);
890
8.95k
891
8.95k
    // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
892
8.95k
    // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
893
8.95k
    // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
894
8.95k
    // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
895
8.95k
    if (match(TrueVal, m_SExt(m_Specific(CmpLHS))) && 
SextRHS == FalseVal13
) {
896
9
      CmpLHS = TrueVal;
897
9
      AdjustedRHS = SextRHS;
898
8.94k
    } else if (match(FalseVal, m_SExt(m_Specific(CmpLHS))) &&
899
8.94k
               
SextRHS == TrueVal267
) {
900
5
      CmpLHS = FalseVal;
901
5
      AdjustedRHS = SextRHS;
902
8.94k
    } else if (Cmp.isUnsigned()) {
903
902
      Constant *ZextRHS = ConstantExpr::getZExt(AdjustedRHS, SelTy);
904
902
      // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
905
902
      // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
906
902
      // zext + signed compare cannot be changed:
907
902
      //    0xff <s 0x00, but 0x00ff >s 0x0000
908
902
      if (match(TrueVal, m_ZExt(m_Specific(CmpLHS))) && 
ZextRHS == FalseVal7
) {
909
4
        CmpLHS = TrueVal;
910
4
        AdjustedRHS = ZextRHS;
911
898
      } else if (match(FalseVal, m_ZExt(m_Specific(CmpLHS))) &&
912
898
                 
ZextRHS == TrueVal6
) {
913
0
        CmpLHS = FalseVal;
914
0
        AdjustedRHS = ZextRHS;
915
898
      } else {
916
898
        return false;
917
898
      }
918
8.04k
    } else {
919
8.04k
      return false;
920
8.04k
    }
921
333k
  } else {
922
333k
    return false;
923
333k
  }
924
96
925
96
  Pred = ICmpInst::getSwappedPredicate(Pred);
926
96
  CmpRHS = AdjustedRHS;
927
96
  std::swap(FalseVal, TrueVal);
928
96
  Cmp.setPredicate(Pred);
929
96
  Cmp.setOperand(0, CmpLHS);
930
96
  Cmp.setOperand(1, CmpRHS);
931
96
  Sel.setOperand(1, TrueVal);
932
96
  Sel.setOperand(2, FalseVal);
933
96
  Sel.swapProfMetadata();
934
96
935
96
  // Move the compare instruction right before the select instruction. Otherwise
936
96
  // the sext/zext value may be defined after the compare instruction uses it.
937
96
  Cmp.moveBefore(&Sel);
938
96
939
96
  return true;
940
96
}
941
942
/// If this is an integer min/max (icmp + select) with a constant operand,
943
/// create the canonical icmp for the min/max operation and canonicalize the
944
/// constant to the 'false' operand of the select:
945
/// select (icmp Pred X, C1), C2, X --> select (icmp Pred' X, C2), X, C2
946
/// Note: if C1 != C2, this will change the icmp constant to the existing
947
/// constant operand of the select.
948
static Instruction *
949
canonicalizeMinMaxWithConstant(SelectInst &Sel, ICmpInst &Cmp,
950
1.03M
                               InstCombiner::BuilderTy &Builder) {
951
1.03M
  if (!Cmp.hasOneUse() || 
!isa<Constant>(Cmp.getOperand(1))847k
)
952
432k
    return nullptr;
953
600k
954
600k
  // Canonicalize the compare predicate based on whether we have min or max.
955
600k
  Value *LHS, *RHS;
956
600k
  SelectPatternResult SPR = matchSelectPattern(&Sel, LHS, RHS);
957
600k
  if (!SelectPatternResult::isMinOrMax(SPR.Flavor))
958
429k
    return nullptr;
959
170k
960
170k
  // Is this already canonical?
961
170k
  ICmpInst::Predicate CanonicalPred = getMinMaxPred(SPR.Flavor);
962
170k
  if (Cmp.getOperand(0) == LHS && 
Cmp.getOperand(1) == RHS170k
&&
963
170k
      
Cmp.getPredicate() == CanonicalPred170k
)
964
162k
    return nullptr;
965
7.93k
966
7.93k
  // Create the canonical compare and plug it into the select.
967
7.93k
  Sel.setCondition(Builder.CreateICmp(CanonicalPred, LHS, RHS));
968
7.93k
969
7.93k
  // If the select operands did not change, we're done.
970
7.93k
  if (Sel.getTrueValue() == LHS && 
Sel.getFalseValue() == RHS56
)
971
56
    return &Sel;
972
7.87k
973
7.87k
  // If we are swapping the select operands, swap the metadata too.
974
7.87k
  assert(Sel.getTrueValue() == RHS && Sel.getFalseValue() == LHS &&
975
7.87k
         "Unexpected results from matchSelectPattern");
976
7.87k
  Sel.setTrueValue(LHS);
977
7.87k
  Sel.setFalseValue(RHS);
978
7.87k
  Sel.swapProfMetadata();
979
7.87k
  return &Sel;
980
7.87k
}
981
982
/// There are many select variants for each of ABS/NABS.
983
/// In matchSelectPattern(), there are different compare constants, compare
984
/// predicates/operands and select operands.
985
/// In isKnownNegation(), there are different formats of negated operands.
986
/// Canonicalize all these variants to 1 pattern.
987
/// This makes CSE more likely.
988
static Instruction *canonicalizeAbsNabs(SelectInst &Sel, ICmpInst &Cmp,
989
1.02M
                                        InstCombiner::BuilderTy &Builder) {
990
1.02M
  if (!Cmp.hasOneUse() || 
!isa<Constant>(Cmp.getOperand(1))839k
)
991
432k
    return nullptr;
992
592k
993
592k
  // Choose a sign-bit check for the compare (likely simpler for codegen).
994
592k
  // ABS:  (X <s 0) ? -X : X
995
592k
  // NABS: (X <s 0) ? X : -X
996
592k
  Value *LHS, *RHS;
997
592k
  SelectPatternFlavor SPF = matchSelectPattern(&Sel, LHS, RHS).Flavor;
998
592k
  if (SPF != SelectPatternFlavor::SPF_ABS &&
999
592k
      
SPF != SelectPatternFlavor::SPF_NABS521k
)
1000
521k
    return nullptr;
1001
70.7k
1002
70.7k
  Value *TVal = Sel.getTrueValue();
1003
70.7k
  Value *FVal = Sel.getFalseValue();
1004
70.7k
  assert(isKnownNegation(TVal, FVal) &&
1005
70.7k
         "Unexpected result from matchSelectPattern");
1006
70.7k
1007
70.7k
  // The compare may use the negated abs()/nabs() operand, or it may use
1008
70.7k
  // negation in non-canonical form such as: sub A, B.
1009
70.7k
  bool CmpUsesNegatedOp = match(Cmp.getOperand(0), m_Neg(m_Specific(TVal))) ||
1010
70.7k
                          
match(Cmp.getOperand(0), m_Neg(m_Specific(FVal)))70.7k
;
1011
70.7k
1012
70.7k
  bool CmpCanonicalized = !CmpUsesNegatedOp &&
1013
70.7k
                          
match(Cmp.getOperand(1), m_ZeroInt())70.7k
&&
1014
70.7k
                          
Cmp.getPredicate() == ICmpInst::ICMP_SLT70.5k
;
1015
70.7k
  bool RHSCanonicalized = match(RHS, m_Neg(m_Specific(LHS)));
1016
70.7k
1017
70.7k
  // Is this already canonical?
1018
70.7k
  if (CmpCanonicalized && 
RHSCanonicalized70.5k
)
1019
70.5k
    return nullptr;
1020
238
1021
238
  // If RHS is used by other instructions except compare and select, don't
1022
238
  // canonicalize it to not increase the instruction count.
1023
238
  if (!(RHS->hasOneUse() || 
(19
RHS->hasNUses(2)19
&&
CmpUsesNegatedOp19
)))
1024
2
    return nullptr;
1025
236
1026
236
  // Create the canonical compare: icmp slt LHS 0.
1027
236
  if (!CmpCanonicalized) {
1028
236
    Cmp.setPredicate(ICmpInst::ICMP_SLT);
1029
236
    Cmp.setOperand(1, ConstantInt::getNullValue(Cmp.getOperand(0)->getType()));
1030
236
    if (CmpUsesNegatedOp)
1031
17
      Cmp.setOperand(0, LHS);
1032
236
  }
1033
236
1034
236
  // Create the canonical RHS: RHS = sub (0, LHS).
1035
236
  if (!RHSCanonicalized) {
1036
14
    assert(RHS->hasOneUse() && "RHS use number is not right");
1037
14
    RHS = Builder.CreateNeg(LHS);
1038
14
    if (TVal == LHS) {
1039
8
      Sel.setFalseValue(RHS);
1040
8
      FVal = RHS;
1041
8
    } else {
1042
6
      Sel.setTrueValue(RHS);
1043
6
      TVal = RHS;
1044
6
    }
1045
14
  }
1046
236
1047
236
  // If the select operands do not change, we're done.
1048
236
  if (SPF == SelectPatternFlavor::SPF_NABS) {
1049
62
    if (TVal == LHS)
1050
19
      return &Sel;
1051
43
    assert(FVal == LHS && "Unexpected results from matchSelectPattern");
1052
174
  } else {
1053
174
    if (FVal == LHS)
1054
21
      return &Sel;
1055
153
    assert(TVal == LHS && "Unexpected results from matchSelectPattern");
1056
153
  }
1057
236
1058
236
  // We are swapping the select operands, so swap the metadata too.
1059
236
  Sel.setTrueValue(FVal);
1060
196
  Sel.setFalseValue(TVal);
1061
196
  Sel.swapProfMetadata();
1062
196
  return &Sel;
1063
236
}
1064
1065
/// Visit a SelectInst that has an ICmpInst as its first operand.
1066
Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI,
1067
1.03M
                                                  ICmpInst *ICI) {
1068
1.03M
  Value *TrueVal = SI.getTrueValue();
1069
1.03M
  Value *FalseVal = SI.getFalseValue();
1070
1.03M
1071
1.03M
  if (Instruction *NewSel = canonicalizeMinMaxWithConstant(SI, *ICI, Builder))
1072
7.93k
    return NewSel;
1073
1.02M
1074
1.02M
  if (Instruction *NewAbs = canonicalizeAbsNabs(SI, *ICI, Builder))
1075
236
    return NewAbs;
1076
1.02M
1077
1.02M
  bool Changed = adjustMinMax(SI, *ICI);
1078
1.02M
1079
1.02M
  if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
1080
112
    return replaceInstUsesWith(SI, V);
1081
1.02M
1082
1.02M
  // NOTE: if we wanted to, this is where to detect integer MIN/MAX
1083
1.02M
  ICmpInst::Predicate Pred = ICI->getPredicate();
1084
1.02M
  Value *CmpLHS = ICI->getOperand(0);
1085
1.02M
  Value *CmpRHS = ICI->getOperand(1);
1086
1.02M
  if (CmpRHS != CmpLHS && 
isa<Constant>(CmpRHS)1.02M
) {
1087
734k
    if (CmpLHS == TrueVal && 
Pred == ICmpInst::ICMP_EQ164k
) {
1088
42
      // Transform (X == C) ? X : Y -> (X == C) ? C : Y
1089
42
      SI.setOperand(1, CmpRHS);
1090
42
      Changed = true;
1091
734k
    } else if (CmpLHS == FalseVal && 
Pred == ICmpInst::ICMP_NE124k
) {
1092
0
      // Transform (X != C) ? Y : X -> (X != C) ? Y : C
1093
0
      SI.setOperand(2, CmpRHS);
1094
0
      Changed = true;
1095
0
    }
1096
734k
  }
1097
1.02M
1098
1.02M
  // FIXME: This code is nearly duplicated in InstSimplify. Using/refactoring
1099
1.02M
  // decomposeBitTestICmp() might help.
1100
1.02M
  {
1101
1.02M
    unsigned BitWidth =
1102
1.02M
        DL.getTypeSizeInBits(TrueVal->getType()->getScalarType());
1103
1.02M
    APInt MinSignedValue = APInt::getSignedMinValue(BitWidth);
1104
1.02M
    Value *X;
1105
1.02M
    const APInt *Y, *C;
1106
1.02M
    bool TrueWhenUnset;
1107
1.02M
    bool IsBitTest = false;
1108
1.02M
    if (ICmpInst::isEquality(Pred) &&
1109
1.02M
        
match(CmpLHS, m_And(m_Value(X), m_Power2(Y)))340k
&&
1110
1.02M
        
match(CmpRHS, m_Zero())48.1k
) {
1111
48.1k
      IsBitTest = true;
1112
48.1k
      TrueWhenUnset = Pred == ICmpInst::ICMP_EQ;
1113
976k
    } else if (Pred == ICmpInst::ICMP_SLT && 
match(CmpRHS, m_Zero())216k
) {
1114
140k
      X = CmpLHS;
1115
140k
      Y = &MinSignedValue;
1116
140k
      IsBitTest = true;
1117
140k
      TrueWhenUnset = false;
1118
836k
    } else if (Pred == ICmpInst::ICMP_SGT && 
match(CmpRHS, m_AllOnes())184k
) {
1119
8.40k
      X = CmpLHS;
1120
8.40k
      Y = &MinSignedValue;
1121
8.40k
      IsBitTest = true;
1122
8.40k
      TrueWhenUnset = true;
1123
8.40k
    }
1124
1.02M
    if (IsBitTest) {
1125
196k
      Value *V = nullptr;
1126
196k
      // (X & Y) == 0 ? X : X ^ Y  --> X & ~Y
1127
196k
      if (TrueWhenUnset && 
TrueVal == X55.7k
&&
1128
196k
          
match(FalseVal, m_Xor(m_Specific(X), m_APInt(C)))492
&&
*Y == *C2
)
1129
2
        V = Builder.CreateAnd(X, ~(*Y));
1130
196k
      // (X & Y) != 0 ? X ^ Y : X  --> X & ~Y
1131
196k
      else if (!TrueWhenUnset && 
FalseVal == X140k
&&
1132
196k
               
match(TrueVal, m_Xor(m_Specific(X), m_APInt(C)))72.4k
&&
*Y == *C1
)
1133
0
        V = Builder.CreateAnd(X, ~(*Y));
1134
196k
      // (X & Y) == 0 ? X ^ Y : X  --> X | Y
1135
196k
      else if (TrueWhenUnset && 
FalseVal == X55.7k
&&
1136
196k
               
match(TrueVal, m_Xor(m_Specific(X), m_APInt(C)))63
&&
*Y == *C2
)
1137
2
        V = Builder.CreateOr(X, *Y);
1138
196k
      // (X & Y) != 0 ? X : X ^ Y  --> X | Y
1139
196k
      else if (!TrueWhenUnset && 
TrueVal == X140k
&&
1140
196k
               
match(FalseVal, m_Xor(m_Specific(X), m_APInt(C)))670
&&
*Y == *C2
)
1141
2
        V = Builder.CreateOr(X, *Y);
1142
196k
1143
196k
      if (V)
1144
6
        return replaceInstUsesWith(SI, V);
1145
1.02M
    }
1146
1.02M
  }
1147
1.02M
1148
1.02M
  if (Instruction *V =
1149
27
          foldSelectICmpAndAnd(SI.getType(), ICI, TrueVal, FalseVal, Builder))
1150
27
    return V;
1151
1.02M
1152
1.02M
  if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
1153
145
    return replaceInstUsesWith(SI, V);
1154
1.02M
1155
1.02M
  if (Value *V = foldSelectICmpLshrAshr(ICI, TrueVal, FalseVal, Builder))
1156
21
    return replaceInstUsesWith(SI, V);
1157
1.02M
1158
1.02M
  if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
1159
34
    return replaceInstUsesWith(SI, V);
1160
1.02M
1161
1.02M
  if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
1162
45
    return replaceInstUsesWith(SI, V);
1163
1.02M
1164
1.02M
  if (Value *V = canonicalizeSaturatedAdd(ICI, TrueVal, FalseVal, Builder))
1165
38
    return replaceInstUsesWith(SI, V);
1166
1.02M
1167
1.02M
  return Changed ? 
&SI138
:
nullptr1.02M
;
1168
1.02M
}
1169
1170
/// SI is a select whose condition is a PHI node (but the two may be in
1171
/// different blocks). See if the true/false values (V) are live in all of the
1172
/// predecessor blocks of the PHI. For example, cases like this can't be mapped:
1173
///
1174
///   X = phi [ C1, BB1], [C2, BB2]
1175
///   Y = add
1176
///   Z = select X, Y, 0
1177
///
1178
/// because Y is not live in BB1/BB2.
1179
static bool canSelectOperandBeMappingIntoPredBlock(const Value *V,
1180
5.53k
                                                   const SelectInst &SI) {
1181
5.53k
  // If the value is a non-instruction value like a constant or argument, it
1182
5.53k
  // can always be mapped.
1183
5.53k
  const Instruction *I = dyn_cast<Instruction>(V);
1184
5.53k
  if (!I) 
return true2.89k
;
1185
2.63k
1186
2.63k
  // If V is a PHI node defined in the same block as the condition PHI, we can
1187
2.63k
  // map the arguments.
1188
2.63k
  const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
1189
2.63k
1190
2.63k
  if (const PHINode *VP = dyn_cast<PHINode>(I))
1191
1.30k
    if (VP->getParent() == CondPHI->getParent())
1192
691
      return true;
1193
1.94k
1194
1.94k
  // Otherwise, if the PHI and select are defined in the same block and if V is
1195
1.94k
  // defined in a different block, then we can transform it.
1196
1.94k
  if (SI.getParent() == CondPHI->getParent() &&
1197
1.94k
      
I->getParent() != CondPHI->getParent()831
)
1198
516
    return true;
1199
1.43k
1200
1.43k
  // Otherwise we have a 'hard' case and we can't tell without doing more
1201
1.43k
  // detailed dominator based analysis, punt.
1202
1.43k
  return false;
1203
1.43k
}
1204
1205
/// We have an SPF (e.g. a min or max) of an SPF of the form:
1206
///   SPF2(SPF1(A, B), C)
1207
Instruction *InstCombiner::foldSPFofSPF(Instruction *Inner,
1208
                                        SelectPatternFlavor SPF1,
1209
                                        Value *A, Value *B,
1210
                                        Instruction &Outer,
1211
58.3k
                                        SelectPatternFlavor SPF2, Value *C) {
1212
58.3k
  if (Outer.getType() != Inner->getType())
1213
10
    return nullptr;
1214
58.3k
1215
58.3k
  if (C == A || 
C == B58.3k
) {
1216
15
    // MAX(MAX(A, B), B) -> MAX(A, B)
1217
15
    // MIN(MIN(a, b), a) -> MIN(a, b)
1218
15
    // TODO: This could be done in instsimplify.
1219
15
    if (SPF1 == SPF2 && 
SelectPatternResult::isMinOrMax(SPF1)6
)
1220
6
      return replaceInstUsesWith(Outer, Inner);
1221
9
1222
9
    // MAX(MIN(a, b), a) -> a
1223
9
    // MIN(MAX(a, b), a) -> a
1224
9
    // TODO: This could be done in instsimplify.
1225
9
    if ((SPF1 == SPF_SMIN && 
SPF2 == SPF_SMAX2
) ||
1226
9
        
(7
SPF1 == SPF_SMAX7
&&
SPF2 == SPF_SMIN1
) ||
1227
9
        
(6
SPF1 == SPF_UMIN6
&&
SPF2 == SPF_UMAX0
) ||
1228
9
        
(6
SPF1 == SPF_UMAX6
&&
SPF2 == SPF_UMIN0
))
1229
3
      return replaceInstUsesWith(Outer, C);
1230
58.3k
  }
1231
58.3k
1232
58.3k
  if (SPF1 == SPF2) {
1233
42.9k
    const APInt *CB, *CC;
1234
42.9k
    if (match(B, m_APInt(CB)) && 
match(C, m_APInt(CC))309
) {
1235
12
      // MIN(MIN(A, 23), 97) -> MIN(A, 23)
1236
12
      // MAX(MAX(A, 97), 23) -> MAX(A, 97)
1237
12
      // TODO: This could be done in instsimplify.
1238
12
      if ((SPF1 == SPF_UMIN && 
CB->ule(*CC)1
) ||
1239
12
          (SPF1 == SPF_SMIN && 
CB->sle(*CC)6
) ||
1240
12
          (SPF1 == SPF_UMAX && 
CB->uge(*CC)1
) ||
1241
12
          (SPF1 == SPF_SMAX && 
CB->sge(*CC)4
))
1242
0
        return replaceInstUsesWith(Outer, Inner);
1243
12
1244
12
      // MIN(MIN(A, 97), 23) -> MIN(A, 23)
1245
12
      // MAX(MAX(A, 23), 97) -> MAX(A, 97)
1246
12
      if ((SPF1 == SPF_UMIN && 
CB->ugt(*CC)1
) ||
1247
12
          
(11
SPF1 == SPF_SMIN11
&&
CB->sgt(*CC)6
) ||
1248
12
          
(5
SPF1 == SPF_UMAX5
&&
CB->ult(*CC)1
) ||
1249
12
          
(4
SPF1 == SPF_SMAX4
&&
CB->slt(*CC)4
)) {
1250
12
        Outer.replaceUsesOfWith(Inner, A);
1251
12
        return &Outer;
1252
12
      }
1253
58.3k
    }
1254
42.9k
  }
1255
58.3k
1256
58.3k
  // ABS(ABS(X)) -> ABS(X)
1257
58.3k
  // NABS(NABS(X)) -> NABS(X)
1258
58.3k
  // TODO: This could be done in instsimplify.
1259
58.3k
  if (SPF1 == SPF2 && 
(42.9k
SPF1 == SPF_ABS42.9k
||
SPF1 == SPF_NABS42.9k
)) {
1260
22
    return replaceInstUsesWith(Outer, Inner);
1261
22
  }
1262
58.3k
1263
58.3k
  // ABS(NABS(X)) -> ABS(X)
1264
58.3k
  // NABS(ABS(X)) -> NABS(X)
1265
58.3k
  if ((SPF1 == SPF_ABS && 
SPF2 == SPF_NABS349
) ||
1266
58.3k
      
(58.2k
SPF1 == SPF_NABS58.2k
&&
SPF2 == SPF_ABS14
)) {
1267
24
    SelectInst *SI = cast<SelectInst>(Inner);
1268
24
    Value *NewSI =
1269
24
        Builder.CreateSelect(SI->getCondition(), SI->getFalseValue(),
1270
24
                             SI->getTrueValue(), SI->getName(), SI);
1271
24
    return replaceInstUsesWith(Outer, NewSI);
1272
24
  }
1273
58.2k
1274
58.2k
  auto IsFreeOrProfitableToInvert =
1275
58.4k
      [&](Value *V, Value *&NotV, bool &ElidesXor) {
1276
58.4k
    if (match(V, m_Not(m_Value(NotV)))) {
1277
13
      // If V has at most 2 uses then we can get rid of the xor operation
1278
13
      // entirely.
1279
13
      ElidesXor |= !V->hasNUsesOrMore(3);
1280
13
      return true;
1281
13
    }
1282
58.4k
1283
58.4k
    if (IsFreeToInvert(V, !V->hasNUsesOrMore(3))) {
1284
533
      NotV = nullptr;
1285
533
      return true;
1286
533
    }
1287
57.8k
1288
57.8k
    return false;
1289
57.8k
  };
1290
58.2k
1291
58.2k
  Value *NotA, *NotB, *NotC;
1292
58.2k
  bool ElidesXor = false;
1293
58.2k
1294
58.2k
  // MIN(MIN(~A, ~B), ~C) == ~MAX(MAX(A, B), C)
1295
58.2k
  // MIN(MAX(~A, ~B), ~C) == ~MAX(MIN(A, B), C)
1296
58.2k
  // MAX(MIN(~A, ~B), ~C) == ~MIN(MAX(A, B), C)
1297
58.2k
  // MAX(MAX(~A, ~B), ~C) == ~MIN(MIN(A, B), C)
1298
58.2k
  //
1299
58.2k
  // This transform is performance neutral if we can elide at least one xor from
1300
58.2k
  // the set of three operands, since we'll be tacking on an xor at the very
1301
58.2k
  // end.
1302
58.2k
  if (SelectPatternResult::isMinOrMax(SPF1) &&
1303
58.2k
      
SelectPatternResult::isMinOrMax(SPF2)57.9k
&&
1304
58.2k
      
IsFreeOrProfitableToInvert(A, NotA, ElidesXor)57.9k
&&
1305
58.2k
      
IsFreeOrProfitableToInvert(B, NotB, ElidesXor)376
&&
1306
58.2k
      
IsFreeOrProfitableToInvert(C, NotC, ElidesXor)118
&&
ElidesXor52
) {
1307
1
    if (!NotA)
1308
0
      NotA = Builder.CreateNot(A);
1309
1
    if (!NotB)
1310
0
      NotB = Builder.CreateNot(B);
1311
1
    if (!NotC)
1312
0
      NotC = Builder.CreateNot(C);
1313
1
1314
1
    Value *NewInner = createMinMax(Builder, getInverseMinMaxFlavor(SPF1), NotA,
1315
1
                                   NotB);
1316
1
    Value *NewOuter = Builder.CreateNot(
1317
1
        createMinMax(Builder, getInverseMinMaxFlavor(SPF2), NewInner, NotC));
1318
1
    return replaceInstUsesWith(Outer, NewOuter);
1319
1
  }
1320
58.2k
1321
58.2k
  return nullptr;
1322
58.2k
}
1323
1324
/// Turn select C, (X + Y), (X - Y) --> (X + (select C, Y, (-Y))).
1325
/// This is even legal for FP.
1326
static Instruction *foldAddSubSelect(SelectInst &SI,
1327
1.17M
                                     InstCombiner::BuilderTy &Builder) {
1328
1.17M
  Value *CondVal = SI.getCondition();
1329
1.17M
  Value *TrueVal = SI.getTrueValue();
1330
1.17M
  Value *FalseVal = SI.getFalseValue();
1331
1.17M
  auto *TI = dyn_cast<Instruction>(TrueVal);
1332
1.17M
  auto *FI = dyn_cast<Instruction>(FalseVal);
1333
1.17M
  if (!TI || 
!FI750k
||
!TI->hasOneUse()506k
||
!FI->hasOneUse()239k
)
1334
1.07M
    return nullptr;
1335
96.5k
1336
96.5k
  Instruction *AddOp = nullptr, *SubOp = nullptr;
1337
96.5k
  if ((TI->getOpcode() == Instruction::Sub &&
1338
96.5k
       
FI->getOpcode() == Instruction::Add4.04k
) ||
1339
96.5k
      
(95.3k
TI->getOpcode() == Instruction::FSub95.3k
&&
1340
95.3k
       
FI->getOpcode() == Instruction::FAdd46
)) {
1341
1.18k
    AddOp = FI;
1342
1.18k
    SubOp = TI;
1343
95.3k
  } else if ((FI->getOpcode() == Instruction::Sub &&
1344
95.3k
              
TI->getOpcode() == Instruction::Add3.09k
) ||
1345
95.3k
             
(95.0k
FI->getOpcode() == Instruction::FSub95.0k
&&
1346
95.0k
              
TI->getOpcode() == Instruction::FAdd43
)) {
1347
275
    AddOp = TI;
1348
275
    SubOp = FI;
1349
275
  }
1350
96.5k
1351
96.5k
  if (AddOp) {
1352
1.45k
    Value *OtherAddOp = nullptr;
1353
1.45k
    if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
1354
30
      OtherAddOp = AddOp->getOperand(1);
1355
1.42k
    } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
1356
11
      OtherAddOp = AddOp->getOperand(0);
1357
11
    }
1358
1.45k
1359
1.45k
    if (OtherAddOp) {
1360
41
      // So at this point we know we have (Y -> OtherAddOp):
1361
41
      //        select C, (add X, Y), (sub X, Z)
1362
41
      Value *NegVal; // Compute -Z
1363
41
      if (SI.getType()->isFPOrFPVectorTy()) {
1364
9
        NegVal = Builder.CreateFNeg(SubOp->getOperand(1));
1365
9
        if (Instruction *NegInst = dyn_cast<Instruction>(NegVal)) {
1366
9
          FastMathFlags Flags = AddOp->getFastMathFlags();
1367
9
          Flags &= SubOp->getFastMathFlags();
1368
9
          NegInst->setFastMathFlags(Flags);
1369
9
        }
1370
32
      } else {
1371
32
        NegVal = Builder.CreateNeg(SubOp->getOperand(1));
1372
32
      }
1373
41
1374
41
      Value *NewTrueOp = OtherAddOp;
1375
41
      Value *NewFalseOp = NegVal;
1376
41
      if (AddOp != TI)
1377
25
        std::swap(NewTrueOp, NewFalseOp);
1378
41
      Value *NewSel = Builder.CreateSelect(CondVal, NewTrueOp, NewFalseOp,
1379
41
                                           SI.getName() + ".p", &SI);
1380
41
1381
41
      if (SI.getType()->isFPOrFPVectorTy()) {
1382
9
        Instruction *RI =
1383
9
            BinaryOperator::CreateFAdd(SubOp->getOperand(0), NewSel);
1384
9
1385
9
        FastMathFlags Flags = AddOp->getFastMathFlags();
1386
9
        Flags &= SubOp->getFastMathFlags();
1387
9
        RI->setFastMathFlags(Flags);
1388
9
        return RI;
1389
9
      } else
1390
32
        return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
1391
96.4k
    }
1392
1.45k
  }
1393
96.4k
  return nullptr;
1394
96.4k
}
1395
1396
1.17M
Instruction *InstCombiner::foldSelectExtConst(SelectInst &Sel) {
1397
1.17M
  Constant *C;
1398
1.17M
  if (!match(Sel.getTrueValue(), m_Constant(C)) &&
1399
1.17M
      
!match(Sel.getFalseValue(), m_Constant(C))803k
)
1400
556k
    return nullptr;
1401
615k
1402
615k
  Instruction *ExtInst;
1403
615k
  if (!match(Sel.getTrueValue(), m_Instruction(ExtInst)) &&
1404
615k
      
!match(Sel.getFalseValue(), m_Instruction(ExtInst))385k
)
1405
238k
    return nullptr;
1406
377k
1407
377k
  auto ExtOpcode = ExtInst->getOpcode();
1408
377k
  if (ExtOpcode != Instruction::ZExt && 
ExtOpcode != Instruction::SExt371k
)
1409
348k
    return nullptr;
1410
28.9k
1411
28.9k
  // If we are extending from a boolean type or if we can create a select that
1412
28.9k
  // has the same size operands as its condition, try to narrow the select.
1413
28.9k
  Value *X = ExtInst->getOperand(0);
1414
28.9k
  Type *SmallType = X->getType();
1415
28.9k
  Value *Cond = Sel.getCondition();
1416
28.9k
  auto *Cmp = dyn_cast<CmpInst>(Cond);
1417
28.9k
  if (!SmallType->isIntOrIntVectorTy(1) &&
1418
28.9k
      
(25.5k
!Cmp25.5k
||
Cmp->getOperand(0)->getType() != SmallType25.3k
))
1419
25.4k
    return nullptr;
1420
3.42k
1421
3.42k
  // If the constant is the same after truncation to the smaller type and
1422
3.42k
  // extension to the original type, we can narrow the select.
1423
3.42k
  Type *SelType = Sel.getType();
1424
3.42k
  Constant *TruncC = ConstantExpr::getTrunc(C, SmallType);
1425
3.42k
  Constant *ExtC = ConstantExpr::getCast(ExtOpcode, TruncC, SelType);
1426
3.42k
  if (ExtC == C) {
1427
360
    Value *TruncCVal = cast<Value>(TruncC);
1428
360
    if (ExtInst == Sel.getFalseValue())
1429
275
      std::swap(X, TruncCVal);
1430
360
1431
360
    // select Cond, (ext X), C --> ext(select Cond, X, C')
1432
360
    // select Cond, C, (ext X) --> ext(select Cond, C', X)
1433
360
    Value *NewSel = Builder.CreateSelect(Cond, X, TruncCVal, "narrow", &Sel);
1434
360
    return CastInst::Create(Instruction::CastOps(ExtOpcode), NewSel, SelType);
1435
360
  }
1436
3.06k
1437
3.06k
  // If one arm of the select is the extend of the condition, replace that arm
1438
3.06k
  // with the extension of the appropriate known bool value.
1439
3.06k
  if (Cond == X) {
1440
10
    if (ExtInst == Sel.getTrueValue()) {
1441
4
      // select X, (sext X), C --> select X, -1, C
1442
4
      // select X, (zext X), C --> select X,  1, C
1443
4
      Constant *One = ConstantInt::getTrue(SmallType);
1444
4
      Constant *AllOnesOrOne = ConstantExpr::getCast(ExtOpcode, One, SelType);
1445
4
      return SelectInst::Create(Cond, AllOnesOrOne, C, "", nullptr, &Sel);
1446
6
    } else {
1447
6
      // select X, C, (sext X) --> select X, C, 0
1448
6
      // select X, C, (zext X) --> select X, C, 0
1449
6
      Constant *Zero = ConstantInt::getNullValue(SelType);
1450
6
      return SelectInst::Create(Cond, C, Zero, "", nullptr, &Sel);
1451
6
    }
1452
3.05k
  }
1453
3.05k
1454
3.05k
  return nullptr;
1455
3.05k
}
1456
1457
/// Try to transform a vector select with a constant condition vector into a
1458
/// shuffle for easier combining with other shuffles and insert/extract.
1459
1.19M
static Instruction *canonicalizeSelectToShuffle(SelectInst &SI) {
1460
1.19M
  Value *CondVal = SI.getCondition();
1461
1.19M
  Constant *CondC;
1462
1.19M
  if (!CondVal->getType()->isVectorTy() || 
!match(CondVal, m_Constant(CondC))7.95k
)
1463
1.19M
    return nullptr;
1464
26
1465
26
  unsigned NumElts = CondVal->getType()->getVectorNumElements();
1466
26
  SmallVector<Constant *, 16> Mask;
1467
26
  Mask.reserve(NumElts);
1468
26
  Type *Int32Ty = Type::getInt32Ty(CondVal->getContext());
1469
187
  for (unsigned i = 0; i != NumElts; 
++i161
) {
1470
164
    Constant *Elt = CondC->getAggregateElement(i);
1471
164
    if (!Elt)
1472
1
      return nullptr;
1473
163
1474
163
    if (Elt->isOneValue()) {
1475
87
      // If the select condition element is true, choose from the 1st vector.
1476
87
      Mask.push_back(ConstantInt::get(Int32Ty, i));
1477
87
    } else 
if (76
Elt->isNullValue()76
) {
1478
74
      // If the select condition element is false, choose from the 2nd vector.
1479
74
      Mask.push_back(ConstantInt::get(Int32Ty, i + NumElts));
1480
74
    } else 
if (2
isa<UndefValue>(Elt)2
) {
1481
2
      // Undef in a select condition (choose one of the operands) does not mean
1482
2
      // the same thing as undef in a shuffle mask (any value is acceptable), so
1483
2
      // give up.
1484
2
      return nullptr;
1485
2
    } else {
1486
0
      // Bail out on a constant expression.
1487
0
      return nullptr;
1488
0
    }
1489
163
  }
1490
26
1491
26
  return new ShuffleVectorInst(SI.getTrueValue(), SI.getFalseValue(),
1492
23
                               ConstantVector::get(Mask));
1493
26
}
1494
1495
/// Reuse bitcasted operands between a compare and select:
1496
/// select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
1497
/// bitcast (select (cmp (bitcast C), (bitcast D)), (bitcast C), (bitcast D))
1498
static Instruction *foldSelectCmpBitcasts(SelectInst &Sel,
1499
1.16M
                                          InstCombiner::BuilderTy &Builder) {
1500
1.16M
  Value *Cond = Sel.getCondition();
1501
1.16M
  Value *TVal = Sel.getTrueValue();
1502
1.16M
  Value *FVal = Sel.getFalseValue();
1503
1.16M
1504
1.16M
  CmpInst::Predicate Pred;
1505
1.16M
  Value *A, *B;
1506
1.16M
  if (!match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B))))
1507
108k
    return nullptr;
1508
1.05M
1509
1.05M
  // The select condition is a compare instruction. If the select's true/false
1510
1.05M
  // values are already the same as the compare operands, there's nothing to do.
1511
1.05M
  if (TVal == A || 
TVal == B777k
||
FVal == A620k
||
FVal == B490k
)
1512
574k
    return nullptr;
1513
484k
1514
484k
  Value *C, *D;
1515
484k
  if (!match(A, m_BitCast(m_Value(C))) || 
!match(B, m_BitCast(m_Value(D)))1.64k
)
1516
484k
    return nullptr;
1517
10
1518
10
  // select (cmp (bitcast C), (bitcast D)), (bitcast TSrc), (bitcast FSrc)
1519
10
  Value *TSrc, *FSrc;
1520
10
  if (!match(TVal, m_BitCast(m_Value(TSrc))) ||
1521
10
      
!match(FVal, m_BitCast(m_Value(FSrc)))3
)
1522
7
    return nullptr;
1523
3
1524
3
  // If the select true/false values are *different bitcasts* of the same source
1525
3
  // operands, make the select operands the same as the compare operands and
1526
3
  // cast the result. This is the canonical select form for min/max.
1527
3
  Value *NewSel;
1528
3
  if (TSrc == C && 
FSrc == D1
) {
1529
1
    // select (cmp (bitcast C), (bitcast D)), (bitcast' C), (bitcast' D) -->
1530
1
    // bitcast (select (cmp A, B), A, B)
1531
1
    NewSel = Builder.CreateSelect(Cond, A, B, "", &Sel);
1532
2
  } else if (TSrc == D && FSrc == C) {
1533
2
    // select (cmp (bitcast C), (bitcast D)), (bitcast' D), (bitcast' C) -->
1534
2
    // bitcast (select (cmp A, B), B, A)
1535
2
    NewSel = Builder.CreateSelect(Cond, B, A, "", &Sel);
1536
2
  } else {
1537
0
    return nullptr;
1538
0
  }
1539
3
  return CastInst::CreateBitOrPointerCast(NewSel, Sel.getType());
1540
3
}
1541
1542
/// Try to eliminate select instructions that test the returned flag of cmpxchg
1543
/// instructions.
1544
///
1545
/// If a select instruction tests the returned flag of a cmpxchg instruction and
1546
/// selects between the returned value of the cmpxchg instruction its compare
1547
/// operand, the result of the select will always be equal to its false value.
1548
/// For example:
1549
///
1550
///   %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
1551
///   %1 = extractvalue { i64, i1 } %0, 1
1552
///   %2 = extractvalue { i64, i1 } %0, 0
1553
///   %3 = select i1 %1, i64 %compare, i64 %2
1554
///   ret i64 %3
1555
///
1556
/// The returned value of the cmpxchg instruction (%2) is the original value
1557
/// located at %ptr prior to any update. If the cmpxchg operation succeeds, %2
1558
/// must have been equal to %compare. Thus, the result of the select is always
1559
/// equal to %2, and the code can be simplified to:
1560
///
1561
///   %0 = cmpxchg i64* %ptr, i64 %compare, i64 %new_value seq_cst seq_cst
1562
///   %1 = extractvalue { i64, i1 } %0, 0
1563
///   ret i64 %1
1564
///
1565
1.16M
static Instruction *foldSelectCmpXchg(SelectInst &SI) {
1566
1.16M
  // A helper that determines if V is an extractvalue instruction whose
1567
1.16M
  // aggregate operand is a cmpxchg instruction and whose single index is equal
1568
1.16M
  // to I. If such conditions are true, the helper returns the cmpxchg
1569
1.16M
  // instruction; otherwise, a nullptr is returned.
1570
1.16M
  auto isExtractFromCmpXchg = [](Value *V, unsigned I) -> AtomicCmpXchgInst * {
1571
1.16M
    auto *Extract = dyn_cast<ExtractValueInst>(V);
1572
1.16M
    if (!Extract)
1573
1.15M
      return nullptr;
1574
11.6k
    if (Extract->getIndices()[0] != I)
1575
0
      return nullptr;
1576
11.6k
    return dyn_cast<AtomicCmpXchgInst>(Extract->getAggregateOperand());
1577
11.6k
  };
1578
1.16M
1579
1.16M
  // If the select has a single user, and this user is a select instruction that
1580
1.16M
  // we can simplify, skip the cmpxchg simplification for now.
1581
1.16M
  if (SI.hasOneUse())
1582
663k
    if (auto *Select = dyn_cast<SelectInst>(SI.user_back()))
1583
17.5k
      if (Select->getCondition() == SI.getCondition())
1584
22
        if (Select->getFalseValue() == SI.getTrueValue() ||
1585
22
            
Select->getTrueValue() == SI.getFalseValue()21
)
1586
1
          return nullptr;
1587
1.16M
1588
1.16M
  // Ensure the select condition is the returned flag of a cmpxchg instruction.
1589
1.16M
  auto *CmpXchg = isExtractFromCmpXchg(SI.getCondition(), 1);
1590
1.16M
  if (!CmpXchg)
1591
1.16M
    return nullptr;
1592
40
1593
40
  // Check the true value case: The true value of the select is the returned
1594
40
  // value of the same cmpxchg used by the condition, and the false value is the
1595
40
  // cmpxchg instruction's compare operand.
1596
40
  if (auto *X = isExtractFromCmpXchg(SI.getTrueValue(), 0))
1597
1
    if (X == CmpXchg && X->getCompareOperand() == SI.getFalseValue()) {
1598
1
      SI.setTrueValue(SI.getFalseValue());
1599
1
      return &SI;
1600
1
    }
1601
39
1602
39
  // Check the false value case: The false value of the select is the returned
1603
39
  // value of the same cmpxchg used by the condition, and the true value is the
1604
39
  // cmpxchg instruction's compare operand.
1605
39
  if (auto *X = isExtractFromCmpXchg(SI.getFalseValue(), 0))
1606
39
    if (X == CmpXchg && X->getCompareOperand() == SI.getTrueValue()) {
1607
39
      SI.setTrueValue(SI.getFalseValue());
1608
39
      return &SI;
1609
39
    }
1610
0
1611
0
  return nullptr;
1612
0
}
1613
1614
static Instruction *moveAddAfterMinMax(SelectPatternFlavor SPF, Value *X,
1615
                                       Value *Y,
1616
307k
                                       InstCombiner::BuilderTy &Builder) {
1617
307k
  assert(SelectPatternResult::isMinOrMax(SPF) && "Expected min/max pattern");
1618
307k
  bool IsUnsigned = SPF == SelectPatternFlavor::SPF_UMIN ||
1619
307k
                    
SPF == SelectPatternFlavor::SPF_UMAX270k
;
1620
307k
  // TODO: If InstSimplify could fold all cases where C2 <= C1, we could change
1621
307k
  // the constant value check to an assert.
1622
307k
  Value *A;
1623
307k
  const APInt *C1, *C2;
1624
307k
  if (IsUnsigned && 
match(X, m_NUWAdd(m_Value(A), m_APInt(C1)))134k
&&
1625
307k
      
match(Y, m_APInt(C2))189
&&
C2->uge(*C1)138
&&
X->hasNUses(2)138
) {
1626
26
    // umin (add nuw A, C1), C2 --> add nuw (umin A, C2 - C1), C1
1627
26
    // umax (add nuw A, C1), C2 --> add nuw (umax A, C2 - C1), C1
1628
26
    Value *NewMinMax = createMinMax(Builder, SPF, A,
1629
26
                                    ConstantInt::get(X->getType(), *C2 - *C1));
1630
26
    return BinaryOperator::CreateNUW(BinaryOperator::Add, NewMinMax,
1631
26
                                     ConstantInt::get(X->getType(), *C1));
1632
26
  }
1633
307k
1634
307k
  if (!IsUnsigned && 
match(X, m_NSWAdd(m_Value(A), m_APInt(C1)))172k
&&
1635
307k
      
match(Y, m_APInt(C2))3.44k
&&
X->hasNUses(2)703
) {
1636
312
    bool Overflow;
1637
312
    APInt Diff = C2->ssub_ov(*C1, Overflow);
1638
312
    if (!Overflow) {
1639
312
      // smin (add nsw A, C1), C2 --> add nsw (smin A, C2 - C1), C1
1640
312
      // smax (add nsw A, C1), C2 --> add nsw (smax A, C2 - C1), C1
1641
312
      Value *NewMinMax = createMinMax(Builder, SPF, A,
1642
312
                                      ConstantInt::get(X->getType(), Diff));
1643
312
      return BinaryOperator::CreateNSW(BinaryOperator::Add, NewMinMax,
1644
312
                                       ConstantInt::get(X->getType(), *C1));
1645
312
    }
1646
306k
  }
1647
306k
1648
306k
  return nullptr;
1649
306k
}
1650
1651
/// Reduce a sequence of min/max with a common operand.
1652
static Instruction *factorizeMinMaxTree(SelectPatternFlavor SPF, Value *LHS,
1653
                                        Value *RHS,
1654
306k
                                        InstCombiner::BuilderTy &Builder) {
1655
306k
  assert(SelectPatternResult::isMinOrMax(SPF) && "Expected a min/max");
1656
306k
  // TODO: Allow FP min/max with nnan/nsz.
1657
306k
  if (!LHS->getType()->isIntOrIntVectorTy())
1658
4.51k
    return nullptr;
1659
302k
1660
302k
  // Match 3 of the same min/max ops. Example: umin(umin(), umin()).
1661
302k
  Value *A, *B, *C, *D;
1662
302k
  SelectPatternResult L = matchSelectPattern(LHS, A, B);
1663
302k
  SelectPatternResult R = matchSelectPattern(RHS, C, D);
1664
302k
  if (SPF != L.Flavor || 
L.Flavor != R.Flavor2.03k
)
1665
301k
    return nullptr;
1666
357
1667
357
  // Look for a common operand. The use checks are different than usual because
1668
357
  // a min/max pattern typically has 2 uses of each op: 1 by the cmp and 1 by
1669
357
  // the select.
1670
357
  Value *MinMaxOp = nullptr;
1671
357
  Value *ThirdOp = nullptr;
1672
357
  if (!LHS->hasNUsesOrMore(3) && 
RHS->hasNUsesOrMore(3)49
) {
1673
42
    // If the LHS is only used in this chain and the RHS is used outside of it,
1674
42
    // reuse the RHS min/max because that will eliminate the LHS.
1675
42
    if (D == A || C == A) {
1676
1
      // min(min(a, b), min(c, a)) --> min(min(c, a), b)
1677
1
      // min(min(a, b), min(a, d)) --> min(min(a, d), b)
1678
1
      MinMaxOp = RHS;
1679
1
      ThirdOp = B;
1680
41
    } else if (D == B || C == B) {
1681
0
      // min(min(a, b), min(c, b)) --> min(min(c, b), a)
1682
0
      // min(min(a, b), min(b, d)) --> min(min(b, d), a)
1683
0
      MinMaxOp = RHS;
1684
0
      ThirdOp = A;
1685
0
    }
1686
315
  } else if (!RHS->hasNUsesOrMore(3)) {
1687
8
    // Reuse the LHS. This will eliminate the RHS.
1688
8
    if (D == A || 
D == B7
) {
1689
3
      // min(min(a, b), min(c, a)) --> min(min(a, b), c)
1690
3
      // min(min(a, b), min(c, b)) --> min(min(a, b), c)
1691
3
      MinMaxOp = LHS;
1692
3
      ThirdOp = C;
1693
5
    } else if (C == A || 
C == B2
) {
1694
4
      // min(min(a, b), min(b, d)) --> min(min(a, b), d)
1695
4
      // min(min(a, b), min(c, b)) --> min(min(a, b), d)
1696
4
      MinMaxOp = LHS;
1697
4
      ThirdOp = D;
1698
4
    }
1699
8
  }
1700
357
  if (!MinMaxOp || 
!ThirdOp8
)
1701
349
    return nullptr;
1702
8
1703
8
  CmpInst::Predicate P = getMinMaxPred(SPF);
1704
8
  Value *CmpABC = Builder.CreateICmp(P, MinMaxOp, ThirdOp);
1705
8
  return SelectInst::Create(CmpABC, MinMaxOp, ThirdOp);
1706
8
}
1707
1708
/// Try to reduce a rotate pattern that includes a compare and select into a
1709
/// funnel shift intrinsic. Example:
1710
/// rotl32(a, b) --> (b == 0 ? a : ((a >> (32 - b)) | (a << b)))
1711
///              --> call llvm.fshl.i32(a, a, b)
1712
1.16M
static Instruction *foldSelectRotate(SelectInst &Sel) {
1713
1.16M
  // The false value of the select must be a rotate of the true value.
1714
1.16M
  Value *Or0, *Or1;
1715
1.16M
  if (!match(Sel.getFalseValue(), m_OneUse(m_Or(m_Value(Or0), m_Value(Or1)))))
1716
1.16M
    return nullptr;
1717
1.58k
1718
1.58k
  Value *TVal = Sel.getTrueValue();
1719
1.58k
  Value *SA0, *SA1;
1720
1.58k
  if (!match(Or0, m_OneUse(m_LogicalShift(m_Specific(TVal), m_Value(SA0)))) ||
1721
1.58k
      
!match(Or1, m_OneUse(m_LogicalShift(m_Specific(TVal), m_Value(SA1))))226
)
1722
1.47k
    return nullptr;
1723
110
1724
110
  auto ShiftOpcode0 = cast<BinaryOperator>(Or0)->getOpcode();
1725
110
  auto ShiftOpcode1 = cast<BinaryOperator>(Or1)->getOpcode();
1726
110
  if (ShiftOpcode0 == ShiftOpcode1)
1727
0
    return nullptr;
1728
110
1729
110
  // We have one of these patterns so far:
1730
110
  // select ?, TVal, (or (lshr TVal, SA0), (shl TVal, SA1))
1731
110
  // select ?, TVal, (or (shl TVal, SA0), (lshr TVal, SA1))
1732
110
  // This must be a power-of-2 rotate for a bitmasking transform to be valid.
1733
110
  unsigned Width = Sel.getType()->getScalarSizeInBits();
1734
110
  if (!isPowerOf2_32(Width))
1735
1
    return nullptr;
1736
109
1737
109
  // Check the shift amounts to see if they are an opposite pair.
1738
109
  Value *ShAmt;
1739
109
  if (match(SA1, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA0)))))
1740
7
    ShAmt = SA0;
1741
102
  else if (match(SA0, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(SA1)))))
1742
3
    ShAmt = SA1;
1743
99
  else
1744
99
    return nullptr;
1745
10
1746
10
  // Finally, see if the select is filtering out a shift-by-zero.
1747
10
  Value *Cond = Sel.getCondition();
1748
10
  ICmpInst::Predicate Pred;
1749
10
  if (!match(Cond, m_OneUse(m_ICmp(Pred, m_Specific(ShAmt), m_ZeroInt()))) ||
1750
10
      Pred != ICmpInst::ICMP_EQ)
1751
0
    return nullptr;
1752
10
1753
10
  // This is a rotate that avoids shift-by-bitwidth UB in a suboptimal way.
1754
10
  // Convert to funnel shift intrinsic.
1755
10
  bool IsFshl = (ShAmt == SA0 && 
ShiftOpcode0 == BinaryOperator::Shl7
) ||
1756
10
                
(9
ShAmt == SA19
&&
ShiftOpcode1 == BinaryOperator::Shl3
);
1757
10
  Intrinsic::ID IID = IsFshl ? 
Intrinsic::fshl3
:
Intrinsic::fshr7
;
1758
10
  Function *F = Intrinsic::getDeclaration(Sel.getModule(), IID, Sel.getType());
1759
10
  return IntrinsicInst::Create(F, { TVal, TVal, ShAmt });
1760
10
}
1761
1762
1.19M
Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
1763
1.19M
  Value *CondVal = SI.getCondition();
1764
1.19M
  Value *TrueVal = SI.getTrueValue();
1765
1.19M
  Value *FalseVal = SI.getFalseValue();
1766
1.19M
  Type *SelType = SI.getType();
1767
1.19M
1768
1.19M
  // FIXME: Remove this workaround when freeze related patches are done.
1769
1.19M
  // For select with undef operand which feeds into an equality comparison,
1770
1.19M
  // don't simplify it so loop unswitch can know the equality comparison
1771
1.19M
  // may have an undef operand. This is a workaround for PR31652 caused by
1772
1.19M
  // descrepancy about branch on undef between LoopUnswitch and GVN.
1773
1.19M
  if (isa<UndefValue>(TrueVal) || 
isa<UndefValue>(FalseVal)1.19M
) {
1774
46
    if (llvm::any_of(SI.users(), [&](User *U) {
1775
46
          ICmpInst *CI = dyn_cast<ICmpInst>(U);
1776
46
          if (CI && 
CI->isEquality()0
)
1777
0
            return true;
1778
46
          return false;
1779
46
        })) {
1780
0
      return nullptr;
1781
0
    }
1782
1.19M
  }
1783
1.19M
1784
1.19M
  if (Value *V = SimplifySelectInst(CondVal, TrueVal, FalseVal,
1785
2.48k
                                    SQ.getWithInstruction(&SI)))
1786
2.48k
    return replaceInstUsesWith(SI, V);
1787
1.19M
1788
1.19M
  if (Instruction *I = canonicalizeSelectToShuffle(SI))
1789
23
    return I;
1790
1.19M
1791
1.19M
  // Canonicalize a one-use integer compare with a non-canonical predicate by
1792
1.19M
  // inverting the predicate and swapping the select operands. This matches a
1793
1.19M
  // compare canonicalization for conditional branches.
1794
1.19M
  // TODO: Should we do the same for FP compares?
1795
1.19M
  CmpInst::Predicate Pred;
1796
1.19M
  if (match(CondVal, m_OneUse(m_ICmp(Pred, m_Value(), m_Value()))) &&
1797
1.19M
      
!isCanonicalPredicate(Pred)855k
) {
1798
2.80k
    // Swap true/false values and condition.
1799
2.80k
    CmpInst *Cond = cast<CmpInst>(CondVal);
1800
2.80k
    Cond->setPredicate(CmpInst::getInversePredicate(Pred));
1801
2.80k
    SI.setOperand(1, FalseVal);
1802
2.80k
    SI.setOperand(2, TrueVal);
1803
2.80k
    SI.swapProfMetadata();
1804
2.80k
    Worklist.Add(Cond);
1805
2.80k
    return &SI;
1806
2.80k
  }
1807
1.18M
1808
1.18M
  if (SelType->isIntOrIntVectorTy(1) &&
1809
1.18M
      
TrueVal->getType() == CondVal->getType()4.19k
) {
1810
4.18k
    if (match(TrueVal, m_One())) {
1811
1.58k
      // Change: A = select B, true, C --> A = or B, C
1812
1.58k
      return BinaryOperator::CreateOr(CondVal, FalseVal);
1813
1.58k
    }
1814
2.60k
    if (match(TrueVal, m_Zero())) {
1815
1.09k
      // Change: A = select B, false, C --> A = and !B, C
1816
1.09k
      Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
1817
1.09k
      return BinaryOperator::CreateAnd(NotCond, FalseVal);
1818
1.09k
    }
1819
1.50k
    if (match(FalseVal, m_Zero())) {
1820
807
      // Change: A = select B, C, false --> A = and B, C
1821
807
      return BinaryOperator::CreateAnd(CondVal, TrueVal);
1822
807
    }
1823
696
    if (match(FalseVal, m_One())) {
1824
399
      // Change: A = select B, C, true --> A = or !B, C
1825
399
      Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
1826
399
      return BinaryOperator::CreateOr(NotCond, TrueVal);
1827
399
    }
1828
297
1829
297
    // select a, a, b  -> a | b
1830
297
    // select a, b, a  -> a & b
1831
297
    if (CondVal == TrueVal)
1832
2
      return BinaryOperator::CreateOr(CondVal, FalseVal);
1833
295
    if (CondVal == FalseVal)
1834
2
      return BinaryOperator::CreateAnd(CondVal, TrueVal);
1835
293
1836
293
    // select a, ~a, b -> (~a) & b
1837
293
    // select a, b, ~a -> (~a) | b
1838
293
    if (match(TrueVal, m_Not(m_Specific(CondVal))))
1839
2
      return BinaryOperator::CreateAnd(TrueVal, FalseVal);
1840
291
    if (match(FalseVal, m_Not(m_Specific(CondVal))))
1841
2
      return BinaryOperator::CreateOr(TrueVal, FalseVal);
1842
1.18M
  }
1843
1.18M
1844
1.18M
  // Selecting between two integer or vector splat integer constants?
1845
1.18M
  //
1846
1.18M
  // Note that we don't handle a scalar select of vectors:
1847
1.18M
  // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
1848
1.18M
  // because that may need 3 instructions to splat the condition value:
1849
1.18M
  // extend, insertelement, shufflevector.
1850
1.18M
  if (SelType->isIntOrIntVectorTy() &&
1851
1.18M
      
CondVal->getType()->isVectorTy() == SelType->isVectorTy()944k
) {
1852
944k
    // select C, 1, 0 -> zext C to int
1853
944k
    if (match(TrueVal, m_One()) && 
match(FalseVal, m_Zero())48.5k
)
1854
2.05k
      return new ZExtInst(CondVal, SelType);
1855
942k
1856
942k
    // select C, -1, 0 -> sext C to int
1857
942k
    if (match(TrueVal, m_AllOnes()) && 
match(FalseVal, m_Zero())22.2k
)
1858
239
      return new SExtInst(CondVal, SelType);
1859
942k
1860
942k
    // select C, 0, 1 -> zext !C to int
1861
942k
    if (match(TrueVal, m_Zero()) && 
match(FalseVal, m_One())132k
) {
1862
1.14k
      Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
1863
1.14k
      return new ZExtInst(NotCond, SelType);
1864
1.14k
    }
1865
940k
1866
940k
    // select C, 0, -1 -> sext !C to int
1867
940k
    if (match(TrueVal, m_Zero()) && 
match(FalseVal, m_AllOnes())131k
) {
1868
142
      Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
1869
142
      return new SExtInst(NotCond, SelType);
1870
142
    }
1871
1.18M
  }
1872
1.18M
1873
1.18M
  // See if we are selecting two values based on a comparison of the two values.
1874
1.18M
  if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) {
1875
38.2k
    if (FCI->getOperand(0) == TrueVal && 
FCI->getOperand(1) == FalseVal8.83k
) {
1876
8.20k
      // Canonicalize to use ordered comparisons by swapping the select
1877
8.20k
      // operands.
1878
8.20k
      //
1879
8.20k
      // e.g.
1880
8.20k
      // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
1881
8.20k
      if (FCI->hasOneUse() && 
FCmpInst::isUnordered(FCI->getPredicate())6.84k
) {
1882
50
        FCmpInst::Predicate InvPred = FCI->getInversePredicate();
1883
50
        IRBuilder<>::FastMathFlagGuard FMFG(Builder);
1884
50
        Builder.setFastMathFlags(FCI->getFastMathFlags());
1885
50
        Value *NewCond = Builder.CreateFCmp(InvPred, TrueVal, FalseVal,
1886
50
                                            FCI->getName() + ".inv");
1887
50
1888
50
        return SelectInst::Create(NewCond, FalseVal, TrueVal,
1889
50
                                  SI.getName() + ".p");
1890
50
      }
1891
30.0k
1892
30.0k
      // NOTE: if we wanted to, this is where to detect MIN/MAX
1893
30.0k
    } else if (FCI->getOperand(0) == FalseVal && 
FCI->getOperand(1) == TrueVal11.3k
){
1894
6.69k
      // Canonicalize to use ordered comparisons by swapping the select
1895
6.69k
      // operands.
1896
6.69k
      //
1897
6.69k
      // e.g.
1898
6.69k
      // (X ugt Y) ? X : Y -> (X ole Y) ? X : Y
1899
6.69k
      if (FCI->hasOneUse() && 
FCmpInst::isUnordered(FCI->getPredicate())5.97k
) {
1900
14
        FCmpInst::Predicate InvPred = FCI->getInversePredicate();
1901
14
        IRBuilder<>::FastMathFlagGuard FMFG(Builder);
1902
14
        Builder.setFastMathFlags(FCI->getFastMathFlags());
1903
14
        Value *NewCond = Builder.CreateFCmp(InvPred, FalseVal, TrueVal,
1904
14
                                            FCI->getName() + ".inv");
1905
14
1906
14
        return SelectInst::Create(NewCond, FalseVal, TrueVal,
1907
14
                                  SI.getName() + ".p");
1908
14
      }
1909
1.18M
1910
1.18M
      // NOTE: if we wanted to, this is where to detect MIN/MAX
1911
1.18M
    }
1912
38.2k
  }
1913
1.18M
1914
1.18M
  // Canonicalize select with fcmp to fabs(). -0.0 makes this tricky. We need
1915
1.18M
  // fast-math-flags (nsz) or fsub with +0.0 (not fneg) for this to work. We
1916
1.18M
  // also require nnan because we do not want to unintentionally change the
1917
1.18M
  // sign of a NaN value.
1918
1.18M
  // FIXME: These folds should test/propagate FMF from the select, not the
1919
1.18M
  //        fsub or fneg.
1920
1.18M
  // (X <= +/-0.0) ? (0.0 - X) : X --> fabs(X)
1921
1.18M
  Instruction *FSub;
1922
1.18M
  if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) &&
1923
1.18M
      
match(TrueVal, m_FSub(m_PosZeroFP(), m_Specific(FalseVal)))5.14k
&&
1924
1.18M
      
match(TrueVal, m_Instruction(FSub))5
&&
FSub->hasNoNaNs()5
&&
1925
1.18M
      
(4
Pred == FCmpInst::FCMP_OLE4
||
Pred == FCmpInst::FCMP_ULE2
)) {
1926
3
    Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, FSub);
1927
3
    return replaceInstUsesWith(SI, Fabs);
1928
3
  }
1929
1.18M
  // (X >  +/-0.0) ? X : (0.0 - X) --> fabs(X)
1930
1.18M
  if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) &&
1931
1.18M
      
match(FalseVal, m_FSub(m_PosZeroFP(), m_Specific(TrueVal)))643
&&
1932
1.18M
      
match(FalseVal, m_Instruction(FSub))5
&&
FSub->hasNoNaNs()5
&&
1933
1.18M
      
(5
Pred == FCmpInst::FCMP_OGT5
||
Pred == FCmpInst::FCMP_UGT3
)) {
1934
3
    Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, FSub);
1935
3
    return replaceInstUsesWith(SI, Fabs);
1936
3
  }
1937
1.18M
  // With nnan and nsz:
1938
1.18M
  // (X <  +/-0.0) ? -X : X --> fabs(X)
1939
1.18M
  // (X <= +/-0.0) ? -X : X --> fabs(X)
1940
1.18M
  Instruction *FNeg;
1941
1.18M
  if (match(CondVal, m_FCmp(Pred, m_Specific(FalseVal), m_AnyZeroFP())) &&
1942
1.18M
      
match(TrueVal, m_FNeg(m_Specific(FalseVal)))5.14k
&&
1943
1.18M
      
match(TrueVal, m_Instruction(FNeg))196
&&
1944
1.18M
      
FNeg->hasNoNaNs()196
&&
FNeg->hasNoSignedZeros()16
&&
1945
1.18M
      
(16
Pred == FCmpInst::FCMP_OLT16
||
Pred == FCmpInst::FCMP_OLE12
||
1946
16
       
Pred == FCmpInst::FCMP_ULT8
||
Pred == FCmpInst::FCMP_ULE4
)) {
1947
16
    Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, FalseVal, FNeg);
1948
16
    return replaceInstUsesWith(SI, Fabs);
1949
16
  }
1950
1.18M
  // With nnan and nsz:
1951
1.18M
  // (X >  +/-0.0) ? X : -X --> fabs(X)
1952
1.18M
  // (X >= +/-0.0) ? X : -X --> fabs(X)
1953
1.18M
  if (match(CondVal, m_FCmp(Pred, m_Specific(TrueVal), m_AnyZeroFP())) &&
1954
1.18M
      
match(FalseVal, m_FNeg(m_Specific(TrueVal)))640
&&
1955
1.18M
      
match(FalseVal, m_Instruction(FNeg))261
&&
1956
1.18M
      
FNeg->hasNoNaNs()261
&&
FNeg->hasNoSignedZeros()14
&&
1957
1.18M
      
(14
Pred == FCmpInst::FCMP_OGT14
||
Pred == FCmpInst::FCMP_OGE11
||
1958
14
       
Pred == FCmpInst::FCMP_UGT7
||
Pred == FCmpInst::FCMP_UGE4
)) {
1959
14
    Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, TrueVal, FNeg);
1960
14
    return replaceInstUsesWith(SI, Fabs);
1961
14
  }
1962
1.18M
1963
1.18M
  // See if we are selecting two values based on a comparison of the two values.
1964
1.18M
  if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
1965
1.03M
    if (Instruction *Result = foldSelectInstWithICmp(SI, ICI))
1966
8.73k
      return Result;
1967
1.17M
1968
1.17M
  if (Instruction *Add = foldAddSubSelect(SI, Builder))
1969
41
    return Add;
1970
1.17M
1971
1.17M
  // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
1972
1.17M
  auto *TI = dyn_cast<Instruction>(TrueVal);
1973
1.17M
  auto *FI = dyn_cast<Instruction>(FalseVal);
1974
1.17M
  if (TI && 
FI750k
&&
TI->getOpcode() == FI->getOpcode()506k
)
1975
141k
    if (Instruction *IV = foldSelectOpOp(SI, TI, FI))
1976
297
      return IV;
1977
1.17M
1978
1.17M
  if (Instruction *I = foldSelectExtConst(SI))
1979
370
    return I;
1980
1.17M
1981
1.17M
  // See if we can fold the select into one of our operands.
1982
1.17M
  if (SelType->isIntOrIntVectorTy() || 
SelType->isFPOrFPVectorTy()240k
) {
1983
991k
    if (Instruction *FoldI = foldSelectIntoOp(SI, TrueVal, FalseVal))
1984
1.60k
      return FoldI;
1985
989k
1986
989k
    Value *LHS, *RHS;
1987
989k
    Instruction::CastOps CastOp;
1988
989k
    SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
1989
989k
    auto SPF = SPR.Flavor;
1990
989k
    if (SPF) {
1991
379k
      Value *LHS2, *RHS2;
1992
379k
      if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
1993
17.0k
        if (Instruction *R = foldSPFofSPF(cast<Instruction>(LHS), SPF2, LHS2,
1994
67
                                          RHS2, SI, SPF, RHS))
1995
67
          return R;
1996
379k
      if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
1997
41.3k
        if (Instruction *R = foldSPFofSPF(cast<Instruction>(RHS), SPF2, LHS2,
1998
1
                                          RHS2, SI, SPF, LHS))
1999
1
          return R;
2000
989k
      // TODO.
2001
989k
      // ABS(-X) -> ABS(X)
2002
989k
    }
2003
989k
2004
989k
    if (SelectPatternResult::isMinOrMax(SPF)) {
2005
307k
      // Canonicalize so that
2006
307k
      // - type casts are outside select patterns.
2007
307k
      // - float clamp is transformed to min/max pattern
2008
307k
2009
307k
      bool IsCastNeeded = LHS->getType() != SelType;
2010
307k
      Value *CmpLHS = cast<CmpInst>(CondVal)->getOperand(0);
2011
307k
      Value *CmpRHS = cast<CmpInst>(CondVal)->getOperand(1);
2012
307k
      if (IsCastNeeded ||
2013
307k
          
(307k
LHS->getType()->isFPOrFPVectorTy()307k
&&
2014
307k
           
(4.52k
(4.52k
CmpLHS != LHS4.52k
&&
CmpLHS != RHS9
) ||
2015
4.52k
            
(4.51k
CmpRHS != LHS4.51k
&&
CmpRHS != RHS4.51k
)))) {
2016
194
        CmpInst::Predicate Pred = getMinMaxPred(SPF, SPR.Ordered);
2017
194
2018
194
        Value *Cmp;
2019
194
        if (CmpInst::isIntPredicate(Pred)) {
2020
171
          Cmp = Builder.CreateICmp(Pred, LHS, RHS);
2021
171
        } else {
2022
23
          IRBuilder<>::FastMathFlagGuard FMFG(Builder);
2023
23
          auto FMF = cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
2024
23
          Builder.setFastMathFlags(FMF);
2025
23
          Cmp = Builder.CreateFCmp(Pred, LHS, RHS);
2026
23
        }
2027
194
2028
194
        Value *NewSI = Builder.CreateSelect(Cmp, LHS, RHS, SI.getName(), &SI);
2029
194
        if (!IsCastNeeded)
2030
11
          return replaceInstUsesWith(SI, NewSI);
2031
183
2032
183
        Value *NewCast = Builder.CreateCast(CastOp, NewSI, SelType);
2033
183
        return replaceInstUsesWith(SI, NewCast);
2034
183
      }
2035
307k
2036
307k
      // MAX(~a, ~b) -> ~MIN(a, b)
2037
307k
      // MAX(~a, C)  -> ~MIN(a, ~C)
2038
307k
      // MIN(~a, ~b) -> ~MAX(a, b)
2039
307k
      // MIN(~a, C)  -> ~MAX(a, ~C)
2040
614k
      
auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * 307k
{
2041
614k
        Value *A;
2042
614k
        if (match(X, m_Not(m_Value(A))) && 
!X->hasNUsesOrMore(3)446
&&
2043
614k
            
!IsFreeToInvert(A, A->hasOneUse())414
&&
2044
614k
            // Passing false to only consider m_Not and constants.
2045
614k
            
IsFreeToInvert(Y, false)368
) {
2046
51
          Value *B = Builder.CreateNot(Y);
2047
51
          Value *NewMinMax = createMinMax(Builder, getInverseMinMaxFlavor(SPF),
2048
51
                                          A, B);
2049
51
          // Copy the profile metadata.
2050
51
          if (MDNode *MD = SI.getMetadata(LLVMContext::MD_prof)) {
2051
5
            cast<SelectInst>(NewMinMax)->setMetadata(LLVMContext::MD_prof, MD);
2052
5
            // Swap the metadata if the operands are swapped.
2053
5
            if (X == SI.getFalseValue() && 
Y == SI.getTrueValue()3
)
2054
3
              cast<SelectInst>(NewMinMax)->swapProfMetadata();
2055
5
          }
2056
51
2057
51
          return BinaryOperator::CreateNot(NewMinMax);
2058
51
        }
2059
614k
2060
614k
        return nullptr;
2061
614k
      };
2062
307k
2063
307k
      if (Instruction *I = moveNotAfterMinMax(LHS, RHS))
2064
41
        return I;
2065
307k
      if (Instruction *I = moveNotAfterMinMax(RHS, LHS))
2066
10
        return I;
2067
307k
2068
307k
      if (Instruction *I = moveAddAfterMinMax(SPF, LHS, RHS, Builder))
2069
338
        return I;
2070
306k
2071
306k
      if (Instruction *I = factorizeMinMaxTree(SPF, LHS, RHS, Builder))
2072
8
        return I;
2073
1.16M
    }
2074
989k
  }
2075
1.16M
2076
1.16M
  // Canonicalize select of FP values where NaN and -0.0 are not valid as
2077
1.16M
  // minnum/maxnum intrinsics.
2078
1.16M
  if (isa<FPMathOperator>(SI) && 
SI.hasNoNaNs()59.3k
&&
SI.hasNoSignedZeros()6
) {
2079
4
    Value *X, *Y;
2080
4
    if (match(&SI, m_OrdFMax(m_Value(X), m_Value(Y))))
2081
2
      return replaceInstUsesWith(
2082
2
          SI, Builder.CreateBinaryIntrinsic(Intrinsic::maxnum, X, Y, &SI));
2083
2
2084
2
    if (match(&SI, m_OrdFMin(m_Value(X), m_Value(Y))))
2085
2
      return replaceInstUsesWith(
2086
2
          SI, Builder.CreateBinaryIntrinsic(Intrinsic::minnum, X, Y, &SI));
2087
1.16M
  }
2088
1.16M
2089
1.16M
  // See if we can fold the select into a phi node if the condition is a select.
2090
1.16M
  if (auto *PN = dyn_cast<PHINode>(SI.getCondition()))
2091
3.14k
    // The true/false values have to be live in the PHI predecessor's blocks.
2092
3.14k
    if (canSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
2093
3.14k
        
canSelectOperandBeMappingIntoPredBlock(FalseVal, SI)2.39k
)
2094
1.71k
      if (Instruction *NV = foldOpIntoPhi(SI, PN))
2095
83
        return NV;
2096
1.16M
2097
1.16M
  if (SelectInst *TrueSI = dyn_cast<SelectInst>(TrueVal)) {
2098
59.1k
    if (TrueSI->getCondition()->getType() == CondVal->getType()) {
2099
59.1k
      // select(C, select(C, a, b), c) -> select(C, a, c)
2100
59.1k
      if (TrueSI->getCondition() == CondVal) {
2101
14
        if (SI.getTrueValue() == TrueSI->getTrueValue())
2102
2
          return nullptr;
2103
12
        SI.setOperand(1, TrueSI->getTrueValue());
2104
12
        return &SI;
2105
12
      }
2106
59.0k
      // select(C0, select(C1, a, b), b) -> select(C0&C1, a, b)
2107
59.0k
      // We choose this as normal form to enable folding on the And and shortening
2108
59.0k
      // paths for the values (this helps GetUnderlyingObjects() for example).
2109
59.0k
      if (TrueSI->getFalseValue() == FalseVal && 
TrueSI->hasOneUse()184
) {
2110
97
        Value *And = Builder.CreateAnd(CondVal, TrueSI->getCondition());
2111
97
        SI.setOperand(0, And);
2112
97
        SI.setOperand(1, TrueSI->getTrueValue());
2113
97
        return &SI;
2114
97
      }
2115
1.16M
    }
2116
59.1k
  }
2117
1.16M
  if (SelectInst *FalseSI = dyn_cast<SelectInst>(FalseVal)) {
2118
120k
    if (FalseSI->getCondition()->getType() == CondVal->getType()) {
2119
120k
      // select(C, a, select(C, b, c)) -> select(C, a, c)
2120
120k
      if (FalseSI->getCondition() == CondVal) {
2121
29
        if (SI.getFalseValue() == FalseSI->getFalseValue())
2122
2
          return nullptr;
2123
27
        SI.setOperand(2, FalseSI->getFalseValue());
2124
27
        return &SI;
2125
27
      }
2126
120k
      // select(C0, a, select(C1, a, b)) -> select(C0|C1, a, b)
2127
120k
      if (FalseSI->getTrueValue() == TrueVal && 
FalseSI->hasOneUse()196
) {
2128
48
        Value *Or = Builder.CreateOr(CondVal, FalseSI->getCondition());
2129
48
        SI.setOperand(0, Or);
2130
48
        SI.setOperand(2, FalseSI->getFalseValue());
2131
48
        return &SI;
2132
48
      }
2133
1.16M
    }
2134
120k
  }
2135
1.16M
2136
1.16M
  auto canMergeSelectThroughBinop = [](BinaryOperator *BO) {
2137
230k
    // The select might be preventing a division by 0.
2138
230k
    switch (BO->getOpcode()) {
2139
230k
    default:
2140
227k
      return true;
2141
230k
    case Instruction::SRem:
2142
2.94k
    case Instruction::URem:
2143
2.94k
    case Instruction::SDiv:
2144
2.94k
    case Instruction::UDiv:
2145
2.94k
      return false;
2146
230k
    }
2147
230k
  };
2148
1.16M
2149
1.16M
  // Try to simplify a binop sandwiched between 2 selects with the same
2150
1.16M
  // condition.
2151
1.16M
  // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
2152
1.16M
  BinaryOperator *TrueBO;
2153
1.16M
  if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) &&
2154
1.16M
      
canMergeSelectThroughBinop(TrueBO)162k
) {
2155
160k
    if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(0))) {
2156
3.49k
      if (TrueBOSI->getCondition() == CondVal) {
2157
2
        TrueBO->setOperand(0, TrueBOSI->getTrueValue());
2158
2
        Worklist.Add(TrueBO);
2159
2
        return &SI;
2160
2
      }
2161
160k
    }
2162
160k
    if (auto *TrueBOSI = dyn_cast<SelectInst>(TrueBO->getOperand(1))) {
2163
20.7k
      if (TrueBOSI->getCondition() == CondVal) {
2164
4
        TrueBO->setOperand(1, TrueBOSI->getTrueValue());
2165
4
        Worklist.Add(TrueBO);
2166
4
        return &SI;
2167
4
      }
2168
1.16M
    }
2169
160k
  }
2170
1.16M
2171
1.16M
  // select(C, Z, binop(select(C, X, Y), W)) -> select(C, Z, binop(Y, W))
2172
1.16M
  BinaryOperator *FalseBO;
2173
1.16M
  if (match(FalseVal, m_OneUse(m_BinOp(FalseBO))) &&
2174
1.16M
      
canMergeSelectThroughBinop(FalseBO)67.5k
) {
2175
67.4k
    if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(0))) {
2176
712
      if (FalseBOSI->getCondition() == CondVal) {
2177
7
        FalseBO->setOperand(0, FalseBOSI->getFalseValue());
2178
7
        Worklist.Add(FalseBO);
2179
7
        return &SI;
2180
7
      }
2181
67.4k
    }
2182
67.4k
    if (auto *FalseBOSI = dyn_cast<SelectInst>(FalseBO->getOperand(1))) {
2183
702
      if (FalseBOSI->getCondition() == CondVal) {
2184
0
        FalseBO->setOperand(1, FalseBOSI->getFalseValue());
2185
0
        Worklist.Add(FalseBO);
2186
0
        return &SI;
2187
0
      }
2188
1.16M
    }
2189
67.4k
  }
2190
1.16M
2191
1.16M
  Value *NotCond;
2192
1.16M
  if (match(CondVal, m_Not(m_Value(NotCond)))) {
2193
982
    SI.setOperand(0, NotCond);
2194
982
    SI.setOperand(1, FalseVal);
2195
982
    SI.setOperand(2, TrueVal);
2196
982
    SI.swapProfMetadata();
2197
982
    return &SI;
2198
982
  }
2199
1.16M
2200
1.16M
  if (VectorType *VecTy = dyn_cast<VectorType>(SelType)) {
2201
7.96k
    unsigned VWidth = VecTy->getNumElements();
2202
7.96k
    APInt UndefElts(VWidth, 0);
2203
7.96k
    APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
2204
7.96k
    if (Value *V = SimplifyDemandedVectorElts(&SI, AllOnesEltMask, UndefElts)) {
2205
0
      if (V != &SI)
2206
0
        return replaceInstUsesWith(SI, V);
2207
0
      return &SI;
2208
0
    }
2209
7.96k
  }
2210
1.16M
2211
1.16M
  // If we can compute the condition, there's no need for a select.
2212
1.16M
  // Like the above fold, we are attempting to reduce compile-time cost by
2213
1.16M
  // putting this fold here with limitations rather than in InstSimplify.
2214
1.16M
  // The motivation for this call into value tracking is to take advantage of
2215
1.16M
  // the assumption cache, so make sure that is populated.
2216
1.16M
  if (!CondVal->getType()->isVectorTy() && 
!AC.assumptions().empty()1.16M
) {
2217
5
    KnownBits Known(1);
2218
5
    computeKnownBits(CondVal, Known, 0, &SI);
2219
5
    if (Known.One.isOneValue())
2220
1
      return replaceInstUsesWith(SI, TrueVal);
2221
4
    if (Known.Zero.isOneValue())
2222
1
      return replaceInstUsesWith(SI, FalseVal);
2223
1.16M
  }
2224
1.16M
2225
1.16M
  if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, Builder))
2226
3
    return BitCastSel;
2227
1.16M
2228
1.16M
  // Simplify selects that test the returned flag of cmpxchg instructions.
2229
1.16M
  if (Instruction *Select = foldSelectCmpXchg(SI))
2230
40
    return Select;
2231
1.16M
2232
1.16M
  if (Instruction *Select = foldSelectBinOpIdentity(SI, TLI))
2233
39
    return Select;
2234
1.16M
2235
1.16M
  if (Instruction *Rot = foldSelectRotate(SI))
2236
10
    return Rot;
2237
1.16M
2238
1.16M
  return nullptr;
2239
1.16M
}