LLVM  7.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 /// Fold (icmp)&(icmp) if possible.
902 Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
903  Instruction &CxtI) {
904  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
905  // if K1 and K2 are a one-bit mask.
906  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, true, CxtI))
907  return V;
908 
909  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
910 
911  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
912  if (PredicatesFoldable(PredL, PredR)) {
913  if (LHS->getOperand(0) == RHS->getOperand(1) &&
914  LHS->getOperand(1) == RHS->getOperand(0))
915  LHS->swapOperands();
916  if (LHS->getOperand(0) == RHS->getOperand(0) &&
917  LHS->getOperand(1) == RHS->getOperand(1)) {
918  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
919  unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
920  bool isSigned = LHS->isSigned() || RHS->isSigned();
921  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
922  }
923  }
924 
925  // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
926  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
927  return V;
928 
929  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
930  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
931  return V;
932 
933  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
934  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
935  return V;
936 
937  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
938  return V;
939 
940  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
941  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
942  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
943  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
944  if (!LHSC || !RHSC)
945  return nullptr;
946 
947  if (LHSC == RHSC && PredL == PredR) {
948  // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
949  // where C is a power of 2 or
950  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
951  if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
952  (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
953  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
954  return Builder.CreateICmp(PredL, NewOr, LHSC);
955  }
956  }
957 
958  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
959  // where CMAX is the all ones value for the truncated type,
960  // iff the lower bits of C2 and CA are zero.
961  if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
962  RHS->hasOneUse()) {
963  Value *V;
964  ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
965 
966  // (trunc x) == C1 & (and x, CA) == C2
967  // (and x, CA) == C2 & (trunc x) == C1
968  if (match(RHS0, m_Trunc(m_Value(V))) &&
969  match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
970  SmallC = RHSC;
971  BigC = LHSC;
972  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
973  match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
974  SmallC = LHSC;
975  BigC = RHSC;
976  }
977 
978  if (SmallC && BigC) {
979  unsigned BigBitSize = BigC->getType()->getBitWidth();
980  unsigned SmallBitSize = SmallC->getType()->getBitWidth();
981 
982  // Check that the low bits are zero.
983  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
984  if ((Low & AndC->getValue()).isNullValue() &&
985  (Low & BigC->getValue()).isNullValue()) {
986  Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue());
987  APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
988  Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
989  return Builder.CreateICmp(PredL, NewAnd, NewVal);
990  }
991  }
992  }
993 
994  // From here on, we only handle:
995  // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
996  if (LHS0 != RHS0)
997  return nullptr;
998 
999  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1000  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1001  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1002  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1003  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1004  return nullptr;
1005 
1006  // We can't fold (ugt x, C) & (sgt x, C2).
1007  if (!PredicatesFoldable(PredL, PredR))
1008  return nullptr;
1009 
1010  // Ensure that the larger constant is on the RHS.
1011  bool ShouldSwap;
1012  if (CmpInst::isSigned(PredL) ||
1013  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1014  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1015  else
1016  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1017 
1018  if (ShouldSwap) {
1019  std::swap(LHS, RHS);
1020  std::swap(LHSC, RHSC);
1021  std::swap(PredL, PredR);
1022  }
1023 
1024  // At this point, we know we have two icmp instructions
1025  // comparing a value against two constants and and'ing the result
1026  // together. Because of the above check, we know that we only have
1027  // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
1028  // (from the icmp folding check above), that the two constants
1029  // are not equal and that the larger constant is on the RHS
1030  assert(LHSC != RHSC && "Compares not folded above?");
1031 
1032  switch (PredL) {
1033  default:
1034  llvm_unreachable("Unknown integer condition code!");
1035  case ICmpInst::ICMP_NE:
1036  switch (PredR) {
1037  default:
1038  llvm_unreachable("Unknown integer condition code!");
1039  case ICmpInst::ICMP_ULT:
1040  if (LHSC == SubOne(RHSC)) // (X != 13 & X u< 14) -> X < 13
1041  return Builder.CreateICmpULT(LHS0, LHSC);
1042  if (LHSC->isZero()) // (X != 0 & X u< 14) -> X-1 u< 13
1043  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1044  false, true);
1045  break; // (X != 13 & X u< 15) -> no change
1046  case ICmpInst::ICMP_SLT:
1047  if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13
1048  return Builder.CreateICmpSLT(LHS0, LHSC);
1049  break; // (X != 13 & X s< 15) -> no change
1050  case ICmpInst::ICMP_NE:
1051  // Potential folds for this case should already be handled.
1052  break;
1053  }
1054  break;
1055  case ICmpInst::ICMP_UGT:
1056  switch (PredR) {
1057  default:
1058  llvm_unreachable("Unknown integer condition code!");
1059  case ICmpInst::ICMP_NE:
1060  if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14
1061  return Builder.CreateICmp(PredL, LHS0, RHSC);
1062  break; // (X u> 13 & X != 15) -> no change
1063  case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
1064  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1065  false, true);
1066  }
1067  break;
1068  case ICmpInst::ICMP_SGT:
1069  switch (PredR) {
1070  default:
1071  llvm_unreachable("Unknown integer condition code!");
1072  case ICmpInst::ICMP_NE:
1073  if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14
1074  return Builder.CreateICmp(PredL, LHS0, RHSC);
1075  break; // (X s> 13 & X != 15) -> no change
1076  case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
1077  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
1078  true);
1079  }
1080  break;
1081  }
1082 
1083  return nullptr;
1084 }
1085 
1086 Value *InstCombiner::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
1087  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1088  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1089  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1090 
1091  if (LHS0 == RHS1 && RHS0 == LHS1) {
1092  // Swap RHS operands to match LHS.
1093  PredR = FCmpInst::getSwappedPredicate(PredR);
1094  std::swap(RHS0, RHS1);
1095  }
1096 
1097  // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1098  // Suppose the relation between x and y is R, where R is one of
1099  // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1100  // testing the desired relations.
1101  //
1102  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1103  // bool(R & CC0) && bool(R & CC1)
1104  // = bool((R & CC0) & (R & CC1))
1105  // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1106  //
1107  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1108  // bool(R & CC0) || bool(R & CC1)
1109  // = bool((R & CC0) | (R & CC1))
1110  // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1111  if (LHS0 == RHS0 && LHS1 == RHS1) {
1112  unsigned FCmpCodeL = getFCmpCode(PredL);
1113  unsigned FCmpCodeR = getFCmpCode(PredR);
1114  unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1115  return getFCmpValue(NewPred, LHS0, LHS1, Builder);
1116  }
1117 
1118  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1119  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1120  if (LHS0->getType() != RHS0->getType())
1121  return nullptr;
1122 
1123  // FCmp canonicalization ensures that (fcmp ord/uno X, X) and
1124  // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0).
1125  if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP()))
1126  // Ignore the constants because they are obviously not NANs:
1127  // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y)
1128  // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y)
1129  return Builder.CreateFCmp(PredL, LHS0, RHS0);
1130  }
1131 
1132  return nullptr;
1133 }
1134 
1135 /// Match De Morgan's Laws:
1136 /// (~A & ~B) == (~(A | B))
1137 /// (~A | ~B) == (~(A & B))
1139  InstCombiner::BuilderTy &Builder) {
1140  auto Opcode = I.getOpcode();
1141  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1142  "Trying to match De Morgan's Laws with something other than and/or");
1143 
1144  // Flip the logic operation.
1145  Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1146 
1147  Value *A, *B;
1148  if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) &&
1149  match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) &&
1150  !IsFreeToInvert(A, A->hasOneUse()) &&
1151  !IsFreeToInvert(B, B->hasOneUse())) {
1152  Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan");
1153  return BinaryOperator::CreateNot(AndOr);
1154  }
1155 
1156  return nullptr;
1157 }
1158 
1159 bool InstCombiner::shouldOptimizeCast(CastInst *CI) {
1160  Value *CastSrc = CI->getOperand(0);
1161 
1162  // Noop casts and casts of constants should be eliminated trivially.
1163  if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1164  return false;
1165 
1166  // If this cast is paired with another cast that can be eliminated, we prefer
1167  // to have it eliminated.
1168  if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1169  if (isEliminableCastPair(PrecedingCI, CI))
1170  return false;
1171 
1172  return true;
1173 }
1174 
1175 /// Fold {and,or,xor} (cast X), C.
1177  InstCombiner::BuilderTy &Builder) {
1178  Constant *C = dyn_cast<Constant>(Logic.getOperand(1));
1179  if (!C)
1180  return nullptr;
1181 
1182  auto LogicOpc = Logic.getOpcode();
1183  Type *DestTy = Logic.getType();
1184  Type *SrcTy = Cast->getSrcTy();
1185 
1186  // Move the logic operation ahead of a zext or sext if the constant is
1187  // unchanged in the smaller source type. Performing the logic in a smaller
1188  // type may provide more information to later folds, and the smaller logic
1189  // instruction may be cheaper (particularly in the case of vectors).
1190  Value *X;
1191  if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1192  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1193  Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1194  if (ZextTruncC == C) {
1195  // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1196  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1197  return new ZExtInst(NewOp, DestTy);
1198  }
1199  }
1200 
1201  if (match(Cast, m_OneUse(m_SExt(m_Value(X))))) {
1202  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1203  Constant *SextTruncC = ConstantExpr::getSExt(TruncC, DestTy);
1204  if (SextTruncC == C) {
1205  // LogicOpc (sext X), C --> sext (LogicOpc X, C)
1206  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1207  return new SExtInst(NewOp, DestTy);
1208  }
1209  }
1210 
1211  return nullptr;
1212 }
1213 
1214 /// Fold {and,or,xor} (cast X), Y.
1215 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
1216  auto LogicOpc = I.getOpcode();
1217  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1218 
1219  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1220  CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1221  if (!Cast0)
1222  return nullptr;
1223 
1224  // This must be a cast from an integer or integer vector source type to allow
1225  // transformation of the logic operation to the source type.
1226  Type *DestTy = I.getType();
1227  Type *SrcTy = Cast0->getSrcTy();
1228  if (!SrcTy->isIntOrIntVectorTy())
1229  return nullptr;
1230 
1231  if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1232  return Ret;
1233 
1234  CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1235  if (!Cast1)
1236  return nullptr;
1237 
1238  // Both operands of the logic operation are casts. The casts must be of the
1239  // same type for reduction.
1240  auto CastOpcode = Cast0->getOpcode();
1241  if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
1242  return nullptr;
1243 
1244  Value *Cast0Src = Cast0->getOperand(0);
1245  Value *Cast1Src = Cast1->getOperand(0);
1246 
1247  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1248  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1249  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1250  I.getName());
1251  return CastInst::Create(CastOpcode, NewOp, DestTy);
1252  }
1253 
1254  // For now, only 'and'/'or' have optimizations after this.
1255  if (LogicOpc == Instruction::Xor)
1256  return nullptr;
1257 
1258  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1259  // cast is otherwise not optimizable. This happens for vector sexts.
1260  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1261  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1262  if (ICmp0 && ICmp1) {
1263  Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I)
1264  : foldOrOfICmps(ICmp0, ICmp1, I);
1265  if (Res)
1266  return CastInst::Create(CastOpcode, Res, DestTy);
1267  return nullptr;
1268  }
1269 
1270  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1271  // cast is otherwise not optimizable. This happens for vector sexts.
1272  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1273  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1274  if (FCmp0 && FCmp1)
1275  if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1276  return CastInst::Create(CastOpcode, R, DestTy);
1277 
1278  return nullptr;
1279 }
1280 
1282  InstCombiner::BuilderTy &Builder) {
1283  assert(I.getOpcode() == Instruction::And);
1284  Value *Op0 = I.getOperand(0);
1285  Value *Op1 = I.getOperand(1);
1286  Value *A, *B;
1287 
1288  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1289  // (A | B) & ~(A & B) --> A ^ B
1290  // (A | B) & ~(B & A) --> A ^ B
1291  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1292  m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
1293  return BinaryOperator::CreateXor(A, B);
1294 
1295  // (A | ~B) & (~A | B) --> ~(A ^ B)
1296  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1297  // (~B | A) & (~A | B) --> ~(A ^ B)
1298  // (~B | A) & (B | ~A) --> ~(A ^ B)
1299  if (Op0->hasOneUse() || Op1->hasOneUse())
1300  if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
1301  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
1302  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1303 
1304  return nullptr;
1305 }
1306 
1308  InstCombiner::BuilderTy &Builder) {
1309  assert(I.getOpcode() == Instruction::Or);
1310  Value *Op0 = I.getOperand(0);
1311  Value *Op1 = I.getOperand(1);
1312  Value *A, *B;
1313 
1314  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1315  // (A & B) | ~(A | B) --> ~(A ^ B)
1316  // (A & B) | ~(B | A) --> ~(A ^ B)
1317  if (Op0->hasOneUse() || Op1->hasOneUse())
1318  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1319  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1320  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1321 
1322  // (A & ~B) | (~A & B) --> A ^ B
1323  // (A & ~B) | (B & ~A) --> A ^ B
1324  // (~B & A) | (~A & B) --> A ^ B
1325  // (~B & A) | (B & ~A) --> A ^ B
1326  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1327  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1328  return BinaryOperator::CreateXor(A, B);
1329 
1330  return nullptr;
1331 }
1332 
1333 /// Return true if a constant shift amount is always less than the specified
1334 /// bit-width. If not, the shift could create poison in the narrower type.
1335 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1336  if (auto *ScalarC = dyn_cast<ConstantInt>(C))
1337  return ScalarC->getZExtValue() < BitWidth;
1338 
1339  if (C->getType()->isVectorTy()) {
1340  // Check each element of a constant vector.
1341  unsigned NumElts = C->getType()->getVectorNumElements();
1342  for (unsigned i = 0; i != NumElts; ++i) {
1343  Constant *Elt = C->getAggregateElement(i);
1344  if (!Elt)
1345  return false;
1346  if (isa<UndefValue>(Elt))
1347  continue;
1348  auto *CI = dyn_cast<ConstantInt>(Elt);
1349  if (!CI || CI->getZExtValue() >= BitWidth)
1350  return false;
1351  }
1352  return true;
1353  }
1354 
1355  // The constant is a constant expression or unknown.
1356  return false;
1357 }
1358 
1359 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1360 /// a common zext operand: and (binop (zext X), C), (zext X).
1361 Instruction *InstCombiner::narrowMaskedBinOp(BinaryOperator &And) {
1362  // This transform could also apply to {or, and, xor}, but there are better
1363  // folds for those cases, so we don't expect those patterns here. AShr is not
1364  // handled because it should always be transformed to LShr in this sequence.
1365  // The subtract transform is different because it has a constant on the left.
1366  // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1367  Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1368  Constant *C;
1369  if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1370  !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1371  !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1372  !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1373  !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1374  return nullptr;
1375 
1376  Value *X;
1377  if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1378  return nullptr;
1379 
1380  Type *Ty = And.getType();
1381  if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1382  return nullptr;
1383 
1384  // If we're narrowing a shift, the shift amount must be safe (less than the
1385  // width) in the narrower type. If the shift amount is greater, instsimplify
1386  // usually handles that case, but we can't guarantee/assert it.
1387  Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1388  if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1390  return nullptr;
1391 
1392  // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1393  // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1394  Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1395  Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1396  : Builder.CreateBinOp(Opc, X, NewC);
1397  return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1398 }
1399 
1400 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1401 // here. We should standardize that construct where it is needed or choose some
1402 // other way to ensure that commutated variants of patterns are not missed.
1404  bool Changed = SimplifyAssociativeOrCommutative(I);
1405  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1406  if (Value *V = SimplifyAndInst(Op0, Op1, SQ.getWithInstruction(&I)))
1407  return replaceInstUsesWith(I, V);
1408 
1409  if (Instruction *X = foldShuffledBinop(I))
1410  return X;
1411 
1412  // See if we can simplify any instructions used by the instruction whose sole
1413  // purpose is to compute bits we don't care about.
1414  if (SimplifyDemandedInstructionBits(I))
1415  return &I;
1416 
1417  // Do this before using distributive laws to catch simple and/or/not patterns.
1418  if (Instruction *Xor = foldAndToXor(I, Builder))
1419  return Xor;
1420 
1421  // (A|B)&(A|C) -> A|(B&C) etc
1422  if (Value *V = SimplifyUsingDistributiveLaws(I))
1423  return replaceInstUsesWith(I, V);
1424 
1425  if (Value *V = SimplifyBSwap(I, Builder))
1426  return replaceInstUsesWith(I, V);
1427 
1428  const APInt *C;
1429  if (match(Op1, m_APInt(C))) {
1430  Value *X, *Y;
1431  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
1432  C->isOneValue()) {
1433  // (1 << X) & 1 --> zext(X == 0)
1434  // (1 >> X) & 1 --> zext(X == 0)
1435  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(I.getType(), 0));
1436  return new ZExtInst(IsZero, I.getType());
1437  }
1438 
1439  const APInt *XorC;
1440  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
1441  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1442  Constant *NewC = ConstantInt::get(I.getType(), *C & *XorC);
1443  Value *And = Builder.CreateAnd(X, Op1);
1444  And->takeName(Op0);
1445  return BinaryOperator::CreateXor(And, NewC);
1446  }
1447 
1448  const APInt *OrC;
1449  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
1450  // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
1451  // NOTE: This reduces the number of bits set in the & mask, which
1452  // can expose opportunities for store narrowing for scalars.
1453  // NOTE: SimplifyDemandedBits should have already removed bits from C1
1454  // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
1455  // above, but this feels safer.
1456  APInt Together = *C & *OrC;
1457  Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(),
1458  Together ^ *C));
1459  And->takeName(Op0);
1460  return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(),
1461  Together));
1462  }
1463 
1464  // If the mask is only needed on one incoming arm, push the 'and' op up.
1465  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
1466  match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
1467  APInt NotAndMask(~(*C));
1468  BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
1469  if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
1470  // Not masking anything out for the LHS, move mask to RHS.
1471  // and ({x}or X, Y), C --> {x}or X, (and Y, C)
1472  Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
1473  return BinaryOperator::Create(BinOp, X, NewRHS);
1474  }
1475  if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
1476  // Not masking anything out for the RHS, move mask to LHS.
1477  // and ({x}or X, Y), C --> {x}or (and X, C), Y
1478  Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
1479  return BinaryOperator::Create(BinOp, NewLHS, Y);
1480  }
1481  }
1482 
1483  }
1484 
1485  if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
1486  const APInt &AndRHSMask = AndRHS->getValue();
1487 
1488  // Optimize a variety of ((val OP C1) & C2) combinations...
1489  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1490  // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth
1491  // of X and OP behaves well when given trunc(C1) and X.
1492  switch (Op0I->getOpcode()) {
1493  default:
1494  break;
1495  case Instruction::Xor:
1496  case Instruction::Or:
1497  case Instruction::Mul:
1498  case Instruction::Add:
1499  case Instruction::Sub:
1500  Value *X;
1501  ConstantInt *C1;
1502  if (match(Op0I, m_c_BinOp(m_ZExt(m_Value(X)), m_ConstantInt(C1)))) {
1503  if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) {
1504  auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType());
1505  Value *BinOp;
1506  Value *Op0LHS = Op0I->getOperand(0);
1507  if (isa<ZExtInst>(Op0LHS))
1508  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), X, TruncC1);
1509  else
1510  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), TruncC1, X);
1511  auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType());
1512  auto *And = Builder.CreateAnd(BinOp, TruncC2);
1513  return new ZExtInst(And, I.getType());
1514  }
1515  }
1516  }
1517 
1518  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1519  if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1520  return Res;
1521  }
1522 
1523  // If this is an integer truncation, and if the source is an 'and' with
1524  // immediate, transform it. This frequently occurs for bitfield accesses.
1525  {
1526  Value *X = nullptr; ConstantInt *YC = nullptr;
1527  if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) {
1528  // Change: and (trunc (and X, YC) to T), C2
1529  // into : and (trunc X to T), trunc(YC) & C2
1530  // This will fold the two constants together, which may allow
1531  // other simplifications.
1532  Value *NewCast = Builder.CreateTrunc(X, I.getType(), "and.shrunk");
1533  Constant *C3 = ConstantExpr::getTrunc(YC, I.getType());
1534  C3 = ConstantExpr::getAnd(C3, AndRHS);
1535  return BinaryOperator::CreateAnd(NewCast, C3);
1536  }
1537  }
1538  }
1539 
1540  if (Instruction *Z = narrowMaskedBinOp(I))
1541  return Z;
1542 
1543  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
1544  return FoldedLogic;
1545 
1546  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1547  return DeMorgan;
1548 
1549  {
1550  Value *A = nullptr, *B = nullptr, *C = nullptr;
1551  // A&(A^B) => A & ~B
1552  {
1553  Value *tmpOp0 = Op0;
1554  Value *tmpOp1 = Op1;
1555  if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
1556  if (A == Op1 || B == Op1 ) {
1557  tmpOp1 = Op0;
1558  tmpOp0 = Op1;
1559  // Simplify below
1560  }
1561  }
1562 
1563  if (match(tmpOp1, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
1564  if (B == tmpOp0) {
1565  std::swap(A, B);
1566  }
1567  // Notice that the pattern (A&(~B)) is actually (A&(-1^B)), so if
1568  // A is originally -1 (or a vector of -1 and undefs), then we enter
1569  // an endless loop. By checking that A is non-constant we ensure that
1570  // we will never get to the loop.
1571  if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B
1572  return BinaryOperator::CreateAnd(A, Builder.CreateNot(B));
1573  }
1574  }
1575 
1576  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1577  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1578  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1579  if (Op1->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1580  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1581 
1582  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1583  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1584  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1585  if (Op0->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1586  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1587 
1588  // (A | B) & ((~A) ^ B) -> (A & B)
1589  // (A | B) & (B ^ (~A)) -> (A & B)
1590  // (B | A) & ((~A) ^ B) -> (A & B)
1591  // (B | A) & (B ^ (~A)) -> (A & B)
1592  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1593  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1594  return BinaryOperator::CreateAnd(A, B);
1595 
1596  // ((~A) ^ B) & (A | B) -> (A & B)
1597  // ((~A) ^ B) & (B | A) -> (A & B)
1598  // (B ^ (~A)) & (A | B) -> (A & B)
1599  // (B ^ (~A)) & (B | A) -> (A & B)
1600  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1601  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1602  return BinaryOperator::CreateAnd(A, B);
1603  }
1604 
1605  {
1606  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1607  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1608  if (LHS && RHS)
1609  if (Value *Res = foldAndOfICmps(LHS, RHS, I))
1610  return replaceInstUsesWith(I, Res);
1611 
1612  // TODO: Make this recursive; it's a little tricky because an arbitrary
1613  // number of 'and' instructions might have to be created.
1614  Value *X, *Y;
1615  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1616  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1617  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1618  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1619  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1620  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1621  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1622  }
1623  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1624  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1625  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1626  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1627  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1628  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1629  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1630  }
1631  }
1632 
1633  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
1634  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
1635  if (Value *Res = foldLogicOfFCmps(LHS, RHS, true))
1636  return replaceInstUsesWith(I, Res);
1637 
1638  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
1639  return CastedAnd;
1640 
1641  // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
1642  Value *A;
1643  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
1644  A->getType()->isIntOrIntVectorTy(1))
1645  return SelectInst::Create(A, Op1, Constant::getNullValue(I.getType()));
1646  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
1647  A->getType()->isIntOrIntVectorTy(1))
1648  return SelectInst::Create(A, Op0, Constant::getNullValue(I.getType()));
1649 
1650  return Changed ? &I : nullptr;
1651 }
1652 
1653 /// Given an OR instruction, check to see if this is a bswap idiom. If so,
1654 /// insert the new intrinsic and return it.
1655 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
1656  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1657 
1658  // Look through zero extends.
1659  if (Instruction *Ext = dyn_cast<ZExtInst>(Op0))
1660  Op0 = Ext->getOperand(0);
1661 
1662  if (Instruction *Ext = dyn_cast<ZExtInst>(Op1))
1663  Op1 = Ext->getOperand(0);
1664 
1665  // (A | B) | C and A | (B | C) -> bswap if possible.
1666  bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
1667  match(Op1, m_Or(m_Value(), m_Value()));
1668 
1669  // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible.
1670  bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1671  match(Op1, m_LogicalShift(m_Value(), m_Value()));
1672 
1673  // (A & B) | (C & D) -> bswap if possible.
1674  bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
1675  match(Op1, m_And(m_Value(), m_Value()));
1676 
1677  // (A << B) | (C & D) -> bswap if possible.
1678  // The bigger pattern here is ((A & C1) << C2) | ((B >> C2) & C1), which is a
1679  // part of the bswap idiom for specific values of C1, C2 (e.g. C1 = 16711935,
1680  // C2 = 8 for i32).
1681  // This pattern can occur when the operands of the 'or' are not canonicalized
1682  // for some reason (not having only one use, for example).
1683  bool OrOfAndAndSh = (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1684  match(Op1, m_And(m_Value(), m_Value()))) ||
1685  (match(Op0, m_And(m_Value(), m_Value())) &&
1686  match(Op1, m_LogicalShift(m_Value(), m_Value())));
1687 
1688  if (!OrOfOrs && !OrOfShifts && !OrOfAnds && !OrOfAndAndSh)
1689  return nullptr;
1690 
1692  if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
1693  return nullptr;
1694  Instruction *LastInst = Insts.pop_back_val();
1695  LastInst->removeFromParent();
1696 
1697  for (auto *Inst : Insts)
1698  Worklist.Add(Inst);
1699  return LastInst;
1700 }
1701 
1702 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
1704  unsigned NumElts = C1->getType()->getVectorNumElements();
1705  for (unsigned i = 0; i != NumElts; ++i) {
1706  Constant *EltC1 = C1->getAggregateElement(i);
1707  Constant *EltC2 = C2->getAggregateElement(i);
1708  if (!EltC1 || !EltC2)
1709  return false;
1710 
1711  // One element must be all ones, and the other must be all zeros.
1712  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
1713  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
1714  return false;
1715  }
1716  return true;
1717 }
1718 
1719 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
1720 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
1721 /// B, it can be used as the condition operand of a select instruction.
1723  InstCombiner::BuilderTy &Builder) {
1724  // If these are scalars or vectors of i1, A can be used directly.
1725  Type *Ty = A->getType();
1726  if (match(A, m_Not(m_Specific(B))) && Ty->isIntOrIntVectorTy(1))
1727  return A;
1728 
1729  // If A and B are sign-extended, look through the sexts to find the booleans.
1730  Value *Cond;
1731  Value *NotB;
1732  if (match(A, m_SExt(m_Value(Cond))) &&
1733  Cond->getType()->isIntOrIntVectorTy(1) &&
1734  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
1735  NotB = peekThroughBitcast(NotB, true);
1736  if (match(NotB, m_SExt(m_Specific(Cond))))
1737  return Cond;
1738  }
1739 
1740  // All scalar (and most vector) possibilities should be handled now.
1741  // Try more matches that only apply to non-splat constant vectors.
1742  if (!Ty->isVectorTy())
1743  return nullptr;
1744 
1745  // If both operands are constants, see if the constants are inverse bitmasks.
1746  Constant *AC, *BC;
1747  if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) &&
1748  areInverseVectorBitmasks(AC, BC)) {
1749  return Builder.CreateZExtOrTrunc(AC, CmpInst::makeCmpResultType(Ty));
1750  }
1751 
1752  // If both operands are xor'd with constants using the same sexted boolean
1753  // operand, see if the constants are inverse bitmasks.
1754  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) &&
1755  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) &&
1756  Cond->getType()->isIntOrIntVectorTy(1) &&
1757  areInverseVectorBitmasks(AC, BC)) {
1759  return Builder.CreateXor(Cond, AC);
1760  }
1761  return nullptr;
1762 }
1763 
1764 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
1765 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
1767  InstCombiner::BuilderTy &Builder) {
1768  // The potential condition of the select may be bitcasted. In that case, look
1769  // through its bitcast and the corresponding bitcast of the 'not' condition.
1770  Type *OrigType = A->getType();
1771  A = peekThroughBitcast(A, true);
1772  B = peekThroughBitcast(B, true);
1773 
1774  if (Value *Cond = getSelectCondition(A, B, Builder)) {
1775  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
1776  // The bitcasts will either all exist or all not exist. The builder will
1777  // not create unnecessary casts if the types already match.
1778  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
1779  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
1780  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
1781  return Builder.CreateBitCast(Select, OrigType);
1782  }
1783 
1784  return nullptr;
1785 }
1786 
1787 /// Fold (icmp)|(icmp) if possible.
1788 Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1789  Instruction &CxtI) {
1790  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
1791  // if K1 and K2 are a one-bit mask.
1792  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, false, CxtI))
1793  return V;
1794 
1795  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1796 
1797  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
1798  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
1799 
1800  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
1801  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
1802  // The original condition actually refers to the following two ranges:
1803  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
1804  // We can fold these two ranges if:
1805  // 1) C1 and C2 is unsigned greater than C3.
1806  // 2) The two ranges are separated.
1807  // 3) C1 ^ C2 is one-bit mask.
1808  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
1809  // This implies all values in the two ranges differ by exactly one bit.
1810 
1811  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
1812  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
1813  LHSC->getType() == RHSC->getType() &&
1814  LHSC->getValue() == (RHSC->getValue())) {
1815 
1816  Value *LAdd = LHS->getOperand(0);
1817  Value *RAdd = RHS->getOperand(0);
1818 
1819  Value *LAddOpnd, *RAddOpnd;
1820  ConstantInt *LAddC, *RAddC;
1821  if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddC))) &&
1822  match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddC))) &&
1823  LAddC->getValue().ugt(LHSC->getValue()) &&
1824  RAddC->getValue().ugt(LHSC->getValue())) {
1825 
1826  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
1827  if (LAddOpnd == RAddOpnd && DiffC.isPowerOf2()) {
1828  ConstantInt *MaxAddC = nullptr;
1829  if (LAddC->getValue().ult(RAddC->getValue()))
1830  MaxAddC = RAddC;
1831  else
1832  MaxAddC = LAddC;
1833 
1834  APInt RRangeLow = -RAddC->getValue();
1835  APInt RRangeHigh = RRangeLow + LHSC->getValue();
1836  APInt LRangeLow = -LAddC->getValue();
1837  APInt LRangeHigh = LRangeLow + LHSC->getValue();
1838  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
1839  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
1840  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
1841  : RRangeLow - LRangeLow;
1842 
1843  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
1844  RangeDiff.ugt(LHSC->getValue())) {
1845  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
1846 
1847  Value *NewAnd = Builder.CreateAnd(LAddOpnd, MaskC);
1848  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
1849  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
1850  }
1851  }
1852  }
1853  }
1854 
1855  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
1856  if (PredicatesFoldable(PredL, PredR)) {
1857  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1858  LHS->getOperand(1) == RHS->getOperand(0))
1859  LHS->swapOperands();
1860  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1861  LHS->getOperand(1) == RHS->getOperand(1)) {
1862  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1863  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
1864  bool isSigned = LHS->isSigned() || RHS->isSigned();
1865  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
1866  }
1867  }
1868 
1869  // handle (roughly):
1870  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
1871  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
1872  return V;
1873 
1874  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1875  if (LHS->hasOneUse() || RHS->hasOneUse()) {
1876  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
1877  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
1878  Value *A = nullptr, *B = nullptr;
1879  if (PredL == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero()) {
1880  B = LHS0;
1881  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS->getOperand(1))
1882  A = RHS0;
1883  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
1884  A = RHS->getOperand(1);
1885  }
1886  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
1887  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
1888  else if (PredR == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) {
1889  B = RHS0;
1890  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS->getOperand(1))
1891  A = LHS0;
1892  else if (PredL == ICmpInst::ICMP_UGT && LHS0 == RHS0)
1893  A = LHS->getOperand(1);
1894  }
1895  if (A && B)
1896  return Builder.CreateICmp(
1898  Builder.CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
1899  }
1900 
1901  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
1902  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
1903  return V;
1904 
1905  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
1906  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
1907  return V;
1908 
1909  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
1910  return V;
1911 
1912  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
1913  if (!LHSC || !RHSC)
1914  return nullptr;
1915 
1916  if (LHSC == RHSC && PredL == PredR) {
1917  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
1918  if (PredL == ICmpInst::ICMP_NE && LHSC->isZero()) {
1919  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
1920  return Builder.CreateICmp(PredL, NewOr, LHSC);
1921  }
1922  }
1923 
1924  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
1925  // iff C2 + CA == C1.
1926  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
1927  ConstantInt *AddC;
1928  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
1929  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
1930  return Builder.CreateICmpULE(LHS0, LHSC);
1931  }
1932 
1933  // From here on, we only handle:
1934  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
1935  if (LHS0 != RHS0)
1936  return nullptr;
1937 
1938  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1939  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1940  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1941  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1942  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1943  return nullptr;
1944 
1945  // We can't fold (ugt x, C) | (sgt x, C2).
1946  if (!PredicatesFoldable(PredL, PredR))
1947  return nullptr;
1948 
1949  // Ensure that the larger constant is on the RHS.
1950  bool ShouldSwap;
1951  if (CmpInst::isSigned(PredL) ||
1952  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1953  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1954  else
1955  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1956 
1957  if (ShouldSwap) {
1958  std::swap(LHS, RHS);
1959  std::swap(LHSC, RHSC);
1960  std::swap(PredL, PredR);
1961  }
1962 
1963  // At this point, we know we have two icmp instructions
1964  // comparing a value against two constants and or'ing the result
1965  // together. Because of the above check, we know that we only have
1966  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
1967  // icmp folding check above), that the two constants are not
1968  // equal.
1969  assert(LHSC != RHSC && "Compares not folded above?");
1970 
1971  switch (PredL) {
1972  default:
1973  llvm_unreachable("Unknown integer condition code!");
1974  case ICmpInst::ICMP_EQ:
1975  switch (PredR) {
1976  default:
1977  llvm_unreachable("Unknown integer condition code!");
1978  case ICmpInst::ICMP_EQ:
1979  // Potential folds for this case should already be handled.
1980  break;
1981  case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
1982  case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
1983  break;
1984  }
1985  break;
1986  case ICmpInst::ICMP_ULT:
1987  switch (PredR) {
1988  default:
1989  llvm_unreachable("Unknown integer condition code!");
1990  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
1991  break;
1992  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
1993  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
1994  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
1995  false, false);
1996  }
1997  break;
1998  case ICmpInst::ICMP_SLT:
1999  switch (PredR) {
2000  default:
2001  llvm_unreachable("Unknown integer condition code!");
2002  case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
2003  break;
2004  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
2005  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
2006  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
2007  false);
2008  }
2009  break;
2010  }
2011  return nullptr;
2012 }
2013 
2014 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2015 // here. We should standardize that construct where it is needed or choose some
2016 // other way to ensure that commutated variants of patterns are not missed.
2018  bool Changed = SimplifyAssociativeOrCommutative(I);
2019  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2020  if (Value *V = SimplifyOrInst(Op0, Op1, SQ.getWithInstruction(&I)))
2021  return replaceInstUsesWith(I, V);
2022 
2023  if (Instruction *X = foldShuffledBinop(I))
2024  return X;
2025 
2026  // See if we can simplify any instructions used by the instruction whose sole
2027  // purpose is to compute bits we don't care about.
2028  if (SimplifyDemandedInstructionBits(I))
2029  return &I;
2030 
2031  // Do this before using distributive laws to catch simple and/or/not patterns.
2032  if (Instruction *Xor = foldOrToXor(I, Builder))
2033  return Xor;
2034 
2035  // (A&B)|(A&C) -> A&(B|C) etc
2036  if (Value *V = SimplifyUsingDistributiveLaws(I))
2037  return replaceInstUsesWith(I, V);
2038 
2039  if (Value *V = SimplifyBSwap(I, Builder))
2040  return replaceInstUsesWith(I, V);
2041 
2042  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2043  return FoldedLogic;
2044 
2045  // Given an OR instruction, check to see if this is a bswap.
2046  if (Instruction *BSwap = MatchBSwap(I))
2047  return BSwap;
2048 
2049  {
2050  Value *A;
2051  const APInt *C;
2052  // (X^C)|Y -> (X|Y)^C iff Y&C == 0
2053  if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
2054  MaskedValueIsZero(Op1, *C, 0, &I)) {
2055  Value *NOr = Builder.CreateOr(A, Op1);
2056  NOr->takeName(Op0);
2057  return BinaryOperator::CreateXor(NOr,
2058  ConstantInt::get(NOr->getType(), *C));
2059  }
2060 
2061  // Y|(X^C) -> (X|Y)^C iff Y&C == 0
2062  if (match(Op1, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
2063  MaskedValueIsZero(Op0, *C, 0, &I)) {
2064  Value *NOr = Builder.CreateOr(A, Op0);
2065  NOr->takeName(Op0);
2066  return BinaryOperator::CreateXor(NOr,
2067  ConstantInt::get(NOr->getType(), *C));
2068  }
2069  }
2070 
2071  Value *A, *B;
2072 
2073  // (A & C)|(B & D)
2074  Value *C = nullptr, *D = nullptr;
2075  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2076  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2079  if (C1 && C2) { // (A & C1)|(B & C2)
2080  Value *V1 = nullptr, *V2 = nullptr;
2081  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2082  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2083  // iff (C1&C2) == 0 and (N&~C1) == 0
2084  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2085  ((V1 == B &&
2086  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2087  (V2 == B &&
2088  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2089  return BinaryOperator::CreateAnd(A,
2090  Builder.getInt(C1->getValue()|C2->getValue()));
2091  // Or commutes, try both ways.
2092  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2093  ((V1 == A &&
2094  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2095  (V2 == A &&
2096  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2097  return BinaryOperator::CreateAnd(B,
2098  Builder.getInt(C1->getValue()|C2->getValue()));
2099 
2100  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2101  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2102  ConstantInt *C3 = nullptr, *C4 = nullptr;
2103  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2104  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2105  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2106  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2107  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2108  return BinaryOperator::CreateAnd(V2,
2109  Builder.getInt(C1->getValue()|C2->getValue()));
2110  }
2111  }
2112 
2113  if (C1->getValue() == ~C2->getValue()) {
2114  Value *X;
2115 
2116  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2117  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2118  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2119  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2120  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2121  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2122 
2123  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2124  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2125  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2126  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2127  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2128  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2129  }
2130  }
2131 
2132  // Don't try to form a select if it's unlikely that we'll get rid of at
2133  // least one of the operands. A select is generally more expensive than the
2134  // 'or' that it is replacing.
2135  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2136  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2137  if (Value *V = matchSelectFromAndOr(A, C, B, D, Builder))
2138  return replaceInstUsesWith(I, V);
2139  if (Value *V = matchSelectFromAndOr(A, C, D, B, Builder))
2140  return replaceInstUsesWith(I, V);
2141  if (Value *V = matchSelectFromAndOr(C, A, B, D, Builder))
2142  return replaceInstUsesWith(I, V);
2143  if (Value *V = matchSelectFromAndOr(C, A, D, B, Builder))
2144  return replaceInstUsesWith(I, V);
2145  if (Value *V = matchSelectFromAndOr(B, D, A, C, Builder))
2146  return replaceInstUsesWith(I, V);
2147  if (Value *V = matchSelectFromAndOr(B, D, C, A, Builder))
2148  return replaceInstUsesWith(I, V);
2149  if (Value *V = matchSelectFromAndOr(D, B, A, C, Builder))
2150  return replaceInstUsesWith(I, V);
2151  if (Value *V = matchSelectFromAndOr(D, B, C, A, Builder))
2152  return replaceInstUsesWith(I, V);
2153  }
2154  }
2155 
2156  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2157  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2158  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2159  return BinaryOperator::CreateOr(Op0, C);
2160 
2161  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2162  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2163  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2164  return BinaryOperator::CreateOr(Op1, C);
2165 
2166  // ((B | C) & A) | B -> B | (A & C)
2167  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2168  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2169 
2170  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2171  return DeMorgan;
2172 
2173  // Canonicalize xor to the RHS.
2174  bool SwappedForXor = false;
2175  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2176  std::swap(Op0, Op1);
2177  SwappedForXor = true;
2178  }
2179 
2180  // A | ( A ^ B) -> A | B
2181  // A | (~A ^ B) -> A | ~B
2182  // (A & B) | (A ^ B)
2183  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2184  if (Op0 == A || Op0 == B)
2185  return BinaryOperator::CreateOr(A, B);
2186 
2187  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2188  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2189  return BinaryOperator::CreateOr(A, B);
2190 
2191  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2192  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2193  return BinaryOperator::CreateOr(Not, Op0);
2194  }
2195  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2196  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2197  return BinaryOperator::CreateOr(Not, Op0);
2198  }
2199  }
2200 
2201  // A | ~(A | B) -> A | ~B
2202  // A | ~(A ^ B) -> A | ~B
2203  if (match(Op1, m_Not(m_Value(A))))
2204  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2205  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2206  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2207  B->getOpcode() == Instruction::Xor)) {
2208  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2209  B->getOperand(0);
2210  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2211  return BinaryOperator::CreateOr(Not, Op0);
2212  }
2213 
2214  if (SwappedForXor)
2215  std::swap(Op0, Op1);
2216 
2217  {
2218  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2219  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2220  if (LHS && RHS)
2221  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2222  return replaceInstUsesWith(I, Res);
2223 
2224  // TODO: Make this recursive; it's a little tricky because an arbitrary
2225  // number of 'or' instructions might have to be created.
2226  Value *X, *Y;
2227  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2228  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2229  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2230  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2231  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2232  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2233  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2234  }
2235  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2236  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2237  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2238  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2239  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2240  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2241  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2242  }
2243  }
2244 
2245  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2246  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2247  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2248  return replaceInstUsesWith(I, Res);
2249 
2250  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2251  return CastedOr;
2252 
2253  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2254  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2255  A->getType()->isIntOrIntVectorTy(1))
2256  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2257  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2258  A->getType()->isIntOrIntVectorTy(1))
2259  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2260 
2261  // Note: If we've gotten to the point of visiting the outer OR, then the
2262  // inner one couldn't be simplified. If it was a constant, then it won't
2263  // be simplified by a later pass either, so we try swapping the inner/outer
2264  // ORs in the hopes that we'll be able to simplify it this way.
2265  // (X|C) | V --> (X|V) | C
2266  ConstantInt *C1;
2267  if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
2268  match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) {
2269  Value *Inner = Builder.CreateOr(A, Op1);
2270  Inner->takeName(Op0);
2271  return BinaryOperator::CreateOr(Inner, C1);
2272  }
2273 
2274  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2275  // Since this OR statement hasn't been optimized further yet, we hope
2276  // that this transformation will allow the new ORs to be optimized.
2277  {
2278  Value *X = nullptr, *Y = nullptr;
2279  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2280  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2281  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2282  Value *orTrue = Builder.CreateOr(A, C);
2283  Value *orFalse = Builder.CreateOr(B, D);
2284  return SelectInst::Create(X, orTrue, orFalse);
2285  }
2286  }
2287 
2288  return Changed ? &I : nullptr;
2289 }
2290 
2291 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2292 /// can fold these early and efficiently by morphing an existing instruction.
2294  InstCombiner::BuilderTy &Builder) {
2295  assert(I.getOpcode() == Instruction::Xor);
2296  Value *Op0 = I.getOperand(0);
2297  Value *Op1 = I.getOperand(1);
2298  Value *A, *B;
2299 
2300  // There are 4 commuted variants for each of the basic patterns.
2301 
2302  // (A & B) ^ (A | B) -> A ^ B
2303  // (A & B) ^ (B | A) -> A ^ B
2304  // (A | B) ^ (A & B) -> A ^ B
2305  // (A | B) ^ (B & A) -> A ^ B
2306  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2307  m_c_Or(m_Deferred(A), m_Deferred(B))))) {
2308  I.setOperand(0, A);
2309  I.setOperand(1, B);
2310  return &I;
2311  }
2312 
2313  // (A | ~B) ^ (~A | B) -> A ^ B
2314  // (~B | A) ^ (~A | B) -> A ^ B
2315  // (~A | B) ^ (A | ~B) -> A ^ B
2316  // (B | ~A) ^ (A | ~B) -> A ^ B
2317  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2318  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2319  I.setOperand(0, A);
2320  I.setOperand(1, B);
2321  return &I;
2322  }
2323 
2324  // (A & ~B) ^ (~A & B) -> A ^ B
2325  // (~B & A) ^ (~A & B) -> A ^ B
2326  // (~A & B) ^ (A & ~B) -> A ^ B
2327  // (B & ~A) ^ (A & ~B) -> A ^ B
2328  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2329  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B))))) {
2330  I.setOperand(0, A);
2331  I.setOperand(1, B);
2332  return &I;
2333  }
2334 
2335  // For the remaining cases we need to get rid of one of the operands.
2336  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2337  return nullptr;
2338 
2339  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2340  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2341  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2342  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2343  // Complexity sorting ensures the not will be on the right side.
2344  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2345  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2346  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2347  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2348  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2349 
2350  return nullptr;
2351 }
2352 
2353 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
2354  if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2355  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2356  LHS->getOperand(1) == RHS->getOperand(0))
2357  LHS->swapOperands();
2358  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2359  LHS->getOperand(1) == RHS->getOperand(1)) {
2360  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2361  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2362  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2363  bool isSigned = LHS->isSigned() || RHS->isSigned();
2364  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
2365  }
2366  }
2367 
2368  // TODO: This can be generalized to compares of non-signbits using
2369  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
2370  // foldLogOpOfMaskedICmps().
2371  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2372  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
2373  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
2374  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
2375  LHS0->getType() == RHS0->getType()) {
2376  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
2377  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
2378  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2379  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
2380  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2381  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
2382  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
2383  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
2384  }
2385  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
2386  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
2387  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2388  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
2389  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2390  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
2391  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
2392  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
2393  }
2394  }
2395 
2396  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2397  // into those logic ops. That is, try to turn this into an and-of-icmps
2398  // because we have many folds for that pattern.
2399  //
2400  // This is based on a truth table definition of xor:
2401  // X ^ Y --> (X | Y) & !(X & Y)
2402  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2403  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2404  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2405  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2406  // TODO: Independently handle cases where the 'and' side is a constant.
2407  if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
2408  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
2409  RHS->setPredicate(RHS->getInversePredicate());
2410  return Builder.CreateAnd(LHS, RHS);
2411  }
2412  if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
2413  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
2414  LHS->setPredicate(LHS->getInversePredicate());
2415  return Builder.CreateAnd(LHS, RHS);
2416  }
2417  }
2418  }
2419 
2420  return nullptr;
2421 }
2422 
2423 /// If we have a masked merge, in the canonical form of:
2424 /// (assuming that A only has one use.)
2425 /// | A | |B|
2426 /// ((x ^ y) & M) ^ y
2427 /// | D |
2428 /// * If M is inverted:
2429 /// | D |
2430 /// ((x ^ y) & ~M) ^ y
2431 /// We can canonicalize by swapping the final xor operand
2432 /// to eliminate the 'not' of the mask.
2433 /// ((x ^ y) & M) ^ x
2434 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
2435 /// because that shortens the dependency chain and improves analysis:
2436 /// (x & M) | (y & ~M)
2438  InstCombiner::BuilderTy &Builder) {
2439  Value *B, *X, *D;
2440  Value *M;
2441  if (!match(&I, m_c_Xor(m_Value(B),
2442  m_OneUse(m_c_And(
2444  m_Value(D)),
2445  m_Value(M))))))
2446  return nullptr;
2447 
2448  Value *NotM;
2449  if (match(M, m_Not(m_Value(NotM)))) {
2450  // De-invert the mask and swap the value in B part.
2451  Value *NewA = Builder.CreateAnd(D, NotM);
2452  return BinaryOperator::CreateXor(NewA, X);
2453  }
2454 
2455  Constant *C;
2456  if (D->hasOneUse() && match(M, m_Constant(C))) {
2457  // Unfold.
2458  Value *LHS = Builder.CreateAnd(X, C);
2459  Value *NotC = Builder.CreateNot(C);
2460  Value *RHS = Builder.CreateAnd(B, NotC);
2461  return BinaryOperator::CreateOr(LHS, RHS);
2462  }
2463 
2464  return nullptr;
2465 }
2466 
2467 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2468 // here. We should standardize that construct where it is needed or choose some
2469 // other way to ensure that commutated variants of patterns are not missed.
2471  bool Changed = SimplifyAssociativeOrCommutative(I);
2472  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2473  if (Value *V = SimplifyXorInst(Op0, Op1, SQ.getWithInstruction(&I)))
2474  return replaceInstUsesWith(I, V);
2475 
2476  if (Instruction *X = foldShuffledBinop(I))
2477  return X;
2478 
2479  if (Instruction *NewXor = foldXorToXor(I, Builder))
2480  return NewXor;
2481 
2482  // (A&B)^(A&C) -> A&(B^C) etc
2483  if (Value *V = SimplifyUsingDistributiveLaws(I))
2484  return replaceInstUsesWith(I, V);
2485 
2486  // See if we can simplify any instructions used by the instruction whose sole
2487  // purpose is to compute bits we don't care about.
2488  if (SimplifyDemandedInstructionBits(I))
2489  return &I;
2490 
2491  if (Value *V = SimplifyBSwap(I, Builder))
2492  return replaceInstUsesWith(I, V);
2493 
2494  // A^B --> A|B iff A and B have no bits set in common.
2495  if (haveNoCommonBitsSet(Op0, Op1, DL, &AC, &I, &DT))
2496  return BinaryOperator::CreateOr(Op0, Op1);
2497 
2498  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
2499  Value *X, *Y;
2500 
2501  // We must eliminate the and/or (one-use) for these transforms to not increase
2502  // the instruction count.
2503  // ~(~X & Y) --> (X | ~Y)
2504  // ~(Y & ~X) --> (X | ~Y)
2505  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
2506  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2507  return BinaryOperator::CreateOr(X, NotY);
2508  }
2509  // ~(~X | Y) --> (X & ~Y)
2510  // ~(Y | ~X) --> (X & ~Y)
2511  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
2512  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2513  return BinaryOperator::CreateAnd(X, NotY);
2514  }
2515 
2516  if (Instruction *Xor = visitMaskedMerge(I, Builder))
2517  return Xor;
2518 
2519  // Is this a 'not' (~) fed by a binary operator?
2520  BinaryOperator *NotVal;
2521  if (match(&I, m_Not(m_BinOp(NotVal)))) {
2522  if (NotVal->getOpcode() == Instruction::And ||
2523  NotVal->getOpcode() == Instruction::Or) {
2524  // Apply DeMorgan's Law when inverts are free:
2525  // ~(X & Y) --> (~X | ~Y)
2526  // ~(X | Y) --> (~X & ~Y)
2527  if (IsFreeToInvert(NotVal->getOperand(0),
2528  NotVal->getOperand(0)->hasOneUse()) &&
2529  IsFreeToInvert(NotVal->getOperand(1),
2530  NotVal->getOperand(1)->hasOneUse())) {
2531  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
2532  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
2533  if (NotVal->getOpcode() == Instruction::And)
2534  return BinaryOperator::CreateOr(NotX, NotY);
2535  return BinaryOperator::CreateAnd(NotX, NotY);
2536  }
2537  }
2538 
2539  // ~(~X >>s Y) --> (X >>s Y)
2540  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
2541  return BinaryOperator::CreateAShr(X, Y);
2542 
2543  // If we are inverting a right-shifted constant, we may be able to eliminate
2544  // the 'not' by inverting the constant and using the opposite shift type.
2545  // Canonicalization rules ensure that only a negative constant uses 'ashr',
2546  // but we must check that in case that transform has not fired yet.
2547  Constant *C;
2548  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
2549  match(C, m_Negative())) {
2550  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
2551  Constant *NotC = ConstantExpr::getNot(C);
2552  return BinaryOperator::CreateLShr(NotC, Y);
2553  }
2554 
2555  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
2556  match(C, m_NonNegative())) {
2557  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
2558  Constant *NotC = ConstantExpr::getNot(C);
2559  return BinaryOperator::CreateAShr(NotC, Y);
2560  }
2561  }
2562 
2563  // not (cmp A, B) = !cmp A, B
2564  CmpInst::Predicate Pred;
2565  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
2566  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
2567  return replaceInstUsesWith(I, Op0);
2568  }
2569 
2570  {
2571  const APInt *RHSC;
2572  if (match(Op1, m_APInt(RHSC))) {
2573  Value *X;
2574  const APInt *C;
2575  if (match(Op0, m_Sub(m_APInt(C), m_Value(X)))) {
2576  // ~(c-X) == X-c-1 == X+(-c-1)
2577  if (RHSC->isAllOnesValue()) {
2578  Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1);
2579  return BinaryOperator::CreateAdd(X, NewC);
2580  }
2581  if (RHSC->isSignMask()) {
2582  // (C - X) ^ signmask -> (C + signmask - X)
2583  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2584  return BinaryOperator::CreateSub(NewC, X);
2585  }
2586  } else if (match(Op0, m_Add(m_Value(X), m_APInt(C)))) {
2587  // ~(X-c) --> (-c-1)-X
2588  if (RHSC->isAllOnesValue()) {
2589  Constant *NewC = ConstantInt::get(I.getType(), -(*C) - 1);
2590  return BinaryOperator::CreateSub(NewC, X);
2591  }
2592  if (RHSC->isSignMask()) {
2593  // (X + C) ^ signmask -> (X + C + signmask)
2594  Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC);
2595  return BinaryOperator::CreateAdd(X, NewC);
2596  }
2597  }
2598 
2599  // (X|C1)^C2 -> X^(C1^C2) iff X&~C1 == 0
2600  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
2601  MaskedValueIsZero(X, *C, 0, &I)) {
2602  Constant *NewC = ConstantInt::get(I.getType(), *C ^ *RHSC);
2603  Worklist.Add(cast<Instruction>(Op0));
2604  I.setOperand(0, X);
2605  I.setOperand(1, NewC);
2606  return &I;
2607  }
2608  }
2609  }
2610 
2611  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
2612  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2613  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2614  if (Op0I->getOpcode() == Instruction::LShr) {
2615  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
2616  // E1 = "X ^ C1"
2617  BinaryOperator *E1;
2618  ConstantInt *C1;
2619  if (Op0I->hasOneUse() &&
2620  (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
2621  E1->getOpcode() == Instruction::Xor &&
2622  (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
2623  // fold (C1 >> C2) ^ C3
2624  ConstantInt *C2 = Op0CI, *C3 = RHSC;
2625  APInt FoldConst = C1->getValue().lshr(C2->getValue());
2626  FoldConst ^= C3->getValue();
2627  // Prepare the two operands.
2628  Value *Opnd0 = Builder.CreateLShr(E1->getOperand(0), C2);
2629  Opnd0->takeName(Op0I);
2630  cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
2631  Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
2632 
2633  return BinaryOperator::CreateXor(Opnd0, FoldVal);
2634  }
2635  }
2636  }
2637  }
2638  }
2639 
2640  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2641  return FoldedLogic;
2642 
2643  {
2644  Value *A, *B;
2645  if (match(Op1, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2646  if (A == Op0) { // A^(A|B) == A^(B|A)
2647  cast<BinaryOperator>(Op1)->swapOperands();
2648  std::swap(A, B);
2649  }
2650  if (B == Op0) { // A^(B|A) == (B|A)^A
2651  I.swapOperands(); // Simplified below.
2652  std::swap(Op0, Op1);
2653  }
2654  } else if (match(Op1, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2655  if (A == Op0) { // A^(A&B) -> A^(B&A)
2656  cast<BinaryOperator>(Op1)->swapOperands();
2657  std::swap(A, B);
2658  }
2659  if (B == Op0) { // A^(B&A) -> (B&A)^A
2660  I.swapOperands(); // Simplified below.
2661  std::swap(Op0, Op1);
2662  }
2663  }
2664  }
2665 
2666  {
2667  Value *A, *B;
2668  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2669  if (A == Op1) // (B|A)^B == (A|B)^B
2670  std::swap(A, B);
2671  if (B == Op1) // (A|B)^B == A & ~B
2672  return BinaryOperator::CreateAnd(A, Builder.CreateNot(Op1));
2673  } else if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2674  if (A == Op1) // (A&B)^A -> (B&A)^A
2675  std::swap(A, B);
2676  const APInt *C;
2677  if (B == Op1 && // (B&A)^A == ~B & A
2678  !match(Op1, m_APInt(C))) { // Canonical form is (B&C)^C
2679  return BinaryOperator::CreateAnd(Builder.CreateNot(A), Op1);
2680  }
2681  }
2682  }
2683 
2684  {
2685  Value *A, *B, *C, *D;
2686  // (A ^ C)^(A | B) -> ((~A) & B) ^ C
2687  if (match(Op0, m_Xor(m_Value(D), m_Value(C))) &&
2688  match(Op1, m_Or(m_Value(A), m_Value(B)))) {
2689  if (D == A)
2690  return BinaryOperator::CreateXor(
2691  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2692  if (D == B)
2693  return BinaryOperator::CreateXor(
2694  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2695  }
2696  // (A | B)^(A ^ C) -> ((~A) & B) ^ C
2697  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2698  match(Op1, m_Xor(m_Value(D), m_Value(C)))) {
2699  if (D == A)
2700  return BinaryOperator::CreateXor(
2701  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2702  if (D == B)
2703  return BinaryOperator::CreateXor(
2704  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2705  }
2706  // (A & B) ^ (A ^ B) -> (A | B)
2707  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2708  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
2709  return BinaryOperator::CreateOr(A, B);
2710  // (A ^ B) ^ (A & B) -> (A | B)
2711  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2712  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2713  return BinaryOperator::CreateOr(A, B);
2714  }
2715 
2716  // (A & ~B) ^ ~A -> ~(A & B)
2717  // (~B & A) ^ ~A -> ~(A & B)
2718  Value *A, *B;
2719  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
2720  match(Op1, m_Not(m_Specific(A))))
2721  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
2722 
2723  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
2724  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
2725  if (Value *V = foldXorOfICmps(LHS, RHS))
2726  return replaceInstUsesWith(I, V);
2727 
2728  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
2729  return CastedXor;
2730 
2731  // Canonicalize a shifty way to code absolute value to the common pattern.
2732  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
2733  // We're relying on the fact that we only do this transform when the shift has
2734  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
2735  // instructions).
2736  if (Op0->hasNUses(2))
2737  std::swap(Op0, Op1);
2738 
2739  const APInt *ShAmt;
2740  Type *Ty = I.getType();
2741  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
2742  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
2743  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
2744  // B = ashr i32 A, 31 ; smear the sign bit
2745  // xor (add A, B), B ; add -1 and flip bits if negative
2746  // --> (A < 0) ? -A : A
2747  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
2748  // Copy the nuw/nsw flags from the add to the negate.
2749  auto *Add = cast<BinaryOperator>(Op0);
2750  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
2751  Add->hasNoSignedWrap());
2752  return SelectInst::Create(Cmp, Neg, A);
2753  }
2754 
2755  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
2756  //
2757  // %notx = xor i32 %x, -1
2758  // %cmp1 = icmp sgt i32 %notx, %y
2759  // %smax = select i1 %cmp1, i32 %notx, i32 %y
2760  // %res = xor i32 %smax, -1
2761  // =>
2762  // %noty = xor i32 %y, -1
2763  // %cmp2 = icmp slt %x, %noty
2764  // %res = select i1 %cmp2, i32 %x, i32 %noty
2765  //
2766  // Same is applicable for smin/umax/umin.
2767  {
2768  Value *LHS, *RHS;
2769  SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
2770  if (Op0->hasOneUse() && SelectPatternResult::isMinOrMax(SPF) &&
2771  match(Op1, m_AllOnes())) {
2772 
2773  Value *X;
2774  if (match(RHS, m_Not(m_Value(X))))
2775  std::swap(RHS, LHS);
2776 
2777  if (match(LHS, m_Not(m_Value(X)))) {
2778  Value *NotY = Builder.CreateNot(RHS);
2779  return SelectInst::Create(
2780  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
2781  }
2782  }
2783  }
2784 
2785  return Changed ? &I : nullptr;
2786 }
const NoneType None
Definition: None.h:24
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:709
uint64_t CallInst * C
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of nonnegative values.
Definition: PatternMatch.h:340
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:574
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to have exactly one bit set when defined. ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1846
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool isSignMask() const
Check if the APInt&#39;s value is returned by getSignMask.
Definition: APInt.h:466
Type * getSrcTy() const
Return the source type, as a convenience.
Definition: InstrTypes.h:850
static bool IsFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
static Value * getFCmpValue(unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp inst...
Instruction * visitXor(BinaryOperator &I)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1246
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:642
Instruction * visitOr(BinaryOperator &I)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:373
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1566
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1127
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1148
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
static unsigned getFCmpCode(FCmpInst::Predicate CC)
Similar to getICmpCode but for FCmpInst.
This class represents zero extension of integer types.
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:661
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:864
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:641
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
unsigned less or equal
Definition: InstrTypes.h:911
unsigned less than
Definition: InstrTypes.h:910
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:739
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:891
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:901
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1258
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:227
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1223
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:161
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:901
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:258
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1282
bool swapOperands()
Exchange the two operands to this instruction.
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:896
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:895
bool isSigned() const
Definition: InstrTypes.h:1054
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:721
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:983
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:592
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
static Constant * AddOne(Constant *C)
Add one to a Constant.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:892
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1618
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:962
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:630
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1632
static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)...
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1629
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:845
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
This instruction compares its operands according to the predicate given to the constructor.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
static Value * foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:433
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
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if LHS and RHS have no common bits set.
SelectClass_match< Cond, LHS, RHS > m_Select(const Cond &C, const LHS &L, const RHS &R)
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:1001
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:170
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1130
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:328
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1854
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
static Optional< std::pair< unsigned, unsigned > > getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR)
Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:733
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
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:715
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1169
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:1901
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if &#39;V & Mask&#39; is known to be zero.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
static Constant * getAnd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2236
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:404
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:490
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:436
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:727
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:894
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
static unsigned conjugateICmpMask(unsigned Mask)
Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite s...
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition: APInt.h:443
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:2171
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:312
1 1 1 1 Always true (always folded)
Definition: InstrTypes.h:902
static Value * getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
void swapOperands()
Exchange the two operands to this instruction in such a way that it does not modify the semantics of ...
static Instruction * matchDeMorgansLaws(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Match De Morgan&#39;s Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B))
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:900
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:503
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:964
signed greater than
Definition: InstrTypes.h:912
Instruction * visitAnd(BinaryOperator &I)
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
static Value * foldLogOpOfMaskedICmpsAsymmetric(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, unsigned LHSMask, unsigned RHSMask, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y), where the left-hand ...
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:889
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:328
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
SelectPatternFlavor Flavor
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:899
SelectPatternFlavor
Specific patterns of select instructions we can match.
signed less than
Definition: InstrTypes.h:914
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:382
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1604
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:611
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:625
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:852
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:567
bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2)
Return true if both predicates match sign or if at least one of them is an equality comparison (which...
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:964
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
signed less or equal
Definition: InstrTypes.h:915
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1207
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:457
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:63
static Instruction * foldAndToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Value * SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
static Value * foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)...
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1239
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:959
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:285
Value * getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, CmpInst::Predicate &NewICmpPred)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
unsigned greater or equal
Definition: InstrTypes.h:909
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
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:2240
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:893
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Value * SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:897
APInt byteSwap() const
Definition: APInt.cpp:616
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1112
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:430
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:888
LLVM Value Representation.
Definition: Value.h:73
This file provides internal interfaces used to implement the InstCombine.
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:898
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:352
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:131
static Instruction * visitMaskedMerge(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have a masked merge, in the canonical form of: (assuming that A only has one use...
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
unsigned greater than
Definition: InstrTypes.h:908
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:999
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
Value * simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction *> &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:2429
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:890
static Value * matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D, InstCombiner::BuilderTy &Builder)
We have an expression of the form (A & C) | (B & D).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
Fold {and,or,xor} (cast X), C.
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
static Instruction * foldXorToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
A ^ B can be specified using other logic ops in a variety of patterns.
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
0 0 0 0 Always false (always folded)
Definition: InstrTypes.h:887
signed greater or equal
Definition: InstrTypes.h:913
static Constant * getXor(Constant *C1, Constant *C2)
Definition: Constants.cpp:2244
CallInst * CreateCall(Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1871