InstCombineAddSub.cpp [plain text]
#include "InstCombine.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;
#define DEBUG_TYPE "instcombine"
namespace {
class FAddendCoef {
public:
FAddendCoef() : IsFp(false), BufHasFpVal(false), IntVal(0) {}
~FAddendCoef();
void set(short C) {
assert(!insaneIntVal(C) && "Insane coefficient");
IsFp = false; IntVal = C;
}
void set(const APFloat& C);
void negate();
bool isZero() const { return isInt() ? !IntVal : getFpVal().isZero(); }
Value *getValue(Type *) const;
void operator=(const FAddendCoef &A);
void operator+=(const FAddendCoef &A);
void operator-=(const FAddendCoef &A);
void operator*=(const FAddendCoef &S);
bool isOne() const { return isInt() && IntVal == 1; }
bool isTwo() const { return isInt() && IntVal == 2; }
bool isMinusOne() const { return isInt() && IntVal == -1; }
bool isMinusTwo() const { return isInt() && IntVal == -2; }
private:
bool insaneIntVal(int V) { return V > 4 || V < -4; }
APFloat *getFpValPtr(void)
{ return reinterpret_cast<APFloat*>(&FpValBuf.buffer[0]); }
const APFloat *getFpValPtr(void) const
{ return reinterpret_cast<const APFloat*>(&FpValBuf.buffer[0]); }
const APFloat &getFpVal(void) const {
assert(IsFp && BufHasFpVal && "Incorret state");
return *getFpValPtr();
}
APFloat &getFpVal(void) {
assert(IsFp && BufHasFpVal && "Incorret state");
return *getFpValPtr();
}
bool isInt() const { return !IsFp; }
void convertToFpType(const fltSemantics &Sem);
APFloat createAPFloatFromInt(const fltSemantics &Sem, int Val);
private:
bool IsFp;
bool BufHasFpVal;
short IntVal;
AlignedCharArrayUnion<APFloat> FpValBuf;
};
class FAddend {
public:
FAddend() { Val = nullptr; }
Value *getSymVal (void) const { return Val; }
const FAddendCoef &getCoef(void) const { return Coeff; }
bool isConstant() const { return Val == nullptr; }
bool isZero() const { return Coeff.isZero(); }
void set(short Coefficient, Value *V) { Coeff.set(Coefficient), Val = V; }
void set(const APFloat& Coefficient, Value *V)
{ Coeff.set(Coefficient); Val = V; }
void set(const ConstantFP* Coefficient, Value *V)
{ Coeff.set(Coefficient->getValueAPF()); Val = V; }
void negate() { Coeff.negate(); }
static unsigned drillValueDownOneStep(Value* V, FAddend &A0, FAddend &A1);
unsigned drillAddendDownOneStep(FAddend &Addend0, FAddend &Addend1) const;
void operator+=(const FAddend &T) {
assert((Val == T.Val) && "Symbolic-values disagree");
Coeff += T.Coeff;
}
private:
void Scale(const FAddendCoef& ScaleAmt) { Coeff *= ScaleAmt; }
Value *Val;
FAddendCoef Coeff;
};
class FAddCombine {
public:
FAddCombine(InstCombiner::BuilderTy *B) : Builder(B), Instr(nullptr) {}
Value *simplify(Instruction *FAdd);
private:
typedef SmallVector<const FAddend*, 4> AddendVect;
Value *simplifyFAdd(AddendVect& V, unsigned InstrQuota);
Value *performFactorization(Instruction *I);
Value *createAddendVal(const FAddend &A, bool& NeedNeg);
unsigned calcInstrNumber(const AddendVect& Vect);
Value *createFSub(Value *Opnd0, Value *Opnd1);
Value *createFAdd(Value *Opnd0, Value *Opnd1);
Value *createFMul(Value *Opnd0, Value *Opnd1);
Value *createFDiv(Value *Opnd0, Value *Opnd1);
Value *createFNeg(Value *V);
Value *createNaryFAdd(const AddendVect& Opnds, unsigned InstrQuota);
void createInstPostProc(Instruction *NewInst, bool NoNumber = false);
InstCombiner::BuilderTy *Builder;
Instruction *Instr;
private:
#ifndef NDEBUG
unsigned CreateInstrNum;
void initCreateInstNum() { CreateInstrNum = 0; }
void incCreateInstNum() { CreateInstrNum++; }
#else
void initCreateInstNum() {}
void incCreateInstNum() {}
#endif
};
}
FAddendCoef::~FAddendCoef() {
if (BufHasFpVal)
getFpValPtr()->~APFloat();
}
void FAddendCoef::set(const APFloat& C) {
APFloat *P = getFpValPtr();
if (isInt()) {
new(P) APFloat(C);
} else
*P = C;
IsFp = BufHasFpVal = true;
}
void FAddendCoef::convertToFpType(const fltSemantics &Sem) {
if (!isInt())
return;
APFloat *P = getFpValPtr();
if (IntVal > 0)
new(P) APFloat(Sem, IntVal);
else {
new(P) APFloat(Sem, 0 - IntVal);
P->changeSign();
}
IsFp = BufHasFpVal = true;
}
APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) {
if (Val >= 0)
return APFloat(Sem, Val);
APFloat T(Sem, 0 - Val);
T.changeSign();
return T;
}
void FAddendCoef::operator=(const FAddendCoef &That) {
if (That.isInt())
set(That.IntVal);
else
set(That.getFpVal());
}
void FAddendCoef::operator+=(const FAddendCoef &That) {
enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
if (isInt() == That.isInt()) {
if (isInt())
IntVal += That.IntVal;
else
getFpVal().add(That.getFpVal(), RndMode);
return;
}
if (isInt()) {
const APFloat &T = That.getFpVal();
convertToFpType(T.getSemantics());
getFpVal().add(T, RndMode);
return;
}
APFloat &T = getFpVal();
T.add(createAPFloatFromInt(T.getSemantics(), That.IntVal), RndMode);
}
void FAddendCoef::operator-=(const FAddendCoef &That) {
enum APFloat::roundingMode RndMode = APFloat::rmNearestTiesToEven;
if (isInt() == That.isInt()) {
if (isInt())
IntVal -= That.IntVal;
else
getFpVal().subtract(That.getFpVal(), RndMode);
return;
}
if (isInt()) {
const APFloat &T = That.getFpVal();
convertToFpType(T.getSemantics());
getFpVal().subtract(T, RndMode);
return;
}
APFloat &T = getFpVal();
T.subtract(createAPFloatFromInt(T.getSemantics(), IntVal), RndMode);
}
void FAddendCoef::operator*=(const FAddendCoef &That) {
if (That.isOne())
return;
if (That.isMinusOne()) {
negate();
return;
}
if (isInt() && That.isInt()) {
int Res = IntVal * (int)That.IntVal;
assert(!insaneIntVal(Res) && "Insane int value");
IntVal = Res;
return;
}
const fltSemantics &Semantic =
isInt() ? That.getFpVal().getSemantics() : getFpVal().getSemantics();
if (isInt())
convertToFpType(Semantic);
APFloat &F0 = getFpVal();
if (That.isInt())
F0.multiply(createAPFloatFromInt(Semantic, That.IntVal),
APFloat::rmNearestTiesToEven);
else
F0.multiply(That.getFpVal(), APFloat::rmNearestTiesToEven);
return;
}
void FAddendCoef::negate() {
if (isInt())
IntVal = 0 - IntVal;
else
getFpVal().changeSign();
}
Value *FAddendCoef::getValue(Type *Ty) const {
return isInt() ?
ConstantFP::get(Ty, float(IntVal)) :
ConstantFP::get(Ty->getContext(), getFpVal());
}
unsigned FAddend::drillValueDownOneStep
(Value *Val, FAddend &Addend0, FAddend &Addend1) {
Instruction *I = nullptr;
if (!Val || !(I = dyn_cast<Instruction>(Val)))
return 0;
unsigned Opcode = I->getOpcode();
if (Opcode == Instruction::FAdd || Opcode == Instruction::FSub) {
ConstantFP *C0, *C1;
Value *Opnd0 = I->getOperand(0);
Value *Opnd1 = I->getOperand(1);
if ((C0 = dyn_cast<ConstantFP>(Opnd0)) && C0->isZero())
Opnd0 = nullptr;
if ((C1 = dyn_cast<ConstantFP>(Opnd1)) && C1->isZero())
Opnd1 = nullptr;
if (Opnd0) {
if (!C0)
Addend0.set(1, Opnd0);
else
Addend0.set(C0, nullptr);
}
if (Opnd1) {
FAddend &Addend = Opnd0 ? Addend1 : Addend0;
if (!C1)
Addend.set(1, Opnd1);
else
Addend.set(C1, nullptr);
if (Opcode == Instruction::FSub)
Addend.negate();
}
if (Opnd0 || Opnd1)
return Opnd0 && Opnd1 ? 2 : 1;
Addend0.set(APFloat(C0->getValueAPF().getSemantics()), nullptr);
return 1;
}
if (I->getOpcode() == Instruction::FMul) {
Value *V0 = I->getOperand(0);
Value *V1 = I->getOperand(1);
if (ConstantFP *C = dyn_cast<ConstantFP>(V0)) {
Addend0.set(C, V1);
return 1;
}
if (ConstantFP *C = dyn_cast<ConstantFP>(V1)) {
Addend0.set(C, V0);
return 1;
}
}
return 0;
}
unsigned FAddend::drillAddendDownOneStep
(FAddend &Addend0, FAddend &Addend1) const {
if (isConstant())
return 0;
unsigned BreakNum = FAddend::drillValueDownOneStep(Val, Addend0, Addend1);
if (!BreakNum || Coeff.isOne())
return BreakNum;
Addend0.Scale(Coeff);
if (BreakNum == 2)
Addend1.Scale(Coeff);
return BreakNum;
}
Value *FAddCombine::performFactorization(Instruction *I) {
assert((I->getOpcode() == Instruction::FAdd ||
I->getOpcode() == Instruction::FSub) && "Expect add/sub");
Instruction *I0 = dyn_cast<Instruction>(I->getOperand(0));
Instruction *I1 = dyn_cast<Instruction>(I->getOperand(1));
if (!I0 || !I1 || I0->getOpcode() != I1->getOpcode())
return nullptr;
bool isMpy = false;
if (I0->getOpcode() == Instruction::FMul)
isMpy = true;
else if (I0->getOpcode() != Instruction::FDiv)
return nullptr;
Value *Opnd0_0 = I0->getOperand(0);
Value *Opnd0_1 = I0->getOperand(1);
Value *Opnd1_0 = I1->getOperand(0);
Value *Opnd1_1 = I1->getOperand(1);
Value *Factor = nullptr;
Value *AddSub0 = nullptr, *AddSub1 = nullptr;
if (isMpy) {
if (Opnd0_0 == Opnd1_0 || Opnd0_0 == Opnd1_1)
Factor = Opnd0_0;
else if (Opnd0_1 == Opnd1_0 || Opnd0_1 == Opnd1_1)
Factor = Opnd0_1;
if (Factor) {
AddSub0 = (Factor == Opnd0_0) ? Opnd0_1 : Opnd0_0;
AddSub1 = (Factor == Opnd1_0) ? Opnd1_1 : Opnd1_0;
}
} else if (Opnd0_1 == Opnd1_1) {
Factor = Opnd0_1;
AddSub0 = Opnd0_0;
AddSub1 = Opnd1_0;
}
if (!Factor)
return nullptr;
FastMathFlags Flags;
Flags.setUnsafeAlgebra();
if (I0) Flags &= I->getFastMathFlags();
if (I1) Flags &= I->getFastMathFlags();
Value *NewAddSub = (I->getOpcode() == Instruction::FAdd) ?
createFAdd(AddSub0, AddSub1) :
createFSub(AddSub0, AddSub1);
if (ConstantFP *CFP = dyn_cast<ConstantFP>(NewAddSub)) {
const APFloat &F = CFP->getValueAPF();
if (!F.isNormal())
return nullptr;
} else if (Instruction *II = dyn_cast<Instruction>(NewAddSub))
II->setFastMathFlags(Flags);
if (isMpy) {
Value *RI = createFMul(Factor, NewAddSub);
if (Instruction *II = dyn_cast<Instruction>(RI))
II->setFastMathFlags(Flags);
return RI;
}
Value *RI = createFDiv(NewAddSub, Factor);
if (Instruction *II = dyn_cast<Instruction>(RI))
II->setFastMathFlags(Flags);
return RI;
}
Value *FAddCombine::simplify(Instruction *I) {
assert(I->hasUnsafeAlgebra() && "Should be in unsafe mode");
if (I->getType()->isVectorTy())
return nullptr;
assert((I->getOpcode() == Instruction::FAdd ||
I->getOpcode() == Instruction::FSub) && "Expect add/sub");
Instr = I;
FAddend Opnd0, Opnd1, Opnd0_0, Opnd0_1, Opnd1_0, Opnd1_1;
unsigned OpndNum = FAddend::drillValueDownOneStep(I, Opnd0, Opnd1);
unsigned Opnd0_ExpNum = 0;
unsigned Opnd1_ExpNum = 0;
if (!Opnd0.isConstant())
Opnd0_ExpNum = Opnd0.drillAddendDownOneStep(Opnd0_0, Opnd0_1);
if (OpndNum == 2 && !Opnd1.isConstant())
Opnd1_ExpNum = Opnd1.drillAddendDownOneStep(Opnd1_0, Opnd1_1);
if (Opnd0_ExpNum && Opnd1_ExpNum) {
AddendVect AllOpnds;
AllOpnds.push_back(&Opnd0_0);
AllOpnds.push_back(&Opnd1_0);
if (Opnd0_ExpNum == 2)
AllOpnds.push_back(&Opnd0_1);
if (Opnd1_ExpNum == 2)
AllOpnds.push_back(&Opnd1_1);
unsigned InstQuota = 0;
Value *V0 = I->getOperand(0);
Value *V1 = I->getOperand(1);
InstQuota = ((!isa<Constant>(V0) && V0->hasOneUse()) &&
(!isa<Constant>(V1) && V1->hasOneUse())) ? 2 : 1;
if (Value *R = simplifyFAdd(AllOpnds, InstQuota))
return R;
}
if (OpndNum != 2) {
const FAddendCoef &CE = Opnd0.getCoef();
return CE.isOne() ? Opnd0.getSymVal() : nullptr;
}
if (Opnd1_ExpNum) {
AddendVect AllOpnds;
AllOpnds.push_back(&Opnd0);
AllOpnds.push_back(&Opnd1_0);
if (Opnd1_ExpNum == 2)
AllOpnds.push_back(&Opnd1_1);
if (Value *R = simplifyFAdd(AllOpnds, 1))
return R;
}
if (Opnd0_ExpNum) {
AddendVect AllOpnds;
AllOpnds.push_back(&Opnd1);
AllOpnds.push_back(&Opnd0_0);
if (Opnd0_ExpNum == 2)
AllOpnds.push_back(&Opnd0_1);
if (Value *R = simplifyFAdd(AllOpnds, 1))
return R;
}
return performFactorization(I);
}
Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) {
unsigned AddendNum = Addends.size();
assert(AddendNum <= 4 && "Too many addends");
unsigned NextTmpIdx = 0;
FAddend TmpResult[3];
const FAddend *ConstAdd = nullptr;
AddendVect SimpVect;
for (unsigned SymIdx = 0; SymIdx < AddendNum; SymIdx++) {
const FAddend *ThisAddend = Addends[SymIdx];
if (!ThisAddend) {
continue;
}
Value *Val = ThisAddend->getSymVal();
unsigned StartIdx = SimpVect.size();
SimpVect.push_back(ThisAddend);
for (unsigned SameSymIdx = SymIdx + 1;
SameSymIdx < AddendNum; SameSymIdx++) {
const FAddend *T = Addends[SameSymIdx];
if (T && T->getSymVal() == Val) {
Addends[SameSymIdx] = nullptr;
SimpVect.push_back(T);
}
}
if (StartIdx + 1 != SimpVect.size()) {
FAddend &R = TmpResult[NextTmpIdx ++];
R = *SimpVect[StartIdx];
for (unsigned Idx = StartIdx + 1; Idx < SimpVect.size(); Idx++)
R += *SimpVect[Idx];
SimpVect.resize(StartIdx);
if (Val) {
if (!R.isZero()) {
SimpVect.push_back(&R);
}
} else {
ConstAdd = &R;
}
}
}
assert((NextTmpIdx <= array_lengthof(TmpResult) + 1) &&
"out-of-bound access");
if (ConstAdd)
SimpVect.push_back(ConstAdd);
Value *Result;
if (!SimpVect.empty())
Result = createNaryFAdd(SimpVect, InstrQuota);
else {
Result = ConstantFP::get(Instr->getType(), 0.0);
}
return Result;
}
Value *FAddCombine::createNaryFAdd
(const AddendVect &Opnds, unsigned InstrQuota) {
assert(!Opnds.empty() && "Expect at least one addend");
unsigned InstrNeeded = calcInstrNumber(Opnds);
if (InstrNeeded > InstrQuota)
return nullptr;
initCreateInstNum();
Value *LastVal = nullptr;
bool LastValNeedNeg = false;
for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
I != E; I++) {
bool NeedNeg;
Value *V = createAddendVal(**I, NeedNeg);
if (!LastVal) {
LastVal = V;
LastValNeedNeg = NeedNeg;
continue;
}
if (LastValNeedNeg == NeedNeg) {
LastVal = createFAdd(LastVal, V);
continue;
}
if (LastValNeedNeg)
LastVal = createFSub(V, LastVal);
else
LastVal = createFSub(LastVal, V);
LastValNeedNeg = false;
}
if (LastValNeedNeg) {
LastVal = createFNeg(LastVal);
}
#ifndef NDEBUG
assert(CreateInstrNum == InstrNeeded &&
"Inconsistent in instruction numbers");
#endif
return LastVal;
}
Value *FAddCombine::createFSub
(Value *Opnd0, Value *Opnd1) {
Value *V = Builder->CreateFSub(Opnd0, Opnd1);
if (Instruction *I = dyn_cast<Instruction>(V))
createInstPostProc(I);
return V;
}
Value *FAddCombine::createFNeg(Value *V) {
Value *Zero = cast<Value>(ConstantFP::get(V->getType(), 0.0));
Value *NewV = createFSub(Zero, V);
if (Instruction *I = dyn_cast<Instruction>(NewV))
createInstPostProc(I, true); return NewV;
}
Value *FAddCombine::createFAdd
(Value *Opnd0, Value *Opnd1) {
Value *V = Builder->CreateFAdd(Opnd0, Opnd1);
if (Instruction *I = dyn_cast<Instruction>(V))
createInstPostProc(I);
return V;
}
Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) {
Value *V = Builder->CreateFMul(Opnd0, Opnd1);
if (Instruction *I = dyn_cast<Instruction>(V))
createInstPostProc(I);
return V;
}
Value *FAddCombine::createFDiv(Value *Opnd0, Value *Opnd1) {
Value *V = Builder->CreateFDiv(Opnd0, Opnd1);
if (Instruction *I = dyn_cast<Instruction>(V))
createInstPostProc(I);
return V;
}
void FAddCombine::createInstPostProc(Instruction *NewInstr,
bool NoNumber) {
NewInstr->setDebugLoc(Instr->getDebugLoc());
if (!NoNumber)
incCreateInstNum();
NewInstr->setFastMathFlags(Instr->getFastMathFlags());
}
unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) {
unsigned OpndNum = Opnds.size();
unsigned InstrNeeded = OpndNum - 1;
unsigned NegOpndNum = 0;
for (AddendVect::const_iterator I = Opnds.begin(), E = Opnds.end();
I != E; I++) {
const FAddend *Opnd = *I;
if (Opnd->isConstant())
continue;
const FAddendCoef &CE = Opnd->getCoef();
if (CE.isMinusOne() || CE.isMinusTwo())
NegOpndNum++;
if (!CE.isMinusOne() && !CE.isOne())
InstrNeeded++;
}
if (NegOpndNum == OpndNum)
InstrNeeded++;
return InstrNeeded;
}
Value *FAddCombine::createAddendVal
(const FAddend &Opnd, bool &NeedNeg) {
const FAddendCoef &Coeff = Opnd.getCoef();
if (Opnd.isConstant()) {
NeedNeg = false;
return Coeff.getValue(Instr->getType());
}
Value *OpndVal = Opnd.getSymVal();
if (Coeff.isMinusOne() || Coeff.isOne()) {
NeedNeg = Coeff.isMinusOne();
return OpndVal;
}
if (Coeff.isTwo() || Coeff.isMinusTwo()) {
NeedNeg = Coeff.isMinusTwo();
return createFAdd(OpndVal, OpndVal);
}
NeedNeg = false;
return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
}
static bool checkRippleForAdd(const APInt &Op0KnownZero,
const APInt &Op1KnownZero) {
APInt Op1MaybeOne = ~Op1KnownZero;
if (Op1MaybeOne.countPopulation() != 1)
return false;
int BitWidth = Op0KnownZero.getBitWidth();
APInt Op0KnownZeroTemp(Op0KnownZero);
Op0KnownZeroTemp.clearBit(BitWidth - 1);
int Op0ZeroPosition = BitWidth - Op0KnownZeroTemp.countLeadingZeros() - 1;
int Op1OnePosition = BitWidth - Op1MaybeOne.countLeadingZeros() - 1;
assert(Op1OnePosition >= 0);
return Op0ZeroPosition >= Op1OnePosition;
}
bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1)
return true;
if (IntegerType *IT = dyn_cast<IntegerType>(LHS->getType())) {
int BitWidth = IT->getBitWidth();
APInt LHSKnownZero(BitWidth, 0);
APInt LHSKnownOne(BitWidth, 0);
computeKnownBits(LHS, LHSKnownZero, LHSKnownOne);
APInt RHSKnownZero(BitWidth, 0);
APInt RHSKnownOne(BitWidth, 0);
computeKnownBits(RHS, RHSKnownZero, RHSKnownOne);
if ((LHSKnownOne[BitWidth - 1] && RHSKnownZero[BitWidth - 1]) ||
(LHSKnownZero[BitWidth - 1] && RHSKnownOne[BitWidth - 1]))
return true;
if (checkRippleForAdd(LHSKnownZero, RHSKnownZero))
return true;
if (checkRippleForAdd(RHSKnownZero, LHSKnownZero))
return true;
}
return false;
}
bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) {
bool LHSKnownNonNegative, LHSKnownNegative;
bool RHSKnownNonNegative, RHSKnownNegative;
ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0);
ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0);
if (LHSKnownNonNegative && RHSKnownNonNegative)
return true;
return false;
}
static Value *checkForNegativeOperand(BinaryOperator &I,
InstCombiner::BuilderTy *Builder) {
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (!LHS->hasOneUse() && !RHS->hasOneUse())
return nullptr;
Value *X = nullptr, *Y = nullptr, *Z = nullptr;
const APInt *C1 = nullptr, *C2 = nullptr;
if (match(RHS, m_Add(m_Value(X), m_One())))
std::swap(LHS, RHS);
if (match(LHS, m_Add(m_Value(X), m_One()))) {
if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
std::swap(X, RHS);
if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) {
Value *NewAnd = Builder->CreateAnd(Z, *C1);
return Builder->CreateSub(RHS, NewAnd, "sub");
} else if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (*C1 == *C2)) {
Value *NewOr = Builder->CreateOr(Z, ~(*C1));
return Builder->CreateSub(RHS, NewOr, "sub");
}
}
}
LHS = I.getOperand(0);
RHS = I.getOperand(1);
if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
std::swap(LHS, RHS);
if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))))
if (C1->countTrailingZeros() == 0)
if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
Value *NewOr = Builder->CreateOr(Z, ~(*C2));
return Builder->CreateSub(RHS, NewOr, "sub");
}
return nullptr;
}
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
bool Changed = SimplifyAssociativeOrCommutative(I);
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
I.hasNoUnsignedWrap(), DL))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifyUsingDistributiveLaws(I))
return ReplaceInstUsesWith(I, V);
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
const APInt &Val = CI->getValue();
if (Val.isSignBit())
return BinaryOperator::CreateXor(LHS, RHS);
if (SimplifyDemandedInstructionBits(I))
return &I;
if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
if (ZI->getSrcTy()->isIntegerTy(1))
return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr;
if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
const APInt &RHSVal = CI->getValue();
unsigned ExtendAmt = 0;
if (XorRHS->getValue() == -RHSVal) {
if (RHSVal.isPowerOf2())
ExtendAmt = TySizeBits - RHSVal.logBase2() - 1;
else if (XorRHS->getValue().isPowerOf2())
ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1;
}
if (ExtendAmt) {
APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt);
if (!MaskedValueIsZero(XorLHS, Mask))
ExtendAmt = 0;
}
if (ExtendAmt) {
Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt);
Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext");
return BinaryOperator::CreateAShr(NewShl, ShAmt);
}
if (LHS->hasOneUse() && (XorRHS->getValue()+1).isPowerOf2()) {
IntegerType *IT = cast<IntegerType>(I.getType());
APInt LHSKnownOne(IT->getBitWidth(), 0);
APInt LHSKnownZero(IT->getBitWidth(), 0);
computeKnownBits(XorLHS, LHSKnownZero, LHSKnownOne);
if ((XorRHS->getValue() | LHSKnownZero).isAllOnesValue())
return BinaryOperator::CreateSub(ConstantExpr::getAdd(XorRHS, CI),
XorLHS);
}
if (XorRHS->getValue().isSignBit())
return BinaryOperator::CreateAdd(XorLHS,
ConstantExpr::getXor(XorRHS, CI));
}
}
if (isa<Constant>(RHS) && isa<PHINode>(LHS))
if (Instruction *NV = FoldOpIntoPhi(I))
return NV;
if (I.getType()->getScalarType()->isIntegerTy(1))
return BinaryOperator::CreateXor(LHS, RHS);
if (LHS == RHS) {
BinaryOperator *New =
BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1));
New->setHasNoSignedWrap(I.hasNoSignedWrap());
New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
return New;
}
if (Value *LHSV = dyn_castNegVal(LHS)) {
if (!isa<Constant>(RHS))
if (Value *RHSV = dyn_castNegVal(RHS)) {
Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum");
return BinaryOperator::CreateNeg(NewAdd);
}
return BinaryOperator::CreateSub(RHS, LHSV);
}
if (!isa<Constant>(RHS))
if (Value *V = dyn_castNegVal(RHS))
return BinaryOperator::CreateSub(LHS, V);
if (Value *V = checkForNegativeOperand(I, Builder))
return ReplaceInstUsesWith(I, V);
if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
APInt LHSKnownOne(IT->getBitWidth(), 0);
APInt LHSKnownZero(IT->getBitWidth(), 0);
computeKnownBits(LHS, LHSKnownZero, LHSKnownOne);
if (LHSKnownZero != 0) {
APInt RHSKnownOne(IT->getBitWidth(), 0);
APInt RHSKnownZero(IT->getBitWidth(), 0);
computeKnownBits(RHS, RHSKnownZero, RHSKnownOne);
if ((LHSKnownZero|RHSKnownZero).isAllOnesValue())
return BinaryOperator::CreateOr(LHS, RHS);
}
}
if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
Value *X;
if (match(LHS, m_Not(m_Value(X)))) return BinaryOperator::CreateSub(SubOne(CRHS), X);
}
if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
Value *X;
ConstantInt *C2;
if (LHS->hasOneUse() &&
match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) &&
CRHS->getValue() == (CRHS->getValue() & C2->getValue())) {
const APInt &AddRHSV = CRHS->getValue();
APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1));
APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue());
if (AddRHSHighBits == AddRHSHighBitsAnd) {
Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName());
return BinaryOperator::CreateAnd(NewAdd, C2);
}
}
if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
if (Instruction *R = FoldOpIntoSelect(I, SI))
return R;
}
{
SelectInst *SI = dyn_cast<SelectInst>(LHS);
Value *A = RHS;
if (!SI) {
SI = dyn_cast<SelectInst>(RHS);
A = LHS;
}
if (SI && SI->hasOneUse()) {
Value *TV = SI->getTrueValue();
Value *FV = SI->getFalseValue();
Value *N;
if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A))))
return SelectInst::Create(SI->getCondition(), N, A);
if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A))))
return SelectInst::Create(SI->getCondition(), A, N);
}
}
if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) {
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
Constant *CI =
ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
if (LHSConv->hasOneUse() &&
ConstantExpr::getSExt(CI, I.getType()) == RHSC &&
WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
CI, "addconv");
return new SExtInst(NewAdd, I.getType());
}
}
if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) {
if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
(LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
WillNotOverflowSignedAdd(LHSConv->getOperand(0),
RHSConv->getOperand(0))) {
Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
RHSConv->getOperand(0), "addconv");
return new SExtInst(NewAdd, I.getType());
}
}
}
{
Value *A = nullptr, *B = nullptr;
if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
(match(LHS, m_And(m_Specific(A), m_Specific(B))) ||
match(LHS, m_And(m_Specific(B), m_Specific(A)))))
return BinaryOperator::CreateOr(A, B);
if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
(match(RHS, m_And(m_Specific(A), m_Specific(B))) ||
match(RHS, m_And(m_Specific(B), m_Specific(A)))))
return BinaryOperator::CreateOr(A, B);
}
{
Value *A = nullptr, *B = nullptr;
if (match(RHS, m_Or(m_Value(A), m_Value(B))) &&
(match(LHS, m_And(m_Specific(A), m_Specific(B))) ||
match(LHS, m_And(m_Specific(B), m_Specific(A))))) {
auto *New = BinaryOperator::CreateAdd(A, B);
New->setHasNoSignedWrap(I.hasNoSignedWrap());
New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
return New;
}
if (match(LHS, m_Or(m_Value(A), m_Value(B))) &&
(match(RHS, m_And(m_Specific(A), m_Specific(B))) ||
match(RHS, m_And(m_Specific(B), m_Specific(A))))) {
auto *New = BinaryOperator::CreateAdd(A, B);
New->setHasNoSignedWrap(I.hasNoSignedWrap());
New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
return New;
}
}
if (!I.hasNoSignedWrap() && WillNotOverflowSignedAdd(LHS, RHS)) {
Changed = true;
I.setHasNoSignedWrap(true);
}
if (!I.hasNoUnsignedWrap() && WillNotOverflowUnsignedAdd(LHS, RHS)) {
Changed = true;
I.setHasNoUnsignedWrap(true);
}
return Changed ? &I : nullptr;
}
Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
bool Changed = SimplifyAssociativeOrCommutative(I);
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), DL))
return ReplaceInstUsesWith(I, V);
if (isa<Constant>(RHS)) {
if (isa<PHINode>(LHS))
if (Instruction *NV = FoldOpIntoPhi(I))
return NV;
if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
if (Instruction *NV = FoldOpIntoSelect(I, SI))
return NV;
}
if (Value *LHSV = dyn_castFNegVal(LHS)) {
Instruction *RI = BinaryOperator::CreateFSub(RHS, LHSV);
RI->copyFastMathFlags(&I);
return RI;
}
if (!isa<Constant>(RHS))
if (Value *V = dyn_castFNegVal(RHS)) {
Instruction *RI = BinaryOperator::CreateFSub(LHS, V);
RI->copyFastMathFlags(&I);
return RI;
}
if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) {
if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) {
Constant *CI =
ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType());
if (LHSConv->hasOneUse() &&
ConstantExpr::getSIToFP(CI, I.getType()) == CFP &&
WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) {
Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
CI, "addconv");
return new SIToFPInst(NewAdd, I.getType());
}
}
if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) {
if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&&
(LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
WillNotOverflowSignedAdd(LHSConv->getOperand(0),
RHSConv->getOperand(0))) {
Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0),
RHSConv->getOperand(0),"addconv");
return new SIToFPInst(NewAdd, I.getType());
}
}
}
{
Value *A1, *B1, *C1, *A2, *B2, *C2;
if (match(LHS, m_Select(m_Value(C1), m_Value(A1), m_Value(B1))) &&
match(RHS, m_Select(m_Value(C2), m_Value(A2), m_Value(B2)))) {
if (C1 == C2) {
Constant *Z1=nullptr, *Z2=nullptr;
Value *A, *B, *C=C1;
if (match(A1, m_AnyZero()) && match(B2, m_AnyZero())) {
Z1 = dyn_cast<Constant>(A1); A = A2;
Z2 = dyn_cast<Constant>(B2); B = B1;
} else if (match(B1, m_AnyZero()) && match(A2, m_AnyZero())) {
Z1 = dyn_cast<Constant>(B1); B = B2;
Z2 = dyn_cast<Constant>(A2); A = A1;
}
if (Z1 && Z2 &&
(I.hasNoSignedZeros() ||
(Z1->isNegativeZeroValue() && Z2->isNegativeZeroValue()))) {
return SelectInst::Create(C, A, B);
}
}
}
}
if (I.hasUnsafeAlgebra()) {
if (Value *V = FAddCombine(Builder).simplify(&I))
return ReplaceInstUsesWith(I, V);
}
return Changed ? &I : nullptr;
}
Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
Type *Ty) {
assert(DL && "Must have target data info for this");
bool Swapped = false;
GEPOperator *GEP1 = nullptr, *GEP2 = nullptr;
if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
if (LHSGEP->getOperand(0) == RHS) {
GEP1 = LHSGEP;
Swapped = false;
} else if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
if (LHSGEP->getOperand(0)->stripPointerCasts() ==
RHSGEP->getOperand(0)->stripPointerCasts()) {
GEP2 = RHSGEP;
GEP1 = LHSGEP;
Swapped = false;
}
}
}
if (GEPOperator *RHSGEP = dyn_cast<GEPOperator>(RHS)) {
if (RHSGEP->getOperand(0) == LHS) {
GEP1 = RHSGEP;
Swapped = true;
} else if (GEPOperator *LHSGEP = dyn_cast<GEPOperator>(LHS)) {
if (RHSGEP->getOperand(0)->stripPointerCasts() ==
LHSGEP->getOperand(0)->stripPointerCasts()) {
GEP2 = LHSGEP;
GEP1 = RHSGEP;
Swapped = true;
}
}
}
if (!GEP1 ||
(GEP2 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse()))
return nullptr;
Value *Result = EmitGEPOffset(GEP1);
if (GEP2) {
Value *Offset = EmitGEPOffset(GEP2);
Result = Builder->CreateSub(Result, Offset);
}
if (Swapped)
Result = Builder->CreateNeg(Result, "diff.neg");
return Builder->CreateIntCast(Result, Ty, true);
}
Instruction *InstCombiner::visitSub(BinaryOperator &I) {
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
I.hasNoUnsignedWrap(), DL))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifyUsingDistributiveLaws(I))
return ReplaceInstUsesWith(I, V);
if (Value *V = dyn_castNegVal(Op1)) {
BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V);
if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
assert(BO->getOpcode() == Instruction::Sub &&
"Expected a subtraction operator!");
if (BO->hasNoSignedWrap() && I.hasNoSignedWrap())
Res->setHasNoSignedWrap(true);
} else {
if (cast<Constant>(Op1)->isNotMinSignedValue() && I.hasNoSignedWrap())
Res->setHasNoSignedWrap(true);
}
return Res;
}
if (I.getType()->isIntegerTy(1))
return BinaryOperator::CreateXor(Op0, Op1);
if (match(Op0, m_AllOnes()))
return BinaryOperator::CreateNot(Op1);
if (Constant *C = dyn_cast<Constant>(Op0)) {
Value *X = nullptr;
if (match(Op1, m_Not(m_Value(X))))
return BinaryOperator::CreateAdd(X, AddOne(C));
if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
if (Instruction *R = FoldOpIntoSelect(I, SI))
return R;
Constant *C2;
if (match(Op1, m_Add(m_Value(X), m_Constant(C2))))
return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
if (SimplifyDemandedInstructionBits(I))
return &I;
if (C->isNullValue() && match(Op1, m_ZExt(m_Value(X))))
if (X->getType()->getScalarType()->isIntegerTy(1))
return CastInst::CreateSExtOrBitCast(X, Op1->getType());
if (C->isNullValue() && match(Op1, m_SExt(m_Value(X))))
if (X->getType()->getScalarType()->isIntegerTy(1))
return CastInst::CreateZExtOrBitCast(X, Op1->getType());
}
if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
if (C->isZero()) {
Value *X; ConstantInt *CI;
if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) &&
CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
return BinaryOperator::CreateAShr(X, CI);
if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) &&
CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1)
return BinaryOperator::CreateLShr(X, CI);
}
}
{ Value *Y;
if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) ||
match(Op1, m_Add(m_Value(Y), m_Specific(Op0))))
return BinaryOperator::CreateNeg(Y);
if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))
return BinaryOperator::CreateNeg(Y);
}
if (Op1->hasOneUse()) {
Value *X = nullptr, *Y = nullptr, *Z = nullptr;
Constant *C = nullptr;
Constant *CI = nullptr;
if (match(Op1, m_Sub(m_Value(Y), m_Value(Z))))
return BinaryOperator::CreateAdd(Op0,
Builder->CreateSub(Z, Y, Op1->getName()));
if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) ||
match(Op1, m_And(m_Specific(Op0), m_Value(Y))))
return BinaryOperator::CreateAnd(Op0,
Builder->CreateNot(Y, Y->getName() + ".not"));
if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) &&
C->isNotMinSignedValue() && !C->isOneValue())
return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
if (Value *XNeg = dyn_castNegVal(X))
return BinaryOperator::CreateShl(XNeg, Y);
Value *A, *B;
if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
if (match(Op1, m_Mul(m_Value(A), m_Constant(CI))) ||
match(Op1, m_Mul(m_Constant(CI), m_Value(A)))) {
Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI));
return BinaryOperator::CreateAdd(Op0, NewMul);
}
}
if (DL) {
Value *LHSOp, *RHSOp;
if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
match(Op1, m_PtrToInt(m_Value(RHSOp))))
if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
return ReplaceInstUsesWith(I, Res);
if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) &&
match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp)))))
if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
return ReplaceInstUsesWith(I, Res);
}
return nullptr;
}
Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), DL))
return ReplaceInstUsesWith(I, V);
if (isa<Constant>(Op0))
if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
if (Instruction *NV = FoldOpIntoSelect(I, SI))
return NV;
if (Value *V = dyn_castFNegVal(Op1)) {
Instruction *NewI = BinaryOperator::CreateFAdd(Op0, V);
NewI->copyFastMathFlags(&I);
return NewI;
}
if (FPTruncInst *FPTI = dyn_cast<FPTruncInst>(Op1)) {
if (Value *V = dyn_castFNegVal(FPTI->getOperand(0))) {
Value *NewTrunc = Builder->CreateFPTrunc(V, I.getType());
Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewTrunc);
NewI->copyFastMathFlags(&I);
return NewI;
}
} else if (FPExtInst *FPEI = dyn_cast<FPExtInst>(Op1)) {
if (Value *V = dyn_castFNegVal(FPEI->getOperand(0))) {
Value *NewExt = Builder->CreateFPExt(V, I.getType());
Instruction *NewI = BinaryOperator::CreateFAdd(Op0, NewExt);
NewI->copyFastMathFlags(&I);
return NewI;
}
}
if (I.hasUnsafeAlgebra()) {
if (Value *V = FAddCombine(Builder).simplify(&I))
return ReplaceInstUsesWith(I, V);
}
return nullptr;
}