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  // Special case: get the ordering right when the values wrap around zero.
778  // Ie, we assumed the constants were unsigned when swapping earlier.
779  if (C1->isZero() && C2->isAllOnes())
780  std::swap(C1, C2);
781 
782  if (*C1 == *C2 - 1) {
783  // (X == 13 || X == 14) --> X - 13 <=u 1
784  // (X != 13 && X != 14) --> X - 13 >u 1
785  // An 'add' is the canonical IR form, so favor that over a 'sub'.
786  Value *Add = Builder.CreateAdd(X, ConstantInt::get(X->getType(), -(*C1)));
787  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
788  return Builder.CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
789  }
790 
791  return nullptr;
792 }
793 
794 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
795 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
796 Value *InstCombinerImpl::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS,
797  ICmpInst *RHS,
798  Instruction *CxtI,
799  bool IsAnd,
800  bool IsLogical) {
802  if (LHS->getPredicate() != Pred || RHS->getPredicate() != Pred)
803  return nullptr;
804 
805  if (!match(LHS->getOperand(1), m_Zero()) ||
806  !match(RHS->getOperand(1), m_Zero()))
807  return nullptr;
808 
809  Value *L1, *L2, *R1, *R2;
810  if (match(LHS->getOperand(0), m_And(m_Value(L1), m_Value(L2))) &&
811  match(RHS->getOperand(0), m_And(m_Value(R1), m_Value(R2)))) {
812  if (L1 == R2 || L2 == R2)
813  std::swap(R1, R2);
814  if (L2 == R1)
815  std::swap(L1, L2);
816 
817  if (L1 == R1 &&
818  isKnownToBeAPowerOfTwo(L2, false, 0, CxtI) &&
819  isKnownToBeAPowerOfTwo(R2, false, 0, CxtI)) {
820  // If this is a logical and/or, then we must prevent propagation of a
821  // poison value from the RHS by inserting freeze.
822  if (IsLogical)
823  R2 = Builder.CreateFreeze(R2);
824  Value *Mask = Builder.CreateOr(L2, R2);
825  Value *Masked = Builder.CreateAnd(L1, Mask);
826  auto NewPred = IsAnd ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
827  return Builder.CreateICmp(NewPred, Masked, Mask);
828  }
829  }
830 
831  return nullptr;
832 }
833 
834 /// General pattern:
835 /// X & Y
836 ///
837 /// Where Y is checking that all the high bits (covered by a mask 4294967168)
838 /// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0
839 /// Pattern can be one of:
840 /// %t = add i32 %arg, 128
841 /// %r = icmp ult i32 %t, 256
842 /// Or
843 /// %t0 = shl i32 %arg, 24
844 /// %t1 = ashr i32 %t0, 24
845 /// %r = icmp eq i32 %t1, %arg
846 /// Or
847 /// %t0 = trunc i32 %arg to i8
848 /// %t1 = sext i8 %t0 to i32
849 /// %r = icmp eq i32 %t1, %arg
850 /// This pattern is a signed truncation check.
851 ///
852 /// And X is checking that some bit in that same mask is zero.
853 /// I.e. can be one of:
854 /// %r = icmp sgt i32 %arg, -1
855 /// Or
856 /// %t = and i32 %arg, 2147483648
857 /// %r = icmp eq i32 %t, 0
858 ///
859 /// Since we are checking that all the bits in that mask are the same,
860 /// and a particular bit is zero, what we are really checking is that all the
861 /// masked bits are zero.
862 /// So this should be transformed to:
863 /// %r = icmp ult i32 %arg, 128
865  Instruction &CxtI,
867  assert(CxtI.getOpcode() == Instruction::And);
868 
869  // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two)
870  auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X,
871  APInt &SignBitMask) -> bool {
872  CmpInst::Predicate Pred;
873  const APInt *I01, *I1; // powers of two; I1 == I01 << 1
874  if (!(match(ICmp,
875  m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) &&
876  Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1))
877  return false;
878  // Which bit is the new sign bit as per the 'signed truncation' pattern?
879  SignBitMask = *I01;
880  return true;
881  };
882 
883  // One icmp needs to be 'signed truncation check'.
884  // We need to match this first, else we will mismatch commutative cases.
885  Value *X1;
886  APInt HighestBit;
887  ICmpInst *OtherICmp;
888  if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit))
889  OtherICmp = ICmp0;
890  else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit))
891  OtherICmp = ICmp1;
892  else
893  return nullptr;
894 
895  assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)");
896 
897  // Try to match/decompose into: icmp eq (X & Mask), 0
898  auto tryToDecompose = [](ICmpInst *ICmp, Value *&X,
899  APInt &UnsetBitsMask) -> bool {
900  CmpInst::Predicate Pred = ICmp->getPredicate();
901  // Can it be decomposed into icmp eq (X & Mask), 0 ?
902  if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1),
903  Pred, X, UnsetBitsMask,
904  /*LookThroughTrunc=*/false) &&
905  Pred == ICmpInst::ICMP_EQ)
906  return true;
907  // Is it icmp eq (X & Mask), 0 already?
908  const APInt *Mask;
909  if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) &&
910  Pred == ICmpInst::ICMP_EQ) {
911  UnsetBitsMask = *Mask;
912  return true;
913  }
914  return false;
915  };
916 
917  // And the other icmp needs to be decomposable into a bit test.
918  Value *X0;
919  APInt UnsetBitsMask;
920  if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask))
921  return nullptr;
922 
923  assert(!UnsetBitsMask.isZero() && "empty mask makes no sense.");
924 
925  // Are they working on the same value?
926  Value *X;
927  if (X1 == X0) {
928  // Ok as is.
929  X = X1;
930  } else if (match(X0, m_Trunc(m_Specific(X1)))) {
931  UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits());
932  X = X1;
933  } else
934  return nullptr;
935 
936  // So which bits should be uniform as per the 'signed truncation check'?
937  // (all the bits starting with (i.e. including) HighestBit)
938  APInt SignBitsMask = ~(HighestBit - 1U);
939 
940  // UnsetBitsMask must have some common bits with SignBitsMask,
941  if (!UnsetBitsMask.intersects(SignBitsMask))
942  return nullptr;
943 
944  // Does UnsetBitsMask contain any bits outside of SignBitsMask?
945  if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) {
946  APInt OtherHighestBit = (~UnsetBitsMask) + 1U;
947  if (!OtherHighestBit.isPowerOf2())
948  return nullptr;
949  HighestBit = APIntOps::umin(HighestBit, OtherHighestBit);
950  }
951  // Else, if it does not, then all is ok as-is.
952 
953  // %r = icmp ult %X, SignBit
954  return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit),
955  CxtI.getName() + ".simplified");
956 }
957 
958 /// Reduce a pair of compares that check if a value has exactly 1 bit set.
959 static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd,
961  // Handle 'and' / 'or' commutation: make the equality check the first operand.
962  if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE)
963  std::swap(Cmp0, Cmp1);
964  else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ)
965  std::swap(Cmp0, Cmp1);
966 
967  // (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1
968  CmpInst::Predicate Pred0, Pred1;
969  Value *X;
970  if (JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
971  match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
972  m_SpecificInt(2))) &&
973  Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT) {
974  Value *CtPop = Cmp1->getOperand(0);
975  return Builder.CreateICmpEQ(CtPop, ConstantInt::get(CtPop->getType(), 1));
976  }
977  // (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1
978  if (!JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
979  match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
980  m_SpecificInt(1))) &&
981  Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_UGT) {
982  Value *CtPop = Cmp1->getOperand(0);
983  return Builder.CreateICmpNE(CtPop, ConstantInt::get(CtPop->getType(), 1));
984  }
985  return nullptr;
986 }
987 
988 /// Commuted variants are assumed to be handled by calling this function again
989 /// with the parameters swapped.
991  ICmpInst *UnsignedICmp, bool IsAnd,
992  const SimplifyQuery &Q,
994  Value *ZeroCmpOp;
995  ICmpInst::Predicate EqPred;
996  if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(ZeroCmpOp), m_Zero())) ||
997  !ICmpInst::isEquality(EqPred))
998  return nullptr;
999 
1000  auto IsKnownNonZero = [&](Value *V) {
1001  return isKnownNonZero(V, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1002  };
1003 
1004  ICmpInst::Predicate UnsignedPred;
1005 
1006  Value *A, *B;
1007  if (match(UnsignedICmp,
1008  m_c_ICmp(UnsignedPred, m_Specific(ZeroCmpOp), m_Value(A))) &&
1009  match(ZeroCmpOp, m_c_Add(m_Specific(A), m_Value(B))) &&
1010  (ZeroICmp->hasOneUse() || UnsignedICmp->hasOneUse())) {
1011  auto GetKnownNonZeroAndOther = [&](Value *&NonZero, Value *&Other) {
1012  if (!IsKnownNonZero(NonZero))
1013  std::swap(NonZero, Other);
1014  return IsKnownNonZero(NonZero);
1015  };
1016 
1017  // Given ZeroCmpOp = (A + B)
1018  // ZeroCmpOp <= A && ZeroCmpOp != 0 --> (0-B) < A
1019  // ZeroCmpOp > A || ZeroCmpOp == 0 --> (0-B) >= A
1020  //
1021  // ZeroCmpOp < A && ZeroCmpOp != 0 --> (0-X) < Y iff
1022  // ZeroCmpOp >= A || ZeroCmpOp == 0 --> (0-X) >= Y iff
1023  // with X being the value (A/B) that is known to be non-zero,
1024  // and Y being remaining value.
1025  if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
1026  IsAnd)
1027  return Builder.CreateICmpULT(Builder.CreateNeg(B), A);
1028  if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE &&
1029  IsAnd && GetKnownNonZeroAndOther(B, A))
1030  return Builder.CreateICmpULT(Builder.CreateNeg(B), A);
1031  if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
1032  !IsAnd)
1033  return Builder.CreateICmpUGE(Builder.CreateNeg(B), A);
1034  if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_EQ &&
1035  !IsAnd && GetKnownNonZeroAndOther(B, A))
1036  return Builder.CreateICmpUGE(Builder.CreateNeg(B), A);
1037  }
1038 
1039  Value *Base, *Offset;
1040  if (!match(ZeroCmpOp, m_Sub(m_Value(Base), m_Value(Offset))))
1041  return nullptr;
1042 
1043  if (!match(UnsignedICmp,
1044  m_c_ICmp(UnsignedPred, m_Specific(Base), m_Specific(Offset))) ||
1045  !ICmpInst::isUnsigned(UnsignedPred))
1046  return nullptr;
1047 
1048  // Base >=/> Offset && (Base - Offset) != 0 <--> Base > Offset
1049  // (no overflow and not null)
1050  if ((UnsignedPred == ICmpInst::ICMP_UGE ||
1051  UnsignedPred == ICmpInst::ICMP_UGT) &&
1052  EqPred == ICmpInst::ICMP_NE && IsAnd)
1053  return Builder.CreateICmpUGT(Base, Offset);
1054 
1055  // Base <=/< Offset || (Base - Offset) == 0 <--> Base <= Offset
1056  // (overflow or null)
1057  if ((UnsignedPred == ICmpInst::ICMP_ULE ||
1058  UnsignedPred == ICmpInst::ICMP_ULT) &&
1059  EqPred == ICmpInst::ICMP_EQ && !IsAnd)
1060  return Builder.CreateICmpULE(Base, Offset);
1061 
1062  // Base <= Offset && (Base - Offset) != 0 --> Base < Offset
1063  if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
1064  IsAnd)
1065  return Builder.CreateICmpULT(Base, Offset);
1066 
1067  // Base > Offset || (Base - Offset) == 0 --> Base >= Offset
1068  if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
1069  !IsAnd)
1070  return Builder.CreateICmpUGE(Base, Offset);
1071 
1072  return nullptr;
1073 }
1074 
1075 struct IntPart {
1077  unsigned StartBit;
1078  unsigned NumBits;
1079 };
1080 
1081 /// Match an extraction of bits from an integer.
1083  Value *X;
1084  if (!match(V, m_OneUse(m_Trunc(m_Value(X)))))
1085  return None;
1086 
1087  unsigned NumOriginalBits = X->getType()->getScalarSizeInBits();
1088  unsigned NumExtractedBits = V->getType()->getScalarSizeInBits();
1089  Value *Y;
1090  const APInt *Shift;
1091  // For a trunc(lshr Y, Shift) pattern, make sure we're only extracting bits
1092  // from Y, not any shifted-in zeroes.
1093  if (match(X, m_OneUse(m_LShr(m_Value(Y), m_APInt(Shift)))) &&
1094  Shift->ule(NumOriginalBits - NumExtractedBits))
1095  return {{Y, (unsigned)Shift->getZExtValue(), NumExtractedBits}};
1096  return {{X, 0, NumExtractedBits}};
1097 }
1098 
1099 /// Materialize an extraction of bits from an integer in IR.
1101  Value *V = P.From;
1102  if (P.StartBit)
1103  V = Builder.CreateLShr(V, P.StartBit);
1104  Type *TruncTy = V->getType()->getWithNewBitWidth(P.NumBits);
1105  if (TruncTy != V->getType())
1106  V = Builder.CreateTrunc(V, TruncTy);
1107  return V;
1108 }
1109 
1110 /// (icmp eq X0, Y0) & (icmp eq X1, Y1) -> icmp eq X01, Y01
1111 /// (icmp ne X0, Y0) | (icmp ne X1, Y1) -> icmp ne X01, Y01
1112 /// where X0, X1 and Y0, Y1 are adjacent parts extracted from an integer.
1113 Value *InstCombinerImpl::foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1,
1114  bool IsAnd) {
1115  if (!Cmp0->hasOneUse() || !Cmp1->hasOneUse())
1116  return nullptr;
1117 
1119  if (Cmp0->getPredicate() != Pred || Cmp1->getPredicate() != Pred)
1120  return nullptr;
1121 
1122  Optional<IntPart> L0 = matchIntPart(Cmp0->getOperand(0));
1123  Optional<IntPart> R0 = matchIntPart(Cmp0->getOperand(1));
1124  Optional<IntPart> L1 = matchIntPart(Cmp1->getOperand(0));
1125  Optional<IntPart> R1 = matchIntPart(Cmp1->getOperand(1));
1126  if (!L0 || !R0 || !L1 || !R1)
1127  return nullptr;
1128 
1129  // Make sure the LHS/RHS compare a part of the same value, possibly after
1130  // an operand swap.
1131  if (L0->From != L1->From || R0->From != R1->From) {
1132  if (L0->From != R1->From || R0->From != L1->From)
1133  return nullptr;
1134  std::swap(L1, R1);
1135  }
1136 
1137  // Make sure the extracted parts are adjacent, canonicalizing to L0/R0 being
1138  // the low part and L1/R1 being the high part.
1139  if (L0->StartBit + L0->NumBits != L1->StartBit ||
1140  R0->StartBit + R0->NumBits != R1->StartBit) {
1141  if (L1->StartBit + L1->NumBits != L0->StartBit ||
1142  R1->StartBit + R1->NumBits != R0->StartBit)
1143  return nullptr;
1144  std::swap(L0, L1);
1145  std::swap(R0, R1);
1146  }
1147 
1148  // We can simplify to a comparison of these larger parts of the integers.
1149  IntPart L = {L0->From, L0->StartBit, L0->NumBits + L1->NumBits};
1150  IntPart R = {R0->From, R0->StartBit, R0->NumBits + R1->NumBits};
1153  return Builder.CreateICmp(Pred, LValue, RValue);
1154 }
1155 
1156 /// Reduce logic-of-compares with equality to a constant by substituting a
1157 /// common operand with the constant. Callers are expected to call this with
1158 /// Cmp0/Cmp1 switched to handle logic op commutativity.
1160  BinaryOperator &Logic,
1162  const SimplifyQuery &Q) {
1163  bool IsAnd = Logic.getOpcode() == Instruction::And;
1164  assert((IsAnd || Logic.getOpcode() == Instruction::Or) && "Wrong logic op");
1165 
1166  // Match an equality compare with a non-poison constant as Cmp0.
1167  // Also, give up if the compare can be constant-folded to avoid looping.
1168  ICmpInst::Predicate Pred0;
1169  Value *X;
1170  Constant *C;
1171  if (!match(Cmp0, m_ICmp(Pred0, m_Value(X), m_Constant(C))) ||
1172  !isGuaranteedNotToBeUndefOrPoison(C) || isa<Constant>(X))
1173  return nullptr;
1174  if ((IsAnd && Pred0 != ICmpInst::ICMP_EQ) ||
1175  (!IsAnd && Pred0 != ICmpInst::ICMP_NE))
1176  return nullptr;
1177 
1178  // The other compare must include a common operand (X). Canonicalize the
1179  // common operand as operand 1 (Pred1 is swapped if the common operand was
1180  // operand 0).
1181  Value *Y;
1182  ICmpInst::Predicate Pred1;
1183  if (!match(Cmp1, m_c_ICmp(Pred1, m_Value(Y), m_Deferred(X))))
1184  return nullptr;
1185 
1186  // Replace variable with constant value equivalence to remove a variable use:
1187  // (X == C) && (Y Pred1 X) --> (X == C) && (Y Pred1 C)
1188  // (X != C) || (Y Pred1 X) --> (X != C) || (Y Pred1 C)
1189  // Can think of the 'or' substitution with the 'and' bool equivalent:
1190  // A || B --> A || (!A && B)
1191  Value *SubstituteCmp = SimplifyICmpInst(Pred1, Y, C, Q);
1192  if (!SubstituteCmp) {
1193  // If we need to create a new instruction, require that the old compare can
1194  // be removed.
1195  if (!Cmp1->hasOneUse())
1196  return nullptr;
1197  SubstituteCmp = Builder.CreateICmp(Pred1, Y, C);
1198  }
1199  return Builder.CreateBinOp(Logic.getOpcode(), Cmp0, SubstituteCmp);
1200 }
1201 
1202 /// Fold (icmp)&(icmp) if possible.
1203 Value *InstCombinerImpl::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1204  BinaryOperator &And) {
1205  const SimplifyQuery Q = SQ.getWithInstruction(&And);
1206 
1207  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
1208  // if K1 and K2 are a one-bit mask.
1209  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, &And,
1210  /* IsAnd */ true))
1211  return V;
1212 
1213  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1214 
1215  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
1216  if (predicatesFoldable(PredL, PredR)) {
1217  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1218  LHS->getOperand(1) == RHS->getOperand(0))
1219  LHS->swapOperands();
1220  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1221  LHS->getOperand(1) == RHS->getOperand(1)) {
1222  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1223  unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
1224  bool IsSigned = LHS->isSigned() || RHS->isSigned();
1225  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
1226  }
1227  }
1228 
1229  // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
1230  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
1231  return V;
1232 
1233  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, And, Builder, Q))
1234  return V;
1235  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, And, Builder, Q))
1236  return V;
1237 
1238  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
1239  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
1240  return V;
1241 
1242  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
1243  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
1244  return V;
1245 
1246  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
1247  return V;
1248 
1249  if (Value *V = foldSignedTruncationCheck(LHS, RHS, And, Builder))
1250  return V;
1251 
1252  if (Value *V = foldIsPowerOf2(LHS, RHS, true /* JoinedByAnd */, Builder))
1253  return V;
1254 
1255  if (Value *X =
1256  foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/true, Q, Builder))
1257  return X;
1258  if (Value *X =
1259  foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/true, Q, Builder))
1260  return X;
1261 
1262  if (Value *X = foldEqOfParts(LHS, RHS, /*IsAnd=*/true))
1263  return X;
1264 
1265  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
1266  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1267 
1268  ConstantInt *LHSC, *RHSC;
1269  if (!match(LHS->getOperand(1), m_ConstantInt(LHSC)) ||
1270  !match(RHS->getOperand(1), m_ConstantInt(RHSC)))
1271  return nullptr;
1272 
1273  if (LHSC == RHSC && PredL == PredR) {
1274  // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
1275  // where C is a power of 2 or
1276  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
1277  if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
1278  (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
1279  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
1280  return Builder.CreateICmp(PredL, NewOr, LHSC);
1281  }
1282  }
1283 
1284  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
1285  // where CMAX is the all ones value for the truncated type,
1286  // iff the lower bits of C2 and CA are zero.
1287  if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
1288  RHS->hasOneUse()) {
1289  Value *V;
1290  ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
1291 
1292  // (trunc x) == C1 & (and x, CA) == C2
1293  // (and x, CA) == C2 & (trunc x) == C1
1294  if (match(RHS0, m_Trunc(m_Value(V))) &&
1295  match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1296  SmallC = RHSC;
1297  BigC = LHSC;
1298  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
1299  match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
1300  SmallC = LHSC;
1301  BigC = RHSC;
1302  }
1303 
1304  if (SmallC && BigC) {
1305  unsigned BigBitSize = BigC->getType()->getBitWidth();
1306  unsigned SmallBitSize = SmallC->getType()->getBitWidth();
1307 
1308  // Check that the low bits are zero.
1309  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
1310  if ((Low & AndC->getValue()).isZero() &&
1311  (Low & BigC->getValue()).isZero()) {
1312  Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue());
1313  APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
1314  Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
1315  return Builder.CreateICmp(PredL, NewAnd, NewVal);
1316  }
1317  }
1318  }
1319 
1320  // From here on, we only handle:
1321  // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
1322  if (LHS0 != RHS0)
1323  return nullptr;
1324 
1325  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1326  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1327  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1328  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1329  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1330  return nullptr;
1331 
1332  // We can't fold (ugt x, C) & (sgt x, C2).
1333  if (!predicatesFoldable(PredL, PredR))
1334  return nullptr;
1335 
1336  // Ensure that the larger constant is on the RHS.
1337  bool ShouldSwap;
1338  if (CmpInst::isSigned(PredL) ||
1339  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1340  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1341  else
1342  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1343 
1344  if (ShouldSwap) {
1345  std::swap(LHS, RHS);
1346  std::swap(LHSC, RHSC);
1347  std::swap(PredL, PredR);
1348  }
1349 
1350  // At this point, we know we have two icmp instructions
1351  // comparing a value against two constants and and'ing the result
1352  // together. Because of the above check, we know that we only have
1353  // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
1354  // (from the icmp folding check above), that the two constants
1355  // are not equal and that the larger constant is on the RHS
1356  assert(LHSC != RHSC && "Compares not folded above?");
1357 
1358  switch (PredL) {
1359  default:
1360  llvm_unreachable("Unknown integer condition code!");
1361  case ICmpInst::ICMP_NE:
1362  switch (PredR) {
1363  default:
1364  llvm_unreachable("Unknown integer condition code!");
1365  case ICmpInst::ICMP_ULT:
1366  // (X != 13 & X u< 14) -> X < 13
1367  if (LHSC->getValue() == (RHSC->getValue() - 1))
1368  return Builder.CreateICmpULT(LHS0, LHSC);
1369  if (LHSC->isZero()) // (X != 0 & X u< C) -> X-1 u< C-1
1370  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1371  false, true);
1372  break; // (X != 13 & X u< 15) -> no change
1373  case ICmpInst::ICMP_SLT:
1374  // (X != 13 & X s< 14) -> X < 13
1375  if (LHSC->getValue() == (RHSC->getValue() - 1))
1376  return Builder.CreateICmpSLT(LHS0, LHSC);
1377  // (X != INT_MIN & X s< C) -> X-(INT_MIN+1) u< (C-(INT_MIN+1))
1378  if (LHSC->isMinValue(true))
1379  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1380  true, true);
1381  break; // (X != 13 & X s< 15) -> no change
1382  case ICmpInst::ICMP_NE:
1383  // Potential folds for this case should already be handled.
1384  break;
1385  }
1386  break;
1387  case ICmpInst::ICMP_UGT:
1388  switch (PredR) {
1389  default:
1390  llvm_unreachable("Unknown integer condition code!");
1391  case ICmpInst::ICMP_NE:
1392  // (X u> 13 & X != 14) -> X u> 14
1393  if (RHSC->getValue() == (LHSC->getValue() + 1))
1394  return Builder.CreateICmp(PredL, LHS0, RHSC);
1395  // X u> C & X != UINT_MAX -> (X-(C+1)) u< UINT_MAX-(C+1)
1396  if (RHSC->isMaxValue(false))
1397  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1398  false, true);
1399  break; // (X u> 13 & X != 15) -> no change
1400  case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) u< 1
1401  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1402  false, true);
1403  }
1404  break;
1405  case ICmpInst::ICMP_SGT:
1406  switch (PredR) {
1407  default:
1408  llvm_unreachable("Unknown integer condition code!");
1409  case ICmpInst::ICMP_NE:
1410  // (X s> 13 & X != 14) -> X s> 14
1411  if (RHSC->getValue() == (LHSC->getValue() + 1))
1412  return Builder.CreateICmp(PredL, LHS0, RHSC);
1413  // X s> C & X != INT_MAX -> (X-(C+1)) u< INT_MAX-(C+1)
1414  if (RHSC->isMaxValue(true))
1415  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
1416  true, true);
1417  break; // (X s> 13 & X != 15) -> no change
1418  case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) u< 1
1419  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
1420  true);
1421  }
1422  break;
1423  }
1424 
1425  return nullptr;
1426 }
1427 
1428 Value *InstCombinerImpl::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS,
1429  bool IsAnd) {
1430  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1431  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1432  FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1433 
1434  if (LHS0 == RHS1 && RHS0 == LHS1) {
1435  // Swap RHS operands to match LHS.
1436  PredR = FCmpInst::getSwappedPredicate(PredR);
1437  std::swap(RHS0, RHS1);
1438  }
1439 
1440  // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1441  // Suppose the relation between x and y is R, where R is one of
1442  // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1443  // testing the desired relations.
1444  //
1445  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1446  // bool(R & CC0) && bool(R & CC1)
1447  // = bool((R & CC0) & (R & CC1))
1448  // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1449  //
1450  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1451  // bool(R & CC0) || bool(R & CC1)
1452  // = bool((R & CC0) | (R & CC1))
1453  // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1454  if (LHS0 == RHS0 && LHS1 == RHS1) {
1455  unsigned FCmpCodeL = getFCmpCode(PredL);
1456  unsigned FCmpCodeR = getFCmpCode(PredR);
1457  unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1458  return getFCmpValue(NewPred, LHS0, LHS1, Builder);
1459  }
1460 
1461  if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1462  (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) {
1463  if (LHS0->getType() != RHS0->getType())
1464  return nullptr;
1465 
1466  // FCmp canonicalization ensures that (fcmp ord/uno X, X) and
1467  // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0).
1468  if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP()))
1469  // Ignore the constants because they are obviously not NANs:
1470  // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y)
1471  // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y)
1472  return Builder.CreateFCmp(PredL, LHS0, RHS0);
1473  }
1474 
1475  return nullptr;
1476 }
1477 
1478 /// This a limited reassociation for a special case (see above) where we are
1479 /// checking if two values are either both NAN (unordered) or not-NAN (ordered).
1480 /// This could be handled more generally in '-reassociation', but it seems like
1481 /// an unlikely pattern for a large number of logic ops and fcmps.
1484  Instruction::BinaryOps Opcode = BO.getOpcode();
1485  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1486  "Expecting and/or op for fcmp transform");
1487 
1488  // There are 4 commuted variants of the pattern. Canonicalize operands of this
1489  // logic op so an fcmp is operand 0 and a matching logic op is operand 1.
1490  Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1), *X;
1491  FCmpInst::Predicate Pred;
1492  if (match(Op1, m_FCmp(Pred, m_Value(), m_AnyZeroFP())))
1493  std::swap(Op0, Op1);
1494 
1495  // Match inner binop and the predicate for combining 2 NAN checks into 1.
1496  BinaryOperator *BO1;
1497  FCmpInst::Predicate NanPred = Opcode == Instruction::And ? FCmpInst::FCMP_ORD
1499  if (!match(Op0, m_FCmp(Pred, m_Value(X), m_AnyZeroFP())) || Pred != NanPred ||
1500  !match(Op1, m_BinOp(BO1)) || BO1->getOpcode() != Opcode)
1501  return nullptr;
1502 
1503  // The inner logic op must have a matching fcmp operand.
1504  Value *BO10 = BO1->getOperand(0), *BO11 = BO1->getOperand(1), *Y;
1505  if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1506  Pred != NanPred || X->getType() != Y->getType())
1507  std::swap(BO10, BO11);
1508 
1509  if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1510  Pred != NanPred || X->getType() != Y->getType())
1511  return nullptr;
1512 
1513  // and (fcmp ord X, 0), (and (fcmp ord Y, 0), Z) --> and (fcmp ord X, Y), Z
1514  // or (fcmp uno X, 0), (or (fcmp uno Y, 0), Z) --> or (fcmp uno X, Y), Z
1515  Value *NewFCmp = Builder.CreateFCmp(Pred, X, Y);
1516  if (auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) {
1517  // Intersect FMF from the 2 source fcmps.
1518  NewFCmpInst->copyIRFlags(Op0);
1519  NewFCmpInst->andIRFlags(BO10);
1520  }
1521  return BinaryOperator::Create(Opcode, NewFCmp, BO11);
1522 }
1523 
1524 /// Match De Morgan's Laws:
1525 /// (~A & ~B) == (~(A | B))
1526 /// (~A | ~B) == (~(A & B))
1529  auto Opcode = I.getOpcode();
1530  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1531  "Trying to match De Morgan's Laws with something other than and/or");
1532 
1533  // Flip the logic operation.
1534  Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1535 
1536  Value *A, *B;
1537  if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) &&
1538  match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) &&
1539  !InstCombiner::isFreeToInvert(A, A->hasOneUse()) &&
1540  !InstCombiner::isFreeToInvert(B, B->hasOneUse())) {
1541  Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan");
1542  return BinaryOperator::CreateNot(AndOr);
1543  }
1544 
1545  return nullptr;
1546 }
1547 
1548 bool InstCombinerImpl::shouldOptimizeCast(CastInst *CI) {
1549  Value *CastSrc = CI->getOperand(0);
1550 
1551  // Noop casts and casts of constants should be eliminated trivially.
1552  if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1553  return false;
1554 
1555  // If this cast is paired with another cast that can be eliminated, we prefer
1556  // to have it eliminated.
1557  if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1558  if (isEliminableCastPair(PrecedingCI, CI))
1559  return false;
1560 
1561  return true;
1562 }
1563 
1564 /// Fold {and,or,xor} (cast X), C.
1567  Constant *C = dyn_cast<Constant>(Logic.getOperand(1));
1568  if (!C)
1569  return nullptr;
1570 
1571  auto LogicOpc = Logic.getOpcode();
1572  Type *DestTy = Logic.getType();
1573  Type *SrcTy = Cast->getSrcTy();
1574 
1575  // Move the logic operation ahead of a zext or sext if the constant is
1576  // unchanged in the smaller source type. Performing the logic in a smaller
1577  // type may provide more information to later folds, and the smaller logic
1578  // instruction may be cheaper (particularly in the case of vectors).
1579  Value *X;
1580  if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1581  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1582  Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1583  if (ZextTruncC == C) {
1584  // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1585  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1586  return new ZExtInst(NewOp, DestTy);
1587  }
1588  }
1589 
1590  if (match(Cast, m_OneUse(m_SExt(m_Value(X))))) {
1591  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1592  Constant *SextTruncC = ConstantExpr::getSExt(TruncC, DestTy);
1593  if (SextTruncC == C) {
1594  // LogicOpc (sext X), C --> sext (LogicOpc X, C)
1595  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1596  return new SExtInst(NewOp, DestTy);
1597  }
1598  }
1599 
1600  return nullptr;
1601 }
1602 
1603 /// Fold {and,or,xor} (cast X), Y.
1604 Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) {
1605  auto LogicOpc = I.getOpcode();
1606  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1607 
1608  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1609  CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1610  if (!Cast0)
1611  return nullptr;
1612 
1613  // This must be a cast from an integer or integer vector source type to allow
1614  // transformation of the logic operation to the source type.
1615  Type *DestTy = I.getType();
1616  Type *SrcTy = Cast0->getSrcTy();
1617  if (!SrcTy->isIntOrIntVectorTy())
1618  return nullptr;
1619 
1620  if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1621  return Ret;
1622 
1623  CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1624  if (!Cast1)
1625  return nullptr;
1626 
1627  // Both operands of the logic operation are casts. The casts must be of the
1628  // same type for reduction.
1629  auto CastOpcode = Cast0->getOpcode();
1630  if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
1631  return nullptr;
1632 
1633  Value *Cast0Src = Cast0->getOperand(0);
1634  Value *Cast1Src = Cast1->getOperand(0);
1635 
1636  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1637  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1638  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1639  I.getName());
1640  return CastInst::Create(CastOpcode, NewOp, DestTy);
1641  }
1642 
1643  // For now, only 'and'/'or' have optimizations after this.
1644  if (LogicOpc == Instruction::Xor)
1645  return nullptr;
1646 
1647  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1648  // cast is otherwise not optimizable. This happens for vector sexts.
1649  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1650  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1651  if (ICmp0 && ICmp1) {
1652  Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I)
1653  : foldOrOfICmps(ICmp0, ICmp1, I);
1654  if (Res)
1655  return CastInst::Create(CastOpcode, Res, DestTy);
1656  return nullptr;
1657  }
1658 
1659  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1660  // cast is otherwise not optimizable. This happens for vector sexts.
1661  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1662  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1663  if (FCmp0 && FCmp1)
1664  if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1665  return CastInst::Create(CastOpcode, R, DestTy);
1666 
1667  return nullptr;
1668 }
1669 
1672  assert(I.getOpcode() == Instruction::And);
1673  Value *Op0 = I.getOperand(0);
1674  Value *Op1 = I.getOperand(1);
1675  Value *A, *B;
1676 
1677  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1678  // (A | B) & ~(A & B) --> A ^ B
1679  // (A | B) & ~(B & A) --> A ^ B
1680  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1681  m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
1682  return BinaryOperator::CreateXor(A, B);
1683 
1684  // (A | ~B) & (~A | B) --> ~(A ^ B)
1685  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1686  // (~B | A) & (~A | B) --> ~(A ^ B)
1687  // (~B | A) & (B | ~A) --> ~(A ^ B)
1688  if (Op0->hasOneUse() || Op1->hasOneUse())
1689  if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
1690  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
1691  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1692 
1693  return nullptr;
1694 }
1695 
1698  assert(I.getOpcode() == Instruction::Or);
1699  Value *Op0 = I.getOperand(0);
1700  Value *Op1 = I.getOperand(1);
1701  Value *A, *B;
1702 
1703  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1704  // (A & B) | ~(A | B) --> ~(A ^ B)
1705  // (A & B) | ~(B | A) --> ~(A ^ B)
1706  if (Op0->hasOneUse() || Op1->hasOneUse())
1707  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1708  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1709  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1710 
1711  // Operand complexity canonicalization guarantees that the 'xor' is Op0.
1712  // (A ^ B) | ~(A | B) --> ~(A & B)
1713  // (A ^ B) | ~(B | A) --> ~(A & B)
1714  if (Op0->hasOneUse() || Op1->hasOneUse())
1715  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1716  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1717  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
1718 
1719  // (A & ~B) | (~A & B) --> A ^ B
1720  // (A & ~B) | (B & ~A) --> A ^ B
1721  // (~B & A) | (~A & B) --> A ^ B
1722  // (~B & A) | (B & ~A) --> A ^ B
1723  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1724  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1725  return BinaryOperator::CreateXor(A, B);
1726 
1727  return nullptr;
1728 }
1729 
1730 /// Return true if a constant shift amount is always less than the specified
1731 /// bit-width. If not, the shift could create poison in the narrower type.
1732 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1733  APInt Threshold(C->getType()->getScalarSizeInBits(), BitWidth);
1735 }
1736 
1737 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1738 /// a common zext operand: and (binop (zext X), C), (zext X).
1739 Instruction *InstCombinerImpl::narrowMaskedBinOp(BinaryOperator &And) {
1740  // This transform could also apply to {or, and, xor}, but there are better
1741  // folds for those cases, so we don't expect those patterns here. AShr is not
1742  // handled because it should always be transformed to LShr in this sequence.
1743  // The subtract transform is different because it has a constant on the left.
1744  // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1745  Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1746  Constant *C;
1747  if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1748  !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1749  !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1750  !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1751  !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1752  return nullptr;
1753 
1754  Value *X;
1755  if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1756  return nullptr;
1757 
1758  Type *Ty = And.getType();
1759  if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1760  return nullptr;
1761 
1762  // If we're narrowing a shift, the shift amount must be safe (less than the
1763  // width) in the narrower type. If the shift amount is greater, instsimplify
1764  // usually handles that case, but we can't guarantee/assert it.
1765  Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1766  if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1767  if (!canNarrowShiftAmt(C, X->getType()->getScalarSizeInBits()))
1768  return nullptr;
1769 
1770  // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1771  // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1772  Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1773  Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1774  : Builder.CreateBinOp(Opc, X, NewC);
1775  return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1776 }
1777 
1778 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1779 // here. We should standardize that construct where it is needed or choose some
1780 // other way to ensure that commutated variants of patterns are not missed.
1782  Type *Ty = I.getType();
1783 
1784  if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1),
1785  SQ.getWithInstruction(&I)))
1786  return replaceInstUsesWith(I, V);
1787 
1788  if (SimplifyAssociativeOrCommutative(I))
1789  return &I;
1790 
1791  if (Instruction *X = foldVectorBinop(I))
1792  return X;
1793 
1794  // See if we can simplify any instructions used by the instruction whose sole
1795  // purpose is to compute bits we don't care about.
1796  if (SimplifyDemandedInstructionBits(I))
1797  return &I;
1798 
1799  // Do this before using distributive laws to catch simple and/or/not patterns.
1801  return Xor;
1802 
1803  // (A|B)&(A|C) -> A|(B&C) etc
1804  if (Value *V = SimplifyUsingDistributiveLaws(I))
1805  return replaceInstUsesWith(I, V);
1806 
1807  if (Value *V = SimplifyBSwap(I, Builder))
1808  return replaceInstUsesWith(I, V);
1809 
1810  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1811 
1812  Value *X, *Y;
1813  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
1814  match(Op1, m_One())) {
1815  // (1 << X) & 1 --> zext(X == 0)
1816  // (1 >> X) & 1 --> zext(X == 0)
1817  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, 0));
1818  return new ZExtInst(IsZero, Ty);
1819  }
1820 
1821  const APInt *C;
1822  if (match(Op1, m_APInt(C))) {
1823  const APInt *XorC;
1824  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
1825  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1826  Constant *NewC = ConstantInt::get(Ty, *C & *XorC);
1827  Value *And = Builder.CreateAnd(X, Op1);
1828  And->takeName(Op0);
1829  return BinaryOperator::CreateXor(And, NewC);
1830  }
1831 
1832  const APInt *OrC;
1833  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
1834  // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
1835  // NOTE: This reduces the number of bits set in the & mask, which
1836  // can expose opportunities for store narrowing for scalars.
1837  // NOTE: SimplifyDemandedBits should have already removed bits from C1
1838  // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
1839  // above, but this feels safer.
1840  APInt Together = *C & *OrC;
1841  Value *And = Builder.CreateAnd(X, ConstantInt::get(Ty, Together ^ *C));
1842  And->takeName(Op0);
1843  return BinaryOperator::CreateOr(And, ConstantInt::get(Ty, Together));
1844  }
1845 
1846  // If the mask is only needed on one incoming arm, push the 'and' op up.
1847  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
1848  match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
1849  APInt NotAndMask(~(*C));
1850  BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
1851  if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
1852  // Not masking anything out for the LHS, move mask to RHS.
1853  // and ({x}or X, Y), C --> {x}or X, (and Y, C)
1854  Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
1855  return BinaryOperator::Create(BinOp, X, NewRHS);
1856  }
1857  if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
1858  // Not masking anything out for the RHS, move mask to LHS.
1859  // and ({x}or X, Y), C --> {x}or (and X, C), Y
1860  Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
1861  return BinaryOperator::Create(BinOp, NewLHS, Y);
1862  }
1863  }
1864 
1865  unsigned Width = Ty->getScalarSizeInBits();
1866  const APInt *ShiftC;
1867  if (match(Op0, m_OneUse(m_SExt(m_AShr(m_Value(X), m_APInt(ShiftC)))))) {
1868  if (*C == APInt::getLowBitsSet(Width, Width - ShiftC->getZExtValue())) {
1869  // We are clearing high bits that were potentially set by sext+ashr:
1870  // and (sext (ashr X, ShiftC)), C --> lshr (sext X), ShiftC
1871  Value *Sext = Builder.CreateSExt(X, Ty);
1872  Constant *ShAmtC = ConstantInt::get(Ty, ShiftC->zext(Width));
1873  return BinaryOperator::CreateLShr(Sext, ShAmtC);
1874  }
1875  }
1876 
1877  const APInt *AddC;
1878  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC)))) {
1879  // If we add zeros to every bit below a mask, the add has no effect:
1880  // (X + AddC) & LowMaskC --> X & LowMaskC
1881  unsigned Ctlz = C->countLeadingZeros();
1882  APInt LowMask(APInt::getLowBitsSet(Width, Width - Ctlz));
1883  if ((*AddC & LowMask).isZero())
1884  return BinaryOperator::CreateAnd(X, Op1);
1885 
1886  // If we are masking the result of the add down to exactly one bit and
1887  // the constant we are adding has no bits set below that bit, then the
1888  // add is flipping a single bit. Example:
1889  // (X + 4) & 4 --> (X & 4) ^ 4
1890  if (Op0->hasOneUse() && C->isPowerOf2() && (*AddC & (*C - 1)) == 0) {
1891  assert((*C & *AddC) != 0 && "Expected common bit");
1892  Value *NewAnd = Builder.CreateAnd(X, Op1);
1893  return BinaryOperator::CreateXor(NewAnd, Op1);
1894  }
1895  }
1896 
1897  // ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if C2 fits in the
1898  // bitwidth of X and OP behaves well when given trunc(C1) and X.
1899  auto isSuitableBinOpcode = [](BinaryOperator *B) {
1900  switch (B->getOpcode()) {
1901  case Instruction::Xor:
1902  case Instruction::Or:
1903  case Instruction::Mul:
1904  case Instruction::Add:
1905  case Instruction::Sub:
1906  return true;
1907  default:
1908  return false;
1909  }
1910  };
1911  BinaryOperator *BO;
1912  if (match(Op0, m_OneUse(m_BinOp(BO))) && isSuitableBinOpcode(BO)) {
1913  Value *X;
1914  const APInt *C1;
1915  // TODO: The one-use restrictions could be relaxed a little if the AND
1916  // is going to be removed.
1917  if (match(BO, m_c_BinOp(m_OneUse(m_ZExt(m_Value(X))), m_APInt(C1))) &&
1918  C->isIntN(X->getType()->getScalarSizeInBits())) {
1919  unsigned XWidth = X->getType()->getScalarSizeInBits();
1920  Constant *TruncC1 = ConstantInt::get(X->getType(), C1->trunc(XWidth));
1921  Value *BinOp = isa<ZExtInst>(BO->getOperand(0))
1922  ? Builder.CreateBinOp(BO->getOpcode(), X, TruncC1)
1923  : Builder.CreateBinOp(BO->getOpcode(), TruncC1, X);
1924  Constant *TruncC = ConstantInt::get(X->getType(), C->trunc(XWidth));
1925  Value *And = Builder.CreateAnd(BinOp, TruncC);
1926  return new ZExtInst(And, Ty);
1927  }
1928  }
1929  }
1930 
1932  m_SignMask())) &&
1934  ICmpInst::Predicate::ICMP_EQ,
1935  APInt(Ty->getScalarSizeInBits(),
1936  Ty->getScalarSizeInBits() -
1937  X->getType()->getScalarSizeInBits())))) {
1938  auto *SExt = Builder.CreateSExt(X, Ty, X->getName() + ".signext");
1939  auto *SanitizedSignMask = cast<Constant>(Op1);
1940  // We must be careful with the undef elements of the sign bit mask, however:
1941  // the mask elt can be undef iff the shift amount for that lane was undef,
1942  // otherwise we need to sanitize undef masks to zero.
1943  SanitizedSignMask = Constant::replaceUndefsWith(
1944  SanitizedSignMask, ConstantInt::getNullValue(Ty->getScalarType()));
1945  SanitizedSignMask =
1946  Constant::mergeUndefsWith(SanitizedSignMask, cast<Constant>(Y));
1947  return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
1948  }
1949 
1950  if (Instruction *Z = narrowMaskedBinOp(I))
1951  return Z;
1952 
1953  if (I.getType()->isIntOrIntVectorTy(1)) {
1954  if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
1955  if (auto *I =
1956  foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ true))
1957  return I;
1958  }
1959  if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
1960  if (auto *I =
1961  foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ true))
1962  return I;
1963  }
1964  }
1965 
1966  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
1967  return FoldedLogic;
1968 
1969  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1970  return DeMorgan;
1971 
1972  {
1973  Value *A, *B, *C;
1974  // A & (A ^ B) --> A & ~B
1975  if (match(Op1, m_OneUse(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1976  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(B));
1977  // (A ^ B) & A --> A & ~B
1978  if (match(Op0, m_OneUse(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1979  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(B));
1980 
1981  // A & ~(A ^ B) --> A & B
1982  if (match(Op1, m_Not(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1983  return BinaryOperator::CreateAnd(Op0, B);
1984  // ~(A ^ B) & A --> A & B
1985  if (match(Op0, m_Not(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1986  return BinaryOperator::CreateAnd(Op1, B);
1987 
1988  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1989  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1990  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1991  if (Op1->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1992  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1993 
1994  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1995  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1996  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1997  if (Op0->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1998  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1999 
2000  // (A | B) & ((~A) ^ B) -> (A & B)
2001  // (A | B) & (B ^ (~A)) -> (A & B)
2002  // (B | A) & ((~A) ^ B) -> (A & B)
2003  // (B | A) & (B ^ (~A)) -> (A & B)
2004  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2005  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2006  return BinaryOperator::CreateAnd(A, B);
2007 
2008  // ((~A) ^ B) & (A | B) -> (A & B)
2009  // ((~A) ^ B) & (B | A) -> (A & B)
2010  // (B ^ (~A)) & (A | B) -> (A & B)
2011  // (B ^ (~A)) & (B | A) -> (A & B)
2012  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2013  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
2014  return BinaryOperator::CreateAnd(A, B);
2015 
2016  // (A & ~B) & ~C -> A & ~(B | C)
2017  // (~B & A) & ~C -> A & ~(B | C)
2018  if (match(Op0, m_OneUse(m_c_And(m_Value(A), m_Not(m_Value(B))))) &&
2019  match(Op1, m_Not(m_Value(C))))
2020  return BinaryOperator::CreateAnd(
2021  A, Builder.CreateNot(Builder.CreateOr(B, C)));
2022  }
2023 
2024  {
2025  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2026  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2027  if (LHS && RHS)
2028  if (Value *Res = foldAndOfICmps(LHS, RHS, I))
2029  return replaceInstUsesWith(I, Res);
2030 
2031  // TODO: Make this recursive; it's a little tricky because an arbitrary
2032  // number of 'and' instructions might have to be created.
2033  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
2034  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2035  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
2036  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
2037  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2038  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
2039  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
2040  }
2041  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
2042  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2043  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
2044  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
2045  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2046  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
2047  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
2048  }
2049  }
2050 
2051  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2052  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2053  if (Value *Res = foldLogicOfFCmps(LHS, RHS, true))
2054  return replaceInstUsesWith(I, Res);
2055 
2056  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2057  return FoldedFCmps;
2058 
2059  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
2060  return CastedAnd;
2061 
2062  // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
2063  Value *A;
2064  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2065  A->getType()->isIntOrIntVectorTy(1))
2066  return SelectInst::Create(A, Op1, Constant::getNullValue(Ty));
2067  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2068  A->getType()->isIntOrIntVectorTy(1))
2069  return SelectInst::Create(A, Op0, Constant::getNullValue(Ty));
2070 
2071  // (iN X s>> (N-1)) & Y --> (X s< 0) ? Y : 0
2072  unsigned FullShift = Ty->getScalarSizeInBits() - 1;
2073  if (match(&I, m_c_And(m_OneUse(m_AShr(m_Value(X), m_SpecificInt(FullShift))),
2074  m_Value(Y)))) {
2075  Constant *Zero = ConstantInt::getNullValue(Ty);
2076  Value *Cmp = Builder.CreateICmpSLT(X, Zero, "isneg");
2077  return SelectInst::Create(Cmp, Y, Zero);
2078  }
2079 
2080  // (~x) & y --> ~(x | (~y)) iff that gets rid of inversions
2081  if (sinkNotIntoOtherHandOfAndOrOr(I))
2082  return &I;
2083 
2084  // An and recurrence w/loop invariant step is equivelent to (and start, step)
2085  PHINode *PN = nullptr;
2086  Value *Start = nullptr, *Step = nullptr;
2087  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2088  return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
2089 
2090  return nullptr;
2091 }
2092 
2094  bool MatchBSwaps,
2095  bool MatchBitReversals) {
2097  if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
2098  Insts))
2099  return nullptr;
2100  Instruction *LastInst = Insts.pop_back_val();
2101  LastInst->removeFromParent();
2102 
2103  for (auto *Inst : Insts)
2104  Worklist.push(Inst);
2105  return LastInst;
2106 }
2107 
2108 /// Match UB-safe variants of the funnel shift intrinsic.
2110  // TODO: Can we reduce the code duplication between this and the related
2111  // rotate matching code under visitSelect and visitTrunc?
2112  unsigned Width = Or.getType()->getScalarSizeInBits();
2113 
2114  // First, find an or'd pair of opposite shifts:
2115  // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
2116  BinaryOperator *Or0, *Or1;
2117  if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
2118  !match(Or.getOperand(1), m_BinOp(Or1)))
2119  return nullptr;
2120 
2121  Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2122  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
2123  !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
2124  Or0->getOpcode() == Or1->getOpcode())
2125  return nullptr;
2126 
2127  // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
2128  if (Or0->getOpcode() == BinaryOperator::LShr) {
2129  std::swap(Or0, Or1);
2130  std::swap(ShVal0, ShVal1);
2131  std::swap(ShAmt0, ShAmt1);
2132  }
2133  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2134  Or1->getOpcode() == BinaryOperator::LShr &&
2135  "Illegal or(shift,shift) pair");
2136 
2137  // Match the shift amount operands for a funnel shift pattern. This always
2138  // matches a subtraction on the R operand.
2139  auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
2140  // Check for constant shift amounts that sum to the bitwidth.
2141  const APInt *LI, *RI;
2142  if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
2143  if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
2144  return ConstantInt::get(L->getType(), *LI);
2145 
2146  Constant *LC, *RC;
2147  if (match(L, m_Constant(LC)) && match(R, m_Constant(RC)) &&
2151  return ConstantExpr::mergeUndefsWith(LC, RC);
2152 
2153  // (shl ShVal, X) | (lshr ShVal, (Width - x)) iff X < Width.
2154  // We limit this to X < Width in case the backend re-expands the intrinsic,
2155  // and has to reintroduce a shift modulo operation (InstCombine might remove
2156  // it after this fold). This still doesn't guarantee that the final codegen
2157  // will match this original pattern.
2158  if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) {
2159  KnownBits KnownL = IC.computeKnownBits(L, /*Depth*/ 0, &Or);
2160  return KnownL.getMaxValue().ult(Width) ? L : nullptr;
2161  }
2162 
2163  // For non-constant cases, the following patterns currently only work for
2164  // rotation patterns.
2165  // TODO: Add general funnel-shift compatible patterns.
2166  if (ShVal0 != ShVal1)
2167  return nullptr;
2168 
2169  // For non-constant cases we don't support non-pow2 shift masks.
2170  // TODO: Is it worth matching urem as well?
2171  if (!isPowerOf2_32(Width))
2172  return nullptr;
2173 
2174  // The shift amount may be masked with negation:
2175  // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
2176  Value *X;
2177  unsigned Mask = Width - 1;
2178  if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
2180  return X;
2181 
2182  // Similar to above, but the shift amount may be extended after masking,
2183  // so return the extended value as the parameter for the intrinsic.
2184  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2186  m_SpecificInt(Mask))))
2187  return L;
2188 
2189  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2191  return L;
2192 
2193  return nullptr;
2194  };
2195 
2196  Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);
2197  bool IsFshl = true; // Sub on LSHR.
2198  if (!ShAmt) {
2199  ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);
2200  IsFshl = false; // Sub on SHL.
2201  }
2202  if (!ShAmt)
2203  return nullptr;
2204 
2205  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2206  Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
2207  return CallInst::Create(F, {ShVal0, ShVal1, ShAmt});
2208 }
2209 
2210 /// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
2213  assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
2214  Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
2215  Type *Ty = Or.getType();
2216 
2217  unsigned Width = Ty->getScalarSizeInBits();
2218  if ((Width & 1) != 0)
2219  return nullptr;
2220  unsigned HalfWidth = Width / 2;
2221 
2222  // Canonicalize zext (lower half) to LHS.
2223  if (!isa<ZExtInst>(Op0))
2224  std::swap(Op0, Op1);
2225 
2226  // Find lower/upper half.
2227  Value *LowerSrc, *ShlVal, *UpperSrc;
2228  const APInt *C;
2229  if (!match(Op0, m_OneUse(m_ZExt(m_Value(LowerSrc)))) ||
2230  !match(Op1, m_OneUse(m_Shl(m_Value(ShlVal), m_APInt(C)))) ||
2231  !match(ShlVal, m_OneUse(m_ZExt(m_Value(UpperSrc)))))
2232  return nullptr;
2233  if (*C != HalfWidth || LowerSrc->getType() != UpperSrc->getType() ||
2234  LowerSrc->getType()->getScalarSizeInBits() != HalfWidth)
2235  return nullptr;
2236 
2237  auto ConcatIntrinsicCalls = [&](Intrinsic::ID id, Value *Lo, Value *Hi) {
2238  Value *NewLower = Builder.CreateZExt(Lo, Ty);
2239  Value *NewUpper = Builder.CreateZExt(Hi, Ty);
2240  NewUpper = Builder.CreateShl(NewUpper, HalfWidth);
2241  Value *BinOp = Builder.CreateOr(NewLower, NewUpper);
2242  Function *F = Intrinsic::getDeclaration(Or.getModule(), id, Ty);
2243  return Builder.CreateCall(F, BinOp);
2244  };
2245 
2246  // BSWAP: Push the concat down, swapping the lower/upper sources.
2247  // concat(bswap(x),bswap(y)) -> bswap(concat(x,y))
2248  Value *LowerBSwap, *UpperBSwap;
2249  if (match(LowerSrc, m_BSwap(m_Value(LowerBSwap))) &&
2250  match(UpperSrc, m_BSwap(m_Value(UpperBSwap))))
2251  return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2252 
2253  // BITREVERSE: Push the concat down, swapping the lower/upper sources.
2254  // concat(bitreverse(x),bitreverse(y)) -> bitreverse(concat(x,y))
2255  Value *LowerBRev, *UpperBRev;
2256  if (match(LowerSrc, m_BitReverse(m_Value(LowerBRev))) &&
2257  match(UpperSrc, m_BitReverse(m_Value(UpperBRev))))
2258  return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2259 
2260  return nullptr;
2261 }
2262 
2263 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
2265  unsigned NumElts = cast<FixedVectorType>(C1->getType())->getNumElements();
2266  for (unsigned i = 0; i != NumElts; ++i) {
2267  Constant *EltC1 = C1->getAggregateElement(i);
2268  Constant *EltC2 = C2->getAggregateElement(i);
2269  if (!EltC1 || !EltC2)
2270  return false;
2271 
2272  // One element must be all ones, and the other must be all zeros.
2273  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
2274  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
2275  return false;
2276  }
2277  return true;
2278 }
2279 
2280 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
2281 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
2282 /// B, it can be used as the condition operand of a select instruction.
2283 Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) {
2284  // Step 1: We may have peeked through bitcasts in the caller.
2285  // Exit immediately if we don't have (vector) integer types.
2286  Type *Ty = A->getType();
2287  if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
2288  return nullptr;
2289 
2290  // Step 2: We need 0 or all-1's bitmasks.
2291  if (ComputeNumSignBits(A) != Ty->getScalarSizeInBits())
2292  return nullptr;
2293 
2294  // Step 3: If B is the 'not' value of A, we have our answer.
2295  if (match(A, m_Not(m_Specific(B)))) {
2296  // If these are scalars or vectors of i1, A can be used directly.
2297  if (Ty->isIntOrIntVectorTy(1))
2298  return A;
2299  return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(Ty));
2300  }
2301 
2302  // If both operands are constants, see if the constants are inverse bitmasks.
2303  Constant *AConst, *BConst;
2304  if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
2305  if (AConst == ConstantExpr::getNot(BConst))
2306  return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty));
2307 
2308  // Look for more complex patterns. The 'not' op may be hidden behind various
2309  // casts. Look through sexts and bitcasts to find the booleans.
2310  Value *Cond;
2311  Value *NotB;
2312  if (match(A, m_SExt(m_Value(Cond))) &&
2313  Cond->getType()->isIntOrIntVectorTy(1) &&
2314  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
2315  NotB = peekThroughBitcast(NotB, true);
2316  if (match(NotB, m_SExt(m_Specific(Cond))))
2317  return Cond;
2318  }
2319 
2320  // All scalar (and most vector) possibilities should be handled now.
2321  // Try more matches that only apply to non-splat constant vectors.
2322  if (!Ty->isVectorTy())
2323  return nullptr;
2324 
2325  // If both operands are xor'd with constants using the same sexted boolean
2326  // operand, see if the constants are inverse bitmasks.
2327  // TODO: Use ConstantExpr::getNot()?
2328  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
2329  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) &&
2330  Cond->getType()->isIntOrIntVectorTy(1) &&
2331  areInverseVectorBitmasks(AConst, BConst)) {
2332  AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty));
2333  return Builder.CreateXor(Cond, AConst);
2334  }
2335  return nullptr;
2336 }
2337 
2338 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
2339 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
2340 Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
2341  Value *D) {
2342  // The potential condition of the select may be bitcasted. In that case, look
2343  // through its bitcast and the corresponding bitcast of the 'not' condition.
2344  Type *OrigType = A->getType();
2345  A = peekThroughBitcast(A, true);
2346  B = peekThroughBitcast(B, true);
2347  if (Value *Cond = getSelectCondition(A, B)) {
2348  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
2349  // The bitcasts will either all exist or all not exist. The builder will
2350  // not create unnecessary casts if the types already match.
2351  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
2352  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
2353  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
2354  return Builder.CreateBitCast(Select, OrigType);
2355  }
2356 
2357  return nullptr;
2358 }
2359 
2360 /// Fold (icmp)|(icmp) if possible.
2361 Value *InstCombinerImpl::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2362  BinaryOperator &Or) {
2363  const SimplifyQuery Q = SQ.getWithInstruction(&Or);
2364 
2365  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
2366  // if K1 and K2 are a one-bit mask.
2367  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, &Or,
2368  /* IsAnd */ false))
2369  return V;
2370 
2371  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2372  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
2373  Value *LHS1 = LHS->getOperand(1), *RHS1 = RHS->getOperand(1);
2374  auto *LHSC = dyn_cast<ConstantInt>(LHS1);
2375  auto *RHSC = dyn_cast<ConstantInt>(RHS1);
2376 
2377  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
2378  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
2379  // The original condition actually refers to the following two ranges:
2380  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
2381  // We can fold these two ranges if:
2382  // 1) C1 and C2 is unsigned greater than C3.
2383  // 2) The two ranges are separated.
2384  // 3) C1 ^ C2 is one-bit mask.
2385  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
2386  // This implies all values in the two ranges differ by exactly one bit.
2387  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
2388  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
2389  LHSC->getType() == RHSC->getType() &&
2390  LHSC->getValue() == (RHSC->getValue())) {
2391 
2392  Value *AddOpnd;
2393  ConstantInt *LAddC, *RAddC;
2394  if (match(LHS0, m_Add(m_Value(AddOpnd), m_ConstantInt(LAddC))) &&
2395  match(RHS0, m_Add(m_Specific(AddOpnd), m_ConstantInt(RAddC))) &&
2396  LAddC->getValue().ugt(LHSC->getValue()) &&
2397  RAddC->getValue().ugt(LHSC->getValue())) {
2398 
2399  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
2400  if (DiffC.isPowerOf2()) {
2401  ConstantInt *MaxAddC = nullptr;
2402  if (LAddC->getValue().ult(RAddC->getValue()))
2403  MaxAddC = RAddC;
2404  else
2405  MaxAddC = LAddC;
2406 
2407  APInt RRangeLow = -RAddC->getValue();
2408  APInt RRangeHigh = RRangeLow + LHSC->getValue();
2409  APInt LRangeLow = -LAddC->getValue();
2410  APInt LRangeHigh = LRangeLow + LHSC->getValue();
2411  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
2412  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
2413  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
2414  : RRangeLow - LRangeLow;
2415 
2416  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
2417  RangeDiff.ugt(LHSC->getValue())) {
2418  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
2419 
2420  Value *NewAnd = Builder.CreateAnd(AddOpnd, MaskC);
2421  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
2422  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
2423  }
2424  }
2425  }
2426  }
2427 
2428  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
2429  if (predicatesFoldable(PredL, PredR)) {
2430  if (LHS0 == RHS1 && LHS1 == RHS0)
2431  LHS->swapOperands();
2432  if (LHS0 == RHS0 && LHS1 == RHS1) {
2433  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
2434  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2435  return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
2436  }
2437  }
2438 
2439  // handle (roughly):
2440  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
2441  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
2442  return V;
2443 
2444  if (LHS->hasOneUse() || RHS->hasOneUse()) {
2445  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
2446  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
2447  Value *A = nullptr, *B = nullptr;
2448  if (PredL == ICmpInst::ICMP_EQ && match(LHS1, m_Zero())) {
2449  B = LHS0;
2450  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS1)
2451  A = RHS0;
2452  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
2453  A = RHS1;
2454  }
2455  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
2456  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
2457  else if (PredR == ICmpInst::ICMP_EQ && match(RHS1, m_Zero())) {
2458  B = RHS0;
2459  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS1)
2460  A = LHS0;
2461  else if (PredL == ICmpInst::ICMP_UGT && RHS0 == LHS0)
2462  A = LHS1;
2463  }
2464  if (A && B && B->getType()->isIntOrIntVectorTy())
2465  return Builder.CreateICmp(
2467  Builder.CreateAdd(B, Constant::getAllOnesValue(B->getType())), A);
2468  }
2469 
2470  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, Or, Builder, Q))
2471  return V;
2472  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, Or, Builder, Q))
2473  return V;
2474 
2475  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
2476  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
2477  return V;
2478 
2479  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
2480  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
2481  return V;
2482 
2483  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
2484  return V;
2485 
2486  if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder))
2487  return V;
2488 
2489  if (Value *X =
2490  foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/false, Q, Builder))
2491  return X;
2492  if (Value *X =
2493  foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/false, Q, Builder))
2494  return X;
2495 
2496  if (Value *X = foldEqOfParts(LHS, RHS, /*IsAnd=*/false))
2497  return X;
2498 
2499  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
2500  // TODO: Remove this when foldLogOpOfMaskedICmps can handle vectors.
2501  if (PredL == ICmpInst::ICMP_NE && match(LHS1, m_Zero()) &&
2502  PredR == ICmpInst::ICMP_NE && match(RHS1, m_Zero()) &&
2503  LHS0->getType()->isIntOrIntVectorTy() &&
2504  LHS0->getType() == RHS0->getType()) {
2505  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
2506  return Builder.CreateICmp(PredL, NewOr,
2507  Constant::getNullValue(NewOr->getType()));
2508  }
2509 
2510  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
2511  if (!LHSC || !RHSC)
2512  return nullptr;
2513 
2514  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
2515  // iff C2 + CA == C1.
2516  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
2517  ConstantInt *AddC;
2518  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
2519  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
2520  return Builder.CreateICmpULE(LHS0, LHSC);
2521  }
2522 
2523  // From here on, we only handle:
2524  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
2525  if (LHS0 != RHS0)
2526  return nullptr;
2527 
2528  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
2529  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
2530  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
2531  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
2532  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
2533  return nullptr;
2534 
2535  // We can't fold (ugt x, C) | (sgt x, C2).
2536  if (!predicatesFoldable(PredL, PredR))
2537  return nullptr;
2538 
2539  // Ensure that the larger constant is on the RHS.
2540  bool ShouldSwap;
2541  if (CmpInst::isSigned(PredL) ||
2542  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
2543  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
2544  else
2545  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
2546 
2547  if (ShouldSwap) {
2548  std::swap(LHS, RHS);
2549  std::swap(LHSC, RHSC);
2550  std::swap(PredL, PredR);
2551  }
2552 
2553  // At this point, we know we have two icmp instructions
2554  // comparing a value against two constants and or'ing the result
2555  // together. Because of the above check, we know that we only have
2556  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
2557  // icmp folding check above), that the two constants are not
2558  // equal.
2559  assert(LHSC != RHSC && "Compares not folded above?");
2560 
2561  switch (PredL) {
2562  default:
2563  llvm_unreachable("Unknown integer condition code!");
2564  case ICmpInst::ICMP_EQ:
2565  switch (PredR) {
2566  default:
2567  llvm_unreachable("Unknown integer condition code!");
2568  case ICmpInst::ICMP_EQ:
2569  // Potential folds for this case should already be handled.
2570  break;
2571  case ICmpInst::ICMP_UGT:
2572  // (X == 0 || X u> C) -> (X-1) u>= C
2573  if (LHSC->isMinValue(false))
2574  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2575  false, false);
2576  // (X == 13 | X u> 14) -> no change
2577  break;
2578  case ICmpInst::ICMP_SGT:
2579  // (X == INT_MIN || X s> C) -> (X-(INT_MIN+1)) u>= C-INT_MIN
2580  if (LHSC->isMinValue(true))
2581  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
2582  true, false);
2583  // (X == 13 | X s> 14) -> no change
2584  break;
2585  }
2586  break;
2587  case ICmpInst::ICMP_ULT:
2588  switch (PredR) {
2589  default:
2590  llvm_unreachable("Unknown integer condition code!");
2591  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
2592  // (X u< C || X == UINT_MAX) => (X-C) u>= UINT_MAX-C
2593  if (RHSC->isMaxValue(false))
2594  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2595  false, false);
2596  break;
2597  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
2598  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
2599  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
2600  false, false);
2601  }
2602  break;
2603  case ICmpInst::ICMP_SLT:
2604  switch (PredR) {
2605  default:
2606  llvm_unreachable("Unknown integer condition code!");
2607  case ICmpInst::ICMP_EQ:
2608  // (X s< C || X == INT_MAX) => (X-C) u>= INT_MAX-C
2609  if (RHSC->isMaxValue(true))
2610  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
2611  true, false);
2612  // (X s< 13 | X == 14) -> no change
2613  break;
2614  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) u> 2
2615  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
2616  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
2617  false);
2618  }
2619  break;
2620  }
2621  return nullptr;
2622 }
2623 
2624 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2625 // here. We should standardize that construct where it is needed or choose some
2626 // other way to ensure that commutated variants of patterns are not missed.
2628  if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
2629  SQ.getWithInstruction(&I)))
2630  return replaceInstUsesWith(I, V);
2631 
2632  if (SimplifyAssociativeOrCommutative(I))
2633  return &I;
2634 
2635  if (Instruction *X = foldVectorBinop(I))
2636  return X;
2637 
2638  // See if we can simplify any instructions used by the instruction whose sole
2639  // purpose is to compute bits we don't care about.
2640  if (SimplifyDemandedInstructionBits(I))
2641  return &I;
2642 
2643  // Do this before using distributive laws to catch simple and/or/not patterns.
2644  if (Instruction *Xor = foldOrToXor(I, Builder))
2645  return Xor;
2646 
2647  // (A&B)|(A&C) -> A&(B|C) etc
2648  if (Value *V = SimplifyUsingDistributiveLaws(I))
2649  return replaceInstUsesWith(I, V);
2650 
2651  if (Value *V = SimplifyBSwap(I, Builder))
2652  return replaceInstUsesWith(I, V);
2653 
2654  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2655  if (I.getType()->isIntOrIntVectorTy(1)) {
2656  if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
2657  if (auto *I =
2658  foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false))
2659  return I;
2660  }
2661  if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
2662  if (auto *I =
2663  foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ false))
2664  return I;
2665  }
2666  }
2667 
2668  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2669  return FoldedLogic;
2670 
2671  if (Instruction *BitOp = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
2672  /*MatchBitReversals*/ true))
2673  return BitOp;
2674 
2675  if (Instruction *Funnel = matchFunnelShift(I, *this))
2676  return Funnel;
2677 
2679  return replaceInstUsesWith(I, Concat);
2680 
2681  Value *X, *Y;
2682  const APInt *CV;
2683  if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
2684  !CV->isAllOnes() && MaskedValueIsZero(Y, *CV, 0, &I)) {
2685  // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
2686  // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
2687  Value *Or = Builder.CreateOr(X, Y);
2688  return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
2689  }
2690 
2691  // (A & C)|(B & D)
2692  Value *A, *B, *C, *D;
2693  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2694  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2695  // (A & C1)|(B & C2)
2696  ConstantInt *C1, *C2;
2697  if (match(C, m_ConstantInt(C1)) && match(D, m_ConstantInt(C2))) {
2698  Value *V1 = nullptr, *V2 = nullptr;
2699  if ((C1->getValue() & C2->getValue()).isZero()) {
2700  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2701  // iff (C1&C2) == 0 and (N&~C1) == 0
2702  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2703  ((V1 == B &&
2704  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2705  (V2 == B &&
2706  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2707  return BinaryOperator::CreateAnd(A,
2708  Builder.getInt(C1->getValue()|C2->getValue()));
2709  // Or commutes, try both ways.
2710  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2711  ((V1 == A &&
2712  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2713  (V2 == A &&
2714  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2715  return BinaryOperator::CreateAnd(B,
2716  Builder.getInt(C1->getValue()|C2->getValue()));
2717 
2718  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2719  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2720  ConstantInt *C3 = nullptr, *C4 = nullptr;
2721  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2722  (C3->getValue() & ~C1->getValue()).isZero() &&
2723  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2724  (C4->getValue() & ~C2->getValue()).isZero()) {
2725  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2726  return BinaryOperator::CreateAnd(V2,
2727  Builder.getInt(C1->getValue()|C2->getValue()));
2728  }
2729  }
2730 
2731  if (C1->getValue() == ~C2->getValue()) {
2732  Value *X;
2733 
2734  // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2
2735  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2736  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B);
2737  // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2
2738  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2739  return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A);
2740 
2741  // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2
2742  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2743  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B);
2744  // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2
2745  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2746  return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A);
2747  }
2748  }
2749 
2750  // Don't try to form a select if it's unlikely that we'll get rid of at
2751  // least one of the operands. A select is generally more expensive than the
2752  // 'or' that it is replacing.
2753  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2754  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2755  if (Value *V = matchSelectFromAndOr(A, C, B, D))
2756  return replaceInstUsesWith(I, V);
2757  if (Value *V = matchSelectFromAndOr(A, C, D, B))
2758  return replaceInstUsesWith(I, V);
2759  if (Value *V = matchSelectFromAndOr(C, A, B, D))
2760  return replaceInstUsesWith(I, V);
2761  if (Value *V = matchSelectFromAndOr(C, A, D, B))
2762  return replaceInstUsesWith(I, V);
2763  if (Value *V = matchSelectFromAndOr(B, D, A, C))
2764  return replaceInstUsesWith(I, V);
2765  if (Value *V = matchSelectFromAndOr(B, D, C, A))
2766  return replaceInstUsesWith(I, V);
2767  if (Value *V = matchSelectFromAndOr(D, B, A, C))
2768  return replaceInstUsesWith(I, V);
2769  if (Value *V = matchSelectFromAndOr(D, B, C, A))
2770  return replaceInstUsesWith(I, V);
2771  }
2772  }
2773 
2774  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2775  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2776  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2777  return BinaryOperator::CreateOr(Op0, C);
2778 
2779  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2780  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2781  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2782  return BinaryOperator::CreateOr(Op1, C);
2783 
2784  // ((B | C) & A) | B -> B | (A & C)
2785  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2786  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2787 
2788  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2789  return DeMorgan;
2790 
2791  // Canonicalize xor to the RHS.
2792  bool SwappedForXor = false;
2793  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2794  std::swap(Op0, Op1);
2795  SwappedForXor = true;
2796  }
2797 
2798  // A | ( A ^ B) -> A | B
2799  // A | (~A ^ B) -> A | ~B
2800  // (A & B) | (A ^ B)
2801  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2802  if (Op0 == A || Op0 == B)
2803  return BinaryOperator::CreateOr(A, B);
2804 
2805  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2806  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2807  return BinaryOperator::CreateOr(A, B);
2808 
2809  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2810  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2811  return BinaryOperator::CreateOr(Not, Op0);
2812  }
2813  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2814  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2815  return BinaryOperator::CreateOr(Not, Op0);
2816  }
2817  }
2818 
2819  // A | ~(A | B) -> A | ~B
2820  // A | ~(A ^ B) -> A | ~B
2821  if (match(Op1, m_Not(m_Value(A))))
2822  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2823  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2824  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2825  B->getOpcode() == Instruction::Xor)) {
2826  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2827  B->getOperand(0);
2828  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2829  return BinaryOperator::CreateOr(Not, Op0);
2830  }
2831 
2832  if (SwappedForXor)
2833  std::swap(Op0, Op1);
2834 
2835  {
2836  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2837  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2838  if (LHS && RHS)
2839  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2840  return replaceInstUsesWith(I, Res);
2841 
2842  // TODO: Make this recursive; it's a little tricky because an arbitrary
2843  // number of 'or' instructions might have to be created.
2844  Value *X, *Y;
2845  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2846  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2847  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2848  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2849  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2850  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2851  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2852  }
2853  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2854  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2855  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2856  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2857  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2858  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2859  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2860  }
2861  }
2862 
2863  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2864  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2865  if (Value *Res = foldLogicOfFCmps(LHS, RHS, false))
2866  return replaceInstUsesWith(I, Res);
2867 
2868  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2869  return FoldedFCmps;
2870 
2871  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2872  return CastedOr;
2873 
2874  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2875  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2876  A->getType()->isIntOrIntVectorTy(1))
2877  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2878  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2879  A->getType()->isIntOrIntVectorTy(1))
2880  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2881 
2882  // Note: If we've gotten to the point of visiting the outer OR, then the
2883  // inner one couldn't be simplified. If it was a constant, then it won't
2884  // be simplified by a later pass either, so we try swapping the inner/outer
2885  // ORs in the hopes that we'll be able to simplify it this way.
2886  // (X|C) | V --> (X|V) | C
2887  ConstantInt *CI;
2888  if (Op0->hasOneUse() && !match(Op1, m_ConstantInt()) &&
2889  match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
2890  Value *Inner = Builder.CreateOr(A, Op1);
2891  Inner->takeName(Op0);
2892  return BinaryOperator::CreateOr(Inner, CI);
2893  }
2894 
2895  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2896  // Since this OR statement hasn't been optimized further yet, we hope
2897  // that this transformation will allow the new ORs to be optimized.
2898  {
2899  Value *X = nullptr, *Y = nullptr;
2900  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2901  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2902  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2903  Value *orTrue = Builder.CreateOr(A, C);
2904  Value *orFalse = Builder.CreateOr(B, D);
2905  return SelectInst::Create(X, orTrue, orFalse);
2906  }
2907  }
2908 
2909  // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X.
2910  {
2911  Value *X, *Y;
2912  Type *Ty = I.getType();
2913  if (match(&I, m_c_Or(m_OneUse(m_AShr(
2914  m_NSWSub(m_Value(Y), m_Value(X)),
2915  m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
2916  m_Deferred(X)))) {
2917  Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
2918  Value *AllOnes = ConstantInt::getAllOnesValue(Ty);
2919  return SelectInst::Create(NewICmpInst, AllOnes, X);
2920  }
2921  }
2922 
2923  if (Instruction *V =
2924  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2925  return V;
2926 
2927  CmpInst::Predicate Pred;
2928  Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2929  // Check if the OR weakens the overflow condition for umul.with.overflow by
2930  // treating any non-zero result as overflow. In that case, we overflow if both
2931  // umul.with.overflow operands are != 0, as in that case the result can only
2932  // be 0, iff the multiplication overflows.
2933  if (match(&I,
2934  m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_Value(UMulWithOv)),
2935  m_Value(Ov)),
2936  m_CombineAnd(m_ICmp(Pred,
2937  m_CombineAnd(m_ExtractValue<0>(
2938  m_Deferred(UMulWithOv)),
2939  m_Value(Mul)),
2940  m_ZeroInt()),
2941  m_Value(MulIsNotZero)))) &&
2942  (Ov->hasOneUse() || (MulIsNotZero->hasOneUse() && Mul->hasOneUse())) &&
2943  Pred == CmpInst::ICMP_NE) {
2944  Value *A, *B;
2945  if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2946  m_Value(A), m_Value(B)))) {
2947  Value *NotNullA = Builder.CreateIsNotNull(A);
2948  Value *NotNullB = Builder.CreateIsNotNull(B);
2949  return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2950  }
2951  }
2952 
2953  // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions
2954  if (sinkNotIntoOtherHandOfAndOrOr(I))
2955  return &I;
2956 
2957  // Improve "get low bit mask up to and including bit X" pattern:
2958  // (1 << X) | ((1 << X) + -1) --> -1 l>> (bitwidth(x) - 1 - X)
2959  if (match(&I, m_c_Or(m_Add(m_Shl(m_One(), m_Value(X)), m_AllOnes()),
2960  m_Shl(m_One(), m_Deferred(X)))) &&
2961  match(&I, m_c_Or(m_OneUse(m_Value()), m_Value()))) {
2962  Type *Ty = X->getType();
2963  Value *Sub = Builder.CreateSub(
2964  ConstantInt::get(Ty, Ty->getScalarSizeInBits() - 1), X);
2965  return BinaryOperator::CreateLShr(Constant::getAllOnesValue(Ty), Sub);
2966  }
2967 
2968  // An or recurrence w/loop invariant step is equivelent to (or start, step)
2969  PHINode *PN = nullptr;
2970  Value *Start = nullptr, *Step = nullptr;
2971  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2972  return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
2973 
2974  return nullptr;
2975 }
2976 
2977 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2978 /// can fold these early and efficiently by morphing an existing instruction.
2981  assert(I.getOpcode() == Instruction::Xor);
2982  Value *Op0 = I.getOperand(0);
2983  Value *Op1 = I.getOperand(1);
2984  Value *A, *B;
2985 
2986  // There are 4 commuted variants for each of the basic patterns.
2987 
2988  // (A & B) ^ (A | B) -> A ^ B
2989  // (A & B) ^ (B | A) -> A ^ B
2990  // (A | B) ^ (A & B) -> A ^ B
2991  // (A | B) ^ (B & A) -> A ^ B
2992  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2993  m_c_Or(m_Deferred(A), m_Deferred(B)))))
2994  return BinaryOperator::CreateXor(A, B);
2995 
2996  // (A | ~B) ^ (~A | B) -> A ^ B
2997  // (~B | A) ^ (~A | B) -> A ^ B
2998  // (~A | B) ^ (A | ~B) -> A ^ B
2999  // (B | ~A) ^ (A | ~B) -> A ^ B
3000  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
3001  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
3002  return BinaryOperator::CreateXor(A, B);
3003 
3004  // (A & ~B) ^ (~A & B) -> A ^ B
3005  // (~B & A) ^ (~A & B) -> A ^ B
3006  // (~A & B) ^ (A & ~B) -> A ^ B
3007  // (B & ~A) ^ (A & ~B) -> A ^ B
3008  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
3009  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B)))))
3010  return BinaryOperator::CreateXor(A, B);
3011 
3012  // For the remaining cases we need to get rid of one of the operands.
3013  if (!Op0->hasOneUse() && !Op1->hasOneUse())
3014  return nullptr;
3015 
3016  // (A | B) ^ ~(A & B) -> ~(A ^ B)
3017  // (A | B) ^ ~(B & A) -> ~(A ^ B)
3018  // (A & B) ^ ~(A | B) -> ~(A ^ B)
3019  // (A & B) ^ ~(B | A) -> ~(A ^ B)
3020  // Complexity sorting ensures the not will be on the right side.
3021  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
3022  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
3023  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
3024  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
3025  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
3026 
3027  return nullptr;
3028 }
3029 
3030 Value *InstCombinerImpl::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
3031  BinaryOperator &I) {
3032  assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
3033  I.getOperand(1) == RHS && "Should be 'xor' with these operands");
3034 
3035  if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
3036  if (LHS->getOperand(0) == RHS->getOperand(1) &&
3037  LHS->getOperand(1) == RHS->getOperand(0))
3038  LHS->swapOperands();
3039  if (LHS->getOperand(0) == RHS->getOperand(0) &&
3040  LHS->getOperand(1) == RHS->getOperand(1)) {
3041  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
3042  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
3043  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
3044  bool IsSigned = LHS->isSigned() || RHS->isSigned();
3045  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
3046  }
3047  }
3048 
3049  // TODO: This can be generalized to compares of non-signbits using
3050  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
3051  // foldLogOpOfMaskedICmps().
3052  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
3053  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
3054  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
3055  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
3056  LHS0->getType() == RHS0->getType() &&
3057  LHS0->getType()->isIntOrIntVectorTy()) {
3058  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
3059  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
3060  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
3061  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
3062  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
3063  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) {
3064  Value *Zero = ConstantInt::getNullValue(LHS0->getType());
3065  return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero);
3066  }
3067  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
3068  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
3069  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
3070  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
3071  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
3072  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) {
3073  Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType());
3074  return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne);
3075  }
3076  }
3077 
3078  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
3079  // into those logic ops. That is, try to turn this into an and-of-icmps
3080  // because we have many folds for that pattern.
3081  //
3082  // This is based on a truth table definition of xor:
3083  // X ^ Y --> (X | Y) & !(X & Y)
3084  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
3085  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
3086  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
3087  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
3088  // TODO: Independently handle cases where the 'and' side is a constant.
3089  ICmpInst *X = nullptr, *Y = nullptr;
3090  if (OrICmp == LHS && AndICmp == RHS) {
3091  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS --> X & !Y
3092  X = LHS;
3093  Y = RHS;
3094  }
3095  if (OrICmp == RHS && AndICmp == LHS) {
3096  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS --> !Y & X
3097  X = RHS;
3098  Y = LHS;
3099  }
3100  if (X && Y && (Y->hasOneUse() || canFreelyInvertAllUsersOf(Y, &I))) {
3101  // Invert the predicate of 'Y', thus inverting its output.
3102  Y->setPredicate(Y->getInversePredicate());
3103  // So, are there other uses of Y?
3104  if (!Y->hasOneUse()) {
3105  // We need to adapt other uses of Y though. Get a value that matches
3106  // the original value of Y before inversion. While this increases
3107  // immediate instruction count, we have just ensured that all the
3108  // users are freely-invertible, so that 'not' *will* get folded away.
3110  // Set insertion point to right after the Y.
3111  Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
3112  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3113  // Replace all uses of Y (excluding the one in NotY!) with NotY.
3114  Worklist.pushUsersToWorkList(*Y);
3115  Y->replaceUsesWithIf(NotY,
3116  [NotY](Use &U) { return U.getUser() != NotY; });
3117  }
3118  // All done.
3119  return Builder.CreateAnd(LHS, RHS);
3120  }
3121  }
3122  }
3123 
3124  return nullptr;
3125 }
3126 
3127 /// If we have a masked merge, in the canonical form of:
3128 /// (assuming that A only has one use.)
3129 /// | A | |B|
3130 /// ((x ^ y) & M) ^ y
3131 /// | D |
3132 /// * If M is inverted:
3133 /// | D |
3134 /// ((x ^ y) & ~M) ^ y
3135 /// We can canonicalize by swapping the final xor operand
3136 /// to eliminate the 'not' of the mask.
3137 /// ((x ^ y) & M) ^ x
3138 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
3139 /// because that shortens the dependency chain and improves analysis:
3140 /// (x & M) | (y & ~M)
3143  Value *B, *X, *D;
3144  Value *M;
3145  if (!match(&I, m_c_Xor(m_Value(B),
3146  m_OneUse(m_c_And(
3148  m_Value(D)),
3149  m_Value(M))))))
3150  return nullptr;
3151 
3152  Value *NotM;
3153  if (match(M, m_Not(m_Value(NotM)))) {
3154  // De-invert the mask and swap the value in B part.
3155  Value *NewA = Builder.CreateAnd(D, NotM);
3156  return BinaryOperator::CreateXor(NewA, X);
3157  }
3158 
3159  Constant *C;
3160  if (D->hasOneUse() && match(M, m_Constant(C))) {
3161  // Propagating undef is unsafe. Clamp undef elements to -1.
3162  Type *EltTy = C->getType()->getScalarType();
3164  // Unfold.
3165  Value *LHS = Builder.CreateAnd(X, C);
3166  Value *NotC = Builder.CreateNot(C);
3167  Value *RHS = Builder.CreateAnd(B, NotC);
3168  return BinaryOperator::CreateOr(LHS, RHS);
3169  }
3170 
3171  return nullptr;
3172 }
3173 
3174 // Transform
3175 // ~(x ^ y)
3176 // into:
3177 // (~x) ^ y
3178 // or into
3179 // x ^ (~y)
3182  Value *X, *Y;
3183  // FIXME: one-use check is not needed in general, but currently we are unable
3184  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
3185  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
3186  return nullptr;
3187 
3188  // We only want to do the transform if it is free to do.
3189  if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) {
3190  // Ok, good.
3191  } else if (InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) {
3192  std::swap(X, Y);
3193  } else
3194  return nullptr;
3195 
3196  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
3197  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
3198 }
3199 
3200 /// Canonicalize a shifty way to code absolute value to the more common pattern
3201 /// that uses negation and select.
3204  assert(Xor.getOpcode() == Instruction::Xor && "Expected an xor instruction.");
3205 
3206  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
3207  // We're relying on the fact that we only do this transform when the shift has
3208  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
3209  // instructions).
3210  Value *Op0 = Xor.getOperand(0), *Op1 = Xor.getOperand(1);
3211  if (Op0->hasNUses(2))
3212  std::swap(Op0, Op1);
3213 
3214  Type *Ty = Xor.getType();
3215  Value *A;
3216  const APInt *ShAmt;
3217  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
3218  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
3219  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
3220  // Op1 = ashr i32 A, 31 ; smear the sign bit
3221  // xor (add A, Op1), Op1 ; add -1 and flip bits if negative
3222  // --> (A < 0) ? -A : A
3223  Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty));
3224  // Copy the nuw/nsw flags from the add to the negate.
3225  auto *Add = cast<BinaryOperator>(Op0);
3226  Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
3227  Add->hasNoSignedWrap());
3228  return SelectInst::Create(Cmp, Neg, A);
3229  }
3230  return nullptr;
3231 }
3232 
3233 // Transform
3234 // z = (~x) &/| y
3235 // into:
3236 // z = ~(x |/& (~y))
3237 // iff y is free to invert and all uses of z can be freely updated.
3239  Instruction::BinaryOps NewOpc;
3240  switch (I.getOpcode()) {
3241  case Instruction::And:
3242  NewOpc = Instruction::Or;
3243  break;
3244  case Instruction::Or:
3245  NewOpc = Instruction::And;
3246  break;
3247  default:
3248  return false;
3249  };
3250 
3251  Value *X, *Y;
3252  if (!match(&I, m_c_BinOp(m_Not(m_Value(X)), m_Value(Y))))
3253  return false;
3254 
3255  // Will we be able to fold the `not` into Y eventually?
3256  if (!InstCombiner::isFreeToInvert(Y, Y->hasOneUse()))
3257  return false;
3258 
3259  // And can our users be adapted?
3260  if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
3261  return false;
3262 
3263  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3264  Value *NewBinOp =
3265  BinaryOperator::Create(NewOpc, X, NotY, I.getName() + ".not");
3266  Builder.Insert(NewBinOp);
3267  replaceInstUsesWith(I, NewBinOp);
3268  // We can not just create an outer `not`, it will most likely be immediately
3269  // folded back, reconstructing our initial pattern, and causing an
3270  // infinite combine loop, so immediately manually fold it away.
3271  freelyInvertAllUsersOf(NewBinOp);
3272  return true;
3273 }
3274 
3275 Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) {
3276  Value *NotOp;
3277  if (!match(&I, m_Not(m_Value(NotOp))))
3278  return nullptr;
3279 
3280  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
3281  // We must eliminate the and/or (one-use) for these transforms to not increase
3282  // the instruction count.
3283  //
3284  // ~(~X & Y) --> (X | ~Y)
3285  // ~(Y & ~X) --> (X | ~Y)
3286  //
3287  // Note: The logical matches do not check for the commuted patterns because
3288  // those are handled via SimplifySelectsFeedingBinaryOp().
3289  Type *Ty = I.getType();
3290  Value *X, *Y;
3291  if (match(NotOp, m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y))))) {
3292  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3293  return BinaryOperator::CreateOr(X, NotY);
3294  }
3295  if (match(NotOp, m_OneUse(m_LogicalAnd(m_Not(m_Value(X)), m_Value(Y))))) {
3296  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3297  return SelectInst::Create(X, ConstantInt::getTrue(Ty), NotY);
3298  }
3299 
3300  // ~(~X | Y) --> (X & ~Y)
3301  // ~(Y | ~X) --> (X & ~Y)
3302  if (match(NotOp, m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y))))) {
3303  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3304  return BinaryOperator::CreateAnd(X, NotY);
3305  }
3306  if (match(NotOp, m_OneUse(m_LogicalOr(m_Not(m_Value(X)), m_Value(Y))))) {
3307  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3308  return SelectInst::Create(X, NotY, ConstantInt::getFalse(Ty));
3309  }
3310 
3311  // Is this a 'not' (~) fed by a binary operator?
3312  BinaryOperator *NotVal;
3313  if (match(NotOp, m_BinOp(NotVal))) {
3314  if (NotVal->getOpcode() == Instruction::And ||
3315  NotVal->getOpcode() == Instruction::Or) {
3316  // Apply DeMorgan's Law when inverts are free:
3317  // ~(X & Y) --> (~X | ~Y)
3318  // ~(X | Y) --> (~X & ~Y)
3319  if (isFreeToInvert(NotVal->getOperand(0),
3320  NotVal->getOperand(0)->hasOneUse()) &&
3321  isFreeToInvert(NotVal->getOperand(1),
3322  NotVal->getOperand(1)->hasOneUse())) {
3323  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
3324  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
3325  if (NotVal->getOpcode() == Instruction::And)
3326  return BinaryOperator::CreateOr(NotX, NotY);
3327  return BinaryOperator::CreateAnd(NotX, NotY);
3328  }
3329  }
3330 
3331  // ~((-X) | Y) --> (X - 1) & (~Y)
3332  if (match(NotVal,
3334  Value *DecX = Builder.CreateAdd(X, ConstantInt::getAllOnesValue(Ty));
3335  Value *NotY = Builder.CreateNot(Y);
3336  return BinaryOperator::CreateAnd(DecX, NotY);
3337  }
3338 
3339  // ~(~X >>s Y) --> (X >>s Y)
3340  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
3341  return BinaryOperator::CreateAShr(X, Y);
3342 
3343  // If we are inverting a right-shifted constant, we may be able to eliminate
3344  // the 'not' by inverting the constant and using the opposite shift type.
3345  // Canonicalization rules ensure that only a negative constant uses 'ashr',
3346  // but we must check that in case that transform has not fired yet.
3347 
3348  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
3349  Constant *C;
3350  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
3351  match(C, m_Negative())) {
3352  // We matched a negative constant, so propagating undef is unsafe.
3353  // Clamp undef elements to -1.
3354  Type *EltTy = Ty->getScalarType();
3356  return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
3357  }
3358 
3359  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
3360  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
3361  match(C, m_NonNegative())) {
3362  // We matched a non-negative constant, so propagating undef is unsafe.
3363  // Clamp undef elements to 0.
3364  Type *EltTy = Ty->getScalarType();
3366  return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
3367  }
3368 
3369  // ~(X + C) --> ~C - X
3370  if (match(NotVal, m_c_Add(m_Value(X), m_ImmConstant(C))))
3371  return BinaryOperator::CreateSub(ConstantExpr::getNot(C), X);
3372 
3373  // ~(X - Y) --> ~X + Y
3374  // FIXME: is it really beneficial to sink the `not` here?
3375  if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
3376  if (isa<Constant>(X) || NotVal->hasOneUse())
3377  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
3378 
3379  // ~(~X + Y) --> X - Y
3380  if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
3381  return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
3382  NotVal);
3383  }
3384 
3385  // not (cmp A, B) = !cmp A, B
3386  CmpInst::Predicate Pred;
3387  if (match(NotOp, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
3388  cast<CmpInst>(NotOp)->setPredicate(CmpInst::getInversePredicate(Pred));
3389  return replaceInstUsesWith(I, NotOp);
3390  }
3391 
3392  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3393  // ~min(~X, ~Y) --> max(X, Y)
3394  // ~max(~X, Y) --> min(X, ~Y)
3395  auto *II = dyn_cast<IntrinsicInst>(NotOp);
3396  if (II && II->hasOneUse()) {
3397  if (match(NotOp, m_MaxOrMin(m_Value(X), m_Value(Y))) &&
3398  isFreeToInvert(X, X->hasOneUse()) &&
3399  isFreeToInvert(Y, Y->hasOneUse())) {
3400  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3401  Value *NotX = Builder.CreateNot(X);
3402  Value *NotY = Builder.CreateNot(Y);
3403  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, NotX, NotY);
3404  return replaceInstUsesWith(I, InvMaxMin);
3405  }
3406  if (match(NotOp, m_c_MaxOrMin(m_Not(m_Value(X)), m_Value(Y)))) {
3407  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3408  Value *NotY = Builder.CreateNot(Y);
3409  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotY);
3410  return replaceInstUsesWith(I, InvMaxMin);
3411  }
3412  }
3413 
3414  // TODO: Remove folds if we canonicalize to intrinsics (see above).
3415  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3416  //
3417  // %notx = xor i32 %x, -1
3418  // %cmp1 = icmp sgt i32 %notx, %y
3419  // %smax = select i1 %cmp1, i32 %notx, i32 %y
3420  // %res = xor i32 %smax, -1
3421  // =>
3422  // %noty = xor i32 %y, -1
3423  // %cmp2 = icmp slt %x, %noty
3424  // %res = select i1 %cmp2, i32 %x, i32 %noty
3425  //
3426  // Same is applicable for smin/umax/umin.
3427  if (NotOp->hasOneUse()) {
3428  Value *LHS, *RHS;
3429  SelectPatternFlavor SPF = matchSelectPattern(NotOp, LHS, RHS).Flavor;
3431  // It's possible we get here before the not has been simplified, so make
3432  // sure the input to the not isn't freely invertible.
3433  if (match(LHS, m_Not(m_Value(X))) && !isFreeToInvert(X, X->hasOneUse())) {
3434  Value *NotY = Builder.CreateNot(RHS);
3435  return SelectInst::Create(
3436  Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
3437  }
3438 
3439  // It's possible we get here before the not has been simplified, so make
3440  // sure the input to the not isn't freely invertible.
3441  if (match(RHS, m_Not(m_Value(Y))) && !isFreeToInvert(Y, Y->hasOneUse())) {
3442  Value *NotX = Builder.CreateNot(LHS);
3443  return SelectInst::Create(
3444  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y);
3445  }
3446 
3447  // If both sides are freely invertible, then we can get rid of the xor
3448  // completely.
3449  if (isFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) &&
3450  isFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) {
3451  Value *NotLHS = Builder.CreateNot(LHS);
3452  Value *NotRHS = Builder.CreateNot(RHS);
3453  return SelectInst::Create(
3454  Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
3455  NotLHS, NotRHS);
3456  }
3457  }
3458 
3459  // Pull 'not' into operands of select if both operands are one-use compares
3460  // or one is one-use compare and the other one is a constant.
3461  // Inverting the predicates eliminates the 'not' operation.
3462  // Example:
3463  // not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
3464  // select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
3465  // not (select ?, (cmp TPred, ?, ?), true -->
3466  // select ?, (cmp InvTPred, ?, ?), false
3467  if (auto *Sel = dyn_cast<SelectInst>(NotOp)) {
3468  Value *TV = Sel->getTrueValue();
3469  Value *FV = Sel->getFalseValue();
3470  auto *CmpT = dyn_cast<CmpInst>(TV);
3471  auto *CmpF = dyn_cast<CmpInst>(FV);
3472  bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3473  bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3474  if (InvertibleT && InvertibleF) {
3475  if (CmpT)
3476  CmpT->setPredicate(CmpT->getInversePredicate());
3477  else
3478  Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
3479  if (CmpF)
3480  CmpF->setPredicate(CmpF->getInversePredicate());
3481  else
3482  Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
3483  return replaceInstUsesWith(I, Sel);
3484  }
3485  }
3486  }
3487 
3488  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
3489  return NewXor;
3490 
3491  return nullptr;
3492 }
3493 
3494 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
3495 // here. We should standardize that construct where it is needed or choose some
3496 // other way to ensure that commutated variants of patterns are not missed.
3498  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
3499  SQ.getWithInstruction(&I)))
3500  return replaceInstUsesWith(I, V);
3501 
3502  if (SimplifyAssociativeOrCommutative(I))
3503  return &I;
3504 
3505  if (Instruction *X = foldVectorBinop(I))
3506  return X;
3507 
3508  if (Instruction *NewXor = foldXorToXor(I, Builder))
3509  return NewXor;
3510 
3511  // (A&B)^(A&C) -> A&(B^C) etc
3512  if (Value *V = SimplifyUsingDistributiveLaws(I))
3513  return replaceInstUsesWith(I, V);
3514 
3515  // See if we can simplify any instructions used by the instruction whose sole
3516  // purpose is to compute bits we don't care about.
3517  if (SimplifyDemandedInstructionBits(I))
3518  return &I;
3519 
3520  if (Value *V = SimplifyBSwap(I, Builder))
3521  return replaceInstUsesWith(I, V);
3522 
3523  if (Instruction *R = foldNot(I))
3524  return R;
3525 
3526  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
3527  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
3528  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
3529  // have already taken care of those cases.
3530  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3531  Value *M;
3532  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
3533  m_c_And(m_Deferred(M), m_Value()))))
3534  return BinaryOperator::CreateOr(Op0, Op1);
3535 
3537  return Xor;
3538 
3539  // Use DeMorgan and reassociation to eliminate a 'not' op.
3540  Value *X, *Y;
3541  Constant *C1;
3542  if (match(Op1, m_Constant(C1))) {
3543  Constant *C2;
3544  if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
3545  // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
3546  Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2));
3547  return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
3548  }
3549  if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
3550  // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
3551  Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2));
3552  return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
3553  }
3554  }
3555 
3556  Type *Ty = I.getType();
3557  {
3558  const APInt *RHSC;
3559  if (match(Op1, m_APInt(RHSC))) {
3560  Value *X;
3561  const APInt *C;
3562  // (C - X) ^ signmaskC --> (C + signmaskC) - X
3563  if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X))))
3564  return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C + *RHSC), X);
3565 
3566  // (X + C) ^ signmaskC --> X + (C + signmaskC)
3567  if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
3568  return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
3569 
3570  // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
3571  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
3572  MaskedValueIsZero(X, *C, 0, &I))
3573  return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
3574 
3575  // If RHSC is inverting the remaining bits of shifted X,
3576  // canonicalize to a 'not' before the shift to help SCEV and codegen:
3577  // (X << C) ^ RHSC --> ~X << C
3578  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
3579  *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).shl(*C)) {
3580  Value *NotX = Builder.CreateNot(X);
3581  return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
3582  }
3583  // (X >>u C) ^ RHSC --> ~X >>u C
3584  if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
3585  *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).lshr(*C)) {
3586  Value *NotX = Builder.CreateNot(X);
3587  return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
3588  }
3589  // TODO: We could handle 'ashr' here as well. That would be matching
3590  // a 'not' op and moving it before the shift. Doing that requires
3591  // preventing the inverse fold in canShiftBinOpWithConstantRHS().
3592  }
3593  }
3594 
3595  // FIXME: This should not be limited to scalar (pull into APInt match above).
3596  {
3597  Value *X;
3598  ConstantInt *C1, *C2, *C3;
3599  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
3600  if (match(Op1, m_ConstantInt(C3)) &&
3602  m_ConstantInt(C2))) &&
3603  Op0->hasOneUse()) {
3604  // fold (C1 >> C2) ^ C3
3605  APInt FoldConst = C1->getValue().lshr(C2->getValue());
3606  FoldConst ^= C3->getValue();
3607  // Prepare the two operands.
3608  auto *Opnd0 = cast<Instruction>(Builder.CreateLShr(X, C2));
3609  Opnd0->takeName(cast<Instruction>(Op0));
3610  Opnd0->setDebugLoc(I.getDebugLoc());
3611  return BinaryOperator::CreateXor(Opnd0, ConstantInt::get(Ty, FoldConst));
3612  }
3613  }
3614 
3615  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
3616  return FoldedLogic;
3617 
3618  // Y ^ (X | Y) --> X & ~Y
3619  // Y ^ (Y | X) --> X & ~Y
3620  if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
3621  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
3622  // (X | Y) ^ Y --> X & ~Y
3623  // (Y | X) ^ Y --> X & ~Y
3624  if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
3625  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
3626 
3627  // Y ^ (X & Y) --> ~X & Y
3628  // Y ^ (Y & X) --> ~X & Y
3629  if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
3630  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
3631  // (X & Y) ^ Y --> ~X & Y
3632  // (Y & X) ^ Y --> ~X & Y
3633  // Canonical form is (X & C) ^ C; don't touch that.
3634  // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
3635  // be fixed to prefer that (otherwise we get infinite looping).
3636  if (!match(Op1, m_Constant()) &&
3637  match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
3638  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
3639 
3640  Value *A, *B, *C;
3641  // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
3642  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3643  m_OneUse(m_c_Or(m_Deferred(A), m_Value(C))))))
3644  return BinaryOperator::CreateXor(
3645  Builder.CreateAnd(Builder.CreateNot(A), C), B);
3646 
3647  // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
3648  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3650  return BinaryOperator::CreateXor(
3651  Builder.CreateAnd(Builder.CreateNot(B), C), A);
3652 
3653  // (A & B) ^ (A ^ B) -> (A | B)
3654  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
3655  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
3656  return BinaryOperator::CreateOr(A, B);
3657  // (A ^ B) ^ (A & B) -> (A | B)
3658  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
3659  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
3660  return BinaryOperator::CreateOr(A, B);
3661 
3662  // (A & ~B) ^ ~A -> ~(A & B)
3663  // (~B & A) ^ ~A -> ~(A & B)
3664  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
3665  match(Op1, m_Not(m_Specific(A))))
3666  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
3667 
3668  // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
3669  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
3670  return BinaryOperator::CreateOr(A, B);
3671 
3672  // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
3673  // TODO: Loosen one-use restriction if common operand is a constant.
3674  Value *D;
3675  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
3676  match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
3677  if (B == C || B == D)
3678  std::swap(A, B);
3679  if (A == C)
3680  std::swap(C, D);
3681  if (A == D) {
3682  Value *NotA = Builder.CreateNot(A);
3683  return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
3684  }
3685  }
3686 
3687  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
3688  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
3689  if (Value *V = foldXorOfICmps(LHS, RHS, I))
3690  return replaceInstUsesWith(I, V);
3691 
3692  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
3693  return CastedXor;
3694 
3695  if (Instruction *Abs = canonicalizeAbs(I, Builder))
3696  return Abs;
3697 
3698  // Otherwise, if all else failed, try to hoist the xor-by-constant:
3699  // (X ^ C) ^ Y --> (X ^ Y) ^ C
3700  // Just like we do in other places, we completely avoid the fold
3701  // for constantexprs, at least to avoid endless combine loop.
3704  m_ImmConstant(C1))),
3705  m_Value(Y))))
3706  return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
3707 
3708  return nullptr;
3709 }
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:959
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:735
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:836
llvm
This file implements support for optimizing divisions by a constant.
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:741
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:356
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
CmpInstAnalysis.h
llvm::InstCombiner::isFreeToInvert
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:233
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h: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:1379
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
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:3497
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:250
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:2180
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2730
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:700
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1147
llvm::SystemZII::IsLogical
@ IsLogical
Definition: SystemZInstrInfo.h:49
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:1482
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:5269
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
llvm::ConstantInt::isMinValue
bool isMinValue(bool IsSigned) const
This function will return true iff this constant represents the smallest value that may be represente...
Definition: Constants.h:225
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:1008
peekThroughBitcast
static Register peekThroughBitcast(Register Reg, const MachineRegisterInfo &MRI)
Definition: CombinerHelper.cpp:1645
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:728
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:6362
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:1031
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:3076
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
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:2211
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:2164
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:305
getFCmpValue
static Value * getFCmpValue(unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp inst...
Definition: InstCombineAndOrXor.cpp:67
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
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::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:1153
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:380
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
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::ConstantInt::isMaxValue
bool isMaxValue(bool IsSigned) const
This function will return true iff this constant represents the largest value that may be represented...
Definition: Constants.h:213
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:6220
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:2242
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:2280
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
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:1347
llvm::CmpInst::FCMP_OGT
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:724
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:820
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:2315
llvm::CastInst::getDestTy
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:684
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
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:2221
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:734
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:2213
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:2093
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:1769
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:1472
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
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:893
foldLogicCastConstant
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
Fold {and,or,xor} (cast X), C.
Definition: InstCombineAndOrXor.cpp:1565
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:746
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:708
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:3708
llvm::FCmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1369
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::PatternMatch::m_PosZeroFP
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:705
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1518
llvm::CmpInst::FCMP_UGE
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:733
IntPart::NumBits
unsigned NumBits
Definition: InstCombineAndOrXor.cpp:1078
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:1639
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:2228
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:1892
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:393
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:730
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::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:2249
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:990
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:1194
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:723
llvm::CmpInst::FCMP_OLT
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:726
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:682
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:2979
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:1781
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:722
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:1135
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:864
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:1670
matchFunnelShift
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
Definition: InstCombineAndOrXor.cpp:2109
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
IntPart::From
Value * From
Definition: InstCombineAndOrXor.cpp:1076
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:781
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:2522
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:5351
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1129
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:3141
llvm::ConstantExpr::getOr
static Constant * getOr(Constant *C1, Constant *C2)
Definition: Constants.cpp:2753
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:1123
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:276
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:213
sinkNotIntoXor
static Instruction * sinkNotIntoXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:3180
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:1020
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:725
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
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:1077
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:4792
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::InstCombinerImpl::visitOr
Instruction * visitOr(BinaryOperator &I)
Definition: InstCombineAndOrXor.cpp:2627
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1633
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:885
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:189
llvm::PatternMatch::m_SpecificInt_ICMP
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:626
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
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:3202
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:430
llvm::getInverseMinMaxPred
CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF)
Return the canonical inverse comparison predicate for the specified minimum/maximum flavor.
Definition: ValueTracking.cpp:6308
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:4831
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
foldOrToXor
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineAndOrXor.cpp:1696
matchIntPart
static Optional< IntPart > matchIntPart(Value *V)
Match an extraction of bits from an integer.
Definition: InstCombineAndOrXor.cpp:1082
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:1159
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:732
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:940
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:3238
llvm::getPredForICmpCode