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" 15202375Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 16249423Sdim#include "llvm/IR/DataLayout.h" 17202375Srdivacky#include "llvm/Support/GetElementPtrTypeIterator.h" 18202375Srdivacky#include "llvm/Support/PatternMatch.h" 19202375Srdivackyusing namespace llvm; 20202375Srdivackyusing namespace PatternMatch; 21202375Srdivacky 22249423Sdimnamespace { 23249423Sdim 24249423Sdim /// Class representing coefficient of floating-point addend. 25249423Sdim /// This class needs to be highly efficient, which is especially true for 26249423Sdim /// the constructor. As of I write this comment, the cost of the default 27251662Sdim /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 28249423Sdim /// perform write-merging). 29251662Sdim /// 30249423Sdim class FAddendCoef { 31249423Sdim public: 32249423Sdim // The constructor has to initialize a APFloat, which is uncessary for 33249423Sdim // most addends which have coefficient either 1 or -1. So, the constructor 34249423Sdim // is expensive. In order to avoid the cost of the constructor, we should 35249423Sdim // reuse some instances whenever possible. The pre-created instances 36249423Sdim // FAddCombine::Add[0-5] embodies this idea. 37249423Sdim // 38249423Sdim FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 39249423Sdim ~FAddendCoef(); 40251662Sdim 41249423Sdim void set(short C) { 42249423Sdim assert(!insaneIntVal(C) && "Insane coefficient"); 43249423Sdim IsFp = false; IntVal = C; 44249423Sdim } 45251662Sdim 46249423Sdim void set(const APFloat& C); 47249423Sdim 48249423Sdim void negate(); 49251662Sdim 50249423Sdim bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 51249423Sdim Value *getValue(Type *) const; 52251662Sdim 53249423Sdim // If possible, don't define operator+/operator- etc because these 54249423Sdim // operators inevitably call FAddendCoef's constructor which is not cheap. 55249423Sdim void operator=(const FAddendCoef &A); 56249423Sdim void operator+=(const FAddendCoef &A); 57249423Sdim void operator-=(const FAddendCoef &A); 58249423Sdim void operator*=(const FAddendCoef &S); 59251662Sdim 60249423Sdim bool isOne() const { return isInt() && IntVal == 1; } 61249423Sdim bool isTwo() const { return isInt() && IntVal == 2; } 62249423Sdim bool isMinusOne() const { return isInt() && IntVal == -1; } 63249423Sdim bool isMinusTwo() const { return isInt() && IntVal == -2; } 64251662Sdim 65249423Sdim private: 66249423Sdim bool insaneIntVal(int V) { return V > 4 || V < -4; } 67249423Sdim APFloat *getFpValPtr(void) 68249423Sdim { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 69249423Sdim const APFloat *getFpValPtr(void) const 70249423Sdim { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 71249423Sdim 72249423Sdim const APFloat &getFpVal(void) const { 73249423Sdim assert(IsFp && BufHasFpVal && "Incorret state"); 74249423Sdim return *getFpValPtr(); 75249423Sdim } 76249423Sdim 77251662Sdim APFloat &getFpVal(void) { 78251662Sdim assert(IsFp && BufHasFpVal && "Incorret state"); 79251662Sdim return *getFpValPtr(); 80251662Sdim } 81251662Sdim 82249423Sdim bool isInt() const { return !IsFp; } 83249423Sdim 84249423Sdim // If the coefficient is represented by an integer, promote it to a 85251662Sdim // floating point. 86249423Sdim void convertToFpType(const fltSemantics &Sem); 87249423Sdim 88249423Sdim // Construct an APFloat from a signed integer. 89249423Sdim // TODO: We should get rid of this function when APFloat can be constructed 90251662Sdim // from an *SIGNED* integer. 91249423Sdim APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 92249423Sdim private: 93249423Sdim 94249423Sdim bool IsFp; 95251662Sdim 96249423Sdim // True iff FpValBuf contains an instance of APFloat. 97249423Sdim bool BufHasFpVal; 98251662Sdim 99249423Sdim // The integer coefficient of an individual addend is either 1 or -1, 100249423Sdim // and we try to simplify at most 4 addends from neighboring at most 101249423Sdim // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 102249423Sdim // is overkill of this end. 103249423Sdim short IntVal; 104249423Sdim 105249423Sdim AlignedCharArrayUnion<APFloat> FpValBuf; 106249423Sdim }; 107251662Sdim 108249423Sdim /// FAddend is used to represent floating-point addend. An addend is 109249423Sdim /// represented as <C, V>, where the V is a symbolic value, and C is a 110249423Sdim /// constant coefficient. A constant addend is represented as <C, 0>. 111249423Sdim /// 112249423Sdim class FAddend { 113249423Sdim public: 114249423Sdim FAddend() { Val = 0; } 115251662Sdim 116249423Sdim Value *getSymVal (void) const { return Val; } 117249423Sdim const FAddendCoef &getCoef(void) const { return Coeff; } 118251662Sdim 119249423Sdim bool isConstant() const { return Val == 0; } 120249423Sdim bool isZero() const { return Coeff.isZero(); } 121249423Sdim 122249423Sdim void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 123249423Sdim void set(const APFloat& Coefficient, Value *V) 124249423Sdim { Coeff.set(Coefficient); Val = V; } 125249423Sdim void set(const ConstantFP* Coefficient, Value *V) 126249423Sdim { Coeff.set(Coefficient->getValueAPF()); Val = V; } 127251662Sdim 128249423Sdim void negate() { Coeff.negate(); } 129251662Sdim 130249423Sdim /// Drill down the U-D chain one step to find the definition of V, and 131249423Sdim /// try to break the definition into one or two addends. 132249423Sdim static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 133251662Sdim 134249423Sdim /// Similar to FAddend::drillDownOneStep() except that the value being 135249423Sdim /// splitted is the addend itself. 136249423Sdim unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 137251662Sdim 138249423Sdim void operator+=(const FAddend &T) { 139249423Sdim assert((Val == T.Val) && "Symbolic-values disagree"); 140249423Sdim Coeff += T.Coeff; 141249423Sdim } 142249423Sdim 143249423Sdim private: 144249423Sdim void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 145251662Sdim 146249423Sdim // This addend has the value of "Coeff * Val". 147249423Sdim Value *Val; 148249423Sdim FAddendCoef Coeff; 149249423Sdim }; 150251662Sdim 151249423Sdim /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 152249423Sdim /// with its neighboring at most two instructions. 153249423Sdim /// 154249423Sdim class FAddCombine { 155249423Sdim public: 156249423Sdim FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {} 157249423Sdim Value *simplify(Instruction *FAdd); 158251662Sdim 159249423Sdim private: 160249423Sdim typedef SmallVector<const FAddend*, 4> AddendVect; 161251662Sdim 162249423Sdim Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 163249423Sdim 164249423Sdim Value *performFactorization(Instruction *I); 165249423Sdim 166249423Sdim /// Convert given addend to a Value 167249423Sdim Value *createAddendVal(const FAddend &A, bool& NeedNeg); 168251662Sdim 169249423Sdim /// Return the number of instructions needed to emit the N-ary addition. 170249423Sdim unsigned calcInstrNumber(const AddendVect& Vect); 171249423Sdim Value *createFSub(Value *Opnd0, Value *Opnd1); 172249423Sdim Value *createFAdd(Value *Opnd0, Value *Opnd1); 173249423Sdim Value *createFMul(Value *Opnd0, Value *Opnd1); 174249423Sdim Value *createFDiv(Value *Opnd0, Value *Opnd1); 175249423Sdim Value *createFNeg(Value *V); 176249423Sdim Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 177249423Sdim void createInstPostProc(Instruction *NewInst); 178251662Sdim 179249423Sdim InstCombiner::BuilderTy *Builder; 180249423Sdim Instruction *Instr; 181251662Sdim 182249423Sdim private: 183249423Sdim // Debugging stuff are clustered here. 184249423Sdim #ifndef NDEBUG 185249423Sdim unsigned CreateInstrNum; 186249423Sdim void initCreateInstNum() { CreateInstrNum = 0; } 187249423Sdim void incCreateInstNum() { CreateInstrNum++; } 188249423Sdim #else 189249423Sdim void initCreateInstNum() {} 190249423Sdim void incCreateInstNum() {} 191249423Sdim #endif 192249423Sdim }; 193251662Sdim} 194249423Sdim 195249423Sdim//===----------------------------------------------------------------------===// 196249423Sdim// 197249423Sdim// Implementation of 198249423Sdim// {FAddendCoef, FAddend, FAddition, FAddCombine}. 199249423Sdim// 200249423Sdim//===----------------------------------------------------------------------===// 201249423SdimFAddendCoef::~FAddendCoef() { 202249423Sdim if (BufHasFpVal) 203249423Sdim getFpValPtr()->~APFloat(); 204249423Sdim} 205249423Sdim 206249423Sdimvoid FAddendCoef::set(const APFloat& C) { 207249423Sdim APFloat *P = getFpValPtr(); 208249423Sdim 209249423Sdim if (isInt()) { 210249423Sdim // As the buffer is meanless byte stream, we cannot call 211249423Sdim // APFloat::operator=(). 212249423Sdim new(P) APFloat(C); 213249423Sdim } else 214249423Sdim *P = C; 215249423Sdim 216251662Sdim IsFp = BufHasFpVal = true; 217249423Sdim} 218249423Sdim 219249423Sdimvoid FAddendCoef::convertToFpType(const fltSemantics &Sem) { 220249423Sdim if (!isInt()) 221249423Sdim return; 222249423Sdim 223249423Sdim APFloat *P = getFpValPtr(); 224249423Sdim if (IntVal > 0) 225249423Sdim new(P) APFloat(Sem, IntVal); 226249423Sdim else { 227249423Sdim new(P) APFloat(Sem, 0 - IntVal); 228249423Sdim P->changeSign(); 229249423Sdim } 230251662Sdim IsFp = BufHasFpVal = true; 231249423Sdim} 232249423Sdim 233249423SdimAPFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 234249423Sdim if (Val >= 0) 235249423Sdim return APFloat(Sem, Val); 236249423Sdim 237249423Sdim APFloat T(Sem, 0 - Val); 238249423Sdim T.changeSign(); 239249423Sdim 240249423Sdim return T; 241249423Sdim} 242249423Sdim 243249423Sdimvoid FAddendCoef::operator=(const FAddendCoef &That) { 244249423Sdim if (That.isInt()) 245249423Sdim set(That.IntVal); 246249423Sdim else 247249423Sdim set(That.getFpVal()); 248249423Sdim} 249249423Sdim 250249423Sdimvoid FAddendCoef::operator+=(const FAddendCoef &That) { 251249423Sdim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 252249423Sdim if (isInt() == That.isInt()) { 253249423Sdim if (isInt()) 254249423Sdim IntVal += That.IntVal; 255249423Sdim else 256249423Sdim getFpVal().add(That.getFpVal(), RndMode); 257249423Sdim return; 258249423Sdim } 259251662Sdim 260249423Sdim if (isInt()) { 261249423Sdim const APFloat &T = That.getFpVal(); 262249423Sdim convertToFpType(T.getSemantics()); 263249423Sdim getFpVal().add(T, RndMode); 264249423Sdim return; 265249423Sdim } 266251662Sdim 267249423Sdim APFloat &T = getFpVal(); 268249423Sdim T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 269249423Sdim} 270249423Sdim 271249423Sdimvoid FAddendCoef::operator-=(const FAddendCoef &That) { 272249423Sdim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 273249423Sdim if (isInt() == That.isInt()) { 274249423Sdim if (isInt()) 275249423Sdim IntVal -= That.IntVal; 276249423Sdim else 277249423Sdim getFpVal().subtract(That.getFpVal(), RndMode); 278249423Sdim return; 279249423Sdim } 280251662Sdim 281249423Sdim if (isInt()) { 282249423Sdim const APFloat &T = That.getFpVal(); 283249423Sdim convertToFpType(T.getSemantics()); 284249423Sdim getFpVal().subtract(T, RndMode); 285249423Sdim return; 286249423Sdim } 287249423Sdim 288249423Sdim APFloat &T = getFpVal(); 289249423Sdim T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 290249423Sdim} 291249423Sdim 292249423Sdimvoid FAddendCoef::operator*=(const FAddendCoef &That) { 293249423Sdim if (That.isOne()) 294249423Sdim return; 295249423Sdim 296249423Sdim if (That.isMinusOne()) { 297249423Sdim negate(); 298249423Sdim return; 299249423Sdim } 300249423Sdim 301249423Sdim if (isInt() && That.isInt()) { 302249423Sdim int Res = IntVal * (int)That.IntVal; 303249423Sdim assert(!insaneIntVal(Res) && "Insane int value"); 304249423Sdim IntVal = Res; 305249423Sdim return; 306249423Sdim } 307249423Sdim 308251662Sdim const fltSemantics &Semantic = 309249423Sdim isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 310249423Sdim 311249423Sdim if (isInt()) 312249423Sdim convertToFpType(Semantic); 313249423Sdim APFloat &F0 = getFpVal(); 314249423Sdim 315249423Sdim if (That.isInt()) 316249423Sdim F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 317249423Sdim APFloat::rmNearestTiesToEven); 318249423Sdim else 319249423Sdim F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 320249423Sdim 321249423Sdim return; 322249423Sdim} 323249423Sdim 324249423Sdimvoid FAddendCoef::negate() { 325249423Sdim if (isInt()) 326249423Sdim IntVal = 0 - IntVal; 327249423Sdim else 328249423Sdim getFpVal().changeSign(); 329249423Sdim} 330249423Sdim 331249423SdimValue *FAddendCoef::getValue(Type *Ty) const { 332249423Sdim return isInt() ? 333249423Sdim ConstantFP::get(Ty, float(IntVal)) : 334249423Sdim ConstantFP::get(Ty->getContext(), getFpVal()); 335249423Sdim} 336249423Sdim 337249423Sdim// The definition of <Val> Addends 338249423Sdim// ========================================= 339249423Sdim// A + B <1, A>, <1,B> 340249423Sdim// A - B <1, A>, <1,B> 341249423Sdim// 0 - B <-1, B> 342249423Sdim// C * A, <C, A> 343251662Sdim// A + C <1, A> <C, NULL> 344249423Sdim// 0 +/- 0 <0, NULL> (corner case) 345249423Sdim// 346249423Sdim// Legend: A and B are not constant, C is constant 347251662Sdim// 348249423Sdimunsigned FAddend::drillValueDownOneStep 349249423Sdim (Value *Val, FAddend &Addend0, FAddend &Addend1) { 350249423Sdim Instruction *I = 0; 351249423Sdim if (Val == 0 || !(I = dyn_cast<Instruction>(Val))) 352249423Sdim return 0; 353249423Sdim 354249423Sdim unsigned Opcode = I->getOpcode(); 355249423Sdim 356249423Sdim if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 357249423Sdim ConstantFP *C0, *C1; 358249423Sdim Value *Opnd0 = I->getOperand(0); 359249423Sdim Value *Opnd1 = I->getOperand(1); 360249423Sdim if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 361249423Sdim Opnd0 = 0; 362249423Sdim 363249423Sdim if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 364249423Sdim Opnd1 = 0; 365249423Sdim 366249423Sdim if (Opnd0) { 367249423Sdim if (!C0) 368249423Sdim Addend0.set(1, Opnd0); 369249423Sdim else 370249423Sdim Addend0.set(C0, 0); 371249423Sdim } 372249423Sdim 373249423Sdim if (Opnd1) { 374249423Sdim FAddend &Addend = Opnd0 ? Addend1 : Addend0; 375249423Sdim if (!C1) 376249423Sdim Addend.set(1, Opnd1); 377249423Sdim else 378249423Sdim Addend.set(C1, 0); 379249423Sdim if (Opcode == Instruction::FSub) 380249423Sdim Addend.negate(); 381249423Sdim } 382249423Sdim 383249423Sdim if (Opnd0 || Opnd1) 384249423Sdim return Opnd0 && Opnd1 ? 2 : 1; 385249423Sdim 386249423Sdim // Both operands are zero. Weird! 387249423Sdim Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0); 388249423Sdim return 1; 389249423Sdim } 390249423Sdim 391249423Sdim if (I->getOpcode() == Instruction::FMul) { 392249423Sdim Value *V0 = I->getOperand(0); 393249423Sdim Value *V1 = I->getOperand(1); 394249423Sdim if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 395249423Sdim Addend0.set(C, V1); 396249423Sdim return 1; 397249423Sdim } 398249423Sdim 399249423Sdim if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 400249423Sdim Addend0.set(C, V0); 401249423Sdim return 1; 402249423Sdim } 403249423Sdim } 404249423Sdim 405249423Sdim return 0; 406249423Sdim} 407249423Sdim 408249423Sdim// Try to break *this* addend into two addends. e.g. Suppose this addend is 409249423Sdim// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 410249423Sdim// i.e. <2.3, X> and <2.3, Y>. 411249423Sdim// 412249423Sdimunsigned FAddend::drillAddendDownOneStep 413249423Sdim (FAddend &Addend0, FAddend &Addend1) const { 414249423Sdim if (isConstant()) 415249423Sdim return 0; 416249423Sdim 417249423Sdim unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 418251662Sdim if (!BreakNum || Coeff.isOne()) 419249423Sdim return BreakNum; 420249423Sdim 421249423Sdim Addend0.Scale(Coeff); 422249423Sdim 423249423Sdim if (BreakNum == 2) 424249423Sdim Addend1.Scale(Coeff); 425249423Sdim 426249423Sdim return BreakNum; 427249423Sdim} 428249423Sdim 429249423Sdim// Try to perform following optimization on the input instruction I. Return the 430249423Sdim// simplified expression if was successful; otherwise, return 0. 431249423Sdim// 432249423Sdim// Instruction "I" is Simplified into 433249423Sdim// ------------------------------------------------------- 434249423Sdim// (x * y) +/- (x * z) x * (y +/- z) 435249423Sdim// (y / x) +/- (z / x) (y +/- z) / x 436249423Sdim// 437249423SdimValue *FAddCombine::performFactorization(Instruction *I) { 438249423Sdim assert((I->getOpcode() == Instruction::FAdd || 439249423Sdim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 440251662Sdim 441249423Sdim Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 442249423Sdim Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 443251662Sdim 444249423Sdim if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 445249423Sdim return 0; 446249423Sdim 447249423Sdim bool isMpy = false; 448249423Sdim if (I0->getOpcode() == Instruction::FMul) 449249423Sdim isMpy = true; 450249423Sdim else if (I0->getOpcode() != Instruction::FDiv) 451249423Sdim return 0; 452249423Sdim 453249423Sdim Value *Opnd0_0 = I0->getOperand(0); 454249423Sdim Value *Opnd0_1 = I0->getOperand(1); 455249423Sdim Value *Opnd1_0 = I1->getOperand(0); 456249423Sdim Value *Opnd1_1 = I1->getOperand(1); 457249423Sdim 458251662Sdim // Input Instr I Factor AddSub0 AddSub1 459249423Sdim // ---------------------------------------------- 460249423Sdim // (x*y) +/- (x*z) x y z 461249423Sdim // (y/x) +/- (z/x) x y z 462249423Sdim // 463249423Sdim Value *Factor = 0; 464249423Sdim Value *AddSub0 = 0, *AddSub1 = 0; 465251662Sdim 466249423Sdim if (isMpy) { 467249423Sdim if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 468249423Sdim Factor = Opnd0_0; 469249423Sdim else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 470249423Sdim Factor = Opnd0_1; 471249423Sdim 472249423Sdim if (Factor) { 473249423Sdim AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 474249423Sdim AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 475249423Sdim } 476249423Sdim } else if (Opnd0_1 == Opnd1_1) { 477249423Sdim Factor = Opnd0_1; 478249423Sdim AddSub0 = Opnd0_0; 479249423Sdim AddSub1 = Opnd1_0; 480249423Sdim } 481249423Sdim 482249423Sdim if (!Factor) 483249423Sdim return 0; 484249423Sdim 485249423Sdim // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 486249423Sdim Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 487249423Sdim createFAdd(AddSub0, AddSub1) : 488249423Sdim createFSub(AddSub0, AddSub1); 489249423Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 490249423Sdim const APFloat &F = CFP->getValueAPF(); 491249423Sdim if (!F.isNormal() || F.isDenormal()) 492249423Sdim return 0; 493249423Sdim } 494249423Sdim 495249423Sdim if (isMpy) 496249423Sdim return createFMul(Factor, NewAddSub); 497251662Sdim 498249423Sdim return createFDiv(NewAddSub, Factor); 499249423Sdim} 500249423Sdim 501249423SdimValue *FAddCombine::simplify(Instruction *I) { 502249423Sdim assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 503249423Sdim 504249423Sdim // Currently we are not able to handle vector type. 505249423Sdim if (I->getType()->isVectorTy()) 506249423Sdim return 0; 507249423Sdim 508249423Sdim assert((I->getOpcode() == Instruction::FAdd || 509249423Sdim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 510249423Sdim 511251662Sdim // Save the instruction before calling other member-functions. 512249423Sdim Instr = I; 513249423Sdim 514249423Sdim FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 515249423Sdim 516249423Sdim unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 517249423Sdim 518249423Sdim // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 519249423Sdim unsigned Opnd0_ExpNum = 0; 520249423Sdim unsigned Opnd1_ExpNum = 0; 521249423Sdim 522251662Sdim if (!Opnd0.isConstant()) 523249423Sdim Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 524249423Sdim 525249423Sdim // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 526249423Sdim if (OpndNum == 2 && !Opnd1.isConstant()) 527249423Sdim Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 528249423Sdim 529249423Sdim // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 530249423Sdim if (Opnd0_ExpNum && Opnd1_ExpNum) { 531249423Sdim AddendVect AllOpnds; 532249423Sdim AllOpnds.push_back(&Opnd0_0); 533249423Sdim AllOpnds.push_back(&Opnd1_0); 534249423Sdim if (Opnd0_ExpNum == 2) 535249423Sdim AllOpnds.push_back(&Opnd0_1); 536249423Sdim if (Opnd1_ExpNum == 2) 537249423Sdim AllOpnds.push_back(&Opnd1_1); 538249423Sdim 539249423Sdim // Compute instruction quota. We should save at least one instruction. 540249423Sdim unsigned InstQuota = 0; 541249423Sdim 542249423Sdim Value *V0 = I->getOperand(0); 543249423Sdim Value *V1 = I->getOperand(1); 544251662Sdim InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 545249423Sdim (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 546249423Sdim 547249423Sdim if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 548249423Sdim return R; 549249423Sdim } 550249423Sdim 551249423Sdim if (OpndNum != 2) { 552249423Sdim // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 553249423Sdim // splitted into two addends, say "V = X - Y", the instruction would have 554249423Sdim // been optimized into "I = Y - X" in the previous steps. 555249423Sdim // 556249423Sdim const FAddendCoef &CE = Opnd0.getCoef(); 557249423Sdim return CE.isOne() ? Opnd0.getSymVal() : 0; 558249423Sdim } 559249423Sdim 560249423Sdim // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 561249423Sdim if (Opnd1_ExpNum) { 562249423Sdim AddendVect AllOpnds; 563249423Sdim AllOpnds.push_back(&Opnd0); 564249423Sdim AllOpnds.push_back(&Opnd1_0); 565249423Sdim if (Opnd1_ExpNum == 2) 566249423Sdim AllOpnds.push_back(&Opnd1_1); 567249423Sdim 568249423Sdim if (Value *R = simplifyFAdd(AllOpnds, 1)) 569249423Sdim return R; 570249423Sdim } 571249423Sdim 572249423Sdim // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 573249423Sdim if (Opnd0_ExpNum) { 574249423Sdim AddendVect AllOpnds; 575249423Sdim AllOpnds.push_back(&Opnd1); 576249423Sdim AllOpnds.push_back(&Opnd0_0); 577249423Sdim if (Opnd0_ExpNum == 2) 578249423Sdim AllOpnds.push_back(&Opnd0_1); 579249423Sdim 580249423Sdim if (Value *R = simplifyFAdd(AllOpnds, 1)) 581249423Sdim return R; 582249423Sdim } 583249423Sdim 584251662Sdim // step 6: Try factorization as the last resort, 585249423Sdim return performFactorization(I); 586249423Sdim} 587249423Sdim 588249423SdimValue *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 589249423Sdim 590249423Sdim unsigned AddendNum = Addends.size(); 591249423Sdim assert(AddendNum <= 4 && "Too many addends"); 592249423Sdim 593251662Sdim // For saving intermediate results; 594249423Sdim unsigned NextTmpIdx = 0; 595249423Sdim FAddend TmpResult[3]; 596249423Sdim 597249423Sdim // Points to the constant addend of the resulting simplified expression. 598249423Sdim // If the resulting expr has constant-addend, this constant-addend is 599249423Sdim // desirable to reside at the top of the resulting expression tree. Placing 600249423Sdim // constant close to supper-expr(s) will potentially reveal some optimization 601249423Sdim // opportunities in super-expr(s). 602249423Sdim // 603249423Sdim const FAddend *ConstAdd = 0; 604249423Sdim 605249423Sdim // Simplified addends are placed <SimpVect>. 606249423Sdim AddendVect SimpVect; 607249423Sdim 608249423Sdim // The outer loop works on one symbolic-value at a time. Suppose the input 609251662Sdim // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 610249423Sdim // The symbolic-values will be processed in this order: x, y, z. 611249423Sdim // 612249423Sdim for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 613249423Sdim 614249423Sdim const FAddend *ThisAddend = Addends[SymIdx]; 615249423Sdim if (!ThisAddend) { 616249423Sdim // This addend was processed before. 617249423Sdim continue; 618249423Sdim } 619249423Sdim 620249423Sdim Value *Val = ThisAddend->getSymVal(); 621249423Sdim unsigned StartIdx = SimpVect.size(); 622249423Sdim SimpVect.push_back(ThisAddend); 623249423Sdim 624249423Sdim // The inner loop collects addends sharing same symbolic-value, and these 625249423Sdim // addends will be later on folded into a single addend. Following above 626249423Sdim // example, if the symbolic value "y" is being processed, the inner loop 627249423Sdim // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 628249423Sdim // be later on folded into "<b1+b2, y>". 629249423Sdim // 630249423Sdim for (unsigned SameSymIdx = SymIdx + 1; 631249423Sdim SameSymIdx < AddendNum; SameSymIdx++) { 632249423Sdim const FAddend *T = Addends[SameSymIdx]; 633249423Sdim if (T && T->getSymVal() == Val) { 634249423Sdim // Set null such that next iteration of the outer loop will not process 635249423Sdim // this addend again. 636251662Sdim Addends[SameSymIdx] = 0; 637249423Sdim SimpVect.push_back(T); 638249423Sdim } 639249423Sdim } 640249423Sdim 641249423Sdim // If multiple addends share same symbolic value, fold them together. 642249423Sdim if (StartIdx + 1 != SimpVect.size()) { 643249423Sdim FAddend &R = TmpResult[NextTmpIdx ++]; 644249423Sdim R = *SimpVect[StartIdx]; 645249423Sdim for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) 646249423Sdim R += *SimpVect[Idx]; 647249423Sdim 648249423Sdim // Pop all addends being folded and push the resulting folded addend. 649251662Sdim SimpVect.resize(StartIdx); 650249423Sdim if (Val != 0) { 651249423Sdim if (!R.isZero()) { 652249423Sdim SimpVect.push_back(&R); 653249423Sdim } 654249423Sdim } else { 655249423Sdim // Don't push constant addend at this time. It will be the last element 656249423Sdim // of <SimpVect>. 657249423Sdim ConstAdd = &R; 658249423Sdim } 659249423Sdim } 660249423Sdim } 661249423Sdim 662251662Sdim assert((NextTmpIdx <= sizeof(TmpResult)/sizeof(TmpResult[0]) + 1) && 663249423Sdim "out-of-bound access"); 664249423Sdim 665249423Sdim if (ConstAdd) 666249423Sdim SimpVect.push_back(ConstAdd); 667249423Sdim 668249423Sdim Value *Result; 669249423Sdim if (!SimpVect.empty()) 670249423Sdim Result = createNaryFAdd(SimpVect, InstrQuota); 671249423Sdim else { 672249423Sdim // The addition is folded to 0.0. 673249423Sdim Result = ConstantFP::get(Instr->getType(), 0.0); 674249423Sdim } 675249423Sdim 676249423Sdim return Result; 677249423Sdim} 678249423Sdim 679249423SdimValue *FAddCombine::createNaryFAdd 680249423Sdim (const AddendVect &Opnds, unsigned InstrQuota) { 681249423Sdim assert(!Opnds.empty() && "Expect at least one addend"); 682249423Sdim 683249423Sdim // Step 1: Check if the # of instructions needed exceeds the quota. 684251662Sdim // 685249423Sdim unsigned InstrNeeded = calcInstrNumber(Opnds); 686249423Sdim if (InstrNeeded > InstrQuota) 687249423Sdim return 0; 688249423Sdim 689249423Sdim initCreateInstNum(); 690249423Sdim 691249423Sdim // step 2: Emit the N-ary addition. 692249423Sdim // Note that at most three instructions are involved in Fadd-InstCombine: the 693249423Sdim // addition in question, and at most two neighboring instructions. 694249423Sdim // The resulting optimized addition should have at least one less instruction 695249423Sdim // than the original addition expression tree. This implies that the resulting 696249423Sdim // N-ary addition has at most two instructions, and we don't need to worry 697249423Sdim // about tree-height when constructing the N-ary addition. 698249423Sdim 699249423Sdim Value *LastVal = 0; 700249423Sdim bool LastValNeedNeg = false; 701249423Sdim 702249423Sdim // Iterate the addends, creating fadd/fsub using adjacent two addends. 703249423Sdim for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 704249423Sdim I != E; I++) { 705251662Sdim bool NeedNeg; 706249423Sdim Value *V = createAddendVal(**I, NeedNeg); 707249423Sdim if (!LastVal) { 708249423Sdim LastVal = V; 709249423Sdim LastValNeedNeg = NeedNeg; 710249423Sdim continue; 711249423Sdim } 712249423Sdim 713249423Sdim if (LastValNeedNeg == NeedNeg) { 714249423Sdim LastVal = createFAdd(LastVal, V); 715249423Sdim continue; 716249423Sdim } 717249423Sdim 718249423Sdim if (LastValNeedNeg) 719249423Sdim LastVal = createFSub(V, LastVal); 720249423Sdim else 721249423Sdim LastVal = createFSub(LastVal, V); 722249423Sdim 723249423Sdim LastValNeedNeg = false; 724249423Sdim } 725249423Sdim 726249423Sdim if (LastValNeedNeg) { 727249423Sdim LastVal = createFNeg(LastVal); 728249423Sdim } 729249423Sdim 730249423Sdim #ifndef NDEBUG 731251662Sdim assert(CreateInstrNum == InstrNeeded && 732249423Sdim "Inconsistent in instruction numbers"); 733249423Sdim #endif 734249423Sdim 735249423Sdim return LastVal; 736249423Sdim} 737249423Sdim 738249423SdimValue *FAddCombine::createFSub 739249423Sdim (Value *Opnd0, Value *Opnd1) { 740249423Sdim Value *V = Builder->CreateFSub(Opnd0, Opnd1); 741249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 742249423Sdim createInstPostProc(I); 743249423Sdim return V; 744249423Sdim} 745249423Sdim 746249423SdimValue *FAddCombine::createFNeg(Value *V) { 747249423Sdim Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0)); 748249423Sdim return createFSub(Zero, V); 749249423Sdim} 750249423Sdim 751249423SdimValue *FAddCombine::createFAdd 752249423Sdim (Value *Opnd0, Value *Opnd1) { 753249423Sdim Value *V = Builder->CreateFAdd(Opnd0, Opnd1); 754249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 755249423Sdim createInstPostProc(I); 756249423Sdim return V; 757249423Sdim} 758249423Sdim 759249423SdimValue *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { 760249423Sdim Value *V = Builder->CreateFMul(Opnd0, Opnd1); 761249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 762249423Sdim createInstPostProc(I); 763249423Sdim return V; 764249423Sdim} 765249423Sdim 766249423SdimValue *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { 767249423Sdim Value *V = Builder->CreateFDiv(Opnd0, Opnd1); 768249423Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 769249423Sdim createInstPostProc(I); 770249423Sdim return V; 771249423Sdim} 772249423Sdim 773249423Sdimvoid FAddCombine::createInstPostProc(Instruction *NewInstr) { 774249423Sdim NewInstr->setDebugLoc(Instr->getDebugLoc()); 775249423Sdim 776249423Sdim // Keep track of the number of instruction created. 777249423Sdim incCreateInstNum(); 778249423Sdim 779249423Sdim // Propagate fast-math flags 780249423Sdim NewInstr->setFastMathFlags(Instr->getFastMathFlags()); 781249423Sdim} 782249423Sdim 783249423Sdim// Return the number of instruction needed to emit the N-ary addition. 784249423Sdim// NOTE: Keep this function in sync with createAddendVal(). 785249423Sdimunsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { 786249423Sdim unsigned OpndNum = Opnds.size(); 787249423Sdim unsigned InstrNeeded = OpndNum - 1; 788249423Sdim 789251662Sdim // The number of addends in the form of "(-1)*x". 790251662Sdim unsigned NegOpndNum = 0; 791249423Sdim 792249423Sdim // Adjust the number of instructions needed to emit the N-ary add. 793249423Sdim for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 794249423Sdim I != E; I++) { 795249423Sdim const FAddend *Opnd = *I; 796249423Sdim if (Opnd->isConstant()) 797249423Sdim continue; 798249423Sdim 799249423Sdim const FAddendCoef &CE = Opnd->getCoef(); 800249423Sdim if (CE.isMinusOne() || CE.isMinusTwo()) 801249423Sdim NegOpndNum++; 802249423Sdim 803249423Sdim // Let the addend be "c * x". If "c == +/-1", the value of the addend 804249423Sdim // is immediately available; otherwise, it needs exactly one instruction 805249423Sdim // to evaluate the value. 806249423Sdim if (!CE.isMinusOne() && !CE.isOne()) 807249423Sdim InstrNeeded++; 808249423Sdim } 809249423Sdim if (NegOpndNum == OpndNum) 810249423Sdim InstrNeeded++; 811249423Sdim return InstrNeeded; 812249423Sdim} 813249423Sdim 814249423Sdim// Input Addend Value NeedNeg(output) 815249423Sdim// ================================================================ 816249423Sdim// Constant C C false 817249423Sdim// <+/-1, V> V coefficient is -1 818249423Sdim// <2/-2, V> "fadd V, V" coefficient is -2 819249423Sdim// <C, V> "fmul V, C" false 820249423Sdim// 821249423Sdim// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. 822249423SdimValue *FAddCombine::createAddendVal 823249423Sdim (const FAddend &Opnd, bool &NeedNeg) { 824249423Sdim const FAddendCoef &Coeff = Opnd.getCoef(); 825249423Sdim 826249423Sdim if (Opnd.isConstant()) { 827249423Sdim NeedNeg = false; 828249423Sdim return Coeff.getValue(Instr->getType()); 829249423Sdim } 830249423Sdim 831249423Sdim Value *OpndVal = Opnd.getSymVal(); 832249423Sdim 833249423Sdim if (Coeff.isMinusOne() || Coeff.isOne()) { 834249423Sdim NeedNeg = Coeff.isMinusOne(); 835249423Sdim return OpndVal; 836249423Sdim } 837249423Sdim 838249423Sdim if (Coeff.isTwo() || Coeff.isMinusTwo()) { 839249423Sdim NeedNeg = Coeff.isMinusTwo(); 840249423Sdim return createFAdd(OpndVal, OpndVal); 841249423Sdim } 842249423Sdim 843249423Sdim NeedNeg = false; 844249423Sdim return createFMul(OpndVal, Coeff.getValue(Instr->getType())); 845249423Sdim} 846249423Sdim 847202375Srdivacky/// AddOne - Add one to a ConstantInt. 848202375Srdivackystatic Constant *AddOne(Constant *C) { 849202375Srdivacky return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 850202375Srdivacky} 851249423Sdim 852202375Srdivacky/// SubOne - Subtract one from a ConstantInt. 853202375Srdivackystatic Constant *SubOne(ConstantInt *C) { 854202375Srdivacky return ConstantInt::get(C->getContext(), C->getValue()-1); 855202375Srdivacky} 856202375Srdivacky 857202375Srdivacky 858202375Srdivacky// dyn_castFoldableMul - If this value is a multiply that can be folded into 859202375Srdivacky// other computations (because it has a constant operand), return the 860202375Srdivacky// non-constant operand of the multiply, and set CST to point to the multiplier. 861202375Srdivacky// Otherwise, return null. 862202375Srdivacky// 863202375Srdivackystatic inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 864203954Srdivacky if (!V->hasOneUse() || !V->getType()->isIntegerTy()) 865202375Srdivacky return 0; 866249423Sdim 867202375Srdivacky Instruction *I = dyn_cast<Instruction>(V); 868202375Srdivacky if (I == 0) return 0; 869249423Sdim 870202375Srdivacky if (I->getOpcode() == Instruction::Mul) 871202375Srdivacky if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 872202375Srdivacky return I->getOperand(0); 873202375Srdivacky if (I->getOpcode() == Instruction::Shl) 874202375Srdivacky if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 875202375Srdivacky // The multiplier is really 1 << CST. 876202375Srdivacky uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 877202375Srdivacky uint32_t CSTVal = CST->getLimitedValue(BitWidth); 878202375Srdivacky CST = ConstantInt::get(V->getType()->getContext(), 879202375Srdivacky APInt(BitWidth, 1).shl(CSTVal)); 880202375Srdivacky return I->getOperand(0); 881202375Srdivacky } 882202375Srdivacky return 0; 883202375Srdivacky} 884202375Srdivacky 885202375Srdivacky 886202375Srdivacky/// WillNotOverflowSignedAdd - Return true if we can prove that: 887202375Srdivacky/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 888202375Srdivacky/// This basically requires proving that the add in the original type would not 889202375Srdivacky/// overflow to change the sign bit or have a carry out. 890202375Srdivackybool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 891202375Srdivacky // There are different heuristics we can use for this. Here are some simple 892202375Srdivacky // ones. 893249423Sdim 894249423Sdim // Add has the property that adding any two 2's complement numbers can only 895202375Srdivacky // have one carry bit which can change a sign. As such, if LHS and RHS each 896202375Srdivacky // have at least two sign bits, we know that the addition of the two values 897202375Srdivacky // will sign extend fine. 898202375Srdivacky if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 899202375Srdivacky return true; 900249423Sdim 901249423Sdim 902202375Srdivacky // If one of the operands only has one non-zero bit, and if the other operand 903202375Srdivacky // has a known-zero bit in a more significant place than it (not including the 904202375Srdivacky // sign bit) the ripple may go up to and fill the zero, but won't change the 905202375Srdivacky // sign. For example, (X & ~4) + 1. 906249423Sdim 907202375Srdivacky // TODO: Implement. 908249423Sdim 909202375Srdivacky return false; 910202375Srdivacky} 911202375Srdivacky 912202375SrdivackyInstruction *InstCombiner::visitAdd(BinaryOperator &I) { 913218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 914202375Srdivacky Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 915202375Srdivacky 916202375Srdivacky if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 917202375Srdivacky I.hasNoUnsignedWrap(), TD)) 918202375Srdivacky return ReplaceInstUsesWith(I, V); 919202375Srdivacky 920218893Sdim // (A*B)+(A*C) -> A*(B+C) etc 921218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 922218893Sdim return ReplaceInstUsesWith(I, V); 923202375Srdivacky 924218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 925218893Sdim // X + (signbit) --> X ^ signbit 926218893Sdim const APInt &Val = CI->getValue(); 927218893Sdim if (Val.isSignBit()) 928218893Sdim return BinaryOperator::CreateXor(LHS, RHS); 929249423Sdim 930218893Sdim // See if SimplifyDemandedBits can simplify this. This handles stuff like 931218893Sdim // (X & 254)+1 -> (X&254)|1 932218893Sdim if (SimplifyDemandedInstructionBits(I)) 933218893Sdim return &I; 934202375Srdivacky 935218893Sdim // zext(bool) + C -> bool ? C + 1 : C 936218893Sdim if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 937218893Sdim if (ZI->getSrcTy()->isIntegerTy(1)) 938218893Sdim return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 939249423Sdim 940218893Sdim Value *XorLHS = 0; ConstantInt *XorRHS = 0; 941218893Sdim if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 942202375Srdivacky uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 943218893Sdim const APInt &RHSVal = CI->getValue(); 944203954Srdivacky unsigned ExtendAmt = 0; 945203954Srdivacky // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 946203954Srdivacky // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 947203954Srdivacky if (XorRHS->getValue() == -RHSVal) { 948203954Srdivacky if (RHSVal.isPowerOf2()) 949203954Srdivacky ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 950203954Srdivacky else if (XorRHS->getValue().isPowerOf2()) 951203954Srdivacky ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 952202375Srdivacky } 953249423Sdim 954203954Srdivacky if (ExtendAmt) { 955203954Srdivacky APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 956203954Srdivacky if (!MaskedValueIsZero(XorLHS, Mask)) 957203954Srdivacky ExtendAmt = 0; 958202375Srdivacky } 959249423Sdim 960203954Srdivacky if (ExtendAmt) { 961203954Srdivacky Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 962203954Srdivacky Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 963203954Srdivacky return BinaryOperator::CreateAShr(NewShl, ShAmt); 964203954Srdivacky } 965234353Sdim 966234353Sdim // If this is a xor that was canonicalized from a sub, turn it back into 967234353Sdim // a sub and fuse this add with it. 968234353Sdim if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { 969234353Sdim IntegerType *IT = cast<IntegerType>(I.getType()); 970234353Sdim APInt LHSKnownOne(IT->getBitWidth(), 0); 971234353Sdim APInt LHSKnownZero(IT->getBitWidth(), 0); 972234353Sdim ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne); 973234353Sdim if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue()) 974234353Sdim return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), 975234353Sdim XorLHS); 976234353Sdim } 977251662Sdim // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C, 978251662Sdim // transform them into (X + (signbit ^ C)) 979251662Sdim if (XorRHS->getValue().isSignBit()) 980251662Sdim return BinaryOperator::CreateAdd(XorLHS, 981251662Sdim ConstantExpr::getXor(XorRHS, CI)); 982202375Srdivacky } 983202375Srdivacky } 984202375Srdivacky 985218893Sdim if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 986218893Sdim if (Instruction *NV = FoldOpIntoPhi(I)) 987218893Sdim return NV; 988218893Sdim 989203954Srdivacky if (I.getType()->isIntegerTy(1)) 990202375Srdivacky return BinaryOperator::CreateXor(LHS, RHS); 991202375Srdivacky 992218893Sdim // X + X --> X << 1 993218893Sdim if (LHS == RHS) { 994218893Sdim BinaryOperator *New = 995218893Sdim BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 996218893Sdim New->setHasNoSignedWrap(I.hasNoSignedWrap()); 997218893Sdim New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 998218893Sdim return New; 999202375Srdivacky } 1000202375Srdivacky 1001202375Srdivacky // -A + B --> B - A 1002202375Srdivacky // -A + -B --> -(A + B) 1003202375Srdivacky if (Value *LHSV = dyn_castNegVal(LHS)) { 1004239462Sdim if (!isa<Constant>(RHS)) 1005239462Sdim if (Value *RHSV = dyn_castNegVal(RHS)) { 1006239462Sdim Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 1007239462Sdim return BinaryOperator::CreateNeg(NewAdd); 1008239462Sdim } 1009249423Sdim 1010202375Srdivacky return BinaryOperator::CreateSub(RHS, LHSV); 1011202375Srdivacky } 1012202375Srdivacky 1013202375Srdivacky // A + -B --> A - B 1014202375Srdivacky if (!isa<Constant>(RHS)) 1015202375Srdivacky if (Value *V = dyn_castNegVal(RHS)) 1016202375Srdivacky return BinaryOperator::CreateSub(LHS, V); 1017202375Srdivacky 1018202375Srdivacky 1019202375Srdivacky ConstantInt *C2; 1020202375Srdivacky if (Value *X = dyn_castFoldableMul(LHS, C2)) { 1021202375Srdivacky if (X == RHS) // X*C + X --> X * (C+1) 1022202375Srdivacky return BinaryOperator::CreateMul(RHS, AddOne(C2)); 1023202375Srdivacky 1024202375Srdivacky // X*C1 + X*C2 --> X * (C1+C2) 1025202375Srdivacky ConstantInt *C1; 1026202375Srdivacky if (X == dyn_castFoldableMul(RHS, C1)) 1027202375Srdivacky return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 1028202375Srdivacky } 1029202375Srdivacky 1030202375Srdivacky // X + X*C --> X * (C+1) 1031202375Srdivacky if (dyn_castFoldableMul(RHS, C2) == LHS) 1032202375Srdivacky return BinaryOperator::CreateMul(LHS, AddOne(C2)); 1033202375Srdivacky 1034202375Srdivacky // A+B --> A|B iff A and B have no bits set in common. 1035226633Sdim if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 1036202375Srdivacky APInt LHSKnownOne(IT->getBitWidth(), 0); 1037202375Srdivacky APInt LHSKnownZero(IT->getBitWidth(), 0); 1038234353Sdim ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne); 1039202375Srdivacky if (LHSKnownZero != 0) { 1040202375Srdivacky APInt RHSKnownOne(IT->getBitWidth(), 0); 1041202375Srdivacky APInt RHSKnownZero(IT->getBitWidth(), 0); 1042234353Sdim ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne); 1043249423Sdim 1044202375Srdivacky // No bits in common -> bitwise or. 1045202375Srdivacky if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 1046202375Srdivacky return BinaryOperator::CreateOr(LHS, RHS); 1047202375Srdivacky } 1048202375Srdivacky } 1049202375Srdivacky 1050202375Srdivacky // W*X + Y*Z --> W * (X+Z) iff W == Y 1051218893Sdim { 1052202375Srdivacky Value *W, *X, *Y, *Z; 1053202375Srdivacky if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 1054202375Srdivacky match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 1055202375Srdivacky if (W != Y) { 1056202375Srdivacky if (W == Z) { 1057202375Srdivacky std::swap(Y, Z); 1058202375Srdivacky } else if (Y == X) { 1059202375Srdivacky std::swap(W, X); 1060202375Srdivacky } else if (X == Z) { 1061202375Srdivacky std::swap(Y, Z); 1062202375Srdivacky std::swap(W, X); 1063202375Srdivacky } 1064202375Srdivacky } 1065202375Srdivacky 1066202375Srdivacky if (W == Y) { 1067202375Srdivacky Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 1068202375Srdivacky return BinaryOperator::CreateMul(W, NewAdd); 1069202375Srdivacky } 1070202375Srdivacky } 1071202375Srdivacky } 1072202375Srdivacky 1073202375Srdivacky if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 1074202375Srdivacky Value *X = 0; 1075202375Srdivacky if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 1076202375Srdivacky return BinaryOperator::CreateSub(SubOne(CRHS), X); 1077202375Srdivacky 1078202375Srdivacky // (X & FF00) + xx00 -> (X+xx00) & FF00 1079202375Srdivacky if (LHS->hasOneUse() && 1080218893Sdim match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 1081218893Sdim CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 1082218893Sdim // See if all bits from the first bit set in the Add RHS up are included 1083218893Sdim // in the mask. First, get the rightmost bit. 1084218893Sdim const APInt &AddRHSV = CRHS->getValue(); 1085249423Sdim 1086218893Sdim // Form a mask of all bits from the lowest bit added through the top. 1087218893Sdim APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 1088202375Srdivacky 1089218893Sdim // See if the and mask includes all of these bits. 1090218893Sdim APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 1091202375Srdivacky 1092218893Sdim if (AddRHSHighBits == AddRHSHighBitsAnd) { 1093218893Sdim // Okay, the xform is safe. Insert the new add pronto. 1094218893Sdim Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 1095218893Sdim return BinaryOperator::CreateAnd(NewAdd, C2); 1096202375Srdivacky } 1097202375Srdivacky } 1098202375Srdivacky 1099202375Srdivacky // Try to fold constant add into select arguments. 1100202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1101202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1102202375Srdivacky return R; 1103202375Srdivacky } 1104202375Srdivacky 1105202375Srdivacky // add (select X 0 (sub n A)) A --> select X A n 1106202375Srdivacky { 1107202375Srdivacky SelectInst *SI = dyn_cast<SelectInst>(LHS); 1108202375Srdivacky Value *A = RHS; 1109202375Srdivacky if (!SI) { 1110202375Srdivacky SI = dyn_cast<SelectInst>(RHS); 1111202375Srdivacky A = LHS; 1112202375Srdivacky } 1113202375Srdivacky if (SI && SI->hasOneUse()) { 1114202375Srdivacky Value *TV = SI->getTrueValue(); 1115202375Srdivacky Value *FV = SI->getFalseValue(); 1116202375Srdivacky Value *N; 1117202375Srdivacky 1118202375Srdivacky // Can we fold the add into the argument of the select? 1119202375Srdivacky // We check both true and false select arguments for a matching subtract. 1120218893Sdim if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 1121202375Srdivacky // Fold the add into the true select value. 1122202375Srdivacky return SelectInst::Create(SI->getCondition(), N, A); 1123249423Sdim 1124218893Sdim if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 1125202375Srdivacky // Fold the add into the false select value. 1126202375Srdivacky return SelectInst::Create(SI->getCondition(), A, N); 1127202375Srdivacky } 1128202375Srdivacky } 1129202375Srdivacky 1130202375Srdivacky // Check for (add (sext x), y), see if we can merge this into an 1131202375Srdivacky // integer add followed by a sext. 1132202375Srdivacky if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 1133202375Srdivacky // (add (sext x), cst) --> (sext (add x, cst')) 1134202375Srdivacky if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 1135249423Sdim Constant *CI = 1136202375Srdivacky ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 1137202375Srdivacky if (LHSConv->hasOneUse() && 1138202375Srdivacky ConstantExpr::getSExt(CI, I.getType()) == RHSC && 1139202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1140202375Srdivacky // Insert the new, smaller add. 1141249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1142202375Srdivacky CI, "addconv"); 1143202375Srdivacky return new SExtInst(NewAdd, I.getType()); 1144202375Srdivacky } 1145202375Srdivacky } 1146249423Sdim 1147202375Srdivacky // (add (sext x), (sext y)) --> (sext (add int x, y)) 1148202375Srdivacky if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 1149202375Srdivacky // Only do this if x/y have the same type, if at last one of them has a 1150202375Srdivacky // single use (so we don't increase the number of sexts), and if the 1151202375Srdivacky // integer add will not overflow. 1152202375Srdivacky if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1153202375Srdivacky (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1154202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1155202375Srdivacky RHSConv->getOperand(0))) { 1156202375Srdivacky // Insert the new integer add. 1157249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1158202375Srdivacky RHSConv->getOperand(0), "addconv"); 1159202375Srdivacky return new SExtInst(NewAdd, I.getType()); 1160202375Srdivacky } 1161202375Srdivacky } 1162202375Srdivacky } 1163202375Srdivacky 1164239462Sdim // Check for (x & y) + (x ^ y) 1165239462Sdim { 1166239462Sdim Value *A = 0, *B = 0; 1167239462Sdim if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && 1168239462Sdim (match(LHS, m_And(m_Specific(A), m_Specific(B))) || 1169239462Sdim match(LHS, m_And(m_Specific(B), m_Specific(A))))) 1170239462Sdim return BinaryOperator::CreateOr(A, B); 1171239462Sdim 1172239462Sdim if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && 1173239462Sdim (match(RHS, m_And(m_Specific(A), m_Specific(B))) || 1174239462Sdim match(RHS, m_And(m_Specific(B), m_Specific(A))))) 1175239462Sdim return BinaryOperator::CreateOr(A, B); 1176239462Sdim } 1177239462Sdim 1178202375Srdivacky return Changed ? &I : 0; 1179202375Srdivacky} 1180202375Srdivacky 1181202375SrdivackyInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 1182218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 1183202375Srdivacky Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 1184202375Srdivacky 1185249423Sdim if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD)) 1186249423Sdim return ReplaceInstUsesWith(I, V); 1187202375Srdivacky 1188249423Sdim if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 1189249423Sdim if (Instruction *NV = FoldOpIntoPhi(I)) 1190249423Sdim return NV; 1191202375Srdivacky 1192202375Srdivacky // -A + B --> B - A 1193202375Srdivacky // -A + -B --> -(A + B) 1194202375Srdivacky if (Value *LHSV = dyn_castFNegVal(LHS)) 1195202375Srdivacky return BinaryOperator::CreateFSub(RHS, LHSV); 1196202375Srdivacky 1197202375Srdivacky // A + -B --> A - B 1198202375Srdivacky if (!isa<Constant>(RHS)) 1199202375Srdivacky if (Value *V = dyn_castFNegVal(RHS)) 1200202375Srdivacky return BinaryOperator::CreateFSub(LHS, V); 1201202375Srdivacky 1202204642Srdivacky // Check for (fadd double (sitofp x), y), see if we can merge this into an 1203202375Srdivacky // integer add followed by a promotion. 1204202375Srdivacky if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 1205204642Srdivacky // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 1206202375Srdivacky // ... if the constant fits in the integer value. This is useful for things 1207202375Srdivacky // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 1208202375Srdivacky // requires a constant pool load, and generally allows the add to be better 1209202375Srdivacky // instcombined. 1210202375Srdivacky if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 1211249423Sdim Constant *CI = 1212202375Srdivacky ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 1213202375Srdivacky if (LHSConv->hasOneUse() && 1214202375Srdivacky ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 1215202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1216202375Srdivacky // Insert the new integer add. 1217202375Srdivacky Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1218202375Srdivacky CI, "addconv"); 1219202375Srdivacky return new SIToFPInst(NewAdd, I.getType()); 1220202375Srdivacky } 1221202375Srdivacky } 1222249423Sdim 1223204642Srdivacky // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 1224202375Srdivacky if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 1225202375Srdivacky // Only do this if x/y have the same type, if at last one of them has a 1226202375Srdivacky // single use (so we don't increase the number of int->fp conversions), 1227202375Srdivacky // and if the integer add will not overflow. 1228202375Srdivacky if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1229202375Srdivacky (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1230202375Srdivacky WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1231202375Srdivacky RHSConv->getOperand(0))) { 1232202375Srdivacky // Insert the new integer add. 1233249423Sdim Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1234202375Srdivacky RHSConv->getOperand(0),"addconv"); 1235202375Srdivacky return new SIToFPInst(NewAdd, I.getType()); 1236202375Srdivacky } 1237202375Srdivacky } 1238202375Srdivacky } 1239249423Sdim 1240251662Sdim // select C, 0, B + select C, A, 0 -> select C, A, B 1241251662Sdim { 1242251662Sdim Value *A1, *B1, *C1, *A2, *B2, *C2; 1243251662Sdim if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) && 1244251662Sdim match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) { 1245251662Sdim if (C1 == C2) { 1246251662Sdim Constant *Z1=0, *Z2=0; 1247251662Sdim Value *A, *B, *C=C1; 1248251662Sdim if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) { 1249251662Sdim Z1 = dyn_cast<Constant>(A1); A = A2; 1250251662Sdim Z2 = dyn_cast<Constant>(B2); B = B1; 1251251662Sdim } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) { 1252251662Sdim Z1 = dyn_cast<Constant>(B1); B = B2; 1253251662Sdim Z2 = dyn_cast<Constant>(A2); A = A1; 1254251662Sdim } 1255251662Sdim 1256251662Sdim if (Z1 && Z2 && 1257251662Sdim (I.hasNoSignedZeros() || 1258251662Sdim (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) { 1259251662Sdim return SelectInst::Create(C, A, B); 1260251662Sdim } 1261251662Sdim } 1262251662Sdim } 1263251662Sdim } 1264251662Sdim 1265249423Sdim if (I.hasUnsafeAlgebra()) { 1266249423Sdim if (Value *V = FAddCombine(Builder).simplify(&I)) 1267249423Sdim return ReplaceInstUsesWith(I, V); 1268249423Sdim } 1269249423Sdim 1270202375Srdivacky return Changed ? &I : 0; 1271202375Srdivacky} 1272202375Srdivacky 1273202375Srdivacky 1274202375Srdivacky/// Optimize pointer differences into the same array into a size. Consider: 1275202375Srdivacky/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 1276202375Srdivacky/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 1277202375Srdivacky/// 1278202375SrdivackyValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 1279226633Sdim Type *Ty) { 1280202375Srdivacky assert(TD && "Must have target data info for this"); 1281249423Sdim 1282202375Srdivacky // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 1283202375Srdivacky // this. 1284202375Srdivacky bool Swapped = false; 1285234353Sdim GEPOperator *GEP1 = 0, *GEP2 = 0; 1286234353Sdim 1287202375Srdivacky // For now we require one side to be the base pointer "A" or a constant 1288234353Sdim // GEP derived from it. 1289234353Sdim if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1290202375Srdivacky // (gep X, ...) - X 1291202375Srdivacky if (LHSGEP->getOperand(0) == RHS) { 1292234353Sdim GEP1 = LHSGEP; 1293202375Srdivacky Swapped = false; 1294234353Sdim } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1295234353Sdim // (gep X, ...) - (gep X, ...) 1296234353Sdim if (LHSGEP->getOperand(0)->stripPointerCasts() == 1297234353Sdim RHSGEP->getOperand(0)->stripPointerCasts()) { 1298234353Sdim GEP2 = RHSGEP; 1299234353Sdim GEP1 = LHSGEP; 1300202375Srdivacky Swapped = false; 1301202375Srdivacky } 1302202375Srdivacky } 1303202375Srdivacky } 1304249423Sdim 1305234353Sdim if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1306202375Srdivacky // X - (gep X, ...) 1307202375Srdivacky if (RHSGEP->getOperand(0) == LHS) { 1308234353Sdim GEP1 = RHSGEP; 1309202375Srdivacky Swapped = true; 1310234353Sdim } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1311234353Sdim // (gep X, ...) - (gep X, ...) 1312234353Sdim if (RHSGEP->getOperand(0)->stripPointerCasts() == 1313234353Sdim LHSGEP->getOperand(0)->stripPointerCasts()) { 1314234353Sdim GEP2 = LHSGEP; 1315234353Sdim GEP1 = RHSGEP; 1316202375Srdivacky Swapped = true; 1317202375Srdivacky } 1318202375Srdivacky } 1319202375Srdivacky } 1320249423Sdim 1321234353Sdim // Avoid duplicating the arithmetic if GEP2 has non-constant indices and 1322234353Sdim // multiple users. 1323234353Sdim if (GEP1 == 0 || 1324234353Sdim (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse())) 1325202375Srdivacky return 0; 1326249423Sdim 1327202375Srdivacky // Emit the offset of the GEP and an intptr_t. 1328234353Sdim Value *Result = EmitGEPOffset(GEP1); 1329249423Sdim 1330202375Srdivacky // If we had a constant expression GEP on the other side offsetting the 1331202375Srdivacky // pointer, subtract it from the offset we have. 1332234353Sdim if (GEP2) { 1333234353Sdim Value *Offset = EmitGEPOffset(GEP2); 1334234353Sdim Result = Builder->CreateSub(Result, Offset); 1335202375Srdivacky } 1336202375Srdivacky 1337202375Srdivacky // If we have p - gep(p, ...) then we have to negate the result. 1338202375Srdivacky if (Swapped) 1339202375Srdivacky Result = Builder->CreateNeg(Result, "diff.neg"); 1340202375Srdivacky 1341202375Srdivacky return Builder->CreateIntCast(Result, Ty, true); 1342202375Srdivacky} 1343202375Srdivacky 1344202375Srdivacky 1345202375SrdivackyInstruction *InstCombiner::visitSub(BinaryOperator &I) { 1346202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1347202375Srdivacky 1348218893Sdim if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 1349218893Sdim I.hasNoUnsignedWrap(), TD)) 1350218893Sdim return ReplaceInstUsesWith(I, V); 1351202375Srdivacky 1352218893Sdim // (A*B)-(A*C) -> A*(B-C) etc 1353218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 1354218893Sdim return ReplaceInstUsesWith(I, V); 1355218893Sdim 1356202375Srdivacky // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 1357202375Srdivacky if (Value *V = dyn_castNegVal(Op1)) { 1358202375Srdivacky BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 1359202375Srdivacky Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 1360202375Srdivacky Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 1361202375Srdivacky return Res; 1362202375Srdivacky } 1363202375Srdivacky 1364203954Srdivacky if (I.getType()->isIntegerTy(1)) 1365202375Srdivacky return BinaryOperator::CreateXor(Op0, Op1); 1366218893Sdim 1367218893Sdim // Replace (-1 - A) with (~A). 1368218893Sdim if (match(Op0, m_AllOnes())) 1369218893Sdim return BinaryOperator::CreateNot(Op1); 1370249423Sdim 1371202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 1372202375Srdivacky // C - ~X == X + (1+C) 1373202375Srdivacky Value *X = 0; 1374202375Srdivacky if (match(Op1, m_Not(m_Value(X)))) 1375202375Srdivacky return BinaryOperator::CreateAdd(X, AddOne(C)); 1376202375Srdivacky 1377202375Srdivacky // -(X >>u 31) -> (X >>s 31) 1378202375Srdivacky // -(X >>s 31) -> (X >>u 31) 1379202375Srdivacky if (C->isZero()) { 1380218893Sdim Value *X; ConstantInt *CI; 1381218893Sdim if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 1382218893Sdim // Verify we are shifting out everything but the sign bit. 1383218893Sdim CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1384218893Sdim return BinaryOperator::CreateAShr(X, CI); 1385218893Sdim 1386218893Sdim if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 1387218893Sdim // Verify we are shifting out everything but the sign bit. 1388218893Sdim CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1389218893Sdim return BinaryOperator::CreateLShr(X, CI); 1390202375Srdivacky } 1391202375Srdivacky 1392202375Srdivacky // Try to fold constant sub into select arguments. 1393202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1394202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 1395202375Srdivacky return R; 1396202375Srdivacky 1397218893Sdim // C-(X+C2) --> (C-C2)-X 1398218893Sdim ConstantInt *C2; 1399218893Sdim if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2)))) 1400218893Sdim return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 1401234353Sdim 1402234353Sdim if (SimplifyDemandedInstructionBits(I)) 1403234353Sdim return &I; 1404249423Sdim 1405249423Sdim // Fold (sub 0, (zext bool to B)) --> (sext bool to B) 1406249423Sdim if (C->isZero() && match(Op1, m_ZExt(m_Value(X)))) 1407249423Sdim if (X->getType()->isIntegerTy(1)) 1408249423Sdim return CastInst::CreateSExtOrBitCast(X, Op1->getType()); 1409249423Sdim 1410249423Sdim // Fold (sub 0, (sext bool to B)) --> (zext bool to B) 1411249423Sdim if (C->isZero() && match(Op1, m_SExt(m_Value(X)))) 1412249423Sdim if (X->getType()->isIntegerTy(1)) 1413249423Sdim return CastInst::CreateZExtOrBitCast(X, Op1->getType()); 1414202375Srdivacky } 1415202375Srdivacky 1416249423Sdim 1417218893Sdim { Value *Y; 1418218893Sdim // X-(X+Y) == -Y X-(Y+X) == -Y 1419218893Sdim if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 1420218893Sdim match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 1421218893Sdim return BinaryOperator::CreateNeg(Y); 1422249423Sdim 1423218893Sdim // (X-Y)-X == -Y 1424218893Sdim if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 1425218893Sdim return BinaryOperator::CreateNeg(Y); 1426218893Sdim } 1427249423Sdim 1428218893Sdim if (Op1->hasOneUse()) { 1429218893Sdim Value *X = 0, *Y = 0, *Z = 0; 1430218893Sdim Constant *C = 0; 1431218893Sdim ConstantInt *CI = 0; 1432202375Srdivacky 1433218893Sdim // (X - (Y - Z)) --> (X + (Z - Y)). 1434218893Sdim if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 1435218893Sdim return BinaryOperator::CreateAdd(Op0, 1436218893Sdim Builder->CreateSub(Z, Y, Op1->getName())); 1437202375Srdivacky 1438218893Sdim // (X - (X & Y)) --> (X & ~Y) 1439218893Sdim // 1440218893Sdim if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 1441218893Sdim match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 1442218893Sdim return BinaryOperator::CreateAnd(Op0, 1443218893Sdim Builder->CreateNot(Y, Y->getName() + ".not")); 1444249423Sdim 1445218893Sdim // 0 - (X sdiv C) -> (X sdiv -C) 1446218893Sdim if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && 1447218893Sdim match(Op0, m_Zero())) 1448218893Sdim return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 1449202375Srdivacky 1450218893Sdim // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 1451218893Sdim if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 1452218893Sdim if (Value *XNeg = dyn_castNegVal(X)) 1453218893Sdim return BinaryOperator::CreateShl(XNeg, Y); 1454202375Srdivacky 1455218893Sdim // X - X*C --> X * (1-C) 1456218893Sdim if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) { 1457218893Sdim Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); 1458218893Sdim return BinaryOperator::CreateMul(Op0, CP1); 1459202375Srdivacky } 1460202375Srdivacky 1461218893Sdim // X - X<<C --> X * (1-(1<<C)) 1462218893Sdim if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) { 1463218893Sdim Constant *One = ConstantInt::get(I.getType(), 1); 1464218893Sdim C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI)); 1465218893Sdim return BinaryOperator::CreateMul(Op0, C); 1466202375Srdivacky } 1467249423Sdim 1468218893Sdim // X - A*-B -> X + A*B 1469218893Sdim // X - -A*B -> X + A*B 1470218893Sdim Value *A, *B; 1471218893Sdim if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 1472218893Sdim match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 1473218893Sdim return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 1474249423Sdim 1475218893Sdim // X - A*CI -> X + A*-CI 1476218893Sdim // X - CI*A -> X + A*-CI 1477218893Sdim if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) || 1478218893Sdim match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) { 1479218893Sdim Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 1480218893Sdim return BinaryOperator::CreateAdd(Op0, NewMul); 1481218893Sdim } 1482202375Srdivacky } 1483202375Srdivacky 1484202375Srdivacky ConstantInt *C1; 1485202375Srdivacky if (Value *X = dyn_castFoldableMul(Op0, C1)) { 1486202375Srdivacky if (X == Op1) // X*C - X --> X * (C-1) 1487202375Srdivacky return BinaryOperator::CreateMul(Op1, SubOne(C1)); 1488202375Srdivacky 1489202375Srdivacky ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 1490202375Srdivacky if (X == dyn_castFoldableMul(Op1, C2)) 1491202375Srdivacky return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 1492202375Srdivacky } 1493249423Sdim 1494202375Srdivacky // Optimize pointer differences into the same array into a size. Consider: 1495202375Srdivacky // &A[10] - &A[0]: we should compile this to "10". 1496202375Srdivacky if (TD) { 1497202375Srdivacky Value *LHSOp, *RHSOp; 1498202375Srdivacky if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 1499202375Srdivacky match(Op1, m_PtrToInt(m_Value(RHSOp)))) 1500202375Srdivacky if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1501202375Srdivacky return ReplaceInstUsesWith(I, Res); 1502249423Sdim 1503202375Srdivacky // trunc(p)-trunc(q) -> trunc(p-q) 1504202375Srdivacky if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 1505202375Srdivacky match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 1506202375Srdivacky if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1507202375Srdivacky return ReplaceInstUsesWith(I, Res); 1508202375Srdivacky } 1509249423Sdim 1510202375Srdivacky return 0; 1511202375Srdivacky} 1512202375Srdivacky 1513202375SrdivackyInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 1514202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1515202375Srdivacky 1516249423Sdim if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD)) 1517249423Sdim return ReplaceInstUsesWith(I, V); 1518249423Sdim 1519202375Srdivacky // If this is a 'B = x-(-A)', change to B = x+A... 1520202375Srdivacky if (Value *V = dyn_castFNegVal(Op1)) 1521202375Srdivacky return BinaryOperator::CreateFAdd(Op0, V); 1522202375Srdivacky 1523249423Sdim if (I.hasUnsafeAlgebra()) { 1524249423Sdim if (Value *V = FAddCombine(Builder).simplify(&I)) 1525249423Sdim return ReplaceInstUsesWith(I, V); 1526249423Sdim } 1527249423Sdim 1528202375Srdivacky return 0; 1529202375Srdivacky} 1530