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  // An and recurrence w/loop invariant step is equivelent to (and start, step)
1991  PHINode *PN = nullptr;
1992  Value *Start = nullptr, *Step = nullptr;
1993  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
1994  return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
1995 
1996  return nullptr;
1997 }
1998 
2000  bool MatchBSwaps,
2001  bool MatchBitReversals) {
2003  if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
2004  Insts))
2005  return nullptr;
2006  Instruction *LastInst = Insts.pop_back_val();
2007  LastInst->removeFromParent();
2008 
2009  for (auto *Inst : Insts)
2010  Worklist.push(Inst);
2011  return LastInst;
2012 }
2013 
2014 /// Match UB-safe variants of the funnel shift intrinsic.
2016  // TODO: Can we reduce the code duplication between this and the related
2017  // rotate matching code under visitSelect and visitTrunc?
2018  unsigned Width = Or.getType()->getScalarSizeInBits();
2019 
2020  // First, find an or'd pair of opposite shifts:
2021  // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
2022  BinaryOperator *Or0, *Or1;
2023  if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
2024  !match(Or.getOperand(1), m_BinOp(Or1)))
2025  return nullptr;
2026 
2027  Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2028  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
2029  !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
2030  Or0->getOpcode() == Or1->getOpcode())
2031  return nullptr;
2032 
2033  // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
2034  if (Or0->getOpcode() == BinaryOperator::LShr) {
2035  std::swap(Or0, Or1);
2036  std::swap(ShVal0, ShVal1);
2037  std::swap(ShAmt0, ShAmt1);
2038  }
2039  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2040  Or1->getOpcode() == BinaryOperator::LShr &&
2041  "Illegal or(shift,shift) pair");
2042 
2043  // Match the shift amount operands for a funnel shift pattern. This always
2044  // matches a subtraction on the R operand.
2045  auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
2046  // Check for constant shift amounts that sum to the bitwidth.
2047  const APInt *LI, *RI;
2048  if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
2049  if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
2050  return ConstantInt::get(L->getType(), *LI);
2051 
2052  Constant *LC, *RC;
2053  if (match(L, m_Constant(LC)) && match(R, m_Constant(RC)) &&
2057  return ConstantExpr::mergeUndefsWith(LC, RC);
2058 
2059  // (shl ShVal, X) | (lshr ShVal, (Width - x)) iff X < Width.
2060  // We limit this to X < Width in case the backend re-expands the intrinsic,
2061  // and has to reintroduce a shift modulo operation (InstCombine might remove
2062  // it after this fold). This still doesn't guarantee that the final codegen
2063  // will match this original pattern.
2064  if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) {
2065  KnownBits KnownL = IC.computeKnownBits(L, /*Depth*/ 0, &Or);
2066  return KnownL.getMaxValue().ult(Width) ? L : nullptr;
2067  }
2068 
2069  // For non-constant cases, the following patterns currently only work for
2070  // rotation patterns.
2071  // TODO: Add general funnel-shift compatible patterns.
2072  if (ShVal0 != ShVal1)
2073  return nullptr;
2074 
2075  // For non-constant cases we don't support non-pow2 shift masks.
2076  // TODO: Is it worth matching urem as well?
2077  if (!isPowerOf2_32(Width))
2078  return nullptr;
2079 
2080  // The shift amount may be masked with negation:
2081  // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
2082  Value *X;
2083  unsigned Mask = Width - 1;
2084  if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
2086  return X;
2087 
2088  // Similar to above, but the shift amount may be extended after masking,
2089  // so return the extended value as the parameter for the intrinsic.
2090  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2092  m_SpecificInt(Mask))))
2093  return L;
2094 
2095  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2097  return L;
2098 
2099  return nullptr;
2100  };
2101 
2102  Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);
2103  bool IsFshl = true; // Sub on LSHR.
2104  if (!ShAmt) {
2105  ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);
2106  IsFshl = false; // Sub on SHL.
2107  }
2108  if (!ShAmt)
2109  return nullptr;
2110 
2111  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2112  Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
2113  return CallInst::Create(F, {ShVal0, ShVal1, ShAmt});
2114 }
2115 
2116 /// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
2119  assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
2120  Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
2121  Type *Ty = Or.getType();
2122 
2123  unsigned Width = Ty->getScalarSizeInBits();
2124  if ((Width & 1) != 0)
2125  return nullptr;
2126  unsigned HalfWidth = Width / 2;
2127 
2128  // Canonicalize zext (lower half) to LHS.
2129  if (!isa<ZExtInst>(Op0))
2130  std::swap(Op0, Op1);
2131 
2132  // Find lower/upper half.
2133  Value *LowerSrc, *ShlVal, *UpperSrc;
2134  const APInt *C;
2135  if (!match(Op0, m_OneUse(m_ZExt(m_Value(LowerSrc)))) ||
2136  !match(Op1, m_OneUse(m_Shl(m_Value(ShlVal), m_APInt(C)))) ||
2137  !match(ShlVal, m_OneUse(m_ZExt(m_Value(UpperSrc)))))
2138  return nullptr;
2139  if (*C != HalfWidth || LowerSrc->getType() != UpperSrc->getType() ||
2140  LowerSrc->getType()->getScalarSizeInBits() != HalfWidth)
2141  return nullptr;
2142 
2143  auto ConcatIntrinsicCalls = [&](Intrinsic::ID id, Value *Lo, Value *Hi) {
2144  Value *NewLower = Builder.CreateZExt(Lo, Ty);
2145  Value *NewUpper = Builder.CreateZExt(Hi, Ty);
2146  NewUpper = Builder.CreateShl(NewUpper, HalfWidth);
2147  Value *BinOp = Builder.CreateOr(NewLower, NewUpper);
2148  Function *F = Intrinsic::getDeclaration(Or.getModule(), id, Ty);
2149  return Builder.CreateCall(F, BinOp);
2150  };
2151 
2152  // BSWAP: Push the concat down, swapping the lower/upper sources.
2153  // concat(bswap(x),bswap(y)) -> bswap(concat(x,y))
2154  Value *LowerBSwap, *UpperBSwap;
2155  if (match(LowerSrc, m_BSwap(m_Value(LowerBSwap))) &&
2156  match(UpperSrc, m_BSwap(m_Value(UpperBSwap))))
2157  return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2158 
2159  // BITREVERSE: Push the concat down, swapping the lower/upper sources.
2160  // concat(bitreverse(x),bitreverse(y)) -> bitreverse(concat(x,y))
2161  Value *LowerBRev, *UpperBRev;
2162  if (match(LowerSrc, m_BitReverse(m_Value(LowerBRev))) &&
2163  match(UpperSrc, m_BitReverse(m_Value(UpperBRev))))
2164  return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2165 
2166  return nullptr;
2167 }
2168 
2169 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
2171  unsigned NumElts = cast<FixedVectorType>(C1->getType())->getNumElements();
2172  for (unsigned i = 0; i != NumElts; ++i) {
2173  Constant *EltC1 = C1->getAggregateElement(i);
2174  Constant *EltC2 = C2->getAggregateElement(i);
2175  if (!EltC1 || !EltC2)
2176  return false;
2177 
2178  // One element must be all ones, and the other must be all zeros.
2179  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
2180  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
2181  return false;
2182  }
2183  return true;
2184 }
2185 
2186 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
2187 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
2188 /// B, it can be used as the condition operand of a select instruction.
2189 Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) {
2190  // Step 1: We may have peeked through bitcasts in the caller.
2191  // Exit immediately if we don't have (vector) integer types.
2192  Type *Ty = A->getType();
2193  if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
2194  return nullptr;
2195 
2196  // Step 2: We need 0 or all-1's bitmasks.
2197  if (ComputeNumSignBits(A) != Ty->getScalarSizeInBits())
2198  return nullptr;
2199 
2200  // Step 3: If B is the 'not' value of A, we have our answer.
2201  if (match(A, m_Not(m_Specific(B)))) {
2202  // If these are scalars or vectors of i1, A can be used directly.
2203  if (Ty->isIntOrIntVectorTy(1))
2204  return A;
2205  return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(Ty));
2206  }
2207 
2208  // If both operands are constants, see if the constants are inverse bitmasks.
2209  Constant *AConst, *BConst;
2210  if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
2211  if (AConst == ConstantExpr::getNot(BConst))
2212  return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty));
2213 
2214  // Look for more complex patterns. The 'not' op may be hidden behind various
2215  // casts. Look through sexts and bitcasts to find the booleans.
2216  Value *Cond;
2217  Value *NotB;
2218  if (match(A, m_SExt(m_Value(Cond))) &&
2219  Cond->getType()->isIntOrIntVectorTy(1) &&
2220  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
2221  NotB = peekThroughBitcast(NotB, true);
2222  if (match(NotB, m_SExt(m_Specific(Cond))))
2223  return Cond;
2224  }
2225 
2226  // All scalar (and most vector) possibilities should be handled now.
2227  // Try more matches that only apply to non-splat constant vectors.
2228  if (!Ty->isVectorTy())
2229  return nullptr;
2230 
2231  // If both operands are xor'd with constants using the same sexted boolean
2232  // operand, see if the constants are inverse bitmasks.
2233  // TODO: Use ConstantExpr::getNot()?
2234  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
2235  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) &&
2236  Cond->getType()->isIntOrIntVectorTy(1) &&
2237  areInverseVectorBitmasks(AConst, BConst)) {
2238  AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty));
2239  return Builder.CreateXor(Cond, AConst);
2240  }
2241  return nullptr;
2242 }
2243 
2244 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
2245 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
2246 Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
2247  Value *D) {
2248  // The potential condition of the select may be bitcasted. In that case, look
2249  // through its bitcast and the corresponding bitcast of the 'not' condition.
2250  Type *OrigType = A->getType();
2251  A = peekThroughBitcast(A, true);
2252  B = peekThroughBitcast(B, true);
2253  if (Value *Cond = getSelectCondition(A, B)) {
2254  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
2255  // The bitcasts will either all exist or all not exist. The builder will
2256  // not create unnecessary casts if the types already match.
2257  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
2258  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
2259  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
2260  return Builder.CreateBitCast(Select, OrigType);
2261  }
2262 
2263  return nullptr;
2264 }
2265 
2266 /// Fold (icmp)|(icmp) if possible.
2267 Value *InstCombinerImpl::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2268  BinaryOperator &Or) {
2269  const SimplifyQuery Q = SQ.getWithInstruction(&Or);
2270 
2271  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
2272  // if K1 and K2 are a one-bit mask.
2273  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, Or))
2274  return V;
2275 
2276  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2277  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
2278  Value *LHS1 = LHS->getOperand(1), *RHS1 = RHS->getOperand(1);
2279  auto *LHSC = dyn_cast<ConstantInt>(LHS1);
2280  auto *RHSC = dyn_cast<ConstantInt>(RHS1);
2281 
2282  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
2283  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
2284  // The original condition actually refers to the following two ranges:
2285  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
2286  // We can fold these two ranges if:
2287  // 1) C1 and C2 is unsigned greater than C3.
2288  // 2) The two ranges are separated.
2289  // 3) C1 ^ C2 is one-bit mask.
2290  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
2291  // This implies all values in the two ranges differ by exactly one bit.
2292  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
2293  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
2294  LHSC->getType() == RHSC->getType() &&
2295  LHSC->getValue() == (RHSC->getValue())) {
2296 
2297  Value *AddOpnd;
2298  ConstantInt *LAddC, *RAddC;
2299  if (match(LHS0, m_Add(m_Value(AddOpnd), m_ConstantInt(LAddC))) &&
2300  match(RHS0, m_Add(m_Specific(AddOpnd), m_ConstantInt(RAddC))) &&
2301  LAddC->getValue().ugt(LHSC->getValue()) &&
2302  RAddC->getValue().ugt(LHSC->getValue())) {
2303 
2304  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
2305  if (DiffC.isPowerOf2()) {
2306  ConstantInt *MaxAddC = nullptr;
2307  if (LAddC->getValue().ult(RAddC->getValue()))
2308  MaxAddC = RAddC;
2309  else
2310  MaxAddC = LAddC;
2311 
2312  APInt RRangeLow = -RAddC->getValue();
2313  APInt RRangeHigh = RRangeLow + LHSC->getValue();
2314  APInt LRangeLow = -LAddC->getValue();
2315  APInt LRangeHigh = LRangeLow + LHSC->getValue();
2316  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
2317  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
2318  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
2319  : RRangeLow - LRangeLow;
2320 
2321  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
2322  RangeDiff.ugt(LHSC->getValue())) {
2323  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
2324 
2325  Value *NewAnd = Builder.CreateAnd(AddOpnd, MaskC);
2326  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
2327  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
2328  }
2329  }
2330  }
2331  }
2332 
2333  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
2334  if (predicatesFoldable(PredL, PredR)) {
2335  if (LHS0 == RHS1 && LHS1 == RHS0)
2336  LHS->swapOperands();
2337  if (LHS0 == RHS0 && LHS1 == RHS1) {
2338  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
2339  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2340  return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
2341  }
2342  }
2343 
2344  // handle (roughly):
2345  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
2346  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
2347  return V;
2348 
2349  if (LHS->hasOneUse() || RHS->hasOneUse()) {
2350  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
2351  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
2352  Value *A = nullptr, *B = nullptr;
2353  if (PredL == ICmpInst::ICMP_EQ && match(LHS1, m_Zero())) {
2354  B = LHS0;
2355  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS1)
2356  A = RHS0;
2357  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
2358  A = RHS1;
2359  }
2360  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
2361  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
2362  else if (PredR == ICmpInst::ICMP_EQ && match(RHS1, m_Zero())) {
2363  B = RHS0;
2364  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS1)
2365  A = LHS0;
2366  else if (PredL == ICmpInst::ICMP_UGT && RHS0 == LHS0)
2367  A = LHS1;
2368  }
2369  if (A && B && B->getType()->isIntOrIntVectorTy())
2370  return Builder.CreateICmp(
2372  Builder.CreateAdd(B, Constant::getAllOnesValue(B->getType())), A);
2373  }
2374 
2375  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, Or, Builder, Q))
2376  return V;
2377  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, Or, Builder, Q))
2378  return V;
2379 
2380  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
2381  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
2382  return V;
2383 
2384  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
2385  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
2386  return V;
2387 
2388  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
2389  return V;
2390 
2391  if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder))
2392  return V;
2393 
2394  if (Value *X =
2395  foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/false, Q, Builder))
2396  return X;
2397  if (Value *X =
2398  foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/false, Q, Builder))
2399  return X;
2400 
2401  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
2402  // TODO: Remove this when foldLogOpOfMaskedICmps can handle vectors.
2403  if (PredL == ICmpInst::ICMP_NE && match(LHS1, m_Zero()) &&
2404  PredR == ICmpInst::ICMP_NE && match(RHS1, m_Zero()) &&
2405  LHS0->getType()->isIntOrIntVectorTy() &&
2406  LHS0->getType() == RHS0->getType()) {
2407  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
2408  return Builder.CreateICmp(PredL, NewOr,
2409  Constant::getNullValue(NewOr->getType()));
2410  }
2411 
2412  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
2413  if (!LHSC || !RHSC)
2414  return nullptr;
2415 
2416  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
2417  // iff C2 + CA == C1.
2418  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
2419  ConstantInt *AddC;
2420  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
2421  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
2422  return Builder.CreateICmpULE(LHS0, LHSC);
2423  }
2424 
2425  // From here on, we only handle:
2426  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
2427  if (LHS0 != RHS0)
2428  return nullptr;
2429 
2430  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
2431  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
2432  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
2433  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
2434  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
2435  return nullptr;
2436 
2437  // We can't fold (ugt x, C) | (sgt x, C2).
2438  if (!predicatesFoldable(PredL, PredR))
2439  return nullptr;
2440 
2441  // Ensure that the larger constant is on the RHS.
2442  bool ShouldSwap;
2443  if (CmpInst::isSigned(PredL) ||
2444  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
2445  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
2446  else
2447  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
2448 
2449  if (ShouldSwap) {
2450  std::swap(LHS, RHS);
2451  std::swap(LHSC, RHSC);
2452  std::swap(PredL, PredR);
2453  }
2454 
2455  // At this point, we know we have two icmp instructions
2456  // comparing a value against two constants and or'ing the result
2457  // together. Because of the above check, we know that we only have
2458  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
2459  // icmp folding check above), that the two constants are not
2460  // equal.
2461  assert(LHSC != RHSC && "Compares not folded above?");
2462 
2463  switch (PredL) {
2464  default:
2465  llvm_unreachable("Unknown integer condition code!");
2466  case ICmpInst::ICMP_EQ:
2467  switch (PredR) {
2468  default:
2469  llvm_unreachable("Unknown integer condition code!");
2470  case ICmpInst::ICMP_EQ:
2471  // Potential folds for this case should already be handled.
2472  break;
2473  case ICmpInst::ICMP_UGT:
2474  // (X == 0 || X u> C) -> (X-1) u>= C
2475  if (LHSC->isMinValue(false))
2476  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2477  false, false);
2478  // (X == 13 | X u> 14) -> no change
2479  break;
2480  case ICmpInst::ICMP_SGT:
2481  // (X == INT_MIN || X s> C) -> (X-(INT_MIN+1)) u>= C-INT_MIN
2482  if (LHSC->isMinValue(true))
2483  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2484  true, false);
2485  // (X == 13 | X s> 14) -> no change
2486  break;
2487  }
2488  break;
2489  case ICmpInst::ICMP_ULT:
2490  switch (PredR) {
2491  default:
2492  llvm_unreachable("Unknown integer condition code!");
2493  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
2494  // (X u< C || X == UINT_MAX) => (X-C) u>= UINT_MAX-C
2495  if (RHSC->isMaxValue(false))
2496  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2497  false, false);
2498  break;
2499  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
2500  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
2501  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
2502  false, false);
2503  }
2504  break;
2505  case ICmpInst::ICMP_SLT:
2506  switch (PredR) {
2507  default:
2508  llvm_unreachable("Unknown integer condition code!");
2509  case ICmpInst::ICMP_EQ:
2510  // (X s< C || X == INT_MAX) => (X-C) u>= INT_MAX-C
2511  if (RHSC->isMaxValue(true))
2512  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2513  true, false);
2514  // (X s< 13 | X == 14) -> no change
2515  break;
2516  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) u> 2
2517  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
2518  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
2519  false);
2520  }
2521  break;
2522  }
2523  return nullptr;
2524 }
2525 
2526 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2527 // here. We should standardize that construct where it is needed or choose some
2528 // other way to ensure that commutated variants of patterns are not missed.
2530  if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
2531  SQ.getWithInstruction(&I)))
2532  return replaceInstUsesWith(I, V);
2533 
2534  if (SimplifyAssociativeOrCommutative(I))
2535  return &I;
2536 
2537  if (Instruction *X = foldVectorBinop(I))
2538  return X;
2539 
2540  // See if we can simplify any instructions used by the instruction whose sole
2541  // purpose is to compute bits we don't care about.
2542  if (SimplifyDemandedInstructionBits(I))
2543  return &I;
2544 
2545  // Do this before using distributive laws to catch simple and/or/not patterns.
2546  if (Instruction *Xor = foldOrToXor(I, Builder))
2547  return Xor;
2548 
2549  // (A&B)|(A&C) -> A&(B|C) etc
2550  if (Value *V = SimplifyUsingDistributiveLaws(I))
2551  return replaceInstUsesWith(I, V);
2552 
2553  if (Value *V = SimplifyBSwap(I, Builder))
2554  return replaceInstUsesWith(I, V);
2555 
2556  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2557  return FoldedLogic;
2558 
2559  if (Instruction *BSwap = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
2560  /*MatchBitReversals*/ false))
2561  return BSwap;
2562 
2563  if (Instruction *Funnel = matchFunnelShift(I, *this))
2564  return Funnel;
2565 
2567  return replaceInstUsesWith(I, Concat);
2568 
2569  Value *X, *Y;
2570  const APInt *CV;
2571  if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
2572  !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) {
2573  // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
2574  // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
2575  Value *Or = Builder.CreateOr(X, Y);
2576  return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
2577  }
2578 
2579  // (A & C)|(B & D)
2580  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2581  Value *A, *B, *C, *D;
2582  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2583  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2584  // (A & C1)|(B & C2)
2585  ConstantInt *C1, *C2;
2586  if (match(C, m_ConstantInt(C1)) && match(D, m_ConstantInt(C2))) {
2587  Value *V1 = nullptr, *V2 = nullptr;
2588  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2589  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2590  // iff (C1&C2) == 0 and (N&~C1) == 0
2591  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2592  ((V1 == B &&
2593  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2594  (V2 == B &&
2595  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2596  return BinaryOperator::CreateAnd(A,
2597  Builder.getInt(C1->getValue()|C2->getValue()));
2598  // Or commutes, try both ways.
2599  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2600  ((V1 == A &&
2601  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2602  (V2 == A &&
2603  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2604  return BinaryOperator::CreateAnd(B,
2605  Builder.getInt(C1->getValue()|C2->getValue()));
2606 
2607  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2608  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2609  ConstantInt *C3 = nullptr, *C4 = nullptr;
2610  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2611  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2612  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2613  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2614  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2615  return BinaryOperator::CreateAnd(V2,
2616  Builder.getInt(C1->getValue()|C2->getValue()));
2617  }
2618  }
2619 
2620  if (C1->getValue() == ~C2->getValue()) {
2621  Value *X;
2622 
2623  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2624  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2625  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2626  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2627  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2628  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2629 
2630  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2631  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2632  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2633  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2634  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2635  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2636  }
2637  }
2638 
2639  // Don't try to form a select if it's unlikely that we'll get rid of at
2640  // least one of the operands. A select is generally more expensive than the
2641  // 'or' that it is replacing.
2642  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2643  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2644  if (Value *V = matchSelectFromAndOr(A, C, B, D))
2645  return replaceInstUsesWith(I, V);
2646  if (Value *V = matchSelectFromAndOr(A, C, D, B))
2647  return replaceInstUsesWith(I, V);
2648  if (Value *V = matchSelectFromAndOr(C, A, B, D))
2649  return replaceInstUsesWith(I, V);
2650  if (Value *V = matchSelectFromAndOr(C, A, D, B))
2651  return replaceInstUsesWith(I, V);
2652  if (Value *V = matchSelectFromAndOr(B, D, A, C))
2653  return replaceInstUsesWith(I, V);
2654  if (Value *V = matchSelectFromAndOr(B, D, C, A))
2655  return replaceInstUsesWith(I, V);
2656  if (Value *V = matchSelectFromAndOr(D, B, A, C))
2657  return replaceInstUsesWith(I, V);
2658  if (Value *V = matchSelectFromAndOr(D, B, C, A))
2659  return replaceInstUsesWith(I, V);
2660  }
2661  }
2662 
2663  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2664  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2665  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2666  return BinaryOperator::CreateOr(Op0, C);
2667 
2668  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2669  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2670  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2671  return BinaryOperator::CreateOr(Op1, C);
2672 
2673  // ((B | C) & A) | B -> B | (A & C)
2674  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2675  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2676 
2677  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2678  return DeMorgan;
2679 
2680  // Canonicalize xor to the RHS.
2681  bool SwappedForXor = false;
2682  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2683  std::swap(Op0, Op1);
2684  SwappedForXor = true;
2685  }
2686 
2687  // A | ( A ^ B) -> A | B
2688  // A | (~A ^ B) -> A | ~B
2689  // (A & B) | (A ^ B)
2690  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2691  if (Op0 == A || Op0 == B)
2692  return BinaryOperator::CreateOr(A, B);
2693 
2694  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2695  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2696  return BinaryOperator::CreateOr(A, B);
2697 
2698  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2699  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2700  return BinaryOperator::CreateOr(Not, Op0);
2701  }
2702  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2703  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2704  return BinaryOperator::CreateOr(Not, Op0);
2705  }
2706  }
2707 
2708  // A | ~(A | B) -> A | ~B
2709  // A | ~(A ^ B) -> A | ~B
2710  if (match(Op1, m_Not(m_Value(A))))
2711  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2712  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2713  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2714  B->getOpcode() == Instruction::Xor)) {
2715  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2716  B->getOperand(0);
2717  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2718  return BinaryOperator::CreateOr(Not, Op0);
2719  }
2720 
2721  if (SwappedForXor)
2722  std::swap(Op0, Op1);
2723 
2724  {
2725  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2726  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2727  if (LHS && RHS)
2728  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2729  return replaceInstUsesWith(I, Res);
2730 
2731  // TODO: Make this recursive; it's a little tricky because an arbitrary
2732  // number of 'or' instructions might have to be created.
2733  Value *X, *Y;
2734  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2735  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2736  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2737  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2738  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2739  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2740  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2741  }
2742  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2743  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2744  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2745  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2746  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2747  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2748  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2749  }
2750  }
2751 
2752  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2753  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2754  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2755  return replaceInstUsesWith(I, Res);
2756 
2757  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2758  return FoldedFCmps;
2759 
2760  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2761  return CastedOr;
2762 
2763  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2764  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2765  A->getType()->isIntOrIntVectorTy(1))
2766  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2767  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2768  A->getType()->isIntOrIntVectorTy(1))
2769  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2770 
2771  // Note: If we've gotten to the point of visiting the outer OR, then the
2772  // inner one couldn't be simplified. If it was a constant, then it won't
2773  // be simplified by a later pass either, so we try swapping the inner/outer
2774  // ORs in the hopes that we'll be able to simplify it this way.
2775  // (X|C) | V --> (X|V) | C
2776  ConstantInt *CI;
2777  if (Op0->hasOneUse() && !match(Op1, m_ConstantInt()) &&
2778  match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
2779  Value *Inner = Builder.CreateOr(A, Op1);
2780  Inner->takeName(Op0);
2781  return BinaryOperator::CreateOr(Inner, CI);
2782  }
2783 
2784  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2785  // Since this OR statement hasn't been optimized further yet, we hope
2786  // that this transformation will allow the new ORs to be optimized.
2787  {
2788  Value *X = nullptr, *Y = nullptr;
2789  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2790  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2791  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2792  Value *orTrue = Builder.CreateOr(A, C);
2793  Value *orFalse = Builder.CreateOr(B, D);
2794  return SelectInst::Create(X, orTrue, orFalse);
2795  }
2796  }
2797 
2798  // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X.
2799  {
2800  Value *X, *Y;
2801  Type *Ty = I.getType();
2802  if (match(&I, m_c_Or(m_OneUse(m_AShr(
2803  m_NSWSub(m_Value(Y), m_Value(X)),
2804  m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
2805  m_Deferred(X)))) {
2806  Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
2807  Value *AllOnes = ConstantInt::getAllOnesValue(Ty);
2808  return SelectInst::Create(NewICmpInst, AllOnes, X);
2809  }
2810  }
2811 
2812  if (Instruction *V =
2813  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2814  return V;
2815 
2816  CmpInst::Predicate Pred;
2817  Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2818  // Check if the OR weakens the overflow condition for umul.with.overflow by
2819  // treating any non-zero result as overflow. In that case, we overflow if both
2820  // umul.with.overflow operands are != 0, as in that case the result can only
2821  // be 0, iff the multiplication overflows.
2822  if (match(&I,
2823  m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_Value(UMulWithOv)),
2824  m_Value(Ov)),
2825  m_CombineAnd(m_ICmp(Pred,
2826  m_CombineAnd(m_ExtractValue<0>(
2827  m_Deferred(UMulWithOv)),
2828  m_Value(Mul)),
2829  m_ZeroInt()),
2830  m_Value(MulIsNotZero)))) &&
2831  (Ov->hasOneUse() || (MulIsNotZero->hasOneUse() && Mul->hasOneUse())) &&
2832  Pred == CmpInst::ICMP_NE) {
2833  Value *A, *B;
2834  if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2835  m_Value(A), m_Value(B)))) {
2836  Value *NotNullA = Builder.CreateIsNotNull(A);
2837  Value *NotNullB = Builder.CreateIsNotNull(B);
2838  return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2839  }
2840  }
2841 
2842  // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions
2843  if (sinkNotIntoOtherHandOfAndOrOr(I))
2844  return &I;
2845 
2846  // Improve "get low bit mask up to and including bit X" pattern:
2847  // (1 << X) | ((1 << X) + -1) --> -1 l>> (bitwidth(x) - 1 - X)
2848  if (match(&I, m_c_Or(m_Add(m_Shl(m_One(), m_Value(X)), m_AllOnes()),
2849  m_Shl(m_One(), m_Deferred(X)))) &&
2850  match(&I, m_c_Or(m_OneUse(m_Value()), m_Value()))) {
2851  Type *Ty = X->getType();
2852  Value *Sub = Builder.CreateSub(
2853  ConstantInt::get(Ty, Ty->getScalarSizeInBits() - 1), X);
2854  return BinaryOperator::CreateLShr(Constant::getAllOnesValue(Ty), Sub);
2855  }
2856 
2857  // An or recurrence w/loop invariant step is equivelent to (or start, step)
2858  PHINode *PN = nullptr;
2859  Value *Start = nullptr, *Step = nullptr;
2860  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2861  return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
2862 
2863  return nullptr;
2864 }
2865 
2866 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2867 /// can fold these early and efficiently by morphing an existing instruction.
2870  assert(I.getOpcode() == Instruction::Xor);
2871  Value *Op0 = I.getOperand(0);
2872  Value *Op1 = I.getOperand(1);
2873  Value *A, *B;
2874 
2875  // There are 4 commuted variants for each of the basic patterns.
2876 
2877  // (A & B) ^ (A | B) -> A ^ B
2878  // (A & B) ^ (B | A) -> A ^ B
2879  // (A | B) ^ (A & B) -> A ^ B
2880  // (A | B) ^ (B & A) -> A ^ B
2881  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2882  m_c_Or(m_Deferred(A), m_Deferred(B)))))
2883  return BinaryOperator::CreateXor(A, B);
2884 
2885  // (A | ~B) ^ (~A | B) -> A ^ B
2886  // (~B | A) ^ (~A | B) -> A ^ B
2887  // (~A | B) ^ (A | ~B) -> A ^ B
2888  // (B | ~A) ^ (A | ~B) -> A ^ B
2889  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2890  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
2891  return BinaryOperator::CreateXor(A, B);
2892 
2893  // (A & ~B) ^ (~A & B) -> A ^ B
2894  // (~B & A) ^ (~A & B) -> A ^ B
2895  // (~A & B) ^ (A & ~B) -> A ^ B
2896  // (B & ~A) ^ (A & ~B) -> A ^ B
2897  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2898  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B)))))
2899  return BinaryOperator::CreateXor(A, B);
2900 
2901  // For the remaining cases we need to get rid of one of the operands.
2902  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2903  return nullptr;
2904 
2905  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2906  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2907  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2908  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2909  // Complexity sorting ensures the not will be on the right side.
2910  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2911  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2912  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2913  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2914  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2915 
2916  return nullptr;
2917 }
2918 
2919 Value *InstCombinerImpl::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2920  BinaryOperator &I) {
2921  assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
2922  I.getOperand(1) == RHS && "Should be 'xor' with these operands");
2923 
2924  if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2925  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2926  LHS->getOperand(1) == RHS->getOperand(0))
2927  LHS->swapOperands();
2928  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2929  LHS->getOperand(1) == RHS->getOperand(1)) {
2930  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2931  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2932  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2933  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2934  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
2935  }
2936  }
2937 
2938  // TODO: This can be generalized to compares of non-signbits using
2939  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
2940  // foldLogOpOfMaskedICmps().
2941  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2942  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
2943  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
2944  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
2945  LHS0->getType() == RHS0->getType() &&
2946  LHS0->getType()->isIntOrIntVectorTy()) {
2947  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
2948  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
2949  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2950  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
2951  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2952  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
2953  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
2954  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
2955  }
2956  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
2957  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
2958  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
2959  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
2960  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
2961  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
2962  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
2963  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
2964  }
2965  }
2966 
2967  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2968  // into those logic ops. That is, try to turn this into an and-of-icmps
2969  // because we have many folds for that pattern.
2970  //
2971  // This is based on a truth table definition of xor:
2972  // X ^ Y --> (X | Y) & !(X & Y)
2973  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2974  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2975  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2976  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2977  // TODO: Independently handle cases where the 'and' side is a constant.
2978  ICmpInst *X = nullptr, *Y = nullptr;
2979  if (OrICmp == LHS && AndICmp == RHS) {
2980  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS --> X & !Y
2981  X = LHS;
2982  Y = RHS;
2983  }
2984  if (OrICmp == RHS && AndICmp == LHS) {
2985  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS --> !Y & X
2986  X = RHS;
2987  Y = LHS;
2988  }
2989  if (X && Y && (Y->hasOneUse() || canFreelyInvertAllUsersOf(Y, &I))) {
2990  // Invert the predicate of 'Y', thus inverting its output.
2991  Y->setPredicate(Y->getInversePredicate());
2992  // So, are there other uses of Y?
2993  if (!Y->hasOneUse()) {
2994  // We need to adapt other uses of Y though. Get a value that matches
2995  // the original value of Y before inversion. While this increases
2996  // immediate instruction count, we have just ensured that all the
2997  // users are freely-invertible, so that 'not' *will* get folded away.
2999  // Set insertion point to right after the Y.
3000  Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
3001  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3002  // Replace all uses of Y (excluding the one in NotY!) with NotY.
3003  Worklist.pushUsersToWorkList(*Y);
3004  Y->replaceUsesWithIf(NotY,
3005  [NotY](Use &U) { return U.getUser() != NotY; });
3006  }
3007  // All done.
3008  return Builder.CreateAnd(LHS, RHS);
3009  }
3010  }
3011  }
3012 
3013  return nullptr;
3014 }
3015 
3016 /// If we have a masked merge, in the canonical form of:
3017 /// (assuming that A only has one use.)
3018 /// | A | |B|
3019 /// ((x ^ y) & M) ^ y
3020 /// | D |
3021 /// * If M is inverted:
3022 /// | D |
3023 /// ((x ^ y) & ~M) ^ y
3024 /// We can canonicalize by swapping the final xor operand
3025 /// to eliminate the 'not' of the mask.
3026 /// ((x ^ y) & M) ^ x
3027 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
3028 /// because that shortens the dependency chain and improves analysis:
3029 /// (x & M) | (y & ~M)
3032  Value *B, *X, *D;
3033  Value *M;
3034  if (!match(&I, m_c_Xor(m_Value(B),
3035  m_OneUse(m_c_And(
3037  m_Value(D)),
3038  m_Value(M))))))
3039  return nullptr;
3040 
3041  Value *NotM;
3042  if (match(M, m_Not(m_Value(NotM)))) {
3043  // De-invert the mask and swap the value in B part.
3044  Value *NewA = Builder.CreateAnd(D, NotM);
3045  return BinaryOperator::CreateXor(NewA, X);
3046  }
3047 
3048  Constant *C;
3049  if (D->hasOneUse() && match(M, m_Constant(C))) {
3050  // Propagating undef is unsafe. Clamp undef elements to -1.
3051  Type *EltTy = C->getType()->getScalarType();
3053  // Unfold.
3054  Value *LHS = Builder.CreateAnd(X, C);
3055  Value *NotC = Builder.CreateNot(C);
3056  Value *RHS = Builder.CreateAnd(B, NotC);
3057  return BinaryOperator::CreateOr(LHS, RHS);
3058  }
3059 
3060  return nullptr;
3061 }
3062 
3063 // Transform
3064 // ~(x ^ y)
3065 // into:
3066 // (~x) ^ y
3067 // or into
3068 // x ^ (~y)
3071  Value *X, *Y;
3072  // FIXME: one-use check is not needed in general, but currently we are unable
3073  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
3074  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
3075  return nullptr;
3076 
3077  // We only want to do the transform if it is free to do.
3078  if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) {
3079  // Ok, good.
3080  } else if (InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) {
3081  std::swap(X, Y);
3082  } else
3083  return nullptr;
3084 
3085  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
3086  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
3087 }
3088 
3089 /// Canonicalize a shifty way to code absolute value to the more common pattern
3090 /// that uses negation and select.
3093  assert(Xor.getOpcode() == Instruction::Xor && "Expected an xor instruction.");
3094 
3095  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
3096  // We're relying on the fact that we only do this transform when the shift has
3097  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
3098  // instructions).
3099  Value *Op0 = Xor.getOperand(0), *Op1 = Xor.getOperand(1);
3100  if (Op0->hasNUses(2))
3101  std::swap(Op0, Op1);
3102 
3103  Type *Ty = Xor.getType();
3104  Value *A;
3105  const APInt *ShAmt;
3106  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
3107  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
3108  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
3109  // Op1 = ashr i32 A, 31 ; smear the sign bit
3110  // xor (add A, Op1), Op1 ; add -1 and flip bits if negative
3111  // --> (A < 0) ? -A : A
3112  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
3113  // Copy the nuw/nsw flags from the add to the negate.
3114  auto *Add = cast<BinaryOperator>(Op0);
3115  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
3116  Add->hasNoSignedWrap());
3117  return SelectInst::Create(Cmp, Neg, A);
3118  }
3119  return nullptr;
3120 }
3121 
3122 // Transform
3123 // z = (~x) &/| y
3124 // into:
3125 // z = ~(x |/& (~y))
3126 // iff y is free to invert and all uses of z can be freely updated.
3128  Instruction::BinaryOps NewOpc;
3129  switch (I.getOpcode()) {
3130  case Instruction::And:
3131  NewOpc = Instruction::Or;
3132  break;
3133  case Instruction::Or:
3134  NewOpc = Instruction::And;
3135  break;
3136  default:
3137  return false;
3138  };
3139 
3140  Value *X, *Y;
3141  if (!match(&I, m_c_BinOp(m_Not(m_Value(X)), m_Value(Y))))
3142  return false;
3143 
3144  // Will we be able to fold the `not` into Y eventually?
3145  if (!InstCombiner::isFreeToInvert(Y, Y->hasOneUse()))
3146  return false;
3147 
3148  // And can our users be adapted?
3149  if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
3150  return false;
3151 
3152  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3153  Value *NewBinOp =
3154  BinaryOperator::Create(NewOpc, X, NotY, I.getName() + ".not");
3155  Builder.Insert(NewBinOp);
3156  replaceInstUsesWith(I, NewBinOp);
3157  // We can not just create an outer `not`, it will most likely be immediately
3158  // folded back, reconstructing our initial pattern, and causing an
3159  // infinite combine loop, so immediately manually fold it away.
3160  freelyInvertAllUsersOf(NewBinOp);
3161  return true;
3162 }
3163 
3164 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
3165 // here. We should standardize that construct where it is needed or choose some
3166 // other way to ensure that commutated variants of patterns are not missed.
3168  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
3169  SQ.getWithInstruction(&I)))
3170  return replaceInstUsesWith(I, V);
3171 
3172  if (SimplifyAssociativeOrCommutative(I))
3173  return &I;
3174 
3175  if (Instruction *X = foldVectorBinop(I))
3176  return X;
3177 
3178  if (Instruction *NewXor = foldXorToXor(I, Builder))
3179  return NewXor;
3180 
3181  // (A&B)^(A&C) -> A&(B^C) etc
3182  if (Value *V = SimplifyUsingDistributiveLaws(I))
3183  return replaceInstUsesWith(I, V);
3184 
3185  // See if we can simplify any instructions used by the instruction whose sole
3186  // purpose is to compute bits we don't care about.
3187  if (SimplifyDemandedInstructionBits(I))
3188  return &I;
3189 
3190  if (Value *V = SimplifyBSwap(I, Builder))
3191  return replaceInstUsesWith(I, V);
3192 
3193  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3194  Type *Ty = I.getType();
3195 
3196  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
3197  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
3198  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
3199  // have already taken care of those cases.
3200  Value *M;
3201  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
3202  m_c_And(m_Deferred(M), m_Value()))))
3203  return BinaryOperator::CreateOr(Op0, Op1);
3204 
3205  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
3206  Value *X, *Y;
3207 
3208  // We must eliminate the and/or (one-use) for these transforms to not increase
3209  // the instruction count.
3210  // ~(~X & Y) --> (X | ~Y)
3211  // ~(Y & ~X) --> (X | ~Y)
3212  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
3213  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3214  return BinaryOperator::CreateOr(X, NotY);
3215  }
3216  // ~(~X | Y) --> (X & ~Y)
3217  // ~(Y | ~X) --> (X & ~Y)
3218  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
3219  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3220  return BinaryOperator::CreateAnd(X, NotY);
3221  }
3222 
3224  return Xor;
3225 
3226  // Is this a 'not' (~) fed by a binary operator?
3227  BinaryOperator *NotVal;
3228  if (match(&I, m_Not(m_BinOp(NotVal)))) {
3229  if (NotVal->getOpcode() == Instruction::And ||
3230  NotVal->getOpcode() == Instruction::Or) {
3231  // Apply DeMorgan's Law when inverts are free:
3232  // ~(X & Y) --> (~X | ~Y)
3233  // ~(X | Y) --> (~X & ~Y)
3234  if (isFreeToInvert(NotVal->getOperand(0),
3235  NotVal->getOperand(0)->hasOneUse()) &&
3236  isFreeToInvert(NotVal->getOperand(1),
3237  NotVal->getOperand(1)->hasOneUse())) {
3238  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
3239  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
3240  if (NotVal->getOpcode() == Instruction::And)
3241  return BinaryOperator::CreateOr(NotX, NotY);
3242  return BinaryOperator::CreateAnd(NotX, NotY);
3243  }
3244  }
3245 
3246  // ~(X - Y) --> ~X + Y
3247  if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
3248  if (isa<Constant>(X) || NotVal->hasOneUse())
3249  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
3250 
3251  // ~((-X) | Y) --> (X - 1) & (~Y)
3252  if (match(NotVal,
3254  Value *DecX = Builder.CreateAdd(X, ConstantInt::getAllOnesValue(Ty));
3255  Value *NotY = Builder.CreateNot(Y);
3256  return BinaryOperator::CreateAnd(DecX, NotY);
3257  }
3258 
3259  // ~(~X >>s Y) --> (X >>s Y)
3260  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
3261  return BinaryOperator::CreateAShr(X, Y);
3262 
3263  // If we are inverting a right-shifted constant, we may be able to eliminate
3264  // the 'not' by inverting the constant and using the opposite shift type.
3265  // Canonicalization rules ensure that only a negative constant uses 'ashr',
3266  // but we must check that in case that transform has not fired yet.
3267 
3268  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
3269  Constant *C;
3270  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
3271  match(C, m_Negative())) {
3272  // We matched a negative constant, so propagating undef is unsafe.
3273  // Clamp undef elements to -1.
3274  Type *EltTy = Ty->getScalarType();
3276  return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
3277  }
3278 
3279  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
3280  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
3281  match(C, m_NonNegative())) {
3282  // We matched a non-negative constant, so propagating undef is unsafe.
3283  // Clamp undef elements to 0.
3284  Type *EltTy = Ty->getScalarType();
3286  return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
3287  }
3288 
3289  // ~(X + C) --> -(C + 1) - X
3290  if (match(Op0, m_Add(m_Value(X), m_Constant(C))))
3291  return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X);
3292 
3293  // ~(~X + Y) --> X - Y
3294  if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
3295  return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
3296  NotVal);
3297  }
3298 
3299  // Use DeMorgan and reassociation to eliminate a 'not' op.
3300  Constant *C1;
3301  if (match(Op1, m_Constant(C1))) {
3302  Constant *C2;
3303  if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
3304  // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
3305  Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2));
3306  return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
3307  }
3308  if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
3309  // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
3310  Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2));
3311  return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
3312  }
3313  }
3314 
3315  // not (cmp A, B) = !cmp A, B
3316  CmpInst::Predicate Pred;
3317  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
3318  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
3319  return replaceInstUsesWith(I, Op0);
3320  }
3321 
3322  {
3323  const APInt *RHSC;
3324  if (match(Op1, m_APInt(RHSC))) {
3325  Value *X;
3326  const APInt *C;
3327  // (C - X) ^ signmaskC --> (C + signmaskC) - X
3328  if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X))))
3329  return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C + *RHSC), X);
3330 
3331  // (X + C) ^ signmaskC --> X + (C + signmaskC)
3332  if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
3333  return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
3334 
3335  // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
3336  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
3337  MaskedValueIsZero(X, *C, 0, &I))
3338  return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
3339 
3340  // If RHSC is inverting the remaining bits of shifted X,
3341  // canonicalize to a 'not' before the shift to help SCEV and codegen:
3342  // (X << C) ^ RHSC --> ~X << C
3343  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
3344  *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).shl(*C)) {
3345  Value *NotX = Builder.CreateNot(X);
3346  return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
3347  }
3348  // (X >>u C) ^ RHSC --> ~X >>u C
3349  if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
3350  *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).lshr(*C)) {
3351  Value *NotX = Builder.CreateNot(X);
3352  return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
3353  }
3354  // TODO: We could handle 'ashr' here as well. That would be matching
3355  // a 'not' op and moving it before the shift. Doing that requires
3356  // preventing the inverse fold in canShiftBinOpWithConstantRHS().
3357  }
3358  }
3359 
3360  // FIXME: This should not be limited to scalar (pull into APInt match above).
3361  {
3362  Value *X;
3363  ConstantInt *C1, *C2, *C3;
3364  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
3365  if (match(Op1, m_ConstantInt(C3)) &&
3367  m_ConstantInt(C2))) &&
3368  Op0->hasOneUse()) {
3369  // fold (C1 >> C2) ^ C3
3370  APInt FoldConst = C1->getValue().lshr(C2->getValue());
3371  FoldConst ^= C3->getValue();
3372  // Prepare the two operands.
3373  auto *Opnd0 = cast<Instruction>(Builder.CreateLShr(X, C2));
3374  Opnd0->takeName(cast<Instruction>(Op0));
3375  Opnd0->setDebugLoc(I.getDebugLoc());
3376  return BinaryOperator::CreateXor(Opnd0, ConstantInt::get(Ty, FoldConst));
3377  }
3378  }
3379 
3380  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
3381  return FoldedLogic;
3382 
3383  // Y ^ (X | Y) --> X & ~Y
3384  // Y ^ (Y | X) --> X & ~Y
3385  if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
3386  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
3387  // (X | Y) ^ Y --> X & ~Y
3388  // (Y | X) ^ Y --> X & ~Y
3389  if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
3390  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
3391 
3392  // Y ^ (X & Y) --> ~X & Y
3393  // Y ^ (Y & X) --> ~X & Y
3394  if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
3395  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
3396  // (X & Y) ^ Y --> ~X & Y
3397  // (Y & X) ^ Y --> ~X & Y
3398  // Canonical form is (X & C) ^ C; don't touch that.
3399  // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
3400  // be fixed to prefer that (otherwise we get infinite looping).
3401  if (!match(Op1, m_Constant()) &&
3402  match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
3403  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
3404 
3405  Value *A, *B, *C;
3406  // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
3407  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3408  m_OneUse(m_c_Or(m_Deferred(A), m_Value(C))))))
3409  return BinaryOperator::CreateXor(
3410  Builder.CreateAnd(Builder.CreateNot(A), C), B);
3411 
3412  // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
3413  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3415  return BinaryOperator::CreateXor(
3416  Builder.CreateAnd(Builder.CreateNot(B), C), A);
3417 
3418  // (A & B) ^ (A ^ B) -> (A | B)
3419  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
3420  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
3421  return BinaryOperator::CreateOr(A, B);
3422  // (A ^ B) ^ (A & B) -> (A | B)
3423  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
3424  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
3425  return BinaryOperator::CreateOr(A, B);
3426 
3427  // (A & ~B) ^ ~A -> ~(A & B)
3428  // (~B & A) ^ ~A -> ~(A & B)
3429  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
3430  match(Op1, m_Not(m_Specific(A))))
3431  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
3432 
3433  // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
3434  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
3435  return BinaryOperator::CreateOr(A, B);
3436 
3437  // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
3438  // TODO: Loosen one-use restriction if common operand is a constant.
3439  Value *D;
3440  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
3441  match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
3442  if (B == C || B == D)
3443  std::swap(A, B);
3444  if (A == C)
3445  std::swap(C, D);
3446  if (A == D) {
3447  Value *NotA = Builder.CreateNot(A);
3448  return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
3449  }
3450  }
3451 
3452  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
3453  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
3454  if (Value *V = foldXorOfICmps(LHS, RHS, I))
3455  return replaceInstUsesWith(I, V);
3456 
3457  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
3458  return CastedXor;
3459 
3460  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3461  // ~min(~X, ~Y) --> max(X, Y)
3462  // ~max(~X, Y) --> min(X, ~Y)
3463  auto *II = dyn_cast<IntrinsicInst>(Op0);
3464  if (II && match(Op1, m_AllOnes())) {
3465  if (match(Op0, m_MaxOrMin(m_Not(m_Value(X)), m_Not(m_Value(Y))))) {
3466  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3467  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
3468  return replaceInstUsesWith(I, InvMaxMin);
3469  }
3470  if (match(Op0, m_OneUse(m_c_MaxOrMin(m_Not(m_Value(X)), m_Value(Y))))) {
3471  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3472  Value *NotY = Builder.CreateNot(Y);
3473  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotY);
3474  return replaceInstUsesWith(I, InvMaxMin);
3475  }
3476  }
3477 
3478  // TODO: Remove folds if we canonicalize to intrinsics (see above).
3479  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3480  //
3481  // %notx = xor i32 %x, -1
3482  // %cmp1 = icmp sgt i32 %notx, %y
3483  // %smax = select i1 %cmp1, i32 %notx, i32 %y
3484  // %res = xor i32 %smax, -1
3485  // =>
3486  // %noty = xor i32 %y, -1
3487  // %cmp2 = icmp slt %x, %noty
3488  // %res = select i1 %cmp2, i32 %x, i32 %noty
3489  //
3490  // Same is applicable for smin/umax/umin.
3491  if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) {
3492  Value *LHS, *RHS;
3493  SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor;
3495  // It's possible we get here before the not has been simplified, so make
3496  // sure the input to the not isn't freely invertible.
3497  if (match(LHS, m_Not(m_Value(X))) && !isFreeToInvert(X, X->hasOneUse())) {
3498  Value *NotY = Builder.CreateNot(RHS);
3499  return SelectInst::Create(
3500  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
3501  }
3502 
3503  // It's possible we get here before the not has been simplified, so make
3504  // sure the input to the not isn't freely invertible.
3505  if (match(RHS, m_Not(m_Value(Y))) && !isFreeToInvert(Y, Y->hasOneUse())) {
3506  Value *NotX = Builder.CreateNot(LHS);
3507  return SelectInst::Create(
3508  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y);
3509  }
3510 
3511  // If both sides are freely invertible, then we can get rid of the xor
3512  // completely.
3513  if (isFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
3514  isFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) {
3515  Value *NotLHS = Builder.CreateNot(LHS);
3516  Value *NotRHS = Builder.CreateNot(RHS);
3517  return SelectInst::Create(
3518  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
3519  NotLHS, NotRHS);
3520  }
3521  }
3522 
3523  // Pull 'not' into operands of select if both operands are one-use compares
3524  // or one is one-use compare and the other one is a constant.
3525  // Inverting the predicates eliminates the 'not' operation.
3526  // Example:
3527  // not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
3528  // select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
3529  // not (select ?, (cmp TPred, ?, ?), true -->
3530  // select ?, (cmp InvTPred, ?, ?), false
3531  if (auto *Sel = dyn_cast<SelectInst>(Op0)) {
3532  Value *TV = Sel->getTrueValue();
3533  Value *FV = Sel->getFalseValue();
3534  auto *CmpT = dyn_cast<CmpInst>(TV);
3535  auto *CmpF = dyn_cast<CmpInst>(FV);
3536  bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3537  bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3538  if (InvertibleT && InvertibleF) {
3539  if (CmpT)
3540  CmpT->setPredicate(CmpT->getInversePredicate());
3541  else
3542  Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
3543  if (CmpF)
3544  CmpF->setPredicate(CmpF->getInversePredicate());
3545  else
3546  Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
3547  return replaceInstUsesWith(I, Sel);
3548  }
3549  }
3550  }
3551 
3552  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
3553  return NewXor;
3554 
3555  if (Instruction *Abs = canonicalizeAbs(I, Builder))
3556  return Abs;
3557 
3558  // Otherwise, if all else failed, try to hoist the xor-by-constant:
3559  // (X ^ C) ^ Y --> (X ^ Y) ^ C
3560  // Just like we do in other places, we completely avoid the fold
3561  // for constantexprs, at least to avoid endless combine loop.
3564  m_ImmConstant(C1))),
3565  m_Value(Y))))
3566  return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
3567 
3568  return nullptr;
3569 }
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:479
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
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:2658
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:359
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:447
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:1295
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:171
AMask_Mixed
@ AMask_Mixed
Definition: InstCombineAndOrXor.cpp:178
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2097
llvm::Function
Definition: Function.h:61
llvm::InstCombinerImpl::visitXor
Instruction * visitXor(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:3167
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:2209
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2605
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:681
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1142
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:469
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:5179
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:131
llvm::ConstantExpr::getSExt
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2083
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
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:223
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:1003
peekThroughBitcast
static Register peekThroughBitcast(Register Reg, const MachineRegisterInfo &MRI)
Definition: CombinerHelper.cpp:1967
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:730
llvm::matchSimpleRecurrence
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
Definition: ValueTracking.cpp:6216
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:2945
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:2117
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:2151
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:308
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:1148
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:383
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::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:211
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:491
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:6084
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:2229
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:2267
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:657
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:815
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:2185
llvm::PatternMatch::m_c_MaxOrMin
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty, true > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty, true > > > m_c_MaxOrMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:2302
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:174
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:2208
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:270
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:2200
llvm::SimplifyQuery::AC
AssumptionCache * AC
Definition: InstructionSimplify.h:98
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:1999
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:1467
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:888
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:689
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:3712
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:705
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:95
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1634
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:2215
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_MaxOrMin
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1887
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:145
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:2236
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:2731
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:60
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:885
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1189
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:74
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:276
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:2868
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:513
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:544
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1130
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:2069
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:535
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:2015
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:781
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:765
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:5227
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1124
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:445
llvm::Value::hasNUsesOrMore
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
Definition: Value.cpp:155
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:3030
llvm::ConstantExpr::getOr
static Constant * getOr(Constant *C1, Constant *C2)
Definition: Constants.cpp:2727
llvm::SimplifyQuery::DT
const DominatorTree * DT
Definition: InstructionSimplify.h:97
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:1118
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:211
sinkNotIntoXor
static Instruction * sinkNotIntoXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:3069
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:1015
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
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:121
llvm::PatternMatch::m_Negative
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:467
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:142
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
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:2529
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:1628
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:880
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:216
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:626
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:256
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
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:204
llvm::recognizeBSwapOrBitReverseIdiom
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3091
llvm::RecurKind::Mul
@ Mul
Product of integers.
canonicalizeAbs
static Instruction * canonicalizeAbs(BinaryOperator &Xor, InstCombiner::BuilderTy &Builder)
Canonicalize a shifty way to code absolute value to the more common pattern that uses negation and se...
Definition: InstCombineAndOrXor.cpp:3091
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:6172
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:299
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:2645
llvm::SimplifyQuery::CxtI
const Instruction * CxtI
Definition: InstructionSimplify.h:99
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2664
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:899
llvm::InstCombinerImpl::sinkNotIntoOtherHandOfAndOrOr
bool sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:3127
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:580
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:151
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::ConstantExpr::getAnd
static Constant * getAnd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2723
llvm::PatternMatch::m_BSwap
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
Definition: PatternMatch.h:2156
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:522
llvm::getInverseMinMaxIntrinsic
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
Definition: ValueTracking.cpp:6162
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:403
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:2243
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:1316
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:696
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:789
llvm::APInt::isNullValue
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:411
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:768
llvm::PatternMatch::m_ConstantExpr
class_match< ConstantExpr > m_ConstantExpr()
Match an arbitrary ConstantExpr and ignore it.
Definition: PatternMatch.h:155
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:802
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:1399
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:2385
llvm::PHINode
Definition: Instructions.h:2572
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:1405
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:2170
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:2251
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:295
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:377
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:1616
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:2549
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:1136
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:2433
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:461
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:1070
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1163
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:38