struct RangeEx : public RangeTy {
RangeEx() : Weight(1) {}
RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
+ RangeEx(const RangeTy &R, unsigned W) : RangeTy(R), Weight(W) {}
RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
protected:
- typedef std::map<RangeEx, SuccessorClass*> CaseItems;
+ typedef std::list<Cluster> CaseItems;
typedef typename CaseItems::iterator CaseItemIt;
typedef typename CaseItems::const_iterator CaseItemConstIt;
// TODO: Change unclean CRS prefixes to SubsetMap for example.
typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
typedef typename CRSMap::iterator CRSMapIt;
+
+ struct ClustersCmp {
+ bool operator()(const Cluster &C1, const Cluster &C2) {
+ return C1.first < C2.first;
+ }
+ };
CaseItems Items;
- bool SingleNumbersOnly;
+ bool Sorted;
bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
return LItem->first.getHigh() >= RItem->first.getLow();
return LItem->first.getHigh() >= RLow;
}
+ void sort() {
+ if (!Sorted) {
+ std::vector<Cluster> clustersVector;
+ clustersVector.reserve(Items.size());
+ clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
+ std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
+ Items.clear();
+ Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
+ Sorted = true;
+ }
+ }
+
enum DiffProcessState {
L_OPENED,
INTERSECT_OPENED,
}
}
- void onRLOpen(const IntTy &Pt,
+ void onLROpen(const IntTy &Pt,
SuccessorClass *LS,
SuccessorClass *RS) {
switch (State) {
OpenPt = Pt;
}
- void onRLClose(const IntTy &Pt) {
+ void onLRClose(const IntTy &Pt) {
switch (State) {
case INTERSECT_OPENED:
if (IntersectionMapping)
bool isLOpened() { return State == L_OPENED; }
bool isROpened() { return State == R_OPENED; }
};
-
- void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude,
- const self& RHS) {
-
- CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
- CaseItemConstIt el = Items.end(), er = RHS.Items.end();
- while (L != el && R != er) {
- const Cluster &LCluster = *L;
- const RangeEx &LRange = LCluster.first;
- const Cluster &RCluster = *R;
- const RangeEx &RRange = RCluster.first;
-
- if (LRange.getLow() < RRange.getLow()) {
- if (LExclude)
- LExclude->add(LRange.getLow(), LCluster.second);
- ++L;
- } else if (LRange.getLow() > RRange.getLow()) {
- if (RExclude)
- RExclude->add(RRange.getLow(), RCluster.second);
- ++R;
- } else {
- if (Intersection)
- Intersection->add(LRange.getLow(), LCluster.second);
- ++L;
- ++R;
- }
- }
-
- if (L != Items.end()) {
- if (LExclude)
- do {
- LExclude->add(L->first, L->second);
- ++L;
- } while (L != Items.end());
- } else if (R != RHS.Items.end()) {
- if (RExclude)
- do {
- RExclude->add(R->first, R->second);
- ++R;
- } while (R != RHS.Items.end());
- }
- }
public:
typedef std::list<Case> Cases;
typedef typename Cases::iterator CasesIt;
- IntegersSubsetMapping() : SingleNumbersOnly(true) {}
+ IntegersSubsetMapping() {
+ Sorted = false;
+ }
bool verify() {
RangeIterator DummyErrItem;
bool verify(RangeIterator& errItem) {
if (Items.empty())
return true;
+ sort();
for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
j != e; i = j++) {
if (isIntersected(i, j) && i->second != j->second) {
void optimize() {
if (Items.size() < 2)
return;
+ sort();
CaseItems OldItems = Items;
Items.clear();
const IntTy *Low = &OldItems.begin()->first.getLow();
const IntTy *High = &OldItems.begin()->first.getHigh();
- unsigned Weight = 1;
+ unsigned Weight = OldItems.begin()->first.Weight;
SuccessorClass *Successor = OldItems.begin()->second;
for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
j != e; i = j++) {
if (isJoinable(i, j)) {
const IntTy *CurHigh = &j->first.getHigh();
- ++Weight;
+ Weight += j->first.Weight;
if (*CurHigh > *High)
High = CurHigh;
} else {
add(R, Successor);
Low = &j->first.getLow();
High = &j->first.getHigh();
- Weight = 1;
+ Weight = j->first.Weight;
Successor = j->second;
}
}
RangeEx R(*Low, *High, Weight);
add(R, Successor);
+ // We recollected the Items, but we kept it sorted.
+ Sorted = true;
}
/// Adds a constant value.
add(REx, S);
}
void add(const RangeEx &R, SuccessorClass *S = 0) {
- Items.insert(std::make_pair(R, S));
- if (!R.isSingleNumber())
- SingleNumbersOnly = false;
+ Items.push_back(std::make_pair(R, S));
+ Sorted = false;
}
/// Adds all ranges and values from given ranges set to the current
/// mapping.
- void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
+ void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0,
+ unsigned Weight = 0) {
+ unsigned ItemWeight = 1;
+ if (Weight)
+ // Weight is associated with CRS, for now we perform a division to
+ // get the weight for each item.
+ ItemWeight = Weight / CRS.getNumItems();
for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
RangeTy R = CRS.getItem(i);
- add(R, S);
+ RangeEx REx(R, ItemWeight);
+ add(REx, S);
}
}
void add(self& RHS) {
- Items.insert(RHS.Items.begin(), RHS.Items.end());
- if (!RHS.SingleNumbersOnly)
- SingleNumbersOnly = false;
+ Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
}
void add(self& RHS, SuccessorClass *S) {
void diff(self *LExclude, self *Intersection, self *RExclude,
const self& RHS) {
- if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
- diff_single_numbers(LExclude, Intersection, RExclude, RHS);
- return;
- }
-
DiffStateMachine Machine(LExclude, Intersection, RExclude);
CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
- CaseItemConstIt el = Items.end(), er = RHS.Items.end();
- while (L != el && R != er) {
+ while (L != Items.end() && R != RHS.Items.end()) {
const Cluster &LCluster = *L;
const RangeEx &LRange = LCluster.first;
const Cluster &RCluster = *R;
continue;
}
- if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
- Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
- Machine.onRLClose(LRange.getLow());
- ++L;
- ++R;
- continue;
- }
-
- if (LRange.isSingleNumber()) {
- Machine.onLOpen(LRange.getLow(), LCluster.second);
- Machine.onLClose(LRange.getLow());
- ++L;
- while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
- Machine.onLOpen(LRange.getLow(), LCluster.second);
- Machine.onLClose(LRange.getLow());
- ++L;
- }
- continue;
- } else if (RRange.isSingleNumber()) {
- Machine.onROpen(R->first.getLow(), R->second);
- Machine.onRClose(R->first.getHigh());
- ++R;
- while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
- Machine.onROpen(R->first.getLow(), R->second);
- Machine.onRClose(R->first.getHigh());
- ++R;
- }
- continue;
- } else
if (LRange.getLow() < RRange.getLow()) {
// May be opened in previous iteration.
if (!Machine.isLOpened())
Machine.onLOpen(LRange.getLow(), LCluster.second);
}
else
- Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
+ Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
if (LRange.getHigh() < RRange.getHigh()) {
Machine.onLClose(LRange.getHigh());
}
}
else {
- Machine.onRLClose(LRange.getHigh());
+ Machine.onLRClose(LRange.getHigh());
++L;
++R;
}
projects / oota-llvm.git / blobdiff