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