aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Support/IntegersSubset.h36
-rw-r--r--include/llvm/Support/IntegersSubsetMapping.h223
-rw-r--r--lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp15
-rw-r--r--lib/Transforms/Utils/LowerSwitch.cpp9
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp233
-rw-r--r--test/Transforms/SimplifyCFG/switch_create.ll2
-rw-r--r--unittests/Support/IntegersSubsetTest.cpp22
7 files changed, 329 insertions, 211 deletions
diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h
index bb9e769..06df793 100644
--- a/include/llvm/Support/IntegersSubset.h
+++ b/include/llvm/Support/IntegersSubset.h
@@ -182,7 +182,12 @@ protected:
IntType Low;
IntType High;
bool IsEmpty : 1;
- bool IsSingleNumber : 1;
+ enum Type {
+ SINGLE_NUMBER,
+ RANGE,
+ UNKNOWN
+ };
+ Type RangeType;
public:
typedef IntRange<IntType> self;
@@ -191,15 +196,30 @@ public:
IntRange() : IsEmpty(true) {}
IntRange(const self &RHS) :
Low(RHS.Low), High(RHS.High),
- IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
+ IsEmpty(RHS.IsEmpty), RangeType(RHS.RangeType) {}
IntRange(const IntType &C) :
- Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
+ Low(C), High(C), IsEmpty(false), RangeType(SINGLE_NUMBER) {}
IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
- IsEmpty(false), IsSingleNumber(Low == High) {}
+ IsEmpty(false), RangeType(UNKNOWN) {}
bool isEmpty() const { return IsEmpty; }
- bool isSingleNumber() const { return IsSingleNumber; }
+ bool isSingleNumber() const {
+ switch (RangeType) {
+ case SINGLE_NUMBER:
+ return true;
+ case RANGE:
+ return false;
+ case UNKNOWN:
+ default:
+ if (Low == High) {
+ const_cast<Type&>(RangeType) = SINGLE_NUMBER;
+ return true;
+ }
+ const_cast<Type&>(RangeType) = RANGE;
+ return false;
+ }
+ }
const IntType& getLow() const {
assert(!IsEmpty && "Range is empty.");
@@ -213,13 +233,13 @@ public:
bool operator<(const self &RHS) const {
assert(!IsEmpty && "Left range is empty.");
assert(!RHS.IsEmpty && "Right range is empty.");
+ if (Low < RHS.Low)
+ return true;
if (Low == RHS.Low) {
if (High > RHS.High)
return true;
return false;
}
- if (Low < RHS.Low)
- return true;
return false;
}
@@ -512,7 +532,7 @@ public:
e = Src.end(); i != e; ++i) {
const Range &R = *i;
std::vector<Constant*> r;
- if (R.isSingleNumber()) {
+ if (!R.isSingleNumber()) {
r.reserve(2);
// FIXME: Since currently we have ConstantInt based numbers
// use hack-conversion of IntItem to ConstantInt
diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index 87d0755..915c777 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -58,22 +58,16 @@ public:
protected:
- typedef std::list<Cluster> CaseItems;
+ typedef std::map<RangeEx, SuccessorClass*> 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 Sorted;
+ bool SingleNumbersOnly;
bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
return LItem->first.getHigh() >= RItem->first.getLow();
@@ -91,18 +85,6 @@ protected:
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,
@@ -213,7 +195,7 @@ protected:
}
}
- void onRLOpen(const IntTy &Pt,
+ void onLROpen(const IntTy &Pt,
SuccessorClass *LS,
SuccessorClass *RS) {
switch (State) {
@@ -229,7 +211,7 @@ protected:
OpenPt = Pt;
}
- void onRLClose(const IntTy &Pt) {
+ void onLRClose(const IntTy &Pt) {
switch (State) {
case INTERSECT_OPENED:
if (IntersectionMapping)
@@ -245,6 +227,48 @@ protected:
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:
@@ -256,15 +280,18 @@ public:
typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
typedef std::list<Case> Cases;
+ typedef typename Cases::iterator CasesIt;
+
+ IntegersSubsetMapping() : SingleNumbersOnly(true) {}
- 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) {
@@ -275,10 +302,36 @@ public:
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 // iRange.getLow() == jRange.getLow()
+ return true;
+ }
+ return false;
+ }
+
+
void optimize() {
if (Items.size() < 2)
return;
- sort();
CaseItems OldItems = Items;
Items.clear();
const IntTy *Low = &OldItems.begin()->first.getLow();
@@ -303,8 +356,6 @@ public:
}
RangeEx R(*Low, *High, Weight);
add(R, Successor);
- // We recollected the Items, but we kept it sorted.
- Sorted = true;
}
/// Adds a constant value.
@@ -323,8 +374,10 @@ public:
add(REx, S);
}
void add(const RangeEx &R, SuccessorClass *S = 0) {
- Items.push_back(std::make_pair(R, S));
- Sorted = false;
+ //Items.push_back(std::make_pair(R, S));
+ Items.insert(std::make_pair(R, S));
+ if (!R.isSingleNumber())
+ SingleNumbersOnly = false;
}
/// Adds all ranges and values from given ranges set to the current
@@ -337,9 +390,17 @@ public:
}
void add(self& RHS) {
- Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
+ //Items.insert(Items.begin(), RHS.Items.begin(), RHS.Items.end());
+ Items.insert(RHS.Items.begin(), RHS.Items.end());
+ if (!RHS.SingleNumbersOnly)
+ SingleNumbersOnly = false;
}
+ 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);
@@ -348,6 +409,34 @@ public:
/// Removes items from set.
void removeItem(RangeIterator i) { Items.erase(i); }
+ /// Moves whole case from current mapping to the NewMapping object.
+ 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;
+ }
+
+ /// Removes all clusters for given successor.
+ void removeCase(SuccessorClass *Succ) {
+ for (CaseItemIt i = Items.begin(); i != Items.end();)
+ if (i->second == Succ) {
+ Items.erase(i++);
+ } else
+ ++i;
+ }
+
+ /// Find successor that satisfies given value.
+ SuccessorClass *findSuccessor(const IntTy& Val) {
+ for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
+ if (i->first.isInRange(Val))
+ return i->second;
+ }
+ return 0;
+ }
+
/// Calculates the difference between this mapping and RHS.
/// THIS without RHS is placed into LExclude,
/// RHS without THIS is placed into RExclude,
@@ -355,10 +444,16 @@ public:
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();
- while (L != Items.end() && R != RHS.Items.end()) {
+ 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;
@@ -377,7 +472,36 @@ public:
++R;
continue;
}
+
+ if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
+ Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
+ Machine.onLRClose(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())
@@ -390,7 +514,7 @@ public:
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());
@@ -411,7 +535,7 @@ public:
}
}
else {
- Machine.onRLClose(LRange.getHigh());
+ Machine.onLRClose(LRange.getHigh());
++L;
++R;
}
@@ -441,7 +565,20 @@ public:
}
/// Builds the finalized case objects.
- void getCases(Cases& TheCases) {
+ void getCases(Cases& TheCases, bool PreventMerging = false) {
+ //FIXME: PreventMerging is a temporary parameter.
+ //Currently a set of passes is still knows nothing about
+ //switches with case ranges, and if these passes meet switch
+ //with complex case that crashs the application.
+ 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);
@@ -458,6 +595,22 @@ public:
return IntegersSubsetTy(Ranges);
}
+ /// Returns pointer to value of case if it is single-numbered or 0
+ /// in another case.
+ 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;
+ }
+
/// Returns true if there is no ranges and values inside.
bool empty() const { return Items.empty(); }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 957d00a..72e5769 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2450,22 +2450,23 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
size_t numCmps = 0;
for (Clusterifier::RangeIterator i = TheClusterifier.begin(),
e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- Clusterifier::Cluster &C = *i;
+ const Clusterifier::RangeEx &R = i->first;
+ MachineBasicBlock *MBB = i->second;
unsigned W = 0;
if (BPI) {
- W = BPI->getEdgeWeight(SI.getParent(), C.second->getBasicBlock());
+ W = BPI->getEdgeWeight(SI.getParent(), MBB->getBasicBlock());
if (!W)
W = 16;
- W *= C.first.Weight;
- BPI->setEdgeWeight(SI.getParent(), C.second->getBasicBlock(), W);
+ W *= R.Weight;
+ BPI->setEdgeWeight(SI.getParent(), MBB->getBasicBlock(), W);
}
// FIXME: Currently work with ConstantInt based numbers.
// Changing it to APInt based is a pretty heavy for this commit.
- Cases.push_back(Case(C.first.getLow().toConstantInt(),
- C.first.getHigh().toConstantInt(), C.second, W));
+ Cases.push_back(Case(R.getLow().toConstantInt(),
+ R.getHigh().toConstantInt(), MBB, W));
- if (C.first.getLow() != C.first.getHigh())
+ if (R.getLow() != R.getHigh())
// A range counts double, since it requires two compares.
++numCmps;
}
diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp
index 1547439..d2bd9d0 100644
--- a/lib/Transforms/Utils/LowerSwitch.cpp
+++ b/lib/Transforms/Utils/LowerSwitch.cpp
@@ -238,13 +238,14 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
size_t numCmps = 0;
for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(),
e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- IntegersSubsetToBB::Cluster &C = *i;
+ const IntegersSubsetToBB::RangeTy &R = i->first;
+ BasicBlock *S = i->second;
// FIXME: Currently work with ConstantInt based numbers.
// Changing it to APInt based is a pretty heavy for this commit.
- Cases.push_back(CaseRange(C.first.getLow().toConstantInt(),
- C.first.getHigh().toConstantInt(), C.second));
- if (C.first.isSingleNumber())
+ Cases.push_back(CaseRange(R.getLow().toConstantInt(),
+ R.getHigh().toConstantInt(), S));
+ if (R.isSingleNumber())
// A range counts double, since it requires two compares.
++numCmps;
}
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index f37ea91..4a58eb3 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -56,26 +56,12 @@ DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
namespace {
- /// ValueEqualityComparisonCase - Represents a case of a switch.
- struct ValueEqualityComparisonCase {
- ConstantInt *Value;
- BasicBlock *Dest;
-
- ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
- : Value(Value), Dest(Dest) {}
-
- bool operator<(ValueEqualityComparisonCase RHS) const {
- // Comparing pointers is ok as we only rely on the order for uniquing.
- return Value < RHS.Value;
- }
- };
-
class SimplifyCFGOpt {
const TargetData *const TD;
Value *isValueEqualityComparison(TerminatorInst *TI);
BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
- std::vector<ValueEqualityComparisonCase> &Cases);
+ IntegersSubsetToBB &Mapping);
bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
BasicBlock *Pred,
IRBuilder<> &Builder);
@@ -532,72 +518,25 @@ Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
/// decode all of the 'cases' that it represents and return the 'default' block.
BasicBlock *SimplifyCFGOpt::
GetValueEqualityComparisonCases(TerminatorInst *TI,
- std::vector<ValueEqualityComparisonCase>
- &Cases) {
+ IntegersSubsetToBB &Mapping) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
- Cases.reserve(SI->getNumCases());
- for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
- Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
- i.getCaseSuccessor()));
+ for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
+ i != e; ++i)
+ Mapping.add(i.getCaseValueEx(), i.getCaseSuccessor());
return SI->getDefaultDest();
}
-
+
BranchInst *BI = cast<BranchInst>(TI);
ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
- BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
- Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
- TD),
- Succ));
+ IntegersSubsetToBB Builder;
+
+ Mapping.add(
+ IntItem::fromConstantInt(GetConstantInt(ICI->getOperand(1), TD)),
+ BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE));
+
return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
}
-
-/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
-/// in the list that match the specified block.
-static void EliminateBlockCases(BasicBlock *BB,
- std::vector<ValueEqualityComparisonCase> &Cases) {
- for (unsigned i = 0, e = Cases.size(); i != e; ++i)
- if (Cases[i].Dest == BB) {
- Cases.erase(Cases.begin()+i);
- --i; --e;
- }
-}
-
-/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
-/// well.
-static bool
-ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
- std::vector<ValueEqualityComparisonCase > &C2) {
- std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
-
- // Make V1 be smaller than V2.
- if (V1->size() > V2->size())
- std::swap(V1, V2);
-
- if (V1->size() == 0) return false;
- if (V1->size() == 1) {
- // Just scan V2.
- ConstantInt *TheVal = (*V1)[0].Value;
- for (unsigned i = 0, e = V2->size(); i != e; ++i)
- if (TheVal == (*V2)[i].Value)
- return true;
- }
-
- // Otherwise, just sort both lists and compare element by element.
- array_pod_sort(V1->begin(), V1->end());
- array_pod_sort(V2->begin(), V2->end());
- unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
- while (i1 != e1 && i2 != e2) {
- if ((*V1)[i1].Value == (*V2)[i2].Value)
- return true;
- if ((*V1)[i1].Value < (*V2)[i2].Value)
- ++i1;
- else
- ++i2;
- }
- return false;
-}
-
/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
/// terminator instruction and its block is known to only have a single
/// predecessor block, check to see if that predecessor is also a value
@@ -616,23 +555,27 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
if (ThisVal != PredVal) return false; // Different predicates.
// Find out information about when control will move from Pred to TI's block.
- std::vector<ValueEqualityComparisonCase> PredCases;
+ IntegersSubsetToBB PredCases;
BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
PredCases);
- EliminateBlockCases(PredDef, PredCases); // Remove default from cases.
+ // Remove default from cases.
+ PredCases.removeCase(PredDef);
+
// Find information about how control leaves this block.
- std::vector<ValueEqualityComparisonCase> ThisCases;
+ IntegersSubsetToBB ThisCases;
BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
- EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases.
+ // Remove default from cases.
+ ThisCases.removeCase(ThisDef);
+
// If TI's block is the default block from Pred's comparison, potentially
// simplify TI based on this knowledge.
if (PredDef == TI->getParent()) {
// If we are here, we know that the value is none of those cases listed in
// PredCases. If there are any cases in ThisCases that are in PredCases, we
// can simplify TI.
- if (!ValuesOverlap(PredCases, ThisCases))
+ if (!PredCases.isOverlapped(ThisCases))
return false;
if (isa<BranchInst>(TI)) {
@@ -644,7 +587,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
(void) NI;
// Remove PHI node entries for the dead edge.
- ThisCases[0].Dest->removePredecessor(TI->getParent());
+ ThisCases.begin()->second->removePredecessor(TI->getParent());
DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
<< "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
@@ -655,45 +598,45 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
SwitchInst *SI = cast<SwitchInst>(TI);
// Okay, TI has cases that are statically dead, prune them away.
- SmallPtrSet<Constant*, 16> DeadCases;
- for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
- DeadCases.insert(PredCases[i].Value);
+ IRBuilder<> CodeBuilder(SI);
+ CodeBuilder.SetCurrentDebugLocation(SI->getDebugLoc());
DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
<< "Through successor TI: " << *TI);
- for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
- --i;
- if (DeadCases.count(i.getCaseValue())) {
- i.getCaseSuccessor()->removePredecessor(TI->getParent());
- SI->removeCase(i);
- }
- }
-
- DEBUG(dbgs() << "Leaving: " << *TI << "\n");
+ // Okay, TI has cases that are statically dead, prune them away.
+ IntegersSubsetToBB NewThisCases;
+ IntegersSubsetToBB WastedCases;
+ ThisCases.diff(&NewThisCases, &WastedCases, 0, PredCases);
+
+ IntegersSubsetToBB::Cases Cases;
+ NewThisCases.getCases(Cases, true/*temporary prevent complex cases*/);
+
+ SwitchInst *NewSI =
+ CodeBuilder.CreateSwitch(ThisVal, SI->getDefaultDest(), Cases.size());
+
+ for (IntegersSubsetToBB::RangeIterator i = WastedCases.begin(),
+ e = WastedCases.end(); i != e; ++i)
+ i->second->removePredecessor(TI->getParent());
+
+ for (IntegersSubsetToBB::CasesIt i = Cases.begin(), e = Cases.end();
+ i != e; ++i)
+ NewSI->addCase(i->second, i->first);
+
+ EraseTerminatorInstAndDCECond(SI);
+ DEBUG(dbgs() << "Leaving: " << *NewSI << "\n");
return true;
}
// Otherwise, TI's block must correspond to some matched value. Find out
// which value (or set of values) this is.
- ConstantInt *TIV = 0;
BasicBlock *TIBB = TI->getParent();
- for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
- if (PredCases[i].Dest == TIBB) {
- if (TIV != 0)
- return false; // Cannot handle multiple values coming to this block.
- TIV = PredCases[i].Value;
- }
- assert(TIV && "No edge from pred to succ?");
+ const IntItem* TIVIntITem = PredCases.getCaseSingleNumber(TIBB);
+ assert(TIVIntITem && "No edge from pred to succ?");
// Okay, we found the one constant that our value can be if we get into TI's
// BB. Find out which successor will unconditionally be branched to.
- BasicBlock *TheRealDest = 0;
- for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
- if (ThisCases[i].Value == TIV) {
- TheRealDest = ThisCases[i].Dest;
- break;
- }
+ BasicBlock *TheRealDest = ThisCases.findSuccessor(*TIVIntITem);
// If not handled by any explicit cases, it is handled by the default case.
if (TheRealDest == 0) TheRealDest = ThisDef;
@@ -759,10 +702,10 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
// Figure out which 'cases' to copy from SI to PSI.
- std::vector<ValueEqualityComparisonCase> BBCases;
+ IntegersSubsetToBB BBCases;
BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
- std::vector<ValueEqualityComparisonCase> PredCases;
+ IntegersSubsetToBB PredCases;
BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
// Based on whether the default edge from PTI goes to BB or not, fill in
@@ -773,61 +716,51 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
if (PredDefault == BB) {
// If this is the default destination from PTI, only the edges in TI
// that don't occur in PTI, or that branch to BB will be activated.
- std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
- for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
- if (PredCases[i].Dest != BB)
- PTIHandled.insert(PredCases[i].Value);
- else {
- // The default destination is BB, we don't need explicit targets.
- std::swap(PredCases[i], PredCases.back());
- PredCases.pop_back();
- --i; --e;
- }
-
- // Reconstruct the new switch statement we will be building.
+
+ PredCases.removeCase(BB);
+ IntegersSubsetToBB NewBBCases;
+ BBCases.diff(&NewBBCases, 0, 0, PredCases);
+ PredCases.add(NewBBCases);
+ for (IntegersSubsetToBB::RangeIterator i = NewBBCases.begin(),
+ e = NewBBCases.end(); i != e; ++i)
+ NewSuccessors.push_back(i->second);
+
+ // Replace the default if needed.
if (PredDefault != BBDefault) {
PredDefault->removePredecessor(Pred);
PredDefault = BBDefault;
NewSuccessors.push_back(BBDefault);
}
- for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
- if (!PTIHandled.count(BBCases[i].Value) &&
- BBCases[i].Dest != BBDefault) {
- PredCases.push_back(BBCases[i]);
- NewSuccessors.push_back(BBCases[i].Dest);
- }
} else {
// If this is not the default destination from PSI, only the edges
// in SI that occur in PSI with a destination of BB will be
// activated.
- std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
- for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
- if (PredCases[i].Dest == BB) {
- PTIHandled.insert(PredCases[i].Value);
- std::swap(PredCases[i], PredCases.back());
- PredCases.pop_back();
- --i; --e;
- }
+ IntegersSubsetToBB BBPredCase;
+ PredCases.detachCase(BBPredCase, BB);
+ IntegersSubsetToBB CasesWithBBDef;
+ IntegersSubsetToBB InharitedCases;
// Okay, now we know which constants were sent to BB from the
// predecessor. Figure out where they will all go now.
- for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
- if (PTIHandled.count(BBCases[i].Value)) {
- // If this is one we are capable of getting...
- PredCases.push_back(BBCases[i]);
- NewSuccessors.push_back(BBCases[i].Dest);
- PTIHandled.erase(BBCases[i].Value);// This constant is taken care of
- }
-
+ if (!BBPredCase.empty()) {
+ BBCases.diff(
+ 0, // LHS excl RHS
+ &InharitedCases, // intersection
+ &CasesWithBBDef, // RHS excl LHS
+ BBPredCase); // RHS.
+ }
+ PredCases.add(InharitedCases);
+ for (IntegersSubsetToBB::RangeIterator i = InharitedCases.begin(),
+ e = InharitedCases.end();
+ i != e; ++i)
+ NewSuccessors.push_back(i->second);
+
// If there are any constants vectored to BB that TI doesn't handle,
// they must go to the default destination of TI.
- for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I =
- PTIHandled.begin(),
- E = PTIHandled.end(); I != E; ++I) {
- PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
+ PredCases.add(CasesWithBBDef, BBDefault);
+ for (unsigned i = 0, e = CasesWithBBDef.size(); i != e; ++i)
NewSuccessors.push_back(BBDefault);
- }
}
// Okay, at this point, we know which new successor Pred will get. Make
@@ -848,8 +781,12 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
PredCases.size());
NewSI->setDebugLoc(PTI->getDebugLoc());
- for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
- NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
+ IntegersSubsetToBB::Cases Cases;
+ PredCases.getCases(Cases, true/*temporary prevent complex case*/);
+
+ for (IntegersSubsetToBB::CasesIt i = Cases.begin(), e = Cases.end();
+ i != e; ++i)
+ NewSI->addCase(i->second, i->first);
EraseTerminatorInstAndDCECond(PTI);
diff --git a/test/Transforms/SimplifyCFG/switch_create.ll b/test/Transforms/SimplifyCFG/switch_create.ll
index 546cc75..c62afd5 100644
--- a/test/Transforms/SimplifyCFG/switch_create.ll
+++ b/test/Transforms/SimplifyCFG/switch_create.ll
@@ -82,8 +82,8 @@ lor.end: ; preds = %lor.rhs, %lor.lhs.f
; CHECK: @test4
; CHECK: switch i8 %c, label %lor.rhs [
-; CHECK: i8 62, label %lor.end
; CHECK: i8 34, label %lor.end
+; CHECK: i8 62, label %lor.end
; CHECK: i8 92, label %lor.end
; CHECK: ]
}
diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp
index 5d1dde4..a103161 100644
--- a/unittests/Support/IntegersSubsetTest.cpp
+++ b/unittests/Support/IntegersSubsetTest.cpp
@@ -193,20 +193,20 @@ namespace {
const unsigned_ranges IntersectRes,
unsigned IntersectResSize
) {
-
+ unsigned successors[2] = {0, 1};
Mapping::RangesCollection Ranges;
Mapping LHSMapping;
for (unsigned i = 0; i < LSize; ++i)
Ranges.push_back(Range(Int(LHS[i][0]), Int(LHS[i][1])));
- LHSMapping.add(Ranges);
+ LHSMapping.add(Ranges, &successors[0]);
Ranges.clear();
Mapping RHSMapping;
for (unsigned i = 0; i < RSize; ++i)
Ranges.push_back(Range(Int(RHS[i][0]), Int(RHS[i][1])));
- RHSMapping.add(Ranges);
+ RHSMapping.add(Ranges, &successors[1]);
Mapping LExclude, Intersection;
@@ -217,8 +217,10 @@ namespace {
unsigned i = 0;
for (Mapping::RangeIterator rei = LExclude.begin(),
- e = LExclude.end(); rei != e; ++rei, ++i)
+ e = LExclude.end(); rei != e; ++rei, ++i) {
EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
+ EXPECT_EQ(rei->second, &successors[0]);
+ }
} else
EXPECT_TRUE(LExclude.empty());
@@ -227,8 +229,10 @@ namespace {
unsigned i = 0;
for (Mapping::RangeIterator ii = Intersection.begin(),
- e = Intersection.end(); ii != e; ++ii, ++i)
+ e = Intersection.end(); ii != e; ++ii, ++i) {
EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1]));
+ EXPECT_EQ(ii->second, &successors[0]);
+ }
} else
EXPECT_TRUE(Intersection.empty());
@@ -241,9 +245,11 @@ namespace {
EXPECT_EQ(LExclude.size(), ExcludeResSize);
unsigned i = 0;
- for (Mapping::RangeIterator rei = LExclude.begin(),
- e = LExclude.end(); rei != e; ++rei, ++i)
- EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
+ for (Mapping::RangeIterator lei = LExclude.begin(),
+ e = LExclude.end(); lei != e; ++lei, ++i) {
+ EXPECT_EQ(lei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
+ EXPECT_EQ(lei->second, &successors[0]);
+ }
} else
EXPECT_TRUE(LExclude.empty());
}
generated by cgit v1.1 at 2024-10-31 00:32:23 +0000