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