diff options
Diffstat (limited to 'llvm/lib/IR')
-rw-r--r-- | llvm/lib/IR/ConstantRange.cpp | 76 | ||||
-rw-r--r-- | llvm/lib/IR/ConstantsContext.h | 3 | ||||
-rw-r--r-- | llvm/lib/IR/IRBuilder.cpp | 59 | ||||
-rw-r--r-- | llvm/lib/IR/SafepointIRVerifier.cpp | 2 |
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 |