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