blob: 7204bf51768112333464971e453aea034e9d2996 [file] [log] [blame]
Eugene Zelenkoffec81c2015-11-04 22:32:32 +00001//===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
Chris Lattner82aa8882010-01-05 07:18:46 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the visit functions for add, fadd, sub, and fsub.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
Craig Topper58713212013-07-15 04:27:47 +000015#include "llvm/ADT/STLExtras.h"
Chris Lattner82aa8882010-01-05 07:18:46 +000016#include "llvm/Analysis/InstructionSimplify.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000017#include "llvm/IR/DataLayout.h"
Chandler Carruth03eb0de2014-03-04 10:40:04 +000018#include "llvm/IR/GetElementPtrTypeIterator.h"
Chandler Carruth820a9082014-03-04 11:08:18 +000019#include "llvm/IR/PatternMatch.h"
Craig Topperb45eabc2017-04-26 16:39:58 +000020#include "llvm/Support/KnownBits.h"
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000021
Chris Lattner82aa8882010-01-05 07:18:46 +000022using namespace llvm;
23using namespace PatternMatch;
24
Chandler Carruth964daaa2014-04-22 02:55:47 +000025#define DEBUG_TYPE "instcombine"
26
Shuxin Yang37a1efe2012-12-18 23:10:12 +000027namespace {
28
29 /// Class representing coefficient of floating-point addend.
30 /// This class needs to be highly efficient, which is especially true for
31 /// the constructor. As of I write this comment, the cost of the default
Jim Grosbachbdbd7342013-04-05 21:20:12 +000032 /// constructor is merely 4-byte-store-zero (Assuming compiler is able to
Shuxin Yang37a1efe2012-12-18 23:10:12 +000033 /// perform write-merging).
Jim Grosbachbdbd7342013-04-05 21:20:12 +000034 ///
Shuxin Yang37a1efe2012-12-18 23:10:12 +000035 class FAddendCoef {
36 public:
Suyog Sardade409fd2014-07-17 06:09:34 +000037 // The constructor has to initialize a APFloat, which is unnecessary for
Shuxin Yang37a1efe2012-12-18 23:10:12 +000038 // most addends which have coefficient either 1 or -1. So, the constructor
39 // is expensive. In order to avoid the cost of the constructor, we should
40 // reuse some instances whenever possible. The pre-created instances
41 // FAddCombine::Add[0-5] embodies this idea.
42 //
43 FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {}
44 ~FAddendCoef();
Jim Grosbachbdbd7342013-04-05 21:20:12 +000045
Shuxin Yang37a1efe2012-12-18 23:10:12 +000046 void set(short C) {
47 assert(!insaneIntVal(C) && "Insane coefficient");
48 IsFp = false; IntVal = C;
49 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +000050
Shuxin Yang37a1efe2012-12-18 23:10:12 +000051 void set(const APFloat& C);
Shuxin Yang389ed4b2013-03-25 20:43:41 +000052
Shuxin Yang37a1efe2012-12-18 23:10:12 +000053 void negate();
Jim Grosbachbdbd7342013-04-05 21:20:12 +000054
Shuxin Yang37a1efe2012-12-18 23:10:12 +000055 bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }
56 Value *getValue(Type *) const;
Jim Grosbachbdbd7342013-04-05 21:20:12 +000057
Shuxin Yang37a1efe2012-12-18 23:10:12 +000058 // If possible, don't define operator+/operator- etc because these
59 // operators inevitably call FAddendCoef's constructor which is not cheap.
60 void operator=(const FAddendCoef &A);
61 void operator+=(const FAddendCoef &A);
Shuxin Yang37a1efe2012-12-18 23:10:12 +000062 void operator*=(const FAddendCoef &S);
Jim Grosbachbdbd7342013-04-05 21:20:12 +000063
Shuxin Yang37a1efe2012-12-18 23:10:12 +000064 bool isOne() const { return isInt() && IntVal == 1; }
65 bool isTwo() const { return isInt() && IntVal == 2; }
66 bool isMinusOne() const { return isInt() && IntVal == -1; }
67 bool isMinusTwo() const { return isInt() && IntVal == -2; }
Jim Grosbachbdbd7342013-04-05 21:20:12 +000068
Shuxin Yang37a1efe2012-12-18 23:10:12 +000069 private:
70 bool insaneIntVal(int V) { return V > 4 || V < -4; }
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000071 APFloat *getFpValPtr()
Shuxin Yang5b841c42012-12-19 01:10:17 +000072 { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); }
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000073 const APFloat *getFpValPtr() const
David Greene530430b2013-01-14 21:04:40 +000074 { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); }
Shuxin Yang37a1efe2012-12-18 23:10:12 +000075
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000076 const APFloat &getFpVal() const {
Shuxin Yang37a1efe2012-12-18 23:10:12 +000077 assert(IsFp && BufHasFpVal && "Incorret state");
David Greene530430b2013-01-14 21:04:40 +000078 return *getFpValPtr();
Shuxin Yang37a1efe2012-12-18 23:10:12 +000079 }
80
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000081 APFloat &getFpVal() {
Jim Grosbachbdbd7342013-04-05 21:20:12 +000082 assert(IsFp && BufHasFpVal && "Incorret state");
83 return *getFpValPtr();
84 }
85
Shuxin Yang37a1efe2012-12-18 23:10:12 +000086 bool isInt() const { return !IsFp; }
87
Shuxin Yang389ed4b2013-03-25 20:43:41 +000088 // If the coefficient is represented by an integer, promote it to a
Jim Grosbachbdbd7342013-04-05 21:20:12 +000089 // floating point.
Shuxin Yang389ed4b2013-03-25 20:43:41 +000090 void convertToFpType(const fltSemantics &Sem);
91
92 // Construct an APFloat from a signed integer.
93 // TODO: We should get rid of this function when APFloat can be constructed
Jim Grosbachbdbd7342013-04-05 21:20:12 +000094 // from an *SIGNED* integer.
Shuxin Yang389ed4b2013-03-25 20:43:41 +000095 APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);
Shuxin Yang5b841c42012-12-19 01:10:17 +000096
Eugene Zelenkoffec81c2015-11-04 22:32:32 +000097 private:
Shuxin Yang37a1efe2012-12-18 23:10:12 +000098 bool IsFp;
Jim Grosbachbdbd7342013-04-05 21:20:12 +000099
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000100 // True iff FpValBuf contains an instance of APFloat.
101 bool BufHasFpVal;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000102
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000103 // The integer coefficient of an individual addend is either 1 or -1,
104 // and we try to simplify at most 4 addends from neighboring at most
105 // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt
106 // is overkill of this end.
107 short IntVal;
Shuxin Yang5b841c42012-12-19 01:10:17 +0000108
109 AlignedCharArrayUnion<APFloat> FpValBuf;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000110 };
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000111
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000112 /// FAddend is used to represent floating-point addend. An addend is
113 /// represented as <C, V>, where the V is a symbolic value, and C is a
114 /// constant coefficient. A constant addend is represented as <C, 0>.
115 ///
116 class FAddend {
117 public:
Eugene Zelenkoffec81c2015-11-04 22:32:32 +0000118 FAddend() : Val(nullptr) {}
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000119
Eugene Zelenkoffec81c2015-11-04 22:32:32 +0000120 Value *getSymVal() const { return Val; }
121 const FAddendCoef &getCoef() const { return Coeff; }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000122
Craig Topperf40110f2014-04-25 05:29:35 +0000123 bool isConstant() const { return Val == nullptr; }
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000124 bool isZero() const { return Coeff.isZero(); }
125
Richard Trieu7a083812016-02-18 22:09:30 +0000126 void set(short Coefficient, Value *V) {
127 Coeff.set(Coefficient);
128 Val = V;
129 }
130 void set(const APFloat &Coefficient, Value *V) {
131 Coeff.set(Coefficient);
132 Val = V;
133 }
134 void set(const ConstantFP *Coefficient, Value *V) {
135 Coeff.set(Coefficient->getValueAPF());
136 Val = V;
137 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000138
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000139 void negate() { Coeff.negate(); }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000140
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000141 /// Drill down the U-D chain one step to find the definition of V, and
142 /// try to break the definition into one or two addends.
143 static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000144
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000145 /// Similar to FAddend::drillDownOneStep() except that the value being
146 /// splitted is the addend itself.
147 unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000148
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000149 void operator+=(const FAddend &T) {
150 assert((Val == T.Val) && "Symbolic-values disagree");
151 Coeff += T.Coeff;
152 }
153
154 private:
155 void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000156
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000157 // This addend has the value of "Coeff * Val".
158 Value *Val;
159 FAddendCoef Coeff;
160 };
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000161
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000162 /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
163 /// with its neighboring at most two instructions.
164 ///
165 class FAddCombine {
166 public:
Craig Topperf40110f2014-04-25 05:29:35 +0000167 FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(nullptr) {}
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000168 Value *simplify(Instruction *FAdd);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000169
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000170 private:
171 typedef SmallVector<const FAddend*, 4> AddendVect;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000172
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000173 Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
Shuxin Yang2eca6022013-03-14 18:08:26 +0000174
175 Value *performFactorization(Instruction *I);
176
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000177 /// Convert given addend to a Value
178 Value *createAddendVal(const FAddend &A, bool& NeedNeg);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000179
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000180 /// Return the number of instructions needed to emit the N-ary addition.
181 unsigned calcInstrNumber(const AddendVect& Vect);
182 Value *createFSub(Value *Opnd0, Value *Opnd1);
183 Value *createFAdd(Value *Opnd0, Value *Opnd1);
184 Value *createFMul(Value *Opnd0, Value *Opnd1);
Shuxin Yang2eca6022013-03-14 18:08:26 +0000185 Value *createFDiv(Value *Opnd0, Value *Opnd1);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000186 Value *createFNeg(Value *V);
187 Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
Owen Anderson1664dc82014-01-20 07:44:53 +0000188 void createInstPostProc(Instruction *NewInst, bool NoNumber = false);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000189
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000190 InstCombiner::BuilderTy *Builder;
191 Instruction *Instr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000192
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000193 // Debugging stuff are clustered here.
194 #ifndef NDEBUG
195 unsigned CreateInstrNum;
196 void initCreateInstNum() { CreateInstrNum = 0; }
197 void incCreateInstNum() { CreateInstrNum++; }
198 #else
199 void initCreateInstNum() {}
200 void incCreateInstNum() {}
201 #endif
202 };
Eugene Zelenkoffec81c2015-11-04 22:32:32 +0000203
204} // anonymous namespace
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000205
206//===----------------------------------------------------------------------===//
207//
208// Implementation of
209// {FAddendCoef, FAddend, FAddition, FAddCombine}.
210//
211//===----------------------------------------------------------------------===//
212FAddendCoef::~FAddendCoef() {
213 if (BufHasFpVal)
214 getFpValPtr()->~APFloat();
215}
216
217void FAddendCoef::set(const APFloat& C) {
218 APFloat *P = getFpValPtr();
219
220 if (isInt()) {
221 // As the buffer is meanless byte stream, we cannot call
222 // APFloat::operator=().
223 new(P) APFloat(C);
224 } else
225 *P = C;
226
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000227 IsFp = BufHasFpVal = true;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000228}
229
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000230void FAddendCoef::convertToFpType(const fltSemantics &Sem) {
231 if (!isInt())
232 return;
233
234 APFloat *P = getFpValPtr();
235 if (IntVal > 0)
236 new(P) APFloat(Sem, IntVal);
237 else {
238 new(P) APFloat(Sem, 0 - IntVal);
239 P->changeSign();
240 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000241 IsFp = BufHasFpVal = true;
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000242}
243
244APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {
245 if (Val >= 0)
246 return APFloat(Sem, Val);
247
248 APFloat T(Sem, 0 - Val);
249 T.changeSign();
250
251 return T;
252}
253
254void FAddendCoef::operator=(const FAddendCoef &That) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000255 if (That.isInt())
256 set(That.IntVal);
257 else
258 set(That.getFpVal());
259}
260
261void FAddendCoef::operator+=(const FAddendCoef &That) {
262 enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
263 if (isInt() == That.isInt()) {
264 if (isInt())
265 IntVal += That.IntVal;
266 else
267 getFpVal().add(That.getFpVal(), RndMode);
268 return;
269 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000270
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000271 if (isInt()) {
272 const APFloat &T = That.getFpVal();
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000273 convertToFpType(T.getSemantics());
274 getFpVal().add(T, RndMode);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000275 return;
276 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000277
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000278 APFloat &T = getFpVal();
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000279 T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000280}
281
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000282void FAddendCoef::operator*=(const FAddendCoef &That) {
283 if (That.isOne())
284 return;
285
286 if (That.isMinusOne()) {
287 negate();
288 return;
289 }
290
291 if (isInt() && That.isInt()) {
292 int Res = IntVal * (int)That.IntVal;
293 assert(!insaneIntVal(Res) && "Insane int value");
294 IntVal = Res;
295 return;
296 }
297
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000298 const fltSemantics &Semantic =
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000299 isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
300
301 if (isInt())
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000302 convertToFpType(Semantic);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000303 APFloat &F0 = getFpVal();
304
305 if (That.isInt())
Shuxin Yang389ed4b2013-03-25 20:43:41 +0000306 F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),
307 APFloat::rmNearestTiesToEven);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000308 else
309 F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000310}
311
312void FAddendCoef::negate() {
313 if (isInt())
314 IntVal = 0 - IntVal;
315 else
316 getFpVal().changeSign();
317}
318
319Value *FAddendCoef::getValue(Type *Ty) const {
320 return isInt() ?
321 ConstantFP::get(Ty, float(IntVal)) :
322 ConstantFP::get(Ty->getContext(), getFpVal());
323}
324
325// The definition of <Val> Addends
326// =========================================
327// A + B <1, A>, <1,B>
328// A - B <1, A>, <1,B>
329// 0 - B <-1, B>
330// C * A, <C, A>
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000331// A + C <1, A> <C, NULL>
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000332// 0 +/- 0 <0, NULL> (corner case)
333//
334// Legend: A and B are not constant, C is constant
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000335//
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000336unsigned FAddend::drillValueDownOneStep
337 (Value *Val, FAddend &Addend0, FAddend &Addend1) {
Craig Topperf40110f2014-04-25 05:29:35 +0000338 Instruction *I = nullptr;
339 if (!Val || !(I = dyn_cast<Instruction>(Val)))
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000340 return 0;
341
342 unsigned Opcode = I->getOpcode();
343
344 if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {
345 ConstantFP *C0, *C1;
346 Value *Opnd0 = I->getOperand(0);
347 Value *Opnd1 = I->getOperand(1);
348 if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())
Craig Topperf40110f2014-04-25 05:29:35 +0000349 Opnd0 = nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000350
351 if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())
Craig Topperf40110f2014-04-25 05:29:35 +0000352 Opnd1 = nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000353
354 if (Opnd0) {
355 if (!C0)
356 Addend0.set(1, Opnd0);
357 else
Craig Topperf40110f2014-04-25 05:29:35 +0000358 Addend0.set(C0, nullptr);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000359 }
360
361 if (Opnd1) {
362 FAddend &Addend = Opnd0 ? Addend1 : Addend0;
363 if (!C1)
364 Addend.set(1, Opnd1);
365 else
Craig Topperf40110f2014-04-25 05:29:35 +0000366 Addend.set(C1, nullptr);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000367 if (Opcode == Instruction::FSub)
368 Addend.negate();
369 }
370
371 if (Opnd0 || Opnd1)
372 return Opnd0 && Opnd1 ? 2 : 1;
373
374 // Both operands are zero. Weird!
Craig Topperf40110f2014-04-25 05:29:35 +0000375 Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000376 return 1;
377 }
378
379 if (I->getOpcode() == Instruction::FMul) {
380 Value *V0 = I->getOperand(0);
381 Value *V1 = I->getOperand(1);
382 if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
383 Addend0.set(C, V1);
384 return 1;
385 }
386
387 if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
388 Addend0.set(C, V0);
389 return 1;
390 }
391 }
392
393 return 0;
394}
395
396// Try to break *this* addend into two addends. e.g. Suppose this addend is
397// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
398// i.e. <2.3, X> and <2.3, Y>.
399//
400unsigned FAddend::drillAddendDownOneStep
401 (FAddend &Addend0, FAddend &Addend1) const {
402 if (isConstant())
403 return 0;
404
405 unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000406 if (!BreakNum || Coeff.isOne())
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000407 return BreakNum;
408
409 Addend0.Scale(Coeff);
410
411 if (BreakNum == 2)
412 Addend1.Scale(Coeff);
413
414 return BreakNum;
415}
416
Shuxin Yang2eca6022013-03-14 18:08:26 +0000417// Try to perform following optimization on the input instruction I. Return the
418// simplified expression if was successful; otherwise, return 0.
419//
420// Instruction "I" is Simplified into
421// -------------------------------------------------------
422// (x * y) +/- (x * z) x * (y +/- z)
423// (y / x) +/- (z / x) (y +/- z) / x
424//
425Value *FAddCombine::performFactorization(Instruction *I) {
426 assert((I->getOpcode() == Instruction::FAdd ||
427 I->getOpcode() == Instruction::FSub) && "Expect add/sub");
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000428
Shuxin Yang2eca6022013-03-14 18:08:26 +0000429 Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0));
430 Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1));
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000431
Shuxin Yang2eca6022013-03-14 18:08:26 +0000432 if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode())
Craig Topperf40110f2014-04-25 05:29:35 +0000433 return nullptr;
Shuxin Yang2eca6022013-03-14 18:08:26 +0000434
435 bool isMpy = false;
436 if (I0->getOpcode() == Instruction::FMul)
437 isMpy = true;
438 else if (I0->getOpcode() != Instruction::FDiv)
Craig Topperf40110f2014-04-25 05:29:35 +0000439 return nullptr;
Shuxin Yang2eca6022013-03-14 18:08:26 +0000440
441 Value *Opnd0_0 = I0->getOperand(0);
442 Value *Opnd0_1 = I0->getOperand(1);
443 Value *Opnd1_0 = I1->getOperand(0);
444 Value *Opnd1_1 = I1->getOperand(1);
445
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000446 // Input Instr I Factor AddSub0 AddSub1
Shuxin Yang2eca6022013-03-14 18:08:26 +0000447 // ----------------------------------------------
448 // (x*y) +/- (x*z) x y z
449 // (y/x) +/- (z/x) x y z
450 //
Craig Topperf40110f2014-04-25 05:29:35 +0000451 Value *Factor = nullptr;
452 Value *AddSub0 = nullptr, *AddSub1 = nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000453
Shuxin Yang2eca6022013-03-14 18:08:26 +0000454 if (isMpy) {
455 if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1)
456 Factor = Opnd0_0;
457 else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1)
458 Factor = Opnd0_1;
459
460 if (Factor) {
461 AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0;
462 AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0;
463 }
464 } else if (Opnd0_1 == Opnd1_1) {
465 Factor = Opnd0_1;
466 AddSub0 = Opnd0_0;
467 AddSub1 = Opnd1_0;
468 }
469
470 if (!Factor)
Craig Topperf40110f2014-04-25 05:29:35 +0000471 return nullptr;
Shuxin Yang2eca6022013-03-14 18:08:26 +0000472
Owen Anderson1664dc82014-01-20 07:44:53 +0000473 FastMathFlags Flags;
474 Flags.setUnsafeAlgebra();
475 if (I0) Flags &= I->getFastMathFlags();
476 if (I1) Flags &= I->getFastMathFlags();
477
Shuxin Yang2eca6022013-03-14 18:08:26 +0000478 // Create expression "NewAddSub = AddSub0 +/- AddsSub1"
479 Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ?
480 createFAdd(AddSub0, AddSub1) :
481 createFSub(AddSub0, AddSub1);
482 if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) {
483 const APFloat &F = CFP->getValueAPF();
Michael Gottesmanc2af8d62013-06-26 23:17:31 +0000484 if (!F.isNormal())
Craig Topperf40110f2014-04-25 05:29:35 +0000485 return nullptr;
Owen Anderson1664dc82014-01-20 07:44:53 +0000486 } else if (Instruction *II = dyn_cast<Instruction>(NewAddSub))
487 II->setFastMathFlags(Flags);
488
489 if (isMpy) {
490 Value *RI = createFMul(Factor, NewAddSub);
491 if (Instruction *II = dyn_cast<Instruction>(RI))
492 II->setFastMathFlags(Flags);
493 return RI;
Shuxin Yang2eca6022013-03-14 18:08:26 +0000494 }
495
Owen Anderson1664dc82014-01-20 07:44:53 +0000496 Value *RI = createFDiv(NewAddSub, Factor);
497 if (Instruction *II = dyn_cast<Instruction>(RI))
498 II->setFastMathFlags(Flags);
499 return RI;
Shuxin Yang2eca6022013-03-14 18:08:26 +0000500}
501
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000502Value *FAddCombine::simplify(Instruction *I) {
503 assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode");
504
505 // Currently we are not able to handle vector type.
506 if (I->getType()->isVectorTy())
Craig Topperf40110f2014-04-25 05:29:35 +0000507 return nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000508
509 assert((I->getOpcode() == Instruction::FAdd ||
510 I->getOpcode() == Instruction::FSub) && "Expect add/sub");
511
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000512 // Save the instruction before calling other member-functions.
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000513 Instr = I;
514
515 FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
516
517 unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
518
519 // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.
520 unsigned Opnd0_ExpNum = 0;
521 unsigned Opnd1_ExpNum = 0;
522
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000523 if (!Opnd0.isConstant())
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000524 Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
525
526 // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.
527 if (OpndNum == 2 && !Opnd1.isConstant())
528 Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
529
530 // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1
531 if (Opnd0_ExpNum && Opnd1_ExpNum) {
532 AddendVect AllOpnds;
533 AllOpnds.push_back(&Opnd0_0);
534 AllOpnds.push_back(&Opnd1_0);
535 if (Opnd0_ExpNum == 2)
536 AllOpnds.push_back(&Opnd0_1);
537 if (Opnd1_ExpNum == 2)
538 AllOpnds.push_back(&Opnd1_1);
539
540 // Compute instruction quota. We should save at least one instruction.
541 unsigned InstQuota = 0;
542
543 Value *V0 = I->getOperand(0);
544 Value *V1 = I->getOperand(1);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000545 InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000546 (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;
547
548 if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
549 return R;
550 }
551
552 if (OpndNum != 2) {
553 // The input instruction is : "I=0.0 +/- V". If the "V" were able to be
554 // splitted into two addends, say "V = X - Y", the instruction would have
555 // been optimized into "I = Y - X" in the previous steps.
556 //
557 const FAddendCoef &CE = Opnd0.getCoef();
Craig Topperf40110f2014-04-25 05:29:35 +0000558 return CE.isOne() ? Opnd0.getSymVal() : nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000559 }
560
561 // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]
562 if (Opnd1_ExpNum) {
563 AddendVect AllOpnds;
564 AllOpnds.push_back(&Opnd0);
565 AllOpnds.push_back(&Opnd1_0);
566 if (Opnd1_ExpNum == 2)
567 AllOpnds.push_back(&Opnd1_1);
568
569 if (Value *R = simplifyFAdd(AllOpnds, 1))
570 return R;
571 }
572
573 // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]
574 if (Opnd0_ExpNum) {
575 AddendVect AllOpnds;
576 AllOpnds.push_back(&Opnd1);
577 AllOpnds.push_back(&Opnd0_0);
578 if (Opnd0_ExpNum == 2)
579 AllOpnds.push_back(&Opnd0_1);
580
581 if (Value *R = simplifyFAdd(AllOpnds, 1))
582 return R;
583 }
584
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000585 // step 6: Try factorization as the last resort,
Shuxin Yang2eca6022013-03-14 18:08:26 +0000586 return performFactorization(I);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000587}
588
589Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000590 unsigned AddendNum = Addends.size();
591 assert(AddendNum <= 4 && "Too many addends");
592
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000593 // For saving intermediate results;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000594 unsigned NextTmpIdx = 0;
595 FAddend TmpResult[3];
596
597 // Points to the constant addend of the resulting simplified expression.
598 // If the resulting expr has constant-addend, this constant-addend is
599 // desirable to reside at the top of the resulting expression tree. Placing
600 // constant close to supper-expr(s) will potentially reveal some optimization
601 // opportunities in super-expr(s).
602 //
Craig Topperf40110f2014-04-25 05:29:35 +0000603 const FAddend *ConstAdd = nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000604
605 // Simplified addends are placed <SimpVect>.
606 AddendVect SimpVect;
607
608 // The outer loop works on one symbolic-value at a time. Suppose the input
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000609 // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000610 // The symbolic-values will be processed in this order: x, y, z.
611 //
612 for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
613
614 const FAddend *ThisAddend = Addends[SymIdx];
615 if (!ThisAddend) {
616 // This addend was processed before.
617 continue;
618 }
619
620 Value *Val = ThisAddend->getSymVal();
621 unsigned StartIdx = SimpVect.size();
622 SimpVect.push_back(ThisAddend);
623
624 // The inner loop collects addends sharing same symbolic-value, and these
625 // addends will be later on folded into a single addend. Following above
626 // example, if the symbolic value "y" is being processed, the inner loop
627 // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will
628 // be later on folded into "<b1+b2, y>".
629 //
630 for (unsigned SameSymIdx = SymIdx + 1;
631 SameSymIdx < AddendNum; SameSymIdx++) {
632 const FAddend *T = Addends[SameSymIdx];
633 if (T && T->getSymVal() == Val) {
634 // Set null such that next iteration of the outer loop will not process
635 // this addend again.
Craig Topperf40110f2014-04-25 05:29:35 +0000636 Addends[SameSymIdx] = nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000637 SimpVect.push_back(T);
638 }
639 }
640
641 // If multiple addends share same symbolic value, fold them together.
642 if (StartIdx + 1 != SimpVect.size()) {
643 FAddend &R = TmpResult[NextTmpIdx ++];
644 R = *SimpVect[StartIdx];
645 for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
646 R += *SimpVect[Idx];
647
648 // Pop all addends being folded and push the resulting folded addend.
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000649 SimpVect.resize(StartIdx);
Craig Topperf40110f2014-04-25 05:29:35 +0000650 if (Val) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000651 if (!R.isZero()) {
652 SimpVect.push_back(&R);
653 }
654 } else {
655 // Don't push constant addend at this time. It will be the last element
656 // of <SimpVect>.
657 ConstAdd = &R;
658 }
659 }
660 }
661
Craig Topper58713212013-07-15 04:27:47 +0000662 assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) &&
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000663 "out-of-bound access");
664
665 if (ConstAdd)
666 SimpVect.push_back(ConstAdd);
667
668 Value *Result;
669 if (!SimpVect.empty())
670 Result = createNaryFAdd(SimpVect, InstrQuota);
671 else {
672 // The addition is folded to 0.0.
673 Result = ConstantFP::get(Instr->getType(), 0.0);
674 }
675
676 return Result;
677}
678
679Value *FAddCombine::createNaryFAdd
680 (const AddendVect &Opnds, unsigned InstrQuota) {
681 assert(!Opnds.empty() && "Expect at least one addend");
682
683 // Step 1: Check if the # of instructions needed exceeds the quota.
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000684 //
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000685 unsigned InstrNeeded = calcInstrNumber(Opnds);
686 if (InstrNeeded > InstrQuota)
Craig Topperf40110f2014-04-25 05:29:35 +0000687 return nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000688
689 initCreateInstNum();
690
691 // step 2: Emit the N-ary addition.
692 // Note that at most three instructions are involved in Fadd-InstCombine: the
693 // addition in question, and at most two neighboring instructions.
694 // The resulting optimized addition should have at least one less instruction
695 // than the original addition expression tree. This implies that the resulting
696 // N-ary addition has at most two instructions, and we don't need to worry
697 // about tree-height when constructing the N-ary addition.
698
Craig Topperf40110f2014-04-25 05:29:35 +0000699 Value *LastVal = nullptr;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000700 bool LastValNeedNeg = false;
701
702 // Iterate the addends, creating fadd/fsub using adjacent two addends.
Benjamin Kramer135f7352016-06-26 12:28:59 +0000703 for (const FAddend *Opnd : Opnds) {
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000704 bool NeedNeg;
Benjamin Kramer135f7352016-06-26 12:28:59 +0000705 Value *V = createAddendVal(*Opnd, NeedNeg);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000706 if (!LastVal) {
707 LastVal = V;
708 LastValNeedNeg = NeedNeg;
709 continue;
710 }
711
712 if (LastValNeedNeg == NeedNeg) {
713 LastVal = createFAdd(LastVal, V);
714 continue;
715 }
716
717 if (LastValNeedNeg)
718 LastVal = createFSub(V, LastVal);
719 else
720 LastVal = createFSub(LastVal, V);
721
722 LastValNeedNeg = false;
723 }
724
725 if (LastValNeedNeg) {
726 LastVal = createFNeg(LastVal);
727 }
728
729 #ifndef NDEBUG
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000730 assert(CreateInstrNum == InstrNeeded &&
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000731 "Inconsistent in instruction numbers");
732 #endif
733
734 return LastVal;
735}
736
Sanjay Patelc242dbb2014-12-18 21:11:09 +0000737Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000738 Value *V = Builder->CreateFSub(Opnd0, Opnd1);
Shuxin Yang2eca6022013-03-14 18:08:26 +0000739 if (Instruction *I = dyn_cast<Instruction>(V))
740 createInstPostProc(I);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000741 return V;
742}
743
744Value *FAddCombine::createFNeg(Value *V) {
Sanjay Patelea3c8022014-12-19 16:44:08 +0000745 Value *Zero = cast<Value>(ConstantFP::getZeroValueForNegation(V->getType()));
Owen Anderson1664dc82014-01-20 07:44:53 +0000746 Value *NewV = createFSub(Zero, V);
747 if (Instruction *I = dyn_cast<Instruction>(NewV))
748 createInstPostProc(I, true); // fneg's don't receive instruction numbers.
749 return NewV;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000750}
751
Sanjay Patelc242dbb2014-12-18 21:11:09 +0000752Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000753 Value *V = Builder->CreateFAdd(Opnd0, Opnd1);
Shuxin Yang2eca6022013-03-14 18:08:26 +0000754 if (Instruction *I = dyn_cast<Instruction>(V))
755 createInstPostProc(I);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000756 return V;
757}
758
759Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
760 Value *V = Builder->CreateFMul(Opnd0, Opnd1);
Shuxin Yang2eca6022013-03-14 18:08:26 +0000761 if (Instruction *I = dyn_cast<Instruction>(V))
762 createInstPostProc(I);
763 return V;
764}
765
766Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) {
767 Value *V = Builder->CreateFDiv(Opnd0, Opnd1);
768 if (Instruction *I = dyn_cast<Instruction>(V))
769 createInstPostProc(I);
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000770 return V;
771}
772
Sanjay Patelc242dbb2014-12-18 21:11:09 +0000773void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000774 NewInstr->setDebugLoc(Instr->getDebugLoc());
775
776 // Keep track of the number of instruction created.
Owen Anderson1664dc82014-01-20 07:44:53 +0000777 if (!NoNumber)
778 incCreateInstNum();
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000779
780 // Propagate fast-math flags
781 NewInstr->setFastMathFlags(Instr->getFastMathFlags());
782}
783
784// Return the number of instruction needed to emit the N-ary addition.
785// NOTE: Keep this function in sync with createAddendVal().
786unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
787 unsigned OpndNum = Opnds.size();
788 unsigned InstrNeeded = OpndNum - 1;
789
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000790 // The number of addends in the form of "(-1)*x".
791 unsigned NegOpndNum = 0;
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000792
793 // Adjust the number of instructions needed to emit the N-ary add.
Benjamin Kramer135f7352016-06-26 12:28:59 +0000794 for (const FAddend *Opnd : Opnds) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000795 if (Opnd->isConstant())
796 continue;
797
Matt Arsenault02907f32017-04-24 17:24:37 +0000798 // The constant check above is really for a few special constant
799 // coefficients.
800 if (isa<UndefValue>(Opnd->getSymVal()))
801 continue;
802
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000803 const FAddendCoef &CE = Opnd->getCoef();
804 if (CE.isMinusOne() || CE.isMinusTwo())
805 NegOpndNum++;
806
807 // Let the addend be "c * x". If "c == +/-1", the value of the addend
808 // is immediately available; otherwise, it needs exactly one instruction
809 // to evaluate the value.
810 if (!CE.isMinusOne() && !CE.isOne())
811 InstrNeeded++;
812 }
813 if (NegOpndNum == OpndNum)
814 InstrNeeded++;
815 return InstrNeeded;
816}
817
818// Input Addend Value NeedNeg(output)
819// ================================================================
820// Constant C C false
821// <+/-1, V> V coefficient is -1
822// <2/-2, V> "fadd V, V" coefficient is -2
823// <C, V> "fmul V, C" false
824//
825// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
Sanjay Patelc242dbb2014-12-18 21:11:09 +0000826Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
Shuxin Yang37a1efe2012-12-18 23:10:12 +0000827 const FAddendCoef &Coeff = Opnd.getCoef();
828
829 if (Opnd.isConstant()) {
830 NeedNeg = false;
831 return Coeff.getValue(Instr->getType());
832 }
833
834 Value *OpndVal = Opnd.getSymVal();
835
836 if (Coeff.isMinusOne() || Coeff.isOne()) {
837 NeedNeg = Coeff.isMinusOne();
838 return OpndVal;
839 }
840
841 if (Coeff.isTwo() || Coeff.isMinusTwo()) {
842 NeedNeg = Coeff.isMinusTwo();
843 return createFAdd(OpndVal, OpndVal);
844 }
845
846 NeedNeg = false;
847 return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
848}
849
David Majnemer57d5bc82014-08-19 23:36:30 +0000850/// \brief Return true if we can prove that:
851/// (sub LHS, RHS) === (sub nsw LHS, RHS)
852/// This basically requires proving that the add in the original type would not
853/// overflow to change the sign bit or have a carry out.
854/// TODO: Handle this for Vectors.
Craig Topper2b1fc322017-05-22 06:25:31 +0000855bool InstCombiner::willNotOverflowSignedSub(const Value *LHS,
856 const Value *RHS,
857 const Instruction &CxtI) const {
David Majnemer57d5bc82014-08-19 23:36:30 +0000858 // If LHS and RHS each have at least two sign bits, the subtraction
859 // cannot overflow.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000860 if (ComputeNumSignBits(LHS, 0, &CxtI) > 1 &&
861 ComputeNumSignBits(RHS, 0, &CxtI) > 1)
David Majnemer57d5bc82014-08-19 23:36:30 +0000862 return true;
863
Craig Topper8205a1a2017-05-24 16:53:07 +0000864 KnownBits LHSKnown = computeKnownBits(LHS, 0, &CxtI);
David Majnemer57d5bc82014-08-19 23:36:30 +0000865
Craig Topper8205a1a2017-05-24 16:53:07 +0000866 KnownBits RHSKnown = computeKnownBits(RHS, 0, &CxtI);
David Majnemer57d5bc82014-08-19 23:36:30 +0000867
Craig Topper957a94c2017-04-11 18:47:58 +0000868 // Subtraction of two 2's complement numbers having identical signs will
David Majnemer54c2ca22014-12-26 09:10:14 +0000869 // never overflow.
Craig Topperaaef41f2017-05-22 00:49:33 +0000870 if ((LHSKnown.isNegative() && RHSKnown.isNegative()) ||
871 (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()))
David Majnemer54c2ca22014-12-26 09:10:14 +0000872 return true;
David Majnemer57d5bc82014-08-19 23:36:30 +0000873
David Majnemer54c2ca22014-12-26 09:10:14 +0000874 // TODO: implement logic similar to checkRippleForAdd
David Majnemer57d5bc82014-08-19 23:36:30 +0000875 return false;
876}
877
David Majnemer42158f32014-08-20 07:17:31 +0000878/// \brief Return true if we can prove that:
879/// (sub LHS, RHS) === (sub nuw LHS, RHS)
Craig Topper2b1fc322017-05-22 06:25:31 +0000880bool InstCombiner::willNotOverflowUnsignedSub(const Value *LHS,
881 const Value *RHS,
882 const Instruction &CxtI) const {
David Majnemer42158f32014-08-20 07:17:31 +0000883 // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
Craig Topper1a36b7d2017-05-15 06:39:41 +0000884 KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI);
885 KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI);
886 if (LHSKnown.isNegative() && RHSKnown.isNonNegative())
David Majnemer42158f32014-08-20 07:17:31 +0000887 return true;
888
889 return false;
890}
891
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000892// Checks if any operand is negative and we can convert add to sub.
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000893// This function checks for following negative patterns
894// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
895// ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
896// XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
Benjamin Kramer6cbe6702014-07-07 14:47:51 +0000897static Value *checkForNegativeOperand(BinaryOperator &I,
898 InstCombiner::BuilderTy *Builder) {
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000899 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000900
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000901 // This function creates 2 instructions to replace ADD, we need at least one
902 // of LHS or RHS to have one use to ensure benefit in transform.
903 if (!LHS->hasOneUse() && !RHS->hasOneUse())
904 return nullptr;
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000905
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000906 Value *X = nullptr, *Y = nullptr, *Z = nullptr;
907 const APInt *C1 = nullptr, *C2 = nullptr;
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000908
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000909 // if ONE is on other side, swap
910 if (match(RHS, m_Add(m_Value(X), m_One())))
911 std::swap(LHS, RHS);
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000912
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000913 if (match(LHS, m_Add(m_Value(X), m_One()))) {
914 // if XOR on other side, swap
915 if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
916 std::swap(X, RHS);
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000917
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000918 if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
919 // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))
920 // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))
921 if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
922 Value *NewAnd = Builder->CreateAnd(Z, *C1);
923 return Builder->CreateSub(RHS, NewAnd, "sub");
924 } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
925 // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))
926 // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))
927 Value *NewOr = Builder->CreateOr(Z, ~(*C1));
928 return Builder->CreateSub(RHS, NewOr, "sub");
929 }
930 }
931 }
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000932
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000933 // Restore LHS and RHS
934 LHS = I.getOperand(0);
935 RHS = I.getOperand(1);
Dinesh Dwivedi562fd752014-06-19 10:36:52 +0000936
Dinesh Dwivediadc07732014-06-27 07:47:35 +0000937 // if XOR is on other side, swap
938 if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
939 std::swap(LHS, RHS);
940
941 // C2 is ODD
942 // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))
943 // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))
944 if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
945 if (C1->countTrailingZeros() == 0)
946 if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
947 Value *NewOr = Builder->CreateOr(Z, ~(*C2));
948 return Builder->CreateSub(RHS, NewOr, "sub");
949 }
950 return nullptr;
951}
952
Sanjay Patel4133d4a2017-05-10 00:07:16 +0000953static Instruction *foldAddWithConstant(BinaryOperator &Add,
954 InstCombiner::BuilderTy &Builder) {
955 Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
956 const APInt *C;
957 if (!match(Op1, m_APInt(C)))
958 return nullptr;
959
960 if (C->isSignMask()) {
961 // If wrapping is not allowed, then the addition must set the sign bit:
962 // X + (signmask) --> X | signmask
963 if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
964 return BinaryOperator::CreateOr(Op0, Op1);
965
966 // If wrapping is allowed, then the addition flips the sign bit of LHS:
967 // X + (signmask) --> X ^ signmask
968 return BinaryOperator::CreateXor(Op0, Op1);
969 }
970
971 Value *X;
972 const APInt *C2;
973 Type *Ty = Add.getType();
974
975 // Is this add the last step in a convoluted sext?
976 // add(zext(xor i16 X, -32768), -32768) --> sext X
977 if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&
978 C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C)
979 return CastInst::Create(Instruction::SExt, X, Ty);
980
981 // (add (zext (add nuw X, C2)), C) --> (zext (add nuw X, C2 + C))
982 // FIXME: This should check hasOneUse to not increase the instruction count?
983 if (C->isNegative() &&
984 match(Op0, m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2)))) &&
985 C->sge(-C2->sext(C->getBitWidth()))) {
986 Constant *NewC =
987 ConstantInt::get(X->getType(), *C2 + C->trunc(C2->getBitWidth()));
988 return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty);
989 }
990
Sanjay Patel2e069f22017-05-10 13:56:52 +0000991 // Shifts and add used to flip and mask off the low bit:
992 // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1
993 const APInt *C3;
994 if (*C == 1 && match(Op0, m_OneUse(m_AShr(m_Shl(m_Value(X), m_APInt(C2)),
995 m_APInt(C3)))) &&
996 C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) {
997 Value *NotX = Builder.CreateNot(X);
998 return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
999 }
1000
Sanjay Patel4133d4a2017-05-10 00:07:16 +00001001 return nullptr;
1002}
1003
Dinesh Dwivediadc07732014-06-27 07:47:35 +00001004Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001005 bool Changed = SimplifyAssociativeOrCommutative(I);
1006 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
Jingyue Wu33bd53d2014-06-17 00:42:07 +00001007
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001008 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001009 return replaceInstUsesWith(I, V);
Chris Lattner82aa8882010-01-05 07:18:46 +00001010
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001011 if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
Daniel Berlin2c75c632017-04-26 20:56:07 +00001012 I.hasNoUnsignedWrap(), SQ))
Sanjay Patel4b198802016-02-01 22:23:39 +00001013 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001014
Dinesh Dwivedia71617352014-06-26 05:40:22 +00001015 // (A*B)+(A*C) -> A*(B+C) etc
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00001016 if (Value *V = SimplifyUsingDistributiveLaws(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001017 return replaceInstUsesWith(I, V);
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00001018
Sanjay Patel4133d4a2017-05-10 00:07:16 +00001019 if (Instruction *X = foldAddWithConstant(I, *Builder))
1020 return X;
Sanjay Patel53c5c3d2017-02-18 22:20:09 +00001021
Sanjay Patel4133d4a2017-05-10 00:07:16 +00001022 // FIXME: This should be moved into the above helper function to allow these
1023 // transforms for splat vectors.
Sanjay Patel79acd2a2016-07-16 18:29:26 +00001024 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001025 // zext(bool) + C -> bool ? C + 1 : C
1026 if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
1027 if (ZI->getSrcTy()->isIntegerTy(1))
1028 return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001029
Craig Topperf40110f2014-04-25 05:29:35 +00001030 Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr;
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001031 if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001032 uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001033 const APInt &RHSVal = CI->getValue();
Eli Friedmana2cc2872010-01-31 04:29:12 +00001034 unsigned ExtendAmt = 0;
1035 // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
1036 // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.
1037 if (XorRHS->getValue() == -RHSVal) {
1038 if (RHSVal.isPowerOf2())
1039 ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
1040 else if (XorRHS->getValue().isPowerOf2())
1041 ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
Chris Lattner82aa8882010-01-05 07:18:46 +00001042 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001043
Eli Friedmana2cc2872010-01-31 04:29:12 +00001044 if (ExtendAmt) {
1045 APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
Hal Finkel60db0582014-09-07 18:57:58 +00001046 if (!MaskedValueIsZero(XorLHS, Mask, 0, &I))
Eli Friedmana2cc2872010-01-31 04:29:12 +00001047 ExtendAmt = 0;
1048 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001049
Eli Friedmana2cc2872010-01-31 04:29:12 +00001050 if (ExtendAmt) {
1051 Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt);
1052 Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext");
1053 return BinaryOperator::CreateAShr(NewShl, ShAmt);
Chris Lattner82aa8882010-01-05 07:18:46 +00001054 }
Benjamin Kramerb16bd772011-12-24 17:31:53 +00001055
1056 // If this is a xor that was canonicalized from a sub, turn it back into
1057 // a sub and fuse this add with it.
1058 if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) {
Craig Topper8205a1a2017-05-24 16:53:07 +00001059 KnownBits LHSKnown = computeKnownBits(XorLHS, 0, &I);
Craig Topperb45eabc2017-04-26 16:39:58 +00001060 if ((XorRHS->getValue() | LHSKnown.Zero).isAllOnesValue())
Benjamin Kramerb16bd772011-12-24 17:31:53 +00001061 return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
1062 XorLHS);
1063 }
Craig Topperbcfd2d12017-04-20 16:56:25 +00001064 // (X + signmask) + C could have gotten canonicalized to (X^signmask) + C,
1065 // transform them into (X + (signmask ^ C))
1066 if (XorRHS->getValue().isSignMask())
Craig Toppereafbd572015-12-21 01:02:28 +00001067 return BinaryOperator::CreateAdd(XorLHS,
1068 ConstantExpr::getXor(XorRHS, CI));
Chris Lattner82aa8882010-01-05 07:18:46 +00001069 }
1070 }
1071
Craig Topper3eec73e2017-04-10 16:40:00 +00001072 if (isa<Constant>(RHS))
1073 if (Instruction *NV = foldOpWithConstantIntoOperand(I))
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001074 return NV;
1075
Benjamin Kramer72196f32014-01-19 15:24:22 +00001076 if (I.getType()->getScalarType()->isIntegerTy(1))
Chris Lattner82aa8882010-01-05 07:18:46 +00001077 return BinaryOperator::CreateXor(LHS, RHS);
1078
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001079 // X + X --> X << 1
Chris Lattnerd4067642011-02-17 20:55:29 +00001080 if (LHS == RHS) {
Chris Lattner55920712011-02-17 02:23:02 +00001081 BinaryOperator *New =
1082 BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
1083 New->setHasNoSignedWrap(I.hasNoSignedWrap());
1084 New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1085 return New;
1086 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001087
1088 // -A + B --> B - A
1089 // -A + -B --> -(A + B)
1090 if (Value *LHSV = dyn_castNegVal(LHS)) {
Nuno Lopes2710f1b2012-06-08 22:30:05 +00001091 if (!isa<Constant>(RHS))
1092 if (Value *RHSV = dyn_castNegVal(RHS)) {
1093 Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
1094 return BinaryOperator::CreateNeg(NewAdd);
1095 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001096
Chris Lattner82aa8882010-01-05 07:18:46 +00001097 return BinaryOperator::CreateSub(RHS, LHSV);
1098 }
1099
1100 // A + -B --> A - B
1101 if (!isa<Constant>(RHS))
1102 if (Value *V = dyn_castNegVal(RHS))
1103 return BinaryOperator::CreateSub(LHS, V);
1104
Dinesh Dwivedi562fd752014-06-19 10:36:52 +00001105 if (Value *V = checkForNegativeOperand(I, Builder))
Sanjay Patel4b198802016-02-01 22:23:39 +00001106 return replaceInstUsesWith(I, V);
Dinesh Dwivedi562fd752014-06-19 10:36:52 +00001107
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001108 // A+B --> A|B iff A and B have no bits set in common.
Daniel Jasperaec2fa32016-12-19 08:22:17 +00001109 if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
Jingyue Wuca321902015-05-14 23:53:19 +00001110 return BinaryOperator::CreateOr(LHS, RHS);
Chris Lattner82aa8882010-01-05 07:18:46 +00001111
Benjamin Kramer72196f32014-01-19 15:24:22 +00001112 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
1113 Value *X;
1114 if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X
Chris Lattner82aa8882010-01-05 07:18:46 +00001115 return BinaryOperator::CreateSub(SubOne(CRHS), X);
Benjamin Kramer72196f32014-01-19 15:24:22 +00001116 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001117
Sanjay Patel79acd2a2016-07-16 18:29:26 +00001118 // FIXME: We already did a check for ConstantInt RHS above this.
1119 // FIXME: Is this pattern covered by another fold? No regression tests fail on
1120 // removal.
Benjamin Kramer72196f32014-01-19 15:24:22 +00001121 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001122 // (X & FF00) + xx00 -> (X+xx00) & FF00
Benjamin Kramer72196f32014-01-19 15:24:22 +00001123 Value *X;
1124 ConstantInt *C2;
Chris Lattner82aa8882010-01-05 07:18:46 +00001125 if (LHS->hasOneUse() &&
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001126 match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) &&
1127 CRHS->getValue() == (CRHS->getValue() & C2->getValue())) {
1128 // See if all bits from the first bit set in the Add RHS up are included
1129 // in the mask. First, get the rightmost bit.
1130 const APInt &AddRHSV = CRHS->getValue();
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001131
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001132 // Form a mask of all bits from the lowest bit added through the top.
1133 APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
Chris Lattner82aa8882010-01-05 07:18:46 +00001134
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001135 // See if the and mask includes all of these bits.
1136 APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
Chris Lattner82aa8882010-01-05 07:18:46 +00001137
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001138 if (AddRHSHighBits == AddRHSHighBitsAnd) {
1139 // Okay, the xform is safe. Insert the new add pronto.
1140 Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
1141 return BinaryOperator::CreateAnd(NewAdd, C2);
Chris Lattner82aa8882010-01-05 07:18:46 +00001142 }
1143 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001144 }
1145
1146 // add (select X 0 (sub n A)) A --> select X A n
1147 {
1148 SelectInst *SI = dyn_cast<SelectInst>(LHS);
1149 Value *A = RHS;
1150 if (!SI) {
1151 SI = dyn_cast<SelectInst>(RHS);
1152 A = LHS;
1153 }
1154 if (SI && SI->hasOneUse()) {
1155 Value *TV = SI->getTrueValue();
1156 Value *FV = SI->getFalseValue();
1157 Value *N;
1158
1159 // Can we fold the add into the argument of the select?
1160 // We check both true and false select arguments for a matching subtract.
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001161 if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
Chris Lattner82aa8882010-01-05 07:18:46 +00001162 // Fold the add into the true select value.
1163 return SelectInst::Create(SI->getCondition(), N, A);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001164
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001165 if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
Chris Lattner82aa8882010-01-05 07:18:46 +00001166 // Fold the add into the false select value.
1167 return SelectInst::Create(SI->getCondition(), A, N);
1168 }
1169 }
1170
1171 // Check for (add (sext x), y), see if we can merge this into an
1172 // integer add followed by a sext.
1173 if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
1174 // (add (sext x), cst) --> (sext (add x, cst'))
1175 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
David Majnemera1cfd7c2016-12-30 00:28:58 +00001176 if (LHSConv->hasOneUse()) {
1177 Constant *CI =
1178 ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
1179 if (ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
Craig Topper2b1fc322017-05-22 06:25:31 +00001180 willNotOverflowSignedAdd(LHSConv->getOperand(0), CI, I)) {
David Majnemera1cfd7c2016-12-30 00:28:58 +00001181 // Insert the new, smaller add.
1182 Value *NewAdd =
1183 Builder->CreateNSWAdd(LHSConv->getOperand(0), CI, "addconv");
1184 return new SExtInst(NewAdd, I.getType());
1185 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001186 }
1187 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001188
Chris Lattner82aa8882010-01-05 07:18:46 +00001189 // (add (sext x), (sext y)) --> (sext (add int x, y))
1190 if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
Craig Topper79e5bc52017-03-30 22:28:55 +00001191 // Only do this if x/y have the same type, if at least one of them has a
Chris Lattner82aa8882010-01-05 07:18:46 +00001192 // single use (so we don't increase the number of sexts), and if the
1193 // integer add will not overflow.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001194 if (LHSConv->getOperand(0)->getType() ==
1195 RHSConv->getOperand(0)->getType() &&
Chris Lattner82aa8882010-01-05 07:18:46 +00001196 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
Craig Topper2b1fc322017-05-22 06:25:31 +00001197 willNotOverflowSignedAdd(LHSConv->getOperand(0),
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001198 RHSConv->getOperand(0), I)) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001199 // Insert the new integer add.
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001200 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
Chris Lattnerdec68472010-01-05 20:56:24 +00001201 RHSConv->getOperand(0), "addconv");
Chris Lattner82aa8882010-01-05 07:18:46 +00001202 return new SExtInst(NewAdd, I.getType());
1203 }
1204 }
1205 }
1206
David Majnemera1cfd7c2016-12-30 00:28:58 +00001207 // Check for (add (zext x), y), see if we can merge this into an
1208 // integer add followed by a zext.
1209 if (auto *LHSConv = dyn_cast<ZExtInst>(LHS)) {
1210 // (add (zext x), cst) --> (zext (add x, cst'))
1211 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
1212 if (LHSConv->hasOneUse()) {
1213 Constant *CI =
1214 ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
1215 if (ConstantExpr::getZExt(CI, I.getType()) == RHSC &&
Craig Topperbb973722017-05-15 02:44:08 +00001216 willNotOverflowUnsignedAdd(LHSConv->getOperand(0), CI, I)) {
David Majnemera1cfd7c2016-12-30 00:28:58 +00001217 // Insert the new, smaller add.
1218 Value *NewAdd =
1219 Builder->CreateNUWAdd(LHSConv->getOperand(0), CI, "addconv");
1220 return new ZExtInst(NewAdd, I.getType());
1221 }
1222 }
1223 }
1224
1225 // (add (zext x), (zext y)) --> (zext (add int x, y))
1226 if (auto *RHSConv = dyn_cast<ZExtInst>(RHS)) {
Craig Topper79e5bc52017-03-30 22:28:55 +00001227 // Only do this if x/y have the same type, if at least one of them has a
David Majnemera1cfd7c2016-12-30 00:28:58 +00001228 // single use (so we don't increase the number of zexts), and if the
1229 // integer add will not overflow.
1230 if (LHSConv->getOperand(0)->getType() ==
1231 RHSConv->getOperand(0)->getType() &&
1232 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
Craig Topperbb973722017-05-15 02:44:08 +00001233 willNotOverflowUnsignedAdd(LHSConv->getOperand(0),
1234 RHSConv->getOperand(0), I)) {
David Majnemera1cfd7c2016-12-30 00:28:58 +00001235 // Insert the new integer add.
1236 Value *NewAdd = Builder->CreateNUWAdd(
1237 LHSConv->getOperand(0), RHSConv->getOperand(0), "addconv");
1238 return new ZExtInst(NewAdd, I.getType());
1239 }
1240 }
1241 }
1242
David Majnemerab07f002014-08-11 22:32:02 +00001243 // (add (xor A, B) (and A, B)) --> (or A, B)
Chad Rosier7813dce2012-04-26 23:29:14 +00001244 {
Craig Topperf40110f2014-04-25 05:29:35 +00001245 Value *A = nullptr, *B = nullptr;
Chad Rosier7813dce2012-04-26 23:29:14 +00001246 if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
Craig Topper31cc1432017-04-10 07:13:40 +00001247 match(LHS, m_c_And(m_Specific(A), m_Specific(B))))
Chad Rosier7813dce2012-04-26 23:29:14 +00001248 return BinaryOperator::CreateOr(A, B);
1249
1250 if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
Craig Topper31cc1432017-04-10 07:13:40 +00001251 match(RHS, m_c_And(m_Specific(A), m_Specific(B))))
Chad Rosier7813dce2012-04-26 23:29:14 +00001252 return BinaryOperator::CreateOr(A, B);
1253 }
1254
David Majnemerab07f002014-08-11 22:32:02 +00001255 // (add (or A, B) (and A, B)) --> (add A, B)
1256 {
1257 Value *A = nullptr, *B = nullptr;
1258 if (match(RHS, m_Or(m_Value(A), m_Value(B))) &&
Craig Topper31cc1432017-04-10 07:13:40 +00001259 match(LHS, m_c_And(m_Specific(A), m_Specific(B)))) {
David Majnemerab07f002014-08-11 22:32:02 +00001260 auto *New = BinaryOperator::CreateAdd(A, B);
1261 New->setHasNoSignedWrap(I.hasNoSignedWrap());
1262 New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1263 return New;
1264 }
1265
1266 if (match(LHS, m_Or(m_Value(A), m_Value(B))) &&
Craig Topper31cc1432017-04-10 07:13:40 +00001267 match(RHS, m_c_And(m_Specific(A), m_Specific(B)))) {
David Majnemerab07f002014-08-11 22:32:02 +00001268 auto *New = BinaryOperator::CreateAdd(A, B);
1269 New->setHasNoSignedWrap(I.hasNoSignedWrap());
1270 New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
1271 return New;
1272 }
1273 }
1274
Craig Topper2b1fc322017-05-22 06:25:31 +00001275 // TODO(jingyue): Consider willNotOverflowSignedAdd and
Craig Topperbb973722017-05-15 02:44:08 +00001276 // willNotOverflowUnsignedAdd to reduce the number of invocations of
Jingyue Wu33bd53d2014-06-17 00:42:07 +00001277 // computeKnownBits.
Craig Topper2b1fc322017-05-22 06:25:31 +00001278 if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
Rafael Espindolad1a2c2d2014-06-02 22:01:04 +00001279 Changed = true;
1280 I.setHasNoSignedWrap(true);
1281 }
Craig Topperbb973722017-05-15 02:44:08 +00001282 if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
Jingyue Wu33bd53d2014-06-17 00:42:07 +00001283 Changed = true;
1284 I.setHasNoUnsignedWrap(true);
1285 }
Rafael Espindolad1a2c2d2014-06-02 22:01:04 +00001286
Craig Topperf40110f2014-04-25 05:29:35 +00001287 return Changed ? &I : nullptr;
Chris Lattner82aa8882010-01-05 07:18:46 +00001288}
1289
1290Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
Duncan Sands641baf12010-11-13 15:10:37 +00001291 bool Changed = SimplifyAssociativeOrCommutative(I);
Chris Lattner82aa8882010-01-05 07:18:46 +00001292 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1293
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001294 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001295 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001296
Daniel Berlin2c75c632017-04-26 20:56:07 +00001297 if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), SQ))
Sanjay Patel4b198802016-02-01 22:23:39 +00001298 return replaceInstUsesWith(I, V);
Chris Lattner82aa8882010-01-05 07:18:46 +00001299
Sanjay Pateldb0938f2017-01-10 23:49:07 +00001300 if (isa<Constant>(RHS))
1301 if (Instruction *FoldedFAdd = foldOpWithConstantIntoOperand(I))
1302 return FoldedFAdd;
Michael Ilsemane2754dc2012-12-14 22:08:26 +00001303
Chris Lattner82aa8882010-01-05 07:18:46 +00001304 // -A + B --> B - A
1305 // -A + -B --> -(A + B)
Owen Andersone7321662014-01-16 21:26:02 +00001306 if (Value *LHSV = dyn_castFNegVal(LHS)) {
1307 Instruction *RI = BinaryOperator::CreateFSub(RHS, LHSV);
1308 RI->copyFastMathFlags(&I);
1309 return RI;
1310 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001311
1312 // A + -B --> A - B
1313 if (!isa<Constant>(RHS))
Owen Andersone7321662014-01-16 21:26:02 +00001314 if (Value *V = dyn_castFNegVal(RHS)) {
1315 Instruction *RI = BinaryOperator::CreateFSub(LHS, V);
1316 RI->copyFastMathFlags(&I);
1317 return RI;
1318 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001319
Dan Gohman6f34abd2010-03-02 01:11:08 +00001320 // Check for (fadd double (sitofp x), y), see if we can merge this into an
Chris Lattner82aa8882010-01-05 07:18:46 +00001321 // integer add followed by a promotion.
1322 if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
Artur Pilipenko4cc61302017-03-21 11:32:15 +00001323 Value *LHSIntVal = LHSConv->getOperand(0);
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001324 Type *FPType = LHSConv->getType();
1325
1326 // TODO: This check is overly conservative. In many cases known bits
1327 // analysis can tell us that the result of the addition has less significant
1328 // bits than the integer type can hold.
1329 auto IsValidPromotion = [](Type *FTy, Type *ITy) {
Artur Pilipenko0632bdc2017-04-22 07:24:52 +00001330 Type *FScalarTy = FTy->getScalarType();
1331 Type *IScalarTy = ITy->getScalarType();
1332
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001333 // Do we have enough bits in the significand to represent the result of
1334 // the integer addition?
1335 unsigned MaxRepresentableBits =
Artur Pilipenko0632bdc2017-04-22 07:24:52 +00001336 APFloat::semanticsPrecision(FScalarTy->getFltSemantics());
1337 return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits;
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001338 };
Artur Pilipenko4cc61302017-03-21 11:32:15 +00001339
Dan Gohman6f34abd2010-03-02 01:11:08 +00001340 // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst))
Chris Lattner82aa8882010-01-05 07:18:46 +00001341 // ... if the constant fits in the integer value. This is useful for things
1342 // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer
1343 // requires a constant pool load, and generally allows the add to be better
1344 // instcombined.
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001345 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS))
1346 if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1347 Constant *CI =
1348 ConstantExpr::getFPToSI(CFP, LHSIntVal->getType());
1349 if (LHSConv->hasOneUse() &&
1350 ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
Craig Topper2b1fc322017-05-22 06:25:31 +00001351 willNotOverflowSignedAdd(LHSIntVal, CI, I)) {
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001352 // Insert the new integer add.
1353 Value *NewAdd = Builder->CreateNSWAdd(LHSIntVal,
1354 CI, "addconv");
1355 return new SIToFPInst(NewAdd, I.getType());
1356 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001357 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001358
Dan Gohman6f34abd2010-03-02 01:11:08 +00001359 // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y))
Chris Lattner82aa8882010-01-05 07:18:46 +00001360 if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
Artur Pilipenko4cc61302017-03-21 11:32:15 +00001361 Value *RHSIntVal = RHSConv->getOperand(0);
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001362 // It's enough to check LHS types only because we require int types to
1363 // be the same for this transform.
1364 if (IsValidPromotion(FPType, LHSIntVal->getType())) {
1365 // Only do this if x/y have the same type, if at least one of them has a
1366 // single use (so we don't increase the number of int->fp conversions),
1367 // and if the integer add will not overflow.
1368 if (LHSIntVal->getType() == RHSIntVal->getType() &&
1369 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
Craig Topper2b1fc322017-05-22 06:25:31 +00001370 willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) {
Artur Pilipenko134d94f2017-04-21 18:45:25 +00001371 // Insert the new integer add.
1372 Value *NewAdd = Builder->CreateNSWAdd(LHSIntVal,
1373 RHSIntVal, "addconv");
1374 return new SIToFPInst(NewAdd, I.getType());
1375 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001376 }
1377 }
1378 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001379
Jean-Luc Duprat3e4fc3e2013-05-06 16:55:50 +00001380 // select C, 0, B + select C, A, 0 -> select C, A, B
1381 {
1382 Value *A1, *B1, *C1, *A2, *B2, *C2;
1383 if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
1384 match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) {
1385 if (C1 == C2) {
Craig Topperf40110f2014-04-25 05:29:35 +00001386 Constant *Z1=nullptr, *Z2=nullptr;
Jean-Luc Duprat3e4fc3e2013-05-06 16:55:50 +00001387 Value *A, *B, *C=C1;
1388 if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
1389 Z1 = dyn_cast<Constant>(A1); A = A2;
1390 Z2 = dyn_cast<Constant>(B2); B = B1;
1391 } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
1392 Z1 = dyn_cast<Constant>(B1); B = B2;
David Majnemer72a643d2014-11-03 05:53:55 +00001393 Z2 = dyn_cast<Constant>(A2); A = A1;
Jean-Luc Duprat3e4fc3e2013-05-06 16:55:50 +00001394 }
David Majnemer72a643d2014-11-03 05:53:55 +00001395
1396 if (Z1 && Z2 &&
1397 (I.hasNoSignedZeros() ||
Jean-Luc Duprat3e4fc3e2013-05-06 16:55:50 +00001398 (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
1399 return SelectInst::Create(C, A, B);
1400 }
1401 }
1402 }
1403 }
1404
Shuxin Yang37a1efe2012-12-18 23:10:12 +00001405 if (I.hasUnsafeAlgebra()) {
1406 if (Value *V = FAddCombine(Builder).simplify(&I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001407 return replaceInstUsesWith(I, V);
Shuxin Yang37a1efe2012-12-18 23:10:12 +00001408 }
1409
Craig Topperf40110f2014-04-25 05:29:35 +00001410 return Changed ? &I : nullptr;
Chris Lattner82aa8882010-01-05 07:18:46 +00001411}
1412
Chris Lattner82aa8882010-01-05 07:18:46 +00001413/// Optimize pointer differences into the same array into a size. Consider:
1414/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer
1415/// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
1416///
1417Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
Chris Lattner229907c2011-07-18 04:54:35 +00001418 Type *Ty) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001419 // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize
1420 // this.
1421 bool Swapped = false;
Craig Topperf40110f2014-04-25 05:29:35 +00001422 GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001423
Chris Lattner82aa8882010-01-05 07:18:46 +00001424 // For now we require one side to be the base pointer "A" or a constant
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001425 // GEP derived from it.
1426 if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001427 // (gep X, ...) - X
1428 if (LHSGEP->getOperand(0) == RHS) {
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001429 GEP1 = LHSGEP;
Chris Lattner82aa8882010-01-05 07:18:46 +00001430 Swapped = false;
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001431 } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
1432 // (gep X, ...) - (gep X, ...)
1433 if (LHSGEP->getOperand(0)->stripPointerCasts() ==
1434 RHSGEP->getOperand(0)->stripPointerCasts()) {
1435 GEP2 = RHSGEP;
1436 GEP1 = LHSGEP;
Chris Lattner82aa8882010-01-05 07:18:46 +00001437 Swapped = false;
1438 }
1439 }
1440 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001441
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001442 if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001443 // X - (gep X, ...)
1444 if (RHSGEP->getOperand(0) == LHS) {
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001445 GEP1 = RHSGEP;
Chris Lattner82aa8882010-01-05 07:18:46 +00001446 Swapped = true;
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001447 } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
1448 // (gep X, ...) - (gep X, ...)
1449 if (RHSGEP->getOperand(0)->stripPointerCasts() ==
1450 LHSGEP->getOperand(0)->stripPointerCasts()) {
1451 GEP2 = LHSGEP;
1452 GEP1 = RHSGEP;
Chris Lattner82aa8882010-01-05 07:18:46 +00001453 Swapped = true;
1454 }
1455 }
1456 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001457
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001458 // Avoid duplicating the arithmetic if GEP2 has non-constant indices and
1459 // multiple users.
Craig Topperf40110f2014-04-25 05:29:35 +00001460 if (!GEP1 ||
1461 (GEP2 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse()))
1462 return nullptr;
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001463
Chris Lattner82aa8882010-01-05 07:18:46 +00001464 // Emit the offset of the GEP and an intptr_t.
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001465 Value *Result = EmitGEPOffset(GEP1);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001466
Chris Lattner82aa8882010-01-05 07:18:46 +00001467 // If we had a constant expression GEP on the other side offsetting the
1468 // pointer, subtract it from the offset we have.
Benjamin Kramer7746eb62012-02-20 14:34:57 +00001469 if (GEP2) {
1470 Value *Offset = EmitGEPOffset(GEP2);
1471 Result = Builder->CreateSub(Result, Offset);
Chris Lattner82aa8882010-01-05 07:18:46 +00001472 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001473
1474 // If we have p - gep(p, ...) then we have to negate the result.
1475 if (Swapped)
1476 Result = Builder->CreateNeg(Result, "diff.neg");
1477
1478 return Builder->CreateIntCast(Result, Ty, true);
1479}
1480
Chris Lattner82aa8882010-01-05 07:18:46 +00001481Instruction *InstCombiner::visitSub(BinaryOperator &I) {
1482 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1483
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001484 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001485 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001486
Duncan Sands0a2c41682010-12-15 14:07:39 +00001487 if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
Daniel Berlin2c75c632017-04-26 20:56:07 +00001488 I.hasNoUnsignedWrap(), SQ))
Sanjay Patel4b198802016-02-01 22:23:39 +00001489 return replaceInstUsesWith(I, V);
Chris Lattner82aa8882010-01-05 07:18:46 +00001490
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00001491 // (A*B)-(A*C) -> A*(B-C) etc
1492 if (Value *V = SimplifyUsingDistributiveLaws(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001493 return replaceInstUsesWith(I, V);
Duncan Sandsfbb9ac32010-12-22 13:36:08 +00001494
David Majnemera92687d2014-07-31 04:49:29 +00001495 // If this is a 'B = x-(-A)', change to B = x+A.
Chris Lattner82aa8882010-01-05 07:18:46 +00001496 if (Value *V = dyn_castNegVal(Op1)) {
1497 BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
David Majnemera92687d2014-07-31 04:49:29 +00001498
1499 if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
1500 assert(BO->getOpcode() == Instruction::Sub &&
1501 "Expected a subtraction operator!");
1502 if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
1503 Res->setHasNoSignedWrap(true);
David Majnemer0e6c9862014-08-22 16:41:23 +00001504 } else {
1505 if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
1506 Res->setHasNoSignedWrap(true);
David Majnemera92687d2014-07-31 04:49:29 +00001507 }
1508
Chris Lattner82aa8882010-01-05 07:18:46 +00001509 return Res;
1510 }
1511
Craig Topperc745b6a2017-04-04 21:44:56 +00001512 if (I.getType()->getScalarType()->isIntegerTy(1))
Chris Lattner82aa8882010-01-05 07:18:46 +00001513 return BinaryOperator::CreateXor(Op0, Op1);
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001514
1515 // Replace (-1 - A) with (~A).
1516 if (match(Op0, m_AllOnes()))
1517 return BinaryOperator::CreateNot(Op1);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001518
Benjamin Kramer72196f32014-01-19 15:24:22 +00001519 if (Constant *C = dyn_cast<Constant>(Op0)) {
Chris Lattner82aa8882010-01-05 07:18:46 +00001520 // C - ~X == X + (1+C)
Craig Topperf40110f2014-04-25 05:29:35 +00001521 Value *X = nullptr;
Chris Lattner82aa8882010-01-05 07:18:46 +00001522 if (match(Op1, m_Not(m_Value(X))))
1523 return BinaryOperator::CreateAdd(X, AddOne(C));
1524
Benjamin Kramer72196f32014-01-19 15:24:22 +00001525 // Try to fold constant sub into select arguments.
1526 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1527 if (Instruction *R = FoldOpIntoSelect(I, SI))
1528 return R;
1529
Craig Topperfb71b7d2017-04-14 19:20:12 +00001530 // Try to fold constant sub into PHI values.
1531 if (PHINode *PN = dyn_cast<PHINode>(Op1))
1532 if (Instruction *R = foldOpIntoPhi(I, PN))
1533 return R;
1534
Benjamin Kramer72196f32014-01-19 15:24:22 +00001535 // C-(X+C2) --> (C-C2)-X
1536 Constant *C2;
1537 if (match(Op1, m_Add(m_Value(X), m_Constant(C2))))
1538 return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
1539
Benjamin Kramer72196f32014-01-19 15:24:22 +00001540 // Fold (sub 0, (zext bool to B)) --> (sext bool to B)
1541 if (C->isNullValue() && match(Op1, m_ZExt(m_Value(X))))
1542 if (X->getType()->getScalarType()->isIntegerTy(1))
1543 return CastInst::CreateSExtOrBitCast(X, Op1->getType());
1544
1545 // Fold (sub 0, (sext bool to B)) --> (zext bool to B)
1546 if (C->isNullValue() && match(Op1, m_SExt(m_Value(X))))
1547 if (X->getType()->getScalarType()->isIntegerTy(1))
1548 return CastInst::CreateZExtOrBitCast(X, Op1->getType());
1549 }
1550
Sanjay Patel6d6eca52016-10-14 16:31:54 +00001551 const APInt *Op0C;
1552 if (match(Op0, m_APInt(Op0C))) {
1553 unsigned BitWidth = I.getType()->getScalarSizeInBits();
1554
Chris Lattner82aa8882010-01-05 07:18:46 +00001555 // -(X >>u 31) -> (X >>s 31)
1556 // -(X >>s 31) -> (X >>u 31)
Sanjay Patel6d6eca52016-10-14 16:31:54 +00001557 if (*Op0C == 0) {
David Majnemer72a643d2014-11-03 05:53:55 +00001558 Value *X;
Sanjay Patel6d6eca52016-10-14 16:31:54 +00001559 const APInt *ShAmt;
1560 if (match(Op1, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
1561 *ShAmt == BitWidth - 1) {
1562 Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
1563 return BinaryOperator::CreateAShr(X, ShAmtOp);
1564 }
1565 if (match(Op1, m_AShr(m_Value(X), m_APInt(ShAmt))) &&
1566 *ShAmt == BitWidth - 1) {
1567 Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
1568 return BinaryOperator::CreateLShr(X, ShAmtOp);
1569 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001570 }
Matthias Braunec683342015-04-30 22:04:26 +00001571
1572 // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
1573 // zero.
Craig Topperb4da6842017-04-06 21:06:03 +00001574 if (Op0C->isMask()) {
Craig Topper8205a1a2017-05-24 16:53:07 +00001575 KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
Craig Topperb45eabc2017-04-26 16:39:58 +00001576 if ((*Op0C | RHSKnown.Zero).isAllOnesValue())
Sanjay Patel6d6eca52016-10-14 16:31:54 +00001577 return BinaryOperator::CreateXor(Op1, Op0);
Matthias Braunec683342015-04-30 22:04:26 +00001578 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001579 }
1580
David Majnemer72a643d2014-11-03 05:53:55 +00001581 {
Suyog Sardacba4b1d2014-10-08 08:37:49 +00001582 Value *Y;
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001583 // X-(X+Y) == -Y X-(Y+X) == -Y
Craig Topper98851ad2017-04-10 16:59:40 +00001584 if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001585 return BinaryOperator::CreateNeg(Y);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001586
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001587 // (X-Y)-X == -Y
1588 if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
1589 return BinaryOperator::CreateNeg(Y);
1590 }
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001591
David Majnemer312c3e52014-10-19 08:32:32 +00001592 // (sub (or A, B) (xor A, B)) --> (and A, B)
1593 {
Craig Topper0d830ff2017-04-10 18:09:25 +00001594 Value *A, *B;
David Majnemer312c3e52014-10-19 08:32:32 +00001595 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
Craig Topper0d830ff2017-04-10 18:09:25 +00001596 match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
David Majnemer312c3e52014-10-19 08:32:32 +00001597 return BinaryOperator::CreateAnd(A, B);
1598 }
1599
Craig Topper0d830ff2017-04-10 18:09:25 +00001600 {
1601 Value *Y;
David Majnemer72a643d2014-11-03 05:53:55 +00001602 // ((X | Y) - X) --> (~X & Y)
Craig Topper0d830ff2017-04-10 18:09:25 +00001603 if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
David Majnemer72a643d2014-11-03 05:53:55 +00001604 return BinaryOperator::CreateAnd(
1605 Y, Builder->CreateNot(Op1, Op1->getName() + ".not"));
1606 }
1607
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001608 if (Op1->hasOneUse()) {
Craig Topperf40110f2014-04-25 05:29:35 +00001609 Value *X = nullptr, *Y = nullptr, *Z = nullptr;
1610 Constant *C = nullptr;
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001611
1612 // (X - (Y - Z)) --> (X + (Z - Y)).
1613 if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
1614 return BinaryOperator::CreateAdd(Op0,
1615 Builder->CreateSub(Z, Y, Op1->getName()));
1616
1617 // (X - (X & Y)) --> (X & ~Y)
1618 //
Craig Topper0d830ff2017-04-10 18:09:25 +00001619 if (match(Op1, m_c_And(m_Value(Y), m_Specific(Op0))))
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001620 return BinaryOperator::CreateAnd(Op0,
1621 Builder->CreateNot(Y, Y->getName() + ".not"));
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001622
David Majnemerbdeef602014-07-02 06:07:09 +00001623 // 0 - (X sdiv C) -> (X sdiv -C) provided the negation doesn't overflow.
1624 if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) &&
David Majnemer0e6c9862014-08-22 16:41:23 +00001625 C->isNotMinSignedValue() && !C->isOneValue())
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001626 return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
1627
1628 // 0 - (X << Y) -> (-X << Y) when X is freely negatable.
1629 if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
1630 if (Value *XNeg = dyn_castNegVal(X))
1631 return BinaryOperator::CreateShl(XNeg, Y);
1632
Sanjay Patelc6c59652016-10-14 15:24:31 +00001633 // Subtracting -1/0 is the same as adding 1/0:
1634 // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
1635 // 'nuw' is dropped in favor of the canonical form.
1636 if (match(Op1, m_SExt(m_Value(Y))) &&
1637 Y->getType()->getScalarSizeInBits() == 1) {
1638 Value *Zext = Builder->CreateZExt(Y, I.getType());
1639 BinaryOperator *Add = BinaryOperator::CreateAdd(Op0, Zext);
1640 Add->setHasNoSignedWrap(I.hasNoSignedWrap());
1641 return Add;
1642 }
1643
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001644 // X - A*-B -> X + A*B
1645 // X - -A*B -> X + A*B
1646 Value *A, *B;
Craig Topper0d830ff2017-04-10 18:09:25 +00001647 Constant *CI;
1648 if (match(Op1, m_c_Mul(m_Value(A), m_Neg(m_Value(B)))))
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001649 return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001650
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001651 // X - A*CI -> X + A*-CI
Craig Topper0d830ff2017-04-10 18:09:25 +00001652 // No need to handle commuted multiply because multiply handling will
1653 // ensure constant will be move to the right hand side.
1654 if (match(Op1, m_Mul(m_Value(A), m_Constant(CI)))) {
Chris Lattner7d0e43f2011-02-10 05:14:58 +00001655 Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
1656 return BinaryOperator::CreateAdd(Op0, NewMul);
Chris Lattner82aa8882010-01-05 07:18:46 +00001657 }
1658 }
1659
Chris Lattner82aa8882010-01-05 07:18:46 +00001660 // Optimize pointer differences into the same array into a size. Consider:
1661 // &A[10] - &A[0]: we should compile this to "10".
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001662 Value *LHSOp, *RHSOp;
1663 if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
1664 match(Op1, m_PtrToInt(m_Value(RHSOp))))
1665 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
Sanjay Patel4b198802016-02-01 22:23:39 +00001666 return replaceInstUsesWith(I, Res);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001667
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001668 // trunc(p)-trunc(q) -> trunc(p-q)
1669 if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
1670 match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
1671 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
Sanjay Patel4b198802016-02-01 22:23:39 +00001672 return replaceInstUsesWith(I, Res);
Michael Ilseman9fc0f252012-12-12 20:57:53 +00001673
David Majnemer57d5bc82014-08-19 23:36:30 +00001674 bool Changed = false;
Craig Topper2b1fc322017-05-22 06:25:31 +00001675 if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
David Majnemer57d5bc82014-08-19 23:36:30 +00001676 Changed = true;
1677 I.setHasNoSignedWrap(true);
1678 }
Craig Topper2b1fc322017-05-22 06:25:31 +00001679 if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {
David Majnemer42158f32014-08-20 07:17:31 +00001680 Changed = true;
1681 I.setHasNoUnsignedWrap(true);
1682 }
David Majnemer57d5bc82014-08-19 23:36:30 +00001683
1684 return Changed ? &I : nullptr;
Chris Lattner82aa8882010-01-05 07:18:46 +00001685}
1686
1687Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
1688 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1689
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001690 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001691 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +00001692
Daniel Berlin2c75c632017-04-26 20:56:07 +00001693 if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), SQ))
Sanjay Patel4b198802016-02-01 22:23:39 +00001694 return replaceInstUsesWith(I, V);
Michael Ilsemand5787be2012-12-12 00:28:32 +00001695
Sanjay Patele68f7152014-12-31 22:14:05 +00001696 // fsub nsz 0, X ==> fsub nsz -0.0, X
1697 if (I.getFastMathFlags().noSignedZeros() && match(Op0, m_Zero())) {
1698 // Subtraction from -0.0 is the canonical form of fneg.
1699 Instruction *NewI = BinaryOperator::CreateFNeg(Op1);
1700 NewI->copyFastMathFlags(&I);
1701 return NewI;
1702 }
1703
Stephen Lina9b57f62013-07-20 07:13:13 +00001704 if (isa<Constant>(Op0))
1705 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1706 if (Instruction *NV = FoldOpIntoSelect(I, SI))
1707 return NV;
1708
Owen Andersone37c2e42013-07-26 21:40:29 +00001709 // If this is a 'B = x-(-A)', change to B = x+A, potentially looking
1710 // through FP extensions/truncations along the way.
Owen Andersonc7be5192013-07-30 23:53:17 +00001711 if (Value *V = dyn_castFNegVal(Op1)) {
1712 Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V);
1713 NewI->copyFastMathFlags(&I);
1714 return NewI;
1715 }
Owen Andersone37c2e42013-07-26 21:40:29 +00001716 if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) {
1717 if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) {
1718 Value *NewTrunc = Builder->CreateFPTrunc(V, I.getType());
Owen Andersonc7be5192013-07-30 23:53:17 +00001719 Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc);
1720 NewI->copyFastMathFlags(&I);
1721 return NewI;
Owen Andersone37c2e42013-07-26 21:40:29 +00001722 }
1723 } else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) {
1724 if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) {
Owen Andersond6d4da02013-07-26 22:06:21 +00001725 Value *NewExt = Builder->CreateFPExt(V, I.getType());
Owen Andersonc7be5192013-07-30 23:53:17 +00001726 Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt);
1727 NewI->copyFastMathFlags(&I);
1728 return NewI;
Owen Andersone37c2e42013-07-26 21:40:29 +00001729 }
1730 }
Chris Lattner82aa8882010-01-05 07:18:46 +00001731
Shuxin Yang37a1efe2012-12-18 23:10:12 +00001732 if (I.hasUnsafeAlgebra()) {
1733 if (Value *V = FAddCombine(Builder).simplify(&I))
Sanjay Patel4b198802016-02-01 22:23:39 +00001734 return replaceInstUsesWith(I, V);
Shuxin Yang37a1efe2012-12-18 23:10:12 +00001735 }
1736
Craig Topperf40110f2014-04-25 05:29:35 +00001737 return nullptr;
Chris Lattner82aa8882010-01-05 07:18:46 +00001738}