Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 1 | //===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===// |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the visit functions for add, fadd, sub, and fsub. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Chandler Carruth | a917458 | 2015-01-22 05:25:13 +0000 | [diff] [blame] | 14 | #include "InstCombineInternal.h" |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 15 | #include "llvm/ADT/APFloat.h" |
| 16 | #include "llvm/ADT/APInt.h" |
Craig Topper | 5871321 | 2013-07-15 04:27:47 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/STLExtras.h" |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/SmallVector.h" |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 19 | #include "llvm/Analysis/InstructionSimplify.h" |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 20 | #include "llvm/Analysis/ValueTracking.h" |
| 21 | #include "llvm/IR/Constant.h" |
| 22 | #include "llvm/IR/Constants.h" |
| 23 | #include "llvm/IR/InstrTypes.h" |
| 24 | #include "llvm/IR/Instruction.h" |
| 25 | #include "llvm/IR/Instructions.h" |
| 26 | #include "llvm/IR/Operator.h" |
Chandler Carruth | 820a908 | 2014-03-04 11:08:18 +0000 | [diff] [blame] | 27 | #include "llvm/IR/PatternMatch.h" |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 28 | #include "llvm/IR/Type.h" |
| 29 | #include "llvm/IR/Value.h" |
| 30 | #include "llvm/Support/AlignOf.h" |
| 31 | #include "llvm/Support/Casting.h" |
Craig Topper | b45eabc | 2017-04-26 16:39:58 +0000 | [diff] [blame] | 32 | #include "llvm/Support/KnownBits.h" |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 33 | #include <cassert> |
| 34 | #include <utility> |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 35 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 36 | using namespace llvm; |
| 37 | using namespace PatternMatch; |
| 38 | |
Chandler Carruth | 964daaa | 2014-04-22 02:55:47 +0000 | [diff] [blame] | 39 | #define DEBUG_TYPE "instcombine" |
| 40 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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 |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 46 | /// constructor is merely 4-byte-store-zero (Assuming compiler is able to |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 47 | /// perform write-merging). |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 48 | /// |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 49 | class FAddendCoef { |
| 50 | public: |
Suyog Sarda | de409fd | 2014-07-17 06:09:34 +0000 | [diff] [blame] | 51 | // The constructor has to initialize a APFloat, which is unnecessary for |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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. |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 56 | FAddendCoef() = default; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 57 | ~FAddendCoef(); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 58 | |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 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 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 65 | void set(short C) { |
| 66 | assert(!insaneIntVal(C) && "Insane coefficient"); |
| 67 | IsFp = false; IntVal = C; |
| 68 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 69 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 70 | void set(const APFloat& C); |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 71 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 72 | void negate(); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 73 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 74 | bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } |
| 75 | Value *getValue(Type *) const; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 76 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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; } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 81 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 82 | private: |
| 83 | bool insaneIntVal(int V) { return V > 4 || V < -4; } |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 84 | |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 85 | APFloat *getFpValPtr() |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 86 | { return reinterpret_cast<APFloat *>(&FpValBuf.buffer[0]); } |
| 87 | |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 88 | const APFloat *getFpValPtr() const |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 89 | { return reinterpret_cast<const APFloat *>(&FpValBuf.buffer[0]); } |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 90 | |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 91 | const APFloat &getFpVal() const { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 92 | assert(IsFp && BufHasFpVal && "Incorret state"); |
David Greene | 530430b | 2013-01-14 21:04:40 +0000 | [diff] [blame] | 93 | return *getFpValPtr(); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 96 | APFloat &getFpVal() { |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 97 | assert(IsFp && BufHasFpVal && "Incorret state"); |
| 98 | return *getFpValPtr(); |
| 99 | } |
| 100 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 101 | bool isInt() const { return !IsFp; } |
| 102 | |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 103 | // If the coefficient is represented by an integer, promote it to a |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 104 | // floating point. |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 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 |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 109 | // from an *SIGNED* integer. |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 110 | APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); |
Shuxin Yang | 5b841c4 | 2012-12-19 01:10:17 +0000 | [diff] [blame] | 111 | |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 112 | bool IsFp = false; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 113 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 114 | // True iff FpValBuf contains an instance of APFloat. |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 115 | bool BufHasFpVal = false; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 116 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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. |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 121 | short IntVal = 0; |
Shuxin Yang | 5b841c4 | 2012-12-19 01:10:17 +0000 | [diff] [blame] | 122 | |
| 123 | AlignedCharArrayUnion<APFloat> FpValBuf; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 124 | }; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 125 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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>. |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 129 | class FAddend { |
| 130 | public: |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 131 | FAddend() = default; |
| 132 | |
| 133 | void operator+=(const FAddend &T) { |
| 134 | assert((Val == T.Val) && "Symbolic-values disagree"); |
| 135 | Coeff += T.Coeff; |
| 136 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 137 | |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 138 | Value *getSymVal() const { return Val; } |
| 139 | const FAddendCoef &getCoef() const { return Coeff; } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 140 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 141 | bool isConstant() const { return Val == nullptr; } |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 142 | bool isZero() const { return Coeff.isZero(); } |
| 143 | |
Richard Trieu | 7a08381 | 2016-02-18 22:09:30 +0000 | [diff] [blame] | 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 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 156 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 157 | void negate() { Coeff.negate(); } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 158 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 162 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 163 | /// Similar to FAddend::drillDownOneStep() except that the value being |
| 164 | /// splitted is the addend itself. |
| 165 | unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 166 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 167 | private: |
| 168 | void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 169 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 170 | // This addend has the value of "Coeff * Val". |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 171 | Value *Val = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 172 | FAddendCoef Coeff; |
| 173 | }; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 174 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 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: |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 180 | FAddCombine(InstCombiner::BuilderTy &B) : Builder(B) {} |
| 181 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 182 | Value *simplify(Instruction *FAdd); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 183 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 184 | private: |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 185 | using AddendVect = SmallVector<const FAddend *, 4>; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 186 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 187 | Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 188 | |
| 189 | Value *performFactorization(Instruction *I); |
| 190 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 191 | /// Convert given addend to a Value |
| 192 | Value *createAddendVal(const FAddend &A, bool& NeedNeg); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 193 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 194 | /// Return the number of instructions needed to emit the N-ary addition. |
| 195 | unsigned calcInstrNumber(const AddendVect& Vect); |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 196 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 197 | Value *createFSub(Value *Opnd0, Value *Opnd1); |
| 198 | Value *createFAdd(Value *Opnd0, Value *Opnd1); |
| 199 | Value *createFMul(Value *Opnd0, Value *Opnd1); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 200 | Value *createFDiv(Value *Opnd0, Value *Opnd1); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 201 | Value *createFNeg(Value *V); |
| 202 | Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 203 | void createInstPostProc(Instruction *NewInst, bool NoNumber = false); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 204 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 205 | // Debugging stuff are clustered here. |
| 206 | #ifndef NDEBUG |
| 207 | unsigned CreateInstrNum; |
| 208 | void initCreateInstNum() { CreateInstrNum = 0; } |
| 209 | void incCreateInstNum() { CreateInstrNum++; } |
| 210 | #else |
| 211 | void initCreateInstNum() {} |
| 212 | void incCreateInstNum() {} |
| 213 | #endif |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 214 | |
| 215 | InstCombiner::BuilderTy &Builder; |
| 216 | Instruction *Instr = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 217 | }; |
Eugene Zelenko | ffec81c | 2015-11-04 22:32:32 +0000 | [diff] [blame] | 218 | |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 219 | } // end anonymous namespace |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 220 | |
| 221 | //===----------------------------------------------------------------------===// |
| 222 | // |
| 223 | // Implementation of |
| 224 | // {FAddendCoef, FAddend, FAddition, FAddCombine}. |
| 225 | // |
| 226 | //===----------------------------------------------------------------------===// |
| 227 | FAddendCoef::~FAddendCoef() { |
| 228 | if (BufHasFpVal) |
| 229 | getFpValPtr()->~APFloat(); |
| 230 | } |
| 231 | |
| 232 | void FAddendCoef::set(const APFloat& C) { |
| 233 | APFloat *P = getFpValPtr(); |
| 234 | |
| 235 | if (isInt()) { |
| 236 | // As the buffer is meanless byte stream, we cannot call |
| 237 | // APFloat::operator=(). |
| 238 | new(P) APFloat(C); |
| 239 | } else |
| 240 | *P = C; |
| 241 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 242 | IsFp = BufHasFpVal = true; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 243 | } |
| 244 | |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 245 | void FAddendCoef::convertToFpType(const fltSemantics &Sem) { |
| 246 | if (!isInt()) |
| 247 | return; |
| 248 | |
| 249 | APFloat *P = getFpValPtr(); |
| 250 | if (IntVal > 0) |
| 251 | new(P) APFloat(Sem, IntVal); |
| 252 | else { |
| 253 | new(P) APFloat(Sem, 0 - IntVal); |
| 254 | P->changeSign(); |
| 255 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 256 | IsFp = BufHasFpVal = true; |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 257 | } |
| 258 | |
| 259 | APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { |
| 260 | if (Val >= 0) |
| 261 | return APFloat(Sem, Val); |
| 262 | |
| 263 | APFloat T(Sem, 0 - Val); |
| 264 | T.changeSign(); |
| 265 | |
| 266 | return T; |
| 267 | } |
| 268 | |
| 269 | void FAddendCoef::operator=(const FAddendCoef &That) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 270 | if (That.isInt()) |
| 271 | set(That.IntVal); |
| 272 | else |
| 273 | set(That.getFpVal()); |
| 274 | } |
| 275 | |
| 276 | void FAddendCoef::operator+=(const FAddendCoef &That) { |
| 277 | enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; |
| 278 | if (isInt() == That.isInt()) { |
| 279 | if (isInt()) |
| 280 | IntVal += That.IntVal; |
| 281 | else |
| 282 | getFpVal().add(That.getFpVal(), RndMode); |
| 283 | return; |
| 284 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 285 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 286 | if (isInt()) { |
| 287 | const APFloat &T = That.getFpVal(); |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 288 | convertToFpType(T.getSemantics()); |
| 289 | getFpVal().add(T, RndMode); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 290 | return; |
| 291 | } |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 292 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 293 | APFloat &T = getFpVal(); |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 294 | T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 295 | } |
| 296 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 297 | void FAddendCoef::operator*=(const FAddendCoef &That) { |
| 298 | if (That.isOne()) |
| 299 | return; |
| 300 | |
| 301 | if (That.isMinusOne()) { |
| 302 | negate(); |
| 303 | return; |
| 304 | } |
| 305 | |
| 306 | if (isInt() && That.isInt()) { |
| 307 | int Res = IntVal * (int)That.IntVal; |
| 308 | assert(!insaneIntVal(Res) && "Insane int value"); |
| 309 | IntVal = Res; |
| 310 | return; |
| 311 | } |
| 312 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 313 | const fltSemantics &Semantic = |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 314 | isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); |
| 315 | |
| 316 | if (isInt()) |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 317 | convertToFpType(Semantic); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 318 | APFloat &F0 = getFpVal(); |
| 319 | |
| 320 | if (That.isInt()) |
Shuxin Yang | 389ed4b | 2013-03-25 20:43:41 +0000 | [diff] [blame] | 321 | F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), |
| 322 | APFloat::rmNearestTiesToEven); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 323 | else |
| 324 | F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 325 | } |
| 326 | |
| 327 | void FAddendCoef::negate() { |
| 328 | if (isInt()) |
| 329 | IntVal = 0 - IntVal; |
| 330 | else |
| 331 | getFpVal().changeSign(); |
| 332 | } |
| 333 | |
| 334 | Value *FAddendCoef::getValue(Type *Ty) const { |
| 335 | return isInt() ? |
| 336 | ConstantFP::get(Ty, float(IntVal)) : |
| 337 | ConstantFP::get(Ty->getContext(), getFpVal()); |
| 338 | } |
| 339 | |
| 340 | // The definition of <Val> Addends |
| 341 | // ========================================= |
| 342 | // A + B <1, A>, <1,B> |
| 343 | // A - B <1, A>, <1,B> |
| 344 | // 0 - B <-1, B> |
| 345 | // C * A, <C, A> |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 346 | // A + C <1, A> <C, NULL> |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 347 | // 0 +/- 0 <0, NULL> (corner case) |
| 348 | // |
| 349 | // Legend: A and B are not constant, C is constant |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 350 | unsigned FAddend::drillValueDownOneStep |
| 351 | (Value *Val, FAddend &Addend0, FAddend &Addend1) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 352 | Instruction *I = nullptr; |
| 353 | if (!Val || !(I = dyn_cast<Instruction>(Val))) |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 354 | return 0; |
| 355 | |
| 356 | unsigned Opcode = I->getOpcode(); |
| 357 | |
| 358 | if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { |
| 359 | ConstantFP *C0, *C1; |
| 360 | Value *Opnd0 = I->getOperand(0); |
| 361 | Value *Opnd1 = I->getOperand(1); |
| 362 | if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 363 | Opnd0 = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 364 | |
| 365 | if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 366 | Opnd1 = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 367 | |
| 368 | if (Opnd0) { |
| 369 | if (!C0) |
| 370 | Addend0.set(1, Opnd0); |
| 371 | else |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 372 | Addend0.set(C0, nullptr); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 373 | } |
| 374 | |
| 375 | if (Opnd1) { |
| 376 | FAddend &Addend = Opnd0 ? Addend1 : Addend0; |
| 377 | if (!C1) |
| 378 | Addend.set(1, Opnd1); |
| 379 | else |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 380 | Addend.set(C1, nullptr); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 381 | if (Opcode == Instruction::FSub) |
| 382 | Addend.negate(); |
| 383 | } |
| 384 | |
| 385 | if (Opnd0 || Opnd1) |
| 386 | return Opnd0 && Opnd1 ? 2 : 1; |
| 387 | |
| 388 | // Both operands are zero. Weird! |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 389 | Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 390 | return 1; |
| 391 | } |
| 392 | |
| 393 | if (I->getOpcode() == Instruction::FMul) { |
| 394 | Value *V0 = I->getOperand(0); |
| 395 | Value *V1 = I->getOperand(1); |
| 396 | if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { |
| 397 | Addend0.set(C, V1); |
| 398 | return 1; |
| 399 | } |
| 400 | |
| 401 | if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { |
| 402 | Addend0.set(C, V0); |
| 403 | return 1; |
| 404 | } |
| 405 | } |
| 406 | |
| 407 | return 0; |
| 408 | } |
| 409 | |
| 410 | // Try to break *this* addend into two addends. e.g. Suppose this addend is |
| 411 | // <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, |
| 412 | // i.e. <2.3, X> and <2.3, Y>. |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 413 | unsigned FAddend::drillAddendDownOneStep |
| 414 | (FAddend &Addend0, FAddend &Addend1) const { |
| 415 | if (isConstant()) |
| 416 | return 0; |
| 417 | |
| 418 | unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 419 | if (!BreakNum || Coeff.isOne()) |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 420 | return BreakNum; |
| 421 | |
| 422 | Addend0.Scale(Coeff); |
| 423 | |
| 424 | if (BreakNum == 2) |
| 425 | Addend1.Scale(Coeff); |
| 426 | |
| 427 | return BreakNum; |
| 428 | } |
| 429 | |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 430 | // Try to perform following optimization on the input instruction I. Return the |
| 431 | // simplified expression if was successful; otherwise, return 0. |
| 432 | // |
| 433 | // Instruction "I" is Simplified into |
| 434 | // ------------------------------------------------------- |
| 435 | // (x * y) +/- (x * z) x * (y +/- z) |
| 436 | // (y / x) +/- (z / x) (y +/- z) / x |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 437 | Value *FAddCombine::performFactorization(Instruction *I) { |
| 438 | assert((I->getOpcode() == Instruction::FAdd || |
| 439 | I->getOpcode() == Instruction::FSub) && "Expect add/sub"); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 440 | |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 441 | Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); |
| 442 | Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 443 | |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 444 | if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 445 | return nullptr; |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 446 | |
| 447 | bool isMpy = false; |
| 448 | if (I0->getOpcode() == Instruction::FMul) |
| 449 | isMpy = true; |
| 450 | else if (I0->getOpcode() != Instruction::FDiv) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 451 | return nullptr; |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 452 | |
| 453 | Value *Opnd0_0 = I0->getOperand(0); |
| 454 | Value *Opnd0_1 = I0->getOperand(1); |
| 455 | Value *Opnd1_0 = I1->getOperand(0); |
| 456 | Value *Opnd1_1 = I1->getOperand(1); |
| 457 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 458 | // Input Instr I Factor AddSub0 AddSub1 |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 459 | // ---------------------------------------------- |
| 460 | // (x*y) +/- (x*z) x y z |
| 461 | // (y/x) +/- (z/x) x y z |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 462 | Value *Factor = nullptr; |
| 463 | Value *AddSub0 = nullptr, *AddSub1 = nullptr; |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 464 | |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 465 | if (isMpy) { |
| 466 | if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) |
| 467 | Factor = Opnd0_0; |
| 468 | else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) |
| 469 | Factor = Opnd0_1; |
| 470 | |
| 471 | if (Factor) { |
| 472 | AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; |
| 473 | AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; |
| 474 | } |
| 475 | } else if (Opnd0_1 == Opnd1_1) { |
| 476 | Factor = Opnd0_1; |
| 477 | AddSub0 = Opnd0_0; |
| 478 | AddSub1 = Opnd1_0; |
| 479 | } |
| 480 | |
| 481 | if (!Factor) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 482 | return nullptr; |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 483 | |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 484 | FastMathFlags Flags; |
Sanjay Patel | 629c411 | 2017-11-06 16:27:15 +0000 | [diff] [blame] | 485 | Flags.setFast(); |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 486 | if (I0) Flags &= I->getFastMathFlags(); |
| 487 | if (I1) Flags &= I->getFastMathFlags(); |
| 488 | |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 489 | // Create expression "NewAddSub = AddSub0 +/- AddsSub1" |
| 490 | Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? |
| 491 | createFAdd(AddSub0, AddSub1) : |
| 492 | createFSub(AddSub0, AddSub1); |
| 493 | if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { |
| 494 | const APFloat &F = CFP->getValueAPF(); |
Michael Gottesman | c2af8d6 | 2013-06-26 23:17:31 +0000 | [diff] [blame] | 495 | if (!F.isNormal()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 496 | return nullptr; |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 497 | } else if (Instruction *II = dyn_cast<Instruction>(NewAddSub)) |
| 498 | II->setFastMathFlags(Flags); |
| 499 | |
| 500 | if (isMpy) { |
| 501 | Value *RI = createFMul(Factor, NewAddSub); |
| 502 | if (Instruction *II = dyn_cast<Instruction>(RI)) |
| 503 | II->setFastMathFlags(Flags); |
| 504 | return RI; |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 505 | } |
| 506 | |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 507 | Value *RI = createFDiv(NewAddSub, Factor); |
| 508 | if (Instruction *II = dyn_cast<Instruction>(RI)) |
| 509 | II->setFastMathFlags(Flags); |
| 510 | return RI; |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 511 | } |
| 512 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 513 | Value *FAddCombine::simplify(Instruction *I) { |
Sanjay Patel | 629c411 | 2017-11-06 16:27:15 +0000 | [diff] [blame] | 514 | assert(I->isFast() && "Expected 'fast' instruction"); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 515 | |
| 516 | // Currently we are not able to handle vector type. |
| 517 | if (I->getType()->isVectorTy()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 518 | return nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 519 | |
| 520 | assert((I->getOpcode() == Instruction::FAdd || |
| 521 | I->getOpcode() == Instruction::FSub) && "Expect add/sub"); |
| 522 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 523 | // Save the instruction before calling other member-functions. |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 524 | Instr = I; |
| 525 | |
| 526 | FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; |
| 527 | |
| 528 | unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); |
| 529 | |
| 530 | // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. |
| 531 | unsigned Opnd0_ExpNum = 0; |
| 532 | unsigned Opnd1_ExpNum = 0; |
| 533 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 534 | if (!Opnd0.isConstant()) |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 535 | Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); |
| 536 | |
| 537 | // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. |
| 538 | if (OpndNum == 2 && !Opnd1.isConstant()) |
| 539 | Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); |
| 540 | |
| 541 | // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 |
| 542 | if (Opnd0_ExpNum && Opnd1_ExpNum) { |
| 543 | AddendVect AllOpnds; |
| 544 | AllOpnds.push_back(&Opnd0_0); |
| 545 | AllOpnds.push_back(&Opnd1_0); |
| 546 | if (Opnd0_ExpNum == 2) |
| 547 | AllOpnds.push_back(&Opnd0_1); |
| 548 | if (Opnd1_ExpNum == 2) |
| 549 | AllOpnds.push_back(&Opnd1_1); |
| 550 | |
| 551 | // Compute instruction quota. We should save at least one instruction. |
| 552 | unsigned InstQuota = 0; |
| 553 | |
| 554 | Value *V0 = I->getOperand(0); |
| 555 | Value *V1 = I->getOperand(1); |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 556 | InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 557 | (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; |
| 558 | |
| 559 | if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) |
| 560 | return R; |
| 561 | } |
| 562 | |
| 563 | if (OpndNum != 2) { |
| 564 | // The input instruction is : "I=0.0 +/- V". If the "V" were able to be |
| 565 | // splitted into two addends, say "V = X - Y", the instruction would have |
| 566 | // been optimized into "I = Y - X" in the previous steps. |
| 567 | // |
| 568 | const FAddendCoef &CE = Opnd0.getCoef(); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 569 | return CE.isOne() ? Opnd0.getSymVal() : nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 570 | } |
| 571 | |
| 572 | // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] |
| 573 | if (Opnd1_ExpNum) { |
| 574 | AddendVect AllOpnds; |
| 575 | AllOpnds.push_back(&Opnd0); |
| 576 | AllOpnds.push_back(&Opnd1_0); |
| 577 | if (Opnd1_ExpNum == 2) |
| 578 | AllOpnds.push_back(&Opnd1_1); |
| 579 | |
| 580 | if (Value *R = simplifyFAdd(AllOpnds, 1)) |
| 581 | return R; |
| 582 | } |
| 583 | |
| 584 | // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] |
| 585 | if (Opnd0_ExpNum) { |
| 586 | AddendVect AllOpnds; |
| 587 | AllOpnds.push_back(&Opnd1); |
| 588 | AllOpnds.push_back(&Opnd0_0); |
| 589 | if (Opnd0_ExpNum == 2) |
| 590 | AllOpnds.push_back(&Opnd0_1); |
| 591 | |
| 592 | if (Value *R = simplifyFAdd(AllOpnds, 1)) |
| 593 | return R; |
| 594 | } |
| 595 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 596 | // step 6: Try factorization as the last resort, |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 597 | return performFactorization(I); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 598 | } |
| 599 | |
| 600 | Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 601 | unsigned AddendNum = Addends.size(); |
| 602 | assert(AddendNum <= 4 && "Too many addends"); |
| 603 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 604 | // For saving intermediate results; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 605 | unsigned NextTmpIdx = 0; |
| 606 | FAddend TmpResult[3]; |
| 607 | |
| 608 | // Points to the constant addend of the resulting simplified expression. |
| 609 | // If the resulting expr has constant-addend, this constant-addend is |
| 610 | // desirable to reside at the top of the resulting expression tree. Placing |
| 611 | // constant close to supper-expr(s) will potentially reveal some optimization |
| 612 | // opportunities in super-expr(s). |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 613 | const FAddend *ConstAdd = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 614 | |
| 615 | // Simplified addends are placed <SimpVect>. |
| 616 | AddendVect SimpVect; |
| 617 | |
| 618 | // The outer loop works on one symbolic-value at a time. Suppose the input |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 619 | // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 620 | // The symbolic-values will be processed in this order: x, y, z. |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 621 | for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { |
| 622 | |
| 623 | const FAddend *ThisAddend = Addends[SymIdx]; |
| 624 | if (!ThisAddend) { |
| 625 | // This addend was processed before. |
| 626 | continue; |
| 627 | } |
| 628 | |
| 629 | Value *Val = ThisAddend->getSymVal(); |
| 630 | unsigned StartIdx = SimpVect.size(); |
| 631 | SimpVect.push_back(ThisAddend); |
| 632 | |
| 633 | // The inner loop collects addends sharing same symbolic-value, and these |
| 634 | // addends will be later on folded into a single addend. Following above |
| 635 | // example, if the symbolic value "y" is being processed, the inner loop |
| 636 | // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will |
| 637 | // be later on folded into "<b1+b2, y>". |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 638 | for (unsigned SameSymIdx = SymIdx + 1; |
| 639 | SameSymIdx < AddendNum; SameSymIdx++) { |
| 640 | const FAddend *T = Addends[SameSymIdx]; |
| 641 | if (T && T->getSymVal() == Val) { |
| 642 | // Set null such that next iteration of the outer loop will not process |
| 643 | // this addend again. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 644 | Addends[SameSymIdx] = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 645 | SimpVect.push_back(T); |
| 646 | } |
| 647 | } |
| 648 | |
| 649 | // If multiple addends share same symbolic value, fold them together. |
| 650 | if (StartIdx + 1 != SimpVect.size()) { |
| 651 | FAddend &R = TmpResult[NextTmpIdx ++]; |
| 652 | R = *SimpVect[StartIdx]; |
| 653 | for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) |
| 654 | R += *SimpVect[Idx]; |
| 655 | |
| 656 | // Pop all addends being folded and push the resulting folded addend. |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 657 | SimpVect.resize(StartIdx); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 658 | if (Val) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 659 | if (!R.isZero()) { |
| 660 | SimpVect.push_back(&R); |
| 661 | } |
| 662 | } else { |
| 663 | // Don't push constant addend at this time. It will be the last element |
| 664 | // of <SimpVect>. |
| 665 | ConstAdd = &R; |
| 666 | } |
| 667 | } |
| 668 | } |
| 669 | |
Craig Topper | 5871321 | 2013-07-15 04:27:47 +0000 | [diff] [blame] | 670 | assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) && |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 671 | "out-of-bound access"); |
| 672 | |
| 673 | if (ConstAdd) |
| 674 | SimpVect.push_back(ConstAdd); |
| 675 | |
| 676 | Value *Result; |
| 677 | if (!SimpVect.empty()) |
| 678 | Result = createNaryFAdd(SimpVect, InstrQuota); |
| 679 | else { |
| 680 | // The addition is folded to 0.0. |
| 681 | Result = ConstantFP::get(Instr->getType(), 0.0); |
| 682 | } |
| 683 | |
| 684 | return Result; |
| 685 | } |
| 686 | |
| 687 | Value *FAddCombine::createNaryFAdd |
| 688 | (const AddendVect &Opnds, unsigned InstrQuota) { |
| 689 | assert(!Opnds.empty() && "Expect at least one addend"); |
| 690 | |
| 691 | // Step 1: Check if the # of instructions needed exceeds the quota. |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 692 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 693 | unsigned InstrNeeded = calcInstrNumber(Opnds); |
| 694 | if (InstrNeeded > InstrQuota) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 695 | return nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 696 | |
| 697 | initCreateInstNum(); |
| 698 | |
| 699 | // step 2: Emit the N-ary addition. |
| 700 | // Note that at most three instructions are involved in Fadd-InstCombine: the |
| 701 | // addition in question, and at most two neighboring instructions. |
| 702 | // The resulting optimized addition should have at least one less instruction |
| 703 | // than the original addition expression tree. This implies that the resulting |
| 704 | // N-ary addition has at most two instructions, and we don't need to worry |
| 705 | // about tree-height when constructing the N-ary addition. |
| 706 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 707 | Value *LastVal = nullptr; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 708 | bool LastValNeedNeg = false; |
| 709 | |
| 710 | // Iterate the addends, creating fadd/fsub using adjacent two addends. |
Benjamin Kramer | 135f735 | 2016-06-26 12:28:59 +0000 | [diff] [blame] | 711 | for (const FAddend *Opnd : Opnds) { |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 712 | bool NeedNeg; |
Benjamin Kramer | 135f735 | 2016-06-26 12:28:59 +0000 | [diff] [blame] | 713 | Value *V = createAddendVal(*Opnd, NeedNeg); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 714 | if (!LastVal) { |
| 715 | LastVal = V; |
| 716 | LastValNeedNeg = NeedNeg; |
| 717 | continue; |
| 718 | } |
| 719 | |
| 720 | if (LastValNeedNeg == NeedNeg) { |
| 721 | LastVal = createFAdd(LastVal, V); |
| 722 | continue; |
| 723 | } |
| 724 | |
| 725 | if (LastValNeedNeg) |
| 726 | LastVal = createFSub(V, LastVal); |
| 727 | else |
| 728 | LastVal = createFSub(LastVal, V); |
| 729 | |
| 730 | LastValNeedNeg = false; |
| 731 | } |
| 732 | |
| 733 | if (LastValNeedNeg) { |
| 734 | LastVal = createFNeg(LastVal); |
| 735 | } |
| 736 | |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 737 | #ifndef NDEBUG |
| 738 | assert(CreateInstrNum == InstrNeeded && |
| 739 | "Inconsistent in instruction numbers"); |
| 740 | #endif |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 741 | |
| 742 | return LastVal; |
| 743 | } |
| 744 | |
Sanjay Patel | c242dbb | 2014-12-18 21:11:09 +0000 | [diff] [blame] | 745 | Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 746 | Value *V = Builder.CreateFSub(Opnd0, Opnd1); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 747 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 748 | createInstPostProc(I); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 749 | return V; |
| 750 | } |
| 751 | |
| 752 | Value *FAddCombine::createFNeg(Value *V) { |
Sanjay Patel | ea3c802 | 2014-12-19 16:44:08 +0000 | [diff] [blame] | 753 | Value *Zero = cast<Value>(ConstantFP::getZeroValueForNegation(V->getType())); |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 754 | Value *NewV = createFSub(Zero, V); |
| 755 | if (Instruction *I = dyn_cast<Instruction>(NewV)) |
| 756 | createInstPostProc(I, true); // fneg's don't receive instruction numbers. |
| 757 | return NewV; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 758 | } |
| 759 | |
Sanjay Patel | c242dbb | 2014-12-18 21:11:09 +0000 | [diff] [blame] | 760 | Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 761 | Value *V = Builder.CreateFAdd(Opnd0, Opnd1); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 762 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 763 | createInstPostProc(I); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 764 | return V; |
| 765 | } |
| 766 | |
| 767 | Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 768 | Value *V = Builder.CreateFMul(Opnd0, Opnd1); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 769 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 770 | createInstPostProc(I); |
| 771 | return V; |
| 772 | } |
| 773 | |
| 774 | Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 775 | Value *V = Builder.CreateFDiv(Opnd0, Opnd1); |
Shuxin Yang | 2eca602 | 2013-03-14 18:08:26 +0000 | [diff] [blame] | 776 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 777 | createInstPostProc(I); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 778 | return V; |
| 779 | } |
| 780 | |
Sanjay Patel | c242dbb | 2014-12-18 21:11:09 +0000 | [diff] [blame] | 781 | void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 782 | NewInstr->setDebugLoc(Instr->getDebugLoc()); |
| 783 | |
| 784 | // Keep track of the number of instruction created. |
Owen Anderson | 1664dc8 | 2014-01-20 07:44:53 +0000 | [diff] [blame] | 785 | if (!NoNumber) |
| 786 | incCreateInstNum(); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 787 | |
| 788 | // Propagate fast-math flags |
| 789 | NewInstr->setFastMathFlags(Instr->getFastMathFlags()); |
| 790 | } |
| 791 | |
| 792 | // Return the number of instruction needed to emit the N-ary addition. |
| 793 | // NOTE: Keep this function in sync with createAddendVal(). |
| 794 | unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { |
| 795 | unsigned OpndNum = Opnds.size(); |
| 796 | unsigned InstrNeeded = OpndNum - 1; |
| 797 | |
Jim Grosbach | bdbd734 | 2013-04-05 21:20:12 +0000 | [diff] [blame] | 798 | // The number of addends in the form of "(-1)*x". |
| 799 | unsigned NegOpndNum = 0; |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 800 | |
| 801 | // Adjust the number of instructions needed to emit the N-ary add. |
Benjamin Kramer | 135f735 | 2016-06-26 12:28:59 +0000 | [diff] [blame] | 802 | for (const FAddend *Opnd : Opnds) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 803 | if (Opnd->isConstant()) |
| 804 | continue; |
| 805 | |
Matt Arsenault | 02907f3 | 2017-04-24 17:24:37 +0000 | [diff] [blame] | 806 | // The constant check above is really for a few special constant |
| 807 | // coefficients. |
| 808 | if (isa<UndefValue>(Opnd->getSymVal())) |
| 809 | continue; |
| 810 | |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 811 | const FAddendCoef &CE = Opnd->getCoef(); |
| 812 | if (CE.isMinusOne() || CE.isMinusTwo()) |
| 813 | NegOpndNum++; |
| 814 | |
| 815 | // Let the addend be "c * x". If "c == +/-1", the value of the addend |
| 816 | // is immediately available; otherwise, it needs exactly one instruction |
| 817 | // to evaluate the value. |
| 818 | if (!CE.isMinusOne() && !CE.isOne()) |
| 819 | InstrNeeded++; |
| 820 | } |
| 821 | if (NegOpndNum == OpndNum) |
| 822 | InstrNeeded++; |
| 823 | return InstrNeeded; |
| 824 | } |
| 825 | |
| 826 | // Input Addend Value NeedNeg(output) |
| 827 | // ================================================================ |
| 828 | // Constant C C false |
| 829 | // <+/-1, V> V coefficient is -1 |
| 830 | // <2/-2, V> "fadd V, V" coefficient is -2 |
| 831 | // <C, V> "fmul V, C" false |
| 832 | // |
| 833 | // NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. |
Sanjay Patel | c242dbb | 2014-12-18 21:11:09 +0000 | [diff] [blame] | 834 | Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 835 | const FAddendCoef &Coeff = Opnd.getCoef(); |
| 836 | |
| 837 | if (Opnd.isConstant()) { |
| 838 | NeedNeg = false; |
| 839 | return Coeff.getValue(Instr->getType()); |
| 840 | } |
| 841 | |
| 842 | Value *OpndVal = Opnd.getSymVal(); |
| 843 | |
| 844 | if (Coeff.isMinusOne() || Coeff.isOne()) { |
| 845 | NeedNeg = Coeff.isMinusOne(); |
| 846 | return OpndVal; |
| 847 | } |
| 848 | |
| 849 | if (Coeff.isTwo() || Coeff.isMinusTwo()) { |
| 850 | NeedNeg = Coeff.isMinusTwo(); |
| 851 | return createFAdd(OpndVal, OpndVal); |
| 852 | } |
| 853 | |
| 854 | NeedNeg = false; |
| 855 | return createFMul(OpndVal, Coeff.getValue(Instr->getType())); |
| 856 | } |
| 857 | |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 858 | /// \brief Return true if we can prove that: |
| 859 | /// (sub LHS, RHS) === (sub nsw LHS, RHS) |
| 860 | /// This basically requires proving that the add in the original type would not |
| 861 | /// overflow to change the sign bit or have a carry out. |
| 862 | /// TODO: Handle this for Vectors. |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 863 | bool InstCombiner::willNotOverflowSignedSub(const Value *LHS, |
| 864 | const Value *RHS, |
| 865 | const Instruction &CxtI) const { |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 866 | // If LHS and RHS each have at least two sign bits, the subtraction |
| 867 | // cannot overflow. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 868 | if (ComputeNumSignBits(LHS, 0, &CxtI) > 1 && |
| 869 | ComputeNumSignBits(RHS, 0, &CxtI) > 1) |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 870 | return true; |
| 871 | |
Craig Topper | 8205a1a | 2017-05-24 16:53:07 +0000 | [diff] [blame] | 872 | KnownBits LHSKnown = computeKnownBits(LHS, 0, &CxtI); |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 873 | |
Craig Topper | 8205a1a | 2017-05-24 16:53:07 +0000 | [diff] [blame] | 874 | KnownBits RHSKnown = computeKnownBits(RHS, 0, &CxtI); |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 875 | |
Craig Topper | 957a94c | 2017-04-11 18:47:58 +0000 | [diff] [blame] | 876 | // Subtraction of two 2's complement numbers having identical signs will |
David Majnemer | 54c2ca2 | 2014-12-26 09:10:14 +0000 | [diff] [blame] | 877 | // never overflow. |
Craig Topper | aaef41f | 2017-05-22 00:49:33 +0000 | [diff] [blame] | 878 | if ((LHSKnown.isNegative() && RHSKnown.isNegative()) || |
| 879 | (LHSKnown.isNonNegative() && RHSKnown.isNonNegative())) |
David Majnemer | 54c2ca2 | 2014-12-26 09:10:14 +0000 | [diff] [blame] | 880 | return true; |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 881 | |
David Majnemer | 54c2ca2 | 2014-12-26 09:10:14 +0000 | [diff] [blame] | 882 | // TODO: implement logic similar to checkRippleForAdd |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 883 | return false; |
| 884 | } |
| 885 | |
David Majnemer | 42158f3 | 2014-08-20 07:17:31 +0000 | [diff] [blame] | 886 | /// \brief Return true if we can prove that: |
| 887 | /// (sub LHS, RHS) === (sub nuw LHS, RHS) |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 888 | bool InstCombiner::willNotOverflowUnsignedSub(const Value *LHS, |
| 889 | const Value *RHS, |
| 890 | const Instruction &CxtI) const { |
David Majnemer | 42158f3 | 2014-08-20 07:17:31 +0000 | [diff] [blame] | 891 | // If the LHS is negative and the RHS is non-negative, no unsigned wrap. |
Craig Topper | 1a36b7d | 2017-05-15 06:39:41 +0000 | [diff] [blame] | 892 | KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI); |
| 893 | KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI); |
| 894 | if (LHSKnown.isNegative() && RHSKnown.isNonNegative()) |
David Majnemer | 42158f3 | 2014-08-20 07:17:31 +0000 | [diff] [blame] | 895 | return true; |
| 896 | |
| 897 | return false; |
| 898 | } |
| 899 | |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 900 | // Checks if any operand is negative and we can convert add to sub. |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 901 | // This function checks for following negative patterns |
| 902 | // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) |
| 903 | // ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C)) |
| 904 | // XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even |
Benjamin Kramer | 6cbe670 | 2014-07-07 14:47:51 +0000 | [diff] [blame] | 905 | static Value *checkForNegativeOperand(BinaryOperator &I, |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 906 | InstCombiner::BuilderTy &Builder) { |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 907 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 908 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 909 | // This function creates 2 instructions to replace ADD, we need at least one |
| 910 | // of LHS or RHS to have one use to ensure benefit in transform. |
| 911 | if (!LHS->hasOneUse() && !RHS->hasOneUse()) |
| 912 | return nullptr; |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 913 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 914 | Value *X = nullptr, *Y = nullptr, *Z = nullptr; |
| 915 | const APInt *C1 = nullptr, *C2 = nullptr; |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 916 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 917 | // if ONE is on other side, swap |
| 918 | if (match(RHS, m_Add(m_Value(X), m_One()))) |
| 919 | std::swap(LHS, RHS); |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 920 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 921 | if (match(LHS, m_Add(m_Value(X), m_One()))) { |
| 922 | // if XOR on other side, swap |
| 923 | if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) |
| 924 | std::swap(X, RHS); |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 925 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 926 | if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) { |
| 927 | // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1)) |
| 928 | // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1)) |
| 929 | if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 930 | Value *NewAnd = Builder.CreateAnd(Z, *C1); |
| 931 | return Builder.CreateSub(RHS, NewAnd, "sub"); |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 932 | } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) { |
| 933 | // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1)) |
| 934 | // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1)) |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 935 | Value *NewOr = Builder.CreateOr(Z, ~(*C1)); |
| 936 | return Builder.CreateSub(RHS, NewOr, "sub"); |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 937 | } |
| 938 | } |
| 939 | } |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 940 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 941 | // Restore LHS and RHS |
| 942 | LHS = I.getOperand(0); |
| 943 | RHS = I.getOperand(1); |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 944 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 945 | // if XOR is on other side, swap |
| 946 | if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) |
| 947 | std::swap(LHS, RHS); |
| 948 | |
| 949 | // C2 is ODD |
| 950 | // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2)) |
| 951 | // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2)) |
| 952 | if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1)))) |
| 953 | if (C1->countTrailingZeros() == 0) |
| 954 | if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 955 | Value *NewOr = Builder.CreateOr(Z, ~(*C2)); |
| 956 | return Builder.CreateSub(RHS, NewOr, "sub"); |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 957 | } |
| 958 | return nullptr; |
| 959 | } |
| 960 | |
Sanjay Patel | 8d810fe | 2017-10-13 16:43:58 +0000 | [diff] [blame] | 961 | Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) { |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 962 | Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1); |
Sanjay Patel | 2150651 | 2017-10-13 16:29:38 +0000 | [diff] [blame] | 963 | Constant *Op1C; |
| 964 | if (!match(Op1, m_Constant(Op1C))) |
| 965 | return nullptr; |
| 966 | |
Sanjay Patel | 8d810fe | 2017-10-13 16:43:58 +0000 | [diff] [blame] | 967 | if (Instruction *NV = foldOpWithConstantIntoOperand(Add)) |
| 968 | return NV; |
| 969 | |
Sanjay Patel | 2150651 | 2017-10-13 16:29:38 +0000 | [diff] [blame] | 970 | Value *X; |
Sanjay Patel | f0242de | 2017-10-13 20:29:11 +0000 | [diff] [blame] | 971 | // zext(bool) + C -> bool ? C + 1 : C |
| 972 | if (match(Op0, m_ZExt(m_Value(X))) && |
| 973 | X->getType()->getScalarSizeInBits() == 1) |
Sanjay Patel | 76ed9ea | 2017-10-13 17:00:47 +0000 | [diff] [blame] | 974 | return SelectInst::Create(X, AddOne(Op1C), Op1); |
Sanjay Patel | 2150651 | 2017-10-13 16:29:38 +0000 | [diff] [blame] | 975 | |
Sanjay Patel | f0242de | 2017-10-13 20:29:11 +0000 | [diff] [blame] | 976 | // ~X + C --> (C-1) - X |
| 977 | if (match(Op0, m_Not(m_Value(X)))) |
| 978 | return BinaryOperator::CreateSub(SubOne(Op1C), X); |
| 979 | |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 980 | const APInt *C; |
| 981 | if (!match(Op1, m_APInt(C))) |
| 982 | return nullptr; |
| 983 | |
| 984 | if (C->isSignMask()) { |
| 985 | // If wrapping is not allowed, then the addition must set the sign bit: |
| 986 | // X + (signmask) --> X | signmask |
| 987 | if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap()) |
| 988 | return BinaryOperator::CreateOr(Op0, Op1); |
| 989 | |
| 990 | // If wrapping is allowed, then the addition flips the sign bit of LHS: |
| 991 | // X + (signmask) --> X ^ signmask |
| 992 | return BinaryOperator::CreateXor(Op0, Op1); |
| 993 | } |
| 994 | |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 995 | // Is this add the last step in a convoluted sext? |
| 996 | // add(zext(xor i16 X, -32768), -32768) --> sext X |
Sanjay Patel | 76ed9ea | 2017-10-13 17:00:47 +0000 | [diff] [blame] | 997 | Type *Ty = Add.getType(); |
Sanjay Patel | 2150651 | 2017-10-13 16:29:38 +0000 | [diff] [blame] | 998 | const APInt *C2; |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 999 | if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) && |
| 1000 | C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C) |
| 1001 | return CastInst::Create(Instruction::SExt, X, Ty); |
| 1002 | |
| 1003 | // (add (zext (add nuw X, C2)), C) --> (zext (add nuw X, C2 + C)) |
Sanjay Patel | c419c9f | 2017-10-13 17:47:25 +0000 | [diff] [blame] | 1004 | if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_APInt(C2))))) && |
| 1005 | C->isNegative() && C->sge(-C2->sext(C->getBitWidth()))) { |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 1006 | Constant *NewC = |
| 1007 | ConstantInt::get(X->getType(), *C2 + C->trunc(C2->getBitWidth())); |
| 1008 | return new ZExtInst(Builder.CreateNUWAdd(X, NewC), Ty); |
| 1009 | } |
| 1010 | |
Sanjay Patel | 2f3ead7 | 2017-06-25 14:15:28 +0000 | [diff] [blame] | 1011 | if (C->isOneValue() && Op0->hasOneUse()) { |
| 1012 | // add (sext i1 X), 1 --> zext (not X) |
| 1013 | // TODO: The smallest IR representation is (select X, 0, 1), and that would |
| 1014 | // not require the one-use check. But we need to remove a transform in |
| 1015 | // visitSelect and make sure that IR value tracking for select is equal or |
| 1016 | // better than for these ops. |
| 1017 | if (match(Op0, m_SExt(m_Value(X))) && |
| 1018 | X->getType()->getScalarSizeInBits() == 1) |
| 1019 | return new ZExtInst(Builder.CreateNot(X), Ty); |
| 1020 | |
| 1021 | // Shifts and add used to flip and mask off the low bit: |
| 1022 | // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1 |
| 1023 | const APInt *C3; |
| 1024 | if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) && |
| 1025 | C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) { |
| 1026 | Value *NotX = Builder.CreateNot(X); |
| 1027 | return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1)); |
| 1028 | } |
Sanjay Patel | 2e069f2 | 2017-05-10 13:56:52 +0000 | [diff] [blame] | 1029 | } |
| 1030 | |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 1031 | return nullptr; |
| 1032 | } |
| 1033 | |
Dinesh Dwivedi | adc0773 | 2014-06-27 07:47:35 +0000 | [diff] [blame] | 1034 | Instruction *InstCombiner::visitAdd(BinaryOperator &I) { |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1035 | bool Changed = SimplifyAssociativeOrCommutative(I); |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1036 | if (Value *V = SimplifyVectorOp(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1037 | return replaceInstUsesWith(I, V); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1038 | |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1039 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
Craig Topper | a420562 | 2017-06-09 03:21:29 +0000 | [diff] [blame] | 1040 | if (Value *V = |
| 1041 | SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), |
| 1042 | SQ.getWithInstruction(&I))) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1043 | return replaceInstUsesWith(I, V); |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1044 | |
Eugene Zelenko | 7f0f9bc | 2017-10-24 21:24:53 +0000 | [diff] [blame] | 1045 | // (A*B)+(A*C) -> A*(B+C) etc |
Duncan Sands | fbb9ac3 | 2010-12-22 13:36:08 +0000 | [diff] [blame] | 1046 | if (Value *V = SimplifyUsingDistributiveLaws(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1047 | return replaceInstUsesWith(I, V); |
Duncan Sands | fbb9ac3 | 2010-12-22 13:36:08 +0000 | [diff] [blame] | 1048 | |
Sanjay Patel | 8d810fe | 2017-10-13 16:43:58 +0000 | [diff] [blame] | 1049 | if (Instruction *X = foldAddWithConstant(I)) |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 1050 | return X; |
Sanjay Patel | 53c5c3d | 2017-02-18 22:20:09 +0000 | [diff] [blame] | 1051 | |
Sanjay Patel | 4133d4a | 2017-05-10 00:07:16 +0000 | [diff] [blame] | 1052 | // FIXME: This should be moved into the above helper function to allow these |
Sanjay Patel | 2150651 | 2017-10-13 16:29:38 +0000 | [diff] [blame] | 1053 | // transforms for general constant or constant splat vectors. |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1054 | Type *Ty = I.getType(); |
Sanjay Patel | 79acd2a | 2016-07-16 18:29:26 +0000 | [diff] [blame] | 1055 | if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1056 | Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr; |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1057 | if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1058 | unsigned TySizeBits = Ty->getScalarSizeInBits(); |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1059 | const APInt &RHSVal = CI->getValue(); |
Eli Friedman | a2cc287 | 2010-01-31 04:29:12 +0000 | [diff] [blame] | 1060 | unsigned ExtendAmt = 0; |
| 1061 | // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. |
| 1062 | // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. |
| 1063 | if (XorRHS->getValue() == -RHSVal) { |
| 1064 | if (RHSVal.isPowerOf2()) |
| 1065 | ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; |
| 1066 | else if (XorRHS->getValue().isPowerOf2()) |
| 1067 | ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1068 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1069 | |
Eli Friedman | a2cc287 | 2010-01-31 04:29:12 +0000 | [diff] [blame] | 1070 | if (ExtendAmt) { |
| 1071 | APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); |
Hal Finkel | 60db058 | 2014-09-07 18:57:58 +0000 | [diff] [blame] | 1072 | if (!MaskedValueIsZero(XorLHS, Mask, 0, &I)) |
Eli Friedman | a2cc287 | 2010-01-31 04:29:12 +0000 | [diff] [blame] | 1073 | ExtendAmt = 0; |
| 1074 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1075 | |
Eli Friedman | a2cc287 | 2010-01-31 04:29:12 +0000 | [diff] [blame] | 1076 | if (ExtendAmt) { |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1077 | Constant *ShAmt = ConstantInt::get(Ty, ExtendAmt); |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1078 | Value *NewShl = Builder.CreateShl(XorLHS, ShAmt, "sext"); |
Eli Friedman | a2cc287 | 2010-01-31 04:29:12 +0000 | [diff] [blame] | 1079 | return BinaryOperator::CreateAShr(NewShl, ShAmt); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1080 | } |
Benjamin Kramer | b16bd77 | 2011-12-24 17:31:53 +0000 | [diff] [blame] | 1081 | |
| 1082 | // If this is a xor that was canonicalized from a sub, turn it back into |
| 1083 | // a sub and fuse this add with it. |
| 1084 | if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { |
Craig Topper | 8205a1a | 2017-05-24 16:53:07 +0000 | [diff] [blame] | 1085 | KnownBits LHSKnown = computeKnownBits(XorLHS, 0, &I); |
Craig Topper | b45eabc | 2017-04-26 16:39:58 +0000 | [diff] [blame] | 1086 | if ((XorRHS->getValue() | LHSKnown.Zero).isAllOnesValue()) |
Benjamin Kramer | b16bd77 | 2011-12-24 17:31:53 +0000 | [diff] [blame] | 1087 | return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), |
| 1088 | XorLHS); |
| 1089 | } |
Craig Topper | bcfd2d1 | 2017-04-20 16:56:25 +0000 | [diff] [blame] | 1090 | // (X + signmask) + C could have gotten canonicalized to (X^signmask) + C, |
| 1091 | // transform them into (X + (signmask ^ C)) |
| 1092 | if (XorRHS->getValue().isSignMask()) |
Craig Topper | eafbd57 | 2015-12-21 01:02:28 +0000 | [diff] [blame] | 1093 | return BinaryOperator::CreateAdd(XorLHS, |
| 1094 | ConstantExpr::getXor(XorRHS, CI)); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1095 | } |
| 1096 | } |
| 1097 | |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1098 | if (Ty->isIntOrIntVectorTy(1)) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1099 | return BinaryOperator::CreateXor(LHS, RHS); |
| 1100 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1101 | // X + X --> X << 1 |
Chris Lattner | d406764 | 2011-02-17 20:55:29 +0000 | [diff] [blame] | 1102 | if (LHS == RHS) { |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1103 | auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1)); |
| 1104 | Shl->setHasNoSignedWrap(I.hasNoSignedWrap()); |
| 1105 | Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); |
| 1106 | return Shl; |
Chris Lattner | 5592071 | 2011-02-17 02:23:02 +0000 | [diff] [blame] | 1107 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1108 | |
Sanjay Patel | b869f76 | 2017-10-13 21:28:50 +0000 | [diff] [blame] | 1109 | Value *A, *B; |
| 1110 | if (match(LHS, m_Neg(m_Value(A)))) { |
| 1111 | // -A + -B --> -(A + B) |
| 1112 | if (match(RHS, m_Neg(m_Value(B)))) |
| 1113 | return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B)); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1114 | |
Sanjay Patel | b869f76 | 2017-10-13 21:28:50 +0000 | [diff] [blame] | 1115 | // -A + B --> B - A |
| 1116 | return BinaryOperator::CreateSub(RHS, A); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1117 | } |
| 1118 | |
| 1119 | // A + -B --> A - B |
Sanjay Patel | b869f76 | 2017-10-13 21:28:50 +0000 | [diff] [blame] | 1120 | if (match(RHS, m_Neg(m_Value(B)))) |
| 1121 | return BinaryOperator::CreateSub(LHS, B); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1122 | |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 1123 | if (Value *V = checkForNegativeOperand(I, Builder)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1124 | return replaceInstUsesWith(I, V); |
Dinesh Dwivedi | 562fd75 | 2014-06-19 10:36:52 +0000 | [diff] [blame] | 1125 | |
Sylvestre Ledru | 91ce36c | 2012-09-27 10:14:43 +0000 | [diff] [blame] | 1126 | // A+B --> A|B iff A and B have no bits set in common. |
Daniel Jasper | aec2fa3 | 2016-12-19 08:22:17 +0000 | [diff] [blame] | 1127 | if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT)) |
Jingyue Wu | ca32190 | 2015-05-14 23:53:19 +0000 | [diff] [blame] | 1128 | return BinaryOperator::CreateOr(LHS, RHS); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1129 | |
Sanjay Patel | 79acd2a | 2016-07-16 18:29:26 +0000 | [diff] [blame] | 1130 | // FIXME: We already did a check for ConstantInt RHS above this. |
| 1131 | // FIXME: Is this pattern covered by another fold? No regression tests fail on |
| 1132 | // removal. |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1133 | if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1134 | // (X & FF00) + xx00 -> (X+xx00) & FF00 |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1135 | Value *X; |
| 1136 | ConstantInt *C2; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1137 | if (LHS->hasOneUse() && |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1138 | match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && |
| 1139 | CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { |
| 1140 | // See if all bits from the first bit set in the Add RHS up are included |
| 1141 | // in the mask. First, get the rightmost bit. |
| 1142 | const APInt &AddRHSV = CRHS->getValue(); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1143 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1144 | // Form a mask of all bits from the lowest bit added through the top. |
| 1145 | APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1146 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1147 | // See if the and mask includes all of these bits. |
| 1148 | APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1149 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1150 | if (AddRHSHighBits == AddRHSHighBitsAnd) { |
| 1151 | // Okay, the xform is safe. Insert the new add pronto. |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1152 | Value *NewAdd = Builder.CreateAdd(X, CRHS, LHS->getName()); |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1153 | return BinaryOperator::CreateAnd(NewAdd, C2); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1154 | } |
| 1155 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1156 | } |
| 1157 | |
| 1158 | // add (select X 0 (sub n A)) A --> select X A n |
| 1159 | { |
| 1160 | SelectInst *SI = dyn_cast<SelectInst>(LHS); |
| 1161 | Value *A = RHS; |
| 1162 | if (!SI) { |
| 1163 | SI = dyn_cast<SelectInst>(RHS); |
| 1164 | A = LHS; |
| 1165 | } |
| 1166 | if (SI && SI->hasOneUse()) { |
| 1167 | Value *TV = SI->getTrueValue(); |
| 1168 | Value *FV = SI->getFalseValue(); |
| 1169 | Value *N; |
| 1170 | |
| 1171 | // Can we fold the add into the argument of the select? |
| 1172 | // We check both true and false select arguments for a matching subtract. |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1173 | if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1174 | // Fold the add into the true select value. |
| 1175 | return SelectInst::Create(SI->getCondition(), N, A); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1176 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1177 | if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1178 | // Fold the add into the false select value. |
| 1179 | return SelectInst::Create(SI->getCondition(), A, N); |
| 1180 | } |
| 1181 | } |
| 1182 | |
| 1183 | // Check for (add (sext x), y), see if we can merge this into an |
| 1184 | // integer add followed by a sext. |
| 1185 | if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { |
| 1186 | // (add (sext x), cst) --> (sext (add x, cst')) |
| 1187 | if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1188 | if (LHSConv->hasOneUse()) { |
| 1189 | Constant *CI = |
| 1190 | ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1191 | if (ConstantExpr::getSExt(CI, Ty) == RHSC && |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1192 | willNotOverflowSignedAdd(LHSConv->getOperand(0), CI, I)) { |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1193 | // Insert the new, smaller add. |
| 1194 | Value *NewAdd = |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1195 | Builder.CreateNSWAdd(LHSConv->getOperand(0), CI, "addconv"); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1196 | return new SExtInst(NewAdd, Ty); |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1197 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1198 | } |
| 1199 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1200 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1201 | // (add (sext x), (sext y)) --> (sext (add int x, y)) |
| 1202 | if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { |
Craig Topper | 79e5bc5 | 2017-03-30 22:28:55 +0000 | [diff] [blame] | 1203 | // Only do this if x/y have the same type, if at least one of them has a |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1204 | // single use (so we don't increase the number of sexts), and if the |
| 1205 | // integer add will not overflow. |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1206 | if (LHSConv->getOperand(0)->getType() == |
| 1207 | RHSConv->getOperand(0)->getType() && |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1208 | (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1209 | willNotOverflowSignedAdd(LHSConv->getOperand(0), |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1210 | RHSConv->getOperand(0), I)) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1211 | // Insert the new integer add. |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1212 | Value *NewAdd = Builder.CreateNSWAdd(LHSConv->getOperand(0), |
Chris Lattner | dec6847 | 2010-01-05 20:56:24 +0000 | [diff] [blame] | 1213 | RHSConv->getOperand(0), "addconv"); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1214 | return new SExtInst(NewAdd, Ty); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1215 | } |
| 1216 | } |
| 1217 | } |
| 1218 | |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1219 | // Check for (add (zext x), y), see if we can merge this into an |
| 1220 | // integer add followed by a zext. |
| 1221 | if (auto *LHSConv = dyn_cast<ZExtInst>(LHS)) { |
| 1222 | // (add (zext x), cst) --> (zext (add x, cst')) |
| 1223 | if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { |
| 1224 | if (LHSConv->hasOneUse()) { |
| 1225 | Constant *CI = |
| 1226 | ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1227 | if (ConstantExpr::getZExt(CI, Ty) == RHSC && |
Craig Topper | bb97372 | 2017-05-15 02:44:08 +0000 | [diff] [blame] | 1228 | willNotOverflowUnsignedAdd(LHSConv->getOperand(0), CI, I)) { |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1229 | // Insert the new, smaller add. |
| 1230 | Value *NewAdd = |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1231 | Builder.CreateNUWAdd(LHSConv->getOperand(0), CI, "addconv"); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1232 | return new ZExtInst(NewAdd, Ty); |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1233 | } |
| 1234 | } |
| 1235 | } |
| 1236 | |
| 1237 | // (add (zext x), (zext y)) --> (zext (add int x, y)) |
| 1238 | if (auto *RHSConv = dyn_cast<ZExtInst>(RHS)) { |
Craig Topper | 79e5bc5 | 2017-03-30 22:28:55 +0000 | [diff] [blame] | 1239 | // Only do this if x/y have the same type, if at least one of them has a |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1240 | // single use (so we don't increase the number of zexts), and if the |
| 1241 | // integer add will not overflow. |
| 1242 | if (LHSConv->getOperand(0)->getType() == |
| 1243 | RHSConv->getOperand(0)->getType() && |
| 1244 | (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && |
Craig Topper | bb97372 | 2017-05-15 02:44:08 +0000 | [diff] [blame] | 1245 | willNotOverflowUnsignedAdd(LHSConv->getOperand(0), |
| 1246 | RHSConv->getOperand(0), I)) { |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1247 | // Insert the new integer add. |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1248 | Value *NewAdd = Builder.CreateNUWAdd( |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1249 | LHSConv->getOperand(0), RHSConv->getOperand(0), "addconv"); |
Sanjay Patel | 2118952 | 2017-10-13 18:32:53 +0000 | [diff] [blame] | 1250 | return new ZExtInst(NewAdd, Ty); |
David Majnemer | a1cfd7c | 2016-12-30 00:28:58 +0000 | [diff] [blame] | 1251 | } |
| 1252 | } |
| 1253 | } |
| 1254 | |
David Majnemer | ab07f00 | 2014-08-11 22:32:02 +0000 | [diff] [blame] | 1255 | // (add (xor A, B) (and A, B)) --> (or A, B) |
Sanjay Patel | 28b3aa3 | 2017-10-13 20:12:21 +0000 | [diff] [blame] | 1256 | if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && |
| 1257 | match(RHS, m_c_And(m_Specific(A), m_Specific(B)))) |
| 1258 | return BinaryOperator::CreateOr(A, B); |
Chad Rosier | 7813dce | 2012-04-26 23:29:14 +0000 | [diff] [blame] | 1259 | |
Sanjay Patel | 28b3aa3 | 2017-10-13 20:12:21 +0000 | [diff] [blame] | 1260 | // (add (and A, B) (xor A, B)) --> (or A, B) |
| 1261 | if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && |
| 1262 | match(LHS, m_c_And(m_Specific(A), m_Specific(B)))) |
| 1263 | return BinaryOperator::CreateOr(A, B); |
Chad Rosier | 7813dce | 2012-04-26 23:29:14 +0000 | [diff] [blame] | 1264 | |
David Majnemer | ab07f00 | 2014-08-11 22:32:02 +0000 | [diff] [blame] | 1265 | // (add (or A, B) (and A, B)) --> (add A, B) |
Sanjay Patel | 28b3aa3 | 2017-10-13 20:12:21 +0000 | [diff] [blame] | 1266 | if (match(LHS, m_Or(m_Value(A), m_Value(B))) && |
| 1267 | match(RHS, m_c_And(m_Specific(A), m_Specific(B)))) { |
| 1268 | I.setOperand(0, A); |
| 1269 | I.setOperand(1, B); |
| 1270 | return &I; |
| 1271 | } |
David Majnemer | ab07f00 | 2014-08-11 22:32:02 +0000 | [diff] [blame] | 1272 | |
Sanjay Patel | 28b3aa3 | 2017-10-13 20:12:21 +0000 | [diff] [blame] | 1273 | // (add (and A, B) (or A, B)) --> (add A, B) |
| 1274 | if (match(RHS, m_Or(m_Value(A), m_Value(B))) && |
| 1275 | match(LHS, m_c_And(m_Specific(A), m_Specific(B)))) { |
| 1276 | I.setOperand(0, A); |
| 1277 | I.setOperand(1, B); |
| 1278 | return &I; |
David Majnemer | ab07f00 | 2014-08-11 22:32:02 +0000 | [diff] [blame] | 1279 | } |
| 1280 | |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1281 | // TODO(jingyue): Consider willNotOverflowSignedAdd and |
Craig Topper | bb97372 | 2017-05-15 02:44:08 +0000 | [diff] [blame] | 1282 | // willNotOverflowUnsignedAdd to reduce the number of invocations of |
Jingyue Wu | 33bd53d | 2014-06-17 00:42:07 +0000 | [diff] [blame] | 1283 | // computeKnownBits. |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1284 | if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) { |
Rafael Espindola | d1a2c2d | 2014-06-02 22:01:04 +0000 | [diff] [blame] | 1285 | Changed = true; |
| 1286 | I.setHasNoSignedWrap(true); |
| 1287 | } |
Craig Topper | bb97372 | 2017-05-15 02:44:08 +0000 | [diff] [blame] | 1288 | if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) { |
Jingyue Wu | 33bd53d | 2014-06-17 00:42:07 +0000 | [diff] [blame] | 1289 | Changed = true; |
| 1290 | I.setHasNoUnsignedWrap(true); |
| 1291 | } |
Rafael Espindola | d1a2c2d | 2014-06-02 22:01:04 +0000 | [diff] [blame] | 1292 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1293 | return Changed ? &I : nullptr; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1294 | } |
| 1295 | |
| 1296 | Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { |
Duncan Sands | 641baf1 | 2010-11-13 15:10:37 +0000 | [diff] [blame] | 1297 | bool Changed = SimplifyAssociativeOrCommutative(I); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1298 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
| 1299 | |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1300 | if (Value *V = SimplifyVectorOp(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1301 | return replaceInstUsesWith(I, V); |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1302 | |
Craig Topper | a420562 | 2017-06-09 03:21:29 +0000 | [diff] [blame] | 1303 | if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), |
| 1304 | SQ.getWithInstruction(&I))) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1305 | return replaceInstUsesWith(I, V); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1306 | |
Sanjay Patel | db0938f | 2017-01-10 23:49:07 +0000 | [diff] [blame] | 1307 | if (isa<Constant>(RHS)) |
| 1308 | if (Instruction *FoldedFAdd = foldOpWithConstantIntoOperand(I)) |
| 1309 | return FoldedFAdd; |
Michael Ilseman | e2754dc | 2012-12-14 22:08:26 +0000 | [diff] [blame] | 1310 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1311 | // -A + B --> B - A |
| 1312 | // -A + -B --> -(A + B) |
Owen Anderson | e732166 | 2014-01-16 21:26:02 +0000 | [diff] [blame] | 1313 | if (Value *LHSV = dyn_castFNegVal(LHS)) { |
| 1314 | Instruction *RI = BinaryOperator::CreateFSub(RHS, LHSV); |
| 1315 | RI->copyFastMathFlags(&I); |
| 1316 | return RI; |
| 1317 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1318 | |
| 1319 | // A + -B --> A - B |
| 1320 | if (!isa<Constant>(RHS)) |
Owen Anderson | e732166 | 2014-01-16 21:26:02 +0000 | [diff] [blame] | 1321 | if (Value *V = dyn_castFNegVal(RHS)) { |
| 1322 | Instruction *RI = BinaryOperator::CreateFSub(LHS, V); |
| 1323 | RI->copyFastMathFlags(&I); |
| 1324 | return RI; |
| 1325 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1326 | |
Dan Gohman | 6f34abd | 2010-03-02 01:11:08 +0000 | [diff] [blame] | 1327 | // Check for (fadd double (sitofp x), y), see if we can merge this into an |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1328 | // integer add followed by a promotion. |
| 1329 | if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { |
Artur Pilipenko | 4cc6130 | 2017-03-21 11:32:15 +0000 | [diff] [blame] | 1330 | Value *LHSIntVal = LHSConv->getOperand(0); |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1331 | Type *FPType = LHSConv->getType(); |
| 1332 | |
| 1333 | // TODO: This check is overly conservative. In many cases known bits |
| 1334 | // analysis can tell us that the result of the addition has less significant |
| 1335 | // bits than the integer type can hold. |
| 1336 | auto IsValidPromotion = [](Type *FTy, Type *ITy) { |
Artur Pilipenko | 0632bdc | 2017-04-22 07:24:52 +0000 | [diff] [blame] | 1337 | Type *FScalarTy = FTy->getScalarType(); |
| 1338 | Type *IScalarTy = ITy->getScalarType(); |
| 1339 | |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1340 | // Do we have enough bits in the significand to represent the result of |
| 1341 | // the integer addition? |
| 1342 | unsigned MaxRepresentableBits = |
Artur Pilipenko | 0632bdc | 2017-04-22 07:24:52 +0000 | [diff] [blame] | 1343 | APFloat::semanticsPrecision(FScalarTy->getFltSemantics()); |
| 1344 | return IScalarTy->getIntegerBitWidth() <= MaxRepresentableBits; |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1345 | }; |
Artur Pilipenko | 4cc6130 | 2017-03-21 11:32:15 +0000 | [diff] [blame] | 1346 | |
Dan Gohman | 6f34abd | 2010-03-02 01:11:08 +0000 | [diff] [blame] | 1347 | // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1348 | // ... if the constant fits in the integer value. This is useful for things |
| 1349 | // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer |
| 1350 | // requires a constant pool load, and generally allows the add to be better |
| 1351 | // instcombined. |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1352 | if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) |
| 1353 | if (IsValidPromotion(FPType, LHSIntVal->getType())) { |
| 1354 | Constant *CI = |
| 1355 | ConstantExpr::getFPToSI(CFP, LHSIntVal->getType()); |
| 1356 | if (LHSConv->hasOneUse() && |
| 1357 | ConstantExpr::getSIToFP(CI, I.getType()) == CFP && |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1358 | willNotOverflowSignedAdd(LHSIntVal, CI, I)) { |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1359 | // Insert the new integer add. |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1360 | Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, CI, "addconv"); |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1361 | return new SIToFPInst(NewAdd, I.getType()); |
| 1362 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1363 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1364 | |
Dan Gohman | 6f34abd | 2010-03-02 01:11:08 +0000 | [diff] [blame] | 1365 | // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1366 | if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { |
Artur Pilipenko | 4cc6130 | 2017-03-21 11:32:15 +0000 | [diff] [blame] | 1367 | Value *RHSIntVal = RHSConv->getOperand(0); |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1368 | // It's enough to check LHS types only because we require int types to |
| 1369 | // be the same for this transform. |
| 1370 | if (IsValidPromotion(FPType, LHSIntVal->getType())) { |
| 1371 | // Only do this if x/y have the same type, if at least one of them has a |
| 1372 | // single use (so we don't increase the number of int->fp conversions), |
| 1373 | // and if the integer add will not overflow. |
| 1374 | if (LHSIntVal->getType() == RHSIntVal->getType() && |
| 1375 | (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1376 | willNotOverflowSignedAdd(LHSIntVal, RHSIntVal, I)) { |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1377 | // Insert the new integer add. |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1378 | Value *NewAdd = Builder.CreateNSWAdd(LHSIntVal, RHSIntVal, "addconv"); |
Artur Pilipenko | 134d94f | 2017-04-21 18:45:25 +0000 | [diff] [blame] | 1379 | return new SIToFPInst(NewAdd, I.getType()); |
| 1380 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1381 | } |
| 1382 | } |
| 1383 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1384 | |
Quentin Colombet | aa103b3 | 2017-09-20 17:32:16 +0000 | [diff] [blame] | 1385 | // Handle specials cases for FAdd with selects feeding the operation |
| 1386 | if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS)) |
| 1387 | return replaceInstUsesWith(I, V); |
Jean-Luc Duprat | 3e4fc3e | 2013-05-06 16:55:50 +0000 | [diff] [blame] | 1388 | |
Sanjay Patel | 629c411 | 2017-11-06 16:27:15 +0000 | [diff] [blame] | 1389 | if (I.isFast()) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 1390 | if (Value *V = FAddCombine(Builder).simplify(&I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1391 | return replaceInstUsesWith(I, V); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 1392 | } |
| 1393 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1394 | return Changed ? &I : nullptr; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1395 | } |
| 1396 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1397 | /// Optimize pointer differences into the same array into a size. Consider: |
| 1398 | /// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer |
| 1399 | /// operands to the ptrtoint instructions for the LHS/RHS of the subtract. |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1400 | Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, |
Chris Lattner | 229907c | 2011-07-18 04:54:35 +0000 | [diff] [blame] | 1401 | Type *Ty) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1402 | // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize |
| 1403 | // this. |
| 1404 | bool Swapped = false; |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1405 | GEPOperator *GEP1 = nullptr, *GEP2 = nullptr; |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1406 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1407 | // For now we require one side to be the base pointer "A" or a constant |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1408 | // GEP derived from it. |
| 1409 | if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1410 | // (gep X, ...) - X |
| 1411 | if (LHSGEP->getOperand(0) == RHS) { |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1412 | GEP1 = LHSGEP; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1413 | Swapped = false; |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1414 | } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { |
| 1415 | // (gep X, ...) - (gep X, ...) |
| 1416 | if (LHSGEP->getOperand(0)->stripPointerCasts() == |
| 1417 | RHSGEP->getOperand(0)->stripPointerCasts()) { |
| 1418 | GEP2 = RHSGEP; |
| 1419 | GEP1 = LHSGEP; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1420 | Swapped = false; |
| 1421 | } |
| 1422 | } |
| 1423 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1424 | |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1425 | if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1426 | // X - (gep X, ...) |
| 1427 | if (RHSGEP->getOperand(0) == LHS) { |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1428 | GEP1 = RHSGEP; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1429 | Swapped = true; |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1430 | } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { |
| 1431 | // (gep X, ...) - (gep X, ...) |
| 1432 | if (RHSGEP->getOperand(0)->stripPointerCasts() == |
| 1433 | LHSGEP->getOperand(0)->stripPointerCasts()) { |
| 1434 | GEP2 = LHSGEP; |
| 1435 | GEP1 = RHSGEP; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1436 | Swapped = true; |
| 1437 | } |
| 1438 | } |
| 1439 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1440 | |
Hiroshi Yamauchi | 6085521 | 2017-07-27 18:27:11 +0000 | [diff] [blame] | 1441 | if (!GEP1) |
| 1442 | // No GEP found. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1443 | return nullptr; |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1444 | |
Hiroshi Yamauchi | 6085521 | 2017-07-27 18:27:11 +0000 | [diff] [blame] | 1445 | if (GEP2) { |
| 1446 | // (gep X, ...) - (gep X, ...) |
| 1447 | // |
| 1448 | // Avoid duplicating the arithmetic if there are more than one non-constant |
| 1449 | // indices between the two GEPs and either GEP has a non-constant index and |
| 1450 | // multiple users. If zero non-constant index, the result is a constant and |
| 1451 | // there is no duplication. If one non-constant index, the result is an add |
| 1452 | // or sub with a constant, which is no larger than the original code, and |
| 1453 | // there's no duplicated arithmetic, even if either GEP has multiple |
| 1454 | // users. If more than one non-constant indices combined, as long as the GEP |
| 1455 | // with at least one non-constant index doesn't have multiple users, there |
| 1456 | // is no duplication. |
| 1457 | unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices(); |
| 1458 | unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices(); |
| 1459 | if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 && |
| 1460 | ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) || |
| 1461 | (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) { |
| 1462 | return nullptr; |
| 1463 | } |
| 1464 | } |
| 1465 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1466 | // Emit the offset of the GEP and an intptr_t. |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1467 | Value *Result = EmitGEPOffset(GEP1); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1468 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1469 | // If we had a constant expression GEP on the other side offsetting the |
| 1470 | // pointer, subtract it from the offset we have. |
Benjamin Kramer | 7746eb6 | 2012-02-20 14:34:57 +0000 | [diff] [blame] | 1471 | if (GEP2) { |
| 1472 | Value *Offset = EmitGEPOffset(GEP2); |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1473 | Result = Builder.CreateSub(Result, Offset); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1474 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1475 | |
| 1476 | // If we have p - gep(p, ...) then we have to negate the result. |
| 1477 | if (Swapped) |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1478 | Result = Builder.CreateNeg(Result, "diff.neg"); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1479 | |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1480 | return Builder.CreateIntCast(Result, Ty, true); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1481 | } |
| 1482 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1483 | Instruction *InstCombiner::visitSub(BinaryOperator &I) { |
| 1484 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
| 1485 | |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1486 | if (Value *V = SimplifyVectorOp(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1487 | return replaceInstUsesWith(I, V); |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1488 | |
Craig Topper | a420562 | 2017-06-09 03:21:29 +0000 | [diff] [blame] | 1489 | if (Value *V = |
| 1490 | SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), |
| 1491 | SQ.getWithInstruction(&I))) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1492 | return replaceInstUsesWith(I, V); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1493 | |
Duncan Sands | fbb9ac3 | 2010-12-22 13:36:08 +0000 | [diff] [blame] | 1494 | // (A*B)-(A*C) -> A*(B-C) etc |
| 1495 | if (Value *V = SimplifyUsingDistributiveLaws(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1496 | return replaceInstUsesWith(I, V); |
Duncan Sands | fbb9ac3 | 2010-12-22 13:36:08 +0000 | [diff] [blame] | 1497 | |
David Majnemer | a92687d | 2014-07-31 04:49:29 +0000 | [diff] [blame] | 1498 | // If this is a 'B = x-(-A)', change to B = x+A. |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1499 | if (Value *V = dyn_castNegVal(Op1)) { |
| 1500 | BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); |
David Majnemer | a92687d | 2014-07-31 04:49:29 +0000 | [diff] [blame] | 1501 | |
| 1502 | if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) { |
| 1503 | assert(BO->getOpcode() == Instruction::Sub && |
| 1504 | "Expected a subtraction operator!"); |
| 1505 | if (BO->hasNoSignedWrap() && I.hasNoSignedWrap()) |
| 1506 | Res->setHasNoSignedWrap(true); |
David Majnemer | 0e6c986 | 2014-08-22 16:41:23 +0000 | [diff] [blame] | 1507 | } else { |
| 1508 | if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap()) |
| 1509 | Res->setHasNoSignedWrap(true); |
David Majnemer | a92687d | 2014-07-31 04:49:29 +0000 | [diff] [blame] | 1510 | } |
| 1511 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1512 | return Res; |
| 1513 | } |
| 1514 | |
Craig Topper | fde4723 | 2017-07-09 07:04:03 +0000 | [diff] [blame] | 1515 | if (I.getType()->isIntOrIntVectorTy(1)) |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1516 | return BinaryOperator::CreateXor(Op0, Op1); |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1517 | |
| 1518 | // Replace (-1 - A) with (~A). |
| 1519 | if (match(Op0, m_AllOnes())) |
| 1520 | return BinaryOperator::CreateNot(Op1); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1521 | |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1522 | if (Constant *C = dyn_cast<Constant>(Op0)) { |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1523 | // C - ~X == X + (1+C) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1524 | Value *X = nullptr; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1525 | if (match(Op1, m_Not(m_Value(X)))) |
| 1526 | return BinaryOperator::CreateAdd(X, AddOne(C)); |
| 1527 | |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1528 | // Try to fold constant sub into select arguments. |
| 1529 | if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) |
| 1530 | if (Instruction *R = FoldOpIntoSelect(I, SI)) |
| 1531 | return R; |
| 1532 | |
Craig Topper | fb71b7d | 2017-04-14 19:20:12 +0000 | [diff] [blame] | 1533 | // Try to fold constant sub into PHI values. |
| 1534 | if (PHINode *PN = dyn_cast<PHINode>(Op1)) |
| 1535 | if (Instruction *R = foldOpIntoPhi(I, PN)) |
| 1536 | return R; |
| 1537 | |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1538 | // C-(X+C2) --> (C-C2)-X |
| 1539 | Constant *C2; |
| 1540 | if (match(Op1, m_Add(m_Value(X), m_Constant(C2)))) |
| 1541 | return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); |
| 1542 | |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1543 | // Fold (sub 0, (zext bool to B)) --> (sext bool to B) |
| 1544 | if (C->isNullValue() && match(Op1, m_ZExt(m_Value(X)))) |
Craig Topper | fde4723 | 2017-07-09 07:04:03 +0000 | [diff] [blame] | 1545 | if (X->getType()->isIntOrIntVectorTy(1)) |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1546 | return CastInst::CreateSExtOrBitCast(X, Op1->getType()); |
| 1547 | |
| 1548 | // Fold (sub 0, (sext bool to B)) --> (zext bool to B) |
| 1549 | if (C->isNullValue() && match(Op1, m_SExt(m_Value(X)))) |
Craig Topper | fde4723 | 2017-07-09 07:04:03 +0000 | [diff] [blame] | 1550 | if (X->getType()->isIntOrIntVectorTy(1)) |
Benjamin Kramer | 72196f3 | 2014-01-19 15:24:22 +0000 | [diff] [blame] | 1551 | return CastInst::CreateZExtOrBitCast(X, Op1->getType()); |
| 1552 | } |
| 1553 | |
Sanjay Patel | 6d6eca5 | 2016-10-14 16:31:54 +0000 | [diff] [blame] | 1554 | const APInt *Op0C; |
| 1555 | if (match(Op0, m_APInt(Op0C))) { |
| 1556 | unsigned BitWidth = I.getType()->getScalarSizeInBits(); |
| 1557 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1558 | // -(X >>u 31) -> (X >>s 31) |
| 1559 | // -(X >>s 31) -> (X >>u 31) |
Craig Topper | 73ba1c8 | 2017-06-07 07:40:37 +0000 | [diff] [blame] | 1560 | if (Op0C->isNullValue()) { |
David Majnemer | 72a643d | 2014-11-03 05:53:55 +0000 | [diff] [blame] | 1561 | Value *X; |
Sanjay Patel | 6d6eca5 | 2016-10-14 16:31:54 +0000 | [diff] [blame] | 1562 | const APInt *ShAmt; |
| 1563 | if (match(Op1, m_LShr(m_Value(X), m_APInt(ShAmt))) && |
| 1564 | *ShAmt == BitWidth - 1) { |
| 1565 | Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1); |
| 1566 | return BinaryOperator::CreateAShr(X, ShAmtOp); |
| 1567 | } |
| 1568 | if (match(Op1, m_AShr(m_Value(X), m_APInt(ShAmt))) && |
| 1569 | *ShAmt == BitWidth - 1) { |
| 1570 | Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1); |
| 1571 | return BinaryOperator::CreateLShr(X, ShAmtOp); |
| 1572 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1573 | } |
Matthias Braun | ec68334 | 2015-04-30 22:04:26 +0000 | [diff] [blame] | 1574 | |
| 1575 | // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known |
| 1576 | // zero. |
Craig Topper | b4da684 | 2017-04-06 21:06:03 +0000 | [diff] [blame] | 1577 | if (Op0C->isMask()) { |
Craig Topper | 8205a1a | 2017-05-24 16:53:07 +0000 | [diff] [blame] | 1578 | KnownBits RHSKnown = computeKnownBits(Op1, 0, &I); |
Craig Topper | b45eabc | 2017-04-26 16:39:58 +0000 | [diff] [blame] | 1579 | if ((*Op0C | RHSKnown.Zero).isAllOnesValue()) |
Sanjay Patel | 6d6eca5 | 2016-10-14 16:31:54 +0000 | [diff] [blame] | 1580 | return BinaryOperator::CreateXor(Op1, Op0); |
Matthias Braun | ec68334 | 2015-04-30 22:04:26 +0000 | [diff] [blame] | 1581 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1582 | } |
| 1583 | |
David Majnemer | 72a643d | 2014-11-03 05:53:55 +0000 | [diff] [blame] | 1584 | { |
Suyog Sarda | cba4b1d | 2014-10-08 08:37:49 +0000 | [diff] [blame] | 1585 | Value *Y; |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1586 | // X-(X+Y) == -Y X-(Y+X) == -Y |
Craig Topper | 98851ad | 2017-04-10 16:59:40 +0000 | [diff] [blame] | 1587 | if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y)))) |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1588 | return BinaryOperator::CreateNeg(Y); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1589 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1590 | // (X-Y)-X == -Y |
| 1591 | if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) |
| 1592 | return BinaryOperator::CreateNeg(Y); |
| 1593 | } |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1594 | |
Hiroshi Yamauchi | 0445e31 | 2017-07-26 21:54:43 +0000 | [diff] [blame] | 1595 | // (sub (or A, B), (xor A, B)) --> (and A, B) |
David Majnemer | 312c3e5 | 2014-10-19 08:32:32 +0000 | [diff] [blame] | 1596 | { |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1597 | Value *A, *B; |
David Majnemer | 312c3e5 | 2014-10-19 08:32:32 +0000 | [diff] [blame] | 1598 | if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1599 | match(Op0, m_c_Or(m_Specific(A), m_Specific(B)))) |
David Majnemer | 312c3e5 | 2014-10-19 08:32:32 +0000 | [diff] [blame] | 1600 | return BinaryOperator::CreateAnd(A, B); |
| 1601 | } |
| 1602 | |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1603 | { |
| 1604 | Value *Y; |
David Majnemer | 72a643d | 2014-11-03 05:53:55 +0000 | [diff] [blame] | 1605 | // ((X | Y) - X) --> (~X & Y) |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1606 | if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1))))) |
David Majnemer | 72a643d | 2014-11-03 05:53:55 +0000 | [diff] [blame] | 1607 | return BinaryOperator::CreateAnd( |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1608 | Y, Builder.CreateNot(Op1, Op1->getName() + ".not")); |
David Majnemer | 72a643d | 2014-11-03 05:53:55 +0000 | [diff] [blame] | 1609 | } |
| 1610 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1611 | if (Op1->hasOneUse()) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1612 | Value *X = nullptr, *Y = nullptr, *Z = nullptr; |
| 1613 | Constant *C = nullptr; |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1614 | |
| 1615 | // (X - (Y - Z)) --> (X + (Z - Y)). |
| 1616 | if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) |
| 1617 | return BinaryOperator::CreateAdd(Op0, |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1618 | Builder.CreateSub(Z, Y, Op1->getName())); |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1619 | |
| 1620 | // (X - (X & Y)) --> (X & ~Y) |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1621 | if (match(Op1, m_c_And(m_Value(Y), m_Specific(Op0)))) |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1622 | return BinaryOperator::CreateAnd(Op0, |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1623 | Builder.CreateNot(Y, Y->getName() + ".not")); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1624 | |
David Majnemer | bdeef60 | 2014-07-02 06:07:09 +0000 | [diff] [blame] | 1625 | // 0 - (X sdiv C) -> (X sdiv -C) provided the negation doesn't overflow. |
| 1626 | if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) && |
David Majnemer | 0e6c986 | 2014-08-22 16:41:23 +0000 | [diff] [blame] | 1627 | C->isNotMinSignedValue() && !C->isOneValue()) |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1628 | return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); |
| 1629 | |
| 1630 | // 0 - (X << Y) -> (-X << Y) when X is freely negatable. |
| 1631 | if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) |
| 1632 | if (Value *XNeg = dyn_castNegVal(X)) |
| 1633 | return BinaryOperator::CreateShl(XNeg, Y); |
| 1634 | |
Sanjay Patel | c6c5965 | 2016-10-14 15:24:31 +0000 | [diff] [blame] | 1635 | // Subtracting -1/0 is the same as adding 1/0: |
| 1636 | // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y) |
| 1637 | // 'nuw' is dropped in favor of the canonical form. |
| 1638 | if (match(Op1, m_SExt(m_Value(Y))) && |
| 1639 | Y->getType()->getScalarSizeInBits() == 1) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1640 | Value *Zext = Builder.CreateZExt(Y, I.getType()); |
Sanjay Patel | c6c5965 | 2016-10-14 15:24:31 +0000 | [diff] [blame] | 1641 | BinaryOperator *Add = BinaryOperator::CreateAdd(Op0, Zext); |
| 1642 | Add->setHasNoSignedWrap(I.hasNoSignedWrap()); |
| 1643 | return Add; |
| 1644 | } |
| 1645 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1646 | // X - A*-B -> X + A*B |
| 1647 | // X - -A*B -> X + A*B |
| 1648 | Value *A, *B; |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1649 | Constant *CI; |
| 1650 | if (match(Op1, m_c_Mul(m_Value(A), m_Neg(m_Value(B))))) |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1651 | return BinaryOperator::CreateAdd(Op0, Builder.CreateMul(A, B)); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1652 | |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1653 | // X - A*CI -> X + A*-CI |
Craig Topper | 0d830ff | 2017-04-10 18:09:25 +0000 | [diff] [blame] | 1654 | // No need to handle commuted multiply because multiply handling will |
| 1655 | // ensure constant will be move to the right hand side. |
| 1656 | if (match(Op1, m_Mul(m_Value(A), m_Constant(CI)))) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1657 | Value *NewMul = Builder.CreateMul(A, ConstantExpr::getNeg(CI)); |
Chris Lattner | 7d0e43f | 2011-02-10 05:14:58 +0000 | [diff] [blame] | 1658 | return BinaryOperator::CreateAdd(Op0, NewMul); |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1659 | } |
| 1660 | } |
| 1661 | |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1662 | // Optimize pointer differences into the same array into a size. Consider: |
| 1663 | // &A[10] - &A[0]: we should compile this to "10". |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1664 | Value *LHSOp, *RHSOp; |
| 1665 | if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && |
| 1666 | match(Op1, m_PtrToInt(m_Value(RHSOp)))) |
| 1667 | if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1668 | return replaceInstUsesWith(I, Res); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1669 | |
Mehdi Amini | a28d91d | 2015-03-10 02:37:25 +0000 | [diff] [blame] | 1670 | // trunc(p)-trunc(q) -> trunc(p-q) |
| 1671 | if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && |
| 1672 | match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) |
| 1673 | if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1674 | return replaceInstUsesWith(I, Res); |
Michael Ilseman | 9fc0f25 | 2012-12-12 20:57:53 +0000 | [diff] [blame] | 1675 | |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 1676 | bool Changed = false; |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1677 | if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) { |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 1678 | Changed = true; |
| 1679 | I.setHasNoSignedWrap(true); |
| 1680 | } |
Craig Topper | 2b1fc32 | 2017-05-22 06:25:31 +0000 | [diff] [blame] | 1681 | if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) { |
David Majnemer | 42158f3 | 2014-08-20 07:17:31 +0000 | [diff] [blame] | 1682 | Changed = true; |
| 1683 | I.setHasNoUnsignedWrap(true); |
| 1684 | } |
David Majnemer | 57d5bc8 | 2014-08-19 23:36:30 +0000 | [diff] [blame] | 1685 | |
| 1686 | return Changed ? &I : nullptr; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1687 | } |
| 1688 | |
| 1689 | Instruction *InstCombiner::visitFSub(BinaryOperator &I) { |
| 1690 | Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); |
| 1691 | |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1692 | if (Value *V = SimplifyVectorOp(I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1693 | return replaceInstUsesWith(I, V); |
Serge Pavlov | 9ef66a8 | 2014-05-11 08:46:12 +0000 | [diff] [blame] | 1694 | |
Craig Topper | a420562 | 2017-06-09 03:21:29 +0000 | [diff] [blame] | 1695 | if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), |
| 1696 | SQ.getWithInstruction(&I))) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1697 | return replaceInstUsesWith(I, V); |
Michael Ilseman | d5787be | 2012-12-12 00:28:32 +0000 | [diff] [blame] | 1698 | |
Sanjay Patel | e68f715 | 2014-12-31 22:14:05 +0000 | [diff] [blame] | 1699 | // fsub nsz 0, X ==> fsub nsz -0.0, X |
| 1700 | if (I.getFastMathFlags().noSignedZeros() && match(Op0, m_Zero())) { |
| 1701 | // Subtraction from -0.0 is the canonical form of fneg. |
| 1702 | Instruction *NewI = BinaryOperator::CreateFNeg(Op1); |
| 1703 | NewI->copyFastMathFlags(&I); |
| 1704 | return NewI; |
| 1705 | } |
| 1706 | |
Stephen Lin | a9b57f6 | 2013-07-20 07:13:13 +0000 | [diff] [blame] | 1707 | if (isa<Constant>(Op0)) |
| 1708 | if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) |
| 1709 | if (Instruction *NV = FoldOpIntoSelect(I, SI)) |
| 1710 | return NV; |
| 1711 | |
Owen Anderson | e37c2e4 | 2013-07-26 21:40:29 +0000 | [diff] [blame] | 1712 | // If this is a 'B = x-(-A)', change to B = x+A, potentially looking |
| 1713 | // through FP extensions/truncations along the way. |
Owen Anderson | c7be519 | 2013-07-30 23:53:17 +0000 | [diff] [blame] | 1714 | if (Value *V = dyn_castFNegVal(Op1)) { |
| 1715 | Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V); |
| 1716 | NewI->copyFastMathFlags(&I); |
| 1717 | return NewI; |
| 1718 | } |
Owen Anderson | e37c2e4 | 2013-07-26 21:40:29 +0000 | [diff] [blame] | 1719 | if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) { |
| 1720 | if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1721 | Value *NewTrunc = Builder.CreateFPTrunc(V, I.getType()); |
Owen Anderson | c7be519 | 2013-07-30 23:53:17 +0000 | [diff] [blame] | 1722 | Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc); |
| 1723 | NewI->copyFastMathFlags(&I); |
| 1724 | return NewI; |
Owen Anderson | e37c2e4 | 2013-07-26 21:40:29 +0000 | [diff] [blame] | 1725 | } |
| 1726 | } else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) { |
| 1727 | if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) { |
Craig Topper | bb4069e | 2017-07-07 23:16:26 +0000 | [diff] [blame] | 1728 | Value *NewExt = Builder.CreateFPExt(V, I.getType()); |
Owen Anderson | c7be519 | 2013-07-30 23:53:17 +0000 | [diff] [blame] | 1729 | Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt); |
| 1730 | NewI->copyFastMathFlags(&I); |
| 1731 | return NewI; |
Owen Anderson | e37c2e4 | 2013-07-26 21:40:29 +0000 | [diff] [blame] | 1732 | } |
| 1733 | } |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1734 | |
Quentin Colombet | aa103b3 | 2017-09-20 17:32:16 +0000 | [diff] [blame] | 1735 | // Handle specials cases for FSub with selects feeding the operation |
| 1736 | if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1)) |
| 1737 | return replaceInstUsesWith(I, V); |
| 1738 | |
Sanjay Patel | 629c411 | 2017-11-06 16:27:15 +0000 | [diff] [blame] | 1739 | if (I.isFast()) { |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 1740 | if (Value *V = FAddCombine(Builder).simplify(&I)) |
Sanjay Patel | 4b19880 | 2016-02-01 22:23:39 +0000 | [diff] [blame] | 1741 | return replaceInstUsesWith(I, V); |
Shuxin Yang | 37a1efe | 2012-12-18 23:10:12 +0000 | [diff] [blame] | 1742 | } |
| 1743 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1744 | return nullptr; |
Chris Lattner | 82aa888 | 2010-01-05 07:18:46 +0000 | [diff] [blame] | 1745 | } |