LLVM  8.0.0svn
InstCombineAndOrXor.cpp
Go to the documentation of this file.
1 //===- InstCombineAndOrXor.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 visitAnd, visitOr, and visitXor functions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
18 #include "llvm/IR/ConstantRange.h"
19 #include "llvm/IR/Intrinsics.h"
20 #include "llvm/IR/PatternMatch.h"
21 using namespace llvm;
22 using namespace PatternMatch;
23 
24 #define DEBUG_TYPE "instcombine"
25 
26 /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
27 /// a four bit mask.
28 static unsigned getFCmpCode(FCmpInst::Predicate CC) {
30  "Unexpected FCmp predicate!");
31  // Take advantage of the bit pattern of FCmpInst::Predicate here.
32  // U L G E
33  static_assert(FCmpInst::FCMP_FALSE == 0, ""); // 0 0 0 0
34  static_assert(FCmpInst::FCMP_OEQ == 1, ""); // 0 0 0 1
35  static_assert(FCmpInst::FCMP_OGT == 2, ""); // 0 0 1 0
36  static_assert(FCmpInst::FCMP_OGE == 3, ""); // 0 0 1 1
37  static_assert(FCmpInst::FCMP_OLT == 4, ""); // 0 1 0 0
38  static_assert(FCmpInst::FCMP_OLE == 5, ""); // 0 1 0 1
39  static_assert(FCmpInst::FCMP_ONE == 6, ""); // 0 1 1 0
40  static_assert(FCmpInst::FCMP_ORD == 7, ""); // 0 1 1 1
41  static_assert(FCmpInst::FCMP_UNO == 8, ""); // 1 0 0 0
42  static_assert(FCmpInst::FCMP_UEQ == 9, ""); // 1 0 0 1
43  static_assert(FCmpInst::FCMP_UGT == 10, ""); // 1 0 1 0
44  static_assert(FCmpInst::FCMP_UGE == 11, ""); // 1 0 1 1
45  static_assert(FCmpInst::FCMP_ULT == 12, ""); // 1 1 0 0
46  static_assert(FCmpInst::FCMP_ULE == 13, ""); // 1 1 0 1
47  static_assert(FCmpInst::FCMP_UNE == 14, ""); // 1 1 1 0
48  static_assert(FCmpInst::FCMP_TRUE == 15, ""); // 1 1 1 1
49  return CC;
50 }
51 
52 /// This is the complement of getICmpCode, which turns an opcode and two
53 /// operands into either a constant true or false, or a brand new ICmp
54 /// instruction. The sign is passed in to determine which kind of predicate to
55 /// use in the new icmp instruction.
56 static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
57  InstCombiner::BuilderTy &Builder) {
58  ICmpInst::Predicate NewPred;
59  if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred))
60  return NewConstant;
61  return Builder.CreateICmp(NewPred, LHS, RHS);
62 }
63 
64 /// This is the complement of getFCmpCode, which turns an opcode and two
65 /// operands into either a FCmp instruction, or a true/false constant.
66 static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
67  InstCombiner::BuilderTy &Builder) {
68  const auto Pred = static_cast<FCmpInst::Predicate>(Code);
69  assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
70  "Unexpected FCmp predicate!");
71  if (Pred == FCmpInst::FCMP_FALSE)
73  if (Pred == FCmpInst::FCMP_TRUE)
75  return Builder.CreateFCmp(Pred, LHS, RHS);
76 }
77 
78 /// Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or
79 /// BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
80 /// \param I Binary operator to transform.
81 /// \return Pointer to node that must replace the original binary operator, or
82 /// null pointer if no transformation was made.
84  InstCombiner::BuilderTy &Builder) {
85  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bswap simplifying");
86 
87  Value *OldLHS = I.getOperand(0);
88  Value *OldRHS = I.getOperand(1);
89 
90  Value *NewLHS;
91  if (!match(OldLHS, m_BSwap(m_Value(NewLHS))))
92  return nullptr;
93 
94  Value *NewRHS;
95  const APInt *C;
96 
97  if (match(OldRHS, m_BSwap(m_Value(NewRHS)))) {
98  // OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
99  if (!OldLHS->hasOneUse() && !OldRHS->hasOneUse())
100  return nullptr;
101  // NewRHS initialized by the matcher.
102  } else if (match(OldRHS, m_APInt(C))) {
103  // OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
104  if (!OldLHS->hasOneUse())
105  return nullptr;
106  NewRHS = ConstantInt::get(I.getType(), C->byteSwap());
107  } else
108  return nullptr;
109 
110  Value *BinOp = Builder.CreateBinOp(I.getOpcode(), NewLHS, NewRHS);
111  Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap,
112  I.getType());
113  return Builder.CreateCall(F, BinOp);
114 }
115 
116 /// This handles expressions of the form ((val OP C1) & C2). Where
117 /// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.
118 Instruction *InstCombiner::OptAndOp(BinaryOperator *Op,
119  ConstantInt *OpRHS,
120  ConstantInt *AndRHS,
121  BinaryOperator &TheAnd) {
122  Value *X = Op->getOperand(0);
123 
124  switch (Op->getOpcode()) {
125  default: break;
126  case Instruction::Add:
127  if (Op->hasOneUse()) {
128  // Adding a one to a single bit bit-field should be turned into an XOR
129  // of the bit. First thing to check is to see if this AND is with a
130  // single bit constant.
131  const APInt &AndRHSV = AndRHS->getValue();
132 
133  // If there is only one bit set.
134  if (AndRHSV.isPowerOf2()) {
135  // Ok, at this point, we know that we are masking the result of the
136  // ADD down to exactly one bit. If the constant we are adding has
137  // no bits set below this bit, then we can eliminate the ADD.
138  const APInt& AddRHS = OpRHS->getValue();
139 
140  // Check to see if any bits below the one bit set in AndRHSV are set.
141  if ((AddRHS & (AndRHSV - 1)).isNullValue()) {
142  // If not, the only thing that can effect the output of the AND is
143  // the bit specified by AndRHSV. If that bit is set, the effect of
144  // the XOR is to toggle the bit. If it is clear, then the ADD has
145  // no effect.
146  if ((AddRHS & AndRHSV).isNullValue()) { // Bit is not set, noop
147  TheAnd.setOperand(0, X);
148  return &TheAnd;
149  } else {
150  // Pull the XOR out of the AND.
151  Value *NewAnd = Builder.CreateAnd(X, AndRHS);
152  NewAnd->takeName(Op);
153  return BinaryOperator::CreateXor(NewAnd, AndRHS);
154  }
155  }
156  }
157  }
158  break;
159  }
160  return nullptr;
161 }
162 
163 /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
164 /// (V < Lo || V >= Hi). This method expects that Lo <= Hi. IsSigned indicates
165 /// whether to treat V, Lo, and Hi as signed or not.
166 Value *InstCombiner::insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
167  bool isSigned, bool Inside) {
168  assert((isSigned ? Lo.sle(Hi) : Lo.ule(Hi)) &&
169  "Lo is not <= Hi in range emission code!");
170 
171  Type *Ty = V->getType();
172  if (Lo == Hi)
173  return Inside ? ConstantInt::getFalse(Ty) : ConstantInt::getTrue(Ty);
174 
175  // V >= Min && V < Hi --> V < Hi
176  // V < Min || V >= Hi --> V >= Hi
178  if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
179  Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
180  return Builder.CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
181  }
182 
183  // V >= Lo && V < Hi --> V - Lo u< Hi - Lo
184  // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo
185  Value *VMinusLo =
186  Builder.CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
187  Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
188  return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo);
189 }
190 
191 /// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns
192 /// that can be simplified.
193 /// One of A and B is considered the mask. The other is the value. This is
194 /// described as the "AMask" or "BMask" part of the enum. If the enum contains
195 /// only "Mask", then both A and B can be considered masks. If A is the mask,
196 /// then it was proven that (A & C) == C. This is trivial if C == A or C == 0.
197 /// If both A and C are constants, this proof is also easy.
198 /// For the following explanations, we assume that A is the mask.
199 ///
200 /// "AllOnes" declares that the comparison is true only if (A & B) == A or all
201 /// bits of A are set in B.
202 /// Example: (icmp eq (A & 3), 3) -> AMask_AllOnes
203 ///
204 /// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all
205 /// bits of A are cleared in B.
206 /// Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes
207 ///
208 /// "Mixed" declares that (A & B) == C and C might or might not contain any
209 /// number of one bits and zero bits.
210 /// Example: (icmp eq (A & 3), 1) -> AMask_Mixed
211 ///
212 /// "Not" means that in above descriptions "==" should be replaced by "!=".
213 /// Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes
214 ///
215 /// If the mask A contains a single bit, then the following is equivalent:
216 /// (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
217 /// (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
227  BMask_Mixed = 256,
229 };
230 
231 /// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C)
232 /// satisfies.
233 static unsigned getMaskedICmpType(Value *A, Value *B, Value *C,
234  ICmpInst::Predicate Pred) {
235  ConstantInt *ACst = dyn_cast<ConstantInt>(A);
236  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
237  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
238  bool IsEq = (Pred == ICmpInst::ICMP_EQ);
239  bool IsAPow2 = (ACst && !ACst->isZero() && ACst->getValue().isPowerOf2());
240  bool IsBPow2 = (BCst && !BCst->isZero() && BCst->getValue().isPowerOf2());
241  unsigned MaskVal = 0;
242  if (CCst && CCst->isZero()) {
243  // if C is zero, then both A and B qualify as mask
244  MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed)
246  if (IsAPow2)
247  MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed)
248  : (AMask_AllOnes | AMask_Mixed));
249  if (IsBPow2)
250  MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed)
251  : (BMask_AllOnes | BMask_Mixed));
252  return MaskVal;
253  }
254 
255  if (A == C) {
256  MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed)
258  if (IsAPow2)
259  MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed)
260  : (Mask_AllZeros | AMask_Mixed));
261  } else if (ACst && CCst && ConstantExpr::getAnd(ACst, CCst) == CCst) {
262  MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed);
263  }
264 
265  if (B == C) {
266  MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed)
268  if (IsBPow2)
269  MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed)
270  : (Mask_AllZeros | BMask_Mixed));
271  } else if (BCst && CCst && ConstantExpr::getAnd(BCst, CCst) == CCst) {
272  MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed);
273  }
274 
275  return MaskVal;
276 }
277 
278 /// Convert an analysis of a masked ICmp into its equivalent if all boolean
279 /// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
280 /// is adjacent to the corresponding normal flag (recording ==), this just
281 /// involves swapping those bits over.
282 static unsigned conjugateICmpMask(unsigned Mask) {
283  unsigned NewMask;
284  NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros |
286  << 1;
287 
288  NewMask |= (Mask & (AMask_NotAllOnes | BMask_NotAllOnes | Mask_NotAllZeros |
290  >> 1;
291 
292  return NewMask;
293 }
294 
295 // Adapts the external decomposeBitTestICmp for local use.
296 static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred,
297  Value *&X, Value *&Y, Value *&Z) {
298  APInt Mask;
299  if (!llvm::decomposeBitTestICmp(LHS, RHS, Pred, X, Mask))
300  return false;
301 
302  Y = ConstantInt::get(X->getType(), Mask);
303  Z = ConstantInt::get(X->getType(), 0);
304  return true;
305 }
306 
307 /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
308 /// Return the pattern classes (from MaskedICmpType) for the left hand side and
309 /// the right hand side as a pair.
310 /// LHS and RHS are the left hand side and the right hand side ICmps and PredL
311 /// and PredR are their predicates, respectively.
312 static
315  Value *&D, Value *&E, ICmpInst *LHS,
316  ICmpInst *RHS,
317  ICmpInst::Predicate &PredL,
318  ICmpInst::Predicate &PredR) {
319  // vectors are not (yet?) supported. Don't support pointers either.
320  if (!LHS->getOperand(0)->getType()->isIntegerTy() ||
321  !RHS->getOperand(0)->getType()->isIntegerTy())
322  return None;
323 
324  // Here comes the tricky part:
325  // LHS might be of the form L11 & L12 == X, X == L21 & L22,
326  // and L11 & L12 == L21 & L22. The same goes for RHS.
327  // Now we must find those components L** and R**, that are equal, so
328  // that we can extract the parameters A, B, C, D, and E for the canonical
329  // above.
330  Value *L1 = LHS->getOperand(0);
331  Value *L2 = LHS->getOperand(1);
332  Value *L11, *L12, *L21, *L22;
333  // Check whether the icmp can be decomposed into a bit test.
334  if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) {
335  L21 = L22 = L1 = nullptr;
336  } else {
337  // Look for ANDs in the LHS icmp.
338  if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
339  // Any icmp can be viewed as being trivially masked; if it allows us to
340  // remove one, it's worth it.
341  L11 = L1;
342  L12 = Constant::getAllOnesValue(L1->getType());
343  }
344 
345  if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
346  L21 = L2;
347  L22 = Constant::getAllOnesValue(L2->getType());
348  }
349  }
350 
351  // Bail if LHS was a icmp that can't be decomposed into an equality.
352  if (!ICmpInst::isEquality(PredL))
353  return None;
354 
355  Value *R1 = RHS->getOperand(0);
356  Value *R2 = RHS->getOperand(1);
357  Value *R11, *R12;
358  bool Ok = false;
359  if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) {
360  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
361  A = R11;
362  D = R12;
363  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
364  A = R12;
365  D = R11;
366  } else {
367  return None;
368  }
369  E = R2;
370  R1 = nullptr;
371  Ok = true;
372  } else {
373  if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
374  // As before, model no mask as a trivial mask if it'll let us do an
375  // optimization.
376  R11 = R1;
377  R12 = Constant::getAllOnesValue(R1->getType());
378  }
379 
380  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
381  A = R11;
382  D = R12;
383  E = R2;
384  Ok = true;
385  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
386  A = R12;
387  D = R11;
388  E = R2;
389  Ok = true;
390  }
391  }
392 
393  // Bail if RHS was a icmp that can't be decomposed into an equality.
394  if (!ICmpInst::isEquality(PredR))
395  return None;
396 
397  // Look for ANDs on the right side of the RHS icmp.
398  if (!Ok) {
399  if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
400  R11 = R2;
401  R12 = Constant::getAllOnesValue(R2->getType());
402  }
403 
404  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
405  A = R11;
406  D = R12;
407  E = R1;
408  Ok = true;
409  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
410  A = R12;
411  D = R11;
412  E = R1;
413  Ok = true;
414  } else {
415  return None;
416  }
417  }
418  if (!Ok)
419  return None;
420 
421  if (L11 == A) {
422  B = L12;
423  C = L2;
424  } else if (L12 == A) {
425  B = L11;
426  C = L2;
427  } else if (L21 == A) {
428  B = L22;
429  C = L1;
430  } else if (L22 == A) {
431  B = L21;
432  C = L1;
433  }
434 
435  unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
436  unsigned RightType = getMaskedICmpType(A, D, E, PredR);
437  return Optional<std::pair<unsigned, unsigned>>(std::make_pair(LeftType, RightType));
438 }
439 
440 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single
441 /// (icmp(A & X) ==/!= Y), where the left-hand side is of type Mask_NotAllZeros
442 /// and the right hand side is of type BMask_Mixed. For example,
443 /// (icmp (A & 12) != 0) & (icmp (A & 15) == 8) -> (icmp (A & 15) == 8).
445  ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
446  Value *A, Value *B, Value *C, Value *D, Value *E,
449  // We are given the canonical form:
450  // (icmp ne (A & B), 0) & (icmp eq (A & D), E).
451  // where D & E == E.
452  //
453  // If IsAnd is false, we get it in negated form:
454  // (icmp eq (A & B), 0) | (icmp ne (A & D), E) ->
455  // !((icmp ne (A & B), 0) & (icmp eq (A & D), E)).
456  //
457  // We currently handle the case of B, C, D, E are constant.
458  //
459  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
460  if (!BCst)
461  return nullptr;
462  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
463  if (!CCst)
464  return nullptr;
465  ConstantInt *DCst = dyn_cast<ConstantInt>(D);
466  if (!DCst)
467  return nullptr;
468  ConstantInt *ECst = dyn_cast<ConstantInt>(E);
469  if (!ECst)
470  return nullptr;
471 
473 
474  // Update E to the canonical form when D is a power of two and RHS is
475  // canonicalized as,
476  // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or
477  // (icmp ne (A & D), D) -> (icmp eq (A & D), 0).
478  if (PredR != NewCC)
479  ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
480 
481  // If B or D is zero, skip because if LHS or RHS can be trivially folded by
482  // other folding rules and this pattern won't apply any more.
483  if (BCst->getValue() == 0 || DCst->getValue() == 0)
484  return nullptr;
485 
486  // If B and D don't intersect, ie. (B & D) == 0, no folding because we can't
487  // deduce anything from it.
488  // For example,
489  // (icmp ne (A & 12), 0) & (icmp eq (A & 3), 1) -> no folding.
490  if ((BCst->getValue() & DCst->getValue()) == 0)
491  return nullptr;
492 
493  // If the following two conditions are met:
494  //
495  // 1. mask B covers only a single bit that's not covered by mask D, that is,
496  // (B & (B ^ D)) is a power of 2 (in other words, B minus the intersection of
497  // B and D has only one bit set) and,
498  //
499  // 2. RHS (and E) indicates that the rest of B's bits are zero (in other
500  // words, the intersection of B and D is zero), that is, ((B & D) & E) == 0
501  //
502  // then that single bit in B must be one and thus the whole expression can be
503  // folded to
504  // (A & (B | D)) == (B & (B ^ D)) | E.
505  //
506  // For example,
507  // (icmp ne (A & 12), 0) & (icmp eq (A & 7), 1) -> (icmp eq (A & 15), 9)
508  // (icmp ne (A & 15), 0) & (icmp eq (A & 7), 0) -> (icmp eq (A & 15), 8)
509  if ((((BCst->getValue() & DCst->getValue()) & ECst->getValue()) == 0) &&
510  (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())).isPowerOf2()) {
511  APInt BorD = BCst->getValue() | DCst->getValue();
512  APInt BandBxorDorE = (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())) |
513  ECst->getValue();
514  Value *NewMask = ConstantInt::get(BCst->getType(), BorD);
515  Value *NewMaskedValue = ConstantInt::get(BCst->getType(), BandBxorDorE);
516  Value *NewAnd = Builder.CreateAnd(A, NewMask);
517  return Builder.CreateICmp(NewCC, NewAnd, NewMaskedValue);
518  }
519 
520  auto IsSubSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) {
521  return (C1->getValue() & C2->getValue()) == C1->getValue();
522  };
523  auto IsSuperSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) {
524  return (C1->getValue() & C2->getValue()) == C2->getValue();
525  };
526 
527  // In the following, we consider only the cases where B is a superset of D, B
528  // is a subset of D, or B == D because otherwise there's at least one bit
529  // covered by B but not D, in which case we can't deduce much from it, so
530  // no folding (aside from the single must-be-one bit case right above.)
531  // For example,
532  // (icmp ne (A & 14), 0) & (icmp eq (A & 3), 1) -> no folding.
533  if (!IsSubSetOrEqual(BCst, DCst) && !IsSuperSetOrEqual(BCst, DCst))
534  return nullptr;
535 
536  // At this point, either B is a superset of D, B is a subset of D or B == D.
537 
538  // If E is zero, if B is a subset of (or equal to) D, LHS and RHS contradict
539  // and the whole expression becomes false (or true if negated), otherwise, no
540  // folding.
541  // For example,
542  // (icmp ne (A & 3), 0) & (icmp eq (A & 7), 0) -> false.
543  // (icmp ne (A & 15), 0) & (icmp eq (A & 3), 0) -> no folding.
544  if (ECst->isZero()) {
545  if (IsSubSetOrEqual(BCst, DCst))
546  return ConstantInt::get(LHS->getType(), !IsAnd);
547  return nullptr;
548  }
549 
550  // At this point, B, D, E aren't zero and (B & D) == B, (B & D) == D or B ==
551  // D. If B is a superset of (or equal to) D, since E is not zero, LHS is
552  // subsumed by RHS (RHS implies LHS.) So the whole expression becomes
553  // RHS. For example,
554  // (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
555  // (icmp ne (A & 15), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
556  if (IsSuperSetOrEqual(BCst, DCst))
557  return RHS;
558  // Otherwise, B is a subset of D. If B and E have a common bit set,
559  // ie. (B & E) != 0, then LHS is subsumed by RHS. For example.
560  // (icmp ne (A & 12), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
561  assert(IsSubSetOrEqual(BCst, DCst) && "Precondition due to above code");
562  if ((BCst->getValue() & ECst->getValue()) != 0)
563  return RHS;
564  // Otherwise, LHS and RHS contradict and the whole expression becomes false
565  // (or true if negated.) For example,
566  // (icmp ne (A & 7), 0) & (icmp eq (A & 15), 8) -> false.
567  // (icmp ne (A & 6), 0) & (icmp eq (A & 15), 8) -> false.
568  return ConstantInt::get(LHS->getType(), !IsAnd);
569 }
570 
571 /// Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single
572 /// (icmp(A & X) ==/!= Y), where the left-hand side and the right hand side
573 /// aren't of the common mask pattern type.
575  ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
576  Value *A, Value *B, Value *C, Value *D, Value *E,
578  unsigned LHSMask, unsigned RHSMask,
581  "Expected equality predicates for masked type of icmps.");
582  // Handle Mask_NotAllZeros-BMask_Mixed cases.
583  // (icmp ne/eq (A & B), C) &/| (icmp eq/ne (A & D), E), or
584  // (icmp eq/ne (A & B), C) &/| (icmp ne/eq (A & D), E)
585  // which gets swapped to
586  // (icmp ne/eq (A & D), E) &/| (icmp eq/ne (A & B), C).
587  if (!IsAnd) {
588  LHSMask = conjugateICmpMask(LHSMask);
589  RHSMask = conjugateICmpMask(RHSMask);
590  }
591  if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) {
593  LHS, RHS, IsAnd, A, B, C, D, E,
594  PredL, PredR, Builder)) {
595  return V;
596  }
597  } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) {
599  RHS, LHS, IsAnd, A, D, E, B, C,
600  PredR, PredL, Builder)) {
601  return V;
602  }
603  }
604  return nullptr;
605 }
606 
607 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
608 /// into a single (icmp(A & X) ==/!= Y).
609 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
611  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
612  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
614  getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
615  if (!MaskPair)
616  return nullptr;
618  "Expected equality predicates for masked type of icmps.");
619  unsigned LHSMask = MaskPair->first;
620  unsigned RHSMask = MaskPair->second;
621  unsigned Mask = LHSMask & RHSMask;
622  if (Mask == 0) {
623  // Even if the two sides don't share a common pattern, check if folding can
624  // still happen.
626  LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
627  Builder))
628  return V;
629  return nullptr;
630  }
631 
632  // In full generality:
633  // (icmp (A & B) Op C) | (icmp (A & D) Op E)
634  // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
635  //
636  // If the latter can be converted into (icmp (A & X) Op Y) then the former is
637  // equivalent to (icmp (A & X) !Op Y).
638  //
639  // Therefore, we can pretend for the rest of this function that we're dealing
640  // with the conjunction, provided we flip the sense of any comparisons (both
641  // input and output).
642 
643  // In most cases we're going to produce an EQ for the "&&" case.
645  if (!IsAnd) {
646  // Convert the masking analysis into its equivalent with negated
647  // comparisons.
648  Mask = conjugateICmpMask(Mask);
649  }
650 
651  if (Mask & Mask_AllZeros) {
652  // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
653  // -> (icmp eq (A & (B|D)), 0)
654  Value *NewOr = Builder.CreateOr(B, D);
655  Value *NewAnd = Builder.CreateAnd(A, NewOr);
656  // We can't use C as zero because we might actually handle
657  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
658  // with B and D, having a single bit set.
659  Value *Zero = Constant::getNullValue(A->getType());
660  return Builder.CreateICmp(NewCC, NewAnd, Zero);
661  }
662  if (Mask & BMask_AllOnes) {
663  // (icmp eq (A & B), B) & (icmp eq (A & D), D)
664  // -> (icmp eq (A & (B|D)), (B|D))
665  Value *NewOr = Builder.CreateOr(B, D);
666  Value *NewAnd = Builder.CreateAnd(A, NewOr);
667  return Builder.CreateICmp(NewCC, NewAnd, NewOr);
668  }
669  if (Mask & AMask_AllOnes) {
670  // (icmp eq (A & B), A) & (icmp eq (A & D), A)
671  // -> (icmp eq (A & (B&D)), A)
672  Value *NewAnd1 = Builder.CreateAnd(B, D);
673  Value *NewAnd2 = Builder.CreateAnd(A, NewAnd1);
674  return Builder.CreateICmp(NewCC, NewAnd2, A);
675  }
676 
677  // Remaining cases assume at least that B and D are constant, and depend on
678  // their actual values. This isn't strictly necessary, just a "handle the
679  // easy cases for now" decision.
680  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
681  if (!BCst)
682  return nullptr;
683  ConstantInt *DCst = dyn_cast<ConstantInt>(D);
684  if (!DCst)
685  return nullptr;
686 
687  if (Mask & (Mask_NotAllZeros | BMask_NotAllOnes)) {
688  // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
689  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
690  // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
691  // Only valid if one of the masks is a superset of the other (check "B&D" is
692  // the same as either B or D).
693  APInt NewMask = BCst->getValue() & DCst->getValue();
694 
695  if (NewMask == BCst->getValue())
696  return LHS;
697  else if (NewMask == DCst->getValue())
698  return RHS;
699  }
700 
701  if (Mask & AMask_NotAllOnes) {
702  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
703  // -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
704  // Only valid if one of the masks is a superset of the other (check "B|D" is
705  // the same as either B or D).
706  APInt NewMask = BCst->getValue() | DCst->getValue();
707 
708  if (NewMask == BCst->getValue())
709  return LHS;
710  else if (NewMask == DCst->getValue())
711  return RHS;
712  }
713 
714  if (Mask & BMask_Mixed) {
715  // (icmp eq (A & B), C) & (icmp eq (A & D), E)
716  // We already know that B & C == C && D & E == E.
717  // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
718  // C and E, which are shared by both the mask B and the mask D, don't
719  // contradict, then we can transform to
720  // -> (icmp eq (A & (B|D)), (C|E))
721  // Currently, we only handle the case of B, C, D, and E being constant.
722  // We can't simply use C and E because we might actually handle
723  // (icmp ne (A & B), B) & (icmp eq (A & D), D)
724  // with B and D, having a single bit set.
725  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
726  if (!CCst)
727  return nullptr;
728  ConstantInt *ECst = dyn_cast<ConstantInt>(E);
729  if (!ECst)
730  return nullptr;
731  if (PredL != NewCC)
732  CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst));
733  if (PredR != NewCC)
734  ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
735 
736  // If there is a conflict, we should actually return a false for the
737  // whole construct.
738  if (((BCst->getValue() & DCst->getValue()) &
739  (CCst->getValue() ^ ECst->getValue())).getBoolValue())
740  return ConstantInt::get(LHS->getType(), !IsAnd);
741 
742  Value *NewOr1 = Builder.CreateOr(B, D);
743  Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
744  Value *NewAnd = Builder.CreateAnd(A, NewOr1);
745  return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
746  }
747 
748  return nullptr;
749 }
750 
751 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
752 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
753 /// If \p Inverted is true then the check is for the inverted range, e.g.
754 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
756  bool Inverted) {
757  // Check the lower range comparison, e.g. x >= 0
758  // InstCombine already ensured that if there is a constant it's on the RHS.
759  ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
760  if (!RangeStart)
761  return nullptr;
762 
763  ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
764  Cmp0->getPredicate());
765 
766  // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
767  if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
768  (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
769  return nullptr;
770 
771  ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
772  Cmp1->getPredicate());
773 
774  Value *Input = Cmp0->getOperand(0);
775  Value *RangeEnd;
776  if (Cmp1->getOperand(0) == Input) {
777  // For the upper range compare we have: icmp x, n
778  RangeEnd = Cmp1->getOperand(1);
779  } else if (Cmp1->getOperand(1) == Input) {
780  // For the upper range compare we have: icmp n, x
781  RangeEnd = Cmp1->getOperand(0);
782  Pred1 = ICmpInst::getSwappedPredicate(Pred1);
783  } else {
784  return nullptr;
785  }
786 
787  // Check the upper range comparison, e.g. x < n
788  ICmpInst::Predicate NewPred;
789  switch (Pred1) {
790  case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
791  case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
792  default: return nullptr;
793  }
794 
795  // This simplification is only valid if the upper range is not negative.
796  KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1);
797  if (!Known.isNonNegative())
798  return nullptr;
799 
800  if (Inverted)
801  NewPred = ICmpInst::getInversePredicate(NewPred);
802 
803  return Builder.CreateICmp(NewPred, Input, RangeEnd);
804 }
805 
806 static Value *
808  bool JoinedByAnd,
809  InstCombiner::BuilderTy &Builder) {
810  Value *X = LHS->getOperand(0);
811  if (X != RHS->getOperand(0))
812  return nullptr;
813 
814  const APInt *C1, *C2;
815  if (!match(LHS->getOperand(1), m_APInt(C1)) ||
816  !match(RHS->getOperand(1), m_APInt(C2)))
817  return nullptr;
818 
819  // We only handle (X != C1 && X != C2) and (X == C1 || X == C2).
820  ICmpInst::Predicate Pred = LHS->getPredicate();
821  if (Pred != RHS->getPredicate())
822  return nullptr;
823  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
824  return nullptr;
825  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
826  return nullptr;
827 
828  // The larger unsigned constant goes on the right.
829  if (C1->ugt(*C2))
830  std::swap(C1, C2);
831 
832  APInt Xor = *C1 ^ *C2;
833  if (Xor.isPowerOf2()) {
834  // If LHSC and RHSC differ by only one bit, then set that bit in X and
835  // compare against the larger constant:
836  // (X == C1 || X == C2) --> (X | (C1 ^ C2)) == C2
837  // (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2
838  // We choose an 'or' with a Pow2 constant rather than the inverse mask with
839  // 'and' because that may lead to smaller codegen from a smaller constant.
840  Value *Or = Builder.CreateOr(X, ConstantInt::get(X->getType(), Xor));
841  return Builder.CreateICmp(Pred, Or, ConstantInt::get(X->getType(), *C2));
842  }
843 
844  // Special case: get the ordering right when the values wrap around zero.
845  // Ie, we assumed the constants were unsigned when swapping earlier.
846  if (C1->isNullValue() && C2->isAllOnesValue())
847  std::swap(C1, C2);
848 
849  if (*C1 == *C2 - 1) {
850  // (X == 13 || X == 14) --> X - 13 <=u 1
851  // (X != 13 && X != 14) --> X - 13 >u 1
852  // An 'add' is the canonical IR form, so favor that over a 'sub'.
853  Value *Add = Builder.CreateAdd(X, ConstantInt::get(X->getType(), -(*C1)));
854  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
855  return Builder.CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
856  }
857 
858  return nullptr;
859 }
860 
861 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
862 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
863 Value *InstCombiner::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
864  bool JoinedByAnd,
865  Instruction &CxtI) {
866  ICmpInst::Predicate Pred = LHS->getPredicate();
867  if (Pred != RHS->getPredicate())
868  return nullptr;
869  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
870  return nullptr;
871  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
872  return nullptr;
873 
874  // TODO support vector splats
875  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
876  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
877  if (!LHSC || !RHSC || !LHSC->isZero() || !RHSC->isZero())
878  return nullptr;
879 
880  Value *A, *B, *C, *D;
881  if (match(LHS->getOperand(0), m_And(m_Value(A), m_Value(B))) &&
882  match(RHS->getOperand(0), m_And(m_Value(C), m_Value(D)))) {
883  if (A == D || B == D)
884  std::swap(C, D);
885  if (B == C)
886  std::swap(A, B);
887 
888  if (A == C &&
889  isKnownToBeAPowerOfTwo(B, false, 0, &CxtI) &&
890  isKnownToBeAPowerOfTwo(D, false, 0, &CxtI)) {
891  Value *Mask = Builder.CreateOr(B, D);
892  Value *Masked = Builder.CreateAnd(A, Mask);
893  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
894  return Builder.CreateICmp(NewPred, Masked, Mask);
895  }
896  }
897 
898  return nullptr;
899 }
900 
901 /// General pattern:
902 /// X & Y
903 ///
904 /// Where Y is checking that all the high bits (covered by a mask 4294967168)
905 /// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0
906 /// Pattern can be one of:
907 /// %t = add i32 %arg, 128
908 /// %r = icmp ult i32 %t, 256
909 /// Or
910 /// %t0 = shl i32 %arg, 24
911 /// %t1 = ashr i32 %t0, 24
912 /// %r = icmp eq i32 %t1, %arg
913 /// Or
914 /// %t0 = trunc i32 %arg to i8
915 /// %t1 = sext i8 %t0 to i32
916 /// %r = icmp eq i32 %t1, %arg
917 /// This pattern is a signed truncation check.
918 ///
919 /// And X is checking that some bit in that same mask is zero.
920 /// I.e. can be one of:
921 /// %r = icmp sgt i32 %arg, -1
922 /// Or
923 /// %t = and i32 %arg, 2147483648
924 /// %r = icmp eq i32 %t, 0
925 ///
926 /// Since we are checking that all the bits in that mask are the same,
927 /// and a particular bit is zero, what we are really checking is that all the
928 /// masked bits are zero.
929 /// So this should be transformed to:
930 /// %r = icmp ult i32 %arg, 128
932  Instruction &CxtI,
933  InstCombiner::BuilderTy &Builder) {
934  assert(CxtI.getOpcode() == Instruction::And);
935 
936  // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two)
937  auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X,
938  APInt &SignBitMask) -> bool {
939  CmpInst::Predicate Pred;
940  const APInt *I01, *I1; // powers of two; I1 == I01 << 1
941  if (!(match(ICmp,
942  m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) &&
943  Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1))
944  return false;
945  // Which bit is the new sign bit as per the 'signed truncation' pattern?
946  SignBitMask = *I01;
947  return true;
948  };
949 
950  // One icmp needs to be 'signed truncation check'.
951  // We need to match this first, else we will mismatch commutative cases.
952  Value *X1;
953  APInt HighestBit;
954  ICmpInst *OtherICmp;
955  if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit))
956  OtherICmp = ICmp0;
957  else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit))
958  OtherICmp = ICmp1;
959  else
960  return nullptr;
961 
962  assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)");
963 
964  // Try to match/decompose into: icmp eq (X & Mask), 0
965  auto tryToDecompose = [](ICmpInst *ICmp, Value *&X,
966  APInt &UnsetBitsMask) -> bool {
967  CmpInst::Predicate Pred = ICmp->getPredicate();
968  // Can it be decomposed into icmp eq (X & Mask), 0 ?
969  if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1),
970  Pred, X, UnsetBitsMask,
971  /*LookThruTrunc=*/false) &&
972  Pred == ICmpInst::ICMP_EQ)
973  return true;
974  // Is it icmp eq (X & Mask), 0 already?
975  const APInt *Mask;
976  if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) &&
977  Pred == ICmpInst::ICMP_EQ) {
978  UnsetBitsMask = *Mask;
979  return true;
980  }
981  return false;
982  };
983 
984  // And the other icmp needs to be decomposable into a bit test.
985  Value *X0;
986  APInt UnsetBitsMask;
987  if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask))
988  return nullptr;
989 
990  assert(!UnsetBitsMask.isNullValue() && "empty mask makes no sense.");
991 
992  // Are they working on the same value?
993  Value *X;
994  if (X1 == X0) {
995  // Ok as is.
996  X = X1;
997  } else if (match(X0, m_Trunc(m_Specific(X1)))) {
998  UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits());
999  X = X1;
1000  } else
1001  return nullptr;
1002 
1003  // So which bits should be uniform as per the 'signed truncation check'?
1004  // (all the bits starting with (i.e. including) HighestBit)
1005  APInt SignBitsMask = ~(HighestBit - 1U);
1006 
1007  // UnsetBitsMask must have some common bits with SignBitsMask,
1008  if (!UnsetBitsMask.intersects(SignBitsMask))
1009  return nullptr;
1010 
1011  // Does UnsetBitsMask contain any bits outside of SignBitsMask?
1012  if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) {
1013  APInt OtherHighestBit = (~UnsetBitsMask) + 1U;
1014  if (!OtherHighestBit.isPowerOf2())
1015  return nullptr;
1016  HighestBit = APIntOps::umin(HighestBit, OtherHighestBit);
1017  }
1018  // Else, if it does not, then all is ok as-is.
1019 
1020  // %r = icmp ult %X, SignBit
1021  return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit),
1022  CxtI.getName() + ".simplified");
1023 }
1024 
1025 /// Fold (icmp)&(icmp) if possible.
1026 Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1027  Instruction &CxtI) {
1028  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
1029  // if K1 and K2 are a one-bit mask.
1030  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, true, CxtI))
1031  return V;
1032 
1033  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1034 
1035  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
1036  if (PredicatesFoldable(PredL, PredR)) {
1037  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1038  LHS->getOperand(1) == RHS->getOperand(0))
1039  LHS->swapOperands();
1040  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1041  LHS->getOperand(1) == RHS->getOperand(1)) {
1042  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1043  unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
1044  bool isSigned = LHS->isSigned() || RHS->isSigned();
1045  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
1046  }
1047  }
1048 
1049  // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
1050  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
1051  return V;
1052 
1053  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
1054  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
1055  return V;
1056 
1057  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
1058  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
1059  return V;
1060 
1061  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
1062  return V;
1063 
1064  if (Value *V = foldSignedTruncationCheck(LHS, RHS, CxtI, Builder))
1065  return V;
1066 
1067  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
1068  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1069  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
1070  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
1071  if (!LHSC || !RHSC)
1072  return nullptr;
1073 
1074  if (LHSC == RHSC && PredL == PredR) {
1075  // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
1076  // where C is a power of 2 or
1077  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
1078  if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
1079  (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
1080  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
1081  return Builder.CreateICmp(PredL, NewOr, LHSC);
1082  }
1083  }
1084 
1085  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
1086  // where CMAX is the all ones value for the truncated type,
1087  // iff the lower bits of C2 and CA are zero.
1088  if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
1089  RHS->hasOneUse()) {
1090  Value *V;
1091  ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
1092 
1093  // (trunc x) == C1 & (and x, CA) == C2
1094  // (and x, CA) == C2 & (trunc x) == C1
1095  if (match(RHS0, m_Trunc(m_Value(V))) &&
1096  match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1097  SmallC = RHSC;
1098  BigC = LHSC;
1099  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
1100  match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1101  SmallC = LHSC;
1102  BigC = RHSC;
1103  }
1104 
1105  if (SmallC && BigC) {
1106  unsigned BigBitSize = BigC->getType()->getBitWidth();
1107  unsigned SmallBitSize = SmallC->getType()->getBitWidth();
1108 
1109  // Check that the low bits are zero.
1110  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
1111  if ((Low & AndC->getValue()).isNullValue() &&
1112  (Low & BigC->getValue()).isNullValue()) {
1113  Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue());
1114  APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
1115  Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
1116  return Builder.CreateICmp(PredL, NewAnd, NewVal);
1117  }
1118  }
1119  }
1120 
1121  // From here on, we only handle:
1122  // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
1123  if (LHS0 != RHS0)
1124  return nullptr;
1125 
1126  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1127  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1128  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1129  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1130  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1131  return nullptr;
1132 
1133  // We can't fold (ugt x, C) & (sgt x, C2).
1134  if (!PredicatesFoldable(PredL, PredR))
1135  return nullptr;
1136 
1137  // Ensure that the larger constant is on the RHS.
1138  bool ShouldSwap;
1139  if (CmpInst::isSigned(PredL) ||
1140  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1141  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1142  else
1143  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1144 
1145  if (ShouldSwap) {
1146  std::swap(LHS, RHS);
1147  std::swap(LHSC, RHSC);
1148  std::swap(PredL, PredR);
1149  }
1150 
1151  // At this point, we know we have two icmp instructions
1152  // comparing a value against two constants and and'ing the result
1153  // together. Because of the above check, we know that we only have
1154  // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
1155  // (from the icmp folding check above), that the two constants
1156  // are not equal and that the larger constant is on the RHS
1157  assert(LHSC != RHSC && "Compares not folded above?");
1158 
1159  switch (PredL) {
1160  default:
1161  llvm_unreachable("Unknown integer condition code!");
1162  case ICmpInst::ICMP_NE:
1163  switch (PredR) {
1164  default:
1165  llvm_unreachable("Unknown integer condition code!");
1166  case ICmpInst::ICMP_ULT:
1167  if (LHSC == SubOne(RHSC)) // (X != 13 & X u< 14) -> X < 13
1168  return Builder.CreateICmpULT(LHS0, LHSC);
1169  if (LHSC->isZero()) // (X != 0 & X u< 14) -> X-1 u< 13
1170  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1171  false, true);
1172  break; // (X != 13 & X u< 15) -> no change
1173  case ICmpInst::ICMP_SLT:
1174  if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13
1175  return Builder.CreateICmpSLT(LHS0, LHSC);
1176  break; // (X != 13 & X s< 15) -> no change
1177  case ICmpInst::ICMP_NE:
1178  // Potential folds for this case should already be handled.
1179  break;
1180  }
1181  break;
1182  case ICmpInst::ICMP_UGT:
1183  switch (PredR) {
1184  default:
1185  llvm_unreachable("Unknown integer condition code!");
1186  case ICmpInst::ICMP_NE:
1187  if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14
1188  return Builder.CreateICmp(PredL, LHS0, RHSC);
1189  break; // (X u> 13 & X != 15) -> no change
1190  case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
1191  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1192  false, true);
1193  }
1194  break;
1195  case ICmpInst::ICMP_SGT:
1196  switch (PredR) {
1197  default:
1198  llvm_unreachable("Unknown integer condition code!");
1199  case ICmpInst::ICMP_NE:
1200  if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14
1201  return Builder.CreateICmp(PredL, LHS0, RHSC);
1202  break; // (X s> 13 & X != 15) -> no change
1203  case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
1204  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
1205  true);
1206  }
1207  break;
1208  }
1209 
1210  return nullptr;
1211 }
1212 
1213 Value *InstCombiner::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
1214  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1215  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1216  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1217 
1218  if (LHS0 == RHS1 && RHS0 == LHS1) {
1219  // Swap RHS operands to match LHS.
1220  PredR = FCmpInst::getSwappedPredicate(PredR);
1221  std::swap(RHS0, RHS1);
1222  }
1223 
1224  // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1225  // Suppose the relation between x and y is R, where R is one of
1226  // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1227  // testing the desired relations.
1228  //
1229  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1230  // bool(R & CC0) && bool(R & CC1)
1231  // = bool((R & CC0) & (R & CC1))
1232  // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1233  //
1234  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1235  // bool(R & CC0) || bool(R & CC1)
1236  // = bool((R & CC0) | (R & CC1))
1237  // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1238  if (LHS0 == RHS0 && LHS1 == RHS1) {
1239  unsigned FCmpCodeL = getFCmpCode(PredL);
1240  unsigned FCmpCodeR = getFCmpCode(PredR);
1241  unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1242  return getFCmpValue(NewPred, LHS0, LHS1, Builder);
1243  }
1244 
1245  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1246  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1247  if (LHS0->getType() != RHS0->getType())
1248  return nullptr;
1249 
1250  // FCmp canonicalization ensures that (fcmp ord/uno X, X) and
1251  // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0).
1252  if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP()))
1253  // Ignore the constants because they are obviously not NANs:
1254  // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y)
1255  // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y)
1256  return Builder.CreateFCmp(PredL, LHS0, RHS0);
1257  }
1258 
1259  return nullptr;
1260 }
1261 
1262 /// Match De Morgan's Laws:
1263 /// (~A & ~B) == (~(A | B))
1264 /// (~A | ~B) == (~(A & B))
1266  InstCombiner::BuilderTy &Builder) {
1267  auto Opcode = I.getOpcode();
1268  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1269  "Trying to match De Morgan's Laws with something other than and/or");
1270 
1271  // Flip the logic operation.
1272  Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1273 
1274  Value *A, *B;
1275  if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) &&
1276  match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) &&
1277  !IsFreeToInvert(A, A->hasOneUse()) &&
1278  !IsFreeToInvert(B, B->hasOneUse())) {
1279  Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan");
1280  return BinaryOperator::CreateNot(AndOr);
1281  }
1282 
1283  return nullptr;
1284 }
1285 
1286 bool InstCombiner::shouldOptimizeCast(CastInst *CI) {
1287  Value *CastSrc = CI->getOperand(0);
1288 
1289  // Noop casts and casts of constants should be eliminated trivially.
1290  if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1291  return false;
1292 
1293  // If this cast is paired with another cast that can be eliminated, we prefer
1294  // to have it eliminated.
1295  if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1296  if (isEliminableCastPair(PrecedingCI, CI))
1297  return false;
1298 
1299  return true;
1300 }
1301 
1302 /// Fold {and,or,xor} (cast X), C.
1304  InstCombiner::BuilderTy &Builder) {
1305  Constant *C = dyn_cast<Constant>(Logic.getOperand(1));
1306  if (!C)
1307  return nullptr;
1308 
1309  auto LogicOpc = Logic.getOpcode();
1310  Type *DestTy = Logic.getType();
1311  Type *SrcTy = Cast->getSrcTy();
1312 
1313  // Move the logic operation ahead of a zext or sext if the constant is
1314  // unchanged in the smaller source type. Performing the logic in a smaller
1315  // type may provide more information to later folds, and the smaller logic
1316  // instruction may be cheaper (particularly in the case of vectors).
1317  Value *X;
1318  if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1319  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1320  Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1321  if (ZextTruncC == C) {
1322  // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1323  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1324  return new ZExtInst(NewOp, DestTy);
1325  }
1326  }
1327 
1328  if (match(Cast, m_OneUse(m_SExt(m_Value(X))))) {
1329  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1330  Constant *SextTruncC = ConstantExpr::getSExt(TruncC, DestTy);
1331  if (SextTruncC == C) {
1332  // LogicOpc (sext X), C --> sext (LogicOpc X, C)
1333  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1334  return new SExtInst(NewOp, DestTy);
1335  }
1336  }
1337 
1338  return nullptr;
1339 }
1340 
1341 /// Fold {and,or,xor} (cast X), Y.
1342 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
1343  auto LogicOpc = I.getOpcode();
1344  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1345 
1346  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1347  CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1348  if (!Cast0)
1349  return nullptr;
1350 
1351  // This must be a cast from an integer or integer vector source type to allow
1352  // transformation of the logic operation to the source type.
1353  Type *DestTy = I.getType();
1354  Type *SrcTy = Cast0->getSrcTy();
1355  if (!SrcTy->isIntOrIntVectorTy())
1356  return nullptr;
1357 
1358  if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1359  return Ret;
1360 
1361  CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1362  if (!Cast1)
1363  return nullptr;
1364 
1365  // Both operands of the logic operation are casts. The casts must be of the
1366  // same type for reduction.
1367  auto CastOpcode = Cast0->getOpcode();
1368  if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
1369  return nullptr;
1370 
1371  Value *Cast0Src = Cast0->getOperand(0);
1372  Value *Cast1Src = Cast1->getOperand(0);
1373 
1374  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1375  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1376  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1377  I.getName());
1378  return CastInst::Create(CastOpcode, NewOp, DestTy);
1379  }
1380 
1381  // For now, only 'and'/'or' have optimizations after this.
1382  if (LogicOpc == Instruction::Xor)
1383  return nullptr;
1384 
1385  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1386  // cast is otherwise not optimizable. This happens for vector sexts.
1387  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1388  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1389  if (ICmp0 && ICmp1) {
1390  Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I)
1391  : foldOrOfICmps(ICmp0, ICmp1, I);
1392  if (Res)
1393  return CastInst::Create(CastOpcode, Res, DestTy);
1394  return nullptr;
1395  }
1396 
1397  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1398  // cast is otherwise not optimizable. This happens for vector sexts.
1399  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1400  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1401  if (FCmp0 && FCmp1)
1402  if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1403  return CastInst::Create(CastOpcode, R, DestTy);
1404 
1405  return nullptr;
1406 }
1407 
1409  InstCombiner::BuilderTy &Builder) {
1410  assert(I.getOpcode() == Instruction::And);
1411  Value *Op0 = I.getOperand(0);
1412  Value *Op1 = I.getOperand(1);
1413  Value *A, *B;
1414 
1415  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1416  // (A | B) & ~(A & B) --> A ^ B
1417  // (A | B) & ~(B & A) --> A ^ B
1418  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1419  m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
1420  return BinaryOperator::CreateXor(A, B);
1421 
1422  // (A | ~B) & (~A | B) --> ~(A ^ B)
1423  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1424  // (~B | A) & (~A | B) --> ~(A ^ B)
1425  // (~B | A) & (B | ~A) --> ~(A ^ B)
1426  if (Op0->hasOneUse() || Op1->hasOneUse())
1427  if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
1428  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
1429  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1430 
1431  return nullptr;
1432 }
1433 
1435  InstCombiner::BuilderTy &Builder) {
1436  assert(I.getOpcode() == Instruction::Or);
1437  Value *Op0 = I.getOperand(0);
1438  Value *Op1 = I.getOperand(1);
1439  Value *A, *B;
1440 
1441  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1442  // (A & B) | ~(A | B) --> ~(A ^ B)
1443  // (A & B) | ~(B | A) --> ~(A ^ B)
1444  if (Op0->hasOneUse() || Op1->hasOneUse())
1445  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1446  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1447  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1448 
1449  // (A & ~B) | (~A & B) --> A ^ B
1450  // (A & ~B) | (B & ~A) --> A ^ B
1451  // (~B & A) | (~A & B) --> A ^ B
1452  // (~B & A) | (B & ~A) --> A ^ B
1453  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1454  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1455  return BinaryOperator::CreateXor(A, B);
1456 
1457  return nullptr;
1458 }
1459 
1460 /// Return true if a constant shift amount is always less than the specified
1461 /// bit-width. If not, the shift could create poison in the narrower type.
1462 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1463  if (auto *ScalarC = dyn_cast<ConstantInt>(C))
1464  return ScalarC->getZExtValue() < BitWidth;
1465 
1466  if (C->getType()->isVectorTy()) {
1467  // Check each element of a constant vector.
1468  unsigned NumElts = C->getType()->getVectorNumElements();
1469  for (unsigned i = 0; i != NumElts; ++i) {
1470  Constant *Elt = C->getAggregateElement(i);
1471  if (!Elt)
1472  return false;
1473  if (isa<UndefValue>(Elt))
1474  continue;
1475  auto *CI = dyn_cast<ConstantInt>(Elt);
1476  if (!CI || CI->getZExtValue() >= BitWidth)
1477  return false;
1478  }
1479  return true;
1480  }
1481 
1482  // The constant is a constant expression or unknown.
1483  return false;
1484 }
1485 
1486 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1487 /// a common zext operand: and (binop (zext X), C), (zext X).
1488 Instruction *InstCombiner::narrowMaskedBinOp(BinaryOperator &And) {
1489  // This transform could also apply to {or, and, xor}, but there are better
1490  // folds for those cases, so we don't expect those patterns here. AShr is not
1491  // handled because it should always be transformed to LShr in this sequence.
1492  // The subtract transform is different because it has a constant on the left.
1493  // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1494  Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1495  Constant *C;
1496  if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1497  !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1498  !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1499  !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1500  !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1501  return nullptr;
1502 
1503  Value *X;
1504  if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1505  return nullptr;
1506 
1507  Type *Ty = And.getType();
1508  if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1509  return nullptr;
1510 
1511  // If we're narrowing a shift, the shift amount must be safe (less than the
1512  // width) in the narrower type. If the shift amount is greater, instsimplify
1513  // usually handles that case, but we can't guarantee/assert it.
1514  Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1515  if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1517  return nullptr;
1518 
1519  // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1520  // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1521  Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1522  Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1523  : Builder.CreateBinOp(Opc, X, NewC);
1524  return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1525 }
1526 
1527 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1528 // here. We should standardize that construct where it is needed or choose some
1529 // other way to ensure that commutated variants of patterns are not missed.
1531  if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1),
1532  SQ.getWithInstruction(&I)))
1533  return replaceInstUsesWith(I, V);
1534 
1535  if (SimplifyAssociativeOrCommutative(I))
1536  return &I;
1537 
1538  if (Instruction *X = foldShuffledBinop(I))
1539  return X;
1540 
1541  // See if we can simplify any instructions used by the instruction whose sole
1542  // purpose is to compute bits we don't care about.
1543  if (SimplifyDemandedInstructionBits(I))
1544  return &I;
1545 
1546  // Do this before using distributive laws to catch simple and/or/not patterns.
1547  if (Instruction *Xor = foldAndToXor(I, Builder))
1548  return Xor;
1549 
1550  // (A|B)&(A|C) -> A|(B&C) etc
1551  if (Value *V = SimplifyUsingDistributiveLaws(I))
1552  return replaceInstUsesWith(I, V);
1553 
1554  if (Value *V = SimplifyBSwap(I, Builder))
1555  return replaceInstUsesWith(I, V);
1556 
1557  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1558  const APInt *C;
1559  if (match(Op1, m_APInt(C))) {
1560  Value *X, *Y;
1561  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
1562  C->isOneValue()) {
1563  // (1 << X) & 1 --> zext(X == 0)
1564  // (1 >> X) & 1 --> zext(X == 0)
1565  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(I.getType(), 0));
1566  return new ZExtInst(IsZero, I.getType());
1567  }
1568 
1569  const APInt *XorC;
1570  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
1571  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1572  Constant *NewC = ConstantInt::get(I.getType(), *C & *XorC);
1573  Value *And = Builder.CreateAnd(X, Op1);
1574  And->takeName(Op0);
1575  return BinaryOperator::CreateXor(And, NewC);
1576  }
1577 
1578  const APInt *OrC;
1579  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
1580  // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
1581  // NOTE: This reduces the number of bits set in the & mask, which
1582  // can expose opportunities for store narrowing for scalars.
1583  // NOTE: SimplifyDemandedBits should have already removed bits from C1
1584  // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
1585  // above, but this feels safer.
1586  APInt Together = *C & *OrC;
1587  Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(),
1588  Together ^ *C));
1589  And->takeName(Op0);
1590  return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(),
1591  Together));
1592  }
1593 
1594  // If the mask is only needed on one incoming arm, push the 'and' op up.
1595  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
1596  match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
1597  APInt NotAndMask(~(*C));
1598  BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
1599  if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
1600  // Not masking anything out for the LHS, move mask to RHS.
1601  // and ({x}or X, Y), C --> {x}or X, (and Y, C)
1602  Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
1603  return BinaryOperator::Create(BinOp, X, NewRHS);
1604  }
1605  if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
1606  // Not masking anything out for the RHS, move mask to LHS.
1607  // and ({x}or X, Y), C --> {x}or (and X, C), Y
1608  Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
1609  return BinaryOperator::Create(BinOp, NewLHS, Y);
1610  }
1611  }
1612 
1613  }
1614 
1615  if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
1616  const APInt &AndRHSMask = AndRHS->getValue();
1617 
1618  // Optimize a variety of ((val OP C1) & C2) combinations...
1619  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1620  // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth
1621  // of X and OP behaves well when given trunc(C1) and X.
1622  switch (Op0I->getOpcode()) {
1623  default:
1624  break;
1625  case Instruction::Xor:
1626  case Instruction::Or:
1627  case Instruction::Mul:
1628  case Instruction::Add:
1629  case Instruction::Sub:
1630  Value *X;
1631  ConstantInt *C1;
1632  if (match(Op0I, m_c_BinOp(m_ZExt(m_Value(X)), m_ConstantInt(C1)))) {
1633  if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) {
1634  auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType());
1635  Value *BinOp;
1636  Value *Op0LHS = Op0I->getOperand(0);
1637  if (isa<ZExtInst>(Op0LHS))
1638  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), X, TruncC1);
1639  else
1640  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), TruncC1, X);
1641  auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType());
1642  auto *And = Builder.CreateAnd(BinOp, TruncC2);
1643  return new ZExtInst(And, I.getType());
1644  }
1645  }
1646  }
1647 
1648  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1649  if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1650  return Res;
1651  }
1652 
1653  // If this is an integer truncation, and if the source is an 'and' with
1654  // immediate, transform it. This frequently occurs for bitfield accesses.
1655  {
1656  Value *X = nullptr; ConstantInt *YC = nullptr;
1657  if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) {
1658  // Change: and (trunc (and X, YC) to T), C2
1659  // into : and (trunc X to T), trunc(YC) & C2
1660  // This will fold the two constants together, which may allow
1661  // other simplifications.
1662  Value *NewCast = Builder.CreateTrunc(X, I.getType(), "and.shrunk");
1663  Constant *C3 = ConstantExpr::getTrunc(YC, I.getType());
1664  C3 = ConstantExpr::getAnd(C3, AndRHS);
1665  return BinaryOperator::CreateAnd(NewCast, C3);
1666  }
1667  }
1668  }
1669 
1670  if (Instruction *Z = narrowMaskedBinOp(I))
1671  return Z;
1672 
1673  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
1674  return FoldedLogic;
1675 
1676  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1677  return DeMorgan;
1678 
1679  {
1680  Value *A, *B, *C;
1681  // A & (A ^ B) --> A & ~B
1682  if (match(Op1, m_OneUse(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1683  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(B));
1684  // (A ^ B) & A --> A & ~B
1685  if (match(Op0, m_OneUse(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1686  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(B));
1687 
1688  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1689  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1690  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1691  if (Op1->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1692  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1693 
1694  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1695  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1696  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1697  if (Op0->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1698  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1699 
1700  // (A | B) & ((~A) ^ B) -> (A & B)
1701  // (A | B) & (B ^ (~A)) -> (A & B)
1702  // (B | A) & ((~A) ^ B) -> (A & B)
1703  // (B | A) & (B ^ (~A)) -> (A & B)
1704  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1705  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1706  return BinaryOperator::CreateAnd(A, B);
1707 
1708  // ((~A) ^ B) & (A | B) -> (A & B)
1709  // ((~A) ^ B) & (B | A) -> (A & B)
1710  // (B ^ (~A)) & (A | B) -> (A & B)
1711  // (B ^ (~A)) & (B | A) -> (A & B)
1712  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1713  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1714  return BinaryOperator::CreateAnd(A, B);
1715  }
1716 
1717  {
1718  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1719  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1720  if (LHS && RHS)
1721  if (Value *Res = foldAndOfICmps(LHS, RHS, I))
1722  return replaceInstUsesWith(I, Res);
1723 
1724  // TODO: Make this recursive; it's a little tricky because an arbitrary
1725  // number of 'and' instructions might have to be created.
1726  Value *X, *Y;
1727  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1728  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1729  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1730  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1731  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1732  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1733  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1734  }
1735  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1736  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1737  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1738  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1739  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1740  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1741  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1742  }
1743  }
1744 
1745  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
1746  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
1747  if (Value *Res = foldLogicOfFCmps(LHS, RHS, true))
1748  return replaceInstUsesWith(I, Res);
1749 
1750  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
1751  return CastedAnd;
1752 
1753  // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
1754  Value *A;
1755  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
1756  A->getType()->isIntOrIntVectorTy(1))
1757  return SelectInst::Create(A, Op1, Constant::getNullValue(I.getType()));
1758  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
1759  A->getType()->isIntOrIntVectorTy(1))
1760  return SelectInst::Create(A, Op0, Constant::getNullValue(I.getType()));
1761 
1762  return nullptr;
1763 }
1764 
1765 /// Given an OR instruction, check to see if this is a bswap idiom. If so,
1766 /// insert the new intrinsic and return it.
1767 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
1768  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1769 
1770  // Look through zero extends.
1771  if (Instruction *Ext = dyn_cast<ZExtInst>(Op0))
1772  Op0 = Ext->getOperand(0);
1773 
1774  if (Instruction *Ext = dyn_cast<ZExtInst>(Op1))
1775  Op1 = Ext->getOperand(0);
1776 
1777  // (A | B) | C and A | (B | C) -> bswap if possible.
1778  bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
1779  match(Op1, m_Or(m_Value(), m_Value()));
1780 
1781  // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible.
1782  bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1783  match(Op1, m_LogicalShift(m_Value(), m_Value()));
1784 
1785  // (A & B) | (C & D) -> bswap if possible.
1786  bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
1787  match(Op1, m_And(m_Value(), m_Value()));
1788 
1789  // (A << B) | (C & D) -> bswap if possible.
1790  // The bigger pattern here is ((A & C1) << C2) | ((B >> C2) & C1), which is a
1791  // part of the bswap idiom for specific values of C1, C2 (e.g. C1 = 16711935,
1792  // C2 = 8 for i32).
1793  // This pattern can occur when the operands of the 'or' are not canonicalized
1794  // for some reason (not having only one use, for example).
1795  bool OrOfAndAndSh = (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1796  match(Op1, m_And(m_Value(), m_Value()))) ||
1797  (match(Op0, m_And(m_Value(), m_Value())) &&
1798  match(Op1, m_LogicalShift(m_Value(), m_Value())));
1799 
1800  if (!OrOfOrs && !OrOfShifts && !OrOfAnds && !OrOfAndAndSh)
1801  return nullptr;
1802 
1804  if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
1805  return nullptr;
1806  Instruction *LastInst = Insts.pop_back_val();
1807  LastInst->removeFromParent();
1808 
1809  for (auto *Inst : Insts)
1810  Worklist.Add(Inst);
1811  return LastInst;
1812 }
1813 
1814 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
1816  unsigned NumElts = C1->getType()->getVectorNumElements();
1817  for (unsigned i = 0; i != NumElts; ++i) {
1818  Constant *EltC1 = C1->getAggregateElement(i);
1819  Constant *EltC2 = C2->getAggregateElement(i);
1820  if (!EltC1 || !EltC2)
1821  return false;
1822 
1823  // One element must be all ones, and the other must be all zeros.
1824  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
1825  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
1826  return false;
1827  }
1828  return true;
1829 }
1830 
1831 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
1832 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
1833 /// B, it can be used as the condition operand of a select instruction.
1835  InstCombiner::BuilderTy &Builder) {
1836  // If these are scalars or vectors of i1, A can be used directly.
1837  Type *Ty = A->getType();
1838  if (match(A, m_Not(m_Specific(B))) && Ty->isIntOrIntVectorTy(1))
1839  return A;
1840 
1841  // If A and B are sign-extended, look through the sexts to find the booleans.
1842  Value *Cond;
1843  Value *NotB;
1844  if (match(A, m_SExt(m_Value(Cond))) &&
1845  Cond->getType()->isIntOrIntVectorTy(1) &&
1846  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
1847  NotB = peekThroughBitcast(NotB, true);
1848  if (match(NotB, m_SExt(m_Specific(Cond))))
1849  return Cond;
1850  }
1851 
1852  // All scalar (and most vector) possibilities should be handled now.
1853  // Try more matches that only apply to non-splat constant vectors.
1854  if (!Ty->isVectorTy())
1855  return nullptr;
1856 
1857  // If both operands are constants, see if the constants are inverse bitmasks.
1858  Constant *AC, *BC;
1859  if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) &&
1860  areInverseVectorBitmasks(AC, BC)) {
1861  return Builder.CreateZExtOrTrunc(AC, CmpInst::makeCmpResultType(Ty));
1862  }
1863 
1864  // If both operands are xor'd with constants using the same sexted boolean
1865  // operand, see if the constants are inverse bitmasks.
1866  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) &&
1867  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) &&
1868  Cond->getType()->isIntOrIntVectorTy(1) &&
1869  areInverseVectorBitmasks(AC, BC)) {
1871  return Builder.CreateXor(Cond, AC);
1872  }
1873  return nullptr;
1874 }
1875 
1876 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
1877 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
1879  InstCombiner::BuilderTy &Builder) {
1880  // The potential condition of the select may be bitcasted. In that case, look
1881  // through its bitcast and the corresponding bitcast of the 'not' condition.
1882  Type *OrigType = A->getType();
1883  A = peekThroughBitcast(A, true);
1884  B = peekThroughBitcast(B, true);
1885 
1886  if (Value *Cond = getSelectCondition(A, B, Builder)) {
1887  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
1888  // The bitcasts will either all exist or all not exist. The builder will
1889  // not create unnecessary casts if the types already match.
1890  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
1891  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
1892  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
1893  return Builder.CreateBitCast(Select, OrigType);
1894  }
1895 
1896  return nullptr;
1897 }
1898 
1899 /// Fold (icmp)|(icmp) if possible.
1900 Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1901  Instruction &CxtI) {
1902  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
1903  // if K1 and K2 are a one-bit mask.
1904  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, false, CxtI))
1905  return V;
1906 
1907  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1908 
1909  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
1910  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
1911 
1912  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
1913  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
1914  // The original condition actually refers to the following two ranges:
1915  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
1916  // We can fold these two ranges if:
1917  // 1) C1 and C2 is unsigned greater than C3.
1918  // 2) The two ranges are separated.
1919  // 3) C1 ^ C2 is one-bit mask.
1920  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
1921  // This implies all values in the two ranges differ by exactly one bit.
1922 
1923  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
1924  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
1925  LHSC->getType() == RHSC->getType() &&
1926  LHSC->getValue() == (RHSC->getValue())) {
1927 
1928  Value *LAdd = LHS->getOperand(0);
1929  Value *RAdd = RHS->getOperand(0);
1930 
1931  Value *LAddOpnd, *RAddOpnd;
1932  ConstantInt *LAddC, *RAddC;
1933  if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddC))) &&
1934  match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddC))) &&
1935  LAddC->getValue().ugt(LHSC->getValue()) &&
1936  RAddC->getValue().ugt(LHSC->getValue())) {
1937 
1938  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
1939  if (LAddOpnd == RAddOpnd && DiffC.isPowerOf2()) {
1940  ConstantInt *MaxAddC = nullptr;
1941  if (LAddC->getValue().ult(RAddC->getValue()))
1942  MaxAddC = RAddC;
1943  else
1944  MaxAddC = LAddC;
1945 
1946  APInt RRangeLow = -RAddC->getValue();
1947  APInt RRangeHigh = RRangeLow + LHSC->getValue();
1948  APInt LRangeLow = -LAddC->getValue();
1949  APInt LRangeHigh = LRangeLow + LHSC->getValue();
1950  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
1951  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
1952  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
1953  : RRangeLow - LRangeLow;
1954 
1955  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
1956  RangeDiff.ugt(LHSC->getValue())) {
1957  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
1958 
1959  Value *NewAnd = Builder.CreateAnd(LAddOpnd, MaskC);
1960  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
1961  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
1962  }
1963  }
1964  }
1965  }
1966 
1967  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
1968  if (PredicatesFoldable(PredL, PredR)) {
1969  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1970  LHS->getOperand(1) == RHS->getOperand(0))
1971  LHS->swapOperands();
1972  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1973  LHS->getOperand(1) == RHS->getOperand(1)) {
1974  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1975  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
1976  bool isSigned = LHS->isSigned() || RHS->isSigned();
1977  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
1978  }
1979  }
1980 
1981  // handle (roughly):
1982  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
1983  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
1984  return V;
1985 
1986  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1987  if (LHS->hasOneUse() || RHS->hasOneUse()) {
1988  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
1989  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
1990  Value *A = nullptr, *B = nullptr;
1991  if (PredL == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero()) {
1992  B = LHS0;
1993  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS->getOperand(1))
1994  A = RHS0;
1995  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
1996  A = RHS->getOperand(1);
1997  }
1998  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
1999  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
2000  else if (PredR == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) {
2001  B = RHS0;
2002  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS->getOperand(1))
2003  A = LHS0;
2004  else if (PredL == ICmpInst::ICMP_UGT && LHS0 == RHS0)
2005  A = LHS->getOperand(1);
2006  }
2007  if (A && B)
2008  return Builder.CreateICmp(
2010  Builder.CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
2011  }
2012 
2013  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
2014  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
2015  return V;
2016 
2017  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
2018  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
2019  return V;
2020 
2021  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
2022  return V;
2023 
2024  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
2025  if (!LHSC || !RHSC)
2026  return nullptr;
2027 
2028  if (LHSC == RHSC && PredL == PredR) {
2029  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
2030  if (PredL == ICmpInst::ICMP_NE && LHSC->isZero()) {
2031  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
2032  return Builder.CreateICmp(PredL, NewOr, LHSC);
2033  }
2034  }
2035 
2036  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
2037  // iff C2 + CA == C1.
2038  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
2039  ConstantInt *AddC;
2040  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
2041  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
2042  return Builder.CreateICmpULE(LHS0, LHSC);
2043  }
2044 
2045  // From here on, we only handle:
2046  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
2047  if (LHS0 != RHS0)
2048  return nullptr;
2049 
2050  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
2051  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
2052  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
2053  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
2054  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
2055  return nullptr;
2056 
2057  // We can't fold (ugt x, C) | (sgt x, C2).
2058  if (!PredicatesFoldable(PredL, PredR))
2059  return nullptr;
2060 
2061  // Ensure that the larger constant is on the RHS.
2062  bool ShouldSwap;
2063  if (CmpInst::isSigned(PredL) ||
2064  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
2065  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
2066  else
2067  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
2068 
2069  if (ShouldSwap) {
2070  std::swap(LHS, RHS);
2071  std::swap(LHSC, RHSC);
2072  std::swap(PredL, PredR);
2073  }
2074 
2075  // At this point, we know we have two icmp instructions
2076  // comparing a value against two constants and or'ing the result
2077  // together. Because of the above check, we know that we only have
2078  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
2079  // icmp folding check above), that the two constants are not
2080  // equal.
2081  assert(LHSC != RHSC && "Compares not folded above?");
2082 
2083  switch (PredL) {
2084  default:
2085  llvm_unreachable("Unknown integer condition code!");
2086  case ICmpInst::ICMP_EQ:
2087  switch (PredR) {
2088  default:
2089  llvm_unreachable("Unknown integer condition code!");
2090  case ICmpInst::ICMP_EQ:
2091  // Potential folds for this case should already be handled.
2092  break;
2093  case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
2094  case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
2095  break;
2096  }
2097  break;
2098  case ICmpInst::ICMP_ULT:
2099  switch (PredR) {
2100  default:
2101  llvm_unreachable("Unknown integer condition code!");
2102  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
2103  break;
2104  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
2105  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
2106  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
2107  false, false);
2108  }
2109  break;
2110  case ICmpInst::ICMP_SLT:
2111  switch (PredR) {
2112  default:
2113  llvm_unreachable("Unknown integer condition code!");
2114  case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
2115  break;
2116  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
2117  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
2118  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
2119  false);
2120  }
2121  break;
2122  }
2123  return nullptr;
2124 }
2125 
2126 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2127 // here. We should standardize that construct where it is needed or choose some
2128 // other way to ensure that commutated variants of patterns are not missed.
2130  if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
2131  SQ.getWithInstruction(&I)))
2132  return replaceInstUsesWith(I, V);
2133 
2134  if (SimplifyAssociativeOrCommutative(I))
2135  return &I;
2136 
2137  if (Instruction *X = foldShuffledBinop(I))
2138  return X;
2139 
2140  // See if we can simplify any instructions used by the instruction whose sole
2141  // purpose is to compute bits we don't care about.
2142  if (SimplifyDemandedInstructionBits(I))
2143  return &I;
2144 
2145  // Do this before using distributive laws to catch simple and/or/not patterns.
2146  if (Instruction *Xor = foldOrToXor(I, Builder))
2147  return Xor;
2148 
2149  // (A&B)|(A&C) -> A&(B|C) etc
2150  if (Value *V = SimplifyUsingDistributiveLaws(I))
2151  return replaceInstUsesWith(I, V);
2152 
2153  if (Value *V = SimplifyBSwap(I, Builder))
2154  return replaceInstUsesWith(I, V);
2155 
2156  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2157  return FoldedLogic;
2158 
2159  // Given an OR instruction, check to see if this is a bswap.
2160  if (Instruction *BSwap = MatchBSwap(I))
2161  return BSwap;
2162 
2163  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2164  {
2165  Value *A;
2166  const APInt *C;
2167  // (X^C)|Y -> (X|Y)^C iff Y&C == 0
2168  if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
2169  MaskedValueIsZero(Op1, *C, 0, &I)) {
2170  Value *NOr = Builder.CreateOr(A, Op1);
2171  NOr->takeName(Op0);
2172  return BinaryOperator::CreateXor(NOr,
2173  ConstantInt::get(NOr->getType(), *C));
2174  }
2175 
2176  // Y|(X^C) -> (X|Y)^C iff Y&C == 0
2177  if (match(Op1, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
2178  MaskedValueIsZero(Op0, *C, 0, &I)) {
2179  Value *NOr = Builder.CreateOr(A, Op0);
2180  NOr->takeName(Op0);
2181  return BinaryOperator::CreateXor(NOr,
2182  ConstantInt::get(NOr->getType(), *C));
2183  }
2184  }
2185 
2186  Value *A, *B;
2187 
2188  // (A & C)|(B & D)
2189  Value *C = nullptr, *D = nullptr;
2190  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2191  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2194  if (C1 && C2) { // (A & C1)|(B & C2)
2195  Value *V1 = nullptr, *V2 = nullptr;
2196  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2197  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2198  // iff (C1&C2) == 0 and (N&~C1) == 0
2199  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2200  ((V1 == B &&
2201  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2202  (V2 == B &&
2203  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2204  return BinaryOperator::CreateAnd(A,
2205  Builder.getInt(C1->getValue()|C2->getValue()));
2206  // Or commutes, try both ways.
2207  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2208  ((V1 == A &&
2209  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2210  (V2 == A &&
2211  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2212  return BinaryOperator::CreateAnd(B,
2213  Builder.getInt(C1->getValue()|C2->getValue()));
2214 
2215  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2216  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2217  ConstantInt *C3 = nullptr, *C4 = nullptr;
2218  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2219  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2220  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2221  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2222  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2223  return BinaryOperator::CreateAnd(V2,
2224  Builder.getInt(C1->getValue()|C2->getValue()));
2225  }
2226  }
2227 
2228  if (C1->getValue() == ~C2->getValue()) {
2229  Value *X;
2230 
2231  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2232  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2233  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2234  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2235  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2236  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2237 
2238  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2239  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2240  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2241  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2242  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2243  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2244  }
2245  }
2246 
2247  // Don't try to form a select if it's unlikely that we'll get rid of at
2248  // least one of the operands. A select is generally more expensive than the
2249  // 'or' that it is replacing.
2250  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2251  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2252  if (Value *V = matchSelectFromAndOr(A, C, B, D, Builder))
2253  return replaceInstUsesWith(I, V);
2254  if (Value *V = matchSelectFromAndOr(A, C, D, B, Builder))
2255  return replaceInstUsesWith(I, V);
2256  if (Value *V = matchSelectFromAndOr(C, A, B, D, Builder))
2257  return replaceInstUsesWith(I, V);
2258  if (Value *V = matchSelectFromAndOr(C, A, D, B, Builder))
2259  return replaceInstUsesWith(I, V);
2260  if (Value *V = matchSelectFromAndOr(B, D, A, C, Builder))
2261  return replaceInstUsesWith(I, V);
2262  if (Value *V = matchSelectFromAndOr(B, D, C, A, Builder))
2263  return replaceInstUsesWith(I, V);
2264  if (Value *V = matchSelectFromAndOr(D, B, A, C, Builder))
2265  return replaceInstUsesWith(I, V);
2266  if (Value *V = matchSelectFromAndOr(D, B, C, A, Builder))
2267  return replaceInstUsesWith(I, V);
2268  }
2269  }
2270 
2271  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2272  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2273  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2274  return BinaryOperator::CreateOr(Op0, C);
2275 
2276  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2277  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2278  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2279  return BinaryOperator::CreateOr(Op1, C);
2280 
2281  // ((B | C) & A) | B -> B | (A & C)
2282  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2283  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2284 
2285  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2286  return DeMorgan;
2287 
2288  // Canonicalize xor to the RHS.
2289  bool SwappedForXor = false;
2290  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2291  std::swap(Op0, Op1);
2292  SwappedForXor = true;
2293  }
2294 
2295  // A | ( A ^ B) -> A | B
2296  // A | (~A ^ B) -> A | ~B
2297  // (A & B) | (A ^ B)
2298  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2299  if (Op0 == A || Op0 == B)
2300  return BinaryOperator::CreateOr(A, B);
2301 
2302  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2303  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2304  return BinaryOperator::CreateOr(A, B);
2305 
2306  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2307  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2308  return BinaryOperator::CreateOr(Not, Op0);
2309  }
2310  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2311  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2312  return BinaryOperator::CreateOr(Not, Op0);
2313  }
2314  }
2315 
2316  // A | ~(A | B) -> A | ~B
2317  // A | ~(A ^ B) -> A | ~B
2318  if (match(Op1, m_Not(m_Value(A))))
2319  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2320  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2321  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2322  B->getOpcode() == Instruction::Xor)) {
2323  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2324  B->getOperand(0);
2325  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2326  return BinaryOperator::CreateOr(Not, Op0);
2327  }
2328 
2329  if (SwappedForXor)
2330  std::swap(Op0, Op1);
2331 
2332  {
2333  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2334  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2335  if (LHS && RHS)
2336  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2337  return replaceInstUsesWith(I, Res);
2338 
2339  // TODO: Make this recursive; it's a little tricky because an arbitrary
2340  // number of 'or' instructions might have to be created.
2341  Value *X, *Y;
2342  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2343  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2344  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2345  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2346  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2347  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2348  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2349  }
2350  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2351  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2352  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2353  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2354  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2355  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2356  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2357  }
2358  }
2359 
2360  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2361  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2362  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2363  return replaceInstUsesWith(I, Res);
2364 
2365  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2366  return CastedOr;
2367 
2368  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2369  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2370  A->getType()->isIntOrIntVectorTy(1))
2371  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2372  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2373  A->getType()->isIntOrIntVectorTy(1))
2374  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2375 
2376  // Note: If we've gotten to the point of visiting the outer OR, then the
2377  // inner one couldn't be simplified. If it was a constant, then it won't
2378  // be simplified by a later pass either, so we try swapping the inner/outer
2379  // ORs in the hopes that we'll be able to simplify it this way.
2380  // (X|C) | V --> (X|V) | C
2381  ConstantInt *C1;
2382  if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
2383  match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) {
2384  Value *Inner = Builder.CreateOr(A, Op1);
2385  Inner->takeName(Op0);
2386  return BinaryOperator::CreateOr(Inner, C1);
2387  }
2388 
2389  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2390  // Since this OR statement hasn't been optimized further yet, we hope
2391  // that this transformation will allow the new ORs to be optimized.
2392  {
2393  Value *X = nullptr, *Y = nullptr;
2394  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2395  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2396  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2397  Value *orTrue = Builder.CreateOr(A, C);
2398  Value *orFalse = Builder.CreateOr(B, D);
2399  return SelectInst::Create(X, orTrue, orFalse);
2400  }
2401  }
2402 
2403  return nullptr;
2404 }
2405 
2406 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2407 /// can fold these early and efficiently by morphing an existing instruction.
2409  InstCombiner::BuilderTy &Builder) {
2410  assert(I.getOpcode() == Instruction::Xor);
2411  Value *Op0 = I.getOperand(0);
2412  Value *Op1 = I.getOperand(1);
2413  Value *A, *B;
2414 
2415  // There are 4 commuted variants for each of the basic patterns.
2416 
2417  // (A & B) ^ (A | B) -> A ^ B
2418  // (A & B) ^ (B | A) -> A ^ B
2419  // (A | B) ^ (A & B) -> A ^ B
2420  // (A | B) ^ (B & A) -> A ^ B
2421  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2422  m_c_Or(m_Deferred(A), m_Deferred(B))))) {
2423  I.setOperand(0, A);
2424  I.setOperand(1, B);
2425  return &I;
2426  }
2427 
2428  // (A | ~B) ^ (~A | B) -> A ^ B
2429  // (~B | A) ^ (~A | B) -> A ^ B
2430  // (~A | B) ^ (A | ~B) -> A ^ B
2431  // (B | ~A) ^ (A | ~B) -> A ^ B
2432  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2433  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2434  I.setOperand(0, A);
2435  I.setOperand(1, B);
2436  return &I;
2437  }
2438 
2439  // (A & ~B) ^ (~A & B) -> A ^ B
2440  // (~B & A) ^ (~A & B) -> A ^ B
2441  // (~A & B) ^ (A & ~B) -> A ^ B
2442  // (B & ~A) ^ (A & ~B) -> A ^ B
2443  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2444  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2445  I.setOperand(0, A);
2446  I.setOperand(1, B);
2447  return &I;
2448  }
2449 
2450  // For the remaining cases we need to get rid of one of the operands.
2451  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2452  return nullptr;
2453 
2454  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2455  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2456  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2457  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2458  // Complexity sorting ensures the not will be on the right side.
2459  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2460  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2461  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2462  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2463  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2464 
2465  return nullptr;
2466 }
2467 
2468 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
2469  if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2470  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2471  LHS->getOperand(1) == RHS->getOperand(0))
2472  LHS->swapOperands();
2473  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2474  LHS->getOperand(1) == RHS->getOperand(1)) {
2475  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2476  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2477  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2478  bool isSigned = LHS->isSigned() || RHS->isSigned();
2479  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
2480  }
2481  }
2482 
2483  // TODO: This can be generalized to compares of non-signbits using
2484  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
2485  // foldLogOpOfMaskedICmps().
2486  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2487  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
2488  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
2489  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
2490  LHS0->getType() == RHS0->getType()) {
2491  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
2492  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
2493  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2494  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
2495  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2496  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
2497  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
2498  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
2499  }
2500  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
2501  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
2502  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2503  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
2504  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2505  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
2506  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
2507  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
2508  }
2509  }
2510 
2511  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2512  // into those logic ops. That is, try to turn this into an and-of-icmps
2513  // because we have many folds for that pattern.
2514  //
2515  // This is based on a truth table definition of xor:
2516  // X ^ Y --> (X | Y) & !(X & Y)
2517  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2518  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2519  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2520  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2521  // TODO: Independently handle cases where the 'and' side is a constant.
2522  if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
2523  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
2524  RHS->setPredicate(RHS->getInversePredicate());
2525  return Builder.CreateAnd(LHS, RHS);
2526  }
2527  if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
2528  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
2529  LHS->setPredicate(LHS->getInversePredicate());
2530  return Builder.CreateAnd(LHS, RHS);
2531  }
2532  }
2533  }
2534 
2535  return nullptr;
2536 }
2537 
2538 /// If we have a masked merge, in the canonical form of:
2539 /// (assuming that A only has one use.)
2540 /// | A | |B|
2541 /// ((x ^ y) & M) ^ y
2542 /// | D |
2543 /// * If M is inverted:
2544 /// | D |
2545 /// ((x ^ y) & ~M) ^ y
2546 /// We can canonicalize by swapping the final xor operand
2547 /// to eliminate the 'not' of the mask.
2548 /// ((x ^ y) & M) ^ x
2549 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
2550 /// because that shortens the dependency chain and improves analysis:
2551 /// (x & M) | (y & ~M)
2553  InstCombiner::BuilderTy &Builder) {
2554  Value *B, *X, *D;
2555  Value *M;
2556  if (!match(&I, m_c_Xor(m_Value(B),
2557  m_OneUse(m_c_And(
2559  m_Value(D)),
2560  m_Value(M))))))
2561  return nullptr;
2562 
2563  Value *NotM;
2564  if (match(M, m_Not(m_Value(NotM)))) {
2565  // De-invert the mask and swap the value in B part.
2566  Value *NewA = Builder.CreateAnd(D, NotM);
2567  return BinaryOperator::CreateXor(NewA, X);
2568  }
2569 
2570  Constant *C;
2571  if (D->hasOneUse() && match(M, m_Constant(C))) {
2572  // Unfold.
2573  Value *LHS = Builder.CreateAnd(X, C);
2574  Value *NotC = Builder.CreateNot(C);
2575  Value *RHS = Builder.CreateAnd(B, NotC);
2576  return BinaryOperator::CreateOr(LHS, RHS);
2577  }
2578 
2579  return nullptr;
2580 }
2581 
2582 // Transform
2583 // ~(x ^ y)
2584 // into:
2585 // (~x) ^ y
2586 // or into
2587 // x ^ (~y)
2589  InstCombiner::BuilderTy &Builder) {
2590  Value *X, *Y;
2591  // FIXME: one-use check is not needed in general, but currently we are unable
2592  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
2593  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
2594  return nullptr;
2595 
2596  // We only want to do the transform if it is free to do.
2597  if (IsFreeToInvert(X, X->hasOneUse())) {
2598  // Ok, good.
2599  } else if (IsFreeToInvert(Y, Y->hasOneUse())) {
2600  std::swap(X, Y);
2601  } else
2602  return nullptr;
2603 
2604  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
2605  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
2606 }
2607 
2608 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2609 // here. We should standardize that construct where it is needed or choose some
2610 // other way to ensure that commutated variants of patterns are not missed.
2612  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
2613  SQ.getWithInstruction(&I)))
2614  return replaceInstUsesWith(I, V);
2615 
2616  if (SimplifyAssociativeOrCommutative(I))
2617  return &I;
2618 
2619  if (Instruction *X = foldShuffledBinop(I))
2620  return X;
2621 
2622  if (Instruction *NewXor = foldXorToXor(I, Builder))
2623  return NewXor;
2624 
2625  // (A&B)^(A&C) -> A&(B^C) etc
2626  if (Value *V = SimplifyUsingDistributiveLaws(I))
2627  return replaceInstUsesWith(I, V);
2628 
2629  // See if we can simplify any instructions used by the instruction whose sole
2630  // purpose is to compute bits we don't care about.
2631  if (SimplifyDemandedInstructionBits(I))
2632  return &I;
2633 
2634  if (Value *V = SimplifyBSwap(I, Builder))
2635  return replaceInstUsesWith(I, V);
2636 
2637  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2638 
2639  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
2640  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
2641  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
2642  // have already taken care of those cases.
2643  Value *M;
2644  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
2645  m_c_And(m_Deferred(M), m_Value()))))
2646  return BinaryOperator::CreateOr(Op0, Op1);
2647 
2648  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
2649  Value *X, *Y;
2650 
2651  // We must eliminate the and/or (one-use) for these transforms to not increase
2652  // the instruction count.
2653  // ~(~X & Y) --> (X | ~Y)
2654  // ~(Y & ~X) --> (X | ~Y)
2655  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
2656  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2657  return BinaryOperator::CreateOr(X, NotY);
2658  }
2659  // ~(~X | Y) --> (X & ~Y)
2660  // ~(Y | ~X) --> (X & ~Y)
2661  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
2662  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2663  return BinaryOperator::CreateAnd(X, NotY);
2664  }
2665 
2666  if (Instruction *Xor = visitMaskedMerge(I, Builder))
2667  return Xor;
2668 
2669  // Is this a 'not' (~) fed by a binary operator?
2670  BinaryOperator *NotVal;
2671  if (match(&I, m_Not(m_BinOp(NotVal)))) {
2672  if (NotVal->getOpcode() == Instruction::And ||
2673  NotVal->getOpcode() == Instruction::Or) {
2674  // Apply DeMorgan's Law when inverts are free:
2675  // ~(X & Y) --> (~X | ~Y)
2676  // ~(X | Y) --> (~X & ~Y)
2677  if (IsFreeToInvert(NotVal->getOperand(0),
2678  NotVal->getOperand(0)->hasOneUse()) &&
2679  IsFreeToInvert(NotVal->getOperand(1),
2680  NotVal->getOperand(1)->hasOneUse())) {
2681  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
2682  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
2683  if (NotVal->getOpcode() == Instruction::And)
2684  return BinaryOperator::CreateOr(NotX, NotY);
2685  return BinaryOperator::CreateAnd(NotX, NotY);
2686  }
2687  }
2688 
2689  // ~(X - Y) --> ~X + Y
2690  if (match(NotVal, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))))
2691  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
2692 
2693  // ~(~X >>s Y) --> (X >>s Y)
2694  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
2695  return BinaryOperator::CreateAShr(X, Y);
2696 
2697  // If we are inverting a right-shifted constant, we may be able to eliminate
2698  // the 'not' by inverting the constant and using the opposite shift type.
2699  // Canonicalization rules ensure that only a negative constant uses 'ashr',
2700  // but we must check that in case that transform has not fired yet.
2701  Constant *C;
2702  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
2703  match(C, m_Negative())) {
2704  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
2705  Constant *NotC = ConstantExpr::getNot(C);
2706  return BinaryOperator::CreateLShr(NotC, Y);
2707  }
2708 
2709  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
2710  match(C, m_NonNegative())) {
2711  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
2712  Constant *NotC = ConstantExpr::getNot(C);
2713  return BinaryOperator::CreateAShr(NotC, Y);
2714  }
2715  }
2716 
2717  // not (cmp A, B) = !cmp A, B
2718  CmpInst::Predicate Pred;
2719  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
2720  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
2721  return replaceInstUsesWith(I, Op0);
2722  }
2723 
2724  {
2725  const APInt *RHSC;
2726  if (match(Op1, m_APInt(RHSC))) {
2727  Value *X;
2728  const APInt *C;
2729  if (match(Op0, m_Sub(m_APInt(C), m_Value(X)))) {
2730  // ~(c-X) == X-c-1 == X+(-c-1)
2731  if (RHSC->isAllOnesValue()) {
2732  Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1);
2733  return BinaryOperator::CreateAdd(X, NewC);
2734  }
2735  if (RHSC->isSignMask()) {
2736  // (C - X) ^ signmask -> (C + signmask - X)
2737  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2738  return BinaryOperator::CreateSub(NewC, X);
2739  }
2740  } else if (match(Op0, m_Add(m_Value(X), m_APInt(C)))) {
2741  // ~(X-c) --> (-c-1)-X
2742  if (RHSC->isAllOnesValue()) {
2743  Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1);
2744  return BinaryOperator::CreateSub(NewC, X);
2745  }
2746  if (RHSC->isSignMask()) {
2747  // (X + C) ^ signmask -> (X + C + signmask)
2748  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2749  return BinaryOperator::CreateAdd(X, NewC);
2750  }
2751  }
2752 
2753  // (X|C1)^C2 -> X^(C1^C2) iff X&~C1 == 0
2754  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
2755  MaskedValueIsZero(X, *C, 0, &I)) {
2756  Constant *NewC = ConstantInt::get(I.getType(), *C ^ *RHSC);
2757  Worklist.Add(cast<Instruction>(Op0));
2758  I.setOperand(0, X);
2759  I.setOperand(1, NewC);
2760  return &I;
2761  }
2762  }
2763  }
2764 
2765  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
2766  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2767  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2768  if (Op0I->getOpcode() == Instruction::LShr) {
2769  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
2770  // E1 = "X ^ C1"
2771  BinaryOperator *E1;
2772  ConstantInt *C1;
2773  if (Op0I->hasOneUse() &&
2774  (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
2775  E1->getOpcode() == Instruction::Xor &&
2776  (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
2777  // fold (C1 >> C2) ^ C3
2778  ConstantInt *C2 = Op0CI, *C3 = RHSC;
2779  APInt FoldConst = C1->getValue().lshr(C2->getValue());
2780  FoldConst ^= C3->getValue();
2781  // Prepare the two operands.
2782  Value *Opnd0 = Builder.CreateLShr(E1->getOperand(0), C2);
2783  Opnd0->takeName(Op0I);
2784  cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
2785  Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
2786 
2787  return BinaryOperator::CreateXor(Opnd0, FoldVal);
2788  }
2789  }
2790  }
2791  }
2792  }
2793 
2794  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2795  return FoldedLogic;
2796 
2797  {
2798  Value *A, *B;
2799  if (match(Op1, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2800  if (A == Op0) { // A^(A|B) == A^(B|A)
2801  cast<BinaryOperator>(Op1)->swapOperands();
2802  std::swap(A, B);
2803  }
2804  if (B == Op0) { // A^(B|A) == (B|A)^A
2805  I.swapOperands(); // Simplified below.
2806  std::swap(Op0, Op1);
2807  }
2808  } else if (match(Op1, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2809  if (A == Op0) { // A^(A&B) -> A^(B&A)
2810  cast<BinaryOperator>(Op1)->swapOperands();
2811  std::swap(A, B);
2812  }
2813  if (B == Op0) { // A^(B&A) -> (B&A)^A
2814  I.swapOperands(); // Simplified below.
2815  std::swap(Op0, Op1);
2816  }
2817  }
2818  }
2819 
2820  {
2821  Value *A, *B;
2822  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2823  if (A == Op1) // (B|A)^B == (A|B)^B
2824  std::swap(A, B);
2825  if (B == Op1) // (A|B)^B == A & ~B
2826  return BinaryOperator::CreateAnd(A, Builder.CreateNot(Op1));
2827  } else if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2828  if (A == Op1) // (A&B)^A -> (B&A)^A
2829  std::swap(A, B);
2830  const APInt *C;
2831  if (B == Op1 && // (B&A)^A == ~B & A
2832  !match(Op1, m_APInt(C))) { // Canonical form is (B&C)^C
2833  return BinaryOperator::CreateAnd(Builder.CreateNot(A), Op1);
2834  }
2835  }
2836  }
2837 
2838  {
2839  Value *A, *B, *C, *D;
2840  // (A ^ C)^(A | B) -> ((~A) & B) ^ C
2841  if (match(Op0, m_Xor(m_Value(D), m_Value(C))) &&
2842  match(Op1, m_Or(m_Value(A), m_Value(B)))) {
2843  if (D == A)
2844  return BinaryOperator::CreateXor(
2845  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2846  if (D == B)
2847  return BinaryOperator::CreateXor(
2848  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2849  }
2850  // (A | B)^(A ^ C) -> ((~A) & B) ^ C
2851  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2852  match(Op1, m_Xor(m_Value(D), m_Value(C)))) {
2853  if (D == A)
2854  return BinaryOperator::CreateXor(
2855  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2856  if (D == B)
2857  return BinaryOperator::CreateXor(
2858  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2859  }
2860  // (A & B) ^ (A ^ B) -> (A | B)
2861  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2862  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
2863  return BinaryOperator::CreateOr(A, B);
2864  // (A ^ B) ^ (A & B) -> (A | B)
2865  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2866  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2867  return BinaryOperator::CreateOr(A, B);
2868  }
2869 
2870  // (A & ~B) ^ ~A -> ~(A & B)
2871  // (~B & A) ^ ~A -> ~(A & B)
2872  Value *A, *B;
2873  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
2874  match(Op1, m_Not(m_Specific(A))))
2875  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
2876 
2877  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
2878  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
2879  if (Value *V = foldXorOfICmps(LHS, RHS))
2880  return replaceInstUsesWith(I, V);
2881 
2882  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
2883  return CastedXor;
2884 
2885  // Canonicalize a shifty way to code absolute value to the common pattern.
2886  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
2887  // We're relying on the fact that we only do this transform when the shift has
2888  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
2889  // instructions).
2890  if (Op0->hasNUses(2))
2891  std::swap(Op0, Op1);
2892 
2893  const APInt *ShAmt;
2894  Type *Ty = I.getType();
2895  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2896  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2897  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
2898  // B = ashr i32 A, 31 ; smear the sign bit
2899  // xor (add A, B), B ; add -1 and flip bits if negative
2900  // --> (A < 0) ? -A : A
2901  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
2902  // Copy the nuw/nsw flags from the add to the negate.
2903  auto *Add = cast<BinaryOperator>(Op0);
2904  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
2905  Add->hasNoSignedWrap());
2906  return SelectInst::Create(Cmp, Neg, A);
2907  }
2908 
2909  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
2910  //
2911  // %notx = xor i32 %x, -1
2912  // %cmp1 = icmp sgt i32 %notx, %y
2913  // %smax = select i1 %cmp1, i32 %notx, i32 %y
2914  // %res = xor i32 %smax, -1
2915  // =>
2916  // %noty = xor i32 %y, -1
2917  // %cmp2 = icmp slt %x, %noty
2918  // %res = select i1 %cmp2, i32 %x, i32 %noty
2919  //
2920  // Same is applicable for smin/umax/umin.
2921  {
2922  Value *LHS, *RHS;
2923  SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
2924  if (Op0->hasOneUse() && SelectPatternResult::isMinOrMax(SPF) &&
2925  match(Op1, m_AllOnes())) {
2926 
2927  Value *X;
2928  if (match(RHS, m_Not(m_Value(X))))
2929  std::swap(RHS, LHS);
2930 
2931  if (match(LHS, m_Not(m_Value(X)))) {
2932  Value *NotY = Builder.CreateNot(RHS);
2933  return SelectInst::Create(
2934  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
2935  }
2936  }
2937  }
2938 
2939  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
2940  return NewXor;
2941 
2942  return nullptr;
2943 }
const NoneType None
Definition: None.h:24
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:718
uint64_t CallInst * C
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of nonnegative values.
Definition: PatternMatch.h:340
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to have exactly one bit set when defined. ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1846
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool isSignMask() const
Check if the APInt&#39;s value is returned by getSignMask.
Definition: APInt.h:473
Type * getSrcTy() const
Return the source type, as a convenience.
Definition: InstrTypes.h:850
static bool IsFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
static Value * getFCmpValue(unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp inst...
Instruction * visitXor(BinaryOperator &I)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1246
static Value * foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, Instruction &CxtI, InstCombiner::BuilderTy &Builder)
General pattern: X & Y.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:651
Instruction * visitOr(BinaryOperator &I)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:373
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1566
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1127
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1752
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1148
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
static unsigned getFCmpCode(FCmpInst::Predicate CC)
Similar to getICmpCode but for FCmpInst.
This class represents zero extension of integer types.
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:670
static bool areInverseVectorBitmasks(Constant *C1, Constant *C2)
If all elements of two constant vectors are 0/-1 and inverses, return true.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:865
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:648
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
unsigned less or equal
Definition: InstrTypes.h:911
unsigned less than
Definition: InstrTypes.h:910
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:748
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1323
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:891
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:901
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1268
MaskedICmpType
Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified...
static Value * SimplifyBSwap(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
F(f)
This class represents a sign extension of integer types.
#define R2(n)
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1233
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
static bool isBitwiseLogicOp(unsigned Opcode)
Determine if the Opcode is and/or/xor.
Definition: Instruction.h:166
Value * SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Or, fold the result or return null.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:910
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1282
bool swapOperands()
Exchange the two operands to this instruction.
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:896
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:895
bool isSigned() const
Definition: InstrTypes.h:1054
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:730
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:983
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:592
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:993
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
static Constant * AddOne(Constant *C)
Add one to a Constant.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:892
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1628
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:962
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:639
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1642
static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)...
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1629
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:845
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
This instruction compares its operands according to the predicate given to the constructor.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
static Value * foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:442
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:203
SelectClass_match< Cond, LHS, RHS > m_Select(const Cond &C, const LHS &L, const RHS &R)
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:382
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:66
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1007
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:170
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1130
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1854
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
static Optional< std::pair< unsigned, unsigned > > getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR)
Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:742
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:396
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool hasNUses(unsigned N) const
Return true if this Value has exactly N users.
Definition: Value.cpp:132
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:177
static Value * getSelectCondition(Value *A, Value *B, InstCombiner::BuilderTy &Builder)
We have an expression of the form (A & C) | (B & D).
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
static unsigned getMaskedICmpType(Value *A, Value *B, Value *C, ICmpInst::Predicate Pred)
Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C) satisfies.
static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth)
Return true if a constant shift amount is always less than the specified bit-width.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:724
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1179
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:1901
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if &#39;V & Mask&#39; is known to be zero.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
static Constant * getAnd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2245
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:411
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:306
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:443
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:736
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:894
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
static unsigned conjugateICmpMask(unsigned Mask)
Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite s...
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition: APInt.h:450
CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF)
Return the canonical inverse comparison predicate for the specified minimum/maximum flavor...
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2180
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:322
1 1 1 1 Always true (always folded)
Definition: InstrTypes.h:902
static Value * getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
void swapOperands()
Exchange the two operands to this instruction in such a way that it does not modify the semantics of ...
static Instruction * matchDeMorgansLaws(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Match De Morgan&#39;s Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B))
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:900
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:512
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:971
signed greater than
Definition: InstrTypes.h:912
Instruction * visitAnd(BinaryOperator &I)
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2109
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
static Value * foldLogOpOfMaskedICmpsAsymmetric(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, unsigned LHSMask, unsigned RHSMask, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y), where the left-hand ...
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:889
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:328
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
SelectPatternFlavor Flavor
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:899
SelectPatternFlavor
Specific patterns of select instructions we can match.
signed less than
Definition: InstrTypes.h:914
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1614
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:635
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:852
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2)
Return true if both predicates match sign or if at least one of them is an equality comparison (which...
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:964
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
signed less or equal
Definition: InstrTypes.h:915
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Class for arbitrary precision integers.
Definition: APInt.h:70
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1217
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:464
static Instruction * sinkNotIntoXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
void removeFromParent()
This method unlinks &#39;this&#39; from the containing basic block, but does not delete it.
Definition: Instruction.cpp:64
static Instruction * foldAndToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Value * SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
static Value * foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)...
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1249
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:290
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1315
Value * getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, CmpInst::Predicate &NewICmpPred)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
unsigned greater or equal
Definition: InstrTypes.h:909
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
static bool isSigned(Value *V)
Can the given value generate sign bits.
bool isEquality() const
Return true if this predicate is either EQ or NE.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static Constant * getOr(Constant *C1, Constant *C2)
Definition: Constants.cpp:2249
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:893
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Value * SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:897
APInt byteSwap() const
Definition: APInt.cpp:617
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1112
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:437
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:888
LLVM Value Representation.
Definition: Value.h:73
This file provides internal interfaces used to implement the InstCombine.
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:898
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:352
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:131
static Instruction * visitMaskedMerge(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have a masked merge, in the canonical form of: (assuming that A only has one use...
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
unsigned greater than
Definition: InstrTypes.h:908
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:999
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
Value * simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction *> &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:2694
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:890
static Value * matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D, InstCombiner::BuilderTy &Builder)
We have an expression of the form (A & C) | (B & D).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
Fold {and,or,xor} (cast X), C.
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
static Instruction * foldXorToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
A ^ B can be specified using other logic ops in a variety of patterns.
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:406
0 0 0 0 Always false (always folded)
Definition: InstrTypes.h:887
signed greater or equal
Definition: InstrTypes.h:913
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:983
static Constant * getXor(Constant *C1, Constant *C2)
Definition: Constants.cpp:2253
CallInst * CreateCall(Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1871