1 //===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// CRSBuilder allows to build and parse ConstantRangesSet objects.
12 /// There is such features like add/remove range, or combine
13 /// Two ConstantRangesSet object with neighboring ranges merging.
14 /// Set IsReadonly=true if you want to operate with "const ConstantInt" and
15 /// "const ConstantRangesSet" objects.
17 //===----------------------------------------------------------------------===//
22 #include "llvm/ConstantRangesSet.h"
29 template <class SuccessorClass, bool IsReadonly>
30 class CRSBuilderBase {
33 typedef ConstantRangesSet::RangeT<IsReadonly> RangeTy;
35 struct RangeEx : public RangeTy {
36 typedef ConstantRangesSet::RangeT<IsReadonly> RangeTy;
37 typedef typename RangeTy::ConstantIntTy ConstantIntTy;
38 RangeEx() : Weight(1) {}
39 RangeEx(const RangeTy &R) : RangeTy(R.Low, R.High), Weight(1) {}
40 RangeEx(ConstantIntTy *C) : RangeTy(C), Weight(1) {}
41 RangeEx(ConstantIntTy *L, ConstantIntTy *H) : RangeTy(L, H), Weight(1) {}
42 RangeEx(ConstantIntTy *L, ConstantIntTy *H, unsigned W) :
43 RangeTy(L, H), Weight(W) {}
47 typedef std::pair<RangeEx, SuccessorClass*> Cluster;
51 typedef std::vector<Cluster> CaseItems;
52 typedef typename CaseItems::iterator CaseItemIt;
53 typedef typename CaseItems::const_iterator CaseItemConstIt;
56 bool operator()(const Cluster &C1, const Cluster &C2) {
57 return C1.first < C2.first;
64 bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
65 return LItem->first.High->getValue().uge(RItem->first.Low->getValue());
68 bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
69 if (LItem->second != RItem->second) {
70 assert(!isIntersected(LItem, RItem) &&
71 "Intersected items with different successors!");
74 APInt RLow = RItem->first.Low->getValue();
75 if (RLow != APInt::getNullValue(RLow.getBitWidth()))
77 return LItem->first.High->getValue().uge(RLow);
82 std::sort(Items.begin(), Items.end(), ClustersCmp());
89 typedef typename CRSConstantTypes<IsReadonly>::ConstantIntTy ConstantIntTy;
90 typedef typename CRSConstantTypes<IsReadonly>::ConstantRangesSetTy ConstantRangesSetTy;
92 // Don't public CaseItems itself. Don't allow edit the Items directly.
93 // Just present the user way to iterate over the internal collection
94 // sharing iterator, begin() and end(). Editing should be controlled by
96 typedef CaseItemIt RangeIterator;
107 for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
109 if (isIntersected(j, i) && j->second != i->second)
116 if (Items.size() < 2)
119 CaseItems OldItems = Items;
121 ConstantIntTy *Low = OldItems.begin()->first.Low;
122 ConstantIntTy *High = OldItems.begin()->first.High;
124 SuccessorClass *Successor = OldItems.begin()->second;
125 for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
127 if (isJoinable(i, j)) {
128 ConstantIntTy *CurHigh = j->first.High;
130 if (CurHigh->getValue().ugt(High->getValue()))
133 RangeEx R(Low, High, Weight);
136 High = j->first.High;
138 Successor = j->second;
141 RangeEx R(Low, High, Weight);
143 // We recollected the Items, but we kept it sorted.
147 /// Adds a constant value.
148 void add(ConstantIntTy *C, SuccessorClass *S = 0) {
154 void add(ConstantIntTy *Low, ConstantIntTy *High, SuccessorClass *S = 0) {
155 RangeTy R(Low, High);
158 void add(RangeTy &R, SuccessorClass *S = 0) {
162 void add(RangeEx &R, SuccessorClass *S = 0) {
163 Items.push_back(std::make_pair(R, S));
167 /// Adds all ranges and values from given ranges set to the current
168 /// CRSBuilder object.
169 void add(ConstantRangesSetTy &CRS, SuccessorClass *S = 0) {
170 for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
171 RangeTy R = CRS.getItem(i);
176 /// Removes items from set.
177 void removeItem(RangeIterator i) { Items.erase(i); }
179 /// Returns true if there is no ranges and values inside.
180 bool empty() const { return Items.empty(); }
182 RangeIterator begin() { return Items.begin(); }
183 RangeIterator end() { return Items.end(); }
186 template <class SuccessorClass>
187 class CRSBuilderT : public CRSBuilderBase<SuccessorClass, false> {
189 typedef typename CRSBuilderBase<SuccessorClass, false>::RangeTy RangeTy;
190 typedef typename CRSBuilderBase<SuccessorClass, false>::RangeIterator
193 typedef std::list<RangeTy> RangesCollection;
194 typedef typename RangesCollection::iterator RangesCollectionIt;
196 typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
197 typedef typename CRSMap::iterator CRSMapIt;
199 ConstantRangesSet getCase(RangesCollection& Src) {
200 std::vector<Constant*> Elts;
201 Elts.reserve(Src.size());
202 for (RangesCollectionIt i = Src.begin(), e = Src.end(); i != e; ++i) {
203 const RangeTy &R = *i;
204 std::vector<Constant*> r;
205 if (R.Low != R.High) {
213 Constant *CV = ConstantVector::get(r);
217 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
218 Constant *Array = ConstantArray::get(ArrTy, Elts);
219 return ConstantRangesSet(Array);
224 typedef std::pair<SuccessorClass*, ConstantRangesSet> Case;
225 typedef std::list<Case> Cases;
227 /// Builds the finalized case objects.
228 void getCases(Cases& TheCases) {
230 for (RangeIterator i = this->begin(); i != this->end(); ++i)
231 TheCRSMap[i->second].push_back(i->first);
232 for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
233 TheCases.push_back(std::make_pair(i->first, getCase(i->second)));
236 /// Builds the finalized case objects ignoring successor values, as though
237 /// all ranges belongs to the same successor.
238 ConstantRangesSet getCase() {
239 RangesCollection Ranges;
240 for (RangeIterator i = this->begin(); i != this->end(); ++i)
241 Ranges.push_back(i->first);
242 return getCase(Ranges);
247 typedef CRSBuilderT<BasicBlock> CRSBuilder;
248 typedef CRSBuilderBase<BasicBlock, true> CRSBuilderConst;
252 #endif /* CRSBUILDER_H_ */