#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
+#include <algorithm>
using namespace llvm;
using namespace llvm::PatternMatch;
if (Op0 == Op1)
return Constant::getNullValue(Op0->getType());
- // X - (0 - Y) -> X if the second sub is NUW.
- // If Y != 0, 0 - Y is a poison value.
- // If Y == 0, 0 - Y simplifies to 0.
- if (BinaryOperator::isNeg(Op1)) {
- if (const auto *BO = dyn_cast<BinaryOperator>(Op1)) {
- assert(BO->getOpcode() == Instruction::Sub &&
- "Expected a subtraction operator!");
- if (BO->hasNoUnsignedWrap())
- return Op0;
- }
- }
+ // 0 - X -> 0 if the sub is NUW.
+ if (isNUW && match(Op0, m_Zero()))
+ return Op0;
// (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
// For example, (X + Y) - Y -> X; (Y + X) - Y -> X
if (match(Op1, m_Undef()))
return Op1;
+ // X / 0 -> undef, we don't need to preserve faults!
+ if (match(Op1, m_Zero()))
+ return UndefValue::get(Op1->getType());
+
// undef / X -> 0
if (match(Op0, m_Undef()))
return Constant::getNullValue(Op0->getType());
if (Op0 == Op1)
return Constant::getNullValue(Op0->getType());
+ // undef >> X -> 0
+ // undef >> X -> undef (if it's exact)
+ if (match(Op0, m_Undef()))
+ return isExact ? Op0 : Constant::getNullValue(Op0->getType());
+
// The low bit cannot be shifted out of an exact shift if it is set.
if (isExact) {
unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
return V;
// undef << X -> 0
+ // undef << X -> undef if (if it's NSW/NUW)
if (match(Op0, m_Undef()))
- return Constant::getNullValue(Op0->getType());
+ return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
// (X >> A) << A -> X
Value *X;
MaxRecurse))
return V;
- // undef >>l X -> 0
- if (match(Op0, m_Undef()))
- return Constant::getNullValue(Op0->getType());
-
// (X << A) >> A -> X
Value *X;
if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
if (match(Op0, m_AllOnes()))
return Op0;
- // undef >>a X -> all ones
- if (match(Op0, m_Undef()))
- return Constant::getAllOnesValue(Op0->getType());
-
// (X << A) >> A -> X
Value *X;
if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
RecursionLimit);
}
+static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
+ ICmpInst *UnsignedICmp, bool IsAnd) {
+ Value *X, *Y;
+
+ ICmpInst::Predicate EqPred;
+ if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
+ !ICmpInst::isEquality(EqPred))
+ return nullptr;
+
+ ICmpInst::Predicate UnsignedPred;
+ if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
+ ICmpInst::isUnsigned(UnsignedPred))
+ ;
+ else if (match(UnsignedICmp,
+ m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) &&
+ ICmpInst::isUnsigned(UnsignedPred))
+ UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
+ else
+ return nullptr;
+
+ // X < Y && Y != 0 --> X < Y
+ // X < Y || Y != 0 --> Y != 0
+ if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
+ return IsAnd ? UnsignedICmp : ZeroICmp;
+
+ // X >= Y || Y != 0 --> true
+ // X >= Y || Y == 0 --> X >= Y
+ if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
+ if (EqPred == ICmpInst::ICMP_NE)
+ return getTrue(UnsignedICmp->getType());
+ return UnsignedICmp;
+ }
+
+ // X < Y && Y == 0 --> false
+ if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
+ IsAnd)
+ return getFalse(UnsignedICmp->getType());
+
+ return nullptr;
+}
+
// Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range
// of possible values cannot be satisfied.
static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
ICmpInst::Predicate Pred0, Pred1;
ConstantInt *CI1, *CI2;
Value *V;
+
+ if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
+ return X;
+
if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)),
m_ConstantInt(CI2))))
return nullptr;
ICmpInst::Predicate Pred0, Pred1;
ConstantInt *CI1, *CI2;
Value *V;
+
+ if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
+ return X;
+
if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)),
m_ConstantInt(CI2))))
return nullptr;
return ConstantExpr::getICmp(Pred,
ConstantExpr::getAdd(LHSOffset, LHSNoBound),
ConstantExpr::getAdd(RHSOffset, RHSNoBound));
+
+ // If one side of the equality comparison must come from a noalias call
+ // (meaning a system memory allocation function), and the other side must
+ // come from a pointer that cannot overlap with dynamically-allocated
+ // memory within the lifetime of the current function (allocas, byval
+ // arguments, globals), then determine the comparison result here.
+ SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
+ GetUnderlyingObjects(LHS, LHSUObjs, DL);
+ GetUnderlyingObjects(RHS, RHSUObjs, DL);
+
+ // Is the set of underlying objects all noalias calls?
+ auto IsNAC = [](SmallVectorImpl<Value *> &Objects) {
+ return std::all_of(Objects.begin(), Objects.end(),
+ [](Value *V){ return isNoAliasCall(V); });
+ };
+
+ // Is the set of underlying objects all things which must be disjoint from
+ // noalias calls. For allocas, we consider only static ones (dynamic
+ // allocas might be transformed into calls to malloc not simultaneously
+ // live with the compared-to allocation). For globals, we exclude symbols
+ // that might be resolve lazily to symbols in another dynamically-loaded
+ // library (and, thus, could be malloc'ed by the implementation).
+ auto IsAllocDisjoint = [](SmallVectorImpl<Value *> &Objects) {
+ return std::all_of(Objects.begin(), Objects.end(),
+ [](Value *V){
+ if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
+ return AI->getParent() && AI->getParent()->getParent() &&
+ AI->isStaticAlloca();
+ if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
+ return (GV->hasLocalLinkage() ||
+ GV->hasHiddenVisibility() ||
+ GV->hasProtectedVisibility() ||
+ GV->hasUnnamedAddr()) &&
+ !GV->isThreadLocal();
+ if (const Argument *A = dyn_cast<Argument>(V))
+ return A->hasByValAttr();
+ return false;
+ });
+ };
+
+ if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
+ (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
+ return ConstantInt::get(GetCompareTy(LHS),
+ !CmpInst::isTrueWhenEqual(Pred));
}
// Otherwise, fail.
}
}
+ // icmp pred (or X, Y), X
+ if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)),
+ m_Or(m_Specific(RHS), m_Value())))) {
+ if (Pred == ICmpInst::ICMP_ULT)
+ return getFalse(ITy);
+ if (Pred == ICmpInst::ICMP_UGE)
+ return getTrue(ITy);
+ }
+ // icmp pred X, (or X, Y)
+ if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)),
+ m_Or(m_Specific(LHS), m_Value())))) {
+ if (Pred == ICmpInst::ICMP_ULE)
+ return getTrue(ITy);
+ if (Pred == ICmpInst::ICMP_UGT)
+ return getFalse(ITy);
+ }
+
+ // icmp pred (and X, Y), X
+ if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)),
+ m_And(m_Specific(RHS), m_Value())))) {
+ if (Pred == ICmpInst::ICMP_UGT)
+ return getFalse(ITy);
+ if (Pred == ICmpInst::ICMP_ULE)
+ return getTrue(ITy);
+ }
+ // icmp pred X, (and X, Y)
+ if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)),
+ m_And(m_Specific(LHS), m_Value())))) {
+ if (Pred == ICmpInst::ICMP_UGE)
+ return getTrue(ITy);
+ if (Pred == ICmpInst::ICMP_ULT)
+ return getFalse(ITy);
+ }
+
// 0 - (zext X) pred C
if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
return TrueVal;
+ if (const auto *ICI = dyn_cast<ICmpInst>(CondVal)) {
+ Value *X;
+ const APInt *Y;
+ ICmpInst::Predicate Pred = ICI->getPredicate();
+ if (ICmpInst::isEquality(Pred) &&
+ match(ICI->getOperand(0), m_And(m_Value(X), m_APInt(Y))) &&
+ match(ICI->getOperand(1), m_Zero())) {
+ const APInt *C;
+ // (X & Y) == 0 ? X & ~Y : X --> X
+ // (X & Y) != 0 ? X & ~Y : X --> X & ~Y
+ if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
+ *Y == ~*C)
+ return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
+ // (X & Y) == 0 ? X : X & ~Y --> X & ~Y
+ // (X & Y) != 0 ? X : X & ~Y --> X
+ if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
+ *Y == ~*C)
+ return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
+
+ if (Y->isPowerOf2()) {
+ // (X & Y) == 0 ? X | Y : X --> X | Y
+ // (X & Y) != 0 ? X | Y : X --> X
+ if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
+ *Y == *C)
+ return Pred == ICmpInst::ICMP_EQ ? TrueVal : FalseVal;
+ // (X & Y) == 0 ? X : X | Y --> X
+ // (X & Y) != 0 ? X : X | Y --> X | Y
+ if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
+ *Y == *C)
+ return Pred == ICmpInst::ICMP_EQ ? TrueVal : FalseVal;
+ }
+ }
+ if (Pred == ICmpInst::ICMP_SLT && match(ICI->getOperand(1), m_Zero())) {
+ // (X < 0) ? X : X | SignBit --> X | SignBit
+ if (TrueVal == ICI->getOperand(0) &&
+ match(FalseVal, m_Or(m_Specific(TrueVal), m_SignBit())))
+ return FalseVal;
+ // (X < 0) ? X | SignBit : X --> X
+ if (FalseVal == ICI->getOperand(0) &&
+ match(TrueVal, m_Or(m_Specific(FalseVal), m_SignBit())))
+ return FalseVal;
+ // (X < 0) ? X & INT_MAX : X --> X & INT_MAX
+ if (FalseVal == ICI->getOperand(0) &&
+ match(TrueVal, m_And(m_Specific(FalseVal), m_MaxSignedValue())))
+ return TrueVal;
+ // (X < 0) ? X : X & INT_MAX --> X
+ if (TrueVal == ICI->getOperand(0) &&
+ match(FalseVal, m_And(m_Specific(TrueVal), m_MaxSignedValue())))
+ return TrueVal;
+ }
+ if (Pred == ICmpInst::ICMP_SGT && match(ICI->getOperand(1), m_AllOnes())) {
+ // (X > -1) ? X : X | SignBit --> X
+ if (TrueVal == ICI->getOperand(0) &&
+ match(FalseVal, m_Or(m_Specific(TrueVal), m_SignBit())))
+ return TrueVal;
+ // (X > -1) ? X | SignBit : X --> X | SignBit
+ if (FalseVal == ICI->getOperand(0) &&
+ match(TrueVal, m_Or(m_Specific(FalseVal), m_SignBit())))
+ return TrueVal;
+ // (X > -1) ? X & INT_MAX : X --> X
+ if (FalseVal == ICI->getOperand(0) &&
+ match(TrueVal, m_And(m_Specific(FalseVal), m_MaxSignedValue())))
+ return FalseVal;
+ // (X > -1) ? X : X & INT_MAX --> X & INT_MAX
+ if (TrueVal == ICI->getOperand(0) &&
+ match(FalseVal, m_And(m_Specific(TrueVal), m_MaxSignedValue())))
+ return FalseVal;
+ }
+ }
+
return nullptr;
}
projects / oota-llvm.git / blobdiff