brintos / llvm-project-archived public Read only

1//===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the visit functions for add, fadd, sub, and fsub.10//11//===----------------------------------------------------------------------===//12 13#include "InstCombineInternal.h"14#include "llvm/ADT/APFloat.h"15#include "llvm/ADT/APInt.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/SmallVector.h"18#include "llvm/Analysis/InstructionSimplify.h"19#include "llvm/Analysis/ValueTracking.h"20#include "llvm/IR/Constant.h"21#include "llvm/IR/Constants.h"22#include "llvm/IR/InstrTypes.h"23#include "llvm/IR/Instruction.h"24#include "llvm/IR/Instructions.h"25#include "llvm/IR/Operator.h"26#include "llvm/IR/PatternMatch.h"27#include "llvm/IR/Type.h"28#include "llvm/IR/Value.h"29#include "llvm/Support/AlignOf.h"30#include "llvm/Support/Casting.h"31#include "llvm/Support/KnownBits.h"32#include "llvm/Transforms/InstCombine/InstCombiner.h"33#include <cassert>34#include <utility>35 36using namespace llvm;37using namespace PatternMatch;38 39#define DEBUG_TYPE "instcombine"40 41namespace {42 43  /// Class representing coefficient of floating-point addend.44  /// This class needs to be highly efficient, which is especially true for45  /// the constructor. As of I write this comment, the cost of the default46  /// constructor is merely 4-byte-store-zero (Assuming compiler is able to47  /// perform write-merging).48  ///49  class FAddendCoef {50  public:51    // The constructor has to initialize a APFloat, which is unnecessary for52    // most addends which have coefficient either 1 or -1. So, the constructor53    // is expensive. In order to avoid the cost of the constructor, we should54    // reuse some instances whenever possible. The pre-created instances55    // FAddCombine::Add[0-5] embodies this idea.56    FAddendCoef() = default;57    ~FAddendCoef();58 59    // If possible, don't define operator+/operator- etc because these60    // operators inevitably call FAddendCoef's constructor which is not cheap.61    void operator=(const FAddendCoef &A);62    void operator+=(const FAddendCoef &A);63    void operator*=(const FAddendCoef &S);64 65    void set(short C) {66      assert(!insaneIntVal(C) && "Insane coefficient");67      IsFp = false; IntVal = C;68    }69 70    void set(const APFloat& C);71 72    void negate();73 74    bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }75    Value *getValue(Type *) const;76 77    bool isOne() const { return isInt() && IntVal == 1; }78    bool isTwo() const { return isInt() && IntVal == 2; }79    bool isMinusOne() const { return isInt() && IntVal == -1; }80    bool isMinusTwo() const { return isInt() && IntVal == -2; }81 82  private:83    bool insaneIntVal(int V) { return V > 4 || V < -4; }84 85    APFloat *getFpValPtr() { return reinterpret_cast<APFloat *>(&FpValBuf); }86 87    const APFloat *getFpValPtr() const {88      return reinterpret_cast<const APFloat *>(&FpValBuf);89    }90 91    const APFloat &getFpVal() const {92      assert(IsFp && BufHasFpVal && "Incorret state");93      return *getFpValPtr();94    }95 96    APFloat &getFpVal() {97      assert(IsFp && BufHasFpVal && "Incorret state");98      return *getFpValPtr();99    }100 101    bool isInt() const { return !IsFp; }102 103    // If the coefficient is represented by an integer, promote it to a104    // floating point.105    void convertToFpType(const fltSemantics &Sem);106 107    // Construct an APFloat from a signed integer.108    // TODO: We should get rid of this function when APFloat can be constructed109    //       from an *SIGNED* integer.110    APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);111 112    bool IsFp = false;113 114    // True iff FpValBuf contains an instance of APFloat.115    bool BufHasFpVal = false;116 117    // The integer coefficient of an individual addend is either 1 or -1,118    // and we try to simplify at most 4 addends from neighboring at most119    // two instructions. So the range of <IntVal> falls in [-4, 4]. APInt120    // is overkill of this end.121    short IntVal = 0;122 123    AlignedCharArrayUnion<APFloat> FpValBuf;124  };125 126  /// FAddend is used to represent floating-point addend. An addend is127  /// represented as <C, V>, where the V is a symbolic value, and C is a128  /// constant coefficient. A constant addend is represented as <C, 0>.129  class FAddend {130  public:131    FAddend() = default;132 133    void operator+=(const FAddend &T) {134      assert((Val == T.Val) && "Symbolic-values disagree");135      Coeff += T.Coeff;136    }137 138    Value *getSymVal() const { return Val; }139    const FAddendCoef &getCoef() const { return Coeff; }140 141    bool isConstant() const { return Val == nullptr; }142    bool isZero() const { return Coeff.isZero(); }143 144    void set(short Coefficient, Value *V) {145      Coeff.set(Coefficient);146      Val = V;147    }148    void set(const APFloat &Coefficient, Value *V) {149      Coeff.set(Coefficient);150      Val = V;151    }152    void set(const ConstantFP *Coefficient, Value *V) {153      Coeff.set(Coefficient->getValueAPF());154      Val = V;155    }156 157    void negate() { Coeff.negate(); }158 159    /// Drill down the U-D chain one step to find the definition of V, and160    /// try to break the definition into one or two addends.161    static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);162 163    /// Similar to FAddend::drillDownOneStep() except that the value being164    /// splitted is the addend itself.165    unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;166 167  private:168    void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }169 170    // This addend has the value of "Coeff * Val".171    Value *Val = nullptr;172    FAddendCoef Coeff;173  };174 175  /// FAddCombine is the class for optimizing an unsafe fadd/fsub along176  /// with its neighboring at most two instructions.177  ///178  class FAddCombine {179  public:180    FAddCombine(InstCombiner::BuilderTy &B) : Builder(B) {}181 182    Value *simplify(Instruction *FAdd);183 184  private:185    using AddendVect = SmallVector<const FAddend *, 4>;186 187    Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);188 189    /// Convert given addend to a Value190    Value *createAddendVal(const FAddend &A, bool& NeedNeg);191 192    /// Return the number of instructions needed to emit the N-ary addition.193    unsigned calcInstrNumber(const AddendVect& Vect);194 195    Value *createFSub(Value *Opnd0, Value *Opnd1);196    Value *createFAdd(Value *Opnd0, Value *Opnd1);197    Value *createFMul(Value *Opnd0, Value *Opnd1);198    Value *createFNeg(Value *V);199    Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);200    void createInstPostProc(Instruction *NewInst, bool NoNumber = false);201 202     // Debugging stuff are clustered here.203    #ifndef NDEBUG204      unsigned CreateInstrNum;205      void initCreateInstNum() { CreateInstrNum = 0; }206      void incCreateInstNum() { CreateInstrNum++; }207    #else208      void initCreateInstNum() {}209      void incCreateInstNum() {}210    #endif211 212    InstCombiner::BuilderTy &Builder;213    Instruction *Instr = nullptr;214  };215 216} // end anonymous namespace217 218//===----------------------------------------------------------------------===//219//220// Implementation of221//    {FAddendCoef, FAddend, FAddition, FAddCombine}.222//223//===----------------------------------------------------------------------===//224FAddendCoef::~FAddendCoef() {225  if (BufHasFpVal)226    getFpValPtr()->~APFloat();227}228 229void FAddendCoef::set(const APFloat& C) {230  APFloat *P = getFpValPtr();231 232  if (isInt()) {233    // As the buffer is meanless byte stream, we cannot call234    // APFloat::operator=().235    new(P) APFloat(C);236  } else237    *P = C;238 239  IsFp = BufHasFpVal = true;240}241 242void FAddendCoef::convertToFpType(const fltSemantics &Sem) {243  if (!isInt())244    return;245 246  APFloat *P = getFpValPtr();247  if (IntVal > 0)248    new(P) APFloat(Sem, IntVal);249  else {250    new(P) APFloat(Sem, 0 - IntVal);251    P->changeSign();252  }253  IsFp = BufHasFpVal = true;254}255 256APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {257  if (Val >= 0)258    return APFloat(Sem, Val);259 260  APFloat T(Sem, 0 - Val);261  T.changeSign();262 263  return T;264}265 266void FAddendCoef::operator=(const FAddendCoef &That) {267  if (That.isInt())268    set(That.IntVal);269  else270    set(That.getFpVal());271}272 273void FAddendCoef::operator+=(const FAddendCoef &That) {274  RoundingMode RndMode = RoundingMode::NearestTiesToEven;275  if (isInt() == That.isInt()) {276    if (isInt())277      IntVal += That.IntVal;278    else279      getFpVal().add(That.getFpVal(), RndMode);280    return;281  }282 283  if (isInt()) {284    const APFloat &T = That.getFpVal();285    convertToFpType(T.getSemantics());286    getFpVal().add(T, RndMode);287    return;288  }289 290  APFloat &T = getFpVal();291  T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);292}293 294void FAddendCoef::operator*=(const FAddendCoef &That) {295  if (That.isOne())296    return;297 298  if (That.isMinusOne()) {299    negate();300    return;301  }302 303  if (isInt() && That.isInt()) {304    int Res = IntVal * (int)That.IntVal;305    assert(!insaneIntVal(Res) && "Insane int value");306    IntVal = Res;307    return;308  }309 310  const fltSemantics &Semantic =311    isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();312 313  if (isInt())314    convertToFpType(Semantic);315  APFloat &F0 = getFpVal();316 317  if (That.isInt())318    F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),319                APFloat::rmNearestTiesToEven);320  else321    F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);322}323 324void FAddendCoef::negate() {325  if (isInt())326    IntVal = 0 - IntVal;327  else328    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>     Addends338// =========================================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 constant347unsigned FAddend::drillValueDownOneStep348  (Value *Val, FAddend &Addend0, FAddend &Addend1) {349  Instruction *I = nullptr;350  if (!Val || !(I = dyn_cast<Instruction>(Val)))351    return 0;352 353  unsigned Opcode = I->getOpcode();354 355  if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {356    ConstantFP *C0, *C1;357    Value *Opnd0 = I->getOperand(0);358    Value *Opnd1 = I->getOperand(1);359    if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())360      Opnd0 = nullptr;361 362    if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())363      Opnd1 = nullptr;364 365    if (Opnd0) {366      if (!C0)367        Addend0.set(1, Opnd0);368      else369        Addend0.set(C0, nullptr);370    }371 372    if (Opnd1) {373      FAddend &Addend = Opnd0 ? Addend1 : Addend0;374      if (!C1)375        Addend.set(1, Opnd1);376      else377        Addend.set(C1, nullptr);378      if (Opcode == Instruction::FSub)379        Addend.negate();380    }381 382    if (Opnd0 || Opnd1)383      return Opnd0 && Opnd1 ? 2 : 1;384 385    // Both operands are zero. Weird!386    Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr);387    return 1;388  }389 390  if (I->getOpcode() == Instruction::FMul) {391    Value *V0 = I->getOperand(0);392    Value *V1 = I->getOperand(1);393    if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {394      Addend0.set(C, V1);395      return 1;396    }397 398    if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {399      Addend0.set(C, V0);400      return 1;401    }402  }403 404  return 0;405}406 407// Try to break *this* addend into two addends. e.g. Suppose this addend is408// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,409// i.e. <2.3, X> and <2.3, Y>.410unsigned FAddend::drillAddendDownOneStep411  (FAddend &Addend0, FAddend &Addend1) const {412  if (isConstant())413    return 0;414 415  unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);416  if (!BreakNum || Coeff.isOne())417    return BreakNum;418 419  Addend0.Scale(Coeff);420 421  if (BreakNum == 2)422    Addend1.Scale(Coeff);423 424  return BreakNum;425}426 427Value *FAddCombine::simplify(Instruction *I) {428  assert(I->hasAllowReassoc() && I->hasNoSignedZeros() &&429         "Expected 'reassoc'+'nsz' instruction");430 431  // Currently we are not able to handle vector type.432  if (I->getType()->isVectorTy())433    return nullptr;434 435  assert((I->getOpcode() == Instruction::FAdd ||436          I->getOpcode() == Instruction::FSub) && "Expect add/sub");437 438  // Save the instruction before calling other member-functions.439  Instr = I;440 441  FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;442 443  unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);444 445  // Step 1: Expand the 1st addend into Opnd0_0 and Opnd0_1.446  unsigned Opnd0_ExpNum = 0;447  unsigned Opnd1_ExpNum = 0;448 449  if (!Opnd0.isConstant())450    Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);451 452  // Step 2: Expand the 2nd addend into Opnd1_0 and Opnd1_1.453  if (OpndNum == 2 && !Opnd1.isConstant())454    Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);455 456  // Step 3: Try to optimize Opnd0_0 + Opnd0_1 + Opnd1_0 + Opnd1_1457  if (Opnd0_ExpNum && Opnd1_ExpNum) {458    AddendVect AllOpnds;459    AllOpnds.push_back(&Opnd0_0);460    AllOpnds.push_back(&Opnd1_0);461    if (Opnd0_ExpNum == 2)462      AllOpnds.push_back(&Opnd0_1);463    if (Opnd1_ExpNum == 2)464      AllOpnds.push_back(&Opnd1_1);465 466    // Compute instruction quota. We should save at least one instruction.467    unsigned InstQuota = 0;468 469    Value *V0 = I->getOperand(0);470    Value *V1 = I->getOperand(1);471    InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&472                 (!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;473 474    if (Value *R = simplifyFAdd(AllOpnds, InstQuota))475      return R;476  }477 478  if (OpndNum != 2) {479    // The input instruction is : "I=0.0 +/- V". If the "V" were able to be480    // splitted into two addends, say "V = X - Y", the instruction would have481    // been optimized into "I = Y - X" in the previous steps.482    //483    const FAddendCoef &CE = Opnd0.getCoef();484    return CE.isOne() ? Opnd0.getSymVal() : nullptr;485  }486 487  // step 4: Try to optimize Opnd0 + Opnd1_0 [+ Opnd1_1]488  if (Opnd1_ExpNum) {489    AddendVect AllOpnds;490    AllOpnds.push_back(&Opnd0);491    AllOpnds.push_back(&Opnd1_0);492    if (Opnd1_ExpNum == 2)493      AllOpnds.push_back(&Opnd1_1);494 495    if (Value *R = simplifyFAdd(AllOpnds, 1))496      return R;497  }498 499  // step 5: Try to optimize Opnd1 + Opnd0_0 [+ Opnd0_1]500  if (Opnd0_ExpNum) {501    AddendVect AllOpnds;502    AllOpnds.push_back(&Opnd1);503    AllOpnds.push_back(&Opnd0_0);504    if (Opnd0_ExpNum == 2)505      AllOpnds.push_back(&Opnd0_1);506 507    if (Value *R = simplifyFAdd(AllOpnds, 1))508      return R;509  }510 511  return nullptr;512}513 514Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {515  unsigned AddendNum = Addends.size();516  assert(AddendNum <= 4 && "Too many addends");517 518  // For saving intermediate results;519  unsigned NextTmpIdx = 0;520  FAddend TmpResult[3];521 522  // Simplified addends are placed <SimpVect>.523  AddendVect SimpVect;524 525  // The outer loop works on one symbolic-value at a time. Suppose the input526  // addends are : <a1, x>, <b1, y>, <a2, x>, <c1, z>, <b2, y>, ...527  // The symbolic-values will be processed in this order: x, y, z.528  for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {529 530    const FAddend *ThisAddend = Addends[SymIdx];531    if (!ThisAddend) {532      // This addend was processed before.533      continue;534    }535 536    Value *Val = ThisAddend->getSymVal();537 538    // If the resulting expr has constant-addend, this constant-addend is539    // desirable to reside at the top of the resulting expression tree. Placing540    // constant close to super-expr(s) will potentially reveal some541    // optimization opportunities in super-expr(s). Here we do not implement542    // this logic intentionally and rely on SimplifyAssociativeOrCommutative543    // call later.544 545    unsigned StartIdx = SimpVect.size();546    SimpVect.push_back(ThisAddend);547 548    // The inner loop collects addends sharing same symbolic-value, and these549    // addends will be later on folded into a single addend. Following above550    // example, if the symbolic value "y" is being processed, the inner loop551    // will collect two addends "<b1,y>" and "<b2,Y>". These two addends will552    // be later on folded into "<b1+b2, y>".553    for (unsigned SameSymIdx = SymIdx + 1;554         SameSymIdx < AddendNum; SameSymIdx++) {555      const FAddend *T = Addends[SameSymIdx];556      if (T && T->getSymVal() == Val) {557        // Set null such that next iteration of the outer loop will not process558        // this addend again.559        Addends[SameSymIdx] = nullptr;560        SimpVect.push_back(T);561      }562    }563 564    // If multiple addends share same symbolic value, fold them together.565    if (StartIdx + 1 != SimpVect.size()) {566      FAddend &R = TmpResult[NextTmpIdx ++];567      R = *SimpVect[StartIdx];568      for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)569        R += *SimpVect[Idx];570 571      // Pop all addends being folded and push the resulting folded addend.572      SimpVect.resize(StartIdx);573      if (!R.isZero()) {574        SimpVect.push_back(&R);575      }576    }577  }578 579  assert((NextTmpIdx <= std::size(TmpResult) + 1) && "out-of-bound access");580 581  Value *Result;582  if (!SimpVect.empty())583    Result = createNaryFAdd(SimpVect, InstrQuota);584  else {585    // The addition is folded to 0.0.586    Result = ConstantFP::get(Instr->getType(), 0.0);587  }588 589  return Result;590}591 592Value *FAddCombine::createNaryFAdd593  (const AddendVect &Opnds, unsigned InstrQuota) {594  assert(!Opnds.empty() && "Expect at least one addend");595 596  // Step 1: Check if the # of instructions needed exceeds the quota.597 598  unsigned InstrNeeded = calcInstrNumber(Opnds);599  if (InstrNeeded > InstrQuota)600    return nullptr;601 602  initCreateInstNum();603 604  // step 2: Emit the N-ary addition.605  // Note that at most three instructions are involved in Fadd-InstCombine: the606  // addition in question, and at most two neighboring instructions.607  // The resulting optimized addition should have at least one less instruction608  // than the original addition expression tree. This implies that the resulting609  // N-ary addition has at most two instructions, and we don't need to worry610  // about tree-height when constructing the N-ary addition.611 612  Value *LastVal = nullptr;613  bool LastValNeedNeg = false;614 615  // Iterate the addends, creating fadd/fsub using adjacent two addends.616  for (const FAddend *Opnd : Opnds) {617    bool NeedNeg;618    Value *V = createAddendVal(*Opnd, NeedNeg);619    if (!LastVal) {620      LastVal = V;621      LastValNeedNeg = NeedNeg;622      continue;623    }624 625    if (LastValNeedNeg == NeedNeg) {626      LastVal = createFAdd(LastVal, V);627      continue;628    }629 630    if (LastValNeedNeg)631      LastVal = createFSub(V, LastVal);632    else633      LastVal = createFSub(LastVal, V);634 635    LastValNeedNeg = false;636  }637 638  if (LastValNeedNeg) {639    LastVal = createFNeg(LastVal);640  }641 642#ifndef NDEBUG643  assert(CreateInstrNum == InstrNeeded &&644         "Inconsistent in instruction numbers");645#endif646 647  return LastVal;648}649 650Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) {651  Value *V = Builder.CreateFSub(Opnd0, Opnd1);652  if (Instruction *I = dyn_cast<Instruction>(V))653    createInstPostProc(I);654  return V;655}656 657Value *FAddCombine::createFNeg(Value *V) {658  Value *NewV = Builder.CreateFNeg(V);659  if (Instruction *I = dyn_cast<Instruction>(NewV))660    createInstPostProc(I, true); // fneg's don't receive instruction numbers.661  return NewV;662}663 664Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) {665  Value *V = Builder.CreateFAdd(Opnd0, Opnd1);666  if (Instruction *I = dyn_cast<Instruction>(V))667    createInstPostProc(I);668  return V;669}670 671Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {672  Value *V = Builder.CreateFMul(Opnd0, Opnd1);673  if (Instruction *I = dyn_cast<Instruction>(V))674    createInstPostProc(I);675  return V;676}677 678void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) {679  NewInstr->setDebugLoc(Instr->getDebugLoc());680 681  // Keep track of the number of instruction created.682  if (!NoNumber)683    incCreateInstNum();684 685  // Propagate fast-math flags686  NewInstr->setFastMathFlags(Instr->getFastMathFlags());687}688 689// Return the number of instruction needed to emit the N-ary addition.690// NOTE: Keep this function in sync with createAddendVal().691unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {692  unsigned OpndNum = Opnds.size();693  unsigned InstrNeeded = OpndNum - 1;694 695  // Adjust the number of instructions needed to emit the N-ary add.696  for (const FAddend *Opnd : Opnds) {697    if (Opnd->isConstant())698      continue;699 700    // The constant check above is really for a few special constant701    // coefficients.702    if (isa<UndefValue>(Opnd->getSymVal()))703      continue;704 705    const FAddendCoef &CE = Opnd->getCoef();706    // Let the addend be "c * x". If "c == +/-1", the value of the addend707    // is immediately available; otherwise, it needs exactly one instruction708    // to evaluate the value.709    if (!CE.isMinusOne() && !CE.isOne())710      InstrNeeded++;711  }712  return InstrNeeded;713}714 715// Input Addend        Value           NeedNeg(output)716// ================================================================717// Constant C          C               false718// <+/-1, V>           V               coefficient is -1719// <2/-2, V>          "fadd V, V"      coefficient is -2720// <C, V>             "fmul V, C"      false721//722// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.723Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {724  const FAddendCoef &Coeff = Opnd.getCoef();725 726  if (Opnd.isConstant()) {727    NeedNeg = false;728    return Coeff.getValue(Instr->getType());729  }730 731  Value *OpndVal = Opnd.getSymVal();732 733  if (Coeff.isMinusOne() || Coeff.isOne()) {734    NeedNeg = Coeff.isMinusOne();735    return OpndVal;736  }737 738  if (Coeff.isTwo() || Coeff.isMinusTwo()) {739    NeedNeg = Coeff.isMinusTwo();740    return createFAdd(OpndVal, OpndVal);741  }742 743  NeedNeg = false;744  return createFMul(OpndVal, Coeff.getValue(Instr->getType()));745}746 747// Checks if any operand is negative and we can convert add to sub.748// This function checks for following negative patterns749//   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))750//   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))751//   XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even752static Value *checkForNegativeOperand(BinaryOperator &I,753                                      InstCombiner::BuilderTy &Builder) {754  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);755 756  // This function creates 2 instructions to replace ADD, we need at least one757  // of LHS or RHS to have one use to ensure benefit in transform.758  if (!LHS->hasOneUse() && !RHS->hasOneUse())759    return nullptr;760 761  Value *X = nullptr, *Y = nullptr, *Z = nullptr;762  const APInt *C1 = nullptr, *C2 = nullptr;763 764  // if ONE is on other side, swap765  if (match(RHS, m_Add(m_Value(X), m_One())))766    std::swap(LHS, RHS);767 768  if (match(LHS, m_Add(m_Value(X), m_One()))) {769    // if XOR on other side, swap770    if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))771      std::swap(X, RHS);772 773    if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {774      // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1))775      // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1))776      if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {777        Value *NewAnd = Builder.CreateAnd(Z, *C1);778        return Builder.CreateSub(RHS, NewAnd, "sub");779      } else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {780        // X = XOR(Y, C1), Y = AND(Z, C2), C2 == C1 ==> X == NOT(OR(Z, ~C1))781        // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, OR(Z, ~C1))782        Value *NewOr = Builder.CreateOr(Z, ~(*C1));783        return Builder.CreateSub(RHS, NewOr, "sub");784      }785    }786  }787 788  // Restore LHS and RHS789  LHS = I.getOperand(0);790  RHS = I.getOperand(1);791 792  // if XOR is on other side, swap793  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))794    std::swap(LHS, RHS);795 796  // C2 is ODD797  // LHS = XOR(Y, C1), Y = AND(Z, C2), C1 == (C2 + 1) => LHS == NEG(OR(Z, ~C2))798  // ADD(LHS, RHS) == SUB(RHS, OR(Z, ~C2))799  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))800    if (C1->countr_zero() == 0)801      if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {802        Value *NewOr = Builder.CreateOr(Z, ~(*C2));803        return Builder.CreateSub(RHS, NewOr, "sub");804      }805  return nullptr;806}807 808/// Wrapping flags may allow combining constants separated by an extend.809static Instruction *foldNoWrapAdd(BinaryOperator &Add,810                                  InstCombiner::BuilderTy &Builder) {811  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);812  Type *Ty = Add.getType();813  Constant *Op1C;814  if (!match(Op1, m_Constant(Op1C)))815    return nullptr;816 817  // Try this match first because it results in an add in the narrow type.818  // (zext (X +nuw C2)) + C1 --> zext (X + (C2 + trunc(C1)))819  Value *X;820  const APInt *C1, *C2;821  if (match(Op1, m_APInt(C1)) &&822      match(Op0, m_ZExt(m_NUWAddLike(m_Value(X), m_APInt(C2)))) &&823      C1->isNegative() && C1->sge(-C2->sext(C1->getBitWidth()))) {824    APInt NewC = *C2 + C1->trunc(C2->getBitWidth());825    // If the smaller add will fold to zero, we don't need to check one use.826    if (NewC.isZero())827      return new ZExtInst(X, Ty);828    // Otherwise only do this if the existing zero extend will be removed.829    if (Op0->hasOneUse())830      return new ZExtInst(831          Builder.CreateNUWAdd(X, ConstantInt::get(X->getType(), NewC)), Ty);832  }833 834  // More general combining of constants in the wide type.835  // (sext (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)836  // or (zext nneg (X +nsw NarrowC)) + C --> (sext X) + (sext(NarrowC) + C)837  Constant *NarrowC;838  if (match(Op0, m_OneUse(m_SExtLike(839                     m_NSWAddLike(m_Value(X), m_Constant(NarrowC)))))) {840    Value *WideC = Builder.CreateSExt(NarrowC, Ty);841    Value *NewC = Builder.CreateAdd(WideC, Op1C);842    Value *WideX = Builder.CreateSExt(X, Ty);843    return BinaryOperator::CreateAdd(WideX, NewC);844  }845  // (zext (X +nuw NarrowC)) + C --> (zext X) + (zext(NarrowC) + C)846  if (match(Op0,847            m_OneUse(m_ZExt(m_NUWAddLike(m_Value(X), m_Constant(NarrowC)))))) {848    Value *WideC = Builder.CreateZExt(NarrowC, Ty);849    Value *NewC = Builder.CreateAdd(WideC, Op1C);850    Value *WideX = Builder.CreateZExt(X, Ty);851    return BinaryOperator::CreateAdd(WideX, NewC);852  }853  return nullptr;854}855 856Instruction *InstCombinerImpl::foldAddWithConstant(BinaryOperator &Add) {857  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);858  Type *Ty = Add.getType();859  Constant *Op1C;860  if (!match(Op1, m_ImmConstant(Op1C)))861    return nullptr;862 863  if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))864    return NV;865 866  Value *X;867  Constant *Op00C;868 869  // add (sub C1, X), C2 --> sub (add C1, C2), X870  if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X))))871    return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X);872 873  Value *Y;874 875  // add (sub X, Y), -1 --> add (not Y), X876  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) &&877      match(Op1, m_AllOnes()))878    return BinaryOperator::CreateAdd(Builder.CreateNot(Y), X);879 880  // zext(bool) + C -> bool ? C + 1 : C881  if (match(Op0, m_ZExt(m_Value(X))) &&882      X->getType()->getScalarSizeInBits() == 1)883    return createSelectInstWithUnknownProfile(X, InstCombiner::AddOne(Op1C),884                                              Op1);885  // sext(bool) + C -> bool ? C - 1 : C886  if (match(Op0, m_SExt(m_Value(X))) &&887      X->getType()->getScalarSizeInBits() == 1)888    return createSelectInstWithUnknownProfile(X, InstCombiner::SubOne(Op1C),889                                              Op1);890 891  // ~X + C --> (C-1) - X892  if (match(Op0, m_Not(m_Value(X)))) {893    // ~X + C has NSW and (C-1) won't oveflow => (C-1)-X can have NSW894    auto *COne = ConstantInt::get(Op1C->getType(), 1);895    bool WillNotSOV = willNotOverflowSignedSub(Op1C, COne, Add);896    BinaryOperator *Res =897        BinaryOperator::CreateSub(ConstantExpr::getSub(Op1C, COne), X);898    Res->setHasNoSignedWrap(Add.hasNoSignedWrap() && WillNotSOV);899    return Res;900  }901 902  // (iN X s>> (N - 1)) + 1 --> zext (X > -1)903  const APInt *C;904  unsigned BitWidth = Ty->getScalarSizeInBits();905  if (match(Op0, m_OneUse(m_AShr(m_Value(X),906                                 m_SpecificIntAllowPoison(BitWidth - 1)))) &&907      match(Op1, m_One()))908    return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);909 910  if (!match(Op1, m_APInt(C)))911    return nullptr;912 913  // (X | Op01C) + Op1C --> X + (Op01C + Op1C) iff the `or` is actually an `add`914  Constant *Op01C;915  if (match(Op0, m_DisjointOr(m_Value(X), m_ImmConstant(Op01C)))) {916    BinaryOperator *NewAdd =917        BinaryOperator::CreateAdd(X, ConstantExpr::getAdd(Op01C, Op1C));918    NewAdd->setHasNoSignedWrap(Add.hasNoSignedWrap() &&919                               willNotOverflowSignedAdd(Op01C, Op1C, Add));920    NewAdd->setHasNoUnsignedWrap(Add.hasNoUnsignedWrap());921    return NewAdd;922  }923 924  // (X | C2) + C --> (X | C2) ^ C2 iff (C2 == -C)925  const APInt *C2;926  if (match(Op0, m_Or(m_Value(), m_APInt(C2))) && *C2 == -*C)927    return BinaryOperator::CreateXor(Op0, ConstantInt::get(Add.getType(), *C2));928 929  if (C->isSignMask()) {930    // If wrapping is not allowed, then the addition must set the sign bit:931    // X + (signmask) --> X | signmask932    if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())933      return BinaryOperator::CreateOr(Op0, Op1);934 935    // If wrapping is allowed, then the addition flips the sign bit of LHS:936    // X + (signmask) --> X ^ signmask937    return BinaryOperator::CreateXor(Op0, Op1);938  }939 940  // Is this add the last step in a convoluted sext?941  // add(zext(xor i16 X, -32768), -32768) --> sext X942  if (match(Op0, m_ZExt(m_Xor(m_Value(X), m_APInt(C2)))) &&943      C2->isMinSignedValue() && C2->sext(Ty->getScalarSizeInBits()) == *C)944    return CastInst::Create(Instruction::SExt, X, Ty);945 946  if (match(Op0, m_Xor(m_Value(X), m_APInt(C2)))) {947    // (X ^ signmask) + C --> (X + (signmask ^ C))948    if (C2->isSignMask())949      return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C2 ^ *C));950 951    // If X has no high-bits set above an xor mask:952    // add (xor X, LowMaskC), C --> sub (LowMaskC + C), X953    if (C2->isMask()) {954      KnownBits LHSKnown = computeKnownBits(X, &Add);955      if ((*C2 | LHSKnown.Zero).isAllOnes())956        return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C2 + *C), X);957    }958 959    // Look for a math+logic pattern that corresponds to sext-in-register of a960    // value with cleared high bits. Convert that into a pair of shifts:961    // add (xor X, 0x80), 0xF..F80 --> (X << ShAmtC) >>s ShAmtC962    // add (xor X, 0xF..F80), 0x80 --> (X << ShAmtC) >>s ShAmtC963    if (Op0->hasOneUse() && *C2 == -(*C)) {964      unsigned BitWidth = Ty->getScalarSizeInBits();965      unsigned ShAmt = 0;966      if (C->isPowerOf2())967        ShAmt = BitWidth - C->logBase2() - 1;968      else if (C2->isPowerOf2())969        ShAmt = BitWidth - C2->logBase2() - 1;970      if (ShAmt &&971          MaskedValueIsZero(X, APInt::getHighBitsSet(BitWidth, ShAmt), &Add)) {972        Constant *ShAmtC = ConstantInt::get(Ty, ShAmt);973        Value *NewShl = Builder.CreateShl(X, ShAmtC, "sext");974        return BinaryOperator::CreateAShr(NewShl, ShAmtC);975      }976    }977  }978 979  if (C->isOne() && Op0->hasOneUse()) {980    // add (sext i1 X), 1 --> zext (not X)981    // TODO: The smallest IR representation is (select X, 0, 1), and that would982    // not require the one-use check. But we need to remove a transform in983    // visitSelect and make sure that IR value tracking for select is equal or984    // better than for these ops.985    if (match(Op0, m_SExt(m_Value(X))) &&986        X->getType()->getScalarSizeInBits() == 1)987      return new ZExtInst(Builder.CreateNot(X), Ty);988 989    // Shifts and add used to flip and mask off the low bit:990    // add (ashr (shl i32 X, 31), 31), 1 --> and (not X), 1991    const APInt *C3;992    if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&993        C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) {994      Value *NotX = Builder.CreateNot(X);995      return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));996    }997  }998 999  // umax(X, C) + -C --> usub.sat(X, C)1000  if (match(Op0, m_OneUse(m_UMax(m_Value(X), m_SpecificInt(-*C)))))1001    return replaceInstUsesWith(1002        Add, Builder.CreateBinaryIntrinsic(1003                 Intrinsic::usub_sat, X, ConstantInt::get(Add.getType(), -*C)));1004 1005  // Fold (add (zext (add X, -1)), 1) -> (zext X) if X is non-zero.1006  // TODO: There's a general form for any constant on the outer add.1007  if (C->isOne()) {1008    if (match(Op0, m_ZExt(m_Add(m_Value(X), m_AllOnes())))) {1009      const SimplifyQuery Q = SQ.getWithInstruction(&Add);1010      if (llvm::isKnownNonZero(X, Q))1011        return new ZExtInst(X, Ty);1012    }1013  }1014 1015  return nullptr;1016}1017 1018// match variations of a^2 + 2*a*b + b^21019//1020// to reuse the code between the FP and Int versions, the instruction OpCodes1021//  and constant types have been turned into template parameters.1022//1023// Mul2Rhs: The constant to perform the multiplicative equivalent of X*2 with;1024//  should be `m_SpecificFP(2.0)` for FP and `m_SpecificInt(1)` for Int1025//  (we're matching `X<<1` instead of `X*2` for Int)1026template <bool FP, typename Mul2Rhs>1027static bool matchesSquareSum(BinaryOperator &I, Mul2Rhs M2Rhs, Value *&A,1028                             Value *&B) {1029  constexpr unsigned MulOp = FP ? Instruction::FMul : Instruction::Mul;1030  constexpr unsigned AddOp = FP ? Instruction::FAdd : Instruction::Add;1031  constexpr unsigned Mul2Op = FP ? Instruction::FMul : Instruction::Shl;1032 1033  // (a * a) + (((a * 2) + b) * b)1034  if (match(&I, m_c_BinOp(1035                    AddOp, m_OneUse(m_BinOp(MulOp, m_Value(A), m_Deferred(A))),1036                    m_OneUse(m_c_BinOp(1037                        MulOp,1038                        m_c_BinOp(AddOp, m_BinOp(Mul2Op, m_Deferred(A), M2Rhs),1039                                  m_Value(B)),1040                        m_Deferred(B))))))1041    return true;1042 1043  // ((a * b) * 2)  or ((a * 2) * b)1044  // +1045  // (a * a + b * b) or (b * b + a * a)1046  return match(1047      &I, m_c_BinOp(1048              AddOp,1049              m_CombineOr(1050                  m_OneUse(m_BinOp(1051                      Mul2Op, m_BinOp(MulOp, m_Value(A), m_Value(B)), M2Rhs)),1052                  m_OneUse(m_c_BinOp(MulOp, m_BinOp(Mul2Op, m_Value(A), M2Rhs),1053                                     m_Value(B)))),1054              m_OneUse(1055                  m_c_BinOp(AddOp, m_BinOp(MulOp, m_Deferred(A), m_Deferred(A)),1056                            m_BinOp(MulOp, m_Deferred(B), m_Deferred(B))))));1057}1058 1059// Fold integer variations of a^2 + 2*a*b + b^2 -> (a + b)^21060Instruction *InstCombinerImpl::foldSquareSumInt(BinaryOperator &I) {1061  Value *A, *B;1062  if (matchesSquareSum</*FP*/ false>(I, m_SpecificInt(1), A, B)) {1063    Value *AB = Builder.CreateAdd(A, B);1064    return BinaryOperator::CreateMul(AB, AB);1065  }1066  return nullptr;1067}1068 1069// Fold floating point variations of a^2 + 2*a*b + b^2 -> (a + b)^21070// Requires `nsz` and `reassoc`.1071Instruction *InstCombinerImpl::foldSquareSumFP(BinaryOperator &I) {1072  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() && "Assumption mismatch");1073  Value *A, *B;1074  if (matchesSquareSum</*FP*/ true>(I, m_SpecificFP(2.0), A, B)) {1075    Value *AB = Builder.CreateFAddFMF(A, B, &I);1076    return BinaryOperator::CreateFMulFMF(AB, AB, &I);1077  }1078  return nullptr;1079}1080 1081// Matches multiplication expression Op * C where C is a constant. Returns the1082// constant value in C and the other operand in Op. Returns true if such a1083// match is found.1084static bool MatchMul(Value *E, Value *&Op, APInt &C) {1085  const APInt *AI;1086  if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {1087    C = *AI;1088    return true;1089  }1090  if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {1091    C = APInt(AI->getBitWidth(), 1);1092    C <<= *AI;1093    return true;1094  }1095  return false;1096}1097 1098// Matches remainder expression Op % C where C is a constant. Returns the1099// constant value in C and the other operand in Op. Returns the signedness of1100// the remainder operation in IsSigned. Returns true if such a match is1101// found.1102static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {1103  const APInt *AI;1104  IsSigned = false;1105  if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {1106    IsSigned = true;1107    C = *AI;1108    return true;1109  }1110  if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {1111    C = *AI;1112    return true;1113  }1114  if (match(E, m_And(m_Value(Op), m_APInt(AI))) && (*AI + 1).isPowerOf2()) {1115    C = *AI + 1;1116    return true;1117  }1118  return false;1119}1120 1121// Matches division expression Op / C with the given signedness as indicated1122// by IsSigned, where C is a constant. Returns the constant value in C and the1123// other operand in Op. Returns true if such a match is found.1124static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {1125  const APInt *AI;1126  if (IsSigned && match(E, m_SDiv(m_Value(Op), m_APInt(AI)))) {1127    C = *AI;1128    return true;1129  }1130  if (!IsSigned) {1131    if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {1132      C = *AI;1133      return true;1134    }1135    if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {1136      C = APInt(AI->getBitWidth(), 1);1137      C <<= *AI;1138      return true;1139    }1140  }1141  return false;1142}1143 1144// Returns whether C0 * C1 with the given signedness overflows.1145static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {1146  bool overflow;1147  if (IsSigned)1148    (void)C0.smul_ov(C1, overflow);1149  else1150    (void)C0.umul_ov(C1, overflow);1151  return overflow;1152}1153 1154// Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)1155// does not overflow.1156// Simplifies (X / C0) * C1 + (X % C0) * C2 to1157// (X / C0) * (C1 - C2 * C0) + X * C21158Value *InstCombinerImpl::SimplifyAddWithRemainder(BinaryOperator &I) {1159  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);1160  Value *X, *MulOpV;1161  APInt C0, MulOpC;1162  bool IsSigned;1163  // Match I = X % C0 + MulOpV * C01164  if (((MatchRem(LHS, X, C0, IsSigned) && MatchMul(RHS, MulOpV, MulOpC)) ||1165       (MatchRem(RHS, X, C0, IsSigned) && MatchMul(LHS, MulOpV, MulOpC))) &&1166      C0 == MulOpC) {1167    Value *RemOpV;1168    APInt C1;1169    bool Rem2IsSigned;1170    // Match MulOpC = RemOpV % C11171    if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&1172        IsSigned == Rem2IsSigned) {1173      Value *DivOpV;1174      APInt DivOpC;1175      // Match RemOpV = X / C01176      if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && X == DivOpV &&1177          C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) {1178        Value *NewDivisor = ConstantInt::get(X->getType(), C0 * C1);1179        return IsSigned ? Builder.CreateSRem(X, NewDivisor, "srem")1180                        : Builder.CreateURem(X, NewDivisor, "urem");1181      }1182    }1183  }1184 1185  // Match I = (X / C0) * C1 + (X % C0) * C21186  Value *Div, *Rem;1187  APInt C1, C2;1188  if (!LHS->hasOneUse() || !MatchMul(LHS, Div, C1))1189    Div = LHS, C1 = APInt(I.getType()->getScalarSizeInBits(), 1);1190  if (!RHS->hasOneUse() || !MatchMul(RHS, Rem, C2))1191    Rem = RHS, C2 = APInt(I.getType()->getScalarSizeInBits(), 1);1192  if (match(Div, m_IRem(m_Value(), m_Value()))) {1193    std::swap(Div, Rem);1194    std::swap(C1, C2);1195  }1196  Value *DivOpV;1197  APInt DivOpC;1198  if (MatchRem(Rem, X, C0, IsSigned) &&1199      MatchDiv(Div, DivOpV, DivOpC, IsSigned) && X == DivOpV && C0 == DivOpC &&1200      // Avoid unprofitable replacement of and with mul.1201      !(C1.isOne() && !IsSigned && DivOpC.isPowerOf2() && DivOpC != 2)) {1202    APInt NewC = C1 - C2 * C0;1203    if (!NewC.isZero() && !Rem->hasOneUse())1204      return nullptr;1205    if (!isGuaranteedNotToBeUndef(X, &AC, &I, &DT))1206      return nullptr;1207    Value *MulXC2 = Builder.CreateMul(X, ConstantInt::get(X->getType(), C2));1208    if (NewC.isZero())1209      return MulXC2;1210    return Builder.CreateAdd(1211        Builder.CreateMul(Div, ConstantInt::get(X->getType(), NewC)), MulXC2);1212  }1213 1214  return nullptr;1215}1216 1217/// Fold1218///   (1 << NBits) - 11219/// Into:1220///   ~(-(1 << NBits))1221/// Because a 'not' is better for bit-tracking analysis and other transforms1222/// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.1223static Instruction *canonicalizeLowbitMask(BinaryOperator &I,1224                                           InstCombiner::BuilderTy &Builder) {1225  Value *NBits;1226  if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))1227    return nullptr;1228 1229  Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());1230  Value *NotMask = Builder.CreateShl(MinusOne, NBits, "notmask");1231  // Be wary of constant folding.1232  if (auto *BOp = dyn_cast<BinaryOperator>(NotMask)) {1233    // Always NSW. But NUW propagates from `add`.1234    BOp->setHasNoSignedWrap();1235    BOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());1236  }1237 1238  return BinaryOperator::CreateNot(NotMask, I.getName());1239}1240 1241static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) {1242  assert(I.getOpcode() == Instruction::Add && "Expecting add instruction");1243  Type *Ty = I.getType();1244  auto getUAddSat = [&]() {1245    return Intrinsic::getOrInsertDeclaration(I.getModule(), Intrinsic::uadd_sat,1246                                             Ty);1247  };1248 1249  // add (umin X, ~Y), Y --> uaddsat X, Y1250  Value *X, *Y;1251  if (match(&I, m_c_Add(m_c_UMin(m_Value(X), m_Not(m_Value(Y))),1252                        m_Deferred(Y))))1253    return CallInst::Create(getUAddSat(), { X, Y });1254 1255  // add (umin X, ~C), C --> uaddsat X, C1256  const APInt *C, *NotC;1257  if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&1258      *C == ~*NotC)1259    return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });1260 1261  return nullptr;1262}1263 1264// Transform:1265//  (add A, (shl (neg B), Y))1266//      -> (sub A, (shl B, Y))1267static Instruction *combineAddSubWithShlAddSub(InstCombiner::BuilderTy &Builder,1268                                               const BinaryOperator &I) {1269  Value *A, *B, *Cnt;1270  if (match(&I,1271            m_c_Add(m_OneUse(m_Shl(m_OneUse(m_Neg(m_Value(B))), m_Value(Cnt))),1272                    m_Value(A)))) {1273    Value *NewShl = Builder.CreateShl(B, Cnt);1274    return BinaryOperator::CreateSub(A, NewShl);1275  }1276  return nullptr;1277}1278 1279/// Try to reduce signed division by power-of-2 to an arithmetic shift right.1280static Instruction *foldAddToAshr(BinaryOperator &Add) {1281  // Division must be by power-of-2, but not the minimum signed value.1282  Value *X;1283  const APInt *DivC;1284  if (!match(Add.getOperand(0), m_SDiv(m_Value(X), m_Power2(DivC))) ||1285      DivC->isNegative())1286    return nullptr;1287 1288  // Rounding is done by adding -1 if the dividend (X) is negative and has any1289  // low bits set. It recognizes two canonical patterns:1290  // 1. For an 'ugt' cmp with the signed minimum value (SMIN), the1291  //    pattern is: sext (icmp ugt (X & (DivC - 1)), SMIN).1292  // 2. For an 'eq' cmp, the pattern's: sext (icmp eq X & (SMIN + 1), SMIN + 1).1293  // Note that, by the time we end up here, if possible, ugt has been1294  // canonicalized into eq.1295  const APInt *MaskC, *MaskCCmp;1296  CmpPredicate Pred;1297  if (!match(Add.getOperand(1),1298             m_SExt(m_ICmp(Pred, m_And(m_Specific(X), m_APInt(MaskC)),1299                           m_APInt(MaskCCmp)))))1300    return nullptr;1301 1302  if ((Pred != ICmpInst::ICMP_UGT || !MaskCCmp->isSignMask()) &&1303      (Pred != ICmpInst::ICMP_EQ || *MaskCCmp != *MaskC))1304    return nullptr;1305 1306  APInt SMin = APInt::getSignedMinValue(Add.getType()->getScalarSizeInBits());1307  bool IsMaskValid = Pred == ICmpInst::ICMP_UGT1308                         ? (*MaskC == (SMin | (*DivC - 1)))1309                         : (*DivC == 2 && *MaskC == SMin + 1);1310  if (!IsMaskValid)1311    return nullptr;1312 1313  // (X / DivC) + sext ((X & (SMin | (DivC - 1)) >u SMin) --> X >>s log2(DivC)1314  return BinaryOperator::CreateAShr(1315      X, ConstantInt::get(Add.getType(), DivC->exactLogBase2()));1316}1317 1318Instruction *InstCombinerImpl::foldAddLikeCommutative(Value *LHS, Value *RHS,1319                                                      bool NSW, bool NUW) {1320  Value *A, *B, *C;1321  if (match(LHS, m_Sub(m_Value(A), m_Value(B))) &&1322      match(RHS, m_Sub(m_Value(C), m_Specific(A)))) {1323    Instruction *R = BinaryOperator::CreateSub(C, B);1324    bool NSWOut = NSW && match(LHS, m_NSWSub(m_Value(), m_Value())) &&1325                  match(RHS, m_NSWSub(m_Value(), m_Value()));1326 1327    bool NUWOut = match(LHS, m_NUWSub(m_Value(), m_Value())) &&1328                  match(RHS, m_NUWSub(m_Value(), m_Value()));1329    R->setHasNoSignedWrap(NSWOut);1330    R->setHasNoUnsignedWrap(NUWOut);1331    return R;1332  }1333 1334  // ((X s/ C1) << C2) + X => X s% -C1 where -C1 is 1 << C21335  const APInt *C1, *C2;1336  if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {1337    APInt One(C2->getBitWidth(), 1);1338    APInt MinusC1 = -(*C1);1339    if (MinusC1 == (One << *C2)) {1340      Constant *NewRHS = ConstantInt::get(RHS->getType(), MinusC1);1341      return BinaryOperator::CreateSRem(RHS, NewRHS);1342    }1343  }1344 1345  return nullptr;1346}1347 1348Instruction *InstCombinerImpl::1349    canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(1350        BinaryOperator &I) {1351  assert((I.getOpcode() == Instruction::Add ||1352          I.getOpcode() == Instruction::Or ||1353          I.getOpcode() == Instruction::Sub) &&1354         "Expecting add/or/sub instruction");1355 1356  // We have a subtraction/addition between a (potentially truncated) *logical*1357  // right-shift of X and a "select".1358  Value *X, *Select;1359  Instruction *LowBitsToSkip, *Extract;1360  if (!match(&I, m_c_BinOp(m_TruncOrSelf(m_Instruction(1361                               Extract, m_LShr(m_Value(X),1362                                               m_Instruction(LowBitsToSkip)))),1363                           m_Value(Select))))1364    return nullptr;1365 1366  // `add`/`or` is commutative; but for `sub`, "select" *must* be on RHS.1367  if (I.getOpcode() == Instruction::Sub && I.getOperand(1) != Select)1368    return nullptr;1369 1370  Type *XTy = X->getType();1371  bool HadTrunc = I.getType() != XTy;1372 1373  // If there was a truncation of extracted value, then we'll need to produce1374  // one extra instruction, so we need to ensure one instruction will go away.1375  if (HadTrunc && !match(&I, m_c_BinOp(m_OneUse(m_Value()), m_Value())))1376    return nullptr;1377 1378  // Extraction should extract high NBits bits, with shift amount calculated as:1379  //   low bits to skip = shift bitwidth - high bits to extract1380  // The shift amount itself may be extended, and we need to look past zero-ext1381  // when matching NBits, that will matter for matching later.1382  Value *NBits;1383  if (!match(LowBitsToSkip,1384             m_ZExtOrSelf(m_Sub(m_SpecificInt(XTy->getScalarSizeInBits()),1385                                m_ZExtOrSelf(m_Value(NBits))))))1386    return nullptr;1387 1388  // Sign-extending value can be zero-extended if we `sub`tract it,1389  // or sign-extended otherwise.1390  auto SkipExtInMagic = [&I](Value *&V) {1391    if (I.getOpcode() == Instruction::Sub)1392      match(V, m_ZExtOrSelf(m_Value(V)));1393    else1394      match(V, m_SExtOrSelf(m_Value(V)));1395  };1396 1397  // Now, finally validate the sign-extending magic.1398  // `select` itself may be appropriately extended, look past that.1399  SkipExtInMagic(Select);1400 1401  CmpPredicate Pred;1402  const APInt *Thr;1403  Value *SignExtendingValue, *Zero;1404  bool ShouldSignext;1405  // It must be a select between two values we will later establish to be a1406  // sign-extending value and a zero constant. The condition guarding the1407  // sign-extension must be based on a sign bit of the same X we had in `lshr`.1408  if (!match(Select, m_Select(m_ICmp(Pred, m_Specific(X), m_APInt(Thr)),1409                              m_Value(SignExtendingValue), m_Value(Zero))) ||1410      !isSignBitCheck(Pred, *Thr, ShouldSignext))1411    return nullptr;1412 1413  // icmp-select pair is commutative.1414  if (!ShouldSignext)1415    std::swap(SignExtendingValue, Zero);1416 1417  // If we should not perform sign-extension then we must add/or/subtract zero.1418  if (!match(Zero, m_Zero()))1419    return nullptr;1420  // Otherwise, it should be some constant, left-shifted by the same NBits we1421  // had in `lshr`. Said left-shift can also be appropriately extended.1422  // Again, we must look past zero-ext when looking for NBits.1423  SkipExtInMagic(SignExtendingValue);1424  Constant *SignExtendingValueBaseConstant;1425  if (!match(SignExtendingValue,1426             m_Shl(m_Constant(SignExtendingValueBaseConstant),1427                   m_ZExtOrSelf(m_Specific(NBits)))))1428    return nullptr;1429  // If we `sub`, then the constant should be one, else it should be all-ones.1430  if (I.getOpcode() == Instruction::Sub1431          ? !match(SignExtendingValueBaseConstant, m_One())1432          : !match(SignExtendingValueBaseConstant, m_AllOnes()))1433    return nullptr;1434 1435  auto *NewAShr = BinaryOperator::CreateAShr(X, LowBitsToSkip,1436                                             Extract->getName() + ".sext");1437  NewAShr->copyIRFlags(Extract); // Preserve `exact`-ness.1438  if (!HadTrunc)1439    return NewAShr;1440 1441  Builder.Insert(NewAShr);1442  return TruncInst::CreateTruncOrBitCast(NewAShr, I.getType());1443}1444 1445/// This is a specialization of a more general transform from1446/// foldUsingDistributiveLaws. If that code can be made to work optimally1447/// for multi-use cases or propagating nsw/nuw, then we would not need this.1448static Instruction *factorizeMathWithShlOps(BinaryOperator &I,1449                                            InstCombiner::BuilderTy &Builder) {1450  // TODO: Also handle mul by doubling the shift amount?1451  assert((I.getOpcode() == Instruction::Add ||1452          I.getOpcode() == Instruction::Sub) &&1453         "Expected add/sub");1454  auto *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));1455  auto *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));1456  if (!Op0 || !Op1 || !(Op0->hasOneUse() || Op1->hasOneUse()))1457    return nullptr;1458 1459  Value *X, *Y, *ShAmt;1460  if (!match(Op0, m_Shl(m_Value(X), m_Value(ShAmt))) ||1461      !match(Op1, m_Shl(m_Value(Y), m_Specific(ShAmt))))1462    return nullptr;1463 1464  // No-wrap propagates only when all ops have no-wrap.1465  bool HasNSW = I.hasNoSignedWrap() && Op0->hasNoSignedWrap() &&1466                Op1->hasNoSignedWrap();1467  bool HasNUW = I.hasNoUnsignedWrap() && Op0->hasNoUnsignedWrap() &&1468                Op1->hasNoUnsignedWrap();1469 1470  // add/sub (X << ShAmt), (Y << ShAmt) --> (add/sub X, Y) << ShAmt1471  Value *NewMath = Builder.CreateBinOp(I.getOpcode(), X, Y);1472  if (auto *NewI = dyn_cast<BinaryOperator>(NewMath)) {1473    NewI->setHasNoSignedWrap(HasNSW);1474    NewI->setHasNoUnsignedWrap(HasNUW);1475  }1476  auto *NewShl = BinaryOperator::CreateShl(NewMath, ShAmt);1477  NewShl->setHasNoSignedWrap(HasNSW);1478  NewShl->setHasNoUnsignedWrap(HasNUW);1479  return NewShl;1480}1481 1482/// Reduce a sequence of masked half-width multiplies to a single multiply.1483/// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y1484static Instruction *foldBoxMultiply(BinaryOperator &I) {1485  unsigned BitWidth = I.getType()->getScalarSizeInBits();1486  // Skip the odd bitwidth types.1487  if ((BitWidth & 0x1))1488    return nullptr;1489 1490  unsigned HalfBits = BitWidth >> 1;1491  APInt HalfMask = APInt::getMaxValue(HalfBits);1492 1493  // ResLo = (CrossSum << HalfBits) + (YLo * XLo)1494  Value *XLo, *YLo;1495  Value *CrossSum;1496  // Require one-use on the multiply to avoid increasing the number of1497  // multiplications.1498  if (!match(&I, m_c_Add(m_Shl(m_Value(CrossSum), m_SpecificInt(HalfBits)),1499                         m_OneUse(m_Mul(m_Value(YLo), m_Value(XLo))))))1500    return nullptr;1501 1502  // XLo = X & HalfMask1503  // YLo = Y & HalfMask1504  // TODO: Refactor with SimplifyDemandedBits or KnownBits known leading zeros1505  // to enhance robustness1506  Value *X, *Y;1507  if (!match(XLo, m_And(m_Value(X), m_SpecificInt(HalfMask))) ||1508      !match(YLo, m_And(m_Value(Y), m_SpecificInt(HalfMask))))1509    return nullptr;1510 1511  // CrossSum = (X' * (Y >> Halfbits)) + (Y' * (X >> HalfBits))1512  // X' can be either X or XLo in the pattern (and the same for Y')1513  if (match(CrossSum,1514            m_c_Add(m_c_Mul(m_LShr(m_Specific(Y), m_SpecificInt(HalfBits)),1515                            m_CombineOr(m_Specific(X), m_Specific(XLo))),1516                    m_c_Mul(m_LShr(m_Specific(X), m_SpecificInt(HalfBits)),1517                            m_CombineOr(m_Specific(Y), m_Specific(YLo))))))1518    return BinaryOperator::CreateMul(X, Y);1519 1520  return nullptr;1521}1522 1523Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {1524  if (Value *V = simplifyAddInst(I.getOperand(0), I.getOperand(1),1525                                 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),1526                                 SQ.getWithInstruction(&I)))1527    return replaceInstUsesWith(I, V);1528 1529  if (SimplifyAssociativeOrCommutative(I))1530    return &I;1531 1532  if (Instruction *X = foldVectorBinop(I))1533    return X;1534 1535  if (Instruction *Phi = foldBinopWithPhiOperands(I))1536    return Phi;1537 1538  // (A*B)+(A*C) -> A*(B+C) etc1539  if (Value *V = foldUsingDistributiveLaws(I))1540    return replaceInstUsesWith(I, V);1541 1542  if (Instruction *R = foldBoxMultiply(I))1543    return R;1544 1545  if (Instruction *R = factorizeMathWithShlOps(I, Builder))1546    return R;1547 1548  if (Instruction *X = foldAddWithConstant(I))1549    return X;1550 1551  if (Instruction *X = foldNoWrapAdd(I, Builder))1552    return X;1553 1554  if (Instruction *R = foldBinOpShiftWithShift(I))1555    return R;1556 1557  if (Instruction *R = combineAddSubWithShlAddSub(Builder, I))1558    return R;1559 1560  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);1561  if (Instruction *R = foldAddLikeCommutative(LHS, RHS, I.hasNoSignedWrap(),1562                                              I.hasNoUnsignedWrap()))1563    return R;1564  if (Instruction *R = foldAddLikeCommutative(RHS, LHS, I.hasNoSignedWrap(),1565                                              I.hasNoUnsignedWrap()))1566    return R;1567  Type *Ty = I.getType();1568  if (Ty->isIntOrIntVectorTy(1))1569    return BinaryOperator::CreateXor(LHS, RHS);1570 1571  // X + X --> X << 11572  if (LHS == RHS) {1573    auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));1574    Shl->setHasNoSignedWrap(I.hasNoSignedWrap());1575    Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());1576    return Shl;1577  }1578 1579  Value *A, *B;1580  if (match(LHS, m_Neg(m_Value(A)))) {1581    // -A + -B --> -(A + B)1582    if (match(RHS, m_Neg(m_Value(B))))1583      return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));1584 1585    // -A + B --> B - A1586    auto *Sub = BinaryOperator::CreateSub(RHS, A);1587    auto *OB0 = cast<OverflowingBinaryOperator>(LHS);1588    Sub->setHasNoSignedWrap(I.hasNoSignedWrap() && OB0->hasNoSignedWrap());1589 1590    return Sub;1591  }1592 1593  // A + -B  -->  A - B1594  if (match(RHS, m_Neg(m_Value(B)))) {1595    auto *Sub = BinaryOperator::CreateSub(LHS, B);1596    auto *OBO = cast<OverflowingBinaryOperator>(RHS);1597    Sub->setHasNoSignedWrap(I.hasNoSignedWrap() && OBO->hasNoSignedWrap());1598    return Sub;1599  }1600 1601  if (Value *V = checkForNegativeOperand(I, Builder))1602    return replaceInstUsesWith(I, V);1603 1604  // (A + 1) + ~B --> A - B1605  // ~B + (A + 1) --> A - B1606  // (~B + A) + 1 --> A - B1607  // (A + ~B) + 1 --> A - B1608  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||1609      match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))1610    return BinaryOperator::CreateSub(A, B);1611 1612  // (A + RHS) + RHS --> A + (RHS << 1)1613  if (match(LHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(RHS)))))1614    return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));1615 1616  // LHS + (A + LHS) --> A + (LHS << 1)1617  if (match(RHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(LHS)))))1618    return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));1619 1620  {1621    // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)1622    Constant *C1, *C2;1623    if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),1624                          m_Sub(m_ImmConstant(C2), m_Value(B)))) &&1625        (LHS->hasOneUse() || RHS->hasOneUse())) {1626      Value *Sub = Builder.CreateSub(A, B);1627      return BinaryOperator::CreateAdd(Sub, ConstantExpr::getAdd(C1, C2));1628    }1629 1630    // Canonicalize a constant sub operand as an add operand for better folding:1631    // (C1 - A) + B --> (B - A) + C11632    if (match(&I, m_c_Add(m_OneUse(m_Sub(m_ImmConstant(C1), m_Value(A))),1633                          m_Value(B)))) {1634      Value *Sub = Builder.CreateSub(B, A, "reass.sub");1635      return BinaryOperator::CreateAdd(Sub, C1);1636    }1637  }1638 1639  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)1640  if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);1641 1642  const APInt *C1;1643  // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit1644  if (match(&I, m_c_Add(m_And(m_Value(A), m_APInt(C1)), m_Deferred(A))) &&1645      C1->isPowerOf2() && (ComputeNumSignBits(A) > C1->countl_zero())) {1646    Constant *NewMask = ConstantInt::get(RHS->getType(), *C1 - 1);1647    return BinaryOperator::CreateAnd(A, NewMask);1648  }1649 1650  // ZExt (B - A) + ZExt(A) --> ZExt(B)1651  if ((match(RHS, m_ZExt(m_Value(A))) &&1652       match(LHS, m_ZExt(m_NUWSub(m_Value(B), m_Specific(A))))) ||1653      (match(LHS, m_ZExt(m_Value(A))) &&1654       match(RHS, m_ZExt(m_NUWSub(m_Value(B), m_Specific(A))))))1655    return new ZExtInst(B, LHS->getType());1656 1657  // zext(A) + sext(A) --> 0 if A is i11658  if (match(&I, m_c_BinOp(m_ZExt(m_Value(A)), m_SExt(m_Deferred(A)))) &&1659      A->getType()->isIntOrIntVectorTy(1))1660    return replaceInstUsesWith(I, Constant::getNullValue(I.getType()));1661 1662  // sext(A < B) + zext(A > B) => ucmp/scmp(A, B)1663  CmpPredicate LTPred, GTPred;1664  if (match(&I,1665            m_c_Add(m_SExt(m_c_ICmp(LTPred, m_Value(A), m_Value(B))),1666                    m_ZExt(m_c_ICmp(GTPred, m_Deferred(A), m_Deferred(B))))) &&1667      A->getType()->isIntOrIntVectorTy()) {1668    if (ICmpInst::isGT(LTPred)) {1669      std::swap(LTPred, GTPred);1670      std::swap(A, B);1671    }1672 1673    if (ICmpInst::isLT(LTPred) && ICmpInst::isGT(GTPred) &&1674        ICmpInst::isSigned(LTPred) == ICmpInst::isSigned(GTPred))1675      return replaceInstUsesWith(1676          I, Builder.CreateIntrinsic(1677                 Ty,1678                 ICmpInst::isSigned(LTPred) ? Intrinsic::scmp : Intrinsic::ucmp,1679                 {A, B}));1680  }1681 1682  // A+B --> A|B iff A and B have no bits set in common.1683  WithCache<const Value *> LHSCache(LHS), RHSCache(RHS);1684  if (haveNoCommonBitsSet(LHSCache, RHSCache, SQ.getWithInstruction(&I)))1685    return BinaryOperator::CreateDisjointOr(LHS, RHS);1686 1687  if (Instruction *Ext = narrowMathIfNoOverflow(I))1688    return Ext;1689 1690  // (add (xor A, B) (and A, B)) --> (or A, B)1691  // (add (and A, B) (xor A, B)) --> (or A, B)1692  if (match(&I, m_c_BinOp(m_Xor(m_Value(A), m_Value(B)),1693                          m_c_And(m_Deferred(A), m_Deferred(B)))))1694    return BinaryOperator::CreateOr(A, B);1695 1696  // (add (or A, B) (and A, B)) --> (add A, B)1697  // (add (and A, B) (or A, B)) --> (add A, B)1698  if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),1699                          m_c_And(m_Deferred(A), m_Deferred(B))))) {1700    // Replacing operands in-place to preserve nuw/nsw flags.1701    replaceOperand(I, 0, A);1702    replaceOperand(I, 1, B);1703    return &I;1704  }1705 1706  // (add A (or A, -A)) --> (and (add A, -1) A)1707  // (add A (or -A, A)) --> (and (add A, -1) A)1708  // (add (or A, -A) A) --> (and (add A, -1) A)1709  // (add (or -A, A) A) --> (and (add A, -1) A)1710  if (match(&I, m_c_BinOp(m_Value(A), m_OneUse(m_c_Or(m_Neg(m_Deferred(A)),1711                                                      m_Deferred(A)))))) {1712    Value *Add =1713        Builder.CreateAdd(A, Constant::getAllOnesValue(A->getType()), "",1714                          I.hasNoUnsignedWrap(), I.hasNoSignedWrap());1715    return BinaryOperator::CreateAnd(Add, A);1716  }1717 1718  // Canonicalize ((A & -A) - 1) --> ((A - 1) & ~A)1719  // Forms all commutable operations, and simplifies ctpop -> cttz folds.1720  if (match(&I,1721            m_Add(m_OneUse(m_c_And(m_Value(A), m_OneUse(m_Neg(m_Deferred(A))))),1722                  m_AllOnes()))) {1723    Constant *AllOnes = ConstantInt::getAllOnesValue(RHS->getType());1724    Value *Dec = Builder.CreateAdd(A, AllOnes);1725    Value *Not = Builder.CreateXor(A, AllOnes);1726    return BinaryOperator::CreateAnd(Dec, Not);1727  }1728 1729  // Disguised reassociation/factorization:1730  // ~(A * C1) + A1731  // ((A * -C1) - 1) + A1732  // ((A * -C1) + A) - 11733  // (A * (1 - C1)) - 11734  if (match(&I,1735            m_c_Add(m_OneUse(m_Not(m_OneUse(m_Mul(m_Value(A), m_APInt(C1))))),1736                    m_Deferred(A)))) {1737    Type *Ty = I.getType();1738    Constant *NewMulC = ConstantInt::get(Ty, 1 - *C1);1739    Value *NewMul = Builder.CreateMul(A, NewMulC);1740    return BinaryOperator::CreateAdd(NewMul, ConstantInt::getAllOnesValue(Ty));1741  }1742 1743  // (A * -2**C) + B --> B - (A << C)1744  const APInt *NegPow2C;1745  if (match(&I, m_c_Add(m_OneUse(m_Mul(m_Value(A), m_NegatedPower2(NegPow2C))),1746                        m_Value(B)))) {1747    Constant *ShiftAmtC = ConstantInt::get(Ty, NegPow2C->countr_zero());1748    Value *Shl = Builder.CreateShl(A, ShiftAmtC);1749    return BinaryOperator::CreateSub(B, Shl);1750  }1751 1752  // Canonicalize signum variant that ends in add:1753  // (A s>> (BW - 1)) + (zext (A s> 0)) --> (A s>> (BW - 1)) | (zext (A != 0))1754  uint64_t BitWidth = Ty->getScalarSizeInBits();1755  if (match(LHS, m_AShr(m_Value(A), m_SpecificIntAllowPoison(BitWidth - 1))) &&1756      match(RHS, m_OneUse(m_ZExt(m_OneUse(m_SpecificICmp(1757                     CmpInst::ICMP_SGT, m_Specific(A), m_ZeroInt())))))) {1758    Value *NotZero = Builder.CreateIsNotNull(A, "isnotnull");1759    Value *Zext = Builder.CreateZExt(NotZero, Ty, "isnotnull.zext");1760    return BinaryOperator::CreateOr(LHS, Zext);1761  }1762 1763  {1764    Value *Cond, *Ext;1765    Constant *C;1766    // (add X, (sext/zext (icmp eq X, C)))1767    //    -> (select (icmp eq X, C), (add C, (sext/zext 1)), X)1768    auto CondMatcher =1769        m_Value(Cond, m_SpecificICmp(ICmpInst::ICMP_EQ, m_Deferred(A),1770                                     m_ImmConstant(C)));1771 1772    if (match(&I,1773              m_c_Add(m_Value(A), m_Value(Ext, m_ZExtOrSExt(CondMatcher)))) &&1774        Ext->hasOneUse()) {1775      Value *Add = isa<ZExtInst>(Ext) ? InstCombiner::AddOne(C)1776                                      : InstCombiner::SubOne(C);1777      return replaceInstUsesWith(I, Builder.CreateSelect(Cond, Add, A));1778    }1779  }1780 1781  // (add (add A, 1), (sext (icmp ne A, 0))) => call umax(A, 1)1782  if (match(LHS, m_Add(m_Value(A), m_One())) &&1783      match(RHS, m_OneUse(m_SExt(m_OneUse(m_SpecificICmp(1784                     ICmpInst::ICMP_NE, m_Specific(A), m_ZeroInt())))))) {1785    Value *OneConst = ConstantInt::get(A->getType(), 1);1786    Value *UMax = Builder.CreateBinaryIntrinsic(Intrinsic::umax, A, OneConst);1787    return replaceInstUsesWith(I, UMax);1788  }1789 1790  if (Instruction *Ashr = foldAddToAshr(I))1791    return Ashr;1792 1793  // Ceiling division by power-of-2:1794  // (X >> log2(N)) + zext(X & (N-1) != 0) --> (X + (N-1)) >> log2(N)1795  // This is valid when adding (N-1) to X doesn't overflow.1796  {1797    Value *X;1798    const APInt *ShiftAmt, *Mask;1799    CmpPredicate Pred;1800 1801    // Match: (X >> C) + zext((X & Mask) != 0)1802    // or:    zext((X & Mask) != 0) + (X >> C)1803    if (match(&I, m_c_Add(m_OneUse(m_LShr(m_Value(X), m_APInt(ShiftAmt))),1804                          m_ZExt(m_SpecificICmp(1805                              ICmpInst::ICMP_NE,1806                              m_And(m_Deferred(X), m_LowBitMask(Mask)),1807                              m_ZeroInt())))) &&1808        Mask->popcount() == *ShiftAmt) {1809 1810      // Check if X + Mask doesn't overflow1811      Constant *MaskC = ConstantInt::get(X->getType(), *Mask);1812      if (willNotOverflowUnsignedAdd(X, MaskC, I)) {1813        // (X + Mask) >> ShiftAmt1814        Value *Add = Builder.CreateNUWAdd(X, MaskC);1815        return BinaryOperator::CreateLShr(1816            Add, ConstantInt::get(X->getType(), *ShiftAmt));1817      }1818    }1819  }1820 1821  // (~X) + (~Y) --> -2 - (X + Y)1822  {1823    // To ensure we can save instructions we need to ensure that we consume both1824    // LHS/RHS (i.e they have a `not`).1825    bool ConsumesLHS, ConsumesRHS;1826    if (isFreeToInvert(LHS, LHS->hasOneUse(), ConsumesLHS) && ConsumesLHS &&1827        isFreeToInvert(RHS, RHS->hasOneUse(), ConsumesRHS) && ConsumesRHS) {1828      Value *NotLHS = getFreelyInverted(LHS, LHS->hasOneUse(), &Builder);1829      Value *NotRHS = getFreelyInverted(RHS, RHS->hasOneUse(), &Builder);1830      assert(NotLHS != nullptr && NotRHS != nullptr &&1831             "isFreeToInvert desynced with getFreelyInverted");1832      Value *LHSPlusRHS = Builder.CreateAdd(NotLHS, NotRHS);1833      return BinaryOperator::CreateSub(1834          ConstantInt::getSigned(RHS->getType(), -2), LHSPlusRHS);1835    }1836  }1837 1838  if (Instruction *R = tryFoldInstWithCtpopWithNot(&I))1839    return R;1840 1841  // TODO(jingyue): Consider willNotOverflowSignedAdd and1842  // willNotOverflowUnsignedAdd to reduce the number of invocations of1843  // computeKnownBits.1844  bool Changed = false;1845  if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHSCache, RHSCache, I)) {1846    Changed = true;1847    I.setHasNoSignedWrap(true);1848  }1849  if (!I.hasNoUnsignedWrap() &&1850      willNotOverflowUnsignedAdd(LHSCache, RHSCache, I)) {1851    Changed = true;1852    I.setHasNoUnsignedWrap(true);1853  }1854 1855  if (Instruction *V = canonicalizeLowbitMask(I, Builder))1856    return V;1857 1858  if (Instruction *V =1859          canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))1860    return V;1861 1862  if (Instruction *SatAdd = foldToUnsignedSaturatedAdd(I))1863    return SatAdd;1864 1865  // usub.sat(A, B) + B => umax(A, B)1866  if (match(&I, m_c_BinOp(1867          m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Value(A), m_Value(B))),1868          m_Deferred(B)))) {1869    return replaceInstUsesWith(I,1870        Builder.CreateIntrinsic(Intrinsic::umax, {I.getType()}, {A, B}));1871  }1872 1873  // ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.1874  if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(A)))) &&1875      match(RHS, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(B)))) &&1876      haveNoCommonBitsSet(A, B, SQ.getWithInstruction(&I)))1877    return replaceInstUsesWith(1878        I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},1879                                   {Builder.CreateOr(A, B)}));1880 1881  // Fold the log2_ceil idiom:1882  // zext(ctpop(A) >u/!= 1) + (ctlz(A, true) ^ (BW - 1))1883  // -->1884  // BW - ctlz(A - 1, false)1885  const APInt *XorC;1886  CmpPredicate Pred;1887  if (match(&I,1888            m_c_Add(1889                m_ZExt(m_ICmp(Pred, m_Intrinsic<Intrinsic::ctpop>(m_Value(A)),1890                              m_One())),1891                m_OneUse(m_ZExtOrSelf(m_OneUse(m_Xor(1892                    m_OneUse(m_TruncOrSelf(m_OneUse(1893                        m_Intrinsic<Intrinsic::ctlz>(m_Deferred(A), m_One())))),1894                    m_APInt(XorC))))))) &&1895      (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_NE) &&1896      *XorC == A->getType()->getScalarSizeInBits() - 1) {1897    Value *Sub = Builder.CreateAdd(A, Constant::getAllOnesValue(A->getType()));1898    Value *Ctlz = Builder.CreateIntrinsic(Intrinsic::ctlz, {A->getType()},1899                                          {Sub, Builder.getFalse()});1900    Value *Ret = Builder.CreateSub(1901        ConstantInt::get(A->getType(), A->getType()->getScalarSizeInBits()),1902        Ctlz, "", /*HasNUW=*/true, /*HasNSW=*/true);1903    return replaceInstUsesWith(I, Builder.CreateZExtOrTrunc(Ret, I.getType()));1904  }1905 1906  if (Instruction *Res = foldSquareSumInt(I))1907    return Res;1908 1909  if (Instruction *Res = foldBinOpOfDisplacedShifts(I))1910    return Res;1911 1912  if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))1913    return Res;1914 1915  // Re-enqueue users of the induction variable of add recurrence if we infer1916  // new nuw/nsw flags.1917  if (Changed) {1918    PHINode *PHI;1919    Value *Start, *Step;1920    if (matchSimpleRecurrence(&I, PHI, Start, Step))1921      Worklist.pushUsersToWorkList(*PHI);1922  }1923 1924  return Changed ? &I : nullptr;1925}1926 1927/// Eliminate an op from a linear interpolation (lerp) pattern.1928static Instruction *factorizeLerp(BinaryOperator &I,1929                                  InstCombiner::BuilderTy &Builder) {1930  Value *X, *Y, *Z;1931  if (!match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_Value(Y),1932                                            m_OneUse(m_FSub(m_FPOne(),1933                                                            m_Value(Z))))),1934                          m_OneUse(m_c_FMul(m_Value(X), m_Deferred(Z))))))1935    return nullptr;1936 1937  // (Y * (1.0 - Z)) + (X * Z) --> Y + Z * (X - Y) [8 commuted variants]1938  Value *XY = Builder.CreateFSubFMF(X, Y, &I);1939  Value *MulZ = Builder.CreateFMulFMF(Z, XY, &I);1940  return BinaryOperator::CreateFAddFMF(Y, MulZ, &I);1941}1942 1943/// Factor a common operand out of fadd/fsub of fmul/fdiv.1944static Instruction *factorizeFAddFSub(BinaryOperator &I,1945                                      InstCombiner::BuilderTy &Builder) {1946  assert((I.getOpcode() == Instruction::FAdd ||1947          I.getOpcode() == Instruction::FSub) && "Expecting fadd/fsub");1948  assert(I.hasAllowReassoc() && I.hasNoSignedZeros() &&1949         "FP factorization requires FMF");1950 1951  if (Instruction *Lerp = factorizeLerp(I, Builder))1952    return Lerp;1953 1954  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);1955  if (!Op0->hasOneUse() || !Op1->hasOneUse())1956    return nullptr;1957 1958  Value *X, *Y, *Z;1959  bool IsFMul;1960  if ((match(Op0, m_FMul(m_Value(X), m_Value(Z))) &&1961       match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))) ||1962      (match(Op0, m_FMul(m_Value(Z), m_Value(X))) &&1963       match(Op1, m_c_FMul(m_Value(Y), m_Specific(Z)))))1964    IsFMul = true;1965  else if (match(Op0, m_FDiv(m_Value(X), m_Value(Z))) &&1966           match(Op1, m_FDiv(m_Value(Y), m_Specific(Z))))1967    IsFMul = false;1968  else1969    return nullptr;1970 1971  // (X * Z) + (Y * Z) --> (X + Y) * Z1972  // (X * Z) - (Y * Z) --> (X - Y) * Z1973  // (X / Z) + (Y / Z) --> (X + Y) / Z1974  // (X / Z) - (Y / Z) --> (X - Y) / Z1975  bool IsFAdd = I.getOpcode() == Instruction::FAdd;1976  Value *XY = IsFAdd ? Builder.CreateFAddFMF(X, Y, &I)1977                     : Builder.CreateFSubFMF(X, Y, &I);1978 1979  // Bail out if we just created a denormal constant.1980  // TODO: This is copied from a previous implementation. Is it necessary?1981  const APFloat *C;1982  if (match(XY, m_APFloat(C)) && !C->isNormal())1983    return nullptr;1984 1985  return IsFMul ? BinaryOperator::CreateFMulFMF(XY, Z, &I)1986                : BinaryOperator::CreateFDivFMF(XY, Z, &I);1987}1988 1989Instruction *InstCombinerImpl::visitFAdd(BinaryOperator &I) {1990  if (Value *V = simplifyFAddInst(I.getOperand(0), I.getOperand(1),1991                                  I.getFastMathFlags(),1992                                  SQ.getWithInstruction(&I)))1993    return replaceInstUsesWith(I, V);1994 1995  if (SimplifyAssociativeOrCommutative(I))1996    return &I;1997 1998  if (Instruction *X = foldVectorBinop(I))1999    return X;2000 2001  if (Instruction *Phi = foldBinopWithPhiOperands(I))2002    return Phi;2003 2004  if (Instruction *FoldedFAdd = foldBinOpIntoSelectOrPhi(I))2005    return FoldedFAdd;2006 2007  // B = fadd A, 0.02008  // Z = Op B2009  // can be transformed into2010  // Z = Op A2011  // Where Op is such that we can ignore sign of 0 in fadd2012  Value *A;2013  if (match(&I, m_OneUse(m_FAdd(m_Value(A), m_AnyZeroFP()))) &&2014      canIgnoreSignBitOfZero(*I.use_begin()))2015    return replaceInstUsesWith(I, A);2016 2017  // (-X) + Y --> Y - X2018  Value *X, *Y;2019  if (match(&I, m_c_FAdd(m_FNeg(m_Value(X)), m_Value(Y))))2020    return BinaryOperator::CreateFSubFMF(Y, X, &I);2021 2022  // Similar to above, but look through fmul/fdiv for the negated term.2023  // (-X * Y) + Z --> Z - (X * Y) [4 commuted variants]2024  Value *Z;2025  if (match(&I, m_c_FAdd(m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))),2026                         m_Value(Z)))) {2027    Value *XY = Builder.CreateFMulFMF(X, Y, &I);2028    return BinaryOperator::CreateFSubFMF(Z, XY, &I);2029  }2030  // (-X / Y) + Z --> Z - (X / Y) [2 commuted variants]2031  // (X / -Y) + Z --> Z - (X / Y) [2 commuted variants]2032  if (match(&I, m_c_FAdd(m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y))),2033                         m_Value(Z))) ||2034      match(&I, m_c_FAdd(m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))),2035                         m_Value(Z)))) {2036    Value *XY = Builder.CreateFDivFMF(X, Y, &I);2037    return BinaryOperator::CreateFSubFMF(Z, XY, &I);2038  }2039 2040  // Check for (fadd double (sitofp x), y), see if we can merge this into an2041  // integer add followed by a promotion.2042  if (Instruction *R = foldFBinOpOfIntCasts(I))2043    return R;2044 2045  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);2046  // Handle specials cases for FAdd with selects feeding the operation2047  if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS, RHS))2048    return replaceInstUsesWith(I, V);2049 2050  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {2051    if (Instruction *F = factorizeFAddFSub(I, Builder))2052      return F;2053 2054    if (Instruction *F = foldSquareSumFP(I))2055      return F;2056 2057    // Try to fold fadd into start value of reduction intrinsic.2058    if (match(&I, m_c_FAdd(m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(2059                               m_AnyZeroFP(), m_Value(X))),2060                           m_Value(Y)))) {2061      // fadd (rdx 0.0, X), Y --> rdx Y, X2062      return replaceInstUsesWith(2063          I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,2064                                     {X->getType()}, {Y, X}, &I));2065    }2066    const APFloat *StartC, *C;2067    if (match(LHS, m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(2068                       m_APFloat(StartC), m_Value(X)))) &&2069        match(RHS, m_APFloat(C))) {2070      // fadd (rdx StartC, X), C --> rdx (C + StartC), X2071      Constant *NewStartC = ConstantFP::get(I.getType(), *C + *StartC);2072      return replaceInstUsesWith(2073          I, Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,2074                                     {X->getType()}, {NewStartC, X}, &I));2075    }2076 2077    // (X * MulC) + X --> X * (MulC + 1.0)2078    Constant *MulC;2079    if (match(&I, m_c_FAdd(m_FMul(m_Value(X), m_ImmConstant(MulC)),2080                           m_Deferred(X)))) {2081      if (Constant *NewMulC = ConstantFoldBinaryOpOperands(2082              Instruction::FAdd, MulC, ConstantFP::get(I.getType(), 1.0), DL))2083        return BinaryOperator::CreateFMulFMF(X, NewMulC, &I);2084    }2085 2086    // (-X - Y) + (X + Z) --> Z - Y2087    if (match(&I, m_c_FAdd(m_FSub(m_FNeg(m_Value(X)), m_Value(Y)),2088                           m_c_FAdd(m_Deferred(X), m_Value(Z)))))2089      return BinaryOperator::CreateFSubFMF(Z, Y, &I);2090 2091    if (Value *V = FAddCombine(Builder).simplify(&I))2092      return replaceInstUsesWith(I, V);2093  }2094 2095  // minumum(X, Y) + maximum(X, Y) => X + Y.2096  if (match(&I,2097            m_c_FAdd(m_Intrinsic<Intrinsic::maximum>(m_Value(X), m_Value(Y)),2098                     m_c_Intrinsic<Intrinsic::minimum>(m_Deferred(X),2099                                                       m_Deferred(Y))))) {2100    BinaryOperator *Result = BinaryOperator::CreateFAddFMF(X, Y, &I);2101    // We cannot preserve ninf if nnan flag is not set.2102    // If X is NaN and Y is Inf then in original program we had NaN + NaN,2103    // while in optimized version NaN + Inf and this is a poison with ninf flag.2104    if (!Result->hasNoNaNs())2105      Result->setHasNoInfs(false);2106    return Result;2107  }2108 2109  return nullptr;2110}2111 2112CommonPointerBase CommonPointerBase::compute(Value *LHS, Value *RHS) {2113  CommonPointerBase Base;2114 2115  if (LHS->getType() != RHS->getType())2116    return Base;2117 2118  // Collect all base pointers of LHS.2119  SmallPtrSet<Value *, 16> Ptrs;2120  Value *Ptr = LHS;2121  while (true) {2122    Ptrs.insert(Ptr);2123    if (auto *GEP = dyn_cast<GEPOperator>(Ptr))2124      Ptr = GEP->getPointerOperand();2125    else2126      break;2127  }2128 2129  // Find common base and collect RHS GEPs.2130  bool First = true;2131  while (true) {2132    if (Ptrs.contains(RHS)) {2133      Base.Ptr = RHS;2134      break;2135    }2136 2137    if (auto *GEP = dyn_cast<GEPOperator>(RHS)) {2138      Base.RHSGEPs.push_back(GEP);2139      if (First) {2140        First = false;2141        Base.RHSNW = GEP->getNoWrapFlags();2142      } else {2143        Base.RHSNW = Base.RHSNW.intersectForOffsetAdd(GEP->getNoWrapFlags());2144      }2145      RHS = GEP->getPointerOperand();2146    } else {2147      // No common base.2148      return Base;2149    }2150  }2151 2152  // Collect LHS GEPs.2153  First = true;2154  while (true) {2155    if (LHS == Base.Ptr)2156      break;2157 2158    auto *GEP = cast<GEPOperator>(LHS);2159    Base.LHSGEPs.push_back(GEP);2160    if (First) {2161      First = false;2162      Base.LHSNW = GEP->getNoWrapFlags();2163    } else {2164      Base.LHSNW = Base.LHSNW.intersectForOffsetAdd(GEP->getNoWrapFlags());2165    }2166    LHS = GEP->getPointerOperand();2167  }2168 2169  return Base;2170}2171 2172bool CommonPointerBase::isExpensive() const {2173  unsigned NumGEPs = 0;2174  auto ProcessGEPs = [&NumGEPs](ArrayRef<GEPOperator *> GEPs) {2175    bool SeenMultiUse = false;2176    for (GEPOperator *GEP : GEPs) {2177      // Only count multi-use GEPs, excluding the first one. For the first one,2178      // we will directly reuse the offset. For one-use GEPs, their offset will2179      // be folded into a multi-use GEP.2180      if (!GEP->hasOneUse()) {2181        if (SeenMultiUse)2182          ++NumGEPs;2183        SeenMultiUse = true;2184      }2185    }2186  };2187  ProcessGEPs(LHSGEPs);2188  ProcessGEPs(RHSGEPs);2189  return NumGEPs > 2;2190}2191 2192/// Optimize pointer differences into the same array into a size.  Consider:2193///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer2194/// operands to the ptrtoint instructions for the LHS/RHS of the subtract.2195Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS,2196                                                   Type *Ty, bool IsNUW) {2197  CommonPointerBase Base = CommonPointerBase::compute(LHS, RHS);2198  if (!Base.Ptr || Base.isExpensive())2199    return nullptr;2200 2201  // To avoid duplicating the offset arithmetic, rewrite the GEP to use the2202  // computed offset.2203  // TODO: We should probably do this even if there is only one GEP.2204  bool RewriteGEPs = !Base.LHSGEPs.empty() && !Base.RHSGEPs.empty();2205 2206  Type *IdxTy = DL.getIndexType(LHS->getType());2207  Value *Result = EmitGEPOffsets(Base.LHSGEPs, Base.LHSNW, IdxTy, RewriteGEPs);2208  Value *Offset2 = EmitGEPOffsets(Base.RHSGEPs, Base.RHSNW, IdxTy, RewriteGEPs);2209 2210  // If this is a single inbounds GEP and the original sub was nuw,2211  // then the final multiplication is also nuw.2212  if (auto *I = dyn_cast<OverflowingBinaryOperator>(Result))2213    if (IsNUW && match(Offset2, m_Zero()) && Base.LHSNW.isInBounds() &&2214        (I->use_empty() || I->hasOneUse()) && I->hasNoSignedWrap() &&2215        !I->hasNoUnsignedWrap() &&2216        ((I->getOpcode() == Instruction::Mul &&2217          match(I->getOperand(1), m_NonNegative())) ||2218         I->getOpcode() == Instruction::Shl))2219      cast<Instruction>(I)->setHasNoUnsignedWrap();2220 2221  // If we have a 2nd GEP of the same base pointer, subtract the offsets.2222  // If both GEPs are inbounds, then the subtract does not have signed overflow.2223  // If both GEPs are nuw and the original sub is nuw, the new sub is also nuw.2224  if (!match(Offset2, m_Zero())) {2225    Result =2226        Builder.CreateSub(Result, Offset2, "gepdiff",2227                          IsNUW && Base.LHSNW.hasNoUnsignedWrap() &&2228                              Base.RHSNW.hasNoUnsignedWrap(),2229                          Base.LHSNW.isInBounds() && Base.RHSNW.isInBounds());2230  }2231 2232  return Builder.CreateIntCast(Result, Ty, true);2233}2234 2235static Instruction *foldSubOfMinMax(BinaryOperator &I,2236                                    InstCombiner::BuilderTy &Builder) {2237  Value *Op0 = I.getOperand(0);2238  Value *Op1 = I.getOperand(1);2239  Type *Ty = I.getType();2240  auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op1);2241  if (!MinMax)2242    return nullptr;2243 2244  // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y)2245  // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y)2246  Value *X = MinMax->getLHS();2247  Value *Y = MinMax->getRHS();2248  if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&2249      (Op0->hasOneUse() || Op1->hasOneUse())) {2250    Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());2251    Function *F = Intrinsic::getOrInsertDeclaration(I.getModule(), InvID, Ty);2252    return CallInst::Create(F, {X, Y});2253  }2254 2255  // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))2256  // sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Z,Y))2257  Value *Z;2258  if (match(Op1, m_OneUse(m_UMin(m_Value(Y), m_Value(Z))))) {2259    if (match(Op0, m_OneUse(m_c_Add(m_Specific(Y), m_Value(X))))) {2260      Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Y, Z});2261      return BinaryOperator::CreateAdd(X, USub);2262    }2263    if (match(Op0, m_OneUse(m_c_Add(m_Specific(Z), m_Value(X))))) {2264      Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, Ty, {Z, Y});2265      return BinaryOperator::CreateAdd(X, USub);2266    }2267  }2268 2269  // sub Op0, smin((sub nsw Op0, Z), 0) --> smax Op0, Z2270  // sub Op0, smax((sub nsw Op0, Z), 0) --> smin Op0, Z2271  if (MinMax->isSigned() && match(Y, m_ZeroInt()) &&2272      match(X, m_NSWSub(m_Specific(Op0), m_Value(Z)))) {2273    Intrinsic::ID InvID = getInverseMinMaxIntrinsic(MinMax->getIntrinsicID());2274    Function *F = Intrinsic::getOrInsertDeclaration(I.getModule(), InvID, Ty);2275    return CallInst::Create(F, {Op0, Z});2276  }2277 2278  return nullptr;2279}2280 2281Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {2282  if (Value *V = simplifySubInst(I.getOperand(0), I.getOperand(1),2283                                 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),2284                                 SQ.getWithInstruction(&I)))2285    return replaceInstUsesWith(I, V);2286 2287  if (Instruction *X = foldVectorBinop(I))2288    return X;2289 2290  if (Instruction *Phi = foldBinopWithPhiOperands(I))2291    return Phi;2292 2293  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);2294 2295  // If this is a 'B = x-(-A)', change to B = x+A.2296  // We deal with this without involving Negator to preserve NSW flag.2297  if (Value *V = dyn_castNegVal(Op1)) {2298    BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);2299 2300    if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {2301      assert(BO->getOpcode() == Instruction::Sub &&2302             "Expected a subtraction operator!");2303      if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())2304        Res->setHasNoSignedWrap(true);2305    } else {2306      if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())2307        Res->setHasNoSignedWrap(true);2308    }2309 2310    return Res;2311  }2312 2313  // Try this before Negator to preserve NSW flag.2314  if (Instruction *R = factorizeMathWithShlOps(I, Builder))2315    return R;2316 2317  Constant *C;2318  if (match(Op0, m_ImmConstant(C))) {2319    Value *X;2320    Constant *C2;2321 2322    // C-(X+C2) --> (C-C2)-X2323    if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2)))) {2324      // C-C2 never overflow, and C-(X+C2), (X+C2) has NSW/NUW2325      // => (C-C2)-X can have NSW/NUW2326      bool WillNotSOV = willNotOverflowSignedSub(C, C2, I);2327      BinaryOperator *Res =2328          BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);2329      auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);2330      Res->setHasNoSignedWrap(I.hasNoSignedWrap() && OBO1->hasNoSignedWrap() &&2331                              WillNotSOV);2332      Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() &&2333                                OBO1->hasNoUnsignedWrap());2334      return Res;2335    }2336  }2337 2338  auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {2339    if (Instruction *Ext = narrowMathIfNoOverflow(I))2340      return Ext;2341 2342    bool Changed = false;2343    if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {2344      Changed = true;2345      I.setHasNoSignedWrap(true);2346    }2347    if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedSub(Op0, Op1, I)) {2348      Changed = true;2349      I.setHasNoUnsignedWrap(true);2350    }2351 2352    return Changed ? &I : nullptr;2353  };2354 2355  // First, let's try to interpret `sub a, b` as `add a, (sub 0, b)`,2356  // and let's try to sink `(sub 0, b)` into `b` itself. But only if this isn't2357  // a pure negation used by a select that looks like abs/nabs.2358  bool IsNegation = match(Op0, m_ZeroInt());2359  if (!IsNegation || none_of(I.users(), match_fn(m_c_Select(m_Specific(Op1),2360                                                            m_Specific(&I))))) {2361    if (Value *NegOp1 = Negator::Negate(IsNegation, /* IsNSW */ IsNegation &&2362                                                        I.hasNoSignedWrap(),2363                                        Op1, *this))2364      return BinaryOperator::CreateAdd(NegOp1, Op0);2365  }2366  if (IsNegation)2367    return TryToNarrowDeduceFlags(); // Should have been handled in Negator!2368 2369  // (A*B)-(A*C) -> A*(B-C) etc2370  if (Value *V = foldUsingDistributiveLaws(I))2371    return replaceInstUsesWith(I, V);2372 2373  if (I.getType()->isIntOrIntVectorTy(1))2374    return BinaryOperator::CreateXor(Op0, Op1);2375 2376  // Replace (-1 - A) with (~A).2377  if (match(Op0, m_AllOnes()))2378    return BinaryOperator::CreateNot(Op1);2379 2380  // (X + -1) - Y --> ~Y + X2381  Value *X, *Y;2382  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_AllOnes()))))2383    return BinaryOperator::CreateAdd(Builder.CreateNot(Op1), X);2384 2385  // if (C1 & C2) == C2 then (X & C1) - (X & C2) -> X & (C1 ^ C2)2386  Constant *C1, *C2;2387  if (match(Op0, m_And(m_Value(X), m_ImmConstant(C1))) &&2388      match(Op1, m_And(m_Specific(X), m_ImmConstant(C2)))) {2389    Value *AndC = ConstantFoldBinaryInstruction(Instruction::And, C1, C2);2390    if (C2->isElementWiseEqual(AndC))2391      return BinaryOperator::CreateAnd(2392          X, ConstantFoldBinaryInstruction(Instruction::Xor, C1, C2));2393  }2394 2395  // Reassociate sub/add sequences to create more add instructions and2396  // reduce dependency chains:2397  // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)2398  Value *Z;2399  if (match(Op0, m_OneUse(m_c_Add(m_OneUse(m_Sub(m_Value(X), m_Value(Y))),2400                                  m_Value(Z))))) {2401    Value *XZ = Builder.CreateAdd(X, Z);2402    Value *YW = Builder.CreateAdd(Y, Op1);2403    return BinaryOperator::CreateSub(XZ, YW);2404  }2405 2406  // ((X - Y) - Op1)  -->  X - (Y + Op1)2407  if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y))))) {2408    OverflowingBinaryOperator *LHSSub = cast<OverflowingBinaryOperator>(Op0);2409    bool HasNUW = I.hasNoUnsignedWrap() && LHSSub->hasNoUnsignedWrap();2410    bool HasNSW = HasNUW && I.hasNoSignedWrap() && LHSSub->hasNoSignedWrap();2411    Value *Add = Builder.CreateAdd(Y, Op1, "", /*HasNUW=*/HasNUW,2412                                   /*HasNSW=*/HasNSW);2413    BinaryOperator *Sub = BinaryOperator::CreateSub(X, Add);2414    Sub->setHasNoUnsignedWrap(HasNUW);2415    Sub->setHasNoSignedWrap(HasNSW);2416    return Sub;2417  }2418 2419  {2420    // (X + Z) - (Y + Z) --> (X - Y)2421    // This is done in other passes, but we want to be able to consume this2422    // pattern in InstCombine so we can generate it without creating infinite2423    // loops.2424    if (match(Op0, m_Add(m_Value(X), m_Value(Z))) &&2425        match(Op1, m_c_Add(m_Value(Y), m_Specific(Z))))2426      return BinaryOperator::CreateSub(X, Y);2427 2428    // (X + C0) - (Y + C1) --> (X - Y) + (C0 - C1)2429    Constant *CX, *CY;2430    if (match(Op0, m_OneUse(m_Add(m_Value(X), m_ImmConstant(CX)))) &&2431        match(Op1, m_OneUse(m_Add(m_Value(Y), m_ImmConstant(CY))))) {2432      Value *OpsSub = Builder.CreateSub(X, Y);2433      Constant *ConstsSub = ConstantExpr::getSub(CX, CY);2434      return BinaryOperator::CreateAdd(OpsSub, ConstsSub);2435    }2436  }2437 2438  {2439    Value *W, *Z;2440    if (match(Op0, m_AddLike(m_Value(W), m_Value(X))) &&2441        match(Op1, m_AddLike(m_Value(Y), m_Value(Z)))) {2442      Instruction *R = nullptr;2443      if (W == Y)2444        R = BinaryOperator::CreateSub(X, Z);2445      else if (W == Z)2446        R = BinaryOperator::CreateSub(X, Y);2447      else if (X == Y)2448        R = BinaryOperator::CreateSub(W, Z);2449      else if (X == Z)2450        R = BinaryOperator::CreateSub(W, Y);2451      if (R) {2452        bool NSW = I.hasNoSignedWrap() &&2453                   match(Op0, m_NSWAddLike(m_Value(), m_Value())) &&2454                   match(Op1, m_NSWAddLike(m_Value(), m_Value()));2455 2456        bool NUW = I.hasNoUnsignedWrap() &&2457                   match(Op1, m_NUWAddLike(m_Value(), m_Value()));2458        R->setHasNoSignedWrap(NSW);2459        R->setHasNoUnsignedWrap(NUW);2460        return R;2461      }2462    }2463  }2464 2465  // (~X) - (~Y) --> Y - X2466  {2467    // Need to ensure we can consume at least one of the `not` instructions,2468    // otherwise this can inf loop.2469    bool ConsumesOp0, ConsumesOp1;2470    if (isFreeToInvert(Op0, Op0->hasOneUse(), ConsumesOp0) &&2471        isFreeToInvert(Op1, Op1->hasOneUse(), ConsumesOp1) &&2472        (ConsumesOp0 || ConsumesOp1)) {2473      Value *NotOp0 = getFreelyInverted(Op0, Op0->hasOneUse(), &Builder);2474      Value *NotOp1 = getFreelyInverted(Op1, Op1->hasOneUse(), &Builder);2475      assert(NotOp0 != nullptr && NotOp1 != nullptr &&2476             "isFreeToInvert desynced with getFreelyInverted");2477      return BinaryOperator::CreateSub(NotOp1, NotOp0);2478    }2479  }2480 2481  auto m_AddRdx = [](Value *&Vec) {2482    return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_add>(m_Value(Vec)));2483  };2484  Value *V0, *V1;2485  if (match(Op0, m_AddRdx(V0)) && match(Op1, m_AddRdx(V1)) &&2486      V0->getType() == V1->getType()) {2487    // Difference of sums is sum of differences:2488    // add_rdx(V0) - add_rdx(V1) --> add_rdx(V0 - V1)2489    Value *Sub = Builder.CreateSub(V0, V1);2490    Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_add,2491                                         {Sub->getType()}, {Sub});2492    return replaceInstUsesWith(I, Rdx);2493  }2494 2495  if (Constant *C = dyn_cast<Constant>(Op0)) {2496    Value *X;2497    if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))2498      // C - (zext bool) --> bool ? C - 1 : C2499      return SelectInst::Create(X, InstCombiner::SubOne(C), C);2500    if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))2501      // C - (sext bool) --> bool ? C + 1 : C2502      return SelectInst::Create(X, InstCombiner::AddOne(C), C);2503 2504    // C - ~X == X + (1+C)2505    if (match(Op1, m_Not(m_Value(X))))2506      return BinaryOperator::CreateAdd(X, InstCombiner::AddOne(C));2507 2508    // Try to fold constant sub into select arguments.2509    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))2510      if (Instruction *R = FoldOpIntoSelect(I, SI))2511        return R;2512 2513    // Try to fold constant sub into PHI values.2514    if (PHINode *PN = dyn_cast<PHINode>(Op1))2515      if (Instruction *R = foldOpIntoPhi(I, PN))2516        return R;2517 2518    Constant *C2;2519 2520    // C-(C2-X) --> X+(C-C2)2521    if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))2522      return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));2523  }2524 2525  const APInt *Op0C;2526  if (match(Op0, m_APInt(Op0C))) {2527    if (Op0C->isMask()) {2528      // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known2529      // zero. We don't use information from dominating conditions so this2530      // transform is easier to reverse if necessary.2531      KnownBits RHSKnown = llvm::computeKnownBits(2532          Op1, SQ.getWithInstruction(&I).getWithoutDomCondCache());2533      if ((*Op0C | RHSKnown.Zero).isAllOnes())2534        return BinaryOperator::CreateXor(Op1, Op0);2535    }2536 2537    // C - ((C3 -nuw X) & C2) --> (C - (C2 & C3)) + (X & C2) when:2538    // (C3 - ((C2 & C3) - 1)) is pow22539    // ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1)2540    // C2 is negative pow2 || sub nuw2541    const APInt *C2, *C3;2542    BinaryOperator *InnerSub;2543    if (match(Op1, m_OneUse(m_And(m_BinOp(InnerSub), m_APInt(C2)))) &&2544        match(InnerSub, m_Sub(m_APInt(C3), m_Value(X))) &&2545        (InnerSub->hasNoUnsignedWrap() || C2->isNegatedPowerOf2())) {2546      APInt C2AndC3 = *C2 & *C3;2547      APInt C2AndC3Minus1 = C2AndC3 - 1;2548      APInt C2AddC3 = *C2 + *C3;2549      if ((*C3 - C2AndC3Minus1).isPowerOf2() &&2550          C2AndC3Minus1.isSubsetOf(C2AddC3)) {2551        Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(), *C2));2552        return BinaryOperator::CreateAdd(2553            And, ConstantInt::get(I.getType(), *Op0C - C2AndC3));2554      }2555    }2556  }2557 2558  {2559    Value *Y;2560    // X-(X+Y) == -Y    X-(Y+X) == -Y2561    if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))2562      return BinaryOperator::CreateNeg(Y);2563 2564    // (X-Y)-X == -Y2565    if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))2566      return BinaryOperator::CreateNeg(Y);2567  }2568 2569  // (sub (or A, B) (and A, B)) --> (xor A, B)2570  {2571    Value *A, *B;2572    if (match(Op1, m_And(m_Value(A), m_Value(B))) &&2573        match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))2574      return BinaryOperator::CreateXor(A, B);2575  }2576 2577  // (sub (add A, B) (or A, B)) --> (and A, B)2578  {2579    Value *A, *B;2580    if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&2581        match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))2582      return BinaryOperator::CreateAnd(A, B);2583  }2584 2585  // (sub (add A, B) (and A, B)) --> (or A, B)2586  {2587    Value *A, *B;2588    if (match(Op0, m_Add(m_Value(A), m_Value(B))) &&2589        match(Op1, m_c_And(m_Specific(A), m_Specific(B))))2590      return BinaryOperator::CreateOr(A, B);2591  }2592 2593  // (sub (and A, B) (or A, B)) --> neg (xor A, B)2594  {2595    Value *A, *B;2596    if (match(Op0, m_And(m_Value(A), m_Value(B))) &&2597        match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&2598        (Op0->hasOneUse() || Op1->hasOneUse()))2599      return BinaryOperator::CreateNeg(Builder.CreateXor(A, B));2600  }2601 2602  // (sub (or A, B), (xor A, B)) --> (and A, B)2603  {2604    Value *A, *B;2605    if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&2606        match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))2607      return BinaryOperator::CreateAnd(A, B);2608  }2609 2610  // (sub (xor A, B) (or A, B)) --> neg (and A, B)2611  {2612    Value *A, *B;2613    if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&2614        match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&2615        (Op0->hasOneUse() || Op1->hasOneUse()))2616      return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));2617  }2618 2619  {2620    Value *Y;2621    // ((X | Y) - X) --> (~X & Y)2622    if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))2623      return BinaryOperator::CreateAnd(2624          Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));2625  }2626 2627  {2628    // (sub (and Op1, (neg X)), Op1) --> neg (and Op1, (add X, -1))2629    Value *X;2630    if (match(Op0, m_OneUse(m_c_And(m_Specific(Op1),2631                                    m_OneUse(m_Neg(m_Value(X))))))) {2632      return BinaryOperator::CreateNeg(Builder.CreateAnd(2633          Op1, Builder.CreateAdd(X, Constant::getAllOnesValue(I.getType()))));2634    }2635  }2636 2637  {2638    // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)2639    Constant *C;2640    if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {2641      return BinaryOperator::CreateNeg(2642          Builder.CreateAnd(Op1, Builder.CreateNot(C)));2643    }2644  }2645 2646  {2647    // (sub (xor X, (sext C)), (sext C)) => (select C, (neg X), X)2648    // (sub (sext C), (xor X, (sext C))) => (select C, X, (neg X))2649    Value *C, *X;2650    auto m_SubXorCmp = [&C, &X](Value *LHS, Value *RHS) {2651      return match(LHS, m_OneUse(m_c_Xor(m_Value(X), m_Specific(RHS)))) &&2652             match(RHS, m_SExt(m_Value(C))) &&2653             (C->getType()->getScalarSizeInBits() == 1);2654    };2655    if (m_SubXorCmp(Op0, Op1))2656      return SelectInst::Create(C, Builder.CreateNeg(X), X);2657    if (m_SubXorCmp(Op1, Op0))2658      return SelectInst::Create(C, X, Builder.CreateNeg(X));2659  }2660 2661  if (Instruction *R = tryFoldInstWithCtpopWithNot(&I))2662    return R;2663 2664  if (Instruction *R = foldSubOfMinMax(I, Builder))2665    return R;2666 2667  {2668    // If we have a subtraction between some value and a select between2669    // said value and something else, sink subtraction into select hands, i.e.:2670    //   sub (select %Cond, %TrueVal, %FalseVal), %Op12671    //     ->2672    //   select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)2673    //  or2674    //   sub %Op0, (select %Cond, %TrueVal, %FalseVal)2675    //     ->2676    //   select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)2677    // This will result in select between new subtraction and 0.2678    auto SinkSubIntoSelect =2679        [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,2680                           auto SubBuilder) -> Instruction * {2681      Value *Cond, *TrueVal, *FalseVal;2682      if (!match(Select, m_OneUse(m_Select(m_Value(Cond), m_Value(TrueVal),2683                                           m_Value(FalseVal)))))2684        return nullptr;2685      if (OtherHandOfSub != TrueVal && OtherHandOfSub != FalseVal)2686        return nullptr;2687      // While it is really tempting to just create two subtractions and let2688      // InstCombine fold one of those to 0, it isn't possible to do so2689      // because of worklist visitation order. So ugly it is.2690      bool OtherHandOfSubIsTrueVal = OtherHandOfSub == TrueVal;2691      Value *NewSub = SubBuilder(OtherHandOfSubIsTrueVal ? FalseVal : TrueVal);2692      Constant *Zero = Constant::getNullValue(Ty);2693      SelectInst *NewSel =2694          SelectInst::Create(Cond, OtherHandOfSubIsTrueVal ? Zero : NewSub,2695                             OtherHandOfSubIsTrueVal ? NewSub : Zero);2696      // Preserve prof metadata if any.2697      NewSel->copyMetadata(cast<Instruction>(*Select));2698      return NewSel;2699    };2700    if (Instruction *NewSel = SinkSubIntoSelect(2701            /*Select=*/Op0, /*OtherHandOfSub=*/Op1,2702            [Builder = &Builder, Op1](Value *OtherHandOfSelect) {2703              return Builder->CreateSub(OtherHandOfSelect,2704                                        /*OtherHandOfSub=*/Op1);2705            }))2706      return NewSel;2707    if (Instruction *NewSel = SinkSubIntoSelect(2708            /*Select=*/Op1, /*OtherHandOfSub=*/Op0,2709            [Builder = &Builder, Op0](Value *OtherHandOfSelect) {2710              return Builder->CreateSub(/*OtherHandOfSub=*/Op0,2711                                        OtherHandOfSelect);2712            }))2713      return NewSel;2714  }2715 2716  // (X - (X & Y))   -->   (X & ~Y)2717  if (match(Op1, m_c_And(m_Specific(Op0), m_Value(Y))) &&2718      (Op1->hasOneUse() || isa<Constant>(Y)))2719    return BinaryOperator::CreateAnd(2720        Op0, Builder.CreateNot(Y, Y->getName() + ".not"));2721 2722  // ~X - Min/Max(~X, Y) -> ~Min/Max(X, ~Y) - X2723  // ~X - Min/Max(Y, ~X) -> ~Min/Max(X, ~Y) - X2724  // Min/Max(~X, Y) - ~X -> X - ~Min/Max(X, ~Y)2725  // Min/Max(Y, ~X) - ~X -> X - ~Min/Max(X, ~Y)2726  // As long as Y is freely invertible, this will be neutral or a win.2727  // Note: We don't generate the inverse max/min, just create the 'not' of2728  // it and let other folds do the rest.2729  if (match(Op0, m_Not(m_Value(X))) &&2730      match(Op1, m_c_MaxOrMin(m_Specific(Op0), m_Value(Y))) &&2731      !Op0->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {2732    Value *Not = Builder.CreateNot(Op1);2733    return BinaryOperator::CreateSub(Not, X);2734  }2735  if (match(Op1, m_Not(m_Value(X))) &&2736      match(Op0, m_c_MaxOrMin(m_Specific(Op1), m_Value(Y))) &&2737      !Op1->hasNUsesOrMore(3) && isFreeToInvert(Y, Y->hasOneUse())) {2738    Value *Not = Builder.CreateNot(Op0);2739    return BinaryOperator::CreateSub(X, Not);2740  }2741 2742  // min(X+1, Y) - min(X, Y) --> zext X < Y2743  // Replacing a sub and at least one min with an icmp2744  // and a zext is a potential improvement.2745  if (match(Op0, m_c_SMin(m_NSWAddLike(m_Value(X), m_One()), m_Value(Y))) &&2746      match(Op1, m_c_SMin(m_Specific(X), m_Specific(Y))) &&2747      I.getType()->getScalarSizeInBits() != 1 &&2748      (Op0->hasOneUse() || Op1->hasOneUse())) {2749    Value *Cond = Builder.CreateICmpSLT(X, Y);2750    return new ZExtInst(Cond, I.getType());2751  }2752  if (match(Op0, m_c_UMin(m_NUWAddLike(m_Value(X), m_One()), m_Value(Y))) &&2753      match(Op1, m_c_UMin(m_Specific(X), m_Specific(Y))) &&2754      I.getType()->getScalarSizeInBits() != 1 &&2755      (Op0->hasOneUse() || Op1->hasOneUse())) {2756    Value *Cond = Builder.CreateICmpULT(X, Y);2757    return new ZExtInst(Cond, I.getType());2758  }2759 2760  // Optimize pointer differences into the same array into a size.  Consider:2761  //  &A[10] - &A[0]: we should compile this to "10".2762  Value *LHSOp, *RHSOp;2763  if (match(Op0, m_PtrToIntOrAddr(m_Value(LHSOp))) &&2764      match(Op1, m_PtrToIntOrAddr(m_Value(RHSOp))))2765    if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),2766                                               I.hasNoUnsignedWrap()))2767      return replaceInstUsesWith(I, Res);2768 2769  // trunc(p)-trunc(q) -> trunc(p-q)2770  if (match(Op0, m_Trunc(m_PtrToIntOrAddr(m_Value(LHSOp)))) &&2771      match(Op1, m_Trunc(m_PtrToIntOrAddr(m_Value(RHSOp)))))2772    if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType(),2773                                               /* IsNUW */ false))2774      return replaceInstUsesWith(I, Res);2775 2776  auto MatchSubOfZExtOfPtrToIntOrAddr = [&]() {2777    if (match(Op0, m_ZExt(m_PtrToIntSameSize(DL, m_Value(LHSOp)))) &&2778        match(Op1, m_ZExt(m_PtrToIntSameSize(DL, m_Value(RHSOp)))))2779      return true;2780    if (match(Op0, m_ZExt(m_PtrToAddr(m_Value(LHSOp)))) &&2781        match(Op1, m_ZExt(m_PtrToAddr(m_Value(RHSOp)))))2782      return true;2783    // Special case for non-canonical ptrtoint in constant expression,2784    // where the zext has been folded into the ptrtoint.2785    if (match(Op0, m_ZExt(m_PtrToIntSameSize(DL, m_Value(LHSOp)))) &&2786        match(Op1, m_PtrToInt(m_Value(RHSOp))))2787      return true;2788    return false;2789  };2790  if (MatchSubOfZExtOfPtrToIntOrAddr()) {2791    if (auto *GEP = dyn_cast<GEPOperator>(LHSOp)) {2792      if (GEP->getPointerOperand() == RHSOp) {2793        if (GEP->hasNoUnsignedWrap() || GEP->hasNoUnsignedSignedWrap()) {2794          Value *Offset = EmitGEPOffset(GEP);2795          Value *Res = GEP->hasNoUnsignedWrap()2796                           ? Builder.CreateZExt(2797                                 Offset, I.getType(), "",2798                                 /*IsNonNeg=*/GEP->hasNoUnsignedSignedWrap())2799                           : Builder.CreateSExt(Offset, I.getType());2800          return replaceInstUsesWith(I, Res);2801        }2802      }2803    }2804  }2805 2806  // Canonicalize a shifty way to code absolute value to the common pattern.2807  // There are 2 potential commuted variants.2808  // We're relying on the fact that we only do this transform when the shift has2809  // exactly 2 uses and the xor has exactly 1 use (otherwise, we might increase2810  // instructions).2811  Value *A;2812  const APInt *ShAmt;2813  Type *Ty = I.getType();2814  unsigned BitWidth = Ty->getScalarSizeInBits();2815  if (match(Op1, m_AShr(m_Value(A), m_APInt(ShAmt))) &&2816      Op1->hasNUses(2) && *ShAmt == BitWidth - 1 &&2817      match(Op0, m_OneUse(m_c_Xor(m_Specific(A), m_Specific(Op1))))) {2818    // B = ashr i32 A, 31 ; smear the sign bit2819    // sub (xor A, B), B  ; flip bits if negative and subtract -1 (add 1)2820    // --> (A < 0) ? -A : A2821    Value *IsNeg = Builder.CreateIsNeg(A);2822    // Copy the nsw flags from the sub to the negate.2823    Value *NegA = I.hasNoUnsignedWrap()2824                      ? Constant::getNullValue(A->getType())2825                      : Builder.CreateNeg(A, "", I.hasNoSignedWrap());2826    return SelectInst::Create(IsNeg, NegA, A);2827  }2828 2829  // If we are subtracting a low-bit masked subset of some value from an add2830  // of that same value with no low bits changed, that is clearing some low bits2831  // of the sum:2832  // sub (X + AddC), (X & AndC) --> and (X + AddC), ~AndC2833  const APInt *AddC, *AndC;2834  if (match(Op0, m_Add(m_Value(X), m_APInt(AddC))) &&2835      match(Op1, m_And(m_Specific(X), m_APInt(AndC)))) {2836    unsigned Cttz = AddC->countr_zero();2837    APInt HighMask(APInt::getHighBitsSet(BitWidth, BitWidth - Cttz));2838    if ((HighMask & *AndC).isZero())2839      return BinaryOperator::CreateAnd(Op0, ConstantInt::get(Ty, ~(*AndC)));2840  }2841 2842  if (Instruction *V =2843          canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))2844    return V;2845 2846  // X - usub.sat(X, Y) => umin(X, Y)2847  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::usub_sat>(m_Specific(Op0),2848                                                           m_Value(Y)))))2849    return replaceInstUsesWith(2850        I, Builder.CreateIntrinsic(Intrinsic::umin, {I.getType()}, {Op0, Y}));2851 2852  // umax(X, Op1) - Op1 --> usub.sat(X, Op1)2853  // TODO: The one-use restriction is not strictly necessary, but it may2854  //       require improving other pattern matching and/or codegen.2855  if (match(Op0, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op1)))))2856    return replaceInstUsesWith(2857        I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op1}));2858 2859  // Op0 - umin(X, Op0) --> usub.sat(Op0, X)2860  if (match(Op1, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op0)))))2861    return replaceInstUsesWith(2862        I, Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op0, X}));2863 2864  // Op0 - umax(X, Op0) --> 0 - usub.sat(X, Op0)2865  if (match(Op1, m_OneUse(m_c_UMax(m_Value(X), m_Specific(Op0))))) {2866    Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {X, Op0});2867    return BinaryOperator::CreateNeg(USub);2868  }2869 2870  // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X)2871  if (match(Op0, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op1))))) {2872    Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X});2873    return BinaryOperator::CreateNeg(USub);2874  }2875 2876  // C - ctpop(X) => ctpop(~X) if C is bitwidth2877  if (match(Op0, m_SpecificInt(BitWidth)) &&2878      match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))2879    return replaceInstUsesWith(2880        I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},2881                                   {Builder.CreateNot(X)}));2882 2883  // Reduce multiplies for difference-of-squares by factoring:2884  // (X * X) - (Y * Y) --> (X + Y) * (X - Y)2885  if (match(Op0, m_OneUse(m_Mul(m_Value(X), m_Deferred(X)))) &&2886      match(Op1, m_OneUse(m_Mul(m_Value(Y), m_Deferred(Y))))) {2887    auto *OBO0 = cast<OverflowingBinaryOperator>(Op0);2888    auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);2889    bool PropagateNSW = I.hasNoSignedWrap() && OBO0->hasNoSignedWrap() &&2890                        OBO1->hasNoSignedWrap() && BitWidth > 2;2891    bool PropagateNUW = I.hasNoUnsignedWrap() && OBO0->hasNoUnsignedWrap() &&2892                        OBO1->hasNoUnsignedWrap() && BitWidth > 1;2893    Value *Add = Builder.CreateAdd(X, Y, "add", PropagateNUW, PropagateNSW);2894    Value *Sub = Builder.CreateSub(X, Y, "sub", PropagateNUW, PropagateNSW);2895    Value *Mul = Builder.CreateMul(Add, Sub, "", PropagateNUW, PropagateNSW);2896    return replaceInstUsesWith(I, Mul);2897  }2898 2899  // max(X,Y) nsw/nuw - min(X,Y) --> abs(X nsw - Y)2900  if (match(Op0, m_OneUse(m_c_SMax(m_Value(X), m_Value(Y)))) &&2901      match(Op1, m_OneUse(m_c_SMin(m_Specific(X), m_Specific(Y))))) {2902    if (I.hasNoUnsignedWrap() || I.hasNoSignedWrap()) {2903      Value *Sub =2904          Builder.CreateSub(X, Y, "sub", /*HasNUW=*/false, /*HasNSW=*/true);2905      Value *Call =2906          Builder.CreateBinaryIntrinsic(Intrinsic::abs, Sub, Builder.getTrue());2907      return replaceInstUsesWith(I, Call);2908    }2909  }2910 2911  if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))2912    return Res;2913 2914  // (sub (sext (add nsw (X, Y)), sext (X))) --> (sext (Y))2915  if (match(Op1, m_SExtLike(m_Value(X))) &&2916      match(Op0, m_SExtLike(m_c_NSWAdd(m_Specific(X), m_Value(Y))))) {2917    Value *SExtY = Builder.CreateSExt(Y, I.getType());2918    return replaceInstUsesWith(I, SExtY);2919  }2920 2921  // (sub[ nsw] (sext (add nsw (X, Y)), sext (add nsw (X, Z)))) -->2922  // --> (sub[ nsw] (sext (Y), sext (Z)))2923  {2924    Value *Z, *Add0, *Add1;2925    if (match(Op0, m_SExtLike(m_Value(Add0))) &&2926        match(Op1, m_SExtLike(m_Value(Add1))) &&2927        ((match(Add0, m_NSWAdd(m_Value(X), m_Value(Y))) &&2928          match(Add1, m_c_NSWAdd(m_Specific(X), m_Value(Z)))) ||2929         (match(Add0, m_NSWAdd(m_Value(Y), m_Value(X))) &&2930          match(Add1, m_c_NSWAdd(m_Specific(X), m_Value(Z)))))) {2931      unsigned NumOfNewInstrs = 0;2932      // Non-constant Y, Z require new SExt.2933      NumOfNewInstrs += !isa<Constant>(Y) ? 1 : 0;2934      NumOfNewInstrs += !isa<Constant>(Z) ? 1 : 0;2935      // Check if we can trade some of the old instructions for the new ones.2936      unsigned NumOfDeadInstrs = 0;2937      if (Op0->hasOneUse()) {2938        // If Op0 (sext) has multiple uses, then we keep it2939        // and the add that it uses, otherwise, we can remove2940        // the sext and probably the add (depending on the number of its uses).2941        ++NumOfDeadInstrs;2942        NumOfDeadInstrs += Add0->hasOneUse() ? 1 : 0;2943      }2944      if (Op1->hasOneUse()) {2945        ++NumOfDeadInstrs;2946        NumOfDeadInstrs += Add1->hasOneUse() ? 1 : 0;2947      }2948      if (NumOfDeadInstrs >= NumOfNewInstrs) {2949        Value *SExtY = Builder.CreateSExt(Y, I.getType());2950        Value *SExtZ = Builder.CreateSExt(Z, I.getType());2951        Value *Sub = Builder.CreateSub(SExtY, SExtZ, "",2952                                       /*HasNUW=*/false,2953                                       /*HasNSW=*/I.hasNoSignedWrap());2954        return replaceInstUsesWith(I, Sub);2955      }2956    }2957  }2958 2959  return TryToNarrowDeduceFlags();2960}2961 2962/// This eliminates floating-point negation in either 'fneg(X)' or2963/// 'fsub(-0.0, X)' form by combining into a constant operand.2964static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) {2965  // This is limited with one-use because fneg is assumed better for2966  // reassociation and cheaper in codegen than fmul/fdiv.2967  // TODO: Should the m_OneUse restriction be removed?2968  Instruction *FNegOp;2969  if (!match(&I, m_FNeg(m_OneUse(m_Instruction(FNegOp)))))2970    return nullptr;2971 2972  Value *X;2973  Constant *C;2974 2975  // Fold negation into constant operand.2976  // -(X * C) --> X * (-C)2977  if (match(FNegOp, m_FMul(m_Value(X), m_Constant(C))))2978    if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) {2979      FastMathFlags FNegF = I.getFastMathFlags();2980      FastMathFlags OpF = FNegOp->getFastMathFlags();2981      FastMathFlags FMF = FastMathFlags::unionValue(FNegF, OpF) |2982                          FastMathFlags::intersectRewrite(FNegF, OpF);2983      FMF.setNoInfs(FNegF.noInfs() && OpF.noInfs());2984      return BinaryOperator::CreateFMulFMF(X, NegC, FMF);2985    }2986  // -(X / C) --> X / (-C)2987  if (match(FNegOp, m_FDiv(m_Value(X), m_Constant(C))))2988    if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))2989      return BinaryOperator::CreateFDivFMF(X, NegC, &I);2990  // -(C / X) --> (-C) / X2991  if (match(FNegOp, m_FDiv(m_Constant(C), m_Value(X))))2992    if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)) {2993      Instruction *FDiv = BinaryOperator::CreateFDivFMF(NegC, X, &I);2994 2995      // Intersect 'nsz' and 'ninf' because those special value exceptions may2996      // not apply to the fdiv. Everything else propagates from the fneg.2997      // TODO: We could propagate nsz/ninf from fdiv alone?2998      FastMathFlags FMF = I.getFastMathFlags();2999      FastMathFlags OpFMF = FNegOp->getFastMathFlags();3000      FDiv->setHasNoSignedZeros(FMF.noSignedZeros() && OpFMF.noSignedZeros());3001      FDiv->setHasNoInfs(FMF.noInfs() && OpFMF.noInfs());3002      return FDiv;3003    }3004  // With NSZ [ counter-example with -0.0: -(-0.0 + 0.0) != 0.0 + -0.0 ]:3005  // -(X + C) --> -X + -C --> -C - X3006  if (I.hasNoSignedZeros() && match(FNegOp, m_FAdd(m_Value(X), m_Constant(C))))3007    if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))3008      return BinaryOperator::CreateFSubFMF(NegC, X, &I);3009 3010  return nullptr;3011}3012 3013Instruction *InstCombinerImpl::hoistFNegAboveFMulFDiv(Value *FNegOp,3014                                                      Instruction &FMFSource) {3015  Value *X, *Y;3016  if (match(FNegOp, m_FMul(m_Value(X), m_Value(Y)))) {3017    // Push into RHS which is more likely to simplify (const or another fneg).3018    // FIXME: It would be better to invert the transform.3019    return cast<Instruction>(Builder.CreateFMulFMF(3020        X, Builder.CreateFNegFMF(Y, &FMFSource), &FMFSource));3021  }3022 3023  if (match(FNegOp, m_FDiv(m_Value(X), m_Value(Y)))) {3024    return cast<Instruction>(Builder.CreateFDivFMF(3025        Builder.CreateFNegFMF(X, &FMFSource), Y, &FMFSource));3026  }3027 3028  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(FNegOp)) {3029    // Make sure to preserve flags and metadata on the call.3030    if (II->getIntrinsicID() == Intrinsic::ldexp) {3031      FastMathFlags FMF = FMFSource.getFastMathFlags() | II->getFastMathFlags();3032      CallInst *New =3033          Builder.CreateCall(II->getCalledFunction(),3034                             {Builder.CreateFNegFMF(II->getArgOperand(0), FMF),3035                              II->getArgOperand(1)});3036      New->setFastMathFlags(FMF);3037      New->copyMetadata(*II);3038      return New;3039    }3040  }3041 3042  return nullptr;3043}3044 3045Instruction *InstCombinerImpl::visitFNeg(UnaryOperator &I) {3046  Value *Op = I.getOperand(0);3047 3048  if (Value *V = simplifyFNegInst(Op, I.getFastMathFlags(),3049                                  getSimplifyQuery().getWithInstruction(&I)))3050    return replaceInstUsesWith(I, V);3051 3052  if (Instruction *X = foldFNegIntoConstant(I, DL))3053    return X;3054 3055  Value *X, *Y;3056 3057  // If we can ignore the sign of zeros: -(X - Y) --> (Y - X)3058  if (I.hasNoSignedZeros() &&3059      match(Op, m_OneUse(m_FSub(m_Value(X), m_Value(Y)))))3060    return BinaryOperator::CreateFSubFMF(Y, X, &I);3061 3062  Value *OneUse;3063  if (!match(Op, m_OneUse(m_Value(OneUse))))3064    return nullptr;3065 3066  if (Instruction *R = hoistFNegAboveFMulFDiv(OneUse, I))3067    return replaceInstUsesWith(I, R);3068 3069  // Try to eliminate fneg if at least 1 arm of the select is negated.3070  Value *Cond;3071  if (match(OneUse, m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))) {3072    // Unlike most transforms, this one is not safe to propagate nsz unless3073    // it is present on the original select. We union the flags from the select3074    // and fneg and then remove nsz if needed.3075    auto propagateSelectFMF = [&](SelectInst *S, bool CommonOperand) {3076      S->copyFastMathFlags(&I);3077      if (auto *OldSel = dyn_cast<SelectInst>(Op)) {3078        FastMathFlags FMF = I.getFastMathFlags() | OldSel->getFastMathFlags();3079        S->setFastMathFlags(FMF);3080        if (!OldSel->hasNoSignedZeros() && !CommonOperand &&3081            !isGuaranteedNotToBeUndefOrPoison(OldSel->getCondition()))3082          S->setHasNoSignedZeros(false);3083      }3084    };3085    // -(Cond ? -P : Y) --> Cond ? P : -Y3086    Value *P;3087    if (match(X, m_FNeg(m_Value(P)))) {3088      Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");3089      SelectInst *NewSel = SelectInst::Create(Cond, P, NegY);3090      propagateSelectFMF(NewSel, P == Y);3091      return NewSel;3092    }3093    // -(Cond ? X : -P) --> Cond ? -X : P3094    if (match(Y, m_FNeg(m_Value(P)))) {3095      Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");3096      SelectInst *NewSel = SelectInst::Create(Cond, NegX, P);3097      propagateSelectFMF(NewSel, P == X);3098      return NewSel;3099    }3100 3101    // -(Cond ? X : C) --> Cond ? -X : -C3102    // -(Cond ? C : Y) --> Cond ? -C : -Y3103    if (match(X, m_ImmConstant()) || match(Y, m_ImmConstant())) {3104      Value *NegX = Builder.CreateFNegFMF(X, &I, X->getName() + ".neg");3105      Value *NegY = Builder.CreateFNegFMF(Y, &I, Y->getName() + ".neg");3106      SelectInst *NewSel = SelectInst::Create(Cond, NegX, NegY);3107      propagateSelectFMF(NewSel, /*CommonOperand=*/true);3108      return NewSel;3109    }3110  }3111 3112  // fneg (copysign x, y) -> copysign x, (fneg y)3113  if (match(OneUse, m_CopySign(m_Value(X), m_Value(Y)))) {3114    // The source copysign has an additional value input, so we can't propagate3115    // flags the copysign doesn't also have.3116    FastMathFlags FMF = I.getFastMathFlags();3117    FMF &= cast<FPMathOperator>(OneUse)->getFastMathFlags();3118    Value *NegY = Builder.CreateFNegFMF(Y, FMF);3119    Value *NewCopySign = Builder.CreateCopySign(X, NegY, FMF);3120    return replaceInstUsesWith(I, NewCopySign);3121  }3122 3123  // fneg (shuffle x, Mask) --> shuffle (fneg x), Mask3124  ArrayRef<int> Mask;3125  if (match(OneUse, m_Shuffle(m_Value(X), m_Poison(), m_Mask(Mask))))3126    return new ShuffleVectorInst(Builder.CreateFNegFMF(X, &I), Mask);3127 3128  // fneg (reverse x) --> reverse (fneg x)3129  if (match(OneUse, m_VecReverse(m_Value(X)))) {3130    Value *Reverse = Builder.CreateVectorReverse(Builder.CreateFNegFMF(X, &I));3131    return replaceInstUsesWith(I, Reverse);3132  }3133 3134  return nullptr;3135}3136 3137Instruction *InstCombinerImpl::visitFSub(BinaryOperator &I) {3138  if (Value *V = simplifyFSubInst(I.getOperand(0), I.getOperand(1),3139                                  I.getFastMathFlags(),3140                                  getSimplifyQuery().getWithInstruction(&I)))3141    return replaceInstUsesWith(I, V);3142 3143  if (Instruction *X = foldVectorBinop(I))3144    return X;3145 3146  if (Instruction *Phi = foldBinopWithPhiOperands(I))3147    return Phi;3148 3149  // Subtraction from -0.0 is the canonical form of fneg.3150  // fsub -0.0, X ==> fneg X3151  // fsub nsz 0.0, X ==> fneg nsz X3152  //3153  // FIXME This matcher does not respect FTZ or DAZ yet:3154  // fsub -0.0, Denorm ==> +-03155  // fneg Denorm ==> -Denorm3156  Value *Op;3157  if (match(&I, m_FNeg(m_Value(Op))))3158    return UnaryOperator::CreateFNegFMF(Op, &I);3159 3160  if (Instruction *X = foldFNegIntoConstant(I, DL))3161    return X;3162 3163  if (Instruction *R = foldFBinOpOfIntCasts(I))3164    return R;3165 3166  Value *X, *Y;3167  Constant *C;3168 3169  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);3170  // If Op0 is not -0.0 or we can ignore -0.0: Z - (X - Y) --> Z + (Y - X)3171  // Canonicalize to fadd to make analysis easier.3172  // This can also help codegen because fadd is commutative.3173  // Note that if this fsub was really an fneg, the fadd with -0.0 will get3174  // killed later. We still limit that particular transform with 'hasOneUse'3175  // because an fneg is assumed better/cheaper than a generic fsub.3176  if (I.hasNoSignedZeros() ||3177      cannotBeNegativeZero(Op0, getSimplifyQuery().getWithInstruction(&I))) {3178    if (match(Op1, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {3179      Value *NewSub = Builder.CreateFSubFMF(Y, X, &I);3180      return BinaryOperator::CreateFAddFMF(Op0, NewSub, &I);3181    }3182  }3183 3184  // (-X) - Op1 --> -(X + Op1)3185  if (I.hasNoSignedZeros() && !isa<ConstantExpr>(Op0) &&3186      match(Op0, m_OneUse(m_FNeg(m_Value(X))))) {3187    Value *FAdd = Builder.CreateFAddFMF(X, Op1, &I);3188    return UnaryOperator::CreateFNegFMF(FAdd, &I);3189  }3190 3191  if (isa<Constant>(Op0))3192    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))3193      if (Instruction *NV = FoldOpIntoSelect(I, SI))3194        return NV;3195 3196  // X - C --> X + (-C)3197  // But don't transform constant expressions because there's an inverse fold3198  // for X + (-Y) --> X - Y.3199  if (match(Op1, m_ImmConstant(C)))3200    if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))3201      return BinaryOperator::CreateFAddFMF(Op0, NegC, &I);3202 3203  // X - (-Y) --> X + Y3204  if (match(Op1, m_FNeg(m_Value(Y))))3205    return BinaryOperator::CreateFAddFMF(Op0, Y, &I);3206 3207  // Similar to above, but look through a cast of the negated value:3208  // X - (fptrunc(-Y)) --> X + fptrunc(Y)3209  Type *Ty = I.getType();3210  if (match(Op1, m_OneUse(m_FPTrunc(m_FNeg(m_Value(Y))))))3211    return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPTrunc(Y, Ty), &I);3212 3213  // X - (fpext(-Y)) --> X + fpext(Y)3214  if (match(Op1, m_OneUse(m_FPExt(m_FNeg(m_Value(Y))))))3215    return BinaryOperator::CreateFAddFMF(Op0, Builder.CreateFPExt(Y, Ty), &I);3216 3217  // Similar to above, but look through fmul/fdiv of the negated value:3218  // Op0 - (-X * Y) --> Op0 + (X * Y)3219  // Op0 - (Y * -X) --> Op0 + (X * Y)3220  if (match(Op1, m_OneUse(m_c_FMul(m_FNeg(m_Value(X)), m_Value(Y))))) {3221    Value *FMul = Builder.CreateFMulFMF(X, Y, &I);3222    return BinaryOperator::CreateFAddFMF(Op0, FMul, &I);3223  }3224  // Op0 - (-X / Y) --> Op0 + (X / Y)3225  // Op0 - (X / -Y) --> Op0 + (X / Y)3226  if (match(Op1, m_OneUse(m_FDiv(m_FNeg(m_Value(X)), m_Value(Y)))) ||3227      match(Op1, m_OneUse(m_FDiv(m_Value(X), m_FNeg(m_Value(Y)))))) {3228    Value *FDiv = Builder.CreateFDivFMF(X, Y, &I);3229    return BinaryOperator::CreateFAddFMF(Op0, FDiv, &I);3230  }3231 3232  // Handle special cases for FSub with selects feeding the operation3233  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))3234    return replaceInstUsesWith(I, V);3235 3236  if (I.hasAllowReassoc() && I.hasNoSignedZeros()) {3237    // (Y - X) - Y --> -X3238    if (match(Op0, m_FSub(m_Specific(Op1), m_Value(X))))3239      return UnaryOperator::CreateFNegFMF(X, &I);3240 3241    // Y - (X + Y) --> -X3242    // Y - (Y + X) --> -X3243    if (match(Op1, m_c_FAdd(m_Specific(Op0), m_Value(X))))3244      return UnaryOperator::CreateFNegFMF(X, &I);3245 3246    // (X * C) - X --> X * (C - 1.0)3247    if (match(Op0, m_FMul(m_Specific(Op1), m_Constant(C)))) {3248      if (Constant *CSubOne = ConstantFoldBinaryOpOperands(3249              Instruction::FSub, C, ConstantFP::get(Ty, 1.0), DL))3250        return BinaryOperator::CreateFMulFMF(Op1, CSubOne, &I);3251    }3252    // X - (X * C) --> X * (1.0 - C)3253    if (match(Op1, m_FMul(m_Specific(Op0), m_Constant(C)))) {3254      if (Constant *OneSubC = ConstantFoldBinaryOpOperands(3255              Instruction::FSub, ConstantFP::get(Ty, 1.0), C, DL))3256        return BinaryOperator::CreateFMulFMF(Op0, OneSubC, &I);3257    }3258 3259    // Reassociate fsub/fadd sequences to create more fadd instructions and3260    // reduce dependency chains:3261    // ((X - Y) + Z) - Op1 --> (X + Z) - (Y + Op1)3262    Value *Z;3263    if (match(Op0, m_OneUse(m_c_FAdd(m_OneUse(m_FSub(m_Value(X), m_Value(Y))),3264                                     m_Value(Z))))) {3265      Value *XZ = Builder.CreateFAddFMF(X, Z, &I);3266      Value *YW = Builder.CreateFAddFMF(Y, Op1, &I);3267      return BinaryOperator::CreateFSubFMF(XZ, YW, &I);3268    }3269 3270    auto m_FaddRdx = [](Value *&Sum, Value *&Vec) {3271      return m_OneUse(m_Intrinsic<Intrinsic::vector_reduce_fadd>(m_Value(Sum),3272                                                                 m_Value(Vec)));3273    };3274    Value *A0, *A1, *V0, *V1;3275    if (match(Op0, m_FaddRdx(A0, V0)) && match(Op1, m_FaddRdx(A1, V1)) &&3276        V0->getType() == V1->getType()) {3277      // Difference of sums is sum of differences:3278      // add_rdx(A0, V0) - add_rdx(A1, V1) --> add_rdx(A0, V0 - V1) - A13279      Value *Sub = Builder.CreateFSubFMF(V0, V1, &I);3280      Value *Rdx = Builder.CreateIntrinsic(Intrinsic::vector_reduce_fadd,3281                                           {Sub->getType()}, {A0, Sub}, &I);3282      return BinaryOperator::CreateFSubFMF(Rdx, A1, &I);3283    }3284 3285    if (Instruction *F = factorizeFAddFSub(I, Builder))3286      return F;3287 3288    // TODO: This performs reassociative folds for FP ops. Some fraction of the3289    // functionality has been subsumed by simple pattern matching here and in3290    // InstSimplify. We should let a dedicated reassociation pass handle more3291    // complex pattern matching and remove this from InstCombine.3292    if (Value *V = FAddCombine(Builder).simplify(&I))3293      return replaceInstUsesWith(I, V);3294 3295    // (X - Y) - Op1 --> X - (Y + Op1)3296    if (match(Op0, m_OneUse(m_FSub(m_Value(X), m_Value(Y))))) {3297      Value *FAdd = Builder.CreateFAddFMF(Y, Op1, &I);3298      return BinaryOperator::CreateFSubFMF(X, FAdd, &I);3299    }3300  }3301 3302  return nullptr;3303}3304