InstCombineAddSub.cpp revision 251662
1//===- InstCombineAddSub.cpp ----------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the visit functions for add, fadd, sub, and fsub. 11// 12//===----------------------------------------------------------------------===// 13 14#include "InstCombine.h" 15#include "llvm/Analysis/InstructionSimplify.h" 16#include "llvm/IR/DataLayout.h" 17#include "llvm/Support/GetElementPtrTypeIterator.h" 18#include "llvm/Support/PatternMatch.h" 19using namespace llvm; 20using namespace PatternMatch; 21 22namespace { 23 24 /// Class representing coefficient of floating-point addend. 25 /// This class needs to be highly efficient, which is especially true for 26 /// the constructor. As of I write this comment, the cost of the default 27 /// constructor is merely 4-byte-store-zero (Assuming compiler is able to 28 /// perform write-merging). 29 /// 30 class FAddendCoef { 31 public: 32 // The constructor has to initialize a APFloat, which is uncessary for 33 // most addends which have coefficient either 1 or -1. So, the constructor 34 // is expensive. In order to avoid the cost of the constructor, we should 35 // reuse some instances whenever possible. The pre-created instances 36 // FAddCombine::Add[0-5] embodies this idea. 37 // 38 FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {} 39 ~FAddendCoef(); 40 41 void set(short C) { 42 assert(!insaneIntVal(C) && "Insane coefficient"); 43 IsFp = false; IntVal = C; 44 } 45 46 void set(const APFloat& C); 47 48 void negate(); 49 50 bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); } 51 Value *getValue(Type *) const; 52 53 // If possible, don't define operator+/operator- etc because these 54 // operators inevitably call FAddendCoef's constructor which is not cheap. 55 void operator=(const FAddendCoef &A); 56 void operator+=(const FAddendCoef &A); 57 void operator-=(const FAddendCoef &A); 58 void operator*=(const FAddendCoef &S); 59 60 bool isOne() const { return isInt() && IntVal == 1; } 61 bool isTwo() const { return isInt() && IntVal == 2; } 62 bool isMinusOne() const { return isInt() && IntVal == -1; } 63 bool isMinusTwo() const { return isInt() && IntVal == -2; } 64 65 private: 66 bool insaneIntVal(int V) { return V > 4 || V < -4; } 67 APFloat *getFpValPtr(void) 68 { return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); } 69 const APFloat *getFpValPtr(void) const 70 { return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); } 71 72 const APFloat &getFpVal(void) const { 73 assert(IsFp && BufHasFpVal && "Incorret state"); 74 return *getFpValPtr(); 75 } 76 77 APFloat &getFpVal(void) { 78 assert(IsFp && BufHasFpVal && "Incorret state"); 79 return *getFpValPtr(); 80 } 81 82 bool isInt() const { return !IsFp; } 83 84 // If the coefficient is represented by an integer, promote it to a 85 // floating point. 86 void convertToFpType(const fltSemantics &Sem); 87 88 // Construct an APFloat from a signed integer. 89 // TODO: We should get rid of this function when APFloat can be constructed 90 // from an *SIGNED* integer. 91 APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val); 92 private: 93 94 bool IsFp; 95 96 // True iff FpValBuf contains an instance of APFloat. 97 bool BufHasFpVal; 98 99 // The integer coefficient of an individual addend is either 1 or -1, 100 // and we try to simplify at most 4 addends from neighboring at most 101 // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt 102 // is overkill of this end. 103 short IntVal; 104 105 AlignedCharArrayUnion<APFloat> FpValBuf; 106 }; 107 108 /// FAddend is used to represent floating-point addend. An addend is 109 /// represented as <C, V>, where the V is a symbolic value, and C is a 110 /// constant coefficient. A constant addend is represented as <C, 0>. 111 /// 112 class FAddend { 113 public: 114 FAddend() { Val = 0; } 115 116 Value *getSymVal (void) const { return Val; } 117 const FAddendCoef &getCoef(void) const { return Coeff; } 118 119 bool isConstant() const { return Val == 0; } 120 bool isZero() const { return Coeff.isZero(); } 121 122 void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; } 123 void set(const APFloat& Coefficient, Value *V) 124 { Coeff.set(Coefficient); Val = V; } 125 void set(const ConstantFP* Coefficient, Value *V) 126 { Coeff.set(Coefficient->getValueAPF()); Val = V; } 127 128 void negate() { Coeff.negate(); } 129 130 /// Drill down the U-D chain one step to find the definition of V, and 131 /// try to break the definition into one or two addends. 132 static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1); 133 134 /// Similar to FAddend::drillDownOneStep() except that the value being 135 /// splitted is the addend itself. 136 unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const; 137 138 void operator+=(const FAddend &T) { 139 assert((Val == T.Val) && "Symbolic-values disagree"); 140 Coeff += T.Coeff; 141 } 142 143 private: 144 void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; } 145 146 // This addend has the value of "Coeff * Val". 147 Value *Val; 148 FAddendCoef Coeff; 149 }; 150 151 /// FAddCombine is the class for optimizing an unsafe fadd/fsub along 152 /// with its neighboring at most two instructions. 153 /// 154 class FAddCombine { 155 public: 156 FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(0) {} 157 Value *simplify(Instruction *FAdd); 158 159 private: 160 typedef SmallVector<const FAddend*, 4> AddendVect; 161 162 Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota); 163 164 Value *performFactorization(Instruction *I); 165 166 /// Convert given addend to a Value 167 Value *createAddendVal(const FAddend &A, bool& NeedNeg); 168 169 /// Return the number of instructions needed to emit the N-ary addition. 170 unsigned calcInstrNumber(const AddendVect& Vect); 171 Value *createFSub(Value *Opnd0, Value *Opnd1); 172 Value *createFAdd(Value *Opnd0, Value *Opnd1); 173 Value *createFMul(Value *Opnd0, Value *Opnd1); 174 Value *createFDiv(Value *Opnd0, Value *Opnd1); 175 Value *createFNeg(Value *V); 176 Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota); 177 void createInstPostProc(Instruction *NewInst); 178 179 InstCombiner::BuilderTy *Builder; 180 Instruction *Instr; 181 182 private: 183 // Debugging stuff are clustered here. 184 #ifndef NDEBUG 185 unsigned CreateInstrNum; 186 void initCreateInstNum() { CreateInstrNum = 0; } 187 void incCreateInstNum() { CreateInstrNum++; } 188 #else 189 void initCreateInstNum() {} 190 void incCreateInstNum() {} 191 #endif 192 }; 193} 194 195//===----------------------------------------------------------------------===// 196// 197// Implementation of 198// {FAddendCoef, FAddend, FAddition, FAddCombine}. 199// 200//===----------------------------------------------------------------------===// 201FAddendCoef::~FAddendCoef() { 202 if (BufHasFpVal) 203 getFpValPtr()->~APFloat(); 204} 205 206void FAddendCoef::set(const APFloat& C) { 207 APFloat *P = getFpValPtr(); 208 209 if (isInt()) { 210 // As the buffer is meanless byte stream, we cannot call 211 // APFloat::operator=(). 212 new(P) APFloat(C); 213 } else 214 *P = C; 215 216 IsFp = BufHasFpVal = true; 217} 218 219void FAddendCoef::convertToFpType(const fltSemantics &Sem) { 220 if (!isInt()) 221 return; 222 223 APFloat *P = getFpValPtr(); 224 if (IntVal > 0) 225 new(P) APFloat(Sem, IntVal); 226 else { 227 new(P) APFloat(Sem, 0 - IntVal); 228 P->changeSign(); 229 } 230 IsFp = BufHasFpVal = true; 231} 232 233APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { 234 if (Val >= 0) 235 return APFloat(Sem, Val); 236 237 APFloat T(Sem, 0 - Val); 238 T.changeSign(); 239 240 return T; 241} 242 243void FAddendCoef::operator=(const FAddendCoef &That) { 244 if (That.isInt()) 245 set(That.IntVal); 246 else 247 set(That.getFpVal()); 248} 249 250void FAddendCoef::operator+=(const FAddendCoef &That) { 251 enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 252 if (isInt() == That.isInt()) { 253 if (isInt()) 254 IntVal += That.IntVal; 255 else 256 getFpVal().add(That.getFpVal(), RndMode); 257 return; 258 } 259 260 if (isInt()) { 261 const APFloat &T = That.getFpVal(); 262 convertToFpType(T.getSemantics()); 263 getFpVal().add(T, RndMode); 264 return; 265 } 266 267 APFloat &T = getFpVal(); 268 T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode); 269} 270 271void FAddendCoef::operator-=(const FAddendCoef &That) { 272 enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven; 273 if (isInt() == That.isInt()) { 274 if (isInt()) 275 IntVal -= That.IntVal; 276 else 277 getFpVal().subtract(That.getFpVal(), RndMode); 278 return; 279 } 280 281 if (isInt()) { 282 const APFloat &T = That.getFpVal(); 283 convertToFpType(T.getSemantics()); 284 getFpVal().subtract(T, RndMode); 285 return; 286 } 287 288 APFloat &T = getFpVal(); 289 T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode); 290} 291 292void FAddendCoef::operator*=(const FAddendCoef &That) { 293 if (That.isOne()) 294 return; 295 296 if (That.isMinusOne()) { 297 negate(); 298 return; 299 } 300 301 if (isInt() && That.isInt()) { 302 int Res = IntVal * (int)That.IntVal; 303 assert(!insaneIntVal(Res) && "Insane int value"); 304 IntVal = Res; 305 return; 306 } 307 308 const fltSemantics &Semantic = 309 isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics(); 310 311 if (isInt()) 312 convertToFpType(Semantic); 313 APFloat &F0 = getFpVal(); 314 315 if (That.isInt()) 316 F0.multiply(createAPFloatFromInt(Semantic, That.IntVal), 317 APFloat::rmNearestTiesToEven); 318 else 319 F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven); 320 321 return; 322} 323 324void FAddendCoef::negate() { 325 if (isInt()) 326 IntVal = 0 - IntVal; 327 else 328 getFpVal().changeSign(); 329} 330 331Value *FAddendCoef::getValue(Type *Ty) const { 332 return isInt() ? 333 ConstantFP::get(Ty, float(IntVal)) : 334 ConstantFP::get(Ty->getContext(), getFpVal()); 335} 336 337// The definition of <Val> Addends 338// ========================================= 339// A + B <1, A>, <1,B> 340// A - B <1, A>, <1,B> 341// 0 - B <-1, B> 342// C * A, <C, A> 343// A + C <1, A> <C, NULL> 344// 0 +/- 0 <0, NULL> (corner case) 345// 346// Legend: A and B are not constant, C is constant 347// 348unsigned FAddend::drillValueDownOneStep 349 (Value *Val, FAddend &Addend0, FAddend &Addend1) { 350 Instruction *I = 0; 351 if (Val == 0 || !(I = dyn_cast<Instruction>(Val))) 352 return 0; 353 354 unsigned Opcode = I->getOpcode(); 355 356 if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) { 357 ConstantFP *C0, *C1; 358 Value *Opnd0 = I->getOperand(0); 359 Value *Opnd1 = I->getOperand(1); 360 if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero()) 361 Opnd0 = 0; 362 363 if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero()) 364 Opnd1 = 0; 365 366 if (Opnd0) { 367 if (!C0) 368 Addend0.set(1, Opnd0); 369 else 370 Addend0.set(C0, 0); 371 } 372 373 if (Opnd1) { 374 FAddend &Addend = Opnd0 ? Addend1 : Addend0; 375 if (!C1) 376 Addend.set(1, Opnd1); 377 else 378 Addend.set(C1, 0); 379 if (Opcode == Instruction::FSub) 380 Addend.negate(); 381 } 382 383 if (Opnd0 || Opnd1) 384 return Opnd0 && Opnd1 ? 2 : 1; 385 386 // Both operands are zero. Weird! 387 Addend0.set(APFloat(C0->getValueAPF().getSemantics()), 0); 388 return 1; 389 } 390 391 if (I->getOpcode() == Instruction::FMul) { 392 Value *V0 = I->getOperand(0); 393 Value *V1 = I->getOperand(1); 394 if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) { 395 Addend0.set(C, V1); 396 return 1; 397 } 398 399 if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) { 400 Addend0.set(C, V0); 401 return 1; 402 } 403 } 404 405 return 0; 406} 407 408// Try to break *this* addend into two addends. e.g. Suppose this addend is 409// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends, 410// i.e. <2.3, X> and <2.3, Y>. 411// 412unsigned FAddend::drillAddendDownOneStep 413 (FAddend &Addend0, FAddend &Addend1) const { 414 if (isConstant()) 415 return 0; 416 417 unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1); 418 if (!BreakNum || Coeff.isOne()) 419 return BreakNum; 420 421 Addend0.Scale(Coeff); 422 423 if (BreakNum == 2) 424 Addend1.Scale(Coeff); 425 426 return BreakNum; 427} 428 429// Try to perform following optimization on the input instruction I. Return the 430// simplified expression if was successful; otherwise, return 0. 431// 432// Instruction "I" is Simplified into 433// ------------------------------------------------------- 434// (x * y) +/- (x * z) x * (y +/- z) 435// (y / x) +/- (z / x) (y +/- z) / x 436// 437Value *FAddCombine::performFactorization(Instruction *I) { 438 assert((I->getOpcode() == Instruction::FAdd || 439 I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 440 441 Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0)); 442 Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1)); 443 444 if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode()) 445 return 0; 446 447 bool isMpy = false; 448 if (I0->getOpcode() == Instruction::FMul) 449 isMpy = true; 450 else if (I0->getOpcode() != Instruction::FDiv) 451 return 0; 452 453 Value *Opnd0_0 = I0->getOperand(0); 454 Value *Opnd0_1 = I0->getOperand(1); 455 Value *Opnd1_0 = I1->getOperand(0); 456 Value *Opnd1_1 = I1->getOperand(1); 457 458 // Input Instr I Factor AddSub0 AddSub1 459 // ---------------------------------------------- 460 // (x*y) +/- (x*z) x y z 461 // (y/x) +/- (z/x) x y z 462 // 463 Value *Factor = 0; 464 Value *AddSub0 = 0, *AddSub1 = 0; 465 466 if (isMpy) { 467 if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1) 468 Factor = Opnd0_0; 469 else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1) 470 Factor = Opnd0_1; 471 472 if (Factor) { 473 AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0; 474 AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0; 475 } 476 } else if (Opnd0_1 == Opnd1_1) { 477 Factor = Opnd0_1; 478 AddSub0 = Opnd0_0; 479 AddSub1 = Opnd1_0; 480 } 481 482 if (!Factor) 483 return 0; 484 485 // Create expression "NewAddSub = AddSub0 +/- AddsSub1" 486 Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ? 487 createFAdd(AddSub0, AddSub1) : 488 createFSub(AddSub0, AddSub1); 489 if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) { 490 const APFloat &F = CFP->getValueAPF(); 491 if (!F.isNormal() || F.isDenormal()) 492 return 0; 493 } 494 495 if (isMpy) 496 return createFMul(Factor, NewAddSub); 497 498 return createFDiv(NewAddSub, Factor); 499} 500 501Value *FAddCombine::simplify(Instruction *I) { 502 assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode"); 503 504 // Currently we are not able to handle vector type. 505 if (I->getType()->isVectorTy()) 506 return 0; 507 508 assert((I->getOpcode() == Instruction::FAdd || 509 I->getOpcode() == Instruction::FSub) && "Expect add/sub"); 510 511 // Save the instruction before calling other member-functions. 512 Instr = I; 513 514 FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1; 515 516 unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1); 517 518 // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1. 519 unsigned Opnd0_ExpNum = 0; 520 unsigned Opnd1_ExpNum = 0; 521 522 if (!Opnd0.isConstant()) 523 Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1); 524 525 // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1. 526 if (OpndNum == 2 && !Opnd1.isConstant()) 527 Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1); 528 529 // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1 530 if (Opnd0_ExpNum && Opnd1_ExpNum) { 531 AddendVect AllOpnds; 532 AllOpnds.push_back(&Opnd0_0); 533 AllOpnds.push_back(&Opnd1_0); 534 if (Opnd0_ExpNum == 2) 535 AllOpnds.push_back(&Opnd0_1); 536 if (Opnd1_ExpNum == 2) 537 AllOpnds.push_back(&Opnd1_1); 538 539 // Compute instruction quota. We should save at least one instruction. 540 unsigned InstQuota = 0; 541 542 Value *V0 = I->getOperand(0); 543 Value *V1 = I->getOperand(1); 544 InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) && 545 (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1; 546 547 if (Value *R = simplifyFAdd(AllOpnds, InstQuota)) 548 return R; 549 } 550 551 if (OpndNum != 2) { 552 // The input instruction is : "I=0.0 +/- V". If the "V" were able to be 553 // splitted into two addends, say "V = X - Y", the instruction would have 554 // been optimized into "I = Y - X" in the previous steps. 555 // 556 const FAddendCoef &CE = Opnd0.getCoef(); 557 return CE.isOne() ? Opnd0.getSymVal() : 0; 558 } 559 560 // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1] 561 if (Opnd1_ExpNum) { 562 AddendVect AllOpnds; 563 AllOpnds.push_back(&Opnd0); 564 AllOpnds.push_back(&Opnd1_0); 565 if (Opnd1_ExpNum == 2) 566 AllOpnds.push_back(&Opnd1_1); 567 568 if (Value *R = simplifyFAdd(AllOpnds, 1)) 569 return R; 570 } 571 572 // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1] 573 if (Opnd0_ExpNum) { 574 AddendVect AllOpnds; 575 AllOpnds.push_back(&Opnd1); 576 AllOpnds.push_back(&Opnd0_0); 577 if (Opnd0_ExpNum == 2) 578 AllOpnds.push_back(&Opnd0_1); 579 580 if (Value *R = simplifyFAdd(AllOpnds, 1)) 581 return R; 582 } 583 584 // step 6: Try factorization as the last resort, 585 return performFactorization(I); 586} 587 588Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { 589 590 unsigned AddendNum = Addends.size(); 591 assert(AddendNum <= 4 && "Too many addends"); 592 593 // For saving intermediate results; 594 unsigned NextTmpIdx = 0; 595 FAddend TmpResult[3]; 596 597 // Points to the constant addend of the resulting simplified expression. 598 // If the resulting expr has constant-addend, this constant-addend is 599 // desirable to reside at the top of the resulting expression tree. Placing 600 // constant close to supper-expr(s) will potentially reveal some optimization 601 // opportunities in super-expr(s). 602 // 603 const FAddend *ConstAdd = 0; 604 605 // Simplified addends are placed <SimpVect>. 606 AddendVect SimpVect; 607 608 // The outer loop works on one symbolic-value at a time. Suppose the input 609 // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ... 610 // The symbolic-values will be processed in this order: x, y, z. 611 // 612 for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) { 613 614 const FAddend *ThisAddend = Addends[SymIdx]; 615 if (!ThisAddend) { 616 // This addend was processed before. 617 continue; 618 } 619 620 Value *Val = ThisAddend->getSymVal(); 621 unsigned StartIdx = SimpVect.size(); 622 SimpVect.push_back(ThisAddend); 623 624 // The inner loop collects addends sharing same symbolic-value, and these 625 // addends will be later on folded into a single addend. Following above 626 // example, if the symbolic value "y" is being processed, the inner loop 627 // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will 628 // be later on folded into "<b1+b2, y>". 629 // 630 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