IntegersSubsetMapping.h [plain text]
#ifndef CRSBUILDER_H_
#define CRSBUILDER_H_
#include "llvm/Support/IntegersSubset.h"
#include <list>
#include <map>
#include <vector>
namespace llvm {
template <class SuccessorClass,
class IntegersSubsetTy = IntegersSubset,
class IntTy = IntItem>
class IntegersSubsetMapping {
public:
typedef IntRange<IntTy> RangeTy;
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) :
RangeTy(L, H), Weight(W) {}
unsigned Weight;
};
typedef std::pair<RangeEx, SuccessorClass*> Cluster;
typedef std::list<RangeTy> RangesCollection;
typedef typename RangesCollection::iterator RangesCollectionIt;
typedef typename RangesCollection::const_iterator RangesCollectionConstIt;
typedef IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> self;
protected:
typedef std::list<Cluster> CaseItems;
typedef typename CaseItems::iterator CaseItemIt;
typedef typename CaseItems::const_iterator CaseItemConstIt;
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 Sorted;
bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
return LItem->first.getHigh() >= RItem->first.getLow();
}
bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
if (LItem->second != RItem->second) {
assert(!isIntersected(LItem, RItem) &&
"Intersected items with different successors!");
return false;
}
APInt RLow = RItem->first.getLow();
if (RLow != APInt::getNullValue(RLow.getBitWidth()))
--RLow;
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,
R_OPENED,
ALL_IS_CLOSED
};
class DiffStateMachine {
DiffProcessState State;
IntTy OpenPt;
SuccessorClass *CurrentLSuccessor;
SuccessorClass *CurrentRSuccessor;
self *LeftMapping;
self *IntersectionMapping;
self *RightMapping;
public:
typedef
IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
DiffStateMachine(MappingTy *L,
MappingTy *Intersection,
MappingTy *R) :
State(ALL_IS_CLOSED),
LeftMapping(L),
IntersectionMapping(Intersection),
RightMapping(R)
{}
void onLOpen(const IntTy &Pt, SuccessorClass *S) {
switch (State) {
case R_OPENED:
if (Pt > OpenPt && RightMapping)
RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
State = INTERSECT_OPENED;
break;
case ALL_IS_CLOSED:
State = L_OPENED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
CurrentLSuccessor = S;
OpenPt = Pt;
}
void onLClose(const IntTy &Pt) {
switch (State) {
case L_OPENED:
assert(Pt >= OpenPt &&
"Subset is not sorted or contains overlapped ranges");
if (LeftMapping)
LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
State = ALL_IS_CLOSED;
break;
case INTERSECT_OPENED:
if (IntersectionMapping)
IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
OpenPt = Pt + 1;
State = R_OPENED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
}
void onROpen(const IntTy &Pt, SuccessorClass *S) {
switch (State) {
case L_OPENED:
if (Pt > OpenPt && LeftMapping)
LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
State = INTERSECT_OPENED;
break;
case ALL_IS_CLOSED:
State = R_OPENED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
CurrentRSuccessor = S;
OpenPt = Pt;
}
void onRClose(const IntTy &Pt) {
switch (State) {
case R_OPENED:
assert(Pt >= OpenPt &&
"Subset is not sorted or contains overlapped ranges");
if (RightMapping)
RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
State = ALL_IS_CLOSED;
break;
case INTERSECT_OPENED:
if (IntersectionMapping)
IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
OpenPt = Pt + 1;
State = L_OPENED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
}
void onLROpen(const IntTy &Pt,
SuccessorClass *LS,
SuccessorClass *RS) {
switch (State) {
case ALL_IS_CLOSED:
State = INTERSECT_OPENED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
CurrentLSuccessor = LS;
CurrentRSuccessor = RS;
OpenPt = Pt;
}
void onLRClose(const IntTy &Pt) {
switch (State) {
case INTERSECT_OPENED:
if (IntersectionMapping)
IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
State = ALL_IS_CLOSED;
break;
default:
assert(0 && "Got unexpected point.");
break;
}
}
bool isLOpened() { return State == L_OPENED; }
bool isROpened() { return State == R_OPENED; }
};
public:
typedef CaseItemIt RangeIterator;
typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
typedef std::list<Case> Cases;
typedef typename Cases::iterator CasesIt;
IntegersSubsetMapping() {
Sorted = false;
}
bool verify() {
RangeIterator DummyErrItem;
return verify(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) {
errItem = j;
return false;
}
}
return true;
}
bool isOverlapped(self &RHS) {
if (Items.empty() || RHS.empty())
return true;
for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
const RangeTy &LRange = L->first;
const RangeTy &RRange = R->first;
if (LRange.getLow() > RRange.getLow()) {
if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
++R;
else
return true;
} else if (LRange.getLow() < RRange.getLow()) {
if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
++L;
else
return true;
} else return true;
}
return false;
}
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 = 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 += j->first.Weight;
if (*CurHigh > *High)
High = CurHigh;
} else {
RangeEx R(*Low, *High, Weight);
add(R, Successor);
Low = &j->first.getLow();
High = &j->first.getHigh();
Weight = j->first.Weight;
Successor = j->second;
}
}
RangeEx R(*Low, *High, Weight);
add(R, Successor);
Sorted = true;
}
void add(const IntTy &C, SuccessorClass *S = 0) {
RangeTy R(C);
add(R, S);
}
void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
RangeTy R(Low, High);
add(R, S);
}
void add(const RangeTy &R, SuccessorClass *S = 0) {
RangeEx REx = R;
add(REx, S);
}
void add(const RangeEx &R, SuccessorClass *S = 0) {
Items.push_back(std::make_pair(R, S));
Sorted = false;
}
void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0,
unsigned Weight = 0) {
unsigned ItemWeight = 1;
if (Weight)
ItemWeight = Weight / CRS.getNumItems();
for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
RangeTy R = CRS.getItem(i);
RangeEx REx(R, ItemWeight);
add(REx, S);
}
}
void add(self& RHS) {
Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
}
void add(self& RHS, SuccessorClass *S) {
for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
add(i->first, S);
}
void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
add(*i, S);
}
void removeItem(RangeIterator i) { Items.erase(i); }
void detachCase(self& NewMapping, SuccessorClass *Succ) {
for (CaseItemIt i = Items.begin(); i != Items.end();)
if (i->second == Succ) {
NewMapping.add(i->first, i->second);
Items.erase(i++);
} else
++i;
}
void removeCase(SuccessorClass *Succ) {
for (CaseItemIt i = Items.begin(); i != Items.end();)
if (i->second == Succ) {
Items.erase(i++);
} else
++i;
}
SuccessorClass *findSuccessor(const IntTy& Val) {
for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
if (i->first.isInRange(Val))
return i->second;
}
return 0;
}
void diff(self *LExclude, self *Intersection, self *RExclude,
const self& RHS) {
DiffStateMachine Machine(LExclude, Intersection, RExclude);
CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
while (L != Items.end() && R != RHS.Items.end()) {
const Cluster &LCluster = *L;
const RangeEx &LRange = LCluster.first;
const Cluster &RCluster = *R;
const RangeEx &RRange = RCluster.first;
if (LRange.getHigh() < RRange.getLow()) {
Machine.onLOpen(LRange.getLow(), LCluster.second);
Machine.onLClose(LRange.getHigh());
++L;
continue;
}
if (LRange.getLow() > RRange.getHigh()) {
Machine.onROpen(RRange.getLow(), RCluster.second);
Machine.onRClose(RRange.getHigh());
++R;
continue;
}
if (LRange.getLow() < RRange.getLow()) {
if (!Machine.isLOpened())
Machine.onLOpen(LRange.getLow(), LCluster.second);
Machine.onROpen(RRange.getLow(), RCluster.second);
}
else if (RRange.getLow() < LRange.getLow()) {
if (!Machine.isROpened())
Machine.onROpen(RRange.getLow(), RCluster.second);
Machine.onLOpen(LRange.getLow(), LCluster.second);
}
else
Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
if (LRange.getHigh() < RRange.getHigh()) {
Machine.onLClose(LRange.getHigh());
++L;
while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
Machine.onLOpen(L->first.getLow(), L->second);
Machine.onLClose(L->first.getHigh());
++L;
}
}
else if (RRange.getHigh() < LRange.getHigh()) {
Machine.onRClose(RRange.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;
}
}
else {
Machine.onLRClose(LRange.getHigh());
++L;
++R;
}
}
if (L != Items.end()) {
if (Machine.isLOpened()) {
Machine.onLClose(L->first.getHigh());
++L;
}
if (LExclude)
while (L != Items.end()) {
LExclude->add(L->first, L->second);
++L;
}
} else if (R != RHS.Items.end()) {
if (Machine.isROpened()) {
Machine.onRClose(R->first.getHigh());
++R;
}
if (RExclude)
while (R != RHS.Items.end()) {
RExclude->add(R->first, R->second);
++R;
}
}
}
void getCases(Cases& TheCases, bool PreventMerging = false) {
if (PreventMerging) {
for (RangeIterator i = this->begin(); i != this->end(); ++i) {
RangesCollection SingleRange;
SingleRange.push_back(i->first);
TheCases.push_back(std::make_pair(i->second,
IntegersSubsetTy(SingleRange)));
}
return;
}
CRSMap TheCRSMap;
for (RangeIterator i = this->begin(); i != this->end(); ++i)
TheCRSMap[i->second].push_back(i->first);
for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
}
IntegersSubsetTy getCase() {
RangesCollection Ranges;
for (RangeIterator i = this->begin(); i != this->end(); ++i)
Ranges.push_back(i->first);
return IntegersSubsetTy(Ranges);
}
const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
const IntTy* Res = 0;
for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
if (i->second == Succ) {
if (!i->first.isSingleNumber())
return 0;
if (Res)
return 0;
else
Res = &(i->first.getLow());
}
return Res;
}
bool empty() const { return Items.empty(); }
void clear() {
Items.clear();
}
unsigned size() const {
return Items.size();
}
RangeIterator begin() { return Items.begin(); }
RangeIterator end() { return Items.end(); }
};
class BasicBlock;
typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
}
#endif