PR1255: case ranges.
[oota-llvm.git] / include / llvm / Support / IntegersSubsetMapping.h
1 //===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// @file
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.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #ifndef CRSBUILDER_H_
20 #define CRSBUILDER_H_
21
22 #include "llvm/Support/IntegersSubset.h"
23 #include <list>
24 #include <map>
25 #include <vector>
26
27 namespace llvm {
28
29 template <class SuccessorClass,
30           class IntegersSubsetTy = IntegersSubset,
31           class IntTy = IntItem>
32 class IntegersSubsetMapping {
33 public:
34   
35   typedef IntRange<IntTy> RangeTy;
36   
37   struct RangeEx : public RangeTy {
38     RangeEx() : Weight(1) {}
39     RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
40     RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
41     RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
42     RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
43       RangeTy(L, H), Weight(W) {}
44     unsigned Weight;
45   };
46
47   typedef std::pair<RangeEx, SuccessorClass*> Cluster;
48
49 protected:
50
51   typedef std::vector<Cluster> CaseItems;
52   typedef typename CaseItems::iterator CaseItemIt;
53   typedef typename CaseItems::const_iterator CaseItemConstIt;
54   
55   typedef std::list<RangeTy> RangesCollection;
56   typedef typename RangesCollection::iterator RangesCollectionIt;
57   
58   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
59   typedef typename CRSMap::iterator CRSMapIt;
60
61   struct ClustersCmp {
62     bool operator()(const Cluster &C1, const Cluster &C2) {
63       return C1.first < C2.first;
64     }
65   };
66   
67   CaseItems Items;
68   bool Sorted;
69   
70   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
71     return LItem->first.getHigh() >= RItem->first.getLow();
72   }
73
74   bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
75     if (LItem->second != RItem->second) {
76       assert(!isIntersected(LItem, RItem) &&
77              "Intersected items with different successors!");
78       return false;
79     }
80     APInt RLow = RItem->first.getLow();
81     if (RLow != APInt::getNullValue(RLow.getBitWidth()))
82       --RLow;
83     return LItem->first.getHigh() >= RLow;
84   }
85   
86   void sort() {
87     if (!Sorted) {
88       std::sort(Items.begin(), Items.end(), ClustersCmp());
89       Sorted = true;
90     }
91   }
92   
93 public:
94   
95   // Don't public CaseItems itself. Don't allow edit the Items directly. 
96   // Just present the user way to iterate over the internal collection
97   // sharing iterator, begin() and end(). Editing should be controlled by
98   // factory.
99   typedef CaseItemIt RangeIterator;
100   
101   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
102   typedef std::list<Case> Cases;
103   
104   IntegersSubsetMapping() {
105     Items.reserve(32);
106     Sorted = false;
107   }
108   
109   bool verify(RangeIterator& errItem) {
110     if (Items.empty())
111       return true;
112     sort();
113     for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
114          j != e; i = j++) {
115       if (isIntersected(j, i) && j->second != i->second) {
116         errItem = j;
117         return false;
118       }
119     }
120     return true;
121   }
122   
123   void optimize() {
124     if (Items.size() < 2)
125       return;
126     sort();
127     CaseItems OldItems = Items;
128     Items.clear();
129     const IntTy *Low = &OldItems.begin()->first.getLow();
130     const IntTy *High = &OldItems.begin()->first.getHigh();
131     unsigned Weight = 1;
132     SuccessorClass *Successor = OldItems.begin()->second;
133     for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
134         j != e; i = j++) {
135       if (isJoinable(i, j)) {
136         const IntTy *CurHigh = &j->first.getHigh();
137         ++Weight;
138         if (*CurHigh > *High)
139           High = CurHigh;
140       } else {
141         RangeEx R(*Low, *High, Weight);
142         add(R, Successor);
143         Low = &j->first.getLow();
144         High = &j->first.getHigh(); 
145         Weight = 1;
146         Successor = j->second;
147       }
148     }
149     RangeEx R(*Low, *High, Weight);
150     add(R, Successor);
151     // We recollected the Items, but we kept it sorted.
152     Sorted = true;
153   }
154   
155   /// Adds a constant value.
156   void add(const IntTy &C, SuccessorClass *S = 0) {
157     RangeTy R(C);
158     add(R, S);
159   }
160   
161   /// Adds a range.
162   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
163     RangeTy R(Low, High);
164     add(R, S);
165   }
166   void add(const RangeTy &R, SuccessorClass *S = 0) {
167     RangeEx REx = R;
168     add(REx, S);
169   }   
170   void add(const RangeEx &R, SuccessorClass *S = 0) {
171     Items.push_back(std::make_pair(R, S));
172     Sorted = false;
173   }  
174   
175   /// Adds all ranges and values from given ranges set to the current
176   /// CRSBuilder object.
177   void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
178     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
179       RangeTy R = CRS.getItem(i);
180       add(R, S);
181     }
182   }
183   
184   /// Removes items from set.
185   void removeItem(RangeIterator i) { Items.erase(i); }
186   
187   /// Builds the finalized case objects.
188   void getCases(Cases& TheCases) {
189     CRSMap TheCRSMap;
190     for (RangeIterator i = this->begin(); i != this->end(); ++i)
191       TheCRSMap[i->second].push_back(i->first);
192     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
193       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
194   }
195   
196   /// Builds the finalized case objects ignoring successor values, as though
197   /// all ranges belongs to the same successor.
198   IntegersSubset getCase() {
199     RangesCollection Ranges;
200     for (RangeIterator i = this->begin(); i != this->end(); ++i)
201       Ranges.push_back(i->first);
202     return IntegersSubsetTy(Ranges);
203   }  
204   
205   /// Returns true if there is no ranges and values inside.
206   bool empty() const { return Items.empty(); }
207   
208   RangeIterator begin() { return Items.begin(); }
209   RangeIterator end() { return Items.end(); }
210 };
211
212 class BasicBlock;
213 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
214
215 }
216
217 #endif /* CRSBUILDER_H_ */