File: | lib/Transforms/InstCombine/InstCombineMulDivRem.cpp |
Warning: | line 824, column 14 Called C++ object pointer is null |
1 | //===- InstCombineMulDivRem.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 visit functions for mul, fmul, sdiv, udiv, fdiv, | |||
11 | // srem, urem, frem. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "InstCombineInternal.h" | |||
16 | #include "llvm/Analysis/InstructionSimplify.h" | |||
17 | #include "llvm/IR/IntrinsicInst.h" | |||
18 | #include "llvm/IR/PatternMatch.h" | |||
19 | using namespace llvm; | |||
20 | using namespace PatternMatch; | |||
21 | ||||
22 | #define DEBUG_TYPE"instcombine" "instcombine" | |||
23 | ||||
24 | ||||
25 | /// The specific integer value is used in a context where it is known to be | |||
26 | /// non-zero. If this allows us to simplify the computation, do so and return | |||
27 | /// the new operand, otherwise return null. | |||
28 | static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC, | |||
29 | Instruction &CxtI) { | |||
30 | // If V has multiple uses, then we would have to do more analysis to determine | |||
31 | // if this is safe. For example, the use could be in dynamically unreached | |||
32 | // code. | |||
33 | if (!V->hasOneUse()) return nullptr; | |||
34 | ||||
35 | bool MadeChange = false; | |||
36 | ||||
37 | // ((1 << A) >>u B) --> (1 << (A-B)) | |||
38 | // Because V cannot be zero, we know that B is less than A. | |||
39 | Value *A = nullptr, *B = nullptr, *One = nullptr; | |||
40 | if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) && | |||
41 | match(One, m_One())) { | |||
42 | A = IC.Builder->CreateSub(A, B); | |||
43 | return IC.Builder->CreateShl(One, A); | |||
44 | } | |||
45 | ||||
46 | // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it | |||
47 | // inexact. Similarly for <<. | |||
48 | BinaryOperator *I = dyn_cast<BinaryOperator>(V); | |||
49 | if (I && I->isLogicalShift() && | |||
50 | IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) { | |||
51 | // We know that this is an exact/nuw shift and that the input is a | |||
52 | // non-zero context as well. | |||
53 | if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) { | |||
54 | I->setOperand(0, V2); | |||
55 | MadeChange = true; | |||
56 | } | |||
57 | ||||
58 | if (I->getOpcode() == Instruction::LShr && !I->isExact()) { | |||
59 | I->setIsExact(); | |||
60 | MadeChange = true; | |||
61 | } | |||
62 | ||||
63 | if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { | |||
64 | I->setHasNoUnsignedWrap(); | |||
65 | MadeChange = true; | |||
66 | } | |||
67 | } | |||
68 | ||||
69 | // TODO: Lots more we could do here: | |||
70 | // If V is a phi node, we can call this on each of its operands. | |||
71 | // "select cond, X, 0" can simplify to "X". | |||
72 | ||||
73 | return MadeChange ? V : nullptr; | |||
74 | } | |||
75 | ||||
76 | ||||
77 | /// True if the multiply can not be expressed in an int this size. | |||
78 | static bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product, | |||
79 | bool IsSigned) { | |||
80 | bool Overflow; | |||
81 | if (IsSigned) | |||
82 | Product = C1.smul_ov(C2, Overflow); | |||
83 | else | |||
84 | Product = C1.umul_ov(C2, Overflow); | |||
85 | ||||
86 | return Overflow; | |||
87 | } | |||
88 | ||||
89 | /// \brief True if C2 is a multiple of C1. Quotient contains C2/C1. | |||
90 | static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, | |||
91 | bool IsSigned) { | |||
92 | assert(C1.getBitWidth() == C2.getBitWidth() &&((C1.getBitWidth() == C2.getBitWidth() && "Inconsistent width of constants!" ) ? static_cast<void> (0) : __assert_fail ("C1.getBitWidth() == C2.getBitWidth() && \"Inconsistent width of constants!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 93, __PRETTY_FUNCTION__)) | |||
93 | "Inconsistent width of constants!")((C1.getBitWidth() == C2.getBitWidth() && "Inconsistent width of constants!" ) ? static_cast<void> (0) : __assert_fail ("C1.getBitWidth() == C2.getBitWidth() && \"Inconsistent width of constants!\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 93, __PRETTY_FUNCTION__)); | |||
94 | ||||
95 | // Bail if we will divide by zero. | |||
96 | if (C2.isMinValue()) | |||
97 | return false; | |||
98 | ||||
99 | // Bail if we would divide INT_MIN by -1. | |||
100 | if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue()) | |||
101 | return false; | |||
102 | ||||
103 | APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned); | |||
104 | if (IsSigned) | |||
105 | APInt::sdivrem(C1, C2, Quotient, Remainder); | |||
106 | else | |||
107 | APInt::udivrem(C1, C2, Quotient, Remainder); | |||
108 | ||||
109 | return Remainder.isMinValue(); | |||
110 | } | |||
111 | ||||
112 | /// \brief A helper routine of InstCombiner::visitMul(). | |||
113 | /// | |||
114 | /// If C is a vector of known powers of 2, then this function returns | |||
115 | /// a new vector obtained from C replacing each element with its logBase2. | |||
116 | /// Return a null pointer otherwise. | |||
117 | static Constant *getLogBase2Vector(ConstantDataVector *CV) { | |||
118 | const APInt *IVal; | |||
119 | SmallVector<Constant *, 4> Elts; | |||
120 | ||||
121 | for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { | |||
122 | Constant *Elt = CV->getElementAsConstant(I); | |||
123 | if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) | |||
124 | return nullptr; | |||
125 | Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); | |||
126 | } | |||
127 | ||||
128 | return ConstantVector::get(Elts); | |||
129 | } | |||
130 | ||||
131 | /// \brief Return true if we can prove that: | |||
132 | /// (mul LHS, RHS) === (mul nsw LHS, RHS) | |||
133 | bool InstCombiner::willNotOverflowSignedMul(const Value *LHS, | |||
134 | const Value *RHS, | |||
135 | const Instruction &CxtI) const { | |||
136 | // Multiplying n * m significant bits yields a result of n + m significant | |||
137 | // bits. If the total number of significant bits does not exceed the | |||
138 | // result bit width (minus 1), there is no overflow. | |||
139 | // This means if we have enough leading sign bits in the operands | |||
140 | // we can guarantee that the result does not overflow. | |||
141 | // Ref: "Hacker's Delight" by Henry Warren | |||
142 | unsigned BitWidth = LHS->getType()->getScalarSizeInBits(); | |||
143 | ||||
144 | // Note that underestimating the number of sign bits gives a more | |||
145 | // conservative answer. | |||
146 | unsigned SignBits = | |||
147 | ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI); | |||
148 | ||||
149 | // First handle the easy case: if we have enough sign bits there's | |||
150 | // definitely no overflow. | |||
151 | if (SignBits > BitWidth + 1) | |||
152 | return true; | |||
153 | ||||
154 | // There are two ambiguous cases where there can be no overflow: | |||
155 | // SignBits == BitWidth + 1 and | |||
156 | // SignBits == BitWidth | |||
157 | // The second case is difficult to check, therefore we only handle the | |||
158 | // first case. | |||
159 | if (SignBits == BitWidth + 1) { | |||
160 | // It overflows only when both arguments are negative and the true | |||
161 | // product is exactly the minimum negative number. | |||
162 | // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000 | |||
163 | // For simplicity we just check if at least one side is not negative. | |||
164 | KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI); | |||
165 | KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI); | |||
166 | if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative()) | |||
167 | return true; | |||
168 | } | |||
169 | return false; | |||
170 | } | |||
171 | ||||
172 | Instruction *InstCombiner::visitMul(BinaryOperator &I) { | |||
173 | bool Changed = SimplifyAssociativeOrCommutative(I); | |||
174 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
175 | ||||
176 | if (Value *V = SimplifyVectorOp(I)) | |||
177 | return replaceInstUsesWith(I, V); | |||
178 | ||||
179 | if (Value *V = SimplifyMulInst(Op0, Op1, SQ.getWithInstruction(&I))) | |||
180 | return replaceInstUsesWith(I, V); | |||
181 | ||||
182 | if (Value *V = SimplifyUsingDistributiveLaws(I)) | |||
183 | return replaceInstUsesWith(I, V); | |||
184 | ||||
185 | // X * -1 == 0 - X | |||
186 | if (match(Op1, m_AllOnes())) { | |||
187 | BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName()); | |||
188 | if (I.hasNoSignedWrap()) | |||
189 | BO->setHasNoSignedWrap(); | |||
190 | return BO; | |||
191 | } | |||
192 | ||||
193 | // Also allow combining multiply instructions on vectors. | |||
194 | { | |||
195 | Value *NewOp; | |||
196 | Constant *C1, *C2; | |||
197 | const APInt *IVal; | |||
198 | if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), | |||
199 | m_Constant(C1))) && | |||
200 | match(C1, m_APInt(IVal))) { | |||
201 | // ((X << C2)*C1) == (X * (C1 << C2)) | |||
202 | Constant *Shl = ConstantExpr::getShl(C1, C2); | |||
203 | BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0)); | |||
204 | BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl); | |||
205 | if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap()) | |||
206 | BO->setHasNoUnsignedWrap(); | |||
207 | if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() && | |||
208 | Shl->isNotMinSignedValue()) | |||
209 | BO->setHasNoSignedWrap(); | |||
210 | return BO; | |||
211 | } | |||
212 | ||||
213 | if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { | |||
214 | Constant *NewCst = nullptr; | |||
215 | if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) | |||
216 | // Replace X*(2^C) with X << C, where C is either a scalar or a splat. | |||
217 | NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); | |||
218 | else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1)) | |||
219 | // Replace X*(2^C) with X << C, where C is a vector of known | |||
220 | // constant powers of 2. | |||
221 | NewCst = getLogBase2Vector(CV); | |||
222 | ||||
223 | if (NewCst) { | |||
224 | unsigned Width = NewCst->getType()->getPrimitiveSizeInBits(); | |||
225 | BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); | |||
226 | ||||
227 | if (I.hasNoUnsignedWrap()) | |||
228 | Shl->setHasNoUnsignedWrap(); | |||
229 | if (I.hasNoSignedWrap()) { | |||
230 | const APInt *V; | |||
231 | if (match(NewCst, m_APInt(V)) && *V != Width - 1) | |||
232 | Shl->setHasNoSignedWrap(); | |||
233 | } | |||
234 | ||||
235 | return Shl; | |||
236 | } | |||
237 | } | |||
238 | } | |||
239 | ||||
240 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { | |||
241 | // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n | |||
242 | // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n | |||
243 | // The "* (2**n)" thus becomes a potential shifting opportunity. | |||
244 | { | |||
245 | const APInt & Val = CI->getValue(); | |||
246 | const APInt &PosVal = Val.abs(); | |||
247 | if (Val.isNegative() && PosVal.isPowerOf2()) { | |||
248 | Value *X = nullptr, *Y = nullptr; | |||
249 | if (Op0->hasOneUse()) { | |||
250 | ConstantInt *C1; | |||
251 | Value *Sub = nullptr; | |||
252 | if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) | |||
253 | Sub = Builder->CreateSub(X, Y, "suba"); | |||
254 | else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) | |||
255 | Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); | |||
256 | if (Sub) | |||
257 | return | |||
258 | BinaryOperator::CreateMul(Sub, | |||
259 | ConstantInt::get(Y->getType(), PosVal)); | |||
260 | } | |||
261 | } | |||
262 | } | |||
263 | } | |||
264 | ||||
265 | // Simplify mul instructions with a constant RHS. | |||
266 | if (isa<Constant>(Op1)) { | |||
267 | if (Instruction *FoldedMul = foldOpWithConstantIntoOperand(I)) | |||
268 | return FoldedMul; | |||
269 | ||||
270 | // Canonicalize (X+C1)*CI -> X*CI+C1*CI. | |||
271 | { | |||
272 | Value *X; | |||
273 | Constant *C1; | |||
274 | if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) { | |||
275 | Value *Mul = Builder->CreateMul(C1, Op1); | |||
276 | // Only go forward with the transform if C1*CI simplifies to a tidier | |||
277 | // constant. | |||
278 | if (!match(Mul, m_Mul(m_Value(), m_Value()))) | |||
279 | return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1), Mul); | |||
280 | } | |||
281 | } | |||
282 | } | |||
283 | ||||
284 | if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y | |||
285 | if (Value *Op1v = dyn_castNegVal(Op1)) { | |||
286 | BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v); | |||
287 | if (I.hasNoSignedWrap() && | |||
288 | match(Op0, m_NSWSub(m_Value(), m_Value())) && | |||
289 | match(Op1, m_NSWSub(m_Value(), m_Value()))) | |||
290 | BO->setHasNoSignedWrap(); | |||
291 | return BO; | |||
292 | } | |||
293 | } | |||
294 | ||||
295 | // (X / Y) * Y = X - (X % Y) | |||
296 | // (X / Y) * -Y = (X % Y) - X | |||
297 | { | |||
298 | Value *Y = Op1; | |||
299 | BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0); | |||
300 | if (!Div || (Div->getOpcode() != Instruction::UDiv && | |||
301 | Div->getOpcode() != Instruction::SDiv)) { | |||
302 | Y = Op0; | |||
303 | Div = dyn_cast<BinaryOperator>(Op1); | |||
304 | } | |||
305 | Value *Neg = dyn_castNegVal(Y); | |||
306 | if (Div && Div->hasOneUse() && | |||
307 | (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) && | |||
308 | (Div->getOpcode() == Instruction::UDiv || | |||
309 | Div->getOpcode() == Instruction::SDiv)) { | |||
310 | Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1); | |||
311 | ||||
312 | // If the division is exact, X % Y is zero, so we end up with X or -X. | |||
313 | if (Div->isExact()) { | |||
314 | if (DivOp1 == Y) | |||
315 | return replaceInstUsesWith(I, X); | |||
316 | return BinaryOperator::CreateNeg(X); | |||
317 | } | |||
318 | ||||
319 | auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem | |||
320 | : Instruction::SRem; | |||
321 | Value *Rem = Builder->CreateBinOp(RemOpc, X, DivOp1); | |||
322 | if (DivOp1 == Y) | |||
323 | return BinaryOperator::CreateSub(X, Rem); | |||
324 | return BinaryOperator::CreateSub(Rem, X); | |||
325 | } | |||
326 | } | |||
327 | ||||
328 | /// i1 mul -> i1 and. | |||
329 | if (I.getType()->getScalarType()->isIntegerTy(1)) | |||
330 | return BinaryOperator::CreateAnd(Op0, Op1); | |||
331 | ||||
332 | // X*(1 << Y) --> X << Y | |||
333 | // (1 << Y)*X --> X << Y | |||
334 | { | |||
335 | Value *Y; | |||
336 | BinaryOperator *BO = nullptr; | |||
337 | bool ShlNSW = false; | |||
338 | if (match(Op0, m_Shl(m_One(), m_Value(Y)))) { | |||
339 | BO = BinaryOperator::CreateShl(Op1, Y); | |||
340 | ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap(); | |||
341 | } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) { | |||
342 | BO = BinaryOperator::CreateShl(Op0, Y); | |||
343 | ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap(); | |||
344 | } | |||
345 | if (BO) { | |||
346 | if (I.hasNoUnsignedWrap()) | |||
347 | BO->setHasNoUnsignedWrap(); | |||
348 | if (I.hasNoSignedWrap() && ShlNSW) | |||
349 | BO->setHasNoSignedWrap(); | |||
350 | return BO; | |||
351 | } | |||
352 | } | |||
353 | ||||
354 | // If one of the operands of the multiply is a cast from a boolean value, then | |||
355 | // we know the bool is either zero or one, so this is a 'masking' multiply. | |||
356 | // X * Y (where Y is 0 or 1) -> X & (0-Y) | |||
357 | if (!I.getType()->isVectorTy()) { | |||
358 | // -2 is "-1 << 1" so it is all bits set except the low one. | |||
359 | APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); | |||
360 | ||||
361 | Value *BoolCast = nullptr, *OtherOp = nullptr; | |||
362 | if (MaskedValueIsZero(Op0, Negative2, 0, &I)) { | |||
363 | BoolCast = Op0; | |||
364 | OtherOp = Op1; | |||
365 | } else if (MaskedValueIsZero(Op1, Negative2, 0, &I)) { | |||
366 | BoolCast = Op1; | |||
367 | OtherOp = Op0; | |||
368 | } | |||
369 | ||||
370 | if (BoolCast) { | |||
371 | Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), | |||
372 | BoolCast); | |||
373 | return BinaryOperator::CreateAnd(V, OtherOp); | |||
374 | } | |||
375 | } | |||
376 | ||||
377 | // Check for (mul (sext x), y), see if we can merge this into an | |||
378 | // integer mul followed by a sext. | |||
379 | if (SExtInst *Op0Conv = dyn_cast<SExtInst>(Op0)) { | |||
380 | // (mul (sext x), cst) --> (sext (mul x, cst')) | |||
381 | if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { | |||
382 | if (Op0Conv->hasOneUse()) { | |||
383 | Constant *CI = | |||
384 | ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType()); | |||
385 | if (ConstantExpr::getSExt(CI, I.getType()) == Op1C && | |||
386 | willNotOverflowSignedMul(Op0Conv->getOperand(0), CI, I)) { | |||
387 | // Insert the new, smaller mul. | |||
388 | Value *NewMul = | |||
389 | Builder->CreateNSWMul(Op0Conv->getOperand(0), CI, "mulconv"); | |||
390 | return new SExtInst(NewMul, I.getType()); | |||
391 | } | |||
392 | } | |||
393 | } | |||
394 | ||||
395 | // (mul (sext x), (sext y)) --> (sext (mul int x, y)) | |||
396 | if (SExtInst *Op1Conv = dyn_cast<SExtInst>(Op1)) { | |||
397 | // Only do this if x/y have the same type, if at last one of them has a | |||
398 | // single use (so we don't increase the number of sexts), and if the | |||
399 | // integer mul will not overflow. | |||
400 | if (Op0Conv->getOperand(0)->getType() == | |||
401 | Op1Conv->getOperand(0)->getType() && | |||
402 | (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) && | |||
403 | willNotOverflowSignedMul(Op0Conv->getOperand(0), | |||
404 | Op1Conv->getOperand(0), I)) { | |||
405 | // Insert the new integer mul. | |||
406 | Value *NewMul = Builder->CreateNSWMul( | |||
407 | Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv"); | |||
408 | return new SExtInst(NewMul, I.getType()); | |||
409 | } | |||
410 | } | |||
411 | } | |||
412 | ||||
413 | // Check for (mul (zext x), y), see if we can merge this into an | |||
414 | // integer mul followed by a zext. | |||
415 | if (auto *Op0Conv = dyn_cast<ZExtInst>(Op0)) { | |||
416 | // (mul (zext x), cst) --> (zext (mul x, cst')) | |||
417 | if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { | |||
418 | if (Op0Conv->hasOneUse()) { | |||
419 | Constant *CI = | |||
420 | ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType()); | |||
421 | if (ConstantExpr::getZExt(CI, I.getType()) == Op1C && | |||
422 | willNotOverflowUnsignedMul(Op0Conv->getOperand(0), CI, I)) { | |||
423 | // Insert the new, smaller mul. | |||
424 | Value *NewMul = | |||
425 | Builder->CreateNUWMul(Op0Conv->getOperand(0), CI, "mulconv"); | |||
426 | return new ZExtInst(NewMul, I.getType()); | |||
427 | } | |||
428 | } | |||
429 | } | |||
430 | ||||
431 | // (mul (zext x), (zext y)) --> (zext (mul int x, y)) | |||
432 | if (auto *Op1Conv = dyn_cast<ZExtInst>(Op1)) { | |||
433 | // Only do this if x/y have the same type, if at last one of them has a | |||
434 | // single use (so we don't increase the number of zexts), and if the | |||
435 | // integer mul will not overflow. | |||
436 | if (Op0Conv->getOperand(0)->getType() == | |||
437 | Op1Conv->getOperand(0)->getType() && | |||
438 | (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) && | |||
439 | willNotOverflowUnsignedMul(Op0Conv->getOperand(0), | |||
440 | Op1Conv->getOperand(0), I)) { | |||
441 | // Insert the new integer mul. | |||
442 | Value *NewMul = Builder->CreateNUWMul( | |||
443 | Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv"); | |||
444 | return new ZExtInst(NewMul, I.getType()); | |||
445 | } | |||
446 | } | |||
447 | } | |||
448 | ||||
449 | if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) { | |||
450 | Changed = true; | |||
451 | I.setHasNoSignedWrap(true); | |||
452 | } | |||
453 | ||||
454 | if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) { | |||
455 | Changed = true; | |||
456 | I.setHasNoUnsignedWrap(true); | |||
457 | } | |||
458 | ||||
459 | return Changed ? &I : nullptr; | |||
460 | } | |||
461 | ||||
462 | /// Detect pattern log2(Y * 0.5) with corresponding fast math flags. | |||
463 | static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) { | |||
464 | if (!Op->hasOneUse()) | |||
465 | return; | |||
466 | ||||
467 | IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op); | |||
468 | if (!II) | |||
469 | return; | |||
470 | if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra()) | |||
471 | return; | |||
472 | Log2 = II; | |||
473 | ||||
474 | Value *OpLog2Of = II->getArgOperand(0); | |||
475 | if (!OpLog2Of->hasOneUse()) | |||
476 | return; | |||
477 | ||||
478 | Instruction *I = dyn_cast<Instruction>(OpLog2Of); | |||
479 | if (!I) | |||
480 | return; | |||
481 | if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra()) | |||
482 | return; | |||
483 | ||||
484 | if (match(I->getOperand(0), m_SpecificFP(0.5))) | |||
485 | Y = I->getOperand(1); | |||
486 | else if (match(I->getOperand(1), m_SpecificFP(0.5))) | |||
487 | Y = I->getOperand(0); | |||
488 | } | |||
489 | ||||
490 | static bool isFiniteNonZeroFp(Constant *C) { | |||
491 | if (C->getType()->isVectorTy()) { | |||
492 | for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; | |||
493 | ++I) { | |||
494 | ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); | |||
495 | if (!CFP || !CFP->getValueAPF().isFiniteNonZero()) | |||
496 | return false; | |||
497 | } | |||
498 | return true; | |||
499 | } | |||
500 | ||||
501 | return isa<ConstantFP>(C) && | |||
502 | cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero(); | |||
503 | } | |||
504 | ||||
505 | static bool isNormalFp(Constant *C) { | |||
506 | if (C->getType()->isVectorTy()) { | |||
507 | for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; | |||
508 | ++I) { | |||
509 | ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); | |||
510 | if (!CFP || !CFP->getValueAPF().isNormal()) | |||
511 | return false; | |||
512 | } | |||
513 | return true; | |||
514 | } | |||
515 | ||||
516 | return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal(); | |||
517 | } | |||
518 | ||||
519 | /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns | |||
520 | /// true iff the given value is FMul or FDiv with one and only one operand | |||
521 | /// being a normal constant (i.e. not Zero/NaN/Infinity). | |||
522 | static bool isFMulOrFDivWithConstant(Value *V) { | |||
523 | Instruction *I = dyn_cast<Instruction>(V); | |||
524 | if (!I || (I->getOpcode() != Instruction::FMul && | |||
525 | I->getOpcode() != Instruction::FDiv)) | |||
526 | return false; | |||
527 | ||||
528 | Constant *C0 = dyn_cast<Constant>(I->getOperand(0)); | |||
529 | Constant *C1 = dyn_cast<Constant>(I->getOperand(1)); | |||
530 | ||||
531 | if (C0 && C1) | |||
532 | return false; | |||
533 | ||||
534 | return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1)); | |||
535 | } | |||
536 | ||||
537 | /// foldFMulConst() is a helper routine of InstCombiner::visitFMul(). | |||
538 | /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand | |||
539 | /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true). | |||
540 | /// This function is to simplify "FMulOrDiv * C" and returns the | |||
541 | /// resulting expression. Note that this function could return NULL in | |||
542 | /// case the constants cannot be folded into a normal floating-point. | |||
543 | /// | |||
544 | Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C, | |||
545 | Instruction *InsertBefore) { | |||
546 | assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid")((isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid" ) ? static_cast<void> (0) : __assert_fail ("isFMulOrFDivWithConstant(FMulOrDiv) && \"V is invalid\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 546, __PRETTY_FUNCTION__)); | |||
547 | ||||
548 | Value *Opnd0 = FMulOrDiv->getOperand(0); | |||
549 | Value *Opnd1 = FMulOrDiv->getOperand(1); | |||
550 | ||||
551 | Constant *C0 = dyn_cast<Constant>(Opnd0); | |||
552 | Constant *C1 = dyn_cast<Constant>(Opnd1); | |||
553 | ||||
554 | BinaryOperator *R = nullptr; | |||
555 | ||||
556 | // (X * C0) * C => X * (C0*C) | |||
557 | if (FMulOrDiv->getOpcode() == Instruction::FMul) { | |||
558 | Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C); | |||
559 | if (isNormalFp(F)) | |||
560 | R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F); | |||
561 | } else { | |||
562 | if (C0) { | |||
563 | // (C0 / X) * C => (C0 * C) / X | |||
564 | if (FMulOrDiv->hasOneUse()) { | |||
565 | // It would otherwise introduce another div. | |||
566 | Constant *F = ConstantExpr::getFMul(C0, C); | |||
567 | if (isNormalFp(F)) | |||
568 | R = BinaryOperator::CreateFDiv(F, Opnd1); | |||
569 | } | |||
570 | } else { | |||
571 | // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal | |||
572 | Constant *F = ConstantExpr::getFDiv(C, C1); | |||
573 | if (isNormalFp(F)) { | |||
574 | R = BinaryOperator::CreateFMul(Opnd0, F); | |||
575 | } else { | |||
576 | // (X / C1) * C => X / (C1/C) | |||
577 | Constant *F = ConstantExpr::getFDiv(C1, C); | |||
578 | if (isNormalFp(F)) | |||
579 | R = BinaryOperator::CreateFDiv(Opnd0, F); | |||
580 | } | |||
581 | } | |||
582 | } | |||
583 | ||||
584 | if (R) { | |||
585 | R->setHasUnsafeAlgebra(true); | |||
586 | InsertNewInstWith(R, *InsertBefore); | |||
587 | } | |||
588 | ||||
589 | return R; | |||
590 | } | |||
591 | ||||
592 | Instruction *InstCombiner::visitFMul(BinaryOperator &I) { | |||
593 | bool Changed = SimplifyAssociativeOrCommutative(I); | |||
594 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
595 | ||||
596 | if (Value *V = SimplifyVectorOp(I)) | |||
597 | return replaceInstUsesWith(I, V); | |||
598 | ||||
599 | if (isa<Constant>(Op0)) | |||
600 | std::swap(Op0, Op1); | |||
601 | ||||
602 | if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), | |||
603 | SQ.getWithInstruction(&I))) | |||
604 | return replaceInstUsesWith(I, V); | |||
605 | ||||
606 | bool AllowReassociate = I.hasUnsafeAlgebra(); | |||
607 | ||||
608 | // Simplify mul instructions with a constant RHS. | |||
609 | if (isa<Constant>(Op1)) { | |||
610 | if (Instruction *FoldedMul = foldOpWithConstantIntoOperand(I)) | |||
611 | return FoldedMul; | |||
612 | ||||
613 | // (fmul X, -1.0) --> (fsub -0.0, X) | |||
614 | if (match(Op1, m_SpecificFP(-1.0))) { | |||
615 | Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType()); | |||
616 | Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0); | |||
617 | RI->copyFastMathFlags(&I); | |||
618 | return RI; | |||
619 | } | |||
620 | ||||
621 | Constant *C = cast<Constant>(Op1); | |||
622 | if (AllowReassociate && isFiniteNonZeroFp(C)) { | |||
623 | // Let MDC denote an expression in one of these forms: | |||
624 | // X * C, C/X, X/C, where C is a constant. | |||
625 | // | |||
626 | // Try to simplify "MDC * Constant" | |||
627 | if (isFMulOrFDivWithConstant(Op0)) | |||
628 | if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I)) | |||
629 | return replaceInstUsesWith(I, V); | |||
630 | ||||
631 | // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C) | |||
632 | Instruction *FAddSub = dyn_cast<Instruction>(Op0); | |||
633 | if (FAddSub && | |||
634 | (FAddSub->getOpcode() == Instruction::FAdd || | |||
635 | FAddSub->getOpcode() == Instruction::FSub)) { | |||
636 | Value *Opnd0 = FAddSub->getOperand(0); | |||
637 | Value *Opnd1 = FAddSub->getOperand(1); | |||
638 | Constant *C0 = dyn_cast<Constant>(Opnd0); | |||
639 | Constant *C1 = dyn_cast<Constant>(Opnd1); | |||
640 | bool Swap = false; | |||
641 | if (C0) { | |||
642 | std::swap(C0, C1); | |||
643 | std::swap(Opnd0, Opnd1); | |||
644 | Swap = true; | |||
645 | } | |||
646 | ||||
647 | if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) { | |||
648 | Value *M1 = ConstantExpr::getFMul(C1, C); | |||
649 | Value *M0 = isNormalFp(cast<Constant>(M1)) ? | |||
650 | foldFMulConst(cast<Instruction>(Opnd0), C, &I) : | |||
651 | nullptr; | |||
652 | if (M0 && M1) { | |||
653 | if (Swap && FAddSub->getOpcode() == Instruction::FSub) | |||
654 | std::swap(M0, M1); | |||
655 | ||||
656 | Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd) | |||
657 | ? BinaryOperator::CreateFAdd(M0, M1) | |||
658 | : BinaryOperator::CreateFSub(M0, M1); | |||
659 | RI->copyFastMathFlags(&I); | |||
660 | return RI; | |||
661 | } | |||
662 | } | |||
663 | } | |||
664 | } | |||
665 | } | |||
666 | ||||
667 | if (Op0 == Op1) { | |||
668 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { | |||
669 | // sqrt(X) * sqrt(X) -> X | |||
670 | if (AllowReassociate && II->getIntrinsicID() == Intrinsic::sqrt) | |||
671 | return replaceInstUsesWith(I, II->getOperand(0)); | |||
672 | ||||
673 | // fabs(X) * fabs(X) -> X * X | |||
674 | if (II->getIntrinsicID() == Intrinsic::fabs) { | |||
675 | Instruction *FMulVal = BinaryOperator::CreateFMul(II->getOperand(0), | |||
676 | II->getOperand(0), | |||
677 | I.getName()); | |||
678 | FMulVal->copyFastMathFlags(&I); | |||
679 | return FMulVal; | |||
680 | } | |||
681 | } | |||
682 | } | |||
683 | ||||
684 | // Under unsafe algebra do: | |||
685 | // X * log2(0.5*Y) = X*log2(Y) - X | |||
686 | if (AllowReassociate) { | |||
687 | Value *OpX = nullptr; | |||
688 | Value *OpY = nullptr; | |||
689 | IntrinsicInst *Log2; | |||
690 | detectLog2OfHalf(Op0, OpY, Log2); | |||
691 | if (OpY) { | |||
692 | OpX = Op1; | |||
693 | } else { | |||
694 | detectLog2OfHalf(Op1, OpY, Log2); | |||
695 | if (OpY) { | |||
696 | OpX = Op0; | |||
697 | } | |||
698 | } | |||
699 | // if pattern detected emit alternate sequence | |||
700 | if (OpX && OpY) { | |||
701 | BuilderTy::FastMathFlagGuard Guard(*Builder); | |||
702 | Builder->setFastMathFlags(Log2->getFastMathFlags()); | |||
703 | Log2->setArgOperand(0, OpY); | |||
704 | Value *FMulVal = Builder->CreateFMul(OpX, Log2); | |||
705 | Value *FSub = Builder->CreateFSub(FMulVal, OpX); | |||
706 | FSub->takeName(&I); | |||
707 | return replaceInstUsesWith(I, FSub); | |||
708 | } | |||
709 | } | |||
710 | ||||
711 | // Handle symmetric situation in a 2-iteration loop | |||
712 | Value *Opnd0 = Op0; | |||
713 | Value *Opnd1 = Op1; | |||
714 | for (int i = 0; i < 2; i++) { | |||
715 | bool IgnoreZeroSign = I.hasNoSignedZeros(); | |||
716 | if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) { | |||
717 | BuilderTy::FastMathFlagGuard Guard(*Builder); | |||
718 | Builder->setFastMathFlags(I.getFastMathFlags()); | |||
719 | ||||
720 | Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign); | |||
721 | Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign); | |||
722 | ||||
723 | // -X * -Y => X*Y | |||
724 | if (N1) { | |||
725 | Value *FMul = Builder->CreateFMul(N0, N1); | |||
726 | FMul->takeName(&I); | |||
727 | return replaceInstUsesWith(I, FMul); | |||
728 | } | |||
729 | ||||
730 | if (Opnd0->hasOneUse()) { | |||
731 | // -X * Y => -(X*Y) (Promote negation as high as possible) | |||
732 | Value *T = Builder->CreateFMul(N0, Opnd1); | |||
733 | Value *Neg = Builder->CreateFNeg(T); | |||
734 | Neg->takeName(&I); | |||
735 | return replaceInstUsesWith(I, Neg); | |||
736 | } | |||
737 | } | |||
738 | ||||
739 | // (X*Y) * X => (X*X) * Y where Y != X | |||
740 | // The purpose is two-fold: | |||
741 | // 1) to form a power expression (of X). | |||
742 | // 2) potentially shorten the critical path: After transformation, the | |||
743 | // latency of the instruction Y is amortized by the expression of X*X, | |||
744 | // and therefore Y is in a "less critical" position compared to what it | |||
745 | // was before the transformation. | |||
746 | // | |||
747 | if (AllowReassociate) { | |||
748 | Value *Opnd0_0, *Opnd0_1; | |||
749 | if (Opnd0->hasOneUse() && | |||
750 | match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) { | |||
751 | Value *Y = nullptr; | |||
752 | if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1) | |||
753 | Y = Opnd0_1; | |||
754 | else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1) | |||
755 | Y = Opnd0_0; | |||
756 | ||||
757 | if (Y) { | |||
758 | BuilderTy::FastMathFlagGuard Guard(*Builder); | |||
759 | Builder->setFastMathFlags(I.getFastMathFlags()); | |||
760 | Value *T = Builder->CreateFMul(Opnd1, Opnd1); | |||
761 | Value *R = Builder->CreateFMul(T, Y); | |||
762 | R->takeName(&I); | |||
763 | return replaceInstUsesWith(I, R); | |||
764 | } | |||
765 | } | |||
766 | } | |||
767 | ||||
768 | if (!isa<Constant>(Op1)) | |||
769 | std::swap(Opnd0, Opnd1); | |||
770 | else | |||
771 | break; | |||
772 | } | |||
773 | ||||
774 | return Changed ? &I : nullptr; | |||
775 | } | |||
776 | ||||
777 | /// Try to fold a divide or remainder of a select instruction. | |||
778 | bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { | |||
779 | SelectInst *SI = cast<SelectInst>(I.getOperand(1)); | |||
780 | ||||
781 | // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y | |||
782 | int NonNullOperand = -1; | |||
783 | if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) | |||
784 | if (ST->isNullValue()) | |||
785 | NonNullOperand = 2; | |||
786 | // div/rem X, (Cond ? Y : 0) -> div/rem X, Y | |||
787 | if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) | |||
788 | if (ST->isNullValue()) | |||
789 | NonNullOperand = 1; | |||
790 | ||||
791 | if (NonNullOperand == -1) | |||
792 | return false; | |||
793 | ||||
794 | Value *SelectCond = SI->getOperand(0); | |||
795 | ||||
796 | // Change the div/rem to use 'Y' instead of the select. | |||
797 | I.setOperand(1, SI->getOperand(NonNullOperand)); | |||
798 | ||||
799 | // Okay, we know we replace the operand of the div/rem with 'Y' with no | |||
800 | // problem. However, the select, or the condition of the select may have | |||
801 | // multiple uses. Based on our knowledge that the operand must be non-zero, | |||
802 | // propagate the known value for the select into other uses of it, and | |||
803 | // propagate a known value of the condition into its other users. | |||
804 | ||||
805 | // If the select and condition only have a single use, don't bother with this, | |||
806 | // early exit. | |||
807 | if (SI->use_empty() && SelectCond->hasOneUse()) | |||
808 | return true; | |||
809 | ||||
810 | // Scan the current block backward, looking for other uses of SI. | |||
811 | BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin(); | |||
812 | ||||
813 | while (BBI != BBFront) { | |||
814 | --BBI; | |||
815 | // If we found a call to a function, we can't assume it will return, so | |||
816 | // information from below it cannot be propagated above it. | |||
817 | if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) | |||
818 | break; | |||
819 | ||||
820 | // Replace uses of the select or its condition with the known values. | |||
821 | for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); | |||
822 | I != E; ++I) { | |||
823 | if (*I == SI) { | |||
824 | *I = SI->getOperand(NonNullOperand); | |||
| ||||
825 | Worklist.Add(&*BBI); | |||
826 | } else if (*I == SelectCond) { | |||
827 | *I = Builder->getInt1(NonNullOperand == 1); | |||
828 | Worklist.Add(&*BBI); | |||
829 | } | |||
830 | } | |||
831 | ||||
832 | // If we past the instruction, quit looking for it. | |||
833 | if (&*BBI == SI) | |||
834 | SI = nullptr; | |||
835 | if (&*BBI == SelectCond) | |||
836 | SelectCond = nullptr; | |||
837 | ||||
838 | // If we ran out of things to eliminate, break out of the loop. | |||
839 | if (!SelectCond && !SI) | |||
840 | break; | |||
841 | ||||
842 | } | |||
843 | return true; | |||
844 | } | |||
845 | ||||
846 | ||||
847 | /// This function implements the transforms common to both integer division | |||
848 | /// instructions (udiv and sdiv). It is called by the visitors to those integer | |||
849 | /// division instructions. | |||
850 | /// @brief Common integer divide transforms | |||
851 | Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { | |||
852 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
853 | ||||
854 | // The RHS is known non-zero. | |||
855 | if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { | |||
856 | I.setOperand(1, V); | |||
857 | return &I; | |||
858 | } | |||
859 | ||||
860 | // Handle cases involving: [su]div X, (select Cond, Y, Z) | |||
861 | // This does not apply for fdiv. | |||
862 | if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) | |||
863 | return &I; | |||
864 | ||||
865 | if (Instruction *LHS = dyn_cast<Instruction>(Op0)) { | |||
866 | const APInt *C2; | |||
867 | if (match(Op1, m_APInt(C2))) { | |||
868 | Value *X; | |||
869 | const APInt *C1; | |||
870 | bool IsSigned = I.getOpcode() == Instruction::SDiv; | |||
871 | ||||
872 | // (X / C1) / C2 -> X / (C1*C2) | |||
873 | if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) || | |||
874 | (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) { | |||
875 | APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); | |||
876 | if (!MultiplyOverflows(*C1, *C2, Product, IsSigned)) | |||
877 | return BinaryOperator::Create(I.getOpcode(), X, | |||
878 | ConstantInt::get(I.getType(), Product)); | |||
879 | } | |||
880 | ||||
881 | if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) || | |||
882 | (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) { | |||
883 | APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); | |||
884 | ||||
885 | // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. | |||
886 | if (IsMultiple(*C2, *C1, Quotient, IsSigned)) { | |||
887 | BinaryOperator *BO = BinaryOperator::Create( | |||
888 | I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); | |||
889 | BO->setIsExact(I.isExact()); | |||
890 | return BO; | |||
891 | } | |||
892 | ||||
893 | // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2. | |||
894 | if (IsMultiple(*C1, *C2, Quotient, IsSigned)) { | |||
895 | BinaryOperator *BO = BinaryOperator::Create( | |||
896 | Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); | |||
897 | BO->setHasNoUnsignedWrap( | |||
898 | !IsSigned && | |||
899 | cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); | |||
900 | BO->setHasNoSignedWrap( | |||
901 | cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); | |||
902 | return BO; | |||
903 | } | |||
904 | } | |||
905 | ||||
906 | if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) && | |||
907 | *C1 != C1->getBitWidth() - 1) || | |||
908 | (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) { | |||
909 | APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); | |||
910 | APInt C1Shifted = APInt::getOneBitSet( | |||
911 | C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue())); | |||
912 | ||||
913 | // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1. | |||
914 | if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) { | |||
915 | BinaryOperator *BO = BinaryOperator::Create( | |||
916 | I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); | |||
917 | BO->setIsExact(I.isExact()); | |||
918 | return BO; | |||
919 | } | |||
920 | ||||
921 | // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2. | |||
922 | if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) { | |||
923 | BinaryOperator *BO = BinaryOperator::Create( | |||
924 | Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); | |||
925 | BO->setHasNoUnsignedWrap( | |||
926 | !IsSigned && | |||
927 | cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); | |||
928 | BO->setHasNoSignedWrap( | |||
929 | cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); | |||
930 | return BO; | |||
931 | } | |||
932 | } | |||
933 | ||||
934 | if (!C2->isNullValue()) // avoid X udiv 0 | |||
935 | if (Instruction *FoldedDiv = foldOpWithConstantIntoOperand(I)) | |||
936 | return FoldedDiv; | |||
937 | } | |||
938 | } | |||
939 | ||||
940 | if (match(Op0, m_One())) { | |||
941 | assert(!I.getType()->getScalarType()->isIntegerTy(1) &&((!I.getType()->getScalarType()->isIntegerTy(1) && "i1 divide not removed?") ? static_cast<void> (0) : __assert_fail ("!I.getType()->getScalarType()->isIntegerTy(1) && \"i1 divide not removed?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 942, __PRETTY_FUNCTION__)) | |||
942 | "i1 divide not removed?")((!I.getType()->getScalarType()->isIntegerTy(1) && "i1 divide not removed?") ? static_cast<void> (0) : __assert_fail ("!I.getType()->getScalarType()->isIntegerTy(1) && \"i1 divide not removed?\"" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 942, __PRETTY_FUNCTION__)); | |||
943 | if (I.getOpcode() == Instruction::SDiv) { | |||
944 | // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the | |||
945 | // result is one, if Op1 is -1 then the result is minus one, otherwise | |||
946 | // it's zero. | |||
947 | Value *Inc = Builder->CreateAdd(Op1, Op0); | |||
948 | Value *Cmp = Builder->CreateICmpULT( | |||
949 | Inc, ConstantInt::get(I.getType(), 3)); | |||
950 | return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0)); | |||
951 | } else { | |||
952 | // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the | |||
953 | // result is one, otherwise it's zero. | |||
954 | return new ZExtInst(Builder->CreateICmpEQ(Op1, Op0), I.getType()); | |||
955 | } | |||
956 | } | |||
957 | ||||
958 | // See if we can fold away this div instruction. | |||
959 | if (SimplifyDemandedInstructionBits(I)) | |||
960 | return &I; | |||
961 | ||||
962 | // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y | |||
963 | Value *X = nullptr, *Z = nullptr; | |||
964 | if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 | |||
965 | bool isSigned = I.getOpcode() == Instruction::SDiv; | |||
966 | if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || | |||
967 | (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) | |||
968 | return BinaryOperator::Create(I.getOpcode(), X, Op1); | |||
969 | } | |||
970 | ||||
971 | return nullptr; | |||
972 | } | |||
973 | ||||
974 | /// dyn_castZExtVal - Checks if V is a zext or constant that can | |||
975 | /// be truncated to Ty without losing bits. | |||
976 | static Value *dyn_castZExtVal(Value *V, Type *Ty) { | |||
977 | if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { | |||
978 | if (Z->getSrcTy() == Ty) | |||
979 | return Z->getOperand(0); | |||
980 | } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { | |||
981 | if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) | |||
982 | return ConstantExpr::getTrunc(C, Ty); | |||
983 | } | |||
984 | return nullptr; | |||
985 | } | |||
986 | ||||
987 | namespace { | |||
988 | const unsigned MaxDepth = 6; | |||
989 | typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, | |||
990 | const BinaryOperator &I, | |||
991 | InstCombiner &IC); | |||
992 | ||||
993 | /// \brief Used to maintain state for visitUDivOperand(). | |||
994 | struct UDivFoldAction { | |||
995 | FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this | |||
996 | ///< operand. This can be zero if this action | |||
997 | ///< joins two actions together. | |||
998 | ||||
999 | Value *OperandToFold; ///< Which operand to fold. | |||
1000 | union { | |||
1001 | Instruction *FoldResult; ///< The instruction returned when FoldAction is | |||
1002 | ///< invoked. | |||
1003 | ||||
1004 | size_t SelectLHSIdx; ///< Stores the LHS action index if this action | |||
1005 | ///< joins two actions together. | |||
1006 | }; | |||
1007 | ||||
1008 | UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) | |||
1009 | : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {} | |||
1010 | UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) | |||
1011 | : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} | |||
1012 | }; | |||
1013 | } | |||
1014 | ||||
1015 | // X udiv 2^C -> X >> C | |||
1016 | static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, | |||
1017 | const BinaryOperator &I, InstCombiner &IC) { | |||
1018 | const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); | |||
1019 | BinaryOperator *LShr = BinaryOperator::CreateLShr( | |||
1020 | Op0, ConstantInt::get(Op0->getType(), C.logBase2())); | |||
1021 | if (I.isExact()) | |||
1022 | LShr->setIsExact(); | |||
1023 | return LShr; | |||
1024 | } | |||
1025 | ||||
1026 | // X udiv C, where C >= signbit | |||
1027 | static Instruction *foldUDivNegCst(Value *Op0, Value *Op1, | |||
1028 | const BinaryOperator &I, InstCombiner &IC) { | |||
1029 | Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); | |||
1030 | ||||
1031 | return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), | |||
1032 | ConstantInt::get(I.getType(), 1)); | |||
1033 | } | |||
1034 | ||||
1035 | // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) | |||
1036 | // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2) | |||
1037 | static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, | |||
1038 | InstCombiner &IC) { | |||
1039 | Value *ShiftLeft; | |||
1040 | if (!match(Op1, m_ZExt(m_Value(ShiftLeft)))) | |||
1041 | ShiftLeft = Op1; | |||
1042 | ||||
1043 | const APInt *CI; | |||
1044 | Value *N; | |||
1045 | if (!match(ShiftLeft, m_Shl(m_APInt(CI), m_Value(N)))) | |||
1046 | llvm_unreachable("match should never fail here!")::llvm::llvm_unreachable_internal("match should never fail here!" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp" , 1046); | |||
1047 | if (*CI != 1) | |||
1048 | N = IC.Builder->CreateAdd(N, | |||
1049 | ConstantInt::get(N->getType(), CI->logBase2())); | |||
1050 | if (Op1 != ShiftLeft) | |||
1051 | N = IC.Builder->CreateZExt(N, Op1->getType()); | |||
1052 | BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); | |||
1053 | if (I.isExact()) | |||
1054 | LShr->setIsExact(); | |||
1055 | return LShr; | |||
1056 | } | |||
1057 | ||||
1058 | // \brief Recursively visits the possible right hand operands of a udiv | |||
1059 | // instruction, seeing through select instructions, to determine if we can | |||
1060 | // replace the udiv with something simpler. If we find that an operand is not | |||
1061 | // able to simplify the udiv, we abort the entire transformation. | |||
1062 | static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, | |||
1063 | SmallVectorImpl<UDivFoldAction> &Actions, | |||
1064 | unsigned Depth = 0) { | |||
1065 | // Check to see if this is an unsigned division with an exact power of 2, | |||
1066 | // if so, convert to a right shift. | |||
1067 | if (match(Op1, m_Power2())) { | |||
1068 | Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); | |||
1069 | return Actions.size(); | |||
1070 | } | |||
1071 | ||||
1072 | if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) | |||
1073 | // X udiv C, where C >= signbit | |||
1074 | if (C->getValue().isNegative()) { | |||
1075 | Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); | |||
1076 | return Actions.size(); | |||
1077 | } | |||
1078 | ||||
1079 | // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) | |||
1080 | if (match(Op1, m_Shl(m_Power2(), m_Value())) || | |||
1081 | match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { | |||
1082 | Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); | |||
1083 | return Actions.size(); | |||
1084 | } | |||
1085 | ||||
1086 | // The remaining tests are all recursive, so bail out if we hit the limit. | |||
1087 | if (Depth++ == MaxDepth) | |||
1088 | return 0; | |||
1089 | ||||
1090 | if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) | |||
1091 | if (size_t LHSIdx = | |||
1092 | visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth)) | |||
1093 | if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) { | |||
1094 | Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1)); | |||
1095 | return Actions.size(); | |||
1096 | } | |||
1097 | ||||
1098 | return 0; | |||
1099 | } | |||
1100 | ||||
1101 | Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { | |||
1102 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1103 | ||||
1104 | if (Value *V = SimplifyVectorOp(I)) | |||
1105 | return replaceInstUsesWith(I, V); | |||
1106 | ||||
1107 | if (Value *V = SimplifyUDivInst(Op0, Op1, SQ.getWithInstruction(&I))) | |||
1108 | return replaceInstUsesWith(I, V); | |||
1109 | ||||
1110 | // Handle the integer div common cases | |||
1111 | if (Instruction *Common = commonIDivTransforms(I)) | |||
1112 | return Common; | |||
1113 | ||||
1114 | // (x lshr C1) udiv C2 --> x udiv (C2 << C1) | |||
1115 | { | |||
1116 | Value *X; | |||
1117 | const APInt *C1, *C2; | |||
1118 | if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && | |||
1119 | match(Op1, m_APInt(C2))) { | |||
1120 | bool Overflow; | |||
1121 | APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow); | |||
1122 | if (!Overflow) { | |||
1123 | bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value())); | |||
1124 | BinaryOperator *BO = BinaryOperator::CreateUDiv( | |||
1125 | X, ConstantInt::get(X->getType(), C2ShlC1)); | |||
1126 | if (IsExact) | |||
1127 | BO->setIsExact(); | |||
1128 | return BO; | |||
1129 | } | |||
1130 | } | |||
1131 | } | |||
1132 | ||||
1133 | // (zext A) udiv (zext B) --> zext (A udiv B) | |||
1134 | if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) | |||
1135 | if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) | |||
1136 | return new ZExtInst( | |||
1137 | Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()), | |||
1138 | I.getType()); | |||
1139 | ||||
1140 | // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) | |||
1141 | SmallVector<UDivFoldAction, 6> UDivActions; | |||
1142 | if (visitUDivOperand(Op0, Op1, I, UDivActions)) | |||
1143 | for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { | |||
1144 | FoldUDivOperandCb Action = UDivActions[i].FoldAction; | |||
1145 | Value *ActionOp1 = UDivActions[i].OperandToFold; | |||
1146 | Instruction *Inst; | |||
1147 | if (Action) | |||
1148 | Inst = Action(Op0, ActionOp1, I, *this); | |||
1149 | else { | |||
1150 | // This action joins two actions together. The RHS of this action is | |||
1151 | // simply the last action we processed, we saved the LHS action index in | |||
1152 | // the joining action. | |||
1153 | size_t SelectRHSIdx = i - 1; | |||
1154 | Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; | |||
1155 | size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; | |||
1156 | Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; | |||
1157 | Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), | |||
1158 | SelectLHS, SelectRHS); | |||
1159 | } | |||
1160 | ||||
1161 | // If this is the last action to process, return it to the InstCombiner. | |||
1162 | // Otherwise, we insert it before the UDiv and record it so that we may | |||
1163 | // use it as part of a joining action (i.e., a SelectInst). | |||
1164 | if (e - i != 1) { | |||
1165 | Inst->insertBefore(&I); | |||
1166 | UDivActions[i].FoldResult = Inst; | |||
1167 | } else | |||
1168 | return Inst; | |||
1169 | } | |||
1170 | ||||
1171 | return nullptr; | |||
1172 | } | |||
1173 | ||||
1174 | Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { | |||
1175 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1176 | ||||
1177 | if (Value *V = SimplifyVectorOp(I)) | |||
1178 | return replaceInstUsesWith(I, V); | |||
1179 | ||||
1180 | if (Value *V = SimplifySDivInst(Op0, Op1, SQ.getWithInstruction(&I))) | |||
1181 | return replaceInstUsesWith(I, V); | |||
1182 | ||||
1183 | // Handle the integer div common cases | |||
1184 | if (Instruction *Common = commonIDivTransforms(I)) | |||
1185 | return Common; | |||
1186 | ||||
1187 | const APInt *Op1C; | |||
1188 | if (match(Op1, m_APInt(Op1C))) { | |||
1189 | // sdiv X, -1 == -X | |||
1190 | if (Op1C->isAllOnesValue()) | |||
1191 | return BinaryOperator::CreateNeg(Op0); | |||
1192 | ||||
1193 | // sdiv exact X, C --> ashr exact X, log2(C) | |||
1194 | if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) { | |||
1195 | Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2()); | |||
1196 | return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); | |||
1197 | } | |||
1198 | ||||
1199 | // If the dividend is sign-extended and the constant divisor is small enough | |||
1200 | // to fit in the source type, shrink the division to the narrower type: | |||
1201 | // (sext X) sdiv C --> sext (X sdiv C) | |||
1202 | Value *Op0Src; | |||
1203 | if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) && | |||
1204 | Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) { | |||
1205 | ||||
1206 | // In the general case, we need to make sure that the dividend is not the | |||
1207 | // minimum signed value because dividing that by -1 is UB. But here, we | |||
1208 | // know that the -1 divisor case is already handled above. | |||
1209 | ||||
1210 | Constant *NarrowDivisor = | |||
1211 | ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType()); | |||
1212 | Value *NarrowOp = Builder->CreateSDiv(Op0Src, NarrowDivisor); | |||
1213 | return new SExtInst(NarrowOp, Op0->getType()); | |||
1214 | } | |||
1215 | } | |||
1216 | ||||
1217 | if (Constant *RHS = dyn_cast<Constant>(Op1)) { | |||
1218 | // X/INT_MIN -> X == INT_MIN | |||
1219 | if (RHS->isMinSignedValue()) | |||
1220 | return new ZExtInst(Builder->CreateICmpEQ(Op0, Op1), I.getType()); | |||
1221 | ||||
1222 | // -X/C --> X/-C provided the negation doesn't overflow. | |||
1223 | Value *X; | |||
1224 | if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { | |||
1225 | auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS)); | |||
1226 | BO->setIsExact(I.isExact()); | |||
1227 | return BO; | |||
1228 | } | |||
1229 | } | |||
1230 | ||||
1231 | // If the sign bits of both operands are zero (i.e. we can prove they are | |||
1232 | // unsigned inputs), turn this into a udiv. | |||
1233 | APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits())); | |||
1234 | if (MaskedValueIsZero(Op0, Mask, 0, &I)) { | |||
1235 | if (MaskedValueIsZero(Op1, Mask, 0, &I)) { | |||
1236 | // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set | |||
1237 | auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); | |||
1238 | BO->setIsExact(I.isExact()); | |||
1239 | return BO; | |||
1240 | } | |||
1241 | ||||
1242 | if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) { | |||
1243 | // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) | |||
1244 | // Safe because the only negative value (1 << Y) can take on is | |||
1245 | // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have | |||
1246 | // the sign bit set. | |||
1247 | auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); | |||
1248 | BO->setIsExact(I.isExact()); | |||
1249 | return BO; | |||
1250 | } | |||
1251 | } | |||
1252 | ||||
1253 | return nullptr; | |||
1254 | } | |||
1255 | ||||
1256 | /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special | |||
1257 | /// FP value and: | |||
1258 | /// 1) 1/C is exact, or | |||
1259 | /// 2) reciprocal is allowed. | |||
1260 | /// If the conversion was successful, the simplified expression "X * 1/C" is | |||
1261 | /// returned; otherwise, NULL is returned. | |||
1262 | /// | |||
1263 | static Instruction *CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor, | |||
1264 | bool AllowReciprocal) { | |||
1265 | if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors. | |||
1266 | return nullptr; | |||
1267 | ||||
1268 | const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF(); | |||
1269 | APFloat Reciprocal(FpVal.getSemantics()); | |||
1270 | bool Cvt = FpVal.getExactInverse(&Reciprocal); | |||
1271 | ||||
1272 | if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { | |||
1273 | Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); | |||
1274 | (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); | |||
1275 | Cvt = !Reciprocal.isDenormal(); | |||
1276 | } | |||
1277 | ||||
1278 | if (!Cvt) | |||
1279 | return nullptr; | |||
1280 | ||||
1281 | ConstantFP *R; | |||
1282 | R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); | |||
1283 | return BinaryOperator::CreateFMul(Dividend, R); | |||
1284 | } | |||
1285 | ||||
1286 | Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { | |||
1287 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1288 | ||||
1289 | if (Value *V = SimplifyVectorOp(I)) | |||
1290 | return replaceInstUsesWith(I, V); | |||
1291 | ||||
1292 | if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(), | |||
1293 | SQ.getWithInstruction(&I))) | |||
1294 | return replaceInstUsesWith(I, V); | |||
1295 | ||||
1296 | if (isa<Constant>(Op0)) | |||
1297 | if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) | |||
1298 | if (Instruction *R = FoldOpIntoSelect(I, SI)) | |||
1299 | return R; | |||
1300 | ||||
1301 | bool AllowReassociate = I.hasUnsafeAlgebra(); | |||
1302 | bool AllowReciprocal = I.hasAllowReciprocal(); | |||
1303 | ||||
1304 | if (Constant *Op1C = dyn_cast<Constant>(Op1)) { | |||
1305 | if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) | |||
1306 | if (Instruction *R = FoldOpIntoSelect(I, SI)) | |||
1307 | return R; | |||
1308 | ||||
1309 | if (AllowReassociate) { | |||
1310 | Constant *C1 = nullptr; | |||
1311 | Constant *C2 = Op1C; | |||
1312 | Value *X; | |||
1313 | Instruction *Res = nullptr; | |||
1314 | ||||
1315 | if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) { | |||
1316 | // (X*C1)/C2 => X * (C1/C2) | |||
1317 | // | |||
1318 | Constant *C = ConstantExpr::getFDiv(C1, C2); | |||
1319 | if (isNormalFp(C)) | |||
1320 | Res = BinaryOperator::CreateFMul(X, C); | |||
1321 | } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) { | |||
1322 | // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] | |||
1323 | // | |||
1324 | Constant *C = ConstantExpr::getFMul(C1, C2); | |||
1325 | if (isNormalFp(C)) { | |||
1326 | Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal); | |||
1327 | if (!Res) | |||
1328 | Res = BinaryOperator::CreateFDiv(X, C); | |||
1329 | } | |||
1330 | } | |||
1331 | ||||
1332 | if (Res) { | |||
1333 | Res->setFastMathFlags(I.getFastMathFlags()); | |||
1334 | return Res; | |||
1335 | } | |||
1336 | } | |||
1337 | ||||
1338 | // X / C => X * 1/C | |||
1339 | if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) { | |||
1340 | T->copyFastMathFlags(&I); | |||
1341 | return T; | |||
1342 | } | |||
1343 | ||||
1344 | return nullptr; | |||
1345 | } | |||
1346 | ||||
1347 | if (AllowReassociate && isa<Constant>(Op0)) { | |||
1348 | Constant *C1 = cast<Constant>(Op0), *C2; | |||
1349 | Constant *Fold = nullptr; | |||
1350 | Value *X; | |||
1351 | bool CreateDiv = true; | |||
1352 | ||||
1353 | // C1 / (X*C2) => (C1/C2) / X | |||
1354 | if (match(Op1, m_FMul(m_Value(X), m_Constant(C2)))) | |||
1355 | Fold = ConstantExpr::getFDiv(C1, C2); | |||
1356 | else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) { | |||
1357 | // C1 / (X/C2) => (C1*C2) / X | |||
1358 | Fold = ConstantExpr::getFMul(C1, C2); | |||
1359 | } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) { | |||
1360 | // C1 / (C2/X) => (C1/C2) * X | |||
1361 | Fold = ConstantExpr::getFDiv(C1, C2); | |||
1362 | CreateDiv = false; | |||
1363 | } | |||
1364 | ||||
1365 | if (Fold && isNormalFp(Fold)) { | |||
1366 | Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X) | |||
1367 | : BinaryOperator::CreateFMul(X, Fold); | |||
1368 | R->setFastMathFlags(I.getFastMathFlags()); | |||
1369 | return R; | |||
1370 | } | |||
1371 | return nullptr; | |||
1372 | } | |||
1373 | ||||
1374 | if (AllowReassociate) { | |||
1375 | Value *X, *Y; | |||
1376 | Value *NewInst = nullptr; | |||
1377 | Instruction *SimpR = nullptr; | |||
1378 | ||||
1379 | if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { | |||
1380 | // (X/Y) / Z => X / (Y*Z) | |||
1381 | // | |||
1382 | if (!isa<Constant>(Y) || !isa<Constant>(Op1)) { | |||
1383 | NewInst = Builder->CreateFMul(Y, Op1); | |||
1384 | if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { | |||
1385 | FastMathFlags Flags = I.getFastMathFlags(); | |||
1386 | Flags &= cast<Instruction>(Op0)->getFastMathFlags(); | |||
1387 | RI->setFastMathFlags(Flags); | |||
1388 | } | |||
1389 | SimpR = BinaryOperator::CreateFDiv(X, NewInst); | |||
1390 | } | |||
1391 | } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { | |||
1392 | // Z / (X/Y) => Z*Y / X | |||
1393 | // | |||
1394 | if (!isa<Constant>(Y) || !isa<Constant>(Op0)) { | |||
1395 | NewInst = Builder->CreateFMul(Op0, Y); | |||
1396 | if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { | |||
1397 | FastMathFlags Flags = I.getFastMathFlags(); | |||
1398 | Flags &= cast<Instruction>(Op1)->getFastMathFlags(); | |||
1399 | RI->setFastMathFlags(Flags); | |||
1400 | } | |||
1401 | SimpR = BinaryOperator::CreateFDiv(NewInst, X); | |||
1402 | } | |||
1403 | } | |||
1404 | ||||
1405 | if (NewInst) { | |||
1406 | if (Instruction *T = dyn_cast<Instruction>(NewInst)) | |||
1407 | T->setDebugLoc(I.getDebugLoc()); | |||
1408 | SimpR->setFastMathFlags(I.getFastMathFlags()); | |||
1409 | return SimpR; | |||
1410 | } | |||
1411 | } | |||
1412 | ||||
1413 | Value *LHS; | |||
1414 | Value *RHS; | |||
1415 | ||||
1416 | // -x / -y -> x / y | |||
1417 | if (match(Op0, m_FNeg(m_Value(LHS))) && match(Op1, m_FNeg(m_Value(RHS)))) { | |||
1418 | I.setOperand(0, LHS); | |||
1419 | I.setOperand(1, RHS); | |||
1420 | return &I; | |||
1421 | } | |||
1422 | ||||
1423 | return nullptr; | |||
1424 | } | |||
1425 | ||||
1426 | /// This function implements the transforms common to both integer remainder | |||
1427 | /// instructions (urem and srem). It is called by the visitors to those integer | |||
1428 | /// remainder instructions. | |||
1429 | /// @brief Common integer remainder transforms | |||
1430 | Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { | |||
1431 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1432 | ||||
1433 | // The RHS is known non-zero. | |||
1434 | if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { | |||
1435 | I.setOperand(1, V); | |||
1436 | return &I; | |||
1437 | } | |||
1438 | ||||
1439 | // Handle cases involving: rem X, (select Cond, Y, Z) | |||
1440 | if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) | |||
1441 | return &I; | |||
1442 | ||||
1443 | if (isa<Constant>(Op1)) { | |||
1444 | if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { | |||
1445 | if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { | |||
1446 | if (Instruction *R = FoldOpIntoSelect(I, SI)) | |||
1447 | return R; | |||
1448 | } else if (auto *PN = dyn_cast<PHINode>(Op0I)) { | |||
1449 | using namespace llvm::PatternMatch; | |||
1450 | const APInt *Op1Int; | |||
1451 | if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() && | |||
1452 | (I.getOpcode() == Instruction::URem || | |||
1453 | !Op1Int->isMinSignedValue())) { | |||
1454 | // foldOpIntoPhi will speculate instructions to the end of the PHI's | |||
1455 | // predecessor blocks, so do this only if we know the srem or urem | |||
1456 | // will not fault. | |||
1457 | if (Instruction *NV = foldOpIntoPhi(I, PN)) | |||
1458 | return NV; | |||
1459 | } | |||
1460 | } | |||
1461 | ||||
1462 | // See if we can fold away this rem instruction. | |||
1463 | if (SimplifyDemandedInstructionBits(I)) | |||
1464 | return &I; | |||
1465 | } | |||
1466 | } | |||
1467 | ||||
1468 | return nullptr; | |||
1469 | } | |||
1470 | ||||
1471 | Instruction *InstCombiner::visitURem(BinaryOperator &I) { | |||
1472 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1473 | ||||
1474 | if (Value *V = SimplifyVectorOp(I)) | |||
1475 | return replaceInstUsesWith(I, V); | |||
1476 | ||||
1477 | if (Value *V = SimplifyURemInst(Op0, Op1, SQ.getWithInstruction(&I))) | |||
1478 | return replaceInstUsesWith(I, V); | |||
1479 | ||||
1480 | if (Instruction *common = commonIRemTransforms(I)) | |||
1481 | return common; | |||
1482 | ||||
1483 | // (zext A) urem (zext B) --> zext (A urem B) | |||
1484 | if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) | |||
1485 | if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) | |||
1486 | return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), | |||
1487 | I.getType()); | |||
1488 | ||||
1489 | // X urem Y -> X and Y-1, where Y is a power of 2, | |||
1490 | if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) { | |||
1491 | Constant *N1 = Constant::getAllOnesValue(I.getType()); | |||
1492 | Value *Add = Builder->CreateAdd(Op1, N1); | |||
1493 | return BinaryOperator::CreateAnd(Op0, Add); | |||
1494 | } | |||
1495 | ||||
1496 | // 1 urem X -> zext(X != 1) | |||
1497 | if (match(Op0, m_One())) { | |||
1498 | Value *Cmp = Builder->CreateICmpNE(Op1, Op0); | |||
1499 | Value *Ext = Builder->CreateZExt(Cmp, I.getType()); | |||
1500 | return replaceInstUsesWith(I, Ext); | |||
1501 | } | |||
1502 | ||||
1503 | // X urem C -> X < C ? X : X - C, where C >= signbit. | |||
1504 | const APInt *DivisorC; | |||
1505 | if (match(Op1, m_APInt(DivisorC)) && DivisorC->isNegative()) { | |||
1506 | Value *Cmp = Builder->CreateICmpULT(Op0, Op1); | |||
1507 | Value *Sub = Builder->CreateSub(Op0, Op1); | |||
1508 | return SelectInst::Create(Cmp, Op0, Sub); | |||
1509 | } | |||
1510 | ||||
1511 | return nullptr; | |||
1512 | } | |||
1513 | ||||
1514 | Instruction *InstCombiner::visitSRem(BinaryOperator &I) { | |||
1515 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1516 | ||||
1517 | if (Value *V = SimplifyVectorOp(I)) | |||
1518 | return replaceInstUsesWith(I, V); | |||
1519 | ||||
1520 | if (Value *V = SimplifySRemInst(Op0, Op1, SQ.getWithInstruction(&I))) | |||
1521 | return replaceInstUsesWith(I, V); | |||
1522 | ||||
1523 | // Handle the integer rem common cases | |||
1524 | if (Instruction *Common = commonIRemTransforms(I)) | |||
1525 | return Common; | |||
1526 | ||||
1527 | { | |||
1528 | const APInt *Y; | |||
1529 | // X % -Y -> X % Y | |||
1530 | if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) { | |||
1531 | Worklist.AddValue(I.getOperand(1)); | |||
1532 | I.setOperand(1, ConstantInt::get(I.getType(), -*Y)); | |||
1533 | return &I; | |||
1534 | } | |||
1535 | } | |||
1536 | ||||
1537 | // If the sign bits of both operands are zero (i.e. we can prove they are | |||
1538 | // unsigned inputs), turn this into a urem. | |||
1539 | APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits())); | |||
1540 | if (MaskedValueIsZero(Op1, Mask, 0, &I) && | |||
1541 | MaskedValueIsZero(Op0, Mask, 0, &I)) { | |||
1542 | // X srem Y -> X urem Y, iff X and Y don't have sign bit set | |||
1543 | return BinaryOperator::CreateURem(Op0, Op1, I.getName()); | |||
1544 | } | |||
1545 | ||||
1546 | // If it's a constant vector, flip any negative values positive. | |||
1547 | if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { | |||
1548 | Constant *C = cast<Constant>(Op1); | |||
1549 | unsigned VWidth = C->getType()->getVectorNumElements(); | |||
1550 | ||||
1551 | bool hasNegative = false; | |||
1552 | bool hasMissing = false; | |||
1553 | for (unsigned i = 0; i != VWidth; ++i) { | |||
1554 | Constant *Elt = C->getAggregateElement(i); | |||
1555 | if (!Elt) { | |||
1556 | hasMissing = true; | |||
1557 | break; | |||
1558 | } | |||
1559 | ||||
1560 | if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) | |||
1561 | if (RHS->isNegative()) | |||
1562 | hasNegative = true; | |||
1563 | } | |||
1564 | ||||
1565 | if (hasNegative && !hasMissing) { | |||
1566 | SmallVector<Constant *, 16> Elts(VWidth); | |||
1567 | for (unsigned i = 0; i != VWidth; ++i) { | |||
1568 | Elts[i] = C->getAggregateElement(i); // Handle undef, etc. | |||
1569 | if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { | |||
1570 | if (RHS->isNegative()) | |||
1571 | Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); | |||
1572 | } | |||
1573 | } | |||
1574 | ||||
1575 | Constant *NewRHSV = ConstantVector::get(Elts); | |||
1576 | if (NewRHSV != C) { // Don't loop on -MININT | |||
1577 | Worklist.AddValue(I.getOperand(1)); | |||
1578 | I.setOperand(1, NewRHSV); | |||
1579 | return &I; | |||
1580 | } | |||
1581 | } | |||
1582 | } | |||
1583 | ||||
1584 | return nullptr; | |||
1585 | } | |||
1586 | ||||
1587 | Instruction *InstCombiner::visitFRem(BinaryOperator &I) { | |||
1588 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); | |||
1589 | ||||
1590 | if (Value *V = SimplifyVectorOp(I)) | |||
| ||||
1591 | return replaceInstUsesWith(I, V); | |||
1592 | ||||
1593 | if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(), | |||
1594 | SQ.getWithInstruction(&I))) | |||
1595 | return replaceInstUsesWith(I, V); | |||
1596 | ||||
1597 | // Handle cases involving: rem X, (select Cond, Y, Z) | |||
1598 | if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) | |||
1599 | return &I; | |||
1600 | ||||
1601 | return nullptr; | |||
1602 | } |