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