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