1202375Srdivacky//===- InstCombineAddSub.cpp ----------------------------------------------===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file implements the visit functions for add, fadd, sub, and fsub. 11202375Srdivacky// 12202375Srdivacky//===----------------------------------------------------------------------===// 13202375Srdivacky 14202375Srdivacky#include "InstCombine.h" 15263508Sdim#include "llvm/ADT/STLExtras.h" 16202375Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 17249423Sdim#include "llvm/IR/DataLayout.h" 18202375Srdivacky#include "llvm/Support/GetElementPtrTypeIterator.h" 19202375Srdivacky#include "llvm/Support/PatternMatch.h" 20202375Srdivackyusing namespace llvm; 21202375Srdivackyusing namespace PatternMatch; 22202375Srdivacky 23249423Sdimnamespace { 24249423Sdim 25249423Sdim /// Class representing coefficient of floating-point addend. 26249423Sdim /// This class needs to be highly efficient, which is especially true for 27249423Sdim /// the constructor. As of I write this comment, the cost of the default 28251662Sdim /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 29249423Sdim /// perform write-merging). 30251662Sdim /// 31249423Sdim class FAddendCoef { 32249423Sdim public: 33249423Sdim // The constructor has to initialize a APFloat, which is uncessary for 34249423Sdim // most addends which have coefficient either 1 or -1. So, the constructor 35249423Sdim // is expensive. In order to avoid the cost of the constructor, we should 36249423Sdim // reuse some instances whenever possible. The pre-created instances 37249423Sdim // FAddCombine::Add[0-5] embodies this idea. 38249423Sdim // 39249423Sdim FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 40249423Sdim ~FAddendCoef(); 41251662Sdim 42249423Sdim void set(short C) { 43249423Sdim assert(!insaneIntVal(C) && "Insane coefficient"); 44249423Sdim IsFp = false; IntVal = C; 45249423Sdim } 46251662Sdim 47249423Sdim void set(const APFloat& C); 48249423Sdim 49249423Sdim void negate(); 50251662Sdim 51249423Sdim bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 52249423Sdim Value *getValue(Type *) const; 53251662Sdim 54249423Sdim // If possible, don't define operator+/operator- etc because these 55249423Sdim // operators inevitably call FAddendCoef's constructor which is not cheap. 56249423Sdim void operator=(const FAddendCoef &A); 57249423Sdim void operator+=(const FAddendCoef &A); 58249423Sdim void operator-=(const FAddendCoef &A); 59249423Sdim void operator*=(const FAddendCoef &S); 60251662Sdim 61249423Sdim bool isOne() const { return isInt() && IntVal == 1; } 62249423Sdim bool isTwo() const { return isInt() && IntVal == 2; } 63249423Sdim bool isMinusOne() const { return isInt() && IntVal == -1; } 64249423Sdim bool isMinusTwo() const { return isInt() && IntVal == -2; } 65251662Sdim 66249423Sdim private: 67249423Sdim bool insaneIntVal(int V) { return V > 4 || V < -4; } 68249423Sdim APFloat *getFpValPtr(void) 69249423Sdim { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 70249423Sdim const APFloat *getFpValPtr(void) const 71249423Sdim { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 72249423Sdim 73249423Sdim const APFloat &getFpVal(void) const { 74249423Sdim assert(IsFp && BufHasFpVal && "Incorret state"); 75249423Sdim return *getFpValPtr(); 76249423Sdim } 77249423Sdim 78251662Sdim APFloat &getFpVal(void) { 79251662Sdim assert(IsFp && BufHasFpVal && "Incorret state"); 80251662Sdim return *getFpValPtr(); 81251662Sdim } 82251662Sdim 83249423Sdim bool isInt() const { return !IsFp; } 84249423Sdim 85249423Sdim // If the coefficient is represented by an integer, promote it to a 86251662Sdim // floating point. 87249423Sdim void convertToFpType(const fltSemantics &Sem); 88249423Sdim 89249423Sdim // Construct an APFloat from a signed integer. 90249423Sdim // TODO: We should get rid of this function when APFloat can be constructed 91251662Sdim // from an *SIGNED* integer. 92249423Sdim APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 93249423Sdim private: 94249423Sdim 95249423Sdim bool IsFp; 96251662Sdim 97249423Sdim // True iff FpValBuf contains an instance of APFloat. 98249423Sdim bool BufHasFpVal; 99251662Sdim 100249423Sdim // The integer coefficient of an individual addend is either 1 or -1, 101249423Sdim // and we try to simplify at most 4 addends from neighboring at most 102249423Sdim // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 103249423Sdim // is overkill of this end. 104249423Sdim short IntVal; 105249423Sdim 106249423Sdim AlignedCharArrayUnion<APFloat> FpValBuf; 107249423Sdim }; 108251662Sdim 109249423Sdim /// FAddend is used to represent floating-point addend. An addend is 110249423Sdim /// represented as <C, V>, where the V is a symbolic value, and C is a 111249423Sdim /// constant coefficient. A constant addend is represented as <C, 0>. 112249423Sdim /// 113249423Sdim class FAddend { 114249423Sdim public: 115249423Sdim FAddend() { Val = 0; } 116251662Sdim 117249423Sdim Value *getSymVal (void) const { return Val; } 118249423Sdim const FAddendCoef &getCoef(void) const { return Coeff; } 119251662Sdim 120249423Sdim bool isConstant() const { return Val == 0; } 121249423Sdim bool isZero() const { return Coeff.isZero(); } 122249423Sdim 123249423Sdim void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 124249423Sdim void set(const APFloat& Coefficient, Value *V) 125249423Sdim { Coeff.set(Coefficient); Val = V; } 126249423Sdim void set(const ConstantFP* Coefficient, Value *V) 127249423Sdim { Coeff.set(Coefficient->getValueAPF()); Val = V; } 128251662Sdim 129249423Sdim void negate() { Coeff.negate(); } 130251662Sdim 131249423Sdim /// Drill down the U-D chain one step to find the definition of V, and 132249423Sdim /// try to break the definition into one or two addends. 133249423Sdim static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 134251662Sdim 135249423Sdim /// Similar to FAddend::drillDownOneStep() except that the value being 136249423Sdim /// splitted is the addend itself. 137249423Sdim unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 138251662Sdim 139249423Sdim void operator+=(const FAddend &T) { 140249423Sdim assert((Val == T.Val) && "Symbolic-values disagree"); 141249423Sdim Coeff += T.Coeff; 142249423Sdim } 143249423Sdim 144249423Sdim private: 145249423Sdim void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 146251662Sdim 147249423Sdim // This addend has the value of "Coeff * Val". 148249423Sdim Value *Val; 149249423Sdim FAddendCoef Coeff; 150249423Sdim }; 151251662Sdim 152249423Sdim /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 153249423Sdim /// with its neighboring at most two instructions. 154249423Sdim /// 155249423Sdim class FAddCombine { 156249423Sdim public: 157249423Sdim FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {} 158249423Sdim Value *simplify(Instruction *FAdd); 159251662Sdim 160249423Sdim private: 161249423Sdim typedef SmallVector<const FAddend*, 4> AddendVect; 162251662Sdim 163249423Sdim Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 164249423Sdim 165249423Sdim Value *performFactorization(Instruction *I); 166249423Sdim 167249423Sdim /// Convert given addend to a Value 168249423Sdim Value *createAddendVal(const FAddend &A, bool& NeedNeg); 169251662Sdim 170249423Sdim /// Return the number of instructions needed to emit the N-ary addition. 171249423Sdim unsigned calcInstrNumber(const AddendVect& Vect); 172249423Sdim Value *createFSub(Value *Opnd0, Value *Opnd1); 173249423Sdim Value *createFAdd(Value *Opnd0, Value *Opnd1); 174249423Sdim Value *createFMul(Value *Opnd0, Value *Opnd1); 175249423Sdim Value *createFDiv(Value *Opnd0, Value *Opnd1); 176249423Sdim Value *createFNeg(Value *V); 177249423Sdim Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 178249423Sdim void createInstPostProc(Instruction *NewInst); 179251662Sdim 180249423Sdim InstCombiner::BuilderTy *Builder; 181249423Sdim Instruction *Instr; 182251662Sdim 183249423Sdim private: 184249423Sdim // Debugging stuff are clustered here. 185249423Sdim #ifndef NDEBUG 186249423Sdim unsigned CreateInstrNum; 187249423Sdim void initCreateInstNum() { CreateInstrNum = 0; } 188249423Sdim void incCreateInstNum() { CreateInstrNum++; } 189249423Sdim #else 190249423Sdim void initCreateInstNum() {} 191249423Sdim void incCreateInstNum() {} 192249423Sdim #endif 193249423Sdim }; 194251662Sdim} 195249423Sdim 196249423Sdim//===----------------------------------------------------------------------===// 197249423Sdim// 198249423Sdim// Implementation of 199249423Sdim// {FAddendCoef, FAddend, FAddition, FAddCombine}. 200249423Sdim// 201249423Sdim//===----------------------------------------------------------------------===// 202249423SdimFAddendCoef::~FAddendCoef() { 203249423Sdim if (BufHasFpVal) 204249423Sdim getFpValPtr()->~APFloat(); 205249423Sdim} 206249423Sdim 207249423Sdimvoid FAddendCoef::set(const APFloat& C) { 208249423Sdim APFloat *P = getFpValPtr(); 209249423Sdim 210249423Sdim if (isInt()) { 211249423Sdim // As the buffer is meanless byte stream, we cannot call 212249423Sdim // APFloat::operator=(). 213249423Sdim new(P) APFloat(C); 214249423Sdim } else 215249423Sdim *P = C; 216249423Sdim 217251662Sdim IsFp = BufHasFpVal = true; 218249423Sdim} 219249423Sdim 220249423Sdimvoid FAddendCoef::convertToFpType(const fltSemantics &Sem) { 221249423Sdim if (!isInt()) 222249423Sdim return; 223249423Sdim 224249423Sdim APFloat *P = getFpValPtr(); 225249423Sdim if (IntVal > 0) 226249423Sdim new(P) APFloat(Sem, IntVal); 227249423Sdim else { 228249423Sdim new(P) APFloat(Sem, 0 - IntVal); 229249423Sdim P->changeSign(); 230249423Sdim } 231251662Sdim IsFp = BufHasFpVal = true; 232249423Sdim} 233249423Sdim 234249423SdimAPFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 235249423Sdim if (Val >= 0) 236249423Sdim return APFloat(Sem, Val); 237249423Sdim 238249423Sdim APFloat T(Sem, 0 - Val); 239249423Sdim T.changeSign(); 240249423Sdim 241249423Sdim return T; 242249423Sdim} 243249423Sdim 244249423Sdimvoid FAddendCoef::operator=(const FAddendCoef &That) { 245249423Sdim if (That.isInt()) 246249423Sdim set(That.IntVal); 247249423Sdim else 248249423Sdim set(That.getFpVal()); 249249423Sdim} 250249423Sdim 251249423Sdimvoid FAddendCoef::operator+=(const FAddendCoef &That) { 252249423Sdim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 253249423Sdim if (isInt() == That.isInt()) { 254249423Sdim if (isInt()) 255249423Sdim IntVal += That.IntVal; 256249423Sdim else 257249423Sdim getFpVal().add(That.getFpVal(), RndMode); 258249423Sdim return; 259249423Sdim } 260251662Sdim 261249423Sdim if (isInt()) { 262249423Sdim const APFloat &T = That.getFpVal(); 263249423Sdim convertToFpType(T.getSemantics()); 264249423Sdim getFpVal().add(T, RndMode); 265249423Sdim return; 266249423Sdim } 267251662Sdim 268249423Sdim APFloat &T = getFpVal(); 269249423Sdim T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 270249423Sdim} 271249423Sdim 272249423Sdimvoid FAddendCoef::operator-=(const FAddendCoef &That) { 273249423Sdim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 274249423Sdim if (isInt() == That.isInt()) { 275249423Sdim if (isInt()) 276249423Sdim IntVal -= That.IntVal; 277249423Sdim else 278249423Sdim getFpVal().subtract(That.getFpVal(), RndMode); 279249423Sdim return; 280249423Sdim } 281251662Sdim 282249423Sdim if (isInt()) { 283249423Sdim const APFloat &T = That.getFpVal(); 284249423Sdim convertToFpType(T.getSemantics()); 285249423Sdim getFpVal().subtract(T, RndMode); 286249423Sdim return; 287249423Sdim } 288249423Sdim 289249423Sdim APFloat &T = getFpVal(); 290249423Sdim T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 291249423Sdim} 292249423Sdim 293249423Sdimvoid FAddendCoef::operator*=(const FAddendCoef &That) { 294249423Sdim if (That.isOne()) 295249423Sdim return; 296249423Sdim 297249423Sdim if (That.isMinusOne()) { 298249423Sdim negate(); 299249423Sdim return; 300249423Sdim } 301249423Sdim 302249423Sdim if (isInt() && That.isInt()) { 303249423Sdim int Res = IntVal * (int)That.IntVal; 304249423Sdim assert(!insaneIntVal(Res) && "Insane int value"); 305249423Sdim IntVal = Res; 306249423Sdim return; 307249423Sdim } 308249423Sdim 309251662Sdim const fltSemantics &Semantic = 310249423Sdim isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 311249423Sdim 312249423Sdim if (isInt()) 313249423Sdim convertToFpType(Semantic); 314249423Sdim APFloat &F0 = getFpVal(); 315249423Sdim 316249423Sdim if (That.isInt()) 317249423Sdim F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 318249423Sdim APFloat::rmNearestTiesToEven); 319249423Sdim else 320249423Sdim F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 321249423Sdim 322249423Sdim return; 323249423Sdim} 324249423Sdim 325249423Sdimvoid FAddendCoef::negate() { 326249423Sdim if (isInt()) 327249423Sdim IntVal = 0 - IntVal; 328249423Sdim else 329249423Sdim getFpVal().changeSign(); 330249423Sdim} 331249423Sdim 332249423SdimValue *FAddendCoef::getValue(Type *Ty) const { 333249423Sdim return isInt() ? 334249423Sdim ConstantFP::get(Ty, float(IntVal)) : 335249423Sdim ConstantFP::get(Ty->getContext(), getFpVal()); 336249423Sdim} 337249423Sdim 338249423Sdim// The definition of <Val> Addends 339249423Sdim// ========================================= 340249423Sdim// A + B <1, A>, <1,B> 341249423Sdim// A - B <1, A>, <1,B> 342249423Sdim// 0 - B <-1, B> 343249423Sdim// C * A, <C, A> 344251662Sdim// A + C <1, A> <C, NULL> 345249423Sdim// 0 +/- 0 <0, NULL> (corner case) 346249423Sdim// 347249423Sdim// Legend: A and B are not constant, C is constant 348251662Sdim// 349249423Sdimunsigned FAddend::drillValueDownOneStep 350249423Sdim (Value *Val, FAddend &Addend0, FAddend &Addend1) { 351249423Sdim Instruction *I = 0; 352249423Sdim if (Val == 0 || !(I = dyn_cast<Instruction>(Val))) 353249423Sdim return 0; 354249423Sdim 355249423Sdim unsigned Opcode = I->getOpcode(); 356249423Sdim 357249423Sdim if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 358249423Sdim ConstantFP *C0, *C1; 359249423Sdim Value *Opnd0 = I->getOperand(0); 360249423Sdim Value *Opnd1 = I->getOperand(1); 361249423Sdim if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 362249423Sdim Opnd0 = 0; 363249423Sdim 364249423Sdim if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 365249423Sdim Opnd1 = 0; 366249423Sdim 367249423Sdim if (Opnd0) { 368249423Sdim if (!C0) 369249423Sdim Addend0.set(1, Opnd0); 370249423Sdim else 371249423Sdim Addend0.set(C0, 0); 372249423Sdim } 373249423Sdim 374249423Sdim if (Opnd1) { 375249423Sdim FAddend &Addend = Opnd0 ? Addend1 : Addend0; 376249423Sdim if (!C1) 377249423Sdim Addend.set(1, Opnd1); 378249423Sdim else 379249423Sdim Addend.set(C1, 0); 380249423Sdim if (Opcode == Instruction::FSub) 381249423Sdim Addend.negate(); 382249423Sdim } 383249423Sdim 384249423Sdim if (Opnd0 || Opnd1) 385249423Sdim return Opnd0 && Opnd1 ? 2 : 1; 386249423Sdim 387249423Sdim // Both operands are zero. Weird! 388249423Sdim Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0); 389249423Sdim return 1; 390249423Sdim } 391249423Sdim 392249423Sdim if (I->getOpcode() == Instruction::FMul) { 393249423Sdim Value *V0 = I->getOperand(0); 394249423Sdim Value *V1 = I->getOperand(1); 395249423Sdim if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 396249423Sdim Addend0.set(C, V1); 397249423Sdim return 1; 398249423Sdim } 399249423Sdim 400249423Sdim if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 401249423Sdim Addend0.set(C, V0); 402249423Sdim return 1; 403249423Sdim } 404249423Sdim } 405249423Sdim 406249423Sdim return 0; 407249423Sdim} 408249423Sdim 409249423Sdim// Try to break *this* addend into two addends. e.g. Suppose this addend is 410249423Sdim// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 411249423Sdim// i.e. <2.3, X> and <2.3, Y>. 412249423Sdim// 413249423Sdimunsigned FAddend::drillAddendDownOneStep 414249423Sdim (FAddend &Addend0, FAddend &Addend1) const { 415249423Sdim if (isConstant()) 416249423Sdim return 0; 417249423Sdim 418249423Sdim unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 419251662Sdim if (!BreakNum || Coeff.isOne()) 420249423Sdim return BreakNum; 421249423Sdim 422249423Sdim Addend0.Scale(Coeff); 423249423Sdim 424249423Sdim if (BreakNum == 2) 425249423Sdim Addend1.Scale(Coeff); 426249423Sdim 427249423Sdim return BreakNum; 428249423Sdim} 429249423Sdim 430249423Sdim// Try to perform following optimization on the input instruction I. Return the 431249423Sdim// simplified expression if was successful; otherwise, return 0. 432249423Sdim// 433249423Sdim// Instruction "I" is Simplified into 434249423Sdim// ------------------------------------------------------- 435249423Sdim// (x * y) +/- (x * z) x * (y +/- z) 436249423Sdim// (y / x) +/- (z / x) (y +/- z) / x 437249423Sdim// 438249423SdimValue *FAddCombine::performFactorization(Instruction *I) { 439249423Sdim assert((I->getOpcode() == Instruction::FAdd || 440249423Sdim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 441251662Sdim 442249423Sdim Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 443249423Sdim Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 444251662Sdim 445249423Sdim if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 446249423Sdim return 0; 447249423Sdim 448249423Sdim bool isMpy = false; 449249423Sdim if (I0->getOpcode() == Instruction::FMul) 450249423Sdim isMpy = true; 451249423Sdim else if (I0->getOpcode() != Instruction::FDiv) 452249423Sdim return 0; 453249423Sdim 454249423Sdim Value *Opnd0_0 = I0->getOperand(0); 455249423Sdim Value *Opnd0_1 = I0->getOperand(1); 456249423Sdim Value *Opnd1_0 = I1->getOperand(0); 457249423Sdim Value *Opnd1_1 = I1->getOperand(1); 458249423Sdim 459251662Sdim // Input Instr I Factor AddSub0 AddSub1 460249423Sdim // ---------------------------------------------- 461249423Sdim // (x*y) +/- (x*z) x y z 462249423Sdim // (y/x) +/- (z/x) x y z 463249423Sdim // 464249423Sdim Value *Factor = 0; 465249423Sdim Value *AddSub0 = 0, *AddSub1 = 0; 466251662Sdim 467249423Sdim if (isMpy) { 468249423Sdim if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 469249423Sdim Factor = Opnd0_0; 470249423Sdim else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 471249423Sdim Factor = Opnd0_1; 472249423Sdim 473249423Sdim if (Factor) { 474249423Sdim AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 475249423Sdim AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 476249423Sdim } 477249423Sdim } else if (Opnd0_1 == Opnd1_1) { 478249423Sdim Factor = Opnd0_1; 479249423Sdim AddSub0 = Opnd0_0; 480249423Sdim AddSub1 = Opnd1_0; 481249423Sdim } 482249423Sdim 483249423Sdim if (!Factor) 484249423Sdim return 0; 485249423Sdim 486249423Sdim // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 487249423Sdim Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 488249423Sdim createFAdd(AddSub0, AddSub1) : 489249423Sdim createFSub(AddSub0, AddSub1); 490249423Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 491249423Sdim const APFloat &F = CFP->getValueAPF(); 492263508Sdim if (!F.isNormal()) 493249423Sdim return 0; 494249423Sdim } 495249423Sdim 496249423Sdim if (isMpy) 497249423Sdim return createFMul(Factor, NewAddSub); 498251662Sdim 499249423Sdim return createFDiv(NewAddSub, Factor); 500249423Sdim} 501249423Sdim 502249423SdimValue *FAddCombine::simplify(Instruction *I) { 503249423Sdim assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 504249423Sdim 505249423Sdim // Currently we are not able to handle vector type. 506249423Sdim if (I->getType()->isVectorTy()) 507249423Sdim return 0; 508249423Sdim 509249423Sdim assert((I->getOpcode() == Instruction::FAdd || 510249423Sdim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 511249423Sdim 512251662Sdim // Save the instruction before calling other member-functions. 513249423Sdim Instr = I; 514249423Sdim 515249423Sdim FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 516249423Sdim 517249423Sdim unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 518249423Sdim 519249423Sdim // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 520249423Sdim unsigned Opnd0_ExpNum = 0; 521249423Sdim unsigned Opnd1_ExpNum = 0; 522249423Sdim 523251662Sdim if (!Opnd0.isConstant()) 524249423Sdim Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 525249423Sdim 526249423Sdim // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 527249423Sdim if (OpndNum == 2 && !Opnd1.isConstant()) 528249423Sdim Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 529249423Sdim 530249423Sdim // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 531249423Sdim if (Opnd0_ExpNum && Opnd1_ExpNum) { 532249423Sdim AddendVect AllOpnds; 533249423Sdim AllOpnds.push_back(&Opnd0_0); 534249423Sdim AllOpnds.push_back(&Opnd1_0); 535249423Sdim if (Opnd0_ExpNum == 2) 536249423Sdim AllOpnds.push_back(&Opnd0_1); 537249423Sdim if (Opnd1_ExpNum == 2) 538249423Sdim AllOpnds.push_back(&Opnd1_1); 539249423Sdim 540249423Sdim // Compute instruction quota. We should save at least one instruction. 541249423Sdim unsigned InstQuota = 0; 542249423Sdim 543249423Sdim Value *V0 = I->getOperand(0); 544249423Sdim Value *V1 = I->getOperand(1); 545251662Sdim InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 546249423Sdim (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 547249423Sdim 548249423Sdim if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 549249423Sdim return R; 550249423Sdim } 551249423Sdim 552249423Sdim if (OpndNum != 2) { 553249423Sdim // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 554249423Sdim // splitted into two addends, say "V = X - Y", the instruction would have 555249423Sdim // been optimized into "I = Y - X" in the previous steps. 556249423Sdim // 557249423Sdim const FAddendCoef &CE = Opnd0.getCoef(); 558249423Sdim return CE.isOne() ? Opnd0.getSymVal() : 0; 559249423Sdim } 560249423Sdim 561249423Sdim // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 562249423Sdim if (Opnd1_ExpNum) { 563249423Sdim AddendVect AllOpnds; 564249423Sdim AllOpnds.push_back(&Opnd0); 565249423Sdim AllOpnds.push_back(&Opnd1_0); 566249423Sdim if (Opnd1_ExpNum == 2) 567249423Sdim AllOpnds.push_back(&Opnd1_1); 568249423Sdim 569249423Sdim if (Value *R = simplifyFAdd(AllOpnds, 1)) 570249423Sdim return R; 571249423Sdim } 572249423Sdim 573249423Sdim // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 574249423Sdim if (Opnd0_ExpNum) { 575249423Sdim AddendVect AllOpnds; 576249423Sdim AllOpnds.push_back(&Opnd1); 577249423Sdim AllOpnds.push_back(&Opnd0_0); 578249423Sdim if (Opnd0_ExpNum == 2) 579249423Sdim AllOpnds.push_back(&Opnd0_1); 580249423Sdim 581249423Sdim if (Value *R = simplifyFAdd(AllOpnds, 1)) 582249423Sdim return R; 583249423Sdim } 584249423Sdim 585251662Sdim // step 6: Try factorization as the last resort, 586249423Sdim return performFactorization(I); 587249423Sdim} 588249423Sdim 589249423SdimValue *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 590249423Sdim 591249423Sdim unsigned AddendNum = Addends.size(); 592249423Sdim assert(AddendNum <= 4 && "Too many addends"); 593249423Sdim 594251662Sdim // For saving intermediate results; 595249423Sdim unsigned NextTmpIdx = 0; 596249423Sdim FAddend TmpResult[3]; 597249423Sdim 598249423Sdim // Points to the constant addend of the resulting simplified expression. 599249423Sdim // If the resulting expr has constant-addend, this constant-addend is 600249423Sdim // desirable to reside at the top of the resulting expression tree. Placing 601249423Sdim // constant close to supper-expr(s) will potentially reveal some optimization 602249423Sdim // opportunities in super-expr(s). 603249423Sdim // 604249423Sdim const FAddend *ConstAdd = 0; 605249423Sdim 606249423Sdim // Simplified addends are placed <SimpVect>. 607249423Sdim AddendVect SimpVect; 608249423Sdim 609249423Sdim // The outer loop works on one symbolic-value at a time. Suppose the input 610251662Sdim // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 611249423Sdim // The symbolic-values will be processed in this order: x, y, z. 612249423Sdim // 613249423Sdim for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 614249423Sdim 615249423Sdim const FAddend *ThisAddend = Addends[SymIdx]; 616249423Sdim if (!ThisAddend) { 617249423Sdim // This addend was processed before. 618249423Sdim continue; 619249423Sdim } 620249423Sdim 621249423Sdim Value *Val = ThisAddend->getSymVal(); 622249423Sdim unsigned StartIdx = SimpVect.size(); 623249423Sdim SimpVect.push_back(ThisAddend); 624249423Sdim 625249423Sdim // The inner loop collects addends sharing same symbolic-value, and these 626249423Sdim // addends will be later on folded into a single addend. Following above 627249423Sdim // example, if the symbolic value "y" is being processed, the inner loop 628249423Sdim // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 629249423Sdim // be later on folded into "<b1+b2, y>". 630249423Sdim // 631249423Sdim for (unsigned SameSymIdx = SymIdx + 1; 632249423Sdim SameSymIdx < AddendNum; SameSymIdx++) { 633249423Sdim const FAddend *T = Addends[SameSymIdx]; 634249423Sdim if (T && T->getSymVal() == Val) { 635249423Sdim // Set null such that next iteration of the outer loop will not process 636249423Sdim // this addend again. 637251662Sdim Addends[SameSymIdx] = 0; 638249423Sdim SimpVect.push_back(T); 639249423Sdim } 640249423Sdim } 641249423Sdim 642249423Sdim // If multiple addends share same symbolic value, fold them together. 643249423Sdim if (StartIdx + 1 != SimpVect.size()) { 644249423Sdim FAddend &R = TmpResult[NextTmpIdx ++]; 645249423Sdim R = *SimpVect[StartIdx]; 646249423Sdim for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) 647249423Sdim R += *SimpVect[Idx]; 648249423Sdim 649249423Sdim // Pop all addends being folded and push the resulting folded addend. 650251662Sdim SimpVect.resize(StartIdx); 651249423Sdim if (Val != 0) { 652249423Sdim if (!R.isZero()) { 653249423Sdim SimpVect.push_back(&R); 654249423Sdim } 655249423Sdim } else { 656249423Sdim // Don't push constant addend at this time. It will be the last element 657249423Sdim // of <SimpVect>. 658249423Sdim ConstAdd = &R; 659249423Sdim } 660249423Sdim } 661249423Sdim } 662249423Sdim 663263508Sdim assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) && 664249423Sdim "out-of-bound access"); 665249423Sdim 666249423Sdim if (ConstAdd) 667249423Sdim SimpVect.push_back(ConstAdd); 668249423Sdim 669249423Sdim Value *Result; 670249423Sdim if (!SimpVect.empty()) 671249423Sdim Result = createNaryFAdd(SimpVect, InstrQuota); 672249423Sdim else { 673249423Sdim // The addition is folded to 0.0. 674249423Sdim Result = ConstantFP::get(Instr->getType(), 0.0); 675249423Sdim } 676249423Sdim 677249423Sdim return Result; 678249423Sdim} 679249423Sdim 680249423SdimValue *FAddCombine::createNaryFAdd 681249423Sdim (const AddendVect &Opnds, unsigned InstrQuota) { 682249423Sdim assert(!Opnds.empty() && "Expect at least one addend"); 683249423Sdim 684249423Sdim // Step 1: Check if the # of instructions needed exceeds the quota. 685251662Sdim // 686249423Sdim unsigned InstrNeeded = calcInstrNumber(Opnds); 687249423Sdim if (InstrNeeded > InstrQuota) 688249423Sdim return 0; 689249423Sdim 690249423Sdim initCreateInstNum(); 691249423Sdim 692249423Sdim // step 2: Emit the N-ary addition. 693249423Sdim // Note that at most three instructions are involved in Fadd-InstCombine: the 694249423Sdim // addition in question, and at most two neighboring instructions. 695249423Sdim // The resulting optimized addition should have at least one less instruction 696249423Sdim // than the original addition expression tree. This implies that the resulting 697249423Sdim // N-ary addition has at most two instructions, and we don't need to worry 698249423Sdim // about tree-height when constructing the N-ary addition. 699249423Sdim 700249423Sdim Value *LastVal = 0; 701249423Sdim bool LastValNeedNeg = false; 702249423Sdim 703249423Sdim // Iterate the addends, creating fadd/fsub using adjacent two addends. 704249423Sdim for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 705249423Sdim I != E; I++) { 706251662Sdim bool NeedNeg; 707249423Sdim Value *V = createAddendVal(**I, NeedNeg); 708249423Sdim if (!LastVal) { 709249423Sdim LastVal = V; 710249423Sdim LastValNeedNeg = NeedNeg; 711249423Sdim continue; 712249423Sdim } 713249423Sdim 714249423Sdim if (LastValNeedNeg == NeedNeg) { 715249423Sdim LastVal = createFAdd(LastVal, V); 716249423Sdim continue; 717249423Sdim } 718249423Sdim 719249423Sdim if (LastValNeedNeg) 720249423Sdim LastVal = createFSub(V, LastVal); 721249423Sdim else 722249423Sdim LastVal = createFSub(LastVal, V); 723249423Sdim 724249423Sdim LastValNeedNeg = false; 725249423Sdim } 726249423Sdim 727249423Sdim if (LastValNeedNeg) { 728249423Sdim LastVal = createFNeg(LastVal); 729249423Sdim } 730249423Sdim 731249423Sdim #ifndef NDEBUG 732251662Sdim assert(CreateInstrNum == InstrNeeded && 733249423Sdim "Inconsistent in instruction numbers"); 734249423Sdim #endif 735249423Sdim 736249423Sdim return LastVal; 737249423Sdim} 738249423Sdim 739249423SdimValue *FAddCombine::createFSub 740249423Sdim (Value *Opnd0, Value *Opnd1) { 741249423Sdim Value *V = Builder->CreateFSub(Opnd0, Opnd1); 742249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 743249423Sdim createInstPostProc(I); 744249423Sdim return V; 745249423Sdim} 746249423Sdim 747249423SdimValue *FAddCombine::createFNeg(Value *V) { 748249423Sdim Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0)); 749249423Sdim return createFSub(Zero, V); 750249423Sdim} 751249423Sdim 752249423SdimValue *FAddCombine::createFAdd 753249423Sdim (Value *Opnd0, Value *Opnd1) { 754249423Sdim Value *V = Builder->CreateFAdd(Opnd0, Opnd1); 755249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 756249423Sdim createInstPostProc(I); 757249423Sdim return V; 758249423Sdim} 759249423Sdim 760249423SdimValue *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { 761249423Sdim Value *V = Builder->CreateFMul(Opnd0, Opnd1); 762249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 763249423Sdim createInstPostProc(I); 764249423Sdim return V; 765249423Sdim} 766249423Sdim 767249423SdimValue *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { 768249423Sdim Value *V = Builder->CreateFDiv(Opnd0, Opnd1); 769249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 770249423Sdim createInstPostProc(I); 771249423Sdim return V; 772249423Sdim} 773249423Sdim 774249423Sdimvoid FAddCombine::createInstPostProc(Instruction *NewInstr) { 775249423Sdim NewInstr->setDebugLoc(Instr->getDebugLoc()); 776249423Sdim 777249423Sdim // Keep track of the number of instruction created. 778249423Sdim incCreateInstNum(); 779249423Sdim 780249423Sdim // Propagate fast-math flags 781249423Sdim NewInstr->setFastMathFlags(Instr->getFastMathFlags()); 782249423Sdim} 783249423Sdim 784249423Sdim// Return the number of instruction needed to emit the N-ary addition. 785249423Sdim// NOTE: Keep this function in sync with createAddendVal(). 786249423Sdimunsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { 787249423Sdim unsigned OpndNum = Opnds.size(); 788249423Sdim unsigned InstrNeeded = OpndNum - 1; 789249423Sdim 790251662Sdim // The number of addends in the form of "(-1)*x". 791251662Sdim unsigned NegOpndNum = 0; 792249423Sdim 793249423Sdim // Adjust the number of instructions needed to emit the N-ary add. 794249423Sdim for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 795249423Sdim I != E; I++) { 796249423Sdim const FAddend *Opnd = *I; 797249423Sdim if (Opnd->isConstant()) 798249423Sdim continue; 799249423Sdim 800249423Sdim const FAddendCoef &CE = Opnd->getCoef(); 801249423Sdim if (CE.isMinusOne() || CE.isMinusTwo()) 802249423Sdim NegOpndNum++; 803249423Sdim 804249423Sdim // Let the addend be "c * x". If "c == +/-1", the value of the addend 805249423Sdim // is immediately available; otherwise, it needs exactly one instruction 806249423Sdim // to evaluate the value. 807249423Sdim if (!CE.isMinusOne() && !CE.isOne()) 808249423Sdim InstrNeeded++; 809249423Sdim } 810249423Sdim if (NegOpndNum == OpndNum) 811249423Sdim InstrNeeded++; 812249423Sdim return InstrNeeded; 813249423Sdim} 814249423Sdim 815249423Sdim// Input Addend Value NeedNeg(output) 816249423Sdim// ================================================================ 817249423Sdim// Constant C C false 818249423Sdim// <+/-1, V> V coefficient is -1 819249423Sdim// <2/-2, V> "fadd V, V" coefficient is -2 820249423Sdim// <C, V> "fmul V, C" false 821249423Sdim// 822249423Sdim// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. 823249423SdimValue *FAddCombine::createAddendVal 824249423Sdim (const FAddend &Opnd, bool &NeedNeg) { 825249423Sdim const FAddendCoef &Coeff = Opnd.getCoef(); 826249423Sdim 827249423Sdim if (Opnd.isConstant()) { 828249423Sdim NeedNeg = false; 829249423Sdim return Coeff.getValue(Instr->getType()); 830249423Sdim } 831249423Sdim 832249423Sdim Value *OpndVal = Opnd.getSymVal(); 833249423Sdim 834249423Sdim if (Coeff.isMinusOne() || Coeff.isOne()) { 835249423Sdim NeedNeg = Coeff.isMinusOne(); 836249423Sdim return OpndVal; 837249423Sdim } 838249423Sdim 839249423Sdim if (Coeff.isTwo() || Coeff.isMinusTwo()) { 840249423Sdim NeedNeg = Coeff.isMinusTwo(); 841249423Sdim return createFAdd(OpndVal, OpndVal); 842249423Sdim } 843249423Sdim 844249423Sdim NeedNeg = false; 845249423Sdim return createFMul(OpndVal, Coeff.getValue(Instr->getType())); 846249423Sdim} 847249423Sdim 848202375Srdivacky/// AddOne - Add one to a ConstantInt. 849202375Srdivackystatic Constant *AddOne(Constant *C) { 850202375Srdivacky return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 851202375Srdivacky} 852249423Sdim 853202375Srdivacky/// SubOne - Subtract one from a ConstantInt. 854202375Srdivackystatic Constant *SubOne(ConstantInt *C) { 855202375Srdivacky return ConstantInt::get(C->getContext(), C->getValue()-1); 856202375Srdivacky} 857202375Srdivacky 858202375Srdivacky 859202375Srdivacky// dyn_castFoldableMul - If this value is a multiply that can be folded into 860202375Srdivacky// other computations (because it has a constant operand), return the 861202375Srdivacky// non-constant operand of the multiply, and set CST to point to the multiplier. 862202375Srdivacky// Otherwise, return null. 863202375Srdivacky// 864202375Srdivackystatic inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 865203954Srdivacky if (!V->hasOneUse() || !V->getType()->isIntegerTy()) 866202375Srdivacky return 0; 867249423Sdim 868202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 869202375Srdivacky if (I == 0) return 0; 870249423Sdim 871202375Srdivacky if (I->getOpcode() == Instruction::Mul) 872202375Srdivacky if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 873202375Srdivacky return I->getOperand(0); 874202375Srdivacky if (I->getOpcode() == Instruction::Shl) 875202375Srdivacky if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 876202375Srdivacky // The multiplier is really 1 << CST. 877202375Srdivacky uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 878202375Srdivacky uint32_t CSTVal = CST->getLimitedValue(BitWidth); 879202375Srdivacky CST = ConstantInt::get(V->getType()->getContext(), 880263508Sdim APInt::getOneBitSet(BitWidth, CSTVal)); 881202375Srdivacky return I->getOperand(0); 882202375Srdivacky } 883202375Srdivacky return 0; 884202375Srdivacky} 885202375Srdivacky 886202375Srdivacky 887202375Srdivacky/// WillNotOverflowSignedAdd - Return true if we can prove that: 888202375Srdivacky/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 889202375Srdivacky/// This basically requires proving that the add in the original type would not 890202375Srdivacky/// overflow to change the sign bit or have a carry out. 891202375Srdivackybool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 892202375Srdivacky // There are different heuristics we can use for this. Here are some simple 893202375Srdivacky // ones. 894249423Sdim 895249423Sdim // Add has the property that adding any two 2's complement numbers can only 896202375Srdivacky // have one carry bit which can change a sign. As such, if LHS and RHS each 897202375Srdivacky // have at least two sign bits, we know that the addition of the two values 898202375Srdivacky // will sign extend fine. 899202375Srdivacky if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 900202375Srdivacky return true; 901249423Sdim 902249423Sdim 903202375Srdivacky // If one of the operands only has one non-zero bit, and if the other operand 904202375Srdivacky // has a known-zero bit in a more significant place than it (not including the 905202375Srdivacky // sign bit) the ripple may go up to and fill the zero, but won't change the 906202375Srdivacky // sign. For example, (X & ~4) + 1. 907249423Sdim 908202375Srdivacky // TODO: Implement. 909249423Sdim 910202375Srdivacky return false; 911202375Srdivacky} 912202375Srdivacky 913202375SrdivackyInstruction *InstCombiner::visitAdd(BinaryOperator &I) { 914218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 915202375Srdivacky Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 916202375Srdivacky 917202375Srdivacky if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 918202375Srdivacky I.hasNoUnsignedWrap(), TD)) 919202375Srdivacky return ReplaceInstUsesWith(I, V); 920202375Srdivacky 921218893Sdim // (A*B)+(A*C) -> A*(B+C) etc 922218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 923218893Sdim return ReplaceInstUsesWith(I, V); 924202375Srdivacky 925218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 926218893Sdim // X + (signbit) --> X ^ signbit 927218893Sdim const APInt &Val = CI->getValue(); 928218893Sdim if (Val.isSignBit()) 929218893Sdim return BinaryOperator::CreateXor(LHS, RHS); 930249423Sdim 931218893Sdim // See if SimplifyDemandedBits can simplify this. This handles stuff like 932218893Sdim // (X & 254)+1 -> (X&254)|1 933218893Sdim if (SimplifyDemandedInstructionBits(I)) 934218893Sdim return &I; 935202375Srdivacky 936218893Sdim // zext(bool) + C -> bool ? C + 1 : C 937218893Sdim if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 938218893Sdim if (ZI->getSrcTy()->isIntegerTy(1)) 939218893Sdim return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 940249423Sdim 941218893Sdim Value *XorLHS = 0; ConstantInt *XorRHS = 0; 942218893Sdim if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 943202375Srdivacky uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 944218893Sdim const APInt &RHSVal = CI->getValue(); 945203954Srdivacky unsigned ExtendAmt = 0; 946203954Srdivacky // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 947203954Srdivacky // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 948203954Srdivacky if (XorRHS->getValue() == -RHSVal) { 949203954Srdivacky if (RHSVal.isPowerOf2()) 950203954Srdivacky ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 951203954Srdivacky else if (XorRHS->getValue().isPowerOf2()) 952203954Srdivacky ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 953202375Srdivacky } 954249423Sdim 955203954Srdivacky if (ExtendAmt) { 956203954Srdivacky APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 957203954Srdivacky if (!MaskedValueIsZero(XorLHS, Mask)) 958203954Srdivacky ExtendAmt = 0; 959202375Srdivacky } 960249423Sdim 961203954Srdivacky if (ExtendAmt) { 962203954Srdivacky Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 963203954Srdivacky Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 964203954Srdivacky return BinaryOperator::CreateAShr(NewShl, ShAmt); 965203954Srdivacky } 966234353Sdim 967234353Sdim // If this is a xor that was canonicalized from a sub, turn it back into 968234353Sdim // a sub and fuse this add with it. 969234353Sdim if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { 970234353Sdim IntegerType *IT = cast<IntegerType>(I.getType()); 971234353Sdim APInt LHSKnownOne(IT->getBitWidth(), 0); 972234353Sdim APInt LHSKnownZero(IT->getBitWidth(), 0); 973234353Sdim ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne); 974234353Sdim if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue()) 975234353Sdim return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), 976234353Sdim XorLHS); 977234353Sdim } 978251662Sdim // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C, 979251662Sdim // transform them into (X + (signbit ^ C)) 980251662Sdim if (XorRHS->getValue().isSignBit()) 981251662Sdim return BinaryOperator::CreateAdd(XorLHS, 982251662Sdim ConstantExpr::getXor(XorRHS, CI)); 983202375Srdivacky } 984202375Srdivacky } 985202375Srdivacky 986218893Sdim if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 987218893Sdim if (Instruction *NV = FoldOpIntoPhi(I)) 988218893Sdim return NV; 989218893Sdim 990203954Srdivacky if (I.getType()->isIntegerTy(1)) 991202375Srdivacky return BinaryOperator::CreateXor(LHS, RHS); 992202375Srdivacky 993218893Sdim // X + X --> X << 1 994218893Sdim if (LHS == RHS) { 995218893Sdim BinaryOperator *New = 996218893Sdim BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 997218893Sdim New->setHasNoSignedWrap(I.hasNoSignedWrap()); 998218893Sdim New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 999218893Sdim return New; 1000202375Srdivacky } 1001202375Srdivacky 1002202375Srdivacky // -A + B --> B - A 1003202375Srdivacky // -A + -B --> -(A + B) 1004202375Srdivacky if (Value *LHSV = dyn_castNegVal(LHS)) { 1005239462Sdim if (!isa<Constant>(RHS)) 1006239462Sdim if (Value *RHSV = dyn_castNegVal(RHS)) { 1007239462Sdim Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 1008239462Sdim return BinaryOperator::CreateNeg(NewAdd); 1009239462Sdim } 1010249423Sdim 1011202375Srdivacky return BinaryOperator::CreateSub(RHS, LHSV); 1012202375Srdivacky } 1013202375Srdivacky 1014202375Srdivacky // A + -B --> A - B 1015202375Srdivacky if (!isa<Constant>(RHS)) 1016202375Srdivacky if (Value *V = dyn_castNegVal(RHS)) 1017202375Srdivacky return BinaryOperator::CreateSub(LHS, V); 1018202375Srdivacky 1019202375Srdivacky 1020202375Srdivacky ConstantInt *C2; 1021202375Srdivacky if (Value *X = dyn_castFoldableMul(LHS, C2)) { 1022202375Srdivacky if (X == RHS) // X*C + X --> X * (C+1) 1023202375Srdivacky return BinaryOperator::CreateMul(RHS, AddOne(C2)); 1024202375Srdivacky 1025202375Srdivacky // X*C1 + X*C2 --> X * (C1+C2) 1026202375Srdivacky ConstantInt *C1; 1027202375Srdivacky if (X == dyn_castFoldableMul(RHS, C1)) 1028202375Srdivacky return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 1029202375Srdivacky } 1030202375Srdivacky 1031202375Srdivacky // X + X*C --> X * (C+1) 1032202375Srdivacky if (dyn_castFoldableMul(RHS, C2) == LHS) 1033202375Srdivacky return BinaryOperator::CreateMul(LHS, AddOne(C2)); 1034202375Srdivacky 1035202375Srdivacky // A+B --> A|B iff A and B have no bits set in common. 1036226633Sdim if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 1037202375Srdivacky APInt LHSKnownOne(IT->getBitWidth(), 0); 1038202375Srdivacky APInt LHSKnownZero(IT->getBitWidth(), 0); 1039234353Sdim ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne); 1040202375Srdivacky if (LHSKnownZero != 0) { 1041202375Srdivacky APInt RHSKnownOne(IT->getBitWidth(), 0); 1042202375Srdivacky APInt RHSKnownZero(IT->getBitWidth(), 0); 1043234353Sdim ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne); 1044249423Sdim 1045202375Srdivacky // No bits in common -> bitwise or. 1046202375Srdivacky if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 1047202375Srdivacky return BinaryOperator::CreateOr(LHS, RHS); 1048202375Srdivacky } 1049202375Srdivacky } 1050202375Srdivacky 1051202375Srdivacky // W*X + Y*Z --> W * (X+Z) iff W == Y 1052218893Sdim { 1053202375Srdivacky Value *W, *X, *Y, *Z; 1054202375Srdivacky if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 1055202375Srdivacky match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 1056202375Srdivacky if (W != Y) { 1057202375Srdivacky if (W == Z) { 1058202375Srdivacky std::swap(Y, Z); 1059202375Srdivacky } else if (Y == X) { 1060202375Srdivacky std::swap(W, X); 1061202375Srdivacky } else if (X == Z) { 1062202375Srdivacky std::swap(Y, Z); 1063202375Srdivacky std::swap(W, X); 1064202375Srdivacky } 1065202375Srdivacky } 1066202375Srdivacky 1067202375Srdivacky if (W == Y) { 1068202375Srdivacky Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 1069202375Srdivacky return BinaryOperator::CreateMul(W, NewAdd); 1070202375Srdivacky } 1071202375Srdivacky } 1072202375Srdivacky } 1073202375Srdivacky 1074202375Srdivacky if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 1075202375Srdivacky Value *X = 0; 1076202375Srdivacky if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 1077202375Srdivacky return BinaryOperator::CreateSub(SubOne(CRHS), X); 1078202375Srdivacky 1079202375Srdivacky // (X & FF00) + xx00 -> (X+xx00) & FF00 1080202375Srdivacky if (LHS->hasOneUse() && 1081218893Sdim match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 1082218893Sdim CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 1083218893Sdim // See if all bits from the first bit set in the Add RHS up are included 1084218893Sdim // in the mask. First, get the rightmost bit. 1085218893Sdim const APInt &AddRHSV = CRHS->getValue(); 1086249423Sdim 1087218893Sdim // Form a mask of all bits from the lowest bit added through the top. 1088218893Sdim APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 1089202375Srdivacky 1090218893Sdim // See if the and mask includes all of these bits. 1091218893Sdim APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 1092202375Srdivacky 1093218893Sdim if (AddRHSHighBits == AddRHSHighBitsAnd) { 1094218893Sdim // Okay, the xform is safe. Insert the new add pronto. 1095218893Sdim Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 1096218893Sdim return BinaryOperator::CreateAnd(NewAdd, C2); 1097202375Srdivacky } 1098202375Srdivacky } 1099202375Srdivacky 1100202375Srdivacky // Try to fold constant add into select arguments. 1101202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1102202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1103202375Srdivacky return R; 1104202375Srdivacky } 1105202375Srdivacky 1106202375Srdivacky // add (select X 0 (sub n A)) A --> select X A n 1107202375Srdivacky { 1108202375Srdivacky SelectInst *SI = dyn_cast<SelectInst>(LHS); 1109202375Srdivacky Value *A = RHS; 1110202375Srdivacky if (!SI) { 1111202375Srdivacky SI = dyn_cast<SelectInst>(RHS); 1112202375Srdivacky A = LHS; 1113202375Srdivacky } 1114202375Srdivacky if (SI && SI->hasOneUse()) { 1115202375Srdivacky Value *TV = SI->getTrueValue(); 1116202375Srdivacky Value *FV = SI->getFalseValue(); 1117202375Srdivacky Value *N; 1118202375Srdivacky 1119202375Srdivacky // Can we fold the add into the argument of the select? 1120202375Srdivacky // We check both true and false select arguments for a matching subtract. 1121218893Sdim if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 1122202375Srdivacky // Fold the add into the true select value. 1123202375Srdivacky return SelectInst::Create(SI->getCondition(), N, A); 1124249423Sdim 1125218893Sdim if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 1126202375Srdivacky // Fold the add into the false select value. 1127202375Srdivacky return SelectInst::Create(SI->getCondition(), A, N); 1128202375Srdivacky } 1129202375Srdivacky } 1130202375Srdivacky 1131202375Srdivacky // Check for (add (sext x), y), see if we can merge this into an 1132202375Srdivacky // integer add followed by a sext. 1133202375Srdivacky if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 1134202375Srdivacky // (add (sext x), cst) --> (sext (add x, cst')) 1135202375Srdivacky if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 1136249423Sdim Constant *CI = 1137202375Srdivacky ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 1138202375Srdivacky if (LHSConv->hasOneUse() && 1139202375Srdivacky ConstantExpr::getSExt(CI, I.getType()) == RHSC && 1140202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1141202375Srdivacky // Insert the new, smaller add. 1142249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1143202375Srdivacky CI, "addconv"); 1144202375Srdivacky return new SExtInst(NewAdd, I.getType()); 1145202375Srdivacky } 1146202375Srdivacky } 1147249423Sdim 1148202375Srdivacky // (add (sext x), (sext y)) --> (sext (add int x, y)) 1149202375Srdivacky if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 1150202375Srdivacky // Only do this if x/y have the same type, if at last one of them has a 1151202375Srdivacky // single use (so we don't increase the number of sexts), and if the 1152202375Srdivacky // integer add will not overflow. 1153202375Srdivacky if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1154202375Srdivacky (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1155202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1156202375Srdivacky RHSConv->getOperand(0))) { 1157202375Srdivacky // Insert the new integer add. 1158249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1159202375Srdivacky RHSConv->getOperand(0), "addconv"); 1160202375Srdivacky return new SExtInst(NewAdd, I.getType()); 1161202375Srdivacky } 1162202375Srdivacky } 1163202375Srdivacky } 1164202375Srdivacky 1165239462Sdim // Check for (x & y) + (x ^ y) 1166239462Sdim { 1167239462Sdim Value *A = 0, *B = 0; 1168239462Sdim if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && 1169239462Sdim (match(LHS, m_And(m_Specific(A), m_Specific(B))) || 1170239462Sdim match(LHS, m_And(m_Specific(B), m_Specific(A))))) 1171239462Sdim return BinaryOperator::CreateOr(A, B); 1172239462Sdim 1173239462Sdim if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && 1174239462Sdim (match(RHS, m_And(m_Specific(A), m_Specific(B))) || 1175239462Sdim match(RHS, m_And(m_Specific(B), m_Specific(A))))) 1176239462Sdim return BinaryOperator::CreateOr(A, B); 1177239462Sdim } 1178239462Sdim 1179202375Srdivacky return Changed ? &I : 0; 1180202375Srdivacky} 1181202375Srdivacky 1182202375SrdivackyInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 1183218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 1184202375Srdivacky Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 1185202375Srdivacky 1186249423Sdim if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD)) 1187249423Sdim return ReplaceInstUsesWith(I, V); 1188202375Srdivacky 1189263508Sdim if (isa<Constant>(RHS)) { 1190263508Sdim if (isa<PHINode>(LHS)) 1191263508Sdim if (Instruction *NV = FoldOpIntoPhi(I)) 1192263508Sdim return NV; 1193202375Srdivacky 1194263508Sdim if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1195263508Sdim if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1196263508Sdim return NV; 1197263508Sdim } 1198263508Sdim 1199202375Srdivacky // -A + B --> B - A 1200202375Srdivacky // -A + -B --> -(A + B) 1201202375Srdivacky if (Value *LHSV = dyn_castFNegVal(LHS)) 1202202375Srdivacky return BinaryOperator::CreateFSub(RHS, LHSV); 1203202375Srdivacky 1204202375Srdivacky // A + -B --> A - B 1205202375Srdivacky if (!isa<Constant>(RHS)) 1206202375Srdivacky if (Value *V = dyn_castFNegVal(RHS)) 1207202375Srdivacky return BinaryOperator::CreateFSub(LHS, V); 1208202375Srdivacky 1209204642Srdivacky // Check for (fadd double (sitofp x), y), see if we can merge this into an 1210202375Srdivacky // integer add followed by a promotion. 1211202375Srdivacky if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 1212204642Srdivacky // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 1213202375Srdivacky // ... if the constant fits in the integer value. This is useful for things 1214202375Srdivacky // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 1215202375Srdivacky // requires a constant pool load, and generally allows the add to be better 1216202375Srdivacky // instcombined. 1217202375Srdivacky if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 1218249423Sdim Constant *CI = 1219202375Srdivacky ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 1220202375Srdivacky if (LHSConv->hasOneUse() && 1221202375Srdivacky ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 1222202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1223202375Srdivacky // Insert the new integer add. 1224202375Srdivacky Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1225202375Srdivacky CI, "addconv"); 1226202375Srdivacky return new SIToFPInst(NewAdd, I.getType()); 1227202375Srdivacky } 1228202375Srdivacky } 1229249423Sdim 1230204642Srdivacky // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 1231202375Srdivacky if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 1232202375Srdivacky // Only do this if x/y have the same type, if at last one of them has a 1233202375Srdivacky // single use (so we don't increase the number of int->fp conversions), 1234202375Srdivacky // and if the integer add will not overflow. 1235202375Srdivacky if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1236202375Srdivacky (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1237202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1238202375Srdivacky RHSConv->getOperand(0))) { 1239202375Srdivacky // Insert the new integer add. 1240249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1241202375Srdivacky RHSConv->getOperand(0),"addconv"); 1242202375Srdivacky return new SIToFPInst(NewAdd, I.getType()); 1243202375Srdivacky } 1244202375Srdivacky } 1245202375Srdivacky } 1246249423Sdim 1247251662Sdim // select C, 0, B + select C, A, 0 -> select C, A, B 1248251662Sdim { 1249251662Sdim Value *A1, *B1, *C1, *A2, *B2, *C2; 1250251662Sdim if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) && 1251251662Sdim match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) { 1252251662Sdim if (C1 == C2) { 1253251662Sdim Constant *Z1=0, *Z2=0; 1254251662Sdim Value *A, *B, *C=C1; 1255251662Sdim if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) { 1256251662Sdim Z1 = dyn_cast<Constant>(A1); A = A2; 1257251662Sdim Z2 = dyn_cast<Constant>(B2); B = B1; 1258251662Sdim } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) { 1259251662Sdim Z1 = dyn_cast<Constant>(B1); B = B2; 1260251662Sdim Z2 = dyn_cast<Constant>(A2); A = A1; 1261251662Sdim } 1262251662Sdim 1263251662Sdim if (Z1 && Z2 && 1264251662Sdim (I.hasNoSignedZeros() || 1265251662Sdim (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) { 1266251662Sdim return SelectInst::Create(C, A, B); 1267251662Sdim } 1268251662Sdim } 1269251662Sdim } 1270251662Sdim } 1271251662Sdim 1272249423Sdim if (I.hasUnsafeAlgebra()) { 1273249423Sdim if (Value *V = FAddCombine(Builder).simplify(&I)) 1274249423Sdim return ReplaceInstUsesWith(I, V); 1275249423Sdim } 1276249423Sdim 1277202375Srdivacky return Changed ? &I : 0; 1278202375Srdivacky} 1279202375Srdivacky 1280202375Srdivacky 1281202375Srdivacky/// Optimize pointer differences into the same array into a size. Consider: 1282202375Srdivacky/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 1283202375Srdivacky/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 1284202375Srdivacky/// 1285202375SrdivackyValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 1286226633Sdim Type *Ty) { 1287202375Srdivacky assert(TD && "Must have target data info for this"); 1288249423Sdim 1289202375Srdivacky // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 1290202375Srdivacky // this. 1291202375Srdivacky bool Swapped = false; 1292234353Sdim GEPOperator *GEP1 = 0, *GEP2 = 0; 1293234353Sdim 1294202375Srdivacky // For now we require one side to be the base pointer "A" or a constant 1295234353Sdim // GEP derived from it. 1296234353Sdim if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1297202375Srdivacky // (gep X, ...) - X 1298202375Srdivacky if (LHSGEP->getOperand(0) == RHS) { 1299234353Sdim GEP1 = LHSGEP; 1300202375Srdivacky Swapped = false; 1301234353Sdim } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1302234353Sdim // (gep X, ...) - (gep X, ...) 1303234353Sdim if (LHSGEP->getOperand(0)->stripPointerCasts() == 1304234353Sdim RHSGEP->getOperand(0)->stripPointerCasts()) { 1305234353Sdim GEP2 = RHSGEP; 1306234353Sdim GEP1 = LHSGEP; 1307202375Srdivacky Swapped = false; 1308202375Srdivacky } 1309202375Srdivacky } 1310202375Srdivacky } 1311249423Sdim 1312234353Sdim if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1313202375Srdivacky // X - (gep X, ...) 1314202375Srdivacky if (RHSGEP->getOperand(0) == LHS) { 1315234353Sdim GEP1 = RHSGEP; 1316202375Srdivacky Swapped = true; 1317234353Sdim } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1318234353Sdim // (gep X, ...) - (gep X, ...) 1319234353Sdim if (RHSGEP->getOperand(0)->stripPointerCasts() == 1320234353Sdim LHSGEP->getOperand(0)->stripPointerCasts()) { 1321234353Sdim GEP2 = LHSGEP; 1322234353Sdim GEP1 = RHSGEP; 1323202375Srdivacky Swapped = true; 1324202375Srdivacky } 1325202375Srdivacky } 1326202375Srdivacky } 1327249423Sdim 1328234353Sdim // Avoid duplicating the arithmetic if GEP2 has non-constant indices and 1329234353Sdim // multiple users. 1330234353Sdim if (GEP1 == 0 || 1331234353Sdim (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse())) 1332202375Srdivacky return 0; 1333249423Sdim 1334202375Srdivacky // Emit the offset of the GEP and an intptr_t. 1335234353Sdim Value *Result = EmitGEPOffset(GEP1); 1336249423Sdim 1337202375Srdivacky // If we had a constant expression GEP on the other side offsetting the 1338202375Srdivacky // pointer, subtract it from the offset we have. 1339234353Sdim if (GEP2) { 1340234353Sdim Value *Offset = EmitGEPOffset(GEP2); 1341234353Sdim Result = Builder->CreateSub(Result, Offset); 1342202375Srdivacky } 1343202375Srdivacky 1344202375Srdivacky // If we have p - gep(p, ...) then we have to negate the result. 1345202375Srdivacky if (Swapped) 1346202375Srdivacky Result = Builder->CreateNeg(Result, "diff.neg"); 1347202375Srdivacky 1348202375Srdivacky return Builder->CreateIntCast(Result, Ty, true); 1349202375Srdivacky} 1350202375Srdivacky 1351202375Srdivacky 1352202375SrdivackyInstruction *InstCombiner::visitSub(BinaryOperator &I) { 1353202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1354202375Srdivacky 1355218893Sdim if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 1356218893Sdim I.hasNoUnsignedWrap(), TD)) 1357218893Sdim return ReplaceInstUsesWith(I, V); 1358202375Srdivacky 1359218893Sdim // (A*B)-(A*C) -> A*(B-C) etc 1360218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 1361218893Sdim return ReplaceInstUsesWith(I, V); 1362218893Sdim 1363202375Srdivacky // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 1364202375Srdivacky if (Value *V = dyn_castNegVal(Op1)) { 1365202375Srdivacky BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 1366202375Srdivacky Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 1367202375Srdivacky Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 1368202375Srdivacky return Res; 1369202375Srdivacky } 1370202375Srdivacky 1371203954Srdivacky if (I.getType()->isIntegerTy(1)) 1372202375Srdivacky return BinaryOperator::CreateXor(Op0, Op1); 1373218893Sdim 1374218893Sdim // Replace (-1 - A) with (~A). 1375218893Sdim if (match(Op0, m_AllOnes())) 1376218893Sdim return BinaryOperator::CreateNot(Op1); 1377249423Sdim 1378202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 1379202375Srdivacky // C - ~X == X + (1+C) 1380202375Srdivacky Value *X = 0; 1381202375Srdivacky if (match(Op1, m_Not(m_Value(X)))) 1382202375Srdivacky return BinaryOperator::CreateAdd(X, AddOne(C)); 1383202375Srdivacky 1384202375Srdivacky // -(X >>u 31) -> (X >>s 31) 1385202375Srdivacky // -(X >>s 31) -> (X >>u 31) 1386202375Srdivacky if (C->isZero()) { 1387218893Sdim Value *X; ConstantInt *CI; 1388218893Sdim if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 1389218893Sdim // Verify we are shifting out everything but the sign bit. 1390218893Sdim CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1391218893Sdim return BinaryOperator::CreateAShr(X, CI); 1392218893Sdim 1393218893Sdim if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 1394218893Sdim // Verify we are shifting out everything but the sign bit. 1395218893Sdim CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1396218893Sdim return BinaryOperator::CreateLShr(X, CI); 1397202375Srdivacky } 1398202375Srdivacky 1399202375Srdivacky // Try to fold constant sub into select arguments. 1400202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1401202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1402202375Srdivacky return R; 1403202375Srdivacky 1404218893Sdim // C-(X+C2) --> (C-C2)-X 1405218893Sdim ConstantInt *C2; 1406218893Sdim if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2)))) 1407218893Sdim return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 1408234353Sdim 1409234353Sdim if (SimplifyDemandedInstructionBits(I)) 1410234353Sdim return &I; 1411249423Sdim 1412249423Sdim // Fold (sub 0, (zext bool to B)) --> (sext bool to B) 1413249423Sdim if (C->isZero() && match(Op1, m_ZExt(m_Value(X)))) 1414249423Sdim if (X->getType()->isIntegerTy(1)) 1415249423Sdim return CastInst::CreateSExtOrBitCast(X, Op1->getType()); 1416249423Sdim 1417249423Sdim // Fold (sub 0, (sext bool to B)) --> (zext bool to B) 1418249423Sdim if (C->isZero() && match(Op1, m_SExt(m_Value(X)))) 1419249423Sdim if (X->getType()->isIntegerTy(1)) 1420249423Sdim return CastInst::CreateZExtOrBitCast(X, Op1->getType()); 1421202375Srdivacky } 1422202375Srdivacky 1423249423Sdim 1424218893Sdim { Value *Y; 1425218893Sdim // X-(X+Y) == -Y X-(Y+X) == -Y 1426218893Sdim if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 1427218893Sdim match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 1428218893Sdim return BinaryOperator::CreateNeg(Y); 1429249423Sdim 1430218893Sdim // (X-Y)-X == -Y 1431218893Sdim if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 1432218893Sdim return BinaryOperator::CreateNeg(Y); 1433218893Sdim } 1434249423Sdim 1435218893Sdim if (Op1->hasOneUse()) { 1436218893Sdim Value *X = 0, *Y = 0, *Z = 0; 1437218893Sdim Constant *C = 0; 1438218893Sdim ConstantInt *CI = 0; 1439202375Srdivacky 1440218893Sdim // (X - (Y - Z)) --> (X + (Z - Y)). 1441218893Sdim if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 1442218893Sdim return BinaryOperator::CreateAdd(Op0, 1443218893Sdim Builder->CreateSub(Z, Y, Op1->getName())); 1444202375Srdivacky 1445218893Sdim // (X - (X & Y)) --> (X & ~Y) 1446218893Sdim // 1447218893Sdim if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 1448218893Sdim match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 1449218893Sdim return BinaryOperator::CreateAnd(Op0, 1450218893Sdim Builder->CreateNot(Y, Y->getName() + ".not")); 1451249423Sdim 1452218893Sdim // 0 - (X sdiv C) -> (X sdiv -C) 1453218893Sdim if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && 1454218893Sdim match(Op0, m_Zero())) 1455218893Sdim return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 1456202375Srdivacky 1457218893Sdim // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 1458218893Sdim if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 1459218893Sdim if (Value *XNeg = dyn_castNegVal(X)) 1460218893Sdim return BinaryOperator::CreateShl(XNeg, Y); 1461202375Srdivacky 1462218893Sdim // X - X*C --> X * (1-C) 1463218893Sdim if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) { 1464218893Sdim Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); 1465218893Sdim return BinaryOperator::CreateMul(Op0, CP1); 1466202375Srdivacky } 1467202375Srdivacky 1468218893Sdim // X - X<<C --> X * (1-(1<<C)) 1469218893Sdim if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) { 1470218893Sdim Constant *One = ConstantInt::get(I.getType(), 1); 1471218893Sdim C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI)); 1472218893Sdim return BinaryOperator::CreateMul(Op0, C); 1473202375Srdivacky } 1474249423Sdim 1475218893Sdim // X - A*-B -> X + A*B 1476218893Sdim // X - -A*B -> X + A*B 1477218893Sdim Value *A, *B; 1478218893Sdim if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 1479218893Sdim match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 1480218893Sdim return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 1481249423Sdim 1482218893Sdim // X - A*CI -> X + A*-CI 1483218893Sdim // X - CI*A -> X + A*-CI 1484218893Sdim if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) || 1485218893Sdim match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) { 1486218893Sdim Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 1487218893Sdim return BinaryOperator::CreateAdd(Op0, NewMul); 1488218893Sdim } 1489202375Srdivacky } 1490202375Srdivacky 1491202375Srdivacky ConstantInt *C1; 1492202375Srdivacky if (Value *X = dyn_castFoldableMul(Op0, C1)) { 1493202375Srdivacky if (X == Op1) // X*C - X --> X * (C-1) 1494202375Srdivacky return BinaryOperator::CreateMul(Op1, SubOne(C1)); 1495202375Srdivacky 1496202375Srdivacky ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 1497202375Srdivacky if (X == dyn_castFoldableMul(Op1, C2)) 1498202375Srdivacky return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 1499202375Srdivacky } 1500249423Sdim 1501202375Srdivacky // Optimize pointer differences into the same array into a size. Consider: 1502202375Srdivacky // &A[10] - &A[0]: we should compile this to "10". 1503202375Srdivacky if (TD) { 1504202375Srdivacky Value *LHSOp, *RHSOp; 1505202375Srdivacky if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 1506202375Srdivacky match(Op1, m_PtrToInt(m_Value(RHSOp)))) 1507202375Srdivacky if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1508202375Srdivacky return ReplaceInstUsesWith(I, Res); 1509249423Sdim 1510202375Srdivacky // trunc(p)-trunc(q) -> trunc(p-q) 1511202375Srdivacky if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 1512202375Srdivacky match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 1513202375Srdivacky if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1514202375Srdivacky return ReplaceInstUsesWith(I, Res); 1515202375Srdivacky } 1516249423Sdim 1517202375Srdivacky return 0; 1518202375Srdivacky} 1519202375Srdivacky 1520202375SrdivackyInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 1521202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1522202375Srdivacky 1523249423Sdim if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD)) 1524249423Sdim return ReplaceInstUsesWith(I, V); 1525249423Sdim 1526263508Sdim if (isa<Constant>(Op0)) 1527263508Sdim if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1528263508Sdim if (Instruction *NV = FoldOpIntoSelect(I, SI)) 1529263508Sdim return NV; 1530202375Srdivacky 1531263508Sdim // If this is a 'B = x-(-A)', change to B = x+A, potentially looking 1532263508Sdim // through FP extensions/truncations along the way. 1533263508Sdim if (Value *V = dyn_castFNegVal(Op1)) { 1534263508Sdim Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V); 1535263508Sdim NewI->copyFastMathFlags(&I); 1536263508Sdim return NewI; 1537263508Sdim } 1538263508Sdim if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) { 1539263508Sdim if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) { 1540263508Sdim Value *NewTrunc = Builder->CreateFPTrunc(V, I.getType()); 1541263508Sdim Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc); 1542263508Sdim NewI->copyFastMathFlags(&I); 1543263508Sdim return NewI; 1544263508Sdim } 1545263508Sdim } else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) { 1546263508Sdim if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) { 1547263508Sdim Value *NewExt = Builder->CreateFPExt(V, I.getType()); 1548263508Sdim Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt); 1549263508Sdim NewI->copyFastMathFlags(&I); 1550263508Sdim return NewI; 1551263508Sdim } 1552263508Sdim } 1553263508Sdim 1554249423Sdim if (I.hasUnsafeAlgebra()) { 1555249423Sdim if (Value *V = FAddCombine(Builder).simplify(&I)) 1556249423Sdim return ReplaceInstUsesWith(I, V); 1557249423Sdim } 1558249423Sdim 1559202375Srdivacky return 0; 1560202375Srdivacky} 1561