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 ((Cast0->hasOneUse() || Cast1->hasOneUse()) &&
1435  shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1436  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1437  I.getName());
1438  return CastInst::Create(CastOpcode, NewOp, DestTy);
1439  }
1440 
1441  // For now, only 'and'/'or' have optimizations after this.
1442  if (LogicOpc == Instruction::Xor)
1443  return nullptr;
1444 
1445  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1446  // cast is otherwise not optimizable. This happens for vector sexts.
1447  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1448  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1449  if (ICmp0 && ICmp1) {
1450  if (Value *Res =
1451  foldAndOrOfICmps(ICmp0, ICmp1, I, LogicOpc == Instruction::And))
1452  return CastInst::Create(CastOpcode, Res, DestTy);
1453  return nullptr;
1454  }
1455 
1456  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1457  // cast is otherwise not optimizable. This happens for vector sexts.
1458  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1459  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1460  if (FCmp0 && FCmp1)
1461  if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1462  return CastInst::Create(CastOpcode, R, DestTy);
1463 
1464  return nullptr;
1465 }
1466 
1469  assert(I.getOpcode() == Instruction::And);
1470  Value *Op0 = I.getOperand(0);
1471  Value *Op1 = I.getOperand(1);
1472  Value *A, *B;
1473 
1474  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1475  // (A | B) & ~(A & B) --> A ^ B
1476  // (A | B) & ~(B & A) --> A ^ B
1477  if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1478  m_Not(m_c_And(m_Deferred(A), m_Deferred(B))))))
1479  return BinaryOperator::CreateXor(A, B);
1480 
1481  // (A | ~B) & (~A | B) --> ~(A ^ B)
1482  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1483  // (~B | A) & (~A | B) --> ~(A ^ B)
1484  // (~B | A) & (B | ~A) --> ~(A ^ B)
1485  if (Op0->hasOneUse() || Op1->hasOneUse())
1486  if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))),
1487  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
1488  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1489 
1490  return nullptr;
1491 }
1492 
1495  assert(I.getOpcode() == Instruction::Or);
1496  Value *Op0 = I.getOperand(0);
1497  Value *Op1 = I.getOperand(1);
1498  Value *A, *B;
1499 
1500  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1501  // (A & B) | ~(A | B) --> ~(A ^ B)
1502  // (A & B) | ~(B | A) --> ~(A ^ B)
1503  if (Op0->hasOneUse() || Op1->hasOneUse())
1504  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1505  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1506  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1507 
1508  // Operand complexity canonicalization guarantees that the 'xor' is Op0.
1509  // (A ^ B) | ~(A | B) --> ~(A & B)
1510  // (A ^ B) | ~(B | A) --> ~(A & B)
1511  if (Op0->hasOneUse() || Op1->hasOneUse())
1512  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1513  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1514  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
1515 
1516  // (A & ~B) | (~A & B) --> A ^ B
1517  // (A & ~B) | (B & ~A) --> A ^ B
1518  // (~B & A) | (~A & B) --> A ^ B
1519  // (~B & A) | (B & ~A) --> A ^ B
1520  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1521  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1522  return BinaryOperator::CreateXor(A, B);
1523 
1524  return nullptr;
1525 }
1526 
1527 /// Return true if a constant shift amount is always less than the specified
1528 /// bit-width. If not, the shift could create poison in the narrower type.
1529 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1530  APInt Threshold(C->getType()->getScalarSizeInBits(), BitWidth);
1531  return match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold));
1532 }
1533 
1534 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1535 /// a common zext operand: and (binop (zext X), C), (zext X).
1536 Instruction *InstCombinerImpl::narrowMaskedBinOp(BinaryOperator &And) {
1537  // This transform could also apply to {or, and, xor}, but there are better
1538  // folds for those cases, so we don't expect those patterns here. AShr is not
1539  // handled because it should always be transformed to LShr in this sequence.
1540  // The subtract transform is different because it has a constant on the left.
1541  // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1542  Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1543  Constant *C;
1544  if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1545  !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1546  !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1547  !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1548  !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1549  return nullptr;
1550 
1551  Value *X;
1552  if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1553  return nullptr;
1554 
1555  Type *Ty = And.getType();
1556  if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1557  return nullptr;
1558 
1559  // If we're narrowing a shift, the shift amount must be safe (less than the
1560  // width) in the narrower type. If the shift amount is greater, instsimplify
1561  // usually handles that case, but we can't guarantee/assert it.
1562  Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1563  if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1564  if (!canNarrowShiftAmt(C, X->getType()->getScalarSizeInBits()))
1565  return nullptr;
1566 
1567  // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1568  // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1569  Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1570  Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1571  : Builder.CreateBinOp(Opc, X, NewC);
1572  return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1573 }
1574 
1575 /// Try folding relatively complex patterns for both And and Or operations
1576 /// with all And and Or swapped.
1579  const Instruction::BinaryOps Opcode = I.getOpcode();
1580  assert(Opcode == Instruction::And || Opcode == Instruction::Or);
1581 
1582  // Flip the logic operation.
1583  const Instruction::BinaryOps FlippedOpcode =
1584  (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1585 
1586  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1587  Value *A, *B, *C, *X, *Y, *Dummy;
1588 
1589  // Match following expressions:
1590  // (~(A | B) & C)
1591  // (~(A & B) | C)
1592  // Captures X = ~(A | B) or ~(A & B)
1593  const auto matchNotOrAnd =
1594  [Opcode, FlippedOpcode](Value *Op, auto m_A, auto m_B, auto m_C,
1595  Value *&X, bool CountUses = false) -> bool {
1596  if (CountUses && !Op->hasOneUse())
1597  return false;
1598 
1599  if (match(Op, m_c_BinOp(FlippedOpcode,
1601  m_Not(m_c_BinOp(Opcode, m_A, m_B))),
1602  m_C)))
1603  return !CountUses || X->hasOneUse();
1604 
1605  return false;
1606  };
1607 
1608  // (~(A | B) & C) | ... --> ...
1609  // (~(A & B) | C) & ... --> ...
1610  // TODO: One use checks are conservative. We just need to check that a total
1611  // number of multiple used values does not exceed reduction
1612  // in operations.
1613  if (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X)) {
1614  // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
1615  // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
1616  if (matchNotOrAnd(Op1, m_Specific(A), m_Specific(C), m_Specific(B), Dummy,
1617  true)) {
1618  Value *Xor = Builder.CreateXor(B, C);
1619  return (Opcode == Instruction::Or)
1620  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
1621  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, A));
1622  }
1623 
1624  // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
1625  // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)
1626  if (matchNotOrAnd(Op1, m_Specific(B), m_Specific(C), m_Specific(A), Dummy,
1627  true)) {
1628  Value *Xor = Builder.CreateXor(A, C);
1629  return (Opcode == Instruction::Or)
1630  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(B))
1631  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, B));
1632  }
1633 
1634  // (~(A | B) & C) | ~(A | C) --> ~((B & C) | A)
1635  // (~(A & B) | C) & ~(A & C) --> ~((B | C) & A)
1636  if (match(Op1, m_OneUse(m_Not(m_OneUse(
1637  m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
1638  return BinaryOperator::CreateNot(Builder.CreateBinOp(
1639  Opcode, Builder.CreateBinOp(FlippedOpcode, B, C), A));
1640 
1641  // (~(A | B) & C) | ~(B | C) --> ~((A & C) | B)
1642  // (~(A & B) | C) & ~(B & C) --> ~((A | C) & B)
1643  if (match(Op1, m_OneUse(m_Not(m_OneUse(
1644  m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)))))))
1645  return BinaryOperator::CreateNot(Builder.CreateBinOp(
1646  Opcode, Builder.CreateBinOp(FlippedOpcode, A, C), B));
1647 
1648  // (~(A | B) & C) | ~(C | (A ^ B)) --> ~((A | B) & (C | (A ^ B)))
1649  // Note, the pattern with swapped and/or is not handled because the
1650  // result is more undefined than a source:
1651  // (~(A & B) | C) & ~(C & (A ^ B)) --> (A ^ B ^ C) | ~(A | C) is invalid.
1652  if (Opcode == Instruction::Or && Op0->hasOneUse() &&
1654  m_Value(Y),
1655  m_c_BinOp(Opcode, m_Specific(C),
1656  m_c_Xor(m_Specific(A), m_Specific(B)))))))) {
1657  // X = ~(A | B)
1658  // Y = (C | (A ^ B)
1659  Value *Or = cast<BinaryOperator>(X)->getOperand(0);
1660  return BinaryOperator::CreateNot(Builder.CreateAnd(Or, Y));
1661  }
1662  }
1663 
1664  // (~A & B & C) | ... --> ...
1665  // (~A | B | C) | ... --> ...
1666  // TODO: One use checks are conservative. We just need to check that a total
1667  // number of multiple used values does not exceed reduction
1668  // in operations.
1669  if (match(Op0,
1670  m_OneUse(m_c_BinOp(FlippedOpcode,
1671  m_BinOp(FlippedOpcode, m_Value(B), m_Value(C)),
1672  m_CombineAnd(m_Value(X), m_Not(m_Value(A)))))) ||
1673  match(Op0, m_OneUse(m_c_BinOp(
1674  FlippedOpcode,
1675  m_c_BinOp(FlippedOpcode, m_Value(C),
1677  m_Value(B))))) {
1678  // X = ~A
1679  // (~A & B & C) | ~(A | B | C) --> ~(A | (B ^ C))
1680  // (~A | B | C) & ~(A & B & C) --> (~A | (B ^ C))
1681  if (match(Op1, m_OneUse(m_Not(m_c_BinOp(
1682  Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)),
1683  m_Specific(C))))) ||
1685  Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
1686  m_Specific(A))))) ||
1688  Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
1689  m_Specific(B)))))) {
1690  Value *Xor = Builder.CreateXor(B, C);
1691  return (Opcode == Instruction::Or)
1692  ? BinaryOperator::CreateNot(Builder.CreateOr(Xor, A))
1693  : BinaryOperator::CreateOr(Xor, X);
1694  }
1695 
1696  // (~A & B & C) | ~(A | B) --> (C | ~B) & ~A
1697  // (~A | B | C) & ~(A & B) --> (C & ~B) | ~A
1698  if (match(Op1, m_OneUse(m_Not(m_OneUse(
1699  m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)))))))
1700  return BinaryOperator::Create(
1701  FlippedOpcode, Builder.CreateBinOp(Opcode, C, Builder.CreateNot(B)),
1702  X);
1703 
1704  // (~A & B & C) | ~(A | C) --> (B | ~C) & ~A
1705  // (~A | B | C) & ~(A & C) --> (B & ~C) | ~A
1706  if (match(Op1, m_OneUse(m_Not(m_OneUse(
1707  m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
1708  return BinaryOperator::Create(
1709  FlippedOpcode, Builder.CreateBinOp(Opcode, B, Builder.CreateNot(C)),
1710  X);
1711  }
1712 
1713  return nullptr;
1714 }
1715 
1716 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1717 // here. We should standardize that construct where it is needed or choose some
1718 // other way to ensure that commutated variants of patterns are not missed.
1720  Type *Ty = I.getType();
1721 
1722  if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1),
1723  SQ.getWithInstruction(&I)))
1724  return replaceInstUsesWith(I, V);
1725 
1726  if (SimplifyAssociativeOrCommutative(I))
1727  return &I;
1728 
1729  if (Instruction *X = foldVectorBinop(I))
1730  return X;
1731 
1732  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1733  return Phi;
1734 
1735  // See if we can simplify any instructions used by the instruction whose sole
1736  // purpose is to compute bits we don't care about.
1737  if (SimplifyDemandedInstructionBits(I))
1738  return &I;
1739 
1740  // Do this before using distributive laws to catch simple and/or/not patterns.
1742  return Xor;
1743 
1745  return X;
1746 
1747  // (A|B)&(A|C) -> A|(B&C) etc
1748  if (Value *V = SimplifyUsingDistributiveLaws(I))
1749  return replaceInstUsesWith(I, V);
1750 
1751  if (Value *V = SimplifyBSwap(I, Builder))
1752  return replaceInstUsesWith(I, V);
1753 
1754  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1755 
1756  Value *X, *Y;
1757  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) &&
1758  match(Op1, m_One())) {
1759  // (1 << X) & 1 --> zext(X == 0)
1760  // (1 >> X) & 1 --> zext(X == 0)
1761  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, 0));
1762  return new ZExtInst(IsZero, Ty);
1763  }
1764 
1765  const APInt *C;
1766  if (match(Op1, m_APInt(C))) {
1767  const APInt *XorC;
1768  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
1769  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1770  Constant *NewC = ConstantInt::get(Ty, *C & *XorC);
1771  Value *And = Builder.CreateAnd(X, Op1);
1772  And->takeName(Op0);
1773  return BinaryOperator::CreateXor(And, NewC);
1774  }
1775 
1776  const APInt *OrC;
1777  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
1778  // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
1779  // NOTE: This reduces the number of bits set in the & mask, which
1780  // can expose opportunities for store narrowing for scalars.
1781  // NOTE: SimplifyDemandedBits should have already removed bits from C1
1782  // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
1783  // above, but this feels safer.
1784  APInt Together = *C & *OrC;
1785  Value *And = Builder.CreateAnd(X, ConstantInt::get(Ty, Together ^ *C));
1786  And->takeName(Op0);
1787  return BinaryOperator::CreateOr(And, ConstantInt::get(Ty, Together));
1788  }
1789 
1790  // If the mask is only needed on one incoming arm, push the 'and' op up.
1791  if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
1792  match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
1793  APInt NotAndMask(~(*C));
1794  BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
1795  if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
1796  // Not masking anything out for the LHS, move mask to RHS.
1797  // and ({x}or X, Y), C --> {x}or X, (and Y, C)
1798  Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
1799  return BinaryOperator::Create(BinOp, X, NewRHS);
1800  }
1801  if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
1802  // Not masking anything out for the RHS, move mask to LHS.
1803  // and ({x}or X, Y), C --> {x}or (and X, C), Y
1804  Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
1805  return BinaryOperator::Create(BinOp, NewLHS, Y);
1806  }
1807  }
1808 
1809  unsigned Width = Ty->getScalarSizeInBits();
1810  const APInt *ShiftC;
1811  if (match(Op0, m_OneUse(m_SExt(m_AShr(m_Value(X), m_APInt(ShiftC)))))) {
1812  if (*C == APInt::getLowBitsSet(Width, Width - ShiftC->getZExtValue())) {
1813  // We are clearing high bits that were potentially set by sext+ashr:
1814  // and (sext (ashr X, ShiftC)), C --> lshr (sext X), ShiftC
1815  Value *Sext = Builder.CreateSExt(X, Ty);
1816  Constant *ShAmtC = ConstantInt::get(Ty, ShiftC->zext(Width));
1817  return BinaryOperator::CreateLShr(Sext, ShAmtC);
1818  }
1819  }
1820 
1821  // If this 'and' clears the sign-bits added by ashr, replace with lshr:
1822  // and (ashr X, ShiftC), C --> lshr X, ShiftC
1823  if (match(Op0, m_AShr(m_Value(X), m_APInt(ShiftC))) && ShiftC->ult(Width) &&
1824  C->isMask(Width - ShiftC->getZExtValue()))
1825  return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, *ShiftC));
1826 
1827  const APInt *AddC;
1828  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC)))) {
1829  // If we add zeros to every bit below a mask, the add has no effect:
1830  // (X + AddC) & LowMaskC --> X & LowMaskC
1831  unsigned Ctlz = C->countLeadingZeros();
1832  APInt LowMask(APInt::getLowBitsSet(Width, Width - Ctlz));
1833  if ((*AddC & LowMask).isZero())
1834  return BinaryOperator::CreateAnd(X, Op1);
1835 
1836  // If we are masking the result of the add down to exactly one bit and
1837  // the constant we are adding has no bits set below that bit, then the
1838  // add is flipping a single bit. Example:
1839  // (X + 4) & 4 --> (X & 4) ^ 4
1840  if (Op0->hasOneUse() && C->isPowerOf2() && (*AddC & (*C - 1)) == 0) {
1841  assert((*C & *AddC) != 0 && "Expected common bit");
1842  Value *NewAnd = Builder.CreateAnd(X, Op1);
1843  return BinaryOperator::CreateXor(NewAnd, Op1);
1844  }
1845  }
1846 
1847  // ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if C2 fits in the
1848  // bitwidth of X and OP behaves well when given trunc(C1) and X.
1849  auto isSuitableBinOpcode = [](BinaryOperator *B) {
1850  switch (B->getOpcode()) {
1851  case Instruction::Xor:
1852  case Instruction::Or:
1853  case Instruction::Mul:
1854  case Instruction::Add:
1855  case Instruction::Sub:
1856  return true;
1857  default:
1858  return false;
1859  }
1860  };
1861  BinaryOperator *BO;
1862  if (match(Op0, m_OneUse(m_BinOp(BO))) && isSuitableBinOpcode(BO)) {
1863  Value *X;
1864  const APInt *C1;
1865  // TODO: The one-use restrictions could be relaxed a little if the AND
1866  // is going to be removed.
1867  if (match(BO, m_c_BinOp(m_OneUse(m_ZExt(m_Value(X))), m_APInt(C1))) &&
1868  C->isIntN(X->getType()->getScalarSizeInBits())) {
1869  unsigned XWidth = X->getType()->getScalarSizeInBits();
1870  Constant *TruncC1 = ConstantInt::get(X->getType(), C1->trunc(XWidth));
1871  Value *BinOp = isa<ZExtInst>(BO->getOperand(0))
1872  ? Builder.CreateBinOp(BO->getOpcode(), X, TruncC1)
1873  : Builder.CreateBinOp(BO->getOpcode(), TruncC1, X);
1874  Constant *TruncC = ConstantInt::get(X->getType(), C->trunc(XWidth));
1875  Value *And = Builder.CreateAnd(BinOp, TruncC);
1876  return new ZExtInst(And, Ty);
1877  }
1878  }
1879  }
1880 
1882  m_SignMask())) &&
1884  ICmpInst::Predicate::ICMP_EQ,
1885  APInt(Ty->getScalarSizeInBits(),
1886  Ty->getScalarSizeInBits() -
1887  X->getType()->getScalarSizeInBits())))) {
1888  auto *SExt = Builder.CreateSExt(X, Ty, X->getName() + ".signext");
1889  auto *SanitizedSignMask = cast<Constant>(Op1);
1890  // We must be careful with the undef elements of the sign bit mask, however:
1891  // the mask elt can be undef iff the shift amount for that lane was undef,
1892  // otherwise we need to sanitize undef masks to zero.
1893  SanitizedSignMask = Constant::replaceUndefsWith(
1894  SanitizedSignMask, ConstantInt::getNullValue(Ty->getScalarType()));
1895  SanitizedSignMask =
1896  Constant::mergeUndefsWith(SanitizedSignMask, cast<Constant>(Y));
1897  return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
1898  }
1899 
1900  if (Instruction *Z = narrowMaskedBinOp(I))
1901  return Z;
1902 
1903  if (I.getType()->isIntOrIntVectorTy(1)) {
1904  if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
1905  if (auto *I =
1906  foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ true))
1907  return I;
1908  }
1909  if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
1910  if (auto *I =
1911  foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ true))
1912  return I;
1913  }
1914  }
1915 
1916  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
1917  return FoldedLogic;
1918 
1919  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1920  return DeMorgan;
1921 
1922  {
1923  Value *A, *B, *C;
1924  // A & (A ^ B) --> A & ~B
1925  if (match(Op1, m_OneUse(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1926  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(B));
1927  // (A ^ B) & A --> A & ~B
1928  if (match(Op0, m_OneUse(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1929  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(B));
1930 
1931  // A & ~(A ^ B) --> A & B
1932  if (match(Op1, m_Not(m_c_Xor(m_Specific(Op0), m_Value(B)))))
1933  return BinaryOperator::CreateAnd(Op0, B);
1934  // ~(A ^ B) & A --> A & B
1935  if (match(Op0, m_Not(m_c_Xor(m_Specific(Op1), m_Value(B)))))
1936  return BinaryOperator::CreateAnd(Op1, B);
1937 
1938  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1939  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1940  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1941  if (Op1->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1942  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1943 
1944  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1945  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1946  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1947  if (Op0->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
1948  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1949 
1950  // (A | B) & (~A ^ B) -> A & B
1951  // (A | B) & (B ^ ~A) -> A & B
1952  // (B | A) & (~A ^ B) -> A & B
1953  // (B | A) & (B ^ ~A) -> A & B
1954  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1955  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1956  return BinaryOperator::CreateAnd(A, B);
1957 
1958  // (~A ^ B) & (A | B) -> A & B
1959  // (~A ^ B) & (B | A) -> A & B
1960  // (B ^ ~A) & (A | B) -> A & B
1961  // (B ^ ~A) & (B | A) -> A & B
1962  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1963  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1964  return BinaryOperator::CreateAnd(A, B);
1965 
1966  // (~A | B) & (A ^ B) -> ~A & B
1967  // (~A | B) & (B ^ A) -> ~A & B
1968  // (B | ~A) & (A ^ B) -> ~A & B
1969  // (B | ~A) & (B ^ A) -> ~A & B
1970  if (match(Op0, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
1971  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
1972  return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
1973 
1974  // (A ^ B) & (~A | B) -> ~A & B
1975  // (B ^ A) & (~A | B) -> ~A & B
1976  // (A ^ B) & (B | ~A) -> ~A & B
1977  // (B ^ A) & (B | ~A) -> ~A & B
1978  if (match(Op1, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
1979  match(Op0, m_c_Xor(m_Specific(A), m_Specific(B))))
1980  return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
1981  }
1982 
1983  {
1984  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1985  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1986  if (LHS && RHS)
1987  if (Value *Res = foldAndOrOfICmps(LHS, RHS, I, /* IsAnd */ true))
1988  return replaceInstUsesWith(I, Res);
1989 
1990  // TODO: Make this recursive; it's a little tricky because an arbitrary
1991  // number of 'and' instructions might have to be created.
1992  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1993  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1994  if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ true))
1995  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1996  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1997  if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ true))
1998  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1999  }
2000  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
2001  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2002  if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ true))
2003  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
2004  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2005  if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ true))
2006  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
2007  }
2008  }
2009 
2010  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2011  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2012  if (Value *Res = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true))
2013  return replaceInstUsesWith(I, Res);
2014 
2015  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2016  return FoldedFCmps;
2017 
2018  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
2019  return CastedAnd;
2020 
2021  if (Instruction *Sel = foldBinopOfSextBoolToSelect(I))
2022  return Sel;
2023 
2024  // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
2025  // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold
2026  // with binop identity constant. But creating a select with non-constant
2027  // arm may not be reversible due to poison semantics. Is that a good
2028  // canonicalization?
2029  Value *A;
2030  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2031  A->getType()->isIntOrIntVectorTy(1))
2032  return SelectInst::Create(A, Op1, Constant::getNullValue(Ty));
2033  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2034  A->getType()->isIntOrIntVectorTy(1))
2035  return SelectInst::Create(A, Op0, Constant::getNullValue(Ty));
2036 
2037  // (iN X s>> (N-1)) & Y --> (X s< 0) ? Y : 0
2038  unsigned FullShift = Ty->getScalarSizeInBits() - 1;
2039  if (match(&I, m_c_And(m_OneUse(m_AShr(m_Value(X), m_SpecificInt(FullShift))),
2040  m_Value(Y)))) {
2041  Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
2042  return SelectInst::Create(IsNeg, Y, ConstantInt::getNullValue(Ty));
2043  }
2044  // If there's a 'not' of the shifted value, swap the select operands:
2045  // ~(iN X s>> (N-1)) & Y --> (X s< 0) ? 0 : Y
2046  if (match(&I, m_c_And(m_OneUse(m_Not(
2047  m_AShr(m_Value(X), m_SpecificInt(FullShift)))),
2048  m_Value(Y)))) {
2049  Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
2050  return SelectInst::Create(IsNeg, ConstantInt::getNullValue(Ty), Y);
2051  }
2052 
2053  // (~x) & y --> ~(x | (~y)) iff that gets rid of inversions
2054  if (sinkNotIntoOtherHandOfAndOrOr(I))
2055  return &I;
2056 
2057  // An and recurrence w/loop invariant step is equivelent to (and start, step)
2058  PHINode *PN = nullptr;
2059  Value *Start = nullptr, *Step = nullptr;
2060  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2061  return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
2062 
2063  return nullptr;
2064 }
2065 
2067  bool MatchBSwaps,
2068  bool MatchBitReversals) {
2070  if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
2071  Insts))
2072  return nullptr;
2073  Instruction *LastInst = Insts.pop_back_val();
2074  LastInst->removeFromParent();
2075 
2076  for (auto *Inst : Insts)
2077  Worklist.push(Inst);
2078  return LastInst;
2079 }
2080 
2081 /// Match UB-safe variants of the funnel shift intrinsic.
2083  // TODO: Can we reduce the code duplication between this and the related
2084  // rotate matching code under visitSelect and visitTrunc?
2085  unsigned Width = Or.getType()->getScalarSizeInBits();
2086 
2087  // First, find an or'd pair of opposite shifts:
2088  // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
2089  BinaryOperator *Or0, *Or1;
2090  if (!match(Or.getOperand(0), m_BinOp(Or0)) ||
2091  !match(Or.getOperand(1), m_BinOp(Or1)))
2092  return nullptr;
2093 
2094  Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2095  if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
2096  !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
2097  Or0->getOpcode() == Or1->getOpcode())
2098  return nullptr;
2099 
2100  // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
2101  if (Or0->getOpcode() == BinaryOperator::LShr) {
2102  std::swap(Or0, Or1);
2103  std::swap(ShVal0, ShVal1);
2104  std::swap(ShAmt0, ShAmt1);
2105  }
2106  assert(Or0->getOpcode() == BinaryOperator::Shl &&
2107  Or1->getOpcode() == BinaryOperator::LShr &&
2108  "Illegal or(shift,shift) pair");
2109 
2110  // Match the shift amount operands for a funnel shift pattern. This always
2111  // matches a subtraction on the R operand.
2112  auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
2113  // Check for constant shift amounts that sum to the bitwidth.
2114  const APInt *LI, *RI;
2115  if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
2116  if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
2117  return ConstantInt::get(L->getType(), *LI);
2118 
2119  Constant *LC, *RC;
2120  if (match(L, m_Constant(LC)) && match(R, m_Constant(RC)) &&
2124  return ConstantExpr::mergeUndefsWith(LC, RC);
2125 
2126  // (shl ShVal, X) | (lshr ShVal, (Width - x)) iff X < Width.
2127  // We limit this to X < Width in case the backend re-expands the intrinsic,
2128  // and has to reintroduce a shift modulo operation (InstCombine might remove
2129  // it after this fold). This still doesn't guarantee that the final codegen
2130  // will match this original pattern.
2131  if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) {
2132  KnownBits KnownL = IC.computeKnownBits(L, /*Depth*/ 0, &Or);
2133  return KnownL.getMaxValue().ult(Width) ? L : nullptr;
2134  }
2135 
2136  // For non-constant cases, the following patterns currently only work for
2137  // rotation patterns.
2138  // TODO: Add general funnel-shift compatible patterns.
2139  if (ShVal0 != ShVal1)
2140  return nullptr;
2141 
2142  // For non-constant cases we don't support non-pow2 shift masks.
2143  // TODO: Is it worth matching urem as well?
2144  if (!isPowerOf2_32(Width))
2145  return nullptr;
2146 
2147  // The shift amount may be masked with negation:
2148  // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
2149  Value *X;
2150  unsigned Mask = Width - 1;
2151  if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
2153  return X;
2154 
2155  // Similar to above, but the shift amount may be extended after masking,
2156  // so return the extended value as the parameter for the intrinsic.
2157  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2159  m_SpecificInt(Mask))))
2160  return L;
2161 
2162  if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2164  return L;
2165 
2166  return nullptr;
2167  };
2168 
2169  Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);
2170  bool IsFshl = true; // Sub on LSHR.
2171  if (!ShAmt) {
2172  ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);
2173  IsFshl = false; // Sub on SHL.
2174  }
2175  if (!ShAmt)
2176  return nullptr;
2177 
2178  Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2179  Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
2180  return CallInst::Create(F, {ShVal0, ShVal1, ShAmt});
2181 }
2182 
2183 /// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
2186  assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
2187  Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
2188  Type *Ty = Or.getType();
2189 
2190  unsigned Width = Ty->getScalarSizeInBits();
2191  if ((Width & 1) != 0)
2192  return nullptr;
2193  unsigned HalfWidth = Width / 2;
2194 
2195  // Canonicalize zext (lower half) to LHS.
2196  if (!isa<ZExtInst>(Op0))
2197  std::swap(Op0, Op1);
2198 
2199  // Find lower/upper half.
2200  Value *LowerSrc, *ShlVal, *UpperSrc;
2201  const APInt *C;
2202  if (!match(Op0, m_OneUse(m_ZExt(m_Value(LowerSrc)))) ||
2203  !match(Op1, m_OneUse(m_Shl(m_Value(ShlVal), m_APInt(C)))) ||
2204  !match(ShlVal, m_OneUse(m_ZExt(m_Value(UpperSrc)))))
2205  return nullptr;
2206  if (*C != HalfWidth || LowerSrc->getType() != UpperSrc->getType() ||
2207  LowerSrc->getType()->getScalarSizeInBits() != HalfWidth)
2208  return nullptr;
2209 
2210  auto ConcatIntrinsicCalls = [&](Intrinsic::ID id, Value *Lo, Value *Hi) {
2211  Value *NewLower = Builder.CreateZExt(Lo, Ty);
2212  Value *NewUpper = Builder.CreateZExt(Hi, Ty);
2213  NewUpper = Builder.CreateShl(NewUpper, HalfWidth);
2214  Value *BinOp = Builder.CreateOr(NewLower, NewUpper);
2215  Function *F = Intrinsic::getDeclaration(Or.getModule(), id, Ty);
2216  return Builder.CreateCall(F, BinOp);
2217  };
2218 
2219  // BSWAP: Push the concat down, swapping the lower/upper sources.
2220  // concat(bswap(x),bswap(y)) -> bswap(concat(x,y))
2221  Value *LowerBSwap, *UpperBSwap;
2222  if (match(LowerSrc, m_BSwap(m_Value(LowerBSwap))) &&
2223  match(UpperSrc, m_BSwap(m_Value(UpperBSwap))))
2224  return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2225 
2226  // BITREVERSE: Push the concat down, swapping the lower/upper sources.
2227  // concat(bitreverse(x),bitreverse(y)) -> bitreverse(concat(x,y))
2228  Value *LowerBRev, *UpperBRev;
2229  if (match(LowerSrc, m_BitReverse(m_Value(LowerBRev))) &&
2230  match(UpperSrc, m_BitReverse(m_Value(UpperBRev))))
2231  return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2232 
2233  return nullptr;
2234 }
2235 
2236 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
2238  unsigned NumElts = cast<FixedVectorType>(C1->getType())->getNumElements();
2239  for (unsigned i = 0; i != NumElts; ++i) {
2240  Constant *EltC1 = C1->getAggregateElement(i);
2241  Constant *EltC2 = C2->getAggregateElement(i);
2242  if (!EltC1 || !EltC2)
2243  return false;
2244 
2245  // One element must be all ones, and the other must be all zeros.
2246  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
2247  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
2248  return false;
2249  }
2250  return true;
2251 }
2252 
2253 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
2254 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
2255 /// B, it can be used as the condition operand of a select instruction.
2256 Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) {
2257  // We may have peeked through bitcasts in the caller.
2258  // Exit immediately if we don't have (vector) integer types.
2259  Type *Ty = A->getType();
2260  if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
2261  return nullptr;
2262 
2263  // If A is the 'not' operand of B and has enough signbits, we have our answer.
2264  if (match(B, m_Not(m_Specific(A)))) {
2265  // If these are scalars or vectors of i1, A can be used directly.
2266  if (Ty->isIntOrIntVectorTy(1))
2267  return A;
2268 
2269  // If we look through a vector bitcast, the caller will bitcast the operands
2270  // to match the condition's number of bits (N x i1).
2271  // To make this poison-safe, disallow bitcast from wide element to narrow
2272  // element. That could allow poison in lanes where it was not present in the
2273  // original code.
2274  A = peekThroughBitcast(A);
2275  if (A->getType()->isIntOrIntVectorTy()) {
2276  unsigned NumSignBits = ComputeNumSignBits(A);
2277  if (NumSignBits == A->getType()->getScalarSizeInBits() &&
2278  NumSignBits <= Ty->getScalarSizeInBits())
2279  return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(A->getType()));
2280  }
2281  return nullptr;
2282  }
2283 
2284  // If both operands are constants, see if the constants are inverse bitmasks.
2285  Constant *AConst, *BConst;
2286  if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
2287  if (AConst == ConstantExpr::getNot(BConst) &&
2289  return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty));
2290 
2291  // Look for more complex patterns. The 'not' op may be hidden behind various
2292  // casts. Look through sexts and bitcasts to find the booleans.
2293  Value *Cond;
2294  Value *NotB;
2295  if (match(A, m_SExt(m_Value(Cond))) &&
2296  Cond->getType()->isIntOrIntVectorTy(1)) {
2297  // A = sext i1 Cond; B = sext (not (i1 Cond))
2298  if (match(B, m_SExt(m_Not(m_Specific(Cond)))))
2299  return Cond;
2300 
2301  // A = sext i1 Cond; B = not ({bitcast} (sext (i1 Cond)))
2302  // TODO: The one-use checks are unnecessary or misplaced. If the caller
2303  // checked for uses on logic ops/casts, that should be enough to
2304  // make this transform worthwhile.
2305  if (match(B, m_OneUse(m_Not(m_Value(NotB))))) {
2306  NotB = peekThroughBitcast(NotB, true);
2307  if (match(NotB, m_SExt(m_Specific(Cond))))
2308  return Cond;
2309  }
2310  }
2311 
2312  // All scalar (and most vector) possibilities should be handled now.
2313  // Try more matches that only apply to non-splat constant vectors.
2314  if (!Ty->isVectorTy())
2315  return nullptr;
2316 
2317  // If both operands are xor'd with constants using the same sexted boolean
2318  // operand, see if the constants are inverse bitmasks.
2319  // TODO: Use ConstantExpr::getNot()?
2320  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
2321  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) &&
2322  Cond->getType()->isIntOrIntVectorTy(1) &&
2323  areInverseVectorBitmasks(AConst, BConst)) {
2324  AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty));
2325  return Builder.CreateXor(Cond, AConst);
2326  }
2327  return nullptr;
2328 }
2329 
2330 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
2331 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
2332 Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
2333  Value *D) {
2334  // The potential condition of the select may be bitcasted. In that case, look
2335  // through its bitcast and the corresponding bitcast of the 'not' condition.
2336  Type *OrigType = A->getType();
2337  A = peekThroughBitcast(A, true);
2338  B = peekThroughBitcast(B, true);
2339  if (Value *Cond = getSelectCondition(A, B)) {
2340  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
2341  // If this is a vector, we may need to cast to match the condition's length.
2342  // The bitcasts will either all exist or all not exist. The builder will
2343  // not create unnecessary casts if the types already match.
2344  Type *SelTy = A->getType();
2345  if (auto *VecTy = dyn_cast<VectorType>(Cond->getType())) {
2346  // For a fixed or scalable vector get N from <{vscale x} N x iM>
2347  unsigned Elts = VecTy->getElementCount().getKnownMinValue();
2348  // For a fixed or scalable vector, get the size in bits of N x iM; for a
2349  // scalar this is just M.
2350  unsigned SelEltSize = SelTy->getPrimitiveSizeInBits().getKnownMinSize();
2351  Type *EltTy = Builder.getIntNTy(SelEltSize / Elts);
2352  SelTy = VectorType::get(EltTy, VecTy->getElementCount());
2353  }
2354  Value *BitcastC = Builder.CreateBitCast(C, SelTy);
2355  Value *BitcastD = Builder.CreateBitCast(D, SelTy);
2356  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
2357  return Builder.CreateBitCast(Select, OrigType);
2358  }
2359 
2360  return nullptr;
2361 }
2362 
2363 // (icmp eq X, 0) | (icmp ult Other, X) -> (icmp ule Other, X-1)
2364 // (icmp ne X, 0) & (icmp uge Other, X) -> (icmp ugt Other, X-1)
2367  ICmpInst::Predicate LPred =
2368  IsAnd ? LHS->getInversePredicate() : LHS->getPredicate();
2369  ICmpInst::Predicate RPred =
2370  IsAnd ? RHS->getInversePredicate() : RHS->getPredicate();
2371  Value *LHS0 = LHS->getOperand(0);
2372  if (LPred != ICmpInst::ICMP_EQ || !match(LHS->getOperand(1), m_Zero()) ||
2373  !LHS0->getType()->isIntOrIntVectorTy() ||
2374  !(LHS->hasOneUse() || RHS->hasOneUse()))
2375  return nullptr;
2376 
2377  Value *Other;
2378  if (RPred == ICmpInst::ICMP_ULT && RHS->getOperand(1) == LHS0)
2379  Other = RHS->getOperand(0);
2380  else if (RPred == ICmpInst::ICMP_UGT && RHS->getOperand(0) == LHS0)
2381  Other = RHS->getOperand(1);
2382  else
2383  return nullptr;
2384 
2385  return Builder.CreateICmp(
2387  Builder.CreateAdd(LHS0, Constant::getAllOnesValue(LHS0->getType())),
2388  Other);
2389 }
2390 
2391 /// Fold (icmp)&(icmp) or (icmp)|(icmp) if possible.
2392 Value *InstCombinerImpl::foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2393  BinaryOperator &BO, bool IsAnd) {
2394  const SimplifyQuery Q = SQ.getWithInstruction(&BO);
2395 
2396  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
2397  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
2398  // if K1 and K2 are a one-bit mask.
2399  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, &BO, IsAnd))
2400  return V;
2401 
2402  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
2403  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
2404  Value *LHS1 = LHS->getOperand(1), *RHS1 = RHS->getOperand(1);
2405  const APInt *LHSC = nullptr, *RHSC = nullptr;
2406  match(LHS1, m_APInt(LHSC));
2407  match(RHS1, m_APInt(RHSC));
2408 
2409  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
2410  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
2411  if (predicatesFoldable(PredL, PredR)) {
2412  if (LHS0 == RHS1 && LHS1 == RHS0) {
2413  PredL = ICmpInst::getSwappedPredicate(PredL);
2414  std::swap(LHS0, LHS1);
2415  }
2416  if (LHS0 == RHS0 && LHS1 == RHS1) {
2417  unsigned Code = IsAnd ? getICmpCode(PredL) & getICmpCode(PredR)
2418  : getICmpCode(PredL) | getICmpCode(PredR);
2419  bool IsSigned = LHS->isSigned() || RHS->isSigned();
2420  return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
2421  }
2422  }
2423 
2424  // handle (roughly):
2425  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
2426  // (icmp eq (A & B), C) & (icmp eq (A & D), E)
2427  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, IsAnd, Builder))
2428  return V;
2429 
2430  if (Value *V = foldAndOrOfICmpEqZeroAndICmp(LHS, RHS, IsAnd, Builder))
2431  return V;
2432  if (Value *V = foldAndOrOfICmpEqZeroAndICmp(RHS, LHS, IsAnd, Builder))
2433  return V;
2434 
2435  if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, BO, Builder, Q))
2436  return V;
2437  if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, BO, Builder, Q))
2438  return V;
2439 
2440  if (Value *V = foldIsPowerOf2OrZero(LHS, RHS, IsAnd, Builder))
2441  return V;
2442  if (Value *V = foldIsPowerOf2OrZero(RHS, LHS, IsAnd, Builder))
2443  return V;
2444 
2445  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
2446  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
2447  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/!IsAnd))
2448  return V;
2449 
2450  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
2451  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
2452  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/!IsAnd))
2453  return V;
2454 
2455  if (IsAnd)
2456  if (Value *V = foldSignedTruncationCheck(LHS, RHS, BO, Builder))
2457  return V;
2458 
2459  if (Value *V = foldIsPowerOf2(LHS, RHS, IsAnd, Builder))
2460  return V;
2461 
2462  if (Value *X = foldUnsignedUnderflowCheck(LHS, RHS, IsAnd, Q, Builder))
2463  return X;
2464  if (Value *X = foldUnsignedUnderflowCheck(RHS, LHS, IsAnd, Q, Builder))
2465  return X;
2466 
2467  if (Value *X = foldEqOfParts(LHS, RHS, IsAnd))
2468  return X;
2469 
2470  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
2471  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
2472  // TODO: Remove this when foldLogOpOfMaskedICmps can handle undefs.
2473  if (PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
2474  PredL == PredR && match(LHS1, m_ZeroInt()) && match(RHS1, m_ZeroInt()) &&
2475  LHS0->getType() == RHS0->getType()) {
2476  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
2477  return Builder.CreateICmp(PredL, NewOr,
2478  Constant::getNullValue(NewOr->getType()));
2479  }
2480 
2481  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
2482  if (!LHSC || !RHSC)
2483  return nullptr;
2484 
2485  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
2486  // (trunc x) != C1 | (and x, CA) != C2 -> (and x, CA|CMAX) != C1|C2
2487  // where CMAX is the all ones value for the truncated type,
2488  // iff the lower bits of C2 and CA are zero.
2489  if (PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
2490  PredL == PredR && LHS->hasOneUse() && RHS->hasOneUse()) {
2491  Value *V;
2492  const APInt *AndC, *SmallC = nullptr, *BigC = nullptr;
2493 
2494  // (trunc x) == C1 & (and x, CA) == C2
2495  // (and x, CA) == C2 & (trunc x) == C1
2496  if (match(RHS0, m_Trunc(m_Value(V))) &&
2497  match(LHS0, m_And(m_Specific(V), m_APInt(AndC)))) {
2498  SmallC = RHSC;
2499  BigC = LHSC;
2500  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
2501  match(RHS0, m_And(m_Specific(V), m_APInt(AndC)))) {
2502  SmallC = LHSC;
2503  BigC = RHSC;
2504  }
2505 
2506  if (SmallC && BigC) {
2507  unsigned BigBitSize = BigC->getBitWidth();
2508  unsigned SmallBitSize = SmallC->getBitWidth();
2509 
2510  // Check that the low bits are zero.
2511  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
2512  if ((Low & *AndC).isZero() && (Low & *BigC).isZero()) {
2513  Value *NewAnd = Builder.CreateAnd(V, Low | *AndC);
2514  APInt N = SmallC->zext(BigBitSize) | *BigC;
2515  Value *NewVal = ConstantInt::get(NewAnd->getType(), N);
2516  return Builder.CreateICmp(PredL, NewAnd, NewVal);
2517  }
2518  }
2519  }
2520 
2521  return foldAndOrOfICmpsUsingRanges(LHS, RHS, IsAnd);
2522 }
2523 
2524 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2525 // here. We should standardize that construct where it is needed or choose some
2526 // other way to ensure that commutated variants of patterns are not missed.
2528  if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1),
2529  SQ.getWithInstruction(&I)))
2530  return replaceInstUsesWith(I, V);
2531 
2532  if (SimplifyAssociativeOrCommutative(I))
2533  return &I;
2534 
2535  if (Instruction *X = foldVectorBinop(I))
2536  return X;
2537 
2538  if (Instruction *Phi = foldBinopWithPhiOperands(I))
2539  return Phi;
2540 
2541  // See if we can simplify any instructions used by the instruction whose sole
2542  // purpose is to compute bits we don't care about.
2543  if (SimplifyDemandedInstructionBits(I))
2544  return &I;
2545 
2546  // Do this before using distributive laws to catch simple and/or/not patterns.
2547  if (Instruction *Xor = foldOrToXor(I, Builder))
2548  return Xor;
2549 
2551  return X;
2552 
2553  // (A&B)|(A&C) -> A&(B|C) etc
2554  if (Value *V = SimplifyUsingDistributiveLaws(I))
2555  return replaceInstUsesWith(I, V);
2556 
2557  if (Value *V = SimplifyBSwap(I, Builder))
2558  return replaceInstUsesWith(I, V);
2559 
2560  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2561  Type *Ty = I.getType();
2562  if (Ty->isIntOrIntVectorTy(1)) {
2563  if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
2564  if (auto *I =
2565  foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false))
2566  return I;
2567  }
2568  if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
2569  if (auto *I =
2570  foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ false))
2571  return I;
2572  }
2573  }
2574 
2575  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2576  return FoldedLogic;
2577 
2578  if (Instruction *BitOp = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
2579  /*MatchBitReversals*/ true))
2580  return BitOp;
2581 
2582  if (Instruction *Funnel = matchFunnelShift(I, *this))
2583  return Funnel;
2584 
2586  return replaceInstUsesWith(I, Concat);
2587 
2588  Value *X, *Y;
2589  const APInt *CV;
2590  if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
2591  !CV->isAllOnes() && MaskedValueIsZero(Y, *CV, 0, &I)) {
2592  // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
2593  // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
2594  Value *Or = Builder.CreateOr(X, Y);
2595  return BinaryOperator::CreateXor(Or, ConstantInt::get(Ty, *CV));
2596  }
2597 
2598  // If the operands have no common bits set:
2599  // or (mul X, Y), X --> add (mul X, Y), X --> mul X, (Y + 1)
2600  if (match(&I,
2602  haveNoCommonBitsSet(Op0, Op1, DL)) {
2603  Value *IncrementY = Builder.CreateAdd(Y, ConstantInt::get(Ty, 1));
2604  return BinaryOperator::CreateMul(X, IncrementY);
2605  }
2606 
2607  // (A & C) | (B & D)
2608  Value *A, *B, *C, *D;
2609  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2610  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2611 
2612  // (A & C0) | (B & C1)
2613  const APInt *C0, *C1;
2614  if (match(C, m_APInt(C0)) && match(D, m_APInt(C1))) {
2615  Value *X;
2616  if (*C0 == ~*C1) {
2617  // ((X | B) & MaskC) | (B & ~MaskC) -> (X & MaskC) | B
2618  if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
2619  return BinaryOperator::CreateOr(Builder.CreateAnd(X, *C0), B);
2620  // (A & MaskC) | ((X | A) & ~MaskC) -> (X & ~MaskC) | A
2621  if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
2622  return BinaryOperator::CreateOr(Builder.CreateAnd(X, *C1), A);
2623 
2624  // ((X ^ B) & MaskC) | (B & ~MaskC) -> (X & MaskC) ^ B
2625  if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
2626  return BinaryOperator::CreateXor(Builder.CreateAnd(X, *C0), B);
2627  // (A & MaskC) | ((X ^ A) & ~MaskC) -> (X & ~MaskC) ^ A
2628  if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
2629  return BinaryOperator::CreateXor(Builder.CreateAnd(X, *C1), A);
2630  }
2631 
2632  if ((*C0 & *C1).isZero()) {
2633  // ((X | B) & C0) | (B & C1) --> (X | B) & (C0 | C1)
2634  // iff (C0 & C1) == 0 and (X & ~C0) == 0
2635  if (match(A, m_c_Or(m_Value(X), m_Specific(B))) &&
2636  MaskedValueIsZero(X, ~*C0, 0, &I)) {
2637  Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
2638  return BinaryOperator::CreateAnd(A, C01);
2639  }
2640  // (A & C0) | ((X | A) & C1) --> (X | A) & (C0 | C1)
2641  // iff (C0 & C1) == 0 and (X & ~C1) == 0
2642  if (match(B, m_c_Or(m_Value(X), m_Specific(A))) &&
2643  MaskedValueIsZero(X, ~*C1, 0, &I)) {
2644  Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
2645  return BinaryOperator::CreateAnd(B, C01);
2646  }
2647  // ((X | C2) & C0) | ((X | C3) & C1) --> (X | C2 | C3) & (C0 | C1)
2648  // iff (C0 & C1) == 0 and (C2 & ~C0) == 0 and (C3 & ~C1) == 0.
2649  const APInt *C2, *C3;
2650  if (match(A, m_Or(m_Value(X), m_APInt(C2))) &&
2651  match(B, m_Or(m_Specific(X), m_APInt(C3))) &&
2652  (*C2 & ~*C0).isZero() && (*C3 & ~*C1).isZero()) {
2653  Value *Or = Builder.CreateOr(X, *C2 | *C3, "bitfield");
2654  Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
2655  return BinaryOperator::CreateAnd(Or, C01);
2656  }
2657  }
2658  }
2659 
2660  // Don't try to form a select if it's unlikely that we'll get rid of at
2661  // least one of the operands. A select is generally more expensive than the
2662  // 'or' that it is replacing.
2663  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2664  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2665  if (Value *V = matchSelectFromAndOr(A, C, B, D))
2666  return replaceInstUsesWith(I, V);
2667  if (Value *V = matchSelectFromAndOr(A, C, D, B))
2668  return replaceInstUsesWith(I, V);
2669  if (Value *V = matchSelectFromAndOr(C, A, B, D))
2670  return replaceInstUsesWith(I, V);
2671  if (Value *V = matchSelectFromAndOr(C, A, D, B))
2672  return replaceInstUsesWith(I, V);
2673  if (Value *V = matchSelectFromAndOr(B, D, A, C))
2674  return replaceInstUsesWith(I, V);
2675  if (Value *V = matchSelectFromAndOr(B, D, C, A))
2676  return replaceInstUsesWith(I, V);
2677  if (Value *V = matchSelectFromAndOr(D, B, A, C))
2678  return replaceInstUsesWith(I, V);
2679  if (Value *V = matchSelectFromAndOr(D, B, C, A))
2680  return replaceInstUsesWith(I, V);
2681  }
2682  }
2683 
2684  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2685  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2686  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2687  return BinaryOperator::CreateOr(Op0, C);
2688 
2689  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2690  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2691  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2692  return BinaryOperator::CreateOr(Op1, C);
2693 
2694  // ((A & B) ^ C) | B -> C | B
2695  if (match(Op0, m_c_Xor(m_c_And(m_Value(A), m_Specific(Op1)), m_Value(C))))
2696  return BinaryOperator::CreateOr(C, Op1);
2697 
2698  // B | ((A & B) ^ C) -> B | C
2699  if (match(Op1, m_c_Xor(m_c_And(m_Value(A), m_Specific(Op0)), m_Value(C))))
2700  return BinaryOperator::CreateOr(Op0, C);
2701 
2702  // ((B | C) & A) | B -> B | (A & C)
2703  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2704  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2705 
2706  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2707  return DeMorgan;
2708 
2709  // Canonicalize xor to the RHS.
2710  bool SwappedForXor = false;
2711  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2712  std::swap(Op0, Op1);
2713  SwappedForXor = true;
2714  }
2715 
2716  // A | ( A ^ B) -> A | B
2717  // A | (~A ^ B) -> A | ~B
2718  // (A & B) | (A ^ B)
2719  // ~A | (A ^ B) -> ~(A & B)
2720  // The swap above should always make Op0 the 'not' for the last case.
2721  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2722  if (Op0 == A || Op0 == B)
2723  return BinaryOperator::CreateOr(A, B);
2724 
2725  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2726  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2727  return BinaryOperator::CreateOr(A, B);
2728 
2729  if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
2730  (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B)))))
2731  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
2732 
2733  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2734  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2735  return BinaryOperator::CreateOr(Not, Op0);
2736  }
2737  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2738  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2739  return BinaryOperator::CreateOr(Not, Op0);
2740  }
2741  }
2742 
2743  // A | ~(A | B) -> A | ~B
2744  // A | ~(A ^ B) -> A | ~B
2745  if (match(Op1, m_Not(m_Value(A))))
2746  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2747  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2748  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2749  B->getOpcode() == Instruction::Xor)) {
2750  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2751  B->getOperand(0);
2752  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2753  return BinaryOperator::CreateOr(Not, Op0);
2754  }
2755 
2756  if (SwappedForXor)
2757  std::swap(Op0, Op1);
2758 
2759  {
2760  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2761  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2762  if (LHS && RHS)
2763  if (Value *Res = foldAndOrOfICmps(LHS, RHS, I, /* IsAnd */ false))
2764  return replaceInstUsesWith(I, Res);
2765 
2766  // TODO: Make this recursive; it's a little tricky because an arbitrary
2767  // number of 'or' instructions might have to be created.
2768  Value *X, *Y;
2769  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2770  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2771  if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ false))
2772  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2773  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2774  if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ false))
2775  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2776  }
2777  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2778  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2779  if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ false))
2780  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2781  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2782  if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ false))
2783  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2784  }
2785  }
2786 
2787  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2788  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2789  if (Value *Res = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false))
2790  return replaceInstUsesWith(I, Res);
2791 
2792  if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2793  return FoldedFCmps;
2794 
2795  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2796  return CastedOr;
2797 
2798  if (Instruction *Sel = foldBinopOfSextBoolToSelect(I))
2799  return Sel;
2800 
2801  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2802  // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold
2803  // with binop identity constant. But creating a select with non-constant
2804  // arm may not be reversible due to poison semantics. Is that a good
2805  // canonicalization?
2806  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2807  A->getType()->isIntOrIntVectorTy(1))
2809  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2810  A->getType()->isIntOrIntVectorTy(1))
2812 
2813  // Note: If we've gotten to the point of visiting the outer OR, then the
2814  // inner one couldn't be simplified. If it was a constant, then it won't
2815  // be simplified by a later pass either, so we try swapping the inner/outer
2816  // ORs in the hopes that we'll be able to simplify it this way.
2817  // (X|C) | V --> (X|V) | C
2818  ConstantInt *CI;
2819  if (Op0->hasOneUse() && !match(Op1, m_ConstantInt()) &&
2820  match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
2821  Value *Inner = Builder.CreateOr(A, Op1);
2822  Inner->takeName(Op0);
2823  return BinaryOperator::CreateOr(Inner, CI);
2824  }
2825 
2826  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2827  // Since this OR statement hasn't been optimized further yet, we hope
2828  // that this transformation will allow the new ORs to be optimized.
2829  {
2830  Value *X = nullptr, *Y = nullptr;
2831  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2832  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2833  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2834  Value *orTrue = Builder.CreateOr(A, C);
2835  Value *orFalse = Builder.CreateOr(B, D);
2836  return SelectInst::Create(X, orTrue, orFalse);
2837  }
2838  }
2839 
2840  // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X.
2841  {
2842  Value *X, *Y;
2843  if (match(&I, m_c_Or(m_OneUse(m_AShr(
2844  m_NSWSub(m_Value(Y), m_Value(X)),
2845  m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
2846  m_Deferred(X)))) {
2847  Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
2848  Value *AllOnes = ConstantInt::getAllOnesValue(Ty);
2849  return SelectInst::Create(NewICmpInst, AllOnes, X);
2850  }
2851  }
2852 
2853  if (Instruction *V =
2854  canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
2855  return V;
2856 
2857  CmpInst::Predicate Pred;
2858  Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2859  // Check if the OR weakens the overflow condition for umul.with.overflow by
2860  // treating any non-zero result as overflow. In that case, we overflow if both
2861  // umul.with.overflow operands are != 0, as in that case the result can only
2862  // be 0, iff the multiplication overflows.
2863  if (match(&I,
2864  m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_Value(UMulWithOv)),
2865  m_Value(Ov)),
2866  m_CombineAnd(m_ICmp(Pred,
2867  m_CombineAnd(m_ExtractValue<0>(
2868  m_Deferred(UMulWithOv)),
2869  m_Value(Mul)),
2870  m_ZeroInt()),
2871  m_Value(MulIsNotZero)))) &&
2872  (Ov->hasOneUse() || (MulIsNotZero->hasOneUse() && Mul->hasOneUse())) &&
2873  Pred == CmpInst::ICMP_NE) {
2874  Value *A, *B;
2875  if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2876  m_Value(A), m_Value(B)))) {
2877  Value *NotNullA = Builder.CreateIsNotNull(A);
2878  Value *NotNullB = Builder.CreateIsNotNull(B);
2879  return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2880  }
2881  }
2882 
2883  // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions
2884  if (sinkNotIntoOtherHandOfAndOrOr(I))
2885  return &I;
2886 
2887  // Improve "get low bit mask up to and including bit X" pattern:
2888  // (1 << X) | ((1 << X) + -1) --> -1 l>> (bitwidth(x) - 1 - X)
2889  if (match(&I, m_c_Or(m_Add(m_Shl(m_One(), m_Value(X)), m_AllOnes()),
2890  m_Shl(m_One(), m_Deferred(X)))) &&
2891  match(&I, m_c_Or(m_OneUse(m_Value()), m_Value()))) {
2892  Value *Sub = Builder.CreateSub(
2893  ConstantInt::get(Ty, Ty->getScalarSizeInBits() - 1), X);
2894  return BinaryOperator::CreateLShr(Constant::getAllOnesValue(Ty), Sub);
2895  }
2896 
2897  // An or recurrence w/loop invariant step is equivelent to (or start, step)
2898  PHINode *PN = nullptr;
2899  Value *Start = nullptr, *Step = nullptr;
2900  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2901  return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
2902 
2903  // (A & B) | (C | D) or (C | D) | (A & B)
2904  // Can be combined if C or D is of type (A/B & X)
2905  if (match(&I, m_c_Or(m_OneUse(m_And(m_Value(A), m_Value(B))),
2906  m_OneUse(m_Or(m_Value(C), m_Value(D)))))) {
2907  // (A & B) | (C | ?) -> C | (? | (A & B))
2908  // (A & B) | (C | ?) -> C | (? | (A & B))
2909  // (A & B) | (C | ?) -> C | (? | (A & B))
2910  // (A & B) | (C | ?) -> 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  // (C | ?) | (A & B) -> C | (? | (A & B))
2915  if (match(D, m_c_And(m_Specific(A), m_Value())) ||
2916  match(D, m_c_And(m_Specific(B), m_Value())))
2917  return BinaryOperator::CreateOr(
2918  C, Builder.CreateOr(D, Builder.CreateAnd(A, B)));
2919  // (A & B) | (? | D) -> (? | (A & B)) | D
2920  // (A & B) | (? | D) -> (? | (A & B)) | D
2921  // (A & B) | (? | D) -> (? | (A & B)) | D
2922  // (A & B) | (? | D) -> (? | (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  // (? | D) | (A & B) -> (? | (A & B)) | D
2927  if (match(C, m_c_And(m_Specific(A), m_Value())) ||
2928  match(C, m_c_And(m_Specific(B), m_Value())))
2929  return BinaryOperator::CreateOr(
2930  Builder.CreateOr(C, Builder.CreateAnd(A, B)), D);
2931  }
2932 
2933  return nullptr;
2934 }
2935 
2936 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2937 /// can fold these early and efficiently by morphing an existing instruction.
2940  assert(I.getOpcode() == Instruction::Xor);
2941  Value *Op0 = I.getOperand(0);
2942  Value *Op1 = I.getOperand(1);
2943  Value *A, *B;
2944 
2945  // There are 4 commuted variants for each of the basic patterns.
2946 
2947  // (A & B) ^ (A | B) -> A ^ B
2948  // (A & B) ^ (B | A) -> A ^ B
2949  // (A | B) ^ (A & B) -> A ^ B
2950  // (A | B) ^ (B & A) -> A ^ B
2951  if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
2952  m_c_Or(m_Deferred(A), m_Deferred(B)))))
2953  return BinaryOperator::CreateXor(A, B);
2954 
2955  // (A | ~B) ^ (~A | B) -> A ^ B
2956  // (~B | A) ^ (~A | B) -> A ^ B
2957  // (~A | B) ^ (A | ~B) -> A ^ B
2958  // (B | ~A) ^ (A | ~B) -> A ^ B
2959  if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
2960  m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B)))))
2961  return BinaryOperator::CreateXor(A, B);
2962 
2963  // (A & ~B) ^ (~A & B) -> A ^ B
2964  // (~B & A) ^ (~A & B) -> A ^ B
2965  // (~A & B) ^ (A & ~B) -> A ^ B
2966  // (B & ~A) ^ (A & ~B) -> A ^ B
2967  if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
2968  m_c_And(m_Not(m_Deferred(A)), m_Deferred(B)))))
2969  return BinaryOperator::CreateXor(A, B);
2970 
2971  // For the remaining cases we need to get rid of one of the operands.
2972  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2973  return nullptr;
2974 
2975  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2976  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2977  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2978  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2979  // Complexity sorting ensures the not will be on the right side.
2980  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2981  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2982  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2983  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2984  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2985 
2986  return nullptr;
2987 }
2988 
2989 Value *InstCombinerImpl::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
2990  BinaryOperator &I) {
2991  assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
2992  I.getOperand(1) == RHS && "Should be 'xor' with these operands");
2993 
2994  if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2995  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2996  LHS->getOperand(1) == RHS->getOperand(0))
2997  LHS->swapOperands();
2998  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2999  LHS->getOperand(1) == RHS->getOperand(1)) {
3000  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
3001  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
3002  unsigned Code =
3003  getICmpCode(LHS->getPredicate()) ^ getICmpCode(RHS->getPredicate());
3004  bool IsSigned = LHS->isSigned() || RHS->isSigned();
3005  return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder);
3006  }
3007  }
3008 
3009  // TODO: This can be generalized to compares of non-signbits using
3010  // decomposeBitTestICmp(). It could be enhanced more by using (something like)
3011  // foldLogOpOfMaskedICmps().
3012  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
3013  Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
3014  Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
3015  if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
3016  LHS0->getType() == RHS0->getType() &&
3017  LHS0->getType()->isIntOrIntVectorTy()) {
3018  // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
3019  // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
3020  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
3021  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) ||
3022  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
3023  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())))
3024  return Builder.CreateIsNeg(Builder.CreateXor(LHS0, RHS0));
3025 
3026  // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
3027  // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
3028  if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) &&
3029  PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) ||
3030  (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) &&
3031  PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())))
3032  return Builder.CreateIsNotNeg(Builder.CreateXor(LHS0, RHS0));
3033 
3034  }
3035 
3036  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
3037  // into those logic ops. That is, try to turn this into an and-of-icmps
3038  // because we have many folds for that pattern.
3039  //
3040  // This is based on a truth table definition of xor:
3041  // X ^ Y --> (X | Y) & !(X & Y)
3042  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
3043  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
3044  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
3045  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
3046  // TODO: Independently handle cases where the 'and' side is a constant.
3047  ICmpInst *X = nullptr, *Y = nullptr;
3048  if (OrICmp == LHS && AndICmp == RHS) {
3049  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS --> X & !Y
3050  X = LHS;
3051  Y = RHS;
3052  }
3053  if (OrICmp == RHS && AndICmp == LHS) {
3054  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS --> !Y & X
3055  X = RHS;
3056  Y = LHS;
3057  }
3058  if (X && Y && (Y->hasOneUse() || canFreelyInvertAllUsersOf(Y, &I))) {
3059  // Invert the predicate of 'Y', thus inverting its output.
3060  Y->setPredicate(Y->getInversePredicate());
3061  // So, are there other uses of Y?
3062  if (!Y->hasOneUse()) {
3063  // We need to adapt other uses of Y though. Get a value that matches
3064  // the original value of Y before inversion. While this increases
3065  // immediate instruction count, we have just ensured that all the
3066  // users are freely-invertible, so that 'not' *will* get folded away.
3068  // Set insertion point to right after the Y.
3069  Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
3070  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3071  // Replace all uses of Y (excluding the one in NotY!) with NotY.
3072  Worklist.pushUsersToWorkList(*Y);
3073  Y->replaceUsesWithIf(NotY,
3074  [NotY](Use &U) { return U.getUser() != NotY; });
3075  }
3076  // All done.
3077  return Builder.CreateAnd(LHS, RHS);
3078  }
3079  }
3080  }
3081 
3082  return nullptr;
3083 }
3084 
3085 /// If we have a masked merge, in the canonical form of:
3086 /// (assuming that A only has one use.)
3087 /// | A | |B|
3088 /// ((x ^ y) & M) ^ y
3089 /// | D |
3090 /// * If M is inverted:
3091 /// | D |
3092 /// ((x ^ y) & ~M) ^ y
3093 /// We can canonicalize by swapping the final xor operand
3094 /// to eliminate the 'not' of the mask.
3095 /// ((x ^ y) & M) ^ x
3096 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
3097 /// because that shortens the dependency chain and improves analysis:
3098 /// (x & M) | (y & ~M)
3101  Value *B, *X, *D;
3102  Value *M;
3103  if (!match(&I, m_c_Xor(m_Value(B),
3104  m_OneUse(m_c_And(
3106  m_Value(D)),
3107  m_Value(M))))))
3108  return nullptr;
3109 
3110  Value *NotM;
3111  if (match(M, m_Not(m_Value(NotM)))) {
3112  // De-invert the mask and swap the value in B part.
3113  Value *NewA = Builder.CreateAnd(D, NotM);
3114  return BinaryOperator::CreateXor(NewA, X);
3115  }
3116 
3117  Constant *C;
3118  if (D->hasOneUse() && match(M, m_Constant(C))) {
3119  // Propagating undef is unsafe. Clamp undef elements to -1.
3120  Type *EltTy = C->getType()->getScalarType();
3122  // Unfold.
3123  Value *LHS = Builder.CreateAnd(X, C);
3124  Value *NotC = Builder.CreateNot(C);
3125  Value *RHS = Builder.CreateAnd(B, NotC);
3126  return BinaryOperator::CreateOr(LHS, RHS);
3127  }
3128 
3129  return nullptr;
3130 }
3131 
3132 // Transform
3133 // ~(x ^ y)
3134 // into:
3135 // (~x) ^ y
3136 // or into
3137 // x ^ (~y)
3140  Value *X, *Y;
3141  // FIXME: one-use check is not needed in general, but currently we are unable
3142  // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
3143  if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
3144  return nullptr;
3145 
3146  // We only want to do the transform if it is free to do.
3147  if (InstCombiner::isFreeToInvert(X, X->hasOneUse())) {
3148  // Ok, good.
3149  } else if (InstCombiner::isFreeToInvert(Y, Y->hasOneUse())) {
3150  std::swap(X, Y);
3151  } else
3152  return nullptr;
3153 
3154  Value *NotX = Builder.CreateNot(X, X->getName() + ".not");
3155  return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan");
3156 }
3157 
3158 /// Canonicalize a shifty way to code absolute value to the more common pattern
3159 /// that uses negation and select.
3162  assert(Xor.getOpcode() == Instruction::Xor && "Expected an xor instruction.");
3163 
3164  // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
3165  // We're relying on the fact that we only do this transform when the shift has
3166  // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
3167  // instructions).
3168  Value *Op0 = Xor.getOperand(0), *Op1 = Xor.getOperand(1);
3169  if (Op0->hasNUses(2))
3170  std::swap(Op0, Op1);
3171 
3172  Type *Ty = Xor.getType();
3173  Value *A;
3174  const APInt *ShAmt;
3175  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
3176  Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
3177  match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
3178  // Op1 = ashr i32 A, 31 ; smear the sign bit
3179  // xor (add A, Op1), Op1 ; add -1 and flip bits if negative
3180  // --> (A < 0) ? -A : A
3181  Value *IsNeg = Builder.CreateIsNeg(A);
3182  // Copy the nuw/nsw flags from the add to the negate.
3183  auto *Add = cast<BinaryOperator>(Op0);
3184  Value *NegA = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
3185  Add->hasNoSignedWrap());
3186  return SelectInst::Create(IsNeg, NegA, A);
3187  }
3188  return nullptr;
3189 }
3190 
3191 // Transform
3192 // z = (~x) &/| y
3193 // into:
3194 // z = ~(x |/& (~y))
3195 // iff y is free to invert and all uses of z can be freely updated.
3197  Instruction::BinaryOps NewOpc;
3198  switch (I.getOpcode()) {
3199  case Instruction::And:
3200  NewOpc = Instruction::Or;
3201  break;
3202  case Instruction::Or:
3203  NewOpc = Instruction::And;
3204  break;
3205  default:
3206  return false;
3207  };
3208 
3209  Value *X, *Y;
3210  if (!match(&I, m_c_BinOp(m_Not(m_Value(X)), m_Value(Y))))
3211  return false;
3212 
3213  // Will we be able to fold the `not` into Y eventually?
3214  if (!InstCombiner::isFreeToInvert(Y, Y->hasOneUse()))
3215  return false;
3216 
3217  // And can our users be adapted?
3218  if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
3219  return false;
3220 
3221  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3222  Value *NewBinOp =
3223  BinaryOperator::Create(NewOpc, X, NotY, I.getName() + ".not");
3224  Builder.Insert(NewBinOp);
3225  replaceInstUsesWith(I, NewBinOp);
3226  // We can not just create an outer `not`, it will most likely be immediately
3227  // folded back, reconstructing our initial pattern, and causing an
3228  // infinite combine loop, so immediately manually fold it away.
3229  freelyInvertAllUsersOf(NewBinOp);
3230  return true;
3231 }
3232 
3233 Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) {
3234  Value *NotOp;
3235  if (!match(&I, m_Not(m_Value(NotOp))))
3236  return nullptr;
3237 
3238  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
3239  // We must eliminate the and/or (one-use) for these transforms to not increase
3240  // the instruction count.
3241  //
3242  // ~(~X & Y) --> (X | ~Y)
3243  // ~(Y & ~X) --> (X | ~Y)
3244  //
3245  // Note: The logical matches do not check for the commuted patterns because
3246  // those are handled via SimplifySelectsFeedingBinaryOp().
3247  Type *Ty = I.getType();
3248  Value *X, *Y;
3249  if (match(NotOp, m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y))))) {
3250  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3251  return BinaryOperator::CreateOr(X, NotY);
3252  }
3253  if (match(NotOp, m_OneUse(m_LogicalAnd(m_Not(m_Value(X)), m_Value(Y))))) {
3254  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3255  return SelectInst::Create(X, ConstantInt::getTrue(Ty), NotY);
3256  }
3257 
3258  // ~(~X | Y) --> (X & ~Y)
3259  // ~(Y | ~X) --> (X & ~Y)
3260  if (match(NotOp, m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y))))) {
3261  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3262  return BinaryOperator::CreateAnd(X, NotY);
3263  }
3264  if (match(NotOp, m_OneUse(m_LogicalOr(m_Not(m_Value(X)), m_Value(Y))))) {
3265  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
3266  return SelectInst::Create(X, NotY, ConstantInt::getFalse(Ty));
3267  }
3268 
3269  // Is this a 'not' (~) fed by a binary operator?
3270  BinaryOperator *NotVal;
3271  if (match(NotOp, m_BinOp(NotVal))) {
3272  if (NotVal->getOpcode() == Instruction::And ||
3273  NotVal->getOpcode() == Instruction::Or) {
3274  // Apply DeMorgan's Law when inverts are free:
3275  // ~(X & Y) --> (~X | ~Y)
3276  // ~(X | Y) --> (~X & ~Y)
3277  if (isFreeToInvert(NotVal->getOperand(0),
3278  NotVal->getOperand(0)->hasOneUse()) &&
3279  isFreeToInvert(NotVal->getOperand(1),
3280  NotVal->getOperand(1)->hasOneUse())) {
3281  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
3282  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
3283  if (NotVal->getOpcode() == Instruction::And)
3284  return BinaryOperator::CreateOr(NotX, NotY);
3285  return BinaryOperator::CreateAnd(NotX, NotY);
3286  }
3287  }
3288 
3289  // ~((-X) | Y) --> (X - 1) & (~Y)
3290  if (match(NotVal,
3292  Value *DecX = Builder.CreateAdd(X, ConstantInt::getAllOnesValue(Ty));
3293  Value *NotY = Builder.CreateNot(Y);
3294  return BinaryOperator::CreateAnd(DecX, NotY);
3295  }
3296 
3297  // ~(~X >>s Y) --> (X >>s Y)
3298  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
3299  return BinaryOperator::CreateAShr(X, Y);
3300 
3301  // If we are inverting a right-shifted constant, we may be able to eliminate
3302  // the 'not' by inverting the constant and using the opposite shift type.
3303  // Canonicalization rules ensure that only a negative constant uses 'ashr',
3304  // but we must check that in case that transform has not fired yet.
3305 
3306  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
3307  Constant *C;
3308  if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
3309  match(C, m_Negative())) {
3310  // We matched a negative constant, so propagating undef is unsafe.
3311  // Clamp undef elements to -1.
3312  Type *EltTy = Ty->getScalarType();
3314  return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
3315  }
3316 
3317  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
3318  if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
3319  match(C, m_NonNegative())) {
3320  // We matched a non-negative constant, so propagating undef is unsafe.
3321  // Clamp undef elements to 0.
3322  Type *EltTy = Ty->getScalarType();
3324  return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
3325  }
3326 
3327  // ~(X + C) --> ~C - X
3328  if (match(NotVal, m_c_Add(m_Value(X), m_ImmConstant(C))))
3329  return BinaryOperator::CreateSub(ConstantExpr::getNot(C), X);
3330 
3331  // ~(X - Y) --> ~X + Y
3332  // FIXME: is it really beneficial to sink the `not` here?
3333  if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
3334  if (isa<Constant>(X) || NotVal->hasOneUse())
3335  return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
3336 
3337  // ~(~X + Y) --> X - Y
3338  if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
3339  return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
3340  NotVal);
3341  }
3342 
3343  // not (cmp A, B) = !cmp A, B
3344  CmpInst::Predicate Pred;
3345  if (match(NotOp, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
3346  cast<CmpInst>(NotOp)->setPredicate(CmpInst::getInversePredicate(Pred));
3347  return replaceInstUsesWith(I, NotOp);
3348  }
3349 
3350  // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
3351  // ~min(~X, ~Y) --> max(X, Y)
3352  // ~max(~X, Y) --> min(X, ~Y)
3353  auto *II = dyn_cast<IntrinsicInst>(NotOp);
3354  if (II && II->hasOneUse()) {
3355  if (match(NotOp, m_MaxOrMin(m_Value(X), m_Value(Y))) &&
3356  isFreeToInvert(X, X->hasOneUse()) &&
3357  isFreeToInvert(Y, Y->hasOneUse())) {
3358  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3359  Value *NotX = Builder.CreateNot(X);
3360  Value *NotY = Builder.CreateNot(Y);
3361  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, NotX, NotY);
3362  return replaceInstUsesWith(I, InvMaxMin);
3363  }
3364  if (match(NotOp, m_c_MaxOrMin(m_Not(m_Value(X)), m_Value(Y)))) {
3365  Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3366  Value *NotY = Builder.CreateNot(Y);
3367  Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotY);
3368  return replaceInstUsesWith(I, InvMaxMin);
3369  }
3370  }
3371 
3372  if (NotOp->hasOneUse()) {
3373  // Pull 'not' into operands of select if both operands are one-use compares
3374  // or one is one-use compare and the other one is a constant.
3375  // Inverting the predicates eliminates the 'not' operation.
3376  // Example:
3377  // not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
3378  // select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
3379  // not (select ?, (cmp TPred, ?, ?), true -->
3380  // select ?, (cmp InvTPred, ?, ?), false
3381  if (auto *Sel = dyn_cast<SelectInst>(NotOp)) {
3382  Value *TV = Sel->getTrueValue();
3383  Value *FV = Sel->getFalseValue();
3384  auto *CmpT = dyn_cast<CmpInst>(TV);
3385  auto *CmpF = dyn_cast<CmpInst>(FV);
3386  bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3387  bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3388  if (InvertibleT && InvertibleF) {
3389  if (CmpT)
3390  CmpT->setPredicate(CmpT->getInversePredicate());
3391  else
3392  Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
3393  if (CmpF)
3394  CmpF->setPredicate(CmpF->getInversePredicate());
3395  else
3396  Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
3397  return replaceInstUsesWith(I, Sel);
3398  }
3399  }
3400  }
3401 
3402  if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
3403  return NewXor;
3404 
3405  return nullptr;
3406 }
3407 
3408 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
3409 // here. We should standardize that construct where it is needed or choose some
3410 // other way to ensure that commutated variants of patterns are not missed.
3412  if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1),
3413  SQ.getWithInstruction(&I)))
3414  return replaceInstUsesWith(I, V);
3415 
3416  if (SimplifyAssociativeOrCommutative(I))
3417  return &I;
3418 
3419  if (Instruction *X = foldVectorBinop(I))
3420  return X;
3421 
3422  if (Instruction *Phi = foldBinopWithPhiOperands(I))
3423  return Phi;
3424 
3425  if (Instruction *NewXor = foldXorToXor(I, Builder))
3426  return NewXor;
3427 
3428  // (A&B)^(A&C) -> A&(B^C) etc
3429  if (Value *V = SimplifyUsingDistributiveLaws(I))
3430  return replaceInstUsesWith(I, V);
3431 
3432  // See if we can simplify any instructions used by the instruction whose sole
3433  // purpose is to compute bits we don't care about.
3434  if (SimplifyDemandedInstructionBits(I))
3435  return &I;
3436 
3437  if (Value *V = SimplifyBSwap(I, Builder))
3438  return replaceInstUsesWith(I, V);
3439 
3440  if (Instruction *R = foldNot(I))
3441  return R;
3442 
3443  // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
3444  // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
3445  // calls in there are unnecessary as SimplifyDemandedInstructionBits should
3446  // have already taken care of those cases.
3447  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3448  Value *M;
3449  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
3450  m_c_And(m_Deferred(M), m_Value()))))
3451  return BinaryOperator::CreateOr(Op0, Op1);
3452 
3454  return Xor;
3455 
3456  Value *X, *Y;
3457  Constant *C1;
3458  if (match(Op1, m_Constant(C1))) {
3459  Constant *C2;
3460 
3461  if (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C2)))) &&
3462  match(C1, m_ImmConstant())) {
3463  // (X | C2) ^ C1 --> (X & ~C2) ^ (C1^C2)
3466  Value *And = Builder.CreateAnd(
3468  return BinaryOperator::CreateXor(
3470  }
3471 
3472  // Use DeMorgan and reassociation to eliminate a 'not' op.
3473  if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
3474  // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
3475  Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2));
3476  return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
3477  }
3478  if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
3479  // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
3480  Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2));
3481  return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
3482  }
3483 
3484  // Convert xor ([trunc] (ashr X, BW-1)), C =>
3485  // select(X >s -1, C, ~C)
3486  // The ashr creates "AllZeroOrAllOne's", which then optionally inverses the
3487  // constant depending on whether this input is less than 0.
3488  const APInt *CA;
3489  if (match(Op0, m_OneUse(m_TruncOrSelf(
3490  m_AShr(m_Value(X), m_APIntAllowUndef(CA))))) &&
3491  *CA == X->getType()->getScalarSizeInBits() - 1 &&
3492  !match(C1, m_AllOnes())) {
3493  assert(!C1->isZeroValue() && "Unexpected xor with 0");
3494  Value *IsNotNeg = Builder.CreateIsNotNeg(X);
3495  return SelectInst::Create(IsNotNeg, Op1, Builder.CreateNot(Op1));
3496  }
3497  }
3498 
3499  Type *Ty = I.getType();
3500  {
3501  const APInt *RHSC;
3502  if (match(Op1, m_APInt(RHSC))) {
3503  Value *X;
3504  const APInt *C;
3505  // (C - X) ^ signmaskC --> (C + signmaskC) - X
3506  if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X))))
3507  return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C + *RHSC), X);
3508 
3509  // (X + C) ^ signmaskC --> X + (C + signmaskC)
3510  if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
3511  return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
3512 
3513  // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
3514  if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
3515  MaskedValueIsZero(X, *C, 0, &I))
3516  return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
3517 
3518  // If RHSC is inverting the remaining bits of shifted X,
3519  // canonicalize to a 'not' before the shift to help SCEV and codegen:
3520  // (X << C) ^ RHSC --> ~X << C
3521  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
3522  *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).shl(*C)) {
3523  Value *NotX = Builder.CreateNot(X);
3524  return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
3525  }
3526  // (X >>u C) ^ RHSC --> ~X >>u C
3527  if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
3528  *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).lshr(*C)) {
3529  Value *NotX = Builder.CreateNot(X);
3530  return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
3531  }
3532  // TODO: We could handle 'ashr' here as well. That would be matching
3533  // a 'not' op and moving it before the shift. Doing that requires
3534  // preventing the inverse fold in canShiftBinOpWithConstantRHS().
3535  }
3536  }
3537 
3538  // FIXME: This should not be limited to scalar (pull into APInt match above).
3539  {
3540  Value *X;
3541  ConstantInt *C1, *C2, *C3;
3542  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
3543  if (match(Op1, m_ConstantInt(C3)) &&
3545  m_ConstantInt(C2))) &&
3546  Op0->hasOneUse()) {
3547  // fold (C1 >> C2) ^ C3
3548  APInt FoldConst = C1->getValue().lshr(C2->getValue());
3549  FoldConst ^= C3->getValue();
3550  // Prepare the two operands.
3551  auto *Opnd0 = Builder.CreateLShr(X, C2);
3552  Opnd0->takeName(Op0);
3553  return BinaryOperator::CreateXor(Opnd0, ConstantInt::get(Ty, FoldConst));
3554  }
3555  }
3556 
3557  if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
3558  return FoldedLogic;
3559 
3560  // Y ^ (X | Y) --> X & ~Y
3561  // Y ^ (Y | X) --> X & ~Y
3562  if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
3563  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
3564  // (X | Y) ^ Y --> X & ~Y
3565  // (Y | X) ^ Y --> X & ~Y
3566  if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
3567  return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
3568 
3569  // Y ^ (X & Y) --> ~X & Y
3570  // Y ^ (Y & X) --> ~X & Y
3571  if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
3572  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
3573  // (X & Y) ^ Y --> ~X & Y
3574  // (Y & X) ^ Y --> ~X & Y
3575  // Canonical form is (X & C) ^ C; don't touch that.
3576  // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
3577  // be fixed to prefer that (otherwise we get infinite looping).
3578  if (!match(Op1, m_Constant()) &&
3579  match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
3580  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
3581 
3582  Value *A, *B, *C;
3583  // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
3584  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3585  m_OneUse(m_c_Or(m_Deferred(A), m_Value(C))))))
3586  return BinaryOperator::CreateXor(
3587  Builder.CreateAnd(Builder.CreateNot(A), C), B);
3588 
3589  // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
3590  if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))),
3592  return BinaryOperator::CreateXor(
3593  Builder.CreateAnd(Builder.CreateNot(B), C), A);
3594 
3595  // (A & B) ^ (A ^ B) -> (A | B)
3596  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
3597  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
3598  return BinaryOperator::CreateOr(A, B);
3599  // (A ^ B) ^ (A & B) -> (A | B)
3600  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
3601  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
3602  return BinaryOperator::CreateOr(A, B);
3603 
3604  // (A & ~B) ^ ~A -> ~(A & B)
3605  // (~B & A) ^ ~A -> ~(A & B)
3606  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
3607  match(Op1, m_Not(m_Specific(A))))
3608  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
3609 
3610  // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
3611  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
3612  return BinaryOperator::CreateOr(A, B);
3613 
3614  // (~A | B) ^ A --> ~(A & B)
3615  if (match(Op0, m_OneUse(m_c_Or(m_Not(m_Specific(Op1)), m_Value(B)))))
3616  return BinaryOperator::CreateNot(Builder.CreateAnd(Op1, B));
3617 
3618  // A ^ (~A | B) --> ~(A & B)
3619  if (match(Op1, m_OneUse(m_c_Or(m_Not(m_Specific(Op0)), m_Value(B)))))
3620  return BinaryOperator::CreateNot(Builder.CreateAnd(Op0, B));
3621 
3622  // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
3623  // TODO: Loosen one-use restriction if common operand is a constant.
3624  Value *D;
3625  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
3626  match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
3627  if (B == C || B == D)
3628  std::swap(A, B);
3629  if (A == C)
3630  std::swap(C, D);
3631  if (A == D) {
3632  Value *NotA = Builder.CreateNot(A);
3633  return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
3634  }
3635  }
3636 
3637  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
3638  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
3639  if (Value *V = foldXorOfICmps(LHS, RHS, I))
3640  return replaceInstUsesWith(I, V);
3641 
3642  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
3643  return CastedXor;
3644 
3645  if (Instruction *Abs = canonicalizeAbs(I, Builder))
3646  return Abs;
3647 
3648  // Otherwise, if all else failed, try to hoist the xor-by-constant:
3649  // (X ^ C) ^ Y --> (X ^ Y) ^ C
3650  // Just like we do in other places, we completely avoid the fold
3651  // for constantexprs, at least to avoid endless combine loop.
3654  m_ImmConstant(C1))),
3655  m_Value(Y))))
3656  return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
3657 
3658  return nullptr;
3659 }
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:3411
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:2184
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:1577
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:2066
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:2938
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:1719
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:1467
llvm::ConstantRange::inverse
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
Definition: ConstantRange.cpp:1620
matchFunnelShift
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
Definition: InstCombineAndOrXor.cpp:2082
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:2365
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:3099
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:3138
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:2527
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.cp