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 = foldVectorBinop(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 = foldVectorBinop(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  if (Instruction *BSwap = MatchBSwap(I))
2160  return BSwap;
2161 
2162  Value *X, *Y;
2163  const APInt *CV;
2164  if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
2165  !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) {
2166  // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
2167  // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
2168  Value *Or = Builder.CreateOr(X, Y);
2169  return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
2170  }
2171 
2172  // (A & C)|(B & D)
2173  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2174  Value *A, *B, *C, *D;
2175  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2176  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2179  if (C1 && C2) { // (A & C1)|(B & C2)
2180  Value *V1 = nullptr, *V2 = nullptr;
2181  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2182  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2183  // iff (C1&C2) == 0 and (N&~C1) == 0
2184  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2185  ((V1 == B &&
2186  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2187  (V2 == B &&
2188  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2189  return BinaryOperator::CreateAnd(A,
2190  Builder.getInt(C1->getValue()|C2->getValue()));
2191  // Or commutes, try both ways.
2192  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2193  ((V1 == A &&
2194  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2195  (V2 == A &&
2196  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2197  return BinaryOperator::CreateAnd(B,
2198  Builder.getInt(C1->getValue()|C2->getValue()));
2199 
2200  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2201  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2202  ConstantInt *C3 = nullptr, *C4 = nullptr;
2203  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2204  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2205  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2206  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2207  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2208  return BinaryOperator::CreateAnd(V2,
2209  Builder.getInt(C1->getValue()|C2->getValue()));
2210  }
2211  }
2212 
2213  if (C1->getValue() == ~C2->getValue()) {
2214  Value *X;
2215 
2216  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2217  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2218  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2219  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2220  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2221  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2222 
2223  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2224  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2225  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2226  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2227  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2228  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2229  }
2230  }
2231 
2232  // Don't try to form a select if it's unlikely that we'll get rid of at
2233  // least one of the operands. A select is generally more expensive than the
2234  // 'or' that it is replacing.
2235  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2236  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2237  if (Value *V = matchSelectFromAndOr(A, C, B, D, Builder))
2238  return replaceInstUsesWith(I, V);
2239  if (Value *V = matchSelectFromAndOr(A, C, D, B, Builder))
2240  return replaceInstUsesWith(I, V);
2241  if (Value *V = matchSelectFromAndOr(C, A, B, D, Builder))
2242  return replaceInstUsesWith(I, V);
2243  if (Value *V = matchSelectFromAndOr(C, A, D, B, Builder))
2244  return replaceInstUsesWith(I, V);
2245  if (Value *V = matchSelectFromAndOr(B, D, A, C, Builder))
2246  return replaceInstUsesWith(I, V);
2247  if (Value *V = matchSelectFromAndOr(B, D, C, A, Builder))
2248  return replaceInstUsesWith(I, V);
2249  if (Value *V = matchSelectFromAndOr(D, B, A, C, Builder))
2250  return replaceInstUsesWith(I, V);
2251  if (Value *V = matchSelectFromAndOr(D, B, C, A, Builder))
2252  return replaceInstUsesWith(I, V);
2253  }
2254  }
2255 
2256  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2257  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2258  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2259  return BinaryOperator::CreateOr(Op0, C);
2260 
2261  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2262  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2263  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2264  return BinaryOperator::CreateOr(Op1, C);
2265 
2266  // ((B | C) & A) | B -> B | (A & C)
2267  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2268  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2269 
2270  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2271  return DeMorgan;
2272 
2273  // Canonicalize xor to the RHS.
2274  bool SwappedForXor = false;
2275  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2276  std::swap(Op0, Op1);
2277  SwappedForXor = true;
2278  }
2279 
2280  // A | ( A ^ B) -> A | B
2281  // A | (~A ^ B) -> A | ~B
2282  // (A & B) | (A ^ B)
2283  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2284  if (Op0 == A || Op0 == B)
2285  return BinaryOperator::CreateOr(A, B);
2286 
2287  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2288  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2289  return BinaryOperator::CreateOr(A, B);
2290 
2291  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2292  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2293  return BinaryOperator::CreateOr(Not, Op0);
2294  }
2295  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2296  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2297  return BinaryOperator::CreateOr(Not, Op0);
2298  }
2299  }
2300 
2301  // A | ~(A | B) -> A | ~B
2302  // A | ~(A ^ B) -> A | ~B
2303  if (match(Op1, m_Not(m_Value(A))))
2304  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2305  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2306  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2307  B->getOpcode() == Instruction::Xor)) {
2308  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2309  B->getOperand(0);
2310  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2311  return BinaryOperator::CreateOr(Not, Op0);
2312  }
2313 
2314  if (SwappedForXor)
2315  std::swap(Op0, Op1);
2316 
2317  {
2318  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2319  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2320  if (LHS && RHS)
2321  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2322  return replaceInstUsesWith(I, Res);
2323 
2324  // TODO: Make this recursive; it's a little tricky because an arbitrary
2325  // number of 'or' instructions might have to be created.
2326  Value *X, *Y;
2327  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2328  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2329  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2330  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2331  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2332  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2333  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2334  }
2335  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2336  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2337  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2338  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2339  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2340  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2341  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2342  }
2343  }
2344 
2345  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2346  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2347  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2348  return replaceInstUsesWith(I, Res);
2349 
2350  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2351  return CastedOr;
2352 
2353  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2354  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2355  A->getType()->isIntOrIntVectorTy(1))
2356  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2357  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2358  A->getType()->isIntOrIntVectorTy(1))
2359  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2360 
2361  // Note: If we've gotten to the point of visiting the outer OR, then the
2362  // inner one couldn't be simplified. If it was a constant, then it won't
2363  // be simplified by a later pass either, so we try swapping the inner/outer
2364  // ORs in the hopes that we'll be able to simplify it this way.
2365  // (X|C) | V --> (X|V) | C
2366  ConstantInt *CI;
2367  if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
2368  match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
2369  Value *Inner = Builder.CreateOr(A, Op1);
2370  Inner->takeName(Op0);
2371  return BinaryOperator::CreateOr(Inner, CI);
2372  }
2373 
2374  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2375  // Since this OR statement hasn't been optimized further yet, we hope
2376  // that this transformation will allow the new ORs to be optimized.
2377  {
2378  Value *X = nullptr, *Y = nullptr;
2379  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2380  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2381  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2382  Value *orTrue = Builder.CreateOr(A, C);
2383  Value *orFalse = Builder.CreateOr(B, D);
2384  return SelectInst::Create(X, orTrue, orFalse);
2385  }
2386  }
2387 
2388  return nullptr;
2389 }
2390 
2391 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2392 /// can fold these early and efficiently by morphing an existing instruction.
2394  InstCombiner::BuilderTy &Builder) {
2395  assert(I.getOpcode() == Instruction::Xor);
2396  Value *Op0 = I.getOperand(0);
2397  Value *Op1 = I.getOperand(1);
2398  Value *A, *B;
2399 
2400  // There are 4 commuted variants for each of the basic patterns.
2401 
2402  // (A & B) ^ (A | B) -> A ^ B
2403  // (A & B) ^ (B | A) -> A ^ B
2404  // (A | B) ^ (A & B) -> A ^ B
2405  // (A | B) ^ (B & A) -> A ^ B
2406  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2407  m_c_Or(m_Deferred(A), m_Deferred(B))))) {
2408  I.setOperand(0, A);
2409  I.setOperand(1, B);
2410  return &I;
2411  }
2412 
2413  // (A | ~B) ^ (~A | B) -> A ^ B
2414  // (~B | A) ^ (~A | B) -> A ^ B
2415  // (~A | B) ^ (A | ~B) -> A ^ B
2416  // (B | ~A) ^ (A | ~B) -> A ^ B
2417  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2418  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2419  I.setOperand(0, A);
2420  I.setOperand(1, B);
2421  return &I;
2422  }
2423 
2424  // (A & ~B) ^ (~A & B) -> A ^ B
2425  // (~B & A) ^ (~A & B) -> A ^ B
2426  // (~A & B) ^ (A & ~B) -> A ^ B
2427  // (B & ~A) ^ (A & ~B) -> A ^ B
2428  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2429  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2430  I.setOperand(0, A);
2431  I.setOperand(1, B);
2432  return &I;
2433  }
2434 
2435  // For the remaining cases we need to get rid of one of the operands.
2436  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2437  return nullptr;
2438 
2439  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2440  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2441  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2442  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2443  // Complexity sorting ensures the not will be on the right side.
2444  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2445  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2446  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2447  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2448  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2449 
2450  return nullptr;
2451 }
2452 
2453 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
2454  if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2455  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2456  LHS->getOperand(1) == RHS->getOperand(0))
2457  LHS->swapOperands();
2458  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2459  LHS->getOperand(1) == RHS->getOperand(1)) {
2460  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2461  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2462  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2463  bool isSigned = LHS->isSigned() || RHS->isSigned();
2464  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
2465  }
2466  }
2467 
2468  // TODO: This can be generalized to compares of non-signbits using
2469  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
2470  // foldLogOpOfMaskedICmps().
2471  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2472  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
2473  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
2474  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
2475  LHS0->getType() == RHS0->getType() &&
2476  LHS0->getType()->isIntOrIntVectorTy()) {
2477  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
2478  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
2479  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2480  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
2481  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2482  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
2483  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
2484  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
2485  }
2486  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
2487  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
2488  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2489  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
2490  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2491  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
2492  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
2493  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
2494  }
2495  }
2496 
2497  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2498  // into those logic ops. That is, try to turn this into an and-of-icmps
2499  // because we have many folds for that pattern.
2500  //
2501  // This is based on a truth table definition of xor:
2502  // X ^ Y --> (X | Y) & !(X & Y)
2503  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2504  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2505  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2506  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2507  // TODO: Independently handle cases where the 'and' side is a constant.
2508  if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
2509  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
2510  RHS->setPredicate(RHS->getInversePredicate());
2511  return Builder.CreateAnd(LHS, RHS);
2512  }
2513  if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
2514  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
2515  LHS->setPredicate(LHS->getInversePredicate());
2516  return Builder.CreateAnd(LHS, RHS);
2517  }
2518  }
2519  }
2520 
2521  return nullptr;
2522 }
2523 
2524 /// If we have a masked merge, in the canonical form of:
2525 /// (assuming that A only has one use.)
2526 /// | A | |B|
2527 /// ((x ^ y) & M) ^ y
2528 /// | D |
2529 /// * If M is inverted:
2530 /// | D |
2531 /// ((x ^ y) & ~M) ^ y
2532 /// We can canonicalize by swapping the final xor operand
2533 /// to eliminate the 'not' of the mask.
2534 /// ((x ^ y) & M) ^ x
2535 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
2536 /// because that shortens the dependency chain and improves analysis:
2537 /// (x & M) | (y & ~M)
2539  InstCombiner::BuilderTy &Builder) {
2540  Value *B, *X, *D;
2541  Value *M;
2542  if (!match(&I, m_c_Xor(m_Value(B),
2543  m_OneUse(m_c_And(
2545  m_Value(D)),
2546  m_Value(M))))))
2547  return nullptr;
2548 
2549  Value *NotM;
2550  if (match(M, m_Not(m_Value(NotM)))) {
2551  // De-invert the mask and swap the value in B part.
2552  Value *NewA = Builder.CreateAnd(D, NotM);
2553  return BinaryOperator::CreateXor(NewA, X);
2554  }
2555 
2556  Constant *C;
2557  if (D->hasOneUse() && match(M, m_Constant(C))) {
2558  // Unfold.
2559  Value *LHS = Builder.CreateAnd(X, C);
2560  Value *NotC = Builder.CreateNot(C);
2561  Value *RHS = Builder.CreateAnd(B, NotC);
2562  return BinaryOperator::CreateOr(LHS, RHS);
2563  }
2564 
2565  return nullptr;
2566 }
2567 
2568 // Transform
2569 // ~(x ^ y)
2570 // into:
2571 // (~x) ^ y
2572 // or into
2573 // x ^ (~y)
2575  InstCombiner::BuilderTy &Builder) {
2576  Value *X, *Y;
2577  // FIXME: one-use check is not needed in general, but currently we are unable
2578  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
2579  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
2580  return nullptr;
2581 
2582  // We only want to do the transform if it is free to do.
2583  if (IsFreeToInvert(X, X->hasOneUse())) {
2584  // Ok, good.
2585  } else if (IsFreeToInvert(Y, Y->hasOneUse())) {
2586  std::swap(X, Y);
2587  } else
2588  return nullptr;
2589 
2590  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
2591  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
2592 }
2593 
2594 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2595 // here. We should standardize that construct where it is needed or choose some
2596 // other way to ensure that commutated variants of patterns are not missed.
2598  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
2599  SQ.getWithInstruction(&I)))
2600  return replaceInstUsesWith(I, V);
2601 
2602  if (SimplifyAssociativeOrCommutative(I))
2603  return &I;
2604 
2605  if (Instruction *X = foldVectorBinop(I))
2606  return X;
2607 
2608  if (Instruction *NewXor = foldXorToXor(I, Builder))
2609  return NewXor;
2610 
2611  // (A&B)^(A&C) -> A&(B^C) etc
2612  if (Value *V = SimplifyUsingDistributiveLaws(I))
2613  return replaceInstUsesWith(I, V);
2614 
2615  // See if we can simplify any instructions used by the instruction whose sole
2616  // purpose is to compute bits we don't care about.
2617  if (SimplifyDemandedInstructionBits(I))
2618  return &I;
2619 
2620  if (Value *V = SimplifyBSwap(I, Builder))
2621  return replaceInstUsesWith(I, V);
2622 
2623  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2624 
2625  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
2626  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
2627  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
2628  // have already taken care of those cases.
2629  Value *M;
2630  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
2631  m_c_And(m_Deferred(M), m_Value()))))
2632  return BinaryOperator::CreateOr(Op0, Op1);
2633 
2634  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
2635  Value *X, *Y;
2636 
2637  // We must eliminate the and/or (one-use) for these transforms to not increase
2638  // the instruction count.
2639  // ~(~X & Y) --> (X | ~Y)
2640  // ~(Y & ~X) --> (X | ~Y)
2641  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
2642  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2643  return BinaryOperator::CreateOr(X, NotY);
2644  }
2645  // ~(~X | Y) --> (X & ~Y)
2646  // ~(Y | ~X) --> (X & ~Y)
2647  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
2648  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2649  return BinaryOperator::CreateAnd(X, NotY);
2650  }
2651 
2652  if (Instruction *Xor = visitMaskedMerge(I, Builder))
2653  return Xor;
2654 
2655  // Is this a 'not' (~) fed by a binary operator?
2656  BinaryOperator *NotVal;
2657  if (match(&I, m_Not(m_BinOp(NotVal)))) {
2658  if (NotVal->getOpcode() == Instruction::And ||
2659  NotVal->getOpcode() == Instruction::Or) {
2660  // Apply DeMorgan's Law when inverts are free:
2661  // ~(X & Y) --> (~X | ~Y)
2662  // ~(X | Y) --> (~X & ~Y)
2663  if (IsFreeToInvert(NotVal->getOperand(0),
2664  NotVal->getOperand(0)->hasOneUse()) &&
2665  IsFreeToInvert(NotVal->getOperand(1),
2666  NotVal->getOperand(1)->hasOneUse())) {
2667  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
2668  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
2669  if (NotVal->getOpcode() == Instruction::And)
2670  return BinaryOperator::CreateOr(NotX, NotY);
2671  return BinaryOperator::CreateAnd(NotX, NotY);
2672  }
2673  }
2674 
2675  // ~(X - Y) --> ~X + Y
2676  if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
2677  if (isa<Constant>(X) || NotVal->hasOneUse())
2678  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
2679 
2680  // ~(~X >>s Y) --> (X >>s Y)
2681  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
2682  return BinaryOperator::CreateAShr(X, Y);
2683 
2684  // If we are inverting a right-shifted constant, we may be able to eliminate
2685  // the 'not' by inverting the constant and using the opposite shift type.
2686  // Canonicalization rules ensure that only a negative constant uses 'ashr',
2687  // but we must check that in case that transform has not fired yet.
2688 
2689  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
2690  Constant *C;
2691  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
2692  match(C, m_Negative()))
2693  return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
2694 
2695  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
2696  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
2697  match(C, m_NonNegative()))
2698  return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
2699 
2700  // ~(X + C) --> -(C + 1) - X
2701  if (match(Op0, m_Add(m_Value(X), m_Constant(C))))
2702  return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X);
2703  }
2704 
2705  // Use DeMorgan and reassociation to eliminate a 'not' op.
2706  Constant *C1;
2707  if (match(Op1, m_Constant(C1))) {
2708  Constant *C2;
2709  if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
2710  // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
2711  Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2));
2712  return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
2713  }
2714  if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
2715  // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
2716  Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2));
2717  return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
2718  }
2719  }
2720 
2721  // not (cmp A, B) = !cmp A, B
2722  CmpInst::Predicate Pred;
2723  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
2724  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
2725  return replaceInstUsesWith(I, Op0);
2726  }
2727 
2728  {
2729  const APInt *RHSC;
2730  if (match(Op1, m_APInt(RHSC))) {
2731  Value *X;
2732  const APInt *C;
2733  if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X)))) {
2734  // (C - X) ^ signmask -> (C + signmask - X)
2735  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2736  return BinaryOperator::CreateSub(NewC, X);
2737  }
2738  if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C)))) {
2739  // (X + C) ^ signmask -> (X + C + signmask)
2740  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2741  return BinaryOperator::CreateAdd(X, NewC);
2742  }
2743 
2744  // (X|C1)^C2 -> X^(C1^C2) iff X&~C1 == 0
2745  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
2746  MaskedValueIsZero(X, *C, 0, &I)) {
2747  Constant *NewC = ConstantInt::get(I.getType(), *C ^ *RHSC);
2748  Worklist.Add(cast<Instruction>(Op0));
2749  I.setOperand(0, X);
2750  I.setOperand(1, NewC);
2751  return &I;
2752  }
2753  }
2754  }
2755 
2756  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
2757  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2758  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2759  if (Op0I->getOpcode() == Instruction::LShr) {
2760  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
2761  // E1 = "X ^ C1"
2762  BinaryOperator *E1;
2763  ConstantInt *C1;
2764  if (Op0I->hasOneUse() &&
2765  (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
2766  E1->getOpcode() == Instruction::Xor &&
2767  (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
2768  // fold (C1 >> C2) ^ C3
2769  ConstantInt *C2 = Op0CI, *C3 = RHSC;
2770  APInt FoldConst = C1->getValue().lshr(C2->getValue());
2771  FoldConst ^= C3->getValue();
2772  // Prepare the two operands.
2773  Value *Opnd0 = Builder.CreateLShr(E1->getOperand(0), C2);
2774  Opnd0->takeName(Op0I);
2775  cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
2776  Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
2777 
2778  return BinaryOperator::CreateXor(Opnd0, FoldVal);
2779  }
2780  }
2781  }
2782  }
2783  }
2784 
2785  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2786  return FoldedLogic;
2787 
2788  // Y ^ (X | Y) --> X & ~Y
2789  // Y ^ (Y | X) --> X & ~Y
2790  if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
2791  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
2792  // (X | Y) ^ Y --> X & ~Y
2793  // (Y | X) ^ Y --> X & ~Y
2794  if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
2795  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
2796 
2797  // Y ^ (X & Y) --> ~X & Y
2798  // Y ^ (Y & X) --> ~X & Y
2799  if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
2800  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
2801  // (X & Y) ^ Y --> ~X & Y
2802  // (Y & X) ^ Y --> ~X & Y
2803  // Canonical form is (X & C) ^ C; don't touch that.
2804  // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
2805  // be fixed to prefer that (otherwise we get infinite looping).
2806  if (!match(Op1, m_Constant()) &&
2807  match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
2808  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
2809 
2810  Value *A, *B, *C;
2811  // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
2812  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
2813  m_OneUse(m_c_Or(m_Deferred(A), m_Value(C))))))
2814  return BinaryOperator::CreateXor(
2815  Builder.CreateAnd(Builder.CreateNot(A), C), B);
2816 
2817  // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
2818  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
2819  m_OneUse(m_c_Or(m_Deferred(B), m_Value(C))))))
2820  return BinaryOperator::CreateXor(
2821  Builder.CreateAnd(Builder.CreateNot(B), C), A);
2822 
2823  // (A & B) ^ (A ^ B) -> (A | B)
2824  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2825  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
2826  return BinaryOperator::CreateOr(A, B);
2827  // (A ^ B) ^ (A & B) -> (A | B)
2828  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2829  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2830  return BinaryOperator::CreateOr(A, B);
2831 
2832  // (A & ~B) ^ ~A -> ~(A & B)
2833  // (~B & A) ^ ~A -> ~(A & B)
2834  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
2835  match(Op1, m_Not(m_Specific(A))))
2836  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
2837 
2838  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
2839  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
2840  if (Value *V = foldXorOfICmps(LHS, RHS))
2841  return replaceInstUsesWith(I, V);
2842 
2843  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
2844  return CastedXor;
2845 
2846  // Canonicalize a shifty way to code absolute value to the common pattern.
2847  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
2848  // We're relying on the fact that we only do this transform when the shift has
2849  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
2850  // instructions).
2851  if (Op0->hasNUses(2))
2852  std::swap(Op0, Op1);
2853 
2854  const APInt *ShAmt;
2855  Type *Ty = I.getType();
2856  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2857  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2858  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
2859  // B = ashr i32 A, 31 ; smear the sign bit
2860  // xor (add A, B), B ; add -1 and flip bits if negative
2861  // --> (A < 0) ? -A : A
2862  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
2863  // Copy the nuw/nsw flags from the add to the negate.
2864  auto *Add = cast<BinaryOperator>(Op0);
2865  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
2866  Add->hasNoSignedWrap());
2867  return SelectInst::Create(Cmp, Neg, A);
2868  }
2869 
2870  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
2871  //
2872  // %notx = xor i32 %x, -1
2873  // %cmp1 = icmp sgt i32 %notx, %y
2874  // %smax = select i1 %cmp1, i32 %notx, i32 %y
2875  // %res = xor i32 %smax, -1
2876  // =>
2877  // %noty = xor i32 %y, -1
2878  // %cmp2 = icmp slt %x, %noty
2879  // %res = select i1 %cmp2, i32 %x, i32 %noty
2880  //
2881  // Same is applicable for smin/umax/umin.
2882  if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) {
2883  Value *LHS, *RHS;
2884  SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
2886  // It's possible we get here before the not has been simplified, so make
2887  // sure the input to the not isn't freely invertible.
2888  if (match(LHS, m_Not(m_Value(X))) && !IsFreeToInvert(X, X->hasOneUse())) {
2889  Value *NotY = Builder.CreateNot(RHS);
2890  return SelectInst::Create(
2891  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
2892  }
2893 
2894  // It's possible we get here before the not has been simplified, so make
2895  // sure the input to the not isn't freely invertible.
2896  if (match(RHS, m_Not(m_Value(Y))) && !IsFreeToInvert(Y, Y->hasOneUse())) {
2897  Value *NotX = Builder.CreateNot(LHS);
2898  return SelectInst::Create(
2899  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y);
2900  }
2901 
2902  // If both sides are freely invertible, then we can get rid of the xor
2903  // completely.
2904  if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
2905  IsFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) {
2906  Value *NotLHS = Builder.CreateNot(LHS);
2907  Value *NotRHS = Builder.CreateNot(RHS);
2908  return SelectInst::Create(
2909  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
2910  NotLHS, NotRHS);
2911  }
2912  }
2913  }
2914 
2915  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
2916  return NewXor;
2917 
2918  return nullptr;
2919 }
const NoneType None
Definition: None.h:24
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:725
uint64_t CallInst * C
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, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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
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:1858
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:622
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:1258
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
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:1578
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:899
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:327
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:1764
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1160
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:677
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:858
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:683
unsigned less than
Definition: InstrTypes.h:682
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:755
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:663
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:673
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:169
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:917
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:1294
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:668
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:667
bool isSigned() const
Definition: InstrTypes.h:826
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:737
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, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined. ...
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:755
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:364
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:743
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:664
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, bool UseInstrInfo=true)
Return true if &#39;V & Mask&#39; is known to be zero.
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:974
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:1641
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:617
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
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:1021
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:1142
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:1866
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:749
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N users or more.
Definition: Value.cpp:140
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:731
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:1913
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:743
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:657
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:666
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:674
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:672
#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:684
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:661
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:671
SelectPatternFlavor
Specific patterns of select instructions we can match.
signed less than
Definition: InstrTypes.h:686
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:624
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:736
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:941
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
signed less or equal
Definition: InstrTypes.h:687
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)
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2167
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:731
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:307
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:681
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
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:665
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:669
APInt byteSwap() const
Definition: APInt.cpp:618
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1124
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:660
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:670
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:680
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:771
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:2711
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:662
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).
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:659
signed greater or equal
Definition: InstrTypes.h:685
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:990
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:1883