LLVM 19.0.0git
InstCombineAndOrXor.cpp
Go to the documentation of this file.
1//===- InstCombineAndOrXor.cpp --------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the visitAnd, visitOr, and visitXor functions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InstCombineInternal.h"
17#include "llvm/IR/Intrinsics.h"
21
22using namespace llvm;
23using namespace PatternMatch;
24
25#define DEBUG_TYPE "instcombine"
26
27/// This is the complement of getICmpCode, which turns an opcode and two
28/// operands into either a constant true or false, or a brand new ICmp
29/// instruction. The sign is passed in to determine which kind of predicate to
30/// use in the new icmp instruction.
31static Value *getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS,
32 InstCombiner::BuilderTy &Builder) {
33 ICmpInst::Predicate NewPred;
34 if (Constant *TorF = getPredForICmpCode(Code, Sign, LHS->getType(), NewPred))
35 return TorF;
36 return Builder.CreateICmp(NewPred, LHS, RHS);
37}
38
39/// This is the complement of getFCmpCode, which turns an opcode and two
40/// operands into either a FCmp instruction, or a true/false constant.
41static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
42 InstCombiner::BuilderTy &Builder) {
43 FCmpInst::Predicate NewPred;
44 if (Constant *TorF = getPredForFCmpCode(Code, LHS->getType(), NewPred))
45 return TorF;
46 return Builder.CreateFCmp(NewPred, LHS, RHS);
47}
48
49/// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
50/// (V < Lo || V >= Hi). This method expects that Lo < Hi. IsSigned indicates
51/// whether to treat V, Lo, and Hi as signed or not.
53 const APInt &Hi, bool isSigned,
54 bool Inside) {
55 assert((isSigned ? Lo.slt(Hi) : Lo.ult(Hi)) &&
56 "Lo is not < Hi in range emission code!");
57
58 Type *Ty = V->getType();
59
60 // V >= Min && V < Hi --> V < Hi
61 // V < Min || V >= Hi --> V >= Hi
63 if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
64 Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
65 return Builder.CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
66 }
67
68 // V >= Lo && V < Hi --> V - Lo u< Hi - Lo
69 // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo
70 Value *VMinusLo =
71 Builder.CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
72 Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
73 return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo);
74}
75
76/// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns
77/// that can be simplified.
78/// One of A and B is considered the mask. The other is the value. This is
79/// described as the "AMask" or "BMask" part of the enum. If the enum contains
80/// only "Mask", then both A and B can be considered masks. If A is the mask,
81/// then it was proven that (A & C) == C. This is trivial if C == A or C == 0.
82/// If both A and C are constants, this proof is also easy.
83/// For the following explanations, we assume that A is the mask.
84///
85/// "AllOnes" declares that the comparison is true only if (A & B) == A or all
86/// bits of A are set in B.
87/// Example: (icmp eq (A & 3), 3) -> AMask_AllOnes
88///
89/// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all
90/// bits of A are cleared in B.
91/// Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes
92///
93/// "Mixed" declares that (A & B) == C and C might or might not contain any
94/// number of one bits and zero bits.
95/// Example: (icmp eq (A & 3), 1) -> AMask_Mixed
96///
97/// "Not" means that in above descriptions "==" should be replaced by "!=".
98/// Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes
99///
100/// If the mask A contains a single bit, then the following is equivalent:
101/// (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
102/// (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
113 BMask_NotMixed = 512
115
116/// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C)
117/// satisfies.
118static unsigned getMaskedICmpType(Value *A, Value *B, Value *C,
119 ICmpInst::Predicate Pred) {
120 const APInt *ConstA = nullptr, *ConstB = nullptr, *ConstC = nullptr;
121 match(A, m_APInt(ConstA));
122 match(B, m_APInt(ConstB));
123 match(C, m_APInt(ConstC));
124 bool IsEq = (Pred == ICmpInst::ICMP_EQ);
125 bool IsAPow2 = ConstA && ConstA->isPowerOf2();
126 bool IsBPow2 = ConstB && ConstB->isPowerOf2();
127 unsigned MaskVal = 0;
128 if (ConstC && ConstC->isZero()) {
129 // if C is zero, then both A and B qualify as mask
130 MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed)
132 if (IsAPow2)
133 MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed)
135 if (IsBPow2)
136 MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed)
138 return MaskVal;
139 }
140
141 if (A == C) {
142 MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed)
144 if (IsAPow2)
145 MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed)
147 } else if (ConstA && ConstC && ConstC->isSubsetOf(*ConstA)) {
148 MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed);
149 }
150
151 if (B == C) {
152 MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed)
154 if (IsBPow2)
155 MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed)
157 } else if (ConstB && ConstC && ConstC->isSubsetOf(*ConstB)) {
158 MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed);
159 }
160
161 return MaskVal;
162}
163
164/// Convert an analysis of a masked ICmp into its equivalent if all boolean
165/// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
166/// is adjacent to the corresponding normal flag (recording ==), this just
167/// involves swapping those bits over.
168static unsigned conjugateICmpMask(unsigned Mask) {
169 unsigned NewMask;
170 NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros |
172 << 1;
173
174 NewMask |= (Mask & (AMask_NotAllOnes | BMask_NotAllOnes | Mask_NotAllZeros |
176 >> 1;
177
178 return NewMask;
179}
180
181// Adapts the external decomposeBitTestICmp for local use.
183 Value *&X, Value *&Y, Value *&Z) {
184 APInt Mask;
185 if (!llvm::decomposeBitTestICmp(LHS, RHS, Pred, X, Mask))
186 return false;
187
188 Y = ConstantInt::get(X->getType(), Mask);
189 Z = ConstantInt::get(X->getType(), 0);
190 return true;
191}
192
193/// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
194/// Return the pattern classes (from MaskedICmpType) for the left hand side and
195/// the right hand side as a pair.
196/// LHS and RHS are the left hand side and the right hand side ICmps and PredL
197/// and PredR are their predicates, respectively.
198static std::optional<std::pair<unsigned, unsigned>> getMaskedTypeForICmpPair(
199 Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS,
200 ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR) {
201 // Don't allow pointers. Splat vectors are fine.
202 if (!LHS->getOperand(0)->getType()->isIntOrIntVectorTy() ||
203 !RHS->getOperand(0)->getType()->isIntOrIntVectorTy())
204 return std::nullopt;
205
206 // Here comes the tricky part:
207 // LHS might be of the form L11 & L12 == X, X == L21 & L22,
208 // and L11 & L12 == L21 & L22. The same goes for RHS.
209 // Now we must find those components L** and R**, that are equal, so
210 // that we can extract the parameters A, B, C, D, and E for the canonical
211 // above.
212 Value *L1 = LHS->getOperand(0);
213 Value *L2 = LHS->getOperand(1);
214 Value *L11, *L12, *L21, *L22;
215 // Check whether the icmp can be decomposed into a bit test.
216 if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) {
217 L21 = L22 = L1 = nullptr;
218 } else {
219 // Look for ANDs in the LHS icmp.
220 if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
221 // Any icmp can be viewed as being trivially masked; if it allows us to
222 // remove one, it's worth it.
223 L11 = L1;
225 }
226
227 if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
228 L21 = L2;
230 }
231 }
232
233 // Bail if LHS was a icmp that can't be decomposed into an equality.
234 if (!ICmpInst::isEquality(PredL))
235 return std::nullopt;
236
237 Value *R1 = RHS->getOperand(0);
238 Value *R2 = RHS->getOperand(1);
239 Value *R11, *R12;
240 bool Ok = false;
241 if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) {
242 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
243 A = R11;
244 D = R12;
245 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
246 A = R12;
247 D = R11;
248 } else {
249 return std::nullopt;
250 }
251 E = R2;
252 R1 = nullptr;
253 Ok = true;
254 } else {
255 if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
256 // As before, model no mask as a trivial mask if it'll let us do an
257 // optimization.
258 R11 = R1;
260 }
261
262 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
263 A = R11;
264 D = R12;
265 E = R2;
266 Ok = true;
267 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
268 A = R12;
269 D = R11;
270 E = R2;
271 Ok = true;
272 }
273 }
274
275 // Bail if RHS was a icmp that can't be decomposed into an equality.
276 if (!ICmpInst::isEquality(PredR))
277 return std::nullopt;
278
279 // Look for ANDs on the right side of the RHS icmp.
280 if (!Ok) {
281 if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
282 R11 = R2;
283 R12 = Constant::getAllOnesValue(R2->getType());
284 }
285
286 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
287 A = R11;
288 D = R12;
289 E = R1;
290 Ok = true;
291 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
292 A = R12;
293 D = R11;
294 E = R1;
295 Ok = true;
296 } else {
297 return std::nullopt;
298 }
299
300 assert(Ok && "Failed to find AND on the right side of the RHS icmp.");
301 }
302
303 if (L11 == A) {
304 B = L12;
305 C = L2;
306 } else if (L12 == A) {
307 B = L11;
308 C = L2;
309 } else if (L21 == A) {
310 B = L22;
311 C = L1;
312 } else if (L22 == A) {
313 B = L21;
314 C = L1;
315 }
316
317 unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
318 unsigned RightType = getMaskedICmpType(A, D, E, PredR);
319 return std::optional<std::pair<unsigned, unsigned>>(
320 std::make_pair(LeftType, RightType));
321}
322
323/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single
324/// (icmp(A & X) ==/!= Y), where the left-hand side is of type Mask_NotAllZeros
325/// and the right hand side is of type BMask_Mixed. For example,
326/// (icmp (A & 12) != 0) & (icmp (A & 15) == 8) -> (icmp (A & 15) == 8).
327/// Also used for logical and/or, must be poison safe.
329 ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C,
331 InstCombiner::BuilderTy &Builder) {
332 // We are given the canonical form:
333 // (icmp ne (A & B), 0) & (icmp eq (A & D), E).
334 // where D & E == E.
335 //
336 // If IsAnd is false, we get it in negated form:
337 // (icmp eq (A & B), 0) | (icmp ne (A & D), E) ->
338 // !((icmp ne (A & B), 0) & (icmp eq (A & D), E)).
339 //
340 // We currently handle the case of B, C, D, E are constant.
341 //
342 const APInt *BCst, *CCst, *DCst, *OrigECst;
343 if (!match(B, m_APInt(BCst)) || !match(C, m_APInt(CCst)) ||
344 !match(D, m_APInt(DCst)) || !match(E, m_APInt(OrigECst)))
345 return nullptr;
346
348
349 // Update E to the canonical form when D is a power of two and RHS is
350 // canonicalized as,
351 // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or
352 // (icmp ne (A & D), D) -> (icmp eq (A & D), 0).
353 APInt ECst = *OrigECst;
354 if (PredR != NewCC)
355 ECst ^= *DCst;
356
357 // If B or D is zero, skip because if LHS or RHS can be trivially folded by
358 // other folding rules and this pattern won't apply any more.
359 if (*BCst == 0 || *DCst == 0)
360 return nullptr;
361
362 // If B and D don't intersect, ie. (B & D) == 0, no folding because we can't
363 // deduce anything from it.
364 // For example,
365 // (icmp ne (A & 12), 0) & (icmp eq (A & 3), 1) -> no folding.
366 if ((*BCst & *DCst) == 0)
367 return nullptr;
368
369 // If the following two conditions are met:
370 //
371 // 1. mask B covers only a single bit that's not covered by mask D, that is,
372 // (B & (B ^ D)) is a power of 2 (in other words, B minus the intersection of
373 // B and D has only one bit set) and,
374 //
375 // 2. RHS (and E) indicates that the rest of B's bits are zero (in other
376 // words, the intersection of B and D is zero), that is, ((B & D) & E) == 0
377 //
378 // then that single bit in B must be one and thus the whole expression can be
379 // folded to
380 // (A & (B | D)) == (B & (B ^ D)) | E.
381 //
382 // For example,
383 // (icmp ne (A & 12), 0) & (icmp eq (A & 7), 1) -> (icmp eq (A & 15), 9)
384 // (icmp ne (A & 15), 0) & (icmp eq (A & 7), 0) -> (icmp eq (A & 15), 8)
385 if ((((*BCst & *DCst) & ECst) == 0) &&
386 (*BCst & (*BCst ^ *DCst)).isPowerOf2()) {
387 APInt BorD = *BCst | *DCst;
388 APInt BandBxorDorE = (*BCst & (*BCst ^ *DCst)) | ECst;
389 Value *NewMask = ConstantInt::get(A->getType(), BorD);
390 Value *NewMaskedValue = ConstantInt::get(A->getType(), BandBxorDorE);
391 Value *NewAnd = Builder.CreateAnd(A, NewMask);
392 return Builder.CreateICmp(NewCC, NewAnd, NewMaskedValue);
393 }
394
395 auto IsSubSetOrEqual = [](const APInt *C1, const APInt *C2) {
396 return (*C1 & *C2) == *C1;
397 };
398 auto IsSuperSetOrEqual = [](const APInt *C1, const APInt *C2) {
399 return (*C1 & *C2) == *C2;
400 };
401
402 // In the following, we consider only the cases where B is a superset of D, B
403 // is a subset of D, or B == D because otherwise there's at least one bit
404 // covered by B but not D, in which case we can't deduce much from it, so
405 // no folding (aside from the single must-be-one bit case right above.)
406 // For example,
407 // (icmp ne (A & 14), 0) & (icmp eq (A & 3), 1) -> no folding.
408 if (!IsSubSetOrEqual(BCst, DCst) && !IsSuperSetOrEqual(BCst, DCst))
409 return nullptr;
410
411 // At this point, either B is a superset of D, B is a subset of D or B == D.
412
413 // If E is zero, if B is a subset of (or equal to) D, LHS and RHS contradict
414 // and the whole expression becomes false (or true if negated), otherwise, no
415 // folding.
416 // For example,
417 // (icmp ne (A & 3), 0) & (icmp eq (A & 7), 0) -> false.
418 // (icmp ne (A & 15), 0) & (icmp eq (A & 3), 0) -> no folding.
419 if (ECst.isZero()) {
420 if (IsSubSetOrEqual(BCst, DCst))
421 return ConstantInt::get(LHS->getType(), !IsAnd);
422 return nullptr;
423 }
424
425 // At this point, B, D, E aren't zero and (B & D) == B, (B & D) == D or B ==
426 // D. If B is a superset of (or equal to) D, since E is not zero, LHS is
427 // subsumed by RHS (RHS implies LHS.) So the whole expression becomes
428 // RHS. For example,
429 // (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
430 // (icmp ne (A & 15), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
431 if (IsSuperSetOrEqual(BCst, DCst))
432 return RHS;
433 // Otherwise, B is a subset of D. If B and E have a common bit set,
434 // ie. (B & E) != 0, then LHS is subsumed by RHS. For example.
435 // (icmp ne (A & 12), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
436 assert(IsSubSetOrEqual(BCst, DCst) && "Precondition due to above code");
437 if ((*BCst & ECst) != 0)
438 return RHS;
439 // Otherwise, LHS and RHS contradict and the whole expression becomes false
440 // (or true if negated.) For example,
441 // (icmp ne (A & 7), 0) & (icmp eq (A & 15), 8) -> false.
442 // (icmp ne (A & 6), 0) & (icmp eq (A & 15), 8) -> false.
443 return ConstantInt::get(LHS->getType(), !IsAnd);
444}
445
446/// Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single
447/// (icmp(A & X) ==/!= Y), where the left-hand side and the right hand side
448/// aren't of the common mask pattern type.
449/// Also used for logical and/or, must be poison safe.
451 ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C,
453 unsigned LHSMask, unsigned RHSMask, InstCombiner::BuilderTy &Builder) {
455 "Expected equality predicates for masked type of icmps.");
456 // Handle Mask_NotAllZeros-BMask_Mixed cases.
457 // (icmp ne/eq (A & B), C) &/| (icmp eq/ne (A & D), E), or
458 // (icmp eq/ne (A & B), C) &/| (icmp ne/eq (A & D), E)
459 // which gets swapped to
460 // (icmp ne/eq (A & D), E) &/| (icmp eq/ne (A & B), C).
461 if (!IsAnd) {
462 LHSMask = conjugateICmpMask(LHSMask);
463 RHSMask = conjugateICmpMask(RHSMask);
464 }
465 if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) {
467 LHS, RHS, IsAnd, A, B, C, D, E,
468 PredL, PredR, Builder)) {
469 return V;
470 }
471 } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) {
473 RHS, LHS, IsAnd, A, D, E, B, C,
474 PredR, PredL, Builder)) {
475 return V;
476 }
477 }
478 return nullptr;
479}
480
481/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
482/// into a single (icmp(A & X) ==/!= Y).
483static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
484 bool IsLogical,
485 InstCombiner::BuilderTy &Builder) {
486 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
487 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
488 std::optional<std::pair<unsigned, unsigned>> MaskPair =
489 getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
490 if (!MaskPair)
491 return nullptr;
493 "Expected equality predicates for masked type of icmps.");
494 unsigned LHSMask = MaskPair->first;
495 unsigned RHSMask = MaskPair->second;
496 unsigned Mask = LHSMask & RHSMask;
497 if (Mask == 0) {
498 // Even if the two sides don't share a common pattern, check if folding can
499 // still happen.
501 LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
502 Builder))
503 return V;
504 return nullptr;
505 }
506
507 // In full generality:
508 // (icmp (A & B) Op C) | (icmp (A & D) Op E)
509 // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
510 //
511 // If the latter can be converted into (icmp (A & X) Op Y) then the former is
512 // equivalent to (icmp (A & X) !Op Y).
513 //
514 // Therefore, we can pretend for the rest of this function that we're dealing
515 // with the conjunction, provided we flip the sense of any comparisons (both
516 // input and output).
517
518 // In most cases we're going to produce an EQ for the "&&" case.
520 if (!IsAnd) {
521 // Convert the masking analysis into its equivalent with negated
522 // comparisons.
523 Mask = conjugateICmpMask(Mask);
524 }
525
526 if (Mask & Mask_AllZeros) {
527 // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
528 // -> (icmp eq (A & (B|D)), 0)
529 if (IsLogical && !isGuaranteedNotToBeUndefOrPoison(D))
530 return nullptr; // TODO: Use freeze?
531 Value *NewOr = Builder.CreateOr(B, D);
532 Value *NewAnd = Builder.CreateAnd(A, NewOr);
533 // We can't use C as zero because we might actually handle
534 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
535 // with B and D, having a single bit set.
536 Value *Zero = Constant::getNullValue(A->getType());
537 return Builder.CreateICmp(NewCC, NewAnd, Zero);
538 }
539 if (Mask & BMask_AllOnes) {
540 // (icmp eq (A & B), B) & (icmp eq (A & D), D)
541 // -> (icmp eq (A & (B|D)), (B|D))
542 if (IsLogical && !isGuaranteedNotToBeUndefOrPoison(D))
543 return nullptr; // TODO: Use freeze?
544 Value *NewOr = Builder.CreateOr(B, D);
545 Value *NewAnd = Builder.CreateAnd(A, NewOr);
546 return Builder.CreateICmp(NewCC, NewAnd, NewOr);
547 }
548 if (Mask & AMask_AllOnes) {
549 // (icmp eq (A & B), A) & (icmp eq (A & D), A)
550 // -> (icmp eq (A & (B&D)), A)
551 if (IsLogical && !isGuaranteedNotToBeUndefOrPoison(D))
552 return nullptr; // TODO: Use freeze?
553 Value *NewAnd1 = Builder.CreateAnd(B, D);
554 Value *NewAnd2 = Builder.CreateAnd(A, NewAnd1);
555 return Builder.CreateICmp(NewCC, NewAnd2, A);
556 }
557
558 // Remaining cases assume at least that B and D are constant, and depend on
559 // their actual values. This isn't strictly necessary, just a "handle the
560 // easy cases for now" decision.
561 const APInt *ConstB, *ConstD;
562 if (!match(B, m_APInt(ConstB)) || !match(D, m_APInt(ConstD)))
563 return nullptr;
564
565 if (Mask & (Mask_NotAllZeros | BMask_NotAllOnes)) {
566 // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
567 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
568 // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
569 // Only valid if one of the masks is a superset of the other (check "B&D" is
570 // the same as either B or D).
571 APInt NewMask = *ConstB & *ConstD;
572 if (NewMask == *ConstB)
573 return LHS;
574 else if (NewMask == *ConstD)
575 return RHS;
576 }
577
578 if (Mask & AMask_NotAllOnes) {
579 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
580 // -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
581 // Only valid if one of the masks is a superset of the other (check "B|D" is
582 // the same as either B or D).
583 APInt NewMask = *ConstB | *ConstD;
584 if (NewMask == *ConstB)
585 return LHS;
586 else if (NewMask == *ConstD)
587 return RHS;
588 }
589
590 if (Mask & (BMask_Mixed | BMask_NotMixed)) {
591 // Mixed:
592 // (icmp eq (A & B), C) & (icmp eq (A & D), E)
593 // We already know that B & C == C && D & E == E.
594 // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
595 // C and E, which are shared by both the mask B and the mask D, don't
596 // contradict, then we can transform to
597 // -> (icmp eq (A & (B|D)), (C|E))
598 // Currently, we only handle the case of B, C, D, and E being constant.
599 // We can't simply use C and E because we might actually handle
600 // (icmp ne (A & B), B) & (icmp eq (A & D), D)
601 // with B and D, having a single bit set.
602
603 // NotMixed:
604 // (icmp ne (A & B), C) & (icmp ne (A & D), E)
605 // -> (icmp ne (A & (B & D)), (C & E))
606 // Check the intersection (B & D) for inequality.
607 // Assume that (B & D) == B || (B & D) == D, i.e B/D is a subset of D/B
608 // and (B & D) & (C ^ E) == 0, bits of C and E, which are shared by both the
609 // B and the D, don't contradict.
610 // Note that we can assume (~B & C) == 0 && (~D & E) == 0, previous
611 // operation should delete these icmps if it hadn't been met.
612
613 const APInt *OldConstC, *OldConstE;
614 if (!match(C, m_APInt(OldConstC)) || !match(E, m_APInt(OldConstE)))
615 return nullptr;
616
617 auto FoldBMixed = [&](ICmpInst::Predicate CC, bool IsNot) -> Value * {
619 const APInt ConstC = PredL != CC ? *ConstB ^ *OldConstC : *OldConstC;
620 const APInt ConstE = PredR != CC ? *ConstD ^ *OldConstE : *OldConstE;
621
622 if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
623 return IsNot ? nullptr : ConstantInt::get(LHS->getType(), !IsAnd);
624
625 if (IsNot && !ConstB->isSubsetOf(*ConstD) && !ConstD->isSubsetOf(*ConstB))
626 return nullptr;
627
628 APInt BD, CE;
629 if (IsNot) {
630 BD = *ConstB & *ConstD;
631 CE = ConstC & ConstE;
632 } else {
633 BD = *ConstB | *ConstD;
634 CE = ConstC | ConstE;
635 }
636 Value *NewAnd = Builder.CreateAnd(A, BD);
637 Value *CEVal = ConstantInt::get(A->getType(), CE);
638 return Builder.CreateICmp(CC, CEVal, NewAnd);
639 };
640
641 if (Mask & BMask_Mixed)
642 return FoldBMixed(NewCC, false);
643 if (Mask & BMask_NotMixed) // can be else also
644 return FoldBMixed(NewCC, true);
645 }
646 return nullptr;
647}
648
649/// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
650/// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
651/// If \p Inverted is true then the check is for the inverted range, e.g.
652/// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
654 bool Inverted) {
655 // Check the lower range comparison, e.g. x >= 0
656 // InstCombine already ensured that if there is a constant it's on the RHS.
657 ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
658 if (!RangeStart)
659 return nullptr;
660
661 ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
662 Cmp0->getPredicate());
663
664 // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
665 if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
666 (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
667 return nullptr;
668
669 ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
670 Cmp1->getPredicate());
671
672 Value *Input = Cmp0->getOperand(0);
673 Value *RangeEnd;
674 if (Cmp1->getOperand(0) == Input) {
675 // For the upper range compare we have: icmp x, n
676 RangeEnd = Cmp1->getOperand(1);
677 } else if (Cmp1->getOperand(1) == Input) {
678 // For the upper range compare we have: icmp n, x
679 RangeEnd = Cmp1->getOperand(0);
680 Pred1 = ICmpInst::getSwappedPredicate(Pred1);
681 } else {
682 return nullptr;
683 }
684
685 // Check the upper range comparison, e.g. x < n
686 ICmpInst::Predicate NewPred;
687 switch (Pred1) {
688 case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
689 case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
690 default: return nullptr;
691 }
692
693 // This simplification is only valid if the upper range is not negative.
694 KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1);
695 if (!Known.isNonNegative())
696 return nullptr;
697
698 if (Inverted)
699 NewPred = ICmpInst::getInversePredicate(NewPred);
700
701 return Builder.CreateICmp(NewPred, Input, RangeEnd);
702}
703
704// Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
705// Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
706Value *InstCombinerImpl::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS,
707 ICmpInst *RHS,
708 Instruction *CxtI,
709 bool IsAnd,
710 bool IsLogical) {
712 if (LHS->getPredicate() != Pred || RHS->getPredicate() != Pred)
713 return nullptr;
714
715 if (!match(LHS->getOperand(1), m_Zero()) ||
716 !match(RHS->getOperand(1), m_Zero()))
717 return nullptr;
718
719 Value *L1, *L2, *R1, *R2;
720 if (match(LHS->getOperand(0), m_And(m_Value(L1), m_Value(L2))) &&
721 match(RHS->getOperand(0), m_And(m_Value(R1), m_Value(R2)))) {
722 if (L1 == R2 || L2 == R2)
723 std::swap(R1, R2);
724 if (L2 == R1)
725 std::swap(L1, L2);
726
727 if (L1 == R1 &&
728 isKnownToBeAPowerOfTwo(L2, false, 0, CxtI) &&
729 isKnownToBeAPowerOfTwo(R2, false, 0, CxtI)) {
730 // If this is a logical and/or, then we must prevent propagation of a
731 // poison value from the RHS by inserting freeze.
732 if (IsLogical)
734 Value *Mask = Builder.CreateOr(L2, R2);
735 Value *Masked = Builder.CreateAnd(L1, Mask);
736 auto NewPred = IsAnd ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
737 return Builder.CreateICmp(NewPred, Masked, Mask);
738 }
739 }
740
741 return nullptr;
742}
743
744/// General pattern:
745/// X & Y
746///
747/// Where Y is checking that all the high bits (covered by a mask 4294967168)
748/// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0
749/// Pattern can be one of:
750/// %t = add i32 %arg, 128
751/// %r = icmp ult i32 %t, 256
752/// Or
753/// %t0 = shl i32 %arg, 24
754/// %t1 = ashr i32 %t0, 24
755/// %r = icmp eq i32 %t1, %arg
756/// Or
757/// %t0 = trunc i32 %arg to i8
758/// %t1 = sext i8 %t0 to i32
759/// %r = icmp eq i32 %t1, %arg
760/// This pattern is a signed truncation check.
761///
762/// And X is checking that some bit in that same mask is zero.
763/// I.e. can be one of:
764/// %r = icmp sgt i32 %arg, -1
765/// Or
766/// %t = and i32 %arg, 2147483648
767/// %r = icmp eq i32 %t, 0
768///
769/// Since we are checking that all the bits in that mask are the same,
770/// and a particular bit is zero, what we are really checking is that all the
771/// masked bits are zero.
772/// So this should be transformed to:
773/// %r = icmp ult i32 %arg, 128
775 Instruction &CxtI,
776 InstCombiner::BuilderTy &Builder) {
777 assert(CxtI.getOpcode() == Instruction::And);
778
779 // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two)
780 auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X,
781 APInt &SignBitMask) -> bool {
783 const APInt *I01, *I1; // powers of two; I1 == I01 << 1
784 if (!(match(ICmp,
785 m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) &&
786 Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1))
787 return false;
788 // Which bit is the new sign bit as per the 'signed truncation' pattern?
789 SignBitMask = *I01;
790 return true;
791 };
792
793 // One icmp needs to be 'signed truncation check'.
794 // We need to match this first, else we will mismatch commutative cases.
795 Value *X1;
796 APInt HighestBit;
797 ICmpInst *OtherICmp;
798 if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit))
799 OtherICmp = ICmp0;
800 else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit))
801 OtherICmp = ICmp1;
802 else
803 return nullptr;
804
805 assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)");
806
807 // Try to match/decompose into: icmp eq (X & Mask), 0
808 auto tryToDecompose = [](ICmpInst *ICmp, Value *&X,
809 APInt &UnsetBitsMask) -> bool {
810 CmpInst::Predicate Pred = ICmp->getPredicate();
811 // Can it be decomposed into icmp eq (X & Mask), 0 ?
812 if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1),
813 Pred, X, UnsetBitsMask,
814 /*LookThroughTrunc=*/false) &&
815 Pred == ICmpInst::ICMP_EQ)
816 return true;
817 // Is it icmp eq (X & Mask), 0 already?
818 const APInt *Mask;
819 if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) &&
820 Pred == ICmpInst::ICMP_EQ) {
821 UnsetBitsMask = *Mask;
822 return true;
823 }
824 return false;
825 };
826
827 // And the other icmp needs to be decomposable into a bit test.
828 Value *X0;
829 APInt UnsetBitsMask;
830 if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask))
831 return nullptr;
832
833 assert(!UnsetBitsMask.isZero() && "empty mask makes no sense.");
834
835 // Are they working on the same value?
836 Value *X;
837 if (X1 == X0) {
838 // Ok as is.
839 X = X1;
840 } else if (match(X0, m_Trunc(m_Specific(X1)))) {
841 UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits());
842 X = X1;
843 } else
844 return nullptr;
845
846 // So which bits should be uniform as per the 'signed truncation check'?
847 // (all the bits starting with (i.e. including) HighestBit)
848 APInt SignBitsMask = ~(HighestBit - 1U);
849
850 // UnsetBitsMask must have some common bits with SignBitsMask,
851 if (!UnsetBitsMask.intersects(SignBitsMask))
852 return nullptr;
853
854 // Does UnsetBitsMask contain any bits outside of SignBitsMask?
855 if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) {
856 APInt OtherHighestBit = (~UnsetBitsMask) + 1U;
857 if (!OtherHighestBit.isPowerOf2())
858 return nullptr;
859 HighestBit = APIntOps::umin(HighestBit, OtherHighestBit);
860 }
861 // Else, if it does not, then all is ok as-is.
862
863 // %r = icmp ult %X, SignBit
864 return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit),
865 CxtI.getName() + ".simplified");
866}
867
868/// Fold (icmp eq ctpop(X) 1) | (icmp eq X 0) into (icmp ult ctpop(X) 2) and
869/// fold (icmp ne ctpop(X) 1) & (icmp ne X 0) into (icmp ugt ctpop(X) 1).
870/// Also used for logical and/or, must be poison safe.
871static Value *foldIsPowerOf2OrZero(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd,
872 InstCombiner::BuilderTy &Builder) {
873 CmpInst::Predicate Pred0, Pred1;
874 Value *X;
875 if (!match(Cmp0, m_ICmp(Pred0, m_Intrinsic<Intrinsic::ctpop>(m_Value(X)),
876 m_SpecificInt(1))) ||
877 !match(Cmp1, m_ICmp(Pred1, m_Specific(X), m_ZeroInt())))
878 return nullptr;
879
880 Value *CtPop = Cmp0->getOperand(0);
881 if (IsAnd && Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_NE)
882 return Builder.CreateICmpUGT(CtPop, ConstantInt::get(CtPop->getType(), 1));
883 if (!IsAnd && Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_EQ)
884 return Builder.CreateICmpULT(CtPop, ConstantInt::get(CtPop->getType(), 2));
885
886 return nullptr;
887}
888
889/// Reduce a pair of compares that check if a value has exactly 1 bit set.
890/// Also used for logical and/or, must be poison safe.
891static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd,
892 InstCombiner::BuilderTy &Builder) {
893 // Handle 'and' / 'or' commutation: make the equality check the first operand.
894 if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE)
895 std::swap(Cmp0, Cmp1);
896 else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ)
897 std::swap(Cmp0, Cmp1);
898
899 // (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1
900 CmpInst::Predicate Pred0, Pred1;
901 Value *X;
902 if (JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
903 match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
904 m_SpecificInt(2))) &&
905 Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT) {
906 Value *CtPop = Cmp1->getOperand(0);
907 return Builder.CreateICmpEQ(CtPop, ConstantInt::get(CtPop->getType(), 1));
908 }
909 // (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1
910 if (!JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) &&
911 match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)),
912 m_SpecificInt(1))) &&
913 Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_UGT) {
914 Value *CtPop = Cmp1->getOperand(0);
915 return Builder.CreateICmpNE(CtPop, ConstantInt::get(CtPop->getType(), 1));
916 }
917 return nullptr;
918}
919
920/// Try to fold (icmp(A & B) == 0) & (icmp(A & D) != E) into (icmp A u< D) iff
921/// B is a contiguous set of ones starting from the most significant bit
922/// (negative power of 2), D and E are equal, and D is a contiguous set of ones
923/// starting at the most significant zero bit in B. Parameter B supports masking
924/// using undef/poison in either scalar or vector values.
929 "Expected equality predicates for masked type of icmps.");
930 if (PredL != ICmpInst::ICMP_EQ || PredR != ICmpInst::ICMP_NE)
931 return nullptr;
932
933 if (!match(B, m_NegatedPower2()) || !match(D, m_ShiftedMask()) ||
934 !match(E, m_ShiftedMask()))
935 return nullptr;
936
937 // Test scalar arguments for conversion. B has been validated earlier to be a
938 // negative power of two and thus is guaranteed to have one or more contiguous
939 // ones starting from the MSB followed by zero or more contiguous zeros. D has
940 // been validated earlier to be a shifted set of one or more contiguous ones.
941 // In order to match, B leading ones and D leading zeros should be equal. The
942 // predicate that B be a negative power of 2 prevents the condition of there
943 // ever being zero leading ones. Thus 0 == 0 cannot occur. The predicate that
944 // D always be a shifted mask prevents the condition of D equaling 0. This
945 // prevents matching the condition where B contains the maximum number of
946 // leading one bits (-1) and D contains the maximum number of leading zero
947 // bits (0).
948 auto isReducible = [](const Value *B, const Value *D, const Value *E) {
949 const APInt *BCst, *DCst, *ECst;
950 return match(B, m_APIntAllowUndef(BCst)) && match(D, m_APInt(DCst)) &&
951 match(E, m_APInt(ECst)) && *DCst == *ECst &&
952 (isa<UndefValue>(B) ||
953 (BCst->countLeadingOnes() == DCst->countLeadingZeros()));
954 };
955
956 // Test vector type arguments for conversion.
957 if (const auto *BVTy = dyn_cast<VectorType>(B->getType())) {
958 const auto *BFVTy = dyn_cast<FixedVectorType>(BVTy);
959 const auto *BConst = dyn_cast<Constant>(B);
960 const auto *DConst = dyn_cast<Constant>(D);
961 const auto *EConst = dyn_cast<Constant>(E);
962
963 if (!BFVTy || !BConst || !DConst || !EConst)
964 return nullptr;
965
966 for (unsigned I = 0; I != BFVTy->getNumElements(); ++I) {
967 const auto *BElt = BConst->getAggregateElement(I);
968 const auto *DElt = DConst->getAggregateElement(I);
969 const auto *EElt = EConst->getAggregateElement(I);
970
971 if (!BElt || !DElt || !EElt)
972 return nullptr;
973 if (!isReducible(BElt, DElt, EElt))
974 return nullptr;
975 }
976 } else {
977 // Test scalar type arguments for conversion.
978 if (!isReducible(B, D, E))
979 return nullptr;
980 }
981 return Builder.CreateICmp(ICmpInst::ICMP_ULT, A, D);
982}
983
984/// Try to fold ((icmp X u< P) & (icmp(X & M) != M)) or ((icmp X s> -1) &
985/// (icmp(X & M) != M)) into (icmp X u< M). Where P is a power of 2, M < P, and
986/// M is a contiguous shifted mask starting at the right most significant zero
987/// bit in P. SGT is supported as when P is the largest representable power of
988/// 2, an earlier optimization converts the expression into (icmp X s> -1).
989/// Parameter P supports masking using undef/poison in either scalar or vector
990/// values.
992 bool JoinedByAnd,
993 InstCombiner::BuilderTy &Builder) {
994 if (!JoinedByAnd)
995 return nullptr;
996 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
997 ICmpInst::Predicate CmpPred0 = Cmp0->getPredicate(),
998 CmpPred1 = Cmp1->getPredicate();
999 // Assuming P is a 2^n, getMaskedTypeForICmpPair will normalize (icmp X u<
1000 // 2^n) into (icmp (X & ~(2^n-1)) == 0) and (icmp X s> -1) into (icmp (X &
1001 // SignMask) == 0).
1002 std::optional<std::pair<unsigned, unsigned>> MaskPair =
1003 getMaskedTypeForICmpPair(A, B, C, D, E, Cmp0, Cmp1, CmpPred0, CmpPred1);
1004 if (!MaskPair)
1005 return nullptr;
1006
1007 const auto compareBMask = BMask_NotMixed | BMask_NotAllOnes;
1008 unsigned CmpMask0 = MaskPair->first;
1009 unsigned CmpMask1 = MaskPair->second;
1010 if ((CmpMask0 & Mask_AllZeros) && (CmpMask1 == compareBMask)) {
1011 if (Value *V = foldNegativePower2AndShiftedMask(A, B, D, E, CmpPred0,
1012 CmpPred1, Builder))
1013 return V;
1014 } else if ((CmpMask0 == compareBMask) && (CmpMask1 & Mask_AllZeros)) {
1015 if (Value *V = foldNegativePower2AndShiftedMask(A, D, B, C, CmpPred1,
1016 CmpPred0, Builder))
1017 return V;
1018 }
1019 return nullptr;
1020}
1021
1022/// Commuted variants are assumed to be handled by calling this function again
1023/// with the parameters swapped.
1025 ICmpInst *UnsignedICmp, bool IsAnd,
1026 const SimplifyQuery &Q,
1027 InstCombiner::BuilderTy &Builder) {
1028 Value *ZeroCmpOp;
1029 ICmpInst::Predicate EqPred;
1030 if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(ZeroCmpOp), m_Zero())) ||
1031 !ICmpInst::isEquality(EqPred))
1032 return nullptr;
1033
1034 auto IsKnownNonZero = [&](Value *V) {
1035 return isKnownNonZero(V, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT);
1036 };
1037
1038 ICmpInst::Predicate UnsignedPred;
1039
1040 Value *A, *B;
1041 if (match(UnsignedICmp,
1042 m_c_ICmp(UnsignedPred, m_Specific(ZeroCmpOp), m_Value(A))) &&
1043 match(ZeroCmpOp, m_c_Add(m_Specific(A), m_Value(B))) &&
1044 (ZeroICmp->hasOneUse() || UnsignedICmp->hasOneUse())) {
1045 auto GetKnownNonZeroAndOther = [&](Value *&NonZero, Value *&Other) {
1046 if (!IsKnownNonZero(NonZero))
1047 std::swap(NonZero, Other);
1048 return IsKnownNonZero(NonZero);
1049 };
1050
1051 // Given ZeroCmpOp = (A + B)
1052 // ZeroCmpOp < A && ZeroCmpOp != 0 --> (0-X) < Y iff
1053 // ZeroCmpOp >= A || ZeroCmpOp == 0 --> (0-X) >= Y iff
1054 // with X being the value (A/B) that is known to be non-zero,
1055 // and Y being remaining value.
1056 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE &&
1057 IsAnd && GetKnownNonZeroAndOther(B, A))
1058 return Builder.CreateICmpULT(Builder.CreateNeg(B), A);
1059 if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_EQ &&
1060 !IsAnd && GetKnownNonZeroAndOther(B, A))
1061 return Builder.CreateICmpUGE(Builder.CreateNeg(B), A);
1062 }
1063
1064 return nullptr;
1065}
1066
1067struct IntPart {
1069 unsigned StartBit;
1070 unsigned NumBits;
1071};
1072
1073/// Match an extraction of bits from an integer.
1074static std::optional<IntPart> matchIntPart(Value *V) {
1075 Value *X;
1076 if (!match(V, m_OneUse(m_Trunc(m_Value(X)))))
1077 return std::nullopt;
1078
1079 unsigned NumOriginalBits = X->getType()->getScalarSizeInBits();
1080 unsigned NumExtractedBits = V->getType()->getScalarSizeInBits();
1081 Value *Y;
1082 const APInt *Shift;
1083 // For a trunc(lshr Y, Shift) pattern, make sure we're only extracting bits
1084 // from Y, not any shifted-in zeroes.
1085 if (match(X, m_OneUse(m_LShr(m_Value(Y), m_APInt(Shift)))) &&
1086 Shift->ule(NumOriginalBits - NumExtractedBits))
1087 return {{Y, (unsigned)Shift->getZExtValue(), NumExtractedBits}};
1088 return {{X, 0, NumExtractedBits}};
1089}
1090
1091/// Materialize an extraction of bits from an integer in IR.
1092static Value *extractIntPart(const IntPart &P, IRBuilderBase &Builder) {
1093 Value *V = P.From;
1094 if (P.StartBit)
1095 V = Builder.CreateLShr(V, P.StartBit);
1096 Type *TruncTy = V->getType()->getWithNewBitWidth(P.NumBits);
1097 if (TruncTy != V->getType())
1098 V = Builder.CreateTrunc(V, TruncTy);
1099 return V;
1100}
1101
1102/// (icmp eq X0, Y0) & (icmp eq X1, Y1) -> icmp eq X01, Y01
1103/// (icmp ne X0, Y0) | (icmp ne X1, Y1) -> icmp ne X01, Y01
1104/// where X0, X1 and Y0, Y1 are adjacent parts extracted from an integer.
1105Value *InstCombinerImpl::foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1,
1106 bool IsAnd) {
1107 if (!Cmp0->hasOneUse() || !Cmp1->hasOneUse())
1108 return nullptr;
1109
1111 auto GetMatchPart = [&](ICmpInst *Cmp,
1112 unsigned OpNo) -> std::optional<IntPart> {
1113 if (Pred == Cmp->getPredicate())
1114 return matchIntPart(Cmp->getOperand(OpNo));
1115
1116 const APInt *C;
1117 // (icmp eq (lshr x, C), (lshr y, C)) gets optimized to:
1118 // (icmp ult (xor x, y), 1 << C) so also look for that.
1119 if (Pred == CmpInst::ICMP_EQ && Cmp->getPredicate() == CmpInst::ICMP_ULT) {
1120 if (!match(Cmp->getOperand(1), m_Power2(C)) ||
1121 !match(Cmp->getOperand(0), m_Xor(m_Value(), m_Value())))
1122 return std::nullopt;
1123 }
1124
1125 // (icmp ne (lshr x, C), (lshr y, C)) gets optimized to:
1126 // (icmp ugt (xor x, y), (1 << C) - 1) so also look for that.
1127 else if (Pred == CmpInst::ICMP_NE &&
1128 Cmp->getPredicate() == CmpInst::ICMP_UGT) {
1129 if (!match(Cmp->getOperand(1), m_LowBitMask(C)) ||
1130 !match(Cmp->getOperand(0), m_Xor(m_Value(), m_Value())))
1131 return std::nullopt;
1132 } else {
1133 return std::nullopt;
1134 }
1135
1136 unsigned From = Pred == CmpInst::ICMP_NE ? C->popcount() : C->countr_zero();
1137 Instruction *I = cast<Instruction>(Cmp->getOperand(0));
1138 return {{I->getOperand(OpNo), From, C->getBitWidth() - From}};
1139 };
1140
1141 std::optional<IntPart> L0 = GetMatchPart(Cmp0, 0);
1142 std::optional<IntPart> R0 = GetMatchPart(Cmp0, 1);
1143 std::optional<IntPart> L1 = GetMatchPart(Cmp1, 0);
1144 std::optional<IntPart> R1 = GetMatchPart(Cmp1, 1);
1145 if (!L0 || !R0 || !L1 || !R1)
1146 return nullptr;
1147
1148 // Make sure the LHS/RHS compare a part of the same value, possibly after
1149 // an operand swap.
1150 if (L0->From != L1->From || R0->From != R1->From) {
1151 if (L0->From != R1->From || R0->From != L1->From)
1152 return nullptr;
1153 std::swap(L1, R1);
1154 }
1155
1156 // Make sure the extracted parts are adjacent, canonicalizing to L0/R0 being
1157 // the low part and L1/R1 being the high part.
1158 if (L0->StartBit + L0->NumBits != L1->StartBit ||
1159 R0->StartBit + R0->NumBits != R1->StartBit) {
1160 if (L1->StartBit + L1->NumBits != L0->StartBit ||
1161 R1->StartBit + R1->NumBits != R0->StartBit)
1162 return nullptr;
1163 std::swap(L0, L1);
1164 std::swap(R0, R1);
1165 }
1166
1167 // We can simplify to a comparison of these larger parts of the integers.
1168 IntPart L = {L0->From, L0->StartBit, L0->NumBits + L1->NumBits};
1169 IntPart R = {R0->From, R0->StartBit, R0->NumBits + R1->NumBits};
1172 return Builder.CreateICmp(Pred, LValue, RValue);
1173}
1174
1175/// Reduce logic-of-compares with equality to a constant by substituting a
1176/// common operand with the constant. Callers are expected to call this with
1177/// Cmp0/Cmp1 switched to handle logic op commutativity.
1179 bool IsAnd, bool IsLogical,
1180 InstCombiner::BuilderTy &Builder,
1181 const SimplifyQuery &Q) {
1182 // Match an equality compare with a non-poison constant as Cmp0.
1183 // Also, give up if the compare can be constant-folded to avoid looping.
1184 ICmpInst::Predicate Pred0;
1185 Value *X;
1186 Constant *C;
1187 if (!match(Cmp0, m_ICmp(Pred0, m_Value(X), m_Constant(C))) ||
1188 !isGuaranteedNotToBeUndefOrPoison(C) || isa<Constant>(X))
1189 return nullptr;
1190 if ((IsAnd && Pred0 != ICmpInst::ICMP_EQ) ||
1191 (!IsAnd && Pred0 != ICmpInst::ICMP_NE))
1192 return nullptr;
1193
1194 // The other compare must include a common operand (X). Canonicalize the
1195 // common operand as operand 1 (Pred1 is swapped if the common operand was
1196 // operand 0).
1197 Value *Y;
1198 ICmpInst::Predicate Pred1;
1199 if (!match(Cmp1, m_c_ICmp(Pred1, m_Value(Y), m_Deferred(X))))
1200 return nullptr;
1201
1202 // Replace variable with constant value equivalence to remove a variable use:
1203 // (X == C) && (Y Pred1 X) --> (X == C) && (Y Pred1 C)
1204 // (X != C) || (Y Pred1 X) --> (X != C) || (Y Pred1 C)
1205 // Can think of the 'or' substitution with the 'and' bool equivalent:
1206 // A || B --> A || (!A && B)
1207 Value *SubstituteCmp = simplifyICmpInst(Pred1, Y, C, Q);
1208 if (!SubstituteCmp) {
1209 // If we need to create a new instruction, require that the old compare can
1210 // be removed.
1211 if (!Cmp1->hasOneUse())
1212 return nullptr;
1213 SubstituteCmp = Builder.CreateICmp(Pred1, Y, C);
1214 }
1215 if (IsLogical)
1216 return IsAnd ? Builder.CreateLogicalAnd(Cmp0, SubstituteCmp)
1217 : Builder.CreateLogicalOr(Cmp0, SubstituteCmp);
1218 return Builder.CreateBinOp(IsAnd ? Instruction::And : Instruction::Or, Cmp0,
1219 SubstituteCmp);
1220}
1221
1222/// Fold (icmp Pred1 V1, C1) & (icmp Pred2 V2, C2)
1223/// or (icmp Pred1 V1, C1) | (icmp Pred2 V2, C2)
1224/// into a single comparison using range-based reasoning.
1225/// NOTE: This is also used for logical and/or, must be poison-safe!
1226Value *InstCombinerImpl::foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1,
1227 ICmpInst *ICmp2,
1228 bool IsAnd) {
1229 ICmpInst::Predicate Pred1, Pred2;
1230 Value *V1, *V2;
1231 const APInt *C1, *C2;
1232 if (!match(ICmp1, m_ICmp(Pred1, m_Value(V1), m_APInt(C1))) ||
1233 !match(ICmp2, m_ICmp(Pred2, m_Value(V2), m_APInt(C2))))
1234 return nullptr;
1235
1236 // Look through add of a constant offset on V1, V2, or both operands. This
1237 // allows us to interpret the V + C' < C'' range idiom into a proper range.
1238 const APInt *Offset1 = nullptr, *Offset2 = nullptr;
1239 if (V1 != V2) {
1240 Value *X;
1241 if (match(V1, m_Add(m_Value(X), m_APInt(Offset1))))
1242 V1 = X;
1243 if (match(V2, m_Add(m_Value(X), m_APInt(Offset2))))
1244 V2 = X;
1245 }
1246
1247 if (V1 != V2)
1248 return nullptr;
1249
1251 IsAnd ? ICmpInst::getInversePredicate(Pred1) : Pred1, *C1);
1252 if (Offset1)
1253 CR1 = CR1.subtract(*Offset1);
1254
1256 IsAnd ? ICmpInst::getInversePredicate(Pred2) : Pred2, *C2);
1257 if (Offset2)
1258 CR2 = CR2.subtract(*Offset2);
1259
1260 Type *Ty = V1->getType();
1261 Value *NewV = V1;
1262 std::optional<ConstantRange> CR = CR1.exactUnionWith(CR2);
1263 if (!CR) {
1264 if (!(ICmp1->hasOneUse() && ICmp2->hasOneUse()) || CR1.isWrappedSet() ||
1265 CR2.isWrappedSet())
1266 return nullptr;
1267
1268 // Check whether we have equal-size ranges that only differ by one bit.
1269 // In that case we can apply a mask to map one range onto the other.
1270 APInt LowerDiff = CR1.getLower() ^ CR2.getLower();
1271 APInt UpperDiff = (CR1.getUpper() - 1) ^ (CR2.getUpper() - 1);
1272 APInt CR1Size = CR1.getUpper() - CR1.getLower();
1273 if (!LowerDiff.isPowerOf2() || LowerDiff != UpperDiff ||
1274 CR1Size != CR2.getUpper() - CR2.getLower())
1275 return nullptr;
1276
1277 CR = CR1.getLower().ult(CR2.getLower()) ? CR1 : CR2;
1278 NewV = Builder.CreateAnd(NewV, ConstantInt::get(Ty, ~LowerDiff));
1279 }
1280
1281 if (IsAnd)
1282 CR = CR->inverse();
1283
1284 CmpInst::Predicate NewPred;
1285 APInt NewC, Offset;
1286 CR->getEquivalentICmp(NewPred, NewC, Offset);
1287
1288 if (Offset != 0)
1289 NewV = Builder.CreateAdd(NewV, ConstantInt::get(Ty, Offset));
1290 return Builder.CreateICmp(NewPred, NewV, ConstantInt::get(Ty, NewC));
1291}
1292
1293/// Ignore all operations which only change the sign of a value, returning the
1294/// underlying magnitude value.
1296 match(Val, m_FNeg(m_Value(Val)));
1297 match(Val, m_FAbs(m_Value(Val)));
1298 match(Val, m_CopySign(m_Value(Val), m_Value()));
1299 return Val;
1300}
1301
1302/// Matches canonical form of isnan, fcmp ord x, 0
1304 return P == FCmpInst::FCMP_ORD && match(RHS, m_AnyZeroFP());
1305}
1306
1307/// Matches fcmp u__ x, +/-inf
1309 Value *RHS) {
1310 return FCmpInst::isUnordered(P) && match(RHS, m_Inf());
1311}
1312
1313/// and (fcmp ord x, 0), (fcmp u* x, inf) -> fcmp o* x, inf
1314///
1315/// Clang emits this pattern for doing an isfinite check in __builtin_isnormal.
1317 FCmpInst *RHS) {
1318 Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1319 Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1320 FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1321
1322 if (!matchIsNotNaN(PredL, LHS0, LHS1) ||
1323 !matchUnorderedInfCompare(PredR, RHS0, RHS1))
1324 return nullptr;
1325
1326 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
1327 FastMathFlags FMF = LHS->getFastMathFlags();
1328 FMF &= RHS->getFastMathFlags();
1329 Builder.setFastMathFlags(FMF);
1330
1331 return Builder.CreateFCmp(FCmpInst::getOrderedPredicate(PredR), RHS0, RHS1);
1332}
1333
1334Value *InstCombinerImpl::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS,
1335 bool IsAnd, bool IsLogicalSelect) {
1336 Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
1337 Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
1338 FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
1339
1340 if (LHS0 == RHS1 && RHS0 == LHS1) {
1341 // Swap RHS operands to match LHS.
1342 PredR = FCmpInst::getSwappedPredicate(PredR);
1343 std::swap(RHS0, RHS1);
1344 }
1345
1346 // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1347 // Suppose the relation between x and y is R, where R is one of
1348 // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1349 // testing the desired relations.
1350 //
1351 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1352 // bool(R & CC0) && bool(R & CC1)
1353 // = bool((R & CC0) & (R & CC1))
1354 // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1355 //
1356 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1357 // bool(R & CC0) || bool(R & CC1)
1358 // = bool((R & CC0) | (R & CC1))
1359 // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1360 if (LHS0 == RHS0 && LHS1 == RHS1) {
1361 unsigned FCmpCodeL = getFCmpCode(PredL);
1362 unsigned FCmpCodeR = getFCmpCode(PredR);
1363 unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1364
1365 // Intersect the fast math flags.
1366 // TODO: We can union the fast math flags unless this is a logical select.
1368 FastMathFlags FMF = LHS->getFastMathFlags();
1369 FMF &= RHS->getFastMathFlags();
1371
1372 return getFCmpValue(NewPred, LHS0, LHS1, Builder);
1373 }
1374
1375 // This transform is not valid for a logical select.
1376 if (!IsLogicalSelect &&
1377 ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) ||
1378 (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO &&
1379 !IsAnd))) {
1380 if (LHS0->getType() != RHS0->getType())
1381 return nullptr;
1382
1383 // FCmp canonicalization ensures that (fcmp ord/uno X, X) and
1384 // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0).
1385 if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP()))
1386 // Ignore the constants because they are obviously not NANs:
1387 // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y)
1388 // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y)
1389 return Builder.CreateFCmp(PredL, LHS0, RHS0);
1390 }
1391
1392 if (IsAnd && stripSignOnlyFPOps(LHS0) == stripSignOnlyFPOps(RHS0)) {
1393 // and (fcmp ord x, 0), (fcmp u* x, inf) -> fcmp o* x, inf
1394 // and (fcmp ord x, 0), (fcmp u* fabs(x), inf) -> fcmp o* x, inf
1395 if (Value *Left = matchIsFiniteTest(Builder, LHS, RHS))
1396 return Left;
1397 if (Value *Right = matchIsFiniteTest(Builder, RHS, LHS))
1398 return Right;
1399 }
1400
1401 // Turn at least two fcmps with constants into llvm.is.fpclass.
1402 //
1403 // If we can represent a combined value test with one class call, we can
1404 // potentially eliminate 4-6 instructions. If we can represent a test with a
1405 // single fcmp with fneg and fabs, that's likely a better canonical form.
1406 if (LHS->hasOneUse() && RHS->hasOneUse()) {
1407 auto [ClassValRHS, ClassMaskRHS] =
1408 fcmpToClassTest(PredR, *RHS->getFunction(), RHS0, RHS1);
1409 if (ClassValRHS) {
1410 auto [ClassValLHS, ClassMaskLHS] =
1411 fcmpToClassTest(PredL, *LHS->getFunction(), LHS0, LHS1);
1412 if (ClassValLHS == ClassValRHS) {
1413 unsigned CombinedMask = IsAnd ? (ClassMaskLHS & ClassMaskRHS)
1414 : (ClassMaskLHS | ClassMaskRHS);
1415 return Builder.CreateIntrinsic(
1416 Intrinsic::is_fpclass, {ClassValLHS->getType()},
1417 {ClassValLHS, Builder.getInt32(CombinedMask)});
1418 }
1419 }
1420 }
1421
1422 // Canonicalize the range check idiom:
1423 // and (fcmp olt/ole/ult/ule x, C), (fcmp ogt/oge/ugt/uge x, -C)
1424 // --> fabs(x) olt/ole/ult/ule C
1425 // or (fcmp ogt/oge/ugt/uge x, C), (fcmp olt/ole/ult/ule x, -C)
1426 // --> fabs(x) ogt/oge/ugt/uge C
1427 // TODO: Generalize to handle a negated variable operand?
1428 const APFloat *LHSC, *RHSC;
1429 if (LHS0 == RHS0 && LHS->hasOneUse() && RHS->hasOneUse() &&
1430 FCmpInst::getSwappedPredicate(PredL) == PredR &&
1431 match(LHS1, m_APFloatAllowUndef(LHSC)) &&
1432 match(RHS1, m_APFloatAllowUndef(RHSC)) &&
1433 LHSC->bitwiseIsEqual(neg(*RHSC))) {
1434 auto IsLessThanOrLessEqual = [](FCmpInst::Predicate Pred) {
1435 switch (Pred) {
1436 case FCmpInst::FCMP_OLT:
1437 case FCmpInst::FCMP_OLE:
1438 case FCmpInst::FCMP_ULT:
1439 case FCmpInst::FCMP_ULE:
1440 return true;
1441 default:
1442 return false;
1443 }
1444 };
1445 if (IsLessThanOrLessEqual(IsAnd ? PredR : PredL)) {
1446 std::swap(LHSC, RHSC);
1447 std::swap(PredL, PredR);
1448 }
1449 if (IsLessThanOrLessEqual(IsAnd ? PredL : PredR)) {
1451 Builder.setFastMathFlags(LHS->getFastMathFlags() |
1452 RHS->getFastMathFlags());
1453
1454 Value *FAbs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, LHS0);
1455 return Builder.CreateFCmp(PredL, FAbs,
1456 ConstantFP::get(LHS0->getType(), *LHSC));
1457 }
1458 }
1459
1460 return nullptr;
1461}
1462
1463/// Match an fcmp against a special value that performs a test possible by
1464/// llvm.is.fpclass.
1465static bool matchIsFPClassLikeFCmp(Value *Op, Value *&ClassVal,
1466 uint64_t &ClassMask) {
1467 auto *FCmp = dyn_cast<FCmpInst>(Op);
1468 if (!FCmp || !FCmp->hasOneUse())
1469 return false;
1470
1471 std::tie(ClassVal, ClassMask) =
1472 fcmpToClassTest(FCmp->getPredicate(), *FCmp->getParent()->getParent(),
1473 FCmp->getOperand(0), FCmp->getOperand(1));
1474 return ClassVal != nullptr;
1475}
1476
1477/// or (is_fpclass x, mask0), (is_fpclass x, mask1)
1478/// -> is_fpclass x, (mask0 | mask1)
1479/// and (is_fpclass x, mask0), (is_fpclass x, mask1)
1480/// -> is_fpclass x, (mask0 & mask1)
1481/// xor (is_fpclass x, mask0), (is_fpclass x, mask1)
1482/// -> is_fpclass x, (mask0 ^ mask1)
1483Instruction *InstCombinerImpl::foldLogicOfIsFPClass(BinaryOperator &BO,
1484 Value *Op0, Value *Op1) {
1485 Value *ClassVal0 = nullptr;
1486 Value *ClassVal1 = nullptr;
1487 uint64_t ClassMask0, ClassMask1;
1488
1489 // Restrict to folding one fcmp into one is.fpclass for now, don't introduce a
1490 // new class.
1491 //
1492 // TODO: Support forming is.fpclass out of 2 separate fcmps when codegen is
1493 // better.
1494
1495 bool IsLHSClass =
1496 match(Op0, m_OneUse(m_Intrinsic<Intrinsic::is_fpclass>(
1497 m_Value(ClassVal0), m_ConstantInt(ClassMask0))));
1498 bool IsRHSClass =
1499 match(Op1, m_OneUse(m_Intrinsic<Intrinsic::is_fpclass>(
1500 m_Value(ClassVal1), m_ConstantInt(ClassMask1))));
1501 if ((((IsLHSClass || matchIsFPClassLikeFCmp(Op0, ClassVal0, ClassMask0)) &&
1502 (IsRHSClass || matchIsFPClassLikeFCmp(Op1, ClassVal1, ClassMask1)))) &&
1503 ClassVal0 == ClassVal1) {
1504 unsigned NewClassMask;
1505 switch (BO.getOpcode()) {
1506 case Instruction::And:
1507 NewClassMask = ClassMask0 & ClassMask1;
1508 break;
1509 case Instruction::Or:
1510 NewClassMask = ClassMask0 | ClassMask1;
1511 break;
1512 case Instruction::Xor:
1513 NewClassMask = ClassMask0 ^ ClassMask1;
1514 break;
1515 default:
1516 llvm_unreachable("not a binary logic operator");
1517 }
1518
1519 if (IsLHSClass) {
1520 auto *II = cast<IntrinsicInst>(Op0);
1521 II->setArgOperand(
1522 1, ConstantInt::get(II->getArgOperand(1)->getType(), NewClassMask));
1523 return replaceInstUsesWith(BO, II);
1524 }
1525
1526 if (IsRHSClass) {
1527 auto *II = cast<IntrinsicInst>(Op1);
1528 II->setArgOperand(
1529 1, ConstantInt::get(II->getArgOperand(1)->getType(), NewClassMask));
1530 return replaceInstUsesWith(BO, II);
1531 }
1532
1533 CallInst *NewClass =
1534 Builder.CreateIntrinsic(Intrinsic::is_fpclass, {ClassVal0->getType()},
1535 {ClassVal0, Builder.getInt32(NewClassMask)});
1536 return replaceInstUsesWith(BO, NewClass);
1537 }
1538
1539 return nullptr;
1540}
1541
1542/// Look for the pattern that conditionally negates a value via math operations:
1543/// cond.splat = sext i1 cond
1544/// sub = add cond.splat, x
1545/// xor = xor sub, cond.splat
1546/// and rewrite it to do the same, but via logical operations:
1547/// value.neg = sub 0, value
1548/// cond = select i1 neg, value.neg, value
1549Instruction *InstCombinerImpl::canonicalizeConditionalNegationViaMathToSelect(
1550 BinaryOperator &I) {
1551 assert(I.getOpcode() == BinaryOperator::Xor && "Only for xor!");
1552 Value *Cond, *X;
1553 // As per complexity ordering, `xor` is not commutative here.
1554 if (!match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())) ||
1555 !match(I.getOperand(1), m_SExt(m_Value(Cond))) ||
1556 !Cond->getType()->isIntOrIntVectorTy(1) ||
1557 !match(I.getOperand(0), m_c_Add(m_SExt(m_Deferred(Cond)), m_Value(X))))
1558 return nullptr;
1559 return SelectInst::Create(Cond, Builder.CreateNeg(X, X->getName() + ".neg"),
1560 X);
1561}
1562
1563/// This a limited reassociation for a special case (see above) where we are
1564/// checking if two values are either both NAN (unordered) or not-NAN (ordered).
1565/// This could be handled more generally in '-reassociation', but it seems like
1566/// an unlikely pattern for a large number of logic ops and fcmps.
1568 InstCombiner::BuilderTy &Builder) {
1569 Instruction::BinaryOps Opcode = BO.getOpcode();
1570 assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1571 "Expecting and/or op for fcmp transform");
1572
1573 // There are 4 commuted variants of the pattern. Canonicalize operands of this
1574 // logic op so an fcmp is operand 0 and a matching logic op is operand 1.
1575 Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1), *X;
1577 if (match(Op1, m_FCmp(Pred, m_Value(), m_AnyZeroFP())))
1578 std::swap(Op0, Op1);
1579
1580 // Match inner binop and the predicate for combining 2 NAN checks into 1.
1581 Value *BO10, *BO11;
1582 FCmpInst::Predicate NanPred = Opcode == Instruction::And ? FCmpInst::FCMP_ORD
1584 if (!match(Op0, m_FCmp(Pred, m_Value(X), m_AnyZeroFP())) || Pred != NanPred ||
1585 !match(Op1, m_BinOp(Opcode, m_Value(BO10), m_Value(BO11))))
1586 return nullptr;
1587
1588 // The inner logic op must have a matching fcmp operand.
1589 Value *Y;
1590 if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1591 Pred != NanPred || X->getType() != Y->getType())
1592 std::swap(BO10, BO11);
1593
1594 if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) ||
1595 Pred != NanPred || X->getType() != Y->getType())
1596 return nullptr;
1597
1598 // and (fcmp ord X, 0), (and (fcmp ord Y, 0), Z) --> and (fcmp ord X, Y), Z
1599 // or (fcmp uno X, 0), (or (fcmp uno Y, 0), Z) --> or (fcmp uno X, Y), Z
1600 Value *NewFCmp = Builder.CreateFCmp(Pred, X, Y);
1601 if (auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) {
1602 // Intersect FMF from the 2 source fcmps.
1603 NewFCmpInst->copyIRFlags(Op0);
1604 NewFCmpInst->andIRFlags(BO10);
1605 }
1606 return BinaryOperator::Create(Opcode, NewFCmp, BO11);
1607}
1608
1609/// Match variations of De Morgan's Laws:
1610/// (~A & ~B) == (~(A | B))
1611/// (~A | ~B) == (~(A & B))
1613 InstCombiner &IC) {
1614 const Instruction::BinaryOps Opcode = I.getOpcode();
1615 assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1616 "Trying to match De Morgan's Laws with something other than and/or");
1617
1618 // Flip the logic operation.
1619 const Instruction::BinaryOps FlippedOpcode =
1620 (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1621
1622 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1623 Value *A, *B;
1624 if (match(Op0, m_OneUse(m_Not(m_Value(A)))) &&
1625 match(Op1, m_OneUse(m_Not(m_Value(B)))) &&
1626 !IC.isFreeToInvert(A, A->hasOneUse()) &&
1627 !IC.isFreeToInvert(B, B->hasOneUse())) {
1628 Value *AndOr =
1629 IC.Builder.CreateBinOp(FlippedOpcode, A, B, I.getName() + ".demorgan");
1630 return BinaryOperator::CreateNot(AndOr);
1631 }
1632
1633 // The 'not' ops may require reassociation.
1634 // (A & ~B) & ~C --> A & ~(B | C)
1635 // (~B & A) & ~C --> A & ~(B | C)
1636 // (A | ~B) | ~C --> A | ~(B & C)
1637 // (~B | A) | ~C --> A | ~(B & C)
1638 Value *C;
1639 if (match(Op0, m_OneUse(m_c_BinOp(Opcode, m_Value(A), m_Not(m_Value(B))))) &&
1640 match(Op1, m_Not(m_Value(C)))) {
1641 Value *FlippedBO = IC.Builder.CreateBinOp(FlippedOpcode, B, C);
1642 return BinaryOperator::Create(Opcode, A, IC.Builder.CreateNot(FlippedBO));
1643 }
1644
1645 return nullptr;
1646}
1647
1648bool InstCombinerImpl::shouldOptimizeCast(CastInst *CI) {
1649 Value *CastSrc = CI->getOperand(0);
1650
1651 // Noop casts and casts of constants should be eliminated trivially.
1652 if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1653 return false;
1654
1655 // If this cast is paired with another cast that can be eliminated, we prefer
1656 // to have it eliminated.
1657 if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1658 if (isEliminableCastPair(PrecedingCI, CI))
1659 return false;
1660
1661 return true;
1662}
1663
1664/// Fold {and,or,xor} (cast X), C.
1666 InstCombinerImpl &IC) {
1667 Constant *C = dyn_cast<Constant>(Logic.getOperand(1));
1668 if (!C)
1669 return nullptr;
1670
1671 auto LogicOpc = Logic.getOpcode();
1672 Type *DestTy = Logic.getType();
1673 Type *SrcTy = Cast->getSrcTy();
1674
1675 // Move the logic operation ahead of a zext or sext if the constant is
1676 // unchanged in the smaller source type. Performing the logic in a smaller
1677 // type may provide more information to later folds, and the smaller logic
1678 // instruction may be cheaper (particularly in the case of vectors).
1679 Value *X;
1680 if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1681 if (Constant *TruncC = IC.getLosslessUnsignedTrunc(C, SrcTy)) {
1682 // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1683 Value *NewOp = IC.Builder.CreateBinOp(LogicOpc, X, TruncC);
1684 return new ZExtInst(NewOp, DestTy);
1685 }
1686 }
1687
1688 if (match(Cast, m_OneUse(m_SExtLike(m_Value(X))))) {
1689 if (Constant *TruncC = IC.getLosslessSignedTrunc(C, SrcTy)) {
1690 // LogicOpc (sext X), C --> sext (LogicOpc X, C)
1691 Value *NewOp = IC.Builder.CreateBinOp(LogicOpc, X, TruncC);
1692 return new SExtInst(NewOp, DestTy);
1693 }
1694 }
1695
1696 return nullptr;
1697}
1698
1699/// Fold {and,or,xor} (cast X), Y.
1700Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) {
1701 auto LogicOpc = I.getOpcode();
1702 assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
1703
1704 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1705
1706 // fold bitwise(A >> BW - 1, zext(icmp)) (BW is the scalar bits of the
1707 // type of A)
1708 // -> bitwise(zext(A < 0), zext(icmp))
1709 // -> zext(bitwise(A < 0, icmp))
1710 auto FoldBitwiseICmpZeroWithICmp = [&](Value *Op0,
1711 Value *Op1) -> Instruction * {
1713 Value *A;
1714 bool IsMatched =
1715 match(Op0,
1717 m_Value(A),
1718 m_SpecificInt(Op0->getType()->getScalarSizeInBits() - 1)))) &&
1719 match(Op1, m_OneUse(m_ZExt(m_ICmp(Pred, m_Value(), m_Value()))));
1720
1721 if (!IsMatched)
1722 return nullptr;
1723
1724 auto *ICmpL =
1726 auto *ICmpR = cast<ZExtInst>(Op1)->getOperand(0);
1727 auto *BitwiseOp = Builder.CreateBinOp(LogicOpc, ICmpL, ICmpR);
1728
1729 return new ZExtInst(BitwiseOp, Op0->getType());
1730 };
1731
1732 if (auto *Ret = FoldBitwiseICmpZeroWithICmp(Op0, Op1))
1733 return Ret;
1734
1735 if (auto *Ret = FoldBitwiseICmpZeroWithICmp(Op1, Op0))
1736 return Ret;
1737
1738 CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1739 if (!Cast0)
1740 return nullptr;
1741
1742 // This must be a cast from an integer or integer vector source type to allow
1743 // transformation of the logic operation to the source type.
1744 Type *DestTy = I.getType();
1745 Type *SrcTy = Cast0->getSrcTy();
1746 if (!SrcTy->isIntOrIntVectorTy())
1747 return nullptr;
1748
1749 if (Instruction *Ret = foldLogicCastConstant(I, Cast0, *this))
1750 return Ret;
1751
1752 CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1753 if (!Cast1)
1754 return nullptr;
1755
1756 // Both operands of the logic operation are casts. The casts must be the
1757 // same kind for reduction.
1758 Instruction::CastOps CastOpcode = Cast0->getOpcode();
1759 if (CastOpcode != Cast1->getOpcode())
1760 return nullptr;
1761
1762 // If the source types do not match, but the casts are matching extends, we
1763 // can still narrow the logic op.
1764 if (SrcTy != Cast1->getSrcTy()) {
1765 Value *X, *Y;
1766 if (match(Cast0, m_OneUse(m_ZExtOrSExt(m_Value(X)))) &&
1767 match(Cast1, m_OneUse(m_ZExtOrSExt(m_Value(Y))))) {
1768 // Cast the narrower source to the wider source type.
1769 unsigned XNumBits = X->getType()->getScalarSizeInBits();
1770 unsigned YNumBits = Y->getType()->getScalarSizeInBits();
1771 if (XNumBits < YNumBits)
1772 X = Builder.CreateCast(CastOpcode, X, Y->getType());
1773 else
1774 Y = Builder.CreateCast(CastOpcode, Y, X->getType());
1775 // Do the logic op in the intermediate width, then widen more.
1776 Value *NarrowLogic = Builder.CreateBinOp(LogicOpc, X, Y);
1777 return CastInst::Create(CastOpcode, NarrowLogic, DestTy);
1778 }
1779
1780 // Give up for other cast opcodes.
1781 return nullptr;
1782 }
1783
1784 Value *Cast0Src = Cast0->getOperand(0);
1785 Value *Cast1Src = Cast1->getOperand(0);
1786
1787 // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
1788 if ((Cast0->hasOneUse() || Cast1->hasOneUse()) &&
1789 shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1790 Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1791 I.getName());
1792 return CastInst::Create(CastOpcode, NewOp, DestTy);
1793 }
1794
1795 return nullptr;
1796}
1797
1799 InstCombiner::BuilderTy &Builder) {
1800 assert(I.getOpcode() == Instruction::And);
1801 Value *Op0 = I.getOperand(0);
1802 Value *Op1 = I.getOperand(1);
1803 Value *A, *B;
1804
1805 // Operand complexity canonicalization guarantees that the 'or' is Op0.
1806 // (A | B) & ~(A & B) --> A ^ B
1807 // (A | B) & ~(B & A) --> A ^ B
1808 if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)),
1810 return BinaryOperator::CreateXor(A, B);
1811
1812 // (A | ~B) & (~A | B) --> ~(A ^ B)
1813 // (A | ~B) & (B | ~A) --> ~(A ^ B)
1814 // (~B | A) & (~A | B) --> ~(A ^ B)
1815 // (~B | A) & (B | ~A) --> ~(A ^ B)
1816 if (Op0->hasOneUse() || Op1->hasOneUse())
1819 return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1820
1821 return nullptr;
1822}
1823
1825 InstCombiner::BuilderTy &Builder) {
1826 assert(I.getOpcode() == Instruction::Or);
1827 Value *Op0 = I.getOperand(0);
1828 Value *Op1 = I.getOperand(1);
1829 Value *A, *B;
1830
1831 // Operand complexity canonicalization guarantees that the 'and' is Op0.
1832 // (A & B) | ~(A | B) --> ~(A ^ B)
1833 // (A & B) | ~(B | A) --> ~(A ^ B)
1834 if (Op0->hasOneUse() || Op1->hasOneUse())
1835 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1837 return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
1838
1839 // Operand complexity canonicalization guarantees that the 'xor' is Op0.
1840 // (A ^ B) | ~(A | B) --> ~(A & B)
1841 // (A ^ B) | ~(B | A) --> ~(A & B)
1842 if (Op0->hasOneUse() || Op1->hasOneUse())
1843 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1845 return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
1846
1847 // (A & ~B) | (~A & B) --> A ^ B
1848 // (A & ~B) | (B & ~A) --> A ^ B
1849 // (~B & A) | (~A & B) --> A ^ B
1850 // (~B & A) | (B & ~A) --> A ^ B
1851 if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
1853 return BinaryOperator::CreateXor(A, B);
1854
1855 return nullptr;
1856}
1857
1858/// Return true if a constant shift amount is always less than the specified
1859/// bit-width. If not, the shift could create poison in the narrower type.
1860static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) {
1861 APInt Threshold(C->getType()->getScalarSizeInBits(), BitWidth);
1862 return match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold));
1863}
1864
1865/// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and
1866/// a common zext operand: and (binop (zext X), C), (zext X).
1867Instruction *InstCombinerImpl::narrowMaskedBinOp(BinaryOperator &And) {
1868 // This transform could also apply to {or, and, xor}, but there are better
1869 // folds for those cases, so we don't expect those patterns here. AShr is not
1870 // handled because it should always be transformed to LShr in this sequence.
1871 // The subtract transform is different because it has a constant on the left.
1872 // Add/mul commute the constant to RHS; sub with constant RHS becomes add.
1873 Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1);
1874 Constant *C;
1875 if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) &&
1876 !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) &&
1877 !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) &&
1878 !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) &&
1879 !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1)))))
1880 return nullptr;
1881
1882 Value *X;
1883 if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3))
1884 return nullptr;
1885
1886 Type *Ty = And.getType();
1887 if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType()))
1888 return nullptr;
1889
1890 // If we're narrowing a shift, the shift amount must be safe (less than the
1891 // width) in the narrower type. If the shift amount is greater, instsimplify
1892 // usually handles that case, but we can't guarantee/assert it.
1893 Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode();
1894 if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1895 if (!canNarrowShiftAmt(C, X->getType()->getScalarSizeInBits()))
1896 return nullptr;
1897
1898 // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X)
1899 // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X)
1900 Value *NewC = ConstantExpr::getTrunc(C, X->getType());
1901 Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X)
1902 : Builder.CreateBinOp(Opc, X, NewC);
1903 return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty);
1904}
1905
1906/// Try folding relatively complex patterns for both And and Or operations
1907/// with all And and Or swapped.
1909 InstCombiner::BuilderTy &Builder) {
1910 const Instruction::BinaryOps Opcode = I.getOpcode();
1911 assert(Opcode == Instruction::And || Opcode == Instruction::Or);
1912
1913 // Flip the logic operation.
1914 const Instruction::BinaryOps FlippedOpcode =
1915 (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1916
1917 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1918 Value *A, *B, *C, *X, *Y, *Dummy;
1919
1920 // Match following expressions:
1921 // (~(A | B) & C)
1922 // (~(A & B) | C)
1923 // Captures X = ~(A | B) or ~(A & B)
1924 const auto matchNotOrAnd =
1925 [Opcode, FlippedOpcode](Value *Op, auto m_A, auto m_B, auto m_C,
1926 Value *&X, bool CountUses = false) -> bool {
1927 if (CountUses && !Op->hasOneUse())
1928 return false;
1929
1930 if (match(Op, m_c_BinOp(FlippedOpcode,
1932 m_Not(m_c_BinOp(Opcode, m_A, m_B))),
1933 m_C)))
1934 return !CountUses || X->hasOneUse();
1935
1936 return false;
1937 };
1938
1939 // (~(A | B) & C) | ... --> ...
1940 // (~(A & B) | C) & ... --> ...
1941 // TODO: One use checks are conservative. We just need to check that a total
1942 // number of multiple used values does not exceed reduction
1943 // in operations.
1944 if (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X)) {
1945 // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
1946 // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
1947 if (matchNotOrAnd(Op1, m_Specific(A), m_Specific(C), m_Specific(B), Dummy,
1948 true)) {
1949 Value *Xor = Builder.CreateXor(B, C);
1950 return (Opcode == Instruction::Or)
1951 ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
1953 }
1954
1955 // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
1956 // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)
1957 if (matchNotOrAnd(Op1, m_Specific(B), m_Specific(C), m_Specific(A), Dummy,
1958 true)) {
1959 Value *Xor = Builder.CreateXor(A, C);
1960 return (Opcode == Instruction::Or)
1961 ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(B))
1963 }
1964
1965 // (~(A | B) & C) | ~(A | C) --> ~((B & C) | A)
1966 // (~(A & B) | C) & ~(A & C) --> ~((B | C) & A)
1967 if (match(Op1, m_OneUse(m_Not(m_OneUse(
1968 m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
1970 Opcode, Builder.CreateBinOp(FlippedOpcode, B, C), A));
1971
1972 // (~(A | B) & C) | ~(B | C) --> ~((A & C) | B)
1973 // (~(A & B) | C) & ~(B & C) --> ~((A | C) & B)
1974 if (match(Op1, m_OneUse(m_Not(m_OneUse(
1975 m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)))))))
1977 Opcode, Builder.CreateBinOp(FlippedOpcode, A, C), B));
1978
1979 // (~(A | B) & C) | ~(C | (A ^ B)) --> ~((A | B) & (C | (A ^ B)))
1980 // Note, the pattern with swapped and/or is not handled because the
1981 // result is more undefined than a source:
1982 // (~(A & B) | C) & ~(C & (A ^ B)) --> (A ^ B ^ C) | ~(A | C) is invalid.
1983 if (Opcode == Instruction::Or && Op0->hasOneUse() &&
1985 m_Value(Y),
1986 m_c_BinOp(Opcode, m_Specific(C),
1987 m_c_Xor(m_Specific(A), m_Specific(B)))))))) {
1988 // X = ~(A | B)
1989 // Y = (C | (A ^ B)
1990 Value *Or = cast<BinaryOperator>(X)->getOperand(0);
1991 return BinaryOperator::CreateNot(Builder.CreateAnd(Or, Y));
1992 }
1993 }
1994
1995 // (~A & B & C) | ... --> ...
1996 // (~A | B | C) | ... --> ...
1997 // TODO: One use checks are conservative. We just need to check that a total
1998 // number of multiple used values does not exceed reduction
1999 // in operations.
2000 if (match(Op0,
2001 m_OneUse(m_c_BinOp(FlippedOpcode,
2002 m_BinOp(FlippedOpcode, m_Value(B), m_Value(C)),
2003 m_CombineAnd(m_Value(X), m_Not(m_Value(A)))))) ||
2005 FlippedOpcode,
2006 m_c_BinOp(FlippedOpcode, m_Value(C),
2008 m_Value(B))))) {
2009 // X = ~A
2010 // (~A & B & C) | ~(A | B | C) --> ~(A | (B ^ C))
2011 // (~A | B | C) & ~(A & B & C) --> (~A | (B ^ C))
2012 if (match(Op1, m_OneUse(m_Not(m_c_BinOp(
2013 Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)),
2014 m_Specific(C))))) ||
2016 Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
2017 m_Specific(A))))) ||
2019 Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
2020 m_Specific(B)))))) {
2021 Value *Xor = Builder.CreateXor(B, C);
2022 return (Opcode == Instruction::Or)
2024 : BinaryOperator::CreateOr(Xor, X);
2025 }
2026
2027 // (~A & B & C) | ~(A | B) --> (C | ~B) & ~A
2028 // (~A | B | C) & ~(A & B) --> (C & ~B) | ~A
2029 if (match(Op1, m_OneUse(m_Not(m_OneUse(
2030 m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)))))))
2032 FlippedOpcode, Builder.CreateBinOp(Opcode, C, Builder.CreateNot(B)),
2033 X);
2034
2035 // (~A & B & C) | ~(A | C) --> (B | ~C) & ~A
2036 // (~A | B | C) & ~(A & C) --> (B & ~C) | ~A
2037 if (match(Op1, m_OneUse(m_Not(m_OneUse(
2038 m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
2040 FlippedOpcode, Builder.CreateBinOp(Opcode, B, Builder.CreateNot(C)),
2041 X);
2042 }
2043
2044 return nullptr;
2045}
2046
2047/// Try to reassociate a pair of binops so that values with one use only are
2048/// part of the same instruction. This may enable folds that are limited with
2049/// multi-use restrictions and makes it more likely to match other patterns that
2050/// are looking for a common operand.
2052 InstCombinerImpl::BuilderTy &Builder) {
2053 Instruction::BinaryOps Opcode = BO.getOpcode();
2054 Value *X, *Y, *Z;
2055 if (match(&BO,
2056 m_c_BinOp(Opcode, m_OneUse(m_BinOp(Opcode, m_Value(X), m_Value(Y))),
2057 m_OneUse(m_Value(Z))))) {
2058 if (!isa<Constant>(X) && !isa<Constant>(Y) && !isa<Constant>(Z)) {
2059 // (X op Y) op Z --> (Y op Z) op X
2060 if (!X->hasOneUse()) {
2061 Value *YZ = Builder.CreateBinOp(Opcode, Y, Z);
2062 return BinaryOperator::Create(Opcode, YZ, X);
2063 }
2064 // (X op Y) op Z --> (X op Z) op Y
2065 if (!Y->hasOneUse()) {
2066 Value *XZ = Builder.CreateBinOp(Opcode, X, Z);
2067 return BinaryOperator::Create(Opcode, XZ, Y);
2068 }
2069 }
2070 }
2071
2072 return nullptr;
2073}
2074
2075// Match
2076// (X + C2) | C
2077// (X + C2) ^ C
2078// (X + C2) & C
2079// and convert to do the bitwise logic first:
2080// (X | C) + C2
2081// (X ^ C) + C2
2082// (X & C) + C2
2083// iff bits affected by logic op are lower than last bit affected by math op
2085 InstCombiner::BuilderTy &Builder) {
2086 Type *Ty = I.getType();
2087 Instruction::BinaryOps OpC = I.getOpcode();
2088 Value *Op0 = I.getOperand(0);
2089 Value *Op1 = I.getOperand(1);
2090 Value *X;
2091 const APInt *C, *C2;
2092
2093 if (!(match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C2)))) &&
2094 match(Op1, m_APInt(C))))
2095 return nullptr;
2096
2097 unsigned Width = Ty->getScalarSizeInBits();
2098 unsigned LastOneMath = Width - C2->countr_zero();
2099
2100 switch (OpC) {
2101 case Instruction::And:
2102 if (C->countl_one() < LastOneMath)
2103 return nullptr;
2104 break;
2105 case Instruction::Xor:
2106 case Instruction::Or:
2107 if (C->countl_zero() < LastOneMath)
2108 return nullptr;
2109 break;
2110 default:
2111 llvm_unreachable("Unexpected BinaryOp!");
2112 }
2113
2114 Value *NewBinOp = Builder.CreateBinOp(OpC, X, ConstantInt::get(Ty, *C));
2115 return BinaryOperator::CreateWithCopiedFlags(Instruction::Add, NewBinOp,
2116 ConstantInt::get(Ty, *C2), Op0);
2117}
2118
2119// binop(shift(ShiftedC1, ShAmt), shift(ShiftedC2, add(ShAmt, AddC))) ->
2120// shift(binop(ShiftedC1, shift(ShiftedC2, AddC)), ShAmt)
2121// where both shifts are the same and AddC is a valid shift amount.
2122Instruction *InstCombinerImpl::foldBinOpOfDisplacedShifts(BinaryOperator &I) {
2123 assert((I.isBitwiseLogicOp() || I.getOpcode() == Instruction::Add) &&
2124 "Unexpected opcode");
2125
2126 Value *ShAmt;
2127 Constant *ShiftedC1, *ShiftedC2, *AddC;
2128 Type *Ty = I.getType();
2129 unsigned BitWidth = Ty->getScalarSizeInBits();
2130 if (!match(&I, m_c_BinOp(m_Shift(m_ImmConstant(ShiftedC1), m_Value(ShAmt)),
2131 m_Shift(m_ImmConstant(ShiftedC2),
2132 m_AddLike(m_Deferred(ShAmt),
2133 m_ImmConstant(AddC))))))
2134 return nullptr;
2135
2136 // Make sure the add constant is a valid shift amount.
2137 if (!match(AddC,
2139 return nullptr;
2140
2141 // Avoid constant expressions.
2142 auto *Op0Inst = dyn_cast<Instruction>(I.getOperand(0));
2143 auto *Op1Inst = dyn_cast<Instruction>(I.getOperand(1));
2144 if (!Op0Inst || !Op1Inst)
2145 return nullptr;
2146
2147 // Both shifts must be the same.
2148 Instruction::BinaryOps ShiftOp =
2149 static_cast<Instruction::BinaryOps>(Op0Inst->getOpcode());
2150 if (ShiftOp != Op1Inst->getOpcode())
2151 return nullptr;
2152
2153 // For adds, only left shifts are supported.
2154 if (I.getOpcode() == Instruction::Add && ShiftOp != Instruction::Shl)
2155 return nullptr;
2156
2157 Value *NewC = Builder.CreateBinOp(
2158 I.getOpcode(), ShiftedC1, Builder.CreateBinOp(ShiftOp, ShiftedC2, AddC));
2159 return BinaryOperator::Create(ShiftOp, NewC, ShAmt);
2160}
2161
2162// Fold and/or/xor with two equal intrinsic IDs:
2163// bitwise(fshl (A, B, ShAmt), fshl(C, D, ShAmt))
2164// -> fshl(bitwise(A, C), bitwise(B, D), ShAmt)
2165// bitwise(fshr (A, B, ShAmt), fshr(C, D, ShAmt))
2166// -> fshr(bitwise(A, C), bitwise(B, D), ShAmt)
2167// bitwise(bswap(A), bswap(B)) -> bswap(bitwise(A, B))
2168// bitwise(bswap(A), C) -> bswap(bitwise(A, bswap(C)))
2169// bitwise(bitreverse(A), bitreverse(B)) -> bitreverse(bitwise(A, B))
2170// bitwise(bitreverse(A), C) -> bitreverse(bitwise(A, bitreverse(C)))
2171static Instruction *
2173 InstCombiner::BuilderTy &Builder) {
2174 assert(I.isBitwiseLogicOp() && "Should and/or/xor");
2175 if (!I.getOperand(0)->hasOneUse())
2176 return nullptr;
2177 IntrinsicInst *X = dyn_cast<IntrinsicInst>(I.getOperand(0));
2178 if (!X)
2179 return nullptr;
2180
2181 IntrinsicInst *Y = dyn_cast<IntrinsicInst>(I.getOperand(1));
2182 if (Y && (!Y->hasOneUse() || X->getIntrinsicID() != Y->getIntrinsicID()))
2183 return nullptr;
2184
2185 Intrinsic::ID IID = X->getIntrinsicID();
2186 const APInt *RHSC;
2187 // Try to match constant RHS.
2188 if (!Y && (!(IID == Intrinsic::bswap || IID == Intrinsic::bitreverse) ||
2189 !match(I.getOperand(1), m_APInt(RHSC))))
2190 return nullptr;
2191
2192 switch (IID) {
2193 case Intrinsic::fshl:
2194 case Intrinsic::fshr: {
2195 if (X->getOperand(2) != Y->getOperand(2))
2196 return nullptr;
2197 Value *NewOp0 =
2198 Builder.CreateBinOp(I.getOpcode(), X->getOperand(0), Y->getOperand(0));
2199 Value *NewOp1 =
2200 Builder.CreateBinOp(I.getOpcode(), X->getOperand(1), Y->getOperand(1));
2201 Function *F = Intrinsic::getDeclaration(I.getModule(), IID, I.getType());
2202 return CallInst::Create(F, {NewOp0, NewOp1, X->getOperand(2)});
2203 }
2204 case Intrinsic::bswap:
2205 case Intrinsic::bitreverse: {
2206 Value *NewOp0 = Builder.CreateBinOp(
2207 I.getOpcode(), X->getOperand(0),
2208 Y ? Y->getOperand(0)
2209 : ConstantInt::get(I.getType(), IID == Intrinsic::bswap
2210 ? RHSC->byteSwap()
2211 : RHSC->reverseBits()));
2212 Function *F = Intrinsic::getDeclaration(I.getModule(), IID, I.getType());
2213 return CallInst::Create(F, {NewOp0});
2214 }
2215 default:
2216 return nullptr;
2217 }
2218}
2219
2220// Try to simplify V by replacing occurrences of Op with RepOp, but only look
2221// through bitwise operations. In particular, for X | Y we try to replace Y with
2222// 0 inside X and for X & Y we try to replace Y with -1 inside X.
2223// Return the simplified result of X if successful, and nullptr otherwise.
2224// If SimplifyOnly is true, no new instructions will be created.
2226 bool SimplifyOnly,
2227 InstCombinerImpl &IC,
2228 unsigned Depth = 0) {
2229 if (Op == RepOp)
2230 return nullptr;
2231
2232 if (V == Op)
2233 return RepOp;
2234
2235 auto *I = dyn_cast<BinaryOperator>(V);
2236 if (!I || !I->isBitwiseLogicOp() || Depth >= 3)
2237 return nullptr;
2238
2239 if (!I->hasOneUse())
2240 SimplifyOnly = true;
2241
2242 Value *NewOp0 = simplifyAndOrWithOpReplaced(I->getOperand(0), Op, RepOp,
2243 SimplifyOnly, IC, Depth + 1);
2244 Value *NewOp1 = simplifyAndOrWithOpReplaced(I->getOperand(1), Op, RepOp,
2245 SimplifyOnly, IC, Depth + 1);
2246 if (!NewOp0 && !NewOp1)
2247 return nullptr;
2248
2249 if (!NewOp0)
2250 NewOp0 = I->getOperand(0);
2251 if (!NewOp1)
2252 NewOp1 = I->getOperand(1);
2253
2254 if (Value *Res = simplifyBinOp(I->getOpcode(), NewOp0, NewOp1,
2256 return Res;
2257
2258 if (SimplifyOnly)
2259 return nullptr;
2260 return IC.Builder.CreateBinOp(I->getOpcode(), NewOp0, NewOp1);
2261}
2262
2263// FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
2264// here. We should standardize that construct where it is needed or choose some
2265// other way to ensure that commutated variants of patterns are not missed.
2267 Type *Ty = I.getType();
2268
2269 if (Value *V = simplifyAndInst(I.getOperand(0), I.getOperand(1),
2271 return replaceInstUsesWith(I, V);
2272
2274 return &I;
2275
2277 return X;
2278
2280 return Phi;
2281
2282 // See if we can simplify any instructions used by the instruction whose sole
2283 // purpose is to compute bits we don't care about.
2285 return &I;
2286
2287 // Do this before using distributive laws to catch simple and/or/not patterns.
2289 return Xor;
2290
2292 return X;
2293
2294 // (A|B)&(A|C) -> A|(B&C) etc
2296 return replaceInstUsesWith(I, V);
2297
2299 return R;
2300
2301 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2302
2303 Value *X, *Y;
2304 const APInt *C;
2305 if ((match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) ||
2306 (match(Op0, m_OneUse(m_Shl(m_APInt(C), m_Value(X)))) && (*C)[0])) &&
2307 match(Op1, m_One())) {
2308 // (1 >> X) & 1 --> zext(X == 0)
2309 // (C << X) & 1 --> zext(X == 0), when C is odd
2310 Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, 0));
2311 return new ZExtInst(IsZero, Ty);
2312 }
2313
2314 // (-(X & 1)) & Y --> (X & 1) == 0 ? 0 : Y
2315 Value *Neg;
2316 if (match(&I,
2318 m_OneUse(m_Neg(m_And(m_Value(), m_One())))),
2319 m_Value(Y)))) {
2320 Value *Cmp = Builder.CreateIsNull(Neg);
2322 }
2323
2324 // Canonicalize:
2325 // (X +/- Y) & Y --> ~X & Y when Y is a power of 2.
2328 m_Sub(m_Value(X), m_Deferred(Y)))))) &&
2329 isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, /*Depth*/ 0, &I))
2330 return BinaryOperator::CreateAnd(Builder.CreateNot(X), Y);
2331
2332 if (match(Op1, m_APInt(C))) {
2333 const APInt *XorC;
2334 if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) {
2335 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
2336 Constant *NewC = ConstantInt::get(Ty, *C & *XorC);
2337 Value *And = Builder.CreateAnd(X, Op1);
2338 And->takeName(Op0);
2339 return BinaryOperator::CreateXor(And, NewC);
2340 }
2341
2342 const APInt *OrC;
2343 if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
2344 // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2)
2345 // NOTE: This reduces the number of bits set in the & mask, which
2346 // can expose opportunities for store narrowing for scalars.
2347 // NOTE: SimplifyDemandedBits should have already removed bits from C1
2348 // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in
2349 // above, but this feels safer.
2350 APInt Together = *C & *OrC;
2351 Value *And = Builder.CreateAnd(X, ConstantInt::get(Ty, Together ^ *C));
2352 And->takeName(Op0);
2353 return BinaryOperator::CreateOr(And, ConstantInt::get(Ty, Together));
2354 }
2355
2356 unsigned Width = Ty->getScalarSizeInBits();
2357 const APInt *ShiftC;
2358 if (match(Op0, m_OneUse(m_SExt(m_AShr(m_Value(X), m_APInt(ShiftC))))) &&
2359 ShiftC->ult(Width)) {
2360 if (*C == APInt::getLowBitsSet(Width, Width - ShiftC->getZExtValue())) {
2361 // We are clearing high bits that were potentially set by sext+ashr:
2362 // and (sext (ashr X, ShiftC)), C --> lshr (sext X), ShiftC
2363 Value *Sext = Builder.CreateSExt(X, Ty);
2364 Constant *ShAmtC = ConstantInt::get(Ty, ShiftC->zext(Width));
2365 return BinaryOperator::CreateLShr(Sext, ShAmtC);
2366 }
2367 }
2368
2369 // If this 'and' clears the sign-bits added by ashr, replace with lshr:
2370 // and (ashr X, ShiftC), C --> lshr X, ShiftC
2371 if (match(Op0, m_AShr(m_Value(X), m_APInt(ShiftC))) && ShiftC->ult(Width) &&
2372 C->isMask(Width - ShiftC->getZExtValue()))
2373 return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, *ShiftC));
2374
2375 const APInt *AddC;
2376 if (match(Op0, m_Add(m_Value(X), m_APInt(AddC)))) {
2377 // If we are masking the result of the add down to exactly one bit and
2378 // the constant we are adding has no bits set below that bit, then the
2379 // add is flipping a single bit. Example:
2380 // (X + 4) & 4 --> (X & 4) ^ 4
2381 if (Op0->hasOneUse() && C->isPowerOf2() && (*AddC & (*C - 1)) == 0) {
2382 assert((*C & *AddC) != 0 && "Expected common bit");
2383 Value *NewAnd = Builder.CreateAnd(X, Op1);
2384 return BinaryOperator::CreateXor(NewAnd, Op1);
2385 }
2386 }
2387
2388 // ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if C2 fits in the
2389 // bitwidth of X and OP behaves well when given trunc(C1) and X.
2390 auto isNarrowableBinOpcode = [](BinaryOperator *B) {
2391 switch (B->getOpcode()) {
2392 case Instruction::Xor:
2393 case Instruction::Or:
2394 case Instruction::Mul:
2395 case Instruction::Add:
2396 case Instruction::Sub:
2397 return true;
2398 default:
2399 return false;
2400 }
2401 };
2402 BinaryOperator *BO;
2403 if (match(Op0, m_OneUse(m_BinOp(BO))) && isNarrowableBinOpcode(BO)) {
2404 Instruction::BinaryOps BOpcode = BO->getOpcode();
2405 Value *X;
2406 const APInt *C1;
2407 // TODO: The one-use restrictions could be relaxed a little if the AND
2408 // is going to be removed.
2409 // Try to narrow the 'and' and a binop with constant operand:
2410 // and (bo (zext X), C1), C --> zext (and (bo X, TruncC1), TruncC)
2411 if (match(BO, m_c_BinOp(m_OneUse(m_ZExt(m_Value(X))), m_APInt(C1))) &&
2412 C->isIntN(X->getType()->getScalarSizeInBits())) {
2413 unsigned XWidth = X->getType()->getScalarSizeInBits();
2414 Constant *TruncC1 = ConstantInt::get(X->getType(), C1->trunc(XWidth));
2415 Value *BinOp = isa<ZExtInst>(BO->getOperand(0))
2416 ? Builder.CreateBinOp(BOpcode, X, TruncC1)
2417 : Builder.CreateBinOp(BOpcode, TruncC1, X);
2418 Constant *TruncC = ConstantInt::get(X->getType(), C->trunc(XWidth));
2419 Value *And = Builder.CreateAnd(BinOp, TruncC);
2420 return new ZExtInst(And, Ty);
2421 }
2422
2423 // Similar to above: if the mask matches the zext input width, then the
2424 // 'and' can be eliminated, so we can truncate the other variable op:
2425 // and (bo (zext X), Y), C --> zext (bo X, (trunc Y))
2426 if (isa<Instruction>(BO->getOperand(0)) &&
2427 match(BO->getOperand(0), m_OneUse(m_ZExt(m_Value(X)))) &&
2428 C->isMask(X->getType()->getScalarSizeInBits())) {
2429 Y = BO->getOperand(1);
2430 Value *TrY = Builder.CreateTrunc(Y, X->getType(), Y->getName() + ".tr");
2431 Value *NewBO =
2432 Builder.CreateBinOp(BOpcode, X, TrY, BO->getName() + ".narrow");
2433 return new ZExtInst(NewBO, Ty);
2434 }
2435 // and (bo Y, (zext X)), C --> zext (bo (trunc Y), X)
2436 if (isa<Instruction>(BO->getOperand(1)) &&
2437 match(BO->getOperand(1), m_OneUse(m_ZExt(m_Value(X)))) &&
2438 C->isMask(X->getType()->getScalarSizeInBits())) {
2439 Y = BO->getOperand(0);
2440 Value *TrY = Builder.CreateTrunc(Y, X->getType(), Y->getName() + ".tr");
2441 Value *NewBO =
2442 Builder.CreateBinOp(BOpcode, TrY, X, BO->getName() + ".narrow");
2443 return new ZExtInst(NewBO, Ty);
2444 }
2445 }
2446
2447 // This is intentionally placed after the narrowing transforms for
2448 // efficiency (transform directly to the narrow logic op if possible).
2449 // If the mask is only needed on one incoming arm, push the 'and' op up.
2450 if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
2451 match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2452 APInt NotAndMask(~(*C));
2453 BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
2454 if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
2455 // Not masking anything out for the LHS, move mask to RHS.
2456 // and ({x}or X, Y), C --> {x}or X, (and Y, C)
2457 Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked");
2458 return BinaryOperator::Create(BinOp, X, NewRHS);
2459 }
2460 if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) {
2461 // Not masking anything out for the RHS, move mask to LHS.
2462 // and ({x}or X, Y), C --> {x}or (and X, C), Y
2463 Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked");
2464 return BinaryOperator::Create(BinOp, NewLHS, Y);
2465 }
2466 }
2467
2468 // When the mask is a power-of-2 constant and op0 is a shifted-power-of-2
2469 // constant, test if the shift amount equals the offset bit index:
2470 // (ShiftC << X) & C --> X == (log2(C) - log2(ShiftC)) ? C : 0
2471 // (ShiftC >> X) & C --> X == (log2(ShiftC) - log2(C)) ? C : 0
2472 if (C->isPowerOf2() &&
2473 match(Op0, m_OneUse(m_LogicalShift(m_Power2(ShiftC), m_Value(X))))) {
2474 int Log2ShiftC = ShiftC->exactLogBase2();
2475 int Log2C = C->exactLogBase2();
2476 bool IsShiftLeft =
2477 cast<BinaryOperator>(Op0)->getOpcode() == Instruction::Shl;
2478 int BitNum = IsShiftLeft ? Log2C - Log2ShiftC : Log2ShiftC - Log2C;
2479 assert(BitNum >= 0 && "Expected demanded bits to handle impossible mask");
2480 Value *Cmp = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, BitNum));
2481 return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C),
2483 }
2484
2485 Constant *C1, *C2;
2486 const APInt *C3 = C;
2487 Value *X;
2488 if (C3->isPowerOf2()) {
2489 Constant *Log2C3 = ConstantInt::get(Ty, C3->countr_zero());
2491 m_ImmConstant(C2)))) &&
2492 match(C1, m_Power2())) {
2494 Constant *LshrC = ConstantExpr::getAdd(C2, Log2C3);
2495 KnownBits KnownLShrc = computeKnownBits(LshrC, 0, nullptr);
2496 if (KnownLShrc.getMaxValue().ult(Width)) {
2497 // iff C1,C3 is pow2 and C2 + cttz(C3) < BitWidth:
2498 // ((C1 << X) >> C2) & C3 -> X == (cttz(C3)+C2-cttz(C1)) ? C3 : 0
2499 Constant *CmpC = ConstantExpr::getSub(LshrC, Log2C1);
2500 Value *Cmp = Builder.CreateICmpEQ(X, CmpC);
2501 return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3),
2503 }
2504 }
2505
2507 m_ImmConstant(C2)))) &&
2508 match(C1, m_Power2())) {
2510 Constant *Cmp =
2512 if (Cmp->isZeroValue()) {
2513 // iff C1,C3 is pow2 and Log2(C3) >= C2:
2514 // ((C1 >> X) << C2) & C3 -> X == (cttz(C1)+C2-cttz(C3)) ? C3 : 0
2515 Constant *ShlC = ConstantExpr::getAdd(C2, Log2C1);
2516 Constant *CmpC = ConstantExpr::getSub(ShlC, Log2C3);
2517 Value *Cmp = Builder.CreateICmpEQ(X, CmpC);
2518 return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3),
2520 }
2521 }
2522 }
2523 }
2524
2525 // If we are clearing the sign bit of a floating-point value, convert this to
2526 // fabs, then cast back to integer.
2527 //
2528 // This is a generous interpretation for noimplicitfloat, this is not a true
2529 // floating-point operation.
2530 //
2531 // Assumes any IEEE-represented type has the sign bit in the high bit.
2532 // TODO: Unify with APInt matcher. This version allows undef unlike m_APInt
2533 Value *CastOp;
2534 if (match(Op0, m_ElementWiseBitCast(m_Value(CastOp))) &&
2535 match(Op1, m_MaxSignedValue()) &&
2537 Attribute::NoImplicitFloat)) {
2538 Type *EltTy = CastOp->getType()->getScalarType();
2539 if (EltTy->isFloatingPointTy() && EltTy->isIEEE()) {
2540 Value *FAbs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, CastOp);
2541 return new BitCastInst(FAbs, I.getType());
2542 }
2543 }
2544
2546 m_SignMask())) &&
2550 Ty->getScalarSizeInBits() -
2551 X->getType()->getScalarSizeInBits())))) {
2552 auto *SExt = Builder.CreateSExt(X, Ty, X->getName() + ".signext");
2553 auto *SanitizedSignMask = cast<Constant>(Op1);
2554 // We must be careful with the undef elements of the sign bit mask, however:
2555 // the mask elt can be undef iff the shift amount for that lane was undef,
2556 // otherwise we need to sanitize undef masks to zero.
2557 SanitizedSignMask = Constant::replaceUndefsWith(
2558 SanitizedSignMask, ConstantInt::getNullValue(Ty->getScalarType()));
2559 SanitizedSignMask =
2560 Constant::mergeUndefsWith(SanitizedSignMask, cast<Constant>(Y));
2561 return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
2562 }
2563
2564 if (Instruction *Z = narrowMaskedBinOp(I))
2565 return Z;
2566
2567 if (I.getType()->isIntOrIntVectorTy(1)) {
2568 if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
2569 if (auto *R =
2570 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ true))
2571 return R;
2572 }
2573 if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
2574 if (auto *R =
2575 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ true))
2576 return R;
2577 }
2578 }
2579
2580 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
2581 return FoldedLogic;
2582
2583 if (Instruction *DeMorgan = matchDeMorgansLaws(I, *this))
2584 return DeMorgan;
2585
2586 {
2587 Value *A, *B, *C;
2588 // A & ~(A ^ B) --> A & B
2589 if (match(Op1, m_Not(m_c_Xor(m_Specific(Op0), m_Value(B)))))
2590 return BinaryOperator::CreateAnd(Op0, B);
2591 // ~(A ^ B) & A --> A & B
2592 if (match(Op0, m_Not(m_c_Xor(m_Specific(Op1), m_Value(B)))))
2593 return BinaryOperator::CreateAnd(Op1, B);
2594
2595 // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
2596 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2597 match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) {
2598 Value *NotC = Op1->hasOneUse()
2600 : getFreelyInverted(C, C->hasOneUse(), &Builder);
2601 if (NotC != nullptr)
2602 return BinaryOperator::CreateAnd(Op0, NotC);
2603 }
2604
2605 // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
2606 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))) &&
2607 match(Op1, m_Xor(m_Specific(B), m_Specific(A)))) {
2608 Value *NotC = Op0->hasOneUse()
2610 : getFreelyInverted(C, C->hasOneUse(), &Builder);
2611 if (NotC != nullptr)
2612 return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
2613 }
2614
2615 // (A | B) & (~A ^ B) -> A & B
2616 // (A | B) & (B ^ ~A) -> A & B
2617 // (B | A) & (~A ^ B) -> A & B
2618 // (B | A) & (B ^ ~A) -> A & B
2619 if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2620 match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
2621 return BinaryOperator::CreateAnd(A, B);
2622
2623 // (~A ^ B) & (A | B) -> A & B
2624 // (~A ^ B) & (B | A) -> A & B
2625 // (B ^ ~A) & (A | B) -> A & B
2626 // (B ^ ~A) & (B | A) -> A & B
2627 if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2628 match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
2629 return BinaryOperator::CreateAnd(A, B);
2630
2631 // (~A | B) & (A ^ B) -> ~A & B
2632 // (~A | B) & (B ^ A) -> ~A & B
2633 // (B | ~A) & (A ^ B) -> ~A & B
2634 // (B | ~A) & (B ^ A) -> ~A & B
2635 if (match(Op0, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
2637 return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
2638
2639 // (A ^ B) & (~A | B) -> ~A & B
2640 // (B ^ A) & (~A | B) -> ~A & B
2641 // (A ^ B) & (B | ~A) -> ~A & B
2642 // (B ^ A) & (B | ~A) -> ~A & B
2643 if (match(Op1, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
2645 return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
2646 }
2647
2648 {
2649 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2650 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2651 if (LHS && RHS)
2652 if (Value *Res = foldAndOrOfICmps(LHS, RHS, I, /* IsAnd */ true))
2653 return replaceInstUsesWith(I, Res);
2654
2655 // TODO: Make this recursive; it's a little tricky because an arbitrary
2656 // number of 'and' instructions might have to be created.
2657 if (LHS && match(Op1, m_OneUse(m_LogicalAnd(m_Value(X), m_Value(Y))))) {
2658 bool IsLogical = isa<SelectInst>(Op1);
2659 // LHS & (X && Y) --> (LHS && X) && Y
2660 if (auto *Cmp = dyn_cast<ICmpInst>(X))
2661 if (Value *Res =
2662 foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ true, IsLogical))
2663 return replaceInstUsesWith(I, IsLogical
2664 ? Builder.CreateLogicalAnd(Res, Y)
2665 : Builder.CreateAnd(Res, Y));
2666 // LHS & (X && Y) --> X && (LHS & Y)
2667 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2668 if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ true,
2669 /* IsLogical */ false))
2670 return replaceInstUsesWith(I, IsLogical
2671 ? Builder.CreateLogicalAnd(X, Res)
2672 : Builder.CreateAnd(X, Res));
2673 }
2674 if (RHS && match(Op0, m_OneUse(m_LogicalAnd(m_Value(X), m_Value(Y))))) {
2675 bool IsLogical = isa<SelectInst>(Op0);
2676 // (X && Y) & RHS --> (X && RHS) && Y
2677 if (auto *Cmp = dyn_cast<ICmpInst>(X))
2678 if (Value *Res =
2679 foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ true, IsLogical))
2680 return replaceInstUsesWith(I, IsLogical
2681 ? Builder.CreateLogicalAnd(Res, Y)
2682 : Builder.CreateAnd(Res, Y));
2683 // (X && Y) & RHS --> X && (Y & RHS)
2684 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2685 if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ true,
2686 /* IsLogical */ false))
2687 return replaceInstUsesWith(I, IsLogical
2688 ? Builder.CreateLogicalAnd(X, Res)
2689 : Builder.CreateAnd(X, Res));
2690 }
2691 }
2692
2693 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2694 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
2695 if (Value *Res = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true))
2696 return replaceInstUsesWith(I, Res);
2697
2698 if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
2699 return FoldedFCmps;
2700
2701 if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
2702 return CastedAnd;
2703
2704 if (Instruction *Sel = foldBinopOfSextBoolToSelect(I))
2705 return Sel;
2706
2707 // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>.
2708 // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold
2709 // with binop identity constant. But creating a select with non-constant
2710 // arm may not be reversible due to poison semantics. Is that a good
2711 // canonicalization?
2712 Value *A, *B;
2713 if (match(&I, m_c_And(m_SExt(m_Value(A)), m_Value(B))) &&
2714 A->getType()->isIntOrIntVectorTy(1))
2716
2717 // Similarly, a 'not' of the bool translates to a swap of the select arms:
2718 // ~sext(A) & B / B & ~sext(A) --> A ? 0 : B
2719 if (match(&I, m_c_And(m_Not(m_SExt(m_Value(A))), m_Value(B))) &&
2720 A->getType()->isIntOrIntVectorTy(1))
2722
2723 // and(zext(A), B) -> A ? (B & 1) : 0
2724 if (match(&I, m_c_And(m_OneUse(m_ZExt(m_Value(A))), m_Value(B))) &&
2725 A->getType()->isIntOrIntVectorTy(1))
2726 return SelectInst::Create(A, Builder.CreateAnd(B, ConstantInt::get(Ty, 1)),
2728
2729 // (-1 + A) & B --> A ? 0 : B where A is 0/1.
2731 m_Value(B)))) {
2732 if (A->getType()->isIntOrIntVectorTy(1))
2734 if (computeKnownBits(A, /* Depth */ 0, &I).countMaxActiveBits() <= 1) {
2735 return SelectInst::Create(
2738 }
2739 }
2740
2741 // (iN X s>> (N-1)) & Y --> (X s< 0) ? Y : 0 -- with optional sext
2744 m_Value(Y))) &&
2745 *C == X->getType()->getScalarSizeInBits() - 1) {
2746 Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
2748 }
2749 // If there's a 'not' of the shifted value, swap the select operands:
2750 // ~(iN X s>> (N-1)) & Y --> (X s< 0) ? 0 : Y -- with optional sext
2753 m_Value(Y))) &&
2754 *C == X->getType()->getScalarSizeInBits() - 1) {
2755 Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
2757 }
2758
2759 // (~x) & y --> ~(x | (~y)) iff that gets rid of inversions
2761 return &I;
2762
2763 // An and recurrence w/loop invariant step is equivelent to (and start, step)
2764 PHINode *PN = nullptr;
2765 Value *Start = nullptr, *Step = nullptr;
2766 if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
2767 return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
2768
2770 return R;
2771
2772 if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
2773 return Canonicalized;
2774
2775 if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1))
2776 return Folded;
2777
2778 if (Instruction *Res = foldBinOpOfDisplacedShifts(I))
2779 return Res;
2780
2782 return Res;
2783
2784 if (Value *V =
2786 /*SimplifyOnly*/ false, *this))
2787 return BinaryOperator::CreateAnd(V, Op1);
2788 if (Value *V =
2790 /*SimplifyOnly*/ false, *this))
2791 return BinaryOperator::CreateAnd(Op0, V);
2792
2793 return nullptr;
2794}
2795
2797 bool MatchBSwaps,
2798 bool MatchBitReversals) {
2800 if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
2801 Insts))
2802 return nullptr;
2803 Instruction *LastInst = Insts.pop_back_val();
2804 LastInst->removeFromParent();
2805
2806 for (auto *Inst : Insts)
2807 Worklist.push(Inst);
2808 return LastInst;
2809}
2810
2811std::optional<std::pair<Intrinsic::ID, SmallVector<Value *, 3>>>
2813 // TODO: Can we reduce the code duplication between this and the related
2814 // rotate matching code under visitSelect and visitTrunc?
2815 assert(Or.getOpcode() == BinaryOperator::Or && "Expecting or instruction");
2816
2817 unsigned Width = Or.getType()->getScalarSizeInBits();
2818
2819 Instruction *Or0, *Or1;
2820 if (!match(Or.getOperand(0), m_Instruction(Or0)) ||
2821 !match(Or.getOperand(1), m_Instruction(Or1)))
2822 return std::nullopt;
2823
2824 bool IsFshl = true; // Sub on LSHR.
2825 SmallVector<Value *, 3> FShiftArgs;
2826
2827 // First, find an or'd pair of opposite shifts:
2828 // or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1)
2829 if (isa<BinaryOperator>(Or0) && isa<BinaryOperator>(Or1)) {
2830 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2831 if (!match(Or0,
2832 m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
2833 !match(Or1,
2834 m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
2835 Or0->getOpcode() == Or1->getOpcode())
2836 return std::nullopt;
2837
2838 // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
2839 if (Or0->getOpcode() == BinaryOperator::LShr) {
2840 std::swap(Or0, Or1);
2841 std::swap(ShVal0, ShVal1);
2842 std::swap(ShAmt0, ShAmt1);
2843 }
2844 assert(Or0->getOpcode() == BinaryOperator::Shl &&
2845 Or1->getOpcode() == BinaryOperator::LShr &&
2846 "Illegal or(shift,shift) pair");
2847
2848 // Match the shift amount operands for a funnel shift pattern. This always
2849 // matches a subtraction on the R operand.
2850 auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
2851 // Check for constant shift amounts that sum to the bitwidth.
2852 const APInt *LI, *RI;
2853 if (match(L, m_APIntAllowUndef(LI)) && match(R, m_APIntAllowUndef(RI)))
2854 if (LI->ult(Width) && RI->ult(Width) && (*LI + *RI) == Width)
2855 return ConstantInt::get(L->getType(), *LI);
2856
2857 Constant *LC, *RC;
2858 if (match(L, m_Constant(LC)) && match(R, m_Constant(RC)) &&
2859 match(L,
2860 m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, APInt(Width, Width))) &&
2861 match(R,
2862 m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, APInt(Width, Width))) &&
2864 return ConstantExpr::mergeUndefsWith(LC, RC);
2865
2866 // (shl ShVal, X) | (lshr ShVal, (Width - x)) iff X < Width.
2867 // We limit this to X < Width in case the backend re-expands the
2868 // intrinsic, and has to reintroduce a shift modulo operation (InstCombine
2869 // might remove it after this fold). This still doesn't guarantee that the
2870 // final codegen will match this original pattern.
2871 if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L))))) {
2872 KnownBits KnownL = computeKnownBits(L, /*Depth*/ 0, &Or);
2873 return KnownL.getMaxValue().ult(Width) ? L : nullptr;
2874 }
2875
2876 // For non-constant cases, the following patterns currently only work for
2877 // rotation patterns.
2878 // TODO: Add general funnel-shift compatible patterns.
2879 if (ShVal0 != ShVal1)
2880 return nullptr;
2881
2882 // For non-constant cases we don't support non-pow2 shift masks.
2883 // TODO: Is it worth matching urem as well?
2884 if (!isPowerOf2_32(Width))
2885 return nullptr;
2886
2887 // The shift amount may be masked with negation:
2888 // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1)))
2889 Value *X;
2890 unsigned Mask = Width - 1;
2891 if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
2892 match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))
2893 return X;
2894
2895 // (shl ShVal, X) | (lshr ShVal, ((-X) & (Width - 1)))
2896 if (match(R, m_And(m_Neg(m_Specific(L)), m_SpecificInt(Mask))))
2897 return L;
2898
2899 // Similar to above, but the shift amount may be extended after masking,
2900 // so return the extended value as the parameter for the intrinsic.
2901 if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2902 match(R,
2904 m_SpecificInt(Mask))))
2905 return L;
2906
2907 if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
2909 return L;
2910
2911 return nullptr;
2912 };
2913
2914 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width);
2915 if (!ShAmt) {
2916 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width);
2917 IsFshl = false; // Sub on SHL.
2918 }
2919 if (!ShAmt)
2920 return std::nullopt;
2921
2922 FShiftArgs = {ShVal0, ShVal1, ShAmt};
2923 } else if (isa<ZExtInst>(Or0) || isa<ZExtInst>(Or1)) {
2924 // If there are two 'or' instructions concat variables in opposite order:
2925 //
2926 // Slot1 and Slot2 are all zero bits.
2927 // | Slot1 | Low | Slot2 | High |
2928 // LowHigh = or (shl (zext Low), ZextLowShlAmt), (zext High)
2929 // | Slot2 | High | Slot1 | Low |
2930 // HighLow = or (shl (zext High), ZextHighShlAmt), (zext Low)
2931 //
2932 // the latter 'or' can be safely convert to
2933 // -> HighLow = fshl LowHigh, LowHigh, ZextHighShlAmt
2934 // if ZextLowShlAmt + ZextHighShlAmt == Width.
2935 if (!isa<ZExtInst>(Or1))
2936 std::swap(Or0, Or1);
2937
2938 Value *High, *ZextHigh, *Low;
2939 const APInt *ZextHighShlAmt;
2940 if (!match(Or0,
2941 m_OneUse(m_Shl(m_Value(ZextHigh), m_APInt(ZextHighShlAmt)))))
2942 return std::nullopt;
2943
2944 if (!match(Or1, m_ZExt(m_Value(Low))) ||
2945 !match(ZextHigh, m_ZExt(m_Value(High))))
2946 return std::nullopt;
2947
2948 unsigned HighSize = High->getType()->getScalarSizeInBits();
2949 unsigned LowSize = Low->getType()->getScalarSizeInBits();
2950 // Make sure High does not overlap with Low and most significant bits of
2951 // High aren't shifted out.
2952 if (ZextHighShlAmt->ult(LowSize) || ZextHighShlAmt->ugt(Width - HighSize))
2953 return std::nullopt;
2954
2955 for (User *U : ZextHigh->users()) {
2956 Value *X, *Y;
2957 if (!match(U, m_Or(m_Value(X), m_Value(Y))))
2958 continue;
2959
2960 if (!isa<ZExtInst>(Y))
2961 std::swap(X, Y);
2962
2963 const APInt *ZextLowShlAmt;
2964 if (!match(X, m_Shl(m_Specific(Or1), m_APInt(ZextLowShlAmt))) ||
2965 !match(Y, m_Specific(ZextHigh)) || !DT.dominates(U, &Or))
2966 continue;
2967
2968 // HighLow is good concat. If sum of two shifts amount equals to Width,
2969 // LowHigh must also be a good concat.
2970 if (*ZextLowShlAmt + *ZextHighShlAmt != Width)
2971 continue;
2972
2973 // Low must not overlap with High and most significant bits of Low must
2974 // not be shifted out.
2975 assert(ZextLowShlAmt->uge(HighSize) &&
2976 ZextLowShlAmt->ule(Width - LowSize) && "Invalid concat");
2977
2978 FShiftArgs = {U, U, ConstantInt::get(Or0->getType(), *ZextHighShlAmt)};
2979 break;
2980 }
2981 }
2982
2983 if (FShiftArgs.empty())
2984 return std::nullopt;
2985
2986 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2987 return std::make_pair(IID, FShiftArgs);
2988}
2989
2990/// Match UB-safe variants of the funnel shift intrinsic.
2992 if (auto Opt = IC.convertOrOfShiftsToFunnelShift(Or)) {
2993 auto [IID, FShiftArgs] = *Opt;
2994 Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType());
2995 return CallInst::Create(F, FShiftArgs);
2996 }
2997
2998 return nullptr;
2999}
3000
3001/// Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
3003 InstCombiner::BuilderTy &Builder) {
3004 assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'");
3005 Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1);
3006 Type *Ty = Or.getType();
3007
3008 unsigned Width = Ty->getScalarSizeInBits();
3009 if ((Width & 1) != 0)
3010 return nullptr;
3011 unsigned HalfWidth = Width / 2;
3012
3013 // Canonicalize zext (lower half) to LHS.
3014 if (!isa<ZExtInst>(Op0))
3015 std::swap(Op0, Op1);
3016
3017 // Find lower/upper half.
3018 Value *LowerSrc, *ShlVal, *UpperSrc;
3019 const APInt *C;
3020 if (!match(Op0, m_OneUse(m_ZExt(m_Value(LowerSrc)))) ||
3021 !match(Op1, m_OneUse(m_Shl(m_Value(ShlVal), m_APInt(C)))) ||
3022 !match(ShlVal, m_OneUse(m_ZExt(m_Value(UpperSrc)))))
3023 return nullptr;
3024 if (*C != HalfWidth || LowerSrc->getType() != UpperSrc->getType() ||
3025 LowerSrc->getType()->getScalarSizeInBits() != HalfWidth)
3026 return nullptr;
3027
3028 auto ConcatIntrinsicCalls = [&](Intrinsic::ID id, Value *Lo, Value *Hi) {
3029 Value *NewLower = Builder.CreateZExt(Lo, Ty);
3030 Value *NewUpper = Builder.CreateZExt(Hi, Ty);
3031 NewUpper = Builder.CreateShl(NewUpper, HalfWidth);
3032 Value *BinOp = Builder.CreateOr(NewLower, NewUpper);
3033 Function *F = Intrinsic::getDeclaration(Or.getModule(), id, Ty);
3034 return Builder.CreateCall(F, BinOp);
3035 };
3036
3037 // BSWAP: Push the concat down, swapping the lower/upper sources.
3038 // concat(bswap(x),bswap(y)) -> bswap(concat(x,y))
3039 Value *LowerBSwap, *UpperBSwap;
3040 if (match(LowerSrc, m_BSwap(m_Value(LowerBSwap))) &&
3041 match(UpperSrc, m_BSwap(m_Value(UpperBSwap))))
3042 return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
3043
3044 // BITREVERSE: Push the concat down, swapping the lower/upper sources.
3045 // concat(bitreverse(x),bitreverse(y)) -> bitreverse(concat(x,y))
3046 Value *LowerBRev, *UpperBRev;
3047 if (match(LowerSrc, m_BitReverse(m_Value(LowerBRev))) &&
3048 match(UpperSrc, m_BitReverse(m_Value(UpperBRev))))
3049 return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
3050
3051 return nullptr;
3052}
3053
3054/// If all elements of two constant vectors are 0/-1 and inverses, return true.
3056 unsigned NumElts = cast<FixedVectorType>(C1->getType())->getNumElements();
3057 for (unsigned i = 0; i != NumElts; ++i) {
3058 Constant *EltC1 = C1->getAggregateElement(i);
3059 Constant *EltC2 = C2->getAggregateElement(i);
3060 if (!EltC1 || !EltC2)
3061 return false;
3062
3063 // One element must be all ones, and the other must be all zeros.
3064 if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
3065 (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
3066 return false;
3067 }
3068 return true;
3069}
3070
3071/// We have an expression of the form (A & C) | (B & D). If A is a scalar or
3072/// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
3073/// B, it can be used as the condition operand of a select instruction.
3074/// We will detect (A & C) | ~(B | D) when the flag ABIsTheSame enabled.
3075Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B,
3076 bool ABIsTheSame) {
3077 // We may have peeked through bitcasts in the caller.
3078 // Exit immediately if we don't have (vector) integer types.
3079 Type *Ty = A->getType();
3080 if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
3081 return nullptr;
3082
3083 // If A is the 'not' operand of B and has enough signbits, we have our answer.
3084 if (ABIsTheSame ? (A == B) : match(B, m_Not(m_Specific(A)))) {
3085 // If these are scalars or vectors of i1, A can be used directly.
3086 if (Ty->isIntOrIntVectorTy(1))
3087 return A;
3088
3089 // If we look through a vector bitcast, the caller will bitcast the operands
3090 // to match the condition's number of bits (N x i1).
3091 // To make this poison-safe, disallow bitcast from wide element to narrow
3092 // element. That could allow poison in lanes where it was not present in the
3093 // original code.
3095 if (A->getType()->isIntOrIntVectorTy()) {
3096 unsigned NumSignBits = ComputeNumSignBits(A);
3097 if (NumSignBits == A->getType()->getScalarSizeInBits() &&
3098 NumSignBits <= Ty->getScalarSizeInBits())
3099 return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(A->getType()));
3100 }
3101 return nullptr;
3102 }
3103
3104 // TODO: add support for sext and constant case
3105 if (ABIsTheSame)
3106 return nullptr;
3107
3108 // If both operands are constants, see if the constants are inverse bitmasks.
3109 Constant *AConst, *BConst;
3110 if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
3111 if (AConst == ConstantExpr::getNot(BConst) &&
3114
3115 // Look for more complex patterns. The 'not' op may be hidden behind various
3116 // casts. Look through sexts and bitcasts to find the booleans.
3117 Value *Cond;
3118 Value *NotB;
3119 if (match(A, m_SExt(m_Value(Cond))) &&
3120 Cond->getType()->isIntOrIntVectorTy(1)) {
3121 // A = sext i1 Cond; B = sext (not (i1 Cond))
3122 if (match(B, m_SExt(m_Not(m_Specific(Cond)))))
3123 return Cond;
3124
3125 // A = sext i1 Cond; B = not ({bitcast} (sext (i1 Cond)))
3126 // TODO: The one-use checks are unnecessary or misplaced. If the caller
3127 // checked for uses on logic ops/casts, that should be enough to
3128 // make this transform worthwhile.
3129 if (match(B, m_OneUse(m_Not(m_Value(NotB))))) {
3130 NotB = peekThroughBitcast(NotB, true);
3131 if (match(NotB, m_SExt(m_Specific(Cond))))
3132 return Cond;
3133 }
3134 }
3135
3136 // All scalar (and most vector) possibilities should be handled now.
3137 // Try more matches that only apply to non-splat constant vectors.
3138 if (!Ty->isVectorTy())
3139 return nullptr;
3140
3141 // If both operands are xor'd with constants using the same sexted boolean
3142 // operand, see if the constants are inverse bitmasks.
3143 // TODO: Use ConstantExpr::getNot()?
3144 if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
3145 match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) &&
3146 Cond->getType()->isIntOrIntVectorTy(1) &&
3147 areInverseVectorBitmasks(AConst, BConst)) {
3149 return Builder.CreateXor(Cond, AConst);
3150 }
3151 return nullptr;
3152}
3153
3154/// We have an expression of the form (A & C) | (B & D). Try to simplify this
3155/// to "A' ? C : D", where A' is a boolean or vector of booleans.
3156/// When InvertFalseVal is set to true, we try to match the pattern
3157/// where we have peeked through a 'not' op and A and B are the same:
3158/// (A & C) | ~(A | D) --> (A & C) | (~A & ~D) --> A' ? C : ~D
3159Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
3160 Value *D, bool InvertFalseVal) {
3161 // The potential condition of the select may be bitcasted. In that case, look
3162 // through its bitcast and the corresponding bitcast of the 'not' condition.
3163 Type *OrigType = A->getType();
3164 A = peekThroughBitcast(A, true);
3165 B = peekThroughBitcast(B, true);
3166 if (Value *Cond = getSelectCondition(A, B, InvertFalseVal)) {
3167 // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
3168 // If this is a vector, we may need to cast to match the condition's length.
3169 // The bitcasts will either all exist or all not exist. The builder will
3170 // not create unnecessary casts if the types already match.
3171 Type *SelTy = A->getType();
3172 if (auto *VecTy = dyn_cast<VectorType>(Cond->getType())) {
3173 // For a fixed or scalable vector get N from <{vscale x} N x iM>
3174 unsigned Elts = VecTy->getElementCount().getKnownMinValue();
3175 // For a fixed or scalable vector, get the size in bits of N x iM; for a
3176 // scalar this is just M.
3177 unsigned SelEltSize = SelTy->getPrimitiveSizeInBits().getKnownMinValue();
3178 Type *EltTy = Builder.getIntNTy(SelEltSize / Elts);
3179 SelTy = VectorType::get(EltTy, VecTy->getElementCount());
3180 }
3181 Value *BitcastC = Builder.CreateBitCast(C, SelTy);
3182 if (InvertFalseVal)
3183 D = Builder.CreateNot(D);
3184 Value *BitcastD = Builder.CreateBitCast(D, SelTy);
3185 Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
3186 return Builder.CreateBitCast(Select, OrigType);
3187 }
3188
3189 return nullptr;
3190}
3191
3192// (icmp eq X, C) | (icmp ult Other, (X - C)) -> (icmp ule Other, (X - (C + 1)))
3193// (icmp ne X, C) & (icmp uge Other, (X - C)) -> (icmp ugt Other, (X - (C + 1)))
3195 bool IsAnd, bool IsLogical,
3196 IRBuilderBase &Builder) {
3197 Value *LHS0 = LHS->getOperand(0);
3198 Value *RHS0 = RHS->getOperand(0);
3199 Value *RHS1 = RHS->getOperand(1);
3200
3201 ICmpInst::Predicate LPred =
3202 IsAnd ? LHS->getInversePredicate() : LHS->getPredicate();
3203 ICmpInst::Predicate RPred =
3204 IsAnd ? RHS->getInversePredicate() : RHS->getPredicate();
3205
3206 const APInt *CInt;
3207 if (LPred != ICmpInst::ICMP_EQ ||
3208 !match(LHS->getOperand(1), m_APIntAllowUndef(CInt)) ||
3209 !LHS0->getType()->isIntOrIntVectorTy() ||
3210 !(LHS->hasOneUse() || RHS->hasOneUse()))
3211 return nullptr;
3212
3213 auto MatchRHSOp = [LHS0, CInt](const Value *RHSOp) {
3214 return match(RHSOp,
3215 m_Add(m_Specific(LHS0), m_SpecificIntAllowUndef(-*CInt))) ||
3216 (CInt->isZero() && RHSOp == LHS0);
3217 };
3218
3219 Value *Other;
3220 if (RPred == ICmpInst::ICMP_ULT && MatchRHSOp(RHS1))
3221 Other = RHS0;
3222 else if (RPred == ICmpInst::ICMP_UGT && MatchRHSOp(RHS0))
3223 Other = RHS1;
3224 else
3225 return nullptr;
3226
3227 if (IsLogical)
3228 Other = Builder.CreateFreeze(Other);
3229
3230 return Builder.CreateICmp(
3232 Builder.CreateSub(LHS0, ConstantInt::get(LHS0->getType(), *CInt + 1)),
3233 Other);
3234}
3235
3236/// Fold (icmp)&(icmp) or (icmp)|(icmp) if possible.
3237/// If IsLogical is true, then the and/or is in select form and the transform
3238/// must be poison-safe.
3239Value *InstCombinerImpl::foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
3240 Instruction &I, bool IsAnd,
3241 bool IsLogical) {
3243
3244 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
3245 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2)
3246 // if K1 and K2 are a one-bit mask.
3247 if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, &I, IsAnd, IsLogical))
3248 return V;
3249
3250 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
3251 Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
3252 Value *LHS1 = LHS->getOperand(1), *RHS1 = RHS->getOperand(1);
3253 const APInt *LHSC = nullptr, *RHSC = nullptr;
3254 match(LHS1, m_APInt(LHSC));
3255 match(RHS1, m_APInt(RHSC));
3256
3257 // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
3258 // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
3259 if (predicatesFoldable(PredL, PredR)) {
3260 if (LHS0 == RHS1 && LHS1 == RHS0) {
3261 PredL = ICmpInst::getSwappedPredicate(PredL);
3262 std::swap(LHS0, LHS1);
3263 }
3264 if (LHS0 == RHS0 && LHS1 == RHS1) {
3265 unsigned Code = IsAnd ? getICmpCode(PredL) & getICmpCode(PredR)
3266 : getICmpCode(PredL) | getICmpCode(PredR);
3267 bool IsSigned = LHS->isSigned() || RHS->isSigned();
3268 return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
3269 }
3270 }
3271
3272 // handle (roughly):
3273 // (icmp ne (A & B), C) | (icmp ne (A & D), E)
3274 // (icmp eq (A & B), C) & (icmp eq (A & D), E)
3275 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, IsAnd, IsLogical, Builder))
3276 return V;
3277
3278 if (Value *V =
3279 foldAndOrOfICmpEqConstantAndICmp(LHS, RHS, IsAnd, IsLogical, Builder))
3280 return V;
3281 // We can treat logical like bitwise here, because both operands are used on
3282 // the LHS, and as such poison from both will propagate.
3283 if (Value *V = foldAndOrOfICmpEqConstantAndICmp(RHS, LHS, IsAnd,
3284 /*IsLogical*/ false, Builder))
3285 return V;
3286
3287 if (Value *V =
3288 foldAndOrOfICmpsWithConstEq(LHS, RHS, IsAnd, IsLogical, Builder, Q))
3289 return V;
3290 // We can convert this case to bitwise and, because both operands are used
3291 // on the LHS, and as such poison from both will propagate.
3292 if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, IsAnd,
3293 /*IsLogical*/ false, Builder, Q))
3294 return V;
3295
3296 if (Value *V = foldIsPowerOf2OrZero(LHS, RHS, IsAnd, Builder))
3297 return V;
3298 if (Value *V = foldIsPowerOf2OrZero(RHS, LHS, IsAnd, Builder))
3299 return V;
3300
3301 // TODO: One of these directions is fine with logical and/or, the other could
3302 // be supported by inserting freeze.
3303 if (!IsLogical) {
3304 // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
3305 // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
3306 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/!IsAnd))
3307 return V;
3308
3309 // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
3310 // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
3311 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/!IsAnd))
3312 return V;
3313 }
3314
3315 // TODO: Add conjugated or fold, check whether it is safe for logical and/or.
3316 if (IsAnd && !IsLogical)
3317 if (Value *V = foldSignedTruncationCheck(LHS, RHS, I, Builder))
3318 return V;
3319
3320 if (Value *V = foldIsPowerOf2(LHS, RHS, IsAnd, Builder))
3321 return V;
3322
3323 if (Value *V = foldPowerOf2AndShiftedMask(LHS, RHS, IsAnd, Builder))
3324 return V;
3325
3326 // TODO: Verify whether this is safe for logical and/or.
3327 if (!IsLogical) {
3328 if (Value *X = foldUnsignedUnderflowCheck(LHS, RHS, IsAnd, Q, Builder))
3329 return X;
3330 if (Value *X = foldUnsignedUnderflowCheck(RHS, LHS, IsAnd, Q, Builder))
3331 return X;
3332 }
3333
3334 if (Value *X = foldEqOfParts(LHS, RHS, IsAnd))
3335 return X;
3336
3337 // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
3338 // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
3339 // TODO: Remove this and below when foldLogOpOfMaskedICmps can handle undefs.
3340 if (!IsLogical && PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
3341 PredL == PredR && match(LHS1, m_ZeroInt()) && match(RHS1, m_ZeroInt()) &&
3342 LHS0->getType() == RHS0->getType()) {
3343 Value *NewOr = Builder.CreateOr(LHS0, RHS0);
3344 return Builder.CreateICmp(PredL, NewOr,
3346 }
3347
3348 // (icmp ne A, -1) | (icmp ne B, -1) --> (icmp ne (A&B), -1)
3349 // (icmp eq A, -1) & (icmp eq B, -1) --> (icmp eq (A&B), -1)
3350 if (!IsLogical && PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
3351 PredL == PredR && match(LHS1, m_AllOnes()) && match(RHS1, m_AllOnes()) &&
3352 LHS0->getType() == RHS0->getType()) {
3353 Value *NewAnd = Builder.CreateAnd(LHS0, RHS0);
3354 return Builder.CreateICmp(PredL, NewAnd,
3356 }
3357
3358 // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
3359 if (!LHSC || !RHSC)
3360 return nullptr;
3361
3362 // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
3363 // (trunc x) != C1 | (and x, CA) != C2 -> (and x, CA|CMAX) != C1|C2
3364 // where CMAX is the all ones value for the truncated type,
3365 // iff the lower bits of C2 and CA are zero.
3366 if (PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
3367 PredL == PredR && LHS->hasOneUse() && RHS->hasOneUse()) {
3368 Value *V;
3369 const APInt *AndC, *SmallC = nullptr, *BigC = nullptr;
3370
3371 // (trunc x) == C1 & (and x, CA) == C2
3372 // (and x, CA) == C2 & (trunc x) == C1
3373 if (match(RHS0, m_Trunc(m_Value(V))) &&
3374 match(LHS0, m_And(m_Specific(V), m_APInt(AndC)))) {
3375 SmallC = RHSC;
3376 BigC = LHSC;
3377 } else if (match(LHS0, m_Trunc(m_Value(V))) &&
3378 match(RHS0, m_And(m_Specific(V), m_APInt(AndC)))) {
3379 SmallC = LHSC;
3380 BigC = RHSC;
3381 }
3382
3383 if (SmallC && BigC) {
3384 unsigned BigBitSize = BigC->getBitWidth();
3385 unsigned SmallBitSize = SmallC->getBitWidth();
3386
3387 // Check that the low bits are zero.
3388 APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
3389 if ((Low & *AndC).isZero() && (Low & *BigC).isZero()) {
3390 Value *NewAnd = Builder.CreateAnd(V, Low | *AndC);
3391 APInt N = SmallC->zext(BigBitSize) | *BigC;
3392 Value *NewVal = ConstantInt::get(NewAnd->getType(), N);
3393 return Builder.CreateICmp(PredL, NewAnd, NewVal);
3394 }
3395 }
3396 }
3397
3398 // Match naive pattern (and its inverted form) for checking if two values
3399 // share same sign. An example of the pattern:
3400 // (icmp slt (X & Y), 0) | (icmp sgt (X | Y), -1) -> (icmp sgt (X ^ Y), -1)
3401 // Inverted form (example):
3402 // (icmp slt (X | Y), 0) & (icmp sgt (X & Y), -1) -> (icmp slt (X ^ Y), 0)
3403 bool TrueIfSignedL, TrueIfSignedR;
3404 if (isSignBitCheck(PredL, *LHSC, TrueIfSignedL) &&
3405 isSignBitCheck(PredR, *RHSC, TrueIfSignedR) &&
3406 (RHS->hasOneUse() || LHS->hasOneUse())) {
3407 Value *X, *Y;
3408 if (IsAnd) {
3409 if ((TrueIfSignedL && !TrueIfSignedR &&
3410 match(LHS0, m_Or(m_Value(X), m_Value(Y))) &&
3411 match(RHS0, m_c_And(m_Specific(X), m_Specific(Y)))) ||
3412 (!TrueIfSignedL && TrueIfSignedR &&
3413 match(LHS0, m_And(m_Value(X), m_Value(Y))) &&
3414 match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y))))) {
3415 Value *NewXor = Builder.CreateXor(X, Y);
3416 return Builder.CreateIsNeg(NewXor);
3417 }
3418 } else {
3419 if ((TrueIfSignedL && !TrueIfSignedR &&
3420 match(LHS0, m_And(m_Value(X), m_Value(Y))) &&
3421 match(RHS0, m_c_Or(m_Specific(X), m_Specific(Y)))) ||
3422 (!TrueIfSignedL && TrueIfSignedR &&
3423 match(LHS0, m_Or(m_Value(X), m_Value(Y))) &&
3424 match(RHS0, m_c_And(m_Specific(X), m_Specific(Y))))) {
3425 Value *NewXor = Builder.CreateXor(X, Y);
3426 return Builder.CreateIsNotNeg(NewXor);
3427 }
3428 }
3429 }
3430
3431 return foldAndOrOfICmpsUsingRanges(LHS, RHS, IsAnd);
3432}
3433
3434// FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
3435// here. We should standardize that construct where it is needed or choose some
3436// other way to ensure that commutated variants of patterns are not missed.
3438 if (Value *V = simplifyOrInst(I.getOperand(0), I.getOperand(1),
3440 return replaceInstUsesWith(I, V);
3441
3443 return &I;
3444
3446 return X;
3447
3449 return Phi;
3450
3451 // See if we can simplify any instructions used by the instruction whose sole
3452 // purpose is to compute bits we don't care about.
3454 return &I;
3455
3456 // Do this before using distributive laws to catch simple and/or/not patterns.
3458 return Xor;
3459
3461 return X;
3462
3463 // (A&B)|(A&C) -> A&(B|C) etc
3465 return replaceInstUsesWith(I, V);
3466
3467 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
3468 Type *Ty = I.getType();
3469 if (Ty->isIntOrIntVectorTy(1)) {
3470 if (auto *SI0 = dyn_cast<SelectInst>(Op0)) {
3471 if (auto *R =
3472 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false))
3473 return R;
3474 }
3475 if (auto *SI1 = dyn_cast<SelectInst>(Op1)) {
3476 if (auto *R =
3477 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ false))
3478 return R;
3479 }
3480 }
3481
3482 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
3483 return FoldedLogic;
3484
3485 if (Instruction *BitOp = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
3486 /*MatchBitReversals*/ true))
3487 return BitOp;
3488
3489 if (Instruction *Funnel = matchFunnelShift(I, *this))
3490 return Funnel;
3491
3493 return replaceInstUsesWith(I, Concat);
3494
3496 return R;
3497
3499 return R;
3500
3501 Value *X, *Y;
3502 const APInt *CV;
3503 if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
3504 !CV->isAllOnes() && MaskedValueIsZero(Y, *CV, 0, &I)) {
3505 // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
3506 // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
3507 Value *Or = Builder.CreateOr(X, Y);
3508 return BinaryOperator::CreateXor(Or, ConstantInt::get(Ty, *CV));
3509 }
3510
3511 // If the operands have no common bits set:
3512 // or (mul X, Y), X --> add (mul X, Y), X --> mul X, (Y + 1)
3514 m_Deferred(X)))) {
3515 Value *IncrementY = Builder.CreateAdd(Y, ConstantInt::get(Ty, 1));
3516 return BinaryOperator::CreateMul(X, IncrementY);
3517 }
3518
3519 // (A & C) | (B & D)
3520 Value *A, *B, *C, *D;
3521 if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
3522 match(Op1, m_And(m_Value(B), m_Value(D)))) {
3523
3524 // (A & C0) | (B & C1)
3525 const APInt *C0, *C1;
3526 if (match(C, m_APInt(C0)) && match(D, m_APInt(C1))) {
3527 Value *X;
3528 if (*C0 == ~*C1) {
3529 // ((X | B) & MaskC) | (B & ~MaskC) -> (X & MaskC) | B
3530 if (match(A, m_c_Or(m_Value(X), m_Specific(B))))
3531 return BinaryOperator::CreateOr(Builder.CreateAnd(X, *C0), B);
3532 // (A & MaskC) | ((X | A) & ~MaskC) -> (X & ~MaskC) | A
3533 if (match(B, m_c_Or(m_Specific(A), m_Value(X))))
3534 return BinaryOperator::CreateOr(Builder.CreateAnd(X, *C1), A);
3535
3536 // ((X ^ B) & MaskC) | (B & ~MaskC) -> (X & MaskC) ^ B
3537 if (match(A, m_c_Xor(m_Value(X), m_Specific(B))))
3538 return BinaryOperator::CreateXor(Builder.CreateAnd(X, *C0), B);
3539 // (A & MaskC) | ((X ^ A) & ~MaskC) -> (X & ~MaskC) ^ A
3540 if (match(B, m_c_Xor(m_Specific(A), m_Value(X))))
3541 return BinaryOperator::CreateXor(Builder.CreateAnd(X, *C1), A);
3542 }
3543
3544 if ((*C0 & *C1).isZero()) {
3545 // ((X | B) & C0) | (B & C1) --> (X | B) & (C0 | C1)
3546 // iff (C0 & C1) == 0 and (X & ~C0) == 0
3547 if (match(A, m_c_Or(m_Value(X), m_Specific(B))) &&
3548 MaskedValueIsZero(X, ~*C0, 0, &I)) {
3549 Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
3550 return BinaryOperator::CreateAnd(A, C01);
3551 }
3552 // (A & C0) | ((X | A) & C1) --> (X | A) & (C0 | C1)
3553 // iff (C0 & C1) == 0 and (X & ~C1) == 0
3554 if (match(B, m_c_Or(m_Value(X), m_Specific(A))) &&
3555 MaskedValueIsZero(X, ~*C1, 0, &I)) {
3556 Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
3557 return BinaryOperator::CreateAnd(B, C01);
3558 }
3559 // ((X | C2) & C0) | ((X | C3) & C1) --> (X | C2 | C3) & (C0 | C1)
3560 // iff (C0 & C1) == 0 and (C2 & ~C0) == 0 and (C3 & ~C1) == 0.
3561 const APInt *C2, *C3;
3562 if (match(A, m_Or(m_Value(X), m_APInt(C2))) &&
3563 match(B, m_Or(m_Specific(X), m_APInt(C3))) &&
3564 (*C2 & ~*C0).isZero() && (*C3 & ~*C1).isZero()) {
3565 Value *Or = Builder.CreateOr(X, *C2 | *C3, "bitfield");
3566 Constant *C01 = ConstantInt::get(Ty, *C0 | *C1);
3567 return BinaryOperator::CreateAnd(Or, C01);
3568 }
3569 }
3570 }
3571
3572 // Don't try to form a select if it's unlikely that we'll get rid of at
3573 // least one of the operands. A select is generally more expensive than the
3574 // 'or' that it is replacing.
3575 if (Op0->hasOneUse() || Op1->hasOneUse()) {
3576 // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
3577 if (Value *V = matchSelectFromAndOr(A, C, B, D))
3578 return replaceInstUsesWith(I, V);
3579 if (Value *V = matchSelectFromAndOr(A, C, D, B))
3580 return replaceInstUsesWith(I, V);
3581 if (Value *V = matchSelectFromAndOr(C, A, B, D))
3582 return replaceInstUsesWith(I, V);
3583 if (Value *V = matchSelectFromAndOr(C, A, D, B))
3584 return replaceInstUsesWith(I, V);
3585 if (Value *V = matchSelectFromAndOr(B, D, A, C))
3586 return replaceInstUsesWith(I, V);
3587 if (Value *V = matchSelectFromAndOr(B, D, C, A))
3588 return replaceInstUsesWith(I, V);
3589 if (Value *V = matchSelectFromAndOr(D, B, A, C))
3590 return replaceInstUsesWith(I, V);
3591 if (Value *V = matchSelectFromAndOr(D, B, C, A))
3592 return replaceInstUsesWith(I, V);
3593 }
3594 }
3595
3596 if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
3597 match(Op1, m_Not(m_Or(m_Value(B), m_Value(D)))) &&
3598 (Op0->hasOneUse() || Op1->hasOneUse())) {
3599 // (Cond & C) | ~(Cond | D) -> Cond ? C : ~D
3600 if (Value *V = matchSelectFromAndOr(A, C, B, D, true))
3601 return replaceInstUsesWith(I, V);
3602 if (Value *V = matchSelectFromAndOr(A, C, D, B, true))
3603 return replaceInstUsesWith(I, V);
3604 if (Value *V = matchSelectFromAndOr(C, A, B, D, true))
3605 return replaceInstUsesWith(I, V);
3606 if (Value *V = matchSelectFromAndOr(C, A, D, B, true))
3607 return replaceInstUsesWith(I, V);
3608 }
3609
3610 // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
3611 if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
3612 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
3613 return BinaryOperator::CreateOr(Op0, C);
3614
3615 // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
3616 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
3617 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
3618 return BinaryOperator::CreateOr(Op1, C);
3619
3620 if (Instruction *DeMorgan = matchDeMorgansLaws(I, *this))
3621 return DeMorgan;
3622
3623 // Canonicalize xor to the RHS.
3624 bool SwappedForXor = false;
3625 if (match(Op0, m_Xor(m_Value(), m_Value()))) {
3626 std::swap(Op0, Op1);
3627 SwappedForXor = true;
3628 }
3629
3630 if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
3631 // (A | ?) | (A ^ B) --> (A | ?) | B
3632 // (B | ?) | (A ^ B) --> (B | ?) | A
3633 if (match(Op0, m_c_Or(m_Specific(A), m_Value())))
3634 return BinaryOperator::CreateOr(Op0, B);
3635 if (match(Op0, m_c_Or(m_Specific(B), m_Value())))
3636 return BinaryOperator::CreateOr(Op0, A);
3637
3638 // (A & B) | (A ^ B) --> A | B
3639 // (B & A) | (A ^ B) --> A | B
3640 if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
3641 match(Op0, m_And(m_Specific(B), m_Specific(A))))
3642 return BinaryOperator::CreateOr(A, B);
3643
3644 // ~A | (A ^ B) --> ~(A & B)
3645 // ~B | (A ^ B) --> ~(A & B)
3646 // The swap above should always make Op0 the 'not'.
3647 if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
3648 (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B)))))
3650
3651 // Same as above, but peek through an 'and' to the common operand:
3652 // ~(A & ?) | (A ^ B) --> ~((A & ?) & B)
3653 // ~(B & ?) | (A ^ B) --> ~((B & ?) & A)
3655 if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
3657 m_c_And(m_Specific(A), m_Value())))))
3659 if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
3661 m_c_And(m_Specific(B), m_Value())))))
3663
3664 // (~A | C) | (A ^ B) --> ~(A & B) | C
3665 // (~B | C) | (A ^ B) --> ~(A & B) | C
3666 if (Op0->hasOneUse() && Op1->hasOneUse() &&
3667 (match(Op0, m_c_Or(m_Not(m_Specific(A)), m_Value(C))) ||
3668 match(Op0, m_c_Or(m_Not(m_Specific(B)), m_Value(C))))) {
3669 Value *Nand = Builder.CreateNot(Builder.CreateAnd(A, B), "nand");
3670 return BinaryOperator::CreateOr(Nand, C);
3671 }
3672 }
3673
3674 if (SwappedForXor)
3675 std::swap(Op0, Op1);
3676
3677 {
3678 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
3679 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
3680 if (LHS && RHS)
3681 if (Value *Res = foldAndOrOfICmps(LHS, RHS, I, /* IsAnd */ false))
3682 return replaceInstUsesWith(I, Res);
3683
3684 // TODO: Make this recursive; it's a little tricky because an arbitrary
3685 // number of 'or' instructions might have to be created.
3686 Value *X, *Y;
3687 if (LHS && match(Op1, m_OneUse(m_LogicalOr(m_Value(X), m_Value(Y))))) {
3688 bool IsLogical = isa<SelectInst>(Op1);
3689 // LHS | (X || Y) --> (LHS || X) || Y
3690 if (auto *Cmp = dyn_cast<ICmpInst>(X))
3691 if (Value *Res =
3692 foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ false, IsLogical))
3693 return replaceInstUsesWith(I, IsLogical
3694 ? Builder.CreateLogicalOr(Res, Y)
3695 : Builder.CreateOr(Res, Y));
3696 // LHS | (X || Y) --> X || (LHS | Y)
3697 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
3698 if (Value *Res = foldAndOrOfICmps(LHS, Cmp, I, /* IsAnd */ false,
3699 /* IsLogical */ false))
3700 return replaceInstUsesWith(I, IsLogical
3701 ? Builder.CreateLogicalOr(X, Res)
3702 : Builder.CreateOr(X, Res));
3703 }
3704 if (RHS && match(Op0, m_OneUse(m_LogicalOr(m_Value(X), m_Value(Y))))) {
3705 bool IsLogical = isa<SelectInst>(Op0);
3706 // (X || Y) | RHS --> (X || RHS) || Y
3707 if (auto *Cmp = dyn_cast<ICmpInst>(X))
3708 if (Value *Res =
3709 foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ false, IsLogical))
3710 return replaceInstUsesWith(I, IsLogical
3711 ? Builder.CreateLogicalOr(Res, Y)
3712 : Builder.CreateOr(Res, Y));
3713 // (X || Y) | RHS --> X || (Y | RHS)
3714 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
3715 if (Value *Res = foldAndOrOfICmps(Cmp, RHS, I, /* IsAnd */ false,
3716 /* IsLogical */ false))
3717 return replaceInstUsesWith(I, IsLogical
3718 ? Builder.CreateLogicalOr(X, Res)
3719 : Builder.CreateOr(X, Res));
3720 }
3721 }
3722
3723 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
3724 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
3725 if (Value *Res = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false))
3726 return replaceInstUsesWith(I, Res);
3727
3728 if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder))
3729 return FoldedFCmps;
3730
3731 if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
3732 return CastedOr;
3733
3734 if (Instruction *Sel = foldBinopOfSextBoolToSelect(I))
3735 return Sel;
3736
3737 // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
3738 // TODO: Move this into foldBinopOfSextBoolToSelect as a more generalized fold
3739 // with binop identity constant. But creating a select with non-constant
3740 // arm may not be reversible due to poison semantics. Is that a good
3741 // canonicalization?
3742 if (match(&I, m_c_Or(m_OneUse(m_SExt(m_Value(A))), m_Value(B))) &&
3743 A->getType()->isIntOrIntVectorTy(1))
3745
3746 // Note: If we've gotten to the point of visiting the outer OR, then the
3747 // inner one couldn't be simplified. If it was a constant, then it won't
3748 // be simplified by a later pass either, so we try swapping the inner/outer
3749 // ORs in the hopes that we'll be able to simplify it this way.
3750 // (X|C) | V --> (X|V) | C
3751 ConstantInt *CI;
3752 if (Op0->hasOneUse() && !match(Op1, m_ConstantInt()) &&
3753 match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) {
3754 Value *Inner = Builder.CreateOr(A, Op1);
3755 Inner->takeName(Op0);
3756 return BinaryOperator::CreateOr(Inner, CI);
3757 }
3758
3759 // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
3760 // Since this OR statement hasn't been optimized further yet, we hope
3761 // that this transformation will allow the new ORs to be optimized.
3762 {
3763 Value *X = nullptr, *Y = nullptr;
3764 if (Op0->hasOneUse() && Op1->hasOneUse() &&
3765 match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
3766 match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
3767 Value *orTrue = Builder.CreateOr(A, C);
3768 Value *orFalse = Builder.CreateOr(B, D);
3769 return SelectInst::Create(X, orTrue, orFalse);
3770 }
3771 }
3772
3773 // or(ashr(subNSW(Y, X), ScalarSizeInBits(Y) - 1), X) --> X s> Y ? -1 : X.
3774 {
3775 Value *X, *Y;
3779 m_Deferred(X)))) {
3780 Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
3782 return SelectInst::Create(NewICmpInst, AllOnes, X);
3783 }
3784 }
3785
3786 {
3787 // ((A & B) ^ A) | ((A & B) ^ B) -> A ^ B
3788 // (A ^ (A & B)) | (B ^ (A & B)) -> A ^ B
3789 // ((A & B) ^ B) | ((A & B) ^ A) -> A ^ B
3790 // (B ^ (A & B)) | (A ^ (A & B)) -> A ^ B
3791 const auto TryXorOpt = [&](Value *Lhs, Value *Rhs) -> Instruction * {
3792 if (match(Lhs, m_c_Xor(m_And(m_Value(A), m_Value(B)), m_Deferred(A))) &&
3793 match(Rhs,
3795 return BinaryOperator::CreateXor(A, B);
3796 }
3797 return nullptr;
3798 };
3799
3800 if (Instruction *Result = TryXorOpt(Op0, Op1))
3801 return Result;
3802 if (Instruction *Result = TryXorOpt(Op1, Op0))
3803 return Result;
3804 }
3805
3806 if (Instruction *V =
3808 return V;
3809
3810 CmpInst::Predicate Pred;
3811 Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
3812 // Check if the OR weakens the overflow condition for umul.with.overflow by
3813 // treating any non-zero result as overflow. In that case, we overflow if both
3814 // umul.with.overflow operands are != 0, as in that case the result can only
3815 // be 0, iff the multiplication overflows.
3816 if (match(&I,
3817 m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_Value(UMulWithOv)),
3818 m_Value(Ov)),
3819 m_CombineAnd(m_ICmp(Pred,
3820 m_CombineAnd(m_ExtractValue<0>(
3821 m_Deferred(UMulWithOv)),
3822 m_Value(Mul)),
3823 m_ZeroInt()),
3824 m_Value(MulIsNotZero)))) &&
3825 (Ov->hasOneUse() || (MulIsNotZero->hasOneUse() && Mul->hasOneUse())) &&
3826 Pred == CmpInst::ICMP_NE) {
3827 Value *A, *B;
3828 if (match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
3829 m_Value(A), m_Value(B)))) {
3830 Value *NotNullA = Builder.CreateIsNotNull(A);
3831 Value *NotNullB = Builder.CreateIsNotNull(B);
3832 return BinaryOperator::CreateAnd(NotNullA, NotNullB);
3833 }
3834 }
3835
3836 /// Res, Overflow = xxx_with_overflow X, C1
3837 /// Try to canonicalize the pattern "Overflow | icmp pred Res, C2" into
3838 /// "Overflow | icmp pred X, C2 +/- C1".
3839 const WithOverflowInst *WO;
3840 const Value *WOV;
3841 const APInt *C1, *C2;
3842 if (match(&I, m_c_Or(m_CombineAnd(m_ExtractValue<1>(m_CombineAnd(
3843 m_WithOverflowInst(WO), m_Value(WOV))),
3844 m_Value(Ov)),
3845 m_OneUse(m_ICmp(Pred, m_ExtractValue<0>(m_Deferred(WOV)),
3846 m_AP