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