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