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