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" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/GetElementPtrTypeIterator.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PatternMatch.h" 2053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace llvm; 2153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace PatternMatch; 2253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "instcombine" 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangnamespace { 261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Class representing coefficient of floating-point addend. 281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// This class needs to be highly efficient, which is especially true for 291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// the constructor. As of I write this comment, the cost of the default 3003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// perform write-merging). 3203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach /// 331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddendCoef { 341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The constructor has to initialize a APFloat, which is uncessary for 361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // most addends which have coefficient either 1 or -1. So, the constructor 371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is expensive. In order to avoid the cost of the constructor, we should 381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // reuse some instances whenever possible. The pre-created instances 391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // FAddCombine::Add[0-5] embodies this idea. 401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ~FAddendCoef(); 4303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(short C) { 451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!insaneIntVal(C) && "Insane coefficient"); 461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IsFp = false; IntVal = C; 471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const APFloat& C); 50c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void negate(); 5203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *getValue(Type *) const; 5503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If possible, don't define operator+/operator- etc because these 571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // operators inevitably call FAddendCoef's constructor which is not cheap. 581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator=(const FAddendCoef &A); 591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator+=(const FAddendCoef &A); 601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator-=(const FAddendCoef &A); 611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator*=(const FAddendCoef &S); 6203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isOne() const { return isInt() && IntVal == 1; } 641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isTwo() const { return isInt() && IntVal == 2; } 651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isMinusOne() const { return isInt() && IntVal == -1; } 661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isMinusTwo() const { return isInt() && IntVal == -2; } 6703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool insaneIntVal(int V) { return V > 4 || V < -4; } 701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat *getFpValPtr(void) 71d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 724ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene const APFloat *getFpValPtr(void) const 734ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &getFpVal(void) const { 761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(IsFp && BufHasFpVal && "Incorret state"); 774ee576fac3a84553c9342faea87ff0e13e8eb48dDavid Greene return *getFpValPtr(); 781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach APFloat &getFpVal(void) { 8103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach assert(IsFp && BufHasFpVal && "Incorret state"); 8203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach return *getFpValPtr(); 8303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach } 8403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isInt() const { return !IsFp; } 861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 87c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // If the coefficient is represented by an integer, promote it to a 8803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // floating point. 89c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang void convertToFpType(const fltSemantics &Sem); 90c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 91c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // Construct an APFloat from a signed integer. 92c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang // TODO: We should get rid of this function when APFloat can be constructed 9303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // from an *SIGNED* integer. 94c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 96d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang 971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool IsFp; 9803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // True iff FpValBuf contains an instance of APFloat. 1001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool BufHasFpVal; 10103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The integer coefficient of an individual addend is either 1 or -1, 1031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // and we try to simplify at most 4 addends from neighboring at most 1041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 1051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is overkill of this end. 1061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang short IntVal; 107d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang 108d6b51d1dc158b82cab2e2a77b6c4b4fddb156952Shuxin Yang AlignedCharArrayUnion<APFloat> FpValBuf; 1091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 11003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// FAddend is used to represent floating-point addend. An addend is 1121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// represented as <C, V>, where the V is a symbolic value, and C is a 1131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// constant coefficient. A constant addend is represented as <C, 0>. 1141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// 1151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddend { 1161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FAddend() { Val = nullptr; } 11803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *getSymVal (void) const { return Val; } 1201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &getCoef(void) const { return Coeff; } 12103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isConstant() const { return Val == nullptr; } 1231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool isZero() const { return Coeff.isZero(); } 1241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 1261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const APFloat& Coefficient, Value *V) 1271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang { Coeff.set(Coefficient); Val = V; } 1281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void set(const ConstantFP* Coefficient, Value *V) 1291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang { Coeff.set(Coefficient->getValueAPF()); Val = V; } 13003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void negate() { Coeff.negate(); } 13203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Drill down the U-D chain one step to find the definition of V, and 1341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// try to break the definition into one or two addends. 1351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 13603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Similar to FAddend::drillDownOneStep() except that the value being 1381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// splitted is the addend itself. 1391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 14003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void operator+=(const FAddend &T) { 1421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert((Val == T.Val) && "Symbolic-values disagree"); 1431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Coeff += T.Coeff; 1441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 1451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 14803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // This addend has the value of "Coeff * Val". 1501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Val; 1511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddendCoef Coeff; 1521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 15303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 1551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// with its neighboring at most two instructions. 1561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// 1571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang class FAddCombine { 1581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang public: 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(nullptr) {} 1601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *simplify(Instruction *FAdd); 16103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang typedef SmallVector<const FAddend*, 4> AddendVect; 16403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 166a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 167a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *performFactorization(Instruction *I); 168a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 1691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Convert given addend to a Value 1701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createAddendVal(const FAddend &A, bool& NeedNeg); 17103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang /// Return the number of instructions needed to emit the N-ary addition. 1731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned calcInstrNumber(const AddendVect& Vect); 1741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFSub(Value *Opnd0, Value *Opnd1); 1751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFAdd(Value *Opnd0, Value *Opnd1); 1761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFMul(Value *Opnd0, Value *Opnd1); 177a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *createFDiv(Value *Opnd0, Value *Opnd1); 1781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createFNeg(Value *V); 1791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void createInstPostProc(Instruction *NewInst, bool NoNumber = false); 18103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstCombiner::BuilderTy *Builder; 1831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Instruction *Instr; 18403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang private: 1861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Debugging stuff are clustered here. 1871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #ifndef NDEBUG 1881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned CreateInstrNum; 1891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void initCreateInstNum() { CreateInstrNum = 0; } 1901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void incCreateInstNum() { CreateInstrNum++; } 1911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #else 1921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void initCreateInstNum() {} 1931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang void incCreateInstNum() {} 1941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #endif 1951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang }; 19603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach} 1971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang//===----------------------------------------------------------------------===// 1991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 2001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Implementation of 2011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// {FAddendCoef, FAddend, FAddition, FAddCombine}. 2021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 2031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang//===----------------------------------------------------------------------===// 2041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangFAddendCoef::~FAddendCoef() { 2051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (BufHasFpVal) 2061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpValPtr()->~APFloat(); 2071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::set(const APFloat& C) { 2101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat *P = getFpValPtr(); 2111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // As the buffer is meanless byte stream, we cannot call 2141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // APFloat::operator=(). 2151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang new(P) APFloat(C); 2161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } else 2171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang *P = C; 2181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 21903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach IsFp = BufHasFpVal = true; 2201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 222c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yangvoid FAddendCoef::convertToFpType(const fltSemantics &Sem) { 223c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (!isInt()) 224c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return; 225c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 226c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat *P = getFpValPtr(); 227c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (IntVal > 0) 228c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang new(P) APFloat(Sem, IntVal); 229c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang else { 230c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang new(P) APFloat(Sem, 0 - IntVal); 231c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang P->changeSign(); 232c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang } 23303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach IsFp = BufHasFpVal = true; 234c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang} 235c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 236c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin YangAPFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 237c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang if (Val >= 0) 238c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return APFloat(Sem, Val); 239c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 240c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat T(Sem, 0 - Val); 241c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.changeSign(); 242c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 243c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang return T; 244c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang} 245c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang 246c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yangvoid FAddendCoef::operator=(const FAddendCoef &That) { 2471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isInt()) 2481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang set(That.IntVal); 2491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang set(That.getFpVal()); 2511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator+=(const FAddendCoef &That) { 2541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 2551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() == That.isInt()) { 2561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 2571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal += That.IntVal; 2581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().add(That.getFpVal(), RndMode); 2601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 26203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &T = That.getFpVal(); 265c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(T.getSemantics()); 266c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang getFpVal().add(T, RndMode); 2671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 26903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &T = getFpVal(); 271c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 2721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator-=(const FAddendCoef &That) { 2751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 2761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() == That.isInt()) { 2771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 2781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal -= That.IntVal; 2791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 2801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().subtract(That.getFpVal(), RndMode); 2811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 28303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) { 2851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const APFloat &T = That.getFpVal(); 286c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(T.getSemantics()); 287c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang getFpVal().subtract(T, RndMode); 2881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 2901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &T = getFpVal(); 292c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 2931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 2941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::operator*=(const FAddendCoef &That) { 2961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isOne()) 2971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 2981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 2991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isMinusOne()) { 3001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang negate(); 3011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt() && That.isInt()) { 3051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang int Res = IntVal * (int)That.IntVal; 3061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!insaneIntVal(Res) && "Insane int value"); 3071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal = Res; 3081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 31103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach const fltSemantics &Semantic = 3121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 3131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 315c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang convertToFpType(Semantic); 3161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang APFloat &F0 = getFpVal(); 3171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (That.isInt()) 319c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 320c76067b7746f15879232c2aa27cf5c1ca35b3449Shuxin Yang APFloat::rmNearestTiesToEven); 3211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 3231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return; 3251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangvoid FAddendCoef::negate() { 3281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isInt()) 3291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang IntVal = 0 - IntVal; 3301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 3311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang getFpVal().changeSign(); 3321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddendCoef::getValue(Type *Ty) const { 3351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return isInt() ? 3361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP::get(Ty, float(IntVal)) : 3371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP::get(Ty->getContext(), getFpVal()); 3381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 3391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// The definition of <Val> Addends 3411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// ========================================= 3421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// A + B <1, A>, <1,B> 3431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// A - B <1, A>, <1,B> 3441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 0 - B <-1, B> 3451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// C * A, <C, A> 34603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach// A + C <1, A> <C, NULL> 3471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 0 +/- 0 <0, NULL> (corner case) 3481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 3491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Legend: A and B are not constant, C is constant 35003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach// 3511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddend::drillValueDownOneStep 3521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Val, FAddend &Addend0, FAddend &Addend1) { 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *I = nullptr; 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Val || !(I = dyn_cast<Instruction>(Val))) 3551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 3561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opcode = I->getOpcode(); 3581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 3601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstantFP *C0, *C1; 3611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Opnd0 = I->getOperand(0); 3621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Opnd1 = I->getOperand(1); 3631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Opnd0 = nullptr; 3651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Opnd1 = nullptr; 3681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0) { 3701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!C0) 3711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(1, Opnd0); 3721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Addend0.set(C0, nullptr); 3741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1) { 3771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend &Addend = Opnd0 ? Addend1 : Addend0; 3781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!C1) 3791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend.set(1, Opnd1); 3801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Addend.set(C1, nullptr); 3821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opcode == Instruction::FSub) 3831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend.negate(); 3841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0 || Opnd1) 3871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Opnd0 && Opnd1 ? 2 : 1; 3881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Both operands are zero. Weird! 390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr); 3911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 3921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 3931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 3941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I->getOpcode() == Instruction::FMul) { 3951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V0 = I->getOperand(0); 3961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V1 = I->getOperand(1); 3971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 3981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(C, V1); 3991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 4001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 4031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.set(C, V0); 4041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 1; 4051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 4071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 4091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 4101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Try to break *this* addend into two addends. e.g. Suppose this addend is 4121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 4131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// i.e. <2.3, X> and <2.3, Y>. 4141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 4151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddend::drillAddendDownOneStep 4161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (FAddend &Addend0, FAddend &Addend1) const { 4171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (isConstant()) 4181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return 0; 4191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 42103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (!BreakNum || Coeff.isOne()) 4221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return BreakNum; 4231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend0.Scale(Coeff); 4251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (BreakNum == 2) 4271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Addend1.Scale(Coeff); 4281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 4291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return BreakNum; 4301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 4311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 432a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// Try to perform following optimization on the input instruction I. Return the 433a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// simplified expression if was successful; otherwise, return 0. 434a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// 435a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// Instruction "I" is Simplified into 436a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// ------------------------------------------------------- 437a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// (x * y) +/- (x * z) x * (y +/- z) 438a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// (y / x) +/- (z / x) (y +/- z) / x 439a0c9939873c404f272b3e0abb102c335146764feShuxin Yang// 440a0c9939873c404f272b3e0abb102c335146764feShuxin YangValue *FAddCombine::performFactorization(Instruction *I) { 441a0c9939873c404f272b3e0abb102c335146764feShuxin Yang assert((I->getOpcode() == Instruction::FAdd || 442a0c9939873c404f272b3e0abb102c335146764feShuxin Yang I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 44303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 444a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 445a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 44603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 447a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 448dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 449a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 450a0c9939873c404f272b3e0abb102c335146764feShuxin Yang bool isMpy = false; 451a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (I0->getOpcode() == Instruction::FMul) 452a0c9939873c404f272b3e0abb102c335146764feShuxin Yang isMpy = true; 453a0c9939873c404f272b3e0abb102c335146764feShuxin Yang else if (I0->getOpcode() != Instruction::FDiv) 454dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 455a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 456a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd0_0 = I0->getOperand(0); 457a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd0_1 = I0->getOperand(1); 458a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd1_0 = I1->getOperand(0); 459a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *Opnd1_1 = I1->getOperand(1); 460a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 46103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // Input Instr I Factor AddSub0 AddSub1 462a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // ---------------------------------------------- 463a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // (x*y) +/- (x*z) x y z 464a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // (y/x) +/- (z/x) x y z 465a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // 466dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Factor = nullptr; 467dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *AddSub0 = nullptr, *AddSub1 = nullptr; 46803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 469a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (isMpy) { 470a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 471a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_0; 472a0c9939873c404f272b3e0abb102c335146764feShuxin Yang else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 473a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_1; 474a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 475a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Factor) { 476a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 477a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 478a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } 479a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } else if (Opnd0_1 == Opnd1_1) { 480a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Factor = Opnd0_1; 481a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub0 = Opnd0_0; 482a0c9939873c404f272b3e0abb102c335146764feShuxin Yang AddSub1 = Opnd1_0; 483a0c9939873c404f272b3e0abb102c335146764feShuxin Yang } 484a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 485a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (!Factor) 486dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 487a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 48836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FastMathFlags Flags; 48936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Flags.setUnsafeAlgebra(); 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I0) Flags &= I->getFastMathFlags(); 49136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I1) Flags &= I->getFastMathFlags(); 49236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 493a0c9939873c404f272b3e0abb102c335146764feShuxin Yang // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 494a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 495a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createFAdd(AddSub0, AddSub1) : 496a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createFSub(AddSub0, AddSub1); 497a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 498a0c9939873c404f272b3e0abb102c335146764feShuxin Yang const APFloat &F = CFP->getValueAPF(); 499c3cfe53b661533401017e39d22022656fc7c74c5Michael Gottesman if (!F.isNormal()) 500dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 50136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (Instruction *II = dyn_cast<Instruction>(NewAddSub)) 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines II->setFastMathFlags(Flags); 503a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 50436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isMpy) { 50536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *RI = createFMul(Factor, NewAddSub); 50636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *II = dyn_cast<Instruction>(RI)) 50736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines II->setFastMathFlags(Flags); 50836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RI; 50936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 51003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 51136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *RI = createFDiv(NewAddSub, Factor); 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *II = dyn_cast<Instruction>(RI)) 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines II->setFastMathFlags(Flags); 51436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RI; 515a0c9939873c404f272b3e0abb102c335146764feShuxin Yang} 516a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 5171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::simplify(Instruction *I) { 5181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 5191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Currently we are not able to handle vector type. 5211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I->getType()->isVectorTy()) 522dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 5231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert((I->getOpcode() == Instruction::FAdd || 5251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 5261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 52703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // Save the instruction before calling other member-functions. 5281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Instr = I; 5291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 5311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 5331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 5351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opnd0_ExpNum = 0; 5361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned Opnd1_ExpNum = 0; 5371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 53803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (!Opnd0.isConstant()) 5391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 5401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 5421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (OpndNum == 2 && !Opnd1.isConstant()) 5431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 5441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 5461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum && Opnd1_ExpNum) { 5471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_0); 5491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_0); 5501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum == 2) 5511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_1); 5521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum == 2) 5531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_1); 5541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Compute instruction quota. We should save at least one instruction. 5561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstQuota = 0; 5571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V0 = I->getOperand(0); 5591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V1 = I->getOperand(1); 56003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 5611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 5621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 5641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (OpndNum != 2) { 5681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 5691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // splitted into two addends, say "V = X - Y", the instruction would have 5701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // been optimized into "I = Y - X" in the previous steps. 5711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 5721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &CE = Opnd0.getCoef(); 573dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return CE.isOne() ? Opnd0.getSymVal() : nullptr; 5741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 5771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum) { 5781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0); 5801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_0); 5811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd1_ExpNum == 2) 5821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1_1); 5831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, 1)) 5851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 5891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum) { 5901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect AllOpnds; 5911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd1); 5921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_0); 5931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd0_ExpNum == 2) 5941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AllOpnds.push_back(&Opnd0_1); 5951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 5961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *R = simplifyFAdd(AllOpnds, 1)) 5971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return R; 5981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 5991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 60003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // step 6: Try factorization as the last resort, 601a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return performFactorization(I); 6021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 6031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 6051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned AddendNum = Addends.size(); 6071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(AddendNum <= 4 && "Too many addends"); 6081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 60903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // For saving intermediate results; 6101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned NextTmpIdx = 0; 6111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend TmpResult[3]; 6121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Points to the constant addend of the resulting simplified expression. 6141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If the resulting expr has constant-addend, this constant-addend is 6151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // desirable to reside at the top of the resulting expression tree. Placing 6161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // constant close to supper-expr(s) will potentially reveal some optimization 6171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // opportunities in super-expr(s). 6181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 619dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const FAddend *ConstAdd = nullptr; 6201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Simplified addends are placed <SimpVect>. 6221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang AddendVect SimpVect; 6231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The outer loop works on one symbolic-value at a time. Suppose the input 62503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 6261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The symbolic-values will be processed in this order: x, y, z. 6271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 6281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 6291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *ThisAddend = Addends[SymIdx]; 6311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!ThisAddend) { 6321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // This addend was processed before. 6331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 6341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Val = ThisAddend->getSymVal(); 6371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned StartIdx = SimpVect.size(); 6381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(ThisAddend); 6391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The inner loop collects addends sharing same symbolic-value, and these 6411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // addends will be later on folded into a single addend. Following above 6421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // example, if the symbolic value "y" is being processed, the inner loop 6431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 6441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // be later on folded into "<b1+b2, y>". 6451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // 6461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned SameSymIdx = SymIdx + 1; 6471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SameSymIdx < AddendNum; SameSymIdx++) { 6481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *T = Addends[SameSymIdx]; 6491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (T && T->getSymVal() == Val) { 6501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Set null such that next iteration of the outer loop will not process 6511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // this addend again. 652dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Addends[SameSymIdx] = nullptr; 6531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(T); 6541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // If multiple addends share same symbolic value, fold them together. 6581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (StartIdx + 1 != SimpVect.size()) { 6591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang FAddend &R = TmpResult[NextTmpIdx ++]; 6601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang R = *SimpVect[StartIdx]; 6611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) 6621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang R += *SimpVect[Idx]; 6631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Pop all addends being folded and push the resulting folded addend. 66503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach SimpVect.resize(StartIdx); 666dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Val) { 6671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!R.isZero()) { 6681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(&R); 6691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } else { 6711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Don't push constant addend at this time. It will be the last element 6721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // of <SimpVect>. 6731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang ConstAdd = &R; 6741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 678b9df53a40b22c74ce3f3a7b4a7c0676a38cf5e73Craig Topper assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) && 6791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang "out-of-bound access"); 6801a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6811a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (ConstAdd) 6821a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang SimpVect.push_back(ConstAdd); 6831a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6841a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Result; 6851a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!SimpVect.empty()) 6861a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Result = createNaryFAdd(SimpVect, InstrQuota); 6871a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else { 6881a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The addition is folded to 0.0. 6891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Result = ConstantFP::get(Instr->getType(), 0.0); 6901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 6911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6921a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Result; 6931a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 6941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createNaryFAdd 6961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (const AddendVect &Opnds, unsigned InstrQuota) { 6971a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang assert(!Opnds.empty() && "Expect at least one addend"); 6981a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 6991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Step 1: Check if the # of instructions needed exceeds the quota. 70003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // 7011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstrNeeded = calcInstrNumber(Opnds); 7021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (InstrNeeded > InstrQuota) 703dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 7041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang initCreateInstNum(); 7061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // step 2: Emit the N-ary addition. 7081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Note that at most three instructions are involved in Fadd-InstCombine: the 7091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // addition in question, and at most two neighboring instructions. 7101a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // The resulting optimized addition should have at least one less instruction 7111a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // than the original addition expression tree. This implies that the resulting 7121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // N-ary addition has at most two instructions, and we don't need to worry 7131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // about tree-height when constructing the N-ary addition. 7141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 715dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *LastVal = nullptr; 7161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang bool LastValNeedNeg = false; 7171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Iterate the addends, creating fadd/fsub using adjacent two addends. 7191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 7201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I != E; I++) { 72103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach bool NeedNeg; 7221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = createAddendVal(**I, NeedNeg); 7231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!LastVal) { 7241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = V; 7251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastValNeedNeg = NeedNeg; 7261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 7271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg == NeedNeg) { 7301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFAdd(LastVal, V); 7311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 7321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg) 7351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFSub(V, LastVal); 7361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang else 7371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFSub(LastVal, V); 7381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastValNeedNeg = false; 7401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (LastValNeedNeg) { 7431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang LastVal = createFNeg(LastVal); 7441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 7451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #ifndef NDEBUG 74703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach assert(CreateInstrNum == InstrNeeded && 7481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang "Inconsistent in instruction numbers"); 7491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang #endif 7501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return LastVal; 7521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFSub 7551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Opnd0, Value *Opnd1) { 7561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFSub(Opnd0, Opnd1); 757a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 758a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFNeg(Value *V) { 7631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0)); 76436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *NewV = createFSub(Zero, V); 76536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *I = dyn_cast<Instruction>(NewV)) 76636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines createInstPostProc(I, true); // fneg's don't receive instruction numbers. 76736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return NewV; 7681a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7691a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7701a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFAdd 7711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (Value *Opnd0, Value *Opnd1) { 7721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFAdd(Opnd0, Opnd1); 773a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 774a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7761a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7771a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7781a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { 7791a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *V = Builder->CreateFMul(Opnd0, Opnd1); 780a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 781a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 782a0c9939873c404f272b3e0abb102c335146764feShuxin Yang return V; 783a0c9939873c404f272b3e0abb102c335146764feShuxin Yang} 784a0c9939873c404f272b3e0abb102c335146764feShuxin Yang 785a0c9939873c404f272b3e0abb102c335146764feShuxin YangValue *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { 786a0c9939873c404f272b3e0abb102c335146764feShuxin Yang Value *V = Builder->CreateFDiv(Opnd0, Opnd1); 787a0c9939873c404f272b3e0abb102c335146764feShuxin Yang if (Instruction *I = dyn_cast<Instruction>(V)) 788a0c9939873c404f272b3e0abb102c335146764feShuxin Yang createInstPostProc(I); 7891a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return V; 7901a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 7911a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 79236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid FAddCombine::createInstPostProc(Instruction *NewInstr, 79336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool NoNumber) { 7941a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NewInstr->setDebugLoc(Instr->getDebugLoc()); 7951a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 7961a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Keep track of the number of instruction created. 79736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!NoNumber) 79836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines incCreateInstNum(); 7991a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8001a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Propagate fast-math flags 8011a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NewInstr->setFastMathFlags(Instr->getFastMathFlags()); 8021a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 8031a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8041a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Return the number of instruction needed to emit the N-ary addition. 8051a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// NOTE: Keep this function in sync with createAddendVal(). 8061a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yangunsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { 8071a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned OpndNum = Opnds.size(); 8081a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang unsigned InstrNeeded = OpndNum - 1; 8091a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 81003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // The number of addends in the form of "(-1)*x". 81103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach unsigned NegOpndNum = 0; 8121a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8131a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Adjust the number of instructions needed to emit the N-ary add. 8141a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 8151a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang I != E; I++) { 8161a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddend *Opnd = *I; 8171a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd->isConstant()) 8181a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang continue; 8191a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8201a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &CE = Opnd->getCoef(); 8211a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (CE.isMinusOne() || CE.isMinusTwo()) 8221a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NegOpndNum++; 8231a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8241a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // Let the addend be "c * x". If "c == +/-1", the value of the addend 8251a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // is immediately available; otherwise, it needs exactly one instruction 8261a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang // to evaluate the value. 8271a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (!CE.isMinusOne() && !CE.isOne()) 8281a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstrNeeded++; 8291a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8301a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (NegOpndNum == OpndNum) 8311a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang InstrNeeded++; 8321a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return InstrNeeded; 8331a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 8341a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8351a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Input Addend Value NeedNeg(output) 8361a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// ================================================================ 8371a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// Constant C C false 8381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <+/-1, V> V coefficient is -1 8391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <2/-2, V> "fadd V, V" coefficient is -2 8401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// <C, V> "fmul V, C" false 8411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// 8421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. 8431a3150098c137181576dc3e0960f8cd4abe9da1fShuxin YangValue *FAddCombine::createAddendVal 8441a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang (const FAddend &Opnd, bool &NeedNeg) { 8451a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang const FAddendCoef &Coeff = Opnd.getCoef(); 8461a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8471a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Opnd.isConstant()) { 8481a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = false; 8491a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return Coeff.getValue(Instr->getType()); 8501a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8511a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8521a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang Value *OpndVal = Opnd.getSymVal(); 8531a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8541a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Coeff.isMinusOne() || Coeff.isOne()) { 8551a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = Coeff.isMinusOne(); 8561a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return OpndVal; 8571a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8581a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8591a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Coeff.isTwo() || Coeff.isMinusTwo()) { 8601a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = Coeff.isMinusTwo(); 8611a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return createFAdd(OpndVal, OpndVal); 8621a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 8631a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 8641a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang NeedNeg = false; 8651a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return createFMul(OpndVal, Coeff.getValue(Instr->getType())); 8661a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang} 8671a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 868cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// If one of the operands only has one non-zero bit, and if the other 869cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// operand has a known-zero bit in a more significant place than it (not 870cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// including the sign bit) the ripple may go up to and fill the zero, but 871cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// won't change the sign. For example, (X & ~4) + 1. 872cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic bool checkRippleForAdd(const APInt &Op0KnownZero, 873cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const APInt &Op1KnownZero) { 874cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt Op1MaybeOne = ~Op1KnownZero; 875cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Make sure that one of the operand has at most one bit set to 1. 876cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Op1MaybeOne.countPopulation() != 1) 877cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 878cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 879cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Find the most significant known 0 other than the sign bit. 880cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines int BitWidth = Op0KnownZero.getBitWidth(); 881cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt Op0KnownZeroTemp(Op0KnownZero); 882cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Op0KnownZeroTemp.clearBit(BitWidth - 1); 883cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines int Op0ZeroPosition = BitWidth - Op0KnownZeroTemp.countLeadingZeros() - 1; 884cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 885cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines int Op1OnePosition = BitWidth - Op1MaybeOne.countLeadingZeros() - 1; 886cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(Op1OnePosition >= 0); 887cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 888cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // This also covers the case of no known zero, since in that case 889cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Op0ZeroPosition is -1. 890cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Op0ZeroPosition >= Op1OnePosition; 89153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 89253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 89353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// WillNotOverflowSignedAdd - Return true if we can prove that: 89453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 89553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// This basically requires proving that the add in the original type would not 89653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// overflow to change the sign bit or have a carry out. 897cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// TODO: Handle this for Vectors. 89853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerbool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 89953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // There are different heuristics we can use for this. Here are some simple 90053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ones. 9014d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 902cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If LHS and RHS each have at least two sign bits, the addition will look 903cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // like 904cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // 905cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // XX..... + 906cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // YY..... 907cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // 908cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If the carry into the most significant position is 0, X and Y can't both 909cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // be 1 and therefore the carry out of the addition is also 0. 910cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // 911cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If the carry into the most significant position is 1, X and Y can't both 912cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // be 0 and therefore the carry out of the addition is also 1. 913cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // 914cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Since the carry into the most significant position is always equal to 915cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // the carry out of the addition, there is no signed overflow. 91653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 91753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return true; 9184d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 919cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (IntegerType *IT = dyn_cast<IntegerType>(LHS->getType())) { 920cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines int BitWidth = IT->getBitWidth(); 921cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt LHSKnownZero(BitWidth, 0); 922cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt LHSKnownOne(BitWidth, 0); 923cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines computeKnownBits(LHS, LHSKnownZero, LHSKnownOne); 9244d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 925cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt RHSKnownZero(BitWidth, 0); 926cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines APInt RHSKnownOne(BitWidth, 0); 927cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines computeKnownBits(RHS, RHSKnownZero, RHSKnownOne); 928cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 929cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Addition of two 2's compliment numbers having opposite signs will never 930cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // overflow. 931cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if ((LHSKnownOne[BitWidth - 1] && RHSKnownZero[BitWidth - 1]) || 932cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines (LHSKnownZero[BitWidth - 1] && RHSKnownOne[BitWidth - 1])) 933cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 934cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 935cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Check if carry bit of addition will not cause overflow. 936cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (checkRippleForAdd(LHSKnownZero, RHSKnownZero)) 937cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 938cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (checkRippleForAdd(RHSKnownZero, LHSKnownZero)) 939cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 940cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 941cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 942cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 9434d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 944cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// WillNotOverflowUnsignedAdd - Return true if we can prove that: 945cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// (zext (add LHS, RHS)) === (add (zext LHS), (zext RHS)) 946cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) { 947cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // There are different heuristics we can use for this. Here is a simple one. 948cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If the sign bit of LHS and that of RHS are both zero, no unsigned wrap. 949cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool LHSKnownNonNegative, LHSKnownNegative; 950cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool RHSKnownNonNegative, RHSKnownNegative; 951cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0); 952cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0); 953cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (LHSKnownNonNegative && RHSKnownNonNegative) 954cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 9554d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 95653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return false; 95753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 95853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 959cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// Checks if any operand is negative and we can convert add to sub. 960cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// This function checks for following negative patterns 961cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) 962cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C)) 963cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even 964cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic Value *checkForNegativeOperand(BinaryOperator &I, 965cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines InstCombiner::BuilderTy *Builder) { 96653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 96753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 968cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // This function creates 2 instructions to replace ADD, we need at least one 969cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // of LHS or RHS to have one use to ensure benefit in transform. 970cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!LHS->hasOneUse() && !RHS->hasOneUse()) 971cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return nullptr; 972dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 973cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *X = nullptr, *Y = nullptr, *Z = nullptr; 974cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const APInt *C1 = nullptr, *C2 = nullptr; 975cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 976cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // if ONE is on other side, swap 977cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(RHS, m_Add(m_Value(X), m_One()))) 978cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::swap(LHS, RHS); 979cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 980cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(LHS, m_Add(m_Value(X), m_One()))) { 981cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // if XOR on other side, swap 982cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) 983cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::swap(X, RHS); 984cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 985cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) { 986cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1)) 987cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1)) 988cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) { 989cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *NewAnd = Builder->CreateAnd(Z, *C1); 990cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Builder->CreateSub(RHS, NewAnd, "sub"); 991cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) { 992cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1)) 993cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1)) 994cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *NewOr = Builder->CreateOr(Z, ~(*C1)); 995cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Builder->CreateSub(RHS, NewOr, "sub"); 996cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 997cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 998cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 999cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1000cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Restore LHS and RHS 1001cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines LHS = I.getOperand(0); 1002cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines RHS = I.getOperand(1); 1003cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1004cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // if XOR is on other side, swap 1005cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) 1006cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::swap(LHS, RHS); 1007cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1008cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // C2 is ODD 1009cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2)) 1010cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2)) 1011cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1)))) 1012cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (C1->countTrailingZeros() == 0) 1013cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) { 1014cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *NewOr = Builder->CreateOr(Z, ~(*C2)); 1015cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Builder->CreateSub(RHS, NewOr, "sub"); 1016cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 1017cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return nullptr; 1018cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 1019cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1020cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesInstruction *InstCombiner::visitAdd(BinaryOperator &I) { 1021cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool Changed = SimplifyAssociativeOrCommutative(I); 1022cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 1023cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1024cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Value *V = SimplifyVectorOp(I)) 1025cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ReplaceInstUsesWith(I, V); 102653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1027cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 1028cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines I.hasNoUnsignedWrap(), DL)) 1029cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ReplaceInstUsesWith(I, V); 1030cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1031cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // (A*B)+(A*C) -> A*(B+C) etc 103237bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 103337bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 103437bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 1035b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1036b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + (signbit) --> X ^ signbit 1037b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &Val = CI->getValue(); 1038b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Val.isSignBit()) 1039b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateXor(LHS, RHS); 10404d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1041b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if SimplifyDemandedBits can simplify this. This handles stuff like 1042b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X & 254)+1 -> (X&254)|1 1043b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (SimplifyDemandedInstructionBits(I)) 1044b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return &I; 1045b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1046b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // zext(bool) + C -> bool ? C + 1 : C 1047b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 1048b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZI->getSrcTy()->isIntegerTy(1)) 1049b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 10504d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1051dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr; 1052b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 105353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 1054b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &RHSVal = CI->getValue(); 1055be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman unsigned ExtendAmt = 0; 1056be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 1057be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 1058be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (XorRHS->getValue() == -RHSVal) { 1059be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (RHSVal.isPowerOf2()) 1060be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 1061be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman else if (XorRHS->getValue().isPowerOf2()) 1062be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 106353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 10644d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1065be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 1066be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 1067be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (!MaskedValueIsZero(XorLHS, Mask)) 1068be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = 0; 1069be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman } 10704d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1071be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 1072be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 1073be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 1074be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman return BinaryOperator::CreateAShr(NewShl, ShAmt); 107553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 107649064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer 107749064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer // If this is a xor that was canonicalized from a sub, turn it back into 107849064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer // a sub and fuse this add with it. 107949064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { 108049064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer IntegerType *IT = cast<IntegerType>(I.getType()); 108149064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer APInt LHSKnownOne(IT->getBitWidth(), 0); 108249064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer APInt LHSKnownZero(IT->getBitWidth(), 0); 1083dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines computeKnownBits(XorLHS, LHSKnownZero, LHSKnownOne); 108449064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue()) 108549064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), 108649064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer XorLHS); 108749064ff7708bcd3b720ce79bc7629c2f3207b8d6Benjamin Kramer } 10888ec23cb07e22198a720c4e151241059cca215c08David Majnemer // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C, 10898ec23cb07e22198a720c4e151241059cca215c08David Majnemer // transform them into (X + (signbit ^ C)) 10908ec23cb07e22198a720c4e151241059cca215c08David Majnemer if (XorRHS->getValue().isSignBit()) 10918ec23cb07e22198a720c4e151241059cca215c08David Majnemer return BinaryOperator::CreateAdd(XorLHS, 10928ec23cb07e22198a720c4e151241059cca215c08David Majnemer ConstantExpr::getXor(XorRHS, CI)); 109353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 109453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 109553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1096b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 1097b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 1098b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return NV; 1099b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 110036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I.getType()->getScalarType()->isIntegerTy(1)) 110153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(LHS, RHS); 110253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1103b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + X --> X << 1 1104bd9f6bf5cd5499715e216415989c29f820a7561cChris Lattner if (LHS == RHS) { 110541429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator *New = 110641429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 110741429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoSignedWrap(I.hasNoSignedWrap()); 110841429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 110941429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner return New; 111041429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner } 111153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 111253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 111353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 111453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castNegVal(LHS)) { 11150f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes if (!isa<Constant>(RHS)) 11160f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes if (Value *RHSV = dyn_castNegVal(RHS)) { 11170f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 11180f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes return BinaryOperator::CreateNeg(NewAdd); 11190f68fbb9e5a6ccc59c3c75581d4e594347ca4c92Nuno Lopes } 11204d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 112153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(RHS, LHSV); 112253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 112353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 112453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 112553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 112653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(RHS)) 112753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(LHS, V); 112853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1129cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Value *V = checkForNegativeOperand(I, Builder)) 1130cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ReplaceInstUsesWith(I, V); 113153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 113294c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // A+B --> A|B iff A and B have no bits set in common. 1133db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 113453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownOne(IT->getBitWidth(), 0); 113553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownZero(IT->getBitWidth(), 0); 1136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines computeKnownBits(LHS, LHSKnownZero, LHSKnownOne); 113753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSKnownZero != 0) { 113853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownOne(IT->getBitWidth(), 0); 113953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownZero(IT->getBitWidth(), 0); 1140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines computeKnownBits(RHS, RHSKnownZero, RHSKnownOne); 11414d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 114253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // No bits in common -> bitwise or. 114353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 114453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateOr(LHS, RHS); 114553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 114653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 114753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 114836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 114936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *X; 115036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 115153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(SubOne(CRHS), X); 115236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 115353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 115436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 115553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (X & FF00) + xx00 -> (X+xx00) & FF00 115636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *X; 115736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantInt *C2; 115853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS->hasOneUse() && 1159b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 1160b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 1161b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if all bits from the first bit set in the Add RHS up are included 1162b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // in the mask. First, get the rightmost bit. 1163b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &AddRHSV = CRHS->getValue(); 11644d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1165b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Form a mask of all bits from the lowest bit added through the top. 1166b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 1167b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1168b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if the and mask includes all of these bits. 1169b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 1170b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1171b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (AddRHSHighBits == AddRHSHighBitsAnd) { 1172b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Okay, the xform is safe. Insert the new add pronto. 1173b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 1174b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(NewAdd, C2); 117553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 117653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 117753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 117853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant add into select arguments. 117953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 118053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 118153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 118253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 118353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 118453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // add (select X 0 (sub n A)) A --> select X A n 118553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner { 118653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SelectInst *SI = dyn_cast<SelectInst>(LHS); 118753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *A = RHS; 118853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!SI) { 118953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI = dyn_cast<SelectInst>(RHS); 119053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner A = LHS; 119153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 119253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SI && SI->hasOneUse()) { 119353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *TV = SI->getTrueValue(); 119453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *FV = SI->getFalseValue(); 119553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *N; 119653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 119753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Can we fold the add into the argument of the select? 119853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We check both true and false select arguments for a matching subtract. 1199b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 120053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the true select value. 120153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), N, A); 12024d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1203b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 120453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the false select value. 120553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), A, N); 120653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 120753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 120853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 120953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for (add (sext x), y), see if we can merge this into an 121053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a sext. 121153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 121253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), cst) --> (sext (add x, cst')) 121353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 12144d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Constant *CI = 121553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 121653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 121753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSExt(CI, I.getType()) == RHSC && 121853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 121953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new, smaller add. 12204d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 122153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 122253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 122353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 122453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 12254d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 122653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), (sext y)) --> (sext (add int x, y)) 122753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 122853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 122953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of sexts), and if the 123053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add will not overflow. 123153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 123253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 123353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 123453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 123553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 12364d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 12373168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner RHSConv->getOperand(0), "addconv"); 123853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 123953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 124053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 124153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 124253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1243c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier // Check for (x & y) + (x ^ y) 1244c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier { 1245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *A = nullptr, *B = nullptr; 1246c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && 1247c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier (match(LHS, m_And(m_Specific(A), m_Specific(B))) || 1248c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier match(LHS, m_And(m_Specific(B), m_Specific(A))))) 1249c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier return BinaryOperator::CreateOr(A, B); 1250c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier 1251c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && 1252c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier (match(RHS, m_And(m_Specific(A), m_Specific(B))) || 1253c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier match(RHS, m_And(m_Specific(B), m_Specific(A))))) 1254c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier return BinaryOperator::CreateOr(A, B); 1255c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier } 1256c1fc5e4464788be072509eab7d66a73dc7a5f275Chad Rosier 1257cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // TODO(jingyue): Consider WillNotOverflowSignedAdd and 1258cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // WillNotOverflowUnsignedAdd to reduce the number of invocations of 1259cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // computeKnownBits. 1260cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!I.hasNoSignedWrap() && WillNotOverflowSignedAdd(LHS, RHS)) { 1261cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Changed = true; 1262cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines I.setHasNoSignedWrap(true); 1263cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 1264cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!I.hasNoUnsignedWrap() && WillNotOverflowUnsignedAdd(LHS, RHS)) { 1265cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Changed = true; 1266cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines I.setHasNoUnsignedWrap(true); 1267cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 1268cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 1269dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Changed ? &I : nullptr; 127053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 127153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 127253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 1273096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 127453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 127553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1277dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1278dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 127936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), DL)) 1280c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman return ReplaceInstUsesWith(I, V); 128153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1282a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<Constant>(RHS)) { 1283a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<PHINode>(LHS)) 1284a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoPhi(I)) 1285a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1286a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 1287a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1288a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1289a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1290a98ce503b958821fd2530aad585c21e730695a9eStephen Lin } 129107acee7a09c4895904f827bf56cf15f6bf8ef9f6Michael Ilseman 129253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 129353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 129436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *LHSV = dyn_castFNegVal(LHS)) { 129536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *RI = BinaryOperator::CreateFSub(RHS, LHSV); 129636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->copyFastMathFlags(&I); 129736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RI; 129836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 129953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 130053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 130153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 130236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = dyn_castFNegVal(RHS)) { 130336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *RI = BinaryOperator::CreateFSub(LHS, V); 130436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->copyFastMathFlags(&I); 130536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RI; 130636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 130753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1308a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // Check for (fadd double (sitofp x), y), see if we can merge this into an 130953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a promotion. 131053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 1311a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 131253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ... if the constant fits in the integer value. This is useful for things 131353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 131453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // requires a constant pool load, and generally allows the add to be better 131553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // instcombined. 131653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 13174d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Constant *CI = 131853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 131953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 132053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 132153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 132253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 132353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 132453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 132553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 132653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 132753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 13284d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1329a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 133053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 133153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 133253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of int->fp conversions), 133353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // and if the integer add will not overflow. 133453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 133553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 133653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 133753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 133853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 13394d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 134053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0),"addconv"); 134153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 134253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 134353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 134453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 13454d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1346c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat // select C, 0, B + select C, A, 0 -> select C, A, B 1347c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat { 1348c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Value *A1, *B1, *C1, *A2, *B2, *C2; 1349c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) && 1350c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) { 1351c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (C1 == C2) { 1352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *Z1=nullptr, *Z2=nullptr; 1353c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Value *A, *B, *C=C1; 1354c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) { 1355c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z1 = dyn_cast<Constant>(A1); A = A2; 1356c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z2 = dyn_cast<Constant>(B2); B = B1; 1357c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) { 1358c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z1 = dyn_cast<Constant>(B1); B = B2; 1359c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat Z2 = dyn_cast<Constant>(A2); A = A1; 1360c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1361c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat 1362c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat if (Z1 && Z2 && 1363c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat (I.hasNoSignedZeros() || 1364c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) { 1365c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat return SelectInst::Create(C, A, B); 1366c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1367c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1368c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1369c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat } 1370c5cf6e536598a3b1e30fce616b771d66a071a54cJean-Luc Duprat 13711a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I.hasUnsafeAlgebra()) { 13721a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *V = FAddCombine(Builder).simplify(&I)) 13731a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return ReplaceInstUsesWith(I, V); 13741a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 13751a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Changed ? &I : nullptr; 137753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 137853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 137953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 138053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// Optimize pointer differences into the same array into a size. Consider: 138153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 138253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 138353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// 138453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 1385db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty) { 138636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(DL && "Must have target data info for this"); 13874d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 138853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 138953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // this. 139053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Swapped = false; 1391dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines GEPOperator *GEP1 = nullptr, *GEP2 = nullptr; 1392d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer 139353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // For now we require one side to be the base pointer "A" or a constant 1394d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // GEP derived from it. 1395d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 139653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - X 139753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSGEP->getOperand(0) == RHS) { 1398d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = LHSGEP; 139953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 1400d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1401d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // (gep X, ...) - (gep X, ...) 1402d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (LHSGEP->getOperand(0)->stripPointerCasts() == 1403d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer RHSGEP->getOperand(0)->stripPointerCasts()) { 1404d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP2 = RHSGEP; 1405d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = LHSGEP; 140653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 140753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 140853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 140953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14104d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1411d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 141253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X - (gep X, ...) 141353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHSGEP->getOperand(0) == LHS) { 1414d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = RHSGEP; 141553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 1416d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1417d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // (gep X, ...) - (gep X, ...) 1418d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (RHSGEP->getOperand(0)->stripPointerCasts() == 1419d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer LHSGEP->getOperand(0)->stripPointerCasts()) { 1420d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP2 = LHSGEP; 1421d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer GEP1 = RHSGEP; 142253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 142353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 142453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 142553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14264d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1427d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // Avoid duplicating the arithmetic if GEP2 has non-constant indices and 1428d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer // multiple users. 1429dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!GEP1 || 1430dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (GEP2 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse())) 1431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 14324d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 143353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit the offset of the GEP and an intptr_t. 1434d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Value *Result = EmitGEPOffset(GEP1); 14354d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 143653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we had a constant expression GEP on the other side offsetting the 143753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // pointer, subtract it from the offset we have. 1438d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer if (GEP2) { 1439d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Value *Offset = EmitGEPOffset(GEP2); 1440d2348639e639573a7708de9ea98dc55bade048a6Benjamin Kramer Result = Builder->CreateSub(Result, Offset); 144153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 144253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 144353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we have p - gep(p, ...) then we have to negate the result. 144453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Swapped) 144553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateNeg(Result, "diff.neg"); 144653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 144753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Builder->CreateIntCast(Result, Ty, true); 144853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 144953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 145053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 145153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitSub(BinaryOperator &I) { 145253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 145353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1454dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1455dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1456dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1457fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 145836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I.hasNoUnsignedWrap(), DL)) 1459fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ReplaceInstUsesWith(I, V); 146053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 146137bf92b5238434b00fde79347ba5336e7554e562Duncan Sands // (A*B)-(A*C) -> A*(B-C) etc 146237bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 146337bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 146437bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 146553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 146653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(Op1)) { 146753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 146853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 146953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 147053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Res; 147153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 147253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1473b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 147453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(Op0, Op1); 1475b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1476b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Replace (-1 - A) with (~A). 1477b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_AllOnes())) 1478b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNot(Op1); 14794d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 148036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *C = dyn_cast<Constant>(Op0)) { 148153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - ~X == X + (1+C) 1482dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *X = nullptr; 148353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op1, m_Not(m_Value(X)))) 148453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAdd(X, AddOne(C)); 148553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 148653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant sub into select arguments. 148753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 148853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 148953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 149053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1491b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // C-(X+C2) --> (C-C2)-X 149236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C2; 149336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_Add(m_Value(X), m_Constant(C2)))) 1494b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 14951fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer 14961fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer if (SimplifyDemandedInstructionBits(I)) 14971fdfae05b0a4356d1ed0633bf3d6cdc6eba2e173Benjamin Kramer return &I; 14988e528100d210e225cee417229d94af91355118c0Paul Redmond 14998e528100d210e225cee417229d94af91355118c0Paul Redmond // Fold (sub 0, (zext bool to B)) --> (sext bool to B) 150036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->isNullValue() && match(Op1, m_ZExt(m_Value(X)))) 150136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (X->getType()->getScalarType()->isIntegerTy(1)) 15028e528100d210e225cee417229d94af91355118c0Paul Redmond return CastInst::CreateSExtOrBitCast(X, Op1->getType()); 15038e528100d210e225cee417229d94af91355118c0Paul Redmond 15048e528100d210e225cee417229d94af91355118c0Paul Redmond // Fold (sub 0, (sext bool to B)) --> (zext bool to B) 150536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->isNullValue() && match(Op1, m_SExt(m_Value(X)))) 150636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (X->getType()->getScalarType()->isIntegerTy(1)) 15078e528100d210e225cee417229d94af91355118c0Paul Redmond return CastInst::CreateZExtOrBitCast(X, Op1->getType()); 150853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 150953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 151036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 151136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // -(X >>u 31) -> (X >>s 31) 151236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // -(X >>s 31) -> (X >>u 31) 151336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->isZero()) { 151436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *X; ConstantInt *CI; 151536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 151636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Verify we are shifting out everything but the sign bit. 151736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 151836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return BinaryOperator::CreateAShr(X, CI); 151936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 152036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 152136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Verify we are shifting out everything but the sign bit. 152236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 152336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return BinaryOperator::CreateLShr(X, CI); 152436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 152536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 152636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15274d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1528b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner { Value *Y; 1529b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X-(X+Y) == -Y X-(Y+X) == -Y 1530b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 1531b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 1532b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 15334d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1534b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X-Y)-X == -Y 1535b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 1536b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 1537b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner } 15384d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1539b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Op1->hasOneUse()) { 1540dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *X = nullptr, *Y = nullptr, *Z = nullptr; 1541dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *C = nullptr; 1542dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *CI = nullptr; 1543b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1544b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (Y - Z)) --> (X + (Z - Y)). 1545b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 1546b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, 1547b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateSub(Z, Y, Op1->getName())); 1548b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1549b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (X & Y)) --> (X & ~Y) 1550b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 1551b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 1552b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 1553b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(Op0, 1554b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateNot(Y, Y->getName() + ".not")); 15554d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1556cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // 0 - (X sdiv C) -> (X sdiv -C) provided the negation doesn't overflow. 1557cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) && 1558cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines !C->isMinSignedValue()) 1559b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 1560b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1561b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 1562b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 1563b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Value *XNeg = dyn_castNegVal(X)) 1564b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateShl(XNeg, Y); 1565b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 1566b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*-B -> X + A*B 1567b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - -A*B -> X + A*B 1568b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *A, *B; 1569b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 1570b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 1571b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 15724d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1573b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*CI -> X + A*-CI 1574b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - CI*A -> X + A*-CI 157536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_Mul(m_Value(A), m_Constant(CI))) || 157636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines match(Op1, m_Mul(m_Constant(CI), m_Value(A)))) { 1577b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 1578b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, NewMul); 157953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 158053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 158153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 158253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Optimize pointer differences into the same array into a size. Consider: 158353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // &A[10] - &A[0]: we should compile this to "10". 158436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DL) { 158553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHSOp, *RHSOp; 158653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 158753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_PtrToInt(m_Value(RHSOp)))) 158853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 158953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 15904d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 159153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // trunc(p)-trunc(q) -> trunc(p-q) 159253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 159353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 159453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 159553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 1596cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 15974d96e6f0d105e60b423a118c3c8c7c5ffffae8b2Michael Ilseman 1598dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 159953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 160053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 160153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 160253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 160353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1604dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1605dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1606dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 160736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), DL)) 1608c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman return ReplaceInstUsesWith(I, V); 1609c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman 1610a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<Constant>(Op0)) 1611a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1612a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1613a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return NV; 1614a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 16150c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson // If this is a 'B = x-(-A)', change to B = x+A, potentially looking 16160c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson // through FP extensions/truncations along the way. 1617605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson if (Value *V = dyn_castFNegVal(Op1)) { 1618605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V); 1619605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1620605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 1621605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson } 16220c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) { 16230c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) { 16240c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson Value *NewTrunc = Builder->CreateFPTrunc(V, I.getType()); 1625605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc); 1626605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1627605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 16280c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 16290c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) { 16300c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) { 1631107c578126c477ad330bb79defb10ef14eb7dad3Owen Anderson Value *NewExt = Builder->CreateFPExt(V, I.getType()); 1632605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt); 1633605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson NewI->copyFastMathFlags(&I); 1634605b3427a9423c1e291a9e9ab94fd7202ca864aeOwen Anderson return NewI; 16350c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 16360c326f07ca713fa00d0dcba8ec9b61e91298f690Owen Anderson } 163753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 16381a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (I.hasUnsafeAlgebra()) { 16391a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang if (Value *V = FAddCombine(Builder).simplify(&I)) 16401a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang return ReplaceInstUsesWith(I, V); 16411a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang } 16421a3150098c137181576dc3e0960f8cd4abe9da1fShuxin Yang 1643dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 164453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 1645