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