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