153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===- InstCombineAddSub.cpp ----------------------------------------------===// 253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// The LLVM Compiler Infrastructure 453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// This file is distributed under the University of Illinois Open Source 653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// License. See LICENSE.TXT for details. 753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===----------------------------------------------------------------------===// 953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 1053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// This file implements the visit functions for add, fadd, sub, and fsub. 1153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 1253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===----------------------------------------------------------------------===// 1353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "InstCombine.h" 15b9df53a40b22c74ce3f3a7b4a7c0676a38cf5e73Craig Topper#include "llvm/ADT/STLExtras.h" 1653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Analysis/InstructionSimplify.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 1853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 1953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Support/PatternMatch.h" 2053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace llvm; 2153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace PatternMatch; 2253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangnamespace { 241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Class representing coefficient of floating-point addend. 261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// This class needs to be highly efficient, which is especially true for 271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// the constructor. As of I write this comment, the cost of the default 2803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// perform write-merging). 3003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach /// 311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddendCoef { 321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The constructor has to initialize a APFloat, which is uncessary for 341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // most addends which have coefficient either 1 or -1. So, the constructor 351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is expensive. In order to avoid the cost of the constructor, we should 361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // reuse some instances whenever possible. The pre-created instances 371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // FAddCombine::Add[0-5] embodies this idea. 381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ~FAddendCoef(); 4103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(short C) { 431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!insaneIntVal(C) && "Insane coefficient"); 441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IsFp = false; IntVal = C; 451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const APFloat& C); 48c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void negate(); 5003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *getValue(Type *) const; 5303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If possible, don't define operator+/operator- etc because these 551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // operators inevitably call FAddendCoef's constructor which is not cheap. 561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator=(const FAddendCoef &A); 571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator+=(const FAddendCoef &A); 581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator-=(const FAddendCoef &A); 591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator*=(const FAddendCoef &S); 6003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isOne() const { return isInt() && IntVal == 1; } 621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isTwo() const { return isInt() && IntVal == 2; } 631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isMinusOne() const { return isInt() && IntVal == -1; } 641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isMinusTwo() const { return isInt() && IntVal == -2; } 6503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool insaneIntVal(int V) { return V > 4 || V < -4; } 681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat *getFpValPtr(void) 69d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 704ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene const APFloat *getFpValPtr(void) const 714ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &getFpVal(void) const { 741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(IsFp && BufHasFpVal && "Incorret state"); 754ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene return *getFpValPtr(); 761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach APFloat &getFpVal(void) { 7903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach assert(IsFp && BufHasFpVal && "Incorret state"); 8003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach return *getFpValPtr(); 8103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach } 8203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isInt() const { return !IsFp; } 841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 85c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // If the coefficient is represented by an integer, promote it to a 8603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // floating point. 87c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang void convertToFpType(const fltSemantics &Sem); 88c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 89c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // Construct an APFloat from a signed integer. 90c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // TODO: We should get rid of this function when APFloat can be constructed 9103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // from an *SIGNED* integer. 92c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 94d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang 951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool IsFp; 9603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // True iff FpValBuf contains an instance of APFloat. 981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool BufHasFpVal; 9903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The integer coefficient of an individual addend is either 1 or -1, 1011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // and we try to simplify at most 4 addends from neighboring at most 1021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 1031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is overkill of this end. 1041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang short IntVal; 105d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang 106d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang AlignedCharArrayUnion<APFloat> FpValBuf; 1071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 10803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// FAddend is used to represent floating-point addend. An addend is 1101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// represented as <C, V>, where the V is a symbolic value, and C is a 1111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// constant coefficient. A constant addend is represented as <C, 0>. 1121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// 1131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddend { 1141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 1151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend() { Val = 0; } 11603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *getSymVal (void) const { return Val; } 1181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &getCoef(void) const { return Coeff; } 11903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isConstant() const { return Val == 0; } 1211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isZero() const { return Coeff.isZero(); } 1221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 1241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const APFloat& Coefficient, Value *V) 1251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang { Coeff.set(Coefficient); Val = V; } 1261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const ConstantFP* Coefficient, Value *V) 1271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang { Coeff.set(Coefficient->getValueAPF()); Val = V; } 12803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void negate() { Coeff.negate(); } 13003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Drill down the U-D chain one step to find the definition of V, and 1321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// try to break the definition into one or two addends. 1331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 13403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Similar to FAddend::drillDownOneStep() except that the value being 1361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// splitted is the addend itself. 1371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 13803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator+=(const FAddend &T) { 1401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert((Val == T.Val) && "Symbolic-values disagree"); 1411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Coeff += T.Coeff; 1421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 1431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 14603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // This addend has the value of "Coeff * Val". 1481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Val; 1491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddendCoef Coeff; 1501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 15103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 1531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// with its neighboring at most two instructions. 1541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// 1551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddCombine { 1561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 1571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {} 1581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *simplify(Instruction *FAdd); 15903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang typedef SmallVector<const FAddend*, 4> AddendVect; 16203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 164a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 165a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *performFactorization(Instruction *I); 166a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 1671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Convert given addend to a Value 1681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createAddendVal(const FAddend &A, bool& NeedNeg); 16903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Return the number of instructions needed to emit the N-ary addition. 1711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned calcInstrNumber(const AddendVect& Vect); 1721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFSub(Value *Opnd0, Value *Opnd1); 1731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFAdd(Value *Opnd0, Value *Opnd1); 1741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFMul(Value *Opnd0, Value *Opnd1); 175a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *createFDiv(Value *Opnd0, Value *Opnd1); 1761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFNeg(Value *V); 1771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 1781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void createInstPostProc(Instruction *NewInst); 17903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstCombiner::BuilderTy *Builder; 1811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Instruction *Instr; 18203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Debugging stuff are clustered here. 1851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #ifndef NDEBUG 1861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned CreateInstrNum; 1871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void initCreateInstNum() { CreateInstrNum = 0; } 1881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void incCreateInstNum() { CreateInstrNum++; } 1891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #else 1901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void initCreateInstNum() {} 1911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void incCreateInstNum() {} 1921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #endif 1931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 19403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach} 1951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang//===----------------------------------------------------------------------===// 1971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 1981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Implementation of 1991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// {FAddendCoef, FAddend, FAddition, FAddCombine}. 2001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 2011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang//===----------------------------------------------------------------------===// 2021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangFAddendCoef::~FAddendCoef() { 2031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (BufHasFpVal) 2041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpValPtr()->~APFloat(); 2051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::set(const APFloat& C) { 2081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat *P = getFpValPtr(); 2091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // As the buffer is meanless byte stream, we cannot call 2121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // APFloat::operator=(). 2131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang new(P) APFloat(C); 2141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } else 2151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang *P = C; 2161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 21703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach IsFp = BufHasFpVal = true; 2181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 220c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yangvoid FAddendCoef::convertToFpType(const fltSemantics &Sem) { 221c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (!isInt()) 222c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return; 223c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 224c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat *P = getFpValPtr(); 225c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (IntVal > 0) 226c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang new(P) APFloat(Sem, IntVal); 227c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang else { 228c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang new(P) APFloat(Sem, 0 - IntVal); 229c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang P->changeSign(); 230c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang } 23103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach IsFp = BufHasFpVal = true; 232c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang} 233c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 234c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin YangAPFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 235c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (Val >= 0) 236c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return APFloat(Sem, Val); 237c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 238c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat T(Sem, 0 - Val); 239c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.changeSign(); 240c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 241c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return T; 242c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang} 243c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 244c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yangvoid FAddendCoef::operator=(const FAddendCoef &That) { 2451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isInt()) 2461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang set(That.IntVal); 2471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang set(That.getFpVal()); 2491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator+=(const FAddendCoef &That) { 2521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 2531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() == That.isInt()) { 2541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 2551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal += That.IntVal; 2561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().add(That.getFpVal(), RndMode); 2581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 26003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &T = That.getFpVal(); 263c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(T.getSemantics()); 264c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang getFpVal().add(T, RndMode); 2651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 26703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &T = getFpVal(); 269c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 2701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator-=(const FAddendCoef &That) { 2731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 2741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() == That.isInt()) { 2751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 2761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal -= That.IntVal; 2771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().subtract(That.getFpVal(), RndMode); 2791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 28103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &T = That.getFpVal(); 284c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(T.getSemantics()); 285c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang getFpVal().subtract(T, RndMode); 2861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 2881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &T = getFpVal(); 290c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 2911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator*=(const FAddendCoef &That) { 2941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isOne()) 2951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isMinusOne()) { 2981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang negate(); 2991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() && That.isInt()) { 3031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang int Res = IntVal * (int)That.IntVal; 3041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!insaneIntVal(Res) && "Insane int value"); 3051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal = Res; 3061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 30903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach const fltSemantics &Semantic = 3101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 3111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 313c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(Semantic); 3141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &F0 = getFpVal(); 3151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isInt()) 317c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 318c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat::rmNearestTiesToEven); 3191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 3211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::negate() { 3261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 3271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal = 0 - IntVal; 3281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().changeSign(); 3301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddendCoef::getValue(Type *Ty) const { 3331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return isInt() ? 3341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP::get(Ty, float(IntVal)) : 3351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP::get(Ty->getContext(), getFpVal()); 3361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// The definition of <Val> Addends 3391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// ========================================= 3401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// A + B <1, A>, <1,B> 3411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// A - B <1, A>, <1,B> 3421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 0 - B <-1, B> 3431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// C * A, <C, A> 34403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach// A + C <1, A> <C, NULL> 3451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 0 +/- 0 <0, NULL> (corner case) 3461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 3471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Legend: A and B are not constant, C is constant 34803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach// 3491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddend::drillValueDownOneStep 3501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Val, FAddend &Addend0, FAddend &Addend1) { 3511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Instruction *I = 0; 3521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Val == 0 || !(I = dyn_cast<Instruction>(Val))) 3531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 3541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opcode = I->getOpcode(); 3561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 3581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP *C0, *C1; 3591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Opnd0 = I->getOperand(0); 3601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Opnd1 = I->getOperand(1); 3611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 3621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd0 = 0; 3631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 3651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd1 = 0; 3661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0) { 3681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!C0) 3691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(1, Opnd0); 3701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(C0, 0); 3721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1) { 3751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend &Addend = Opnd0 ? Addend1 : Addend0; 3761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!C1) 3771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend.set(1, Opnd1); 3781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend.set(C1, 0); 3801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opcode == Instruction::FSub) 3811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend.negate(); 3821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0 || Opnd1) 3851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Opnd0 && Opnd1 ? 2 : 1; 3861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Both operands are zero. Weird! 3881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0); 3891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 3901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I->getOpcode() == Instruction::FMul) { 3931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V0 = I->getOperand(0); 3941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V1 = I->getOperand(1); 3951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 3961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(C, V1); 3971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 3981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 4011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(C, V0); 4021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 4031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 4071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 4081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Try to break *this* addend into two addends. e.g. Suppose this addend is 4101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 4111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// i.e. <2.3, X> and <2.3, Y>. 4121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 4131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddend::drillAddendDownOneStep 4141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (FAddend &Addend0, FAddend &Addend1) const { 4151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isConstant()) 4161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 4171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 41903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (!BreakNum || Coeff.isOne()) 4201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return BreakNum; 4211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.Scale(Coeff); 4231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (BreakNum == 2) 4251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend1.Scale(Coeff); 4261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return BreakNum; 4281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 4291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 430a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// Try to perform following optimization on the input instruction I. Return the 431a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// simplified expression if was successful; otherwise, return 0. 432a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// 433a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// Instruction "I" is Simplified into 434a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// ------------------------------------------------------- 435a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// (x * y) +/- (x * z) x * (y +/- z) 436a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// (y / x) +/- (z / x) (y +/- z) / x 437a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// 438a0c9939873c404f272b3e0abb102c335146764feShuxin YangValue *FAddCombine::performFactorization(Instruction *I) { 439a0c9939873c404f272b3e0abb102c335146764feShuxin Yang assert((I->getOpcode() == Instruction::FAdd || 440a0c9939873c404f272b3e0abb102c335146764feShuxin Yang I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 44103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 442a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 443a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 44403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 445a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 446a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return 0; 447a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 448a0c9939873c404f272b3e0abb102c335146764feShuxin Yang bool isMpy = false; 449a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (I0->getOpcode() == Instruction::FMul) 450a0c9939873c404f272b3e0abb102c335146764feShuxin Yang isMpy = true; 451a0c9939873c404f272b3e0abb102c335146764feShuxin Yang else if (I0->getOpcode() != Instruction::FDiv) 452a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return 0; 453a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 454a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd0_0 = I0->getOperand(0); 455a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd0_1 = I0->getOperand(1); 456a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd1_0 = I1->getOperand(0); 457a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd1_1 = I1->getOperand(1); 458a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 45903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // Input Instr I Factor AddSub0 AddSub1 460a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // ---------------------------------------------- 461a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // (x*y) +/- (x*z) x y z 462a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // (y/x) +/- (z/x) x y z 463a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // 464a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Factor = 0; 465a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *AddSub0 = 0, *AddSub1 = 0; 46603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 467a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (isMpy) { 468a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 469a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_0; 470a0c9939873c404f272b3e0abb102c335146764feShuxin Yang else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 471a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_1; 472a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 473a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Factor) { 474a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 475a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 476a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } 477a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } else if (Opnd0_1 == Opnd1_1) { 478a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_1; 479a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub0 = Opnd0_0; 480a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub1 = Opnd1_0; 481a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } 482a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 483a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (!Factor) 484a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return 0; 485a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 486a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 487a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 488a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createFAdd(AddSub0, AddSub1) : 489a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createFSub(AddSub0, AddSub1); 490a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 491a0c9939873c404f272b3e0abb102c335146764feShuxin Yang const APFloat &F = CFP->getValueAPF(); 492c3cfe53b661533401017e39d22022656fc7c74c5Michael Gottesman if (!F.isNormal()) 493a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return 0; 494a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } 495a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 496a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (isMpy) 497a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return createFMul(Factor, NewAddSub); 49803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 499a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return createFDiv(NewAddSub, Factor); 500a0c9939873c404f272b3e0abb102c335146764feShuxin Yang} 501a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 5021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::simplify(Instruction *I) { 5031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 5041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Currently we are not able to handle vector type. 5061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I->getType()->isVectorTy()) 5071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 5081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert((I->getOpcode() == Instruction::FAdd || 5101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 5111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 51203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // Save the instruction before calling other member-functions. 5131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Instr = I; 5141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 5161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 5181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 5201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opnd0_ExpNum = 0; 5211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opnd1_ExpNum = 0; 5221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 52303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (!Opnd0.isConstant()) 5241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 5251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 5271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (OpndNum == 2 && !Opnd1.isConstant()) 5281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 5291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 5311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum && Opnd1_ExpNum) { 5321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_0); 5341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_0); 5351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum == 2) 5361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_1); 5371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum == 2) 5381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_1); 5391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Compute instruction quota. We should save at least one instruction. 5411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstQuota = 0; 5421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V0 = I->getOperand(0); 5441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V1 = I->getOperand(1); 54503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 5461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 5471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 5491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (OpndNum != 2) { 5531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 5541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // splitted into two addends, say "V = X - Y", the instruction would have 5551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // been optimized into "I = Y - X" in the previous steps. 5561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 5571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &CE = Opnd0.getCoef(); 5581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return CE.isOne() ? Opnd0.getSymVal() : 0; 5591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 5621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum) { 5631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0); 5651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_0); 5661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum == 2) 5671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_1); 5681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, 1)) 5701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 5741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum) { 5751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1); 5771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_0); 5781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum == 2) 5791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_1); 5801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, 1)) 5821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 58503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // step 6: Try factorization as the last resort, 586a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return performFactorization(I); 5871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 5881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 5901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned AddendNum = Addends.size(); 5921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(AddendNum <= 4 && "Too many addends"); 5931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 59403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // For saving intermediate results; 5951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned NextTmpIdx = 0; 5961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend TmpResult[3]; 5971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Points to the constant addend of the resulting simplified expression. 5991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If the resulting expr has constant-addend, this constant-addend is 6001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // desirable to reside at the top of the resulting expression tree. Placing 6011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // constant close to supper-expr(s) will potentially reveal some optimization 6021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // opportunities in super-expr(s). 6031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 6041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *ConstAdd = 0; 6051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Simplified addends are placed <SimpVect>. 6071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect SimpVect; 6081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The outer loop works on one symbolic-value at a time. Suppose the input 61003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 6111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The symbolic-values will be processed in this order: x, y, z. 6121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 6131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 6141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *ThisAddend = Addends[SymIdx]; 6161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!ThisAddend) { 6171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // This addend was processed before. 6181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 6191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Val = ThisAddend->getSymVal(); 6221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned StartIdx = SimpVect.size(); 6231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(ThisAddend); 6241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The inner loop collects addends sharing same symbolic-value, and these 6261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // addends will be later on folded into a single addend. Following above 6271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // example, if the symbolic value "y" is being processed, the inner loop 6281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 6291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // be later on folded into "<b1+b2, y>". 6301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 6311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned SameSymIdx = SymIdx + 1; 6321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SameSymIdx < AddendNum; SameSymIdx++) { 6331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *T = Addends[SameSymIdx]; 6341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (T && T->getSymVal() == Val) { 6351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Set null such that next iteration of the outer loop will not process 6361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // this addend again. 63703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach Addends[SameSymIdx] = 0; 6381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(T); 6391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If multiple addends share same symbolic value, fold them together. 6431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (StartIdx + 1 != SimpVect.size()) { 6441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend &R = TmpResult[NextTmpIdx ++]; 6451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang R = *SimpVect[StartIdx]; 6461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) 6471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang R += *SimpVect[Idx]; 6481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Pop all addends being folded and push the resulting folded addend. 65003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach SimpVect.resize(StartIdx); 6511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Val != 0) { 6521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!R.isZero()) { 6531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(&R); 6541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } else { 6561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Don't push constant addend at this time. It will be the last element 6571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // of <SimpVect>. 6581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstAdd = &R; 6591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 663b9df53a40b22c74ce3f3a7b4a7c0676a38cf5e73Craig Topper assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) && 6641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang "out-of-bound access"); 6651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstAdd) 6671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(ConstAdd); 6681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Result; 6701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!SimpVect.empty()) 6711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Result = createNaryFAdd(SimpVect, InstrQuota); 6721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else { 6731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The addition is folded to 0.0. 6741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Result = ConstantFP::get(Instr->getType(), 0.0); 6751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Result; 6781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 6791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createNaryFAdd 6811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (const AddendVect &Opnds, unsigned InstrQuota) { 6821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!Opnds.empty() && "Expect at least one addend"); 6831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 1: Check if the # of instructions needed exceeds the quota. 68503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // 6861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstrNeeded = calcInstrNumber(Opnds); 6871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (InstrNeeded > InstrQuota) 6881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 6891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang initCreateInstNum(); 6911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 2: Emit the N-ary addition. 6931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Note that at most three instructions are involved in Fadd-InstCombine: the 6941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // addition in question, and at most two neighboring instructions. 6951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The resulting optimized addition should have at least one less instruction 6961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // than the original addition expression tree. This implies that the resulting 6971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // N-ary addition has at most two instructions, and we don't need to worry 6981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // about tree-height when constructing the N-ary addition. 6991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *LastVal = 0; 7011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool LastValNeedNeg = false; 7021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Iterate the addends, creating fadd/fsub using adjacent two addends. 7041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 7051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I != E; I++) { 70603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach bool NeedNeg; 7071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = createAddendVal(**I, NeedNeg); 7081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!LastVal) { 7091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = V; 7101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastValNeedNeg = NeedNeg; 7111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 7121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg == NeedNeg) { 7151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFAdd(LastVal, V); 7161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 7171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg) 7201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFSub(V, LastVal); 7211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 7221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFSub(LastVal, V); 7231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastValNeedNeg = false; 7251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg) { 7281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFNeg(LastVal); 7291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #ifndef NDEBUG 73203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach assert(CreateInstrNum == InstrNeeded && 7331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang "Inconsistent in instruction numbers"); 7341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #endif 7351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return LastVal; 7371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFSub 7401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Opnd0, Value *Opnd1) { 7411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFSub(Opnd0, Opnd1); 742a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 743a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFNeg(Value *V) { 7481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0)); 7491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return createFSub(Zero, V); 7501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFAdd 7531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Opnd0, Value *Opnd1) { 7541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFAdd(Opnd0, Opnd1); 755a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 756a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { 7611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFMul(Opnd0, Opnd1); 762a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 763a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 764a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return V; 765a0c9939873c404f272b3e0abb102c335146764feShuxin Yang} 766a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 767a0c9939873c404f272b3e0abb102c335146764feShuxin YangValue *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { 768a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *V = Builder->CreateFDiv(Opnd0, Opnd1); 769a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 770a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddCombine::createInstPostProc(Instruction *NewInstr) { 7751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NewInstr->setDebugLoc(Instr->getDebugLoc()); 7761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Keep track of the number of instruction created. 7781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang incCreateInstNum(); 7791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Propagate fast-math flags 7811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NewInstr->setFastMathFlags(Instr->getFastMathFlags()); 7821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Return the number of instruction needed to emit the N-ary addition. 7851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// NOTE: Keep this function in sync with createAddendVal(). 7861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { 7871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned OpndNum = Opnds.size(); 7881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstrNeeded = OpndNum - 1; 7891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 79003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // The number of addends in the form of "(-1)*x". 79103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach unsigned NegOpndNum = 0; 7921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Adjust the number of instructions needed to emit the N-ary add. 7941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 7951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I != E; I++) { 7961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *Opnd = *I; 7971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd->isConstant()) 7981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 7991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &CE = Opnd->getCoef(); 8011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (CE.isMinusOne() || CE.isMinusTwo()) 8021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NegOpndNum++; 8031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Let the addend be "c * x". If "c == +/-1", the value of the addend 8051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is immediately available; otherwise, it needs exactly one instruction 8061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // to evaluate the value. 8071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!CE.isMinusOne() && !CE.isOne()) 8081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstrNeeded++; 8091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (NegOpndNum == OpndNum) 8111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstrNeeded++; 8121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return InstrNeeded; 8131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 8141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Input Addend Value NeedNeg(output) 8161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// ================================================================ 8171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Constant C C false 8181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <+/-1, V> V coefficient is -1 8191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <2/-2, V> "fadd V, V" coefficient is -2 8201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <C, V> "fmul V, C" false 8211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 8221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. 8231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createAddendVal 8241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (const FAddend &Opnd, bool &NeedNeg) { 8251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &Coeff = Opnd.getCoef(); 8261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd.isConstant()) { 8281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = false; 8291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Coeff.getValue(Instr->getType()); 8301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *OpndVal = Opnd.getSymVal(); 8331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Coeff.isMinusOne() || Coeff.isOne()) { 8351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = Coeff.isMinusOne(); 8361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return OpndVal; 8371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Coeff.isTwo() || Coeff.isMinusTwo()) { 8401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = Coeff.isMinusTwo(); 8411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return createFAdd(OpndVal, OpndVal); 8421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = false; 8451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return createFMul(OpndVal, Coeff.getValue(Instr->getType())); 8461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 8471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 84853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// AddOne - Add one to a ConstantInt. 84953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic Constant *AddOne(Constant *C) { 85053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 85153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 8521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 85353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// SubOne - Subtract one from a ConstantInt. 85453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic Constant *SubOne(ConstantInt *C) { 85553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ConstantInt::get(C->getContext(), C->getValue()-1); 85653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 85753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 85853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 85953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// dyn_castFoldableMul - If this value is a multiply that can be folded into 86053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// other computations (because it has a constant operand), return the 86153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// non-constant operand of the multiply, and set CST to point to the multiplier. 86253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// Otherwise, return null. 86353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 86453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 865b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (!V->hasOneUse() || !V->getType()->isIntegerTy()) 8663168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return 0; 8674d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 8683168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 8693168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I == 0) return 0; 8704d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 8713168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I->getOpcode() == Instruction::Mul) 8723168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 8733168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return I->getOperand(0); 8743168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I->getOpcode() == Instruction::Shl) 8753168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 8763168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner // The multiplier is really 1 << CST. 8773168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 8783168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner uint32_t CSTVal = CST->getLimitedValue(BitWidth); 8793168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner CST = ConstantInt::get(V->getType()->getContext(), 8800a230e0d985625a3909cb78fd867a3abaf434565Benjamin Kramer APInt::getOneBitSet(BitWidth, CSTVal)); 8813168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return I->getOperand(0); 88253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 88353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 88453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 88553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 88653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 88753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// WillNotOverflowSignedAdd - Return true if we can prove that: 88853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 88953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// This basically requires proving that the add in the original type would not 89053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// overflow to change the sign bit or have a carry out. 89153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerbool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 89253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // There are different heuristics we can use for this. Here are some simple 89353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ones. 8944d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 8954d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman // Add has the property that adding any two 2's complement numbers can only 89653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // have one carry bit which can change a sign. As such, if LHS and RHS each 89753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // have at least two sign bits, we know that the addition of the two values 89853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // will sign extend fine. 89953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 90053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return true; 9014d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 9024d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 90353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If one of the operands only has one non-zero bit, and if the other operand 90453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // has a known-zero bit in a more significant place than it (not including the 90553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // sign bit) the ripple may go up to and fill the zero, but won't change the 90653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // sign. For example, (X & ~4) + 1. 9074d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 90853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // TODO: Implement. 9094d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 91053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return false; 91153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 91253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 91353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitAdd(BinaryOperator &I) { 914096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 91553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 91653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 91753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 91853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner I.hasNoUnsignedWrap(), TD)) 91953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, V); 92053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 92137bf92b5238434b00fde79347ba5336e7554e562Duncan Sands // (A*B)+(A*C) -> A*(B+C) etc 92237bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 92337bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 92437bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 925b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 926b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + (signbit) --> X ^ signbit 927b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &Val = CI->getValue(); 928b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Val.isSignBit()) 929b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateXor(LHS, RHS); 9304d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 931b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if SimplifyDemandedBits can simplify this. This handles stuff like 932b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X & 254)+1 -> (X&254)|1 933b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (SimplifyDemandedInstructionBits(I)) 934b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return &I; 935b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 936b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // zext(bool) + C -> bool ? C + 1 : C 937b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 938b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZI->getSrcTy()->isIntegerTy(1)) 939b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 9404d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 941b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *XorLHS = 0; ConstantInt *XorRHS = 0; 942b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 94353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 944b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &RHSVal = CI->getValue(); 945be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman unsigned ExtendAmt = 0; 946be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 947be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 948be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (XorRHS->getValue() == -RHSVal) { 949be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (RHSVal.isPowerOf2()) 950be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 951be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman else if (XorRHS->getValue().isPowerOf2()) 952be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 95353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 9544d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 955be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 956be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 957be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (!MaskedValueIsZero(XorLHS, Mask)) 958be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = 0; 959be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman } 9604d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 961be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 962be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 963be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 964be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman return BinaryOperator::CreateAShr(NewShl, ShAmt); 96553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 96649064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer 96749064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer // If this is a xor that was canonicalized from a sub, turn it back into 96849064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer // a sub and fuse this add with it. 96949064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { 97049064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer IntegerType *IT = cast<IntegerType>(I.getType()); 97149064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer APInt LHSKnownOne(IT->getBitWidth(), 0); 97249064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer APInt LHSKnownZero(IT->getBitWidth(), 0); 97326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne); 97449064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue()) 97549064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), 97649064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer XorLHS); 97749064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer } 9788ec23cb07e22198a720c4e151241059cca215c08David Majnemer // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C, 9798ec23cb07e22198a720c4e151241059cca215c08David Majnemer // transform them into (X + (signbit ^ C)) 9808ec23cb07e22198a720c4e151241059cca215c08David Majnemer if (XorRHS->getValue().isSignBit()) 9818ec23cb07e22198a720c4e151241059cca215c08David Majnemer return BinaryOperator::CreateAdd(XorLHS, 9828ec23cb07e22198a720c4e151241059cca215c08David Majnemer ConstantExpr::getXor(XorRHS, CI)); 98353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 98453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 98553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 986b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 987b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 988b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return NV; 989b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 990b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 99153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(LHS, RHS); 99253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 993b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + X --> X << 1 994bd9f6bf5cd5499715e216415989c29f820a7561cChris Lattner if (LHS == RHS) { 99541429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator *New = 99641429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 99741429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoSignedWrap(I.hasNoSignedWrap()); 99841429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 99941429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner return New; 100041429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner } 100153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 100253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 100353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 100453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castNegVal(LHS)) { 10050f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes if (!isa<Constant>(RHS)) 10060f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes if (Value *RHSV = dyn_castNegVal(RHS)) { 10070f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 10080f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes return BinaryOperator::CreateNeg(NewAdd); 10090f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes } 10104d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 101153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(RHS, LHSV); 101253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 101353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 101453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 101553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 101653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(RHS)) 101753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(LHS, V); 101853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 101953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 102053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; 102153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(LHS, C2)) { 102253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == RHS) // X*C + X --> X * (C+1) 102353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(RHS, AddOne(C2)); 102453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 102553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X*C1 + X*C2 --> X * (C1+C2) 102653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 102753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(RHS, C1)) 102853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 102953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 103053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 103153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + X*C --> X * (C+1) 103253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (dyn_castFoldableMul(RHS, C2) == LHS) 103353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(LHS, AddOne(C2)); 103453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 103594c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // A+B --> A|B iff A and B have no bits set in common. 1036db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 103753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownOne(IT->getBitWidth(), 0); 103853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownZero(IT->getBitWidth(), 0); 103926c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne); 104053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSKnownZero != 0) { 104153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownOne(IT->getBitWidth(), 0); 104253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownZero(IT->getBitWidth(), 0); 104326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne); 10444d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 104553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // No bits in common -> bitwise or. 104653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 104753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateOr(LHS, RHS); 104853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 104953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 105053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 105194c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // W*X + Y*Z --> W * (X+Z) iff W == Y 1052b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner { 105353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *W, *X, *Y, *Z; 105453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 105553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 105653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W != Y) { 105753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Z) { 105853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 105953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (Y == X) { 106053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 106153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (X == Z) { 106253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 106353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 106453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 106553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 106653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 106753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Y) { 106853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 106953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(W, NewAdd); 107053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 107153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 107253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 107353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 107453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 107553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 107653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 107753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(SubOne(CRHS), X); 107853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 107953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (X & FF00) + xx00 -> (X+xx00) & FF00 108053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS->hasOneUse() && 1081b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 1082b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 1083b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if all bits from the first bit set in the Add RHS up are included 1084b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // in the mask. First, get the rightmost bit. 1085b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &AddRHSV = CRHS->getValue(); 10864d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1087b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Form a mask of all bits from the lowest bit added through the top. 1088b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 1089b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1090b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if the and mask includes all of these bits. 1091b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 1092b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1093b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (AddRHSHighBits == AddRHSHighBitsAnd) { 1094b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Okay, the xform is safe. Insert the new add pronto. 1095b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 1096b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(NewAdd, C2); 109753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 109853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 109953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 110053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant add into select arguments. 110153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 110253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 110353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 110453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 110553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 110653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // add (select X 0 (sub n A)) A --> select X A n 110753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner { 110853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SelectInst *SI = dyn_cast<SelectInst>(LHS); 110953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *A = RHS; 111053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!SI) { 111153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI = dyn_cast<SelectInst>(RHS); 111253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner A = LHS; 111353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 111453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SI && SI->hasOneUse()) { 111553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *TV = SI->getTrueValue(); 111653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *FV = SI->getFalseValue(); 111753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *N; 111853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 111953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Can we fold the add into the argument of the select? 112053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We check both true and false select arguments for a matching subtract. 1121b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 112253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the true select value. 112353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), N, A); 11244d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1125b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 112653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the false select value. 112753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), A, N); 112853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 112953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 113053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 113153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for (add (sext x), y), see if we can merge this into an 113253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a sext. 113353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 113453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), cst) --> (sext (add x, cst')) 113553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 11364d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Constant *CI = 113753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 113853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 113953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSExt(CI, I.getType()) == RHSC && 114053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 114153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new, smaller add. 11424d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 114353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 114453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 114553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 114653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 11474d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 114853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), (sext y)) --> (sext (add int x, y)) 114953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 115053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 115153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of sexts), and if the 115253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add will not overflow. 115353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 115453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 115553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 115653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 115753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 11584d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 11593168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner RHSConv->getOperand(0), "addconv"); 116053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 116153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 116253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 116353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 116453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1165c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier // Check for (x & y) + (x ^ y) 1166c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier { 1167c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier Value *A = 0, *B = 0; 1168c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && 1169c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier (match(LHS, m_And(m_Specific(A), m_Specific(B))) || 1170c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier match(LHS, m_And(m_Specific(B), m_Specific(A))))) 1171c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier return BinaryOperator::CreateOr(A, B); 1172c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier 1173c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && 1174c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier (match(RHS, m_And(m_Specific(A), m_Specific(B))) || 1175c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier match(RHS, m_And(m_Specific(B), m_Specific(A))))) 1176c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier return BinaryOperator::CreateOr(A, B); 1177c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier } 1178c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier 117953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 118053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 118153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 118253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 1183096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 118453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 118553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1186c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD)) 1187c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman return ReplaceInstUsesWith(I, V); 118853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1189a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<Constant>(RHS)) { 1190a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<PHINode>(LHS)) 1191a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoPhi(I)) 1192a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1193a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 1194a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1195a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1196a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1197a98ce503b958821fd2530aad585c21e730695a9eStephen Lin } 119807acee7a09c4895904f827bf56cf15f6bf8ef9f6Michael Ilseman 119953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 120053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 120153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castFNegVal(LHS)) 120253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(RHS, LHSV); 120353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 120453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 120553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 120653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castFNegVal(RHS)) 120753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(LHS, V); 120853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1209a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // Check for (fadd double (sitofp x), y), see if we can merge this into an 121053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a promotion. 121153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 1212a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 121353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ... if the constant fits in the integer value. This is useful for things 121453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 121553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // requires a constant pool load, and generally allows the add to be better 121653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // instcombined. 121753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 12184d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Constant *CI = 121953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 122053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 122153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 122253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 122353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 122453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 122553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 122653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 122753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 122853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 12294d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1230a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 123153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 123253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 123353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of int->fp conversions), 123453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // and if the integer add will not overflow. 123553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 123653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 123753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 123853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 123953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 12404d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 124153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0),"addconv"); 124253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 124353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 124453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 124553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 12464d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1247c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat // select C, 0, B + select C, A, 0 -> select C, A, B 1248c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat { 1249c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Value *A1, *B1, *C1, *A2, *B2, *C2; 1250c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) && 1251c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) { 1252c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (C1 == C2) { 1253c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Constant *Z1=0, *Z2=0; 1254c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Value *A, *B, *C=C1; 1255c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) { 1256c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z1 = dyn_cast<Constant>(A1); A = A2; 1257c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z2 = dyn_cast<Constant>(B2); B = B1; 1258c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) { 1259c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z1 = dyn_cast<Constant>(B1); B = B2; 1260c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z2 = dyn_cast<Constant>(A2); A = A1; 1261c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1262c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat 1263c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (Z1 && Z2 && 1264c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat (I.hasNoSignedZeros() || 1265c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) { 1266c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat return SelectInst::Create(C, A, B); 1267c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1268c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1269c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1270c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1271c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat 12721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I.hasUnsafeAlgebra()) { 12731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *V = FAddCombine(Builder).simplify(&I)) 12741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return ReplaceInstUsesWith(I, V); 12751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 12761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 127753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 127853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 127953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 128053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 128153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// Optimize pointer differences into the same array into a size. Consider: 128253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 128353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 128453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// 128553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 1286db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty) { 128753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner assert(TD && "Must have target data info for this"); 12884d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 128953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 129053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // this. 129153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Swapped = false; 1292d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEPOperator *GEP1 = 0, *GEP2 = 0; 1293d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer 129453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // For now we require one side to be the base pointer "A" or a constant 1295d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // GEP derived from it. 1296d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 129753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - X 129853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSGEP->getOperand(0) == RHS) { 1299d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = LHSGEP; 130053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 1301d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1302d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // (gep X, ...) - (gep X, ...) 1303d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (LHSGEP->getOperand(0)->stripPointerCasts() == 1304d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer RHSGEP->getOperand(0)->stripPointerCasts()) { 1305d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP2 = RHSGEP; 1306d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = LHSGEP; 130753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 130853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 130953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 131053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 13114d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1312d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 131353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X - (gep X, ...) 131453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHSGEP->getOperand(0) == LHS) { 1315d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = RHSGEP; 131653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 1317d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1318d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // (gep X, ...) - (gep X, ...) 1319d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (RHSGEP->getOperand(0)->stripPointerCasts() == 1320d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer LHSGEP->getOperand(0)->stripPointerCasts()) { 1321d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP2 = LHSGEP; 1322d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = RHSGEP; 132353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 132453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 132553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 132653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 13274d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1328d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // Avoid duplicating the arithmetic if GEP2 has non-constant indices and 1329d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // multiple users. 1330d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEP1 == 0 || 1331d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse())) 133253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 13334d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 133453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit the offset of the GEP and an intptr_t. 1335d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Value *Result = EmitGEPOffset(GEP1); 13364d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 133753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we had a constant expression GEP on the other side offsetting the 133853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // pointer, subtract it from the offset we have. 1339d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEP2) { 1340d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Value *Offset = EmitGEPOffset(GEP2); 1341d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Result = Builder->CreateSub(Result, Offset); 134253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 134353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 134453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we have p - gep(p, ...) then we have to negate the result. 134553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Swapped) 134653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateNeg(Result, "diff.neg"); 134753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 134853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Builder->CreateIntCast(Result, Ty, true); 134953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 135053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 135153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 135253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitSub(BinaryOperator &I) { 135353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 135453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1355fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 1356fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands I.hasNoUnsignedWrap(), TD)) 1357fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ReplaceInstUsesWith(I, V); 135853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 135937bf92b5238434b00fde79347ba5336e7554e562Duncan Sands // (A*B)-(A*C) -> A*(B-C) etc 136037bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 136137bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 136237bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 136353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 136453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(Op1)) { 136553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 136653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 136753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 136853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Res; 136953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 137053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1371b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 137253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(Op0, Op1); 1373b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1374b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Replace (-1 - A) with (~A). 1375b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_AllOnes())) 1376b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNot(Op1); 13774d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 137853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 137953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - ~X == X + (1+C) 138053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 138153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op1, m_Not(m_Value(X)))) 138253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAdd(X, AddOne(C)); 138353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 138453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>u 31) -> (X >>s 31) 138553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>s 31) -> (X >>u 31) 138653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (C->isZero()) { 1387b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *X; ConstantInt *CI; 1388b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 1389b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Verify we are shifting out everything but the sign bit. 1390b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1391b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAShr(X, CI); 1392b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1393b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 1394b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Verify we are shifting out everything but the sign bit. 1395b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1396b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateLShr(X, CI); 139753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 139853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 139953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant sub into select arguments. 140053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 140153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 140253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 140353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1404b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // C-(X+C2) --> (C-C2)-X 1405b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner ConstantInt *C2; 1406b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2)))) 1407b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 14081fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 14091fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if (SimplifyDemandedInstructionBits(I)) 14101fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer return &I; 14118e528100d210e225cee417229d94af91355118c0Paul Redmond 14128e528100d210e225cee417229d94af91355118c0Paul Redmond // Fold (sub 0, (zext bool to B)) --> (sext bool to B) 14138e528100d210e225cee417229d94af91355118c0Paul Redmond if (C->isZero() && match(Op1, m_ZExt(m_Value(X)))) 14148e528100d210e225cee417229d94af91355118c0Paul Redmond if (X->getType()->isIntegerTy(1)) 14158e528100d210e225cee417229d94af91355118c0Paul Redmond return CastInst::CreateSExtOrBitCast(X, Op1->getType()); 14168e528100d210e225cee417229d94af91355118c0Paul Redmond 14178e528100d210e225cee417229d94af91355118c0Paul Redmond // Fold (sub 0, (sext bool to B)) --> (zext bool to B) 14188e528100d210e225cee417229d94af91355118c0Paul Redmond if (C->isZero() && match(Op1, m_SExt(m_Value(X)))) 14198e528100d210e225cee417229d94af91355118c0Paul Redmond if (X->getType()->isIntegerTy(1)) 14208e528100d210e225cee417229d94af91355118c0Paul Redmond return CastInst::CreateZExtOrBitCast(X, Op1->getType()); 142153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 142253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 14234d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1424b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner { Value *Y; 1425b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X-(X+Y) == -Y X-(Y+X) == -Y 1426b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 1427b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 1428b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 14294d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1430b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X-Y)-X == -Y 1431b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 1432b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 1433b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner } 14344d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1435b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Op1->hasOneUse()) { 1436b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *X = 0, *Y = 0, *Z = 0; 1437b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *C = 0; 1438b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner ConstantInt *CI = 0; 1439b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1440b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (Y - Z)) --> (X + (Z - Y)). 1441b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 1442b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, 1443b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateSub(Z, Y, Op1->getName())); 1444b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1445b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (X & Y)) --> (X & ~Y) 1446b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 1447b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 1448b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 1449b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(Op0, 1450b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateNot(Y, Y->getName() + ".not")); 14514d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1452b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 0 - (X sdiv C) -> (X sdiv -C) 1453b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && 1454b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op0, m_Zero())) 1455b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 1456b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1457b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 1458b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 1459b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Value *XNeg = dyn_castNegVal(X)) 1460b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateShl(XNeg, Y); 1461b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1462b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - X*C --> X * (1-C) 1463b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) { 1464b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); 1465b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateMul(Op0, CP1); 146653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 146753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1468b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - X<<C --> X * (1-(1<<C)) 1469b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) { 1470b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *One = ConstantInt::get(I.getType(), 1); 1471b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI)); 1472b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateMul(Op0, C); 147353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14744d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1475b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*-B -> X + A*B 1476b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - -A*B -> X + A*B 1477b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *A, *B; 1478b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 1479b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 1480b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 14814d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1482b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*CI -> X + A*-CI 1483b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - CI*A -> X + A*-CI 1484b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) || 1485b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) { 1486b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 1487b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, NewMul); 148853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 148953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 149053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 149153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 149253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(Op0, C1)) { 149353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == Op1) // X*C - X --> X * (C-1) 149453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(Op1, SubOne(C1)); 149553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 149653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 149753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(Op1, C2)) 149853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 149953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 15004d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 150153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Optimize pointer differences into the same array into a size. Consider: 150253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // &A[10] - &A[0]: we should compile this to "10". 150353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (TD) { 150453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHSOp, *RHSOp; 150553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 150653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_PtrToInt(m_Value(RHSOp)))) 150753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 150853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 15094d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 151053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // trunc(p)-trunc(q) -> trunc(p-q) 151153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 151253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 151353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 151453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 151553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 15164d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 151753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 151853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 151953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 152053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 152153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 152253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1523c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD)) 1524c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman return ReplaceInstUsesWith(I, V); 1525c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman 1526a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<Constant>(Op0)) 1527a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1528a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1529a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1530a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 15310c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson // If this is a 'B = x-(-A)', change to B = x+A, potentially looking 15320c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson // through FP extensions/truncations along the way. 1533605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson if (Value *V = dyn_castFNegVal(Op1)) { 1534605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V); 1535605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1536605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 1537605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson } 15380c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) { 15390c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) { 15400c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson Value *NewTrunc = Builder->CreateFPTrunc(V, I.getType()); 1541605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc); 1542605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1543605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 15440c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 15450c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) { 15460c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) { 1547107c578126c477ad330bb79defb10ef14eb7dad3Owen Anderson Value *NewExt = Builder->CreateFPExt(V, I.getType()); 1548605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt); 1549605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1550605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 15510c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 15520c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 155353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 15541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I.hasUnsafeAlgebra()) { 15551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *V = FAddCombine(Builder).simplify(&I)) 15561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return ReplaceInstUsesWith(I, V); 15571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 15581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 155953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 156053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 1561