1202375Srdivacky//===- InstCombineAndOrXor.cpp --------------------------------------------===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file implements the visitAnd, visitOr, and visitXor functions. 11202375Srdivacky// 12202375Srdivacky//===----------------------------------------------------------------------===// 13202375Srdivacky 14202375Srdivacky#include "InstCombine.h" 15202375Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 16252723Sdim#include "llvm/IR/Intrinsics.h" 17221345Sdim#include "llvm/Support/ConstantRange.h" 18202375Srdivacky#include "llvm/Support/PatternMatch.h" 19252723Sdim#include "llvm/Transforms/Utils/CmpInstAnalysis.h" 20202375Srdivackyusing namespace llvm; 21202375Srdivackyusing namespace PatternMatch; 22202375Srdivacky 23202375Srdivacky 24202375Srdivacky/// AddOne - Add one to a ConstantInt. 25252723Sdimstatic Constant *AddOne(ConstantInt *C) { 26252723Sdim return ConstantInt::get(C->getContext(), C->getValue() + 1); 27202375Srdivacky} 28202375Srdivacky/// SubOne - Subtract one from a ConstantInt. 29202375Srdivackystatic Constant *SubOne(ConstantInt *C) { 30202375Srdivacky return ConstantInt::get(C->getContext(), C->getValue()-1); 31202375Srdivacky} 32202375Srdivacky 33202375Srdivacky/// isFreeToInvert - Return true if the specified value is free to invert (apply 34202375Srdivacky/// ~ to). This happens in cases where the ~ can be eliminated. 35202375Srdivackystatic inline bool isFreeToInvert(Value *V) { 36202375Srdivacky // ~(~(X)) -> X. 37202375Srdivacky if (BinaryOperator::isNot(V)) 38202375Srdivacky return true; 39252723Sdim 40202375Srdivacky // Constants can be considered to be not'ed values. 41202375Srdivacky if (isa<ConstantInt>(V)) 42202375Srdivacky return true; 43252723Sdim 44202375Srdivacky // Compares can be inverted if they have a single use. 45202375Srdivacky if (CmpInst *CI = dyn_cast<CmpInst>(V)) 46202375Srdivacky return CI->hasOneUse(); 47252723Sdim 48202375Srdivacky return false; 49202375Srdivacky} 50202375Srdivacky 51202375Srdivackystatic inline Value *dyn_castNotVal(Value *V) { 52202375Srdivacky // If this is not(not(x)) don't return that this is a not: we want the two 53202375Srdivacky // not's to be folded first. 54202375Srdivacky if (BinaryOperator::isNot(V)) { 55202375Srdivacky Value *Operand = BinaryOperator::getNotArgument(V); 56202375Srdivacky if (!isFreeToInvert(Operand)) 57202375Srdivacky return Operand; 58202375Srdivacky } 59252723Sdim 60202375Srdivacky // Constants can be considered to be not'ed values... 61202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(V)) 62202375Srdivacky return ConstantInt::get(C->getType(), ~C->getValue()); 63202375Srdivacky return 0; 64202375Srdivacky} 65202375Srdivacky 66202375Srdivacky/// getFCmpCode - Similar to getICmpCode but for FCmpInst. This encodes a fcmp 67202375Srdivacky/// predicate into a three bit mask. It also returns whether it is an ordered 68202375Srdivacky/// predicate by reference. 69202375Srdivackystatic unsigned getFCmpCode(FCmpInst::Predicate CC, bool &isOrdered) { 70202375Srdivacky isOrdered = false; 71202375Srdivacky switch (CC) { 72202375Srdivacky case FCmpInst::FCMP_ORD: isOrdered = true; return 0; // 000 73202375Srdivacky case FCmpInst::FCMP_UNO: return 0; // 000 74202375Srdivacky case FCmpInst::FCMP_OGT: isOrdered = true; return 1; // 001 75202375Srdivacky case FCmpInst::FCMP_UGT: return 1; // 001 76202375Srdivacky case FCmpInst::FCMP_OEQ: isOrdered = true; return 2; // 010 77202375Srdivacky case FCmpInst::FCMP_UEQ: return 2; // 010 78202375Srdivacky case FCmpInst::FCMP_OGE: isOrdered = true; return 3; // 011 79202375Srdivacky case FCmpInst::FCMP_UGE: return 3; // 011 80202375Srdivacky case FCmpInst::FCMP_OLT: isOrdered = true; return 4; // 100 81202375Srdivacky case FCmpInst::FCMP_ULT: return 4; // 100 82202375Srdivacky case FCmpInst::FCMP_ONE: isOrdered = true; return 5; // 101 83202375Srdivacky case FCmpInst::FCMP_UNE: return 5; // 101 84202375Srdivacky case FCmpInst::FCMP_OLE: isOrdered = true; return 6; // 110 85202375Srdivacky case FCmpInst::FCMP_ULE: return 6; // 110 86202375Srdivacky // True -> 7 87202375Srdivacky default: 88202375Srdivacky // Not expecting FCMP_FALSE and FCMP_TRUE; 89202375Srdivacky llvm_unreachable("Unexpected FCmp predicate!"); 90202375Srdivacky } 91202375Srdivacky} 92202375Srdivacky 93235633Sdim/// getNewICmpValue - This is the complement of getICmpCode, which turns an 94252723Sdim/// opcode and two operands into either a constant true or false, or a brand 95202375Srdivacky/// new ICmp instruction. The sign is passed in to determine which kind 96202375Srdivacky/// of predicate to use in the new icmp instruction. 97235633Sdimstatic Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, 98235633Sdim InstCombiner::BuilderTy *Builder) { 99235633Sdim ICmpInst::Predicate NewPred; 100235633Sdim if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred)) 101235633Sdim return NewConstant; 102235633Sdim return Builder->CreateICmp(NewPred, LHS, RHS); 103202375Srdivacky} 104202375Srdivacky 105202375Srdivacky/// getFCmpValue - This is the complement of getFCmpCode, which turns an 106202375Srdivacky/// opcode and two operands into either a FCmp instruction. isordered is passed 107202375Srdivacky/// in to determine which kind of predicate to use in the new fcmp instruction. 108202375Srdivackystatic Value *getFCmpValue(bool isordered, unsigned code, 109204792Srdivacky Value *LHS, Value *RHS, 110204792Srdivacky InstCombiner::BuilderTy *Builder) { 111204792Srdivacky CmpInst::Predicate Pred; 112202375Srdivacky switch (code) { 113235633Sdim default: llvm_unreachable("Illegal FCmp code!"); 114204792Srdivacky case 0: Pred = isordered ? FCmpInst::FCMP_ORD : FCmpInst::FCMP_UNO; break; 115204792Srdivacky case 1: Pred = isordered ? FCmpInst::FCMP_OGT : FCmpInst::FCMP_UGT; break; 116204792Srdivacky case 2: Pred = isordered ? FCmpInst::FCMP_OEQ : FCmpInst::FCMP_UEQ; break; 117204792Srdivacky case 3: Pred = isordered ? FCmpInst::FCMP_OGE : FCmpInst::FCMP_UGE; break; 118204792Srdivacky case 4: Pred = isordered ? FCmpInst::FCMP_OLT : FCmpInst::FCMP_ULT; break; 119204792Srdivacky case 5: Pred = isordered ? FCmpInst::FCMP_ONE : FCmpInst::FCMP_UNE; break; 120204792Srdivacky case 6: Pred = isordered ? FCmpInst::FCMP_OLE : FCmpInst::FCMP_ULE; break; 121252723Sdim case 7: 122218893Sdim if (!isordered) return ConstantInt::getTrue(LHS->getContext()); 123218893Sdim Pred = FCmpInst::FCMP_ORD; break; 124202375Srdivacky } 125204792Srdivacky return Builder->CreateFCmp(Pred, LHS, RHS); 126202375Srdivacky} 127202375Srdivacky 128202375Srdivacky// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where 129202375Srdivacky// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is 130202375Srdivacky// guaranteed to be a binary operator. 131202375SrdivackyInstruction *InstCombiner::OptAndOp(Instruction *Op, 132202375Srdivacky ConstantInt *OpRHS, 133202375Srdivacky ConstantInt *AndRHS, 134202375Srdivacky BinaryOperator &TheAnd) { 135202375Srdivacky Value *X = Op->getOperand(0); 136202375Srdivacky Constant *Together = 0; 137202375Srdivacky if (!Op->isShift()) 138202375Srdivacky Together = ConstantExpr::getAnd(AndRHS, OpRHS); 139202375Srdivacky 140202375Srdivacky switch (Op->getOpcode()) { 141202375Srdivacky case Instruction::Xor: 142202375Srdivacky if (Op->hasOneUse()) { 143202375Srdivacky // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2) 144202375Srdivacky Value *And = Builder->CreateAnd(X, AndRHS); 145202375Srdivacky And->takeName(Op); 146202375Srdivacky return BinaryOperator::CreateXor(And, Together); 147202375Srdivacky } 148202375Srdivacky break; 149202375Srdivacky case Instruction::Or: 150218893Sdim if (Op->hasOneUse()){ 151218893Sdim if (Together != OpRHS) { 152218893Sdim // (X | C1) & C2 --> (X | (C1&C2)) & C2 153218893Sdim Value *Or = Builder->CreateOr(X, Together); 154218893Sdim Or->takeName(Op); 155218893Sdim return BinaryOperator::CreateAnd(Or, AndRHS); 156218893Sdim } 157252723Sdim 158218893Sdim ConstantInt *TogetherCI = dyn_cast<ConstantInt>(Together); 159218893Sdim if (TogetherCI && !TogetherCI->isZero()){ 160218893Sdim // (X | C1) & C2 --> (X & (C2^(C1&C2))) | C1 161218893Sdim // NOTE: This reduces the number of bits set in the & mask, which 162218893Sdim // can expose opportunities for store narrowing. 163218893Sdim Together = ConstantExpr::getXor(AndRHS, Together); 164218893Sdim Value *And = Builder->CreateAnd(X, Together); 165218893Sdim And->takeName(Op); 166218893Sdim return BinaryOperator::CreateOr(And, OpRHS); 167218893Sdim } 168202375Srdivacky } 169252723Sdim 170202375Srdivacky break; 171202375Srdivacky case Instruction::Add: 172202375Srdivacky if (Op->hasOneUse()) { 173202375Srdivacky // Adding a one to a single bit bit-field should be turned into an XOR 174202375Srdivacky // of the bit. First thing to check is to see if this AND is with a 175202375Srdivacky // single bit constant. 176263509Sdim const APInt &AndRHSV = AndRHS->getValue(); 177202375Srdivacky 178202375Srdivacky // If there is only one bit set. 179202375Srdivacky if (AndRHSV.isPowerOf2()) { 180202375Srdivacky // Ok, at this point, we know that we are masking the result of the 181202375Srdivacky // ADD down to exactly one bit. If the constant we are adding has 182202375Srdivacky // no bits set below this bit, then we can eliminate the ADD. 183263509Sdim const APInt& AddRHS = OpRHS->getValue(); 184202375Srdivacky 185202375Srdivacky // Check to see if any bits below the one bit set in AndRHSV are set. 186202375Srdivacky if ((AddRHS & (AndRHSV-1)) == 0) { 187202375Srdivacky // If not, the only thing that can effect the output of the AND is 188202375Srdivacky // the bit specified by AndRHSV. If that bit is set, the effect of 189202375Srdivacky // the XOR is to toggle the bit. If it is clear, then the ADD has 190202375Srdivacky // no effect. 191202375Srdivacky if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop 192202375Srdivacky TheAnd.setOperand(0, X); 193202375Srdivacky return &TheAnd; 194202375Srdivacky } else { 195202375Srdivacky // Pull the XOR out of the AND. 196202375Srdivacky Value *NewAnd = Builder->CreateAnd(X, AndRHS); 197202375Srdivacky NewAnd->takeName(Op); 198202375Srdivacky return BinaryOperator::CreateXor(NewAnd, AndRHS); 199202375Srdivacky } 200202375Srdivacky } 201202375Srdivacky } 202202375Srdivacky } 203202375Srdivacky break; 204202375Srdivacky 205202375Srdivacky case Instruction::Shl: { 206202375Srdivacky // We know that the AND will not produce any of the bits shifted in, so if 207202375Srdivacky // the anded constant includes them, clear them now! 208202375Srdivacky // 209202375Srdivacky uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 210202375Srdivacky uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 211202375Srdivacky APInt ShlMask(APInt::getHighBitsSet(BitWidth, BitWidth-OpRHSVal)); 212263509Sdim ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShlMask); 213202375Srdivacky 214218893Sdim if (CI->getValue() == ShlMask) 215218893Sdim // Masking out bits that the shift already masks. 216202375Srdivacky return ReplaceInstUsesWith(TheAnd, Op); // No need for the and. 217252723Sdim 218218893Sdim if (CI != AndRHS) { // Reducing bits set in and. 219202375Srdivacky TheAnd.setOperand(1, CI); 220202375Srdivacky return &TheAnd; 221202375Srdivacky } 222202375Srdivacky break; 223202375Srdivacky } 224202375Srdivacky case Instruction::LShr: { 225202375Srdivacky // We know that the AND will not produce any of the bits shifted in, so if 226202375Srdivacky // the anded constant includes them, clear them now! This only applies to 227202375Srdivacky // unsigned shifts, because a signed shr may bring in set bits! 228202375Srdivacky // 229202375Srdivacky uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 230202375Srdivacky uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 231202375Srdivacky APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal)); 232263509Sdim ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShrMask); 233202375Srdivacky 234218893Sdim if (CI->getValue() == ShrMask) 235218893Sdim // Masking out bits that the shift already masks. 236202375Srdivacky return ReplaceInstUsesWith(TheAnd, Op); 237252723Sdim 238218893Sdim if (CI != AndRHS) { 239202375Srdivacky TheAnd.setOperand(1, CI); // Reduce bits set in and cst. 240202375Srdivacky return &TheAnd; 241202375Srdivacky } 242202375Srdivacky break; 243202375Srdivacky } 244202375Srdivacky case Instruction::AShr: 245202375Srdivacky // Signed shr. 246202375Srdivacky // See if this is shifting in some sign extension, then masking it out 247202375Srdivacky // with an and. 248202375Srdivacky if (Op->hasOneUse()) { 249202375Srdivacky uint32_t BitWidth = AndRHS->getType()->getBitWidth(); 250202375Srdivacky uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth); 251202375Srdivacky APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal)); 252263509Sdim Constant *C = Builder->getInt(AndRHS->getValue() & ShrMask); 253202375Srdivacky if (C == AndRHS) { // Masking out bits shifted in. 254202375Srdivacky // (Val ashr C1) & C2 -> (Val lshr C1) & C2 255202375Srdivacky // Make the argument unsigned. 256202375Srdivacky Value *ShVal = Op->getOperand(0); 257202375Srdivacky ShVal = Builder->CreateLShr(ShVal, OpRHS, Op->getName()); 258202375Srdivacky return BinaryOperator::CreateAnd(ShVal, AndRHS, TheAnd.getName()); 259202375Srdivacky } 260202375Srdivacky } 261202375Srdivacky break; 262202375Srdivacky } 263202375Srdivacky return 0; 264202375Srdivacky} 265202375Srdivacky 266252723Sdim/// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise 267252723Sdim/// (V < Lo || V >= Hi). In practice, we emit the more efficient 268252723Sdim/// (V-Lo) \<u Hi-Lo. This method expects that Lo <= Hi. isSigned indicates 269202375Srdivacky/// whether to treat the V, Lo and HI as signed or not. IB is the location to 270202375Srdivacky/// insert new instructions. 271204792SrdivackyValue *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi, 272204792Srdivacky bool isSigned, bool Inside) { 273252723Sdim assert(cast<ConstantInt>(ConstantExpr::getICmp((isSigned ? 274202375Srdivacky ICmpInst::ICMP_SLE:ICmpInst::ICMP_ULE), Lo, Hi))->getZExtValue() && 275202375Srdivacky "Lo is not <= Hi in range emission code!"); 276252723Sdim 277202375Srdivacky if (Inside) { 278202375Srdivacky if (Lo == Hi) // Trivially false. 279263509Sdim return Builder->getFalse(); 280202375Srdivacky 281202375Srdivacky // V >= Min && V < Hi --> V < Hi 282202375Srdivacky if (cast<ConstantInt>(Lo)->isMinValue(isSigned)) { 283252723Sdim ICmpInst::Predicate pred = (isSigned ? 284202375Srdivacky ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT); 285204792Srdivacky return Builder->CreateICmp(pred, V, Hi); 286202375Srdivacky } 287202375Srdivacky 288202375Srdivacky // Emit V-Lo <u Hi-Lo 289202375Srdivacky Constant *NegLo = ConstantExpr::getNeg(Lo); 290202375Srdivacky Value *Add = Builder->CreateAdd(V, NegLo, V->getName()+".off"); 291202375Srdivacky Constant *UpperBound = ConstantExpr::getAdd(NegLo, Hi); 292204792Srdivacky return Builder->CreateICmpULT(Add, UpperBound); 293202375Srdivacky } 294202375Srdivacky 295202375Srdivacky if (Lo == Hi) // Trivially true. 296263509Sdim return Builder->getTrue(); 297202375Srdivacky 298202375Srdivacky // V < Min || V >= Hi -> V > Hi-1 299202375Srdivacky Hi = SubOne(cast<ConstantInt>(Hi)); 300202375Srdivacky if (cast<ConstantInt>(Lo)->isMinValue(isSigned)) { 301252723Sdim ICmpInst::Predicate pred = (isSigned ? 302202375Srdivacky ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT); 303204792Srdivacky return Builder->CreateICmp(pred, V, Hi); 304202375Srdivacky } 305202375Srdivacky 306202375Srdivacky // Emit V-Lo >u Hi-1-Lo 307202375Srdivacky // Note that Hi has already had one subtracted from it, above. 308202375Srdivacky ConstantInt *NegLo = cast<ConstantInt>(ConstantExpr::getNeg(Lo)); 309202375Srdivacky Value *Add = Builder->CreateAdd(V, NegLo, V->getName()+".off"); 310202375Srdivacky Constant *LowerBound = ConstantExpr::getAdd(NegLo, Hi); 311204792Srdivacky return Builder->CreateICmpUGT(Add, LowerBound); 312202375Srdivacky} 313202375Srdivacky 314202375Srdivacky// isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with 315202375Srdivacky// any number of 0s on either side. The 1s are allowed to wrap from LSB to 316202375Srdivacky// MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is 317202375Srdivacky// not, since all 1s are not contiguous. 318202375Srdivackystatic bool isRunOfOnes(ConstantInt *Val, uint32_t &MB, uint32_t &ME) { 319202375Srdivacky const APInt& V = Val->getValue(); 320202375Srdivacky uint32_t BitWidth = Val->getType()->getBitWidth(); 321202375Srdivacky if (!APIntOps::isShiftedMask(BitWidth, V)) return false; 322202375Srdivacky 323202375Srdivacky // look for the first zero bit after the run of ones 324202375Srdivacky MB = BitWidth - ((V - 1) ^ V).countLeadingZeros(); 325202375Srdivacky // look for the first non-zero bit 326252723Sdim ME = V.getActiveBits(); 327202375Srdivacky return true; 328202375Srdivacky} 329202375Srdivacky 330202375Srdivacky/// FoldLogicalPlusAnd - This is part of an expression (LHS +/- RHS) & Mask, 331202375Srdivacky/// where isSub determines whether the operator is a sub. If we can fold one of 332202375Srdivacky/// the following xforms: 333252723Sdim/// 334202375Srdivacky/// ((A & N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == Mask 335202375Srdivacky/// ((A | N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0 336202375Srdivacky/// ((A ^ N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0 337202375Srdivacky/// 338202375Srdivacky/// return (A +/- B). 339202375Srdivacky/// 340202375SrdivackyValue *InstCombiner::FoldLogicalPlusAnd(Value *LHS, Value *RHS, 341202375Srdivacky ConstantInt *Mask, bool isSub, 342202375Srdivacky Instruction &I) { 343202375Srdivacky Instruction *LHSI = dyn_cast<Instruction>(LHS); 344202375Srdivacky if (!LHSI || LHSI->getNumOperands() != 2 || 345202375Srdivacky !isa<ConstantInt>(LHSI->getOperand(1))) return 0; 346202375Srdivacky 347202375Srdivacky ConstantInt *N = cast<ConstantInt>(LHSI->getOperand(1)); 348202375Srdivacky 349202375Srdivacky switch (LHSI->getOpcode()) { 350202375Srdivacky default: return 0; 351202375Srdivacky case Instruction::And: 352202375Srdivacky if (ConstantExpr::getAnd(N, Mask) == Mask) { 353202375Srdivacky // If the AndRHS is a power of two minus one (0+1+), this is simple. 354252723Sdim if ((Mask->getValue().countLeadingZeros() + 355252723Sdim Mask->getValue().countPopulation()) == 356202375Srdivacky Mask->getValue().getBitWidth()) 357202375Srdivacky break; 358202375Srdivacky 359202375Srdivacky // Otherwise, if Mask is 0+1+0+, and if B is known to have the low 0+ 360202375Srdivacky // part, we don't need any explicit masks to take them out of A. If that 361202375Srdivacky // is all N is, ignore it. 362202375Srdivacky uint32_t MB = 0, ME = 0; 363202375Srdivacky if (isRunOfOnes(Mask, MB, ME)) { // begin/end bit of run, inclusive 364202375Srdivacky uint32_t BitWidth = cast<IntegerType>(RHS->getType())->getBitWidth(); 365202375Srdivacky APInt Mask(APInt::getLowBitsSet(BitWidth, MB-1)); 366202375Srdivacky if (MaskedValueIsZero(RHS, Mask)) 367202375Srdivacky break; 368202375Srdivacky } 369202375Srdivacky } 370202375Srdivacky return 0; 371202375Srdivacky case Instruction::Or: 372202375Srdivacky case Instruction::Xor: 373202375Srdivacky // If the AndRHS is a power of two minus one (0+1+), and N&Mask == 0 374252723Sdim if ((Mask->getValue().countLeadingZeros() + 375202375Srdivacky Mask->getValue().countPopulation()) == Mask->getValue().getBitWidth() 376202375Srdivacky && ConstantExpr::getAnd(N, Mask)->isNullValue()) 377202375Srdivacky break; 378202375Srdivacky return 0; 379202375Srdivacky } 380252723Sdim 381202375Srdivacky if (isSub) 382202375Srdivacky return Builder->CreateSub(LHSI->getOperand(0), RHS, "fold"); 383202375Srdivacky return Builder->CreateAdd(LHSI->getOperand(0), RHS, "fold"); 384202375Srdivacky} 385202375Srdivacky 386218893Sdim/// enum for classifying (icmp eq (A & B), C) and (icmp ne (A & B), C) 387252723Sdim/// One of A and B is considered the mask, the other the value. This is 388252723Sdim/// described as the "AMask" or "BMask" part of the enum. If the enum 389218893Sdim/// contains only "Mask", then both A and B can be considered masks. 390218893Sdim/// If A is the mask, then it was proven, that (A & C) == C. This 391218893Sdim/// is trivial if C == A, or C == 0. If both A and C are constants, this 392218893Sdim/// proof is also easy. 393218893Sdim/// For the following explanations we assume that A is the mask. 394252723Sdim/// The part "AllOnes" declares, that the comparison is true only 395218893Sdim/// if (A & B) == A, or all bits of A are set in B. 396218893Sdim/// Example: (icmp eq (A & 3), 3) -> FoldMskICmp_AMask_AllOnes 397252723Sdim/// The part "AllZeroes" declares, that the comparison is true only 398218893Sdim/// if (A & B) == 0, or all bits of A are cleared in B. 399218893Sdim/// Example: (icmp eq (A & 3), 0) -> FoldMskICmp_Mask_AllZeroes 400252723Sdim/// The part "Mixed" declares, that (A & B) == C and C might or might not 401218893Sdim/// contain any number of one bits and zero bits. 402218893Sdim/// Example: (icmp eq (A & 3), 1) -> FoldMskICmp_AMask_Mixed 403218893Sdim/// The Part "Not" means, that in above descriptions "==" should be replaced 404218893Sdim/// by "!=". 405218893Sdim/// Example: (icmp ne (A & 3), 3) -> FoldMskICmp_AMask_NotAllOnes 406218893Sdim/// If the mask A contains a single bit, then the following is equivalent: 407218893Sdim/// (icmp eq (A & B), A) equals (icmp ne (A & B), 0) 408218893Sdim/// (icmp ne (A & B), A) equals (icmp eq (A & B), 0) 409218893Sdimenum MaskedICmpType { 410218893Sdim FoldMskICmp_AMask_AllOnes = 1, 411218893Sdim FoldMskICmp_AMask_NotAllOnes = 2, 412218893Sdim FoldMskICmp_BMask_AllOnes = 4, 413218893Sdim FoldMskICmp_BMask_NotAllOnes = 8, 414218893Sdim FoldMskICmp_Mask_AllZeroes = 16, 415218893Sdim FoldMskICmp_Mask_NotAllZeroes = 32, 416218893Sdim FoldMskICmp_AMask_Mixed = 64, 417218893Sdim FoldMskICmp_AMask_NotMixed = 128, 418218893Sdim FoldMskICmp_BMask_Mixed = 256, 419218893Sdim FoldMskICmp_BMask_NotMixed = 512 420218893Sdim}; 421218893Sdim 422218893Sdim/// return the set of pattern classes (from MaskedICmpType) 423218893Sdim/// that (icmp SCC (A & B), C) satisfies 424252723Sdimstatic unsigned getTypeOfMaskedICmp(Value* A, Value* B, Value* C, 425218893Sdim ICmpInst::Predicate SCC) 426218893Sdim{ 427218893Sdim ConstantInt *ACst = dyn_cast<ConstantInt>(A); 428218893Sdim ConstantInt *BCst = dyn_cast<ConstantInt>(B); 429218893Sdim ConstantInt *CCst = dyn_cast<ConstantInt>(C); 430218893Sdim bool icmp_eq = (SCC == ICmpInst::ICMP_EQ); 431252723Sdim bool icmp_abit = (ACst != 0 && !ACst->isZero() && 432218893Sdim ACst->getValue().isPowerOf2()); 433252723Sdim bool icmp_bbit = (BCst != 0 && !BCst->isZero() && 434218893Sdim BCst->getValue().isPowerOf2()); 435218893Sdim unsigned result = 0; 436218893Sdim if (CCst != 0 && CCst->isZero()) { 437218893Sdim // if C is zero, then both A and B qualify as mask 438218893Sdim result |= (icmp_eq ? (FoldMskICmp_Mask_AllZeroes | 439218893Sdim FoldMskICmp_Mask_AllZeroes | 440218893Sdim FoldMskICmp_AMask_Mixed | 441218893Sdim FoldMskICmp_BMask_Mixed) 442218893Sdim : (FoldMskICmp_Mask_NotAllZeroes | 443218893Sdim FoldMskICmp_Mask_NotAllZeroes | 444218893Sdim FoldMskICmp_AMask_NotMixed | 445218893Sdim FoldMskICmp_BMask_NotMixed)); 446218893Sdim if (icmp_abit) 447218893Sdim result |= (icmp_eq ? (FoldMskICmp_AMask_NotAllOnes | 448252723Sdim FoldMskICmp_AMask_NotMixed) 449218893Sdim : (FoldMskICmp_AMask_AllOnes | 450218893Sdim FoldMskICmp_AMask_Mixed)); 451218893Sdim if (icmp_bbit) 452218893Sdim result |= (icmp_eq ? (FoldMskICmp_BMask_NotAllOnes | 453252723Sdim FoldMskICmp_BMask_NotMixed) 454218893Sdim : (FoldMskICmp_BMask_AllOnes | 455218893Sdim FoldMskICmp_BMask_Mixed)); 456218893Sdim return result; 457218893Sdim } 458218893Sdim if (A == C) { 459218893Sdim result |= (icmp_eq ? (FoldMskICmp_AMask_AllOnes | 460218893Sdim FoldMskICmp_AMask_Mixed) 461218893Sdim : (FoldMskICmp_AMask_NotAllOnes | 462218893Sdim FoldMskICmp_AMask_NotMixed)); 463218893Sdim if (icmp_abit) 464218893Sdim result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes | 465218893Sdim FoldMskICmp_AMask_NotMixed) 466218893Sdim : (FoldMskICmp_Mask_AllZeroes | 467218893Sdim FoldMskICmp_AMask_Mixed)); 468252723Sdim } else if (ACst != 0 && CCst != 0 && 469252723Sdim ConstantExpr::getAnd(ACst, CCst) == CCst) { 470218893Sdim result |= (icmp_eq ? FoldMskICmp_AMask_Mixed 471218893Sdim : FoldMskICmp_AMask_NotMixed); 472218893Sdim } 473252723Sdim if (B == C) { 474218893Sdim result |= (icmp_eq ? (FoldMskICmp_BMask_AllOnes | 475218893Sdim FoldMskICmp_BMask_Mixed) 476218893Sdim : (FoldMskICmp_BMask_NotAllOnes | 477218893Sdim FoldMskICmp_BMask_NotMixed)); 478218893Sdim if (icmp_bbit) 479218893Sdim result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes | 480252723Sdim FoldMskICmp_BMask_NotMixed) 481218893Sdim : (FoldMskICmp_Mask_AllZeroes | 482218893Sdim FoldMskICmp_BMask_Mixed)); 483252723Sdim } else if (BCst != 0 && CCst != 0 && 484252723Sdim ConstantExpr::getAnd(BCst, CCst) == CCst) { 485218893Sdim result |= (icmp_eq ? FoldMskICmp_BMask_Mixed 486218893Sdim : FoldMskICmp_BMask_NotMixed); 487218893Sdim } 488218893Sdim return result; 489218893Sdim} 490218893Sdim 491263509Sdim/// Convert an analysis of a masked ICmp into its equivalent if all boolean 492263509Sdim/// operations had the opposite sense. Since each "NotXXX" flag (recording !=) 493263509Sdim/// is adjacent to the corresponding normal flag (recording ==), this just 494263509Sdim/// involves swapping those bits over. 495263509Sdimstatic unsigned conjugateICmpMask(unsigned Mask) { 496263509Sdim unsigned NewMask; 497263509Sdim NewMask = (Mask & (FoldMskICmp_AMask_AllOnes | FoldMskICmp_BMask_AllOnes | 498263509Sdim FoldMskICmp_Mask_AllZeroes | FoldMskICmp_AMask_Mixed | 499263509Sdim FoldMskICmp_BMask_Mixed)) 500263509Sdim << 1; 501263509Sdim 502263509Sdim NewMask |= 503263509Sdim (Mask & (FoldMskICmp_AMask_NotAllOnes | FoldMskICmp_BMask_NotAllOnes | 504263509Sdim FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_AMask_NotMixed | 505263509Sdim FoldMskICmp_BMask_NotMixed)) 506263509Sdim >> 1; 507263509Sdim 508263509Sdim return NewMask; 509263509Sdim} 510263509Sdim 511235633Sdim/// decomposeBitTestICmp - Decompose an icmp into the form ((X & Y) pred Z) 512235633Sdim/// if possible. The returned predicate is either == or !=. Returns false if 513235633Sdim/// decomposition fails. 514235633Sdimstatic bool decomposeBitTestICmp(const ICmpInst *I, ICmpInst::Predicate &Pred, 515235633Sdim Value *&X, Value *&Y, Value *&Z) { 516235633Sdim // X < 0 is equivalent to (X & SignBit) != 0. 517235633Sdim if (I->getPredicate() == ICmpInst::ICMP_SLT) 518235633Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(I->getOperand(1))) 519235633Sdim if (C->isZero()) { 520235633Sdim X = I->getOperand(0); 521235633Sdim Y = ConstantInt::get(I->getContext(), 522235633Sdim APInt::getSignBit(C->getBitWidth())); 523235633Sdim Pred = ICmpInst::ICMP_NE; 524235633Sdim Z = C; 525235633Sdim return true; 526235633Sdim } 527235633Sdim 528235633Sdim // X > -1 is equivalent to (X & SignBit) == 0. 529235633Sdim if (I->getPredicate() == ICmpInst::ICMP_SGT) 530235633Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(I->getOperand(1))) 531235633Sdim if (C->isAllOnesValue()) { 532235633Sdim X = I->getOperand(0); 533235633Sdim Y = ConstantInt::get(I->getContext(), 534235633Sdim APInt::getSignBit(C->getBitWidth())); 535235633Sdim Pred = ICmpInst::ICMP_EQ; 536235633Sdim Z = ConstantInt::getNullValue(C->getType()); 537235633Sdim return true; 538235633Sdim } 539235633Sdim 540235633Sdim return false; 541235633Sdim} 542235633Sdim 543218893Sdim/// foldLogOpOfMaskedICmpsHelper: 544218893Sdim/// handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) 545218893Sdim/// return the set of pattern classes (from MaskedICmpType) 546218893Sdim/// that both LHS and RHS satisfy 547252723Sdimstatic unsigned foldLogOpOfMaskedICmpsHelper(Value*& A, 548218893Sdim Value*& B, Value*& C, 549218893Sdim Value*& D, Value*& E, 550235633Sdim ICmpInst *LHS, ICmpInst *RHS, 551235633Sdim ICmpInst::Predicate &LHSCC, 552235633Sdim ICmpInst::Predicate &RHSCC) { 553218893Sdim if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType()) return 0; 554218893Sdim // vectors are not (yet?) supported 555218893Sdim if (LHS->getOperand(0)->getType()->isVectorTy()) return 0; 556218893Sdim 557218893Sdim // Here comes the tricky part: 558252723Sdim // LHS might be of the form L11 & L12 == X, X == L21 & L22, 559218893Sdim // and L11 & L12 == L21 & L22. The same goes for RHS. 560218893Sdim // Now we must find those components L** and R**, that are equal, so 561252723Sdim // that we can extract the parameters A, B, C, D, and E for the canonical 562218893Sdim // above. 563218893Sdim Value *L1 = LHS->getOperand(0); 564218893Sdim Value *L2 = LHS->getOperand(1); 565218893Sdim Value *L11,*L12,*L21,*L22; 566235633Sdim // Check whether the icmp can be decomposed into a bit test. 567235633Sdim if (decomposeBitTestICmp(LHS, LHSCC, L11, L12, L2)) { 568235633Sdim L21 = L22 = L1 = 0; 569235633Sdim } else { 570235633Sdim // Look for ANDs in the LHS icmp. 571263509Sdim if (!L1->getType()->isIntegerTy()) { 572263509Sdim // You can icmp pointers, for example. They really aren't masks. 573263509Sdim L11 = L12 = 0; 574263509Sdim } else if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) { 575263509Sdim // Any icmp can be viewed as being trivially masked; if it allows us to 576263509Sdim // remove one, it's worth it. 577263509Sdim L11 = L1; 578263509Sdim L12 = Constant::getAllOnesValue(L1->getType()); 579263509Sdim } 580263509Sdim 581263509Sdim if (!L2->getType()->isIntegerTy()) { 582263509Sdim // You can icmp pointers, for example. They really aren't masks. 583218893Sdim L21 = L22 = 0; 584263509Sdim } else if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) { 585263509Sdim L21 = L2; 586263509Sdim L22 = Constant::getAllOnesValue(L2->getType()); 587235633Sdim } 588218893Sdim } 589218893Sdim 590235633Sdim // Bail if LHS was a icmp that can't be decomposed into an equality. 591235633Sdim if (!ICmpInst::isEquality(LHSCC)) 592235633Sdim return 0; 593235633Sdim 594218893Sdim Value *R1 = RHS->getOperand(0); 595218893Sdim Value *R2 = RHS->getOperand(1); 596218893Sdim Value *R11,*R12; 597218893Sdim bool ok = false; 598235633Sdim if (decomposeBitTestICmp(RHS, RHSCC, R11, R12, R2)) { 599235633Sdim if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 600235633Sdim A = R11; D = R12; 601235633Sdim } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 602235633Sdim A = R12; D = R11; 603235633Sdim } else { 604235633Sdim return 0; 605235633Sdim } 606235633Sdim E = R2; R1 = 0; ok = true; 607263509Sdim } else if (R1->getType()->isIntegerTy()) { 608263509Sdim if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) { 609263509Sdim // As before, model no mask as a trivial mask if it'll let us do an 610263509Sdim // optimisation. 611263509Sdim R11 = R1; 612263509Sdim R12 = Constant::getAllOnesValue(R1->getType()); 613263509Sdim } 614263509Sdim 615235633Sdim if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 616218893Sdim A = R11; D = R12; E = R2; ok = true; 617235633Sdim } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 618218893Sdim A = R12; D = R11; E = R2; ok = true; 619218893Sdim } 620218893Sdim } 621235633Sdim 622235633Sdim // Bail if RHS was a icmp that can't be decomposed into an equality. 623235633Sdim if (!ICmpInst::isEquality(RHSCC)) 624235633Sdim return 0; 625235633Sdim 626235633Sdim // Look for ANDs in on the right side of the RHS icmp. 627263509Sdim if (!ok && R2->getType()->isIntegerTy()) { 628263509Sdim if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) { 629263509Sdim R11 = R2; 630263509Sdim R12 = Constant::getAllOnesValue(R2->getType()); 631263509Sdim } 632263509Sdim 633235633Sdim if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { 634235633Sdim A = R11; D = R12; E = R1; ok = true; 635235633Sdim } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) { 636218893Sdim A = R12; D = R11; E = R1; ok = true; 637235633Sdim } else { 638235633Sdim return 0; 639218893Sdim } 640218893Sdim } 641218893Sdim if (!ok) 642218893Sdim return 0; 643218893Sdim 644218893Sdim if (L11 == A) { 645218893Sdim B = L12; C = L2; 646252723Sdim } else if (L12 == A) { 647218893Sdim B = L11; C = L2; 648252723Sdim } else if (L21 == A) { 649218893Sdim B = L22; C = L1; 650252723Sdim } else if (L22 == A) { 651218893Sdim B = L21; C = L1; 652218893Sdim } 653218893Sdim 654218893Sdim unsigned left_type = getTypeOfMaskedICmp(A, B, C, LHSCC); 655218893Sdim unsigned right_type = getTypeOfMaskedICmp(A, D, E, RHSCC); 656218893Sdim return left_type & right_type; 657218893Sdim} 658218893Sdim/// foldLogOpOfMaskedICmps: 659218893Sdim/// try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) 660218893Sdim/// into a single (icmp(A & X) ==/!= Y) 661263509Sdimstatic Value* foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, 662218893Sdim llvm::InstCombiner::BuilderTy* Builder) { 663218893Sdim Value *A = 0, *B = 0, *C = 0, *D = 0, *E = 0; 664235633Sdim ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 665235633Sdim unsigned mask = foldLogOpOfMaskedICmpsHelper(A, B, C, D, E, LHS, RHS, 666235633Sdim LHSCC, RHSCC); 667218893Sdim if (mask == 0) return 0; 668235633Sdim assert(ICmpInst::isEquality(LHSCC) && ICmpInst::isEquality(RHSCC) && 669235633Sdim "foldLogOpOfMaskedICmpsHelper must return an equality predicate."); 670218893Sdim 671263509Sdim // In full generality: 672263509Sdim // (icmp (A & B) Op C) | (icmp (A & D) Op E) 673263509Sdim // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ] 674263509Sdim // 675263509Sdim // If the latter can be converted into (icmp (A & X) Op Y) then the former is 676263509Sdim // equivalent to (icmp (A & X) !Op Y). 677263509Sdim // 678263509Sdim // Therefore, we can pretend for the rest of this function that we're dealing 679263509Sdim // with the conjunction, provided we flip the sense of any comparisons (both 680263509Sdim // input and output). 681218893Sdim 682263509Sdim // In most cases we're going to produce an EQ for the "&&" case. 683263509Sdim ICmpInst::Predicate NEWCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE; 684263509Sdim if (!IsAnd) { 685263509Sdim // Convert the masking analysis into its equivalent with negated 686263509Sdim // comparisons. 687263509Sdim mask = conjugateICmpMask(mask); 688263509Sdim } 689263509Sdim 690218893Sdim if (mask & FoldMskICmp_Mask_AllZeroes) { 691252723Sdim // (icmp eq (A & B), 0) & (icmp eq (A & D), 0) 692218893Sdim // -> (icmp eq (A & (B|D)), 0) 693218893Sdim Value* newOr = Builder->CreateOr(B, D); 694218893Sdim Value* newAnd = Builder->CreateAnd(A, newOr); 695218893Sdim // we can't use C as zero, because we might actually handle 696252723Sdim // (icmp ne (A & B), B) & (icmp ne (A & D), D) 697218893Sdim // with B and D, having a single bit set 698218893Sdim Value* zero = Constant::getNullValue(A->getType()); 699218893Sdim return Builder->CreateICmp(NEWCC, newAnd, zero); 700218893Sdim } 701252723Sdim if (mask & FoldMskICmp_BMask_AllOnes) { 702252723Sdim // (icmp eq (A & B), B) & (icmp eq (A & D), D) 703218893Sdim // -> (icmp eq (A & (B|D)), (B|D)) 704218893Sdim Value* newOr = Builder->CreateOr(B, D); 705218893Sdim Value* newAnd = Builder->CreateAnd(A, newOr); 706218893Sdim return Builder->CreateICmp(NEWCC, newAnd, newOr); 707252723Sdim } 708252723Sdim if (mask & FoldMskICmp_AMask_AllOnes) { 709252723Sdim // (icmp eq (A & B), A) & (icmp eq (A & D), A) 710218893Sdim // -> (icmp eq (A & (B&D)), A) 711218893Sdim Value* newAnd1 = Builder->CreateAnd(B, D); 712218893Sdim Value* newAnd = Builder->CreateAnd(A, newAnd1); 713218893Sdim return Builder->CreateICmp(NEWCC, newAnd, A); 714218893Sdim } 715263509Sdim 716263509Sdim // Remaining cases assume at least that B and D are constant, and depend on 717263509Sdim // their actual values. This isn't strictly, necessary, just a "handle the 718263509Sdim // easy cases for now" decision. 719263509Sdim ConstantInt *BCst = dyn_cast<ConstantInt>(B); 720263509Sdim if (BCst == 0) return 0; 721263509Sdim ConstantInt *DCst = dyn_cast<ConstantInt>(D); 722263509Sdim if (DCst == 0) return 0; 723263509Sdim 724263509Sdim if (mask & (FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_BMask_NotAllOnes)) { 725263509Sdim // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and 726263509Sdim // (icmp ne (A & B), B) & (icmp ne (A & D), D) 727263509Sdim // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0) 728263509Sdim // Only valid if one of the masks is a superset of the other (check "B&D" is 729263509Sdim // the same as either B or D). 730263509Sdim APInt NewMask = BCst->getValue() & DCst->getValue(); 731263509Sdim 732263509Sdim if (NewMask == BCst->getValue()) 733263509Sdim return LHS; 734263509Sdim else if (NewMask == DCst->getValue()) 735263509Sdim return RHS; 736263509Sdim } 737263509Sdim if (mask & FoldMskICmp_AMask_NotAllOnes) { 738263509Sdim // (icmp ne (A & B), B) & (icmp ne (A & D), D) 739263509Sdim // -> (icmp ne (A & B), A) or (icmp ne (A & D), A) 740263509Sdim // Only valid if one of the masks is a superset of the other (check "B|D" is 741263509Sdim // the same as either B or D). 742263509Sdim APInt NewMask = BCst->getValue() | DCst->getValue(); 743263509Sdim 744263509Sdim if (NewMask == BCst->getValue()) 745263509Sdim return LHS; 746263509Sdim else if (NewMask == DCst->getValue()) 747263509Sdim return RHS; 748263509Sdim } 749252723Sdim if (mask & FoldMskICmp_BMask_Mixed) { 750252723Sdim // (icmp eq (A & B), C) & (icmp eq (A & D), E) 751218893Sdim // We already know that B & C == C && D & E == E. 752218893Sdim // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of 753218893Sdim // C and E, which are shared by both the mask B and the mask D, don't 754218893Sdim // contradict, then we can transform to 755218893Sdim // -> (icmp eq (A & (B|D)), (C|E)) 756218893Sdim // Currently, we only handle the case of B, C, D, and E being constant. 757218893Sdim // we can't simply use C and E, because we might actually handle 758252723Sdim // (icmp ne (A & B), B) & (icmp eq (A & D), D) 759218893Sdim // with B and D, having a single bit set 760218893Sdim ConstantInt *CCst = dyn_cast<ConstantInt>(C); 761218893Sdim if (CCst == 0) return 0; 762235633Sdim if (LHSCC != NEWCC) 763218893Sdim CCst = dyn_cast<ConstantInt>( ConstantExpr::getXor(BCst, CCst) ); 764218893Sdim ConstantInt *ECst = dyn_cast<ConstantInt>(E); 765218893Sdim if (ECst == 0) return 0; 766235633Sdim if (RHSCC != NEWCC) 767218893Sdim ECst = dyn_cast<ConstantInt>( ConstantExpr::getXor(DCst, ECst) ); 768218893Sdim ConstantInt* MCst = dyn_cast<ConstantInt>( 769218893Sdim ConstantExpr::getAnd(ConstantExpr::getAnd(BCst, DCst), 770218893Sdim ConstantExpr::getXor(CCst, ECst)) ); 771218893Sdim // if there is a conflict we should actually return a false for the 772218893Sdim // whole construct 773218893Sdim if (!MCst->isZero()) 774218893Sdim return 0; 775218893Sdim Value *newOr1 = Builder->CreateOr(B, D); 776218893Sdim Value *newOr2 = ConstantExpr::getOr(CCst, ECst); 777218893Sdim Value *newAnd = Builder->CreateAnd(A, newOr1); 778218893Sdim return Builder->CreateICmp(NEWCC, newAnd, newOr2); 779218893Sdim } 780218893Sdim return 0; 781218893Sdim} 782218893Sdim 783202375Srdivacky/// FoldAndOfICmps - Fold (icmp)&(icmp) if possible. 784204792SrdivackyValue *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) { 785202375Srdivacky ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 786202375Srdivacky 787202375Srdivacky // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B) 788202375Srdivacky if (PredicatesFoldable(LHSCC, RHSCC)) { 789202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(1) && 790202375Srdivacky LHS->getOperand(1) == RHS->getOperand(0)) 791202375Srdivacky LHS->swapOperands(); 792202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(0) && 793202375Srdivacky LHS->getOperand(1) == RHS->getOperand(1)) { 794202375Srdivacky Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 795202375Srdivacky unsigned Code = getICmpCode(LHS) & getICmpCode(RHS); 796202375Srdivacky bool isSigned = LHS->isSigned() || RHS->isSigned(); 797235633Sdim return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); 798202375Srdivacky } 799202375Srdivacky } 800218893Sdim 801218893Sdim // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E) 802263509Sdim if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder)) 803218893Sdim return V; 804252723Sdim 805202375Srdivacky // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2). 806202375Srdivacky Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0); 807202375Srdivacky ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1)); 808202375Srdivacky ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1)); 809202375Srdivacky if (LHSCst == 0 || RHSCst == 0) return 0; 810252723Sdim 811202375Srdivacky if (LHSCst == RHSCst && LHSCC == RHSCC) { 812202375Srdivacky // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C) 813202375Srdivacky // where C is a power of 2 814202375Srdivacky if (LHSCC == ICmpInst::ICMP_ULT && 815202375Srdivacky LHSCst->getValue().isPowerOf2()) { 816202375Srdivacky Value *NewOr = Builder->CreateOr(Val, Val2); 817204792Srdivacky return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 818202375Srdivacky } 819252723Sdim 820202375Srdivacky // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0) 821202375Srdivacky if (LHSCC == ICmpInst::ICMP_EQ && LHSCst->isZero()) { 822202375Srdivacky Value *NewOr = Builder->CreateOr(Val, Val2); 823204792Srdivacky return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 824202375Srdivacky } 825202375Srdivacky } 826221345Sdim 827221345Sdim // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2 828221345Sdim // where CMAX is the all ones value for the truncated type, 829221345Sdim // iff the lower bits of C2 and CA are zero. 830235633Sdim if (LHSCC == ICmpInst::ICMP_EQ && LHSCC == RHSCC && 831221345Sdim LHS->hasOneUse() && RHS->hasOneUse()) { 832221345Sdim Value *V; 833221345Sdim ConstantInt *AndCst, *SmallCst = 0, *BigCst = 0; 834221345Sdim 835221345Sdim // (trunc x) == C1 & (and x, CA) == C2 836252723Sdim // (and x, CA) == C2 & (trunc x) == C1 837221345Sdim if (match(Val2, m_Trunc(m_Value(V))) && 838221345Sdim match(Val, m_And(m_Specific(V), m_ConstantInt(AndCst)))) { 839221345Sdim SmallCst = RHSCst; 840221345Sdim BigCst = LHSCst; 841252723Sdim } else if (match(Val, m_Trunc(m_Value(V))) && 842252723Sdim match(Val2, m_And(m_Specific(V), m_ConstantInt(AndCst)))) { 843221345Sdim SmallCst = LHSCst; 844221345Sdim BigCst = RHSCst; 845221345Sdim } 846221345Sdim 847221345Sdim if (SmallCst && BigCst) { 848221345Sdim unsigned BigBitSize = BigCst->getType()->getBitWidth(); 849221345Sdim unsigned SmallBitSize = SmallCst->getType()->getBitWidth(); 850221345Sdim 851221345Sdim // Check that the low bits are zero. 852221345Sdim APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize); 853221345Sdim if ((Low & AndCst->getValue()) == 0 && (Low & BigCst->getValue()) == 0) { 854221345Sdim Value *NewAnd = Builder->CreateAnd(V, Low | AndCst->getValue()); 855221345Sdim APInt N = SmallCst->getValue().zext(BigBitSize) | BigCst->getValue(); 856221345Sdim Value *NewVal = ConstantInt::get(AndCst->getType()->getContext(), N); 857221345Sdim return Builder->CreateICmp(LHSCC, NewAnd, NewVal); 858221345Sdim } 859221345Sdim } 860221345Sdim } 861235633Sdim 862202375Srdivacky // From here on, we only handle: 863202375Srdivacky // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler. 864202375Srdivacky if (Val != Val2) return 0; 865252723Sdim 866202375Srdivacky // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere. 867202375Srdivacky if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE || 868202375Srdivacky RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE || 869202375Srdivacky LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE || 870202375Srdivacky RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE) 871202375Srdivacky return 0; 872221345Sdim 873221345Sdim // Make a constant range that's the intersection of the two icmp ranges. 874221345Sdim // If the intersection is empty, we know that the result is false. 875252723Sdim ConstantRange LHSRange = 876221345Sdim ConstantRange::makeICmpRegion(LHSCC, LHSCst->getValue()); 877252723Sdim ConstantRange RHSRange = 878221345Sdim ConstantRange::makeICmpRegion(RHSCC, RHSCst->getValue()); 879221345Sdim 880221345Sdim if (LHSRange.intersectWith(RHSRange).isEmptySet()) 881221345Sdim return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 882221345Sdim 883202375Srdivacky // We can't fold (ugt x, C) & (sgt x, C2). 884202375Srdivacky if (!PredicatesFoldable(LHSCC, RHSCC)) 885202375Srdivacky return 0; 886252723Sdim 887202375Srdivacky // Ensure that the larger constant is on the RHS. 888202375Srdivacky bool ShouldSwap; 889202375Srdivacky if (CmpInst::isSigned(LHSCC) || 890252723Sdim (ICmpInst::isEquality(LHSCC) && 891202375Srdivacky CmpInst::isSigned(RHSCC))) 892202375Srdivacky ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue()); 893202375Srdivacky else 894202375Srdivacky ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue()); 895252723Sdim 896202375Srdivacky if (ShouldSwap) { 897202375Srdivacky std::swap(LHS, RHS); 898202375Srdivacky std::swap(LHSCst, RHSCst); 899202375Srdivacky std::swap(LHSCC, RHSCC); 900202375Srdivacky } 901202375Srdivacky 902203954Srdivacky // At this point, we know we have two icmp instructions 903202375Srdivacky // comparing a value against two constants and and'ing the result 904202375Srdivacky // together. Because of the above check, we know that we only have 905252723Sdim // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know 906252723Sdim // (from the icmp folding check above), that the two constants 907202375Srdivacky // are not equal and that the larger constant is on the RHS 908202375Srdivacky assert(LHSCst != RHSCst && "Compares not folded above?"); 909202375Srdivacky 910202375Srdivacky switch (LHSCC) { 911202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 912202375Srdivacky case ICmpInst::ICMP_EQ: 913202375Srdivacky switch (RHSCC) { 914202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 915202375Srdivacky case ICmpInst::ICMP_NE: // (X == 13 & X != 15) -> X == 13 916202375Srdivacky case ICmpInst::ICMP_ULT: // (X == 13 & X < 15) -> X == 13 917202375Srdivacky case ICmpInst::ICMP_SLT: // (X == 13 & X < 15) -> X == 13 918204792Srdivacky return LHS; 919202375Srdivacky } 920202375Srdivacky case ICmpInst::ICMP_NE: 921202375Srdivacky switch (RHSCC) { 922202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 923202375Srdivacky case ICmpInst::ICMP_ULT: 924202375Srdivacky if (LHSCst == SubOne(RHSCst)) // (X != 13 & X u< 14) -> X < 13 925204792Srdivacky return Builder->CreateICmpULT(Val, LHSCst); 926202375Srdivacky break; // (X != 13 & X u< 15) -> no change 927202375Srdivacky case ICmpInst::ICMP_SLT: 928202375Srdivacky if (LHSCst == SubOne(RHSCst)) // (X != 13 & X s< 14) -> X < 13 929204792Srdivacky return Builder->CreateICmpSLT(Val, LHSCst); 930202375Srdivacky break; // (X != 13 & X s< 15) -> no change 931202375Srdivacky case ICmpInst::ICMP_EQ: // (X != 13 & X == 15) -> X == 15 932202375Srdivacky case ICmpInst::ICMP_UGT: // (X != 13 & X u> 15) -> X u> 15 933202375Srdivacky case ICmpInst::ICMP_SGT: // (X != 13 & X s> 15) -> X s> 15 934204792Srdivacky return RHS; 935202375Srdivacky case ICmpInst::ICMP_NE: 936263509Sdim // Special case to get the ordering right when the values wrap around 937263509Sdim // zero. 938263509Sdim if (LHSCst->getValue() == 0 && RHSCst->getValue().isAllOnesValue()) 939263509Sdim std::swap(LHSCst, RHSCst); 940202375Srdivacky if (LHSCst == SubOne(RHSCst)){// (X != 13 & X != 14) -> X-13 >u 1 941202375Srdivacky Constant *AddCST = ConstantExpr::getNeg(LHSCst); 942202375Srdivacky Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off"); 943263509Sdim return Builder->CreateICmpUGT(Add, ConstantInt::get(Add->getType(), 1), 944263509Sdim Val->getName()+".cmp"); 945202375Srdivacky } 946202375Srdivacky break; // (X != 13 & X != 15) -> no change 947202375Srdivacky } 948202375Srdivacky break; 949202375Srdivacky case ICmpInst::ICMP_ULT: 950202375Srdivacky switch (RHSCC) { 951202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 952202375Srdivacky case ICmpInst::ICMP_EQ: // (X u< 13 & X == 15) -> false 953202375Srdivacky case ICmpInst::ICMP_UGT: // (X u< 13 & X u> 15) -> false 954204792Srdivacky return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 955202375Srdivacky case ICmpInst::ICMP_SGT: // (X u< 13 & X s> 15) -> no change 956202375Srdivacky break; 957202375Srdivacky case ICmpInst::ICMP_NE: // (X u< 13 & X != 15) -> X u< 13 958202375Srdivacky case ICmpInst::ICMP_ULT: // (X u< 13 & X u< 15) -> X u< 13 959204792Srdivacky return LHS; 960202375Srdivacky case ICmpInst::ICMP_SLT: // (X u< 13 & X s< 15) -> no change 961202375Srdivacky break; 962202375Srdivacky } 963202375Srdivacky break; 964202375Srdivacky case ICmpInst::ICMP_SLT: 965202375Srdivacky switch (RHSCC) { 966202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 967202375Srdivacky case ICmpInst::ICMP_UGT: // (X s< 13 & X u> 15) -> no change 968202375Srdivacky break; 969202375Srdivacky case ICmpInst::ICMP_NE: // (X s< 13 & X != 15) -> X < 13 970202375Srdivacky case ICmpInst::ICMP_SLT: // (X s< 13 & X s< 15) -> X < 13 971204792Srdivacky return LHS; 972202375Srdivacky case ICmpInst::ICMP_ULT: // (X s< 13 & X u< 15) -> no change 973202375Srdivacky break; 974202375Srdivacky } 975202375Srdivacky break; 976202375Srdivacky case ICmpInst::ICMP_UGT: 977202375Srdivacky switch (RHSCC) { 978202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 979202375Srdivacky case ICmpInst::ICMP_EQ: // (X u> 13 & X == 15) -> X == 15 980202375Srdivacky case ICmpInst::ICMP_UGT: // (X u> 13 & X u> 15) -> X u> 15 981204792Srdivacky return RHS; 982202375Srdivacky case ICmpInst::ICMP_SGT: // (X u> 13 & X s> 15) -> no change 983202375Srdivacky break; 984202375Srdivacky case ICmpInst::ICMP_NE: 985202375Srdivacky if (RHSCst == AddOne(LHSCst)) // (X u> 13 & X != 14) -> X u> 14 986204792Srdivacky return Builder->CreateICmp(LHSCC, Val, RHSCst); 987202375Srdivacky break; // (X u> 13 & X != 15) -> no change 988202375Srdivacky case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1 989204792Srdivacky return InsertRangeTest(Val, AddOne(LHSCst), RHSCst, false, true); 990202375Srdivacky case ICmpInst::ICMP_SLT: // (X u> 13 & X s< 15) -> no change 991202375Srdivacky break; 992202375Srdivacky } 993202375Srdivacky break; 994202375Srdivacky case ICmpInst::ICMP_SGT: 995202375Srdivacky switch (RHSCC) { 996202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 997202375Srdivacky case ICmpInst::ICMP_EQ: // (X s> 13 & X == 15) -> X == 15 998202375Srdivacky case ICmpInst::ICMP_SGT: // (X s> 13 & X s> 15) -> X s> 15 999204792Srdivacky return RHS; 1000202375Srdivacky case ICmpInst::ICMP_UGT: // (X s> 13 & X u> 15) -> no change 1001202375Srdivacky break; 1002202375Srdivacky case ICmpInst::ICMP_NE: 1003202375Srdivacky if (RHSCst == AddOne(LHSCst)) // (X s> 13 & X != 14) -> X s> 14 1004204792Srdivacky return Builder->CreateICmp(LHSCC, Val, RHSCst); 1005202375Srdivacky break; // (X s> 13 & X != 15) -> no change 1006202375Srdivacky case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1 1007204792Srdivacky return InsertRangeTest(Val, AddOne(LHSCst), RHSCst, true, true); 1008202375Srdivacky case ICmpInst::ICMP_ULT: // (X s> 13 & X u< 15) -> no change 1009202375Srdivacky break; 1010202375Srdivacky } 1011202375Srdivacky break; 1012202375Srdivacky } 1013252723Sdim 1014202375Srdivacky return 0; 1015202375Srdivacky} 1016202375Srdivacky 1017204792Srdivacky/// FoldAndOfFCmps - Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of 1018204792Srdivacky/// instcombine, this returns a Value which should already be inserted into the 1019204792Srdivacky/// function. 1020204792SrdivackyValue *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) { 1021202375Srdivacky if (LHS->getPredicate() == FCmpInst::FCMP_ORD && 1022202375Srdivacky RHS->getPredicate() == FCmpInst::FCMP_ORD) { 1023252723Sdim if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType()) 1024252723Sdim return 0; 1025252723Sdim 1026202375Srdivacky // (fcmp ord x, c) & (fcmp ord y, c) -> (fcmp ord x, y) 1027202375Srdivacky if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1))) 1028202375Srdivacky if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) { 1029202375Srdivacky // If either of the constants are nans, then the whole thing returns 1030202375Srdivacky // false. 1031202375Srdivacky if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN()) 1032263509Sdim return Builder->getFalse(); 1033204792Srdivacky return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0)); 1034202375Srdivacky } 1035252723Sdim 1036202375Srdivacky // Handle vector zeros. This occurs because the canonical form of 1037202375Srdivacky // "fcmp ord x,x" is "fcmp ord x, 0". 1038202375Srdivacky if (isa<ConstantAggregateZero>(LHS->getOperand(1)) && 1039202375Srdivacky isa<ConstantAggregateZero>(RHS->getOperand(1))) 1040204792Srdivacky return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0)); 1041202375Srdivacky return 0; 1042202375Srdivacky } 1043252723Sdim 1044202375Srdivacky Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1); 1045202375Srdivacky Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1); 1046202375Srdivacky FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate(); 1047252723Sdim 1048252723Sdim 1049202375Srdivacky if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) { 1050202375Srdivacky // Swap RHS operands to match LHS. 1051202375Srdivacky Op1CC = FCmpInst::getSwappedPredicate(Op1CC); 1052202375Srdivacky std::swap(Op1LHS, Op1RHS); 1053202375Srdivacky } 1054252723Sdim 1055202375Srdivacky if (Op0LHS == Op1LHS && Op0RHS == Op1RHS) { 1056202375Srdivacky // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y). 1057202375Srdivacky if (Op0CC == Op1CC) 1058204792Srdivacky return Builder->CreateFCmp((FCmpInst::Predicate)Op0CC, Op0LHS, Op0RHS); 1059202375Srdivacky if (Op0CC == FCmpInst::FCMP_FALSE || Op1CC == FCmpInst::FCMP_FALSE) 1060204792Srdivacky return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1061202375Srdivacky if (Op0CC == FCmpInst::FCMP_TRUE) 1062204792Srdivacky return RHS; 1063202375Srdivacky if (Op1CC == FCmpInst::FCMP_TRUE) 1064204792Srdivacky return LHS; 1065252723Sdim 1066202375Srdivacky bool Op0Ordered; 1067202375Srdivacky bool Op1Ordered; 1068202375Srdivacky unsigned Op0Pred = getFCmpCode(Op0CC, Op0Ordered); 1069202375Srdivacky unsigned Op1Pred = getFCmpCode(Op1CC, Op1Ordered); 1070245431Sdim // uno && ord -> false 1071245431Sdim if (Op0Pred == 0 && Op1Pred == 0 && Op0Ordered != Op1Ordered) 1072245431Sdim return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1073202375Srdivacky if (Op1Pred == 0) { 1074202375Srdivacky std::swap(LHS, RHS); 1075202375Srdivacky std::swap(Op0Pred, Op1Pred); 1076202375Srdivacky std::swap(Op0Ordered, Op1Ordered); 1077202375Srdivacky } 1078202375Srdivacky if (Op0Pred == 0) { 1079245431Sdim // uno && ueq -> uno && (uno || eq) -> uno 1080202375Srdivacky // ord && olt -> ord && (ord && lt) -> olt 1081245431Sdim if (!Op0Ordered && (Op0Ordered == Op1Ordered)) 1082245431Sdim return LHS; 1083245431Sdim if (Op0Ordered && (Op0Ordered == Op1Ordered)) 1084204792Srdivacky return RHS; 1085252723Sdim 1086202375Srdivacky // uno && oeq -> uno && (ord && eq) -> false 1087202375Srdivacky if (!Op0Ordered) 1088204792Srdivacky return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 1089202375Srdivacky // ord && ueq -> ord && (uno || eq) -> oeq 1090204792Srdivacky return getFCmpValue(true, Op1Pred, Op0LHS, Op0RHS, Builder); 1091202375Srdivacky } 1092202375Srdivacky } 1093202375Srdivacky 1094202375Srdivacky return 0; 1095202375Srdivacky} 1096202375Srdivacky 1097202375Srdivacky 1098202375SrdivackyInstruction *InstCombiner::visitAnd(BinaryOperator &I) { 1099218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 1100202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1101202375Srdivacky 1102202375Srdivacky if (Value *V = SimplifyAndInst(Op0, Op1, TD)) 1103202375Srdivacky return ReplaceInstUsesWith(I, V); 1104202375Srdivacky 1105218893Sdim // (A|B)&(A|C) -> A|(B&C) etc 1106218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 1107218893Sdim return ReplaceInstUsesWith(I, V); 1108218893Sdim 1109252723Sdim // See if we can simplify any instructions used by the instruction whose sole 1110202375Srdivacky // purpose is to compute bits we don't care about. 1111202375Srdivacky if (SimplifyDemandedInstructionBits(I)) 1112252723Sdim return &I; 1113202375Srdivacky 1114202375Srdivacky if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) { 1115202375Srdivacky const APInt &AndRHSMask = AndRHS->getValue(); 1116202375Srdivacky 1117202375Srdivacky // Optimize a variety of ((val OP C1) & C2) combinations... 1118202375Srdivacky if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 1119202375Srdivacky Value *Op0LHS = Op0I->getOperand(0); 1120202375Srdivacky Value *Op0RHS = Op0I->getOperand(1); 1121202375Srdivacky switch (Op0I->getOpcode()) { 1122202375Srdivacky default: break; 1123202375Srdivacky case Instruction::Xor: 1124218893Sdim case Instruction::Or: { 1125202375Srdivacky // If the mask is only needed on one incoming arm, push it up. 1126202375Srdivacky if (!Op0I->hasOneUse()) break; 1127252723Sdim 1128218893Sdim APInt NotAndRHS(~AndRHSMask); 1129202375Srdivacky if (MaskedValueIsZero(Op0LHS, NotAndRHS)) { 1130202375Srdivacky // Not masking anything out for the LHS, move to RHS. 1131202375Srdivacky Value *NewRHS = Builder->CreateAnd(Op0RHS, AndRHS, 1132202375Srdivacky Op0RHS->getName()+".masked"); 1133202375Srdivacky return BinaryOperator::Create(Op0I->getOpcode(), Op0LHS, NewRHS); 1134202375Srdivacky } 1135202375Srdivacky if (!isa<Constant>(Op0RHS) && 1136202375Srdivacky MaskedValueIsZero(Op0RHS, NotAndRHS)) { 1137202375Srdivacky // Not masking anything out for the RHS, move to LHS. 1138202375Srdivacky Value *NewLHS = Builder->CreateAnd(Op0LHS, AndRHS, 1139202375Srdivacky Op0LHS->getName()+".masked"); 1140202375Srdivacky return BinaryOperator::Create(Op0I->getOpcode(), NewLHS, Op0RHS); 1141202375Srdivacky } 1142202375Srdivacky 1143202375Srdivacky break; 1144218893Sdim } 1145202375Srdivacky case Instruction::Add: 1146202375Srdivacky // ((A & N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == AndRHS. 1147202375Srdivacky // ((A | N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0 1148202375Srdivacky // ((A ^ N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0 1149202375Srdivacky if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, false, I)) 1150202375Srdivacky return BinaryOperator::CreateAnd(V, AndRHS); 1151202375Srdivacky if (Value *V = FoldLogicalPlusAnd(Op0RHS, Op0LHS, AndRHS, false, I)) 1152202375Srdivacky return BinaryOperator::CreateAnd(V, AndRHS); // Add commutes 1153202375Srdivacky break; 1154202375Srdivacky 1155202375Srdivacky case Instruction::Sub: 1156202375Srdivacky // ((A & N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == AndRHS. 1157202375Srdivacky // ((A | N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0 1158202375Srdivacky // ((A ^ N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0 1159202375Srdivacky if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I)) 1160202375Srdivacky return BinaryOperator::CreateAnd(V, AndRHS); 1161202375Srdivacky 1162202375Srdivacky // (A - N) & AndRHS -> -N & AndRHS iff A&AndRHS==0 and AndRHS 1163202375Srdivacky // has 1's for all bits that the subtraction with A might affect. 1164218893Sdim if (Op0I->hasOneUse() && !match(Op0LHS, m_Zero())) { 1165202375Srdivacky uint32_t BitWidth = AndRHSMask.getBitWidth(); 1166202375Srdivacky uint32_t Zeros = AndRHSMask.countLeadingZeros(); 1167202375Srdivacky APInt Mask = APInt::getLowBitsSet(BitWidth, BitWidth - Zeros); 1168202375Srdivacky 1169218893Sdim if (MaskedValueIsZero(Op0LHS, Mask)) { 1170202375Srdivacky Value *NewNeg = Builder->CreateNeg(Op0RHS); 1171202375Srdivacky return BinaryOperator::CreateAnd(NewNeg, AndRHS); 1172202375Srdivacky } 1173202375Srdivacky } 1174202375Srdivacky break; 1175202375Srdivacky 1176202375Srdivacky case Instruction::Shl: 1177202375Srdivacky case Instruction::LShr: 1178202375Srdivacky // (1 << x) & 1 --> zext(x == 0) 1179202375Srdivacky // (1 >> x) & 1 --> zext(x == 0) 1180202375Srdivacky if (AndRHSMask == 1 && Op0LHS == AndRHS) { 1181202375Srdivacky Value *NewICmp = 1182202375Srdivacky Builder->CreateICmpEQ(Op0RHS, Constant::getNullValue(I.getType())); 1183202375Srdivacky return new ZExtInst(NewICmp, I.getType()); 1184202375Srdivacky } 1185202375Srdivacky break; 1186202375Srdivacky } 1187252723Sdim 1188202375Srdivacky if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) 1189202375Srdivacky if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I)) 1190202375Srdivacky return Res; 1191218893Sdim } 1192252723Sdim 1193218893Sdim // If this is an integer truncation, and if the source is an 'and' with 1194218893Sdim // immediate, transform it. This frequently occurs for bitfield accesses. 1195218893Sdim { 1196218893Sdim Value *X = 0; ConstantInt *YC = 0; 1197218893Sdim if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) { 1198218893Sdim // Change: and (trunc (and X, YC) to T), C2 1199218893Sdim // into : and (trunc X to T), trunc(YC) & C2 1200252723Sdim // This will fold the two constants together, which may allow 1201218893Sdim // other simplifications. 1202218893Sdim Value *NewCast = Builder->CreateTrunc(X, I.getType(), "and.shrunk"); 1203218893Sdim Constant *C3 = ConstantExpr::getTrunc(YC, I.getType()); 1204218893Sdim C3 = ConstantExpr::getAnd(C3, AndRHS); 1205218893Sdim return BinaryOperator::CreateAnd(NewCast, C3); 1206202375Srdivacky } 1207202375Srdivacky } 1208202375Srdivacky 1209202375Srdivacky // Try to fold constant and into select arguments. 1210202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1211202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1212202375Srdivacky return R; 1213202375Srdivacky if (isa<PHINode>(Op0)) 1214202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 1215202375Srdivacky return NV; 1216202375Srdivacky } 1217202375Srdivacky 1218202375Srdivacky 1219202375Srdivacky // (~A & ~B) == (~(A | B)) - De Morgan's Law 1220202375Srdivacky if (Value *Op0NotVal = dyn_castNotVal(Op0)) 1221202375Srdivacky if (Value *Op1NotVal = dyn_castNotVal(Op1)) 1222202375Srdivacky if (Op0->hasOneUse() && Op1->hasOneUse()) { 1223202375Srdivacky Value *Or = Builder->CreateOr(Op0NotVal, Op1NotVal, 1224202375Srdivacky I.getName()+".demorgan"); 1225202375Srdivacky return BinaryOperator::CreateNot(Or); 1226202375Srdivacky } 1227252723Sdim 1228202375Srdivacky { 1229202375Srdivacky Value *A = 0, *B = 0, *C = 0, *D = 0; 1230202375Srdivacky // (A|B) & ~(A&B) -> A^B 1231202375Srdivacky if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1232202375Srdivacky match(Op1, m_Not(m_And(m_Value(C), m_Value(D)))) && 1233202375Srdivacky ((A == C && B == D) || (A == D && B == C))) 1234202375Srdivacky return BinaryOperator::CreateXor(A, B); 1235252723Sdim 1236202375Srdivacky // ~(A&B) & (A|B) -> A^B 1237202375Srdivacky if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1238202375Srdivacky match(Op0, m_Not(m_And(m_Value(C), m_Value(D)))) && 1239202375Srdivacky ((A == C && B == D) || (A == D && B == C))) 1240202375Srdivacky return BinaryOperator::CreateXor(A, B); 1241252723Sdim 1242226890Sdim // A&(A^B) => A & ~B 1243226890Sdim { 1244226890Sdim Value *tmpOp0 = Op0; 1245226890Sdim Value *tmpOp1 = Op1; 1246226890Sdim if (Op0->hasOneUse() && 1247226890Sdim match(Op0, m_Xor(m_Value(A), m_Value(B)))) { 1248226890Sdim if (A == Op1 || B == Op1 ) { 1249226890Sdim tmpOp1 = Op0; 1250226890Sdim tmpOp0 = Op1; 1251226890Sdim // Simplify below 1252226890Sdim } 1253202375Srdivacky } 1254202375Srdivacky 1255226890Sdim if (tmpOp1->hasOneUse() && 1256226890Sdim match(tmpOp1, m_Xor(m_Value(A), m_Value(B)))) { 1257226890Sdim if (B == tmpOp0) { 1258226890Sdim std::swap(A, B); 1259226890Sdim } 1260226890Sdim // Notice that the patten (A&(~B)) is actually (A&(-1^B)), so if 1261226890Sdim // A is originally -1 (or a vector of -1 and undefs), then we enter 1262226890Sdim // an endless loop. By checking that A is non-constant we ensure that 1263226890Sdim // we will never get to the loop. 1264226890Sdim if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B 1265226890Sdim return BinaryOperator::CreateAnd(A, Builder->CreateNot(B)); 1266202375Srdivacky } 1267202375Srdivacky } 1268202375Srdivacky 1269202375Srdivacky // (A&((~A)|B)) -> A&B 1270202375Srdivacky if (match(Op0, m_Or(m_Not(m_Specific(Op1)), m_Value(A))) || 1271202375Srdivacky match(Op0, m_Or(m_Value(A), m_Not(m_Specific(Op1))))) 1272202375Srdivacky return BinaryOperator::CreateAnd(A, Op1); 1273202375Srdivacky if (match(Op1, m_Or(m_Not(m_Specific(Op0)), m_Value(A))) || 1274202375Srdivacky match(Op1, m_Or(m_Value(A), m_Not(m_Specific(Op0))))) 1275202375Srdivacky return BinaryOperator::CreateAnd(A, Op0); 1276202375Srdivacky } 1277252723Sdim 1278202375Srdivacky if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1)) 1279202375Srdivacky if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0)) 1280204792Srdivacky if (Value *Res = FoldAndOfICmps(LHS, RHS)) 1281204792Srdivacky return ReplaceInstUsesWith(I, Res); 1282252723Sdim 1283203954Srdivacky // If and'ing two fcmp, try combine them into one. 1284203954Srdivacky if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 1285203954Srdivacky if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 1286204792Srdivacky if (Value *Res = FoldAndOfFCmps(LHS, RHS)) 1287204792Srdivacky return ReplaceInstUsesWith(I, Res); 1288252723Sdim 1289252723Sdim 1290202375Srdivacky // fold (and (cast A), (cast B)) -> (cast (and A, B)) 1291202375Srdivacky if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) 1292203954Srdivacky if (CastInst *Op1C = dyn_cast<CastInst>(Op1)) { 1293226890Sdim Type *SrcTy = Op0C->getOperand(0)->getType(); 1294203954Srdivacky if (Op0C->getOpcode() == Op1C->getOpcode() && // same cast kind ? 1295203954Srdivacky SrcTy == Op1C->getOperand(0)->getType() && 1296203954Srdivacky SrcTy->isIntOrIntVectorTy()) { 1297203954Srdivacky Value *Op0COp = Op0C->getOperand(0), *Op1COp = Op1C->getOperand(0); 1298252723Sdim 1299203954Srdivacky // Only do this if the casts both really cause code to be generated. 1300203954Srdivacky if (ShouldOptimizeCast(Op0C->getOpcode(), Op0COp, I.getType()) && 1301203954Srdivacky ShouldOptimizeCast(Op1C->getOpcode(), Op1COp, I.getType())) { 1302203954Srdivacky Value *NewOp = Builder->CreateAnd(Op0COp, Op1COp, I.getName()); 1303202375Srdivacky return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 1304202375Srdivacky } 1305252723Sdim 1306203954Srdivacky // If this is and(cast(icmp), cast(icmp)), try to fold this even if the 1307203954Srdivacky // cast is otherwise not optimizable. This happens for vector sexts. 1308203954Srdivacky if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1COp)) 1309203954Srdivacky if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0COp)) 1310204792Srdivacky if (Value *Res = FoldAndOfICmps(LHS, RHS)) 1311203954Srdivacky return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 1312252723Sdim 1313203954Srdivacky // If this is and(cast(fcmp), cast(fcmp)), try to fold this even if the 1314203954Srdivacky // cast is otherwise not optimizable. This happens for vector sexts. 1315203954Srdivacky if (FCmpInst *RHS = dyn_cast<FCmpInst>(Op1COp)) 1316203954Srdivacky if (FCmpInst *LHS = dyn_cast<FCmpInst>(Op0COp)) 1317204792Srdivacky if (Value *Res = FoldAndOfFCmps(LHS, RHS)) 1318203954Srdivacky return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 1319202375Srdivacky } 1320203954Srdivacky } 1321252723Sdim 1322202375Srdivacky // (X >> Z) & (Y >> Z) -> (X&Y) >> Z for all shifts. 1323202375Srdivacky if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) { 1324202375Srdivacky if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0)) 1325252723Sdim if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() && 1326202375Srdivacky SI0->getOperand(1) == SI1->getOperand(1) && 1327202375Srdivacky (SI0->hasOneUse() || SI1->hasOneUse())) { 1328202375Srdivacky Value *NewOp = 1329202375Srdivacky Builder->CreateAnd(SI0->getOperand(0), SI1->getOperand(0), 1330202375Srdivacky SI0->getName()); 1331252723Sdim return BinaryOperator::Create(SI1->getOpcode(), NewOp, 1332202375Srdivacky SI1->getOperand(1)); 1333202375Srdivacky } 1334202375Srdivacky } 1335202375Srdivacky 1336252723Sdim { 1337252723Sdim Value *X = 0; 1338252723Sdim bool OpsSwapped = false; 1339252723Sdim // Canonicalize SExt or Not to the LHS 1340252723Sdim if (match(Op1, m_SExt(m_Value())) || 1341252723Sdim match(Op1, m_Not(m_Value()))) { 1342252723Sdim std::swap(Op0, Op1); 1343252723Sdim OpsSwapped = true; 1344252723Sdim } 1345252723Sdim 1346252723Sdim // Fold (and (sext bool to A), B) --> (select bool, B, 0) 1347252723Sdim if (match(Op0, m_SExt(m_Value(X))) && 1348252723Sdim X->getType()->getScalarType()->isIntegerTy(1)) { 1349252723Sdim Value *Zero = Constant::getNullValue(Op1->getType()); 1350252723Sdim return SelectInst::Create(X, Op1, Zero); 1351252723Sdim } 1352252723Sdim 1353252723Sdim // Fold (and ~(sext bool to A), B) --> (select bool, 0, B) 1354252723Sdim if (match(Op0, m_Not(m_SExt(m_Value(X)))) && 1355252723Sdim X->getType()->getScalarType()->isIntegerTy(1)) { 1356252723Sdim Value *Zero = Constant::getNullValue(Op0->getType()); 1357252723Sdim return SelectInst::Create(X, Zero, Op1); 1358252723Sdim } 1359252723Sdim 1360252723Sdim if (OpsSwapped) 1361252723Sdim std::swap(Op0, Op1); 1362252723Sdim } 1363252723Sdim 1364202375Srdivacky return Changed ? &I : 0; 1365202375Srdivacky} 1366202375Srdivacky 1367202375Srdivacky/// CollectBSwapParts - Analyze the specified subexpression and see if it is 1368202375Srdivacky/// capable of providing pieces of a bswap. The subexpression provides pieces 1369202375Srdivacky/// of a bswap if it is proven that each of the non-zero bytes in the output of 1370202375Srdivacky/// the expression came from the corresponding "byte swapped" byte in some other 1371202375Srdivacky/// value. For example, if the current subexpression is "(shl i32 %X, 24)" then 1372202375Srdivacky/// we know that the expression deposits the low byte of %X into the high byte 1373202375Srdivacky/// of the bswap result and that all other bytes are zero. This expression is 1374202375Srdivacky/// accepted, the high byte of ByteValues is set to X to indicate a correct 1375202375Srdivacky/// match. 1376202375Srdivacky/// 1377202375Srdivacky/// This function returns true if the match was unsuccessful and false if so. 1378202375Srdivacky/// On entry to the function the "OverallLeftShift" is a signed integer value 1379202375Srdivacky/// indicating the number of bytes that the subexpression is later shifted. For 1380202375Srdivacky/// example, if the expression is later right shifted by 16 bits, the 1381202375Srdivacky/// OverallLeftShift value would be -2 on entry. This is used to specify which 1382202375Srdivacky/// byte of ByteValues is actually being set. 1383202375Srdivacky/// 1384202375Srdivacky/// Similarly, ByteMask is a bitmask where a bit is clear if its corresponding 1385202375Srdivacky/// byte is masked to zero by a user. For example, in (X & 255), X will be 1386202375Srdivacky/// processed with a bytemask of 1. Because bytemask is 32-bits, this limits 1387202375Srdivacky/// this function to working on up to 32-byte (256 bit) values. ByteMask is 1388202375Srdivacky/// always in the local (OverallLeftShift) coordinate space. 1389202375Srdivacky/// 1390202375Srdivackystatic bool CollectBSwapParts(Value *V, int OverallLeftShift, uint32_t ByteMask, 1391263509Sdim SmallVectorImpl<Value *> &ByteValues) { 1392202375Srdivacky if (Instruction *I = dyn_cast<Instruction>(V)) { 1393202375Srdivacky // If this is an or instruction, it may be an inner node of the bswap. 1394202375Srdivacky if (I->getOpcode() == Instruction::Or) { 1395202375Srdivacky return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1396202375Srdivacky ByteValues) || 1397202375Srdivacky CollectBSwapParts(I->getOperand(1), OverallLeftShift, ByteMask, 1398202375Srdivacky ByteValues); 1399202375Srdivacky } 1400252723Sdim 1401202375Srdivacky // If this is a logical shift by a constant multiple of 8, recurse with 1402202375Srdivacky // OverallLeftShift and ByteMask adjusted. 1403202375Srdivacky if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) { 1404252723Sdim unsigned ShAmt = 1405202375Srdivacky cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U); 1406202375Srdivacky // Ensure the shift amount is defined and of a byte value. 1407202375Srdivacky if ((ShAmt & 7) || (ShAmt > 8*ByteValues.size())) 1408202375Srdivacky return true; 1409202375Srdivacky 1410202375Srdivacky unsigned ByteShift = ShAmt >> 3; 1411202375Srdivacky if (I->getOpcode() == Instruction::Shl) { 1412202375Srdivacky // X << 2 -> collect(X, +2) 1413202375Srdivacky OverallLeftShift += ByteShift; 1414202375Srdivacky ByteMask >>= ByteShift; 1415202375Srdivacky } else { 1416202375Srdivacky // X >>u 2 -> collect(X, -2) 1417202375Srdivacky OverallLeftShift -= ByteShift; 1418202375Srdivacky ByteMask <<= ByteShift; 1419202375Srdivacky ByteMask &= (~0U >> (32-ByteValues.size())); 1420202375Srdivacky } 1421202375Srdivacky 1422202375Srdivacky if (OverallLeftShift >= (int)ByteValues.size()) return true; 1423202375Srdivacky if (OverallLeftShift <= -(int)ByteValues.size()) return true; 1424202375Srdivacky 1425252723Sdim return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1426202375Srdivacky ByteValues); 1427202375Srdivacky } 1428202375Srdivacky 1429202375Srdivacky // If this is a logical 'and' with a mask that clears bytes, clear the 1430202375Srdivacky // corresponding bytes in ByteMask. 1431202375Srdivacky if (I->getOpcode() == Instruction::And && 1432202375Srdivacky isa<ConstantInt>(I->getOperand(1))) { 1433202375Srdivacky // Scan every byte of the and mask, seeing if the byte is either 0 or 255. 1434202375Srdivacky unsigned NumBytes = ByteValues.size(); 1435202375Srdivacky APInt Byte(I->getType()->getPrimitiveSizeInBits(), 255); 1436202375Srdivacky const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue(); 1437252723Sdim 1438202375Srdivacky for (unsigned i = 0; i != NumBytes; ++i, Byte <<= 8) { 1439202375Srdivacky // If this byte is masked out by a later operation, we don't care what 1440202375Srdivacky // the and mask is. 1441202375Srdivacky if ((ByteMask & (1 << i)) == 0) 1442202375Srdivacky continue; 1443252723Sdim 1444202375Srdivacky // If the AndMask is all zeros for this byte, clear the bit. 1445202375Srdivacky APInt MaskB = AndMask & Byte; 1446202375Srdivacky if (MaskB == 0) { 1447202375Srdivacky ByteMask &= ~(1U << i); 1448202375Srdivacky continue; 1449202375Srdivacky } 1450252723Sdim 1451202375Srdivacky // If the AndMask is not all ones for this byte, it's not a bytezap. 1452202375Srdivacky if (MaskB != Byte) 1453202375Srdivacky return true; 1454202375Srdivacky 1455202375Srdivacky // Otherwise, this byte is kept. 1456202375Srdivacky } 1457202375Srdivacky 1458252723Sdim return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask, 1459202375Srdivacky ByteValues); 1460202375Srdivacky } 1461202375Srdivacky } 1462252723Sdim 1463202375Srdivacky // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be 1464202375Srdivacky // the input value to the bswap. Some observations: 1) if more than one byte 1465202375Srdivacky // is demanded from this input, then it could not be successfully assembled 1466202375Srdivacky // into a byteswap. At least one of the two bytes would not be aligned with 1467202375Srdivacky // their ultimate destination. 1468202375Srdivacky if (!isPowerOf2_32(ByteMask)) return true; 1469263509Sdim unsigned InputByteNo = countTrailingZeros(ByteMask); 1470252723Sdim 1471202375Srdivacky // 2) The input and ultimate destinations must line up: if byte 3 of an i32 1472202375Srdivacky // is demanded, it needs to go into byte 0 of the result. This means that the 1473202375Srdivacky // byte needs to be shifted until it lands in the right byte bucket. The 1474202375Srdivacky // shift amount depends on the position: if the byte is coming from the high 1475202375Srdivacky // part of the value (e.g. byte 3) then it must be shifted right. If from the 1476202375Srdivacky // low part, it must be shifted left. 1477202375Srdivacky unsigned DestByteNo = InputByteNo + OverallLeftShift; 1478235633Sdim if (ByteValues.size()-1-DestByteNo != InputByteNo) 1479235633Sdim return true; 1480252723Sdim 1481202375Srdivacky // If the destination byte value is already defined, the values are or'd 1482202375Srdivacky // together, which isn't a bswap (unless it's an or of the same bits). 1483202375Srdivacky if (ByteValues[DestByteNo] && ByteValues[DestByteNo] != V) 1484202375Srdivacky return true; 1485202375Srdivacky ByteValues[DestByteNo] = V; 1486202375Srdivacky return false; 1487202375Srdivacky} 1488202375Srdivacky 1489202375Srdivacky/// MatchBSwap - Given an OR instruction, check to see if this is a bswap idiom. 1490202375Srdivacky/// If so, insert the new bswap intrinsic and return it. 1491202375SrdivackyInstruction *InstCombiner::MatchBSwap(BinaryOperator &I) { 1492224145Sdim IntegerType *ITy = dyn_cast<IntegerType>(I.getType()); 1493252723Sdim if (!ITy || ITy->getBitWidth() % 16 || 1494202375Srdivacky // ByteMask only allows up to 32-byte values. 1495252723Sdim ITy->getBitWidth() > 32*8) 1496202375Srdivacky return 0; // Can only bswap pairs of bytes. Can't do vectors. 1497252723Sdim 1498202375Srdivacky /// ByteValues - For each byte of the result, we keep track of which value 1499202375Srdivacky /// defines each byte. 1500202375Srdivacky SmallVector<Value*, 8> ByteValues; 1501202375Srdivacky ByteValues.resize(ITy->getBitWidth()/8); 1502252723Sdim 1503202375Srdivacky // Try to find all the pieces corresponding to the bswap. 1504202375Srdivacky uint32_t ByteMask = ~0U >> (32-ByteValues.size()); 1505202375Srdivacky if (CollectBSwapParts(&I, 0, ByteMask, ByteValues)) 1506202375Srdivacky return 0; 1507252723Sdim 1508202375Srdivacky // Check to see if all of the bytes come from the same value. 1509202375Srdivacky Value *V = ByteValues[0]; 1510202375Srdivacky if (V == 0) return 0; // Didn't find a byte? Must be zero. 1511252723Sdim 1512202375Srdivacky // Check to make sure that all of the bytes come from the same value. 1513202375Srdivacky for (unsigned i = 1, e = ByteValues.size(); i != e; ++i) 1514202375Srdivacky if (ByteValues[i] != V) 1515202375Srdivacky return 0; 1516202375Srdivacky Module *M = I.getParent()->getParent()->getParent(); 1517224145Sdim Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, ITy); 1518202375Srdivacky return CallInst::Create(F, V); 1519202375Srdivacky} 1520202375Srdivacky 1521202375Srdivacky/// MatchSelectFromAndOr - We have an expression of the form (A&C)|(B&D). Check 1522202375Srdivacky/// If A is (cond?-1:0) and either B or D is ~(cond?-1,0) or (cond?0,-1), then 1523202375Srdivacky/// we can simplify this expression to "cond ? C : D or B". 1524202375Srdivackystatic Instruction *MatchSelectFromAndOr(Value *A, Value *B, 1525202375Srdivacky Value *C, Value *D) { 1526202375Srdivacky // If A is not a select of -1/0, this cannot match. 1527202375Srdivacky Value *Cond = 0; 1528203954Srdivacky if (!match(A, m_SExt(m_Value(Cond))) || 1529203954Srdivacky !Cond->getType()->isIntegerTy(1)) 1530202375Srdivacky return 0; 1531202375Srdivacky 1532202375Srdivacky // ((cond?-1:0)&C) | (B&(cond?0:-1)) -> cond ? C : B. 1533203954Srdivacky if (match(D, m_Not(m_SExt(m_Specific(Cond))))) 1534202375Srdivacky return SelectInst::Create(Cond, C, B); 1535203954Srdivacky if (match(D, m_SExt(m_Not(m_Specific(Cond))))) 1536202375Srdivacky return SelectInst::Create(Cond, C, B); 1537252723Sdim 1538202375Srdivacky // ((cond?-1:0)&C) | ((cond?0:-1)&D) -> cond ? C : D. 1539203954Srdivacky if (match(B, m_Not(m_SExt(m_Specific(Cond))))) 1540202375Srdivacky return SelectInst::Create(Cond, C, D); 1541203954Srdivacky if (match(B, m_SExt(m_Not(m_Specific(Cond))))) 1542202375Srdivacky return SelectInst::Create(Cond, C, D); 1543202375Srdivacky return 0; 1544202375Srdivacky} 1545202375Srdivacky 1546263509Sdim/// IsOneHotValue - Returns true for "one-hot" values (values where at most 1547263509Sdim/// one bit can be set). 1548263509Sdimstatic bool IsOneHotValue(Value *V) { 1549263509Sdim // Match 1<<K. 1550263509Sdim if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) 1551263509Sdim if (BO->getOpcode() == Instruction::Shl) { 1552263509Sdim ConstantInt *One = dyn_cast<ConstantInt>(BO->getOperand(0)); 1553263509Sdim return One && One->isOne(); 1554263509Sdim } 1555263509Sdim 1556263509Sdim // Check for power of two integer constants. 1557263509Sdim if (ConstantInt *K = dyn_cast<ConstantInt>(V)) 1558263509Sdim return K->getValue().isPowerOf2(); 1559263509Sdim 1560263509Sdim return false; 1561263509Sdim} 1562263509Sdim 1563202375Srdivacky/// FoldOrOfICmps - Fold (icmp)|(icmp) if possible. 1564204792SrdivackyValue *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS) { 1565202375Srdivacky ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate(); 1566202375Srdivacky 1567263509Sdim // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2) 1568263509Sdim // if K1 and K2 are a one-bit mask. 1569263509Sdim ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1)); 1570263509Sdim ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1)); 1571263509Sdim 1572263509Sdim if (LHS->getPredicate() == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero() && 1573263509Sdim RHS->getPredicate() == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) { 1574263509Sdim 1575263509Sdim BinaryOperator *LAnd = dyn_cast<BinaryOperator>(LHS->getOperand(0)); 1576263509Sdim BinaryOperator *RAnd = dyn_cast<BinaryOperator>(RHS->getOperand(0)); 1577263509Sdim if (LAnd && RAnd && LAnd->hasOneUse() && RHS->hasOneUse() && 1578263509Sdim LAnd->getOpcode() == Instruction::And && 1579263509Sdim RAnd->getOpcode() == Instruction::And) { 1580263509Sdim 1581263509Sdim Value *Mask = 0; 1582263509Sdim Value *Masked = 0; 1583263509Sdim if (LAnd->getOperand(0) == RAnd->getOperand(0) && 1584263509Sdim IsOneHotValue(LAnd->getOperand(1)) && 1585263509Sdim IsOneHotValue(RAnd->getOperand(1))) { 1586263509Sdim Mask = Builder->CreateOr(LAnd->getOperand(1), RAnd->getOperand(1)); 1587263509Sdim Masked = Builder->CreateAnd(LAnd->getOperand(0), Mask); 1588263509Sdim } else if (LAnd->getOperand(1) == RAnd->getOperand(1) && 1589263509Sdim IsOneHotValue(LAnd->getOperand(0)) && 1590263509Sdim IsOneHotValue(RAnd->getOperand(0))) { 1591263509Sdim Mask = Builder->CreateOr(LAnd->getOperand(0), RAnd->getOperand(0)); 1592263509Sdim Masked = Builder->CreateAnd(LAnd->getOperand(1), Mask); 1593263509Sdim } 1594263509Sdim 1595263509Sdim if (Masked) 1596263509Sdim return Builder->CreateICmp(ICmpInst::ICMP_NE, Masked, Mask); 1597263509Sdim } 1598263509Sdim } 1599263509Sdim 1600202375Srdivacky // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B) 1601202375Srdivacky if (PredicatesFoldable(LHSCC, RHSCC)) { 1602202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(1) && 1603202375Srdivacky LHS->getOperand(1) == RHS->getOperand(0)) 1604202375Srdivacky LHS->swapOperands(); 1605202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(0) && 1606202375Srdivacky LHS->getOperand(1) == RHS->getOperand(1)) { 1607202375Srdivacky Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 1608202375Srdivacky unsigned Code = getICmpCode(LHS) | getICmpCode(RHS); 1609202375Srdivacky bool isSigned = LHS->isSigned() || RHS->isSigned(); 1610235633Sdim return getNewICmpValue(isSigned, Code, Op0, Op1, Builder); 1611202375Srdivacky } 1612202375Srdivacky } 1613218893Sdim 1614218893Sdim // handle (roughly): 1615218893Sdim // (icmp ne (A & B), C) | (icmp ne (A & D), E) 1616263509Sdim if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder)) 1617218893Sdim return V; 1618218893Sdim 1619263509Sdim Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0); 1620263509Sdim if (LHS->hasOneUse() || RHS->hasOneUse()) { 1621263509Sdim // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1) 1622263509Sdim // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1) 1623263509Sdim Value *A = 0, *B = 0; 1624263509Sdim if (LHSCC == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero()) { 1625263509Sdim B = Val; 1626263509Sdim if (RHSCC == ICmpInst::ICMP_ULT && Val == RHS->getOperand(1)) 1627263509Sdim A = Val2; 1628263509Sdim else if (RHSCC == ICmpInst::ICMP_UGT && Val == Val2) 1629263509Sdim A = RHS->getOperand(1); 1630263509Sdim } 1631263509Sdim // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1) 1632263509Sdim // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1) 1633263509Sdim else if (RHSCC == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) { 1634263509Sdim B = Val2; 1635263509Sdim if (LHSCC == ICmpInst::ICMP_ULT && Val2 == LHS->getOperand(1)) 1636263509Sdim A = Val; 1637263509Sdim else if (LHSCC == ICmpInst::ICMP_UGT && Val2 == Val) 1638263509Sdim A = LHS->getOperand(1); 1639263509Sdim } 1640263509Sdim if (A && B) 1641263509Sdim return Builder->CreateICmp( 1642263509Sdim ICmpInst::ICMP_UGE, 1643263509Sdim Builder->CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A); 1644263509Sdim } 1645263509Sdim 1646202375Srdivacky // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2). 1647202375Srdivacky if (LHSCst == 0 || RHSCst == 0) return 0; 1648202375Srdivacky 1649212904Sdim if (LHSCst == RHSCst && LHSCC == RHSCC) { 1650212904Sdim // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0) 1651212904Sdim if (LHSCC == ICmpInst::ICMP_NE && LHSCst->isZero()) { 1652212904Sdim Value *NewOr = Builder->CreateOr(Val, Val2); 1653212904Sdim return Builder->CreateICmp(LHSCC, NewOr, LHSCst); 1654212904Sdim } 1655202375Srdivacky } 1656218893Sdim 1657218893Sdim // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1) 1658218893Sdim // iff C2 + CA == C1. 1659218893Sdim if (LHSCC == ICmpInst::ICMP_ULT && RHSCC == ICmpInst::ICMP_EQ) { 1660218893Sdim ConstantInt *AddCst; 1661218893Sdim if (match(Val, m_Add(m_Specific(Val2), m_ConstantInt(AddCst)))) 1662218893Sdim if (RHSCst->getValue() + AddCst->getValue() == LHSCst->getValue()) 1663218893Sdim return Builder->CreateICmpULE(Val, LHSCst); 1664218893Sdim } 1665218893Sdim 1666202375Srdivacky // From here on, we only handle: 1667202375Srdivacky // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler. 1668202375Srdivacky if (Val != Val2) return 0; 1669252723Sdim 1670202375Srdivacky // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere. 1671202375Srdivacky if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE || 1672202375Srdivacky RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE || 1673202375Srdivacky LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE || 1674202375Srdivacky RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE) 1675202375Srdivacky return 0; 1676252723Sdim 1677202375Srdivacky // We can't fold (ugt x, C) | (sgt x, C2). 1678202375Srdivacky if (!PredicatesFoldable(LHSCC, RHSCC)) 1679202375Srdivacky return 0; 1680252723Sdim 1681202375Srdivacky // Ensure that the larger constant is on the RHS. 1682202375Srdivacky bool ShouldSwap; 1683202375Srdivacky if (CmpInst::isSigned(LHSCC) || 1684252723Sdim (ICmpInst::isEquality(LHSCC) && 1685202375Srdivacky CmpInst::isSigned(RHSCC))) 1686202375Srdivacky ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue()); 1687202375Srdivacky else 1688202375Srdivacky ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue()); 1689252723Sdim 1690202375Srdivacky if (ShouldSwap) { 1691202375Srdivacky std::swap(LHS, RHS); 1692202375Srdivacky std::swap(LHSCst, RHSCst); 1693202375Srdivacky std::swap(LHSCC, RHSCC); 1694202375Srdivacky } 1695252723Sdim 1696203954Srdivacky // At this point, we know we have two icmp instructions 1697202375Srdivacky // comparing a value against two constants and or'ing the result 1698202375Srdivacky // together. Because of the above check, we know that we only have 1699202375Srdivacky // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the 1700202375Srdivacky // icmp folding check above), that the two constants are not 1701202375Srdivacky // equal. 1702202375Srdivacky assert(LHSCst != RHSCst && "Compares not folded above?"); 1703202375Srdivacky 1704202375Srdivacky switch (LHSCC) { 1705202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1706202375Srdivacky case ICmpInst::ICMP_EQ: 1707202375Srdivacky switch (RHSCC) { 1708202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1709202375Srdivacky case ICmpInst::ICMP_EQ: 1710252723Sdim if (LHS->getOperand(0) == RHS->getOperand(0)) { 1711252723Sdim // if LHSCst and RHSCst differ only by one bit: 1712252723Sdim // (A == C1 || A == C2) -> (A & ~(C1 ^ C2)) == C1 1713252723Sdim assert(LHSCst->getValue().ule(LHSCst->getValue())); 1714252723Sdim 1715252723Sdim APInt Xor = LHSCst->getValue() ^ RHSCst->getValue(); 1716252723Sdim if (Xor.isPowerOf2()) { 1717252723Sdim Value *NegCst = Builder->getInt(~Xor); 1718252723Sdim Value *And = Builder->CreateAnd(LHS->getOperand(0), NegCst); 1719252723Sdim return Builder->CreateICmp(ICmpInst::ICMP_EQ, And, LHSCst); 1720252723Sdim } 1721252723Sdim } 1722252723Sdim 1723202375Srdivacky if (LHSCst == SubOne(RHSCst)) { 1724202375Srdivacky // (X == 13 | X == 14) -> X-13 <u 2 1725202375Srdivacky Constant *AddCST = ConstantExpr::getNeg(LHSCst); 1726202375Srdivacky Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off"); 1727202375Srdivacky AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst); 1728204792Srdivacky return Builder->CreateICmpULT(Add, AddCST); 1729202375Srdivacky } 1730252723Sdim 1731202375Srdivacky break; // (X == 13 | X == 15) -> no change 1732202375Srdivacky case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change 1733202375Srdivacky case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change 1734202375Srdivacky break; 1735202375Srdivacky case ICmpInst::ICMP_NE: // (X == 13 | X != 15) -> X != 15 1736202375Srdivacky case ICmpInst::ICMP_ULT: // (X == 13 | X u< 15) -> X u< 15 1737202375Srdivacky case ICmpInst::ICMP_SLT: // (X == 13 | X s< 15) -> X s< 15 1738204792Srdivacky return RHS; 1739202375Srdivacky } 1740202375Srdivacky break; 1741202375Srdivacky case ICmpInst::ICMP_NE: 1742202375Srdivacky switch (RHSCC) { 1743202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1744202375Srdivacky case ICmpInst::ICMP_EQ: // (X != 13 | X == 15) -> X != 13 1745202375Srdivacky case ICmpInst::ICMP_UGT: // (X != 13 | X u> 15) -> X != 13 1746202375Srdivacky case ICmpInst::ICMP_SGT: // (X != 13 | X s> 15) -> X != 13 1747204792Srdivacky return LHS; 1748202375Srdivacky case ICmpInst::ICMP_NE: // (X != 13 | X != 15) -> true 1749202375Srdivacky case ICmpInst::ICMP_ULT: // (X != 13 | X u< 15) -> true 1750202375Srdivacky case ICmpInst::ICMP_SLT: // (X != 13 | X s< 15) -> true 1751263509Sdim return Builder->getTrue(); 1752202375Srdivacky } 1753202375Srdivacky case ICmpInst::ICMP_ULT: 1754202375Srdivacky switch (RHSCC) { 1755202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1756202375Srdivacky case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change 1757202375Srdivacky break; 1758202375Srdivacky case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2 1759202375Srdivacky // If RHSCst is [us]MAXINT, it is always false. Not handling 1760202375Srdivacky // this can cause overflow. 1761202375Srdivacky if (RHSCst->isMaxValue(false)) 1762204792Srdivacky return LHS; 1763204792Srdivacky return InsertRangeTest(Val, LHSCst, AddOne(RHSCst), false, false); 1764202375Srdivacky case ICmpInst::ICMP_SGT: // (X u< 13 | X s> 15) -> no change 1765202375Srdivacky break; 1766202375Srdivacky case ICmpInst::ICMP_NE: // (X u< 13 | X != 15) -> X != 15 1767202375Srdivacky case ICmpInst::ICMP_ULT: // (X u< 13 | X u< 15) -> X u< 15 1768204792Srdivacky return RHS; 1769202375Srdivacky case ICmpInst::ICMP_SLT: // (X u< 13 | X s< 15) -> no change 1770202375Srdivacky break; 1771202375Srdivacky } 1772202375Srdivacky break; 1773202375Srdivacky case ICmpInst::ICMP_SLT: 1774202375Srdivacky switch (RHSCC) { 1775202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1776202375Srdivacky case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change 1777202375Srdivacky break; 1778202375Srdivacky case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2 1779202375Srdivacky // If RHSCst is [us]MAXINT, it is always false. Not handling 1780202375Srdivacky // this can cause overflow. 1781202375Srdivacky if (RHSCst->isMaxValue(true)) 1782204792Srdivacky return LHS; 1783204792Srdivacky return InsertRangeTest(Val, LHSCst, AddOne(RHSCst), true, false); 1784202375Srdivacky case ICmpInst::ICMP_UGT: // (X s< 13 | X u> 15) -> no change 1785202375Srdivacky break; 1786202375Srdivacky case ICmpInst::ICMP_NE: // (X s< 13 | X != 15) -> X != 15 1787202375Srdivacky case ICmpInst::ICMP_SLT: // (X s< 13 | X s< 15) -> X s< 15 1788204792Srdivacky return RHS; 1789202375Srdivacky case ICmpInst::ICMP_ULT: // (X s< 13 | X u< 15) -> no change 1790202375Srdivacky break; 1791202375Srdivacky } 1792202375Srdivacky break; 1793202375Srdivacky case ICmpInst::ICMP_UGT: 1794202375Srdivacky switch (RHSCC) { 1795202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1796202375Srdivacky case ICmpInst::ICMP_EQ: // (X u> 13 | X == 15) -> X u> 13 1797202375Srdivacky case ICmpInst::ICMP_UGT: // (X u> 13 | X u> 15) -> X u> 13 1798204792Srdivacky return LHS; 1799202375Srdivacky case ICmpInst::ICMP_SGT: // (X u> 13 | X s> 15) -> no change 1800202375Srdivacky break; 1801202375Srdivacky case ICmpInst::ICMP_NE: // (X u> 13 | X != 15) -> true 1802202375Srdivacky case ICmpInst::ICMP_ULT: // (X u> 13 | X u< 15) -> true 1803263509Sdim return Builder->getTrue(); 1804202375Srdivacky case ICmpInst::ICMP_SLT: // (X u> 13 | X s< 15) -> no change 1805202375Srdivacky break; 1806202375Srdivacky } 1807202375Srdivacky break; 1808202375Srdivacky case ICmpInst::ICMP_SGT: 1809202375Srdivacky switch (RHSCC) { 1810202375Srdivacky default: llvm_unreachable("Unknown integer condition code!"); 1811202375Srdivacky case ICmpInst::ICMP_EQ: // (X s> 13 | X == 15) -> X > 13 1812202375Srdivacky case ICmpInst::ICMP_SGT: // (X s> 13 | X s> 15) -> X > 13 1813204792Srdivacky return LHS; 1814202375Srdivacky case ICmpInst::ICMP_UGT: // (X s> 13 | X u> 15) -> no change 1815202375Srdivacky break; 1816202375Srdivacky case ICmpInst::ICMP_NE: // (X s> 13 | X != 15) -> true 1817202375Srdivacky case ICmpInst::ICMP_SLT: // (X s> 13 | X s< 15) -> true 1818263509Sdim return Builder->getTrue(); 1819202375Srdivacky case ICmpInst::ICMP_ULT: // (X s> 13 | X u< 15) -> no change 1820202375Srdivacky break; 1821202375Srdivacky } 1822202375Srdivacky break; 1823202375Srdivacky } 1824202375Srdivacky return 0; 1825202375Srdivacky} 1826202375Srdivacky 1827204792Srdivacky/// FoldOrOfFCmps - Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of 1828204792Srdivacky/// instcombine, this returns a Value which should already be inserted into the 1829204792Srdivacky/// function. 1830204792SrdivackyValue *InstCombiner::FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) { 1831202375Srdivacky if (LHS->getPredicate() == FCmpInst::FCMP_UNO && 1832252723Sdim RHS->getPredicate() == FCmpInst::FCMP_UNO && 1833202375Srdivacky LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType()) { 1834202375Srdivacky if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1))) 1835202375Srdivacky if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) { 1836202375Srdivacky // If either of the constants are nans, then the whole thing returns 1837202375Srdivacky // true. 1838202375Srdivacky if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN()) 1839263509Sdim return Builder->getTrue(); 1840252723Sdim 1841202375Srdivacky // Otherwise, no need to compare the two constants, compare the 1842202375Srdivacky // rest. 1843204792Srdivacky return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0)); 1844202375Srdivacky } 1845252723Sdim 1846202375Srdivacky // Handle vector zeros. This occurs because the canonical form of 1847202375Srdivacky // "fcmp uno x,x" is "fcmp uno x, 0". 1848202375Srdivacky if (isa<ConstantAggregateZero>(LHS->getOperand(1)) && 1849202375Srdivacky isa<ConstantAggregateZero>(RHS->getOperand(1))) 1850204792Srdivacky return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0)); 1851252723Sdim 1852202375Srdivacky return 0; 1853202375Srdivacky } 1854252723Sdim 1855202375Srdivacky Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1); 1856202375Srdivacky Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1); 1857202375Srdivacky FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate(); 1858252723Sdim 1859202375Srdivacky if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) { 1860202375Srdivacky // Swap RHS operands to match LHS. 1861202375Srdivacky Op1CC = FCmpInst::getSwappedPredicate(Op1CC); 1862202375Srdivacky std::swap(Op1LHS, Op1RHS); 1863202375Srdivacky } 1864202375Srdivacky if (Op0LHS == Op1LHS && Op0RHS == Op1RHS) { 1865202375Srdivacky // Simplify (fcmp cc0 x, y) | (fcmp cc1 x, y). 1866202375Srdivacky if (Op0CC == Op1CC) 1867204792Srdivacky return Builder->CreateFCmp((FCmpInst::Predicate)Op0CC, Op0LHS, Op0RHS); 1868202375Srdivacky if (Op0CC == FCmpInst::FCMP_TRUE || Op1CC == FCmpInst::FCMP_TRUE) 1869204792Srdivacky return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 1870202375Srdivacky if (Op0CC == FCmpInst::FCMP_FALSE) 1871204792Srdivacky return RHS; 1872202375Srdivacky if (Op1CC == FCmpInst::FCMP_FALSE) 1873204792Srdivacky return LHS; 1874202375Srdivacky bool Op0Ordered; 1875202375Srdivacky bool Op1Ordered; 1876202375Srdivacky unsigned Op0Pred = getFCmpCode(Op0CC, Op0Ordered); 1877202375Srdivacky unsigned Op1Pred = getFCmpCode(Op1CC, Op1Ordered); 1878202375Srdivacky if (Op0Ordered == Op1Ordered) { 1879202375Srdivacky // If both are ordered or unordered, return a new fcmp with 1880202375Srdivacky // or'ed predicates. 1881204792Srdivacky return getFCmpValue(Op0Ordered, Op0Pred|Op1Pred, Op0LHS, Op0RHS, Builder); 1882202375Srdivacky } 1883202375Srdivacky } 1884202375Srdivacky return 0; 1885202375Srdivacky} 1886202375Srdivacky 1887202375Srdivacky/// FoldOrWithConstants - This helper function folds: 1888202375Srdivacky/// 1889202375Srdivacky/// ((A | B) & C1) | (B & C2) 1890202375Srdivacky/// 1891202375Srdivacky/// into: 1892252723Sdim/// 1893202375Srdivacky/// (A & C1) | B 1894202375Srdivacky/// 1895202375Srdivacky/// when the XOR of the two constants is "all ones" (-1). 1896202375SrdivackyInstruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op, 1897202375Srdivacky Value *A, Value *B, Value *C) { 1898202375Srdivacky ConstantInt *CI1 = dyn_cast<ConstantInt>(C); 1899202375Srdivacky if (!CI1) return 0; 1900202375Srdivacky 1901202375Srdivacky Value *V1 = 0; 1902202375Srdivacky ConstantInt *CI2 = 0; 1903202375Srdivacky if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) return 0; 1904202375Srdivacky 1905202375Srdivacky APInt Xor = CI1->getValue() ^ CI2->getValue(); 1906202375Srdivacky if (!Xor.isAllOnesValue()) return 0; 1907202375Srdivacky 1908202375Srdivacky if (V1 == A || V1 == B) { 1909202375Srdivacky Value *NewOp = Builder->CreateAnd((V1 == A) ? B : A, CI1); 1910202375Srdivacky return BinaryOperator::CreateOr(NewOp, V1); 1911202375Srdivacky } 1912202375Srdivacky 1913202375Srdivacky return 0; 1914202375Srdivacky} 1915202375Srdivacky 1916202375SrdivackyInstruction *InstCombiner::visitOr(BinaryOperator &I) { 1917218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 1918202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1919202375Srdivacky 1920202375Srdivacky if (Value *V = SimplifyOrInst(Op0, Op1, TD)) 1921202375Srdivacky return ReplaceInstUsesWith(I, V); 1922204642Srdivacky 1923218893Sdim // (A&B)|(A&C) -> A&(B|C) etc 1924218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 1925218893Sdim return ReplaceInstUsesWith(I, V); 1926218893Sdim 1927252723Sdim // See if we can simplify any instructions used by the instruction whose sole 1928202375Srdivacky // purpose is to compute bits we don't care about. 1929202375Srdivacky if (SimplifyDemandedInstructionBits(I)) 1930202375Srdivacky return &I; 1931202375Srdivacky 1932202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 1933202375Srdivacky ConstantInt *C1 = 0; Value *X = 0; 1934202375Srdivacky // (X & C1) | C2 --> (X | C2) & (C1|C2) 1935204642Srdivacky // iff (C1 & C2) == 0. 1936202375Srdivacky if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && 1937204642Srdivacky (RHS->getValue() & C1->getValue()) != 0 && 1938202375Srdivacky Op0->hasOneUse()) { 1939202375Srdivacky Value *Or = Builder->CreateOr(X, RHS); 1940202375Srdivacky Or->takeName(Op0); 1941252723Sdim return BinaryOperator::CreateAnd(Or, 1942263509Sdim Builder->getInt(RHS->getValue() | C1->getValue())); 1943202375Srdivacky } 1944202375Srdivacky 1945202375Srdivacky // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2) 1946202375Srdivacky if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && 1947202375Srdivacky Op0->hasOneUse()) { 1948202375Srdivacky Value *Or = Builder->CreateOr(X, RHS); 1949202375Srdivacky Or->takeName(Op0); 1950202375Srdivacky return BinaryOperator::CreateXor(Or, 1951263509Sdim Builder->getInt(C1->getValue() & ~RHS->getValue())); 1952202375Srdivacky } 1953202375Srdivacky 1954202375Srdivacky // Try to fold constant and into select arguments. 1955202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1956202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1957202375Srdivacky return R; 1958204642Srdivacky 1959202375Srdivacky if (isa<PHINode>(Op0)) 1960202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 1961202375Srdivacky return NV; 1962202375Srdivacky } 1963202375Srdivacky 1964202375Srdivacky Value *A = 0, *B = 0; 1965202375Srdivacky ConstantInt *C1 = 0, *C2 = 0; 1966202375Srdivacky 1967202375Srdivacky // (A | B) | C and A | (B | C) -> bswap if possible. 1968202375Srdivacky // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible. 1969202375Srdivacky if (match(Op0, m_Or(m_Value(), m_Value())) || 1970202375Srdivacky match(Op1, m_Or(m_Value(), m_Value())) || 1971218893Sdim (match(Op0, m_LogicalShift(m_Value(), m_Value())) && 1972218893Sdim match(Op1, m_LogicalShift(m_Value(), m_Value())))) { 1973202375Srdivacky if (Instruction *BSwap = MatchBSwap(I)) 1974202375Srdivacky return BSwap; 1975202375Srdivacky } 1976252723Sdim 1977202375Srdivacky // (X^C)|Y -> (X|Y)^C iff Y&C == 0 1978202375Srdivacky if (Op0->hasOneUse() && 1979202375Srdivacky match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) && 1980202375Srdivacky MaskedValueIsZero(Op1, C1->getValue())) { 1981202375Srdivacky Value *NOr = Builder->CreateOr(A, Op1); 1982202375Srdivacky NOr->takeName(Op0); 1983202375Srdivacky return BinaryOperator::CreateXor(NOr, C1); 1984202375Srdivacky } 1985202375Srdivacky 1986202375Srdivacky // Y|(X^C) -> (X|Y)^C iff Y&C == 0 1987202375Srdivacky if (Op1->hasOneUse() && 1988202375Srdivacky match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) && 1989202375Srdivacky MaskedValueIsZero(Op0, C1->getValue())) { 1990202375Srdivacky Value *NOr = Builder->CreateOr(A, Op0); 1991202375Srdivacky NOr->takeName(Op0); 1992202375Srdivacky return BinaryOperator::CreateXor(NOr, C1); 1993202375Srdivacky } 1994202375Srdivacky 1995202375Srdivacky // (A & C)|(B & D) 1996202375Srdivacky Value *C = 0, *D = 0; 1997202375Srdivacky if (match(Op0, m_And(m_Value(A), m_Value(C))) && 1998202375Srdivacky match(Op1, m_And(m_Value(B), m_Value(D)))) { 1999218893Sdim Value *V1 = 0, *V2 = 0; 2000202375Srdivacky C1 = dyn_cast<ConstantInt>(C); 2001202375Srdivacky C2 = dyn_cast<ConstantInt>(D); 2002202375Srdivacky if (C1 && C2) { // (A & C1)|(B & C2) 2003202375Srdivacky // If we have: ((V + N) & C1) | (V & C2) 2004202375Srdivacky // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 2005202375Srdivacky // replace with V+N. 2006202375Srdivacky if (C1->getValue() == ~C2->getValue()) { 2007202375Srdivacky if ((C2->getValue() & (C2->getValue()+1)) == 0 && // C2 == 0+1+ 2008202375Srdivacky match(A, m_Add(m_Value(V1), m_Value(V2)))) { 2009202375Srdivacky // Add commutes, try both ways. 2010202375Srdivacky if (V1 == B && MaskedValueIsZero(V2, C2->getValue())) 2011202375Srdivacky return ReplaceInstUsesWith(I, A); 2012202375Srdivacky if (V2 == B && MaskedValueIsZero(V1, C2->getValue())) 2013202375Srdivacky return ReplaceInstUsesWith(I, A); 2014202375Srdivacky } 2015202375Srdivacky // Or commutes, try both ways. 2016202375Srdivacky if ((C1->getValue() & (C1->getValue()+1)) == 0 && 2017202375Srdivacky match(B, m_Add(m_Value(V1), m_Value(V2)))) { 2018202375Srdivacky // Add commutes, try both ways. 2019202375Srdivacky if (V1 == A && MaskedValueIsZero(V2, C1->getValue())) 2020202375Srdivacky return ReplaceInstUsesWith(I, B); 2021202375Srdivacky if (V2 == A && MaskedValueIsZero(V1, C1->getValue())) 2022202375Srdivacky return ReplaceInstUsesWith(I, B); 2023202375Srdivacky } 2024202375Srdivacky } 2025252723Sdim 2026202375Srdivacky if ((C1->getValue() & C2->getValue()) == 0) { 2027202375Srdivacky // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2) 2028202375Srdivacky // iff (C1&C2) == 0 and (N&~C1) == 0 2029202375Srdivacky if (match(A, m_Or(m_Value(V1), m_Value(V2))) && 2030202375Srdivacky ((V1 == B && MaskedValueIsZero(V2, ~C1->getValue())) || // (V|N) 2031202375Srdivacky (V2 == B && MaskedValueIsZero(V1, ~C1->getValue())))) // (N|V) 2032202375Srdivacky return BinaryOperator::CreateAnd(A, 2033263509Sdim Builder->getInt(C1->getValue()|C2->getValue())); 2034202375Srdivacky // Or commutes, try both ways. 2035202375Srdivacky if (match(B, m_Or(m_Value(V1), m_Value(V2))) && 2036202375Srdivacky ((V1 == A && MaskedValueIsZero(V2, ~C2->getValue())) || // (V|N) 2037202375Srdivacky (V2 == A && MaskedValueIsZero(V1, ~C2->getValue())))) // (N|V) 2038202375Srdivacky return BinaryOperator::CreateAnd(B, 2039263509Sdim Builder->getInt(C1->getValue()|C2->getValue())); 2040252723Sdim 2041202375Srdivacky // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2) 2042202375Srdivacky // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0. 2043202375Srdivacky ConstantInt *C3 = 0, *C4 = 0; 2044202375Srdivacky if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) && 2045202375Srdivacky (C3->getValue() & ~C1->getValue()) == 0 && 2046202375Srdivacky match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) && 2047202375Srdivacky (C4->getValue() & ~C2->getValue()) == 0) { 2048202375Srdivacky V2 = Builder->CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield"); 2049202375Srdivacky return BinaryOperator::CreateAnd(V2, 2050263509Sdim Builder->getInt(C1->getValue()|C2->getValue())); 2051202375Srdivacky } 2052202375Srdivacky } 2053202375Srdivacky } 2054202375Srdivacky 2055203954Srdivacky // (A & (C0?-1:0)) | (B & ~(C0?-1:0)) -> C0 ? A : B, and commuted variants. 2056203954Srdivacky // Don't do this for vector select idioms, the code generator doesn't handle 2057203954Srdivacky // them well yet. 2058204642Srdivacky if (!I.getType()->isVectorTy()) { 2059203954Srdivacky if (Instruction *Match = MatchSelectFromAndOr(A, B, C, D)) 2060203954Srdivacky return Match; 2061203954Srdivacky if (Instruction *Match = MatchSelectFromAndOr(B, A, D, C)) 2062203954Srdivacky return Match; 2063203954Srdivacky if (Instruction *Match = MatchSelectFromAndOr(C, B, A, D)) 2064203954Srdivacky return Match; 2065203954Srdivacky if (Instruction *Match = MatchSelectFromAndOr(D, A, B, C)) 2066203954Srdivacky return Match; 2067203954Srdivacky } 2068202375Srdivacky 2069202375Srdivacky // ((A&~B)|(~A&B)) -> A^B 2070202375Srdivacky if ((match(C, m_Not(m_Specific(D))) && 2071202375Srdivacky match(B, m_Not(m_Specific(A))))) 2072202375Srdivacky return BinaryOperator::CreateXor(A, D); 2073202375Srdivacky // ((~B&A)|(~A&B)) -> A^B 2074202375Srdivacky if ((match(A, m_Not(m_Specific(D))) && 2075202375Srdivacky match(B, m_Not(m_Specific(C))))) 2076202375Srdivacky return BinaryOperator::CreateXor(C, D); 2077202375Srdivacky // ((A&~B)|(B&~A)) -> A^B 2078202375Srdivacky if ((match(C, m_Not(m_Specific(B))) && 2079202375Srdivacky match(D, m_Not(m_Specific(A))))) 2080202375Srdivacky return BinaryOperator::CreateXor(A, B); 2081202375Srdivacky // ((~B&A)|(B&~A)) -> A^B 2082202375Srdivacky if ((match(A, m_Not(m_Specific(B))) && 2083202375Srdivacky match(D, m_Not(m_Specific(C))))) 2084202375Srdivacky return BinaryOperator::CreateXor(C, B); 2085210299Sed 2086210299Sed // ((A|B)&1)|(B&-2) -> (A&1) | B 2087210299Sed if (match(A, m_Or(m_Value(V1), m_Specific(B))) || 2088210299Sed match(A, m_Or(m_Specific(B), m_Value(V1)))) { 2089210299Sed Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C); 2090210299Sed if (Ret) return Ret; 2091210299Sed } 2092210299Sed // (B&-2)|((A|B)&1) -> (A&1) | B 2093210299Sed if (match(B, m_Or(m_Specific(A), m_Value(V1))) || 2094210299Sed match(B, m_Or(m_Value(V1), m_Specific(A)))) { 2095210299Sed Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D); 2096210299Sed if (Ret) return Ret; 2097210299Sed } 2098202375Srdivacky } 2099252723Sdim 2100202375Srdivacky // (X >> Z) | (Y >> Z) -> (X|Y) >> Z for all shifts. 2101202375Srdivacky if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) { 2102202375Srdivacky if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0)) 2103252723Sdim if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() && 2104202375Srdivacky SI0->getOperand(1) == SI1->getOperand(1) && 2105202375Srdivacky (SI0->hasOneUse() || SI1->hasOneUse())) { 2106202375Srdivacky Value *NewOp = Builder->CreateOr(SI0->getOperand(0), SI1->getOperand(0), 2107202375Srdivacky SI0->getName()); 2108252723Sdim return BinaryOperator::Create(SI1->getOpcode(), NewOp, 2109202375Srdivacky SI1->getOperand(1)); 2110202375Srdivacky } 2111202375Srdivacky } 2112202375Srdivacky 2113202375Srdivacky // (~A | ~B) == (~(A & B)) - De Morgan's Law 2114202375Srdivacky if (Value *Op0NotVal = dyn_castNotVal(Op0)) 2115202375Srdivacky if (Value *Op1NotVal = dyn_castNotVal(Op1)) 2116202375Srdivacky if (Op0->hasOneUse() && Op1->hasOneUse()) { 2117202375Srdivacky Value *And = Builder->CreateAnd(Op0NotVal, Op1NotVal, 2118202375Srdivacky I.getName()+".demorgan"); 2119202375Srdivacky return BinaryOperator::CreateNot(And); 2120202375Srdivacky } 2121202375Srdivacky 2122219077Sdim // Canonicalize xor to the RHS. 2123235633Sdim bool SwappedForXor = false; 2124235633Sdim if (match(Op0, m_Xor(m_Value(), m_Value()))) { 2125219077Sdim std::swap(Op0, Op1); 2126235633Sdim SwappedForXor = true; 2127235633Sdim } 2128219077Sdim 2129219077Sdim // A | ( A ^ B) -> A | B 2130219077Sdim // A | (~A ^ B) -> A | ~B 2131245431Sdim // (A & B) | (A ^ B) 2132219077Sdim if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) { 2133219077Sdim if (Op0 == A || Op0 == B) 2134219077Sdim return BinaryOperator::CreateOr(A, B); 2135219077Sdim 2136245431Sdim if (match(Op0, m_And(m_Specific(A), m_Specific(B))) || 2137245431Sdim match(Op0, m_And(m_Specific(B), m_Specific(A)))) 2138245431Sdim return BinaryOperator::CreateOr(A, B); 2139245431Sdim 2140219077Sdim if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) { 2141219077Sdim Value *Not = Builder->CreateNot(B, B->getName()+".not"); 2142219077Sdim return BinaryOperator::CreateOr(Not, Op0); 2143219077Sdim } 2144219077Sdim if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) { 2145219077Sdim Value *Not = Builder->CreateNot(A, A->getName()+".not"); 2146219077Sdim return BinaryOperator::CreateOr(Not, Op0); 2147219077Sdim } 2148219077Sdim } 2149219077Sdim 2150219077Sdim // A | ~(A | B) -> A | ~B 2151219077Sdim // A | ~(A ^ B) -> A | ~B 2152219077Sdim if (match(Op1, m_Not(m_Value(A)))) 2153219077Sdim if (BinaryOperator *B = dyn_cast<BinaryOperator>(A)) 2154219077Sdim if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) && 2155219077Sdim Op1->hasOneUse() && (B->getOpcode() == Instruction::Or || 2156219077Sdim B->getOpcode() == Instruction::Xor)) { 2157219077Sdim Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) : 2158219077Sdim B->getOperand(0); 2159219077Sdim Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not"); 2160219077Sdim return BinaryOperator::CreateOr(Not, Op0); 2161219077Sdim } 2162219077Sdim 2163235633Sdim if (SwappedForXor) 2164235633Sdim std::swap(Op0, Op1); 2165235633Sdim 2166202375Srdivacky if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1))) 2167202375Srdivacky if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0))) 2168204792Srdivacky if (Value *Res = FoldOrOfICmps(LHS, RHS)) 2169204792Srdivacky return ReplaceInstUsesWith(I, Res); 2170252723Sdim 2171203954Srdivacky // (fcmp uno x, c) | (fcmp uno y, c) -> (fcmp uno x, y) 2172203954Srdivacky if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0))) 2173203954Srdivacky if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1))) 2174204792Srdivacky if (Value *Res = FoldOrOfFCmps(LHS, RHS)) 2175204792Srdivacky return ReplaceInstUsesWith(I, Res); 2176252723Sdim 2177202375Srdivacky // fold (or (cast A), (cast B)) -> (cast (or A, B)) 2178202375Srdivacky if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2179218893Sdim CastInst *Op1C = dyn_cast<CastInst>(Op1); 2180218893Sdim if (Op1C && Op0C->getOpcode() == Op1C->getOpcode()) {// same cast kind ? 2181226890Sdim Type *SrcTy = Op0C->getOperand(0)->getType(); 2182218893Sdim if (SrcTy == Op1C->getOperand(0)->getType() && 2183218893Sdim SrcTy->isIntOrIntVectorTy()) { 2184218893Sdim Value *Op0COp = Op0C->getOperand(0), *Op1COp = Op1C->getOperand(0); 2185203954Srdivacky 2186218893Sdim if ((!isa<ICmpInst>(Op0COp) || !isa<ICmpInst>(Op1COp)) && 2187218893Sdim // Only do this if the casts both really cause code to be 2188218893Sdim // generated. 2189218893Sdim ShouldOptimizeCast(Op0C->getOpcode(), Op0COp, I.getType()) && 2190218893Sdim ShouldOptimizeCast(Op1C->getOpcode(), Op1COp, I.getType())) { 2191218893Sdim Value *NewOp = Builder->CreateOr(Op0COp, Op1COp, I.getName()); 2192218893Sdim return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 2193202375Srdivacky } 2194252723Sdim 2195218893Sdim // If this is or(cast(icmp), cast(icmp)), try to fold this even if the 2196218893Sdim // cast is otherwise not optimizable. This happens for vector sexts. 2197218893Sdim if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1COp)) 2198218893Sdim if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0COp)) 2199218893Sdim if (Value *Res = FoldOrOfICmps(LHS, RHS)) 2200218893Sdim return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 2201252723Sdim 2202218893Sdim // If this is or(cast(fcmp), cast(fcmp)), try to fold this even if the 2203218893Sdim // cast is otherwise not optimizable. This happens for vector sexts. 2204218893Sdim if (FCmpInst *RHS = dyn_cast<FCmpInst>(Op1COp)) 2205218893Sdim if (FCmpInst *LHS = dyn_cast<FCmpInst>(Op0COp)) 2206218893Sdim if (Value *Res = FoldOrOfFCmps(LHS, RHS)) 2207218893Sdim return CastInst::Create(Op0C->getOpcode(), Res, I.getType()); 2208202375Srdivacky } 2209218893Sdim } 2210202375Srdivacky } 2211221345Sdim 2212221345Sdim // or(sext(A), B) -> A ? -1 : B where A is an i1 2213221345Sdim // or(A, sext(B)) -> B ? -1 : A where B is an i1 2214221345Sdim if (match(Op0, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1)) 2215221345Sdim return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1); 2216221345Sdim if (match(Op1, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1)) 2217221345Sdim return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0); 2218221345Sdim 2219218893Sdim // Note: If we've gotten to the point of visiting the outer OR, then the 2220218893Sdim // inner one couldn't be simplified. If it was a constant, then it won't 2221218893Sdim // be simplified by a later pass either, so we try swapping the inner/outer 2222218893Sdim // ORs in the hopes that we'll be able to simplify it this way. 2223218893Sdim // (X|C) | V --> (X|V) | C 2224218893Sdim if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) && 2225218893Sdim match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) { 2226218893Sdim Value *Inner = Builder->CreateOr(A, Op1); 2227218893Sdim Inner->takeName(Op0); 2228218893Sdim return BinaryOperator::CreateOr(Inner, C1); 2229218893Sdim } 2230252723Sdim 2231252723Sdim // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D)) 2232252723Sdim // Since this OR statement hasn't been optimized further yet, we hope 2233252723Sdim // that this transformation will allow the new ORs to be optimized. 2234252723Sdim { 2235252723Sdim Value *X = 0, *Y = 0; 2236252723Sdim if (Op0->hasOneUse() && Op1->hasOneUse() && 2237252723Sdim match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) && 2238252723Sdim match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) { 2239252723Sdim Value *orTrue = Builder->CreateOr(A, C); 2240252723Sdim Value *orFalse = Builder->CreateOr(B, D); 2241252723Sdim return SelectInst::Create(X, orTrue, orFalse); 2242252723Sdim } 2243252723Sdim } 2244252723Sdim 2245202375Srdivacky return Changed ? &I : 0; 2246202375Srdivacky} 2247202375Srdivacky 2248202375SrdivackyInstruction *InstCombiner::visitXor(BinaryOperator &I) { 2249218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 2250202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2251202375Srdivacky 2252218893Sdim if (Value *V = SimplifyXorInst(Op0, Op1, TD)) 2253218893Sdim return ReplaceInstUsesWith(I, V); 2254202375Srdivacky 2255218893Sdim // (A&B)^(A&C) -> A&(B^C) etc 2256218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 2257218893Sdim return ReplaceInstUsesWith(I, V); 2258218893Sdim 2259252723Sdim // See if we can simplify any instructions used by the instruction whose sole 2260202375Srdivacky // purpose is to compute bits we don't care about. 2261202375Srdivacky if (SimplifyDemandedInstructionBits(I)) 2262202375Srdivacky return &I; 2263202375Srdivacky 2264202375Srdivacky // Is this a ~ operation? 2265202375Srdivacky if (Value *NotOp = dyn_castNotVal(&I)) { 2266202375Srdivacky if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) { 2267252723Sdim if (Op0I->getOpcode() == Instruction::And || 2268202375Srdivacky Op0I->getOpcode() == Instruction::Or) { 2269202375Srdivacky // ~(~X & Y) --> (X | ~Y) - De Morgan's Law 2270202375Srdivacky // ~(~X | Y) === (X & ~Y) - De Morgan's Law 2271202375Srdivacky if (dyn_castNotVal(Op0I->getOperand(1))) 2272202375Srdivacky Op0I->swapOperands(); 2273202375Srdivacky if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) { 2274202375Srdivacky Value *NotY = 2275202375Srdivacky Builder->CreateNot(Op0I->getOperand(1), 2276202375Srdivacky Op0I->getOperand(1)->getName()+".not"); 2277202375Srdivacky if (Op0I->getOpcode() == Instruction::And) 2278202375Srdivacky return BinaryOperator::CreateOr(Op0NotVal, NotY); 2279202375Srdivacky return BinaryOperator::CreateAnd(Op0NotVal, NotY); 2280202375Srdivacky } 2281252723Sdim 2282202375Srdivacky // ~(X & Y) --> (~X | ~Y) - De Morgan's Law 2283202375Srdivacky // ~(X | Y) === (~X & ~Y) - De Morgan's Law 2284252723Sdim if (isFreeToInvert(Op0I->getOperand(0)) && 2285202375Srdivacky isFreeToInvert(Op0I->getOperand(1))) { 2286202375Srdivacky Value *NotX = 2287202375Srdivacky Builder->CreateNot(Op0I->getOperand(0), "notlhs"); 2288202375Srdivacky Value *NotY = 2289202375Srdivacky Builder->CreateNot(Op0I->getOperand(1), "notrhs"); 2290202375Srdivacky if (Op0I->getOpcode() == Instruction::And) 2291202375Srdivacky return BinaryOperator::CreateOr(NotX, NotY); 2292202375Srdivacky return BinaryOperator::CreateAnd(NotX, NotY); 2293202375Srdivacky } 2294202878Srdivacky 2295202878Srdivacky } else if (Op0I->getOpcode() == Instruction::AShr) { 2296202878Srdivacky // ~(~X >>s Y) --> (X >>s Y) 2297202878Srdivacky if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) 2298202878Srdivacky return BinaryOperator::CreateAShr(Op0NotVal, Op0I->getOperand(1)); 2299202375Srdivacky } 2300202375Srdivacky } 2301202375Srdivacky } 2302252723Sdim 2303252723Sdim 2304202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 2305207618Srdivacky if (RHS->isOne() && Op0->hasOneUse()) 2306202375Srdivacky // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B 2307207618Srdivacky if (CmpInst *CI = dyn_cast<CmpInst>(Op0)) 2308207618Srdivacky return CmpInst::Create(CI->getOpcode(), 2309207618Srdivacky CI->getInversePredicate(), 2310207618Srdivacky CI->getOperand(0), CI->getOperand(1)); 2311202375Srdivacky 2312202375Srdivacky // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp). 2313202375Srdivacky if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2314202375Srdivacky if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) { 2315202375Srdivacky if (CI->hasOneUse() && Op0C->hasOneUse()) { 2316202375Srdivacky Instruction::CastOps Opcode = Op0C->getOpcode(); 2317202375Srdivacky if ((Opcode == Instruction::ZExt || Opcode == Instruction::SExt) && 2318263509Sdim (RHS == ConstantExpr::getCast(Opcode, Builder->getTrue(), 2319202375Srdivacky Op0C->getDestTy()))) { 2320202375Srdivacky CI->setPredicate(CI->getInversePredicate()); 2321202375Srdivacky return CastInst::Create(Opcode, CI, Op0C->getType()); 2322202375Srdivacky } 2323202375Srdivacky } 2324202375Srdivacky } 2325202375Srdivacky } 2326202375Srdivacky 2327202375Srdivacky if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 2328202375Srdivacky // ~(c-X) == X-c-1 == X+(-c-1) 2329202375Srdivacky if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue()) 2330202375Srdivacky if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) { 2331202375Srdivacky Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C); 2332202375Srdivacky Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C, 2333202375Srdivacky ConstantInt::get(I.getType(), 1)); 2334202375Srdivacky return BinaryOperator::CreateAdd(Op0I->getOperand(1), ConstantRHS); 2335202375Srdivacky } 2336252723Sdim 2337202375Srdivacky if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) { 2338202375Srdivacky if (Op0I->getOpcode() == Instruction::Add) { 2339202375Srdivacky // ~(X-c) --> (-c-1)-X 2340202375Srdivacky if (RHS->isAllOnesValue()) { 2341202375Srdivacky Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI); 2342202375Srdivacky return BinaryOperator::CreateSub( 2343202375Srdivacky ConstantExpr::getSub(NegOp0CI, 2344202375Srdivacky ConstantInt::get(I.getType(), 1)), 2345202375Srdivacky Op0I->getOperand(0)); 2346202375Srdivacky } else if (RHS->getValue().isSignBit()) { 2347202375Srdivacky // (X + C) ^ signbit -> (X + C + signbit) 2348263509Sdim Constant *C = Builder->getInt(RHS->getValue() + Op0CI->getValue()); 2349202375Srdivacky return BinaryOperator::CreateAdd(Op0I->getOperand(0), C); 2350202375Srdivacky 2351202375Srdivacky } 2352202375Srdivacky } else if (Op0I->getOpcode() == Instruction::Or) { 2353202375Srdivacky // (X|C1)^C2 -> X^(C1|C2) iff X&~C1 == 0 2354202375Srdivacky if (MaskedValueIsZero(Op0I->getOperand(0), Op0CI->getValue())) { 2355202375Srdivacky Constant *NewRHS = ConstantExpr::getOr(Op0CI, RHS); 2356202375Srdivacky // Anything in both C1 and C2 is known to be zero, remove it from 2357202375Srdivacky // NewRHS. 2358202375Srdivacky Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHS); 2359252723Sdim NewRHS = ConstantExpr::getAnd(NewRHS, 2360202375Srdivacky ConstantExpr::getNot(CommonBits)); 2361202375Srdivacky Worklist.Add(Op0I); 2362202375Srdivacky I.setOperand(0, Op0I->getOperand(0)); 2363202375Srdivacky I.setOperand(1, NewRHS); 2364202375Srdivacky return &I; 2365202375Srdivacky } 2366252723Sdim } else if (Op0I->getOpcode() == Instruction::LShr) { 2367252723Sdim // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3) 2368252723Sdim // E1 = "X ^ C1" 2369252723Sdim BinaryOperator *E1; 2370252723Sdim ConstantInt *C1; 2371252723Sdim if (Op0I->hasOneUse() && 2372252723Sdim (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) && 2373252723Sdim E1->getOpcode() == Instruction::Xor && 2374252723Sdim (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) { 2375252723Sdim // fold (C1 >> C2) ^ C3 2376252723Sdim ConstantInt *C2 = Op0CI, *C3 = RHS; 2377252723Sdim APInt FoldConst = C1->getValue().lshr(C2->getValue()); 2378252723Sdim FoldConst ^= C3->getValue(); 2379252723Sdim // Prepare the two operands. 2380252723Sdim Value *Opnd0 = Builder->CreateLShr(E1->getOperand(0), C2); 2381252723Sdim Opnd0->takeName(Op0I); 2382252723Sdim cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc()); 2383252723Sdim Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst); 2384252723Sdim 2385252723Sdim return BinaryOperator::CreateXor(Opnd0, FoldVal); 2386252723Sdim } 2387202375Srdivacky } 2388202375Srdivacky } 2389202375Srdivacky } 2390202375Srdivacky 2391202375Srdivacky // Try to fold constant and into select arguments. 2392202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 2393202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 2394202375Srdivacky return R; 2395202375Srdivacky if (isa<PHINode>(Op0)) 2396202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 2397202375Srdivacky return NV; 2398202375Srdivacky } 2399202375Srdivacky 2400202375Srdivacky BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1); 2401202375Srdivacky if (Op1I) { 2402202375Srdivacky Value *A, *B; 2403202375Srdivacky if (match(Op1I, m_Or(m_Value(A), m_Value(B)))) { 2404202375Srdivacky if (A == Op0) { // B^(B|A) == (A|B)^B 2405202375Srdivacky Op1I->swapOperands(); 2406202375Srdivacky I.swapOperands(); 2407202375Srdivacky std::swap(Op0, Op1); 2408202375Srdivacky } else if (B == Op0) { // B^(A|B) == (A|B)^B 2409202375Srdivacky I.swapOperands(); // Simplified below. 2410202375Srdivacky std::swap(Op0, Op1); 2411202375Srdivacky } 2412252723Sdim } else if (match(Op1I, m_And(m_Value(A), m_Value(B))) && 2413202375Srdivacky Op1I->hasOneUse()){ 2414202375Srdivacky if (A == Op0) { // A^(A&B) -> A^(B&A) 2415202375Srdivacky Op1I->swapOperands(); 2416202375Srdivacky std::swap(A, B); 2417202375Srdivacky } 2418202375Srdivacky if (B == Op0) { // A^(B&A) -> (B&A)^A 2419202375Srdivacky I.swapOperands(); // Simplified below. 2420202375Srdivacky std::swap(Op0, Op1); 2421202375Srdivacky } 2422202375Srdivacky } 2423202375Srdivacky } 2424252723Sdim 2425202375Srdivacky BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0); 2426202375Srdivacky if (Op0I) { 2427202375Srdivacky Value *A, *B; 2428202375Srdivacky if (match(Op0I, m_Or(m_Value(A), m_Value(B))) && 2429202375Srdivacky Op0I->hasOneUse()) { 2430202375Srdivacky if (A == Op1) // (B|A)^B == (A|B)^B 2431202375Srdivacky std::swap(A, B); 2432202375Srdivacky if (B == Op1) // (A|B)^B == A & ~B 2433226890Sdim return BinaryOperator::CreateAnd(A, Builder->CreateNot(Op1)); 2434252723Sdim } else if (match(Op0I, m_And(m_Value(A), m_Value(B))) && 2435202375Srdivacky Op0I->hasOneUse()){ 2436202375Srdivacky if (A == Op1) // (A&B)^A -> (B&A)^A 2437202375Srdivacky std::swap(A, B); 2438202375Srdivacky if (B == Op1 && // (B&A)^A == ~B & A 2439202375Srdivacky !isa<ConstantInt>(Op1)) { // Canonical form is (B&C)^C 2440226890Sdim return BinaryOperator::CreateAnd(Builder->CreateNot(A), Op1); 2441202375Srdivacky } 2442202375Srdivacky } 2443202375Srdivacky } 2444252723Sdim 2445202375Srdivacky // (X >> Z) ^ (Y >> Z) -> (X^Y) >> Z for all shifts. 2446252723Sdim if (Op0I && Op1I && Op0I->isShift() && 2447252723Sdim Op0I->getOpcode() == Op1I->getOpcode() && 2448202375Srdivacky Op0I->getOperand(1) == Op1I->getOperand(1) && 2449245431Sdim (Op0I->hasOneUse() || Op1I->hasOneUse())) { 2450202375Srdivacky Value *NewOp = 2451202375Srdivacky Builder->CreateXor(Op0I->getOperand(0), Op1I->getOperand(0), 2452202375Srdivacky Op0I->getName()); 2453252723Sdim return BinaryOperator::Create(Op1I->getOpcode(), NewOp, 2454202375Srdivacky Op1I->getOperand(1)); 2455202375Srdivacky } 2456252723Sdim 2457202375Srdivacky if (Op0I && Op1I) { 2458202375Srdivacky Value *A, *B, *C, *D; 2459202375Srdivacky // (A & B)^(A | B) -> A ^ B 2460202375Srdivacky if (match(Op0I, m_And(m_Value(A), m_Value(B))) && 2461202375Srdivacky match(Op1I, m_Or(m_Value(C), m_Value(D)))) { 2462252723Sdim if ((A == C && B == D) || (A == D && B == C)) 2463202375Srdivacky return BinaryOperator::CreateXor(A, B); 2464202375Srdivacky } 2465202375Srdivacky // (A | B)^(A & B) -> A ^ B 2466202375Srdivacky if (match(Op0I, m_Or(m_Value(A), m_Value(B))) && 2467202375Srdivacky match(Op1I, m_And(m_Value(C), m_Value(D)))) { 2468252723Sdim if ((A == C && B == D) || (A == D && B == C)) 2469202375Srdivacky return BinaryOperator::CreateXor(A, B); 2470202375Srdivacky } 2471202375Srdivacky } 2472218893Sdim 2473202375Srdivacky // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B) 2474202375Srdivacky if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1))) 2475202375Srdivacky if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0))) 2476202375Srdivacky if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) { 2477202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(1) && 2478202375Srdivacky LHS->getOperand(1) == RHS->getOperand(0)) 2479202375Srdivacky LHS->swapOperands(); 2480202375Srdivacky if (LHS->getOperand(0) == RHS->getOperand(0) && 2481202375Srdivacky LHS->getOperand(1) == RHS->getOperand(1)) { 2482202375Srdivacky Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); 2483202375Srdivacky unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS); 2484202375Srdivacky bool isSigned = LHS->isSigned() || RHS->isSigned(); 2485252723Sdim return ReplaceInstUsesWith(I, 2486235633Sdim getNewICmpValue(isSigned, Code, Op0, Op1, 2487235633Sdim Builder)); 2488202375Srdivacky } 2489202375Srdivacky } 2490202375Srdivacky 2491202375Srdivacky // fold (xor (cast A), (cast B)) -> (cast (xor A, B)) 2492202375Srdivacky if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) { 2493202375Srdivacky if (CastInst *Op1C = dyn_cast<CastInst>(Op1)) 2494202375Srdivacky if (Op0C->getOpcode() == Op1C->getOpcode()) { // same cast kind? 2495226890Sdim Type *SrcTy = Op0C->getOperand(0)->getType(); 2496203954Srdivacky if (SrcTy == Op1C->getOperand(0)->getType() && SrcTy->isIntegerTy() && 2497202375Srdivacky // Only do this if the casts both really cause code to be generated. 2498252723Sdim ShouldOptimizeCast(Op0C->getOpcode(), Op0C->getOperand(0), 2499203954Srdivacky I.getType()) && 2500252723Sdim ShouldOptimizeCast(Op1C->getOpcode(), Op1C->getOperand(0), 2501203954Srdivacky I.getType())) { 2502202375Srdivacky Value *NewOp = Builder->CreateXor(Op0C->getOperand(0), 2503202375Srdivacky Op1C->getOperand(0), I.getName()); 2504202375Srdivacky return CastInst::Create(Op0C->getOpcode(), NewOp, I.getType()); 2505202375Srdivacky } 2506202375Srdivacky } 2507202375Srdivacky } 2508202375Srdivacky 2509202375Srdivacky return Changed ? &I : 0; 2510202375Srdivacky} 2511