blob: ecb406fabefb8e3aca0f73270074a61d731398b9 [file] [log] [blame]
Chris Lattner0a8191e2010-01-05 07:50:36 +00001//===- InstCombineAndOrXor.cpp --------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the visitAnd, visitOr, and visitXor functions.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
Chris Lattner0a8191e2010-01-05 07:50:36 +000015#include "llvm/Analysis/InstructionSimplify.h"
Chandler Carruth8cd041e2014-03-04 12:24:34 +000016#include "llvm/IR/ConstantRange.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000017#include "llvm/IR/Intrinsics.h"
Chandler Carruth820a9082014-03-04 11:08:18 +000018#include "llvm/IR/PatternMatch.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000019#include "llvm/Transforms/Utils/CmpInstAnalysis.h"
James Molloyf01488e2016-01-15 09:20:19 +000020#include "llvm/Transforms/Utils/Local.h"
Chris Lattner0a8191e2010-01-05 07:50:36 +000021using namespace llvm;
22using namespace PatternMatch;
23
Chandler Carruth964daaa2014-04-22 02:55:47 +000024#define DEBUG_TYPE "instcombine"
25
Chris Lattner0a8191e2010-01-05 07:50:36 +000026static inline Value *dyn_castNotVal(Value *V) {
27 // If this is not(not(x)) don't return that this is a not: we want the two
28 // not's to be folded first.
29 if (BinaryOperator::isNot(V)) {
30 Value *Operand = BinaryOperator::getNotArgument(V);
Sanjoy Das82ea3d42015-02-24 00:08:41 +000031 if (!IsFreeToInvert(Operand, Operand->hasOneUse()))
Chris Lattner0a8191e2010-01-05 07:50:36 +000032 return Operand;
33 }
Craig Topper9d4171a2012-12-20 07:09:41 +000034
Chris Lattner0a8191e2010-01-05 07:50:36 +000035 // Constants can be considered to be not'ed values...
36 if (ConstantInt *C = dyn_cast<ConstantInt>(V))
37 return ConstantInt::get(C->getType(), ~C->getValue());
Craig Topperf40110f2014-04-25 05:29:35 +000038 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +000039}
40
Sanjay Patel18549272015-09-08 18:24:36 +000041/// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
Tim Shenaec68b22016-06-29 20:10:17 +000042/// a four bit mask.
43static unsigned getFCmpCode(FCmpInst::Predicate CC) {
44 assert(FCmpInst::FCMP_FALSE <= CC && CC <= FCmpInst::FCMP_TRUE &&
45 "Unexpected FCmp predicate!");
46 // Take advantage of the bit pattern of FCmpInst::Predicate here.
47 // U L G E
48 static_assert(FCmpInst::FCMP_FALSE == 0, ""); // 0 0 0 0
49 static_assert(FCmpInst::FCMP_OEQ == 1, ""); // 0 0 0 1
50 static_assert(FCmpInst::FCMP_OGT == 2, ""); // 0 0 1 0
51 static_assert(FCmpInst::FCMP_OGE == 3, ""); // 0 0 1 1
52 static_assert(FCmpInst::FCMP_OLT == 4, ""); // 0 1 0 0
53 static_assert(FCmpInst::FCMP_OLE == 5, ""); // 0 1 0 1
54 static_assert(FCmpInst::FCMP_ONE == 6, ""); // 0 1 1 0
55 static_assert(FCmpInst::FCMP_ORD == 7, ""); // 0 1 1 1
56 static_assert(FCmpInst::FCMP_UNO == 8, ""); // 1 0 0 0
57 static_assert(FCmpInst::FCMP_UEQ == 9, ""); // 1 0 0 1
58 static_assert(FCmpInst::FCMP_UGT == 10, ""); // 1 0 1 0
59 static_assert(FCmpInst::FCMP_UGE == 11, ""); // 1 0 1 1
60 static_assert(FCmpInst::FCMP_ULT == 12, ""); // 1 1 0 0
61 static_assert(FCmpInst::FCMP_ULE == 13, ""); // 1 1 0 1
62 static_assert(FCmpInst::FCMP_UNE == 14, ""); // 1 1 1 0
63 static_assert(FCmpInst::FCMP_TRUE == 15, ""); // 1 1 1 1
64 return CC;
Chris Lattner0a8191e2010-01-05 07:50:36 +000065}
66
Sanjay Patel18549272015-09-08 18:24:36 +000067/// This is the complement of getICmpCode, which turns an opcode and two
68/// operands into either a constant true or false, or a brand new ICmp
69/// instruction. The sign is passed in to determine which kind of predicate to
70/// use in the new icmp instruction.
Benjamin Kramerbaba1aa2012-02-06 11:28:19 +000071static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
72 InstCombiner::BuilderTy *Builder) {
Pete Cooperebf98c12011-12-17 01:20:32 +000073 ICmpInst::Predicate NewPred;
74 if (Value *NewConstant = getICmpValue(Sign, Code, LHS, RHS, NewPred))
75 return NewConstant;
76 return Builder->CreateICmp(NewPred, LHS, RHS);
Chris Lattner0a8191e2010-01-05 07:50:36 +000077}
78
Sanjay Patel18549272015-09-08 18:24:36 +000079/// This is the complement of getFCmpCode, which turns an opcode and two
Tim Shenaec68b22016-06-29 20:10:17 +000080/// operands into either a FCmp instruction, or a true/false constant.
81static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
Chris Lattner067459c2010-03-05 08:46:26 +000082 InstCombiner::BuilderTy *Builder) {
Tim Shenaec68b22016-06-29 20:10:17 +000083 const auto Pred = static_cast<FCmpInst::Predicate>(Code);
84 assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
85 "Unexpected FCmp predicate!");
86 if (Pred == FCmpInst::FCMP_FALSE)
87 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
88 if (Pred == FCmpInst::FCMP_TRUE)
89 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
Chris Lattner067459c2010-03-05 08:46:26 +000090 return Builder->CreateFCmp(Pred, LHS, RHS);
Chris Lattner0a8191e2010-01-05 07:50:36 +000091}
92
Simon Pilgrimbe24ab32014-12-04 09:44:01 +000093/// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) to BSWAP(BITWISE_OP(A, B))
94/// \param I Binary operator to transform.
95/// \return Pointer to node that must replace the original binary operator, or
96/// null pointer if no transformation was made.
97Value *InstCombiner::SimplifyBSwap(BinaryOperator &I) {
98 IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
99
100 // Can't do vectors.
101 if (I.getType()->isVectorTy()) return nullptr;
102
103 // Can only do bitwise ops.
104 unsigned Op = I.getOpcode();
105 if (Op != Instruction::And && Op != Instruction::Or &&
106 Op != Instruction::Xor)
107 return nullptr;
108
109 Value *OldLHS = I.getOperand(0);
110 Value *OldRHS = I.getOperand(1);
111 ConstantInt *ConstLHS = dyn_cast<ConstantInt>(OldLHS);
112 ConstantInt *ConstRHS = dyn_cast<ConstantInt>(OldRHS);
113 IntrinsicInst *IntrLHS = dyn_cast<IntrinsicInst>(OldLHS);
114 IntrinsicInst *IntrRHS = dyn_cast<IntrinsicInst>(OldRHS);
115 bool IsBswapLHS = (IntrLHS && IntrLHS->getIntrinsicID() == Intrinsic::bswap);
116 bool IsBswapRHS = (IntrRHS && IntrRHS->getIntrinsicID() == Intrinsic::bswap);
117
118 if (!IsBswapLHS && !IsBswapRHS)
119 return nullptr;
120
121 if (!IsBswapLHS && !ConstLHS)
122 return nullptr;
123
124 if (!IsBswapRHS && !ConstRHS)
125 return nullptr;
126
127 /// OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
128 /// OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
129 Value *NewLHS = IsBswapLHS ? IntrLHS->getOperand(0) :
130 Builder->getInt(ConstLHS->getValue().byteSwap());
131
132 Value *NewRHS = IsBswapRHS ? IntrRHS->getOperand(0) :
133 Builder->getInt(ConstRHS->getValue().byteSwap());
134
135 Value *BinOp = nullptr;
136 if (Op == Instruction::And)
137 BinOp = Builder->CreateAnd(NewLHS, NewRHS);
138 else if (Op == Instruction::Or)
139 BinOp = Builder->CreateOr(NewLHS, NewRHS);
140 else //if (Op == Instruction::Xor)
141 BinOp = Builder->CreateXor(NewLHS, NewRHS);
142
Sanjay Patelaf674fb2015-12-14 17:24:23 +0000143 Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap, ITy);
Simon Pilgrimbe24ab32014-12-04 09:44:01 +0000144 return Builder->CreateCall(F, BinOp);
145}
146
Sanjay Patel18549272015-09-08 18:24:36 +0000147/// This handles expressions of the form ((val OP C1) & C2). Where
148/// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
149/// guaranteed to be a binary operator.
Chris Lattner0a8191e2010-01-05 07:50:36 +0000150Instruction *InstCombiner::OptAndOp(Instruction *Op,
151 ConstantInt *OpRHS,
152 ConstantInt *AndRHS,
153 BinaryOperator &TheAnd) {
154 Value *X = Op->getOperand(0);
Craig Topperf40110f2014-04-25 05:29:35 +0000155 Constant *Together = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000156 if (!Op->isShift())
157 Together = ConstantExpr::getAnd(AndRHS, OpRHS);
158
159 switch (Op->getOpcode()) {
160 case Instruction::Xor:
161 if (Op->hasOneUse()) {
162 // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
163 Value *And = Builder->CreateAnd(X, AndRHS);
164 And->takeName(Op);
165 return BinaryOperator::CreateXor(And, Together);
166 }
167 break;
168 case Instruction::Or:
Owen Andersonc237a842010-09-13 17:59:27 +0000169 if (Op->hasOneUse()){
170 if (Together != OpRHS) {
171 // (X | C1) & C2 --> (X | (C1&C2)) & C2
172 Value *Or = Builder->CreateOr(X, Together);
173 Or->takeName(Op);
174 return BinaryOperator::CreateAnd(Or, AndRHS);
175 }
Craig Topper9d4171a2012-12-20 07:09:41 +0000176
Owen Andersonc237a842010-09-13 17:59:27 +0000177 ConstantInt *TogetherCI = dyn_cast<ConstantInt>(Together);
178 if (TogetherCI && !TogetherCI->isZero()){
179 // (X | C1) & C2 --> (X & (C2^(C1&C2))) | C1
180 // NOTE: This reduces the number of bits set in the & mask, which
181 // can expose opportunities for store narrowing.
182 Together = ConstantExpr::getXor(AndRHS, Together);
183 Value *And = Builder->CreateAnd(X, Together);
184 And->takeName(Op);
185 return BinaryOperator::CreateOr(And, OpRHS);
186 }
Chris Lattner0a8191e2010-01-05 07:50:36 +0000187 }
Craig Topper9d4171a2012-12-20 07:09:41 +0000188
Chris Lattner0a8191e2010-01-05 07:50:36 +0000189 break;
190 case Instruction::Add:
191 if (Op->hasOneUse()) {
192 // Adding a one to a single bit bit-field should be turned into an XOR
193 // of the bit. First thing to check is to see if this AND is with a
194 // single bit constant.
Jakub Staszak9de494e2013-06-06 00:49:57 +0000195 const APInt &AndRHSV = AndRHS->getValue();
Chris Lattner0a8191e2010-01-05 07:50:36 +0000196
197 // If there is only one bit set.
198 if (AndRHSV.isPowerOf2()) {
199 // Ok, at this point, we know that we are masking the result of the
200 // ADD down to exactly one bit. If the constant we are adding has
201 // no bits set below this bit, then we can eliminate the ADD.
Jakub Staszak9de494e2013-06-06 00:49:57 +0000202 const APInt& AddRHS = OpRHS->getValue();
Chris Lattner0a8191e2010-01-05 07:50:36 +0000203
204 // Check to see if any bits below the one bit set in AndRHSV are set.
205 if ((AddRHS & (AndRHSV-1)) == 0) {
206 // If not, the only thing that can effect the output of the AND is
207 // the bit specified by AndRHSV. If that bit is set, the effect of
208 // the XOR is to toggle the bit. If it is clear, then the ADD has
209 // no effect.
210 if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
211 TheAnd.setOperand(0, X);
212 return &TheAnd;
213 } else {
214 // Pull the XOR out of the AND.
215 Value *NewAnd = Builder->CreateAnd(X, AndRHS);
216 NewAnd->takeName(Op);
217 return BinaryOperator::CreateXor(NewAnd, AndRHS);
218 }
219 }
220 }
221 }
222 break;
223
224 case Instruction::Shl: {
225 // We know that the AND will not produce any of the bits shifted in, so if
226 // the anded constant includes them, clear them now!
227 //
228 uint32_t BitWidth = AndRHS->getType()->getBitWidth();
229 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
230 APInt ShlMask(APInt::getHighBitsSet(BitWidth, BitWidth-OpRHSVal));
Jakub Staszak461d1fe2013-06-06 00:37:23 +0000231 ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShlMask);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000232
Chris Lattner9f0ac0d2011-02-15 01:56:08 +0000233 if (CI->getValue() == ShlMask)
234 // Masking out bits that the shift already masks.
Sanjay Patel4b198802016-02-01 22:23:39 +0000235 return replaceInstUsesWith(TheAnd, Op); // No need for the and.
Craig Topper9d4171a2012-12-20 07:09:41 +0000236
Chris Lattner9f0ac0d2011-02-15 01:56:08 +0000237 if (CI != AndRHS) { // Reducing bits set in and.
Chris Lattner0a8191e2010-01-05 07:50:36 +0000238 TheAnd.setOperand(1, CI);
239 return &TheAnd;
240 }
241 break;
242 }
243 case Instruction::LShr: {
244 // We know that the AND will not produce any of the bits shifted in, so if
245 // the anded constant includes them, clear them now! This only applies to
246 // unsigned shifts, because a signed shr may bring in set bits!
247 //
248 uint32_t BitWidth = AndRHS->getType()->getBitWidth();
249 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
250 APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
Jakub Staszak461d1fe2013-06-06 00:37:23 +0000251 ConstantInt *CI = Builder->getInt(AndRHS->getValue() & ShrMask);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000252
Chris Lattner9f0ac0d2011-02-15 01:56:08 +0000253 if (CI->getValue() == ShrMask)
254 // Masking out bits that the shift already masks.
Sanjay Patel4b198802016-02-01 22:23:39 +0000255 return replaceInstUsesWith(TheAnd, Op);
Craig Topper9d4171a2012-12-20 07:09:41 +0000256
Chris Lattner9f0ac0d2011-02-15 01:56:08 +0000257 if (CI != AndRHS) {
Chris Lattner0a8191e2010-01-05 07:50:36 +0000258 TheAnd.setOperand(1, CI); // Reduce bits set in and cst.
259 return &TheAnd;
260 }
261 break;
262 }
263 case Instruction::AShr:
264 // Signed shr.
265 // See if this is shifting in some sign extension, then masking it out
266 // with an and.
267 if (Op->hasOneUse()) {
268 uint32_t BitWidth = AndRHS->getType()->getBitWidth();
269 uint32_t OpRHSVal = OpRHS->getLimitedValue(BitWidth);
270 APInt ShrMask(APInt::getLowBitsSet(BitWidth, BitWidth - OpRHSVal));
Jakub Staszak461d1fe2013-06-06 00:37:23 +0000271 Constant *C = Builder->getInt(AndRHS->getValue() & ShrMask);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000272 if (C == AndRHS) { // Masking out bits shifted in.
273 // (Val ashr C1) & C2 -> (Val lshr C1) & C2
274 // Make the argument unsigned.
275 Value *ShVal = Op->getOperand(0);
276 ShVal = Builder->CreateLShr(ShVal, OpRHS, Op->getName());
277 return BinaryOperator::CreateAnd(ShVal, AndRHS, TheAnd.getName());
278 }
279 }
280 break;
281 }
Craig Topperf40110f2014-04-25 05:29:35 +0000282 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000283}
284
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000285/// Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000286/// (V < Lo || V >= Hi). This method expects that Lo <= Hi. IsSigned indicates
287/// whether to treat V, Lo, and Hi as signed or not.
Sanjay Patel85d79742016-08-31 19:49:56 +0000288Value *InstCombiner::insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
Chris Lattner067459c2010-03-05 08:46:26 +0000289 bool isSigned, bool Inside) {
Sanjay Patel85d79742016-08-31 19:49:56 +0000290 assert((isSigned ? Lo.sle(Hi) : Lo.ule(Hi)) &&
Chris Lattner0a8191e2010-01-05 07:50:36 +0000291 "Lo is not <= Hi in range emission code!");
Craig Topper9d4171a2012-12-20 07:09:41 +0000292
Sanjay Patel85d79742016-08-31 19:49:56 +0000293 Type *Ty = V->getType();
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000294 if (Lo == Hi)
Sanjay Patel85d79742016-08-31 19:49:56 +0000295 return Inside ? ConstantInt::getFalse(Ty) : ConstantInt::getTrue(Ty);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000296
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000297 // V >= Min && V < Hi --> V < Hi
298 // V < Min || V >= Hi --> V >= Hi
299 ICmpInst::Predicate Pred = Inside ? ICmpInst::ICMP_ULT : ICmpInst::ICMP_UGE;
Sanjay Patel85d79742016-08-31 19:49:56 +0000300 if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000301 Pred = isSigned ? ICmpInst::getSignedPredicate(Pred) : Pred;
Sanjay Patel85d79742016-08-31 19:49:56 +0000302 return Builder->CreateICmp(Pred, V, ConstantInt::get(Ty, Hi));
Chris Lattner0a8191e2010-01-05 07:50:36 +0000303 }
304
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000305 // V >= Lo && V < Hi --> V - Lo u< Hi - Lo
306 // V < Lo || V >= Hi --> V - Lo u>= Hi - Lo
Sanjay Patel85d79742016-08-31 19:49:56 +0000307 Value *VMinusLo =
308 Builder->CreateSub(V, ConstantInt::get(Ty, Lo), V->getName() + ".off");
309 Constant *HiMinusLo = ConstantInt::get(Ty, Hi - Lo);
Sanjay Patel7d9ebaf2016-08-31 00:19:35 +0000310 return Builder->CreateICmp(Pred, VMinusLo, HiMinusLo);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000311}
312
Sanjay Patel18549272015-09-08 18:24:36 +0000313/// Returns true iff Val consists of one contiguous run of 1s with any number
314/// of 0s on either side. The 1s are allowed to wrap from LSB to MSB,
315/// so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
316/// not, since all 1s are not contiguous.
Chris Lattner0a8191e2010-01-05 07:50:36 +0000317static bool isRunOfOnes(ConstantInt *Val, uint32_t &MB, uint32_t &ME) {
318 const APInt& V = Val->getValue();
319 uint32_t BitWidth = Val->getType()->getBitWidth();
320 if (!APIntOps::isShiftedMask(BitWidth, V)) return false;
321
322 // look for the first zero bit after the run of ones
323 MB = BitWidth - ((V - 1) ^ V).countLeadingZeros();
324 // look for the first non-zero bit
Craig Topper9d4171a2012-12-20 07:09:41 +0000325 ME = V.getActiveBits();
Chris Lattner0a8191e2010-01-05 07:50:36 +0000326 return true;
327}
328
Sanjay Patel18549272015-09-08 18:24:36 +0000329/// This is part of an expression (LHS +/- RHS) & Mask, where isSub determines
330/// whether the operator is a sub. If we can fold one of the following xforms:
Craig Topper9d4171a2012-12-20 07:09:41 +0000331///
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000332/// ((A & N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == Mask
333/// ((A | N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0
334/// ((A ^ N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +0000335///
336/// return (A +/- B).
337///
338Value *InstCombiner::FoldLogicalPlusAnd(Value *LHS, Value *RHS,
339 ConstantInt *Mask, bool isSub,
340 Instruction &I) {
341 Instruction *LHSI = dyn_cast<Instruction>(LHS);
342 if (!LHSI || LHSI->getNumOperands() != 2 ||
Craig Topperf40110f2014-04-25 05:29:35 +0000343 !isa<ConstantInt>(LHSI->getOperand(1))) return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000344
345 ConstantInt *N = cast<ConstantInt>(LHSI->getOperand(1));
346
347 switch (LHSI->getOpcode()) {
Craig Topperf40110f2014-04-25 05:29:35 +0000348 default: return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000349 case Instruction::And:
350 if (ConstantExpr::getAnd(N, Mask) == Mask) {
351 // If the AndRHS is a power of two minus one (0+1+), this is simple.
Craig Topper9d4171a2012-12-20 07:09:41 +0000352 if ((Mask->getValue().countLeadingZeros() +
353 Mask->getValue().countPopulation()) ==
Chris Lattner0a8191e2010-01-05 07:50:36 +0000354 Mask->getValue().getBitWidth())
355 break;
356
357 // Otherwise, if Mask is 0+1+0+, and if B is known to have the low 0+
358 // part, we don't need any explicit masks to take them out of A. If that
359 // is all N is, ignore it.
360 uint32_t MB = 0, ME = 0;
361 if (isRunOfOnes(Mask, MB, ME)) { // begin/end bit of run, inclusive
362 uint32_t BitWidth = cast<IntegerType>(RHS->getType())->getBitWidth();
363 APInt Mask(APInt::getLowBitsSet(BitWidth, MB-1));
Hal Finkel60db0582014-09-07 18:57:58 +0000364 if (MaskedValueIsZero(RHS, Mask, 0, &I))
Chris Lattner0a8191e2010-01-05 07:50:36 +0000365 break;
366 }
367 }
Craig Topperf40110f2014-04-25 05:29:35 +0000368 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000369 case Instruction::Or:
370 case Instruction::Xor:
371 // If the AndRHS is a power of two minus one (0+1+), and N&Mask == 0
Craig Topper9d4171a2012-12-20 07:09:41 +0000372 if ((Mask->getValue().countLeadingZeros() +
Chris Lattner0a8191e2010-01-05 07:50:36 +0000373 Mask->getValue().countPopulation()) == Mask->getValue().getBitWidth()
374 && ConstantExpr::getAnd(N, Mask)->isNullValue())
375 break;
Craig Topperf40110f2014-04-25 05:29:35 +0000376 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000377 }
Craig Topper9d4171a2012-12-20 07:09:41 +0000378
Chris Lattner0a8191e2010-01-05 07:50:36 +0000379 if (isSub)
380 return Builder->CreateSub(LHSI->getOperand(0), RHS, "fold");
381 return Builder->CreateAdd(LHSI->getOperand(0), RHS, "fold");
382}
383
Owen Anderson3fe002d2010-09-08 22:16:17 +0000384/// enum for classifying (icmp eq (A & B), C) and (icmp ne (A & B), C)
Craig Topper9d4171a2012-12-20 07:09:41 +0000385/// One of A and B is considered the mask, the other the value. This is
386/// described as the "AMask" or "BMask" part of the enum. If the enum
Owen Anderson3fe002d2010-09-08 22:16:17 +0000387/// contains only "Mask", then both A and B can be considered masks.
388/// If A is the mask, then it was proven, that (A & C) == C. This
389/// is trivial if C == A, or C == 0. If both A and C are constants, this
390/// proof is also easy.
391/// For the following explanations we assume that A is the mask.
Craig Topper9d4171a2012-12-20 07:09:41 +0000392/// The part "AllOnes" declares, that the comparison is true only
Owen Anderson3fe002d2010-09-08 22:16:17 +0000393/// if (A & B) == A, or all bits of A are set in B.
394/// Example: (icmp eq (A & 3), 3) -> FoldMskICmp_AMask_AllOnes
Craig Topper9d4171a2012-12-20 07:09:41 +0000395/// The part "AllZeroes" declares, that the comparison is true only
Owen Anderson3fe002d2010-09-08 22:16:17 +0000396/// if (A & B) == 0, or all bits of A are cleared in B.
397/// Example: (icmp eq (A & 3), 0) -> FoldMskICmp_Mask_AllZeroes
Craig Topper9d4171a2012-12-20 07:09:41 +0000398/// The part "Mixed" declares, that (A & B) == C and C might or might not
Owen Anderson3fe002d2010-09-08 22:16:17 +0000399/// contain any number of one bits and zero bits.
400/// Example: (icmp eq (A & 3), 1) -> FoldMskICmp_AMask_Mixed
401/// The Part "Not" means, that in above descriptions "==" should be replaced
402/// by "!=".
403/// Example: (icmp ne (A & 3), 3) -> FoldMskICmp_AMask_NotAllOnes
404/// If the mask A contains a single bit, then the following is equivalent:
405/// (icmp eq (A & B), A) equals (icmp ne (A & B), 0)
406/// (icmp ne (A & B), A) equals (icmp eq (A & B), 0)
407enum MaskedICmpType {
408 FoldMskICmp_AMask_AllOnes = 1,
409 FoldMskICmp_AMask_NotAllOnes = 2,
410 FoldMskICmp_BMask_AllOnes = 4,
411 FoldMskICmp_BMask_NotAllOnes = 8,
412 FoldMskICmp_Mask_AllZeroes = 16,
413 FoldMskICmp_Mask_NotAllZeroes = 32,
414 FoldMskICmp_AMask_Mixed = 64,
415 FoldMskICmp_AMask_NotMixed = 128,
416 FoldMskICmp_BMask_Mixed = 256,
417 FoldMskICmp_BMask_NotMixed = 512
418};
419
Sanjay Patel18549272015-09-08 18:24:36 +0000420/// Return the set of pattern classes (from MaskedICmpType)
421/// that (icmp SCC (A & B), C) satisfies.
Craig Topper9d4171a2012-12-20 07:09:41 +0000422static unsigned getTypeOfMaskedICmp(Value* A, Value* B, Value* C,
Owen Anderson3fe002d2010-09-08 22:16:17 +0000423 ICmpInst::Predicate SCC)
424{
425 ConstantInt *ACst = dyn_cast<ConstantInt>(A);
426 ConstantInt *BCst = dyn_cast<ConstantInt>(B);
427 ConstantInt *CCst = dyn_cast<ConstantInt>(C);
428 bool icmp_eq = (SCC == ICmpInst::ICMP_EQ);
Craig Topperf40110f2014-04-25 05:29:35 +0000429 bool icmp_abit = (ACst && !ACst->isZero() &&
Owen Anderson3fe002d2010-09-08 22:16:17 +0000430 ACst->getValue().isPowerOf2());
Craig Topperf40110f2014-04-25 05:29:35 +0000431 bool icmp_bbit = (BCst && !BCst->isZero() &&
Owen Anderson3fe002d2010-09-08 22:16:17 +0000432 BCst->getValue().isPowerOf2());
433 unsigned result = 0;
Craig Topperf40110f2014-04-25 05:29:35 +0000434 if (CCst && CCst->isZero()) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000435 // if C is zero, then both A and B qualify as mask
436 result |= (icmp_eq ? (FoldMskICmp_Mask_AllZeroes |
Owen Anderson3fe002d2010-09-08 22:16:17 +0000437 FoldMskICmp_AMask_Mixed |
438 FoldMskICmp_BMask_Mixed)
439 : (FoldMskICmp_Mask_NotAllZeroes |
Owen Anderson3fe002d2010-09-08 22:16:17 +0000440 FoldMskICmp_AMask_NotMixed |
441 FoldMskICmp_BMask_NotMixed));
442 if (icmp_abit)
443 result |= (icmp_eq ? (FoldMskICmp_AMask_NotAllOnes |
Craig Topper9d4171a2012-12-20 07:09:41 +0000444 FoldMskICmp_AMask_NotMixed)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000445 : (FoldMskICmp_AMask_AllOnes |
446 FoldMskICmp_AMask_Mixed));
447 if (icmp_bbit)
448 result |= (icmp_eq ? (FoldMskICmp_BMask_NotAllOnes |
Craig Topper9d4171a2012-12-20 07:09:41 +0000449 FoldMskICmp_BMask_NotMixed)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000450 : (FoldMskICmp_BMask_AllOnes |
451 FoldMskICmp_BMask_Mixed));
452 return result;
453 }
454 if (A == C) {
455 result |= (icmp_eq ? (FoldMskICmp_AMask_AllOnes |
456 FoldMskICmp_AMask_Mixed)
457 : (FoldMskICmp_AMask_NotAllOnes |
458 FoldMskICmp_AMask_NotMixed));
459 if (icmp_abit)
460 result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes |
461 FoldMskICmp_AMask_NotMixed)
462 : (FoldMskICmp_Mask_AllZeroes |
463 FoldMskICmp_AMask_Mixed));
Craig Topperf40110f2014-04-25 05:29:35 +0000464 } else if (ACst && CCst &&
Craig Topperae48cb22012-12-20 07:15:54 +0000465 ConstantExpr::getAnd(ACst, CCst) == CCst) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000466 result |= (icmp_eq ? FoldMskICmp_AMask_Mixed
467 : FoldMskICmp_AMask_NotMixed);
468 }
Craig Topperae48cb22012-12-20 07:15:54 +0000469 if (B == C) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000470 result |= (icmp_eq ? (FoldMskICmp_BMask_AllOnes |
471 FoldMskICmp_BMask_Mixed)
472 : (FoldMskICmp_BMask_NotAllOnes |
473 FoldMskICmp_BMask_NotMixed));
474 if (icmp_bbit)
475 result |= (icmp_eq ? (FoldMskICmp_Mask_NotAllZeroes |
Craig Topper9d4171a2012-12-20 07:09:41 +0000476 FoldMskICmp_BMask_NotMixed)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000477 : (FoldMskICmp_Mask_AllZeroes |
478 FoldMskICmp_BMask_Mixed));
Craig Topperf40110f2014-04-25 05:29:35 +0000479 } else if (BCst && CCst &&
Craig Topperae48cb22012-12-20 07:15:54 +0000480 ConstantExpr::getAnd(BCst, CCst) == CCst) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000481 result |= (icmp_eq ? FoldMskICmp_BMask_Mixed
482 : FoldMskICmp_BMask_NotMixed);
483 }
484 return result;
485}
486
Tim Northoverc0756c42013-09-04 11:57:13 +0000487/// Convert an analysis of a masked ICmp into its equivalent if all boolean
488/// operations had the opposite sense. Since each "NotXXX" flag (recording !=)
489/// is adjacent to the corresponding normal flag (recording ==), this just
490/// involves swapping those bits over.
491static unsigned conjugateICmpMask(unsigned Mask) {
492 unsigned NewMask;
493 NewMask = (Mask & (FoldMskICmp_AMask_AllOnes | FoldMskICmp_BMask_AllOnes |
494 FoldMskICmp_Mask_AllZeroes | FoldMskICmp_AMask_Mixed |
495 FoldMskICmp_BMask_Mixed))
496 << 1;
497
498 NewMask |=
499 (Mask & (FoldMskICmp_AMask_NotAllOnes | FoldMskICmp_BMask_NotAllOnes |
500 FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_AMask_NotMixed |
501 FoldMskICmp_BMask_NotMixed))
502 >> 1;
503
504 return NewMask;
505}
506
Sanjay Patel18549272015-09-08 18:24:36 +0000507/// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
508/// Return the set of pattern classes (from MaskedICmpType)
509/// that both LHS and RHS satisfy.
Craig Topper9d4171a2012-12-20 07:09:41 +0000510static unsigned foldLogOpOfMaskedICmpsHelper(Value*& A,
Owen Anderson3fe002d2010-09-08 22:16:17 +0000511 Value*& B, Value*& C,
512 Value*& D, Value*& E,
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000513 ICmpInst *LHS, ICmpInst *RHS,
514 ICmpInst::Predicate &LHSCC,
515 ICmpInst::Predicate &RHSCC) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000516 if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType()) return 0;
517 // vectors are not (yet?) supported
518 if (LHS->getOperand(0)->getType()->isVectorTy()) return 0;
519
520 // Here comes the tricky part:
Craig Topper9d4171a2012-12-20 07:09:41 +0000521 // LHS might be of the form L11 & L12 == X, X == L21 & L22,
Owen Anderson3fe002d2010-09-08 22:16:17 +0000522 // and L11 & L12 == L21 & L22. The same goes for RHS.
523 // Now we must find those components L** and R**, that are equal, so
Craig Topper9d4171a2012-12-20 07:09:41 +0000524 // that we can extract the parameters A, B, C, D, and E for the canonical
Owen Anderson3fe002d2010-09-08 22:16:17 +0000525 // above.
526 Value *L1 = LHS->getOperand(0);
527 Value *L2 = LHS->getOperand(1);
528 Value *L11,*L12,*L21,*L22;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000529 // Check whether the icmp can be decomposed into a bit test.
530 if (decomposeBitTestICmp(LHS, LHSCC, L11, L12, L2)) {
Craig Topperf40110f2014-04-25 05:29:35 +0000531 L21 = L22 = L1 = nullptr;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000532 } else {
533 // Look for ANDs in the LHS icmp.
Tim Northoverdc647a22013-09-04 11:57:17 +0000534 if (!L1->getType()->isIntegerTy()) {
535 // You can icmp pointers, for example. They really aren't masks.
Craig Topperf40110f2014-04-25 05:29:35 +0000536 L11 = L12 = nullptr;
Tim Northoverdc647a22013-09-04 11:57:17 +0000537 } else if (!match(L1, m_And(m_Value(L11), m_Value(L12)))) {
538 // Any icmp can be viewed as being trivially masked; if it allows us to
539 // remove one, it's worth it.
540 L11 = L1;
541 L12 = Constant::getAllOnesValue(L1->getType());
542 }
543
544 if (!L2->getType()->isIntegerTy()) {
545 // You can icmp pointers, for example. They really aren't masks.
Craig Topperf40110f2014-04-25 05:29:35 +0000546 L21 = L22 = nullptr;
Tim Northoverdc647a22013-09-04 11:57:17 +0000547 } else if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
548 L21 = L2;
549 L22 = Constant::getAllOnesValue(L2->getType());
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000550 }
Owen Anderson3fe002d2010-09-08 22:16:17 +0000551 }
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000552
553 // Bail if LHS was a icmp that can't be decomposed into an equality.
554 if (!ICmpInst::isEquality(LHSCC))
555 return 0;
Owen Anderson3fe002d2010-09-08 22:16:17 +0000556
557 Value *R1 = RHS->getOperand(0);
558 Value *R2 = RHS->getOperand(1);
559 Value *R11,*R12;
560 bool ok = false;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000561 if (decomposeBitTestICmp(RHS, RHSCC, R11, R12, R2)) {
562 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
563 A = R11; D = R12;
564 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
565 A = R12; D = R11;
566 } else {
567 return 0;
Owen Anderson3fe002d2010-09-08 22:16:17 +0000568 }
Craig Topperf40110f2014-04-25 05:29:35 +0000569 E = R2; R1 = nullptr; ok = true;
Tim Northoverdc647a22013-09-04 11:57:17 +0000570 } else if (R1->getType()->isIntegerTy()) {
571 if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
572 // As before, model no mask as a trivial mask if it'll let us do an
Mayur Pandey75b76c62014-08-19 06:41:55 +0000573 // optimization.
Tim Northoverdc647a22013-09-04 11:57:17 +0000574 R11 = R1;
575 R12 = Constant::getAllOnesValue(R1->getType());
576 }
577
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000578 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
579 A = R11; D = R12; E = R2; ok = true;
580 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000581 A = R12; D = R11; E = R2; ok = true;
582 }
583 }
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000584
585 // Bail if RHS was a icmp that can't be decomposed into an equality.
586 if (!ICmpInst::isEquality(RHSCC))
587 return 0;
588
Chad Rosier58919cc2016-05-09 21:37:43 +0000589 // Look for ANDs on the right side of the RHS icmp.
Tim Northoverdc647a22013-09-04 11:57:17 +0000590 if (!ok && R2->getType()->isIntegerTy()) {
591 if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
592 R11 = R2;
593 R12 = Constant::getAllOnesValue(R2->getType());
594 }
595
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000596 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
597 A = R11; D = R12; E = R1; ok = true;
598 } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000599 A = R12; D = R11; E = R1; ok = true;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000600 } else {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000601 return 0;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000602 }
Owen Anderson3fe002d2010-09-08 22:16:17 +0000603 }
604 if (!ok)
605 return 0;
606
607 if (L11 == A) {
608 B = L12; C = L2;
Craig Topperae48cb22012-12-20 07:15:54 +0000609 } else if (L12 == A) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000610 B = L11; C = L2;
Craig Topperae48cb22012-12-20 07:15:54 +0000611 } else if (L21 == A) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000612 B = L22; C = L1;
Craig Topperae48cb22012-12-20 07:15:54 +0000613 } else if (L22 == A) {
Owen Anderson3fe002d2010-09-08 22:16:17 +0000614 B = L21; C = L1;
615 }
616
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000617 unsigned LeftType = getTypeOfMaskedICmp(A, B, C, LHSCC);
618 unsigned RightType = getTypeOfMaskedICmp(A, D, E, RHSCC);
619 return LeftType & RightType;
Owen Anderson3fe002d2010-09-08 22:16:17 +0000620}
Sanjay Patel18549272015-09-08 18:24:36 +0000621
622/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
623/// into a single (icmp(A & X) ==/!= Y).
David Majnemer1a3327b2014-11-18 09:31:36 +0000624static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
625 llvm::InstCombiner::BuilderTy *Builder) {
Craig Topperf40110f2014-04-25 05:29:35 +0000626 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000627 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate();
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000628 unsigned Mask = foldLogOpOfMaskedICmpsHelper(A, B, C, D, E, LHS, RHS,
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000629 LHSCC, RHSCC);
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000630 if (Mask == 0) return nullptr;
Benjamin Kramerf9d0cc02012-01-09 17:23:27 +0000631 assert(ICmpInst::isEquality(LHSCC) && ICmpInst::isEquality(RHSCC) &&
632 "foldLogOpOfMaskedICmpsHelper must return an equality predicate.");
Owen Anderson3fe002d2010-09-08 22:16:17 +0000633
Tim Northoverc0756c42013-09-04 11:57:13 +0000634 // In full generality:
635 // (icmp (A & B) Op C) | (icmp (A & D) Op E)
636 // == ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
637 //
638 // If the latter can be converted into (icmp (A & X) Op Y) then the former is
639 // equivalent to (icmp (A & X) !Op Y).
640 //
641 // Therefore, we can pretend for the rest of this function that we're dealing
642 // with the conjunction, provided we flip the sense of any comparisons (both
643 // input and output).
644
645 // In most cases we're going to produce an EQ for the "&&" case.
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000646 ICmpInst::Predicate NewCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
Tim Northoverc0756c42013-09-04 11:57:13 +0000647 if (!IsAnd) {
648 // Convert the masking analysis into its equivalent with negated
649 // comparisons.
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000650 Mask = conjugateICmpMask(Mask);
Tim Northoverc0756c42013-09-04 11:57:13 +0000651 }
Owen Anderson3fe002d2010-09-08 22:16:17 +0000652
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000653 if (Mask & FoldMskICmp_Mask_AllZeroes) {
Craig Topper9d4171a2012-12-20 07:09:41 +0000654 // (icmp eq (A & B), 0) & (icmp eq (A & D), 0)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000655 // -> (icmp eq (A & (B|D)), 0)
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000656 Value *NewOr = Builder->CreateOr(B, D);
657 Value *NewAnd = Builder->CreateAnd(A, NewOr);
658 // We can't use C as zero because we might actually handle
Craig Topper9d4171a2012-12-20 07:09:41 +0000659 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000660 // with B and D, having a single bit set.
661 Value *Zero = Constant::getNullValue(A->getType());
662 return Builder->CreateICmp(NewCC, NewAnd, Zero);
Owen Anderson3fe002d2010-09-08 22:16:17 +0000663 }
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000664 if (Mask & FoldMskICmp_BMask_AllOnes) {
Craig Topper9d4171a2012-12-20 07:09:41 +0000665 // (icmp eq (A & B), B) & (icmp eq (A & D), D)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000666 // -> (icmp eq (A & (B|D)), (B|D))
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000667 Value *NewOr = Builder->CreateOr(B, D);
668 Value *NewAnd = Builder->CreateAnd(A, NewOr);
669 return Builder->CreateICmp(NewCC, NewAnd, NewOr);
Craig Topper9d4171a2012-12-20 07:09:41 +0000670 }
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000671 if (Mask & FoldMskICmp_AMask_AllOnes) {
Craig Topper9d4171a2012-12-20 07:09:41 +0000672 // (icmp eq (A & B), A) & (icmp eq (A & D), A)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000673 // -> (icmp eq (A & (B&D)), A)
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000674 Value *NewAnd1 = Builder->CreateAnd(B, D);
675 Value *NewAnd2 = Builder->CreateAnd(A, NewAnd1);
676 return Builder->CreateICmp(NewCC, NewAnd2, A);
Owen Anderson3fe002d2010-09-08 22:16:17 +0000677 }
Tim Northoverc0756c42013-09-04 11:57:13 +0000678
679 // Remaining cases assume at least that B and D are constant, and depend on
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000680 // their actual values. This isn't strictly necessary, just a "handle the
Tim Northoverc0756c42013-09-04 11:57:13 +0000681 // easy cases for now" decision.
682 ConstantInt *BCst = dyn_cast<ConstantInt>(B);
Craig Topperf40110f2014-04-25 05:29:35 +0000683 if (!BCst) return nullptr;
Tim Northoverc0756c42013-09-04 11:57:13 +0000684 ConstantInt *DCst = dyn_cast<ConstantInt>(D);
Craig Topperf40110f2014-04-25 05:29:35 +0000685 if (!DCst) return nullptr;
Tim Northoverc0756c42013-09-04 11:57:13 +0000686
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000687 if (Mask & (FoldMskICmp_Mask_NotAllZeroes | FoldMskICmp_BMask_NotAllOnes)) {
Tim Northoverc0756c42013-09-04 11:57:13 +0000688 // (icmp ne (A & B), 0) & (icmp ne (A & D), 0) and
689 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
690 // -> (icmp ne (A & B), 0) or (icmp ne (A & D), 0)
691 // Only valid if one of the masks is a superset of the other (check "B&D" is
692 // the same as either B or D).
693 APInt NewMask = BCst->getValue() & DCst->getValue();
694
695 if (NewMask == BCst->getValue())
696 return LHS;
697 else if (NewMask == DCst->getValue())
698 return RHS;
699 }
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000700 if (Mask & FoldMskICmp_AMask_NotAllOnes) {
Tim Northoverc0756c42013-09-04 11:57:13 +0000701 // (icmp ne (A & B), B) & (icmp ne (A & D), D)
702 // -> (icmp ne (A & B), A) or (icmp ne (A & D), A)
703 // Only valid if one of the masks is a superset of the other (check "B|D" is
704 // the same as either B or D).
705 APInt NewMask = BCst->getValue() | DCst->getValue();
706
707 if (NewMask == BCst->getValue())
708 return LHS;
709 else if (NewMask == DCst->getValue())
710 return RHS;
711 }
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000712 if (Mask & FoldMskICmp_BMask_Mixed) {
Craig Topper9d4171a2012-12-20 07:09:41 +0000713 // (icmp eq (A & B), C) & (icmp eq (A & D), E)
Owen Anderson3fe002d2010-09-08 22:16:17 +0000714 // We already know that B & C == C && D & E == E.
715 // If we can prove that (B & D) & (C ^ E) == 0, that is, the bits of
716 // C and E, which are shared by both the mask B and the mask D, don't
717 // contradict, then we can transform to
718 // -> (icmp eq (A & (B|D)), (C|E))
719 // Currently, we only handle the case of B, C, D, and E being constant.
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000720 // We can't simply use C and E because we might actually handle
Craig Topper9d4171a2012-12-20 07:09:41 +0000721 // (icmp ne (A & B), B) & (icmp eq (A & D), D)
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000722 // with B and D, having a single bit set.
Owen Anderson3fe002d2010-09-08 22:16:17 +0000723 ConstantInt *CCst = dyn_cast<ConstantInt>(C);
Craig Topperf40110f2014-04-25 05:29:35 +0000724 if (!CCst) return nullptr;
Owen Anderson3fe002d2010-09-08 22:16:17 +0000725 ConstantInt *ECst = dyn_cast<ConstantInt>(E);
Craig Topperf40110f2014-04-25 05:29:35 +0000726 if (!ECst) return nullptr;
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000727 if (LHSCC != NewCC)
David Majnemer1a3327b2014-11-18 09:31:36 +0000728 CCst = cast<ConstantInt>(ConstantExpr::getXor(BCst, CCst));
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000729 if (RHSCC != NewCC)
David Majnemer1a3327b2014-11-18 09:31:36 +0000730 ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000731 // If there is a conflict, we should actually return a false for the
732 // whole construct.
David Majnemer1a3327b2014-11-18 09:31:36 +0000733 if (((BCst->getValue() & DCst->getValue()) &
734 (CCst->getValue() ^ ECst->getValue())) != 0)
David Majnemer6fdb6b82014-11-18 09:31:41 +0000735 return ConstantInt::get(LHS->getType(), !IsAnd);
Sanjay Patel3b8dcc72016-01-18 18:28:09 +0000736 Value *NewOr1 = Builder->CreateOr(B, D);
737 Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
738 Value *NewAnd = Builder->CreateAnd(A, NewOr1);
739 return Builder->CreateICmp(NewCC, NewAnd, NewOr2);
Owen Anderson3fe002d2010-09-08 22:16:17 +0000740 }
Craig Topperf40110f2014-04-25 05:29:35 +0000741 return nullptr;
Owen Anderson3fe002d2010-09-08 22:16:17 +0000742}
743
Erik Ecksteind1817522014-12-03 10:39:15 +0000744/// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
745/// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
746/// If \p Inverted is true then the check is for the inverted range, e.g.
747/// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
748Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
749 bool Inverted) {
750 // Check the lower range comparison, e.g. x >= 0
751 // InstCombine already ensured that if there is a constant it's on the RHS.
752 ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
753 if (!RangeStart)
754 return nullptr;
755
756 ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
757 Cmp0->getPredicate());
758
759 // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
760 if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
761 (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
762 return nullptr;
763
764 ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
765 Cmp1->getPredicate());
766
767 Value *Input = Cmp0->getOperand(0);
768 Value *RangeEnd;
769 if (Cmp1->getOperand(0) == Input) {
770 // For the upper range compare we have: icmp x, n
771 RangeEnd = Cmp1->getOperand(1);
772 } else if (Cmp1->getOperand(1) == Input) {
773 // For the upper range compare we have: icmp n, x
774 RangeEnd = Cmp1->getOperand(0);
775 Pred1 = ICmpInst::getSwappedPredicate(Pred1);
776 } else {
777 return nullptr;
778 }
779
780 // Check the upper range comparison, e.g. x < n
781 ICmpInst::Predicate NewPred;
782 switch (Pred1) {
783 case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
784 case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
785 default: return nullptr;
786 }
787
788 // This simplification is only valid if the upper range is not negative.
789 bool IsNegative, IsNotNegative;
David Majnemer54c2ca22014-12-26 09:10:14 +0000790 ComputeSignBit(RangeEnd, IsNotNegative, IsNegative, /*Depth=*/0, Cmp1);
Erik Ecksteind1817522014-12-03 10:39:15 +0000791 if (!IsNotNegative)
792 return nullptr;
793
794 if (Inverted)
795 NewPred = ICmpInst::getInversePredicate(NewPred);
796
797 return Builder->CreateICmp(NewPred, Input, RangeEnd);
798}
799
Sanjay Patel18549272015-09-08 18:24:36 +0000800/// Fold (icmp)&(icmp) if possible.
Chris Lattner067459c2010-03-05 08:46:26 +0000801Value *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
Chris Lattner0a8191e2010-01-05 07:50:36 +0000802 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate();
803
804 // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
805 if (PredicatesFoldable(LHSCC, RHSCC)) {
806 if (LHS->getOperand(0) == RHS->getOperand(1) &&
807 LHS->getOperand(1) == RHS->getOperand(0))
808 LHS->swapOperands();
809 if (LHS->getOperand(0) == RHS->getOperand(0) &&
810 LHS->getOperand(1) == RHS->getOperand(1)) {
811 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
812 unsigned Code = getICmpCode(LHS) & getICmpCode(RHS);
813 bool isSigned = LHS->isSigned() || RHS->isSigned();
Pete Cooperebf98c12011-12-17 01:20:32 +0000814 return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000815 }
816 }
Owen Anderson3fe002d2010-09-08 22:16:17 +0000817
Chris Lattnerdcef03f2011-02-10 05:17:27 +0000818 // handle (roughly): (icmp eq (A & B), C) & (icmp eq (A & D), E)
Tim Northoverc0756c42013-09-04 11:57:13 +0000819 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
Chris Lattnerdcef03f2011-02-10 05:17:27 +0000820 return V;
Craig Topper9d4171a2012-12-20 07:09:41 +0000821
Erik Ecksteind1817522014-12-03 10:39:15 +0000822 // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
823 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
824 return V;
825
826 // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
827 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
828 return V;
829
Chris Lattner0a8191e2010-01-05 07:50:36 +0000830 // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
831 Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0);
832 ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1));
833 ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1));
Craig Topperf40110f2014-04-25 05:29:35 +0000834 if (!LHSCst || !RHSCst) return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +0000835
Chris Lattner0a8191e2010-01-05 07:50:36 +0000836 if (LHSCst == RHSCst && LHSCC == RHSCC) {
837 // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
Sanjay Patelc2ceb8b2016-01-18 19:17:58 +0000838 // where C is a power of 2 or
Chris Lattner0a8191e2010-01-05 07:50:36 +0000839 // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
Sanjay Patelc2ceb8b2016-01-18 19:17:58 +0000840 if ((LHSCC == ICmpInst::ICMP_ULT && LHSCst->getValue().isPowerOf2()) ||
841 (LHSCC == ICmpInst::ICMP_EQ && LHSCst->isZero())) {
Chris Lattner0a8191e2010-01-05 07:50:36 +0000842 Value *NewOr = Builder->CreateOr(Val, Val2);
Chris Lattner067459c2010-03-05 08:46:26 +0000843 return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000844 }
845 }
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000846
Benjamin Kramer101720f2011-04-28 20:09:57 +0000847 // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000848 // where CMAX is the all ones value for the truncated type,
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000849 // iff the lower bits of C2 and CA are zero.
Bill Wendlingf2c78f32012-02-29 01:46:50 +0000850 if (LHSCC == ICmpInst::ICMP_EQ && LHSCC == RHSCC &&
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000851 LHS->hasOneUse() && RHS->hasOneUse()) {
852 Value *V;
Craig Topperf40110f2014-04-25 05:29:35 +0000853 ConstantInt *AndCst, *SmallCst = nullptr, *BigCst = nullptr;
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000854
855 // (trunc x) == C1 & (and x, CA) == C2
Craig Topperae48cb22012-12-20 07:15:54 +0000856 // (and x, CA) == C2 & (trunc x) == C1
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000857 if (match(Val2, m_Trunc(m_Value(V))) &&
858 match(Val, m_And(m_Specific(V), m_ConstantInt(AndCst)))) {
859 SmallCst = RHSCst;
860 BigCst = LHSCst;
Craig Topperae48cb22012-12-20 07:15:54 +0000861 } else if (match(Val, m_Trunc(m_Value(V))) &&
862 match(Val2, m_And(m_Specific(V), m_ConstantInt(AndCst)))) {
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000863 SmallCst = LHSCst;
864 BigCst = RHSCst;
865 }
866
867 if (SmallCst && BigCst) {
868 unsigned BigBitSize = BigCst->getType()->getBitWidth();
869 unsigned SmallBitSize = SmallCst->getType()->getBitWidth();
870
871 // Check that the low bits are zero.
872 APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
Benjamin Kramercf9d1ad2011-04-28 21:38:51 +0000873 if ((Low & AndCst->getValue()) == 0 && (Low & BigCst->getValue()) == 0) {
Benjamin Kramer4145c0d2011-04-28 16:58:40 +0000874 Value *NewAnd = Builder->CreateAnd(V, Low | AndCst->getValue());
875 APInt N = SmallCst->getValue().zext(BigBitSize) | BigCst->getValue();
876 Value *NewVal = ConstantInt::get(AndCst->getType()->getContext(), N);
877 return Builder->CreateICmp(LHSCC, NewAnd, NewVal);
878 }
879 }
880 }
Benjamin Kramerda37e152012-01-08 18:32:24 +0000881
Chris Lattner0a8191e2010-01-05 07:50:36 +0000882 // From here on, we only handle:
883 // (icmp1 A, C1) & (icmp2 A, C2) --> something simpler.
Craig Topperf40110f2014-04-25 05:29:35 +0000884 if (Val != Val2) return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +0000885
Chris Lattner0a8191e2010-01-05 07:50:36 +0000886 // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere.
887 if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE ||
888 RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE ||
889 LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE ||
890 RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE)
Craig Topperf40110f2014-04-25 05:29:35 +0000891 return nullptr;
Anders Carlssonda80afe2011-03-01 15:05:01 +0000892
Chris Lattner0a8191e2010-01-05 07:50:36 +0000893 // We can't fold (ugt x, C) & (sgt x, C2).
894 if (!PredicatesFoldable(LHSCC, RHSCC))
Craig Topperf40110f2014-04-25 05:29:35 +0000895 return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +0000896
Chris Lattner0a8191e2010-01-05 07:50:36 +0000897 // Ensure that the larger constant is on the RHS.
898 bool ShouldSwap;
899 if (CmpInst::isSigned(LHSCC) ||
Craig Topper9d4171a2012-12-20 07:09:41 +0000900 (ICmpInst::isEquality(LHSCC) &&
Chris Lattner0a8191e2010-01-05 07:50:36 +0000901 CmpInst::isSigned(RHSCC)))
902 ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue());
903 else
904 ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue());
Craig Topper9d4171a2012-12-20 07:09:41 +0000905
Chris Lattner0a8191e2010-01-05 07:50:36 +0000906 if (ShouldSwap) {
907 std::swap(LHS, RHS);
908 std::swap(LHSCst, RHSCst);
909 std::swap(LHSCC, RHSCC);
910 }
911
Dan Gohman4a618822010-02-10 16:03:48 +0000912 // At this point, we know we have two icmp instructions
Chris Lattner0a8191e2010-01-05 07:50:36 +0000913 // comparing a value against two constants and and'ing the result
914 // together. Because of the above check, we know that we only have
Craig Topper9d4171a2012-12-20 07:09:41 +0000915 // icmp eq, icmp ne, icmp [su]lt, and icmp [SU]gt here. We also know
916 // (from the icmp folding check above), that the two constants
Chris Lattner0a8191e2010-01-05 07:50:36 +0000917 // are not equal and that the larger constant is on the RHS
918 assert(LHSCst != RHSCst && "Compares not folded above?");
919
920 switch (LHSCC) {
921 default: llvm_unreachable("Unknown integer condition code!");
922 case ICmpInst::ICMP_EQ:
923 switch (RHSCC) {
924 default: llvm_unreachable("Unknown integer condition code!");
Chris Lattner0a8191e2010-01-05 07:50:36 +0000925 case ICmpInst::ICMP_NE: // (X == 13 & X != 15) -> X == 13
926 case ICmpInst::ICMP_ULT: // (X == 13 & X < 15) -> X == 13
927 case ICmpInst::ICMP_SLT: // (X == 13 & X < 15) -> X == 13
Chris Lattner067459c2010-03-05 08:46:26 +0000928 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000929 }
930 case ICmpInst::ICMP_NE:
931 switch (RHSCC) {
932 default: llvm_unreachable("Unknown integer condition code!");
933 case ICmpInst::ICMP_ULT:
934 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X u< 14) -> X < 13
Chris Lattner067459c2010-03-05 08:46:26 +0000935 return Builder->CreateICmpULT(Val, LHSCst);
Benjamin Kramer240b85e2014-10-12 14:02:34 +0000936 if (LHSCst->isNullValue()) // (X != 0 & X u< 14) -> X-1 u< 13
Sanjay Patel85d79742016-08-31 19:49:56 +0000937 return insertRangeTest(Val, LHSCst->getValue() + 1, RHSCst->getValue(),
938 false, true);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000939 break; // (X != 13 & X u< 15) -> no change
940 case ICmpInst::ICMP_SLT:
941 if (LHSCst == SubOne(RHSCst)) // (X != 13 & X s< 14) -> X < 13
Chris Lattner067459c2010-03-05 08:46:26 +0000942 return Builder->CreateICmpSLT(Val, LHSCst);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000943 break; // (X != 13 & X s< 15) -> no change
944 case ICmpInst::ICMP_EQ: // (X != 13 & X == 15) -> X == 15
945 case ICmpInst::ICMP_UGT: // (X != 13 & X u> 15) -> X u> 15
946 case ICmpInst::ICMP_SGT: // (X != 13 & X s> 15) -> X s> 15
Chris Lattner067459c2010-03-05 08:46:26 +0000947 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000948 case ICmpInst::ICMP_NE:
Jim Grosbach20e3b9a2013-08-16 00:15:20 +0000949 // Special case to get the ordering right when the values wrap around
950 // zero.
Jim Grosbachd0de8ac2013-08-16 17:03:36 +0000951 if (LHSCst->getValue() == 0 && RHSCst->getValue().isAllOnesValue())
Jim Grosbach20e3b9a2013-08-16 00:15:20 +0000952 std::swap(LHSCst, RHSCst);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000953 if (LHSCst == SubOne(RHSCst)){// (X != 13 & X != 14) -> X-13 >u 1
954 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
955 Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off");
Jim Grosbach20e3b9a2013-08-16 00:15:20 +0000956 return Builder->CreateICmpUGT(Add, ConstantInt::get(Add->getType(), 1),
957 Val->getName()+".cmp");
Chris Lattner0a8191e2010-01-05 07:50:36 +0000958 }
959 break; // (X != 13 & X != 15) -> no change
960 }
961 break;
962 case ICmpInst::ICMP_ULT:
963 switch (RHSCC) {
964 default: llvm_unreachable("Unknown integer condition code!");
965 case ICmpInst::ICMP_EQ: // (X u< 13 & X == 15) -> false
966 case ICmpInst::ICMP_UGT: // (X u< 13 & X u> 15) -> false
Chris Lattner067459c2010-03-05 08:46:26 +0000967 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
Chris Lattner0a8191e2010-01-05 07:50:36 +0000968 case ICmpInst::ICMP_SGT: // (X u< 13 & X s> 15) -> no change
969 break;
970 case ICmpInst::ICMP_NE: // (X u< 13 & X != 15) -> X u< 13
971 case ICmpInst::ICMP_ULT: // (X u< 13 & X u< 15) -> X u< 13
Chris Lattner067459c2010-03-05 08:46:26 +0000972 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000973 case ICmpInst::ICMP_SLT: // (X u< 13 & X s< 15) -> no change
974 break;
975 }
976 break;
977 case ICmpInst::ICMP_SLT:
978 switch (RHSCC) {
979 default: llvm_unreachable("Unknown integer condition code!");
Chris Lattner0a8191e2010-01-05 07:50:36 +0000980 case ICmpInst::ICMP_UGT: // (X s< 13 & X u> 15) -> no change
981 break;
982 case ICmpInst::ICMP_NE: // (X s< 13 & X != 15) -> X < 13
983 case ICmpInst::ICMP_SLT: // (X s< 13 & X s< 15) -> X < 13
Chris Lattner067459c2010-03-05 08:46:26 +0000984 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000985 case ICmpInst::ICMP_ULT: // (X s< 13 & X u< 15) -> no change
986 break;
987 }
988 break;
989 case ICmpInst::ICMP_UGT:
990 switch (RHSCC) {
991 default: llvm_unreachable("Unknown integer condition code!");
992 case ICmpInst::ICMP_EQ: // (X u> 13 & X == 15) -> X == 15
993 case ICmpInst::ICMP_UGT: // (X u> 13 & X u> 15) -> X u> 15
Chris Lattner067459c2010-03-05 08:46:26 +0000994 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +0000995 case ICmpInst::ICMP_SGT: // (X u> 13 & X s> 15) -> no change
996 break;
997 case ICmpInst::ICMP_NE:
998 if (RHSCst == AddOne(LHSCst)) // (X u> 13 & X != 14) -> X u> 14
Chris Lattner067459c2010-03-05 08:46:26 +0000999 return Builder->CreateICmp(LHSCC, Val, RHSCst);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001000 break; // (X u> 13 & X != 15) -> no change
1001 case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
Sanjay Patel85d79742016-08-31 19:49:56 +00001002 return insertRangeTest(Val, LHSCst->getValue() + 1, RHSCst->getValue(),
1003 false, true);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001004 case ICmpInst::ICMP_SLT: // (X u> 13 & X s< 15) -> no change
1005 break;
1006 }
1007 break;
1008 case ICmpInst::ICMP_SGT:
1009 switch (RHSCC) {
1010 default: llvm_unreachable("Unknown integer condition code!");
1011 case ICmpInst::ICMP_EQ: // (X s> 13 & X == 15) -> X == 15
1012 case ICmpInst::ICMP_SGT: // (X s> 13 & X s> 15) -> X s> 15
Chris Lattner067459c2010-03-05 08:46:26 +00001013 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001014 case ICmpInst::ICMP_UGT: // (X s> 13 & X u> 15) -> no change
1015 break;
1016 case ICmpInst::ICMP_NE:
1017 if (RHSCst == AddOne(LHSCst)) // (X s> 13 & X != 14) -> X s> 14
Chris Lattner067459c2010-03-05 08:46:26 +00001018 return Builder->CreateICmp(LHSCC, Val, RHSCst);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001019 break; // (X s> 13 & X != 15) -> no change
1020 case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
Sanjay Patel85d79742016-08-31 19:49:56 +00001021 return insertRangeTest(Val, LHSCst->getValue() + 1, RHSCst->getValue(),
1022 true, true);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001023 case ICmpInst::ICMP_ULT: // (X s> 13 & X u< 15) -> no change
1024 break;
1025 }
1026 break;
1027 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001028
Craig Topperf40110f2014-04-25 05:29:35 +00001029 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001030}
1031
Sanjay Patel18549272015-09-08 18:24:36 +00001032/// Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of instcombine, this returns
1033/// a Value which should already be inserted into the function.
Chris Lattner067459c2010-03-05 08:46:26 +00001034Value *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
Tim Shenaec68b22016-06-29 20:10:17 +00001035 Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
1036 Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
1037 FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
1038
1039 if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
1040 // Swap RHS operands to match LHS.
1041 Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
1042 std::swap(Op1LHS, Op1RHS);
1043 }
1044
1045 // Simplify (fcmp cc0 x, y) & (fcmp cc1 x, y).
1046 // Suppose the relation between x and y is R, where R is one of
1047 // U(1000), L(0100), G(0010) or E(0001), and CC0 and CC1 are the bitmasks for
1048 // testing the desired relations.
1049 //
1050 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1051 // bool(R & CC0) && bool(R & CC1)
1052 // = bool((R & CC0) & (R & CC1))
1053 // = bool(R & (CC0 & CC1)) <= by re-association, commutation, and idempotency
1054 if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
1055 return getFCmpValue(getFCmpCode(Op0CC) & getFCmpCode(Op1CC), Op0LHS, Op0RHS,
1056 Builder);
1057
Chris Lattner0a8191e2010-01-05 07:50:36 +00001058 if (LHS->getPredicate() == FCmpInst::FCMP_ORD &&
1059 RHS->getPredicate() == FCmpInst::FCMP_ORD) {
Benjamin Kramere89c7052013-04-12 21:56:23 +00001060 if (LHS->getOperand(0)->getType() != RHS->getOperand(0)->getType())
Craig Topperf40110f2014-04-25 05:29:35 +00001061 return nullptr;
Benjamin Kramere89c7052013-04-12 21:56:23 +00001062
Chris Lattner0a8191e2010-01-05 07:50:36 +00001063 // (fcmp ord x, c) & (fcmp ord y, c) -> (fcmp ord x, y)
1064 if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
1065 if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
1066 // If either of the constants are nans, then the whole thing returns
1067 // false.
1068 if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
Jakub Staszak461d1fe2013-06-06 00:37:23 +00001069 return Builder->getFalse();
Chris Lattner067459c2010-03-05 08:46:26 +00001070 return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
Chris Lattner0a8191e2010-01-05 07:50:36 +00001071 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001072
Chris Lattner0a8191e2010-01-05 07:50:36 +00001073 // Handle vector zeros. This occurs because the canonical form of
1074 // "fcmp ord x,x" is "fcmp ord x, 0".
1075 if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
1076 isa<ConstantAggregateZero>(RHS->getOperand(1)))
Chris Lattner067459c2010-03-05 08:46:26 +00001077 return Builder->CreateFCmpORD(LHS->getOperand(0), RHS->getOperand(0));
Craig Topperf40110f2014-04-25 05:29:35 +00001078 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001079 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001080
Craig Topperf40110f2014-04-25 05:29:35 +00001081 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001082}
1083
Sanjay Patelb54e62f2015-09-08 20:14:13 +00001084/// Match De Morgan's Laws:
1085/// (~A & ~B) == (~(A | B))
1086/// (~A | ~B) == (~(A & B))
1087static Instruction *matchDeMorgansLaws(BinaryOperator &I,
1088 InstCombiner::BuilderTy *Builder) {
1089 auto Opcode = I.getOpcode();
1090 assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1091 "Trying to match De Morgan's Laws with something other than and/or");
Sanjay Patele1b09ca2015-09-25 23:21:38 +00001092 // Flip the logic operation.
1093 if (Opcode == Instruction::And)
1094 Opcode = Instruction::Or;
1095 else
1096 Opcode = Instruction::And;
Sanjay Patelb54e62f2015-09-08 20:14:13 +00001097
1098 Value *Op0 = I.getOperand(0);
1099 Value *Op1 = I.getOperand(1);
1100 // TODO: Use pattern matchers instead of dyn_cast.
1101 if (Value *Op0NotVal = dyn_castNotVal(Op0))
1102 if (Value *Op1NotVal = dyn_castNotVal(Op1))
1103 if (Op0->hasOneUse() && Op1->hasOneUse()) {
Sanjay Patelb54e62f2015-09-08 20:14:13 +00001104 Value *LogicOp = Builder->CreateBinOp(Opcode, Op0NotVal, Op1NotVal,
1105 I.getName() + ".demorgan");
1106 return BinaryOperator::CreateNot(LogicOp);
1107 }
1108
1109 return nullptr;
1110}
1111
Tobias Grosser8ef834c2016-07-19 09:06:08 +00001112bool InstCombiner::shouldOptimizeCast(CastInst *CI) {
1113 Value *CastSrc = CI->getOperand(0);
1114
1115 // Noop casts and casts of constants should be eliminated trivially.
1116 if (CI->getSrcTy() == CI->getDestTy() || isa<Constant>(CastSrc))
1117 return false;
1118
1119 // If this cast is paired with another cast that can be eliminated, we prefer
1120 // to have it eliminated.
1121 if (const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1122 if (isEliminableCastPair(PrecedingCI, CI))
1123 return false;
1124
1125 // If this is a vector sext from a compare, then we don't want to break the
1126 // idiom where each element of the extended vector is either zero or all ones.
1127 if (CI->getOpcode() == Instruction::SExt &&
1128 isa<CmpInst>(CastSrc) && CI->getDestTy()->isVectorTy())
1129 return false;
1130
1131 return true;
1132}
1133
Sanjay Patel60312bc42016-09-12 00:16:23 +00001134/// Fold {and,or,xor} (cast X), C.
1135static Instruction *foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast,
1136 InstCombiner::BuilderTy *Builder) {
1137 Constant *C;
1138 if (!match(Logic.getOperand(1), m_Constant(C)))
1139 return nullptr;
1140
1141 auto LogicOpc = Logic.getOpcode();
1142 Type *DestTy = Logic.getType();
1143 Type *SrcTy = Cast->getSrcTy();
1144
1145 // If the first operand is bitcast, move the logic operation ahead of the
1146 // bitcast (do the logic operation in the original type). This can eliminate
1147 // bitcasts and allow combines that would otherwise be impeded by the bitcast.
1148 Value *X;
1149 if (match(Cast, m_BitCast(m_Value(X)))) {
1150 Value *NewConstant = ConstantExpr::getBitCast(C, SrcTy);
1151 Value *NewOp = Builder->CreateBinOp(LogicOpc, X, NewConstant);
1152 return CastInst::CreateBitOrPointerCast(NewOp, DestTy);
1153 }
1154
1155 // Similarly, move the logic operation ahead of a zext if the constant is
1156 // unchanged in the smaller source type. Performing the logic in a smaller
1157 // type may provide more information to later folds, and the smaller logic
1158 // instruction may be cheaper (particularly in the case of vectors).
1159 if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
1160 Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
1161 Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
1162 if (ZextTruncC == C) {
1163 // LogicOpc (zext X), C --> zext (LogicOpc X, C)
1164 Value *NewOp = Builder->CreateBinOp(LogicOpc, X, TruncC);
1165 return new ZExtInst(NewOp, DestTy);
1166 }
1167 }
1168
1169 return nullptr;
1170}
1171
1172/// Fold {and,or,xor} (cast X), Y.
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001173Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001174 auto LogicOpc = I.getOpcode();
Sanjay Pateldbbaca02016-02-24 17:00:34 +00001175 assert((LogicOpc == Instruction::And || LogicOpc == Instruction::Or ||
1176 LogicOpc == Instruction::Xor) &&
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001177 "Unexpected opcode for bitwise logic folding");
1178
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001179 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Sanjay Patel713f25e2016-02-23 17:41:34 +00001180 CastInst *Cast0 = dyn_cast<CastInst>(Op0);
Sanjay Patel9bba7502016-03-03 19:19:04 +00001181 if (!Cast0)
Sanjay Patel7d0d8102016-02-23 16:59:21 +00001182 return nullptr;
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001183
Sanjay Patel9bba7502016-03-03 19:19:04 +00001184 // This must be a cast from an integer or integer vector source type to allow
1185 // transformation of the logic operation to the source type.
1186 Type *DestTy = I.getType();
Sanjay Patel713f25e2016-02-23 17:41:34 +00001187 Type *SrcTy = Cast0->getSrcTy();
Sanjay Patel9bba7502016-03-03 19:19:04 +00001188 if (!SrcTy->isIntOrIntVectorTy())
1189 return nullptr;
1190
Sanjay Patel60312bc42016-09-12 00:16:23 +00001191 if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
1192 return Ret;
Sanjay Patel0753c062016-07-21 00:24:18 +00001193
Sanjay Patel9bba7502016-03-03 19:19:04 +00001194 CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1195 if (!Cast1)
1196 return nullptr;
1197
1198 // Both operands of the logic operation are casts. The casts must be of the
1199 // same type for reduction.
1200 auto CastOpcode = Cast0->getOpcode();
1201 if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
Sanjay Patel713f25e2016-02-23 17:41:34 +00001202 return nullptr;
1203
1204 Value *Cast0Src = Cast0->getOperand(0);
1205 Value *Cast1Src = Cast1->getOperand(0);
Sanjay Patel713f25e2016-02-23 17:41:34 +00001206
Tobias Grosser8ef834c2016-07-19 09:06:08 +00001207 // fold logic(cast(A), cast(B)) -> cast(logic(A, B))
Tobias Grosser8757e382016-08-03 19:30:35 +00001208 if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001209 Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1210 I.getName());
Sanjay Patel713f25e2016-02-23 17:41:34 +00001211 return CastInst::Create(CastOpcode, NewOp, DestTy);
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001212 }
Sanjay Patel713f25e2016-02-23 17:41:34 +00001213
Sanjay Pateldbbaca02016-02-24 17:00:34 +00001214 // For now, only 'and'/'or' have optimizations after this.
1215 if (LogicOpc == Instruction::Xor)
1216 return nullptr;
1217
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001218 // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
Sanjay Patel713f25e2016-02-23 17:41:34 +00001219 // cast is otherwise not optimizable. This happens for vector sexts.
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001220 ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1221 ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1222 if (ICmp0 && ICmp1) {
1223 Value *Res = LogicOpc == Instruction::And ? FoldAndOfICmps(ICmp0, ICmp1)
1224 : FoldOrOfICmps(ICmp0, ICmp1, &I);
1225 if (Res)
1226 return CastInst::Create(CastOpcode, Res, DestTy);
1227 return nullptr;
1228 }
Sanjay Patel713f25e2016-02-23 17:41:34 +00001229
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001230 // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
Sanjay Patel713f25e2016-02-23 17:41:34 +00001231 // cast is otherwise not optimizable. This happens for vector sexts.
Sanjay Patel75b4ae22016-02-23 23:56:23 +00001232 FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1233 FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1234 if (FCmp0 && FCmp1) {
1235 Value *Res = LogicOpc == Instruction::And ? FoldAndOfFCmps(FCmp0, FCmp1)
1236 : FoldOrOfFCmps(FCmp0, FCmp1);
1237 if (Res)
1238 return CastInst::Create(CastOpcode, Res, DestTy);
1239 return nullptr;
1240 }
Sanjay Patel713f25e2016-02-23 17:41:34 +00001241
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001242 return nullptr;
1243}
1244
Sanjay Patel74d23ad2016-05-27 21:41:29 +00001245static Instruction *foldBoolSextMaskToSelect(BinaryOperator &I) {
1246 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1247
1248 // Canonicalize SExt or Not to the LHS
1249 if (match(Op1, m_SExt(m_Value())) || match(Op1, m_Not(m_Value()))) {
1250 std::swap(Op0, Op1);
1251 }
1252
1253 // Fold (and (sext bool to A), B) --> (select bool, B, 0)
1254 Value *X = nullptr;
1255 if (match(Op0, m_SExt(m_Value(X))) &&
1256 X->getType()->getScalarType()->isIntegerTy(1)) {
1257 Value *Zero = Constant::getNullValue(Op1->getType());
1258 return SelectInst::Create(X, Op1, Zero);
1259 }
1260
1261 // Fold (and ~(sext bool to A), B) --> (select bool, 0, B)
1262 if (match(Op0, m_Not(m_SExt(m_Value(X)))) &&
1263 X->getType()->getScalarType()->isIntegerTy(1)) {
1264 Value *Zero = Constant::getNullValue(Op0->getType());
1265 return SelectInst::Create(X, Zero, Op1);
1266 }
Justin Bognerc7e4fbe2016-08-05 01:09:48 +00001267
Sanjay Patel74d23ad2016-05-27 21:41:29 +00001268 return nullptr;
1269}
1270
Chris Lattner0a8191e2010-01-05 07:50:36 +00001271Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
Duncan Sands641baf12010-11-13 15:10:37 +00001272 bool Changed = SimplifyAssociativeOrCommutative(I);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001273 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1274
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001275 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001276 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001277
Justin Bogner99798402016-08-05 01:06:44 +00001278 if (Value *V = SimplifyAndInst(Op0, Op1, DL, &TLI, &DT, &AC))
Sanjay Patel4b198802016-02-01 22:23:39 +00001279 return replaceInstUsesWith(I, V);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001280
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00001281 // (A|B)&(A|C) -> A|(B&C) etc
1282 if (Value *V = SimplifyUsingDistributiveLaws(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001283 return replaceInstUsesWith(I, V);
Duncan Sandsadc7771f2010-11-23 14:23:47 +00001284
Craig Topper9d4171a2012-12-20 07:09:41 +00001285 // See if we can simplify any instructions used by the instruction whose sole
Chris Lattner0a8191e2010-01-05 07:50:36 +00001286 // purpose is to compute bits we don't care about.
1287 if (SimplifyDemandedInstructionBits(I))
Craig Topper9d4171a2012-12-20 07:09:41 +00001288 return &I;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001289
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00001290 if (Value *V = SimplifyBSwap(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001291 return replaceInstUsesWith(I, V);
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00001292
Chris Lattner0a8191e2010-01-05 07:50:36 +00001293 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
1294 const APInt &AndRHSMask = AndRHS->getValue();
Chris Lattner0a8191e2010-01-05 07:50:36 +00001295
1296 // Optimize a variety of ((val OP C1) & C2) combinations...
1297 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1298 Value *Op0LHS = Op0I->getOperand(0);
1299 Value *Op0RHS = Op0I->getOperand(1);
1300 switch (Op0I->getOpcode()) {
1301 default: break;
1302 case Instruction::Xor:
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001303 case Instruction::Or: {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001304 // If the mask is only needed on one incoming arm, push it up.
1305 if (!Op0I->hasOneUse()) break;
Craig Topper9d4171a2012-12-20 07:09:41 +00001306
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001307 APInt NotAndRHS(~AndRHSMask);
Hal Finkel60db0582014-09-07 18:57:58 +00001308 if (MaskedValueIsZero(Op0LHS, NotAndRHS, 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001309 // Not masking anything out for the LHS, move to RHS.
1310 Value *NewRHS = Builder->CreateAnd(Op0RHS, AndRHS,
1311 Op0RHS->getName()+".masked");
1312 return BinaryOperator::Create(Op0I->getOpcode(), Op0LHS, NewRHS);
1313 }
1314 if (!isa<Constant>(Op0RHS) &&
Hal Finkel60db0582014-09-07 18:57:58 +00001315 MaskedValueIsZero(Op0RHS, NotAndRHS, 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001316 // Not masking anything out for the RHS, move to LHS.
1317 Value *NewLHS = Builder->CreateAnd(Op0LHS, AndRHS,
1318 Op0LHS->getName()+".masked");
1319 return BinaryOperator::Create(Op0I->getOpcode(), NewLHS, Op0RHS);
1320 }
1321
1322 break;
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001323 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00001324 case Instruction::Add:
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001325 // ((A & N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == AndRHS.
1326 // ((A | N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0
1327 // ((A ^ N) + B) & AndRHS -> (A + B) & AndRHS iff N&AndRHS == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +00001328 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, false, I))
1329 return BinaryOperator::CreateAnd(V, AndRHS);
1330 if (Value *V = FoldLogicalPlusAnd(Op0RHS, Op0LHS, AndRHS, false, I))
1331 return BinaryOperator::CreateAnd(V, AndRHS); // Add commutes
1332 break;
1333
1334 case Instruction::Sub:
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001335 // ((A & N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == AndRHS.
1336 // ((A | N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
1337 // ((A ^ N) - B) & AndRHS -> (A - B) & AndRHS iff N&AndRHS == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +00001338 if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I))
1339 return BinaryOperator::CreateAnd(V, AndRHS);
1340
Balaram Makamccf59732015-08-20 15:35:00 +00001341 // -x & 1 -> x & 1
1342 if (AndRHSMask == 1 && match(Op0LHS, m_Zero()))
1343 return BinaryOperator::CreateAnd(Op0RHS, AndRHS);
1344
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001345 // (A - N) & AndRHS -> -N & AndRHS iff A&AndRHS==0 and AndRHS
Chris Lattner0a8191e2010-01-05 07:50:36 +00001346 // has 1's for all bits that the subtraction with A might affect.
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001347 if (Op0I->hasOneUse() && !match(Op0LHS, m_Zero())) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001348 uint32_t BitWidth = AndRHSMask.getBitWidth();
1349 uint32_t Zeros = AndRHSMask.countLeadingZeros();
1350 APInt Mask = APInt::getLowBitsSet(BitWidth, BitWidth - Zeros);
1351
Hal Finkel60db0582014-09-07 18:57:58 +00001352 if (MaskedValueIsZero(Op0LHS, Mask, 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001353 Value *NewNeg = Builder->CreateNeg(Op0RHS);
1354 return BinaryOperator::CreateAnd(NewNeg, AndRHS);
1355 }
1356 }
1357 break;
1358
1359 case Instruction::Shl:
1360 case Instruction::LShr:
1361 // (1 << x) & 1 --> zext(x == 0)
1362 // (1 >> x) & 1 --> zext(x == 0)
1363 if (AndRHSMask == 1 && Op0LHS == AndRHS) {
1364 Value *NewICmp =
1365 Builder->CreateICmpEQ(Op0RHS, Constant::getNullValue(I.getType()));
1366 return new ZExtInst(NewICmp, I.getType());
1367 }
1368 break;
1369 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001370
Chris Lattner0a8191e2010-01-05 07:50:36 +00001371 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1372 if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1373 return Res;
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001374 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001375
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001376 // If this is an integer truncation, and if the source is an 'and' with
1377 // immediate, transform it. This frequently occurs for bitfield accesses.
1378 {
Craig Topperf40110f2014-04-25 05:29:35 +00001379 Value *X = nullptr; ConstantInt *YC = nullptr;
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001380 if (match(Op0, m_Trunc(m_And(m_Value(X), m_ConstantInt(YC))))) {
1381 // Change: and (trunc (and X, YC) to T), C2
1382 // into : and (trunc X to T), trunc(YC) & C2
Craig Topper9d4171a2012-12-20 07:09:41 +00001383 // This will fold the two constants together, which may allow
Chris Lattnerdcef03f2011-02-10 05:17:27 +00001384 // other simplifications.
1385 Value *NewCast = Builder->CreateTrunc(X, I.getType(), "and.shrunk");
1386 Constant *C3 = ConstantExpr::getTrunc(YC, I.getType());
1387 C3 = ConstantExpr::getAnd(C3, AndRHS);
1388 return BinaryOperator::CreateAnd(NewCast, C3);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001389 }
1390 }
1391
1392 // Try to fold constant and into select arguments.
1393 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1394 if (Instruction *R = FoldOpIntoSelect(I, SI))
1395 return R;
1396 if (isa<PHINode>(Op0))
1397 if (Instruction *NV = FoldOpIntoPhi(I))
1398 return NV;
1399 }
1400
Sanjay Patelb54e62f2015-09-08 20:14:13 +00001401 if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
1402 return DeMorgan;
Craig Topper9d4171a2012-12-20 07:09:41 +00001403
Chris Lattner0a8191e2010-01-05 07:50:36 +00001404 {
Craig Topperf40110f2014-04-25 05:29:35 +00001405 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001406 // (A|B) & ~(A&B) -> A^B
1407 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1408 match(Op1, m_Not(m_And(m_Value(C), m_Value(D)))) &&
1409 ((A == C && B == D) || (A == D && B == C)))
1410 return BinaryOperator::CreateXor(A, B);
Craig Topper9d4171a2012-12-20 07:09:41 +00001411
Chris Lattner0a8191e2010-01-05 07:50:36 +00001412 // ~(A&B) & (A|B) -> A^B
1413 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
1414 match(Op0, m_Not(m_And(m_Value(C), m_Value(D)))) &&
1415 ((A == C && B == D) || (A == D && B == C)))
1416 return BinaryOperator::CreateXor(A, B);
Craig Topper9d4171a2012-12-20 07:09:41 +00001417
Eli Friedman61d7c8a2011-09-19 21:58:15 +00001418 // A&(A^B) => A & ~B
1419 {
1420 Value *tmpOp0 = Op0;
1421 Value *tmpOp1 = Op1;
Sanjay Patel7b7eec12016-01-18 18:36:38 +00001422 if (match(Op0, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
Eli Friedman61d7c8a2011-09-19 21:58:15 +00001423 if (A == Op1 || B == Op1 ) {
1424 tmpOp1 = Op0;
1425 tmpOp0 = Op1;
1426 // Simplify below
1427 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00001428 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00001429
Sanjay Patel7b7eec12016-01-18 18:36:38 +00001430 if (match(tmpOp1, m_OneUse(m_Xor(m_Value(A), m_Value(B))))) {
Eli Friedman61d7c8a2011-09-19 21:58:15 +00001431 if (B == tmpOp0) {
1432 std::swap(A, B);
1433 }
Sanjay Pateld09b44a2016-01-18 17:50:23 +00001434 // Notice that the pattern (A&(~B)) is actually (A&(-1^B)), so if
Eli Friedman61d7c8a2011-09-19 21:58:15 +00001435 // A is originally -1 (or a vector of -1 and undefs), then we enter
1436 // an endless loop. By checking that A is non-constant we ensure that
1437 // we will never get to the loop.
1438 if (A == tmpOp0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B
Benjamin Kramer547b6c52011-09-27 20:39:19 +00001439 return BinaryOperator::CreateAnd(A, Builder->CreateNot(B));
Chris Lattner0a8191e2010-01-05 07:50:36 +00001440 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00001441 }
1442
1443 // (A&((~A)|B)) -> A&B
1444 if (match(Op0, m_Or(m_Not(m_Specific(Op1)), m_Value(A))) ||
1445 match(Op0, m_Or(m_Value(A), m_Not(m_Specific(Op1)))))
1446 return BinaryOperator::CreateAnd(A, Op1);
1447 if (match(Op1, m_Or(m_Not(m_Specific(Op0)), m_Value(A))) ||
1448 match(Op1, m_Or(m_Value(A), m_Not(m_Specific(Op0)))))
1449 return BinaryOperator::CreateAnd(A, Op0);
David Majnemer42af3602014-07-30 21:26:37 +00001450
1451 // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
1452 if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
1453 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
1454 if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
1455 return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(C));
1456
1457 // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
1458 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
1459 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
1460 if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
1461 return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C));
Suyog Sarda1c6c2f62014-08-01 04:59:26 +00001462
1463 // (A | B) & ((~A) ^ B) -> (A & B)
1464 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1465 match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B))))
1466 return BinaryOperator::CreateAnd(A, B);
1467
1468 // ((~A) ^ B) & (A | B) -> (A & B)
1469 if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) &&
1470 match(Op1, m_Or(m_Specific(A), m_Specific(B))))
1471 return BinaryOperator::CreateAnd(A, B);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001472 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001473
David Majnemer5e96f1b2014-08-30 06:18:20 +00001474 {
1475 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
1476 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
1477 if (LHS && RHS)
Chris Lattner067459c2010-03-05 08:46:26 +00001478 if (Value *Res = FoldAndOfICmps(LHS, RHS))
Sanjay Patel4b198802016-02-01 22:23:39 +00001479 return replaceInstUsesWith(I, Res);
Craig Topper9d4171a2012-12-20 07:09:41 +00001480
David Majnemer5e96f1b2014-08-30 06:18:20 +00001481 // TODO: Make this recursive; it's a little tricky because an arbitrary
1482 // number of 'and' instructions might have to be created.
1483 Value *X, *Y;
1484 if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1485 if (auto *Cmp = dyn_cast<ICmpInst>(X))
1486 if (Value *Res = FoldAndOfICmps(LHS, Cmp))
Sanjay Patel4b198802016-02-01 22:23:39 +00001487 return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
David Majnemer5e96f1b2014-08-30 06:18:20 +00001488 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1489 if (Value *Res = FoldAndOfICmps(LHS, Cmp))
Sanjay Patel4b198802016-02-01 22:23:39 +00001490 return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
David Majnemer5e96f1b2014-08-30 06:18:20 +00001491 }
1492 if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
1493 if (auto *Cmp = dyn_cast<ICmpInst>(X))
1494 if (Value *Res = FoldAndOfICmps(Cmp, RHS))
Sanjay Patel4b198802016-02-01 22:23:39 +00001495 return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
David Majnemer5e96f1b2014-08-30 06:18:20 +00001496 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
1497 if (Value *Res = FoldAndOfICmps(Cmp, RHS))
Sanjay Patel4b198802016-02-01 22:23:39 +00001498 return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
David Majnemer5e96f1b2014-08-30 06:18:20 +00001499 }
1500 }
1501
Chris Lattner4e8137d2010-02-11 06:26:33 +00001502 // If and'ing two fcmp, try combine them into one.
1503 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
1504 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
Chris Lattner067459c2010-03-05 08:46:26 +00001505 if (Value *Res = FoldAndOfFCmps(LHS, RHS))
Sanjay Patel4b198802016-02-01 22:23:39 +00001506 return replaceInstUsesWith(I, Res);
Craig Topper9d4171a2012-12-20 07:09:41 +00001507
Sanjay Patel40e7ba02016-02-23 16:36:07 +00001508 if (Instruction *CastedAnd = foldCastedBitwiseLogic(I))
1509 return CastedAnd;
Craig Topper9d4171a2012-12-20 07:09:41 +00001510
Sanjay Patel74d23ad2016-05-27 21:41:29 +00001511 if (Instruction *Select = foldBoolSextMaskToSelect(I))
1512 return Select;
Nadav Rotem513bd8a2013-01-30 06:35:22 +00001513
Craig Topperf40110f2014-04-25 05:29:35 +00001514 return Changed ? &I : nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001515}
1516
Chad Rosiera00df492016-05-25 16:22:14 +00001517/// Given an OR instruction, check to see if this is a bswap idiom. If so,
1518/// insert the new intrinsic and return it.
1519Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
Chad Rosiere5819e22016-05-26 14:58:51 +00001520 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1521
1522 // Look through zero extends.
1523 if (Instruction *Ext = dyn_cast<ZExtInst>(Op0))
1524 Op0 = Ext->getOperand(0);
1525
1526 if (Instruction *Ext = dyn_cast<ZExtInst>(Op1))
1527 Op1 = Ext->getOperand(0);
1528
1529 // (A | B) | C and A | (B | C) -> bswap if possible.
1530 bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
1531 match(Op1, m_Or(m_Value(), m_Value()));
1532
1533 // (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible.
1534 bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
1535 match(Op1, m_LogicalShift(m_Value(), m_Value()));
1536
1537 // (A & B) | (C & D) -> bswap if possible.
1538 bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
1539 match(Op1, m_And(m_Value(), m_Value()));
1540
1541 if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
1542 return nullptr;
1543
James Molloyf01488e2016-01-15 09:20:19 +00001544 SmallVector<Instruction*, 4> Insts;
Chad Rosiera00df492016-05-25 16:22:14 +00001545 if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
Craig Topperf40110f2014-04-25 05:29:35 +00001546 return nullptr;
James Molloyf01488e2016-01-15 09:20:19 +00001547 Instruction *LastInst = Insts.pop_back_val();
1548 LastInst->removeFromParent();
Craig Topper9d4171a2012-12-20 07:09:41 +00001549
James Molloyf01488e2016-01-15 09:20:19 +00001550 for (auto *Inst : Insts)
1551 Worklist.Add(Inst);
1552 return LastInst;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001553}
1554
Sanjay Patelc00e48a2016-07-13 18:07:02 +00001555/// If all elements of two constant vectors are 0/-1 and inverses, return true.
1556static bool areInverseVectorBitmasks(Constant *C1, Constant *C2) {
1557 unsigned NumElts = C1->getType()->getVectorNumElements();
1558 for (unsigned i = 0; i != NumElts; ++i) {
1559 Constant *EltC1 = C1->getAggregateElement(i);
1560 Constant *EltC2 = C2->getAggregateElement(i);
1561 if (!EltC1 || !EltC2)
1562 return false;
1563
1564 // One element must be all ones, and the other must be all zeros.
1565 // FIXME: Allow undef elements.
1566 if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
1567 (match(EltC2, m_Zero()) && match(EltC1, m_AllOnes()))))
1568 return false;
1569 }
1570 return true;
1571}
1572
Sanjay Patel7ad98ba2016-06-30 14:18:18 +00001573/// We have an expression of the form (A & C) | (B & D). If A is a scalar or
1574/// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
1575/// B, it can be used as the condition operand of a select instruction.
Sanjay Patelc00e48a2016-07-13 18:07:02 +00001576static Value *getSelectCondition(Value *A, Value *B,
1577 InstCombiner::BuilderTy &Builder) {
Sanjay Patel7ad98ba2016-06-30 14:18:18 +00001578 // If these are scalars or vectors of i1, A can be used directly.
1579 Type *Ty = A->getType();
1580 if (match(A, m_Not(m_Specific(B))) && Ty->getScalarType()->isIntegerTy(1))
1581 return A;
1582
1583 // If A and B are sign-extended, look through the sexts to find the booleans.
1584 Value *Cond;
1585 if (match(A, m_SExt(m_Value(Cond))) &&
1586 Cond->getType()->getScalarType()->isIntegerTy(1) &&
1587 match(B, m_CombineOr(m_Not(m_SExt(m_Specific(Cond))),
1588 m_SExt(m_Not(m_Specific(Cond))))))
1589 return Cond;
1590
Sanjay Patelc00e48a2016-07-13 18:07:02 +00001591 // All scalar (and most vector) possibilities should be handled now.
1592 // Try more matches that only apply to non-splat constant vectors.
1593 if (!Ty->isVectorTy())
1594 return nullptr;
Sanjay Patel7ad98ba2016-06-30 14:18:18 +00001595
Sanjay Patelc00e48a2016-07-13 18:07:02 +00001596 // If both operands are constants, see if the constants are inverse bitmasks.
1597 Constant *AC, *BC;
1598 if (match(A, m_Constant(AC)) && match(B, m_Constant(BC)) &&
1599 areInverseVectorBitmasks(AC, BC))
1600 return ConstantExpr::getTrunc(AC, CmpInst::makeCmpResultType(Ty));
1601
1602 // If both operands are xor'd with constants using the same sexted boolean
1603 // operand, see if the constants are inverse bitmasks.
1604 if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AC)))) &&
1605 match(B, (m_Xor(m_SExt(m_Specific(Cond)), m_Constant(BC)))) &&
1606 Cond->getType()->getScalarType()->isIntegerTy(1) &&
1607 areInverseVectorBitmasks(AC, BC)) {
1608 AC = ConstantExpr::getTrunc(AC, CmpInst::makeCmpResultType(Ty));
1609 return Builder.CreateXor(Cond, AC);
1610 }
Sanjay Patel7ad98ba2016-06-30 14:18:18 +00001611 return nullptr;
1612}
1613
1614/// We have an expression of the form (A & C) | (B & D). Try to simplify this
1615/// to "A' ? C : D", where A' is a boolean or vector of booleans.
Sanjay Patel4e8ebce2016-06-24 18:55:27 +00001616static Value *matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D,
Sanjay Patel7ad98ba2016-06-30 14:18:18 +00001617 InstCombiner::BuilderTy &Builder) {
Sanjay Patel4e8ebce2016-06-24 18:55:27 +00001618 // The potential condition of the select may be bitcasted. In that case, look
1619 // through its bitcast and the corresponding bitcast of the 'not' condition.
1620 Type *OrigType = A->getType();
1621 Value *SrcA, *SrcB;
Sanjay Patel664514f2016-07-08 21:17:51 +00001622 if (match(A, m_OneUse(m_BitCast(m_Value(SrcA)))) &&
1623 match(B, m_OneUse(m_BitCast(m_Value(SrcB))))) {
Sanjay Patel4e8ebce2016-06-24 18:55:27 +00001624 A = SrcA;
1625 B = SrcB;
Sanjay Patel6cf18af2016-06-03 14:42:07 +00001626 }
1627
Sanjay Patelc00e48a2016-07-13 18:07:02 +00001628 if (Value *Cond = getSelectCondition(A, B, Builder)) {
Sanjay Patel6cf18af2016-06-03 14:42:07 +00001629 // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
Sanjay Patel4e8ebce2016-06-24 18:55:27 +00001630 // The bitcasts will either all exist or all not exist. The builder will
1631 // not create unnecessary casts if the types already match.
1632 Value *BitcastC = Builder.CreateBitCast(C, A->getType());
1633 Value *BitcastD = Builder.CreateBitCast(D, A->getType());
1634 Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
1635 return Builder.CreateBitCast(Select, OrigType);
Sanjay Patel6cf18af2016-06-03 14:42:07 +00001636 }
Sanjay Patel5c0bc022016-06-02 18:03:05 +00001637
Craig Topperf40110f2014-04-25 05:29:35 +00001638 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001639}
1640
Sanjay Patel18549272015-09-08 18:24:36 +00001641/// Fold (icmp)|(icmp) if possible.
Hal Finkel60db0582014-09-07 18:57:58 +00001642Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
1643 Instruction *CxtI) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00001644 ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate();
1645
Nadav Rotem0ed2fdb2013-11-12 22:38:59 +00001646 // Fold (iszero(A & K1) | iszero(A & K2)) -> (A & (K1 | K2)) != (K1 | K2)
1647 // if K1 and K2 are a one-bit mask.
1648 ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1));
1649 ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1));
1650
1651 if (LHS->getPredicate() == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero() &&
1652 RHS->getPredicate() == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) {
1653
1654 BinaryOperator *LAnd = dyn_cast<BinaryOperator>(LHS->getOperand(0));
1655 BinaryOperator *RAnd = dyn_cast<BinaryOperator>(RHS->getOperand(0));
1656 if (LAnd && RAnd && LAnd->hasOneUse() && RHS->hasOneUse() &&
1657 LAnd->getOpcode() == Instruction::And &&
1658 RAnd->getOpcode() == Instruction::And) {
1659
Craig Topperf40110f2014-04-25 05:29:35 +00001660 Value *Mask = nullptr;
1661 Value *Masked = nullptr;
Nadav Rotem0ed2fdb2013-11-12 22:38:59 +00001662 if (LAnd->getOperand(0) == RAnd->getOperand(0) &&
Justin Bogner99798402016-08-05 01:06:44 +00001663 isKnownToBeAPowerOfTwo(LAnd->getOperand(1), DL, false, 0, &AC, CxtI,
1664 &DT) &&
1665 isKnownToBeAPowerOfTwo(RAnd->getOperand(1), DL, false, 0, &AC, CxtI,
1666 &DT)) {
Nadav Rotem0ed2fdb2013-11-12 22:38:59 +00001667 Mask = Builder->CreateOr(LAnd->getOperand(1), RAnd->getOperand(1));
1668 Masked = Builder->CreateAnd(LAnd->getOperand(0), Mask);
1669 } else if (LAnd->getOperand(1) == RAnd->getOperand(1) &&
Justin Bogner99798402016-08-05 01:06:44 +00001670 isKnownToBeAPowerOfTwo(LAnd->getOperand(0), DL, false, 0, &AC,
1671 CxtI, &DT) &&
1672 isKnownToBeAPowerOfTwo(RAnd->getOperand(0), DL, false, 0, &AC,
1673 CxtI, &DT)) {
Nadav Rotem0ed2fdb2013-11-12 22:38:59 +00001674 Mask = Builder->CreateOr(LAnd->getOperand(0), RAnd->getOperand(0));
1675 Masked = Builder->CreateAnd(LAnd->getOperand(1), Mask);
1676 }
1677
1678 if (Masked)
1679 return Builder->CreateICmp(ICmpInst::ICMP_NE, Masked, Mask);
1680 }
1681 }
1682
Yi Jiang1a4e73d2014-08-20 22:55:40 +00001683 // Fold (icmp ult/ule (A + C1), C3) | (icmp ult/ule (A + C2), C3)
1684 // --> (icmp ult/ule ((A & ~(C1 ^ C2)) + max(C1, C2)), C3)
1685 // The original condition actually refers to the following two ranges:
1686 // [MAX_UINT-C1+1, MAX_UINT-C1+1+C3] and [MAX_UINT-C2+1, MAX_UINT-C2+1+C3]
1687 // We can fold these two ranges if:
1688 // 1) C1 and C2 is unsigned greater than C3.
1689 // 2) The two ranges are separated.
1690 // 3) C1 ^ C2 is one-bit mask.
1691 // 4) LowRange1 ^ LowRange2 and HighRange1 ^ HighRange2 are one-bit mask.
1692 // This implies all values in the two ranges differ by exactly one bit.
1693
1694 if ((LHSCC == ICmpInst::ICMP_ULT || LHSCC == ICmpInst::ICMP_ULE) &&
1695 LHSCC == RHSCC && LHSCst && RHSCst && LHS->hasOneUse() &&
1696 RHS->hasOneUse() && LHSCst->getType() == RHSCst->getType() &&
1697 LHSCst->getValue() == (RHSCst->getValue())) {
1698
1699 Value *LAdd = LHS->getOperand(0);
1700 Value *RAdd = RHS->getOperand(0);
1701
1702 Value *LAddOpnd, *RAddOpnd;
1703 ConstantInt *LAddCst, *RAddCst;
1704 if (match(LAdd, m_Add(m_Value(LAddOpnd), m_ConstantInt(LAddCst))) &&
1705 match(RAdd, m_Add(m_Value(RAddOpnd), m_ConstantInt(RAddCst))) &&
1706 LAddCst->getValue().ugt(LHSCst->getValue()) &&
1707 RAddCst->getValue().ugt(LHSCst->getValue())) {
1708
1709 APInt DiffCst = LAddCst->getValue() ^ RAddCst->getValue();
1710 if (LAddOpnd == RAddOpnd && DiffCst.isPowerOf2()) {
1711 ConstantInt *MaxAddCst = nullptr;
1712 if (LAddCst->getValue().ult(RAddCst->getValue()))
1713 MaxAddCst = RAddCst;
1714 else
1715 MaxAddCst = LAddCst;
1716
1717 APInt RRangeLow = -RAddCst->getValue();
1718 APInt RRangeHigh = RRangeLow + LHSCst->getValue();
1719 APInt LRangeLow = -LAddCst->getValue();
1720 APInt LRangeHigh = LRangeLow + LHSCst->getValue();
1721 APInt LowRangeDiff = RRangeLow ^ LRangeLow;
1722 APInt HighRangeDiff = RRangeHigh ^ LRangeHigh;
1723 APInt RangeDiff = LRangeLow.sgt(RRangeLow) ? LRangeLow - RRangeLow
1724 : RRangeLow - LRangeLow;
1725
1726 if (LowRangeDiff.isPowerOf2() && LowRangeDiff == HighRangeDiff &&
1727 RangeDiff.ugt(LHSCst->getValue())) {
1728 Value *MaskCst = ConstantInt::get(LAddCst->getType(), ~DiffCst);
1729
1730 Value *NewAnd = Builder->CreateAnd(LAddOpnd, MaskCst);
1731 Value *NewAdd = Builder->CreateAdd(NewAnd, MaxAddCst);
1732 return (Builder->CreateICmp(LHS->getPredicate(), NewAdd, LHSCst));
1733 }
1734 }
1735 }
1736 }
1737
Chris Lattner0a8191e2010-01-05 07:50:36 +00001738 // (icmp1 A, B) | (icmp2 A, B) --> (icmp3 A, B)
1739 if (PredicatesFoldable(LHSCC, RHSCC)) {
1740 if (LHS->getOperand(0) == RHS->getOperand(1) &&
1741 LHS->getOperand(1) == RHS->getOperand(0))
1742 LHS->swapOperands();
1743 if (LHS->getOperand(0) == RHS->getOperand(0) &&
1744 LHS->getOperand(1) == RHS->getOperand(1)) {
1745 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
1746 unsigned Code = getICmpCode(LHS) | getICmpCode(RHS);
1747 bool isSigned = LHS->isSigned() || RHS->isSigned();
Pete Cooperebf98c12011-12-17 01:20:32 +00001748 return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001749 }
1750 }
Benjamin Kramer2bca3a62010-12-20 16:21:59 +00001751
1752 // handle (roughly):
1753 // (icmp ne (A & B), C) | (icmp ne (A & D), E)
Tim Northoverc0756c42013-09-04 11:57:13 +00001754 if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, false, Builder))
Benjamin Kramer2bca3a62010-12-20 16:21:59 +00001755 return V;
Owen Anderson3fe002d2010-09-08 22:16:17 +00001756
Chris Lattner0a8191e2010-01-05 07:50:36 +00001757 Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0);
David Majnemerc2a990b2013-07-05 00:31:17 +00001758 if (LHS->hasOneUse() || RHS->hasOneUse()) {
1759 // (icmp eq B, 0) | (icmp ult A, B) -> (icmp ule A, B-1)
1760 // (icmp eq B, 0) | (icmp ugt B, A) -> (icmp ule A, B-1)
Craig Topperf40110f2014-04-25 05:29:35 +00001761 Value *A = nullptr, *B = nullptr;
David Majnemerc2a990b2013-07-05 00:31:17 +00001762 if (LHSCC == ICmpInst::ICMP_EQ && LHSCst && LHSCst->isZero()) {
1763 B = Val;
1764 if (RHSCC == ICmpInst::ICMP_ULT && Val == RHS->getOperand(1))
1765 A = Val2;
1766 else if (RHSCC == ICmpInst::ICMP_UGT && Val == Val2)
1767 A = RHS->getOperand(1);
1768 }
1769 // (icmp ult A, B) | (icmp eq B, 0) -> (icmp ule A, B-1)
1770 // (icmp ugt B, A) | (icmp eq B, 0) -> (icmp ule A, B-1)
1771 else if (RHSCC == ICmpInst::ICMP_EQ && RHSCst && RHSCst->isZero()) {
1772 B = Val2;
1773 if (LHSCC == ICmpInst::ICMP_ULT && Val2 == LHS->getOperand(1))
1774 A = Val;
1775 else if (LHSCC == ICmpInst::ICMP_UGT && Val2 == Val)
1776 A = LHS->getOperand(1);
1777 }
1778 if (A && B)
1779 return Builder->CreateICmp(
1780 ICmpInst::ICMP_UGE,
1781 Builder->CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
1782 }
1783
Erik Ecksteind1817522014-12-03 10:39:15 +00001784 // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
1785 if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
1786 return V;
1787
1788 // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
1789 if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
1790 return V;
Justin Bognerc7e4fbe2016-08-05 01:09:48 +00001791
David Majnemerc2a990b2013-07-05 00:31:17 +00001792 // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
Craig Topperf40110f2014-04-25 05:29:35 +00001793 if (!LHSCst || !RHSCst) return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001794
Owen Anderson8f306a72010-08-02 09:32:13 +00001795 if (LHSCst == RHSCst && LHSCC == RHSCC) {
1796 // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
1797 if (LHSCC == ICmpInst::ICMP_NE && LHSCst->isZero()) {
1798 Value *NewOr = Builder->CreateOr(Val, Val2);
1799 return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
1800 }
Benjamin Kramerda37e152012-01-08 18:32:24 +00001801 }
1802
Benjamin Kramerf7957d02010-12-20 20:00:31 +00001803 // (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001804 // iff C2 + CA == C1.
Benjamin Kramerf7957d02010-12-20 20:00:31 +00001805 if (LHSCC == ICmpInst::ICMP_ULT && RHSCC == ICmpInst::ICMP_EQ) {
Benjamin Kramer68531ba2010-12-20 16:18:51 +00001806 ConstantInt *AddCst;
1807 if (match(Val, m_Add(m_Specific(Val2), m_ConstantInt(AddCst))))
1808 if (RHSCst->getValue() + AddCst->getValue() == LHSCst->getValue())
Benjamin Kramerf7957d02010-12-20 20:00:31 +00001809 return Builder->CreateICmpULE(Val, LHSCst);
Benjamin Kramer68531ba2010-12-20 16:18:51 +00001810 }
1811
Chris Lattner0a8191e2010-01-05 07:50:36 +00001812 // From here on, we only handle:
1813 // (icmp1 A, C1) | (icmp2 A, C2) --> something simpler.
Craig Topperf40110f2014-04-25 05:29:35 +00001814 if (Val != Val2) return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +00001815
Chris Lattner0a8191e2010-01-05 07:50:36 +00001816 // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere.
1817 if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE ||
1818 RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE ||
1819 LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE ||
1820 RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE)
Craig Topperf40110f2014-04-25 05:29:35 +00001821 return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +00001822
Chris Lattner0a8191e2010-01-05 07:50:36 +00001823 // We can't fold (ugt x, C) | (sgt x, C2).
1824 if (!PredicatesFoldable(LHSCC, RHSCC))
Craig Topperf40110f2014-04-25 05:29:35 +00001825 return nullptr;
Craig Topper9d4171a2012-12-20 07:09:41 +00001826
Chris Lattner0a8191e2010-01-05 07:50:36 +00001827 // Ensure that the larger constant is on the RHS.
1828 bool ShouldSwap;
1829 if (CmpInst::isSigned(LHSCC) ||
Craig Topper9d4171a2012-12-20 07:09:41 +00001830 (ICmpInst::isEquality(LHSCC) &&
Chris Lattner0a8191e2010-01-05 07:50:36 +00001831 CmpInst::isSigned(RHSCC)))
1832 ShouldSwap = LHSCst->getValue().sgt(RHSCst->getValue());
1833 else
1834 ShouldSwap = LHSCst->getValue().ugt(RHSCst->getValue());
Craig Topper9d4171a2012-12-20 07:09:41 +00001835
Chris Lattner0a8191e2010-01-05 07:50:36 +00001836 if (ShouldSwap) {
1837 std::swap(LHS, RHS);
1838 std::swap(LHSCst, RHSCst);
1839 std::swap(LHSCC, RHSCC);
1840 }
Craig Topper9d4171a2012-12-20 07:09:41 +00001841
Dan Gohman4a618822010-02-10 16:03:48 +00001842 // At this point, we know we have two icmp instructions
Chris Lattner0a8191e2010-01-05 07:50:36 +00001843 // comparing a value against two constants and or'ing the result
1844 // together. Because of the above check, we know that we only have
1845 // ICMP_EQ, ICMP_NE, ICMP_LT, and ICMP_GT here. We also know (from the
1846 // icmp folding check above), that the two constants are not
1847 // equal.
1848 assert(LHSCst != RHSCst && "Compares not folded above?");
1849
1850 switch (LHSCC) {
1851 default: llvm_unreachable("Unknown integer condition code!");
1852 case ICmpInst::ICMP_EQ:
1853 switch (RHSCC) {
1854 default: llvm_unreachable("Unknown integer condition code!");
1855 case ICmpInst::ICMP_EQ:
Jakub Staszakea2b9b92012-12-31 00:34:55 +00001856 if (LHS->getOperand(0) == RHS->getOperand(0)) {
Jakub Staszakf5849772012-12-31 01:40:44 +00001857 // if LHSCst and RHSCst differ only by one bit:
David Majnemer942003a2015-12-02 16:15:07 +00001858 // (A == C1 || A == C2) -> (A | (C1 ^ C2)) == C2
Jakub Staszakc48bbe72012-12-31 18:26:42 +00001859 assert(LHSCst->getValue().ule(LHSCst->getValue()));
1860
Jakub Staszakea2b9b92012-12-31 00:34:55 +00001861 APInt Xor = LHSCst->getValue() ^ RHSCst->getValue();
1862 if (Xor.isPowerOf2()) {
David Majnemer942003a2015-12-02 16:15:07 +00001863 Value *Cst = Builder->getInt(Xor);
1864 Value *Or = Builder->CreateOr(LHS->getOperand(0), Cst);
1865 return Builder->CreateICmp(ICmpInst::ICMP_EQ, Or, RHSCst);
Jakub Staszakea2b9b92012-12-31 00:34:55 +00001866 }
1867 }
1868
David Majnemer1fae1952013-04-14 21:15:43 +00001869 if (LHSCst == SubOne(RHSCst)) {
1870 // (X == 13 | X == 14) -> X-13 <u 2
1871 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
1872 Value *Add = Builder->CreateAdd(Val, AddCST, Val->getName()+".off");
1873 AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst);
1874 return Builder->CreateICmpULT(Add, AddCST);
1875 }
1876
Chris Lattner0a8191e2010-01-05 07:50:36 +00001877 break; // (X == 13 | X == 15) -> no change
1878 case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
1879 case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
1880 break;
1881 case ICmpInst::ICMP_NE: // (X == 13 | X != 15) -> X != 15
1882 case ICmpInst::ICMP_ULT: // (X == 13 | X u< 15) -> X u< 15
1883 case ICmpInst::ICMP_SLT: // (X == 13 | X s< 15) -> X s< 15
Chris Lattner067459c2010-03-05 08:46:26 +00001884 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001885 }
1886 break;
1887 case ICmpInst::ICMP_NE:
1888 switch (RHSCC) {
1889 default: llvm_unreachable("Unknown integer condition code!");
1890 case ICmpInst::ICMP_EQ: // (X != 13 | X == 15) -> X != 13
1891 case ICmpInst::ICMP_UGT: // (X != 13 | X u> 15) -> X != 13
1892 case ICmpInst::ICMP_SGT: // (X != 13 | X s> 15) -> X != 13
Chris Lattner067459c2010-03-05 08:46:26 +00001893 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001894 case ICmpInst::ICMP_NE: // (X != 13 | X != 15) -> true
1895 case ICmpInst::ICMP_ULT: // (X != 13 | X u< 15) -> true
1896 case ICmpInst::ICMP_SLT: // (X != 13 | X s< 15) -> true
Jakub Staszak461d1fe2013-06-06 00:37:23 +00001897 return Builder->getTrue();
Chris Lattner0a8191e2010-01-05 07:50:36 +00001898 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00001899 case ICmpInst::ICMP_ULT:
1900 switch (RHSCC) {
1901 default: llvm_unreachable("Unknown integer condition code!");
1902 case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
1903 break;
1904 case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
1905 // If RHSCst is [us]MAXINT, it is always false. Not handling
1906 // this can cause overflow.
1907 if (RHSCst->isMaxValue(false))
Chris Lattner067459c2010-03-05 08:46:26 +00001908 return LHS;
Sanjay Patel85d79742016-08-31 19:49:56 +00001909 return insertRangeTest(Val, LHSCst->getValue(), RHSCst->getValue() + 1,
1910 false, false);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001911 case ICmpInst::ICMP_SGT: // (X u< 13 | X s> 15) -> no change
1912 break;
1913 case ICmpInst::ICMP_NE: // (X u< 13 | X != 15) -> X != 15
1914 case ICmpInst::ICMP_ULT: // (X u< 13 | X u< 15) -> X u< 15
Chris Lattner067459c2010-03-05 08:46:26 +00001915 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001916 case ICmpInst::ICMP_SLT: // (X u< 13 | X s< 15) -> no change
1917 break;
1918 }
1919 break;
1920 case ICmpInst::ICMP_SLT:
1921 switch (RHSCC) {
1922 default: llvm_unreachable("Unknown integer condition code!");
1923 case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
1924 break;
1925 case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
1926 // If RHSCst is [us]MAXINT, it is always false. Not handling
1927 // this can cause overflow.
1928 if (RHSCst->isMaxValue(true))
Chris Lattner067459c2010-03-05 08:46:26 +00001929 return LHS;
Sanjay Patel85d79742016-08-31 19:49:56 +00001930 return insertRangeTest(Val, LHSCst->getValue(), RHSCst->getValue() + 1,
1931 true, false);
Chris Lattner0a8191e2010-01-05 07:50:36 +00001932 case ICmpInst::ICMP_UGT: // (X s< 13 | X u> 15) -> no change
1933 break;
1934 case ICmpInst::ICMP_NE: // (X s< 13 | X != 15) -> X != 15
1935 case ICmpInst::ICMP_SLT: // (X s< 13 | X s< 15) -> X s< 15
Chris Lattner067459c2010-03-05 08:46:26 +00001936 return RHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001937 case ICmpInst::ICMP_ULT: // (X s< 13 | X u< 15) -> no change
1938 break;
1939 }
1940 break;
1941 case ICmpInst::ICMP_UGT:
1942 switch (RHSCC) {
1943 default: llvm_unreachable("Unknown integer condition code!");
1944 case ICmpInst::ICMP_EQ: // (X u> 13 | X == 15) -> X u> 13
1945 case ICmpInst::ICMP_UGT: // (X u> 13 | X u> 15) -> X u> 13
Chris Lattner067459c2010-03-05 08:46:26 +00001946 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001947 case ICmpInst::ICMP_SGT: // (X u> 13 | X s> 15) -> no change
1948 break;
1949 case ICmpInst::ICMP_NE: // (X u> 13 | X != 15) -> true
1950 case ICmpInst::ICMP_ULT: // (X u> 13 | X u< 15) -> true
Jakub Staszak461d1fe2013-06-06 00:37:23 +00001951 return Builder->getTrue();
Chris Lattner0a8191e2010-01-05 07:50:36 +00001952 case ICmpInst::ICMP_SLT: // (X u> 13 | X s< 15) -> no change
1953 break;
1954 }
1955 break;
1956 case ICmpInst::ICMP_SGT:
1957 switch (RHSCC) {
1958 default: llvm_unreachable("Unknown integer condition code!");
1959 case ICmpInst::ICMP_EQ: // (X s> 13 | X == 15) -> X > 13
1960 case ICmpInst::ICMP_SGT: // (X s> 13 | X s> 15) -> X > 13
Chris Lattner067459c2010-03-05 08:46:26 +00001961 return LHS;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001962 case ICmpInst::ICMP_UGT: // (X s> 13 | X u> 15) -> no change
1963 break;
1964 case ICmpInst::ICMP_NE: // (X s> 13 | X != 15) -> true
1965 case ICmpInst::ICMP_SLT: // (X s> 13 | X s< 15) -> true
Jakub Staszak461d1fe2013-06-06 00:37:23 +00001966 return Builder->getTrue();
Chris Lattner0a8191e2010-01-05 07:50:36 +00001967 case ICmpInst::ICMP_ULT: // (X s> 13 | X u< 15) -> no change
1968 break;
1969 }
1970 break;
1971 }
Craig Topperf40110f2014-04-25 05:29:35 +00001972 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00001973}
1974
Sanjay Patel18549272015-09-08 18:24:36 +00001975/// Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of instcombine, this returns
1976/// a Value which should already be inserted into the function.
Chris Lattner067459c2010-03-05 08:46:26 +00001977Value *InstCombiner::FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
Tim Shenaec68b22016-06-29 20:10:17 +00001978 Value *Op0LHS = LHS->getOperand(0), *Op0RHS = LHS->getOperand(1);
1979 Value *Op1LHS = RHS->getOperand(0), *Op1RHS = RHS->getOperand(1);
1980 FCmpInst::Predicate Op0CC = LHS->getPredicate(), Op1CC = RHS->getPredicate();
1981
1982 if (Op0LHS == Op1RHS && Op0RHS == Op1LHS) {
1983 // Swap RHS operands to match LHS.
1984 Op1CC = FCmpInst::getSwappedPredicate(Op1CC);
1985 std::swap(Op1LHS, Op1RHS);
1986 }
1987
1988 // Simplify (fcmp cc0 x, y) | (fcmp cc1 x, y).
1989 // This is a similar transformation to the one in FoldAndOfFCmps.
1990 //
1991 // Since (R & CC0) and (R & CC1) are either R or 0, we actually have this:
1992 // bool(R & CC0) || bool(R & CC1)
1993 // = bool((R & CC0) | (R & CC1))
1994 // = bool(R & (CC0 | CC1)) <= by reversed distribution (contribution? ;)
1995 if (Op0LHS == Op1LHS && Op0RHS == Op1RHS)
1996 return getFCmpValue(getFCmpCode(Op0CC) | getFCmpCode(Op1CC), Op0LHS, Op0RHS,
1997 Builder);
1998
Chris Lattner0a8191e2010-01-05 07:50:36 +00001999 if (LHS->getPredicate() == FCmpInst::FCMP_UNO &&
Craig Topper9d4171a2012-12-20 07:09:41 +00002000 RHS->getPredicate() == FCmpInst::FCMP_UNO &&
Chris Lattner0a8191e2010-01-05 07:50:36 +00002001 LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType()) {
2002 if (ConstantFP *LHSC = dyn_cast<ConstantFP>(LHS->getOperand(1)))
2003 if (ConstantFP *RHSC = dyn_cast<ConstantFP>(RHS->getOperand(1))) {
2004 // If either of the constants are nans, then the whole thing returns
2005 // true.
2006 if (LHSC->getValueAPF().isNaN() || RHSC->getValueAPF().isNaN())
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002007 return Builder->getTrue();
Craig Topper9d4171a2012-12-20 07:09:41 +00002008
Chris Lattner0a8191e2010-01-05 07:50:36 +00002009 // Otherwise, no need to compare the two constants, compare the
2010 // rest.
Chris Lattner067459c2010-03-05 08:46:26 +00002011 return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002012 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002013
Chris Lattner0a8191e2010-01-05 07:50:36 +00002014 // Handle vector zeros. This occurs because the canonical form of
2015 // "fcmp uno x,x" is "fcmp uno x, 0".
2016 if (isa<ConstantAggregateZero>(LHS->getOperand(1)) &&
2017 isa<ConstantAggregateZero>(RHS->getOperand(1)))
Chris Lattner067459c2010-03-05 08:46:26 +00002018 return Builder->CreateFCmpUNO(LHS->getOperand(0), RHS->getOperand(0));
Craig Topper9d4171a2012-12-20 07:09:41 +00002019
Craig Topperf40110f2014-04-25 05:29:35 +00002020 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002021 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002022
Craig Topperf40110f2014-04-25 05:29:35 +00002023 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002024}
2025
Sanjay Patel18549272015-09-08 18:24:36 +00002026/// This helper function folds:
Chris Lattner0a8191e2010-01-05 07:50:36 +00002027///
2028/// ((A | B) & C1) | (B & C2)
2029///
2030/// into:
Craig Topper9d4171a2012-12-20 07:09:41 +00002031///
Chris Lattner0a8191e2010-01-05 07:50:36 +00002032/// (A & C1) | B
2033///
2034/// when the XOR of the two constants is "all ones" (-1).
2035Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op,
2036 Value *A, Value *B, Value *C) {
2037 ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
Craig Topperf40110f2014-04-25 05:29:35 +00002038 if (!CI1) return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002039
Craig Topperf40110f2014-04-25 05:29:35 +00002040 Value *V1 = nullptr;
2041 ConstantInt *CI2 = nullptr;
2042 if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2)))) return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002043
2044 APInt Xor = CI1->getValue() ^ CI2->getValue();
Craig Topperf40110f2014-04-25 05:29:35 +00002045 if (!Xor.isAllOnesValue()) return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002046
2047 if (V1 == A || V1 == B) {
2048 Value *NewOp = Builder->CreateAnd((V1 == A) ? B : A, CI1);
2049 return BinaryOperator::CreateOr(NewOp, V1);
2050 }
2051
Craig Topperf40110f2014-04-25 05:29:35 +00002052 return nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002053}
2054
David Majnemer5d1aeba2014-08-21 05:14:48 +00002055/// \brief This helper function folds:
2056///
2057/// ((A | B) & C1) ^ (B & C2)
2058///
2059/// into:
2060///
2061/// (A & C1) ^ B
2062///
2063/// when the XOR of the two constants is "all ones" (-1).
2064Instruction *InstCombiner::FoldXorWithConstants(BinaryOperator &I, Value *Op,
2065 Value *A, Value *B, Value *C) {
2066 ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
2067 if (!CI1)
2068 return nullptr;
2069
2070 Value *V1 = nullptr;
2071 ConstantInt *CI2 = nullptr;
2072 if (!match(Op, m_And(m_Value(V1), m_ConstantInt(CI2))))
2073 return nullptr;
2074
2075 APInt Xor = CI1->getValue() ^ CI2->getValue();
2076 if (!Xor.isAllOnesValue())
2077 return nullptr;
2078
2079 if (V1 == A || V1 == B) {
2080 Value *NewOp = Builder->CreateAnd(V1 == A ? B : A, CI1);
2081 return BinaryOperator::CreateXor(NewOp, V1);
2082 }
2083
2084 return nullptr;
2085}
2086
Chris Lattner0a8191e2010-01-05 07:50:36 +00002087Instruction *InstCombiner::visitOr(BinaryOperator &I) {
Duncan Sands641baf12010-11-13 15:10:37 +00002088 bool Changed = SimplifyAssociativeOrCommutative(I);
Chris Lattner0a8191e2010-01-05 07:50:36 +00002089 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2090
Serge Pavlov9ef66a82014-05-11 08:46:12 +00002091 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002092 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00002093
Justin Bogner99798402016-08-05 01:06:44 +00002094 if (Value *V = SimplifyOrInst(Op0, Op1, DL, &TLI, &DT, &AC))
Sanjay Patel4b198802016-02-01 22:23:39 +00002095 return replaceInstUsesWith(I, V);
Bill Wendlingaf13d822010-03-03 00:35:56 +00002096
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00002097 // (A&B)|(A&C) -> A&(B|C) etc
2098 if (Value *V = SimplifyUsingDistributiveLaws(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002099 return replaceInstUsesWith(I, V);
Duncan Sandsadc7771f2010-11-23 14:23:47 +00002100
Craig Topper9d4171a2012-12-20 07:09:41 +00002101 // See if we can simplify any instructions used by the instruction whose sole
Chris Lattner0a8191e2010-01-05 07:50:36 +00002102 // purpose is to compute bits we don't care about.
2103 if (SimplifyDemandedInstructionBits(I))
2104 return &I;
2105
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00002106 if (Value *V = SimplifyBSwap(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002107 return replaceInstUsesWith(I, V);
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00002108
Chris Lattner0a8191e2010-01-05 07:50:36 +00002109 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
Craig Topperf40110f2014-04-25 05:29:35 +00002110 ConstantInt *C1 = nullptr; Value *X = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002111 // (X & C1) | C2 --> (X | C2) & (C1|C2)
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002112 // iff (C1 & C2) == 0.
Chris Lattner0a8191e2010-01-05 07:50:36 +00002113 if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) &&
Bill Wendlingaf13d822010-03-03 00:35:56 +00002114 (RHS->getValue() & C1->getValue()) != 0 &&
Chris Lattner0a8191e2010-01-05 07:50:36 +00002115 Op0->hasOneUse()) {
2116 Value *Or = Builder->CreateOr(X, RHS);
2117 Or->takeName(Op0);
Craig Topper9d4171a2012-12-20 07:09:41 +00002118 return BinaryOperator::CreateAnd(Or,
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002119 Builder->getInt(RHS->getValue() | C1->getValue()));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002120 }
2121
2122 // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
2123 if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) &&
2124 Op0->hasOneUse()) {
2125 Value *Or = Builder->CreateOr(X, RHS);
2126 Or->takeName(Op0);
2127 return BinaryOperator::CreateXor(Or,
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002128 Builder->getInt(C1->getValue() & ~RHS->getValue()));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002129 }
2130
2131 // Try to fold constant and into select arguments.
2132 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
2133 if (Instruction *R = FoldOpIntoSelect(I, SI))
2134 return R;
Bill Wendlingaf13d822010-03-03 00:35:56 +00002135
Chris Lattner0a8191e2010-01-05 07:50:36 +00002136 if (isa<PHINode>(Op0))
2137 if (Instruction *NV = FoldOpIntoPhi(I))
2138 return NV;
2139 }
2140
Chad Rosiere5819e22016-05-26 14:58:51 +00002141 // Given an OR instruction, check to see if this is a bswap.
2142 if (Instruction *BSwap = MatchBSwap(I))
2143 return BSwap;
2144
Craig Topperf40110f2014-04-25 05:29:35 +00002145 Value *A = nullptr, *B = nullptr;
2146 ConstantInt *C1 = nullptr, *C2 = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002147
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002148 // (X^C)|Y -> (X|Y)^C iff Y&C == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +00002149 if (Op0->hasOneUse() &&
2150 match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
Hal Finkel60db0582014-09-07 18:57:58 +00002151 MaskedValueIsZero(Op1, C1->getValue(), 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00002152 Value *NOr = Builder->CreateOr(A, Op1);
2153 NOr->takeName(Op0);
2154 return BinaryOperator::CreateXor(NOr, C1);
2155 }
2156
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002157 // Y|(X^C) -> (X|Y)^C iff Y&C == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +00002158 if (Op1->hasOneUse() &&
2159 match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
Hal Finkel60db0582014-09-07 18:57:58 +00002160 MaskedValueIsZero(Op0, C1->getValue(), 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00002161 Value *NOr = Builder->CreateOr(A, Op0);
2162 NOr->takeName(Op0);
2163 return BinaryOperator::CreateXor(NOr, C1);
2164 }
2165
Suyog Sardad64faf62014-07-22 18:09:41 +00002166 // ((~A & B) | A) -> (A | B)
2167 if (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
2168 match(Op1, m_Specific(A)))
2169 return BinaryOperator::CreateOr(A, B);
2170
2171 // ((A & B) | ~A) -> (~A | B)
2172 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2173 match(Op1, m_Not(m_Specific(A))))
2174 return BinaryOperator::CreateOr(Builder->CreateNot(A), B);
2175
Suyog Sarda52324c82014-08-01 04:50:31 +00002176 // (A & (~B)) | (A ^ B) -> (A ^ B)
2177 if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
2178 match(Op1, m_Xor(m_Specific(A), m_Specific(B))))
2179 return BinaryOperator::CreateXor(A, B);
2180
2181 // (A ^ B) | ( A & (~B)) -> (A ^ B)
2182 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
2183 match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B)))))
2184 return BinaryOperator::CreateXor(A, B);
2185
Chris Lattner0a8191e2010-01-05 07:50:36 +00002186 // (A & C)|(B & D)
Craig Topperf40110f2014-04-25 05:29:35 +00002187 Value *C = nullptr, *D = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002188 if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
2189 match(Op1, m_And(m_Value(B), m_Value(D)))) {
Craig Topperf40110f2014-04-25 05:29:35 +00002190 Value *V1 = nullptr, *V2 = nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002191 C1 = dyn_cast<ConstantInt>(C);
2192 C2 = dyn_cast<ConstantInt>(D);
2193 if (C1 && C2) { // (A & C1)|(B & C2)
Chris Lattner0a8191e2010-01-05 07:50:36 +00002194 if ((C1->getValue() & C2->getValue()) == 0) {
Chris Lattner95188692010-01-11 06:55:24 +00002195 // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002196 // iff (C1&C2) == 0 and (N&~C1) == 0
Chris Lattner0a8191e2010-01-05 07:50:36 +00002197 if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
Hal Finkel60db0582014-09-07 18:57:58 +00002198 ((V1 == B &&
2199 MaskedValueIsZero(V2, ~C1->getValue(), 0, &I)) || // (V|N)
2200 (V2 == B &&
2201 MaskedValueIsZero(V1, ~C1->getValue(), 0, &I)))) // (N|V)
Chris Lattner0a8191e2010-01-05 07:50:36 +00002202 return BinaryOperator::CreateAnd(A,
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002203 Builder->getInt(C1->getValue()|C2->getValue()));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002204 // Or commutes, try both ways.
2205 if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
Hal Finkel60db0582014-09-07 18:57:58 +00002206 ((V1 == A &&
2207 MaskedValueIsZero(V2, ~C2->getValue(), 0, &I)) || // (V|N)
2208 (V2 == A &&
2209 MaskedValueIsZero(V1, ~C2->getValue(), 0, &I)))) // (N|V)
Chris Lattner0a8191e2010-01-05 07:50:36 +00002210 return BinaryOperator::CreateAnd(B,
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002211 Builder->getInt(C1->getValue()|C2->getValue()));
Craig Topper9d4171a2012-12-20 07:09:41 +00002212
Chris Lattner95188692010-01-11 06:55:24 +00002213 // ((V|C3)&C1) | ((V|C4)&C2) --> (V|C3|C4)&(C1|C2)
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002214 // iff (C1&C2) == 0 and (C3&~C1) == 0 and (C4&~C2) == 0.
Craig Topperf40110f2014-04-25 05:29:35 +00002215 ConstantInt *C3 = nullptr, *C4 = nullptr;
Chris Lattner95188692010-01-11 06:55:24 +00002216 if (match(A, m_Or(m_Value(V1), m_ConstantInt(C3))) &&
2217 (C3->getValue() & ~C1->getValue()) == 0 &&
2218 match(B, m_Or(m_Specific(V1), m_ConstantInt(C4))) &&
2219 (C4->getValue() & ~C2->getValue()) == 0) {
2220 V2 = Builder->CreateOr(V1, ConstantExpr::getOr(C3, C4), "bitfield");
2221 return BinaryOperator::CreateAnd(V2,
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002222 Builder->getInt(C1->getValue()|C2->getValue()));
Chris Lattner95188692010-01-11 06:55:24 +00002223 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002224 }
2225 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002226
Sanjay Patelf4a08ed2016-07-08 20:53:29 +00002227 // Don't try to form a select if it's unlikely that we'll get rid of at
2228 // least one of the operands. A select is generally more expensive than the
2229 // 'or' that it is replacing.
2230 if (Op0->hasOneUse() || Op1->hasOneUse()) {
2231 // (Cond & C) | (~Cond & D) -> Cond ? C : D, and commuted variants.
2232 if (Value *V = matchSelectFromAndOr(A, C, B, D, *Builder))
2233 return replaceInstUsesWith(I, V);
2234 if (Value *V = matchSelectFromAndOr(A, C, D, B, *Builder))
2235 return replaceInstUsesWith(I, V);
2236 if (Value *V = matchSelectFromAndOr(C, A, B, D, *Builder))
2237 return replaceInstUsesWith(I, V);
2238 if (Value *V = matchSelectFromAndOr(C, A, D, B, *Builder))
2239 return replaceInstUsesWith(I, V);
2240 if (Value *V = matchSelectFromAndOr(B, D, A, C, *Builder))
2241 return replaceInstUsesWith(I, V);
2242 if (Value *V = matchSelectFromAndOr(B, D, C, A, *Builder))
2243 return replaceInstUsesWith(I, V);
2244 if (Value *V = matchSelectFromAndOr(D, B, A, C, *Builder))
2245 return replaceInstUsesWith(I, V);
2246 if (Value *V = matchSelectFromAndOr(D, B, C, A, *Builder))
2247 return replaceInstUsesWith(I, V);
2248 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002249
2250 // ((A&~B)|(~A&B)) -> A^B
2251 if ((match(C, m_Not(m_Specific(D))) &&
2252 match(B, m_Not(m_Specific(A)))))
2253 return BinaryOperator::CreateXor(A, D);
2254 // ((~B&A)|(~A&B)) -> A^B
2255 if ((match(A, m_Not(m_Specific(D))) &&
2256 match(B, m_Not(m_Specific(C)))))
2257 return BinaryOperator::CreateXor(C, D);
2258 // ((A&~B)|(B&~A)) -> A^B
2259 if ((match(C, m_Not(m_Specific(B))) &&
2260 match(D, m_Not(m_Specific(A)))))
2261 return BinaryOperator::CreateXor(A, B);
2262 // ((~B&A)|(B&~A)) -> A^B
2263 if ((match(A, m_Not(m_Specific(B))) &&
2264 match(D, m_Not(m_Specific(C)))))
2265 return BinaryOperator::CreateXor(C, B);
Benjamin Kramer11743242010-07-12 13:34:22 +00002266
2267 // ((A|B)&1)|(B&-2) -> (A&1) | B
2268 if (match(A, m_Or(m_Value(V1), m_Specific(B))) ||
2269 match(A, m_Or(m_Specific(B), m_Value(V1)))) {
2270 Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C);
2271 if (Ret) return Ret;
2272 }
2273 // (B&-2)|((A|B)&1) -> (A&1) | B
2274 if (match(B, m_Or(m_Specific(A), m_Value(V1))) ||
2275 match(B, m_Or(m_Value(V1), m_Specific(A)))) {
2276 Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D);
2277 if (Ret) return Ret;
2278 }
David Majnemer5d1aeba2014-08-21 05:14:48 +00002279 // ((A^B)&1)|(B&-2) -> (A&1) ^ B
2280 if (match(A, m_Xor(m_Value(V1), m_Specific(B))) ||
2281 match(A, m_Xor(m_Specific(B), m_Value(V1)))) {
2282 Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C);
2283 if (Ret) return Ret;
2284 }
2285 // (B&-2)|((A^B)&1) -> (A&1) ^ B
2286 if (match(B, m_Xor(m_Specific(A), m_Value(V1))) ||
2287 match(B, m_Xor(m_Value(V1), m_Specific(A)))) {
2288 Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D);
2289 if (Ret) return Ret;
2290 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002291 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002292
David Majnemer42af3602014-07-30 21:26:37 +00002293 // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
2294 if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
2295 if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
2296 if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
2297 return BinaryOperator::CreateOr(Op0, C);
2298
2299 // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
2300 if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
2301 if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
2302 if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
2303 return BinaryOperator::CreateOr(Op1, C);
2304
David Majnemerf1eda232014-08-14 06:41:38 +00002305 // ((B | C) & A) | B -> B | (A & C)
2306 if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
2307 return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C));
2308
Sanjay Patelb54e62f2015-09-08 20:14:13 +00002309 if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
2310 return DeMorgan;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002311
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002312 // Canonicalize xor to the RHS.
Eli Friedmane06535b2012-03-16 00:52:42 +00002313 bool SwappedForXor = false;
2314 if (match(Op0, m_Xor(m_Value(), m_Value()))) {
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002315 std::swap(Op0, Op1);
Eli Friedmane06535b2012-03-16 00:52:42 +00002316 SwappedForXor = true;
2317 }
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002318
2319 // A | ( A ^ B) -> A | B
2320 // A | (~A ^ B) -> A | ~B
Chad Rosier7813dce2012-04-26 23:29:14 +00002321 // (A & B) | (A ^ B)
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002322 if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
2323 if (Op0 == A || Op0 == B)
2324 return BinaryOperator::CreateOr(A, B);
2325
Chad Rosier7813dce2012-04-26 23:29:14 +00002326 if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
2327 match(Op0, m_And(m_Specific(B), m_Specific(A))))
2328 return BinaryOperator::CreateOr(A, B);
2329
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002330 if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
2331 Value *Not = Builder->CreateNot(B, B->getName()+".not");
2332 return BinaryOperator::CreateOr(Not, Op0);
2333 }
2334 if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
2335 Value *Not = Builder->CreateNot(A, A->getName()+".not");
2336 return BinaryOperator::CreateOr(Not, Op0);
2337 }
2338 }
2339
2340 // A | ~(A | B) -> A | ~B
2341 // A | ~(A ^ B) -> A | ~B
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002342 if (match(Op1, m_Not(m_Value(A))))
2343 if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
Benjamin Kramer5b7a4e02011-02-20 15:20:01 +00002344 if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
2345 Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
2346 B->getOpcode() == Instruction::Xor)) {
2347 Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
2348 B->getOperand(0);
2349 Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not");
2350 return BinaryOperator::CreateOr(Not, Op0);
2351 }
Benjamin Kramerd5d7f372011-02-20 13:23:43 +00002352
Suyog Sarda16d64652014-08-01 04:41:43 +00002353 // (A & B) | ((~A) ^ B) -> (~A ^ B)
2354 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
2355 match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B))))
2356 return BinaryOperator::CreateXor(Builder->CreateNot(A), B);
2357
2358 // ((~A) ^ B) | (A & B) -> (~A ^ B)
2359 if (match(Op0, m_Xor(m_Not(m_Value(A)), m_Value(B))) &&
2360 match(Op1, m_And(m_Specific(A), m_Specific(B))))
2361 return BinaryOperator::CreateXor(Builder->CreateNot(A), B);
2362
Eli Friedmane06535b2012-03-16 00:52:42 +00002363 if (SwappedForXor)
2364 std::swap(Op0, Op1);
2365
David Majnemer3d6f80b2014-11-28 19:58:29 +00002366 {
2367 ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
2368 ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
2369 if (LHS && RHS)
Hal Finkel60db0582014-09-07 18:57:58 +00002370 if (Value *Res = FoldOrOfICmps(LHS, RHS, &I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002371 return replaceInstUsesWith(I, Res);
Craig Topper9d4171a2012-12-20 07:09:41 +00002372
David Majnemer3d6f80b2014-11-28 19:58:29 +00002373 // TODO: Make this recursive; it's a little tricky because an arbitrary
2374 // number of 'or' instructions might have to be created.
2375 Value *X, *Y;
2376 if (LHS && match(Op1, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2377 if (auto *Cmp = dyn_cast<ICmpInst>(X))
2378 if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002379 return replaceInstUsesWith(I, Builder->CreateOr(Res, Y));
David Majnemer3d6f80b2014-11-28 19:58:29 +00002380 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2381 if (Value *Res = FoldOrOfICmps(LHS, Cmp, &I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002382 return replaceInstUsesWith(I, Builder->CreateOr(Res, X));
David Majnemer3d6f80b2014-11-28 19:58:29 +00002383 }
2384 if (RHS && match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
2385 if (auto *Cmp = dyn_cast<ICmpInst>(X))
2386 if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002387 return replaceInstUsesWith(I, Builder->CreateOr(Res, Y));
David Majnemer3d6f80b2014-11-28 19:58:29 +00002388 if (auto *Cmp = dyn_cast<ICmpInst>(Y))
2389 if (Value *Res = FoldOrOfICmps(Cmp, RHS, &I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002390 return replaceInstUsesWith(I, Builder->CreateOr(Res, X));
David Majnemer3d6f80b2014-11-28 19:58:29 +00002391 }
2392 }
2393
Chris Lattner4e8137d2010-02-11 06:26:33 +00002394 // (fcmp uno x, c) | (fcmp uno y, c) -> (fcmp uno x, y)
2395 if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
2396 if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
Chris Lattner067459c2010-03-05 08:46:26 +00002397 if (Value *Res = FoldOrOfFCmps(LHS, RHS))
Sanjay Patel4b198802016-02-01 22:23:39 +00002398 return replaceInstUsesWith(I, Res);
Craig Topper9d4171a2012-12-20 07:09:41 +00002399
Sanjay Patel75b4ae22016-02-23 23:56:23 +00002400 if (Instruction *CastedOr = foldCastedBitwiseLogic(I))
2401 return CastedOr;
Eli Friedman23956262011-04-14 22:41:27 +00002402
Sanjay Patelcbfca9e2016-07-08 17:01:15 +00002403 // or(sext(A), B) / or(B, sext(A)) --> A ? -1 : B, where A is i1 or <N x i1>.
Sanjay Patel1b6b8242016-07-08 17:26:47 +00002404 if (match(Op0, m_OneUse(m_SExt(m_Value(A)))) &&
Sanjay Patelcbfca9e2016-07-08 17:01:15 +00002405 A->getType()->getScalarType()->isIntegerTy(1))
Eli Friedman23956262011-04-14 22:41:27 +00002406 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
Sanjay Patel1b6b8242016-07-08 17:26:47 +00002407 if (match(Op1, m_OneUse(m_SExt(m_Value(A)))) &&
Sanjay Patelcbfca9e2016-07-08 17:01:15 +00002408 A->getType()->getScalarType()->isIntegerTy(1))
Eli Friedman23956262011-04-14 22:41:27 +00002409 return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
2410
Owen Andersonc237a842010-09-13 17:59:27 +00002411 // Note: If we've gotten to the point of visiting the outer OR, then the
2412 // inner one couldn't be simplified. If it was a constant, then it won't
2413 // be simplified by a later pass either, so we try swapping the inner/outer
2414 // ORs in the hopes that we'll be able to simplify it this way.
2415 // (X|C) | V --> (X|V) | C
2416 if (Op0->hasOneUse() && !isa<ConstantInt>(Op1) &&
2417 match(Op0, m_Or(m_Value(A), m_ConstantInt(C1)))) {
2418 Value *Inner = Builder->CreateOr(A, Op1);
2419 Inner->takeName(Op0);
2420 return BinaryOperator::CreateOr(Inner, C1);
2421 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002422
Bill Wendling23242092013-02-16 23:41:36 +00002423 // Change (or (bool?A:B),(bool?C:D)) --> (bool?(or A,C):(or B,D))
2424 // Since this OR statement hasn't been optimized further yet, we hope
2425 // that this transformation will allow the new ORs to be optimized.
2426 {
Craig Topperf40110f2014-04-25 05:29:35 +00002427 Value *X = nullptr, *Y = nullptr;
Bill Wendling23242092013-02-16 23:41:36 +00002428 if (Op0->hasOneUse() && Op1->hasOneUse() &&
2429 match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
2430 match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
2431 Value *orTrue = Builder->CreateOr(A, C);
2432 Value *orFalse = Builder->CreateOr(B, D);
2433 return SelectInst::Create(X, orTrue, orFalse);
2434 }
2435 }
2436
Craig Topperf40110f2014-04-25 05:29:35 +00002437 return Changed ? &I : nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002438}
2439
2440Instruction *InstCombiner::visitXor(BinaryOperator &I) {
Duncan Sands641baf12010-11-13 15:10:37 +00002441 bool Changed = SimplifyAssociativeOrCommutative(I);
Chris Lattner0a8191e2010-01-05 07:50:36 +00002442 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2443
Serge Pavlov9ef66a82014-05-11 08:46:12 +00002444 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002445 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00002446
Justin Bogner99798402016-08-05 01:06:44 +00002447 if (Value *V = SimplifyXorInst(Op0, Op1, DL, &TLI, &DT, &AC))
Sanjay Patel4b198802016-02-01 22:23:39 +00002448 return replaceInstUsesWith(I, V);
Chris Lattner0a8191e2010-01-05 07:50:36 +00002449
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00002450 // (A&B)^(A&C) -> A&(B^C) etc
2451 if (Value *V = SimplifyUsingDistributiveLaws(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002452 return replaceInstUsesWith(I, V);
Duncan Sandsadc7771f2010-11-23 14:23:47 +00002453
Craig Topper9d4171a2012-12-20 07:09:41 +00002454 // See if we can simplify any instructions used by the instruction whose sole
Chris Lattner0a8191e2010-01-05 07:50:36 +00002455 // purpose is to compute bits we don't care about.
2456 if (SimplifyDemandedInstructionBits(I))
2457 return &I;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002458
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00002459 if (Value *V = SimplifyBSwap(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00002460 return replaceInstUsesWith(I, V);
Simon Pilgrimbe24ab32014-12-04 09:44:01 +00002461
Chris Lattner0a8191e2010-01-05 07:50:36 +00002462 // Is this a ~ operation?
2463 if (Value *NotOp = dyn_castNotVal(&I)) {
2464 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) {
Craig Topper9d4171a2012-12-20 07:09:41 +00002465 if (Op0I->getOpcode() == Instruction::And ||
Chris Lattner0a8191e2010-01-05 07:50:36 +00002466 Op0I->getOpcode() == Instruction::Or) {
2467 // ~(~X & Y) --> (X | ~Y) - De Morgan's Law
2468 // ~(~X | Y) === (X & ~Y) - De Morgan's Law
2469 if (dyn_castNotVal(Op0I->getOperand(1)))
2470 Op0I->swapOperands();
2471 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) {
2472 Value *NotY =
2473 Builder->CreateNot(Op0I->getOperand(1),
2474 Op0I->getOperand(1)->getName()+".not");
2475 if (Op0I->getOpcode() == Instruction::And)
2476 return BinaryOperator::CreateOr(Op0NotVal, NotY);
2477 return BinaryOperator::CreateAnd(Op0NotVal, NotY);
2478 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002479
Chris Lattner0a8191e2010-01-05 07:50:36 +00002480 // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
2481 // ~(X | Y) === (~X & ~Y) - De Morgan's Law
Sanjoy Das82ea3d42015-02-24 00:08:41 +00002482 if (IsFreeToInvert(Op0I->getOperand(0),
2483 Op0I->getOperand(0)->hasOneUse()) &&
2484 IsFreeToInvert(Op0I->getOperand(1),
2485 Op0I->getOperand(1)->hasOneUse())) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00002486 Value *NotX =
2487 Builder->CreateNot(Op0I->getOperand(0), "notlhs");
2488 Value *NotY =
2489 Builder->CreateNot(Op0I->getOperand(1), "notrhs");
2490 if (Op0I->getOpcode() == Instruction::And)
2491 return BinaryOperator::CreateOr(NotX, NotY);
2492 return BinaryOperator::CreateAnd(NotX, NotY);
2493 }
Chris Lattner18f49ce2010-01-19 18:16:19 +00002494
2495 } else if (Op0I->getOpcode() == Instruction::AShr) {
2496 // ~(~X >>s Y) --> (X >>s Y)
2497 if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0)))
2498 return BinaryOperator::CreateAShr(Op0NotVal, Op0I->getOperand(1));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002499 }
2500 }
2501 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002502
Benjamin Kramer443c7962015-02-12 20:26:46 +00002503 if (Constant *RHS = dyn_cast<Constant>(Op1)) {
2504 if (RHS->isAllOnesValue() && Op0->hasOneUse())
Chris Lattner0a8191e2010-01-05 07:50:36 +00002505 // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
Dan Gohman0a8175d2010-04-09 14:53:59 +00002506 if (CmpInst *CI = dyn_cast<CmpInst>(Op0))
2507 return CmpInst::Create(CI->getOpcode(),
2508 CI->getInversePredicate(),
2509 CI->getOperand(0), CI->getOperand(1));
Benjamin Kramer443c7962015-02-12 20:26:46 +00002510 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002511
Benjamin Kramer443c7962015-02-12 20:26:46 +00002512 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00002513 // fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp).
2514 if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) {
2515 if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) {
2516 if (CI->hasOneUse() && Op0C->hasOneUse()) {
2517 Instruction::CastOps Opcode = Op0C->getOpcode();
2518 if ((Opcode == Instruction::ZExt || Opcode == Instruction::SExt) &&
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002519 (RHS == ConstantExpr::getCast(Opcode, Builder->getTrue(),
Chris Lattner0a8191e2010-01-05 07:50:36 +00002520 Op0C->getDestTy()))) {
2521 CI->setPredicate(CI->getInversePredicate());
2522 return CastInst::Create(Opcode, CI, Op0C->getType());
2523 }
2524 }
2525 }
2526 }
2527
2528 if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
2529 // ~(c-X) == X-c-1 == X+(-c-1)
2530 if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
2531 if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
2532 Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
2533 Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C,
2534 ConstantInt::get(I.getType(), 1));
2535 return BinaryOperator::CreateAdd(Op0I->getOperand(1), ConstantRHS);
2536 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002537
Chris Lattner0a8191e2010-01-05 07:50:36 +00002538 if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
2539 if (Op0I->getOpcode() == Instruction::Add) {
2540 // ~(X-c) --> (-c-1)-X
2541 if (RHS->isAllOnesValue()) {
2542 Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
2543 return BinaryOperator::CreateSub(
2544 ConstantExpr::getSub(NegOp0CI,
2545 ConstantInt::get(I.getType(), 1)),
2546 Op0I->getOperand(0));
2547 } else if (RHS->getValue().isSignBit()) {
2548 // (X + C) ^ signbit -> (X + C + signbit)
Jakub Staszak461d1fe2013-06-06 00:37:23 +00002549 Constant *C = Builder->getInt(RHS->getValue() + Op0CI->getValue());
Chris Lattner0a8191e2010-01-05 07:50:36 +00002550 return BinaryOperator::CreateAdd(Op0I->getOperand(0), C);
2551
2552 }
2553 } else if (Op0I->getOpcode() == Instruction::Or) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00002554 // (X|C1)^C2 -> X^(C1|C2) iff X&~C1 == 0
Hal Finkel60db0582014-09-07 18:57:58 +00002555 if (MaskedValueIsZero(Op0I->getOperand(0), Op0CI->getValue(),
2556 0, &I)) {
Chris Lattner0a8191e2010-01-05 07:50:36 +00002557 Constant *NewRHS = ConstantExpr::getOr(Op0CI, RHS);
2558 // Anything in both C1 and C2 is known to be zero, remove it from
2559 // NewRHS.
2560 Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHS);
Craig Topper9d4171a2012-12-20 07:09:41 +00002561 NewRHS = ConstantExpr::getAnd(NewRHS,
Chris Lattner0a8191e2010-01-05 07:50:36 +00002562 ConstantExpr::getNot(CommonBits));
2563 Worklist.Add(Op0I);
2564 I.setOperand(0, Op0I->getOperand(0));
2565 I.setOperand(1, NewRHS);
2566 return &I;
2567 }
Shuxin Yang6ea79e82012-11-26 21:44:25 +00002568 } else if (Op0I->getOpcode() == Instruction::LShr) {
2569 // ((X^C1) >> C2) ^ C3 -> (X>>C2) ^ ((C1>>C2)^C3)
2570 // E1 = "X ^ C1"
Craig Topper9d4171a2012-12-20 07:09:41 +00002571 BinaryOperator *E1;
Shuxin Yang6ea79e82012-11-26 21:44:25 +00002572 ConstantInt *C1;
2573 if (Op0I->hasOneUse() &&
2574 (E1 = dyn_cast<BinaryOperator>(Op0I->getOperand(0))) &&
2575 E1->getOpcode() == Instruction::Xor &&
2576 (C1 = dyn_cast<ConstantInt>(E1->getOperand(1)))) {
2577 // fold (C1 >> C2) ^ C3
2578 ConstantInt *C2 = Op0CI, *C3 = RHS;
2579 APInt FoldConst = C1->getValue().lshr(C2->getValue());
2580 FoldConst ^= C3->getValue();
2581 // Prepare the two operands.
2582 Value *Opnd0 = Builder->CreateLShr(E1->getOperand(0), C2);
2583 Opnd0->takeName(Op0I);
2584 cast<Instruction>(Opnd0)->setDebugLoc(I.getDebugLoc());
2585 Value *FoldVal = ConstantInt::get(Opnd0->getType(), FoldConst);
2586
2587 return BinaryOperator::CreateXor(Opnd0, FoldVal);
2588 }
Chris Lattner0a8191e2010-01-05 07:50:36 +00002589 }
2590 }
2591 }
2592
2593 // Try to fold constant and into select arguments.
2594 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
2595 if (Instruction *R = FoldOpIntoSelect(I, SI))
2596 return R;
2597 if (isa<PHINode>(Op0))
2598 if (Instruction *NV = FoldOpIntoPhi(I))
2599 return NV;
2600 }
2601
Chris Lattner0a8191e2010-01-05 07:50:36 +00002602 BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1);
2603 if (Op1I) {
2604 Value *A, *B;
2605 if (match(Op1I, m_Or(m_Value(A), m_Value(B)))) {
2606 if (A == Op0) { // B^(B|A) == (A|B)^B
2607 Op1I->swapOperands();
2608 I.swapOperands();
2609 std::swap(Op0, Op1);
2610 } else if (B == Op0) { // B^(A|B) == (A|B)^B
2611 I.swapOperands(); // Simplified below.
2612 std::swap(Op0, Op1);
2613 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002614 } else if (match(Op1I, m_And(m_Value(A), m_Value(B))) &&
Chris Lattner0a8191e2010-01-05 07:50:36 +00002615 Op1I->hasOneUse()){
2616 if (A == Op0) { // A^(A&B) -> A^(B&A)
2617 Op1I->swapOperands();
2618 std::swap(A, B);
2619 }
2620 if (B == Op0) { // A^(B&A) -> (B&A)^A
2621 I.swapOperands(); // Simplified below.
2622 std::swap(Op0, Op1);
2623 }
2624 }
2625 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002626
Chris Lattner0a8191e2010-01-05 07:50:36 +00002627 BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0);
2628 if (Op0I) {
2629 Value *A, *B;
2630 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) &&
2631 Op0I->hasOneUse()) {
2632 if (A == Op1) // (B|A)^B == (A|B)^B
2633 std::swap(A, B);
2634 if (B == Op1) // (A|B)^B == A & ~B
Benjamin Kramer547b6c52011-09-27 20:39:19 +00002635 return BinaryOperator::CreateAnd(A, Builder->CreateNot(Op1));
Craig Topper9d4171a2012-12-20 07:09:41 +00002636 } else if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
Chris Lattner0a8191e2010-01-05 07:50:36 +00002637 Op0I->hasOneUse()){
2638 if (A == Op1) // (A&B)^A -> (B&A)^A
2639 std::swap(A, B);
2640 if (B == Op1 && // (B&A)^A == ~B & A
2641 !isa<ConstantInt>(Op1)) { // Canonical form is (B&C)^C
Benjamin Kramer547b6c52011-09-27 20:39:19 +00002642 return BinaryOperator::CreateAnd(Builder->CreateNot(A), Op1);
Chris Lattner0a8191e2010-01-05 07:50:36 +00002643 }
2644 }
2645 }
Craig Topper9d4171a2012-12-20 07:09:41 +00002646
Chris Lattner0a8191e2010-01-05 07:50:36 +00002647 if (Op0I && Op1I) {
2648 Value *A, *B, *C, *D;
2649 // (A & B)^(A | B) -> A ^ B
2650 if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
2651 match(Op1I, m_Or(m_Value(C), m_Value(D)))) {
Craig Topper9d4171a2012-12-20 07:09:41 +00002652 if ((A == C && B == D) || (A == D && B == C))
Chris Lattner0a8191e2010-01-05 07:50:36 +00002653 return BinaryOperator::CreateXor(A, B);
2654 }
2655 // (A | B)^(A & B) -> A ^ B
2656 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) &&
2657 match(Op1I, m_And(m_Value(C), m_Value(D)))) {
Craig Topper9d4171a2012-12-20 07:09:41 +00002658 if ((A == C && B == D) || (A == D && B == C))
Chris Lattner0a8191e2010-01-05 07:50:36 +00002659 return BinaryOperator::CreateXor(A, B);
2660 }
David Majnemer698dca02014-08-14 06:46:25 +00002661 // (A | ~B) ^ (~A | B) -> A ^ B
2662 if (match(Op0I, m_Or(m_Value(A), m_Not(m_Value(B)))) &&
2663 match(Op1I, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) {
2664 return BinaryOperator::CreateXor(A, B);
2665 }
2666 // (~A | B) ^ (A | ~B) -> A ^ B
2667 if (match(Op0I, m_Or(m_Not(m_Value(A)), m_Value(B))) &&
2668 match(Op1I, m_Or(m_Specific(A), m_Not(m_Specific(B))))) {
2669 return BinaryOperator::CreateXor(A, B);
2670 }
Mayur Pandey960507b2014-08-19 08:19:19 +00002671 // (A & ~B) ^ (~A & B) -> A ^ B
2672 if (match(Op0I, m_And(m_Value(A), m_Not(m_Value(B)))) &&
2673 match(Op1I, m_And(m_Not(m_Specific(A)), m_Specific(B)))) {
2674 return BinaryOperator::CreateXor(A, B);
2675 }
2676 // (~A & B) ^ (A & ~B) -> A ^ B
2677 if (match(Op0I, m_And(m_Not(m_Value(A)), m_Value(B))) &&
2678 match(Op1I, m_And(m_Specific(A), m_Not(m_Specific(B))))) {
2679 return BinaryOperator::CreateXor(A, B);
2680 }
David Majnemer6fe6ea72014-09-05 06:09:24 +00002681 // (A ^ C)^(A | B) -> ((~A) & B) ^ C
2682 if (match(Op0I, m_Xor(m_Value(D), m_Value(C))) &&
2683 match(Op1I, m_Or(m_Value(A), m_Value(B)))) {
2684 if (D == A)
2685 return BinaryOperator::CreateXor(
2686 Builder->CreateAnd(Builder->CreateNot(A), B), C);
2687 if (D == B)
2688 return BinaryOperator::CreateXor(
2689 Builder->CreateAnd(Builder->CreateNot(B), A), C);
Karthik Bhata4a4db92014-08-13 05:13:14 +00002690 }
David Majnemer6fe6ea72014-09-05 06:09:24 +00002691 // (A | B)^(A ^ C) -> ((~A) & B) ^ C
Karthik Bhata4a4db92014-08-13 05:13:14 +00002692 if (match(Op0I, m_Or(m_Value(A), m_Value(B))) &&
David Majnemer6fe6ea72014-09-05 06:09:24 +00002693 match(Op1I, m_Xor(m_Value(D), m_Value(C)))) {
2694 if (D == A)
2695 return BinaryOperator::CreateXor(
2696 Builder->CreateAnd(Builder->CreateNot(A), B), C);
2697 if (D == B)
2698 return BinaryOperator::CreateXor(
2699 Builder->CreateAnd(Builder->CreateNot(B), A), C);
Karthik Bhata4a4db92014-08-13 05:13:14 +00002700 }
Suyog Sardab60ec902014-07-22 18:30:54 +00002701 // (A & B) ^ (A ^ B) -> (A | B)
2702 if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
2703 match(Op1I, m_Xor(m_Specific(A), m_Specific(B))))
2704 return BinaryOperator::CreateOr(A, B);
2705 // (A ^ B) ^ (A & B) -> (A | B)
2706 if (match(Op0I, m_Xor(m_Value(A), m_Value(B))) &&
2707 match(Op1I, m_And(m_Specific(A), m_Specific(B))))
2708 return BinaryOperator::CreateOr(A, B);
Chris Lattner0a8191e2010-01-05 07:50:36 +00002709 }
Duncan Sandsadc7771f2010-11-23 14:23:47 +00002710
Suyog Sarda521237c2014-07-22 15:37:39 +00002711 Value *A = nullptr, *B = nullptr;
Suyog Sarda56c9a872014-08-01 05:07:20 +00002712 // (A & ~B) ^ (~A) -> ~(A & B)
2713 if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
2714 match(Op1, m_Not(m_Specific(A))))
2715 return BinaryOperator::CreateNot(Builder->CreateAnd(A, B));
2716
Chris Lattner0a8191e2010-01-05 07:50:36 +00002717 // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
2718 if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
2719 if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
2720 if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
2721 if (LHS->getOperand(0) == RHS->getOperand(1) &&
2722 LHS->getOperand(1) == RHS->getOperand(0))
2723 LHS->swapOperands();
2724 if (LHS->getOperand(0) == RHS->getOperand(0) &&
2725 LHS->getOperand(1) == RHS->getOperand(1)) {
2726 Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
2727 unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
2728 bool isSigned = LHS->isSigned() || RHS->isSigned();
Sanjay Patel4b198802016-02-01 22:23:39 +00002729 return replaceInstUsesWith(I,
Pete Cooperebf98c12011-12-17 01:20:32 +00002730 getNewICmpValue(isSigned, Code, Op0, Op1,
2731 Builder));
Chris Lattner0a8191e2010-01-05 07:50:36 +00002732 }
2733 }
2734
Sanjay Pateldbbaca02016-02-24 17:00:34 +00002735 if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
2736 return CastedXor;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002737
Craig Topperf40110f2014-04-25 05:29:35 +00002738 return Changed ? &I : nullptr;
Chris Lattner0a8191e2010-01-05 07:50:36 +00002739}