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_APInt(C2))))) &&
3847 (WO->getBinaryOp() == Instruction::Add ||
3848 WO->getBinaryOp() == Instruction::Sub) &&
3849 (ICmpInst::isEquality(Pred) ||
3850 WO->isSigned() == ICmpInst::isSigned(Pred)) &&
3851 match(WO->getRHS(), m_APInt(C1))) {
3852 bool Overflow;
3853 APInt NewC = WO->getBinaryOp() == Instruction::Add
3854 ? (ICmpInst::isSigned(Pred) ? C2->ssub_ov(*C1, Overflow)
3855 : C2->usub_ov(*C1, Overflow))
3856 : (ICmpInst::isSigned(Pred) ? C2->sadd_ov(*C1, Overflow)
3857 : C2->uadd_ov(*C1, Overflow));
3858 if (!Overflow || ICmpInst::isEquality(Pred)) {
3859 Value *NewCmp = Builder.CreateICmp(
3860 Pred, WO->getLHS(), ConstantInt::get(WO->getLHS()->getType(), NewC));
3861 return BinaryOperator::CreateOr(Ov, NewCmp);
3862 }
3863 }
3864
3865 // (~x) | y --> ~(x & (~y)) iff that gets rid of inversions
3867 return &I;
3868
3869 // Improve "get low bit mask up to and including bit X" pattern:
3870 // (1 << X) | ((1 << X) + -1) --> -1 l>> (bitwidth(x) - 1 - X)
3871 if (match(&I, m_c_Or(m_Add(m_Shl(m_One(), m_Value(X)), m_AllOnes()),
3872 m_Shl(m_One(), m_Deferred(X)))) &&
3873 match(&I, m_c_Or(m_OneUse(m_Value()), m_Value()))) {
3874 Value *Sub = Builder.CreateSub(
3875 ConstantInt::get(Ty, Ty->getScalarSizeInBits() - 1), X);
3876 return BinaryOperator::CreateLShr(Constant::getAllOnesValue(Ty), Sub);
3877 }
3878
3879 // An or recurrence w/loop invariant step is equivelent to (or start, step)
3880 PHINode *PN = nullptr;
3881 Value *Start = nullptr, *Step = nullptr;
3882 if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
3883 return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
3884
3885 // (A & B) | (C | D) or (C | D) | (A & B)
3886 // Can be combined if C or D is of type (A/B & X)
3888 m_OneUse(m_Or(m_Value(C), m_Value(D)))))) {
3889 // (A & B) | (C | ?) -> C | (? | (A & B))
3890 // (A & B) | (C | ?) -> C | (? | (A & B))
3891 // (A & B) | (C | ?) -> C | (? | (A & B))
3892 // (A & B) | (C | ?) -> C | (? | (A & B))
3893 // (C | ?) | (A & B) -> C | (? | (A & B))
3894 // (C | ?) | (A & B) -> C | (? | (A & B))
3895 // (C | ?) | (A & B) -> C | (? | (A & B))
3896 // (C | ?) | (A & B) -> C | (? | (A & B))
3897 if (match(D, m_OneUse(m_c_And(m_Specific(A), m_Value()))) ||
3899 return BinaryOperator::CreateOr(
3901 // (A & B) | (? | D) -> (? | (A & B)) | D
3902 // (A & B) | (? | D) -> (? | (A & B)) | D
3903 // (A & B) | (? | D) -> (? | (A & B)) | D
3904 // (A & B) | (? | D) -> (? | (A & B)) | D
3905 // (? | D) | (A & B) -> (? | (A & B)) | D
3906 // (? | D) | (A & B) -> (? | (A & B)) | D
3907 // (? | D) | (A & B) -> (? | (A & B)) | D
3908 // (? | D) | (A & B) -> (? | (A & B)) | D
3909 if (match(C, m_OneUse(m_c_And(m_Specific(A), m_Value()))) ||
3911 return BinaryOperator::CreateOr(
3913 }
3914
3916 return R;
3917
3918 if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
3919 return Canonicalized;
3920
3921 if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1))
3922 return Folded;
3923
3924 if (Instruction *Res = foldBinOpOfDisplacedShifts(I))
3925 return Res;
3926
3927 // If we are setting the sign bit of a floating-point value, convert
3928 // this to fneg(fabs), then cast back to integer.
3929 //
3930 // If the result isn't immediately cast back to a float, this will increase
3931 // the number of instructions. This is still probably a better canonical form
3932 // as it enables FP value tracking.
3933 //
3934 // Assumes any IEEE-represented type has the sign bit in the high bit.
3935 //
3936 // This is generous interpretation of noimplicitfloat, this is not a true
3937 // floating-point operation.
3938 Value *CastOp;
3939 if (match(Op0, m_ElementWiseBitCast(m_Value(CastOp))) &&
3940 match(Op1, m_SignMask()) &&
3942 Attribute::NoImplicitFloat)) {
3943 Type *EltTy = CastOp->getType()->getScalarType();
3944 if (EltTy->isFloatingPointTy() && EltTy->isIEEE()) {
3945 Value *FAbs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, CastOp);
3946 Value *FNegFAbs = Builder.CreateFNeg(FAbs);
3947 return new BitCastInst(FNegFAbs, I.getType());
3948 }
3949 }
3950
3951 // (X & C1) | C2 -> X & (C1 | C2) iff (X & C2) == C2
3952 if (match(Op0, m_OneUse(m_And(m_Value(X), m_APInt(C1)))) &&
3953 match(Op1, m_APInt(C2))) {
3954 KnownBits KnownX = computeKnownBits(X, /*Depth*/ 0, &I);
3955 if ((KnownX.One & *C2) == *C2)
3956 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, *C1 | *C2));
3957 }
3958
3960 return Res;
3961
3962 if (Value *V =
3964 /*SimplifyOnly*/ false, *this))
3965 return BinaryOperator::CreateOr(V, Op1);
3966 if (Value *V =
3968 /*SimplifyOnly*/ false, *this))
3969 return BinaryOperator::CreateOr(Op0, V);
3970
3971 return nullptr;
3972}
3973
3974/// A ^ B can be specified using other logic ops in a variety of patterns. We
3975/// can fold these early and efficiently by morphing an existing instruction.
3977 InstCombiner::BuilderTy &Builder) {
3978 assert(I.getOpcode() == Instruction::Xor);
3979 Value *Op0 = I.getOperand(0);
3980 Value *Op1 = I.getOperand(1);
3981 Value *A, *B;
3982
3983 // There are 4 commuted variants for each of the basic patterns.
3984
3985 // (A & B) ^ (A | B) -> A ^ B
3986 // (A & B) ^ (B | A) -> A ^ B
3987 // (A | B) ^ (A & B) -> A ^ B
3988 // (A | B) ^ (B & A) -> A ^ B
3989 if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)),
3991 return BinaryOperator::CreateXor(A, B);
3992
3993 // (A | ~B) ^ (~A | B) -> A ^ B
3994 // (~B | A) ^ (~A | B) -> A ^ B
3995 // (~A | B) ^ (A | ~B) -> A ^ B
3996 // (B | ~A) ^ (A | ~B) -> A ^ B
3997 if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))),
3999 return BinaryOperator::CreateXor(A, B);
4000
4001 // (A & ~B) ^ (~A & B) -> A ^ B
4002 // (~B & A) ^ (~A & B) -> A ^ B
4003 // (~A & B) ^ (A & ~B) -> A ^ B
4004 // (B & ~A) ^ (A & ~B) -> A ^ B
4005 if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))),
4007 return BinaryOperator::CreateXor(A, B);
4008
4009 // For the remaining cases we need to get rid of one of the operands.
4010 if (!Op0->hasOneUse() && !Op1->hasOneUse())
4011 return nullptr;
4012
4013 // (A | B) ^ ~(A & B) -> ~(A ^ B)
4014 // (A | B) ^ ~(B & A) -> ~(A ^ B)
4015 // (A & B) ^ ~(A | B) -> ~(A ^ B)
4016 // (A & B) ^ ~(B | A) -> ~(A ^ B)
4017 // Complexity sorting ensures the not will be on the right side.
4018 if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
4019 match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
4020 (match(Op0, m_And(m_Value(A), m_Value(B))) &&
4022 return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
4023
4024 return nullptr;
4025}
4026
4027Value *InstCombinerImpl::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
4028 BinaryOperator &I) {
4029 assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
4030 I.getOperand(1) == RHS && "Should be 'xor' with these operands");
4031
4032 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
4033 Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
4034 Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1);
4035
4036 if (predicatesFoldable(PredL, PredR)) {
4037 if (LHS0 == RHS1 && LHS1 == RHS0) {
4038 std::swap(LHS0, LHS1);
4039 PredL = ICmpInst::getSwappedPredicate(PredL);
4040 }
4041 if (LHS0 == RHS0 && LHS1 == RHS1) {
4042 // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
4043 unsigned Code = getICmpCode(PredL) ^ getICmpCode(PredR);
4044 bool IsSigned = LHS->isSigned() || RHS->isSigned();
4045 return getNewICmpValue(Code, IsSigned, LHS0, LHS1, Builder);
4046 }
4047 }
4048
4049 // TODO: This can be generalized to compares of non-signbits using
4050 // decomposeBitTestICmp(). It could be enhanced more by using (something like)
4051 // foldLogOpOfMaskedICmps().
4052 const APInt *LC, *RC;
4053 if (match(LHS1, m_APInt(LC)) && match(RHS1, m_APInt(RC)) &&
4054 LHS0->getType() == RHS0->getType() &&
4055 LHS0->getType()->isIntOrIntVectorTy()) {
4056 // Convert xor of signbit tests to signbit test of xor'd values:
4057 // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0
4058 // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0
4059 // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1
4060 // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1
4061 bool TrueIfSignedL, TrueIfSignedR;
4062 if ((LHS->hasOneUse() || RHS->hasOneUse()) &&
4063 isSignBitCheck(PredL, *LC, TrueIfSignedL) &&
4064 isSignBitCheck(PredR, *RC, TrueIfSignedR)) {
4065 Value *XorLR = Builder.CreateXor(LHS0, RHS0);
4066 return TrueIfSignedL == TrueIfSignedR ? Builder.CreateIsNeg(XorLR) :
4067 Builder.CreateIsNotNeg(XorLR);
4068 }
4069
4070 // Fold (icmp pred1 X, C1) ^ (icmp pred2 X, C2)
4071 // into a single comparison using range-based reasoning.
4072 if (LHS0 == RHS0) {
4075 auto CRUnion = CR1.exactUnionWith(CR2);
4076 auto CRIntersect = CR1.exactIntersectWith(CR2);
4077 if (CRUnion && CRIntersect)
4078 if (auto CR = CRUnion->exactIntersectWith(CRIntersect->inverse())) {
4079 if (CR->isFullSet())
4080 return ConstantInt::getTrue(I.getType());
4081 if (CR->isEmptySet())
4082 return ConstantInt::getFalse(I.getType());
4083
4084 CmpInst::Predicate NewPred;
4085 APInt NewC, Offset;
4086 CR->getEquivalentICmp(NewPred, NewC, Offset);
4087
4088 if ((Offset.isZero() && (LHS->hasOneUse() || RHS->hasOneUse())) ||
4089 (LHS->hasOneUse() && RHS->hasOneUse())) {
4090 Value *NewV = LHS0;
4091 Type *Ty = LHS0->getType();
4092 if (!Offset.isZero())
4093 NewV = Builder.CreateAdd(NewV, ConstantInt::get(Ty, Offset));
4094 return Builder.CreateICmp(NewPred, NewV,
4095 ConstantInt::get(Ty, NewC));
4096 }
4097 }
4098 }
4099 }
4100
4101 // Instead of trying to imitate the folds for and/or, decompose this 'xor'
4102 // into those logic ops. That is, try to turn this into an and-of-icmps
4103 // because we have many folds for that pattern.
4104 //
4105 // This is based on a truth table definition of xor:
4106 // X ^ Y --> (X | Y) & !(X & Y)
4107 if (Value *OrICmp = simplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
4108 // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
4109 // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
4110 if (Value *AndICmp = simplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
4111 // TODO: Independently handle cases where the 'and' side is a constant.
4112 ICmpInst *X = nullptr, *Y = nullptr;
4113 if (OrICmp == LHS && AndICmp == RHS) {
4114 // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS --> X & !Y
4115 X = LHS;
4116 Y = RHS;
4117 }
4118 if (OrICmp == RHS && AndICmp == LHS) {
4119 // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS --> !Y & X
4120 X = RHS;
4121 Y = LHS;
4122 }
4123 if (X && Y && (Y->hasOneUse() || canFreelyInvertAllUsersOf(Y, &I))) {
4124 // Invert the predicate of 'Y', thus inverting its output.
4125 Y->setPredicate(Y->getInversePredicate());
4126 // So, are there other uses of Y?
4127 if (!Y->hasOneUse()) {
4128 // We need to adapt other uses of Y though. Get a value that matches
4129 // the original value of Y before inversion. While this increases
4130 // immediate instruction count, we have just ensured that all the
4131 // users are freely-invertible, so that 'not' *will* get folded away.
4133 // Set insertion point to right after the Y.
4134 Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
4135 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
4136 // Replace all uses of Y (excluding the one in NotY!) with NotY.
4138 Y->replaceUsesWithIf(NotY,
4139 [NotY](Use &U) { return U.getUser() != NotY; });
4140 }
4141 // All done.
4142 return Builder.CreateAnd(LHS, RHS);
4143 }
4144 }
4145 }
4146
4147 return nullptr;
4148}
4149
4150/// If we have a masked merge, in the canonical form of:
4151/// (assuming that A only has one use.)
4152/// | A | |B|
4153/// ((x ^ y) & M) ^ y
4154/// | D |
4155/// * If M is inverted:
4156/// | D |
4157/// ((x ^ y) & ~M) ^ y
4158/// We can canonicalize by swapping the final xor operand
4159/// to eliminate the 'not' of the mask.
4160/// ((x ^ y) & M) ^ x
4161/// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops
4162/// because that shortens the dependency chain and improves analysis:
4163/// (x & M) | (y & ~M)
4165 InstCombiner::BuilderTy &Builder) {
4166 Value *B, *X, *D;
4167 Value *M;
4168 if (!match(&I, m_c_Xor(m_Value(B),
4171 m_Value(D)),
4172 m_Value(M))))))
4173 return nullptr;
4174
4175 Value *NotM;
4176 if (match(M, m_Not(m_Value(NotM)))) {
4177 // De-invert the mask and swap the value in B part.
4178 Value *NewA = Builder.CreateAnd(D, NotM);
4179 return BinaryOperator::CreateXor(NewA, X);
4180 }
4181
4182 Constant *C;
4183 if (D->hasOneUse() && match(M, m_Constant(C))) {
4184 // Propagating undef is unsafe. Clamp undef elements to -1.
4185 Type *EltTy = C->getType()->getScalarType();
4187 // Unfold.
4188 Value *LHS = Builder.CreateAnd(X, C);
4189 Value *NotC = Builder.CreateNot(C);
4190 Value *RHS = Builder.CreateAnd(B, NotC);
4191 return BinaryOperator::CreateOr(LHS, RHS);
4192 }
4193
4194 return nullptr;
4195}
4196
4198 InstCombiner::BuilderTy &Builder) {
4199 Value *X, *Y;
4200 // FIXME: one-use check is not needed in general, but currently we are unable
4201 // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182)
4202 if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y))))))
4203 return nullptr;
4204
4205 auto hasCommonOperand = [](Value *A, Value *B, Value *C, Value *D) {
4206 return A == C || A == D || B == C || B == D;
4207 };
4208
4209 Value *A, *B, *C, *D;
4210 // Canonicalize ~((A & B) ^ (A | ?)) -> (A & B) | ~(A | ?)
4211 // 4 commuted variants
4212 if (match(X, m_And(m_Value(A), m_Value(B))) &&
4213 match(Y, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) {
4214 Value *NotY = Builder.CreateNot(Y);
4215 return BinaryOperator::CreateOr(X, NotY);
4216 };
4217
4218 // Canonicalize ~((A | ?) ^ (A & B)) -> (A & B) | ~(A | ?)
4219 // 4 commuted variants
4220 if (match(Y, m_And(m_Value(A), m_Value(B))) &&
4221 match(X, m_Or(m_Value(C), m_Value(D))) && hasCommonOperand(A, B, C, D)) {
4222 Value *NotX = Builder.CreateNot(X);
4223 return BinaryOperator::CreateOr(Y, NotX);
4224 };
4225
4226 return nullptr;
4227}
4228
4229/// Canonicalize a shifty way to code absolute value to the more common pattern
4230/// that uses negation and select.
4232 InstCombiner::BuilderTy &Builder) {
4233 assert(Xor.getOpcode() == Instruction::Xor && "Expected an xor instruction.");
4234
4235 // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
4236 // We're relying on the fact that we only do this transform when the shift has
4237 // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
4238 // instructions).
4239 Value *Op0 = Xor.getOperand(0), *Op1 = Xor.getOperand(1);
4240 if (Op0->hasNUses(2))
4241 std::swap(Op0, Op1);
4242
4243 Type *Ty = Xor.getType();
4244 Value *A;
4245 const APInt *ShAmt;
4246 if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&
4247 Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 &&
4248 match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) {
4249 // Op1 = ashr i32 A, 31 ; smear the sign bit
4250 // xor (add A, Op1), Op1 ; add -1 and flip bits if negative
4251 // --> (A < 0) ? -A : A
4252 Value *IsNeg = Builder.CreateIsNeg(A);
4253 // Copy the nuw/nsw flags from the add to the negate.
4254 auto *Add = cast<BinaryOperator>(Op0);
4255 Value *NegA = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(),
4256 Add->hasNoSignedWrap());
4257 return SelectInst::Create(IsNeg, NegA, A);
4258 }
4259 return nullptr;
4260}
4261
4263 Instruction *IgnoredUser) {
4264 auto *I = dyn_cast<Instruction>(Op);
4265 return I && IC.isFreeToInvert(I, /*WillInvertAllUses=*/true) &&
4266 IC.canFreelyInvertAllUsersOf(I, IgnoredUser);
4267}
4268
4270 Instruction *IgnoredUser) {
4271 auto *I = cast<Instruction>(Op);
4272 IC.Builder.SetInsertPoint(*I->getInsertionPointAfterDef());
4273 Value *NotOp = IC.Builder.CreateNot(Op, Op->getName() + ".not");
4274 Op->replaceUsesWithIf(NotOp,
4275 [NotOp](Use &U) { return U.getUser() != NotOp; });
4276 IC.freelyInvertAllUsersOf(NotOp, IgnoredUser);
4277 return NotOp;
4278}
4279
4280// Transform
4281// z = ~(x &/| y)
4282// into:
4283// z = ((~x) |/& (~y))
4284// iff both x and y are free to invert and all uses of z can be freely updated.
4286 Value *Op0, *Op1;
4287 if (!match(&I, m_LogicalOp(m_Value(Op0), m_Value(Op1))))
4288 return false;
4289
4290 // If this logic op has not been simplified yet, just bail out and let that
4291 // happen first. Otherwise, the code below may wrongly invert.
4292 if (Op0 == Op1)
4293 return false;
4294
4295 Instruction::BinaryOps NewOpc =
4296 match(&I, m_LogicalAnd()) ? Instruction::Or : Instruction::And;
4297 bool IsBinaryOp = isa<BinaryOperator>(I);
4298
4299 // Can our users be adapted?
4300 if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
4301 return false;
4302
4303 // And can the operands be adapted?
4304 if (!canFreelyInvert(*this, Op0, &I) || !canFreelyInvert(*this, Op1, &I))
4305 return false;
4306
4307 Op0 = freelyInvert(*this, Op0, &I);
4308 Op1 = freelyInvert(*this, Op1, &I);
4309
4310 Builder.SetInsertPoint(*I.getInsertionPointAfterDef());
4311 Value *NewLogicOp;
4312 if (IsBinaryOp)
4313 NewLogicOp = Builder.CreateBinOp(NewOpc, Op0, Op1, I.getName() + ".not");
4314 else
4315 NewLogicOp =
4316 Builder.CreateLogicalOp(NewOpc, Op0, Op1, I.getName() + ".not");
4317
4318 replaceInstUsesWith(I, NewLogicOp);
4319 // We can not just create an outer `not`, it will most likely be immediately
4320 // folded back, reconstructing our initial pattern, and causing an
4321 // infinite combine loop, so immediately manually fold it away.
4322 freelyInvertAllUsersOf(NewLogicOp);
4323 return true;
4324}
4325
4326// Transform
4327// z = (~x) &/| y
4328// into:
4329// z = ~(x |/& (~y))
4330// iff y is free to invert and all uses of z can be freely updated.
4332 Value *Op0, *Op1;
4333 if (!match(&I, m_LogicalOp(m_Value(Op0), m_Value(Op1))))
4334 return false;
4335 Instruction::BinaryOps NewOpc =
4336 match(&I, m_LogicalAnd()) ? Instruction::Or : Instruction::And;
4337 bool IsBinaryOp = isa<BinaryOperator>(I);
4338
4339 Value *NotOp0 = nullptr;
4340 Value *NotOp1 = nullptr;
4341 Value **OpToInvert = nullptr;
4342 if (match(Op0, m_Not(m_Value(NotOp0))) && canFreelyInvert(*this, Op1, &I)) {
4343 Op0 = NotOp0;
4344 OpToInvert = &Op1;
4345 } else if (match(Op1, m_Not(m_Value(NotOp1))) &&
4346 canFreelyInvert(*this, Op0, &I)) {
4347 Op1 = NotOp1;
4348 OpToInvert = &Op0;
4349 } else
4350 return false;
4351
4352 // And can our users be adapted?
4353 if (!InstCombiner::canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr))
4354 return false;
4355
4356 *OpToInvert = freelyInvert(*this, *OpToInvert, &I);
4357
4358 Builder.SetInsertPoint(*I.getInsertionPointAfterDef());
4359 Value *NewBinOp;
4360 if (IsBinaryOp)
4361 NewBinOp = Builder.CreateBinOp(NewOpc, Op0, Op1, I.getName() + ".not");
4362 else
4363 NewBinOp = Builder.CreateLogicalOp(NewOpc, Op0, Op1, I.getName() + ".not");
4364 replaceInstUsesWith(I, NewBinOp);
4365 // We can not just create an outer `not`, it will most likely be immediately
4366 // folded back, reconstructing our initial pattern, and causing an
4367 // infinite combine loop, so immediately manually fold it away.
4368 freelyInvertAllUsersOf(NewBinOp);
4369 return true;
4370}
4371
4372Instruction *InstCombinerImpl::foldNot(BinaryOperator &I) {
4373 Value *NotOp;
4374 if (!match(&I, m_Not(m_Value(NotOp))))
4375 return nullptr;
4376
4377 // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand.
4378 // We must eliminate the and/or (one-use) for these transforms to not increase
4379 // the instruction count.
4380 //
4381 // ~(~X & Y) --> (X | ~Y)
4382 // ~(Y & ~X) --> (X | ~Y)
4383 //
4384 // Note: The logical matches do not check for the commuted patterns because
4385 // those are handled via SimplifySelectsFeedingBinaryOp().
4386 Type *Ty = I.getType();
4387 Value *X, *Y;
4388 if (match(NotOp, m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y))))) {
4389 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
4390 return BinaryOperator::CreateOr(X, NotY);
4391 }
4392 if (match(NotOp, m_OneUse(m_LogicalAnd(m_Not(m_Value(X)), m_Value(Y))))) {
4393 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
4394 return SelectInst::Create(X, ConstantInt::getTrue(Ty), NotY);
4395 }
4396
4397 // ~(~X | Y) --> (X & ~Y)
4398 // ~(Y | ~X) --> (X & ~Y)
4399 if (match(NotOp, m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y))))) {
4400 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
4401 return BinaryOperator::CreateAnd(X, NotY);
4402 }
4403 if (match(NotOp, m_OneUse(m_LogicalOr(m_Not(m_Value(X)), m_Value(Y))))) {
4404 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
4405 return SelectInst::Create(X, NotY, ConstantInt::getFalse(Ty));
4406 }
4407
4408 // Is this a 'not' (~) fed by a binary operator?
4409 BinaryOperator *NotVal;
4410 if (match(NotOp, m_BinOp(NotVal))) {
4411 // ~((-X) | Y) --> (X - 1) & (~Y)
4412 if (match(NotVal,
4415 Value *NotY = Builder.CreateNot(Y);
4416 return BinaryOperator::CreateAnd(DecX, NotY);
4417 }
4418
4419 // ~(~X >>s Y) --> (X >>s Y)
4420 if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y))))
4421 return BinaryOperator::CreateAShr(X, Y);
4422
4423 // Treat lshr with non-negative operand as ashr.
4424 // ~(~X >>u Y) --> (X >>s Y) iff X is known negative
4425 if (match(NotVal, m_LShr(m_Not(m_Value(X)), m_Value(Y))) &&
4427 return BinaryOperator::CreateAShr(X, Y);
4428
4429 // Bit-hack form of a signbit test for iN type:
4430 // ~(X >>s (N - 1)) --> sext i1 (X > -1) to iN
4431 unsigned FullShift = Ty->getScalarSizeInBits() - 1;
4432 if (match(NotVal, m_OneUse(m_AShr(m_Value(X), m_SpecificInt(FullShift))))) {
4433 Value *IsNotNeg = Builder.CreateIsNotNeg(X, "isnotneg");
4434 return new SExtInst(IsNotNeg, Ty);
4435 }
4436
4437 // If we are inverting a right-shifted constant, we may be able to eliminate
4438 // the 'not' by inverting the constant and using the opposite shift type.
4439 // Canonicalization rules ensure that only a negative constant uses 'ashr',
4440 // but we must check that in case that transform has not fired yet.
4441
4442 // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits)
4443 Constant *C;
4444 if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) &&
4445 match(C, m_Negative())) {
4446 // We matched a negative constant, so propagating undef is unsafe.
4447 // Clamp undef elements to -1.
4448 Type *EltTy = Ty->getScalarType();
4450 return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y);
4451 }
4452
4453 // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits)
4454 if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) &&
4455 match(C, m_NonNegative())) {
4456 // We matched a non-negative constant, so propagating undef is unsafe.
4457 // Clamp undef elements to 0.
4458 Type *EltTy = Ty->getScalarType();
4460 return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y);
4461 }
4462
4463 // ~(X + C) --> ~C - X
4464 if (match(NotVal, m_Add(m_Value(X), m_ImmConstant(C))))
4465 return BinaryOperator::CreateSub(ConstantExpr::getNot(C), X);
4466
4467 // ~(X - Y) --> ~X + Y
4468 // FIXME: is it really beneficial to sink the `not` here?
4469 if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
4470 if (isa<Constant>(X) || NotVal->hasOneUse())
4471 return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);
4472
4473 // ~(~X + Y) --> X - Y
4474 if (match(NotVal, m_c_Add(m_Not(m_Value(X)), m_Value(Y))))
4475 return BinaryOperator::CreateWithCopiedFlags(Instruction::Sub, X, Y,
4476 NotVal);
4477 }
4478
4479 // not (cmp A, B) = !cmp A, B
4480 CmpInst::Predicate Pred;
4481 if (match(NotOp, m_Cmp(Pred, m_Value(), m_Value())) &&
4482 (NotOp->hasOneUse() ||
4483 InstCombiner::canFreelyInvertAllUsersOf(cast<Instruction>(NotOp),
4484 /*IgnoredUser=*/nullptr))) {
4485 cast<CmpInst>(NotOp)->setPredicate(CmpInst::getInversePredicate(Pred));
4487 return &I;
4488 }
4489
4490 // Move a 'not' ahead of casts of a bool to enable logic reduction:
4491 // not (bitcast (sext i1 X)) --> bitcast (sext (not i1 X))
4492 if (match(NotOp, m_OneUse(m_BitCast(m_OneUse(m_SExt(m_Value(X)))))) && X->getType()->isIntOrIntVectorTy(1)) {
4493 Type *SextTy = cast<BitCastOperator>(NotOp)->getSrcTy();
4494 Value *NotX = Builder.CreateNot(X);
4495 Value *Sext = Builder.CreateSExt(NotX, SextTy);
4496 return CastInst::CreateBitOrPointerCast(Sext, Ty);
4497 }
4498
4499 if (auto *NotOpI = dyn_cast<Instruction>(NotOp))
4500 if (sinkNotIntoLogicalOp(*NotOpI))
4501 return &I;
4502
4503 // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max:
4504 // ~min(~X, ~Y) --> max(X, Y)
4505 // ~max(~X, Y) --> min(X, ~Y)
4506 auto *II = dyn_cast<IntrinsicInst>(NotOp);
4507 if (II && II->hasOneUse()) {
4508 if (match(NotOp, m_c_MaxOrMin(m_Not(m_Value(X)), m_Value(Y)))) {
4509 Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
4510 Value *NotY = Builder.CreateNot(Y);
4511 Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotY);
4512 return replaceInstUsesWith(I, InvMaxMin);
4513 }
4514
4515 if (II->getIntrinsicID() == Intrinsic::is_fpclass) {
4516 ConstantInt *ClassMask = cast<ConstantInt>(II->getArgOperand(1));
4517 II->setArgOperand(
4518 1, ConstantInt::get(ClassMask->getType(),
4519 ~ClassMask->getZExtValue() & fcAllFlags));
4520 return replaceInstUsesWith(I, II);
4521 }
4522 }
4523
4524 if (NotOp->hasOneUse()) {
4525 // Pull 'not' into operands of select if both operands are one-use compares
4526 // or one is one-use compare and the other one is a constant.
4527 // Inverting the predicates eliminates the 'not' operation.
4528 // Example:
4529 // not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
4530 // select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
4531 // not (select ?, (cmp TPred, ?, ?), true -->
4532 // select ?, (cmp InvTPred, ?, ?), false
4533 if (auto *Sel = dyn_cast<SelectInst>(NotOp)) {
4534 Value *TV = Sel->getTrueValue();
4535 Value *FV = Sel->getFalseValue();
4536 auto *CmpT = dyn_cast<CmpInst>(TV);
4537 auto *CmpF = dyn_cast<CmpInst>(FV);
4538 bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
4539 bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
4540 if (InvertibleT && InvertibleF) {
4541 if (CmpT)
4542 CmpT->setPredicate(CmpT->getInversePredicate());
4543 else
4544 Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
4545 if (CmpF)
4546 CmpF->setPredicate(CmpF->getInversePredicate());
4547 else
4548 Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
4549 return replaceInstUsesWith(I, Sel);
4550 }
4551 }
4552 }
4553
4554 if (Instruction *NewXor = foldNotXor(I, Builder))
4555 return NewXor;
4556
4557 // TODO: Could handle multi-use better by checking if all uses of NotOp (other
4558 // than I) can be inverted.
4559 if (Value *R = getFreelyInverted(NotOp, NotOp->hasOneUse(), &Builder))
4560 return replaceInstUsesWith(I, R);
4561
4562 return nullptr;
4563}
4564
4565// FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
4566// here. We should standardize that construct where it is needed or choose some
4567// other way to ensure that commutated variants of patterns are not missed.
4569 if (Value *V = simplifyXorInst(I.getOperand(0), I.getOperand(1),
4571 return replaceInstUsesWith(I, V);
4572
4574 return &I;
4575
4577 return X;
4578
4580 return Phi;
4581
4582 if (Instruction *NewXor = foldXorToXor(I, Builder))
4583 return NewXor;
4584
4585 // (A&B)^(A&C) -> A&(B^C) etc
4587 return replaceInstUsesWith(I, V);
4588
4589 // See if we can simplify any instructions used by the instruction whose sole
4590 // purpose is to compute bits we don't care about.
4592 return &I;
4593
4594 if (Instruction *R = foldNot(I))
4595 return R;
4596
4598 return R;
4599
4600 // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M)
4601 // This it a special case in haveNoCommonBitsSet, but the computeKnownBits
4602 // calls in there are unnecessary as SimplifyDemandedInstructionBits should
4603 // have already taken care of those cases.
4604 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
4605 Value *M;
4606 if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()),
4607 m_c_And(m_Deferred(M), m_Value()))))
4608 return BinaryOperator::CreateDisjointOr(Op0, Op1);
4609
4611 return Xor;
4612
4613 Value *X, *Y;
4614 Constant *C1;
4615 if (match(Op1, m_Constant(C1))) {
4616 Constant *C2;
4617
4618 if (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C2)))) &&
4619 match(C1, m_ImmConstant())) {
4620 // (X | C2) ^ C1 --> (X & ~C2) ^ (C1^C2)
4625 return BinaryOperator::CreateXor(
4627 }
4628
4629 // Use DeMorgan and reassociation to eliminate a 'not' op.
4630 if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) {
4631 // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1
4633 return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1));
4634 }
4635 if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) {
4636 // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1
4638 return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1));
4639 }
4640
4641 // Convert xor ([trunc] (ashr X, BW-1)), C =>
4642 // select(X >s -1, C, ~C)
4643 // The ashr creates "AllZeroOrAllOne's", which then optionally inverses the
4644 // constant depending on whether this input is less than 0.
4645 const APInt *CA;
4646 if (match(Op0, m_OneUse(m_TruncOrSelf(
4647 m_AShr(m_Value(X), m_APIntAllowUndef(CA))))) &&
4648 *CA == X->getType()->getScalarSizeInBits() - 1 &&
4649 !match(C1, m_AllOnes())) {
4650 assert(!C1->isZeroValue() && "Unexpected xor with 0");
4651 Value *IsNotNeg = Builder.CreateIsNotNeg(X);
4652 return SelectInst::Create(IsNotNeg, Op1, Builder.CreateNot(Op1));
4653 }
4654 }
4655
4656 Type *Ty = I.getType();
4657 {
4658 const APInt *RHSC;
4659 if (match(Op1, m_APInt(RHSC))) {
4660 Value *X;
4661 const APInt *C;
4662 // (C - X) ^ signmaskC --> (C + signmaskC) - X
4663 if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X))))
4664 return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C + *RHSC), X);
4665
4666 // (X + C) ^ signmaskC --> X + (C + signmaskC)
4667 if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
4668 return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
4669
4670 // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
4671 if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
4672 MaskedValueIsZero(X, *C, 0, &I))
4673 return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
4674
4675 // When X is a power-of-two or zero and zero input is poison:
4676 // ctlz(i32 X) ^ 31 --> cttz(X)
4677 // cttz(i32 X) ^ 31 --> ctlz(X)
4678 auto *II = dyn_cast<IntrinsicInst>(Op0);
4679 if (II && II->hasOneUse() && *RHSC == Ty->getScalarSizeInBits() - 1) {
4680 Intrinsic::ID IID = II->getIntrinsicID();
4681 if ((IID == Intrinsic::ctlz || IID == Intrinsic::cttz) &&
4682 match(II->getArgOperand(1), m_One()) &&
4683 isKnownToBeAPowerOfTwo(II->getArgOperand(0), /*OrZero */ true)) {
4684 IID = (IID == Intrinsic::ctlz) ? Intrinsic::cttz : Intrinsic::ctlz;
4685 Function *F = Intrinsic::getDeclaration(II->getModule(), IID, Ty);
4686 return CallInst::Create(F, {II->getArgOperand(0), Builder.getTrue()});
4687 }
4688 }
4689
4690 // If RHSC is inverting the remaining bits of shifted X,
4691 // canonicalize to a 'not' before the shift to help SCEV and codegen:
4692 // (X << C) ^ RHSC --> ~X << C
4693 if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
4694 *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).shl(*C)) {
4695 Value *NotX = Builder.CreateNot(X);
4696 return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
4697 }
4698 // (X >>u C) ^ RHSC --> ~X >>u C
4699 if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
4700 *RHSC == APInt::getAllOnes(Ty->getScalarSizeInBits()).lshr(*C)) {
4701 Value *NotX = Builder.CreateNot(X);
4702 return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
4703 }
4704 // TODO: We could handle 'ashr' here as well. That would be matching
4705 // a 'not' op and moving it before the shift. Doing that requires
4706 // preventing the inverse fold in canShiftBinOpWithConstantRHS().
4707 }
4708
4709 // If we are XORing the sign bit of a floating-point value, convert
4710 // this to fneg, then cast back to integer.
4711 //
4712 // This is generous interpretation of noimplicitfloat, this is not a true
4713 // floating-point operation.
4714 //
4715 // Assumes any IEEE-represented type has the sign bit in the high bit.
4716 // TODO: Unify with APInt matcher. This version allows undef unlike m_APInt
4717 Value *CastOp;
4718 if (match(Op0, m_ElementWiseBitCast(m_Value(CastOp))) &&
4719 match(Op1, m_SignMask()) &&
4721 Attribute::NoImplicitFloat)) {
4722 Type *EltTy = CastOp->getType()->getScalarType();
4723 if (EltTy->isFloatingPointTy() && EltTy->isIEEE()) {
4724 Value *FNeg = Builder.CreateFNeg(CastOp);
4725 return new BitCastInst(FNeg, I.getType());
4726 }
4727 }
4728 }
4729
4730 // FIXME: This should not be limited to scalar (pull into APInt match above).
4731 {
4732 Value *X;
4733 ConstantInt *C1, *C2, *C3;
4734 // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
4735 if (match(Op1, m_ConstantInt(C3)) &&
4737 m_ConstantInt(C2))) &&
4738 Op0->hasOneUse()) {
4739 // fold (C1 >> C2) ^ C3
4740 APInt FoldConst = C1->getValue().lshr(C2->getValue());
4741 FoldConst ^= C3->getValue();
4742 // Prepare the two operands.
4743 auto *Opnd0 = Builder.CreateLShr(X, C2);
4744 Opnd0->takeName(Op0);
4745 return BinaryOperator::CreateXor(Opnd0, ConstantInt::get(Ty, FoldConst));
4746 }
4747 }
4748
4749 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
4750 return FoldedLogic;
4751
4752 // Y ^ (X | Y) --> X & ~Y
4753 // Y ^ (Y | X) --> X & ~Y
4754 if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0)))))
4755 return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0));
4756 // (X | Y) ^ Y --> X & ~Y
4757 // (Y | X) ^ Y --> X & ~Y
4758 if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1)))))
4759 return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1));
4760
4761 // Y ^ (X & Y) --> ~X & Y
4762 // Y ^ (Y & X) --> ~X & Y
4763 if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0)))))
4764 return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X));
4765 // (X & Y) ^ Y --> ~X & Y
4766 // (Y & X) ^ Y --> ~X & Y
4767 // Canonical form is (X & C) ^ C; don't touch that.
4768 // TODO: A 'not' op is better for analysis and codegen, but demanded bits must
4769 // be fixed to prefer that (otherwise we get infinite looping).
4770 if (!match(Op1, m_Constant()) &&
4771 match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1)))))
4772 return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X));
4773
4774 Value *A, *B, *C;
4775 // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants.
4778 return BinaryOperator::CreateXor(
4780
4781 // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants.
4784 return BinaryOperator::CreateXor(
4786
4787 // (A & B) ^ (A ^ B) -> (A | B)
4788 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
4790 return BinaryOperator::CreateOr(A, B);
4791 // (A ^ B) ^ (A & B) -> (A | B)
4792 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
4794 return BinaryOperator::CreateOr(A, B);
4795
4796 // (A & ~B) ^ ~A -> ~(A & B)
4797 // (~B & A) ^ ~A -> ~(A & B)
4798 if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
4799 match(Op1, m_Not(m_Specific(A))))
4801
4802 // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
4804 return BinaryOperator::CreateOr(A, B);
4805
4806 // (~A | B) ^ A --> ~(A & B)
4807 if (match(Op0, m_OneUse(m_c_Or(m_Not(m_Specific(Op1)), m_Value(B)))))
4809
4810 // A ^ (~A | B) --> ~(A & B)
4811 if (match(Op1, m_OneUse(m_c_Or(m_Not(m_Specific(Op0)), m_Value(B)))))
4813
4814 // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
4815 // TODO: Loosen one-use restriction if common operand is a constant.
4816 Value *D;
4817 if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
4818 match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
4819 if (B == C || B == D)
4820 std::swap(A, B);
4821 if (A == C)
4822 std::swap(C, D);
4823 if (A == D) {
4824 Value *NotA = Builder.CreateNot(A);
4825 return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
4826 }
4827 }
4828
4829 // (A & B) ^ (A | C) --> A ? ~B : C -- There are 4 commuted variants.
4830 if (I.getType()->isIntOrIntVectorTy(1) &&
4833 bool NeedFreeze = isa<SelectInst>(Op0) && isa<SelectInst>(Op1) && B == D;
4834 if (B == C || B == D)
4835 std::swap(A, B);
4836 if (A == C)
4837 std::swap(C, D);
4838 if (A == D) {
4839 if (NeedFreeze)
4841 Value *NotB = Builder.CreateNot(B);
4842 return SelectInst::Create(A, NotB, C);
4843 }
4844 }
4845
4846 if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
4847 if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
4848 if (Value *V = foldXorOfICmps(LHS, RHS, I))
4849 return replaceInstUsesWith(I, V);
4850
4851 if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
4852 return CastedXor;
4853
4854 if (Instruction *Abs = canonicalizeAbs(I, Builder))
4855 return Abs;
4856
4857 // Otherwise, if all else failed, try to hoist the xor-by-constant:
4858 // (X ^ C) ^ Y --> (X ^ Y) ^ C
4859 // Just like we do in other places, we completely avoid the fold
4860 // for constantexprs, at least to avoid endless combine loop.
4863 m_ImmConstant(C1))),
4864 m_Value(Y))))
4865 return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
4866
4868 return R;
4869
4870 if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
4871 return Canonicalized;
4872
4873 if (Instruction *Folded = foldLogicOfIsFPClass(I, Op0, Op1))
4874 return Folded;
4875
4876 if (Instruction *Folded = canonicalizeConditionalNegationViaMathToSelect(I))
4877 return Folded;
4878
4879 if (Instruction *Res = foldBinOpOfDisplacedShifts(I))
4880 return Res;
4881
4883 return Res;
4884
4885 return nullptr;
4886}
amdgpu AMDGPU Register Bank Select
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
static unsigned conjugateICmpMask(unsigned Mask)
Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite s...
static Instruction * foldNotXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static bool matchIsFPClassLikeFCmp(Value *Op, Value *&ClassVal, uint64_t &ClassMask)
Match an fcmp against a special value that performs a test possible by llvm.is.fpclass.
static Value * foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, Instruction &CxtI, InstCombiner::BuilderTy &Builder)
General pattern: X & Y.
static Instruction * visitMaskedMerge(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have a masked merge, in the canonical form of: (assuming that A only has one use....
static Instruction * canonicalizeAbs(BinaryOperator &Xor, InstCombiner::BuilderTy &Builder)
Canonicalize a shifty way to code absolute value to the more common pattern that uses negation and se...
static Value * foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp, ICmpInst *UnsignedICmp, bool IsAnd, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
Commuted variants are assumed to be handled by calling this function again with the parameters swappe...
static Instruction * foldOrToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Value * simplifyAndOrWithOpReplaced(Value *V, Value *Op, Value *RepOp, bool SimplifyOnly, InstCombinerImpl &IC, unsigned Depth=0)
static Instruction * matchDeMorgansLaws(BinaryOperator &I, InstCombiner &IC)
Match variations of De Morgan's Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B))
static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
static Value * foldIsPowerOf2OrZero(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd, InstCombiner::BuilderTy &Builder)
Fold (icmp eq ctpop(X) 1) | (icmp eq X 0) into (icmp ult ctpop(X) 2) and fold (icmp ne ctpop(X) 1) & ...
static Instruction * foldAndToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static unsigned getMaskedICmpType(Value *A, Value *B, Value *C, ICmpInst::Predicate Pred)
Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C) satisfies.
static Instruction * foldXorToXor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
A ^ B can be specified using other logic ops in a variety of patterns.
static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth)
Return true if a constant shift amount is always less than the specified bit-width.
static Instruction * foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, InstCombinerImpl &IC)
Fold {and,or,xor} (cast X), C.
static Value * foldAndOrOfICmpEqConstantAndICmp(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, bool IsLogical, IRBuilderBase &Builder)
static bool canFreelyInvert(InstCombiner &IC, Value *Op, Instruction *IgnoredUser)
static Value * foldNegativePower2AndShiftedMask(Value *A, Value *B, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) == 0) & (icmp(A & D) != E) into (icmp A u< D) iff B is a contiguous set of o...
static Value * matchIsFiniteTest(InstCombiner::BuilderTy &Builder, FCmpInst *LHS, FCmpInst *RHS)
and (fcmp ord x, 0), (fcmp u* x, inf) -> fcmp o* x, inf
static Value * foldPowerOf2AndShiftedMask(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
Try to fold ((icmp X u< P) & (icmp(X & M) != M)) or ((icmp X s> -1) & (icmp(X & M) !...
static Value * stripSignOnlyFPOps(Value *Val)
Ignore all operations which only change the sign of a value, returning the underlying magnitude value...
static Value * freelyInvert(InstCombinerImpl &IC, Value *Op, Instruction *IgnoredUser)
static Value * foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, bool IsLogical, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
static Value * foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
Reduce a pair of compares that check if a value has exactly 1 bit set.
static Value * foldLogOpOfMaskedICmpsAsymmetric(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C, Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, unsigned LHSMask, unsigned RHSMask, InstCombiner::BuilderTy &Builder)
Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!...
static std::optional< IntPart > matchIntPart(Value *V)
Match an extraction of bits from an integer.
static Instruction * canonicalizeLogicFirst(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Instruction * reassociateFCmps(BinaryOperator &BO, InstCombiner::BuilderTy &Builder)
This a limited reassociation for a special case (see above) where we are checking if two values are e...
static Value * getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
static std::optional< std::pair< unsigned, unsigned > > getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR)
Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
static Value * extractIntPart(const IntPart &P, IRBuilderBase &Builder)
Materialize an extraction of bits from an integer in IR.
static bool matchUnorderedInfCompare(FCmpInst::Predicate P, Value *LHS, Value *RHS)
Matches fcmp u__ x, +/-inf.
static Instruction * matchOrConcat(Instruction &Or, InstCombiner::BuilderTy &Builder)
Attempt to combine or(zext(x),shl(zext(y),bw/2) concat packing patterns.
static bool matchIsNotNaN(FCmpInst::Predicate P, Value *LHS, Value *RHS)
Matches canonical form of isnan, fcmp ord x, 0.
static bool areInverseVectorBitmasks(Constant *C1, Constant *C2)
If all elements of two constant vectors are 0/-1 and inverses, return true.
MaskedICmpType
Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified.
@ BMask_NotMixed
@ AMask_NotMixed
@ BMask_NotAllOnes
@ Mask_AllZeros
@ BMask_AllOnes
@ AMask_NotAllOnes
@ AMask_AllOnes
@ Mask_NotAllZeros
static Instruction * foldComplexAndOrPatterns(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Try folding relatively complex patterns for both And and Or operations with all And and Or swapped.
static Value * getFCmpValue(unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp inst...
static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)
Match UB-safe variants of the funnel shift intrinsic.
static Instruction * reassociateForUses(BinaryOperator &BO, InstCombinerImpl::BuilderTy &Builder)
Try to reassociate a pair of binops so that values with one use only are part of the same instruction...
static Instruction * foldBitwiseLogicWithIntrinsics(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Value * foldAndOrOfICmpsWithConstEq(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd, bool IsLogical, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q)
Reduce logic-of-compares with equality to a constant by substituting a common operand with the consta...
This file provides internal interfaces used to implement the InstCombine.
This file provides the interface for the instcombine pass implementation.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:531
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define R2(n)
uint64_t High
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static unsigned getScalarSizeInBits(Type *Ty)
static constexpr int Concat[]
Value * RHS
Value * LHS
support::ulittle16_t & Lo
Definition: aarch32.cpp:206
support::ulittle16_t & Hi
Definition: aarch32.cpp:205
bool bitwiseIsEqual(const APFloat &RHS) const
Definition: APFloat.h:1260
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:981
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1491
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
unsigned countLeadingOnes() const
Definition: APInt.h:1574
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:349
APInt usub_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1954
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:358
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
Definition: APInt.h:444
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1934
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1227
int32_t exactLogBase2() const
Definition: APInt.h:1725
APInt reverseBits() const
Definition: APInt.cpp:737
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1941
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1589
unsigned countLeadingZeros() const
Definition: APInt.h:1556
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1128
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:851
APInt byteSwap() const
Definition: APInt.cpp:715
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1235
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:418
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1947
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:829
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
Value * getRHS() const
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Value * getLHS() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
Definition: InstrTypes.h:491
static BinaryOperator * CreateNot(Value *Op, const Twine &Name, BasicBlock::iterator InsertBefore)
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, Value *CopyO, const Twine &Name, BasicBlock::iterator InsertBefore)
Definition: InstrTypes.h:297
This class represents a no-op cast from one type to another.
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:579
Type * getSrcTy() const
Return the source type, as a convenience.
Definition: InstrTypes.h:913
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:908
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
Type * getDestTy() const
Return the destination type, as a convenience.
Definition: InstrTypes.h:915
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1323
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:994
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:995
@ FCMP_OLT
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:971
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:980
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:989
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:988
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:992
@ FCMP_ULT
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:979
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:990
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:972
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
Definition: InstrTypes.h:974
@ ICMP_EQ
equal
Definition: InstrTypes.h:986
@ ICMP_NE
not equal
Definition: InstrTypes.h:987
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:993
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:991
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Definition: InstrTypes.h:975
bool isSigned() const
Definition: InstrTypes.h:1226
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1128
Predicate getOrderedPredicate() const
Definition: InstrTypes.h:1101
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:1090
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:1066
static bool isUnordered(Predicate predicate)
Determine if the predicate is an unordered operation.
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2544
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2531
static Constant * getXor(Constant *C1, Constant *C2)
Definition: Constants.cpp:2558
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2537
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2098
static Constant * getExactLogBase2(Constant *C)
If C is a scalar/fixed width vector of known powers of 2, then this function returns a new scalar/fix...
Definition: Constants.cpp:2569
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:2328
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:216
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:204
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:856
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:153
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
This class represents a range of values.
Definition: ConstantRange.h:47
std::optional< ConstantRange > exactUnionWith(const ConstantRange &CR) const
Union the two ranges and return the result if it can be represented exactly, otherwise return std::nu...
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt & getLower() const
Return the lower value for this range.
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
const APInt & getUpper() const
Return the upper value for this range.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
Definition: Constants.cpp:767
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
Definition: Constants.cpp:791
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:417
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:432
bool isZeroValue() const
Return true if the value is negative zero or null value.
Definition: Constants.cpp:76
This class represents an Operation in the Expression.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
This instruction compares its operands according to the predicate given to the constructor.
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:20
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:669
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Definition: IRBuilder.cpp:913
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2240
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2006
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1715
Value * CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS, Value *RHS, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 2 operands which is mangled on the first type.
Definition: IRBuilder.cpp:921
Value * CreateFCmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2344
Value * CreateLogicalOp(Instruction::BinaryOps Opc, Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1682
IntegerType * getIntNTy(unsigned N)
Fetch the type representing an N-bit integer.
Definition: IRBuilder.h:533
Value * CreateICmpSGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2248
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:2028
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:460
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:932
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1110
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2022
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2518
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1431
Value * CreateIsNotNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg > -1.
Definition: IRBuilder.h:2542
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:174
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:305
Value * CreateICmpNE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2228
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:480
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1748
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2224
Value * CreateIsNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg < 0.
Definition: IRBuilder.h:2537
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1338
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2110
Value * CreateICmpUGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2232
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1410
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2010
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1469
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1321
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg != 0.
Definition: IRBuilder.h:2532
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1491
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1660
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1670
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2256
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2144
Value * CreateICmpUGE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2236
Value * CreateIsNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg == 0.
Definition: IRBuilder.h:2527
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2395
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1513
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2334
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1676
Value * CreateFNeg(Value *V, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1729
Instruction * canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(BinaryOperator &I)
Instruction * foldBinOpIntoSelectOrPhi(BinaryOperator &I)
This is a convenience wrapper function for the above two functions.
Instruction * visitOr(BinaryOperator &I)
bool SimplifyAssociativeOrCommutative(BinaryOperator &I)
Performs a few simplifications for operators which are associative or commutative.
Value * foldUsingDistributiveLaws(BinaryOperator &I)
Tries to simplify binary operations which some other binary operation distributes over.
Instruction * foldBinOpShiftWithShift(BinaryOperator &I)
Value * insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, bool isSigned, bool Inside)
Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise (V < Lo || V >= Hi).
bool sinkNotIntoLogicalOp(Instruction &I)
std::optional< std::pair< Intrinsic::ID, SmallVector< Value *, 3 > > > convertOrOfShiftsToFunnelShift(Instruction &Or)
Constant * getLosslessUnsignedTrunc(Constant *C, Type *TruncTy)
Instruction * visitAnd(BinaryOperator &I)
bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I)
Instruction * foldBinopWithPhiOperands(BinaryOperator &BO)
For a binary operator with 2 phi operands, try to hoist the binary operation before the phi.
Value * simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted)
Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
Instruction * tryFoldInstWithCtpopWithNot(Instruction *I)
Constant * getLosslessSignedTrunc(Constant *C, Type *TruncTy)
Instruction * visitXor(BinaryOperator &I)
bool SimplifyDemandedInstructionBits(Instruction &Inst)
Tries to simplify operands to an integer instruction based on its demanded bits.
Instruction * foldVectorBinop(BinaryOperator &Inst)
Canonicalize the position of binops relative to shufflevector.
Instruction * matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps, bool MatchBitReversals)
Given an initial instruction, check to see if it is the root of a bswap/bitreverse idiom.
void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser=nullptr)
Freely adapt every user of V as-if V was changed to !V.
The core instruction combiner logic.
Definition: InstCombiner.h:47
SimplifyQuery SQ
Definition: InstCombiner.h:76
bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:231
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:440
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:385
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:64
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:451
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Definition: InstCombiner.h:112
bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
Definition: InstCombiner.h:247
DominatorTree & DT
Definition: InstCombiner.h:74
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:430
BuilderTy & Builder
Definition: InstCombiner.h:60
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:446
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
Definition: InstCombiner.h:212
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:341
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
void push(Instruction *I)
Push the instruction onto the worklist stack.
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: Instruction.cpp:88
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:251
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This class represents a sign extension of integer types.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr, BasicBlock::iterator InsertBefore, Instruction *MDFrom=nullptr)
bool empty() const
Definition: SmallVector.h:94
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIEEE() const
Return whether the type is IEEE compatible, as defined by the eponymous method in APFloat.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition: Type.h:185
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:348
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
iterator_range< user_iterator > users()
Definition: Value.h:421
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
Definition: Value.cpp:153
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:149
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:676
Represents an op.with.overflow intrinsic.
This class represents zero extension of integer types.
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:168
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2188
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1451
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:477
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
Definition: PatternMatch.h:622
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:903
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:499
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:100
apfloat_match m_APFloatAllowUndef(const APFloat *&Res)
Match APFloat while allowing undefs in splat vector constants.
Definition: PatternMatch.h:317
cst_pred_ty< is_sign_mask > m_SignMask()
Match an integer or vector with only the sign bit(s) set.
Definition: PatternMatch.h:613
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
cstfp_pred_ty< is_inf > m_Inf()
Match a positive or negative infinity FP constant.
Definition: PatternMatch.h:675
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:300
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:568
auto m_LogicalOp()
Matches either L && R or L || R where L and R are arbitrary values.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:160
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
cst_pred_ty< is_shifted_mask > m_ShiftedMask()
Definition: PatternMatch.h:468
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:765
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:713
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:821
constantexpr_match m_ConstantExpr()
Match a constant expression or a constant that contains a constant expression.
Definition: PatternMatch.h:181
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
Definition: PatternMatch.h:509
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:163
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:541
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
match_combine_or< CastInst_match< OpTy, SExtInst >, OpTy > m_SExtOrSelf(const OpTy &Op)
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:240
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
CastOperator_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
Definition: PatternMatch.h:771
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:839
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:548
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:800
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:105
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
Definition: PatternMatch.h:576
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
DisjointOr_match< LHS, RHS, true > m_c_DisjointOr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty, true > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty, true >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty, true > > > m_c_MaxOrMin(const LHS &L, const RHS &R)
match_combine_or< CastOperator_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)
Match either "sext" or "zext nneg".
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:911
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:294
cst_pred_ty< is_maxsignedvalue > m_MaxSignedValue()
Match an integer or vector with values having all bits except for the high bit set (0x7f....
Definition: PatternMatch.h:487
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:722
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:561
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ElementWiseBitCast_match< OpTy > m_ElementWiseBitCast(const OpTy &Op)
m_Intrinsic_Ty< Opnd0 >::Ty m_FAbs(const Opnd0 &Op0)
m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_CopySign(const Opnd0 &Op0, const Opnd1 &Op1)
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
Definition: PatternMatch.h:198
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:234
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:647
NodeAddr< CodeNode * > Code
Definition: RDFGraph.h:388
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
@ Offset
Definition: DWP.cpp:456
Constant * getPredForFCmpCode(unsigned Code, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getFCmpCode.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
bool predicatesFoldable(CmpInst::Predicate P1, CmpInst::Predicate P2)
Return true if both predicates match sign or if at least one of them is an equality comparison (which...
Value * simplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Or, fold the result or return null.
Value * simplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3919
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:264
Value * simplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
Value * simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
@ Other
Any other memory.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
bool isKnownNegative(const Value *V, const SimplifyQuery &DL, unsigned Depth=0)
Returns true if the given value is known be negative (i.e.
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
@ Add
Sum of integers.
DWARFExpression::Operation Op
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
std::pair< Value *, FPClassTest > fcmpToClassTest(CmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
APFloat neg(APFloat X)
Returns the negated value of the argument.
Definition: APFloat.h:1387
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
unsigned getICmpCode(CmpInst::Predicate Pred)
Encode a icmp predicate into a three bit mask.
unsigned getFCmpCode(CmpInst::Predicate CC)
Similar to getICmpCode but for FCmpInst.
Constant * getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getICmpCode.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:104
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:141
const DataLayout & DL
Definition: SimplifyQuery.h:61
const Instruction * CxtI
Definition: SimplifyQuery.h:65
const DominatorTree * DT
Definition: SimplifyQuery.h:63
SimplifyQuery getWithInstruction(const Instruction *I) const
Definition: SimplifyQuery.h:96
AssumptionCache * AC
Definition: SimplifyQuery.h:64