1 //===- InstCombineSelect.cpp ----------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the visitSelect function.
12 //===----------------------------------------------------------------------===//
14 #include "InstCombine.h"
15 #include "llvm/Support/PatternMatch.h"
16 #include "llvm/Analysis/ConstantFolding.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
19 using namespace PatternMatch
;
21 /// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms,
22 /// returning the kind and providing the out parameter results if we
23 /// successfully match.
24 static SelectPatternFlavor
25 MatchSelectPattern(Value
*V
, Value
*&LHS
, Value
*&RHS
) {
26 SelectInst
*SI
= dyn_cast
<SelectInst
>(V
);
27 if (SI
== 0) return SPF_UNKNOWN
;
29 ICmpInst
*ICI
= dyn_cast
<ICmpInst
>(SI
->getCondition());
30 if (ICI
== 0) return SPF_UNKNOWN
;
32 LHS
= ICI
->getOperand(0);
33 RHS
= ICI
->getOperand(1);
35 // (icmp X, Y) ? X : Y
36 if (SI
->getTrueValue() == ICI
->getOperand(0) &&
37 SI
->getFalseValue() == ICI
->getOperand(1)) {
38 switch (ICI
->getPredicate()) {
39 default: return SPF_UNKNOWN
; // Equality.
40 case ICmpInst::ICMP_UGT
:
41 case ICmpInst::ICMP_UGE
: return SPF_UMAX
;
42 case ICmpInst::ICMP_SGT
:
43 case ICmpInst::ICMP_SGE
: return SPF_SMAX
;
44 case ICmpInst::ICMP_ULT
:
45 case ICmpInst::ICMP_ULE
: return SPF_UMIN
;
46 case ICmpInst::ICMP_SLT
:
47 case ICmpInst::ICMP_SLE
: return SPF_SMIN
;
51 // (icmp X, Y) ? Y : X
52 if (SI
->getTrueValue() == ICI
->getOperand(1) &&
53 SI
->getFalseValue() == ICI
->getOperand(0)) {
54 switch (ICI
->getPredicate()) {
55 default: return SPF_UNKNOWN
; // Equality.
56 case ICmpInst::ICMP_UGT
:
57 case ICmpInst::ICMP_UGE
: return SPF_UMIN
;
58 case ICmpInst::ICMP_SGT
:
59 case ICmpInst::ICMP_SGE
: return SPF_SMIN
;
60 case ICmpInst::ICMP_ULT
:
61 case ICmpInst::ICMP_ULE
: return SPF_UMAX
;
62 case ICmpInst::ICMP_SLT
:
63 case ICmpInst::ICMP_SLE
: return SPF_SMAX
;
67 // TODO: (X > 4) ? X : 5 --> (X >= 5) ? X : 5 --> MAX(X, 5)
73 /// GetSelectFoldableOperands - We want to turn code that looks like this:
75 /// %D = select %cond, %C, %A
77 /// %C = select %cond, %B, 0
80 /// Assuming that the specified instruction is an operand to the select, return
81 /// a bitmask indicating which operands of this instruction are foldable if they
82 /// equal the other incoming value of the select.
84 static unsigned GetSelectFoldableOperands(Instruction
*I
) {
85 switch (I
->getOpcode()) {
86 case Instruction::Add
:
87 case Instruction::Mul
:
88 case Instruction::And
:
90 case Instruction::Xor
:
91 return 3; // Can fold through either operand.
92 case Instruction::Sub
: // Can only fold on the amount subtracted.
93 case Instruction::Shl
: // Can only fold on the shift amount.
94 case Instruction::LShr
:
95 case Instruction::AShr
:
98 return 0; // Cannot fold
102 /// GetSelectFoldableConstant - For the same transformation as the previous
103 /// function, return the identity constant that goes into the select.
104 static Constant
*GetSelectFoldableConstant(Instruction
*I
) {
105 switch (I
->getOpcode()) {
106 default: llvm_unreachable("This cannot happen!");
107 case Instruction::Add
:
108 case Instruction::Sub
:
109 case Instruction::Or
:
110 case Instruction::Xor
:
111 case Instruction::Shl
:
112 case Instruction::LShr
:
113 case Instruction::AShr
:
114 return Constant::getNullValue(I
->getType());
115 case Instruction::And
:
116 return Constant::getAllOnesValue(I
->getType());
117 case Instruction::Mul
:
118 return ConstantInt::get(I
->getType(), 1);
122 /// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI
123 /// have the same opcode and only one use each. Try to simplify this.
124 Instruction
*InstCombiner::FoldSelectOpOp(SelectInst
&SI
, Instruction
*TI
,
126 if (TI
->getNumOperands() == 1) {
127 // If this is a non-volatile load or a cast from the same type,
130 if (TI
->getOperand(0)->getType() != FI
->getOperand(0)->getType())
132 // The select condition may be a vector. We may only change the operand
133 // type if the vector width remains the same (and matches the condition).
134 Type
*CondTy
= SI
.getCondition()->getType();
135 if (CondTy
->isVectorTy() && CondTy
->getVectorNumElements() !=
136 FI
->getOperand(0)->getType()->getVectorNumElements())
139 return 0; // unknown unary op.
142 // Fold this by inserting a select from the input values.
143 Value
*NewSI
= Builder
->CreateSelect(SI
.getCondition(), TI
->getOperand(0),
144 FI
->getOperand(0), SI
.getName()+".v");
145 return CastInst::Create(Instruction::CastOps(TI
->getOpcode()), NewSI
,
149 // Only handle binary operators here.
150 if (!isa
<BinaryOperator
>(TI
))
153 // Figure out if the operations have any operands in common.
154 Value
*MatchOp
, *OtherOpT
, *OtherOpF
;
156 if (TI
->getOperand(0) == FI
->getOperand(0)) {
157 MatchOp
= TI
->getOperand(0);
158 OtherOpT
= TI
->getOperand(1);
159 OtherOpF
= FI
->getOperand(1);
160 MatchIsOpZero
= true;
161 } else if (TI
->getOperand(1) == FI
->getOperand(1)) {
162 MatchOp
= TI
->getOperand(1);
163 OtherOpT
= TI
->getOperand(0);
164 OtherOpF
= FI
->getOperand(0);
165 MatchIsOpZero
= false;
166 } else if (!TI
->isCommutative()) {
168 } else if (TI
->getOperand(0) == FI
->getOperand(1)) {
169 MatchOp
= TI
->getOperand(0);
170 OtherOpT
= TI
->getOperand(1);
171 OtherOpF
= FI
->getOperand(0);
172 MatchIsOpZero
= true;
173 } else if (TI
->getOperand(1) == FI
->getOperand(0)) {
174 MatchOp
= TI
->getOperand(1);
175 OtherOpT
= TI
->getOperand(0);
176 OtherOpF
= FI
->getOperand(1);
177 MatchIsOpZero
= true;
182 // If we reach here, they do have operations in common.
183 Value
*NewSI
= Builder
->CreateSelect(SI
.getCondition(), OtherOpT
,
184 OtherOpF
, SI
.getName()+".v");
186 if (BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(TI
)) {
188 return BinaryOperator::Create(BO
->getOpcode(), MatchOp
, NewSI
);
190 return BinaryOperator::Create(BO
->getOpcode(), NewSI
, MatchOp
);
192 llvm_unreachable("Shouldn't get here");
195 static bool isSelect01(Constant
*C1
, Constant
*C2
) {
196 ConstantInt
*C1I
= dyn_cast
<ConstantInt
>(C1
);
199 ConstantInt
*C2I
= dyn_cast
<ConstantInt
>(C2
);
202 if (!C1I
->isZero() && !C2I
->isZero()) // One side must be zero.
204 return C1I
->isOne() || C1I
->isAllOnesValue() ||
205 C2I
->isOne() || C2I
->isAllOnesValue();
208 /// FoldSelectIntoOp - Try fold the select into one of the operands to
209 /// facilitate further optimization.
210 Instruction
*InstCombiner::FoldSelectIntoOp(SelectInst
&SI
, Value
*TrueVal
,
212 // See the comment above GetSelectFoldableOperands for a description of the
213 // transformation we are doing here.
214 if (Instruction
*TVI
= dyn_cast
<Instruction
>(TrueVal
)) {
215 if (TVI
->hasOneUse() && TVI
->getNumOperands() == 2 &&
216 !isa
<Constant
>(FalseVal
)) {
217 if (unsigned SFO
= GetSelectFoldableOperands(TVI
)) {
218 unsigned OpToFold
= 0;
219 if ((SFO
& 1) && FalseVal
== TVI
->getOperand(0)) {
221 } else if ((SFO
& 2) && FalseVal
== TVI
->getOperand(1)) {
226 Constant
*C
= GetSelectFoldableConstant(TVI
);
227 Value
*OOp
= TVI
->getOperand(2-OpToFold
);
228 // Avoid creating select between 2 constants unless it's selecting
229 // between 0, 1 and -1.
230 if (!isa
<Constant
>(OOp
) || isSelect01(C
, cast
<Constant
>(OOp
))) {
231 Value
*NewSel
= Builder
->CreateSelect(SI
.getCondition(), OOp
, C
);
232 NewSel
->takeName(TVI
);
233 BinaryOperator
*TVI_BO
= cast
<BinaryOperator
>(TVI
);
234 BinaryOperator
*BO
= BinaryOperator::Create(TVI_BO
->getOpcode(),
236 if (isa
<PossiblyExactOperator
>(BO
))
237 BO
->setIsExact(TVI_BO
->isExact());
238 if (isa
<OverflowingBinaryOperator
>(BO
)) {
239 BO
->setHasNoUnsignedWrap(TVI_BO
->hasNoUnsignedWrap());
240 BO
->setHasNoSignedWrap(TVI_BO
->hasNoSignedWrap());
249 if (Instruction
*FVI
= dyn_cast
<Instruction
>(FalseVal
)) {
250 if (FVI
->hasOneUse() && FVI
->getNumOperands() == 2 &&
251 !isa
<Constant
>(TrueVal
)) {
252 if (unsigned SFO
= GetSelectFoldableOperands(FVI
)) {
253 unsigned OpToFold
= 0;
254 if ((SFO
& 1) && TrueVal
== FVI
->getOperand(0)) {
256 } else if ((SFO
& 2) && TrueVal
== FVI
->getOperand(1)) {
261 Constant
*C
= GetSelectFoldableConstant(FVI
);
262 Value
*OOp
= FVI
->getOperand(2-OpToFold
);
263 // Avoid creating select between 2 constants unless it's selecting
264 // between 0, 1 and -1.
265 if (!isa
<Constant
>(OOp
) || isSelect01(C
, cast
<Constant
>(OOp
))) {
266 Value
*NewSel
= Builder
->CreateSelect(SI
.getCondition(), C
, OOp
);
267 NewSel
->takeName(FVI
);
268 BinaryOperator
*FVI_BO
= cast
<BinaryOperator
>(FVI
);
269 BinaryOperator
*BO
= BinaryOperator::Create(FVI_BO
->getOpcode(),
271 if (isa
<PossiblyExactOperator
>(BO
))
272 BO
->setIsExact(FVI_BO
->isExact());
273 if (isa
<OverflowingBinaryOperator
>(BO
)) {
274 BO
->setHasNoUnsignedWrap(FVI_BO
->hasNoUnsignedWrap());
275 BO
->setHasNoSignedWrap(FVI_BO
->hasNoSignedWrap());
287 /// SimplifyWithOpReplaced - See if V simplifies when its operand Op is
288 /// replaced with RepOp.
289 static Value
*SimplifyWithOpReplaced(Value
*V
, Value
*Op
, Value
*RepOp
,
290 const TargetData
*TD
,
291 const TargetLibraryInfo
*TLI
) {
292 // Trivial replacement.
296 Instruction
*I
= dyn_cast
<Instruction
>(V
);
300 // If this is a binary operator, try to simplify it with the replaced op.
301 if (BinaryOperator
*B
= dyn_cast
<BinaryOperator
>(I
)) {
302 if (B
->getOperand(0) == Op
)
303 return SimplifyBinOp(B
->getOpcode(), RepOp
, B
->getOperand(1), TD
, TLI
);
304 if (B
->getOperand(1) == Op
)
305 return SimplifyBinOp(B
->getOpcode(), B
->getOperand(0), RepOp
, TD
, TLI
);
308 // Same for CmpInsts.
309 if (CmpInst
*C
= dyn_cast
<CmpInst
>(I
)) {
310 if (C
->getOperand(0) == Op
)
311 return SimplifyCmpInst(C
->getPredicate(), RepOp
, C
->getOperand(1), TD
,
313 if (C
->getOperand(1) == Op
)
314 return SimplifyCmpInst(C
->getPredicate(), C
->getOperand(0), RepOp
, TD
,
318 // TODO: We could hand off more cases to instsimplify here.
320 // If all operands are constant after substituting Op for RepOp then we can
321 // constant fold the instruction.
322 if (Constant
*CRepOp
= dyn_cast
<Constant
>(RepOp
)) {
323 // Build a list of all constant operands.
324 SmallVector
<Constant
*, 8> ConstOps
;
325 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
) {
326 if (I
->getOperand(i
) == Op
)
327 ConstOps
.push_back(CRepOp
);
328 else if (Constant
*COp
= dyn_cast
<Constant
>(I
->getOperand(i
)))
329 ConstOps
.push_back(COp
);
334 // All operands were constants, fold it.
335 if (ConstOps
.size() == I
->getNumOperands()) {
336 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
))
337 if (!LI
->isVolatile())
338 return ConstantFoldLoadFromConstPtr(ConstOps
[0], TD
);
340 return ConstantFoldInstOperands(I
->getOpcode(), I
->getType(),
348 /// visitSelectInstWithICmp - Visit a SelectInst that has an
349 /// ICmpInst as its first operand.
351 Instruction
*InstCombiner::visitSelectInstWithICmp(SelectInst
&SI
,
353 bool Changed
= false;
354 ICmpInst::Predicate Pred
= ICI
->getPredicate();
355 Value
*CmpLHS
= ICI
->getOperand(0);
356 Value
*CmpRHS
= ICI
->getOperand(1);
357 Value
*TrueVal
= SI
.getTrueValue();
358 Value
*FalseVal
= SI
.getFalseValue();
360 // Check cases where the comparison is with a constant that
361 // can be adjusted to fit the min/max idiom. We may move or edit ICI
362 // here, so make sure the select is the only user.
363 if (ICI
->hasOneUse())
364 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(CmpRHS
)) {
365 // X < MIN ? T : F --> F
366 if ((Pred
== ICmpInst::ICMP_SLT
|| Pred
== ICmpInst::ICMP_ULT
)
367 && CI
->isMinValue(Pred
== ICmpInst::ICMP_SLT
))
368 return ReplaceInstUsesWith(SI
, FalseVal
);
369 // X > MAX ? T : F --> F
370 else if ((Pred
== ICmpInst::ICMP_SGT
|| Pred
== ICmpInst::ICMP_UGT
)
371 && CI
->isMaxValue(Pred
== ICmpInst::ICMP_SGT
))
372 return ReplaceInstUsesWith(SI
, FalseVal
);
375 case ICmpInst::ICMP_ULT
:
376 case ICmpInst::ICMP_SLT
:
377 case ICmpInst::ICMP_UGT
:
378 case ICmpInst::ICMP_SGT
: {
379 // These transformations only work for selects over integers.
380 IntegerType
*SelectTy
= dyn_cast
<IntegerType
>(SI
.getType());
384 Constant
*AdjustedRHS
;
385 if (Pred
== ICmpInst::ICMP_UGT
|| Pred
== ICmpInst::ICMP_SGT
)
386 AdjustedRHS
= ConstantInt::get(CI
->getContext(), CI
->getValue() + 1);
387 else // (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT)
388 AdjustedRHS
= ConstantInt::get(CI
->getContext(), CI
->getValue() - 1);
390 // X > C ? X : C+1 --> X < C+1 ? C+1 : X
391 // X < C ? X : C-1 --> X > C-1 ? C-1 : X
392 if ((CmpLHS
== TrueVal
&& AdjustedRHS
== FalseVal
) ||
393 (CmpLHS
== FalseVal
&& AdjustedRHS
== TrueVal
))
394 ; // Nothing to do here. Values match without any sign/zero extension.
396 // Types do not match. Instead of calculating this with mixed types
397 // promote all to the larger type. This enables scalar evolution to
398 // analyze this expression.
399 else if (CmpRHS
->getType()->getScalarSizeInBits()
400 < SelectTy
->getBitWidth()) {
401 Constant
*sextRHS
= ConstantExpr::getSExt(AdjustedRHS
, SelectTy
);
403 // X = sext x; x >s c ? X : C+1 --> X = sext x; X <s C+1 ? C+1 : X
404 // X = sext x; x <s c ? X : C-1 --> X = sext x; X >s C-1 ? C-1 : X
405 // X = sext x; x >u c ? X : C+1 --> X = sext x; X <u C+1 ? C+1 : X
406 // X = sext x; x <u c ? X : C-1 --> X = sext x; X >u C-1 ? C-1 : X
407 if (match(TrueVal
, m_SExt(m_Specific(CmpLHS
))) &&
408 sextRHS
== FalseVal
) {
410 AdjustedRHS
= sextRHS
;
411 } else if (match(FalseVal
, m_SExt(m_Specific(CmpLHS
))) &&
412 sextRHS
== TrueVal
) {
414 AdjustedRHS
= sextRHS
;
415 } else if (ICI
->isUnsigned()) {
416 Constant
*zextRHS
= ConstantExpr::getZExt(AdjustedRHS
, SelectTy
);
417 // X = zext x; x >u c ? X : C+1 --> X = zext x; X <u C+1 ? C+1 : X
418 // X = zext x; x <u c ? X : C-1 --> X = zext x; X >u C-1 ? C-1 : X
419 // zext + signed compare cannot be changed:
420 // 0xff <s 0x00, but 0x00ff >s 0x0000
421 if (match(TrueVal
, m_ZExt(m_Specific(CmpLHS
))) &&
422 zextRHS
== FalseVal
) {
424 AdjustedRHS
= zextRHS
;
425 } else if (match(FalseVal
, m_ZExt(m_Specific(CmpLHS
))) &&
426 zextRHS
== TrueVal
) {
428 AdjustedRHS
= zextRHS
;
436 Pred
= ICmpInst::getSwappedPredicate(Pred
);
437 CmpRHS
= AdjustedRHS
;
438 std::swap(FalseVal
, TrueVal
);
439 ICI
->setPredicate(Pred
);
440 ICI
->setOperand(0, CmpLHS
);
441 ICI
->setOperand(1, CmpRHS
);
442 SI
.setOperand(1, TrueVal
);
443 SI
.setOperand(2, FalseVal
);
445 // Move ICI instruction right before the select instruction. Otherwise
446 // the sext/zext value may be defined after the ICI instruction uses it.
447 ICI
->moveBefore(&SI
);
455 // Transform (X >s -1) ? C1 : C2 --> ((X >>s 31) & (C2 - C1)) + C1
456 // and (X <s 0) ? C2 : C1 --> ((X >>s 31) & (C2 - C1)) + C1
457 // FIXME: Type and constness constraints could be lifted, but we have to
458 // watch code size carefully. We should consider xor instead of
459 // sub/add when we decide to do that.
460 if (IntegerType
*Ty
= dyn_cast
<IntegerType
>(CmpLHS
->getType())) {
461 if (TrueVal
->getType() == Ty
) {
462 if (ConstantInt
*Cmp
= dyn_cast
<ConstantInt
>(CmpRHS
)) {
463 ConstantInt
*C1
= NULL
, *C2
= NULL
;
464 if (Pred
== ICmpInst::ICMP_SGT
&& Cmp
->isAllOnesValue()) {
465 C1
= dyn_cast
<ConstantInt
>(TrueVal
);
466 C2
= dyn_cast
<ConstantInt
>(FalseVal
);
467 } else if (Pred
== ICmpInst::ICMP_SLT
&& Cmp
->isNullValue()) {
468 C1
= dyn_cast
<ConstantInt
>(FalseVal
);
469 C2
= dyn_cast
<ConstantInt
>(TrueVal
);
472 // This shift results in either -1 or 0.
473 Value
*AShr
= Builder
->CreateAShr(CmpLHS
, Ty
->getBitWidth()-1);
475 // Check if we can express the operation with a single or.
476 if (C2
->isAllOnesValue())
477 return ReplaceInstUsesWith(SI
, Builder
->CreateOr(AShr
, C1
));
479 Value
*And
= Builder
->CreateAnd(AShr
, C2
->getValue()-C1
->getValue());
480 return ReplaceInstUsesWith(SI
, Builder
->CreateAdd(And
, C1
));
486 // If we have an equality comparison then we know the value in one of the
487 // arms of the select. See if substituting this value into the arm and
488 // simplifying the result yields the same value as the other arm.
489 if (Pred
== ICmpInst::ICMP_EQ
) {
490 if (SimplifyWithOpReplaced(FalseVal
, CmpLHS
, CmpRHS
, TD
, TLI
) == TrueVal
||
491 SimplifyWithOpReplaced(FalseVal
, CmpRHS
, CmpLHS
, TD
, TLI
) == TrueVal
)
492 return ReplaceInstUsesWith(SI
, FalseVal
);
493 if (SimplifyWithOpReplaced(TrueVal
, CmpLHS
, CmpRHS
, TD
, TLI
) == FalseVal
||
494 SimplifyWithOpReplaced(TrueVal
, CmpRHS
, CmpLHS
, TD
, TLI
) == FalseVal
)
495 return ReplaceInstUsesWith(SI
, FalseVal
);
496 } else if (Pred
== ICmpInst::ICMP_NE
) {
497 if (SimplifyWithOpReplaced(TrueVal
, CmpLHS
, CmpRHS
, TD
, TLI
) == FalseVal
||
498 SimplifyWithOpReplaced(TrueVal
, CmpRHS
, CmpLHS
, TD
, TLI
) == FalseVal
)
499 return ReplaceInstUsesWith(SI
, TrueVal
);
500 if (SimplifyWithOpReplaced(FalseVal
, CmpLHS
, CmpRHS
, TD
, TLI
) == TrueVal
||
501 SimplifyWithOpReplaced(FalseVal
, CmpRHS
, CmpLHS
, TD
, TLI
) == TrueVal
)
502 return ReplaceInstUsesWith(SI
, TrueVal
);
505 // NOTE: if we wanted to, this is where to detect integer MIN/MAX
507 if (CmpRHS
!= CmpLHS
&& isa
<Constant
>(CmpRHS
)) {
508 if (CmpLHS
== TrueVal
&& Pred
== ICmpInst::ICMP_EQ
) {
509 // Transform (X == C) ? X : Y -> (X == C) ? C : Y
510 SI
.setOperand(1, CmpRHS
);
512 } else if (CmpLHS
== FalseVal
&& Pred
== ICmpInst::ICMP_NE
) {
513 // Transform (X != C) ? Y : X -> (X != C) ? Y : C
514 SI
.setOperand(2, CmpRHS
);
519 return Changed
? &SI
: 0;
523 /// CanSelectOperandBeMappingIntoPredBlock - SI is a select whose condition is a
524 /// PHI node (but the two may be in different blocks). See if the true/false
525 /// values (V) are live in all of the predecessor blocks of the PHI. For
526 /// example, cases like this cannot be mapped:
528 /// X = phi [ C1, BB1], [C2, BB2]
530 /// Z = select X, Y, 0
532 /// because Y is not live in BB1/BB2.
534 static bool CanSelectOperandBeMappingIntoPredBlock(const Value
*V
,
535 const SelectInst
&SI
) {
536 // If the value is a non-instruction value like a constant or argument, it
537 // can always be mapped.
538 const Instruction
*I
= dyn_cast
<Instruction
>(V
);
539 if (I
== 0) return true;
541 // If V is a PHI node defined in the same block as the condition PHI, we can
542 // map the arguments.
543 const PHINode
*CondPHI
= cast
<PHINode
>(SI
.getCondition());
545 if (const PHINode
*VP
= dyn_cast
<PHINode
>(I
))
546 if (VP
->getParent() == CondPHI
->getParent())
549 // Otherwise, if the PHI and select are defined in the same block and if V is
550 // defined in a different block, then we can transform it.
551 if (SI
.getParent() == CondPHI
->getParent() &&
552 I
->getParent() != CondPHI
->getParent())
555 // Otherwise we have a 'hard' case and we can't tell without doing more
556 // detailed dominator based analysis, punt.
560 /// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form:
561 /// SPF2(SPF1(A, B), C)
562 Instruction
*InstCombiner::FoldSPFofSPF(Instruction
*Inner
,
563 SelectPatternFlavor SPF1
,
566 SelectPatternFlavor SPF2
, Value
*C
) {
567 if (C
== A
|| C
== B
) {
568 // MAX(MAX(A, B), B) -> MAX(A, B)
569 // MIN(MIN(a, b), a) -> MIN(a, b)
571 return ReplaceInstUsesWith(Outer
, Inner
);
573 // MAX(MIN(a, b), a) -> a
574 // MIN(MAX(a, b), a) -> a
575 if ((SPF1
== SPF_SMIN
&& SPF2
== SPF_SMAX
) ||
576 (SPF1
== SPF_SMAX
&& SPF2
== SPF_SMIN
) ||
577 (SPF1
== SPF_UMIN
&& SPF2
== SPF_UMAX
) ||
578 (SPF1
== SPF_UMAX
&& SPF2
== SPF_UMIN
))
579 return ReplaceInstUsesWith(Outer
, C
);
582 // TODO: MIN(MIN(A, 23), 97)
587 /// foldSelectICmpAnd - If one of the constants is zero (we know they can't
588 /// both be) and we have an icmp instruction with zero, and we have an 'and'
589 /// with the non-constant value and a power of two we can turn the select
590 /// into a shift on the result of the 'and'.
591 static Value
*foldSelectICmpAnd(const SelectInst
&SI
, ConstantInt
*TrueVal
,
592 ConstantInt
*FalseVal
,
593 InstCombiner::BuilderTy
*Builder
) {
594 const ICmpInst
*IC
= dyn_cast
<ICmpInst
>(SI
.getCondition());
595 if (!IC
|| !IC
->isEquality())
598 if (!match(IC
->getOperand(1), m_Zero()))
602 Value
*LHS
= IC
->getOperand(0);
603 if (LHS
->getType() != SI
.getType() ||
604 !match(LHS
, m_And(m_Value(), m_ConstantInt(AndRHS
))))
607 // If both select arms are non-zero see if we have a select of the form
608 // 'x ? 2^n + C : C'. Then we can offset both arms by C, use the logic
609 // for 'x ? 2^n : 0' and fix the thing up at the end.
610 ConstantInt
*Offset
= 0;
611 if (!TrueVal
->isZero() && !FalseVal
->isZero()) {
612 if ((TrueVal
->getValue() - FalseVal
->getValue()).isPowerOf2())
614 else if ((FalseVal
->getValue() - TrueVal
->getValue()).isPowerOf2())
619 // Adjust TrueVal and FalseVal to the offset.
620 TrueVal
= ConstantInt::get(Builder
->getContext(),
621 TrueVal
->getValue() - Offset
->getValue());
622 FalseVal
= ConstantInt::get(Builder
->getContext(),
623 FalseVal
->getValue() - Offset
->getValue());
626 // Make sure the mask in the 'and' and one of the select arms is a power of 2.
627 if (!AndRHS
->getValue().isPowerOf2() ||
628 (!TrueVal
->getValue().isPowerOf2() &&
629 !FalseVal
->getValue().isPowerOf2()))
632 // Determine which shift is needed to transform result of the 'and' into the
634 ConstantInt
*ValC
= !TrueVal
->isZero() ? TrueVal
: FalseVal
;
635 unsigned ValZeros
= ValC
->getValue().logBase2();
636 unsigned AndZeros
= AndRHS
->getValue().logBase2();
639 if (ValZeros
> AndZeros
)
640 V
= Builder
->CreateShl(V
, ValZeros
- AndZeros
);
641 else if (ValZeros
< AndZeros
)
642 V
= Builder
->CreateLShr(V
, AndZeros
- ValZeros
);
644 // Okay, now we know that everything is set up, we just don't know whether we
645 // have a icmp_ne or icmp_eq and whether the true or false val is the zero.
646 bool ShouldNotVal
= !TrueVal
->isZero();
647 ShouldNotVal
^= IC
->getPredicate() == ICmpInst::ICMP_NE
;
649 V
= Builder
->CreateXor(V
, ValC
);
651 // Apply an offset if needed.
653 V
= Builder
->CreateAdd(V
, Offset
);
657 Instruction
*InstCombiner::visitSelectInst(SelectInst
&SI
) {
658 Value
*CondVal
= SI
.getCondition();
659 Value
*TrueVal
= SI
.getTrueValue();
660 Value
*FalseVal
= SI
.getFalseValue();
662 if (Value
*V
= SimplifySelectInst(CondVal
, TrueVal
, FalseVal
, TD
))
663 return ReplaceInstUsesWith(SI
, V
);
665 if (SI
.getType()->isIntegerTy(1)) {
666 if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(TrueVal
)) {
667 if (C
->getZExtValue()) {
668 // Change: A = select B, true, C --> A = or B, C
669 return BinaryOperator::CreateOr(CondVal
, FalseVal
);
671 // Change: A = select B, false, C --> A = and !B, C
672 Value
*NotCond
= Builder
->CreateNot(CondVal
, "not."+CondVal
->getName());
673 return BinaryOperator::CreateAnd(NotCond
, FalseVal
);
674 } else if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(FalseVal
)) {
675 if (C
->getZExtValue() == false) {
676 // Change: A = select B, C, false --> A = and B, C
677 return BinaryOperator::CreateAnd(CondVal
, TrueVal
);
679 // Change: A = select B, C, true --> A = or !B, C
680 Value
*NotCond
= Builder
->CreateNot(CondVal
, "not."+CondVal
->getName());
681 return BinaryOperator::CreateOr(NotCond
, TrueVal
);
684 // select a, b, a -> a&b
685 // select a, a, b -> a|b
686 if (CondVal
== TrueVal
)
687 return BinaryOperator::CreateOr(CondVal
, FalseVal
);
688 else if (CondVal
== FalseVal
)
689 return BinaryOperator::CreateAnd(CondVal
, TrueVal
);
691 // select a, ~a, b -> (~a)&b
692 // select a, b, ~a -> (~a)|b
693 if (match(TrueVal
, m_Not(m_Specific(CondVal
))))
694 return BinaryOperator::CreateAnd(TrueVal
, FalseVal
);
695 else if (match(FalseVal
, m_Not(m_Specific(CondVal
))))
696 return BinaryOperator::CreateOr(TrueVal
, FalseVal
);
699 // Selecting between two integer constants?
700 if (ConstantInt
*TrueValC
= dyn_cast
<ConstantInt
>(TrueVal
))
701 if (ConstantInt
*FalseValC
= dyn_cast
<ConstantInt
>(FalseVal
)) {
702 // select C, 1, 0 -> zext C to int
703 if (FalseValC
->isZero() && TrueValC
->getValue() == 1)
704 return new ZExtInst(CondVal
, SI
.getType());
706 // select C, -1, 0 -> sext C to int
707 if (FalseValC
->isZero() && TrueValC
->isAllOnesValue())
708 return new SExtInst(CondVal
, SI
.getType());
710 // select C, 0, 1 -> zext !C to int
711 if (TrueValC
->isZero() && FalseValC
->getValue() == 1) {
712 Value
*NotCond
= Builder
->CreateNot(CondVal
, "not."+CondVal
->getName());
713 return new ZExtInst(NotCond
, SI
.getType());
716 // select C, 0, -1 -> sext !C to int
717 if (TrueValC
->isZero() && FalseValC
->isAllOnesValue()) {
718 Value
*NotCond
= Builder
->CreateNot(CondVal
, "not."+CondVal
->getName());
719 return new SExtInst(NotCond
, SI
.getType());
722 if (Value
*V
= foldSelectICmpAnd(SI
, TrueValC
, FalseValC
, Builder
))
723 return ReplaceInstUsesWith(SI
, V
);
726 // See if we are selecting two values based on a comparison of the two values.
727 if (FCmpInst
*FCI
= dyn_cast
<FCmpInst
>(CondVal
)) {
728 if (FCI
->getOperand(0) == TrueVal
&& FCI
->getOperand(1) == FalseVal
) {
729 // Transform (X == Y) ? X : Y -> Y
730 if (FCI
->getPredicate() == FCmpInst::FCMP_OEQ
) {
731 // This is not safe in general for floating point:
732 // consider X== -0, Y== +0.
733 // It becomes safe if either operand is a nonzero constant.
734 ConstantFP
*CFPt
, *CFPf
;
735 if (((CFPt
= dyn_cast
<ConstantFP
>(TrueVal
)) &&
736 !CFPt
->getValueAPF().isZero()) ||
737 ((CFPf
= dyn_cast
<ConstantFP
>(FalseVal
)) &&
738 !CFPf
->getValueAPF().isZero()))
739 return ReplaceInstUsesWith(SI
, FalseVal
);
741 // Transform (X une Y) ? X : Y -> X
742 if (FCI
->getPredicate() == FCmpInst::FCMP_UNE
) {
743 // This is not safe in general for floating point:
744 // consider X== -0, Y== +0.
745 // It becomes safe if either operand is a nonzero constant.
746 ConstantFP
*CFPt
, *CFPf
;
747 if (((CFPt
= dyn_cast
<ConstantFP
>(TrueVal
)) &&
748 !CFPt
->getValueAPF().isZero()) ||
749 ((CFPf
= dyn_cast
<ConstantFP
>(FalseVal
)) &&
750 !CFPf
->getValueAPF().isZero()))
751 return ReplaceInstUsesWith(SI
, TrueVal
);
753 // NOTE: if we wanted to, this is where to detect MIN/MAX
755 } else if (FCI
->getOperand(0) == FalseVal
&& FCI
->getOperand(1) == TrueVal
){
756 // Transform (X == Y) ? Y : X -> X
757 if (FCI
->getPredicate() == FCmpInst::FCMP_OEQ
) {
758 // This is not safe in general for floating point:
759 // consider X== -0, Y== +0.
760 // It becomes safe if either operand is a nonzero constant.
761 ConstantFP
*CFPt
, *CFPf
;
762 if (((CFPt
= dyn_cast
<ConstantFP
>(TrueVal
)) &&
763 !CFPt
->getValueAPF().isZero()) ||
764 ((CFPf
= dyn_cast
<ConstantFP
>(FalseVal
)) &&
765 !CFPf
->getValueAPF().isZero()))
766 return ReplaceInstUsesWith(SI
, FalseVal
);
768 // Transform (X une Y) ? Y : X -> Y
769 if (FCI
->getPredicate() == FCmpInst::FCMP_UNE
) {
770 // This is not safe in general for floating point:
771 // consider X== -0, Y== +0.
772 // It becomes safe if either operand is a nonzero constant.
773 ConstantFP
*CFPt
, *CFPf
;
774 if (((CFPt
= dyn_cast
<ConstantFP
>(TrueVal
)) &&
775 !CFPt
->getValueAPF().isZero()) ||
776 ((CFPf
= dyn_cast
<ConstantFP
>(FalseVal
)) &&
777 !CFPf
->getValueAPF().isZero()))
778 return ReplaceInstUsesWith(SI
, TrueVal
);
780 // NOTE: if we wanted to, this is where to detect MIN/MAX
782 // NOTE: if we wanted to, this is where to detect ABS
785 // See if we are selecting two values based on a comparison of the two values.
786 if (ICmpInst
*ICI
= dyn_cast
<ICmpInst
>(CondVal
))
787 if (Instruction
*Result
= visitSelectInstWithICmp(SI
, ICI
))
790 if (Instruction
*TI
= dyn_cast
<Instruction
>(TrueVal
))
791 if (Instruction
*FI
= dyn_cast
<Instruction
>(FalseVal
))
792 if (TI
->hasOneUse() && FI
->hasOneUse()) {
793 Instruction
*AddOp
= 0, *SubOp
= 0;
795 // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
796 if (TI
->getOpcode() == FI
->getOpcode())
797 if (Instruction
*IV
= FoldSelectOpOp(SI
, TI
, FI
))
800 // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))). This is
801 // even legal for FP.
802 if ((TI
->getOpcode() == Instruction::Sub
&&
803 FI
->getOpcode() == Instruction::Add
) ||
804 (TI
->getOpcode() == Instruction::FSub
&&
805 FI
->getOpcode() == Instruction::FAdd
)) {
806 AddOp
= FI
; SubOp
= TI
;
807 } else if ((FI
->getOpcode() == Instruction::Sub
&&
808 TI
->getOpcode() == Instruction::Add
) ||
809 (FI
->getOpcode() == Instruction::FSub
&&
810 TI
->getOpcode() == Instruction::FAdd
)) {
811 AddOp
= TI
; SubOp
= FI
;
815 Value
*OtherAddOp
= 0;
816 if (SubOp
->getOperand(0) == AddOp
->getOperand(0)) {
817 OtherAddOp
= AddOp
->getOperand(1);
818 } else if (SubOp
->getOperand(0) == AddOp
->getOperand(1)) {
819 OtherAddOp
= AddOp
->getOperand(0);
823 // So at this point we know we have (Y -> OtherAddOp):
824 // select C, (add X, Y), (sub X, Z)
825 Value
*NegVal
; // Compute -Z
826 if (SI
.getType()->isFPOrFPVectorTy()) {
827 NegVal
= Builder
->CreateFNeg(SubOp
->getOperand(1));
829 NegVal
= Builder
->CreateNeg(SubOp
->getOperand(1));
832 Value
*NewTrueOp
= OtherAddOp
;
833 Value
*NewFalseOp
= NegVal
;
835 std::swap(NewTrueOp
, NewFalseOp
);
837 Builder
->CreateSelect(CondVal
, NewTrueOp
,
838 NewFalseOp
, SI
.getName() + ".p");
840 if (SI
.getType()->isFPOrFPVectorTy())
841 return BinaryOperator::CreateFAdd(SubOp
->getOperand(0), NewSel
);
843 return BinaryOperator::CreateAdd(SubOp
->getOperand(0), NewSel
);
848 // See if we can fold the select into one of our operands.
849 if (SI
.getType()->isIntegerTy()) {
850 if (Instruction
*FoldI
= FoldSelectIntoOp(SI
, TrueVal
, FalseVal
))
853 // MAX(MAX(a, b), a) -> MAX(a, b)
854 // MIN(MIN(a, b), a) -> MIN(a, b)
855 // MAX(MIN(a, b), a) -> a
856 // MIN(MAX(a, b), a) -> a
857 Value
*LHS
, *RHS
, *LHS2
, *RHS2
;
858 if (SelectPatternFlavor SPF
= MatchSelectPattern(&SI
, LHS
, RHS
)) {
859 if (SelectPatternFlavor SPF2
= MatchSelectPattern(LHS
, LHS2
, RHS2
))
860 if (Instruction
*R
= FoldSPFofSPF(cast
<Instruction
>(LHS
),SPF2
,LHS2
,RHS2
,
863 if (SelectPatternFlavor SPF2
= MatchSelectPattern(RHS
, LHS2
, RHS2
))
864 if (Instruction
*R
= FoldSPFofSPF(cast
<Instruction
>(RHS
),SPF2
,LHS2
,RHS2
,
871 // ABS(ABS(X)) -> ABS(X)
874 // See if we can fold the select into a phi node if the condition is a select.
875 if (isa
<PHINode
>(SI
.getCondition()))
876 // The true/false values have to be live in the PHI predecessor's blocks.
877 if (CanSelectOperandBeMappingIntoPredBlock(TrueVal
, SI
) &&
878 CanSelectOperandBeMappingIntoPredBlock(FalseVal
, SI
))
879 if (Instruction
*NV
= FoldOpIntoPhi(SI
))
882 if (SelectInst
*TrueSI
= dyn_cast
<SelectInst
>(TrueVal
)) {
883 if (TrueSI
->getCondition() == CondVal
) {
884 if (SI
.getTrueValue() == TrueSI
->getTrueValue())
886 SI
.setOperand(1, TrueSI
->getTrueValue());
890 if (SelectInst
*FalseSI
= dyn_cast
<SelectInst
>(FalseVal
)) {
891 if (FalseSI
->getCondition() == CondVal
) {
892 if (SI
.getFalseValue() == FalseSI
->getFalseValue())
894 SI
.setOperand(2, FalseSI
->getFalseValue());
899 if (BinaryOperator::isNot(CondVal
)) {
900 SI
.setOperand(0, BinaryOperator::getNotArgument(CondVal
));
901 SI
.setOperand(1, FalseVal
);
902 SI
.setOperand(2, TrueVal
);
906 if (VectorType
*VecTy
= dyn_cast
<VectorType
>(SI
.getType())) {
907 unsigned VWidth
= VecTy
->getNumElements();
908 APInt
UndefElts(VWidth
, 0);
909 APInt
AllOnesEltMask(APInt::getAllOnesValue(VWidth
));
910 if (Value
*V
= SimplifyDemandedVectorElts(&SI
, AllOnesEltMask
, UndefElts
)) {
912 return ReplaceInstUsesWith(SI
, V
);
916 if (ConstantVector
*CV
= dyn_cast
<ConstantVector
>(CondVal
)) {
917 // Form a shufflevector instruction.
918 SmallVector
<Constant
*, 8> Mask(VWidth
);
919 Type
*Int32Ty
= Type::getInt32Ty(CV
->getContext());
920 for (unsigned i
= 0; i
!= VWidth
; ++i
) {
921 Constant
*Elem
= cast
<Constant
>(CV
->getOperand(i
));
922 if (ConstantInt
*E
= dyn_cast
<ConstantInt
>(Elem
))
923 Mask
[i
] = ConstantInt::get(Int32Ty
, i
+ (E
->isZero() ? VWidth
: 0));
924 else if (isa
<UndefValue
>(Elem
))
925 Mask
[i
] = UndefValue::get(Int32Ty
);
929 Constant
*MaskVal
= ConstantVector::get(Mask
);
930 Value
*V
= Builder
->CreateShuffleVector(TrueVal
, FalseVal
, MaskVal
);
931 return ReplaceInstUsesWith(SI
, V
);
934 if (isa
<ConstantAggregateZero
>(CondVal
)) {
935 return ReplaceInstUsesWith(SI
, FalseVal
);