InstCombineAddSub.cpp revision 251662
1196000Sjkim//===- InstCombineAddSub.cpp ----------------------------------------------===// 2196000Sjkim// 3196000Sjkim// The LLVM Compiler Infrastructure 4196000Sjkim// 5196000Sjkim// This file is distributed under the University of Illinois Open Source 6196000Sjkim// License. See LICENSE.TXT for details. 7217365Sjkim// 8281075Sdim//===----------------------------------------------------------------------===// 9196000Sjkim// 10196000Sjkim// This file implements the visit functions for add, fadd, sub, and fsub. 11217365Sjkim// 12217365Sjkim//===----------------------------------------------------------------------===// 13217365Sjkim 14217365Sjkim#include "InstCombine.h" 15217365Sjkim#include "llvm/Analysis/InstructionSimplify.h" 16217365Sjkim#include "llvm/IR/DataLayout.h" 17217365Sjkim#include "llvm/Support/GetElementPtrTypeIterator.h" 18217365Sjkim#include "llvm/Support/PatternMatch.h" 19217365Sjkimusing namespace llvm; 20217365Sjkimusing namespace PatternMatch; 21217365Sjkim 22217365Sjkimnamespace { 23217365Sjkim 24217365Sjkim /// Class representing coefficient of floating-point addend. 25196000Sjkim /// This class needs to be highly efficient, which is especially true for 26217365Sjkim /// the constructor. As of I write this comment, the cost of the default 27217365Sjkim /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 28217365Sjkim /// perform write-merging). 29196000Sjkim /// 30217365Sjkim class FAddendCoef { 31217365Sjkim public: 32217365Sjkim // The constructor has to initialize a APFloat, which is uncessary for 33217365Sjkim // most addends which have coefficient either 1 or -1. So, the constructor 34217365Sjkim // is expensive. In order to avoid the cost of the constructor, we should 35217365Sjkim // reuse some instances whenever possible. The pre-created instances 36217365Sjkim // FAddCombine::Add[0-5] embodies this idea. 37217365Sjkim // 38217365Sjkim FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 39217365Sjkim ~FAddendCoef(); 40217365Sjkim 41217365Sjkim void set(short C) { 42217365Sjkim assert(!insaneIntVal(C) && "Insane coefficient"); 43196000Sjkim IsFp = false; IntVal = C; 44197107Sjkim } 45197107Sjkim 46197107Sjkim void set(const APFloat& C); 47198237Sjkim 48202773Sjkim void negate(); 49246849Sjkim 50196000Sjkim bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 51196000Sjkim Value *getValue(Type *) const; 52196000Sjkim 53196000Sjkim // If possible, don't define operator+/operator- etc because these 54196000Sjkim // operators inevitably call FAddendCoef's constructor which is not cheap. 55196000Sjkim void operator=(const FAddendCoef &A); 56196000Sjkim void operator+=(const FAddendCoef &A); 57200553Sjkim void operator-=(const FAddendCoef &A); 58200553Sjkim void operator*=(const FAddendCoef &S); 59200553Sjkim 60200553Sjkim bool isOne() const { return isInt() && IntVal == 1; } 61200553Sjkim bool isTwo() const { return isInt() && IntVal == 2; } 62200553Sjkim bool isMinusOne() const { return isInt() && IntVal == -1; } 63200553Sjkim bool isMinusTwo() const { return isInt() && IntVal == -2; } 64200553Sjkim 65200553Sjkim private: 66200553Sjkim bool insaneIntVal(int V) { return V > 4 || V < -4; } 67200553Sjkim APFloat *getFpValPtr(void) 68200553Sjkim { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 69200553Sjkim const APFloat *getFpValPtr(void) const 70200553Sjkim { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 71200553Sjkim 72200553Sjkim const APFloat &getFpVal(void) const { 73200553Sjkim assert(IsFp && BufHasFpVal && "Incorret state"); 74200553Sjkim return *getFpValPtr(); 75200553Sjkim } 76246849Sjkim 77246849Sjkim APFloat &getFpVal(void) { 78246849Sjkim assert(IsFp && BufHasFpVal && "Incorret state"); 79246849Sjkim return *getFpValPtr(); 80246849Sjkim } 81233617Sjkim 82200553Sjkim bool isInt() const { return !IsFp; } 83202771Sjkim 84202771Sjkim // If the coefficient is represented by an integer, promote it to a 85202771Sjkim // floating point. 86200553Sjkim void convertToFpType(const fltSemantics &Sem); 87200553Sjkim 88200553Sjkim // Construct an APFloat from a signed integer. 89200553Sjkim // TODO: We should get rid of this function when APFloat can be constructed 90200553Sjkim // from an *SIGNED* integer. 91246849Sjkim APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 92246849Sjkim private: 93246849Sjkim 94246849Sjkim bool IsFp; 95246849Sjkim 96200553Sjkim // True iff FpValBuf contains an instance of APFloat. 97200553Sjkim bool BufHasFpVal; 98246849Sjkim 99246849Sjkim // The integer coefficient of an individual addend is either 1 or -1, 100246849Sjkim // and we try to simplify at most 4 addends from neighboring at most 101246849Sjkim // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 102246849Sjkim // is overkill of this end. 103246849Sjkim short IntVal; 104246849Sjkim 105246849Sjkim AlignedCharArrayUnion<APFloat> FpValBuf; 106200553Sjkim }; 107246849Sjkim 108246849Sjkim /// FAddend is used to represent floating-point addend. An addend is 109246849Sjkim /// represented as <C, V>, where the V is a symbolic value, and C is a 110246849Sjkim /// constant coefficient. A constant addend is represented as <C, 0>. 111246849Sjkim /// 112246849Sjkim class FAddend { 113246849Sjkim public: 114246849Sjkim FAddend() { Val = 0; } 115246849Sjkim 116200553Sjkim Value *getSymVal (void) const { return Val; } 117246849Sjkim const FAddendCoef &getCoef(void) const { return Coeff; } 118246849Sjkim 119246849Sjkim bool isConstant() const { return Val == 0; } 120246849Sjkim bool isZero() const { return Coeff.isZero(); } 121246849Sjkim 122246849Sjkim void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 123246849Sjkim void set(const APFloat& Coefficient, Value *V) 124246849Sjkim { Coeff.set(Coefficient); Val = V; } 125246849Sjkim void set(const ConstantFP* Coefficient, Value *V) 126246849Sjkim { Coeff.set(Coefficient->getValueAPF()); Val = V; } 127246849Sjkim 128200553Sjkim void negate() { Coeff.negate(); } 129200553Sjkim 130246849Sjkim /// Drill down the U-D chain one step to find the definition of V, and 131196000Sjkim /// try to break the definition into one or two addends. 132249663Sjkim static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 133196000Sjkim 134196000Sjkim /// Similar to FAddend::drillDownOneStep() except that the value being 135196000Sjkim /// splitted is the addend itself. 136196000Sjkim unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 137196000Sjkim 138196000Sjkim void operator+=(const FAddend &T) { 139196000Sjkim assert((Val == T.Val) && "Symbolic-values disagree"); 140196000Sjkim Coeff += T.Coeff; 141196000Sjkim } 142196000Sjkim 143196000Sjkim private: 144196000Sjkim void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 145196000Sjkim 146196000Sjkim // This addend has the value of "Coeff * Val". 147196000Sjkim Value *Val; 148246849Sjkim FAddendCoef Coeff; 149249663Sjkim }; 150196000Sjkim 151196000Sjkim /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 152196000Sjkim /// with its neighboring at most two instructions. 153196000Sjkim /// 154196000Sjkim class FAddCombine { 155246849Sjkim public: 156198237Sjkim FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {} 157246849Sjkim Value *simplify(Instruction *FAdd); 158196000Sjkim 159196000Sjkim private: 160246849Sjkim typedef SmallVector<const FAddend*, 4> AddendVect; 161200553Sjkim 162200553Sjkim Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 163198237Sjkim 164246849Sjkim Value *performFactorization(Instruction *I); 165246849Sjkim 166246849Sjkim /// Convert given addend to a Value 167249663Sjkim Value *createAddendVal(const FAddend &A, bool& NeedNeg); 168249663Sjkim 169246849Sjkim /// Return the number of instructions needed to emit the N-ary addition. 170246849Sjkim unsigned calcInstrNumber(const AddendVect& Vect); 171246849Sjkim Value *createFSub(Value *Opnd0, Value *Opnd1); 172246849Sjkim Value *createFAdd(Value *Opnd0, Value *Opnd1); 173249663Sjkim Value *createFMul(Value *Opnd0, Value *Opnd1); 174246849Sjkim Value *createFDiv(Value *Opnd0, Value *Opnd1); 175246849Sjkim Value *createFNeg(Value *V); 176246849Sjkim Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 177246849Sjkim void createInstPostProc(Instruction *NewInst); 178246849Sjkim 179246849Sjkim InstCombiner::BuilderTy *Builder; 180246849Sjkim Instruction *Instr; 181246849Sjkim 182246849Sjkim private: 183246849Sjkim // Debugging stuff are clustered here. 184246849Sjkim #ifndef NDEBUG 185246849Sjkim unsigned CreateInstrNum; 186246849Sjkim void initCreateInstNum() { CreateInstrNum = 0; } 187246849Sjkim void incCreateInstNum() { CreateInstrNum++; } 188246849Sjkim #else 189246849Sjkim void initCreateInstNum() {} 190246849Sjkim void incCreateInstNum() {} 191246849Sjkim #endif 192246849Sjkim }; 193246849Sjkim} 194246849Sjkim 195246849Sjkim//===----------------------------------------------------------------------===// 196249663Sjkim// 197246849Sjkim// Implementation of 198246849Sjkim// {FAddendCoef, FAddend, FAddition, FAddCombine}. 199246849Sjkim// 200246849Sjkim//===----------------------------------------------------------------------===// 201246849SjkimFAddendCoef::~FAddendCoef() { 202198237Sjkim if (BufHasFpVal) 203198237Sjkim getFpValPtr()->~APFloat(); 204200553Sjkim} 205200553Sjkim 206198237Sjkimvoid FAddendCoef::set(const APFloat& C) { 207246849Sjkim APFloat *P = getFpValPtr(); 208246849Sjkim 209246849Sjkim if (isInt()) { 210246849Sjkim // As the buffer is meanless byte stream, we cannot call 211246849Sjkim // APFloat::operator=(). 212246849Sjkim new(P) APFloat(C); 213281075Sdim } else 214246849Sjkim *P = C; 215246849Sjkim 216246849Sjkim IsFp = BufHasFpVal = true; 217246849Sjkim} 218246849Sjkim 219281075Sdimvoid FAddendCoef::convertToFpType(const fltSemantics &Sem) { 220281075Sdim if (!isInt()) 221281075Sdim return; 222281075Sdim 223246849Sjkim APFloat *P = getFpValPtr(); 224281075Sdim if (IntVal > 0) 225281075Sdim new(P) APFloat(Sem, IntVal); 226281075Sdim else { 227281075Sdim new(P) APFloat(Sem, 0 - IntVal); 228281075Sdim P->changeSign(); 229281075Sdim } 230281075Sdim IsFp = BufHasFpVal = true; 231281075Sdim} 232281075Sdim 233281075SdimAPFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 234281075Sdim if (Val >= 0) 235281075Sdim return APFloat(Sem, Val); 236281075Sdim 237246849Sjkim APFloat T(Sem, 0 - Val); 238246849Sjkim T.changeSign(); 239246849Sjkim 240246849Sjkim return T; 241200553Sjkim} 242196000Sjkim 243200553Sjkimvoid FAddendCoef::operator=(const FAddendCoef &That) { 244200553Sjkim if (That.isInt()) 245200553Sjkim set(That.IntVal); 246200553Sjkim else 247200553Sjkim set(That.getFpVal()); 248200553Sjkim} 249200553Sjkim 250200553Sjkimvoid FAddendCoef::operator+=(const FAddendCoef &That) { 251200553Sjkim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 252200553Sjkim if (isInt() == That.isInt()) { 253200553Sjkim if (isInt()) 254200553Sjkim IntVal += That.IntVal; 255200553Sjkim else 256200553Sjkim getFpVal().add(That.getFpVal(), RndMode); 257200553Sjkim return; 258200553Sjkim } 259200553Sjkim 260200553Sjkim if (isInt()) { 261200553Sjkim const APFloat &T = That.getFpVal(); 262200553Sjkim convertToFpType(T.getSemantics()); 263200553Sjkim getFpVal().add(T, RndMode); 264200553Sjkim return; 265200553Sjkim } 266200553Sjkim 267233617Sjkim APFloat &T = getFpVal(); 268233617Sjkim T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 269233617Sjkim} 270233617Sjkim 271233617Sjkimvoid FAddendCoef::operator-=(const FAddendCoef &That) { 272233617Sjkim enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 273233617Sjkim if (isInt() == That.isInt()) { 274233617Sjkim if (isInt()) 275249663Sjkim IntVal -= That.IntVal; 276200553Sjkim else 277200553Sjkim getFpVal().subtract(That.getFpVal(), RndMode); 278233617Sjkim return; 279233617Sjkim } 280233617Sjkim 281233617Sjkim if (isInt()) { 282233617Sjkim const APFloat &T = That.getFpVal(); 283249663Sjkim convertToFpType(T.getSemantics()); 284233617Sjkim getFpVal().subtract(T, RndMode); 285200553Sjkim return; 286200553Sjkim } 287200553Sjkim 288200553Sjkim APFloat &T = getFpVal(); 289200553Sjkim T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 290200553Sjkim} 291200553Sjkim 292200553Sjkimvoid FAddendCoef::operator*=(const FAddendCoef &That) { 293200553Sjkim if (That.isOne()) 294200553Sjkim return; 295200553Sjkim 296200553Sjkim if (That.isMinusOne()) { 297200553Sjkim negate(); 298200553Sjkim return; 299233617Sjkim } 300233617Sjkim 301233617Sjkim if (isInt() && That.isInt()) { 302233617Sjkim int Res = IntVal * (int)That.IntVal; 303233617Sjkim assert(!insaneIntVal(Res) && "Insane int value"); 304233617Sjkim IntVal = Res; 305233617Sjkim return; 306233617Sjkim } 307233617Sjkim 308249663Sjkim const fltSemantics &Semantic = 309233617Sjkim isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 310233617Sjkim 311233617Sjkim if (isInt()) 312233555Sjkim convertToFpType(Semantic); 313233617Sjkim APFloat &F0 = getFpVal(); 314233617Sjkim 315233617Sjkim if (That.isInt()) 316233617Sjkim F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 317200553Sjkim APFloat::rmNearestTiesToEven); 318200553Sjkim else 319200553Sjkim F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 320233617Sjkim 321249663Sjkim return; 322200553Sjkim} 323200553Sjkim 324200553Sjkimvoid FAddendCoef::negate() { 325200553Sjkim if (isInt()) 326200553Sjkim IntVal = 0 - IntVal; 327200553Sjkim else 328249663Sjkim getFpVal().changeSign(); 329200553Sjkim} 330200553Sjkim 331200553SjkimValue *FAddendCoef::getValue(Type *Ty) const { 332200553Sjkim return isInt() ? 333200553Sjkim ConstantFP::get(Ty, float(IntVal)) : 334200553Sjkim ConstantFP::get(Ty->getContext(), getFpVal()); 335200553Sjkim} 336249663Sjkim 337200553Sjkim// The definition of <Val> Addends 338200553Sjkim// ========================================= 339200553Sjkim// A + B <1, A>, <1,B> 340200553Sjkim// A - B <1, A>, <1,B> 341246849Sjkim// 0 - B <-1, B> 342200553Sjkim// C * A, <C, A> 343246849Sjkim// A + C <1, A> <C, NULL> 344200553Sjkim// 0 +/- 0 <0, NULL> (corner case) 345246849Sjkim// 346246849Sjkim// Legend: A and B are not constant, C is constant 347246849Sjkim// 348246849Sjkimunsigned FAddend::drillValueDownOneStep 349246849Sjkim (Value *Val, FAddend &Addend0, FAddend &Addend1) { 350200553Sjkim Instruction *I = 0; 351246849Sjkim if (Val == 0 || !(I = dyn_cast<Instruction>(Val))) 352200553Sjkim return 0; 353246849Sjkim 354200553Sjkim unsigned Opcode = I->getOpcode(); 355246849Sjkim 356200553Sjkim if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 357246849Sjkim ConstantFP *C0, *C1; 358246849Sjkim Value *Opnd0 = I->getOperand(0); 359246849Sjkim Value *Opnd1 = I->getOperand(1); 360246849Sjkim if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 361246849Sjkim Opnd0 = 0; 362200553Sjkim 363246849Sjkim if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 364200553Sjkim Opnd1 = 0; 365200553Sjkim 366246849Sjkim if (Opnd0) { 367200553Sjkim if (!C0) 368246849Sjkim Addend0.set(1, Opnd0); 369246849Sjkim else 370200553Sjkim Addend0.set(C0, 0); 371246849Sjkim } 372200553Sjkim 373246849Sjkim if (Opnd1) { 374200553Sjkim FAddend &Addend = Opnd0 ? Addend1 : Addend0; 375246849Sjkim if (!C1) 376246849Sjkim Addend.set(1, Opnd1); 377200553Sjkim else 378246849Sjkim Addend.set(C1, 0); 379200553Sjkim if (Opcode == Instruction::FSub) 380200553Sjkim Addend.negate(); 381246849Sjkim } 382196000Sjkim 383246849Sjkim if (Opnd0 || Opnd1) 384200553Sjkim return Opnd0 && Opnd1 ? 2 : 1; 385198237Sjkim 386246849Sjkim // Both operands are zero. Weird! 387200553Sjkim Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0); 388200553Sjkim return 1; 389200553Sjkim } 390200553Sjkim 391200553Sjkim if (I->getOpcode() == Instruction::FMul) { 392202771Sjkim Value *V0 = I->getOperand(0); 393202771Sjkim Value *V1 = I->getOperand(1); 394249663Sjkim if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 395202771Sjkim Addend0.set(C, V1); 396202771Sjkim return 1; 397202771Sjkim } 398202771Sjkim 399202771Sjkim if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 400202771Sjkim Addend0.set(C, V0); 401202771Sjkim return 1; 402202771Sjkim } 403202771Sjkim } 404202771Sjkim 405202771Sjkim return 0; 406202771Sjkim} 407202771Sjkim 408202771Sjkim// Try to break *this* addend into two addends. e.g. Suppose this addend is 409202771Sjkim// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 410249663Sjkim// i.e. <2.3, X> and <2.3, Y>. 411202771Sjkim// 412202771Sjkimunsigned FAddend::drillAddendDownOneStep 413202771Sjkim (FAddend &Addend0, FAddend &Addend1) const { 414202771Sjkim if (isConstant()) 415202771Sjkim return 0; 416202771Sjkim 417202771Sjkim unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 418202771Sjkim if (!BreakNum || Coeff.isOne()) 419202771Sjkim return BreakNum; 420202771Sjkim 421202771Sjkim Addend0.Scale(Coeff); 422202771Sjkim 423202771Sjkim if (BreakNum == 2) 424202771Sjkim Addend1.Scale(Coeff); 425202771Sjkim 426202771Sjkim return BreakNum; 427202771Sjkim} 428202771Sjkim 429202771Sjkim// Try to perform following optimization on the input instruction I. Return the 430202771Sjkim// simplified expression if was successful; otherwise, return 0. 431202771Sjkim// 432202771Sjkim// Instruction "I" is Simplified into 433202771Sjkim// ------------------------------------------------------- 434202771Sjkim// (x * y) +/- (x * z) x * (y +/- z) 435202771Sjkim// (y / x) +/- (z / x) (y +/- z) / x 436202771Sjkim// 437202771SjkimValue *FAddCombine::performFactorization(Instruction *I) { 438202771Sjkim assert((I->getOpcode() == Instruction::FAdd || 439209746Sjkim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 440202771Sjkim 441202771Sjkim Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 442202771Sjkim Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 443202771Sjkim 444202771Sjkim if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 445202771Sjkim return 0; 446202771Sjkim 447202771Sjkim bool isMpy = false; 448202771Sjkim if (I0->getOpcode() == Instruction::FMul) 449202771Sjkim isMpy = true; 450202771Sjkim else if (I0->getOpcode() != Instruction::FDiv) 451202771Sjkim return 0; 452202771Sjkim 453202771Sjkim Value *Opnd0_0 = I0->getOperand(0); 454202771Sjkim Value *Opnd0_1 = I0->getOperand(1); 455202771Sjkim Value *Opnd1_0 = I1->getOperand(0); 456202771Sjkim Value *Opnd1_1 = I1->getOperand(1); 457202771Sjkim 458202771Sjkim // Input Instr I Factor AddSub0 AddSub1 459202771Sjkim // ---------------------------------------------- 460202771Sjkim // (x*y) +/- (x*z) x y z 461202771Sjkim // (y/x) +/- (z/x) x y z 462202771Sjkim // 463202771Sjkim Value *Factor = 0; 464202771Sjkim Value *AddSub0 = 0, *AddSub1 = 0; 465202771Sjkim 466202771Sjkim if (isMpy) { 467249663Sjkim if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 468202771Sjkim Factor = Opnd0_0; 469202771Sjkim else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 470202771Sjkim Factor = Opnd0_1; 471249663Sjkim 472202771Sjkim if (Factor) { 473202771Sjkim AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 474249663Sjkim AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 475202771Sjkim } 476202771Sjkim } else if (Opnd0_1 == Opnd1_1) { 477202771Sjkim Factor = Opnd0_1; 478202771Sjkim AddSub0 = Opnd0_0; 479202771Sjkim AddSub1 = Opnd1_0; 480202771Sjkim } 481202771Sjkim 482202771Sjkim if (!Factor) 483249663Sjkim return 0; 484202771Sjkim 485202771Sjkim // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 486202771Sjkim Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 487202771Sjkim createFAdd(AddSub0, AddSub1) : 488202771Sjkim createFSub(AddSub0, AddSub1); 489202771Sjkim if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 490281075Sdim const APFloat &F = CFP->getValueAPF(); 491202771Sjkim if (!F.isNormal() || F.isDenormal()) 492202771Sjkim return 0; 493202771Sjkim } 494202771Sjkim 495202771Sjkim if (isMpy) 496202771Sjkim return createFMul(Factor, NewAddSub); 497249663Sjkim 498202771Sjkim return createFDiv(NewAddSub, Factor); 499202771Sjkim} 500202771Sjkim 501202771SjkimValue *FAddCombine::simplify(Instruction *I) { 502202771Sjkim assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 503202771Sjkim 504202771Sjkim // Currently we are not able to handle vector type. 505202771Sjkim if (I->getType()->isVectorTy()) 506202771Sjkim return 0; 507202771Sjkim 508202771Sjkim assert((I->getOpcode() == Instruction::FAdd || 509202771Sjkim I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 510202771Sjkim 511202771Sjkim // Save the instruction before calling other member-functions. 512220663Sjkim Instr = I; 513220663Sjkim 514281075Sdim FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 515202771Sjkim 516202771Sjkim unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 517202771Sjkim 518202771Sjkim // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 519202771Sjkim unsigned Opnd0_ExpNum = 0; 520202771Sjkim unsigned Opnd1_ExpNum = 0; 521202771Sjkim 522202771Sjkim if (!Opnd0.isConstant()) 523202771Sjkim Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 524202771Sjkim 525228110Sjkim // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 526250838Sjkim if (OpndNum == 2 && !Opnd1.isConstant()) 527202771Sjkim Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 528202771Sjkim 529202771Sjkim // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 530220663Sjkim if (Opnd0_ExpNum && Opnd1_ExpNum) { 531220663Sjkim AddendVect AllOpnds; 532202771Sjkim AllOpnds.push_back(&Opnd0_0); 533202771Sjkim AllOpnds.push_back(&Opnd1_0); 534202771Sjkim if (Opnd0_ExpNum == 2) 535202771Sjkim AllOpnds.push_back(&Opnd0_1); 536202771Sjkim if (Opnd1_ExpNum == 2) 537202771Sjkim AllOpnds.push_back(&Opnd1_1); 538202771Sjkim 539202771Sjkim // Compute instruction quota. We should save at least one instruction. 540202771Sjkim unsigned InstQuota = 0; 541202771Sjkim 542202771Sjkim Value *V0 = I->getOperand(0); 543202771Sjkim Value *V1 = I->getOperand(1); 544202771Sjkim InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 545202771Sjkim (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 546202771Sjkim 547202771Sjkim if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 548202771Sjkim return R; 549202771Sjkim } 550202771Sjkim 551202771Sjkim if (OpndNum != 2) { 552202771Sjkim // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 553202771Sjkim // splitted into two addends, say "V = X - Y", the instruction would have 554202771Sjkim // been optimized into "I = Y - X" in the previous steps. 555202771Sjkim // 556202771Sjkim const FAddendCoef &CE = Opnd0.getCoef(); 557202771Sjkim return CE.isOne() ? Opnd0.getSymVal() : 0; 558202771Sjkim } 559202771Sjkim 560202771Sjkim // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 561202771Sjkim if (Opnd1_ExpNum) { 562202771Sjkim AddendVect AllOpnds; 563249663Sjkim AllOpnds.push_back(&Opnd0); 564202771Sjkim AllOpnds.push_back(&Opnd1_0); 565202771Sjkim if (Opnd1_ExpNum == 2) 566202771Sjkim AllOpnds.push_back(&Opnd1_1); 567202771Sjkim 568202771Sjkim if (Value *R = simplifyFAdd(AllOpnds, 1)) 569202771Sjkim return R; 570202771Sjkim } 571202771Sjkim 572202771Sjkim // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 573202771Sjkim if (Opnd0_ExpNum) { 574202771Sjkim AddendVect AllOpnds; 575233617Sjkim AllOpnds.push_back(&Opnd1); 576196000Sjkim AllOpnds.push_back(&Opnd0_0); 577249663Sjkim if (Opnd0_ExpNum == 2) 578233617Sjkim AllOpnds.push_back(&Opnd0_1); 579233617Sjkim 580196000Sjkim if (Value *R = simplifyFAdd(AllOpnds, 1)) 581196000Sjkim return R; 582196000Sjkim } 583233617Sjkim 584233617Sjkim // step 6: Try factorization as the last resort, 585233617Sjkim return performFactorization(I); 586233617Sjkim} 587233617Sjkim 588233617SjkimValue *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 589233617Sjkim 590196000Sjkim unsigned AddendNum = Addends.size(); 591196000Sjkim assert(AddendNum <= 4 && "Too many addends"); 592233617Sjkim 593233617Sjkim // For saving intermediate results; 594196000Sjkim unsigned NextTmpIdx = 0; 595196000Sjkim FAddend TmpResult[3]; 596196000Sjkim 597196000Sjkim // Points to the constant addend of the resulting simplified expression. 598233617Sjkim // If the resulting expr has constant-addend, this constant-addend is 599249663Sjkim // desirable to reside at the top of the resulting expression tree. Placing 600233617Sjkim // constant close to supper-expr(s) will potentially reveal some optimization 601196000Sjkim // opportunities in super-expr(s). 602196000Sjkim // 603196000Sjkim const FAddend *ConstAdd = 0; 604196000Sjkim 605196000Sjkim // Simplified addends are placed <SimpVect>. 606233617Sjkim AddendVect SimpVect; 607200553Sjkim 608200553Sjkim // The outer loop works on one symbolic-value at a time. Suppose the input 609196000Sjkim // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 610196000Sjkim // The symbolic-values will be processed in this order: x, y, z. 611233617Sjkim // 612196000Sjkim for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 613196000Sjkim 614196000Sjkim const FAddend *ThisAddend = Addends[SymIdx]; 615196000Sjkim if (!ThisAddend) { 616196000Sjkim // This addend was processed before. 617196000Sjkim continue; 618196000Sjkim } 619233617Sjkim 620196000Sjkim Value *Val = ThisAddend->getSymVal(); 621233617Sjkim unsigned StartIdx = SimpVect.size(); 622233617Sjkim SimpVect.push_back(ThisAddend); 623249663Sjkim 624233617Sjkim // The inner loop collects addends sharing same symbolic-value, and these 625196000Sjkim // addends will be later on folded into a single addend. Following above 626196000Sjkim // example, if the symbolic value "y" is being processed, the inner loop 627196000Sjkim // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 628249663Sjkim // be later on folded into "<b1+b2, y>". 629196000Sjkim // 630196000Sjkim for (unsigned SameSymIdx = SymIdx + 1; 631 SameSymIdx < AddendNum; SameSymIdx++) { 632 const FAddend *T = Addends[SameSymIdx]; 633 if (T && T->getSymVal() == Val) { 634 // Set null such that next iteration of the outer loop will not process 635 // this addend again. 636 Addends[SameSymIdx] = 0; 637 SimpVect.push_back(T); 638 } 639 } 640 641 // If multiple addends share same symbolic value, fold them together. 642 if (StartIdx + 1 != SimpVect.size()) { 643 FAddend &R = TmpResult[NextTmpIdx ++]; 644 R = *SimpVect[StartIdx]; 645 for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++) 646 R += *SimpVect[Idx]; 647 648 // Pop all addends being folded and push the resulting folded addend. 649 SimpVect.resize(StartIdx); 650 if (Val != 0) { 651 if (!R.isZero()) { 652 SimpVect.push_back(&R); 653 } 654 } else { 655 // Don't push constant addend at this time. It will be the last element 656 // of <SimpVect>. 657 ConstAdd = &R; 658 } 659 } 660 } 661 662 assert((NextTmpIdx <= sizeof(TmpResult)/sizeof(TmpResult[0]) + 1) && 663 "out-of-bound access"); 664 665 if (ConstAdd) 666 SimpVect.push_back(ConstAdd); 667 668 Value *Result; 669 if (!SimpVect.empty()) 670 Result = createNaryFAdd(SimpVect, InstrQuota); 671 else { 672 // The addition is folded to 0.0. 673 Result = ConstantFP::get(Instr->getType(), 0.0); 674 } 675 676 return Result; 677} 678 679Value *FAddCombine::createNaryFAdd 680 (const AddendVect &Opnds, unsigned InstrQuota) { 681 assert(!Opnds.empty() && "Expect at least one addend"); 682 683 // Step 1: Check if the # of instructions needed exceeds the quota. 684 // 685 unsigned InstrNeeded = calcInstrNumber(Opnds); 686 if (InstrNeeded > InstrQuota) 687 return 0; 688 689 initCreateInstNum(); 690 691 // step 2: Emit the N-ary addition. 692 // Note that at most three instructions are involved in Fadd-InstCombine: the 693 // addition in question, and at most two neighboring instructions. 694 // The resulting optimized addition should have at least one less instruction 695 // than the original addition expression tree. This implies that the resulting 696 // N-ary addition has at most two instructions, and we don't need to worry 697 // about tree-height when constructing the N-ary addition. 698 699 Value *LastVal = 0; 700 bool LastValNeedNeg = false; 701 702 // Iterate the addends, creating fadd/fsub using adjacent two addends. 703 for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 704 I != E; I++) { 705 bool NeedNeg; 706 Value *V = createAddendVal(**I, NeedNeg); 707 if (!LastVal) { 708 LastVal = V; 709 LastValNeedNeg = NeedNeg; 710 continue; 711 } 712 713 if (LastValNeedNeg == NeedNeg) { 714 LastVal = createFAdd(LastVal, V); 715 continue; 716 } 717 718 if (LastValNeedNeg) 719 LastVal = createFSub(V, LastVal); 720 else 721 LastVal = createFSub(LastVal, V); 722 723 LastValNeedNeg = false; 724 } 725 726 if (LastValNeedNeg) { 727 LastVal = createFNeg(LastVal); 728 } 729 730 #ifndef NDEBUG 731 assert(CreateInstrNum == InstrNeeded && 732 "Inconsistent in instruction numbers"); 733 #endif 734 735 return LastVal; 736} 737 738Value *FAddCombine::createFSub 739 (Value *Opnd0, Value *Opnd1) { 740 Value *V = Builder->CreateFSub(Opnd0, Opnd1); 741 if (Instruction *I = dyn_cast<Instruction>(V)) 742 createInstPostProc(I); 743 return V; 744} 745 746Value *FAddCombine::createFNeg(Value *V) { 747 Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0)); 748 return createFSub(Zero, V); 749} 750 751Value *FAddCombine::createFAdd 752 (Value *Opnd0, Value *Opnd1) { 753 Value *V = Builder->CreateFAdd(Opnd0, Opnd1); 754 if (Instruction *I = dyn_cast<Instruction>(V)) 755 createInstPostProc(I); 756 return V; 757} 758 759Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { 760 Value *V = Builder->CreateFMul(Opnd0, Opnd1); 761 if (Instruction *I = dyn_cast<Instruction>(V)) 762 createInstPostProc(I); 763 return V; 764} 765 766Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) { 767 Value *V = Builder->CreateFDiv(Opnd0, Opnd1); 768 if (Instruction *I = dyn_cast<Instruction>(V)) 769 createInstPostProc(I); 770 return V; 771} 772 773void FAddCombine::createInstPostProc(Instruction *NewInstr) { 774 NewInstr->setDebugLoc(Instr->getDebugLoc()); 775 776 // Keep track of the number of instruction created. 777 incCreateInstNum(); 778 779 // Propagate fast-math flags 780 NewInstr->setFastMathFlags(Instr->getFastMathFlags()); 781} 782 783// Return the number of instruction needed to emit the N-ary addition. 784// NOTE: Keep this function in sync with createAddendVal(). 785unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { 786 unsigned OpndNum = Opnds.size(); 787 unsigned InstrNeeded = OpndNum - 1; 788 789 // The number of addends in the form of "(-1)*x". 790 unsigned NegOpndNum = 0; 791 792 // Adjust the number of instructions needed to emit the N-ary add. 793 for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end(); 794 I != E; I++) { 795 const FAddend *Opnd = *I; 796 if (Opnd->isConstant()) 797 continue; 798 799 const FAddendCoef &CE = Opnd->getCoef(); 800 if (CE.isMinusOne() || CE.isMinusTwo()) 801 NegOpndNum++; 802 803 // Let the addend be "c * x". If "c == +/-1", the value of the addend 804 // is immediately available; otherwise, it needs exactly one instruction 805 // to evaluate the value. 806 if (!CE.isMinusOne() && !CE.isOne()) 807 InstrNeeded++; 808 } 809 if (NegOpndNum == OpndNum) 810 InstrNeeded++; 811 return InstrNeeded; 812} 813 814// Input Addend Value NeedNeg(output) 815// ================================================================ 816// Constant C C false 817// <+/-1, V> V coefficient is -1 818// <2/-2, V> "fadd V, V" coefficient is -2 819// <C, V> "fmul V, C" false 820// 821// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber. 822Value *FAddCombine::createAddendVal 823 (const FAddend &Opnd, bool &NeedNeg) { 824 const FAddendCoef &Coeff = Opnd.getCoef(); 825 826 if (Opnd.isConstant()) { 827 NeedNeg = false; 828 return Coeff.getValue(Instr->getType()); 829 } 830 831 Value *OpndVal = Opnd.getSymVal(); 832 833 if (Coeff.isMinusOne() || Coeff.isOne()) { 834 NeedNeg = Coeff.isMinusOne(); 835 return OpndVal; 836 } 837 838 if (Coeff.isTwo() || Coeff.isMinusTwo()) { 839 NeedNeg = Coeff.isMinusTwo(); 840 return createFAdd(OpndVal, OpndVal); 841 } 842 843 NeedNeg = false; 844 return createFMul(OpndVal, Coeff.getValue(Instr->getType())); 845} 846 847/// AddOne - Add one to a ConstantInt. 848static Constant *AddOne(Constant *C) { 849 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 850} 851 852/// SubOne - Subtract one from a ConstantInt. 853static Constant *SubOne(ConstantInt *C) { 854 return ConstantInt::get(C->getContext(), C->getValue()-1); 855} 856 857 858// dyn_castFoldableMul - If this value is a multiply that can be folded into 859// other computations (because it has a constant operand), return the 860// non-constant operand of the multiply, and set CST to point to the multiplier. 861// Otherwise, return null. 862// 863static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 864 if (!V->hasOneUse() || !V->getType()->isIntegerTy()) 865 return 0; 866 867 Instruction *I = dyn_cast<Instruction>(V); 868 if (I == 0) return 0; 869 870 if (I->getOpcode() == Instruction::Mul) 871 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 872 return I->getOperand(0); 873 if (I->getOpcode() == Instruction::Shl) 874 if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 875 // The multiplier is really 1 << CST. 876 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 877 uint32_t CSTVal = CST->getLimitedValue(BitWidth); 878 CST = ConstantInt::get(V->getType()->getContext(), 879 APInt(BitWidth, 1).shl(CSTVal)); 880 return I->getOperand(0); 881 } 882 return 0; 883} 884 885 886/// WillNotOverflowSignedAdd - Return true if we can prove that: 887/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 888/// This basically requires proving that the add in the original type would not 889/// overflow to change the sign bit or have a carry out. 890bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 891 // There are different heuristics we can use for this. Here are some simple 892 // ones. 893 894 // Add has the property that adding any two 2's complement numbers can only 895 // have one carry bit which can change a sign. As such, if LHS and RHS each 896 // have at least two sign bits, we know that the addition of the two values 897 // will sign extend fine. 898 if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 899 return true; 900 901 902 // If one of the operands only has one non-zero bit, and if the other operand 903 // has a known-zero bit in a more significant place than it (not including the 904 // sign bit) the ripple may go up to and fill the zero, but won't change the 905 // sign. For example, (X & ~4) + 1. 906 907 // TODO: Implement. 908 909 return false; 910} 911 912Instruction *InstCombiner::visitAdd(BinaryOperator &I) { 913 bool Changed = SimplifyAssociativeOrCommutative(I); 914 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 915 916 if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 917 I.hasNoUnsignedWrap(), TD)) 918 return ReplaceInstUsesWith(I, V); 919 920 // (A*B)+(A*C) -> A*(B+C) etc 921 if (Value *V = SimplifyUsingDistributiveLaws(I)) 922 return ReplaceInstUsesWith(I, V); 923 924 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 925 // X + (signbit) --> X ^ signbit 926 const APInt &Val = CI->getValue(); 927 if (Val.isSignBit()) 928 return BinaryOperator::CreateXor(LHS, RHS); 929 930 // See if SimplifyDemandedBits can simplify this. This handles stuff like 931 // (X & 254)+1 -> (X&254)|1 932 if (SimplifyDemandedInstructionBits(I)) 933 return &I; 934 935 // zext(bool) + C -> bool ? C + 1 : C 936 if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 937 if (ZI->getSrcTy()->isIntegerTy(1)) 938 return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 939 940 Value *XorLHS = 0; ConstantInt *XorRHS = 0; 941 if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 942 uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 943 const APInt &RHSVal = CI->getValue(); 944 unsigned ExtendAmt = 0; 945 // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 946 // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 947 if (XorRHS->getValue() == -RHSVal) { 948 if (RHSVal.isPowerOf2()) 949 ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 950 else if (XorRHS->getValue().isPowerOf2()) 951 ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 952 } 953 954 if (ExtendAmt) { 955 APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 956 if (!MaskedValueIsZero(XorLHS, Mask)) 957 ExtendAmt = 0; 958 } 959 960 if (ExtendAmt) { 961 Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 962 Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 963 return BinaryOperator::CreateAShr(NewShl, ShAmt); 964 } 965 966 // If this is a xor that was canonicalized from a sub, turn it back into 967 // a sub and fuse this add with it. 968 if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) { 969 IntegerType *IT = cast<IntegerType>(I.getType()); 970 APInt LHSKnownOne(IT->getBitWidth(), 0); 971 APInt LHSKnownZero(IT->getBitWidth(), 0); 972 ComputeMaskedBits(XorLHS, LHSKnownZero, LHSKnownOne); 973 if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue()) 974 return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI), 975 XorLHS); 976 } 977 // (X + signbit) + C could have gotten canonicalized to (X ^ signbit) + C, 978 // transform them into (X + (signbit ^ C)) 979 if (XorRHS->getValue().isSignBit()) 980 return BinaryOperator::CreateAdd(XorLHS, 981 ConstantExpr::getXor(XorRHS, CI)); 982 } 983 } 984 985 if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 986 if (Instruction *NV = FoldOpIntoPhi(I)) 987 return NV; 988 989 if (I.getType()->isIntegerTy(1)) 990 return BinaryOperator::CreateXor(LHS, RHS); 991 992 // X + X --> X << 1 993 if (LHS == RHS) { 994 BinaryOperator *New = 995 BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 996 New->setHasNoSignedWrap(I.hasNoSignedWrap()); 997 New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 998 return New; 999 } 1000 1001 // -A + B --> B - A 1002 // -A + -B --> -(A + B) 1003 if (Value *LHSV = dyn_castNegVal(LHS)) { 1004 if (!isa<Constant>(RHS)) 1005 if (Value *RHSV = dyn_castNegVal(RHS)) { 1006 Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 1007 return BinaryOperator::CreateNeg(NewAdd); 1008 } 1009 1010 return BinaryOperator::CreateSub(RHS, LHSV); 1011 } 1012 1013 // A + -B --> A - B 1014 if (!isa<Constant>(RHS)) 1015 if (Value *V = dyn_castNegVal(RHS)) 1016 return BinaryOperator::CreateSub(LHS, V); 1017 1018 1019 ConstantInt *C2; 1020 if (Value *X = dyn_castFoldableMul(LHS, C2)) { 1021 if (X == RHS) // X*C + X --> X * (C+1) 1022 return BinaryOperator::CreateMul(RHS, AddOne(C2)); 1023 1024 // X*C1 + X*C2 --> X * (C1+C2) 1025 ConstantInt *C1; 1026 if (X == dyn_castFoldableMul(RHS, C1)) 1027 return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 1028 } 1029 1030 // X + X*C --> X * (C+1) 1031 if (dyn_castFoldableMul(RHS, C2) == LHS) 1032 return BinaryOperator::CreateMul(LHS, AddOne(C2)); 1033 1034 // A+B --> A|B iff A and B have no bits set in common. 1035 if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 1036 APInt LHSKnownOne(IT->getBitWidth(), 0); 1037 APInt LHSKnownZero(IT->getBitWidth(), 0); 1038 ComputeMaskedBits(LHS, LHSKnownZero, LHSKnownOne); 1039 if (LHSKnownZero != 0) { 1040 APInt RHSKnownOne(IT->getBitWidth(), 0); 1041 APInt RHSKnownZero(IT->getBitWidth(), 0); 1042 ComputeMaskedBits(RHS, RHSKnownZero, RHSKnownOne); 1043 1044 // No bits in common -> bitwise or. 1045 if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 1046 return BinaryOperator::CreateOr(LHS, RHS); 1047 } 1048 } 1049 1050 // W*X + Y*Z --> W * (X+Z) iff W == Y 1051 { 1052 Value *W, *X, *Y, *Z; 1053 if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 1054 match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 1055 if (W != Y) { 1056 if (W == Z) { 1057 std::swap(Y, Z); 1058 } else if (Y == X) { 1059 std::swap(W, X); 1060 } else if (X == Z) { 1061 std::swap(Y, Z); 1062 std::swap(W, X); 1063 } 1064 } 1065 1066 if (W == Y) { 1067 Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 1068 return BinaryOperator::CreateMul(W, NewAdd); 1069 } 1070 } 1071 } 1072 1073 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 1074 Value *X = 0; 1075 if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 1076 return BinaryOperator::CreateSub(SubOne(CRHS), X); 1077 1078 // (X & FF00) + xx00 -> (X+xx00) & FF00 1079 if (LHS->hasOneUse() && 1080 match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 1081 CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 1082 // See if all bits from the first bit set in the Add RHS up are included 1083 // in the mask. First, get the rightmost bit. 1084 const APInt &AddRHSV = CRHS->getValue(); 1085 1086 // Form a mask of all bits from the lowest bit added through the top. 1087 APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 1088 1089 // See if the and mask includes all of these bits. 1090 APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 1091 1092 if (AddRHSHighBits == AddRHSHighBitsAnd) { 1093 // Okay, the xform is safe. Insert the new add pronto. 1094 Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 1095 return BinaryOperator::CreateAnd(NewAdd, C2); 1096 } 1097 } 1098 1099 // Try to fold constant add into select arguments. 1100 if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 1101 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1102 return R; 1103 } 1104 1105 // add (select X 0 (sub n A)) A --> select X A n 1106 { 1107 SelectInst *SI = dyn_cast<SelectInst>(LHS); 1108 Value *A = RHS; 1109 if (!SI) { 1110 SI = dyn_cast<SelectInst>(RHS); 1111 A = LHS; 1112 } 1113 if (SI && SI->hasOneUse()) { 1114 Value *TV = SI->getTrueValue(); 1115 Value *FV = SI->getFalseValue(); 1116 Value *N; 1117 1118 // Can we fold the add into the argument of the select? 1119 // We check both true and false select arguments for a matching subtract. 1120 if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 1121 // Fold the add into the true select value. 1122 return SelectInst::Create(SI->getCondition(), N, A); 1123 1124 if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 1125 // Fold the add into the false select value. 1126 return SelectInst::Create(SI->getCondition(), A, N); 1127 } 1128 } 1129 1130 // Check for (add (sext x), y), see if we can merge this into an 1131 // integer add followed by a sext. 1132 if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 1133 // (add (sext x), cst) --> (sext (add x, cst')) 1134 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 1135 Constant *CI = 1136 ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 1137 if (LHSConv->hasOneUse() && 1138 ConstantExpr::getSExt(CI, I.getType()) == RHSC && 1139 WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1140 // Insert the new, smaller add. 1141 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1142 CI, "addconv"); 1143 return new SExtInst(NewAdd, I.getType()); 1144 } 1145 } 1146 1147 // (add (sext x), (sext y)) --> (sext (add int x, y)) 1148 if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 1149 // Only do this if x/y have the same type, if at last one of them has a 1150 // single use (so we don't increase the number of sexts), and if the 1151 // integer add will not overflow. 1152 if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1153 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1154 WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1155 RHSConv->getOperand(0))) { 1156 // Insert the new integer add. 1157 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1158 RHSConv->getOperand(0), "addconv"); 1159 return new SExtInst(NewAdd, I.getType()); 1160 } 1161 } 1162 } 1163 1164 // Check for (x & y) + (x ^ y) 1165 { 1166 Value *A = 0, *B = 0; 1167 if (match(RHS, m_Xor(m_Value(A), m_Value(B))) && 1168 (match(LHS, m_And(m_Specific(A), m_Specific(B))) || 1169 match(LHS, m_And(m_Specific(B), m_Specific(A))))) 1170 return BinaryOperator::CreateOr(A, B); 1171 1172 if (match(LHS, m_Xor(m_Value(A), m_Value(B))) && 1173 (match(RHS, m_And(m_Specific(A), m_Specific(B))) || 1174 match(RHS, m_And(m_Specific(B), m_Specific(A))))) 1175 return BinaryOperator::CreateOr(A, B); 1176 } 1177 1178 return Changed ? &I : 0; 1179} 1180 1181Instruction *InstCombiner::visitFAdd(BinaryOperator &I) { 1182 bool Changed = SimplifyAssociativeOrCommutative(I); 1183 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 1184 1185 if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), TD)) 1186 return ReplaceInstUsesWith(I, V); 1187 1188 if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 1189 if (Instruction *NV = FoldOpIntoPhi(I)) 1190 return NV; 1191 1192 // -A + B --> B - A 1193 // -A + -B --> -(A + B) 1194 if (Value *LHSV = dyn_castFNegVal(LHS)) 1195 return BinaryOperator::CreateFSub(RHS, LHSV); 1196 1197 // A + -B --> A - B 1198 if (!isa<Constant>(RHS)) 1199 if (Value *V = dyn_castFNegVal(RHS)) 1200 return BinaryOperator::CreateFSub(LHS, V); 1201 1202 // Check for (fadd double (sitofp x), y), see if we can merge this into an 1203 // integer add followed by a promotion. 1204 if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 1205 // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 1206 // ... if the constant fits in the integer value. This is useful for things 1207 // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 1208 // requires a constant pool load, and generally allows the add to be better 1209 // instcombined. 1210 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 1211 Constant *CI = 1212 ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 1213 if (LHSConv->hasOneUse() && 1214 ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 1215 WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 1216 // Insert the new integer add. 1217 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1218 CI, "addconv"); 1219 return new SIToFPInst(NewAdd, I.getType()); 1220 } 1221 } 1222 1223 // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 1224 if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 1225 // Only do this if x/y have the same type, if at last one of them has a 1226 // single use (so we don't increase the number of int->fp conversions), 1227 // and if the integer add will not overflow. 1228 if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 1229 (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 1230 WillNotOverflowSignedAdd(LHSConv->getOperand(0), 1231 RHSConv->getOperand(0))) { 1232 // Insert the new integer add. 1233 Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 1234 RHSConv->getOperand(0),"addconv"); 1235 return new SIToFPInst(NewAdd, I.getType()); 1236 } 1237 } 1238 } 1239 1240 // select C, 0, B + select C, A, 0 -> select C, A, B 1241 { 1242 Value *A1, *B1, *C1, *A2, *B2, *C2; 1243 if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) && 1244 match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) { 1245 if (C1 == C2) { 1246 Constant *Z1=0, *Z2=0; 1247 Value *A, *B, *C=C1; 1248 if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) { 1249 Z1 = dyn_cast<Constant>(A1); A = A2; 1250 Z2 = dyn_cast<Constant>(B2); B = B1; 1251 } else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) { 1252 Z1 = dyn_cast<Constant>(B1); B = B2; 1253 Z2 = dyn_cast<Constant>(A2); A = A1; 1254 } 1255 1256 if (Z1 && Z2 && 1257 (I.hasNoSignedZeros() || 1258 (Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) { 1259 return SelectInst::Create(C, A, B); 1260 } 1261 } 1262 } 1263 } 1264 1265 if (I.hasUnsafeAlgebra()) { 1266 if (Value *V = FAddCombine(Builder).simplify(&I)) 1267 return ReplaceInstUsesWith(I, V); 1268 } 1269 1270 return Changed ? &I : 0; 1271} 1272 1273 1274/// Optimize pointer differences into the same array into a size. Consider: 1275/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 1276/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 1277/// 1278Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 1279 Type *Ty) { 1280 assert(TD && "Must have target data info for this"); 1281 1282 // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 1283 // this. 1284 bool Swapped = false; 1285 GEPOperator *GEP1 = 0, *GEP2 = 0; 1286 1287 // For now we require one side to be the base pointer "A" or a constant 1288 // GEP derived from it. 1289 if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1290 // (gep X, ...) - X 1291 if (LHSGEP->getOperand(0) == RHS) { 1292 GEP1 = LHSGEP; 1293 Swapped = false; 1294 } else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1295 // (gep X, ...) - (gep X, ...) 1296 if (LHSGEP->getOperand(0)->stripPointerCasts() == 1297 RHSGEP->getOperand(0)->stripPointerCasts()) { 1298 GEP2 = RHSGEP; 1299 GEP1 = LHSGEP; 1300 Swapped = false; 1301 } 1302 } 1303 } 1304 1305 if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) { 1306 // X - (gep X, ...) 1307 if (RHSGEP->getOperand(0) == LHS) { 1308 GEP1 = RHSGEP; 1309 Swapped = true; 1310 } else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) { 1311 // (gep X, ...) - (gep X, ...) 1312 if (RHSGEP->getOperand(0)->stripPointerCasts() == 1313 LHSGEP->getOperand(0)->stripPointerCasts()) { 1314 GEP2 = LHSGEP; 1315 GEP1 = RHSGEP; 1316 Swapped = true; 1317 } 1318 } 1319 } 1320 1321 // Avoid duplicating the arithmetic if GEP2 has non-constant indices and 1322 // multiple users. 1323 if (GEP1 == 0 || 1324 (GEP2 != 0 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse())) 1325 return 0; 1326 1327 // Emit the offset of the GEP and an intptr_t. 1328 Value *Result = EmitGEPOffset(GEP1); 1329 1330 // If we had a constant expression GEP on the other side offsetting the 1331 // pointer, subtract it from the offset we have. 1332 if (GEP2) { 1333 Value *Offset = EmitGEPOffset(GEP2); 1334 Result = Builder->CreateSub(Result, Offset); 1335 } 1336 1337 // If we have p - gep(p, ...) then we have to negate the result. 1338 if (Swapped) 1339 Result = Builder->CreateNeg(Result, "diff.neg"); 1340 1341 return Builder->CreateIntCast(Result, Ty, true); 1342} 1343 1344 1345Instruction *InstCombiner::visitSub(BinaryOperator &I) { 1346 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1347 1348 if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 1349 I.hasNoUnsignedWrap(), TD)) 1350 return ReplaceInstUsesWith(I, V); 1351 1352 // (A*B)-(A*C) -> A*(B-C) etc 1353 if (Value *V = SimplifyUsingDistributiveLaws(I)) 1354 return ReplaceInstUsesWith(I, V); 1355 1356 // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 1357 if (Value *V = dyn_castNegVal(Op1)) { 1358 BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 1359 Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 1360 Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 1361 return Res; 1362 } 1363 1364 if (I.getType()->isIntegerTy(1)) 1365 return BinaryOperator::CreateXor(Op0, Op1); 1366 1367 // Replace (-1 - A) with (~A). 1368 if (match(Op0, m_AllOnes())) 1369 return BinaryOperator::CreateNot(Op1); 1370 1371 if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 1372 // C - ~X == X + (1+C) 1373 Value *X = 0; 1374 if (match(Op1, m_Not(m_Value(X)))) 1375 return BinaryOperator::CreateAdd(X, AddOne(C)); 1376 1377 // -(X >>u 31) -> (X >>s 31) 1378 // -(X >>s 31) -> (X >>u 31) 1379 if (C->isZero()) { 1380 Value *X; ConstantInt *CI; 1381 if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 1382 // Verify we are shifting out everything but the sign bit. 1383 CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1384 return BinaryOperator::CreateAShr(X, CI); 1385 1386 if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 1387 // Verify we are shifting out everything but the sign bit. 1388 CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 1389 return BinaryOperator::CreateLShr(X, CI); 1390 } 1391 1392 // Try to fold constant sub into select arguments. 1393 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1394 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1395 return R; 1396 1397 // C-(X+C2) --> (C-C2)-X 1398 ConstantInt *C2; 1399 if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2)))) 1400 return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 1401 1402 if (SimplifyDemandedInstructionBits(I)) 1403 return &I; 1404 1405 // Fold (sub 0, (zext bool to B)) --> (sext bool to B) 1406 if (C->isZero() && match(Op1, m_ZExt(m_Value(X)))) 1407 if (X->getType()->isIntegerTy(1)) 1408 return CastInst::CreateSExtOrBitCast(X, Op1->getType()); 1409 1410 // Fold (sub 0, (sext bool to B)) --> (zext bool to B) 1411 if (C->isZero() && match(Op1, m_SExt(m_Value(X)))) 1412 if (X->getType()->isIntegerTy(1)) 1413 return CastInst::CreateZExtOrBitCast(X, Op1->getType()); 1414 } 1415 1416 1417 { Value *Y; 1418 // X-(X+Y) == -Y X-(Y+X) == -Y 1419 if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 1420 match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 1421 return BinaryOperator::CreateNeg(Y); 1422 1423 // (X-Y)-X == -Y 1424 if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 1425 return BinaryOperator::CreateNeg(Y); 1426 } 1427 1428 if (Op1->hasOneUse()) { 1429 Value *X = 0, *Y = 0, *Z = 0; 1430 Constant *C = 0; 1431 ConstantInt *CI = 0; 1432 1433 // (X - (Y - Z)) --> (X + (Z - Y)). 1434 if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 1435 return BinaryOperator::CreateAdd(Op0, 1436 Builder->CreateSub(Z, Y, Op1->getName())); 1437 1438 // (X - (X & Y)) --> (X & ~Y) 1439 // 1440 if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 1441 match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 1442 return BinaryOperator::CreateAnd(Op0, 1443 Builder->CreateNot(Y, Y->getName() + ".not")); 1444 1445 // 0 - (X sdiv C) -> (X sdiv -C) 1446 if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && 1447 match(Op0, m_Zero())) 1448 return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 1449 1450 // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 1451 if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 1452 if (Value *XNeg = dyn_castNegVal(X)) 1453 return BinaryOperator::CreateShl(XNeg, Y); 1454 1455 // X - X*C --> X * (1-C) 1456 if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) { 1457 Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); 1458 return BinaryOperator::CreateMul(Op0, CP1); 1459 } 1460 1461 // X - X<<C --> X * (1-(1<<C)) 1462 if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) { 1463 Constant *One = ConstantInt::get(I.getType(), 1); 1464 C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI)); 1465 return BinaryOperator::CreateMul(Op0, C); 1466 } 1467 1468 // X - A*-B -> X + A*B 1469 // X - -A*B -> X + A*B 1470 Value *A, *B; 1471 if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 1472 match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 1473 return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 1474 1475 // X - A*CI -> X + A*-CI 1476 // X - CI*A -> X + A*-CI 1477 if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) || 1478 match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) { 1479 Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 1480 return BinaryOperator::CreateAdd(Op0, NewMul); 1481 } 1482 } 1483 1484 ConstantInt *C1; 1485 if (Value *X = dyn_castFoldableMul(Op0, C1)) { 1486 if (X == Op1) // X*C - X --> X * (C-1) 1487 return BinaryOperator::CreateMul(Op1, SubOne(C1)); 1488 1489 ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 1490 if (X == dyn_castFoldableMul(Op1, C2)) 1491 return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 1492 } 1493 1494 // Optimize pointer differences into the same array into a size. Consider: 1495 // &A[10] - &A[0]: we should compile this to "10". 1496 if (TD) { 1497 Value *LHSOp, *RHSOp; 1498 if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 1499 match(Op1, m_PtrToInt(m_Value(RHSOp)))) 1500 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1501 return ReplaceInstUsesWith(I, Res); 1502 1503 // trunc(p)-trunc(q) -> trunc(p-q) 1504 if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 1505 match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 1506 if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 1507 return ReplaceInstUsesWith(I, Res); 1508 } 1509 1510 return 0; 1511} 1512 1513Instruction *InstCombiner::visitFSub(BinaryOperator &I) { 1514 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1515 1516 if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), TD)) 1517 return ReplaceInstUsesWith(I, V); 1518 1519 // If this is a 'B = x-(-A)', change to B = x+A... 1520 if (Value *V = dyn_castFNegVal(Op1)) 1521 return BinaryOperator::CreateFAdd(Op0, V); 1522 1523 if (I.hasUnsafeAlgebra()) { 1524 if (Value *V = FAddCombine(Builder).simplify(&I)) 1525 return ReplaceInstUsesWith(I, V); 1526 } 1527 1528 return 0; 1529} 1530