1 | //===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file implements the visit functions for add, fadd, sub, and fsub. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "InstCombineInternal.h" |
14 | #include "llvm/ADT/APFloat.h" |
15 | #include "llvm/ADT/APInt.h" |
16 | #include "llvm/ADT/STLExtras.h" |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/Analysis/InstructionSimplify.h" |
19 | #include "llvm/Analysis/ValueTracking.h" |
20 | #include "llvm/IR/Constant.h" |
21 | #include "llvm/IR/Constants.h" |
22 | #include "llvm/IR/InstrTypes.h" |
23 | #include "llvm/IR/Instruction.h" |
24 | #include "llvm/IR/Instructions.h" |
25 | #include "llvm/IR/Operator.h" |
26 | #include "llvm/IR/PatternMatch.h" |
27 | #include "llvm/IR/Type.h" |
28 | #include "llvm/IR/Value.h" |
29 | #include "llvm/Support/AlignOf.h" |
30 | #include "llvm/Support/Casting.h" |
31 | #include "llvm/Support/KnownBits.h" |
32 | #include "llvm/Transforms/InstCombine/InstCombiner.h" |
33 | #include <cassert> |
34 | #include <utility> |
35 | |
36 | using namespace llvm; |
37 | using namespace PatternMatch; |
38 | |
39 | #define DEBUG_TYPE "instcombine" |
40 | |
41 | namespace { |
42 | |
43 | /// Class representing coefficient of floating-point addend. |
44 | /// This class needs to be highly efficient, which is especially true for |
45 | /// the constructor. As of I write this comment, the cost of the default |
46 | /// constructor is merely 4-byte-store-zero (Assuming compiler is able to |
47 | /// perform write-merging). |
48 | /// |
49 | class FAddendCoef { |
50 | public: |
51 | // The constructor has to initialize a APFloat, which is unnecessary for |
52 | // most addends which have coefficient either 1 or -1. So, the constructor |
53 | // is expensive. In order to avoid the cost of the constructor, we should |
54 | // reuse some instances whenever possible. The pre-created instances |
55 | // FAddCombine::Add[0-5] embodies this idea. |
56 | FAddendCoef() = default; |
57 | ~FAddendCoef(); |
58 | |
59 | // If possible, don't define operator+/operator- etc because these |
60 | // operators inevitably call FAddendCoef's constructor which is not cheap. |
61 | void operator=(const FAddendCoef &A); |
62 | void operator+=(const FAddendCoef &A); |
63 | void operator*=(const FAddendCoef &S); |
64 | |
65 | void set(short C) { |
66 | assert(!insaneIntVal(C) && "Insane coefficient" ); |
67 | IsFp = false; IntVal = C; |
68 | } |
69 | |
70 | void set(const APFloat& C); |
71 | |
72 | void negate(); |
73 | |
74 | bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } |
75 | Value *getValue(Type *) const; |
76 | |
77 | bool isOne() const { return isInt() && IntVal == 1; } |
78 | bool isTwo() const { return isInt() && IntVal == 2; } |
79 | bool isMinusOne() const { return isInt() && IntVal == -1; } |
80 | bool isMinusTwo() const { return isInt() && IntVal == -2; } |
81 | |
82 | private: |
83 | bool insaneIntVal(int V) { return V > 4 || V < -4; } |
84 | |
85 | APFloat *getFpValPtr() { return reinterpret_cast<APFloat *>(&FpValBuf); } |
86 | |
87 | const APFloat *getFpValPtr() const { |
88 | return reinterpret_cast<const APFloat *>(&FpValBuf); |
89 | } |
90 | |
91 | const APFloat &getFpVal() const { |
92 | assert(IsFp && BufHasFpVal && "Incorret state" ); |
93 | return *getFpValPtr(); |
94 | } |
95 | |
96 | APFloat &getFpVal() { |
97 | assert(IsFp && BufHasFpVal && "Incorret state" ); |
98 | return *getFpValPtr(); |
99 | } |
100 | |
101 | bool isInt() const { return !IsFp; } |
102 | |
103 | // If the coefficient is represented by an integer, promote it to a |
104 | // floating point. |
105 | void convertToFpType(const fltSemantics &Sem); |
106 | |
107 | // Construct an APFloat from a signed integer. |
108 | // TODO: We should get rid of this function when APFloat can be constructed |
109 | // from an *SIGNED* integer. |
110 | APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); |
111 | |
112 | bool IsFp = false; |
113 | |
114 | // True iff FpValBuf contains an instance of APFloat. |
115 | bool BufHasFpVal = false; |
116 | |
117 | // The integer coefficient of an individual addend is either 1 or -1, |
118 | // and we try to simplify at most 4 addends from neighboring at most |
119 | // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt |
120 | // is overkill of this end. |
121 | short IntVal = 0; |
122 | |
123 | AlignedCharArrayUnion<APFloat> FpValBuf; |
124 | }; |
125 | |
126 | /// FAddend is used to represent floating-point addend. An addend is |
127 | /// represented as <C, V>, where the V is a symbolic value, and C is a |
128 | /// constant coefficient. A constant addend is represented as <C, 0>. |
129 | class FAddend { |
130 | public: |
131 | FAddend() = default; |
132 | |
133 | void operator+=(const FAddend &T) { |
134 | assert((Val == T.Val) && "Symbolic-values disagree" ); |
135 | Coeff += T.Coeff; |
136 | } |
137 | |
138 | Value *getSymVal() const { return Val; } |
139 | const FAddendCoef &getCoef() const { return Coeff; } |
140 | |
141 | bool isConstant() const { return Val == nullptr; } |
142 | bool isZero() const { return Coeff.isZero(); } |
143 | |
144 | void set(short Coefficient, Value *V) { |
145 | Coeff.set(Coefficient); |
146 | Val = V; |
147 | } |
148 | void set(const APFloat &Coefficient, Value *V) { |
149 | Coeff.set(Coefficient); |
150 | Val = V; |
151 | } |
152 | void set(const ConstantFP *Coefficient, Value *V) { |
153 | Coeff.set(Coefficient->getValueAPF()); |
154 | Val = V; |
155 | } |
156 | |
157 | void negate() { Coeff.negate(); } |
158 | |
159 | /// Drill down the U-D chain one step to find the definition of V, and |
160 | /// try to break the definition into one or two addends. |
161 | static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); |
162 | |
163 | /// Similar to FAddend::drillDownOneStep() except that the value being |
164 | /// splitted is the addend itself. |
165 | unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; |
166 | |
167 | private: |
168 | void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } |
169 | |
170 | // This addend has the value of "Coeff * Val". |
171 | Value *Val = nullptr; |
172 | FAddendCoef Coeff; |
173 | }; |
174 | |
175 | /// FAddCombine is the class for optimizing an unsafe fadd/fsub along |
176 | /// with its neighboring at most two instructions. |
177 | /// |
178 | class FAddCombine { |
179 | public: |
180 | FAddCombine(InstCombiner::BuilderTy &B) : Builder(B) {} |
181 | |
182 | Value *simplify(Instruction *FAdd); |
183 | |
184 | private: |
185 | using AddendVect = SmallVector<const FAddend *, 4>; |
186 | |
187 | Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); |
188 | |
189 | /// Convert given addend to a Value |
190 | Value *createAddendVal(const FAddend &A, bool& NeedNeg); |
191 | |
192 | /// Return the number of instructions needed to emit the N-ary addition. |
193 | unsigned calcInstrNumber(const AddendVect& Vect); |
194 | |
195 | Value *createFSub(Value *Opnd0, Value *Opnd1); |
196 | Value *createFAdd(Value *Opnd0, Value *Opnd1); |
197 | Value *createFMul(Value *Opnd0, Value *Opnd1); |
198 | Value *createFNeg(Value *V); |
199 | Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); |
200 | void createInstPostProc(Instruction *NewInst, bool NoNumber = false); |
201 | |
202 | // Debugging stuff are clustered here. |
203 | #ifndef NDEBUG |
204 | unsigned CreateInstrNum; |
205 | void initCreateInstNum() { CreateInstrNum = 0; } |
206 | void incCreateInstNum() { CreateInstrNum++; } |
207 | #else |
208 | void initCreateInstNum() {} |
209 | void incCreateInstNum() {} |
210 | #endif |
211 | |
212 | InstCombiner::BuilderTy &Builder; |
213 | Instruction *Instr = nullptr; |
214 | }; |
215 | |
216 | } // end anonymous namespace |
217 | |
218 | //===----------------------------------------------------------------------===// |
219 | // |
220 | // Implementation of |
221 | // {FAddendCoef, FAddend, FAddition, FAddCombine}. |
222 | // |
223 | //===----------------------------------------------------------------------===// |
224 | FAddendCoef::~FAddendCoef() { |
225 | if (BufHasFpVal) |
226 | getFpValPtr()->~APFloat(); |
227 | } |
228 | |
229 | void FAddendCoef::set(const APFloat& C) { |
230 | APFloat *P = getFpValPtr(); |
231 | |
232 | if (isInt()) { |
233 | // As the buffer is meanless byte stream, we cannot call |
234 | // APFloat::operator=(). |
235 | new(P) APFloat(C); |
236 | } else |
237 | *P = C; |
238 | |
239 | IsFp = BufHasFpVal = true; |
240 | } |
241 | |
242 | void FAddendCoef::convertToFpType(const fltSemantics &Sem) { |
243 | if (!isInt()) |
244 | return; |
245 | |
246 | APFloat *P = getFpValPtr(); |
247 | if (IntVal > 0) |
248 | new(P) APFloat(Sem, IntVal); |
249 | else { |
250 | new(P) APFloat(Sem, 0 - IntVal); |
251 | P->changeSign(); |
252 | } |
253 | IsFp = BufHasFpVal = true; |
254 | } |
255 | |
256 | APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { |
257 | if (Val >= 0) |
258 | return APFloat(Sem, Val); |
259 | |
260 | APFloat T(Sem, 0 - Val); |
261 | T.changeSign(); |
262 | |
263 | return T; |
264 | } |
265 | |
266 | void FAddendCoef::operator=(const FAddendCoef &That) { |
267 | if (That.isInt()) |
268 | set(That.IntVal); |
269 | else |
270 | set(That.getFpVal()); |
271 | } |
272 | |
273 | void FAddendCoef::operator+=(const FAddendCoef &That) { |
274 | RoundingMode RndMode = RoundingMode::NearestTiesToEven; |
275 | if (isInt() == That.isInt()) { |
276 | if (isInt()) |
277 | IntVal += That.IntVal; |
278 | else |
279 | getFpVal().add(RHS: That.getFpVal(), RM: RndMode); |
280 | return; |
281 | } |
282 | |
283 | if (isInt()) { |
284 | const APFloat &T = That.getFpVal(); |
285 | convertToFpType(Sem: T.getSemantics()); |
286 | getFpVal().add(RHS: T, RM: RndMode); |
287 | return; |
288 | } |
289 | |
290 | APFloat &T = getFpVal(); |
291 | T.add(RHS: createAPFloatFromInt(Sem: T.getSemantics(), Val: That.IntVal), RM: RndMode); |
292 | } |
293 | |
294 | void FAddendCoef::operator*=(const FAddendCoef &That) { |
295 | if (That.isOne()) |
296 | return; |
297 | |
298 | if (That.isMinusOne()) { |
299 | negate(); |
300 | return; |
301 | } |
302 | |
303 | if (isInt() && That.isInt()) { |
304 | int Res = IntVal * (int)That.IntVal; |
305 | assert(!insaneIntVal(Res) && "Insane int value" ); |
306 | IntVal = Res; |
307 | return; |
308 | } |
309 | |
310 | const fltSemantics &Semantic = |
311 | isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); |
312 | |
313 | if (isInt()) |
314 | convertToFpType(Sem: Semantic); |
315 | APFloat &F0 = getFpVal(); |
316 | |
317 | if (That.isInt()) |
318 | F0.multiply(RHS: createAPFloatFromInt(Sem: Semantic, Val: That.IntVal), |
319 | RM: APFloat::rmNearestTiesToEven); |
320 | else |
321 | F0.multiply(RHS: That.getFpVal(), RM: APFloat::rmNearestTiesToEven); |
322 | } |
323 | |
324 | void FAddendCoef::negate() { |
325 | if (isInt()) |
326 | IntVal = 0 - IntVal; |
327 | else |
328 | getFpVal().changeSign(); |
329 | } |
330 | |
331 | Value *FAddendCoef::getValue(Type *Ty) const { |
332 | return isInt() ? |
333 | ConstantFP::get(Ty, V: float(IntVal)) : |
334 | ConstantFP::get(Context&: Ty->getContext(), V: getFpVal()); |
335 | } |
336 | |
337 | // The definition of <Val> Addends |
338 | // ========================================= |
339 | // A + B <1, A>, <1,B> |
340 | // A - B <1, A>, <1,B> |
341 | // 0 - B <-1, B> |
342 | // C * A, <C, A> |
343 | // A + C <1, A> <C, NULL> |
344 | // 0 +/- 0 <0, NULL> (corner case) |
345 | // |
346 | // Legend: A and B are not constant, C is constant |
347 | unsigned FAddend::drillValueDownOneStep |
348 | (Value *Val, FAddend &Addend0, FAddend &Addend1) { |
349 | Instruction *I = nullptr; |
350 | if (!Val || !(I = dyn_cast<Instruction>(Val))) |
351 | return 0; |
352 | |
353 | unsigned Opcode = I->getOpcode(); |
354 | |
355 | if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { |
356 | ConstantFP *C0, *C1; |
357 | Value *Opnd0 = I->getOperand(i: 0); |
358 | Value *Opnd1 = I->getOperand(i: 1); |
359 | if ((C0 = dyn_cast<ConstantFP>(Val: Opnd0)) && C0->isZero()) |
360 | Opnd0 = nullptr; |
361 | |
362 | if ((C1 = dyn_cast<ConstantFP>(Val: Opnd1)) && C1->isZero()) |
363 | Opnd1 = nullptr; |
364 | |
365 | if (Opnd0) { |
366 | if (!C0) |
367 | Addend0.set(Coefficient: 1, V: Opnd0); |
368 | else |
369 | Addend0.set(Coefficient: C0, V: nullptr); |
370 | } |
371 | |
372 | if (Opnd1) { |
373 | FAddend &Addend = Opnd0 ? Addend1 : Addend0; |
374 | if (!C1) |
375 | Addend.set(Coefficient: 1, V: Opnd1); |
376 | else |
377 | Addend.set(Coefficient: C1, V: nullptr); |
378 | if (Opcode == Instruction::FSub) |
379 | Addend.negate(); |
380 | } |
381 | |
382 | if (Opnd0 || Opnd1) |
383 | return Opnd0 && Opnd1 ? 2 : 1; |
384 | |
385 | // Both operands are zero. Weird! |
386 | Addend0.set(Coefficient: APFloat(C0->getValueAPF().getSemantics()), V: nullptr); |
387 | return 1; |
388 | } |
389 | |
390 | if (I->getOpcode() == Instruction::FMul) { |
391 | Value *V0 = I->getOperand(i: 0); |
392 | Value *V1 = I->getOperand(i: 1); |
393 | if (ConstantFP *C = dyn_cast<ConstantFP>(Val: V0)) { |
394 | Addend0.set(Coefficient: C, V: V1); |
395 | return 1; |
396 | } |
397 | |
398 | if (ConstantFP *C = dyn_cast<ConstantFP>(Val: V1)) { |
399 | Addend0.set(Coefficient: C, V: V0); |
400 | return 1; |
401 | } |
402 | } |
403 | |
404 | return 0; |
405 | } |
406 | |
407 | // Try to break *this* addend into two addends. e.g. Suppose this addend is |
408 | // <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, |
409 | // i.e. <2.3, X> and <2.3, Y>. |
410 | unsigned FAddend::drillAddendDownOneStep |
411 | (FAddend &Addend0, FAddend &Addend1) const { |
412 | if (isConstant()) |
413 | return 0; |
414 | |
415 | unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); |
416 | if (!BreakNum || Coeff.isOne()) |
417 | return BreakNum; |
418 | |
419 | Addend0.Scale(ScaleAmt: Coeff); |
420 | |
421 | if (BreakNum == 2) |
422 | Addend1.Scale(ScaleAmt: Coeff); |
423 | |
424 | return BreakNum; |
425 | } |
426 | |
427 | Value *FAddCombine::simplify(Instruction *I) { |
428 | assert(I->hasAllowReassoc() && I->hasNoSignedZeros() && |
429 | "Expected 'reassoc'+'nsz' instruction" ); |
430 | |
431 | // Currently we are not able to handle vector type. |
432 | if (I->getType()->isVectorTy()) |
433 | return nullptr; |
434 | |
435 | assert((I->getOpcode() == Instruction::FAdd || |
436 | I->getOpcode() == Instruction::FSub) && "Expect add/sub" ); |
437 | |
438 | // Save the instruction before calling other member-functions. |
439 | Instr = I; |
440 | |
441 | FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; |
442 | |
443 | unsigned OpndNum = FAddend::drillValueDownOneStep(Val: I, Addend0&: Opnd0, Addend1&: Opnd1); |
444 | |
445 | // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. |
446 | unsigned Opnd0_ExpNum = 0; |
447 | unsigned Opnd1_ExpNum = 0; |
448 | |
449 | if (!Opnd0.isConstant()) |
450 | Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Addend0&: Opnd0_0, Addend1&: Opnd0_1); |
451 | |
452 | // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. |
453 | if (OpndNum == 2 && !Opnd1.isConstant()) |
454 | Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Addend0&: Opnd1_0, Addend1&: Opnd1_1); |
455 | |
456 | // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 |
457 | if (Opnd0_ExpNum && Opnd1_ExpNum) { |
458 | AddendVect AllOpnds; |
459 | AllOpnds.push_back(Elt: &Opnd0_0); |
460 | AllOpnds.push_back(Elt: &Opnd1_0); |
461 | if (Opnd0_ExpNum == 2) |
462 | AllOpnds.push_back(Elt: &Opnd0_1); |
463 | if (Opnd1_ExpNum == 2) |
464 | AllOpnds.push_back(Elt: &Opnd1_1); |
465 | |
466 | // Compute instruction quota. We should save at least one instruction. |
467 | unsigned InstQuota = 0; |
468 | |
469 | Value *V0 = I->getOperand(i: 0); |
470 | Value *V1 = I->getOperand(i: 1); |
471 | InstQuota = ((!isa<Constant>(Val: V0) && V0->hasOneUse()) && |
472 | (!isa<Constant>(Val: V1) && V1->hasOneUse())) ? 2 : 1; |
473 | |
474 | if (Value *R = simplifyFAdd(V&: AllOpnds, InstrQuota: InstQuota)) |
475 | return R; |
476 | } |
477 | |
478 | if (OpndNum != 2) { |
479 | // The input instruction is : "I=0.0 +/- V". If the "V" were able to be |
480 | // splitted into two addends, say "V = X - Y", the instruction would have |
481 | // been optimized into "I = Y - X" in the previous steps. |
482 | // |
483 | const FAddendCoef &CE = Opnd0.getCoef(); |
484 | return CE.isOne() ? Opnd0.getSymVal() : nullptr; |
485 | } |
486 | |
487 | // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] |
488 | if (Opnd1_ExpNum) { |
489 | AddendVect AllOpnds; |
490 | AllOpnds.push_back(Elt: &Opnd0); |
491 | AllOpnds.push_back(Elt: &Opnd1_0); |
492 | if (Opnd1_ExpNum == 2) |
493 | AllOpnds.push_back(Elt: &Opnd1_1); |
494 | |
495 | if (Value *R = simplifyFAdd(V&: AllOpnds, InstrQuota: 1)) |
496 | return R; |
497 | } |
498 | |
499 | // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] |
500 | if (Opnd0_ExpNum) { |
501 | AddendVect AllOpnds; |
502 | AllOpnds.push_back(Elt: &Opnd1); |
503 | AllOpnds.push_back(Elt: &Opnd0_0); |
504 | if (Opnd0_ExpNum == 2) |
505 | AllOpnds.push_back(Elt: &Opnd0_1); |
506 | |
507 | if (Value *R = simplifyFAdd(V&: AllOpnds, InstrQuota: 1)) |
508 | return R; |
509 | } |
510 | |
511 | return nullptr; |
512 | } |
513 | |
514 | Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { |
515 | unsigned AddendNum = Addends.size(); |
516 | assert(AddendNum <= 4 && "Too many addends" ); |
517 | |
518 | // For saving intermediate results; |
519 | unsigned NextTmpIdx = 0; |
520 | FAddend TmpResult[3]; |
521 | |
522 | // Simplified addends are placed <SimpVect>. |
523 | AddendVect SimpVect; |
524 | |
525 | // The outer loop works on one symbolic-value at a time. Suppose the input |
526 | // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... |
527 | // The symbolic-values will be processed in this order: x, y, z. |
528 | for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { |
529 | |
530 | const FAddend *ThisAddend = Addends[SymIdx]; |
531 | if (!ThisAddend) { |
532 | // This addend was processed before. |
533 | continue; |
534 | } |
535 | |
536 | Value *Val = ThisAddend->getSymVal(); |
537 | |
538 | // If the resulting expr has constant-addend, this constant-addend is |
539 | // desirable to reside at the top of the resulting expression tree. Placing |
540 | // constant close to super-expr(s) will potentially reveal some |
541 | // optimization opportunities in super-expr(s). Here we do not implement |
542 | // this logic intentionally and rely on SimplifyAssociativeOrCommutative |
543 | // call later. |
544 | |
545 | unsigned StartIdx = SimpVect.size(); |
546 | SimpVect.push_back(Elt: ThisAddend); |
547 | |
548 | // The inner loop collects addends sharing same symbolic-value, and these |
549 | // addends will be later on folded into a single addend. Following above |
550 | // example, if the symbolic value "y" is being processed, the inner loop |
551 | // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will |
552 | // be later on folded into "<b1+b2, y>". |
553 | for (unsigned SameSymIdx = SymIdx + 1; |
554 | SameSymIdx < AddendNum; SameSymIdx++) { |
555 | const FAddend *T = Addends[SameSymIdx]; |
556 | if (T && T->getSymVal() == Val) { |
557 | // Set null such that next iteration of the outer loop will not process |
558 | // this addend again. |
559 | Addends[SameSymIdx] = nullptr; |
560 | SimpVect.push_back(Elt: T); |
561 | } |
562 | } |
563 | |
564 | // If multiple addends share same symbolic value, fold them together. |
565 | if (StartIdx + 1 != SimpVect.size()) { |
566 | FAddend &R = TmpResult[NextTmpIdx ++]; |
567 | R = *SimpVect[StartIdx]; |
568 | for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) |
569 | R += *SimpVect[Idx]; |
570 | |
571 | // Pop all addends being folded and push the resulting folded addend. |
572 | SimpVect.resize(N: StartIdx); |
573 | if (!R.isZero()) { |
574 | SimpVect.push_back(Elt: &R); |
575 | } |
576 | } |
577 | } |
578 | |
579 | assert((NextTmpIdx <= std::size(TmpResult) + 1) && "out-of-bound access" ); |
580 | |
581 | Value *Result; |
582 | if (!SimpVect.empty()) |
583 | Result = createNaryFAdd(Opnds: SimpVect, InstrQuota); |
584 | else { |
585 | // The addition is folded to 0.0. |
586 | Result = ConstantFP::get(Ty: Instr->getType(), V: 0.0); |
587 | } |
588 | |
589 | return Result; |
590 | } |
591 | |
592 | Value *FAddCombine::createNaryFAdd |
593 | (const AddendVect &Opnds, unsigned InstrQuota) { |
594 | assert(!Opnds.empty() && "Expect at least one addend" ); |
595 | |
596 | // Step 1: Check if the # of instructions needed exceeds the quota. |
597 | |
598 | unsigned InstrNeeded = calcInstrNumber(Vect: Opnds); |
599 | if (InstrNeeded > InstrQuota) |
600 | return nullptr; |
601 | |
602 | initCreateInstNum(); |
603 | |
604 | // step 2: Emit the N-ary addition. |
605 | // Note that at most three instructions are involved in Fadd-InstCombine: the |
606 | // addition in question, and at most two neighboring instructions. |
607 | // The resulting optimized addition should have at least one less instruction |
608 | // than the original addition expression tree. This implies that the resulting |
609 | // N-ary addition has at most two instructions, and we don't need to worry |
610 | // about tree-height when constructing the N-ary addition. |
611 | |
612 | Value *LastVal = nullptr; |
613 | bool LastValNeedNeg = false; |
614 | |
615 | // Iterate the addends, creating fadd/fsub using adjacent two addends. |
616 | for (const FAddend *Opnd : Opnds) { |
617 | bool NeedNeg; |
618 | Value *V = createAddendVal(A: *Opnd, NeedNeg); |
619 | if (!LastVal) { |
620 | LastVal = V; |
621 | LastValNeedNeg = NeedNeg; |
622 | continue; |
623 | } |
624 | |
625 | if (LastValNeedNeg == NeedNeg) { |
626 | LastVal = createFAdd(Opnd0: LastVal, Opnd1: V); |
627 | continue; |
628 | } |
629 | |
630 | if (LastValNeedNeg) |
631 | LastVal = createFSub(Opnd0: V, Opnd1: LastVal); |
632 | else |
633 | LastVal = createFSub(Opnd0: LastVal, Opnd1: V); |
634 | |
635 | LastValNeedNeg = false; |
636 | } |
637 | |
638 | if (LastValNeedNeg) { |
639 | LastVal = createFNeg(V: LastVal); |
640 | } |
641 | |
642 | #ifndef NDEBUG |
643 | assert(CreateInstrNum == InstrNeeded && |
644 | "Inconsistent in instruction numbers" ); |
645 | #endif |
646 | |
647 | return LastVal; |
648 | } |
649 | |
650 | Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) { |
651 | Value *V = Builder.CreateFSub(L: Opnd0, R: Opnd1); |
652 | if (Instruction *I = dyn_cast<Instruction>(Val: V)) |
653 | createInstPostProc(NewInst: I); |
654 | return V; |
655 | } |
656 | |
657 | Value *FAddCombine::createFNeg(Value *V) { |
658 | Value *NewV = Builder.CreateFNeg(V); |
659 | if (Instruction *I = dyn_cast<Instruction>(Val: NewV)) |
660 | createInstPostProc(NewInst: I, NoNumber: true); // fneg's don't receive instruction numbers. |
661 | return NewV; |
662 | } |
663 | |
664 | Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) { |
665 | Value *V = Builder.CreateFAdd(L: Opnd0, R: Opnd1); |
666 | if (Instruction *I = dyn_cast<Instruction>(Val: V)) |
667 | createInstPostProc(NewInst: I); |
668 | return V; |
669 | } |
670 | |
671 | Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { |
672 | Value *V = Builder.CreateFMul(L: Opnd0, R: Opnd1); |
673 | if (Instruction *I = dyn_cast<Instruction>(Val: V)) |
674 | createInstPostProc(NewInst: I); |
675 | return V; |
676 | } |
677 | |
678 | void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) { |
679 | NewInstr->setDebugLoc(Instr->getDebugLoc()); |
680 | |
681 | // Keep track of the number of instruction created. |
682 | if (!NoNumber) |
683 | incCreateInstNum(); |
684 | |
685 | // Propagate fast-math flags |
686 | NewInstr->setFastMathFlags(Instr->getFastMathFlags()); |
687 | } |
688 | |
689 | // Return the number of instruction needed to emit the N-ary addition. |
690 | // NOTE: Keep this function in sync with createAddendVal(). |
691 | unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { |
692 | unsigned OpndNum = Opnds.size(); |
693 | unsigned InstrNeeded = OpndNum - 1; |
694 | |
695 | // Adjust the number of instructions needed to emit the N-ary add. |
696 | for (const FAddend *Opnd : Opnds) { |
697 | if (Opnd->isConstant()) |
698 | continue; |
699 | |
700 | // The constant check above is really for a few special constant |
701 | // coefficients. |
702 | if (isa<UndefValue>(Val: Opnd->getSymVal())) |
703 | continue; |
704 | |
705 | const FAddendCoef &CE = Opnd->getCoef(); |
706 | // Let the addend be "c * x". If "c == +/-1", the value of the addend |
707 | // is immediately available; otherwise, it needs exactly one instruction |
708 | // to evaluate the value. |
709 | if (!CE.isMinusOne() && !CE.isOne()) |
710 | InstrNeeded++; |
711 | } |
712 | return InstrNeeded; |
713 | } |
714 | |
715 | // Input Addend Value NeedNeg(output) |
716 | // ================================================================ |
717 | // Constant C C false |
718 | // <+/-1, V> V coefficient is -1 |
719 | // <2/-2, V> "fadd V, V" coefficient is -2 |
720 | // <C, V> "fmul V, C" false |
721 | // |
722 | // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. |
723 | Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) { |
724 | const FAddendCoef &Coeff = Opnd.getCoef(); |
725 | |
726 | if (Opnd.isConstant()) { |
727 | NeedNeg = false; |
728 | return Coeff.getValue(Ty: Instr->getType()); |
729 | } |
730 | |
731 | Value *OpndVal = Opnd.getSymVal(); |
732 | |
733 | if (Coeff.isMinusOne() || Coeff.isOne()) { |
734 | NeedNeg = Coeff.isMinusOne(); |
735 | return OpndVal; |
736 | } |
737 | |
738 | if (Coeff.isTwo() || Coeff.isMinusTwo()) { |
739 | NeedNeg = Coeff.isMinusTwo(); |
740 | return createFAdd(Opnd0: OpndVal, Opnd1: OpndVal); |
741 | } |
742 | |
743 | NeedNeg = false; |
744 | return createFMul(Opnd0: OpndVal, Opnd1: Coeff.getValue(Ty: Instr->getType())); |
745 | } |
746 | |
747 | // Checks if any operand is negative and we can convert add to sub. |
748 | // This function checks for following negative patterns |
749 | // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) |
750 | // ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C)) |
751 | // XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even |
752 | static Value *checkForNegativeOperand(BinaryOperator &I, |
753 | InstCombiner::BuilderTy &Builder) { |
754 | Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1); |
755 | |
756 | // This function creates 2 instructions to replace ADD, we need at least one |
757 | // of LHS or RHS to have one use to ensure benefit in transform. |
758 | if (!LHS->hasOneUse() && !RHS->hasOneUse()) |
759 | return nullptr; |
760 | |
761 | Value *X = nullptr, *Y = nullptr, *Z = nullptr; |
762 | const APInt *C1 = nullptr, *C2 = nullptr; |
763 | |
764 | // if ONE is on other side, swap |
765 | if (match(V: RHS, P: m_Add(L: m_Value(V&: X), R: m_One()))) |
766 | std::swap(a&: LHS, b&: RHS); |
767 | |
768 | if (match(V: LHS, P: m_Add(L: m_Value(V&: X), R: m_One()))) { |
769 | // if XOR on other side, swap |
770 | if (match(V: RHS, P: m_Xor(L: m_Value(V&: Y), R: m_APInt(Res&: C1)))) |
771 | std::swap(a&: X, b&: RHS); |
772 | |
773 | if (match(V: X, P: m_Xor(L: m_Value(V&: Y), R: m_APInt(Res&: C1)))) { |
774 | // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1)) |
775 | // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1)) |
776 | if (match(V: Y, P: m_Or(L: m_Value(V&: Z), R: m_APInt(Res&: C2))) && (*C2 == ~(*C1))) { |
777 | Value *NewAnd = Builder.CreateAnd(LHS: Z, RHS: *C1); |
778 | return Builder.CreateSub(LHS: RHS, RHS: NewAnd, Name: "sub" ); |
779 | } else if (match(V: Y, P: m_And(L: m_Value(V&: Z), R: m_APInt(Res&: C2))) && (*C1 == *C2)) { |
780 | // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1)) |
781 | // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1)) |
782 | Value *NewOr = Builder.CreateOr(LHS: Z, RHS: ~(*C1)); |
783 | return Builder.CreateSub(LHS: RHS, RHS: NewOr, Name: "sub" ); |
784 | } |
785 | } |
786 | } |
787 | |
788 | // Restore LHS and RHS |
789 | LHS = I.getOperand(i_nocapture: 0); |
790 | RHS = I.getOperand(i_nocapture: 1); |
791 | |
792 | // if XOR is on other side, swap |
793 | if (match(V: RHS, P: m_Xor(L: m_Value(V&: Y), R: m_APInt(Res&: C1)))) |
794 | std::swap(a&: LHS, b&: RHS); |
795 | |
796 | // C2 is ODD |
797 | // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2)) |
798 | // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2)) |
799 | if (match(V: LHS, P: m_Xor(L: m_Value(V&: Y), R: m_APInt(Res&: C1)))) |
800 | if (C1->countr_zero() == 0) |
801 | if (match(V: Y, P: m_And(L: m_Value(V&: Z), R: m_APInt(Res&: C2))) && *C1 == (*C2 + 1)) { |
802 | Value *NewOr = Builder.CreateOr(LHS: Z, RHS: ~(*C2)); |
803 | return Builder.CreateSub(LHS: RHS, RHS: NewOr, Name: "sub" ); |
804 | } |
805 | return nullptr; |
806 | } |
807 | |
808 | /// Wrapping flags may allow combining constants separated by an extend. |
809 | static Instruction *foldNoWrapAdd(BinaryOperator &Add, |
810 | InstCombiner::BuilderTy &Builder) { |
811 | Value *Op0 = Add.getOperand(i_nocapture: 0), *Op1 = Add.getOperand(i_nocapture: 1); |
812 | Type *Ty = Add.getType(); |
813 | Constant *Op1C; |
814 | if (!match(V: Op1, P: m_Constant(C&: Op1C))) |
815 | return nullptr; |
816 | |
817 | // Try this match first because it results in an add in the narrow type. |
818 | // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1))) |
819 | Value *X; |
820 | const APInt *C1, *C2; |
821 | if (match(V: Op1, P: m_APInt(Res&: C1)) && |
822 | match(V: Op0, P: m_OneUse(SubPattern: m_ZExt(Op: m_NUWAddLike(L: m_Value(V&: X), R: m_APInt(Res&: C2))))) && |
823 | C1->isNegative() && C1->sge(RHS: -C2->sext(width: C1->getBitWidth()))) { |
824 | Constant *NewC = |
825 | ConstantInt::get(Ty: X->getType(), V: *C2 + C1->trunc(width: C2->getBitWidth())); |
826 | return new ZExtInst(Builder.CreateNUWAdd(LHS: X, RHS: NewC), Ty); |
827 | } |
828 | |
829 | // More general combining of constants in the wide type. |
830 | // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C) |
831 | // or (zext nneg (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C) |
832 | Constant *NarrowC; |
833 | if (match(V: Op0, P: m_OneUse(SubPattern: m_SExtLike( |
834 | Op: m_NSWAddLike(L: m_Value(V&: X), R: m_Constant(C&: NarrowC)))))) { |
835 | Value *WideC = Builder.CreateSExt(V: NarrowC, DestTy: Ty); |
836 | Value *NewC = Builder.CreateAdd(LHS: WideC, RHS: Op1C); |
837 | Value *WideX = Builder.CreateSExt(V: X, DestTy: Ty); |
838 | return BinaryOperator::CreateAdd(V1: WideX, V2: NewC); |
839 | } |
840 | // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C) |
841 | if (match(V: Op0, |
842 | P: m_OneUse(SubPattern: m_ZExt(Op: m_NUWAddLike(L: m_Value(V&: X), R: m_Constant(C&: NarrowC)))))) { |
843 | Value *WideC = Builder.CreateZExt(V: NarrowC, DestTy: Ty); |
844 | Value *NewC = Builder.CreateAdd(LHS: WideC, RHS: Op1C); |
845 | Value *WideX = Builder.CreateZExt(V: X, DestTy: Ty); |
846 | return BinaryOperator::CreateAdd(V1: WideX, V2: NewC); |
847 | } |
848 | return nullptr; |
849 | } |
850 | |
851 | Instruction *InstCombinerImpl::foldAddWithConstant(BinaryOperator &Add) { |
852 | Value *Op0 = Add.getOperand(i_nocapture: 0), *Op1 = Add.getOperand(i_nocapture: 1); |
853 | Type *Ty = Add.getType(); |
854 | Constant *Op1C; |
855 | if (!match(V: Op1, P: m_ImmConstant(C&: Op1C))) |
856 | return nullptr; |
857 | |
858 | if (Instruction *NV = foldBinOpIntoSelectOrPhi(I&: Add)) |
859 | return NV; |
860 | |
861 | Value *X; |
862 | Constant *Op00C; |
863 | |
864 | // add (sub C1, X), C2 --> sub (add C1, C2), X |
865 | if (match(V: Op0, P: m_Sub(L: m_Constant(C&: Op00C), R: m_Value(V&: X)))) |
866 | return BinaryOperator::CreateSub(V1: ConstantExpr::getAdd(C1: Op00C, C2: Op1C), V2: X); |
867 | |
868 | Value *Y; |
869 | |
870 | // add (sub X, Y), -1 --> add (not Y), X |
871 | if (match(V: Op0, P: m_OneUse(SubPattern: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Y)))) && |
872 | match(V: Op1, P: m_AllOnes())) |
873 | return BinaryOperator::CreateAdd(V1: Builder.CreateNot(V: Y), V2: X); |
874 | |
875 | // zext(bool) + C -> bool ? C + 1 : C |
876 | if (match(V: Op0, P: m_ZExt(Op: m_Value(V&: X))) && |
877 | X->getType()->getScalarSizeInBits() == 1) |
878 | return SelectInst::Create(C: X, S1: InstCombiner::AddOne(C: Op1C), S2: Op1); |
879 | // sext(bool) + C -> bool ? C - 1 : C |
880 | if (match(V: Op0, P: m_SExt(Op: m_Value(V&: X))) && |
881 | X->getType()->getScalarSizeInBits() == 1) |
882 | return SelectInst::Create(C: X, S1: InstCombiner::SubOne(C: Op1C), S2: Op1); |
883 | |
884 | // ~X + C --> (C-1) - X |
885 | if (match(V: Op0, P: m_Not(V: m_Value(V&: X)))) { |
886 | // ~X + C has NSW and (C-1) won't oveflow => (C-1)-X can have NSW |
887 | auto *COne = ConstantInt::get(Ty: Op1C->getType(), V: 1); |
888 | bool WillNotSOV = willNotOverflowSignedSub(LHS: Op1C, RHS: COne, CxtI: Add); |
889 | BinaryOperator *Res = |
890 | BinaryOperator::CreateSub(V1: ConstantExpr::getSub(C1: Op1C, C2: COne), V2: X); |
891 | Res->setHasNoSignedWrap(Add.hasNoSignedWrap() && WillNotSOV); |
892 | return Res; |
893 | } |
894 | |
895 | // (iN X s>> (N - 1)) + 1 --> zext (X > -1) |
896 | const APInt *C; |
897 | unsigned BitWidth = Ty->getScalarSizeInBits(); |
898 | if (match(V: Op0, P: m_OneUse(SubPattern: m_AShr(L: m_Value(V&: X), |
899 | R: m_SpecificIntAllowPoison(V: BitWidth - 1)))) && |
900 | match(V: Op1, P: m_One())) |
901 | return new ZExtInst(Builder.CreateIsNotNeg(Arg: X, Name: "isnotneg" ), Ty); |
902 | |
903 | if (!match(V: Op1, P: m_APInt(Res&: C))) |
904 | return nullptr; |
905 | |
906 | // (X | Op01C) + Op1C --> X + (Op01C + Op1C) iff the `or` is actually an `add` |
907 | Constant *Op01C; |
908 | if (match(V: Op0, P: m_DisjointOr(L: m_Value(V&: X), R: m_ImmConstant(C&: Op01C)))) |
909 | return BinaryOperator::CreateAdd(V1: X, V2: ConstantExpr::getAdd(C1: Op01C, C2: Op1C)); |
910 | |
911 | // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C) |
912 | const APInt *C2; |
913 | if (match(V: Op0, P: m_Or(L: m_Value(), R: m_APInt(Res&: C2))) && *C2 == -*C) |
914 | return BinaryOperator::CreateXor(V1: Op0, V2: ConstantInt::get(Ty: Add.getType(), V: *C2)); |
915 | |
916 | if (C->isSignMask()) { |
917 | // If wrapping is not allowed, then the addition must set the sign bit: |
918 | // X + (signmask) --> X | signmask |
919 | if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap()) |
920 | return BinaryOperator::CreateOr(V1: Op0, V2: Op1); |
921 | |
922 | // If wrapping is allowed, then the addition flips the sign bit of LHS: |
923 | // X + (signmask) --> X ^ signmask |
924 | return BinaryOperator::CreateXor(V1: Op0, V2: Op1); |
925 | } |
926 | |
927 | // Is this add the last step in a convoluted sext? |
928 | // add(zext(xor i16 X, -32768), -32768) --> sext X |
929 | if (match(V: Op0, P: m_ZExt(Op: m_Xor(L: m_Value(V&: X), R: m_APInt(Res&: C2)))) && |
930 | C2->isMinSignedValue() && C2->sext(width: Ty->getScalarSizeInBits()) == *C) |
931 | return CastInst::Create(Instruction::SExt, S: X, Ty); |
932 | |
933 | if (match(V: Op0, P: m_Xor(L: m_Value(V&: X), R: m_APInt(Res&: C2)))) { |
934 | // (X ^ signmask) + C --> (X + (signmask ^ C)) |
935 | if (C2->isSignMask()) |
936 | return BinaryOperator::CreateAdd(V1: X, V2: ConstantInt::get(Ty, V: *C2 ^ *C)); |
937 | |
938 | // If X has no high-bits set above an xor mask: |
939 | // add (xor X, LowMaskC), C --> sub (LowMaskC + C), X |
940 | if (C2->isMask()) { |
941 | KnownBits LHSKnown = computeKnownBits(V: X, Depth: 0, CxtI: &Add); |
942 | if ((*C2 | LHSKnown.Zero).isAllOnes()) |
943 | return BinaryOperator::CreateSub(V1: ConstantInt::get(Ty, V: *C2 + *C), V2: X); |
944 | } |
945 | |
946 | // Look for a math+logic pattern that corresponds to sext-in-register of a |
947 | // value with cleared high bits. Convert that into a pair of shifts: |
948 | // add (xor X, 0x80), 0xF..F80 --> (X << ShAmtC) >>s ShAmtC |
949 | // add (xor X, 0xF..F80), 0x80 --> (X << ShAmtC) >>s ShAmtC |
950 | if (Op0->hasOneUse() && *C2 == -(*C)) { |
951 | unsigned BitWidth = Ty->getScalarSizeInBits(); |
952 | unsigned ShAmt = 0; |
953 | if (C->isPowerOf2()) |
954 | ShAmt = BitWidth - C->logBase2() - 1; |
955 | else if (C2->isPowerOf2()) |
956 | ShAmt = BitWidth - C2->logBase2() - 1; |
957 | if (ShAmt && MaskedValueIsZero(V: X, Mask: APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShAmt), |
958 | Depth: 0, CxtI: &Add)) { |
959 | Constant *ShAmtC = ConstantInt::get(Ty, V: ShAmt); |
960 | Value *NewShl = Builder.CreateShl(LHS: X, RHS: ShAmtC, Name: "sext" ); |
961 | return BinaryOperator::CreateAShr(V1: NewShl, V2: ShAmtC); |
962 | } |
963 | } |
964 | } |
965 | |
966 | if (C->isOne() && Op0->hasOneUse()) { |
967 | // add (sext i1 X), 1 --> zext (not X) |
968 | // TODO: The smallest IR representation is (select X, 0, 1), and that would |
969 | // not require the one-use check. But we need to remove a transform in |
970 | // visitSelect and make sure that IR value tracking for select is equal or |
971 | // better than for these ops. |
972 | if (match(V: Op0, P: m_SExt(Op: m_Value(V&: X))) && |
973 | X->getType()->getScalarSizeInBits() == 1) |
974 | return new ZExtInst(Builder.CreateNot(V: X), Ty); |
975 | |
976 | // Shifts and add used to flip and mask off the low bit: |
977 | // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1 |
978 | const APInt *C3; |
979 | if (match(V: Op0, P: m_AShr(L: m_Shl(L: m_Value(V&: X), R: m_APInt(Res&: C2)), R: m_APInt(Res&: C3))) && |
980 | C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) { |
981 | Value *NotX = Builder.CreateNot(V: X); |
982 | return BinaryOperator::CreateAnd(V1: NotX, V2: ConstantInt::get(Ty, V: 1)); |
983 | } |
984 | } |
985 | |
986 | // Fold (add (zext (add X, -1)), 1) -> (zext X) if X is non-zero. |
987 | // TODO: There's a general form for any constant on the outer add. |
988 | if (C->isOne()) { |
989 | if (match(V: Op0, P: m_ZExt(Op: m_Add(L: m_Value(V&: X), R: m_AllOnes())))) { |
990 | const SimplifyQuery Q = SQ.getWithInstruction(I: &Add); |
991 | if (llvm::isKnownNonZero(V: X, Q)) |
992 | return new ZExtInst(X, Ty); |
993 | } |
994 | } |
995 | |
996 | return nullptr; |
997 | } |
998 | |
999 | // match variations of a^2 + 2*a*b + b^2 |
1000 | // |
1001 | // to reuse the code between the FP and Int versions, the instruction OpCodes |
1002 | // and constant types have been turned into template parameters. |
1003 | // |
1004 | // Mul2Rhs: The constant to perform the multiplicative equivalent of X*2 with; |
1005 | // should be `m_SpecificFP(2.0)` for FP and `m_SpecificInt(1)` for Int |
1006 | // (we're matching `X<<1` instead of `X*2` for Int) |
1007 | template <bool FP, typename Mul2Rhs> |
1008 | static bool matchesSquareSum(BinaryOperator &I, Mul2Rhs M2Rhs, Value *&A, |
1009 | Value *&B) { |
1010 | constexpr unsigned MulOp = FP ? Instruction::FMul : Instruction::Mul; |
1011 | constexpr unsigned AddOp = FP ? Instruction::FAdd : Instruction::Add; |
1012 | constexpr unsigned Mul2Op = FP ? Instruction::FMul : Instruction::Shl; |
1013 | |
1014 | // (a * a) + (((a * 2) + b) * b) |
1015 | if (match(&I, m_c_BinOp( |
1016 | AddOp, m_OneUse(SubPattern: m_BinOp(Opcode: MulOp, L: m_Value(V&: A), R: m_Deferred(V: A))), |
1017 | m_OneUse(m_BinOp( |
1018 | MulOp, |
1019 | m_c_BinOp(AddOp, m_BinOp(Mul2Op, m_Deferred(V: A), M2Rhs), |
1020 | m_Value(V&: B)), |
1021 | m_Deferred(V: B)))))) |
1022 | return true; |
1023 | |
1024 | // ((a * b) * 2) or ((a * 2) * b) |
1025 | // + |
1026 | // (a * a + b * b) or (b * b + a * a) |
1027 | return match( |
1028 | &I, |
1029 | m_c_BinOp(AddOp, |
1030 | m_CombineOr( |
1031 | m_OneUse(m_BinOp( |
1032 | Mul2Op, m_BinOp(Opcode: MulOp, L: m_Value(V&: A), R: m_Value(V&: B)), M2Rhs)), |
1033 | m_OneUse(m_BinOp(MulOp, m_BinOp(Mul2Op, m_Value(V&: A), M2Rhs), |
1034 | m_Value(V&: B)))), |
1035 | m_OneUse(SubPattern: m_c_BinOp( |
1036 | Opcode: AddOp, L: m_BinOp(Opcode: MulOp, L: m_Deferred(V: A), R: m_Deferred(V: A)), |
1037 | R: m_BinOp(Opcode: MulOp, L: m_Deferred(V: B), R: m_Deferred(V: B)))))); |
1038 | } |
1039 | |
1040 | // Fold integer variations of a^2 + 2*a*b + b^2 -> (a + b)^2 |
1041 | Instruction *InstCombinerImpl::foldSquareSumInt(BinaryOperator &I) { |
1042 | Value *A, *B; |
1043 | if (matchesSquareSum</*FP*/ false>(I, M2Rhs: m_SpecificInt(V: 1), A, B)) { |
1044 | Value *AB = Builder.CreateAdd(LHS: A, RHS: B); |
1045 | return BinaryOperator::CreateMul(V1: AB, V2: AB); |
1046 | } |
1047 | return nullptr; |
1048 | } |
1049 | |
1050 | // Fold floating point variations of a^2 + 2*a*b + b^2 -> (a + b)^2 |
1051 | // Requires `nsz` and `reassoc`. |
1052 | Instruction *InstCombinerImpl::foldSquareSumFP(BinaryOperator &I) { |
1053 | assert(I.hasAllowReassoc() && I.hasNoSignedZeros() && "Assumption mismatch" ); |
1054 | Value *A, *B; |
1055 | if (matchesSquareSum</*FP*/ true>(I, M2Rhs: m_SpecificFP(V: 2.0), A, B)) { |
1056 | Value *AB = Builder.CreateFAddFMF(L: A, R: B, FMFSource: &I); |
1057 | return BinaryOperator::CreateFMulFMF(V1: AB, V2: AB, FMFSource: &I); |
1058 | } |
1059 | return nullptr; |
1060 | } |
1061 | |
1062 | // Matches multiplication expression Op * C where C is a constant. Returns the |
1063 | // constant value in C and the other operand in Op. Returns true if such a |
1064 | // match is found. |
1065 | static bool MatchMul(Value *E, Value *&Op, APInt &C) { |
1066 | const APInt *AI; |
1067 | if (match(V: E, P: m_Mul(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1068 | C = *AI; |
1069 | return true; |
1070 | } |
1071 | if (match(V: E, P: m_Shl(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1072 | C = APInt(AI->getBitWidth(), 1); |
1073 | C <<= *AI; |
1074 | return true; |
1075 | } |
1076 | return false; |
1077 | } |
1078 | |
1079 | // Matches remainder expression Op % C where C is a constant. Returns the |
1080 | // constant value in C and the other operand in Op. Returns the signedness of |
1081 | // the remainder operation in IsSigned. Returns true if such a match is |
1082 | // found. |
1083 | static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) { |
1084 | const APInt *AI; |
1085 | IsSigned = false; |
1086 | if (match(V: E, P: m_SRem(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1087 | IsSigned = true; |
1088 | C = *AI; |
1089 | return true; |
1090 | } |
1091 | if (match(V: E, P: m_URem(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1092 | C = *AI; |
1093 | return true; |
1094 | } |
1095 | if (match(V: E, P: m_And(L: m_Value(V&: Op), R: m_APInt(Res&: AI))) && (*AI + 1).isPowerOf2()) { |
1096 | C = *AI + 1; |
1097 | return true; |
1098 | } |
1099 | return false; |
1100 | } |
1101 | |
1102 | // Matches division expression Op / C with the given signedness as indicated |
1103 | // by IsSigned, where C is a constant. Returns the constant value in C and the |
1104 | // other operand in Op. Returns true if such a match is found. |
1105 | static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) { |
1106 | const APInt *AI; |
1107 | if (IsSigned && match(V: E, P: m_SDiv(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1108 | C = *AI; |
1109 | return true; |
1110 | } |
1111 | if (!IsSigned) { |
1112 | if (match(V: E, P: m_UDiv(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1113 | C = *AI; |
1114 | return true; |
1115 | } |
1116 | if (match(V: E, P: m_LShr(L: m_Value(V&: Op), R: m_APInt(Res&: AI)))) { |
1117 | C = APInt(AI->getBitWidth(), 1); |
1118 | C <<= *AI; |
1119 | return true; |
1120 | } |
1121 | } |
1122 | return false; |
1123 | } |
1124 | |
1125 | // Returns whether C0 * C1 with the given signedness overflows. |
1126 | static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) { |
1127 | bool overflow; |
1128 | if (IsSigned) |
1129 | (void)C0.smul_ov(RHS: C1, Overflow&: overflow); |
1130 | else |
1131 | (void)C0.umul_ov(RHS: C1, Overflow&: overflow); |
1132 | return overflow; |
1133 | } |
1134 | |
1135 | // Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1) |
1136 | // does not overflow. |
1137 | // Simplifies (X / C0) * C1 + (X % C0) * C2 to |
1138 | // (X / C0) * (C1 - C2 * C0) + X * C2 |
1139 | Value *InstCombinerImpl::SimplifyAddWithRemainder(BinaryOperator &I) { |
1140 | Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1); |
1141 | Value *X, *MulOpV; |
1142 | APInt C0, MulOpC; |
1143 | bool IsSigned; |
1144 | // Match I = X % C0 + MulOpV * C0 |
1145 | if (((MatchRem(E: LHS, Op&: X, C&: C0, IsSigned) && MatchMul(E: RHS, Op&: MulOpV, C&: MulOpC)) || |
1146 | (MatchRem(E: RHS, Op&: X, C&: C0, IsSigned) && MatchMul(E: LHS, Op&: MulOpV, C&: MulOpC))) && |
1147 | C0 == MulOpC) { |
1148 | Value *RemOpV; |
1149 | APInt C1; |
1150 | bool Rem2IsSigned; |
1151 | // Match MulOpC = RemOpV % C1 |
1152 | if (MatchRem(E: MulOpV, Op&: RemOpV, C&: C1, IsSigned&: Rem2IsSigned) && |
1153 | IsSigned == Rem2IsSigned) { |
1154 | Value *DivOpV; |
1155 | APInt DivOpC; |
1156 | // Match RemOpV = X / C0 |
1157 | if (MatchDiv(E: RemOpV, Op&: DivOpV, C&: DivOpC, IsSigned) && X == DivOpV && |
1158 | C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) { |
1159 | Value *NewDivisor = ConstantInt::get(Ty: X->getType(), V: C0 * C1); |
1160 | return IsSigned ? Builder.CreateSRem(LHS: X, RHS: NewDivisor, Name: "srem" ) |
1161 | : Builder.CreateURem(LHS: X, RHS: NewDivisor, Name: "urem" ); |
1162 | } |
1163 | } |
1164 | } |
1165 | |
1166 | // Match I = (X / C0) * C1 + (X % C0) * C2 |
1167 | Value *Div, *Rem; |
1168 | APInt C1, C2; |
1169 | if (!LHS->hasOneUse() || !MatchMul(E: LHS, Op&: Div, C&: C1)) |
1170 | Div = LHS, C1 = APInt(I.getType()->getScalarSizeInBits(), 1); |
1171 | if (!RHS->hasOneUse() || !MatchMul(E: RHS, Op&: Rem, C&: C2)) |
1172 | Rem = RHS, C2 = APInt(I.getType()->getScalarSizeInBits(), 1); |
1173 | if (match(V: Div, P: m_IRem(L: m_Value(), R: m_Value()))) { |
1174 | std::swap(a&: Div, b&: Rem); |
1175 | std::swap(a&: C1, b&: C2); |
1176 | } |
1177 | Value *DivOpV; |
1178 | APInt DivOpC; |
1179 | if (MatchRem(E: Rem, Op&: X, C&: C0, IsSigned) && |
1180 | MatchDiv(E: Div, Op&: DivOpV, C&: DivOpC, IsSigned) && X == DivOpV && C0 == DivOpC) { |
1181 | APInt NewC = C1 - C2 * C0; |
1182 | if (!NewC.isZero() && !Rem->hasOneUse()) |
1183 | return nullptr; |
1184 | if (!isGuaranteedNotToBeUndef(V: X, AC: &AC, CtxI: &I, DT: &DT)) |
1185 | return nullptr; |
1186 | Value *MulXC2 = Builder.CreateMul(LHS: X, RHS: ConstantInt::get(Ty: X->getType(), V: C2)); |
1187 | if (NewC.isZero()) |
1188 | return MulXC2; |
1189 | return Builder.CreateAdd( |
1190 | LHS: Builder.CreateMul(LHS: Div, RHS: ConstantInt::get(Ty: X->getType(), V: NewC)), RHS: MulXC2); |
1191 | } |
1192 | |
1193 | return nullptr; |
1194 | } |
1195 | |
1196 | /// Fold |
1197 | /// (1 << NBits) - 1 |
1198 | /// Into: |
1199 | /// ~(-(1 << NBits)) |
1200 | /// Because a 'not' is better for bit-tracking analysis and other transforms |
1201 | /// than an 'add'. The new shl is always nsw, and is nuw if old `and` was. |
1202 | static Instruction *canonicalizeLowbitMask(BinaryOperator &I, |
1203 | InstCombiner::BuilderTy &Builder) { |
1204 | Value *NBits; |
1205 | if (!match(V: &I, P: m_Add(L: m_OneUse(SubPattern: m_Shl(L: m_One(), R: m_Value(V&: NBits))), R: m_AllOnes()))) |
1206 | return nullptr; |
1207 | |
1208 | Constant *MinusOne = Constant::getAllOnesValue(Ty: NBits->getType()); |
1209 | Value *NotMask = Builder.CreateShl(LHS: MinusOne, RHS: NBits, Name: "notmask" ); |
1210 | // Be wary of constant folding. |
1211 | if (auto *BOp = dyn_cast<BinaryOperator>(Val: NotMask)) { |
1212 | // Always NSW. But NUW propagates from `add`. |
1213 | BOp->setHasNoSignedWrap(); |
1214 | BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); |
1215 | } |
1216 | |
1217 | return BinaryOperator::CreateNot(Op: NotMask, Name: I.getName()); |
1218 | } |
1219 | |
1220 | static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) { |
1221 | assert(I.getOpcode() == Instruction::Add && "Expecting add instruction" ); |
1222 | Type *Ty = I.getType(); |
1223 | auto getUAddSat = [&]() { |
1224 | return Intrinsic::getDeclaration(I.getModule(), Intrinsic::uadd_sat, Ty); |
1225 | }; |
1226 | |
1227 | // add (umin X, ~Y), Y --> uaddsat X, Y |
1228 | Value *X, *Y; |
1229 | if (match(V: &I, P: m_c_Add(L: m_c_UMin(L: m_Value(V&: X), R: m_Not(V: m_Value(V&: Y))), |
1230 | R: m_Deferred(V: Y)))) |
1231 | return CallInst::Create(getUAddSat(), { X, Y }); |
1232 | |
1233 | // add (umin X, ~C), C --> uaddsat X, C |
1234 | const APInt *C, *NotC; |
1235 | if (match(V: &I, P: m_Add(L: m_UMin(L: m_Value(V&: X), R: m_APInt(Res&: NotC)), R: m_APInt(Res&: C))) && |
1236 | *C == ~*NotC) |
1237 | return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, V: *C) }); |
1238 | |
1239 | return nullptr; |
1240 | } |
1241 | |
1242 | // Transform: |
1243 | // (add A, (shl (neg B), Y)) |
1244 | // -> (sub A, (shl B, Y)) |
1245 | static Instruction *combineAddSubWithShlAddSub(InstCombiner::BuilderTy &Builder, |
1246 | const BinaryOperator &I) { |
1247 | Value *A, *B, *Cnt; |
1248 | if (match(V: &I, |
1249 | P: m_c_Add(L: m_OneUse(SubPattern: m_Shl(L: m_OneUse(SubPattern: m_Neg(V: m_Value(V&: B))), R: m_Value(V&: Cnt))), |
1250 | R: m_Value(V&: A)))) { |
1251 | Value *NewShl = Builder.CreateShl(LHS: B, RHS: Cnt); |
1252 | return BinaryOperator::CreateSub(V1: A, V2: NewShl); |
1253 | } |
1254 | return nullptr; |
1255 | } |
1256 | |
1257 | /// Try to reduce signed division by power-of-2 to an arithmetic shift right. |
1258 | static Instruction *foldAddToAshr(BinaryOperator &Add) { |
1259 | // Division must be by power-of-2, but not the minimum signed value. |
1260 | Value *X; |
1261 | const APInt *DivC; |
1262 | if (!match(V: Add.getOperand(i_nocapture: 0), P: m_SDiv(L: m_Value(V&: X), R: m_Power2(V&: DivC))) || |
1263 | DivC->isNegative()) |
1264 | return nullptr; |
1265 | |
1266 | // Rounding is done by adding -1 if the dividend (X) is negative and has any |
1267 | // low bits set. It recognizes two canonical patterns: |
1268 | // 1. For an 'ugt' cmp with the signed minimum value (SMIN), the |
1269 | // pattern is: sext (icmp ugt (X & (DivC - 1)), SMIN). |
1270 | // 2. For an 'eq' cmp, the pattern's: sext (icmp eq X & (SMIN + 1), SMIN + 1). |
1271 | // Note that, by the time we end up here, if possible, ugt has been |
1272 | // canonicalized into eq. |
1273 | const APInt *MaskC, *MaskCCmp; |
1274 | ICmpInst::Predicate Pred; |
1275 | if (!match(V: Add.getOperand(i_nocapture: 1), |
1276 | P: m_SExt(Op: m_ICmp(Pred, L: m_And(L: m_Specific(V: X), R: m_APInt(Res&: MaskC)), |
1277 | R: m_APInt(Res&: MaskCCmp))))) |
1278 | return nullptr; |
1279 | |
1280 | if ((Pred != ICmpInst::ICMP_UGT || !MaskCCmp->isSignMask()) && |
1281 | (Pred != ICmpInst::ICMP_EQ || *MaskCCmp != *MaskC)) |
1282 | return nullptr; |
1283 | |
1284 | APInt SMin = APInt::getSignedMinValue(numBits: Add.getType()->getScalarSizeInBits()); |
1285 | bool IsMaskValid = Pred == ICmpInst::ICMP_UGT |
1286 | ? (*MaskC == (SMin | (*DivC - 1))) |
1287 | : (*DivC == 2 && *MaskC == SMin + 1); |
1288 | if (!IsMaskValid) |
1289 | return nullptr; |
1290 | |
1291 | // (X / DivC) + sext ((X & (SMin | (DivC - 1)) >u SMin) --> X >>s log2(DivC) |
1292 | return BinaryOperator::CreateAShr( |
1293 | V1: X, V2: ConstantInt::get(Ty: Add.getType(), V: DivC->exactLogBase2())); |
1294 | } |
1295 | |
1296 | Instruction *InstCombinerImpl:: |
1297 | ( |
1298 | BinaryOperator &I) { |
1299 | assert((I.getOpcode() == Instruction::Add || |
1300 | I.getOpcode() == Instruction::Or || |
1301 | I.getOpcode() == Instruction::Sub) && |
1302 | "Expecting add/or/sub instruction" ); |
1303 | |
1304 | // We have a subtraction/addition between a (potentially truncated) *logical* |
1305 | // right-shift of X and a "select". |
1306 | Value *X, *Select; |
1307 | Instruction *LowBitsToSkip, *; |
1308 | if (!match(V: &I, P: m_c_BinOp(L: m_TruncOrSelf(Op: m_CombineAnd( |
1309 | L: m_LShr(L: m_Value(V&: X), R: m_Instruction(I&: LowBitsToSkip)), |
1310 | R: m_Instruction(I&: Extract))), |
1311 | R: m_Value(V&: Select)))) |
1312 | return nullptr; |
1313 | |
1314 | // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS. |
1315 | if (I.getOpcode() == Instruction::Sub && I.getOperand(i_nocapture: 1) != Select) |
1316 | return nullptr; |
1317 | |
1318 | Type *XTy = X->getType(); |
1319 | bool HadTrunc = I.getType() != XTy; |
1320 | |
1321 | // If there was a truncation of extracted value, then we'll need to produce |
1322 | // one extra instruction, so we need to ensure one instruction will go away. |
1323 | if (HadTrunc && !match(V: &I, P: m_c_BinOp(L: m_OneUse(SubPattern: m_Value()), R: m_Value()))) |
1324 | return nullptr; |
1325 | |
1326 | // Extraction should extract high NBits bits, with shift amount calculated as: |
1327 | // low bits to skip = shift bitwidth - high bits to extract |
1328 | // The shift amount itself may be extended, and we need to look past zero-ext |
1329 | // when matching NBits, that will matter for matching later. |
1330 | Constant *C; |
1331 | Value *NBits; |
1332 | if (!match( |
1333 | V: LowBitsToSkip, |
1334 | P: m_ZExtOrSelf(Op: m_Sub(L: m_Constant(C), R: m_ZExtOrSelf(Op: m_Value(V&: NBits))))) || |
1335 | !match(V: C, P: m_SpecificInt_ICMP(Predicate: ICmpInst::Predicate::ICMP_EQ, |
1336 | Threshold: APInt(C->getType()->getScalarSizeInBits(), |
1337 | X->getType()->getScalarSizeInBits())))) |
1338 | return nullptr; |
1339 | |
1340 | // Sign-extending value can be zero-extended if we `sub`tract it, |
1341 | // or sign-extended otherwise. |
1342 | auto SkipExtInMagic = [&I](Value *&V) { |
1343 | if (I.getOpcode() == Instruction::Sub) |
1344 | match(V, P: m_ZExtOrSelf(Op: m_Value(V))); |
1345 | else |
1346 | match(V, P: m_SExtOrSelf(Op: m_Value(V))); |
1347 | }; |
1348 | |
1349 | // Now, finally validate the sign-extending magic. |
1350 | // `select` itself may be appropriately extended, look past that. |
1351 | SkipExtInMagic(Select); |
1352 | |
1353 | ICmpInst::Predicate Pred; |
1354 | const APInt *Thr; |
1355 | Value *SignExtendingValue, *Zero; |
1356 | bool ShouldSignext; |
1357 | // It must be a select between two values we will later establish to be a |
1358 | // sign-extending value and a zero constant. The condition guarding the |
1359 | // sign-extension must be based on a sign bit of the same X we had in `lshr`. |
1360 | if (!match(V: Select, P: m_Select(C: m_ICmp(Pred, L: m_Specific(V: X), R: m_APInt(Res&: Thr)), |
1361 | L: m_Value(V&: SignExtendingValue), R: m_Value(V&: Zero))) || |
1362 | !isSignBitCheck(Pred, RHS: *Thr, TrueIfSigned&: ShouldSignext)) |
1363 | return nullptr; |
1364 | |
1365 | // icmp-select pair is commutative. |
1366 | if (!ShouldSignext) |
1367 | std::swap(a&: SignExtendingValue, b&: Zero); |
1368 | |
1369 | // If we should not perform sign-extension then we must add/or/subtract zero. |
1370 | if (!match(V: Zero, P: m_Zero())) |
1371 | return nullptr; |
1372 | // Otherwise, it should be some constant, left-shifted by the same NBits we |
1373 | // had in `lshr`. Said left-shift can also be appropriately extended. |
1374 | // Again, we must look past zero-ext when looking for NBits. |
1375 | SkipExtInMagic(SignExtendingValue); |
1376 | Constant *SignExtendingValueBaseConstant; |
1377 | if (!match(V: SignExtendingValue, |
1378 | P: m_Shl(L: m_Constant(C&: SignExtendingValueBaseConstant), |
1379 | R: m_ZExtOrSelf(Op: m_Specific(V: NBits))))) |
1380 | return nullptr; |
1381 | // If we `sub`, then the constant should be one, else it should be all-ones. |
1382 | if (I.getOpcode() == Instruction::Sub |
1383 | ? !match(V: SignExtendingValueBaseConstant, P: m_One()) |
1384 | : !match(V: SignExtendingValueBaseConstant, P: m_AllOnes())) |
1385 | return nullptr; |
1386 | |
1387 | auto *NewAShr = BinaryOperator::CreateAShr(V1: X, V2: LowBitsToSkip, |
1388 | Name: Extract->getName() + ".sext" ); |
1389 | NewAShr->copyIRFlags(V: Extract); // Preserve `exact`-ness. |
1390 | if (!HadTrunc) |
1391 | return NewAShr; |
1392 | |
1393 | Builder.Insert(I: NewAShr); |
1394 | return TruncInst::CreateTruncOrBitCast(S: NewAShr, Ty: I.getType()); |
1395 | } |
1396 | |
1397 | /// This is a specialization of a more general transform from |
1398 | /// foldUsingDistributiveLaws. If that code can be made to work optimally |
1399 | /// for multi-use cases or propagating nsw/nuw, then we would not need this. |
1400 | static Instruction *factorizeMathWithShlOps(BinaryOperator &I, |
1401 | InstCombiner::BuilderTy &Builder) { |
1402 | // TODO: Also handle mul by doubling the shift amount? |
1403 | assert((I.getOpcode() == Instruction::Add || |
1404 | I.getOpcode() == Instruction::Sub) && |
1405 | "Expected add/sub" ); |
1406 | auto *Op0 = dyn_cast<BinaryOperator>(Val: I.getOperand(i_nocapture: 0)); |
1407 | auto *Op1 = dyn_cast<BinaryOperator>(Val: I.getOperand(i_nocapture: 1)); |
1408 | if (!Op0 || !Op1 || !(Op0->hasOneUse() || Op1->hasOneUse())) |
1409 | return nullptr; |
1410 | |
1411 | Value *X, *Y, *ShAmt; |
1412 | if (!match(V: Op0, P: m_Shl(L: m_Value(V&: X), R: m_Value(V&: ShAmt))) || |
1413 | !match(V: Op1, P: m_Shl(L: m_Value(V&: Y), R: m_Specific(V: ShAmt)))) |
1414 | return nullptr; |
1415 | |
1416 | // No-wrap propagates only when all ops have no-wrap. |
1417 | bool HasNSW = I.hasNoSignedWrap() && Op0->hasNoSignedWrap() && |
1418 | Op1->hasNoSignedWrap(); |
1419 | bool HasNUW = I.hasNoUnsignedWrap() && Op0->hasNoUnsignedWrap() && |
1420 | Op1->hasNoUnsignedWrap(); |
1421 | |
1422 | // add/sub (X << ShAmt), (Y << ShAmt) --> (add/sub X, Y) << ShAmt |
1423 | Value *NewMath = Builder.CreateBinOp(Opc: I.getOpcode(), LHS: X, RHS: Y); |
1424 | if (auto *NewI = dyn_cast<BinaryOperator>(Val: NewMath)) { |
1425 | NewI->setHasNoSignedWrap(HasNSW); |
1426 | NewI->setHasNoUnsignedWrap(HasNUW); |
1427 | } |
1428 | auto *NewShl = BinaryOperator::CreateShl(V1: NewMath, V2: ShAmt); |
1429 | NewShl->setHasNoSignedWrap(HasNSW); |
1430 | NewShl->setHasNoUnsignedWrap(HasNUW); |
1431 | return NewShl; |
1432 | } |
1433 | |
1434 | /// Reduce a sequence of masked half-width multiplies to a single multiply. |
1435 | /// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y |
1436 | static Instruction *foldBoxMultiply(BinaryOperator &I) { |
1437 | unsigned BitWidth = I.getType()->getScalarSizeInBits(); |
1438 | // Skip the odd bitwidth types. |
1439 | if ((BitWidth & 0x1)) |
1440 | return nullptr; |
1441 | |
1442 | unsigned HalfBits = BitWidth >> 1; |
1443 | APInt HalfMask = APInt::getMaxValue(numBits: HalfBits); |
1444 | |
1445 | // ResLo = (CrossSum << HalfBits) + (YLo * XLo) |
1446 | Value *XLo, *YLo; |
1447 | Value *CrossSum; |
1448 | // Require one-use on the multiply to avoid increasing the number of |
1449 | // multiplications. |
1450 | if (!match(V: &I, P: m_c_Add(L: m_Shl(L: m_Value(V&: CrossSum), R: m_SpecificInt(V: HalfBits)), |
1451 | R: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: YLo), R: m_Value(V&: XLo)))))) |
1452 | return nullptr; |
1453 | |
1454 | // XLo = X & HalfMask |
1455 | // YLo = Y & HalfMask |
1456 | // TODO: Refactor with SimplifyDemandedBits or KnownBits known leading zeros |
1457 | // to enhance robustness |
1458 | Value *X, *Y; |
1459 | if (!match(V: XLo, P: m_And(L: m_Value(V&: X), R: m_SpecificInt(V: HalfMask))) || |
1460 | !match(V: YLo, P: m_And(L: m_Value(V&: Y), R: m_SpecificInt(V: HalfMask)))) |
1461 | return nullptr; |
1462 | |
1463 | // CrossSum = (X' * (Y >> Halfbits)) + (Y' * (X >> HalfBits)) |
1464 | // X' can be either X or XLo in the pattern (and the same for Y') |
1465 | if (match(V: CrossSum, |
1466 | P: m_c_Add(L: m_c_Mul(L: m_LShr(L: m_Specific(V: Y), R: m_SpecificInt(V: HalfBits)), |
1467 | R: m_CombineOr(L: m_Specific(V: X), R: m_Specific(V: XLo))), |
1468 | R: m_c_Mul(L: m_LShr(L: m_Specific(V: X), R: m_SpecificInt(V: HalfBits)), |
1469 | R: m_CombineOr(L: m_Specific(V: Y), R: m_Specific(V: YLo)))))) |
1470 | return BinaryOperator::CreateMul(V1: X, V2: Y); |
1471 | |
1472 | return nullptr; |
1473 | } |
1474 | |
1475 | Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) { |
1476 | if (Value *V = simplifyAddInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), |
1477 | IsNSW: I.hasNoSignedWrap(), IsNUW: I.hasNoUnsignedWrap(), |
1478 | Q: SQ.getWithInstruction(I: &I))) |
1479 | return replaceInstUsesWith(I, V); |
1480 | |
1481 | if (SimplifyAssociativeOrCommutative(I)) |
1482 | return &I; |
1483 | |
1484 | if (Instruction *X = foldVectorBinop(Inst&: I)) |
1485 | return X; |
1486 | |
1487 | if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I)) |
1488 | return Phi; |
1489 | |
1490 | // (A*B)+(A*C) -> A*(B+C) etc |
1491 | if (Value *V = foldUsingDistributiveLaws(I)) |
1492 | return replaceInstUsesWith(I, V); |
1493 | |
1494 | if (Instruction *R = foldBoxMultiply(I)) |
1495 | return R; |
1496 | |
1497 | if (Instruction *R = factorizeMathWithShlOps(I, Builder)) |
1498 | return R; |
1499 | |
1500 | if (Instruction *X = foldAddWithConstant(Add&: I)) |
1501 | return X; |
1502 | |
1503 | if (Instruction *X = foldNoWrapAdd(Add&: I, Builder)) |
1504 | return X; |
1505 | |
1506 | if (Instruction *R = foldBinOpShiftWithShift(I)) |
1507 | return R; |
1508 | |
1509 | if (Instruction *R = combineAddSubWithShlAddSub(Builder, I)) |
1510 | return R; |
1511 | |
1512 | Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1); |
1513 | Type *Ty = I.getType(); |
1514 | if (Ty->isIntOrIntVectorTy(BitWidth: 1)) |
1515 | return BinaryOperator::CreateXor(V1: LHS, V2: RHS); |
1516 | |
1517 | // X + X --> X << 1 |
1518 | if (LHS == RHS) { |
1519 | auto *Shl = BinaryOperator::CreateShl(V1: LHS, V2: ConstantInt::get(Ty, V: 1)); |
1520 | Shl->setHasNoSignedWrap(I.hasNoSignedWrap()); |
1521 | Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); |
1522 | return Shl; |
1523 | } |
1524 | |
1525 | Value *A, *B; |
1526 | if (match(V: LHS, P: m_Neg(V: m_Value(V&: A)))) { |
1527 | // -A + -B --> -(A + B) |
1528 | if (match(V: RHS, P: m_Neg(V: m_Value(V&: B)))) |
1529 | return BinaryOperator::CreateNeg(Op: Builder.CreateAdd(LHS: A, RHS: B)); |
1530 | |
1531 | // -A + B --> B - A |
1532 | auto *Sub = BinaryOperator::CreateSub(V1: RHS, V2: A); |
1533 | auto *OB0 = cast<OverflowingBinaryOperator>(Val: LHS); |
1534 | Sub->setHasNoSignedWrap(I.hasNoSignedWrap() && OB0->hasNoSignedWrap()); |
1535 | |
1536 | return Sub; |
1537 | } |
1538 | |
1539 | // A + -B --> A - B |
1540 | if (match(V: RHS, P: m_Neg(V: m_Value(V&: B)))) |
1541 | return BinaryOperator::CreateSub(V1: LHS, V2: B); |
1542 | |
1543 | if (Value *V = checkForNegativeOperand(I, Builder)) |
1544 | return replaceInstUsesWith(I, V); |
1545 | |
1546 | // (A + 1) + ~B --> A - B |
1547 | // ~B + (A + 1) --> A - B |
1548 | // (~B + A) + 1 --> A - B |
1549 | // (A + ~B) + 1 --> A - B |
1550 | if (match(V: &I, P: m_c_BinOp(L: m_Add(L: m_Value(V&: A), R: m_One()), R: m_Not(V: m_Value(V&: B)))) || |
1551 | match(V: &I, P: m_BinOp(L: m_c_Add(L: m_Not(V: m_Value(V&: B)), R: m_Value(V&: A)), R: m_One()))) |
1552 | return BinaryOperator::CreateSub(V1: A, V2: B); |
1553 | |
1554 | // (A + RHS) + RHS --> A + (RHS << 1) |
1555 | if (match(V: LHS, P: m_OneUse(SubPattern: m_c_Add(L: m_Value(V&: A), R: m_Specific(V: RHS))))) |
1556 | return BinaryOperator::CreateAdd(V1: A, V2: Builder.CreateShl(LHS: RHS, RHS: 1, Name: "reass.add" )); |
1557 | |
1558 | // LHS + (A + LHS) --> A + (LHS << 1) |
1559 | if (match(V: RHS, P: m_OneUse(SubPattern: m_c_Add(L: m_Value(V&: A), R: m_Specific(V: LHS))))) |
1560 | return BinaryOperator::CreateAdd(V1: A, V2: Builder.CreateShl(LHS, RHS: 1, Name: "reass.add" )); |
1561 | |
1562 | { |
1563 | // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2) |
1564 | Constant *C1, *C2; |
1565 | if (match(V: &I, P: m_c_Add(L: m_Add(L: m_Value(V&: A), R: m_ImmConstant(C&: C1)), |
1566 | R: m_Sub(L: m_ImmConstant(C&: C2), R: m_Value(V&: B)))) && |
1567 | (LHS->hasOneUse() || RHS->hasOneUse())) { |
1568 | Value *Sub = Builder.CreateSub(LHS: A, RHS: B); |
1569 | return BinaryOperator::CreateAdd(V1: Sub, V2: ConstantExpr::getAdd(C1, C2)); |
1570 | } |
1571 | |
1572 | // Canonicalize a constant sub operand as an add operand for better folding: |
1573 | // (C1 - A) + B --> (B - A) + C1 |
1574 | if (match(V: &I, P: m_c_Add(L: m_OneUse(SubPattern: m_Sub(L: m_ImmConstant(C&: C1), R: m_Value(V&: A))), |
1575 | R: m_Value(V&: B)))) { |
1576 | Value *Sub = Builder.CreateSub(LHS: B, RHS: A, Name: "reass.sub" ); |
1577 | return BinaryOperator::CreateAdd(V1: Sub, V2: C1); |
1578 | } |
1579 | } |
1580 | |
1581 | // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1) |
1582 | if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V); |
1583 | |
1584 | // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C2 |
1585 | const APInt *C1, *C2; |
1586 | if (match(V: LHS, P: m_Shl(L: m_SDiv(L: m_Specific(V: RHS), R: m_APInt(Res&: C1)), R: m_APInt(Res&: C2)))) { |
1587 | APInt one(C2->getBitWidth(), 1); |
1588 | APInt minusC1 = -(*C1); |
1589 | if (minusC1 == (one << *C2)) { |
1590 | Constant *NewRHS = ConstantInt::get(Ty: RHS->getType(), V: minusC1); |
1591 | return BinaryOperator::CreateSRem(V1: RHS, V2: NewRHS); |
1592 | } |
1593 | } |
1594 | |
1595 | // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit |
1596 | if (match(V: &I, P: m_c_Add(L: m_And(L: m_Value(V&: A), R: m_APInt(Res&: C1)), R: m_Deferred(V: A))) && |
1597 | C1->isPowerOf2() && (ComputeNumSignBits(Op: A) > C1->countl_zero())) { |
1598 | Constant *NewMask = ConstantInt::get(Ty: RHS->getType(), V: *C1 - 1); |
1599 | return BinaryOperator::CreateAnd(V1: A, V2: NewMask); |
1600 | } |
1601 | |
1602 | // ZExt (B - A) + ZExt(A) --> ZExt(B) |
1603 | if ((match(V: RHS, P: m_ZExt(Op: m_Value(V&: A))) && |
1604 | match(V: LHS, P: m_ZExt(Op: m_NUWSub(L: m_Value(V&: B), R: m_Specific(V: A))))) || |
1605 | (match(V: LHS, P: m_ZExt(Op: m_Value(V&: A))) && |
1606 | match(V: RHS, P: m_ZExt(Op: m_NUWSub(L: m_Value(V&: B), R: m_Specific(V: A)))))) |
1607 | return new ZExtInst(B, LHS->getType()); |
1608 | |
1609 | // zext(A) + sext(A) --> 0 if A is i1 |
1610 | if (match(V: &I, P: m_c_BinOp(L: m_ZExt(Op: m_Value(V&: A)), R: m_SExt(Op: m_Deferred(V: A)))) && |
1611 | A->getType()->isIntOrIntVectorTy(BitWidth: 1)) |
1612 | return replaceInstUsesWith(I, V: Constant::getNullValue(Ty: I.getType())); |
1613 | |
1614 | // A+B --> A|B iff A and B have no bits set in common. |
1615 | WithCache<const Value *> LHSCache(LHS), RHSCache(RHS); |
1616 | if (haveNoCommonBitsSet(LHSCache, RHSCache, SQ: SQ.getWithInstruction(I: &I))) |
1617 | return BinaryOperator::CreateDisjointOr(V1: LHS, V2: RHS); |
1618 | |
1619 | if (Instruction *Ext = narrowMathIfNoOverflow(I)) |
1620 | return Ext; |
1621 | |
1622 | // (add (xor A, B) (and A, B)) --> (or A, B) |
1623 | // (add (and A, B) (xor A, B)) --> (or A, B) |
1624 | if (match(V: &I, P: m_c_BinOp(L: m_Xor(L: m_Value(V&: A), R: m_Value(V&: B)), |
1625 | R: m_c_And(L: m_Deferred(V: A), R: m_Deferred(V: B))))) |
1626 | return BinaryOperator::CreateOr(V1: A, V2: B); |
1627 | |
1628 | // (add (or A, B) (and A, B)) --> (add A, B) |
1629 | // (add (and A, B) (or A, B)) --> (add A, B) |
1630 | if (match(V: &I, P: m_c_BinOp(L: m_Or(L: m_Value(V&: A), R: m_Value(V&: B)), |
1631 | R: m_c_And(L: m_Deferred(V: A), R: m_Deferred(V: B))))) { |
1632 | // Replacing operands in-place to preserve nuw/nsw flags. |
1633 | replaceOperand(I, OpNum: 0, V: A); |
1634 | replaceOperand(I, OpNum: 1, V: B); |
1635 | return &I; |
1636 | } |
1637 | |
1638 | // (add A (or A, -A)) --> (and (add A, -1) A) |
1639 | // (add A (or -A, A)) --> (and (add A, -1) A) |
1640 | // (add (or A, -A) A) --> (and (add A, -1) A) |
1641 | // (add (or -A, A) A) --> (and (add A, -1) A) |
1642 | if (match(V: &I, P: m_c_BinOp(L: m_Value(V&: A), R: m_OneUse(SubPattern: m_c_Or(L: m_Neg(V: m_Deferred(V: A)), |
1643 | R: m_Deferred(V: A)))))) { |
1644 | Value *Add = |
1645 | Builder.CreateAdd(LHS: A, RHS: Constant::getAllOnesValue(Ty: A->getType()), Name: "" , |
1646 | HasNUW: I.hasNoUnsignedWrap(), HasNSW: I.hasNoSignedWrap()); |
1647 | return BinaryOperator::CreateAnd(V1: Add, V2: A); |
1648 | } |
1649 | |
1650 | // Canonicalize ((A & -A) - 1) --> ((A - 1) & ~A) |
1651 | // Forms all commutable operations, and simplifies ctpop -> cttz folds. |
1652 | if (match(V: &I, |
1653 | P: m_Add(L: m_OneUse(SubPattern: m_c_And(L: m_Value(V&: A), R: m_OneUse(SubPattern: m_Neg(V: m_Deferred(V: A))))), |
1654 | R: m_AllOnes()))) { |
1655 | Constant *AllOnes = ConstantInt::getAllOnesValue(Ty: RHS->getType()); |
1656 | Value *Dec = Builder.CreateAdd(LHS: A, RHS: AllOnes); |
1657 | Value *Not = Builder.CreateXor(LHS: A, RHS: AllOnes); |
1658 | return BinaryOperator::CreateAnd(V1: Dec, V2: Not); |
1659 | } |
1660 | |
1661 | // Disguised reassociation/factorization: |
1662 | // ~(A * C1) + A |
1663 | // ((A * -C1) - 1) + A |
1664 | // ((A * -C1) + A) - 1 |
1665 | // (A * (1 - C1)) - 1 |
1666 | if (match(V: &I, |
1667 | P: m_c_Add(L: m_OneUse(SubPattern: m_Not(V: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: A), R: m_APInt(Res&: C1))))), |
1668 | R: m_Deferred(V: A)))) { |
1669 | Type *Ty = I.getType(); |
1670 | Constant *NewMulC = ConstantInt::get(Ty, V: 1 - *C1); |
1671 | Value *NewMul = Builder.CreateMul(LHS: A, RHS: NewMulC); |
1672 | return BinaryOperator::CreateAdd(V1: NewMul, V2: ConstantInt::getAllOnesValue(Ty)); |
1673 | } |
1674 | |
1675 | // (A * -2**C) + B --> B - (A << C) |
1676 | const APInt *NegPow2C; |
1677 | if (match(V: &I, P: m_c_Add(L: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: A), R: m_NegatedPower2(V&: NegPow2C))), |
1678 | R: m_Value(V&: B)))) { |
1679 | Constant *ShiftAmtC = ConstantInt::get(Ty, V: NegPow2C->countr_zero()); |
1680 | Value *Shl = Builder.CreateShl(LHS: A, RHS: ShiftAmtC); |
1681 | return BinaryOperator::CreateSub(V1: B, V2: Shl); |
1682 | } |
1683 | |
1684 | // Canonicalize signum variant that ends in add: |
1685 | // (A s>> (BW - 1)) + (zext (A s> 0)) --> (A s>> (BW - 1)) | (zext (A != 0)) |
1686 | ICmpInst::Predicate Pred; |
1687 | uint64_t BitWidth = Ty->getScalarSizeInBits(); |
1688 | if (match(V: LHS, P: m_AShr(L: m_Value(V&: A), R: m_SpecificIntAllowPoison(V: BitWidth - 1))) && |
1689 | match(V: RHS, P: m_OneUse(SubPattern: m_ZExt( |
1690 | Op: m_OneUse(SubPattern: m_ICmp(Pred, L: m_Specific(V: A), R: m_ZeroInt()))))) && |
1691 | Pred == CmpInst::ICMP_SGT) { |
1692 | Value *NotZero = Builder.CreateIsNotNull(Arg: A, Name: "isnotnull" ); |
1693 | Value *Zext = Builder.CreateZExt(V: NotZero, DestTy: Ty, Name: "isnotnull.zext" ); |
1694 | return BinaryOperator::CreateOr(V1: LHS, V2: Zext); |
1695 | } |
1696 | |
1697 | if (Instruction *Ashr = foldAddToAshr(Add&: I)) |
1698 | return Ashr; |
1699 | |
1700 | // (~X) + (~Y) --> -2 - (X + Y) |
1701 | { |
1702 | // To ensure we can save instructions we need to ensure that we consume both |
1703 | // LHS/RHS (i.e they have a `not`). |
1704 | bool ConsumesLHS, ConsumesRHS; |
1705 | if (isFreeToInvert(V: LHS, WillInvertAllUses: LHS->hasOneUse(), DoesConsume&: ConsumesLHS) && ConsumesLHS && |
1706 | isFreeToInvert(V: RHS, WillInvertAllUses: RHS->hasOneUse(), DoesConsume&: ConsumesRHS) && ConsumesRHS) { |
1707 | Value *NotLHS = getFreelyInverted(V: LHS, WillInvertAllUses: LHS->hasOneUse(), Builder: &Builder); |
1708 | Value *NotRHS = getFreelyInverted(V: RHS, WillInvertAllUses: RHS->hasOneUse(), Builder: &Builder); |
1709 | assert(NotLHS != nullptr && NotRHS != nullptr && |
1710 | "isFreeToInvert desynced with getFreelyInverted" ); |
1711 | Value *LHSPlusRHS = Builder.CreateAdd(LHS: NotLHS, RHS: NotRHS); |
1712 | return BinaryOperator::CreateSub( |
1713 | V1: ConstantInt::getSigned(Ty: RHS->getType(), V: -2), V2: LHSPlusRHS); |
1714 | } |
1715 | } |
1716 | |
1717 | if (Instruction *R = tryFoldInstWithCtpopWithNot(I: &I)) |
1718 | return R; |
1719 | |
1720 | // TODO(jingyue): Consider willNotOverflowSignedAdd and |
1721 | // willNotOverflowUnsignedAdd to reduce the number of invocations of |
1722 | // computeKnownBits. |
1723 | bool Changed = false; |
1724 | if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS: LHSCache, RHS: RHSCache, CxtI: I)) { |
1725 | Changed = true; |
1726 | I.setHasNoSignedWrap(true); |
1727 | } |
1728 | if (!I.hasNoUnsignedWrap() && |
1729 | willNotOverflowUnsignedAdd(LHS: LHSCache, RHS: RHSCache, CxtI: I)) { |
1730 | Changed = true; |
1731 | I.setHasNoUnsignedWrap(true); |
1732 | } |
1733 | |
1734 | if (Instruction *V = canonicalizeLowbitMask(I, Builder)) |
1735 | return V; |
1736 | |
1737 | if (Instruction *V = |
1738 | canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I)) |
1739 | return V; |
1740 | |
1741 | if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I)) |
1742 | return SatAdd; |
1743 | |
1744 | // usub.sat(A, B) + B => umax(A, B) |
1745 | if (match(&I, m_c_BinOp( |
1746 | m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))), |
1747 | m_Deferred(B)))) { |
1748 | return replaceInstUsesWith(I, |
1749 | V: Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B})); |
1750 | } |
1751 | |
1752 | // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common. |
1753 | if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) && |
1754 | match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) && |
1755 | haveNoCommonBitsSet(A, B, SQ.getWithInstruction(&I))) |
1756 | return replaceInstUsesWith( |
1757 | I, V: Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()}, |
1758 | {Builder.CreateOr(LHS: A, RHS: B)})); |
1759 | |
1760 | // Fold the log2_ceil idiom: |
1761 | // zext(ctpop(A) >u/!= 1) + (ctlz(A, true) ^ (BW - 1)) |
1762 | // --> |
1763 | // BW - ctlz(A - 1, false) |
1764 | const APInt *XorC; |
1765 | if (match(&I, |
1766 | m_c_Add( |
1767 | m_ZExt(m_ICmp(Pred, m_Intrinsic<Intrinsic::ctpop>(m_Value(A)), |
1768 | m_One())), |
1769 | m_OneUse(m_ZExtOrSelf(m_OneUse(m_Xor( |
1770 | m_OneUse(m_TruncOrSelf(m_OneUse( |
1771 | m_Intrinsic<Intrinsic::ctlz>(m_Deferred(A), m_One())))), |
1772 | m_APInt(XorC))))))) && |
1773 | (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_NE) && |
1774 | *XorC == A->getType()->getScalarSizeInBits() - 1) { |
1775 | Value *Sub = Builder.CreateAdd(LHS: A, RHS: Constant::getAllOnesValue(Ty: A->getType())); |
1776 | Value *Ctlz = Builder.CreateIntrinsic(Intrinsic::ctlz, {A->getType()}, |
1777 | {Sub, Builder.getFalse()}); |
1778 | Value *Ret = Builder.CreateSub( |
1779 | LHS: ConstantInt::get(Ty: A->getType(), V: A->getType()->getScalarSizeInBits()), |
1780 | RHS: Ctlz, Name: "" , /*HasNUW*/ true, /*HasNSW*/ true); |
1781 | return replaceInstUsesWith(I, V: Builder.CreateZExtOrTrunc(V: Ret, DestTy: I.getType())); |
1782 | } |
1783 | |
1784 | if (Instruction *Res = foldSquareSumInt(I)) |
1785 | return Res; |
1786 | |
1787 | if (Instruction *Res = foldBinOpOfDisplacedShifts(I)) |
1788 | return Res; |
1789 | |
1790 | if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I)) |
1791 | return Res; |
1792 | |
1793 | return Changed ? &I : nullptr; |
1794 | } |
1795 | |
1796 | /// Eliminate an op from a linear interpolation (lerp) pattern. |
1797 | static Instruction *factorizeLerp(BinaryOperator &I, |
1798 | InstCombiner::BuilderTy &Builder) { |
1799 | Value *X, *Y, *Z; |
1800 | if (!match(V: &I, P: m_c_FAdd(L: m_OneUse(SubPattern: m_c_FMul(L: m_Value(V&: Y), |
1801 | R: m_OneUse(SubPattern: m_FSub(L: m_FPOne(), |
1802 | R: m_Value(V&: Z))))), |
1803 | R: m_OneUse(SubPattern: m_c_FMul(L: m_Value(V&: X), R: m_Deferred(V: Z)))))) |
1804 | return nullptr; |
1805 | |
1806 | // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants] |
1807 | Value *XY = Builder.CreateFSubFMF(L: X, R: Y, FMFSource: &I); |
1808 | Value *MulZ = Builder.CreateFMulFMF(L: Z, R: XY, FMFSource: &I); |
1809 | return BinaryOperator::CreateFAddFMF(V1: Y, V2: MulZ, FMFSource: &I); |
1810 | } |
1811 | |
1812 | /// Factor a common operand out of fadd/fsub of fmul/fdiv. |
1813 | static Instruction *factorizeFAddFSub(BinaryOperator &I, |
1814 | InstCombiner::BuilderTy &Builder) { |
1815 | assert((I.getOpcode() == Instruction::FAdd || |
1816 | I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub" ); |
1817 | assert(I.hasAllowReassoc() && I.hasNoSignedZeros() && |
1818 | "FP factorization requires FMF" ); |
1819 | |
1820 | if (Instruction *Lerp = factorizeLerp(I, Builder)) |
1821 | return Lerp; |
1822 | |
1823 | Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1); |
1824 | if (!Op0->hasOneUse() || !Op1->hasOneUse()) |
1825 | return nullptr; |
1826 | |
1827 | Value *X, *Y, *Z; |
1828 | bool IsFMul; |
1829 | if ((match(V: Op0, P: m_FMul(L: m_Value(V&: X), R: m_Value(V&: Z))) && |
1830 | match(V: Op1, P: m_c_FMul(L: m_Value(V&: Y), R: m_Specific(V: Z)))) || |
1831 | (match(V: Op0, P: m_FMul(L: m_Value(V&: Z), R: m_Value(V&: X))) && |
1832 | match(V: Op1, P: m_c_FMul(L: m_Value(V&: Y), R: m_Specific(V: Z))))) |
1833 | IsFMul = true; |
1834 | else if (match(V: Op0, P: m_FDiv(L: m_Value(V&: X), R: m_Value(V&: Z))) && |
1835 | match(V: Op1, P: m_FDiv(L: m_Value(V&: Y), R: m_Specific(V: Z)))) |
1836 | IsFMul = false; |
1837 | else |
1838 | return nullptr; |
1839 | |
1840 | // (X * Z) + (Y * Z) --> (X + Y) * Z |
1841 | // (X * Z) - (Y * Z) --> (X - Y) * Z |
1842 | // (X / Z) + (Y / Z) --> (X + Y) / Z |
1843 | // (X / Z) - (Y / Z) --> (X - Y) / Z |
1844 | bool IsFAdd = I.getOpcode() == Instruction::FAdd; |
1845 | Value *XY = IsFAdd ? Builder.CreateFAddFMF(L: X, R: Y, FMFSource: &I) |
1846 | : Builder.CreateFSubFMF(L: X, R: Y, FMFSource: &I); |
1847 | |
1848 | // Bail out if we just created a denormal constant. |
1849 | // TODO: This is copied from a previous implementation. Is it necessary? |
1850 | const APFloat *C; |
1851 | if (match(V: XY, P: m_APFloat(Res&: C)) && !C->isNormal()) |
1852 | return nullptr; |
1853 | |
1854 | return IsFMul ? BinaryOperator::CreateFMulFMF(V1: XY, V2: Z, FMFSource: &I) |
1855 | : BinaryOperator::CreateFDivFMF(V1: XY, V2: Z, FMFSource: &I); |
1856 | } |
1857 | |
1858 | Instruction *InstCombinerImpl::visitFAdd(BinaryOperator &I) { |
1859 | if (Value *V = simplifyFAddInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), |
1860 | FMF: I.getFastMathFlags(), |
1861 | Q: SQ.getWithInstruction(I: &I))) |
1862 | return replaceInstUsesWith(I, V); |
1863 | |
1864 | if (SimplifyAssociativeOrCommutative(I)) |
1865 | return &I; |
1866 | |
1867 | if (Instruction *X = foldVectorBinop(Inst&: I)) |
1868 | return X; |
1869 | |
1870 | if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I)) |
1871 | return Phi; |
1872 | |
1873 | if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I)) |
1874 | return FoldedFAdd; |
1875 | |
1876 | // (-X) + Y --> Y - X |
1877 | Value *X, *Y; |
1878 | if (match(V: &I, P: m_c_FAdd(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y)))) |
1879 | return BinaryOperator::CreateFSubFMF(V1: Y, V2: X, FMFSource: &I); |
1880 | |
1881 | // Similar to above, but look through fmul/fdiv for the negated term. |
1882 | // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants] |
1883 | Value *Z; |
1884 | if (match(V: &I, P: m_c_FAdd(L: m_OneUse(SubPattern: m_c_FMul(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y))), |
1885 | R: m_Value(V&: Z)))) { |
1886 | Value *XY = Builder.CreateFMulFMF(L: X, R: Y, FMFSource: &I); |
1887 | return BinaryOperator::CreateFSubFMF(V1: Z, V2: XY, FMFSource: &I); |
1888 | } |
1889 | // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants] |
1890 | // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants] |
1891 | if (match(V: &I, P: m_c_FAdd(L: m_OneUse(SubPattern: m_FDiv(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y))), |
1892 | R: m_Value(V&: Z))) || |
1893 | match(V: &I, P: m_c_FAdd(L: m_OneUse(SubPattern: m_FDiv(L: m_Value(V&: X), R: m_FNeg(X: m_Value(V&: Y)))), |
1894 | R: m_Value(V&: Z)))) { |
1895 | Value *XY = Builder.CreateFDivFMF(L: X, R: Y, FMFSource: &I); |
1896 | return BinaryOperator::CreateFSubFMF(V1: Z, V2: XY, FMFSource: &I); |
1897 | } |
1898 | |
1899 | // Check for (fadd double (sitofp x), y), see if we can merge this into an |
1900 | // integer add followed by a promotion. |
1901 | if (Instruction *R = foldFBinOpOfIntCasts(I)) |
1902 | return R; |
1903 | |
1904 | Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1); |
1905 | // Handle specials cases for FAdd with selects feeding the operation |
1906 | if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS)) |
1907 | return replaceInstUsesWith(I, V); |
1908 | |
1909 | if (I.hasAllowReassoc() && I.hasNoSignedZeros()) { |
1910 | if (Instruction *F = factorizeFAddFSub(I, Builder)) |
1911 | return F; |
1912 | |
1913 | if (Instruction *F = foldSquareSumFP(I)) |
1914 | return F; |
1915 | |
1916 | // Try to fold fadd into start value of reduction intrinsic. |
1917 | if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>( |
1918 | m_AnyZeroFP(), m_Value(X))), |
1919 | m_Value(Y)))) { |
1920 | // fadd (rdx 0.0, X), Y --> rdx Y, X |
1921 | return replaceInstUsesWith( |
1922 | I, V: Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd, |
1923 | {X->getType()}, {Y, X}, &I)); |
1924 | } |
1925 | const APFloat *StartC, *C; |
1926 | if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>( |
1927 | m_APFloat(StartC), m_Value(X)))) && |
1928 | match(RHS, m_APFloat(C))) { |
1929 | // fadd (rdx StartC, X), C --> rdx (C + StartC), X |
1930 | Constant *NewStartC = ConstantFP::get(Ty: I.getType(), V: *C + *StartC); |
1931 | return replaceInstUsesWith( |
1932 | I, V: Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd, |
1933 | {X->getType()}, {NewStartC, X}, &I)); |
1934 | } |
1935 | |
1936 | // (X * MulC) + X --> X * (MulC + 1.0) |
1937 | Constant *MulC; |
1938 | if (match(V: &I, P: m_c_FAdd(L: m_FMul(L: m_Value(V&: X), R: m_ImmConstant(C&: MulC)), |
1939 | R: m_Deferred(V: X)))) { |
1940 | if (Constant *NewMulC = ConstantFoldBinaryOpOperands( |
1941 | Opcode: Instruction::FAdd, LHS: MulC, RHS: ConstantFP::get(Ty: I.getType(), V: 1.0), DL)) |
1942 | return BinaryOperator::CreateFMulFMF(V1: X, V2: NewMulC, FMFSource: &I); |
1943 | } |
1944 | |
1945 | // (-X - Y) + (X + Z) --> Z - Y |
1946 | if (match(V: &I, P: m_c_FAdd(L: m_FSub(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y)), |
1947 | R: m_c_FAdd(L: m_Deferred(V: X), R: m_Value(V&: Z))))) |
1948 | return BinaryOperator::CreateFSubFMF(V1: Z, V2: Y, FMFSource: &I); |
1949 | |
1950 | if (Value *V = FAddCombine(Builder).simplify(I: &I)) |
1951 | return replaceInstUsesWith(I, V); |
1952 | } |
1953 | |
1954 | // minumum(X, Y) + maximum(X, Y) => X + Y. |
1955 | if (match(&I, |
1956 | m_c_FAdd(m_Intrinsic<Intrinsic::maximum>(m_Value(V&: X), m_Value(V&: Y)), |
1957 | m_c_Intrinsic<Intrinsic::minimum>(m_Deferred(V: X), |
1958 | m_Deferred(V: Y))))) { |
1959 | BinaryOperator *Result = BinaryOperator::CreateFAddFMF(V1: X, V2: Y, FMFSource: &I); |
1960 | // We cannot preserve ninf if nnan flag is not set. |
1961 | // If X is NaN and Y is Inf then in original program we had NaN + NaN, |
1962 | // while in optimized version NaN + Inf and this is a poison with ninf flag. |
1963 | if (!Result->hasNoNaNs()) |
1964 | Result->setHasNoInfs(false); |
1965 | return Result; |
1966 | } |
1967 | |
1968 | return nullptr; |
1969 | } |
1970 | |
1971 | /// Optimize pointer differences into the same array into a size. Consider: |
1972 | /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer |
1973 | /// operands to the ptrtoint instructions for the LHS/RHS of the subtract. |
1974 | Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS, |
1975 | Type *Ty, bool IsNUW) { |
1976 | // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize |
1977 | // this. |
1978 | bool Swapped = false; |
1979 | GEPOperator *GEP1 = nullptr, *GEP2 = nullptr; |
1980 | if (!isa<GEPOperator>(Val: LHS) && isa<GEPOperator>(Val: RHS)) { |
1981 | std::swap(a&: LHS, b&: RHS); |
1982 | Swapped = true; |
1983 | } |
1984 | |
1985 | // Require at least one GEP with a common base pointer on both sides. |
1986 | if (auto *LHSGEP = dyn_cast<GEPOperator>(Val: LHS)) { |
1987 | // (gep X, ...) - X |
1988 | if (LHSGEP->getOperand(i_nocapture: 0)->stripPointerCasts() == |
1989 | RHS->stripPointerCasts()) { |
1990 | GEP1 = LHSGEP; |
1991 | } else if (auto *RHSGEP = dyn_cast<GEPOperator>(Val: RHS)) { |
1992 | // (gep X, ...) - (gep X, ...) |
1993 | if (LHSGEP->getOperand(i_nocapture: 0)->stripPointerCasts() == |
1994 | RHSGEP->getOperand(i_nocapture: 0)->stripPointerCasts()) { |
1995 | GEP1 = LHSGEP; |
1996 | GEP2 = RHSGEP; |
1997 | } |
1998 | } |
1999 | } |
2000 | |
2001 | if (!GEP1) |
2002 | return nullptr; |
2003 | |
2004 | if (GEP2) { |
2005 | // (gep X, ...) - (gep X, ...) |
2006 | // |
2007 | // Avoid duplicating the arithmetic if there are more than one non-constant |
2008 | // indices between the two GEPs and either GEP has a non-constant index and |
2009 | // multiple users. If zero non-constant index, the result is a constant and |
2010 | // there is no duplication. If one non-constant index, the result is an add |
2011 | // or sub with a constant, which is no larger than the original code, and |
2012 | // there's no duplicated arithmetic, even if either GEP has multiple |
2013 | // users. If more than one non-constant indices combined, as long as the GEP |
2014 | // with at least one non-constant index doesn't have multiple users, there |
2015 | // is no duplication. |
2016 | unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices(); |
2017 | unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices(); |
2018 | if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 && |
2019 | ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) || |
2020 | (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) { |
2021 | return nullptr; |
2022 | } |
2023 | } |
2024 | |
2025 | // Emit the offset of the GEP and an intptr_t. |
2026 | Value *Result = EmitGEPOffset(GEP: GEP1); |
2027 | |
2028 | // If this is a single inbounds GEP and the original sub was nuw, |
2029 | // then the final multiplication is also nuw. |
2030 | if (auto *I = dyn_cast<Instruction>(Val: Result)) |
2031 | if (IsNUW && !GEP2 && !Swapped && GEP1->isInBounds() && |
2032 | I->getOpcode() == Instruction::Mul) |
2033 | I->setHasNoUnsignedWrap(); |
2034 | |
2035 | // If we have a 2nd GEP of the same base pointer, subtract the offsets. |
2036 | // If both GEPs are inbounds, then the subtract does not have signed overflow. |
2037 | if (GEP2) { |
2038 | Value *Offset = EmitGEPOffset(GEP: GEP2); |
2039 | Result = Builder.CreateSub(LHS: Result, RHS: Offset, Name: "gepdiff" , /* NUW */ HasNUW: false, |
2040 | HasNSW: GEP1->isInBounds() && GEP2->isInBounds()); |
2041 | } |
2042 | |
2043 | // If we have p - gep(p, ...) then we have to negate the result. |
2044 | if (Swapped) |
2045 | Result = Builder.CreateNeg(V: Result, Name: "diff.neg" ); |
2046 | |
2047 | return Builder.CreateIntCast(V: Result, DestTy: Ty, isSigned: true); |
2048 | } |
2049 | |
2050 | static Instruction *foldSubOfMinMax(BinaryOperator &I, |
2051 | InstCombiner::BuilderTy &Builder) { |
2052 | Value *Op0 = I.getOperand(i_nocapture: 0); |
2053 | Value *Op1 = I.getOperand(i_nocapture: 1); |
2054 | Type *Ty = I.getType(); |
2055 | auto *MinMax = dyn_cast<MinMaxIntrinsic>(Val: Op1); |
2056 | if (!MinMax) |
2057 | return nullptr; |
2058 | |
2059 | // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y) |
2060 | // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y) |
2061 | Value *X = MinMax->getLHS(); |
2062 | Value *Y = MinMax->getRHS(); |
2063 | if (match(V: Op0, P: m_c_Add(L: m_Specific(V: X), R: m_Specific(V: Y))) && |
2064 | (Op0->hasOneUse() || Op1->hasOneUse())) { |
2065 | Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMaxID: MinMax->getIntrinsicID()); |
2066 | Function *F = Intrinsic::getDeclaration(M: I.getModule(), id: InvID, Tys: Ty); |
2067 | return CallInst::Create(Func: F, Args: {X, Y}); |
2068 | } |
2069 | |
2070 | // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z)) |
2071 | // sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Z,Y)) |
2072 | Value *Z; |
2073 | if (match(V: Op1, P: m_OneUse(SubPattern: m_UMin(L: m_Value(V&: Y), R: m_Value(V&: Z))))) { |
2074 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Add(L: m_Specific(V: Y), R: m_Value(V&: X))))) { |
2075 | Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Y, Z}); |
2076 | return BinaryOperator::CreateAdd(V1: X, V2: USub); |
2077 | } |
2078 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Add(L: m_Specific(V: Z), R: m_Value(V&: X))))) { |
2079 | Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Z, Y}); |
2080 | return BinaryOperator::CreateAdd(V1: X, V2: USub); |
2081 | } |
2082 | } |
2083 | |
2084 | // sub Op0, smin((sub nsw Op0, Z), 0) --> smax Op0, Z |
2085 | // sub Op0, smax((sub nsw Op0, Z), 0) --> smin Op0, Z |
2086 | if (MinMax->isSigned() && match(V: Y, P: m_ZeroInt()) && |
2087 | match(V: X, P: m_NSWSub(L: m_Specific(V: Op0), R: m_Value(V&: Z)))) { |
2088 | Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMaxID: MinMax->getIntrinsicID()); |
2089 | Function *F = Intrinsic::getDeclaration(M: I.getModule(), id: InvID, Tys: Ty); |
2090 | return CallInst::Create(Func: F, Args: {Op0, Z}); |
2091 | } |
2092 | |
2093 | return nullptr; |
2094 | } |
2095 | |
2096 | Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) { |
2097 | if (Value *V = simplifySubInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), |
2098 | IsNSW: I.hasNoSignedWrap(), IsNUW: I.hasNoUnsignedWrap(), |
2099 | Q: SQ.getWithInstruction(I: &I))) |
2100 | return replaceInstUsesWith(I, V); |
2101 | |
2102 | if (Instruction *X = foldVectorBinop(Inst&: I)) |
2103 | return X; |
2104 | |
2105 | if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I)) |
2106 | return Phi; |
2107 | |
2108 | Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1); |
2109 | |
2110 | // If this is a 'B = x-(-A)', change to B = x+A. |
2111 | // We deal with this without involving Negator to preserve NSW flag. |
2112 | if (Value *V = dyn_castNegVal(V: Op1)) { |
2113 | BinaryOperator *Res = BinaryOperator::CreateAdd(V1: Op0, V2: V); |
2114 | |
2115 | if (const auto *BO = dyn_cast<BinaryOperator>(Val: Op1)) { |
2116 | assert(BO->getOpcode() == Instruction::Sub && |
2117 | "Expected a subtraction operator!" ); |
2118 | if (BO->hasNoSignedWrap() && I.hasNoSignedWrap()) |
2119 | Res->setHasNoSignedWrap(true); |
2120 | } else { |
2121 | if (cast<Constant>(Val: Op1)->isNotMinSignedValue() && I.hasNoSignedWrap()) |
2122 | Res->setHasNoSignedWrap(true); |
2123 | } |
2124 | |
2125 | return Res; |
2126 | } |
2127 | |
2128 | // Try this before Negator to preserve NSW flag. |
2129 | if (Instruction *R = factorizeMathWithShlOps(I, Builder)) |
2130 | return R; |
2131 | |
2132 | Constant *C; |
2133 | if (match(V: Op0, P: m_ImmConstant(C))) { |
2134 | Value *X; |
2135 | Constant *C2; |
2136 | |
2137 | // C-(X+C2) --> (C-C2)-X |
2138 | if (match(V: Op1, P: m_Add(L: m_Value(V&: X), R: m_ImmConstant(C&: C2)))) { |
2139 | // C-C2 never overflow, and C-(X+C2), (X+C2) has NSW/NUW |
2140 | // => (C-C2)-X can have NSW/NUW |
2141 | bool WillNotSOV = willNotOverflowSignedSub(LHS: C, RHS: C2, CxtI: I); |
2142 | BinaryOperator *Res = |
2143 | BinaryOperator::CreateSub(V1: ConstantExpr::getSub(C1: C, C2), V2: X); |
2144 | auto *OBO1 = cast<OverflowingBinaryOperator>(Val: Op1); |
2145 | Res->setHasNoSignedWrap(I.hasNoSignedWrap() && OBO1->hasNoSignedWrap() && |
2146 | WillNotSOV); |
2147 | Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() && |
2148 | OBO1->hasNoUnsignedWrap()); |
2149 | return Res; |
2150 | } |
2151 | } |
2152 | |
2153 | auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * { |
2154 | if (Instruction *Ext = narrowMathIfNoOverflow(I)) |
2155 | return Ext; |
2156 | |
2157 | bool Changed = false; |
2158 | if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(LHS: Op0, RHS: Op1, CxtI: I)) { |
2159 | Changed = true; |
2160 | I.setHasNoSignedWrap(true); |
2161 | } |
2162 | if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(LHS: Op0, RHS: Op1, CxtI: I)) { |
2163 | Changed = true; |
2164 | I.setHasNoUnsignedWrap(true); |
2165 | } |
2166 | |
2167 | return Changed ? &I : nullptr; |
2168 | }; |
2169 | |
2170 | // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`, |
2171 | // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't |
2172 | // a pure negation used by a select that looks like abs/nabs. |
2173 | bool IsNegation = match(V: Op0, P: m_ZeroInt()); |
2174 | if (!IsNegation || none_of(Range: I.users(), P: [&I, Op1](const User *U) { |
2175 | const Instruction *UI = dyn_cast<Instruction>(Val: U); |
2176 | if (!UI) |
2177 | return false; |
2178 | return match(V: UI, |
2179 | P: m_Select(C: m_Value(), L: m_Specific(V: Op1), R: m_Specific(V: &I))) || |
2180 | match(V: UI, P: m_Select(C: m_Value(), L: m_Specific(V: &I), R: m_Specific(V: Op1))); |
2181 | })) { |
2182 | if (Value *NegOp1 = Negator::Negate(LHSIsZero: IsNegation, /* IsNSW */ IsNegation && |
2183 | I.hasNoSignedWrap(), |
2184 | Root: Op1, IC&: *this)) |
2185 | return BinaryOperator::CreateAdd(V1: NegOp1, V2: Op0); |
2186 | } |
2187 | if (IsNegation) |
2188 | return TryToNarrowDeduceFlags(); // Should have been handled in Negator! |
2189 | |
2190 | // (A*B)-(A*C) -> A*(B-C) etc |
2191 | if (Value *V = foldUsingDistributiveLaws(I)) |
2192 | return replaceInstUsesWith(I, V); |
2193 | |
2194 | if (I.getType()->isIntOrIntVectorTy(BitWidth: 1)) |
2195 | return BinaryOperator::CreateXor(V1: Op0, V2: Op1); |
2196 | |
2197 | // Replace (-1 - A) with (~A). |
2198 | if (match(V: Op0, P: m_AllOnes())) |
2199 | return BinaryOperator::CreateNot(Op: Op1); |
2200 | |
2201 | // (X + -1) - Y --> ~Y + X |
2202 | Value *X, *Y; |
2203 | if (match(V: Op0, P: m_OneUse(SubPattern: m_Add(L: m_Value(V&: X), R: m_AllOnes())))) |
2204 | return BinaryOperator::CreateAdd(V1: Builder.CreateNot(V: Op1), V2: X); |
2205 | |
2206 | // Reassociate sub/add sequences to create more add instructions and |
2207 | // reduce dependency chains: |
2208 | // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1) |
2209 | Value *Z; |
2210 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Add(L: m_OneUse(SubPattern: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Y))), |
2211 | R: m_Value(V&: Z))))) { |
2212 | Value *XZ = Builder.CreateAdd(LHS: X, RHS: Z); |
2213 | Value *YW = Builder.CreateAdd(LHS: Y, RHS: Op1); |
2214 | return BinaryOperator::CreateSub(V1: XZ, V2: YW); |
2215 | } |
2216 | |
2217 | // ((X - Y) - Op1) --> X - (Y + Op1) |
2218 | if (match(V: Op0, P: m_OneUse(SubPattern: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Y))))) { |
2219 | OverflowingBinaryOperator *LHSSub = cast<OverflowingBinaryOperator>(Val: Op0); |
2220 | bool HasNUW = I.hasNoUnsignedWrap() && LHSSub->hasNoUnsignedWrap(); |
2221 | bool HasNSW = HasNUW && I.hasNoSignedWrap() && LHSSub->hasNoSignedWrap(); |
2222 | Value *Add = Builder.CreateAdd(LHS: Y, RHS: Op1, Name: "" , /* HasNUW */ HasNUW, |
2223 | /* HasNSW */ HasNSW); |
2224 | BinaryOperator *Sub = BinaryOperator::CreateSub(V1: X, V2: Add); |
2225 | Sub->setHasNoUnsignedWrap(HasNUW); |
2226 | Sub->setHasNoSignedWrap(HasNSW); |
2227 | return Sub; |
2228 | } |
2229 | |
2230 | { |
2231 | // (X + Z) - (Y + Z) --> (X - Y) |
2232 | // This is done in other passes, but we want to be able to consume this |
2233 | // pattern in InstCombine so we can generate it without creating infinite |
2234 | // loops. |
2235 | if (match(V: Op0, P: m_Add(L: m_Value(V&: X), R: m_Value(V&: Z))) && |
2236 | match(V: Op1, P: m_c_Add(L: m_Value(V&: Y), R: m_Specific(V: Z)))) |
2237 | return BinaryOperator::CreateSub(V1: X, V2: Y); |
2238 | |
2239 | // (X + C0) - (Y + C1) --> (X - Y) + (C0 - C1) |
2240 | Constant *CX, *CY; |
2241 | if (match(V: Op0, P: m_OneUse(SubPattern: m_Add(L: m_Value(V&: X), R: m_ImmConstant(C&: CX)))) && |
2242 | match(V: Op1, P: m_OneUse(SubPattern: m_Add(L: m_Value(V&: Y), R: m_ImmConstant(C&: CY))))) { |
2243 | Value *OpsSub = Builder.CreateSub(LHS: X, RHS: Y); |
2244 | Constant *ConstsSub = ConstantExpr::getSub(C1: CX, C2: CY); |
2245 | return BinaryOperator::CreateAdd(V1: OpsSub, V2: ConstsSub); |
2246 | } |
2247 | } |
2248 | |
2249 | // (~X) - (~Y) --> Y - X |
2250 | { |
2251 | // Need to ensure we can consume at least one of the `not` instructions, |
2252 | // otherwise this can inf loop. |
2253 | bool ConsumesOp0, ConsumesOp1; |
2254 | if (isFreeToInvert(V: Op0, WillInvertAllUses: Op0->hasOneUse(), DoesConsume&: ConsumesOp0) && |
2255 | isFreeToInvert(V: Op1, WillInvertAllUses: Op1->hasOneUse(), DoesConsume&: ConsumesOp1) && |
2256 | (ConsumesOp0 || ConsumesOp1)) { |
2257 | Value *NotOp0 = getFreelyInverted(V: Op0, WillInvertAllUses: Op0->hasOneUse(), Builder: &Builder); |
2258 | Value *NotOp1 = getFreelyInverted(V: Op1, WillInvertAllUses: Op1->hasOneUse(), Builder: &Builder); |
2259 | assert(NotOp0 != nullptr && NotOp1 != nullptr && |
2260 | "isFreeToInvert desynced with getFreelyInverted" ); |
2261 | return BinaryOperator::CreateSub(V1: NotOp1, V2: NotOp0); |
2262 | } |
2263 | } |
2264 | |
2265 | auto m_AddRdx = [](Value *&Vec) { |
2266 | return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec))); |
2267 | }; |
2268 | Value *V0, *V1; |
2269 | if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) && |
2270 | V0->getType() == V1->getType()) { |
2271 | // Difference of sums is sum of differences: |
2272 | // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1) |
2273 | Value *Sub = Builder.CreateSub(LHS: V0, RHS: V1); |
2274 | Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add, |
2275 | {Sub->getType()}, {Sub}); |
2276 | return replaceInstUsesWith(I, V: Rdx); |
2277 | } |
2278 | |
2279 | if (Constant *C = dyn_cast<Constant>(Val: Op0)) { |
2280 | Value *X; |
2281 | if (match(V: Op1, P: m_ZExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) |
2282 | // C - (zext bool) --> bool ? C - 1 : C |
2283 | return SelectInst::Create(C: X, S1: InstCombiner::SubOne(C), S2: C); |
2284 | if (match(V: Op1, P: m_SExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) |
2285 | // C - (sext bool) --> bool ? C + 1 : C |
2286 | return SelectInst::Create(C: X, S1: InstCombiner::AddOne(C), S2: C); |
2287 | |
2288 | // C - ~X == X + (1+C) |
2289 | if (match(V: Op1, P: m_Not(V: m_Value(V&: X)))) |
2290 | return BinaryOperator::CreateAdd(V1: X, V2: InstCombiner::AddOne(C)); |
2291 | |
2292 | // Try to fold constant sub into select arguments. |
2293 | if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op1)) |
2294 | if (Instruction *R = FoldOpIntoSelect(Op&: I, SI)) |
2295 | return R; |
2296 | |
2297 | // Try to fold constant sub into PHI values. |
2298 | if (PHINode *PN = dyn_cast<PHINode>(Val: Op1)) |
2299 | if (Instruction *R = foldOpIntoPhi(I, PN)) |
2300 | return R; |
2301 | |
2302 | Constant *C2; |
2303 | |
2304 | // C-(C2-X) --> X+(C-C2) |
2305 | if (match(V: Op1, P: m_Sub(L: m_ImmConstant(C&: C2), R: m_Value(V&: X)))) |
2306 | return BinaryOperator::CreateAdd(V1: X, V2: ConstantExpr::getSub(C1: C, C2)); |
2307 | } |
2308 | |
2309 | const APInt *Op0C; |
2310 | if (match(V: Op0, P: m_APInt(Res&: Op0C))) { |
2311 | if (Op0C->isMask()) { |
2312 | // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known |
2313 | // zero. We don't use information from dominating conditions so this |
2314 | // transform is easier to reverse if necessary. |
2315 | KnownBits RHSKnown = llvm::computeKnownBits( |
2316 | V: Op1, Depth: 0, Q: SQ.getWithInstruction(I: &I).getWithoutDomCondCache()); |
2317 | if ((*Op0C | RHSKnown.Zero).isAllOnes()) |
2318 | return BinaryOperator::CreateXor(V1: Op1, V2: Op0); |
2319 | } |
2320 | |
2321 | // C - ((C3 -nuw X) & C2) --> (C - (C2 & C3)) + (X & C2) when: |
2322 | // (C3 - ((C2 & C3) - 1)) is pow2 |
2323 | // ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1) |
2324 | // C2 is negative pow2 || sub nuw |
2325 | const APInt *C2, *C3; |
2326 | BinaryOperator *InnerSub; |
2327 | if (match(V: Op1, P: m_OneUse(SubPattern: m_And(L: m_BinOp(I&: InnerSub), R: m_APInt(Res&: C2)))) && |
2328 | match(V: InnerSub, P: m_Sub(L: m_APInt(Res&: C3), R: m_Value(V&: X))) && |
2329 | (InnerSub->hasNoUnsignedWrap() || C2->isNegatedPowerOf2())) { |
2330 | APInt C2AndC3 = *C2 & *C3; |
2331 | APInt C2AndC3Minus1 = C2AndC3 - 1; |
2332 | APInt C2AddC3 = *C2 + *C3; |
2333 | if ((*C3 - C2AndC3Minus1).isPowerOf2() && |
2334 | C2AndC3Minus1.isSubsetOf(RHS: C2AddC3)) { |
2335 | Value *And = Builder.CreateAnd(LHS: X, RHS: ConstantInt::get(Ty: I.getType(), V: *C2)); |
2336 | return BinaryOperator::CreateAdd( |
2337 | V1: And, V2: ConstantInt::get(Ty: I.getType(), V: *Op0C - C2AndC3)); |
2338 | } |
2339 | } |
2340 | } |
2341 | |
2342 | { |
2343 | Value *Y; |
2344 | // X-(X+Y) == -Y X-(Y+X) == -Y |
2345 | if (match(V: Op1, P: m_c_Add(L: m_Specific(V: Op0), R: m_Value(V&: Y)))) |
2346 | return BinaryOperator::CreateNeg(Op: Y); |
2347 | |
2348 | // (X-Y)-X == -Y |
2349 | if (match(V: Op0, P: m_Sub(L: m_Specific(V: Op1), R: m_Value(V&: Y)))) |
2350 | return BinaryOperator::CreateNeg(Op: Y); |
2351 | } |
2352 | |
2353 | // (sub (or A, B) (and A, B)) --> (xor A, B) |
2354 | { |
2355 | Value *A, *B; |
2356 | if (match(V: Op1, P: m_And(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2357 | match(V: Op0, P: m_c_Or(L: m_Specific(V: A), R: m_Specific(V: B)))) |
2358 | return BinaryOperator::CreateXor(V1: A, V2: B); |
2359 | } |
2360 | |
2361 | // (sub (add A, B) (or A, B)) --> (and A, B) |
2362 | { |
2363 | Value *A, *B; |
2364 | if (match(V: Op0, P: m_Add(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2365 | match(V: Op1, P: m_c_Or(L: m_Specific(V: A), R: m_Specific(V: B)))) |
2366 | return BinaryOperator::CreateAnd(V1: A, V2: B); |
2367 | } |
2368 | |
2369 | // (sub (add A, B) (and A, B)) --> (or A, B) |
2370 | { |
2371 | Value *A, *B; |
2372 | if (match(V: Op0, P: m_Add(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2373 | match(V: Op1, P: m_c_And(L: m_Specific(V: A), R: m_Specific(V: B)))) |
2374 | return BinaryOperator::CreateOr(V1: A, V2: B); |
2375 | } |
2376 | |
2377 | // (sub (and A, B) (or A, B)) --> neg (xor A, B) |
2378 | { |
2379 | Value *A, *B; |
2380 | if (match(V: Op0, P: m_And(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2381 | match(V: Op1, P: m_c_Or(L: m_Specific(V: A), R: m_Specific(V: B))) && |
2382 | (Op0->hasOneUse() || Op1->hasOneUse())) |
2383 | return BinaryOperator::CreateNeg(Op: Builder.CreateXor(LHS: A, RHS: B)); |
2384 | } |
2385 | |
2386 | // (sub (or A, B), (xor A, B)) --> (and A, B) |
2387 | { |
2388 | Value *A, *B; |
2389 | if (match(V: Op1, P: m_Xor(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2390 | match(V: Op0, P: m_c_Or(L: m_Specific(V: A), R: m_Specific(V: B)))) |
2391 | return BinaryOperator::CreateAnd(V1: A, V2: B); |
2392 | } |
2393 | |
2394 | // (sub (xor A, B) (or A, B)) --> neg (and A, B) |
2395 | { |
2396 | Value *A, *B; |
2397 | if (match(V: Op0, P: m_Xor(L: m_Value(V&: A), R: m_Value(V&: B))) && |
2398 | match(V: Op1, P: m_c_Or(L: m_Specific(V: A), R: m_Specific(V: B))) && |
2399 | (Op0->hasOneUse() || Op1->hasOneUse())) |
2400 | return BinaryOperator::CreateNeg(Op: Builder.CreateAnd(LHS: A, RHS: B)); |
2401 | } |
2402 | |
2403 | { |
2404 | Value *Y; |
2405 | // ((X | Y) - X) --> (~X & Y) |
2406 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Or(L: m_Value(V&: Y), R: m_Specific(V: Op1))))) |
2407 | return BinaryOperator::CreateAnd( |
2408 | V1: Y, V2: Builder.CreateNot(V: Op1, Name: Op1->getName() + ".not" )); |
2409 | } |
2410 | |
2411 | { |
2412 | // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1)) |
2413 | Value *X; |
2414 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_And(L: m_Specific(V: Op1), |
2415 | R: m_OneUse(SubPattern: m_Neg(V: m_Value(V&: X))))))) { |
2416 | return BinaryOperator::CreateNeg(Op: Builder.CreateAnd( |
2417 | LHS: Op1, RHS: Builder.CreateAdd(LHS: X, RHS: Constant::getAllOnesValue(Ty: I.getType())))); |
2418 | } |
2419 | } |
2420 | |
2421 | { |
2422 | // (sub (and Op1, C), Op1) --> neg (and Op1, ~C) |
2423 | Constant *C; |
2424 | if (match(V: Op0, P: m_OneUse(SubPattern: m_And(L: m_Specific(V: Op1), R: m_Constant(C))))) { |
2425 | return BinaryOperator::CreateNeg( |
2426 | Op: Builder.CreateAnd(LHS: Op1, RHS: Builder.CreateNot(V: C))); |
2427 | } |
2428 | } |
2429 | |
2430 | { |
2431 | // (sub (xor X, (sext C)), (sext C)) => (select C, (neg X), X) |
2432 | // (sub (sext C), (xor X, (sext C))) => (select C, X, (neg X)) |
2433 | Value *C, *X; |
2434 | auto m_SubXorCmp = [&C, &X](Value *LHS, Value *RHS) { |
2435 | return match(V: LHS, P: m_OneUse(SubPattern: m_c_Xor(L: m_Value(V&: X), R: m_Specific(V: RHS)))) && |
2436 | match(V: RHS, P: m_SExt(Op: m_Value(V&: C))) && |
2437 | (C->getType()->getScalarSizeInBits() == 1); |
2438 | }; |
2439 | if (m_SubXorCmp(Op0, Op1)) |
2440 | return SelectInst::Create(C, S1: Builder.CreateNeg(V: X), S2: X); |
2441 | if (m_SubXorCmp(Op1, Op0)) |
2442 | return SelectInst::Create(C, S1: X, S2: Builder.CreateNeg(V: X)); |
2443 | } |
2444 | |
2445 | if (Instruction *R = tryFoldInstWithCtpopWithNot(I: &I)) |
2446 | return R; |
2447 | |
2448 | if (Instruction *R = foldSubOfMinMax(I, Builder)) |
2449 | return R; |
2450 | |
2451 | { |
2452 | // If we have a subtraction between some value and a select between |
2453 | // said value and something else, sink subtraction into select hands, i.e.: |
2454 | // sub (select %Cond, %TrueVal, %FalseVal), %Op1 |
2455 | // -> |
2456 | // select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1) |
2457 | // or |
2458 | // sub %Op0, (select %Cond, %TrueVal, %FalseVal) |
2459 | // -> |
2460 | // select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal) |
2461 | // This will result in select between new subtraction and 0. |
2462 | auto SinkSubIntoSelect = |
2463 | [Ty = I.getType()](Value *Select, Value *OtherHandOfSub, |
2464 | auto SubBuilder) -> Instruction * { |
2465 | Value *Cond, *TrueVal, *FalseVal; |
2466 | if (!match(V: Select, P: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: TrueVal), |
2467 | R: m_Value(V&: FalseVal))))) |
2468 | return nullptr; |
2469 | if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal) |
2470 | return nullptr; |
2471 | // While it is really tempting to just create two subtractions and let |
2472 | // InstCombine fold one of those to 0, it isn't possible to do so |
2473 | // because of worklist visitation order. So ugly it is. |
2474 | bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal; |
2475 | Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal); |
2476 | Constant *Zero = Constant::getNullValue(Ty); |
2477 | SelectInst *NewSel = |
2478 | SelectInst::Create(C: Cond, S1: OtherHandOfSubIsTrueVal ? Zero : NewSub, |
2479 | S2: OtherHandOfSubIsTrueVal ? NewSub : Zero); |
2480 | // Preserve prof metadata if any. |
2481 | NewSel->copyMetadata(SrcInst: cast<Instruction>(Val&: *Select)); |
2482 | return NewSel; |
2483 | }; |
2484 | if (Instruction *NewSel = SinkSubIntoSelect( |
2485 | /*Select=*/Op0, /*OtherHandOfSub=*/Op1, |
2486 | [Builder = &Builder, Op1](Value *OtherHandOfSelect) { |
2487 | return Builder->CreateSub(LHS: OtherHandOfSelect, |
2488 | /*OtherHandOfSub=*/RHS: Op1); |
2489 | })) |
2490 | return NewSel; |
2491 | if (Instruction *NewSel = SinkSubIntoSelect( |
2492 | /*Select=*/Op1, /*OtherHandOfSub=*/Op0, |
2493 | [Builder = &Builder, Op0](Value *OtherHandOfSelect) { |
2494 | return Builder->CreateSub(/*OtherHandOfSub=*/LHS: Op0, |
2495 | RHS: OtherHandOfSelect); |
2496 | })) |
2497 | return NewSel; |
2498 | } |
2499 | |
2500 | // (X - (X & Y)) --> (X & ~Y) |
2501 | if (match(V: Op1, P: m_c_And(L: m_Specific(V: Op0), R: m_Value(V&: Y))) && |
2502 | (Op1->hasOneUse() || isa<Constant>(Val: Y))) |
2503 | return BinaryOperator::CreateAnd( |
2504 | V1: Op0, V2: Builder.CreateNot(V: Y, Name: Y->getName() + ".not" )); |
2505 | |
2506 | // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X |
2507 | // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X |
2508 | // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y) |
2509 | // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y) |
2510 | // As long as Y is freely invertible, this will be neutral or a win. |
2511 | // Note: We don't generate the inverse max/min, just create the 'not' of |
2512 | // it and let other folds do the rest. |
2513 | if (match(V: Op0, P: m_Not(V: m_Value(V&: X))) && |
2514 | match(V: Op1, P: m_c_MaxOrMin(L: m_Specific(V: Op0), R: m_Value(V&: Y))) && |
2515 | !Op0->hasNUsesOrMore(N: 3) && isFreeToInvert(V: Y, WillInvertAllUses: Y->hasOneUse())) { |
2516 | Value *Not = Builder.CreateNot(V: Op1); |
2517 | return BinaryOperator::CreateSub(V1: Not, V2: X); |
2518 | } |
2519 | if (match(V: Op1, P: m_Not(V: m_Value(V&: X))) && |
2520 | match(V: Op0, P: m_c_MaxOrMin(L: m_Specific(V: Op1), R: m_Value(V&: Y))) && |
2521 | !Op1->hasNUsesOrMore(N: 3) && isFreeToInvert(V: Y, WillInvertAllUses: Y->hasOneUse())) { |
2522 | Value *Not = Builder.CreateNot(V: Op0); |
2523 | return BinaryOperator::CreateSub(V1: X, V2: Not); |
2524 | } |
2525 | |
2526 | // Optimize pointer differences into the same array into a size. Consider: |
2527 | // &A[10] - &A[0]: we should compile this to "10". |
2528 | Value *LHSOp, *RHSOp; |
2529 | if (match(V: Op0, P: m_PtrToInt(Op: m_Value(V&: LHSOp))) && |
2530 | match(V: Op1, P: m_PtrToInt(Op: m_Value(V&: RHSOp)))) |
2531 | if (Value *Res = OptimizePointerDifference(LHS: LHSOp, RHS: RHSOp, Ty: I.getType(), |
2532 | IsNUW: I.hasNoUnsignedWrap())) |
2533 | return replaceInstUsesWith(I, V: Res); |
2534 | |
2535 | // trunc(p)-trunc(q) -> trunc(p-q) |
2536 | if (match(V: Op0, P: m_Trunc(Op: m_PtrToInt(Op: m_Value(V&: LHSOp)))) && |
2537 | match(V: Op1, P: m_Trunc(Op: m_PtrToInt(Op: m_Value(V&: RHSOp))))) |
2538 | if (Value *Res = OptimizePointerDifference(LHS: LHSOp, RHS: RHSOp, Ty: I.getType(), |
2539 | /* IsNUW */ false)) |
2540 | return replaceInstUsesWith(I, V: Res); |
2541 | |
2542 | // Canonicalize a shifty way to code absolute value to the common pattern. |
2543 | // There are 2 potential commuted variants. |
2544 | // We're relying on the fact that we only do this transform when the shift has |
2545 | // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase |
2546 | // instructions). |
2547 | Value *A; |
2548 | const APInt *ShAmt; |
2549 | Type *Ty = I.getType(); |
2550 | unsigned BitWidth = Ty->getScalarSizeInBits(); |
2551 | if (match(V: Op1, P: m_AShr(L: m_Value(V&: A), R: m_APInt(Res&: ShAmt))) && |
2552 | Op1->hasNUses(N: 2) && *ShAmt == BitWidth - 1 && |
2553 | match(V: Op0, P: m_OneUse(SubPattern: m_c_Xor(L: m_Specific(V: A), R: m_Specific(V: Op1))))) { |
2554 | // B = ashr i32 A, 31 ; smear the sign bit |
2555 | // sub (xor A, B), B ; flip bits if negative and subtract -1 (add 1) |
2556 | // --> (A < 0) ? -A : A |
2557 | Value *IsNeg = Builder.CreateIsNeg(Arg: A); |
2558 | // Copy the nsw flags from the sub to the negate. |
2559 | Value *NegA = I.hasNoUnsignedWrap() |
2560 | ? Constant::getNullValue(Ty: A->getType()) |
2561 | : Builder.CreateNeg(V: A, Name: "" , HasNSW: I.hasNoSignedWrap()); |
2562 | return SelectInst::Create(C: IsNeg, S1: NegA, S2: A); |
2563 | } |
2564 | |
2565 | // If we are subtracting a low-bit masked subset of some value from an add |
2566 | // of that same value with no low bits changed, that is clearing some low bits |
2567 | // of the sum: |
2568 | // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC |
2569 | const APInt *AddC, *AndC; |
2570 | if (match(V: Op0, P: m_Add(L: m_Value(V&: X), R: m_APInt(Res&: AddC))) && |
2571 | match(V: Op1, P: m_And(L: m_Specific(V: X), R: m_APInt(Res&: AndC)))) { |
2572 | unsigned Cttz = AddC->countr_zero(); |
2573 | APInt HighMask(APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - Cttz)); |
2574 | if ((HighMask & *AndC).isZero()) |
2575 | return BinaryOperator::CreateAnd(V1: Op0, V2: ConstantInt::get(Ty, V: ~(*AndC))); |
2576 | } |
2577 | |
2578 | if (Instruction *V = |
2579 | canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I)) |
2580 | return V; |
2581 | |
2582 | // X - usub.sat(X, Y) => umin(X, Y) |
2583 | if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0), |
2584 | m_Value(Y))))) |
2585 | return replaceInstUsesWith( |
2586 | I, V: Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y})); |
2587 | |
2588 | // umax(X, Op1) - Op1 --> usub.sat(X, Op1) |
2589 | // TODO: The one-use restriction is not strictly necessary, but it may |
2590 | // require improving other pattern matching and/or codegen. |
2591 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_UMax(L: m_Value(V&: X), R: m_Specific(V: Op1))))) |
2592 | return replaceInstUsesWith( |
2593 | I, V: Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1})); |
2594 | |
2595 | // Op0 - umin(X, Op0) --> usub.sat(Op0, X) |
2596 | if (match(V: Op1, P: m_OneUse(SubPattern: m_c_UMin(L: m_Value(V&: X), R: m_Specific(V: Op0))))) |
2597 | return replaceInstUsesWith( |
2598 | I, V: Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op0, X})); |
2599 | |
2600 | // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0) |
2601 | if (match(V: Op1, P: m_OneUse(SubPattern: m_c_UMax(L: m_Value(V&: X), R: m_Specific(V: Op0))))) { |
2602 | Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0}); |
2603 | return BinaryOperator::CreateNeg(Op: USub); |
2604 | } |
2605 | |
2606 | // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X) |
2607 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_UMin(L: m_Value(V&: X), R: m_Specific(V: Op1))))) { |
2608 | Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X}); |
2609 | return BinaryOperator::CreateNeg(Op: USub); |
2610 | } |
2611 | |
2612 | // C - ctpop(X) => ctpop(~X) if C is bitwidth |
2613 | if (match(Op0, m_SpecificInt(BitWidth)) && |
2614 | match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X))))) |
2615 | return replaceInstUsesWith( |
2616 | I, V: Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()}, |
2617 | {Builder.CreateNot(V: X)})); |
2618 | |
2619 | // Reduce multiplies for difference-of-squares by factoring: |
2620 | // (X * X) - (Y * Y) --> (X + Y) * (X - Y) |
2621 | if (match(V: Op0, P: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: X), R: m_Deferred(V: X)))) && |
2622 | match(V: Op1, P: m_OneUse(SubPattern: m_Mul(L: m_Value(V&: Y), R: m_Deferred(V: Y))))) { |
2623 | auto *OBO0 = cast<OverflowingBinaryOperator>(Val: Op0); |
2624 | auto *OBO1 = cast<OverflowingBinaryOperator>(Val: Op1); |
2625 | bool PropagateNSW = I.hasNoSignedWrap() && OBO0->hasNoSignedWrap() && |
2626 | OBO1->hasNoSignedWrap() && BitWidth > 2; |
2627 | bool PropagateNUW = I.hasNoUnsignedWrap() && OBO0->hasNoUnsignedWrap() && |
2628 | OBO1->hasNoUnsignedWrap() && BitWidth > 1; |
2629 | Value *Add = Builder.CreateAdd(LHS: X, RHS: Y, Name: "add" , HasNUW: PropagateNUW, HasNSW: PropagateNSW); |
2630 | Value *Sub = Builder.CreateSub(LHS: X, RHS: Y, Name: "sub" , HasNUW: PropagateNUW, HasNSW: PropagateNSW); |
2631 | Value *Mul = Builder.CreateMul(LHS: Add, RHS: Sub, Name: "" , HasNUW: PropagateNUW, HasNSW: PropagateNSW); |
2632 | return replaceInstUsesWith(I, V: Mul); |
2633 | } |
2634 | |
2635 | // max(X,Y) nsw/nuw - min(X,Y) --> abs(X nsw - Y) |
2636 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_SMax(L: m_Value(V&: X), R: m_Value(V&: Y)))) && |
2637 | match(V: Op1, P: m_OneUse(SubPattern: m_c_SMin(L: m_Specific(V: X), R: m_Specific(V: Y))))) { |
2638 | if (I.hasNoUnsignedWrap() || I.hasNoSignedWrap()) { |
2639 | Value *Sub = |
2640 | Builder.CreateSub(LHS: X, RHS: Y, Name: "sub" , /*HasNUW=*/false, /*HasNSW=*/true); |
2641 | Value *Call = |
2642 | Builder.CreateBinaryIntrinsic(Intrinsic::ID: abs, LHS: Sub, RHS: Builder.getTrue()); |
2643 | return replaceInstUsesWith(I, V: Call); |
2644 | } |
2645 | } |
2646 | |
2647 | if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I)) |
2648 | return Res; |
2649 | |
2650 | return TryToNarrowDeduceFlags(); |
2651 | } |
2652 | |
2653 | /// This eliminates floating-point negation in either 'fneg(X)' or |
2654 | /// 'fsub(-0.0, X)' form by combining into a constant operand. |
2655 | static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) { |
2656 | // This is limited with one-use because fneg is assumed better for |
2657 | // reassociation and cheaper in codegen than fmul/fdiv. |
2658 | // TODO: Should the m_OneUse restriction be removed? |
2659 | Instruction *FNegOp; |
2660 | if (!match(V: &I, P: m_FNeg(X: m_OneUse(SubPattern: m_Instruction(I&: FNegOp))))) |
2661 | return nullptr; |
2662 | |
2663 | Value *X; |
2664 | Constant *C; |
2665 | |
2666 | // Fold negation into constant operand. |
2667 | // -(X * C) --> X * (-C) |
2668 | if (match(V: FNegOp, P: m_FMul(L: m_Value(V&: X), R: m_Constant(C)))) |
2669 | if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL)) |
2670 | return BinaryOperator::CreateFMulFMF(V1: X, V2: NegC, FMFSource: &I); |
2671 | // -(X / C) --> X / (-C) |
2672 | if (match(V: FNegOp, P: m_FDiv(L: m_Value(V&: X), R: m_Constant(C)))) |
2673 | if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL)) |
2674 | return BinaryOperator::CreateFDivFMF(V1: X, V2: NegC, FMFSource: &I); |
2675 | // -(C / X) --> (-C) / X |
2676 | if (match(V: FNegOp, P: m_FDiv(L: m_Constant(C), R: m_Value(V&: X)))) |
2677 | if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL)) { |
2678 | Instruction *FDiv = BinaryOperator::CreateFDivFMF(V1: NegC, V2: X, FMFSource: &I); |
2679 | |
2680 | // Intersect 'nsz' and 'ninf' because those special value exceptions may |
2681 | // not apply to the fdiv. Everything else propagates from the fneg. |
2682 | // TODO: We could propagate nsz/ninf from fdiv alone? |
2683 | FastMathFlags FMF = I.getFastMathFlags(); |
2684 | FastMathFlags OpFMF = FNegOp->getFastMathFlags(); |
2685 | FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros()); |
2686 | FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs()); |
2687 | return FDiv; |
2688 | } |
2689 | // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]: |
2690 | // -(X + C) --> -X + -C --> -C - X |
2691 | if (I.hasNoSignedZeros() && match(V: FNegOp, P: m_FAdd(L: m_Value(V&: X), R: m_Constant(C)))) |
2692 | if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL)) |
2693 | return BinaryOperator::CreateFSubFMF(V1: NegC, V2: X, FMFSource: &I); |
2694 | |
2695 | return nullptr; |
2696 | } |
2697 | |
2698 | Instruction *InstCombinerImpl::hoistFNegAboveFMulFDiv(Value *FNegOp, |
2699 | Instruction &FMFSource) { |
2700 | Value *X, *Y; |
2701 | if (match(V: FNegOp, P: m_FMul(L: m_Value(V&: X), R: m_Value(V&: Y)))) { |
2702 | return cast<Instruction>(Val: Builder.CreateFMulFMF( |
2703 | L: Builder.CreateFNegFMF(V: X, FMFSource: &FMFSource), R: Y, FMFSource: &FMFSource)); |
2704 | } |
2705 | |
2706 | if (match(V: FNegOp, P: m_FDiv(L: m_Value(V&: X), R: m_Value(V&: Y)))) { |
2707 | return cast<Instruction>(Val: Builder.CreateFDivFMF( |
2708 | L: Builder.CreateFNegFMF(V: X, FMFSource: &FMFSource), R: Y, FMFSource: &FMFSource)); |
2709 | } |
2710 | |
2711 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: FNegOp)) { |
2712 | // Make sure to preserve flags and metadata on the call. |
2713 | if (II->getIntrinsicID() == Intrinsic::ldexp) { |
2714 | FastMathFlags FMF = FMFSource.getFastMathFlags() | II->getFastMathFlags(); |
2715 | IRBuilder<>::FastMathFlagGuard FMFGuard(Builder); |
2716 | Builder.setFastMathFlags(FMF); |
2717 | |
2718 | CallInst *New = Builder.CreateCall( |
2719 | Callee: II->getCalledFunction(), |
2720 | Args: {Builder.CreateFNeg(V: II->getArgOperand(i: 0)), II->getArgOperand(i: 1)}); |
2721 | New->copyMetadata(SrcInst: *II); |
2722 | return New; |
2723 | } |
2724 | } |
2725 | |
2726 | return nullptr; |
2727 | } |
2728 | |
2729 | Instruction *InstCombinerImpl::visitFNeg(UnaryOperator &I) { |
2730 | Value *Op = I.getOperand(i_nocapture: 0); |
2731 | |
2732 | if (Value *V = simplifyFNegInst(Op, FMF: I.getFastMathFlags(), |
2733 | Q: getSimplifyQuery().getWithInstruction(I: &I))) |
2734 | return replaceInstUsesWith(I, V); |
2735 | |
2736 | if (Instruction *X = foldFNegIntoConstant(I, DL)) |
2737 | return X; |
2738 | |
2739 | Value *X, *Y; |
2740 | |
2741 | // If we can ignore the sign of zeros: -(X - Y) --> (Y - X) |
2742 | if (I.hasNoSignedZeros() && |
2743 | match(V: Op, P: m_OneUse(SubPattern: m_FSub(L: m_Value(V&: X), R: m_Value(V&: Y))))) |
2744 | return BinaryOperator::CreateFSubFMF(V1: Y, V2: X, FMFSource: &I); |
2745 | |
2746 | Value *OneUse; |
2747 | if (!match(V: Op, P: m_OneUse(SubPattern: m_Value(V&: OneUse)))) |
2748 | return nullptr; |
2749 | |
2750 | if (Instruction *R = hoistFNegAboveFMulFDiv(FNegOp: OneUse, FMFSource&: I)) |
2751 | return replaceInstUsesWith(I, V: R); |
2752 | |
2753 | // Try to eliminate fneg if at least 1 arm of the select is negated. |
2754 | Value *Cond; |
2755 | if (match(V: OneUse, P: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: X), R: m_Value(V&: Y)))) { |
2756 | // Unlike most transforms, this one is not safe to propagate nsz unless |
2757 | // it is present on the original select. We union the flags from the select |
2758 | // and fneg and then remove nsz if needed. |
2759 | auto propagateSelectFMF = [&](SelectInst *S, bool CommonOperand) { |
2760 | S->copyFastMathFlags(I: &I); |
2761 | if (auto *OldSel = dyn_cast<SelectInst>(Val: Op)) { |
2762 | FastMathFlags FMF = I.getFastMathFlags() | OldSel->getFastMathFlags(); |
2763 | S->setFastMathFlags(FMF); |
2764 | if (!OldSel->hasNoSignedZeros() && !CommonOperand && |
2765 | !isGuaranteedNotToBeUndefOrPoison(V: OldSel->getCondition())) |
2766 | S->setHasNoSignedZeros(false); |
2767 | } |
2768 | }; |
2769 | // -(Cond ? -P : Y) --> Cond ? P : -Y |
2770 | Value *P; |
2771 | if (match(V: X, P: m_FNeg(X: m_Value(V&: P)))) { |
2772 | Value *NegY = Builder.CreateFNegFMF(V: Y, FMFSource: &I, Name: Y->getName() + ".neg" ); |
2773 | SelectInst *NewSel = SelectInst::Create(C: Cond, S1: P, S2: NegY); |
2774 | propagateSelectFMF(NewSel, P == Y); |
2775 | return NewSel; |
2776 | } |
2777 | // -(Cond ? X : -P) --> Cond ? -X : P |
2778 | if (match(V: Y, P: m_FNeg(X: m_Value(V&: P)))) { |
2779 | Value *NegX = Builder.CreateFNegFMF(V: X, FMFSource: &I, Name: X->getName() + ".neg" ); |
2780 | SelectInst *NewSel = SelectInst::Create(C: Cond, S1: NegX, S2: P); |
2781 | propagateSelectFMF(NewSel, P == X); |
2782 | return NewSel; |
2783 | } |
2784 | } |
2785 | |
2786 | // fneg (copysign x, y) -> copysign x, (fneg y) |
2787 | if (match(V: OneUse, P: m_CopySign(Op0: m_Value(V&: X), Op1: m_Value(V&: Y)))) { |
2788 | // The source copysign has an additional value input, so we can't propagate |
2789 | // flags the copysign doesn't also have. |
2790 | FastMathFlags FMF = I.getFastMathFlags(); |
2791 | FMF &= cast<FPMathOperator>(Val: OneUse)->getFastMathFlags(); |
2792 | |
2793 | IRBuilder<>::FastMathFlagGuard FMFGuard(Builder); |
2794 | Builder.setFastMathFlags(FMF); |
2795 | |
2796 | Value *NegY = Builder.CreateFNeg(V: Y); |
2797 | Value *NewCopySign = Builder.CreateCopySign(LHS: X, RHS: NegY); |
2798 | return replaceInstUsesWith(I, V: NewCopySign); |
2799 | } |
2800 | |
2801 | return nullptr; |
2802 | } |
2803 | |
2804 | Instruction *InstCombinerImpl::visitFSub(BinaryOperator &I) { |
2805 | if (Value *V = simplifyFSubInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), |
2806 | FMF: I.getFastMathFlags(), |
2807 | Q: getSimplifyQuery().getWithInstruction(I: &I))) |
2808 | return replaceInstUsesWith(I, V); |
2809 | |
2810 | if (Instruction *X = foldVectorBinop(Inst&: I)) |
2811 | return X; |
2812 | |
2813 | if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I)) |
2814 | return Phi; |
2815 | |
2816 | // Subtraction from -0.0 is the canonical form of fneg. |
2817 | // fsub -0.0, X ==> fneg X |
2818 | // fsub nsz 0.0, X ==> fneg nsz X |
2819 | // |
2820 | // FIXME This matcher does not respect FTZ or DAZ yet: |
2821 | // fsub -0.0, Denorm ==> +-0 |
2822 | // fneg Denorm ==> -Denorm |
2823 | Value *Op; |
2824 | if (match(V: &I, P: m_FNeg(X: m_Value(V&: Op)))) |
2825 | return UnaryOperator::CreateFNegFMF(Op, FMFSource: &I); |
2826 | |
2827 | if (Instruction *X = foldFNegIntoConstant(I, DL)) |
2828 | return X; |
2829 | |
2830 | if (Instruction *R = foldFBinOpOfIntCasts(I)) |
2831 | return R; |
2832 | |
2833 | Value *X, *Y; |
2834 | Constant *C; |
2835 | |
2836 | Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1); |
2837 | // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X) |
2838 | // Canonicalize to fadd to make analysis easier. |
2839 | // This can also help codegen because fadd is commutative. |
2840 | // Note that if this fsub was really an fneg, the fadd with -0.0 will get |
2841 | // killed later. We still limit that particular transform with 'hasOneUse' |
2842 | // because an fneg is assumed better/cheaper than a generic fsub. |
2843 | if (I.hasNoSignedZeros() || |
2844 | cannotBeNegativeZero(V: Op0, Depth: 0, SQ: getSimplifyQuery().getWithInstruction(I: &I))) { |
2845 | if (match(V: Op1, P: m_OneUse(SubPattern: m_FSub(L: m_Value(V&: X), R: m_Value(V&: Y))))) { |
2846 | Value *NewSub = Builder.CreateFSubFMF(L: Y, R: X, FMFSource: &I); |
2847 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: NewSub, FMFSource: &I); |
2848 | } |
2849 | } |
2850 | |
2851 | // (-X) - Op1 --> -(X + Op1) |
2852 | if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Val: Op0) && |
2853 | match(V: Op0, P: m_OneUse(SubPattern: m_FNeg(X: m_Value(V&: X))))) { |
2854 | Value *FAdd = Builder.CreateFAddFMF(L: X, R: Op1, FMFSource: &I); |
2855 | return UnaryOperator::CreateFNegFMF(Op: FAdd, FMFSource: &I); |
2856 | } |
2857 | |
2858 | if (isa<Constant>(Val: Op0)) |
2859 | if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op1)) |
2860 | if (Instruction *NV = FoldOpIntoSelect(Op&: I, SI)) |
2861 | return NV; |
2862 | |
2863 | // X - C --> X + (-C) |
2864 | // But don't transform constant expressions because there's an inverse fold |
2865 | // for X + (-Y) --> X - Y. |
2866 | if (match(V: Op1, P: m_ImmConstant(C))) |
2867 | if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL)) |
2868 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: NegC, FMFSource: &I); |
2869 | |
2870 | // X - (-Y) --> X + Y |
2871 | if (match(V: Op1, P: m_FNeg(X: m_Value(V&: Y)))) |
2872 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: Y, FMFSource: &I); |
2873 | |
2874 | // Similar to above, but look through a cast of the negated value: |
2875 | // X - (fptrunc(-Y)) --> X + fptrunc(Y) |
2876 | Type *Ty = I.getType(); |
2877 | if (match(V: Op1, P: m_OneUse(SubPattern: m_FPTrunc(Op: m_FNeg(X: m_Value(V&: Y)))))) |
2878 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: Builder.CreateFPTrunc(V: Y, DestTy: Ty), FMFSource: &I); |
2879 | |
2880 | // X - (fpext(-Y)) --> X + fpext(Y) |
2881 | if (match(V: Op1, P: m_OneUse(SubPattern: m_FPExt(Op: m_FNeg(X: m_Value(V&: Y)))))) |
2882 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: Builder.CreateFPExt(V: Y, DestTy: Ty), FMFSource: &I); |
2883 | |
2884 | // Similar to above, but look through fmul/fdiv of the negated value: |
2885 | // Op0 - (-X * Y) --> Op0 + (X * Y) |
2886 | // Op0 - (Y * -X) --> Op0 + (X * Y) |
2887 | if (match(V: Op1, P: m_OneUse(SubPattern: m_c_FMul(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y))))) { |
2888 | Value *FMul = Builder.CreateFMulFMF(L: X, R: Y, FMFSource: &I); |
2889 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: FMul, FMFSource: &I); |
2890 | } |
2891 | // Op0 - (-X / Y) --> Op0 + (X / Y) |
2892 | // Op0 - (X / -Y) --> Op0 + (X / Y) |
2893 | if (match(V: Op1, P: m_OneUse(SubPattern: m_FDiv(L: m_FNeg(X: m_Value(V&: X)), R: m_Value(V&: Y)))) || |
2894 | match(V: Op1, P: m_OneUse(SubPattern: m_FDiv(L: m_Value(V&: X), R: m_FNeg(X: m_Value(V&: Y)))))) { |
2895 | Value *FDiv = Builder.CreateFDivFMF(L: X, R: Y, FMFSource: &I); |
2896 | return BinaryOperator::CreateFAddFMF(V1: Op0, V2: FDiv, FMFSource: &I); |
2897 | } |
2898 | |
2899 | // Handle special cases for FSub with selects feeding the operation |
2900 | if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS: Op0, RHS: Op1)) |
2901 | return replaceInstUsesWith(I, V); |
2902 | |
2903 | if (I.hasAllowReassoc() && I.hasNoSignedZeros()) { |
2904 | // (Y - X) - Y --> -X |
2905 | if (match(V: Op0, P: m_FSub(L: m_Specific(V: Op1), R: m_Value(V&: X)))) |
2906 | return UnaryOperator::CreateFNegFMF(Op: X, FMFSource: &I); |
2907 | |
2908 | // Y - (X + Y) --> -X |
2909 | // Y - (Y + X) --> -X |
2910 | if (match(V: Op1, P: m_c_FAdd(L: m_Specific(V: Op0), R: m_Value(V&: X)))) |
2911 | return UnaryOperator::CreateFNegFMF(Op: X, FMFSource: &I); |
2912 | |
2913 | // (X * C) - X --> X * (C - 1.0) |
2914 | if (match(V: Op0, P: m_FMul(L: m_Specific(V: Op1), R: m_Constant(C)))) { |
2915 | if (Constant *CSubOne = ConstantFoldBinaryOpOperands( |
2916 | Opcode: Instruction::FSub, LHS: C, RHS: ConstantFP::get(Ty, V: 1.0), DL)) |
2917 | return BinaryOperator::CreateFMulFMF(V1: Op1, V2: CSubOne, FMFSource: &I); |
2918 | } |
2919 | // X - (X * C) --> X * (1.0 - C) |
2920 | if (match(V: Op1, P: m_FMul(L: m_Specific(V: Op0), R: m_Constant(C)))) { |
2921 | if (Constant *OneSubC = ConstantFoldBinaryOpOperands( |
2922 | Opcode: Instruction::FSub, LHS: ConstantFP::get(Ty, V: 1.0), RHS: C, DL)) |
2923 | return BinaryOperator::CreateFMulFMF(V1: Op0, V2: OneSubC, FMFSource: &I); |
2924 | } |
2925 | |
2926 | // Reassociate fsub/fadd sequences to create more fadd instructions and |
2927 | // reduce dependency chains: |
2928 | // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1) |
2929 | Value *Z; |
2930 | if (match(V: Op0, P: m_OneUse(SubPattern: m_c_FAdd(L: m_OneUse(SubPattern: m_FSub(L: m_Value(V&: X), R: m_Value(V&: Y))), |
2931 | R: m_Value(V&: Z))))) { |
2932 | Value *XZ = Builder.CreateFAddFMF(L: X, R: Z, FMFSource: &I); |
2933 | Value *YW = Builder.CreateFAddFMF(L: Y, R: Op1, FMFSource: &I); |
2934 | return BinaryOperator::CreateFSubFMF(V1: XZ, V2: YW, FMFSource: &I); |
2935 | } |
2936 | |
2937 | auto m_FaddRdx = [](Value *&Sum, Value *&Vec) { |
2938 | return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum), |
2939 | m_Value(Vec))); |
2940 | }; |
2941 | Value *A0, *A1, *V0, *V1; |
2942 | if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) && |
2943 | V0->getType() == V1->getType()) { |
2944 | // Difference of sums is sum of differences: |
2945 | // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A1 |
2946 | Value *Sub = Builder.CreateFSubFMF(L: V0, R: V1, FMFSource: &I); |
2947 | Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd, |
2948 | {Sub->getType()}, {A0, Sub}, &I); |
2949 | return BinaryOperator::CreateFSubFMF(V1: Rdx, V2: A1, FMFSource: &I); |
2950 | } |
2951 | |
2952 | if (Instruction *F = factorizeFAddFSub(I, Builder)) |
2953 | return F; |
2954 | |
2955 | // TODO: This performs reassociative folds for FP ops. Some fraction of the |
2956 | // functionality has been subsumed by simple pattern matching here and in |
2957 | // InstSimplify. We should let a dedicated reassociation pass handle more |
2958 | // complex pattern matching and remove this from InstCombine. |
2959 | if (Value *V = FAddCombine(Builder).simplify(I: &I)) |
2960 | return replaceInstUsesWith(I, V); |
2961 | |
2962 | // (X - Y) - Op1 --> X - (Y + Op1) |
2963 | if (match(V: Op0, P: m_OneUse(SubPattern: m_FSub(L: m_Value(V&: X), R: m_Value(V&: Y))))) { |
2964 | Value *FAdd = Builder.CreateFAddFMF(L: Y, R: Op1, FMFSource: &I); |
2965 | return BinaryOperator::CreateFSubFMF(V1: X, V2: FAdd, FMFSource: &I); |
2966 | } |
2967 | } |
2968 | |
2969 | return nullptr; |
2970 | } |
2971 | |