LLVM  13.0.0git
InstCombineAndOrXor.cpp
Go to the documentation of this file.
1 //===- InstCombineAndOrXor.cpp --------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the visitAnd, visitOr, and visitXor functions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "InstCombineInternal.h"
16 #include "llvm/IR/ConstantRange.h"
17 #include "llvm/IR/Intrinsics.h"
18 #include "llvm/IR/PatternMatch.h"
21 
22 using namespace llvm;
23 using namespace PatternMatch;
24 
25 #define DEBUG_TYPE "instcombine"
26 
27 /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
28 /// a four bit mask.
29 static unsigned getFCmpCode(FCmpInst::Predicate CC) {
31  "Unexpected FCmp predicate!");
32  // Take advantage of the bit pattern of FCmpInst::Predicate here.
33  // U L G E
34  static_assert(FCmpInst::FCMP_FALSE == 0, ""); // 0 0 0 0
35  static_assert(FCmpInst::FCMP_OEQ == 1, ""); // 0 0 0 1
36  static_assert(FCmpInst::FCMP_OGT == 2, ""); // 0 0 1 0
37  static_assert(FCmpInst::FCMP_OGE == 3, ""); // 0 0 1 1
38  static_assert(FCmpInst::FCMP_OLT == 4, ""); // 0 1 0 0
39  static_assert(FCmpInst::FCMP_OLE == 5, ""); // 0 1 0 1
40  static_assert(FCmpInst::FCMP_ONE == 6, ""); // 0 1 1 0
41  static_assert(FCmpInst::FCMP_ORD == 7, ""); // 0 1 1 1
42  static_assert(FCmpInst::FCMP_UNO == 8, ""); // 1 0 0 0
43  static_assert(FCmpInst::FCMP_UEQ == 9, ""); // 1 0 0 1
44  static_assert(FCmpInst::FCMP_UGT == 10, ""); // 1 0 1 0
45  static_assert(FCmpInst::FCMP_UGE == 11, ""); // 1 0 1 1
46  static_assert(FCmpInst::FCMP_ULT == 12, ""); // 1 1 0 0
47  static_assert(FCmpInst::FCMP_ULE == 13, ""); // 1 1 0 1
48  static_assert(FCmpInst::FCMP_UNE == 14, ""); // 1 1 1 0
49  static_assert(FCmpInst::FCMP_TRUE == 15, ""); // 1 1 1 1
50  return CC;
51 }
52 
53 /// This is the complement of getICmpCode, which turns an opcode and two
54 /// operands into either a constant true or false, or a brand new ICmp
55 /// instruction. The sign is passed in to determine which kind of predicate to
56 /// use in the new icmp instruction.
57 static Value *getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS,
59  ICmpInst::Predicate NewPred;
60  if (Constant *TorF = getPredForICmpCode(Code, Sign, LHS->getType(), NewPred))
61  return TorF;
62  return Builder.CreateICmp(NewPred, LHS, RHS);
63 }
64 
65 /// This is the complement of getFCmpCode, which turns an opcode and two
66 /// operands into either a FCmp instruction, or a true/false constant.
67 static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
69  const auto Pred = static_cast<FCmpInst::Predicate>(Code);
70  assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
71  "Unexpected FCmp predicate!");
72  if (Pred == FCmpInst::FCMP_FALSE)
74  if (Pred == FCmpInst::FCMP_TRUE)
76  return Builder.CreateFCmp(Pred, LHS, RHS);
77 }
78 
79 /// Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or
80 /// BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
81 /// \param I Binary operator to transform.
82 /// \return Pointer to node that must replace the original binary operator, or
83 /// null pointer if no transformation was made.
86  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bswap simplifying");
87 
88  Value *OldLHS = I.getOperand(0);
89  Value *OldRHS = I.getOperand(1);
90 
91  Value *NewLHS;
92  if (!match(OldLHS, m_BSwap(m_Value(NewLHS))))
93  return nullptr;
94 
95  Value *NewRHS;
96  const APInt *C;
97 
98  if (match(OldRHS, m_BSwap(m_Value(NewRHS)))) {
99  // OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
100  if (!OldLHS->hasOneUse() && !OldRHS->hasOneUse())
101  return nullptr;
102  // NewRHS initialized by the matcher.
103  } else if (match(OldRHS, m_APInt(C))) {
104  // OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
105  if (!OldLHS->hasOneUse())
106  return nullptr;
107  NewRHS = ConstantInt::get(I.getType(), C->byteSwap());
108  } else
109  return nullptr;
110 
111  Value *BinOp = Builder.CreateBinOp(I.getOpcode(), NewLHS, NewRHS);
112  Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap,
113  I.getType());
114  return Builder.CreateCall(F, BinOp);
115 }
116 
117 /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
118 /// (V < Lo || V >= Hi). This method expects that Lo < Hi. IsSigned indicates
119 /// whether to treat V, Lo, and Hi as signed or not.
121  const APInt &Hi, bool isSigned,
122  bool Inside) {
123  assert((isSigned ? Lo.slt(Hi) : Lo.ult(Hi)) &&
124  "Lo is not < Hi in range emission code!");
125 
126  Type *Ty = V->getType();
127 
128  // V >= Min && V < Hi --> V < Hi
129  // V < Min || V >= Hi --> V >= Hi
131  if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
132  Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
133  return Builder.CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
134  }
135 
136  // V >= Lo && V < Hi --> V - Lo u< Hi - Lo
137  // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo
138  Value *VMinusLo =
139  Builder.CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
140  Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
141  return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo);
142 }
143 
144 /// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns
145 /// that can be simplified.
146 /// One of A and B is considered the mask. The other is the value. This is
147 /// described as the "AMask" or "BMask" part of the enum. If the enum contains
148 /// only "Mask", then both A and B can be considered masks. If A is the mask,
149 /// then it was proven that (A & C) == C. This is trivial if C == A or C == 0.
150 /// If both A and C are constants, this proof is also easy.
151 /// For the following explanations, we assume that A is the mask.
152 ///
153 /// "AllOnes" declares that the comparison is true only if (A & B) == A or all
154 /// bits of A are set in B.
155 /// Example: (icmp eq (A & 3), 3) -> AMask_AllOnes
156 ///
157 /// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all
158 /// bits of A are cleared in B.
159 /// Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes
160 ///
161 /// "Mixed" declares that (A & B) == C and C might or might not contain any
162 /// number of one bits and zero bits.
163 /// Example: (icmp eq (A & 3), 1) -> AMask_Mixed
164 ///
165 /// "Not" means that in above descriptions "==" should be replaced by "!=".
166 /// Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes
167 ///
168 /// If the mask A contains a single bit, then the following is equivalent:
169 /// (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
170 /// (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
180  BMask_Mixed = 256,
182 };
183 
184 /// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C)
185 /// satisfies.
186 static unsigned getMaskedICmpType(Value *A, Value *B, Value *C,
187  ICmpInst::Predicate Pred) {
188  ConstantInt *ACst = dyn_cast<ConstantInt>(A);
189  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
190  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
191  bool IsEq = (Pred == ICmpInst::ICMP_EQ);
192  bool IsAPow2 = (ACst && !ACst->isZero() && ACst->getValue().isPowerOf2());
193  bool IsBPow2 = (BCst && !BCst->isZero() && BCst->getValue().isPowerOf2());
194  unsigned MaskVal = 0;
195  if (CCst && CCst->isZero()) {
196  // if C is zero, then both A and B qualify as mask
197  MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed)
199  if (IsAPow2)
200  MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed)
201  : (AMask_AllOnes | AMask_Mixed));
202  if (IsBPow2)
203  MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed)
204  : (BMask_AllOnes | BMask_Mixed));
205  return MaskVal;
206  }
207 
208  if (A == C) {
209  MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed)
211  if (IsAPow2)
212  MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed)
213  : (Mask_AllZeros | AMask_Mixed));
214  } else if (ACst && CCst && ConstantExpr::getAnd(ACst, CCst) == CCst) {
215  MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed);
216  }
217 
218  if (B == C) {
219  MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed)
221  if (IsBPow2)
222  MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed)
223  : (Mask_AllZeros | BMask_Mixed));
224  } else if (BCst && CCst && ConstantExpr::getAnd(BCst, CCst) == CCst) {
225  MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed);
226  }
227 
228  return MaskVal;
229 }
230 
231 /// Convert an analysis of a masked ICmp into its equivalent if all boolean
232 /// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
233 /// is adjacent to the corresponding normal flag (recording ==), this just
234 /// involves swapping those bits over.
235 static unsigned conjugateICmpMask(unsigned Mask) {
236  unsigned NewMask;
237  NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros |
239  << 1;
240 
243  >> 1;
244 
245  return NewMask;
246 }
247 
248 // Adapts the external decomposeBitTestICmp for local use.
249 static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred,
250  Value *&X, Value *&Y, Value *&Z) {
251  APInt Mask;
252  if (!llvm::decomposeBitTestICmp(LHS, RHS, Pred, X, Mask))
253  return false;
254 
255  Y = ConstantInt::get(X->getType(), Mask);
256  Z = ConstantInt::get(X->getType(), 0);
257  return true;
258 }
259 
260 /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
261 /// Return the pattern classes (from MaskedICmpType) for the left hand side and
262 /// the right hand side as a pair.
263 /// LHS and RHS are the left hand side and the right hand side ICmps and PredL
264 /// and PredR are their predicates, respectively.
265 static
268  Value *&D, Value *&E, ICmpInst *LHS,
269  ICmpInst *RHS,
270  ICmpInst::Predicate &PredL,
271  ICmpInst::Predicate &PredR) {
272  // vectors are not (yet?) supported. Don't support pointers either.
273  if (!LHS->getOperand(0)->getType()->isIntegerTy() ||
274  !RHS->getOperand(0)->getType()->isIntegerTy())
275  return None;
276 
277  // Here comes the tricky part:
278  // LHS might be of the form L11 & L12 == X, X == L21 & L22,
279  // and L11 & L12 == L21 & L22. The same goes for RHS.
280  // Now we must find those components L** and R**, that are equal, so
281  // that we can extract the parameters A, B, C, D, and E for the canonical
282  // above.
283  Value *L1 = LHS->getOperand(0);
284  Value *L2 = LHS->getOperand(1);
285  Value *L11, *L12, *L21, *L22;
286  // Check whether the icmp can be decomposed into a bit test.
287  if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) {
288  L21 = L22 = L1 = nullptr;
289  } else {
290  // Look for ANDs in the LHS icmp.
291  if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
292  // Any icmp can be viewed as being trivially masked; if it allows us to
293  // remove one, it's worth it.
294  L11 = L1;
295  L12 = Constant::getAllOnesValue(L1->getType());
296  }
297 
298  if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
299  L21 = L2;
300  L22 = Constant::getAllOnesValue(L2->getType());
301  }
302  }
303 
304  // Bail if LHS was a icmp that can't be decomposed into an equality.
305  if (!ICmpInst::isEquality(PredL))
306  return None;
307 
308  Value *R1 = RHS->getOperand(0);
309  Value *R2 = RHS->getOperand(1);
310  Value *R11, *R12;
311  bool Ok = false;
312  if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) {
313  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
314  A = R11;
315  D = R12;
316  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
317  A = R12;
318  D = R11;
319  } else {
320  return None;
321  }
322  E = R2;
323  R1 = nullptr;
324  Ok = true;
325  } else {
326  if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
327  // As before, model no mask as a trivial mask if it'll let us do an
328  // optimization.
329  R11 = R1;
330  R12 = Constant::getAllOnesValue(R1->getType());
331  }
332 
333  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
334  A = R11;
335  D = R12;
336  E = R2;
337  Ok = true;
338  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
339  A = R12;
340  D = R11;
341  E = R2;
342  Ok = true;
343  }
344  }
345 
346  // Bail if RHS was a icmp that can't be decomposed into an equality.
347  if (!ICmpInst::isEquality(PredR))
348  return None;
349 
350  // Look for ANDs on the right side of the RHS icmp.
351  if (!Ok) {
352  if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
353  R11 = R2;
354  R12 = Constant::getAllOnesValue(R2->getType());
355  }
356 
357  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
358  A = R11;
359  D = R12;
360  E = R1;
361  Ok = true;
362  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
363  A = R12;
364  D = R11;
365  E = R1;
366  Ok = true;
367  } else {
368  return None;
369  }
370  }
371  if (!Ok)
372  return None;
373 
374  if (L11 == A) {
375  B = L12;
376  C = L2;
377  } else if (L12 == A) {
378  B = L11;
379  C = L2;
380  } else if (L21 == A) {
381  B = L22;
382  C = L1;
383  } else if (L22 == A) {
384  B = L21;
385  C = L1;
386  }
387 
388  unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
389  unsigned RightType = getMaskedICmpType(A, D, E, PredR);
390  return Optional<std::pair<unsigned, unsigned>>(std::make_pair(LeftType, RightType));
391 }
392 
393 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single
394 /// (icmp(A & X) ==/!= Y), where the left-hand side is of type Mask_NotAllZeros
395 /// and the right hand side is of type BMask_Mixed. For example,
396 /// (icmp (A & 12) != 0) & (icmp (A & 15) == 8) -> (icmp (A & 15) == 8).
398  ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C,
401  // We are given the canonical form:
402  // (icmp ne (A & B), 0) & (icmp eq (A & D), E).
403  // where D & E == E.
404  //
405  // If IsAnd is false, we get it in negated form:
406  // (icmp eq (A & B), 0) | (icmp ne (A & D), E) ->
407  // !((icmp ne (A & B), 0) & (icmp eq (A & D), E)).
408  //
409  // We currently handle the case of B, C, D, E are constant.
410  //
411  ConstantInt *BCst, *CCst, *DCst, *ECst;
412  if (!match(B, m_ConstantInt(BCst)) || !match(C, m_ConstantInt(CCst)) ||
413  !match(D, m_ConstantInt(DCst)) || !match(E, m_ConstantInt(ECst)))
414  return nullptr;
415 
417 
418  // Update E to the canonical form when D is a power of two and RHS is
419  // canonicalized as,
420  // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or
421  // (icmp ne (A & D), D) -> (icmp eq (A & D), 0).
422  if (PredR != NewCC)
423  ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
424 
425  // If B or D is zero, skip because if LHS or RHS can be trivially folded by
426  // other folding rules and this pattern won't apply any more.
427  if (BCst->getValue() == 0 || DCst->getValue() == 0)
428  return nullptr;
429 
430  // If B and D don't intersect, ie. (B & D) == 0, no folding because we can't
431  // deduce anything from it.
432  // For example,
433  // (icmp ne (A & 12), 0) & (icmp eq (A & 3), 1) -> no folding.
434  if ((BCst->getValue() & DCst->getValue()) == 0)
435  return nullptr;
436 
437  // If the following two conditions are met:
438  //
439  // 1. mask B covers only a single bit that's not covered by mask D, that is,
440  // (B & (B ^ D)) is a power of 2 (in other words, B minus the intersection of
441  // B and D has only one bit set) and,
442  //
443  // 2. RHS (and E) indicates that the rest of B's bits are zero (in other
444  // words, the intersection of B and D is zero), that is, ((B & D) & E) == 0
445  //
446  // then that single bit in B must be one and thus the whole expression can be
447  // folded to
448  // (A & (B | D)) == (B & (B ^ D)) | E.
449  //
450  // For example,
451  // (icmp ne (A & 12), 0) & (icmp eq (A & 7), 1) -> (icmp eq (A & 15), 9)
452  // (icmp ne (A & 15), 0) & (icmp eq (A & 7), 0) -> (icmp eq (A & 15), 8)
453  if ((((BCst->getValue() & DCst->getValue()) & ECst->getValue()) == 0) &&
454  (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())).isPowerOf2()) {
455  APInt BorD = BCst->getValue() | DCst->getValue();
456  APInt BandBxorDorE = (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())) |
457  ECst->getValue();
458  Value *NewMask = ConstantInt::get(BCst->getType(), BorD);
459  Value *NewMaskedValue = ConstantInt::get(BCst->getType(), BandBxorDorE);
460  Value *NewAnd = Builder.CreateAnd(A, NewMask);
461  return Builder.CreateICmp(NewCC, NewAnd, NewMaskedValue);
462  }
463 
464  auto IsSubSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) {
465  return (C1->getValue() & C2->getValue()) == C1->getValue();
466  };
467  auto IsSuperSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) {
468  return (C1->getValue() & C2->getValue()) == C2->getValue();
469  };
470 
471  // In the following, we consider only the cases where B is a superset of D, B
472  // is a subset of D, or B == D because otherwise there's at least one bit
473  // covered by B but not D, in which case we can't deduce much from it, so
474  // no folding (aside from the single must-be-one bit case right above.)
475  // For example,
476  // (icmp ne (A & 14), 0) & (icmp eq (A & 3), 1) -> no folding.
477  if (!IsSubSetOrEqual(BCst, DCst) && !IsSuperSetOrEqual(BCst, DCst))
478  return nullptr;
479 
480  // At this point, either B is a superset of D, B is a subset of D or B == D.
481 
482  // If E is zero, if B is a subset of (or equal to) D, LHS and RHS contradict
483  // and the whole expression becomes false (or true if negated), otherwise, no
484  // folding.
485  // For example,
486  // (icmp ne (A & 3), 0) & (icmp eq (A & 7), 0) -> false.
487  // (icmp ne (A & 15), 0) & (icmp eq (A & 3), 0) -> no folding.
488  if (ECst->isZero()) {
489  if (IsSubSetOrEqual(BCst, DCst))
490  return ConstantInt::get(LHS->getType(), !IsAnd);
491  return nullptr;
492  }
493 
494  // At this point, B, D, E aren't zero and (B & D) == B, (B & D) == D or B ==
495  // D. If B is a superset of (or equal to) D, since E is not zero, LHS is
496  // subsumed by RHS (RHS implies LHS.) So the whole expression becomes
497  // RHS. For example,
498  // (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
499  // (icmp ne (A & 15), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
500  if (IsSuperSetOrEqual(BCst, DCst))
501  return RHS;
502  // Otherwise, B is a subset of D. If B and E have a common bit set,
503  // ie. (B & E) != 0, then LHS is subsumed by RHS. For example.
504  // (icmp ne (A & 12), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
505  assert(IsSubSetOrEqual(BCst, DCst) && "Precondition due to above code");
506  if ((BCst->getValue() & ECst->getValue()) != 0)
507  return RHS;
508  // Otherwise, LHS and RHS contradict and the whole expression becomes false
509  // (or true if negated.) For example,
510  // (icmp ne (A & 7), 0) & (icmp eq (A & 15), 8) -> false.
511  // (icmp ne (A & 6), 0) & (icmp eq (A & 15), 8) -> false.
512  return ConstantInt::get(LHS->getType(), !IsAnd);
513 }
514 
515 /// Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single
516 /// (icmp(A & X) ==/!= Y), where the left-hand side and the right hand side
517 /// aren't of the common mask pattern type.
519  ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C,
521  unsigned LHSMask, unsigned RHSMask, InstCombiner::BuilderTy &Builder) {
523  "Expected equality predicates for masked type of icmps.");
524  // Handle Mask_NotAllZeros-BMask_Mixed cases.
525  // (icmp ne/eq (A & B), C) &/| (icmp eq/ne (A & D), E), or
526  // (icmp eq/ne (A & B), C) &/| (icmp ne/eq (A & D), E)
527  // which gets swapped to
528  // (icmp ne/eq (A & D), E) &/| (icmp eq/ne (A & B), C).
529  if (!IsAnd) {
530  LHSMask = conjugateICmpMask(LHSMask);
531  RHSMask = conjugateICmpMask(RHSMask);
532  }
533  if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) {
535  LHS, RHS, IsAnd, A, B, C, D, E,
536  PredL, PredR, Builder)) {
537  return V;
538  }
539  } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) {
541  RHS, LHS, IsAnd, A, D, E, B, C,
542  PredR, PredL, Builder)) {
543  return V;
544  }
545  }
546  return nullptr;
547 }
548 
549 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
550 /// into a single (icmp(A & X) ==/!= Y).
551 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
553  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
554  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
556  getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
557  if (!MaskPair)
558  return nullptr;
560  "Expected equality predicates for masked type of icmps.");
561  unsigned LHSMask = MaskPair->first;
562  unsigned RHSMask = MaskPair->second;
563  unsigned Mask = LHSMask & RHSMask;
564  if (Mask == 0) {
565  // Even if the two sides don't share a common pattern, check if folding can
566  // still happen.
568  LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
569  Builder))
570  return V;
571  return nullptr;
572  }
573 
574  // In full generality:
575  // (icmp (A & B) Op C) | (icmp (A & D) Op E)
576  // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
577  //
578  // If the latter can be converted into (icmp (A & X) Op Y) then the former is
579  // equivalent to (icmp (A & X) !Op Y).
580  //
581  // Therefore, we can pretend for the rest of this function that we're dealing
582  // with the conjunction, provided we flip the sense of any comparisons (both
583  // input and output).
584 
585  // In most cases we're going to produce an EQ for the "&&" case.
587  if (!IsAnd) {
588  // Convert the masking analysis into its equivalent with negated
589  // comparisons.
591  }
592 
593  if (Mask & Mask_AllZeros) {
594  // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
595  // -> (icmp eq (A & (B|D)), 0)
596  Value *NewOr = Builder.CreateOr(B, D);
597  Value *NewAnd = Builder.CreateAnd(A, NewOr);
598  // We can't use C as zero because we might actually handle
599  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
600  // with B and D, having a single bit set.
601  Value *Zero = Constant::getNullValue(A->getType());
602  return Builder.CreateICmp(NewCC, NewAnd, Zero);
603  }
604  if (Mask & BMask_AllOnes) {
605  // (icmp eq (A & B), B) & (icmp eq (A & D), D)
606  // -> (icmp eq (A & (B|D)), (B|D))
607  Value *NewOr = Builder.CreateOr(B, D);
608  Value *NewAnd = Builder.CreateAnd(A, NewOr);
609  return Builder.CreateICmp(NewCC, NewAnd, NewOr);
610  }
611  if (Mask & AMask_AllOnes) {
612  // (icmp eq (A & B), A) & (icmp eq (A & D), A)
613  // -> (icmp eq (A & (B&D)), A)
614  Value *NewAnd1 = Builder.CreateAnd(B, D);
615  Value *NewAnd2 = Builder.CreateAnd(A, NewAnd1);
616  return Builder.CreateICmp(NewCC, NewAnd2, A);
617  }
618 
619  // Remaining cases assume at least that B and D are constant, and depend on
620  // their actual values. This isn't strictly necessary, just a "handle the
621  // easy cases for now" decision.
622  ConstantInt *BCst, *DCst;
623  if (!match(B, m_ConstantInt(BCst)) || !match(D, m_ConstantInt(DCst)))
624  return nullptr;
625 
627  // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
628  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
629  // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
630  // Only valid if one of the masks is a superset of the other (check "B&D" is
631  // the same as either B or D).
632  APInt NewMask = BCst->getValue() & DCst->getValue();
633 
634  if (NewMask == BCst->getValue())
635  return LHS;
636  else if (NewMask == DCst->getValue())
637  return RHS;
638  }
639 
640  if (Mask & AMask_NotAllOnes) {
641  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
642  // -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
643  // Only valid if one of the masks is a superset of the other (check "B|D" is
644  // the same as either B or D).
645  APInt NewMask = BCst->getValue() | DCst->getValue();
646 
647  if (NewMask == BCst->getValue())
648  return LHS;
649  else if (NewMask == DCst->getValue())
650  return RHS;
651  }
652 
653  if (Mask & BMask_Mixed) {
654  // (icmp eq (A & B), C) & (icmp eq (A & D), E)
655  // We already know that B & C == C && D & E == E.
656  // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
657  // C and E, which are shared by both the mask B and the mask D, don't
658  // contradict, then we can transform to
659  // -> (icmp eq (A & (B|D)), (C|E))
660  // Currently, we only handle the case of B, C, D, and E being constant.
661  // We can't simply use C and E because we might actually handle
662  // (icmp ne (A & B), B) & (icmp eq (A & D), D)
663  // with B and D, having a single bit set.
664  ConstantInt *CCst, *ECst;
665  if (!match(C, m_ConstantInt(CCst)) || !match(E, m_ConstantInt(ECst)))
666  return nullptr;
667  if (PredL != NewCC)
668  CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst));
669  if (PredR != NewCC)
670  ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
671 
672  // If there is a conflict, we should actually return a false for the
673  // whole construct.
674  if (((BCst->getValue() & DCst->getValue()) &
675  (CCst->getValue() ^ ECst->getValue())).getBoolValue())
676  return ConstantInt::get(LHS->getType(), !IsAnd);
677 
678  Value *NewOr1 = Builder.CreateOr(B, D);
679  Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
680  Value *NewAnd = Builder.CreateAnd(A, NewOr1);
681  return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
682  }
683 
684  return nullptr;
685 }
686 
687 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
688 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
689 /// If \p Inverted is true then the check is for the inverted range, e.g.
690 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
692  bool Inverted) {
693  // Check the lower range comparison, e.g. x >= 0
694  // InstCombine already ensured that if there is a constant it's on the RHS.
695  ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
696  if (!RangeStart)
697  return nullptr;
698 
699  ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
700  Cmp0->getPredicate());
701 
702  // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
703  if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
704  (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
705  return nullptr;
706 
707  ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
708  Cmp1->getPredicate());
709 
710  Value *Input = Cmp0->getOperand(0);
711  Value *RangeEnd;
712  if (Cmp1->getOperand(0) == Input) {
713  // For the upper range compare we have: icmp x, n
714  RangeEnd = Cmp1->getOperand(1);
715  } else if (Cmp1->getOperand(1) == Input) {
716  // For the upper range compare we have: icmp n, x
717  RangeEnd = Cmp1->getOperand(0);
718  Pred1 = ICmpInst::getSwappedPredicate(Pred1);
719  } else {
720  return nullptr;
721  }
722 
723  // Check the upper range comparison, e.g. x < n
724  ICmpInst::Predicate NewPred;
725  switch (Pred1) {
726  case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
727  case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
728  default: return nullptr;
729  }
730 
731  // This simplification is only valid if the upper range is not negative.
732  KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1);
733  if (!Known.isNonNegative())
734  return nullptr;
735 
736  if (Inverted)
737  NewPred = ICmpInst::getInversePredicate(NewPred);
738 
739  return Builder.CreateICmp(NewPred, Input, RangeEnd);
740 }
741 
742 static Value *
744  bool JoinedByAnd,
746  Value *X = LHS->getOperand(0);
747  if (X != RHS->getOperand(0))
748  return nullptr;
749 
750  const APInt *C1, *C2;
751  if (!match(LHS->getOperand(1), m_APInt(C1)) ||
752  !match(RHS->getOperand(1), m_APInt(C2)))
753  return nullptr;
754 
755  // We only handle (X != C1 && X != C2) and (X == C1 || X == C2).
756  ICmpInst::Predicate Pred = LHS->getPredicate();
757  if (Pred != RHS->getPredicate())
758  return nullptr;
759  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
760  return nullptr;
761  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
762  return nullptr;
763 
764  // The larger unsigned constant goes on the right.
765  if (C1->ugt(*C2))
766  std::swap(C1, C2);
767 
768  APInt Xor = *C1 ^ *C2;
769  if (Xor.isPowerOf2()) {
770  // If LHSC and RHSC differ by only one bit, then set that bit in X and
771  // compare against the larger constant:
772  // (X == C1 || X == C2) --> (X | (C1 ^ C2)) == C2
773  // (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2
774  // We choose an 'or' with a Pow2 constant rather than the inverse mask with
775  // 'and' because that may lead to smaller codegen from a smaller constant.
776  Value *Or = Builder.CreateOr(X, ConstantInt::get(X->getType(), Xor));
777  return Builder.CreateICmp(Pred, Or, ConstantInt::get(X->getType(), *C2));
778  }
779 
780  // Special case: get the ordering right when the values wrap around zero.
781  // Ie, we assumed the constants were unsigned when swapping earlier.
782  if (C1->isNullValue() && C2->isAllOnesValue())
783  std::swap(C1, C2);
784 
785  if (*C1 == *C2 - 1) {
786  // (X == 13 || X == 14) --> X - 13 <=u 1
787  // (X != 13 && X != 14) --> X - 13 >u 1
788  // An 'add' is the canonical IR form, so favor that over a 'sub'.
789  Value *Add = Builder.CreateAdd(X, ConstantInt::get(X->getType(), -(*C1)));
790  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
791  return Builder.CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
792  }
793 
794  return nullptr;
795 }
796 
797 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
798 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
799 Value *InstCombinerImpl::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS,
800  ICmpInst *RHS,
801  BinaryOperator &Logic) {
802  bool JoinedByAnd = Logic.getOpcode() == Instruction::And;
803  assert((JoinedByAnd || Logic.getOpcode() == Instruction::Or) &&
804  "Wrong opcode");
805  ICmpInst::Predicate Pred = LHS->getPredicate();
806  if (Pred != RHS->getPredicate())
807  return nullptr;
808  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
809  return nullptr;
810  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
811  return nullptr;
812 
813  if (!match(LHS->getOperand(1), m_Zero()) ||
814  !match(RHS->getOperand(1), m_Zero()))
815  return nullptr;
816 
817  Value *A, *B, *C, *D;
818  if (match(LHS->getOperand(0), m_And(m_Value(A), m_Value(B))) &&
819  match(RHS->getOperand(0), m_And(m_Value(C), m_Value(D)))) {
820  if (A == D || B == D)
821  std::swap(C, D);
822  if (B == C)
823  std::swap(A, B);
824 
825  if (A == C &&
826  isKnownToBeAPowerOfTwo(B, false, 0, &Logic) &&
827  isKnownToBeAPowerOfTwo(D, false, 0, &Logic)) {
828  Value *Mask = Builder.CreateOr(B, D);
829  Value *Masked = Builder.CreateAnd(A, Mask);
830  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
831  return Builder.CreateICmp(NewPred, Masked, Mask);
832  }
833  }
834 
835  return nullptr;
836 }
837 
838 /// General pattern:
839 /// X & Y
840 ///
841 /// Where Y is checking that all the high bits (covered by a mask 4294967168)
842 /// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0
843 /// Pattern can be one of:
844 /// %t = add i32 %arg, 128
845 /// %r = icmp ult i32 %t, 256
846 /// Or
847 /// %t0 = shl i32 %arg, 24
848 /// %t1 = ashr i32 %t0, 24
849 /// %r = icmp eq i32 %t1, %arg
850 /// Or
851 /// %t0 = trunc i32 %arg to i8
852 /// %t1 = sext i8 %t0 to i32
853 /// %r = icmp eq i32 %t1, %arg
854 /// This pattern is a signed truncation check.
855 ///
856 /// And X is checking that some bit in that same mask is zero.
857 /// I.e. can be one of:
858 /// %r = icmp sgt i32 %arg, -1
859 /// Or
860 /// %t = and i32 %arg, 2147483648
861 /// %r = icmp eq i32 %t, 0
862 ///
863 /// Since we are checking that all the bits in that mask are the same,
864 /// and a particular bit is zero, what we are really checking is that all the
865 /// masked bits are zero.
866 /// So this should be transformed to:
867 /// %r = icmp ult i32 %arg, 128
869  Instruction &CxtI,
871  assert(CxtI.getOpcode() == Instruction::And);
872 
873  // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two)
874  auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X,
875  APInt &SignBitMask) -> bool {
876  CmpInst::Predicate Pred;
877  const APInt *I01, *I1; // powers of two; I1 == I01 << 1
878  if (!(match(ICmp,
879  m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) &&
880  Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1))
881  return false;
882  // Which bit is the new sign bit as per the 'signed truncation' pattern?
883  SignBitMask = *I01;
884  return true;
885  };
886 
887  // One icmp needs to be 'signed truncation check'.
888  // We need to match this first, else we will mismatch commutative cases.
889  Value *X1;
890  APInt HighestBit;
891  ICmpInst *OtherICmp;
892  if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit))
893  OtherICmp = ICmp0;
894  else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit))
895  OtherICmp = ICmp1;
896  else
897  return nullptr;
898 
899  assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)");
900 
901  // Try to match/decompose into: icmp eq (X & Mask), 0
902  auto tryToDecompose = [](ICmpInst *ICmp, Value *&X,
903  APInt &UnsetBitsMask) -> bool {
904  CmpInst::Predicate Pred = ICmp->getPredicate();
905  // Can it be decomposed into icmp eq (X & Mask), 0 ?
906  if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1),
907  Pred, X, UnsetBitsMask,
908  /*LookThroughTrunc=*/false) &&
909  Pred == ICmpInst::ICMP_EQ)
910  return true;
911  // Is it icmp eq (X & Mask), 0 already?
912  const APInt *Mask;
913  if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) &&
914  Pred == ICmpInst::ICMP_EQ) {
915  UnsetBitsMask = *Mask;
916  return true;
917  }
918  return false;
919  };
920 
921  // And the other icmp needs to be decomposable into a bit test.
922  Value *X0;
923  APInt UnsetBitsMask;
924  if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask))
925  return nullptr;
926 
927  assert(!UnsetBitsMask.isNullValue() && "empty mask makes no sense.");
928 
929  // Are they working on the same value?
930  Value *X;
931  if (X1 == X0) {
932  // Ok as is.
933  X = X1;
934  } else if (match(X0, m_Trunc(m_Specific(X1)))) {
935  UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits());
936  X = X1;
937  } else
938  return nullptr;
939 
940  // So which bits should be uniform as per the 'signed truncation check'?
941  // (all the bits starting with (i.e. including) HighestBit)
942  APInt SignBitsMask = ~(HighestBit - 1U);
943 
944  // UnsetBitsMask must have some common bits with SignBitsMask,
945  if (!UnsetBitsMask.intersects(SignBitsMask))
946  return nullptr;
947 
948  // Does UnsetBitsMask contain any bits outside of SignBitsMask?
949  if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) {
950  APInt OtherHighestBit = (~UnsetBitsMask) + 1U;
951  if (!OtherHighestBit.isPowerOf2())
952  return nullptr;
953  HighestBit = APIntOps::umin(HighestBit, OtherHighestBit);
954  }
955  // Else, if it does not, then all is ok as-is.
956 
957  // %r = icmp ult %X, SignBit
958  return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit),
959  CxtI.getName() + ".simplified");
960 }
961 
962 /// Reduce a pair of compares that check if a value has exactly 1 bit set.
963 static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd,
965  // Handle 'and' / 'or' commutation: make the equality check the first operand.
966  if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE)
967  std::swap(Cmp0, Cmp1);
968  else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ)
969  std::swap(Cmp0, Cmp1);
970 
971  // (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1
972  CmpInst::Predicate Pred0, Pred1;
973  Value *X;
974  if (JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
975  match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
976  m_SpecificInt(2))) &&
977  Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT) {
978  Value *CtPop = Cmp1->getOperand(0);
979  return Builder.CreateICmpEQ(CtPop, ConstantInt::get(CtPop->getType(), 1));
980  }
981  // (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1
982  if (!JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
983  match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
984  m_SpecificInt(1))) &&
985  Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_UGT) {
986  Value *CtPop = Cmp1->getOperand(0);
987  return Builder.CreateICmpNE(CtPop, ConstantInt::get(CtPop->getType(), 1));
988  }
989  return nullptr;
990 }
991 
992 /// Commuted variants are assumed to be handled by calling this function again
993 /// with the parameters swapped.
995  ICmpInst *UnsignedICmp, bool IsAnd,
996  const SimplifyQuery &Q,
998  Value *ZeroCmpOp;
999  ICmpInst::Predicate EqPred;
1000  if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(ZeroCmpOp), m_Zero())) ||
1001  !ICmpInst::isEquality(EqPred))
1002  return nullptr;
1003 
1004  auto IsKnownNonZero = [&](Value *V) {
1005  return isKnownNonZero(V, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1006  };
1007 
1008  ICmpInst::Predicate UnsignedPred;
1009 
1010  Value *A, *B;
1011  if (match(UnsignedICmp,
1012  m_c_ICmp(UnsignedPred, m_Specific(ZeroCmpOp), m_Value(A))) &&
1013  match(ZeroCmpOp, m_c_Add(m_Specific(A), m_Value(B))) &&
1014  (ZeroICmp->hasOneUse() || UnsignedICmp->hasOneUse())) {
1015  auto GetKnownNonZeroAndOther = [&](Value *&NonZero, Value *&Other) {
1016  if (!IsKnownNonZero(NonZero))
1017  std::swap(NonZero, Other);
1018  return IsKnownNonZero(NonZero);
1019  };
1020 
1021  // Given ZeroCmpOp = (A + B)
1022  // ZeroCmpOp <= A && ZeroCmpOp != 0 --> (0-B) < A
1023  // ZeroCmpOp > A || ZeroCmpOp == 0 --> (0-B) >= A
1024  //
1025  // ZeroCmpOp < A && ZeroCmpOp != 0 --> (0-X) < Y iff
1026  // ZeroCmpOp >= A || ZeroCmpOp == 0 --> (0-X) >= Y iff
1027  // with X being the value (A/B) that is known to be non-zero,
1028  // and Y being remaining value.
1029  if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
1030  IsAnd)
1031  return Builder.CreateICmpULT(Builder.CreateNeg(B), A);
1032  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE &&
1033  IsAnd && GetKnownNonZeroAndOther(B, A))
1034  return Builder.CreateICmpULT(Builder.CreateNeg(B), A);
1035  if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
1036  !IsAnd)
1037  return Builder.CreateICmpUGE(Builder.CreateNeg(B), A);
1038  if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_EQ &&
1039  !IsAnd && GetKnownNonZeroAndOther(B, A))
1040  return Builder.CreateICmpUGE(Builder.CreateNeg(B), A);
1041  }
1042 
1043  Value *Base, *Offset;
1044  if (!match(ZeroCmpOp, m_Sub(m_Value(Base), m_Value(Offset))))
1045  return nullptr;
1046 
1047  if (!match(UnsignedICmp,
1048  m_c_ICmp(UnsignedPred, m_Specific(Base), m_Specific(Offset))) ||
1049  !ICmpInst::isUnsigned(UnsignedPred))
1050  return nullptr;
1051 
1052  // Base >=/> Offset && (Base - Offset) != 0 <--> Base > Offset
1053  // (no overflow and not null)
1054  if ((UnsignedPred == ICmpInst::ICMP_UGE ||
1055  UnsignedPred == ICmpInst::ICMP_UGT) &&
1056  EqPred == ICmpInst::ICMP_NE && IsAnd)
1057  return Builder.CreateICmpUGT(Base, Offset);
1058 
1059  // Base <=/< Offset || (Base - Offset) == 0 <--> Base <= Offset
1060  // (overflow or null)
1061  if ((UnsignedPred == ICmpInst::ICMP_ULE ||
1062  UnsignedPred == ICmpInst::ICMP_ULT) &&
1063  EqPred == ICmpInst::ICMP_EQ && !IsAnd)
1064  return Builder.CreateICmpULE(Base, Offset);
1065 
1066  // Base <= Offset && (Base - Offset) != 0 --> Base < Offset
1067  if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
1068  IsAnd)
1069  return Builder.CreateICmpULT(Base, Offset);
1070 
1071  // Base > Offset || (Base - Offset) == 0 --> Base >= Offset
1072  if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
1073  !IsAnd)
1074  return Builder.CreateICmpUGE(Base, Offset);
1075 
1076  return nullptr;
1077 }
1078 
1079 /// Reduce logic-of-compares with equality to a constant by substituting a
1080 /// common operand with the constant. Callers are expected to call this with
1081 /// Cmp0/Cmp1 switched to handle logic op commutativity.
1083  BinaryOperator &Logic,
1085  const SimplifyQuery &Q) {
1086  bool IsAnd = Logic.getOpcode() == Instruction::And;
1087  assert((IsAnd || Logic.getOpcode() == Instruction::Or) && "Wrong logic op");
1088 
1089  // Match an equality compare with a non-poison constant as Cmp0.
1090  // Also, give up if the compare can be constant-folded to avoid looping.
1091  ICmpInst::Predicate Pred0;
1092  Value *X;
1093  Constant *C;
1094  if (!match(Cmp0, m_ICmp(Pred0, m_Value(X), m_Constant(C))) ||
1095  !isGuaranteedNotToBeUndefOrPoison(C) || isa<Constant>(X))
1096  return nullptr;
1097  if ((IsAnd && Pred0 != ICmpInst::ICMP_EQ) ||
1098  (!IsAnd && Pred0 != ICmpInst::ICMP_NE))
1099  return nullptr;
1100 
1101  // The other compare must include a common operand (X). Canonicalize the
1102  // common operand as operand 1 (Pred1 is swapped if the common operand was
1103  // operand 0).
1104  Value *Y;
1105  ICmpInst::Predicate Pred1;
1106  if (!match(Cmp1, m_c_ICmp(Pred1, m_Value(Y), m_Deferred(X))))
1107  return nullptr;
1108 
1109  // Replace variable with constant value equivalence to remove a variable use:
1110  // (X == C) && (Y Pred1 X) --> (X == C) && (Y Pred1 C)
1111  // (X != C) || (Y Pred1 X) --> (X != C) || (Y Pred1 C)
1112  // Can think of the 'or' substitution with the 'and' bool equivalent:
1113  // A || B --> A || (!A && B)
1114  Value *SubstituteCmp = SimplifyICmpInst(Pred1, Y, C, Q);
1115  if (!SubstituteCmp) {
1116  // If we need to create a new instruction, require that the old compare can
1117  // be removed.
1118  if (!Cmp1->hasOneUse())
1119  return nullptr;
1120  SubstituteCmp = Builder.CreateICmp(Pred1, Y, C);
1121  }
1122  return Builder.CreateBinOp(Logic.getOpcode(), Cmp0, SubstituteCmp);
1123 }
1124 
1125 /// Fold (icmp)&(icmp) if possible.
1126 Value *InstCombinerImpl::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1127  BinaryOperator &And) {
1128  const SimplifyQuery Q = SQ.getWithInstruction(&And);
1129 
1130  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
1131  // if K1 and K2 are a one-bit mask.
1132  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, And))
1133  return V;
1134 
1135  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1136 
1137  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
1138  if (predicatesFoldable(PredL, PredR)) {
1139  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1140  LHS->getOperand(1) == RHS->getOperand(0))
1141  LHS->swapOperands();
1142  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1143  LHS->getOperand(1) == RHS->getOperand(1)) {
1144  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1145  unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
1146  bool IsSigned = LHS->isSigned() || RHS->isSigned();
1147  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
1148  }
1149  }
1150 
1151  // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
1152  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
1153  return V;
1154 
1155  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, And, Builder, Q))
1156  return V;
1157  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, And, Builder, Q))
1158  return V;
1159 
1160  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
1161  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
1162  return V;
1163 
1164  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
1165  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
1166  return V;
1167 
1168  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
1169  return V;
1170 
1171  if (Value *V = foldSignedTruncationCheck(LHS, RHS, And, Builder))
1172  return V;
1173 
1174  if (Value *V = foldIsPowerOf2(LHS, RHS, true /* JoinedByAnd */, Builder))
1175  return V;
1176 
1177  if (Value *X =
1178  foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/true, Q, Builder))
1179  return X;
1180  if (Value *X =
1181  foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/true, Q, Builder))
1182  return X;
1183 
1184  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
1185  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1186 
1187  ConstantInt *LHSC, *RHSC;
1188  if (!match(LHS->getOperand(1), m_ConstantInt(LHSC)) ||
1189  !match(RHS->getOperand(1), m_ConstantInt(RHSC)))
1190  return nullptr;
1191 
1192  if (LHSC == RHSC && PredL == PredR) {
1193  // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
1194  // where C is a power of 2 or
1195  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
1196  if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
1197  (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
1198  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
1199  return Builder.CreateICmp(PredL, NewOr, LHSC);
1200  }
1201  }
1202 
1203  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
1204  // where CMAX is the all ones value for the truncated type,
1205  // iff the lower bits of C2 and CA are zero.
1206  if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
1207  RHS->hasOneUse()) {
1208  Value *V;
1209  ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
1210 
1211  // (trunc x) == C1 & (and x, CA) == C2
1212  // (and x, CA) == C2 & (trunc x) == C1
1213  if (match(RHS0, m_Trunc(m_Value(V))) &&
1214  match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1215  SmallC = RHSC;
1216  BigC = LHSC;
1217  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
1218  match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1219  SmallC = LHSC;
1220  BigC = RHSC;
1221  }
1222 
1223  if (SmallC && BigC) {
1224  unsigned BigBitSize = BigC->getType()->getBitWidth();
1225  unsigned SmallBitSize = SmallC->getType()->getBitWidth();
1226 
1227  // Check that the low bits are zero.
1228  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
1229  if ((Low & AndC->getValue()).isNullValue() &&
1230  (Low & BigC->getValue()).isNullValue()) {
1231  Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue());
1232  APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
1233  Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
1234  return Builder.CreateICmp(PredL, NewAnd, NewVal);
1235  }
1236  }
1237  }
1238 
1239  // From here on, we only handle:
1240  // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
1241  if (LHS0 != RHS0)
1242  return nullptr;
1243 
1244  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1245  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1246  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1247  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1248  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1249  return nullptr;
1250 
1251  // We can't fold (ugt x, C) & (sgt x, C2).
1252  if (!predicatesFoldable(PredL, PredR))
1253  return nullptr;
1254 
1255  // Ensure that the larger constant is on the RHS.
1256  bool ShouldSwap;
1257  if (CmpInst::isSigned(PredL) ||
1258  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1259  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1260  else
1261  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1262 
1263  if (ShouldSwap) {
1264  std::swap(LHS, RHS);
1265  std::swap(LHSC, RHSC);
1266  std::swap(PredL, PredR);
1267  }
1268 
1269  // At this point, we know we have two icmp instructions
1270  // comparing a value against two constants and and'ing the result
1271  // together. Because of the above check, we know that we only have
1272  // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
1273  // (from the icmp folding check above), that the two constants
1274  // are not equal and that the larger constant is on the RHS
1275  assert(LHSC != RHSC && "Compares not folded above?");
1276 
1277  switch (PredL) {
1278  default:
1279  llvm_unreachable("Unknown integer condition code!");
1280  case ICmpInst::ICMP_NE:
1281  switch (PredR) {
1282  default:
1283  llvm_unreachable("Unknown integer condition code!");
1284  case ICmpInst::ICMP_ULT:
1285  // (X != 13 & X u< 14) -> X < 13
1286  if (LHSC->getValue() == (RHSC->getValue() - 1))
1287  return Builder.CreateICmpULT(LHS0, LHSC);
1288  if (LHSC->isZero()) // (X != 0 & X u< C) -> X-1 u< C-1
1289  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1290  false, true);
1291  break; // (X != 13 & X u< 15) -> no change
1292  case ICmpInst::ICMP_SLT:
1293  // (X != 13 & X s< 14) -> X < 13
1294  if (LHSC->getValue() == (RHSC->getValue() - 1))
1295  return Builder.CreateICmpSLT(LHS0, LHSC);
1296  // (X != INT_MIN & X s< C) -> X-(INT_MIN+1) u< (C-(INT_MIN+1))
1297  if (LHSC->isMinValue(true))
1298  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1299  true, true);
1300  break; // (X != 13 & X s< 15) -> no change
1301  case ICmpInst::ICMP_NE:
1302  // Potential folds for this case should already be handled.
1303  break;
1304  }
1305  break;
1306  case ICmpInst::ICMP_UGT:
1307  switch (PredR) {
1308  default:
1309  llvm_unreachable("Unknown integer condition code!");
1310  case ICmpInst::ICMP_NE:
1311  // (X u> 13 & X != 14) -> X u> 14
1312  if (RHSC->getValue() == (LHSC->getValue() + 1))
1313  return Builder.CreateICmp(PredL, LHS0, RHSC);
1314  // X u> C & X != UINT_MAX -> (X-(C+1)) u< UINT_MAX-(C+1)
1315  if (RHSC->isMaxValue(false))
1316  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1317  false, true);
1318  break; // (X u> 13 & X != 15) -> no change
1319  case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) u< 1
1320  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1321  false, true);
1322  }
1323  break;
1324  case ICmpInst::ICMP_SGT:
1325  switch (PredR) {
1326  default:
1327  llvm_unreachable("Unknown integer condition code!");
1328  case ICmpInst::ICMP_NE:
1329  // (X s> 13 & X != 14) -> X s> 14
1330  if (RHSC->getValue() == (LHSC->getValue() + 1))
1331  return Builder.CreateICmp(PredL, LHS0, RHSC);
1332  // X s> C & X != INT_MAX -> (X-(C+1)) u< INT_MAX-(C+1)
1333  if (RHSC->isMaxValue(true))
1334  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1335  true, true);
1336  break; // (X s> 13 & X != 15) -> no change
1337  case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) u< 1
1338  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
1339  true);
1340  }
1341  break;
1342  }
1343 
1344  return nullptr;
1345 }
1346 
1347 Value *InstCombinerImpl::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS,
1348  bool IsAnd) {
1349  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1350  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1351  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1352 
1353  if (LHS0 == RHS1 && RHS0 == LHS1) {
1354  // Swap RHS operands to match LHS.
1355  PredR = FCmpInst::getSwappedPredicate(PredR);
1356  std::swap(RHS0, RHS1);
1357  }
1358 
1359  // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1360  // Suppose the relation between x and y is R, where R is one of
1361  // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1362  // testing the desired relations.
1363  //
1364  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1365  // bool(R & CC0) && bool(R & CC1)
1366  // = bool((R & CC0) & (R & CC1))
1367  // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1368  //
1369  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1370  // bool(R & CC0) || bool(R & CC1)
1371  // = bool((R & CC0) | (R & CC1))
1372  // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1373  if (LHS0 == RHS0 && LHS1 == RHS1) {
1374  unsigned FCmpCodeL = getFCmpCode(PredL);
1375  unsigned FCmpCodeR = getFCmpCode(PredR);
1376  unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1377  return getFCmpValue(NewPred, LHS0, LHS1, Builder);
1378  }
1379 
1380  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1381  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1382  if (LHS0->getType() != RHS0->getType())
1383  return nullptr;
1384 
1385  // FCmp canonicalization ensures that (fcmp ord/uno X, X) and
1386  // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0).
1387  if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP()))
1388  // Ignore the constants because they are obviously not NANs:
1389  // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y)
1390  // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y)
1391  return Builder.CreateFCmp(PredL, LHS0, RHS0);
1392  }
1393 
1394  return nullptr;
1395 }
1396 
1397 /// This a limited reassociation for a special case (see above) where we are
1398 /// checking if two values are either both NAN (unordered) or not-NAN (ordered).
1399 /// This could be handled more generally in '-reassociation', but it seems like
1400 /// an unlikely pattern for a large number of logic ops and fcmps.
1403  Instruction::BinaryOps Opcode = BO.getOpcode();
1404  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1405  "Expecting and/or op for fcmp transform");
1406 
1407  // There are 4 commuted variants of the pattern. Canonicalize operands of this
1408  // logic op so an fcmp is operand 0 and a matching logic op is operand 1.
1409  Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1), *X;
1410  FCmpInst::Predicate Pred;
1411  if (match(Op1, m_FCmp(Pred, m_Value(), m_AnyZeroFP())))
1412  std::swap(Op0, Op1);
1413 
1414  // Match inner binop and the predicate for combining 2 NAN checks into 1.
1415  BinaryOperator *BO1;
1416  FCmpInst::Predicate NanPred = Opcode == Instruction::And ? FCmpInst::FCMP_ORD
1418  if (!match(Op0, m_FCmp(Pred, m_Value(X), m_AnyZeroFP())) || Pred != NanPred ||
1419  !match(Op1, m_BinOp(BO1)) || BO1->getOpcode() != Opcode)
1420  return nullptr;
1421 
1422  // The inner logic op must have a matching fcmp operand.
1423  Value *BO10 = BO1->getOperand(0), *BO11 = BO1->getOperand(1), *Y;
1424  if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1425  Pred != NanPred || X->getType() != Y->getType())
1426  std::swap(BO10, BO11);
1427 
1428  if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1429  Pred != NanPred || X->getType() != Y->getType())
1430  return nullptr;
1431 
1432  // and (fcmp ord X, 0), (and (fcmp ord Y, 0), Z) --> and (fcmp ord X, Y), Z
1433  // or (fcmp uno X, 0), (or (fcmp uno Y, 0), Z) --> or (fcmp uno X, Y), Z
1434  Value *NewFCmp = Builder.CreateFCmp(Pred, X, Y);
1435  if (auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) {
1436  // Intersect FMF from the 2 source fcmps.
1437  NewFCmpInst->copyIRFlags(Op0);
1438  NewFCmpInst->andIRFlags(BO10);
1439  }
1440  return BinaryOperator::Create(Opcode, NewFCmp, BO11);
1441 }
1442 
1443 /// Match De Morgan's Laws:
1444 /// (~A & ~B) == (~(A | B))
1445 /// (~A | ~B) == (~(A & B))
1448  auto Opcode = I.getOpcode();
1449  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1450  "Trying to match De Morgan's Laws with something other than and/or");
1451 
1452  // Flip the logic operation.
1453  Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1454 
1455  Value *A, *B;
1456  if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) &&
1457  match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) &&
1458  !InstCombiner::isFreeToInvert(A, A->hasOneUse()) &&
1459  !InstCombiner::isFreeToInvert(B, B->hasOneUse())) {
1460  Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan");
1461  return BinaryOperator::CreateNot(AndOr);
1462  }
1463 
1464  return nullptr;
1465 }
1466 
1467 bool InstCombinerImpl::shouldOptimizeCast(CastInst *CI) {
1468  Value *CastSrc = CI->getOperand(0);
1469 
1470  // Noop casts and casts of constants should be eliminated trivially.
1471  if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1472  return false;
1473 
1474  // If this cast is paired with another cast that can be eliminated, we prefer
1475  // to have it eliminated.
1476  if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1477  if (isEliminableCastPair(PrecedingCI, CI))
1478  return false;
1479 
1480  return true;
1481 }
1482 
1483 /// Fold {and,or,xor} (cast X), C.
1486  Constant *C = dyn_cast<Constant>(Logic.getOperand(1));
1487  if (!C)
1488  return nullptr;
1489 
1490  auto LogicOpc = Logic.getOpcode();
1491  Type *DestTy = Logic.getType();
1492  Type *SrcTy = Cast->getSrcTy();
1493 
1494  // Move the logic operation ahead of a zext or sext if the constant is
1495  // unchanged in the smaller source type. Performing the logic in a smaller
1496  // type may provide more information to later folds, and the smaller logic
1497  // instruction may be cheaper (particularly in the case of vectors).
1498  Value *X;
1499  if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1500  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1501  Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1502  if (ZextTruncC == C) {
1503  // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1504  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1505  return new ZExtInst(NewOp, DestTy);
1506  }
1507  }
1508 
1509  if (match(Cast, m_OneUse(m_SExt(m_Value(X))))) {
1510  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1511  Constant *SextTruncC = ConstantExpr::getSExt(TruncC, DestTy);
1512  if (SextTruncC == C) {
1513  // LogicOpc (sext X), C --> sext (LogicOpc X, C)
1514  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1515  return new SExtInst(NewOp, DestTy);
1516  }
1517  }
1518 
1519  return nullptr;
1520 }
1521 
1522 /// Fold {and,or,xor} (cast X), Y.
1523 Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) {
1524  auto LogicOpc = I.getOpcode();
1525  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1526 
1527  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1528  CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1529  if (!Cast0)
1530  return nullptr;
1531 
1532  // This must be a cast from an integer or integer vector source type to allow
1533  // transformation of the logic operation to the source type.
1534  Type *DestTy = I.getType();
1535  Type *SrcTy = Cast0->getSrcTy();
1536  if (!SrcTy->isIntOrIntVectorTy())
1537  return nullptr;
1538 
1539  if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1540  return Ret;
1541 
1542  CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1543  if (!Cast1)
1544  return nullptr;
1545 
1546  // Both operands of the logic operation are casts. The casts must be of the
1547  // same type for reduction.
1548  auto CastOpcode = Cast0->getOpcode();
1549  if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
1550  return nullptr;
1551 
1552  Value *Cast0Src = Cast0->getOperand(0);
1553  Value *Cast1Src = Cast1->getOperand(0);
1554 
1555  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1556  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1557  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1558  I.getName());
1559  return CastInst::Create(CastOpcode, NewOp, DestTy);
1560  }
1561 
1562  // For now, only 'and'/'or' have optimizations after this.
1563  if (LogicOpc == Instruction::Xor)
1564  return nullptr;
1565 
1566  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1567  // cast is otherwise not optimizable. This happens for vector sexts.
1568  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1569  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1570  if (ICmp0 && ICmp1) {
1571  Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I)
1572  : foldOrOfICmps(ICmp0, ICmp1, I);
1573  if (Res)
1574  return CastInst::Create(CastOpcode, Res, DestTy);
1575  return nullptr;
1576  }
1577 
1578  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1579  // cast is otherwise not optimizable. This happens for vector sexts.
1580  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1581  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1582  if (FCmp0 && FCmp1)
1583  if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1584  return CastInst::Create(CastOpcode, R, DestTy);
1585 
1586  return nullptr;
1587 }
1588 
1591  assert(I.getOpcode() == Instruction::And);
1592  Value *Op0 = I.getOperand(0);
1593  Value *Op1 = I.getOperand(1);
1594  Value *A, *B;
1595 
1596  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1597  // (A | B) & ~(A & B) --> A ^ B
1598  // (A | B) & ~(B & A) --> A ^ B
1599  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1600  m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
1601  return BinaryOperator::CreateXor(A, B);
1602 
1603  // (A | ~B) & (~A | B) --> ~(A ^ B)
1604  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1605  // (~B | A) & (~A | B) --> ~(A ^ B)
1606  // (~B | A) & (B | ~A) --> ~(A ^ B)
1607  if (Op0->hasOneUse() || Op1->hasOneUse())
1608  if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
1609  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
1610  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1611 
1612  return nullptr;
1613 }
1614 
1617  assert(I.getOpcode() == Instruction::Or);
1618  Value *Op0 = I.getOperand(0);
1619  Value *Op1 = I.getOperand(1);
1620  Value *A, *B;
1621 
1622  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1623  // (A & B) | ~(A | B) --> ~(A ^ B)
1624  // (A & B) | ~(B | A) --> ~(A ^ B)
1625  if (Op0->hasOneUse() || Op1->hasOneUse())
1626  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1627  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1628  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1629 
1630  // Operand complexity canonicalization guarantees that the 'xor' is Op0.
1631  // (A ^ B) | ~(A | B) --> ~(A & B)
1632  // (A ^ B) | ~(B | A) --> ~(A & B)
1633  if (Op0->hasOneUse() || Op1->hasOneUse())
1634  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1635  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1636  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
1637 
1638  // (A & ~B) | (~A & B) --> A ^ B
1639  // (A & ~B) | (B & ~A) --> A ^ B
1640  // (~B & A) | (~A & B) --> A ^ B
1641  // (~B & A) | (B & ~A) --> A ^ B
1642  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1643  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1644  return BinaryOperator::CreateXor(A, B);
1645 
1646  return nullptr;
1647 }
1648 
1649 /// Return true if a constant shift amount is always less than the specified
1650 /// bit-width. If not, the shift could create poison in the narrower type.
1651 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1652  APInt Threshold(C->getType()->getScalarSizeInBits(), BitWidth);
1654 }
1655 
1656 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1657 /// a common zext operand: and (binop (zext X), C), (zext X).
1658 Instruction *InstCombinerImpl::narrowMaskedBinOp(BinaryOperator &And) {
1659  // This transform could also apply to {or, and, xor}, but there are better
1660  // folds for those cases, so we don't expect those patterns here. AShr is not
1661  // handled because it should always be transformed to LShr in this sequence.
1662  // The subtract transform is different because it has a constant on the left.
1663  // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1664  Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1665  Constant *C;
1666  if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1667  !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1668  !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1669  !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1670  !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1671  return nullptr;
1672 
1673  Value *X;
1674  if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1675  return nullptr;
1676 
1677  Type *Ty = And.getType();
1678  if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1679  return nullptr;
1680 
1681  // If we're narrowing a shift, the shift amount must be safe (less than the
1682  // width) in the narrower type. If the shift amount is greater, instsimplify
1683  // usually handles that case, but we can't guarantee/assert it.
1684  Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1685  if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1686  if (!canNarrowShiftAmt(C, X->getType()->getScalarSizeInBits()))
1687  return nullptr;
1688 
1689  // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1690  // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1691  Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1692  Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1693  : Builder.CreateBinOp(Opc, X, NewC);
1694  return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1695 }
1696 
1697 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1698 // here. We should standardize that construct where it is needed or choose some
1699 // other way to ensure that commutated variants of patterns are not missed.
1701  Type *Ty = I.getType();
1702 
1703  if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1),
1704  SQ.getWithInstruction(&I)))
1705  return replaceInstUsesWith(I, V);
1706 
1707  if (SimplifyAssociativeOrCommutative(I))
1708  return &I;
1709 
1710  if (Instruction *X = foldVectorBinop(I))
1711  return X;
1712 
1713  // See if we can simplify any instructions used by the instruction whose sole
1714  // purpose is to compute bits we don't care about.
1715  if (SimplifyDemandedInstructionBits(I))
1716  return &I;
1717 
1718  // Do this before using distributive laws to catch simple and/or/not patterns.
1720  return Xor;
1721 
1722  // (A|B)&(A|C) -> A|(B&C) etc
1723  if (Value *V = SimplifyUsingDistributiveLaws(I))
1724  return replaceInstUsesWith(I, V);
1725 
1726  if (Value *V = SimplifyBSwap(I, Builder))
1727  return replaceInstUsesWith(I, V);
1728 
1729  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1730 
1731  Value *X, *Y;
1732  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
1733  match(Op1, m_One())) {
1734  // (1 << X) & 1 --> zext(X == 0)
1735  // (1 >> X) & 1 --> zext(X == 0)
1736  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, 0));
1737  return new ZExtInst(IsZero, Ty);
1738  }
1739 
1740  const APInt *C;
1741  if (match(Op1, m_APInt(C))) {
1742  const APInt *XorC;
1743  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
1744  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1745  Constant *NewC = ConstantInt::get(Ty, *C & *XorC);
1746  Value *And = Builder.CreateAnd(X, Op1);
1747  And->takeName(Op0);
1748  return BinaryOperator::CreateXor(And, NewC);
1749  }
1750 
1751  const APInt *OrC;
1752  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
1753  // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
1754  // NOTE: This reduces the number of bits set in the & mask, which
1755  // can expose opportunities for store narrowing for scalars.
1756  // NOTE: SimplifyDemandedBits should have already removed bits from C1
1757  // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
1758  // above, but this feels safer.
1759  APInt Together = *C & *OrC;
1760  Value *And = Builder.CreateAnd(X, ConstantInt::get(Ty, Together ^ *C));
1761  And->takeName(Op0);
1762  return BinaryOperator::CreateOr(And, ConstantInt::get(Ty, Together));
1763  }
1764 
1765  // If the mask is only needed on one incoming arm, push the 'and' op up.
1766  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
1767  match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
1768  APInt NotAndMask(~(*C));
1769  BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
1770  if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
1771  // Not masking anything out for the LHS, move mask to RHS.
1772  // and ({x}or X, Y), C --> {x}or X, (and Y, C)
1773  Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
1774  return BinaryOperator::Create(BinOp, X, NewRHS);
1775  }
1776  if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
1777  // Not masking anything out for the RHS, move mask to LHS.
1778  // and ({x}or X, Y), C --> {x}or (and X, C), Y
1779  Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
1780  return BinaryOperator::Create(BinOp, NewLHS, Y);
1781  }
1782  }
1783 
1784  unsigned Width = Ty->getScalarSizeInBits();
1785  const APInt *ShiftC;
1786  if (match(Op0, m_OneUse(m_SExt(m_AShr(m_Value(X), m_APInt(ShiftC)))))) {
1787  if (*C == APInt::getLowBitsSet(Width, Width - ShiftC->getZExtValue())) {
1788  // We are clearing high bits that were potentially set by sext+ashr:
1789  // and (sext (ashr X, ShiftC)), C --> lshr (sext X), ShiftC
1790  Value *Sext = Builder.CreateSExt(X, Ty);
1791  Constant *ShAmtC = ConstantInt::get(Ty, ShiftC->zext(Width));
1792  return BinaryOperator::CreateLShr(Sext, ShAmtC);
1793  }
1794  }
1795 
1796  const APInt *AddC;
1797  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC)))) {
1798  // If we add zeros to every bit below a mask, the add has no effect:
1799  // (X + AddC) & LowMaskC --> X & LowMaskC
1800  unsigned Ctlz = C->countLeadingZeros();
1801  APInt LowMask(APInt::getLowBitsSet(Width, Width - Ctlz));
1802  if ((*AddC & LowMask).isNullValue())
1803  return BinaryOperator::CreateAnd(X, Op1);
1804 
1805  // If we are masking the result of the add down to exactly one bit and
1806  // the constant we are adding has no bits set below that bit, then the
1807  // add is flipping a single bit. Example:
1808  // (X + 4) & 4 --> (X & 4) ^ 4
1809  if (Op0->hasOneUse() && C->isPowerOf2() && (*AddC & (*C - 1)) == 0) {
1810  assert((*C & *AddC) != 0 && "Expected common bit");
1811  Value *NewAnd = Builder.CreateAnd(X, Op1);
1812  return BinaryOperator::CreateXor(NewAnd, Op1);
1813  }
1814  }
1815  }
1816 
1817  ConstantInt *AndRHS;
1818  if (match(Op1, m_ConstantInt(AndRHS))) {
1819  const APInt &AndRHSMask = AndRHS->getValue();
1820 
1821  // Optimize a variety of ((val OP C1) & C2) combinations...
1822  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1823  // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth
1824  // of X and OP behaves well when given trunc(C1) and X.
1825  // TODO: Do this for vectors by using m_APInt instead of m_ConstantInt.
1826  switch (Op0I->getOpcode()) {
1827  default:
1828  break;
1829  case Instruction::Xor:
1830  case Instruction::Or:
1831  case Instruction::Mul:
1832  case Instruction::Add:
1833  case Instruction::Sub:
1834  Value *X;
1835  ConstantInt *C1;
1836  // TODO: The one use restrictions could be relaxed a little if the AND
1837  // is going to be removed.
1839  m_ConstantInt(C1))))) {
1840  if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) {
1841  auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType());
1842  Value *BinOp;
1843  Value *Op0LHS = Op0I->getOperand(0);
1844  if (isa<ZExtInst>(Op0LHS))
1845  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), X, TruncC1);
1846  else
1847  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), TruncC1, X);
1848  auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType());
1849  auto *And = Builder.CreateAnd(BinOp, TruncC2);
1850  return new ZExtInst(And, Ty);
1851  }
1852  }
1853  }
1854  }
1855  }
1856 
1858  m_SignMask())) &&
1860  ICmpInst::Predicate::ICMP_EQ,
1861  APInt(Ty->getScalarSizeInBits(),
1862  Ty->getScalarSizeInBits() -
1863  X->getType()->getScalarSizeInBits())))) {
1864  auto *SExt = Builder.CreateSExt(X, Ty, X->getName() + ".signext");
1865  auto *SanitizedSignMask = cast<Constant>(Op1);
1866  // We must be careful with the undef elements of the sign bit mask, however:
1867  // the mask elt can be undef iff the shift amount for that lane was undef,
1868  // otherwise we need to sanitize undef masks to zero.
1869  SanitizedSignMask = Constant::replaceUndefsWith(
1870  SanitizedSignMask, ConstantInt::getNullValue(Ty->getScalarType()));
1871  SanitizedSignMask =
1872  Constant::mergeUndefsWith(SanitizedSignMask, cast<Constant>(Y));
1873  return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
1874  }
1875 
1876  if (Instruction *Z = narrowMaskedBinOp(I))
1877  return Z;
1878 
1879  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
1880  return FoldedLogic;
1881 
1882  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1883  return DeMorgan;
1884 
1885  {
1886  Value *A, *B, *C;
1887  // A & (A ^ B) --> A & ~B
1888  if (match(Op1, m_OneUse(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1889  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(B));
1890  // (A ^ B) & A --> A & ~B
1891  if (match(Op0, m_OneUse(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1892  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(B));
1893 
1894  // A & ~(A ^ B) --> A & B
1895  if (match(Op1, m_Not(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1896  return BinaryOperator::CreateAnd(Op0, B);
1897  // ~(A ^ B) & A --> A & B
1898  if (match(Op0, m_Not(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1899  return BinaryOperator::CreateAnd(Op1, B);
1900 
1901  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1902  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1903  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1904  if (Op1->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1905  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1906 
1907  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1908  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1909  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1910  if (Op0->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1911  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1912 
1913  // (A | B) & ((~A) ^ B) -> (A & B)
1914  // (A | B) & (B ^ (~A)) -> (A & B)
1915  // (B | A) & ((~A) ^ B) -> (A & B)
1916  // (B | A) & (B ^ (~A)) -> (A & B)
1917  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1918  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1919  return BinaryOperator::CreateAnd(A, B);
1920 
1921  // ((~A) ^ B) & (A | B) -> (A & B)
1922  // ((~A) ^ B) & (B | A) -> (A & B)
1923  // (B ^ (~A)) & (A | B) -> (A & B)
1924  // (B ^ (~A)) & (B | A) -> (A & B)
1925  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1926  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1927  return BinaryOperator::CreateAnd(A, B);
1928  }
1929 
1930  {
1931  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1932  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1933  if (LHS && RHS)
1934  if (Value *Res = foldAndOfICmps(LHS, RHS, I))
1935  return replaceInstUsesWith(I, Res);
1936 
1937  // TODO: Make this recursive; it's a little tricky because an arbitrary
1938  // number of 'and' instructions might have to be created.
1939  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1940  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1941  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1942  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1943  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1944  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1945  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1946  }
1947  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1948  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1949  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1950  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1951  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1952  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1953  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1954  }
1955  }
1956 
1957  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
1958  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
1959  if (Value *Res = foldLogicOfFCmps(LHS, RHS, true))
1960  return replaceInstUsesWith(I, Res);
1961 
1962  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
1963  return FoldedFCmps;
1964 
1965  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
1966  return CastedAnd;
1967 
1968  // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
1969  Value *A;
1970  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
1971  A->getType()->isIntOrIntVectorTy(1))
1972  return SelectInst::Create(A, Op1, Constant::getNullValue(Ty));
1973  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
1974  A->getType()->isIntOrIntVectorTy(1))
1975  return SelectInst::Create(A, Op0, Constant::getNullValue(Ty));
1976 
1977  // and(ashr(subNSW(Y, X), ScalarSizeInBits(Y)-1), X) --> X s> Y ? X : 0.
1978  if (match(&I, m_c_And(m_OneUse(m_AShr(
1979  m_NSWSub(m_Value(Y), m_Value(X)),
1980  m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
1981  m_Deferred(X)))) {
1982  Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
1983  return SelectInst::Create(NewICmpInst, X, ConstantInt::getNullValue(Ty));
1984  }
1985 
1986  // (~x) & y --> ~(x | (~y)) iff that gets rid of inversions
1987  if (sinkNotIntoOtherHandOfAndOrOr(I))
1988  return &I;
1989 
1990  return nullptr;
1991 }
1992 
1994  bool MatchBSwaps,
1995  bool MatchBitReversals) {
1997  if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
1998  Insts))
1999  return nullptr;
2000  Instruction *LastInst = Insts.pop_back_val();
2001  LastInst->removeFromParent();
2002 
2003  for (auto *Inst : Insts)
2004  Worklist.push(Inst);
2005  return LastInst;
2006 }
2007 
2008 /// Match UB-safe variants of the funnel shift intrinsic.
2010  // TODO: Can we reduce the code duplication between this and the related
2011  // rotate matching code under visitSelect and visitTrunc?
2012  unsigned Width = Or.getType()->getScalarSizeInBits();
2013 
2014  // First, find an or'd pair of opposite shifts:
2015  // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
2016  BinaryOperator *Or0, *Or1;
2017  if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
2018  !match(Or.getOperand(1), m_BinOp(Or1)))
2019  return nullptr;
2020 
2021  Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2022  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
2023  !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
2024  Or0->getOpcode() == Or1->getOpcode())
2025  return nullptr;
2026 
2027  // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
2028  if (Or0->getOpcode() == BinaryOperator::LShr) {
2029  std::swap(Or0, Or1);
2030  std::swap(ShVal0, ShVal1);
2031  std::swap(ShAmt0, ShAmt1);
2032  }
2033  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2034  Or1->getOpcode() == BinaryOperator::LShr &&
2035  "Illegal or(shift,shift) pair");
2036 
2037  // Match the shift amount operands for a funnel shift pattern. This always
2038  // matches a subtraction on the R operand.
2039  auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
2040  // Check for constant shift amounts that sum to the bitwidth.
2041  const APInt *LI, *RI;
2042  if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
2043  if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
2044  return ConstantInt::get(L->getType(), *LI);
2045 
2046  Constant *LC, *RC;
2047  if (match(L, m_Constant(LC)) && match(R, m_Constant(RC)) &&
2051  return ConstantExpr::mergeUndefsWith(LC, RC);
2052 
2053  // (shl ShVal, X) | (lshr ShVal, (Width - x)) iff X < Width.
2054  // We limit this to X < Width in case the backend re-expands the intrinsic,
2055  // and has to reintroduce a shift modulo operation (InstCombine might remove
2056  // it after this fold). This still doesn't guarantee that the final codegen
2057  // will match this original pattern.
2058  if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) {
2059  KnownBits KnownL = IC.computeKnownBits(L, /*Depth*/ 0, &Or);
2060  return KnownL.getMaxValue().ult(Width) ? L : nullptr;
2061  }
2062 
2063  // For non-constant cases, the following patterns currently only work for
2064  // rotation patterns.
2065  // TODO: Add general funnel-shift compatible patterns.
2066  if (ShVal0 != ShVal1)
2067  return nullptr;
2068 
2069  // For non-constant cases we don't support non-pow2 shift masks.
2070  // TODO: Is it worth matching urem as well?
2071  if (!isPowerOf2_32(Width))
2072  return nullptr;
2073 
2074  // The shift amount may be masked with negation:
2075  // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
2076  Value *X;
2077  unsigned Mask = Width - 1;
2078  if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
2080  return X;
2081 
2082  // Similar to above, but the shift amount may be extended after masking,
2083  // so return the extended value as the parameter for the intrinsic.
2084  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2086  m_SpecificInt(Mask))))
2087  return L;
2088 
2089  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2091  return L;
2092 
2093  return nullptr;
2094  };
2095 
2096  Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);
2097  bool IsFshl = true; // Sub on LSHR.
2098  if (!ShAmt) {
2099  ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);
2100  IsFshl = false; // Sub on SHL.
2101  }
2102  if (!ShAmt)
2103  return nullptr;
2104 
2105  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2106  Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
2107  return IntrinsicInst::Create(F, {ShVal0, ShVal1, ShAmt});
2108 }
2109 
2110 /// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
2113  assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
2114  Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
2115  Type *Ty = Or.getType();
2116 
2117  unsigned Width = Ty->getScalarSizeInBits();
2118  if ((Width & 1) != 0)
2119  return nullptr;
2120  unsigned HalfWidth = Width / 2;
2121 
2122  // Canonicalize zext (lower half) to LHS.
2123  if (!isa<ZExtInst>(Op0))
2124  std::swap(Op0, Op1);
2125 
2126  // Find lower/upper half.
2127  Value *LowerSrc, *ShlVal, *UpperSrc;
2128  const APInt *C;
2129  if (!match(Op0, m_OneUse(m_ZExt(m_Value(LowerSrc)))) ||
2130  !match(Op1, m_OneUse(m_Shl(m_Value(ShlVal), m_APInt(C)))) ||
2131  !match(ShlVal, m_OneUse(m_ZExt(m_Value(UpperSrc)))))
2132  return nullptr;
2133  if (*C != HalfWidth || LowerSrc->getType() != UpperSrc->getType() ||
2134  LowerSrc->getType()->getScalarSizeInBits() != HalfWidth)
2135  return nullptr;
2136 
2137  auto ConcatIntrinsicCalls = [&](Intrinsic::ID id, Value *Lo, Value *Hi) {
2138  Value *NewLower = Builder.CreateZExt(Lo, Ty);
2139  Value *NewUpper = Builder.CreateZExt(Hi, Ty);
2140  NewUpper = Builder.CreateShl(NewUpper, HalfWidth);
2141  Value *BinOp = Builder.CreateOr(NewLower, NewUpper);
2142  Function *F = Intrinsic::getDeclaration(Or.getModule(), id, Ty);
2143  return Builder.CreateCall(F, BinOp);
2144  };
2145 
2146  // BSWAP: Push the concat down, swapping the lower/upper sources.
2147  // concat(bswap(x),bswap(y)) -> bswap(concat(x,y))
2148  Value *LowerBSwap, *UpperBSwap;
2149  if (match(LowerSrc, m_BSwap(m_Value(LowerBSwap))) &&
2150  match(UpperSrc, m_BSwap(m_Value(UpperBSwap))))
2151  return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2152 
2153  // BITREVERSE: Push the concat down, swapping the lower/upper sources.
2154  // concat(bitreverse(x),bitreverse(y)) -> bitreverse(concat(x,y))
2155  Value *LowerBRev, *UpperBRev;
2156  if (match(LowerSrc, m_BitReverse(m_Value(LowerBRev))) &&
2157  match(UpperSrc, m_BitReverse(m_Value(UpperBRev))))
2158  return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2159 
2160  return nullptr;
2161 }
2162 
2163 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
2165  unsigned NumElts = cast<FixedVectorType>(C1->getType())->getNumElements();
2166  for (unsigned i = 0; i != NumElts; ++i) {
2167  Constant *EltC1 = C1->getAggregateElement(i);
2168  Constant *EltC2 = C2->getAggregateElement(i);
2169  if (!EltC1 || !EltC2)
2170  return false;
2171 
2172  // One element must be all ones, and the other must be all zeros.
2173  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
2174  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
2175  return false;
2176  }
2177  return true;
2178 }
2179 
2180 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
2181 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
2182 /// B, it can be used as the condition operand of a select instruction.
2183 Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) {
2184  // Step 1: We may have peeked through bitcasts in the caller.
2185  // Exit immediately if we don't have (vector) integer types.
2186  Type *Ty = A->getType();
2187  if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
2188  return nullptr;
2189 
2190  // Step 2: We need 0 or all-1's bitmasks.
2191  if (ComputeNumSignBits(A) != Ty->getScalarSizeInBits())
2192  return nullptr;
2193 
2194  // Step 3: If B is the 'not' value of A, we have our answer.
2195  if (match(A, m_Not(m_Specific(B)))) {
2196  // If these are scalars or vectors of i1, A can be used directly.
2197  if (Ty->isIntOrIntVectorTy(1))
2198  return A;
2199  return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(Ty));
2200  }
2201 
2202  // If both operands are constants, see if the constants are inverse bitmasks.
2203  Constant *AConst, *BConst;
2204  if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
2205  if (AConst == ConstantExpr::getNot(BConst))
2206  return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty));
2207 
2208  // Look for more complex patterns. The 'not' op may be hidden behind various
2209  // casts. Look through sexts and bitcasts to find the booleans.
2210  Value *Cond;
2211  Value *NotB;
2212  if (match(A, m_SExt(m_Value(Cond))) &&
2213  Cond->getType()->isIntOrIntVectorTy(1) &&
2214  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
2215  NotB = peekThroughBitcast(NotB, true);
2216  if (match(NotB, m_SExt(m_Specific(Cond))))
2217  return Cond;
2218  }
2219 
2220  // All scalar (and most vector) possibilities should be handled now.
2221  // Try more matches that only apply to non-splat constant vectors.
2222  if (!Ty->isVectorTy())
2223  return nullptr;
2224 
2225  // If both operands are xor'd with constants using the same sexted boolean
2226  // operand, see if the constants are inverse bitmasks.
2227  // TODO: Use ConstantExpr::getNot()?
2228  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
2229  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) &&
2230  Cond->getType()->isIntOrIntVectorTy(1) &&
2231  areInverseVectorBitmasks(AConst, BConst)) {
2232  AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty));
2233  return Builder.CreateXor(Cond, AConst);
2234  }
2235  return nullptr;
2236 }
2237 
2238 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
2239 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
2240 Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
2241  Value *D) {
2242  // The potential condition of the select may be bitcasted. In that case, look
2243  // through its bitcast and the corresponding bitcast of the 'not' condition.
2244  Type *OrigType = A->getType();
2245  A = peekThroughBitcast(A, true);
2246  B = peekThroughBitcast(B, true);
2247  if (Value *Cond = getSelectCondition(A, B)) {
2248  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
2249  // The bitcasts will either all exist or all not exist. The builder will
2250  // not create unnecessary casts if the types already match.
2251  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
2252  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
2253  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
2254  return Builder.CreateBitCast(Select, OrigType);
2255  }
2256 
2257  return nullptr;
2258 }
2259 
2260 /// Fold (icmp)|(icmp) if possible.
2261 Value *InstCombinerImpl::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2262  BinaryOperator &Or) {
2263  const SimplifyQuery Q = SQ.getWithInstruction(&Or);
2264 
2265  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
2266  // if K1 and K2 are a one-bit mask.
2267  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, Or))
2268  return V;
2269 
2270  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2271  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
2272  Value *LHS1 = LHS->getOperand(1), *RHS1 = RHS->getOperand(1);
2273  auto *LHSC = dyn_cast<ConstantInt>(LHS1);
2274  auto *RHSC = dyn_cast<ConstantInt>(RHS1);
2275 
2276  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
2277  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
2278  // The original condition actually refers to the following two ranges:
2279  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
2280  // We can fold these two ranges if:
2281  // 1) C1 and C2 is unsigned greater than C3.
2282  // 2) The two ranges are separated.
2283  // 3) C1 ^ C2 is one-bit mask.
2284  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
2285  // This implies all values in the two ranges differ by exactly one bit.
2286  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
2287  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
2288  LHSC->getType() == RHSC->getType() &&
2289  LHSC->getValue() == (RHSC->getValue())) {
2290 
2291  Value *AddOpnd;
2292  ConstantInt *LAddC, *RAddC;
2293  if (match(LHS0, m_Add(m_Value(AddOpnd), m_ConstantInt(LAddC))) &&
2294  match(RHS0, m_Add(m_Specific(AddOpnd), m_ConstantInt(RAddC))) &&
2295  LAddC->getValue().ugt(LHSC->getValue()) &&
2296  RAddC->getValue().ugt(LHSC->getValue())) {
2297 
2298  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
2299  if (DiffC.isPowerOf2()) {
2300  ConstantInt *MaxAddC = nullptr;
2301  if (LAddC->getValue().ult(RAddC->getValue()))
2302  MaxAddC = RAddC;
2303  else
2304  MaxAddC = LAddC;
2305 
2306  APInt RRangeLow = -RAddC->getValue();
2307  APInt RRangeHigh = RRangeLow + LHSC->getValue();
2308  APInt LRangeLow = -LAddC->getValue();
2309  APInt LRangeHigh = LRangeLow + LHSC->getValue();
2310  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
2311  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
2312  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
2313  : RRangeLow - LRangeLow;
2314 
2315  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
2316  RangeDiff.ugt(LHSC->getValue())) {
2317  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
2318 
2319  Value *NewAnd = Builder.CreateAnd(AddOpnd, MaskC);
2320  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
2321  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
2322  }
2323  }
2324  }
2325  }
2326 
2327  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
2328  if (predicatesFoldable(PredL, PredR)) {
2329  if (LHS0 == RHS1 && LHS1 == RHS0)
2330  LHS->swapOperands();
2331  if (LHS0 == RHS0 && LHS1 == RHS1) {
2332  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
2333  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2334  return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
2335  }
2336  }
2337 
2338  // handle (roughly):
2339  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
2340  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
2341  return V;
2342 
2343  if (LHS->hasOneUse() || RHS->hasOneUse()) {
2344  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
2345  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
2346  Value *A = nullptr, *B = nullptr;
2347  if (PredL == ICmpInst::ICMP_EQ && match(LHS1, m_Zero())) {
2348  B = LHS0;
2349  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS1)
2350  A = RHS0;
2351  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
2352  A = RHS1;
2353  }
2354  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
2355  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
2356  else if (PredR == ICmpInst::ICMP_EQ && match(RHS1, m_Zero())) {
2357  B = RHS0;
2358  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS1)
2359  A = LHS0;
2360  else if (PredL == ICmpInst::ICMP_UGT && RHS0 == LHS0)
2361  A = LHS1;
2362  }
2363  if (A && B && B->getType()->isIntOrIntVectorTy())
2364  return Builder.CreateICmp(
2366  Builder.CreateAdd(B, Constant::getAllOnesValue(B->getType())), A);
2367  }
2368 
2369  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, Or, Builder, Q))
2370  return V;
2371  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, Or, Builder, Q))
2372  return V;
2373 
2374  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
2375  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
2376  return V;
2377 
2378  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
2379  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
2380  return V;
2381 
2382  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
2383  return V;
2384 
2385  if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder))
2386  return V;
2387 
2388  if (Value *X =
2389  foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/false, Q, Builder))
2390  return X;
2391  if (Value *X =
2392  foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/false, Q, Builder))
2393  return X;
2394 
2395  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
2396  // TODO: Remove this when foldLogOpOfMaskedICmps can handle vectors.
2397  if (PredL == ICmpInst::ICMP_NE && match(LHS1, m_Zero()) &&
2398  PredR == ICmpInst::ICMP_NE && match(RHS1, m_Zero()) &&
2399  LHS0->getType()->isIntOrIntVectorTy() &&
2400  LHS0->getType() == RHS0->getType()) {
2401  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
2402  return Builder.CreateICmp(PredL, NewOr,
2403  Constant::getNullValue(NewOr->getType()));
2404  }
2405 
2406  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
2407  if (!LHSC || !RHSC)
2408  return nullptr;
2409 
2410  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
2411  // iff C2 + CA == C1.
2412  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
2413  ConstantInt *AddC;
2414  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
2415  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
2416  return Builder.CreateICmpULE(LHS0, LHSC);
2417  }
2418 
2419  // From here on, we only handle:
2420  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
2421  if (LHS0 != RHS0)
2422  return nullptr;
2423 
2424  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
2425  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
2426  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
2427  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
2428  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
2429  return nullptr;
2430 
2431  // We can't fold (ugt x, C) | (sgt x, C2).
2432  if (!predicatesFoldable(PredL, PredR))
2433  return nullptr;
2434 
2435  // Ensure that the larger constant is on the RHS.
2436  bool ShouldSwap;
2437  if (CmpInst::isSigned(PredL) ||
2438  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
2439  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
2440  else
2441  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
2442 
2443  if (ShouldSwap) {
2444  std::swap(LHS, RHS);
2445  std::swap(LHSC, RHSC);
2446  std::swap(PredL, PredR);
2447  }
2448 
2449  // At this point, we know we have two icmp instructions
2450  // comparing a value against two constants and or'ing the result
2451  // together. Because of the above check, we know that we only have
2452  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
2453  // icmp folding check above), that the two constants are not
2454  // equal.
2455  assert(LHSC != RHSC && "Compares not folded above?");
2456 
2457  switch (PredL) {
2458  default:
2459  llvm_unreachable("Unknown integer condition code!");
2460  case ICmpInst::ICMP_EQ:
2461  switch (PredR) {
2462  default:
2463  llvm_unreachable("Unknown integer condition code!");
2464  case ICmpInst::ICMP_EQ:
2465  // Potential folds for this case should already be handled.
2466  break;
2467  case ICmpInst::ICMP_UGT:
2468  // (X == 0 || X u> C) -> (X-1) u>= C
2469  if (LHSC->isMinValue(false))
2470  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2471  false, false);
2472  // (X == 13 | X u> 14) -> no change
2473  break;
2474  case ICmpInst::ICMP_SGT:
2475  // (X == INT_MIN || X s> C) -> (X-(INT_MIN+1)) u>= C-INT_MIN
2476  if (LHSC->isMinValue(true))
2477  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2478  true, false);
2479  // (X == 13 | X s> 14) -> no change
2480  break;
2481  }
2482  break;
2483  case ICmpInst::ICMP_ULT:
2484  switch (PredR) {
2485  default:
2486  llvm_unreachable("Unknown integer condition code!");
2487  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
2488  // (X u< C || X == UINT_MAX) => (X-C) u>= UINT_MAX-C
2489  if (RHSC->isMaxValue(false))
2490  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2491  false, false);
2492  break;
2493  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
2494  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
2495  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
2496  false, false);
2497  }
2498  break;
2499  case ICmpInst::ICMP_SLT:
2500  switch (PredR) {
2501  default:
2502  llvm_unreachable("Unknown integer condition code!");
2503  case ICmpInst::ICMP_EQ:
2504  // (X s< C || X == INT_MAX) => (X-C) u>= INT_MAX-C
2505  if (RHSC->isMaxValue(true))
2506  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2507  true, false);
2508  // (X s< 13 | X == 14) -> no change
2509  break;
2510  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) u> 2
2511  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
2512  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
2513  false);
2514  }
2515  break;
2516  }
2517  return nullptr;
2518 }
2519 
2520 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2521 // here. We should standardize that construct where it is needed or choose some
2522 // other way to ensure that commutated variants of patterns are not missed.
2524  if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
2525  SQ.getWithInstruction(&I)))
2526  return replaceInstUsesWith(I, V);
2527 
2528  if (SimplifyAssociativeOrCommutative(I))
2529  return &I;
2530 
2531  if (Instruction *X = foldVectorBinop(I))
2532  return X;
2533 
2534  // See if we can simplify any instructions used by the instruction whose sole
2535  // purpose is to compute bits we don't care about.
2536  if (SimplifyDemandedInstructionBits(I))
2537  return &I;
2538 
2539  // Do this before using distributive laws to catch simple and/or/not patterns.
2540  if (Instruction *Xor = foldOrToXor(I, Builder))
2541  return Xor;
2542 
2543  // (A&B)|(A&C) -> A&(B|C) etc
2544  if (Value *V = SimplifyUsingDistributiveLaws(I))
2545  return replaceInstUsesWith(I, V);
2546 
2547  if (Value *V = SimplifyBSwap(I, Builder))
2548  return replaceInstUsesWith(I, V);
2549 
2550  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2551  return FoldedLogic;
2552 
2553  if (Instruction *BSwap = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
2554  /*MatchBitReversals*/ false))
2555  return BSwap;
2556 
2557  if (Instruction *Funnel = matchFunnelShift(I, *this))
2558  return Funnel;
2559 
2561  return replaceInstUsesWith(I, Concat);
2562 
2563  Value *X, *Y;
2564  const APInt *CV;
2565  if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
2566  !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) {
2567  // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
2568  // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
2569  Value *Or = Builder.CreateOr(X, Y);
2570  return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
2571  }
2572 
2573  // (A & C)|(B & D)
2574  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2575  Value *A, *B, *C, *D;
2576  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2577  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2578  // (A & C1)|(B & C2)
2579  ConstantInt *C1, *C2;
2580  if (match(C, m_ConstantInt(C1)) && match(D, m_ConstantInt(C2))) {
2581  Value *V1 = nullptr, *V2 = nullptr;
2582  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2583  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2584  // iff (C1&C2) == 0 and (N&~C1) == 0
2585  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2586  ((V1 == B &&
2587  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2588  (V2 == B &&
2589  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2590  return BinaryOperator::CreateAnd(A,
2591  Builder.getInt(C1->getValue()|C2->getValue()));
2592  // Or commutes, try both ways.
2593  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2594  ((V1 == A &&
2595  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2596  (V2 == A &&
2597  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2598  return BinaryOperator::CreateAnd(B,
2599  Builder.getInt(C1->getValue()|C2->getValue()));
2600 
2601  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2602  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2603  ConstantInt *C3 = nullptr, *C4 = nullptr;
2604  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2605  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2606  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2607  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2608  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2609  return BinaryOperator::CreateAnd(V2,
2610  Builder.getInt(C1->getValue()|C2->getValue()));
2611  }
2612  }
2613 
2614  if (C1->getValue() == ~C2->getValue()) {
2615  Value *X;
2616 
2617  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2618  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2619  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2620  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2621  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2622  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2623 
2624  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2625  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2626  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2627  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2628  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2629  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2630  }
2631  }
2632 
2633  // Don't try to form a select if it's unlikely that we'll get rid of at
2634  // least one of the operands. A select is generally more expensive than the
2635  // 'or' that it is replacing.
2636  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2637  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2638  if (Value *V = matchSelectFromAndOr(A, C, B, D))
2639  return replaceInstUsesWith(I, V);
2640  if (Value *V = matchSelectFromAndOr(A, C, D, B))
2641  return replaceInstUsesWith(I, V);
2642  if (Value *V = matchSelectFromAndOr(C, A, B, D))
2643  return replaceInstUsesWith(I, V);
2644  if (Value *V = matchSelectFromAndOr(C, A, D, B))
2645  return replaceInstUsesWith(I, V);
2646  if (Value *V = matchSelectFromAndOr(B, D, A, C))
2647  return replaceInstUsesWith(I, V);
2648  if (Value *V = matchSelectFromAndOr(B, D, C, A))
2649  return replaceInstUsesWith(I, V);
2650  if (Value *V = matchSelectFromAndOr(D, B, A, C))
2651  return replaceInstUsesWith(I, V);
2652  if (Value *V = matchSelectFromAndOr(D, B, C, A))
2653  return replaceInstUsesWith(I, V);
2654  }
2655  }
2656 
2657  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2658  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2659  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2660  return BinaryOperator::CreateOr(Op0, C);
2661 
2662  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2663  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2664  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2665  return BinaryOperator::CreateOr(Op1, C);
2666 
2667  // ((B | C) & A) | B -> B | (A & C)
2668  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2669  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2670 
2671  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2672  return DeMorgan;
2673 
2674  // Canonicalize xor to the RHS.
2675  bool SwappedForXor = false;
2676  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2677  std::swap(Op0, Op1);
2678  SwappedForXor = true;
2679  }
2680 
2681  // A | ( A ^ B) -> A | B
2682  // A | (~A ^ B) -> A | ~B
2683  // (A & B) | (A ^ B)
2684  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2685  if (Op0 == A || Op0 == B)
2686  return BinaryOperator::CreateOr(A, B);
2687 
2688  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2689  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2690  return BinaryOperator::CreateOr(A, B);
2691 
2692  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2693  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2694  return BinaryOperator::CreateOr(Not, Op0);
2695  }
2696  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2697  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2698  return BinaryOperator::CreateOr(Not, Op0);
2699  }
2700  }
2701 
2702  // A | ~(A | B) -> A | ~B
2703  // A | ~(A ^ B) -> A | ~B
2704  if (match(Op1, m_Not(m_Value(A))))
2705  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2706  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2707  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2708  B->getOpcode() == Instruction::Xor)) {
2709  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2710  B->getOperand(0);
2711  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2712  return BinaryOperator::CreateOr(Not, Op0);
2713  }
2714 
2715  if (SwappedForXor)
2716  std::swap(Op0, Op1);
2717 
2718  {
2719  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2720  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2721  if (LHS && RHS)
2722  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2723  return replaceInstUsesWith(I, Res);
2724 
2725  // TODO: Make this recursive; it's a little tricky because an arbitrary
2726  // number of 'or' instructions might have to be created.
2727  Value *X, *Y;
2728  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2729  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2730  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2731  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2732  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2733  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2734  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2735  }
2736  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2737  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2738  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2739  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2740  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2741  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2742  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2743  }
2744  }
2745 
2746  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2747  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2748  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2749  return replaceInstUsesWith(I, Res);
2750 
2751  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2752  return FoldedFCmps;
2753 
2754  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2755  return CastedOr;
2756 
2757  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2758  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2759  A->getType()->isIntOrIntVectorTy(1))
2760  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2761  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2762  A->getType()->isIntOrIntVectorTy(1))
2763  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2764 
2765  // Note: If we've gotten to the point of visiting the outer OR, then the
2766  // inner one couldn't be simplified. If it was a constant, then it won't
2767  // be simplified by a later pass either, so we try swapping the inner/outer
2768  // ORs in the hopes that we'll be able to simplify it this way.
2769  // (X|C) | V --> (X|V) | C
2770  ConstantInt *CI;
2771  if (Op0->hasOneUse() && !match(Op1, m_ConstantInt()) &&
2772  match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
2773  Value *Inner = Builder.CreateOr(A, Op1);
2774  Inner->takeName(Op0);
2775  return BinaryOperator::CreateOr(Inner, CI);
2776  }
2777 
2778  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2779  // Since this OR statement hasn't been optimized further yet, we hope
2780  // that this transformation will allow the new ORs to be optimized.
2781  {
2782  Value *X = nullptr, *Y = nullptr;
2783  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2784  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2785  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2786  Value *orTrue = Builder.CreateOr(A, C);
2787  Value *orFalse = Builder.CreateOr(B, D);
2788  return SelectInst::Create(X, orTrue, orFalse);
2789  }
2790  }
2791 
2792  // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X.
2793  {
2794  Value *X, *Y;
2795  Type *Ty = I.getType();
2796  if (match(&I, m_c_Or(m_OneUse(m_AShr(
2797  m_NSWSub(m_Value(Y), m_Value(X)),
2798  m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
2799  m_Deferred(X)))) {
2800  Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
2801  Value *AllOnes = ConstantInt::getAllOnesValue(Ty);
2802  return SelectInst::Create(NewICmpInst, AllOnes, X);
2803  }
2804  }
2805 
2806  if (Instruction *V =
2807  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2808  return V;
2809 
2810  CmpInst::Predicate Pred;
2811  Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2812  // Check if the OR weakens the overflow condition for umul.with.overflow by
2813  // treating any non-zero result as overflow. In that case, we overflow if both
2814  // umul.with.overflow operands are != 0, as in that case the result can only
2815  // be 0, iff the multiplication overflows.
2816  if (match(&I,
2817  m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_Value(UMulWithOv)),
2818  m_Value(Ov)),
2819  m_CombineAnd(m_ICmp(Pred,
2820  m_CombineAnd(m_ExtractValue<0>(
2821  m_Deferred(UMulWithOv)),
2822  m_Value(Mul)),
2823  m_ZeroInt()),
2824  m_Value(MulIsNotZero)))) &&
2825  (Ov->hasOneUse() || (MulIsNotZero->hasOneUse() && Mul->hasOneUse())) &&
2826  Pred == CmpInst::ICMP_NE) {
2827  Value *A, *B;
2828  if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2829  m_Value(A), m_Value(B)))) {
2830  Value *NotNullA = Builder.CreateIsNotNull(A);
2831  Value *NotNullB = Builder.CreateIsNotNull(B);
2832  return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2833  }
2834  }
2835 
2836  // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions
2837  if (sinkNotIntoOtherHandOfAndOrOr(I))
2838  return &I;
2839 
2840  return nullptr;
2841 }
2842 
2843 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2844 /// can fold these early and efficiently by morphing an existing instruction.
2847  assert(I.getOpcode() == Instruction::Xor);
2848  Value *Op0 = I.getOperand(0);
2849  Value *Op1 = I.getOperand(1);
2850  Value *A, *B;
2851 
2852  // There are 4 commuted variants for each of the basic patterns.
2853 
2854  // (A & B) ^ (A | B) -> A ^ B
2855  // (A & B) ^ (B | A) -> A ^ B
2856  // (A | B) ^ (A & B) -> A ^ B
2857  // (A | B) ^ (B & A) -> A ^ B
2858  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2859  m_c_Or(m_Deferred(A), m_Deferred(B)))))
2860  return BinaryOperator::CreateXor(A, B);
2861 
2862  // (A | ~B) ^ (~A | B) -> A ^ B
2863  // (~B | A) ^ (~A | B) -> A ^ B
2864  // (~A | B) ^ (A | ~B) -> A ^ B
2865  // (B | ~A) ^ (A | ~B) -> A ^ B
2866  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2867  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
2868  return BinaryOperator::CreateXor(A, B);
2869 
2870  // (A & ~B) ^ (~A & B) -> A ^ B
2871  // (~B & A) ^ (~A & B) -> A ^ B
2872  // (~A & B) ^ (A & ~B) -> A ^ B
2873  // (B & ~A) ^ (A & ~B) -> A ^ B
2874  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2875  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B)))))
2876  return BinaryOperator::CreateXor(A, B);
2877 
2878  // For the remaining cases we need to get rid of one of the operands.
2879  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2880  return nullptr;
2881 
2882  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2883  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2884  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2885  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2886  // Complexity sorting ensures the not will be on the right side.
2887  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2888  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2889  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2890  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2891  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2892 
2893  return nullptr;
2894 }
2895 
2896 Value *InstCombinerImpl::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2897  BinaryOperator &I) {
2898  assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
2899  I.getOperand(1) == RHS && "Should be 'xor' with these operands");
2900 
2901  if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2902  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2903  LHS->getOperand(1) == RHS->getOperand(0))
2904  LHS->swapOperands();
2905  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2906  LHS->getOperand(1) == RHS->getOperand(1)) {
2907  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2908  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2909  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2910  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2911  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
2912  }
2913  }
2914 
2915  // TODO: This can be generalized to compares of non-signbits using
2916  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
2917  // foldLogOpOfMaskedICmps().
2918  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2919  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
2920  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
2921  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
2922  LHS0->getType() == RHS0->getType() &&
2923  LHS0->getType()->isIntOrIntVectorTy()) {
2924  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
2925  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
2926  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2927  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
2928  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2929  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
2930  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
2931  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
2932  }
2933  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
2934  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
2935  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2936  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
2937  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2938  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
2939  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
2940  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
2941  }
2942  }
2943 
2944  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2945  // into those logic ops. That is, try to turn this into an and-of-icmps
2946  // because we have many folds for that pattern.
2947  //
2948  // This is based on a truth table definition of xor:
2949  // X ^ Y --> (X | Y) & !(X & Y)
2950  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2951  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2952  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2953  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2954  // TODO: Independently handle cases where the 'and' side is a constant.
2955  ICmpInst *X = nullptr, *Y = nullptr;
2956  if (OrICmp == LHS && AndICmp == RHS) {
2957  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS --> X & !Y
2958  X = LHS;
2959  Y = RHS;
2960  }
2961  if (OrICmp == RHS && AndICmp == LHS) {
2962  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS --> !Y & X
2963  X = RHS;
2964  Y = LHS;
2965  }
2966  if (X && Y && (Y->hasOneUse() || canFreelyInvertAllUsersOf(Y, &I))) {
2967  // Invert the predicate of 'Y', thus inverting its output.
2968  Y->setPredicate(Y->getInversePredicate());
2969  // So, are there other uses of Y?
2970  if (!Y->hasOneUse()) {
2971  // We need to adapt other uses of Y though. Get a value that matches
2972  // the original value of Y before inversion. While this increases
2973  // immediate instruction count, we have just ensured that all the
2974  // users are freely-invertible, so that 'not' *will* get folded away.
2976  // Set insertion point to right after the Y.
2977  Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
2978  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2979  // Replace all uses of Y (excluding the one in NotY!) with NotY.
2980  Worklist.pushUsersToWorkList(*Y);
2981  Y->replaceUsesWithIf(NotY,
2982  [NotY](Use &U) { return U.getUser() != NotY; });
2983  }
2984  // All done.
2985  return Builder.CreateAnd(LHS, RHS);
2986  }
2987  }
2988  }
2989 
2990  return nullptr;
2991 }
2992 
2993 /// If we have a masked merge, in the canonical form of:
2994 /// (assuming that A only has one use.)
2995 /// | A | |B|
2996 /// ((x ^ y) & M) ^ y
2997 /// | D |
2998 /// * If M is inverted:
2999 /// | D |
3000 /// ((x ^ y) & ~M) ^ y
3001 /// We can canonicalize by swapping the final xor operand
3002 /// to eliminate the 'not' of the mask.
3003 /// ((x ^ y) & M) ^ x
3004 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
3005 /// because that shortens the dependency chain and improves analysis:
3006 /// (x & M) | (y & ~M)
3009  Value *B, *X, *D;
3010  Value *M;
3011  if (!match(&I, m_c_Xor(m_Value(B),
3012  m_OneUse(m_c_And(
3014  m_Value(D)),
3015  m_Value(M))))))
3016  return nullptr;
3017 
3018  Value *NotM;
3019  if (match(M, m_Not(m_Value(NotM)))) {
3020  // De-invert the mask and swap the value in B part.
3021  Value *NewA = Builder.CreateAnd(D, NotM);
3022  return BinaryOperator::CreateXor(NewA, X);
3023  }
3024 
3025  Constant *C;
3026  if (D->hasOneUse() && match(M, m_Constant(C))) {
3027  // Propagating undef is unsafe. Clamp undef elements to -1.
3028  Type *EltTy = C->getType()->getScalarType();
3030  // Unfold.
3031  Value *LHS = Builder.CreateAnd(X, C);
3032  Value *NotC = Builder.CreateNot(C);
3033  Value *RHS = Builder.CreateAnd(B, NotC);
3034  return BinaryOperator::CreateOr(LHS, RHS);
3035  }
3036 
3037  return nullptr;
3038 }
3039 
3040 // Transform
3041 // ~(x ^ y)
3042 // into:
3043 // (~x) ^ y
3044 // or into
3045 // x ^ (~y)
3048  Value *X, *Y;
3049  // FIXME: one-use check is not needed in general, but currently we are unable
3050  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
3051  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
3052  return nullptr;
3053 
3054  // We only want to do the transform if it is free to do.
3055  if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) {
3056  // Ok, good.
3057  } else if (InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) {
3058  std::swap(X, Y);
3059  } else
3060  return nullptr;
3061 
3062  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
3063  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
3064 }
3065 
3066 // Transform
3067 // z = (~x) &/| y
3068 // into:
3069 // z = ~(x |/& (~y))
3070 // iff y is free to invert and all uses of z can be freely updated.
3072  Instruction::BinaryOps NewOpc;
3073  switch (I.getOpcode()) {
3074  case Instruction::And:
3075  NewOpc = Instruction::Or;
3076  break;
3077  case Instruction::Or:
3078  NewOpc = Instruction::And;
3079  break;
3080  default:
3081  return false;
3082  };
3083 
3084  Value *X, *Y;
3085  if (!match(&I, m_c_BinOp(m_Not(m_Value(X)), m_Value(Y))))
3086  return false;
3087 
3088  // Will we be able to fold the `not` into Y eventually?
3089  if (!InstCombiner::isFreeToInvert(Y, Y->hasOneUse()))
3090  return false;
3091 
3092  // And can our users be adapted?
3093  if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
3094  return false;
3095 
3096  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3097  Value *NewBinOp =
3098  BinaryOperator::Create(NewOpc, X, NotY, I.getName() + ".not");
3099  Builder.Insert(NewBinOp);
3100  replaceInstUsesWith(I, NewBinOp);
3101  // We can not just create an outer `not`, it will most likely be immediately
3102  // folded back, reconstructing our initial pattern, and causing an
3103  // infinite combine loop, so immediately manually fold it away.
3104  freelyInvertAllUsersOf(NewBinOp);
3105  return true;
3106 }
3107 
3108 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
3109 // here. We should standardize that construct where it is needed or choose some
3110 // other way to ensure that commutated variants of patterns are not missed.
3112  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
3113  SQ.getWithInstruction(&I)))
3114  return replaceInstUsesWith(I, V);
3115 
3116  if (SimplifyAssociativeOrCommutative(I))
3117  return &I;
3118 
3119  if (Instruction *X = foldVectorBinop(I))
3120  return X;
3121 
3122  if (Instruction *NewXor = foldXorToXor(I, Builder))
3123  return NewXor;
3124 
3125  // (A&B)^(A&C) -> A&(B^C) etc
3126  if (Value *V = SimplifyUsingDistributiveLaws(I))
3127  return replaceInstUsesWith(I, V);
3128 
3129  // See if we can simplify any instructions used by the instruction whose sole
3130  // purpose is to compute bits we don't care about.
3131  if (SimplifyDemandedInstructionBits(I))
3132  return &I;
3133 
3134  if (Value *V = SimplifyBSwap(I, Builder))
3135  return replaceInstUsesWith(I, V);
3136 
3137  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3138  Type *Ty = I.getType();
3139 
3140  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
3141  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
3142  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
3143  // have already taken care of those cases.
3144  Value *M;
3145  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
3146  m_c_And(m_Deferred(M), m_Value()))))
3147  return BinaryOperator::CreateOr(Op0, Op1);
3148 
3149  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
3150  Value *X, *Y;
3151 
3152  // We must eliminate the and/or (one-use) for these transforms to not increase
3153  // the instruction count.
3154  // ~(~X & Y) --> (X | ~Y)
3155  // ~(Y & ~X) --> (X | ~Y)
3156  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
3157  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3158  return BinaryOperator::CreateOr(X, NotY);
3159  }
3160  // ~(~X | Y) --> (X & ~Y)
3161  // ~(Y | ~X) --> (X & ~Y)
3162  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
3163  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3164  return BinaryOperator::CreateAnd(X, NotY);
3165  }
3166 
3168  return Xor;
3169 
3170  // Is this a 'not' (~) fed by a binary operator?
3171  BinaryOperator *NotVal;
3172  if (match(&I, m_Not(m_BinOp(NotVal)))) {
3173  if (NotVal->getOpcode() == Instruction::And ||
3174  NotVal->getOpcode() == Instruction::Or) {
3175  // Apply DeMorgan's Law when inverts are free:
3176  // ~(X & Y) --> (~X | ~Y)
3177  // ~(X | Y) --> (~X & ~Y)
3178  if (isFreeToInvert(NotVal->getOperand(0),
3179  NotVal->getOperand(0)->hasOneUse()) &&
3180  isFreeToInvert(NotVal->getOperand(1),
3181  NotVal->getOperand(1)->hasOneUse())) {
3182  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
3183  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
3184  if (NotVal->getOpcode() == Instruction::And)
3185  return BinaryOperator::CreateOr(NotX, NotY);
3186  return BinaryOperator::CreateAnd(NotX, NotY);
3187  }
3188  }
3189 
3190  // ~(X - Y) --> ~X + Y
3191  if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
3192  if (isa<Constant>(X) || NotVal->hasOneUse())
3193  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
3194 
3195  // ~(~X >>s Y) --> (X >>s Y)
3196  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
3197  return BinaryOperator::CreateAShr(X, Y);
3198 
3199  // If we are inverting a right-shifted constant, we may be able to eliminate
3200  // the 'not' by inverting the constant and using the opposite shift type.
3201  // Canonicalization rules ensure that only a negative constant uses 'ashr',
3202  // but we must check that in case that transform has not fired yet.
3203 
3204  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
3205  Constant *C;
3206  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
3207  match(C, m_Negative())) {
3208  // We matched a negative constant, so propagating undef is unsafe.
3209  // Clamp undef elements to -1.
3210  Type *EltTy = Ty->getScalarType();
3212  return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
3213  }
3214 
3215  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
3216  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
3217  match(C, m_NonNegative())) {
3218  // We matched a non-negative constant, so propagating undef is unsafe.
3219  // Clamp undef elements to 0.
3220  Type *EltTy = Ty->getScalarType();
3222  return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
3223  }
3224 
3225  // ~(X + C) --> -(C + 1) - X
3226  if (match(Op0, m_Add(m_Value(X), m_Constant(C))))
3227  return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X);
3228 
3229  // ~(~X + Y) --> X - Y
3230  if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
3231  return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
3232  NotVal);
3233  }
3234 
3235  // Use DeMorgan and reassociation to eliminate a 'not' op.
3236  Constant *C1;
3237  if (match(Op1, m_Constant(C1))) {
3238  Constant *C2;
3239  if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
3240  // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
3241  Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2));
3242  return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
3243  }
3244  if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
3245  // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
3246  Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2));
3247  return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
3248  }
3249  }
3250 
3251  // not (cmp A, B) = !cmp A, B
3252  CmpInst::Predicate Pred;
3253  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
3254  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
3255  return replaceInstUsesWith(I, Op0);
3256  }
3257 
3258  {
3259  const APInt *RHSC;
3260  if (match(Op1, m_APInt(RHSC))) {
3261  Value *X;
3262  const APInt *C;
3263  // (C - X) ^ signmaskC --> (C + signmaskC) - X
3264  if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X))))
3265  return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C + *RHSC), X);
3266 
3267  // (X + C) ^ signmaskC --> X + (C + signmaskC)
3268  if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
3269  return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
3270 
3271  // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
3272  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
3273  MaskedValueIsZero(X, *C, 0, &I))
3274  return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
3275 
3276  // If RHSC is inverting the remaining bits of shifted X,
3277  // canonicalize to a 'not' before the shift to help SCEV and codegen:
3278  // (X << C) ^ RHSC --> ~X << C
3279  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
3280  *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).shl(*C)) {
3281  Value *NotX = Builder.CreateNot(X);
3282  return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
3283  }
3284  // (X >>u C) ^ RHSC --> ~X >>u C
3285  if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
3286  *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).lshr(*C)) {
3287  Value *NotX = Builder.CreateNot(X);
3288  return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
3289  }
3290  // TODO: We could handle 'ashr' here as well. That would be matching
3291  // a 'not' op and moving it before the shift. Doing that requires
3292  // preventing the inverse fold in canShiftBinOpWithConstantRHS().
3293  }
3294  }
3295 
3296  // FIXME: This should not be limited to scalar (pull into APInt match above).
3297  {
3298  Value *X;
3299  ConstantInt *C1, *C2, *C3;
3300  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
3301  if (match(Op1, m_ConstantInt(C3)) &&
3303  m_ConstantInt(C2))) &&
3304  Op0->hasOneUse()) {
3305  // fold (C1 >> C2) ^ C3
3306  APInt FoldConst = C1->getValue().lshr(C2->getValue());
3307  FoldConst ^= C3->getValue();
3308  // Prepare the two operands.
3309  auto *Opnd0 = cast<Instruction>(Builder.CreateLShr(X, C2));
3310  Opnd0->takeName(cast<Instruction>(Op0));
3311  Opnd0->setDebugLoc(I.getDebugLoc());
3312  return BinaryOperator::CreateXor(Opnd0, ConstantInt::get(Ty, FoldConst));
3313  }
3314  }
3315 
3316  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
3317  return FoldedLogic;
3318 
3319  // Y ^ (X | Y) --> X & ~Y
3320  // Y ^ (Y | X) --> X & ~Y
3321  if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
3322  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
3323  // (X | Y) ^ Y --> X & ~Y
3324  // (Y | X) ^ Y --> X & ~Y
3325  if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
3326  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
3327 
3328  // Y ^ (X & Y) --> ~X & Y
3329  // Y ^ (Y & X) --> ~X & Y
3330  if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
3331  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
3332  // (X & Y) ^ Y --> ~X & Y
3333  // (Y & X) ^ Y --> ~X & Y
3334  // Canonical form is (X & C) ^ C; don't touch that.
3335  // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
3336  // be fixed to prefer that (otherwise we get infinite looping).
3337  if (!match(Op1, m_Constant()) &&
3338  match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
3339  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
3340 
3341  Value *A, *B, *C;
3342  // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
3343  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3344  m_OneUse(m_c_Or(m_Deferred(A), m_Value(C))))))
3345  return BinaryOperator::CreateXor(
3346  Builder.CreateAnd(Builder.CreateNot(A), C), B);
3347 
3348  // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
3349  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3351  return BinaryOperator::CreateXor(
3352  Builder.CreateAnd(Builder.CreateNot(B), C), A);
3353 
3354  // (A & B) ^ (A ^ B) -> (A | B)
3355  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
3356  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
3357  return BinaryOperator::CreateOr(A, B);
3358  // (A ^ B) ^ (A & B) -> (A | B)
3359  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
3360  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
3361  return BinaryOperator::CreateOr(A, B);
3362 
3363  // (A & ~B) ^ ~A -> ~(A & B)
3364  // (~B & A) ^ ~A -> ~(A & B)
3365  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
3366  match(Op1, m_Not(m_Specific(A))))
3367  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
3368 
3369  // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
3370  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
3371  return BinaryOperator::CreateOr(A, B);
3372 
3373  // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
3374  // TODO: Loosen one-use restriction if common operand is a constant.
3375  Value *D;
3376  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
3377  match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
3378  if (B == C || B == D)
3379  std::swap(A, B);
3380  if (A == C)
3381  std::swap(C, D);
3382  if (A == D) {
3383  Value *NotA = Builder.CreateNot(A);
3384  return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
3385  }
3386  }
3387 
3388  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
3389  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
3390  if (Value *V = foldXorOfICmps(LHS, RHS, I))
3391  return replaceInstUsesWith(I, V);
3392 
3393  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
3394  return CastedXor;
3395 
3396  // Canonicalize a shifty way to code absolute value to the common pattern.
3397  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
3398  // We're relying on the fact that we only do this transform when the shift has
3399  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
3400  // instructions).
3401  if (Op0->hasNUses(2))
3402  std::swap(Op0, Op1);
3403 
3404  const APInt *ShAmt;
3405  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
3406  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
3407  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
3408  // B = ashr i32 A, 31 ; smear the sign bit
3409  // xor (add A, B), B ; add -1 and flip bits if negative
3410  // --> (A < 0) ? -A : A
3411  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
3412  // Copy the nuw/nsw flags from the add to the negate.
3413  auto *Add = cast<BinaryOperator>(Op0);
3414  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
3415  Add->hasNoSignedWrap());
3416  return SelectInst::Create(Cmp, Neg, A);
3417  }
3418 
3419  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3420  //
3421  // %notx = xor i32 %x, -1
3422  // %cmp1 = icmp sgt i32 %notx, %y
3423  // %smax = select i1 %cmp1, i32 %notx, i32 %y
3424  // %res = xor i32 %smax, -1
3425  // =>
3426  // %noty = xor i32 %y, -1
3427  // %cmp2 = icmp slt %x, %noty
3428  // %res = select i1 %cmp2, i32 %x, i32 %noty
3429  //
3430  // Same is applicable for smin/umax/umin.
3431  if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) {
3432  Value *LHS, *RHS;
3433  SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
3435  // It's possible we get here before the not has been simplified, so make
3436  // sure the input to the not isn't freely invertible.
3437  if (match(LHS, m_Not(m_Value(X))) && !isFreeToInvert(X, X->hasOneUse())) {
3438  Value *NotY = Builder.CreateNot(RHS);
3439  return SelectInst::Create(
3440  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
3441  }
3442 
3443  // It's possible we get here before the not has been simplified, so make
3444  // sure the input to the not isn't freely invertible.
3445  if (match(RHS, m_Not(m_Value(Y))) && !isFreeToInvert(Y, Y->hasOneUse())) {
3446  Value *NotX = Builder.CreateNot(LHS);
3447  return SelectInst::Create(
3448  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y);
3449  }
3450 
3451  // If both sides are freely invertible, then we can get rid of the xor
3452  // completely.
3453  if (isFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
3454  isFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) {
3455  Value *NotLHS = Builder.CreateNot(LHS);
3456  Value *NotRHS = Builder.CreateNot(RHS);
3457  return SelectInst::Create(
3458  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
3459  NotLHS, NotRHS);
3460  }
3461  }
3462 
3463  // Pull 'not' into operands of select if both operands are one-use compares
3464  // or one is one-use compare and the other one is a constant.
3465  // Inverting the predicates eliminates the 'not' operation.
3466  // Example:
3467  // not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
3468  // select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
3469  // not (select ?, (cmp TPred, ?, ?), true -->
3470  // select ?, (cmp InvTPred, ?, ?), false
3471  if (auto *Sel = dyn_cast<SelectInst>(Op0)) {
3472  Value *TV = Sel->getTrueValue();
3473  Value *FV = Sel->getFalseValue();
3474  auto *CmpT = dyn_cast<CmpInst>(TV);
3475  auto *CmpF = dyn_cast<CmpInst>(FV);
3476  bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3477  bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3478  if (InvertibleT && InvertibleF) {
3479  if (CmpT)
3480  CmpT->setPredicate(CmpT->getInversePredicate());
3481  else
3482  Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
3483  if (CmpF)
3484  CmpF->setPredicate(CmpF->getInversePredicate());
3485  else
3486  Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
3487  return replaceInstUsesWith(I, Sel);
3488  }
3489  }
3490  }
3491 
3492  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
3493  return NewXor;
3494 
3495  // Otherwise, if all else failed, try to hoist the xor-by-constant:
3496  // (X ^ C) ^ Y --> (X ^ Y) ^ C
3497  // Just like we do in other places, we completely avoid the fold
3498  // for constantexprs, at least to avoid endless combine loop.
3501  m_ImmConstant(C1))),
3502  m_Value(Y))))
3503  return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
3504 
3505  return nullptr;
3506 }
foldIsPowerOf2
static Value * foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
Reduce a pair of compares that check if a value has exactly 1 bit set.
Definition: InstCombineAndOrXor.cpp:963
i
i
Definition: README.txt:29
llvm::CmpInst::FCMP_ULE
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:737
Mask_NotAllZeros
@ Mask_NotAllZeros
Definition: InstCombineAndOrXor.cpp:177
AMask_NotMixed
@ AMask_NotMixed
Definition: InstCombineAndOrXor.cpp:179
llvm::PatternMatch::m_NonNegative
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
Definition: PatternMatch.h:435
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:839
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2633
llvm::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:386
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
CmpInstAnalysis.h
llvm::InstCombiner::isFreeToInvert
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:233
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:437
InstCombiner.h
llvm::Intrinsic::getDeclaration
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:1254
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:181
AMask_Mixed
@ AMask_Mixed
Definition: InstCombineAndOrXor.cpp:178
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2072
llvm::Function
Definition: Function.h:61
llvm::InstCombinerImpl::visitXor
Instruction * visitXor(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:3111
llvm::SimplifyAndInst
Value * SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
Definition: InstructionSimplify.cpp:2207
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2592
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:679
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1098
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:469
llvm::ConstantInt::isMaxValue
bool isMaxValue(bool isSigned) const
This function will return true iff this constant represents the largest value that may be represented...
Definition: Constants.h:227
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
reassociateFCmps
static Instruction * reassociateFCmps(BinaryOperator &BO, InstCombiner::BuilderTy &Builder)
This a limited reassociation for a special case (see above) where we are checking if two values are e...
Definition: InstCombineAndOrXor.cpp:1401
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5024
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:317
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2058
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::tgtok::Code
@ Code
Definition: TGLexer.h:50
AMask_AllOnes
@ AMask_AllOnes
Definition: InstCombineAndOrXor.cpp:172
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:959
peekThroughBitcast
static Register peekThroughBitcast(Register Reg, const MachineRegisterInfo &MRI)
Definition: CombinerHelper.cpp:1877
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:730
llvm::MipsISD::Lo
@ Lo
Definition: MipsISelLowering.h:79
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1034
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::CastInst::Create
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's ...
Definition: Instructions.cpp:2932
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:823
Local.h
matchOrConcat
static Instruction * matchOrConcat(Instruction &Or, InstCombiner::BuilderTy &Builder)
Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
Definition: InstCombineAndOrXor.cpp:2111
getMaskedICmpType
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.
Definition: InstCombineAndOrXor.cpp:186
llvm::PatternMatch::m_BitReverse
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
Definition: PatternMatch.h:2106
llvm::ICmpInst::getSignedPredicate
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
Definition: Instructions.h:1245
llvm::isKnownNonZero
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
Definition: ValueTracking.cpp:335
getFCmpValue
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...
Definition: InstCombineAndOrXor.cpp:67
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:749
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::ICmpInst::isEquality
bool isEquality() const
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1273
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1275
llvm::Optional
Definition: APInt.h:33
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1104
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:410
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:752
llvm::APInt::intersects
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1341
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:987
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:492
llvm::matchSelectPattern
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...
Definition: ValueTracking.cpp:5913
llvm::PatternMatch::m_c_And
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.
Definition: PatternMatch.h:2184
llvm::ConstantInt::isMinValue
bool isMinValue(bool isSigned) const
This function will return true iff this constant represents the smallest value that may be represente...
Definition: Constants.h:239
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2222
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:655
llvm::ICmpInst::swapOperands
void swapOperands()
Exchange the two operands to this instruction in such a way that it does not modify the semantics of ...
Definition: Instructions.h:1322
llvm::CmpInst::FCMP_OGT
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:726
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:771
BMask_AllOnes
@ BMask_AllOnes
Definition: InstCombineAndOrXor.cpp:174
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2183
llvm::CastInst::getDestTy
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:686
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MipsISD::Hi
@ Hi
Definition: MipsISelLowering.h:75
llvm::PatternMatch::m_Unless
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
Definition: PatternMatch.h:130
llvm::APInt::isSignMask
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
Definition: APInt.h:478
llvm::PatternMatch::m_c_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
Definition: PatternMatch.h:2163
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::CmpInst::FCMP_ULT
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:736
foldAndOrOfEqualityCmpsWithConstants
static Value * foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:743
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:226
llvm::ConstantInt::get
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:876
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2155
llvm::SimplifyQuery::AC
AssumptionCache * AC
Definition: InstructionSimplify.h:97
llvm::InstCombinerImpl::matchBSwapOrBitReverse
Instruction * matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps, bool MatchBitReversals)
Given an initial instruction, check to see if it is the root of a bswap/bitreverse idiom.
Definition: InstCombineAndOrXor.cpp:1993
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::KnownBits::isNonNegative
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
R2
#define R2(n)
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1746
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
llvm::predicatesFoldable
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...
Definition: CmpInstAnalysis.cpp:60
InstCombineInternal.h
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1423
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:844
foldLogicCastConstant
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
Fold {and,or,xor} (cast X), C.
Definition: InstCombineAndOrXor.cpp:1484
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:748
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::SelectPatternResult::isMinOrMax
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
Definition: ValueTracking.h:687
llvm::SimplifyICmpInst
Value * SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
Definition: InstructionSimplify.cpp:3707
llvm::FCmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1344
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::PatternMatch::m_PosZeroFP
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:661
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1493
llvm::CmpInst::FCMP_UGE
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:735
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:235
llvm::SimplifyQuery::DL
const DataLayout & DL
Definition: InstructionSimplify.h:94
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1590
llvm::PatternMatch::m_c_Add
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.
Definition: PatternMatch.h:2170
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MaskedICmpType
MaskedICmpType
Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified.
Definition: InstCombineAndOrXor.cpp:171
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:405
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:395
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:101
llvm::CmpInst::FCMP_UNO
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:732
llvm::Instruction
Definition: Instruction.h:45
Concat
static constexpr int Concat[]
Definition: X86InterleavedAccess.cpp:239
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:147
llvm::PatternMatch::m_c_Or
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.
Definition: PatternMatch.h:2191
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1631
foldUnsignedUnderflowCheck
static Value * foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp, ICmpInst *UnsignedICmp, bool IsAnd, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
Commuted variants are assumed to be handled by calling this function again with the parameters swappe...
Definition: InstCombineAndOrXor.cpp:994
llvm::APInt::isIntN
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition: APInt.h:455
llvm::ConstantExpr::getXor
static Constant * getXor(Constant *C1, Constant *C2)
Definition: Constants.cpp:2706
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:60
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1145
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
llvm::CmpInst::FCMP_OEQ
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:725
llvm::CmpInst::FCMP_OLT
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:728
llvm::Instruction::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: Instruction.cpp:73
PatternMatch.h
llvm::PatternMatch::m_APIntAllowUndef
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:232
llvm::CastInst::getSrcTy
Type * getSrcTy() const
Return the source type, as a convenience.
Definition: InstrTypes.h:684
llvm::getICmpCode
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
Definition: CmpInstAnalysis.cpp:21
llvm::None
const NoneType None
Definition: None.h:23
foldXorToXor
static Instruction * foldXorToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
A ^ B can be specified using other logic ops in a variety of patterns.
Definition: InstCombineAndOrXor.cpp:2845
llvm::APInt::isAllOnesValue
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:401
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:469
llvm::InstCombinerImpl::visitAnd
Instruction * visitAnd(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:1700
Mask_AllZeros
@ Mask_AllZeros
Definition: InstCombineAndOrXor.cpp:176
llvm::CmpInst::FCMP_FALSE
@ FCMP_FALSE
0 0 0 0 Always false (always folded)
Definition: InstrTypes.h:724
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:500
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1086
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:202
llvm::APInt::isSubsetOf
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1349
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2044
foldSignedTruncationCheck
static Value * foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, Instruction &CxtI, InstCombiner::BuilderTy &Builder)
General pattern: X & Y.
Definition: InstCombineAndOrXor.cpp:868
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:491
foldAndToXor
static Instruction * foldAndToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:1589
matchFunnelShift
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
Definition: InstCombineAndOrXor.cpp:2009
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
foldLogOpOfMaskedICmpsAsymmetric
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, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
Definition: InstCombineAndOrXor.cpp:518
llvm::InstCombinerImpl::insertRangeTest
Value * insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, bool isSigned, bool Inside)
Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise (V < Lo || V >= Hi).
Definition: InstCombineAndOrXor.cpp:120
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:737
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1178
llvm::Constant::replaceUndefsWith
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
Definition: Constants.cpp:756
foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed
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, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
Definition: InstCombineAndOrXor.cpp:397
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
BMask_NotMixed
@ BMask_NotMixed
Definition: InstCombineAndOrXor.cpp:181
llvm::SimplifyBinOp
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5220
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1080
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:401
llvm::Value::hasNUsesOrMore
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
Definition: Value.cpp:150
I
#define I(x, y, z)
Definition: MD5.cpp:59
visitMaskedMerge
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....
Definition: InstCombineAndOrXor.cpp:3007
llvm::ConstantExpr::getOr
static Constant * getOr(Constant *C1, Constant *C2)
Definition: Constants.cpp:2702
llvm::SimplifyQuery::DT
const DominatorTree * DT
Definition: InstructionSimplify.h:96
conjugateICmpMask
static unsigned conjugateICmpMask(unsigned Mask)
Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite s...
Definition: InstCombineAndOrXor.cpp:235
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1074
llvm::KnownBits::getMaxValue
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:134
llvm::InstCombiner::canFreelyInvertAllUsersOf
static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
Definition: InstCombiner.h:269
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:238
sinkNotIntoXor
static Instruction * sinkNotIntoXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:3046
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:971
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
llvm::InstCombinerImpl::simplifyRangeCheck
Value * simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
Definition: InstCombineAndOrXor.cpp:691
llvm::CmpInst::FCMP_OGE
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:727
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:746
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:120
llvm::PatternMatch::m_Negative
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:423
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:98
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4730
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::InstCombinerImpl::visitOr
Instruction * visitOr(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:2523
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:751
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1584
llvm::PatternMatch::m_SpecificInt
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:836
llvm::PatternMatch::m_CombineAnd
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:172
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
llvm::PatternMatch::m_SpecificInt_ICMP
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:582
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:747
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:421
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:202
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:367
ConstantRange.h
llvm::ConstantInt::isMinusOne
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:218
llvm::recognizeBSwapOrBitReverseIdiom
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3097
llvm::RecurKind::Mul
@ Mul
Product of integers.
getFCmpCode
static unsigned getFCmpCode(FCmpInst::Predicate CC)
Similar to getICmpCode but for FCmpInst.
Definition: InstCombineAndOrXor.cpp:29
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:432
llvm::getInverseMinMaxPred
CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF)
Return the canonical inverse comparison predicate for the specified minimum/maximum flavor.
Definition: ValueTracking.cpp:5991
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1205
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4769
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:128
foldOrToXor
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:1615
getNewICmpValue
static Value * getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
Definition: InstCombineAndOrXor.cpp:57
AMask_NotAllOnes
@ AMask_NotAllOnes
Definition: InstCombineAndOrXor.cpp:173
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:930
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:163
foldAndOrOfICmpsWithConstEq
static Value * foldAndOrOfICmpsWithConstEq(ICmpInst *Cmp0, ICmpInst *Cmp1, BinaryOperator &Logic, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q)
Reduce logic-of-compares with equality to a constant by substituting a common operand with the consta...
Definition: InstCombineAndOrXor.cpp:1082
BMask_NotAllOnes
@ BMask_NotAllOnes
Definition: InstCombineAndOrXor.cpp:175
llvm::CmpInst::FCMP_UGT
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:734
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::APInt::countLeadingZeros
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1664
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:347
llvm::KnownBits
Definition: KnownBits.h:23
llvm::decomposeBitTestICmp
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.
Definition: CmpInstAnalysis.cpp:66
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2620
llvm::SimplifyQuery::CxtI
const Instruction * CxtI
Definition: InstructionSimplify.h:98
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2639
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:208
llvm::CmpInst::isUnsigned
bool isUnsigned() const
Definition: InstrTypes.h:943
llvm::ConstantInt::getSigned
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:890
llvm::InstCombinerImpl::sinkNotIntoOtherHandOfAndOrOr
bool sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:3071
llvm::getPredForICmpCode
Constant * getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getICmpCode.
Definition: CmpInstAnalysis.cpp:42
llvm::PatternMatch::m_SignMask
cst_pred_ty< is_sign_mask > m_SignMask()
Match an integer or vector with only the sign bit(s) set.
Definition: PatternMatch.h:536
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:146
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::ConstantExpr::getAnd
static Constant * getAnd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2698
llvm::PatternMatch::m_BSwap
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
Definition: PatternMatch.h:2111
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:937
llvm::PatternMatch::m_ZeroInt
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:478
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:750
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:391
llvm::PatternMatch::m_c_Xor
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.
Definition: PatternMatch.h:2198
llvm::PatternMatch::m_LogicalShift
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:1272
llvm::PatternMatch::m_AnyZeroFP
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:652
llvm::Constant::mergeUndefsWith
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
Definition: Constants.cpp:780
llvm::APInt::isNullValue
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:411
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:761
llvm::PatternMatch::m_ConstantExpr
class_match< ConstantExpr > m_ConstantExpr()
Match an arbitrary ConstantExpr and ignore it.
Definition: PatternMatch.h:111
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:758
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1355
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:745
llvm::CmpInst::FCMP_UNE
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:738
N
#define N
llvm::CastInst::getOpcode
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:679
BMask_Mixed
@ BMask_Mixed
Definition: InstCombineAndOrXor.cpp:180
InstructionSimplify.h
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:799
SimplifyBSwap
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,...
Definition: InstCombineAndOrXor.cpp:84
llvm::IntegerType::getBitWidth
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:71
llvm::SimplifyOrInst
Value * SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Or, fold the result or return null.
Definition: InstructionSimplify.cpp:2383
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
llvm::CmpInst::FCMP_OLE
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:729
llvm::PatternMatch::m_FCmp
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1361
canNarrowShiftAmt
static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth)
Return true if a constant shift amount is always less than the specified bit-width.
Definition: InstCombineAndOrXor.cpp:1651
llvm::APInt::sgt
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1294
getMaskedTypeForICmpPair
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).
Definition: InstCombineAndOrXor.cpp:267
areInverseVectorBitmasks
static bool areInverseVectorBitmasks(Constant *C1, Constant *C2)
If all elements of two constant vectors are 0/-1 and inverses, return true.
Definition: InstCombineAndOrXor.cpp:2164
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2206
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:667
llvm::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
Definition: ValueTracking.cpp:322
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:234
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:373
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:1009
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1572
llvm::BinaryOperator::Create
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.
Definition: Instructions.cpp:2536
llvm::CmpInst::FCMP_TRUE
@ FCMP_TRUE
1 1 1 1 Always true (always folded)
Definition: InstrTypes.h:739
matchDeMorgansLaws
static Instruction * matchDeMorgansLaws(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Match De Morgan's Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B))
Definition: InstCombineAndOrXor.cpp:1446
llvm::BinaryOperator::CreateWithCopiedFlags
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, Instruction *CopyO, const Twine &Name="")
Definition: InstrTypes.h:251
llvm::PatternMatch::m_Cmp
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:89
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1092
llvm::SimplifyXorInst
Value * SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
Definition: InstructionSimplify.cpp:2431
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:460
llvm::CmpInst::FCMP_ORD
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:731
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1026
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1131
llvm::CmpInst::FCMP_UEQ
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:733
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
foldLogOpOfMaskedICmps
static Value * foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
Definition: InstCombineAndOrXor.cpp:551
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37