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/Transforms/Utils/Local.h" 17 #include "llvm/IR/ConstantRange.h" 18 #include "llvm/IR/Intrinsics.h" 19 #include "llvm/IR/PatternMatch.h" 20 using namespace llvm; 21 using namespace PatternMatch; 22 23 #define DEBUG_TYPE "instcombine" 24 25 /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into 26 /// a four bit mask. 27 static unsigned getFCmpCode(FCmpInst::Predicate CC) { 28 assert(FCmpInst::FCMP_FALSE <= CC && CC <= FCmpInst::FCMP_TRUE && 29 "Unexpected FCmp predicate!"); 30 // Take advantage of the bit pattern of FCmpInst::Predicate here. 31 // U L G E 32 static_assert(FCmpInst::FCMP_FALSE == 0, ""); // 0 0 0 0 33 static_assert(FCmpInst::FCMP_OEQ == 1, ""); // 0 0 0 1 34 static_assert(FCmpInst::FCMP_OGT == 2, ""); // 0 0 1 0 35 static_assert(FCmpInst::FCMP_OGE == 3, ""); // 0 0 1 1 36 static_assert(FCmpInst::FCMP_OLT == 4, ""); // 0 1 0 0 37 static_assert(FCmpInst::FCMP_OLE == 5, ""); // 0 1 0 1 38 static_assert(FCmpInst::FCMP_ONE == 6, ""); // 0 1 1 0 39 static_assert(FCmpInst::FCMP_ORD == 7, ""); // 0 1 1 1 40 static_assert(FCmpInst::FCMP_UNO == 8, ""); // 1 0 0 0 41 static_assert(FCmpInst::FCMP_UEQ == 9, ""); // 1 0 0 1 42 static_assert(FCmpInst::FCMP_UGT == 10, ""); // 1 0 1 0 43 static_assert(FCmpInst::FCMP_UGE == 11, ""); // 1 0 1 1 44 static_assert(FCmpInst::FCMP_ULT == 12, ""); // 1 1 0 0 45 static_assert(FCmpInst::FCMP_ULE == 13, ""); // 1 1 0 1 46 static_assert(FCmpInst::FCMP_UNE == 14, ""); // 1 1 1 0 47 static_assert(FCmpInst::FCMP_TRUE == 15, ""); // 1 1 1 1 48 return CC; 49 } 50 51 /// This is the complement of getICmpCode, which turns an opcode and two 52 /// operands into either a constant true or false, or a brand new ICmp 53 /// instruction. The sign is passed in to determine which kind of predicate to 54 /// use in the new icmp instruction. 55 static Value *getNewICmpValue(unsigned Code, bool Sign, Value *LHS, Value *RHS, 56 InstCombiner::BuilderTy &Builder) { 57 ICmpInst::Predicate NewPred; 58 if (Constant *TorF = getPredForICmpCode(Code, Sign, LHS->getType(), NewPred)) 59 return TorF; 60 return Builder.CreateICmp(NewPred, LHS, RHS); 61 } 62 63 /// This is the complement of getFCmpCode, which turns an opcode and two 64 /// operands into either a FCmp instruction, or a true/false constant. 65 static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS, 66 InstCombiner::BuilderTy &Builder) { 67 const auto Pred = static_cast<FCmpInst::Predicate>(Code); 68 assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE && 69 "Unexpected FCmp predicate!"); 70 if (Pred == FCmpInst::FCMP_FALSE) 71 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 72 if (Pred == FCmpInst::FCMP_TRUE) 73 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 74 return Builder.CreateFCmp(Pred, LHS, RHS); 75 } 76 77 /// Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or 78 /// BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B)) 79 /// \param I Binary operator to transform. 80 /// \return Pointer to node that must replace the original binary operator, or 81 /// null pointer if no transformation was made. 82 static Value *SimplifyBSwap(BinaryOperator &I, 83 InstCombiner::BuilderTy &Builder) { 84 assert(I.isBitwiseLogicOp() && "Unexpected opcode for bswap simplifying"); 85 86 Value *OldLHS = I.getOperand(0); 87 Value *OldRHS = I.getOperand(1); 88 89 Value *NewLHS; 90 if (!match(OldLHS, m_BSwap(m_Value(NewLHS)))) 91 return nullptr; 92 93 Value *NewRHS; 94 const APInt *C; 95 96 if (match(OldRHS, m_BSwap(m_Value(NewRHS)))) { 97 // OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) ) 98 if (!OldLHS->hasOneUse() && !OldRHS->hasOneUse()) 99 return nullptr; 100 // NewRHS initialized by the matcher. 101 } else if (match(OldRHS, m_APInt(C))) { 102 // OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) ) 103 if (!OldLHS->hasOneUse()) 104 return nullptr; 105 NewRHS = ConstantInt::get(I.getType(), C->byteSwap()); 106 } else 107 return nullptr; 108 109 Value *BinOp = Builder.CreateBinOp(I.getOpcode(), NewLHS, NewRHS); 110 Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap, 111 I.getType()); 112 return Builder.CreateCall(F, BinOp); 113 } 114 115 /// This handles expressions of the form ((val OP C1) & C2). Where 116 /// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. 117 Instruction *InstCombiner::OptAndOp(BinaryOperator *Op, 118 ConstantInt *OpRHS, 119 ConstantInt *AndRHS, 120 BinaryOperator &TheAnd) { 121 Value *X = Op->getOperand(0); 122 123 switch (Op->getOpcode()) { 124 default: break; 125 case Instruction::Add: 126 if (Op->hasOneUse()) { 127 // Adding a one to a single bit bit-field should be turned into an XOR 128 // of the bit. First thing to check is to see if this AND is with a 129 // single bit constant. 130 const APInt &AndRHSV = AndRHS->getValue(); 131 132 // If there is only one bit set. 133 if (AndRHSV.isPowerOf2()) { 134 // Ok, at this point, we know that we are masking the result of the 135 // ADD down to exactly one bit. If the constant we are adding has 136 // no bits set below this bit, then we can eliminate the ADD. 137 const APInt& AddRHS = OpRHS->getValue(); 138 139 // Check to see if any bits below the one bit set in AndRHSV are set. 140 if ((AddRHS & (AndRHSV - 1)).isNullValue()) { 141 // If not, the only thing that can effect the output of the AND is 142 // the bit specified by AndRHSV. If that bit is set, the effect of 143 // the XOR is to toggle the bit. If it is clear, then the ADD has 144 // no effect. 145 if ((AddRHS & AndRHSV).isNullValue()) { // Bit is not set, noop 146 TheAnd.setOperand(0, X); 147 return &TheAnd; 148 } else { 149 // Pull the XOR out of the AND. 150 Value *NewAnd = Builder.CreateAnd(X, AndRHS); 151 NewAnd->takeName(Op); 152 return BinaryOperator::CreateXor(NewAnd, AndRHS); 153 } 154 } 155 } 156 } 157 break; 158 } 159 return nullptr; 160 } 161 162 /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise 163 /// (V < Lo || V >= Hi). This method expects that Lo <= Hi. IsSigned indicates 164 /// whether to treat V, Lo, and Hi as signed or not. 165 Value *InstCombiner::insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, 166 bool isSigned, bool Inside) { 167 assert((isSigned ? Lo.sle(Hi) : Lo.ule(Hi)) && 168 "Lo is not <= Hi in range emission code!"); 169 170 Type *Ty = V->getType(); 171 if (Lo == Hi) 172 return Inside ? ConstantInt::getFalse(Ty) : ConstantInt::getTrue(Ty); 173 174 // V >= Min && V < Hi --> V < Hi 175 // V < Min || V >= Hi --> V >= Hi 176 ICmpInst::Predicate Pred = Inside ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE; 177 if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) { 178 Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred; 179 return Builder.CreateICmp(Pred, V, ConstantInt::get(Ty, Hi)); 180 } 181 182 // V >= Lo && V < Hi --> V - Lo u< Hi - Lo 183 // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo 184 Value *VMinusLo = 185 Builder.CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off"); 186 Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo); 187 return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo); 188 } 189 190 /// Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns 191 /// that can be simplified. 192 /// One of A and B is considered the mask. The other is the value. This is 193 /// described as the "AMask" or "BMask" part of the enum. If the enum contains 194 /// only "Mask", then both A and B can be considered masks. If A is the mask, 195 /// then it was proven that (A & C) == C. This is trivial if C == A or C == 0. 196 /// If both A and C are constants, this proof is also easy. 197 /// For the following explanations, we assume that A is the mask. 198 /// 199 /// "AllOnes" declares that the comparison is true only if (A & B) == A or all 200 /// bits of A are set in B. 201 /// Example: (icmp eq (A & 3), 3) -> AMask_AllOnes 202 /// 203 /// "AllZeros" declares that the comparison is true only if (A & B) == 0 or all 204 /// bits of A are cleared in B. 205 /// Example: (icmp eq (A & 3), 0) -> Mask_AllZeroes 206 /// 207 /// "Mixed" declares that (A & B) == C and C might or might not contain any 208 /// number of one bits and zero bits. 209 /// Example: (icmp eq (A & 3), 1) -> AMask_Mixed 210 /// 211 /// "Not" means that in above descriptions "==" should be replaced by "!=". 212 /// Example: (icmp ne (A & 3), 3) -> AMask_NotAllOnes 213 /// 214 /// If the mask A contains a single bit, then the following is equivalent: 215 /// (icmp eq (A & B), A) equals (icmp ne (A & B), 0) 216 /// (icmp ne (A & B), A) equals (icmp eq (A & B), 0) 217 enum MaskedICmpType { 218 AMask_AllOnes = 1, 219 AMask_NotAllOnes = 2, 220 BMask_AllOnes = 4, 221 BMask_NotAllOnes = 8, 222 Mask_AllZeros = 16, 223 Mask_NotAllZeros = 32, 224 AMask_Mixed = 64, 225 AMask_NotMixed = 128, 226 BMask_Mixed = 256, 227 BMask_NotMixed = 512 228 }; 229 230 /// Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C) 231 /// satisfies. 232 static unsigned getMaskedICmpType(Value *A, Value *B, Value *C, 233 ICmpInst::Predicate Pred) { 234 ConstantInt *ACst = dyn_cast<ConstantInt>(A); 235 ConstantInt *BCst = dyn_cast<ConstantInt>(B); 236 ConstantInt *CCst = dyn_cast<ConstantInt>(C); 237 bool IsEq = (Pred == ICmpInst::ICMP_EQ); 238 bool IsAPow2 = (ACst && !ACst->isZero() && ACst->getValue().isPowerOf2()); 239 bool IsBPow2 = (BCst && !BCst->isZero() && BCst->getValue().isPowerOf2()); 240 unsigned MaskVal = 0; 241 if (CCst && CCst->isZero()) { 242 // if C is zero, then both A and B qualify as mask 243 MaskVal |= (IsEq ? (Mask_AllZeros | AMask_Mixed | BMask_Mixed) 244 : (Mask_NotAllZeros | AMask_NotMixed | BMask_NotMixed)); 245 if (IsAPow2) 246 MaskVal |= (IsEq ? (AMask_NotAllOnes | AMask_NotMixed) 247 : (AMask_AllOnes | AMask_Mixed)); 248 if (IsBPow2) 249 MaskVal |= (IsEq ? (BMask_NotAllOnes | BMask_NotMixed) 250 : (BMask_AllOnes | BMask_Mixed)); 251 return MaskVal; 252 } 253 254 if (A == C) { 255 MaskVal |= (IsEq ? (AMask_AllOnes | AMask_Mixed) 256 : (AMask_NotAllOnes | AMask_NotMixed)); 257 if (IsAPow2) 258 MaskVal |= (IsEq ? (Mask_NotAllZeros | AMask_NotMixed) 259 : (Mask_AllZeros | AMask_Mixed)); 260 } else if (ACst && CCst && ConstantExpr::getAnd(ACst, CCst) == CCst) { 261 MaskVal |= (IsEq ? AMask_Mixed : AMask_NotMixed); 262 } 263 264 if (B == C) { 265 MaskVal |= (IsEq ? (BMask_AllOnes | BMask_Mixed) 266 : (BMask_NotAllOnes | BMask_NotMixed)); 267 if (IsBPow2) 268 MaskVal |= (IsEq ? (Mask_NotAllZeros | BMask_NotMixed) 269 : (Mask_AllZeros | BMask_Mixed)); 270 } else if (BCst && CCst && ConstantExpr::getAnd(BCst, CCst) == CCst) { 271 MaskVal |= (IsEq ? BMask_Mixed : BMask_NotMixed); 272 } 273 274 return MaskVal; 275 } 276 277 /// Convert an analysis of a masked ICmp into its equivalent if all boolean 278 /// operations had the opposite sense. Since each "NotXXX" flag (recording !=) 279 /// is adjacent to the corresponding normal flag (recording ==), this just 280 /// involves swapping those bits over. 281 static unsigned conjugateICmpMask(unsigned Mask) { 282 unsigned NewMask; 283 NewMask = (Mask & (AMask_AllOnes | BMask_AllOnes | Mask_AllZeros | 284 AMask_Mixed | BMask_Mixed)) 285 << 1; 286 287 NewMask |= (Mask & (AMask_NotAllOnes | BMask_NotAllOnes | Mask_NotAllZeros | 288 AMask_NotMixed | BMask_NotMixed)) 289 >> 1; 290 291 return NewMask; 292 } 293 294 // Adapts the external decomposeBitTestICmp for local use. 295 static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, 296 Value *&X, Value *&Y, Value *&Z) { 297 APInt Mask; 298 if (!llvm::decomposeBitTestICmp(LHS, RHS, Pred, X, Mask)) 299 return false; 300 301 Y = ConstantInt::get(X->getType(), Mask); 302 Z = ConstantInt::get(X->getType(), 0); 303 return true; 304 } 305 306 /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E). 307 /// Return the pattern classes (from MaskedICmpType) for the left hand side and 308 /// the right hand side as a pair. 309 /// LHS and RHS are the left hand side and the right hand side ICmps and PredL 310 /// and PredR are their predicates, respectively. 311 static 312 Optional<std::pair<unsigned, unsigned>> 313 getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, 314 Value *&D, Value *&E, ICmpInst *LHS, 315 ICmpInst *RHS, 316 ICmpInst::Predicate &PredL, 317 ICmpInst::Predicate &PredR) { 318 // vectors are not (yet?) supported. Don't support pointers either. 319 if (!LHS->getOperand(0)->getType()->isIntegerTy() || 320 !RHS->getOperand(0)->getType()->isIntegerTy()) 321 return None; 322 323 // Here comes the tricky part: 324 // LHS might be of the form L11 & L12 == X, X == L21 & L22, 325 // and L11 & L12 == L21 & L22. The same goes for RHS. 326 // Now we must find those components L** and R**, that are equal, so 327 // that we can extract the parameters A, B, C, D, and E for the canonical 328 // above. 329 Value *L1 = LHS->getOperand(0); 330 Value *L2 = LHS->getOperand(1); 331 Value *L11, *L12, *L21, *L22; 332 // Check whether the icmp can be decomposed into a bit test. 333 if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) { 334 L21 = L22 = L1 = nullptr; 335 } else { 336 // Look for ANDs in the LHS icmp. 337 if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) { 338 // Any icmp can be viewed as being trivially masked; if it allows us to 339 // remove one, it's worth it. 340 L11 = L1; 341 L12 = Constant::getAllOnesValue(L1->getType()); 342 } 343 344 if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) { 345 L21 = L2; 346 L22 = Constant::getAllOnesValue(L2->getType()); 347 } 348 } 349 350 // Bail if LHS was a icmp that can't be decomposed into an equality. 351 if (!ICmpInst::isEquality(PredL)) 352 return None; 353 354 Value *R1 = RHS->getOperand(0); 355 Value *R2 = RHS->getOperand(1); 356 Value *R11, *R12; 357 bool Ok = false; 358 if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) { 359 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 360 A = R11; 361 D = R12; 362 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 363 A = R12; 364 D = R11; 365 } else { 366 return None; 367 } 368 E = R2; 369 R1 = nullptr; 370 Ok = true; 371 } else { 372 if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) { 373 // As before, model no mask as a trivial mask if it'll let us do an 374 // optimization. 375 R11 = R1; 376 R12 = Constant::getAllOnesValue(R1->getType()); 377 } 378 379 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 380 A = R11; 381 D = R12; 382 E = R2; 383 Ok = true; 384 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 385 A = R12; 386 D = R11; 387 E = R2; 388 Ok = true; 389 } 390 } 391 392 // Bail if RHS was a icmp that can't be decomposed into an equality. 393 if (!ICmpInst::isEquality(PredR)) 394 return None; 395 396 // Look for ANDs on the right side of the RHS icmp. 397 if (!Ok) { 398 if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) { 399 R11 = R2; 400 R12 = Constant::getAllOnesValue(R2->getType()); 401 } 402 403 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 404 A = R11; 405 D = R12; 406 E = R1; 407 Ok = true; 408 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 409 A = R12; 410 D = R11; 411 E = R1; 412 Ok = true; 413 } else { 414 return None; 415 } 416 } 417 if (!Ok) 418 return None; 419 420 if (L11 == A) { 421 B = L12; 422 C = L2; 423 } else if (L12 == A) { 424 B = L11; 425 C = L2; 426 } else if (L21 == A) { 427 B = L22; 428 C = L1; 429 } else if (L22 == A) { 430 B = L21; 431 C = L1; 432 } 433 434 unsigned LeftType = getMaskedICmpType(A, B, C, PredL); 435 unsigned RightType = getMaskedICmpType(A, D, E, PredR); 436 return Optional<std::pair<unsigned, unsigned>>(std::make_pair(LeftType, RightType)); 437 } 438 439 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single 440 /// (icmp(A & X) ==/!= Y), where the left-hand side is of type Mask_NotAllZeros 441 /// and the right hand side is of type BMask_Mixed. For example, 442 /// (icmp (A & 12) != 0) & (icmp (A & 15) == 8) -> (icmp (A & 15) == 8). 443 static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( 444 ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, 445 Value *A, Value *B, Value *C, Value *D, Value *E, 446 ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, 447 llvm::InstCombiner::BuilderTy &Builder) { 448 // We are given the canonical form: 449 // (icmp ne (A & B), 0) & (icmp eq (A & D), E). 450 // where D & E == E. 451 // 452 // If IsAnd is false, we get it in negated form: 453 // (icmp eq (A & B), 0) | (icmp ne (A & D), E) -> 454 // !((icmp ne (A & B), 0) & (icmp eq (A & D), E)). 455 // 456 // We currently handle the case of B, C, D, E are constant. 457 // 458 ConstantInt *BCst = dyn_cast<ConstantInt>(B); 459 if (!BCst) 460 return nullptr; 461 ConstantInt *CCst = dyn_cast<ConstantInt>(C); 462 if (!CCst) 463 return nullptr; 464 ConstantInt *DCst = dyn_cast<ConstantInt>(D); 465 if (!DCst) 466 return nullptr; 467 ConstantInt *ECst = dyn_cast<ConstantInt>(E); 468 if (!ECst) 469 return nullptr; 470 471 ICmpInst::Predicate NewCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; 472 473 // Update E to the canonical form when D is a power of two and RHS is 474 // canonicalized as, 475 // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or 476 // (icmp ne (A & D), D) -> (icmp eq (A & D), 0). 477 if (PredR != NewCC) 478 ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst)); 479 480 // If B or D is zero, skip because if LHS or RHS can be trivially folded by 481 // other folding rules and this pattern won't apply any more. 482 if (BCst->getValue() == 0 || DCst->getValue() == 0) 483 return nullptr; 484 485 // If B and D don't intersect, ie. (B & D) == 0, no folding because we can't 486 // deduce anything from it. 487 // For example, 488 // (icmp ne (A & 12), 0) & (icmp eq (A & 3), 1) -> no folding. 489 if ((BCst->getValue() & DCst->getValue()) == 0) 490 return nullptr; 491 492 // If the following two conditions are met: 493 // 494 // 1. mask B covers only a single bit that's not covered by mask D, that is, 495 // (B & (B ^ D)) is a power of 2 (in other words, B minus the intersection of 496 // B and D has only one bit set) and, 497 // 498 // 2. RHS (and E) indicates that the rest of B's bits are zero (in other 499 // words, the intersection of B and D is zero), that is, ((B & D) & E) == 0 500 // 501 // then that single bit in B must be one and thus the whole expression can be 502 // folded to 503 // (A & (B | D)) == (B & (B ^ D)) | E. 504 // 505 // For example, 506 // (icmp ne (A & 12), 0) & (icmp eq (A & 7), 1) -> (icmp eq (A & 15), 9) 507 // (icmp ne (A & 15), 0) & (icmp eq (A & 7), 0) -> (icmp eq (A & 15), 8) 508 if ((((BCst->getValue() & DCst->getValue()) & ECst->getValue()) == 0) && 509 (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())).isPowerOf2()) { 510 APInt BorD = BCst->getValue() | DCst->getValue(); 511 APInt BandBxorDorE = (BCst->getValue() & (BCst->getValue() ^ DCst->getValue())) | 512 ECst->getValue(); 513 Value *NewMask = ConstantInt::get(BCst->getType(), BorD); 514 Value *NewMaskedValue = ConstantInt::get(BCst->getType(), BandBxorDorE); 515 Value *NewAnd = Builder.CreateAnd(A, NewMask); 516 return Builder.CreateICmp(NewCC, NewAnd, NewMaskedValue); 517 } 518 519 auto IsSubSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) { 520 return (C1->getValue() & C2->getValue()) == C1->getValue(); 521 }; 522 auto IsSuperSetOrEqual = [](ConstantInt *C1, ConstantInt *C2) { 523 return (C1->getValue() & C2->getValue()) == C2->getValue(); 524 }; 525 526 // In the following, we consider only the cases where B is a superset of D, B 527 // is a subset of D, or B == D because otherwise there's at least one bit 528 // covered by B but not D, in which case we can't deduce much from it, so 529 // no folding (aside from the single must-be-one bit case right above.) 530 // For example, 531 // (icmp ne (A & 14), 0) & (icmp eq (A & 3), 1) -> no folding. 532 if (!IsSubSetOrEqual(BCst, DCst) && !IsSuperSetOrEqual(BCst, DCst)) 533 return nullptr; 534 535 // At this point, either B is a superset of D, B is a subset of D or B == D. 536 537 // If E is zero, if B is a subset of (or equal to) D, LHS and RHS contradict 538 // and the whole expression becomes false (or true if negated), otherwise, no 539 // folding. 540 // For example, 541 // (icmp ne (A & 3), 0) & (icmp eq (A & 7), 0) -> false. 542 // (icmp ne (A & 15), 0) & (icmp eq (A & 3), 0) -> no folding. 543 if (ECst->isZero()) { 544 if (IsSubSetOrEqual(BCst, DCst)) 545 return ConstantInt::get(LHS->getType(), !IsAnd); 546 return nullptr; 547 } 548 549 // At this point, B, D, E aren't zero and (B & D) == B, (B & D) == D or B == 550 // D. If B is a superset of (or equal to) D, since E is not zero, LHS is 551 // subsumed by RHS (RHS implies LHS.) So the whole expression becomes 552 // RHS. For example, 553 // (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). 554 // (icmp ne (A & 15), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). 555 if (IsSuperSetOrEqual(BCst, DCst)) 556 return RHS; 557 // Otherwise, B is a subset of D. If B and E have a common bit set, 558 // ie. (B & E) != 0, then LHS is subsumed by RHS. For example. 559 // (icmp ne (A & 12), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). 560 assert(IsSubSetOrEqual(BCst, DCst) && "Precondition due to above code"); 561 if ((BCst->getValue() & ECst->getValue()) != 0) 562 return RHS; 563 // Otherwise, LHS and RHS contradict and the whole expression becomes false 564 // (or true if negated.) For example, 565 // (icmp ne (A & 7), 0) & (icmp eq (A & 15), 8) -> false. 566 // (icmp ne (A & 6), 0) & (icmp eq (A & 15), 8) -> false. 567 return ConstantInt::get(LHS->getType(), !IsAnd); 568 } 569 570 /// Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single 571 /// (icmp(A & X) ==/!= Y), where the left-hand side and the right hand side 572 /// aren't of the common mask pattern type. 573 static Value *foldLogOpOfMaskedICmpsAsymmetric( 574 ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, 575 Value *A, Value *B, Value *C, Value *D, Value *E, 576 ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, 577 unsigned LHSMask, unsigned RHSMask, 578 llvm::InstCombiner::BuilderTy &Builder) { 579 assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) && 580 "Expected equality predicates for masked type of icmps."); 581 // Handle Mask_NotAllZeros-BMask_Mixed cases. 582 // (icmp ne/eq (A & B), C) &/| (icmp eq/ne (A & D), E), or 583 // (icmp eq/ne (A & B), C) &/| (icmp ne/eq (A & D), E) 584 // which gets swapped to 585 // (icmp ne/eq (A & D), E) &/| (icmp eq/ne (A & B), C). 586 if (!IsAnd) { 587 LHSMask = conjugateICmpMask(LHSMask); 588 RHSMask = conjugateICmpMask(RHSMask); 589 } 590 if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) { 591 if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( 592 LHS, RHS, IsAnd, A, B, C, D, E, 593 PredL, PredR, Builder)) { 594 return V; 595 } 596 } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) { 597 if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( 598 RHS, LHS, IsAnd, A, D, E, B, C, 599 PredR, PredL, Builder)) { 600 return V; 601 } 602 } 603 return nullptr; 604 } 605 606 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) 607 /// into a single (icmp(A & X) ==/!= Y). 608 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, 609 llvm::InstCombiner::BuilderTy &Builder) { 610 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr; 611 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); 612 Optional<std::pair<unsigned, unsigned>> MaskPair = 613 getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR); 614 if (!MaskPair) 615 return nullptr; 616 assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) && 617 "Expected equality predicates for masked type of icmps."); 618 unsigned LHSMask = MaskPair->first; 619 unsigned RHSMask = MaskPair->second; 620 unsigned Mask = LHSMask & RHSMask; 621 if (Mask == 0) { 622 // Even if the two sides don't share a common pattern, check if folding can 623 // still happen. 624 if (Value *V = foldLogOpOfMaskedICmpsAsymmetric( 625 LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask, 626 Builder)) 627 return V; 628 return nullptr; 629 } 630 631 // In full generality: 632 // (icmp (A & B) Op C) | (icmp (A & D) Op E) 633 // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ] 634 // 635 // If the latter can be converted into (icmp (A & X) Op Y) then the former is 636 // equivalent to (icmp (A & X) !Op Y). 637 // 638 // Therefore, we can pretend for the rest of this function that we're dealing 639 // with the conjunction, provided we flip the sense of any comparisons (both 640 // input and output). 641 642 // In most cases we're going to produce an EQ for the "&&" case. 643 ICmpInst::Predicate NewCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; 644 if (!IsAnd) { 645 // Convert the masking analysis into its equivalent with negated 646 // comparisons. 647 Mask = conjugateICmpMask(Mask); 648 } 649 650 if (Mask & Mask_AllZeros) { 651 // (icmp eq (A & B), 0) & (icmp eq (A & D), 0) 652 // -> (icmp eq (A & (B|D)), 0) 653 Value *NewOr = Builder.CreateOr(B, D); 654 Value *NewAnd = Builder.CreateAnd(A, NewOr); 655 // We can't use C as zero because we might actually handle 656 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 657 // with B and D, having a single bit set. 658 Value *Zero = Constant::getNullValue(A->getType()); 659 return Builder.CreateICmp(NewCC, NewAnd, Zero); 660 } 661 if (Mask & BMask_AllOnes) { 662 // (icmp eq (A & B), B) & (icmp eq (A & D), D) 663 // -> (icmp eq (A & (B|D)), (B|D)) 664 Value *NewOr = Builder.CreateOr(B, D); 665 Value *NewAnd = Builder.CreateAnd(A, NewOr); 666 return Builder.CreateICmp(NewCC, NewAnd, NewOr); 667 } 668 if (Mask & AMask_AllOnes) { 669 // (icmp eq (A & B), A) & (icmp eq (A & D), A) 670 // -> (icmp eq (A & (B&D)), A) 671 Value *NewAnd1 = Builder.CreateAnd(B, D); 672 Value *NewAnd2 = Builder.CreateAnd(A, NewAnd1); 673 return Builder.CreateICmp(NewCC, NewAnd2, A); 674 } 675 676 // Remaining cases assume at least that B and D are constant, and depend on 677 // their actual values. This isn't strictly necessary, just a "handle the 678 // easy cases for now" decision. 679 ConstantInt *BCst = dyn_cast<ConstantInt>(B); 680 if (!BCst) 681 return nullptr; 682 ConstantInt *DCst = dyn_cast<ConstantInt>(D); 683 if (!DCst) 684 return nullptr; 685 686 if (Mask & (Mask_NotAllZeros | BMask_NotAllOnes)) { 687 // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and 688 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 689 // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0) 690 // Only valid if one of the masks is a superset of the other (check "B&D" is 691 // the same as either B or D). 692 APInt NewMask = BCst->getValue() & DCst->getValue(); 693 694 if (NewMask == BCst->getValue()) 695 return LHS; 696 else if (NewMask == DCst->getValue()) 697 return RHS; 698 } 699 700 if (Mask & AMask_NotAllOnes) { 701 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 702 // -> (icmp ne (A & B), A) or (icmp ne (A & D), A) 703 // Only valid if one of the masks is a superset of the other (check "B|D" is 704 // the same as either B or D). 705 APInt NewMask = BCst->getValue() | DCst->getValue(); 706 707 if (NewMask == BCst->getValue()) 708 return LHS; 709 else if (NewMask == DCst->getValue()) 710 return RHS; 711 } 712 713 if (Mask & BMask_Mixed) { 714 // (icmp eq (A & B), C) & (icmp eq (A & D), E) 715 // We already know that B & C == C && D & E == E. 716 // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of 717 // C and E, which are shared by both the mask B and the mask D, don't 718 // contradict, then we can transform to 719 // -> (icmp eq (A & (B|D)), (C|E)) 720 // Currently, we only handle the case of B, C, D, and E being constant. 721 // We can't simply use C and E because we might actually handle 722 // (icmp ne (A & B), B) & (icmp eq (A & D), D) 723 // with B and D, having a single bit set. 724 ConstantInt *CCst = dyn_cast<ConstantInt>(C); 725 if (!CCst) 726 return nullptr; 727 ConstantInt *ECst = dyn_cast<ConstantInt>(E); 728 if (!ECst) 729 return nullptr; 730 if (PredL != NewCC) 731 CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst)); 732 if (PredR != NewCC) 733 ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst)); 734 735 // If there is a conflict, we should actually return a false for the 736 // whole construct. 737 if (((BCst->getValue() & DCst->getValue()) & 738 (CCst->getValue() ^ ECst->getValue())).getBoolValue()) 739 return ConstantInt::get(LHS->getType(), !IsAnd); 740 741 Value *NewOr1 = Builder.CreateOr(B, D); 742 Value *NewOr2 = ConstantExpr::getOr(CCst, ECst); 743 Value *NewAnd = Builder.CreateAnd(A, NewOr1); 744 return Builder.CreateICmp(NewCC, NewAnd, NewOr2); 745 } 746 747 return nullptr; 748 } 749 750 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp. 751 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n 752 /// If \p Inverted is true then the check is for the inverted range, e.g. 753 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n 754 Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, 755 bool Inverted) { 756 // Check the lower range comparison, e.g. x >= 0 757 // InstCombine already ensured that if there is a constant it's on the RHS. 758 ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1)); 759 if (!RangeStart) 760 return nullptr; 761 762 ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() : 763 Cmp0->getPredicate()); 764 765 // Accept x > -1 or x >= 0 (after potentially inverting the predicate). 766 if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) || 767 (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero()))) 768 return nullptr; 769 770 ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() : 771 Cmp1->getPredicate()); 772 773 Value *Input = Cmp0->getOperand(0); 774 Value *RangeEnd; 775 if (Cmp1->getOperand(0) == Input) { 776 // For the upper range compare we have: icmp x, n 777 RangeEnd = Cmp1->getOperand(1); 778 } else if (Cmp1->getOperand(1) == Input) { 779 // For the upper range compare we have: icmp n, x 780 RangeEnd = Cmp1->getOperand(0); 781 Pred1 = ICmpInst::getSwappedPredicate(Pred1); 782 } else { 783 return nullptr; 784 } 785 786 // Check the upper range comparison, e.g. x < n 787 ICmpInst::Predicate NewPred; 788 switch (Pred1) { 789 case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break; 790 case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break; 791 default: return nullptr; 792 } 793 794 // This simplification is only valid if the upper range is not negative. 795 KnownBits Known = computeKnownBits(RangeEnd, /*Depth=*/0, Cmp1); 796 if (!Known.isNonNegative()) 797 return nullptr; 798 799 if (Inverted) 800 NewPred = ICmpInst::getInversePredicate(NewPred); 801 802 return Builder.CreateICmp(NewPred, Input, RangeEnd); 803 } 804 805 static Value * 806 foldAndOrOfEqualityCmpsWithConstants(ICmpInst *LHS, ICmpInst *RHS, 807 bool JoinedByAnd, 808 InstCombiner::BuilderTy &Builder) { 809 Value *X = LHS->getOperand(0); 810 if (X != RHS->getOperand(0)) 811 return nullptr; 812 813 const APInt *C1, *C2; 814 if (!match(LHS->getOperand(1), m_APInt(C1)) || 815 !match(RHS->getOperand(1), m_APInt(C2))) 816 return nullptr; 817 818 // We only handle (X != C1 && X != C2) and (X == C1 || X == C2). 819 ICmpInst::Predicate Pred = LHS->getPredicate(); 820 if (Pred != RHS->getPredicate()) 821 return nullptr; 822 if (JoinedByAnd && Pred != ICmpInst::ICMP_NE) 823 return nullptr; 824 if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ) 825 return nullptr; 826 827 // The larger unsigned constant goes on the right. 828 if (C1->ugt(*C2)) 829 std::swap(C1, C2); 830 831 APInt Xor = *C1 ^ *C2; 832 if (Xor.isPowerOf2()) { 833 // If LHSC and RHSC differ by only one bit, then set that bit in X and 834 // compare against the larger constant: 835 // (X == C1 || X == C2) --> (X | (C1 ^ C2)) == C2 836 // (X != C1 && X != C2) --> (X | (C1 ^ C2)) != C2 837 // We choose an 'or' with a Pow2 constant rather than the inverse mask with 838 // 'and' because that may lead to smaller codegen from a smaller constant. 839 Value *Or = Builder.CreateOr(X, ConstantInt::get(X->getType(), Xor)); 840 return Builder.CreateICmp(Pred, Or, ConstantInt::get(X->getType(), *C2)); 841 } 842 843 // Special case: get the ordering right when the values wrap around zero. 844 // Ie, we assumed the constants were unsigned when swapping earlier. 845 if (C1->isNullValue() && C2->isAllOnesValue()) 846 std::swap(C1, C2); 847 848 if (*C1 == *C2 - 1) { 849 // (X == 13 || X == 14) --> X - 13 <=u 1 850 // (X != 13 && X != 14) --> X - 13 >u 1 851 // An 'add' is the canonical IR form, so favor that over a 'sub'. 852 Value *Add = Builder.CreateAdd(X, ConstantInt::get(X->getType(), -(*C1))); 853 auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE; 854 return Builder.CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1)); 855 } 856 857 return nullptr; 858 } 859 860 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2) 861 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2) 862 Value *InstCombiner::foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS, 863 bool JoinedByAnd, 864 Instruction &CxtI) { 865 ICmpInst::Predicate Pred = LHS->getPredicate(); 866 if (Pred != RHS->getPredicate()) 867 return nullptr; 868 if (JoinedByAnd && Pred != ICmpInst::ICMP_NE) 869 return nullptr; 870 if (!JoinedByAnd && Pred != ICmpInst::ICMP_EQ) 871 return nullptr; 872 873 // TODO support vector splats 874 ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1)); 875 ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1)); 876 if (!LHSC || !RHSC || !LHSC->isZero() || !RHSC->isZero()) 877 return nullptr; 878 879 Value *A, *B, *C, *D; 880 if (match(LHS->getOperand(0), m_And(m_Value(A), m_Value(B))) && 881 match(RHS->getOperand(0), m_And(m_Value(C), m_Value(D)))) { 882 if (A == D || B == D) 883 std::swap(C, D); 884 if (B == C) 885 std::swap(A, B); 886 887 if (A == C && 888 isKnownToBeAPowerOfTwo(B, false, 0, &CxtI) && 889 isKnownToBeAPowerOfTwo(D, false, 0, &CxtI)) { 890 Value *Mask = Builder.CreateOr(B, D); 891 Value *Masked = Builder.CreateAnd(A, Mask); 892 auto NewPred = JoinedByAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; 893 return Builder.CreateICmp(NewPred, Masked, Mask); 894 } 895 } 896 897 return nullptr; 898 } 899 900 /// General pattern: 901 /// X & Y 902 /// 903 /// Where Y is checking that all the high bits (covered by a mask 4294967168) 904 /// are uniform, i.e. %arg & 4294967168 can be either 4294967168 or 0 905 /// Pattern can be one of: 906 /// %t = add i32 %arg, 128 907 /// %r = icmp ult i32 %t, 256 908 /// Or 909 /// %t0 = shl i32 %arg, 24 910 /// %t1 = ashr i32 %t0, 24 911 /// %r = icmp eq i32 %t1, %arg 912 /// Or 913 /// %t0 = trunc i32 %arg to i8 914 /// %t1 = sext i8 %t0 to i32 915 /// %r = icmp eq i32 %t1, %arg 916 /// This pattern is a signed truncation check. 917 /// 918 /// And X is checking that some bit in that same mask is zero. 919 /// I.e. can be one of: 920 /// %r = icmp sgt i32 %arg, -1 921 /// Or 922 /// %t = and i32 %arg, 2147483648 923 /// %r = icmp eq i32 %t, 0 924 /// 925 /// Since we are checking that all the bits in that mask are the same, 926 /// and a particular bit is zero, what we are really checking is that all the 927 /// masked bits are zero. 928 /// So this should be transformed to: 929 /// %r = icmp ult i32 %arg, 128 930 static Value *foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1, 931 Instruction &CxtI, 932 InstCombiner::BuilderTy &Builder) { 933 assert(CxtI.getOpcode() == Instruction::And); 934 935 // Match icmp ult (add %arg, C01), C1 (C1 == C01 << 1; powers of two) 936 auto tryToMatchSignedTruncationCheck = [](ICmpInst *ICmp, Value *&X, 937 APInt &SignBitMask) -> bool { 938 CmpInst::Predicate Pred; 939 const APInt *I01, *I1; // powers of two; I1 == I01 << 1 940 if (!(match(ICmp, 941 m_ICmp(Pred, m_Add(m_Value(X), m_Power2(I01)), m_Power2(I1))) && 942 Pred == ICmpInst::ICMP_ULT && I1->ugt(*I01) && I01->shl(1) == *I1)) 943 return false; 944 // Which bit is the new sign bit as per the 'signed truncation' pattern? 945 SignBitMask = *I01; 946 return true; 947 }; 948 949 // One icmp needs to be 'signed truncation check'. 950 // We need to match this first, else we will mismatch commutative cases. 951 Value *X1; 952 APInt HighestBit; 953 ICmpInst *OtherICmp; 954 if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit)) 955 OtherICmp = ICmp0; 956 else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit)) 957 OtherICmp = ICmp1; 958 else 959 return nullptr; 960 961 assert(HighestBit.isPowerOf2() && "expected to be power of two (non-zero)"); 962 963 // Try to match/decompose into: icmp eq (X & Mask), 0 964 auto tryToDecompose = [](ICmpInst *ICmp, Value *&X, 965 APInt &UnsetBitsMask) -> bool { 966 CmpInst::Predicate Pred = ICmp->getPredicate(); 967 // Can it be decomposed into icmp eq (X & Mask), 0 ? 968 if (llvm::decomposeBitTestICmp(ICmp->getOperand(0), ICmp->getOperand(1), 969 Pred, X, UnsetBitsMask, 970 /*LookThroughTrunc=*/false) && 971 Pred == ICmpInst::ICMP_EQ) 972 return true; 973 // Is it icmp eq (X & Mask), 0 already? 974 const APInt *Mask; 975 if (match(ICmp, m_ICmp(Pred, m_And(m_Value(X), m_APInt(Mask)), m_Zero())) && 976 Pred == ICmpInst::ICMP_EQ) { 977 UnsetBitsMask = *Mask; 978 return true; 979 } 980 return false; 981 }; 982 983 // And the other icmp needs to be decomposable into a bit test. 984 Value *X0; 985 APInt UnsetBitsMask; 986 if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask)) 987 return nullptr; 988 989 assert(!UnsetBitsMask.isNullValue() && "empty mask makes no sense."); 990 991 // Are they working on the same value? 992 Value *X; 993 if (X1 == X0) { 994 // Ok as is. 995 X = X1; 996 } else if (match(X0, m_Trunc(m_Specific(X1)))) { 997 UnsetBitsMask = UnsetBitsMask.zext(X1->getType()->getScalarSizeInBits()); 998 X = X1; 999 } else 1000 return nullptr; 1001 1002 // So which bits should be uniform as per the 'signed truncation check'? 1003 // (all the bits starting with (i.e. including) HighestBit) 1004 APInt SignBitsMask = ~(HighestBit - 1U); 1005 1006 // UnsetBitsMask must have some common bits with SignBitsMask, 1007 if (!UnsetBitsMask.intersects(SignBitsMask)) 1008 return nullptr; 1009 1010 // Does UnsetBitsMask contain any bits outside of SignBitsMask? 1011 if (!UnsetBitsMask.isSubsetOf(SignBitsMask)) { 1012 APInt OtherHighestBit = (~UnsetBitsMask) + 1U; 1013 if (!OtherHighestBit.isPowerOf2()) 1014 return nullptr; 1015 HighestBit = APIntOps::umin(HighestBit, OtherHighestBit); 1016 } 1017 // Else, if it does not, then all is ok as-is. 1018 1019 // %r = icmp ult %X, SignBit 1020 return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit), 1021 CxtI.getName() + ".simplified"); 1022 } 1023 1024 /// Reduce a pair of compares that check if a value has exactly 1 bit set. 1025 static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd, 1026 InstCombiner::BuilderTy &Builder) { 1027 // Handle 'and' / 'or' commutation: make the equality check the first operand. 1028 if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE) 1029 std::swap(Cmp0, Cmp1); 1030 else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ) 1031 std::swap(Cmp0, Cmp1); 1032 1033 // (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1 1034 CmpInst::Predicate Pred0, Pred1; 1035 Value *X; 1036 if (JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) && 1037 match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)), 1038 m_SpecificInt(2))) && 1039 Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_ULT) { 1040 Value *CtPop = Cmp1->getOperand(0); 1041 return Builder.CreateICmpEQ(CtPop, ConstantInt::get(CtPop->getType(), 1)); 1042 } 1043 // (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1 1044 if (!JoinedByAnd && match(Cmp0, m_ICmp(Pred0, m_Value(X), m_ZeroInt())) && 1045 match(Cmp1, m_ICmp(Pred1, m_Intrinsic<Intrinsic::ctpop>(m_Specific(X)), 1046 m_SpecificInt(1))) && 1047 Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_UGT) { 1048 Value *CtPop = Cmp1->getOperand(0); 1049 return Builder.CreateICmpNE(CtPop, ConstantInt::get(CtPop->getType(), 1)); 1050 } 1051 return nullptr; 1052 } 1053 1054 /// Fold (icmp)&(icmp) if possible. 1055 Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, 1056 Instruction &CxtI) { 1057 // Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2) 1058 // if K1 and K2 are a one-bit mask. 1059 if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, true, CxtI)) 1060 return V; 1061 1062 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); 1063 1064 // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B) 1065 if (predicatesFoldable(PredL, PredR)) { 1066 if (LHS->getOperand(0) == RHS->getOperand(1) && 1067 LHS->getOperand(1) == RHS->getOperand(0)) 1068 LHS->swapOperands(); 1069 if (LHS->getOperand(0) == RHS->getOperand(0) && 1070 LHS->getOperand(1) == RHS->getOperand(1)) { 1071 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 1072 unsigned Code = getICmpCode(LHS) & getICmpCode(RHS); 1073 bool IsSigned = LHS->isSigned() || RHS->isSigned(); 1074 return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); 1075 } 1076 } 1077 1078 // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E) 1079 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder)) 1080 return V; 1081 1082 // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n 1083 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false)) 1084 return V; 1085 1086 // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n 1087 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false)) 1088 return V; 1089 1090 if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder)) 1091 return V; 1092 1093 if (Value *V = foldSignedTruncationCheck(LHS, RHS, CxtI, Builder)) 1094 return V; 1095 1096 if (Value *V = foldIsPowerOf2(LHS, RHS, true /* JoinedByAnd */, Builder)) 1097 return V; 1098 1099 // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2). 1100 Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0); 1101 ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1)); 1102 ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1)); 1103 if (!LHSC || !RHSC) 1104 return nullptr; 1105 1106 if (LHSC == RHSC && PredL == PredR) { 1107 // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C) 1108 // where C is a power of 2 or 1109 // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0) 1110 if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) || 1111 (PredL == ICmpInst::ICMP_EQ && LHSC->isZero())) { 1112 Value *NewOr = Builder.CreateOr(LHS0, RHS0); 1113 return Builder.CreateICmp(PredL, NewOr, LHSC); 1114 } 1115 } 1116 1117 // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2 1118 // where CMAX is the all ones value for the truncated type, 1119 // iff the lower bits of C2 and CA are zero. 1120 if (PredL == ICmpInst::ICMP_EQ && PredL == PredR && LHS->hasOneUse() && 1121 RHS->hasOneUse()) { 1122 Value *V; 1123 ConstantInt *AndC, *SmallC = nullptr, *BigC = nullptr; 1124 1125 // (trunc x) == C1 & (and x, CA) == C2 1126 // (and x, CA) == C2 & (trunc x) == C1 1127 if (match(RHS0, m_Trunc(m_Value(V))) && 1128 match(LHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) { 1129 SmallC = RHSC; 1130 BigC = LHSC; 1131 } else if (match(LHS0, m_Trunc(m_Value(V))) && 1132 match(RHS0, m_And(m_Specific(V), m_ConstantInt(AndC)))) { 1133 SmallC = LHSC; 1134 BigC = RHSC; 1135 } 1136 1137 if (SmallC && BigC) { 1138 unsigned BigBitSize = BigC->getType()->getBitWidth(); 1139 unsigned SmallBitSize = SmallC->getType()->getBitWidth(); 1140 1141 // Check that the low bits are zero. 1142 APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize); 1143 if ((Low & AndC->getValue()).isNullValue() && 1144 (Low & BigC->getValue()).isNullValue()) { 1145 Value *NewAnd = Builder.CreateAnd(V, Low | AndC->getValue()); 1146 APInt N = SmallC->getValue().zext(BigBitSize) | BigC->getValue(); 1147 Value *NewVal = ConstantInt::get(AndC->getType()->getContext(), N); 1148 return Builder.CreateICmp(PredL, NewAnd, NewVal); 1149 } 1150 } 1151 } 1152 1153 // From here on, we only handle: 1154 // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler. 1155 if (LHS0 != RHS0) 1156 return nullptr; 1157 1158 // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere. 1159 if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE || 1160 PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE || 1161 PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE || 1162 PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE) 1163 return nullptr; 1164 1165 // We can't fold (ugt x, C) & (sgt x, C2). 1166 if (!predicatesFoldable(PredL, PredR)) 1167 return nullptr; 1168 1169 // Ensure that the larger constant is on the RHS. 1170 bool ShouldSwap; 1171 if (CmpInst::isSigned(PredL) || 1172 (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR))) 1173 ShouldSwap = LHSC->getValue().sgt(RHSC->getValue()); 1174 else 1175 ShouldSwap = LHSC->getValue().ugt(RHSC->getValue()); 1176 1177 if (ShouldSwap) { 1178 std::swap(LHS, RHS); 1179 std::swap(LHSC, RHSC); 1180 std::swap(PredL, PredR); 1181 } 1182 1183 // At this point, we know we have two icmp instructions 1184 // comparing a value against two constants and and'ing the result 1185 // together. Because of the above check, we know that we only have 1186 // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know 1187 // (from the icmp folding check above), that the two constants 1188 // are not equal and that the larger constant is on the RHS 1189 assert(LHSC != RHSC && "Compares not folded above?"); 1190 1191 switch (PredL) { 1192 default: 1193 llvm_unreachable("Unknown integer condition code!"); 1194 case ICmpInst::ICMP_NE: 1195 switch (PredR) { 1196 default: 1197 llvm_unreachable("Unknown integer condition code!"); 1198 case ICmpInst::ICMP_ULT: 1199 if (LHSC == SubOne(RHSC)) // (X != 13 & X u< 14) -> X < 13 1200 return Builder.CreateICmpULT(LHS0, LHSC); 1201 if (LHSC->isZero()) // (X != 0 & X u< 14) -> X-1 u< 13 1202 return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), 1203 false, true); 1204 break; // (X != 13 & X u< 15) -> no change 1205 case ICmpInst::ICMP_SLT: 1206 if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13 1207 return Builder.CreateICmpSLT(LHS0, LHSC); 1208 break; // (X != 13 & X s< 15) -> no change 1209 case ICmpInst::ICMP_NE: 1210 // Potential folds for this case should already be handled. 1211 break; 1212 } 1213 break; 1214 case ICmpInst::ICMP_UGT: 1215 switch (PredR) { 1216 default: 1217 llvm_unreachable("Unknown integer condition code!"); 1218 case ICmpInst::ICMP_NE: 1219 if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14 1220 return Builder.CreateICmp(PredL, LHS0, RHSC); 1221 break; // (X u> 13 & X != 15) -> no change 1222 case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1 1223 return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), 1224 false, true); 1225 } 1226 break; 1227 case ICmpInst::ICMP_SGT: 1228 switch (PredR) { 1229 default: 1230 llvm_unreachable("Unknown integer condition code!"); 1231 case ICmpInst::ICMP_NE: 1232 if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14 1233 return Builder.CreateICmp(PredL, LHS0, RHSC); 1234 break; // (X s> 13 & X != 15) -> no change 1235 case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1 1236 return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true, 1237 true); 1238 } 1239 break; 1240 } 1241 1242 return nullptr; 1243 } 1244 1245 Value *InstCombiner::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) { 1246 Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); 1247 Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1); 1248 FCmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); 1249 1250 if (LHS0 == RHS1 && RHS0 == LHS1) { 1251 // Swap RHS operands to match LHS. 1252 PredR = FCmpInst::getSwappedPredicate(PredR); 1253 std::swap(RHS0, RHS1); 1254 } 1255 1256 // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y). 1257 // Suppose the relation between x and y is R, where R is one of 1258 // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for 1259 // testing the desired relations. 1260 // 1261 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this: 1262 // bool(R & CC0) && bool(R & CC1) 1263 // = bool((R & CC0) & (R & CC1)) 1264 // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency 1265 // 1266 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this: 1267 // bool(R & CC0) || bool(R & CC1) 1268 // = bool((R & CC0) | (R & CC1)) 1269 // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;) 1270 if (LHS0 == RHS0 && LHS1 == RHS1) { 1271 unsigned FCmpCodeL = getFCmpCode(PredL); 1272 unsigned FCmpCodeR = getFCmpCode(PredR); 1273 unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR; 1274 return getFCmpValue(NewPred, LHS0, LHS1, Builder); 1275 } 1276 1277 if ((PredL == FCmpInst::FCMP_ORD && PredR == FCmpInst::FCMP_ORD && IsAnd) || 1278 (PredL == FCmpInst::FCMP_UNO && PredR == FCmpInst::FCMP_UNO && !IsAnd)) { 1279 if (LHS0->getType() != RHS0->getType()) 1280 return nullptr; 1281 1282 // FCmp canonicalization ensures that (fcmp ord/uno X, X) and 1283 // (fcmp ord/uno X, C) will be transformed to (fcmp X, +0.0). 1284 if (match(LHS1, m_PosZeroFP()) && match(RHS1, m_PosZeroFP())) 1285 // Ignore the constants because they are obviously not NANs: 1286 // (fcmp ord x, 0.0) & (fcmp ord y, 0.0) -> (fcmp ord x, y) 1287 // (fcmp uno x, 0.0) | (fcmp uno y, 0.0) -> (fcmp uno x, y) 1288 return Builder.CreateFCmp(PredL, LHS0, RHS0); 1289 } 1290 1291 return nullptr; 1292 } 1293 1294 /// This a limited reassociation for a special case (see above) where we are 1295 /// checking if two values are either both NAN (unordered) or not-NAN (ordered). 1296 /// This could be handled more generally in '-reassociation', but it seems like 1297 /// an unlikely pattern for a large number of logic ops and fcmps. 1298 static Instruction *reassociateFCmps(BinaryOperator &BO, 1299 InstCombiner::BuilderTy &Builder) { 1300 Instruction::BinaryOps Opcode = BO.getOpcode(); 1301 assert((Opcode == Instruction::And || Opcode == Instruction::Or) && 1302 "Expecting and/or op for fcmp transform"); 1303 1304 // There are 4 commuted variants of the pattern. Canonicalize operands of this 1305 // logic op so an fcmp is operand 0 and a matching logic op is operand 1. 1306 Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1), *X; 1307 FCmpInst::Predicate Pred; 1308 if (match(Op1, m_FCmp(Pred, m_Value(), m_AnyZeroFP()))) 1309 std::swap(Op0, Op1); 1310 1311 // Match inner binop and the predicate for combining 2 NAN checks into 1. 1312 BinaryOperator *BO1; 1313 FCmpInst::Predicate NanPred = Opcode == Instruction::And ? FCmpInst::FCMP_ORD 1314 : FCmpInst::FCMP_UNO; 1315 if (!match(Op0, m_FCmp(Pred, m_Value(X), m_AnyZeroFP())) || Pred != NanPred || 1316 !match(Op1, m_BinOp(BO1)) || BO1->getOpcode() != Opcode) 1317 return nullptr; 1318 1319 // The inner logic op must have a matching fcmp operand. 1320 Value *BO10 = BO1->getOperand(0), *BO11 = BO1->getOperand(1), *Y; 1321 if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) || 1322 Pred != NanPred || X->getType() != Y->getType()) 1323 std::swap(BO10, BO11); 1324 1325 if (!match(BO10, m_FCmp(Pred, m_Value(Y), m_AnyZeroFP())) || 1326 Pred != NanPred || X->getType() != Y->getType()) 1327 return nullptr; 1328 1329 // and (fcmp ord X, 0), (and (fcmp ord Y, 0), Z) --> and (fcmp ord X, Y), Z 1330 // or (fcmp uno X, 0), (or (fcmp uno Y, 0), Z) --> or (fcmp uno X, Y), Z 1331 Value *NewFCmp = Builder.CreateFCmp(Pred, X, Y); 1332 if (auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) { 1333 // Intersect FMF from the 2 source fcmps. 1334 NewFCmpInst->copyIRFlags(Op0); 1335 NewFCmpInst->andIRFlags(BO10); 1336 } 1337 return BinaryOperator::Create(Opcode, NewFCmp, BO11); 1338 } 1339 1340 /// Match De Morgan's Laws: 1341 /// (~A & ~B) == (~(A | B)) 1342 /// (~A | ~B) == (~(A & B)) 1343 static Instruction *matchDeMorgansLaws(BinaryOperator &I, 1344 InstCombiner::BuilderTy &Builder) { 1345 auto Opcode = I.getOpcode(); 1346 assert((Opcode == Instruction::And || Opcode == Instruction::Or) && 1347 "Trying to match De Morgan's Laws with something other than and/or"); 1348 1349 // Flip the logic operation. 1350 Opcode = (Opcode == Instruction::And) ? Instruction::Or : Instruction::And; 1351 1352 Value *A, *B; 1353 if (match(I.getOperand(0), m_OneUse(m_Not(m_Value(A)))) && 1354 match(I.getOperand(1), m_OneUse(m_Not(m_Value(B)))) && 1355 !IsFreeToInvert(A, A->hasOneUse()) && 1356 !IsFreeToInvert(B, B->hasOneUse())) { 1357 Value *AndOr = Builder.CreateBinOp(Opcode, A, B, I.getName() + ".demorgan"); 1358 return BinaryOperator::CreateNot(AndOr); 1359 } 1360 1361 return nullptr; 1362 } 1363 1364 bool InstCombiner::shouldOptimizeCast(CastInst *CI) { 1365 Value *CastSrc = CI->getOperand(0); 1366 1367 // Noop casts and casts of constants should be eliminated trivially. 1368 if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc)) 1369 return false; 1370 1371 // If this cast is paired with another cast that can be eliminated, we prefer 1372 // to have it eliminated. 1373 if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc)) 1374 if (isEliminableCastPair(PrecedingCI, CI)) 1375 return false; 1376 1377 return true; 1378 } 1379 1380 /// Fold {and,or,xor} (cast X), C. 1381 static Instruction *foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast, 1382 InstCombiner::BuilderTy &Builder) { 1383 Constant *C = dyn_cast<Constant>(Logic.getOperand(1)); 1384 if (!C) 1385 return nullptr; 1386 1387 auto LogicOpc = Logic.getOpcode(); 1388 Type *DestTy = Logic.getType(); 1389 Type *SrcTy = Cast->getSrcTy(); 1390 1391 // Move the logic operation ahead of a zext or sext if the constant is 1392 // unchanged in the smaller source type. Performing the logic in a smaller 1393 // type may provide more information to later folds, and the smaller logic 1394 // instruction may be cheaper (particularly in the case of vectors). 1395 Value *X; 1396 if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) { 1397 Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy); 1398 Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy); 1399 if (ZextTruncC == C) { 1400 // LogicOpc (zext X), C --> zext (LogicOpc X, C) 1401 Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC); 1402 return new ZExtInst(NewOp, DestTy); 1403 } 1404 } 1405 1406 if (match(Cast, m_OneUse(m_SExt(m_Value(X))))) { 1407 Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy); 1408 Constant *SextTruncC = ConstantExpr::getSExt(TruncC, DestTy); 1409 if (SextTruncC == C) { 1410 // LogicOpc (sext X), C --> sext (LogicOpc X, C) 1411 Value *NewOp = Builder.CreateBinOp(LogicOpc, X, TruncC); 1412 return new SExtInst(NewOp, DestTy); 1413 } 1414 } 1415 1416 return nullptr; 1417 } 1418 1419 /// Fold {and,or,xor} (cast X), Y. 1420 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) { 1421 auto LogicOpc = I.getOpcode(); 1422 assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding"); 1423 1424 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1425 CastInst *Cast0 = dyn_cast<CastInst>(Op0); 1426 if (!Cast0) 1427 return nullptr; 1428 1429 // This must be a cast from an integer or integer vector source type to allow 1430 // transformation of the logic operation to the source type. 1431 Type *DestTy = I.getType(); 1432 Type *SrcTy = Cast0->getSrcTy(); 1433 if (!SrcTy->isIntOrIntVectorTy()) 1434 return nullptr; 1435 1436 if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder)) 1437 return Ret; 1438 1439 CastInst *Cast1 = dyn_cast<CastInst>(Op1); 1440 if (!Cast1) 1441 return nullptr; 1442 1443 // Both operands of the logic operation are casts. The casts must be of the 1444 // same type for reduction. 1445 auto CastOpcode = Cast0->getOpcode(); 1446 if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy()) 1447 return nullptr; 1448 1449 Value *Cast0Src = Cast0->getOperand(0); 1450 Value *Cast1Src = Cast1->getOperand(0); 1451 1452 // fold logic(cast(A), cast(B)) -> cast(logic(A, B)) 1453 if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) { 1454 Value *NewOp = Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src, 1455 I.getName()); 1456 return CastInst::Create(CastOpcode, NewOp, DestTy); 1457 } 1458 1459 // For now, only 'and'/'or' have optimizations after this. 1460 if (LogicOpc == Instruction::Xor) 1461 return nullptr; 1462 1463 // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the 1464 // cast is otherwise not optimizable. This happens for vector sexts. 1465 ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src); 1466 ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src); 1467 if (ICmp0 && ICmp1) { 1468 Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, I) 1469 : foldOrOfICmps(ICmp0, ICmp1, I); 1470 if (Res) 1471 return CastInst::Create(CastOpcode, Res, DestTy); 1472 return nullptr; 1473 } 1474 1475 // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the 1476 // cast is otherwise not optimizable. This happens for vector sexts. 1477 FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src); 1478 FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src); 1479 if (FCmp0 && FCmp1) 1480 if (Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And)) 1481 return CastInst::Create(CastOpcode, R, DestTy); 1482 1483 return nullptr; 1484 } 1485 1486 static Instruction *foldAndToXor(BinaryOperator &I, 1487 InstCombiner::BuilderTy &Builder) { 1488 assert(I.getOpcode() == Instruction::And); 1489 Value *Op0 = I.getOperand(0); 1490 Value *Op1 = I.getOperand(1); 1491 Value *A, *B; 1492 1493 // Operand complexity canonicalization guarantees that the 'or' is Op0. 1494 // (A | B) & ~(A & B) --> A ^ B 1495 // (A | B) & ~(B & A) --> A ^ B 1496 if (match(&I, m_BinOp(m_Or(m_Value(A), m_Value(B)), 1497 m_Not(m_c_And(m_Deferred(A), m_Deferred(B)))))) 1498 return BinaryOperator::CreateXor(A, B); 1499 1500 // (A | ~B) & (~A | B) --> ~(A ^ B) 1501 // (A | ~B) & (B | ~A) --> ~(A ^ B) 1502 // (~B | A) & (~A | B) --> ~(A ^ B) 1503 // (~B | A) & (B | ~A) --> ~(A ^ B) 1504 if (Op0->hasOneUse() || Op1->hasOneUse()) 1505 if (match(&I, m_BinOp(m_c_Or(m_Value(A), m_Not(m_Value(B))), 1506 m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) 1507 return BinaryOperator::CreateNot(Builder.CreateXor(A, B)); 1508 1509 return nullptr; 1510 } 1511 1512 static Instruction *foldOrToXor(BinaryOperator &I, 1513 InstCombiner::BuilderTy &Builder) { 1514 assert(I.getOpcode() == Instruction::Or); 1515 Value *Op0 = I.getOperand(0); 1516 Value *Op1 = I.getOperand(1); 1517 Value *A, *B; 1518 1519 // Operand complexity canonicalization guarantees that the 'and' is Op0. 1520 // (A & B) | ~(A | B) --> ~(A ^ B) 1521 // (A & B) | ~(B | A) --> ~(A ^ B) 1522 if (Op0->hasOneUse() || Op1->hasOneUse()) 1523 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1524 match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))) 1525 return BinaryOperator::CreateNot(Builder.CreateXor(A, B)); 1526 1527 // (A & ~B) | (~A & B) --> A ^ B 1528 // (A & ~B) | (B & ~A) --> A ^ B 1529 // (~B & A) | (~A & B) --> A ^ B 1530 // (~B & A) | (B & ~A) --> A ^ B 1531 if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) && 1532 match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))) 1533 return BinaryOperator::CreateXor(A, B); 1534 1535 return nullptr; 1536 } 1537 1538 /// Return true if a constant shift amount is always less than the specified 1539 /// bit-width. If not, the shift could create poison in the narrower type. 1540 static bool canNarrowShiftAmt(Constant *C, unsigned BitWidth) { 1541 if (auto *ScalarC = dyn_cast<ConstantInt>(C)) 1542 return ScalarC->getZExtValue() < BitWidth; 1543 1544 if (C->getType()->isVectorTy()) { 1545 // Check each element of a constant vector. 1546 unsigned NumElts = C->getType()->getVectorNumElements(); 1547 for (unsigned i = 0; i != NumElts; ++i) { 1548 Constant *Elt = C->getAggregateElement(i); 1549 if (!Elt) 1550 return false; 1551 if (isa<UndefValue>(Elt)) 1552 continue; 1553 auto *CI = dyn_cast<ConstantInt>(Elt); 1554 if (!CI || CI->getZExtValue() >= BitWidth) 1555 return false; 1556 } 1557 return true; 1558 } 1559 1560 // The constant is a constant expression or unknown. 1561 return false; 1562 } 1563 1564 /// Try to use narrower ops (sink zext ops) for an 'and' with binop operand and 1565 /// a common zext operand: and (binop (zext X), C), (zext X). 1566 Instruction *InstCombiner::narrowMaskedBinOp(BinaryOperator &And) { 1567 // This transform could also apply to {or, and, xor}, but there are better 1568 // folds for those cases, so we don't expect those patterns here. AShr is not 1569 // handled because it should always be transformed to LShr in this sequence. 1570 // The subtract transform is different because it has a constant on the left. 1571 // Add/mul commute the constant to RHS; sub with constant RHS becomes add. 1572 Value *Op0 = And.getOperand(0), *Op1 = And.getOperand(1); 1573 Constant *C; 1574 if (!match(Op0, m_OneUse(m_Add(m_Specific(Op1), m_Constant(C)))) && 1575 !match(Op0, m_OneUse(m_Mul(m_Specific(Op1), m_Constant(C)))) && 1576 !match(Op0, m_OneUse(m_LShr(m_Specific(Op1), m_Constant(C)))) && 1577 !match(Op0, m_OneUse(m_Shl(m_Specific(Op1), m_Constant(C)))) && 1578 !match(Op0, m_OneUse(m_Sub(m_Constant(C), m_Specific(Op1))))) 1579 return nullptr; 1580 1581 Value *X; 1582 if (!match(Op1, m_ZExt(m_Value(X))) || Op1->hasNUsesOrMore(3)) 1583 return nullptr; 1584 1585 Type *Ty = And.getType(); 1586 if (!isa<VectorType>(Ty) && !shouldChangeType(Ty, X->getType())) 1587 return nullptr; 1588 1589 // If we're narrowing a shift, the shift amount must be safe (less than the 1590 // width) in the narrower type. If the shift amount is greater, instsimplify 1591 // usually handles that case, but we can't guarantee/assert it. 1592 Instruction::BinaryOps Opc = cast<BinaryOperator>(Op0)->getOpcode(); 1593 if (Opc == Instruction::LShr || Opc == Instruction::Shl) 1594 if (!canNarrowShiftAmt(C, X->getType()->getScalarSizeInBits())) 1595 return nullptr; 1596 1597 // and (sub C, (zext X)), (zext X) --> zext (and (sub C', X), X) 1598 // and (binop (zext X), C), (zext X) --> zext (and (binop X, C'), X) 1599 Value *NewC = ConstantExpr::getTrunc(C, X->getType()); 1600 Value *NewBO = Opc == Instruction::Sub ? Builder.CreateBinOp(Opc, NewC, X) 1601 : Builder.CreateBinOp(Opc, X, NewC); 1602 return new ZExtInst(Builder.CreateAnd(NewBO, X), Ty); 1603 } 1604 1605 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches 1606 // here. We should standardize that construct where it is needed or choose some 1607 // other way to ensure that commutated variants of patterns are not missed. 1608 Instruction *InstCombiner::visitAnd(BinaryOperator &I) { 1609 if (Value *V = SimplifyAndInst(I.getOperand(0), I.getOperand(1), 1610 SQ.getWithInstruction(&I))) 1611 return replaceInstUsesWith(I, V); 1612 1613 if (SimplifyAssociativeOrCommutative(I)) 1614 return &I; 1615 1616 if (Instruction *X = foldVectorBinop(I)) 1617 return X; 1618 1619 // See if we can simplify any instructions used by the instruction whose sole 1620 // purpose is to compute bits we don't care about. 1621 if (SimplifyDemandedInstructionBits(I)) 1622 return &I; 1623 1624 // Do this before using distributive laws to catch simple and/or/not patterns. 1625 if (Instruction *Xor = foldAndToXor(I, Builder)) 1626 return Xor; 1627 1628 // (A|B)&(A|C) -> A|(B&C) etc 1629 if (Value *V = SimplifyUsingDistributiveLaws(I)) 1630 return replaceInstUsesWith(I, V); 1631 1632 if (Value *V = SimplifyBSwap(I, Builder)) 1633 return replaceInstUsesWith(I, V); 1634 1635 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1636 const APInt *C; 1637 if (match(Op1, m_APInt(C))) { 1638 Value *X, *Y; 1639 if (match(Op0, m_OneUse(m_LogicalShift(m_One(), m_Value(X)))) && 1640 C->isOneValue()) { 1641 // (1 << X) & 1 --> zext(X == 0) 1642 // (1 >> X) & 1 --> zext(X == 0) 1643 Value *IsZero = Builder.CreateICmpEQ(X, ConstantInt::get(I.getType(), 0)); 1644 return new ZExtInst(IsZero, I.getType()); 1645 } 1646 1647 const APInt *XorC; 1648 if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_APInt(XorC))))) { 1649 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) 1650 Constant *NewC = ConstantInt::get(I.getType(), *C & *XorC); 1651 Value *And = Builder.CreateAnd(X, Op1); 1652 And->takeName(Op0); 1653 return BinaryOperator::CreateXor(And, NewC); 1654 } 1655 1656 const APInt *OrC; 1657 if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) { 1658 // (X | C1) & C2 --> (X & C2^(C1&C2)) | (C1&C2) 1659 // NOTE: This reduces the number of bits set in the & mask, which 1660 // can expose opportunities for store narrowing for scalars. 1661 // NOTE: SimplifyDemandedBits should have already removed bits from C1 1662 // that aren't set in C2. Meaning we can replace (C1&C2) with C1 in 1663 // above, but this feels safer. 1664 APInt Together = *C & *OrC; 1665 Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(), 1666 Together ^ *C)); 1667 And->takeName(Op0); 1668 return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(), 1669 Together)); 1670 } 1671 1672 // If the mask is only needed on one incoming arm, push the 'and' op up. 1673 if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) || 1674 match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) { 1675 APInt NotAndMask(~(*C)); 1676 BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode(); 1677 if (MaskedValueIsZero(X, NotAndMask, 0, &I)) { 1678 // Not masking anything out for the LHS, move mask to RHS. 1679 // and ({x}or X, Y), C --> {x}or X, (and Y, C) 1680 Value *NewRHS = Builder.CreateAnd(Y, Op1, Y->getName() + ".masked"); 1681 return BinaryOperator::Create(BinOp, X, NewRHS); 1682 } 1683 if (!isa<Constant>(Y) && MaskedValueIsZero(Y, NotAndMask, 0, &I)) { 1684 // Not masking anything out for the RHS, move mask to LHS. 1685 // and ({x}or X, Y), C --> {x}or (and X, C), Y 1686 Value *NewLHS = Builder.CreateAnd(X, Op1, X->getName() + ".masked"); 1687 return BinaryOperator::Create(BinOp, NewLHS, Y); 1688 } 1689 } 1690 1691 } 1692 1693 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) { 1694 const APInt &AndRHSMask = AndRHS->getValue(); 1695 1696 // Optimize a variety of ((val OP C1) & C2) combinations... 1697 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 1698 // ((C1 OP zext(X)) & C2) -> zext((C1-X) & C2) if C2 fits in the bitwidth 1699 // of X and OP behaves well when given trunc(C1) and X. 1700 // TODO: Do this for vectors by using m_APInt isntead of m_ConstantInt. 1701 switch (Op0I->getOpcode()) { 1702 default: 1703 break; 1704 case Instruction::Xor: 1705 case Instruction::Or: 1706 case Instruction::Mul: 1707 case Instruction::Add: 1708 case Instruction::Sub: 1709 Value *X; 1710 ConstantInt *C1; 1711 // TODO: The one use restrictions could be relaxed a little if the AND 1712 // is going to be removed. 1713 if (match(Op0I, m_OneUse(m_c_BinOp(m_OneUse(m_ZExt(m_Value(X))), 1714 m_ConstantInt(C1))))) { 1715 if (AndRHSMask.isIntN(X->getType()->getScalarSizeInBits())) { 1716 auto *TruncC1 = ConstantExpr::getTrunc(C1, X->getType()); 1717 Value *BinOp; 1718 Value *Op0LHS = Op0I->getOperand(0); 1719 if (isa<ZExtInst>(Op0LHS)) 1720 BinOp = Builder.CreateBinOp(Op0I->getOpcode(), X, TruncC1); 1721 else 1722 BinOp = Builder.CreateBinOp(Op0I->getOpcode(), TruncC1, X); 1723 auto *TruncC2 = ConstantExpr::getTrunc(AndRHS, X->getType()); 1724 auto *And = Builder.CreateAnd(BinOp, TruncC2); 1725 return new ZExtInst(And, I.getType()); 1726 } 1727 } 1728 } 1729 1730 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) 1731 if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I)) 1732 return Res; 1733 } 1734 1735 // If this is an integer truncation, and if the source is an 'and' with 1736 // immediate, transform it. This frequently occurs for bitfield accesses. 1737 { 1738 Value *X = nullptr; ConstantInt *YC = nullptr; 1739 if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) { 1740 // Change: and (trunc (and X, YC) to T), C2 1741 // into : and (trunc X to T), trunc(YC) & C2 1742 // This will fold the two constants together, which may allow 1743 // other simplifications. 1744 Value *NewCast = Builder.CreateTrunc(X, I.getType(), "and.shrunk"); 1745 Constant *C3 = ConstantExpr::getTrunc(YC, I.getType()); 1746 C3 = ConstantExpr::getAnd(C3, AndRHS); 1747 return BinaryOperator::CreateAnd(NewCast, C3); 1748 } 1749 } 1750 } 1751 1752 if (Instruction *Z = narrowMaskedBinOp(I)) 1753 return Z; 1754 1755 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) 1756 return FoldedLogic; 1757 1758 if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder)) 1759 return DeMorgan; 1760 1761 { 1762 Value *A, *B, *C; 1763 // A & (A ^ B) --> A & ~B 1764 if (match(Op1, m_OneUse(m_c_Xor(m_Specific(Op0), m_Value(B))))) 1765 return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(B)); 1766 // (A ^ B) & A --> A & ~B 1767 if (match(Op0, m_OneUse(m_c_Xor(m_Specific(Op1), m_Value(B))))) 1768 return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(B)); 1769 1770 // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C 1771 if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) 1772 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) 1773 if (Op1->hasOneUse() || IsFreeToInvert(C, C->hasOneUse())) 1774 return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(C)); 1775 1776 // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C 1777 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B)))) 1778 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A)))) 1779 if (Op0->hasOneUse() || IsFreeToInvert(C, C->hasOneUse())) 1780 return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C)); 1781 1782 // (A | B) & ((~A) ^ B) -> (A & B) 1783 // (A | B) & (B ^ (~A)) -> (A & B) 1784 // (B | A) & ((~A) ^ B) -> (A & B) 1785 // (B | A) & (B ^ (~A)) -> (A & B) 1786 if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) && 1787 match(Op0, m_c_Or(m_Specific(A), m_Specific(B)))) 1788 return BinaryOperator::CreateAnd(A, B); 1789 1790 // ((~A) ^ B) & (A | B) -> (A & B) 1791 // ((~A) ^ B) & (B | A) -> (A & B) 1792 // (B ^ (~A)) & (A | B) -> (A & B) 1793 // (B ^ (~A)) & (B | A) -> (A & B) 1794 if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) && 1795 match(Op1, m_c_Or(m_Specific(A), m_Specific(B)))) 1796 return BinaryOperator::CreateAnd(A, B); 1797 } 1798 1799 { 1800 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0); 1801 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1); 1802 if (LHS && RHS) 1803 if (Value *Res = foldAndOfICmps(LHS, RHS, I)) 1804 return replaceInstUsesWith(I, Res); 1805 1806 // TODO: Make this recursive; it's a little tricky because an arbitrary 1807 // number of 'and' instructions might have to be created. 1808 Value *X, *Y; 1809 if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) { 1810 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 1811 if (Value *Res = foldAndOfICmps(LHS, Cmp, I)) 1812 return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y)); 1813 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 1814 if (Value *Res = foldAndOfICmps(LHS, Cmp, I)) 1815 return replaceInstUsesWith(I, Builder.CreateAnd(Res, X)); 1816 } 1817 if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) { 1818 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 1819 if (Value *Res = foldAndOfICmps(Cmp, RHS, I)) 1820 return replaceInstUsesWith(I, Builder.CreateAnd(Res, Y)); 1821 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 1822 if (Value *Res = foldAndOfICmps(Cmp, RHS, I)) 1823 return replaceInstUsesWith(I, Builder.CreateAnd(Res, X)); 1824 } 1825 } 1826 1827 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 1828 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 1829 if (Value *Res = foldLogicOfFCmps(LHS, RHS, true)) 1830 return replaceInstUsesWith(I, Res); 1831 1832 if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder)) 1833 return FoldedFCmps; 1834 1835 if (Instruction *CastedAnd = foldCastedBitwiseLogic(I)) 1836 return CastedAnd; 1837 1838 // and(sext(A), B) / and(B, sext(A)) --> A ? B : 0, where A is i1 or <N x i1>. 1839 Value *A; 1840 if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) && 1841 A->getType()->isIntOrIntVectorTy(1)) 1842 return SelectInst::Create(A, Op1, Constant::getNullValue(I.getType())); 1843 if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) && 1844 A->getType()->isIntOrIntVectorTy(1)) 1845 return SelectInst::Create(A, Op0, Constant::getNullValue(I.getType())); 1846 1847 return nullptr; 1848 } 1849 1850 Instruction *InstCombiner::matchBSwap(BinaryOperator &Or) { 1851 assert(Or.getOpcode() == Instruction::Or && "bswap requires an 'or'"); 1852 Value *Op0 = Or.getOperand(0), *Op1 = Or.getOperand(1); 1853 1854 // Look through zero extends. 1855 if (Instruction *Ext = dyn_cast<ZExtInst>(Op0)) 1856 Op0 = Ext->getOperand(0); 1857 1858 if (Instruction *Ext = dyn_cast<ZExtInst>(Op1)) 1859 Op1 = Ext->getOperand(0); 1860 1861 // (A | B) | C and A | (B | C) -> bswap if possible. 1862 bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) || 1863 match(Op1, m_Or(m_Value(), m_Value())); 1864 1865 // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible. 1866 bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) && 1867 match(Op1, m_LogicalShift(m_Value(), m_Value())); 1868 1869 // (A & B) | (C & D) -> bswap if possible. 1870 bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) && 1871 match(Op1, m_And(m_Value(), m_Value())); 1872 1873 // (A << B) | (C & D) -> bswap if possible. 1874 // The bigger pattern here is ((A & C1) << C2) | ((B >> C2) & C1), which is a 1875 // part of the bswap idiom for specific values of C1, C2 (e.g. C1 = 16711935, 1876 // C2 = 8 for i32). 1877 // This pattern can occur when the operands of the 'or' are not canonicalized 1878 // for some reason (not having only one use, for example). 1879 bool OrOfAndAndSh = (match(Op0, m_LogicalShift(m_Value(), m_Value())) && 1880 match(Op1, m_And(m_Value(), m_Value()))) || 1881 (match(Op0, m_And(m_Value(), m_Value())) && 1882 match(Op1, m_LogicalShift(m_Value(), m_Value()))); 1883 1884 if (!OrOfOrs && !OrOfShifts && !OrOfAnds && !OrOfAndAndSh) 1885 return nullptr; 1886 1887 SmallVector<Instruction*, 4> Insts; 1888 if (!recognizeBSwapOrBitReverseIdiom(&Or, true, false, Insts)) 1889 return nullptr; 1890 Instruction *LastInst = Insts.pop_back_val(); 1891 LastInst->removeFromParent(); 1892 1893 for (auto *Inst : Insts) 1894 Worklist.Add(Inst); 1895 return LastInst; 1896 } 1897 1898 /// Transform UB-safe variants of bitwise rotate to the funnel shift intrinsic. 1899 static Instruction *matchRotate(Instruction &Or) { 1900 // TODO: Can we reduce the code duplication between this and the related 1901 // rotate matching code under visitSelect and visitTrunc? 1902 unsigned Width = Or.getType()->getScalarSizeInBits(); 1903 if (!isPowerOf2_32(Width)) 1904 return nullptr; 1905 1906 // First, find an or'd pair of opposite shifts with the same shifted operand: 1907 // or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1) 1908 BinaryOperator *Or0, *Or1; 1909 if (!match(Or.getOperand(0), m_BinOp(Or0)) || 1910 !match(Or.getOperand(1), m_BinOp(Or1))) 1911 return nullptr; 1912 1913 Value *ShVal, *ShAmt0, *ShAmt1; 1914 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) || 1915 !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1))))) 1916 return nullptr; 1917 1918 BinaryOperator::BinaryOps ShiftOpcode0 = Or0->getOpcode(); 1919 BinaryOperator::BinaryOps ShiftOpcode1 = Or1->getOpcode(); 1920 if (ShiftOpcode0 == ShiftOpcode1) 1921 return nullptr; 1922 1923 // Match the shift amount operands for a rotate pattern. This always matches 1924 // a subtraction on the R operand. 1925 auto matchShiftAmount = [](Value *L, Value *R, unsigned Width) -> Value * { 1926 // The shift amount may be masked with negation: 1927 // (shl ShVal, (X & (Width - 1))) | (lshr ShVal, ((-X) & (Width - 1))) 1928 Value *X; 1929 unsigned Mask = Width - 1; 1930 if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) && 1931 match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))) 1932 return X; 1933 1934 // Similar to above, but the shift amount may be extended after masking, 1935 // so return the extended value as the parameter for the intrinsic. 1936 if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) && 1937 match(R, m_And(m_Neg(m_ZExt(m_And(m_Specific(X), m_SpecificInt(Mask)))), 1938 m_SpecificInt(Mask)))) 1939 return L; 1940 1941 return nullptr; 1942 }; 1943 1944 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, Width); 1945 bool SubIsOnLHS = false; 1946 if (!ShAmt) { 1947 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, Width); 1948 SubIsOnLHS = true; 1949 } 1950 if (!ShAmt) 1951 return nullptr; 1952 1953 bool IsFshl = (!SubIsOnLHS && ShiftOpcode0 == BinaryOperator::Shl) || 1954 (SubIsOnLHS && ShiftOpcode1 == BinaryOperator::Shl); 1955 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr; 1956 Function *F = Intrinsic::getDeclaration(Or.getModule(), IID, Or.getType()); 1957 return IntrinsicInst::Create(F, { ShVal, ShVal, ShAmt }); 1958 } 1959 1960 /// If all elements of two constant vectors are 0/-1 and inverses, return true. 1961 static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) { 1962 unsigned NumElts = C1->getType()->getVectorNumElements(); 1963 for (unsigned i = 0; i != NumElts; ++i) { 1964 Constant *EltC1 = C1->getAggregateElement(i); 1965 Constant *EltC2 = C2->getAggregateElement(i); 1966 if (!EltC1 || !EltC2) 1967 return false; 1968 1969 // One element must be all ones, and the other must be all zeros. 1970 if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) || 1971 (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes())))) 1972 return false; 1973 } 1974 return true; 1975 } 1976 1977 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or 1978 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of 1979 /// B, it can be used as the condition operand of a select instruction. 1980 Value *InstCombiner::getSelectCondition(Value *A, Value *B) { 1981 // Step 1: We may have peeked through bitcasts in the caller. 1982 // Exit immediately if we don't have (vector) integer types. 1983 Type *Ty = A->getType(); 1984 if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy()) 1985 return nullptr; 1986 1987 // Step 2: We need 0 or all-1's bitmasks. 1988 if (ComputeNumSignBits(A) != Ty->getScalarSizeInBits()) 1989 return nullptr; 1990 1991 // Step 3: If B is the 'not' value of A, we have our answer. 1992 if (match(A, m_Not(m_Specific(B)))) { 1993 // If these are scalars or vectors of i1, A can be used directly. 1994 if (Ty->isIntOrIntVectorTy(1)) 1995 return A; 1996 return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(Ty)); 1997 } 1998 1999 // If both operands are constants, see if the constants are inverse bitmasks. 2000 Constant *AConst, *BConst; 2001 if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst))) 2002 if (AConst == ConstantExpr::getNot(BConst)) 2003 return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty)); 2004 2005 // Look for more complex patterns. The 'not' op may be hidden behind various 2006 // casts. Look through sexts and bitcasts to find the booleans. 2007 Value *Cond; 2008 Value *NotB; 2009 if (match(A, m_SExt(m_Value(Cond))) && 2010 Cond->getType()->isIntOrIntVectorTy(1) && 2011 match(B, m_OneUse(m_Not(m_Value(NotB))))) { 2012 NotB = peekThroughBitcast(NotB, true); 2013 if (match(NotB, m_SExt(m_Specific(Cond)))) 2014 return Cond; 2015 } 2016 2017 // All scalar (and most vector) possibilities should be handled now. 2018 // Try more matches that only apply to non-splat constant vectors. 2019 if (!Ty->isVectorTy()) 2020 return nullptr; 2021 2022 // If both operands are xor'd with constants using the same sexted boolean 2023 // operand, see if the constants are inverse bitmasks. 2024 // TODO: Use ConstantExpr::getNot()? 2025 if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) && 2026 match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BConst)))) && 2027 Cond->getType()->isIntOrIntVectorTy(1) && 2028 areInverseVectorBitmasks(AConst, BConst)) { 2029 AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty)); 2030 return Builder.CreateXor(Cond, AConst); 2031 } 2032 return nullptr; 2033 } 2034 2035 /// We have an expression of the form (A & C) | (B & D). Try to simplify this 2036 /// to "A' ? C : D", where A' is a boolean or vector of booleans. 2037 Value *InstCombiner::matchSelectFromAndOr(Value *A, Value *C, Value *B, 2038 Value *D) { 2039 // The potential condition of the select may be bitcasted. In that case, look 2040 // through its bitcast and the corresponding bitcast of the 'not' condition. 2041 Type *OrigType = A->getType(); 2042 A = peekThroughBitcast(A, true); 2043 B = peekThroughBitcast(B, true); 2044 if (Value *Cond = getSelectCondition(A, B)) { 2045 // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D)) 2046 // The bitcasts will either all exist or all not exist. The builder will 2047 // not create unnecessary casts if the types already match. 2048 Value *BitcastC = Builder.CreateBitCast(C, A->getType()); 2049 Value *BitcastD = Builder.CreateBitCast(D, A->getType()); 2050 Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD); 2051 return Builder.CreateBitCast(Select, OrigType); 2052 } 2053 2054 return nullptr; 2055 } 2056 2057 /// Fold (icmp)|(icmp) if possible. 2058 Value *InstCombiner::foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, 2059 Instruction &CxtI) { 2060 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2) 2061 // if K1 and K2 are a one-bit mask. 2062 if (Value *V = foldAndOrOfICmpsOfAndWithPow2(LHS, RHS, false, CxtI)) 2063 return V; 2064 2065 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); 2066 2067 ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1)); 2068 ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1)); 2069 2070 // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3) 2071 // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3) 2072 // The original condition actually refers to the following two ranges: 2073 // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3] 2074 // We can fold these two ranges if: 2075 // 1) C1 and C2 is unsigned greater than C3. 2076 // 2) The two ranges are separated. 2077 // 3) C1 ^ C2 is one-bit mask. 2078 // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask. 2079 // This implies all values in the two ranges differ by exactly one bit. 2080 2081 if ((PredL == ICmpInst::ICMP_ULT || PredL == ICmpInst::ICMP_ULE) && 2082 PredL == PredR && LHSC && RHSC && LHS->hasOneUse() && RHS->hasOneUse() && 2083 LHSC->getType() == RHSC->getType() && 2084 LHSC->getValue() == (RHSC->getValue())) { 2085 2086 Value *LAdd = LHS->getOperand(0); 2087 Value *RAdd = RHS->getOperand(0); 2088 2089 Value *LAddOpnd, *RAddOpnd; 2090 ConstantInt *LAddC, *RAddC; 2091 if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddC))) && 2092 match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddC))) && 2093 LAddC->getValue().ugt(LHSC->getValue()) && 2094 RAddC->getValue().ugt(LHSC->getValue())) { 2095 2096 APInt DiffC = LAddC->getValue() ^ RAddC->getValue(); 2097 if (LAddOpnd == RAddOpnd && DiffC.isPowerOf2()) { 2098 ConstantInt *MaxAddC = nullptr; 2099 if (LAddC->getValue().ult(RAddC->getValue())) 2100 MaxAddC = RAddC; 2101 else 2102 MaxAddC = LAddC; 2103 2104 APInt RRangeLow = -RAddC->getValue(); 2105 APInt RRangeHigh = RRangeLow + LHSC->getValue(); 2106 APInt LRangeLow = -LAddC->getValue(); 2107 APInt LRangeHigh = LRangeLow + LHSC->getValue(); 2108 APInt LowRangeDiff = RRangeLow ^ LRangeLow; 2109 APInt HighRangeDiff = RRangeHigh ^ LRangeHigh; 2110 APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow 2111 : RRangeLow - LRangeLow; 2112 2113 if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff && 2114 RangeDiff.ugt(LHSC->getValue())) { 2115 Value *MaskC = ConstantInt::get(LAddC->getType(), ~DiffC); 2116 2117 Value *NewAnd = Builder.CreateAnd(LAddOpnd, MaskC); 2118 Value *NewAdd = Builder.CreateAdd(NewAnd, MaxAddC); 2119 return Builder.CreateICmp(LHS->getPredicate(), NewAdd, LHSC); 2120 } 2121 } 2122 } 2123 } 2124 2125 // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B) 2126 if (predicatesFoldable(PredL, PredR)) { 2127 if (LHS->getOperand(0) == RHS->getOperand(1) && 2128 LHS->getOperand(1) == RHS->getOperand(0)) 2129 LHS->swapOperands(); 2130 if (LHS->getOperand(0) == RHS->getOperand(0) && 2131 LHS->getOperand(1) == RHS->getOperand(1)) { 2132 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 2133 unsigned Code = getICmpCode(LHS) | getICmpCode(RHS); 2134 bool IsSigned = LHS->isSigned() || RHS->isSigned(); 2135 return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); 2136 } 2137 } 2138 2139 // handle (roughly): 2140 // (icmp ne (A & B), C) | (icmp ne (A & D), E) 2141 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder)) 2142 return V; 2143 2144 Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0); 2145 if (LHS->hasOneUse() || RHS->hasOneUse()) { 2146 // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1) 2147 // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1) 2148 Value *A = nullptr, *B = nullptr; 2149 if (PredL == ICmpInst::ICMP_EQ && LHSC && LHSC->isZero()) { 2150 B = LHS0; 2151 if (PredR == ICmpInst::ICMP_ULT && LHS0 == RHS->getOperand(1)) 2152 A = RHS0; 2153 else if (PredR == ICmpInst::ICMP_UGT && LHS0 == RHS0) 2154 A = RHS->getOperand(1); 2155 } 2156 // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1) 2157 // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1) 2158 else if (PredR == ICmpInst::ICMP_EQ && RHSC && RHSC->isZero()) { 2159 B = RHS0; 2160 if (PredL == ICmpInst::ICMP_ULT && RHS0 == LHS->getOperand(1)) 2161 A = LHS0; 2162 else if (PredL == ICmpInst::ICMP_UGT && LHS0 == RHS0) 2163 A = LHS->getOperand(1); 2164 } 2165 if (A && B) 2166 return Builder.CreateICmp( 2167 ICmpInst::ICMP_UGE, 2168 Builder.CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A); 2169 } 2170 2171 // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n 2172 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true)) 2173 return V; 2174 2175 // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n 2176 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true)) 2177 return V; 2178 2179 if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder)) 2180 return V; 2181 2182 if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder)) 2183 return V; 2184 2185 // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2). 2186 if (!LHSC || !RHSC) 2187 return nullptr; 2188 2189 if (LHSC == RHSC && PredL == PredR) { 2190 // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0) 2191 if (PredL == ICmpInst::ICMP_NE && LHSC->isZero()) { 2192 Value *NewOr = Builder.CreateOr(LHS0, RHS0); 2193 return Builder.CreateICmp(PredL, NewOr, LHSC); 2194 } 2195 } 2196 2197 // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1) 2198 // iff C2 + CA == C1. 2199 if (PredL == ICmpInst::ICMP_ULT && PredR == ICmpInst::ICMP_EQ) { 2200 ConstantInt *AddC; 2201 if (match(LHS0, m_Add(m_Specific(RHS0), m_ConstantInt(AddC)))) 2202 if (RHSC->getValue() + AddC->getValue() == LHSC->getValue()) 2203 return Builder.CreateICmpULE(LHS0, LHSC); 2204 } 2205 2206 // From here on, we only handle: 2207 // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler. 2208 if (LHS0 != RHS0) 2209 return nullptr; 2210 2211 // ICMP_[US][GL]E X, C is folded to ICMP_[US][GL]T elsewhere. 2212 if (PredL == ICmpInst::ICMP_UGE || PredL == ICmpInst::ICMP_ULE || 2213 PredR == ICmpInst::ICMP_UGE || PredR == ICmpInst::ICMP_ULE || 2214 PredL == ICmpInst::ICMP_SGE || PredL == ICmpInst::ICMP_SLE || 2215 PredR == ICmpInst::ICMP_SGE || PredR == ICmpInst::ICMP_SLE) 2216 return nullptr; 2217 2218 // We can't fold (ugt x, C) | (sgt x, C2). 2219 if (!predicatesFoldable(PredL, PredR)) 2220 return nullptr; 2221 2222 // Ensure that the larger constant is on the RHS. 2223 bool ShouldSwap; 2224 if (CmpInst::isSigned(PredL) || 2225 (ICmpInst::isEquality(PredL) && CmpInst::isSigned(PredR))) 2226 ShouldSwap = LHSC->getValue().sgt(RHSC->getValue()); 2227 else 2228 ShouldSwap = LHSC->getValue().ugt(RHSC->getValue()); 2229 2230 if (ShouldSwap) { 2231 std::swap(LHS, RHS); 2232 std::swap(LHSC, RHSC); 2233 std::swap(PredL, PredR); 2234 } 2235 2236 // At this point, we know we have two icmp instructions 2237 // comparing a value against two constants and or'ing the result 2238 // together. Because of the above check, we know that we only have 2239 // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the 2240 // icmp folding check above), that the two constants are not 2241 // equal. 2242 assert(LHSC != RHSC && "Compares not folded above?"); 2243 2244 switch (PredL) { 2245 default: 2246 llvm_unreachable("Unknown integer condition code!"); 2247 case ICmpInst::ICMP_EQ: 2248 switch (PredR) { 2249 default: 2250 llvm_unreachable("Unknown integer condition code!"); 2251 case ICmpInst::ICMP_EQ: 2252 // Potential folds for this case should already be handled. 2253 break; 2254 case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change 2255 case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change 2256 break; 2257 } 2258 break; 2259 case ICmpInst::ICMP_ULT: 2260 switch (PredR) { 2261 default: 2262 llvm_unreachable("Unknown integer condition code!"); 2263 case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change 2264 break; 2265 case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2 2266 assert(!RHSC->isMaxValue(false) && "Missed icmp simplification"); 2267 return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, 2268 false, false); 2269 } 2270 break; 2271 case ICmpInst::ICMP_SLT: 2272 switch (PredR) { 2273 default: 2274 llvm_unreachable("Unknown integer condition code!"); 2275 case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change 2276 break; 2277 case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2 2278 assert(!RHSC->isMaxValue(true) && "Missed icmp simplification"); 2279 return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true, 2280 false); 2281 } 2282 break; 2283 } 2284 return nullptr; 2285 } 2286 2287 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches 2288 // here. We should standardize that construct where it is needed or choose some 2289 // other way to ensure that commutated variants of patterns are not missed. 2290 Instruction *InstCombiner::visitOr(BinaryOperator &I) { 2291 if (Value *V = SimplifyOrInst(I.getOperand(0), I.getOperand(1), 2292 SQ.getWithInstruction(&I))) 2293 return replaceInstUsesWith(I, V); 2294 2295 if (SimplifyAssociativeOrCommutative(I)) 2296 return &I; 2297 2298 if (Instruction *X = foldVectorBinop(I)) 2299 return X; 2300 2301 // See if we can simplify any instructions used by the instruction whose sole 2302 // purpose is to compute bits we don't care about. 2303 if (SimplifyDemandedInstructionBits(I)) 2304 return &I; 2305 2306 // Do this before using distributive laws to catch simple and/or/not patterns. 2307 if (Instruction *Xor = foldOrToXor(I, Builder)) 2308 return Xor; 2309 2310 // (A&B)|(A&C) -> A&(B|C) etc 2311 if (Value *V = SimplifyUsingDistributiveLaws(I)) 2312 return replaceInstUsesWith(I, V); 2313 2314 if (Value *V = SimplifyBSwap(I, Builder)) 2315 return replaceInstUsesWith(I, V); 2316 2317 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) 2318 return FoldedLogic; 2319 2320 if (Instruction *BSwap = matchBSwap(I)) 2321 return BSwap; 2322 2323 if (Instruction *Rotate = matchRotate(I)) 2324 return Rotate; 2325 2326 Value *X, *Y; 2327 const APInt *CV; 2328 if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) && 2329 !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) { 2330 // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0 2331 // The check for a 'not' op is for efficiency (if Y is known zero --> ~X). 2332 Value *Or = Builder.CreateOr(X, Y); 2333 return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV)); 2334 } 2335 2336 // (A & C)|(B & D) 2337 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2338 Value *A, *B, *C, *D; 2339 if (match(Op0, m_And(m_Value(A), m_Value(C))) && 2340 match(Op1, m_And(m_Value(B), m_Value(D)))) { 2341 ConstantInt *C1 = dyn_cast<ConstantInt>(C); 2342 ConstantInt *C2 = dyn_cast<ConstantInt>(D); 2343 if (C1 && C2) { // (A & C1)|(B & C2) 2344 Value *V1 = nullptr, *V2 = nullptr; 2345 if ((C1->getValue() & C2->getValue()).isNullValue()) { 2346 // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2) 2347 // iff (C1&C2) == 0 and (N&~C1) == 0 2348 if (match(A, m_Or(m_Value(V1), m_Value(V2))) && 2349 ((V1 == B && 2350 MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N) 2351 (V2 == B && 2352 MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V) 2353 return BinaryOperator::CreateAnd(A, 2354 Builder.getInt(C1->getValue()|C2->getValue())); 2355 // Or commutes, try both ways. 2356 if (match(B, m_Or(m_Value(V1), m_Value(V2))) && 2357 ((V1 == A && 2358 MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N) 2359 (V2 == A && 2360 MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V) 2361 return BinaryOperator::CreateAnd(B, 2362 Builder.getInt(C1->getValue()|C2->getValue())); 2363 2364 // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2) 2365 // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0. 2366 ConstantInt *C3 = nullptr, *C4 = nullptr; 2367 if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) && 2368 (C3->getValue() & ~C1->getValue()).isNullValue() && 2369 match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) && 2370 (C4->getValue() & ~C2->getValue()).isNullValue()) { 2371 V2 = Builder.CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield"); 2372 return BinaryOperator::CreateAnd(V2, 2373 Builder.getInt(C1->getValue()|C2->getValue())); 2374 } 2375 } 2376 2377 if (C1->getValue() == ~C2->getValue()) { 2378 Value *X; 2379 2380 // ((X|B)&C1)|(B&C2) -> (X&C1) | B iff C1 == ~C2 2381 if (match(A, m_c_Or(m_Value(X), m_Specific(B)))) 2382 return BinaryOperator::CreateOr(Builder.CreateAnd(X, C1), B); 2383 // (A&C2)|((X|A)&C1) -> (X&C2) | A iff C1 == ~C2 2384 if (match(B, m_c_Or(m_Specific(A), m_Value(X)))) 2385 return BinaryOperator::CreateOr(Builder.CreateAnd(X, C2), A); 2386 2387 // ((X^B)&C1)|(B&C2) -> (X&C1) ^ B iff C1 == ~C2 2388 if (match(A, m_c_Xor(m_Value(X), m_Specific(B)))) 2389 return BinaryOperator::CreateXor(Builder.CreateAnd(X, C1), B); 2390 // (A&C2)|((X^A)&C1) -> (X&C2) ^ A iff C1 == ~C2 2391 if (match(B, m_c_Xor(m_Specific(A), m_Value(X)))) 2392 return BinaryOperator::CreateXor(Builder.CreateAnd(X, C2), A); 2393 } 2394 } 2395 2396 // Don't try to form a select if it's unlikely that we'll get rid of at 2397 // least one of the operands. A select is generally more expensive than the 2398 // 'or' that it is replacing. 2399 if (Op0->hasOneUse() || Op1->hasOneUse()) { 2400 // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants. 2401 if (Value *V = matchSelectFromAndOr(A, C, B, D)) 2402 return replaceInstUsesWith(I, V); 2403 if (Value *V = matchSelectFromAndOr(A, C, D, B)) 2404 return replaceInstUsesWith(I, V); 2405 if (Value *V = matchSelectFromAndOr(C, A, B, D)) 2406 return replaceInstUsesWith(I, V); 2407 if (Value *V = matchSelectFromAndOr(C, A, D, B)) 2408 return replaceInstUsesWith(I, V); 2409 if (Value *V = matchSelectFromAndOr(B, D, A, C)) 2410 return replaceInstUsesWith(I, V); 2411 if (Value *V = matchSelectFromAndOr(B, D, C, A)) 2412 return replaceInstUsesWith(I, V); 2413 if (Value *V = matchSelectFromAndOr(D, B, A, C)) 2414 return replaceInstUsesWith(I, V); 2415 if (Value *V = matchSelectFromAndOr(D, B, C, A)) 2416 return replaceInstUsesWith(I, V); 2417 } 2418 } 2419 2420 // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C 2421 if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) 2422 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) 2423 return BinaryOperator::CreateOr(Op0, C); 2424 2425 // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C 2426 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B)))) 2427 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A)))) 2428 return BinaryOperator::CreateOr(Op1, C); 2429 2430 // ((B | C) & A) | B -> B | (A & C) 2431 if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A)))) 2432 return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C)); 2433 2434 if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder)) 2435 return DeMorgan; 2436 2437 // Canonicalize xor to the RHS. 2438 bool SwappedForXor = false; 2439 if (match(Op0, m_Xor(m_Value(), m_Value()))) { 2440 std::swap(Op0, Op1); 2441 SwappedForXor = true; 2442 } 2443 2444 // A | ( A ^ B) -> A | B 2445 // A | (~A ^ B) -> A | ~B 2446 // (A & B) | (A ^ B) 2447 if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) { 2448 if (Op0 == A || Op0 == B) 2449 return BinaryOperator::CreateOr(A, B); 2450 2451 if (match(Op0, m_And(m_Specific(A), m_Specific(B))) || 2452 match(Op0, m_And(m_Specific(B), m_Specific(A)))) 2453 return BinaryOperator::CreateOr(A, B); 2454 2455 if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) { 2456 Value *Not = Builder.CreateNot(B, B->getName() + ".not"); 2457 return BinaryOperator::CreateOr(Not, Op0); 2458 } 2459 if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) { 2460 Value *Not = Builder.CreateNot(A, A->getName() + ".not"); 2461 return BinaryOperator::CreateOr(Not, Op0); 2462 } 2463 } 2464 2465 // A | ~(A | B) -> A | ~B 2466 // A | ~(A ^ B) -> A | ~B 2467 if (match(Op1, m_Not(m_Value(A)))) 2468 if (BinaryOperator *B = dyn_cast<BinaryOperator>(A)) 2469 if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) && 2470 Op1->hasOneUse() && (B->getOpcode() == Instruction::Or || 2471 B->getOpcode() == Instruction::Xor)) { 2472 Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) : 2473 B->getOperand(0); 2474 Value *Not = Builder.CreateNot(NotOp, NotOp->getName() + ".not"); 2475 return BinaryOperator::CreateOr(Not, Op0); 2476 } 2477 2478 if (SwappedForXor) 2479 std::swap(Op0, Op1); 2480 2481 { 2482 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0); 2483 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1); 2484 if (LHS && RHS) 2485 if (Value *Res = foldOrOfICmps(LHS, RHS, I)) 2486 return replaceInstUsesWith(I, Res); 2487 2488 // TODO: Make this recursive; it's a little tricky because an arbitrary 2489 // number of 'or' instructions might have to be created. 2490 Value *X, *Y; 2491 if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) { 2492 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 2493 if (Value *Res = foldOrOfICmps(LHS, Cmp, I)) 2494 return replaceInstUsesWith(I, Builder.CreateOr(Res, Y)); 2495 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 2496 if (Value *Res = foldOrOfICmps(LHS, Cmp, I)) 2497 return replaceInstUsesWith(I, Builder.CreateOr(Res, X)); 2498 } 2499 if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) { 2500 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 2501 if (Value *Res = foldOrOfICmps(Cmp, RHS, I)) 2502 return replaceInstUsesWith(I, Builder.CreateOr(Res, Y)); 2503 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 2504 if (Value *Res = foldOrOfICmps(Cmp, RHS, I)) 2505 return replaceInstUsesWith(I, Builder.CreateOr(Res, X)); 2506 } 2507 } 2508 2509 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 2510 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 2511 if (Value *Res = foldLogicOfFCmps(LHS, RHS, false)) 2512 return replaceInstUsesWith(I, Res); 2513 2514 if (Instruction *FoldedFCmps = reassociateFCmps(I, Builder)) 2515 return FoldedFCmps; 2516 2517 if (Instruction *CastedOr = foldCastedBitwiseLogic(I)) 2518 return CastedOr; 2519 2520 // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>. 2521 if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) && 2522 A->getType()->isIntOrIntVectorTy(1)) 2523 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1); 2524 if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) && 2525 A->getType()->isIntOrIntVectorTy(1)) 2526 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0); 2527 2528 // Note: If we've gotten to the point of visiting the outer OR, then the 2529 // inner one couldn't be simplified. If it was a constant, then it won't 2530 // be simplified by a later pass either, so we try swapping the inner/outer 2531 // ORs in the hopes that we'll be able to simplify it this way. 2532 // (X|C) | V --> (X|V) | C 2533 ConstantInt *CI; 2534 if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) && 2535 match(Op0, m_Or(m_Value(A), m_ConstantInt(CI)))) { 2536 Value *Inner = Builder.CreateOr(A, Op1); 2537 Inner->takeName(Op0); 2538 return BinaryOperator::CreateOr(Inner, CI); 2539 } 2540 2541 // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D)) 2542 // Since this OR statement hasn't been optimized further yet, we hope 2543 // that this transformation will allow the new ORs to be optimized. 2544 { 2545 Value *X = nullptr, *Y = nullptr; 2546 if (Op0->hasOneUse() && Op1->hasOneUse() && 2547 match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) && 2548 match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) { 2549 Value *orTrue = Builder.CreateOr(A, C); 2550 Value *orFalse = Builder.CreateOr(B, D); 2551 return SelectInst::Create(X, orTrue, orFalse); 2552 } 2553 } 2554 2555 return nullptr; 2556 } 2557 2558 /// A ^ B can be specified using other logic ops in a variety of patterns. We 2559 /// can fold these early and efficiently by morphing an existing instruction. 2560 static Instruction *foldXorToXor(BinaryOperator &I, 2561 InstCombiner::BuilderTy &Builder) { 2562 assert(I.getOpcode() == Instruction::Xor); 2563 Value *Op0 = I.getOperand(0); 2564 Value *Op1 = I.getOperand(1); 2565 Value *A, *B; 2566 2567 // There are 4 commuted variants for each of the basic patterns. 2568 2569 // (A & B) ^ (A | B) -> A ^ B 2570 // (A & B) ^ (B | A) -> A ^ B 2571 // (A | B) ^ (A & B) -> A ^ B 2572 // (A | B) ^ (B & A) -> A ^ B 2573 if (match(&I, m_c_Xor(m_And(m_Value(A), m_Value(B)), 2574 m_c_Or(m_Deferred(A), m_Deferred(B))))) { 2575 I.setOperand(0, A); 2576 I.setOperand(1, B); 2577 return &I; 2578 } 2579 2580 // (A | ~B) ^ (~A | B) -> A ^ B 2581 // (~B | A) ^ (~A | B) -> A ^ B 2582 // (~A | B) ^ (A | ~B) -> A ^ B 2583 // (B | ~A) ^ (A | ~B) -> A ^ B 2584 if (match(&I, m_Xor(m_c_Or(m_Value(A), m_Not(m_Value(B))), 2585 m_c_Or(m_Not(m_Deferred(A)), m_Deferred(B))))) { 2586 I.setOperand(0, A); 2587 I.setOperand(1, B); 2588 return &I; 2589 } 2590 2591 // (A & ~B) ^ (~A & B) -> A ^ B 2592 // (~B & A) ^ (~A & B) -> A ^ B 2593 // (~A & B) ^ (A & ~B) -> A ^ B 2594 // (B & ~A) ^ (A & ~B) -> A ^ B 2595 if (match(&I, m_Xor(m_c_And(m_Value(A), m_Not(m_Value(B))), 2596 m_c_And(m_Not(m_Deferred(A)), m_Deferred(B))))) { 2597 I.setOperand(0, A); 2598 I.setOperand(1, B); 2599 return &I; 2600 } 2601 2602 // For the remaining cases we need to get rid of one of the operands. 2603 if (!Op0->hasOneUse() && !Op1->hasOneUse()) 2604 return nullptr; 2605 2606 // (A | B) ^ ~(A & B) -> ~(A ^ B) 2607 // (A | B) ^ ~(B & A) -> ~(A ^ B) 2608 // (A & B) ^ ~(A | B) -> ~(A ^ B) 2609 // (A & B) ^ ~(B | A) -> ~(A ^ B) 2610 // Complexity sorting ensures the not will be on the right side. 2611 if ((match(Op0, m_Or(m_Value(A), m_Value(B))) && 2612 match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) || 2613 (match(Op0, m_And(m_Value(A), m_Value(B))) && 2614 match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))) 2615 return BinaryOperator::CreateNot(Builder.CreateXor(A, B)); 2616 2617 return nullptr; 2618 } 2619 2620 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) { 2621 if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) { 2622 if (LHS->getOperand(0) == RHS->getOperand(1) && 2623 LHS->getOperand(1) == RHS->getOperand(0)) 2624 LHS->swapOperands(); 2625 if (LHS->getOperand(0) == RHS->getOperand(0) && 2626 LHS->getOperand(1) == RHS->getOperand(1)) { 2627 // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B) 2628 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 2629 unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS); 2630 bool IsSigned = LHS->isSigned() || RHS->isSigned(); 2631 return getNewICmpValue(Code, IsSigned, Op0, Op1, Builder); 2632 } 2633 } 2634 2635 // TODO: This can be generalized to compares of non-signbits using 2636 // decomposeBitTestICmp(). It could be enhanced more by using (something like) 2637 // foldLogOpOfMaskedICmps(). 2638 ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); 2639 Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1); 2640 Value *RHS0 = RHS->getOperand(0), *RHS1 = RHS->getOperand(1); 2641 if ((LHS->hasOneUse() || RHS->hasOneUse()) && 2642 LHS0->getType() == RHS0->getType() && 2643 LHS0->getType()->isIntOrIntVectorTy()) { 2644 // (X > -1) ^ (Y > -1) --> (X ^ Y) < 0 2645 // (X < 0) ^ (Y < 0) --> (X ^ Y) < 0 2646 if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) && 2647 PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes())) || 2648 (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) && 2649 PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero()))) { 2650 Value *Zero = ConstantInt::getNullValue(LHS0->getType()); 2651 return Builder.CreateICmpSLT(Builder.CreateXor(LHS0, RHS0), Zero); 2652 } 2653 // (X > -1) ^ (Y < 0) --> (X ^ Y) > -1 2654 // (X < 0) ^ (Y > -1) --> (X ^ Y) > -1 2655 if ((PredL == CmpInst::ICMP_SGT && match(LHS1, m_AllOnes()) && 2656 PredR == CmpInst::ICMP_SLT && match(RHS1, m_Zero())) || 2657 (PredL == CmpInst::ICMP_SLT && match(LHS1, m_Zero()) && 2658 PredR == CmpInst::ICMP_SGT && match(RHS1, m_AllOnes()))) { 2659 Value *MinusOne = ConstantInt::getAllOnesValue(LHS0->getType()); 2660 return Builder.CreateICmpSGT(Builder.CreateXor(LHS0, RHS0), MinusOne); 2661 } 2662 } 2663 2664 // Instead of trying to imitate the folds for and/or, decompose this 'xor' 2665 // into those logic ops. That is, try to turn this into an and-of-icmps 2666 // because we have many folds for that pattern. 2667 // 2668 // This is based on a truth table definition of xor: 2669 // X ^ Y --> (X | Y) & !(X & Y) 2670 if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) { 2671 // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y). 2672 // TODO: If OrICmp is false, the whole thing is false (InstSimplify?). 2673 if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) { 2674 // TODO: Independently handle cases where the 'and' side is a constant. 2675 if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) { 2676 // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS 2677 RHS->setPredicate(RHS->getInversePredicate()); 2678 return Builder.CreateAnd(LHS, RHS); 2679 } 2680 if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) { 2681 // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS 2682 LHS->setPredicate(LHS->getInversePredicate()); 2683 return Builder.CreateAnd(LHS, RHS); 2684 } 2685 } 2686 } 2687 2688 return nullptr; 2689 } 2690 2691 /// If we have a masked merge, in the canonical form of: 2692 /// (assuming that A only has one use.) 2693 /// | A | |B| 2694 /// ((x ^ y) & M) ^ y 2695 /// | D | 2696 /// * If M is inverted: 2697 /// | D | 2698 /// ((x ^ y) & ~M) ^ y 2699 /// We can canonicalize by swapping the final xor operand 2700 /// to eliminate the 'not' of the mask. 2701 /// ((x ^ y) & M) ^ x 2702 /// * If M is a constant, and D has one use, we transform to 'and' / 'or' ops 2703 /// because that shortens the dependency chain and improves analysis: 2704 /// (x & M) | (y & ~M) 2705 static Instruction *visitMaskedMerge(BinaryOperator &I, 2706 InstCombiner::BuilderTy &Builder) { 2707 Value *B, *X, *D; 2708 Value *M; 2709 if (!match(&I, m_c_Xor(m_Value(B), 2710 m_OneUse(m_c_And( 2711 m_CombineAnd(m_c_Xor(m_Deferred(B), m_Value(X)), 2712 m_Value(D)), 2713 m_Value(M)))))) 2714 return nullptr; 2715 2716 Value *NotM; 2717 if (match(M, m_Not(m_Value(NotM)))) { 2718 // De-invert the mask and swap the value in B part. 2719 Value *NewA = Builder.CreateAnd(D, NotM); 2720 return BinaryOperator::CreateXor(NewA, X); 2721 } 2722 2723 Constant *C; 2724 if (D->hasOneUse() && match(M, m_Constant(C))) { 2725 // Unfold. 2726 Value *LHS = Builder.CreateAnd(X, C); 2727 Value *NotC = Builder.CreateNot(C); 2728 Value *RHS = Builder.CreateAnd(B, NotC); 2729 return BinaryOperator::CreateOr(LHS, RHS); 2730 } 2731 2732 return nullptr; 2733 } 2734 2735 // Transform 2736 // ~(x ^ y) 2737 // into: 2738 // (~x) ^ y 2739 // or into 2740 // x ^ (~y) 2741 static Instruction *sinkNotIntoXor(BinaryOperator &I, 2742 InstCombiner::BuilderTy &Builder) { 2743 Value *X, *Y; 2744 // FIXME: one-use check is not needed in general, but currently we are unable 2745 // to fold 'not' into 'icmp', if that 'icmp' has multiple uses. (D35182) 2746 if (!match(&I, m_Not(m_OneUse(m_Xor(m_Value(X), m_Value(Y)))))) 2747 return nullptr; 2748 2749 // We only want to do the transform if it is free to do. 2750 if (IsFreeToInvert(X, X->hasOneUse())) { 2751 // Ok, good. 2752 } else if (IsFreeToInvert(Y, Y->hasOneUse())) { 2753 std::swap(X, Y); 2754 } else 2755 return nullptr; 2756 2757 Value *NotX = Builder.CreateNot(X, X->getName() + ".not"); 2758 return BinaryOperator::CreateXor(NotX, Y, I.getName() + ".demorgan"); 2759 } 2760 2761 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches 2762 // here. We should standardize that construct where it is needed or choose some 2763 // other way to ensure that commutated variants of patterns are not missed. 2764 Instruction *InstCombiner::visitXor(BinaryOperator &I) { 2765 if (Value *V = SimplifyXorInst(I.getOperand(0), I.getOperand(1), 2766 SQ.getWithInstruction(&I))) 2767 return replaceInstUsesWith(I, V); 2768 2769 if (SimplifyAssociativeOrCommutative(I)) 2770 return &I; 2771 2772 if (Instruction *X = foldVectorBinop(I)) 2773 return X; 2774 2775 if (Instruction *NewXor = foldXorToXor(I, Builder)) 2776 return NewXor; 2777 2778 // (A&B)^(A&C) -> A&(B^C) etc 2779 if (Value *V = SimplifyUsingDistributiveLaws(I)) 2780 return replaceInstUsesWith(I, V); 2781 2782 // See if we can simplify any instructions used by the instruction whose sole 2783 // purpose is to compute bits we don't care about. 2784 if (SimplifyDemandedInstructionBits(I)) 2785 return &I; 2786 2787 if (Value *V = SimplifyBSwap(I, Builder)) 2788 return replaceInstUsesWith(I, V); 2789 2790 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2791 2792 // Fold (X & M) ^ (Y & ~M) -> (X & M) | (Y & ~M) 2793 // This it a special case in haveNoCommonBitsSet, but the computeKnownBits 2794 // calls in there are unnecessary as SimplifyDemandedInstructionBits should 2795 // have already taken care of those cases. 2796 Value *M; 2797 if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(M)), m_Value()), 2798 m_c_And(m_Deferred(M), m_Value())))) 2799 return BinaryOperator::CreateOr(Op0, Op1); 2800 2801 // Apply DeMorgan's Law for 'nand' / 'nor' logic with an inverted operand. 2802 Value *X, *Y; 2803 2804 // We must eliminate the and/or (one-use) for these transforms to not increase 2805 // the instruction count. 2806 // ~(~X & Y) --> (X | ~Y) 2807 // ~(Y & ~X) --> (X | ~Y) 2808 if (match(&I, m_Not(m_OneUse(m_c_And(m_Not(m_Value(X)), m_Value(Y)))))) { 2809 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not"); 2810 return BinaryOperator::CreateOr(X, NotY); 2811 } 2812 // ~(~X | Y) --> (X & ~Y) 2813 // ~(Y | ~X) --> (X & ~Y) 2814 if (match(&I, m_Not(m_OneUse(m_c_Or(m_Not(m_Value(X)), m_Value(Y)))))) { 2815 Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not"); 2816 return BinaryOperator::CreateAnd(X, NotY); 2817 } 2818 2819 if (Instruction *Xor = visitMaskedMerge(I, Builder)) 2820 return Xor; 2821 2822 // Is this a 'not' (~) fed by a binary operator? 2823 BinaryOperator *NotVal; 2824 if (match(&I, m_Not(m_BinOp(NotVal)))) { 2825 if (NotVal->getOpcode() == Instruction::And || 2826 NotVal->getOpcode() == Instruction::Or) { 2827 // Apply DeMorgan's Law when inverts are free: 2828 // ~(X & Y) --> (~X | ~Y) 2829 // ~(X | Y) --> (~X & ~Y) 2830 if (IsFreeToInvert(NotVal->getOperand(0), 2831 NotVal->getOperand(0)->hasOneUse()) && 2832 IsFreeToInvert(NotVal->getOperand(1), 2833 NotVal->getOperand(1)->hasOneUse())) { 2834 Value *NotX = Builder.CreateNot(NotVal->getOperand(0), "notlhs"); 2835 Value *NotY = Builder.CreateNot(NotVal->getOperand(1), "notrhs"); 2836 if (NotVal->getOpcode() == Instruction::And) 2837 return BinaryOperator::CreateOr(NotX, NotY); 2838 return BinaryOperator::CreateAnd(NotX, NotY); 2839 } 2840 } 2841 2842 // ~(X - Y) --> ~X + Y 2843 if (match(NotVal, m_Sub(m_Value(X), m_Value(Y)))) 2844 if (isa<Constant>(X) || NotVal->hasOneUse()) 2845 return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y); 2846 2847 // ~(~X >>s Y) --> (X >>s Y) 2848 if (match(NotVal, m_AShr(m_Not(m_Value(X)), m_Value(Y)))) 2849 return BinaryOperator::CreateAShr(X, Y); 2850 2851 // If we are inverting a right-shifted constant, we may be able to eliminate 2852 // the 'not' by inverting the constant and using the opposite shift type. 2853 // Canonicalization rules ensure that only a negative constant uses 'ashr', 2854 // but we must check that in case that transform has not fired yet. 2855 2856 // ~(C >>s Y) --> ~C >>u Y (when inverting the replicated sign bits) 2857 Constant *C; 2858 if (match(NotVal, m_AShr(m_Constant(C), m_Value(Y))) && 2859 match(C, m_Negative())) 2860 return BinaryOperator::CreateLShr(ConstantExpr::getNot(C), Y); 2861 2862 // ~(C >>u Y) --> ~C >>s Y (when inverting the replicated sign bits) 2863 if (match(NotVal, m_LShr(m_Constant(C), m_Value(Y))) && 2864 match(C, m_NonNegative())) 2865 return BinaryOperator::CreateAShr(ConstantExpr::getNot(C), Y); 2866 2867 // ~(X + C) --> -(C + 1) - X 2868 if (match(Op0, m_Add(m_Value(X), m_Constant(C)))) 2869 return BinaryOperator::CreateSub(ConstantExpr::getNeg(AddOne(C)), X); 2870 } 2871 2872 // Use DeMorgan and reassociation to eliminate a 'not' op. 2873 Constant *C1; 2874 if (match(Op1, m_Constant(C1))) { 2875 Constant *C2; 2876 if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) { 2877 // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1 2878 Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2)); 2879 return BinaryOperator::CreateXor(And, ConstantExpr::getNot(C1)); 2880 } 2881 if (match(Op0, m_OneUse(m_And(m_Not(m_Value(X)), m_Constant(C2))))) { 2882 // (~X & C2) ^ C1 --> ((X | ~C2) ^ -1) ^ C1 --> (X | ~C2) ^ ~C1 2883 Value *Or = Builder.CreateOr(X, ConstantExpr::getNot(C2)); 2884 return BinaryOperator::CreateXor(Or, ConstantExpr::getNot(C1)); 2885 } 2886 } 2887 2888 // not (cmp A, B) = !cmp A, B 2889 CmpInst::Predicate Pred; 2890 if (match(&I, m_Not(m_OneUse(m_Cmp(Pred, m_Value(), m_Value()))))) { 2891 cast<CmpInst>(Op0)->setPredicate(CmpInst::getInversePredicate(Pred)); 2892 return replaceInstUsesWith(I, Op0); 2893 } 2894 2895 { 2896 const APInt *RHSC; 2897 if (match(Op1, m_APInt(RHSC))) { 2898 Value *X; 2899 const APInt *C; 2900 if (RHSC->isSignMask() && match(Op0, m_Sub(m_APInt(C), m_Value(X)))) { 2901 // (C - X) ^ signmask -> (C + signmask - X) 2902 Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); 2903 return BinaryOperator::CreateSub(NewC, X); 2904 } 2905 if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C)))) { 2906 // (X + C) ^ signmask -> (X + C + signmask) 2907 Constant *NewC = ConstantInt::get(I.getType(), *C + *RHSC); 2908 return BinaryOperator::CreateAdd(X, NewC); 2909 } 2910 2911 // (X|C1)^C2 -> X^(C1^C2) iff X&~C1 == 0 2912 if (match(Op0, m_Or(m_Value(X), m_APInt(C))) && 2913 MaskedValueIsZero(X, *C, 0, &I)) { 2914 Constant *NewC = ConstantInt::get(I.getType(), *C ^ *RHSC); 2915 Worklist.Add(cast<Instruction>(Op0)); 2916 I.setOperand(0, X); 2917 I.setOperand(1, NewC); 2918 return &I; 2919 } 2920 } 2921 } 2922 2923 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) { 2924 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 2925 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) { 2926 if (Op0I->getOpcode() == Instruction::LShr) { 2927 // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3) 2928 // E1 = "X ^ C1" 2929 BinaryOperator *E1; 2930 ConstantInt *C1; 2931 if (Op0I->hasOneUse() && 2932 (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) && 2933 E1->getOpcode() == Instruction::Xor && 2934 (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) { 2935 // fold (C1 >> C2) ^ C3 2936 ConstantInt *C2 = Op0CI, *C3 = RHSC; 2937 APInt FoldConst = C1->getValue().lshr(C2->getValue()); 2938 FoldConst ^= C3->getValue(); 2939 // Prepare the two operands. 2940 Value *Opnd0 = Builder.CreateLShr(E1->getOperand(0), C2); 2941 Opnd0->takeName(Op0I); 2942 cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc()); 2943 Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst); 2944 2945 return BinaryOperator::CreateXor(Opnd0, FoldVal); 2946 } 2947 } 2948 } 2949 } 2950 } 2951 2952 if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) 2953 return FoldedLogic; 2954 2955 // Y ^ (X | Y) --> X & ~Y 2956 // Y ^ (Y | X) --> X & ~Y 2957 if (match(Op1, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op0))))) 2958 return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op0)); 2959 // (X | Y) ^ Y --> X & ~Y 2960 // (Y | X) ^ Y --> X & ~Y 2961 if (match(Op0, m_OneUse(m_c_Or(m_Value(X), m_Specific(Op1))))) 2962 return BinaryOperator::CreateAnd(X, Builder.CreateNot(Op1)); 2963 2964 // Y ^ (X & Y) --> ~X & Y 2965 // Y ^ (Y & X) --> ~X & Y 2966 if (match(Op1, m_OneUse(m_c_And(m_Value(X), m_Specific(Op0))))) 2967 return BinaryOperator::CreateAnd(Op0, Builder.CreateNot(X)); 2968 // (X & Y) ^ Y --> ~X & Y 2969 // (Y & X) ^ Y --> ~X & Y 2970 // Canonical form is (X & C) ^ C; don't touch that. 2971 // TODO: A 'not' op is better for analysis and codegen, but demanded bits must 2972 // be fixed to prefer that (otherwise we get infinite looping). 2973 if (!match(Op1, m_Constant()) && 2974 match(Op0, m_OneUse(m_c_And(m_Value(X), m_Specific(Op1))))) 2975 return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(X)); 2976 2977 Value *A, *B, *C; 2978 // (A ^ B) ^ (A | C) --> (~A & C) ^ B -- There are 4 commuted variants. 2979 if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))), 2980 m_OneUse(m_c_Or(m_Deferred(A), m_Value(C)))))) 2981 return BinaryOperator::CreateXor( 2982 Builder.CreateAnd(Builder.CreateNot(A), C), B); 2983 2984 // (A ^ B) ^ (B | C) --> (~B & C) ^ A -- There are 4 commuted variants. 2985 if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_Value(A), m_Value(B))), 2986 m_OneUse(m_c_Or(m_Deferred(B), m_Value(C)))))) 2987 return BinaryOperator::CreateXor( 2988 Builder.CreateAnd(Builder.CreateNot(B), C), A); 2989 2990 // (A & B) ^ (A ^ B) -> (A | B) 2991 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 2992 match(Op1, m_c_Xor(m_Specific(A), m_Specific(B)))) 2993 return BinaryOperator::CreateOr(A, B); 2994 // (A ^ B) ^ (A & B) -> (A | B) 2995 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && 2996 match(Op1, m_c_And(m_Specific(A), m_Specific(B)))) 2997 return BinaryOperator::CreateOr(A, B); 2998 2999 // (A & ~B) ^ ~A -> ~(A & B) 3000 // (~B & A) ^ ~A -> ~(A & B) 3001 if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) && 3002 match(Op1, m_Not(m_Specific(A)))) 3003 return BinaryOperator::CreateNot(Builder.CreateAnd(A, B)); 3004 3005 if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0))) 3006 if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1))) 3007 if (Value *V = foldXorOfICmps(LHS, RHS)) 3008 return replaceInstUsesWith(I, V); 3009 3010 if (Instruction *CastedXor = foldCastedBitwiseLogic(I)) 3011 return CastedXor; 3012 3013 // Canonicalize a shifty way to code absolute value to the common pattern. 3014 // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1. 3015 // We're relying on the fact that we only do this transform when the shift has 3016 // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase 3017 // instructions). 3018 if (Op0->hasNUses(2)) 3019 std::swap(Op0, Op1); 3020 3021 const APInt *ShAmt; 3022 Type *Ty = I.getType(); 3023 if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) && 3024 Op1->hasNUses(2) && *ShAmt == Ty->getScalarSizeInBits() - 1 && 3025 match(Op0, m_OneUse(m_c_Add(m_Specific(A), m_Specific(Op1))))) { 3026 // B = ashr i32 A, 31 ; smear the sign bit 3027 // xor (add A, B), B ; add -1 and flip bits if negative 3028 // --> (A < 0) ? -A : A 3029 Value *Cmp = Builder.CreateICmpSLT(A, ConstantInt::getNullValue(Ty)); 3030 // Copy the nuw/nsw flags from the add to the negate. 3031 auto *Add = cast<BinaryOperator>(Op0); 3032 Value *Neg = Builder.CreateNeg(A, "", Add->hasNoUnsignedWrap(), 3033 Add->hasNoSignedWrap()); 3034 return SelectInst::Create(Cmp, Neg, A); 3035 } 3036 3037 // Eliminate a bitwise 'not' op of 'not' min/max by inverting the min/max: 3038 // 3039 // %notx = xor i32 %x, -1 3040 // %cmp1 = icmp sgt i32 %notx, %y 3041 // %smax = select i1 %cmp1, i32 %notx, i32 %y 3042 // %res = xor i32 %smax, -1 3043 // => 3044 // %noty = xor i32 %y, -1 3045 // %cmp2 = icmp slt %x, %noty 3046 // %res = select i1 %cmp2, i32 %x, i32 %noty 3047 // 3048 // Same is applicable for smin/umax/umin. 3049 if (match(Op1, m_AllOnes()) && Op0->hasOneUse()) { 3050 Value *LHS, *RHS; 3051 SelectPatternFlavor SPF = matchSelectPattern(Op0, LHS, RHS).Flavor; 3052 if (SelectPatternResult::isMinOrMax(SPF)) { 3053 // It's possible we get here before the not has been simplified, so make 3054 // sure the input to the not isn't freely invertible. 3055 if (match(LHS, m_Not(m_Value(X))) && !IsFreeToInvert(X, X->hasOneUse())) { 3056 Value *NotY = Builder.CreateNot(RHS); 3057 return SelectInst::Create( 3058 Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY); 3059 } 3060 3061 // It's possible we get here before the not has been simplified, so make 3062 // sure the input to the not isn't freely invertible. 3063 if (match(RHS, m_Not(m_Value(Y))) && !IsFreeToInvert(Y, Y->hasOneUse())) { 3064 Value *NotX = Builder.CreateNot(LHS); 3065 return SelectInst::Create( 3066 Builder.CreateICmp(getInverseMinMaxPred(SPF), NotX, Y), NotX, Y); 3067 } 3068 3069 // If both sides are freely invertible, then we can get rid of the xor 3070 // completely. 3071 if (IsFreeToInvert(LHS, !LHS->hasNUsesOrMore(3)) && 3072 IsFreeToInvert(RHS, !RHS->hasNUsesOrMore(3))) { 3073 Value *NotLHS = Builder.CreateNot(LHS); 3074 Value *NotRHS = Builder.CreateNot(RHS); 3075 return SelectInst::Create( 3076 Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS), 3077 NotLHS, NotRHS); 3078 } 3079 } 3080 } 3081 3082 if (Instruction *NewXor = sinkNotIntoXor(I, Builder)) 3083 return NewXor; 3084 3085 return nullptr; 3086 } 3087