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