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