aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/IR
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/IR')
-rw-r--r--llvm/lib/IR/ConstantRange.cpp76
-rw-r--r--llvm/lib/IR/ConstantsContext.h3
-rw-r--r--llvm/lib/IR/IRBuilder.cpp59
-rw-r--r--llvm/lib/IR/SafepointIRVerifier.cpp2
4 files changed, 103 insertions, 37 deletions
diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index d81a292..3566435 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1520,15 +1520,72 @@ ConstantRange ConstantRange::binaryNot() const {
return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
}
+/// Estimate the 'bit-masked AND' operation's lower bound.
+///
+/// E.g., given two ranges as follows (single quotes are separators and
+/// have no meaning here),
+///
+/// LHS = [10'00101'1, ; LLo
+/// 10'10000'0] ; LHi
+/// RHS = [10'11111'0, ; RLo
+/// 10'11111'1] ; RHi
+///
+/// we know that the higher 2 bits of the result is always 10; and we also
+/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than
+/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.
+///
+/// The algorithm is as follows,
+/// 1. we first calculate a mask to find the higher common bits by
+/// Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
+/// Mask = clear all non-leading-ones bits in Mask;
+/// in the example, the Mask is set to 11'00000'0;
+/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and
+/// keeping the longest leading ones (i.e., 11'11111'0 in the example);
+/// 3. return (LLo & new mask) as the lower bound;
+/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower
+/// bound with the larger one.
+static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,
+ const ConstantRange &RHS) {
+ auto BitWidth = LHS.getBitWidth();
+ // If either is full set or unsigned wrapped, then the range must contain '0'
+ // which leads the lower bound to 0.
+ if ((LHS.isFullSet() || RHS.isFullSet()) ||
+ (LHS.isWrappedSet() || RHS.isWrappedSet()))
+ return APInt::getZero(BitWidth);
+
+ auto LLo = LHS.getLower();
+ auto LHi = LHS.getUpper() - 1;
+ auto RLo = RHS.getLower();
+ auto RHi = RHS.getUpper() - 1;
+
+ // Calculate the mask for the higher common bits.
+ auto Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
+ unsigned LeadingOnes = Mask.countLeadingOnes();
+ Mask.clearLowBits(BitWidth - LeadingOnes);
+
+ auto estimateBound = [BitWidth, &Mask](APInt ALo, const APInt &BLo,
+ const APInt &BHi) {
+ unsigned LeadingOnes = ((BLo & BHi) | Mask).countLeadingOnes();
+ unsigned StartBit = BitWidth - LeadingOnes;
+ ALo.clearLowBits(StartBit);
+ return ALo;
+ };
+
+ auto LowerBoundByLHS = estimateBound(LLo, RLo, RHi);
+ auto LowerBoundByRHS = estimateBound(RLo, LLo, LHi);
+
+ return APIntOps::umax(LowerBoundByLHS, LowerBoundByRHS);
+}
+
ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const {
if (isEmptySet() || Other.isEmptySet())
return getEmpty();
ConstantRange KnownBitsRange =
fromKnownBits(toKnownBits() & Other.toKnownBits(), false);
- ConstantRange UMinUMaxRange =
- getNonEmpty(APInt::getZero(getBitWidth()),
- APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
+ auto LowerBound = estimateBitMaskedAndLowerBound(*this, Other);
+ ConstantRange UMinUMaxRange = getNonEmpty(
+ LowerBound, APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
return KnownBitsRange.intersectWith(UMinUMaxRange);
}
@@ -1538,10 +1595,17 @@ ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const {
ConstantRange KnownBitsRange =
fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
+
+ // ~a & ~b >= x
+ // <=> ~(~a & ~b) <= ~x
+ // <=> a | b <= ~x
+ // <=> a | b < ~x + 1 = -x
+ // thus, UpperBound(a | b) == -LowerBound(~a & ~b)
+ auto UpperBound =
+ -estimateBitMaskedAndLowerBound(binaryNot(), Other.binaryNot());
// Upper wrapped range.
- ConstantRange UMaxUMinRange =
- getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()),
- APInt::getZero(getBitWidth()));
+ ConstantRange UMaxUMinRange = getNonEmpty(
+ APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()), UpperBound);
return KnownBitsRange.intersectWith(UMaxUMinRange);
}
diff --git a/llvm/lib/IR/ConstantsContext.h b/llvm/lib/IR/ConstantsContext.h
index aaaab0b..08bf3f9 100644
--- a/llvm/lib/IR/ConstantsContext.h
+++ b/llvm/lib/IR/ConstantsContext.h
@@ -491,8 +491,7 @@ public:
default:
if (Instruction::isCast(Opcode))
return new CastConstantExpr(Opcode, Ops[0], Ty);
- if ((Opcode >= Instruction::BinaryOpsBegin &&
- Opcode < Instruction::BinaryOpsEnd))
+ if (Instruction::isBinaryOp(Opcode))
return new BinaryConstantExpr(Opcode, Ops[0], Ops[1],
SubclassOptionalData);
llvm_unreachable("Invalid ConstantExpr!");
diff --git a/llvm/lib/IR/IRBuilder.cpp b/llvm/lib/IR/IRBuilder.cpp
index f340f7a..27b499e 100644
--- a/llvm/lib/IR/IRBuilder.cpp
+++ b/llvm/lib/IR/IRBuilder.cpp
@@ -78,11 +78,11 @@ void IRBuilderBase::SetInstDebugLocation(Instruction *I) const {
CallInst *
IRBuilderBase::createCallHelper(Function *Callee, ArrayRef<Value *> Ops,
- const Twine &Name, Instruction *FMFSource,
+ const Twine &Name, FMFSource FMFSource,
ArrayRef<OperandBundleDef> OpBundles) {
CallInst *CI = CreateCall(Callee, Ops, OpBundles, Name);
- if (FMFSource)
- CI->copyFastMathFlags(FMFSource);
+ if (isa<FPMathOperator>(CI))
+ CI->setFastMathFlags(FMFSource.get(FMF));
return CI;
}
@@ -869,7 +869,7 @@ CallInst *IRBuilderBase::CreateGCGetPointerOffset(Value *DerivedPtr,
}
CallInst *IRBuilderBase::CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V,
- Instruction *FMFSource,
+ FMFSource FMFSource,
const Twine &Name) {
Module *M = BB->getModule();
Function *Fn = Intrinsic::getOrInsertDeclaration(M, ID, {V->getType()});
@@ -877,12 +877,12 @@ CallInst *IRBuilderBase::CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V,
}
Value *IRBuilderBase::CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS,
- Value *RHS, Instruction *FMFSource,
+ Value *RHS, FMFSource FMFSource,
const Twine &Name) {
Module *M = BB->getModule();
Function *Fn = Intrinsic::getOrInsertDeclaration(M, ID, {LHS->getType()});
if (Value *V = Folder.FoldBinaryIntrinsic(ID, LHS, RHS, Fn->getReturnType(),
- FMFSource))
+ /*FMFSource=*/nullptr))
return V;
return createCallHelper(Fn, {LHS, RHS}, Name, FMFSource);
}
@@ -890,7 +890,7 @@ Value *IRBuilderBase::CreateBinaryIntrinsic(Intrinsic::ID ID, Value *LHS,
CallInst *IRBuilderBase::CreateIntrinsic(Intrinsic::ID ID,
ArrayRef<Type *> Types,
ArrayRef<Value *> Args,
- Instruction *FMFSource,
+ FMFSource FMFSource,
const Twine &Name) {
Module *M = BB->getModule();
Function *Fn = Intrinsic::getOrInsertDeclaration(M, ID, Types);
@@ -899,7 +899,7 @@ CallInst *IRBuilderBase::CreateIntrinsic(Intrinsic::ID ID,
CallInst *IRBuilderBase::CreateIntrinsic(Type *RetTy, Intrinsic::ID ID,
ArrayRef<Value *> Args,
- Instruction *FMFSource,
+ FMFSource FMFSource,
const Twine &Name) {
Module *M = BB->getModule();
@@ -925,16 +925,13 @@ CallInst *IRBuilderBase::CreateIntrinsic(Type *RetTy, Intrinsic::ID ID,
}
CallInst *IRBuilderBase::CreateConstrainedFPBinOp(
- Intrinsic::ID ID, Value *L, Value *R, Instruction *FMFSource,
- const Twine &Name, MDNode *FPMathTag,
- std::optional<RoundingMode> Rounding,
+ Intrinsic::ID ID, Value *L, Value *R, FMFSource FMFSource,
+ const Twine &Name, MDNode *FPMathTag, std::optional<RoundingMode> Rounding,
std::optional<fp::ExceptionBehavior> Except) {
Value *RoundingV = getConstrainedFPRounding(Rounding);
Value *ExceptV = getConstrainedFPExcept(Except);
- FastMathFlags UseFMF = FMF;
- if (FMFSource)
- UseFMF = FMFSource->getFastMathFlags();
+ FastMathFlags UseFMF = FMFSource.get(FMF);
CallInst *C = CreateIntrinsic(ID, {L->getType()},
{L, R, RoundingV, ExceptV}, nullptr, Name);
@@ -944,14 +941,12 @@ CallInst *IRBuilderBase::CreateConstrainedFPBinOp(
}
CallInst *IRBuilderBase::CreateConstrainedFPUnroundedBinOp(
- Intrinsic::ID ID, Value *L, Value *R, Instruction *FMFSource,
+ Intrinsic::ID ID, Value *L, Value *R, FMFSource FMFSource,
const Twine &Name, MDNode *FPMathTag,
std::optional<fp::ExceptionBehavior> Except) {
Value *ExceptV = getConstrainedFPExcept(Except);
- FastMathFlags UseFMF = FMF;
- if (FMFSource)
- UseFMF = FMFSource->getFastMathFlags();
+ FastMathFlags UseFMF = FMFSource.get(FMF);
CallInst *C =
CreateIntrinsic(ID, {L->getType()}, {L, R, ExceptV}, nullptr, Name);
@@ -976,15 +971,12 @@ Value *IRBuilderBase::CreateNAryOp(unsigned Opc, ArrayRef<Value *> Ops,
}
CallInst *IRBuilderBase::CreateConstrainedFPCast(
- Intrinsic::ID ID, Value *V, Type *DestTy,
- Instruction *FMFSource, const Twine &Name, MDNode *FPMathTag,
- std::optional<RoundingMode> Rounding,
+ Intrinsic::ID ID, Value *V, Type *DestTy, FMFSource FMFSource,
+ const Twine &Name, MDNode *FPMathTag, std::optional<RoundingMode> Rounding,
std::optional<fp::ExceptionBehavior> Except) {
Value *ExceptV = getConstrainedFPExcept(Except);
- FastMathFlags UseFMF = FMF;
- if (FMFSource)
- UseFMF = FMFSource->getFastMathFlags();
+ FastMathFlags UseFMF = FMFSource.get(FMF);
CallInst *C;
if (Intrinsic::hasConstrainedFPRoundingModeOperand(ID)) {
@@ -1002,9 +994,10 @@ CallInst *IRBuilderBase::CreateConstrainedFPCast(
return C;
}
-Value *IRBuilderBase::CreateFCmpHelper(
- CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name,
- MDNode *FPMathTag, bool IsSignaling) {
+Value *IRBuilderBase::CreateFCmpHelper(CmpInst::Predicate P, Value *LHS,
+ Value *RHS, const Twine &Name,
+ MDNode *FPMathTag, FMFSource FMFSource,
+ bool IsSignaling) {
if (IsFPConstrained) {
auto ID = IsSignaling ? Intrinsic::experimental_constrained_fcmps
: Intrinsic::experimental_constrained_fcmp;
@@ -1013,7 +1006,9 @@ Value *IRBuilderBase::CreateFCmpHelper(
if (auto *V = Folder.FoldCmp(P, LHS, RHS))
return V;
- return Insert(setFPAttrs(new FCmpInst(P, LHS, RHS), FPMathTag, FMF), Name);
+ return Insert(
+ setFPAttrs(new FCmpInst(P, LHS, RHS), FPMathTag, FMFSource.get(FMF)),
+ Name);
}
CallInst *IRBuilderBase::CreateConstrainedFPCmp(
@@ -1047,6 +1042,12 @@ CallInst *IRBuilderBase::CreateConstrainedFPCall(
Value *IRBuilderBase::CreateSelect(Value *C, Value *True, Value *False,
const Twine &Name, Instruction *MDFrom) {
+ return CreateSelectFMF(C, True, False, {}, Name, MDFrom);
+}
+
+Value *IRBuilderBase::CreateSelectFMF(Value *C, Value *True, Value *False,
+ FMFSource FMFSource, const Twine &Name,
+ Instruction *MDFrom) {
if (auto *V = Folder.FoldSelect(C, True, False))
return V;
@@ -1057,7 +1058,7 @@ Value *IRBuilderBase::CreateSelect(Value *C, Value *True, Value *False,
Sel = addBranchMetadata(Sel, Prof, Unpred);
}
if (isa<FPMathOperator>(Sel))
- setFPAttrs(Sel, nullptr /* MDNode* */, FMF);
+ setFPAttrs(Sel, /*MDNode=*/nullptr, FMFSource.get(FMF));
return Insert(Sel, Name);
}
diff --git a/llvm/lib/IR/SafepointIRVerifier.cpp b/llvm/lib/IR/SafepointIRVerifier.cpp
index ed99d05..d32852b 100644
--- a/llvm/lib/IR/SafepointIRVerifier.cpp
+++ b/llvm/lib/IR/SafepointIRVerifier.cpp
@@ -289,6 +289,7 @@ static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
using AvailableValueSet = DenseSet<const Value *>;
+namespace {
/// State we compute and track per basic block.
struct BasicBlockState {
// Set of values available coming in, before the phi nodes
@@ -305,6 +306,7 @@ struct BasicBlockState {
// contribute to AvailableOut.
bool Cleared = false;
};
+} // namespace
/// A given derived pointer can have multiple base pointers through phi/selects.
/// This type indicates when the base pointer is exclusively constant