1 //===- InstCombineAndOrXor.cpp --------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the visitAnd, visitOr, and visitXor functions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "InstCombineInternal.h" 15 #include "llvm/Analysis/InstructionSimplify.h" 16 #include "llvm/IR/ConstantRange.h" 17 #include "llvm/IR/Intrinsics.h" 18 #include "llvm/IR/PatternMatch.h" 19 #include "llvm/Transforms/Utils/CmpInstAnalysis.h" 20 using namespace llvm; 21 using namespace PatternMatch; 22 23 #define DEBUG_TYPE "instcombine" 24 25 static inline Value *dyn_castNotVal(Value *V) { 26 // If this is not(not(x)) don't return that this is a not: we want the two 27 // not's to be folded first. 28 if (BinaryOperator::isNot(V)) { 29 Value *Operand = BinaryOperator::getNotArgument(V); 30 if (!IsFreeToInvert(Operand, Operand->hasOneUse())) 31 return Operand; 32 } 33 34 // Constants can be considered to be not'ed values... 35 if (ConstantInt *C = dyn_cast<ConstantInt>(V)) 36 return ConstantInt::get(C->getType(), ~C->getValue()); 37 return nullptr; 38 } 39 40 /// getFCmpCode - Similar to getICmpCode but for FCmpInst. This encodes a fcmp 41 /// predicate into a three bit mask. It also returns whether it is an ordered 42 /// predicate by reference. 43 static unsigned getFCmpCode(FCmpInst::Predicate CC, bool &isOrdered) { 44 isOrdered = false; 45 switch (CC) { 46 case FCmpInst::FCMP_ORD: isOrdered = true; return 0; // 000 47 case FCmpInst::FCMP_UNO: return 0; // 000 48 case FCmpInst::FCMP_OGT: isOrdered = true; return 1; // 001 49 case FCmpInst::FCMP_UGT: return 1; // 001 50 case FCmpInst::FCMP_OEQ: isOrdered = true; return 2; // 010 51 case FCmpInst::FCMP_UEQ: return 2; // 010 52 case FCmpInst::FCMP_OGE: isOrdered = true; return 3; // 011 53 case FCmpInst::FCMP_UGE: return 3; // 011 54 case FCmpInst::FCMP_OLT: isOrdered = true; return 4; // 100 55 case FCmpInst::FCMP_ULT: return 4; // 100 56 case FCmpInst::FCMP_ONE: isOrdered = true; return 5; // 101 57 case FCmpInst::FCMP_UNE: return 5; // 101 58 case FCmpInst::FCMP_OLE: isOrdered = true; return 6; // 110 59 case FCmpInst::FCMP_ULE: return 6; // 110 60 // True -> 7 61 default: 62 // Not expecting FCMP_FALSE and FCMP_TRUE; 63 llvm_unreachable("Unexpected FCmp predicate!"); 64 } 65 } 66 67 /// getNewICmpValue - This is the complement of getICmpCode, which turns an 68 /// opcode and two operands into either a constant true or false, or a brand 69 /// new ICmp instruction. The sign is passed in to determine which kind 70 /// of predicate to use in the new icmp instruction. 71 static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, 72 InstCombiner::BuilderTy *Builder) { 73 ICmpInst::Predicate NewPred; 74 if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred)) 75 return NewConstant; 76 return Builder->CreateICmp(NewPred, LHS, RHS); 77 } 78 79 /// getFCmpValue - This is the complement of getFCmpCode, which turns an 80 /// opcode and two operands into either a FCmp instruction. isordered is passed 81 /// in to determine which kind of predicate to use in the new fcmp instruction. 82 static Value *getFCmpValue(bool isordered, unsigned code, 83 Value *LHS, Value *RHS, 84 InstCombiner::BuilderTy *Builder) { 85 CmpInst::Predicate Pred; 86 switch (code) { 87 default: llvm_unreachable("Illegal FCmp code!"); 88 case 0: Pred = isordered ? FCmpInst::FCMP_ORD : FCmpInst::FCMP_UNO; break; 89 case 1: Pred = isordered ? FCmpInst::FCMP_OGT : FCmpInst::FCMP_UGT; break; 90 case 2: Pred = isordered ? FCmpInst::FCMP_OEQ : FCmpInst::FCMP_UEQ; break; 91 case 3: Pred = isordered ? FCmpInst::FCMP_OGE : FCmpInst::FCMP_UGE; break; 92 case 4: Pred = isordered ? FCmpInst::FCMP_OLT : FCmpInst::FCMP_ULT; break; 93 case 5: Pred = isordered ? FCmpInst::FCMP_ONE : FCmpInst::FCMP_UNE; break; 94 case 6: Pred = isordered ? FCmpInst::FCMP_OLE : FCmpInst::FCMP_ULE; break; 95 case 7: 96 if (!isordered) return ConstantInt::getTrue(LHS->getContext()); 97 Pred = FCmpInst::FCMP_ORD; break; 98 } 99 return Builder->CreateFCmp(Pred, LHS, RHS); 100 } 101 102 /// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) to BSWAP(BITWISE_OP(A, B)) 103 /// \param I Binary operator to transform. 104 /// \return Pointer to node that must replace the original binary operator, or 105 /// null pointer if no transformation was made. 106 Value *InstCombiner::SimplifyBSwap(BinaryOperator &I) { 107 IntegerType *ITy = dyn_cast<IntegerType>(I.getType()); 108 109 // Can't do vectors. 110 if (I.getType()->isVectorTy()) return nullptr; 111 112 // Can only do bitwise ops. 113 unsigned Op = I.getOpcode(); 114 if (Op != Instruction::And && Op != Instruction::Or && 115 Op != Instruction::Xor) 116 return nullptr; 117 118 Value *OldLHS = I.getOperand(0); 119 Value *OldRHS = I.getOperand(1); 120 ConstantInt *ConstLHS = dyn_cast<ConstantInt>(OldLHS); 121 ConstantInt *ConstRHS = dyn_cast<ConstantInt>(OldRHS); 122 IntrinsicInst *IntrLHS = dyn_cast<IntrinsicInst>(OldLHS); 123 IntrinsicInst *IntrRHS = dyn_cast<IntrinsicInst>(OldRHS); 124 bool IsBswapLHS = (IntrLHS && IntrLHS->getIntrinsicID() == Intrinsic::bswap); 125 bool IsBswapRHS = (IntrRHS && IntrRHS->getIntrinsicID() == Intrinsic::bswap); 126 127 if (!IsBswapLHS && !IsBswapRHS) 128 return nullptr; 129 130 if (!IsBswapLHS && !ConstLHS) 131 return nullptr; 132 133 if (!IsBswapRHS && !ConstRHS) 134 return nullptr; 135 136 /// OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) ) 137 /// OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) ) 138 Value *NewLHS = IsBswapLHS ? IntrLHS->getOperand(0) : 139 Builder->getInt(ConstLHS->getValue().byteSwap()); 140 141 Value *NewRHS = IsBswapRHS ? IntrRHS->getOperand(0) : 142 Builder->getInt(ConstRHS->getValue().byteSwap()); 143 144 Value *BinOp = nullptr; 145 if (Op == Instruction::And) 146 BinOp = Builder->CreateAnd(NewLHS, NewRHS); 147 else if (Op == Instruction::Or) 148 BinOp = Builder->CreateOr(NewLHS, NewRHS); 149 else //if (Op == Instruction::Xor) 150 BinOp = Builder->CreateXor(NewLHS, NewRHS); 151 152 Module *M = I.getParent()->getParent()->getParent(); 153 Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, ITy); 154 return Builder->CreateCall(F, BinOp); 155 } 156 157 // OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where 158 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is 159 // guaranteed to be a binary operator. 160 Instruction *InstCombiner::OptAndOp(Instruction *Op, 161 ConstantInt *OpRHS, 162 ConstantInt *AndRHS, 163 BinaryOperator &TheAnd) { 164 Value *X = Op->getOperand(0); 165 Constant *Together = nullptr; 166 if (!Op->isShift()) 167 Together = ConstantExpr::getAnd(AndRHS, OpRHS); 168 169 switch (Op->getOpcode()) { 170 case Instruction::Xor: 171 if (Op->hasOneUse()) { 172 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) 173 Value *And = Builder->CreateAnd(X, AndRHS); 174 And->takeName(Op); 175 return BinaryOperator::CreateXor(And, Together); 176 } 177 break; 178 case Instruction::Or: 179 if (Op->hasOneUse()){ 180 if (Together != OpRHS) { 181 // (X | C1) & C2 --> (X | (C1&C2)) & C2 182 Value *Or = Builder->CreateOr(X, Together); 183 Or->takeName(Op); 184 return BinaryOperator::CreateAnd(Or, AndRHS); 185 } 186 187 ConstantInt *TogetherCI = dyn_cast<ConstantInt>(Together); 188 if (TogetherCI && !TogetherCI->isZero()){ 189 // (X | C1) & C2 --> (X & (C2^(C1&C2))) | C1 190 // NOTE: This reduces the number of bits set in the & mask, which 191 // can expose opportunities for store narrowing. 192 Together = ConstantExpr::getXor(AndRHS, Together); 193 Value *And = Builder->CreateAnd(X, Together); 194 And->takeName(Op); 195 return BinaryOperator::CreateOr(And, OpRHS); 196 } 197 } 198 199 break; 200 case Instruction::Add: 201 if (Op->hasOneUse()) { 202 // Adding a one to a single bit bit-field should be turned into an XOR 203 // of the bit. First thing to check is to see if this AND is with a 204 // single bit constant. 205 const APInt &AndRHSV = AndRHS->getValue(); 206 207 // If there is only one bit set. 208 if (AndRHSV.isPowerOf2()) { 209 // Ok, at this point, we know that we are masking the result of the 210 // ADD down to exactly one bit. If the constant we are adding has 211 // no bits set below this bit, then we can eliminate the ADD. 212 const APInt& AddRHS = OpRHS->getValue(); 213 214 // Check to see if any bits below the one bit set in AndRHSV are set. 215 if ((AddRHS & (AndRHSV-1)) == 0) { 216 // If not, the only thing that can effect the output of the AND is 217 // the bit specified by AndRHSV. If that bit is set, the effect of 218 // the XOR is to toggle the bit. If it is clear, then the ADD has 219 // no effect. 220 if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop 221 TheAnd.setOperand(0, X); 222 return &TheAnd; 223 } else { 224 // Pull the XOR out of the AND. 225 Value *NewAnd = Builder->CreateAnd(X, AndRHS); 226 NewAnd->takeName(Op); 227 return BinaryOperator::CreateXor(NewAnd, AndRHS); 228 } 229 } 230 } 231 } 232 break; 233 234 case Instruction::Shl: { 235 // We know that the AND will not produce any of the bits shifted in, so if 236 // the anded constant includes them, clear them now! 237 // 238 uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 239 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 240 APInt ShlMask(APInt::getHighBitsSet(BitWidth, BitWidth-OpRHSVal)); 241 ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShlMask); 242 243 if (CI->getValue() == ShlMask) 244 // Masking out bits that the shift already masks. 245 return ReplaceInstUsesWith(TheAnd, Op); // No need for the and. 246 247 if (CI != AndRHS) { // Reducing bits set in and. 248 TheAnd.setOperand(1, CI); 249 return &TheAnd; 250 } 251 break; 252 } 253 case Instruction::LShr: { 254 // We know that the AND will not produce any of the bits shifted in, so if 255 // the anded constant includes them, clear them now! This only applies to 256 // unsigned shifts, because a signed shr may bring in set bits! 257 // 258 uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 259 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 260 APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal)); 261 ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShrMask); 262 263 if (CI->getValue() == ShrMask) 264 // Masking out bits that the shift already masks. 265 return ReplaceInstUsesWith(TheAnd, Op); 266 267 if (CI != AndRHS) { 268 TheAnd.setOperand(1, CI); // Reduce bits set in and cst. 269 return &TheAnd; 270 } 271 break; 272 } 273 case Instruction::AShr: 274 // Signed shr. 275 // See if this is shifting in some sign extension, then masking it out 276 // with an and. 277 if (Op->hasOneUse()) { 278 uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 279 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 280 APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal)); 281 Constant *C = Builder->getInt(AndRHS->getValue() & ShrMask); 282 if (C == AndRHS) { // Masking out bits shifted in. 283 // (Val ashr C1) & C2 -> (Val lshr C1) & C2 284 // Make the argument unsigned. 285 Value *ShVal = Op->getOperand(0); 286 ShVal = Builder->CreateLShr(ShVal, OpRHS, Op->getName()); 287 return BinaryOperator::CreateAnd(ShVal, AndRHS, TheAnd.getName()); 288 } 289 } 290 break; 291 } 292 return nullptr; 293 } 294 295 /// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise 296 /// (V < Lo || V >= Hi). In practice, we emit the more efficient 297 /// (V-Lo) \<u Hi-Lo. This method expects that Lo <= Hi. isSigned indicates 298 /// whether to treat the V, Lo and HI as signed or not. IB is the location to 299 /// insert new instructions. 300 Value *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, 301 bool isSigned, bool Inside) { 302 assert(cast<ConstantInt>(ConstantExpr::getICmp((isSigned ? 303 ICmpInst::ICMP_SLE:ICmpInst::ICMP_ULE), Lo, Hi))->getZExtValue() && 304 "Lo is not <= Hi in range emission code!"); 305 306 if (Inside) { 307 if (Lo == Hi) // Trivially false. 308 return Builder->getFalse(); 309 310 // V >= Min && V < Hi --> V < Hi 311 if (cast<ConstantInt>(Lo)->isMinValue(isSigned)) { 312 ICmpInst::Predicate pred = (isSigned ? 313 ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT); 314 return Builder->CreateICmp(pred, V, Hi); 315 } 316 317 // Emit V-Lo <u Hi-Lo 318 Constant *NegLo = ConstantExpr::getNeg(Lo); 319 Value *Add = Builder->CreateAdd(V, NegLo, V->getName()+".off"); 320 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Hi); 321 return Builder->CreateICmpULT(Add, UpperBound); 322 } 323 324 if (Lo == Hi) // Trivially true. 325 return Builder->getTrue(); 326 327 // V < Min || V >= Hi -> V > Hi-1 328 Hi = SubOne(cast<ConstantInt>(Hi)); 329 if (cast<ConstantInt>(Lo)->isMinValue(isSigned)) { 330 ICmpInst::Predicate pred = (isSigned ? 331 ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT); 332 return Builder->CreateICmp(pred, V, Hi); 333 } 334 335 // Emit V-Lo >u Hi-1-Lo 336 // Note that Hi has already had one subtracted from it, above. 337 ConstantInt *NegLo = cast<ConstantInt>(ConstantExpr::getNeg(Lo)); 338 Value *Add = Builder->CreateAdd(V, NegLo, V->getName()+".off"); 339 Constant *LowerBound = ConstantExpr::getAdd(NegLo, Hi); 340 return Builder->CreateICmpUGT(Add, LowerBound); 341 } 342 343 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with 344 // any number of 0s on either side. The 1s are allowed to wrap from LSB to 345 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is 346 // not, since all 1s are not contiguous. 347 static bool isRunOfOnes(ConstantInt *Val, uint32_t &MB, uint32_t &ME) { 348 const APInt& V = Val->getValue(); 349 uint32_t BitWidth = Val->getType()->getBitWidth(); 350 if (!APIntOps::isShiftedMask(BitWidth, V)) return false; 351 352 // look for the first zero bit after the run of ones 353 MB = BitWidth - ((V - 1) ^ V).countLeadingZeros(); 354 // look for the first non-zero bit 355 ME = V.getActiveBits(); 356 return true; 357 } 358 359 /// FoldLogicalPlusAnd - This is part of an expression (LHS +/- RHS) & Mask, 360 /// where isSub determines whether the operator is a sub. If we can fold one of 361 /// the following xforms: 362 /// 363 /// ((A & N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == Mask 364 /// ((A | N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0 365 /// ((A ^ N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0 366 /// 367 /// return (A +/- B). 368 /// 369 Value *InstCombiner::FoldLogicalPlusAnd(Value *LHS, Value *RHS, 370 ConstantInt *Mask, bool isSub, 371 Instruction &I) { 372 Instruction *LHSI = dyn_cast<Instruction>(LHS); 373 if (!LHSI || LHSI->getNumOperands() != 2 || 374 !isa<ConstantInt>(LHSI->getOperand(1))) return nullptr; 375 376 ConstantInt *N = cast<ConstantInt>(LHSI->getOperand(1)); 377 378 switch (LHSI->getOpcode()) { 379 default: return nullptr; 380 case Instruction::And: 381 if (ConstantExpr::getAnd(N, Mask) == Mask) { 382 // If the AndRHS is a power of two minus one (0+1+), this is simple. 383 if ((Mask->getValue().countLeadingZeros() + 384 Mask->getValue().countPopulation()) == 385 Mask->getValue().getBitWidth()) 386 break; 387 388 // Otherwise, if Mask is 0+1+0+, and if B is known to have the low 0+ 389 // part, we don't need any explicit masks to take them out of A. If that 390 // is all N is, ignore it. 391 uint32_t MB = 0, ME = 0; 392 if (isRunOfOnes(Mask, MB, ME)) { // begin/end bit of run, inclusive 393 uint32_t BitWidth = cast<IntegerType>(RHS->getType())->getBitWidth(); 394 APInt Mask(APInt::getLowBitsSet(BitWidth, MB-1)); 395 if (MaskedValueIsZero(RHS, Mask, 0, &I)) 396 break; 397 } 398 } 399 return nullptr; 400 case Instruction::Or: 401 case Instruction::Xor: 402 // If the AndRHS is a power of two minus one (0+1+), and N&Mask == 0 403 if ((Mask->getValue().countLeadingZeros() + 404 Mask->getValue().countPopulation()) == Mask->getValue().getBitWidth() 405 && ConstantExpr::getAnd(N, Mask)->isNullValue()) 406 break; 407 return nullptr; 408 } 409 410 if (isSub) 411 return Builder->CreateSub(LHSI->getOperand(0), RHS, "fold"); 412 return Builder->CreateAdd(LHSI->getOperand(0), RHS, "fold"); 413 } 414 415 /// enum for classifying (icmp eq (A & B), C) and (icmp ne (A & B), C) 416 /// One of A and B is considered the mask, the other the value. This is 417 /// described as the "AMask" or "BMask" part of the enum. If the enum 418 /// contains only "Mask", then both A and B can be considered masks. 419 /// If A is the mask, then it was proven, that (A & C) == C. This 420 /// is trivial if C == A, or C == 0. If both A and C are constants, this 421 /// proof is also easy. 422 /// For the following explanations we assume that A is the mask. 423 /// The part "AllOnes" declares, that the comparison is true only 424 /// if (A & B) == A, or all bits of A are set in B. 425 /// Example: (icmp eq (A & 3), 3) -> FoldMskICmp_AMask_AllOnes 426 /// The part "AllZeroes" declares, that the comparison is true only 427 /// if (A & B) == 0, or all bits of A are cleared in B. 428 /// Example: (icmp eq (A & 3), 0) -> FoldMskICmp_Mask_AllZeroes 429 /// The part "Mixed" declares, that (A & B) == C and C might or might not 430 /// contain any number of one bits and zero bits. 431 /// Example: (icmp eq (A & 3), 1) -> FoldMskICmp_AMask_Mixed 432 /// The Part "Not" means, that in above descriptions "==" should be replaced 433 /// by "!=". 434 /// Example: (icmp ne (A & 3), 3) -> FoldMskICmp_AMask_NotAllOnes 435 /// If the mask A contains a single bit, then the following is equivalent: 436 /// (icmp eq (A & B), A) equals (icmp ne (A & B), 0) 437 /// (icmp ne (A & B), A) equals (icmp eq (A & B), 0) 438 enum MaskedICmpType { 439 FoldMskICmp_AMask_AllOnes = 1, 440 FoldMskICmp_AMask_NotAllOnes = 2, 441 FoldMskICmp_BMask_AllOnes = 4, 442 FoldMskICmp_BMask_NotAllOnes = 8, 443 FoldMskICmp_Mask_AllZeroes = 16, 444 FoldMskICmp_Mask_NotAllZeroes = 32, 445 FoldMskICmp_AMask_Mixed = 64, 446 FoldMskICmp_AMask_NotMixed = 128, 447 FoldMskICmp_BMask_Mixed = 256, 448 FoldMskICmp_BMask_NotMixed = 512 449 }; 450 451 /// return the set of pattern classes (from MaskedICmpType) 452 /// that (icmp SCC (A & B), C) satisfies 453 static unsigned getTypeOfMaskedICmp(Value* A, Value* B, Value* C, 454 ICmpInst::Predicate SCC) 455 { 456 ConstantInt *ACst = dyn_cast<ConstantInt>(A); 457 ConstantInt *BCst = dyn_cast<ConstantInt>(B); 458 ConstantInt *CCst = dyn_cast<ConstantInt>(C); 459 bool icmp_eq = (SCC == ICmpInst::ICMP_EQ); 460 bool icmp_abit = (ACst && !ACst->isZero() && 461 ACst->getValue().isPowerOf2()); 462 bool icmp_bbit = (BCst && !BCst->isZero() && 463 BCst->getValue().isPowerOf2()); 464 unsigned result = 0; 465 if (CCst && CCst->isZero()) { 466 // if C is zero, then both A and B qualify as mask 467 result |= (icmp_eq ? (FoldMskICmp_Mask_AllZeroes | 468 FoldMskICmp_Mask_AllZeroes | 469 FoldMskICmp_AMask_Mixed | 470 FoldMskICmp_BMask_Mixed) 471 : (FoldMskICmp_Mask_NotAllZeroes | 472 FoldMskICmp_Mask_NotAllZeroes | 473 FoldMskICmp_AMask_NotMixed | 474 FoldMskICmp_BMask_NotMixed)); 475 if (icmp_abit) 476 result |= (icmp_eq ? (FoldMskICmp_AMask_NotAllOnes | 477 FoldMskICmp_AMask_NotMixed) 478 : (FoldMskICmp_AMask_AllOnes | 479 FoldMskICmp_AMask_Mixed)); 480 if (icmp_bbit) 481 result |= (icmp_eq ? (FoldMskICmp_BMask_NotAllOnes | 482 FoldMskICmp_BMask_NotMixed) 483 : (FoldMskICmp_BMask_AllOnes | 484 FoldMskICmp_BMask_Mixed)); 485 return result; 486 } 487 if (A == C) { 488 result |= (icmp_eq ? (FoldMskICmp_AMask_AllOnes | 489 FoldMskICmp_AMask_Mixed) 490 : (FoldMskICmp_AMask_NotAllOnes | 491 FoldMskICmp_AMask_NotMixed)); 492 if (icmp_abit) 493 result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes | 494 FoldMskICmp_AMask_NotMixed) 495 : (FoldMskICmp_Mask_AllZeroes | 496 FoldMskICmp_AMask_Mixed)); 497 } else if (ACst && CCst && 498 ConstantExpr::getAnd(ACst, CCst) == CCst) { 499 result |= (icmp_eq ? FoldMskICmp_AMask_Mixed 500 : FoldMskICmp_AMask_NotMixed); 501 } 502 if (B == C) { 503 result |= (icmp_eq ? (FoldMskICmp_BMask_AllOnes | 504 FoldMskICmp_BMask_Mixed) 505 : (FoldMskICmp_BMask_NotAllOnes | 506 FoldMskICmp_BMask_NotMixed)); 507 if (icmp_bbit) 508 result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes | 509 FoldMskICmp_BMask_NotMixed) 510 : (FoldMskICmp_Mask_AllZeroes | 511 FoldMskICmp_BMask_Mixed)); 512 } else if (BCst && CCst && 513 ConstantExpr::getAnd(BCst, CCst) == CCst) { 514 result |= (icmp_eq ? FoldMskICmp_BMask_Mixed 515 : FoldMskICmp_BMask_NotMixed); 516 } 517 return result; 518 } 519 520 /// Convert an analysis of a masked ICmp into its equivalent if all boolean 521 /// operations had the opposite sense. Since each "NotXXX" flag (recording !=) 522 /// is adjacent to the corresponding normal flag (recording ==), this just 523 /// involves swapping those bits over. 524 static unsigned conjugateICmpMask(unsigned Mask) { 525 unsigned NewMask; 526 NewMask = (Mask & (FoldMskICmp_AMask_AllOnes | FoldMskICmp_BMask_AllOnes | 527 FoldMskICmp_Mask_AllZeroes | FoldMskICmp_AMask_Mixed | 528 FoldMskICmp_BMask_Mixed)) 529 << 1; 530 531 NewMask |= 532 (Mask & (FoldMskICmp_AMask_NotAllOnes | FoldMskICmp_BMask_NotAllOnes | 533 FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_AMask_NotMixed | 534 FoldMskICmp_BMask_NotMixed)) 535 >> 1; 536 537 return NewMask; 538 } 539 540 /// decomposeBitTestICmp - Decompose an icmp into the form ((X & Y) pred Z) 541 /// if possible. The returned predicate is either == or !=. Returns false if 542 /// decomposition fails. 543 static bool decomposeBitTestICmp(const ICmpInst *I, ICmpInst::Predicate &Pred, 544 Value *&X, Value *&Y, Value *&Z) { 545 ConstantInt *C = dyn_cast<ConstantInt>(I->getOperand(1)); 546 if (!C) 547 return false; 548 549 switch (I->getPredicate()) { 550 default: 551 return false; 552 case ICmpInst::ICMP_SLT: 553 // X < 0 is equivalent to (X & SignBit) != 0. 554 if (!C->isZero()) 555 return false; 556 Y = ConstantInt::get(I->getContext(), APInt::getSignBit(C->getBitWidth())); 557 Pred = ICmpInst::ICMP_NE; 558 break; 559 case ICmpInst::ICMP_SGT: 560 // X > -1 is equivalent to (X & SignBit) == 0. 561 if (!C->isAllOnesValue()) 562 return false; 563 Y = ConstantInt::get(I->getContext(), APInt::getSignBit(C->getBitWidth())); 564 Pred = ICmpInst::ICMP_EQ; 565 break; 566 case ICmpInst::ICMP_ULT: 567 // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0. 568 if (!C->getValue().isPowerOf2()) 569 return false; 570 Y = ConstantInt::get(I->getContext(), -C->getValue()); 571 Pred = ICmpInst::ICMP_EQ; 572 break; 573 case ICmpInst::ICMP_UGT: 574 // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0. 575 if (!(C->getValue() + 1).isPowerOf2()) 576 return false; 577 Y = ConstantInt::get(I->getContext(), ~C->getValue()); 578 Pred = ICmpInst::ICMP_NE; 579 break; 580 } 581 582 X = I->getOperand(0); 583 Z = ConstantInt::getNullValue(C->getType()); 584 return true; 585 } 586 587 /// foldLogOpOfMaskedICmpsHelper: 588 /// handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) 589 /// return the set of pattern classes (from MaskedICmpType) 590 /// that both LHS and RHS satisfy 591 static unsigned foldLogOpOfMaskedICmpsHelper(Value*& A, 592 Value*& B, Value*& C, 593 Value*& D, Value*& E, 594 ICmpInst *LHS, ICmpInst *RHS, 595 ICmpInst::Predicate &LHSCC, 596 ICmpInst::Predicate &RHSCC) { 597 if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType()) return 0; 598 // vectors are not (yet?) supported 599 if (LHS->getOperand(0)->getType()->isVectorTy()) return 0; 600 601 // Here comes the tricky part: 602 // LHS might be of the form L11 & L12 == X, X == L21 & L22, 603 // and L11 & L12 == L21 & L22. The same goes for RHS. 604 // Now we must find those components L** and R**, that are equal, so 605 // that we can extract the parameters A, B, C, D, and E for the canonical 606 // above. 607 Value *L1 = LHS->getOperand(0); 608 Value *L2 = LHS->getOperand(1); 609 Value *L11,*L12,*L21,*L22; 610 // Check whether the icmp can be decomposed into a bit test. 611 if (decomposeBitTestICmp(LHS, LHSCC, L11, L12, L2)) { 612 L21 = L22 = L1 = nullptr; 613 } else { 614 // Look for ANDs in the LHS icmp. 615 if (!L1->getType()->isIntegerTy()) { 616 // You can icmp pointers, for example. They really aren't masks. 617 L11 = L12 = nullptr; 618 } else if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) { 619 // Any icmp can be viewed as being trivially masked; if it allows us to 620 // remove one, it's worth it. 621 L11 = L1; 622 L12 = Constant::getAllOnesValue(L1->getType()); 623 } 624 625 if (!L2->getType()->isIntegerTy()) { 626 // You can icmp pointers, for example. They really aren't masks. 627 L21 = L22 = nullptr; 628 } else if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) { 629 L21 = L2; 630 L22 = Constant::getAllOnesValue(L2->getType()); 631 } 632 } 633 634 // Bail if LHS was a icmp that can't be decomposed into an equality. 635 if (!ICmpInst::isEquality(LHSCC)) 636 return 0; 637 638 Value *R1 = RHS->getOperand(0); 639 Value *R2 = RHS->getOperand(1); 640 Value *R11,*R12; 641 bool ok = false; 642 if (decomposeBitTestICmp(RHS, RHSCC, R11, R12, R2)) { 643 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 644 A = R11; D = R12; 645 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 646 A = R12; D = R11; 647 } else { 648 return 0; 649 } 650 E = R2; R1 = nullptr; ok = true; 651 } else if (R1->getType()->isIntegerTy()) { 652 if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) { 653 // As before, model no mask as a trivial mask if it'll let us do an 654 // optimization. 655 R11 = R1; 656 R12 = Constant::getAllOnesValue(R1->getType()); 657 } 658 659 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 660 A = R11; D = R12; E = R2; ok = true; 661 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 662 A = R12; D = R11; E = R2; ok = true; 663 } 664 } 665 666 // Bail if RHS was a icmp that can't be decomposed into an equality. 667 if (!ICmpInst::isEquality(RHSCC)) 668 return 0; 669 670 // Look for ANDs in on the right side of the RHS icmp. 671 if (!ok && R2->getType()->isIntegerTy()) { 672 if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) { 673 R11 = R2; 674 R12 = Constant::getAllOnesValue(R2->getType()); 675 } 676 677 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 678 A = R11; D = R12; E = R1; ok = true; 679 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 680 A = R12; D = R11; E = R1; ok = true; 681 } else { 682 return 0; 683 } 684 } 685 if (!ok) 686 return 0; 687 688 if (L11 == A) { 689 B = L12; C = L2; 690 } else if (L12 == A) { 691 B = L11; C = L2; 692 } else if (L21 == A) { 693 B = L22; C = L1; 694 } else if (L22 == A) { 695 B = L21; C = L1; 696 } 697 698 unsigned left_type = getTypeOfMaskedICmp(A, B, C, LHSCC); 699 unsigned right_type = getTypeOfMaskedICmp(A, D, E, RHSCC); 700 return left_type & right_type; 701 } 702 /// foldLogOpOfMaskedICmps: 703 /// try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) 704 /// into a single (icmp(A & X) ==/!= Y) 705 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, 706 llvm::InstCombiner::BuilderTy *Builder) { 707 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr; 708 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 709 unsigned mask = foldLogOpOfMaskedICmpsHelper(A, B, C, D, E, LHS, RHS, 710 LHSCC, RHSCC); 711 if (mask == 0) return nullptr; 712 assert(ICmpInst::isEquality(LHSCC) && ICmpInst::isEquality(RHSCC) && 713 "foldLogOpOfMaskedICmpsHelper must return an equality predicate."); 714 715 // In full generality: 716 // (icmp (A & B) Op C) | (icmp (A & D) Op E) 717 // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ] 718 // 719 // If the latter can be converted into (icmp (A & X) Op Y) then the former is 720 // equivalent to (icmp (A & X) !Op Y). 721 // 722 // Therefore, we can pretend for the rest of this function that we're dealing 723 // with the conjunction, provided we flip the sense of any comparisons (both 724 // input and output). 725 726 // In most cases we're going to produce an EQ for the "&&" case. 727 ICmpInst::Predicate NEWCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; 728 if (!IsAnd) { 729 // Convert the masking analysis into its equivalent with negated 730 // comparisons. 731 mask = conjugateICmpMask(mask); 732 } 733 734 if (mask & FoldMskICmp_Mask_AllZeroes) { 735 // (icmp eq (A & B), 0) & (icmp eq (A & D), 0) 736 // -> (icmp eq (A & (B|D)), 0) 737 Value *newOr = Builder->CreateOr(B, D); 738 Value *newAnd = Builder->CreateAnd(A, newOr); 739 // we can't use C as zero, because we might actually handle 740 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 741 // with B and D, having a single bit set 742 Value *zero = Constant::getNullValue(A->getType()); 743 return Builder->CreateICmp(NEWCC, newAnd, zero); 744 } 745 if (mask & FoldMskICmp_BMask_AllOnes) { 746 // (icmp eq (A & B), B) & (icmp eq (A & D), D) 747 // -> (icmp eq (A & (B|D)), (B|D)) 748 Value *newOr = Builder->CreateOr(B, D); 749 Value *newAnd = Builder->CreateAnd(A, newOr); 750 return Builder->CreateICmp(NEWCC, newAnd, newOr); 751 } 752 if (mask & FoldMskICmp_AMask_AllOnes) { 753 // (icmp eq (A & B), A) & (icmp eq (A & D), A) 754 // -> (icmp eq (A & (B&D)), A) 755 Value *newAnd1 = Builder->CreateAnd(B, D); 756 Value *newAnd = Builder->CreateAnd(A, newAnd1); 757 return Builder->CreateICmp(NEWCC, newAnd, A); 758 } 759 760 // Remaining cases assume at least that B and D are constant, and depend on 761 // their actual values. This isn't strictly, necessary, just a "handle the 762 // easy cases for now" decision. 763 ConstantInt *BCst = dyn_cast<ConstantInt>(B); 764 if (!BCst) return nullptr; 765 ConstantInt *DCst = dyn_cast<ConstantInt>(D); 766 if (!DCst) return nullptr; 767 768 if (mask & (FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_BMask_NotAllOnes)) { 769 // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and 770 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 771 // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0) 772 // Only valid if one of the masks is a superset of the other (check "B&D" is 773 // the same as either B or D). 774 APInt NewMask = BCst->getValue() & DCst->getValue(); 775 776 if (NewMask == BCst->getValue()) 777 return LHS; 778 else if (NewMask == DCst->getValue()) 779 return RHS; 780 } 781 if (mask & FoldMskICmp_AMask_NotAllOnes) { 782 // (icmp ne (A & B), B) & (icmp ne (A & D), D) 783 // -> (icmp ne (A & B), A) or (icmp ne (A & D), A) 784 // Only valid if one of the masks is a superset of the other (check "B|D" is 785 // the same as either B or D). 786 APInt NewMask = BCst->getValue() | DCst->getValue(); 787 788 if (NewMask == BCst->getValue()) 789 return LHS; 790 else if (NewMask == DCst->getValue()) 791 return RHS; 792 } 793 if (mask & FoldMskICmp_BMask_Mixed) { 794 // (icmp eq (A & B), C) & (icmp eq (A & D), E) 795 // We already know that B & C == C && D & E == E. 796 // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of 797 // C and E, which are shared by both the mask B and the mask D, don't 798 // contradict, then we can transform to 799 // -> (icmp eq (A & (B|D)), (C|E)) 800 // Currently, we only handle the case of B, C, D, and E being constant. 801 // we can't simply use C and E, because we might actually handle 802 // (icmp ne (A & B), B) & (icmp eq (A & D), D) 803 // with B and D, having a single bit set 804 ConstantInt *CCst = dyn_cast<ConstantInt>(C); 805 if (!CCst) return nullptr; 806 ConstantInt *ECst = dyn_cast<ConstantInt>(E); 807 if (!ECst) return nullptr; 808 if (LHSCC != NEWCC) 809 CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst)); 810 if (RHSCC != NEWCC) 811 ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst)); 812 // if there is a conflict we should actually return a false for the 813 // whole construct 814 if (((BCst->getValue() & DCst->getValue()) & 815 (CCst->getValue() ^ ECst->getValue())) != 0) 816 return ConstantInt::get(LHS->getType(), !IsAnd); 817 Value *newOr1 = Builder->CreateOr(B, D); 818 Value *newOr2 = ConstantExpr::getOr(CCst, ECst); 819 Value *newAnd = Builder->CreateAnd(A, newOr1); 820 return Builder->CreateICmp(NEWCC, newAnd, newOr2); 821 } 822 return nullptr; 823 } 824 825 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp. 826 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n 827 /// If \p Inverted is true then the check is for the inverted range, e.g. 828 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n 829 Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, 830 bool Inverted) { 831 // Check the lower range comparison, e.g. x >= 0 832 // InstCombine already ensured that if there is a constant it's on the RHS. 833 ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1)); 834 if (!RangeStart) 835 return nullptr; 836 837 ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() : 838 Cmp0->getPredicate()); 839 840 // Accept x > -1 or x >= 0 (after potentially inverting the predicate). 841 if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) || 842 (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero()))) 843 return nullptr; 844 845 ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() : 846 Cmp1->getPredicate()); 847 848 Value *Input = Cmp0->getOperand(0); 849 Value *RangeEnd; 850 if (Cmp1->getOperand(0) == Input) { 851 // For the upper range compare we have: icmp x, n 852 RangeEnd = Cmp1->getOperand(1); 853 } else if (Cmp1->getOperand(1) == Input) { 854 // For the upper range compare we have: icmp n, x 855 RangeEnd = Cmp1->getOperand(0); 856 Pred1 = ICmpInst::getSwappedPredicate(Pred1); 857 } else { 858 return nullptr; 859 } 860 861 // Check the upper range comparison, e.g. x < n 862 ICmpInst::Predicate NewPred; 863 switch (Pred1) { 864 case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break; 865 case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break; 866 default: return nullptr; 867 } 868 869 // This simplification is only valid if the upper range is not negative. 870 bool IsNegative, IsNotNegative; 871 ComputeSignBit(RangeEnd, IsNotNegative, IsNegative, /*Depth=*/0, Cmp1); 872 if (!IsNotNegative) 873 return nullptr; 874 875 if (Inverted) 876 NewPred = ICmpInst::getInversePredicate(NewPred); 877 878 return Builder->CreateICmp(NewPred, Input, RangeEnd); 879 } 880 881 /// FoldAndOfICmps - Fold (icmp)&(icmp) if possible. 882 Value *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) { 883 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 884 885 // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B) 886 if (PredicatesFoldable(LHSCC, RHSCC)) { 887 if (LHS->getOperand(0) == RHS->getOperand(1) && 888 LHS->getOperand(1) == RHS->getOperand(0)) 889 LHS->swapOperands(); 890 if (LHS->getOperand(0) == RHS->getOperand(0) && 891 LHS->getOperand(1) == RHS->getOperand(1)) { 892 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 893 unsigned Code = getICmpCode(LHS) & getICmpCode(RHS); 894 bool isSigned = LHS->isSigned() || RHS->isSigned(); 895 return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); 896 } 897 } 898 899 // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E) 900 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder)) 901 return V; 902 903 // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n 904 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false)) 905 return V; 906 907 // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n 908 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false)) 909 return V; 910 911 // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2). 912 Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0); 913 ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1)); 914 ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1)); 915 if (!LHSCst || !RHSCst) return nullptr; 916 917 if (LHSCst == RHSCst && LHSCC == RHSCC) { 918 // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C) 919 // where C is a power of 2 920 if (LHSCC == ICmpInst::ICMP_ULT && 921 LHSCst->getValue().isPowerOf2()) { 922 Value *NewOr = Builder->CreateOr(Val, Val2); 923 return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 924 } 925 926 // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0) 927 if (LHSCC == ICmpInst::ICMP_EQ && LHSCst->isZero()) { 928 Value *NewOr = Builder->CreateOr(Val, Val2); 929 return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 930 } 931 } 932 933 // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2 934 // where CMAX is the all ones value for the truncated type, 935 // iff the lower bits of C2 and CA are zero. 936 if (LHSCC == ICmpInst::ICMP_EQ && LHSCC == RHSCC && 937 LHS->hasOneUse() && RHS->hasOneUse()) { 938 Value *V; 939 ConstantInt *AndCst, *SmallCst = nullptr, *BigCst = nullptr; 940 941 // (trunc x) == C1 & (and x, CA) == C2 942 // (and x, CA) == C2 & (trunc x) == C1 943 if (match(Val2, m_Trunc(m_Value(V))) && 944 match(Val, m_And(m_Specific(V), m_ConstantInt(AndCst)))) { 945 SmallCst = RHSCst; 946 BigCst = LHSCst; 947 } else if (match(Val, m_Trunc(m_Value(V))) && 948 match(Val2, m_And(m_Specific(V), m_ConstantInt(AndCst)))) { 949 SmallCst = LHSCst; 950 BigCst = RHSCst; 951 } 952 953 if (SmallCst && BigCst) { 954 unsigned BigBitSize = BigCst->getType()->getBitWidth(); 955 unsigned SmallBitSize = SmallCst->getType()->getBitWidth(); 956 957 // Check that the low bits are zero. 958 APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize); 959 if ((Low & AndCst->getValue()) == 0 && (Low & BigCst->getValue()) == 0) { 960 Value *NewAnd = Builder->CreateAnd(V, Low | AndCst->getValue()); 961 APInt N = SmallCst->getValue().zext(BigBitSize) | BigCst->getValue(); 962 Value *NewVal = ConstantInt::get(AndCst->getType()->getContext(), N); 963 return Builder->CreateICmp(LHSCC, NewAnd, NewVal); 964 } 965 } 966 } 967 968 // From here on, we only handle: 969 // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler. 970 if (Val != Val2) return nullptr; 971 972 // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere. 973 if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE || 974 RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE || 975 LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE || 976 RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE) 977 return nullptr; 978 979 // Make a constant range that's the intersection of the two icmp ranges. 980 // If the intersection is empty, we know that the result is false. 981 ConstantRange LHSRange = 982 ConstantRange::makeAllowedICmpRegion(LHSCC, LHSCst->getValue()); 983 ConstantRange RHSRange = 984 ConstantRange::makeAllowedICmpRegion(RHSCC, RHSCst->getValue()); 985 986 if (LHSRange.intersectWith(RHSRange).isEmptySet()) 987 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 988 989 // We can't fold (ugt x, C) & (sgt x, C2). 990 if (!PredicatesFoldable(LHSCC, RHSCC)) 991 return nullptr; 992 993 // Ensure that the larger constant is on the RHS. 994 bool ShouldSwap; 995 if (CmpInst::isSigned(LHSCC) || 996 (ICmpInst::isEquality(LHSCC) && 997 CmpInst::isSigned(RHSCC))) 998 ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue()); 999 else 1000 ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue()); 1001 1002 if (ShouldSwap) { 1003 std::swap(LHS, RHS); 1004 std::swap(LHSCst, RHSCst); 1005 std::swap(LHSCC, RHSCC); 1006 } 1007 1008 // At this point, we know we have two icmp instructions 1009 // comparing a value against two constants and and'ing the result 1010 // together. Because of the above check, we know that we only have 1011 // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know 1012 // (from the icmp folding check above), that the two constants 1013 // are not equal and that the larger constant is on the RHS 1014 assert(LHSCst != RHSCst && "Compares not folded above?"); 1015 1016 switch (LHSCC) { 1017 default: llvm_unreachable("Unknown integer condition code!"); 1018 case ICmpInst::ICMP_EQ: 1019 switch (RHSCC) { 1020 default: llvm_unreachable("Unknown integer condition code!"); 1021 case ICmpInst::ICMP_NE: // (X == 13 & X != 15) -> X == 13 1022 case ICmpInst::ICMP_ULT: // (X == 13 & X < 15) -> X == 13 1023 case ICmpInst::ICMP_SLT: // (X == 13 & X < 15) -> X == 13 1024 return LHS; 1025 } 1026 case ICmpInst::ICMP_NE: 1027 switch (RHSCC) { 1028 default: llvm_unreachable("Unknown integer condition code!"); 1029 case ICmpInst::ICMP_ULT: 1030 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X u< 14) -> X < 13 1031 return Builder->CreateICmpULT(Val, LHSCst); 1032 if (LHSCst->isNullValue()) // (X != 0 & X u< 14) -> X-1 u< 13 1033 return InsertRangeTest(Val, AddOne(LHSCst), RHSCst, false, true); 1034 break; // (X != 13 & X u< 15) -> no change 1035 case ICmpInst::ICMP_SLT: 1036 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X s< 14) -> X < 13 1037 return Builder->CreateICmpSLT(Val, LHSCst); 1038 break; // (X != 13 & X s< 15) -> no change 1039 case ICmpInst::ICMP_EQ: // (X != 13 & X == 15) -> X == 15 1040 case ICmpInst::ICMP_UGT: // (X != 13 & X u> 15) -> X u> 15 1041 case ICmpInst::ICMP_SGT: // (X != 13 & X s> 15) -> X s> 15 1042 return RHS; 1043 case ICmpInst::ICMP_NE: 1044 // Special case to get the ordering right when the values wrap around 1045 // zero. 1046 if (LHSCst->getValue() == 0 && RHSCst->getValue().isAllOnesValue()) 1047 std::swap(LHSCst, RHSCst); 1048 if (LHSCst == SubOne(RHSCst)){// (X != 13 & X != 14) -> X-13 >u 1 1049 Constant *AddCST = ConstantExpr::getNeg(LHSCst); 1050 Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off"); 1051 return Builder->CreateICmpUGT(Add, ConstantInt::get(Add->getType(), 1), 1052 Val->getName()+".cmp"); 1053 } 1054 break; // (X != 13 & X != 15) -> no change 1055 } 1056 break; 1057 case ICmpInst::ICMP_ULT: 1058 switch (RHSCC) { 1059 default: llvm_unreachable("Unknown integer condition code!"); 1060 case ICmpInst::ICMP_EQ: // (X u< 13 & X == 15) -> false 1061 case ICmpInst::ICMP_UGT: // (X u< 13 & X u> 15) -> false 1062 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1063 case ICmpInst::ICMP_SGT: // (X u< 13 & X s> 15) -> no change 1064 break; 1065 case ICmpInst::ICMP_NE: // (X u< 13 & X != 15) -> X u< 13 1066 case ICmpInst::ICMP_ULT: // (X u< 13 & X u< 15) -> X u< 13 1067 return LHS; 1068 case ICmpInst::ICMP_SLT: // (X u< 13 & X s< 15) -> no change 1069 break; 1070 } 1071 break; 1072 case ICmpInst::ICMP_SLT: 1073 switch (RHSCC) { 1074 default: llvm_unreachable("Unknown integer condition code!"); 1075 case ICmpInst::ICMP_UGT: // (X s< 13 & X u> 15) -> no change 1076 break; 1077 case ICmpInst::ICMP_NE: // (X s< 13 & X != 15) -> X < 13 1078 case ICmpInst::ICMP_SLT: // (X s< 13 & X s< 15) -> X < 13 1079 return LHS; 1080 case ICmpInst::ICMP_ULT: // (X s< 13 & X u< 15) -> no change 1081 break; 1082 } 1083 break; 1084 case ICmpInst::ICMP_UGT: 1085 switch (RHSCC) { 1086 default: llvm_unreachable("Unknown integer condition code!"); 1087 case ICmpInst::ICMP_EQ: // (X u> 13 & X == 15) -> X == 15 1088 case ICmpInst::ICMP_UGT: // (X u> 13 & X u> 15) -> X u> 15 1089 return RHS; 1090 case ICmpInst::ICMP_SGT: // (X u> 13 & X s> 15) -> no change 1091 break; 1092 case ICmpInst::ICMP_NE: 1093 if (RHSCst == AddOne(LHSCst)) // (X u> 13 & X != 14) -> X u> 14 1094 return Builder->CreateICmp(LHSCC, Val, RHSCst); 1095 break; // (X u> 13 & X != 15) -> no change 1096 case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1 1097 return InsertRangeTest(Val, AddOne(LHSCst), RHSCst, false, true); 1098 case ICmpInst::ICMP_SLT: // (X u> 13 & X s< 15) -> no change 1099 break; 1100 } 1101 break; 1102 case ICmpInst::ICMP_SGT: 1103 switch (RHSCC) { 1104 default: llvm_unreachable("Unknown integer condition code!"); 1105 case ICmpInst::ICMP_EQ: // (X s> 13 & X == 15) -> X == 15 1106 case ICmpInst::ICMP_SGT: // (X s> 13 & X s> 15) -> X s> 15 1107 return RHS; 1108 case ICmpInst::ICMP_UGT: // (X s> 13 & X u> 15) -> no change 1109 break; 1110 case ICmpInst::ICMP_NE: 1111 if (RHSCst == AddOne(LHSCst)) // (X s> 13 & X != 14) -> X s> 14 1112 return Builder->CreateICmp(LHSCC, Val, RHSCst); 1113 break; // (X s> 13 & X != 15) -> no change 1114 case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1 1115 return InsertRangeTest(Val, AddOne(LHSCst), RHSCst, true, true); 1116 case ICmpInst::ICMP_ULT: // (X s> 13 & X u< 15) -> no change 1117 break; 1118 } 1119 break; 1120 } 1121 1122 return nullptr; 1123 } 1124 1125 /// FoldAndOfFCmps - Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of 1126 /// instcombine, this returns a Value which should already be inserted into the 1127 /// function. 1128 Value *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) { 1129 if (LHS->getPredicate() == FCmpInst::FCMP_ORD && 1130 RHS->getPredicate() == FCmpInst::FCMP_ORD) { 1131 if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType()) 1132 return nullptr; 1133 1134 // (fcmp ord x, c) & (fcmp ord y, c) -> (fcmp ord x, y) 1135 if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1))) 1136 if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) { 1137 // If either of the constants are nans, then the whole thing returns 1138 // false. 1139 if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN()) 1140 return Builder->getFalse(); 1141 return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0)); 1142 } 1143 1144 // Handle vector zeros. This occurs because the canonical form of 1145 // "fcmp ord x,x" is "fcmp ord x, 0". 1146 if (isa<ConstantAggregateZero>(LHS->getOperand(1)) && 1147 isa<ConstantAggregateZero>(RHS->getOperand(1))) 1148 return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0)); 1149 return nullptr; 1150 } 1151 1152 Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1); 1153 Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1); 1154 FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate(); 1155 1156 1157 if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) { 1158 // Swap RHS operands to match LHS. 1159 Op1CC = FCmpInst::getSwappedPredicate(Op1CC); 1160 std::swap(Op1LHS, Op1RHS); 1161 } 1162 1163 if (Op0LHS == Op1LHS && Op0RHS == Op1RHS) { 1164 // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y). 1165 if (Op0CC == Op1CC) 1166 return Builder->CreateFCmp((FCmpInst::Predicate)Op0CC, Op0LHS, Op0RHS); 1167 if (Op0CC == FCmpInst::FCMP_FALSE || Op1CC == FCmpInst::FCMP_FALSE) 1168 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1169 if (Op0CC == FCmpInst::FCMP_TRUE) 1170 return RHS; 1171 if (Op1CC == FCmpInst::FCMP_TRUE) 1172 return LHS; 1173 1174 bool Op0Ordered; 1175 bool Op1Ordered; 1176 unsigned Op0Pred = getFCmpCode(Op0CC, Op0Ordered); 1177 unsigned Op1Pred = getFCmpCode(Op1CC, Op1Ordered); 1178 // uno && ord -> false 1179 if (Op0Pred == 0 && Op1Pred == 0 && Op0Ordered != Op1Ordered) 1180 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1181 if (Op1Pred == 0) { 1182 std::swap(LHS, RHS); 1183 std::swap(Op0Pred, Op1Pred); 1184 std::swap(Op0Ordered, Op1Ordered); 1185 } 1186 if (Op0Pred == 0) { 1187 // uno && ueq -> uno && (uno || eq) -> uno 1188 // ord && olt -> ord && (ord && lt) -> olt 1189 if (!Op0Ordered && (Op0Ordered == Op1Ordered)) 1190 return LHS; 1191 if (Op0Ordered && (Op0Ordered == Op1Ordered)) 1192 return RHS; 1193 1194 // uno && oeq -> uno && (ord && eq) -> false 1195 if (!Op0Ordered) 1196 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1197 // ord && ueq -> ord && (uno || eq) -> oeq 1198 return getFCmpValue(true, Op1Pred, Op0LHS, Op0RHS, Builder); 1199 } 1200 } 1201 1202 return nullptr; 1203 } 1204 1205 Instruction *InstCombiner::visitAnd(BinaryOperator &I) { 1206 bool Changed = SimplifyAssociativeOrCommutative(I); 1207 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1208 1209 if (Value *V = SimplifyVectorOp(I)) 1210 return ReplaceInstUsesWith(I, V); 1211 1212 if (Value *V = SimplifyAndInst(Op0, Op1, DL, TLI, DT, AC)) 1213 return ReplaceInstUsesWith(I, V); 1214 1215 // (A|B)&(A|C) -> A|(B&C) etc 1216 if (Value *V = SimplifyUsingDistributiveLaws(I)) 1217 return ReplaceInstUsesWith(I, V); 1218 1219 // See if we can simplify any instructions used by the instruction whose sole 1220 // purpose is to compute bits we don't care about. 1221 if (SimplifyDemandedInstructionBits(I)) 1222 return &I; 1223 1224 if (Value *V = SimplifyBSwap(I)) 1225 return ReplaceInstUsesWith(I, V); 1226 1227 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) { 1228 const APInt &AndRHSMask = AndRHS->getValue(); 1229 1230 // Optimize a variety of ((val OP C1) & C2) combinations... 1231 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 1232 Value *Op0LHS = Op0I->getOperand(0); 1233 Value *Op0RHS = Op0I->getOperand(1); 1234 switch (Op0I->getOpcode()) { 1235 default: break; 1236 case Instruction::Xor: 1237 case Instruction::Or: { 1238 // If the mask is only needed on one incoming arm, push it up. 1239 if (!Op0I->hasOneUse()) break; 1240 1241 APInt NotAndRHS(~AndRHSMask); 1242 if (MaskedValueIsZero(Op0LHS, NotAndRHS, 0, &I)) { 1243 // Not masking anything out for the LHS, move to RHS. 1244 Value *NewRHS = Builder->CreateAnd(Op0RHS, AndRHS, 1245 Op0RHS->getName()+".masked"); 1246 return BinaryOperator::Create(Op0I->getOpcode(), Op0LHS, NewRHS); 1247 } 1248 if (!isa<Constant>(Op0RHS) && 1249 MaskedValueIsZero(Op0RHS, NotAndRHS, 0, &I)) { 1250 // Not masking anything out for the RHS, move to LHS. 1251 Value *NewLHS = Builder->CreateAnd(Op0LHS, AndRHS, 1252 Op0LHS->getName()+".masked"); 1253 return BinaryOperator::Create(Op0I->getOpcode(), NewLHS, Op0RHS); 1254 } 1255 1256 break; 1257 } 1258 case Instruction::Add: 1259 // ((A & N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == AndRHS. 1260 // ((A | N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0 1261 // ((A ^ N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0 1262 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, false, I)) 1263 return BinaryOperator::CreateAnd(V, AndRHS); 1264 if (Value *V = FoldLogicalPlusAnd(Op0RHS, Op0LHS, AndRHS, false, I)) 1265 return BinaryOperator::CreateAnd(V, AndRHS); // Add commutes 1266 break; 1267 1268 case Instruction::Sub: 1269 // ((A & N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == AndRHS. 1270 // ((A | N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0 1271 // ((A ^ N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0 1272 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I)) 1273 return BinaryOperator::CreateAnd(V, AndRHS); 1274 1275 // (A - N) & AndRHS -> -N & AndRHS iff A&AndRHS==0 and AndRHS 1276 // has 1's for all bits that the subtraction with A might affect. 1277 if (Op0I->hasOneUse() && !match(Op0LHS, m_Zero())) { 1278 uint32_t BitWidth = AndRHSMask.getBitWidth(); 1279 uint32_t Zeros = AndRHSMask.countLeadingZeros(); 1280 APInt Mask = APInt::getLowBitsSet(BitWidth, BitWidth - Zeros); 1281 1282 if (MaskedValueIsZero(Op0LHS, Mask, 0, &I)) { 1283 Value *NewNeg = Builder->CreateNeg(Op0RHS); 1284 return BinaryOperator::CreateAnd(NewNeg, AndRHS); 1285 } 1286 } 1287 break; 1288 1289 case Instruction::Shl: 1290 case Instruction::LShr: 1291 // (1 << x) & 1 --> zext(x == 0) 1292 // (1 >> x) & 1 --> zext(x == 0) 1293 if (AndRHSMask == 1 && Op0LHS == AndRHS) { 1294 Value *NewICmp = 1295 Builder->CreateICmpEQ(Op0RHS, Constant::getNullValue(I.getType())); 1296 return new ZExtInst(NewICmp, I.getType()); 1297 } 1298 break; 1299 } 1300 1301 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) 1302 if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I)) 1303 return Res; 1304 } 1305 1306 // If this is an integer truncation, and if the source is an 'and' with 1307 // immediate, transform it. This frequently occurs for bitfield accesses. 1308 { 1309 Value *X = nullptr; ConstantInt *YC = nullptr; 1310 if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) { 1311 // Change: and (trunc (and X, YC) to T), C2 1312 // into : and (trunc X to T), trunc(YC) & C2 1313 // This will fold the two constants together, which may allow 1314 // other simplifications. 1315 Value *NewCast = Builder->CreateTrunc(X, I.getType(), "and.shrunk"); 1316 Constant *C3 = ConstantExpr::getTrunc(YC, I.getType()); 1317 C3 = ConstantExpr::getAnd(C3, AndRHS); 1318 return BinaryOperator::CreateAnd(NewCast, C3); 1319 } 1320 } 1321 1322 // Try to fold constant and into select arguments. 1323 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1324 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1325 return R; 1326 if (isa<PHINode>(Op0)) 1327 if (Instruction *NV = FoldOpIntoPhi(I)) 1328 return NV; 1329 } 1330 1331 1332 // (~A & ~B) == (~(A | B)) - De Morgan's Law 1333 if (Value *Op0NotVal = dyn_castNotVal(Op0)) 1334 if (Value *Op1NotVal = dyn_castNotVal(Op1)) 1335 if (Op0->hasOneUse() && Op1->hasOneUse()) { 1336 Value *Or = Builder->CreateOr(Op0NotVal, Op1NotVal, 1337 I.getName()+".demorgan"); 1338 return BinaryOperator::CreateNot(Or); 1339 } 1340 1341 { 1342 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 1343 // (A|B) & ~(A&B) -> A^B 1344 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1345 match(Op1, m_Not(m_And(m_Value(C), m_Value(D)))) && 1346 ((A == C && B == D) || (A == D && B == C))) 1347 return BinaryOperator::CreateXor(A, B); 1348 1349 // ~(A&B) & (A|B) -> A^B 1350 if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1351 match(Op0, m_Not(m_And(m_Value(C), m_Value(D)))) && 1352 ((A == C && B == D) || (A == D && B == C))) 1353 return BinaryOperator::CreateXor(A, B); 1354 1355 // A&(A^B) => A & ~B 1356 { 1357 Value *tmpOp0 = Op0; 1358 Value *tmpOp1 = Op1; 1359 if (Op0->hasOneUse() && 1360 match(Op0, m_Xor(m_Value(A), m_Value(B)))) { 1361 if (A == Op1 || B == Op1 ) { 1362 tmpOp1 = Op0; 1363 tmpOp0 = Op1; 1364 // Simplify below 1365 } 1366 } 1367 1368 if (tmpOp1->hasOneUse() && 1369 match(tmpOp1, m_Xor(m_Value(A), m_Value(B)))) { 1370 if (B == tmpOp0) { 1371 std::swap(A, B); 1372 } 1373 // Notice that the patten (A&(~B)) is actually (A&(-1^B)), so if 1374 // A is originally -1 (or a vector of -1 and undefs), then we enter 1375 // an endless loop. By checking that A is non-constant we ensure that 1376 // we will never get to the loop. 1377 if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B 1378 return BinaryOperator::CreateAnd(A, Builder->CreateNot(B)); 1379 } 1380 } 1381 1382 // (A&((~A)|B)) -> A&B 1383 if (match(Op0, m_Or(m_Not(m_Specific(Op1)), m_Value(A))) || 1384 match(Op0, m_Or(m_Value(A), m_Not(m_Specific(Op1))))) 1385 return BinaryOperator::CreateAnd(A, Op1); 1386 if (match(Op1, m_Or(m_Not(m_Specific(Op0)), m_Value(A))) || 1387 match(Op1, m_Or(m_Value(A), m_Not(m_Specific(Op0))))) 1388 return BinaryOperator::CreateAnd(A, Op0); 1389 1390 // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C 1391 if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) 1392 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) 1393 if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse()) 1394 return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(C)); 1395 1396 // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C 1397 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B)))) 1398 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A)))) 1399 if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse()) 1400 return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C)); 1401 1402 // (A | B) & ((~A) ^ B) -> (A & B) 1403 if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1404 match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B)))) 1405 return BinaryOperator::CreateAnd(A, B); 1406 1407 // ((~A) ^ B) & (A | B) -> (A & B) 1408 if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) && 1409 match(Op1, m_Or(m_Specific(A), m_Specific(B)))) 1410 return BinaryOperator::CreateAnd(A, B); 1411 } 1412 1413 { 1414 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0); 1415 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1); 1416 if (LHS && RHS) 1417 if (Value *Res = FoldAndOfICmps(LHS, RHS)) 1418 return ReplaceInstUsesWith(I, Res); 1419 1420 // TODO: Make this recursive; it's a little tricky because an arbitrary 1421 // number of 'and' instructions might have to be created. 1422 Value *X, *Y; 1423 if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) { 1424 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 1425 if (Value *Res = FoldAndOfICmps(LHS, Cmp)) 1426 return ReplaceInstUsesWith(I, Builder->CreateAnd(Res, Y)); 1427 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 1428 if (Value *Res = FoldAndOfICmps(LHS, Cmp)) 1429 return ReplaceInstUsesWith(I, Builder->CreateAnd(Res, X)); 1430 } 1431 if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) { 1432 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 1433 if (Value *Res = FoldAndOfICmps(Cmp, RHS)) 1434 return ReplaceInstUsesWith(I, Builder->CreateAnd(Res, Y)); 1435 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 1436 if (Value *Res = FoldAndOfICmps(Cmp, RHS)) 1437 return ReplaceInstUsesWith(I, Builder->CreateAnd(Res, X)); 1438 } 1439 } 1440 1441 // If and'ing two fcmp, try combine them into one. 1442 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 1443 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 1444 if (Value *Res = FoldAndOfFCmps(LHS, RHS)) 1445 return ReplaceInstUsesWith(I, Res); 1446 1447 1448 // fold (and (cast A), (cast B)) -> (cast (and A, B)) 1449 if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) 1450 if (CastInst *Op1C = dyn_cast<CastInst>(Op1)) { 1451 Type *SrcTy = Op0C->getOperand(0)->getType(); 1452 if (Op0C->getOpcode() == Op1C->getOpcode() && // same cast kind ? 1453 SrcTy == Op1C->getOperand(0)->getType() && 1454 SrcTy->isIntOrIntVectorTy()) { 1455 Value *Op0COp = Op0C->getOperand(0), *Op1COp = Op1C->getOperand(0); 1456 1457 // Only do this if the casts both really cause code to be generated. 1458 if (ShouldOptimizeCast(Op0C->getOpcode(), Op0COp, I.getType()) && 1459 ShouldOptimizeCast(Op1C->getOpcode(), Op1COp, I.getType())) { 1460 Value *NewOp = Builder->CreateAnd(Op0COp, Op1COp, I.getName()); 1461 return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 1462 } 1463 1464 // If this is and(cast(icmp), cast(icmp)), try to fold this even if the 1465 // cast is otherwise not optimizable. This happens for vector sexts. 1466 if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1COp)) 1467 if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0COp)) 1468 if (Value *Res = FoldAndOfICmps(LHS, RHS)) 1469 return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 1470 1471 // If this is and(cast(fcmp), cast(fcmp)), try to fold this even if the 1472 // cast is otherwise not optimizable. This happens for vector sexts. 1473 if (FCmpInst *RHS = dyn_cast<FCmpInst>(Op1COp)) 1474 if (FCmpInst *LHS = dyn_cast<FCmpInst>(Op0COp)) 1475 if (Value *Res = FoldAndOfFCmps(LHS, RHS)) 1476 return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 1477 } 1478 } 1479 1480 { 1481 Value *X = nullptr; 1482 bool OpsSwapped = false; 1483 // Canonicalize SExt or Not to the LHS 1484 if (match(Op1, m_SExt(m_Value())) || 1485 match(Op1, m_Not(m_Value()))) { 1486 std::swap(Op0, Op1); 1487 OpsSwapped = true; 1488 } 1489 1490 // Fold (and (sext bool to A), B) --> (select bool, B, 0) 1491 if (match(Op0, m_SExt(m_Value(X))) && 1492 X->getType()->getScalarType()->isIntegerTy(1)) { 1493 Value *Zero = Constant::getNullValue(Op1->getType()); 1494 return SelectInst::Create(X, Op1, Zero); 1495 } 1496 1497 // Fold (and ~(sext bool to A), B) --> (select bool, 0, B) 1498 if (match(Op0, m_Not(m_SExt(m_Value(X)))) && 1499 X->getType()->getScalarType()->isIntegerTy(1)) { 1500 Value *Zero = Constant::getNullValue(Op0->getType()); 1501 return SelectInst::Create(X, Zero, Op1); 1502 } 1503 1504 if (OpsSwapped) 1505 std::swap(Op0, Op1); 1506 } 1507 1508 return Changed ? &I : nullptr; 1509 } 1510 1511 /// CollectBSwapParts - Analyze the specified subexpression and see if it is 1512 /// capable of providing pieces of a bswap. The subexpression provides pieces 1513 /// of a bswap if it is proven that each of the non-zero bytes in the output of 1514 /// the expression came from the corresponding "byte swapped" byte in some other 1515 /// value. For example, if the current subexpression is "(shl i32 %X, 24)" then 1516 /// we know that the expression deposits the low byte of %X into the high byte 1517 /// of the bswap result and that all other bytes are zero. This expression is 1518 /// accepted, the high byte of ByteValues is set to X to indicate a correct 1519 /// match. 1520 /// 1521 /// This function returns true if the match was unsuccessful and false if so. 1522 /// On entry to the function the "OverallLeftShift" is a signed integer value 1523 /// indicating the number of bytes that the subexpression is later shifted. For 1524 /// example, if the expression is later right shifted by 16 bits, the 1525 /// OverallLeftShift value would be -2 on entry. This is used to specify which 1526 /// byte of ByteValues is actually being set. 1527 /// 1528 /// Similarly, ByteMask is a bitmask where a bit is clear if its corresponding 1529 /// byte is masked to zero by a user. For example, in (X & 255), X will be 1530 /// processed with a bytemask of 1. Because bytemask is 32-bits, this limits 1531 /// this function to working on up to 32-byte (256 bit) values. ByteMask is 1532 /// always in the local (OverallLeftShift) coordinate space. 1533 /// 1534 static bool CollectBSwapParts(Value *V, int OverallLeftShift, uint32_t ByteMask, 1535 SmallVectorImpl<Value *> &ByteValues) { 1536 if (Instruction *I = dyn_cast<Instruction>(V)) { 1537 // If this is an or instruction, it may be an inner node of the bswap. 1538 if (I->getOpcode() == Instruction::Or) { 1539 return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1540 ByteValues) || 1541 CollectBSwapParts(I->getOperand(1), OverallLeftShift, ByteMask, 1542 ByteValues); 1543 } 1544 1545 // If this is a logical shift by a constant multiple of 8, recurse with 1546 // OverallLeftShift and ByteMask adjusted. 1547 if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) { 1548 unsigned ShAmt = 1549 cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U); 1550 // Ensure the shift amount is defined and of a byte value. 1551 if ((ShAmt & 7) || (ShAmt > 8*ByteValues.size())) 1552 return true; 1553 1554 unsigned ByteShift = ShAmt >> 3; 1555 if (I->getOpcode() == Instruction::Shl) { 1556 // X << 2 -> collect(X, +2) 1557 OverallLeftShift += ByteShift; 1558 ByteMask >>= ByteShift; 1559 } else { 1560 // X >>u 2 -> collect(X, -2) 1561 OverallLeftShift -= ByteShift; 1562 ByteMask <<= ByteShift; 1563 ByteMask &= (~0U >> (32-ByteValues.size())); 1564 } 1565 1566 if (OverallLeftShift >= (int)ByteValues.size()) return true; 1567 if (OverallLeftShift <= -(int)ByteValues.size()) return true; 1568 1569 return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1570 ByteValues); 1571 } 1572 1573 // If this is a logical 'and' with a mask that clears bytes, clear the 1574 // corresponding bytes in ByteMask. 1575 if (I->getOpcode() == Instruction::And && 1576 isa<ConstantInt>(I->getOperand(1))) { 1577 // Scan every byte of the and mask, seeing if the byte is either 0 or 255. 1578 unsigned NumBytes = ByteValues.size(); 1579 APInt Byte(I->getType()->getPrimitiveSizeInBits(), 255); 1580 const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue(); 1581 1582 for (unsigned i = 0; i != NumBytes; ++i, Byte <<= 8) { 1583 // If this byte is masked out by a later operation, we don't care what 1584 // the and mask is. 1585 if ((ByteMask & (1 << i)) == 0) 1586 continue; 1587 1588 // If the AndMask is all zeros for this byte, clear the bit. 1589 APInt MaskB = AndMask & Byte; 1590 if (MaskB == 0) { 1591 ByteMask &= ~(1U << i); 1592 continue; 1593 } 1594 1595 // If the AndMask is not all ones for this byte, it's not a bytezap. 1596 if (MaskB != Byte) 1597 return true; 1598 1599 // Otherwise, this byte is kept. 1600 } 1601 1602 return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1603 ByteValues); 1604 } 1605 } 1606 1607 // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be 1608 // the input value to the bswap. Some observations: 1) if more than one byte 1609 // is demanded from this input, then it could not be successfully assembled 1610 // into a byteswap. At least one of the two bytes would not be aligned with 1611 // their ultimate destination. 1612 if (!isPowerOf2_32(ByteMask)) return true; 1613 unsigned InputByteNo = countTrailingZeros(ByteMask); 1614 1615 // 2) The input and ultimate destinations must line up: if byte 3 of an i32 1616 // is demanded, it needs to go into byte 0 of the result. This means that the 1617 // byte needs to be shifted until it lands in the right byte bucket. The 1618 // shift amount depends on the position: if the byte is coming from the high 1619 // part of the value (e.g. byte 3) then it must be shifted right. If from the 1620 // low part, it must be shifted left. 1621 unsigned DestByteNo = InputByteNo + OverallLeftShift; 1622 if (ByteValues.size()-1-DestByteNo != InputByteNo) 1623 return true; 1624 1625 // If the destination byte value is already defined, the values are or'd 1626 // together, which isn't a bswap (unless it's an or of the same bits). 1627 if (ByteValues[DestByteNo] && ByteValues[DestByteNo] != V) 1628 return true; 1629 ByteValues[DestByteNo] = V; 1630 return false; 1631 } 1632 1633 /// MatchBSwap - Given an OR instruction, check to see if this is a bswap idiom. 1634 /// If so, insert the new bswap intrinsic and return it. 1635 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) { 1636 IntegerType *ITy = dyn_cast<IntegerType>(I.getType()); 1637 if (!ITy || ITy->getBitWidth() % 16 || 1638 // ByteMask only allows up to 32-byte values. 1639 ITy->getBitWidth() > 32*8) 1640 return nullptr; // Can only bswap pairs of bytes. Can't do vectors. 1641 1642 /// ByteValues - For each byte of the result, we keep track of which value 1643 /// defines each byte. 1644 SmallVector<Value*, 8> ByteValues; 1645 ByteValues.resize(ITy->getBitWidth()/8); 1646 1647 // Try to find all the pieces corresponding to the bswap. 1648 uint32_t ByteMask = ~0U >> (32-ByteValues.size()); 1649 if (CollectBSwapParts(&I, 0, ByteMask, ByteValues)) 1650 return nullptr; 1651 1652 // Check to see if all of the bytes come from the same value. 1653 Value *V = ByteValues[0]; 1654 if (!V) return nullptr; // Didn't find a byte? Must be zero. 1655 1656 // Check to make sure that all of the bytes come from the same value. 1657 for (unsigned i = 1, e = ByteValues.size(); i != e; ++i) 1658 if (ByteValues[i] != V) 1659 return nullptr; 1660 Module *M = I.getParent()->getParent()->getParent(); 1661 Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, ITy); 1662 return CallInst::Create(F, V); 1663 } 1664 1665 /// MatchSelectFromAndOr - We have an expression of the form (A&C)|(B&D). Check 1666 /// If A is (cond?-1:0) and either B or D is ~(cond?-1,0) or (cond?0,-1), then 1667 /// we can simplify this expression to "cond ? C : D or B". 1668 static Instruction *MatchSelectFromAndOr(Value *A, Value *B, 1669 Value *C, Value *D) { 1670 // If A is not a select of -1/0, this cannot match. 1671 Value *Cond = nullptr; 1672 if (!match(A, m_SExt(m_Value(Cond))) || 1673 !Cond->getType()->isIntegerTy(1)) 1674 return nullptr; 1675 1676 // ((cond?-1:0)&C) | (B&(cond?0:-1)) -> cond ? C : B. 1677 if (match(D, m_Not(m_SExt(m_Specific(Cond))))) 1678 return SelectInst::Create(Cond, C, B); 1679 if (match(D, m_SExt(m_Not(m_Specific(Cond))))) 1680 return SelectInst::Create(Cond, C, B); 1681 1682 // ((cond?-1:0)&C) | ((cond?0:-1)&D) -> cond ? C : D. 1683 if (match(B, m_Not(m_SExt(m_Specific(Cond))))) 1684 return SelectInst::Create(Cond, C, D); 1685 if (match(B, m_SExt(m_Not(m_Specific(Cond))))) 1686 return SelectInst::Create(Cond, C, D); 1687 return nullptr; 1688 } 1689 1690 /// FoldOrOfICmps - Fold (icmp)|(icmp) if possible. 1691 Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, 1692 Instruction *CxtI) { 1693 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 1694 1695 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2) 1696 // if K1 and K2 are a one-bit mask. 1697 ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1)); 1698 ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1)); 1699 1700 if (LHS->getPredicate() == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero() && 1701 RHS->getPredicate() == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) { 1702 1703 BinaryOperator *LAnd = dyn_cast<BinaryOperator>(LHS->getOperand(0)); 1704 BinaryOperator *RAnd = dyn_cast<BinaryOperator>(RHS->getOperand(0)); 1705 if (LAnd && RAnd && LAnd->hasOneUse() && RHS->hasOneUse() && 1706 LAnd->getOpcode() == Instruction::And && 1707 RAnd->getOpcode() == Instruction::And) { 1708 1709 Value *Mask = nullptr; 1710 Value *Masked = nullptr; 1711 if (LAnd->getOperand(0) == RAnd->getOperand(0) && 1712 isKnownToBeAPowerOfTwo(LAnd->getOperand(1), DL, false, 0, AC, CxtI, 1713 DT) && 1714 isKnownToBeAPowerOfTwo(RAnd->getOperand(1), DL, false, 0, AC, CxtI, 1715 DT)) { 1716 Mask = Builder->CreateOr(LAnd->getOperand(1), RAnd->getOperand(1)); 1717 Masked = Builder->CreateAnd(LAnd->getOperand(0), Mask); 1718 } else if (LAnd->getOperand(1) == RAnd->getOperand(1) && 1719 isKnownToBeAPowerOfTwo(LAnd->getOperand(0), DL, false, 0, AC, 1720 CxtI, DT) && 1721 isKnownToBeAPowerOfTwo(RAnd->getOperand(0), DL, false, 0, AC, 1722 CxtI, DT)) { 1723 Mask = Builder->CreateOr(LAnd->getOperand(0), RAnd->getOperand(0)); 1724 Masked = Builder->CreateAnd(LAnd->getOperand(1), Mask); 1725 } 1726 1727 if (Masked) 1728 return Builder->CreateICmp(ICmpInst::ICMP_NE, Masked, Mask); 1729 } 1730 } 1731 1732 // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3) 1733 // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3) 1734 // The original condition actually refers to the following two ranges: 1735 // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3] 1736 // We can fold these two ranges if: 1737 // 1) C1 and C2 is unsigned greater than C3. 1738 // 2) The two ranges are separated. 1739 // 3) C1 ^ C2 is one-bit mask. 1740 // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask. 1741 // This implies all values in the two ranges differ by exactly one bit. 1742 1743 if ((LHSCC == ICmpInst::ICMP_ULT || LHSCC == ICmpInst::ICMP_ULE) && 1744 LHSCC == RHSCC && LHSCst && RHSCst && LHS->hasOneUse() && 1745 RHS->hasOneUse() && LHSCst->getType() == RHSCst->getType() && 1746 LHSCst->getValue() == (RHSCst->getValue())) { 1747 1748 Value *LAdd = LHS->getOperand(0); 1749 Value *RAdd = RHS->getOperand(0); 1750 1751 Value *LAddOpnd, *RAddOpnd; 1752 ConstantInt *LAddCst, *RAddCst; 1753 if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddCst))) && 1754 match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddCst))) && 1755 LAddCst->getValue().ugt(LHSCst->getValue()) && 1756 RAddCst->getValue().ugt(LHSCst->getValue())) { 1757 1758 APInt DiffCst = LAddCst->getValue() ^ RAddCst->getValue(); 1759 if (LAddOpnd == RAddOpnd && DiffCst.isPowerOf2()) { 1760 ConstantInt *MaxAddCst = nullptr; 1761 if (LAddCst->getValue().ult(RAddCst->getValue())) 1762 MaxAddCst = RAddCst; 1763 else 1764 MaxAddCst = LAddCst; 1765 1766 APInt RRangeLow = -RAddCst->getValue(); 1767 APInt RRangeHigh = RRangeLow + LHSCst->getValue(); 1768 APInt LRangeLow = -LAddCst->getValue(); 1769 APInt LRangeHigh = LRangeLow + LHSCst->getValue(); 1770 APInt LowRangeDiff = RRangeLow ^ LRangeLow; 1771 APInt HighRangeDiff = RRangeHigh ^ LRangeHigh; 1772 APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow 1773 : RRangeLow - LRangeLow; 1774 1775 if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff && 1776 RangeDiff.ugt(LHSCst->getValue())) { 1777 Value *MaskCst = ConstantInt::get(LAddCst->getType(), ~DiffCst); 1778 1779 Value *NewAnd = Builder->CreateAnd(LAddOpnd, MaskCst); 1780 Value *NewAdd = Builder->CreateAdd(NewAnd, MaxAddCst); 1781 return (Builder->CreateICmp(LHS->getPredicate(), NewAdd, LHSCst)); 1782 } 1783 } 1784 } 1785 } 1786 1787 // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B) 1788 if (PredicatesFoldable(LHSCC, RHSCC)) { 1789 if (LHS->getOperand(0) == RHS->getOperand(1) && 1790 LHS->getOperand(1) == RHS->getOperand(0)) 1791 LHS->swapOperands(); 1792 if (LHS->getOperand(0) == RHS->getOperand(0) && 1793 LHS->getOperand(1) == RHS->getOperand(1)) { 1794 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 1795 unsigned Code = getICmpCode(LHS) | getICmpCode(RHS); 1796 bool isSigned = LHS->isSigned() || RHS->isSigned(); 1797 return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); 1798 } 1799 } 1800 1801 // handle (roughly): 1802 // (icmp ne (A & B), C) | (icmp ne (A & D), E) 1803 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder)) 1804 return V; 1805 1806 Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0); 1807 if (LHS->hasOneUse() || RHS->hasOneUse()) { 1808 // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1) 1809 // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1) 1810 Value *A = nullptr, *B = nullptr; 1811 if (LHSCC == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero()) { 1812 B = Val; 1813 if (RHSCC == ICmpInst::ICMP_ULT && Val == RHS->getOperand(1)) 1814 A = Val2; 1815 else if (RHSCC == ICmpInst::ICMP_UGT && Val == Val2) 1816 A = RHS->getOperand(1); 1817 } 1818 // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1) 1819 // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1) 1820 else if (RHSCC == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) { 1821 B = Val2; 1822 if (LHSCC == ICmpInst::ICMP_ULT && Val2 == LHS->getOperand(1)) 1823 A = Val; 1824 else if (LHSCC == ICmpInst::ICMP_UGT && Val2 == Val) 1825 A = LHS->getOperand(1); 1826 } 1827 if (A && B) 1828 return Builder->CreateICmp( 1829 ICmpInst::ICMP_UGE, 1830 Builder->CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A); 1831 } 1832 1833 // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n 1834 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true)) 1835 return V; 1836 1837 // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n 1838 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true)) 1839 return V; 1840 1841 // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2). 1842 if (!LHSCst || !RHSCst) return nullptr; 1843 1844 if (LHSCst == RHSCst && LHSCC == RHSCC) { 1845 // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0) 1846 if (LHSCC == ICmpInst::ICMP_NE && LHSCst->isZero()) { 1847 Value *NewOr = Builder->CreateOr(Val, Val2); 1848 return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 1849 } 1850 } 1851 1852 // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1) 1853 // iff C2 + CA == C1. 1854 if (LHSCC == ICmpInst::ICMP_ULT && RHSCC == ICmpInst::ICMP_EQ) { 1855 ConstantInt *AddCst; 1856 if (match(Val, m_Add(m_Specific(Val2), m_ConstantInt(AddCst)))) 1857 if (RHSCst->getValue() + AddCst->getValue() == LHSCst->getValue()) 1858 return Builder->CreateICmpULE(Val, LHSCst); 1859 } 1860 1861 // From here on, we only handle: 1862 // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler. 1863 if (Val != Val2) return nullptr; 1864 1865 // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere. 1866 if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE || 1867 RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE || 1868 LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE || 1869 RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE) 1870 return nullptr; 1871 1872 // We can't fold (ugt x, C) | (sgt x, C2). 1873 if (!PredicatesFoldable(LHSCC, RHSCC)) 1874 return nullptr; 1875 1876 // Ensure that the larger constant is on the RHS. 1877 bool ShouldSwap; 1878 if (CmpInst::isSigned(LHSCC) || 1879 (ICmpInst::isEquality(LHSCC) && 1880 CmpInst::isSigned(RHSCC))) 1881 ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue()); 1882 else 1883 ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue()); 1884 1885 if (ShouldSwap) { 1886 std::swap(LHS, RHS); 1887 std::swap(LHSCst, RHSCst); 1888 std::swap(LHSCC, RHSCC); 1889 } 1890 1891 // At this point, we know we have two icmp instructions 1892 // comparing a value against two constants and or'ing the result 1893 // together. Because of the above check, we know that we only have 1894 // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the 1895 // icmp folding check above), that the two constants are not 1896 // equal. 1897 assert(LHSCst != RHSCst && "Compares not folded above?"); 1898 1899 switch (LHSCC) { 1900 default: llvm_unreachable("Unknown integer condition code!"); 1901 case ICmpInst::ICMP_EQ: 1902 switch (RHSCC) { 1903 default: llvm_unreachable("Unknown integer condition code!"); 1904 case ICmpInst::ICMP_EQ: 1905 if (LHS->getOperand(0) == RHS->getOperand(0)) { 1906 // if LHSCst and RHSCst differ only by one bit: 1907 // (A == C1 || A == C2) -> (A & ~(C1 ^ C2)) == C1 1908 assert(LHSCst->getValue().ule(LHSCst->getValue())); 1909 1910 APInt Xor = LHSCst->getValue() ^ RHSCst->getValue(); 1911 if (Xor.isPowerOf2()) { 1912 Value *NegCst = Builder->getInt(~Xor); 1913 Value *And = Builder->CreateAnd(LHS->getOperand(0), NegCst); 1914 return Builder->CreateICmp(ICmpInst::ICMP_EQ, And, LHSCst); 1915 } 1916 } 1917 1918 if (LHSCst == SubOne(RHSCst)) { 1919 // (X == 13 | X == 14) -> X-13 <u 2 1920 Constant *AddCST = ConstantExpr::getNeg(LHSCst); 1921 Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off"); 1922 AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst); 1923 return Builder->CreateICmpULT(Add, AddCST); 1924 } 1925 1926 break; // (X == 13 | X == 15) -> no change 1927 case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change 1928 case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change 1929 break; 1930 case ICmpInst::ICMP_NE: // (X == 13 | X != 15) -> X != 15 1931 case ICmpInst::ICMP_ULT: // (X == 13 | X u< 15) -> X u< 15 1932 case ICmpInst::ICMP_SLT: // (X == 13 | X s< 15) -> X s< 15 1933 return RHS; 1934 } 1935 break; 1936 case ICmpInst::ICMP_NE: 1937 switch (RHSCC) { 1938 default: llvm_unreachable("Unknown integer condition code!"); 1939 case ICmpInst::ICMP_EQ: // (X != 13 | X == 15) -> X != 13 1940 case ICmpInst::ICMP_UGT: // (X != 13 | X u> 15) -> X != 13 1941 case ICmpInst::ICMP_SGT: // (X != 13 | X s> 15) -> X != 13 1942 return LHS; 1943 case ICmpInst::ICMP_NE: // (X != 13 | X != 15) -> true 1944 case ICmpInst::ICMP_ULT: // (X != 13 | X u< 15) -> true 1945 case ICmpInst::ICMP_SLT: // (X != 13 | X s< 15) -> true 1946 return Builder->getTrue(); 1947 } 1948 case ICmpInst::ICMP_ULT: 1949 switch (RHSCC) { 1950 default: llvm_unreachable("Unknown integer condition code!"); 1951 case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change 1952 break; 1953 case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2 1954 // If RHSCst is [us]MAXINT, it is always false. Not handling 1955 // this can cause overflow. 1956 if (RHSCst->isMaxValue(false)) 1957 return LHS; 1958 return InsertRangeTest(Val, LHSCst, AddOne(RHSCst), false, false); 1959 case ICmpInst::ICMP_SGT: // (X u< 13 | X s> 15) -> no change 1960 break; 1961 case ICmpInst::ICMP_NE: // (X u< 13 | X != 15) -> X != 15 1962 case ICmpInst::ICMP_ULT: // (X u< 13 | X u< 15) -> X u< 15 1963 return RHS; 1964 case ICmpInst::ICMP_SLT: // (X u< 13 | X s< 15) -> no change 1965 break; 1966 } 1967 break; 1968 case ICmpInst::ICMP_SLT: 1969 switch (RHSCC) { 1970 default: llvm_unreachable("Unknown integer condition code!"); 1971 case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change 1972 break; 1973 case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2 1974 // If RHSCst is [us]MAXINT, it is always false. Not handling 1975 // this can cause overflow. 1976 if (RHSCst->isMaxValue(true)) 1977 return LHS; 1978 return InsertRangeTest(Val, LHSCst, AddOne(RHSCst), true, false); 1979 case ICmpInst::ICMP_UGT: // (X s< 13 | X u> 15) -> no change 1980 break; 1981 case ICmpInst::ICMP_NE: // (X s< 13 | X != 15) -> X != 15 1982 case ICmpInst::ICMP_SLT: // (X s< 13 | X s< 15) -> X s< 15 1983 return RHS; 1984 case ICmpInst::ICMP_ULT: // (X s< 13 | X u< 15) -> no change 1985 break; 1986 } 1987 break; 1988 case ICmpInst::ICMP_UGT: 1989 switch (RHSCC) { 1990 default: llvm_unreachable("Unknown integer condition code!"); 1991 case ICmpInst::ICMP_EQ: // (X u> 13 | X == 15) -> X u> 13 1992 case ICmpInst::ICMP_UGT: // (X u> 13 | X u> 15) -> X u> 13 1993 return LHS; 1994 case ICmpInst::ICMP_SGT: // (X u> 13 | X s> 15) -> no change 1995 break; 1996 case ICmpInst::ICMP_NE: // (X u> 13 | X != 15) -> true 1997 case ICmpInst::ICMP_ULT: // (X u> 13 | X u< 15) -> true 1998 return Builder->getTrue(); 1999 case ICmpInst::ICMP_SLT: // (X u> 13 | X s< 15) -> no change 2000 break; 2001 } 2002 break; 2003 case ICmpInst::ICMP_SGT: 2004 switch (RHSCC) { 2005 default: llvm_unreachable("Unknown integer condition code!"); 2006 case ICmpInst::ICMP_EQ: // (X s> 13 | X == 15) -> X > 13 2007 case ICmpInst::ICMP_SGT: // (X s> 13 | X s> 15) -> X > 13 2008 return LHS; 2009 case ICmpInst::ICMP_UGT: // (X s> 13 | X u> 15) -> no change 2010 break; 2011 case ICmpInst::ICMP_NE: // (X s> 13 | X != 15) -> true 2012 case ICmpInst::ICMP_SLT: // (X s> 13 | X s< 15) -> true 2013 return Builder->getTrue(); 2014 case ICmpInst::ICMP_ULT: // (X s> 13 | X u< 15) -> no change 2015 break; 2016 } 2017 break; 2018 } 2019 return nullptr; 2020 } 2021 2022 /// FoldOrOfFCmps - Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of 2023 /// instcombine, this returns a Value which should already be inserted into the 2024 /// function. 2025 Value *InstCombiner::FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) { 2026 if (LHS->getPredicate() == FCmpInst::FCMP_UNO && 2027 RHS->getPredicate() == FCmpInst::FCMP_UNO && 2028 LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType()) { 2029 if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1))) 2030 if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) { 2031 // If either of the constants are nans, then the whole thing returns 2032 // true. 2033 if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN()) 2034 return Builder->getTrue(); 2035 2036 // Otherwise, no need to compare the two constants, compare the 2037 // rest. 2038 return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0)); 2039 } 2040 2041 // Handle vector zeros. This occurs because the canonical form of 2042 // "fcmp uno x,x" is "fcmp uno x, 0". 2043 if (isa<ConstantAggregateZero>(LHS->getOperand(1)) && 2044 isa<ConstantAggregateZero>(RHS->getOperand(1))) 2045 return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0)); 2046 2047 return nullptr; 2048 } 2049 2050 Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1); 2051 Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1); 2052 FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate(); 2053 2054 if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) { 2055 // Swap RHS operands to match LHS. 2056 Op1CC = FCmpInst::getSwappedPredicate(Op1CC); 2057 std::swap(Op1LHS, Op1RHS); 2058 } 2059 if (Op0LHS == Op1LHS && Op0RHS == Op1RHS) { 2060 // Simplify (fcmp cc0 x, y) | (fcmp cc1 x, y). 2061 if (Op0CC == Op1CC) 2062 return Builder->CreateFCmp((FCmpInst::Predicate)Op0CC, Op0LHS, Op0RHS); 2063 if (Op0CC == FCmpInst::FCMP_TRUE || Op1CC == FCmpInst::FCMP_TRUE) 2064 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 2065 if (Op0CC == FCmpInst::FCMP_FALSE) 2066 return RHS; 2067 if (Op1CC == FCmpInst::FCMP_FALSE) 2068 return LHS; 2069 bool Op0Ordered; 2070 bool Op1Ordered; 2071 unsigned Op0Pred = getFCmpCode(Op0CC, Op0Ordered); 2072 unsigned Op1Pred = getFCmpCode(Op1CC, Op1Ordered); 2073 if (Op0Ordered == Op1Ordered) { 2074 // If both are ordered or unordered, return a new fcmp with 2075 // or'ed predicates. 2076 return getFCmpValue(Op0Ordered, Op0Pred|Op1Pred, Op0LHS, Op0RHS, Builder); 2077 } 2078 } 2079 return nullptr; 2080 } 2081 2082 /// FoldOrWithConstants - This helper function folds: 2083 /// 2084 /// ((A | B) & C1) | (B & C2) 2085 /// 2086 /// into: 2087 /// 2088 /// (A & C1) | B 2089 /// 2090 /// when the XOR of the two constants is "all ones" (-1). 2091 Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op, 2092 Value *A, Value *B, Value *C) { 2093 ConstantInt *CI1 = dyn_cast<ConstantInt>(C); 2094 if (!CI1) return nullptr; 2095 2096 Value *V1 = nullptr; 2097 ConstantInt *CI2 = nullptr; 2098 if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) return nullptr; 2099 2100 APInt Xor = CI1->getValue() ^ CI2->getValue(); 2101 if (!Xor.isAllOnesValue()) return nullptr; 2102 2103 if (V1 == A || V1 == B) { 2104 Value *NewOp = Builder->CreateAnd((V1 == A) ? B : A, CI1); 2105 return BinaryOperator::CreateOr(NewOp, V1); 2106 } 2107 2108 return nullptr; 2109 } 2110 2111 /// \brief This helper function folds: 2112 /// 2113 /// ((A | B) & C1) ^ (B & C2) 2114 /// 2115 /// into: 2116 /// 2117 /// (A & C1) ^ B 2118 /// 2119 /// when the XOR of the two constants is "all ones" (-1). 2120 Instruction *InstCombiner::FoldXorWithConstants(BinaryOperator &I, Value *Op, 2121 Value *A, Value *B, Value *C) { 2122 ConstantInt *CI1 = dyn_cast<ConstantInt>(C); 2123 if (!CI1) 2124 return nullptr; 2125 2126 Value *V1 = nullptr; 2127 ConstantInt *CI2 = nullptr; 2128 if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) 2129 return nullptr; 2130 2131 APInt Xor = CI1->getValue() ^ CI2->getValue(); 2132 if (!Xor.isAllOnesValue()) 2133 return nullptr; 2134 2135 if (V1 == A || V1 == B) { 2136 Value *NewOp = Builder->CreateAnd(V1 == A ? B : A, CI1); 2137 return BinaryOperator::CreateXor(NewOp, V1); 2138 } 2139 2140 return nullptr; 2141 } 2142 2143 Instruction *InstCombiner::visitOr(BinaryOperator &I) { 2144 bool Changed = SimplifyAssociativeOrCommutative(I); 2145 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2146 2147 if (Value *V = SimplifyVectorOp(I)) 2148 return ReplaceInstUsesWith(I, V); 2149 2150 if (Value *V = SimplifyOrInst(Op0, Op1, DL, TLI, DT, AC)) 2151 return ReplaceInstUsesWith(I, V); 2152 2153 // (A&B)|(A&C) -> A&(B|C) etc 2154 if (Value *V = SimplifyUsingDistributiveLaws(I)) 2155 return ReplaceInstUsesWith(I, V); 2156 2157 // See if we can simplify any instructions used by the instruction whose sole 2158 // purpose is to compute bits we don't care about. 2159 if (SimplifyDemandedInstructionBits(I)) 2160 return &I; 2161 2162 if (Value *V = SimplifyBSwap(I)) 2163 return ReplaceInstUsesWith(I, V); 2164 2165 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 2166 ConstantInt *C1 = nullptr; Value *X = nullptr; 2167 // (X & C1) | C2 --> (X | C2) & (C1|C2) 2168 // iff (C1 & C2) == 0. 2169 if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && 2170 (RHS->getValue() & C1->getValue()) != 0 && 2171 Op0->hasOneUse()) { 2172 Value *Or = Builder->CreateOr(X, RHS); 2173 Or->takeName(Op0); 2174 return BinaryOperator::CreateAnd(Or, 2175 Builder->getInt(RHS->getValue() | C1->getValue())); 2176 } 2177 2178 // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) 2179 if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && 2180 Op0->hasOneUse()) { 2181 Value *Or = Builder->CreateOr(X, RHS); 2182 Or->takeName(Op0); 2183 return BinaryOperator::CreateXor(Or, 2184 Builder->getInt(C1->getValue() & ~RHS->getValue())); 2185 } 2186 2187 // Try to fold constant and into select arguments. 2188 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 2189 if (Instruction *R = FoldOpIntoSelect(I, SI)) 2190 return R; 2191 2192 if (isa<PHINode>(Op0)) 2193 if (Instruction *NV = FoldOpIntoPhi(I)) 2194 return NV; 2195 } 2196 2197 Value *A = nullptr, *B = nullptr; 2198 ConstantInt *C1 = nullptr, *C2 = nullptr; 2199 2200 // (A | B) | C and A | (B | C) -> bswap if possible. 2201 // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible. 2202 if (match(Op0, m_Or(m_Value(), m_Value())) || 2203 match(Op1, m_Or(m_Value(), m_Value())) || 2204 (match(Op0, m_LogicalShift(m_Value(), m_Value())) && 2205 match(Op1, m_LogicalShift(m_Value(), m_Value())))) { 2206 if (Instruction *BSwap = MatchBSwap(I)) 2207 return BSwap; 2208 } 2209 2210 // (X^C)|Y -> (X|Y)^C iff Y&C == 0 2211 if (Op0->hasOneUse() && 2212 match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) && 2213 MaskedValueIsZero(Op1, C1->getValue(), 0, &I)) { 2214 Value *NOr = Builder->CreateOr(A, Op1); 2215 NOr->takeName(Op0); 2216 return BinaryOperator::CreateXor(NOr, C1); 2217 } 2218 2219 // Y|(X^C) -> (X|Y)^C iff Y&C == 0 2220 if (Op1->hasOneUse() && 2221 match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) && 2222 MaskedValueIsZero(Op0, C1->getValue(), 0, &I)) { 2223 Value *NOr = Builder->CreateOr(A, Op0); 2224 NOr->takeName(Op0); 2225 return BinaryOperator::CreateXor(NOr, C1); 2226 } 2227 2228 // ((~A & B) | A) -> (A | B) 2229 if (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) && 2230 match(Op1, m_Specific(A))) 2231 return BinaryOperator::CreateOr(A, B); 2232 2233 // ((A & B) | ~A) -> (~A | B) 2234 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 2235 match(Op1, m_Not(m_Specific(A)))) 2236 return BinaryOperator::CreateOr(Builder->CreateNot(A), B); 2237 2238 // (A & (~B)) | (A ^ B) -> (A ^ B) 2239 if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) && 2240 match(Op1, m_Xor(m_Specific(A), m_Specific(B)))) 2241 return BinaryOperator::CreateXor(A, B); 2242 2243 // (A ^ B) | ( A & (~B)) -> (A ^ B) 2244 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && 2245 match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B))))) 2246 return BinaryOperator::CreateXor(A, B); 2247 2248 // (A & C)|(B & D) 2249 Value *C = nullptr, *D = nullptr; 2250 if (match(Op0, m_And(m_Value(A), m_Value(C))) && 2251 match(Op1, m_And(m_Value(B), m_Value(D)))) { 2252 Value *V1 = nullptr, *V2 = nullptr; 2253 C1 = dyn_cast<ConstantInt>(C); 2254 C2 = dyn_cast<ConstantInt>(D); 2255 if (C1 && C2) { // (A & C1)|(B & C2) 2256 if ((C1->getValue() & C2->getValue()) == 0) { 2257 // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2) 2258 // iff (C1&C2) == 0 and (N&~C1) == 0 2259 if (match(A, m_Or(m_Value(V1), m_Value(V2))) && 2260 ((V1 == B && 2261 MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N) 2262 (V2 == B && 2263 MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V) 2264 return BinaryOperator::CreateAnd(A, 2265 Builder->getInt(C1->getValue()|C2->getValue())); 2266 // Or commutes, try both ways. 2267 if (match(B, m_Or(m_Value(V1), m_Value(V2))) && 2268 ((V1 == A && 2269 MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N) 2270 (V2 == A && 2271 MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V) 2272 return BinaryOperator::CreateAnd(B, 2273 Builder->getInt(C1->getValue()|C2->getValue())); 2274 2275 // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2) 2276 // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0. 2277 ConstantInt *C3 = nullptr, *C4 = nullptr; 2278 if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) && 2279 (C3->getValue() & ~C1->getValue()) == 0 && 2280 match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) && 2281 (C4->getValue() & ~C2->getValue()) == 0) { 2282 V2 = Builder->CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield"); 2283 return BinaryOperator::CreateAnd(V2, 2284 Builder->getInt(C1->getValue()|C2->getValue())); 2285 } 2286 } 2287 } 2288 2289 // (A & (C0?-1:0)) | (B & ~(C0?-1:0)) -> C0 ? A : B, and commuted variants. 2290 // Don't do this for vector select idioms, the code generator doesn't handle 2291 // them well yet. 2292 if (!I.getType()->isVectorTy()) { 2293 if (Instruction *Match = MatchSelectFromAndOr(A, B, C, D)) 2294 return Match; 2295 if (Instruction *Match = MatchSelectFromAndOr(B, A, D, C)) 2296 return Match; 2297 if (Instruction *Match = MatchSelectFromAndOr(C, B, A, D)) 2298 return Match; 2299 if (Instruction *Match = MatchSelectFromAndOr(D, A, B, C)) 2300 return Match; 2301 } 2302 2303 // ((A&~B)|(~A&B)) -> A^B 2304 if ((match(C, m_Not(m_Specific(D))) && 2305 match(B, m_Not(m_Specific(A))))) 2306 return BinaryOperator::CreateXor(A, D); 2307 // ((~B&A)|(~A&B)) -> A^B 2308 if ((match(A, m_Not(m_Specific(D))) && 2309 match(B, m_Not(m_Specific(C))))) 2310 return BinaryOperator::CreateXor(C, D); 2311 // ((A&~B)|(B&~A)) -> A^B 2312 if ((match(C, m_Not(m_Specific(B))) && 2313 match(D, m_Not(m_Specific(A))))) 2314 return BinaryOperator::CreateXor(A, B); 2315 // ((~B&A)|(B&~A)) -> A^B 2316 if ((match(A, m_Not(m_Specific(B))) && 2317 match(D, m_Not(m_Specific(C))))) 2318 return BinaryOperator::CreateXor(C, B); 2319 2320 // ((A|B)&1)|(B&-2) -> (A&1) | B 2321 if (match(A, m_Or(m_Value(V1), m_Specific(B))) || 2322 match(A, m_Or(m_Specific(B), m_Value(V1)))) { 2323 Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C); 2324 if (Ret) return Ret; 2325 } 2326 // (B&-2)|((A|B)&1) -> (A&1) | B 2327 if (match(B, m_Or(m_Specific(A), m_Value(V1))) || 2328 match(B, m_Or(m_Value(V1), m_Specific(A)))) { 2329 Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D); 2330 if (Ret) return Ret; 2331 } 2332 // ((A^B)&1)|(B&-2) -> (A&1) ^ B 2333 if (match(A, m_Xor(m_Value(V1), m_Specific(B))) || 2334 match(A, m_Xor(m_Specific(B), m_Value(V1)))) { 2335 Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C); 2336 if (Ret) return Ret; 2337 } 2338 // (B&-2)|((A^B)&1) -> (A&1) ^ B 2339 if (match(B, m_Xor(m_Specific(A), m_Value(V1))) || 2340 match(B, m_Xor(m_Value(V1), m_Specific(A)))) { 2341 Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D); 2342 if (Ret) return Ret; 2343 } 2344 } 2345 2346 // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C 2347 if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) 2348 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A)))) 2349 if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse()) 2350 return BinaryOperator::CreateOr(Op0, C); 2351 2352 // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C 2353 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B)))) 2354 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A)))) 2355 if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse()) 2356 return BinaryOperator::CreateOr(Op1, C); 2357 2358 // ((B | C) & A) | B -> B | (A & C) 2359 if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A)))) 2360 return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C)); 2361 2362 // (~A | ~B) == (~(A & B)) - De Morgan's Law 2363 if (Value *Op0NotVal = dyn_castNotVal(Op0)) 2364 if (Value *Op1NotVal = dyn_castNotVal(Op1)) 2365 if (Op0->hasOneUse() && Op1->hasOneUse()) { 2366 Value *And = Builder->CreateAnd(Op0NotVal, Op1NotVal, 2367 I.getName()+".demorgan"); 2368 return BinaryOperator::CreateNot(And); 2369 } 2370 2371 // Canonicalize xor to the RHS. 2372 bool SwappedForXor = false; 2373 if (match(Op0, m_Xor(m_Value(), m_Value()))) { 2374 std::swap(Op0, Op1); 2375 SwappedForXor = true; 2376 } 2377 2378 // A | ( A ^ B) -> A | B 2379 // A | (~A ^ B) -> A | ~B 2380 // (A & B) | (A ^ B) 2381 if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) { 2382 if (Op0 == A || Op0 == B) 2383 return BinaryOperator::CreateOr(A, B); 2384 2385 if (match(Op0, m_And(m_Specific(A), m_Specific(B))) || 2386 match(Op0, m_And(m_Specific(B), m_Specific(A)))) 2387 return BinaryOperator::CreateOr(A, B); 2388 2389 if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) { 2390 Value *Not = Builder->CreateNot(B, B->getName()+".not"); 2391 return BinaryOperator::CreateOr(Not, Op0); 2392 } 2393 if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) { 2394 Value *Not = Builder->CreateNot(A, A->getName()+".not"); 2395 return BinaryOperator::CreateOr(Not, Op0); 2396 } 2397 } 2398 2399 // A | ~(A | B) -> A | ~B 2400 // A | ~(A ^ B) -> A | ~B 2401 if (match(Op1, m_Not(m_Value(A)))) 2402 if (BinaryOperator *B = dyn_cast<BinaryOperator>(A)) 2403 if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) && 2404 Op1->hasOneUse() && (B->getOpcode() == Instruction::Or || 2405 B->getOpcode() == Instruction::Xor)) { 2406 Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) : 2407 B->getOperand(0); 2408 Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not"); 2409 return BinaryOperator::CreateOr(Not, Op0); 2410 } 2411 2412 // (A & B) | ((~A) ^ B) -> (~A ^ B) 2413 if (match(Op0, m_And(m_Value(A), m_Value(B))) && 2414 match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B)))) 2415 return BinaryOperator::CreateXor(Builder->CreateNot(A), B); 2416 2417 // ((~A) ^ B) | (A & B) -> (~A ^ B) 2418 if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) && 2419 match(Op1, m_And(m_Specific(A), m_Specific(B)))) 2420 return BinaryOperator::CreateXor(Builder->CreateNot(A), B); 2421 2422 if (SwappedForXor) 2423 std::swap(Op0, Op1); 2424 2425 { 2426 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0); 2427 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1); 2428 if (LHS && RHS) 2429 if (Value *Res = FoldOrOfICmps(LHS, RHS, &I)) 2430 return ReplaceInstUsesWith(I, Res); 2431 2432 // TODO: Make this recursive; it's a little tricky because an arbitrary 2433 // number of 'or' instructions might have to be created. 2434 Value *X, *Y; 2435 if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) { 2436 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 2437 if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I)) 2438 return ReplaceInstUsesWith(I, Builder->CreateOr(Res, Y)); 2439 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 2440 if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I)) 2441 return ReplaceInstUsesWith(I, Builder->CreateOr(Res, X)); 2442 } 2443 if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) { 2444 if (auto *Cmp = dyn_cast<ICmpInst>(X)) 2445 if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I)) 2446 return ReplaceInstUsesWith(I, Builder->CreateOr(Res, Y)); 2447 if (auto *Cmp = dyn_cast<ICmpInst>(Y)) 2448 if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I)) 2449 return ReplaceInstUsesWith(I, Builder->CreateOr(Res, X)); 2450 } 2451 } 2452 2453 // (fcmp uno x, c) | (fcmp uno y, c) -> (fcmp uno x, y) 2454 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 2455 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 2456 if (Value *Res = FoldOrOfFCmps(LHS, RHS)) 2457 return ReplaceInstUsesWith(I, Res); 2458 2459 // fold (or (cast A), (cast B)) -> (cast (or A, B)) 2460 if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2461 CastInst *Op1C = dyn_cast<CastInst>(Op1); 2462 if (Op1C && Op0C->getOpcode() == Op1C->getOpcode()) {// same cast kind ? 2463 Type *SrcTy = Op0C->getOperand(0)->getType(); 2464 if (SrcTy == Op1C->getOperand(0)->getType() && 2465 SrcTy->isIntOrIntVectorTy()) { 2466 Value *Op0COp = Op0C->getOperand(0), *Op1COp = Op1C->getOperand(0); 2467 2468 if ((!isa<ICmpInst>(Op0COp) || !isa<ICmpInst>(Op1COp)) && 2469 // Only do this if the casts both really cause code to be 2470 // generated. 2471 ShouldOptimizeCast(Op0C->getOpcode(), Op0COp, I.getType()) && 2472 ShouldOptimizeCast(Op1C->getOpcode(), Op1COp, I.getType())) { 2473 Value *NewOp = Builder->CreateOr(Op0COp, Op1COp, I.getName()); 2474 return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 2475 } 2476 2477 // If this is or(cast(icmp), cast(icmp)), try to fold this even if the 2478 // cast is otherwise not optimizable. This happens for vector sexts. 2479 if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1COp)) 2480 if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0COp)) 2481 if (Value *Res = FoldOrOfICmps(LHS, RHS, &I)) 2482 return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 2483 2484 // If this is or(cast(fcmp), cast(fcmp)), try to fold this even if the 2485 // cast is otherwise not optimizable. This happens for vector sexts. 2486 if (FCmpInst *RHS = dyn_cast<FCmpInst>(Op1COp)) 2487 if (FCmpInst *LHS = dyn_cast<FCmpInst>(Op0COp)) 2488 if (Value *Res = FoldOrOfFCmps(LHS, RHS)) 2489 return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 2490 } 2491 } 2492 } 2493 2494 // or(sext(A), B) -> A ? -1 : B where A is an i1 2495 // or(A, sext(B)) -> B ? -1 : A where B is an i1 2496 if (match(Op0, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1)) 2497 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1); 2498 if (match(Op1, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1)) 2499 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0); 2500 2501 // Note: If we've gotten to the point of visiting the outer OR, then the 2502 // inner one couldn't be simplified. If it was a constant, then it won't 2503 // be simplified by a later pass either, so we try swapping the inner/outer 2504 // ORs in the hopes that we'll be able to simplify it this way. 2505 // (X|C) | V --> (X|V) | C 2506 if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) && 2507 match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) { 2508 Value *Inner = Builder->CreateOr(A, Op1); 2509 Inner->takeName(Op0); 2510 return BinaryOperator::CreateOr(Inner, C1); 2511 } 2512 2513 // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D)) 2514 // Since this OR statement hasn't been optimized further yet, we hope 2515 // that this transformation will allow the new ORs to be optimized. 2516 { 2517 Value *X = nullptr, *Y = nullptr; 2518 if (Op0->hasOneUse() && Op1->hasOneUse() && 2519 match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) && 2520 match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) { 2521 Value *orTrue = Builder->CreateOr(A, C); 2522 Value *orFalse = Builder->CreateOr(B, D); 2523 return SelectInst::Create(X, orTrue, orFalse); 2524 } 2525 } 2526 2527 return Changed ? &I : nullptr; 2528 } 2529 2530 Instruction *InstCombiner::visitXor(BinaryOperator &I) { 2531 bool Changed = SimplifyAssociativeOrCommutative(I); 2532 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2533 2534 if (Value *V = SimplifyVectorOp(I)) 2535 return ReplaceInstUsesWith(I, V); 2536 2537 if (Value *V = SimplifyXorInst(Op0, Op1, DL, TLI, DT, AC)) 2538 return ReplaceInstUsesWith(I, V); 2539 2540 // (A&B)^(A&C) -> A&(B^C) etc 2541 if (Value *V = SimplifyUsingDistributiveLaws(I)) 2542 return ReplaceInstUsesWith(I, V); 2543 2544 // See if we can simplify any instructions used by the instruction whose sole 2545 // purpose is to compute bits we don't care about. 2546 if (SimplifyDemandedInstructionBits(I)) 2547 return &I; 2548 2549 if (Value *V = SimplifyBSwap(I)) 2550 return ReplaceInstUsesWith(I, V); 2551 2552 // Is this a ~ operation? 2553 if (Value *NotOp = dyn_castNotVal(&I)) { 2554 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) { 2555 if (Op0I->getOpcode() == Instruction::And || 2556 Op0I->getOpcode() == Instruction::Or) { 2557 // ~(~X & Y) --> (X | ~Y) - De Morgan's Law 2558 // ~(~X | Y) === (X & ~Y) - De Morgan's Law 2559 if (dyn_castNotVal(Op0I->getOperand(1))) 2560 Op0I->swapOperands(); 2561 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) { 2562 Value *NotY = 2563 Builder->CreateNot(Op0I->getOperand(1), 2564 Op0I->getOperand(1)->getName()+".not"); 2565 if (Op0I->getOpcode() == Instruction::And) 2566 return BinaryOperator::CreateOr(Op0NotVal, NotY); 2567 return BinaryOperator::CreateAnd(Op0NotVal, NotY); 2568 } 2569 2570 // ~(X & Y) --> (~X | ~Y) - De Morgan's Law 2571 // ~(X | Y) === (~X & ~Y) - De Morgan's Law 2572 if (IsFreeToInvert(Op0I->getOperand(0), 2573 Op0I->getOperand(0)->hasOneUse()) && 2574 IsFreeToInvert(Op0I->getOperand(1), 2575 Op0I->getOperand(1)->hasOneUse())) { 2576 Value *NotX = 2577 Builder->CreateNot(Op0I->getOperand(0), "notlhs"); 2578 Value *NotY = 2579 Builder->CreateNot(Op0I->getOperand(1), "notrhs"); 2580 if (Op0I->getOpcode() == Instruction::And) 2581 return BinaryOperator::CreateOr(NotX, NotY); 2582 return BinaryOperator::CreateAnd(NotX, NotY); 2583 } 2584 2585 } else if (Op0I->getOpcode() == Instruction::AShr) { 2586 // ~(~X >>s Y) --> (X >>s Y) 2587 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) 2588 return BinaryOperator::CreateAShr(Op0NotVal, Op0I->getOperand(1)); 2589 } 2590 } 2591 } 2592 2593 if (Constant *RHS = dyn_cast<Constant>(Op1)) { 2594 if (RHS->isAllOnesValue() && Op0->hasOneUse()) 2595 // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B 2596 if (CmpInst *CI = dyn_cast<CmpInst>(Op0)) 2597 return CmpInst::Create(CI->getOpcode(), 2598 CI->getInversePredicate(), 2599 CI->getOperand(0), CI->getOperand(1)); 2600 } 2601 2602 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 2603 // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp). 2604 if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2605 if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) { 2606 if (CI->hasOneUse() && Op0C->hasOneUse()) { 2607 Instruction::CastOps Opcode = Op0C->getOpcode(); 2608 if ((Opcode == Instruction::ZExt || Opcode == Instruction::SExt) && 2609 (RHS == ConstantExpr::getCast(Opcode, Builder->getTrue(), 2610 Op0C->getDestTy()))) { 2611 CI->setPredicate(CI->getInversePredicate()); 2612 return CastInst::Create(Opcode, CI, Op0C->getType()); 2613 } 2614 } 2615 } 2616 } 2617 2618 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 2619 // ~(c-X) == X-c-1 == X+(-c-1) 2620 if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue()) 2621 if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) { 2622 Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C); 2623 Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C, 2624 ConstantInt::get(I.getType(), 1)); 2625 return BinaryOperator::CreateAdd(Op0I->getOperand(1), ConstantRHS); 2626 } 2627 2628 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) { 2629 if (Op0I->getOpcode() == Instruction::Add) { 2630 // ~(X-c) --> (-c-1)-X 2631 if (RHS->isAllOnesValue()) { 2632 Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI); 2633 return BinaryOperator::CreateSub( 2634 ConstantExpr::getSub(NegOp0CI, 2635 ConstantInt::get(I.getType(), 1)), 2636 Op0I->getOperand(0)); 2637 } else if (RHS->getValue().isSignBit()) { 2638 // (X + C) ^ signbit -> (X + C + signbit) 2639 Constant *C = Builder->getInt(RHS->getValue() + Op0CI->getValue()); 2640 return BinaryOperator::CreateAdd(Op0I->getOperand(0), C); 2641 2642 } 2643 } else if (Op0I->getOpcode() == Instruction::Or) { 2644 // (X|C1)^C2 -> X^(C1|C2) iff X&~C1 == 0 2645 if (MaskedValueIsZero(Op0I->getOperand(0), Op0CI->getValue(), 2646 0, &I)) { 2647 Constant *NewRHS = ConstantExpr::getOr(Op0CI, RHS); 2648 // Anything in both C1 and C2 is known to be zero, remove it from 2649 // NewRHS. 2650 Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHS); 2651 NewRHS = ConstantExpr::getAnd(NewRHS, 2652 ConstantExpr::getNot(CommonBits)); 2653 Worklist.Add(Op0I); 2654 I.setOperand(0, Op0I->getOperand(0)); 2655 I.setOperand(1, NewRHS); 2656 return &I; 2657 } 2658 } else if (Op0I->getOpcode() == Instruction::LShr) { 2659 // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3) 2660 // E1 = "X ^ C1" 2661 BinaryOperator *E1; 2662 ConstantInt *C1; 2663 if (Op0I->hasOneUse() && 2664 (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) && 2665 E1->getOpcode() == Instruction::Xor && 2666 (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) { 2667 // fold (C1 >> C2) ^ C3 2668 ConstantInt *C2 = Op0CI, *C3 = RHS; 2669 APInt FoldConst = C1->getValue().lshr(C2->getValue()); 2670 FoldConst ^= C3->getValue(); 2671 // Prepare the two operands. 2672 Value *Opnd0 = Builder->CreateLShr(E1->getOperand(0), C2); 2673 Opnd0->takeName(Op0I); 2674 cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc()); 2675 Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst); 2676 2677 return BinaryOperator::CreateXor(Opnd0, FoldVal); 2678 } 2679 } 2680 } 2681 } 2682 2683 // Try to fold constant and into select arguments. 2684 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 2685 if (Instruction *R = FoldOpIntoSelect(I, SI)) 2686 return R; 2687 if (isa<PHINode>(Op0)) 2688 if (Instruction *NV = FoldOpIntoPhi(I)) 2689 return NV; 2690 } 2691 2692 BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1); 2693 if (Op1I) { 2694 Value *A, *B; 2695 if (match(Op1I, m_Or(m_Value(A), m_Value(B)))) { 2696 if (A == Op0) { // B^(B|A) == (A|B)^B 2697 Op1I->swapOperands(); 2698 I.swapOperands(); 2699 std::swap(Op0, Op1); 2700 } else if (B == Op0) { // B^(A|B) == (A|B)^B 2701 I.swapOperands(); // Simplified below. 2702 std::swap(Op0, Op1); 2703 } 2704 } else if (match(Op1I, m_And(m_Value(A), m_Value(B))) && 2705 Op1I->hasOneUse()){ 2706 if (A == Op0) { // A^(A&B) -> A^(B&A) 2707 Op1I->swapOperands(); 2708 std::swap(A, B); 2709 } 2710 if (B == Op0) { // A^(B&A) -> (B&A)^A 2711 I.swapOperands(); // Simplified below. 2712 std::swap(Op0, Op1); 2713 } 2714 } 2715 } 2716 2717 BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0); 2718 if (Op0I) { 2719 Value *A, *B; 2720 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) && 2721 Op0I->hasOneUse()) { 2722 if (A == Op1) // (B|A)^B == (A|B)^B 2723 std::swap(A, B); 2724 if (B == Op1) // (A|B)^B == A & ~B 2725 return BinaryOperator::CreateAnd(A, Builder->CreateNot(Op1)); 2726 } else if (match(Op0I, m_And(m_Value(A), m_Value(B))) && 2727 Op0I->hasOneUse()){ 2728 if (A == Op1) // (A&B)^A -> (B&A)^A 2729 std::swap(A, B); 2730 if (B == Op1 && // (B&A)^A == ~B & A 2731 !isa<ConstantInt>(Op1)) { // Canonical form is (B&C)^C 2732 return BinaryOperator::CreateAnd(Builder->CreateNot(A), Op1); 2733 } 2734 } 2735 } 2736 2737 if (Op0I && Op1I) { 2738 Value *A, *B, *C, *D; 2739 // (A & B)^(A | B) -> A ^ B 2740 if (match(Op0I, m_And(m_Value(A), m_Value(B))) && 2741 match(Op1I, m_Or(m_Value(C), m_Value(D)))) { 2742 if ((A == C && B == D) || (A == D && B == C)) 2743 return BinaryOperator::CreateXor(A, B); 2744 } 2745 // (A | B)^(A & B) -> A ^ B 2746 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) && 2747 match(Op1I, m_And(m_Value(C), m_Value(D)))) { 2748 if ((A == C && B == D) || (A == D && B == C)) 2749 return BinaryOperator::CreateXor(A, B); 2750 } 2751 // (A | ~B) ^ (~A | B) -> A ^ B 2752 if (match(Op0I, m_Or(m_Value(A), m_Not(m_Value(B)))) && 2753 match(Op1I, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) { 2754 return BinaryOperator::CreateXor(A, B); 2755 } 2756 // (~A | B) ^ (A | ~B) -> A ^ B 2757 if (match(Op0I, m_Or(m_Not(m_Value(A)), m_Value(B))) && 2758 match(Op1I, m_Or(m_Specific(A), m_Not(m_Specific(B))))) { 2759 return BinaryOperator::CreateXor(A, B); 2760 } 2761 // (A & ~B) ^ (~A & B) -> A ^ B 2762 if (match(Op0I, m_And(m_Value(A), m_Not(m_Value(B)))) && 2763 match(Op1I, m_And(m_Not(m_Specific(A)), m_Specific(B)))) { 2764 return BinaryOperator::CreateXor(A, B); 2765 } 2766 // (~A & B) ^ (A & ~B) -> A ^ B 2767 if (match(Op0I, m_And(m_Not(m_Value(A)), m_Value(B))) && 2768 match(Op1I, m_And(m_Specific(A), m_Not(m_Specific(B))))) { 2769 return BinaryOperator::CreateXor(A, B); 2770 } 2771 // (A ^ C)^(A | B) -> ((~A) & B) ^ C 2772 if (match(Op0I, m_Xor(m_Value(D), m_Value(C))) && 2773 match(Op1I, m_Or(m_Value(A), m_Value(B)))) { 2774 if (D == A) 2775 return BinaryOperator::CreateXor( 2776 Builder->CreateAnd(Builder->CreateNot(A), B), C); 2777 if (D == B) 2778 return BinaryOperator::CreateXor( 2779 Builder->CreateAnd(Builder->CreateNot(B), A), C); 2780 } 2781 // (A | B)^(A ^ C) -> ((~A) & B) ^ C 2782 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) && 2783 match(Op1I, m_Xor(m_Value(D), m_Value(C)))) { 2784 if (D == A) 2785 return BinaryOperator::CreateXor( 2786 Builder->CreateAnd(Builder->CreateNot(A), B), C); 2787 if (D == B) 2788 return BinaryOperator::CreateXor( 2789 Builder->CreateAnd(Builder->CreateNot(B), A), C); 2790 } 2791 // (A & B) ^ (A ^ B) -> (A | B) 2792 if (match(Op0I, m_And(m_Value(A), m_Value(B))) && 2793 match(Op1I, m_Xor(m_Specific(A), m_Specific(B)))) 2794 return BinaryOperator::CreateOr(A, B); 2795 // (A ^ B) ^ (A & B) -> (A | B) 2796 if (match(Op0I, m_Xor(m_Value(A), m_Value(B))) && 2797 match(Op1I, m_And(m_Specific(A), m_Specific(B)))) 2798 return BinaryOperator::CreateOr(A, B); 2799 } 2800 2801 Value *A = nullptr, *B = nullptr; 2802 // (A & ~B) ^ (~A) -> ~(A & B) 2803 if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) && 2804 match(Op1, m_Not(m_Specific(A)))) 2805 return BinaryOperator::CreateNot(Builder->CreateAnd(A, B)); 2806 2807 // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B) 2808 if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1))) 2809 if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0))) 2810 if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) { 2811 if (LHS->getOperand(0) == RHS->getOperand(1) && 2812 LHS->getOperand(1) == RHS->getOperand(0)) 2813 LHS->swapOperands(); 2814 if (LHS->getOperand(0) == RHS->getOperand(0) && 2815 LHS->getOperand(1) == RHS->getOperand(1)) { 2816 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 2817 unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS); 2818 bool isSigned = LHS->isSigned() || RHS->isSigned(); 2819 return ReplaceInstUsesWith(I, 2820 getNewICmpValue(isSigned, Code, Op0, Op1, 2821 Builder)); 2822 } 2823 } 2824 2825 // fold (xor (cast A), (cast B)) -> (cast (xor A, B)) 2826 if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2827 if (CastInst *Op1C = dyn_cast<CastInst>(Op1)) 2828 if (Op0C->getOpcode() == Op1C->getOpcode()) { // same cast kind? 2829 Type *SrcTy = Op0C->getOperand(0)->getType(); 2830 if (SrcTy == Op1C->getOperand(0)->getType() && SrcTy->isIntegerTy() && 2831 // Only do this if the casts both really cause code to be generated. 2832 ShouldOptimizeCast(Op0C->getOpcode(), Op0C->getOperand(0), 2833 I.getType()) && 2834 ShouldOptimizeCast(Op1C->getOpcode(), Op1C->getOperand(0), 2835 I.getType())) { 2836 Value *NewOp = Builder->CreateXor(Op0C->getOperand(0), 2837 Op1C->getOperand(0), I.getName()); 2838 return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 2839 } 2840 } 2841 } 2842 2843 return Changed ? &I : nullptr; 2844 } 2845