Skip to content

Commit c686868

Browse files
nikicnikic
committed
[ConstantRange] Add srem() support
Add support for srem() to ConstantRange so we can use it in LVI. For srem the sign of the result matches the sign of the LHS. For the RHS only the absolute value is important. Apart from that the logic is like urem. Just like for urem this is only an approximate implementation. The tests check a few specific cases and run an exhaustive test for conservative correctness (but not exactness). Differential Revision: https://reviews.llvm.org/D61207 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@360055 91177308-0d34-0410-b5e6-96231b3b80d8
1 parent 68567be commit c686868

File tree

3 files changed

+140
-8
lines changed

3 files changed

+140
-8
lines changed

‎include/llvm/IR/ConstantRange.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -369,6 +369,11 @@ class LLVM_NODISCARD ConstantRange {
369369
/// value in \p Other.
370370
ConstantRange urem(const ConstantRange &Other) const;
371371

372+
/// Return a new range representing the possible values resulting
373+
/// from a signed remainder operation of a value in this range and a
374+
/// value in \p Other.
375+
ConstantRange srem(const ConstantRange &Other) const;
376+
372377
/// Return a new range representing the possible values resulting
373378
/// from a binary-and of a value in this range by a value in \p Other.
374379
ConstantRange binaryAnd(const ConstantRange &Other) const;

‎lib/IR/ConstantRange.cpp

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -804,6 +804,8 @@ ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
804804
return udiv(Other);
805805
case Instruction::URem:
806806
return urem(Other);
807+
case Instruction::SRem:
808+
return srem(Other);
807809
case Instruction::Shl:
808810
return shl(Other);
809811
case Instruction::LShr:
@@ -1010,6 +1012,48 @@ ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
10101012
return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
10111013
}
10121014

1015+
ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1016+
if (isEmptySet() || RHS.isEmptySet())
1017+
return getEmpty();
1018+
1019+
ConstantRange AbsRHS = RHS.abs();
1020+
APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1021+
APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1022+
1023+
// Modulus by zero is UB.
1024+
if (MaxAbsRHS.isNullValue())
1025+
return getEmpty();
1026+
1027+
if (MinAbsRHS.isNullValue())
1028+
++MinAbsRHS;
1029+
1030+
APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1031+
1032+
if (MinLHS.isNonNegative()) {
1033+
// L % R for L < R is L.
1034+
if (MaxLHS.ult(MinAbsRHS))
1035+
return *this;
1036+
1037+
// L % R is <= L and < R.
1038+
APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1039+
return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1040+
}
1041+
1042+
// Same basic logic as above, but the result is negative.
1043+
if (MaxLHS.isNegative()) {
1044+
if (MinLHS.ugt(-MinAbsRHS))
1045+
return *this;
1046+
1047+
APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1048+
return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1049+
}
1050+
1051+
// LHS range crosses zero.
1052+
APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1053+
APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1054+
return ConstantRange(std::move(Lower), std::move(Upper));
1055+
}
1056+
10131057
ConstantRange
10141058
ConstantRange::binaryAnd(const ConstantRange &Other) const {
10151059
if (isEmptySet() || Other.isEmptySet())

‎unittests/IR/ConstantRangeTest.cpp

Lines changed: 91 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -96,20 +96,19 @@ static void TestUnsignedBinOpExhaustive(
9696
}
9797

9898
template<typename Fn1, typename Fn2>
99-
static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
99+
static void TestSignedBinOpExhaustive(
100+
Fn1 RangeFn, Fn2 IntFn,
101+
bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
100102
unsigned Bits = 4;
101103
EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
102104
const ConstantRange &CR2) {
103-
ConstantRange CR = RangeFn(CR1, CR2);
104-
if (CR1.isEmptySet() || CR2.isEmptySet()) {
105-
EXPECT_TRUE(CR.isEmptySet());
106-
return;
107-
}
108-
109105
APInt Min = APInt::getSignedMaxValue(Bits);
110106
APInt Max = APInt::getSignedMinValue(Bits);
111107
ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
112108
ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
109+
if (SkipZeroRHS && N2 == 0)
110+
return;
111+
113112
APInt N = IntFn(N1, N2);
114113
if (N.slt(Min))
115114
Min = N;
@@ -118,7 +117,18 @@ static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
118117
});
119118
});
120119

121-
EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR);
120+
ConstantRange CR = RangeFn(CR1, CR2);
121+
if (Min.sgt(Max)) {
122+
EXPECT_TRUE(CR.isEmptySet());
123+
return;
124+
}
125+
126+
ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
127+
if (CorrectnessOnly) {
128+
EXPECT_TRUE(CR.contains(Exact));
129+
} else {
130+
EXPECT_EQ(Exact, CR);
131+
}
122132
});
123133
}
124134

@@ -870,6 +880,79 @@ TEST_F(ConstantRangeTest, URem) {
870880
/* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
871881
}
872882

883+
TEST_F(ConstantRangeTest, SRem) {
884+
EXPECT_EQ(Full.srem(Empty), Empty);
885+
EXPECT_EQ(Empty.srem(Full), Empty);
886+
// srem by zero is UB.
887+
EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
888+
// srem by full range doesn't contain SignedMinValue.
889+
EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
890+
APInt::getSignedMinValue(16)));
891+
892+
ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
893+
ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
894+
ConstantRange IntMinMod(APInt::getSignedMinValue(16));
895+
896+
ConstantRange Expected(16, true);
897+
898+
// srem is bounded by abs(RHS) minus one.
899+
ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
900+
Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
901+
EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
902+
EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
903+
ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
904+
Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
905+
EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
906+
EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
907+
ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
908+
Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
909+
EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
910+
EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
911+
912+
// srem is bounded by LHS.
913+
ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
914+
EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
915+
EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
916+
EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
917+
ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
918+
EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
919+
EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
920+
EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
921+
ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
922+
EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
923+
EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
924+
EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
925+
926+
// srem is LHS if it is smaller than RHS.
927+
ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
928+
EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
929+
EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
930+
EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
931+
ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
932+
EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
933+
EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
934+
EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
935+
ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
936+
EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
937+
EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
938+
EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
939+
940+
// Example of a suboptimal result:
941+
// [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
942+
EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
943+
.srem(ConstantRange(APInt(16, 10))),
944+
ConstantRange(APInt(16, 0), APInt(16, 10)));
945+
946+
TestSignedBinOpExhaustive(
947+
[](const ConstantRange &CR1, const ConstantRange &CR2) {
948+
return CR1.srem(CR2);
949+
},
950+
[](const APInt &N1, const APInt &N2) {
951+
return N1.srem(N2);
952+
},
953+
/* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
954+
}
955+
873956
TEST_F(ConstantRangeTest, Shl) {
874957
ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
875958
ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));

0 commit comments

Comments
 (0)