1 //===- ConstantRangeListTest.cpp - ConstantRangeList tests ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/IR/ConstantRangeList.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13
14 namespace {
15
16 using ConstantRangeListTest = ::testing::Test;
17
TEST_F(ConstantRangeListTest,Basics)18 TEST_F(ConstantRangeListTest, Basics) {
19 ConstantRangeList CRL1a;
20 CRL1a.insert(0, 12);
21 EXPECT_FALSE(CRL1a.empty());
22
23 ConstantRangeList CRL1b;
24 CRL1b.insert(0, 4);
25 CRL1b.insert(4, 8);
26 CRL1b.insert(8, 12);
27 EXPECT_TRUE(CRL1a == CRL1b);
28
29 ConstantRangeList CRL1c;
30 CRL1c.insert(0, 4);
31 CRL1c.insert(8, 12);
32 CRL1c.insert(4, 8);
33 EXPECT_TRUE(CRL1a == CRL1c);
34
35 ConstantRangeList CRL2;
36 CRL2.insert(-4, 0);
37 CRL2.insert(8, 12);
38 EXPECT_TRUE(CRL1a != CRL2);
39 }
40
TEST_F(ConstantRangeListTest,getConstantRangeList)41 TEST_F(ConstantRangeListTest, getConstantRangeList) {
42 SmallVector<ConstantRange, 2> Empty;
43 EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Empty).has_value());
44
45 SmallVector<ConstantRange, 2> Valid;
46 Valid.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
47 Valid.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 12, true)));
48 EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Valid).has_value());
49
50 SmallVector<ConstantRange, 2> Invalid1;
51 Invalid1.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 0, true)));
52 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid1), std::nullopt);
53
54 SmallVector<ConstantRange, 2> Invalid2;
55 Invalid2.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
56 Invalid2.push_back(ConstantRange(APInt(64, 12, true), APInt(64, 8, true)));
57 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid2), std::nullopt);
58
59 SmallVector<ConstantRange, 2> Invalid3;
60 Invalid3.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
61 Invalid3.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 8, true)));
62 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid3), std::nullopt);
63
64 SmallVector<ConstantRange, 2> Invalid4;
65 Invalid4.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 12, true)));
66 Invalid4.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 16, true)));
67 EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid4), std::nullopt);
68 }
69
TEST_F(ConstantRangeListTest,Insert)70 TEST_F(ConstantRangeListTest, Insert) {
71 ConstantRangeList CRL;
72 CRL.insert(0, 4);
73 CRL.insert(8, 12);
74 // No overlap, left
75 CRL.insert(-8, -4);
76 // No overlap, right
77 CRL.insert(16, 20);
78 // No overlap, middle
79 CRL.insert(13, 15);
80 // Overlap with left
81 CRL.insert(-6, -2);
82 // Overlap with right
83 CRL.insert(5, 9);
84 // Overlap with left and right
85 CRL.insert(14, 18);
86 // Overlap cross ranges
87 CRL.insert(2, 14);
88 // An existing range
89 CRL.insert(0, 20);
90
91 ConstantRangeList Expected;
92 Expected.insert(-8, -2);
93 Expected.insert(0, 20);
94 EXPECT_TRUE(CRL == Expected);
95 }
96
GetCRL(ArrayRef<std::pair<APInt,APInt>> Pairs)97 ConstantRangeList GetCRL(ArrayRef<std::pair<APInt, APInt>> Pairs) {
98 SmallVector<ConstantRange, 2> Ranges;
99 for (auto &[Start, End] : Pairs)
100 Ranges.push_back(ConstantRange(Start, End));
101 return ConstantRangeList(Ranges);
102 }
103
TEST_F(ConstantRangeListTest,Subtract)104 TEST_F(ConstantRangeListTest, Subtract) {
105 APInt AP0 = APInt(64, 0, /*isSigned=*/true);
106 APInt AP2 = APInt(64, 2, /*isSigned=*/true);
107 APInt AP3 = APInt(64, 3, /*isSigned=*/true);
108 APInt AP4 = APInt(64, 4, /*isSigned=*/true);
109 APInt AP8 = APInt(64, 8, /*isSigned=*/true);
110 APInt AP10 = APInt(64, 10, /*isSigned=*/true);
111 APInt AP11 = APInt(64, 11, /*isSigned=*/true);
112 APInt AP12 = APInt(64, 12, /*isSigned=*/true);
113 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
114
115 // Execute ConstantRangeList::subtract(ConstantRange) and check the result
116 // is expected. Pass "CRL" by value so that subtract() does not affect the
117 // argument in caller.
118 auto SubtractAndCheck = [](ConstantRangeList CRL,
119 const std::pair<int64_t, int64_t> &Range,
120 const ConstantRangeList &ExpectedCRL) {
121 CRL.subtract(ConstantRange(APInt(64, Range.first, /*isSigned=*/true),
122 APInt(64, Range.second, /*isSigned=*/true)));
123 EXPECT_EQ(CRL, ExpectedCRL);
124 };
125
126 // No overlap
127 SubtractAndCheck(CRL, {-4, 0}, CRL);
128 SubtractAndCheck(CRL, {4, 8}, CRL);
129 SubtractAndCheck(CRL, {12, 16}, CRL);
130
131 // Overlap (left, right, or both)
132 SubtractAndCheck(CRL, {-4, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));
133 SubtractAndCheck(CRL, {-4, 4}, GetCRL({{AP8, AP12}}));
134 SubtractAndCheck(CRL, {-4, 8}, GetCRL({{AP8, AP12}}));
135 SubtractAndCheck(CRL, {0, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));
136 SubtractAndCheck(CRL, {0, 4}, GetCRL({{AP8, AP12}}));
137 SubtractAndCheck(CRL, {0, 8}, GetCRL({{AP8, AP12}}));
138 SubtractAndCheck(CRL, {10, 12}, GetCRL({{AP0, AP4}, {AP8, AP10}}));
139 SubtractAndCheck(CRL, {8, 12}, GetCRL({{AP0, AP4}}));
140 SubtractAndCheck(CRL, {6, 12}, GetCRL({{AP0, AP4}}));
141 SubtractAndCheck(CRL, {10, 16}, GetCRL({{AP0, AP4}, {AP8, AP10}}));
142 SubtractAndCheck(CRL, {8, 16}, GetCRL({{AP0, AP4}}));
143 SubtractAndCheck(CRL, {6, 16}, GetCRL({{AP0, AP4}}));
144 SubtractAndCheck(CRL, {2, 10}, GetCRL({{AP0, AP2}, {AP10, AP12}}));
145
146 // Subset
147 SubtractAndCheck(CRL, {2, 3}, GetCRL({{AP0, AP2}, {AP3, AP4}, {AP8, AP12}}));
148 SubtractAndCheck(CRL, {10, 11},
149 GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}}));
150
151 // Superset
152 SubtractAndCheck(CRL, {0, 12}, GetCRL({}));
153 SubtractAndCheck(CRL, {-4, 16}, GetCRL({}));
154 }
155
TEST_F(ConstantRangeListTest,Union)156 TEST_F(ConstantRangeListTest, Union) {
157 APInt APN4 = APInt(64, -4, /*isSigned=*/true);
158 APInt APN2 = APInt(64, -2, /*isSigned=*/true);
159 APInt AP0 = APInt(64, 0, /*isSigned=*/true);
160 APInt AP2 = APInt(64, 2, /*isSigned=*/true);
161 APInt AP4 = APInt(64, 4, /*isSigned=*/true);
162 APInt AP6 = APInt(64, 6, /*isSigned=*/true);
163 APInt AP7 = APInt(64, 7, /*isSigned=*/true);
164 APInt AP8 = APInt(64, 8, /*isSigned=*/true);
165 APInt AP10 = APInt(64, 10, /*isSigned=*/true);
166 APInt AP11 = APInt(64, 11, /*isSigned=*/true);
167 APInt AP12 = APInt(64, 12, /*isSigned=*/true);
168 APInt AP16 = APInt(64, 16, /*isSigned=*/true);
169 APInt AP18 = APInt(64, 18, /*isSigned=*/true);
170 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
171
172 // Union with a subset.
173 ConstantRangeList Empty;
174 EXPECT_EQ(CRL.unionWith(Empty), CRL);
175 EXPECT_EQ(Empty.unionWith(CRL), CRL);
176
177 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}})), CRL);
178 EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP12}})), CRL);
179
180 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP8, AP10}})), CRL);
181 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP10, AP12}})), CRL);
182 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP8, AP10}})), CRL);
183 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP10, AP12}})), CRL);
184
185 EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}})),
186 CRL);
187
188 EXPECT_EQ(CRL.unionWith(CRL), CRL);
189
190 // Union with new ranges.
191 EXPECT_EQ(CRL.unionWith(GetCRL({{APN4, APN2}})),
192 GetCRL({{APN4, APN2}, {AP0, AP4}, {AP8, AP12}}));
193 EXPECT_EQ(CRL.unionWith(GetCRL({{AP6, AP7}})),
194 GetCRL({{AP0, AP4}, {AP6, AP7}, {AP8, AP12}}));
195 EXPECT_EQ(CRL.unionWith(GetCRL({{AP16, AP18}})),
196 GetCRL({{AP0, AP4}, {AP8, AP12}, {AP16, AP18}}));
197
198 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP2}})),
199 GetCRL({{APN2, AP4}, {AP8, AP12}}));
200 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP6}})),
201 GetCRL({{AP0, AP6}, {AP8, AP12}}));
202 EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP16}})),
203 GetCRL({{AP0, AP4}, {AP8, AP16}}));
204
205 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP10}})), GetCRL({{APN2, AP12}}));
206 EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP10}})), GetCRL({{AP0, AP12}}));
207 EXPECT_EQ(CRL.unionWith(GetCRL({{AP4, AP16}})), GetCRL({{AP0, AP16}}));
208 EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP16}})), GetCRL({{APN2, AP16}}));
209 }
210
TEST_F(ConstantRangeListTest,Intersect)211 TEST_F(ConstantRangeListTest, Intersect) {
212 APInt APN2 = APInt(64, -2, /*isSigned=*/true);
213 APInt AP0 = APInt(64, 0, /*isSigned=*/true);
214 APInt AP2 = APInt(64, 2, /*isSigned=*/true);
215 APInt AP4 = APInt(64, 4, /*isSigned=*/true);
216 APInt AP6 = APInt(64, 6, /*isSigned=*/true);
217 APInt AP7 = APInt(64, 7, /*isSigned=*/true);
218 APInt AP8 = APInt(64, 8, /*isSigned=*/true);
219 APInt AP10 = APInt(64, 10, /*isSigned=*/true);
220 APInt AP11 = APInt(64, 11, /*isSigned=*/true);
221 APInt AP12 = APInt(64, 12, /*isSigned=*/true);
222 APInt AP16 = APInt(64, 16, /*isSigned=*/true);
223 ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
224
225 // No intersection.
226 ConstantRangeList Empty;
227 EXPECT_EQ(CRL.intersectWith(Empty), Empty);
228 EXPECT_EQ(Empty.intersectWith(CRL), Empty);
229
230 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP0}})), Empty);
231 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP8}})), Empty);
232 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP12, AP16}})), Empty);
233
234 // Single intersect range.
235 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}})), GetCRL({{AP0, AP2}}));
236 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP6}})), GetCRL({{AP0, AP4}}));
237 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP4}})), GetCRL({{AP2, AP4}}));
238 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}})), GetCRL({{AP2, AP4}}));
239 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP10}})), GetCRL({{AP8, AP10}}));
240 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP16}})), GetCRL({{AP8, AP12}}));
241 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP12}})), GetCRL({{AP10, AP12}}));
242 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP16}})), GetCRL({{AP10, AP12}}));
243
244 // Multiple intersect ranges.
245 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP10}})),
246 GetCRL({{AP0, AP4}, {AP8, AP10}}));
247 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP16}})), CRL);
248 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP10}})),
249 GetCRL({{AP2, AP4}, {AP8, AP10}}));
250 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP16}})),
251 GetCRL({{AP2, AP4}, {AP8, AP12}}));
252 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP6, AP10}})),
253 GetCRL({{AP0, AP2}, {AP8, AP10}}));
254 EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}, {AP10, AP16}})),
255 GetCRL({{AP2, AP4}, {AP10, AP12}}));
256 EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP7, AP10}, {AP11, AP16}})),
257 GetCRL({{AP0, AP2}, {AP8, AP10}, {AP11, AP12}}));
258 EXPECT_EQ(CRL.intersectWith(CRL), CRL);
259 }
260
261 } // anonymous namespace
262