aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Support/IntegersSubset.h45
-rw-r--r--include/llvm/Support/IntegersSubsetMapping.h18
-rw-r--r--unittests/Support/IntegersSubsetTest.cpp180
3 files changed, 223 insertions, 20 deletions
diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h
index ac4eb97a3a..998cc73c84 100644
--- a/include/llvm/Support/IntegersSubset.h
+++ b/include/llvm/Support/IntegersSubset.h
@@ -1,4 +1,4 @@
-//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- C++ -*-===//
+//===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
@@ -9,10 +9,9 @@
//
/// @file
/// This file contains class that implements constant set of ranges:
-/// [<Low0,High0>,...,<LowN,HighN>]. Mainly, this set is used by SwitchInst and
-/// represents case value that may contain multiple ranges for a single
-/// successor.
-///
+/// [<Low0,High0>,...,<LowN,HighN>]. Initially, this class was created for
+/// SwitchInst and was used for case value representation that may contain
+/// multiple ranges for a single successor.
//
//===----------------------------------------------------------------------===//
@@ -280,7 +279,9 @@ public:
typedef std::list<IntTy> FlatCollectionTy;
typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
- typedef typename RangeLinksTy::iterator RangeLinksConstIt;
+ typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
+
+ typedef IntegersSubsetGeneric<IntTy> self;
protected:
@@ -304,6 +305,26 @@ public:
}
}
+ IntegersSubsetGeneric(const self& RHS) {
+ *this = RHS;
+ }
+
+ self& operator=(const self& RHS) {
+ FlatCollection.clear();
+ RangeLinks.clear();
+ for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
+ i != e; ++i) {
+ RangeLinkTy RangeLink;
+ FlatCollection.push_back(*(i->first));
+ RangeLink.first = &FlatCollection.back();
+ if (i->first != i->second)
+ FlatCollection.push_back(*(i->second));
+ RangeLink.second = &FlatCollection.back();
+ RangeLinks.push_back(RangeLink);
+ }
+ return *this;
+ }
+
typedef IntRange<IntTy> Range;
/// Checks is the given constant satisfies this case. Returns
@@ -314,8 +335,8 @@ public:
if (RangeLinks[i].first == RangeLinks[i].second) {
if (*RangeLinks[i].first == CheckingVal)
return true;
- } else if (*RangeLinks[i].first >= CheckingVal &&
- *RangeLinks[i].second <= CheckingVal)
+ } else if (*RangeLinks[i].first <= CheckingVal &&
+ *RangeLinks[i].second >= CheckingVal)
return true;
}
return false;
@@ -357,7 +378,7 @@ public:
for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
const APInt &Low = getItem(i).getLow();
const APInt &High = getItem(i).getHigh();
- const APInt &S = High - Low;
+ APInt S = High - Low + 1;
sz += S;
}
return sz.getZExtValue();
@@ -372,12 +393,12 @@ public:
for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
const APInt &Low = getItem(i).getLow();
const APInt &High = getItem(i).getHigh();
- const APInt& S = High - Low;
+ APInt S = High - Low + 1;
APInt oldSz = sz;
sz += S;
- if (oldSz.uge(i) && sz.ult(i)) {
+ if (sz.ugt(idx)) {
APInt Res = Low;
- APInt Offset(oldSz.getBitWidth(), i);
+ APInt Offset(oldSz.getBitWidth(), idx);
Offset -= oldSz;
Res += Offset;
return Res;
diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index b630119aea..d3d11f03ba 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -1,4 +1,4 @@
-//===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===//
+//===- IntegersSubsetMapping.h - Mapping subset ==> Successor ---*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
@@ -8,11 +8,12 @@
//===----------------------------------------------------------------------===//
//
/// @file
-/// CRSBuilder allows to build and parse ConstantRangesSet objects.
-/// There is such features like add/remove range, or combine
-/// Two ConstantRangesSet object with neighboring ranges merging.
-/// Set IsReadonly=true if you want to operate with "const ConstantInt" and
-/// "const ConstantRangesSet" objects.
+/// IntegersSubsetMapping is mapping from A to B, where
+/// Items in A is subsets of integers,
+/// Items in B some pointers (Successors).
+/// If user which to add another subset for successor that is already
+/// exists in mapping, IntegersSubsetMapping merges existing subset with
+/// added one.
//
//===----------------------------------------------------------------------===//
@@ -55,6 +56,7 @@ protected:
typedef std::list<RangeTy> RangesCollection;
typedef typename RangesCollection::iterator RangesCollectionIt;
+ // TODO: Change unclean CRS prefixes to SubsetMap for example.
typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
typedef typename CRSMap::iterator CRSMapIt;
@@ -112,7 +114,7 @@ public:
sort();
for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
j != e; i = j++) {
- if (isIntersected(j, i) && j->second != i->second) {
+ if (isIntersected(i, j) && i->second != j->second) {
errItem = j;
return false;
}
@@ -173,7 +175,7 @@ public:
}
/// Adds all ranges and values from given ranges set to the current
- /// CRSBuilder object.
+ /// mapping.
void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
RangeTy R = CRS.getItem(i);
diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp
new file mode 100644
index 0000000000..5de1f7c221
--- /dev/null
+++ b/unittests/Support/IntegersSubsetTest.cpp
@@ -0,0 +1,180 @@
+//===- llvm/unittest/Support/IntegersSubsetTest.cpp - IntegersSubset tests ===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/APInt.h"
+#include "llvm/Support/IntegersSubset.h"
+#include "llvm/Support/IntegersSubsetMapping.h"
+
+#include "gtest/gtest.h"
+
+#include <vector>
+
+using namespace llvm;
+
+namespace {
+
+ class Int : public APInt {
+ public:
+ Int(uint64_t V) : APInt(64, V) {}
+ bool operator < (const APInt& RHS) const { return ult(RHS); }
+ bool operator > (const APInt& RHS) const { return ugt(RHS); }
+ bool operator <= (const APInt& RHS) const { return ule(RHS); }
+ bool operator >= (const APInt& RHS) const { return uge(RHS); }
+ };
+
+ typedef IntRange<Int> Range;
+ typedef IntegersSubsetGeneric<Int> Subset;
+ typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
+
+ TEST(IntegersSubsetTest, GeneralTest) {
+
+ // Test construction.
+
+ std::vector<Range> Ranges;
+ Ranges.reserve(3);
+
+ // Initialize Subset as union of three pairs:
+ // { {0, 8}, {10, 18}, {20, 28} }
+ for (unsigned i = 0; i < 3; ++i)
+ Ranges.push_back(Range(Int(i*10), Int(i*10 + 8)));
+
+ Subset TheSubset(Ranges);
+
+ for (unsigned i = 0; i < 3; ++i) {
+ EXPECT_EQ(TheSubset.getItem(i).getLow(), Int(i*10));
+ EXPECT_EQ(TheSubset.getItem(i).getHigh(), Int(i*10 + 8));
+ }
+
+ EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
+
+ // Test belonging to range.
+
+ EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
+ EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
+
+ // Test when subset contains the only item.
+
+ Ranges.clear();
+ Ranges.push_back(Range(Int(10), Int(10)));
+
+ Subset TheSingleNumber(Ranges);
+
+ EXPECT_TRUE(TheSingleNumber.isSingleNumber());
+
+ Ranges.push_back(Range(Int(12), Int(15)));
+
+ Subset NotASingleNumber(Ranges);
+
+ EXPECT_FALSE(NotASingleNumber.isSingleNumber());
+
+ // Test when subset contains items that are not a ranges but
+ // the single numbers.
+
+ Ranges.clear();
+ Ranges.push_back(Range(Int(10), Int(10)));
+ Ranges.push_back(Range(Int(15), Int(19)));
+
+ Subset WithSingleNumberItems(Ranges);
+
+ EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
+ EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
+
+ // Test size of subset. Note subset itself may be not optimized (improper),
+ // so it may contain duplicates, and the size of subset { {0, 9} {5, 9} }
+ // will 15 instead of 10.
+
+ Ranges.clear();
+ Ranges.push_back(Range(Int(0), Int(9)));
+ Ranges.push_back(Range(Int(5), Int(9)));
+
+ Subset NotOptimizedSubset(Ranges);
+
+ EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
+
+ // Test access to a single value.
+ // getSingleValue(idx) method represents subset as flat numbers collection,
+ // so subset { {0, 3}, {8, 10} } will represented as array
+ // { 0, 1, 2, 3, 8, 9, 10 }.
+
+ Ranges.clear();
+ Ranges.push_back(Range(Int(0), Int(3)));
+ Ranges.push_back(Range(Int(8), Int(10)));
+
+ Subset OneMoreSubset(Ranges);
+
+ EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
+ }
+
+ TEST(IntegersSubsetTest, MappingTest) {
+
+ Mapping::Cases TheCases;
+
+ unsigned Successors[3] = {0, 1, 2};
+
+ // Test construction.
+
+ Mapping TheMapping;
+ for (unsigned i = 0; i < 3; ++i)
+ TheMapping.add(Int(10*i), Int(10*i + 9), Successors + i);
+ TheMapping.add(Int(111), Int(222), Successors);
+ TheMapping.removeItem(--TheMapping.end());
+
+ TheMapping.getCases(TheCases);
+
+ EXPECT_EQ(TheCases.size(), 3ULL);
+
+ for (unsigned i = 0; i < 3; ++i) {
+ Mapping::Cases::iterator CaseIt = TheCases.begin();
+ std::advance(CaseIt, i);
+ EXPECT_EQ(CaseIt->first, Successors + i);
+ EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
+ EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(10*i), Int(10*i + 9)));
+ }
+
+ // Test verification.
+
+ Mapping ImproperMapping;
+ ImproperMapping.add(Int(10), Int(11), Successors + 0);
+ ImproperMapping.add(Int(11), Int(12), Successors + 1);
+
+ Mapping::RangeIterator ErrItem;
+ EXPECT_FALSE(ImproperMapping.verify(ErrItem));
+ EXPECT_EQ(ErrItem, --ImproperMapping.end());
+
+ Mapping ProperMapping;
+ ProperMapping.add(Int(10), Int(11), Successors + 0);
+ ProperMapping.add(Int(12), Int(13), Successors + 1);
+
+ EXPECT_TRUE(ProperMapping.verify(ErrItem));
+
+ // Test optimization.
+
+ Mapping ToBeOptimized;
+
+ for (unsigned i = 0; i < 3; ++i) {
+ ToBeOptimized.add(Int(i * 10), Int(i * 10 + 1), Successors + i);
+ ToBeOptimized.add(Int(i * 10 + 2), Int(i * 10 + 9), Successors + i);
+ }
+
+ ToBeOptimized.optimize();
+
+ TheCases.clear();
+ ToBeOptimized.getCases(TheCases);
+
+ EXPECT_EQ(TheCases.size(), 3ULL);
+
+ for (unsigned i = 0; i < 3; ++i) {
+ Mapping::Cases::iterator CaseIt = TheCases.begin();
+ std::advance(CaseIt, i);
+ EXPECT_EQ(CaseIt->first, Successors + i);
+ EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
+ EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9)));
+ }
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-24 23:04:45 +0000