LLVM  6.0.0svn
InstCombineAndOrXor.cpp
Go to the documentation of this file.
1 //===- InstCombineAndOrXor.cpp --------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the visitAnd, visitOr, and visitXor functions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
16 #include "llvm/IR/ConstantRange.h"
17 #include "llvm/IR/Intrinsics.h"
18 #include "llvm/IR/PatternMatch.h"
21 using namespace llvm;
22 using namespace PatternMatch;
23 
24 #define DEBUG_TYPE "instcombine"
25 
26 /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
27 /// a four bit mask.
28 static unsigned getFCmpCode(FCmpInst::Predicate CC) {
30  "Unexpected FCmp predicate!");
31  // Take advantage of the bit pattern of FCmpInst::Predicate here.
32  // U L G E
33  static_assert(FCmpInst::FCMP_FALSE == 0, ""); // 0 0 0 0
34  static_assert(FCmpInst::FCMP_OEQ == 1, ""); // 0 0 0 1
35  static_assert(FCmpInst::FCMP_OGT == 2, ""); // 0 0 1 0
36  static_assert(FCmpInst::FCMP_OGE == 3, ""); // 0 0 1 1
37  static_assert(FCmpInst::FCMP_OLT == 4, ""); // 0 1 0 0
38  static_assert(FCmpInst::FCMP_OLE == 5, ""); // 0 1 0 1
39  static_assert(FCmpInst::FCMP_ONE == 6, ""); // 0 1 1 0
40  static_assert(FCmpInst::FCMP_ORD == 7, ""); // 0 1 1 1
41  static_assert(FCmpInst::FCMP_UNO == 8, ""); // 1 0 0 0
42  static_assert(FCmpInst::FCMP_UEQ == 9, ""); // 1 0 0 1
43  static_assert(FCmpInst::FCMP_UGT == 10, ""); // 1 0 1 0
44  static_assert(FCmpInst::FCMP_UGE == 11, ""); // 1 0 1 1
45  static_assert(FCmpInst::FCMP_ULT == 12, ""); // 1 1 0 0
46  static_assert(FCmpInst::FCMP_ULE == 13, ""); // 1 1 0 1
47  static_assert(FCmpInst::FCMP_UNE == 14, ""); // 1 1 1 0
48  static_assert(FCmpInst::FCMP_TRUE == 15, ""); // 1 1 1 1
49  return CC;
50 }
51 
52 /// This is the complement of getICmpCode, which turns an opcode and two
53 /// operands into either a constant true or false, or a brand new ICmp
54 /// instruction. The sign is passed in to determine which kind of predicate to
55 /// use in the new icmp instruction.
56 static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
57  InstCombiner::BuilderTy &Builder) {
58  ICmpInst::Predicate NewPred;
59  if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred))
60  return NewConstant;
61  return Builder.CreateICmp(NewPred, LHS, RHS);
62 }
63 
64 /// This is the complement of getFCmpCode, which turns an opcode and two
65 /// operands into either a FCmp instruction, or a true/false constant.
66 static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
67  InstCombiner::BuilderTy &Builder) {
68  const auto Pred = static_cast<FCmpInst::Predicate>(Code);
69  assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
70  "Unexpected FCmp predicate!");
71  if (Pred == FCmpInst::FCMP_FALSE)
73  if (Pred == FCmpInst::FCMP_TRUE)
75  return Builder.CreateFCmp(Pred, LHS, RHS);
76 }
77 
78 /// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or
79 /// BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
80 /// \param I Binary operator to transform.
81 /// \return Pointer to node that must replace the original binary operator, or
82 /// null pointer if no transformation was made.
84  InstCombiner::BuilderTy &Builder) {
85  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bswap simplifying");
86 
87  Value *OldLHS = I.getOperand(0);
88  Value *OldRHS = I.getOperand(1);
89 
90  Value *NewLHS;
91  if (!match(OldLHS, m_BSwap(m_Value(NewLHS))))
92  return nullptr;
93 
94  Value *NewRHS;
95  const APInt *C;
96 
97  if (match(OldRHS, m_BSwap(m_Value(NewRHS)))) {
98  // OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
99  if (!OldLHS->hasOneUse() && !OldRHS->hasOneUse())
100  return nullptr;
101  // NewRHS initialized by the matcher.
102  } else if (match(OldRHS, m_APInt(C))) {
103  // OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
104  if (!OldLHS->hasOneUse())
105  return nullptr;
106  NewRHS = ConstantInt::get(I.getType(), C->byteSwap());
107  } else
108  return nullptr;
109 
110  Value *BinOp = Builder.CreateBinOp(I.getOpcode(), NewLHS, NewRHS);
111  Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap,
112  I.getType());
113  return Builder.CreateCall(F, BinOp);
114 }
115 
116 /// This handles expressions of the form ((val OP C1) & C2). Where
117 /// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.
118 Instruction *InstCombiner::OptAndOp(BinaryOperator *Op,
119  ConstantInt *OpRHS,
120  ConstantInt *AndRHS,
121  BinaryOperator &TheAnd) {
122  Value *X = Op->getOperand(0);
123  Constant *Together = nullptr;
124  if (!Op->isShift())
125  Together = ConstantExpr::getAnd(AndRHS, OpRHS);
126 
127  switch (Op->getOpcode()) {
128  default: break;
129  case Instruction::Xor:
130  if (Op->hasOneUse()) {
131  // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
132  Value *And = Builder.CreateAnd(X, AndRHS);
133  And->takeName(Op);
134  return BinaryOperator::CreateXor(And, Together);
135  }
136  break;
137  case Instruction::Or:
138  if (Op->hasOneUse()){
139  ConstantInt *TogetherCI = dyn_cast<ConstantInt>(Together);
140  if (TogetherCI && !TogetherCI->isZero()){
141  // (X | C1) & C2 --> (X & (C2^(C1&C2))) | C1
142  // NOTE: This reduces the number of bits set in the & mask, which
143  // can expose opportunities for store narrowing.
144  Together = ConstantExpr::getXor(AndRHS, Together);
145  Value *And = Builder.CreateAnd(X, Together);
146  And->takeName(Op);
147  return BinaryOperator::CreateOr(And, OpRHS);
148  }
149  }
150 
151  break;
152  case Instruction::Add:
153  if (Op->hasOneUse()) {
154  // Adding a one to a single bit bit-field should be turned into an XOR
155  // of the bit. First thing to check is to see if this AND is with a
156  // single bit constant.
157  const APInt &AndRHSV = AndRHS->getValue();
158 
159  // If there is only one bit set.
160  if (AndRHSV.isPowerOf2()) {
161  // Ok, at this point, we know that we are masking the result of the
162  // ADD down to exactly one bit. If the constant we are adding has
163  // no bits set below this bit, then we can eliminate the ADD.
164  const APInt& AddRHS = OpRHS->getValue();
165 
166  // Check to see if any bits below the one bit set in AndRHSV are set.
167  if ((AddRHS & (AndRHSV - 1)).isNullValue()) {
168  // If not, the only thing that can effect the output of the AND is
169  // the bit specified by AndRHSV. If that bit is set, the effect of
170  // the XOR is to toggle the bit. If it is clear, then the ADD has
171  // no effect.
172  if ((AddRHS & AndRHSV).isNullValue()) { // Bit is not set, noop
173  TheAnd.setOperand(0, X);
174  return &TheAnd;
175  } else {
176  // Pull the XOR out of the AND.
177  Value *NewAnd = Builder.CreateAnd(X, AndRHS);
178  NewAnd->takeName(Op);
179  return BinaryOperator::CreateXor(NewAnd, AndRHS);
180  }
181  }
182  }
183  }
184  break;
185 
186  case Instruction::Shl: {
187  // We know that the AND will not produce any of the bits shifted in, so if
188  // the anded constant includes them, clear them now!
189  //
190  uint32_t BitWidth = AndRHS->getType()->getBitWidth();
191  uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
192  APInt ShlMask(APInt::getHighBitsSet(BitWidth, BitWidth-OpRHSVal));
193  ConstantInt *CI = Builder.getInt(AndRHS->getValue() & ShlMask);
194 
195  if (CI->getValue() == ShlMask)
196  // Masking out bits that the shift already masks.
197  return replaceInstUsesWith(TheAnd, Op); // No need for the and.
198 
199  if (CI != AndRHS) { // Reducing bits set in and.
200  TheAnd.setOperand(1, CI);
201  return &TheAnd;
202  }
203  break;
204  }
205  case Instruction::LShr: {
206  // We know that the AND will not produce any of the bits shifted in, so if
207  // the anded constant includes them, clear them now! This only applies to
208  // unsigned shifts, because a signed shr may bring in set bits!
209  //
210  uint32_t BitWidth = AndRHS->getType()->getBitWidth();
211  uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
212  APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
213  ConstantInt *CI = Builder.getInt(AndRHS->getValue() & ShrMask);
214 
215  if (CI->getValue() == ShrMask)
216  // Masking out bits that the shift already masks.
217  return replaceInstUsesWith(TheAnd, Op);
218 
219  if (CI != AndRHS) {
220  TheAnd.setOperand(1, CI); // Reduce bits set in and cst.
221  return &TheAnd;
222  }
223  break;
224  }
225  case Instruction::AShr:
226  // Signed shr.
227  // See if this is shifting in some sign extension, then masking it out
228  // with an and.
229  if (Op->hasOneUse()) {
230  uint32_t BitWidth = AndRHS->getType()->getBitWidth();
231  uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
232  APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
233  Constant *C = Builder.getInt(AndRHS->getValue() & ShrMask);
234  if (C == AndRHS) { // Masking out bits shifted in.
235  // (Val ashr C1) & C2 -> (Val lshr C1) & C2
236  // Make the argument unsigned.
237  Value *ShVal = Op->getOperand(0);
238  ShVal = Builder.CreateLShr(ShVal, OpRHS, Op->getName());
239  return BinaryOperator::CreateAnd(ShVal, AndRHS, TheAnd.getName());
240  }
241  }
242  break;
243  }
244  return nullptr;
245 }
246 
247 /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
248 /// (V < Lo || V >= Hi). This method expects that Lo <= Hi. IsSigned indicates
249 /// whether to treat V, Lo, and Hi as signed or not.
250 Value *InstCombiner::insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
251  bool isSigned, bool Inside) {
252  assert((isSigned ? Lo.sle(Hi) : Lo.ule(Hi)) &&
253  "Lo is not <= Hi in range emission code!");
254 
255  Type *Ty = V->getType();
256  if (Lo == Hi)
257  return Inside ? ConstantInt::getFalse(Ty) : ConstantInt::getTrue(Ty);
258 
259  // V >= Min && V < Hi --> V < Hi
260  // V < Min || V >= Hi --> V >= Hi
262  if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
263  Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
264  return Builder.CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
265  }
266 
267  // V >= Lo && V < Hi --> V - Lo u< Hi - Lo
268  // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo
269  Value *VMinusLo =
270  Builder.CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
271  Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
272  return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo);
273 }
274 
275 /// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns
276 /// that can be simplified.
277 /// One of A and B is considered the mask. The other is the value. This is
278 /// described as the "AMask" or "BMask" part of the enum. If the enum contains
279 /// only "Mask", then both A and B can be considered masks. If A is the mask,
280 /// then it was proven that (A & C) == C. This is trivial if C == A or C == 0.
281 /// If both A and C are constants, this proof is also easy.
282 /// For the following explanations, we assume that A is the mask.
283 ///
284 /// "AllOnes" declares that the comparison is true only if (A & B) == A or all
285 /// bits of A are set in B.
286 /// Example: (icmp eq (A & 3), 3) -> AMask_AllOnes
287 ///
288 /// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all
289 /// bits of A are cleared in B.
290 /// Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes
291 ///
292 /// "Mixed" declares that (A & B) == C and C might or might not contain any
293 /// number of one bits and zero bits.
294 /// Example: (icmp eq (A & 3), 1) -> AMask_Mixed
295 ///
296 /// "Not" means that in above descriptions "==" should be replaced by "!=".
297 /// Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes
298 ///
299 /// If the mask A contains a single bit, then the following is equivalent:
300 /// (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
301 /// (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
311  BMask_Mixed = 256,
313 };
314 
315 /// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C)
316 /// satisfies.
317 static unsigned getMaskedICmpType(Value *A, Value *B, Value *C,
318  ICmpInst::Predicate Pred) {
319  ConstantInt *ACst = dyn_cast<ConstantInt>(A);
320  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
321  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
322  bool IsEq = (Pred == ICmpInst::ICMP_EQ);
323  bool IsAPow2 = (ACst && !ACst->isZero() && ACst->getValue().isPowerOf2());
324  bool IsBPow2 = (BCst && !BCst->isZero() && BCst->getValue().isPowerOf2());
325  unsigned MaskVal = 0;
326  if (CCst && CCst->isZero()) {
327  // if C is zero, then both A and B qualify as mask
328  MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed)
330  if (IsAPow2)
331  MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed)
332  : (AMask_AllOnes | AMask_Mixed));
333  if (IsBPow2)
334  MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed)
335  : (BMask_AllOnes | BMask_Mixed));
336  return MaskVal;
337  }
338 
339  if (A == C) {
340  MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed)
342  if (IsAPow2)
343  MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed)
344  : (Mask_AllZeros | AMask_Mixed));
345  } else if (ACst && CCst && ConstantExpr::getAnd(ACst, CCst) == CCst) {
346  MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed);
347  }
348 
349  if (B == C) {
350  MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed)
352  if (IsBPow2)
353  MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed)
354  : (Mask_AllZeros | BMask_Mixed));
355  } else if (BCst && CCst && ConstantExpr::getAnd(BCst, CCst) == CCst) {
356  MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed);
357  }
358 
359  return MaskVal;
360 }
361 
362 /// Convert an analysis of a masked ICmp into its equivalent if all boolean
363 /// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
364 /// is adjacent to the corresponding normal flag (recording ==), this just
365 /// involves swapping those bits over.
366 static unsigned conjugateICmpMask(unsigned Mask) {
367  unsigned NewMask;
368  NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros |
370  << 1;
371 
372  NewMask |= (Mask & (AMask_NotAllOnes | BMask_NotAllOnes | Mask_NotAllZeros |
374  >> 1;
375 
376  return NewMask;
377 }
378 
379 /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
380 /// Return the set of pattern classes (from MaskedICmpType) that both LHS and
381 /// RHS satisfy.
382 static unsigned getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C,
383  Value *&D, Value *&E, ICmpInst *LHS,
384  ICmpInst *RHS,
385  ICmpInst::Predicate &PredL,
386  ICmpInst::Predicate &PredR) {
387  if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType())
388  return 0;
389  // vectors are not (yet?) supported
390  if (LHS->getOperand(0)->getType()->isVectorTy())
391  return 0;
392 
393  // Here comes the tricky part:
394  // LHS might be of the form L11 & L12 == X, X == L21 & L22,
395  // and L11 & L12 == L21 & L22. The same goes for RHS.
396  // Now we must find those components L** and R**, that are equal, so
397  // that we can extract the parameters A, B, C, D, and E for the canonical
398  // above.
399  Value *L1 = LHS->getOperand(0);
400  Value *L2 = LHS->getOperand(1);
401  Value *L11, *L12, *L21, *L22;
402  // Check whether the icmp can be decomposed into a bit test.
403  if (decomposeBitTestICmp(LHS, PredL, L11, L12, L2)) {
404  L21 = L22 = L1 = nullptr;
405  } else {
406  // Look for ANDs in the LHS icmp.
407  if (!L1->getType()->isIntegerTy()) {
408  // You can icmp pointers, for example. They really aren't masks.
409  L11 = L12 = nullptr;
410  } else if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
411  // Any icmp can be viewed as being trivially masked; if it allows us to
412  // remove one, it's worth it.
413  L11 = L1;
414  L12 = Constant::getAllOnesValue(L1->getType());
415  }
416 
417  if (!L2->getType()->isIntegerTy()) {
418  // You can icmp pointers, for example. They really aren't masks.
419  L21 = L22 = nullptr;
420  } else if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
421  L21 = L2;
422  L22 = Constant::getAllOnesValue(L2->getType());
423  }
424  }
425 
426  // Bail if LHS was a icmp that can't be decomposed into an equality.
427  if (!ICmpInst::isEquality(PredL))
428  return 0;
429 
430  Value *R1 = RHS->getOperand(0);
431  Value *R2 = RHS->getOperand(1);
432  Value *R11, *R12;
433  bool Ok = false;
434  if (decomposeBitTestICmp(RHS, PredR, R11, R12, R2)) {
435  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
436  A = R11;
437  D = R12;
438  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
439  A = R12;
440  D = R11;
441  } else {
442  return 0;
443  }
444  E = R2;
445  R1 = nullptr;
446  Ok = true;
447  } else if (R1->getType()->isIntegerTy()) {
448  if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
449  // As before, model no mask as a trivial mask if it'll let us do an
450  // optimization.
451  R11 = R1;
452  R12 = Constant::getAllOnesValue(R1->getType());
453  }
454 
455  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
456  A = R11;
457  D = R12;
458  E = R2;
459  Ok = true;
460  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
461  A = R12;
462  D = R11;
463  E = R2;
464  Ok = true;
465  }
466  }
467 
468  // Bail if RHS was a icmp that can't be decomposed into an equality.
469  if (!ICmpInst::isEquality(PredR))
470  return 0;
471 
472  // Look for ANDs on the right side of the RHS icmp.
473  if (!Ok && R2->getType()->isIntegerTy()) {
474  if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
475  R11 = R2;
476  R12 = Constant::getAllOnesValue(R2->getType());
477  }
478 
479  if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
480  A = R11;
481  D = R12;
482  E = R1;
483  Ok = true;
484  } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
485  A = R12;
486  D = R11;
487  E = R1;
488  Ok = true;
489  } else {
490  return 0;
491  }
492  }
493  if (!Ok)
494  return 0;
495 
496  if (L11 == A) {
497  B = L12;
498  C = L2;
499  } else if (L12 == A) {
500  B = L11;
501  C = L2;
502  } else if (L21 == A) {
503  B = L22;
504  C = L1;
505  } else if (L22 == A) {
506  B = L21;
507  C = L1;
508  }
509 
510  unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
511  unsigned RightType = getMaskedICmpType(A, D, E, PredR);
512  return LeftType & RightType;
513 }
514 
515 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
516 /// into a single (icmp(A & X) ==/!= Y).
517 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
519  Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
520  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
521  unsigned Mask =
522  getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
523  if (Mask == 0)
524  return nullptr;
525 
527  "Expected equality predicates for masked type of icmps.");
528 
529  // In full generality:
530  // (icmp (A & B) Op C) | (icmp (A & D) Op E)
531  // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
532  //
533  // If the latter can be converted into (icmp (A & X) Op Y) then the former is
534  // equivalent to (icmp (A & X) !Op Y).
535  //
536  // Therefore, we can pretend for the rest of this function that we're dealing
537  // with the conjunction, provided we flip the sense of any comparisons (both
538  // input and output).
539 
540  // In most cases we're going to produce an EQ for the "&&" case.
542  if (!IsAnd) {
543  // Convert the masking analysis into its equivalent with negated
544  // comparisons.
545  Mask = conjugateICmpMask(Mask);
546  }
547 
548  if (Mask & Mask_AllZeros) {
549  // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
550  // -> (icmp eq (A & (B|D)), 0)
551  Value *NewOr = Builder.CreateOr(B, D);
552  Value *NewAnd = Builder.CreateAnd(A, NewOr);
553  // We can't use C as zero because we might actually handle
554  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
555  // with B and D, having a single bit set.
557  return Builder.CreateICmp(NewCC, NewAnd, Zero);
558  }
559  if (Mask & BMask_AllOnes) {
560  // (icmp eq (A & B), B) & (icmp eq (A & D), D)
561  // -> (icmp eq (A & (B|D)), (B|D))
562  Value *NewOr = Builder.CreateOr(B, D);
563  Value *NewAnd = Builder.CreateAnd(A, NewOr);
564  return Builder.CreateICmp(NewCC, NewAnd, NewOr);
565  }
566  if (Mask & AMask_AllOnes) {
567  // (icmp eq (A & B), A) & (icmp eq (A & D), A)
568  // -> (icmp eq (A & (B&D)), A)
569  Value *NewAnd1 = Builder.CreateAnd(B, D);
570  Value *NewAnd2 = Builder.CreateAnd(A, NewAnd1);
571  return Builder.CreateICmp(NewCC, NewAnd2, A);
572  }
573 
574  // Remaining cases assume at least that B and D are constant, and depend on
575  // their actual values. This isn't strictly necessary, just a "handle the
576  // easy cases for now" decision.
577  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
578  if (!BCst)
579  return nullptr;
580  ConstantInt *DCst = dyn_cast<ConstantInt>(D);
581  if (!DCst)
582  return nullptr;
583 
584  if (Mask & (Mask_NotAllZeros | BMask_NotAllOnes)) {
585  // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
586  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
587  // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
588  // Only valid if one of the masks is a superset of the other (check "B&D" is
589  // the same as either B or D).
590  APInt NewMask = BCst->getValue() & DCst->getValue();
591 
592  if (NewMask == BCst->getValue())
593  return LHS;
594  else if (NewMask == DCst->getValue())
595  return RHS;
596  }
597 
598  if (Mask & AMask_NotAllOnes) {
599  // (icmp ne (A & B), B) & (icmp ne (A & D), D)
600  // -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
601  // Only valid if one of the masks is a superset of the other (check "B|D" is
602  // the same as either B or D).
603  APInt NewMask = BCst->getValue() | DCst->getValue();
604 
605  if (NewMask == BCst->getValue())
606  return LHS;
607  else if (NewMask == DCst->getValue())
608  return RHS;
609  }
610 
611  if (Mask & BMask_Mixed) {
612  // (icmp eq (A & B), C) & (icmp eq (A & D), E)
613  // We already know that B & C == C && D & E == E.
614  // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
615  // C and E, which are shared by both the mask B and the mask D, don't
616  // contradict, then we can transform to
617  // -> (icmp eq (A & (B|D)), (C|E))
618  // Currently, we only handle the case of B, C, D, and E being constant.
619  // We can't simply use C and E because we might actually handle
620  // (icmp ne (A & B), B) & (icmp eq (A & D), D)
621  // with B and D, having a single bit set.
622  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
623  if (!CCst)
624  return nullptr;
625  ConstantInt *ECst = dyn_cast<ConstantInt>(E);
626  if (!ECst)
627  return nullptr;
628  if (PredL != NewCC)
629  CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst));
630  if (PredR != NewCC)
631  ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
632 
633  // If there is a conflict, we should actually return a false for the
634  // whole construct.
635  if (((BCst->getValue() & DCst->getValue()) &
636  (CCst->getValue() ^ ECst->getValue())).getBoolValue())
637  return ConstantInt::get(LHS->getType(), !IsAnd);
638 
639  Value *NewOr1 = Builder.CreateOr(B, D);
640  Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
641  Value *NewAnd = Builder.CreateAnd(A, NewOr1);
642  return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
643  }
644 
645  return nullptr;
646 }
647 
648 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
649 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
650 /// If \p Inverted is true then the check is for the inverted range, e.g.
651 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
653  bool Inverted) {
654  // Check the lower range comparison, e.g. x >= 0
655  // InstCombine already ensured that if there is a constant it's on the RHS.
656  ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
657  if (!RangeStart)
658  return nullptr;
659 
660  ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
661  Cmp0->getPredicate());
662 
663  // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
664  if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
665  (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
666  return nullptr;
667 
668  ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
669  Cmp1->getPredicate());
670 
671  Value *Input = Cmp0->getOperand(0);
672  Value *RangeEnd;
673  if (Cmp1->getOperand(0) == Input) {
674  // For the upper range compare we have: icmp x, n
675  RangeEnd = Cmp1->getOperand(1);
676  } else if (Cmp1->getOperand(1) == Input) {
677  // For the upper range compare we have: icmp n, x
678  RangeEnd = Cmp1->getOperand(0);
679  Pred1 = ICmpInst::getSwappedPredicate(Pred1);
680  } else {
681  return nullptr;
682  }
683 
684  // Check the upper range comparison, e.g. x < n
685  ICmpInst::Predicate NewPred;
686  switch (Pred1) {
687  case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
688  case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
689  default: return nullptr;
690  }
691 
692  // This simplification is only valid if the upper range is not negative.
693  KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1);
694  if (!Known.isNonNegative())
695  return nullptr;
696 
697  if (Inverted)
698  NewPred = ICmpInst::getInversePredicate(NewPred);
699 
700  return Builder.CreateICmp(NewPred, Input, RangeEnd);
701 }
702 
703 static Value *
705  bool JoinedByAnd,
706  InstCombiner::BuilderTy &Builder) {
707  Value *X = LHS->getOperand(0);
708  if (X != RHS->getOperand(0))
709  return nullptr;
710 
711  const APInt *C1, *C2;
712  if (!match(LHS->getOperand(1), m_APInt(C1)) ||
713  !match(RHS->getOperand(1), m_APInt(C2)))
714  return nullptr;
715 
716  // We only handle (X != C1 && X != C2) and (X == C1 || X == C2).
717  ICmpInst::Predicate Pred = LHS->getPredicate();
718  if (Pred != RHS->getPredicate())
719  return nullptr;
720  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
721  return nullptr;
722  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
723  return nullptr;
724 
725  // The larger unsigned constant goes on the right.
726  if (C1->ugt(*C2))
727  std::swap(C1, C2);
728 
729  APInt Xor = *C1 ^ *C2;
730  if (Xor.isPowerOf2()) {
731  // If LHSC and RHSC differ by only one bit, then set that bit in X and
732  // compare against the larger constant:
733  // (X == C1 || X == C2) --> (X | (C1 ^ C2)) == C2
734  // (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2
735  // We choose an 'or' with a Pow2 constant rather than the inverse mask with
736  // 'and' because that may lead to smaller codegen from a smaller constant.
737  Value *Or = Builder.CreateOr(X, ConstantInt::get(X->getType(), Xor));
738  return Builder.CreateICmp(Pred, Or, ConstantInt::get(X->getType(), *C2));
739  }
740 
741  // Special case: get the ordering right when the values wrap around zero.
742  // Ie, we assumed the constants were unsigned when swapping earlier.
743  if (C1->isNullValue() && C2->isAllOnesValue())
744  std::swap(C1, C2);
745 
746  if (*C1 == *C2 - 1) {
747  // (X == 13 || X == 14) --> X - 13 <=u 1
748  // (X != 13 && X != 14) --> X - 13 >u 1
749  // An 'add' is the canonical IR form, so favor that over a 'sub'.
750  Value *Add = Builder.CreateAdd(X, ConstantInt::get(X->getType(), -(*C1)));
751  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
752  return Builder.CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
753  }
754 
755  return nullptr;
756 }
757 
758 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
759 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
760 Value *InstCombiner::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
761  bool JoinedByAnd,
762  Instruction &CxtI) {
763  ICmpInst::Predicate Pred = LHS->getPredicate();
764  if (Pred != RHS->getPredicate())
765  return nullptr;
766  if (JoinedByAnd && Pred != ICmpInst::ICMP_NE)
767  return nullptr;
768  if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ)
769  return nullptr;
770 
771  // TODO support vector splats
772  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
773  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
774  if (!LHSC || !RHSC || !LHSC->isZero() || !RHSC->isZero())
775  return nullptr;
776 
777  Value *A, *B, *C, *D;
778  if (match(LHS->getOperand(0), m_And(m_Value(A), m_Value(B))) &&
779  match(RHS->getOperand(0), m_And(m_Value(C), m_Value(D)))) {
780  if (A == D || B == D)
781  std::swap(C, D);
782  if (B == C)
783  std::swap(A, B);
784 
785  if (A == C &&
786  isKnownToBeAPowerOfTwo(B, false, 0, &CxtI) &&
787  isKnownToBeAPowerOfTwo(D, false, 0, &CxtI)) {
788  Value *Mask = Builder.CreateOr(B, D);
789  Value *Masked = Builder.CreateAnd(A, Mask);
790  auto NewPred = JoinedByAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
791  return Builder.CreateICmp(NewPred, Masked, Mask);
792  }
793  }
794 
795  return nullptr;
796 }
797 
798 /// Fold (icmp)&(icmp) if possible.
799 Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
800  Instruction &CxtI) {
801  // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
802  // if K1 and K2 are a one-bit mask.
803  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, true, CxtI))
804  return V;
805 
806  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
807 
808  // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
809  if (PredicatesFoldable(PredL, PredR)) {
810  if (LHS->getOperand(0) == RHS->getOperand(1) &&
811  LHS->getOperand(1) == RHS->getOperand(0))
812  LHS->swapOperands();
813  if (LHS->getOperand(0) == RHS->getOperand(0) &&
814  LHS->getOperand(1) == RHS->getOperand(1)) {
815  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
816  unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
817  bool isSigned = LHS->isSigned() || RHS->isSigned();
818  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
819  }
820  }
821 
822  // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
823  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
824  return V;
825 
826  // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
827  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
828  return V;
829 
830  // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
831  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
832  return V;
833 
834  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
835  return V;
836 
837  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
838  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
839  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
840  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
841  if (!LHSC || !RHSC)
842  return nullptr;
843 
844  if (LHSC == RHSC && PredL == PredR) {
845  // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
846  // where C is a power of 2 or
847  // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
848  if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
849  (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) {
850  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
851  return Builder.CreateICmp(PredL, NewOr, LHSC);
852  }
853  }
854 
855  // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
856  // where CMAX is the all ones value for the truncated type,
857  // iff the lower bits of C2 and CA are zero.
858  if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() &&
859  RHS->hasOneUse()) {
860  Value *V;
861  ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr;
862 
863  // (trunc x) == C1 & (and x, CA) == C2
864  // (and x, CA) == C2 & (trunc x) == C1
865  if (match(RHS0, m_Trunc(m_Value(V))) &&
866  match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
867  SmallC = RHSC;
868  BigC = LHSC;
869  } else if (match(LHS0, m_Trunc(m_Value(V))) &&
870  match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) {
871  SmallC = LHSC;
872  BigC = RHSC;
873  }
874 
875  if (SmallC && BigC) {
876  unsigned BigBitSize = BigC->getType()->getBitWidth();
877  unsigned SmallBitSize = SmallC->getType()->getBitWidth();
878 
879  // Check that the low bits are zero.
880  APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
881  if ((Low & AndC->getValue()).isNullValue() &&
882  (Low & BigC->getValue()).isNullValue()) {
883  Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue());
884  APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue();
885  Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N);
886  return Builder.CreateICmp(PredL, NewAnd, NewVal);
887  }
888  }
889  }
890 
891  // From here on, we only handle:
892  // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
893  if (LHS0 != RHS0)
894  return nullptr;
895 
896  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
897  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
898  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
899  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
900  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
901  return nullptr;
902 
903  // We can't fold (ugt x, C) & (sgt x, C2).
904  if (!PredicatesFoldable(PredL, PredR))
905  return nullptr;
906 
907  // Ensure that the larger constant is on the RHS.
908  bool ShouldSwap;
909  if (CmpInst::isSigned(PredL) ||
910  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
911  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
912  else
913  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
914 
915  if (ShouldSwap) {
916  std::swap(LHS, RHS);
917  std::swap(LHSC, RHSC);
918  std::swap(PredL, PredR);
919  }
920 
921  // At this point, we know we have two icmp instructions
922  // comparing a value against two constants and and'ing the result
923  // together. Because of the above check, we know that we only have
924  // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
925  // (from the icmp folding check above), that the two constants
926  // are not equal and that the larger constant is on the RHS
927  assert(LHSC != RHSC && "Compares not folded above?");
928 
929  switch (PredL) {
930  default:
931  llvm_unreachable("Unknown integer condition code!");
932  case ICmpInst::ICMP_NE:
933  switch (PredR) {
934  default:
935  llvm_unreachable("Unknown integer condition code!");
936  case ICmpInst::ICMP_ULT:
937  if (LHSC == SubOne(RHSC)) // (X != 13 & X u< 14) -> X < 13
938  return Builder.CreateICmpULT(LHS0, LHSC);
939  if (LHSC->isZero()) // (X != 0 & X u< 14) -> X-1 u< 13
940  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
941  false, true);
942  break; // (X != 13 & X u< 15) -> no change
943  case ICmpInst::ICMP_SLT:
944  if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13
945  return Builder.CreateICmpSLT(LHS0, LHSC);
946  break; // (X != 13 & X s< 15) -> no change
947  case ICmpInst::ICMP_NE:
948  // Potential folds for this case should already be handled.
949  break;
950  }
951  break;
952  case ICmpInst::ICMP_UGT:
953  switch (PredR) {
954  default:
955  llvm_unreachable("Unknown integer condition code!");
956  case ICmpInst::ICMP_NE:
957  if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14
958  return Builder.CreateICmp(PredL, LHS0, RHSC);
959  break; // (X u> 13 & X != 15) -> no change
960  case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
961  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
962  false, true);
963  }
964  break;
965  case ICmpInst::ICMP_SGT:
966  switch (PredR) {
967  default:
968  llvm_unreachable("Unknown integer condition code!");
969  case ICmpInst::ICMP_NE:
970  if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14
971  return Builder.CreateICmp(PredL, LHS0, RHSC);
972  break; // (X s> 13 & X != 15) -> no change
973  case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
974  return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
975  true);
976  }
977  break;
978  }
979 
980  return nullptr;
981 }
982 
983 /// Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of instcombine, this returns
984 /// a Value which should already be inserted into the function.
985 Value *InstCombiner::foldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
986  Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
987  Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
988  FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
989 
990  if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
991  // Swap RHS operands to match LHS.
992  Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
993  std::swap(Op1LHS, Op1RHS);
994  }
995 
996  // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
997  // Suppose the relation between x and y is R, where R is one of
998  // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
999  // testing the desired relations.
1000  //
1001  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1002  // bool(R & CC0) && bool(R & CC1)
1003  // = bool((R & CC0) & (R & CC1))
1004  // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1005  if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
1006  return getFCmpValue(getFCmpCode(Op0CC) & getFCmpCode(Op1CC), Op0LHS, Op0RHS,
1007  Builder);
1008 
1009  if (LHS->getPredicate() == FCmpInst::FCMP_ORD &&
1010  RHS->getPredicate() == FCmpInst::FCMP_ORD) {
1011  if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType())
1012  return nullptr;
1013 
1014  // (fcmp ord x, c) & (fcmp ord y, c) -> (fcmp ord x, y)
1015  if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
1016  if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
1017  // If either of the constants are nans, then the whole thing returns
1018  // false.
1019  if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
1020  return Builder.getFalse();
1021  return Builder.CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
1022  }
1023 
1024  // Handle vector zeros. This occurs because the canonical form of
1025  // "fcmp ord x,x" is "fcmp ord x, 0".
1026  if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
1027  isa<ConstantAggregateZero>(RHS->getOperand(1)))
1028  return Builder.CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
1029  return nullptr;
1030  }
1031 
1032  return nullptr;
1033 }
1034 
1035 /// Match De Morgan's Laws:
1036 /// (~A & ~B) == (~(A | B))
1037 /// (~A | ~B) == (~(A & B))
1039  InstCombiner::BuilderTy &Builder) {
1040  auto Opcode = I.getOpcode();
1041  assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1042  "Trying to match De Morgan's Laws with something other than and/or");
1043 
1044  // Flip the logic operation.
1045  Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1046 
1047  Value *A, *B;
1048  if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) &&
1049  match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) &&
1050  !IsFreeToInvert(A, A->hasOneUse()) &&
1051  !IsFreeToInvert(B, B->hasOneUse())) {
1052  Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan");
1053  return BinaryOperator::CreateNot(AndOr);
1054  }
1055 
1056  return nullptr;
1057 }
1058 
1059 bool InstCombiner::shouldOptimizeCast(CastInst *CI) {
1060  Value *CastSrc = CI->getOperand(0);
1061 
1062  // Noop casts and casts of constants should be eliminated trivially.
1063  if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1064  return false;
1065 
1066  // If this cast is paired with another cast that can be eliminated, we prefer
1067  // to have it eliminated.
1068  if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1069  if (isEliminableCastPair(PrecedingCI, CI))
1070  return false;
1071 
1072  // If this is a vector sext from a compare, then we don't want to break the
1073  // idiom where each element of the extended vector is either zero or all ones.
1074  if (CI->getOpcode() == Instruction::SExt &&
1075  isa<CmpInst>(CastSrc) && CI->getDestTy()->isVectorTy())
1076  return false;
1077 
1078  return true;
1079 }
1080 
1081 /// Fold {and,or,xor} (cast X), C.
1083  InstCombiner::BuilderTy &Builder) {
1084  Constant *C;
1085  if (!match(Logic.getOperand(1), m_Constant(C)))
1086  return nullptr;
1087 
1088  auto LogicOpc = Logic.getOpcode();
1089  Type *DestTy = Logic.getType();
1090  Type *SrcTy = Cast->getSrcTy();
1091 
1092  // Move the logic operation ahead of a zext if the constant is unchanged in
1093  // the smaller source type. Performing the logic in a smaller type may provide
1094  // more information to later folds, and the smaller logic instruction may be
1095  // cheaper (particularly in the case of vectors).
1096  Value *X;
1097  if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1098  Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1099  Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1100  if (ZextTruncC == C) {
1101  // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1102  Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC);
1103  return new ZExtInst(NewOp, DestTy);
1104  }
1105  }
1106 
1107  return nullptr;
1108 }
1109 
1110 /// Fold {and,or,xor} (cast X), Y.
1111 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
1112  auto LogicOpc = I.getOpcode();
1113  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1114 
1115  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1116  CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1117  if (!Cast0)
1118  return nullptr;
1119 
1120  // This must be a cast from an integer or integer vector source type to allow
1121  // transformation of the logic operation to the source type.
1122  Type *DestTy = I.getType();
1123  Type *SrcTy = Cast0->getSrcTy();
1124  if (!SrcTy->isIntOrIntVectorTy())
1125  return nullptr;
1126 
1127  if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1128  return Ret;
1129 
1130  CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1131  if (!Cast1)
1132  return nullptr;
1133 
1134  // Both operands of the logic operation are casts. The casts must be of the
1135  // same type for reduction.
1136  auto CastOpcode = Cast0->getOpcode();
1137  if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
1138  return nullptr;
1139 
1140  Value *Cast0Src = Cast0->getOperand(0);
1141  Value *Cast1Src = Cast1->getOperand(0);
1142 
1143  // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1144  if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1145  Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1146  I.getName());
1147  return CastInst::Create(CastOpcode, NewOp, DestTy);
1148  }
1149 
1150  // For now, only 'and'/'or' have optimizations after this.
1151  if (LogicOpc == Instruction::Xor)
1152  return nullptr;
1153 
1154  // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
1155  // cast is otherwise not optimizable. This happens for vector sexts.
1156  ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1157  ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1158  if (ICmp0 && ICmp1) {
1159  Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I)
1160  : foldOrOfICmps(ICmp0, ICmp1, I);
1161  if (Res)
1162  return CastInst::Create(CastOpcode, Res, DestTy);
1163  return nullptr;
1164  }
1165 
1166  // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
1167  // cast is otherwise not optimizable. This happens for vector sexts.
1168  FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1169  FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1170  if (FCmp0 && FCmp1) {
1171  Value *Res = LogicOpc == Instruction::And ? foldAndOfFCmps(FCmp0, FCmp1)
1172  : foldOrOfFCmps(FCmp0, FCmp1);
1173  if (Res)
1174  return CastInst::Create(CastOpcode, Res, DestTy);
1175  return nullptr;
1176  }
1177 
1178  return nullptr;
1179 }
1180 
1182  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1183 
1184  // Canonicalize SExt or Not to the LHS
1185  if (match(Op1, m_SExt(m_Value())) || match(Op1, m_Not(m_Value()))) {
1186  std::swap(Op0, Op1);
1187  }
1188 
1189  // Fold (and (sext bool to A), B) --> (select bool, B, 0)
1190  Value *X = nullptr;
1191  if (match(Op0, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1192  Value *Zero = Constant::getNullValue(Op1->getType());
1193  return SelectInst::Create(X, Op1, Zero);
1194  }
1195 
1196  // Fold (and ~(sext bool to A), B) --> (select bool, 0, B)
1197  if (match(Op0, m_Not(m_SExt(m_Value(X)))) &&
1198  X->getType()->isIntOrIntVectorTy(1)) {
1200  return SelectInst::Create(X, Zero, Op1);
1201  }
1202 
1203  return nullptr;
1204 }
1205 
1207  InstCombiner::BuilderTy &Builder) {
1208  assert(I.getOpcode() == Instruction::And);
1209  Value *Op0 = I.getOperand(0);
1210  Value *Op1 = I.getOperand(1);
1211  Value *A, *B;
1212 
1213  // Operand complexity canonicalization guarantees that the 'or' is Op0.
1214  // (A | B) & ~(A & B) --> A ^ B
1215  // (A | B) & ~(B & A) --> A ^ B
1216  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1217  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B)))))
1218  return BinaryOperator::CreateXor(A, B);
1219 
1220  // (A | ~B) & (~A | B) --> ~(A ^ B)
1221  // (A | ~B) & (B | ~A) --> ~(A ^ B)
1222  // (~B | A) & (~A | B) --> ~(A ^ B)
1223  // (~B | A) & (B | ~A) --> ~(A ^ B)
1224  if (Op0->hasOneUse() || Op1->hasOneUse())
1225  if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
1226  match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B))))
1227  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1228 
1229  return nullptr;
1230 }
1231 
1233  InstCombiner::BuilderTy &Builder) {
1234  assert(I.getOpcode() == Instruction::Or);
1235  Value *Op0 = I.getOperand(0);
1236  Value *Op1 = I.getOperand(1);
1237  Value *A, *B;
1238 
1239  // Operand complexity canonicalization guarantees that the 'and' is Op0.
1240  // (A & B) | ~(A | B) --> ~(A ^ B)
1241  // (A & B) | ~(B | A) --> ~(A ^ B)
1242  if (Op0->hasOneUse() || Op1->hasOneUse())
1243  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1244  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
1245  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1246 
1247  // (A & ~B) | (~A & B) --> A ^ B
1248  // (A & ~B) | (B & ~A) --> A ^ B
1249  // (~B & A) | (~A & B) --> A ^ B
1250  // (~B & A) | (B & ~A) --> A ^ B
1251  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1252  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B))))
1253  return BinaryOperator::CreateXor(A, B);
1254 
1255  return nullptr;
1256 }
1257 
1258 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1259 // here. We should standardize that construct where it is needed or choose some
1260 // other way to ensure that commutated variants of patterns are not missed.
1262  bool Changed = SimplifyAssociativeOrCommutative(I);
1263  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1264 
1265  if (Value *V = SimplifyVectorOp(I))
1266  return replaceInstUsesWith(I, V);
1267 
1268  if (Value *V = SimplifyAndInst(Op0, Op1, SQ.getWithInstruction(&I)))
1269  return replaceInstUsesWith(I, V);
1270 
1271  // See if we can simplify any instructions used by the instruction whose sole
1272  // purpose is to compute bits we don't care about.
1273  if (SimplifyDemandedInstructionBits(I))
1274  return &I;
1275 
1276  // Do this before using distributive laws to catch simple and/or/not patterns.
1277  if (Instruction *Xor = foldAndToXor(I, Builder))
1278  return Xor;
1279 
1280  // (A|B)&(A|C) -> A|(B&C) etc
1281  if (Value *V = SimplifyUsingDistributiveLaws(I))
1282  return replaceInstUsesWith(I, V);
1283 
1284  if (Value *V = SimplifyBSwap(I, Builder))
1285  return replaceInstUsesWith(I, V);
1286 
1287  if (match(Op1, m_One())) {
1288  // (1 << x) & 1 --> zext(x == 0)
1289  // (1 >> x) & 1 --> zext(x == 0)
1290  Value *X;
1291  if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X))))) {
1292  Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(I.getType(), 0));
1293  return new ZExtInst(IsZero, I.getType());
1294  }
1295  }
1296 
1297  if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
1298  const APInt &AndRHSMask = AndRHS->getValue();
1299 
1300  // Optimize a variety of ((val OP C1) & C2) combinations...
1301  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1302  Value *Op0LHS = Op0I->getOperand(0);
1303  Value *Op0RHS = Op0I->getOperand(1);
1304  switch (Op0I->getOpcode()) {
1305  default: break;
1306  case Instruction::Xor:
1307  case Instruction::Or: {
1308  // If the mask is only needed on one incoming arm, push it up.
1309  if (!Op0I->hasOneUse()) break;
1310 
1311  APInt NotAndRHS(~AndRHSMask);
1312  if (MaskedValueIsZero(Op0LHS, NotAndRHS, 0, &I)) {
1313  // Not masking anything out for the LHS, move to RHS.
1314  Value *NewRHS = Builder.CreateAnd(Op0RHS, AndRHS,
1315  Op0RHS->getName()+".masked");
1316  return BinaryOperator::Create(Op0I->getOpcode(), Op0LHS, NewRHS);
1317  }
1318  if (!isa<Constant>(Op0RHS) &&
1319  MaskedValueIsZero(Op0RHS, NotAndRHS, 0, &I)) {
1320  // Not masking anything out for the RHS, move to LHS.
1321  Value *NewLHS = Builder.CreateAnd(Op0LHS, AndRHS,
1322  Op0LHS->getName()+".masked");
1323  return BinaryOperator::Create(Op0I->getOpcode(), NewLHS, Op0RHS);
1324  }
1325 
1326  break;
1327  }
1328  }
1329 
1330  // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth
1331  // of X and OP behaves well when given trunc(C1) and X.
1332  switch (Op0I->getOpcode()) {
1333  default:
1334  break;
1335  case Instruction::Xor:
1336  case Instruction::Or:
1337  case Instruction::Mul:
1338  case Instruction::Add:
1339  case Instruction::Sub:
1340  Value *X;
1341  ConstantInt *C1;
1342  if (match(Op0I, m_c_BinOp(m_ZExt(m_Value(X)), m_ConstantInt(C1)))) {
1343  if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) {
1344  auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType());
1345  Value *BinOp;
1346  if (isa<ZExtInst>(Op0LHS))
1347  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), X, TruncC1);
1348  else
1349  BinOp = Builder.CreateBinOp(Op0I->getOpcode(), TruncC1, X);
1350  auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType());
1351  auto *And = Builder.CreateAnd(BinOp, TruncC2);
1352  return new ZExtInst(And, I.getType());
1353  }
1354  }
1355  }
1356 
1357  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1358  if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1359  return Res;
1360  }
1361 
1362  // If this is an integer truncation, and if the source is an 'and' with
1363  // immediate, transform it. This frequently occurs for bitfield accesses.
1364  {
1365  Value *X = nullptr; ConstantInt *YC = nullptr;
1366  if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) {
1367  // Change: and (trunc (and X, YC) to T), C2
1368  // into : and (trunc X to T), trunc(YC) & C2
1369  // This will fold the two constants together, which may allow
1370  // other simplifications.
1371  Value *NewCast = Builder.CreateTrunc(X, I.getType(), "and.shrunk");
1372  Constant *C3 = ConstantExpr::getTrunc(YC, I.getType());
1373  C3 = ConstantExpr::getAnd(C3, AndRHS);
1374  return BinaryOperator::CreateAnd(NewCast, C3);
1375  }
1376  }
1377  }
1378 
1379  if (isa<Constant>(Op1))
1380  if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
1381  return FoldedLogic;
1382 
1383  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1384  return DeMorgan;
1385 
1386  {
1387  Value *A = nullptr, *B = nullptr, *C = nullptr;
1388  // A&(A^B) => A & ~B
1389  {
1390  Value *tmpOp0 = Op0;
1391  Value *tmpOp1 = Op1;
1392  if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
1393  if (A == Op1 || B == Op1 ) {
1394  tmpOp1 = Op0;
1395  tmpOp0 = Op1;
1396  // Simplify below
1397  }
1398  }
1399 
1400  if (match(tmpOp1, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
1401  if (B == tmpOp0) {
1402  std::swap(A, B);
1403  }
1404  // Notice that the pattern (A&(~B)) is actually (A&(-1^B)), so if
1405  // A is originally -1 (or a vector of -1 and undefs), then we enter
1406  // an endless loop. By checking that A is non-constant we ensure that
1407  // we will never get to the loop.
1408  if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B
1409  return BinaryOperator::CreateAnd(A, Builder.CreateNot(B));
1410  }
1411  }
1412 
1413  // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1414  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1415  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1416  if (Op1->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1417  return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C));
1418 
1419  // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1420  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1421  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1422  if (Op0->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
1423  return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
1424 
1425  // (A | B) & ((~A) ^ B) -> (A & B)
1426  // (A | B) & (B ^ (~A)) -> (A & B)
1427  // (B | A) & ((~A) ^ B) -> (A & B)
1428  // (B | A) & (B ^ (~A)) -> (A & B)
1429  if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1430  match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
1431  return BinaryOperator::CreateAnd(A, B);
1432 
1433  // ((~A) ^ B) & (A | B) -> (A & B)
1434  // ((~A) ^ B) & (B | A) -> (A & B)
1435  // (B ^ (~A)) & (A | B) -> (A & B)
1436  // (B ^ (~A)) & (B | A) -> (A & B)
1437  if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1438  match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
1439  return BinaryOperator::CreateAnd(A, B);
1440  }
1441 
1442  {
1443  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1444  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1445  if (LHS && RHS)
1446  if (Value *Res = foldAndOfICmps(LHS, RHS, I))
1447  return replaceInstUsesWith(I, Res);
1448 
1449  // TODO: Make this recursive; it's a little tricky because an arbitrary
1450  // number of 'and' instructions might have to be created.
1451  Value *X, *Y;
1452  if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1453  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1454  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1455  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1456  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1457  if (Value *Res = foldAndOfICmps(LHS, Cmp, I))
1458  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1459  }
1460  if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1461  if (auto *Cmp = dyn_cast<ICmpInst>(X))
1462  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1463  return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y));
1464  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1465  if (Value *Res = foldAndOfICmps(Cmp, RHS, I))
1466  return replaceInstUsesWith(I, Builder.CreateAnd(Res, X));
1467  }
1468  }
1469 
1470  // If and'ing two fcmp, try combine them into one.
1471  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
1472  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
1473  if (Value *Res = foldAndOfFCmps(LHS, RHS))
1474  return replaceInstUsesWith(I, Res);
1475 
1476  if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
1477  return CastedAnd;
1478 
1480  return Select;
1481 
1482  return Changed ? &I : nullptr;
1483 }
1484 
1485 /// Given an OR instruction, check to see if this is a bswap idiom. If so,
1486 /// insert the new intrinsic and return it.
1487 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
1488  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1489 
1490  // Look through zero extends.
1491  if (Instruction *Ext = dyn_cast<ZExtInst>(Op0))
1492  Op0 = Ext->getOperand(0);
1493 
1494  if (Instruction *Ext = dyn_cast<ZExtInst>(Op1))
1495  Op1 = Ext->getOperand(0);
1496 
1497  // (A | B) | C and A | (B | C) -> bswap if possible.
1498  bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
1499  match(Op1, m_Or(m_Value(), m_Value()));
1500 
1501  // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible.
1502  bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1503  match(Op1, m_LogicalShift(m_Value(), m_Value()));
1504 
1505  // (A & B) | (C & D) -> bswap if possible.
1506  bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
1507  match(Op1, m_And(m_Value(), m_Value()));
1508 
1509  if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
1510  return nullptr;
1511 
1513  if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
1514  return nullptr;
1515  Instruction *LastInst = Insts.pop_back_val();
1516  LastInst->removeFromParent();
1517 
1518  for (auto *Inst : Insts)
1519  Worklist.Add(Inst);
1520  return LastInst;
1521 }
1522 
1523 /// If all elements of two constant vectors are 0/-1 and inverses, return true.
1525  unsigned NumElts = C1->getType()->getVectorNumElements();
1526  for (unsigned i = 0; i != NumElts; ++i) {
1527  Constant *EltC1 = C1->getAggregateElement(i);
1528  Constant *EltC2 = C2->getAggregateElement(i);
1529  if (!EltC1 || !EltC2)
1530  return false;
1531 
1532  // One element must be all ones, and the other must be all zeros.
1533  // FIXME: Allow undef elements.
1534  if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
1535  (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
1536  return false;
1537  }
1538  return true;
1539 }
1540 
1541 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
1542 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
1543 /// B, it can be used as the condition operand of a select instruction.
1545  InstCombiner::BuilderTy &Builder) {
1546  // If these are scalars or vectors of i1, A can be used directly.
1547  Type *Ty = A->getType();
1548  if (match(A, m_Not(m_Specific(B))) && Ty->isIntOrIntVectorTy(1))
1549  return A;
1550 
1551  // If A and B are sign-extended, look through the sexts to find the booleans.
1552  Value *Cond;
1553  Value *NotB;
1554  if (match(A, m_SExt(m_Value(Cond))) &&
1555  Cond->getType()->isIntOrIntVectorTy(1) &&
1556  match(B, m_OneUse(m_Not(m_Value(NotB))))) {
1557  NotB = peekThroughBitcast(NotB, true);
1558  if (match(NotB, m_SExt(m_Specific(Cond))))
1559  return Cond;
1560  }
1561 
1562  // All scalar (and most vector) possibilities should be handled now.
1563  // Try more matches that only apply to non-splat constant vectors.
1564  if (!Ty->isVectorTy())
1565  return nullptr;
1566 
1567  // If both operands are constants, see if the constants are inverse bitmasks.
1568  Constant *AC, *BC;
1569  if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) &&
1570  areInverseVectorBitmasks(AC, BC))
1572 
1573  // If both operands are xor'd with constants using the same sexted boolean
1574  // operand, see if the constants are inverse bitmasks.
1575  if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) &&
1576  match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) &&
1577  Cond->getType()->isIntOrIntVectorTy(1) &&
1578  areInverseVectorBitmasks(AC, BC)) {
1580  return Builder.CreateXor(Cond, AC);
1581  }
1582  return nullptr;
1583 }
1584 
1585 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
1586 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
1588  InstCombiner::BuilderTy &Builder) {
1589  // The potential condition of the select may be bitcasted. In that case, look
1590  // through its bitcast and the corresponding bitcast of the 'not' condition.
1591  Type *OrigType = A->getType();
1592  A = peekThroughBitcast(A, true);
1593  B = peekThroughBitcast(B, true);
1594 
1595  if (Value *Cond = getSelectCondition(A, B, Builder)) {
1596  // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
1597  // The bitcasts will either all exist or all not exist. The builder will
1598  // not create unnecessary casts if the types already match.
1599  Value *BitcastC = Builder.CreateBitCast(C, A->getType());
1600  Value *BitcastD = Builder.CreateBitCast(D, A->getType());
1601  Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
1602  return Builder.CreateBitCast(Select, OrigType);
1603  }
1604 
1605  return nullptr;
1606 }
1607 
1608 /// Fold (icmp)|(icmp) if possible.
1609 Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1610  Instruction &CxtI) {
1611  // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
1612  // if K1 and K2 are a one-bit mask.
1613  if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, false, CxtI))
1614  return V;
1615 
1616  ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1617 
1618  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
1619  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
1620 
1621  // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
1622  // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
1623  // The original condition actually refers to the following two ranges:
1624  // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
1625  // We can fold these two ranges if:
1626  // 1) C1 and C2 is unsigned greater than C3.
1627  // 2) The two ranges are separated.
1628  // 3) C1 ^ C2 is one-bit mask.
1629  // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
1630  // This implies all values in the two ranges differ by exactly one bit.
1631 
1632  if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) &&
1633  PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() &&
1634  LHSC->getType() == RHSC->getType() &&
1635  LHSC->getValue() == (RHSC->getValue())) {
1636 
1637  Value *LAdd = LHS->getOperand(0);
1638  Value *RAdd = RHS->getOperand(0);
1639 
1640  Value *LAddOpnd, *RAddOpnd;
1641  ConstantInt *LAddC, *RAddC;
1642  if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddC))) &&
1643  match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddC))) &&
1644  LAddC->getValue().ugt(LHSC->getValue()) &&
1645  RAddC->getValue().ugt(LHSC->getValue())) {
1646 
1647  APInt DiffC = LAddC->getValue() ^ RAddC->getValue();
1648  if (LAddOpnd == RAddOpnd && DiffC.isPowerOf2()) {
1649  ConstantInt *MaxAddC = nullptr;
1650  if (LAddC->getValue().ult(RAddC->getValue()))
1651  MaxAddC = RAddC;
1652  else
1653  MaxAddC = LAddC;
1654 
1655  APInt RRangeLow = -RAddC->getValue();
1656  APInt RRangeHigh = RRangeLow + LHSC->getValue();
1657  APInt LRangeLow = -LAddC->getValue();
1658  APInt LRangeHigh = LRangeLow + LHSC->getValue();
1659  APInt LowRangeDiff = RRangeLow ^ LRangeLow;
1660  APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
1661  APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
1662  : RRangeLow - LRangeLow;
1663 
1664  if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
1665  RangeDiff.ugt(LHSC->getValue())) {
1666  Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC);
1667 
1668  Value *NewAnd = Builder.CreateAnd(LAddOpnd, MaskC);
1669  Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC);
1670  return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC);
1671  }
1672  }
1673  }
1674  }
1675 
1676  // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
1677  if (PredicatesFoldable(PredL, PredR)) {
1678  if (LHS->getOperand(0) == RHS->getOperand(1) &&
1679  LHS->getOperand(1) == RHS->getOperand(0))
1680  LHS->swapOperands();
1681  if (LHS->getOperand(0) == RHS->getOperand(0) &&
1682  LHS->getOperand(1) == RHS->getOperand(1)) {
1683  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1684  unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
1685  bool isSigned = LHS->isSigned() || RHS->isSigned();
1686  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
1687  }
1688  }
1689 
1690  // handle (roughly):
1691  // (icmp ne (A & B), C) | (icmp ne (A & D), E)
1692  if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
1693  return V;
1694 
1695  Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
1696  if (LHS->hasOneUse() || RHS->hasOneUse()) {
1697  // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
1698  // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
1699  Value *A = nullptr, *B = nullptr;
1700  if (PredL == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero()) {
1701  B = LHS0;
1702  if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS->getOperand(1))
1703  A = RHS0;
1704  else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0)
1705  A = RHS->getOperand(1);
1706  }
1707  // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
1708  // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
1709  else if (PredR == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) {
1710  B = RHS0;
1711  if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS->getOperand(1))
1712  A = LHS0;
1713  else if (PredL == ICmpInst::ICMP_UGT && LHS0 == RHS0)
1714  A = LHS->getOperand(1);
1715  }
1716  if (A && B)
1717  return Builder.CreateICmp(
1719  Builder.CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
1720  }
1721 
1722  // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
1723  if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
1724  return V;
1725 
1726  // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
1727  if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
1728  return V;
1729 
1730  if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
1731  return V;
1732 
1733  // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
1734  if (!LHSC || !RHSC)
1735  return nullptr;
1736 
1737  if (LHSC == RHSC && PredL == PredR) {
1738  // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
1739  if (PredL == ICmpInst::ICMP_NE && LHSC->isZero()) {
1740  Value *NewOr = Builder.CreateOr(LHS0, RHS0);
1741  return Builder.CreateICmp(PredL, NewOr, LHSC);
1742  }
1743  }
1744 
1745  // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
1746  // iff C2 + CA == C1.
1747  if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) {
1748  ConstantInt *AddC;
1749  if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC))))
1750  if (RHSC->getValue() + AddC->getValue() == LHSC->getValue())
1751  return Builder.CreateICmpULE(LHS0, LHSC);
1752  }
1753 
1754  // From here on, we only handle:
1755  // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
1756  if (LHS0 != RHS0)
1757  return nullptr;
1758 
1759  // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere.
1760  if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE ||
1761  PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE ||
1762  PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE ||
1763  PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE)
1764  return nullptr;
1765 
1766  // We can't fold (ugt x, C) | (sgt x, C2).
1767  if (!PredicatesFoldable(PredL, PredR))
1768  return nullptr;
1769 
1770  // Ensure that the larger constant is on the RHS.
1771  bool ShouldSwap;
1772  if (CmpInst::isSigned(PredL) ||
1773  (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR)))
1774  ShouldSwap = LHSC->getValue().sgt(RHSC->getValue());
1775  else
1776  ShouldSwap = LHSC->getValue().ugt(RHSC->getValue());
1777 
1778  if (ShouldSwap) {
1779  std::swap(LHS, RHS);
1780  std::swap(LHSC, RHSC);
1781  std::swap(PredL, PredR);
1782  }
1783 
1784  // At this point, we know we have two icmp instructions
1785  // comparing a value against two constants and or'ing the result
1786  // together. Because of the above check, we know that we only have
1787  // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
1788  // icmp folding check above), that the two constants are not
1789  // equal.
1790  assert(LHSC != RHSC && "Compares not folded above?");
1791 
1792  switch (PredL) {
1793  default:
1794  llvm_unreachable("Unknown integer condition code!");
1795  case ICmpInst::ICMP_EQ:
1796  switch (PredR) {
1797  default:
1798  llvm_unreachable("Unknown integer condition code!");
1799  case ICmpInst::ICMP_EQ:
1800  // Potential folds for this case should already be handled.
1801  break;
1802  case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
1803  case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
1804  break;
1805  }
1806  break;
1807  case ICmpInst::ICMP_ULT:
1808  switch (PredR) {
1809  default:
1810  llvm_unreachable("Unknown integer condition code!");
1811  case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
1812  break;
1813  case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
1814  assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
1815  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
1816  false, false);
1817  }
1818  break;
1819  case ICmpInst::ICMP_SLT:
1820  switch (PredR) {
1821  default:
1822  llvm_unreachable("Unknown integer condition code!");
1823  case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
1824  break;
1825  case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
1826  assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
1827  return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
1828  false);
1829  }
1830  break;
1831  }
1832  return nullptr;
1833 }
1834 
1835 /// Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of instcombine, this returns
1836 /// a Value which should already be inserted into the function.
1837 Value *InstCombiner::foldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
1838  Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
1839  Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
1840  FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
1841 
1842  if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
1843  // Swap RHS operands to match LHS.
1844  Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
1845  std::swap(Op1LHS, Op1RHS);
1846  }
1847 
1848  // Simplify (fcmp cc0 x, y) | (fcmp cc1 x, y).
1849  // This is a similar transformation to the one in FoldAndOfFCmps.
1850  //
1851  // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1852  // bool(R & CC0) || bool(R & CC1)
1853  // = bool((R & CC0) | (R & CC1))
1854  // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1855  if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
1856  return getFCmpValue(getFCmpCode(Op0CC) | getFCmpCode(Op1CC), Op0LHS, Op0RHS,
1857  Builder);
1858 
1859  if (LHS->getPredicate() == FCmpInst::FCMP_UNO &&
1860  RHS->getPredicate() == FCmpInst::FCMP_UNO &&
1861  LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType()) {
1862  if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
1863  if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
1864  // If either of the constants are nans, then the whole thing returns
1865  // true.
1866  if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
1867  return Builder.getTrue();
1868 
1869  // Otherwise, no need to compare the two constants, compare the
1870  // rest.
1871  return Builder.CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
1872  }
1873 
1874  // Handle vector zeros. This occurs because the canonical form of
1875  // "fcmp uno x,x" is "fcmp uno x, 0".
1876  if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
1877  isa<ConstantAggregateZero>(RHS->getOperand(1)))
1878  return Builder.CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
1879 
1880  return nullptr;
1881  }
1882 
1883  return nullptr;
1884 }
1885 
1886 /// This helper function folds:
1887 ///
1888 /// ((A | B) & C1) | (B & C2)
1889 ///
1890 /// into:
1891 ///
1892 /// (A & C1) | B
1893 ///
1894 /// when the XOR of the two constants is "all ones" (-1).
1896  Value *A, Value *B, Value *C,
1897  InstCombiner::BuilderTy &Builder) {
1898  ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
1899  if (!CI1) return nullptr;
1900 
1901  Value *V1 = nullptr;
1902  ConstantInt *CI2 = nullptr;
1903  if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) return nullptr;
1904 
1905  APInt Xor = CI1->getValue() ^ CI2->getValue();
1906  if (!Xor.isAllOnesValue()) return nullptr;
1907 
1908  if (V1 == A || V1 == B) {
1909  Value *NewOp = Builder.CreateAnd((V1 == A) ? B : A, CI1);
1910  return BinaryOperator::CreateOr(NewOp, V1);
1911  }
1912 
1913  return nullptr;
1914 }
1915 
1916 /// \brief This helper function folds:
1917 ///
1918 /// ((A ^ B) & C1) | (B & C2)
1919 ///
1920 /// into:
1921 ///
1922 /// (A & C1) ^ B
1923 ///
1924 /// when the XOR of the two constants is "all ones" (-1).
1926  Value *A, Value *B, Value *C,
1927  InstCombiner::BuilderTy &Builder) {
1928  ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
1929  if (!CI1)
1930  return nullptr;
1931 
1932  Value *V1 = nullptr;
1933  ConstantInt *CI2 = nullptr;
1934  if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2))))
1935  return nullptr;
1936 
1937  APInt Xor = CI1->getValue() ^ CI2->getValue();
1938  if (!Xor.isAllOnesValue())
1939  return nullptr;
1940 
1941  if (V1 == A || V1 == B) {
1942  Value *NewOp = Builder.CreateAnd(V1 == A ? B : A, CI1);
1943  return BinaryOperator::CreateXor(NewOp, V1);
1944  }
1945 
1946  return nullptr;
1947 }
1948 
1949 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
1950 // here. We should standardize that construct where it is needed or choose some
1951 // other way to ensure that commutated variants of patterns are not missed.
1953  bool Changed = SimplifyAssociativeOrCommutative(I);
1954  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1955 
1956  if (Value *V = SimplifyVectorOp(I))
1957  return replaceInstUsesWith(I, V);
1958 
1959  if (Value *V = SimplifyOrInst(Op0, Op1, SQ.getWithInstruction(&I)))
1960  return replaceInstUsesWith(I, V);
1961 
1962  // See if we can simplify any instructions used by the instruction whose sole
1963  // purpose is to compute bits we don't care about.
1964  if (SimplifyDemandedInstructionBits(I))
1965  return &I;
1966 
1967  // Do this before using distributive laws to catch simple and/or/not patterns.
1968  if (Instruction *Xor = foldOrToXor(I, Builder))
1969  return Xor;
1970 
1971  // (A&B)|(A&C) -> A&(B|C) etc
1972  if (Value *V = SimplifyUsingDistributiveLaws(I))
1973  return replaceInstUsesWith(I, V);
1974 
1975  if (Value *V = SimplifyBSwap(I, Builder))
1976  return replaceInstUsesWith(I, V);
1977 
1978  if (isa<Constant>(Op1))
1979  if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
1980  return FoldedLogic;
1981 
1982  // Given an OR instruction, check to see if this is a bswap.
1983  if (Instruction *BSwap = MatchBSwap(I))
1984  return BSwap;
1985 
1986  {
1987  Value *A;
1988  const APInt *C;
1989  // (X^C)|Y -> (X|Y)^C iff Y&C == 0
1990  if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
1991  MaskedValueIsZero(Op1, *C, 0, &I)) {
1992  Value *NOr = Builder.CreateOr(A, Op1);
1993  NOr->takeName(Op0);
1994  return BinaryOperator::CreateXor(NOr,
1995  ConstantInt::get(NOr->getType(), *C));
1996  }
1997 
1998  // Y|(X^C) -> (X|Y)^C iff Y&C == 0
1999  if (match(Op1, m_OneUse(m_Xor(m_Value(A), m_APInt(C)))) &&
2000  MaskedValueIsZero(Op0, *C, 0, &I)) {
2001  Value *NOr = Builder.CreateOr(A, Op0);
2002  NOr->takeName(Op0);
2003  return BinaryOperator::CreateXor(NOr,
2004  ConstantInt::get(NOr->getType(), *C));
2005  }
2006  }
2007 
2008  Value *A, *B;
2009 
2010  // (A & C)|(B & D)
2011  Value *C = nullptr, *D = nullptr;
2012  if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2013  match(Op1, m_And(m_Value(B), m_Value(D)))) {
2014  Value *V1 = nullptr, *V2 = nullptr;
2017  if (C1 && C2) { // (A & C1)|(B & C2)
2018  if ((C1->getValue() & C2->getValue()).isNullValue()) {
2019  // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
2020  // iff (C1&C2) == 0 and (N&~C1) == 0
2021  if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
2022  ((V1 == B &&
2023  MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2024  (V2 == B &&
2025  MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
2026  return BinaryOperator::CreateAnd(A,
2027  Builder.getInt(C1->getValue()|C2->getValue()));
2028  // Or commutes, try both ways.
2029  if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
2030  ((V1 == A &&
2031  MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2032  (V2 == A &&
2033  MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
2034  return BinaryOperator::CreateAnd(B,
2035  Builder.getInt(C1->getValue()|C2->getValue()));
2036 
2037  // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
2038  // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
2039  ConstantInt *C3 = nullptr, *C4 = nullptr;
2040  if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2041  (C3->getValue() & ~C1->getValue()).isNullValue() &&
2042  match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2043  (C4->getValue() & ~C2->getValue()).isNullValue()) {
2044  V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2045  return BinaryOperator::CreateAnd(V2,
2046  Builder.getInt(C1->getValue()|C2->getValue()));
2047  }
2048  }
2049  }
2050 
2051  // Don't try to form a select if it's unlikely that we'll get rid of at
2052  // least one of the operands. A select is generally more expensive than the
2053  // 'or' that it is replacing.
2054  if (Op0->hasOneUse() || Op1->hasOneUse()) {
2055  // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2056  if (Value *V = matchSelectFromAndOr(A, C, B, D, Builder))
2057  return replaceInstUsesWith(I, V);
2058  if (Value *V = matchSelectFromAndOr(A, C, D, B, Builder))
2059  return replaceInstUsesWith(I, V);
2060  if (Value *V = matchSelectFromAndOr(C, A, B, D, Builder))
2061  return replaceInstUsesWith(I, V);
2062  if (Value *V = matchSelectFromAndOr(C, A, D, B, Builder))
2063  return replaceInstUsesWith(I, V);
2064  if (Value *V = matchSelectFromAndOr(B, D, A, C, Builder))
2065  return replaceInstUsesWith(I, V);
2066  if (Value *V = matchSelectFromAndOr(B, D, C, A, Builder))
2067  return replaceInstUsesWith(I, V);
2068  if (Value *V = matchSelectFromAndOr(D, B, A, C, Builder))
2069  return replaceInstUsesWith(I, V);
2070  if (Value *V = matchSelectFromAndOr(D, B, C, A, Builder))
2071  return replaceInstUsesWith(I, V);
2072  }
2073 
2074  // ((A|B)&1)|(B&-2) -> (A&1) | B
2075  if (match(A, m_c_Or(m_Value(V1), m_Specific(B)))) {
2076  if (Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C, Builder))
2077  return Ret;
2078  }
2079  // (B&-2)|((A|B)&1) -> (A&1) | B
2080  if (match(B, m_c_Or(m_Specific(A), m_Value(V1)))) {
2081  if (Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D, Builder))
2082  return Ret;
2083  }
2084  // ((A^B)&1)|(B&-2) -> (A&1) ^ B
2085  if (match(A, m_c_Xor(m_Value(V1), m_Specific(B)))) {
2086  if (Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C, Builder))
2087  return Ret;
2088  }
2089  // (B&-2)|((A^B)&1) -> (A&1) ^ B
2090  if (match(B, m_c_Xor(m_Specific(A), m_Value(V1)))) {
2091  if (Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D, Builder))
2092  return Ret;
2093  }
2094  }
2095 
2096  // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2097  if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2098  if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2099  return BinaryOperator::CreateOr(Op0, C);
2100 
2101  // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2102  if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2103  if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2104  return BinaryOperator::CreateOr(Op1, C);
2105 
2106  // ((B | C) & A) | B -> B | (A & C)
2107  if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2108  return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
2109 
2110  if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2111  return DeMorgan;
2112 
2113  // Canonicalize xor to the RHS.
2114  bool SwappedForXor = false;
2115  if (match(Op0, m_Xor(m_Value(), m_Value()))) {
2116  std::swap(Op0, Op1);
2117  SwappedForXor = true;
2118  }
2119 
2120  // A | ( A ^ B) -> A | B
2121  // A | (~A ^ B) -> A | ~B
2122  // (A & B) | (A ^ B)
2123  if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2124  if (Op0 == A || Op0 == B)
2125  return BinaryOperator::CreateOr(A, B);
2126 
2127  if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2128  match(Op0, m_And(m_Specific(B), m_Specific(A))))
2129  return BinaryOperator::CreateOr(A, B);
2130 
2131  if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2132  Value *Not = Builder.CreateNot(B, B->getName() + ".not");
2133  return BinaryOperator::CreateOr(Not, Op0);
2134  }
2135  if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2136  Value *Not = Builder.CreateNot(A, A->getName() + ".not");
2137  return BinaryOperator::CreateOr(Not, Op0);
2138  }
2139  }
2140 
2141  // A | ~(A | B) -> A | ~B
2142  // A | ~(A ^ B) -> A | ~B
2143  if (match(Op1, m_Not(m_Value(A))))
2144  if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
2145  if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2146  Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2147  B->getOpcode() == Instruction::Xor)) {
2148  Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2149  B->getOperand(0);
2150  Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not");
2151  return BinaryOperator::CreateOr(Not, Op0);
2152  }
2153 
2154  if (SwappedForXor)
2155  std::swap(Op0, Op1);
2156 
2157  {
2158  ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2159  ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2160  if (LHS && RHS)
2161  if (Value *Res = foldOrOfICmps(LHS, RHS, I))
2162  return replaceInstUsesWith(I, Res);
2163 
2164  // TODO: Make this recursive; it's a little tricky because an arbitrary
2165  // number of 'or' instructions might have to be created.
2166  Value *X, *Y;
2167  if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2168  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2169  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2170  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2171  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2172  if (Value *Res = foldOrOfICmps(LHS, Cmp, I))
2173  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2174  }
2175  if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2176  if (auto *Cmp = dyn_cast<ICmpInst>(X))
2177  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2178  return replaceInstUsesWith(I, Builder.CreateOr(Res, Y));
2179  if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2180  if (Value *Res = foldOrOfICmps(Cmp, RHS, I))
2181  return replaceInstUsesWith(I, Builder.CreateOr(Res, X));
2182  }
2183  }
2184 
2185  // (fcmp uno x, c) | (fcmp uno y, c) -> (fcmp uno x, y)
2186  if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2187  if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2188  if (Value *Res = foldOrOfFCmps(LHS, RHS))
2189  return replaceInstUsesWith(I, Res);
2190 
2191  if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2192  return CastedOr;
2193 
2194  // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
2195  if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
2196  A->getType()->isIntOrIntVectorTy(1))
2197  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
2198  if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
2199  A->getType()->isIntOrIntVectorTy(1))
2200  return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2201 
2202  // Note: If we've gotten to the point of visiting the outer OR, then the
2203  // inner one couldn't be simplified. If it was a constant, then it won't
2204  // be simplified by a later pass either, so we try swapping the inner/outer
2205  // ORs in the hopes that we'll be able to simplify it this way.
2206  // (X|C) | V --> (X|V) | C
2207  ConstantInt *C1;
2208  if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
2209  match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) {
2210  Value *Inner = Builder.CreateOr(A, Op1);
2211  Inner->takeName(Op0);
2212  return BinaryOperator::CreateOr(Inner, C1);
2213  }
2214 
2215  // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2216  // Since this OR statement hasn't been optimized further yet, we hope
2217  // that this transformation will allow the new ORs to be optimized.
2218  {
2219  Value *X = nullptr, *Y = nullptr;
2220  if (Op0->hasOneUse() && Op1->hasOneUse() &&
2221  match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2222  match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2223  Value *orTrue = Builder.CreateOr(A, C);
2224  Value *orFalse = Builder.CreateOr(B, D);
2225  return SelectInst::Create(X, orTrue, orFalse);
2226  }
2227  }
2228 
2229  return Changed ? &I : nullptr;
2230 }
2231 
2232 /// A ^ B can be specified using other logic ops in a variety of patterns. We
2233 /// can fold these early and efficiently by morphing an existing instruction.
2235  InstCombiner::BuilderTy &Builder) {
2236  assert(I.getOpcode() == Instruction::Xor);
2237  Value *Op0 = I.getOperand(0);
2238  Value *Op1 = I.getOperand(1);
2239  Value *A, *B;
2240 
2241  // There are 4 commuted variants for each of the basic patterns.
2242 
2243  // (A & B) ^ (A | B) -> A ^ B
2244  // (A & B) ^ (B | A) -> A ^ B
2245  // (A | B) ^ (A & B) -> A ^ B
2246  // (A | B) ^ (B & A) -> A ^ B
2247  if ((match(Op0, m_And(m_Value(A), m_Value(B))) &&
2248  match(Op1, m_c_Or(m_Specific(A), m_Specific(B)))) ||
2249  (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2250  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))) {
2251  I.setOperand(0, A);
2252  I.setOperand(1, B);
2253  return &I;
2254  }
2255 
2256  // (A | ~B) ^ (~A | B) -> A ^ B
2257  // (~B | A) ^ (~A | B) -> A ^ B
2258  // (~A | B) ^ (A | ~B) -> A ^ B
2259  // (B | ~A) ^ (A | ~B) -> A ^ B
2260  if ((match(Op0, m_Or(m_Value(A), m_Not(m_Value(B)))) &&
2261  match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B)))) ||
2262  (match(Op0, m_Or(m_Not(m_Value(A)), m_Value(B))) &&
2263  match(Op1, m_c_Or(m_Specific(A), m_Not(m_Specific(B)))))) {
2264  I.setOperand(0, A);
2265  I.setOperand(1, B);
2266  return &I;
2267  }
2268 
2269  // (A & ~B) ^ (~A & B) -> A ^ B
2270  // (~B & A) ^ (~A & B) -> A ^ B
2271  // (~A & B) ^ (A & ~B) -> A ^ B
2272  // (B & ~A) ^ (A & ~B) -> A ^ B
2273  if ((match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
2274  match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))) ||
2275  (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
2276  match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))))) {
2277  I.setOperand(0, A);
2278  I.setOperand(1, B);
2279  return &I;
2280  }
2281 
2282  // For the remaining cases we need to get rid of one of the operands.
2283  if (!Op0->hasOneUse() && !Op1->hasOneUse())
2284  return nullptr;
2285 
2286  // (A | B) ^ ~(A & B) -> ~(A ^ B)
2287  // (A | B) ^ ~(B & A) -> ~(A ^ B)
2288  // (A & B) ^ ~(A | B) -> ~(A ^ B)
2289  // (A & B) ^ ~(B | A) -> ~(A ^ B)
2290  // Complexity sorting ensures the not will be on the right side.
2291  if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2292  match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
2293  (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2294  match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
2295  return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
2296 
2297  return nullptr;
2298 }
2299 
2300 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
2301  if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2302  if (LHS->getOperand(0) == RHS->getOperand(1) &&
2303  LHS->getOperand(1) == RHS->getOperand(0))
2304  LHS->swapOperands();
2305  if (LHS->getOperand(0) == RHS->getOperand(0) &&
2306  LHS->getOperand(1) == RHS->getOperand(1)) {
2307  // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2308  Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2309  unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2310  bool isSigned = LHS->isSigned() || RHS->isSigned();
2311  return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
2312  }
2313  }
2314 
2315  // Instead of trying to imitate the folds for and/or, decompose this 'xor'
2316  // into those logic ops. That is, try to turn this into an and-of-icmps
2317  // because we have many folds for that pattern.
2318  //
2319  // This is based on a truth table definition of xor:
2320  // X ^ Y --> (X | Y) & !(X & Y)
2321  if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
2322  // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
2323  // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
2324  if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
2325  // TODO: Independently handle cases where the 'and' side is a constant.
2326  if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
2327  // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
2328  RHS->setPredicate(RHS->getInversePredicate());
2329  return Builder.CreateAnd(LHS, RHS);
2330  }
2331  if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
2332  // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
2333  LHS->setPredicate(LHS->getInversePredicate());
2334  return Builder.CreateAnd(LHS, RHS);
2335  }
2336  }
2337  }
2338 
2339  return nullptr;
2340 }
2341 
2342 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2343 // here. We should standardize that construct where it is needed or choose some
2344 // other way to ensure that commutated variants of patterns are not missed.
2346  bool Changed = SimplifyAssociativeOrCommutative(I);
2347  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2348 
2349  if (Value *V = SimplifyVectorOp(I))
2350  return replaceInstUsesWith(I, V);
2351 
2352  if (Value *V = SimplifyXorInst(Op0, Op1, SQ.getWithInstruction(&I)))
2353  return replaceInstUsesWith(I, V);
2354 
2355  if (Instruction *NewXor = foldXorToXor(I, Builder))
2356  return NewXor;
2357 
2358  // (A&B)^(A&C) -> A&(B^C) etc
2359  if (Value *V = SimplifyUsingDistributiveLaws(I))
2360  return replaceInstUsesWith(I, V);
2361 
2362  // See if we can simplify any instructions used by the instruction whose sole
2363  // purpose is to compute bits we don't care about.
2364  if (SimplifyDemandedInstructionBits(I))
2365  return &I;
2366 
2367  if (Value *V = SimplifyBSwap(I, Builder))
2368  return replaceInstUsesWith(I, V);
2369 
2370  // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
2371  Value *X, *Y;
2372 
2373  // We must eliminate the and/or (one-use) for these transforms to not increase
2374  // the instruction count.
2375  // ~(~X & Y) --> (X | ~Y)
2376  // ~(Y & ~X) --> (X | ~Y)
2377  if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) {
2378  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2379  return BinaryOperator::CreateOr(X, NotY);
2380  }
2381  // ~(~X | Y) --> (X & ~Y)
2382  // ~(Y | ~X) --> (X & ~Y)
2383  if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) {
2384  Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
2385  return BinaryOperator::CreateAnd(X, NotY);
2386  }
2387 
2388  // Is this a 'not' (~) fed by a binary operator?
2389  BinaryOperator *NotVal;
2390  if (match(&I, m_Not(m_BinOp(NotVal)))) {
2391  if (NotVal->getOpcode() == Instruction::And ||
2392  NotVal->getOpcode() == Instruction::Or) {
2393  // Apply DeMorgan's Law when inverts are free:
2394  // ~(X & Y) --> (~X | ~Y)
2395  // ~(X | Y) --> (~X & ~Y)
2396  if (IsFreeToInvert(NotVal->getOperand(0),
2397  NotVal->getOperand(0)->hasOneUse()) &&
2398  IsFreeToInvert(NotVal->getOperand(1),
2399  NotVal->getOperand(1)->hasOneUse())) {
2400  Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs");
2401  Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs");
2402  if (NotVal->getOpcode() == Instruction::And)
2403  return BinaryOperator::CreateOr(NotX, NotY);
2404  return BinaryOperator::CreateAnd(NotX, NotY);
2405  }
2406  }
2407 
2408  // ~(~X >>s Y) --> (X >>s Y)
2409  if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
2410  return BinaryOperator::CreateAShr(X, Y);
2411 
2412  // If we are inverting a right-shifted constant, we may be able to eliminate
2413  // the 'not' by inverting the constant and using the opposite shift type.
2414  // Canonicalization rules ensure that only a negative constant uses 'ashr',
2415  // but we must check that in case that transform has not fired yet.
2416  const APInt *C;
2417  if (match(NotVal, m_AShr(m_APInt(C), m_Value(Y))) && C->isNegative()) {
2418  // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
2419  Constant *NotC = ConstantInt::get(I.getType(), ~(*C));
2420  return BinaryOperator::CreateLShr(NotC, Y);
2421  }
2422 
2423  if (match(NotVal, m_LShr(m_APInt(C), m_Value(Y))) && C->isNonNegative()) {
2424  // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
2425  Constant *NotC = ConstantInt::get(I.getType(), ~(*C));
2426  return BinaryOperator::CreateAShr(NotC, Y);
2427  }
2428  }
2429 
2430  // not (cmp A, B) = !cmp A, B
2431  CmpInst::Predicate Pred;
2432  if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) {
2433  cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred));
2434  return replaceInstUsesWith(I, Op0);
2435  }
2436 
2437  if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
2438  // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp).
2439  if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) {
2440  if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) {
2441  if (CI->hasOneUse() && Op0C->hasOneUse()) {
2442  Instruction::CastOps Opcode = Op0C->getOpcode();
2443  if ((Opcode == Instruction::ZExt || Opcode == Instruction::SExt) &&
2444  (RHSC == ConstantExpr::getCast(Opcode, Builder.getTrue(),
2445  Op0C->getDestTy()))) {
2446  CI->setPredicate(CI->getInversePredicate());
2447  return CastInst::Create(Opcode, CI, Op0C->getType());
2448  }
2449  }
2450  }
2451  }
2452 
2453  if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2454  // ~(c-X) == X-c-1 == X+(-c-1)
2455  if (Op0I->getOpcode() == Instruction::Sub && RHSC->isMinusOne())
2456  if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
2457  Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
2458  return BinaryOperator::CreateAdd(Op0I->getOperand(1),
2459  SubOne(NegOp0I0C));
2460  }
2461 
2462  if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2463  if (Op0I->getOpcode() == Instruction::Add) {
2464  // ~(X-c) --> (-c-1)-X
2465  if (RHSC->isMinusOne()) {
2466  Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
2467  return BinaryOperator::CreateSub(SubOne(NegOp0CI),
2468  Op0I->getOperand(0));
2469  } else if (RHSC->getValue().isSignMask()) {
2470  // (X + C) ^ signmask -> (X + C + signmask)
2471  Constant *C = Builder.getInt(RHSC->getValue() + Op0CI->getValue());
2472  return BinaryOperator::CreateAdd(Op0I->getOperand(0), C);
2473 
2474  }
2475  } else if (Op0I->getOpcode() == Instruction::Or) {
2476  // (X|C1)^C2 -> X^(C1|C2) iff X&~C1 == 0
2477  if (MaskedValueIsZero(Op0I->getOperand(0), Op0CI->getValue(),
2478  0, &I)) {
2479  Constant *NewRHS = ConstantExpr::getOr(Op0CI, RHSC);
2480  // Anything in both C1 and C2 is known to be zero, remove it from
2481  // NewRHS.
2482  Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHSC);
2483  NewRHS = ConstantExpr::getAnd(NewRHS,
2484  ConstantExpr::getNot(CommonBits));
2485  Worklist.Add(Op0I);
2486  I.setOperand(0, Op0I->getOperand(0));
2487  I.setOperand(1, NewRHS);
2488  return &I;
2489  }
2490  } else if (Op0I->getOpcode() == Instruction::LShr) {
2491  // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
2492  // E1 = "X ^ C1"
2493  BinaryOperator *E1;
2494  ConstantInt *C1;
2495  if (Op0I->hasOneUse() &&
2496  (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
2497  E1->getOpcode() == Instruction::Xor &&
2498  (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
2499  // fold (C1 >> C2) ^ C3
2500  ConstantInt *C2 = Op0CI, *C3 = RHSC;
2501  APInt FoldConst = C1->getValue().lshr(C2->getValue());
2502  FoldConst ^= C3->getValue();
2503  // Prepare the two operands.
2504  Value *Opnd0 = Builder.CreateLShr(E1->getOperand(0), C2);
2505  Opnd0->takeName(Op0I);
2506  cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
2507  Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
2508 
2509  return BinaryOperator::CreateXor(Opnd0, FoldVal);
2510  }
2511  }
2512  }
2513  }
2514  }
2515 
2516  if (isa<Constant>(Op1))
2517  if (Instruction *FoldedLogic = foldOpWithConstantIntoOperand(I))
2518  return FoldedLogic;
2519 
2520  {
2521  Value *A, *B;
2522  if (match(Op1, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2523  if (A == Op0) { // A^(A|B) == A^(B|A)
2524  cast<BinaryOperator>(Op1)->swapOperands();
2525  std::swap(A, B);
2526  }
2527  if (B == Op0) { // A^(B|A) == (B|A)^A
2528  I.swapOperands(); // Simplified below.
2529  std::swap(Op0, Op1);
2530  }
2531  } else if (match(Op1, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2532  if (A == Op0) { // A^(A&B) -> A^(B&A)
2533  cast<BinaryOperator>(Op1)->swapOperands();
2534  std::swap(A, B);
2535  }
2536  if (B == Op0) { // A^(B&A) -> (B&A)^A
2537  I.swapOperands(); // Simplified below.
2538  std::swap(Op0, Op1);
2539  }
2540  }
2541  }
2542 
2543  {
2544  Value *A, *B;
2545  if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B))))) {
2546  if (A == Op1) // (B|A)^B == (A|B)^B
2547  std::swap(A, B);
2548  if (B == Op1) // (A|B)^B == A & ~B
2549  return BinaryOperator::CreateAnd(A, Builder.CreateNot(Op1));
2550  } else if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B))))) {
2551  if (A == Op1) // (A&B)^A -> (B&A)^A
2552  std::swap(A, B);
2553  const APInt *C;
2554  if (B == Op1 && // (B&A)^A == ~B & A
2555  !match(Op1, m_APInt(C))) { // Canonical form is (B&C)^C
2556  return BinaryOperator::CreateAnd(Builder.CreateNot(A), Op1);
2557  }
2558  }
2559  }
2560 
2561  {
2562  Value *A, *B, *C, *D;
2563  // (A ^ C)^(A | B) -> ((~A) & B) ^ C
2564  if (match(Op0, m_Xor(m_Value(D), m_Value(C))) &&
2565  match(Op1, m_Or(m_Value(A), m_Value(B)))) {
2566  if (D == A)
2567  return BinaryOperator::CreateXor(
2568  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2569  if (D == B)
2570  return BinaryOperator::CreateXor(
2571  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2572  }
2573  // (A | B)^(A ^ C) -> ((~A) & B) ^ C
2574  if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
2575  match(Op1, m_Xor(m_Value(D), m_Value(C)))) {
2576  if (D == A)
2577  return BinaryOperator::CreateXor(
2578  Builder.CreateAnd(Builder.CreateNot(A), B), C);
2579  if (D == B)
2580  return BinaryOperator::CreateXor(
2581  Builder.CreateAnd(Builder.CreateNot(B), A), C);
2582  }
2583  // (A & B) ^ (A ^ B) -> (A | B)
2584  if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2585  match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
2586  return BinaryOperator::CreateOr(A, B);
2587  // (A ^ B) ^ (A & B) -> (A | B)
2588  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2589  match(Op1, m_c_And(m_Specific(A), m_Specific(B))))
2590  return BinaryOperator::CreateOr(A, B);
2591  }
2592 
2593  // (A & ~B) ^ ~A -> ~(A & B)
2594  // (~B & A) ^ ~A -> ~(A & B)
2595  Value *A, *B;
2596  if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
2597  match(Op1, m_Not(m_Specific(A))))
2598  return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
2599 
2600  if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
2601  if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
2602  if (Value *V = foldXorOfICmps(LHS, RHS))
2603  return replaceInstUsesWith(I, V);
2604 
2605  if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
2606  return CastedXor;
2607 
2608  return Changed ? &I : nullptr;
2609 }
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:550
uint64_t CallInst * C
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:172
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to have exactly one bit set when defined. ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1634
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:850
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Type * getSrcTy() const
Return the source type, as a convenience.
Definition: InstrTypes.h:825
static bool IsFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
static Value * getFCmpValue(unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp inst...
Instruction * visitXor(BinaryOperator &I)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1108
Instruction * visitOr(BinaryOperator &I)
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1074
bool decomposeBitTestICmp(const ICmpInst *I, CmpInst::Predicate &Pred, Value *&X, Value *&Y, Value *&Z)
Decompose an icmp into the form ((X & Y) pred Z) if possible.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1095
match_zero m_Zero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:145
static unsigned getFCmpCode(FCmpInst::Predicate CC)
Similar to getICmpCode but for FCmpInst.
This class represents zero extension of integer types.
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
static bool areInverseVectorBitmasks(Constant *C1, Constant *C2)
If all elements of two constant vectors are 0/-1 and inverses, return true.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:865
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:641
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
unsigned less or equal
Definition: InstrTypes.h:886
unsigned less than
Definition: InstrTypes.h:885
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:580
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:866
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:876
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1253
MaskedICmpType
Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified...
static Value * SimplifyBSwap(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
#define R2(n)
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1218
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
static bool isBitwiseLogicOp(unsigned Opcode)
Determine if the Opcode is and/or/xor.
Definition: Instruction.h:156
Value * SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Or, fold the result or return null.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:742
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
bool swapOperands()
Exchange the two operands to this instruction.
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:871
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:870
bool isSigned() const
Determine if this instruction is using a signed comparison.
Definition: InstrTypes.h:1001
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:562
static Instruction * FoldXorWithConstants(BinaryOperator &I, Value *Op, Value *A, Value *B, Value *C, InstCombiner::BuilderTy &Builder)
This helper function folds:
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:958
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:362
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:888
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
static Constant * AddOne(Constant *C)
Add one to a Constant.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:867
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:889
not_match< LHS > m_Not(const LHS &L)
Definition: PatternMatch.h:961
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:478
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1570
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1444
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:820
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:900
This instruction compares its operands according to the predicate given to the constructor.
static Instruction * FoldOrWithConstants(BinaryOperator &I, Value *Op, Value *A, Value *B, Value *C, InstCombiner::BuilderTy &Builder)
This helper function folds:
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
static Value * foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:203
SelectClass_match< Cond, LHS, RHS > m_Select(const Cond &C, const LHS &L, const RHS &R)
Definition: PatternMatch.h:845
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:66
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
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:975
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:154
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1079
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:277
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:629
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1641
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:357
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:574
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:240
static Value * getSelectCondition(Value *A, Value *B, InstCombiner::BuilderTy &Builder)
We have an expression of the form (A & C) | (B & D).
static unsigned getMaskedICmpType(Value *A, Value *B, Value *C, ICmpInst::Predicate Pred)
Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C) satisfies.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:556
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1164
This is an important base class in LLVM.
Definition: Constant.h:42
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.h:1689
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)
Return true if &#39;V & Mask&#39; is known to be zero.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
static Constant * getAnd(Constant *C1, Constant *C2)
Definition: Constants.cpp:2174
#define A
Definition: LargeTest.cpp:12
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:264
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:358
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:436
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:860
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:869
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
static unsigned conjugateICmpMask(unsigned Mask)
Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite s...
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition: APInt.h:443
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2109
static Constant * getAllOnesValue(Type *Ty)
Get the all ones value.
Definition: Constants.cpp:261
1 1 1 1 Always true (always folded)
Definition: InstrTypes.h:877
static Value * getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
void swapOperands()
Exchange the two operands to this instruction in such a way that it does not modify the semantics of ...
static Instruction * matchDeMorgansLaws(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Match De Morgan&#39;s Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B))
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:875
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static Instruction * foldBoolSextMaskToSelect(BinaryOperator &I)
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:959
signed greater than
Definition: InstrTypes.h:887
Instruction * visitAnd(BinaryOperator &I)
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:894
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:864
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
Definition: Constants.h:251
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
#define B
Definition: LargeTest.cpp:24
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:874
signed less than
Definition: InstrTypes.h:889
const size_t N
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1542
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:560
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:574
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:827
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2)
Return true if both predicates match sign or if at least one of them is an equality comparison (which...
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:939
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
signed less or equal
Definition: InstrTypes.h:890
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1202
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:457
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1435
void removeFromParent()
This method unlinks &#39;this&#39; from the containing basic block, but does not delete it.
Definition: Instruction.cpp:65
static Instruction * foldAndToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2096
Value * SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
static Value * foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, llvm::InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)...
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
static unsigned getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR)
Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1234
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:934
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:280
Value * getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, CmpInst::Predicate &NewICmpPred)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
unsigned greater or equal
Definition: InstrTypes.h:884
match_one m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:194
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
bool isEquality() const
Return true if this predicate is either EQ or NE.
#define I(x, y, z)
Definition: MD5.cpp:58
static Constant * getOr(Constant *C1, Constant *C2)
Definition: Constants.cpp:2178
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:868
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Value * SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
static volatile int Zero
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:872
APInt byteSwap() const
Definition: APInt.cpp:617
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1063
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:430
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
match_all_ones m_AllOnes()
Match an integer or vector with all bits set to true.
Definition: PatternMatch.h:205
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:863
LLVM Value Representation.
Definition: Value.h:73
This file provides internal interfaces used to implement the InstCombine.
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:873
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:408
unsigned greater than
Definition: InstrTypes.h:883
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:974
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
Value * simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction *> &InsertedInsts)
Try and match a bswap or bitreverse idiom.
Definition: Local.cpp:2074
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:865
static Value * matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D, InstCombiner::BuilderTy &Builder)
We have an expression of the form (A & C) | (B & D).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
Fold {and,or,xor} (cast X), C.
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
#define D
Definition: LargeTest.cpp:26
static Instruction * foldXorToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
A ^ B can be specified using other logic ops in a variety of patterns.
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
0 0 0 0 Always false (always folded)
Definition: InstrTypes.h:862
signed greater or equal
Definition: InstrTypes.h:888
static Constant * getXor(Constant *C1, Constant *C2)
Definition: Constants.cpp:2182
CallInst * CreateCall(Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1659